# Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 20 references that are in the map.
- First posted on arXiv 24 May 2024.

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

- [Learning to Optimize via Information-Directed Sampling](https://mlsanity.com/paper/1403.5556/) (2014)
- [Information Directed Sampling and Bandits with Heteroscedastic Noise](https://mlsanity.com/paper/1801.09667/) (2018)
- [The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits](https://mlsanity.com/paper/1610.04491/) (2016)
- [Information Directed Sampling for Linear Partial Monitoring](https://mlsanity.com/paper/2002.11182/) (2020)
- [Asymptotically Optimal Information-Directed Sampling](https://mlsanity.com/paper/2011.05944/) (2020)
- [Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Bandits](https://mlsanity.com/paper/2309.00814/) (2023)
- [Maillard Sampling: Boltzmann Exploration Done Optimally](https://mlsanity.com/paper/2111.03290/) (2021)
- [Indexed Minimum Empirical Divergence for Unimodal Bandits](https://mlsanity.com/paper/2112.01452/) (2021)
- [A General Recipe for the Analysis of Randomized Multi-Armed Bandit Algorithms](https://mlsanity.com/paper/2303.06058/) (2023)

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

- [The Confusing Instance Principle for Online Linear Quadratic Control](https://mlsanity.com/paper/2510.19531/) (2025)
- [Bandits for Efficient Experimentation: Adapting to Control Group, Preferences, and Context Drifts](https://mlsanity.com/paper/2606.09802/) (2026)

## Abstract (arXiv)

The Indexed Minimum Empirical Divergence (IMED) algorithm is a highly effective approach that offers a stronger theoretical guarantee of the asymptotic optimality compared to the Kullback--Leibler Upper Confidence Bound (KL-UCB) algorithm for the multi-armed bandit problem. Additionally, it has been observed to empirically outperform UCB-based algorithms and Thompson Sampling. Despite its effectiveness, the generalization of this algorithm to contextual bandits with linear payoffs has remained elusive. In this paper, we present novel linear versions of the IMED algorithm, which we call the family of LinIMED algorithms. We demonstrate that LinIMED provides a widetildeO(d√T) upper regret bound where d is the dimension of the context and T is the time horizon. Furthermore, extensive empirical studies reveal that LinIMED and its variants outperform widely-used linear bandit algorithms such as LinUCB and Linear Thompson Sampling in some regimes.