Abstract

We give a simple optimistic algorithm for which it is easy to derive regretbounds of $\tilde{O}(\sqrt{t_{\rm mix} SAT})$ after $T$ steps in uniformlyergodic MDPs with $S$ states, $A$ actions, and mixing time parameter $t_{\rmmix}$. These bounds are the first regret bounds in the general, non-episodicsetting with an optimal dependence on all given parameters. They could only beimproved by using an alternative mixing time parameter.

 

Quick Read (beta)