560 citations · 3.3k across the 60 of their papers we have counts for
3 papers · 2 filters
On the Complexity of Solving Markov Decision Problems
Michael L. Littman, Thomas L. Dean, Leslie Pack Kaelbling
Markov decision problems (MDPs) provide the foundations for a number of problems of interest to AI researchers studying automated planning and reinforcement learning. In this paper…
The Complexity of Plan Existence and Evaluation in Probabilistic Domains
Judy Goldsmith, Michael L. Littman, Martin Mundhenk
We examine the computational complexity of testing and finding small plans in probabilistic planning domains with succinct representations. We find that many problems of interest a…
Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processes
Anthony R. Cassandra, Michael L. Littman, Nevin Lianwen Zhang
Most exact algorithms for general partially observable Markov decision processes (POMDPs) use a form of dynamic programming in which a piecewise-linear and convex representation of…