Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP

Abstract

This paper presents new 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 O(poly(d)1 + _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 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 no explicit polynomial dependency on K. When variances are small, this bound can be significantly smaller than the (dK) worst-case regret bound. For linear mixture MDPs, we obtain an O(poly(d, H)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 logarithmically with H in the reinforcement learning with linear function approximation setting, thus exponentially improving existing results, and resolving an open problem in 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.

Tasks

Reproductions