論文の概要: Toward Optimal Second-Order Path-Length Guarantee for Adversarial Multi-Armed Bandits

• arxiv url: http://arxiv.org/abs/2608.15996v1
• Date: Mon, 17 Aug 2026 01:17:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-18 19:59:03.496858
• Title: Toward Optimal Second-Order Path-Length Guarantee for Adversarial Multi-Armed Bandits
• Title（参考訳）: 最適2次パス長保証に向けて
• Abstract要約: 本研究は, 敵の損失列に対するK$武器帯の2次パス長後悔について検討する。 我々のアルゴリズムは$mathcalOleft(Klog(KT)+sqrtKlog(KT)bigl (1+Q_infty,2bigr)right)$ expected regret if $Q_infty,2$ is known, where $T$ is the horizon。
• 参考スコア（独自算出の注目度）: 13.08870048693199
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study second-order path-length regret in adversarial $K$-armed bandits against oblivious loss sequences. Bubeck et al. [2019] designed an algorithm that achieves $\widetilde{\mathcal{O}}(K+\sqrt{KQ_{\infty,1}})$ regret, where $Q_{\infty,1}$ is the first-order path length, and left open whether $\widetilde{\mathcal{O}}(\text{poly}(K)\sqrt{1+Q_{\infty,2}})$ regret is achievable under bandit feedback, where $Q_{\infty,2}$ is the second-order path length. Somewhat surprisingly, we resolve this question positively by showing that with a more involved analysis, the exact same algorithm of Bubeck et al. [2019] achieves $\mathcal{O}\left(K\log(KT)+\sqrt{K\log(KT)\bigl(1+Q_{\infty,2}\bigr)}\right)$ expected regret when $Q_{\infty,2}$ is known, where $T$ is the horizon. This matches the $Ω(\sqrt{KQ_{\infty,2}})$ lower bound up to logarithmic factors and additive terms. We further remove the knowledge of $Q_{\infty,2}$ using an adaptive restart scheme whose path-length estimator has uniformly bounded increments.
• Abstract（参考訳）: 本研究は, 敵の損失列に対するK$武器帯の2次パス長後悔について検討する。 Bubeck et al [2019] は $\widetilde{\mathcal{O}}(K+\sqrt{KQ_{\infty,1}})$ regret, where $Q_{\infty,1}$は一階のパス長であり、$\widetilde{\mathcal{O}}(\text{poly}(K)\sqrt{1+Q_{\infty,2}})$ regret は二階のパス長である。 驚くべきことに、より複雑な解析によって、Bubeck et al [2019] の全く同じアルゴリズムが $\mathcal{O}\left(K\log(KT)+\sqrt{K\log(KT)\bigl(1+Q_{\infty,2}\bigr)}\right)$Q_{\infty,2}$ が知られているときの期待される後悔は、$Q_{\infty,2}$ が地平線であることを示すことによって、この問題を肯定的に解決する。 これは$Ω(\sqrt{KQ_{\infty,2}})$ 対数因子と加法的項に下界する。 さらに、経路長推定器が一様有界なインクリメントを持つ適応的再帰スキームを用いて、$Q_{\infty,2}$の知識を除去する。

関連論文リスト

• Nearly Minimax-Optimal Regret for Linear Contextual Bandits with Arbitrary Adaptive Action Sets [10.262827207917585]
  パラメータや相互作用履歴に依存する任意のアクションメニューを持つ線形文脈帯域について検討する。 対数的要因まで,上下境界の一致を確立した。
  論文  参考訳（メタデータ） (2026-09-14T07:57:45Z)
• High-Dimensional Procrustes Matching via Tree Counts [5.464035038606368]
  Procrustes matching problem(英語版)は、2つの集合を整列する$[n]$の未知の置換を復元するように要求する。 gtrsim maxlog n/d,sqrtlog n/n$ のとき、正確な回復が可能であることを示す。 また,木数計算アルゴリズムには条件2 > sqrt$ が必要であることを示唆する低次優位計算を行う。
  論文  参考訳（メタデータ） (2026-07-09T14:33:47Z)
• Deterministic Hardness of Approximation of Unique-SVP and GapSVP in $\ell_p$ norms for $p>2$ [0.0]
  我々は、$ell_p$ norm(mathsfSVP_p$)およびUnique-SVP(mathsfuSVP_p$)における最短ベクトル問題に対する近似結果の決定的困難性を確立する。 すべての$p > 2$に対して、定数比硬さを証明します: no-time algorithm almosts $mathsfSVP_p$ or $mathsfuSVP_p$ in a ratio of $sqrt2 - o(1)$。
  論文  参考訳（メタデータ） (2025-10-19T20:17:26Z)
• Batched Stochastic Bandit for Nondegenerate Functions [8.015503209312786]
  本稿では,非退化関数に対するバッチ帯域学習問題について検討する。 本稿では,非退化関数に対するバッチバンドイット問題をほぼ最適に解くアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-09T12:50:16Z)
• On the Minimax Regret for Online Learning with Feedback Graphs [5.721380617450645]
  強く観察可能な無向フィードバックグラフを用いて,オンライン学習を後悔する上で,上層と下層の境界を改善した。 改良された上界$mathcalObigl(sqrtalpha T(ln K)/(lnalpha)bigr)$ hold for any $alpha$ and the lower bounds for bandits and experts。
  論文  参考訳（メタデータ） (2023-05-24T17:40:57Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。 我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。 技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
  論文  参考訳（メタデータ） (2022-10-15T09:22:22Z)
• Delaytron: Efficient Learning of Multiclass Classifiers with Delayed Bandit Feedbacks [6.624726878647541]
  Adaptive Delaytronは、$mathcalOleft(sqrtfrac2 Kgammaleft[fracT2+left(2+fracL2R2Vert WVert_F2right)sum_t=1Td_tright)の後悔の限界を達成する。 我々は、Adaptive Delaytronが$mathcalOleft(sqrtfrac2 Kgammaleft[fracT2]の後悔の限界を達成することを示す。
  論文  参考訳（メタデータ） (2022-05-17T11:12:20Z)
• Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
  S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。 経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
  論文  参考訳（メタデータ） (2021-03-25T18:52:17Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。 2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
  論文  参考訳（メタデータ） (2021-03-10T07:33:03Z)
• 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)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)

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

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