Maria Dimakopoulou, Zhimei Ren, Zhengyuan Zhou
arXiv 25 Feb 2021 · Machine Learning · 14 citations (OpenAlex)
arXiv:2102.13202 · PDF · DOI · OpenAlex · Extracted main text
During online decision making in Multi-Armed Bandits (MAB), one needs to conduct inference on the true mean reward of each arm based on data collected so far at each step. However, since the arms are adaptively selected--thereby yielding non-iid data--conducting inference accurately is not straightforward. In particular, sample averaging, which is used in the family of UCB and Thompson sampling (TS) algorithms, does not provide a good choice as it suffers from bias and a lack of good statistical properties (e.g. asymptotic normality). Our thesis in this paper is that more sophisticated inference schemes that take into account the adaptive nature of the sequentially collected data can unlock further performance gains, even though both UCB and TS type algorithms are optimal in the worst case. In particular, we propose a variant of TS-style algorithms--which we call doubly adaptive TS--that leverages recent advances in causal inference and adaptively reweights the terms of a doubly robust estimator on the true mean reward of each arm. Through 20 synthetic domain experiments and a semi-synthetic experiment based on data from an A/B test of a web service, we demonstrate that using an adaptive inferential scheme (while still retaining the exploration efficacy of TS) provides clear benefits in online decision making: the proposed DATS algorithm has superior empirical performance to existing baselines (UCB and TS) in terms of regret and sample complexity in identifying the best arm. In addition, we also provide a finite-time regret bound of doubly adaptive TS that matches (up to log factors) those of UCB and TS algorithms, thereby establishing that its improved practical benefits do not come at the expense of worst-case suboptimality.
appendix boundary found by appendix_command · 76% of the source is main text. Read the extracted text to check this.
The works this paper leans on most, across its whole bibliography — not restricted to papers in our corpus. Ranked by composite intensity, which combines how often a work is mentioned, how many sections mention it, and how much of that falls in the main text rather than the appendix.
| Reference | Intensity | Mentions | Sections | Main text | |
|---|---|---|---|---|---|
| 1 | Hadad, V., Hirshberg, D. A., Zhan, R., Wager, S., and Athey, S (2019) Confidence intervals for policy evaluation in adaptive experiments | 0.874 | 11 | 2 | 100% |
| 2 | Luedtke, A. R. and Van Der Laan, M. J (2016) Statistical inference for the mean outcome under a possibly non-unique optimal treatment strategy | 0.874 | 11 | 2 | 100% |
| 3 | Auer, P., Cesa-Bianchi, N., and Fischer, P (2002) Finite-time analysis of the multiarmed bandit problem | 0.843 | 3 | 3 | 100% |
| 4 | Bowden, J. and Trippa, L (2017) Unbiased estimation for response adaptive clinical trials | 0.644 | 2 | 2 | 100% |
| 5 | Lattimore, T. and Szepesvári, C (2020) Bandit algorithms | 0.644 | 2 | 2 | 100% |
| 6 | Nie, X., Tian, X., Taylor, J., and Zou, J (2018) Why adaptively collected data have negative bias and how to correct for it | 0.644 | 2 | 2 | 100% |
| 7 | Russo, D., Van Roy, B., Kazerouni, A., Osband, I., and Wen, Z (2017) A tutorial on thompson sampling | 0.644 | 2 | 2 | 100% |
| 8 | Shin, J., Ramdas, A., and Rinaldo, A (2019) On the bias, risk and consistency of sample means in multi-armed bandits | 0.644 | 2 | 2 | 100% |
| 9 | Xu, M., Qin, T., and Liu, T.-Y (2013) Estimation bias in multi-armed bandit algorithms for search advertising | 0.644 | 2 | 2 | 100% |
| 10 | Russo, D (2016) Simple bayesian algorithms for best arm identification | 0.511 | 2 | 1 | 100% |
Showing the top 10 of 52 scored citations.
arXiv econ.EM papers that cite this one, ranked by how heavily they lean on it.