論文の概要: Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary

• arxiv url: http://arxiv.org/abs/2609.13547v1
• Date: Fri, 11 Sep 2026 21:23:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-16 07:15:05.390051
• Title: Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary
• Title（参考訳）: Oblivious Adversary を用いたマルチArmed Bandit の最適スイッチングレギュレータの実現に向けて
• Abstract要約: 我々は, 1 つのアルゴリズムが, 難解な敵に対して 1 ドルごとに$widetildemathcalO(sqrt(S+1)KT)$ expected regret を達成することを示す。 提案アルゴリズムは,固定共有学習者と,局所的な改善を探索するダイアディック・インターバルを併用する。
• 参考スコア（独自算出の注目度）: 13.08870048693199
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study switching regret in adversarial multi-armed bandits, where the learner competes with an arm sequence that changes at most $S$ times. When $S$ is known, an optimal expected regret of $\widetilde{\mathcal{O}}(\sqrt{(S+1)KT})$ is obtainable [Auer et al., 2002]. However, when $S$ is unknown, Marinov and Zimmert [2021] show that this guarantee is impossible under an adaptive adversary. In this paper, we show that a single algorithm achieves $\widetilde{\mathcal{O}}(\sqrt{(S+1)KT})$ expected regret for every $S$ against an oblivious adversary, resolving an open problem of Auer et al. [2019b]. Our algorithm combines a fixed-share learner initialized with a small learning rate and dyadic-interval subroutines that search for local improvements using randomized learning rates and implicit exploration. Importantly, a non-uniform prior favors following the main learner, keeping the cost of maintaining many subroutines small. When the subroutines accumulate sufficient improvement over the main learner, its learning rate doubles, allowing adaptation to the unknown number of comparator switches $S$.
• Abstract（参考訳）: 本研究は,学習者が最大で$S$のアームシーケンスと競合する,対向的マルチアームバンディットにおける切替後悔について検討する。 S$ が知られているとき、$\widetilde{\mathcal{O}}(\sqrt{(S+1)KT})$ の最適後悔が得られます [Auer et al , 2002]。 しかし、$S$が未知の場合、Marinov と Zimmert [2021] は、この保証は適応的敵の下では不可能であることを示した。 本論文では, 1つのアルゴリズムが, Auer et al [2019b] のオープンな問題を解き, 難解な相手に対して$S$に対して$\widetilde{\mathcal{O}}(\sqrt{(S+1)KT})$期待の後悔を達成することを示す。 提案アルゴリズムは,ランダム化学習率と暗黙的な探索を用いて局所的な改善を探索する,固定共有学習器を,学習率とダイアディック・インターバルサブルーチンに初期化したものである。 重要なことは、一様でない前向きが主学習者に従い、多くのサブルーチンを小さく維持するコストを抑えることである。 サブルーチンがメインの学習者に対して十分な改善を蓄積すると、学習率が2倍になり、未知のコンパレータスイッチへの適応が$S$となる。

関連論文リスト

• Tracking the Best Strategy in an Extensive-Form Game [6.572714770742585]
  本稿では, 学習者の期待性能を, 振り返りにおける混合戦略のスイッチングシーケンスに対して測定する, 後悔の切り替えという概念に焦点をあてる。 我々のアルゴリズムは非常に効率的で、トライアル時間は$mathcalO(HB)$で、そこでは$B$は学習者が任意の情報集合で利用できる最大アクション数である。
  論文  参考訳（メタデータ） (2026-08-10T12:05:54Z)
• Online learning with Erdős-Rényi side-observation graphs [23.85024184793822]
  本研究では,学習者が実際に選択した腕の横にある多数の腕の損失を観察できるような,逆方向のマルチアームバンディット問題について考察する。 本研究は,すべての非調波アームが,互いに独立に,かつ学習者の行動によって,固定的だが未知の確率$r$で損失を露呈する事例について検討する。 我々は、$N$アームのバンディット問題で$T$ラウンドを行った後、最初のアルゴリズムの期待された後悔は$O(sqrt(T /r) log N )$ whenever $rge(log T)/(2であることを示した。
  論文  参考訳（メタデータ） (2026-04-28T06:29:13Z)
• Scale-Invariant Regret Matching and Online Learning with Optimal Convergence: Bridging Theory and Practice in Zero-Sum Games [60.871651115241406]
  ゼロサムゲームにおける理論と実践の間、何十年にもわたってかなりのシャズムが一階法によって浸食されてきた。 我々は、IREG-PRM$+$と呼ぶPRM$+$の新しいスケール不変かつパラメータフリーな変種を提案する。 ベンチマークゲームでは, PRM$+$と同等でありながら, 最適収束保証を$T-1/2$, $T-1$とする。
  論文  参考訳（メタデータ） (2025-10-06T00:33:20Z)
• p-Mean Regret for Stochastic Bandits [52.828710025519996]
  単純で統一された UCB ベースのアルゴリズムを導入し、新しい$p$-mean の後悔境界を実現する。 我々の枠組みは、特別な場合として、平均的な累積的後悔とナッシュ後悔の両方を包含する。
  論文  参考訳（メタデータ） (2024-12-14T08:38:26Z)
• 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)
• A New Look at Dynamic Regret for Non-Stationary Stochastic Bandits [11.918230810566945]
  本研究では,学習過程において各腕の報酬統計が数回変化しうる非定常的マルチアームバンディット問題について検討する。 我々は、$K$の武器付きバンディット問題において、ほぼ最適の$widetilde O(sqrtK N(S+1))$ dynamic regretを実現する方法を提案する。
  論文  参考訳（メタデータ） (2022-01-17T17:23:56Z)
• On Submodular Contextual Bandits [92.45432756301231]
  作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。 Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
  論文  参考訳（メタデータ） (2021-12-03T21:42:33Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。 提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。 我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
  論文  参考訳（メタデータ） (2021-06-15T02:23:07Z)
• An Algorithm for Stochastic and Adversarial Bandits with Switching Costs [10.549307055348596]
  そこで本研究では,マルチアームバンディットのスイッチングコストを考慮したアルゴリズムを提案し,そのアルゴリズムがアームを切り替える度に$lambda$を支払う。 私たちのアルゴリズムは、Zimmert and Seldin(2021)のTsallis-INFアルゴリズムの適応に基づいています。
  論文  参考訳（メタデータ） (2021-02-19T11:03:51Z)
• Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks [48.32532049640782]
  ガウス境界の下で, 1層ReLUネットワークを$k$の隠れ単位で学習する問題をmathbbRd$で研究する。 正の係数の場合、この学習問題の初回アルゴリズムを$k$から$tildeOOmega(sqrtlog d)$まで与える。
  論文  参考訳（メタデータ） (2020-06-22T17:53:54Z)
• Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transition [38.28925339231888]
  我々は,世界最良保証付きの最初のアルゴリズムを開発した。 損失が逆ならば、$mathcalO(log T)$ regretを達成します。 より一般的には、中間設定で $tildemathcalO(sqrtC)$ regret を達成する。
  論文  参考訳（メタデータ） (2020-06-10T01:59:34Z)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)

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

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