Easy as ABCs: Unifying Boltzmann Q-Learning and Counterfactual Regret Minimization

Luca D'Amico-Wong, Hugh Zhang, Marc Lanctot, David C. ParkesarXiv 2024 · DOI · arXiv

Abstract

In artificial intelligence, Reinforcement Learning (RL) and Game Theory often operate as distinct paradigms. RL algorithms like Boltzmann Q-Learning (BQL) excel in stationary environments but struggle with nonstationary multi-agent dynamics. Conversely, Counterfactual Regret Minimization (CFR) provides convergence guarantees in games but suffers from extreme inefficiency in simple tasks. We present ABCs (Adaptive Branching through Child stationarity), a "best-of-both-worlds" algorithm that bridges this gap. By adaptively detecting local stationarity, ABCs achieves RL-level efficiency in stable tasks while maintaining the theoretical robustness of CFR in complex games.

Introduction

Modern AI challenges often involve "partially stationary" environments—scenarios containing both stable physical components and volatile, nonstationary agents. Traditional approaches fail to handle this duality: RL methods are often exploitable in games, while game-theoretic methods are too computationally expensive for simple sub-tasks. The core problem is the lack of a general-purpose algorithm that can selectively allocate computational resources based on the nature of the environment.

Methodology: Adaptive Branching through Child Stationarity

The proposed algorithm, ABCs, introduces a novel mechanism called Adaptive Branching. Unlike traditional Markov stationarity, which considers the entire environment, ABCs focuses on Child Stationarity—determining if the rewards and transitions following a specific state-action pair remain stable over time.

The ABCs Update Logic

  1. Stationarity Detection: At each state, ABCs employs a Chi-Squared Goodness-of-Fit test to monitor changes in transitions and rewards.
  2. Dynamic Update Selection:
    • Stationary States: The algorithm performs a "cheap" BQL-style update, exploring only a single trajectory to maximize efficiency.
  3. Nonstationary States: The algorithm "branches," performing an "expensive" CFR-style update (specifically a variant called MAX-CFR) that evaluates all possible actions to prevent exploitation.
  4. Mathematical Unification: The authors demonstrate that BQL and MAX-CFR are mathematically related through the "temperature" of the learning process, allowing ABCs to transition seamlessly between modes.

Experimental Evaluation

ABCs was benchmarked against standard RL and game theory algorithms across several environments:

  • Cartpole: A classic stationary RL task.
  • Kuhn and Leduc Poker: Standard benchmarks for imperfect-information games.
  • Weighted Rock-Paper-Scissors: A nonstationary game designed to challenge standard RL.
  • Stacked Environment: A novel benchmark where an agent plays Cartpole followed by Leduc Poker, testing resource allocation across different environment types.

Key Results

In stationary tasks like Cartpole, ABCs matches the performance and efficiency of BQL, whereas CFR-based methods fail to run effectively due to their exhaustive search requirements.

Performance in the stationary Cartpole environment, where ABCs matches the efficiency of BQL.

In multi-agent and complex environments, ABCs demonstrates its robustness. In the Stacked Environment, it was the only algorithm capable of solving both the stationary (Cartpole) and nonstationary (Poker) components efficiently. It successfully identifies when to "sample" and when to "branch."

Performance across Weighted RPS, Leduc Poker, and the Stacked Environment.

Discussion and Future Work

While ABCs provides a powerful theoretical and practical bridge, it currently relies on a stationarity detector that, while effective, is not perfect. Future work includes scaling ABCs to high-dimensional state spaces using deep neural networks and establishing formal convergence rate bounds. By pruning the search tree in stationary regions, ABCs avoids the exponential slowdown of standard CFR, paving the way for more efficient general-purpose AI agents.

Summary updated

Abstract

We propose ABCs (Adaptive Branching through Child stationarity), a best-of-both-worlds algorithm combining Boltzmann Q-learning (BQL), a classic reinforcement learning algorithm for single-agent domains, and counterfactual regret minimization (CFR), a central algorithm for learning in multi-agent domains. ABCs adaptively chooses what fraction of the environment to explore each iteration by measuring the stationarity of the environment's reward and transition dynamics. In Markov decision processes, ABCs converges to the optimal policy with at most an O(A) factor slowdown compared to BQL, where A is the number of actions in the environment. In two-player zero-sum games, ABCs is guaranteed to converge to a Nash equilibrium (assuming access to a perfect oracle for detecting stationarity), while BQL has no such guarantees. Empirically, ABCs demonstrates strong performance when benchmarked across environments drawn from the OpenSpiel game library and OpenAI Gym and exceeds all prior methods in environments which are neither fully stationary nor fully nonstationary.
BibTeX
@misc{damicowong2024easy,
  author = {Luca D'Amico-Wong and Hugh Zhang and Marc Lanctot and David C. Parkes},
  title = {{Easy as ABCs: Unifying Boltzmann Q-Learning and Counterfactual Regret Minimization}},
  year = {2024},
  eprint = {2402.11835},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2402.11835},
}
Figure