We present an oracle-efficient relaxation for the adversarial contextual bandits problem, where the contexts are sequentially drawn i.i.d from a known distribution and the cost sequence is chosen by an online adversary. Our algorithm has a regret bound of $O(T^{\frac{2}{3}}(K\log(|\Pi|))^{\frac{1}{3}})$ and makes at most $O(K)$ calls per round to an offline optimization oracle, where $K$ denotes the number of actions, $T$ denotes the number of rounds and $\Pi$ denotes the set of policies. This is the first result to improve the prior best bound of $O((TK)^{\frac{2}{3}}(\log(|\Pi|))^{\frac{1}{3}})$ as obtained by Syrgkanis et al. at NeurIPS 2016, and the first to match the original bound of Langford and Zhang at NeurIPS 2007 which was obtained for the stochastic case.

我们提出了一种对抗情境下上下文弛豫的方法，其中上下文是从已知分布中顺序独立抽取的，并且成本序列由在线对手选择。我们的算法在每一轮最多对离线优化预言机进行O(K)次调用，有一个遗憾界限为O(T^（2/3）(Klog(|Pi|))^（1/3）)，这是首次改进了Syrgkanis等人在2016年NeurIPS会议上获得的 O((TK)^（2/3）(log(|Pi|))^（1/3）) 最佳界限，也是第一次与Langford和Zhang在2007年NeurIPS会议上为随机情况获得的原始界限相匹配。

一种改进的用于Oracle-Efficient Adversarial Contextual Bandits的松弛方法