Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs

arXiv:2403.11477v1 Announce Type: new
Abstract: We study the sample complexity of learning an $\epsilon$-optimal policy in an average-reward Markov decision process (MDP) under a generative model. For weakly communicating MDPs, we establish the complexity bound $\tilde{O}(SA\frac{H}{\epsilon^2})$, where $H$ is the span of the bias function of the optimal policy and $SA$ is the cardinality of the state-action space. Our result is the first that is minimax optimal (up to log factors) in all parameters $S,A,H$ and $\epsilon$, improving on existing …

abstract arxiv bias complexity cs.it cs.lg decision epsilon function general generative markov math.it math.oc policy process sample stat.ml study type