Solving Bernoulli Rank-One Bandits with Unimodal Thompson Sampling
Abstract
Stochastic Rank-One Bandits are a simple framework for regret minimization problems over rank-one matrices of arms. The initially proposed algorithms are proved to have logarithmic regret, but do not match the existing lower bound for this problem. We close this gap by first proving that rank-one bandits are a particular instance of unimodal bandits, and then providing a new analysis of Unimodal Thompson Sampling (UTS). We prove an asymptotically optimal regret bound on the frequentist regret of UTS and we support our claims with simulations showing the significant improvement of our method compared to the state-of-the-art.
Cite
Text
Trinh et al. "Solving Bernoulli Rank-One Bandits with Unimodal Thompson Sampling." Proceedings of the 31st International Conference on Algorithmic Learning Theory, 2020.Markdown
[Trinh et al. "Solving Bernoulli Rank-One Bandits with Unimodal Thompson Sampling." Proceedings of the 31st International Conference on Algorithmic Learning Theory, 2020.](https://mlanthology.org/alt/2020/trinh2020alt-solving/)BibTeX
@inproceedings{trinh2020alt-solving,
title = {{Solving Bernoulli Rank-One Bandits with Unimodal Thompson Sampling}},
author = {Trinh, Cindy and Kaufmann, Emilie and Vernade, Claire and Combes, Richard},
booktitle = {Proceedings of the 31st International Conference on Algorithmic Learning Theory},
year = {2020},
pages = {862-889},
volume = {117},
url = {https://mlanthology.org/alt/2020/trinh2020alt-solving/}
}