Yunbei Xu
We propose a MAIR framework that unifies GP-UCB and DEC methods, and prove that in kernel bandits, algorithmic complexity can be more useful than minimax complexity.
Existing GP-UCB and DEC methods have different theoretical backgrounds, lacking a unified understanding. In particular, the relationship and difference between algorithmic complexity and class-wide minimax complexity needed to be clarified.
We introduce the MAIR framework to integrate GP-UCB's algorithmic prior and MAMS's minimax approach. Using heterogeneous positive-semidefinite algorithmic priors, we generalize both methods and propose a safeguarded master algorithm that combines their advantages. Additionally, we provide a concrete construction in the kernel bandit setting showing that algorithmic complexity is more useful in overparameterized models.
We show that algorithmic information and class-wide minimax coefficients answer different questions, and their difference becomes mathematically clear in kernel bandits. This provides new insights into the relationship between algorithmic complexity and minimax complexity in bandit theory.