# Online Bandits with (Biased) Offline Data: Adaptive Learning under Distribution Mismatch

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 May 2024.

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

- [Multi-Armed Bandits With Machine Learning-Generated Surrogate Rewards](https://mlsanity.com/paper/2506.16658/) (2025)
- [Balancing optimism and pessimism in offline-to-online learning](https://mlsanity.com/paper/2502.08259/) (2025)
- [Optimal Adaptive Experimental Design for Estimating Treatment Effect](https://mlsanity.com/paper/2410.05552/) (2024)
- [Best Arm Identification with Possibly Biased Offline Data](https://mlsanity.com/paper/2505.23165/) (2025)
- [Augmenting Online RL with Offline Data is All You Need: A Unified Hybrid RL Algorithm Design and Analysis](https://mlsanity.com/paper/2505.13768/) (2025)
- [Using causal abstractions to accelerate decision-making in complex bandit problems](https://mlsanity.com/paper/2509.04296/) (2025)
- [Bayesian Decision Making around Experts](https://mlsanity.com/paper/2510.08113/) (2025)
- [Offline Clustering of Preference Learning with Active-data Augmentation](https://mlsanity.com/paper/2510.26301/) (2025)
- [The Value of Information in Resource-Constrained Pricing](https://mlsanity.com/paper/2603.24974/) (2026)
- [Offline-Online Reinforcement Learning for Linear Mixture MDPs](https://mlsanity.com/paper/2604.11994/) (2026)

## Abstract (arXiv)

Traditional online learning models are typically initialized from scratch. By contrast, contemporary real-world applications often have access to historical datasets that can potentially enhanced the online learning processes. We study how offline data can be leveraged to facilitate online learning in stochastic multi-armed bandits and combinatorial bandits. In our study, the probability distributions that govern the offline data and the online rewards can be different. We first show that, without a non-trivial upper bound on their difference, no non-anticipatory policy can outperform the classical Upper Confidence Bound (UCB) policy, even with the access to offline data. In complement, we propose an online policy MIN-UCB for multi-armed bandits. MIN-UCB outperforms the UCB when such an upper bound is available. MIN-UCB adaptively chooses to utilize the offline data when they are deemed informative, and to ignore them otherwise. We establish that MIN-UCB achieves tight regret bounds, in both instance independent and dependent settings. We generalize our approach to the combinatorial bandit setting by introducing MIN-COMB-UCB, and we provide corresponding instance dependent and instance independent regret bounds. We illustrate how various factors, such as the biases and the size of offline datasets, affect the utility of offline data in online learning. We discuss several applications and conduct numerical experiments to validate our findings.