論文の概要: Near-Optimal Regret for Oracle-Efficient Adversarial Contextual Bandits
- arxiv url: http://arxiv.org/abs/2611.17109v1
- Date: Thu, 12 Nov 2026 17:04:36 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-14 01:36:33.563949
- Title: Near-Optimal Regret for Oracle-Efficient Adversarial Contextual Bandits
- Title(参考訳): Oracle-Efficient Adversarial Contextual Bandits の準最適レグレ
- Abstract要約: 我々は、$K$アクション、$N$ポリシーのクラス、すなわち学習者がサンプリングできる分布からコンテキストを学習する。
プレー前に固定された損失関数の任意の列に対して、実現されたコンテキストを考慮に入れた最良のポリシーに対して、期待された後悔の$O(sqrtKTlog (2N),log (2KT)$のオラクル効率のアルゴリズムを与える。
- 参考スコア(独自算出の注目度): 24.0850778188305
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study contextual bandits with $K$ actions, a class of $N$ policies, and i.i.d.\ contexts from a distribution that the learner can sample. For any sequence of loss functions fixed before play, we give an oracle-efficient algorithm with expected regret $O(\sqrt{KT\log(2N)}\,\log(2KT))$ against the best policy in hindsight on the realized contexts. This improves the $T^{2/3}$ dependence on the horizon in prior oracle-efficient bounds and achieves the optimal regret rate in this setting up to logarithmic factors. Our algorithm perturbs policy scores using a Poisson sample of auxiliary contexts. At each sampled context, the perturbation assigned to an action is a Laplace noise draw multiplied by a scale specific to that context and action. We show that choosing these scales to minimize a convex objective determined by past observations yields the stated regret bound. We further approximate the minimizing scales by projected stochastic gradient descent using only an exact offline cost-sensitive optimization oracle that returns the optimum value. Since the table of scales can be large, the algorithm represents the SGD iterates implicitly by storing the random draws that determine each update and evaluates the scales only at queried contexts. Both the oracle complexity and the remaining resource bounds are polynomial in $T$, $K$, and $\log(2N)$.
- Abstract(参考訳): 我々は、学習者がサンプリングできる分布から、$K$アクション、$N$ポリシーのクラス、およびi.d.\コンテキストについて研究する。
プレー前に固定された損失関数の任意の列に対して、期待された後悔$O(\sqrt{KT\log(2N)}\,\log(2KT))$ のオラクル効率のアルゴリズムを、実現された文脈の後での最良のポリシーに対して与える。
これにより、事前のオラクル係数境界における地平線への$T^{2/3}$依存が改善され、対数係数に設定した際の最適な後悔率が得られる。
我々のアルゴリズムは、Poissonの補助的文脈のサンプルを用いてポリシースコアを摂動する。
それぞれのサンプルコンテキストにおいて、アクションに割り当てられた摂動は、そのコンテキストとアクションに特有のスケールに乗じてラプラスノイズドローである。
過去の観測によって決定された凸目標を最小化するためにこれらの尺度を選択すると、記述された後悔の束縛が得られることを示す。
さらに、最適な値を返す正確なオフラインコスト依存性最適化オラクルのみを用いて、確率勾配勾配の投影による最小化スケールを近似する。
スケールのテーブルが大きくなる可能性があるため、アルゴリズムは各更新を決定するランダムなドローを格納し、クエリされたコンテキストでのみスケールを評価することで、SGDを暗黙的に反復する。
オラクル複雑性と残りのリソース境界はともに$T$、$K$、$\log(2N)$の多項式である。
関連論文リスト
- Near-Optimal Regret Bounds for Monotone Stochastic Optimization under Semi-Bandit Feedback [7.234249257243776]
citetagarwal2026semibanditは、半帯域でのモノトン最適化をオンラインからオフラインに還元する。
citetliu2025は問題固有のアルゴリズムを使って$widetilde O(sqrtnT)$を達成する。
論文 参考訳(メタデータ) (2026-10-12T19:21:10Z) - Contextual Slate GLM Bandits with Limited Adaptivity [1.8843687952462742]
適応性に制限のある一般化線形報酬を用いた文脈スレートバンドイット問題について検討する。
Batched と (b) Rarely-Switching という2つの限定適応性設定の下でアルゴリズムを提案する。
我々のアルゴリズムは計算効率が良く、スレートが2(N)$であるにもかかわらず、1ラウンドあたりのtextpoly(N)$時間しか必要としない。
論文 参考訳(メタデータ) (2026-06-30T10:24:37Z) - The Sample Complexity of Multiclass and Sparse Contextual Bandits [106.74652380822778]
我々は,包括的フィードバックに基づいて,与えられたクラスからほぼ最適なポリシーを特定することを目的とする。
ゼロ・ワンの報酬を伴うバンド型マルチクラス分類に動機付けられ、emph$s$-sparse設定に焦点をあてる。
我々は、$s$-sparseの報酬で、誘導モデルクラスは、$s$でスケールするシャープなDEC境界を認め、直接最適なレートを得ることを示す。
論文 参考訳(メタデータ) (2026-05-28T09:12:20Z) - A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳(メタデータ) (2024-09-07T06:37:23Z) - Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits [12.674929126684528]
我々は、プレイヤーがPアクションの中から d 個の基本アイテムを含む集合のパワーセットから選択する半帯域の問題に対処する。
提案手法は半帯域フィードバックを効果的に活用し,帯域フィードバックアプローチより優れていることを示す。
論文 参考訳(メタデータ) (2024-02-23T08:07:54Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳(メタデータ) (2024-02-14T07:52:00Z) - Oblivious Stochastic Composite Optimization [47.48197617884748]
我々のアルゴリズムは問題のパラメータに関する事前の知識なしで収束することを示す。
3つのアルゴリズムは全て、実現可能な集合の直径、リプシッツ定数、あるいは目的関数の滑らかさについて事前の知識なしに機能する。
我々は,フレームワークを比較的大規模に拡張し,大規模半確定プログラム上での手法の効率性と堅牢性を実証する。
論文 参考訳(メタデータ) (2023-06-30T08:34:29Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳(メタデータ) (2022-08-11T04:12:50Z) - Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free
Reinforcement Learning [52.76230802067506]
漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。
提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。
初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
論文 参考訳(メタデータ) (2021-10-09T21:13:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。