A Unified Approach to Translate Classical Bandit Algorithms to Structured Bandits
Samarth Gupta, Shreyas Chaudhari, Subhojyoti Mukherjee, Gauri Joshi, Osman Yagan
Abstract
We consider a finite-armed structured bandit problem in which mean rewards of different arms are known functions of a common hidden parameter θ <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">*</sup> . This problem setting subsumes several previously studied frameworks that assume linear or invertible reward functions. We propose a novel approach to gradually estimate the hidden θ <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">*</sup> and use the estimate together with the mean reward functions to substantially reduce exploration of sub-optimal arms. This approach enables us to fundamentally generalize any classic bandit algorithm including UCB and Thompson Sampling to the structured bandit setting. We prove via regret analysis that our proposed UCB-C and TS-C algorithms (structured bandit versions of UCB and Thompson Sampling, respectively) pull only a subset of the sub-optimal arms O(log T ) times while the other sub-optimal arms (referred to as non-competitive arms) are pulled O(1) times. As a result, in cases where all sub-optimal arms are noncompetitive, which can happen in many practical scenarios, the proposed algorithms achieve bounded regret.
BibTeX
@inproceedings{icassp2021_aunifiedapproach,
title = {A Unified Approach to Translate Classical Bandit Algorithms to Structured Bandits},
author = {Samarth Gupta and Shreyas Chaudhari and Subhojyoti Mukherjee and Gauri Joshi and Osman Yagan},
booktitle = {ICASSP 2021},
year = {2021}
}