What game are we playing? End-to-end learning in normal and extensive form games

Introduction

Recent work in artificial intelligence has led to huge advances in methods for solving large-scale, zero-sum, extensive form games, both from methodological and applied standpoints. From the algorithmic approach, methods based on Counterfactual Regret Minimization Zinkevich et al. (2008) and first-order methods for game solving Kroer et al. (2017), have enabled solutions to larger and larger games. In terms of applications, there have been a number of recent breakthroughs, including exceeding human performance in no-limit poker Brown and Sandholm (2017); Moravčík et al. (2017), essentially weakly solving limit poker Bowling et al. (2015), work in security games with applications to infrastructure security Pita et al. (2009), and many others. However, virtually all this progress in game theoretic approaches to large games has operated under the assumption that the parameters of the game are known to the solvers, and that the main challenge is simply finding the optimal strategy. In contrast, in many real world scenarios, certain elements of the game (e.g., payoff matrices, chance node probabilities, etc), are unknown to some of the agents prior to the game. For example, in security games, we may want to understand the underlying payoffs of an adversary, rather than just their observed strategy, to better understand how aspects of the game can be manipulated or changed to get a desirable outcome.

In this paper, we propose an end-to-end framework for learning the parameters of uncertain games (both for normal-form and extensive-form games), purely by observing the actions of the agents. Although there has been a great deal of work at the intersection of game theory and reinforcement learning Busoniu et al. (2008); Bowling and Veloso (2000), most game-theoretic analysis either assumes that the payoffs underlying the game are known (this is the standard game theory setting), or forgoes trying to learn an explicit and complete representation of the game and instead looks for merely learning agent strategies that will perform well Letchford et al. (2009); Vorobeychik et al. (2007); Fearnley et al. (2015). However, in many cases when the true underlying payoffs of the agents are not known, our primary goal is precisely to recover or understand the payoffs. The few exceptions that focus on learning the payoffs often rely on special structures of the game (e.g., symmetry in multiplayer setting Vorobeychik et al. (2007)), or querying the best response of the agent with unknown payoffs by asking other agents to play carefully designed strategies Blum et al. (2014); Letchford et al. (2009). However, the general problem of learning game parameters by observing actions is still under-explored. One of the most closely-related works to our own is the Computational Rationalization framework Waugh et al. (2011), though 1) our approach differs in how the utilities/payoffs are modeled; and 2) we crucially focus heavily on the extensive form settings, whereas this past work considered only normal form games.

The crux of our approach is to consider the quantal response equilibrium (QRE), a generalization of Nash equilibrium (NE) that includes some possibility of agents acting suboptimally. We show that the solution of the QRE is a differentiable function of the game payoff matrix, and backpropagation can be computed analytically via implicit differentiation. We develop a solver that jointly solves the QRE for two-player zero-sum games using a primal-dual Newton Method, and allows us to compute the derivatives of agent actions with respect to the underlying payoff matrix. This enables us to develop end-to-end learning approaches that can infer the payoff matrix or other parameters underlying a game merely from samples of the agents acting according to their QREs. Naturally, there are some questions here about when games are identifiable or not; in general, the answer is no, because e.g. many payoff matrices can lead to identical strategies or policies for the agent, so we do not expect to always be able to recover a true underlying payoff matrix. However, we show that for various classes of parametrized games, our approach is able to recover the true underlying payoffs of different agents. More generally, the method allows for (both normal form and extensive form) game-solving to be integrated as a module in deep learning systems, a strategy that can find use in multiple application areas.

We demonstrate the effectiveness of our approach on several domains: a toy normal-form game where payoffs depend on external context; a one-card poker game (with a small representation in strategic form, but which would already be too large to solved in normal form); and a security resource allocation game, which is an extensive-form generalization of defender-attacker game in security domain. In all settings, we show that our approach is able to learn, solely from observed actions, the relevant underlying parameters of the game, such as the payoff matrices or (agent belief over) chance node probabilities. We believe this represents a substantial step forward in understanding how game theoretic methods can be applied to uncertain settings, where the “true” parameters of the game are unknown to an agent. Due to space constraints, supplementary material and appendices are available at arXiv.https://arxiv.org/abs/1805.02777

Learning and Quantal Response in Normal Form Games

Our game-solving module provides all the elements required to perform differentiable learning through the game solution. The resulting learning approach learns a mapping from contextual features $x$ to payoff matrices $P$ and computes equilibrium strategies $(u^{*},v^{*})$ under a new set of contextual features. An example architecture is presented in Figure 1. Here, $P$ is parameterized by a domain-dependent low-dimensional vector $\phi$, which is dependent on a differentiable function $M_{1}(x)$. Similarly, the loss function is taken after applying any differentiable $M_{2}(u^{*},v^{*})$. For the remainder of the paper, we focus on zero-sum games, which capture a wide class of adversarial environments.

We begin by considering normal form games. Although normal form games have limited real-world utility due to the fact that they can only handle relatively small-scale settings, the game solver and learning approach in this restricted setting captures much of the intuition and basic methodology of our approach.

In two-player zero-sum game with payoff matrix $P$, a classic min-max formulation to compute the NE is as follows

$u$ and $v$ denote the (mixed) strategies employed by the min and max player respectively. The solution $(u^{*},v_{0})$ to this optimization problem and the solution $(u_{0},v^{*})$ of the corresponding problem with inversed player order (i.e., $\min_{v}\max_{u}u^{T}Pv$) forms the Nash equilibrium $(u^{*},v^{*})$.

Here we present an introduction to our approach considering the case where the payoff matrix $P$ is not known a priori. $P$ could represent either a single fixed but unknown payoff matrix, or, in a more complex setting, depend on some external context $x$. For example, in anti-poaching games Fang et al. (2016), $P$ depends on temperature and precipitation. In general, however, we consider the case where we observe samples of actions $a^{(i)}$, $i=1,\ldots,N$, consisting of observed actions, from one or both players, sampled from the equilibrium strategies $(u^{*},v^{*})$. The goal is to recover the true underlying payoff matrix $P$, or a function form $P(x)$ depending on the current context.

2 Quantal Response Equilibria

While extremely powerful both theoretically and as a modeling tool, the NE is poorly-suited for our purposes because:

NEs are overly strict. In practice, many payoff matrices result in actions never being played. This tends to be overly restrictive and does not adequately describe real-world scenarios where players are boundedly rational.

NEs in zero-sum games may not be unique. This leads to difficulties when resolving which NE to select.

NEs are discontinuous with respect to $P$ – a small change in $P$ can lead to jumps in $u^{*},v^{*}$. This precludes integrating the technique into differentiable learning procedures.

To address these issues, in our learning setting we propose to model the player’s action with the quantal response equilibria McKelvey and Palfrey (1995) instead. In general, QRE models situations where payoff matrices are injected with some noise. Specifically, we consider the logit equilibrium, where payoffs are perturbed by samples from a Gumbel distribution. The smoothness of QRE makes gradient-based approaches feasible Amin et al. (2016). It is known that for zero-sum games, the logit equilibrium obeys the fixed point In the QRE, there is an additional rationality parameter $\lambda$. In this work, we fix $\lambda=1$ throughout.

It is further known that for a fixed opponent strategy, the logit equilibrium corresponds to a strategy regularized by the Gibbs entropy Mertikopoulos and Sandholm (2016). Since the Gibbs entropy is strictly convex, the regularized best response is unique.

3 End-to-End Learning

In order to integrate zero-sum game solvers into an end-to-end learning framework, we need a method for “differentiating through” the game solution itself; that is, we need to compute the Jacobian (or more precisely, compute the Jacobian-vector products needed for backpropagation) of the quantal equilibrium solution with respect to the payoff matrix. Our method for doing so relies on techniques from differential calculus, and is a relatively straightforward extension of similar approaches to differentiating through optimization problems. However, as a prelude to the more involved extensive form solution that we will discuss shortly, we describe our method in some detail, which involves both a particular approach to solving the QRE and to differentiating through its solution.

We observe that finding the fixed point in (4) is equivalent to solving the regularized min-max game

where $H(y)$ is the Gibbs entropy $\sum_{i}y_{i}\log y_{i}$. Notice that the non-negative constraints are implicit from the entropy term, and that the entropy regularization renders the equilibrium continuous with respect to $P$. Intuitively, entropy regularization encourages players to play more randomly, and no action has probability . Furthermore, since the objective is strictly a convex-concave problem, it has a unique saddle point which corresponds to $(u^{*},v^{*})$.

This formulation leads to a solver for the QRE for two-player zero-sum games, using a primal-dual Newton Method. To begin, the KKT conditions for the above problem are

where $\mu,\nu$ are Lagrange multipliers for the equality constraints on $u,v$ respectively. Following Newton’s method, we get the following update rule, which provides a convergent method for computing the QRE for 2 player zero-sum games

3.2 Differentiating Through QRE Solutions

The QRE solver also provides a method for computing the necessary Jacobian-vector products. The derivation follows in a similar manner to recent work in differentiating equality-constrained optimization problems Gould et al. (2016); Johnson et al. (2016); Amos and Kolter (2017) (the only difference being the min-max objective instead of a pure minimization objective, but since we compute differentials via the KKT conditions, the differences are minor). Specifically, given the solution $(u^{*},v^{*})$ to the QRE, and considering some loss function $L(u^{*},v^{*})$ (for example, the log-likelihood of some observed data given this equilibrium probabilities), we show here how to compute the gradient of the loss with respect to the payoff $P$. In particular, taking differentials of the KKT conditions and rearranging leads to the following expression

For small changes denoted by $\mathsf{d}u,\mathsf{d}v$, we have

where the last step is from symmetry of $Q$. This expression governs how small changes in $\mathsf{d}P$ affect $L$. For example, we may obtain the change in $L$ after perturbing a single entry in $P$. Applying this procedure to all entries in $P$, simplifying and taking limits as $\mathsf{d}P$ is small yields

Hence, the forward and backward passes with our module are respectively given by: 1) Using the expression in (7), solve for the logit equilibrium given $P$, and 2) Using $\nabla_{u}L$ and $\nabla_{v}L$, obtain $\nabla_{P}L$ using (10). It is stressed that the module is sufficiently general to be included in any existing architecture where having a zero-sum game module is appropriate.

3.3 A Note on Identifiability

As mentioned in Section 1, it is natural to ask if the games are identifiable – that is, is there a unique $P$ which under the logit QRE, generates $u^{*},v^{*}$? The answer is no, in general. Assuming $u^{*},v^{*}$ are fixed, we can rewrite the KKT conditions in (6) as a system of linear equations in $P$. This system has $\mathcal{O}(nm)$ unknowns but only $\mathcal{O}(n+m)$ constraints. This implies that without a sufficiently compact parametrization, there will be infinitely many payoff matrices leading to identical equilibria. For example, one can add a constant to all entries in $P$ without changing the QRE. When under-constrained, one cannot expect to recover $P$. However, as we show below, there are also many settings where it is possible to recover underlying parameters reliably.

Learning Extensive Form Games (EFG)

In practice, many games are more naturally and compactly represented in extensive form. Unfortunately, learning payoff matrices of their equivalent normal form representation is computationally unfeasible even for small games. For example, one-card poker has $2^{26}$ pure strategies per player. In order to facilitate learning of EFGs, we turn to the sequence form representation Von Stengel (1996), which is sufficiently rich to represent all strategic behaviors given perfect recall.

2 Dilated Entropy Regularization

Denote $\mathcal{I}_{u}$ and $\mathcal{I}_{v}$ to be all information sets for the min and max player. For an information set $i\in\mathcal{I}_{u}\cup\mathcal{I}_{v}$, $\mathcal{A}_{i}$ denotes the possible actions at information set $i$, while $p_{i}$ is the action (from the same player) preceding $i$. Similarly, define $\rho_{a}$ to be the information set immediately preceding the action $a$ ,i.e. $i$ where $a\in\mathcal{A}_{i}$. As with the normal form representation, we solve the regularized min-max problem

This form of regularization is known as dilated entropy Kroer et al. (2017) or normalized entropy Boyd and Vandenberghe (2004), and is known to be strictly convex/concave in $u$ and $v$ respectively. Observe that this formulation operates in $\mathcal{O}(m+n)$ dimensions. The number of sequences is bounded by the size of the game tree and is normally much smaller than the number of pure strategies.

One of our first primary results in this paper is the fact that this particular form of regularization, applied to the sequence form, recovers the QRE as applied to the equivalent reduced normal form game (that is, the normal form representation of the extensive form, but with unattainable strategies omitted).

The solution to (11) is realization equivalent to the QRE of the game in reduced normal form.

(Sketch) Consider the max player in isolation and his game tree, represented by alternating actions and information states. Choose any action $a_{0}$ with parallel information sets, near the bottom of the tree (i.e. all child information sets are leaves). In sequence form, this action and its subtree may be coalesced into a set of strategies, corresponding to the Cartesian product $\prod_{\{i|p_{i}=a_{0}\}}\mathcal{A}_{i}$. This essentially converts a part of the sequence form into normal form. It can be shown that the solutions to (11) before and after this replacement are realization equivalent. The proof follows by repeated bottom-up application of this operation, eventually collapsing the tree to its reduced normal form, all while maintaining realization equivalence. The full proof is in the Appendix. ∎

Theorem 1 shows dilated entropy regularization leads to a well-accepted solution concept, even if it differs slightly from the more traditional definition of the QRE for extensive form games McKelvey and Palfrey (1998). A side consequence is that under certain regimes, the excessive gap technique Kroer et al. (2017); Hoda et al. (2010) used to quickly solve zero-sum EFGs converges to the NE specified by QRE in reduced normal form, as the rationality-parameter tends to $\infty$.

3 Differentiable Learning in Sequence Form

Here we derive a differentiable formulation of the sequence form QRE, mirroring our derivation for the normal form case, but admittedly with significantly more complex notation due to the more involved entropy term. The KKT conditions of our optimization problem are,

where $\mathcal{C}_{a},\mathcal{C}_{a^{\prime}}$ are sets of possible information sets immediately following $a$ or $a^{\prime}$. $J_{a},J_{a^{\prime}}$ are their sizes, i.e. $|\mathcal{C}_{a}|,|\mathcal{C}_{a^{\prime}}|$.

We write the terms on the left hand side as a vector $g(u,v,\mu,\nu)$. Taking derivatives again yields the updates for Newton’s method.

The updates are done in exactly the same manner as (10)

We can use this differentiable game solver within an automatic differentiation framework to easily obtain gradients of virtually any loss with respect to any of the game parameters. In particular, we used the PyTorch automatic differentiation library Paszke et al. (2017), and will release the full code for our solver as open source along with the release of this paper.

Experiments

We empirically demonstrate our module’s novel aspects – learning extensive form games in the presence of side information, with partial observations. In the first experiment, we learn a non-symmetric variant of rock, paper, scissors with side information. We illustrate the learning of extensive form games with one-card poker, and learning with partial information with a security resource allocation game. In all cases, we minimize the log-loss of the observed sequence - that is, maximizing the likelihood of realizing observed sequence from the player, assuming he acts in accordance to the QRE.

Due to space constraints, hyper-parameters and details of train/test environment are deferred to the Appendix. Generally, our module works well with a medium or large batch size (e.g. 128), RMSProp Tieleman and Hinton (2012) or Adam Kingma and Ba (2014) optimizers with learning rates between $[0.0001,0.01]$.

Rock Paper Scissors (RPS) is among the most well-studied 2-player zero-sum game. It is well known that playing uniformly is an NE and QRE for RPS. In this experiment, we consider the following variant (Figure 2), which breaks symmetry between the 3 actions. Notice that the traditional RPS is recovered when $b_{1},b_{2},b_{3}$ are all 1.

2 One-Card Poker

We consider a simple poker game where players are dealt a single card, with ante/bets of $10$, and two stages of betting for the first player. Specifically, suppose $n$ cards labeled $1$ through $n$ are dealt uniformly. Both players begin with an ante of $10$. Player 1 decides whether to bet an additional $10$, followed by Player 2 (who folds if he does not call). Lastly, Player 1 may choose to bet if Player 2 raises. Both players are obliged to reveal their card at the end of each game.

While relatively simple, the game contains the key elements in extensive-form games and the strategic concepts in poker such as slow playing (e.g. not betting even if Player 1 holds the high card) and bluffing (e.g. betting even if the player holds a low card). Despite its simple structure, the game with $n$ cards has $2^{2n}$ normal form pure strategies for each player. This exponential explosion of strategies is not improved by using the reduced normal form. However, in sequence form, we only need to work with realization plans of size $4n$.

Remark. While counting cards seems to be a straightforward way to learn the card distribution when $d$ does not change over time, our method is suited to learn the player’s perceived or believed distribution of cards, which may be different from the distribution of cards dealt. This may even be a function of contextual features such as demographics of players.

A total of three experiments were run with $n=4$. For each experiment, $d\sim\text{Dir}(1,1,1,1)$. Each experiment comprises 5 runs of training, with same weights but different training sets. Training was for $2500$ epochs, which was observed to be after convergence. The mean squared error of learned parameters are averaged over all runs and are presented in Figure 4.

3 Security Resource Allocation Game

In this set of experiments, we demonstrate the ability to learn from incomplete observations in a setting that abstracts attacks in cybersecurity domain. The defender possesses $k$ indistinguishable and indivisible defensive resources, e.g., cyber analysts, which he splits among $n$ targets, $\{T_{1},...,T_{n}\}$. In an attacking attempt, the attacker (row player) chooses one target. In the event an attack on $T_{i}$ succeeds, the attacker obtains a reward of $R_{i}$ (and the defender $-R_{i}$), otherwise, the payoffs to both parties are . Each defensive resource independently prevents an intrusion with probability $0.5$. For example, if there are two defenders guarding $T_{1}$, the chance of a successful attack on $T_{1}$ is $\frac{1}{2^{2}}$. This creates a scenario where the marginal benefit of each defensive resources decreases, thus requiring the defender to strike a balance. The matrix of expected payoffs when $n=2,k=3$ is shown in Figure 5.

In addition to considering the case where the attacker launches a single attack, we also consider a multi-stage game where the attacker can launch $t$ attacks, one in each stage while the defender chooses his allocation of resources in stage $1$ and cannot change it in later stages. On the other hand, the attacker has the option of changing his target between stages. This describes a setting where analysts are deployed to specific network assets on a daily basis, while attackers are sufficiently nimble to make multiple attacks in a single day. To understand why the attacker may change target, consider that target $T_{i}$ is attacked in stage $1$ and the attack is unsuccessful. It may be inferred that it is more likely that $T_{i}$ is better guarded, prompting the attacker to switch targets.

Three experiments are run with $n=2,k=5$ for games with single attack and double attack, i.e, $t=1$ and $t=2$. Crucially, in this set of experiments, we learn $R_{i}$ only based on observations of the defender’s actions. This setting yields a $10\times 6$ sequence form payoff matrix. For each experiment, $R_{1}$ and $R_{2}$ are drawn uniformly in $$. Each experiment is run$10$times for at least$2000$ epochs per run. The mean and standard error over each run is presented in Figure 6. The results show that our algorithm can still recover the game setting by only observing defender’s actions.

4 Discussion

As expected, the quality of learned parameters improves as the number of data points increases. Notable exceptions occur in (i) the green plot for the security game when $t=2$ and (ii) RPS, when comparing between training sizes of $2000$ and $5000$. These outliers are no longer observed when comparing MSE of $u,v$. For example, Figure 3 shows that predicted strategies improve significantly when going from $2000$ to $5000$ samples, showing that despite not converging to better parameters, the network still demonstrates a marked improvement in predicting player strategies.

Conclusion

In this paper, we present a fully differentiable module capable of learning payoff and other parameters in zero-sum games, given side information and partial observability. The proposed module’s unique capabilities are demonstrated over a broad range of problems. Future work entails faster solvers by exploiting structure in the KKT matrix and extensions to learning general-sum games.

References

Appendix A Proofs and derivations

In this section we present the proof of one of the main technical results of this paper, that the dilated entropy regularization of a extensive form game is equivalent to the standard entropy-regularized QRE of the equivalent reduced normal-form game.

Consider the max player in isolation. His game in sequence form may be represented by a tree with alternating actions and information sets. Consider the game shown in Figure 7. Red nodes are vertices and black nodes are information sets. White squares represent sibling actions of $A$, which may in turn, contain other parts of the game tree. The information states associated with $I_{1},I_{2}$ are parallel information states, i.e. both of which may be reached from $A$ with non-zero probability (assuming suitable opponent/chance actions).

We show that the optimal solution using dilated entropy regularization on the game in Figure 7 is realization equivalent to the optimum of the reduced game in Figure 8. Essentially, this operation converts part of the sequences to the normal form, by replacing parts of the tree with all possibly contingencies. Repeated application of this operation eventually translates the sequence-form representation to the reduced normal form. This is performed on the tree in a bottom-up manner, all while maintaining realization equivalence.

Let $A$ be the an action such that all immediate child actions are leaves (e.g. Figure 7) and $I$ be its parent. We condition on having taken the action $A$, that is, assume that the player reaches $A$ with probability $1$ (barring chance or the other player’s actions). We will first show that after conditioning, the resultant reduced normal form is equivalent to its sequence form.

Notation. Recall $\mathcal{C}_{A}=\{I_{k}\}$ denotes the children information sets of $A$. The action set at $I_{k}$ is denoted by $\mathcal{A}_{k}=\{A_{kj}\}=\{a\in\mathcal{A}_{v}|\rho_{a}=I_{k}\}$. For the purposes of this derivation, the opponent’s strategy is fixed, and his strategy profile is combined to give $P^{T}u=x$.

In normal form, all contingencies are accounted for, and the set of pure strategies are given by the Cartesian product of action sets $\hat{\mathcal{A}}_{A}=\prod_{k}\mathcal{A}_{k}$. We denote the normal form mixed strategy profile, payoff matrix, and normal form payoff vector as $\hat{v}$, $\hat{P}$ and $\hat{x}=\hat{P}^{T}\hat{u}$. Note that the sizes of these vectors/matrices are not equivalent to their counterparts in sequence form. For convenience, we define $f(\hat{v})$ to be a function mapping $\hat{v}$ to $v$ by performing the appropriate marginalization. Let $g(v,j)$ be the distribution of actions extracted from $v$ supposing an information state of $I_{j}$. For simplicity let $H$ now define the Shannon entropy, $H(y)=-\sum y_{i}\log(y_{i})$.

Derivation. The resultant QRE in the reduced normal form is,

The first line is by definition. The second line holds from the fact that joint entropy is maximized by independent random variables (induced by the marginals $g(f(\hat{v}),j)$). That is, if this independence relationship does not hold, then we could construct a strictly better candidate solution. The third line follows from the fact that the joint entropy of mutually independent random variables is equal to the sum of their entropies. The last line is true since every sequence form strategy is induced by at least one normal form strategy (i.e. the image of $f$ is equal to the domain of $v$) and vice versa.

A.1.2 Part 2

In Part 1, we showed realization equivalence when the white square is non-existent, i.e. there are no other children of $I$. In this section, we relax that assumption. For this part of the proof, $I$ may possibly not be the root.

The first line follows from the result in Part 1. The second line splits the entropy regularization terms from $I$ into the terms involving $A$ and those which do not. The last line follows from ‘reintroducing’ the flow constraints into the inner maximization. Observe that the $\acute{v}_{A}\log\acute{v}_{A}$ terms cancel out, allowing for the following simplifications,

Observe that $\acute{x}_{A}$ is zero, since it must be a non-leaf node (all rewards are deferred to leaves). This allows us to recombine $\acute{v}$ and $\hat{v}$ into a long vector in sequence form, which we denote $\grave{v}$ – which is the sequence form of the condensed version (e.g. Figure 8. The flow constraints in the inner maximization is ‘compatible’ with the form required by the outer maximization.

where the $\grave{\mathcal{A}}$ and $\grave{\mathcal{I}_{v}}$ are the action sets in the condensed game (i.e all the information sets originally children of $A$ are gone, and the actions in the normal form are now actions in $\rho_{A}$). $\grave{x}$ refers to the reward vector obtained by merging $\hat{x},\acute{x}$ together, and removing the term associated with $\acute{x}_{A}$ (which was to begin with).

The final part of the proof follows by repeatedly applying the transform described. Note that it is always possible to find a suitable $I$ and $A$ for this process, if not, then we have already arrived at the reduced normal form. The number of non-leaf actions must drop monotonically, hence the process will terminate at some point. Lastly, observe that our assumption that non-leaf actions have payoffs is remains true after every iteration.

Appendix B Experimental setup

Here we provide a complete example of how to encode and parameterize one-card poker in sequence form, as required by our approach. We begin with the linear constraints in sequence form. Recall $E$ and $F$ matrices define the structure of the game state transitions, $Eu-e=0$, $Fv-f=0$. For a game with $4$ cards, there are $8$ information sets and $16$ actions per player. The constraint matrices are given by

We now turn to parameterization of the payoff matrix in terms of the card distribution $d$. Suppose for the time being that the deck is uniformly stacked, i.e. $d=(0.25,0.25,0.25,0.25)$. Define the showdown matrix

where by our convention, the row player is the minimizing player. Each block is of size $4\times 4$, and gives possible outcomes for each of the $4^{2}$ possible ways of dealing cards. The 4 blocks for the row player correspond to the actions ‘do not raise on first move’, ‘raise on first move’, ‘fold on second move’, ‘raise on second move’. For the column player, the $16$ actions are ‘fold after first player did not raise’, ‘raise after first player did not raise’, ‘fold after first player raised’, ‘raise after first player raised’.

When $d$ is not uniform, define the $4\times 4$ distribution matrix

i.e. every $4\times 4$ block is pointwise weighted by the chance of being dealt the relevant cards. It may be seen that the forfeit matrix $X$ is really just the all-ones matrix multiplied pointwise by $D$.

B.2 Experimental setup

All of the experiments are run using CPU cycles.

Experiments were run on a 3.1 GHz Intel Core i5 with 16 GB of RAM. The learning rate is $0.0005$, with a batch size of $128$. We utilized the Adam optimizer. The maximum number of epochs before termination is $10000$. Parameters were initialized to the -matrix for each experiment.

B.2.2 One card poker

Experiments are run on a 4.2GHz Intel Core i7 with 128GB of RAM . The learning rate is $0.002$, batch size of $128$, using the RMSProp optimizer. Weights are initialized to be uniform, i.e. $(0.25,0.25,0.25,0.25)$. In order to ensure that $d$ is valid probability distribution, the features are passed through softmax layer which then outputs $d$. The maximum number of epochs is $2500$, although convergence occurs significantly faster. Since there is no context, experiments may be run much faster by computing the forward pass just once for each minibatch. Similarly, the inverse matrix required in the backward pass may be cached and reused between each member in the same minibatch.

B.2.3 Security resource allocation game

The experiments were run on an Amazon c4.2xlarge EC2 instance. The learning rate is $0.002$ using the RMSProp optimizer (all other hyperparameters are left as the defaults in Pytorch). Each run was $2000$ epochs. The weights are passed through $f(x)=(\text{tanh}(x)+1)$ to clip rewards to between $$ for the payoff matrix.