An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints
An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints
复制标题
DOI：
--
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Xin Liu;Bin Li;P. Shi;Lei Ying
中科院分区：
文献类型：
--
作者：
Xin Liu;Bin Li;P. Shi;Lei Ying
本文考虑了一般非线性约束下的随机线性土匪问题。我们的目标是最大限度地提高预期的累积回报超过地平线$T$的约束条件下，在每一轮$\tau\leq T$。我们提出了一个悲观-乐观算法，这是有效的，在两个方面。首先，该算法产生$\tilde{\cal O}\left（\left（\frac{K^{0.75}}{\delta}+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 nonlinear 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^{0.75}}{\delta}+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, but is independent of the sizes of the contextual space, the action space, and the feature space. Thus, the overall computational complexity of our algorithm is similar to that of the linear UCB for unconstrained stochastic linear bandits.