On Conditional Versus Marginal Bias in Multi-Armed Bandits

Jaehyeok Shin, Aaditya Ramdas, Alessandro Rinaldo
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:8852-8861, 2020.

Abstract

The bias of the sample means of the arms in multi-armed bandits is an important issue in adaptive data analysis that has recently received considerable attention in the literature. Existing results relate in precise ways the sign and magnitude of the bias to various sources of data adaptivity, but do not apply to the conditional inference setting in which the sample means are computed only if some specific conditions are satisfied. In this paper, we characterize the sign of the conditional bias of monotone functions of the rewards, including the sample mean. Our results hold for arbitrary conditioning events and leverage natural monotonicity properties of the data collection policy. We further demonstrate, through several examples from sequential testing and best arm identification, that the sign of the conditional and marginal bias of the sample mean of an arm can be different, depending on the conditioning event. Our analysis offers new and interesting perspectives on the subtleties of assessing the bias in data adaptive settings.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-shin20a, title = {On Conditional Versus Marginal Bias in Multi-Armed Bandits}, author = {Shin, Jaehyeok and Ramdas, Aaditya and Rinaldo, Alessandro}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {8852--8861}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/shin20a/shin20a.pdf}, url = {https://proceedings.mlr.press/v119/shin20a.html}, abstract = {The bias of the sample means of the arms in multi-armed bandits is an important issue in adaptive data analysis that has recently received considerable attention in the literature. Existing results relate in precise ways the sign and magnitude of the bias to various sources of data adaptivity, but do not apply to the conditional inference setting in which the sample means are computed only if some specific conditions are satisfied. In this paper, we characterize the sign of the conditional bias of monotone functions of the rewards, including the sample mean. Our results hold for arbitrary conditioning events and leverage natural monotonicity properties of the data collection policy. We further demonstrate, through several examples from sequential testing and best arm identification, that the sign of the conditional and marginal bias of the sample mean of an arm can be different, depending on the conditioning event. Our analysis offers new and interesting perspectives on the subtleties of assessing the bias in data adaptive settings.} }
Endnote
%0 Conference Paper %T On Conditional Versus Marginal Bias in Multi-Armed Bandits %A Jaehyeok Shin %A Aaditya Ramdas %A Alessandro Rinaldo %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-shin20a %I PMLR %P 8852--8861 %U https://proceedings.mlr.press/v119/shin20a.html %V 119 %X The bias of the sample means of the arms in multi-armed bandits is an important issue in adaptive data analysis that has recently received considerable attention in the literature. Existing results relate in precise ways the sign and magnitude of the bias to various sources of data adaptivity, but do not apply to the conditional inference setting in which the sample means are computed only if some specific conditions are satisfied. In this paper, we characterize the sign of the conditional bias of monotone functions of the rewards, including the sample mean. Our results hold for arbitrary conditioning events and leverage natural monotonicity properties of the data collection policy. We further demonstrate, through several examples from sequential testing and best arm identification, that the sign of the conditional and marginal bias of the sample mean of an arm can be different, depending on the conditioning event. Our analysis offers new and interesting perspectives on the subtleties of assessing the bias in data adaptive settings.
APA
Shin, J., Ramdas, A. & Rinaldo, A.. (2020). On Conditional Versus Marginal Bias in Multi-Armed Bandits. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:8852-8861 Available from https://proceedings.mlr.press/v119/shin20a.html.

Related Material