mlsanityData to 7 Oct 2026

Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs

arXiv 2305.08359 ↗First posted 15 May 2023cs.LG math.OC stat.MLcited by 4

Not on the map. Why?

Abstract (arXiv)

Recent studies have shown that episodic reinforcement learning (RL) is no harder than bandits when the total reward is bounded by 1, and proved regret bounds that have a polylogarithmic dependence on the planning horizon H. However, it remains an open question that if such results can be carried over to adversarial RL, where the reward is adversarially chosen at each episode. In this paper, we answer this question affirmatively by proposing the first horizon-free policy search algorithm. To tackle the challenges caused by exploration and adversarially chosen reward, our algorithm employs (1) a variance-uncertainty-aware weighted least square estimator for the transition kernel; and (2) an occupancy measure-based technique for the online search of a stochastic policy. We show that our algorithm achieves an tildeObig((d+log (|S|2 |A|))√Kbig) regret with full-information feedback, where d is the dimension of a known feature mapping linearly parametrizing the unknown transition kernel of the MDP, K is the number of episodes, |S| and |A| are the cardinalities of the state and action spaces. We also provide hardness results and regret lower bounds to justify the near optimality of our algorithm and the unavoidability of log|S| and log|A| in the regret bound.

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

Builds on

32 of 58 references.

References · 32

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2018Is Q-learning Provably Efficient?cited by 485
  3. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  4. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  5. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  6. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  7. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  8. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  9. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  10. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  11. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  12. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105
20 more
  1. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  2. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 84
  3. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  4. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  5. 2020Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functionscited by 71
  6. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  7. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  8. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
  9. 2020A Unifying View of Optimism in Episodic Reinforcement Learningcited by 50
  10. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  11. 2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
  12. 2020Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?cited by 34
  13. 2020A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraintscited by 34
  14. 2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
  15. 2020Online learning in MDPs with linear function approximation and bandit feedbackcited by 29
  16. 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
  17. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  18. 2020Nearly Minimax Optimal Reward-free Reinforcement Learningcited by 26
  19. 2022Follow-the-Perturbed-Leader for Adversarial Markov Decision Processes with Bandit Feedbackcited by 16
  20. 2021Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDPcited by 14

Built on by

Cited by year (2026 to 7 Oct)

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

4 papers.

  1. 2025Towards a Sharp Analysis of Offline Policy Learning for f-Divergence-Regularized Contextual Banditscited by 9
  2. 2024Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transitioncited by 6
  3. 2024Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPscited by 5
  4. 2026Near-Optimal Regret for KL-Regularized Multi-Armed Banditscited by 3