Large Scale Learning of Agent Rationality in Two-Player Zero-Sum Games
Chun Kai Ling1 , Fei Fang1 , J. Zico Kolter1,21School of Computer Science, Carnegie Mellon University
2
Bosch Center for Artificial Intelligence{chunkail, feif, zkolter}@cs.cmu.edu

Abstract
With the recent advances in solving large, zero-sum extensive
form games, there is a growing interest in the inverse problem
of inferring underlying game parameters given only access toagent actions. Although a recent work provides a powerful
differentiable end-to-end learning frameworks which embeda game solver within a deep-learning framework, allowing
unknown game parameters to be learned via backpropagation,
this framework faces significant limitations when applied toboundedly rational human agents and large scale problems,
leading to poor practicality. In this paper, we address theselimitations and propose a framework that is applicable formore practical settings. First, seeking to learn the rationality of human agents in complex two-player zero-sum games,
we draw upon well-known ideas in decision theory to obtain a concise and interpretable agent behavior model, andderive solvers and gradients for end-to-end learning. Second,
to scale up to large, real-world scenarios, we propose an efficient first-order primal-dual method which exploits the structure of extensive-form games, yielding significantly fastercomputation for both game solving and gradient computation. When tested on randomly generated games, we report
speedups of orders of magnitude over previous approaches.
We also demonstrate the effectiveness of our model on bothreal-world one-player settings and synthetic data.

1

Introduction

Game theory has traditionally been centered around finding players’ strategies in equilibrium. In recent years, there
has been growing interest in the inverse setting of learning game parameters from observed player actions (Vorobeychik, Wellman, and Singh 2007; Blum, Haghtalab, andProcaccia 2014; Waugh, Ziebart, and Bagnell 2011). Recent
work by Ling, Fang, and Kolter (2018) tackle this problem
in the zero-sum setting by providing an end-to-end learning
framework to learn game parameters such as payoff matrices and chance node probability distributions assuming theactions are sampled from the Quantal Response equilibrium.
At the core of the framework is a differentiable game solving
module.
However, their proposed method suffers from two major
flaws. Firstly, the assumption that players behave in accordance to the QRE severely limits the space of player strateCopyright c 2019, Association for the Advancement of Artificial
Intelligence (www.aaai.org). All rights reserved.

gies, and is known to exhibit pathological behavior even in
one-player settings. Second, their solvers are computationally inefficient and are unable to scale.
Our work addresses these deficiencies in two ways. First,
we propose the Nested Logit Quantal Response equilibrium(NLQRE), which draws upon ideas from from behavioral
science and allows for varying levels of player rationality ateach stage of the game. We show that the NLQRE is strictly
more general than the models considered by Ling, Fang,
and Kolter, and may not be replicated by a straightforward
scaling of payoff matrices. We derive the required gradientsand show that player rationality can be learned via gradientdescent can be learned using the same end-to-end learning
framework. Second, we substantially reduce training time byreformulating the backward pass as a min-max convex optimization problem and uses state-of-the-art first order primaldual methods for both the forward pass and backward pass.
Unlike previous work, which relied on second-order methods, our first-order solver does not require explicit formationof Hessians and only requires access to a fast best-response
oracle. In our evaluation with random payoff matrices andone-card poker, we report orders of magnitude of speedups.
Lastly, we evaluate the NLQRE on real-world data in an
one-player information gathering game and provide qualitative insights. In total, we believe that our work is a significant step towards the practical learning of human behavior
in zero-sum settings.

2

Background and related work

Although much less well studied than traditional equilibrium finding, there are several approaches aimed at the taskof learning games in the setting where underlying game payoffs are unknown. These include methods which rely on specific game structure such as symmetry (Vorobeychik, Wellman, and Singh 2007), operate in an active setting (Blum,
Haghtalab, and Procaccia 2014), or focus primarily on normal form games and straightforward linear settings (Waugh,
Ziebart, and Bagnell 2011). Ling, Fang, and Kolter (2018)provide an alternative framework which embeds a differentiable game solver within another gradient based learner(e.g., a deep network), as illustrated in Figure 1. This enables
game parameters to be learned via simple gradient descent.
We now describe their framework briefly.
Suppose PΦ (x) is the zero-sum payoff matrix given some

Figure 1: The framework used by Ling, Fang, and Kolter
features x and game parameters Φ which we wish to learn.
The game solver takes in PΦ (x) and outputs the QRE (u, v),
which correspond to mixed strategies of the min and max
player. During training, the log loss L(a, u, v) of the solver’s
predicted strategies is computed against observed actions a.
The game parameters Φ are then optimized by minimizing
L. This is performed by propagating gradients backwards
through the game solver and performing gradient descent,where the required gradients for the backward pass are readily derived by using the implicit function theorem. The training phase is summarized in Algorithm 1. We will now touch
on two key ideas from decision and game theory, which will
eventually culminate in the proposed NLQRE.
Algorithm 1: Learning game parameters Φ using SGD
Input: training data {(x(i) , a(i) )}, learning rate η, Φinit
for ep in {0, . . . , epmax } doSample (x(i) , a(i) ) from training data;
Forward pass: Compute PΦ (x(i) ), QRE (u, v) andloss L(a(i) , u, v);
Backward pass: Compute gradients∇u L, ∇v L, ∇P L, ∇Φ L;
Update parameters: Φ ← Φ − η∇Φ L;
end

2.1

Nested-logit choice models

One of the fundamental research problems in behavioral science is to mathematically model seemingly irrational (ornon-utility maximizing) human behavior. Among the mostimportant models is the class of the random utility models (RUM) (Thurstone 1927). The Logit model1 is the mostnotable RUM, where given a set of alternatives A eachwith (known) utility Ua , the probability that alternative a isa)picked is u∗a = P 0 exp(U. It is equivalent to the proba ∈A exp(Ua0 )ability that alternative a has highest utility under Gumbel
noise, i.e., u∗a = P (arg maxa0 (Ua0 + a0 ) = a), where a0
are i.i.d. Gumbel distributed.
However, the logit model suffers from limitations. This
includes classic ‘red and blue bus’ pathologies2 (Luce 2012)1

Logits are more commonly known by the machine learning
community as the ‘softmax’ operator.
2
Suppose there are 3 alternatives for transport – a red bus, ablue bus, and a car. The player derives the same utility for eachalternative, xcar = xred = xblue . Applying the logit model gives anequal probability of choosing each vehicle. One would however,expect the car to be taken with probability 1/2 and each bus to bechosen with probability 1/4, since the color of buses should haveno impact on decisions.

which restrict the class of behaviors permitted. Specifically,
logit models obey the property of independence of irrelevantalternatives, which does not take into account cases whenalternatives are ‘qualitatively’ similar.
Nested-logit (NL) models (Train 2009) address this limitation by grouping fundamentally similar alternatives together and allows for correlations between ’s belonging to
the same group. In a two-level NL model, A is divided into
K disjoint clusters, with alternatives a belonging to cluster
k(a) chosen with probabilityλk(a) −1X,u∗a ∝ exp Ua /λk(a) 
exp Ua0 /λk(a) 
a0 ∈k(a)where λ’s are parameters governing noise correlation. These
probabilities may be interpreted as a two-stage decision
making process: in the first stage, a cluster is chosen, andin the second stage, the specific action is selected based on(scaled) softmax on Ua within the cluster. The probability ofchoosing each cluster in the first stage is given by the softmax over the (scaled) log-sum-exp of each cluster. When
λ = 1, the standard logit model is recovered, and when
λ → 0+ , the ‘elimination by aspects’ is obtained (Tversky1972). NL models can have multiple layers, leading to a NL
tree representing the nested grouping. The reader is directedto the book by Train for background about nested logits andtheir various interpretations.

2.2

Quantal response equilibria (QRE)

We now turn our attention to 2-player games. Seminal workby McKelvey propose QRE as a noisy alternative to NE.
(McKelvey and Palfrey 1995). Similar to logit choice models, the QRE is the equilibrium obtained when payoffs are
perturbed by noise obeying a Gumbel distribution. Formally,(u∗ , v ∗ ) is a QRE of a normal form game with action sets Au
and Av for the two players and payoff matrix P if
exp(−P v ∗ /λ)aexp(P T u∗ /λ)au∗a = P,, va∗ = P∗exp(−P v /λ)a0
exp(P T u∗ /λ)a0
a0 ∈Aua0 ∈Auwhere 1/λ is a parameter governing the level of agent rationality. Observe that as λ → ∞, players behave uniformly
at random, while (u∗ , v ∗ ) approaches a NE as λ → 0+ .
For zero-sum games, it is further known (Mertikopoulos andSandholm 2016) that QRE is the unique solution of the following convex-concave program
X
X
minn maxuT P v + λua log ua − λva log vamu∈R v∈R

subject to 1T u = 1,aa

1T v = 1.

For a two-player extensive form game characterized by agame tree with information sets Iu and Iv for the min andmax player respectively, Ling, Fang, and Kolter show thatwhen λ = 1, the QRE in reduced normal form of the game isequivalent to the solution of the following regularized minmax problem, where u and v are the players’ strategies insequence form (Von Stengel 1996).
X X
ua
min max uT P v +ua loguv
uphh∈Iu a∈Ah
X X
va−va logvphh∈Iv a∈Ahsubject to Eu = e,

Fv = f(1)

In the above, P is the sequence form payoff matrix and E
and F are the sequence form constraint matrices. Ah denotes the possible actions at information set h, while ph isthe action (from the same player) preceding h. In the sequence form, one works with realization plans u, v as opposed to probability vectors. These realization plans represent probabilities of choosing a given sequence, while theconstraint matrices E, F are matrices containing {0, 1, −1}
and contain parent-child relationships in the game tree. The
sequence form is significantly more compact than the normal form while retaining virtually all of its strategic elements.

3

Nested-logit quantal response equilibria

Our proposed Nested-logit QRE (NLQRE) is a generalization of both the QRE (in zero-sum games) and NL models.
That is, it generalizes NL models to two player zero-sum
games, or equivalently, extends the QRE by permitting amore general nested logit structure. This allows us to modela far wider range of player behaviors, and in particular, cases
where player rationality varies between stages of the game.
We assume that the grouping of actions within each information set is known a-priori. The NLQRE is given by theunique solution to the following optimization problem
XXua
min max
uT P v +λhua log
u
v
uph
a∈Ah
h∈Iu
X
X
va
−
λh
va logvphh∈Iv

subject toa∈Ah

Eu = e,F v = f.

(2)

The NL model is recovered in a one-player setting (i.e., P v
is a constant vector) and the QRE is recovered when there
is no nesting and λ’s are equal. Ling, Fang, and Kolter assumes that all the λ’s are equal to 1 and focus on learning
entries of the payoff matrix P by exploiting the smoothness
of QRE solutions. This allows us to employ gradient-based
approaches (Amin, Singh, and Wellman 2016) for learning.
In this paper, we do not assume λ’s are known in our solution
concept and instead treat them as parameters to be learned.
The additional representation power brought by introducing λ’s to 1 cannot be achieved by a simple scaling of thepayoff matrix in the original formulation by Ling, Fang,
and Kolter, even in the non-nested, simultaneous move normal form settings. To see why this is so, consider the gameof symmetric rock-paper-scissors with non-uniform rewards(i.e., the payoffs for winners depend on their specific action).
Suppose the game is played between ‘strong’ and ‘weak’
players, and this is reflected by low and high λ parametersrespectively. Due to differing λ’s for each player, the strategies of the two players in equilibrium are different. However,scaling P , or even changing individual payoffs for winners(while maintaining symmetry) can only result in symmetricequilibrium.
Remark 1. Readers familiar with nested logits may recall
that the most common form of nested logits do not admit
chance nodes (or in our 2-player setting, parallel information sets). It may be shown that there is a natural way of
doing so by considering representing each alternative as apure strategy in the reduced normal form, and by nestingeach action based on the information sets which have a nonzero probability of being reached. The details are presented
in the appendix.
Remark 2. The expression in (2) is fairly general. Broadly
speaking, our framework allows for 2 types of nesting. First
we allow for nesting via information sets (i.e., each information set gets its own λ, see Remark 1), and second, by clustering actions within an information set, which is achievedby introducing intermediate information sets (e.g., the ‘redand blue bus’ example). Our experiments in Section 5 focus
on the former. However (2) and our proposed solver is able
to handle the latter case, assuming that the nesting structure
is known a-priori.

3.1

NLQRE solver

Following the ideas proposed by Ling, Fang, and Kolter,
we present a naive solver for the NLQRE based on
Newton’s method. Denote Ca and Ca0 as sets of possible0
information
P sets immediately following a or a . Define0Ja =h0 ∈Ca λh , and let ρa be the information set
immediately preceding the action a, i.e. h where a ∈ Ah .
The KKT conditions for (2) are, for all h0 ∈ Iv , a0 ∈ Ah0 ,and for all h ∈ Iu , a ∈ Ah ,Xua
) − Ja +µc − µh = 0
uph
c∈Ca
X
va0
) + Ja0 +νc − νh0 = 0(P T u)a0 − λρa0 (1 + log
vph0(P v)a + λρa (1 + log

c∈Ca0

Eu − e = 0

F v − f = 0.

(3)

These are necessary and sufficient conditions for NLQRE,
implying that the NLQRE can be found by applying Newton’s method to (3), yielding the following updates
 

Ξ(u)
P
E 0
∆u
T
−Ξ(v) 0 F   ∆v P
= −g(u, v, µ, ν), (4) ET
00 0  ∆µ
T
∆ν
0
F
0 0
 λρ +P 0ah ∈Ca λh0

, a=b

ua
where Ξ(u)ab = − λuρa , pρa = b,(5) λρbb− ua , pρb = ag(u, v, µ, ν) contains terms in (3) and Ξ(v) is defined analogously in terms of the appropriate v and λ’s. Observethat Ξ(u) and Ξ(v) are diagonally dominant and symmetric, implying that they are positive definite. In the back-ward pass, we require the gradients of the loss L with respect to P and λ. Similar to prior work (Gould et al. 2016;
Amos and Kolter 2017; Ling, Fang, and Kolter 2018), thismay be done by applying the implicit function theorem orby simply manipulating differentials. This yields the gradients ∇P L = yu v T + uyvT ; ∇λh L = κTh yu for h ∈ Iu ,∇λh L = −KhT yv for h ∈ Iv , where
1 + log(ua /upρa ),ρa = h(6)(κh )a =−1,
h ∈ Ca
1 + log(va /vpρa ),ρa = h(Kh )a =(7)−1,
h ∈ Ca

  
−1 
−Ξ(u)
P
E 0
−∇u L
yu
Ξ(v) 0 F  −∇v L yv   P T. (8)y  =  E T
0
0 0  0 
µ
0
yν
0
FT
0 0

4

Fast forward and backward pass solvers

In the framework of Ling, Fang, and Kolter, each gradientstep in Algorithm 1 involves solving an optimization problem. Thus, having efficient solvers is crucial in scaling up. In
the naive solver, the forward pass is solved using Newton’s
method and we need to solve the system of linear equations(5) in each iteration. When the game tree is large, solving
the system of linear equations in (5) multiple times dramatically slows down training. Similarly for the backward
pass, one needs to solve a single linear system shown in (8).
When the game is large, naively solving the linear system isalso prohibitively slow, even when utilizing sparse matrices.
This serves as motivation for a first-order iterative method(FOM) which do not require the solution of a linear system
as a subroutine. FOMs are also computationally attractive
for solving extensive form games because of the underlying
tree structures in games which may be exploited. We will
focus on optimization problems in the following min-max
form.
min max xT P y + E(x) − F(y),Ex=x0 F y=y0(9)where E(x) and F(y) are strictly convex functions. It is obvious from (2) that the forward pass in our problem solves
a problem in this form. We will show later that the backward pass problem shown in (8) can also be seen as solving
a problem in this format.
Many methods to solve (9) have been proposed. In this paper, we adapt the method proposed by Chambolle and Pock
(2016)3 . This, as well as many other first order methods apply best response subroutines towards smoothed versions of
the min or max original problem taken in isolation. The solution is obtained by alternating between best-responses tominimization and maximization. Algorithm 2 gives the highlevel overview of the optimization procedure, where BR aresmoothed best responses with appropriately chosen Bregman divergences Dx , Dy , their associated convex functions
3
Note that the algorithm by Chambolle and Pock is more general and applies beyond game solving.

Ψx , Ψy , and ‘step sizes’ τ, α.
1
Dx (x, x̄)τ1
BRy (ȳ, x̃) = arg min −x̃T P y + F(y) + Dy (y, ȳ).
σF y=y0BRx (x̄, ỹ) = arg min xT P ỹ + E(x) +Ex=x0

We first set τ = σ for convenience. For Algorithm 2
to be practical, we will require the best response oracles
BRx , BRy to be computed efficiently. By setting Dx (x, x̄)and Dy (y, ȳ) to be of specific form similar to E(x) and F(y)respectively will simplify BRx and BRy to be (up to a factor)of the forms
arg min xT cx + E(x) andarg min y T cy + F(y),Ex=x0

F y=y0which are efficiently computed by exploiting the structure of
the problem in extensive form games. This avoids the need tosolve a linear system with P as part of the design matrix. The
remainder of this section outlines the procedures requiredfor both forward and backward passes. For brevity, we discuss this from the view of the minimization – the maximization subroutine is entirely analogous. Lastly, we remark thatthe computational advances in this section are independentof the NLQRE, i.e., they remains applicable to the originalframework of Ling, Fang, and Kolter.
Algorithm 2: FOM method to solve (9)Input: x(0) , y (0) , P, τ, σfor i in {0, . . . } doỹ = y (i) ;x(i+1) = BRx (x(i) , ỹ; P, τ );x̃ = 2x(i+1) − x(i) ;y (i+1) = BRy (y (i) , x̃; P, σ);endForward Pass For this section, the u = x, v = y whenreferring Algorithm 2. Setting E(u), F(v) to be the entropy
terms in (2) and u0 = e, v0 = f gives the expression in
the form of (9). The natural divergence to be chosen is thestandard entropy divergence adapted to the dilated setting(dropping terms in Du which do not contain u).
XXuaΨu (u) = E(u) =λhua log
uph
h∈Iu

a∈Ah

Du (u, ū) = Ψu (u) − uT Ψ0u (ū)
Xūa
Ψ0u (ū) = λρa −λh0 + λρa log
ū
pa
0
h ∈Ca

where a similar expression holds for Dv (v, v̄). Plugging into
the expression for BRu givesτuT (P ṽ + Ψ0u (ū)) + E(u).
BRu (ū, ṽ) = arg min
Eu=e 1 + τ
It is known that, BRu (ū, ṽ) may be solved by a single
bottom-up traversal of the game tree and a single sparsematrix-vector multiplication (Hoda et al. 2010). At each information set , we solve for the ‘behavioral’ best response(i.e., assuming that information set was the root). Each ofthese sub-problems may be expressed in closed form using log-sum-exp and softmax functions. The sequence form
is recovered from behavioral strategies with a single downwards traversal of the tree. The precise details are containedin the appendix.
Backward Pass The backward pass also requires solving
a linear system to obtain [yu yv yµ yν ]. We first begin bymaking the crucial observation that the (necessary and sufficient) KKT conditions of the following optimization problem is precisely the linear system in (8).
1
1
xT P y + xT Ξ(u)x − y T Ξ(v)y2
2TT+ ∇u L x + ∇ v L ysubject to Ex = 0
F y = 0.
(10)
min maxxyNote that u and v are constants in the backwards pass,here we are optimizing over x, y, which are not probabilities. Since Ξ(u) and Ξ(v) are positive definite, this isa convex-concave problem of the form required by Algorithm 2. We select the natural distance generating function
Ψx = 12 xT Ξ(u)x which yields (ignoring terms containing
only x̄),1 T
x Ξ(u)x − xT Ξ(u)x̄2Plugging this into the expression for BRx (x̄, ỹ) and rearranging gives
Dx (x, x̄) =1
1
τ
xT (∇u L + P ỹ − Ξ(u)x̄) + xT Ξ(u)x
1+τ
τ
2
(11)

τ
Letting c = 1+τ
∇u L + P ỹ − τ1 Ξ(u)x̄ in (16) gives the
KKT conditions
arg min
Ex=0c + E T γ + Ξ(u)x = 0,

Ex = 0where γ are Lagrange multipliers. Multiplying by EΞ−1 (u)gives a linear system in γ
EΞ−1 (u)c + EΞ−1 E T γ = 0.

(12)

After solving for γ, one may solve for xx = Ξ−1 (u) −c − E T γ .

(13)

Proposition 1. Solving for γ and x in Equations (12) and(13) require linear time (in the size of the game tree).
The derivation involves exploiting the tree-structure inherent in extensive form games. Computational details andproofs are deferred to the appendix.

5

Experiments

The proposed first order method was implemented using
Cython. We chose to do so since the best-response subroutines require tree-traversals, which are expensive in Python.
while the second order method used the Numpy and Scipy

libraries for the solution of linear systems. Where possible,
we utilized the Scipy sparse matrix library. This was seen
to provide a significant speedup for sparse P for both our
method and Newton’s method. The PyTorch automatic differentiation library (Paszke et al. 2017) was used to automatically obtain gradients for components outside the gamesolving module.

5.1

Synthetic datasets

Here we use randomly generated extensive form games toillustrate the computational efficiency of our proposed firstorder method compared to the second order method usedby Ling, Fang, and Kolter. We evaluate the solvers for theforward and backward passes in isolation. The experiments
are run over several depths d. Normal form games haved = 1. When d > 1, we adopt the following extensive
form game. players play d distinct simultaneous sub-games
in succession, where each simultaneous sub-game has n̂ actions. Transitions to the next sub-game is governed by thejoint action by both players, i.e., the size of P will be exponential in d. The payoff matrices P were generated with each
non-zero entry uniformly chosen from [−10, 10], and rationality parameter λ for each information set uniformly andindependently chosen between [0.9, 1.1]. All timings presented are wall-clock timings. Experiments are run on thecloud with identical Amazon EC2 instances. We set τ = 0.1
for all evaluations.
Evaluation of forward passes In the forward pass, we
compared the baseline Newton solver to our proposed firstorder method. However, the termination criterion for the 2
methods are non-identical; as Newton’s method minimizes
the residual rather than duality gap. To strike a fair comparison, we evaluated the 2 methods by first running Newton’s
method till a residual of less than 10−3 is achieved. The duality gap of that solution is computed and subsequently usedas the termination criterion for the FOM4 . The timings andspeedup are averaged over 50 trials and presented in Figure 2.
Evaluation of backward passes In the backward pass, thecomparison for our proposed FOM is against solving the linear system in (8) directly. In the loss function, we will concern ourselves with the setting where the true matrix P and λparameters are used in computing u, v for the forward pass.
This corresponds to the case the model is already fairly welltrained. The results over 50 trials are presented in Figure 3.
It is clear from both figures that our method scales muchbetter than Newton’s method for randomly generated matrices. Speedups of more than an order of magnitude are
fairly common, and the improvement increases with problem size. Furthermore, it was also observed that our method
consumed far less memory than sparse solvers. In fact, solving the sparse system when d = 3, n̂ = 17 (not plotted) required more than 10GB of memory. On the other hand, ourFOM was able to solve such instances in less than a minute,4

On occasion, the Newton solver gave a gap extremely close
to numerical precision. In these cases, we apply to a termination
criterion of 10−12 .

Figure 2: Timings (left) and speedup (right) for forward
passes. From top to bottom, d = 1, 2. Error bars represent
1 standard deviation. Dotted lines are optimal results given
the ground truth.
and with no noticeable increase in memory usage. Note that
P contains more than 1.4 million rows and columns in thissetting.

5.2

One-Card Poker

Here we evaluate our method on the game of one card poker.
This multi-card extension of Kuhn poker contains most interesting strategic elements of game playing (e.g., bluffing)
and was used by Ling, Fang, and Kolter to illustrate that it
is possible to learn distribution of cards in a deck just by observation player actions. However, the authors worked only
on tiny settings with just 4 cards – in sequence form, player
strategies may be represented in a 16 dimension vector. Furthermore, the authors assumed that there were no varying
input features (i.e., the card distributions were identical foreach action observed). These assumptions enabled them toachieve significant speedup by solving the game just oncein the forward pass, rather than once for each point in themini-batch. As we will see, their solver is too slow to be ofpractical use in larger or featurized settings.
Here, we operate in a slightly different setting. Instead oftrying to learn underlying card distributions, we learn player
rationality parameters. We assume that player rationality is
independent of the cards being drawn, and only depends on
the past actions of (both) players. In this setting, there arejust 4 parameters to be learned. This is independent of thesize of the deck.
We generate our data assuming that player rationality issome linear function of a scalar feature, i.e., there are 4
weights to be learned. The weight vector is drawn uniformly
from [0, 0.01]. Feature vectors are drawn between [0, 1]. Ourmodel is λh = wi ×f +λ . The addition of a small λ ensuresthat the λ’s will always remain positive; in our experiments,
λ = 0.001. For each feature, we compute the λ’s and findits corresponding equilibrium from which we sample player
actions. The training set of size 2000, with an independent
test set of size 1000. We minimized the log loss using theAdam optimizer with a batch size of 64 and learning rate of
10−4 .

Figure 3: Timings (left) and speedup (right) for backward
passes. From top to bottom, d = 1, 2, 3. Error bars represent
1 standard deviation. Dotted lines are optimal results given
the ground truth.

We compared our solver against Newton’s method, which
terminates at a residual of 10−8 . We fixed τ = 1 for theforward solver and τ = 0.1 for the backward solver. The
results are plotted in Figure 4.
In all 3 cases, both the log-loss is close to optimal given
around 30 epochs. As expected, our exacts solver exhibits
behavior almost identical to that of Newton’s method on aper-epoch basis. Our solver is significantly faster than thebaseline. It was observed that at almost all stages of training,
Newton’s method took almost 2 orders of magnitude timein order to learn a model of similar performance. In fact, asingle epoch using Newton’s method takes as much time astraining the entire model using our solver.

Figure 4: Left: log-loss and mse per epoch, Right: time required to obtain a particular log loss or mse. Dotted lines are
optimal results given the ground truth.

U NIFORM
N O F EAT
F EAT

loss
1.833
1.422
1.419

loss(1)
1.099
0.878
0.874

loss(2)
1.099
0.863
0.866

loss(3)
1.099
0.826
0.818

loss(4)
0.693
0.130
0.145

Figure 5: Log losses for the information gathering dataset.
The first column shows losses over the whole game, othercolumns show losses for individual stages.

5.3

Information gathering dataset

Here we demonstrate the applicability of the nested logit
model (i.e., a one player game) using a publically available
dataset (Hunt et al. 2016). The game proceeds as follows.
Suppose there are 4 faced-down cards ranging from 1-10
placed in a 2×2 matrix (with potential repetitions). The goalof the game is to select the row containing cards with thelargest sum. The game proceeds in 4 stages. At each stageof the game, the player may make a guess prematurely, orspend some points in revealing a new card. At the fourth andfinal stage, the player has to make a guess. The player obtains a reward of 60 and -50 points for correct and incorrect
guesses, and may only guess once. The challenge is for theplayer to judge if it is worth paying to gather more information. Computationally, the optimal policy may be easily
obtained using dynamic programming.
However, humans are rarely perfectly rational. We model
bounded rationality using the nested logit model. It is assumed that the level of rationality should be a function ofa) how many cards are already open, and b) side information such as one’s educational qualifications. This leads toa natural description of the game with 4 different λ’s, eachof which is some function of features, which we describe
below.
Two models are trained for this experiment. N O F EAT
refers to the case when there are no features (i.e., we aresimply learning λ) and F EAT when we are exploiting demographic information. In this case, features comprise theplayer’s academic qualifications and age, both with one-hot
encodings. A player’s age is split into 8 age ranges, and education levels follow that of the UK (i.e., GCSE, A levels,
Undergraduate, Graduate). Our model employs a neural network with 3 hidden layers of width 100, interspersed by rectified linear activations. To ensure λ’s are positive, all inputs
were exponentiated before being fed into the solver. Figure 5
shows the log loss over the overall game as well as the loss
at each individual stage. For comparison, we also provide
the results for a player who picks a random action at every
stage of the game. The learned λ parameters for each configuration of features is presented in Figure 6.
From Figure 5, we can see that both trained models significantly outperform U NIFORM. Log losses at each stage appear to decrease with the stage number. This is unsurprisingsince players behave more rationally (and hence predictably)
as more information is revealed. However, our model appears to perform worse at stage 4, which is in fact a problem
with full observability. We suspect this higher loss is a consequence of our model ‘overfitting’ to be overly confident at
the final stage, incurring a huge loss on the rare occasion a

Figure 6: Rationality parameters λ for each stage of thegame as a function of age and education. Stages are presented in row-major ordering. Note that ages are binned
within some range. All respondents below the age of 18 weregrouped together in a single age range.

player answers incorrectly.
Several trends are observed from Figure 6. First, noticethat λ decrease by approximately a factor of 10 between
stages. This is fairly expected, since each information gathering leads to 10 other potential states. Also unsurprisingly,
better educated respondents exhibit more rationality (recall
a lower λ implies a more rational player). Interestingly, we
can see a U-shaped trend in all stages, suggesting that people
in the mid twenties and thirties are most rational. Both theseobservations agree with the findings by (Hunt et al. 2016),
where it was shown that higher educated and middle aged
respondents obtained the most reward.

6

Conclusion

In this paper, we substantially improve upon existing workin differentiable game learning. We propose the NLQRE
which generalizes QRE and NL models. We also derive gradients for backpropagation and learning, and develop solvers
which lead to speedups of several orders of magnitude. Future work include the learning of game structure and extensions for general-sum games.

References
Amin, K.; Singh, S.; and Wellman, M. P. 2016. Gradientmethods for stackelberg security games. In Conference on
Uncertainty in Artificial Intelligence, 2–11.
Amos, B., and Kolter, J. Z. 2017. Optnet: Differentiable
optimization as a layer in neural networks. arXiv preprint
arXiv:1703.00443.
Blum, A.; Haghtalab, N.; and Procaccia, A. D. 2014. Learning optimal commitment to overcome insecurity. In Advances in Neural Information Processing Systems, 1826–
1834.
Chambolle, A., and Pock, T. 2016. On the ergodic conver-gence rates of a first-order primal–dual algorithm. Mathematical Programming 159(1-2):253–287.
Gould, S.; Fernando, B.; Cherian, A.; Anderson, P.; Cruz,
R. S.; and Guo, E. 2016. On differentiating parameterizedargmin and argmax problems with application to bi-level optimization. arXiv preprint arXiv:1607.05447.
Hoda, S.; Gilpin, A.; Pena, J.; and Sandholm, T. 2010.
Smoothing techniques for computing nash equilibria ofsequential games. Mathematics of Operations Research
35(2):494–512.
Hunt, L. T.; Rutledge, R. B.; Malalasekera, W. N.; Kennerley, S. W.; and Dolan, R. J. 2016. Approach-induced
biases in human information sampling. PLoS biology
14(11):e2000638.
Ling, C. K.; Fang, F.; and Kolter, J. Z. 2018. What gameare we playing? end-to-end learning in normal and extensive
form games. arXiv preprint arXiv:1805.02777.
Luce, R. D. 2012. Individual choice behavior: A theoreticalanalysis. Courier Corporation.
McKelvey, R. D., and Palfrey, T. R. 1995. Quantal response
equilibria for normal form games. Games and economic behavior 10(1):6–38.
Mertikopoulos, P., and Sandholm, W. H. 2016. Learning ingames via reinforcement and regularization. Mathematics ofOperations Research 41(4):1297–1324.
Paszke, A.; Gross, S.; Chintala, S.; Chanan, G.; Yang, E.;
DeVito, Z.; Lin, Z.; Desmaison, A.; Antiga, L.; and Lerer,
A. 2017. Automatic differentiation in pytorch.
Thurstone, L. L. 1927. A law of comparative judgment.
Psychological review 34(4):273.
Train, K. E. 2009. Discrete choice methods with simulation.
Cambridge university press.
Tversky, A. 1972. Elimination by aspects: A theory ofchoice. Psychological review 79(4):281.
Von Stengel, B. 1996. Efficient computation of behavior
strategies. Games and Economic Behavior 14(2):220–246.
Vorobeychik, Y.; Wellman, M. P.; and Singh, S. 2007. Learning payoff functions in infinite games. Mach Learn 67:145–
168.
Waugh, K.; Ziebart, B. D.; and Bagnell, J. A. 2011. Computational rationalization: the inverse equilibrium problem.
In Proceedings of the 28th International Conference on International Conference on Machine Learning, 1169–1176.
Omnipress.

Appendix
Best response of the NLQRE as a nested logit
Here we show that the best-response in the NLQRE, which
may contain parallel information sets (either due to chanceor actions by other players) may be regarded as a nested
logit. The idea is to express each strategy in the reduced normal form into a sequence of decisions, each describing what
is to be done in each parallel information set.
Consider the following game in Figure 7. Chance (or theother player), labelled as (2), first chooses out of 2 actions,which is made known to the player. For example, this could
be the private cards which are dealt to a player in a game ofpoker. The nodes T1 and T2 are the subtrees following these2 actions by the chance player.

parameters for the roots of all copies T20 to be λ2 and the rationality parameter at T10 to be λ1 yields precisely one-player
version of the optimization problem in (2), since the objective in each copy of T20 is identical and their coefficients sum
to 1. Recursively applying this process bottom up to each
subtree (i.e., making duplicate copies of subtrees whenever
we encounter parallel information sets) gives the desired result.

Figure 8: Player’s decision tree. Red and blue components
are decision trees for the player. Each leaf (or path from theroot to a leaf) is a pure strategy in the reduced normal formof the game in Figure 7.

Figure 7: Full 2-player game tree. The first action is performed by chance (or the other player). The player has toprovide for contingencies in both the red and blue trees.

Observe that each pure strategy (path) in Figure 8 is a purestrategy in reduced normal form. However, each path may
pass through different information sets (for example, when
there is nesting of actions in the bus example), and hence
different λ parameters. This is in line with what one would
expect with nested logits.

Fast forward and backward pass solvers
Without loss of generality, let T10 and T20 be the tree representation of the player’s strategies in subgame T1 and T2 ,i.e., T10 and T20 are decision trees for the player. Given thatchance could have chosen either action to begin with, thepure strategies are the cross product of all strategies between
T10 and T20 , i.e., the player has to account for all possible contingencies. This may be written as a 2-stage decision process
in Figure 8, where the first and second stages are choicesfrom T10 and T20 respectively, where T20 is duplicated nleaves
times, where nleaves is the number of possible leaves for T10 .
The rewards are additive in each stage, implying that thebest response for each of the duplicated trees are identical.
(Note however that the actual payoffs are modulated by theprobability of the chance player choosing the left or rightaction, but this factor is identical for each copy of T20 ). Furthermore, the leaves of T10 form a probability vector (since
T10 is a decision tree). This implies that setting the rationality

In this section, we provide the complete computational details and proofs with regard of how to compute best responses for the forward and backward passes.
Forward Pass For this section, the u = x, v = y whenreferring to Algorithm 2. Setting E(u), F(v) to be the entropy terms in (2) and u0 = e, v0 = f gives the expression
in the form of (9). The natural divergence to be chosen is thestandard entropy divergence adapted to the dilated setting(dropping terms in Du which do not contain u).
XXuaΨu (u) = E(u) =λhua log
uph
h∈Iu
T

a∈Ah

Ψ0u (ū)Du (u, ū) = Ψu (u) − uXūaΨ0u (ū) = λρa −λh0 + λρa log
ū
pa
0
h ∈Ca

where a similar expression holds for Dv (v, v̄). Plugging into
the expression for BRu givesτBRu (ū, ṽ) = arg minuT (P ṽ + Ψ0u (ū)) + E(u).
1
+
τ
Eu=e
It is known that, BRu (ū, ṽ) may be solved by a single
bottom-up traversal of the game tree and a single sparse
matrix-vector multiplication (Hoda et al. 2010). At each information set , we solve for the ‘behavioral’ best response(i.e., assuming that information set was the root). Each ofthese sub-problems may be conveniently expressed using
log-sum-exp and softmax functions. Denoting cu = P ṽ +
Ψ0u (ū), we compute


X ua
X
ua
T
λh uphmin u cu +
log,u,Eu=e
uph
uph
h∈Iu

a∈Ah

where the constraint that u > 0 is implicit from the log barrier.
Optimization of the inner summation, along with the relevant part of the inner product may be done in closed form
using log-sum-exp. The tree constraints for u allows them toperform traversals bottom up. Throughout the traversal process, denote zh as the ‘value’ of each infoset h and ra as thevalue of eachaction.

 
X
X
ra 
zh = λh log exp, ra = −ca +
zh
λh
ρ =i
a

h∈C(a)The behavioral strategies ûa may be expressed using thesoftmax function. For an action a belonging to info set h,exp(ra /λh )(14)ûa = P0
a0 ∈Ch exp(ra /λh )The sequence form may be recovered from behavioral strategies using a single downwards traversal of the tree.
Backward Pass The backward pass also requires solving
a linear system to obtain [yu yv yµ yν ]. By rewriting thelinear system as another min-max problem, we may again
apply Algorithm 2. Observe that the solution to the system
are precisely the (necessary and sufficient) KKT conditionsof the following min-max problem
1
1
min max xT P y + xT Ξ(u)x − y T Ξ(v)y
x
y
2
2
T
T
+ ∇u L x + ∇ v L ysubject to Ex = 0
F y = 0.
(15)Note that u and v are constants in the backwards pass, here
we are optimizing over x, y, which are not probabilities.
Since Ξ(u) and Ξ(v) are positive definite, this is of the form
required by Algorithm 2. We select the natural distance generating function Ψx = 21 xT Ξ(u)x which yields (ignoringterms containing only x̄),1
Dx (x, x̄) = xT Ξ(u)x − xT Ξ(u)x̄2Plugging this into the expression for BRx (x̄, ỹ) and rearranging givesτ1
1
arg minxT (∇u L + P ỹ − Ξ(u)x̄) + xT Ξ(u)xτ
2
Ex=0 1 + τ(16)

Proposition 1 Solving for γ and x in Equations (12) and(13) require linear time (in the size of the game tree).
Proof. To obtain efficient solutions for the best responses,
we require the following handy results, which may all beverified by algebraic manipulation.
Lemma 2. Ξ−1 (u)E T = α1 , α2 , . . . , α|Iu | , where αi ’s
are column vectors of size equal to number of actions, andcontain ua /λh ’s where a is some descendent of information
set i, and 0 otherwise.
−1
Takingtransposes gives the following, EΞ (u) is equalto β1 , . . . , β|Au | , where the βa ’s are column vectors oflength equal to |Iu |, and have entries equal to λuha if the index
i is an ancestor of a.

Lemma 3. EΞ−1 (u)E T = diag({uph }), i.e. equal to asquare matrix of size |Iu |, with diagonal entries equal to theu ph
λh corresponding to a given information state’s parent action.
Lemma 4. For any vector c, EΞ−1 (u)c may be computedin linear time by traversing the tree bottom-up.
We are now ready to provethe main theorem. Letting c =∇u L + P ỹ − τ1 Ξ(u)x̄ in (16) gives

τ
1+τ

1
BRx (x̄, ỹ) = min xT c + xT Ξ(u)x,x,Ex=02(17)which has KKT conditions
c + E T γ + Ξ(u)x = 0
Ex = 0(18)(19)

Multiplying by EΞ−1 (u) givesEΞ−1 (u)c + EΞ−1 E T γ = 0(20)Note that we should not have introduced new roots in doing so, since these are linear systems and there is a uniquesolution to γ both before and after the multiplication. Applying Lemma 2 and Lemma 3 gives an expression for γ.
Lemma 4, together with the fact that EΞ−1 E T is diagonal
implies that γ may be solved for in linear time. The computation of c requires P y, which may be done in time linear in
the size of the extensive form game tree. In the extreme case,the game could be a single-stage simultaneous move game,
resulting in P being dense. However, for typical EFGs, P
should be fairly sparse.
With γ, we may solve for xx = Ξ−1 (u) −c − E T γ(21)Since Ξ(u) is tree-structured, the inversion may be done inlinear time using Gaussian Elimination. Similarly, E T γ may
be computed in linear time because of sparsity in E. That is,
the number of non-zero elements in E is equal to the sum of
the number of actions over all information sets (recall thateach row in E has non-zero entries for the actions for a given
information set and its parent).