# Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning

arXiv: https://arxiv.org/abs/1612.02516 · HTML: https://mlsanity.com/paper/1612.02516/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Dec 2016.

## Built on by (most cited first, 15 of 15)

- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [What is a Good Metric to Study Generalization of Minimax Learners?](https://mlsanity.com/paper/2206.04502/) (2022)
- [Robust Markov Decision Processes without Model Estimation](https://mlsanity.com/paper/2302.01248/) (2023)
- [New Versions of Gradient Temporal Difference Learning](https://mlsanity.com/paper/2109.04033/) (2021)
- [Model-Based Safe Reinforcement Learning with Time-Varying State and Control Constraints: An Application to Intelligent Vehicles](https://mlsanity.com/paper/2112.11217/) (2021)
- [Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Duality](https://mlsanity.com/paper/2508.17448/) (2025)
- [Learning to Act Safely with Limited Exposure and Almost Sure Certainty](https://mlsanity.com/paper/2105.08748/) (2021)
- [Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learning](https://mlsanity.com/paper/2402.10810/) (2024)
- [Near Optimal Policy Optimization via REPS](https://mlsanity.com/paper/2103.09756/) (2021)
- [Provably Efficient Convergence of Primal-Dual Actor-Critic with Nonlinear Function Approximation](https://mlsanity.com/paper/2202.13863/) (2022)
- [Lagrangian Method for Q-Function Learning (with Applications to Machine Translation)](https://mlsanity.com/paper/2207.11161/) (2022)
- [Value Mirror Descent for Reinforcement Learning](https://mlsanity.com/paper/2604.06039/) (2026)
- [A Two-Timescale Primal-Dual Framework for Reinforcement Learning via Online Dual Variable Guidance](https://mlsanity.com/paper/2505.04494/) (2025)
- [Realizable Abstractions: Near-Optimal Hierarchical Reinforcement Learning](https://mlsanity.com/paper/2512.04958/) (2025)
- [R-GTD: A Geometric Analysis of Gradient Temporal-Difference Learning in Singular Regimes](https://mlsanity.com/paper/2601.20599/) (2026)

## 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.