  We study the sample complexity of learning an $\varepsilon$-optimal policy in
an average-reward Markov decision process (MDP) under a generative model. For
weakly communicating MDPs, we establish the complexity bound
$\widetilde{O}(SA\frac{H}{\varepsilon^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 $\varepsilon$, improving on existing work that
either assumes uniformly bounded mixing times for all policies or has
suboptimal dependence on the parameters. We also initiate the study of sample
complexity in general (multichain) average-reward MDPs. We argue a new
transient time parameter $B$ is necessary, establish an
$\widetilde{O}(SA\frac{B + H}{\varepsilon^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 optimally analyze this reduction, we develop
improved bounds for $\gamma$-discounted MDPs, showing that
$\widetilde{O}(SA\frac{H}{(1-\gamma)^2\varepsilon^2} )$ and
$\widetilde{O}(SA\frac{B + H}{(1-\gamma)^2\varepsilon^2} )$ samples suffice to
learn $\varepsilon$-optimal policies in weakly communicating and in general
MDPs, respectively. Both these results circumvent the well-known minimax lower
bound of $\widetilde{\Omega}(SA\frac{1}{(1-\gamma)^3\varepsilon^2} )$ for
$\gamma$-discounted MDPs, and establish a quadratic rather than cubic horizon
dependence for a fixed MDP instance.
