Title: POSTERIOR SAMPLING FOR MULTI-AGENT REINFORCE-MENT LEARNING: SOLVING EXTENSIVE GAMES WITH IMPERFECT INFORMATION

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 an 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 largely unexplored. In this work, we extend PSRL to twoplayer zero-sum extensive-games with imperfect information (TEGI), which is a class of multi-agent systems. Technically, we combine PSRL with counterfactual regret minimization (CFR), which is a 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( √ log T /T ). Empirical results show that our algorithm works well.

1. INTRODUCTION:

Reinforcement Learning (RL) (Sutton & Barto, 2018) provides a framework for decision-making problems in an unknown environment, such as robotics control. In an RL 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 strategies. 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 to interact with the environment. PSRL originates from the famous bandit algorithm Thompson Sampling (Russo et al., 2018) , which uses samples from posterior distributions of bandit parameters to calculate current policy. PSRL also maintains a posterior distribution for the underlying environment 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 (Osband et al., 2013) . Theoretical and empirical results (Osband & Van Roy, 2016) both demonstrate that PSRL is one of the near-optimal methods for SARL. Moreover, although PSRL is a Bayesian-style algorithm, empirical evaluation (Chapelle & Li, 2011) and theoretical analysis on the multi-armed bandit problems (Agrawal & Goyal, 2017) suggest that it also enjoys good performance for a problem with fixed parameters.

However, applying PSRL to multi-agent RL (MARL) tasks requires additional design on the interaction 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 relies not only on the environment, but also on 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 to deviate its strategy individually. So we 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 (Osborne & Rubinstein, 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 a 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) is known, counterfactual regret minimization (CFR) (Zinkevich et al., 2008) is the leading algorithm in approximating the NE in a TEGI. However, in the RL setting where the environment is unknown, CFR is not applicable.

In this work, we present a posterior sampling algorithm for TEGIs with the technique of CFR. That is, we apply CFR to the environment sampled from the posterior distribution. Our main contribution is a novel design of interaction strategies for the RL problem of TEGIs. With the proposed strategies, we show that our algorithm can provably converge to an approximate NE at a rate of O( √ log T /T ). 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) (Zinkevich et al., 2008) and posterior sampling for reinforcement learning (PSRL) (Osband et al., 2013) , which inspire our solution.

2.1. PROBLEM FORMULATION OF TEGI:

We start from the definition of general N -player extensive games (See (Osborne & Rubinstein, 1994, pg. 200 ) for a formal definition.), which include TEGI as a nontivial special case when N = 2.

Definition 1 (Extensive game). An extensive game has the following components::

• A finite set of players that includes N agents and a chance player C representing the "Nature" of the game.

• A finite set H of sequences that satisfies: 1) The empty sequence is a member of

H; 2) If a sequence {a 1 , • • • , a k } belongs to H, then for all 1 ≤ l < k, {a 1 , • • • , a l } is a member of H.

Here, each member of H is a history and each component of a history is an action taken by a player. The set of available actions after a history is denoted by α(h) = {a : (h, a) ∈ 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 i represents the set of all h that P (h) = i.

• A function c * that is the strategy of the chance player, i.e., c * (h, a) is the probability of action a occurs after h if P (h) = C.

• For each player i (besides the chance player), a partition I i of H: I i is an information partition of player i; a set I ∈ I i is a subset of H such that if h 1 , h 2 ∈ I, then player i cannot distinguish them.

• A reward function r * where r * (h, i) is the distribution of the reward of player i at h ∈ Z. We assume the rewards are bounded in [-1, 1] .

For convenience, let A = max h |α(h)| be the maximal size of actions for one history. A strategy σ i for player i is a mapping from H i to the distribution over valid actions. We use σ i (h, a) to represent the probability of taking action a at h ∈ H i and σ i (h) to be the vector of σ i (h, a), a ∈ α(h). And a strategy profile σ consists of the strategies of all players in

[N ] := {1, • • • , N }, i.e., σ = {σ i } i∈[N ] .

We use σ -i to refer to the strategies of all players except i. Since player i cannot distinguish h 1 , h 2 ∈ I ∈ I i , σ i (h 1 ) and σ i (h 2 ) must be the same and we denote σ i (I) = σ i (h 1 ). 

(h|d * ) = ∏ i∈[N ]∪{C} π i σ (h|d * ).

We use D(h) to refer to the depth of h in the game tree and D i (h) to refer to the number of h's ancestors whose player is i. Obviously, we have

D(h) = 1 + ∑ i∈{N }∪{C} D i (h). And let D = max h D(h) and D i = max h D i (h).

With the above notations, then in a TEGI there are two-players besides the chance player (i.e., N = 2), player 1 and player 2, and u1 (h|r * ) + u 2 (h|r * ) = 0 for all histories h ∈ Z.

Nash Equilibrium and exploitability: In a multi-agent system, a solution is often referred to a Nash Equilibrium (NE) (Osborne & Rubinstein, 1994) . In a TEGI,

σ = (σ 1 , σ 2 ) is a NE if and only if u i (σ|d * ) = max σ * ,i u i (σ * ,i , σ -i |d * ).

Our target is to approximate NE. More specifically, in TEGIs, the approximation error of σ = (σ 1 , σ 2 ) is usually measured by its exploitability:

EQUATION

If the environment of a TEGI, i.e. d * , is known for the players, we can directly use counterfactural regret minimization (CFR) (Zinkevich et al., 2008) to minimize the exploitability of this TEGI, as briefly reviewed in Sec. 2.2.

In this paper, we concentrate on 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 to gain sufficient knowledge of the game for making optimal decisions, thereby becoming a reinforcement learning (RL) task. In particular, the task of finding approximate NEs for TEGIs with unknown d * is a Multi-Agent Reinforcement Learning (MARL) task (Buşoniu et al., 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 a prior distribution P 0 . That is, the underlying d * = (c * , r * ) is sampled from P 0 (c, r). Here c 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 t . For example, in the case where r * (h, i) is a Bernoulli distribution and its prior is a Beta distribution, the posterior distribution P t (r) is also a Beta distribution. Similarly if the prior for c * is a Dirichlet distribution, then

P t (c) is a Dirichlet distribution since c * (h) is a multinomial distribution for h ∈ H C .

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 * = (c * , r * ), are known 1 , counterfactual regret minimization (CFR) (Zinkevich et al., 2008) provides an effective solution to TEGIs with state-of-the-art performance. Formally, CFR is a self-play algorithm that generates a sequence of strategy profiles, {σ t } T t=1 , by minimizing the following regrets: 

R * ,i T = max σ i T ∑ t=1 u i (σ i , σ -i t |d * ) - T ∑ t=1 u i (σ t |d * ).

max σ i ∑ t≤T u i (σ i , σ -i t |d t ) - ∑ t≤T u i (σ t |d t )

. end for Calculate interaction strategies σ1,T and σ2,T with Eq.( 6). Use σ1,T and σ2,T to interact with the environment to gather data and then compute P t+1 . end while

Output: σ = 1 t ∑ T t=1 σ t .

For convenience, we write σT = 1 (I) . One important observation (Zinkevich et al., 2008) is that in a TEGI the exploitability is:

T ∑ T t=1 σ t if σi T (I) = ∑ t π i σ t (I)σ i t (I) ∑ t π i σ t

EQUATION

)

Therefore, CFR makes σT converge to the NE by minimizing R * ,1 T and R * ,2 T .

2.3. POSTERIOR SAMPLING FOR REINFORCEMENT LEARNING (PSRL):

Posterior sampling for reinforcement learning (PSRL) (Osband et al., 2013) provides an effective method for solving RL problems when the environment has uncertainty. Formally, PSRL applies to the Bayesian RL setting with a given prior distribution over the transition and reward function; and the agents can access this prior distribution and then update the posterior distribution using the observations 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 the strategy with the maximum expected value as the interaction strategy in the singleagent 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 our problem of TZEISs, we need to design of proper interaction strategies.

3. 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 can coordinate with CFR to interact with the environment.

Before diving into details, we given an overview of our algorithm. We call two games interacted with the environment as one episode. In episode t, we sample a d t from posterior distribution P t and then apply CFR to d t to get a policy tuple (σ 1 t , σ 2 t ). Then we sample another dt to calculate the interaction strategies. 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( √ log(T )/T ). The time complexity of computing the interaction strategies is linear to |H|.

Here we introduce our method in detail. The algorithm is presented in Alg.1. The detailed format of the interaction strategy will be given soon in Eq. ( 6).

To compute the approximate NE, we adopt a CFR algorithm to minimize the following regret for episode T :

EQUATION

where d t is sampled from the posterior distribution at episode t (i.e., P t ). Then we take σ = 1 T ∑ t≤T σ t as the output strategy for our algorithm. Obviously, simply minimizing RT will not make the exploitability expl(σ|d * ) small, as d * can be very different with d t , so we need the interaction strategy to be efficient enough to make sure the difference between d t and d * is relatively small. The following equation establishes a relation between the exploitability expl(σ|d * ) and regret Ri T :

EQUATION

)

Here by fixing that the player -i plays the strategy σ -i t at episode t,2 we use σ * ,i

T = arg max σ i ∑ t≤T u i (σ i , σ -i t |d * )

to denote player i's optimal strategy in the underlying game d * , and

σ ′i T = arg max σ i ∑ t≤T u i (σ i , σ -i t |d t )

to denote player i's optimal strategy when the game at episode t is d t . For convenience, let

G i T = 1 T ∑ t≤T (u i (σ * ,i T , σ -i t |d * ) -u i (σ ′i T , σ -i t |d t )

) denote the gap between exploitability and the regret from CFR. Intuitively, σ t is generated by CFR with a biased knowledge on the environment. The bias can be described by the term G i T . As we can minimize Ri

T by CFR, we only need to minimize G i T in order to minimize expl(σ|d * ). Thus, the target of the interaction strategies is to fix the bias, i.e., minimize G i T . The remaining challenge is to design interaction strategies to minimize G i T efficiently. In episode t, we first draw dt = (c t , rt ) ∼ P t . Then for i ∈ {1, 2}, we compute the strategy that maximizes the cumulative reward gaps between games sampled from the posterior:

σi t = arg max σ i t ∑ t ′ =1 ( u i (σ i , σ -i t ′ | dt ) -u i (σ i , σ -i t ′ |d t ′ )

) .

(5)

Interaction strategy: We adopt the following interaction strategies for episode T :

EQUATION

The computation of σi t 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 t in Fig. 1 . We present d t , dt and σ t . The interaction strategy is then calculated from these quantities. It needs to be emphasized that the strategies σ 1 t and σ 2 t are generated by CFR in episode t -1 and they are used as the opponents' strategies in the interaction strategies.

With the interaction strategies (σ 1 T , σ 2 T ) and (σ 1 T , σ2 T ), we can prove the following bound on the exploitability expl(σ).

Theorem 1. Let ξ i = ∑ D j=1 √ max σ i ∑ I∈I i ,D(I)=j π i σ i (I)

. Use E d * to represent the expectation over all the prior distribution P 0 (d * ). If the true game is sampled from a prior P 0 over the chance player nodes and terminal nodes, then for σT computed by Alg. 1, we have

EQUATION

)

EQUATION

)

E d * expl(σ T |d * ) =O ( 1 T ( (ξ 1 + ξ 2 ) √ AT + √ |Z|T ln(|Z|T ) + √ |H C |D C AT ln(|H C |T )

)) .

(9)

Figure 1 : A toy game. Here P (h 1 ) = C, h 2 , h 3 are the nodes for player 1 and h 4 , h 5 are the nodes for player 2. At episode t, d t and dt are sampled from the posterior distribution, as shown as c t , ct , u 1 (•|d t ) and u 1 (•| dt ). Then σ 1 t and σ 2 t can be calculated by CFR. Finally we use these parameters on the graph to calculate the interaction strategies with Eq. ( 5).

Here ξ i is a game-dependent parameter, related to the structure of the game. Its definition comes from Corrollary 2 in Burch (2018) . Under some mild assumptions, we have that

√ |I i | ≤ ξ i ≤ |I i |.

The present theorem is 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 1 and h 2 , h 1 , h 2 ∈ H C , are independent. Our theorem and algorithms can also be applied to such situations.

Lastly, our interaction strategies σ1,T and σ2,T only contribute to the bound for G i T , which can be treated as the error for interaction strategy's exploring the environment. If we apply PSRL to a single-agent tree game, the Bayesian regret might be considered as some error caused by interacting with the environment. Using the analysis in (Osband et al., 2013) , we can get that PSRL enjoys an averaged Bayesian regret bound of order O(

√ |Z| ln(|Z|T )/T + √ |H C |D C A ln(|H C |T )/T

) for a general prior. Therefore, our bound for G i T has a comparable order to the bound for the average Bayesian regret in single-agent tree games.

3.1. PROOF SKETCH OF THEOREM 1:

Before giving the detailed proof, we introduce some additional notations. For episode t, we generate two trajectories by interacting with the environment. More specifically, we use T i,t (i ∈ {1, 2}) to denote the trajectory generated by σi,t in environment d * . We use E Ti,t to denote the expectation over all trajectories for episode t. Then we use

T C i,t = {h C 1,t , h C 2,t , ..., h C mi,t,t

} to denote the trajectory for the chance player in episode t, and here m i,t denotes the length of T C i,t . Furthermore, we denote the terminal node for T i,t as z i,t . Besides, we denote the collection of T 1,1 , T 2,1 ..., T 1,t-1 , T 2,t-1 and the related rewards as H t , which represents all the observations before episode t. For each history h, we further use n t (h) to denote the count that h has been visited in H t . Further, we use E Ti,t to denoting the expectation over all possible trajectories T i,t .

Below we give the key part for the proof. Obviously, we need to bound the regret of CFR, i.e., Ri T , and G i T . We can directly apply the technique in Theorem 1 of (Burch, 2018, pg. 34) 3 to bound Ri T with Eq. ( 7). Next we show the key part for bounding G i T . Using the definition of σ ′i T , we have:

G i T ≤ 1 T ∑ t≤T (u i (σ * ,i T , σ -i t |d * ) -u i (σ * ,i T , σ -i t |d t ))) ≤ 1 T max σ i ∑ t≤T (u i (σ i , σ -i t |d * ) -u i (σ i , σ -i t |d t ))).

And then, in Lemma 1 and 2, we decompose the above bound into the weighted sum of |c * (h)c t (h)| and |r * (h) -r t (h)|. And soon later we will show how each term decreases as the number of episodes increases. Lemma 1. At episode T , with σ defined in Eq. ( 6), we can upper bound the expectation of G i T :

EQUATION

)

Lemma 1 decomposes the expectation of G i T into two terms, representing the reward difference between d * and dt and the difference between d * and d t . Below we give an intuitive sketch for bounding the first term

u i (σ i t , σ -i t | dt ) -u i (σ i t , σ -i t |d * ). Lemma 2. At episode T , the expectation of u i (σ i t , σ -i t | dt ) -u i (σ i t , σ -i t |d *

) can be bounded by the summation of the difference between d * and dt :

EQUATION

)

According to the definition of the expectation E d,d * E Ti,t , we can see that Eq. ( 11) is a weighted sum of |c t (h) -c * (h)| and |u i (h|r t ) -u i (h|r * )|. Recall that u i (h|r) refers to the expectation of r(h) for player i. Intuitively, we can use concentration bound on |c t (h) -c * (h)|, so for h with a large weight, we should visit it for more times. Notice that the weight in Eq. ( 11) is essentially the probability of reaching h under our interaction strategy σ and the real environment c * . Hence if we use σ to interact with the environment, we can expect our algorithm can visit h with large weight for sufficient times.

To simplify the derivation, we tentatively assume that dt and d * are identically distributed for nodes h C j,i and z i,t conditioning on H t . That is, for any node h, with P r referring to the probability of some event, we here assume that

P r(d * |H t , h) = P r( dt |H t , h).

In fact this assumption fails when h is reached, because the probability to reach h is influenced by d * and d. We will remove this assumption and provide a rigorous proof in Appendix A. For (h C j,i , a) and z i,t , we can insert the empirical mean estimations ct (h C j,i , a) and ūi t (z i,t ) and use the frequentists' concentration bound (Hoeffding, 1994; Weissman et al., 2003) . Then for any δ ∈ (0, 1), we have the following inequalities:

E Ht    E dt,d * E Ti,t   ∑ a∈α(h C j,t ) |c(h C j,t , a) -c * (h C j,t , a)|   H t    ≤ E Ht [ 2 √ 2 ln(2 A /δ) max(n t (h C j,t ), 1) H t ] + 2|H C |δ, E Ht { E dt,d * E Ti,t [ u i (h|r t ) -u i (h|r * ) ] H t } ≤ E Ht [ 2 √ 2 log(2/δ) max(n t (z i,t ), 1) H t ] + 4|Z|δ.

Published as a conference paper at ICLR 2020 Then for a history h ∈ Z ∪ H C , we have

nt(h) ∑ n=i √ 1/i ≤ √ n t (h).

Using the Jensen's inequality to the summation over Z and H C , we can get the following bound:

T ∑ t=1 E Ht { E dt,d * [ u i (σ i t , σ -i t | dt ) -u i (σ i t , σ -i t |d * ) ] H t } = O ( √ |Z|T ln(|Z|T ) + √ |H C |D C AT ln(|H C |T )

) .

We can apply the same method to

T ∑ t=1 E Ht { E dt,d * [ u i (σ i t , σ -i t |d * ) -u i (σ i t , σ -i t |d t ) ] H t } and get

Eq. ( 8). Combining the results of Eq. ( 7) and ( 8), we can finish the proof of the theorem 1.

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, 1951) is another popular algorithm for approximating NE. In FP, the agent takes the best response to the average strategy of its opponent. Heinrich et al. (2015) extend FP to TEGIs. Though it may be easier to 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-OS) (Lanctot et al., 2009) can also be applied to TEGIs to approximate NE in a model-free style. It uses Monte Carlo estimates of the environment to conduct CFR and can converge to the NE. Since it is updated without a 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, Srinivasan et al. (2018) adapts actor-critic to games in a model-free style.

MDP: SARL problems are often formalized as the Markov Decision Process (MDP). In the simplest MDP with no transitions, i.e. the Multi-armed bandit problems, the problem-dependent regret upper bound of PSRL (also named Thompson Sampling in bandit problems) has been carefully analyzed (Agrawal & Goyal, 2017) . The problem-dependent bounds for general MDP is still an open problem. Besides PSRL, there is another kind of provable algorithms for MDP (Jaksch et al., 2010; Azar et al., 2013) 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, 1994) 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 (Szepesvári & Littman, 1996; Perolat et al., 2015; Wei et al., 2017) concentrates on two-player zero-sum stochastic games in RL setting. This kind of games don't involve imperfect information, and this makes them different from TEGI.

5. EXPERIMENTS:

To empirically evaluate our algorithm, we test it on imperfect-information 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 baselines. 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 as 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 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 a fitted-Q iteration algorithm (FSP-fitted-Q): we follow (Heinrich et al., 2015) to use a Fitted-Q iteration to learn the best response. We use the same hyperparameters as reported in Heinrich et al. (2015) ; 2) FSP with PSRL (FSP-PSRL): we use a combination of FP and PSRL to give a new baseline: In episode t, we compute player i's best response under

d t ∼ P t , that is, arg max σ i ∑ t ′ <t u i (σ i , σ -i t ′ |d t ).

• Monte Carlo CFR with outcome sampling (MCCFR-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 can converge to NE. This method can be applied to TEGIs under the RL setting.

We use ϵ-greedy with ϵ = 0.1 as the exploration strategy for MCCFR-OS in our experiments.

• Variants of Alg. 1: Though we have proved the convergence of Alg. 1 with interaction strategy (σ i , σ -i ), the proposed method does not necessarily work well in practice. In our experiments, we evaluate four interaction strategies: 1) Random: the players take actions randomly; 2) Naive: the players use the output of the CFR procedure, i.e., σ t , to interact with the environment; 3) the best response to σ -i t (Bestresp): (σ ′i t , σ -i t ) where σ′i t is the best response to σ -i t under dt i.e., σ′i t = arg max σ i u i (σ i , σ -i t | dt ); 4) Default: the interaction strategies in Eq. ( 6).

We test these algorithms on variants of Leduc Hold'em poker (Southey et al., 2012) which is widely used in imperfect-information game solving. We generate games by keeping the tree structure of the Leduc Hold'em poker and replacing c 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 4 or 5 times the big blind. The numbers of histories in the generated games are 9435 and 34776 respectively. The reward function r i (h) is a binary distribution. With a probability p the value of r 1 (h) is -1 and with probability 1 -p, the value is 1. The prior

P 0 (r 1 (h)) is a uniform [0, 1] distribution over parameter p. Obviously, r 2 (h) = -r 1 (h). Let e d denote the vector in R d with every element is 1. c(h) is sampled from Dirichlet(e |A(h)| ).

We generate 20 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 environment for 2 rounds of games. The result is shown in Fig. 2 . As Fig. 2 shows, the exploitability of naive CFR fails to decrease after 10000 rounds on both Leduc(4) and Leduc(5). This might be caused by the lack of 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-inefficiency of model-free methods and the inefficient exploration strategies. Random interaction and FP can gradually decrease the exploitability, but our algorithm decrease at a higher speed. Thus the empirical result shows that our algorithm outperforms baselines on the two games.

6. CONCLUSIONS AND DISCUSSIONS:

In this work, we consider the problem of posterior sampling for TEGIs, which is a class of multiagent reinforcement learning problems. By a novel design of interaction staregies, we conjoin the merits of PSRL and CFR and present a provably convergent algorithm for TEGIs. Our algorithm empirically works well.

In the future, there are various directions to improve the result. For example, our bound is a Bayesian bound describing the expected performance. Considering one sample from the prior, Frequentists' methods such as UCBVI (Azar et al., 2013 ) also give a high probability regret bound for SARL of a similar order to PSRL. Further, comparing with the worst-case bound, the problem-dependent performance is much more important. Though it is possible that our method has a better performance on a specific TEGI than the bound in Theorem 1, our algorithm is very possibly not the best in the sense of problem-dependent 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 to extend posterior sampling to more complicated multi-agent systems, such as stochastic games (Littman, 1994) and extensive games with more than two players.

Moreover, the generalization for PSRL is another important but challenging future work direction. It is 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. Osband et al. (2016) applies the principle of PSRL to DQN by using bootstrapping. Another possible direction is to adapt more practical Bayesian inference algorithms to RL tasks.

A PROOF FOR THEOREM1:

Let σ = 1 T ∑ t≤T σ t denote the average strategy tuple up to episode T . We can decompose the exploitability at episode T into the CFR regret and an extra exploration term:

expl(σ|d * ) = 1 T ( R1 T + R2 T + ∑ i∈{1,2} ∑ t≤T (u i (σ * ,i T , σ -i t |d * ) -u i (σ ′i T , σ -i t |d t ))),

where Ri T , σ * ,i T and σ ′i T are formally defined as:

Ri T = max σ i ∑ t≤T u i (σ i , σ -i t |d t ) - ∑ t≤T u i (σ t |d t ), σ * ,i T = arg max σ i ∑ t≤T u i (σ i , σ -i t |d * ), σ ′i T = arg max σ i T ∑ t=1 u i (σ i , σ -i t |d t ).

Here Ri T is the regret from CFR. And σ * ,i T and σ ′i T represent the optimal strategies under d * and d t respectively, fixing that the its opponent plays the strategy σ -i t at episode t. Recall that d t is sampled from the posterior distribution P t . The proof for this decomposition is given below:

Proof. Inserting a term u i (σ ′i T , σ -i t |d t ) for episode t, we have:

∑ t≤T u i (σ * ,i T , σ -i t |d * ) = ∑ t≤T (u i (σ * ,i T , σ -i t |d * ) -u i (σ ′i T , σ -i t |d t ) + u i (σ ′i T , σ -i t |d t )) = ∑ i,t (u i (σ * ,i T , σ -i t |d * ) -u i (σ ′i T , σ -i t |d t )) + ∑ t≤T u i (σ t |d t ) + Ri T Moreover, with u 1 (σ t |d t ) + u 2 (σ t |d t ) = 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

Ri T ≤ 1 T ( ξ i √ AT ) ,

where

ξ i = ∑ D j=1 √ max σ i ∑ I∈I i ,D(I)=j π i σ i (I)

represents the complexity of the game tree.

For convenience, let

G i T = 1 T ∑ t≤T (u i (σ * ,i T , σ -i t |d * ) -u i (σ ′i T , σ -i t |d t )

) denote the gap between exploitability and the regret from CFR. Since we have upper bounded Ri T , we only need to bound G i T and then we can upper bound the exploitability of the average strategy σ. Obviously, G i T represents the difference between d * and d t . Thus we need to design a suitable interaction strategy to make sure that G i T is small. Using the definition of σ ′i T , we have

G i T ≤ 1 T ∑ t≤T (u i (σ * ,i T , σ -i t |d * ) -u i (σ * ,i T , σ -i t |d t ))) ≤ 1 T max σ i ∑ t≤T (u i (σ i , σ -i t |d * ) -u i (σ i , σ -i t |d t ))).

We select the interaction strategy as follows. First, we draw dt ∼ P t . For i ∈ {1, 2}, we compute

EQUATION

And then we use (σ 1 t , σ 2 t ) and (σ 2 t , σ 1 t ) to interact with the environment. Following lemma provides an upper bound on G i t . Then we get below lemma: Lemma 3. With σi t defined in Eq. ( 12), the expectation of G i T can be bounded by:

EQUATION

)

This lemma decompose G i T 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

E H T { E d * ,d T [ max σi ( T ∑ t=1 (u i (σ i , σ -i t |d * ) -u i (σ i , σ -i t |d t ))

)]

H T } 1 ⃝ = E H T { E dT ,d T [ max σi ( T ∑ t=1 (u i (σ i , σ -i t | dT ) -u i (σ i , σ -i t |d t ))

)]

H T } 2 ⃝ = E H T { E dT ,d T [ T ∑ t=1 (u i (σ i T , σ -i t | dT ) -u i (σ i T , σ -i t |d t )) ] H T } =E H T { E dT [ T -1 ∑ t=1 (u i (σ i T , σ -i t | dT ) -u i (σ i T , σ -i t |d t ))

]

H T } + E H T { E dT ,d T [ u i (σ i T , σ -i T | dT ) -u i (σ i T , σ -i T |d T ) ] H T } 3 ⃝ ≤ E H T { E dT [ max σi ( T -1 ∑ t=1 (u i (σ i , σ -i t | dT ) -u i (σ i , σ -i t |d t ))

)]

H T } + E H T { E dT ,d T [ u i (σ i T , σ -i T | dT ) -u i (σ i T , σ -i T |d T ) ] H T } 4 ⃝ = E H T -1 { E dT -1 ,d T -1 [ T -1 ∑ t=1 (u i (σ i T -1 , σ -i t | dT -1 ) -u i (σ i T -1 , σ -i t |d t )) ] H T -1 } + E H T { E dT ,d T [ u i (σ i T , σ -i T | dT ) -u i (σ i T , σ -i t |d T ) ] H T } 5 ⃝ ≤ T ∑ t=1 E Ht { E dt,dt [ u i (σ i t , σ -i t | dt ) -u i (σ i t , σ -i t |d t ) ] H t } 6 ⃝ = T ∑ t=1 E Ht { E dt,d * [ u i (σ i t , σ -i t | dt ) -u i (σ i t , σ -i t |d * ) ] H t } + T ∑ t=1 E Ht { E dt,d * ,dt [ u i (σ i t , σ -i t |d * ) -u i (σ i t , σ -i t |d t ) ] H t } .

Here equality 1 ⃝ holds since d * and dT are identical distributed conditioning on H t . Equation 2⃝ holds due to the definition of σi T . Then we get 3 ⃝ with the maximum function. Equality 4 ⃝ holds with the definition of σi T -1 . Inequality 5 ⃝ holds by using the induction to episode t. Finally we get equality 6 ⃝ by inserting u i (σ i t , σ -i t |d * ). Therefore, we finish the proof.

Then we only to give upper bounds for the above two terms. Also mentioned in sec.3.1, we introduce some additional notations. For episode t, we generate two trajectories by interacting with the environment. More specifically, we use T i,t (i ∈ {1, 2}) to denote the trajectory generated by σi,t with d * . We use E Ti,t to denote the expectation over all trajectories for episode t. Then we denote T C i,t = {h C 1,t , h C 2,t , ..., h C mi,t,t } the trajectory for the chance player in episode t, and here m i,t denotes the length of T C i,t . Furthermore, we denote the terminal node for episode t as z i,t . Besides, we denote the collection of T 1,1 , T 2,1 ..., T 1,t-1 , T 2,t-1 as H t , which represents all the observations before episode t. For each history h, we further use n t (h) to denote the count that h has been visited in H t . Further, we use E Ti,t to denoting the expectation over all possible trajectories T i,t .

Then we concentrate on the first term

T ∑ t=1 E Ht { E dt,d * [ u i (σ i t , σ -i t | dt ) -u i (σ i t , σ -i t |d * ) ] H t } and

the second term has similar proof. Since the strategy tuple is the same for the two utilities, we can decompose their difference with below lemma.

Lemma 4. At episode t, the expectation of

u i (σ i t , σ -i t | dt ) -u i (σ i t , σ -i t |d *

) can be upper bounded:

E Ht { E dt,d * [ u i (σ i t , σ -i t | dt ) -u i (σ i t , σ -i t |d * ) ] H t } =E Ht    E dt,d * E Ti,t   mi,t ∑ j=1 ∑ a∈α(h) (c t (h C j,t , a) -c * (h C j,t , a))u i (h C j,t |σ i t , σ -i t , dt )   H t    + E Ht { E dt,d * E Ti,t [ u i (z i,t |r t ) -u i (z i,t |r * ) ] H t } .

Proof. From the root node to h C 1,t , players take actions according to (σ i t , σ -i t ). Thus we should have

E Ht { E dt,d * [ u i (σ i t , σ -i t | dt ) -u i (σ i t , σ -i t |d * ) ] H t } =E Ht { E dt,d * E Ti,t [ u i (h C 1,t |σ i t , σ -i t , dt ) -u i (h C 1,t |σ i t , σ -i t , d * ) ] H t } =E Ht    E dt,d * E Ti,t   ∑ a∈α(h C 1,t ) (c t (h C 1,t , a)u i (h C 1,t |σ i t , σ -i t , dt ) -c * (h C 1,t , a)u i (h C 1,t |σ i t , σ -i t , d * ))   H t    1 ⃝ = E Ht    E dt,d * E Ti,t   ∑ a∈α(h C 1,t ) (c t (h C 1,t , a) -c * (h C 1,t , a))u i (h C 1,t |σ i t , σ -i t , dt )   H t    + E Ht    E dt,d * E Ti,t   ∑ a∈α(h C 1,t ) c * (h C 1,t , a)(u i (h C 1,t |σ i t , σ -i t , dt ) -u i (h C 1,t |σ i t , σ -i t , d * ))   H t    2 ⃝ = E Ht    E dt,d * E Ti,t   ∑ a∈α(h C 1,t ) (c t (h C 1,t , a) -c * (h C 1,t , a))u i (h C 1,t |σ i t , σ -i t , dt )   H t    + E Ht { E dt,d * E Ti,t [ u i (h C 2,t |σ i t , σ -i t , dt ) -u i (h C 2,t |σ i t , σ -i t , d * ) ] H t } 3 ⃝ = E Ht    E dt,d * E Ti,t   mi,t ∑ j=1 ∑ a∈α(h C j,t ) (c t (h C j,t , a) -c * (h C j,t , a))u i (h C j,t |σ i t , σ -i t , dt )   H t    + E Ht { E dt,d * E Ti,t [ u i (z i,t |r t ) -u i (z i,t |r * ) ] H t } .

Here (Hoeffding, 1994) . For δ ∈ (0, 1) P r

EQUATION

)

where P r denote the probability.

Then we use the above inequality to get below lemma: Lemma 5. At episode t, the expectation of

|ū i t (z i,t ) -u i (z i,t |r * )| can be bounded by E Ht { E dt,d * E Ti,t [ |ū i t (z i,t ) -u i (z i,t |r * )| ] H t } ≤E Ht { E dt,d * E Ti,t [√ 2 log(2/δ) max(n t (z i,t ), 1) ] H t } + 2|Z|δ.

Proof. Notice that Eq. 14 holds conditioning on r * (z i,t ) and the expectation is taken over the prior P 0 . Then we need to carefully apply the Eq. 14. For the convenience of notation, we use π t (h|d * ) to represent π σi t ,σ -i t (h|d * ). We further use I(•) to indicate the identical function. Then we expand the expectation into integration

E Ht { E dt,d * E Ti,t [ |ū i t (z i,t ) -u i (z i,t |r * )| ] H t } 1 ⃝ = ∑ z∈Z ∫ |ū i t (z) -u i (z|r * )|π t (z|d * )P r(d * , d t |H t )P r(H t )d(d * , d t , H t ) 2 ⃝ ≤ ∑ z∈Z ∫ √ ln(2/δ) 2 max(n t (z), 1) π t (z|d * )P r(d * , d t |H t )P r(H t )d(d * , d t , H t ) + ∑ z∈Z ∫ 2I ( |ū i t (z) -u i (z|r * )| ≥ √ ln(2/δ) 2 max(n t (z), 1) ) P r(d * |H t )P r(H t )d(d * , H t ) (15) 3 ⃝ = E Ht { E dt,d * [√ 2 log(2/δ) max(n t (z i,t ), 1) ] H t } + ∑ z∈Z ∫ 2I ( |ū i t (z) -u i (z|r * )| ≥ √ ln(2/δ) 2 max(n t (z), 1) ) P r(H t |d * )P 0 (d * )d(d * , H t ) 4 ⃝ ≤ E Ht { E dt,d * [√ 2 log(2/δ) max(n t (z i,t ), 1) ] H t } + 2|Z|δ.

Here we extend the expectation into integration in equation 1 ⃝. Inequality 2 ⃝ holds by separating the integral space. Equation 3⃝ uses the Bayes rule and thus we can apply Eq. ( 14) to get equation 4 ⃝.

Therefore we finish the proof. 

) P r( d|H t )P r(H t )d(d * , H t ) (16) =E Ht { E dt,d * [√ 2 log(2/δ) max(n t (z i,t ), 1) ] H t } + ∑ s∈Z ∫ 2I ( |u i (s|r t ) -ūi t (s)| ≥ √ ln(2/δ) 2 max(n t (s), 1) ) P r(H t |d * )P 0 (d * )d(d * , H t ) ≤E Ht { E dt,d * [√ 2 log(2/δ) max(n t (z i,t ), 1) ] H t } + 2|Z|δ.

The above proof is almost the same as that in Lemma 5 expect inequality (16). Since d * and dt are identically distributed conditioning on H t , then we apply below equality to Eq. ( 16):

I ( |u i (s|r t ) -ūi t (s)| ≥ √ ln(2/δ) 2 max(n t (s), 1) ) P r( dt |H t )P r(H t ) =I ( |u i (s|r * ) -ūi t (s)| ≥ √ ln(2/δ) 2 max(n t (s), 1) ) P r(d * |H t )P r(H t ).

Then we finish the proof.

Hence we combine the results in Lemma 5 and 6 and get the conclusion that for any δ ∈ (0, 1),

E Ht { E dt,d * E Ti,t [ u i (z i,t |r t ) -u i (z i,t |r * ) ] H t } ≤ E Ht { E dt,d * [ 2 √ 2 log(2/δ) max(n t (z i,t ), 1) ] H t } + 4|Z|δ.

Using a pigeon-hole principle and choosing δ = 1/(|Z|T ), we have below lemma: Lemma 7. At episode T , the expectation of the summation of u i (z i,t |r t ) -u i (z i,t |r * ) over the prior distribution P 0 has an order of:

E P0 [ T ∑ t=1 u i (z i,t |r t ) -u i (z i,t |r * ) ] = O( √ |Z|T ln(|Z|T )).

Then we consider chance player node h C j,t . We also denote c(h Then conditioning on c * (h C j,t , a), we use the concentration bound for L 1 norm (i.e. the deviation inequality (Weissman et al., 2003) 

] H t } + |H C |δ.

The proof process here is similar to that of Lemma 6.

Next, we use a pigeon-hole principle and choosing δ = 1/(|H C |T ), we have below lemma: Lemma 10. At episode T , the expectation of the summation of |c t (h C j,t , a) -c * (h C j,t , a)| over the prior distribution P 0 has an order of:

E P0   T ∑ t=1 mi,t ∑ j=1 ∑ a∈α(h) |c t (h C j,t , a) -c * (h C j,t , a)|   = O( √ |H C |D C AT ln(|H C |T )).

Therefore we use the conclusion in Lemma7 and 10 to get Sum the analysis together, we get to the conclusion that

E H T { E d * ,d T [ G i T H T ]} = O( √ |Z| ln(|Z|T ) T + √ |H C |D C A ln(|H C |T ) T )

:

In this case, the distribution of d * degenerates to a single fixed value; therefore no uncertainty on d * .

Here for two-player games, -i denotes the other player not i; for multi-player games, -i generally denotes all players except i.

Theorem 1 in(Burch, 2018) was used to analyze regret with the chance player is fixed in different time steps. But it can also be used to bound Eq. (7)

Figures and Tables:

Figure 2: Results for different algorithms on variants of Leduc-4 and Leduc-5. Here "default" refers to our algorithm CFR-PSRL.

For the clarity of notation, we abbreviate (c

Table content: <table/>

Algorithm 1 CFR-PSRL while t < T do Sample d t and dt from the posterior P t . for all i ∈ {1, 2} do Select σ t by exploiting CFR to minimize the regret:

Table content: <table/>

We upper bound the term u i (z i,t |r t ) -u i (z i,t |r * ) first. We can refer to the technique of previous work in PSRL. Recall that in episode t, players reaches terminal node z i,t with a visited count n t (z i,t ). We denote that ūi t (z i,t ) as the empirical mean of u i (z i,t |r * ). Simply we insert ūi t (z i,t ) to get u i (z i,t |r t ) -u i (z i,t |r * ) ≤ |u i (z i,t |r t ) -ūi t (z i,t )| + |ū i t (z i,t ) -u i (z i,t |r * )|. First we consider the second one |ū i t (z i,t ) -u i (z i,t |r * )| and we have similar bound for the first term. Conditioning on r * (z i,t ), we can apply the Chernoff-Hoeffding bound

Table content: <table><tr><td>equation 1 ⃝ holds by inserting a term c  *  (h C 1,t , a)u i (h C 1,t |σ i t , σ -i t , dt ); equation 2 ⃝ holds since</td></tr><tr><td>that h C 2,t is reached following the underlying transition c  *  (h C 1,t ; and equation 3 ⃝ holds by using</td></tr><tr><td>induction.</td></tr><tr><td>Therefore we finish the proof.</td></tr></table>

For another term |u i (z i,t |r t ) -ūi t (z i,t )|, we can still apply the technique in Lemma 5 to get below lemma: Lemma 6. At episode t, the expectation of |u i (z i,t |r t ) -ūi t (z i,t )| can be bounded by (s|r t ) -ūi t (s)|π t (s|d * )P r(d * , d t |H t )P r(H t )d(d * , d t , H t )

Table content: <table><tr><td>E Ht</td><td>{ E dt,d  *  E Ti,t</td><td>[ |u i (z i,t |r t ) -ūi t (z i,t )| ]</td><td>H t</td><td colspan="2">}</td><td colspan="2">≤ E Ht</td><td>{ E dt,d  *</td><td>[√</td><td>2 log(2/δ) max(n t (z i,t ), 1)</td><td>]</td><td>H t</td><td>}</td><td>+ 2|Z|δ.</td></tr><tr><td colspan="3">Proof. We can directly prove that</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td colspan="5">E Ht ∑ s∈Z |u i ≤ { E dt,d  *  E Ti,t = ∫ ∑ s∈Z ∫ √ ln(2/δ) [ |u i (z i,t |r t ) -ūi t (z i,t )| 2 max(n t (s), 1) π t (s|d  √</td><td>]</td><td>H t</td><td>}</td><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td colspan="3">ln(2/δ)</td><td/><td/><td/><td/></tr><tr><td/><td/><td/><td colspan="6">2 max(n t (s), 1)</td><td/><td/><td/><td/></tr></table>

C j,t , a) as the empirical mean of chance player's probability to choose a at h C j,t . Notice that the utility is bounded in [-1, 1]. We have ∑

Table content: <table><tr><td/><td colspan="4">(c t (h C j,t , a) -c  *  (h C j,t , a))u i (h C j,t |σ i t , σ -i t , dt )</td></tr><tr><td colspan="2">a∈α(h C j,t ) ≤2 ∑</td><td>|c t (h C j,t , a) -c  *  (h C j,t , a)|</td><td/><td/></tr><tr><td>≤2</td><td>a∈α(h C j,t ) ∑</td><td>|c t (h C j,t , a) -c(h C j,t , a)| + 2</td><td>∑</td><td>|c(h C j,t , a) -c  *  (h C j,t , a)|.</td></tr><tr><td/><td>a∈α(h C j,t )</td><td/><td>a∈α(h C j,t )</td><td/></tr></table>

to get that for δ ∈ (0, 1) Similar to the analysis in r, we give below lemma:Lemma At episode t, the expectation of |c(h C j,t , a) -c * (h C j,t , a)| can be bounded by ∑ |H t )P r(H t )d(d * , H t ) )P 0 (d * )d(d * , H t )The proof process above is similar to that of Lemma 5.Once again, we get below lemma: Lemma 9. At episode t, the expectation of |c(h C j,t , a) -c(h C j,t , a)| can be bounded by ∑ -c(h, a)|π t (h|d * )P r(d * , d t |H t )P r(H t )d(d * , d t , H t ) d|H t )P r(H t )d(d * , H t )

Table content: <table><tr><td/><td/><td>E Ht</td><td colspan="2">{ E dt,d  *  E Ti,t</td><td colspan="2">[ |c(h C j,t , a) -c(h C j,t , a)| ]</td><td>H t</td><td>}</td></tr><tr><td/><td colspan="2">a∈α(h C j,t ) {</td><td>[√</td><td/><td/><td>]</td><td>}</td></tr><tr><td/><td>≤E Ht</td><td>E dt,d  *</td><td/><td colspan="3">2 ln(2 A /δ) max(n t (h C j,t ), 1)</td><td>H t</td><td>+ |H C |δ.</td></tr><tr><td colspan="7">Proof. We use similar techniques to get E Ht    E dt,d  *  E Ti,t   ∑ a∈α(h C |c(h C j,t , a) -c(h C j,t , a)| j,t ) ∑ ∫ ∑</td><td>  H t</td><td>  </td></tr><tr><td colspan="7">P r h∈H C |c(h, a) ≤   ∑ a∈α(h C j,t ) |c(h C j,t , a) -c  *  (h C j,t , a)| ≥ a∈α(h C E Ht { E dt,d  ] √ 2 ln(2 A /δ) max(n t (h C j,t ), 1) c  *  (h C j,t , a) H t } = a∈α(h) ∑ h∈H C ∫ √ 2 A /δ) max(n t (h), 1) π t (s|d  h∈H C ∫ I    √ ∑ a∈α(h) |c(h, a) -c(h, a)| ≥ 2 ln(2 A /δ) max(n t (h), 1)  P r( (18)   &lt; δ. { [√ ] } j,t ) ≤E Ht { E dt,d  *  [√ 2 ln(2 A /δ) max(n t (h C j,t ), 1) ] H t } + |H C |δ. Proof. We use similar techniques to get E Ht    E dt,d  *  E Ti,t   ∑ a∈α(h C ∑ ∫ ∑ j,t ) |c(h C j,t , a) -c  *  (h C j,t , a)|   H t    =E Ht E dt,d  *  2 ln(2 A /δ) H t max(n t (h), 1) + ∑ h∈H C ∫ I    √ ∑ a∈α(h) 2 ln(2 A /δ) max(n t (h), 1) { [√  P r(H t |d  ≤E Ht 2 log(2 A /δ) E dt,d  *  max(n t (z i,t ), 1)</td></tr><tr><td>=</td><td/><td/><td/><td/><td/></tr><tr><td>≤</td><td colspan="3">h∈H C ∑ h∈H C π t (s|d  h∈H C a∈α(h) ∫ √ 2 ln(2 A /δ) max(n t (h), 1) ∫ I   ∑ a∈α(h) { [√ ]</td><td>}</td><td>√</td><td>2 ln(2 A /δ) max(n t (h), 1)</td><td>  P r(d  (17)</td></tr><tr><td colspan="7">=E Ht + ∑ E dt,d  *  h∈H C ∫ I {  P r(H t |d  ≤E Ht 2 ln(2 A /δ) H t max(n t (h), 1)    √ ∑ a∈α(h) |c(h, a) -c  *  (h, a)| ≥ 2 ln(2 A /δ) max(n t (h), 1) [√ ] } E dt,d  *  2 log(2 A /δ) max(n t (z i,t ), 1) H t + |H C |δ.</td></tr></table>

|D C AT ln(|H C |T )).The similar proof can be applied to the second term to get the same upper bound by simply replacing dt with d t : |D C AT ln(|H C |T )).

Table content: <table><tr><td>T ∑ t=1 |H C T E Ht { E dt,d  *  [ u i (σ i t , σ -i t | dt ) -u i (σ i t , σ -i t |d  *  ) ] H t } = O( √ √ |Z|T ln(|Z|T )+ ∑ E Ht { E dt,d  *  ,dt [ u i (σ i t , σ -i t |d  *  ) -u i (σ i t , σ -i t |d t ) ] H t } = O( √ √ |Z|T ln(|Z|T )+ |H C</td></tr><tr><td>t=1</td></tr></table>

Peer review (iclr2020):
Posterior sampling for multi-agent reinforcement learning: solving extensive games with imperfect information ================================================================ This paper investigates the use of Thompson sampling in multi-agent reinforcement learning. They present a natural extension of the PSRL algorithm paired with counterfactual regret minimization, rather than expected reward maximization. They 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. There are several things to like about this paper: - 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. - 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). - The general structure of the paper and presentation is good. - The support from the theorem is great, and also the empirical evaluation is convincing. There are a few places where the paper might be improved: - 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. - 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? - I*m not really an expert on the novelty / impressiveness of this algorithm in the multi-agent setting so cannot fully comment on that. Overall I think this is a really interesting paper that should be of interest to the ICLR community. I 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!