Asymptotically Optimal Model-Free Reinforcement Learning for Average-Reward MDPs

We study average-reward reinforcement learning in finite weakly communicating Markov decision processes with access to a generative model under an $\text{tO}(SA)$ working-space constraint, where $S$ and $A$ denote the numbers of states and actions, respectively. Let $H=\max \{1,\text{spn}(h^{\star })\}$, where $h^{\star }$ is an optimal bias function. Our basic algorithm requires no prior bound on $H$ and terminates almost surely. With high probability, it returns a stationary deterministic policy that is $\text{eps}$-optimal from every initial state using \[ \tO\left( SAH\eps^2 + S^14/3A^4/3H^4/3\eps^4/3 \right) \] samples. For fixed $S,A,H$, this bound matches the span-based statistical lower bound up to logarithmic factors as $\text{eps}\to 0$. Our approach has two key ingredients: (i) reward shaping based on a coarse reference bias to reduce the value scale of the planning problem; and (ii) space-efficient linear programming coupled with a randomized square-grid decoder that reconstructs transition probability on demand.