Asymptotically Optimal Problem-Dependent Bandit Policies for Transfer Learning
Abstract
We study the non-contextual multi-armed bandit problem in a transfer learning setting: before any pulls, the learner is given $N’_k$ i.i.d.\\samples from each source distribution $\\nu’_k$, and the true target distributions $\\nu_k$ lie within a known distance bound $d_k(\\nu_k,\\nu’_k)\\le L_k$. In this framework, we first derive a problem-dependent asymptotic lower bound on cumulative regret that extends the classical Lai–Robbins result to incorporate the transfer parameters $(d_k,L_k,N’_k)$. We then propose \\textsc\{KL-UCB-Transfer\}, a simple index policy that matches this new bound in the Gaussian case. Finally, we validate our approach via simulations, showing that \\textsc\{KL-UCB-Transfer\} significantly outperforms the no-prior baseline when source and target distributions are sufficiently close.
Cite
Text
Prevost et al. "Asymptotically Optimal Problem-Dependent Bandit Policies for Transfer Learning." Proceedings of the 17th Asian Conference on Machine Learning, 2025.Markdown
[Prevost et al. "Asymptotically Optimal Problem-Dependent Bandit Policies for Transfer Learning." Proceedings of the 17th Asian Conference on Machine Learning, 2025.](https://mlanthology.org/acml/2025/prevost2025acml-asymptotically/)BibTeX
@inproceedings{prevost2025acml-asymptotically,
title = {{Asymptotically Optimal Problem-Dependent Bandit Policies for Transfer Learning}},
author = {Prevost, Adrien and Mathieu, Timothée and Maillard, Odalric-Ambrym},
booktitle = {Proceedings of the 17th Asian Conference on Machine Learning},
year = {2025},
pages = {319-334},
volume = {304},
url = {https://mlanthology.org/acml/2025/prevost2025acml-asymptotically/}
}