論文の概要: Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback

• arxiv url: http://arxiv.org/abs/2505.24193v1
• Date: Fri, 30 May 2025 04:05:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-02 19:47:52.762307
• Title: Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback
• Title（参考訳）: 遅延フィードバックによる帯域幅のBest-of-Both-Worlds Regretの改善
• Authors: Ofir Schlisselberg, Tal Lancewicki, Peter Auer, Yishay Mansour,
• Abstract要約: 本稿では,Best-Both-Worlds (BoBW) フレームワークにおいて,逆選択遅延を用いたマルチアームバンディット問題について検討する。 我々の主な貢献は、各設定の既知の下界を個別にマッチングする新しいアルゴリズムである。 これは$sum_i>0left(log T/Delta_iright) + frac1Ksum Delta_i sigma_max$で、$Delta_i$はarm $i$と$のサブ最適ギャップである。
• 参考スコア（独自算出の注目度）: 40.86836752251116
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the multi-armed bandit problem with adversarially chosen delays in the Best-of-Both-Worlds (BoBW) framework, which aims to achieve near-optimal performance in both stochastic and adversarial environments. While prior work has made progress toward this goal, existing algorithms suffer from significant gaps to the known lower bounds, especially in the stochastic settings. Our main contribution is a new algorithm that, up to logarithmic factors, matches the known lower bounds in each setting individually. In the adversarial case, our algorithm achieves regret of $\widetilde{O}(\sqrt{KT} + \sqrt{D})$, which is optimal up to logarithmic terms, where $T$ is the number of rounds, $K$ is the number of arms, and $D$ is the cumulative delay. In the stochastic case, we provide a regret bound which scale as $\sum_{i:\Delta_i>0}\left(\log T/\Delta_i\right) + \frac{1}{K}\sum \Delta_i \sigma_{max}$, where $\Delta_i$ is the sub-optimality gap of arm $i$ and $\sigma_{\max}$ is the maximum number of missing observations. To the best of our knowledge, this is the first BoBW algorithm to simultaneously match the lower bounds in both stochastic and adversarial regimes in delayed environment. Moreover, even beyond the BoBW setting, our stochastic regret bound is the first to match the known lower bound under adversarial delays, improving the second term over the best known result by a factor of $K$.
• Abstract（参考訳）: 確率的, 対角的両環境において, 最適に近い性能を実現することを目的としたBest-of-Both-Worlds (BoBW) フレームワークにおいて, 逆選択遅延を伴うマルチアームバンディット問題について検討する。 これまでの研究は、この目標に向けて進歩してきたが、既存のアルゴリズムは、特に確率的設定において、既知の下界に重大なギャップを被っている。 我々の主な貢献は、対数的因子を除いて、各設定の既知下界と個別に一致する新しいアルゴリズムである。 逆数の場合、我々のアルゴリズムは$\widetilde{O}(\sqrt{KT} + \sqrt{D})$を後悔させるが、これは対数項に最適であり、$T$はラウンドの数、$K$はアームの数、$D$は累積遅延である。 確率的ケースでは、$\sum_{i:\Delta_i>0}\left(\log T/\Delta_i\right) + \frac{1}{K}\sum \Delta_i \sigma_{max}$, ここで $\Delta_i$ はarm $i$ と $\sigma_{\max}$ の準最適ギャップであり、失った観測数の最大値である。 我々の知る限りでは、これは遅延環境における確率的・対角的両方の下界を同時に一致させる最初のBoBWアルゴリズムである。 さらに、BoBW設定を超えても、我々の確率的後悔境界は、敵の遅延の下で既知の下界と初めて一致し、最もよく知られた結果よりも、K$の係数で第二項を改善する。

関連論文リスト

• LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits [38.41164102066483]
  本研究では,両逆境における上界を後悔するEmphBest-of-Both-Worlds (BoBW) アルゴリズムを開発した。 提案アルゴリズムは限界条件下で$Oleft(log(T)1+beta2+betaTfrac12+betaright)$ regretを達成していることを示す。
  論文  参考訳（メタデータ） (2024-03-05T18:59:47Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Exploration by Optimization with Hybrid Regularizers: Logarithmic Regret with Adversarial Robustness in Partial Monitoring [41.20252349191698]
  部分的な監視は、限られたフィードバックを伴うオンライン意思決定問題の一般的なフレームワークである。 ハイブリッド正規化器を用いたExOの新しいフレームワークと解析法を提案する。 特に、$O(sum_a neq a*)$で、$k$、$m$、$T$はアクション、観察、ラウンドの数である。
  論文  参考訳（メタデータ） (2024-02-13T09:34:22Z)
• Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
  両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。 我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
  論文  参考訳（メタデータ） (2023-12-24T08:27:30Z)
• Non-stationary Online Convex Optimization with Arbitrary Delays [50.46856739179311]
  本稿では,非定常環境における遅延オンライン凸最適化(OCO)について検討する。 まず, 遅延勾配の勾配降下ステップを, 到着順に応じて行う単純なアルゴリズム, DOGDを提案する。 DOGDが達成した動的後悔境界を$O(sqrtbardT(P_T+1))$に削減する改良アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-05-20T07:54:07Z)
• A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedback [25.68113242132723]
  本稿では,Zimmert と Seldin [2020] のアルゴリズムを,フィードバックの遅れによる逆方向の多重武装バンディットに対して修正したチューニングを行う。 我々は,時間的遅れのある設定において,ほぼ最適の相反的後悔の保証を同時に達成する。 また,任意の遅延の場合に対するアルゴリズムの拡張も提案する。
  論文  参考訳（メタデータ） (2022-06-29T20:49:45Z)
• Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Bounds [34.37963000493442]
  本稿では,マルチアーム・バンディット(MAB)問題について考察し,両対向的条件下でほぼ最適に機能する,新たなベスト・オブ・ボス・ワールド(BOBW)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-06-14T12:58:46Z)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。 O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。 さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
  論文  参考訳（メタデータ） (2021-10-15T00:54:04Z)
• 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)

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

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