Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs
This work addresses the computational bottleneck in reinforcement learning for linear mixture MDPs, providing an efficient solution for researchers and practitioners in AI and machine learning.
The paper tackles the problem of computationally inefficient algorithms for episodic reinforcement learning in linear mixture MDPs by proposing a horizon-free algorithm that achieves optimal regret of $ ilde O(d\sqrt{K} +d^2)$ up to logarithmic factors, using a variance- and uncertainty-aware weighted least square estimator.
Recent studies have shown that episodic reinforcement learning (RL) is not more difficult than contextual bandits, even with a long planning horizon and unknown state transitions. However, these results are limited to either tabular Markov decision processes (MDPs) or computationally inefficient algorithms for linear mixture MDPs. In this paper, we propose the first computationally efficient horizon-free algorithm for linear mixture MDPs, which achieves the optimal $\tilde O(d\sqrt{K} +d^2)$ regret up to logarithmic factors. Our algorithm adapts a weighted least square estimator for the unknown transitional dynamic, where the weight is both \emph{variance-aware} and \emph{uncertainty-aware}. When applying our weighted least square estimator to heterogeneous linear bandits, we can obtain an $\tilde O(d\sqrt{\sum_{k=1}^K σ_k^2} +d)$ regret in the first $K$ rounds, where $d$ is the dimension of the context and $σ_k^2$ is the variance of the reward in the $k$-th round. This also improves upon the best-known algorithms in this setting when $σ_k^2$'s are known.