論文の概要: 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ドル倍の相当な計算効率向上を実現し、同時に両レシエーションの実証性能も向上した。 最後に,本手法が純粋な探索政策より優れており,また,本手法と標準的な搾取政策とを鼻で組み合わせることが準最適であることを実証的に示す。

関連論文リスト

• 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)

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

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