Open Problem: Regret Bounds for Noise-Free Kernel-Based Bandits
Abstract
Kernel-based bandit is an extensively studied black-box optimization problem, in which the objective function is assumed to live in a known reproducing kernel Hilbert space. While nearly optimal regret bounds (up to logarithmic factors) are established in the noisy setting, surprisingly, less is known about the noise-free setting (when the exact values of the underlying function is accessible without observation noise). We discuss several upper bounds on regret; none of which seem order optimal, and provide a conjecture on the order optimal regret bound.
Cite
Text
Vakili. "Open Problem: Regret Bounds for Noise-Free Kernel-Based Bandits." Conference on Learning Theory, 2022.Markdown
[Vakili. "Open Problem: Regret Bounds for Noise-Free Kernel-Based Bandits." Conference on Learning Theory, 2022.](https://mlanthology.org/colt/2022/vakili2022colt-open/)BibTeX
@inproceedings{vakili2022colt-open,
title = {{Open Problem: Regret Bounds for Noise-Free Kernel-Based Bandits}},
author = {Vakili, Sattar},
booktitle = {Conference on Learning Theory},
year = {2022},
pages = {5624-5629},
volume = {178},
url = {https://mlanthology.org/colt/2022/vakili2022colt-open/}
}