Lifelong Bandit Optimization: No Prior and No Regret
Not on the map. Why?
Abstract (arXiv)
Machine learning algorithms are often repeatedly applied to problems with similar structure over and over again. We focus on solving a sequence of bandit optimization tasks and develop LIBO, an algorithm which adapts to the environment by learning from past experience and becomes more sample-efficient in the process. We assume a kernelized structure where the kernel is unknown but shared across all tasks. LIBO sequentially meta-learns a kernel that approximates the true kernel and solves the incoming tasks with the latest kernel estimate. Our algorithm can be paired with any kernelized or linear bandit algorithm and guarantees oracle optimal performance, meaning that as more tasks are solved, the regret of LIBO on each task converges to the regret of the bandit algorithm with oracle knowledge of the true kernel. Naturally, if paired with a sublinear bandit algorithm, LIBO yields a sublinear lifelong regret. We also show that direct access to the data from each task is not necessary for attaining sublinear regret. We propose F-LIBO, which solves the lifelong problem in a federated manner.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 47 of its 81 references that are in the map. First posted on arXiv 27 Oct 2022.
Builds on
47 of 81 references.
References · 47
- 2019Advances and Open Problems in Federated Learningcited by 3,021
- 2017On Kernelized Multi-armed Banditscited by 348
- 2018Scalable Private Learning with PATEcited by 266
- 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 195
- 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
- 2014Learning to Optimize via Information-Directed Samplingcited by 168
- 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 156
- 2018Federated Meta-Learning with Fast Convergence and Efficient Communicationcited by 154
- 2016Corralling a Band of Bandit Algorithmscited by 99
- 2017Mostly Exploration-Free Algorithms for Contextual Banditscited by 85
- 2020PACOH: Bayes-Optimal Meta-Learning with PAC-Guaranteescited by 85
- 2020Differentially-Private Federated Linear Banditscited by 83
35 more
- 2021Adapting to Misspecification in Contextual Banditscited by 81
- 2013Confidence Intervals and Hypothesis Testing for High-Dimensional Regressioncited by 78
- 2020Model Selection in Contextual Stochastic Bandit Problemscited by 71
- 2021Robust and Differentially Private Mean Estimationcited by 66
- 2021Federated Multi-armed Bandits with Personalizationcited by 62
- 2020High-Dimensional Sparse Linear Banditscited by 61
- 2021Federated Linear Contextual Banditscited by 61
- 2021High-Dimensional Experimental Design and Kernel Banditscited by 55
- 2019Nearly Minimax-Optimal Regret for Linearly Parameterized Banditscited by 54
- 2021Misspecified Gaussian Process Bandit Optimizationcited by 52
- 2017Batched High-dimensional Bayesian Optimization via Structural Kernel Learningcited by 51
- 2020Impact of Representation Learning in Linear Banditscited by 51
- 2019No-Regret Bayesian Optimization with Unknown Hyperparameterscited by 50
- 2019Doubly-Robust Lasso Banditcited by 49
- 2018Meta-Learning Priors for Efficient Online Bayesian Regressioncited by 47
- 2020Meta-learning with Stochastic Linear Banditscited by 45
- 2021Near-optimal Representation Learning for Linear Bandits and Linear RLcited by 45
- 2021Bayesian decision-making under misspecified priors with applications to meta-learningcited by 43
- 2021Hierarchical Bayesian Banditscited by 33
- 2018Celer: a Fast Solver for the Lasso with Dual Extrapolationcited by 31
- 2018Regret bounds for meta Bayesian optimization with an unknown Gaussian process priorcited by 31
- 2014Theoretical Analysis of Bayesian Optimisation with Unknown Gaussian Process Hyper-Parameterscited by 30
- 2020Convergence Guarantees for Gaussian Process Means With Misspecified Likelihoods and Smoothnesscited by 29
- 2021No Regrets for Learning the Prior in Banditscited by 29
- 2021Meta-Learning Reliable Priors in the Function Spacecited by 23
- 2019Tight Regret Bounds for Infinite-armed Linear Contextual Banditscited by 17
- 2022Nearly Minimax Algorithms for Linear Bandits with Shared Representationcited by 16
- 2021Metalearning Linear Bandits by Prior Updatecited by 15
- 2022Meta-Learning Priors for Safe Bayesian Optimizationcited by 14
- 2018Automatic Exploration of Machine Learning Experiments on OpenMLcited by 13
- 2022Non-stationary Bandits and Meta-Learning with a Small Set of Optimal Armscited by 8
- 2022Meta Representation Learning with Contextual Linear Banditscited by 6
- 2022Meta-Learning Hypothesis Spaces for Sequential Decision-makingcited by 5
- 2022Meta-Learning Adversarial Banditscited by 5
- 2022Online Meta-Learning in Adversarial Multi-Armed Banditscited by 2
Built on by
Citing papers per year: 2022: 1; 2023: 1; 2024: 1.
3 papers.