Year: 2022

Abstract:
Two-player zero-sum Markov game is a fundamental problem in reinforcement learning and game theory. Although many algorithms have been proposed for solving zero-sum Markov games in the existing literature, many of them either require a full knowledge of the environment or are not sample-efficient. In this paper, we develop a fully decentralized and sample-efficient stochastic policy extragradient algorithm for solving tabular zero-sum Markov games. In particular, our algorithm utilizes multiple stochastic estimators to accurately estimate the value functions involved in the stochastic updates, and leverages entropy regularization to accelerate the convergence. Specifically, with a proper entropy-regularization parameter, we prove that the stochastic policy extragradient algorithm has a sample complexity of the order Õ( Amax μmin 5.5(1−γ)13.5 ) for finding a solution that achieves -Nash equilibrium duality gap, where Amax is the maximum number of actions between the players, μmin is the lower bound of state stationary distribution, and γ is the discount factor. Such a sample complexity result substantially improves the state-of-the-art complexity result.

Two-player zero-sum Markov game is a fundamental problem in reinforcement learning and game theory. Although many algorithms have been proposed for solving zero-sum Markov games in the existing literature, many of them either require a full knowledge of the environment or are not sample-efficient. In this paper, we develop a fully decentralized and sample-efficient stochastic policy extragradient algorithm for solving tabular zero-sum Markov games. In particular, our algorithm utilizes multiple stochastic estimators to accurately estimate the value functions involved in the stochastic updates, and leverages entropy regularization to accelerate the convergence. Specifically, with a proper entropy-regularization parameter, we prove that the stochastic policy extragradient algorithm has a sample complexity of the order Õ( Amaxµmin 5.5(1−γ)13.5 ) for finding a solution that achieves -Nash equilibrium duality gap, where Amax is the maximum number of actions between the players, µmin is the lower bound of state stationary distribution, and γ is the discount factor. Such a sample complexity result substantially improves the state-of-the-art complexity result.
1 INTRODUCTION
Competitive reinforcement learning (RL) is an emerging and popular framework that has broad applications in various areas, including market pricing applications (Kononen and Oja, 2004), realtime strategy-making (Vinyals et al., 2019), board games (Silver et al., 2017; Moerland et al., 2018) and inverse RL (Zhang et al., 2019). In particular, an important and fundamental formulation of competitive RL is the two-player zero-sum Markov game, which involves two competing players that interact with a common environment and receive zero-sum rewards. Both players aim to learn the optimal policy that achieves the Nash equilibrium of accumulated rewards.
Algorithms for solving Markov games are very different from conventional single-agent RL algorithms. In particular, both players must learn to improve their policies based on feedback from the opponent and the environment, but usually the opponent will not reveal any sensitive information (e.g., actions or policy) or cooperate with each other. In the existing literature, numerous algorithms have been developed for solving zero-sum Markov games, including Q-learning (Fan et al., 2020; Zhu and Zhao, 2020), fitted Q iteration (Zhang et al., 2021), policy gradient (Daskalakis et al., 2020; Zhao et al., 2021), policy extragradient (Cen et al., 2021), model-based Monte Carlo estimation (Zhang et al., 2020), optimistic gradient descent ascent (Wei et al., 2021), etc. However, many of these algorithms require both players to access their opponent’s actions (Wei et al., 2017; Sidford et al., 2020; Huang et al., 2021; Jafarnia-Jahromi et al., 2021), which causes privacy issues. On the other hand, some algorithms need to know about the environment transition kernel and reward mapping (Cen et al., 2021), which are usually unknown a priori in practice. Moreover, other algorithms require both players to perform asymmetric policy updates using different numbers of iterations, learning rates or exploration probabilities (Zhao et al., 2021; Daskalakis et al., 2020), which are generally
hard to coordinate in advance between two competing players. Therefore, it is desired to develop an algorithm for solving Markov games that avoids all the aforementioned issues.
Moreover, from a theoretical perspective, the convergence and sample complexity of these existing algorithms for solving Markov games have not been comprehensively studied. Specifically, some studies established the convergence of the algorithms with i.i.d. samples (Zhao et al., 2021; Guo et al., 2021), which violates the dependent nature of samples collected from the dynamic Markov decision process. Also, other algorithms suffer from an extremely high sample complexity to achieve an approximate Nash equilibrium solution (Wei et al., 2021). Hence, we are motivated to answer the following fundamental question.
• Q: Can we develop a fully decentralized algorithm that is model-free and takes symmetric and private policy updates for solving zero-sum Markov games, with provable convergence guarantee and an improved sample complexity for achieving a Nash equilibrium solution?
In this paper, we provide positive and comprehensive answers to this question by developing a fully decentralized stochastic policy extragradient algorithm. In Table 1 of Appendix F, we compare the key properties and sample complexity of our algorithm with those of the existing algorithms.
1.1 OUR CONTRIBUTIONS
We consider a standard zero-sum Markov game with discounted reward over infinite horizon. To solve such a Markov game, we propose a stochastic variant of the policy extragradient algorithm (Cen et al., 2021) that satisfies the following amenable properties.
• Our algorithm uses multiple stochastic estimators to estimate the value functions involved in the predictive updates for solving entropy-regularized matrix games, and therefore the algorithm does not rely on any prior knowledge of the environment transition kernel (model-free). Moreover, the resulting stochastic policy updates of our algorithm for both players are symmetric and do not involve any sensitive information of the opponent (private).
• Compared with the stochastic estimators used in (Wei et al., 2021), our estimators have much smaller variance that helps improve the estimation accuracy. Specifically, by developing new techniques (explained in the next bullet), we establish tight high-probability estimation error bounds for our stochastic estimators with Markovian samples. Then, with a proper entropyregularization parameter, we show that our stochastic policy extragradient algorithm requires a sample complexity of the order O( Amaxµmin 5.5(1−γ)13.5 ) to achieve an -Nash equilibrium duality gap, which substantially improves the state-of-the-art complexity result of (Wei et al., 2021).
• We develop novel techniques to bound the estimation error of the proposed stochastic estimators, whose numerator and denominator involve sample average approximations. First, we propose a special estimation error decomposition that avoids divergence of the bound caused by possibly small numerical values of the sample average involved in the denominator of the stochastic estimators. Second, we leverage this error decomposition and the recursive structure of the stochastic estimators to derive a contraction property of the estimation errors, which eventually leads to tight bounds for the estimation error. We refer to Section 4 for more elaboration on our technical novelties.
1.2 OTHER RELATED WORK
Other settings of two-player zero-sum Markov games. In this paper, we focus on a standard setting of two-player zero-sum Markov game with discount and infinite horizon in the discrete time domain. There are other settings of two-player zero-sum Markov games. For example, Bai et al. (2020); Huang et al. (2021) studied a two-player zero-sum Markov game with finite horizon and without discount, whereas Daskalakis et al. (2020) considered finite random horizon without discount. Jafarnia-Jahromi et al. (2021) also considered the setting without discount, and it allows one of the players to constantly adjust its policy based on the entire history of states and actions. Ghosh et al. (2021) studied a two-player zero-sum Markov game in the continuous time domain.
Multi-agent general-sum Markov game. Some works studied multi-agent Markov games, which extend the two-player zero-sum Markov games to multiple players without the zero-sum constraint (Wang and Sandholm, 2002; Hu and Wellman, 2003; Deng et al., 2021; Leonardos et al., 2021). More specifically, Leonardos et al. (2021) defined and studied Markov potential game which has a potential
function assumption. Guo et al. (2019); Elie et al. (2020); Gu et al. (2021) studied mean-field games with a large number of players.
Entropy regularization and value iteration Our algorithm leverages entropy regularization and value iteration to accelerate convergence. Entropy regularization is a popular technique that has been widely used in reinforcement learning (Neu et al., 2017; Geist et al., 2019; Mei et al., 2020; Cen et al., 2020) and Markov game (Mertikopoulos and Sandholm, 2016; Savas et al., 2019; Cen et al., 2021) to encourage environment exploration and accelerate algorithm convergence. Value iteration is also a classical method that is widely used in both single-agent reinforcement learning (Ernst et al., 2005; Tamar et al., 2016; Farahmand and Ghavamzadeh, 2021) and Markov games (Zhu and Zhao, 2020; Cen et al., 2021). With full knowledge of the environment, it exponentially converges to the fixed point of Bellman operator (Cen et al., 2021). Compared to another similar classical method called policy iteration, value iteration does not need policy evaluation which involves additional computation (Sutton and Barto, 2018).
2 BACKGROUND OF MARKOV GAME AND ENTROPY REGULARIZATION
2.1 TWO-PLAYER ZERO-SUM MARKOV GAME
In a zero-sum Markov game, two players compete with each other in a common environment. Throughout, the state space is denoted as S. The action spaces and policies of both players are denoted as A(1), π(1) and A(2), π(2), respectively. Here, π(1) ∈ ∆(|A(1)|), π(2) ∈ ∆(|A(2)|) are random policies defined over the corresponding simplex sets. The reward function is denoted as R : S ×A(1) ×A(2) → [0, 1], and the discount factor is denoted as γ ∈ (0, 1). At any time t, both players observe state st ∈ S of the environment. Then, both players respectively select their actions following their own policies, i.e., a(1)t ∼ π(1)(·|st) and a (2) t ∼ π(2)(·|st). After that, the environment state transfers to a new state st+1 following the underlying transition kernel P(·|st, a(1)t , a (2) t ), and both players receive zero-sum rewards, i.e., R (1) t = −R (2) t = Rt, where Rt := R(st, a (1) t , a (2) t ). With this Markov decision process, we can define the following state value function associated with the players’ policies π(1) and π(2) for any environment state s ∈ S.
Vπ(1),π(2)(s) = E [ ∞∑ t=0 γtRt ∣∣∣s0 = s]. (1) The goal of both players is to compete via the following minimax game in all states s.
min π(2) max π(1) Vπ(1),π(2)(s). (2)
In particular, it has been shown in (Shapley, 1953) that there exists a Nash equilibrium policy pair π (1) ∗ , π
(2) ∗ for zero-sum Markov games, i.e., Vπ(1),π(2)∗ (s) ≤ Vπ(1)∗ ,π(2)∗ (s) ≤ Vπ(1)∗ ,π(2)(s) holds for
any other policies π(1), π(2) and for all states s.
2.2 ENTROPY-REGULARIZED MARKOV GAME
Entropy regularization is a popular technique that has been widely used in reinforcement learning (Neu et al., 2017; Geist et al., 2019; Mei et al., 2020; Cen et al., 2020) and Markov game (Mertikopoulos and Sandholm, 2016; Savas et al., 2019; Cen et al., 2021) to encourage environment exploration and accelerate algorithm convergence.
Specifically, for the zero-sum Markov game, we can define an entropy-regularized state value function by adding entropy regularization to the state value function in (1) as follows (Cen et al., 2021).
V (τ)
π(1),π(2) (s) :=E [ ∞∑ t=0 γt [ Rt − τ lnπ(1)(a(1)t |st) + τ lnπ(2)(a (2) t |st) ]∣∣∣s0 = s], (3) where τ > 0 is called the regularization parameter. With the above definition, we further define the following entropy-regularized state-action value function (also called Q-function) (Cen et al., 2021).
Q (τ) π(1),π(2) (s, a(1), a(2)) :=R(s, a(1), a(2)) + γEs′∼P(·|s,a(1),a(2))
[ V (τ) π(1),π(2) (s′) ] . (4)
In particular, V (τ) π(1),π(2) can be obtained from Q(τ) π(1),π(2) as follows.
V (τ) π(1),π(2) (s) =[π(1)(s)]>Q (τ) π(1),π(2) (s)π(2)(s) + τH
( π(1)(s) ) − τH ( π(2)(s) ) :=fτ ( Q (τ)
π(1),π(2) (s), π(1)(s), π(2)(s)
) , (5)
whereH(π) denotes the entropy of policy π, and we define this mapping as fτ for convenience. For the entropy regularized Markov game, it has an equilibrium policy pair that solves the minimax optimization problem minπ(2) maxπ(1) V (τ) π(1),π(2) (s). Such a policy pair is called the quantal response equilibrium (QRE). Our goal is to find the equilibrium policy pair of the original Markov game in (2) by solving the entropy-regularized Markov game with a proper regularization parameter τ . In particular, compared with the equilibrium policy of the Markov game, the QRE tends to have a larger entropy due to the entropy regularization, which encourages the players to explore and obtain a better understanding of the environment. Another advantage of considering the entropy-regularized Markov game is that the entropy regularization makes the minimax problem have a better optimization geometry that accelerates the convergence of the optimization process.
3 STOCHASTIC POLICY EXTRAGRADIENT ALGORITHM FOR ENTROPY-REGULARIZED MARKOV GAME
In this section, we develop a stochastic policy extragradient (SPE) algorithm for solving entropyregularized Markov games. First, we recap the policy extragradient (PE) algorithm, which is introduced in (Cen et al., 2021) to solve entropy-regularized Markov games with full knowledge of the environment transition kernel and reward mapping. Then, we propose the model-free SPE algorithm that solves entropy-regularized Markov games using only stochastic samples.
3.1 REVIEW OF POLICY EXTRAGRADIENT ALGORITHM
Value iteration is a classical reinforcement learning algorithm that requires full knowledge of the environment and achieves an exponential convergence rate. In particular, for the entropy-regularized Markov game, the k-th value iteration update is defined as follows.
Qk(s, a (1), a(2)) =R(s, a(1), a(2)) + γEs′∼P(·|s,a(1),a(2)) [ Vk(s ′) ] , ∀s, a(1), a(2), (6)
Vk+1(s) = min π(2)(s) max π(1)(s)
fτ ( Qk(s);π (1)(s), π(2)(s) ) , ∀s, (7)
where we define Qk(s) := Qk(s, ·, ·) ∈ R|A (1)|×|A(2)|. This algorithm alternatively updates all the entries of the value functions Qk and Vk. Thanks to the entropy regularization in the function fτ (see (5) for the definition), the minimax matrix game in (7) is τ -strongly concave in π(1) and τ -strongly convex in π(2), and therefore it has a unique solution.
To solve the entropy-regularized minimax matrix game in (7), Cen et al. (2021) proposed a predictive update (PU) algorithm. Specifically, with uniform policy initialization, i.e., π(m)k,0 (s) = 1 |A(m)| ,∀m ∈ {1, 2},∀s ∈ S, the PU algorithm performs the following policy updates: for t = 0, 1, 2, ...
(PU):  π (1) k,t+1(a (1)|s) ∝ π(1)k,t (a (1)|s)1−ητ exp ( ηQ (1) k,t(s, a (1)) ) π (2) k,t+1(a (2)|s) ∝ π(2)k,t (a (2)|s)1−ητ exp ( − ηQ(2)k,t(s, a (2)) ) π (1) k,t+1(a (1)|s) ∝ π(1)k,t (a (1)|s)1−ητ exp ( ηQ (1) k,t+1(s, a (1)) )
π (2) k,t+1(a (2)|s) ∝ π(2)k,t (a (2)|s)1−ητ exp ( − ηQ(2)k,t+1(s, a(2))
) , (8)
where we use the following notations (superscript (\m) denotes the opponent of the m-th player.).
Q (m) k,t (s, a (m)) := E a(\m)∼π(\m)k,t (s)
[ Qk(s, a (1), a(2)) ] , m ∈ {1, 2} (9)
Q (m)
k,t+1(s, a (m)) := E
a(\m)∼π(\m)k,t+1(s)
[ Qk(s, a (1), a(2)) ] , m ∈ {1, 2}. (10)
Once we obtain the output policy pair (π(1)k , π (2) k ) of the PU algorithm, we can obtain an approximation of Vk+1(s) as V ′k+1(s) = fτ ( Qk(s);π (1) k (s), π (2) k (s) ) , which will be further used in the next Q-value function update (6) to replace Vk+1(s′). The updates (6), (7) & (8) are referred to as policy extragradient (PE) algorithm.
In the PE algorithm, the PU update in (8) allows both players to take symmetric updates without revealing their private actions, and has been shown to converge to the unique solution of the entropyregularized matrix game (7) exponentially fast (Cen et al., 2021). However, the PE algorithm has several limitations. First, in the PU update, each player m ∈ {1, 2} needs to query the quantities Q
(m) k,t (s, a (m)), Q (m) k,t (s, a (m)) from its opponent. To compute these quantities, the opponent needs to multiply the entire Q-table by its own policy vector. This requires both players to coordinate with each other and share aQ-table. Second, the update of theQ-table in (6) requires full knowledge of the environment transition kernel P and the reward mapping R, which are unknown a priori in practice. To overcome these limitations, we develop a fully stochastic PE algorithm in the next subsection.
3.2 STOCHASTIC POLICY EXTRAGRADIENT ALGORITHM
The major challenge of the PE algorithm is computing the quantities Q(m)k,t , Q (m) k,t and V ′ k+1, which requires coordinating with the opponent and involves the environment information. Here, we develop a model-free and fully stochastic variant of PE that estimates these key quantities using Markovian stochastic samples. We refer to this algorithm as stochastic policy extragradient (SPE).
Specifically, we first estimate the quantity V ′k+1(s) = fτ ( Qk(s);π (1) k (s), π (2) k (s) ) . By definition of fτ in (5) and the update of Qk in (6) (now we use V ′k(s ′) instead of Vk(s′)) and using some standard tricks on random variables (see Lemma 2 in Appendix B for a full proof), we can rewrite V ′k+1(s) as
V ′k+1(s) = E [( R(s̃, ã(1), ã(2)) + γV ′k(s ′) ) 1{s̃ = s} ] µk(s) + τH ( π (1) k (s) ) − τH ( π (2) k (s) ) , (11)
where µk(s) denotes the stationary state distribution associated with the policy pair (π (1) k , π (2) k ), and the expectation is taken over s̃ ∼ µk, ã(1) ∼ π(1)k (s), ã(2) ∼ π (2) k (s), s
′ ∼ P(·|s̃, ã(1), ã(2)). To estimate this quantity, we query a set Nk+1 (with cardinality Nk+1) of samples from the Markov decision process following the pair of policies (π(1)k , π (2) k ). Then, we estimate V ′ k+1(s) as
V̂k+1(s) =
1 Nk+1 ∑ i∈Nk+1 ( Ri + γV̂k(si+1) ) 1{si = s}
1 Nk+1 ∑ i∈Nk+1 1{si = s}
+ τH ( π
(1) k (s)
) − τH ( π
(2) k (s)
) . (12)
Intuitively, we use the sample average of Markovian samples to estimate the expectation terms in (11). Thanks to the concentration phenomenon of dependent samples (Paulin, 2015), these sample averages converge to the desired expected values provided that the sample size is sufficiently large.
Next, we estimate Q(m)k,t ,m ∈ 1, 2. Leveraging (9) and (6), we obtain the following equivalent characterization for both players m ∈ 1, 2 (see Lemma 2 in Appendix B for the proof of equivalence).
Q (m) k,t (s, a
(m)) = E [( R(s̃, ã(1), ã(2)) + γV ′k(s ′) ) 1{s̃ = s, ã(m) = a(m)} ] µk,t(s)π (m) k,t (a (m)|s) , (13)
where 1{·} denotes the indicator function, µk,t denotes the stationary state distribution associated with the policy pair (π(1)k,t , π (2) k,t ), and the expectation is taken over s̃ ∼ µk,t, ã(1) ∼ π (1) k,t (s), ã
(2) ∼ π
(2) k,t (s), s ′ ∼ P(·|s̃, ã(1), ã(2)). To estimate this quantity, we query a set Nk,t (with cardinality Nk,t) of samples from the Markov decision process following a pair of smoothed policies π′(m)k,t (s) = (1− ′)π(m)k,t (s) + ′ |A(m)|1, where ′ ∈ [0, 1] is a small smoothing constant that will be theoretically determined later. Then, we estimate Q(m)k,t (s, a (m)) as follows.
Q̂ (m) k,t (s, a (m)) =
1 Nk,t ∑ i∈Nk,t ( Ri + γV̂k(si+1) ) 1{si = s, a(m)i = a(m)}(
1 Nk,t ∑ i∈Nk,t 1{si = s} ) π ′(m) k,t (a (m)|s) , (14)
where we have replaced the expectations with sample averages, and replaced V ′k(s ′) with V̂k(s′). Here, the Markovian samples are queried following the ′-smoothed policies (π′(1)k,t , π ′(2) k,t ). On one hand, ′ should not be too small so that it keeps the denominator of the above estimation away from zero. On the other hand, ′ should not be too large so that it is sufficiently close to the original policy.
Similarly, to estimate Q (m)
k,t , we query another set N k,t (with cardinality Nk,t) of samples from the Markov decision process following a pair of smoothed policies π′(m)k,t (s) = (1− ′)π (m) k,t (s)+ ′ |A(m)|1, where ′ ∈ [0, 1] will be theoretically determined later. Then, we estimate Q(m)k,t as follows.
Q̂ (m)
k,t (s, a (m)) =
1 Nk,t ∑ i∈Nk,t ( Ri + γV̂k(si+1) ) 1{si = s, a(m)i = a(m)}(
1 Nk,t ∑ i∈Nk,t 1{si = s} ) π ′(m) k,t (a (m)|s) . (15)
Remark 1. The estimators (12), (14) & (15) essentially use ratio of sample averages to approximate ratio of expectations. Estimators with similar structure have been used in (Ortner and Auer, 2007; Xia et al., 2016; Wei et al., 2021). However, these works analyze the estimation error of their estimators with independence samples. As a comparison, our analysis of the estimation error bounds the additional bias induced by the correlated Markovian samples, and achieves an improved sample complexity in the main Theorem 2.
We summarize our stochastic policy extragradient (SPE) algorithm in Algorithm 1. Specifically, in SPE, we estimate the quantities Q(m)k,t , Q (m) k,t , V ′ k using their corresponding stochastic estimators. As a result, the SPE algorithm is model-free, and the updates for both players are symmetric and private.
Algorithm 1 Stochastic policy extragradient (SPE) for entropy-regularized Markov game Initialize: V ′0(s) for all s ∈ S. for value iterations k = 0, 1, . . . ,K − 1 do
Initialize π(1)k,0, π (2) k,0 with uniform distribution. for PU iterations t = 0, 1, . . . , Tk − 1 do Players 1,2 sample Nk,t Markovian samples following smoothed policies π ′(1) k,t , π ′(2) k,t .
Every player m ∈ {1, 2} computes Q̂(m)k,t (s, a(m)) for all s, a(m) using (14). Players 1,2 sample Nk,t Markovian samples following smoothed policies π ′(1) k,t , π ′(2) k,t . Every player m ∈ {1, 2} computes Q̂ (m)
k,t (s, a (m)) for all s, a(m) using (15).
Implement the t-th PU iteration for all s, a(1), a(2) using (8) with estimations (14)&(15). end Let π(m)k = π (m) k,Tk , m = 1, 2. Players sample Nk Markovian samples following π (1) k , π (2) k .
Compute V̂k+1(s) for all s using (12). end Output: π(1)K−1, π (2) K−1.
4 FINITE-TIME CONVERGENCE ANALYSIS OF SPE
Throughout our convergence analysis, we adopt the following two standard assumptions.
Assumption 1. Denote Tπ(1),π(2)(s, s′) := inf{t ≥ 1 : st = s′|s0 = s} as the first-visit time under the policy pair π(1), π(2). We assume that
sup s,s′∈S sup π(1),π(2)
Eπ(1),π(2) [ Tπ(1),π(2)(s, s ′) ] < +∞. (16)
Assumption 1 is widely used in the reinforcement learning literature (Ortner and Auer, 2007; Ortner, 2020; Wei et al., 2021; Jafarnia-Jahromi et al., 2021). It ensures that every state will be visited at least once within a finite duration of time, thus ensuring that all the states will be visited infinitely often.
This guarantees sufficient exploration. In our analysis, we use the following equivalent statement of Assumption 1 for convenience, which means that the stationary state distribution µπ(1),π(2) has a uniform lower bound µmin > 0. Their equivalence is based on Theorem 5.5.11 of (Durrett, 2019).
µmin := inf s∈S inf π(1),π(2)
µπ(1),π(2)(s) = [
sup s∈S sup π(1),π(2)
Eπ(1),π(2)Tπ(1),π(2)(s, s) ]−1 > 0. (17)
Assumption 2. There exists a mixing time tmix ∈ N such that for any policy pair π(1), π(2) and its corresponding stationary state distribution µπ(1),π(2) , we have
dTV ( Pπ(1),π(2)(stmix), µπ(1),π(2) ) ≤ 1
4 .
where Pπ(1),π(2)(stmix) denotes the state distribution under the policy pair π(1), π(2) at time tmix, and dTV denotes the total variation distance between two probability distributions.
In this subsection, we analyze the finite-time convergence of Algorithm 1 for solving the entropyregularized Markov game (5). We focus on the convergence rate of the following Nash equilibrium duality gap, which is a standard optimality metric widely adopted in the existing literature (Xu et al., 2020; Jin and Sidford, 2021; Wei et al., 2021).
D(τ)(π(1), π(2)) := max s ( max π V (τ) π,π(2) (s)−min π′ V (τ) π(1),π′ (s) ) .
In particular, when τ = 0, D(0)(π(1), π(2)) corresponds to the duality gap of the original Markov game. Throughout, we define Amax := max{|A(1)|, |A(2)|}, Qmax := 1+γτ lnAmax1−γ and Vmax := 1+τ lnAmax
1−γ . We also require that the batch sizes of Algorithm 1 satisfy the following conditions.
Nk,t, Nk,t ≥ 650tmixAmax µmin ln (20Tsum|S|Amax δ √ µmin ) , ∀k, t, (18)
Nk+1 ≥ 650tmix µmin(1− γ)2 ln ( 4 δ √ µmin ) , ∀k. (19)
Then, we obtain the following convergence result of Algorithm 1, where Tsum := ∑K−1 k=0 Tk. Theorem 1 (Finite-time convergence rate). Apply Algorithm 1 to solve the entropy-regularized Markov game with τ ∈ (0, 1]. Choose learning rate η = [2(τ +Qmax)]−1, initialization ‖V̂0‖∞ ≤ Vmax and batch sizes Nk,t, Nk,t, Nk+1 that satisfy (18) & (19). Then, the Nash equilibrium duality gap converges at the following rate with probability at least 1− δ. D(τ) ( π
(1) K−1, π (2) K−1
) ≤ O ( Vmax lnAmax
1− γ
K−1∑ k=0 γK−k(1− ητ)Tk−1
+ Vmax 1− γ [ tmixAmax µmin ln (Tsum|S|Amax δµmin )]2/3 K−1∑ k=0 γK−k−1 Tk−1∑ t=0 (1− ητ)Tk−2−t ( 1 N 2/3 k,t + Vmax τN 2/3 k,t+1 )
+ V 3maxγ K
τ2(1− γ)2 +
tmixV 3 max τ2µmin(1− γ)3 ln ( K|S| δµmin )K−1∑ k=0 γK−k−1 Nk+1 ) . (20)
Remark 2. In the proof of Theorem 1, we also prove that the convergence rate of the Q-function estimation error ‖QK−Q(τ)∗ ‖∞ is (1−γ) times the convergence rate in (20). Here, QK corresponds to the Q-function associated with the policy pair (π(1)K , π (2) K ) produced by Algorithm 1 in the K-th iteration, and Q(τ)∗ corresponds to the optimal Q-function associated with the Nash equilibrium policy pair π(1)∗τ , π (2) ∗τ of the entropy-regularized Markov game.
Theorem 1 characterizes the convergence of duality gap of the SPE algorithm under general hyperparameter scheduling of the batch sizes Nk,t, Nk,t, Nk+1 and number of inner iterations Tk. Specifically, it can be seen that as the number of outer iterations K and inner iterations Tk increase, the duality gap converges to an exponentially weighted average of N−2/3k,t , N −2/3 k,t+1 and N −1 k+1, and the
gap can be made arbitrarily small by choosing sufficiently large batch sizes. To provide an intuitive understanding, we can set these hyper-parameters as constants, i.e., Tk ≡ T , Nk,t ≡ N , Nk,t ≡ N , Nk+1 ≡ N ′, and then the convergence rate in (20) simplifies to
O ( V 3maxγ K
τ2(1− γ)2 + γVmax lnAmax (1− γ)2 (1− ητ)T−1 + tmixV
3 max τ2µmin(1− γ)4 ln ( K|S| δµmin ) 1 N
+ Vmax ητ(1− ητ)(1− γ)2 [ tmixAmax µmin ln (Tsum|S|Amax δµmin )]2/3( 1 N2/3 + Vmax
τN 2/3
)) . (21)
To elaborate, the first term characterizes the exponential convergence of the K outer value iterations. This convergence is faster than the sublinear convergence O( √ lnK/K) established in (Wei et al., 2021). The second term characterizes the exponential convergence of the T inner PU iterations. Moreover, the last two terms characterize the estimation errorsO(N−1) andO(N−2/3)+O(N−2/3) of the estimators (12) and (14,15), respectively. As a comparison, Wei et al. (2021) established a much larger estimation error O(N−1/3). These improvements, as we show in Theorem 2 later, lead to a substantially improved overall sample complexity over the state-of-the-art result. In particular, due to the exponentially weighted average structure in (20), the sample complexity can be further optimized by an adaptive scheduling of the batch sizes.
Technical Novelty. We further comment on the proof of Theorem 1. Note that the analysis of the PE algorithm in (Cen et al., 2021) requires full knowledge of the environment and does not characterize the convergence of duality gap. As a comparison, to establish the duality gap convergence rate (20) of the model-free SPE, we need to make substantial new developments to tightly bound the estimation errors of the proposed stochastic estimators. We elaborate our technical contributions below.
• As we explained in Remark 1, the sample averages involved in our estimators are correlated Markovian samples. To bound the additional bias induced by these correlated samples, we apply the concentration inequalities developed in (Paulin, 2015) for dependent samples to establish tight high-probability estimation error bounds.
• We develop a much refined analysis of the state value function estimation error ‖V̂k+1 − V ′k+1‖∞, which is the key to develop tight bounds for all the other estimation errors. Specifically, we first propose the following error decomposition for any state s
|V̂k+1(s)−V ′k+1(s)|= ∣∣∣ v̂k+1(s) µ̂k(s) − vk+1(s) µk(s) ∣∣∣≤ |v̂k+1(s)−vk+1(s)| µk(s) + ∣∣v̂k+1(s)∣∣∣∣∣µk(s)−µ̂k(s) µk(s)µ̂k(s) ∣∣∣, where v̂k+1(s), µ̂k+1(s) are sample average estimators of vk+1(s), µk+1(s), respectively, and we refer to Appendix B for the definitions of these terms. The motivation is that the
∣∣v̂k+1(s)∣∣ in the second term helps cancel out the estimator µ̂k(s) in the denominator, and then all the denominators do not involve any sample average estimators, which may take a small numerical value that causes divergence and a loose concentration bound. By leveraging this special decomposition and the recursive structure of the stochastic estimator (12), we are able to establish the following key contraction property of the estimation error (see (85) in Appendix B).
‖V̂k+1 − V ′k+1‖∞ ≤ γ‖V̂k − V ′k‖∞ +O ( N −1/2 k+1 ) .
By telescoping the above contraction bound, we obtain tight estimation error bounds for all the proposed stochastic estimators. As a comparison, Wei et al. (2021) directly applied the AzumaHoeffding inequality with independent samples to bound the entire estimator and obtain a loose error bound, and Liu et al. (2021) simply assumed a small upper bound for the estimation error.
• We develop a stochastic predictive update (SPU) algorithm with general inexact value function estimations and a finite-time convergence analysis of its duality gap (see Lemma 1 for the SPU algorithm and its convergence proof). This generalizes the convergence result of the PU algorithm established in (Cen et al., 2021), which uses exact value functions based on full knowledge of the environment. Finally, by incorporating our developed tight estimation error bounds into the finite-time duality gap bound of SPU, we obtain the desired convergence rate in Theorem 1.
Based on Theorem 1, we obtain the following sample complexity of SPE for achieving an -Nash equilibrium duality gap of the original Markov game, i.e., D(0)(π(1)K−1, π (2) K−1) ≤ . Here, we adopt an adaptive batch size scheduling scheme to optimize the complexity order. The overall sample complexity is given by ∑K−1 k=0 [ Nk+1 + 2 ∑Tk−1 t=0 (Nk,t +Nk,t+1) ] .
Theorem 2 (Sample complexity). Implement Algorithm 1 with η = O ( 1 − γ ) , τ = O ( (1−γ) lnAmax ) ,
K = O [
1 1−γ ln ( lnAmax (1−γ) )] and Tk = 1 + k ln γ −1 ln(1−ητ)−1 . Choose the following adaptive batch sizes.
Nk+1 = Õ ( tmix(ln2Amax)γ− k2 2µmin(1− γ)8 ) , Nk,t = Nk,t 3 2 (1− γ)3 = Õ ( tmixAmax(1− ητ)−3(t+1)5 µmin(1− γ)3 ) .
Then, for any ≤ lnAmax1−γ , the overall sample complexity to achieve D (0)(π (1) K−1, π (2) K−1) ≤ is Õ (
tmixAmax µmin 5.5(1−γ)13.5
) . Please refer to (118) in Appendix E for a complete expression.
The above complexity result is obtained by choosing a small τ = O ( (1−γ)
lnAmax
) for the convergence rate
result in Theorem 1. Specifically, we show in Lemma 6 that the duality gap is Lipschitz continuous with regard to the entropy regularization parameter, i.e., ∣∣D(τ)(π(1), π(2)) − D(0)(π(1), π(2))∣∣ ≤ 2τ lnAmax
1−γ . Therefore, by choosing a proper small τ , convergence of the duality gap D (τ) of the entropy-regularized Markov game implies the convergence of the duality gap D(0) of the original Markov game.
Remark on Improvement of Sample Complexity. We elaborate on the improvement of sample complexity in two different levels: population level (with known environment) and stochastic level (using stochastic samples). First, in the population level, the original policy extragradient (PE) algorithm in (Cen et al., 2021) already achieves a faster convergence rate than the OGDA-based algorithm proposed in (Wei et al., 2021). Specifically, to achieve an -Nash equilibrium point of the original Markov game, PE requires O ( Amax
(1−γ) ln 2 −1
) iterations by choosing a proper entropy
regularization parameter τ = O( (1−γ)lnAmax ). As a comparison, the OGDA-based algorithm requires Õ (
|S|3 (1−γ)9 2
) iterations by substituting = 0 (no stochastic error) and their choice of step size into
the Theorem 1 of Wei et al. (2021). This improvement is in the order of Õ( −1) and is due to the use of entropy regularization in the PE algorithm, which improves the geometry of the bilinear matrix game. Second, the rest of the improvement of sample complexity (about Õ( −1.5)) comes from the stochastic level. Specifically, our stochastic PE (SPE) allows to use a large constant learning rate η = O ( 1− γ ) , whereas the OGDA-based algorithm in (Wei et al., 2021) needs to use a substantially
smaller learning rate η = O( √
(1− γ)5|S|−1), which significantly slows down its convergence in both the population and stochastic levels. Moreover, both the PE and our SPE take O(ln −1) inner updates to achieve an accurate solution of the matrix game (7), whereas the OGDA-based algorithm uses only one inner update to solve the matrix game and hence suffers from a larger optimization error. Finally, as we explained in the previous technical novelty paragraph, we improve the techniques used in bounding the estimation errors. Specifically, Wei et al. (2021) bounds the estimation errors in all the iterations by a small constant using independent samples. As a comparison, we establish a key contraction property of the estimation error over the iterations with correlated Markovian samples. Such a property allows us to use a growing batch size that bounds the errors loosely in the initial iterations and achieves tight error bounds in the end.
5 CONCLUSION
In this paper, we developed a model-free, provably convergent, sample efficient, symmetric and private stochastic policy extra gradient algorithm for solving two-player zero-sum Markov games. Our algorithm leverages entropy regularization to facilitate the algorithm convergence and develops new stochastic estimators to accurately estimate the value functions. We proved that our SPE algorithm achieved a fast convergence rate in terms of the Nash equilibrium duality gap and moreover, achieves a substantially improved sample complexity over the state-of-the-art result. We believe our algorithm deepens the understanding of Markov games from a computation complexity perspective. In the future study, it is interesting to extend SPE algorithm to the multi-agent setting for solving general-sum Markov games and competitive games that involve multiple cooperative teams. Another interesting direction is to improve the algorithm to further reduce the sample complexity to approach the theoretical lower bound established in (Zhang et al., 2020).
ACKNOWLEDGMENTS
The work of Ziyi Chen, Shaocong Ma and Yi Zhou was supported in part by U.S. National Science Foundation under the Grants CCF-2106216 and DMS-2134223.
REFERENCES Bai, Y., Jin, C., and Yu, T. (2020). Near-optimal reinforcement learning with self-play. Proc. Advances
in Neural Information Processing Systems (Neurips), 33.
Cen, S., Cheng, C., Chen, Y., Wei, Y., and Chi, Y. (2020). Fast global convergence of natural policy gradient methods with entropy regularization. ArXiv:2007.06558.
Cen, S., Wei, Y., and Chi, Y. (2021). Fast policy extragradient methods for competitive games with entropy regularization. ArXiv:2105.15186.
Daskalakis, C., Foster, D. J., and Golowich, N. (2020). Independent policy gradient methods for competitive reinforcement learning. In Proc. Advances in Neural Information Processing Systems (Neurips), volume 33.
Deng, X., Li, Y., Mguni, D. H., Wang, J., and Yang, Y. (2021). On the complexity of computing markov perfect equilibrium in general-sum stochastic games. ArXiv:2109.01795.
Durrett, R. (2019). Probability: theory and examples, volume 49. Cambridge university press.
Elie, R., Perolat, J., Laurière, M., Geist, M., and Pietquin, O. (2020). On the convergence of model free learning in mean field games. In Proc. the AAAI Conference on Artificial Intelligence (AAAI), volume 34, pages 7143–7150.
Ernst, D., Geurts, P., and Wehenkel, L. (2005). Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 6:503–556.
Fan, J., Wang, Z., Xie, Y., and Yang, Z. (2020). A theoretical analysis of deep q-learning. In Proc. Learning for Dynamics and Control (L4DC), pages 486–489.
Farahmand, A.-M. and Ghavamzadeh, M. (2021). Pid accelerated value iteration algorithm. In Proc. International Conference on Machine Learning (ICML), pages 3143–3153.
Geist, M., Scherrer, B., and Pietquin, O. (2019). A theory of regularized markov decision processes. In Proc. International Conference on Machine Learning (ICML), pages 2160–2169.
Ghosh, M. K., Golui, S., Pal, C., and Pradhan, S. (2021). Zero-sum games for continuous-time markov decision processes with risk-sensitive average cost criterion. ArXiv:2109.08837.
Gu, H., Guo, X., Wei, X., and Xu, R. (2021). Mean-field multi-agent reinforcement learning: A decentralized network approach. ArXiv:2108.02731.
Guo, H., Fu, Z., Yang, Z., and Wang, Z. (2021). Decentralized single-timescale actor-critic on zero-sum two-player stochastic games. In Proc. International Conference on Machine Learning (ICML), pages 3899–3909.
Guo, X., Hu, A., Xu, R., and Zhang, J. (2019). Learning mean-field games. Proc. Advances in Neural Information Processing Systems (Neurips), 32:4966–4976.
Hu, J. and Wellman, M. P. (2003). Nash q-learning for general-sum stochastic games. Journal of machine learning research, 4(Nov):1039–1069.
Huang, B., Lee, J. D., Wang, Z., and Yang, Z. (2021). Towards general function approximation in zero-sum markov games. ArXiv:2107.14702.
Jafarnia-Jahromi, M., Jain, R., and Nayyar, A. (2021). Learning zero-sum stochastic games with posterior sampling. ArXiv:2109.03396.
Jin, Y. and Sidford, A. (2021). Towards tight bounds on the sample complexity of average-reward mdps. In Proc. International Conference on Machine Learning (ICML), pages 5055–5064.
Kononen, V. and Oja, E. (2004). Asymmetric multiagent reinforcement learning in pricing applications. In Proc. IEEE International Joint Conference on Neural Networks (IEEE Cat. No. 04CH37541), volume 2, pages 1097–1102.
Leonardos, S., Overman, W., Panageas, I., and Piliouras, G. (2021). Global convergence of multiagent policy gradient in markov potential games. ArXiv:2106.01969.
Liu, B., Yang, Z., and Wang, Z. (2021). Policy optimization in zero-sum markov games: Fictitious self-play provably attains nash equilibria.
Mei, J., Xiao, C., Szepesvari, C., and Schuurmans, D. (2020). On the global convergence rates of softmax policy gradient methods. In Proc. International Conference on Machine Learning (ICML), pages 6820–6829.
Mertikopoulos, P. and Sandholm, W. H. (2016). Learning in games via reinforcement and regularization. Mathematics of Operations Research, 41(4):1297–1324.
Moerland, T. M., Broekens, J., Plaat, A., and Jonker, C. M. (2018). A0c: Alpha zero in continuous action space. ArXiv:1805.09613.
Neu, G., Jonsson, A., and Gómez, V. (2017). A unified view of entropy-regularized markov decision processes. ArXiv:1705.07798.
Ortner, P. and Auer, R. (2007). Logarithmic online regret bounds for undiscounted reinforcement learning. In Proc. Advances in Neural Information Processing Systems (Neurips), volume 19, page 49.
Ortner, R. (2020). Regret bounds for reinforcement learning via markov chain concentration. Journal of Artificial Intelligence Research, 67:115–128.
Paulin, D. (2015). Concentration inequalities for markov chains by marton couplings and spectral methods. Electronic Journal of Probability, 20:1–32.
Savas, Y., Ahmadi, M., Tanaka, T., and Topcu, U. (2019). Entropy-regularized stochastic games. In Proc. IEEE 58th Conference on Decision and Control (CDC), pages 5955–5962.
Shapley, L. S. (1953). Stochastic games. Proceedings of the national academy of sciences, 39(10):1095–1100.
Sidford, A., Wang, M., Yang, L., and Ye, Y. (2020). Solving discounted stochastic two-player games with near-optimal time and sample complexity. In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS), pages 2992–3002.
Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., et al. (2017). Mastering the game of go without human knowledge. nature, 550(7676):354–359.
Sutton, R. S. and Barto, A. G. (2018). Reinforcement learning: An introduction. MIT press.
Tamar, A., Wu, Y., Thomas, G., Levine, S., and Abbeel, P. (2016). Value iteration networks. In Proc. Advances in neural information processing systems (Neurips), pages 2154–2162.
Vinyals, O., Babuschkin, I., Czarnecki, W. M., Mathieu, M., Dudzik, A., Chung, J., Choi, D. H., Powell, R., Ewalds, T., Georgiev, P., et al. (2019). Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782):350–354.
Wang, X. and Sandholm, T. (2002). Reinforcement learning to play an optimal nash equilibrium in team markov games. volume 15, pages 1603–1610.
Wei, C.-Y., Hong, Y.-T., and Lu, C.-J. (2017). Online reinforcement learning in stochastic games. In Proc. Advances in neural information processing systems (Neurips), pages 4994–5004.
Wei, C.-Y., Lee, C.-W., Zhang, M., and Luo, H. (2021). Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizon competitive markov games. In Proc. Conference on Learning Theory (COLT).
Xia, Y., Ding, W., Zhang, X.-D., Yu, N., and Qin, T. (2016). Budgeted bandit problems with continuous random costs. In Proc. Asian conference on machine learning (ACML), pages 317–332.
Xu, Y., Deng, Z., Wang, M., Xu, W., So, A. M.-C., and Cui, S. (2020). Voting-based multiagent reinforcement learning for intelligent iot. IEEE Internet of Things Journal, 8(4):2681–2693.
Zhang, K., Kakade, S., Basar, T., and Yang, L. (2020). Model-based multi-agent rl in zero-sum markov games with near-optimal sample complexity. In Proc. Advances in Neural Information Processing Systems (Neurips), volume 33.
Zhang, K., Yang, Z., Liu, H., Zhang, T., and Basar, T. (2021). Finite-sample analysis for decentralized batch multi-agent reinforcement learning with networked agents. IEEE Transactions on Automatic Control.
Zhang, X., Zhang, K., Miehling, E., and Basar, T. (2019). Non-cooperative inverse reinforcement learning. In Proc. Advances in Neural Information Processing Systems (Neurips), volume 32, pages 9487–9497.
Zhao, Y., Tian, Y., Lee, J. D., and Du, S. S. (2021). Provably efficient policy gradient methods for two-player zero-sum markov games. ArXiv:2102.08903.
Zhu, Y. and Zhao, D. (2020). Online minimax q network learning for two-player zero-sum markov games. IEEE Transactions on Neural Networks and Learning Systems.
Zou, S., Xu, T., and Liang, Y. (2019). Finite-sample analysis for sarsa and q-learning with linear function approximation. ArXiv:1902.02234.
Appendix
Table of Contents A Analysis of stochastic PU (SPU) for entropy-regularized matrix game 13
B Estimation error bounds 18
C Properties of the Duality Gap 25
D Proof of Theorem 1 27
E Proof of Theorem 2 31
F Summary of Comparison of Sample Complexities 34
G Rationality 35
A ANALYSIS OF STOCHASTIC PU (SPU) FOR ENTROPY-REGULARIZED MATRIX GAME
We first consider the following zero-sum entropy regularized matrix game, which can be considered as a simple special case of Markov game with only one state.
max µ∈∆(d1) min ν∈∆(d2)
hτ (µ, ν) := µ >Qν + τH(µ)− τH(ν). (22)
where Q ∈ Rd1×d2 is fixed. The solution (µ∗τ , ν∗τ ) of the above problem, also known as the quantal response equilibrium (QRE), satisfies the following condition (Cen et al., 2021)
µ∗τ ∝ exp(Qν∗τ /τ), ν∗τ ∝ exp(−Q>µ∗τ/τ). (23)
Our stochastic PU (SPU) algorithm for the above matrix game is written as follows, µt+1(a) ∝µt(a)1−ητ exp ( η [ Qνt + δ (1) t ] a ) (24)
νt+1(b) ∝νt(b)1−ητ exp ( − η [ Q>µt + δ (2) t ] b ) (25)
µt+1(a) ∝µt(a)1−ητ exp ( η [ Qνt+1 + δ (1)
t ] a ) (26)
νt+1(b) ∝νt(b)1−ητ exp ( − η [ Q>µt+1 + δ (2) t ] b ) , (27)
where δ(1)t is an additive noise to the underlying true quantity Qνt, and the other noises δ (2) t , δ
(1) t ,
δ (2)
t are similar. If all these noises are zero, the above stochastic PU algorithm reduces to the PU algorithm for matrix game defined in Section 2 of (Cen et al., 2021).
The convergence rate of stochastic PU for matrix game is shown below. The proof logic follows from that of (Cen et al., 2021).
Lemma 1. Choose learning rate η ≤ [ 2(τ + ‖Q‖∞) ]−1 and use the uniform policy initialization µ0 = 1/d1, ν0 = 1/d2. Then, the SPU algorithm defined by eqs. (24)-(27) for entropy-regularized matrix game has the following convergence rates.
KL(µ∗τ‖µt) +KL(ν∗τ ‖νt) ≤ (1− ητ)t ln(d1d2)
+ t−1∑ j=0 (1− ητ)t−1−j [ 2η2 ( ‖δ(1)j ‖ 2 ∞ + ‖δ (2) j ‖ 2 ∞ ) + 2η τ ( ‖δ(1)j ‖2∞ + ‖δ (2) j ‖2∞ )] . (28)∣∣hτ (µ?τ , ν?τ )− hτ (µt+1, νt+1)∣∣
≤ 4 η (1− ητ)t ln(d1d2)
+ t∑ j=0 (1− ητ)t−1−j [ 8η ( ‖δ(1)j ‖ 2 ∞ + ‖δ (2) j ‖ 2 ∞ ) + 33 4τ ( ‖δ(1)j ‖2∞ + ‖δ (2) j ‖2∞ )] . (29)
max µ∈∆(d1) hτ (µ, νt+1)− min ν∈∆(d2) hτ (µt+1, ν)
≤ 2 η (1− ητ)t ln(d1d2)
+ t∑ j=0 (1− ητ)t−1−j [ 16η ( ‖δ(1)j ‖ 2 ∞ + ‖δ (2) j ‖ 2 ∞ ) + 12 τ ( ‖δ(1)j ‖2∞ + ‖δ (2) j ‖2∞ )] . (30)
Proof. Eq. (26) implies that for some constant c ∈ R,
lnµt+1 = (1− ητ) lnµt + η(Qνt+1 + δ (1) t ) + c1 ⇒ 〈 lnµt+1 − (1− ητ) lnµt − η(Qνt+1 + δ (1) t ), µt+1 − µ∗τ 〉 = 0. (31)
where we used 〈µt+1 − µ∗τ ,1〉 = 0. Similarly, eqs. (27)&(23) respectively imply that〈 ln νt+1 − (1− ητ) ln νt + η(Q>µt+1 + δ (2) t ), νt+1 − ν∗τ 〉
=0 (32)〈 lnµ∗τ −Qν∗τ /τ, µt+1 − µ∗τ 〉 =0 (33)〈
ln ν∗τ +Q >µ∗τ/τ, νt+1 − ν∗τ
〉 =0. (34)
Similarly, eqs. (24)&(26) imply that〈 ln(µt+1/µt+1), µt+1 − µt+1 〉 = 〈 η [ Q(νt − νt+1) + δ(1)t − δ (1) t ] , µt+1 − µt+1
〉 ≤ η‖Q‖∞‖µt+1 − µt+1‖1‖νt − νt+1‖1 + η‖δ (1) t − δ (1) t ‖∞‖µt+1 − µt+1‖1
≤ η 2 ‖Q‖∞
( ‖µt+1 − µt+1‖21 + ‖νt − νt+1‖21 ) +
η2
2(1− η‖Q‖∞) ‖δ(1)t − δ
(1) t ‖2∞
+ 1
2 (1− η‖Q‖∞)‖µt+1 − µt+1‖21
(i) ≤ KL(µt+1‖µt+1) + η‖Q‖∞KL(νt+1‖νt) + 2η2 ( ‖δ(1)t ‖2∞ + ‖δ (1) t ‖2∞ ) , (35)
where (i) uses the Pinsker’s inequality and η ≤ [ 2(τ + ‖Q‖∞) ]−1 .
Similarly to the above derivation, we can infer from eqs. (25)&(27) that〈 ln(νt+1/νt+1), νt+1 − νt+1 〉 ≤KL(νt+1‖νt+1) + η‖Q‖∞KL(µt+1‖µt)
+ 2η2 ( ‖δ(2)t ‖2∞ + ‖δ (2) t ‖2∞ ) . (36)
Computing eq. (31)+eq. (32)-ητ [eq. (33)+eq. (34)] yields that η〈δ(1)t , µt+1 − µ∗τ 〉 − η〈δ(2)t , νt+1 − ν∗τ 〉 = 〈 lnµt+1 − (1− ητ) lnµt − ητ lnµ∗τ − ηQ(νt+1 − ν∗τ ), µt+1 − µ∗τ 〉
+ 〈 ln νt+1 − (1− ητ) ln νt − ητ ln ν∗τ + ηQ>(µt+1 − µ∗τ ), νt+1 − ν∗τ 〉
= 〈
ln(µt+1/µ ∗ τ )− (1− ητ) ln(µt/µ∗τ ), µt+1 − µ∗τ
〉
+ 〈
ln(νt+1/ν ∗ τ )− (1− ητ) ln(νt/ν∗τ ), νt+1 − ν∗τ 〉 =KL(µ∗τ‖µt+1)− (1− ητ)KL(µ∗τ‖µt)
+ 〈
ln(µt+1/µ ∗ τ )− ln(µt+1/µt+1)− (1− ητ) [ ln(µt+1/µ ∗ τ )− ln(µt+1/µt) ] , µt+1 〉 +KL(ν∗τ ‖νt+1)− (1− ητ)KL(ν∗τ ‖νt) + 〈
ln(νt+1/ν ∗ τ )− ln(νt+1/νt+1)− (1− ητ) [ ln(νt+1/ν ∗ τ )− ln(νt+1/νt) ] , νt+1 〉 =KL(µ∗τ‖µt+1)− (1− ητ)KL(µ∗τ‖µt) + ητKL(µt+1‖µ∗τ )
+ (1− ητ)KL(µt+1‖µt) +KL(µt+1‖µt+1) +KL(ν∗τ ‖νt+1)− (1− ητ)KL(ν∗τ ‖νt) + ητKL(νt+1‖ν∗τ ) + (1− ητ)KL(νt+1‖νt) +KL(νt+1‖νt+1) − 〈 ln(µt+1/µt+1), µt+1 − µt+1 〉 − 〈 ln(νt+1/νt+1), νt+1 − νt+1 〉
(i) ≥KL(µ∗τ‖µt+1)− (1− ητ)KL(µ∗τ‖µt) + ητKL(µt+1‖µ∗τ ) + (1− ητ − η‖Q‖∞)KL(µt+1‖µt) +KL(ν∗τ ‖νt+1)− (1− ητ)KL(ν∗τ ‖νt) + ητKL(νt+1‖ν∗τ ) + (1− ητ − η‖Q‖∞)KL(νt+1‖νt)
− 2η2 ( ‖δ(1)t ‖2∞ + ‖δ (1) t ‖2∞ + ‖δ (2) t ‖2∞ + ‖δ (2) t ‖2∞ ) , (37)
where (i) uses eqs. (35)&(36). The left side of the above inequality has the following upper bound. η〈δ(1)t , µt+1 − µ∗τ 〉 − η〈δ(2)t , νt+1 − ν∗τ 〉 ≤η‖δ(1)t ‖∞‖µt+1 − µ∗τ‖1 + η‖δ (2) t ‖∞‖νt+1 − ν∗τ ‖1
≤η 2 (2‖δ(1)t ‖2∞ τ + τ 2 ‖µt+1 − µ∗τ‖21 + 2‖δ(2)t ‖2∞ τ + τ 2 ‖νt+1 − ν∗τ ‖21 ) ≤η τ ( ‖δ(1)t ‖2∞ + ‖δ (2) t ‖2∞ ) + ητ 2 ( KL(µt+1‖µ∗τ ) +KL(νt+1‖ν∗τ ) ) . (38)
Substituting eq. (38) into eq. (37) and rearranging it yields that
KL(µ∗τ‖µt+1) +KL(ν∗τ ‖νt+1) + ητ
2
[ KL(µt+1‖µ∗τ ) +KL(νt+1‖ν∗τ ) ] + 1
2
[ KL(µt+1‖µt) +KL(νt+1‖νt) ] ≤ (1− ητ) [ KL(µ∗τ‖µt) +KL(ν∗τ ‖νt) ] + 2η2 ( ‖δ(1)t ‖2∞ + ‖δ (2) t ‖2∞
) + 2η
τ
( ‖δ(1)t ‖2∞ + ‖δ (2) t ‖2∞ ) , (39)
where we use η ≤ [ 2(τ + ‖Q‖∞) ]−1 ≤ (2τ)−1. This further implies that KL(µ∗τ‖µt+1) +KL(ν∗τ ‖νt+1) ≤ (1− ητ) [ KL(µ∗τ‖µt) +KL(ν∗τ ‖νt)
] + 2η2 ( ‖δ(1)t ‖2∞ + ‖δ (2) t ‖2∞ ) + 2η
τ
( ‖δ(1)t ‖2∞ + ‖δ (2) t ‖2∞ ) . (40)
Consequently, eq. (28) can be proved via iterating the above inequality and using the facts that KL(µ∗τ‖µ0) ≤ ln d1, KL(ν∗τ ‖ν0) ≤ ln d2 (Since µ0 and ν0 are uniform probability vectors). Next, we will prove eq. (29).
Computing eq. (31) −ητ ·eq. (33) yields that 〈Q(νt+1 − ν∗τ ), µt+1 − µ∗τ 〉
= η−1 〈 lnµt+1 − (1− ητ) lnµt − ητ lnµ∗τ − ηδ (1) t , µt+1 − µ∗τ 〉 . (41)
Hence, we conclude that
hτ (µt+1, νt+1)− hτ (µ?τ , ν?τ ) ≤ hτ (µt+1, νt+1)− hτ (µt+1, ν?τ )
= µ>t+1Q(νt+1 − ν?τ ) + τν>t+1 ln νt+1 − τν?>τ ln ν?τ = (µt+1 − µ?τ )>Q(νt+1 − ν?τ ) + µ?>τ Q(νt+1 − ν?τ ) + τν>t+1 ln νt+1 − τν?>τ ln ν?τ (i) = η−1 〈 lnµt+1 − (1− ητ) lnµt − ητ lnµ∗τ − ηδ (1) t , µt+1 − µ∗τ 〉 − τ 〈 ln ν∗τ , νt+1 − ν∗τ 〉
+ τν>t+1 ln νt+1 − τν?>τ ln ν?τ (ii) = η−1 [ KL(µ∗τ‖µt+1)− (1− ητ)KL(µ∗τ‖µt) + ητKL(µt+1‖µ∗τ ) + (1− ητ)KL(µt+1‖µt)
+KL(µt+1‖µt+1)− 〈 ln(µt+1/µt+1), µt+1 − µt+1 〉] + τKL(νt+1‖ν?τ )− 〈δ (1) t , µt+1 − µ∗τ 〉
≤ η−1 [ KL(µ∗τ‖µt+1)− (1− ητ)KL(µ∗τ‖µt) + ητ ( KL(µt+1‖µ∗τ ) +KL(νt+1‖ν?τ ) ) + (1− ητ)KL(µt+1‖µt)−KL(µt+1‖µt+1) ] + 1
2τ ‖δ(1)t ‖2∞ +
τ 2 ‖µt+1 − µ∗τ‖21
(iii) ≤ η−1 [ KL(µ∗τ‖µt+1) + 2ητ ( KL(µt+1‖µ∗τ ) +KL(νt+1‖ν?τ ) ) +KL(µt+1‖µt) ] + 1
4τ ‖δ(1)t ‖2∞
(iv) ≤ 4η−1 [ KL(µ∗τ‖µt) +KL(ν∗τ ‖νt) + 2η2 ( ‖δ(1)t ‖2∞ + ‖δ (2) t ‖2∞ ) + 2η
τ
( ‖δ(1)t ‖2∞ + ‖δ (2) t ‖2∞ )]
+ 1 4τ ‖δ(1)t ‖2∞
(v) ≤ 4η−1 [ KL(µ∗τ‖µt) +KL(ν∗τ ‖νt) ] + 8η ( ‖δ(1)t ‖2∞ + ‖δ (2) t ‖2∞ ) + 33
4τ
( ‖δ(1)t ‖2∞ + ‖δ (2) t ‖2∞ ) , (42)
where (i) uses eq. (41)&(34), (ii) follows the derivation of eq. (37), (iii) uses the Pinsker’s inequality, (iv) uses eq. (39), and (v) uses η ≤ [ 2(τ + ‖Q‖∞) ]−1 . In a similar way, we can also prove that
hτ (µ ? τ , ν ? τ )− hτ (µt+1, νt+1) ≤ hτ (µ?τ , νt+1)− hτ (µt+1, νt+1) ≤ 4η−1 [ KL(µ∗τ‖µt) +KL(ν∗τ ‖νt) ] + 8η ( ‖δ(1)t ‖2∞ + ‖δ (2) t ‖2∞ ) + 33
4τ
( ‖δ(1)t ‖2∞ + ‖δ (2) t ‖2∞ ) . (43)
Combining eqs. (42)&(43) yields that∣∣hτ (µ?τ , ν?τ )− hτ (µt+1, νt+1)∣∣ ≤ 4η−1 [ KL(µ∗τ‖µt) +KL(ν∗τ ‖νt) ] + 8η ( ‖δ(1)t ‖2∞ + ‖δ (2) t ‖2∞ ) + 33
4τ
( ‖δ(1)t ‖2∞ + ‖δ (2) t ‖2∞ )
(i) ≤ 4η−1(1− ητ)t ln(d1d2)
+ t−1∑ j=0 (1− ητ)t−1−j [ 8η ( ‖δ(1)j ‖ 2 ∞ + ‖δ (2) j ‖ 2 ∞ ) + 8 τ ( ‖δ(1)j ‖2∞ + ‖δ (2) j ‖2∞ )]
+ 8η ( ‖δ(1)t ‖2∞ + ‖δ (2) t ‖2∞ ) + 33
4τ
( ‖δ(1)t ‖2∞ + ‖δ (2) t ‖2∞ )
≤ 4η−1(1− ητ)t ln(d1d2)
+ t∑ j=0 (1− ητ)t−1−j [ 8η ( ‖δ(1)j ‖ 2 ∞ + ‖δ (2) j ‖ 2 ∞ ) + 33 4τ ( ‖δ(1)j ‖2∞ + ‖δ (2) j ‖2∞ )] ,
where (i) uses eq. (28). This proves eq. (29).
Next, to prove the duality gap (30), we first derive an upper bound ofKL(µ?τ‖µt+1)+KL(ν?τ ‖νt+1). KL(ν?τ ‖νt+1) =KL(ν?τ ‖νt+1)−KL(νt+1‖νt+1) + 〈 νt+1 − ν?τ , ln νt+1 − ln νt+1
〉 ≤KL(ν?τ ‖νt+1) + 〈 νt+1 − ν?τ , ηQ>(µt+1 − µt) + η(δ (2) t − δ (2) t ) 〉
≤KL(ν?τ ‖νt+1) + ‖νt+1 − ν?τ ‖1 ( η‖Q‖∞‖µt+1 − µt‖1 + η‖δ (2) t − δ (2) t ‖∞ )
≤KL(ν?τ ‖νt+1)
+ 1
2
[( η‖Q‖∞ + 1
4
) ‖νt+1 − ν?τ ‖21 + η‖Q‖∞‖µt+1 − µt‖21 + 4η2‖δ (2) t − δ (2) t ‖2∞ ] (i) ≤KL(ν?τ ‖νt+1) + 3
4 KL(ν?τ ‖νt+1) +
1 2 KL(µt+1‖µt) + 4η2
( ‖δ(2)t ‖2∞ + ‖δ (2) t ‖2∞ ) , (44)
where (i) uses the Pinker’s inequality and η ≤ [ 2(τ + ‖Q‖∞) ]−1 . Rearranging the above inequality yields that
KL(ν?τ ‖νt+1) ≤4KL(ν?τ ‖νt+1) + 2KL(µt+1‖µt) + 16η2 ( ‖δ(2)t ‖2∞ + ‖δ (2) t ‖2∞ ) . (45)
Similarly, we can prove that
KL(µ?τ‖µt+1) ≤4KL(µ?τ‖µt+1) + 2KL(νt+1‖νt) + 16η2 ( ‖δ(1)t ‖2∞ + ‖δ (1) t ‖2∞ ) . (46)
Summing up eqs. (45)&(46) yields that
KL(µ?τ‖µt+1) +KL(ν?τ ‖νt+1) ≤ 4 [ KL(µ∗τ‖µt+1) +KL(ν∗τ ‖νt+1) ] + 2 [ KL(µt+1‖µt) +KL(νt+1‖νt) ] + 16η2 ( ‖δ(1)t ‖2∞ + ‖δ (1) t ‖2∞ + ‖δ (2) t ‖2∞ + ‖δ (2) t ‖2∞ )
(i) ≤ 4 [ KL(µ∗τ‖µt) +KL(ν∗τ ‖νt) ] + 24η2 ( ‖δ(1)t ‖2∞ + ‖δ (2) t ‖2∞ ) + 16η
τ
( ‖δ(1)t ‖2∞ + ‖δ (2) t ‖2∞ ) , (47)
where (i) uses eq. (39) and η ≤ [ 2(τ + ‖Q‖∞) ]−1 ≤ (2τ)−1. Finally, we prove the duality gap bound (30).
hτ (µ ? τ , ν ? τ )− hτ (µ, ν?τ ) = (µ?τ − µ)>Qν?τ + τµ> lnµ− τµ?>τ lnµ?τ
(i) = τ(〈µ?τ − µ, lnµ?τ 〉+ µ> lnµ− µ?>τ lnµ?τ ) = τKL(µ‖µ?τ ), (48)
where (i) uses eq. (33).
hτ (µ, νt+1)− hτ (µ, ν?τ ) = µ>Q(νt+1 − ν?τ ) + τν>t+1 ln νt+1 − τν?>τ ln ν?τ = (µ− µ?τ )>Q(νt+1 − ν?τ ) + µ?>τ Q(νt+1 − ν?τ ) + τν>t+1 ln νt+1 − τν?>τ ln ν?τ (i)
≤ ‖µ− µ?τ‖1‖Q‖∞‖νt+1 − ν?τ ‖1 − τ 〈 ln ν∗τ , νt+1 − ν∗τ 〉 + τν>t+1 ln νt+1 − τν?>τ ln ν?τ
≤ 1 2
[ τ‖µ− µ?τ‖21 + ‖Q‖2∞‖νt+1 − ν?τ ‖21/τ ] + τKL(νt+1‖ν?τ )
(ii)
≤ τKL(µ‖µ?τ ) + τKL(νt+1‖ν?τ ) + τ−1‖Q‖2∞KL(ν?τ ‖νt+1), (49)
where (i) uses eq. (34) and (ii) uses the Pinsker’s inequality. Then, eq. (49) & eq. (48) imply that
hτ (µ, νt+1)− hτ (µ?τ , ν?τ ) ≤ τKL(νt+1‖ν?τ ) + τ−1‖Q‖2∞KL(ν?τ ‖νt+1), (50)
where (i) uses eq. (45), (ii) uses the Pinker’s inequality and η ≤ [ 2(τ + ‖Q‖∞) ]−1 .
Similarly, it can be proved that
hτ (µ ? τ , ν ? τ )− hτ (µt+1, ν) ≤ τKL(µt+1‖µ?τ ) + τ−1‖Q‖2∞KL(µ?τ‖µt+1). (51)
Therefore, the duality gap (30) can be proved as follows.
max µ∈∆(d1) hτ (µ, νt+1)− min ν∈∆(d2) hτ (µt+1, ν)
= max µ∈∆(d1),ν∈∆(d2)
[ hτ (µ, νt+1)− hτ (µt+1, ν) ]
(i) ≤ τ [KL(µt+1‖µ?τ ) +KL(νt+1‖ν?τ )] + τ−1‖Q‖2∞[KL(µ?τ‖µt+1) +KL(ν?τ ‖νt+1)] (ii)
≤ τ [KL(µt+1‖µ?τ ) +KL(νt+1‖ν?τ )] + τ−1‖Q‖2∞[ 4 [ KL(µ∗τ‖µt) +KL(ν∗τ ‖νt) ] + 24η2 ( ‖δ(1)t ‖2∞ + ‖δ (2) t ‖2∞ ) + 16η
τ
( ‖δ(1)t ‖2∞ + ‖δ (2) t ‖2∞ )]
(iii) ≤ max (2 η , 4‖Q‖2∞ τ ) [ KL(µ∗τ‖µt) +KL(ν∗τ ‖νt) + 2η2 ( ‖δ(1)t ‖2∞ + ‖δ (2) t ‖2∞ ) + 2η
τ
( ‖δ(1)t ‖2∞ + ‖δ (2) t ‖2∞ )]
+ τ−1‖Q‖2∞ [ 24η2 ( ‖δ(1)t ‖2∞ + ‖δ (2) t ‖2∞ ) + 16η
τ
( ‖δ(1)t ‖2∞ + ‖δ (2) t ‖2∞ )]
(iv)
≤ 2 η
( (1− ητ)t ln(d1d2)
+ t−1∑ j=0 (1− ητ)t−1−j [ 2η2 ( ‖δ(1)j ‖ 2 ∞ + ‖δ (2) j ‖ 2 ∞ ) + 2η τ ( ‖δ(1)j ‖2∞ + ‖δ (2) j ‖2∞ )])
+ 16η ( ‖δ(1)t ‖2∞ + ‖δ (2) t ‖2∞ ) + 12
τ
( ‖δ(1)t ‖2∞ + ‖δ (2) t ‖2∞ )
≤ 2 η (1− ητ)t ln(d1d2)
+ t∑ j=0 (1− ητ)t−1−j [ 16η ( ‖δ(1)j ‖ 2 ∞ + ‖δ (2) j ‖ 2 ∞ ) + 12 τ ( ‖δ(1)j ‖2∞ + ‖δ (2) j ‖2∞ )] , (52)
where (i) adds up eqs. (50) & (51), (ii) uses eq. (47), (iii) uses eq. (39), and (iv) uses eq. (28) and 4τ−1‖Q‖2∞ ≤ 2/η (since η ≤ [ 2(τ + ‖Q‖∞) ]−1 , τ ≤ 1). This proves eq. (30)
B ESTIMATION ERROR BOUNDS
In this section, we derive error bounds for the estimators V̂k+1 ≈ V ′k+1, Q̂ (m) k,t ≈ Q (m) k,t , Q̂
(m) k,t ≈ Q (m) k,t
used in Algorithm 1. For convenience, we define the following additional notations.
µ̂k(s) := 1
Nk+1 ∑ i∈Nk+1 1{si = s} ≈ µk(s) (53)
vk+1(s) := Eµk,π(1)k ,π(2)k
[[ R(s̃, ã(1), ã(2)) + γV ′k(s ′) ] 1{s̃ = s} ] (54)
v′k+1(s) := Eµk,π(1)k ,π(2)k
[[ R(s̃, ã(1), ã(2)) + γV̂k(s ′) ] 1{s̃ = s} ] (55)
v̂k+1(s) := 1
Nk+1 ∑ i∈Nk+1 [[ Ri + γV̂k(si+1) ] 1{si = s} ] ≈ v′k+1(s) ≈ vk+1(s) (56)
Qk(s, a (1), a(2)) := R(s, a(1), a(2)) + γEs′∼P(·|s,a(1),a(2)) [ V ′k(s ′) ]
(57)
V ′k+1(s) = fτ ( Qk(s);π (1) k (s), π (2) k (s) ) = vk+1(s)
µk(s) + τH
( π
(1) k (s)
) − τH ( π
(2) k (s)
) (58)
V̂k+1(s) := v̂k+1(s)
µ̂k(s) + τH
( π
(1) k (s)
) − τH ( π
(2) k (s) ) ≈ V ′k+1(s) (59)
µ̂k,t(s) := 1
Nk,t ∑ i∈Nk,t 1{si = s} ≈ µ′k,t(s) ≈ µk,t(s), (60)
q (m) k,t (s, a (m)) := E µ′k,t,π ′(1) k,t ,π ′(2) k,t
[[ R(s̃, ã(1), ã(2)) + γV ′k(s ′) ] 1{s̃ = s, ã(m) = a(m)} ] (61)
q ′(m) k,t (s, a (m)) := E µ′k,t,π ′(1) k,t ,π ′(2) k,t
[[ R(s̃, ã(1), ã(2)) + γV̂k(s ′) ] 1{s̃ = s, ã(m) = a(m)} ] (62)
q̂ (m) k,t (s, a
(m)) := 1
Nk,t ∑ i∈Nk,t [[ Ri + γV̂k(si+1) ] 1{si = s, a(m)i = a (m)} ]
≈ q′(m)k,t (s, a (m)) ≈ q(m)k,t (s, a (m)) (63)
Q ′(m) k,t (s, a (m)) := E a(\m)∼π′(\m)k,t (s)
[ Qk(s, a (1), a(2)) ] = q (m) k,t (s, a (m))
µ′k,t(s)π ′(m) k,t (a
(m)|s) (64)
Q̂ (m) k,t (s, a
(m)) := q̂
(m) k,t (s, a (m))
µ̂k,t(s)π ′(m) k,t (a
(m)|s) ≈ Q′(m)k,t (s, a (m)) ≈ Q(m)k,t (s, a (m)), (65)
where eqs. (53)-(59) and (60)-(65) are introduced for the description and error bound proof of the estimations V̂k+1 ≈ V ′k+1 and Q̂ (m) k,t ≈ Q (m) k,t , respectively. Specifically, eq. (53) estimates the stationary state distribution µk associated with the policy pair π (1) k , π (2) k using state frequency µ̂k(s). In eqs. (54)&(55), the expectation is taken over s̃ ∼ µk, ã(1) ∼ π(1)k (s), ã(2) ∼ π (2) k (s), s
′ ∼ P(·|s̃, ã(1), ã(2)). The definition of E
µ′k,t,π ′(1) k,t ,π ′(2) k,t
in eqs. (61)&(62) is similar. Equations (58)
& (64) give two equivalent definitions of V ′k+1 and Q ′(m) k,t (s, a (m)), respectively 1 (We will prove the equivalence in Lemma 2 below). Equation (60) estimates the stationary state distribution µ′k,t associated with the smoothed policy pair π′(1)k,t , π ′(2) k,t , and thus approximates the stationary state distribution µk,t associated with the current policy pair π (1) k,t , π (2) k,t .
To prove the estimation error bounds, we first prove the following two lemmas.
Lemma 2. Eq. (13) and the second “=” of eqs. (58) & (64) hold for all s, a(1), a(2).
Proof. The second “=” of eq. (64) under m = 1 can be proved as follows.
q (1) k,t (s, a (1))
(i) = E
µ′k,t,π ′(1) k,t ,π ′(2) k,t
[[ R(s̃, ã(1), ã(2)) + γV ′k(s ′) ] 1{s̃ = s, ã(m) = a(m)} ] = E
s̃∼µ′k,t,ã(1)∼π ′(1) k,t (s),ã (2)∼π′(2)k,t (s),s′∼P(·|s,a(1),ã(2))[[ R(s, a(1), ã(2)) + γV ′k(s ′) ] 1{s̃ = s, ã(1) = a(1)} ] (ii) = E
s̃∼µ′k,t,ã(1)∼π ′(1) k,t (s)
[ 1{s̃ = s, ã(1) = a(1)} ] E ã(2)∼π′(2)k,t (s),s′∼P(·|s,a(1),ã(2)) [ R(s, a(1), ã(2)) + γV ′k(s ′) ]
(iii) = µ′k,t(s)π ′(1) k,t (a (1)|s)E ã(2)∼π′(2)k,t (s)
[ Qk(s, a (1), ã(2)) ]
(iv) = µ′k,t(s)π ′(1) k,t (a (1)|s)Q′k,t(s, a(1)),
where (i) uses eq. (61) which denotes E µ′k,t,π ′(1) k,t ,π ′(2) k,t
as expectation over s̃ ∼ µ′k,t, ã(1) ∼ π ′(1) k,t (s̃),
ã(2) ∼ π′(2)k,t (s̃), s′ ∼ P(·|s̃, ã(1), ã(2)), (ii) uses independence between s̃ ∼ µ′k,t, ã(1) ∼ π ′(1) k,t (s) and ã(2) ∼ π′(2)k,t (s), s′ ∼ P(·|s, a(1), ã(2)), (iii) uses eq. (57), and (iv) uses the first definition of eq. (64). The second “=” of eq. (64) under m = 2 and eq. (13) can be proved in a similar way.
The second “=” of eq. (58) can be proved as follows.
vk+1(s)
(i) = E
µk,π (1) k ,π (2) k
[[ R(s̃, ã(1), ã(2)) + γV ′k(s ′) ] 1{s̃ = s} ] = E
s̃∼µk,ã(1)∼π(1)k (s),ã(2)∼π (2) k (s),s ′∼P(·|s,ã(1),ã(2))
[[ R(s, ã(1), ã(2)) + γV ′k(s ′) ] 1{s̃ = s} ] 1The definition after the second “=” of eq. (58) is the same as eq. (11)
(ii) = Es̃∼µk
[ 1{s̃ = s} ] E ã(1)∼π(1)k (s),ã(2)∼π (2) k (s),s ′∼P(·|s,ã(1),ã(2)) [ R(s, ã(1), ã(2)) + γV ′k(s ′) ]
(iii) = µk(s)Eã(1)∼π(1)k (s),ã(2)∼π(2)k (s)
[ Qk(s, ã (1), ã(2)) ]
= µk,t(s) [ fτ ( Qk(s);π (1) k (s), π (2) k (s) ) − τH ( π (1) k (s) ) + τH ( π (2) k (s) )] (iv) = µk(s) [ V ′k+1(s)− τH ( π (1) k (s) ) + τH ( π (2) k (s)
)] where (i) uses eq. (54), (ii) uses independence between s′ ∼ µk and ã(1) ∼ π(1)k (s), ã(2) ∼ π
(2) k (s), s ′ ∼ P(·|s, ã(1), ã(2)), (iii) uses eq. (57), and (iv) uses eq. (58).
Lemma 3. If ‖V̂0‖∞ ≤ Vmax := 1+τ lnAmax1−γ , then for all k ≥ 0, 0 ≤ t ≤ Tk − 1, we have
‖V̂k‖∞, ‖V ′k‖∞, ‖V ∗‖∞ ≤ Vmax, (66) |v̂k+1(s)| ≤ 2Vmaxµ̂k(s),∀s ∈ S, (67)
max ( ‖Qk‖∞, ‖Q′(m)k,t ‖∞, ‖Q ∗‖∞ ) ≤ Qmax, (68)
where Qmax := 1 + γVmax = 1+γτ lnAmax1−γ with Amax := max ( |A(1)|, |A(2)| ) .
Proof. We will first prove ‖V̂k‖∞ ≤ Vmax in eq. (66) by induction. Suppose ‖V̂k′‖∞ ≤ Vmax holds for a certain k′ ∈ N. Then, eq. (59) implies that for all s ∈ S,
|V̂k′+1(s)| ≤ ∣∣∣ v̂k′+1(s) µ̂′k′(s) ∣∣∣+ τ[H(π(1)k′ (s))−H(π(2)k′ (s))] ≤ ∑ i∈Nk′+1 [[ |Ri|+ γ|V̂k′(si+1)| ] 1{si = s}
] ∑ i∈Nk′+1 1{si = s} + τ lnAmax
(i) ≤
∑ i∈Nk′+1 [( 1 + γVmax ) 1{si = s} ] ∑ i∈Nk′+1 1{si = s} + τ lnAmax
=1 + γ(1 + τ lnAmax)
1− γ + τ lnAmax = Vmax, (69)
where (i) uses the inequality that 0 ≤ H(π(m)) ≤ ln |A(m)| ≤ lnAmax,∀π(m) ∈ ∆(|A(m)|). Since ‖V̂0‖∞ ≤ Vmax, ‖V̂k‖∞ ≤ Vmax for all k ∈ N. A similar induction yields that ‖V ′k‖∞ ≤ Vmax. Next, we prove ‖V ∗‖∞ ≤ Vmax, ‖Q∗‖∞ ≤ Qmax in eqs. (66) & (68) respectively. Notice that V ∗ and Q∗ have the following relation.
Q∗(s, a(1), a(2)) = R(s, a(1), a(2)) + γEs′∼P(·|s,a(1),a(2))V ∗(s′), V ∗(s) = π∗(1)(s)>Q∗(s)π∗(2)(s) + τ [ H(π∗(1)(s))−H(π∗(2)(s)) ] .
Hence,
‖Q∗‖∞ ≤ 1 + γ‖V ∗‖∞ (70) ‖V ∗‖∞ ≤ ‖Q∗‖∞ + τ lnAmax (71)
Substituting eq. (70) into eq. (71) yields that
‖V ∗‖∞ ≤ 1 + γ‖V ∗‖∞ + τ lnAmax ⇒ ‖V ∗‖∞ ≤ Vmax.
The proof of eq. (66) is finished. Then, substituting ‖V ∗‖∞ ≤ Vmax into eq. (70) proves that ‖Q∗‖∞ ≤ Qmax. Equation (67) can be proved as follows.∣∣∣ v̂k+1(s)
µ̂k(s)
∣∣∣ (i)≤|V̂k+1(s)|+ τ ∣∣H(π(2)k (s))−H(π(1)k (s))∣∣ ≤ Vmax + τ lnAmax (ii)≤ 2Vmax,
where (i) uses eq. (58) and (ii) uses Vmax := 1+τ lnAmax1−γ ≥ τ lnAmax.
Next, we prove eq. (68). It can be easily seen from eqs. (57) & (66) that∣∣Qk(s, a(1), a(2))∣∣ ≤∣∣R(s, a(1), a(2))∣∣+ γEs′∼P(·|s,a(1),a(2))∣∣V ′k(s′)∣∣ ≤ 1 + γVmax = Qmax, which implies that ‖Qk‖∞ ≤ Qmax. Hence,∣∣Q′(m)k,t (s, a(m))∣∣ (i)≤ Ea(\m)∼π′(\m)k,t (s)∣∣Qk(s, a(1), a(2))∣∣ ≤ Qmax where (i) uses eq. (64). This proves eq. (68).
With the above two Lemmas, we can derive the estimation error bounds as follows. Lemma 4. Use hyperparameter choices Nk,t, Nk,t ≥ 650tmixAmaxµmin ln ( 20Tsum|S|Amax δ √ µmin ) and Nk+1 ≥
650tmix µmin(1−γ)2 ln
( 4
δ √ µmin
) in Algorithm 1. Then with probability at least 1 − δ, all the following
bounds hold for all 0 ≤ k ≤ K − 1, 0 ≤ t ≤ Tk − 1, m = 1, 2, s ∈ S, a(m) ∈ A(m), where Tsum := ∑K−1 k=0 Tk.∥∥V̂k − V ′k∥∥∞ ≤ 2Vmaxγk + 171Vmax1− γ √ tmix Nk+1µmin ln ( 4K|S| δ √ µmin
) (72)∥∥Q̂(m)k,t −Q(m)k,t ∥∥∞
≤ Qmax [ 640tmixAmax Nk,tµmin ′ ln (20Tsum|S|Amax δ √ µmin ) + 25 √ tmixAmax Nk,tµmin ′ ln (20Tsum|S|Amax δ √ µmin ) + ′ ] + 2 ∥∥V̂k − V ′k∥∥∞ (73)∥∥Q̂(m)k,t −Q(m)k,t ∥∥∞
≤ Qmax
[ 640tmixAmax
Nk,tµmin ′ ln (20Tsum|S|Amax δ √ µmin ) + 25
√ tmixAmax
Nk,tµmin ′ ln (20Tsum|S|Amax δ √ µmin ) + ′ ] + 2 ∥∥V̂k − V ′k∥∥∞. (74)
More specifically, the upper bounds (73)&(74) can be simplified respectively as follows when ′ =[ 650tmixAmax Nk,tµmin ln ( 20Tsum|S|Amax δ √ µmin )]1/3 and ′ = [ 650tmixAmax Nk,tµmin ln ( 20Tsum|S|Amax δ √ µmin )]1/3 .
∥∥Q̂(m)k,t −Q(m)k,t ∥∥∞ ≤18Qmax[ tmixAmaxNk,tµmin ln (20Tsum|S|Amax δ √ µmin )]1/3 + 2 ∥∥V̂k − V ′k∥∥∞, (75)
∥∥Q̂(m)k,t −Q(m)k,t ∥∥∞ ≤18Qmax [ tmixAmaxNk,tµmin ln (20Tsum|S|Amax δ √ µmin )]1/3 + 2 ∥∥V̂k − V ′k∥∥∞. (76)
Proof. If the initial state distribution of the minibatch Nk,t equals µ′k,t, i.e., sk,t,0 ∼ µ′k,t, then Nk,tq̂ (m) k,t (s, a (m)) := ∑ i∈Nk,t g(si, a (1) i , a (2) i , si+1) (g(si, a (1) i , a (2) i , si+1) := [ Ri +
γV̂k(si+1) ] 1{si = s, a(m)i = a(m)}) and its expectated value Nk,tq ′(m) k,t (s, a
(m)) satisfy the following concentration bound.
Pµ′k,t {∣∣Nk,tq̂(m)k,t (s, a(m))−Nk,tq′(m)k,t (s, a(m))∣∣ ≥ u}
(i) ≤ 2 exp [ − u 2γps
8(Nk,t + 1/γps)Q2maxµ ′ k,t(s)π ′(m) k,t (a (m)|s) + 40uQmax ] (ii)
≤ 2 exp [ − u 2/(2tmix)
8(Nk,t + 2tmix)Q2maxµ ′ k,t(s)π ′(m) k,t (a (m)|s) + 40uQmax
] , (77)
where Pµ′k,t is under the initial state distribution µ ′ k,t, (i) uses Theorem 3.4 of (Paulin, 2015) and the inequalities that ∣∣g(si, a(1)i , a(2)i , si+1) − Esi∼µ′k,tg(si, a(1)i , a(2)i , si+1)∣∣ ≤ 2(1 +
γVmax) = 2Qmax (Based on Lemma 3) and that varsi∼µ′k,t [ g(si, a (1) i , a (2) i , si+1) ] ≤
Esi∼µ′k,t [[ Ri + γV ′ k(si+1) ]2 1{si = s, a(m)i = a(m)} ] ≤ (1 + γVmax)2µ′k,t(s)π ′(m) k,t (a (m)|s) = Q2maxµ ′ k,t(s)π ′(m) k,t (a
(m)|s), (ii) uses Proposition 3.4 of (Paulin, 2015) which states that the pseudo spectral gap γps has a lower bound 1/(2tmix) for any uniformly ergodic Markov chain (This condition holds for our MDP with finitely many states and actions). Then, for any initial state distribution st,k,0 ∼ ξ, Proposition 3.10 of (Paulin, 2015) implies that
Pξ {∣∣Nk,tq̂(m)k,t (s, a(m))−Nk,tq′(m)k,t (s, a(m))∣∣ ≥ u} ≤ √ Es∼ξ
[ ξ(s) µ′k,t(s) ] Pµ′k,t {∣∣Nk,tq̂(m)k,t (s, a(m))−Nk,tq′(m)k,t (s, a(m))∣∣ ≥ u} (i)
≤ √ 1
µmin exp
[ − u 2/(4tmix)
8(Nk,t + 2tmix)Q2maxµ ′ k,t(s)π ′(m) k,t (a (m)|s) + 40uQmax
] , (78)
where (i) uses eq. (77) and the inequality that Es∼ξ [
ξ(s) µ′k,t(s) ] ≤ 1µmin .
In a similar way, the following concentration bound can be proved for Nk,tµ̂k,t(s) :=∑ i∈Nk,t 1{si = s} and Nk,tµ ′ k,t(s) = Eµ′k,t [ Nk,tµ̂k,t(s) ] .
Pξ {∣∣Nk,tµ̂k,t(s)−Nk,tµ′k,t(s)∣∣ ≥ u} ≤√ 1µmin exp [ − u 2/(4tmix) 8(Nk,t + 2tmix)µ′k,t(s) + 40u ] , (79)
where we use the inequalities that varµ′k,t1{si = s} ≤ µ ′ k,t(s) and that ∣∣1{si = s} − Eµ′k,t1{si = s} ∣∣ ≤ 1. Letting the right hand sides of eqs. (78)&(79) be upper bounded by δ/4 and applying the union bound yields that, with probability at least 1−δ/2, the following two inequalities simultaneously hold. ∣∣q̂(m)k,t (s, a(m))− q′(m)k,t (s, a(m))∣∣
≤ 160Qmax Nk,t tmix ln ( 4 δ √ µmin ) +
6Qmax√ Nk,t
√ tmix(1 + 2tmix/Nk,t)µ′k,t(s)π ′(m) k,t (a (m)|s) ln ( 4 δ √ µmin ) , (80)∣∣µ̂k,t(s)− µ′k,t(s)∣∣
≤ 160 Nk,t tmix ln ( 4 δ √ µmin ) +
6√ Nk,t
√ tmix(1 + 2tmix/Nk,t)µ′k,t(s) ln ( 4 δ √ µmin ) (i) ≤ 1 2 µ′k,t(s), (81)
where (i) holds since Nk,t ≥ 650tmixAmaxµmin ln ( 20Tsum|S|Amax δ √ µmin ) ≥ 650tmix and µ′k,t(s) ≥ µmin.
Similarly, it can be proved that the following two inequalities holds with probability at least 1− δ/2.∣∣v̂k+1(s)− v′k+1(s)∣∣ ≤ 160Qmax
Nk+1 tmix ln ( 4 δ √ µmin ) + 6Qmax√ Nk+1 √ tmix(1 + 2tmix/Nk+1)µk(s) ln ( 4 δ √ µmin ) , (82)∣∣µ̂k(s)− µk(s)∣∣
≤ 160 Nk+1 tmix ln ( 4 δ √ µmin ) + 6√ Nk+1 √ tmix(1 + 2tmix/Nk+1)µk(s) ln ( 4 δ √ µmin ) . (83)
Hence, eqs. (80)-(83) hold with probability at least 1− δ. In this case, we have that∣∣v̂k+1(s)− vk+1(s)∣∣ ≤ ∣∣v̂k+1(s)− v′k+1(s)∣∣+ ∣∣v′k+1(s)− vk+1(s)∣∣
(i) ≤ 160Qmax Nk+1 tmix ln ( 4 δ √ µmin ) + 6Qmax√ Nk+1 √ tmix(1 + 2tmix/Nk+1)µk(s) ln ( 4 δ √ µmin ) + γE
µk,π (1) k ,π (2) k
[[ V̂k(s ′)− V ′k(s′) ] 1{s̃ = s} ] ≤ 160Qmax
Nk+1 tmix ln ( 4 δ √ µmin ) + 6Qmax√ Nk+1 √ tmix(1 + 2tmix/Nk+1)µk(s) ln ( 4 δ √ µmin ) + γmax
s′ ∣∣V̂k(s′)− V ′k(s′)∣∣Eµk1{s̃ = s} ≤ 160Qmax
Nk+1 tmix ln ( 4 δ √ µmin ) + 6Qmax√ Nk+1 √ tmix(1 + 2tmix/Nk+1)µk(s) ln ( 4 δ √ µmin ) + γµk(s)
∥∥V̂k − V ′k∥∥∞, (84) where (i) uses eqs. (54), (55) & (82).
|V̂k+1(s)− V ′k+1(s)| (i) = ∣∣∣ v̂k+1(s) µ̂k(s) − vk+1(s) µk(s) ∣∣∣ ≤ µ−1k (s) ∣∣v̂k+1(s)− vk+1(s)∣∣+ ∣∣v̂k+1(s)∣∣∣∣∣µk(s)− µ̂k(s) µk(s)µ̂k(s)
∣∣∣ (ii)
≤ µ−1k (s) [160Qmax
Nk+1 tmix ln ( 4 δ √ µmin ) + 6Qmax√ Nk+1 √ tmix(1 + 2tmix/Nk+1)µk(s) ln ( 4 δ √ µmin ) + γµk(s) ∥∥V̂k − V ′k∥∥∞]+ 2Vmaxµ−1k (s) [ 160
Nk+1 tmix ln ( 4 δ √ µmin ) +
6√ Nk+1
√ tmix(1 + 2tmix/Nk+1)µk(s) ln ( 4 δ √ µmin ) ] (iii)
≤ γ‖V̂k − V ′k‖∞ + Vmax µk(s) [ 480tmix Nk+1 ln ( 4 δ √ µmin ) + 18 √ tmixµk(s)
Nk+1 (1 + 2tmix/Nk+1) ln ( 4 δ √ µmin ) ] (iv)
≤ γ‖V̂k − V ′k‖∞ + Vmax
[ 24
40tmix Nk+1µmin ln ( 4 δ √ µmin ) + 18 √ 1.05tmix Nk+1µmin ln ( 4 δ √ µmin ) ] (v) ≤ γ‖V̂k − V ′k‖∞ + Vmax [ 24 √ 40tmix Nk+1µmin ln ( 4 δ √ µmin ) + 18 √ 1.05tmix Nk+1µmin ln ( 4 δ √ µmin ) ]
≤ γ‖V̂k − V ′k‖∞ + 171Vmax
√ tmix Nk+1µmin ln ( 4 δ √ µmin ) , (85)
where (i) uses eqs. (58)&(59), (ii) uses eqs. (67), (83)&(84), (iii) uses Qmax ≤ Vmax, (iv) uses µk(s) ≥ µmin and Nk+1 ≥ 40tmixµmin ln
( 4
δ √ µmin ) ≥ 40tmix, and (v) uses Nk+1 ≥ 40tmixµmin ln ( 4 δ √ µmin ) .
Applying the union bound to the above inequality over all 0 ≤ k ≤ K − 1, s ∈ S and taking maximum over s ∈ S, we obtain that with probability at least 1− δ,
‖V̂k+1 − V ′k+1‖∞ ≤γ‖V̂k − V ′k‖∞ + 171Vmax
√ tmix Nk+1µmin ln ( 4 δ √ µmin ) .
Iterating the above inequality yields that with probability at least 1− δ,
‖V̂k − V ′k‖∞ ≤γk‖V̂0 − V ′0‖∞ + 171Vmax
1− γ
√ tmix
Nk+1µmin ln ( 4K|S| δ √ µmin ) (i) ≤2Vmaxγk + 171Vmax
1− γ
√ tmix
Nk+1µmin ln ( 4K|S| δ √ µmin ) , (86)
where (i) uses the fact that ‖V ′0‖∞, ‖V̂0‖∞ ≤ Vmax. Hence, with probability at least 1− 2δ, eqs. (80), (81) & (86) hold simultaneously. In this case,
∣∣Q̂(m)k,t (s, a(m))−Q′(m)k,t (s, a(m))∣∣ (i)= ∣∣∣ q̂(m)k,t (s, a(m)) µ̂k,t(s)π ′(m) k,t (a (m)|s) −
q (m) k,t (s, a (m))
µ′k,t(s)π ′(m) k,t (a (m)|s) ∣∣∣ (ii)
≤ ∣∣q̂(m)k,t (s, a(m))− q(m)k,t (s, a(m))∣∣
µ̂k,t(s)π ′(m) k,t (a (m)|s)
+ |µ′k,t(s)π ′(m) k,t (a (m)|s)Q′(m)k,t (s, a (m))| ∣∣µ̂k,t(s)− µ′k,t(s)∣∣ µ̂k,t(s)µ′k,t(s)π ′(m) k,t (a (m)|s)
(iii) ≤ 2 ∣∣q̂(m)k,t (s, a(m))− q′(m)k,t (s, a(m))∣∣+ 2∣∣q′(m)k,t (s, a(m))− q(m)k,t (s, a(m))∣∣
µ′k,t(s)π ′(m) k,t (a (m)|s)
+ 2Qmax ∣∣µ̂k,t(s)− µ′k,t(s)∣∣ µ′k,t(s)
(iv)
≤ 2Qmax µ′k,t(s)π ′(m) k,t (a (m)|s)
[ 320
Nk,t tmix ln ( 4 δ √ µmin )
+ 12√ Nk,t
√ tmix(1 + 2tmix/Nk,t)µ′k,t(s)π ′(m) k,t (a (m)|s) ln ( 4 δ √ µmin ) ] + 2 ∥∥V̂k − V ′k∥∥∞
(v) ≤ Qmax [ 640tmixAmax Nk,tµmin ′ ln ( 4 δ √ µmin ) + 25 √ tmixAmax Nk,tµmin ′ ln ( 4 δ √ µmin ) ] + 2 ∥∥V̂k − V ′k∥∥∞,
(87)
where (i) uses eqs. (64)&(65), (ii) uses eq. (64), (iii) uses eq. (68) and the inequality that µ̂k,t(s) ≥ µ′k,t(s)/2 implied by (i) of eq. (81), (iv) uses eqs. (80)&(81) and the following inequality based on eqs. (61)&(62), and (v) uses µ′k,t(s) ≥ µmin (based on Assumption 1), π ′(m) k,t (a
(m)|s) = (1 − ′)π
(m) k,t (a (m)|s) + ′/|A(m)| ≥ ′/Amax and Nk,t ≥ 650tmix.∣∣q′(m)k,t (s, a(m))− q(m)k,t (s, a(m))∣∣ ≤ γE
µ′k,t,π ′(1) k,t ,π ′(2) k,t [∣∣V̂k(s′)− V ′k(s′)∣∣1{s̃ = s, ã(m) = a(m)}] ≤ µ′k,t(s)π ′(m) k,t (s, a (m)) ∥∥V̂k − V ′k∥∥∞.
Notice that the following inequality always holds.∣∣Q′(m)k,t (s, a(m))−Q(m)k,t (s, a(m))∣∣ ≤ ∑ a(\m)
∣∣Qk(s, a(1), a(2))∣∣∣∣π′(\m)k,t (a(\m)|s)− π(\m)k,t (a(\m)|s)∣∣ (i)
≤ Qmax ′ ∣∣∣π(\m)k,t (a(\m)|s)− |A(m)|−1∣∣∣ ≤ Qmax ′, (88)
where (i) uses eq. (68).
Hence, combining eqs. (87)&(88), it can be seen that with probability at least 1− 2δ, the following inequality holds∣∣Q̂(m)k,t (s, a(m))−Q(m)k,t (s, a(m))∣∣
≤ Qmax [ 640tmixAmax Nk,tµmin ′ ln ( 4 δ √ µmin ) + 25 √ tmixAmax Nk,tµmin ′ ln ( 4 δ √ µmin ) + ′ ] + 2 ∥∥V̂k − V ′k∥∥∞. (89)
Similarly, it can be proved that with probability at least 1− 2δ,∣∣Q̂(m)k,t (s, a(m))−Q(m)k,t (s, a(m))∣∣ ≤ Qmax [ 640tmixAmax
Nk,tµmin ′ ln ( 4 δ √ µmin ) + 25 √ tmixAmax Nk,tµmin ′ ln ( 4 δ √ µmin ) + ′ ] + 2 ∥∥V̂k − V ′k∥∥∞. (90)
Finally, eqs. (72)-(74) are proved by applying a union bound to eq. (86) and to eqs. (89)&(90) over all 0 ≤ k ≤ T − 1, 0 ≤ t ≤ Tk − 1, m = 1, 2, s ∈ S, a(m) ∈ A(m).
Now we consider the hyperparameter choice ′ = [
650tmixAmax Nk,tµmin
ln (
20Tsum|S|Amax δ √ µmin
)]1/3 . First, this is
a valid choice, since Nk,t ≥ 650tmixAmaxµmin ln ( 20Tsum|S|Amax δ √ µmin ) implies that ′ ∈ [0, 1]. Then, for this ′, the upper bound (73) is simplified as follows.∥∥Q̂(m)k,t −Q(m)k,t ∥∥∞ ≤ Qmax [ 640tmixAmax Nk,tµmin ′ ln (20Tsum|S|Amax δ √ µmin ) + 25 √ tmixAmax Nk,tµmin ′ ln (20Tsum|S|Amax δ √ µmin ) + ′
] + 2 ∥∥V̂k − V ′k∥∥∞
(i) ≤ Qmax (640
650 ′2 + 25√ 650
′ ) + 2 ∥∥V̂k − V ′k∥∥∞
(ii) ≤ 2Qmax ′ + 2 ∥∥V̂k − V ′k∥∥∞ = 18Qmax[ tmixAmaxNk,tµmin ln (20Tsum|S|Amax δ √ µmin )]1/3 + 2 ∥∥V̂k − V ′k∥∥∞,
where (i) uses tmixAmaxNk,tµmin ln ( 20Tsum|S|Amax δ √ µmin ) = ′3/650, and (ii) uses ′ ∈ [0, 1]. This proves eq. (75). The proof of eq. (76) is similar.
C PROPERTIES OF THE DUALITY GAP
In this section, we prove some useful properties of the duality gap
D(τ)(π(1), π(2)) := max s,π′(1),π′(2)
[ V (τ)
π′(1),π(2) (s)− V (τ) π(1),π′(2) (s) ] .
Lemma 5. For any policy pair π(1), π(2), it holds that
D(τ)(π(1), π(2)) ≤ 1 1− γ max s,π′(1)(s),π′(2)(s)
[ fτ [ Q (τ) ∗ (s), π ′(1)(s), π(2)(s) ] − fτ [ Q (τ) ∗ (s), π (1)(s), π′(2)(s) ]] .
This Lemma generalized the Lemma 32 of (Wei et al., 2021) to entropy-regularized Markov game.
Proof. Throughout this proof, we denote the policy pair (π(1)∗τ , π (2) ∗τ ) as the Nash equilibrium and their associated V-function and Q-function are respectively denoted as V (τ)∗ and Q (τ) ∗ .
Note that
V (τ) π′(1),π(2) (s)− V (τ)∗ (s) = ∑
a(1),a(2)
[ Q (τ)
π′(1),π(2) (s, a(1), a(2))π′(1)(a(1)|s)π(2)(a(2)|s)
−Q(τ)∗ (s, a(1), a(2))π(1)∗τ (a(1)|s)π(2)∗τ (a(2)|s) ]
+ τ [ H ( π′(1)(s) ) −H ( π(2)(s) ) −H ( π (1) ∗τ (s) ) +H ( π (2) ∗τ (s) )] =
∑ a(1),a(2) [ Q (τ) π′(1),π(2) (s, a(1), a(2))−Q(τ)∗ (s, a(1), a(2)) ] π′(1)(a(1)|s)π(2)(a(2)|s)
+ ∑
a(1),a(2)
Q (τ) ∗ (s, a (1), a(2)) [ π′(1)(a(1)|s)π(2)(a(2)|s)− π(1)∗τ (a(1)|s)π(2)∗τ (a(2)|s) ] + τ [ H ( π′(1)(s) ) −H ( π(2)(s) ) −H ( π (1) ∗τ (s) ) +H ( π (2) ∗τ (s)
)] = γ
∑ a(1),a(2) [ π′(1)(a(1)|s)π(2)(a(2)|s)Es′∼P(·|s,a(1),a(2)) [ V (τ) π′(1),π(2) (s′)− V (τ)∗ (s′) ]] + π′(1)(s)>Q (τ) ∗ (s)π (2)(s)− π(1)∗τ (s)>Q(τ)∗ (s)π(2)∗τ (s)
+ τ [ H ( π′(1)(s) ) −H ( π(2)(s) ) −H ( π (1) ∗τ (s) ) +H ( π (2) ∗τ (s) )] ≤ γmax
s′
[ V (τ)
π′(1),π(2) (s′)− V (τ)∗ (s′) ] + τfτ ( Q (τ) ∗ (s);π ′(1)(s), π(2)(s) ) − τfτ ( Q (τ) ∗ (s);π (1) ∗τ (s), π (2) ∗τ (s)
) (i) ≤ γmax s′ [ V (τ) π′(1),π(2) (s′)− V (τ)∗ (s′)
] + τfτ ( Q (τ) ∗ (s);π ′(1)(s), π(2)(s) ) − τ min π′(2) fτ ( Q (τ) ∗ (s);π (1)(s), π′(2)(s) ) ,
where (i) uses fτ ( Q (τ) ∗ (s);π (1) ∗τ (s), π (2) ∗τ (s) ) = maxπ′′(1) minπ′(2) fτ ( Q (τ) ∗ (s);π ′′(1)(s), π′(2)(s) ) ≥
minπ′(2) fτ ( Q (τ) ∗ (s);π (1)(s), π′(2)(s) ) .
Applying maxs,π′(1) to both sides of the above inequality and rearranging it yields that
max s,π′(1)
[ V (τ)
π′(1),π(2) (s)− V (τ)∗ (s) ] ≤ 1
1− γ max s,π′(1)(s),π′(2)(s)
[ fτ [ Q (τ) ∗ (s), π ′(1)(s), π(2)(s) ] − fτ [ Q (τ) ∗ (s), π (1)(s), π′(2)(s) ]] . (91)
Similarly, we can obtain that
max s,π′(2)
[ V
(τ) ∗ (s)− V (τ)π(1),π′(2)(s) ] ≤ 1
1− γ max s,π′(1)(s),π′(2)(s)
[ fτ [ Q (τ) ∗ (s), π ′(1)(s), π(2)(s) ] − fτ [ Q (τ) ∗ (s), π (1)(s), π′(2)(s) ]] . (92)
Therefore,
D(τ)(π(1), π(2))
= max s,π′(1),π′(2)
[ V (τ)
π′(1),π(2) (s)− V (τ) π(1),π′(2) (s) ]
≤ max s,π′(1)
[ V (τ)
π′(1),π(2) (s)− V (τ)∗ (s) ] + max s,π′(2) [ V (τ) ∗ (s)− V (τ)π(1),π′(2)(s) ] (i) ≤ 2 1− γ max s,π′(1)(s),π′(2)(s) [ fτ [ Q (τ) ∗ (s), π ′(1)(s), π(2)(s) ] − fτ [ Q (τ) ∗ (s), π (1)(s), π′(2)(s) ]]
where (i) uses eqs. (91)&(92).
Lemma 6. D(τ)(π(1), π(2)) is 2 lnAmax1−γ -Lipschitz continuous with regard to τ .
Proof. The definition of the state value function V (τ) π(1),π(2) in (3) can be rewritten as follows.
V (τ)
π(1),π(2) (s) =E [ ∞∑ t=0 γtRt ∣∣∣s0 = s]+ ∞∑ t=0 γtτ [H(π(1)(st))−H(π(2)(st))]. (93)
Hence, for any τ, τ ′ ≥ 0, ∣∣V (τ ′) π(1),π(2) (s)− V (τ) π(1),π(2) (s) ∣∣
≤ ∞∑ t=0 γt|τ ′ − τ ||H(π(1)(st))−H(π(2)(st))|
(i) ≤ ∞∑ t=0 γt|τ ′ − τ | lnAmax ≤ lnAmax 1− γ |τ ′ − τ |, (94)
where (i) uses 0 ≤ H(π(m)(st)) ≤ ln |A(m)| ≤ lnAmax. Hence, this Lemma can be proved as follows.
|D(τ ′)(π(1), π(2))−D(τ)(π(1), π(2))| ≤ ∣∣∣ max s,π′(1),π′(2) [ V (τ ′) π′(1),π(2) (s)− V (τ ′) π(1),π′(2) (s) ] − max s,π′(1),π′(2) [ V (τ) π′(1),π(2) (s)− V (τ) π(1),π′(2) (s) ]∣∣∣
≤ max s,π′(1),π′(2) ∣∣∣[V (τ ′)π′(1),π(2)(s)− V (τ ′)π(1),π′(2)(s)]− [V (τ)π′(1),π(2)(s)− V (τ)π(1),π′(2)(s)]∣∣∣ ≤ max s,π′(1),π′(2) [∣∣V (τ ′) π′(1),π(2) (s)− V (τ) π′(1),π(2) (s) ∣∣+ ∣∣V (τ) π(1),π′(2) (s)− V (τ ′) π(1),π′(2) (s) ∣∣]
(i) ≤ 2 lnAmax 1− γ |τ ′ − τ |,
where (i) uses eq. (94).
D PROOF OF THEOREM 1
Theorem 1 (Finite-time convergence rate). Apply Algorithm 1 to solve the entropy-regularized Markov game with τ ∈ (0, 1]. Choose learning rate η = [2(τ +Qmax)]−1, initialization ‖V̂0‖∞ ≤ Vmax and batch sizes Nk,t, Nk,t, Nk+1 that satisfy (18) & (19). Then, the Nash equilibrium duality gap converges at the following rate with probability at least 1− δ. D(τ) ( π
(1) K−1, π (2) K−1
) ≤ O ( Vmax lnAmax
1− γ
K−1∑ k=0 γK−k(1− ητ)Tk−1
+ Vmax 1− γ [ tmixAmax µmin ln (Tsum|S|Amax δµmin )]2/3 K−1∑ k=0 γK−k−1 Tk−1∑ t=0 (1− ητ)Tk−2−t ( 1 N 2/3 k,t + Vmax τN 2/3 k,t+1 )
+ V 3maxγ K
τ2(1− γ)2 +
tmixV 3 max τ2µmin(1− γ)3 ln ( K|S| δµmin )K−1∑ k=0 γK−k−1 Nk+1 ) . (20)
Proof. First, consider the SPU iterations that are defined by replacingQ(m)k,t , Q (m) k,t+1 in (8) with Q̂ (m) k,t , Q̂ (m)
k,t+1, respectively, for m = 1, 2. We can apply Lemma 1 with the quantities being specified as follows.
• Q := Qk(s), hτ (µ, ν) := fτ ( Qk(s);µ, ν ) ,
• µt := π (1) k,t (s), νt := π (2) k,t (s), µt+1 := π (1) k,t+1(s), νt+1 := π (2) k,t+1(s),
µ∗τ := π ∗(1) k (s), ν ∗ τ := π ∗(2) k (s),
• dm := |A(m)|,
• δ(m)k,t := Q̂ (m) k,t (s)−Q (m) k,t (s), δ
(m) k,t := Q̂ (m) k,t+1(s)−Q (m) k,t+1(s),
where π(1)∗k (s), π (2)∗ k (s) is the solution policy pair to the minimax optimization problem minπ(2)(s) maxπ(1)(s) fτ ( Qk(s);π (1)(s), π(2)(s) ) .
Consequently, eqs. (29) & (30) with t = Tk − 1 imply the following two inequalities, respectively.∣∣fτ(Qk(s);π(1)k,Tk(s), π(1)k,Tk(s))− fτ(Qk(s);π∗(1)k (s), π∗(2)k (s))∣∣ = ∣∣V ′k+1(s)− fτ(Qk(s);π∗(1)k (s), π∗(2)k (s))∣∣
≤ 8 η (1− ητ)Tk−1 lnAmax + Tk−1∑ t=0 (1− ητ)Tk−2−t
2∑ m=1 [ 8η ∥∥Q̂(m)k,t (s)−Q(m)k,t (s)∥∥2∞ + 334τ ∥∥Q̂(m)k,t+1(s)−Q(m)k,t+1(s)∥∥2∞], (95)
max π(1)(s),π(2)(s)
[ fτ ( Qk(s);π
(1)(s), π (2) k,Tk
(s) ) − fτ ( Qk(s);π
(1) k,Tk
(s), π(2)(s) )]
= max π(1)(s),π(2)(s)
[ fτ ( Qk(s);π (1)(s), π (2) k (s) ) − fτ ( Qk(s);π (1) k (s), π (2)(s) )]
≤ 4 η (1− ητ)Tk−1 lnAmax + Tk−1∑ t=0 (1− ητ)Tk−2−t
2∑ m=1 [ 16η ∥∥Q̂(m)k,t (s)−Q(m)k,t (s)∥∥2∞ + 12τ ∥∥Q̂(m)k,t+1(s)−Q(m)k,t+1(s)∥∥2∞]. (96)
Then, define the soft Bellman operator Bτ as follows.
Bτ (Q)(s, a(1), a(2)) := R(s, a(1), a(2)) + γEs′∼P(·|s,a(1),a(2)) [
max π(1)(s′) min π(2)(s′)
fτ ( Q(s′);π(1)(s′), π(2)(s′) )] , (97)
where Q : S × A(1) × A(2) → R and Q(s′) ∈ R|A(1)|×|A(2)| with each entry given by [Q(s′)]a(1),a(2) := Q(s, a
(1), a(2)). It can be proved that Bτ is a contraction operator and has a unique fixed point Q(τ)∗ (Cen et al., 2021), that is,
‖Bτ (Q′)− Bτ (Q)‖∞ ≤γ‖Q′ −Q‖∞, (98)
Bτ (Q(τ)∗ ) =Q(τ)∗ . (99)
As a result, we obtain that
‖Qk+1 −Q(τ)∗ ‖∞ (i)
≤ ‖Qk+1 − Bτ (Qk)‖∞ + ‖Bτ (Qk)− Bτ (Q(τ)∗ )‖∞ (ii)
≤ max s,a(1),a(2) |Qk+1(s, a(1), a(2))− Bτ (Qk)(s, a(1), a(2))|+ γ‖Qk −Q(τ)∗ ‖∞
= max s,a(1),a(2) ∣∣∣R(s, a(1), a(2)) + γEs′∼P(·|s,a(1),a(2))V ′k+1(s′) − [ R(s, a(1), a(2)) + γEs′∼P(·|s,a(1),a(2))fτ ( Qk(s ′);π ∗(1) k (s ′), π ∗(2) k (s ′) )]∣∣∣+ γ‖Qk −Q(τ)∗ ‖∞
≤ γmax s′∈S
∣∣V ′k+1(s′)− fτ(Qk(s′);π∗(1)k (s′), π∗(2)k (s′))∣∣+ γ‖Qk −Q(τ)∗ ‖∞, (100)
where (i) uses eq. (99) and (ii) uses eq. (98). Throughout the proof, suppose that eqs. (72), (75) & (76) hold simultaneously which occurs with probability at least 1− δ. In this case, we have∥∥Q̂(m)k,t (s)−Q(m)k,t (s)∥∥2∞
(i) ≤ 648Q2max [ tmixAmax Nk,tµmin ln (20Tsum|S|Amax δ √ µmin )]2/3 + 8 ∥∥V̂k − V ′k∥∥2∞
(ii) ≤ 648Q2max [ tmixAmax Nk,tµmin ln (20Tsum|S|Amax δ √ µmin )]2/3 + 32V 2maxγ 2k + 29241tmixV 2 max Nk+1µmin(1− γ)2 ln ( 4K|S| δ √ µmin ) , (101)
where (i) uses eq. (75) and the inequality that (a + b)2 ≤ 2a2 + 2b2 for any a, b ≥ 0, (ii) uses eq. (72) and also (a+ b)2 ≤ 2a2 + 2b2 for any a, b ≥ 0. Similarly, we obtain that∥∥Q̂(m)k,t+1(s)−Q(m)k,t+1(s)∥∥2∞
≤ 648Q2max [ tmixAmax Nk,t+1µmin ln (20Tsum|S|Amax δ √ µmin )]2/3 + 32V 2maxγ 2k + 29241tmixV 2 max Nk+1µmin(1− γ)2 ln ( 4K|S| δ √ µmin ) . (102)
Then, iterating eq. (100) yields that
‖QK−1 −Q(τ)∗ ‖∞
≤ γK−1‖Q0 −Q(τ)∗ ‖∞ + K−2∑ k=0 γK−k−1 max s′∈S ∣∣Vk+1(s′)− fτ(Qk(s′);π∗(1)k (s′), π∗(2)k (s′))∣∣ (i)
≤ 2γK−1Qmax + K−2∑ k=0 γK−k−1
[ 8
η (1− ητ)Tk−1 lnAmax + Tk−1∑ t=0 (1− ητ)Tk−2−t
2∑ m=1 [ 8η ∥∥Q̂(m)k,t (s)−Q(m)k,t (s)∥∥2∞ + 334τ ∥∥Q̂(m)k,t+1(s)−Q(m)k,t+1(s)∥∥2∞] ] (ii)
≤ 2γK−1Qmax + K−2∑ k=0 γK−k−1
[ 8
η (1− ητ)Tk−1 lnAmax + Tk−1∑ t=0 (1− ητ)Tk−2−t
2∑ m=1 ( 648Q2max [ tmixAmax µmin ln (20Tsum|S|Amax δ √ µmin )]2/3( 8η N 2/3 k,t + 33 4τN 2/3 k,t+1 )
+ ( 8η + 33
4τ
)[ 32V 2maxγ 2k + 29241tmixV 2 max Nk+1µmin(1− γ)2 ln ( 4K|S| δ √ µmin )])] (iii)
≤ 2γK−1Qmax + 8
η lnAmax K−2∑ k=0 γK−k−1(1− ητ)Tk−1
+ 324Q2max [ tmixAmax µmin ln (20Tsum|S|Amax δ √ µmin )]2/3 K−2∑ k=0 γK−k−1 Tk−1∑ t=0 (1− ητ)Tk−2−t ( 32η N 2/3 k,t + 33 τN 2/3 k,t+1 ) + 1568γK−1V 2max ητ2(1− γ)
+ 1432809tmixV
2 max ητ2µmin(1− γ)2 ln ( 4K|S| δ √ µmin )K−2∑ k=0 γK−k−1N−1k+1 (103)
(iv) = O [ Vmax lnAmax
K−2∑ k=0 γK−k(1− ητ)Tk−1 + Vmax [ tmixAmax µmin ln (Tsum|S|Amax δµmin )]2/3
K−2∑ k=0 γK−k−1 Tk−1∑ t=0 (1− ητ)Tk−2−t ( 1 N 2/3 k,t + Vmax τN 2/3 k,t+1 )
+ V 3maxγ K
τ2(1− γ) +
tmixV 3 max τ2µmin(1− γ)2 ln ( K|S| δµmin )K−2∑ k=0 γK−k−1N−1k+1 ] (104)
where (i) uses eqs. (68)&(95), (ii) uses eqs. (101)&(102), (iii) uses η = [2(τ +Qmax)]−1 ≤ 1/(2τ),∑Tk−1 t=0 (1 − ητ)Tk−2−t ≤ 1 ητ(1−ητ) ≤ 2 ητ and ∑K−2 k=0 γ K+k−1 ≤ γ K−1
1−γ , and (iv) uses Qmax = O(Vmax) for γ ≈ 1 and η = [2(τ + Qmax)]−1 = O(Q−1max) = O(V −1max) (Since Qmax ≥ γτ = O(τ)). Using Lemma 5, the convergence rate of the duality gap in eq. (20) can be proved as follows.
D(τ) ( π
(1) K−1, π (2) K−1 ) (i) ≤ 2 1− γ max s,π(1),π(2) [ fτ [ Q (τ) ∗ (s), π (1)(s), π (2) K−1(s) ] − fτ [ Q (τ) ∗ (s), π (1) K−1(s), π (2)(s) ]]
≤ 2 1− γ max s,π(1),π(2)
[ fτ ( QK−1(s);π (1)(s), π (2) K−1(s) ) − fτ ( QK−1(s);π (1) K−1(s), π (2)(s) )]
+ 2
1− γ max s,π(1),π(2) ∣∣fτ(Q(τ)∗ (s);π(1)(s), π(2)K−1(s))− fτ(QK−1(s);π(1)(s), π(2)K−1(s))∣∣ + 2
1− γ max s,π(1),π(2) ∣∣fτ(QK−1(s);π(1)K−1(s), π(2)(s))− fτ(Q(τ)∗ (s);π(1)K−1(s), π(2)(s))∣∣ (ii)
≤ 8 η(1− γ) (1− ητ)TK−1−1 lnAmax + 2 1− γ TK−1−1∑ t=0 (1− ητ)TK−1−2−t
2∑ m=1 [ 16η ∥∥Q̂(m)K−1,t(s)−Q(m)K−1,t(s)∥∥2∞ + 12τ ∥∥Q̂(m)K−1,t+1(s)−Q(m)K−1,t+1(s)∥∥2∞]
+ 2
1− γ max s,π(1) ∣∣π(1)(s)>[Q(τ)∗ (s)−QK−1(s)]π(2)K−1(s)∣∣ + 2
1− γ max s,π(2) ∣∣π(1)K−1(s)>[QK−1(s)−Q(τ)∗ (s)]π(2)(s)∣∣ (iii)
≤ 8 lnAmax η(1− γ) (1− ητ)TK−1−1 + 4 1− γ TK−1−1∑ t=0
(1− ητ)TK−1−2−t( 648Q2max [ tmixAmax µmin ln (20Tsum|S|Amax δ √ µmin )]2/3( 16η N
2/3 K−1,t
+ 12
τN 2/3
K−1,t+1
)
+ ( 32η + 24
τ
)[ 32V 2maxγ 2(K−1) + 29241tmixV 2 max NKµmin(1− γ)2 ln ( 4K|S| δ √ µmin
)])
+ 4
1− γ ‖QK−1 −Q(τ)∗ ‖∞
(iv)
≤ 8 lnAmax η(1− γ) (1− ητ)TK−1−1 + 2592Q 2 max 1− γ [ tmixAmax µmin ln (20Tsum|S|Amax δ √ µmin )]2/3 TK−1−1∑ t=0 (1− ητ)TK−1−2−t ( 16η N 2/3 K−1,t + 12 τN 2/3 K−1,t+1
) + 160
ητ2 [32V 2max 1− γ γ2(K−1) + 29241tmixV 2 max NKµmin(1− γ)3 ln ( 4K|S| δ √ µmin )] +
8γK−1Qmax 1− γ + 32 lnAmax η(1− γ) K−2∑ k=0 γK−k−1(1− ητ)Tk−1
+ 1296Q2max
1− γ [ tmixAmax µmin ln (20Tsum|S|Amax δ √ µmin )]2/3 K−2∑ k=0 γK−k−1 Tk−1∑ t=0 (1− ητ)Tk−2−t ( 32η N 2/3 k,t + 33 τN 2/3 k,t+1 ) + 6272γK−1V 2max ητ2(1− γ)2
+ 5731236tmixV
2 max ητ2µmin(1− γ)3 ln ( 4K|S| δ √ µmin )K−2∑ k=0 γK−k−1N−1k+1
≤ 8γ K−1Qmax 1− γ + 32 lnAmax η(1− γ) K−1∑ k=0 γK−k−1(1− ητ)Tk−1
+ 1296Q2max
1− γ [ tmixAmax µmin ln (20Tsum|S|Amax δ √ µmin )]2/3 K−1∑ k=0 γK−k−1 Tk−1∑ t=0 (1− ητ)Tk−2−t ( 32η N 2/3 k,t + 33 τN 2/3 k,t+1 ) + 11392γK−1V 2max ητ2(1− γ)2
+ 5731236tmixV
2 max ητ2µmin(1− γ)3 ln ( 4K|S| δ √ µmin )K−1∑ k=0 γK−k−1N−1k+1
(v) = O
[ Vmax lnAmax
1− γ
K−1∑ k=0 γK−k(1− ητ)Tk−1 + Vmax 1− γ [ tmixAmax µmin ln (Tsum|S|Amax δµmin )]2/3 K−1∑ k=0 γK−k−1 Tk−1∑ t=0 (1− ητ)Tk−2−t ( 1 N 2/3 k,t + Vmax τN 2/3 k,t+1 ) + V 3maxγ K τ2(1− γ)2
+ tmixV
3 max τ2µmin(1− γ)3 ln ( K|S| δµmin )K−1∑ k=0 γK−k−1N−1k+1 ] ,
where (i) uses Lemma 5, (ii) uses eq. (96) and the definition of the function fτ , (iii) uses eqs. (101)&(102), (iv) uses eq. (103) and η = [2(τ + Qmax)]−1 ≤ 1/(2τ), ∑Tk−1 t=0 (1 − ητ)Tk−2−t ≤
1 ητ(1−ητ) ≤ 2 ητ , and (v) uses Qmax = O(Vmax) for γ ≈ 1 and η = [2(τ +Qmax)] −1 = O(Q−1max) = O(V −1max) (Since Qmax ≥ γτ = O(τ)).
E PROOF OF THEOREM 2 Theorem 2 (Sample complexity). Implement Algorithm 1 with η = O ( 1 − γ ) , τ = O ( (1−γ) lnAmax ) ,
K = O [
1 1−γ ln ( lnAmax (1−γ) )] and Tk = 1 + k ln γ −1 ln(1−ητ)−1 . Choose the following adaptive batch sizes.
Nk+1 = Õ ( tmix(ln2Amax)γ− k2 2µmin(1− γ)8 ) , Nk,t = Nk,t 3 2 (1− γ)3 = Õ ( tmixAmax(1− ητ)−3(t+1)5 µmin(1− γ)3 ) .
Then, for any ≤ lnAmax1−γ , the overall sample complexity to achieve D (0)(π (1) K−1, π (2) K−1) ≤ is Õ (
tmixAmax µmin 5.5(1−γ)13.5
) . Please refer to (118) in Appendix E for a complete expression.
Proof. Since τ = O ( (1−γ)
lnAmax
) , we have
Vmax = 1 + τ lnAmax
1− γ =
1
1− γ +O( ) = O
( (1− γ)−1 ) . (105)
Qmax = 1 + γτ lnAmax
1− γ =
1
1− γ +O( ) = O
( (1− γ)−1 ) . (106)
Since Tk = 1 + k ln γ −1
ln(1−ητ)−1 , we have
Tsum = K−1∑ k=0 ( 1 + k ln γ−1 ln(1− ητ)−1 )
=K + K(K − 1) 2 O (1− γ ητ ) =K +
K(K − 1) 2 O ( lnAmax (1− γ) ) =O (K2 lnAmax (1− γ)
) =O [ lnAmax (1− γ)3 ln2 ( lnAmax (1− γ) )] . (107)
Hence,
ln (Tsum|S|Amax
δµmin
) = O [ ln ( |S|Amax lnAmax δµmin (1− γ)3 ) + ln ( 2 ln ( lnAmax (1− γ) ))] = O
[ ln ( |S|Amax δµmin(1− γ) )] . (108)
Similarly, ln ( K|S| δµmin ) =O [ ln (( |S| δµmin(1− γ) ) ln ( lnAmax (1− γ) ))] =O [ ln ( |S| ln( −1 lnAmax)
δµmin(1− γ)
)] +O [ ln (( |S|
δµmin(1− γ)
) ln ( 1
1− γ ))] =O [ ln ( |S| ln( −1 lnAmax)
δµmin(1− γ)
)] +O [ ln ( |S| δµmin(1− γ) )] =O [ ln ( |S| ln( −1 lnAmax)
δµmin(1− γ)
)] (109)
where (i) uses ≤ lnAmax1−γ . With the above equalities, we will prove below that the hyperparameter choices in Theorem 2 are valid and satisfy the conditions of Theorem 1 with proper constants hidden in O(·).
η =[2(τ +Qmax)] −1 = O ( 1− γ ) (110)
τ =O ( (1− γ)
lnAmax
) ∈ (0, 1] (111)
K = 1 ln γ−1 ln ( ln5/2Amax 5(1− γ)7.5 ) = O [ 1 1− γ ln ( lnAmax (1− γ) )] ≥ 1 (112)
Tk =1 + k ln γ−1
ln(1− ητ)−1 ≥ 1 (113)
Nk+1 =O [ tmix(ln2Amax)γ−k/2 2µmin(1− γ)8 ln ( |S| ln( −1 lnAmax) δµmin(1− γ) )] ≥650tmix
µmin ln ( 4 δ √ µmin ) = O [ tmix µmin ln ( 1 δµmin )] (114)
Nk,t =O [ tmixAmax(1− ητ)−3(t+1)/5 µmin(1− γ)3 ln ( |S|Amax δµmin(1− γ) )] ≥650tmixAmax
µmin ln (20Tsum|S|Amax δ √ µmin ) = O [ tmixAmax µmin ln ( |S|Amax δµmin(1− γ) )] (115)
Nk,t =O [ tmixAmax(ln3/2Amax)(1− ητ)−3(t+1)/5 µmin 3/2(1− γ)6 ln ( |S|Amax δµmin(1− γ) )]
≥650tmixAmax µmin
ln (20Tsum|S|Amax
δ √ µmin
) = O [ tmixAmax µmin ln ( |S|Amax δµmin(1− γ) )] , (116)
With these hyperparameters and eqs. (108)&(109), the duality gap bound (20) can be simplified as follows,
D(τ) ( π
(1) K−1, π (2) K−1 ) ≤ O [ Vmax lnAmax
1− γ
K−1∑ k=0 γK−k(1− ητ)Tk−1 + Vmax 1− γ [ tmixAmax µmin ln (Tsum|S|Amax δµmin )]2/3 K−1∑ k=0 γK−k−1 Tk−1∑ t=0 (1− ητ)Tk−2−t ( 1 N 2/3 k,t + Vmax τN 2/3 k,t+1 ) + V 3maxγ K τ2(1− γ)2
+ tmixV
3 max τ2µmin(1− γ)3 ln ( K|S| δµmin )K−1∑ k=0 γK−k−1 Nk+1 ] (i) ≤ O [ lnAmax (1− γ)2 K−1∑ k=0 γK−kγk
+ 1 (1− γ)2 [ tmixAmax µmin ln ( |S|Amax δµmin(1− γ) )]2/3 K−1∑ k=0 γK−k−1 Tk−1∑ t=0
(1− ητ)Tk−2−t( O [ tmixAmax µmin(1− γ)3 ln ( |S|Amax δµmin(1− γ) )]−2/3 (1− ητ)2(t+1)/5
+O ( lnAmax (1− γ)2 ) O [ tmixAmax(ln3/2Amax) µmin 3/2(1− γ)6 ln ( |S|Amax δµmin(1− γ) )]−2/3 (1− ητ)2(t+1)/5
)
+ γK(ln2Amax)
2(1− γ)7 + tmix(ln
2Amax) 2µmin(1− γ)8 ln ( |S| ln( −1 lnAmax) δµmin(1− γ) ) K−1∑ k=0 γK−k−1O [ tmix(ln2Amax)γ−k/2 2µmin(1− γ)8 ln ( |S| ln( −1 lnAmax) δµmin(1− γ) )]−1]
≤ O [ lnAmax (1− γ)2 KγK + K−1∑ k=0 γK−k−1 Tk−1∑ t=0 (1− ητ)Tk−1−3(t+1)/5
+ γK(ln2Amax)
2(1− γ)7 + K−1∑ k=0 γK−k/2−1 ] (ii)
≤ O [ lnAmax (1− γ)2 KγK + K−1∑ k=0 γK−1 (1− ητ)−3/5[(1− ητ)−3Tk/5 − 1] (1− ητ)−3/5 − 1
+ γK(ln2Amax)
2(1− γ)7 + γK−1 γ−K/2 − 1 γ−1/2 − 1 ] (iii)
≤ O [ lnAmax (1− γ)2 KγK + K−1∑ k=0 γK−1−3k/5 1− (1− ητ)3/5 + γK(ln2Amax) 2(1− γ)7 + γ(K−1)/2 1− γ1/2 ] (iv)
≤ O [ lnAmax (1− γ)2 KγK + γK−1(γ−3K/5 − 1) ητ(γ−3/5 − 1) + γK(ln2Amax) 2(1− γ)7 + γK/2 1− γ ] (v) ≤ O [ γK lnAmax (1− γ)3 ln ( lnAmax (1− γ) ) + γ2K/5 lnAmax (1− γ)3 + γK(ln2Amax) 2(1− γ)7 + γK/2 1− γ
] (vi)
≤ O [ + 3 √ 1− γ
lnAmax + 5/2(1− γ)2.75 ln5/4Amax
] = O( ) (vii) ≤ c (117)
where (i), (ii) and (iii) use (1−ητ)Tk−1 = γk based on eq. (113), (i) also uses eqs. (105), (108)-(111) & (114)-(116), (iv) uses 1 − (1 − ητ)3/5 = O(ητ), 1 − γ1/2 = O(1 − γ), (v) uses eqs. (110)- (112), (vi) uses O [ γK lnAmax (1−γ)3 ln ( lnAmax (1−γ) )] ≤ O [ γK(ln2 Amax) 2(1−γ)7 ] and γK = 5(1−γ)7.5 ln5/2 Amax implied by eq. (112), and the numeric constant c > 0 in (vii) exists. By replacing with /c, we obtain that Dτ ( π (1) K−1, π (2) K−1 ) ≤ which means (π(1)K−1, π (2) K−1) is an -Nash equilibrium policy pair, and the orders of all the hyperparameter choices remain the same. In this case, the overall sample complexity is given by
K−1∑ k=0 [ Nk+1 + 2 Tk−1∑ t=0 (Nk,t +Nk,t+1) ]
(i) = O [ tmix(ln2Amax) 2µmin(1− γ)8 ln ( |S| ln( −1 lnAmax) δµmin(1− γ) )]K−1∑ k=0 γ−k/2
+O [ tmixAmax(ln3/2Amax) µmin 3/2(1− γ)6 ln ( |S|Amax δµmin(1− γ) )]K−1∑ k=0 Tk−1∑ t=0 (1− ητ)−3(t+1)/5
= O [ tmix(ln2Amax) 2µmin(1− γ)8 ln ( |S| ln( −1 lnAmax) δµmin(1− γ) )]γ−K/2 − 1 γ−1/2 − 1
+O [ tmixAmax(ln3/2Amax) µmin 3/2(1− γ)6 ln ( |S|Amax δµmin(1− γ) )]K−1∑ k=0 [(1− ητ)−3Tk/5 − 1] 1− (1− ητ)3/5
(ii) ≤ O [ tmix(ln2Amax) 2µmin(1− γ)8 ln ( |S| ln( −1 lnAmax) δµmin(1− γ) )] γ−K/2
+O [ tmixAmax(ln3/2Amax) µmin 3/2(1− γ)6 ln ( |S|Amax δµmin(1− γ) ) lnAmax (1− γ)2 ]K−1∑ k=0 γ−3k/5
≤ O [ tmix(ln2Amax) 2µmin(1− γ)8 ln ( |S| ln( −1 lnAmax) δµmin(1− γ) )] γ−K/2
+O [ tmixAmax(ln5/2Amax) µmin 5/2(1− γ)8 ln ( |S|Amax δµmin(1− γ) )] γ−3K/5 γ−3/5 − 1
(iii) ≤ O [ tmix(ln2Amax) 2µmin(1− γ)8 ln ( |S| ln( −1 lnAmax) δµmin(1− γ) )] ln5/4Amax 5/2(1− γ)3.75
+O [ tmixAmax(ln5/2Amax) µmin 5/2(1− γ)8 ln ( |S|Amax δµmin(1− γ) )] ln3/2Amax 3(1− γ)5.5
(iv) = O [ tmixAmax(ln4Amax) µmin 5.5(1− γ)13.5 ln ( |S|Amax δµmin(1− γ) )] (118)
= Õ ( tmixAmax µmin 5.5(1− γ)13.5 ) where (i) usesNk,t ≤ Nk,t and eqs. (114)&(116), (ii) uses γ−1/2−1 = O(1−γ), 1−(1−ητ)3/5 = O(ητ) = O ( (1−γ)2 lnAmax ) and (1−ητ)Tk−1 = γk, (iii) uses γ−3/5−1 = O(1−γ) and γK = 5(1−γ)7.5
ln5/2 Amax implied by the hyperparameter choice (112), and (iv) uses the fact that the second term of (iii) is larger than the first term of (iii).
F SUMMARY OF COMPARISON OF SAMPLE COMPLEXITIES
In the column “Model-free”, a Xmeans that an algorithm does not need any prior knowledge of the environment, including reward mapping and transition kernel.
In the column “Private update”, a Xmeans that the algorithm updates do not involve the opponent’s sensitive information, including action and policy.
The sample complexity is defined as the total number of samples required to achieve an -duality gap for the Markov game. A “–” sign in this column means that such type of sample complexity is unavailable in that paper or its setting is different from ours. We use Õ to hide all the logarithm factors.
We next explain how the sample complexity of (Wei et al., 2021) is calculated. Corollary 4 of (Wei et al., 2021) shows that the iterate-average duality gap is smaller than with the hyper-parameter choices: number of iterations T = Õ [ |S|2
η2(1−γ)4 2
] and number of samples queried per iteration
L = Õ [ A3max|S| 6
(1−γ)13µminη3 6
] (we replace ξ with ). Hence, the overall sample complexity is
LT = Õ [ A3max|S|8 (1− γ)17µminη5 8 ] (i) ≥ Õ [ A3max|S|10.5 (1− γ)29.5µmin 8 ] ,
where (i) uses the choice of learning rate η ≤ O [√
(1−γ)5 |S|
] required by their Algorithm 1.
G RATIONALITY
In this section, we will prove that the policy extragradient (PE) algorithm Cen et al. (2021) is rational. The following analysis can be directly extended to our stochastic policy extragradient (SPE) algorithm by applying the estimation error bounds in Appendix B.
An algorithm is called rational if, whenever the player 2 adopts an arbitrary stationary policy π(2), the policy of the player 1 converges to the best response to π(2), i.e., π̃(1)∗τ (s) = arg maxπ(1)(s) V (τ) π(1),π(2) (s) for all s ∈ S. We add tilde in π̃(1)∗τ (s) to differentiate it from the Nash policy pair (π(1)∗τ (s), π (2) ∗τ (s)) and some consequent notations are similar. Denote Q̃ (τ) ∗ := Q (τ)
π̃ (1) ∗τ ,π(2)
,
Ṽ (τ) ∗ := V (τ)
π̃ (1) ∗τ ,π(2)
as the optimal value functions and define the soft Bellman operator as follows
B̃τ (Q)(s, a(1), a(2)) := R(s, a(1), a(2)) + γEs′∼P(·|s,a(1),a(2)) [
max π(1)(s′)
fτ ( Q(s′);π(1)(s′), π(2)(s′) )] . (119)
Similar to eqs. (98)&(99), it can be proved that the soft Bellman operator B̃τ is also a contraction operator and has a unique fixed point Q̃(τ)∗ , i.e.,
‖B̃τ (Q′)− B̃τ (Q)‖∞ ≤γ‖Q′ −Q‖∞, (120)
B̃τ (Q̃(τ)∗ ) =Q̃(τ)∗ . (121)
To solve modified Markov game with fixed policy π(2), we develop the single-player-perspective version of the PE algorithm in Algorithm 2, which basically approximates the value iteration Qk+1 = B̃τ (Qk). The main modification from the original PE algorithm is that the new policy update (126) only keeps the third expression of the PU steps (8) since only that affects the final policy of player 1 with fixed π(2). This new policy update (126) aims to find π(1) that maximizes the following single-player Markov game problem with fixed Qk(s) and π(2)(s) for all s ∈ S, while the original PU algorithm seeks the Nash equilibrium (π(1), π(2)) of the following function.
max π(1)(s)
fτ (Qk(s);π (1)(s), π(2)(s))
:= [π(1)(s)]>Qk(s)π (2)(s) + τH ( π(1)(s) ) − τH ( π(2)(s) ) . (122)
Similar to eq. (23), it can be derived that the solution π̃∗(1)k (s) to the above optimization problem satisfies the following condition Cen et al. (2021).
π̃ ∗(1) k (s) ∝ exp(Qk(s)π2(s)/τ). (123)
Algorithm 2 Single-player perspective PE algorithm for entropy-regularized Markov game. Initialize: V0(s) for all s ∈ S. for value iterations k = 0, 1, . . . ,K − 1 do
Compute the following Q functions for all (s, a(1), a(2)).
Qk(s, a (1), a(2)) =R(s, a(1), a(2)) + γEs′∼P(s,a(1),a(2))Vk(s′) (124)
Q (1) k (s, a (1)) =Ea(2)∼π(2)(s)Qk(s, a(1), a(2)) (125)
Initialize π(1)k,0 with uniform distribution. for PU iterations t = 0, 1, . . . , T − 1 do
Player 1 implements the t-th policy update for all s, a(1) as follows.
π (1) k,t+1(a (1)|s) ∝ π(1)k,t (a (1)|s)1−ητ exp
( ηQ
(1) k (s, a
(1)) ) , (126)
end Let π(1)k = π (1) k,T , and perform the following value iteration for all s
Vk+1(s) := fτ (Qk(s);π (1) k (s), π (2)(s)) (127)
end Output: π(1)K−1.
We first prove that the value functions Vk and Qk in Algorithm 2 are bounded as follows.
Lemma 7. If ‖V0‖∞ ≤ Vmax := 1+τ lnAmax1−γ in Algorithm 2, then for all k ≥ 0, 0 ≤ t ≤ Tk − 1, we have
max ( ‖Vk‖∞, ‖Ṽ (τ)∗ ‖∞ ) ≤ Vmax, (128)
max ( ‖Qk‖∞, Q̃(τ)∗ ‖∞‖∞ ) ≤ Qmax, (129)
where Qmax := 1 + γVmax = 1+γτ lnAmax1−γ with Amax := max ( |A(1)|, |A(2)| ) .
Proof. The proof is similar to that of Lemma 3.
Similar to Lemma 1, we can prove the following lemma about the convergence rates of the modified PU steps defined by eq. (126).
Lemma 8. Apply Algorithm 2 to solve the entropy regularized game with τ > 0. Choose learning rate η ≤ τ−1 and initialization ‖V0‖∞ ≤ Vmax. Then, the policy update defined by eq. (126) for maximizing the function (122) has the following convergence rates.
KL(π̃ ∗(1) k (s)‖π (1) k,T (s)) +KL
( π
(1) k,T (s)‖π̃ ∗(1) k (s)
) ≤ 2Qmax
τ (1− ητ)T (130)
fτ (Qk(s); π̃ ∗(1) k (s), π (2)(s))− Vk+1(s) = τKL ( π (1) k,T (s)‖π̃ ∗(1) k (s) ) ≤ 2Qmax(1− ητ)T (131)
Proof. Taking logarithm of eq. (126) yields that there exists ck,t ∈ R such that
lnπ (1) k,t+1(s) = (1− ητ) lnπ (1) k,t (s) + ηQk(s)π2(s) + ck,t1.
Iterating the above equality over t = 0, 1, . . . , t yields that there exists c ∈ R such that
lnπ (1) k,T (s) =
1− (1− ητ)T
τ Qk(s)π2(s) + c1 (132)
where we use the uniform policy initialization π(1)k,0(s) = 1/|A(1)|.
Taking logarithm of eq. (123) yields that there exists c∗ ∈ R such that ln π̃
∗(1) k (s) = Qk(s)π2(s)/τ + c ∗1 (133)
Therefore, eq. (130) can be proved as follows.
KL(π̃ ∗(1) k (s)‖π (1) k,T (s)) +KL(π (1) k,T (s)‖π̃ ∗(1) k (s)) = 〈 π̃ ∗(1) k (s), ln π̃ ∗(1) k (s)− lnπ (1) k,T (s) 〉 + 〈 π (1) k,T (s), lnπ (1) k,T (s)− ln π̃ ∗(1) k (s) 〉 (i) = 〈 π̃ ∗(1) k (s)− π (1) k,T (s), (1− ητ)T
τ Qk(s)π2(s) + (c
∗ − c)1 〉
(ii) =
(1− ητ)T
τ [π̃ ∗(1) k (s)− π (1) k,T (s)] >Qk(s)π2(s)
(iii)
≤ 2Qmax τ (1− ητ)T
where (i) uses eqs. (132)&(133), (ii) uses 〈π̃∗(1)k (s)− π (1) k,T (s),1〉 = 0 and (iii) uses ‖Qk(s)‖∞ ≤ Qmax, ‖π̃∗(1)k − π (1) k,T ‖1 ≤ 2, ‖π2(s)‖1 = 1 and 1− ητ > 0.
fτ (Qk(s); π̃ ∗(1) k (s), π (2)(s))− Vk+1(s)
= fτ (Qk(s); π̃ ∗(1) k (s), π (2)(s))− fτ (Qk(s);π(1)k,T (s), π (2)(s)) = 〈 π̃ ∗(1) k (s)− π (1) k,T (s), Qk(s)π (2)(s) 〉 + τ 〈 π (1) k,T (s), lnπ (1) k,T (s) 〉 − τ 〈 π̃ ∗(1) k (s), ln π̃ ∗(1) k (s) 〉 (i) = 〈 π̃ ∗(1) k (s)− π (1) k,T (s), τ ln π̃ ∗(1) k (s) 〉 + τ 〈 π (1) k,T (s), lnπ (1) k,T (s) 〉 − τ 〈 π̃ ∗(1) k (s), ln π̃ ∗(1) k (s)
〉 = τKL ( π
(1) k,T (s)‖π̃ ∗(1) k (s) ) (ii)
≤ 2Qmax(1− ητ)T where (i) uses eq. (133) and 〈 π̃ ∗(1) k (s)− π (1) k,T (s),1 〉 = 0 and (ii) uses eq. (130).
Finally, we prove the convergence rate of Algorithm 2 as follows. Theorem 3. Apply Algorithm 2 to solve the entropy regularized game with τ > 0. Choose learning rate η ≤ τ−1 and initialization ‖V0‖∞ ≤ Vmax. Then, the Q function estimation error ‖QK−1 − Q̃ (τ) ∗ ‖∞ and the function value gap maxs [ Ṽ (τ) ∗ (s)− V (τ)
π (1) K−1,π
(2) (s) ] converge at the following rates
‖QK−1 − Q̃(τ)∗ ‖∞ ≤ 2QmaxγK + 2γQmax 1− γ (1− ητ)T , (134)
max s
[ Ṽ (τ) ∗ (s)− V (τ)
π (1) K−1,π
(2) (s) ] ≤ 2Qmax
1− γ
( 2γK−1 + 1 + γ
1− γ (1− ητ)T
) . (135)
Proof.
‖Qk+1 − Q̃(τ)∗ ‖∞ (i)
≤ ‖Qk+1 − B̃τ (Qk)‖∞ + ‖B̃τ (Qk)− B̃τ (Q̃(τ)∗ )‖∞ (ii)
≤ max s,a(1),a(2) |Qk+1(s, a(1), a(2))− B̃τ (Qk)(s, a(1), a(2))|+ γ‖Qk − Q̃(τ)∗ ‖∞
= max s,a(1),a(2) ∣∣∣R(s, a(1), a(2)) + γEs′∼P(·|s,a(1),a(2))Vk+1(s′) − [ R(s, a(1), a(2)) + γEs′∼P(·|s,a(1),a(2))fτ ( Qk(s ′); π̃ ∗(1) k (s ′), π(2)(s′) )]∣∣∣+ γ‖Qk − Q̃(τ)∗ ‖∞
≤ γmax s′∈S ∣∣Vk+1(s′)− fτ(Qk(s′); π̃∗(1)k (s′), π(2)(s′))∣∣+ γ‖Qk − Q̃(τ)∗ ‖∞ (iii)
≤ 2γQmax(1− ητ)T + γ‖Qk − Q̃(τ)∗ ‖∞, where (i) uses eq. (121), (ii) uses eq. (120), (iii) uses eq. (131). Iterating the above inequality yields that
‖QK−1 − Q̃(τ)∗ ‖∞ ≤ γK‖Q0 − Q̃(τ)∗ ‖∞ + 2γQmax(1− ητ)T 1− γT
1− γ
≤ 2QmaxγK + 2γQmax 1− γ (1− ητ)T ,
which proves eq. (134). Finally, eq. (135) can be proved as follows
Ṽ (τ) ∗ (s)− V (τ)
π (1) K−1,π
(2) (s) = ∑
a(1),a(2)
[ Q̃ (τ) ∗ (s, a (1), a(2))π̃ (1) ∗τ (a
(1)|s)−Q(τ) π (1) K−1,π (2) (s, a(1), a(2))π (1) K−1(a
(1)|s) ] π(2)(a(2)|s)
+ τ [ H ( π̃ (1) ∗τ (s) ) −H ( π (1) K−1(s) )] =
∑ a(1),a(2) [ Q̃ (τ) ∗ (s, a (1), a(2))−Q(τ) π (1) K−1,π (2) (s, a(1), a(2)) ] π (1) K−1(a (1)|s)π(2)(a(2)|s)
+ ∑
a(1),a(2)
Q̃ (τ) ∗ (s, a (1), a(2)) [ π̃ (1) ∗τ (a (1)|s)− π(1)K−1(a (1)|s) ] π(2)(a(2)|s)
+ τ [ H ( π̃ (1) ∗τ (s) ) −H ( π (1) K−1(s) )] = γ
∑ a(1),a(2) [ π (1) K−1(a (1)|s)π(2)(a(2)|s)Es′∼P(·|s,a(1),a(2)) [ Ṽ (τ) ∗ (s ′)− V (τ) π (1) K−1,π (2) (s′) ]]
+ ( π̃
(1) ∗τ (s)− π(1)K−1(s)
)> Q̃ (τ) ∗ (s)π (2)(s) + τ [ H ( π̃ (1) ∗τ (s) ) −H ( π (1) K−1(s) )] ≤ γmax
s′
[ Ṽ (τ) ∗ (s
′)− V (τ) π (1) K−1,π
(2) (s′) ] + ( π̃ (1) ∗τ (s)− π(1)K−1(s) )> Q̃ (τ) ∗ (s)π (2)(s)
+ τ [ H ( π̃ (1) ∗τ (s) ) −H ( π (1) K−1(s) )] .
Applying maxs to both sides of the above inequality and rearranging it yields that
max s
[ Ṽ (τ) ∗ (s)− V (τ)
π (1) K−1,π
(2) (s) ]
≤ 1 1− γ max s
(( π̃
(1) ∗τ (s)− π(1)K−1(s)
)> Q̃ (τ) ∗ (s)π (2)(s) + τ [ H ( π̃ (1) ∗τ (s) ) −H ( π (1) K−1(s) )]) ≤ 1
1− γ max s
( fτ ( Q̃ (τ) ∗ (s); π̃ (1) ∗τ (s), π (2)(s) ) − fτ ( Q̃ (τ) ∗ (s);π (1) K−1(s), π (2)(s) ))
≤ 1 1− γ max s
( fτ ( Q̃ (τ) ∗ (s); π̃ (1) ∗τ (s), π (2)(s) ) − fτ ( QK−1(s); π̃ ∗(1) K−1, π (2)(s) ))
+ 1
1− γ max s
( fτ ( QK−1(s); π̃ ∗(1) K−1(s), π (2)(s) ) − fτ ( QK−1(s);π (1) K−1(s), π (2)(s) ))
+ 1
1− γ max s
( fτ ( QK−1(s);π (1) K−1(s), π (2)(s) ) − fτ ( Q̃ (τ) ∗ (s);π (1) K−1(s), π (2)(s) ))
≤ 1 1− γ max s ∣∣∣( max π(1)(s) fτ ( Q̃ (τ) ∗ (s);π (1)(s), π(2)(s) )) − ( max π(1)(s) fτ ( QK−1(s);π (1)(s), π(2)(s) ))∣∣∣
+ 1
1− γ max s
( fτ ( QK−1(s); π̃ ∗(1) K−1(s), π (2)(s) ) − VK(s) ) + 1
1− γ max s ∣∣∣fτ(QK−1(s);π(1)K−1(s), π(2)(s))− fτ(Q̃(τ)∗ (s);π(1)K−1(s), π(2)(s))∣∣∣ (i) ≤ 2 1− γ ( 2Qmaxγ K + 2γQmax 1− γ (1− ητ)T ) + 2Qmax 1− γ (1− ητ)T
≤ 2Qmax 1− γ
( 2γK−1 + 1 + γ
1− γ (1− ητ)T
) ,
where (i) uses eq. (131) and the following inequality that holds for all s, π(1)(s), π(2)(s), (ii) uses eq. (134) and VK−1(s) = fτ ( Q (τ) K−1(s);π (1) K−1(s), π (2)(s) ) .∣∣∣fτ(QK−1(s);π(1)K−1(s), π(2)(s))− fτ(Q̃(τ)∗ (s);π(1)K−1(s), π(2)(s))∣∣∣
≤ ‖QK−1(s)− Q̃(τ)∗ (s)‖∞ eq.(134) ≤ 2QmaxγK + 2γQmax 1− γ (1− ητ)T .
In Theorem 3, the convergence rates of both the Q function estimation error ‖QK−1−Q̃(τ)∗ ‖∞ and the function value gap maxs [ Ṽ (τ) ∗ (s)− V (τ)
π (1) K−1,π
(2) (s) ]
consist of two terms O(γK) and O(1− ητ)T , which characterize the exponential convergence rates of the K outer value iterations and the T inner policy updates respectively. Such a convergence result indicates that Algorithm 2 converges to the optimal solution to the regularized Markov game, and thus can be arbitrarily close to the optimal solution of the unregularized Markov game with sufficiently small τ . As a result, the PU algorithm Cen et al. (2020) is rational. Similar result can be directly extended to our stochastic policy extragradient (SPE) algorithm by applying the estimation error bounds in Appendix B.

Review summaries:
The authors consider two-player zero-sum Markov games. The goal is to develop decentralized, model-free, symmetric algorithm. With entropy regularization and new estimators, the authors show the stochastic policy extragradient algorithms have these properties and the sample complexity improves the sate-of-the-art. 

## Summary   This paper studies a decentralized stochastic policy extra-gradient algorithm for solving two-player zero-sum Markov game. In comparison to the standard policy extra-gradient algorithm, this algorithm uses a set of stochastic estimators to estimate the value functions involved in the stochastic updates. Improved sample complexity guarantee is also derived. 

This paper focuses on the two-player zero-sum Markov Game setting and proposes a stochastic version of the policy extragradient (PE). The PE algorithm, which solves an entropy-regularized minimax matrix game problem by predictive update (PU) [Cen et al., 2021], has been well studied under the deterministic case in the work of [Cen et al., 2021], proven to converge exponentially to a unique solution. However, with an inquiry into the full Q-table, and the full transition matrix P, the original PE algorithm has its limitations in practice.  The authors of this paper design a stochastic counterpart of the PE algorithm, the main sampling technique of introducing stochasticity is similar to the stochastic OGDA in [Wei et al. 2021] with several substantial technical improvements. Theoretically, by tightly bounding the estimation error via a novel error decomposition, this paper obtains a significant sample complexity of $\tilde{\mathcal{O}}(\frac{A_{\max}}{\epsilon^{5.5}(1 - \gamma)^{13.5}})$, compared with the previous state-of-the-art result $\tilde{\mathcal{O}}(\frac{A_{\max}^3 |S|^{10.5}}{\epsilon^8 (1 - \gamma)^{29.5}})$.