Finding good policies in average-reward Markov Decision Processes without prior knowledge

Adrienne Tuynman, Rémy Degenne, Emilie Kaufmann

We revisit the identification of an $\epsilon$-optimal policy in average-reward Markov Decision Processes (MDP). In such MDPs, two measures of complexity have appeared in the li…