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

• arxiv url: http://arxiv.org/abs/2504.07307v2
• Date: Tue, 22 Apr 2025 15:16:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-01 02:33:48.967971
• Title: Follow-the-Perturbed-Leader Approaches Best-of-Both-Worlds for the m-Set Semi-Bandit Problems
• Title（参考訳）: mセット半帯域問題に対するFollow-the-Perturbed-Leader Approachs Best-of-Both-Worlds
• Authors: Jingxin Zhan, Yuchen Xin, Zhihua Zhang,
• Abstract要約: 半帯域問題の場合、学習者は、合計$d$アームから$m$アームを正確に選択する。 また, Fr'echet 摂動を持つFTPL は, 逆向き設定で $mathcalO(sqrtnmdlog(d))$ に近い最適リセットも享受できることを示す。
• 参考スコア（独自算出の注目度）: 20.47953854427799
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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. However, this requires to explicitly compute the arm-selection probabilities via optimizing problems at each time step and sample according to them. 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 near optimal regret bound $\mathcal{O}(\sqrt{nmd\log(d)})$ in the adversarial setting and approaches 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\log(d)})$ に近い最適リフレクションを享受し, 対数的リフレクション(対数的リフレクション)を実現していることを示す。

関連論文リスト

• 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)
• Fast and Regret Optimal Best Arm Identification: Fundamental Limits and Low-Complexity Algorithms [15.038210624870656]
  2つの目的を持つマルチアーメッド・バンドイット(MAB)問題: (i) 最適なアームに対する迅速な識別とコミットメント、および (ii) 連続したラウンドで連続して$T$の報酬。 本稿では,これら2つの目的を達成することを目的としたemphRegret Best Arm Identification (ROBAI)を紹介する。
  論文  参考訳（メタデータ） (2023-09-01T17:12:43Z)
• 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)
• On Submodular Contextual Bandits [92.45432756301231]
  作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。 Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
  論文  参考訳（メタデータ） (2021-12-03T21:42:33Z)
• Scale-Free Adversarial Multi-Armed Bandit with Arbitrary Feedback Delays [21.94728545221709]
  制限のないフィードバック遅延を伴うMAB(Scale-Free Adversarial Multi Armed Bandit)問題を考える。 textttSFBankerは$mathcal O(sqrtK(D+T)L)cdot rm polylog(T, L)$ total regret, where $T$ is the total number of steps, $D$ is the total feedback delay。
  論文  参考訳（メタデータ） (2021-10-26T04:06:51Z)
• 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)
• Explicit Best Arm Identification in Linear Bandits Using No-Regret Learners [17.224805430291177]
  線形パラメータ化マルチアームバンドにおけるベストアーム識別の問題について検討する。 そこで本研究では,この問題を解決するために,明示的に実装可能かつ証明可能な順序-最適サンプル-複雑度アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-13T05:00:01Z)

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

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