mlsanityData to 7 Oct 2026

Warm-up Free Policy Optimization: Improved Regret in Linear Markov Decision Processes

arXiv 2407.03065 ↗First posted 3 Jul 2024cs.LG stat.MLcited by 5

Not on the map. Why?

Abstract (arXiv)

Policy Optimization (PO) methods are among the most popular Reinforcement Learning (RL) algorithms in practice. Recently, Sherman et al. [2023a] proposed a PO-based algorithm with rate-optimal regret guarantees under the linear Markov Decision Process (MDP) model. However, their algorithm relies on a costly pure exploration warm-up phase that is hard to implement in practice. This paper eliminates this undesired warm-up phase, replacing it with a simple and efficient contraction mechanism. Our PO algorithm achieves rate-optimal regret with improved dependence on the other parameters of the problem (horizon and function approximation dimension) in two fundamental settings: adversarial losses with full-information feedback and stochastic losses with bandit feedback.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 42 of its 54 references that are in the map. First posted on arXiv 3 Jul 2024.

Builds on

42 of 54 references.

References · 42

  1. 2022Training language models to follow instructions with human feedbackcited by 15,712
  2. 2017Proximal Policy Optimization Algorithmscited by 14,441
  3. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,635
  4. 2020Learning to summarize from human feedbackcited by 2,562
  5. 2015Trust Region Policy Optimizationcited by 2,503
  6. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  7. 2018Is Q-learning Provably Efficient?cited by 485
  8. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  9. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  10. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  11. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  12. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
30 more
  1. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  2. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  3. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  4. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  5. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  6. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  7. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 84
  8. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  9. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  10. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  11. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  12. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
  13. 2020Near-optimal Regret Bounds for Stochastic Shortest Pathcited by 50
  14. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  15. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  16. 2022VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximationcited by 44
  17. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  18. 2020Learning Adversarial Markov Decision Processes with Delayed Feedbackcited by 33
  19. 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
  20. 2020Online learning in MDPs with linear function approximation and bandit feedbackcited by 29
  21. 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
  22. 2023A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processescited by 28
  23. 2023Best of Both Worlds Policy Optimizationcited by 17
  24. 2023Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimizationcited by 14
  25. 2023Rate-Optimal Policy Optimization for Linear Markov Decision Processescited by 14
  26. 2021Nearly Optimal Policy Optimization with Stable at Any Time Guaranteecited by 13
  27. 2023Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedbackcited by 12
  28. 2024Near-Optimal Regret in Linear MDPs with Aggregate Bandit Feedbackcited by 10
  29. 2023Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 6
  30. 2024Horizon-Free Regret for Linear Markov Decision Processescited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 1; 2026: 3.

5 papers.

  1. 2025CDE: Curiosity-Driven Exploration for Efficient Reinforcement Learning in Large Language Modelscited by 28
  2. 2026Optimal Regret for Policy Optimization in Contextual Banditscited by 1
  3. 2024Narrowing the Gap between Adversarial and Stochastic MDPs via Policy Optimizationcited by 0
  4. 2026Near-Optimal Regret for Policy Optimization in Contextual MDPs with General Offline Function Approximationcited by 0
  5. 2026Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Lossescited by 0