Provably Efficient Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs

We resolve the open problem of designing a computationally efficient algorithm for infinite-horizon average-reward linear Markov Decision Processes (MDPs) with O(√T) regret. Previous approaches with O(√T) regret either suffer from computational inefficiency or require strong assumptions on dynamics, such as ergodicity. In this paper, we approximate the average-reward setting by the discounted setting and show that running an optimistic value iteration-based algorithm for learning the discounted setting achieves O(√T) regret when the discounting factor γ is tuned appropriately. The challenge in the approximation approach is to get a regret bound with a sharp dependency on the effective horizon 1 / (1 - γ). We use a computationally efficient clipping operator that constrains the span of the optimistic state value function estimate to achieve a sharp regret bound in terms of the effective horizon, which leads to O(√T) regret.