論文の概要: Comparator-Adaptive $Φ$-Regret: Improved Bounds, Simpler Algorithms, and Applications to Games

• arxiv url: http://arxiv.org/abs/2505.17277v1
• Date: Thu, 22 May 2025 20:45:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-26 18:08:33.68941
• Title: Comparator-Adaptive $Φ$-Regret: Improved Bounds, Simpler Algorithms, and Applications to Games
• Title（参考訳）: Comparator-Adaptive $ $-Regret: 改良された境界、より単純なアルゴリズム、ゲームへの応用
• Authors: Soumita Hait, Ping Li, Haipeng Luo, Mengxiao Zhang,
• Abstract要約: Lu et al., [2025] による最近の研究は、コンパレータ $phi$ に対する後悔が、ある疎度ベースの複雑性尺度$phi$ に依存する適応アルゴリズムを導入している。 本研究では,より単純なアルゴリズムを用いて,より優れたコンパレータ適応型$Phi$-regretバウンドを実現するための一般的なアイデアを提案する。
• 参考スコア（独自算出の注目度）: 43.12477663757647
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the classic expert problem, $\Phi$-regret measures the gap between the learner's total loss and that achieved by applying the best action transformation $\phi \in \Phi$. A recent work by Lu et al., [2025] introduces an adaptive algorithm whose regret against a comparator $\phi$ depends on a certain sparsity-based complexity measure of $\phi$, (almost) recovering and interpolating optimal bounds for standard regret notions such as external, internal, and swap regret. In this work, we propose a general idea to achieve an even better comparator-adaptive $\Phi$-regret bound via much simpler algorithms compared to Lu et al., [2025]. Specifically, we discover a prior distribution over all possible binary transformations and show that it suffices to achieve prior-dependent regret against these transformations. Then, we propose two concrete and efficient algorithms to achieve so, where the first one learns over multiple copies of a prior-aware variant of the Kernelized MWU algorithm of Farina et al., [2022], and the second one learns over multiple copies of a prior-aware variant of the BM-reduction [Blum and Mansour, 2007]. To further showcase the power of our methods and the advantages over Lu et al., [2025] besides the simplicity and better regret bounds, we also show that our second approach can be extended to the game setting to achieve accelerated and adaptive convergence rate to $\Phi$-equilibria for a class of general-sum games. When specified to the special case of correlated equilibria, our bound improves over the existing ones from Anagnostides et al., [2022a,b]
• Abstract（参考訳）: 古典的エキスパート問題では、$\Phi$-regretは学習者の総損失と、最良のアクション変換を$\phi \in \Phi$に適用することで達成される損失のギャップを測定する。 Lu et al , [2025] による最近の研究は、コンパレータ $\phi$ に対する後悔は、(ほとんど)外部、内部、スワップ後悔のような標準的な後悔の概念に対して最適な境界を復元し補間する、ある空間ベースの複雑性尺度に依存する適応アルゴリズムを導入している。 本研究では,Lu et al ,[2025] と比較してはるかに単純なアルゴリズムを用いて,より優れたコンパレータ適応型$\Phi$-regretバウンドを実現するための一般的なアイデアを提案する。 具体的には、可能なすべてのバイナリ変換に対する事前分布を発見し、これらの変換に対する事前依存の後悔を達成するのに十分であることを示す。 そこで本研究では,Farina et al , [2022] の Kernelized MWU アルゴリズムの既知変種を複数コピー以上学習し,第2のアルゴリズムは BM 減算の既知変種を複数コピー以上学習する,という,具体的で効率的な2つのアルゴリズムを提案する。 我々の手法のパワーとLu et al に対する優位性をさらに示すために、単純さと良質な後悔境界に加えて、我々の第2のアプローチがゲーム設定にまで拡張され、一般化された適応収束率を1組の一般ゲームに対して$\Phi$-equilibriaに拡張できることも示している。 相関平衡の特別な場合に指定された場合、我々の境界は、Anagnostides et al , [2022a,b] から既存のものよりも向上する。

関連論文リスト

• Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learning [13.429541377715296]
  無限水平割引線形マルコフ決定過程において, 速度-最適後悔保証を実現するための計算効率のよいアルゴリズムを提案する。 正規化された近似的動的プログラミングスキームと組み合わせると、結果のアルゴリズムは、$tildemathcalO (sqrtd3 (1 - gamma)- 7 / 2 T)$, $T$ はサンプル遷移の総数、$gamma in (0,1)$ は割引係数、$d$ は特徴次元を後悔する。
  論文  参考訳（メタデータ） (2025-02-19T17:32:35Z)
• Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization [55.81991984375959]
  本研究では、以下の簡単な観察を通して、個別化されたプライバシ会計を解析する新しい手法を提案する。 我々は、分解可能な部分モジュラーおよびセットアルゴリズム被覆を含む、プライベート最適化問題に対するいくつかの改良されたアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-05-28T19:02:30Z)
• Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits [12.674929126684528]
  我々は、プレイヤーがPアクションの中から d 個の基本アイテムを含む集合のパワーセットから選択する半帯域の問題に対処する。 提案手法は半帯域フィードバックを効果的に活用し,帯域フィードバックアプローチより優れていることを示す。
  論文  参考訳（メタデータ） (2024-02-23T08:07:54Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。 本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。 我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
  論文  参考訳（メタデータ） (2023-10-02T08:15:52Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)
• Projection-free Adaptive Regret with Membership Oracles [31.422532403048738]
  ほとんどの反復アルゴリズムは凸集合への射影の計算を必要とし、計算コストがかかる。 GK22による最近の研究は、フランク・ウルフのアプローチに基づく射影自由アルゴリズムによる準線形適応的後悔の保証を与えた。 我々はMhammedi22にインスパイアされた異なる手法に基づくプロジェクションフリーなアルゴリズムを提案し、プロジェクションをセットメンバーシップ計算で置き換える。
  論文  参考訳（メタデータ） (2022-11-22T23:53:06Z)
• Planning and Learning with Adaptive Lookahead [74.39132848733847]
  ポリシーイテレーション(PI)アルゴリズムは、欲求の一段階の改善と政策評価を交互に行う。 近年の文献では、複数段階のルックアヘッドポリシーの改善が、イテレーション毎の複雑さの増加を犠牲にして、よりコンバージェンス率の向上につながることが示されている。 本研究では,多段階の地平線を状態と推定値の関数として動的に適応する手法を初めて提案する。
  論文  参考訳（メタデータ） (2022-01-28T20:26:55Z)
• 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)
• BiAdam: Fast Adaptive Bilevel Optimization Methods [104.96004056928474]
  バイレベル最適化は多くの応用のために機械学習への関心が高まっている。 制約付き最適化と制約なし最適化の両方に有用な分析フレームワークを提供する。
  論文  参考訳（メタデータ） (2021-06-21T20:16:40Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。 我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
  論文  参考訳（メタデータ） (2021-03-04T19:01:20Z)
• Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation [44.374427255708135]
  線形関数近似を用いた無限水平平均逆設定でマルコフ決定過程を学習するための新しいアルゴリズムを開発した。 まず,最適$widetildeO(sqrtT)$ regretの計算非効率アルゴリズムを提案する。 次に,逆線形包帯から着想を得て,$widetildeO(sqrtT)$ regretのアルゴリズムを新たに開発した。
  論文  参考訳（メタデータ） (2020-07-23T08:23:44Z)

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

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