mlsanityData to 7 Oct 2026

A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processes

arXiv 2305.08841 ↗First posted 15 May 2023cs.LG cs.AI math.OCcited by 28

Not on the map. Why?

Abstract (arXiv)

The proximal policy optimization (PPO) algorithm stands as one of the most prosperous methods in the field of reinforcement learning (RL). Despite its success, the theoretical understanding of PPO remains deficient. Specifically, it is unclear whether PPO or its optimistic variants can effectively solve linear Markov decision processes (MDPs), which are arguably the simplest models in RL with function approximation. To bridge this gap, we propose an optimistic variant of PPO for episodic adversarial linear MDPs with full-information feedback, and establish a tildeO(d3/4H2K3/4) regret for it. Here d is the ambient dimension of linear MDPs, H is the length of each episode, and K is the number of episodes. Compared with existing policy-based algorithms, we achieve the state-of-the-art regret bound in both stochastic linear MDPs and adversarial linear MDPs with full information. Additionally, our algorithm design features a novel multi-batched updating mechanism and the theoretical analysis utilizes a new covering number argument of value and policy classes, which might be of independent interest.

Key facts. Cited by 28 papers in the map (data through 7 Oct 2026). Builds on 32 of its 47 references that are in the map. First posted on arXiv 15 May 2023.

Builds on

32 of 47 references.

References · 32

  1. 2022Training language models to follow instructions with human feedbackcited by 15,712
  2. 2017Proximal Policy Optimization Algorithmscited by 14,441
  3. 2015Trust Region Policy Optimizationcited by 2,503
  4. 2018Soft Actor-Critic Algorithms and Applicationscited by 1,179
  5. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  6. 2018Is Q-learning Provably Efficient?cited by 485
  7. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  8. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  9. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  10. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  11. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  12. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
20 more
  1. 2020PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learningcited by 91
  2. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  3. 2020Sequential Batch Learning in Finite-Action Linear Contextual Banditscited by 63
  4. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  5. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  6. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  7. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
  8. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  9. 2022VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximationcited by 44
  10. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  11. 2020Dynamic Regret of Policy Optimization in Non-stationary Environmentscited by 32
  12. 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
  13. 2020Online learning in MDPs with linear function approximation and bandit feedbackcited by 29
  14. 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
  15. 2023Refined Regret for Adversarial MDPs with Linear Function Approximationcited by 18
  16. 2021Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPscited by 16
  17. 2023Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximationcited by 16
  18. 2023Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimizationcited by 14
  19. 2021Provably Correct Optimization and Exploration with Non-linear Policiescited by 13
  20. 2021Nearly Optimal Policy Optimization with Stable at Any Time Guaranteecited by 13

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 7; 2024: 11; 2025: 7; 2026: 3.

28 papers.

Sort:

By area:

  1. 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraintcited by 346
  2. 2024DPO Meets PPO: Reinforced Token Optimization for RLHFcited by 126
  3. 2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithmscited by 24
  4. 2023Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Explorationcited by 20
  5. 2024Imitation Learning in Discounted Linear MDPs without exploration assumptionscited by 15
  6. 2023Rate-Optimal Policy Optimization for Linear Markov Decision Processescited by 14
  7. 2023Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Boundscited by 13
  8. 2023Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedbackcited by 12
  9. 2024Sublinear Regret for a Class of Continuous-Time Linear-Quadratic Reinforcement Learning Problemscited by 10
  10. 2025BRiTE: Bootstrapping Reinforced Thinking Process to Enhance Language Model Reasoningcited by 10
  11. 2025Greedy Sampling Is Provably Efficient for RLHFcited by 10
  12. 2024Latent Safety-Constrained Policy Approach for Safe Offline Reinforcement Learningcited by 7
16 more
  1. 2024Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transitioncited by 6
  2. 2024Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximationcited by 6
  3. 2025DVM: Towards Controllable LLM Agents in Social Deduction Gamescited by 6
  4. 2024Warm-up Free Policy Optimization: Improved Regret in Linear Markov Decision Processescited by 5
  5. 2024Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learningcited by 5
  6. 2023Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedbackcited by 4
  7. 2025Enhancing PPO with Trajectory-Aware Hybrid Policiescited by 4
  8. 2025PPO in the Fisher-Rao geometrycited by 4
  9. 2025A Hierarchical Reinforcement Learning Framework for Multi-UAV Combat Using Leader-Follower Strategycited by 3
  10. 2023Rethinking Model-based, Policy-based, and Value-based Reinforcement Learning via the Lens of Representation Complexitycited by 2
  11. 2024Fast Convergence of Softmax Policy Mirror Ascentcited by 2
  12. 2025Provably Mitigating Corruption, Overoptimization, and Verbosity Simultaneously in Offline and Online RLHF/DPO Alignmentcited by 1
  13. 2026Control Reinforcement Learning: Interpretable Token-Level Steering of LLMs via Sparse Autoencoder Featurescited by 1
  14. 2026Rethinking Reinforcement Fine-Tuning in LVLM: Convergence, Reward Decomposition, and Generalizationcited by 1
  15. 2024Narrowing the Gap between Adversarial and Stochastic MDPs via Policy Optimizationcited by 0
  16. 2026Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Lossescited by 0