# Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimization

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 49 references that are in the map.
- First posted on arXiv 21 Oct 2022.

## Builds on (most cited first, 26 of 26)

- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [A unified view of entropy-regularized Markov decision processes](https://mlsanity.com/paper/1705.07798/) (2017)
- [Learning Near Optimal Policies with Low Inherent Bellman Error](https://mlsanity.com/paper/2003.00153/) (2020)
- [Minimax Weight and Q-Function Learning for Off-Policy Evaluation](https://mlsanity.com/paper/1910.12809/) (2019)
- [Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?](https://mlsanity.com/paper/1910.03016/) (2019)
- [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Offline Reinforcement Learning with Realizability and Single-policy Concentrability](https://mlsanity.com/paper/2202.04634/) (2022)
- [PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning](https://mlsanity.com/paper/2007.08459/) (2020)
- [Efficiently Solving MDPs with Stochastic Mirror Descent](https://mlsanity.com/paper/2008.12776/) (2020)
- [A Unifying View of Optimism in Episodic Reinforcement Learning](https://mlsanity.com/paper/2007.01891/) (2020)
- [Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation](https://mlsanity.com/paper/2007.11849/) (2020)
- [Logistic Q-Learning](https://mlsanity.com/paper/2010.11151/) (2020)
- [Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems](https://mlsanity.com/paper/1710.06100/) (2017)
- [Proximal Point Imitation Learning](https://mlsanity.com/paper/2209.10968/) (2022)
- [Efficient Local Planning with Linear Function Approximation](https://mlsanity.com/paper/2108.05533/) (2021)
- [Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model](https://mlsanity.com/paper/2105.14016/) (2021)
- [Efficient Planning in Large MDPs with Weak Linear Function Approximation](https://mlsanity.com/paper/2007.06184/) (2020)
- [Scalable Bilinear π Learning Using State and Action Features](https://mlsanity.com/paper/1804.10328/) (2018)
- [A Reduction from Reinforcement Learning to No-Regret Online Learning](https://mlsanity.com/paper/1911.05873/) (2019)
- [Efficient Performance Bounds for Primal-Dual Reinforcement Learning from Demonstrations](https://mlsanity.com/paper/2112.14004/) (2021)
- [A Linearly Relaxed Approximate Linear Program for Markov Decision Processes](https://mlsanity.com/paper/1704.02544/) (2017)
- [Faster saddle-point optimization for solving large-scale Markov decision processes](https://mlsanity.com/paper/1909.10904/) (2019)
- [Primal-Dual Stochastic Mirror Descent for MDPs](https://mlsanity.com/paper/2103.00299/) (2021)

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

- [Offline Primal-Dual Reinforcement Learning for Linear MDPs](https://mlsanity.com/paper/2305.12944/) (2023)
- [Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation](https://mlsanity.com/paper/2502.10138/) (2025)
- [Convex Q Learning in a Stochastic Environment: Extended Version](https://mlsanity.com/paper/2309.05105/) (2023)
- [Offline RL via Feature-Occupancy Gradient Ascent](https://mlsanity.com/paper/2405.13755/) (2024)
- [Offline Constrained Reinforcement Learning under Partial Data Coverage](https://mlsanity.com/paper/2505.17506/) (2025)
- [Analysis of approximate linear programming solution to Markov decision problem with log barrier function](https://mlsanity.com/paper/2509.19800/) (2025)
- [Realizable Abstractions: Near-Optimal Hierarchical Reinforcement Learning](https://mlsanity.com/paper/2512.04958/) (2025)
- [Mathematical methods of reinforcement learning](https://mlsanity.com/paper/2607.06935/) (2026)

## Abstract (arXiv)

We propose a new stochastic primal-dual optimization algorithm for planning in a large discounted Markov decision process with a generative model and linear function approximation. Assuming that the feature map approximately satisfies standard realizability and Bellman-closedness conditions and also that the feature vectors of all state-action pairs are representable as convex combinations of a small core set of state-action pairs, we show that our method outputs a near-optimal policy after a polynomial number of queries to the generative model. Our method is computationally efficient and comes with the major advantage that it outputs a single softmax policy that is compactly represented by a low-dimensional parameter vector, and does not need to execute computationally expensive local planning subroutines in runtime.