Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Span
This work provides a more efficient learning algorithm for linear mixture MDPs, which are relevant for researchers and practitioners working with sequential decision-making problems under average-reward criteria.
This paper presents a computationally tractable algorithm for learning infinite-horizon average-reward linear mixture Markov Decision Processes (MDPs). The algorithm achieves a nearly minimax optimal regret upper bound of $\widetilde{\mathcal{O}}(d\sqrt{\mathrm{sp}(v^*)T})$ over $T$ time steps, where $\mathrm{sp}(v^*)$ is the span of the optimal bias function and $d$ is the feature dimension.
This paper proposes a computationally tractable algorithm for learning infinite-horizon average-reward linear mixture Markov decision processes (MDPs) under the Bellman optimality condition. Our algorithm for linear mixture MDPs achieves a nearly minimax optimal regret upper bound of $\widetilde{\mathcal{O}}(d\sqrt{\mathrm{sp}(v^*)T})$ over $T$ time steps where $\mathrm{sp}(v^*)$ is the span of the optimal bias function $v^*$ and $d$ is the dimension of the feature mapping. Our algorithm applies the recently developed technique of running value iteration on a discounted-reward MDP approximation with clipping by the span. We prove that the value iteration procedure, even with the clipping operation, converges. Moreover, we show that the associated variance term due to random transitions can be bounded even under clipping. Combined with the weighted ridge regression-based parameter estimation scheme, this leads to the nearly minimax optimal regret guarantee.