Near-Optimal Sample Complexity for MDPs via Anchoring

Jongmin Lee, Mario Bravo, Roberto Cominetti

We study a new model-free algorithm to compute $\epsilon$-optimal policies for average reward Markov decision processes, in the weakly communicating case. Given a generative mod…