Lifelong Bandit Optimization: No Prior and No Regret
- URL: http://arxiv.org/abs/2210.15513v3
- Date: Tue, 20 Jun 2023 08:55:23 GMT
- Title: Lifelong Bandit Optimization: No Prior and No Regret
- Authors: Felix Schur, Parnian Kassraie, Jonas Rothfuss, Andreas Krause
- Abstract summary: We develop LIBO, an algorithm which adapts to the environment by learning from past experience.
We assume a kernelized structure where the kernel is unknown but shared across all tasks.
Our algorithm can be paired with any kernelized or linear bandit algorithm and guarantees optimal performance.
- Score: 70.94238868711952
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: 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.
Related papers
- Learning Arithmetic Formulas in the Presence of Noise: A General
Framework and Applications to Unsupervised Learning [4.10375234787249]
We present a framework for designing efficient algorithms for unsupervised learning problems.
Our framework is based on a meta algorithm that learns arithmetic circuits in the presence of noise.
arXiv Detail & Related papers (2023-11-13T12:26:25Z) - Equation Discovery with Bayesian Spike-and-Slab Priors and Efficient Kernels [57.46832672991433]
We propose a novel equation discovery method based on Kernel learning and BAyesian Spike-and-Slab priors (KBASS)
We use kernel regression to estimate the target function, which is flexible, expressive, and more robust to data sparsity and noises.
We develop an expectation-propagation expectation-maximization algorithm for efficient posterior inference and function estimation.
arXiv Detail & Related papers (2023-10-09T03:55:09Z) - Efficient Convex Algorithms for Universal Kernel Learning [46.573275307034336]
An ideal set of kernels should: admit a linear parameterization (for tractability); dense in the set of all kernels (for accuracy)
Previous algorithms for optimization of kernels were limited to classification and relied on computationally complex Semidefinite Programming (SDP) algorithms.
We propose a SVD-QCQPQP algorithm which dramatically reduces the computational complexity as compared with previous SDP-based approaches.
arXiv Detail & Related papers (2023-04-15T04:57:37Z) - An Optimization-based Algorithm for Non-stationary Kernel Bandits
without Prior Knowledge [23.890686553141798]
We propose an algorithm for non-stationary kernel bandits that does not require prior knowledge of the degree of non-stationarity.
Our algorithm enjoys a tighter dynamic regret bound than previous work on the non-stationary kernel bandit setting.
arXiv Detail & Related papers (2022-05-29T21:32:53Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
This paper investigates the classical integer least-squares problem which estimates signals integer from linear models.
The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning.
We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
arXiv Detail & Related papers (2021-01-07T08:00:02Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
We introduce a novel algorithm improving over the state-of-the-art along multiple dimensions.
We establish minimax optimality for any learning horizon in the special case of non-contextual linear bandits.
arXiv Detail & Related papers (2020-10-23T09:12:47Z) - No-regret Algorithms for Multi-task Bayesian Optimization [26.13594355150718]
We consider multi-objective optimization (MOO) of an unknown vector-valued function in the non-parametric Bayesian optimization setting.
We develop two novel BO algorithms based on random scalarizations of the objectives.
We numerically benchmark our algorithms on both synthetic and real-life MOO problems, and show the advantages offered by learning with multi-task kernels.
arXiv Detail & Related papers (2020-08-20T10:55:20Z) - A New Algorithm for Tessellated Kernel Learning [4.264192013842097]
An ideal set of kernels should: admit a linear parameterization (for tractability); be dense in the set of all kernels (for robustness); be universal (for accuracy)
The recently proposed Tesselated Kernels (TKs) is currently the only known class which meets all three criteria.
By contrast, the 2-step algorithm proposed here scales to 10,000 data points and extends to the regression problem.
arXiv Detail & Related papers (2020-06-13T18:33:31Z) - Meta-learning with Stochastic Linear Bandits [120.43000970418939]
We consider a class of bandit algorithms that implement a regularized version of the well-known OFUL algorithm, where the regularization is a square euclidean distance to a bias vector.
We show both theoretically and experimentally, that when the number of tasks grows and the variance of the task-distribution is small, our strategies have a significant advantage over learning the tasks in isolation.
arXiv Detail & Related papers (2020-05-18T08:41:39Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
A fundamental component of neural network verification is the computation of bounds on the values their outputs can take.
We propose a novel approach based on Lagrangian Decomposition.
We show that we obtain bounds comparable with off-the-shelf solvers in a fraction of their running time.
arXiv Detail & Related papers (2020-02-24T17:55:10Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.