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

arXiv: https://arxiv.org/abs/2402.11835 · HTML: https://mlsanity.com/paper/2402.11835/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods.
- Builds on 19 of its 45 references that are in the map.
- First posted on arXiv 19 Feb 2024.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

## Builds on (most cited first, 19 of 19)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [Rainbow: Combining Improvements in Deep Reinforcement Learning](https://mlsanity.com/paper/1710.02298/) (2017)
- [Dueling Network Architectures for Deep Reinforcement Learning](https://mlsanity.com/paper/1511.06581/) (2015)
- [A Distributional Perspective on Reinforcement Learning](https://mlsanity.com/paper/1707.06887/) (2017)
- [OpenSpiel: A Framework for Reinforcement Learning in Games](https://mlsanity.com/paper/1908.09453/) (2019)
- [Combining Deep Reinforcement Learning and Search for Imperfect-Information Games](https://mlsanity.com/paper/2007.13544/) (2020)
- [Deep Counterfactual Regret Minimization](https://mlsanity.com/paper/1811.00164/) (2018)
- [Solving Large Imperfect Information Games Using CFR+](https://mlsanity.com/paper/1407.5042/) (2014)
- [Boltzmann Exploration Done Right](https://mlsanity.com/paper/1705.10257/) (2017)
- [Solving Imperfect-Information Games via Discounted Regret Minimization](https://mlsanity.com/paper/1809.04040/) (2018)
- [A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Games](https://mlsanity.com/paper/2206.05825/) (2022)
- [Mastering the Game of No-Press Diplomacy via Human-Regularized Reinforcement Learning and Planning](https://mlsanity.com/paper/2210.05492/) (2022)
- [Actor-Critic Policy Optimization in Partially Observable Multiagent Environments](https://mlsanity.com/paper/1810.09026/) (2018)
- [ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regret](https://mlsanity.com/paper/2206.04122/) (2022)
- [Hindsight and Sequential Rationality of Correlated Play](https://mlsanity.com/paper/2012.05874/) (2020)
- [No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium](https://mlsanity.com/paper/2004.00603/) (2020)
- [Equilibrium Finding in Normal-Form Games Via Greedy Regret Minimization](https://mlsanity.com/paper/2204.04826/) (2022)

## Abstract (arXiv)

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.