Efficient kernelized bandit algorithms via exploration distributions

2025-06-11 · Bingshan Hu, Zheng He, Danica J. Sutherland

We consider a kernelized bandit problem with a compact arm set ${X} \subset \mathbb{R}^d $ and a fixed but unknown reward function $f^*$ with a finite norm in some Reproducing Kernel Hilbert Space (RKHS). We propose a class of computationally efficient kernelized bandit algorithms, which we call GP-Generic, based on a novel concept: exploration distributions. This class of algorithms includes Upper Confidence Bound-based approaches as a special case, but also allows for a variety of randomized algorithms. With careful choice of exploration distribution, our proposed generic algorithm realizes a wide range of concrete algorithms that achieve $\tilde{O}(\gamma_T\sqrt{T})$ regret bounds, where $\gamma_T$ characterizes the RKHS complexity. This matches known results for UCB- and Thompson Sampling-based algorithms; we also show that in practice, randomization can yield better practical results.

📄 PDF Abstract BibTeX arXiv:2506.10091

Code (0)

등록된 구현이 없습니다.

Tasks

Thompson Sampling

Methods 이 논문이 사용한 방법론

SET Dynamic Sparse Training method where weight mask is updated randomly periodically

Collaborative Pure Exploration in Kernel Bandit

2021-10-29 · Yihan Du, Wei Chen, Yuko Kuroki, Longbo Huang

In this paper, we formulate a Collaborative Pure Exploration in Kernel Bandit problem (CoPE-KB), which provides a novel model for multi-agent multi-task decision making under limited communication and general reward func…

Decision Making Recommendation Systems Scheduling

On Kernelized Multi-Armed Bandits with Constraints

2022-03-29 · Xingyu Zhou, Bo Ji

We study a stochastic bandit problem with a general unknown reward function and a general unknown constraint function. Both functions can be non-linear (even non-convex) and are assumed to lie in a reproducing kernel Hil…

Multi-Armed Bandits Thompson Sampling

Laplacian Kernelized Bandit

2026-01-01 · Shuang Wu, Arash A. Amini arxiv

We study multi-user contextual bandits where users are related by a graph and their reward functions exhibit both non-linear behavior and graph homophily. We introduce a principled joint penalty for the collection of use…

Bandits with Preference Feedback: A Stackelberg Game Perspective

2024-06-24 · Barna Pásztor, Parnian Kassraie, Andreas Krause

Bandits with preference feedback present a powerful tool for optimizing unknown target functions when only pairwise comparisons are allowed instead of direct value queries. This model allows for incorporating human feedb…

valid

Mostly Exploration-Free Algorithms for Contextual Bandits

2017-04-28 · Hamsa Bastani, Mohsen Bayati, Khashayar Khosravi

The contextual bandit literature has traditionally focused on algorithms that address the exploration-exploitation tradeoff. In particular, greedy algorithms that exploit current estimates without any exploration may be …

Diversity Multi-Armed Bandits Thompson Sampling