Spotlight

Towards Tight Bounds on the Sample Complexity of Average-reward MDPs

Yujia Jin · Aaron Sidford

[ Abstract ] [ Livestream: Visit Reinforcement Learning Theory 4 ] [ Paper ]
Wed 21 Jul 6:35 p.m. — 6:40 p.m. PDT

We prove new upper and lower bounds for sample complexity of finding an $\epsilon$-optimal policy of an infinite-horizon average-reward Markov decision process (MDP) given access to a generative model. When the mixing time of the probability transition matrix of all policies is at most $t_\mathrm{mix}$, we provide an algorithm that solves the problem using $\widetilde{O}(t_\mathrm{mix} \epsilon^{-3})$ (oblivious) samples per state-action pair. Further, we provide a lower bound showing that a linear dependence on $t_\mathrm{mix}$ is necessary in the worst case for any algorithm which computes oblivious samples. We obtain our results by establishing connections between infinite-horizon average-reward MDPs and discounted MDPs of possible further utility.

Chat is not available.