# Refined Analysis of FPL for Adversarial Markov Decision Processes

arXiv: https://arxiv.org/abs/2008.09251 · HTML: https://mlsanity.com/paper/2008.09251/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Aug 2020.

## Built on by (most cited first, 2 of 2)

- [Follow-the-Perturbed-Leader for Adversarial Markov Decision Processes with Bandit Feedback](https://mlsanity.com/paper/2205.13451/) (2022)
- [Provably Efficient Off-Policy Adversarial Imitation Learning with Convergence Guarantees](https://mlsanity.com/paper/2405.16668/) (2024)

## Abstract (arXiv)

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.