mlsanityData to 7 Oct 2026

Nearly Optimal Policy Optimization with Stable at Any Time Guarantee

arXiv 2112.10935 ↗First posted 21 Dec 2021cs.LG stat.MLcited by 13

Not on the map. Why?

Abstract (arXiv)

Policy optimization methods are one of the most widely used classes of Reinforcement Learning (RL) algorithms. However, theoretical understanding of these methods remains insufficient. Even in the episodic (time-inhomogeneous) tabular setting, the state-of-the-art theoretical result of policy-based method in citetshani2020optimistic is only tildeO(√S2AH4K) where S is the number of states, A is the number of actions, H is the horizon, and K is the number of episodes, and there is a √SH gap compared with the information theoretic lower bound tildeOmega(√SAH3K). To bridge such a gap, we propose a novel algorithm Reference-based Policy Optimization with Stable at Any Time guarantee (algnameacro), which features the property "Stable at Any Time". We prove that our algorithm achieves tildeO(√SAH3K + √AH4K) regret. When S > H, our algorithm is minimax optimal when ignoring logarithmic factors. To our best knowledge, RPO-SAT is the first computationally efficient, nearly minimax optimal policy-based algorithm for tabular RL.

Key facts. Cited by 13 papers in the map (data through 7 Oct 2026). Builds on 25 of its 40 references that are in the map. First posted on arXiv 21 Dec 2021.

Builds on

25 of 40 references.

References · 25

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2015Trust Region Policy Optimizationcited by 2,503
  3. 2018Soft Actor-Critic Algorithms and Applicationscited by 1,179
  4. 2015End-to-End Training of Deep Visuomotor Policiescited by 847
  5. 2018QT-Opt: Scalable Deep Reinforcement Learning for Vision-Based Robotic Manipulationcited by 730
  6. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  7. 2018Is Q-learning Provably Efficient?cited by 485
  8. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
  9. 2016Deep Reinforcement Learning for Robotic Manipulation with Asynchronous Off-Policy Updatescited by 342
  10. 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 211
  11. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  12. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
13 more
  1. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  2. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 157
  3. 2019Global Optimality Guarantees For Policy Gradient Methodscited by 146
  4. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  5. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
  6. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  7. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  8. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  9. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
  10. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 45
  11. 2020Learning Adversarial Markov Decision Processes with Delayed Feedbackcited by 33
  12. 2020Dynamic Regret of Policy Optimization in Non-stationary Environmentscited by 32
  13. 2021Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPscited by 16

Built on by

Cited by year

Citing papers per year: 2022: 3; 2023: 5; 2024: 4; 2025: 1.

13 papers.

Sort:

By area:

  1. 2024DPO Meets PPO: Reinforced Token Optimization for RLHFcited by 126
  2. 2023Pairwise Proximal Policy Optimization: Harnessing Relative Feedback for LLM Alignmentcited by 57
  3. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 53
  4. 2023A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processescited by 28
  5. 2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithmscited by 24
  6. 2022Online Policy Optimization for Robust MDPcited by 19
  7. 2022Policy Optimization for Stochastic Shortest Pathcited by 13
  8. 2023Optimistic Natural Policy Gradient: a Simple Efficient Policy Optimization Framework for Online RLcited by 13
  9. 2023Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regretcited by 9
  10. 2024Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyondcited by 7
  11. 2024Warm-up Free Policy Optimization: Improved Regret in Linear Markov Decision Processescited by 5
  12. 2025ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learningcited by 5
1 more
  1. 2023Rethinking Model-based, Policy-based, and Value-based Reinforcement Learning via the Lens of Representation Complexitycited by 2