Quantile-Regret Minimisation in Infinitely Many-Armed Bandits

Arghya Roy Chaudhuri, Shivaram Kalyanakrishnan
Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, PMLR R16:424-433, 2018.

Abstract

The stochastic multi-armed bandit is a well- studied abstraction of decision making in the face of uncertainty. We consider the setting in which the number of bandit arms is much larger than the possible number of pulls, and can even be infinite. With the aim of minimising regret with respect to an optimal arm, existing methods for this set- ting either assume some structure over the set of arms (Kleinberg et al., 2008, Ray Chowdhury and Gopalan, 2017), or some property of the re- ward distribution (Wang et al., 2008). Invariably, the validity of such assumptions—and therefore the performance of the corresponding methods— depends on instance-specific parameters, which might not be known beforehand. We propose a conceptually simple, parameter-free, and practically effective alternative. Specifically we introduce a notion of regret with respect to the top quantile of a probability distribution over the expected reward of randomly drawn arms. Our main contribution is an algorithm that achieves sublinear “quantile-regret”, both (1) when it is specified a quantile, and (2) when the quantile can be any (unknown) positive value. The algorithm needs no side information about the arms or about the structure of their reward distributions: it re- lies on random sampling to reach arms in the top quantile. Experiments show that our algorithm outperforms several previous methods (in terms of conventional regret) when the latter are not tuned well, and often even when they are.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR16-chaudhuri18a, title = {Quantile-Regret Minimisation in Infinitely Many-Armed Bandits}, author = {Chaudhuri, Arghya Roy and Kalyanakrishnan, Shivaram}, booktitle = {Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence}, pages = {424--433}, year = {2018}, editor = {Globerson, Amir and Silva, Ricardo}, volume = {R16}, series = {Proceedings of Machine Learning Research}, month = {06--10 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r16/main/assets/chaudhuri18a/chaudhuri18a.pdf}, url = {https://proceedings.mlr.press/r16/chaudhuri18a.html}, abstract = {The stochastic multi-armed bandit is a well- studied abstraction of decision making in the face of uncertainty. We consider the setting in which the number of bandit arms is much larger than the possible number of pulls, and can even be infinite. With the aim of minimising regret with respect to an optimal arm, existing methods for this set- ting either assume some structure over the set of arms (Kleinberg et al., 2008, Ray Chowdhury and Gopalan, 2017), or some property of the re- ward distribution (Wang et al., 2008). Invariably, the validity of such assumptions—and therefore the performance of the corresponding methods— depends on instance-specific parameters, which might not be known beforehand. We propose a conceptually simple, parameter-free, and practically effective alternative. Specifically we introduce a notion of regret with respect to the top quantile of a probability distribution over the expected reward of randomly drawn arms. Our main contribution is an algorithm that achieves sublinear “quantile-regret”, both (1) when it is specified a quantile, and (2) when the quantile can be any (unknown) positive value. The algorithm needs no side information about the arms or about the structure of their reward distributions: it re- lies on random sampling to reach arms in the top quantile. Experiments show that our algorithm outperforms several previous methods (in terms of conventional regret) when the latter are not tuned well, and often even when they are.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Quantile-Regret Minimisation in Infinitely Many-Armed Bandits %A Arghya Roy Chaudhuri %A Shivaram Kalyanakrishnan %B Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2018 %E Amir Globerson %E Ricardo Silva %F pmlr-vR16-chaudhuri18a %I PMLR %P 424--433 %U https://proceedings.mlr.press/r16/chaudhuri18a.html %V R16 %X The stochastic multi-armed bandit is a well- studied abstraction of decision making in the face of uncertainty. We consider the setting in which the number of bandit arms is much larger than the possible number of pulls, and can even be infinite. With the aim of minimising regret with respect to an optimal arm, existing methods for this set- ting either assume some structure over the set of arms (Kleinberg et al., 2008, Ray Chowdhury and Gopalan, 2017), or some property of the re- ward distribution (Wang et al., 2008). Invariably, the validity of such assumptions—and therefore the performance of the corresponding methods— depends on instance-specific parameters, which might not be known beforehand. We propose a conceptually simple, parameter-free, and practically effective alternative. Specifically we introduce a notion of regret with respect to the top quantile of a probability distribution over the expected reward of randomly drawn arms. Our main contribution is an algorithm that achieves sublinear “quantile-regret”, both (1) when it is specified a quantile, and (2) when the quantile can be any (unknown) positive value. The algorithm needs no side information about the arms or about the structure of their reward distributions: it re- lies on random sampling to reach arms in the top quantile. Experiments show that our algorithm outperforms several previous methods (in terms of conventional regret) when the latter are not tuned well, and often even when they are. %Z Reissued by PMLR on 04 October 2026.
APA
Chaudhuri, A.R. & Kalyanakrishnan, S.. (2018). Quantile-Regret Minimisation in Infinitely Many-Armed Bandits. Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R16:424-433 Available from https://proceedings.mlr.press/r16/chaudhuri18a.html. Reissued by PMLR on 04 October 2026.

Related Material