# Faster saddle-point optimization for solving large-scale Markov decision processes

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Sep 2019.

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

- [Proximal Point Imitation Learning](https://mlsanity.com/paper/2209.10968/) (2022)
- [Offline Primal-Dual Reinforcement Learning for Linear MDPs](https://mlsanity.com/paper/2305.12944/) (2023)
- [Efficient Performance Bounds for Primal-Dual Reinforcement Learning from Demonstrations](https://mlsanity.com/paper/2112.14004/) (2021)
- [Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimization](https://mlsanity.com/paper/2210.12057/) (2022)
- [Accelerating Primal-dual Methods for Regularized Markov Decision Processes](https://mlsanity.com/paper/2202.10506/) (2022)
- [Near Optimal Policy Optimization via REPS](https://mlsanity.com/paper/2103.09756/) (2021)
- [Lagrangian Method for Q-Function Learning (with Applications to Machine Translation)](https://mlsanity.com/paper/2207.11161/) (2022)
- [Analysis of approximate linear programming solution to Markov decision problem with log barrier function](https://mlsanity.com/paper/2509.19800/) (2025)

## Abstract (arXiv)

We consider the problem of computing optimal policies in average-reward Markov decision processes. This classical problem can be formulated as a linear program directly amenable to saddle-point optimization methods, albeit with a number of variables that is linear in the number of states. To address this issue, recent work has considered a linearly relaxed version of the resulting saddle-point problem. Our work aims at achieving a better understanding of this relaxed optimization problem by characterizing the conditions necessary for convergence to the optimal policy, and designing an optimization algorithm enjoying fast convergence rates that are independent of the size of the state space. Notably, our characterization points out some potential issues with previous work.