mlsanityData to 7 Oct 2026

Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback

arXiv 2310.11550 ↗First posted 17 Oct 2023cs.LG cs.AI stat.MLcited by 12

Not on the map. Why?

Abstract (arXiv)

We study online reinforcement learning in linear Markov decision processes with adversarial losses and bandit feedback, without prior knowledge on transitions or access to simulators. We introduce two algorithms that achieve improved regret performance compared to existing approaches. The first algorithm, although computationally inefficient, ensures a regret of widetildeOleft(√Kright), where K is the number of episodes. This is the first result with the optimal K dependence in the considered setting. The second algorithm, which is based on the policy optimization framework, guarantees a regret of widetildeOleft(K^frac34 right) and is computationally efficient. Both our results significantly improve over the state-of-the-art: a computationally inefficient algorithm by Kong et al. [2023] with widetildeOleft(K^frac45+polyleft(frac1λminright) right) regret, for some problem-dependent constant λmin that can be arbitrarily close to zero, and a computationally efficient algorithm by Sherman et al. [2023b] with widetildeOleft(K^frac67 right) regret.

Key facts. Cited by 12 papers in the map (data through 7 Oct 2026). Builds on 29 of its 37 references that are in the map. First posted on arXiv 17 Oct 2023.

Builds on

29 of 37 references.

References · 29

  1. 2018Exploration by Random Network Distillationcited by 966
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  3. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  4. 2020PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learningcited by 91
  5. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 84
  6. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  7. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  8. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
  9. 2020Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPscited by 49
  10. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  11. 2021The best of both worlds: stochastic and adversarial episodic MDPs with unknown transitioncited by 40
  12. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
17 more
  1. 2022On the Complexity of Adversarial Decision Makingcited by 32
  2. 2020Online learning in MDPs with linear function approximation and bandit feedbackcited by 29
  3. 2023A Blackbox Approach to Best of Both Worlds in Bandits and Beyondcited by 29
  4. 2021Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Casecited by 28
  5. 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
  6. 2023A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processescited by 28
  7. 2023Refined Regret for Adversarial MDPs with Linear Function Approximationcited by 18
  8. 2023Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Banditscited by 18
  9. 2023Best of Both Worlds Policy Optimizationcited by 17
  10. 2022Follow-the-Perturbed-Leader for Adversarial Markov Decision Processes with Bandit Feedbackcited by 16
  11. 2023Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximationcited by 16
  12. 2022Pushing the Efficiency-Regret Pareto Frontier for Online Learning of Portfolios and Quantum Statescited by 15
  13. 2023Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimizationcited by 14
  14. 2023Rate-Optimal Policy Optimization for Linear Markov Decision Processescited by 14
  15. 2023Optimistic Natural Policy Gradient: a Simple Efficient Policy Optimization Framework for Online RLcited by 13
  16. 2022Model-Free Reinforcement Learning with the Decision-Estimation Coefficientcited by 11
  17. 2018Policy Optimization with Model-based Explorationscited by 5

Built on by

Cited by year (2026 to 7 Oct)

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

12 papers.

  1. 2025Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learningcited by 12
  2. 2024Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecificationcited by 6
  3. 2024Warm-up Free Policy Optimization: Improved Regret in Linear Markov Decision Processescited by 5
  4. 2024Refined Sample Complexity for Markov Games with Independent Linear Function Approximationcited by 3
  5. 2025Decision Making in Hybrid Environments: A Model Aggregation Approachcited by 3
  6. 2025An Improved Algorithm for Adversarial Linear Contextual Bandits via Reductioncited by 3
  7. 2024Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedbackcited by 2
  8. 2025An Improved Model-Free Decision-Estimation Coefficient with Applications in Adversarial MDPscited by 2
  9. 2026Best-of-Both-Worlds for Heavy-Tailed Markov Decision Processescited by 1
  10. 2026Optimal Regret for Policy Optimization in Contextual Banditscited by 1
  11. 2024Narrowing the Gap between Adversarial and Stochastic MDPs via Policy Optimizationcited by 0
  12. 2026Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Lossescited by 0