Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP
Dec 6, 2021
Speakers
Zihan Zhang
Speaker · 0 followers
Jia-Qi Yang
Speaker · 0 followers
Xiangyang Ji
Speaker · 0 followers
Simon Shaolei Du
Speaker · 0 followers
About
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 Θ(d√(K)) worst-case regret bound.For linear mixture MDPs, we obtain an O(poly(d, log 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 <cit.>.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.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 …
Organizer
NeurIPS 2021
Account · 1.9k followers
About NeurIPS 2021
Neural Information Processing Systems (NeurIPS) is a multi-track machine learning and computational neuroscience conference that includes invited talks, demonstrations, symposia and oral and poster presentations of refereed papers. Following the conference, there are workshops which provide a less formal setting.
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Role of recurrent computations in primate visual object recognition
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Self-Supervised Learning Disentangled Group Representation as Feature
Watch later
Tan Wang, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Contextual Similarity Aggregation with Self-attention for Visual Re-ranking
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
A First Look Towards One-Shot Object Detection with SPOT for Data-Efficient Learning
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Proxy-Normalizing Activations to Match Batch Normalization while Removing Batch Dependence
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
When False Positive is Intolerant: End-to-End Optimization with Low FPR for Multipartite Ranking
Watch later
Peisong Wen, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%