Refined Analysis of FPL for Adversarial Markov Decision Processes
This work provides incremental improvements for researchers in online learning and reinforcement learning by enhancing algorithm efficiency in adversarial settings.
The paper tackles the adversarial Markov Decision Process problem by improving the analysis of Follow-the-Perturbed-Leader based algorithms, achieving regret bounds that match the current best while being faster and simpler.
We consider the adversarial Markov Decision Process (MDP) problem, where the rewards for the MDP can be adversarially chosen, and the transition function can be either known or unknown. In both settings, Follow-the-PerturbedLeader (FPL) based algorithms have been proposed in previous literature. However, the established regret bounds for FPL based algorithms are worse than algorithms based on mirrordescent. We improve the analysis of FPL based algorithms in both settings, matching the current best regret bounds using faster and simpler algorithms.