Minimum Empirical Divergence for Sub-Gaussian Linear Bandits

Kapilan Balagopalan, Kwang-Sung Jun
Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, PMLR 258:1585-1593, 2025.

Abstract

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\sqrt{n}$ up to logarithmic factors where $d$ is the dimension and $n$ is the time horizon. We further show that LinMED enjoys a $\frac{d^2}{\Delta}\left(\log^2(n)\right)\log\left(\log(n)\right)$ problem-dependent regret where $\Delta$ is the smallest suboptimality gap. Our empirical study shows that LinMED has a competitive performance with the state-of-the-art algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v258-balagopalan25a, title = {Minimum Empirical Divergence for Sub-Gaussian Linear Bandits}, author = {Balagopalan, Kapilan and Jun, Kwang-Sung}, booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics}, pages = {1585--1593}, year = {2025}, editor = {Li, Yingzhen and Mandt, Stephan and Agrawal, Shipra and Khan, Emtiyaz}, volume = {258}, series = {Proceedings of Machine Learning Research}, month = {03--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v258/main/assets/balagopalan25a/balagopalan25a.pdf}, url = {https://proceedings.mlr.press/v258/balagopalan25a.html}, abstract = {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\sqrt{n}$ up to logarithmic factors where $d$ is the dimension and $n$ is the time horizon. We further show that LinMED enjoys a $\frac{d^2}{\Delta}\left(\log^2(n)\right)\log\left(\log(n)\right)$ problem-dependent regret where $\Delta$ is the smallest suboptimality gap. Our empirical study shows that LinMED has a competitive performance with the state-of-the-art algorithms.} }
Endnote
%0 Conference Paper %T Minimum Empirical Divergence for Sub-Gaussian Linear Bandits %A Kapilan Balagopalan %A Kwang-Sung Jun %B Proceedings of The 28th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2025 %E Yingzhen Li %E Stephan Mandt %E Shipra Agrawal %E Emtiyaz Khan %F pmlr-v258-balagopalan25a %I PMLR %P 1585--1593 %U https://proceedings.mlr.press/v258/balagopalan25a.html %V 258 %X 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\sqrt{n}$ up to logarithmic factors where $d$ is the dimension and $n$ is the time horizon. We further show that LinMED enjoys a $\frac{d^2}{\Delta}\left(\log^2(n)\right)\log\left(\log(n)\right)$ problem-dependent regret where $\Delta$ is the smallest suboptimality gap. Our empirical study shows that LinMED has a competitive performance with the state-of-the-art algorithms.
APA
Balagopalan, K. & Jun, K.. (2025). Minimum Empirical Divergence for Sub-Gaussian Linear Bandits. Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 258:1585-1593 Available from https://proceedings.mlr.press/v258/balagopalan25a.html.

Related Material