mlsanityData to 14 Oct 2026

Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximation

arXiv 2301.13087 ↗First posted 30 Jan 2023cs.LG stat.MLcited by 17

Not on the map. Why?

Abstract (arXiv)

We study reinforcement learning with linear function approximation and adversarially changing cost functions, a setup that has mostly been considered under simplifying assumptions such as full information feedback or exploratory conditions.We present a computationally efficient policy optimization algorithm for the challenging general setting of unknown dynamics and bandit feedback, featuring a combination of mirror-descent and least squares policy evaluation in an auxiliary MDP used to compute exploration bonuses.Our algorithm obtains an widetilde O(K6/7) regret bound, improving significantly over previous state-of-the-art of widetilde O (K14/15) in this setting. In addition, we present a version of the same algorithm under the assumption a simulator of the environment is available to the learner (but otherwise no exploratory assumptions are made), and prove it obtains state-of-the-art regret of widetilde O (K2/3).

Key facts. Cited by 17 papers in the map (data through 14 Oct 2026). Builds on 45 of its 79 references that are in the map. First posted on arXiv 30 Jan 2023.

Builds on

45 of 79 references.

References · 45

  1. 2015Continuous control with deep reinforcement learningcited by 3,407
  2. 2013Playing Atari with Deep Reinforcement Learningcited by 3,274
  3. 2015High-Dimensional Continuous Control Using Generalized Advantage Estimationcited by 2,026
  4. 2019Introduction to Online Convex Optimizationcited by 803
  5. 2019Solving Rubik's Cube with a Robot Handcited by 734
  6. 2020Deep Reinforcement Learning for Autonomous Driving: A Surveycited by 721
  7. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  8. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  9. 2018Is Q-learning Provably Efficient?cited by 487
  10. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  11. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 287
  12. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
33 more
  1. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  2. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
  3. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
  4. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  5. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  6. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
  7. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 176
  8. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 156
  9. 2019Global Optimality Guarantees For Policy Gradient Methodscited by 150
  10. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 106
  11. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  12. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 101
  13. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  14. 2020PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learningcited by 92
  15. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 85
  16. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 84
  17. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  18. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  19. 2019Corruption-robust exploration in episodic reinforcement learningcited by 72
  20. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 66
  21. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  22. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 52
  23. 2020Near-optimal Regret Bounds for Stochastic Shortest Pathcited by 50
  24. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  25. 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
  26. 2020Efficient and Robust Algorithms for Adversarial Linear Contextual Banditscited by 43
  27. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  28. 2020Learning Adversarial Markov Decision Processes with Delayed Feedbackcited by 33
  29. 2020Online learning in MDPs with linear function approximation and bandit feedbackcited by 30
  30. 2020Stochastic Shortest Path with Adversarially Changing Costscited by 28
  31. 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
  32. 2022Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 22
  33. 2019√n-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rankcited by 20

Built on by

Cited by year (2026 to 14 Oct)

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

17 papers.

Sort:

By area:

  1. 2023Is RLHF More Difficult than Standard RL?cited by 96
  2. 2023A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processescited by 29
  3. 2023Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Banditscited by 19
  4. 2024Imitation Learning in Discounted Linear MDPs without exploration assumptionscited by 15
  5. 2023Rate-Optimal Policy Optimization for Linear Markov Decision Processescited by 14
  6. 2023Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedbackcited by 13
  7. 2023Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 6
  8. 2024Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transitioncited by 6
  9. 2023Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedbackcited by 4
  10. 2025Enhancing PPO with Trajectory-Aware Hybrid Policiescited by 4
  11. 2025An Improved Algorithm for Adversarial Linear Contextual Bandits via Reductioncited by 4
  12. 2024Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedbackcited by 2
5 more
  1. 2025An Improved Model-Free Decision-Estimation Coefficient with Applications in Adversarial MDPscited by 2
  2. 2026Optimal Regret for Policy Optimization in Contextual Banditscited by 2
  3. 2026Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Expertscited by 1
  4. 2026Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Lossescited by 0
  5. 2026Follow the Perturbed Leader for Linear Bandits: √T Regret over General Convex Setscited by 0