Research map / Bandits and online learning / Multi-armed bandits
Leveraging (Biased) Information: Multi-armed Bandits with Offline Data
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that without a bias bound no non-anticipatory policy beats UCB even with biased offline data, and proposes MIN-UCB, which uses a valid bias bound to adaptively use or ignore offline data in stochastic bandits.
Problem
Online stochastic multi-armed bandits where offline data follow a possibly different reward distribution than the online rewards; the question is whether offline data can beat vanilla UCB without knowing the bias.
Approach
Without a bound on the offline-online distribution shift, no non-anticipatory policy can outperform UCB. Given a valid bias bound V per arm, MIN-UCB takes the minimum of the vanilla UCB and a warm-start UCB that pools offline and online samples plus a bias correction term, so it uses offline data only when they appear informative.
Key results
- Proposition 3.1 shows no non-anticipatory policy can beat vanilla UCB across all instances without a bias bound, giving Omega(T^{1-beta}) regret on a constructed alternative instance.
- MIN-UCB achieves instance-dependent regret O(sum_a max{log T/Delta(a) - Sav0(a), Delta(a)}) with Sav0 = T_S(a) Delta(a) max{1 - omega(a)/Delta(a), 0}^2, matched by a lower bound up to a small additive term.
- Instance-independent regret O(min{sqrt(KT log T), (1/sqrt(tau*) + V_max) T}) is shown to be nearly tight via a matching lower bound up to a log factor; in the aligned case it gives O(T sqrt(log T / tau*)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MIN-UCB with a valid non-trivial bias bound and offline data instead of vanilla UCB | MIN-UCB · Stochastic multi-armed bandits with biased offline data | regret | Helped |
| Use offline data without an additional bound on the difference between offline and online distributions | Non-anticipatory bandit policies · Stochastic multi-armed bandits with biased offline data | regret | No clear effect |
| Increase the offline sample size | MIN-UCB · Numerical experiments with small valid bias bound | regret | Helped |
| Increase the offline sample size | MIN-UCB · Numerical experiments with large valid bias bound | regret | No clear effect |
| Use MIN-UCB's adaptive choice between offline-informed and vanilla UCB estimates | MIN-UCB · Numerical experiments across valid bias bounds | regret | Helped |
Surprising findings
- The saving term can increase when the offline mean is pessimistically below the online mean, so the direction of bias matters, not just its magnitude.
- Even with infinite offline data and known distributions, no non-anticipatory policy can simultaneously beat UCB on the favorable instance and match it on the misleading one.
Limitations
- Requires a valid bias bound V as auxiliary input; no online method to tune V is possible per the impossibility result.
- Analysis restricted to 1-subGaussian rewards and independent arms with a single offline dataset per arm.
- Experiments are small simulations with K=4 Gaussian arms only.
Experimental setup
Benchmarks: simulated K=4 Gaussian bandit instances
Metrics: cumulative regret
Baselines: PURE-UCB (vanilla UCB) UCBS HUCB1 MonUCB ARROW-CB
Builds on: UCB (Auer et al., 2002) HUCB1 (Shivaswamy & Joachims, 2012) MonUCB (Banerjee et al., 2022) ARROW-CB (Zhang et al., 2019)
Closest papers by meaning
- Direction-Aware Offline-to-Online Learning in Linear Contextual Bandits (NeurIPS 2026 · similarity 0.91)
- Robustly Improving Bandit Algorithms with Confounded and Selection Biased Offline Data: A Causal Approach (AAAI 2024 · similarity 0.90)
- Regret minimization in Linear Bandits with offline data via extended D-optimal exploration. (NeurIPS 2026 · similarity 0.90)
- Bayesian Regret Minimization in Offline Bandits (ICML 2024 · similarity 0.89)
- On The Statistical Complexity of Offline Decision-Making (ICML 2024 · similarity 0.89)
- Leveraging Offline Data in Linear Latent Contextual Bandits (ICML 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.