# Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Oct 2017.

## Built on by (most cited first, 30 of 33)

- [Offline Reinforcement Learning with Realizability and Single-policy Concentrability](https://mlsanity.com/paper/2202.04634/) (2022)
- [Towards Tight Bounds on the Sample Complexity of Average-reward MDPs](https://mlsanity.com/paper/2106.07046/) (2021)
- [Stochastic first-order methods for average-reward Markov decision processes](https://mlsanity.com/paper/2205.05800/) (2022)
- [Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP](https://mlsanity.com/paper/2212.00603/) (2022)
- [Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes](https://mlsanity.com/paper/2306.16394/) (2023)
- [Quantum Algorithms for Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2112.08451/) (2021)
- [Differentially Private SGDA for Minimax Problems](https://mlsanity.com/paper/2201.09046/) (2022)
- [Average-reward model-free reinforcement learning: a systematic review and literature mapping](https://mlsanity.com/paper/2010.08920/) (2020)
- [Dealing with unbounded gradients in stochastic saddle-point optimization](https://mlsanity.com/paper/2402.13903/) (2024)
- [Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints](https://mlsanity.com/paper/2212.13861/) (2022)
- [Optimal Sample Complexity for Average Reward Markov Decision Processes](https://mlsanity.com/paper/2310.08833/) (2023)
- [Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factor](https://mlsanity.com/paper/2302.00036/) (2023)
- [Finding good policies in average-reward Markov Decision Processes without prior knowledge](https://mlsanity.com/paper/2405.17108/) (2024)
- [Logarithmic regret bounds for continuous-time average-reward Markov decision processes](https://mlsanity.com/paper/2205.11168/) (2022)
- [Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimization](https://mlsanity.com/paper/2210.12057/) (2022)
- [Learning Stationary Nash Equilibrium Policies in n-Player Stochastic Games with Independent Chains](https://mlsanity.com/paper/2201.12224/) (2022)
- [Long-Term Resource Allocation Fairness in Average Markov Decision Process (AMDP) Environment](https://mlsanity.com/paper/2102.07120/) (2021)
- [Optimal Sample Complexity of Stable Discounted Markov Decision Processes](https://mlsanity.com/paper/2302.07477/) (2023)
- [A Near-Optimal Primal-Dual Method for Off-Policy Learning in CMDP](https://mlsanity.com/paper/2207.06147/) (2022)
- [Second-Order Min-Max Optimization with Lazy Hessians](https://mlsanity.com/paper/2410.09568/) (2024)
- [Primal-Dual Stochastic Mirror Descent for MDPs](https://mlsanity.com/paper/2103.00299/) (2021)
- [Connected Superlevel Set in (Deep) Reinforcement Learning and its Application to Minimax Theorems](https://mlsanity.com/paper/2303.12981/) (2023)
- [Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learning](https://mlsanity.com/paper/2601.13642/) (2026)
- [Policy Gradient Algorithms in Average-Reward Multichain MDPs](https://mlsanity.com/paper/2602.18003/) (2026)
- [Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process](https://mlsanity.com/paper/2606.16729/) (2026)
- [Accelerating Primal-dual Methods for Regularized Markov Decision Processes](https://mlsanity.com/paper/2202.10506/) (2022)
- [Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learning](https://mlsanity.com/paper/2402.10810/) (2024)
- [Efficiently Solving Discounted MDPs with Predictions on Transition Matrices](https://mlsanity.com/paper/2502.15345/) (2025)
- [Finite-Time Bounds for Average-Reward Fitted Q-Iteration](https://mlsanity.com/paper/2510.17391/) (2025)
- [Near Optimal Policy Optimization via REPS](https://mlsanity.com/paper/2103.09756/) (2021)

## Abstract (arXiv)

Consider the problem of approximating the optimal policy of a Markov decision process (MDP) by sampling state transitions. In contrast to existing reinforcement learning methods that are based on successive approximations to the nonlinear Bellman equation, we propose a Primal-Dual π Learning method in light of the linear duality between the value and policy. The π learning method is model-free and makes primal-dual updates to the policy and value vectors as new data are revealed. For infinite-horizon undiscounted Markov decision process with finite state space S and finite action space A, the π learning method finds an ε-optimal policy using the following number of sample transitions  tildeO( frac(τ· t^*mix)2 |S| |A| ε2 ), where t^*mix is an upper bound of mixing times across all policies and τ is a parameter characterizing the range of stationary distributions across policies. The π learning method also applies to the computational problem of MDP where the transition probabilities and rewards are explicitly given as the input. In the case where each state transition can be sampled in tildeO(1) time, the π learning method gives a sublinear-time algorithm for solving the averaged-reward MDP.