#### 論文の概要: An Efficient Pessimistic-Optimistic Algorithm for Constrained Linear Bandits

• arxiv url: http://arxiv.org/abs/2102.05295v1
• Date: Wed, 10 Feb 2021 07:30:37 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-11 14:33:05.156239
• Title: An Efficient Pessimistic-Optimistic Algorithm for Constrained Linear Bandits
• Title（参考訳）: 制約付き線形バンディットに対する効率的な悲観的最適アルゴリズム
• Authors: Xin Liu, Bin Li, Pengyi Shi, Lei Ying
• Abstract要約: 本稿では,一般制約付き線形帯域について考察する。 目的は、各ラウンドにおける一連の制約の対象となる水平線上の累積報酬を最大化することである。 本稿では,この問題に対する悲観的最適化アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 16.103685478563072
• Abstract: 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.
• Abstract（参考訳）: 本稿では,一般制約付き確率線形帯域について考察する。 目的は、各ラウンド$\tau\leq T$における制約の集合の下の水平線上の期待累積報酬を最大化することである。 本論文では,この問題に対する悲観的最適化アルゴリズムを提案する。 まず、アルゴリズムは $\tilde{\cal O}\left(\left(\frac{K^{1.5}}{\delta^2}+d\right)\sqrt{\tau}\right)$ (pseudo) をラウンド $\tau\leq T,$ ここで $K$ は制約数、$d$ は報酬機能空間の次元、$\delta$ はスレーター定数、$\delta$ は任意のラウンド $\tau>\tau' におけるゼロ制約違反、$ $\tau'$ は水平 $T.$ から独立しており、アルゴリズムは計算的に効率的である。 アルゴリズムは最適化における原始双対アプローチに基づいており、2つの成分を含んでいる。 原始成分は、制約のない確率線形帯域(我々のアルゴリズムは線形上信頼境界アルゴリズム(LinUCB)を用いる)に類似している。 双対成分の計算の複雑さは制約の数に依存し、文脈空間、アクション空間、さらには特徴空間のサイズから独立している。 したがって、アルゴリズムの全体的な計算複雑性は、制約のない確率線形帯の線形UBBと類似している。