論文の概要: Equivalence Analysis between Counterfactual Regret Minimization and Online Mirror Descent

• arxiv url: http://arxiv.org/abs/2110.04961v1
• Date: Mon, 11 Oct 2021 02:12:25 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-12 18:58:16.082674
• Title: Equivalence Analysis between Counterfactual Regret Minimization and Online Mirror Descent
• Title（参考訳）: 対実的レグレスト最小化とオンラインミラーディフレッシュの等価性解析
• Authors: Weiming Liu, Huacong Jiang, Bin Li, Houqiang Li
• Abstract要約: 反実的回帰最小化(英: Counterfactual Regret Minimization, CFR)は、局所的反実的後悔を最小化することにより、全遺を最小化する後悔最小化アルゴリズムである。 FTRL(Follow-the-Regularized-Lead)アルゴリズムとOMD(Online Mirror Descent)アルゴリズムは,オンライン凸最適化における最小化アルゴリズムである。 本稿では,CFR と Regret Matching+ の CFR が FTRL および OMD の特別な形式であることを証明し,CFR を解析・拡張する新しい方法を提案する。
• 参考スコア（独自算出の注目度）: 67.60077332154853
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Counterfactual Regret Minimization (CFR) is a kind of regret minimization algorithm that minimizes the total regret by minimizing the local counterfactual regrets. CFRs have a fast convergence rate in practice and they have been widely used for solving large-scale imperfect-information Extensive-form games (EFGs). However, due to their locality, CFRs are difficult to analyze and extend. Follow-the-Regularized-Lead (FTRL) and Online Mirror Descent (OMD) algorithms are regret minimization algorithms in Online Convex Optimization. They are mathematically elegant but less practical in solving EFGs. In this paper, we provide a new way to analyze and extend CFRs, by proving that CFR with Regret Matching and CFR with Regret Matching+ are special forms of FTRL and OMD, respectively. With these equivalences, two new algorithms, which can be considered as the extensions of vanilla CFR and CFR+, are deduced from the perspective of FTRL and OMD. In these two variants, maintaining the local counterfactual regrets is not necessary anymore. The experiments show that the two variants converge faster than vanilla CFR and CFR+ in some EFGs.
• Abstract（参考訳）: 反実的回帰最小化(英: Counterfactual Regret Minimization, CFR)は、局所的反実的後悔を最小化することにより、全遺を最小化する後悔最小化アルゴリズムの一種である。 CFRは実際に高速収束速度を持ち、大規模な不完全情報集約型ゲーム(EFG)の解決に広く利用されている。 しかし、その局所性のため、CFRの分析と拡張は困難である。 FTRL(Follow-the-Regularized-Lead)アルゴリズムとOMD(Online Mirror Descent)アルゴリズムは,オンライン凸最適化における最小化アルゴリズムである。 数学的にはエレガントだが、EFGを解くには実用的ではない。 本稿では,CFR と Regret Matching+ の CFR が FTRL と OMD の特殊形式であることを証明し,CFR を解析・拡張する新しい方法を提案する。 これらの等価性により、FTRLとOMDの観点から、バニラCFRとCFR+の拡張と見なせる2つの新しいアルゴリズムが導出される。 この2つの変種では、地元の反事実的後悔の維持はもはや不要である。 実験により、2つの変種はいくつかのEFGにおいてバニラCFRとCFR+よりも早く収束することが示された。

関連論文リスト

• Minimizing Weighted Counterfactual Regret with Optimistic Online Mirror Descent [44.080852682765276]
  本研究は,楽観的オンラインミラードライザー(OMD)による重み付き反事実的後悔の最小化を探求する。 PCFR+とDiscounted CFR(DCFR)を原則的に統合し、支配的な作用の負の効果を迅速に緩和する。 PDCFR+は不完全情報ゲームにおいて高速収束を示す実験結果が得られた。
  論文  参考訳（メタデータ） (2024-04-22T05:37:22Z)
• Efficient Last-iterate Convergence Algorithms in Solving Games [20.00785679098103]
  非回帰アルゴリズムは、2プレイヤゼロサム正規形式ゲーム(NFG)およびワイドフォームゲーム(EFG)におけるナッシュ均衡の学習に人気がある。 近年,MWU に対するリワード変換 (RT) フレームワークが提案されている。 RTアルゴリズムのボトルネックは凸凹最適化問題(SCCP)の解法であることを示す。
  論文  参考訳（メタデータ） (2023-08-22T07:59:49Z)
• Adaptive Federated Minimax Optimization with Lower Complexities [82.51223883622552]
  本稿では,これらのミニマックス問題の解法として,適応最小最適化アルゴリズム(AdaFGDA)を提案する。 運動量に基づく還元および局所SGD技術を構築し、様々な適応学習率を柔軟に組み込む。
  論文  参考訳（メタデータ） (2022-11-14T12:32:18Z)
• Large-scale Optimization of Partial AUC in a Range of False Positive Rates [51.12047280149546]
  ROC曲線 (AUC) の下の領域は、機械学習において最も広く使われている分類モデルのパフォーマンス指標の1つである。 近年の封筒平滑化技術に基づく効率的な近似勾配降下法を開発した。 提案アルゴリズムは,効率のよい解法を欠くランク付けされた範囲損失の和を最小化するためにも利用できる。
  論文  参考訳（メタデータ） (2022-03-03T03:46:18Z)
• NNCFR: Minimize Counterfactual Regret with Neural Networks [4.418221583366099]
  本稿では, textitDeep CFRの改良版である textitNeural Network Counterfactual Regret Minimization (NNCFR) を紹介する。 textitNNCFRは、TextitDeep CFRよりも早く収束し、より安定して動作する。
  論文  参考訳（メタデータ） (2021-05-26T04:58:36Z)
• 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)

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

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