mlsanityData to 7 Oct 2026

Follow-the-Perturbed-Leader for Adversarial Markov Decision Processes with Bandit Feedback

arXiv 2205.13451 ↗First posted 26 May 2022cs.LG cs.AI stat.MLcited by 16

Not on the map. Why?

Abstract (arXiv)

We consider regret minimization for Adversarial Markov Decision Processes (AMDPs), where the loss functions are changing over time and adversarially chosen, and the learner only observes the losses for the visited state-action pairs (i.e., bandit feedback). While there has been a surge of studies on this problem using Online-Mirror-Descent (OMD) methods, very little is known about the Follow-the-Perturbed-Leader (FTPL) methods, which are usually computationally more efficient and also easier to implement since it only requires solving an offline planning problem. Motivated by this, we take a closer look at FTPL for learning AMDPs, starting from the standard episodic finite-horizon setting. We find some unique and intriguing difficulties in the analysis and propose a workaround to eventually show that FTPL is also able to achieve near-optimal regret bounds in this case. More importantly, we then find two significant applications: First, the analysis of FTPL turns out to be readily generalizable to delayed bandit feedback with order-optimal regret, while OMD methods exhibit extra difficulties (Jin et al., 2022). Second, using FTPL, we also develop the first no-regret algorithm for learning communicating AMDPs in the infinite-horizon setting with bandit feedback and stochastic transitions. Our algorithm is efficient assuming access to an offline planning oracle, while even for the easier full-information setting, the only existing algorithm (Chandrasekaran and Tewari, 2021) is computationally inefficient.

Key facts. Cited by 16 papers in the map (data through 7 Oct 2026). Builds on 19 of its 57 references that are in the map. First posted on arXiv 26 May 2022.

Builds on

19 of 57 references.

References · 19

  1. 2018Is Q-learning Provably Efficient?cited by 485
  2. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 84
  3. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  4. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  5. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
  6. 2022Smoothed Online Learning is as Easy as Statistical Learningcited by 50
  7. 2019Nonstochastic Multiarmed Bandits with Unrestricted Delayscited by 46
  8. 2021The best of both worlds: stochastic and adversarial episodic MDPs with unknown transitioncited by 40
  9. 2013Bandits with Switching Costs: T^{2/3} Regretcited by 38
  10. 2020Learning Adversarial Markov Decision Processes with Delayed Feedbackcited by 33
  11. 2016Efficient Algorithms for Adversarial Contextual Learningcited by 32
  12. 2016Oracle-Efficient Online Learning and Auction Designcited by 32
7 more
  1. 2020Adapting to Delays and Data in Adversarial Multi-Armed Banditscited by 29
  2. 2015First-order regret bounds for combinatorial semi-banditscited by 25
  3. 2022Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 22
  4. 2013An efficient algorithm for learning with semi-bandit feedbackcited by 21
  5. 2022Oracle-Efficient Online Learning for Beyond Worst-Case Adversariescited by 19
  6. 2015Importance weighting without importance weights: An efficient algorithm for combinatorial semi-banditscited by 15
  7. 2020Refined Analysis of FPL for Adversarial Markov Decision Processescited by 2

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 8; 2024: 4; 2025: 3.

16 papers.

Sort:

  1. 2022Online Prediction in Sub-linear Spacecited by 16
  2. 2023A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPscited by 15
  3. 2023Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedbackcited by 12
  4. 2023Banker Online Mirror Descent: A Universal Approach for Delayed Online Bandit Learningcited by 7
  5. 2023Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 6
  6. 2024Random Latent Exploration for Deep Reinforcement Learningcited by 6
  7. 2023Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Makingcited by 5
  8. 2023Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPscited by 4
  9. 2023Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedbackcited by 4
  10. 2025Revisiting Follow-the-Perturbed-Leader with Unbounded Perturbations in Bandit Problemscited by 3
  11. 2024Scale-free Adversarial Reinforcement Learningcited by 2
  12. 2024Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedbackcited by 2
4 more
  1. 2025Follow-the-Perturbed-Leader Approaches Best-of-Both-Worlds for the m-Set Semi-Bandit Problemscited by 2
  2. 2023Online Resource Allocation in Episodic Markov Decision Processescited by 1
  3. 2024State-free Reinforcement Learningcited by 0
  4. 2025Optimistic Learning for Communication Networkscited by 0