mlsanityData to 7 Oct 2026

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

arXiv 2402.11835 ↗First posted 19 Feb 2024cs.LG cs.GT cs.MAcited by 0

Not on the map. Why?

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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 19 of its 45 references that are in the map. First posted on arXiv 19 Feb 2024.

Builds on

19 of 45 references.

References · 19

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
  3. 2016OpenAI Gymcited by 1,684
  4. 2017Rainbow: Combining Improvements in Deep Reinforcement Learningcited by 774
  5. 2015Dueling Network Architectures for Deep Reinforcement Learningcited by 769
  6. 2017A Distributional Perspective on Reinforcement Learningcited by 743
  7. 2019OpenSpiel: A Framework for Reinforcement Learning in Gamescited by 180
  8. 2020Combining Deep Reinforcement Learning and Search for Imperfect-Information Gamescited by 110
  9. 2018Deep Counterfactual Regret Minimizationcited by 102
  10. 2014Solving Large Imperfect Information Games Using CFR+cited by 78
  11. 2017Boltzmann Exploration Done Rightcited by 69
  12. 2018Solving Imperfect-Information Games via Discounted Regret Minimizationcited by 68
7 more
  1. 2022A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Gamescited by 64
  2. 2022Mastering the Game of No-Press Diplomacy via Human-Regularized Reinforcement Learning and Planningcited by 47
  3. 2018Actor-Critic Policy Optimization in Partially Observable Multiagent Environmentscited by 35
  4. 2022ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regretcited by 24
  5. 2020Hindsight and Sequential Rationality of Correlated Playcited by 21
  6. 2020No-Regret Learning Dynamics for Extensive-Form Correlated Equilibriumcited by 19
  7. 2022Equilibrium Finding in Normal-Form Games Via Greedy Regret Minimizationcited by 5

Built on by

Not cited yet.