Easy as ABCs: Unifying Boltzmann Q-Learning and Counterfactual Regret Minimization
This work addresses the challenge of adaptive exploration in reinforcement learning for both single-agent and multi-agent settings, representing an incremental advancement by hybridizing existing methods.
The authors tackled the problem of unifying single-agent and multi-agent reinforcement learning by proposing ABCs, an algorithm that adaptively combines Boltzmann Q-learning and counterfactual regret minimization, achieving convergence to optimal policies in Markov decision processes with an O(A) slowdown and to Nash equilibria in two-player zero-sum games, while empirically outperforming prior methods in non-stationary environments.
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.