Follow-the-Perturbed-Leader for Adversarial Markov Decision Processes with Bandit Feedback
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.