mlsanityData to 14 Oct 2026

Rate-Optimal Policy Optimization for Linear Markov Decision Processes

arXiv 2308.14642 ↗First posted 28 Aug 2023cs.LGcited by 14

Not on the map. Why?

Abstract (arXiv)

We study regret minimization in online episodic linear Markov Decision Processes, and obtain rate-optimal widetilde O (√ K) regret where K denotes the number of episodes. Our work is the first to establish the optimal (w.r.t.~K) rate of convergence in the stochastic setting with bandit feedback using a policy optimization based approach, and the first to establish the optimal (w.r.t.~K) rate in the adversarial setup with full information feedback, for which no algorithm with an optimal rate guarantee is currently known.

Key facts. Cited by 14 papers in the map (data through 14 Oct 2026). Builds on 35 of its 51 references that are in the map. First posted on arXiv 28 Aug 2023.

Builds on

35 of 51 references.

References · 35

  1. 2022Training language models to follow instructions with human feedbackcited by 15,971
  2. 2017Proximal Policy Optimization Algorithmscited by 15,215
  3. 2015High-Dimensional Continuous Control Using Generalized Advantage Estimationcited by 2,026
  4. 2018Soft Actor-Critic Algorithms and Applicationscited by 1,240
  5. 2019Introduction to Online Convex Optimizationcited by 803
  6. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  7. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  8. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  9. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  10. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
  11. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
  12. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
23 more
  1. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  2. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
  3. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 156
  4. 2019Global Optimality Guarantees For Policy Gradient Methodscited by 150
  5. 2022On the Convergence Rates of Policy Gradient Methodscited by 119
  6. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  7. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  8. 2020PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learningcited by 92
  9. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  10. 2019Learning Linear-Quadratic Regulators Efficiently with only √T Regretcited by 70
  11. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  12. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 52
  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. 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 46
  16. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  17. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  18. 2020Online learning in MDPs with linear function approximation and bandit feedbackcited by 30
  19. 2023A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processescited by 29
  20. 2023Refined Regret for Adversarial MDPs with Linear Function Approximationcited by 19
  21. 2023Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximationcited by 17
  22. 2023Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimizationcited by 15
  23. 2023Optimistic Natural Policy Gradient: a Simple Efficient Policy Optimization Framework for Online RLcited by 13

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 2; 2024: 6; 2025: 2; 2026: 4.

14 papers.

Sort:

By area:

  1. 2024Imitation Learning in Discounted Linear MDPs without exploration assumptionscited by 15
  2. 2023Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedbackcited by 13
  3. 2025Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learningcited by 12
  4. 2025Greedy Sampling Is Provably Efficient for RLHFcited by 11
  5. 2024Near-Optimal Regret in Linear MDPs with Aggregate Bandit Feedbackcited by 10
  6. 2024Warm-up Free Policy Optimization: Improved Regret in Linear Markov Decision Processescited by 5
  7. 2024Refined Sample Complexity for Markov Games with Independent Linear Function Approximationcited by 3
  8. 2023Rethinking Model-based, Policy-based, and Value-based Reinforcement Learning via the Lens of Representation Complexitycited by 2
  9. 2024Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedbackcited by 2
  10. 2026Optimal Regret for Policy Optimization in Contextual Banditscited by 2
  11. 2026Near-Optimal Regret for Policy Optimization in Contextual MDPs with General Offline Function Approximationcited by 2
  12. 2024Narrowing the Gap between Adversarial and Stochastic MDPs via Policy Optimizationcited by 0
2 more
  1. 2026Optimistic Actor-Critic with Parametric Policies for Linear Markov Decision Processescited by 0
  2. 2026Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Lossescited by 0