論文の概要: 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 22:09:11.00492
- 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: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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(これらの構造は他のベンチマークゲームよりも非対称な意味で)の先行アルゴリズムを著しく上回り、全てのベンチマークゲームにおいてスムーズな収束挙動を連続的に実行する分散関数を同定する。
関連論文リスト
- Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic Shuffle [53.239242017802056]
強化学習(Reinforcement Learning, RL)は、マルチモーダル大言語モデル(MLLM)の推論能力を高めるための効果的なポストトレーニングパラダイムとして登場した。
しかしながら、現在のRLパイプラインは、アドバンテージ・コラプシング(Advantage Collapsing)とロールアウト・サイレンシング(Rollout Silencing)という2つの未解決の問題によって、トレーニングの非効率に悩まされることが多い。
軌道サンプリングとバッチ合成を動的に再構成することにより、RLの微調整効率を向上する、シンプルだが原則化されたフレームワークであるShuffle-R1を提案する。
論文 参考訳(メタデータ) (2025-08-07T17:53:47Z) - Logarithmic Regret for Online KL-Regularized Reinforcement Learning [51.113248212150964]
KL正規化は、大規模言語モデルにおけるRL微調整の効率向上に重要な役割を果たしている。
経験的優位性にもかかわらず、KL-正則化RLと標準RLの理論的相違はほとんど未探索のままである。
楽観的なKL正規化オンライン文脈帯域幅アルゴリズムを提案し,その後悔の新たな分析法を提案する。
論文 参考訳(メタデータ) (2025-02-11T11:11:05Z) - Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
機械学習の幅広い問題にまたがる正規化誤差フィードバックアルゴリズムに対する収束の最初の証明を提供する。
提案手法では,許容可能なステップサイズが大きくなったため,新しい正規化エラーフィードバックアルゴリズムは,各種タスクにおける非正規化エラーよりも優れていた。
論文 参考訳(メタデータ) (2024-10-22T10:19:27Z) - More Benefits of Being Distributional: Second-Order Bounds for
Reinforcement Learning [58.626683114119906]
本研究では,分散強化学習(DistRL)がオンラインとオフラインのRLの2次境界を得ることができることを示す。
我々の結果は、低ランク MDP とオフライン RL に対する最初の2階境界である。
論文 参考訳(メタデータ) (2024-02-11T13:25:53Z) - 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) - Distributional Reinforcement Learning with Dual Expectile-Quantile Regression [51.87411935256015]
分布RLに対する量子レグレッションアプローチは、任意の戻り分布を柔軟かつ効果的に学習する方法を提供する。
我々は,分布推定が消失することを示し,推定分布が急速に平均に崩壊することを実証的に観察した。
我々は,$L$の学習効率に感化され,効率のよい学習方法として,返却分布の期待値と量子値を共同で学習することを提案する。
論文 参考訳(メタデータ) (2023-05-26T12:30:05Z) - How Does Return Distribution in Distributional Reinforcement Learning Help Optimization? [10.149055921090572]
ニューラルネットワークZ-Iteration(Neural FZI)フレームワークにおける分布RLの最適化の利点について検討する。
その結果, 分布RLは良好な滑らかさ特性を有し, 安定な勾配を享受できることが示唆された。
本研究は,分布RLアルゴリズムの帰属分布が最適化にどう役立つかを明らかにする。
論文 参考訳(メタデータ) (2022-09-29T02:18:31Z) - 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) - The Benefits of Being Categorical Distributional: Uncertainty-aware
Regularized Exploration in Reinforcement Learning [18.525166928667876]
分布RLのポテンシャル優位性は、回帰密度関数分解法を適用して導出した分布整合正則化に帰着する。
分布RLコンテキストにおけるこの探索されていない正規化は、期待によらず、追加の戻り分布情報を取得することを目的としている。
実験は、古典的RLに対する経験的利益に対する分布RLにおけるこの不確実性を考慮した正規化の重要性を裏付ける。
論文 参考訳(メタデータ) (2021-10-07T03:14:46Z) - 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) - Forward and inverse reinforcement learning sharing network weights and
hyperparameters [3.705785916791345]
ERILは、エントロピー規則化マルコフ決定プロセスの枠組みの下で、前方および逆強化学習(RL)を組み合わせる。
前部RLステップは、逆RLステップによって推定される逆KLを最小化する。
逆KL分岐の最小化は最適ポリシーの発見と等価であることを示す。
論文 参考訳(メタデータ) (2020-08-17T13:12:44Z) - Towards Tractable Optimism in Model-Based Reinforcement Learning [37.51073590932658]
成功させるためには、楽観的なRLアルゴリズムは真の値関数(最適化)を過大に見積もる必要があるが、不正確な(推定誤差)ほどではない。
我々は,これらのスケーラブルな楽観的モデルベースアルゴリズムを,トラクタブルノイズ拡張MDPの解法として再解釈する。
この誤差が低減された場合、楽観的なモデルベースRLアルゴリズムは、連続制御問題における最先端性能と一致することを示す。
論文 参考訳(メタデータ) (2020-06-21T20:53:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。