Span-Based Optimal Sample Complexity for Weakly Communicating and
  General Average Reward MDPs
Matthew Zurek Yudong Chen
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 work that either
assumes uniformly bounded mixing times for all policies or has suboptimal
dependence on the parameters. We further investigate sample complexity in
general (non-weakly-communicating) average-reward MDPs. We argue a new
transient time parameter $B$ is necessary, establish an
$\tilde{O}(SA\frac{B+H}{\epsilon^2})$ complexity bound, and prove a matching
(up to log factors) minimax lower bound. Both results are based on reducing the
average-reward MDP to a discounted MDP, which requires new ideas in the general
setting. To establish the optimality of this reduction, we develop improved
bounds for $\gamma$-discounted MDPs, showing that
$\tilde{\Omega}\left(SA\frac{H}{(1-\gamma)^2\epsilon^2}\right)$ samples suffice
to learn an $\epsilon$-optimal policy in weakly communicating MDPs under the
regime that $\gamma\geq 1-1/H$, and
$\tilde{\Omega}\left(SA\frac{B+H}{(1-\gamma)^2\epsilon^2}\right)$ samples
suffice in general MDPs when $\gamma\geq 1-\frac{1}{B+H}$. Both these results
circumvent the well-known lower bound of
$\tilde{\Omega}\left(SA\frac{1}{(1-\gamma)^3\epsilon^2}\right)$ for arbitrary
$\gamma$-discounted MDPs. Our analysis develops upper bounds on certain
instance-dependent variance parameters in terms of the span and transient time
parameters. The weakly communicating bounds are tighter than those based on the
mixing time or diameter of the MDP and may be of broader use.