Learning in two-player zero-sum partially observable Markov games with perfect recall
Authors: Tadashi Kozuno
Pierre MENARD
Remi Munos
Michal Valko
Venue: NeurIPS 2021 Poster (2021)
Keywords: online learning
reinforcement learning
Nash equilibrium
Markov games

Abstract: We study the problem of learning a Nash equilibrium (NE) in an extensive game with imperfect information (EGII) through self-play. Precisely, we focus on two-player, zero-sum, episodic, tabular EGII under the \textit{perfect-recall} assumption where the only feedback is realizations of the game (bandit feedback). In particular the \textit{dynamics of the EGII is not known}---we can only access it by sampling or interacting with a game simulator. For this learning setting, we provide the Implicit Exploration Online Mirror Descent (IXOMD) algorithm. It is a model-free algorithm with a high-probability bound on convergence rate to the NE of order $1/\sqrt{T}$ where~$T$ is the number of played games. Moreover IXOMD is computationally efficient as it needs to perform the updates only along the sampled trajectory.

Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recall
Tadashi Kozuno* University of Alberta
Pierre Ménard Otto Guericke Universität Magdeburg pierre.menardBoggu
tadashi. tadashi.kozuno www.kooooailia.ccoooooommooo
Rémi Munos Deep Paris
Michal Valko
DeepMind Paris
munos@deepmind. com
valkom@deeppindd.comm com
Abstract
We study the problem of learning Nash equilibrium (NE) in imperfect infor- mation game (IIG) through self-play. Precisely, we focus on two-player, zero-sum, episodic, tabular IIG under the perfect-recall assumption where the only feedback is realizations of the game (bandit feedback). In particular, the dynamics of the IIG is not known-we can only access by sampling or interacting with game simu- lator. For this learning setting, we provide the Implicit Exploration Online Mirror Descent (IXOMD) algorithm.
model-free algorithm with a eigh-probbbility bound on the convergence rate the NE of order 1/ 1/VT where T is the number of played games. Moreover, IXOMD is computationally efficient as it needs to perform the updates only along the sampled trajectory.
Introduction
We study the setting of learning a Nash equilibrium (NE, Nash Jr, 1950) in an imperfect information game (IIG, Osborne and Rubinstein, 1994). Precisely, focus two-player zero-sum IIG under the perfect-recall assumption (Kuhn, 1953). Perfect recall means that the players do not forget observations encountered actions taken during the game. We model the game tabular, episodic of horizon H. partially observable Markov game (POMG) with a state space of size S, action spaces of size A and B for the max- and min-player respectively, and observation spaces (i.e., information set spaces, which are partitions of the state space) of size X and for the max- and min-player. In learning by self play, we control both the and min-player. After T episodes of the game we asked to return a profile that close to a NE in terms of exploitability gap (Ponsen et al., 201 1).
Full feedback case when we have perfect knowledge of the game (i.e., the transition probabilities and rewards) there already exist several methods approximating the NE. The first line of work casts the setting through the sequence-fore representation as a linear program which can be solved efficiently for games with moderate sizes of observation spaces X and Y (Romanovsky, 1962; von Stengel, 1996; Koller et al., 1996). The sequence-from representation allows also to cast the setting as finding saddle point (Hoda al., 2010). It is then possible adapt first-order methods such Nesterov's 'ss smoothing (Nesterov, 2005) and MirrorProx (Nemirovski, 2004) to IIG, as done respectively by Hoda al. (2010); Kroer al. (2018) and Kroer et al. (2015, 2020). These methods have rate of
Equul contribution
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

convergence of order Ō((X + Y)/T), where Ô hides poly-log terms in e" B.T. Note that game-dependent exponential rate could also be obtained with first-order methods, see Gilpin et al. (2012) and Munos et al. (2020). Another important line of work relies on minimizing the counterfactual regret (Zinkevich et al., 2007). It uses an algorithm designed for adversarial bandits to locally minimize the regret of each player. A well-known example is CFR by Zinkevich et al. algorithm (Hart and Mas-Colell, 2000; Gordon, 2007). There exist many other variants of it, such as CFR+ (Tammelin, 2014; Burch et al., 2019), see also Farina et al. (2019, 202 These algorithms however only enjoy a (known) guarantee of convergence of order O((XVÁ + YvB)/vT), Note that the two last approaches require computing a full feedback: either some gradient for the first-order methods or the local regret for counterfactual regret minimization. Usually, this can be done by a complete traversal of the state space leading to a cime-comllexity of order (S). Sampling can reduce this time-complexity to O + Y), i.e.
(2007) based on the regret-matching
we sample the transitions and the actions of the other player; see for example the external-sampling
MCCFR algorithm (Lanctot et al., 2009; Farina et al., 2020).
Bandit feedback In this paper, we consider a more challenging setting where we only observe realizations of the games (bandit feedback) and do not have any prior knowledge of the game. Precisely, the rewards, the transition probabilities (sometimes modeled as the policy of chance player), the observation/state space, and its (tree) structure are unknown.
Bandit feedback, model-based To deal with the limited bandit feedback, Zhou et al. (2020) consider model-based approach by using posterior sampling (PS, Strens, 2000) learn model and then use the CFR algorithm in games sampled from the posterior. They obtain a convergence rate of order Ó(max(X X A + YB, vS)/vT) but only when the games are actually sampled according to the known prior. addition, they still need to know the state space and its structure" in order to instantiate the prior. Instead, Zhang and Sandholm (2021) rely on the principle of optimism in presence of uncertainty to incrementally build a model of the game. Then, they feed optimistic local regrets to a counterfactual regret minimizer algorithm such as the CFR algorithm. They prove high-probability bound on the exploitability gap of order O((XVA+YVB))V)
Bandit feedback, model-free Our results follows another line of work which consider a model- free approach. A well known algorithm of this type is outcome-sampling MCCFR (Lanctot al., 2009; Farina et al., 2020), which builds an importance-sampling estimate of the counterfactual regret given exploration profile (named balanced strategy by Farina al., 2020). This exploration strategy should ensure that the players explore the information sets uniformly (i.e., such that all induced reach probabilities are lower-bounded by an absolute constant). Note that it is not clear how to find such an exploration profile without knowing the structure of the game." In particular, following the uniform distribution over the actions at each information set is not necessarily good choice, e.g., when the tree formed by the information set space is not balanced. This algorithm has guarantee of order ((XVA Y YVB), /BB//VTT with high probability. Building on this idea, Farina and Sandholm (2021) propose to mix the exploration profile with one produced by a counterfactual regret minimizer such as CFR. They prove high-probability bound on the exploitability gap of order (poly(XX, Y, B) TT//)) Note that this bound is consequence of a bound on the regret of both players (see Section 2) that holds even in the non-stochastic setting where an adversary picks a new game at each episode. Closer to our approach, Farina et al. (2021b) recast the setting to an adversarial bandit linear optimization (Flaxman et al., 2005; Abernethy et al., 2008, see also Section 3.. Precisely, they use the online mirror descent (OMD) algorithm with the dilated entropy function (Hoda et al., 2010; Kroer et al., 2015) as regularizer. Then, OMD is fed with an estimate of the losses of the reformulated adversarial bandit linear instance. The estimator is a generalization of the typical one-point linear regression (Dani et al., 2008). They obtain rate of order Ō(XA- + YB) /T),, which is, similarly done by Farina and Sandholm (2021), derived from a regret bound valid in the adversarial setting. However, their bound holds only in expectation and not in high probability.
Therefore, we hide polynomial dependence on the horizon H. P Note that O(X + Y) is at most (SS).
'By structure refer to the tree structure of the state space or observations spaces, see Section 2.
2

---

Algorithm
Adv. game
Rate
Zhou et al. (2020)
Olmax(XvA+ VVV.V
model-based
Zhang and Sandholm (2021)
no
O((XAAYVVB)VV
Lanctot et al. (2009); Farina et al. (2020)
O((XVA+XVB)/VT)
Farina and Sandholm (2021)
O(poy(XX.A.Y.B)/7HH)
model-free
Farina et al. (2021b)
yes
O((XA+YB)/V))
IXOMD (this paper)
O((XVA+YVB)/
Table 1: Algorithms for computing NE of an IIG with bandit feedback and their respective upper
bound on the exploitability gap after T episodes. In the adversarial game column we precise whether the algorithm could be used to obtain a -rerrtt for one player when the other player and the game are chosen by an adversary at each episodes.
Only in expectation according known prior the game.
Only in expectation.
To obtain bigh-probability bound, we instead propose to use an importance sampling estimator of the losses with implicit exploration (Kocák al., 2014; Neu, 2015). Indeed, the implicit bias of this estimator allows to effortlessly control the variance of the estimate, see Lattimore and Szepesvári (2020, Chapter 12) for an in-depth discussion. Using this estimator, we give the Implicit Exploration Online Mirror Descent (IXOMD) based on OMD with the dilated entropy (using uniform weights) as regularizer and add implicit exploration the importance sampling estimator of the losses. Using our new analysis of this particular combination, we prove high-
function
probability bound the exploitability gap of the average profile of order Y cf. Table to see how our result compares to the prior work mentioned above. Precisely, our bound is obtained by bounding the regret of each player if they both follow the policy prescribed by
IXOMD. Note that the regret bound, c.g.. of the max-player, of order (AT). remains valid the opponent's policy and the game are picked by an adversary at each episode. IXOMD shares some similarities with the approach of Jin et al. (2020) designed for a different setting (see Remark 1). A regularizer
function instead of the no-nomaalized Kullback-Leiblee divergence (Rosenberg and Mansour, 2019). Our choice of regularizer allows an efficient update of the current policy with O A) time-complexity per episode (see Section 3.3). In particular, our result answers the open problem raised by Farina et al. (2021b) and Farina and Sandholm (2021) of providing an algorithm with high-probability regret bound scaling with /T with O(H A) computations per episode. Interestingly, average profile (which will be returned at the end of the learning. see Section 3.3) in an online fashion. As consequence, IXOMD enjoys overall time-complexity of (OTTH(A + B) + min B)) and space-complexity order (min(TT, X)A + min Y)B).
notable difference is that we use the dilated entropy
can also update the
Moreover, IXOMD requires almost no prior knowledge of the game. In particular, we do not need to know the list of information sets in advance. We only require an oracle providing the possible actions at encountered information sets and a bound on A, B, and H to optimally* tune the learning rate, see Remark
We highlight our main contributions:
We give the IXOMD algorithm that learns a NE of an IIG in self-play with limited feedback. It has provably high-probability convergence rate of order Õ((X / (YVBB//TT) The timeccompexxtty of LXOMD is of order (T + B) min(TH, X)A + Hin with space-complexity of order O X)4 +
B)
If only one player follows IXOMD, e.g., the max-player, then its regret is w.h.p. at most (AT). J. The important property of our result is that it remains valid even if the policy and the game are picked by an adversary each episode. Furthermore, the time-complexity
'Precisely, with this knowledge obtain a regret bound, e.g. for the max-player, of order Õ(X VAT): whereas get Ö AvT) it.
3

---

of IXOMD per episode is of order ().). This answers an open problem of Farina et al. (2021b); Farina and Sandholm (2021).
IXOMD only needs to know the possible actions the encountered information sets and bound on A. B, and H to tune the learning rate. particular, we do not need to know the list of information sets in advance.
2
Preliminaries
In this section, we introduce our notations and our setting partially observable Markov game (POMG) with bandit feedback and perfect recall. For positive integer i, we denote by [t] the set (1. ,). For a finite set A, we let A or (AA) denote the set of all probability distributions over A.
Partially observable Markov game (POMG) We consider an episodie, tabular, two-player, zero- sum POMG (8, X, A, B, H, {pr heim (reth))))) ). which consists of the following components (Littman, 1994; Shapley, 1953): a finite state space 8 of size S, its information set spaces (partitions of S) X' of size X and y of size Y for the max- and min min-player (resp.), finite action spaces A of size A and B of size B for the max- and min-player (resp.). horezoorionn H E N. initial state distribution state-transition probability kernel pa, : S x A x B - (SS) for each h E [H], and reward function Ta : S x Ax x B + [o, 1] for each h E [H]. For a state & we denote by x(s) E X and y(s) E y/ information sets such that E as)) and y E y(s).
Po (SS),
Learning procedure The players play this game for T episodes, following so-called policies. A policy μ of the max-player is a sequence (μa)ae(и) of mappings from X₁, to AA. (A₂ C X' is defined later.) A policy v of the min-player is defined similarly. We let Immax and Imin denote the sets of max- and min-player's 's policies, respectively. The t-th episode proceeds as follows: an initial state si sampled from Pa- At the step h, the max- and min-player (resp.) observe their information sets rx, := (xs,)) and yi. := =.())) Given the information, the max- and min-player (resp.) choose and execute actions a p (-12,) and bf, (- (n). As result, the current state transitions next state _/ Ph (115%, a bf,). and the max- and min- min-player receive rewards r/ r& (5%, d bf,) and -rh respectively. This is repeated until time step H, at which the episode finishes.
Tree-like game structure and perfect recall assumption We assume that the game has tree-like structure: for any state E S, there is unique step h and history ($), Q1. bi......5 = 9) to reach s. Precisely, for any policy of the players, for any realization of the game (i.e., trajectory) (5h, o/ (a)REIZ), conditionally to s = s, it almost surely holds that i = h and (s'....,,,)) = (s1,..., 88). We also assume perfect recall, which means that each player remembers its past observations and actions. For example, in case of the max-player, for each information set X there is a unique history (I), (1,,,.,..... TA = v) up to x. These assumptions require that X' can be partitioned to H subsets (Xi)eeim such that ay E Xr is reachable only at time step h; otherwise there would be two different histories up to zh. S and y can be also partitioned into H subsets (S)))E(H)) and (e)) respectively.
Given the assumptions above, there exists unique history (s1, 01, bi...., 84 = 8, as a, by = b) ending with (an. = 8, a = a, by = b) for any state 8 Sh, the max-player's action a E A, and the min-player's action b E B. Accordingly, the probability of 8h 8, ab = a, by b can be computed by ph 1 (s, a, b) = Pi (s) 1... b), where
PI:k (s) = (o(s [T PK (SW+1lSW Ni-tilss,,aa ans, bw))
Min(s, a) = (z)) == Ih He (awl 2 ((
(1, b) = (1(s))))) = - uN (bwl ((*)))
With abuse of notation, we let 115) = M1 (x())((((s)) == Piah- ( an-1), (s) == Pish (5))41:-11 a) 1 b) and ph (x) = Exee(e) (ii((s) for any information set E Xr.
We use P1-h-1 similarly.
Bandit feedback We assume that the value of ru ra a, b) is revealed to the players only when actions E A and B are taken in state S at time step h. Notice that the players are

---

not aware of the underlying state. Furthermore, we assume that the players know neither the state transition dynamics nor the set of states S. Such limitations impose significant difficulty as the players need to carefully play the game trying different actions to gain the information of the game.
Remark 1. Jin et al. (2020) consider a similar setting (from the view point of the max-player) of learning adversarial MDPs with bandit feedback wherein the reward function is chosen by adversary. Our setting is different in that the players have only imperfect information, and that the state transition dynamics is changing due the learning opponents. Nonetheless, the tree structure and perfect-recall assumptions allow a simple and efficiens model-free algorithm that we provide.
Remark 2. Another recent line of works, Bai and Jin (2020); Bai al. (2020); Liu et al. (2020), consider perfect information Markov game with bandits feedback, whereas our setting is the imperfect information one. By setting each information set of both players to a singleton of the state, the perfect information setting is recovered. However, we assume perfect recall and the tree structure of the game, Although those assumptions are standard in game theory, they make the direct comparison of our setting and theirs impossible.
Regret and Nash Equilibrium (NE) For policies y and v we define the expected return (of the max- max-player) by V := E En Ph (sh, ans by) (8h, an b₁). For sequences of policies (u') (mm E 11 and (v' keem Iimin the regret of the max-pla max-player, relative to some policy nd E IImax is defined as
R Nrun (u¹) = Σ Vulter vuser))
(I)
Similarly, CVn'' Vul is the min min-player's regret relative to some v E IImi.
Our aim is to compute a NE. The following well-known folklore theorem, which we prove in Appendix A, states that this problem can be converted into regret minimization problem.
Theorem 1. For each h [H), (Bn,an) Xn x A. and (yn, bn) Vn x B, define the average profile (T, v) by
(an(a))) Etzr (i and V. (bullu))) Et= 1
Et (in Σt= (
if the sum of the denominator is non-zero, otherwise as the uniform distribution over actions. If for some non-negative real value E, we have that (R (at) + RT (v"))()))) /)TT)/TT S E for any profile (ul, v\), then (p, D) are e-NE, i.e., maxpellmax VI.2 mil VP." S..
Given Theorem 1, we consider how to minimize the regret for the max- and min-player; or how to control the regret such that it grows sublinearly. The subsequent section presents algorithm, which we call implicit exploration online mirror descent (IXOMD), that accomplishes this goal.
Implicit Exploration Online Mirror Descent (IXOMD)
Due to the symmetry of the players, it suffices to consider only the learning of the max-player. Therefore, we mainly focus on and denote the max-player's regret (1) by R² ((²)). We first convert the original regret minimization problem into adversarial linear bandit an explanation behind the use of implicit exploration and introduce our algorithm, IXOMD, whose pseudocode is given in Algorithm 1. For simplicity, we first give simple-to-read but inefficient version. In Appendix F, we provide practical version, whose computational and memory complexity detailed in Section 3.3.
Then, give
Additional notation For a policy la E Tmaax and a sequence of functions f f== (fh (eee)) where M1n1 an fn (2h, an) by
fn : Xr, x A + R. we denote the scalar product Σxe(rr]
(n, f). We let F be the o-algebra generated by variables up to the beginning of the t-th episode,
ie., (8% ah. b,, 1hel) We let EE " == [
Forr example, Farina al. (2019) or Lanctot al. (2009).
5

---

Algorithm 1: IXOMD for the Max-Player
Input: IX hyper-parameter Ty E (0, 00) and OMD's learning rate v E (0, 00).
Output: A near-NE policy for the max-player.
Initialize 1 (an. [...) ) <- 1/A for each (Ih, On. h) E Xr x [
for t 1
do
for h 1,
Observe 2/ execute dj (-12)) and receive r
end
H f for h = H ....... do Construct the IX loss estimate Łg by
Set
1- r Mish (1), a/)) +
For each h E [H (with 7/411 f-1) 1)
z t 1 - ( (2/h) + pha(aj (ah)) (rrr))ppppp)))p)))))p exp(<x (xp(-n?h + log Zitz).
Update 2e to p at 2% by
10
(an (2f))) exp -npeh + log 2h+1 - -log 2%)
if az = af otherwise
p/ (an
(a (x%))=) -
p (an (xf)) exp(- log 27,)
and 1 (-(on)) p0 at other information sets E Nn.
11
12
end
13
end
return Policy p which is the average of p1,... PT defined in Theorem 1.
3.1
Conversion to online linear regret minimization
Note that for any profile (J, have
H
VR.
Σ
()n((n))Ls an (u (sn, (n) an, bn)
h=1 8a
EB
11
- Σ
(in an)
Σ
Prnn(snuunad by bn)ra(sn, an;ba); bn);
h= AA
86 E.EER ELEB
where used the facts that Mish dependent on (2), and rather than (sh, an). and Es, ES, f(8)) Exs Ex, Emser, fsr) for any function f. S - IR. Therefore defining loss by
(x an) =
Σ
(Inh(sn) (sn, bn)(1 rh rn(s ab. bn))
5y, EB
rewrite the regret (1) as?
nt (Ht)
Σ (p'- ut, ut,
(3)
As introduced at Additional notation, (p', IH Eng Cx2, uEA His an (2 an). Hence the meaning of μí' here is abused, and we are viewing it as sequence (ii))e of functions. In this case, j must satisfy the following two conditions: (non negatiiity pis (Ia, an) 2 0 for any o E Xr, and h [H]: (consistency) >,,, A fi (In, ax) = 1 a1-1) for any E Xs and E (2..... H), where (2^-1, -)) 1) is a unique predecessor of æh. and Enje E Min (x1, = 1 for any E X1. Nonetheless there is a bijective mapping between 1mmax and the set of 1r satisfying these two conditions. Therefore we do not discern these two sets.

---

This result tells us that we may convert the original regret minimization problem to linear one in which we choose μ² such that D (x²) grows sublinearly. Note that, mentioned in the introduction. this reduction is not new and can be traced back to the work by Romanovsky (1962); von Stengel (1996). important to remark that the losses are bounded in the unit interval. See Appendix E for proof of the following lemma.
Lemma 2. For all t, h, The On the loss is bounded ( ax) [0. 1].
3.2 Loss estimation and implicit exploration
To solve the regret minimization problem (3) with bandit feedback, we need to estimate e An unbiased importance sampling estimator is
[(e on mnj rh). 11,n (1 ap)
(1 and
However, instead, we estimate the loss by
I [aa iiion maj))
E (Tn, oh) =
(5)
Mi (2 an) +
where y a positive real value and in bandits (IX, Kocák et al., 2014; Neu, 2015; Lattimore and Szepesvári, 2020, Chapter 12), and we therefore refer to it as the IX estimator. Note that IX uses a biased estimate, but it prevents the variance of the IX estimator from becoming too large.
This estimator is used by implicit exploration
3.3 Efficient implementation, Space- and Time-Complexities
Given loss estimate, find 41 by solving
++ arg min n7 (u.²t) (u(lll)),
(6)
pellmax
where is the dilated entropy Destance-generating function (with uniform weights, Kroer al. (2015)) defined by
44 (a (2)) 1y (an (1h)
D(ulle')
Σ Σ
Mish (2k, as) log
1=1 EX,,
Note that is Bregman divergence, see Lemma Appendix E. The update in (6) has an easy implementation, explained next. For more details of its derivation, please refer to Appendix C. To compute a new policy, we first need to compute for each [M]].
7h = Σ ph (an (xh) exp T(an=0o,) -nnnin (1h, an) + log 7)tt))
on EAA
1 - μd, (x) + p1, (aj, (x exp (-nōt) ( (0h,, ah) + log Zhrt).
with Z := 1. Then, we can compute a new policy by
(8) Note that this policy is updated only at the information sets visited along the 1-th trajectory. This implies that the update requires O(H A) time-complexity per episode. Therefore the learning of the policies require ((THA) time-complexity in total.
M ++1 (axlx)) μ (an (xf)) exp (Lon==o;) (-nk ax) + log 2h+1) log 2i
Interestingly, the update of the average policy zu can also be performed in semi-online way, Appendix D. This method has a total time-complexity of O(TH + min(TH, X) and space- complexity of Omin(TTH, A))). Please refer to Algorithm 3 in Appendix FF for pseudocode of this practical implementation.
Algorithm 3 requires a post-hoc computation that is the source of O (min (T X)A) cime-compl.xiyy possible to defer the post-hoe computation until p(-|19, needed for playing game. this case, the computation of ((r()))))) is performed while traversing game tree. For one traversal, f computed for each h, and the total time-complexity ((HA) The space-complexity is unchanged and is O(min X)

---

Theoretical Analysis of IXOMD
We now analyze IXOMD. It has the following guarantee, which we shall prove the present section. Theorem (regret bound of IXOMD). Let å E (0,1) 1). The regret (1) satisfies the following guarantee with probability at least 1 -
Xt 27
X logg A
nH 27
max R. (Nt) 1 x'Ellmax
TTXA+
+
+HTXAA+
"
log A
where L == log A/)68. In particular 1
and 7
result in
THA
2T
Hi log A
max 1tt Ellmas
X TTH A + H
Remark 3. We emphasize that this result is agnostic of the min-player In particular, the same result holds for learning in partially observable MDP with adversarial state-transition dynamics and reward function, as long as assumptions similar to the tree-like structure and perfect recall hold.
Remark 4. In Theorem 3, adjusted 1i and Y using T, H, X, and A. Even when know T only, setting 17 1/vTT and y 1/VT guarantees an upper-bound of the order of Õ(X Av))s. If we additionally know H and A (which is likely to be the case). but do not know X. setting Vlog A/(THA) and y = 1/V2TA A still results in an upper- upper-bound of the order of VAA).
similar result holds for the min- min-player thanks to the symmetry. From Theorem and 3, it follows that the average profile (μ, v) is close to Nash equilibrium with high probability.
Corollary 3.1. Suppose that both max- and min-players learn their policies by IXOMD with the setting" of n and y Theorem Then with probability at least 1 - ô, the averuge profile (T. D) defined in Theorem I is E-Nash equilibrium, with
=== Ō TT
(XVA+YVB))
4.1 Proof of Theorem
Now we start the proof of Theorem 3. In the first step, we decompose the regret (3) to three terms:
RF. ( Σ (1 p1) - Σ (utee e 7o
ut,Et Et
(9)
BIAS 1
BIAS
REGRET
Then, we prove a high- high-probability upper-bound for each term. After deriving each upper-bound, Theorem follows simply by taking the union bound over the three terms.
For proving the upper- bounds, we need the following lemma, which almost immediately follows from Lemma 1 by Neu (2015) (also see Lemma 12.2 of Lattimore and Szepesvári (2020) for more general statement). For completeness we prove it in Appendix E.
Lemma 4. Let d (0,1) and 7 E oc). Fix h [H], and let a a' an) E 00, 27| be Ft measurable random variable for each (Ih, on) E Xr, x A. Then with probability at least - 8
Σ
Σ
a' d' an) (BiEE, an) (2n, ax)) s log
1
Ir En
We first prove an upper-bound of BIAS shown below.
$ We recall we hide with δ poly-log terms in " T,X, 1/1 "ote that A and X must be replaced with B and Y (resp.) for the min cin-player's and ry. Also note that to archive the same order of bound the one shown in this corollary, need neither X nor Y.

---

Lemma 5 (upper-bound of BIAS 1). Ler d E 1). It holds with probability at least 1 - 8/3 that
BIAS < HVVTT++
Proof. To see that this true, we first deduce that
H
1 Yox=shhan=oo (1 r1-
(
E
(iin an)
MIn (o an) +
Am EA
= 11=H
Am1 2y EME.A
hm1
where the inequality follows from facts that Min (2n, (H)/(Hnn (on, an) + 7) - 1, and 0 < 1 1 , < 1. By Hoeffding-Azuma inequality, we deduce that Σt= (nt, z - [e') 2 22 2 -11 V2T' with probability least 1 8/3. (The final inequality to simplify the result.) Next, we deduce that
(nt et E² 1
Σ
Σ
Malcon
1i (xn, e (z) and +
h= En
Tei an) Mh (2h an) +
Σ
Minlon, an)
h=1 EdA.OREA
11
11 S7 an)
Σ
Σ
Σ 1=1 zn En
Σ 1SAA
1=
where the first inequality follows from (1n, ap on)/(((. (Th, an) + 7) S 1, and the last inequality follows from Σ Exsexhaned I XA. Combining both bounds, we obtain the claimed result.
Next we prove an upper-bound of BIAS 2.
Lemma 6 (upper-bound of BIAS 2). Let 8 E (0, 1). For any jit Tmax it holds with probability at least 1 8/3 that BIAS S (2)(27).
Proof. Note that
H
ΣΣ
Σ
M (In, and (Ei(En, an) Ei a:))
us EEn
Σ
Σ
(e and
Σ
[(oh mas mas) ah) -E) ch))
h= By EXY.
1=1 2/ EdKi En
Now apply Lemma 4 to & and deduce that, for each (I an), we have
T
Σ
[a, =an (Ch( a/,) - e, (1th11 ah)) s 4
2y
1=1
with probability at least 8/(3XA). We deduce that
H
ΣΣ
Σ
(Es,
(en, (E)(((n C/ an))
1=1 an EEAA
Xt
Σ
Σ
Min(sn, an)
2
27
with probability at least - 8/3, using union bound over all (æh, an) E Xn. x A and each h. G

---

Finally we prove the following upper-bound of REGRET in Appendix B. Lemma (upper-bound of REGRET). Let (0, For any pl =max holds with probability at least - 5/3 that
X log A +
n
REGRET'S I
n
27
5 Conclusion
We theoretically studied the problem of learning a NE of an IIG under a perfect-recall assumption. We provided the IXOMD algorithm based OMD with the dilated entropy distance-generating function as regularizer and implicit exploration for estimation of the losses. We proved high-probability bound on the convergence rate to the NE of order OA + Y /BB /T)) derived from a regret bound of order ((XVAT) (for the max-player). Notably, the regret bound remains valid in the adversarial setting (where the opponent and the game are picked by an adversary). Furthermore, due to our choice of the regularizer, the updates of the policy (e.g., of the max-player) could be implemented with time- complexity of O A) per episode, which makes IXOMD also computationally efficient. Precisely, the total time complexity (after 7 episodes) of order (A min H, HX A+) Y)B) while the space complexity is of order (mmin(TH,, + min(TH,
An interesting next direction of research would be to characterize the problem-indepenee regret, e.g., for the max-player. in our setting. We conjecture that it of order O(vXAZ) even in the adversarial setting (where the opponent and the game are picked by an adversary). This would make our current bound to be loose by factor VX.
optimal
Acknowledgments
Tadashi Kozuno gratefully acknowledges funding from the Canada CIFAR AI Chairs Program, Amii, and NSERC. Pierre Ménard is supported by the SFI Sachsen- Anhalt for the project REBCI 28/2019/10/102024 by the Investitionsbank SachsenAnhalt.
References
Jacob Abemethy, U Berkeley, and Alexander Rakhlin. Competing in the Dark An Efficient Algorithm for Bandit Linear Optimization. In Conference on Learning Theory, 2008.
Yu Bai and Chi Jin. Provable self-play algorithms for competitive reinforcement learning. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research. PMLR, 2020.
Yu Bai, Chi Jin, and Tiancheng Yu. Near-optimal reinforcement learning with self-play. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neu- ral Information Processing Systems, volume 33. Curran Associates, Inc., 2020.
Neil Burch, Matej Moravcik, and Martin Schmid. Revisiting CFR+ and Alternating Updates. Journal of Artificial Intelligence Research, 2019.
Varsha Dani, Thomas Hayes, and Sham Kakade. The Price of Bandit Information for Online Platt, Koller, Y Singer, and S Roweis, editors, Advances in Neural Information Processing Systems, volume 20, 2008.
Optimization.
Gabriele Farina and Tuomas Sandholm. Model-Free Online Learning in Unknown Sequential Decision Making Problems and Games. AAAI Conference on Artificial Intelligence, 2021.
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generatin Functions. In Advances in Neural Infor- mation Processing Systems, 2019.
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Stochastic Regret Minimization in Extensive- Form Games. In International Conference Machine Learning, 2020.
10

---

Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent. In AAAI Conference on Artificial Intelligence, 2021a.
Gabriele Farina, Christian Kroer, and Tuomas Sandholm. Bandit Linear Optimization for Sequential Decision Making and Extensive-Fori Games. In AAAI Conference on Artificial Intelligence, 2021b.
Abraham D. Flaxman, Adam Tauman Kalai, and H. Brendan McMahan. Online Convex Optimization in the Bandit Setting: Gradient Descent without a Gradient. In Anmual ACM- Symposium on Discrete Algorithms, 2005.
Andrew Gilpin, Javier Peña, and Tuomas Sandholm. First-order algorithm with (ll((1 fc))) conver- genee for c-equilibrium in two-person zero-sum games. Mathematical Programming, 2012.
Geoffrey Gordon. No-regret Algorithms for Online Convex Programs. In Advances in Neural Information Processing Systems, 2007.
Sergiu Hart and Andreu Mas-Colell. A Simple Adaptive Procedure Leading to Correlated Equilibrium. Econometrica, 2000.
Samid Hoda, Andrew Gilpin, Javier Peña, and Tuomas Sandholm. Smoothing Techniques for Computing Nash Equilibria of Sequential Games. Mathematics of Operations Research, 2010.
Chi Jin, Tiancheng Jin, Haipeng Luo, Suvrit Sra, and Tiancheng Yu. Learning Adversarial Markov Decision Processes with Bandit Feedback and Unknown Transition. In International Conference on Machine Learning, 2020.
Tomáš Kocák, Gergely Neu, Michal Valko, and Rémi Munos. Efficient learning by implicit explo- ration in bandit problems with side observations. Advances in Neural Information Processing Systems, 2014.
Daphne Koller, Nimrod Megiddo, and Bernhard Von Stengel. Efficient Computation of Equilibria for Extensive Two-Person Games. Games and Economic Behavior, 1996.
Christian Kroer, Kevin Waugh, Fatma Kilinę-Karzann and Tuomas Sandholm. Faster First-Order Methods for Extensive-Form Game Solving. In ACM Conference on Economics and Computation, 2015.
Christian Kroer, Gabriele Farina, and Tuomas Sandholm. Solving Large Sequential Games with the Excessive Gap Technique. In Advances in Neural Information Processing Systems, 2018.
Christian Kroer, Kevin Waugh, Fatma Kaling-Kazza, and Tuomas Sandholm. Faster algorithms for extensive-form game solving via improved smoothing functions. Mathematical Programming, 2020.
Harold W Kuhn. Extensive Games and the Problem of Information. Annals of Mathematics Studies, 1953.
Mare Lanetot, Kevin Waugh, Martin Zinkevich, and Michael Bowling. Monte Carlo Sampling for Regret Minimization in Extensive Games. In Advances in Neural Information Processing Systems, 2009.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
Michael L.. Lituman. Markov Games as a Framework for Multi-Agent Reinforcement Learning. In International Conference Machine Learning, 1994.
Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin. A sharp analysis of model-based reinforcement learning with self-play. CORR, 2020.
Remi Munos, Julien Perolat, lean-Bap Lespiau, Mark Rowland, Bart De Vylder, Marc Lanctot, Finbarr Timbers, Daniel Hennes, Shayegan Omidshafiei, Audrunas Gruslys, et al. Fast Computation of Nash Equilibria Imperfect Information Games. In International Conference on Machine Learning, 2020.

---

John F Nash Jr. Equilibrium points in N-person games. Proceedings of the National Academy of Sciences of the United States of America, 1950.
Arkadi Nemirovski. Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems. SIAM Journal on Optimization, 2004.
Yu Nesterov. Smooth minimization of non-smooth functions. Mathematical programming, 2005.
Gergely Neu. Explore no more:
Improved high-probability regret bounds for non-stochastic bandits. In Advances Neural Information Processing Systems, 2015.
Martin J. Osborne and Ariel Rubinstein. A Course Game Theory. The MIT Press, 1994.
Marc Ponsen, Steven De Jong, and Mare Lanctot. Computing Approximate Nash Equilibria and Robust Best-Responses Using Sampling. Journal of Artificial Intelligence Research, 2011.
J. V. Romanovsky. Reduction of game with complete memory to matricial game. Dokl. Akad. Nauk SSSR, 1962.
Aviv Rosenberg and Yishay Mansour. Online Convex Optimization Adversarial Markov Decision Processes. In International Conference Machine Learning, 2019.
Lloyd Shapley. Stochastic Games. Proceedings of the National Academy of Sciences of the United States, 1953.
Malcolm Strens. A Bayesian Framework for Reinforcement Learning. In International Conference on Machine Learning, 2000.
Oskari Tammelin. Solving Large Imperfect Information Games Using CFR+. arXiv preprint
arXiv:1407.5044 2014.
Bernhard von Stengel. Efficient Computation of Behavior Strategies. Games and Economic Behavior, 1996.
Brian Hu Zhang and Tuomas Sandholm. Finding and Certifying (Near-) Optimal Strategies in Black-Boo Extensive-Fome Games. In AAAI Conference on Artificial Intelligence, 2021.
Yichi Zhou, J. Li, and J. Zhu, Posterior sampling for multi-agent reinforcement learning: solving extensive games with imperfect information. In International Conference on Learning Representa- lions, 2020.
Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret Minimization in Games with Incomplete Information. Advances neural information processing systems, 2007.
12


Reviews:
[{"review_id": "qpz9Q2uhSS", "reviewer": "Reviewer_BNiZ", "summary": "This paper studies partially observable extensive games with perfect recall. They propose a computationally efficient model-free algorithm with $\\sqrt{T}$-regret. The algorithm works by reducing the tree-structured game to a linear bandits problem and then applying some variant of EXP-IX (similar to Jin et al., 2020) to solve it.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "This paper is well-written and easy to follow. The new algorithm looks computationally efficient and has regret guarantee matching the best known result. Moreover, it can also play favourably against adversarial components. \n\nIs the conversion to online linear bandits first proposed in this work? If not, maybe it would be better to point this out explicitly in section 3.1. Besides, the algorithm designed in this paper bears much similarity to Jin et al., 2020. I feel it’s worthwhile to point it out in the paper.\n\nCould you provide a direct comparison between this paper and Lanctot et al. (2009); Farina et al. (2020) in terms of computational complexity? I believe this comparison is necessary especially when these works have the same regret.\n\nHow do you compare this work to [1]? I think it would be interesting to compare the two settings studied in this paper and [1]. Which setting is more general or practical? \n\nOverall this is an interesting paper making reasonable contributions. \n\n[1] A Sharp Analysis of Model-based Reinforcement Learning with Self-Play.\nQinghua Liu, Tiancheng Yu, Yu Bai, Chi Jin. ICML 2021\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "YgAh7HxqAWc", "reviewer": "Reviewer_5YpW", "summary": "This paper studies self-play algorithms in extensive form games with imperfect information. The proposed algorithm, IXOMD, can achieve the best-known sample complexity and achieve several desirable properties.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "I have a few concerns about the results:\n\n1. How is the POMG setting in this paper related to EGII? Are they just one thing? Because the name of POMG always reminds me of general MG, where you don't have a tree structure.\n\n2. The idea of reduce the problem into online linear bandit optimization and use a different divergence are brilliant. My understanding is that they are borrowed from existing literature and this paper improves them to high probability regret bound, right? Then I think maybe the authors want to make this explicit and add some explanation. For example, I don't understand why we need dilated entropy instead of KL as in adversarial MDP?\n\n3. On time complexity. The authors claim the proposed algorithm requires only O(HA) time per episode. However, there are many existing works on computational barriers in POMDP, which is a special case of POMG. For example, see the discussion in 1.1 in [2]. Why this is not a contradiction?\n\n4. On related work. The authors have made a long remark on related work on adversarial MDP. Actually, I think a more related setting is self-play algorithms in MG (with perfect information). Comparing with the sample complexity of algorithms for MG can also highlight the unique challenge in POMG. For example. see [3][4][5]\n\n5. On the setting. In the related work section, the authors make the difference between full information and bandit information. So in the bandit feedback setting, can we see the state (instead of just the observation)? I know the algorithm proposed in this paper doesn't need this additional information, just a question concerning the setup. Furthermore, a natural question will be, it seems knowing the state when rolling out a trajectory doesn't help to achieve a better rate (by comparing the rate with existing works). Am I understanding correctly?\n\n[1]  Regret Minimization in Games with Incomplete Information \n\n[2] Sample-Efficient Reinforcement Learning of Undercomplete POMDPs\n\n[3] Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium\n\n[4] Provable Self-Play Algorithms for Competitive Reinforcement Learning\n\n[5] Near-Optimal Reinforcement Learning with Self-Play", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This part is good.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "O0LwhH5HkkK", "reviewer": "Reviewer_o4zK", "summary": "This paper proposes Implicit Exploration Online Mirror Descent (IXOMD) algorithm that achieves sublinear regret in unknown extensive-form two-player zero-sum games with high probability. The setup is that player learn rewards only when actions are taken at some step, and do not learn about counterfactual reward they could have earned, have they made a different choice in the iteration. IXOMD is an adaptation of OMD, it uses importance sampling estimator of the losses with implicit exploration (to appropriately weigh the reward of the action taken and reduce its possibly high variance) and dilated entropy distance-generating function as a regularizer for the computation of next-step strategies.\nAuthors prove that IXOMD achieves sublinear regret with appropriate setting of the algorithm hyperparameters - the learning rate and the exploration penalty. Thus the algorithm can be used to approximate Nash equilibria (if both players use the algorithm) with high probability.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "The paper is quite dense in notation, but clear and easy to follow. The proposed OMD adaptation achieves a high-probability regret bound, compared to other OMD adaptations that achieve the bound only in expectation. As authors note, there exist several other algorithms for their proposed online setting, and while they claim to achieve a better convergence rate in theory, it is a bit shame that they did not compare them in experiments as well. Especially, when other works [1] found that in practice CFR-based methods are still faster than OMD, despite worse convergence rates of CFR. Adding the experiments would improve my rating.\n\nI do not understand the classification of \"adversarial game\" in Table 1. Some algorithms were classified as incapable of playing in the setting where the adversary also picks the game to play. This is a trivial game transformation, that can be formally achieved as the opponent has an additional decision node in which it picks the game to play, and thus this is a well specified large game (that can be decomposed into the multiple sub-games). Perhaps authors meant the adversary can pick any game whatsoever, from an infinite number of games? But wouldn't such an unlimited choice make the convergence rates vacuous, as they all depend on the number of infosets (that would be infinite as well?)\n\nAuthors write that \"IXOMD requires almost no prior knowledge of the game. [..] We only require an oracle providing the possible actions at encountered information sets and a bound on A, B, and H to tune optimally the learning rate\". \nHowever, in Remark 3, to set the learning rate and exploration, also the time horizon T is used. Without the knowledge of the time horizon the regret bound can still contain the bias caused by the exploration. This should be mentioned as another (theoretical) limitation when this algorithm can be used. In constrast, for example [2,3] have worse convergence rates, but their algorithm is independent of the time horizon, because the hyperparameters do not depend on time, thus may be suitable in a repeated play where we do not know the time horizon.\n\nOther comments:\n- L37-38 while CFR+ achieves 1/sqrt(T) in theory, in practice it is often 1/T and it does not need a choice of hyperparameters.\n\n\n[1]  Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functions\n\n[2]  Model-Free Online Learning in Unknown Sequential Decision Making Problems and Games. \n\n[3]   Stochastic Regret Minimization in Extensive-Form Games.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The time horizon should be discussed, see the main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "3sRq2imV-xC", "reviewer": "Reviewer_mGny", "summary": "This paper studies the problem of learning Nash equilibrium policies in two-player zero-sum extensive games, under the assumption of bandit feedback. The authors propose an algorithm that is based on Implicit Exploration and OMD, and they provide an high-probability regret bound that scales sub-linearly in the number of iterations and polynomially in the size of the game. Interestingly, the regret bound holds even in an online setting (not in self-play) in which both the policies of the opponent and the game structure are chosen adversarially.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "Originality: The problem studied in the paper is not novel, but it recently received a lot of attention in the literature. The ideas used in the paper are novel; in particular that of using Implicit Exploration.\n\nQuality: As far as I am concerned, the proofs are correct.\n\nClarity: Overall, the paper is clear, but there are some minor typos and I have some suggestions:\n- Line 9: \"Moreover...\" => \"Moreover,...\".\n- Line 19: \"max...\" => \"max-...\".\n- Line 58: \"consider\" => \"considers\".\n- Line 66: It is not clear to which algorithm the sentence \"This algorithm...\" refers to.\n- Line 69: \"such that\" => \"such as\".\n- Line 96: Is it \"O(H)\" or \"O(H A)\"?\n- Line 120: \"p_0\" is missing from the definition.\n- Line 128: \"define\" => \"defined\"; I think it's better to define \"X_h\" here.\n- Section 2: The notation is cumbersome and hard to follow; I would suggest the authors trying to avoid the use of multiple subscripts and apices and that of many indexes, such as \"h\", \"h'\", and \"k\". (Don't know actually if notation can be improved easily).\n- Line 184: \"gives\" => \"give\".\n- Line 9 in Algorithm 1: \"with...\" is redundant.\nAlso, it seems to me that the algorithm is working over the sequence-form strategy space. Am I correct? If yes, why didn't you frame the whole technical contribution in the sequence-form setting? I think that would have helped clarifying notation and presentation.\n\nSignificance: The paper provides a good contribution to its field, and I think it fits well within the scope of the NeurIPS conference.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Adequate.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies partially observable extensive games with perfect recall. They propose a computationally efficient model-free algorithm with sqrt(T) regret. All reviewers believe the results are solid and strong, and the techniques used in this paper are interesting. Therefore, we recommend acceptance.
Decision: Accept (Poster)