論文の概要: An Improved Relaxation for Oracle-Efficient Adversarial Contextual Bandits

• arxiv url: http://arxiv.org/abs/2310.19025v2
• Date: Fri, 10 Nov 2023 16:14:10 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-13 17:26:48.145351
• Title: An Improved Relaxation for Oracle-Efficient Adversarial Contextual Bandits
• Title（参考訳）: oracle によるコンテクスト・バンディットのリラクゼーション改善
• Authors: Kiarash Banihashem, MohammadTaghi Hajiaghayi, Suho Shin, Max Springer
• Abstract要約: 対向的な文脈的包帯問題に対するオラクル効率の緩和法を提案する。 我々のアルゴリズムは、$O(Tfrac23(Klog(|Pi|))frac13)$という残念なバウンダリを持ち、1ラウンド当たりのO(K)$コールをオフラインで最適化する。
• 参考スコア（独自算出の注目度）: 14.058574632553547
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present an oracle-efficient relaxation for the adversarial contextual bandits problem, where the contexts are sequentially drawn i.i.d from a known distribution and the cost sequence is chosen by an online adversary. Our algorithm has a regret bound of $O(T^{\frac{2}{3}}(K\log(|\Pi|))^{\frac{1}{3}})$ and makes at most $O(K)$ calls per round to an offline optimization oracle, where $K$ denotes the number of actions, $T$ denotes the number of rounds and $\Pi$ denotes the set of policies. This is the first result to improve the prior best bound of $O((TK)^{\frac{2}{3}}(\log(|\Pi|))^{\frac{1}{3}})$ as obtained by Syrgkanis et al. at NeurIPS 2016, and the first to match the original bound of Langford and Zhang at NeurIPS 2007 which was obtained for the stochastic case.
• Abstract（参考訳）: 我々は,既知の分布から文脈が順次引き起こされ,コストシーケンスがオンラインの敵によって選択される,敵対的文脈的バンディット問題に対するoracleの効率的な緩和を提案する。 我々のアルゴリズムは、$O(T^{\frac{2}{3}}(K\log(|\Pi|))^{\frac{1}{3}})$の後悔のバウンダリを持ち、少なくとも$O(K)$コールをオフラインの最適化オラクルに呼び出し、$K$はアクションの数を表し、$T$はラウンドの数を表し、$\Pi$はポリシーの集合を示す。 これは、NeurIPS 2016 で Syrgkanis et al. によって得られたような$O((TK)^{\frac{2}{3}}(\log(|\Pi|))^{\frac{1}{3}})$ の事前の最高境界を改善する最初の結果であり、NeurIPS 2007 で得られるラングフォードと張の元の境界と一致する最初の結果である。

関連論文リスト

• Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
  両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。 我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
  論文  参考訳（メタデータ） (2023-12-24T08:27:30Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• 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)
• First- and Second-Order Bounds for Adversarial Linear Contextual Bandits [22.367921675238318]
  我々は,K$の腕に付随する損失関数を制限なく時間とともに変化させることができる,逆線形文脈帯域設定を考える。 V_T$ または $L_T*$ は$T$ よりもかなり小さい可能性があるため、環境が比較的良心的であれば、最悪の場合の後悔よりも改善される。
  論文  参考訳（メタデータ） (2023-05-01T14:00:15Z)
• Towards Painless Policy Optimization for Constrained MDPs [46.12526917024248]
  我々は、無限の地平線における政策最適化、$gamma$-discounted constrained Markov decision process (CMDP)について研究する。 我々の目標は、小さな制約違反で大きな期待された報酬を達成する政策を返却することである。 本稿では,任意のアルゴリズムに対して,報酬の準最適性と制約違反を拘束できる汎用的原始双対フレームワークを提案する。
  論文  参考訳（メタデータ） (2022-04-11T15:08:09Z)
• 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)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
  私たちは発見するアルゴリズムを見つけます。 epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using $(epsilon,gamma)$surimateランダムランダムポイント。 ここでの私たちの下限は、ノイズのないケースでも新規です。
  論文  参考訳（メタデータ） (2020-06-24T04:41:43Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)
• Efficient and Robust Algorithms for Adversarial Linear Contextual Bandits [13.32560004325655]
  古典的な$K$武器の線形文脈包帯問題の逆変法を考える。 $d$-dimensionalコンテキストがランダムに生成されるという仮定の下で、古典的なExp3アルゴリズムに基づいて効率的なアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2020-02-01T22:49:46Z)

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

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