Open Problem: Regret Bounds for Noise-Free Kernel-Based Bandits

Sattar Vakili
Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:5624-5629, 2022.

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 this Paper

BibTeX
@InProceedings{pmlr-v178-open-problem-vakili22a, title = {Open Problem: Regret Bounds for Noise-Free Kernel-Based Bandits}, author = {Vakili, Sattar}, booktitle = {Proceedings of Thirty Fifth Conference on Learning Theory}, pages = {5624--5629}, year = {2022}, editor = {Loh, Po-Ling and Raginsky, Maxim}, volume = {178}, series = {Proceedings of Machine Learning Research}, month = {02--05 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v178/open-problem-vakili22a/open-problem-vakili22a.pdf}, url = {https://proceedings.mlr.press/v178/open-problem-vakili22a.html}, 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.} }
Endnote
%0 Conference Paper %T Open Problem: Regret Bounds for Noise-Free Kernel-Based Bandits %A Sattar Vakili %B Proceedings of Thirty Fifth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Po-Ling Loh %E Maxim Raginsky %F pmlr-v178-open-problem-vakili22a %I PMLR %P 5624--5629 %U https://proceedings.mlr.press/v178/open-problem-vakili22a.html %V 178 %X 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.
APA
Vakili, S.. (2022). Open Problem: Regret Bounds for Noise-Free Kernel-Based Bandits. Proceedings of Thirty Fifth Conference on Learning Theory, in Proceedings of Machine Learning Research 178:5624-5629 Available from https://proceedings.mlr.press/v178/open-problem-vakili22a.html.

Related Material