Solving Bernoulli Rank-One Bandits with Unimodal Thompson Sampling
This work addresses a gap in bandit algorithms for researchers, providing an optimal solution for a specific problem, though it is incremental as it builds on existing UTS methods.
The paper tackled the regret minimization problem in stochastic rank-one bandits by proving they are an instance of unimodal bandits and analyzing Unimodal Thompson Sampling (UTS), achieving an asymptotically optimal regret bound and showing significant improvement over state-of-the-art methods in simulations.
Stochastic Rank-One Bandits (Katarya et al, (2017a,b)) 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), initially proposed by Paladino et al (2017). 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.