Grad research talk: Heuristic Approaches for Planning in Large Scale MDPs
Many real-world sequential decision problems have both concurrency of action choices and uncertainty in the resulting transitions, leading to large scale combinatorial optimization problems. In this talk, I will show that even a slight increase in problems size leads to failure of most state of art algorithms, when addressing such problems. I will describe heuristic approaches from our recent work that address some of these limitations. Our heuristics use notions of aggregation and independence assumptions to yield approximate but scalable solvers for the optimization problems. The algorithms perform well across a range of challenging benchmark problems, scaling well beyond state of the art.