Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recall

Abstract:
We study the problem of learning a Nash equilibrium (NE) in an imperfect information 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 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 the convergence rate to the NE of order 1/ √ 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.

text: √ 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.

heading: 1 Introduction
text: We study the setting of learning a Nash equilibrium (NE, Nash Jr, 1950) in an imperfect information game (IIG, Osborne and Rubinstein, 1994). Precisely, we focus on two-player zero-sum IIG under the perfect-recall assumption (Kuhn, 1953). Perfect recall means that the players do not forget observations encountered or actions taken during the game. We model the game as a 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 Y for the max- and min-player. In learning by self play, we control both the max and min-player. After T episodes of the game we are asked to return a profile that is close to a NE in terms of exploitability gap (Ponsen et al., 2011).
Full feedback In 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-form 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 a saddle point (Hoda et al., 2010). It is then possible to adapt first-order methods such as Nesterov’s smoothing (Nesterov, 2005) and MirrorProx (Nemirovski, 2004) to IIG, as done respectively by Hoda et al. (2010); Kroer et al. (2018) and Kroer et al. (2015, 2020). These methods have a rate of
∗Equal contribution
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
convergence of order Õ((X + Y )/T ), where Õ hides poly-log terms in eH , X,A, Y,B, T .2 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. (2007) based on the regret-matching 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, 2021a). These algorithms however only enjoy a (known) guarantee of convergence of order Õ((X √ A + Y √ B)/ √ T ). 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 time-complexity of order O(S). Sampling can reduce this time-complexity to O(X + Y ),3 i.e., 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 a 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) to learn a model and then use the CFR algorithm in games sampled from the posterior. They obtain a convergence rate of order Õ(max(XA + Y B, √ S)/ √ T ) but only when the games are actually sampled according to the known prior. In addition, they still need to know the state space and its structure4 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 a high-probability bound on the exploitability gap of order Õ((X √ A+ Y √ B)/ √ T ).
Bandit feedback, model-free Our results follows another line of work which consider a modelfree approach. A well known algorithm of this type is outcome-sampling MCCFR (Lanctot et al., 2009; Farina et al., 2020), which builds an importance-sampling estimate of the counterfactual regret given exploration profile (named balanced strategy by Farina et 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.4 In particular, following the uniform distribution over the actions at each information set is not necessarily a good choice, e.g., when the tree formed by the information set space is not balanced. This algorithm has a guarantee of order Õ((X √ A+ Y √ B)/ √ T ) 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 a high-probability bound on the exploitability gap of order Õ(poly(X,A, Y,B)/T 1/4). Note that this bound is a 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.1). Precisely, they use the online mirror descent (OMD) algorithm with the dilated entropy distance-generating 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 a rate of order Õ((XA + Y B)/ √ T ), which is, similarly as 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.
2Therefore, we hide polynomial dependence on the horizon H . 3Note that O(X + Y ) is at most O(S). 4By structure we refer to the tree structure of the state space or observations spaces, see Section 2.
1 Only in expectation according to a known prior on the game. 2 Only in expectation.
To obtain high-probability bound, we instead propose to use an importance sampling estimator of the losses with implicit exploration (Kocák et 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 distance-generating function (using uniform weights) as a regularizer and add implicit exploration in the importance sampling estimator of the losses. Using our new analysis of this particular combination, we prove a highprobability bound on the exploitability gap of the average profile of order Õ((X √ A+ Y √ B)/ √ T ); cf. Table 1 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, e.g., of the max-player, of order Õ(X √ AT ), remains valid if 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 notable difference is that we use the dilated entropy distance-generating function as a regularizer instead of the un-normalized Kullback-Leibler divergence (Rosenberg and Mansour, 2019). Our choice of regularizer allows an efficient update of the current policy with a O(HA) 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(HA) computations per episode. Interestingly, we can also update the average profile (which will be returned at the end of the learning, see Section 3.3) in an online fashion. As consequence, IXOMD enjoys an overall time-complexity of O(TH(A+B) + min(TH,X)A+ min(TH, Y )B) and space-complexity of order O(min(TH,X)A+ min(TH, Y )B). 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 optimally5 tune the learning rate, see Remark 4.
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 a provably high-probability convergence rate of order Õ((X √ A+ Y √ B)/ √ T ). The
time-complexity of IXOMD is of order O(TH(A+B) + min(TH,X)A+ min(TH, Y )B) with a space-complexity of order O(min(TH,X)A+ min(TH, Y )B).
• If only one player follows IXOMD, e.g., the max-player, then its regret is w.h.p. at most Õ(X √ AT ). The important property of our result is that it remains valid even if the policy
and the game are picked by an adversary at each episode. Furthermore, the time-complexity
5Precisely, with this knowledge we obtain a regret bound, e.g. for the max-player, of order Õ(X √ AT );
whereas we get Õ(XA √ T ) without it.
of IXOMD per episode is of order O(HA). This answers an open problem of Farina et al. (2021b); Farina and Sandholm (2021). • IXOMD only needs to know the possible actions at the encountered information sets and a
bound on A, B, and H to tune the learning rate. In particular, we do not need to know the list of information sets in advance.

heading: 2 Preliminaries
text: In this section, we introduce our notations and our setting—partially observable Markov game (POMG) with bandit feedback and perfect recall. For a positive integer i, we denote by [i] the set {1, 2, . . . , i}. For a finite set A, we let ∆A or ∆(A) denote the set of all probability distributions over A.
Partially observable Markov game (POMG) We consider an episodic, tabular, two-player, zerosum POMG (S,X ,Y,A,B, H, {ph}h∈[H], {rh}h∈[H]), which consists of the following components (Littman, 1994; Shapley, 1953): a finite state space S of size S, its information set spaces (partitions of S) X of size X and Y of size Y for the max- and min-player (resp.), finite action spaces A of size A and B of size B for the max- and min-player (resp.), time-horizon H ∈ N, initial state distribution p0 ∈ ∆(S), a state-transition probability kernel ph : S × A× B → ∆(S) for each h ∈ [H], and a reward function rh : S ×A×B → [0, 1] for each h ∈ [H]. For a state s ∈ S we denote by x(s) ∈ X and y(s) ∈ Y information sets such that s ∈ x(s) and y ∈ y(s).
Learning procedure The players play this game for T episodes, following so-called policies. A policy µ of the max-player is a sequence (µh)h∈[H] of mappings from Xh to ∆A. (Xh ⊂ X is defined later.) A policy ν of the min-player is defined similarly. We let Πmax and Πmin denote the sets of max- and min-player’s policies, respectively. The t-th episode proceeds as follows: an initial state st1 is sampled from p0. At the step h, the max- and min-player (resp.) observe their information sets xth := x(s t h) and y t h := y(s t h). Given the information, the max- and min-player (resp.) choose and execute actions ath ∼ µth(·|xh) and bth ∼ νth(·|yh). As a result, the current state transitions to a next state sth+1 ∼ ph(·|sth, ath, bth), and the max- and min-player receive rewards rth := rh(sth, ath, bth) and −rth, respectively. This is repeated until a time step H , at which the episode finishes.
Tree-like game structure and perfect recall assumption We assume that the game has a tree-like structure: for any state s ∈ S, there is a unique step h and history (s1, a1, b1, . . . , sh = s) to reach s. Precisely, for any policy of the players, for any realization of the game (i.e., trajectory) (s′k, a ′ k, b ′ k)k∈[H], conditionally to s ′ i = s, it almost surely holds that i = h and (s ′ 1, . . . , s ′ h) = (s1, . . . , sh). 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 ∈ X there is a unique history (x1, a1, . . . , xh = x) up to x. These assumptions require that X can be partitioned to H subsets (Xh)h∈[H] such that xh ∈ Xh is reachable only at time step h; otherwise there would be two different histories up to xh. S and Y can be also partitioned into H subsets (Sh)h∈[H], and (Yh)h∈[H], respectively.
Given the assumptions above, there exists a unique history (s1, a1, b1, . . . , sh = s, ah = a, bh = b) ending with (sh = s, ah = a, bh = b) for any state s ∈ Sh, the max-player’s action a ∈ A, and the min-player’s action b ∈ B. Accordingly, the probability of sh = s, ah = a, bh = b can be computed by pµ,νh (s, a, b) = p1:h(s)µ1:h(s, a)ν1:h(s, b), where
p1:h(s) := p0(s1) ∏h−1 h′=1 ph′ (sh′+1|sh′ , ah′ , bh′) ,
µ1:h(s, a) := µ1:h(x(s), a) := ∏h h′=1 µh′ (ah′ |x(sh′)) ,
ν1:h(s, b) := ν1:h(y(s), b) := ∏h h′=1 νh′ (bh′ | y(sh′)) .
With abuse of notation, we let µ1:h−1(s) := µ1:h−1(x(s)) := µ1:h−1(sh−1, ah−1), p µ,ν h (s) := p1:h(s)µ1:h−1(s, a)ν1:h−1(s, b) and p µ,ν h (x) := ∑ s∈x(s) p µ,ν h (s) for any information set x ∈ Xh. We use ν1:h−1 similarly.
Bandit feedback We assume that the value of rh(s, a, b) is revealed to the players only when actions a ∈ A and b ∈ B are taken in a state s ∈ 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 a 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 an adversary. Our setting is different in that the players have only imperfect information, and that the state transition dynamics is changing due to the learning opponents. Nonetheless, the tree structure and perfect-recall assumptions allow a simple and efficient model-free algorithm that we provide. Remark 2. Another recent line of works, Bai and Jin (2020); Bai et 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 be 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 µ and ν we define the expected return (of the max-player) by V µ,ν := ∑H h=1 ∑ sh∈Sh,ah∈A,bh∈B p µ,ν h (sh, ah, bh)rh(sh, ah, bh). For sequences of policies (µt)t∈[T ] ∈ ΠTmax and (νt)t∈[T ] ∈ ΠTmin, the regret of the max-player, relative to some policy µ† ∈ Πmax, is defined as
RTmax(µ †) := T∑ t=1 ( V µ †,νt − V µ t,νt ) . (1)
Similarly, ∑T t=1(V µt,νt − V µt,ν†) is the min-player’s regret relative to some ν† ∈ Πmin.
Our aim is to compute a NE. The following well-known folklore theorem,6 which we prove in Appendix A, states that this problem can be converted into a regret minimization problem. Theorem 1. For each h ∈ [H], (xh, ah) ∈ Xh × A, and (yh, bh) ∈ Yh × B, define the average profile (µ, ν) by
µh(ah|xh) := ∑T t=1 µ t 1:h(xh, ah)∑T
t=1 µ t 1:h−1(xh)
and νh(bh|yh) := ∑T t=1 ν t 1:h(yh, bh)∑T
t=1 ν t 1:h−1(yh)
, (2)
if the sum of the denominator is non-zero, otherwise as the uniform distribution over actions. If for some non-negative real value ε, we have that (RTmax(µ †) + RTmin(ν †))/T ≤ ε for any profile (µ†, ν†), then (µ, ν) are an ε-NE, i.e., maxµ∈Πmax V µ,ν −minν∈Πmin V µ,ν ≤ ε.
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 an algorithm, which we call implicit exploration online mirror descent (IXOMD), that accomplishes this goal.
3 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 it and denote the max-player’s regret (1) by RT (µ†). We first convert the original regret minimization problem into a adversarial linear bandit one. Then, we give 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 a simple-to-read but inefficient version. In Appendix F, we provide a practical version, whose computational and memory complexity are detailed in Section 3.3.
Additional notation For a policy µ ∈ Πmax and a sequence of functions f := (fh)h∈[H], where fh : Xh ×A → R, we denote the scalar product ∑ h∈[H] ∑ xh∈Xh,a∈A µ1:h(xh, ah)fh(xh, ah) by 〈µ, f〉. We let F t−1 be the σ-algebra generated by variables up to the beginning of the t-th episode, i.e., {sτh, aτh, bτh}h∈[H],τ∈[t−1]. We let Et−1[ · ] := E[ · |F t−1].
6For example, see Farina et al. (2019) or Lanctot et al. (2009).
Algorithm 1: IXOMD for the Max-Player Input: IX hyper-parameter γ ∈ (0,∞) and OMD’s learning rate η ∈ (0,∞). Output: A near-NE policy for the max-player.
1 Initialize µ1h(ah|xh)← 1/A for each (xh, ah, h) ∈ Xh ×A× [H]. 2 for t = 1, . . . , T do 3 for h = 1, . . . ,H do 4 Observe xth, execute a t h ∼ µth(·|xth), and receive rth. 5 end 6 Set ZtH+1 ← 1. 7 for h = H, . . . , 1 do 8 Construct the IX loss estimate ˜̀th by
˜̀t h ←
1− rth µt1:h(x t h, a t h) + γ ·
9 For each h ∈ [H] (with ZtH+1 ← 1) Zth ← 1− µth(ath|xth) + µth(ath|xth) exp ( −η˜̀th + logZth+1).
10 Update µt to µt+1 at xth by
µt+1h (ah|x t h)←
{ µth(ah|xth) exp ( −η˜̀th + logZth+1 − logZth) if ah = ath
µth(ah|xth) exp(− logZth) otherwise
11 and µt+1(·|xh)← µt(·|xh) at other information sets xh ∈ Xh . 12 end 13 end 14 return Policy µ which is the average of µ1, . . . , µT defined in Theorem 1.

heading: 3.1 Conversion to online linear regret minimization
text: Note that for any profile (µ, ν), we have
V µ,ν = H∑ h=1 ∑ sh∈Sh,ah∈A,bh∈B p1:h(sh)µ1:h(sh, ah)ν1:h(sh, bh)rh(sh, ah, bh)
= H∑ h=1 ∑ xh∈Xh,ah∈A µ1:h(xh, ah) ∑ sh∈xh,bh∈B p1:h(sh)ν1:h(sh, bh)rh(sh, ah, bh),
where we used the facts that µ1:h is dependent on (xh, ah) rather than (sh, ah), and ∑ sh∈Sh f(sh) =∑
xh∈Xh ∑ sh∈xh f(sh) for any function f : S → R. Therefore defining a loss by
` th(xh, ah) := ∑
sh∈xh,bh∈B
p1:h(sh)ν t 1:h(sh, bh)(1− rh(sh, ah, bh)) ,
we can rewrite the regret (1) as7
RT (µ†) = T∑ t=1 〈 µt − µ†, `t 〉 . (3)
7As introduced at Additional notation, 〈µt, ˜̀t〉 = ∑Hh=1∑xh∈Xh,a∈A µt1:h(xh, ah)˜̀th(xh, ah). Hence the meaning of µt here is abused, and we are viewing it as a sequence (µt1:h)h∈[H] of functions. In this case, µ t must satisfy the following two conditions: (non-negativity) µt1:h(xh, ah) ≥ 0 for any xh ∈ Xh and h ∈ [H]; (consistency) ∑ ah∈A µt1:h(xh, ah) = µ t 1:h−1(xh−1, ah−1) for any xh ∈ Xh and h ∈ {2, . . . , H}, where
(xh−1, ah−1) is a unique predecessor of xh, and ∑ a1∈A µ t 1:1(x1, a1) = 1 for any x1 ∈ X1. Nonetheless there is a bijective mapping between Πmax and the set of µt 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 a linear one in which we choose µt such that RT (µ†) grows sublinearly. Note that, as mentioned in the introduction, this reduction is not new and can be traced back to the work by Romanovsky (1962); von Stengel (1996). It is important to remark that the losses are bounded in the unit interval. See Appendix E for a proof of the following lemma. Lemma 2. For all t, h, xh, ah the loss is bounded `th(xh, ah) ∈ [0, 1].

heading: 3.2 Loss estimation and implicit exploration
text: To solve the regret minimization problem (3) with bandit feedback, we need to estimate `t. An unbiased importance sampling estimator is
̂̀t h(xh, ah) :=
I{xh=xth,ah=ath} µt1:h(xh, ah)
( 1− rth ) . (4)
However, instead, we estimate the loss by
˜̀t h(xh, ah) :=
I{xh=xth,ah=ath} µt1:h(xh, ah) + γ
( 1− rth ) , (5)
where γ is a positive real value and a hyper-parameter. This estimator is used by implicit exploration 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.

heading: 3.3 Efficient implementation, Space- and Time-Complexities
text: Given a loss estimate, we find µt+1 by solving
µt+1 := arg min µ∈Πmax
η 〈 µ, ˜̀t〉+ D(µ∥∥µt) , (6)
where D is the dilated entropy distance-generating function (with uniform weights, Kroer et al. (2015)) defined by
D(µ‖µ′) := H∑ h=1 ∑ xh∈Xh,ah∈A µ1:h(xh, ah) log µh(ah|xh) µ′h(ah|xh) ·
Note that D is a Bregman divergence, see Lemma 9 in Appendix E. The update in (6) has an easy implementation, as 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 h ∈ [H],
Zth := ∑ ah∈A µth(ah|xth) exp ( I{ah=ath} ( −η˜̀tH(xth, ah) + logZth+1))
= 1− µth(ath|xth) + µth(ath|xth) exp ( −η˜̀tH(xth, ath) + logZth+1), (7)
with ZtH+1 := 1. Then, we can compute a new policy by
µt+1h (ah|x t h) = µ t h(ah|xth) exp ( I{ah=ath} ( −η˜̀th(xth, ah) + logZth+1)− logZth) . (8)
Note that this policy is updated only at the information sets visited along the t-th trajectory. This implies that the update requires O(HA) time-complexity per episode. Therefore the learning of the policies require O(THA) time-complexity in total. Interestingly, the update of the average policy µ can also be performed in a semi-online way, see Appendix D. This method has a total time-complexity of O(THA + min(TH,X)A) and spacecomplexity of O(min(TH,X)A). Please refer to Algorithm 3 in Appendix F for a pseudocode of this practical implementation.
Algorithm 3 requires a post-hoc computation that is the source ofO(min(TH,X)A) time-complexity. It is possible to defer the post-hoc computation until µ(·|xh) is needed for playing a game. In this case, the computation of µ(·|xh) is performed while traversing a game tree. For one traversal, µ(·|xh) is computed for each h, and the total time-complexity isO(HA). The space-complexity is unchanged and is O(min(TH,X)A).
4 Theoretical Analysis of IXOMD
We now analyze IXOMD. It has the following guarantee, which we shall prove in the present section.
Theorem 3 (regret bound of IXOMD). Let δ ∈ (0, 1). The regret (1) satisfies the following guarantee with probability at least 1− δ
max µ†∈Πmax
RT (µ†) ≤ H √ 2Tι+ γTXA+ Xι
2γ + X logA η + ηHTXA+
ηH2ι
2γ ,
where ι := log(3XA/δ). In particular η =
√ logA
THA and γ =
√ ι
2TA result in
max µ†∈Πmax
RT (µ†) ≤ H √ 2Tι+X √ 2TAι+X √ THA logA+H
√ Hι logA
2 .
Remark 3. We emphasize that this result is agnostic of the min-player. In particular, the same result holds for learning in a 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, we adjusted η and γ using T , H , X , and A. Even when we know T only, setting η = 1/ √ T and γ = 1/ √ T guarantees an upper-bound of the order of Õ(XA √ T )8. If we additionally know H and A (which is likely to be the case), but do not know X , setting η = √ logA/(THA) and γ = 1/ √ 2TA still results in an upper-bound of the order of Õ(X √ TA).
A similar result holds for the min-player thanks to the symmetry. From Theorem 1 and 3, it follows that the average profile (µ, ν) is close to a Nash equilibrium with high probability.
Corollary 3.1. Suppose that both max- and min-players learn their policies by IXOMD with the setting9 of η and γ in Theorem 3. Then with probability at least 1 − δ, the average profile (µ, ν) defined in Theorem 1 is ε-Nash equilibrium, with
ε := Õ (
1√ T
( X √ A+ Y √ B )) .

heading: 4.1 Proof of Theorem 3
text: Now we start the proof of Theorem 3. In the first step, we decompose the regret (3) to three terms:
RT (µ†) = T∑ t=1 〈 µt, ` t − ˜̀t〉︸ ︷︷ ︸
BIAS 1
− T∑ t=1 〈 µ†, ` t − ˜̀t〉︸ ︷︷ ︸
BIAS 2
+ T∑ t=1 〈 µt − µ†, ˜̀t〉︸ ︷︷ ︸ REGRET . (9)
Then, we prove a high-probability upper-bound for each term. After deriving each upper-bound, Theorem 3 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 a more general statement). For completeness we prove it in Appendix E.
Lemma 4. Let δ ∈ (0, 1) and γ ∈ (0,∞). Fix h ∈ [H], and let αt(xh, ah) ∈ [0, 2γ] be F t−1measurable random variable for each (xh, ah) ∈ Xh ×A. Then with probability at least 1− δ
T∑ t=1 ∑ xh∈Xh,ah∈A αt(xh, ah) (˜̀t h(xh, ah)− ` th(xh, ah) ) ≤ log 1 δ
We first prove an upper-bound of BIAS 1 shown below.
8We recall that we hide with Õ poly-log terms in eH , T,X,A, 1/δ. 9Note that A and X must be replaced with B and Y (resp.) for the min-player’s η and γ. Also note that to
archive the same order of a bound as the one shown in this corollary, we need neither X nor Y .
Lemma 5 (upper-bound of BIAS 1). Let δ ∈ (0, 1). It holds with probability at least 1− δ/3 that BIAS 1 ≤ H √ 2Tι+ γTXA.
Proof. To see that this is true, we first deduce that〈 µt, ˜̀t〉 = H∑
h=1 ∑ xh∈Xh,ah∈A µt1:h(xh, ah) I{xh=xth,ah=ath} µt1:h(xh, ah) + γ ( 1− rth ) ≤
H∑ h=1 ∑ xh∈Xh,ah∈A I{xh=xth,ah=ath} = H∑ h=1 1 = H ,
where the inequality follows from facts that µt1:h(xh, ah)/(µ t 1:h(xh, ah) + γ) ≤ 1, and 0 ≤ 1 − rth ≤ 1. By Hoeffding-Azuma inequality, we deduce that ∑T t=1〈µt, ˜̀t − Et−1[˜̀t]〉 ≥
−H √ 2T log(3/δ) ≥ −H √
2Tι with probability at least 1 − δ/3. (The final inequality is to simplify the result.) Next, we deduce that〈
µt, ` t − Et−1 [˜̀t]〉 = H∑
h=1 ∑ xh∈Xh,ah∈A µt1:h(xh, ah) ( 1− µ t 1:h(xh, ah) µt1:h(xh, ah) + γ ) ` th(xh, ah)
= H∑ h=1 ∑ xh∈Xh,ah∈A µt1:h(xh, ah) γ` th(xh, ah) µt1:h(xh, ah) + γ
≤ γ H∑ h=1 ∑ xh∈Xh,ah∈A ` th(xh, ah) ≤ γ H∑ h=1 ∑ xh∈Xh,ah∈A 1 ≤ γXA ,
where the first inequality follows from µt(xh, ah)/(µt1:h(xh, ah) + γ) ≤ 1, and the last inequality follows from ∑H h=1 ∑ xh∈Xh,ah∈A 1 = ∑H h=1|Xh|A = 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 δ ∈ (0, 1). For any µ† ∈ Πmax it holds with probability at least 1− δ/3 that BIAS 2 ≤ Xι/(2γ).
Proof. Note that T∑ t=1 H∑ h=1 ∑ xh∈Xh,a∈A µ†1:h(xh, ah) (˜̀t h(xh, ah)− ` th(xh, ah) )
= H∑ h=1 ∑ xh∈Xh,ah∈A µ†1:h(xh, ah) T∑ t=1 ∑ x′h∈Xh,a ′ h∈A I{x′h=xh,a′h=ah} (˜̀t h(x ′ h, a ′ h)− ` th(x′h, a′h) ) ︸ ︷︷ ︸
♣
.
Now we can apply Lemma 4 to ♣ and deduce that, for each (xh, ah), we have T∑ t=1 ∑ x′h∈Xh,a ′ h∈A I{x′h=xh,a′h=ah} (˜̀t h(x ′ h, a ′ h)− ` th(x′h, a′h) ) ≤ ι 2γ
with probability at least 1− δ/(3XA). We deduce that T∑ t=1 H∑ h=1 ∑ xh∈Xh,a∈A µ†1:h(xh, ah) (˜̀t h(xh, ah)− ` th(xh, ah) )
≤ ι 2γ H∑ h=1 ∑ xh∈Xh,ah∈A µ†1:h(xh, ah) ≤ Xι 2γ
with probability at least 1− δ/3, using a union bound over all (xh, ah) ∈ Xh ×A and each h.
Finally we prove the following upper-bound of REGRET in Appendix B. Lemma 7 (upper-bound of REGRET). Let δ ∈ (0, 1). For any µ† ∈ Πmax it holds with probability at least 1− δ/3 that
REGRET ≤ X logA η + ηHTXA+ ηH2ι 2γ .

heading: 5 Conclusion
text: We theoretically studied the problem of learning a NE of an IIG under a perfect-recall assumption. We provided the IXOMD algorithm based on OMD with the dilated entropy distance-generating function as a regularizer and implicit exploration for estimation of the losses. We proved a high-probability bound on the convergence rate to the NE of order Õ(X √ A+ Y √ B)/ √ T ) derived from a regret bound of order Õ(X √ AT ) (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 a timecomplexity ofO(HA) per episode, which makes IXOMD also computationally efficient. Precisely, the total time complexity (after T episodes) is of orderO(TH(A+B)+min(TH,X)A+min(TH, Y )B) while the space complexity is of order O(min(TH,X)A+ min(TH, Y )B). An interesting next direction of research would be to characterize the problem-independent optimal regret, e.g., for the max-player, in our setting. We conjecture that it is of order Õ( √ XAT ) 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 a factor √ X .

heading: Acknowledgments
text: 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 ZS/2019/10/102024 by the Investitionsbank SachsenAnhalt.

Review summaries:
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. 

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.

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. Authors 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.