Stage-wise Conservative Linear Bandits
Stage-wise Conservative Linear Bandits
复制标题
DOI：
--
复制
发表时间：
2020-09
期刊：
影响因子：
--
通讯作者：
Ahmadreza Moradipari;Christos Thrampoulidis;M. Alizadeh
中科院分区：
文献类型：
--
作者：
Ahmadreza Moradipari;Christos Thrampoulidis;M. Alizadeh
我们研究了阶段性保守线性随机强盗：强盗优化的一个实例，它考虑了在线广告和医疗试验等应用中出现的（未知）安全约束。在每一个阶段，学习者必须选择的行动不仅要在整个时间范围内最大化累积奖励，而且还要满足线性基线约束，即瞬时奖励的下限。对于这个问题，我们提出了两个新的算法，阶段式保守线性汤普森采样（SCLTS）和阶段式保守线性UCB（SCLUCB），尊重基线约束，并分别享有O（\sqrt{T} \log^{3/2}T）和O（\sqrt{T} \log T）的概率遗憾界。值得注意的是，只需对所提出的算法进行较小的修改即可进行调整，以解决不同的问题变化，例如具有强盗反馈的约束或未知的基线动作序列。我们讨论了这些和其他改进的最先进的。例如，与现有的解决方案相比，我们表明，SCLTS发挥（非最佳）基线动作在最多O（\log{T}）次（相比O（\sqrt{T}））。最后，我们将连接到另一种研究形式的安全约束，其形式为瞬时奖励的上限。虽然这会给学习过程带来额外的复杂性，因为不能保证最佳动作在每一轮都属于安全集，但我们证明了SCLUCB可以通过简单的修改在此设置中进行适当的调整。
We study stage-wise conservative linear stochastic bandits: an instance of bandit optimization, which accounts for (unknown) safety constraints that appear in applications such as online advertising and medical trials. At each stage, the learner must choose actions that not only maximize cumulative reward across the entire time horizon but further satisfy a linear baseline constraint that takes the form of a lower bound on the instantaneous reward. For this problem, we present two novel algorithms, stage-wise conservative linear Thompson Sampling (SCLTS) and stage-wise conservative linear UCB (SCLUCB), that respect the baseline constraints and enjoy probabilistic regret bounds of order O(\sqrt{T} \log^{3/2}T) and O(\sqrt{T} \log T), respectively. Notably, the proposed algorithms can be adjusted with only minor modifications to tackle different problem variations, such as constraints with bandit-feedback, or an unknown sequence of baseline actions. We discuss these and other improvements over the state-of-the-art. For instance, compared to existing solutions, we show that SCLTS plays the (non-optimal) baseline action at most O(\log{T}) times (compared to O(\sqrt{T})). Finally, we make connections to another studied form of safety constraints that takes the form of an upper bound on the instantaneous reward. While this incurs additional complexity to the learning process as the optimal action is not guaranteed to belong to the safe set at each round, we show that SCLUCB can properly adjust in this setting via a simple modification.