Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP
This work addresses the challenge of achieving tighter, data-dependent regret bounds in reinforcement learning and bandit settings, offering significant improvements over prior worst-case bounds, though it is incremental in building on existing linear function approximation methods.
The paper tackles the problem of improving regret bounds in linear bandits and linear mixture MDPs by introducing variance-aware confidence sets, resulting in a regret bound for linear bandits that scales only with variance and dimension without explicit polynomial dependency on K, and for linear mixture MDPs, a bound that scales logarithmically with H, exponentially improving existing results.
This paper presents new \emph{variance-aware} confidence sets for linear bandits and linear mixture Markov Decision Processes (MDPs). With the new confidence sets, we obtain the follow regret bounds: For linear bandits, we obtain an $\tilde{O}(poly(d)\sqrt{1 + \sum_{k=1}^{K}σ_k^2})$ data-dependent regret bound, where $d$ is the feature dimension, $K$ is the number of rounds, and $σ_k^2$ is the \emph{unknown} variance of the reward at the $k$-th round. This is the first regret bound that only scales with the variance and the dimension but \emph{no explicit polynomial dependency on $K$}. When variances are small, this bound can be significantly smaller than the $\tildeΘ\left(d\sqrt{K}\right)$ worst-case regret bound. For linear mixture MDPs, we obtain an $\tilde{O}(poly(d, \log H)\sqrt{K})$ regret bound, where $d$ is the number of base models, $K$ is the number of episodes, and $H$ is the planning horizon. This is the first regret bound that only scales \emph{logarithmically} with $H$ in the reinforcement learning with linear function approximation setting, thus \emph{exponentially improving} existing results, and resolving an open problem in \citep{zhou2020nearly}. We develop three technical ideas that may be of independent interest: 1) applications of the peeling technique to both the input norm and the variance magnitude, 2) a recursion-based estimator for the variance, and 3) a new convex potential lemma that generalizes the seminal elliptical potential lemma.