Continuum-Armed Bandits: A Function Space Perspective

Shashank Singh
Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR 130:2620-2628, 2021.

Abstract

The continuum-armed bandits problem involves optimizing an unknown objective function given an oracle that evaluates the function at a query point. In the most well-studied case, the objective function is assumed to be Lipschitz continuous and minimax rates of simple and cumulative regrets are known under both noiseless and noisy conditions. In this paper, we investigate continuum-armed bandits under more general smoothness conditions, namely Besov smoothness conditions, on the objective function. In both noiseless and noisy conditions, we derive minimax rates under both simple and cumulative regrets. In particular, our results show that minimax rates over objective functions in a Besov space are identical to minimax rates over objective functions in the smallest Holder space into which the Besov space embeds.

Cite this Paper

BibTeX
@InProceedings{pmlr-v130-singh21a, title = { Continuum-Armed Bandits: A Function Space Perspective }, author = {Singh, Shashank}, booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics}, pages = {2620--2628}, year = {2021}, editor = {Banerjee, Arindam and Fukumizu, Kenji}, volume = {130}, series = {Proceedings of Machine Learning Research}, month = {13--15 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v130/singh21a/singh21a.pdf}, url = {https://proceedings.mlr.press/v130/singh21a.html}, abstract = { The continuum-armed bandits problem involves optimizing an unknown objective function given an oracle that evaluates the function at a query point. In the most well-studied case, the objective function is assumed to be Lipschitz continuous and minimax rates of simple and cumulative regrets are known under both noiseless and noisy conditions. In this paper, we investigate continuum-armed bandits under more general smoothness conditions, namely Besov smoothness conditions, on the objective function. In both noiseless and noisy conditions, we derive minimax rates under both simple and cumulative regrets. In particular, our results show that minimax rates over objective functions in a Besov space are identical to minimax rates over objective functions in the smallest Holder space into which the Besov space embeds. } }
Endnote
%0 Conference Paper %T Continuum-Armed Bandits: A Function Space Perspective %A Shashank Singh %B Proceedings of The 24th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2021 %E Arindam Banerjee %E Kenji Fukumizu %F pmlr-v130-singh21a %I PMLR %P 2620--2628 %U https://proceedings.mlr.press/v130/singh21a.html %V 130 %X The continuum-armed bandits problem involves optimizing an unknown objective function given an oracle that evaluates the function at a query point. In the most well-studied case, the objective function is assumed to be Lipschitz continuous and minimax rates of simple and cumulative regrets are known under both noiseless and noisy conditions. In this paper, we investigate continuum-armed bandits under more general smoothness conditions, namely Besov smoothness conditions, on the objective function. In both noiseless and noisy conditions, we derive minimax rates under both simple and cumulative regrets. In particular, our results show that minimax rates over objective functions in a Besov space are identical to minimax rates over objective functions in the smallest Holder space into which the Besov space embeds.
APA
Singh, S.. (2021). Continuum-Armed Bandits: A Function Space Perspective . Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 130:2620-2628 Available from https://proceedings.mlr.press/v130/singh21a.html.

Related Material