mlsanityData to 7 Oct 2026

Improved Regret Bound and Experience Replay in Regularized Policy Iteration

arXiv 2102.12611 ↗First posted 25 Feb 2021cs.LG stat.MLcited by 18

Not on the map. Why?

Abstract (arXiv)

In this work, we study algorithms for learning in infinite-horizon undiscounted Markov decision processes (MDPs) with function approximation. We first show that the regret analysis of the Politex algorithm (a version of regularized policy iteration) can be sharpened from O(T3/4) to O(√T) under nearly identical assumptions, and instantiate the bound with linear function approximation. Our result provides the first high-probability O(√T) regret bound for a computationally efficient algorithm in this setting. The exact implementation of Politex with neural network function approximation is inefficient in terms of memory and computation. Since our analysis suggests that we need to approximate the average of the action-value functions of past policies well, we propose a simple efficient implementation where we train a single Q-function on a replay buffer with past data. We show that this often leads to superior performance over other implementation choices, especially in terms of wall-clock time. Our work also provides a novel theoretical justification for using experience replay within policy iteration algorithms.

Key facts. Cited by 18 papers in the map (data through 7 Oct 2026). Builds on 29 of its 53 references that are in the map. First posted on arXiv 25 Feb 2021.

Builds on

29 of 53 references.

References · 29

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2016Overcoming catastrophic forgetting in neural networkscited by 4,718
  3. 2015Continuous control with deep reinforcement learningcited by 3,279
  4. 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
  5. 2015Trust Region Policy Optimizationcited by 2,503
  6. 2017Gradient Episodic Memory for Continual Learningcited by 1,871
  7. 2016Progressive Neural Networkscited by 1,332
  8. 2015Prioritized Experience Replaycited by 1,070
  9. 2018Efficient Lifelong Learning with A-GEMcited by 1,044
  10. 2018DeepMind Control Suitecited by 935
  11. 2017Constrained Policy Optimizationcited by 928
  12. 2019Orthogonal Gradient Descent for Continual Learningcited by 361
17 more
  1. 2018Maximum a Posteriori Policy Optimisationcited by 318
  2. 2020Coresets via Bilevel Optimization for Continual Learning and Streamingcited by 191
  3. 2015Learning Continuous Control Policies by Stochastic Value Gradientscited by 156
  4. 2019A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Normcited by 105
  5. 2020Mirror Descent Policy Optimizationcited by 102
  6. 2019V-MPO: On-Policy Maximum a Posteriori Policy Optimization for Discrete and Continuous Controlcited by 85
  7. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 81
  8. 2017Practical Coreset Constructions for Machine Learningcited by 75
  9. 2017Learning Unknown Markov Decision Processes: A Thompson Sampling Approachcited by 65
  10. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 65
  11. 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
  12. 2018Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPscited by 41
  13. 2020Leverage the Average: an Analysis of KL Regularization in RLcited by 33
  14. 2019Momentum in Reinforcement Learningcited by 19
  15. 2020Optimization and Generalization of Regularization-Based Continual Learning: a Loss Approximation Viewpointcited by 10
  16. 2020Adaptive Approximate Policy Iterationcited by 9
  17. 2019Quinoa: a Q-function You Infer Normalized Over Actionscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 3; 2023: 7; 2024: 2; 2025: 1; 2026: 2.

18 papers.

Sort:

  1. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 83
  2. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
  3. 2022Stochastic first-order methods for average-reward Markov decision processescited by 30
  4. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 28
  5. 2024Apple Intelligence Foundation Language Modelscited by 22
  6. 2021Efficient Local Planning with Linear Function Approximationcited by 21
  7. 2022Analysis of Stochastic Processes through Replay Bufferscited by 9
  8. 2023Sample Efficient Deep Reinforcement Learning via Local Planningcited by 9
  9. 2023Performance Bounds for Policy-Based Average Reward Reinforcement Learning Algorithmscited by 6
  10. 2023Efficient Planning in Combinatorial Action Spaces with Applications to Cooperative Multi-Agent Reinforcement Learningcited by 6
  11. 2023Selective experience replay compression using coresets for lifelong deep reinforcement learning in medical imagingcited by 6
  12. 2024Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximationcited by 6
6 more
  1. 2022Entropy Regularized Reinforcement Learning with Cascading Networkscited by 2
  2. 2023Finite-Time Analysis of Temporal Difference Learning with Experience Replaycited by 1
  3. 2026Multiscale replay: A robust algorithm for stochastic variational inequalities with a Markovian buffercited by 1
  4. 2023Acceleration in Policy Optimizationcited by 0
  5. 2025Natural Policy Gradient for Average Reward Non-Stationary RLcited by 0
  6. 2026Finite Constant Frontiers and Auditable Regret Certificates for Average-Reward Reinforcement Learningcited by 0