Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning

Abstract

We study the online estimation of the optimal policy of a Markov decision process (MDP). We propose a class of Stochastic Primal-Dual (SPD) methods which exploit the inherent minimax duality of Bellman equations. The SPD methods update a few coordinates of the value and policy estimates as a new state transition is observed. These methods use small storage and has low computational complexity per iteration. The SPD methods find an absolute-$\epsilon$-optimal policy, with high probability, using $\mathcal{O}\left(\frac{|\mathcal{S}{|}^4|\mathcal{A}{|}^2{\sigma }^2}{(1-\gamma {)}^6{\epsilon }^2}\right)$ iterations/samples for the infinite-horizon discounted-reward MDP and $\mathcal{O}\left(\frac{|\mathcal{S}{|}^4|\mathcal{A}{|}^2{H}^6{\sigma }^2}{{\epsilon }^2}\right)$ for the finite-horizon MDP.

References in corpus (3)

• On Lower Bounds for Regret in Reinforcement Learning
• Proximal Reinforcement Learning: A New Theory of Sequential Decision Making in Primal-Dual Spaces
• Linear Programming for Large-Scale Markov Decision Problems

Cited by in corpus (21)

• Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems
• Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimization
• AlgaeDICE: Policy Gradient from Arbitrary Experience
• Primal-Dual $\pi$ Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems
• Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems
• Reinforcement Learning via Fenchel-Rockafellar Duality
• Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Running Time
• A Primal-Dual Approach to Constrained Markov Decision Processes
• Doubly Robust Bias Reduction in Infinite Horizon Off-Policy Estimation
• Cautious Reinforcement Learning via Distributional Risk in the Dual Domain
• Efficient Planning in Large MDPs with Weak Linear Function Approximation
• Stochastic Primal-Dual Q-Learning
• Primal-Dual Distributed Temporal Difference Learning
• Deep Primal-Dual Reinforcement Learning: Accelerating Actor-Critic using Bellman Duality
• Privacy-preserving Q-Learning with Functional Noise in Continuous State Spaces
• Generalization Bounds for Stochastic Saddle Point Problems
• A Provably Efficient Sample Collection Strategy for Reinforcement Learning
• A Reduction from Reinforcement Learning to No-Regret Online Learning
• Asynchronous Optimization over Weakly Coupled Renewal Systems
• Near Optimal Policy Optimization via REPS
• Voting-Based Multi-Agent Reinforcement Learning for Intelligent IoT