mlsanityData to 14 Oct 2026

Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPs

arXiv 2411.03107 ↗First posted 5 Nov 2024cs.LG stat.MLcited by 5

Not on the map. Why?

Abstract (arXiv)

We study episodic linear mixture MDPs with the unknown transition and adversarial rewards under full-information feedback, employing dynamic regret as the performance measure. We start with in-depth analyses of the strengths and limitations of the two most popular methods: occupancy-measure-based and policy-based methods. We observe that while the occupancy-measure-based method is effective in addressing non-stationary environments, it encounters difficulties with the unknown transition. In contrast, the policy-based method can deal with the unknown transition effectively but faces challenges in handling non-stationary environments. Building on this, we propose a novel algorithm that combines the benefits of both methods. Specifically, it employs (i) an occupancy-measure-based global optimization with a two-layer structure to handle non-stationary environments; and (ii) a policy-based variance-aware value-targeted regression to tackle the unknown transition. We bridge these two parts by a novel conversion. Our algorithm enjoys an widetildeO(d √H3 K + √HK(H + barPK)) dynamic regret, where d is the feature dimension, H is the episode length, K is the number of episodes, barPK is the non-stationarity measure. We show it is minimax optimal up to logarithmic factors by establishing a matching lower bound. To the best of our knowledge, this is the first work that achieves near-optimal dynamic regret for adversarial linear mixture MDPs with the unknown transition without prior knowledge of the non-stationarity measure.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 27 of its 49 references that are in the map. First posted on arXiv 5 Nov 2024.

Builds on

27 of 49 references.

References · 27

  1. 2022Training language models to follow instructions with human feedbackcited by 15,971
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  4. 2018Is Q-learning Provably Efficient?cited by 487
  5. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  6. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
  7. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  8. 2018Adaptive Online Learning in Dynamic Environmentscited by 133
  9. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  10. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  11. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 85
  12. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
15 more
  1. 2020Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimismcited by 76
  2. 2021Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimizationcited by 66
  3. 2021A Simple Approach for Non-stationary Linear Banditscited by 54
  4. 2020Nearly Minimax Optimal Reinforcement Learning for Discounted MDPscited by 42
  5. 2019Variational Regret Bounds for Reinforcement Learningcited by 32
  6. 2020A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spacescited by 32
  7. 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
  8. 2020Efficient Learning in Non-Stationary Linear Markov Decision Processescited by 26
  9. 2020Nonstationary Reinforcement Learning with Linear Function Approximationcited by 23
  10. 2021Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPscited by 16
  11. 2022Dynamic Regret of Online Markov Decision Processescited by 13
  12. 2024Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximationcited by 10
  13. 2023Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approachcited by 9
  14. 2024Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transitioncited by 6
  15. 2023Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPscited by 4

Built on by

Cited by year (2026 to 14 Oct)

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

5 papers.

  1. 2025Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixabilitycited by 7
  2. 2026Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPscited by 5
  3. 2026Dynamic Regret via Discounted-to-Dynamic Reduction with Applications to Curved Losses and Adam Optimizercited by 4
  4. 2025Distributionally Robust Online Markov Game with Linear Function Approximationcited by 1
  5. 2026Priced Motion Through Optimal Faces: A Normal-Fan Geometry for Non-Stationary Adversarial MDPscited by 0