Minimizing Weighted Counterfactual Regret with Optimistic Online Mirror Descent

• URL: http://arxiv.org/abs/2404.13891v2
• Date: Tue, 14 May 2024 09:16:46 GMT
• Title: Minimizing Weighted Counterfactual Regret with Optimistic Online Mirror Descent
• Authors: Hang Xu, Kai Li, Bingyun Liu, Haobo Fu, Qiang Fu, Junliang Xing, Jian Cheng,
• Abstract summary: 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.
• Score: 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.

Related papers

• 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)
• ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regret [97.73233271730616]
  Recent techniques for approximating Nash equilibria in very large games leverage neural networks to learn approximately optimal policies (strategies) DREAM, the only current CFR-based neural method that is model free and therefore scalable to very large games, trains a neural network on an estimated regret target that can have extremely high variance due to an importance sampling term inherited from Monte Carlo CFR (MCCFR) We show that a deep learning version of ESCHER outperforms the prior state of the art -- DREAM and neural fictitious self play (NFSP) -- and the difference becomes dramatic as game size increases.
  arXiv  Detail & Related papers  (2022-06-08T18:43:45Z)
• Equivalence Analysis between Counterfactual Regret Minimization and Online Mirror Descent [67.60077332154853]
  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.
  arXiv  Detail & Related papers  (2021-10-11T02:12:25Z)
• Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
  We study last-iterate convergence of optimistic algorithms in sequential games. We show that all of these algorithms enjoy last-iterate convergence, with some of them even converging exponentially fast.
  arXiv  Detail & Related papers  (2021-06-27T22:02:26Z)
• 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)
• The Advantage Regret-Matching Actor-Critic [31.475994100183794]
  We propose a model-free reinforcement learning algorithm for no-regret learning. We use retrospective value estimates to predict conditional advantages which, combined with regret matching, produce a new policy. In the single-agent setting, ARMAC shows an interesting form of exploration by keeping past policies intact.
  arXiv  Detail & Related papers  (2020-08-27T16:30:17Z)
• 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.