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.

提出了 ABCs（Adaptive Branching through Child stationarity）算法，通过结合 Boltzmann Q-learning（BQL）和 counterfactual regret minimization（CFR）两种算法，实现了在单一智能体和多智能体领域的自适应分支，该算法通过测量环境的奖励和转移动力学的稳定性，在马尔可夫决策过程中，ABCs 收敛到最佳策略，最多比 BQL 慢 O（A）个因子，其中 A 是环境中的动作数量，在两人零和游戏中，ABCs 保证收敛到纳什均衡（假设可以访问用于检测稳定性的完美 Oracle），而 BQL 没有这样的保证，在 OpenSpiel 游戏库和 OpenAI Gym 中基准测试时，ABCs 在既非完全稳定也非完全非稳定的环境中表现出了强大的性能，超过了所有先前的方法。