Abstracting Imperfect Information Away from Two-Player Zero-Sum Games
Authors: Samuel Sokota
Ryan D'Orazio
Chun Kai Ling
David J Wu
J Zico Kolter
Noam Brown
Venue: Submitted to ICLR 2023 (2023)
Keywords: imperfect information
public belief states
decision-time planning
regularized equilibria

Abstract: In their seminal work, Nayyar et al. (2013) showed that imperfect information can be abstracted away from common-payoff games by having players publicly announce their policies as they play. This insight underpins sound solvers and decision-time planning algorithms for common-payoff games. Unfortunately, a naive application of the same insight to two-player zero-sum games fails because Nash equilibria of the game with public policy announcements may not correspond to Nash equilibria of the original game. As a consequence, existing sound decision-time planning algorithms require complicated additional mechanisms that have unappealing properties. The main contribution of this work is showing that certain regularized equilibria do not possess the aforementioned non-correspondence problem---thus, computing them can be treated as perfect information problems. This result yields a simplified framework for decision-time planning in two-player zero-sum games, void of the unappealing properties that plague existing decision-time planning algorithms.

Under review as a conference paper at ICLR 2023
ABSTRACTING IMPERFECT INFORMATION FROM TWO-PLAYER ZERO-SUM GAMES
AWAY
Anonymous authors Paper under double-blind review
ABSTRACT
In their seminal work, Nayyar et al. (2013) showed that imperfect information can be abstracted away from common-payoff games by having players publicly announce their policies as they play. This insight underpins sound solvers and decision-time planning algorithms for common-payoff games. Unfortunately, a naive application of the same insight to two-player zero-sum games fails be- cause Nash equilibria of the game with public policy announcements may not correspond to Nash equilibria of the original game. As consequence, existing sound decision-time planning algorithms require complicated additional mech- anisms that have unappealing properties. The main contribution of this work is showing that certain regularized equilibria do not possess the aforementioned non-correepondeece troblem-thus, computing them can be treated perfect in- formation problems. This result yields a simplified framework for decision-time planning in two-player zero-sum games, void of the unappealing properties that plague existing decision-time planning algorithms.
INTRODUCTION
In single-agent settings, dynamic programming (Bertsekas 2000) serves bedrock for reinforce- ment learning (Sutton& & Barto 2018), justifying approximating optimal policies by backward induc- tion and facilitating simple framework for decision-time planning. One might hope that dynamic programming could also provide similar grounding in multi-agent settings for well-defined notions of optimality, like optimal joint policies common-payot games, Nash equilibria in two-player zero-sum (2p0s) games, and team correlated equilibria in two-team zero-sum (2t0s) games. Unfor- tunately, this is not straightforwardly the case when there is imperfect information ciarmationn...... one player has knowledge that another does not two players act simultancously. This difficulty arises from two causes, which we call the backward dependence problem and the non-correspondencc problem.
Nayyar et al, 2013
Markov Decision Processes
Common- Payoff Games
Carminati et al, 2022: Zhang et al, 2022
Two-Team Zero-Sum Games
Two-Player Zero-Sum Games
Alternating Markov Games
Correlated
Imperfect
Fully Observable
Optima
Information
Figure Our contribution in the context related work, an abstract level.
The backward dependence problem that computing the expected return starting from a decision point generally requires knowledge about policies that were played up until now, in addition the

---

Under review as a conference paper at ICLR 2023
policies that will be played going forward. This is in stark contrast to perfect information settings, in which the expected return starting from a decision point is independent of the policy played before arriving at the decision point. As a result of this bidirectional temporal dependence, backward induction arguments that work in perfect information settings fail imperfect information settings.
In their seminal work, Nayyar al. (2013) showed that the backward dependence problem can be resolved by having players publicly announce their policies as they play. Using this insight, common-payoft game can be transformed into public belief Markov decision processes (PuB- MDP). Importantly, deterministic optimal policies in the PuB-MDP can be mapped back to optimal joint policies of the original common common-payoff game.
Having players publicly announce their policies can also be used to transform 2p0s games into alternating Markov games (AMGs) with public belief states, which we call public belief alternating Markov games (PuB-AMGis AMGs are fully observable turn- based games (like Go and chess) and, therefore, are amenable to dynamic programming- based approaches (Littman 1996). Unfortunately, computing Nash equilibria of PuB-AMGs carries little value because these Nash equilibria may not correspond with Nash equilibria in the original game (Ganzfried Sandholm, 2015 Brown et al.) 2020). Indeed, as we will show, they may correspond with arbitrarily exploitable policies. We call this problem the non correspondencce problem.
The main contribution of this work is showing that regularized minimax objectives that guarantec unique equilibria subgames do not suffer from the non-correspondence problem. In other words, computing these uniqueness guaranteeing equilibria be reduced computing the associated equilibria in the PuB-AMG. Because guaranteeing uniqueness is as simple as adding entropy regu- larization (Perolat al. 202T our result straightforward apply in practice.
We view the primary importance of this reduction from imperfect information 2p0s games to perfect information games three fold.
1. It is the first known reduction of its kind; specifically. it is the first regularized equilibrium preserving transformation from imperfect information 2p0s games to perfect information 2p0s games that is meaningful in the sense that regularized equilibria can be made arbitrarily close to Nash equilibria.
2. It yields simple framework for decision-time planning in 2p0s games. The simplicity of this framework in stark contrast to existing approaches (Brown Sandholm] 2217a by Moravčík
al. 2017 Brown et al. 2020 Schmid et al. 2021), which are hampered by complications that involve undesirable facets, such as discontinuous functions.
can be applied across the whole class of 210s games (as depicted in Figure I because of the recent results of CCrmminati et al.] (2022a); Zhang et al. (2022); Carminati et al. (202bb), who showed that 2t0s games can be cast as 2p0s games.
NOTATION
2.1
-ORIIZN SEQUENTIAL GAMES
We use the terminology finite-horizon sequential game to describe settings in which players act one- at-a-time and in which the game terminates after a fixed number of steps. This setting can express any simullaneous-move timeable perfect-recall finite-horizon game. See, for example, Kovarík et al. (2019) for more details.
Symbolically, we say setting is finite-horizon sequential game if it can be described by tuple (A, [O.], Opab. [H]]], Hpub: IH, μ. [O.], Pub. [R.], T.T).
where
ranges from 0 to N and E {O...., 13 denotes the acting player]
A is the set of actions.
O2 the set of private observations for player i.
Opub is the set of public observations (common knowledge to all players).
"Our usage of is informal hut unambiguous in context.
2

---

Under review as a conference paper at ICLR 2023
H T-1 pub 0,)² pub O, is player i's action-observation histories (AOHs).
1=n
Hlpub - pub is the of public histories.
H C Hig X... - is the set of histories.
14 E A (IHbl(/ppb) x ..... x H (Aubb) is the initial history distribution.
O H + O; is player i's observation function
Opub : H + Pab is the public observation function.
R.: IH A IR is the player i's reward function.
T: H x A + A (IH)) is the transition function.
T is the time horizon which the game terminates.
For given pub E pab- we use HH, (hpub) to denote the set of AOHs for player that are consistent with pob and (((ghub)) to denote the set of histories that are consistent with hpub- Also, for a history h, we use h, to denote the AOH for the acting player at history h. We use capitals of the same letters denote random variables of the same types.
Special Cases This work will make use of the following special cases.
1} disjoint union of two blocks, where Vi,j. R2 = R, if j.j belong to the same block and R. = -R, i, belong to opposite blocks.
Two team zero sum: Games in which {0.... (O.....)
Common payoff:: Games in which Vi, j, R; R,
Two player zero sum: Games in which N = 2 and Ra = R1.
In these special cases, the reward of all players is uniquely determined by the reward of any individ- ual player. Thus, we will drop the player index i on the reward function and use R. Ro-
Subgames For given finite-horizon sequential game, we use the term subgame refer to a game that begins with initial history distribution A (Mipu)))) x N 1 (Appb) for some particular pub and is otherwise the same as the original game.
2.2 FINITE-HORIZON FULLY OBSERVABLE SEQUENTIAL. GAMES
We also introduce specialized notation for fully observable settings. We use the terminology finite- horizon fully observable sequential game to describe tuples
(A, S, S,, [R,), T,T),
where
S is the set of states.
s E S is the initial state.
R2 S x A +
the player i's reward function.
T: S x + (SS) is the transition function.
i, i, A., and 7 are defined they were in the finite-horizon sequential game formalism.
Special Cases In the fully observable context, we are interested in the following settings.
Markov decision processes (MDPs): Games in which N
Alternating Markov games (AMGs): Games that are two player zero sum.
As before, because the reward of one player uniquely determines the others in these settings, we will use R Ro.
Subgames For given finite-horizon fully observable sequential game, we use the term subgame to refer to game that begins with initial state s = s for some particular and otherwise proceeds by same rules of the original game.
BACKGROUND
The Backward Dependence Problem To illustrate the presence the backward dependence prob- lem in very simple settings, show cooperative matching pennies game in Figure [ The goal of the game is for the blue player and the red player to select the same side of coin. The
We that, if time i's action included in its private observation time
3

---

Under review as a conference paper at ICLR 2023
blue player moves first; then, without observing the blue player's choice, the red player moves ond. Because the red player does not observe the blue player's s choice (as denoted by the dotted line between the two nodes), it must make the same decision at both nodes.
Now, let us consider the value for the red player. In perfect-information settings, because the red player is at a penultimate decision point, such value would be equal to the expected return for the best action, independent of any prior events. However, here, with imperfect information, the expected return for the best action is equal to max(p, 1-p) p) where p is the probability that the blue player selects heads. If the blue player's s policy is unknown, there is no way to compute this value, illustrating that the backward induction approach to learning in perfect information settings fails in imperfect information settings.
The Public Belief Markov Decision Process We now describe Nayyar et al. (2013)'s 's trans- formation for turning common- paanoff---oofff- games into public belief MDPs (called PuB-MDPs) in such a way that circumvents the backward dependence problem. Let
Tails
Heads
(A,, [O,], pubb [H,], pulp IHI, μ4, [O,], Opb, R, T.T.))
be mnite-horizon common-payoff game. Then we define the associated PuB-MDP as the fol- lowing finite-horizon fully observable sequen- tial game
Tails
Heads
Tails
Heads
1,1
0,
0, O
1,
",,
Figure 2: The best action for the red player de- pends on the blue player's policy.
where
i L = 0.
Å {ā à: H,, (Ripb) + A. hpub Hppb) is the set of prescriptions.
$ Uh (Hmb)) is the set public belief states (PBSs).
fu is the initial PBS.
R: ă, +r, where = RSHNRR(H,
(8,,41 (8 = P(opute 8²,ū)= = B EA P(o 2+1 Pub
AT) where the PBS & 8,e4a 2
is
pp
defined by 6 (1*+1)= = P(h++ 8t, ā, optit) B BANH P(h H A (41)
T T.
Nayyar et al. (013)) showed that optimal deterministic policies the PuB-MDP correspond with optimal joint policies for the common payoff game. Indeed, for the matching pennies game de- scribed in Figure 2 we can see that the PuB-MDP perspective resolves the backward dependence problem because the red player observes the blue player's decision rule. If the blue player plays heads with probability p. the red player can achieve a value of max(p. 1 p) by best responding. By backward induction, the blue player can then determine that it is optimal use p 0 or p 1. Thus, the players can arrive at an optimal joint policy of the original game. For more detailed discussion on the PuB-MDP, see, e.g., (Sokota 2020 Sokota et al.) 2021).
4 THE PUBLIC BELIEF ALTERNATING MARKOV GAME
Here, we introduce construction analogous to the PuB-MDD that we call the PuB-AMG, Note that, while the name PuB-AN AM- novel to this work, the idea already exists in literature (Brown et al.) 2020 Buffer et al. 2020 Delage al. 202T) Let
(A, [O,]. O pab. [H]]]. Hppb, IH, μ1, [O.], Pub. R.J, T.T),
be a finite-horizon 2p0s sequential game. Then we define the associated PuB-AMG as the following finite-horizon fully observable sequential game
(A,5,5 R.
where
4

---

Under review as a conference paper at ICLR 2023
ranges from 0 to 1 and E {0, is the acting player.
(A)) pub Hugh) is the set of public decision rules (or decision rules, for short), Note that public decision rules differ from prescriptions in that they map to distribution over actions, rather than an action.
A {ā à: IHI, (Atghh)
S, 5 R. T, and T are defined in the same fashion as in the PuB-MDP.
The Correspondence Mapping As alluded to earlier, Nash equilibrium in the PuB-AMG may be undesirable because it does not necessarily correspond to Nash equilibrium in the original game. Here, we make precise the notion of what we mean by correspond by defining a correspondence function IT+ that maps public belief (joint) policies to joint policies of the original game. Given a PuB-AMG policy H. (T) is the joint policy that, for cach AOH h, plays actions with the probability that गे would hes assuming that h, was reached using म. (See Section [A] for more rigorous definition.) Importantly, (π); can be implemented in practice by running πi under the assumption that the opponent is playing according -
The Con-Correspondence Prob-
lem We can now make the non- correspondence problem precise. To illustrate, we show the perturbed vari- ant of rock-paper-scissore described in (Brown et al., 2020) in Figure In the game, the payouts are doubled either player plays seissors. The unique Nash equilibrium of the game (R, P) + (0.4, 0.2..
R
S
S
P
S
R
P
0,0
-
2, 2
1,-1
0.0
-2,2
-2,2
2.-2
0
Similarly to before, the red player can compute the associated value for each of the blue player's decision rules. Thus, the blue player can determine
Figure 3: A perturbed variant of rock-pappr-ssiissor..
that the Nash equilibrium policy maximizes its value. It is at this point that the non-correspooddece problem becomes apparent. Because the red player is conditioning on the blue player's 's decision rule, it achieves the the optimal value by playing any best response the red player. In the per- turbed vock-paper-scissors game, all policies are best responses to the Nash equilibrium. Thus, there is nothing constraining the red player the Nash equilibrium policy of the original game.
A similar argument, detailed in Section B.I leads to the following disappointing result.
Proposition A PuB-AMG Nash equilibrium â may correspond with a joint policy IT) that is maximally exploitable.
At an intuitive level, the non-correspondence problem arises because there is important distinction between the public belief game and the original game. Specifically, in the public belief game, players acting earlier are forced to reveal their decision rules players acting later. As result, later acting players are able to "slack off" without losing any value because the earlier acting players cannot deviate to exploit them. In common-payoff games, this is a non-issue because the interests of every player are aligned. However, in 2p0s games, where there are adversarial interests, this distinction changes the strategic nature of the game in a more fundamental sense.
CORRESPONDENCH OF UNIQUENESS GAAESSSTEAAAAGGINNG EQUILIBRIA
We will now show that the non-correspondennce problem does not exist for minimax objectives that guarantee unique equilibria in subgames of the original game. The class of minimax objectives we consider generalizes the expected return minimax objective in that it includes objectives that may have dependence on policies beyond the actions they select.
Definition 5.1. We use the term regularized minimax objective (or objective for short) to refer to mappings of the form
J: +E
Σ R(H A (HH)) To,
5

---

Under review as a conference paper at ICLR 2023
where Ri is real-valued function.
Definition 5.2. Given an objective 3 induced by for some game. we can construct an objective 5 for the associated public belief state game that is equivalent 3 in the sense that 3( (1)+ by defining
T Σ
3: No: #1 + E
A(S", A') Āo. $1
where
R: (5, + EH )
HH A, (HH)).
Next we formalize what we mean by uniqueness guaranteeing. Definition 5.3. For a particular game, we say minimax objective 3 is uniqueness guaranteeing if.
for any subgame,
max max 3(To, TT)
No
guaranteed to have a unique solution (To m1)
We can state our main result.
Theorem 1. If स is an equilibrium of PuB-AMG under uniqueness-uuarateer guaranteeing objective, then corresponding joint policy (f) is the equilibrium the original game under the same objective.
Proof. (Sketch) The first decision rule of any PuB-AMG equilibrium must correspond to the first decision rule of equilibrium of the original game. Furthermore, if the objective is uniqueness- guaranteeing, subgame equilibria must be restrictions of the equilibrium of the whole game. Thus, by forward induction, PuB-AMG equilibria must correspond to the equilibrium of the original game.
We detail the proof for Theorem I in Section to the entire class of 2t0s games.
B.2
Due to recent work, Theorem can be generalized
Corollary 1. Computing team-come leam-correlated equilibria of 2:0s games under a uniqueness guaranteeing objectives can be reduced to computing an equilibrium of a PuB-AMG under the same uniqueness guaranteeing objectives.
Proof. This follows immediately from chaining the results of Carminati et al. (2022a) Zhang et al. 2022); Carminati al. (2022b), who provide reduction from 210s games 2p0s games via intra- team public policy announcements, with Theorem
6 SUFFICIENT CONDITIONS FOR UNIQUENESS GUARANTEEING
Theorem I tells us that uniqueness guaranteeing is a sufficient condition to ameliorate the non- correspondence problem. We now discuss objectives that are uniqueness guaranteeing and general sufficient conditions for guaranteeing uniqueness.
Definition 6.1. We call the objective induced by
R: (h, 5) + RR(h, a) - aKL(), = 0
akL( == 1,
for some reference policy p. MiniMaxKL objective. Definition 6.2. We call the objective induced by
R((h,a) aH(( 0 (R(h.a)-aHk)
R: a,,
for some reference policy p. a MiniMaxEnt objective.
Remark 1. MiniMaxEnt is the special case of MiniMaxKL. in which p is uniform.

---

Under review as a conference paper at ICLR 2023
To our knowledge, MiniMaxKL objectives first introduced by Perolat et al. (2021) who showed the following result using Lyapumov techniques.
Theorem 2. (Perolat et al. 2021) MiniMaxKL objectives are uniqueness guaranteeing for inte- rior p.
While the MiniMaxKL equilibrium is likely the most useful concept. it is conceivable that other unqquenes-guuaaateecnn guaranteeing concepts may be useful. Thus, provide a generalization below.
equilibrium
Theorem 3. Consider an objective induced by
R: (h, 0) + [R(h, a) -6,,h.) ==0 [R(h, + b(), ==
and define a policy greedification fontcaattiiofuiiiio function
g: [-2n, MM) |AI x H,, (AA)
where Mi the maximum of the absolute values of the expected returns of and where
q, h, + arg max (6, (, q) (6,,
For each AOH which a player acts his 9 maps possible regularized action values to the policy that is greedy with respect to the regularized objective under those regularized action values.
If. for all ho vb(,, h.) is continuous and g(: ht) is i) well defined, ii) continuous, and iii) has an interior image, then the objective 3 is uniqueness guaranteeing.
Proof. (Sketch) Consider the following facts:
Because of our assumptions & and g, equilibrium must exist.
Because has an interior image, the best response to an equilibrium must be unique.
Because the game is two player sum, there cannot exist incompatible equilibria.
These facts can only be simultaneously satisfied if there is a unique equilibrium.
We detail the proof for Theorem 3 Section B.3
Remark The premises of Theorem 3 are satisfied (f h.)) is bounded and is strictly convex and differentiable on its interior with 1i || s8, h,)l== too for 8' on the boundary of (AA). Remark 3. One example of objective covered by Theorem but not by Theorem is that which is induced by setting (-(, h.)) to a sum of reverse KL divergence to an interior point and a bounded differentiable convex function.
7 DISCUSSION
In the previous section, we showed that computing certain regularized equilibria in 2p0s games can be reduced perfect information problems. This may give the impression that it is now possible to apply perfect information algorithms out-of-the of-the-box to solve imperfect information problems. While this is technically true, is not a good way view the value of our reduction. Indeed, because the PuB-AMG has action space of dimensionality an approach would quickly become intractable as the size of the game increases
the order of A [B. (Ppo)), naively pursuing such
Instead, two main ways to approach solving regularized PuB-AMGs. The first is adapt heuristic search value iteration (Smith & Simmons) 2004) into tabular regularized PuB-AMG solver. Encouragingly, this has already been done for PuB-MDPs (Dibangoye al. 2013b) and for unregularized Pub-AMGs (Horák & BBoaanský) 2019 Buffet et al. [2200] Delage et al., 2021). The second to use the regularized PuB-AMG as a building block for expert iteration with function approximation (Anthony et al. 2017). This approach would look almost identical to ReBel. (Brown al., (2020) but have a few key differences: i) would use a regularized objective, rather than an unregularized one as ReBeL does; ii) It would use the beliefs induced by its own policy at test time, rather than the fictitious beliefs that ReBeL uses; iii) would (optionally) be able to perform re- planning (e.g., wherein multi-ply ply search is only used to make the immediate decision), whereas ReBeL must play its search policy until the end of the subgame that was searched over.
Athhough attempt has been made scale up such approaches for the PuB-MDP Focester
2019

---

Under review as a conference paper at ICLR 2023
8 EXPERIMENTS
We perform two experiments in which naively tabularly solve small PuB-AMGs using magnetic mirror descent (Sokota et al. 2022a) to offer further evidence for our results. We show the results for perturbed tock-paper-scisseee Figure 4 and include results for Kuhn poker, well as the details
of our solving procedures, in Section
PuB-AMG Exploitabliity
PuB-AMG Regularized Exploitability
Exploitability
Regularized Exploitability
10
0
10-1
0 1/t
10-3
0
0.1
10
10e
102
102
10
10
103
In
10a
102
109
100
101
102
10
Iterations
Figure 4: Results for perturbed rock- seck-pper-scissors.
On the far left, we show exploitability in the PuB-AMG. The iterates from the unregularized ob- jective (blue) trend and the objective with annealed regularization (orange) trend toward zero. The iterates from the objective with constant regularization converge to a constant positive exploitability.
On the middle left, we show the regularized exploitability (i.e., exploitability under the regularized objective) in the PuB-AMG of the objective associated for the iterate. We observe that all objectives induce iterates that converge to zero.
On the middle right, we show the exploitability in the original game. Because the non- correspondence exists for the second moving player, the exploitabilities of the iterates from the unregularized objective (blue) remain high, despite that exploitability is going to zero in the PuB- AMG. The objectives with fixed regularization (green, red) induce iterates that converge to lower, but non-zero, exploitability values. The objective with annealed regularization (orange) induces iterates that converge to zero exploitability.
On the far right, we show the regularized exploitability in the original game. We observe that, in ac- cordance Theorem [[ the approaches with non-zero regularization that converge to zero regularized exploitability in the PuB-AMG also converge to zero regularized exploitability in the original game. In contrast, the unregularized approach does not converge, despite converging in the PuB-AMG.
RELATED WORK
Public Belief States in Common-Payoff Games In the sense of providing reductions for multi- agent problems using PBSs, work is similar to those of Nayyar al. (2013), Dibangoye et al. (2035)) and Olichoek (2013). As discussed in the background, Nayyar et al. (2013) provided a reduction from solving common-payoff games solving belief MDPs; independently. Dibangoye ct al. (2013b) and Olichock (2013) discovered similar reductions. These ideas have been leveraged large body of work in decentralized control literature (Lessard & Nayyar 2013) Nayyar al.
2014
Arabneydi & Mahajan 2014 Ouyang et al., 2015 Vasconcelos & Martins/ 2016, Tavafoghi
al.
Afshaa & Mahajan [0188] Gagrani G Nayyar 2018: Tavafoghh et al. [018]]Zang Zhang al.
Mahajan|20188
2019
Gupta. 2021) ) and machine learning literature (Dibangoye et 201| MecDermed & Isbell
2013
Dibangoye al. [2044a]] ( Dibangoye & Buffel 2018 Foerster et al. [219 et al.] 2020
Sokota et al. 2021 Fickinger al. 2021 Sokota et al. [002bb Kao et al. 2022). Use cases include
game solving (Dibangoye et al. 2013b). expert iteration (Sokota et al. 2021) and decision-
planning (Lerer al. 2020 Fickinger et al. 2021 Sokota al. 2022b).
Public Belief States Two-Player Zero-Sum Games PBSs have also been used in many works in the context of 2p0s games. For our purposes, taxonomize these into those concerned with solving the PuB-AMG (Wiggers et al. 2016, Horák Bošansky 2019; [uffett et al.) 20200: Delage
al. 2021 and those concerned with sound decision-time planning and expert iteration (Burch
8

---

Under review as a conference paper at ICLR 2023
et al.
2014
Moravcik et al. 2016 Brown & Sandholm, 2017a b. Moravčík et al. 2017
Brown
et al.
2018 Serrino et al. 2019; Brown et al. 2020, Schmid et al. 2021).
The former group is concerned with analyzing the structure of the PuB-AMG and using HSVI (Smith & Simmons 2004) to solve the PuB-AMG. Our work is complementary in the sense that it shows that using an approach such HSVI to solve regularized PuB-AMG would yield regularized equilibrium in the original game.
The latter group can be broken down into two subgroups, those that use opt-out values to circumvent the non-correspondence problem (Brown & Sandholm 201 b. Moravčík et al.] 2017 Schmid et al. 202T) and those that use no-regret learning circumvent the non-correspondence problem (Brown et al. 2020). Both possess substantial downsides. For the opt-out value approach: i) the policy and value are discontinuous functions of the opt-out value and ii) the opt-values must be approximated separately from self play. For the no-regret learning approach: i) the search policy must be played for the entire subgame that was searched over (i.e., re-planning not allowed), ii) the search algorithm must be no regret, and iii) the policy is discontinuous function of the PBS. In contrast, decision-time planning using a regularized objective in the PuB-AMG involves no opt-out values, involves no value discontinuities (as is shown in Section D) allows for re-planning, and is search algorithm agnostic.
MiniMaxKL Objectives in Two- Two-Player Zero-Sum Games As discussed, prior to this work, Perolat ct al. (202T) made use of MiniMaxEnt and MiniMaxKL objectives; they have also been used in more recent works (Cen et al. 2021; Zeng al. 2022 [ookota et al. 2022a Perolat et al. 2022). Our use case for MiniMaxKL objectives (eliminating the non non-correspondence problem) differs substantially from that of these works (inducing the last iterate convergence of model-free algorithms).
Public Belief States in Two-Team Zero-Sum Games In the sense of providing reductions for multi-agent problems using PBSs, our work is similar to a recent body of literature (Carminati al. 2022a Zhang et al. 2022 Carminati et al. 2022b) showing that solving 2t0s games can be reduced to solving a 2p0s game by using intra-team policy announcements. As articulated by Corollary I combining our results with these yields a reduction from computing regularized team correlated equilíbria in 2t0s games to computing regularized equilibria PuB-AMGs.
Stackelberg Games Public belief games with two-time steps are closely related to Stackelberg games (von Stackelberg, 1934, Schelling] 1960; Gibbons 1992). A Stackelberg game is one in which distinguished leader publicly commits to strategy and a follower best responds to it, resulting in a bilevel optimization problem. As with a public belief game, when a Stackelberg game is two player zero sum, Stackelberg equilibrium coincides with Nash equilibrium for the leader, but the follower's 's best response is generally highly exploitable in the game without public commitments. While there exist tie- breaking procedures in Stackelberg literature (e.g., strong weak Stackelberg equilibrium), they do not resolve the non-correspondence issue.
10 CONCLUSION AND FUTURE WORK
In this work, we provided a reduction from computing regularized equilibria of 2p0s games to com- puting regularized equilibria of PuB-AMGs. We see this contribution as resolving an important gap in literature between common-payoff games and 2p0s games.
We see three impactful directions for future work. The first involves comparing a high performance implementation of a poallaized-oohjeciiv----teee Paathe-PuB-AMMe approach to expert iteration (Anthony) et al. 2017) to those of existing approaches (Brown et al. 2020 Schmid et al. 202 }); while we have shown here that a a oojtaaiiiiedddeeeeeeeeeeeeeeeeee in-the-PuB-AAA AMG approach possesses favorable properties in comparison to ReBeL (Brown et al. 2020) and Player of Games (Schmid et al. 2021). verifying that these advantages manifest in practice would be a valuable contribution. Second, by providing simpler approach working with PBSs in 2p0s games, our work provides further motivation for developing new approaches for approximating PBSs at scale; while Sokota et al. (2022b) recently made progress in this direction by showing that fine-tuning can effectively approximate PBSs, amor- tized approximation of PBSs remains an open problem. Finally, third, we believe it may be possible to extend some weaker form of the results from our work to general sum settings.
"Though Schmid et al. (2021) show that certain approximate value functions can be made continuous.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Mohammad Afshari and Aditya Mahajan. Team optimal decentralized state estimation. 2018 IEEE Conference Decision and Control (CDC), pp. 5044-5050, 2018. doi: 10.1109/DDC. 2018.8619493.
Thomas Anthony, Zheng Tian, and David Barber. Thinking fast and slow with deep learning and tree search. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, pp. 5366-5376, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN
9781510860964.
Jalal Arabneydi and Aditya Mahajan. Team optimal control of coupled subsystems with mean- field sharing. In 53rd IEEE Conference on Decision and Control, pp. 1669-1674, 2014. doi: 10.1 N0.1109/CDC:220147333656
Dimitri P. Bertsekas, Dynamic Programming and Optimal Control. Athena Scientific, 2nd edition, 2000. ISBN 1886529094.
Noam Brown and Tuomas Sandholm. Libratus: The superhuman ai for no-limit poker. In Carles Sierra (ed.), IJCAL, pp. 5226 5228. ojeai.org. 2017a. ISBN 978-0-9992411-0- 1-0-3. URL http: //dblp. uni -trierrrer.... http:///coooff/////////
2017 7 htm #Brown517
Noam Brown and Tuomas Sandholm. Safe and nested subgame solving for imperfect-informatiee games. In Proceedings the 31st International Conference Neural Information Processing Systems, NIPS' 17, pp. 689-699, Red Hook, NY, USA, 2017b. Curran Associates Inc. ISBN 9781510860964.
Noam Brown, Tuomas Sandholm, and Brandon Amos. information games. In NeurlPS, 2018.
Depth-limited solving for imperfect-
Noam Brown, Anton Bakhtin, Adam Lerer, and Qucheng Gong. Combining deep reinforcement learning and search for imperfect-ifformatior games. Advances in Neural Information Processing Systems, 33, 2020.
Olivier Buffet, Jilles Dibangoye, Aurélien Delage, Abdallah Saffidine, and Vincent Thomas. On Bellman's ' Optimality Principle for POSGs. working paper or preprint, December 2020. URL
https: //halhhhaa..... iiriiiiiii..... fr http:halllla hhtp:hhhal110001111
Neil Burch, Michael Johanson, and Michael Bowling. Solving imperfect information games using decomposition. In Proceedings of the Twenty-Fighth AAAI Conference on Artificial Intelligence, AAAI'14, pp. 602-608. AAAI Press, 2014.
Luca Carminati, Federico Cacciamani, Marco Ciccone, and Nicola Gatti. Public information rep- resentation for adversarial team games, 2022a. URL
10377
Luca Carminati, Federico Cacciamani, Marco Ciccone, and Nicola Gatti. A marriage between ad- versarial team games and 2-player games: Enabling abstractions, no-regret learning, and subgame solving. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 2638-2657. PMLR, 17-23 Jul 2022b. httphhtts:://poooeeeee
ml www.m..........mmmmmmmmmmmm v /atcaa/aaammmmm rmi nat 22a. .tml
Shicong Cen, Yuting Wei, and Yuejie Chi. Fast policy extragradient methods for competitive games with entropy regularization. In NeurIPS, 2021.
Aurélien Delage, Olivier Buffet, and Jilles Dibangoye. HSVI fo zs-POSGs using Concavity, Con- vexity and Lipschitz Properties. 37 pages, 4 figures, 4 tables, 3 algorithms, October 2021. URL
https: //al: inria. Er hha--aal-00 /r/aaa-035233399 03523399
Jilles Dibangoye and Olivier Buffet. Learning to act in decentralized partially observable MDPs. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Confer- Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1233-1242. PMLR, 10-15 Jul 2018. URL https: pttps://pproceedingg mir. ptt..ppess//B// di dibangoye 8a. html
10

---

Under review as a conference paper at ICLR 2023
Jilles S. Dibangoye. Christopher Amato, Olivier Buffet, and Francçois Charpillet. Exploiting sepa- rability in multiagent planning with contimuous-stad state mdps. In Proceedings of the 2014 Interna- tional Conference Autonomous Agents and Multi-Agent Systems, AAMAS '4, pp. 1281-1288, Richland, SC, 2014a. International Foundation for Autonomous Agents and Multiagent Systems. ISBN 9781450327381.
Jilles Dibangoye, Olivier Buffet, and François Charpillet. Error-bounded approximations for infinite-horizon discounted decentralized pomdps. In Machine Learning and Knowledge Dis- covery in Databases, pp. 338-353 Berlin, Heidelberg, 2014b. Springer- Verlag. ISBN 978-3- 662 662-44847-2. doi: 10.
22. URL https: //cc: wwt.:ei...rrrg//
Jilles Steeve Dibangoye, Chris Amato, Arnaud Doniec, and François Charpillet. Producing efficient urror-bounded solutions for transition independent decentralized mdps. AAMAS, 2013a.
Jilles Steeve Dibangoye, Christopher Amato, Olivier Buffet, and François Charpillet. Optimally solving dec-pomdps as continuous-state mdps. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, ICAI '13, pp. 90-96. AAAI Press, 2013b. ISBN 9781577356332.
Arnaud Fickinger, Hengyuan Hu, Brandon Amos, Stuart Russell, and Noam Brown. Scalable online planning via reinforcement learning fine-tuning. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL
httpp:://pperreview. net www.foorrmiiiooom meet/forrumlddDDxGG0333333
Jakob Foerster, Francis Song, Edward Hughes, Neil Burch, lain Dunning, Shimon Whiteson, Matthew Botvinick, and Michael Bowling. Bayesian action decoder for deep multi-agent inforcement learning. Kamalika Chaudhuri and Ruslan Salakhutdinov (, Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 1942- 1951, PMLR, 09-15 Jun 2019. http::/: / http://pooccee........ mlr. wttppppssss//f//eespeee
9a..19991... htmll
Mukul Gagrani and Ashutosh Nayyar. Thompson sampling for some decentralized control problems. In 2018 IEEE Conference Decision and Control (CDC), pp. 1053-1058, 2018. doi: 10. 109/ CDC.2018 22201.11199222 8619423.
Sam Ganzfried and Tuomas Sandholm. Endgame solving in large imperfect-infformaioon games, In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Sys- tems, AAMAS '15 pp. 37-45, Richland, SC, 2015. International Foundation for Autonomous Agents and Multiagent Systems. ISBN 978 9781450334136.
R. Gibbons. A Primer in Game Theory. Pearson Education, 1992.
Abhishek Gupta. Existence of team-optimal strategies in teams with countable observation spaces. IEEE Transactions on Automatic Control, 66 66(10):4792-4798, 2021. doi: 10.1109/TAC.200. 3037047.
Karel Horák and Branislav Bošanský. Solving partially observable stochastic games with pub- lic observations. In Proceedings of the Thirty-Thire AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI
Symposium on Educational Advances in Artificial Intelligence,
(TT11///AA11//AAAA/T URL
AAAI Press, 2019. ISBN 978-1-57735-809-11
doi: 10.
https://doo ww..rr///o 100 1609/6aaa v33.01 033100013300229
Hsu Kao, Subramanian, and Vijay. Common information based approximate state representations in multi-agent reinforcement learning. 25th International Conference on Artifi- cial Intelligence and Statisties (AISTATS) 2022, Valencia, Spain. PMLR, 151, 2022.
//par .nf.
gov htw./biblo/// 0at.o//11339912
Vojtech Kovarík, Martin Schmid, Neil Burch, Michael Bowling, and Viliam Lisy. Rethinking formal models of partially observable multiagent decision making. CoRR, abs/ 11110, 10, 2019. URL http://arxil wwwp:/wwwwggg////o//ooo/ooos
11110

---

Under review as a conference paper at ICLR 2023
Adam Lerer, Hengyuan Hu, Jakob N. Foerster, and Noam Brown. Improving policies via search in cooperative partially observable games. In AAAI, 2020.
Laurent Lessard and Ashutosh Nayyar. Structural results and explicit solution for two-player lgg systems on finite time horizon. 52nd IEEE Conference on Decision and Control, pp. 6542- 6549, 2013. doi: DC.100/CDDC.2213666666999
Michael Lederman Littman. Algorithms for sequential decision making, 1996.
Liam MecDer and Charles L.. Isbell. Point based value iteration with optimal belief compres- sion for dec-pomdps. In Proceedings of the 26th International Conference on Neural Information Processing Systems Volume 1, NIPS' 13, pp. 100-108, Red Hook, NY, USA, 2013. Curran As- sociates Inc.
Matej Moravcik, Martin Schmid, Karel Ha, Milan Hladik, and Stephen Gaukrodger. Refining sub- games in large imperfect information games. Proceedings of the AAAI Conference Artificial Intelligence, 30(1), Feb. 2016. doi: 10. 10.9/aaaa.. v30il 10033. URL [RL[ntts:://o// aaai.
org/index. AAAT/ /AAAT/rra arrt ic wew.eeeveewwlee
Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artifi- cial intelligence heads-up no-limit poker. Science, 356(6337):508-- 513, 2017. doi: 10.1 acience.aam6960) URL https: /wwww aaam6600]
Ashutosh Nayyar, Aditya Mahajan, and Demosthenis Teneketzis. Decentralized stochastic control with partial history sharing: A common information approach. IEEE Transactions on Automatic Control, 58(7):1644-166) 2013. doi: (0.1109/TAC.201332222000
Ashutosh Nayyar, Abhishek Gupta, Cédrie Langbort, and Tamer Başar. Common information based markov perfect equilibria for stochastic games with asymmetric information: Finite games. IEEE Transactions on Automatic Control, 59(3):555-570, 2014. doi: T..109/TTAC.20132228744
Frans A. Olichock. Sufficient plan-time statistics for decentralized pomdps. In IJCAI, 2013.
Yi Ouyang, Hamidreza Tavafoghi, and Demosthenis Teneketzis. Dynamic oligopoly games with private markovian dynamics. In 2015 54th IEEE Conference on Decision and Control (CDC), pp- 5851-5858, 2015. doi: 10.1
Julien Perolat, Remi Munos, Jean- Baptiste Lespiau, Shayegan Omidshafiei, Mark Rowland, Pe- dro Ortega, Neil Burch, Thomas Anthony, David Balduzzi, Bart De Vylder, Georgios Pil- iouras, Marc Lanetot, and Karl Tuyls. From poincaré recurrence to convergence in imperfect information games: Finding equilibrium via regularization. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 8525-8535. PMLR, 18-24 Jul 2021. URL https::/
mlr
Julien Perolat, Bart de Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome T. Connor, Neil Burch, Thomas Anthony, Stephen McAleer, Romuald Elie, Sarah H. Cen, Zhe Wang, Audrunas Gruslys, Aleksandra Malysheva, Mina Khan, Sher- jil Ozair, Finbarr Timbers, Toby Pohlen, Tom Eccles, Mark Rowland, Marc Lanctot, Jean- Baptiste Lespiau, Bilal Piot, Shayegan Omidshafiei, Edward Lockhart, Laurent Sifre, Nathalie Beauguerlange, Remi Munos, David Silver, Satinder Singh, Demis Hassabis, and Karl Tuyls. Mastering the game of stratego with model-free multiagent reinforcement learning, 2022. URL als 220 15378
T.C. Schelling. The Strategy of Conflict. Harvard University Press, 1960.
Martin Schmid, Matej Moravcik, Neil Burch, Rudolf Kadlec, Joshua Davidson. Kevin Waugh, Nolan Bard, Finbarr Timbers. Mare Lanctot. Zach Holland, Elnaz Davoodi, Alden Christian- son, and Michael Bowling. Player of games. CoRR, abs/2112.03178, 2021. URL hetps:
12

---

Under review as a conference paper at ICLR 2023
Jack Serrino, Max Kleiman- -einne,, David C. Parkes, and Joshua B. Tenenbaum. Finding friend and foe in multi-agent games. In NewrIPS, 2019.
Trey Smith and Reid Simmons. Heuristic search value iteration for pomdps. In Proceedings of the 20th Conference Uncertainty in Artificial Intelligence, UAI '04, pp. 520-527, Arlington, Virginia, USA, 2004, AUAI Press. ISBN 0974903906.
Samuel Sokota. Solving common-payoff games with approximate policy iteration. Master's thesis, University of Alberta, 2020.
Samuel Sokota, Edward Lockhart, Finbarr Timbers, Elnaz Davoodi, Ryan D D'Orazio, Neil Burch, Martin Schmid, Michael Bowling, and Mare Lanctot. Solving common-payon payoff games with ap- proximate policy iteration. 2021.
Samuel Sokota, Ryan D D'Orazio, J. Zico Kolter, Nicolas Loizou, Mare Lanctot, Ioannis Mitliagkas, Noam Brown, and Christian Kroer. unified approach to reinforcement learning, quantal re- sponse equilibria, and two-player zero-sum games, 2022a. URLhttps://arxii .ww. abs/
2206. 05825
Samuel Sokota, Hengyuan Hu, David Wu, Zico Kolter, Jakob Nicolaus Foerster, and Noam Brown. A fine-tuning approach to belief state modeling. In International Conference Learning Representations, 2022b. URL
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Hamidreza Tavafoghi, Yi Ouyang, and Demosthenis Teneketzis. On stochastic dynamic games with delayed sharing information structure. In 20/6 IEEE 55th Conference on Decision and Control (CDC), pp. 7002-7009, 2016. doi: 10. D0.110//DDC2221..799993
Hamidreza Tavafoghi, Yi Ouyang, and Demosthenis Teneketzis. A sufficient information approach to decentralized decision making. In 2018 IEEE Conference on Decision and Control (CDC), pp. 0069-5076..0 IEEE Press, 2018. doi: 10. (L/////C...1..8119.00.. URL httph:ttp///oo
10.1109/CDC... 2018. 8619040)
Marcos M. Vasconcelos and Nuno C. Martins. The structure of optimal communication policies for remote estimation over the collision channel with private and common observations. In 2016 IEEE 55th Conference on Decision and Control (CDC), pp. 320-326, 2016. doi: 10.1109/CDC. 2016. 7798289.
H. von Stackelberg. Marktform und Gleichgewicht. Springer, Vienna, 1934.
Auke Wiggers, Frans A. Olichock, and Diederik M. Roijers. Structure in the value function of two-player zero-sum games of incomplete information. In ECAI, 2016.
Sihan Zeng, Thinh T. Doan, and Justin Romberg. Regularizee descent ascent for two-player zero-sum markov games, 2022. URL https:t:::////
13746
B. Zhang, Gabriele Farina, and Tuomas Sandholm. Team belief dag form: A concise representation for team-correlated came-theoretic decision making. ArXiv, abs/2202.00789, 2022.
K. Zhang, Erik Miehling, and Tamer Başar Online planning for decentralized stochastic control with partial history sharing. 2019 American Control Conference (ACC), pp. 3544-35500 2019.
13

---

Under review as a conference paper at ICLR 2023
A
DEFINITIONS
First, we formalize our definition of the correspondence mapping 11+ in Algorithm below.
Algorithm Correspondence Mapping
procedure (T) queue
[
+- 0
while Iquuqe) > do
8 queue.pop()
à - (5)
b Assume deterministic for reachable
for h E s5 do
T(h,)= =(h,) ā(h,)
end for for 3' E ( (8. a]) do queue.append(3)
D Continue along states reachable by ft
end for end while for untouched h, do Set (h, arbitrarily. end for return π end procedure
These information states are unreachable.
Next, define canonical choice function II, which maps each joint policy corresponding PuB-AMG policy,
Algorithm 2 Canonical Choice Mapping
1: procedure (T))
2:
0
3:
for all do
4:
ā 5
5: for supp(() do
6:
a(h,) = n (h.)
Do what π does.
7:
end for 7(5)= = end for
8:
9:
10: return
11:
end procedure
In short, Aggorithm2yyiedss PuB-AMG policy in which the agents play according to irrespective
of the public belief. Therefore, we have that R(x) = (x)))( Note that, in contrast to the correspondence mapping, the canonical choice mapping invariant opponent policy. Thus, also allow IIT to be applied directly to individual player policies.
We also introduce some additional definitions.
Definition A.1. For minimax objective J. the value of the game under is max min& H(T,, (() = min,; max MaT =().
Remark 4, mediately from the fact that both players can guarantee the unique equilibrium value.
objectives guarantee a well-defined value. This follows im-
Definition A.2. For minimax objective 3. the best response value to To under 3 is ming; I(Fo x(); analogously, the best response value gı under is max,; 3( T1). We denote the best response
TThis assumption is not required, but makes for cleaner presentation.
14

---

Under review as a conference paper at ICLR 2023
ne (R( A policy is part of Nash equilibrium the best response value to it is equal the value of the game.
Definition A.3. For a minimax objective 3, the exploitability n under 3 is:
minng I(To wi) + maxx, Mo Ri)
2
joint policy a Nash equilibrium if has exploitability zero. Definition A.4. For minimax objective 3 induced by
== 0 R: (h, a, 6) + [R(h, a) h.) [R(h, a) + h,)
L= 1,
the action value for action at AOH R; under joint policy is
Q),,, (-1)) R(H A', a - I[aa = al) + > R(H A , xAAAA)) aI, hr a
PSt
In words, the expected future value to the acting player for taking h assuming that both players have played according to π up until now and will continue to play according to π hereinafter.
B
THEORY
We now detail the proof' of our theoretical results.
B.
PROPOSITION I
Fair Game
Unfer Game
Tail
Heads
Opt Out
Tails
Heads
Opt
Talk
Heads
Talla
Heads
1,11
-1,1
-1.1
1,-1
Figure 5: A rigged and adversarial variant of matching pennies.
Proposition 1 A PuB-AMG Nash equilibrium may correspond with a joint policy II+ that is maximally exploitable.
Proof. We show that this worst case can be realized in the 2p0s rigged adversarial matching pennies game depicted in Figure 5 The game starts with two options for the red player: it can either decide to make the game fair or to rig the game. Then, without having observed the red player's decision, blue player decides whether to opt out of the game altogether, in which case both players receive payout of O, or to play adversarial matching pennies. If the blue player opts in and the game is rigged, the red player receives a payout of 1 independent of the blue player's 's selection. If the blue player opts in and the game is not rigged, the blue player receives payout of 1 if the players select the same side of the coin; otherwise, if the players selected opposite sides of the coin, the red player receives payout of 1.
In the game, the blue player's only Nash equilibrium strategy is to opt out with probability one. The red player's Nash equilibria strategies require least one of i) rigging the game with probability one and ii) mixing 50-50 between tails and heads.
Now, consider the following PuB-AMG policy, where superscript denotes time step within the game:
15

---

Under review as a conference paper at ICLR 2023
(0) (Fair, Unfair) + (1,0).
(Tails, Heads, Out) + (1/2, 1/2,0)
(F(ir)))
(#9)
(Tailss, Heads, Out) + (0, 00,0,1)
otherwise.
* =² xt) = (Tails, Heads) + (0, 1)
(Tails) 2 1/2
(Tails, Heads) > (1, otherwise.
We claim that 7 is PuB-AMG Nash equilibrium. To see this, first consider that the expected return the red player always opts in, the blue player mixes evenly between heads and tails, and the red player always selects tails. Next consider that the red player has incentive to deviate to unfair game, because the blue player will opt out, yielding an expected return zero. Also consider the blue player has incentive place additional mass on opting out, it yields expected return of zero. Furthermore, the blue player has no incentive to select different mixture of heads and tails, doing will decrease its expected return since the red player best responds the final time step. Lastly, consider that the red player is best responding at the final time step and, therefore, has no incentive to deviate.
Then, consider that the corresponding policy = [T) is as follows:
π (Fair, Unfair) + (1,
x! (Tills, Heads, Out) (1/2, 1/2,0).
x (Tails, Heads) + (0, 1).
We claim that this policy is maximally exploitable. To see this, consider that red player that always rigs the game achieves an expected return of one against the blue player's policy, and consider that a blue player that always selects heads achieves an expected return of one against the red player's policy.
B.2 THEOREM CORRESPONDENCE OF UNIQUENESS-GUARANEENN GUARANTEEING EQUILIBRIA
To prove Threom T
we first require some lemmas.
Lemma 1. The best response value to n, the original game is equal to the best response value of I1))) in PuB-AMG.
Proof. This follows because player -i has no mechanism exploit II' (mT)) beyond that of the original game, since IIT (T:) ignores belief information.
More formally, consider
min 3(T (mo), #1) 3(TT (Ro), (mo))
(TT))
3(II (II' (R (mo)))) II (II' (T)) (R))((
3mo. III (II* (mo). BR( (To))))1
2 (mm. BR (R)))
min 3(mo, 7
The first equality follows by definition of the best response function BR. The second equality be- cause I preserves expected return. The third equality is notational expansion. The fourth equality follows because To and II (II' (m)). BR((I (I(()( can only differ at AOHs that not reached when playing against II (II* (mp), BR(IIT (TT)))) (R)))( The inequality and final equality follow by def- inition of best response.
16

---

Under review as a conference paper at ICLR 2023
Also, consider
min J(To m() 3( (R(T)))
zi
3(II* (mo); II (BR()))))
2 5(TT") (mo) (R (To))
min (11 (TO), R1).
x
The first equality follows by definition of the best response function BR. The second equality follows because IT preserves expected return. The inequality and final equality follows by definition of best response.
These inequalities only be true if minz; 5(II' (TO); m1) min:; (TT. mi). An analogous argument shows the same result for πT
Corollary 2. The exploitability of in the original game is equal to the exploitability of (xt in PuB-AMG.
Proof. This follows immediately from Lemma I and the fact that exploitability defined in terms of best response values.
The value of the PuB-AMG under and equal to that of the original game.
Corollary 3.
objective is well-defined
Proof. Note that suffices to show that PuB-AMGs are guaranteed have an equilibrium with the same expected return as the equilibrium of the original game. Then consider मे = II' (T)) where π an equilibrium. Then, since ı an equilibrium and, per Corollary 2 IT' preserves exploitability, स is an equilibrium. Additionally, since IT preserves expected return, the original game and the PuB-AMG possess equilibria ग and म, respectively, that yield the same expected return.
We are now ready to prove our two main lemmas.
Lemma 2. Let be the equilibrium of a uniqueness-guane guaranteeing objective. Let 5 define subgame of the original game induced by playing for some number of steps. Then the unique equilibrium of the subgame n², considered as an independent game, the restriction ą/ă of a to the subgame.
Proof. If a _ is not an equilibrium of the subgame, then it must be exploitable in the subgame. This means that either
min 3 (m) -1) < (mb m or 3 (mm) m < max 3 ( ,1.²)
%
Without loss of generality, assume the former. Let _ = argmin ( ) let PM (3) represent the probability of reaching & using policy म; let t be the time step corresponding to é and let J denote the expected return prior to time t. Further, let 3' + range over the possible subgames entered at time / if 8 is not entered. Then
(mO, कι) J (To,
"F00 + -1)
Σ (3')3 (mo
18'
> (To, nI (T) +
pT (8') (=) )
[ [T |
Here, the first line decomposes the expected return into 1) that which is accrued prior to time t, 2) that which is accrued in subgame and 3) that which is accrued after time outside of subgame $. The second line invokes our assumption that 7 does not achieve the best response value against To and pa (3) > 0. The third line re-assembles the expected return, where |m\r म -5 denote policy that plays गi outside and n/ inside s.
17

---

Under review as a conference paper at ICLR 2023
In total, we have shown that if 7/ is not an equilibrium in the subgame induced by 8, then is not an equilibrium because is not a best response. Thus, 2 must be an equilibrium of the subgame. Therefore, because 3 is uniqueness guaranteeing, we must have x =
Lemma 3. If क is an equilibrium of the PuB-AMG, then the decision rule for the first time step (#) must be part of an equilibrium policy in the original game.
Proof. Without loss of generality, assume that 1 0 the first time step. Also, use To denote the part of no that is relevant after the first time step. Also, let [x= = denote policy for i that plays according n/ at the first time step and -/- otherwise. Let be equilibrium of the PuB-AMG. Then observe
max min 3( m|) 76
max min 3( m1)
m1
#1
max min 3( " #1)
(2)
%6
#1
max min 3(T " #11)
(3)
#6
#
max min J II (1#), " "1 #/ #1))
(4)
#6"
#1
max 3(II _ 1, x()
(5)
"o
mi
-min ((11 arg m min 3 ,= ", "["],,
(6)
xx
Here, the first equality follows by Corollary the second equality follows because H" is part of an equilibrium; the third equality follows because J(7') 3(1)((7)): the fourth line equality follows because the image of the correspondence mapping for the first time step is invariant to the PuB- AMG policy at later time steps; the fifth line follows because each player can express any policy in the original game through III, up to reachability, and because changes over unreachable AOHs do not change the expected return; the sixth line follows because the evaluation of argmax is equal to the max.
This chain of equalities shows that the best response value
III (7)), arg max max_;-o min
I(III T6 -..% x[]
"
is equal to the value of the game. Thus, IT (+)) is part of an equilibrium.
Theorem I i is an equilibrium of the PuB-AMG induced by a then its projection (++) is an equilibrium in the original game.
objective,
Proof. Lemma shows this to be true for the first time step. Now assume this is true up to time step and consider time step + 1. Then, for particular reachable g++1, the PuB-AMG subgame starting at this point is the PuB-AMG of the subgame of the original game starting from g*+1, Thus, the PuB-AMG strategy for g++1 must correspond to an equilibrium of the subgame of the original game, per Lemma 3 Furthermore, because the minimax objective is uniqueness guarantecing, the equilibrium strategy of the subgame of the original game must the unique restriction of the equilibrium of the original game that subgame, per Lemma
B.3 THEOREM 3 SUFFICIENT CONDITIONS FOR UNIQUENESS GUARANTEEING
Theorem Consider an objective induced by
[Rh,, a) (66,1.) 1= 0 R(h, a) + (6,,h.)) t=
R: h, a, 5
and define policy greedification function 9: q, h, + arg max (5. (5, h.)) where g: 1- mt) [A] x H. A(A)
18

---

Under review as a conference paper at ICLR 2023
and where 2t is the maximum of the absolute values of the returns of the objective. Then, if. for all he +b(,,,, ) is continuous and g(:, h2) is i) well defined, ii) continuous, and iii) has an interior image, the objective is uniqueness guaranteeing.
Proof. First, we show that such an equilibrium is guaranteed to exist. Let F: [-91, 2t) [H.Il-A| [-2R, 2t] [H.]|A] be a function that maps each vector [gh,] Jt, to the action-value vector for the joint policy dictated by the application of to [[th, h.)],,- Note that F is well defined-i.e., the ensuant action values are always well defined-because g maps to the interior, so every history is reached with positive probability. Also note that this function is continuous, by the continuity of g and v., and single valued because g single valued. Thus, because [-DR, Dt IIA) is compact and convex, by Brouwer's 's fixed point theorem, a fixed point must exist. The policy corresponding these fixed- point action values is equilibrium. This follows because, by backward induction, each player is optimally responding to the other, holding the other fixed.
Now we show that there is unique equilibrium. Note that, for any fixed opponent, the optimal policy at any decision point reached with positive probability must be full support because g image is within the interior. By forward induction, this means that every equilibrium must be full support at every decision point. Now, note that, by backward induction, the best responses to full support policies are unique because g is single valued with interior image. In aggregate, these things show that any equilibrium is strict-i.e., the only best response to one part of the equilibrium the other part of the equilibrium. Now, assume there exist two distinct equilibria and x'. Without loss of generality, assume that performs at least as well as To against TT If To performs equally well, there is contradiction because To is not the unique best response. If mo outperforms x', there is contradiction because T' is not at equilibrium. Thus, the equilibrium must be unique.
The result follows because this proof also holds for every subgame of the original game.
C EXPERIMENTS
C.I MAGNETIC MIRROR DESCENT
In experiments, magnetic mirror descent (MMD) (Sokota et al. 2022a) our game solver. In the instance of MMD we use, updates are of the form
Te++1 argmax Eannn (A) aHH(T) 1 "
KL( me)
where Te is the current policy and % is the MiniMaxEnt Q-value vector for time t. This update possesses the closed form
Tet1 x [rre |मम..
(8)
The fixed point of equation
8 is policy satisfying
n2 arg max E. (Ax_(A))(AA)) a'H((T) clo
(9)
C.2 TABULAR PUB-AMG POLICIES
In PuB-AMGs, the state space is continuous. Thus, it may not be possible to express fully specified PuB-AM AMB policy tabular form. We describe how we handle this issue for perturbed rock- paper- scissors and Kuhn poker, respectively, in subsequent subsections.
In both settings, we solve the games using full feedback, meaning that we compute exact Q-values and update the policy for every AOH.
C.2.1 PERTURBED
SAPER-SSISSOOSS
In perturbed rock -aper-sssssosrss the first moving player's state space is trivial; thus, its policy can be expressed exactly. Also, the (regularized) best response of the second player can be computed in closed form using equation. Thus, set the second moving player's (regularized) PuB-AMG
19

---

Under review as a conference paper at ICLR 2023
Regularized Exploitability
Exploitability
Q = 0
10-1
α 1/ V
Q = 0.05
10
Q = 0.1
Q 0.2
10-3
100
10
102
103
100 10 102
103
Iterations
Figure 6: Results for Kuhn poker.
Nash equilibrium policy induced by equation 9
We update the first moving player's policy using equation (8) where is the feedback induced by the second moving player's (regularized) PuB-AMG Nash equilibium policy.
C.2.2
KUHN POKER
We also investigate MiniMaxEnt objectives in an extensive-form game- Kuhn poker. Kuhn poker, there are up to three time steps. For the third time step, we use the (regularized) Pub-AMG Nash equilibrium policy induced by equation (9) For the first time step, at each iteration, we update the policy each information state using MMD the feedback from the previous time step. For the second time step, at iteration f, holding fixed the iteration decision rule for the first time step, we use the policy induced by performing // iterations of MMD against the (regularized) PuB-AMG Nash equilibrium policy of the third time step. vi grows large, we expect the decision rules for the second time step to approximate PuB-AMG best response.
We show the results for the original game Figure 6 Qualitatively, they are analogous to those from the perturbed pock-paper-scissors game. The unregularized objective induces high exploitabil- ity iterates (blue) that do not converge the original game; the objectives with fixed regularization (purple, red, greed) converge constant exploitability and zero regularized exploitability in the original game; the objective with annealed regularization converges to zero exploitability and zero regularized exploitability.
D CONTINUITY IN THE PUB-AMG
Lemma 4. Let fI, fa be real-valued continuous functions with shared compact domain X x y. Furthermore, assume their max-min values are attained and the following inequality holds for any (I,y) E X x y:
Ifi v) fe(x, <c.
Then it follows that
[max min (z, v)]
[max min fa(x,))) <.. zex vey
xEX yey
"We omit PuB-AMG (regularized) exploitability, it difficult compute exactly in this case.
20

---

Under review as a conference paper at ICLR 2023
Proof. Note that by assumption we have for all (z. y) within the domains of fi. f2 holds
( S f2 y) te, fz(2.y) S fi y) +e.
(10)
(11)
Therefore,
max min (I = min fi (I., y) for E max min fi (z, v) #eX yEY
vey
se yey
S min (2 y) t
yey
max min fa(z, y) + =E vEy
Where the first inequality is due to taking the min of both sides of equation 10 Following the same steps starting with f2 and using equation 11 gives
min f2(2, v) s max min fi (zr y) +c.
EE DEY
sE yEy
These two inequalities together yield the result.
Theorem 4. The minimax PuB-AMG value function i. is continuous for any objective 3 for which policy evaluation is continuous.
Proof. Fix >> O. Let b and 1' differ in total variation distance by less than
220t
Then observe that, for a joint policy æ, we have that
|u (b) ux (b') Σ b(hjuz (h) b'hh)) (h)
Σ (b(h)v, (h) - 6 (hh),, (h)
h
20
Σ
(b(h) (h))
h
22M5
where Ux (b) is the expected return under playing starting from the subgame defined by b.
Then
0. (b) (b() [max min ÜN (b)
[max min 0z (b')
5o
Ri
Rg
R1
[max min U. (b) [max min Ux (b')]
The first equality follows by definition of i.. The second equality follows from Corollary 3 The third equality follows from Lemma
Corollary 4. The minimax PuB-AMG value function 8_ is continuous for the standard expected return objective.
Corollary 5. The minimax PuB-AMG value function U, is continuous for any objective satisfying premises of Theorem 3
21


Reviews:
[{"review_id": "gY5xg2PwF0T", "reviewer": "Reviewer_igpY", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The main contributions of the paper are twofold:\n\n* on one hand, the paper provides an overview of the main sources of complexity when computing a Nash Equilibrium in two-player zero-sum game with imperfect information. Those are named *backward dependence problem* and *non-correspondence problem*.\n* on the other hand, the paper propose a novel resolution scheme that addresses these two problems by combining the Pub-MDP construction developed by Nayyar et al. (2013) with the minmaxKL framework developed by Perolat et al (2021). These two techniques respectively address the backward dependence problem by transforming the game to remove the private information and the non-correspondence problem by guaranteeing a unique Regularized Nash Equilibrium in any subgame.\n\nThis is a theoretical paper that introduces and formally defines each concept and gradually constructs the final proposed solving procedure. Small experiments are provided to add empirical evidence of convergence of the proposed method.", "summary_of_the_review": "Overall, I find the result offered by the paper and the justifications provided really interesting for the game-solving community. On the other hand, the weaknesses highlighted previously are important issues that should be properly addressed to allows a smoother and comprehensive exposition.", "strength_and_weaknesses": "The strengths of the paper are a well-explained setting, in which the crucial problems are clearly highlighted, a strong formalism adopted, a well explained relation with previous works, and a novel result which connects in an actionable framework imperfect information and perfect information settings.\n\nOn the other hand, I found crucial steps of the paper to be difficult to quickly comprehend due to the heavy formalism adopted and a lack of insightful comments (more details on this in the next Clarity section). More importantly, I think that the lack of an algorithmic perspective on the results makes very unclear any evaluation of impact of the proposed framework. I would have liked to see a justified algorithm-like procedure to wrap-up the contribution of the paper, and a transparent evaluation of the time/complexity needed to solve game instances , maybe with a comparison to the CFR algorithm that is currently state-of-the-art.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "a1KyGjxu05", "reviewer": "Reviewer_D4EG", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In two-player zero-sum games, when we modify utility objective of minimax optimization with an appropriate regularization term, it is always possible to find a unique solution that has error at most $\\epsilon > 0$ in the original optimization problem. This is an important previous result from [1]. Let's call any such objective modification \"uniqueness-guaranteeing\" (UG).\n\nThis paper shows that solution of UG optimization tackles the \"non-correspondence problem\" between the subgame strategies and the trunk strategies (part of the game played above the subgame), simply from the virtue of UG solution being unique (so there is no danger of using two incompatible equilibria). \nIn contrast, in the existing literature, the correspondence has been solved for arbitrary equilibria using gadget games [2].\nThis work shows that one can use value-solving subgames [3] when using UG, without the need to use the gadget game.\n\nValue-solving subgames are rooted in public belief states, where players publicly announce what strategies they played so far.\nAuthors thus identify that optimizing minimax UG objective in imperfect-information game is equivalent to optimizing minimax UG objective in what authors call \"perfect-information\" PuB-AMGs.\n\n[1] From poincaré recurrence to convergence in imperfect information games: Finding equilibrium via regularization.\n\n[2] Solving imperfect information games using decomposition.\n\n[3] Rethinking formal models of partially observable multiagent decision making.\n\n[4] Sound algorithms in imperfect information games\n\n[5] Player of games.\n", "summary_of_the_review": "Overall I like the direction of the paper. It has two substantial contributions, solving non-correspondence problem using value-solving subgames, and generalization of UG.\nThe paper could be made stronger by including experimental comparisons with gadget games to show (if) convergence to equilibrium shows faster in practice.\nHowever, addressing all the criticism would require a major rewrite. I recommend authors to resubmit their revised work.", "strength_and_weaknesses": "Strengths:\n+ Provably correct solution of the non-correspondence problem without using gadget games. This is important, because empirically strategies in gadget games converge very slowly, often at rate close to their upper bound, and value-solving subgames are empirically fast. \n+ Authors generalize result from [1], i.e. what regularizations are UG.\n\nWeaknesses:\n- I find introduction of PuB-AMGs and calling them \"perfect-information\" games misleading at best, and disingenuous at worst. \n  A similar \"perfect-information\" game transformation would be to let a player pick a strategy for the whole game, announce it publicly, and let opponent do the same, and evaluate the expected utility of the game. Pub-AMGs trick is the strategies are additionally factored over public states.\n  One could get a superficial impression that with the transformation, you can take any off-the-shelf algorithm for perfect-information games, such as AlphaZero, to find an equilibrium in imperfect-information games, which is not true. In this sense the reduction is not particularly useful. I view it as \"rebranding\" of value-solving games as a new concept, i.e. the PuB-AMGs.\n  Futher, the diagram in Figure 1 suggests that PuB-AMGs are fully observable. This is false. The players do not receive full observations about what is going on the game -- they do not receive opponent's observations.\n- The non-correspondence problem has been studied before and is not cited, i.e. [4].\n- There is a missing text on limitations of the method:\n  - Computing KL-regularized equilibrium for arbitrary small $\\epsilon > 0$ is slow. Further, computing regularized equilibrium in sequential games needs recursive computation of regularized best responses, yielding asymptotic complexity of $O(T^D)$, where D is depth of the game and T is number of regret minimizer iterations. The algorithm has been applied to Kuhn Poker (with some tricks to make if faster, as explained in appendix), and is impractical for even slighly bigger game, like Leduc Poker.\n  - A lot of the practical speedups of CFR-based methods comes from pruning unreachable subtrees. When using regularized equilibria, all actions are in the support, and no subtrees can be pruned.\n- In introduction, authors write existing approaches are hampered by discontinous functions (i.e. values for AOH not being convex in terms of their associated beliefs). However, [5] proved that approximative value functions, unlike optimal value functions, can be made continuous. Additionally, authors do not prove whether their approach yields continous functions or not.\n\nOther comments:\n- Definition 6.1. \\rho in  is not defined.\n- Definition 5.1. R is a real-valued funtion of what? What is pi(H_i^t) ?\n- Experiments: Regularized exploitability is undefined.\n- Is annealed regularization the same algorithm as in [1], i.e. double-iteration algorithm where one approximates reg. equilibrium, and then iterates over the regularization step size (to speed-up convergence)?\n- \"We observe that all objectives with positive regularization converge to zero regularized exploitability, in accordance with our theory.\" -- Can you refer the theorem?\n- Figure 4,5: Why did you pick 1/sqrt(t) and 1/t, and not just one consistenly?\n- I would be interested in comparison of minimaxEnt/minimaxKL in experiments.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "YtY6tR9eJDR", "reviewer": "Reviewer_X9vx", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In games of imperfect information, players' payoffs are known, but actions may not be.  An example would be a two player simultaneous move game, whose game tree depicts one player as moving second, but unable to distinguish between the nodes reachable from each of the other player's actions.\n\nAs imperfect information complicates reasoning, some method for handling it must be developed when deriving equilibria.\n\nIn games in which players' incentives are aligned, it may be enough for one player to announce its strategy (Nayyer et al.).\n\nThe current manuscript argues that imperfect information can also be abstracted away from when one player has a unique strategy, allowing the other to determine which node has been reached.", "summary_of_the_review": "Overall, I felt that the paper was trying to pack too much specialist material in, without motivating it enough for a more general reader to understand.  This also meant, unfortunately, that the paper was only able to motivate its connection to machine learning in passing.\n\nIf the manuscript is not accepted here, I think it could be a fruitful exercise to rewrite it for submission to a dedicated game theory journal.  This would allow it more 'space to breathe', without the tight page limit, and require it to connect more tightly to the existing literature, strengthening its foundations.", "strength_and_weaknesses": "**Strengths**\n\n**Weaknesses**\n\nSee below.  On the latter, I am primarily concerned that the manuscirpt's density makes it difficult to read and understand.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject