論文の概要: Follow-the-Perturbed-Leader for Decoupled Bandits: Best-of-Both-Worlds and Practicality

• arxiv url: http://arxiv.org/abs/2510.12152v1
• Date: Tue, 14 Oct 2025 05:14:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-15 19:02:32.193975
• Title: Follow-the-Perturbed-Leader for Decoupled Bandits: Best-of-Both-Worlds and Practicality
• Title（参考訳）: 疎結合バンドのフォロー・ザ・フォーチュアベッド・リーダー:ベスト・オブ・ボトム・ワールドと実用性
• Authors: Chaiwon Kim, Jongyeong Lee, Min-hwan Oh,
• Abstract要約: そこで,本研究では,学習者が探索用アームと各ラウンドでの活用用アームを1つ選択する,切り離されたマルチアームバンディット(MAB)問題について検討する。 本稿では,摂動を用いたFollow-the-Perturbed-Leaderフレームワークのポリシーを提案する。
• 参考スコア（独自算出の注目度）: 31.976008841459237
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the decoupled multi-armed bandit (MAB) problem, where the learner selects one arm for exploration and one arm for exploitation in each round. The loss of the explored arm is observed but not counted, while the loss of the exploited arm is incurred without being observed. We propose a policy within the Follow-the-Perturbed-Leader (FTPL) framework using Pareto perturbations. Our policy achieves (near-)optimal regret regardless of the environment, i.e., Best-of-Both-Worlds (BOBW): constant regret in the stochastic regime, improving upon the optimal bound of the standard MABs, and minimax optimal regret in the adversarial regime. Moreover, the practicality of our policy stems from avoiding both the convex optimization step required by the previous BOBW policy, Decoupled-Tsallis-INF (Rouyer & Seldin, 2020), and the resampling step that is typically necessary in FTPL. Consequently, it achieves substantial computational improvement, about $20$ times faster than Decoupled-Tsallis-INF, while also demonstrating better empirical performance in both regimes. Finally, we empirically show that our approach outperforms a pure exploration policy, and that naively combining a pure exploration with a standard exploitation policy is suboptimal.
• Abstract（参考訳）: そこで,本研究では,学習者が探索用アームと各ラウンドでの活用用アームを1つ選択する,切り離されたマルチアームバンディット(MAB)問題について検討する。 探索された腕の喪失は観察されるが数えられず、一方、悪用された腕の喪失は観察されることなく引き起こされる。 本稿では,Pareto摂動を用いたFTPL(Follow-the-Perturbed-Leader)フレームワーク内でのポリシーを提案する。 我々の政策は、環境に関係なく(BOBW(Best-of-Both-Worlds:ベスト・オブ・ボス・ワールドズ)、確率的体制における絶え間ない後悔、標準MABの最適境界の改善、敵的体制における最小の後悔を(ほぼ)達成する。 さらに,本政策の実践性は,従来のBOBW政策で求められる凸最適化ステップであるDecoupled-Tsallis-INF (Rouyer & Seldin, 2020)と,FTPLで通常必要とされる再サンプリングステップの両方を回避することに起因する。 その結果、Decoupled-Tsallis-INFの約20ドル倍の相当な計算効率向上を実現し、同時に両レシエーションの実証性能も向上した。 最後に,本手法が純粋な探索政策より優れており,また,本手法と標準的な搾取政策とを鼻で組み合わせることが準最適であることを実証的に示す。

関連論文リスト

• Coverage Improvement and Fast Convergence of On-policy Preference Learning [67.36750525893514]
  言語モデルアライメントのためのオンラインのオンラインプライオリティ学習アルゴリズムは、オフラインのアルゴリズムよりも大幅に優れている。 我々は,サンプリング政策の包括的範囲が政治訓練を通じてどのように進展するかを分析する。 一般機能クラス設定における報奨蒸留のための原則的オンライン方式を開発した。
  論文  参考訳（メタデータ） (2026-01-13T10:46:06Z)
• Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback [61.49239204705301]
  本研究では,有限水平マルコフ決定過程(MDP)におけるオンライン学習について,包括的包括的包括的フィードバックモデルを用いて検討する。 本研究は, オンライン最短経路問題の近年の進展に触発された, 占領対策, 自己拘束技術, 新たな損失推定器の組合せに依拠する。
  論文  参考訳（メタデータ） (2025-10-20T02:28:08Z)
• Follow-the-Perturbed-Leader Approaches Best-of-Both-Worlds for the m-Set Semi-Bandit Problems [18.74680577173648]
  我々は、学習者が$m$の腕から$m$の腕を正確に選択する、$m$セット半帯域問題の一般的な場合を考える。 また, Fr'echet 摂動を持つFTPL は, 対向的な設定で, $mathcalO(sqrtnm(sqrtdlog(d)+m5/6)$ をほぼ最適に再現できることを示す。
  論文  参考訳（メタデータ） (2025-04-09T22:07:01Z)
• Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizer [52.09480867526656]
  人間の嗜好を学習する際の分布変化と不確実性の一形態として,不一致の原因を同定する。 過度な最適化を緩和するために、まず、逆選択された報酬モデルに最適なポリシーを選択する理論アルゴリズムを提案する。 報奨モデルとそれに対応する最適ポリシーの等価性を用いて、優先最適化損失と教師付き学習損失を組み合わせた単純な目的を特徴とする。
  論文  参考訳（メタデータ） (2024-05-26T05:38:50Z)
• Thompson Exploration with Best Challenger Rule in Best Arm Identification [59.02170783023547]
  本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。 我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
  論文  参考訳（メタデータ） (2023-10-01T01:37:02Z)
• Provably Convergent Policy Optimization via Metric-aware Trust Region Methods [21.950484108431944]
  信頼領域法は、強化学習における政策最適化の安定化に広く用いられている。 我々は、より柔軟なメトリクスを活用し、ワッサーシュタインとシンクホーンの信頼領域によるポリシー最適化の2つの自然な拡張について検討する。 WPOは単調な性能向上を保証し、SPOはエントロピー正則化器が減少するにつれてWPOに確実に収束することを示す。
  論文  参考訳（メタデータ） (2023-06-25T05:41:38Z)
• Best of Both Worlds Policy Optimization [33.13041034490332]
  本稿では,正則化器,探索ボーナス,学習率を適切に設計することにより,損失が相反する場合には,より好意的なポリログ$(T)=後悔が得られることを示す。 政策最適化のために、ギャップ依存のポリログ$(T)$後悔境界が示されるのはこれが初めてである。
  論文  参考訳（メタデータ） (2023-02-18T19:46:11Z)
• A Simple and Optimal Policy Design with Safety against Heavy-Tailed Risk for Stochastic Bandits [27.058087400790555]
  マルチアームバンディット問題について検討し,期待された後悔に対する最悪のケース最適性と,後悔の分布に対する軽微なリスクの両方を享受する新しいポリシーを設計する。 経営的な観点から、我々の新しい政策設計は、より良い尾の分布をもたらし、祝福された政策よりも好まれることがわかった。
  論文  参考訳（メタデータ） (2022-06-07T02:10:30Z)
• Achieving the Pareto Frontier of Regret Minimization and Best Arm Identification in Multi-Armed Bandits [91.8283876874947]
  本稿では,BoBW-lil'UCB$(gamma)$アルゴリズムの設計と解析を行う。 i) RMとBAIの両方の目的に対して最適なアルゴリズムを同時に実行できないことを示す。 また、BoBW-lil'UCB$(gamma)$は、時間複雑性と後悔の点で競合よりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-10-16T17:52:32Z)
• Optimistic Policy Optimization with Bandit Feedback [70.75568142146493]
  我々は,事前の報奨を後悔する$tilde O(sqrtS2 A H4 K)を定め,楽観的な信頼領域ポリシー最適化(TRPO)アルゴリズムを提案する。 我々の知る限り、この2つの結果は、未知の遷移と帯域幅フィードバックを持つポリシー最適化アルゴリズムにおいて得られた最初のサブ線形後悔境界である。
  論文  参考訳（メタデータ） (2020-02-19T15:41:18Z)

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

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