Refined Analysis of FPL for Adversarial Markov Decision Processes
  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.
