論文の概要: Follow-the-Perturbed-Leader Achieves Best-of-Both-Worlds for the m-Set Semi-Bandit Problems

• arxiv url: http://arxiv.org/abs/2504.07307v1
• Date: Wed, 09 Apr 2025 22:07:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-11 12:23:12.326225
• Title: Follow-the-Perturbed-Leader Achieves Best-of-Both-Worlds for the m-Set Semi-Bandit Problems
• Title（参考訳）: mセット半帯域問題に対するFollow-the-Perturbed-Leader Achievs Best-of-Both-Worlds
• Authors: Jingxin Zhan, Zhihua Zhang,
• Abstract要約: FTRL(Follow-the-Regularized-Leader)ポリシーは、アーム選択確率を明示的に計算する必要がある。 また, Fr'eche't 摂動を持つFTPLは, 対向的な設定で, $mathcalO(sqrtnmd)$を最適に再現できることを示す。
• 参考スコア（独自算出の注目度）: 22.87882885963586
• License:
• Abstract: We consider a common case of the combinatorial semi-bandit problem, the $m$-set semi-bandit, where the learner exactly selects $m$ arms from the total $d$ arms. In the adversarial setting, the best regret bound, known to be $\mathcal{O}(\sqrt{nmd})$ for time horizon $n$, is achieved by the well-known Follow-the-Regularized-Leader (FTRL) policy, which, however, requires to explicitly compute the arm-selection probabilities by solving optimizing problems at each time step and sample according to it. This problem can be avoided by the Follow-the-Perturbed-Leader (FTPL) policy, which simply pulls the $m$ arms that rank among the $m$ smallest (estimated) loss with random perturbation. In this paper, we show that FTPL with a Fr\'echet perturbation also enjoys the optimal regret bound $\mathcal{O}(\sqrt{nmd})$ in the adversarial setting and achieves best-of-both-world regret bounds, i.e., achieves a logarithmic regret for the stochastic setting.
• Abstract（参考訳）: 組み合わせ半バンド問題である$m$-set半バンド問題では、学習者が合計$d$アームから$m$のアームを正確に選択する。 逆条件では、最良の後悔境界である$\mathcal{O}(\sqrt{nmd})$ for time horizon $n$は、よく知られたFollow-the-Regularized-Leader (FTRL)ポリシーによって達成される。 この問題はFollow-the-Perturbed-Leader (FTPL)ポリシーによって回避できる。 本稿では, Fr'echet 摂動を持つFTPL は, 対数的条件下では$\mathcal{O}(\sqrt{nmd})$ の最適リフレッシュを享受し, 対数的リフレクション(対数的リフレクション)を達成していることを示す。

関連論文リスト

• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Best-of-Both-Worlds Linear Contextual Bandits [45.378265414553226]
  本研究は, 対向汚職下での多武装盗賊問題の事例である$K$腕線形文脈盗賊の問題を考察する。 我々は,理論的保証のもと,双方の敵環境に有効な戦略を開発する。 両体制の理論的保証から,我々の戦略をBest-of-Both-Worlds (BoBW) RealFTRLと呼んでいる。
  論文  参考訳（メタデータ） (2023-12-27T09:32:18Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Multi-Fidelity Multi-Armed Bandits Revisited [46.19926456682379]
  我々は,MF-MAB(Multi-fidelity multi-armed bandit)問題の拡張であるMF-MAB(Multi-fidelity multi-armed bandit)について検討した。 MF-MABは、各アームを異なるコスト(忠実さ)と観察精度で引っ張ることができる。
  論文  参考訳（メタデータ） (2023-06-13T13:19:20Z)
• Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
  確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。 トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
  論文  参考訳（メタデータ） (2023-03-30T02:51:00Z)
• Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Bounds [34.37963000493442]
  本稿では,マルチアーム・バンディット(MAB)問題について考察し,両対向的条件下でほぼ最適に機能する,新たなベスト・オブ・ボス・ワールド(BOBW)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-06-14T12:58:46Z)
• Combinatorial Bandits without Total Order for Arms [52.93972547896022]
  セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。 我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
  論文  参考訳（メタデータ） (2021-03-03T23:08:59Z)
• 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)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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