# Online Multi-Armed Bandits with Adaptive Inference

arXiv: https://arxiv.org/abs/2102.13202 · HTML: https://mlsanity.com/paper/2102.13202/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 56 references that are in the map.
- First posted on arXiv 25 Feb 2021.

## Builds on (most cited first, 16 of 16)

- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Simple Bayesian Algorithms for Best Arm Identification](https://mlsanity.com/paper/1602.08448/) (2016)
- [Confidence Intervals for Policy Evaluation in Adaptive Experiments](https://mlsanity.com/paper/1911.02768/) (2019)
- [Scalable Generalized Linear Bandits: Online Computation and Hashing](https://mlsanity.com/paper/1706.00136/) (2017)
- [A Contextual Bandit Bake-off](https://mlsanity.com/paper/1802.04064/) (2018)
- [Inference for Batched Bandits](https://mlsanity.com/paper/2002.03217/) (2020)
- [Why Adaptively Collected Data Have Negative Bias and How to Correct for It](https://mlsanity.com/paper/1708.01977/) (2017)
- [Thompson Sampling for the MNL-Bandit](https://mlsanity.com/paper/1706.00977/) (2017)
- [Balanced Linear Contextual Bandits](https://mlsanity.com/paper/1812.06227/) (2018)
- [Upper-Confidence-Bound Algorithms for Active Learning in Multi-Armed Bandits](https://mlsanity.com/paper/1507.04523/) (2015)
- [On the bias, risk and consistency of sample means in multi-armed bandits](https://mlsanity.com/paper/1902.00746/) (2019)
- [Estimation Considerations in Contextual Bandits](https://mlsanity.com/paper/1711.07077/) (2017)
- [Mitigating Bias in Adaptive Data Gathering via Differential Privacy](https://mlsanity.com/paper/1806.02329/) (2018)

## Built on by (most cited first, 22 of 22)

- [Anytime-valid off-policy inference for contextual bandits](https://mlsanity.com/paper/2210.10768/) (2022)
- [Non-Stationary Representation Learning in Sequential Linear Bandits](https://mlsanity.com/paper/2201.04805/) (2022)
- [An Experimental Design for Anytime-Valid Causal Inference on Multi-Armed Bandits](https://mlsanity.com/paper/2311.05794/) (2023)
- [Online Experimental Design With Estimation-Regret Trade-off Under Network Interference](https://mlsanity.com/paper/2412.03727/) (2024)
- [Reinforcement Learning in Modern Biostatistics: Constructing Optimal Adaptive Interventions](https://mlsanity.com/paper/2203.02605/) (2022)
- [Adaptive Linear Estimating Equations](https://mlsanity.com/paper/2307.07320/) (2023)
- [Optimal Adaptive Experimental Design for Estimating Treatment Effect](https://mlsanity.com/paper/2410.05552/) (2024)
- [Doubly Robust Interval Estimation for Optimal Policy Evaluation in Online Learning](https://mlsanity.com/paper/2110.15501/) (2021)
- [Optimal Best Arm Identification in Two-Armed Bandits with a Fixed Budget under a Small Gap](https://mlsanity.com/paper/2201.04469/) (2022)
- [Allocation Stability and Wald Inference under Variance-Aware UCB](https://mlsanity.com/paper/2412.08843/) (2024)
- [Valid Best-Model Identification for LLM Evaluation via Low-Rank Factorization](https://mlsanity.com/paper/2605.10405/) (2026)
- [Best Arm Identification with Contextual Information under a Small Gap](https://mlsanity.com/paper/2209.07330/) (2022)
- [Statistical Inference in Reinforcement Learning: A Selective Survey](https://mlsanity.com/paper/2502.16195/) (2025)
- [A characterization of sample adaptivity in UCB data](https://mlsanity.com/paper/2503.04855/) (2025)
- [Optimism Stabilizes Thompson Sampling for Adaptive Inference](https://mlsanity.com/paper/2602.06014/) (2026)
- [Some performance considerations when using multi-armed bandit algorithms in the presence of missing data](https://mlsanity.com/paper/2205.03820/) (2022)
- [Entropy Regularization for Population Estimation](https://mlsanity.com/paper/2208.11747/) (2022)
- [Design-Based Bandits Under Network Interference: Trade-Off Between Regret and Statistical Inference](https://mlsanity.com/paper/2510.07646/) (2025)
- [An Online Bootstrap for Time Series](https://mlsanity.com/paper/2310.19683/) (2023)
- [Navigating the Evaluation Funnel to Optimize Iteration Speed for Recommender Systems](https://mlsanity.com/paper/2404.08671/) (2024)
- [Adaptive Experiments Under Data Sparse Settings: Applications for Educational Platforms](https://mlsanity.com/paper/2501.03999/) (2025)
- [Sampling Allocation of LinUCB: Optimal Design Limits in the Small-Gap Regime](https://mlsanity.com/paper/2610.06213/) (2026)

## Abstract (arXiv)

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.