Upper Bounds for All and Max-gain Policy Iteration Algorithms on Deterministic MDPs

2022/11/28 by Ritesh Goenka, Goenka, Ritesh, Eashan Gupta +9 · 1 citation
Computer Science · #Formal Methods in Verification

paper · pdf · doi:10.48550/arxiv.2211.15602

Abstract

Policy Iteration (PI) is a widely used family of algorithms to compute optimal policies for Markov Decision Problems (MDPs). We derive upper bounds on the running time of PI on Deterministic MDPs (DMDPs): the class of MDPs in which every state-action pair has a unique next state. Our results include a non-trivial upper bound that applies to the entire family of PI algorithms; another to all "max-gain" switching variants; and affirmation that a conjecture regarding Howard's PI on MDPs is true for DMDPs. Our analysis is based on certain graph-theoretic results, which may be of independent interest.

Cited by

• Howard's Policy Iteration is Subexponential for Deterministic Markov Decision Problems with Rewards of Fixed Bit-size and Arbitrary Discount Factor

Related

• Lower Bounds for Policy Iteration on Multi-action MDPs
• Improved bound on the worst case complexity of Policy Iteration
• Howard's Policy Iteration is Subexponential for Deterministic Markov Decision Problems with Rewards of Fixed Bit-size and Arbitrary Discount Factor
• Lower Bound on Howard Policy Iteration for Deterministic Markov Decision Processes
• Improved and Generalized Upper Bounds on the Complexity of Policy Iteration