Equivalence Analysis between Counterfactual Regret Minimization and Online Mirror Descent

• URL: http://arxiv.org/abs/2110.04961v1
• Date: Mon, 11 Oct 2021 02:12:25 GMT
• Title: Equivalence Analysis between Counterfactual Regret Minimization and Online Mirror Descent
• Authors: Weiming Liu, Huacong Jiang, Bin Li, Houqiang Li
• Abstract summary: Counterfactual Regret Minimization (CFR) is a regret minimization algorithm that minimizes the total regret by minimizing the local counterfactual regrets. Follow-the-Regularized-Lead (FTRL) and Online Mirror Descent (OMD) algorithms are regret minimization algorithms in Online Convex Optimization. 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.
• Score: 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.

Related papers

• Minimizing Weighted Counterfactual Regret with Optimistic Online Mirror Descent [44.080852682765276]
  This work explores minimizing weighted counterfactual regret with optimistic Online Mirror Descent (OMD) It integrates PCFR+ and Discounted CFR (DCFR) in a principled manner, swiftly mitigating negative effects of dominated actions. Experimental results demonstrate PDCFR+'s fast convergence in common imperfect-information games.
  arXiv  Detail & Related papers  (2024-04-22T05:37:22Z)
• Efficient Last-iterate Convergence Algorithms in Solving Games [20.00785679098103]
  No-regret algorithms are popular for learning Nash equilibrium in two-player zero-sum normal-form games (NFGs) and extensive-form games (EFGs) Recent works propose a Reward Transformation (RT) framework for MWU, which removes the uniqueness condition and achieves competitive performance with OMWU. We show that the bottleneck of RT-based algorithms is the speed of solving convex-concave optimization problems (SCCPs)
  arXiv  Detail & Related papers  (2023-08-22T07:59:49Z)
• Adaptive Federated Minimax Optimization with Lower Complexities [82.51223883622552]
  We propose an efficient adaptive minimax optimization algorithm (i.e., AdaFGDA) to solve these minimax problems. It builds our momentum-based reduced and localSGD techniques, and it flexibly incorporate various adaptive learning rates.
  arXiv  Detail & Related papers  (2022-11-14T12:32:18Z)
• Large-scale Optimization of Partial AUC in a Range of False Positive Rates [51.12047280149546]
  The area under the ROC curve (AUC) is one of the most widely used performance measures for classification models in machine learning. We develop an efficient approximated gradient descent method based on recent practical envelope smoothing technique. Our proposed algorithm can also be used to minimize the sum of some ranked range loss, which also lacks efficient solvers.
  arXiv  Detail & Related papers  (2022-03-03T03:46:18Z)
• NNCFR: Minimize Counterfactual Regret with Neural Networks [4.418221583366099]
  This paper introduces textitNeural Network Counterfactual Regret Minimization (NNCFR), an improved variant of textitDeep CFR. The textitNNCFR converges faster and performs more stable than textitDeep CFR, and outperforms textitDeep CFR with respect to exploitability and head-to-head performance on test games.
  arXiv  Detail & Related papers  (2021-05-26T04:58:36Z)
• Model-free Neural Counterfactual Regret Minimization with Bootstrap Learning [10.816436463322237]
  Current CFR algorithms have to approximate the cumulative regrets with neural networks. A new CFR variant, Recursive CFR, is proposed, in which the cumulative regrets are recovered by Recursive Substitute Values (RSVs) It is proved the new Recursive CFR converges to a Nash equilibrium. Experimental results show that the new algorithm can match the state-of-the-art neural CFR algorithms but with less training overhead.
  arXiv  Detail & Related papers  (2020-12-03T12:26:50Z)
• Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent [119.5481797273995]
  Follow-the-regularized-leader (FTRL) and online mirror descent (OMD) are the most prevalent regret minimizers in online convex optimization. We show that RM and RM+ are the algorithms that result from running FTRL and OMD, respectively, to select the halfspace to force at all times in the underlying Blackwell approachability game. In experiments across 18 common zero-sum extensive-form benchmark games, we show that predictive RM+ coupled with counterfactual regret minimization converges vastly faster than the fastest prior algorithms.
  arXiv  Detail & Related papers  (2020-07-28T16:49:55Z)
• Stochastic Regret Minimization in Extensive-Form Games [109.43344748069933]
  Monte-Carlo counterfactual regret minimization (MCCFR) is the state-of-the-art algorithm for solving sequential games that are too large for full trees. We develop a new framework for developing regret minimization methods. We show extensive experiments on three games, where some variants of our methods outperform MCCFR.
  arXiv  Detail & Related papers  (2020-02-19T23:05:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.