論文の概要: Minimizing Weighted Counterfactual Regret with Optimistic Online Mirror Descent

• arxiv url: http://arxiv.org/abs/2404.13891v2
• Date: Tue, 14 May 2024 09:16:46 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-15 18:42:17.822696
• Title: Minimizing Weighted Counterfactual Regret with Optimistic Online Mirror Descent
• Title（参考訳）: 最適オンラインミラーダイスによる重み付き対実レグレストの最小化
• Authors: Hang Xu, Kai Li, Bingyun Liu, Haobo Fu, Qiang Fu, Junliang Xing, Jian Cheng,
• Abstract要約: 本研究は,楽観的オンラインミラードライザー(OMD)による重み付き反事実的後悔の最小化を探求する。 PCFR+とDiscounted CFR(DCFR)を原則的に統合し、支配的な作用の負の効果を迅速に緩和する。 PDCFR+は不完全情報ゲームにおいて高速収束を示す実験結果が得られた。
• 参考スコア（独自算出の注目度）: 44.080852682765276
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Counterfactual regret minimization (CFR) is a family of algorithms for effectively solving imperfect-information games. It decomposes the total regret into counterfactual regrets, utilizing local regret minimization algorithms, such as Regret Matching (RM) or RM+, to minimize them. Recent research establishes a connection between Online Mirror Descent (OMD) and RM+, paving the way for an optimistic variant PRM+ and its extension PCFR+. However, PCFR+ assigns uniform weights for each iteration when determining regrets, leading to substantial regrets when facing dominated actions. This work explores minimizing weighted counterfactual regret with optimistic OMD, resulting in a novel CFR variant PDCFR+. It integrates PCFR+ and Discounted CFR (DCFR) in a principled manner, swiftly mitigating negative effects of dominated actions and consistently leveraging predictions to accelerate convergence. Theoretical analyses prove that PDCFR+ converges to a Nash equilibrium, particularly under distinct weighting schemes for regrets and average strategies. Experimental results demonstrate PDCFR+'s fast convergence in common imperfect-information games. The code is available at https://github.com/rpSebastian/PDCFRPlus.
• Abstract（参考訳）: 反事実的後悔の最小化(英: Counterfactual regret minimization, CFR)は、不完全情報ゲーム(英語版)を効果的に解くアルゴリズムの一群である。 これは、Regret Matching (RM) や RM+ などの局所的後悔最小化アルゴリズムを利用して、全後悔を偽りの後悔に分解する。 近年の研究では、オンラインミラー蛍光(OMD)とRM+の関係を確立し、楽観的なPRM+とその拡張PCFR+への道を開いた。 しかし、PCFR+は、後悔を決定するときに各イテレーションに一様重みを割り当て、支配的な行動に直面した時にかなりの後悔をもたらす。 この研究は、楽観的な OMD による重み付き反事実的後悔の最小化を探求し、その結果、新しい CFR 変種 PDCFR+ が生み出された。 PCFR+ と Discounted CFR (DCFR) を原則的に統合し、支配的な行動の負の効果を迅速に緩和し、収束を加速する予測を一貫して活用する。 理論的解析により、PDCFR+はナッシュ平衡に収束し、特に後悔と平均戦略の異なる重み付けスキームの下にあることが証明された。 PDCFR+は不完全情報ゲームにおいて高速収束を示す実験結果が得られた。 コードはhttps://github.com/rpSebastian/PDCFRPlusで公開されている。

関連論文リスト

• Pure Monte Carlo Counterfactual Regret Minimization [0.0]
  本稿ではCFRに基づくPure CFR(PCFR)と呼ばれる新しいアルゴリズムを提案する。 CFRとFPの組み合わせとして見ることができ、CFRから反実的後悔(値)の概念を継承している。 1つのイテレーションの時間と空間の複雑さを著しく減らすことができます。
  論文  参考訳（メタデータ） (2023-09-04T09:16:49Z)
• Efficient Last-iterate Convergence Algorithms in Solving Games [20.00785679098103]
  非回帰アルゴリズムは、2プレイヤゼロサム正規形式ゲーム(NFG)およびワイドフォームゲーム(EFG)におけるナッシュ均衡の学習に人気がある。 近年,MWU に対するリワード変換 (RT) フレームワークが提案されている。 RTアルゴリズムのボトルネックは凸凹最適化問題(SCCP)の解法であることを示す。
  論文  参考訳（メタデータ） (2023-08-22T07:59:49Z)
• ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regret [97.73233271730616]
  超大型ゲームにおけるナッシュ均衡の近似手法 : ニューラルネットワークを用いて近似最適ポリシー(戦略)を学習する DREAMは,モンテカルロCFR(MCCFR)から受け継がれた重要なサンプリング項により,極めて高いばらつきを有すると推定された後悔のターゲット上で,ニューラルネットワークを訓練する。 ESCHERの深層学習バージョンは、DREAMとニューラル・フィクション・セルフプレイ(NFSP)の先行状態よりも優れており、ゲームサイズが大きくなるにつれて、その違いは劇的になる。
  論文  参考訳（メタデータ） (2022-06-08T18:43:45Z)
• Equivalence Analysis between Counterfactual Regret Minimization and Online Mirror Descent [67.60077332154853]
  反実的回帰最小化(英: Counterfactual Regret Minimization, CFR)は、局所的反実的後悔を最小化することにより、全遺を最小化する後悔最小化アルゴリズムである。 FTRL(Follow-the-Regularized-Lead)アルゴリズムとOMD(Online Mirror Descent)アルゴリズムは,オンライン凸最適化における最小化アルゴリズムである。 本稿では,CFR と Regret Matching+ の CFR が FTRL および OMD の特別な形式であることを証明し,CFR を解析・拡張する新しい方法を提案する。
  論文  参考訳（メタデータ） (2021-10-11T02:12:25Z)
• Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
  逐次ゲームにおける楽観的アルゴリズムの最後の点収束について検討する。 これらのアルゴリズムはいずれも最終点収束を楽しみ、そのいくつかは指数関数的に高速に収束する。
  論文  参考訳（メタデータ） (2021-06-27T22:02:26Z)
• Model-free Neural Counterfactual Regret Minimization with Bootstrap Learning [10.816436463322237]
  現在のCFRアルゴリズムは、累積的後悔をニューラルネットワークで近似する必要がある。 新しいCFR変種であるRecursive CFRが提案され、Recursive Substitute Values (RSVs) によって累積的後悔が回復される。 新しい再帰的CFRはナッシュ平衡に収束することが証明されている。 実験の結果、新しいアルゴリズムは最先端のニューラルCFRアルゴリズムと一致できるが、トレーニングのオーバーヘッドは少ないことがわかった。
  論文  参考訳（メタデータ） (2020-12-03T12:26:50Z)
• Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent [119.5481797273995]
  FTRL (Follow-the-regularized-leader) とオンラインミラー降下 (OMD) は、オンライン凸最適化における最も一般的な後悔の最小化手法である。 RMとRM+はFTRLとOMDをそれぞれ実行し、ブラックウェルのアプローチ性ゲームにおいて、ハーフスペースを常に強制的に選択するアルゴリズムであることを示す。 18の共通ゼロサムワイドフォームベンチマークゲームを対象とした実験では,予測的RM+と反ファクト的後悔の最小化が,最速のアルゴリズムよりもはるかに高速に収束することを示した。
  論文  参考訳（メタデータ） (2020-07-28T16:49:55Z)
• Stochastic Regret Minimization in Extensive-Form Games [109.43344748069933]
  Monte-Carlo counterfactual regret minimization (MCCFR) は、完全な木には大きすぎるシーケンシャルゲームを解くための最先端のアルゴリズムである。 後悔の最小化手法を開発するための新しい枠組みを開発する。 MCCFRよりも優れた方法がいくつかある3つのゲームについて広範な実験を行った。
  論文  参考訳（メタデータ） (2020-02-19T23:05:41Z)

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

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