Posterior sampling for multi-agent reinforcement learning: solving extensive games with imperfect information
Authors: Yichi Zhou
Jialian Li
Jun Zhu
Venue:  (2020)

Abstract: Posterior sampling for reinforcement learning (PSRL) is a useful framework for making decisions in an unknown environment.  PSRL maintains a posterior distribution of the environment and then makes planning on the environment sampled from the posterior distribution. Though PSRL works well on single-agent reinforcement learning problems, how to apply PSRL to multi-agent reinforcement learning problems is relatively unexplored. In this work, we extend PSRL to two-player zero-sum extensive-games with imperfect information (TEGI), which is a class of multi-agent systems. More specifically, we combine PSRL with counterfactual regret minimization (CFR), which is the leading algorithm for TEGI with a known environment. Our main contribution is a novel design of interaction strategies. With our interaction strategies, our algorithm provably converges to the Nash Equilibrium at a rate of $O(\sqrt{\log T/T})$. Empirical results show that our algorithm works well.

Published as a conference paper at ICLR 2020
POSTERIOR SAMPLING FOR MULTI-AGENT REINFORCE- MENT LEARNING: SOLVING EXTENSIVE GAMES WITH
IMPERFECT INFORMATION
Yichi Zhou, Jialian Li, Jun Zhu"
Dept. of Comp. Sci. & Tech., BNRist Center, Institute for AI, Tsinghua University; RealAI wofhqn@gmail.commm com, 1ij ian an 701 63. com, desz j@mail. tsinghua. edu. en
ABSTRACT
Posterior sampling for reinforcement learning (PSRL) is useful framework for making decisions an unknown environment. PSRL maintains a posterior distri- bution of the environment and then makes planning from the posterior distribution. Though PSRL works well on single-agent rein- forcement learning problems, how apply PSRL multi-agent reinforcement learning problems is largely unexplored. In this work, we extend PSRL to two- player zero-sum extensive-games with imperfect information (TEGI), which is a class of multi-agent systems. Technically, we combine PSRL with counterfac- tual regret minimization (CFR), which leading algorithm for TEGI with a known environment. Our main contribution is novel design of interaction strate- gies. With our interaction strategies, our algorithm provably converges the Nash Equilibrium a rate of O( Olylog T/T). Empirical results show that our algorithm works well.
environment sampled
INTRODUCTION
Reinforcement Learning (RL) (Sution Bartd, 201) provides a framework for decision-making problems in an unknown environment, such as robotics control. In an RI. problem, agents improve their strategies by gaining information from iterative interactions with the environment, One typical target in designing RL algorithms is to reduce the number of interactions needed to find good strate- gies. Thus, how to reduce the number of samples by designing efficient interaction strategies is one of the key challenges in RL.
Posterior sampling for RL (PSRL) (Strens, 2000) provides a useful framework for deciding how interact with the environment. PSRL originates from the famous bandit algorithm Thompson Sampling (Russo all 2018), which uses samples from posterior distributions bandit parameters calculate current policy. PSRL also maintains a posterior distribution for the underlying envi- ronment and uses an environment which is sampled from this posterior to compute its interaction strategies. The interaction strategies are then used to interact with the environment to collect data. The design of the interaction strategies depends on the specific property of the task. For example, in a single-agent RL (SARL) problem, PSRL takes the strategy with the maximum expected reward on the sampled environment as the interaction strategy (Oshand all, 2013). Theoretical and empirical results (Oshand Van Roy 2016) both demonstrate that PSRL one of the near-optimal methods for SARL. Moreover, although PSRL is Bayesian-style algorithm, empirical evaluation (Chapellc Li 2010) and theoretical analysis on the multi-armed bandit problems (Agrawal & Goyal, 2017) suggest that it also enjoys good performance for problem with fixed parameters.
However, applying PSRL to multi multi-agent RL (MARL) tasks requires additional design on the interac- tion strategies. This is because the goal of MARL is quite different from that of SARL. In an MARL problem, each agent still aims to maximize its own reward, but the reward of an agent's strategy re- lies not only the environment, but also the strategies of other agents. Therefore, in MARL, the goal of learning is generally referred to finding a Nash Equilibrium (NE) where no agent is willing
"J.Z.is the corresponding author.

---

Published as a conference paper at ICLR 2020
to deviate its strategy individually. So should design the interaction strategies with which the agents can find or approximate the NE efficiently.
More specifically, we consider the RL problems in imperfect information extensive games (Oshorne & Rubinstei 1994). Extensive games provide a unified model for sequential decision-making problems in which agents take actions in turn. Imperfect information here means that agents can keep their own private information, such as the private cards in poker games. Games with imperfect information are also fundamental to many practical applications such as economics and security. In particular, we concentrate on two-player zero-sum imperfect information games (TEGI) where there are two players gaining opposite rewards and chance player to model the transitions of the environment. When the environment (i.e. the transition functions of the chance player and the reward functions) known, counterfactual regret minimization (CFR) (Zinkevich et all, 2008) the leading algorithm in approximating the NE in TEGI. However, in the RI. setting where the environment unknown, CFR is not applicable.
In this work, present a posterior sampling algorithm for TEGIs with the technique of CFR. That is, we apply CFR to the environment sampled from posterior distribution. Our main contribution is a novel design of interaction strategies for the RL problem of TEGIs. With the proposed strategies, show that our algorithm provably converge to approximate NE at rate of O( (looo T/T). T/TT Empirical results show that our algorithm works well.
2 PRELIMINARY
In this section, we formally define the task of two-player zero-sum imperfect information games (TEGI) under Reinforcement Learning; and then briefly review two closely related techniques, namely counterfactual regret minimization (CFR) (Zinkeyich et all (008) and posterior sampling for reinforcement learning (PSRL) (Osband al 2013), which inspire our solution.
2.1 PROBLEM FORMULATION OF TEGI
We start from the definition of general N-player extensive games (See (Oshorne & Rubinstein, [994, pg. 200) for formal definition.), which include TEGI as nontivial special case when N = 2.
Definition (Extensive game). An extensive game has the following components:
finite set of players that includes N agents and chance player C representing the "Nature" of the game.
finite H of sequences that satisfies: 1) The empty sequence is a member of H; 2) If sequence {ar,..., ,.). belongs to H. then for all 1 < < k, {a),... .03 is member of H. Here, each member of H is a history and each component of history is an action taken by player. The set of available actions after history is denoted by a(h) = {a (h,a) E H} and the set of terminal histories is denoted by Z.
A function P such that P(h) is the player who takes the action after history h. H' represents the of all h that P(h) =
function e² that is the strategy of the chance player, i.e., oº (h, a) is the probability of action occurs after h if P(h) =C
For each player (besides the chance player), partition I' of H: I$ is information partition of player i; a set Ie a subset of such that if Ju, h2 E I, then player cannot distinguish them.
reward function r" where y" (h, is the distribution of the reward of player i at h Z. We assume the rewards are bounded in 1).
For convenience, let A max, [a(h)] be the maximal size of actions for one history. A strategy o' for player is mapping from H' to the distribution over valid actions. We use o' (h, a) to represent the probability taking action a at E H' and o¹ (h) to be the vector of of (h, a), E a(h). And a strategy profile consists of the strategies of all players in [N] = (1,..., ,N), i.e., a (a") [e))
2

---

Published as a conference paper at ICLR 2020
We use o² to refer to the strategies of all players except i. Since player cannot distinguish h1, h2 E E I', o' (h1) and o d'(h2) must be the same and we denote o' = d'(h)). For the clarity of notation,
d'. Let u ahlo,, d²) denote the expected reward of player i E [N] at history h under strategy a. For convenience, let u'(a ((]dd) = u' (h, la, d²) where hy is the root of H and w' (h(rr" is the expected reward of player for h E Z.
abbreviate (c",r")
To (h((") is the probability of reaching h with a and c². It is easy to see that we can de- compose To (hld") into the product of the contribution of each player. That is, To (h(ld" [ukENj Th (hid")). We use (hh) to refer to the depth of in the game tree and (*(h) to refer to the number of h's ancestors whose player i. Obviously, we have D(h) 1+ LLE+)iENNUEC (h).).
And let D = max, (hh and D = max; D (h)).
With the above notations, then in TEGI there are two-players besides the chance player (i.e., N 2), player and player 2, and u (d((h))) + w² (h/r*) = 0 for all histories / E Z.
Nash Equilibrium and exploitability: In multi-agent system, solution is often referred Nash Equilibrium (NE) (Oshorne & Rubinstem, (194)). In TEGI, = (o'.o²) ) is NE if and only if u' d") max, u'(a"., "1 ). Our target is approximate NE. More specifically, in TEGIs, the approximation error of o (a a²) is usually measured by its exploitability:
expl(a)d")) = max u u' ,02ld") + max ue (o o (1d")
(1)
a+.
If the environment of a TEGL, i.c. d', is known for the players, we can directly use counterfactural regret minimization (CFR) (Zinkevich all, 2008 to minimize the exploitability of this TEGI, as briefly reviewed in Sec. 2.
In this paper, we concentrate the more challenging yet relatively under-explored setting of TEGI, where the environment d' is unknown and moreover d" is subject to some intrinsic uncertainty. For example, poker games with unknown deck fall into this setting. In practice, this setting is not uncommon in industrial organisation with unknown entry, exit and firm-specific sources (Ericson Pakes, 1995). In this setting, players have to interact with the unknown environment gain sufficient knowledge of the game for making optimal decisions. thereby becoming a reinforcement learning (RI) task. particular, the task of finding approximate NEs for TEGIs with unknown d" is a Multi-Agent Reinforcement Learning (MARL) task (Buşoniu et all, 2010).
Moreover, to consider the intrinsic uncertainty of the unknown environment, we adopt a Bayesian formulation for our TEGI task, which can flexibly incorporate the prior information and enjoys various potential benefits (Russo & Van Roy, 2014). Formally, we consider the setting where the chance player and the reward functions follow prior distribution Po. That is, the underlying d' (c", rr) is sampled from ro(c,r). Here e and r are not necessarily independent. After playing t games, players collect some samples from d' (c", r²) and they can get the posterior distribution, denoted as P,. For example, in the case where r" rh( i) is a Bernoulli distribution and its prior is a Beta distribution, the posterior distribution (r(r) is also Beta distribution. Similarly if the prior for e* is a Dirichlet distribution, then (z(c) is Dirichlet distribution since (h) is a multinomial distribution for H².
To solve the above TEGI problems, we present a method that draws inspirations from the solutions for two simplified settings, as briefly reviewed below.
2.2 COUNTERFACTUAL REGRET MINIMIZATION (CFR)
As stated above, when the parameters of the game, i.e. d' = regret minimization (CFR) (Zinkevich et all 2003) provides an effective solution to TEGIs with state-of-the-arr performance. Formally, CFR is a self-play algorithm that generates sequence of strategy profiles, (or)T= by minimizing the following regrets:
(c", (c",,")) are known", counterfactual
T Σ (o.ld))
R max Σ 1
Lu'
In this case, the distribution of d' degenerates single fixed value; therefore no uncertainty d'.
3

---

Published as a conference paper at ICLR 2020
Algorithm 1 CER-PSRL
while < T do
Sample de and de from the posterior Pr..
for all i E {1 do
Select 0, by exploiting CFR minimize the regret: max, Eisr o
Eisr Eigr"'(oyld u'(o)ld))
end for
Calculate interaction strategies o1, and 02,r with Eq.(E.
Use ,1,r and ,2, to interact with the environment to gather data and then compute P end while
Output: 5 Et=
For convenience, we write or + E'= of if (1) Σ. n (1) E. (1,11)
One important observation
(Zikevich et all 2008 is that in a TEGI the exploitability is:
1 expl(orld")) = T [ + 12??))
(2)
Therefore, CFR makes ōT converge to the NE by minimizing 187 and R772
2.3 POSTERIOR SAMPLING FOR REINFORCEMENT LEARNING (PSRL)
Posterior sampling for reinforcement learning (PSRL) (Osband et all 2013) provides an effective method for solving RL problems when the environment has uncertainty. Formally, PSRL applies to the Bayesian RL setting with given prior distribution over the transition and reward function; and the agents access this prior distribution and then update the posterior distribution using the ob- servations collected from interactions with the environment. PSRL provides a framework on how to select the strategy to interact with the environment under the Bayesian setting. The process of PSRL can be decomposed into two steps: (1) sampling one environment from the posterior and computing strategies for agents according to the sampled environment; (2) using the computed strategies to interact with the underlying environment and updating the posterior distribution with the collected data. The two steps are iterated. The strategies that are used to play games are called interaction strategies.
For different kinds of RL problems, the interaction strategies for PSRL are different. For example, PSRL chooses choI.choose the strategy with the maximum expected value as the interaction strategy in the single- agent RL problems (SARL). However, this cannot be trivially extended to MARL since the learning goal turns to be the NE. Hence, in order to apply PSRL to problem of TZEISs, need to design of proper interaction strategies.
METHOD
In this section, we formally present our method, which conjoins the merits of PSRL and CFR and can efficiently compute the approximate NE for TEGI tasks. The key is our design of a proper interaction strategy, which coordinate with CFR interact with the environment.
Before diving into details, we given an overview of our algorithm. We call two games interacted with the environment one episode. In episode f, we sample a de from posterior distribution P. and then apply CFR to d, to get a policy tuple (a. oo). Then sample another d, to calculate the interaction strategics. Then we use the interaction strategies to interact with the environment to collect data and update the posterior. Our algorithm can converge to the NE at a rate of O (())og(T))T)) The time complexity of computing the interaction strategies is linear to H
Here we introduce our method detail. The algorithm presented in Alg The detailed format of the interaction strategy will be given soon in Eq.. (
4

---

Published as a conference paper at ICLR 2020
To compute the approximate NE, we adopt CFR algorithm to minimize the following regret for episode
max Σ Cu'lo',
Σ Eu'(orle (or()))))
EST
where d, is sampled from the posterior distribution at episode t (i.c., Pt).. Then take ō Eigr of as the output strategy for our algorithm. Obviously, simply minimizing Ry will not make the exploitability ezpl dd)) small, as d' can be very different with d, so we need the interac- tion strategy to be efficient enough to make sure the difference between de and d' is relatively small. The following equation establishes relation between the exploitability expl( d²) and regret RA:
expl(o)dd)) T
R
RG
Σ xE(1,2) EST
Σ
u' ,0,1000 -----u'e u' od))
(4)
Here by fixing that the player -i plays the strategy o at episode 6,0 we use oT arg max,: Eigr u' ( (d)) to denote player i's optimal strategy in the underlying game d², and of = arg max,i Eisr w² (o",a, (d,) episode l is de For convenience, let 9 = Ei ",,"",,,llll "o""d"))) - w' (a%, or '(d)) denote the gap between exploitability and the regret from CFR. Intuitively, or generated by CFR with a biased knowledge on the environment. The bias can be described by the term Gj.. As we can minimize Ri by CFR, we only need to minimize Gj in order to minimize expl(old"). Thus, the target of the interaction strategies is to fix the bias, i.e., minimize G
to denote player i's optimal strategy when the game at
The remaining challenge is to design interaction strategies to minimize G7 efficiently. In episode t, we first draw de (e,, Fr) P,. Then for i E {1,2). we compute the strategy that maximizes the cumulative reward gaps between games sampled from the posterior:
. arg max o
Σ ('''o''_oy' oy
u' u''o''o7''da (ol.o)lle)).
(5)
Interaction strategy: We adopt the following interaction strategies for episode T:
Ô1,7 = (
and 02,т (o) o
(6)
The computation of oj can be implemented in time O(H)) To make the whole procedure clear, we use a simple toy game to show the game tree at episode in Fig. II We present d, d, and o The interaction strategy is then calculated from these quantities. It needs to be emphasized that the strategies of and of are generated by CFR in episode t 1 and they are used as the opponents' strategies in the interaction strategies.
With the interaction strategies of) and (af, of), we can prove the following bound on the exploitability expp(())
Theorem 1. Let g¹ Σ v maxxi ΣIET: ( (T). Use Exp represent the expectation
all the prior distribution Pold"). If the true game is sampled from prior P. over the chance player nodes and terminal nodes, then for o. computed by Alg. WI we have
1 (R)
R2)) =0 ( ((5 +
T
0 =0
(7 (VIZTTim((ZTT) + AT
(8)
Eg. erpl(or (d') =0
1
( ( + VI
Here for two-player games, -i denotes the other player not é; for multi-player games, -i generally denotes all players except
5

---

Published as a conference paper at ICLR 2020
h2
G,Ch,, 2;
Ec(h..
a()
celhs.a)) az) af (fs.aa)))
h2
of (12.a22)
of (be.
of (2)
v (hgazldd)
u ('ggadd))
u² (12ag/d0 (d)
x ((tg
ha
iis
4
of (1)1)a))
of
af
(de)
ut (h4aglde) u² (H
al (heas Id:) of (hga,
we (hggggld)) x² (faggldd)
Figure 1: toy game. Here P(h1) = C. h2, ha are the nodes for player 1 and hıg hs are the nodes for player 2. At episode t, dN and d, are sampled from the posterior distribution, as shown as (t, GR, (-1d2) and w (-Id)). Then of and of can be calculated by CFR. Finally we use these parameters on the graph calculate the interaction strategies with Eq. (S)).
Here Ç is game-dependent parameter, related to the structure of the game. Its definition comes from Corrollary in BBrrch (2018). Under some mild assumptions, we have that VIza S 5" [T'
The present theorem significant at least in the following aspects.
Firstly, the per episode running time is linear to the size of game tree and the bound is sublinear to T. Thus, we can expect our algorithm to reach a certain approximate error in a finite time.
Secondly, our theorem holds for any prior distribution over d'. In practical TEGIs, it is possible that the priors for h and h2, h1, E HS, are independent. Our theorem and algorithms can also be applied to such situations.
Lastly, our interaction strategies ,1,т and 02,7 only contribute the bound for G which can be treated as the error for interaction strategy's exploring the environment. If we apply PSRL to single-agent tree game, the Bayesian regret might be considered as some error caused by interacting with the environment. Using the analysis in (Osband at 2013), we can get that PSRL enjoys an averaged Bayesian regret bound of order O ((VlZ) In([Z]T)/ / |HHC D ( for general prior. Therefore, bound for G has comparable order to the bound for the average Bayesian regret single-agent tree games.
3.1 PROOF SKETCH OF THEOREM
Before giving the detailed proof, we introduce some additional notations. For episode f, we generate two trajectories by interacting with the environment. More specifically, denote the trajectory generated by oü in environment d" We use ET., to denote the expectation over all trajectories for episode t. Then we use TG = [ h....... hC m to denote the trajectory for the chance player in episode f, and here m,,; denotes the length of T Furthermore, we denote the terminal node for Tr as 24,,. Besides, we denote the collection of T1.1 T2.1..., T1,--1, T2 and the related rewards H4, which represents all the observations before episode t. For each history h, we further use (h) to denote the count that h has been visited in H.. Further, we use BT,, to denoting the expectation over all possible trajectories T
Tr, {1,2)) to
Below we give the key part for the proof. Obviously, we need to bound the regret of CFR, i.e., ny. and Gt.. We can directly apply the technique in Theorem of (Burch, 2018, pg. 34) B to bound Ri
Theorem 1 in (urch 201N was used to analyze regret with the chance player is fixed in different time steps. But also he used to bound Eq. (X)

---

Published as a conference paper at ICLR 2020
with Eq. (0)) Next show the key part for bounding 9j. Using the definition of o4, we have:
1
Σ
(o''
"d") u (oT' oi or (d:)))
T
SST
1
(u'(o'' 1ST
u' , oz d,))).
max
T
And then, in Lemma 0 and D. we decompose the above bound into the weighted sum of |c* (e(h) and (h) (90)-re -r)),, And soon later we will show how each term decreases as the number of episodes increases.
Lemma 1. At episode T. with defined Eq. (G), we can upper bound the expectation of gi:
Ehr
g HT
}
Rgee
( ( u o6t, (H4e)
T
Σ BH, (B [o) 'd" n' o, _o,,o,,,))))) |do]] M.]. (10) T
1
Lemma decomposes the expectation of Gj. into two terms, representing the reward difference between d' and de and the difference between d' and de Below we give an intuitive sketch for bounding the first term u² (ōj, o, ((d,) - n' o, "d")))
Lemma 2. At episode T, the expectation of u² (o), of (dss)) u' u') "11d) can be bounded by the summation of the difference between d' and de:
(Bz.ar (ot oeoo) u (o), 00 [cr]]]]]]] or(()) |ii
Ex.
SEH,
Σ
|oc(h c² "hh a)l He [
aEa(h)
+ Ex, [E BTA (2,,l - -u' (2L,0) me]
(11)
According to the definition of the expectation Bz ET,. we can see that Eq. (lII is weighted
sum of (c) - ch)l and (h(r)) (h(rr")) Recall that u² (h(rr refers to the expectation of r(h) for player i. Intuitively, large weight, we should visit for more times. Notice that the weight in Eq. (L) is essentially probability of reaching h under our interaction strategy ē and the real environment e*. Hence if we
can use concentration bound on lcx(h) c² (h)], so for h with
use to interact with the environment, we can expect our algorithm can visit with large weight for sufficient times.
To simplify the derivation, we tentatively assume that de and d' are identically distributed for nodes hy, and zi, conditioning on He. That is, for any node h, with Pr referring to the probability of some event, we here assume that
Pr(d" 12, = Pr(d,
fact this assumption fails when reached, because the probability to reach influenced by d' and d. We will remove this assumption and provide a rigorous proof in Appendix AI. For (hf. a) and
Zi,.. we can insert the empirical mean estimations &2 (e 5 a) and (21,e) and use the frequentists' concentration bound (Hoetldmng [994;; Weissman et all 2003)). Then for any d E (0, 1), we have the following inequalities:
21m(24/8)
En, ExgarEE
Σ aEa(hS.))
18)h)r,a)-c c cC a)l
H4
En. PVV
max(mm (N 1) 74
+ 2 88
2 log (2/6)
Exc EEg ETE [ut (M|Fe) - (1//r1)]] [72] s Tazes
2
+ 4|2 He
(nxx)n

---

Published as a conference paper at ICLR 2020
mh(
Then for history h E Z U HC, have Σ ViJis Vnehh). Using the Jensen's inequality to the summation over Z and HC, we can get the following bound:
Σ Eele { Ed (0%, (da) n' (ot, Mll =0 -0VIZ(TinzZ) (
We apply the same method Σ En, (Er,a- [u' of - o, He and get
Eq. H Combining the results of Eq. (77) and (8), we can finish the proof of the theorem M1
4 RELATED WORK
Other methods for TEGIs under unknown environment: There also exist some works on TEGIs under an unknown environment. Fictitious play (FP) (Brown, (95II) is another popular algorithm for approximating NE, In FP, the agent takes the best response to the average strategy of its opponent. Heinrich et all (2155) extend FP TEGIs. Though may be easier combine FP with other machine learning techniques than CFR, when the chance player is known, the convergence rate of FP is usually worse than CFR variants. Monte Carlo CFR with outcome sampling (MCCFR-OK (Lanctor all 2009) can also be applied to TEGIs to approximate NE in model-free style. It uses Monte Carlo estimates of the environment to conduct CFR and can converge to the NE. Since is updated without model of the environment, it is much less efficient than model-based methods. There is also work that applies SARL methods to TEGIs. For example, Sriinvasaan et all (2018) adapts actor-critic games in model-free style.
MDP: SARL problems are often formalized as the Markov Decision Process (MDP). In the sim- plest MDP with transitions, i.e. the Multi-armed bandit problems, the dependent regret upper bound of PSRL. (also named Thompson Sampling in bandit problems) has been carefully an- alyzed (Agrawal & Goyal, 2017). The problen-dependent bounds for general MDP is still open problem. Besides PSRL, there is another kind of provable algorithms for MDP (Jaksch al 2010, Azar all 20T33) following the Optimism in the Face of Uncertainty principle. They estimate the uncertainty of the underlying MDP and then use the currently optimal policy to interact with the environment.
Stochastic Games: the stochastic game (Littman (994) is also one kind of multi-agent systems. In a stochastic game, players take actions at each state and then the environment transits to a new state and returns immediate rewards. Nash Q-learning (Hu & Wellman, 2003) converges to approximate NE by extending Q-learning to games, but it lacks finite-time analysis. Some other work (Szepesvan & Litiman 1996: Perolat etall 20L5; Wei al, ( concentrates on two-player zero-sum stochas- tic games in RL setting. This kind of games don't involve imperfect information, and this makes them different from TEGL.
5 EXPERIMENTS
To empirically evaluate our algorithm, we test it on imperfecttinfooration poker games. In this section, we first introduce our baseline methods and then present the details of the games. Finally, we show the results.
We choose three kinds of methods as our basclines. The first one is Fictitious Play (FP) and the second is Monte Carlo CFR with outcome sampling (MCCFR). Both are algorithms for MARL. Thus we can compare the performance of our algorithm and these existing methods. We choose two variants of our algorithm the other kind of baselines, which is used to compare different choices of interaction strategies. Details of baselines are given below:
Fictitious self-play (FSP): FSP is another popular algorithm to solve games in the RL setting. In FP, when d' is known, each player chooses the best response of its opponent's 's average strategy. When d' is not known, we need other RL algorithms to learn the best response. We combine FSP with two kinds of RL algorithms: 1) FSP with fitted-Q iteration algorithm (FSP-fitte-Q)):
8

---

Published as a conference paper at ICLR 2020
Cards: betm: 4
Cards: 3 betm: 5
Exploitabilty (log 10)
-0.2
Exploitability (log 10)
011
-0.3
FSP-PSAL
FSP-PSAL
-03-
FSP-Fitted-
-0.4
F3P-Fitted ttod-Q
Bestresp
.05
Bestresp
Defaull
Defau
0.7
Naive
Naive
Rando'n
Random
MCCFR-0S
40
2003
1000:
5002
80co 335co 1290o
secco
Rounds
Rounds
(a) Leduc-4
(b) Leduc-5
Figure 2: Results for different algorithms on variants of Leduc-4 and Leduc-5. Here "default" refers to our algorithm CFR-PSRL.
follow (Heinrich et all 2015) to use a Fitted-Q iteration to learn the best response. We use the (20TS); 2) FSP with PSRL (FSP-PSRL): we use combination of FP and PSRL to give new baseline: In episode t, we compute player i's best response under de ~ P,, that is, arg max,, Eree u'(o", (d4).
same hyperparameters as reported in Heinrcc
Monte Carlo CFR with outcome sampling (MCCFR-OS) -OS: MCCFR-OS uses samples of the game tree to conduct CFR. Estimated counterfactual values are used to update the policies and the average polices
converge NE. This method can be applied to TEGIs under the RL setting. We use e-greedy with = 0.1 as the exploration strategy for MCCER-OS in our experiments.
Variants of Alg. II: Though we have proved the convergence of Alg. M with interaction strategy (ō',a-") the proposed method does not necessarily work well in practice.
our experiments, evaluate four interaction strategies: 1) Random: the players take actions randomly; 2) Naive: the players use the output of the CFR procedure, i.e., d,, to interact with the environment; 3) the best response to o, (Bestresp): (ō" a) where o. is the best response to o, under de i.e., a/¹ arg max.+ u (''o a, Idz); ; 4) Default: the interaction strategies in Eq. (i).
We these algorithms on variants of Ledue Hold'em poker (Southey al, 20112) which is widely used in imperfect-informatio game solving. We generate games by keeping the tree structure of the Ledue Hold'en em poker and replacing с and r by randomly generated functions. More specifically, when generating the tree structure, to control the sizes of the generated game tree, we restrict each player not to bid more than
times the big blind. The numbers of histories in the generated games are 9435 and 34776 respectively. The reward function r'hh) is binary distribution. With probability p the value of (h)
and with probability 1- Pp the value The prior (r is uniform [0, 1] distribution over parameter Obviously, r²( (h). Let ed denote the vector in Idd with every element is 1. c(h) is sampled from Dirichlet(e))(NN))
We generate variants for Leduc(4) and Leduc(5) respectively. And on each generated game, each algorithm updates its strategies for 10000 times, and after each update, it interacts with the environ- ment for rounds of games. The result shown Fig. As Fig. shows, the exploitability of naive CFR fails to decrease after 10000 rounds both Leduc(4) and Leduc(5). This might be caused by the lack efficient exploration of the environment. MCCFR-OS and FSP-Fitted-Q have poor performances comparing to other algorithms. This may be caused by the data- nata-inefficiency of model-free methods and the inefficient exploration strategies. Random interaction and FP can grad- ually decrease the exploitability, but algorithm decrease higher speed. Thus the empirical result shows that our algorithm outperforms baselines on the two games.
CONCLUSIONS AND DISCUSSIONS
In this work, we consider the problem of posterior sampling for TEGIs, which a class of multi- agent reinforcement learning problems. By novel design of interaction staregies, we conjoin the

---

Published as a conference paper at ICLR 2020
merits of PSRL and CFR and present provably convergent algorithm for TEGIs. Our algorithm empirically works well.
In the future, there various directions to improve the result. For example, our bound is Bayesian bound describing the expected performance. Considering one sample from the prior, Frequentists' methods such UCBVI (Azar et all, 2003 also give high probability regret bound for SARL of a similar order to PSRL. Further, comparing with the worst-case bound, the problem-dependemt performance much more important. Though it possible that our method has better performance on a specific TEGI than the bound in Theorem II our algorithm is very possibly not the best in the sense of problem-dependens performance.
Another direction is that our method heavily relies on the structure of TEGIs and the solution concept of Nash Equilibrium. Thus, further work is needed extend posterior sampling more complicated multi-agent systems, such as stochastic games (Liftman, (994) and extensive games with more than two players.
Moreover, the generalization for PSRL is another important but challenging future work direction. It worth of a systematic investigation to bridge the gap between the provable tabular RL algorithms and PSRL methods with generalization. Bootstrapping might be one possible direction. Oshhad etal (2016) applies the principle of PSRL to DQN by using bootstrapping. Another possible direc- tion is to adapt more practical Bayesian inference algorithms to RL tasks.
ACKNOWLEGEMENT
This work was supported by the National Key Research and Development Program of China (No. 2017YFA0700904), NSFC Projects (Nos. 61620106010, U19B2034, U1811461), Beijing NSF Project (No. L172037), Beijing Academy of Artificial Intelligence (BAAI), Tsinghua-Huawel Joint Research Program, a grant from Tsinghua Institute for Guo Qiang. Tiangong Institute for Intelli- gent Computing, the JP Morgan Faculty Research Program and the NVIDIA NVAIL Program with GPU/DGX Acceleration.
REFERENCES
Shipra Agrawal and Navin Goyal. Near-optimal regret bounds for thompson sampling. Journal of the ACM (JACM), 64(5):30, 2017.
Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert Kappen. Minimax pac bounds on the sample complexity of reinforcement learning with generative model. Machine learning, 91);: 325-349, 2013.
George W Brown. Iterative solution of games by fictitious play, 1951. Activity Analysis of Produc- fion and Allocation (TC Koopmans, Ed.). pp. 374-376, 1951.
Neil Burch. Time and space: Why imperfect information games are hard. 2018
Lucian Buşomiu, Robert Babuška, and Bart De Schutter. Multi-agent reinforcement learning: An overview. In Innovations in multi-agent systems and applications-I, pp. 183-221. Springer, 2010.
Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. In Advances in neural information processing systems, pp. 2249-2257, 2011.
Richard Ericson and Ariel Pakes. Markov-perfect industry dynamics: A framework for empirical work. The Review of economic studies, 62(1):53-82, 1995.
Johannes Heinrich, Mare Lanctot, and David Silver. Fictitious self-play in extensive-form games. 2015.
In International Conference on Machine Learning, pp.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. In The Collected Works of Wassily Hoeffding, pp. 409-426. Springer, 1994.
Junling Hu and Michael P Wellman. Nash q-learning for seneral-sum stochastic games. Journal of machine learning research, 4(N9v):1039-1066) 2003.
10

---

Published as a conference paper at ICLR 2020
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(AAp):1563 -6000 2010.
Marc Lanctot, Kevin Waugh, Martin Zinkevich, and Michael Bowling. Monte carlo sampling for regret minimization extensive games. In Advances in neural information processing systems, pp. 1078-1086, 2009.
Michael L. Littman. Markov games as framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pp. 157-163. Elsevier, 1994.
Ian Osband and Benjamin Van Roy. Why is posterior sampling better than optimism for reinforce- ment learning? arXiv preprint 167.v00607..02115 2016.
Ian Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. In Advances in Neural Information Processing Systems, pp. 3003-301 2013. 2013
lan Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped don. In Advances in neural information processing systems, pp. 4026-4034, 2016.
Martin Osborne and Ariel Rubinstein. course in game theory. MIT press, 1994.
Julien Perolat, Bruno Scherrer, Bilal Piot, and Olivier Pietquin. Approximate dynamic programming for two-player zero-sum markov games. In International Conference on Machine Learning (ICML. 2015), 2015.
Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 39(4):1221-124; 2014.
Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Osband, Zheng Wen, al. A tutorial on thompson sampling. Foundations and Trends in Machine Learning, 11(1):1-96, 2018.
Finnegan Southey, Michael P Bowling, Bryce Larson, Carmelo Piccione, Neil Burch, Darse Billings, and Chris Rayner. Bayes' bluff: Opponent modelling in poker. arXiv preprint 12Xiv:1207.144 2012.
Sriram Srinivasan, Mare Lanetot, Vinicius Zambaldi, Julien Pérolat, Karl Tuyls, Rémi Munos, and Michael Bowling. Actor-critic policy optimization in partially observable multiagent environ- ments. Advances in Neural Information Processing Systems, pp. 3422-3435, 2018.
Malcolm Strens. A bayesian framework for reinforcement learning. In ICML, volume 2000, pp. 943-950 2000.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Csaba Szepesvári and Michael L Littman. Generalized markov decision processes: Dynamic- programming and reinforcement-leariin algorithss. In Proceedings of International Conference of Machine Learning, volume 96, 1996.
Chen-Yu Yu Wei, Yi-Te Hong, and Chi-Jen Lu. Online reinforcement learning stochastic games. In Advances in Neural Information Processing Systems. pp. 4987-4997, 2017.
Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo Weinberger. In- equalities for the I1 deviation of the empirical distribution. Hewlett-Packenn Labs, Tech. Rep, 2003.
Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret minimization in games with incomplete information. In Advances in neural information processing systems, pp. 1739-1736, 2008
11

---

Published as a conference paper at ICLR 2020
A PROOF FOR THEOREMI]
Let ō + EisT or denote the average strategy tuple to episode T. We can decompose the exploitability at episode T into the CFR regret and an extra exploration term:
1 (R) expl(ō d')
R2
+
(ot' - of(o7.0==1d)) (S(
Σ
T
where Ri. of and of are formally defined as:
RS max
of "dd) - " Eu'(orld)).
IST
1ST
x,
u'(( (o" ,0 ",d))))
0T
arg max
KT
TT arg max Σ u''o', or o ((
Here iřG is the regret from CFR. And OT and of represent the optimal strategies under d' and de respectively, fixing that the its opponent plays the strategy or at episode t.
Recall that d, is sampled from the posterior distribution P.. The proof for this decomposition is given below:
Proof. Inserting a w² u'(oj,, o((d)) for episode have:
Σ uo of Id')
Σ (o or
( d o + u
1ST
1 .ori"o,,f0 (d')) a (o of (()))
Σ (a + R
4
Moreover, with (a,ld; u (d,)d) 0 and the definition of expl, we finish the proof.
By directly applying the result in (Burch. 2018) we can upper bound the CFR regret with
1 (5VVA))
R4 S
where Eº = Ep / /max.: ElEr, T (1) represents the complexity of the game tree.
For convenience, let G (u or ,od) u' (d))) denote the gap between exploitability and the regret from CFR. Since have upper bounded Ri only need to bound Gj. and then we can upper bound the exploitability of the average strategy ō.
Obviously, Gj. represents the difference between d' and d,. Thus we need to design suitable interaction strategy to make sure that Gj is small. Using the definition of o'i, we have
g
<
1
Σ
nu' (a o n (a , (d))))
T
IST
1
<
T
max
(u' " v' (o' 1000007 or (.)))
at
1ST
12

---

Published as a conference paper at ICLR 2020
We select the interaction strategy as follows. First, we draw de ~ Pt. For E {1,2), compute
o = arg max
Σ Psse
Co'lo', of - (0
(12)
And then we use (Ø, o and (oî, o.)) to interact with the environment. Following lemma provides an upper bound on Gt. Then we get below lemma:
Lemma 3. With oj defined in Eq. (I the expectation of Grr can be bounded by:
Efr { (ar-dr {
1 T
Σ EH,, Bad,d [u'(ot, of u² (oi
[(t]] o [e1
Edg (Eardr,d de [u'(o], ut u' 0, [di]] ma].
T
(13)
This lemma decompose G into two terms, which can be bounded with careful analysis of the posterior distribution. We first give the proof for this lemma.
Proof. We have
Hr }
Bitr
Ex dr
max
Σ (o
,00 or - - w'(0' (00',o"((de))
da
T
HT }
Exrr
Fy dr
max at
Σ (u' (dd) - w n'(0", or od()))
T
Ettr
E dy
Σ (u' - u (5)) o.- (dt))
HT
-Bir
Ear
Σ (ut (dd)) uf (ōt, o. |db))
HT
(Erndr
[u' 4 dr) - u' u' (5 |dr)
H|g) }
+ Enr
) HT
Eetr
max Ejr
E( (d)) u' (ō', 'o',0;-00 =di()d))
+ Ehr
E Ed
(o'o (dr) u (o+. ( mm
4 E
E Edr-idr
T
Σ
(/ 1dr-1) u² | | }
Bdddrr v - u' u' or |(r)] [tr)
+ Ehr
Exi (Ea. o - n/ (0) -, |dt) [16]]
EHi
(B (6) n² (o) (0) |(r)) Ht
Σ EH, (Ea,ar.a (1d) - u' (āt o. [dde]] Hel}
Here equality ① holds since d' and dr are identical distributed conditioning on Hg. Equation 2 holds due to the definition of of. Then we get ( with the maximum function. Equality 4 holds
13

---

Published as a conference paper at ICLR 2020
with the definition of 0 Inequality @ holds by using the induction to episode t. Finally get equality ④ by inserting u² (Ø) "d")
Therefore, we finish the proof.
Then we only to give upper bounds for the above two terms. Also mentioned in sec 1. we intro- duce some additional notations. For episode t, generate two trajectories by interacting with the environment. More specifically, we use Ti, (i E (1,2) 2222) to denote the trajectory generated by oz, with d" We ET,, to denote the expectation over all trajectories for episode Then we denote T. (hf,e. e hS,,....,hhm m.. the trajectory for the chance player in episode t, and here mi, denotes the length of T. Furthermore, we denote the terminal node for episode as 2,,t- Besides, we de- note the collection of 11,1 T2.1..,TT..111 T2,11 as Hr, which represents all the observations before
episode t. For each history h, we further use (h) to denote the count that h has been visited in H4. Further, we use T., denoting the expectation over all possible trajectories Ti.
T Then we concentrate on the first term Σ Es,, [B
He and the second term has similar proof. Since the strategy tuple is the same for the utilities, we can decompose their difference with below lemma.
[u'(ot, of " - w (f
Lemma 4. At episode t, the expectation of u' u' o, (dde) u'(oi, of (Td)") can be upper bounded:
(f ((d,) - u' (0 |
EH,
mi,t
|
-EH,
E Eg ET,,
Σ
Σ
(C.( a) c* (hS, a)) (1) of dd)
j=l (h)
+ En,
{E BT,,, (x.(F1)))))) w (2]d)r))] me..
Proof.
From the root node hf,t. players take actions according to (ā), a, Thus should have
{ (ii [u'(ot, (dd)) u' u' o, 1a:1dd% [d'] mi}
En,
=BH,
B BB BT,
u ( or ;d))))))==)))))<) n 00 [Hl
=EH,
E Ed ETI,
Σ
dd)) c¹ (16 (1i, 1ii,elot,00 dt))
He
! DEn.
Enc.
EigddiEn ET.,
Σ
(o c² ( (hf,,l,,, .d) He
+ EM,
E BTa,
Σ
( oi d.) w w' of of
He
En.
E, Er
Σ
(o.(kf,,)))) c (f o; .do) He
aEa(Af,))
+ EH, E2g BT,,
' (1S,elot, d.) u' of d')] mel}
Me.e
EHt Edj ET.
Σ
Σ (o.(hS.., c² (hS. a) a)) (n (1g,, of do) He
aEa(!S.)
Em, { (E Ey., (2., u² (2,))r"]] [12)-
14

---

Published as a conference paper at ICLR 2020
Here equation ! holds by inserting term e² (hS, aaa'a)) (Mf, (hf,lo o, :d): equation ② holds since that f6g, is reached following the underlying transition c* (Af,,; and equation 3 holds by using induction.
Therefore we finish the proof.
We upper bound the term w' (=),)))) - u² (24,)r") first. We refer to the technique of previous work in PSRL. Recall that in episode t, players reaches terminal node 2i, with visited count (z(z),)). We denote that uf (z),) as the empirical mean of u² (z(zelr))) Simply we insert (z(a)) to get
Fo - u' (z),)>")) & (z), - (z,,)) + (2,,) - ul (zaalr").
First we consider the second one | u ( (z),,(r)) and we have similar bound for the first term. Conditioning r" (z,,)), we can apply the Chernoff-Hocffding bound (Hoeftding, (T994). For
E (0,
Pr [a((2))) - (22,a)
ln(2/5)
1r (2((2)))
s 6,
(14)
V max((,(22.))
where Pr denote the probability.
Then we use the above inequality to get below lemma:
Lemma 5. At episode i, the expectation of (2t,e) w/ (2),((=") can be bounded by
Ex, Ea 1T, [((b(Z)))) u' (=,,e1r) H.
2lg(2/88) max((1 1)
SEM,
E BT,
He + 2/
Proof. Notice that Eq. 14 holds conditioning on (z(,)) and the expectation is taken over the prior Fo. Then need to carefully apply the Eq. [4] For the convenience of notation, use n, (hld") to represent -: Tat_=,((hld'", We further use I(()) to indicate the identical function. Then we expand the expectation into integration
Exe
Eg F BT., [1,,)) (2(, He)
1
Σ
u' ((("""))((((())))00000
,es He)
ZEZ
In(2/0)
2 max(14 (1),) Te (=(dd Pr(d", (H..))) H.)
#E2
In(2/5)
+ Σ
[u:(2) - ul (2/r=)) 2
2 maxx(n P((d"(NL))P((H))((( H.) (15)
REZ
2 2l0g(2/0)
E
Exle
HH
max max
In(2/5)
+ Σ
[u((s) - (2/r")) 2
Pr(Au(d")Pu(d""dd H.)
V 2 1))
2EZ
2 l2g(2/0) max(me(22..,))
Ep
H4 2
Here we extend the expectation into integration in equation !. Inequality 2 holds by separating the integral space. Equation 3 uses the Bayes rule and thus apply Eq. (I4) to get equation
④.
Therefore finish the proof.
15

---

Published as a conference paper at ICLR 2020
For another term (2,,(1))))) (2,,)) still apply the technique in Lemma 5 to get below lemma:
Lemma 6. Ar episode t, the expectation of (2s,elFF)) ūi (21,1) can be bounded by
2 log(2/6) max(m)(a.)):
Bhe (d TT. (2a(F)))))) (z(,)) Hef I Bri. Edndd [V
H4 216.
Proof. We can directly prove that
EH,
EE ET.
[ (Z (=,))) [
/
Σ
(s((s))
( H4)
+EZ
In(2/5) ( ,d, H4)
Σ
V
2 maxx(1 (n((),,))
#E
In(2/6) Pr(((H.)PT(HH)d(( Hi) (16)
Σ
211
(u'(s)i))-((((0) [({(s] 2
mmax((n()))
2 (2/()
=EE, Fina
HH [84]
In(2/5)
+ Σ
21
(u'(s)Fe) [r(s)] 2
Pr(He (Pola) H4)
2 mmxx(n; (n))
sEZ
2lg(2 ((ex,)) 1)
<EHH
E Bddr.d
144 2|26.
The above proof almost the same that Lemma Dl expect inequality (IG)), Since d' and de are identically distributed conditioning on He, then we apply below equality to Eq. (IG):
In(2/8)
Ju' (s(Ft) m((s)] Z
Pr(d()H))PP((HH)
2 maxx(n(s))..
In(2/8)
=1l (u((s)r))-((())) x((s)|2
Pr(d")H))PP(HH))
maxx(n:(s).
Then we finish the proof.
Hence combine the results in Lemma El and and get the conclusion that for any 8 E (0, 1),
log(2/8) u² (2,, He < En. Eggaa ( max(n) 1)
EH, "' [ut (2,,
H4
4|216.
Using phgeon-hole principle and choosing 5 = 1/([Z(T), we have below lemma:
Lemma 7. At episode T, the expectation of the summation of u² (zc,eFFe) u² (z(,,elr*) over the prior distribution Py has an order of:
T
EP
Σ
u' (zceliee) u (zi,er))) = -OVIZTT(n(211)
16

---

Published as a conference paper at ICLR 2020
Then consider chance player node h5,1- We also denote e(h5, as the empirical mean of chance player's probability to choose at N Notice that the utility is bounded in [-1,1]. We have
Σ
(Ce(h (.. a) c² (he a))'' (M (1,,, ,
aEa(hS.))
Σ
c* ch a)l
aEa(h).)
Σ
Jit jas a)
E(h a)l +2
Σ
()) - c² (N a)l.
aEa(hS,
aEalh
Then conditioning on c² (" j.2 a). we use the concentration bound for In norm (i.e. the deviation inequality (Weissman et all 2003) to get that for ò E (0.
2 2
Pr
Σ
ch (N),
max(nn((f) (1 <
(EE
Similar to the analysis in r, we give below lemma: Lemma 8. At episode I, the expectation of (o(hS, a) c* (1 (NS,,: can be bounded by
Σ
EHe
Ed ET... [Ia(h c² (1 mr
(ES()
2 2ln(24/5)
SEH,
He
+ +111100.
max no max(n: (h5,),),.
Proof. We use similar techniques to get
En,
E E BTi..
Σ
1a(h -c -c a]l
Σ
1e(k, a) c ((bb,))-(((ho/mm(((())))) (H) Ha)
hEHe
aka(k)
2ln(21/5)
Σ hEHC
max(n)(h), (. H4,
V
2ln(24/8)
Σ
1e(h, a) - c (h, a))
Pr(("1H))PP(()))00 (7,)
mh)(n.(h),1)
hEHC
(h)(())
(17)
21m(24/5)
=EH, Bij..
max(
21n(24/8)
+ Σ hE#e
Σ
16(b, a) -c"(ha))
Pr(HHldd)Po H.)
ma)(
(k)(k)
2 (24/8))))
<EH
E. Br
\ max)))
174
1H
The proof process above is similar to that of Lemma
Once again, get below lemma:
17

---

Published as a conference paper at ICLR 2020
Lemma 9. At episode t, the expectation of (, a) E(h a)) can be bounded by ( ET, [1o(h a) chhS,,,)) [la
Σ aEa(A),)
ER,
( (nax(no((1) (15,)).1) [ } + 111100
2 2nn (ln(21/8)
ITEr
Proof. We use similar techniques to get
()) -) 1 | |
Eii,
ETe,
Σ
aEa(h)..)
Σ
Σ
a) - (H))))))) dd,)
dd, H.)
hEMC
aEa(h)
2 2lm(24/))
max(n:(h),
bEHC
21m(2^18) max(n:(h).1)
jā(h,a) a) E(h,
Pr(@HH))P((H)dddd Hi)
kE#C
(Ea(h)
(18)
21n(24/8) V max((n(())))
=Eni Bignd
H
2 2l(22/0)
(a(h,a) ch,
H.)
(M).))
NEHC
(EE((h)
2 12g(22//0) (8) max (o 1)
<En.
He + 11988
The proof process here is similar to that of Lemma R
Next, we use a pigeon-hole principle and choosing = 1/(HH(TT) we have below lemma:
Lemma 10. At episode T, the expectation of the summution of 1ē (N.,a)))) c² @hh a)) over the prior distribution Po has an order of:
E
ΣΣ
(a( - -h =0I1I1)DDET(I((((()))
eEa(h)
Therefore we use the conclusion in Lemmald and to get
EH, ( ( u u'( ]+] Me = (2V1 ( AT
The similar proof can be applied to the second term to get the same upper bound by simply replacing d, with dei
T
Σ EH, Eij
( He -0VIO///TTII (T((HETT)(()))7
Sum the analysis together, we get the conclusion that
Ehr Es dr [ Hr o(v
Z (
HC D In HC(T)
T
T
18


Reviews:
[{"review_id": "HkxcDKmIFB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Posterior sampling for multi-agent reinforcement learning: solving extensive games with imperfect information\n================================================================\n\n\nThis paper investigates the use of Thompson sampling in multi-agent reinforcement learning.\nThey present a natural extension of the PSRL algorithm paired with counterfactual regret minimization, rather than expected reward maximization.\nThey provide support for this algorithm's efficacy through a theorem that proves polynomial learning rates, together with empirical evaluation where this approach is competitive with state of the art.\n\n\nThere are several things to like about this paper:\n- This paper is definitely \"groundbreaking\" in that it makes a true extension to the existing literature: PSRL has been relatively well-studied in single-agent RL but never (to my knowledge) in the multi-agent setting.\n- The extensions from single agent to multi-agent are natural, but also non-trivial, and it seems like this is a genuinely novel piece of work that can be interesting to both side (exploration and multi-agent).\n- The general structure of the paper and presentation is good.\n- The support from the theorem is great, and also the empirical evaluation is convincing.\n\nThere are a few places where the paper might be improved:\n- It might be helpful to draw the connection to Thompson sampling more explicitly at the start. PSRL is really an application of Thompson sampling principle, but it is important that it doesn't happen every step but instead on a longer timescale. It might be helpful to cite \"a tutorial on thompson sampling\" Russo et al.\n- Do you think there are promising avenues towards PSRL with generalization (rather than tabular)? It feels like actually this should carry over naturally... so maybe you should mention this?\n- I'm not really an expert on the novelty / impressiveness of this algorithm in the multi-agent setting so cannot fully comment on that.\n\n\nOverall I think this is a really interesting paper that should be of interest to the ICLR community.\nI can't say this with full confidence (especially with respect to the multi-agent side) but I do think it's something that probably would add value to the conference!\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "HJg09qHzqS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "PSRL\n------\n\nThis work considers the task of finding a Nash equilibrium in a two-player zero-sum imperfect information game, where some aspects of the game are not known to the agents (specifically, the chance node probabilities, and the reward function). \n\nThe authors propose a method based on PSRL, i.e. at each iteration a set of game parameters are sampled from the posterior of the distribution. Then, CFR is applied in the inner loop; but instead of finding the NE strategy, one player finds the strategy that basically maximizes the reward deviation between two games sampled from the posterior, given that the opponent is playing Nash in the first game.\n\nThe authors prove convergence bounds for their algorithm, and demonstrate its performance on Leduc Hold'em with game parameters randomly chosen from a Dirichlet distribution.\n\n-------------------------\n\nI agree with the authors that standard CFR suffers from the requirement that the full game is known, so it doesn't work well in its standard form when the environment is not known. There *are* other regret minimizers that do work in the model-free setting ([1], [2], [3]), none of which are discussed by the authors.\n\nI also find the proposed setting somewhat unconvincing. The authors are considering a situation where the environment is unknown, but it's not the RL setting because you still must control both (opposing!) agents. Of course, you can't actually find a Nash Equilibrium if you can't control the other player (because they might just never explore part of the game tree). But you would want your algorithm to be a regret minimizer regardless of your partner's strategy. Is this true of the proposed algorithm?\n\nThe proposed interaction strategy described in Eq. 5 and 6 is clever: basically, each player explores a part of the tree that maximizes the difference in payoffs between the two sampled games. This seems a bit inefficient thouggh, why doesn't the agent just find the BR to \\sigma_{-i} under \\tilde{d} given that the opponent plays the NE under d? I don't see why you would want to explore parameters that have a high reward uncertainty if there's a different strategy that does better than the whole confidence interval. It's like UCB: you should play a strategy not with the highest uncertainty, but with the highest optimistic payoff.\n\nI think the work could be substantially improved by comparing against model-free baselines, e.g. fictitious self-play [2], CFR with outcome sampling [1]. The current work deosn't provide any evidence of what benefits the Bayesian approach provides over model-free regret minimization. Especially since the Bayesian approach presumably does not scale as well due to the requirement of maintaining beliefs over all possible games, and the requirement that a correct prior is provided. I would be curious to see Bayesian and model-free appraoches compared in games of different sizes to see how the different methods scale.\n\nNits:\n- such as the private pokers in poker games (private cards)\n- h_1, h_1 \\in H^C, are independent\n- The reference to Neil 2018 should be \"Neil Burch\", not \"Burch Neil\"\n- And if you're going to say \"we can directly apply the technique from [100-page PhD thesis]\", please mention the page number.\n\n\n\n[1] Lanctot, Marc, et al. \"Monte Carlo sampling for regret minimization in extensive games.\" Advances in neural information processing systems. 2009.\n[2] Heinrich, Johannes, Marc Lanctot, and David Silver. \"Fictitious self-play in extensive-form games.\" International Conference on Machine Learning. 2015.\n[3] Srinivasan, Sriram, et al. \"Actor-critic policy optimization in partially observable multiagent environments.\" Advances in Neural Information Processing Systems. 2018.\n\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BkgacWb0cS", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Review for \"Posterior Sampling for Multi-Agent Reinforcement Learning\".\n\nThe paper proposes a sample-efficient way to compute a Nash equilibrium of an extensive form game. The algorithm works by maintaining a probability distribution over the chance player / reward pair (i.e. an environment model).\n\nI give a weak recommendation to accept the paper. Although I haven't checked the proofs in detail, the premise seems to be sound - the authors extend model-based exploration results from MDPs to games. The essence of the argument seems to be that the model of the chance player becomes close to d^\\star quickly enough to get a sub-linear bound.\n\nThe main complaints I have about the paper concern clarity.\n\n1. The paper is very densely written. This isn't necessarily bad, but it makes the paper a bit hard to understand. It would benefit the manuscript greatly to provide a figure which shows how the algorithm works for a small toy game. There is space left in the paper, so even a one-page figure would fit in. The figure should show all the major quantities: d, \\sigma, u.\n\n2. The meaning of the quantity \\mathcal{G}_T^i should be more thoroughly described, given it is important in the proof. \n\n3. You define a game with N players, but the algorithm works with 2.\n\n4. Do you really need all the notations in section 2.1? Why not just define the ones used in the algorithm?\n\n5. Can you discuss how large the constants \\xi can become in practice? The definition of \\xi^i seems to be different on page 10 and in Theorem 1 - please disambiguate.\n\nI ask the authors to add a figure and address the issues above. \n\nI am not an expert in this sub-field so I may have missed aspects of the paper.\n\nMinor points:\n- In Figure 1, please say that \"default\" is your algorithm.\n- \"optimal in the face of uncertainty\" => \"optimism in the face of uncertainty\" ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper extends posterior sampling to the multi-agent RL setting, and develops a novel algorithm with convergence guarantees to a Nash Equilibrium strategy in two-player zero sum games. Reviewers raised several questions, many of which were well addressed by the authors and which helped further clarify the approach and contribution of the paper. The paper is timely in that novel connections between Game Theory and RL are being explored in fruitful ways, and the paper provides valuable new insights and directions for future research.
Decision: Accept (Talk)