mlsanityData to 7 Oct 2026

Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transition

arXiv 2006.05606 ↗First posted 10 Jun 2020cs.LG stat.MLcited by 48

Not on the map. Why?

Abstract (arXiv)

This work studies the problem of learning episodic Markov Decision Processes with known transition and bandit feedback. We develop the first algorithm with a ``best-of-both-worlds'' guarantee: it achieves O(log T) regret when the losses are stochastic, and simultaneously enjoys worst-case robustness with tildeO(√T) regret even when the losses are adversarial, where T is the number of episodes. More generally, it achieves tildeO(√C) regret in an intermediate setting where the losses are corrupted by a total amount of C. Our algorithm is based on the Follow-the-Regularized-Leader method from Zimin and Neu (2013), with a novel hybrid regularizer inspired by recent works of Zimmert et al. (2019a, 2019b) for the special case of multi-armed bandits. Crucially, our regularizer admits a non-diagonal Hessian with a highly complicated inverse. Analyzing such a regularizer and deriving a particular self-bounding regret guarantee is our key technical contribution and might be of independent interest.

Key facts. Cited by 48 papers in the map (data through 7 Oct 2026). First posted on arXiv 10 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 12; 2022: 13; 2023: 11; 2024: 6; 2025: 4; 2026: 2.

48 papers.

Sort:

By area:

  1. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  2. 2021Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneouslycited by 48
  3. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  4. 2021The best of both worlds: stochastic and adversarial episodic MDPs with unknown transitioncited by 40
  5. 2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
  6. 2021Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learningcited by 33
  7. 2022Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processescited by 33
  8. 2022On the Complexity of Adversarial Decision Makingcited by 32
  9. 2021Robust Policy Gradient against Strong Data Corruptioncited by 30
  10. 2021Minimax Regret for Stochastic Shortest Pathcited by 30
  11. 2023Corruption-Robust Offline Reinforcement Learning with General Function Approximationcited by 30
  12. 2023A Blackbox Approach to Best of Both Worlds in Bandits and Beyondcited by 29
36 more
  1. 2022Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphscited by 26
  2. 2022Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 22
  3. 2022Regret Minimization and Convergence to Equilibria in General-sum Markov Gamescited by 22
  4. 2021Improved Corruption Robust Algorithms for Episodic Reinforcement Learningcited by 20
  5. 2022Best-of-Both-Worlds Algorithms for Partial Monitoringcited by 19
  6. 2022Online Policy Optimization for Robust MDPcited by 19
  7. 2021An Algorithm for Stochastic and Adversarial Bandits with Switching Costscited by 18
  8. 2022Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed Banditscited by 17
  9. 2022A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphscited by 17
  10. 2023Best of Both Worlds Policy Optimizationcited by 17
  11. 2021Improved Analysis of the Tsallis-INF Algorithm in Stochastically Constrained Adversarial Bandits and Stochastic Bandits with Adversarial Corruptionscited by 15
  12. 2022Socially Fair Reinforcement Learningcited by 13
  13. 2023Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Boundscited by 13
  14. 2022Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Boundscited by 12
  15. 2023Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithmcited by 11
  16. 2024Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worldscited by 11
  17. 2025Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedbackcited by 9
  18. 2023Banker Online Mirror Descent: A Universal Approach for Delayed Online Bandit Learningcited by 7
  19. 2024The Real Price of Bandit Information in Multiclass Classificationcited by 7
  20. 2024uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABscited by 7
  21. 2023Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 6
  22. 2021Best-of-All-Worlds Bounds for Online Learning with Feedback Graphscited by 4
  23. 2022Cooperative Online Learning in Stochastic and Adversarial MDPscited by 4
  24. 2023Online Reinforcement Learning with Uncertain Episode Lengthscited by 4
  25. 2023Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedbackcited by 4
  26. 2024LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Banditscited by 4
  27. 2024MetaCURL: Non-stationary Concave Utility Reinforcement Learningcited by 4
  28. 2022Simultaneously Learning Stochastic and Adversarial Bandits under the Position-Based Modelcited by 2
  29. 2023Reinforcement Learning with Delayed, Composite, and Partially Anonymous Rewardcited by 2
  30. 2025Reinforcement Learning from Adversarial Preferences in Tabular MDPscited by 2
  31. 2025Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedbackcited by 2
  32. 2023Online Resource Allocation in Episodic Markov Decision Processescited by 1
  33. 2026Best-of-Both-Worlds for Heavy-Tailed Markov Decision Processescited by 1
  34. 2024Online MDP with Transition Prototypes: A Robust Adaptive Approachcited by 0
  35. 2025Playing Markov Games Without Observing Payoffscited by 0
  36. 2026Toward Optimal Second-Order Path-Length Guarantee for Adversarial Multi-Armed Banditscited by 0