Combining Counterfactual Regret Minimization With Information Gain to Solve Extensive Games With Unknown Environments

Chen Qiu, Xuan Wang, Tenghao Ma, Wenjun Yuan, Jiajia ZhangInternational Journal of Intelligent Systems 2024 · DOI

TL;DR

This paper introduces VCFR, a novel algorithm that combines Counterfactual Regret Minimization (CFR) with information gain to efficiently find Nash Equilibria (NE) in complex games with unknown environments. By using a Bayesian Neural Network (BNN) to model the environment and incorporating information gain as an intrinsic reward, VCFR significantly reduces the number of interactions needed to achieve accurate results compared to existing methods.

What Problem Does This Paper Address?

Many real-world decision-making scenarios, such as those in reinforcement learning (RL), involve games with imperfect information where the rules (transition probabilities, rewards) are not fully known. Traditional algorithms like Counterfactual Regret Minimization (CFR) excel at finding Nash Equilibria (NE) in games but require complete knowledge of the environment. Applying CFR to unknown environments is challenging because it necessitates extensive interaction to learn the environment's dynamics, often leading to slow convergence and high variance. Existing methods struggle to balance efficient exploration with accurate NE computation in these uncertain settings.

Methods

The core of the proposed method, VCFR, lies in its hybrid approach:

  • Bayesian Neural Network (BNN) for Environment Modeling: VCFR uses a BNN to model the unknown environment. Unlike standard neural networks, BNNs can represent uncertainty in their predictions by modeling weights as distributions. This allows VCFR to capture the probabilistic nature of the unknown environment and quantify its uncertainty.
  • Information Gain for Exploration: The algorithm leverages "information gain" as a curiosity-driven exploration mechanism. This is quantified using the Kullback-Leibler (KL) divergence between the predicted environment model and the actual environment. This information gain is then incorporated as an intrinsic reward, guiding the agent to explore states that provide the most new information about the environment.
  • Modified CFR with Information Gain: The standard CFR algorithm is adapted by integrating this information gain into the reward signal. This modified reward encourages exploration while still aiming to minimize regret and converge towards a Nash Equilibrium. The resulting average strategy from CFR can then be directly used as the interaction policy for further exploration.

Datasets

The experiments were conducted on standard game theory testbeds:

  • Kuhn poker
  • Leduc poker (specifically, Leduc(4) and Leduc(5) variants, differing in game tree size)

These are well-established games used for evaluating algorithms in imperfect information settings. The paper notes modifications to Leduc Hold'em Poker to introduce uncertain transition probabilities and reward functions, creating the "unknown environment" setting.

Key Insights and Ideas

  • Information Gain as Intrinsic Reward: The paper highlights that information gain, derived from the uncertainty reduction in the environment model, can be effectively used as an intrinsic reward. This reward mechanism directly encourages exploration of uncertain parts of the game.
  • Bridging RL and Game Theory: VCFR demonstrates a promising way to bridge the gap between reinforcement learning (which excels in unknown environments) and game theory (which provides tools for finding optimal strategies like NE).
  • Exploration-Exploitation Synergy: By integrating information gain into the CFR framework, the algorithm achieves a synergistic balance between exploring the unknown environment and exploiting learned information to find an approximate NE.
  • Average Strategy as Interaction Policy: A key innovation is using the average strategy computed by the modified CFR directly as the interaction policy. This allows for more efficient data collection and environment learning.

Key Results

  • Reduced Interactions: VCFR significantly reduces the number of interactions required to find an approximate Nash Equilibrium compared to baselines like PSRLCFR, MCCFR-OS, Naive, and Random. For instance, in Leduc(4), VCFR achieved an exploitability of -0.135 after 20,000 rounds, outperforming PSRLCFR (-0.864).
  • Improved Accuracy: The strategies obtained by VCFR are closer to NE within the same number of interaction rounds.
  • Effective Exploration: The incorporation of information gain demonstrably accelerates strategy convergence and leads to more effective exploration of unknown environments.
  • Scalability: The method shows good performance across different scales of Leduc poker, indicating its generalization capability.

Limitations and Future Work

  • Computational Cost of KL Divergence: The paper acknowledges that computing KL divergence at each round can be computationally intensive. While they explored thresholding to reduce this, the impact was limited. Developing more practical approaches to reduce KL divergence computation time is suggested as a future research direction.
  • Dependence on Game Structure: The authors suggest exploring methods to decrease the approach's dependence on the specific structure of two-player zero-sum games.
  • Extension to Multi-Player Games: Future work could extend the approach to games involving three or more players.

Summary updated

Abstract

Counterfactual regret minimization (CFR) is an effective algorithm for solving extensive‐form games with imperfect information (IIEGs). However, CFR is only allowed to be applied in known environments, where the transition function of the chance player and the reward function of the terminal node in IIEGs are known. In uncertain situations, such as reinforcement learning (RL) problems, CFR is not applicable. Thus, applying CFR in unknown environments is a significant challenge that can also address some difficulties in the real world. Currently, advanced solutions require more interactions with the environment and are limited by large single‐sampling variances to narrow the gap with the real environment. In this paper, we propose a method that combines CFR with information gain to compute the Nash equilibrium (NE) of IIEGs with unknown environments. We use a curiosity‐driven approach to explore unknown environments and minimize the discrepancy between uncertain and real environments. In addition, by incorporating information into the reward, the average strategy calculated by CFR can be directly implemented as the interaction policy with the environment, thereby improving the exploration efficiency of our method in uncertain environments. Through experiments on standard testbeds such as Kuhn poker and Leduc poker, our method significantly reduces the number of interactions with the environment compared to the different baselines and computes a more accurate approximate NE within the same number of interaction rounds.
BibTeX
@article{qiu2024combining,
  author = {Chen Qiu and Xuan Wang and Tenghao Ma and Wenjun Yuan and Jiajia Zhang},
  title = {{Combining Counterfactual Regret Minimization With Information Gain to Solve Extensive Games With Unknown Environments}},
  journal = {International Journal of Intelligent Systems},
  year = {2024},
  doi = {10.1155/int/9482323},
}
Figure