mlsanityData to 14 Oct 2026

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

arXiv 2210.12057 ↗First posted 21 Oct 2022cs.LG math.OCcited by 8

Not on the map. Why?

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.

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

26 of 49 references.

References · 26

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  2. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 287
  3. 2013Optimization, Learning, and Games with Predictable Sequencescited by 188
  4. 2017A unified view of entropy-regularized Markov decision processescited by 182
  5. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  6. 2019Minimax Weight and Q-Function Learning for Off-Policy Evaluationcited by 150
  7. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  8. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 127
  9. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 127
  10. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrabilitycited by 123
  11. 2020PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learningcited by 92
  12. 2020Efficiently Solving MDPs with Stochastic Mirror Descentcited by 53
14 more
  1. 2020A Unifying View of Optimism in Episodic Reinforcement Learningcited by 52
  2. 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
  3. 2020Logistic Q-Learningcited by 34
  4. 2017Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problemscited by 33
  5. 2022Proximal Point Imitation Learningcited by 26
  6. 2021Efficient Local Planning with Linear Function Approximationcited by 23
  7. 2021Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Modelcited by 18
  8. 2020Efficient Planning in Large MDPs with Weak Linear Function Approximationcited by 17
  9. 2018Scalable Bilinear π Learning Using State and Action Featurescited by 10
  10. 2019A Reduction from Reinforcement Learning to No-Regret Online Learningcited by 10
  11. 2021Efficient Performance Bounds for Primal-Dual Reinforcement Learning from Demonstrationscited by 10
  12. 2017A Linearly Relaxed Approximate Linear Program for Markov Decision Processescited by 9
  13. 2019Faster saddle-point optimization for solving large-scale Markov decision processescited by 8
  14. 2021Primal-Dual Stochastic Mirror Descent for MDPscited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 2; 2024: 1; 2025: 4; 2026: 1.

8 papers.

  1. 2023Offline Primal-Dual Reinforcement Learning for Linear MDPscited by 17
  2. 2025Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximationcited by 6
  3. 2023Convex Q Learning in a Stochastic Environment: Extended Versioncited by 5
  4. 2024Offline RL via Feature-Occupancy Gradient Ascentcited by 2
  5. 2025Offline Constrained Reinforcement Learning under Partial Data Coveragecited by 1
  6. 2025Analysis of approximate linear programming solution to Markov decision problem with log barrier functioncited by 1
  7. 2025Realizable Abstractions: Near-Optimal Hierarchical Reinforcement Learningcited by 0
  8. 2026Mathematical methods of reinforcement learningcited by 0