No Regrets for Learning the Prior in Bandits
This work addresses the challenge of learning task priors in bandit settings, which is incremental as it builds on existing Thompson sampling methods by adding adaptation capabilities.
The paper tackles the problem of adapting to unknown task prior distributions in bandit problems by proposing AdaTS, a Thompson sampling algorithm that marginalizes out uncertainty over prior parameters, resulting in improved performance with small Bayes regret loss as shown in experiments.
We propose ${\tt AdaTS}$, a Thompson sampling algorithm that adapts sequentially to bandit tasks that it interacts with. The key idea in ${\tt AdaTS}$ is to adapt to an unknown task prior distribution by maintaining a distribution over its parameters. When solving a bandit task, that uncertainty is marginalized out and properly accounted for. ${\tt AdaTS}$ is a fully-Bayesian algorithm that can be implemented efficiently in several classes of bandit problems. We derive upper bounds on its Bayes regret that quantify the loss due to not knowing the task prior, and show that it is small. Our theory is supported by experiments, where ${\tt AdaTS}$ outperforms prior algorithms and works well even in challenging real-world problems.