Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning

2016/12/08 by Yi‐Chen Chen, Mengdi Wang, Chen, Yichen +1 · 6 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Neural Networks and Applications #Optimization and Control (math.OC) #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.1612.02516

openalex publication_date 2016/12/08 · openalex created_date 2017/01/06 · openalex updated_date 2026/07/28

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-ε-optimal policy, with high probability, using O((|S|⁴ |A|²σ² )/((1-γ)⁶ε²) ) iterations/samples for the infinite-horizon discounted-reward MDP and O((|S|⁴ |A|²H⁶σ² )/(ε²) ) for the finite-horizon MDP.

Citations

• Stochastic Approximation: A Dynamical Systems Viewpoint
• Linear Programming for Large-Scale Markov Decision Problems
• On Lower Bounds for Regret in Reinforcement Learning

Cited by

• Realizable Abstractions: Near-Optimal Hierarchical Reinforcement Learning
• Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Duality
• A Two-Timescale Primal-Dual Framework for Reinforcement Learning via Online Dual Variable Guidance
• Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimization
• Privacy-preserving Q-Learning with Functional Noise in Continuous State Spaces
• Doubly Robust Bias Reduction in Infinite Horizon Off-Policy Estimation

Related

• Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems
• Deep Primal-Dual Reinforcement Learning: Accelerating Actor-Critic using Bellman Duality
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss
• A Two-Timescale Primal-Dual Framework for Reinforcement Learning via Online Dual Variable Guidance
• Online Reinforcement Learning of Optimal Threshold Policies for Markov\n Decision Processes