Optimistic Policy Iteration for MDPs with Acyclic Transient State Structure

2021/01/29 by Joseph Lubars, Anna Winnicki, Lubars, Joseph +5 · 1 citation
Computer Science · #Reinforcement Learning in Robotics #Formal Methods in Verification #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.2102.00030

Abstract

We consider Markov Decision Processes (MDPs) in which every stationary policy induces the same graph structure for the underlying Markov chain and further, the graph has the following property: if we replace each recurrent class by a node, then the resulting graph is acyclic. For such MDPs, we prove the convergence of the stochastic dynamics associated with a version of optimistic policy iteration (OPI), suggested in Tsitsiklis (2002), in which the values associated with all the nodes visited during each iteration of the OPI are updated.

Citations

• Provably Efficient Reinforcement Learning with Linear Function Approximation

Cited by

• Convergence of Monte Carlo Optimistic Policy Iteration: Beyond Uniform State-Action Updates

Related

• On-line Policy Iteration with Policy Switching for Markov Decision Processes
• Convergence of Fast Policy Iteration in Markov Games and Robust MDPs
• Inexact Policy Iteration Methods for Large-Scale Markov Decision Processes
• Structure Matters: Dynamic Policy Gradient
• On the Convergence of Modified Policy Iteration in Risk Sensitive Exponential Cost Markov Decision Processes