Provably Efficient Infinite-Horizon Average-Reward Reinforcement Learning with Linear Function Approximation

This paper proposes a computationally tractable algorithm for learning infinite-horizon average-reward linear Markov decision processes (MDPs) and linear mixture MDPs under the Bellman optimality condition. While guaranteeing computational efficiency, our algorithm for linear MDPs achieves the best-known regret upper bound of $\tilde{\mathcal{O}}(d^{3\mathrm{/}2}\mathrm{s}\mathrm{p}(v^{\ast })\sqrt{T})$ over $T$ time steps where $\mathrm{s}\mathrm{p}(v^{\ast })$ is the span of the optimal bias function $v^{\ast }$ and $d$ is the dimension of the feature mapping. For linear mixture MDPs, our algorithm attains a regret bound of $\tilde{\mathcal{O}}(d\cdot \mathrm{s}\mathrm{p}(v^{\ast })\sqrt{T})$. The algorithm applies novel techniques to control the covering number of the value function class and the span of optimistic estimators of the value function, which is of independent interest.