Linear Contextual Bandits with Adversarial Corruptions
Linear Contextual Bandits with Adversarial Corruptions
复制标题
具有对抗性腐败的线性上下文强盗
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Quanquan Gu
中科院分区：
文献类型：
--
作者：
Heyang Zhao;Dongruo Zhou;Quanquan Gu
我们研究存在对抗性腐败的线性上下文强盗问题，其中玩家和可能无限的决策集之间的交互受到对手的污染，该对手可以将奖励破坏到腐败水平 $C$，该腐败水平由每轮奖励的最大变化之和来衡量。我们提出了一种方差感知算法，可适应对抗性污染 $C$ 的水平。关键算法设计包括（1）观察数据的多级划分方案，（2）适应损坏级别的级联置信集，以及（3）可以利用低方差奖励的方差感知置信集构造。我们进一步证明该算法的遗憾为$ilde{O}(C^2dsqrt{sum_{t = 1}^T sigma_t^2} + C^2Rsqrt{dT})$，其中$d$是上下文向量的维度，$T$是轮数，$R$是噪声范围，$sigma_t^2,t=1ldots,T$是瞬时方差奖励。我们还证明了所提出的算法的间隙依赖后悔界限，该算法依赖于实例，因此可以在良好的实际实例上获得更好的性能。据我们所知，这是第一个针对上下文强盗的方差感知腐败鲁棒算法。合成数据的实验证实了我们的理论。
We study the linear contextual bandit problem in the presence of adversarial corruption, where the interaction between the player and a possibly infinite decision set is contaminated by an adversary that can corrupt the reward up to a corruption level $C$ measured by the sum of the largest alteration on rewards in each round. We present a variance-aware algorithm that is adaptive to the level of adversarial contamination $C$. The key algorithmic design includes (1) a multi-level partition scheme of the observed data, (2) a cascade of confidence sets that are adaptive to the level of the corruption, and (3) a variance-aware confidence set construction that can take advantage of low-variance reward. We further prove that the regret of the proposed algorithm is $ ilde{O}(C^2dsqrt{sum_{t = 1}^T sigma_t^2} + C^2Rsqrt{dT})$, where $d$ is the dimension of context vectors, $T$ is the number of rounds, $R$ is the range of noise and $sigma_t^2,t=1ldots,T$ are the variances of instantaneous reward. We also prove a gap-dependent regret bound for the proposed algorithm, which is instance-dependent and thus leads to better performance on good practical instances. To the best of our knowledge, this is the first variance-aware corruption-robust algorithm for contextual bandits. Experiments on synthetic data corroborate our theory.