# Optimal Exploitation of Clustering and History Information in Multi-Armed Bandit

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

## Key facts

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

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

- [Optimal Clustering with Bandit Feedback](https://mlsanity.com/paper/2202.04294/) (2022)
- [Artificial Replay: A Meta-Algorithm for Harnessing Historical Data in Bandits](https://mlsanity.com/paper/2210.00025/) (2022)
- [Optimal Best-Arm Identification in Bandits with Access to Offline Data](https://mlsanity.com/paper/2306.09048/) (2023)
- [Max-Min Grouped Bandits](https://mlsanity.com/paper/2111.08862/) (2021)
- [Thompson Sampling for Bandits with Clustered Arms](https://mlsanity.com/paper/2109.01656/) (2021)
- [Online Bandit Learning with Offline Preference Data for Improved RLHF](https://mlsanity.com/paper/2406.09574/) (2024)
- [Best Arm Identification with Possibly Biased Offline Data](https://mlsanity.com/paper/2505.23165/) (2025)
- [Natural Hierarchical Cluster Analysis by Nearest Neighbors with Near-Linear Time Complexity](https://mlsanity.com/paper/2203.08027/) (2022)
- [Etat de l'art sur l'application des bandits multi-bras](https://mlsanity.com/paper/2101.00001/) (2021)
- [A recommender for the management of chronic pain in patients undergoing spinal cord stimulation](https://mlsanity.com/paper/2309.03918/) (2023)
- [Identifiable Latent Bandits: Leveraging observational data for personalized decision-making](https://mlsanity.com/paper/2407.16239/) (2024)
- [Multi-Objective Reward and Preference Optimization: Theory and Algorithms](https://mlsanity.com/paper/2512.10601/) (2025)
- [Almost Asymptotically Optimal Active Clustering Through Pairwise Observations](https://mlsanity.com/paper/2602.05690/) (2026)
- [Fast Online Learning with Gaussian Prior-Driven Hierarchical Unimodal Thompson Sampling](https://mlsanity.com/paper/2602.15972/) (2026)

## Abstract (arXiv)

We consider the stochastic multi-armed bandit problem and the contextual bandit problem with historical observations and pre-clustered arms. The historical observations can contain any number of instances for each arm, and the pre-clustering information is a fixed clustering of arms provided as part of the input. We develop a variety of algorithms which incorporate this offline information effectively during the online exploration phase and derive their regret bounds. In particular, we develop the META algorithm which effectively hedges between two other algorithms: one which uses both historical observations and clustering, and another which uses only the historical observations. The former outperforms the latter when the clustering quality is good, and vice-versa. Extensive experiments on synthetic and real world datasets on Warafin drug dosage and web server selection for latency minimization validate our theoretical insights and demonstrate that META is a robust strategy for optimally exploiting the pre-clustering information.