論文の概要: An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction
- arxiv url: http://arxiv.org/abs/2508.11931v1
- Date: Sat, 16 Aug 2025 06:25:18 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-19 14:49:10.461225
- Title: An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction
- Title（参考訳）: 逆線形帯域の削減による改善アルゴリズム
- Authors: Tim van Erven, Jack Mayo, Julia Olkhovskaya, Chen-Yu Wei,
- Abstract要約: 逆損失とアクションセットを持つ線形文脈帯域に対する効率的なアルゴリズムを提案する。
我々のアルゴリズムは、まず最初に$text(d)sqrtT$後悔を達成するが、事前のアルゴリズムが我々の知識に間に合うように$o(T)$後悔することはない。
- 参考スコア（独自算出の注目度）: 13.78877509090251
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present an efficient algorithm for linear contextual bandits with adversarial losses and stochastic action sets. Our approach reduces this setting to misspecification-robust adversarial linear bandits with fixed action sets. Without knowledge of the context distribution or access to a context simulator, the algorithm achieves $\tilde{O}(\min\{d^2\sqrt{T}, \sqrt{d^3T\log K}\})$ regret and runs in $\text{poly}(d,C,T)$ time, where $d$ is the feature dimension, $C$ is an upper bound on the number of linear constraints defining the action set in each round, $K$ is an upper bound on the number of actions in each round, and $T$ is number of rounds. This resolves the open question by Liu et al. (2023) on whether one can obtain $\text{poly}(d)\sqrt{T}$ regret in polynomial time independent of the number of actions. For the important class of combinatorial bandits with adversarial losses and stochastic action sets where the action sets can be described by a polynomial number of linear constraints, our algorithm is the first to achieve $\text{poly}(d)\sqrt{T}$ regret in polynomial time, while no prior algorithm achieves even $o(T)$ regret in polynomial time to our knowledge. When a simulator is available, the regret bound can be improved to $\tilde{O}(d\sqrt{L^\star})$, where $L^\star$ is the cumulative loss of the best policy.
- Abstract（参考訳）: 本稿では,対向的損失と確率的作用セットを有する線形文脈帯域に対する効率的なアルゴリズムを提案する。
提案手法は, この設定を, 固定された作用集合を持つ逆線形帯域の誤特定に還元する。
文脈分布や文脈シミュレータへのアクセスの知識がなければ、アルゴリズムは $\tilde{O}(\min\{d^2\sqrt{T}, \sqrt{d^3T\log K}\})$ regret and run in $\text{poly}(d,C,T)$ time, where $d$ is the feature dimension, $C$ is a upper bound on the number of linear constraints defined the action set in each round, $K$ is a upper bound on the actions on each rounds, $T$ is number of rounds。
これは、Liu et al (2023) によるオープンな質問を解決し、アクションの数に依存しない多項式時間で $\text{poly}(d)\sqrt{T}$ の後悔が得られるかどうかを論じる。
線形制約の多項式数で作用集合を記述できる対角的損失と確率的作用集合を持つ組合せ的包帯の重要なクラスに対して、我々のアルゴリズムは多項式時間で$\text{poly}(d)\sqrt{T}$後悔を達成する最初のアルゴリズムであり、事前のアルゴリズムは多項式時間で$o(T)$後悔することができない。
シミュレータが利用可能であれば、後悔のバウンダリを$\tilde{O}(d\sqrt{L^\star})$に改善することができる。
関連論文リスト
- Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
$Phi$-equilibriaは、オンライン学習とゲーム理論の中心にある、強力で柔軟なフレームワークだ。
効率的なオンラインアルゴリズムは、$textpoly(d, k)/epsilon2$ラウンドを使用して、平均$Phi$-regretを最大$epsilon$で生成することを示す。
また、オンライン設定において、ほぼ一致した下限を示し、その結果、$Phi$-regretの学習可能性を取得する偏差の族が初めて得られる。
論文 参考訳（メタデータ） (2025-02-25T19:08:26Z) - Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。
我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
論文 参考訳（メタデータ） (2023-12-24T08:27:30Z) - Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual
Bandits [30.337826346496385]
本稿では、損失ベクトルを全対角に選択し、ラウンドごとのアクションセットを固定分布から引き出す対角線形境界帯域問題について考察する。
この問題の既存の方法は、自由な文脈を生成するためにシミュレータへのアクセスを必要とするか、準最適後悔を達成するか、あるいは計算的に非効率である。
シミュレーションを使わずに$widetildeO(sqrtT)$を後悔して、各ラウンドで設定したアクションが小さい場合に計算効率を維持することで、これらの結果を大幅に改善する。
論文 参考訳（メタデータ） (2023-09-02T03:49:05Z) - 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) - 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) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。