論文の概要: Follow-the-Perturbed-Leader with Fr\'{e}chet-type Tail Distributions: Optimality in Adversarial Bandits and Best-of-Both-Worlds

• arxiv url: http://arxiv.org/abs/2403.05134v1
• Date: Fri, 8 Mar 2024 08:07:26 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-11 20:41:20.394854
• Title: Follow-the-Perturbed-Leader with Fr\'{e}chet-type Tail Distributions: Optimality in Adversarial Bandits and Best-of-Both-Worlds
• Title（参考訳）: fr\'{e}chet型テール分布をもつ摂動リーダー--逆バンディットと両世界の最適性
• Authors: Jongyeong Lee and Junya Honda and Shinji Ito and Min-hwan Oh
• Abstract要約: 本研究では,敵対的・武装的盗賊に対するFTPL(Follow-the-Perturbed-Leader)政策の最適性について検討した。 逆条件で$mathcalO(sqrtKT)$ regretsを達成するのに十分な摂動条件を確立する。
• 参考スコア（独自算出の注目度）: 43.35179630620512
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies the optimality of the Follow-the-Perturbed-Leader (FTPL) policy in both adversarial and stochastic $K$-armed bandits. Despite the widespread use of the Follow-the-Regularized-Leader (FTRL) framework with various choices of regularization, the FTPL framework, which relies on random perturbations, has not received much attention, despite its inherent simplicity. In adversarial bandits, there has been conjecture that FTPL could potentially achieve $\mathcal{O}(\sqrt{KT})$ regrets if perturbations follow a distribution with a Fr\'{e}chet-type tail. Recent work by Honda et al. (2023) showed that FTPL with Fr\'{e}chet distribution with shape $\alpha=2$ indeed attains this bound and, notably logarithmic regret in stochastic bandits, meaning the Best-of-Both-Worlds (BOBW) capability of FTPL. However, this result only partly resolves the above conjecture because their analysis heavily relies on the specific form of the Fr\'{e}chet distribution with this shape. In this paper, we establish a sufficient condition for perturbations to achieve $\mathcal{O}(\sqrt{KT})$ regrets in the adversarial setting, which covers, e.g., Fr\'{e}chet, Pareto, and Student-$t$ distributions. We also demonstrate the BOBW achievability of FTPL with certain Fr\'{e}chet-type tail distributions. Our results contribute not only to resolving existing conjectures through the lens of extreme value theory but also potentially offer insights into the effect of the regularization functions in FTRL through the mapping from FTPL to FTRL.
• Abstract（参考訳）: 本稿では,逆境と確率的k$-armed banditsにおけるftplポリシーの最適性について検討する。 FTRL(Follow-the-Regularized-Leader)フレームワークが多種多様な正規化の選択肢で広く使われているにもかかわらず、FTPLフレームワークは本質的に単純であるにもかかわらず、ランダムな摂動に依存しているがあまり注目されていない。 逆の包帯では、FTPL が Fr\'{e}chet 型の尾を持つ分布に摂動が従えば $\mathcal{O}(\sqrt{KT})$ regrets を達成できると推測されている。 最近のHonda et al. (2023) による研究によると、Fr\'{e}chet分布と形状が$\alpha=2$のFTPLはこの境界に達しており、特に確率的包帯における対数的後悔はFTPLのBest-of-Both-Worlds(BOBW)能力を意味する。 しかし、この結果は上記の予想を部分的に解決するだけであり、その解析はこの形を持つfr\'{e}chet分布の特定の形式に大きく依存するためである。 本稿では, 反逆集合において, 摂動が$\mathcal{o}(\sqrt{kt})$ となるような十分条件を定め, 例えばfr\'{e}chet, pareto, student-$t$ 分布を含む。 また,特定のFr\'{e}chet型テール分布を持つFTPLのBOBW達成可能性を示す。 この結果は, 極値理論のレンズによる既存予想の解法だけでなく, FTPL から FTRL への写像による FTRL の正則化関数の効果に関する洞察を与える可能性がある。

関連論文リスト

• Distributed Online Optimization with Stochastic Agent Availability [14.801853435122904]
  エージェントが各ステップで既知の確率$p$でアクティブである分散オンライン最適化の変種について検討する。 我々は,そのネットワーク後悔を,アクティブエージェントの即時後悔の平均から分析する。
  論文  参考訳（メタデータ） (2024-11-25T15:20:01Z)
• Gradual Domain Adaptation via Manifold-Constrained Distributionally Robust Optimization [0.4732176352681218]
  本稿では、多様体制約データ分布のクラスにおける段階的領域適応の課題に対処する。 本稿では,適応的なワッサースタイン半径を持つ分布ロバスト最適化(DRO)を基礎とした手法を提案する。 我々のバウンダリは、新たに導入されたそれとの互換性尺度に依存しており、シーケンスに沿ったエラー伝搬のダイナミクスを完全に特徴付けています。
  論文  参考訳（メタデータ） (2024-10-17T22:07:25Z)
• Optimism in the Face of Ambiguity Principle for Multi-Armed Bandits [6.7310264583128445]
  FTRL (Follow-The-Regularized-Leader) アルゴリズムは、しばしば敵対的問題や盗賊問題に対して最適な後悔を味わう。 本稿では,逆方向と多重方向の両方の帯域に対して最適なポリシを生成する新しいFTPLアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-09-30T16:00:23Z)
• Implicitly normalized forecaster with clipping for linear and non-linear heavy-tailed multi-armed bandits [85.27420062094086]
  Implicitly Normalized Forecaster (INF) は、敵対的マルチアームバンディット(MAB)問題に対する最適解であると考えられている。 重み付き設定のMAB問題に対するクリッピング(INFclip)を用いたINFの新バージョン"Implicitly Normalized Forecaster"を提案する。 INFclipは線形重み付きMAB問題に対して最適であり、非線形問題に対して有効であることを示す。
  論文  参考訳（メタデータ） (2023-05-11T12:00:43Z)
• Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a Generative Model [50.38446482252857]
  2人プレイのゼロサムマルコフゲームは多エージェント強化学習においておそらく最も基本的な設定である。 我々は,$$ widetildeObiggを用いて,$varepsilon$-approximate Markov NEポリシーを学習する学習アルゴリズムを開発した。 我々は、分散型量の役割を明確にするFTRLに対する洗練された後悔境界を導出する。
  論文  参考訳（メタデータ） (2022-08-22T17:24:55Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。 次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。 我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
  論文  参考訳（メタデータ） (2022-02-23T16:10:23Z)
• Robust Learning of Optimal Auctions [84.13356290199603]
  本研究では、入札者の評価値のサンプルを逆向きに破損させたり、逆向きに歪んだ分布から引き出すことができる場合に、サンプルから収益-最適マルチバイダオークションを学習する問題について検討する。 我々は,コルモゴロフ-スミルノフ距離における元の分布に対して$alpha$-closeの「全ての真の分布」に対して,収入がほぼ同時に最適であるメカニズムを学習できる新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-07-13T17:37:21Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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