論文の概要: The Power of Perturbation under Sampling in Solving Extensive-Form Games

• arxiv url: http://arxiv.org/abs/2501.16600v1
• Date: Tue, 28 Jan 2025 00:29:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-29 16:40:04.349689
• Title: The Power of Perturbation under Sampling in Solving Extensive-Form Games
• Title（参考訳）: 集中型競技におけるサンプリング時の摂動力
• Authors: Wataru Masaka, Mitsuki Sakamoto, Kenshi Abe, Kaito Ariu, Tuomas Sandholm, Atsushi Iwasaki,
• Abstract要約: 本稿では,不完全な情報形式ゲームにおいて,摂動がFTRL(Follow-the-Regularized-Leader)アルゴリズムをどのように改善するかを検討する。 期待されるペイオフの摂動は、FTRL力学が近似平衡に達することを保証している。 最後に、FTRLは非サンプリングFTRLよりも一貫して優れていることを示す。
• 参考スコア（独自算出の注目度）: 56.013335390600524
• License:
• Abstract: This paper investigates how perturbation does and does not improve the Follow-the-Regularized-Leader (FTRL) algorithm in imperfect-information extensive-form games. Perturbing the expected payoffs guarantees that the FTRL dynamics reach an approximate equilibrium, and proper adjustments of the magnitude of the perturbation lead to a Nash equilibrium (\textit{last-iterate convergence}). This approach is robust even when payoffs are estimated using sampling -- as is the case for large games -- while the optimistic approach often becomes unstable. Building upon those insights, we first develop a general framework for perturbed FTRL algorithms under \textit{sampling}. We then empirically show that in the last-iterate sense, the perturbed FTRL consistently outperforms the non-perturbed FTRL. We further identify a divergence function that reduces the variance of the estimates for perturbed payoffs, with which it significantly outperforms the prior algorithms on Leduc poker (whose structure is more asymmetric in a sense than that of the other benchmark games) and consistently performs smooth convergence behavior on all the benchmark games.
• Abstract（参考訳）: 本稿では,不完全な情報形式ゲームにおいて,摂動がFTRL(Follow-the-Regularized-Leader)アルゴリズムをどのように改善するかを検討する。 期待されるペイオフの摂動は、FTRL力学が近似平衡に達することを保証し、摂動の大きさの適切な調整はナッシュ平衡(\textit{last-iterate convergence})につながる。 大規模なゲームの場合のように、サンプリングを使ってペイオフを見積もる場合でも、このアプローチは堅牢だが、楽観的なアプローチは不安定になることが多い。 これらの知見に基づいて、まず、textit{sampling} の下で摂動型 FTRL アルゴリズムの一般的なフレームワークを開発する。 最後に, 摂動FTRLが非摂動FTRLより常に優れていることが実証的に示される。 さらに、摂動ペイオフの推定値のばらつきを低減し、Leduc poker(これらの構造は他のベンチマークゲームよりも非対称な意味で)の先行アルゴリズムを著しく上回り、全てのベンチマークゲームにおいてスムーズな収束挙動を連続的に実行する分散関数を同定する。

関連論文リスト

• Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
  機械学習の幅広い問題にまたがる正規化誤差フィードバックアルゴリズムに対する収束の最初の証明を提供する。 提案手法では,許容可能なステップサイズが大きくなったため,新しい正規化エラーフィードバックアルゴリズムは,各種タスクにおける非正規化エラーよりも優れていた。
  論文  参考訳（メタデータ） (2024-10-22T10:19:27Z)
• Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximation [62.969796245827006]
  Delayed-PSVI は楽観的な値に基づくアルゴリズムであり、後続サンプリングによる雑音摂動により値関数空間を探索する。 我々のアルゴリズムは、未知の遅延が存在する場合に、$widetildeO(sqrtd3H3 T + d2H2 E[tau]$最悪の後悔を実現する。 遅延LPSVIのための勾配に基づく近似サンプリングスキームをLangevin動的に組み込んだ。
  論文  参考訳（メタデータ） (2023-10-29T06:12:43Z)
• Distributionally Robust Optimization with Bias and Variance Reduction [9.341215359733601]
  勾配に基づくアルゴリズムであるProspectは、スムーズな正規化損失に対する線形収束を享受していることを示す。 また、勾配法のようなベースラインよりも2～3$times$早く収束できることも示している。
  論文  参考訳（メタデータ） (2023-10-21T00:03:54Z)
• Game-Theoretic Robust Reinforcement Learning Handles Temporally-Coupled Perturbations [98.5802673062712]
  我々は時間的に結合した摂動を導入し、既存の頑健な強化学習手法に挑戦する。 本稿では、時間的に結合したロバストなRL問題を部分的に観測可能な2プレイヤーゼロサムゲームとして扱う新しいゲーム理論であるGRADを提案する。
  論文  参考訳（メタデータ） (2023-07-22T12:10:04Z)
• Mutation-Driven Follow the Regularized Leader for Last-Iterate Convergence in Zero-Sum Games [8.347058637480506]
  正規化リーダ(FTRL)のフォローは、戦略を時分割する際にナッシュ均衡に収束することが保証される。 FTRL(M-FTRL)は,行動確率の摂動に対する突然変異を導入するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-06-18T17:32:07Z)
• Stochastic Training is Not Necessary for Generalization [57.04880404584737]
  勾配降下の暗黙的な正則化(SGD)は、ニューラルネットワークで観測される印象的な一般化の振る舞いに基礎的であると広く信じられている。 本研究では,SGDと同等のCIFAR-10において,非確率的フルバッチトレーニングが強力な性能を発揮することを示す。
  論文  参考訳（メタデータ） (2021-09-29T00:50:00Z)
• Regularization Guarantees Generalization in Bayesian Reinforcement Learning through Algorithmic Stability [48.62272919754204]
  ベイズ RL の一般化を、おそらくほぼ正しい (PAC) フレームワークで研究する。 我々の主な貢献は、正規化を加えることで、最適な政策が適切な意味で安定することを示しています。
  論文  参考訳（メタデータ） (2021-09-24T07:48:34Z)
• Exploring the Training Robustness of Distributional Reinforcement Learning against Noisy State Observations [7.776010676090131]
  エージェントが観察する状態の観察は、測定誤差や敵のノイズを含んでおり、エージェントが最適な行動を取るように誤解したり、訓練中に崩壊することもある。 本稿では,本研究の成果である分散強化学習(RL)のトレーニングロバスト性について検討する。
  論文  参考訳（メタデータ） (2021-09-17T22:37:39Z)
• Towards Tractable Optimism in Model-Based Reinforcement Learning [37.51073590932658]
  成功させるためには、楽観的なRLアルゴリズムは真の値関数(最適化)を過大に見積もる必要があるが、不正確な(推定誤差)ほどではない。 我々は,これらのスケーラブルな楽観的モデルベースアルゴリズムを,トラクタブルノイズ拡張MDPの解法として再解釈する。 この誤差が低減された場合、楽観的なモデルベースRLアルゴリズムは、連続制御問題における最先端性能と一致することを示す。
  論文  参考訳（メタデータ） (2020-06-21T20:53:19Z)

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

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