mlsanityData to 7 Oct 2026

Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs

arXiv 2205.09056 ↗First posted 18 May 2022cs.LGcited by 2

Not on the map. Why?

Abstract (arXiv)

Reinforcement learning generalizes multi-armed bandit problems with additional difficulties of a longer planning horizon and unknown transition kernel. We explore a black-box reduction from discounted infinite-horizon tabular reinforcement learning to multi-armed bandits, where, specifically, an independent bandit learner is placed in each state. We show that, under ergodicity and fast mixing assumptions, any slowly changing adversarial bandit algorithm achieving optimal regret in the adversarial bandit setting can also attain optimal expected regret in infinite-horizon discounted Markov decision processes, with respect to the number of rounds T. Furthermore, we examine our reduction using a specific instance of the exponential-weight algorithm.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 55 of its 91 references that are in the map. First posted on arXiv 18 May 2022.

Builds on

55 of 91 references.

References · 55

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  2. 2018Is Q-learning Provably Efficient?cited by 485
  3. 2017Revisiting the Arcade Learning Environment: Evaluation Protocols and Open Problems for General Agentscited by 267
  4. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  5. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  6. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  7. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  8. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  9. 2013Online Learning under Delayed Feedbackcited by 137
  10. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  11. 2016Why is Posterior Sampling Better than Optimism for Reinforcement Learning?cited by 116
  12. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
38 more
  1. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105
  2. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
  3. 2018Deep Counterfactual Regret Minimizationcited by 102
  4. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  5. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  6. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  7. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 84
  8. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  9. 2016Delay and Cooperation in Nonstochastic Banditscited by 71
  10. 2017Learning Unknown Markov Decision Processes: A Thompson Sampling Approachcited by 65
  11. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 65
  12. 2020Q-learning with Logarithmic Regretcited by 59
  13. 2019Worst-Case Regret Bounds for Exploration via Randomized Value Functionscited by 57
  14. 2019Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDPcited by 53
  15. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
  16. 2020A Unifying View of Optimism in Episodic Reinforcement Learningcited by 50
  17. 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
  18. 2019Nonstochastic Multiarmed Bandits with Unrestricted Delayscited by 46
  19. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 45
  20. 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 43
  21. 2020Nearly Minimax Optimal Reinforcement Learning for Discounted MDPscited by 42
  22. 2018Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPscited by 41
  23. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 41
  24. 2020Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?cited by 34
  25. 2020Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexitycited by 28
  26. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  27. 2020Optimistic Exploration even with a Pessimistic Initialisationcited by 25
  28. 2022Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 22
  29. 2016Refined Lower Bounds for Adversarial Banditscited by 20
  30. 2018Regret Bounds for Reinforcement Learning via Markov Chain Concentrationcited by 19
  31. 2020Regret Bounds for Discounted MDPscited by 19
  32. 2020Average-reward model-free reinforcement learning: a systematic review and literature mappingcited by 19
  33. 2013The Sample-Complexity of General Reinforcement Learningcited by 18
  34. 2021Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 18
  35. 2018Near Optimal Exploration-Exploitation in Non-Communicating Markov Decision Processescited by 14
  36. 2013Bounded regret in stochastic multi-armed banditscited by 10
  37. 2019Online Learning with Continuous Variations: Dynamic Regret and Reductionscited by 10
  38. 2019A Reduction from Reinforcement Learning to No-Regret Online Learningcited by 10

50 most cited of 55 All 55 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Regret and Sample Complexity of Online Q-Learning via Concentration of Stochastic Approximation with Time-Inhomogeneous Markov Chainscited by 1
  2. 2026Truthful Online Preference Aggregation for LLM Fine-Tuning in Mobile Crowdsourcingcited by 0