mlsanityData to 7 Oct 2026

The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition

arXiv 2106.04117 ↗First posted 8 Jun 2021cs.LGcited by 40

Not on the map. Why?

Abstract (arXiv)

We consider the best-of-both-worlds problem for learning an episodic Markov Decision Process through T episodes, with the goal of achieving widetildeO(√T) regret when the losses are adversarial and simultaneously O(polylog(T)) regret when the losses are (almost) stochastic. Recent work by [Jin and Luo, 2020] achieves this goal when the fixed transition is known, and leaves the case of unknown transition as a major open question. In this work, we resolve this open problem by using the same Follow-the-Regularized-Leader (FTRL) framework together with a set of new techniques. Specifically, we first propose a loss-shifting trick in the FTRL analysis, which greatly simplifies the approach of [Jin and Luo, 2020] and already improves their results for the known transition case. Then, we extend this idea to the unknown transition case and develop a novel analysis which upper bounds the transition estimation error by (a fraction of) the regret itself in the stochastic setting, a key property to ensure O(polylog(T)) regret.

Key facts. Cited by 40 papers in the map (data through 7 Oct 2026). Builds on 21 of its 30 references that are in the map. First posted on arXiv 8 Jun 2021.

Builds on

21 of 30 references.

References · 21

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  2. 2018Is Q-learning Provably Efficient?cited by 485
  3. 2018Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Banditscited by 123
  4. 2018Stochastic bandits robust to adversarial corruptionscited by 118
  5. 2018More Adaptive Algorithms for Adversarial Banditscited by 114
  6. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
  7. 2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 91
  8. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 84
  9. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  10. 2019Corruption-robust exploration in episodic reinforcement learningcited by 72
  11. 2020Q-learning with Logarithmic Regretcited by 59
  12. 2019Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneouslycited by 53
9 more
  1. 2020Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPscited by 49
  2. 2020Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transitioncited by 48
  3. 2021Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneouslycited by 48
  4. 2016An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial banditscited by 47
  5. 2017An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Banditscited by 43
  6. 2018On the optimality of the Hedge algorithm in the stochastic regimecited by 32
  7. 2020Prediction with Corrupted Expert Advicecited by 26
  8. 2020A Closer Look at Small-loss Bounds for Bandits with Graph Feedbackcited by 21
  9. 2021Improved Corruption Robust Algorithms for Episodic Reinforcement Learningcited by 20

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 8; 2023: 12; 2024: 9; 2025: 5; 2026: 3.

40 papers.

Sort:

By area:

  1. 2024Online conformal prediction with decaying step sizescited by 53
  2. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  3. 2023A Blackbox Approach to Best of Both Worlds in Bandits and Beyondcited by 29
  4. 2022Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphscited by 26
  5. 2022Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 22
  6. 2021On Optimal Robustness to Adversarial Corruption in Online Decision Problemscited by 20
  7. 2022Best-of-Both-Worlds Algorithms for Partial Monitoringcited by 19
  8. 2022Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithmscited by 19
  9. 2023Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits: FTRL with General Regularizers and Multiple Optimal Armscited by 18
  10. 2022Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed Banditscited by 17
  11. 2022A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphscited by 17
  12. 2023Best of Both Worlds Policy Optimizationcited by 17
28 more
  1. 2022Follow-the-Perturbed-Leader for Adversarial Markov Decision Processes with Bandit Feedbackcited by 16
  2. 2023Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worldscited by 15
  3. 2021Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDPcited by 14
  4. 2023Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Boundscited by 13
  5. 2022Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Boundscited by 12
  6. 2023Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedbackcited by 12
  7. 2023Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithmcited by 11
  8. 2024Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worldscited by 11
  9. 2023Best-of-Both-Worlds Algorithms for Linear Contextual Banditscited by 10
  10. 2023A Best-of-Both-Worlds Algorithm for Constrained MDPs with Long-Term Constraintscited by 9
  11. 2025Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedbackcited by 9
  12. 2024The Real Price of Bandit Information in Multiclass Classificationcited by 7
  13. 2023Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 6
  14. 2023Near-Optimal Adversarial Reinforcement Learning with Switching Costscited by 4
  15. 2023Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedbackcited by 4
  16. 2024A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of Theta(T2/3) and its Application to Best-of-Both-Worldscited by 3
  17. 2024Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedbackcited by 2
  18. 2025Follow-the-Perturbed-Leader Approaches Best-of-Both-Worlds for the m-Set Semi-Bandit Problemscited by 2
  19. 2025Reinforcement Learning from Adversarial Preferences in Tabular MDPscited by 2
  20. 2025Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedbackcited by 2
  21. 2024Provably Efficient Reinforcement Learning for Adversarial Restless Multi-Armed Bandits with Unknown Transitions and Bandit Feedbackcited by 1
  22. 2024Provably Efficient Off-Policy Adversarial Imitation Learning with Convergence Guaranteescited by 1
  23. 2025Last-Iterate Analyses of FTRL with the 1/2-Tsallis Entropy in Stochastic Banditscited by 1
  24. 2026Best-of-Both-Worlds for Heavy-Tailed Markov Decision Processescited by 1
  25. 2024Narrowing the Gap between Adversarial and Stochastic MDPs via Policy Optimizationcited by 0
  26. 2024Safe Exploitative Play with Untrusted Type Beliefscited by 0
  27. 2026Best-of-Both-Worlds Multi-Dueling Bandits: Unified Algorithms for Stochastic and Adversarial Preferences under Condorcet and Borda Objectivescited by 0
  28. 2026Toward Optimal Second-Order Path-Length Guarantee for Adversarial Multi-Armed Banditscited by 0