# Open Problem: Tight Bounds for Kernelized Multi-Armed Bandits with Bernoulli Rewards

arXiv: https://arxiv.org/abs/2407.06321 · HTML: https://mlsanity.com/paper/2407.06321/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 19 references that are in the map.
- First posted on arXiv 8 Jul 2024.

## Builds on (most cited first, 6 of 6)

- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.4758/) (2014)
- [Jointly Efficient and Optimal Algorithms for Logistic Bandits](https://mlsanity.com/paper/2201.01985/) (2022)
- [Instance-Dependent Regret Analysis of Kernelized Bandits](https://mlsanity.com/paper/2203.06297/) (2022)
- [Efficient learning of smooth probability functions from Bernoulli tests with guarantees](https://mlsanity.com/paper/1812.04428/) (2018)
- [Simultaneous Inference for Multiple Proportions: A Multivariate Beta-Binomial Model](https://mlsanity.com/paper/1911.00098/) (2019)

## Built on by (most cited first, 3 of 3)

- [A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits](https://mlsanity.com/paper/2407.13977/) (2024)
- [Generalized Kernelized Bandits: A Novel Self-Normalized Bernstein-Like Dimension-Free Inequality and Regret Bounds](https://mlsanity.com/paper/2508.01681/) (2025)
- [Online Dynamic Pricing of Complementary Products](https://mlsanity.com/paper/2511.22291/) (2025)

## Abstract (arXiv)

We consider Kernelized Bandits (KBs) to optimize a function f : X rightarrow [0,1] belonging to the Reproducing Kernel Hilbert Space (RKHS) Hk. Mainstream works on kernelized bandits focus on a subgaussian noise model in which observations of the form f(xt)+εt, being εt a subgaussian noise, are available (Chowdhury and Gopalan, 2017). Differently, we focus on the case in which we observe realizations yt ~ Ber(f(xt)) sampled from a Bernoulli distribution with parameter f(xt). While the Bernoulli model has been investigated successfully in multi-armed bandits (Garivier and Capp'e, 2011), logistic bandits (Faury et al., 2022), bandits in metric spaces (Magureanu et al., 2014), it remains an open question whether tight results can be obtained for KBs. This paper aims to draw the attention of the online learning community to this open problem.