An Efficient Pessimistic-Optimistic Algorithm for Constrained Linear Bandits
An Efficient Pessimistic-Optimistic Algorithm for Constrained Linear Bandits
复制标题
一种高效的约束线性强盗悲观-乐观算法
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Lei Ying
中科院分区：
文献类型：
--
作者：
Xin Liu;Bin Li;P. Shi;Lei Ying
本文研究了一般约束下的随机线性强盗问题。我们的目标是最大限度地提高预期的累积回报超过地平线$T$的约束条件下，在每一轮$\tau\leq T$。我们提出了一个悲观-乐观算法，这是有效的，在两个方面。首先，该算法产生$\tilde{\cal O}\left（\left（\frac{K^{1.5}}{\delta^2}+d\right）\sqrt{\tau}\right）$（pseudo）regret in round $\tau\leq T，$其中$K$是约束的数量，$d$是奖励特征空间的维数，$\delta$是斯莱特常数;和零约束违反在任何轮$\tau>\tau '，$其中$\tau'$是独立的地平线$T.$第二，算法计算效率高。我们的算法是基于优化的原始-对偶方法，并包括两个组件。原始分量类似于无约束随机线性强盗（我们的算法使用线性置信上限算法（LinUCB））。对偶分量的计算复杂度取决于约束的数量，并且与上下文空间、动作空间甚至特征空间的大小无关。因此，我们的算法的整体计算复杂度是类似的线性UCB无约束随机线性土匪。
This paper considers stochastic linear bandits with general constraints. The objective is to maximize the expected cumulative reward over horizon $T$ subject to a set of constraints in each round $\tau\leq T$. We propose a pessimistic-optimistic algorithm for this problem, which is efficient in two aspects. First, the algorithm yields $\tilde{\cal O}\left(\left(\frac{K^{1.5}}{\delta^2}+d\right)\sqrt{\tau}\right)$ (pseudo) regret in round $\tau\leq T,$ where $K$ is the number of constraints, $d$ is the dimension of the reward feature space, and $\delta$ is a Slater's constant; and zero constraint violation in any round $\tau>\tau',$ where $\tau'$ is independent of horizon $T.$ Second, the algorithm is computationally efficient. Our algorithm is based on the primal-dual approach in optimization, and includes two components. The primal component is similar to unconstrained stochastic linear bandits (our algorithm uses the linear upper confidence bound algorithm (LinUCB)). The computational complexity of the dual component depends on the number of constraints, and is independent of sizes of the contextual space, the action space, and even the feature space. So the overall computational complexity of our algorithm is similar to the linear UCB for unconstrained stochastic linear bandits.
DOI：
10.1145/3392157
发表时间：
2019-08
期刊：
Proceedings of the ACM on Measurement and Analysis of Computing Systems
影响因子：
--
作者：
Xiaohan Wei;Hao Yu;M. Neely
通讯作者：
Xiaohan Wei;Hao Yu;M. Neely
DOI：
--
发表时间：
2020-06
期刊：
IEICE Trans. Fundam. Electron. Commun. Comput. Sci.
影响因子：
--
作者：
Aldo Pacchiano;M. Ghavamzadeh;P. Bartlett;Heinrich Jiang
通讯作者：
Aldo Pacchiano;M. Ghavamzadeh;P. Bartlett;Heinrich Jiang
影响因子：
3.2
作者：
Harvey, Hanjeong;Habash, Marc;Burrows, Lori L.
通讯作者：
Burrows, Lori L.