A Unified Approach to Translate Classical Bandit Algorithms to the Structured Bandit Setting
A Unified Approach to Translate Classical Bandit Algorithms to the Structured Bandit Setting
复制标题
DOI：
10.1109/jsait.2020.3041246
复制
发表时间：
2018-10
期刊：
影响因子：
--
通讯作者：
Samarth Gupta;Shreyas Chaudhari;Subhojyoti Mukherjee;Gauri Joshi;Osman Yaugan
中科院分区：
文献类型：
--
作者：
Samarth Gupta;Shreyas Chaudhari;Subhojyoti Mukherjee;Gauri Joshi;Osman Yaugan
我们考虑一个有限臂的结构化强盗问题，其中不同的武器的平均回报是一个共同的隐藏参数$\theta ^{*}$的函数。由于我们对这些函数没有任何限制，因此问题设置包含了几个先前研究的框架，这些框架假设线性或可逆的奖励函数。我们提出了一种新的方法来逐步估计隐藏的$\theta ^{*}$，并使用估计与平均奖励函数，大大减少探索次优武器。这种方法使我们能够从根本上概括任何经典的强盗算法，包括UCB和汤普森采样的结构化强盗设置。我们通过遗憾分析证明，我们提出的UCB-C算法（UCB的结构化强盗版本）只拉一个子集的次优武器$\mathrm {O}（\log T）$次，而其他次优武器（称为非竞争武器）被拉O（1）次。因此，在所有次优武器都是非竞争性的情况下，这可能发生在许多实际情况下，所提出的算法实现了有限的遗憾。我们还进行模拟MOVIELENS建议数据集上，以证明所提出的算法比现有的结构化强盗算法的改进。
We consider a finite-armed structured bandit problem in which mean rewards of different arms are known functions of a common hidden parameter $\theta ^{*}$ . Since we do not place any restrictions on these functions, the problem setting subsumes several previously studied frameworks that assume linear or invertible reward functions. We propose a novel approach to gradually estimate the hidden $\theta ^{*}$ 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 classical bandit algorithm including UCB and Thompson Sampling to the structured bandit setting. We prove via regret analysis that our proposed UCB-C algorithm (structured bandit versions of UCB) pulls only a subset of the sub-optimal arms $\mathrm {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 non-competitive, which can happen in many practical scenarios, the proposed algorithm achieves bounded regret. We also conduct simulations on the MOVIELENS recommendations dataset to demonstrate the improvement of the proposed algorithms over existing structured bandit algorithms.