We show how to construct variance-aware confidence sets for linear bandits and linear mixture Markov Decision Process (MDP). Our method yields the following new regret bounds: * For linear bandits, we obtain an $\widetilde{O}(\mathrm{poly}(d)\sqrt{1 + \sum_{i=1}^{K}\sigma_i^2})$ regret bound, where $d$ is the feature dimension, $K$ is the number of rounds, and $\sigma_i^2$ is the (unknown) variance of the reward at the $i$-th round. This is the first regret bound that only scales with the variance and the dimension, with no explicit polynomial dependency on $K$. * For linear mixture MDP, we obtain an $\widetilde{O}(\mathrm{poly}(d, \log H)\sqrt{K})$ regret bound for linear mixture MDP, 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 logarthmically with $H$ in the reinforcement learning (RL) with linear function approximation setting, thus exponentially improving existing results. Our methods utilize three novel ideas that may be of independent interest: 1) applications of the layering techniques to the norm of input and the magnitude of variance, 2) a recursion-based approach to estimate the variance, and 3) a convex potential lemma that in a sense generalizes the seminal elliptical potential lemma.

本文提出了一种新的方差感知置信集，用于线性 bandits 和线性混合马尔可夫决策过程（MDPs）中，我们得到了与方差和维度相关，但不显式依赖于循环次数 k 的后悔上限，并获得了史上首个仅在强化学习中呈对数比例的后悔上限，这三种技术思想可能是独立感兴趣的应用。

基于方差的线性赌博机和线性混合MDP置信区间的改进