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

Discovering general algorithms capable of learning in varied environments is a common theme in RL and more generally in machine learning. For example, DQN (Mnih et al., 2015) and its successors (Wang et al., 2016; Bellemare et al., 2017; Hessel et al., 2018) are capable of obtaining human level performance on a test suite of games drawn from the Arcade Learning Environment, and algorithms such as AlphaZero (Silver et al., 2017) attain superhuman performance on perfect information games such as Go, Shogi, and Chess. However, such algorithms still fail on multi-agent imperfect information settings such as Poker (Brown et al., 2020). More recently, several algorithms such as Player of Games (PoG) (Schmid et al., 2021), REBEL (Brown et al., 2020), and MMD (Sokota et al., 2023) have been able to simultaneously achieve reasonable performance on both perfect and imperfect information games. However, unlike ABCs, none of these algorithms adapt to the stationarity of their environment. As such, they can neither guarantee performance comparable to their reinforcement learning counterparts in MDPs nor efficiently allocate resources in environments which are partially stationary, as ABCs is able to do.

Classical single-agent RL typically assumes that the learning environment is a Markov Decision Process (MDP). An MDP is defined via a tuple $(S,A,T,R,\gamma)$. $S$ and $A$ are the set of states and actions, respectively. The state transition function, $T(s^{\prime}\mid s,a)$, defines the probability of transitioning to state $s^{\prime}$ after taking action $a$ at state $s$. $R(r\mid s,a,s^{\prime})$ is the reward function, which specifies the reward for taking action $a$ at state $s$, given that we transition to state $s^{\prime}$. Importantly, in an MDP, both the transition and the reward functions are assumed to be stationary/fixed. $\gamma\in[0,1]$ is the discount factor determining the importance of future rewards relative to immediate rewards. In an episodic MDP, the agent interacts with the environment across each of separate episodes via a policy, which is a function $\pi:S\rightarrow\Delta A$, mapping states to probabilities over valid actions. In a Partially Observable Markov Decision Process (POMDP), the tuple contains an additional element $\mathcal{H}$. In a POMDP, the agent only observes information states $S$ while the true hidden states $\mathcal{H}$ of the world remain unknown. The transition and reward dynamics of the environment follow an MDP over the hidden states $\mathcal{H}$, but the agent’s policy $\pi:S\to\Delta A$ must depend on the observed infostates rather than hidden states. However, since POMDPs still only contain a single agent and fix the transition probabilities over time, they are still stationary environments, and there exist standard methods for reducing POMDPs into MDPs (Shani et al., 2013).

While MDPs and POMDPs model a large class of single-agent environments, the stationarity assumption can easily fail in multi-agent environments. Specifically, from a single agent’s perspective, the transition and reward dynamics are no longer fixed as they now depend on the other agents, who are also learning. To capture these multi-agent environments, we cast our environment as a finite, imperfect information, extensive-form game with perfect recall.

In defining this, we have a set of $M$ players (or agents), and an additional chance player, denoted by $c$, whose moves capture any potential stochasticity in the game. There is a finite set $\mathcal{H}$ of possible histories/hidden states, corresponding to a finite sequence of states encountered and actions taken by all players in the game. Let $h\sqsubseteq h^{\prime}$ denote that $h$ is a prefix of $h^{\prime}$, as sequences. The set of terminal histories, $Z\subseteq\mathcal{H}$, is the set of histories where the game terminates. For each history $h\in\mathcal{H}$, we let $r_{i}(h)$ denote the reward obtained by player $i$ upon reaching history $h$. The total utility in a given episode for player $i$ after reaching terminal history $z\in Z$ is $u_{i}(z)=\sum_{h_{t}\sqsubseteq z}\gamma^{t}r_{i}(h_{t})$, where $h_{t}$ denotes the $t+1$st longest prefix of $z$ (i.e., $t$ indexes a step within an episode). Let $u_{i}(h,h^{\prime})$ denote the total utility for player $i$ when reaching history $h^{\prime}$, starting from history $h$. Many of the guarantees in this paper focus on two-player zero-sum games, which have the additional property that the sum of the utility functions at any $z\in Z$ for the two players is guaranteed to be $0$.

To model imperfect information, we define the set of infostates $S$ as a partition of the possible histories $\mathcal{H}$. Let $S(h)$ denote the information states (abbreviated infostates) corresponding to history $h$. There is a player function $P:S\to\{1,\dots,M\}\cup\{c\}$ that maps infostates to the player whose turn it is to move. Each infostate $s\in S$ is composed of states that are observationally equivalent to the player $P(s)$ whose turn it is to play. As is standard, we assume perfect recall in that players never forget information obtained through prior states and actions (Zinkevich et al., 2008; Brown & Sandholm, 2018; Moravčík et al., 2017; Celli et al., 2020).

Let $\mathcal{A}(s)$ denote the set of possible actions available to player $P(s)$ at infostate $s$. We denote the policy of player $i$ as $\pi_{i}:S\rightarrow\Delta\mathcal{A}$ and let $\pi=\{\pi_{1},\cdots\pi_{N}\}$ denote the joint policy. Let $\mathcal{H}_{\pi}(s)$ denote the distribution of true hidden states corresponding to infostate $s$, assuming all players play according to joint policy $\pi$.

In order to bridge the gap between POMDPs and general extensive-form games, it will be helpful to recast our multi-agent environment into $|M|$ separate single-agent environments. From the perspective of any single agent $i$, the policy of the other agents $\pi_{-i}$ uniquely defines a POMDP which agent $i$ interacts with alone. To construct this POMDP, after player $i$ takes an action, we simulate the play of the other agents according to $\pi_{-i}$ and return the state/rewards corresponding to the point at which it is next $i$’s turn to play. Within these single-agent POMDPs, defined by the joint policy $\pi$, we use $T_{\pi}\left(h^{\prime}\mid h,a\right)$ to denote the probability¹¹1Note that these transition probabilities are only defined for the player whose turn it is to play at history $h$ that $h^{\prime}$ is the next hidden state after player $i$ plays action $a$ under true hidden state $h$. We can similarly define the transition probability to infostate $s^{\prime}$ from hidden state $h$ as $T_{\pi}\left(s^{\prime}\mid h,a\right)=\sum_{h^{\prime}\in\mathcal{H}_{\pi}(s^{\prime})}\mathds{1}\left(S\left(h^{\prime}\right)=s^{\prime}\right)T_{\pi}\left(h^{\prime}\mid h,a\right)$, and the transition probabilities from infostate to infostate as $T_{\pi}\left(s^{\prime}\mid s,a\right)=\mathbb{E}_{h\sim\mathcal{H}_{\pi}(s)}\left[T_{\pi}\left(s^{\prime}\mid h,a\right)\right]$. Analogously, let $R_{\pi}\left(r\mid s,a,s^{\prime}\right)$ denote the probability of obtaining immediate reward $r$ after taking action $a$ at infostate $s$ under joint policy $\pi$ and transitioning to state $s^{\prime}$. For the above transitions to always be well defined, we require that all policies be fully mixed, in that $\pi(a\mid s)>0$ for all valid actions $a$ and all infostates $s$. It is important to note that the $h^{\prime},s^{\prime}$ above do not refer to the next history/infostate seen in the full game but rather the next in the single-agent POMDP of the current player—i.e., the agent who actually takes action $a$.

Boltzmann Q-learning (BQL) is a variant of the standard Q-learning algorithm, where Boltzmann exploration is used as the exploration policy. Formally, we define the value $V$ of a state and the $Q$-value of an action at that state as:

where the $i$ in the definition of $Q^{\pi}(s,a)$ refers to the player who plays at state $s$.

We adapt BQL to the multi-agent setting as follows. At each iteration, BQL first freezes the policies of each agent. It then samples a single trajectory for each agent. These trajectories take the form of $(s,a,r,s^{\prime})$ tuples, recording the reward $r$ and new infostate $s^{\prime}$ observed after taking action $a$ at infostate $s$. Q-values are updated for each $(s,a)$ pair in the trajectory using a temporal difference update $Q(s,a)\leftarrow(1-\alpha)Q(s,a)+\alpha(r+\gamma\max_{a^{\prime}}Q(s^{\prime},a^{\prime}))$, where $\alpha$ denotes the learning rate. These average Q-values are stored, and at the end of each iteration $n$, a new joint policy $\pi^{n+1}(s,a)=\frac{\exp\left(Q(s,a)/\tau\right)}{\sum_{a^{\prime}\in A}\exp\left(Q(s,a^{\prime})/\tau\right)}$ is computed, where $\tau$ is the temperature parameter. While BQL converges to the optimal policy in MDPs and in perfect information games (given a suitable temperature schedule) (Cesa-Bianchi et al., 2017; Singh et al., 2000), it fails to converge to a Nash equilibrium in imperfect-information multi-agent games such as Poker (Brown et al., 2020).

Counterfactual regret minimization (CFR) is a popular method for solving imperfect-information extensive form games and is based on the notion of minimizing counterfactual regrets. The counterfactual value for a given infostate is given by $v_{i}^{\pi}(s)=\sum_{(h,z)\in Z_{s}}\eta_{-i}^{\pi}(h)\eta^{\pi}(h,z)u_{i}(h,z)$. The counterfactual regret for not taking action $a$ at infostate $s$ is then given by $r^{\pi}(s,a)=v_{i}^{\pi_{(s\to a)}}(s)-v_{i}^{\pi}(s)$, where $i=P(s)$ and $\pi_{(s\to a)}$ is identical to policy $\pi$ except action $a$ is always taken at infostate $s$. Notice that because $\eta^{\pi}_{i}(s)=\eta^{\pi}_{i}(h)$ (due to the assumption of perfect recall), the counterfactual values are simply the standard RL value functions normalized by the opponents’ contribution to the probability of reaching $s$; that is, $v_{i}^{\pi}(s)=\frac{V_{i}^{\pi}(s)}{\eta^{\pi}_{-i}(s)}$²²2Intuitively, the counterfactual regret upper bounds how much an agent could possibly “regret” not playing action $a$ at infostate $s$ if she modified her policy to maximize the probability that state $s$ is encountered. As such, the normalization constant excludes player $i$’s probability contribution to reaching $s$ under $\pi$.. This was first pointed out by (Srinivasan et al., 2018). As with multi-agent BQL, at each iteration, we freeze all agents’ policies before traversing the game tree and computing the counterfactual regrets for each $(s,a)$ pair. A new current policy $\pi^{n+1}$ is then computed using a regret minimizer, typically regret matching (Hart & Mas-Colell, 2000) or Hedge (Arora et al., 2012a) on the cumulative regrets $R^{n}(s,a)=\sum_{n}r^{\pi^{n}}(s,a)$, and the process continues. A learning procedure has vanishing regret if $\lim_{N\rightarrow\infty}\frac{1}{N}R^{N}(s,a)=0$ for all $s,a$. In two player, zero-sum games, (Zinkevich et al., 2008) prove that CFR has vanishing regret, and by extension, that the average policy converges to a Nash equilibrium of the game. In general-sum games, computing a Nash equilibrium is computationally hard (Daskalakis et al., 2009), but CFR guarantees convergence to a weaker solution concept known as a coarse-correlated equilibrium (Morrill et al., 2021).

External sampling MCCFR (ES-MCCFR) is a popular variant of CFR which uses sampling to get unbiased estimates of the counterfactual regrets without exploring the full game tree (Lanctot et al., 2009). For each player $i$, ES-MCCFR samples a single action for every infostate which players other than $i$ act on, but explores all actions for player $i$. Let $W$ denote the set of terminal histories reached during this sampling process. For any infostate $s$, let $h(s)$ denote the corresponding history that was reached during exploration (there can only be one due to perfect recall). For each visited infostate $s$, the sampled counterfactual regret, $\tilde{r}_{i}(s,a)=\tilde{v}^{\pi_{(s\to a)}}_{i}(s,a)-\tilde{v}^{\pi}_{i}(s,a)=\sum_{z\in W}u_{i}(h,z)(\eta_{i}^{\pi}(h(s^{\prime}),z)-\eta_{i}^{\pi}(h(s),z))$, is added to the cumulative regret, where $s^{\prime}$ is the infostate reached after taking action $a$ at infostate $s$. After this process has been completed for each player, a new joint policy is computed using Hedge on the new cumulative regrets, and the procedure continues. Under Hedge, the joint policy at episode $n+1$ is given by $\pi^{n+1}(s,a)=\frac{e^{R^{n}(s,a)/\tau_{n}}}{\sum_{a^{\prime}\in A(s)}e^{R^{n}(s,a^{\prime})/\tau_{n}}}$, where $\tau_{n}$ is a temperature hyperparameter. As Hedge is invariant to any additive constants in the exponent, we can replace the sampled counterfactual regrets with the sampled counterfactual values, i.e., $\tilde{v}^{\pi}_{i}(s,a)=\sum_{z\in W}u_{i}(z)\cdot\eta_{i}^{\pi}(h(s^{\prime}),z)$, and similarly with the cumulative regrets.

The most important difference between CFR and BQL is in regard to which infostates are updated at each iteration of learning. By default, BQL only performs updates along a single trajectory of encountered infostates (“trajectory based”). In a game of depth $D$, this means that there will be at most $O(D)$ updates per iteration. By contrast, CFR and most of its variants are typically³³3In theory, variants such as OS-MCCFR can learn with $O(D)$ updates per iteration, but the variance of such methods is often too high for practical usage. Other approaches, such as ESCHER (McAleer et al., 2022), have attempted to address this issue by avoiding the use of importance sampling. not trajectory-based learning algorithms because many infostates that are updated are not on the path of play. In particular, CFR (Zinkevich et al., 2008) requires performing counterfactual value updates at every infostate, which can require up to $O(A^{D})$ updates per iteration. While MCCFR reduces this by performing Monte-Carlo updates, variants such as ES-MCCFR still require making an exponential number of updates per iteration.

Despite the differences between BQL and CFR, the two algorithms are intimately linked. (Brown et al., 2019, Lemma 1) first pointed out that the sampled counterfactual values $\tilde{v}_{i}^{\pi}(s,a)$ from ES-MCCFR have an alternative interpretation as Monte-Carlo based estimates of the Q-value $Q^{\pi}(s,a)$. Thus, ES-MCCFR with Hedge has a gradient update that ends up being very similar to BQL, with two exceptions. Firstly, BQL estimates its Q-values by bootstrapping whereas ES-MCCFR uses a Monte-Carlo update and thus updates based on the current policy of all players. Secondly, BQL chooses a policy based on a softmax over the average Q-values, while CFR(Hedge) uses a softmax over cumulative Q-values. As not every action is tested in BQL, the average Q-values may be based on a different number of samples for each action, making it unclear how to convert average Q-values into cumulative Q-values.

Motivated by the goal of adaptive exploration, we define the important concept of child stationarity, which is a relaxation of the standard Markov stationarity requirement. Let $\sigma:\Delta\Pi$ denote a distribution over joint policies.

An infostate action pair $(s,a)$ satisfies child stationarity for policy distributions $\sigma$ and $\sigma^{\prime}$ if the local reward and state transition functions, from the perspective of the current player, remain stationary despite a change in policy distribution, and even if other portions of the environment, possibly including ancestors of $s$, are nonstationary. Importantly, the transition function must remain constant with respect to the true, hidden states and not merely the observed infostates.⁴⁴4We give a more detailed discussion of the similarities and differences between child stationarity and Markovian stationarity in Appendix B. By definition, an MDP satisfies child stationarity for all infostates $s$ and actions $a$ with respect to all possible distributions over joint policies $\sigma,\sigma^{\prime}$. In contrast, in imperfect-information games such as Poker, the distribution over the hidden state at your next turn, after playing a given action $a$ at infostate $s$, will generally depend on the policies of the other players, violating child stationarity.

The utility of child stationarity can be seen as follows. While MDPs and perfect information games can be decomposed into subgames that are solved independently from each other (Tesauro et al., 1995; Silver et al., 2016; Sutton & Barto, 2018), the same is not true for their imperfect-information counterparts (Brown et al., 2020). Finding transitions that satisfy child stationarity allows for natural decompositions of the environment that can be solved independently from the rest of the environment. As such, child stationarity forms a core reason for why ABCs is able to unify BQL and CFR into a single algorithm.

Define $G^{\sigma}(s,a)$ as a game whose initial hidden state is drawn from $\mathbb{E}_{\pi\in\sigma}\left[T_{\pi}(h^{\prime}\mid s,a)\right]$ and then played identically to $G$, the original game, from that point onward. $G^{\sigma}(s,a)$ is analogous to the concept of Public Belief States introduced by ReBeL (Brown et al., 2020, Section 4).

Child stationarity forms the crux of the adaptive exploration policy of ABCs, allowing us to employ trajectory-style updates at stationary $(s,a)$ pairs without affecting the convergence guarantees of CFR in two-player zero-sum games.

How can we measure child stationarity in practice? Notice that the definition only requires that the transition and reward dynamics stay fixed with respect to two particular distributions of joint policies, not all of them. Let $\pi_{1},\pi_{2},\cdots\pi_{N}$ be the policies used by our learning procedure for each iteration of learning from $1\cdots N$. Define $\sigma^{N}_{A}$ as the uniform distribution over $\{\pi_{1}\cdots\pi_{\left\lfloor N/2\right\rfloor}\}$ and $\sigma^{N}_{B}$ as the uniform distribution over $\{\pi_{\left\lfloor N/2\right\rfloor+1}\cdots\pi_{N}\}$. At iteration $N$, Algorithm 1 directly tests child stationarity with respect to distributions over joint policies $\sigma_{A}^{N},\sigma_{B}^{N}$ as follows: for each infostate $s$ and action $a$, it keeps track of the rewards and true hidden states that follow playing action $a$ at $s$. Then, it runs a Chi-Squared Goodness-Of-Fit test (Pearson, 1900) to determine whether the distribution of true hidden states has changed between the first and second half of training. We adopt child stationarity as the null hypothesis. While Algorithm 1 is not a perfect detector, Theorem 4.3 shows that in the limit, Algorithm 1 will asymptotically never claim that a given $s,a,\sigma_{A},\sigma_{B}$ satisfies child stationarity when it does not, assuming $(s,a)$ is queried infinitely often. However, the Chi Squared test retains a fixed rate of false positives given by the significance level $\alpha_{s}$, so Algorithm 2 will incorrectly reject the null hypothesis of child stationarity with some positive probability.

We are now ready to learn our ABCs. At a high level, ABCs chooses between a BQL update and a CFR update for each $Q(s,a)$ value based on whether or not it satisfies child stationarity with respect to the joint policies encountered over the course of training. One can view ABCs from two equivalent perspectives. From one perspective, ABCs runs a variant of ES-MCCFR, except that at stationary infostates, where it is unnecessary to run a full CFR update, it defaults to a cheaper BQL update. Alternatively, one can view ABCs as defaulting to a variant of BQL until it realizes that an infostate is too nonstationary for BQL to converge. At that point, it backs off to more expensive CFR style updates. We provide the formal description of ABCs in Algorithm 2. In the multi-agent setting, ABCs freezes all players’ policies at the beginning of each learning iteration and then runs independently for each player, exactly as multi-agent BQL and ES-MCCFR does.