# Artificial Replay: A Meta-Algorithm for Harnessing Historical Data in Bandits

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 56 references that are in the map.
- First posted on arXiv 30 Sep 2022.

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

- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Prioritized Experience Replay](https://mlsanity.com/paper/1511.05952/) (2015)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Learning to Optimize via Information-Directed Sampling](https://mlsanity.com/paper/1403.5556/) (2014)
- [Bandits and Experts in Metric Spaces](https://mlsanity.com/paper/1312.1277/) (2013)
- [Warm-starting Contextual Bandits: Robustly Combining Supervised and Bandit Feedback](https://mlsanity.com/paper/1901.00301/) (2019)
- [Optimal Exploitation of Clustering and History Information in Multi-Armed Bandit](https://mlsanity.com/paper/1906.03979/) (2019)
- [Dual-Mandate Patrols: Multi-Armed Bandits for Green Security](https://mlsanity.com/paper/2009.06560/) (2020)
- [Adaptive Discretization in Online Reinforcement Learning](https://mlsanity.com/paper/2110.15843/) (2021)
- [Stay Ahead of Poachers: Illegal Wildlife Poaching Prediction and Patrol Planning Under Uncertainty with Field Test Evaluations](https://mlsanity.com/paper/1903.06669/) (2019)
- [Combinatorial Multi-armed Bandits for Resource Allocation](https://mlsanity.com/paper/2105.04373/) (2021)
- [Optimal Resource Allocation with Semi-Bandit Feedback](https://mlsanity.com/paper/1406.3840/) (2014)
- [A Better Resource Allocation Algorithm with Semi-Bandit Feedback](https://mlsanity.com/paper/1803.10415/) (2018)
- [Observe Before Play: Multi-armed Bandit with Pre-observations](https://mlsanity.com/paper/1911.09458/) (2019)

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

- [Multi-Armed Bandits With Machine Learning-Generated Surrogate Rewards](https://mlsanity.com/paper/2506.16658/) (2025)
- [Leveraging Demonstrations to Improve Online Learning: Quality Matters](https://mlsanity.com/paper/2302.03319/) (2023)
- [Optimal Best-Arm Identification in Bandits with Access to Offline Data](https://mlsanity.com/paper/2306.09048/) (2023)
- [Online Bandit Learning with Offline Preference Data for Improved RLHF](https://mlsanity.com/paper/2406.09574/) (2024)
- [Speed Up the Cold-Start Learning in Two-Sided Bandits with Many Arms](https://mlsanity.com/paper/2210.00340/) (2022)
- [Design Experiments to Compare Multi-armed Bandit Algorithms](https://mlsanity.com/paper/2603.05919/) (2026)
- [Deconfounded Warm-Start Thompson Sampling with Applications to Precision Medicine](https://mlsanity.com/paper/2505.17283/) (2025)
- [Offline Clustering of Preference Learning with Active-data Augmentation](https://mlsanity.com/paper/2510.26301/) (2025)
- [Multi-Objective Reward and Preference Optimization: Theory and Algorithms](https://mlsanity.com/paper/2512.10601/) (2025)
- [Offline-Online Reinforcement Learning for Linear Mixture MDPs](https://mlsanity.com/paper/2604.11994/) (2026)
- [Sample-Mean Anchored Thompson Sampling for Offline-to-Online Learning with Distribution Shift](https://mlsanity.com/paper/2605.10289/) (2026)
- [Fast A/B/n Testing: Exact Multi-Policy Comparison via Tree-Coupled Feedback Sharing](https://mlsanity.com/paper/2608.12831/) (2026)
- [Beyond Reward Suppression: Near-Optimal Offline Attacks on Warm-Start Bandits with Bounded Rewards](https://mlsanity.com/paper/2610.10000/) (2026)

## Abstract (arXiv)

Most real-world deployments of bandit algorithms exist somewhere in between the offline and online set-up, where some historical data is available upfront and additional data is collected dynamically online. How best to incorporate historical data to "warm start" bandit algorithms is an open question: naively initializing reward estimates using all historical samples can suffer from spurious data and imbalanced data coverage, leading to data inefficiency (amount of historical data used) - particularly for continuous action spaces. To address these challenges, we propose ArtificialReplay, a meta-algorithm for incorporating historical data into any arbitrary base bandit algorithm. We show that ArtificialReplay uses only a fraction of the historical data compared to a full warm-start approach, while still achieving identical regret for base algorithms that satisfy independence of irrelevant data (IIData), a novel and broadly applicable property that we introduce. We complement these theoretical results with experiments on K-armed bandits and continuous combinatorial bandits, on which we model green security domains using real poaching data. Our results show the practical benefits of ArtificialReplay for improving data efficiency, including for base algorithms that do not satisfy IIData.