Towards Sharp Performance Bounds for Kernel-Based Bandit Optimization Problems
COM3 Level 2
SR21, COM3 02-60
Abstract:
Optimization of an expensive-to-evaluate function based on black-box queries is a ubiquitous problem in machine learning. In this thesis, we first consider kernel-based bandit optimization problems using Gaussian process (GP) optimization. Assuming the underlying function is a GP bandit that has a low complexity associated with some given kernel, we study this problem under three specific settings: (1) GP bandit optimization based on few batches of noisy observations, (2) cascaded GP bandit optimization based on noise-free observations, and (3) GP bandit optimization based on adversarially corrupted observations. In addition to the traditional function optimization problem, we also study the fair item allocation problem with noisy item value queries and model it as a kernel-based bandit allocation problem.
For the few batches setting, we introduce a batch algorithm BPE using O(loglogT) batches within time horizon T, which achieves near-optimal cumulative regret bound for the squared exponential (SE) and Matern kernels. In addition, in the case of a constant number of batches, we propose a modified version of our algorithm, and characterize how the regret is impacted by the number of batches. The algorithmic upper bounds are shown to be nearly minimax optimal via analogous algorithm-independent lower bounds.
For the cascaded setting, we consider optimizing a function network composed of multiple GP bandits, where the exact intermediate results are observable. We assume that the structure of the network is known, and we study three types of structure: chain, multi-output chain, and feed-forward network. We propose a sequential upper confidence bound based algorithm GPN-UCB and a non-adaptive sampling based method. We also establish algorithm-independent lower bounds on the simple and cumulative regret. Our regret bounds for GPN-UCB have the same dependence on the time horizon as the best known in the vanilla black-box setting, as well as near-optimal dependencies on other parameters.
For the corrupted setting, we experimentally evaluate the RGP-PE algorithm proposed by our collaborator Bogunovic et al. (2022), which attains near-optimal cumulative regret bound for the SE kernel and improves upon the existing regret guarantee for the Matern kernel. The experimental results evidence that RGP-PE is able to defend against various adversarial attacks in practice. We also propose an alternative approach based on bandit reduction, whose cumulative regret bound for the SE kernel matches that of RGP-PE.
Lastly, for the fair item allocation problem, where the agents have additive utilities over multiple items and the utilities can be evaluated via noisy item value queries, we study the query complexity for producing an envy-free allocation. We propose a repeated sampling based method for independent utilities with query complexity upper bound and establish a corresponding algorithm-independent lower bound. We also consider kernel-based utilities and show that the correlation between utilities decreases the number of queries required by envy-free fairness. Given the gap between the upper and lower bounds, we further discuss the challenges in attaining a tight query complexity upper bound.