Stochastic Bandits with Linear Constraints
Stochastic Bandits with Linear Constraints
复制标题
DOI：
--
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Aldo Pacchiano;M. Ghavamzadeh;P. Bartlett;Heinrich Jiang
中科院分区：
文献类型：
--
作者：
Aldo Pacchiano;M. Ghavamzadeh;P. Bartlett;Heinrich Jiang
我们研究了一个受约束的上下文线性盗贼环境，其中代理人的目标是产生一系列策略，这些策略在$T$轮次过程中的期望累积回报是最大的，并且每个策略的期望成本都低于某个阈值$\tau$。我们提出了一个求解该问题的置信度上界算法，称为乐观悲观线性盗贼算法，并证明了其$T轮遗憾的$\widetilde{\mathcal{O}}(\frac{d\sqrt{T}}{\tau-c_0})$界，其中分母是约束阈值与已知可行行动的代价之差。我们进一步将我们的结果专门化到多武装强盗身上，并提出了一种针对这种设置的计算高效的算法。我们证明了该算法在$K$-武装土匪中的一个遗憾界，这是对我们简单地将多个武装土匪作为上下文线性土匪的一个实例并利用OPLB的遗憾界得到的改进。我们还证明了本文所研究问题的一个下界，并通过仿真验证了我们的理论结果。
We study a constrained contextual linear bandit setting, where the goal of the agent is to produce a sequence of policies, whose expected cumulative reward over the course of $T$ rounds is maximum, and each has an expected cost below a certain threshold $\tau$. We propose an upper-confidence bound algorithm for this problem, called optimistic pessimistic linear bandit (OPLB), and prove an $\widetilde{\mathcal{O}}(\frac{d\sqrt{T}}{\tau-c_0})$ bound on its $T$-round regret, where the denominator is the difference between the constraint threshold and the cost of a known feasible action. We further specialize our results to multi-armed bandits and propose a computationally efficient algorithm for this setting. We prove a regret bound of $\widetilde{\mathcal{O}}(\frac{\sqrt{KT}}{\tau - c_0})$ for this algorithm in $K$-armed bandits, which is a $\sqrt{K}$ improvement over the regret bound we obtain by simply casting multi-armed bandits as an instance of contextual linear bandits and using the regret bound of OPLB. We also prove a lower-bound for the problem studied in the paper and provide simulations to validate our theoretical results.