論文の概要: Note on Follow-the-Perturbed-Leader in Combinatorial Semi-Bandit Problems

• arxiv url: http://arxiv.org/abs/2506.12490v1
• Date: Sat, 14 Jun 2025 13:06:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-17 17:28:46.381122
• Title: Note on Follow-the-Perturbed-Leader in Combinatorial Semi-Bandit Problems
• Title（参考訳）: 組合せ半帯域問題におけるFollow-the-Perturbed-Leaderについて
• Authors: Botao Chen, Junya Honda,
• Abstract要約: 小型不変半帯域問題におけるFollow-the-Perturbed-Leader(FTPL)ポリシーの最適性と複雑性について検討する。 我々は条件付き幾何再サンプリング(CGR)をサイズ不変半帯域設定に拡張し、計算の複雑さをオリジナルのGRの$O(d2)$から$Oleft(mdleft(log(d/m)+1right)$に縮める。
• 参考スコア（独自算出の注目度）: 10.435741631709403
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies the optimality and complexity of Follow-the-Perturbed-Leader (FTPL) policy in size-invariant combinatorial semi-bandit problems. Recently, Honda et al. (2023) and Lee et al. (2024) showed that FTPL achieves Best-of-Both-Worlds (BOBW) optimality in standard multi-armed bandit problems with Fr\'{e}chet-type distributions. However, the optimality of FTPL in combinatorial semi-bandit problems remains unclear. In this paper, we consider the regret bound of FTPL with geometric resampling (GR) in size-invariant semi-bandit setting, showing that FTPL respectively achieves $O\left(\sqrt{m^2 d^\frac{1}{\alpha}T}+\sqrt{mdT}\right)$ regret with Fr\'{e}chet distributions, and the best possible regret bound of $O\left(\sqrt{mdT}\right)$ with Pareto distributions in adversarial setting. Furthermore, we extend the conditional geometric resampling (CGR) to size-invariant semi-bandit setting, which reduces the computational complexity from $O(d^2)$ of original GR to $O\left(md\left(\log(d/m)+1\right)\right)$ without sacrificing the regret performance of FTPL.
• Abstract（参考訳）: 本稿では,Follow-the-Perturbed-Leader(FTPL)ポリシーの,サイズ不変な組合せ半帯域問題における最適性と複雑性について検討する。 最近、Honda et al (2023) とLee et al (2024) は、Fr\'{e}chet型分布を持つ標準的な多重武装バンディット問題においてFTPLがBest-of-Both-Worlds (BOBW) 最適性を達成することを示した。 しかし、組合せ半帯域問題におけるFTPLの最適性は未だ不明である。 本稿では,サイズ不変半帯域設定におけるFTPLと幾何再サンプリング(GR)との後悔境界について考察し,それぞれ$O\left(\sqrt{m^2 d^\frac{1}{\alpha}T}+\sqrt{mdT}\right)$ regret with Fr\'{e}chet distributions, and the best possible regret bound of $O\left(\sqrt{mdT}\right)$ with Pareto distributions in adversarial set。 さらに、条件付き幾何再サンプリング(CGR)をサイズ不変半帯域設定に拡張し、元のGRの$O(d^2)$から$O\left(md\left(\log(d/m)+1\right)\right)$に計算複雑性を低減させる。

関連論文リスト

• Follow-the-Perturbed-Leader Approaches Best-of-Both-Worlds for the m-Set Semi-Bandit Problems [20.47953854427799]
  半帯域問題の場合、学習者は、合計$d$アームから$m$アームを正確に選択する。 また, Fr'echet 摂動を持つFTPL は, 逆向き設定で $mathcalO(sqrtnmdlog(d))$ に近い最適リセットも享受できることを示す。
  論文  参考訳（メタデータ） (2025-04-09T22:07:01Z)
• Follow-the-Perturbed-Leader with Fr\'{e}chet-type Tail Distributions: Optimality in Adversarial Bandits and Best-of-Both-Worlds [43.35179630620512]
  本研究では,敵対的・武装的盗賊に対するFTPL(Follow-the-Perturbed-Leader)政策の最適性について検討した。 逆条件で$mathcalO(sqrtKT)$ regretsを達成するのに十分な摂動条件を確立する。
  論文  参考訳（メタデータ） (2024-03-08T08:07:26Z)
• LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits [38.41164102066483]
  本研究では,両逆境における上界を後悔するEmphBest-of-Both-Worlds (BoBW) アルゴリズムを開発した。 提案アルゴリズムは限界条件下で$Oleft(log(T)1+beta2+betaTfrac12+betaright)$ regretを達成していることを示す。
  論文  参考訳（メタデータ） (2024-03-05T18:59:47Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• 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)
• Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games [104.74734408204749]
  マルチプレイヤーの汎用正規形式ゲームにおいて,OMWU(Optimistic Multiplicative Weights Update)を用いているエージェントが全員,O(textrmpolylog(T))$(T$)$(T$)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$)であることを示す。 外部の後悔から内部の後悔へと結果を拡張し、後悔を交換することで、近似した平衡に収束する非結合学習ダイナミクスを確立する。
  論文  参考訳（メタデータ） (2021-11-11T01:19:53Z)
• 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)

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

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