Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning
Not on the map. Why?
Abstract (arXiv)
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 Oleft(frac|S|4 |A|2σ2 (1-γ)6ε2 right) iterations/samples for the infinite-horizon discounted-reward MDP and Oleft(frac|S|4 |A|2H6σ2 ε2 right) for the finite-horizon MDP.
Key facts. Cited by 15 papers in the map (data through 7 Oct 2026). First posted on arXiv 8 Dec 2016.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2020: 1; 2021: 4; 2022: 3; 2023: 1; 2024: 1; 2025: 3; 2026: 2.
15 papers.
Sort:
By area:
- 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problemscited by 1,873
- 2022What is a Good Metric to Study Generalization of Minimax Learners?cited by 16
- 2023Robust Markov Decision Processes without Model Estimationcited by 11
- 2021New Versions of Gradient Temporal Difference Learningcited by 6
- 2025Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Dualitycited by 4
- 2021Model-Based Safe Reinforcement Learning with Time-Varying State and Control Constraints: An Application to Intelligent Vehiclescited by 3
- 2021Learning to Act Safely with Limited Exposure and Almost Sure Certaintycited by 2
- 2024Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learningcited by 2
- 2021Near Optimal Policy Optimization via REPScited by 1
- 2022Provably Efficient Convergence of Primal-Dual Actor-Critic with Nonlinear Function Approximationcited by 1
- 2022Lagrangian Method for Q-Function Learning (with Applications to Machine Translation)cited by 1
- 2026Value Mirror Descent for Reinforcement Learningcited by 1
3 more
- 2025A Two-Timescale Primal-Dual Framework for Reinforcement Learning via Online Dual Variable Guidancecited by 0
- 2025Realizable Abstractions: Near-Optimal Hierarchical Reinforcement Learningcited by 0
- 2026R-GTD: A Geometric Analysis of Gradient Temporal-Difference Learning in Singular Regimescited by 0
- 2026Value Mirror Descent for Reinforcement Learning7 Apr 2026
- 2026R-GTD: A Geometric Analysis of Gradient Temporal-Difference Learning in Singular Regimes28 Jan 2026
- 2025Realizable Abstractions: Near-Optimal Hierarchical Reinforcement Learning4 Dec 2025
- 2025Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Duality24 Aug 2025
- 2025A Two-Timescale Primal-Dual Framework for Reinforcement Learning via Online Dual Variable Guidance7 May 2025
- 2024Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learning16 Feb 2024
- 2023Robust Markov Decision Processes without Model Estimation2 Feb 2023
- 2022Lagrangian Method for Q-Function Learning (with Applications to Machine Translation)22 Jul 2022
- 2022What is a Good Metric to Study Generalization of Minimax Learners?9 Jun 2022
- 2022Provably Efficient Convergence of Primal-Dual Actor-Critic with Nonlinear Function Approximation28 Feb 2022
- 2021Model-Based Safe Reinforcement Learning with Time-Varying State and Control Constraints: An Application to Intelligent Vehicles18 Dec 2021
- 2021New Versions of Gradient Temporal Difference Learning9 Sep 2021
3 more
- 2022What is a Good Metric to Study Generalization of Minimax Learners?cited by 16
- 2023Robust Markov Decision Processes without Model Estimationcited by 11
- 2021New Versions of Gradient Temporal Difference Learningcited by 6
- 2025Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Dualitycited by 4
- 2021Model-Based Safe Reinforcement Learning with Time-Varying State and Control Constraints: An Application to Intelligent Vehiclescited by 3
- 2021Learning to Act Safely with Limited Exposure and Almost Sure Certaintycited by 2
- 2024Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learningcited by 2
- 2021Near Optimal Policy Optimization via REPScited by 1
- 2022Provably Efficient Convergence of Primal-Dual Actor-Critic with Nonlinear Function Approximationcited by 1
- 2022Lagrangian Method for Q-Function Learning (with Applications to Machine Translation)cited by 1
- 2026Value Mirror Descent for Reinforcement Learningcited by 1
- 2025A Two-Timescale Primal-Dual Framework for Reinforcement Learning via Online Dual Variable Guidancecited by 0
12 most cited of 14 All 14 (JSON)
- 2026Value Mirror Descent for Reinforcement Learning7 Apr 2026
- 2026R-GTD: A Geometric Analysis of Gradient Temporal-Difference Learning in Singular Regimes28 Jan 2026
- 2025Realizable Abstractions: Near-Optimal Hierarchical Reinforcement Learning4 Dec 2025
- 2025Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Duality24 Aug 2025
- 2025A Two-Timescale Primal-Dual Framework for Reinforcement Learning via Online Dual Variable Guidance7 May 2025
- 2024Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learning16 Feb 2024
- 2023Robust Markov Decision Processes without Model Estimation2 Feb 2023
- 2022Lagrangian Method for Q-Function Learning (with Applications to Machine Translation)22 Jul 2022
- 2022What is a Good Metric to Study Generalization of Minimax Learners?9 Jun 2022
- 2022Provably Efficient Convergence of Primal-Dual Actor-Critic with Nonlinear Function Approximation28 Feb 2022
- 2021Model-Based Safe Reinforcement Learning with Time-Varying State and Control Constraints: An Application to Intelligent Vehicles18 Dec 2021
- 2021New Versions of Gradient Temporal Difference Learning9 Sep 2021
12 newest of 14 All 14 (JSON)