Randomization for Faster Exact Optimization of Discounted Markov Decision Processes
Provides faster exact algorithms for a fundamental problem in reinforcement learning and operations research, benefiting practitioners who need precise solutions.
The paper presents faster deterministic and randomized algorithms for exactly solving discounted Markov Decision Processes by reducing the problem to policy evaluation and approximate optimization, achieving improved computational complexity.
We provide faster deterministic and randomized algorithms for exactly solving discounted Markov Decision Processes (DMDPs). We obtain our results by efficiently reducing computing optimal values and policies in DMDPs to the easier tasks of policy evaluation and computing approximately optimal values in DMDPs. We provide both a straightforward deterministic reduction and a more efficient randomized variant that, together with advances in approximately solving DMDPs, yield our results.