mlsanityData to 7 Oct 2026

Approximate Policy Iteration Schemes: A Comparison

arXiv 1405.2878 ↗First posted 12 May 2014cs.AI cs.LG stat.MLcited by 39

Not on the map. Why?

Abstract (arXiv)

We consider the infinite-horizon discounted optimal control problem formalized by Markov Decision Processes. We focus on several approximate variations of the Policy Iteration algorithm: Approximate Policy Iteration, Conservative Policy Iteration (CPI), a natural adaptation of the Policy Search by Dynamic Programming algorithm to the infinite-horizon case (PSDP_∞), and the recently proposed Non-Stationary Policy iteration (NSPI(m)). For all algorithms, we describe performance bounds, and make a comparison by paying a particular attention to the concentrability constants involved, the number of iterations and the memory required. Our analysis highlights the following points: 1) The performance guarantee of CPI can be arbitrarily better than that of API/API(α), but this comes at the cost of a relative---exponential in frac1ε---increase of the number of iterations. 2) PSDP_∞ enjoys the best of both worlds: its performance guarantee is similar to that of CPI, but within a number of iterations similar to that of API. 3) Contrary to API that requires a constant memory, the memory needed by CPI and PSDP_∞ is proportional to their number of iterations, which may be problematic when the discount factor γ is close to 1 or the approximation error ε is close to 0; we show that the NSPI(m) algorithm allows to make an overall trade-off between memory and performance. Simulations with these schemes confirm our analysis.

Key facts. Cited by 39 papers in the map (data through 7 Oct 2026). First posted on arXiv 12 May 2014.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 3; 2021: 9; 2022: 11; 2023: 6; 2024: 3; 2025: 4; 2026: 3.

39 papers.

Sort:

By area:

  1. 2020Conservative Q-Learning for Offline Reinforcement Learningcited by 1,777
  2. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  3. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 267
  4. 2022On the Convergence Rates of Policy Gradient Methodscited by 115
  5. 2022Jump-Start Reinforcement Learningcited by 102
  6. 2025Curriculum Reinforcement Learning from Easy to Hard Tasks Improves LLM Reasoningcited by 89
  7. 2020Provably Good Batch Reinforcement Learning Without Great Explorationcited by 77
  8. 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 44
  9. 2021MADE: Exploration via Maximizing Deviation from Explored Regionscited by 40
  10. 2021Greedification Operators for Policy Optimization: Investigating Forward and Reverse KL Divergencescited by 40
  11. 2022Policy Gradient in Robust MDPs with Global Convergence Guaranteecited by 35
  12. 2022Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gapscited by 34
27 more
  1. 2022Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangiancited by 29
  2. 2023A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergencecited by 29
  3. 2021Fast Rates for the Regret of Offline Reinforcement Learningcited by 26
  4. 2020Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparisoncited by 22
  5. 2021Revisiting Peng's Q(λ) for Modern Reinforcement Learningcited by 19
  6. 2021Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Gamescited by 18
  7. 2023Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processescited by 17
  8. 2021Linear Convergence of Entropy-Regularized Natural Policy Gradient with Linear Function Approximationcited by 15
  9. 2022Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Rewardcited by 13
  10. 2023Importance Weighted Actor-Critic for Optimal Conservative Offline Reinforcement Learningcited by 13
  11. 2022Approximate Policy Iteration with Bisimulation Metricscited by 11
  12. 2022Confident Approximate Policy Iteration for Efficient Local Planning in qπ-realizable MDPscited by 8
  13. 2021Stateful Offline Contextual Policy Evaluation and Learningcited by 6
  14. 2023Provably Efficient Offline Goal-Conditioned Reinforcement Learning with General Function Approximation and Single-Policy Concentrabilitycited by 5
  15. 2024Hybrid Reinforcement Learning from Offline Observation Alonecited by 5
  16. 2022An Approximate Policy Iteration Viewpoint of Actor-Critic Algorithmscited by 3
  17. 2023Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approachcited by 3
  18. 2026ADV-0: Closed-Loop Min-Max Adversarial Training for Long-Tail Robustness in Autonomous Drivingcited by 3
  19. 2022Beyond the Policy Gradient Theorem for Efficient Policy Updates in Actor-Critic Algorithmscited by 2
  20. 2023Neural Network Approximation for Pessimistic Offline Reinforcement Learningcited by 1
  21. 2024Structure Matters: Dynamic Policy Gradientcited by 1
  22. 2025Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learningcited by 1
  23. 2025Finite-Time Bounds for Average-Reward Fitted Q-Iterationcited by 1
  24. 2025Fitted Q-Evaluation without Bellman Completeness via Occupancy Weightingcited by 1
  25. 2026Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrabilitycited by 1
  26. 2024Solving Rubik's Cube Without Tricky Samplingcited by 0
  27. 2026Natural Policy Gradient as Doubly Smoothed Policy Iteration: A Bellman-Operator Frameworkcited by 0