Int8 about machine learning

Immediate Counterfactual Regret

To introduce counterfactual regret minimization we will need to look at the poker game from a certain specific angle. First of all we will be looking at single information set, single decision point. We will consider acting in this information set repeatedly over time with the goal to act in a best possible way with respect to certain reward measure.

Assuming we are playing as player \(i\), let’s agree that reward for playing action \(a\) is unnormalized counterfactual utility under assumption we played action \(a\) (let’s just assume this is how environment reward us). Entity in consideration is then defined as:

We can easily abstract the whole thing as ‘combining experts advice’ model via interpretation similar to Rock-Paper-Scissors game from the previous section:

• at our decision point we have fixed finite set of actions \(A(\mathrm{I})\) (or experts advice)
• we assume we act in our information set \(\mathrm{I}\) according to some algorithm \(\mathrm{H}\) repeatedly over time
• algorithm \(\mathrm{H}\) job is to update probabilities of actions being played (behavioral strategy at our decision point)
• for every \(t\) we have a probability distribution over actions \(\sigma^t_{\mathrm{H}}(\mathrm{I})\) that expresses our confidence of playing them (behavioral strategy/trust towards experts learnt by \(\mathrm{H}\))
• for every \(t\) black-box mechanism (environment) triggers reward vector being revealed (vector of unnormalized counterfactual utilities, one for each action, expressing conequences of playing these actions)

As you know already, in online-learning setup it is beneficial to consider expected reward (and compare it to the single best action performance) of our algorithm H over time. Let’s try to think what expected reward we land on

if we follow expected reward definition and compute weighted sum of rewards’ vector using weights according to behavioral strategy in our information set \(\mathrm{I}\) (a ‘trust’ distribution) we will actually end up having unnormalized counterfactual utility for \(\mathrm{I}\) at time \(t\):

\[
\begin{align}
\sum_{a\in A(\mathrm{I})} \sigma^t_{\mathrm{H}}(\mathrm{I})(a) \hat{u}_{|\mathrm{I} \rightarrow a}(\sigma^t_{\mathrm{H}}, \mathrm{I}) &= \\ \sum_{a\in A(\mathrm{I})} \sigma^t_{\mathrm{H}}(\mathrm{I})(a) \sum_{h \in \mathrm{I}, h’ \in \mathrm{Z}} \pi^{\sigma^t_{\mathrm{H}}}_{-i}(h) \pi^{\sigma^t_{\mathrm{H}}}(ha, h’) u(h’) &= \\ \sum_{h \in \mathrm{I}, h’ \in \mathrm{Z}} \pi^{\sigma^t_{\mathrm{H}}}_{-i}(h) \pi^{\sigma^t_{\mathrm{H}}}(h, h’) u(h’) &= \\ \hat{u}_i(\sigma^t_{\mathrm{H}}, \mathrm{I})
\end{align}
\]

note that, choosing action \(a\) gets \(\sigma^t_{\mathrm{H}}(\mathrm{I})(a)\) out of formula but it is brought back again via expected reward computation

Having total reward of algorithm \(\mathrm{H}\) we can define regret in our setting to be:

\[
R_{i, imm}^T(\mathrm{I}) = \frac{1}{T} \max_{a \in A(\mathrm{I})} \sum_{t=1}^{T} (\hat{u}_{|\mathrm{I} \rightarrow a}(\sigma^t_{\mathrm{H}}, \mathrm{I}) – \hat{u}_i(\sigma^t_{\mathrm{H}}, \mathrm{I}))
\]

which Zinkevich and his colleagues called Immediate Counterfactual Regret.

Last important entity, Immediate Counterfactual Regret of not playing action \(a\) is given by:

\[
R_{i, imm}^T(\mathrm{I},a ) = \frac{1}{T} \sum_{t=1}^{T} (\hat{u_i}_{|\mathrm{I} \rightarrow a}(\sigma^t_{\mathrm{H}}, \mathrm{I}) – \hat{u}_i(\sigma^t_{\mathrm{H}}, \mathrm{I}))
\]

and is actually equivalent to regret of not listening to expert \(a\) in our no-regret interpretation.

Immediate Counterfactual Regret and Nash Equilibrium

Landing in regret minimization framework again does not imply we can apply our theorem that we used for Rock-Paper-Scissors. The difference is that in our case we ‘regret’ in the single information set only, not the whole game. Fortunately Zinkevich and his colleagues showed that this is still OK and we can still land in Nash-Equilibrium if we consecutively apply regret matching for Immediate Counterfactual Regret over time for all information sets. They actually proved two things:

• For fixed strategy profile if we compute immediate counterfactual regrets in all information sets, their sum will bound overall average regret.
  \[
  \hat{R}_i^T \leq \sum_{\mathrm{I} \in \mathcal{I}} R_{i, imm}^T(\mathrm{I})
  \]
• if player selects actions according to regret matching routine, counterfactual regret goes to zero eventually

Counterfactual Regret Minimization – implementation plan

Let’s try to summarize what we actually need to compute Nash Equilibrium via counterfactual regret minimization.

From very high level point of view we will need to:

• initialize strategies for both players – uniform distribution is ok
• run regret matching routine for all information sets for both players separately. Each time we will assume there is unknown adversary environment players may not be aware of, and they just try to play the best they can via application of no-regret learning in every time step. It means they will be adjusting their current strategy in current information set so it matches total positive regret (which happens to be counterfactual regret as we already established)
• Consecutive application of no-regret learning for both players for all information sets will trigger lots of strategy changes over time. Following our theorem, the averages of these strategies for both players will be an approximation of Nash Equilibrium.

The memory requirements

In every single information set \(\mathrm{I}\), regret matching routine requires us to distinguish:

• reward for playing action \(a\) at time \(t\):

  \[
  \hat{u_i}^t_{|\mathrm{I} \rightarrow a}(\sigma^t, \mathrm{I}) = \sum_{h \in \mathrm{I}, h’ \in \mathrm{Z}} \pi^{\sigma^t}_{-i}(h) \pi^{\sigma^t}(ha, h’) u(h’)
  \] Every action will be rewarded via unnormalized counterfactual utility assuming action was played. It is worth noting every element of the sum above can be computed separately for every game state in information set:
  \[
  \hat{u_i}^t_{|\mathrm{I} \rightarrow a}(\sigma^t, h) = \pi^{\sigma^t}_{-i}(h) \sum_{h’ \in \mathrm{Z}} \pi^{\sigma^t}(ha, h’) u(h’)
  \]

  Let’s remember that, in fact later on in our actual implementation we will be traversing through game states, not information sets.

• total reward for playing action \(a\) at time \(T\):

  \[
  \sum_{t=1}^T \hat{u_i}^t_{|\mathrm{I} \rightarrow a}(\sigma^t, \mathrm{I})
  \]

  Thiese will be our references we will be comparing current strategy performance

• reward for playing according to current behavioral strategy at time \(t\):

  \[
  \hat{u}_i(\sigma^t, \mathrm{I}) = \sum_{h \in \mathrm{I}, h’ \in \mathrm{Z}} \pi^{\sigma^t}_{-i}(h) \pi^{\sigma^t}(h, h’) u(h’)
  \]

  This will express how our current strategy performs in terms of unnormalized counterfactual utility at time \(t\)

• and finally total reward for playing according to our behavioral strategies up to time \(T\):

  \[
  \sum_{t=1}^T \hat{u}_i(\sigma^t, \mathrm{I})
  \]

  We will compare this value with total rewards for playing each action and update strategy for the next iteration accordingly

Regret matching routine will update a strategy at time \(t\) in information set \(\mathrm{I}\) with the following formula:

\[
\sigma^{T+1}_\mathrm{H} (I)(a) =
\begin{cases}
\frac{R_{i, imm}^{T,+}(\mathrm{I, a })}{\sum_{a’ \in \mathrm{I}} R_{i, imm}^{T,+}(\mathrm{I, a’})},& \text{if } \sum_{a’ \in \mathrm{I}} R_{i, imm}^{T,+}(\mathrm{I, a’}) > 0\\
\frac{1}{T}, & \text{otherwise}
\end{cases}
=
\]

where

\[
R_{i, imm}^T(\mathrm{I},a ) = \frac{1}{T} \sum_{t=1}^{T} (\hat{u_i}_{|\mathrm{I} \rightarrow a}(\sigma^t_{\mathrm{H}}, \mathrm{I}) – \hat{u}_i(\sigma^t_{\mathrm{H}}, \mathrm{I}))
\]

In every iteration we need current strategy profile, game tree (this is static) and immediate counterfactual regrets. Important observation here is that we don’t really need \( \frac{1}{T} \) in \(R_{i, imm}^{T,+}\) because it cancels out anyways. Therefore for every information set and every action it is enough to store the following sum, let’s call it \(R_{i, cum}^T(\mathrm{I},a )\):
\[
R_{i, cum}^T(\mathrm{I},a ) = \sum_{t=1}^{T} (\hat{u_i}_{|\mathrm{I} \rightarrow a}(\sigma^t_{\mathrm{H}}, \mathrm{I}) – \hat{u}_i(\sigma^t_{\mathrm{H}}, \mathrm{I}))
\]

Computation – what do we need to compute to get Nash Equilibrium?

We already established that for every information set, in every iteration we will need to store three vectors: vector of sums of strategies played so far, vector of \(R_{i, cum}^T(\mathrm{I},a )\) and current strategy \(\sigma_t\).

Now we need a clever way to go to every possible information set, compute counterfactual utilities for every action, counterfactual utility for our behavioral strategy, add the difference between these two up to the vector of cumulative immediate regrets and finally compute the strategy for the next iteration.

The very core entity we need in order to achieve so is game-state centric unnormalized counterfactual utility (under assumption of action \(a\) was played):

\[
\hat{u_i}^t_{|\mathrm{I} \rightarrow a}(\sigma^t, h) = \pi^{\sigma^t}_{-i}(h) \sum_{h’ \in \mathrm{Z}} \pi^{\sigma^t}(ha, h’) u(h’)
\]

If we had it computed for all actions and game states in information set \(\mathrm{I}\), we could easily derive the rest of the entities involved. This is a clue of how we need our final algorithm to be constructed.

Let’s then focus on how we could cleverly compute these values assuming we have the strategies for both players in place. We will start by introducing a notion of expected utility in a game state:

\[
u_i^{\sigma}(h) = \sum_{h’ \in \mathrm{Z}} \pi^{\sigma}(h, h’) u_i(h’)
\]

If this was computed for the root of the game tree it would result in expected utility of the game – well known concept in game theory. We will now proceed in the following way: we will start with expected utility computation algorithm and add more and more side effects to get our final CFR algorithm.

Expected utility computation is as easy as recursive tree traversal + propagating the results back:

def _utility_recursive(self, state):
    if state.is_terminal():
        # evaluate terminal node according to the game result
        return state.evaluation()
    # sum up all utilities for playing actions in our game state
    utility = 0.
    for action in state.actions: 
        # utility computation for current node, here we assume sigma is available 
        utility +=  self.sigma[state.inf_set()][action] * self._utility_recursive(state.play(action))
    return utility 

There is actually only very subtle difference between our unnormalized counterfactual utility and the expected utility. In fact our expected utility can be seen as a sum of the following:

\[
\sigma(h)(a) \sum_{h’ \in \mathrm{Z}} \pi^{\sigma}(ha, h’) u_i(h’)
\]

for every action \(a\) available in \(h\). The only difference is weighting component. In case of unnormalized counterfactual utility we use counterfactual reach probability, in case of expected utility it is transition probability between game states. Let’s then try to inject some extra code, a side effect, into utility computation algorithm to get unnormalized counterfactual utilities:

def _cfr_utility_recursive(self, state):
    if state.is_terminal():
        # evaluate terminal node according to the game result
        return state.evaluation()
    # sum up all utilities for playing actions in our game state
    utility = 0.
    for action in state.actions: 
        child_state_utility = self._cfr_utility_recursive(state.play(action))
        # utility computation for current node, here we assume sigma is available 
        utility +=  self.sigma[state.inf_set()][action] * child_state_utility
        # computing counterfactual utilities as a side effect, we assume we magically have cfr_reach function here
        cfr_utility[action] = cfr_reach(state.inf_set()) * child_state_utility
    # function still returns utility, side effect was added to compute counterfactual utility, too 
    return utility 

By adding this tiny side effect to our utility computation routine we in fact are now computing unnormalized counterfactual utilities for every possible action \(a\) in \(h\) for the whole game tree (if started from the root)!

One puzzle that is still missing is the weighting component (counterfactual reach probability), probability of our opponent getting to \(h\) under assumption we did all we could to get there. Good news is that these probabilities are products of transition probabilities between states we already visited. It means, we must be able to collect these products on our way down to the current game state.

def _cfr_utility_recursive(self, state, reach_a, reach_b):
    children_states_utilities = {}
    if state.is_terminal():
        # evaluate terminal node according to the game result
        return state.evaluation()
    # sum up all utilities for playing actions in our game state
    utility = 0.
    for action in state.actions:         
        child_reach_a = reach_a * (self.sigma[state.inf_set()][action] if state.to_move == A else 1)
        child_reach_b = reach_b * (self.sigma[state.inf_set()][action] if state.to_move == -A else 1)
        child_state_utility = self._cfr_utility_recursive(state.play(action), child_reach_a, child_reach_b)
        # utility computation for current node, here we assume sigma is available 
        utility +=  self.sigma[state.inf_set()][action] * child_state_utility        
        children_states_utilities[action] = child_state_utility    
    cfr_reach = reach_b if state.to_move == A else reach_a
    for action in state.actions: 
        # player to act is either 1 or -1
        # utilities are computed for player 1 - therefore we need to change their signs if player #2 acts
        action_cfr_regret = state.to_move * cfr_reach * children_states_utilities[action]       
    # function still returns utility, side effect was added to compute counterfactual utility, too 
    return utility 

We added extra parameters to our function, now at every game state we keep track of counterfactual reach probabilities for both players, they are products of probabilities of actions that were played prior to current game state (computed separately for both players).

All we need now is to run our routine for the game tree root node with reach probabilities equal to 1 for both players. This will cause counterfactual utility of not playing actions being available. Now we need to inject the rest of the code:

def _cfr_utility_recursive(self, state, reach_a, reach_b):
    children_states_utilities = {}
    if state.is_terminal():
        # evaluate terminal node according to the game result
        return state.evaluation()
    # please note that now we also handle chance node, we simply traverse the tree further down 
    # not breaking computation of utility 
    if state.is_chance():      
        outcomes = {state.play(action) for action in state.actions}
        return  sum([state.chance_prob() * self._cfr_utility_recursive(c, reach_a, reach_b) for c in outcomes])

    # sum up all utilities for playing actions in our game state
    utility = 0.
    for action in state.actions: 
        child_reach_a = reach_a * (self.sigma[state.inf_set()][action] if state.to_move == A else 1)
        child_reach_b = reach_b * (self.sigma[state.inf_set()][action] if state.to_move == -A else 1)
        child_state_utility = self._cfr_utility_recursive(state.play(action), child_reach_a, child_reach_b)
        # utility computation for current node, here we assume sigma is available 
        utility +=  self.sigma[state.inf_set()][action] * child_state_utility
        children_states_utilities[action] = child_state_utility    
    (cfr_reach, reach) = (reach_b, reach_a) if state.to_move == A else (reach_a, reach_b)
    for action in state.actions: 
        # player to act is either 1 or -1
        # utilities are computed for player 1 - therefore we need to change their signs if player #2 acts
        action_cfr_regret = state.to_move * cfr_reach * (children_states_utilities[action] - value)
        # we start accumulating cfr_regrets for not playing actions in information set 
        # and action probabilities (weighted with reach probabilites) needed for final NE computation 
        self._cumulate_cfr_regret(state.inf_set(), action, action_cfr_regret)
        self._cumulate_sigma(state.inf_set(), action, reach * self.sigma[state.inf_set()][action])
    # function still returns utility, side effect was added to compute counterfactual utility, too 
    return utility 

We added few important bits, first of all now we cumulate unnormalized counterfactual utilities for actions in information sets and we sum up sigmas (to later on computer NE out of it). Also we handle chance nodes – simply by omitting CFR-specific side effects (we don’t make decisions in chance nodes – no need to compute anything) trying not to break utility computation.

Running this once with reach for both players being 1 will result in accumulating strategies and unnormalized counterfactual regrets in all information sets and actions. After such an iteration we have to update sigma for the next iteration via regret matching routine:

def __update_sigma_recursively(self, node):
    # stop traversal at terminal node
    if node.is_terminal():
        return
    # omit chance
    if not node.is_chance():
        self._update_sigma(node.inf_set())
    # go to subtrees
    for k in node.children:
        self.__update_sigma_recursively(node.children[k])

def _update_sigma(self, i):
    rgrt_sum = sum(filter(lambda x : x > 0, self.cumulative_regrets[i].values()))
    nr_of_actions = len(self.cumulative_regrets[i].keys()
    for a in self.cumulative_regrets[i]:        
        self.sigma[i][a] = max(self.cumulative_regrets[i][a], 0.) / rgrt_sum if rgrt_sum > 0 else 1. / nr_of_actions )

That leads us to a function:

def run(self, iterations = 1):
    for _ in range(0, iterations):
        self._cfr_utility_recursive(self.root, 1, 1)
        # since we do not update sigmas in each information set while traversing, we need to
        # traverse the tree to perform to update it now
        self.__update_sigma_recursively(self.root)

After running our run method we are ready to compute Nash-Equilibrium (in a manner similar to new sigma):

def compute_nash_equilibrium(self):
    self.__compute_ne_rec(self.root)

def __compute_ne_rec(self, node):
    if node.is_terminal():
        return
    i = node.inf_set()
    if node.is_chance():
        self.nash_equilibrium[i] = {a:node.chance_prob() for a in node.actions}
    else:
        sigma_sum = sum(self.cumulative_sigma[i].values())       
        self.nash_equilibrium[i] = {a: self.cumulative_sigma[i][a] / sigma_sum for a in node.actions}
    # go to subtrees
    for k in node.children:
        self.__compute_ne_rec(node.children[k])

One iteration of counterfactual regret minimization turns out to be a single pass through the game tree + another pass for sigma and nash equilibrium computations. In essence it is utility computation routine with some side effects added.

Going through the whole game tree few times should already raise a red flag. For large size game trees it is very impractical.

Reducing a game tree size via chance sampling

Zinkevich and colleagues decided to limit number of visited nodes by sampling only one chance outcome at the time.
This means they do not visit all information sets in single iteration. They explore all possible actions in information sets they visit though.

In case of poker, sampling each chance node only once means that every single information set contains only one game state. That is because also initial hands dealing is sampled only once and the whole tree traversal is performed for that one hand only. This means we only consider single hand in an information set. That implies sigma can be updated right after computing regret in a game state – we don’t need additional traverse to update it.

Let’s improve our implementation then. Whenever we end up in chance node we need to sample one outcome and follow that choice without changing reach probabilities, we just continue traversal ‘normally’ returning utility for chosen chance outcome. Another bit is adding sigma update at the end of the ‘node visit’ – we can do it because this is the only time we are there for single iteration.

def _cfr_utility_recursive(self, state, reach_a, reach_b):
    children_states_utilities = {}
    if state.is_terminal():
        # evaluate terminal node according to the game result
        return state.evaluation()
    # now we only go through single outcome of chance
    if state.is_chance():              
        return self._cfr_utility_recursive(state.sample_one(), reach_a, reach_b)

    # sum up all utilities for playing actions in our game state
    utility = 0.
    for action in state.actions: 
        child_state_utility = self._cfr_utility_recursive(state.play(action))
        # utility computation for current node, here we assume sigma is available 
        utility +=  self.sigma[state.inf_set()][action] * child_state_utility
        children_states_utilities[action] = child_state_utility    
    (cfr_reach, reach) = (reach_b, reach_a) if state.to_move == A else (reach_a, reach_b)
    for action in state.actions: 
        # player to act is either 1 or -1
        # utilities are computed for player 1 - therefore we need to change their signs if player #2 acts
        action_cfr_regret = state.to_move * cfr_reach * (children_states_utilities[action] - value)
        # we start accumulating cfr_regrets for not playing actions in information set 
        # and action probabilities (weighted with reach probabilites) needed for final NE computation 
        self._cumulate_cfr_regret(state.inf_set(), action, action_cfr_regret)
        self._cumulate_sigma(state.inf_set(), action, reach * self.sigma[state.inf_set()][action])
    # sigma update can be performed here now as any information set contains a single game state
    self._update_sigma(state.inf_set())
    # function still returns utility, side effect was added to compute counterfactual utility, too 
    return utility 

Sampling makes single iteration much faster but it may require more iterations than vanilla version of CFR.

In practice people often use other versions of CFR. One particularly intriguing improvement is algorithm called CFR+ (one that was used in Cepheus). CFR+ is especially nice because it does not require the averaging step (which costs the whole tree traversal) to get Nash Equilibrium. After each iteration sigma is already its good approximation. Interestingly, it was never proved why sigma is enough, but it tends to happen in practice very often.

The final code for this post – our example toy CFR with chance sampling implementation – is available on github. It may differ a bit from pseudo-python presented above but should more or less be readable.

Summary

That’s all folks.

I hope you enjoyed this (a bit too long) tutorial and you are now more familiar with basics of game theory, no-regret learning and counterfactual regret minimization. Hopefully you can implement simple version of CFR for yourself or maybe even extend existing ones.

Good luck with your projects and have a good rest of the day (+ lots of nice hands)!