mlsanityData to 7 Oct 2026

Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transition

arXiv 2403.04568 ↗First posted 7 Mar 2024cs.LG stat.MLcited by 6

Not on the map. Why?

Abstract (arXiv)

We study reinforcement learning with linear function approximation, unknown transition, and adversarial losses in the bandit feedback setting. Specifically, we focus on linear mixture MDPs whose transition kernel is a linear mixture model. We propose a new algorithm that attains an widetildeO(d√HS3K + √HSAK) regret with high probability, where d is the dimension of feature mappings, S is the size of state space, A is the size of action space, H is the episode length and K is the number of episodes. Our result strictly improves the previous best-known widetildeO(dS2 √K + √HSAK) result in Zhao et al. (2023a) since H ≤ S holds by the layered MDP structure. Our advancements are primarily attributed to (i) a new least square estimator for the transition parameter that leverages the visit information of all states, as opposed to only one state in prior work, and (ii) a new self-normalized concentration tailored specifically to handle non-independent noises, originally proposed in the dynamic assortment area and firstly applied in reinforcement learning to handle correlations between different states.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 30 of its 52 references that are in the map. First posted on arXiv 7 Mar 2024.

Builds on

30 of 52 references.

References · 30

  1. 2023GPT-4 Technical Reportcited by 18,132
  2. 2017Proximal Policy Optimization Algorithmscited by 14,441
  3. 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
  4. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  5. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  6. 2018Is Q-learning Provably Efficient?cited by 485
  7. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
  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. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  11. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  12. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
18 more
  1. 2015Explore no more: Improved high-probability regret bounds for non-stochastic banditscited by 120
  2. 2020Improved Optimistic Algorithms for Logistic Banditscited by 117
  3. 2018More Adaptive Algorithms for Adversarial Banditscited by 114
  4. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 84
  5. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  6. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  7. 2021Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimizationcited by 66
  8. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
  9. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 39
  10. 2020Dynamic Regret of Policy Optimization in Non-stationary Environmentscited by 32
  11. 2020Online learning in MDPs with linear function approximation and bandit feedbackcited by 29
  12. 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
  13. 2023A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processescited by 28
  14. 2021Dynamic pricing and assortment under a contextual MNL demandcited by 20
  15. 2023Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximationcited by 16
  16. 2023Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimizationcited by 14
  17. 2022Dynamic Regret of Online Markov Decision Processescited by 13
  18. 2023Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPscited by 4

Built on by

Cited by year (2026 to 7 Oct)

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

6 papers.

  1. 2024Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximationcited by 10
  2. 2024Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPscited by 5
  3. 2025Linear Mixture Distributionally Robust Markov Decision Processescited by 5
  4. 2025Decision Making in Hybrid Environments: A Model Aggregation Approachcited by 3
  5. 2025An Improved Model-Free Decision-Estimation Coefficient with Applications in Adversarial MDPscited by 2
  6. 2026Priced Motion Through Optimal Faces: A Normal-Fan Geometry for Non-Stationary Adversarial MDPscited by 0