Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Running Time

Abstract

We propose a novel randomized linear programming algorithm for approximating the optimal policy of the discounted Markov decision problem. By leveraging the value-policy duality and binary-tree data structures, the algorithm adaptively samples state-action-state transitions and makes exponentiated primal-dual updates. We show that it finds an $\epsilon$-optimal policy using nearly-linear run time in the worst case. When the Markov decision process is ergodic and specified in some special data formats, the algorithm finds an $\epsilon$-optimal policy using run time linear in the total number of state-action pairs, which is sublinear in the input size. These results provide a new venue and complexity benchmarks for solving stochastic dynamic programs.

References in corpus (4)

• On the Complexity of Policy Iteration
• Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning
• Randomized First-Order Methods for Saddle Point Optimization
• Lower Bound On the Computational Complexity of Discounted Markov Decision Problems

Cited by in corpus (13)

• Primal-Dual $\pi$ Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems
• Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal
• Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity
• Reinforcement Learning via Fenchel-Rockafellar Duality
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity
• Off-Policy Evaluation via the Regularized Lagrangian
• Lower Bound On the Computational Complexity of Discounted Markov Decision Problems
• Cautious Reinforcement Learning via Distributional Risk in the Dual Domain
• Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs
• Navigating to the Best Policy in Markov Decision Processes
• Gap-Dependent Unsupervised Exploration for Reinforcement Learning
• Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes
• Near Optimal Policy Optimization via REPS