# Minimum Empirical Divergence for Sub-Gaussian Linear Bandits

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

## Key facts

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

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

- [Achieving adaptivity and optimality for multi-armed bandits using Exponential-Kullback Leibler Maillard Sampling](https://mlsanity.com/paper/2502.14379/) (2025)
- [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)

We propose a novel linear bandit algorithm called LinMED (Linear Minimum Empirical Divergence), which is a linear extension of the MED algorithm that was originally designed for multi-armed bandits. LinMED is a randomized algorithm that admits a closed-form computation of the arm sampling probabilities, unlike the popular randomized algorithm called linear Thompson sampling. Such a feature proves useful for off-policy evaluation where the unbiased evaluation requires accurately computing the sampling probability. We prove that LinMED enjoys a near-optimal regret bound of d√n up to logarithmic factors where d is the dimension and n is the time horizon. We further show that LinMED enjoys a fracd2Deltaleft(log2(n)right)logleft(log(n)right) problem-dependent regret where Delta is the smallest sub-optimality gap. Our empirical study shows that LinMED has a competitive performance with the state-of-the-art algorithms.