論文の概要: 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
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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と類似している。
関連論文リスト
- Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。
我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
論文 参考訳（メタデータ） (2023-12-24T08:27:30Z) - Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback [30.337826346496385]
線形マルコフ決定過程におけるオンライン強化学習について,敵対的損失と帯域幅フィードバックを用いて検討した。
既存の手法と比較して、後悔性能を向上させるアルゴリズムを2つ導入する。
論文 参考訳（メタデータ） (2023-10-17T19:43:37Z) - Projection-free Online Exp-concave Optimization [21.30065439295409]
LOOをベースとしたONSスタイルのアルゴリズムを提案する。これは全体$O(T)$コールを使用して,$widetildeO(n2/3T2/3)$でバウンドされた最悪のケースを保証します。
我々のアルゴリズムは、重要かつ確実な低次元データシナリオにおいて最も興味深い。
論文 参考訳（メタデータ） (2023-02-09T18:58:05Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Computationally Efficient Horizon-Free Reinforcement Learning for Linear
Mixture MDPs [111.75736569611159]
線形混合MDPのための計算効率のよい初めての地平線フリーアルゴリズムを提案する。
我々のアルゴリズムは、未知の遷移力学に対する重み付き最小二乗推定器に適応する。
これにより、$sigma_k2$'sが知られているときに、この設定で最もよく知られたアルゴリズムも改善される。
論文 参考訳（メタデータ） (2022-05-23T17:59:18Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Gradient-Variation Bound for Online Convex Optimization with Constraints [25.002868073267464]
複数の機能的制約とユークリッド球のような比較的単純な制約セットからなる制約を持つオンライン凸最適化について検討する。
一階法は、$mathcalO(sqrtT)$ regret と $mathcalO(1)$ 制約違反を達成するが、問題の構造的情報を考慮してはならない。
本稿では,新しいオンライン原始双対ミラー-プロキシアルゴリズムによって得られる複雑な制約を伴って,オンライン凸最適化のインセンタンス依存バウンダリを提供する。
論文 参考訳（メタデータ） (2020-06-22T17:38:14Z) - Statistically Efficient, Polynomial Time Algorithms for Combinatorial
Semi Bandits [3.9919781077062497]
アームの集合である$cal X の部分集合 0,1d$ 上の半帯域を考える。
この問題に対して、ESCB アルゴリズムは最小の既約値 $R(T) = cal OBig(d (ln m)2 (ln T) over Delta_min Big)$ を生成するが、計算複雑性 $cal O(|cal X|)$ を持つ。
論文 参考訳（メタデータ） (2020-02-17T21:32:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。