論文の概要: First- and Second-Order Bounds for Adversarial Linear Contextual Bandits

• arxiv url: http://arxiv.org/abs/2305.00832v3
• Date: Wed, 24 May 2023 12:27:03 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-25 11:11:44.200380
• Title: First- and Second-Order Bounds for Adversarial Linear Contextual Bandits
• Title（参考訳）: 逆線形帯域に対する1次および2次境界
• Authors: Julia Olkhovskaya, Jack Mayo, Tim van Erven, Gergely Neu and Chen-Yu Wei
• Abstract要約: 我々は,K$の腕に付随する損失関数を制限なく時間とともに変化させることができる,逆線形文脈帯域設定を考える。 V_T$ または $L_T*$ は$T$ よりもかなり小さい可能性があるため、環境が比較的良心的であれば、最悪の場合の後悔よりも改善される。
• 参考スコア（独自算出の注目度）: 22.367921675238318
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the adversarial linear contextual bandit setting, which allows for the loss functions associated with each of $K$ arms to change over time without restriction. Assuming the $d$-dimensional contexts are drawn from a fixed known distribution, the worst-case expected regret over the course of $T$ rounds is known to scale as $\tilde O(\sqrt{Kd T})$. Under the additional assumption that the density of the contexts is log-concave, we obtain a second-order bound of order $\tilde O(K\sqrt{d V_T})$ in terms of the cumulative second moment of the learner's losses $V_T$, and a closely related first-order bound of order $\tilde O(K\sqrt{d L_T^*})$ in terms of the cumulative loss of the best policy $L_T^*$. Since $V_T$ or $L_T^*$ may be significantly smaller than $T$, these improve over the worst-case regret whenever the environment is relatively benign. Our results are obtained using a truncated version of the continuous exponential weights algorithm over the probability simplex, which we analyse by exploiting a novel connection to the linear bandit setting without contexts.
• Abstract（参考訳）: 我々は,K$の腕に付随する損失関数を制限なく時間とともに変化させることができる,逆線形文脈帯域設定を考える。 固定された既知分布から$d$次元の文脈が引き出されると仮定すると、$T$ラウンドにおける最悪の後悔は$\tilde O(\sqrt{Kd T})$としてスケールすることが知られている。 文脈の密度がlog-concaveであるという追加の仮定の下で、学習者の損失の累積的第2モーメント(v_t$)の項で、次数$\tilde o(k\sqrt{d v_t}) と次数$\tilde o(k\sqrt{d l_t^*}) と密接に関連する次数$\tilde o(k\sqrt{d l_t^*})$ を得る。 v_t$ や $l_t^*$ は$t$ よりもかなり小さいため、環境が比較的良質な場合の最悪の後悔よりも改善される。 本研究は,連続指数重みアルゴリズムの確率的単純性に対する縮小版を用いて,文脈を伴わない線形バンディット設定への新たな接続を活用し,解析を行った。

関連論文リスト

• Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
  両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。 我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
  論文  参考訳（メタデータ） (2023-12-24T08:27:30Z)
• Context-lumpable stochastic bandits [49.024050919419366]
  我々は、$S$コンテキストと$K$アクションによる文脈的盗賊問題を考える。 我々は,最大$widetilde O(r (S +K )/epsilon2)$サンプルを用いて,$epsilon$-optimal Policyを出力するアルゴリズムを提案する。 後悔の設定では、T$までの累積後悔を$widetilde O(sqrtr3(S+K)T)$で束縛するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2023-06-22T17:20:30Z)
• Variance-Aware Sparse Linear Bandits [64.70681598741417]
  余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。 ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。 我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
  論文  参考訳（メタデータ） (2022-05-26T15:55:44Z)
• 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)
• Minimal Expected Regret in Linear Quadratic Control [79.81807680370677]
  オンライン学習アルゴリズムを考案し、その期待された後悔を保証します。 当時のこの後悔は、$A$と$B$が未知の場合、$widetildeO((d_u+d_x)sqrtd_xT)$によって上界(i)となる。
  論文  参考訳（メタデータ） (2021-09-29T14:07:21Z)
• Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
  我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。 いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。 文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
  論文  参考訳（メタデータ） (2020-07-07T09:00:57Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Nearly Optimal Regret for Stochastic Linear Bandits with Heavy-Tailed Payoffs [35.988644745703645]
  我々は、リニアバンディットをヘビーテールのペイオフで分析し、そこではペイオフは1+epsilon$のモーメントしか持たない。 本稿では,$widetildeO(dfrac12Tfrac11+epsilon)$のサブ線形後悔境界を満足する2つの新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-28T13:01:38Z)
• Efficient and Robust Algorithms for Adversarial Linear Contextual Bandits [13.32560004325655]
  古典的な$K$武器の線形文脈包帯問題の逆変法を考える。 $d$-dimensionalコンテキストがランダムに生成されるという仮定の下で、古典的なExp3アルゴリズムに基づいて効率的なアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2020-02-01T22:49:46Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。