論文の概要: Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback

• arxiv url: http://arxiv.org/abs/2510.09127v1
• Date: Fri, 10 Oct 2025 08:28:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-14 00:38:48.487777
• Title: Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback
• Title（参考訳）: 一般関数近似と遅延フィードバックを用いた逆コンテキスト帯域のレグレト境界
• Authors: Orin Levy, Liad Erez, Alon Cohen, Yishay Mansour,
• Abstract要約: 我々は,コンテキスト型マルチアーム・バンディット(CMAB)問題に対する後悔のアルゴリズムをK$アクションに対して提示する。 我々は、$ O (sqrtKT log |Pi| + sqrtD log |Pi|) $ の最適再帰境界を確立し、$D$ は遅延の和である。
• 参考スコア（独自算出の注目度）: 43.017740308285845
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present regret minimization algorithms for the contextual multi-armed bandit (CMAB) problem over $K$ actions in the presence of delayed feedback, a scenario where loss observations arrive with delays chosen by an adversary. As a preliminary result, assuming direct access to a finite policy class $\Pi$ we establish an optimal expected regret bound of $ O (\sqrt{KT \log |\Pi|} + \sqrt{D \log |\Pi|)} $ where $D$ is the sum of delays. For our main contribution, we study the general function approximation setting over a (possibly infinite) contextual loss function class $ \mathcal{F} $ with access to an online least-square regression oracle $\mathcal{O}$ over $\mathcal{F}$. In this setting, we achieve an expected regret bound of $O(\sqrt{KT\mathcal{R}_T(\mathcal{O})} + \sqrt{ d_{\max} D \beta})$ assuming FIFO order, where $d_{\max}$ is the maximal delay, $\mathcal{R}_T(\mathcal{O})$ is an upper bound on the oracle's regret and $\beta$ is a stability parameter associated with the oracle. We complement this general result by presenting a novel stability analysis of a Hedge-based version of Vovk's aggregating forecaster as an oracle implementation for least-square regression over a finite function class $\mathcal{F}$ and show that its stability parameter $\beta$ is bounded by $\log |\mathcal{F}|$, resulting in an expected regret bound of $O(\sqrt{KT \log |\mathcal{F}|} + \sqrt{d_{\max} D \log |\mathcal{F}|})$ which is a $\sqrt{d_{\max}}$ factor away from the lower bound of $\Omega(\sqrt{KT \log |\mathcal{F}|} + \sqrt{D \log |\mathcal{F}|})$ that we also present.
• Abstract（参考訳）: 提案手法では, 遅延フィードバックが存在する場合, 文脈的マルチアームバンディット(CMAB)問題に対する後悔の最小化アルゴリズムを, 相手が選択した遅延を伴って損失観測を行うシナリオとして提示する。 予備的な結果として、有限ポリシークラス $\Pi$ への直接アクセスを仮定すると、$ O (\sqrt{KT \log |\Pi|} + \sqrt{D \log |\Pi|)} $ の最適再帰境界を定め、$D$ は遅延の和である。 主な貢献として、オンライン最小二乗回帰オアクル $\mathcal{O}$ over $\mathcal{F}$ にアクセスできるような(おそらく無限の)文脈損失関数クラス $ \mathcal{F} $ 上の一般関数近似について検討する。 この設定では、期待される後悔境界である$O(\sqrt{KT\mathcal{R}_T(\mathcal{O})} + \sqrt{d_{\max} D \beta})$ FIFO 順序を仮定すると、$d_{\max}$ は最大遅延、$\mathcal{R}_T(\mathcal{O})$ はオラクルの後悔の上限、$\beta$ はオラクルの後悔の上限であり、$\beta$ はオラクルに関連する安定性パラメータである。 この一般的な結果は、有限関数類 $\mathcal{F}$ 上の最小二乗回帰のオラクル実装として、Vovkの凝集予測器のヘッジベースバージョンの新しい安定性解析を提示し、その安定性パラメータ $\beta$ が $\log |\mathcal{F}|$ で有界であることを示し、その結果、期待される後悔境界は $O(\sqrt{KT \log |\mathcal{F}|} + \sqrt{d_{\max} D \log |\mathcal{F}|})$ である。

関連論文リスト

• Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs [54.28273395444243]
  我々は,モノトニック値 Omega (MVP) アルゴリズムが,差分を考慮した差分依存残差境界を$tildeOleft(left(sum_Delta_h(s,a)>0 fracH2 log K land MathttVar_maxtextc$。
  論文  参考訳（メタデータ） (2025-06-06T20:33:57Z)
• An Information-Theoretic Analysis of Thompson Sampling for Logistic Bandits [36.37704574907495]
  本稿では,ロジスティックバンディット問題に対するトンプソンサンプリングアルゴリズムの性能について検討する。 我々は、$O(d/alphaqrtT log(beta T/d))$ of regret incurred after $T$ expected of Smpling steps.
  論文  参考訳（メタデータ） (2024-12-03T21:55:41Z)
• Eluder-based Regret for Stochastic Contextual MDPs [43.19667415823089]
  文脈マルコフ決定過程(CMDP)における後悔最小化のためのE-UC$3$RLアルゴリズムを提案する。 我々のアルゴリズムは効率的であり(効率的なオフライン回帰オラクルを仮定すると)、$ widetildeO(H3 sqrtT |S| |A|d_mathrmE(mathcalP)$の後悔の保証を享受する。
  論文  参考訳（メタデータ） (2022-11-27T20:38:47Z)
• Optimism in Face of a Context: Regret Guarantees for Stochastic Contextual MDP [46.86114958340962]
  我々は,最小到達可能性仮定の下での文脈的MDPに対する後悔のアルゴリズムを提案する。 我々のアプローチは、一般関数近似を用いた文脈的MDPに適用された最初の楽観的アプローチである。
  論文  参考訳（メタデータ） (2022-07-22T15:00:15Z)
• A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedback [25.68113242132723]
  本稿では,Zimmert と Seldin [2020] のアルゴリズムを,フィードバックの遅れによる逆方向の多重武装バンディットに対して修正したチューニングを行う。 我々は,時間的遅れのある設定において,ほぼ最適の相反的後悔の保証を同時に達成する。 また,任意の遅延の場合に対するアルゴリズムの拡張も提案する。
  論文  参考訳（メタデータ） (2022-06-29T20:49:45Z)
• On Submodular Contextual Bandits [92.45432756301231]
  作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。 Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
  論文  参考訳（メタデータ） (2021-12-03T21:42:33Z)
• Scale-Free Adversarial Multi-Armed Bandit with Arbitrary Feedback Delays [21.94728545221709]
  制限のないフィードバック遅延を伴うMAB(Scale-Free Adversarial Multi Armed Bandit)問題を考える。 textttSFBankerは$mathcal O(sqrtK(D+T)L)cdot rm polylog(T, L)$ total regret, where $T$ is the total number of steps, $D$ is the total feedback delay。
  論文  参考訳（メタデータ） (2021-10-26T04:06:51Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
  論文  参考訳（メタデータ） (2020-06-16T13:01:33Z)

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

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