Provable Memory Efficient Self-Play Algorithm for Model-free Reinforcement Learning
Authors: Na Li
Yuchen Jiao
Hangguan Shan
Shefeng Yan
Venue: ICLR 2024 poster (2024)
Keywords: model-free RL
self-play
memory efficiency
Q-learning
Nash equilibrium
Markov policy
Primary area: learning theory
TL;DR: We design an algorithm that achieves memory, computational, and sample efficiency, and meanwhile has a low burn-in cost and outputs a Markov and Nash policy for two-player zero-sum Markov games.

Abstract: The thriving field of multi-agent reinforcement learning (MARL) studies how a group of interacting agents make decisions autonomously in a shared dynamic environment. Existing theoretical studies in this area suffer from at least two of the following obstacles: memory inefficiency, the heavy dependence of sample complexity on the long horizon and the large state space, the high computational complexity, non-Markov policy, non-Nash policy, and high burn-in cost. In this work, we take a step towards settling this problem by designing a model-free self-play algorithm \emph{Memory-Efficient Nash Q-Learning (ME-Nash-QL)} for two-player zero-sum Markov games, which is a specific setting of MARL. We prove that ME-Nash-QL can output an $\varepsilon$-approximate Nash policy with remarkable space complexity $O(SABH)$, sample complexity $\widetilde{O}(H^4SAB/\varepsilon^2)$, and computational complexity $O(T\mathrm{poly}(AB))$, where $S$ is the number of states, $\{A, B\}$ is the number of actions for the two players, $H$ is the horizon length, and $T$ is the number of samples. Notably, our approach outperforms in terms of space complexity compared to existing algorithms for tabular cases. It achieves the lowest computational complexity while preserving Markov policies, setting a new standard. Furthermore, our algorithm outputs a Nash policy and achieves the best sample complexity compared with the existing guarantee for long horizons, i.e. when $\min \\{ A, B \\} \ll H^2$. Our algorithm also achieves the best burn-in cost $O(SAB\,\mathrm{poly}(H))$, whereas previous algorithms need at least $O(S^3 AB\,\mathrm{poly}(H))$ to attain the same level of sample complexity with ours.

Published as a conference paper at ICLR 2024
PROVABLE MEMORY EFFICIENT SELF-PLAY ALGO- RITHM FOR MODEL-FREE REINFORCEMENT LEARNING
Na Li Yuchen Jiao", Hangguan Shan',Shefeng Yan
1 College of Information Science and Electronic Engineering, Zhejjang University, Hangzhou, China School of Information and Electronics, Beijing Institute of Technology, Beijing, China 3 'Institute Acoustics, Chinese Academy of Sciences, Beijing, China
ABSTRACT
The thriving field of multi-agent reinforcement learning (MARL) studies how a group of interacting agents make decisions autonomously in shared dynamic environment. Existing theoretical studies in this area suffer from at least two the following obstacles: memory inefficiency, the heavy dependence of sample complexity on the long horizon and the large state space, the high computational complexity, non-Markov policy, non-Nash policy, and high burn-in cost. In this work, we take step towards settling this problem by designing a model-free free self- play algorithm Stemory-Ffficienn Nash Q-Learning (ME-Nash- QL.) for two-player zero-sum Markov games, which is a specific setting of MARL. ME-Nash-ON aas--LL is proven to enjoy the following merits. First, it can output an s-approximate Nash policy with space complexity O(SABH) and sample complexity Ö O(H AB//²)) where S is the number of states, {A, B} is the number of actions for two players, and H is the horizon length. It outperforms existing algorithms in terms space complexity for tabular cases, and in terms of sample complexity for long horizons, i.e., when min A, B} < 112. Second, ME-Nash-QL achieves the lowest compu- tational complexity O(T')o)(AA)) while preserving Markov policies, where is the number of samples. Third, ME-Nash- also achieves the best burn-in cost AB poly(H),, whereas previous algorithms have a burn-in cost of least O AB poly (H)) to attain the same level of sample complexity with ours.
INTRODUCTION
In this paper, consider the problem of multi-agent reinforcement learning (MARL), which focuses on developing algorithms for multiple agents to learn and make decisions in multi-agent environ- ments. MARL has attracted plethora of attention across various domains, including autonomous driving Shalev-Shwartz et al. (016)), game playing (Silver et al.) 2017). and social systems (Baker et al. 2020). Considering that online data collection, storage, and computation can be expensive, time-conumiing or high-stakes in the above applications, achieving memory efficiency and low sam- ple and computational complexity important online MARL scenarios. Generally, the approaches to solving MARL can be categorized into model-free and model- methods. The former involves directly learning an optimal/equllibrium policy for multiple agents without explicitly modeling the environment, such as friend-or-foe Q- Q-Learning (Littman 2001) and Nash Q-Learning (Hu & Wellman Nov. 2003). They typically involve using techniques such as Q-learning, actor-critic methods, or policy gradients to optimize the policy. The latter relies on learned predefined model of the envi- ronment. This usually involves estimating state-transition probabilities and rewards based on agent behaviors and then utilizing these estimations to simulate possible results and choose actions, such as AORPO (Zhang et al. 2021) and OFTRL (Zhang et al.) 2022). Although recent research (Bai et al. 2020: Jin et al. 2022 Liu al. July 2021 Xie et al. Jun. 2022) has demonstrated the effectiveness of both model free and model based algorithms in MARL, a more comprehensive understanding of efficient memory, optimal sample complexity and minimal computational complexity is still lacking.
As a specific setting of MARL, two-player zero-sum Markov games (TZMG) are a fascinating area of research. Considering a tabular TZMG with S states, actions {A, B) for two players, and

---

Published as a conference paper at ICLR 2024
Table 1: Sample complexity (the order of the regret bound, modulo log factors), computational/space complexity, the range of samples to attain Ö( ( -sample complexity, and whether the output
policy is the Markov/Nash policy, for algorithms: V-learning (Jin et al., (022). Nash V/Q-learning (Bai et al. 2020), PRefI/PReBO (Cui et al. 2023), OMNI-VI (Xie et al. Jun. 2022), NaRh-UCRL
(Chen et al. 2022). Optimistic PO (Qiu al., (02I), VI-ExploreVI--UCL (Bai & Jin 2020),
Nash- VI (Liu et al. July 202I). and Q-learning (Feng et al. 2023). The best results are highlighted.
Range of samples
Markov/
Sample
Computational/ space complexity
Algorithm
to attain H'S/22
Nash
complexity T
sample complexity
policy
V-learning
H B)/E²
Tpoly S(A + BYT
Nash V-learning
H'S B)/E²
No/No
Tpoly(ABy
Nash Q-lcarning
SAB/E2
SABT
PSA
PReFI
HA + B)%
Never
S(A BYHT
Yes/No
PReBO
5 + B)
SABHT
OMNI-VI
A"
Tpoly(SAB),
Nash-UCRL
A"
B2
Optimistic PO
H'SAAB/E H²
Tpoly(SABy
Yes/Yes
VI-Explore
S
PPAD-complete/
VI-ULCB
#PS2AB/E*
ABB
PSABY
Nash-VI
ASH
S ABH
Q-learning (Feng et al. 2023)
SAB/E
11 "ell'poyySAAI
[S o0)
No/No
SA B H
Tpoly ABY SABH
ME-Nash-O QL
[SABH .00)
Yes/Yes
horizon length of H, one important aspect of it is the sample complexity, which refers to the number of samples T required to achieve an e-approximate Nash equilibrium (NE). Currently, the Q-FTRL algorithm (Li et al., 2022), which employs generative model, is the leading method for achieving optimal sample complexity in TZMG. However, the accessibility of the generative model is unclear and restrictive. In the absence of flexible sampling mechanism, the self-play
algorithms with minimal sample complexity are the model-free method V-learning (Jin et al. 2022) and the model-based method Optimistic Nash Value Iteration (Nash-VI (Liu et al.) July 202ID. along with the FTRL idea (from adversarial bandit, i.e., H = 1) and a different style of bonus term, respectively. V-learning is able find e-approximate policy with sample complexity of ((++ (modulo log factors), but the output policy is non- Morakvioov..n. Nash- VI achieves the best sample complexity 0 SAB/ssB/ee ) among model-based algorithms so far, while its burn-in cost S ABH has heavy dependence on S. Besides, the computational complexity of Nash- VI is OoT (SAB), higher than T (oly((A)) in V-learning. Moreover, the space complexities of the above algorithms are unsatisfactory, with the former's (SS(A+ BYT) increasing with the number of samples T and the latter's O(S2 AB H) relying heavily on S. These complexities are large compared with the space (BSAB)) required by Q-value tabular cases, A summary of prior results is shown in Table [ Thus, a natural question motivated by prior algorithms to pose is:
Can a TZMG algorithm be designed with memory, sample, and computational efficiency, while having low burn-in cost and a Markov and Nash output policy?
1.1 CONTRIBUTIONS
We contribute the advancement of theoretical understanding by providing sharp analysis of the model-free algorithm on TZMG. Our main contribution lies in the development of novel model-free algorithm with Markov and Nash output policy and theoretically achieves the best space and
2

---

Published as a conference paper at ICLR 2024
computational complexities and the superior sample complexity compared to existing methods for long horizons, i..,, min A, B} < H². Specifically, we summarize our main contributions as follows.
We design a model-free algorithm Memory-Eificient Nash Q-Learning (ME-Nash-QL)) which is generated from Nash Q-learning, along with the carly-settlement method designed and the reference-advantage decomposition technique incorporated in TZMG for the first time. ME-Nash- QL firstly achieves the best memory complexity O ((SBH)), corresponding to the minimum space to store Q- Q-values in tabular cases. Furthermore, the computational complexity of our algorithm is ( (oly(AA)) which is lower than that of prior algorithms.
We prove that ME-Nash- QL can find an s-approximate NE for Markov games with sam- ples Ö(H* SAB/E), which is equivalent to achieving the regret bound Ö(v O(HHSSABT) provided that samples T exceeds (SSAB We remark that the sample complexity of ME-Nash-QU QL has an optimal dependence on H and S. According to TT it outperforms existing algorithms as long as min A, B} < H Compared with Nash-VI VI with the same sample complexity Ö(H SAB/E²). Nash- VI requires T to be larger than Ö(S " to attain the above sample complexity, which is generally significantly larger than that of ME-Nash-QL- as S > 11. These conditions are common and are satisfied in many scenarios. For example, in Go, there is 150 < H < 722, S = 2361 and min A, B} 360 (Silver et al. 2017). Similar examples include Atari games and Poker.
Unlike the state-of-the-ar model-free algorithms such as Nash V/Q-Learning our algorithm outputs both the single Markov policy and Nash policy (instead of a nested mixture of Markov policies returned by Nash V-Learning). Overall, Table[ that our algorithm outperforms all previous algorithms with a Markov and Nash policy in terms of space, sample, computational complexity, and burn-in cost. We design an extended algorithm of ME-Nash- -LL for multi-player general-sum Markov games and achieve an c-optimal policy in Ö(H*S [IEE[ A1/²)) samples with M players and A; actions per player.
1.2 RELATED WORK
Markov games Markov games (MGs), also known as stochastic games, were introduced in the early 1950s (Shapley 1953). Since then, numerous studies have been conducted, with a particular focus on Nash equilibrium (Littman 1994; Lee et al. 2020). However, these studies are based on two strong assumptions. First, transition and rewards are generally assumed to be known and partly based on the asymptotic setting with an infinite amount of data. Under the curse of dimensionality, the con-asympootic setting is an important component of relevant research, and the transition and reward should be estimated under a limited amount of data. Second, some work makes strong reachability assumptions and fails to consider the impact of exploration strategies. The agent can sample transition and rewards for any state-action pair based on the assumption of accessing simulators (generative models). For example. (Jia et al. 2019 Sidford et al. Aug. 2020 Zhang et al., 2020a) derive non-asymptotic bounds for achieving E E-approximate Nash equilibrium based on the number of visits to the simulator. Especially, (Wei et al. 2017) studies MGs assuming that one agent can always reach all states using a certain policy under the compliance of the other agent with any policy.
Non-asymptotic guarantees without reachability assumptions As the milestone for MGs, (Bai & Jin] 2020) and (Xie et al. Jun. 2022) firstly provide non-asymptotic sample complexity guarantees for model-based algorithms (e.g.. Vi-Explore and VI-ULCB) and model-free algorithms (e.g.. OMNI- VI), respectively. These are investigated further by the Nash- VI and Nash Q/V-Learning and provide a better sample complexity guarantee. Nash V-learning achieves sample complexity that has optimal dependence on S, A, and B, but the dependence on H is worse than ours. Nash-V VI has the same complexity as ours, but requires space complexity O (BH). Besides, Nash- UCRL obtains sample complexity with near-optimal dependence on H. Optimistic PO gets VT-regret. PReBO has space complexity for the storage of historical policies. OMNI-VI has O A2 B²T) space complexity. However, neither of them achieves optimal dependence on S. A, or B. The detailed comparison is shown in Table I During the preparation of our work, observed that (Feng et al.) 2023) also employs Coarse Correlated Equilibrium (CCE) and seference-advanttae decomposition technique, with a higher burn-in cost and outputting policies neither Nash nor Markov.
3

---

Published as a conference paper at ICLR 2024
Multi-player general-sum Markov games (Lu et al.
developed model-based algorithm with sample complexity O(H 52 L A,/c² which suffers from the curse of multi-
July 2021
agent. To alleviate this issue, (Song al. 2021 Mao al. 2022 Mao & Başar 2023 Cui et 2023
Wang et al. )023) proposed V-learning a algorithms, coupled with the adversarial bandit subroutine, to break the curse of multi-agent. Among them, the best sample complexity is ( S Ihe A;/c²)
achieved by (Song et al. (022)) In addition, (Daskalakis et al.) 2023 with sample complexity
Ö(H 53 [[E[M As/e²) learned approximate CCE that is guaranteed to he Markov.
Single-agent RL
There is rich literature on reinforcement learning in MDPs (see e.g., Jaksch
et al. April 2010 Osband et al. 2016 Azar ct al. 2017 Dann et al.) 2017 Strehl et al., |2006] Jiin et al. 2018a Li et al.) Dec. 2022). MDPs are special cases of Markov games, where only a single agent interacts with a stochastic environment. For the tabular episodic setting with non-stationary dynamics and no simulators, regret and sample analysis are the commonly adopted analytical paradigm for the trade-off between exploration and exploitation. Notably, the lower bound of the regret is v VH25AT AT, corresponding to the sample complexity OHH$SA/E")) SA/=²), which has been achieved by the model-basee algorithm in (Azar al. 2017) and the model-free algorithm in (Li et
Dec. 2022).
2 PROBLEM FORMULATION
In this paper, we consider the tabular episodic version of TZMG problem. Specifically, we denote a mnite-horizon TZMG as M = (S.A, B, H. (Pr) fr 1-1). Here == f1..... ,S} is the state space of size S, (A = f1.... .A).B = {1.... B}) denote the action spaces of the max- player and the min-player with size A and B. respectively, H is the horizon length, and Pa. = S S A x B + (rS(rppp. Th == S A x B - [0. 1)) represents the probability transition kernel (resp. reward function) at the h-th time step, 1 S h S H. Moreover, (. a, b) E (SS) stands for the transition probability vector from state at time step when action pair (a, b) is taken, while (s, a, 6) indicates the immediate reward received at time step h on state-action pair (s, a, 6) (which is assumed to be deterministic and falls within the range [0, 1)). For TZMG, this reward can represent both the gain of the max- max-player and the loss of the min-player.
1H
Markov policy of the max- the action selection rule at time step h. Similarly, a Markov policy of the min-player is defined as {un, 1== with in == - Ag. Each player executes the MDP sequentially
is represented by μ {ur [_ where μ4N S - AA is
a total number of K episodes, leading to T = KH samples collected in total. Moreover, in each episode k = 1,...... K, we start with an arbitrary initial state of. and both players implement their own policy μ {1% hml and u* = 1 learned based on the information up to the (k: 1)-th episode.
Value function. V. (s) S + IR is denoted as the value function and gives the expected cumulative rewards received starting from state s at step under policy μ and v:
Σ>=_ The The (sw aw bw) Sn
H
Vi (s) = Ey,,
(1)
where the expectation taken over the randomness of the MDP trajectory (s, h H). We also define QK A x - to be the action-value function (a.k.a the Q function). Q (s)a,b) gives the cumulative rewards under policy and v, starting from (s, b) at step h:
(s, a b) EEp, Σ H
M=n Σ
Th (Sk,, ask bw) 8h. 8, an =a, by. =
(2)
We define VR. (s) QH1 1 (s, b) 0 for any a and and (s, a, b) S A x B. Moreover, (- (1)) Q( b) for any Q function. Thus, have the Bellman equation
define (s) = (a.b)~rr(
0 a, = rn(s, a. b) + (.s (V)) (s (Dus.es 21(²)(s) (3)
Best response and Nash equilibrium. For any policy of the max- max-player μ., there exists the best response of the min-player, which is policy vf (n) satisfying ( (")(s inf, V.' (s) for any (s, h) 8 [H). For simplicity, we denote Vut = Vau."(n) By symmetry, we define (V) and
4

---

Published as a conference paper at ICLR 2024
Vit" in similar way. It is further known (cf. Filar & Vrieze, 2012) that there exist policies μ² and 1² that are optimal against the best responses of the opponents, in the sense that
Vi 1 (s) sup, V/+((s) Vi (s) = inn, V (s), for all (s, (s,
(4)
These optimal strategies (n", v*) are the Nash equilibrium of the Markov game satisfying:
sup, inf, (s) = V." (s) sup, (s).
(5)
A Nash equilibrium gives a solution in which player has anything gain by changing only its own policy. We denote the values of Nash equilibrium Vid ,²" and 0% .r' as V and Ti respectively.
Learning objective. We use the gap between the max- player and the min-playee under the optimal strategy (i.e., NE) as the learning objective, which can be expressed as V/ (st) V.R. (s*). Our goal is to design an algorithm that can find an e-approximate NE using several episodes under the space complexity SABH H and computational time 7 poly (alyy(All) (AB) with output policies of two players that are independent of past and independent of each other (i.e.. Markov and Nash policy), and achieve regret that is sublinear in T KH and polynomial in S, A. B, H (regret bound).
V1- (ot)) S. then Definition (s-approximate Nash equilibrium) If K ΣE=1 -
the pair of policies (ft D) is an e-approximate Nash equilibrium.
Definition 2 (Regret) Let (p² v²) denote the policies deployed by the algorithm in the k-th episode. After a total of episodes, the regret is defined as
Regret(K) = =>
== (ntie* - vtt (sf).
(6)
Notably, sample complexity 7 refers to the required number of samples to achieve Regret (K S e.
Notation. Before presenting our main results, we introduce some convenient notations used through- out this paper. For any vector r E S&AB that constitutes certain quantities for all state-action pairs, we use (8, a, b) to denote the entry associated with the state-action pair (s, a, b). We shall also
Ph.s.a.b = Pr(-1as a, b) R
(7)
abbreviate the transition probability vector given the (s, a, b) pair at time step h. Additionally, e, is denoted as the i-th standard basis vector with the i-th entry equal to I and others are all 0.
ALGORITHM AND THEORETICAL GUARANTEES
In this section, present the proposed algorithm called ME-Nash-QU and provide its theoretical guarantee of memory and sample efficiency.
3.1 ALGORITHM DESCRIPTION
We propose a model-free algorithm ME-Nash-QL. described in Algorithm [ which is the first to integrate the reference-advantage decomposition technique to TZMG along with an innovative early-settlement approach. For the n-th visit of state-action pair at any time step h, the proposed algorithm adopts the linearly rescaled learning rate as H+n In each episode, the algorithm can be decomposed into two parts, i.c.. policy evaluation and improvement, which are standard in the majority of model-free algorithms.
H+1
Lines 4-12 of Algorithm| I (Policy evaluation): Select actions based on the current policy to obtain the next state and the reward information. The sampled data then used estimate several types of Q-function: Q and QJCB with an exploration bonus, Øº and Q using the reference-advantage advantage decomposition, and Qn and Q,. which are obtained by combining the above estimations.
Lines 13-19 of Algorithm (Policy improvement): Compute new (joint) policy Ty using the estimated value functions, update those value functions, and perform updates of reference values under the early settlement.
5

---

Published as a conference paper at ICLR 2024
Q-function estimation In each episode, the algorithm is designed to maintain estimates of the Q function with low sample complexity that provide optimistic and pessimistic views (namely, over-estimate and under-estimate) of the truth Q²". The algorithm aims to reduce the bias Q ---Q Q" and Q Q' in two ways. Firstly, we migrate the Q-learning algorithm with the upper-confidence bound (UCB) exploration strategy proposed in (Jin et al. 2018a) to Q-learning with UCBB/lowrr-confcdeee bound (LCB) exploration strategy. This is expressed as the subroutine update-qO with bonus
6x Cb H log SABT in Algorithm Secondly, we leverage the idea of variance reduction to shave the H factor of sample complexity compared Nash Q-learning based reference-advantage decomposition (Zhang et al. (2020b) in single-agent scenarios. Taking UCB as an example, we adopt the update rule each time step
Un (s, a, b)- a b) ra(s Phaaaa
A ++1)+ [Pa h+1 b)t (8)
R where bj is the exploration bonus, V.lt A+2 1 is the reference value introduced next, and Pr.s, (V h+1 V h+1 (s') with Phy,,a,b b as the estimate of Pr.,,,,b Vh+t)) is the stochastic estimate of V h+1 (5")
Besides, the term Ps 4+1 indicates an estimate the one-step look-ahead value PAV h+11 which can be computed via the batch data like line 12 in Algorithm Accordingly, combine the UCB V.
PA
for Ph (V - V h+1) and Pr. h+1 together as the exploration bonus term hp-
Thus, based on QUCB, QLCB Q² and Q we can combine them as line 1 11-12 in Algorithm to further reduce the bias without violating the optimism or pessimism principle of Q-function estimate.
Algorithm 1: Memory--fficiine Nash Q-Learning (ME-Nash-QL)
Parameter: some universal constant c > 0 and probability of failure å E (0, 1)
Initialize: (s, a, b), Q
(s, a, b), Q (s, b). < H: Q (s, a, b), Of (s, QL b)+ 0; V.(s)) (s) 11: (s),, (s) Nu
(s, b). 3n (s, a, b), (s, (s, of (s. b) (s b), of a. b). - (s (s
2 (s, b), B (s. a, b), (s, <- 0: and (8) True for all
(s, E E S A B [H].
for Episode k= =,....,, do
Set initial state 81 < =
for Step 1,.., H do
Take action (an, by) ~ Th (. (sn), and draw sh41 ~ Po(. (-11 sh, an. bn). Nr an, by) t (s,,,, an, bn) + 1; +- (sh, bn); Vn x- 11
H+n
[QUCB Q8.B] (sh, an. by)) update-q ().
Qh an; bn) update-ur ()-
(RR,, an, bn) + update-Ir ().
10
(sh, an, bn) + min (Q) (sh an, bb), ( an, bn), (Sh an bn)
11
2, (Sn,an ah, bn) <- max (Q on, bn). QLBB an, bn), ; Q, (sh, an, bn)).
Qn (Sh, ahe bn) = min 12 (sh, an, bn), Q QUCB(SN an, bn)} and
13
2, (Sh, an, bb) = max (Q) (sh, an. by), Q1 (s an. by)) then
Th(s (1hh) +- CCE((u (Sh.", " ),,2 (Shr
Va(sn) t- min( (sn). (.).))))..()))) Va(sn) + max( (sh). if VV (s() then
15
( +- VA(s);; (R) + (s()).
18
else if (, )- = True then A (s)) + Va(Sn): (R((s)) (n(sn): u,(sn) False.
Output: The marginal policies of {TTA 1H (Lun) (P

---

Published as a conference paper at ICLR 2024
Algorithm 2: Auxiliary functions
Function update- ( [[Q QkCB] (sh, ar bn); [V h+1, Mntzl (sh+1)): 1))
Q (sh; an, bn) f- (1-7)) QL (sh, on, bn) +7mm (rn (8h, an, bn) + V b+l (sn+1 +bm);
QL
(sh, ahe bb) 6 (1 1/.)) QLCB (sh; , on, bp) +m (rn (Sh,an,
an, an,bn) V h+1 (8h+1) 1-11)-4) bn)-
oho tho aa a Phe Vh: BR On R (sh; any bn); V Ntt1 Va+i (sh+1) R BB (sh,anbb)),
Function update-ur
(sn. b/ update-q--attt bonus (oh On (sh: un. bn)) + (1 the) 2% (0h: "h: un,bn) + Tn (% (sh: an, bb) + Va+1 ($u+1)= Vhtt ($h+1) + 3 (sh, an, bn) + bx
V h+ n+1 (88+1);
Function update-1r r ([e% Eh Ln Ln. BR, 28. (sh; an, bn), [L Ln+1] (#h+z)): (sn,an, .b updato-q- b-bous (00 12 OR (sh; an, bn) t (1 Th)) 2thh (sh: an bn)
26 2 f Bi (sn (V Vn+ ( I(snti)):
Vn Th (sh; an,lni bn) + Vn+i (SK+1)
vh+t (88+1) + of (8h, an bn) LR
Function update- q bonus ( phh who 2h, vh: BR (sh, ahe bn), [VM Vn-1 (sh+1)):
10
11
5% (sh, an, bn) <- (1 ) 0f (sn, On, bn) + 1 1V
n h+1 (SK+1);
4% (sh. ab: bn] + (1 - n 1% (sh, an bn) + 1 (V
h+1 (sh+1))
12
13
0% (sh, an, bb) t (1 TTn) 2f (sh, an, bn)
+ Tn (Vu+1 (8N+2) - V.B
h+11 (81+1));
v (sh, an, bn) + (1 mma) with (sh. ane bp) + The (Vh+1 (92-1)
V/ (3
14
By Beemp (shr ah. bn) t Cb.
log² SABT
V 1h (sh, an. bn) - (0% (sh, an, bx +
15
log² SABT
v H V 16t (sh, an, by) (1f (Sh, ab, bn))
9h (Shs an, (nnbb))) bn) B,m (sh; an, bn) - BR (sh, ahe bn);
16
Bl (Sh, ah, bn) + Brenn (sh, ah, bn))
17
BR + B (sh: an, bb) + (1 - nm) o (en
H2 log" SABT 3//
18
cb
nn
Reference values update Motivated by Li et al. Dec. 2022), we implement the following appropriate termination rules to allow for the early settlement of the reference values V and VR.
(*)) - V., (sn) 1
which is displayed in lines 16-19 of Algorithm [ Notably, due to references and the early settlement, our algorithm obtains a lower sample complexity and burn-in cost than Nash Q-learning.
Weaken the dependency of the sample complexity on H: the uncertainty of the update rule largely stems from the third and fourth terms on the right-hand side of (8). The reference
value V/l (resp. V/Al) stays reasonably close to Vn (resp. Kn), which suggests that the standard deviation of the third term is small. For the fourth term, the reference value is fixed and never changes after satisfying condition (lines 16-19 in Algorithm 1) for the first time, R and can all the samples collected to estimate PA f++11 Therefore, both of these two terms have much smaller variances than that of usual UCB/LCB value functions due to the incorporation of reference terms, which enables the algorithm to estimate them with high accuracy with a limited number of samples.
Reduce the burn-in cost: reference value VR (resp. VRB used to keep tracking the value of Vn (resp. V₁,) before it stops being updated. Based on the early-settlement method, the reference values will stop being updated shortly after the condition (lines 16-19 in Algorithm 1) met for the first time. As a result, the algorithm has the ability to quickly settle on a desirable "reference" during the initial stage. Moreover, the aggregate difference between v-ik (resp. V-R. and the final reference %. (resp. V-R.K, over the entire trajectory can be bounded in reasonably tight fashion.
7

---

Published as a conference paper at ICLR 2024
Policy computation We apply a relaxation of the Nash equilibrium Coarse Correlated Equilib- rium (CCE) to output a single Markov policy rather than a nested mixture of Markov policies, which is introduced by (Moulin& & Vial Sep. 1978) and developed by (Xie et al. Jun. 2022). Specifically,
for any pair of matrices Q E 00 HJ A CCE(Q. Q) returns a distribution æ E Axx such that
E ((a,b)== (s, b) =(a,b)== (s)d(.)) Va',
(10a)
E [(a,b)==Q (s, a, =(a as, A9'.
(10b)
Intuitively, no one can benefit from unilateral unconditional deviation in a CCE since the players' action strategies have underlying correlation, unlike in Nash equilibrium where each player's strategy is independent. Another advantage of a CCE is its ability to obtain results in polynomial time through linear programming. Moreover, since Nash equilibrium always exists, and a Nash cquilibrium is also a CCE, we can conclude that CCE always exists as well. We would like to recommend readers interested in the detailed computation of CCE refer to (Xie al.
Jun. 2022).
Specifically, line 14 is used for computing our output policies. These final policies (J4, v) are simply the marginal policies of πTЧ. That is, for any given (s, h)) S x [H], we have yn (-1s) := EBEB Th( bls) and 1% (-[s) := Eae a Th (a, ((s). In contrast to previous algorithms that require space complexity dependent on to generate a generic history-dependent policy, which can only written as a nested mixture of Markov policies. our algorithm has the ability to produce a single
Markov policy with space complexity O(SABH))
3.2 MAIN RESULTS
We begin by proving the theoretical guarantee of ME-Nash-OU LLash--Q... by the following theorem.
Theorem Consider any ō E 10, and suppose that eb 0 is chosen to be a sufficiently large
universal constant. Then there exists some absolute constant Co > such that Algorithm 7 achieves
K
(ytia (s V/th:t(s) ((())) SE
(11)
K km
the number of samples T satisfies
H SAB
SABT
S'BAB
SAB log 8
T Co
log"
(12)
g2
8
with probability at least
Sample complexity and burn-in cost
The sample complexity 112 can be simplified as
Ö (H*
(13)
for sufficiently large T. Moreover, our algorithm achieves the best burn-in cost O(SABH1)) which is the minimum sample size to guarantee that the sample complexity of the algorithm is near optimal. This corresponds to Regret ()) I 2(H2SABT) as Section 1.1. And the state-of-the algorithm has a burn-in cost of at least Õ(S ABH to attain the O(HA)) ( >sample complexity.
self-play
Theorem I guarantees that the average Nash gap is smaller than with sample complexity in (13) For supplementary, the following theorem provides the theoretical guarantee of an actual output policy.
Theorem 2 Consider the policy nt = (n*" .1 with k- arg ming (Vi vi( If we take R² as the output marginal policy, for any 8 (0, 1), with probability least there is vl.ck
((xt") V (sf v (st)) s Ōō O (VHSSABT)
Besides, our algorithm can be extended multi-player general-sum Markov games with m players and A, actions per player with details in Appendix F called Multi-ME-Nash-OO NL. We can obtain the following theoretical guarantee of Kulti-ME-Nash-OL as
Theorem Consider any E (0, and suppose that cb > 0 is chosen to be a sufficiently large universal constant. Then there exists some absolute constant Co such that Multi-ME-Ne QL
achieves sample complexity Ō HH 1= A, with probability at least 1 - 8.
8

---

Published as a conference paper at ICLR 2024
Memory efficiency, computational complexity, and Markov/Nash policy ME-Nash- -L achieves space complexity O(SABH), which is essentially unimprovable in the tabular case if the Q-values stored. To the best of our knowledge, this is the first time that such complexity has been achieved along with the delivery of a Markow/Nash policy. Furthermore, the computational complexity of our algorithm is ((Tpoly(AB)) which is due the CCE computation by linear programming in polynomial time (poly (AB)). In comparison, although the previous algorithm Nash- VI also achieves same sample complexity, it has significantly larger space complexity of O(SAABI) due to its model-base nature, along with larger computational complexity (A))).(SABB).
ANALYSIS
In this section, we outline the main steps needed to prove our main result in Theorem with detailed proof in Appendix A.3.2 To simplify the presentation, we have ignored the dependency on & in Algorithms and Next, we need to be more explicit with the following notations for completion.
(i) (5% ah, b is denoted as the state-action pair encountered and chosen at step h in the k-th episode.
(ii) T (s. a, 6). (s, a, b), Th
R.k (s, b). 2. (s, a, b) and (s). (s) denote, resp.. 2n a, b).
2, (8, a, b), oh (s, a, b). O (s, b) and (s)),, (8) at the beginning of the k-th episode.
Step 1: regret decomposition. We can obtain
Regret (o)ett(K== (K) > K
1= (vitt* virh = k- @haii a bb) - a (/)
K
with S (a,d))n ( (5% b) a 2 at bt) (see Appendix A.3.2 for details).
Step 2: managing regret by recursion. The regret can be further manipulated by leveraging the update rule of Qn and Q This leads to a key decomposition as summarized as Lemma 5 in Appendix A.3.2 and proved in Appendix D
Step 3: controlling the terms in Step 2 separately. Each of the terms in Step 2 can be well controlled, We provide the bounds for these terms as Lemma in Appendix [ and summarize them in Appendix [A..2]] To derive the above bounds, the main strategy is to apply the Bernstein-type concentration inqqualities carefully, and to upper bound the sum of variance.
Step 4: putting all this together. We now establish our main result. Taking the bounds in Step 3 together with Step 2, we see that with probability at least - ô and a constant Co > O, one has
( VHHSSBBTOo SABT/6 + SAB log SABT/8
Regret (K) < Co
(14)
Theorem is proved under sample complexity with e average regret (i.e., 1 K Regret(K)) S E).
CONCLUSION
In this paper, we propose a novel model-free algorithm ME-Nash-QL. for two-play zero-sum Markow games and provide sharp analysis. ME-Nash- Maash-QL boasts several advantages over previous algorithms. First, to the best of our knowledge, it is the first TZMG algorithm that attains minimal space complexity O(SABH). In addition, can effectively produce an e-approximate Nash equilibrium of TZMG in O(H*SAB/e" samples of game playing, along with the computational complexity O(Tpoly(AB)) This near-optimal sample complexity of the algorithm comes into effect as soon as the sample size exceeds SABH10, which is the best burn-in cost compared to the previous algorithms with the same sample complexity. Further, it outputs a single Markov and Nash policy, which is a departure from previous algorithms that output nested mixture policies or non-Markov policies. There are some compelling future directions. For example, can we achieve model-free MG algorithms with O(A+ B) sample complexity (thus breaking the curse of multi-agent in the extension to multi- player general-sum MGs) without compromising the performance of existing metrics? How can we design independent actions with this sample complexity? We leave these problems for future work.
9

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
We thank Gen Li for helpful discussions and paper feedback. The work was supported in part by the National Natural Science Foundation of China (NSFC) under Grants U21B2029 and U21A20456, in part by the China Postdoctoral Science Foundation under Grant Number 2023M730264, and in part by the Zhejiang Provincial Natural Science Foundation of China under Grant LR23F010006.
REFERENCES
Mohammad Gheshlaghi Azar, Ian Oshand, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In International Conference on Machine Learning, pp. 263-272, 2017.
Yu Bai and Chi Jin, Provable self-play algorithms for competitive reinforcement learning. In International conference on machine learning, pp. 551-600. PMLR, 2020.
Yu Bai, Chi Jin, and Tiancheng Yu. Near-optimal reinforcement learning with self-play. In Proceed- ings of the 34th International Conference on Neural Information Processing Systems, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 978171 13829546.
Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch. Emergent tool use from multi-agent autocurricula. In International Conference on Learning Representations, 2020.
Zixiang Chen, Dongruo Zhou, and Quanquan Gu. Almost optimal algorithms for two-player zero-sum linear mixture Markov games. In International Conference on Algorithmic Learning Theory, pp. 227-261. PMLR, 2022.
Qiwen Cui, Kaiqing Zhang, and Simon Du Breaking the curse of multiagents in large state space: RI in markov games with independent linear function approximation. In The Thirty Sixth Annual Conference on Learning Theory, pp. 2651-2652. PMLR, 2023.
Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. In Advances in Neural Information Processing Systems, pp. 5713 17233 2017.
Constantinos Daskalakis, Noah Golowich, and Kaiqing Zhang. The complexity markov equilibrium in stochastic games. In The Thirty Sixth Annual Conference on Learning Theory, pp. 4180-4234. PMLR, 2023.
Songtao Feng, Ming Yin, Yu-Xiang Wang. Jing Yang, and Yingbin Liang. Model-free algorithm with improved sample efficiency for zero-sum markov games, 2023.
Jerzy Filar and Koos Vrieze. Competitive Markov decision processes. Springer Science & Business Media, 2012.
David A Freedman. On tail probabilities for martingales. the Annals of Probability, pp. 100-118. 1975.
Junling Hu and Michael P Wellman. Nash Q-lcarning for general-sum stochastic games. Journal of Machine Learning Research, 4:1039-1069, Nov. 2003.
Thomas Jaksch, Ronald Ortner. and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11:1563-1600, April 2010.
Zeyu Jia, Lin F Yang, and Mengdi Wang. Feature-hased Q-learning for two-player stochastic games. arXiv preprint arXiv: 1906. 00000,0003..... 2019.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is Q-learning provably efficient? In Advances in Neural Information Processing Systems, pp. 4863-4873 4873, 2018a.
Chi Jin, Zeyuan Allen-Zhus Sebastien Bubeck, and Michael Jordan. Is Q-learning provably efficient? arXiv preprint arXiv: 1007 03766, 2018b.
10

---

Published as a conference paper at ICLR 2024
Chi Jin, Qinghua Liu, Yuanhao Wang. and Tiancheng Yu. V-learnigg simple, efficient, decentralized algorithm for multiagent RL. ICLR 2022 Workshop on Gamification and Multiagent Solutions, 2022.
Chung- Wei Lee, Haipeng Luo, Chen- Yu Wei, and Mengxiao Zhang. Linear last-iterate convergence for matrix games and stochastic games. arXiv preprini arXiv:2006.09517 2020.
Gen Li, Yuejie Chi, Yuting Wei, and Yuxin Chen. Minimax-optimal multi-agent RL in Markov games with generative model. In Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 15353-15367. Curran Associates, Inc., 2022.
Gen Li, Changxiao Cai, Yuxin Chen, Yuting Wei, and Yuejie Chi. Is Q-learning minimax optimal? tight sample complexity analysis. Operations Research, 2023.
Gen Li, Laixi Shi, Yuxin Chen, and Yuejie Chi. Breaking the sample complexity barrier to regret- optimal model-free reinforcement learning. Information and Inference: Journal of the IMA, 12 (2):969-1043, Dec. 2022. ISSN 2049-8772.
doi: 10.1093/immaia/aaac004..
Michael L Littman. Markov games as framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pp. 157-163 Elsevier, 1994.
Michael L. Littmmn. Friend-or-foe Q-learning in general-sume games. In Proceedings of the Eighteenth International Conference Machine Learning, pp. 322-328, San Francisco, CA, USA, 2001. Morgan Kaufmann Publishers Inc. ISBN 1558607781.
Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin. A sharp analysis of model-based reinforcement learning with self-play. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th Inter- national Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 7001-7010. PMLR, July 2021.
Weichao Mao and Tamer Başar. Provably efficient reinforcement learning in decentralized general- sum markov games. Dynamic Games and Applications, 13(1):165-188) 2023.
Weichao Mao, Lin Yang, Kaiqing Zhang, and Tamer Basar. On improving model-free algorithms for decentralized multi-agent reinforcement learning. International Conference on Machine Learning, pp. 15007-15049. PMLR, 2022.
H. Moulin and J. P. Vial. Strategically zero-sum games: The class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory, 7(3-4):201-2111 Sep. 1978. ISSN 0020-7276.
Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007.
Ian Osband, Benjamin Van Roy, and Zheng Wen. Generalization and exploration via randomized value functions. In Proceedings of the 33rd International Conference on International Conference on Machine Learning Volume 48, pp. 2377-2386. JMLR.org. 2016.
Shuang Qiu, Xiaohan Wei, Jieping Ye, Zhaoran Wang, and Zhuoran Yang. Provably efficient fictitious play policy optimization for zero-sum Markov games with structured transitions. In International Conference on Machine Learning, pp.
PMLR, 2021.
Shai Shalev-Shwartz, Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. CORR, abs/1610.03295, 2016.
Lloyd $ Shapley. Stochastic games. Proceedings of the National Academy of Sciences, 39(10): 1095-1100, 1953.
Aaron Sidford, Mengdi Wang, Lin Yang, and Yinyu Ye. Solving discounted stochastic two-player games with near-optimal time and sample complexity. In Silvia Chiappa and Roberto Calandra (eds.), Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 2992-3002 PMLR, Aug. 2020.
11

---

Published as a conference paper at ICLR 2024
David Silver, Julian Schrittwieser, Karen Simonyan, loannis Antonoglou. Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. Nature, 550(7676):354 359, 2017.
Ziang Song, Song Mei, and Yu Bai. When can learn general-sum markov games with large number of players sample-efficientyy In International Conference on Learning Representations, 2021.
Alexander Strehl, Lihong Li, Eric Wiewiora, John Langford, and Michael Littman. PAC model- free reinforcement learning. In International Conference Machine Learning, pp. 881-888, 2006.
Terence Tao. Topics in Random Matrix Theory. Graduate Studies in Mathematics. American Mathematical Society, Providence, Rhode Island, 2012.
Joel Tropp. Freedman's inequality for matrix martingales. Electronic Communications in Probability, 16:262-270, Jan. 2011.
Yuanhao Wang, Qinghua Liu, Yu Bai, and Chi Jin. Breaking the curse of multiagency: Provably efficient decentralized multi-agent rl with function approximation. In Gergely Neu and Lorenzo Rosasco (eds.), Proceedings of Thirty Sixth Conference Learning Theory, volume 195 of Proceedings of Machine Learning Research, pp. 2793-2848. PMLR, 12-15 Jul 2023.
Yu Wei, Yi-Te Hong, and Chi-Jen Lu, Online reinforcement learning in stochastic games. In Advances in Neural Information Processing Systems, pp. 4987-4997, 2017.
Qiaomin Xie, Yudong Chen, Zhaoran Wang, and Zhuoran Yang. Learning zero-sum simultaneous- move Markov games using function approximation and correlated equilibrium. Math. Oper. Res., 48(1) 48(1))433-4444 Jun. 2022. ISSN 0364-765X, doi: 10. 287122/m0r.202 126..
Kunhe Yang, Lin Yang, and Simon Du Q-learning with logarithmic regret. International Conference Artificial Intelligence and Statistics, pp.
PMLR, 2021.
Kaiqing Zhang, Sham M. Kakade, Tamer Başar, and Lin F. Yang. Model-based multi-agent RL in zero-sum Markov games with near-optimal sample complexity. In Proceedings of the 34th International Conference on Neural Information Processing Systems, Red Hook, NY, USA, 2020a.
Curran Associates Inc. ISBN 9781713829546.
Runyu Zhang, Qinghua Liu, Huan Wang, Caiming Xiong, Na Li, and Yu Bai. Policy optimization for Markov games: Unified framework and faster convergence. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022.
Weinan Zhang, Xihuai Wang, Jian Shen, and Ming Zhou. Model-based multi-agent policy optimiza- tion with adaptive opponent-wise rollouts. In Zhi-Hua Zhou (ed.), Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pp. 3384-3391, International Joint Conferences on Artificial Intelligence Organization, 8 2021. doi: (0.24963/iccui222214466
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learning via reference-advantage decomposition. In Proceedings of the 34th International Conference on Neural Information Processing Systems, Red Hook, NY, USA, 2020b. Curran Associates Inc. ISBN 978 17 38299446.
12

---

Published as a conference paper at ICLR 2024
A ADDITIONAL NOTATION AND KEY LEMMAS
A.1 ADDITIONAL NOTATION
In the main text, we ignore the & dependency Algorithms and for simplicity. However, rewrite Algorithm | with dependency on k as Algorithm 3 for the following proof. In addition, we also rewrite some notations except for those introduced the main text below.
kg (s, a, (resp, (s)): the index of the episode in which (s, a, b) (resp. s) is visited for the n-th time at time step h; for the sake of conciseness, we shall sometimes use the shorthand kn (g, a, b) (resp. k" kf (s)) whenever it is clear from the context.
Pk E {0, 1]1x|s); the empirical transition at time step h in the k-th episode, namely,
(s) = 1 (s=
(15)
(s, a, b) denotes (s, a. b) by the end of the k-th episode; for the sake conciseness, we shall often abbreviate N Nf a, b) or N = N (sh a by,) (depending on which result we proving).
I..k (s) and VR (s), respectively, denote QN (1, a, b). @ (s, b), Qh LCB.K (8, b). Vh
Qh b), V (s) and (R (s) at the beginning of the k-th episode.
(s) denotes (s) at the beginning of the k-th episode.
at the beginning of B @h , 1h Uh , 1 .h BBhh denotes joh Th oh Vn R
r.k ar. ank a,k RR
the k-th episode.
L Th Lh 2n the k-th episode.
ja.k wak
Bil at the beginning of oRi BR. denotes Le 2n
RR
Furthermore, for any matrix P = [Prgl we have |||1 == maxisism Σj= Pagl-
Similarly, for any vector V [V its loc norm is defined as || = maxi Vil. We extend scalar functions and expressions to accept vector-valued inputs, with the expectation that they will be applied in an entrywise fashion. For example, for vector x = [ralisisns we denote x.2 [ For any two vectors x = [mg] igiinn and y = [M]isisn the notation x S y (resp. 2 y) means S (resp. zi 2 yı) for all 1 Tiisi n.
For any given vector V E SR.,, we define the variance parameter w.r.t. Ph.s,a,b (ef. 7 as follows
Vark.e.o, (V) = Es'Ph (V(s') Ph Ph.e,, (V2) (P (P))..,,V)?
(16)
The notation fxx) S g(x) (resp. f(x) 2 gx)) means that there exists a universal constant C.
such that f(x) < Cug(z) (resp. f(x) 2 Cog(z)). Besides, f(z) x g(x) represents that f(z) S g(x)
and (xx Z g(x) hold simultaneously.
A.2 PRELIMINARIES: BASIC PROPERTIES ABOUT LEARNING RATES
For notation convenience, first introduce two sequences of quantities related to the learning rate for any integer 2 0 and n 2 1:
n:), if N n, 1/ 1i
Th
N
7/1
if N = n,
and T
I
m)) =0 if O, (17)
1,
if 0.
0,
if N < n
We can obtain
Σn Th
1.
if >
(18)
0, if
Based the above definitions, We introduce the following important properties before analysis.
13

---

Published as a conference paper at ICLR 2024
Algorithm 3: ME-Nash-QUL (a rewrite of Algorithm 1 that specifies dependency on k-)
Parameter: some universal constant Cb > 0 and probability of failure E (0, 1);
Initialize: Qu(s, a, b), Qh Q.C.B.
(s, a, b). Qn (s, b), + H: 2 (s, b), Q (s, b).
Rt,1
1 (s, 0; (s). V (s)e H: ( Vh (s) 0: Ny t 0: 0s, (s, v (s, a. b). oe (s. a (s, (s. (y (f (). b).
(s, R a18,a,b. b). B (8. a, (s, a, < 0: and (8) = True for all
h) E x x [M]. for Episode = K do
Set initial state 81 < st.
for Step h 1,..., H do
Take action (ah, b/f) ~ (11%)) and draw shi2 ~ Pr.. I sh bl).
N ah M/)) + N ab 1// + n +- (o ah 1/)): The H4m
#+1
[00 [QUCBAt], QLCBB,+1]]] (sh at bb) t update-q()
2h
gRit1 (s o b/) - update-ur ().
Q gR.tt (sho aho b))) + update-ur ()-
(sh
10
b+1 ( (sh ah bl) min (2h R.++1
Qn
(s h: on bb) @UB (sh ah bl), (s a b.)).
2 kl+ (sh a b - max (Q R. (s dhi b Qu LCBB++
(sh an b/), 2 (s ag b.)).
12
if 1 (sh a b min (Qn
R
(s ohe
k
bl) a LCB (sh ah. bR) and
13
2 (st, o btt) max [Q..+ (8h a b)) Qh
LCB.b+1
(s at ) then
Th (s)) f- CCE(Q1
g (sh..))))
14
vitt (sh) <- -mmin(() A Qn (sh)) (>
15
vhtt (sh) f max((()
(s V (s))).
V h+1 (s V (s > then
16
Vh R. (5/) V (sf)): VR RR,+1 (st) v (sf))
17
else if att (st) True then
18
(s V (sh)
V
RRA+I (s/)) 1 (sh):
(x False.
Output: The marginal policies of { K+1H
(fmn) (mn)
20
Jh=l
Lemma
For any integer N O, the following properties hold:
1
S
Σ
N
2
for all
1
Sasi,
(19a)
NG
n=
n
Na
2
max ISRSN
<
2H
N
Σ
n=1
N
(m
N2²
2H
N
Σ
Σ 0
N=n
The 11+
H
(19b)
A.3 KEY LEMMAS
A.3.1 KEY PROPERTIES AND AUXILIARY SEQUENCES
Properties of the Q-estimate and V-estimate Variables T R.A and yh (resp. Vh provide an
"optimistic view" of Q and Q" (resp. Vt and V*), as stated in Lemma Similarly, R. and
º (resp. V provide "pessimism view" of Qulit and Q" (resp. vultt and V*). Lemma proved in Appendix C.I
14

---

Published as a conference paper at ICLR 2024
Lemma 2 Consider any 5 E (0. 1). Suppose that co > 0 is some sufficiently large constant. Then with probability at least 1 6.
Qn R.k (s, a. b) Q,(s, a, b) 2 Q Ql (s, a, b) (') & (s. s as)
Va(+) 2 vi vV)))) (20) VM(s) S VuLll (8) S (s) (21)
L ()
hold simultaneously for all (s, (s,a,b, E Sx H
Properties of the Q-estimate and V-estimate To begin with, it is straightforward see that the
update rule in Algorithm 3 (cf. lines 11-12) ensures the following monotonicity property: for all (s, a, k h) S A x
5
[K] x [M]
2n k+ (s, a. b) - (2),,, O (s, 2
a)
(s, b)
(22)
Similarly, based on line 15 of Algorithm
3 the monotonicity of Vo and L can be obtained as (+) 2 (+).
k+1 b (8) S (+),
(23)
Besides, the update rules in line 11-12 of Algorithm
3 allso result in the following property:
Qn R.k. (s, (,,,,,) b) 2 a,, b), 2 (s, a, S (s,
(24)
Lemma 2 implies that V (resp. vit is a pointwise upper bound (resp. lower bound) on Vy-- Taking this result together with the non- non- incrrcsccinng (resp. non-decreasing) property (23 we see that V and V become increasingly tighter estimates- of Vi as the number of episodes k increases, which means that it becomes increasingly more likely for V and VA to stay close to each other as increases. Furthermore, it indicates that the confidence interval that contains the optimal value Vi2 becomes shorter and shorter, as asserted by the following lemma.
Lemma For any given E (0, 1). with probability at least 1 8,
K Em k= 1 (Va ak b%) ( at, 1k) > 8)
H
SABA log SABT
(25)
2²a
holds for all (O,
Combining with 24 we can straightforwardly see that with probability least 1 1-66 5:
Qh
R, (s, Q (s, a, b) 2 Q. (s, a for all (k, s, s, a) b) E [K] [M]
(26)
Properties of the reference RRR and VR. As stated in Section 3.1, the conclusions reference values guarantee that (i) our value function estimate and the reference value are always sufficiently close, and (ii) the aggregate difference between V.Rk and the final reference value R.K (resp. V.R.k
and the final reference value KR. is nearly independent of the sample size T (except for some logarithmic scaling). The above conclusions are summarised as follows and justified in Appendix C.3
Lemma 4 Consider any 5 E (0, 1). Suppose that Cb > O is some sufficiently large constant. Then with probability exceeding - 8. one has
(8) R.A. (s) 22
[+((s) - V.lA((s <2
(27)
for all (s, k. h)) ES x [K] [H], and
Σ h=1 Σ k=
(viLi
R1,k (5 - - (sht S H log
SABT
(28)
8
H
(VR.K (sh) RR (st) S H log
SABT
(29)
b=
15

---

Published as a conference paper at ICLR 2024
A.3.2 MAIN SUMMARY OF STEPS SECTION
The key proof of Step 1 is based on the Lemma 2 which allows one upper bound the regret as follows
Regret(K) = Ex k= (vitue - v/te.) (5f) S Σ k=1 (V* V (of).
(30)
To continue, it boils down to controlling (vr- - 24t (sf). Towards this end, we intend to examine
(V.- (VÝ-VV w*) (sf) across all time steps 1 Sh H, which admits the following decomposition:
V V*((h)- - (x s (a @ 0 (b) a, b) ( ah (/) 2 (oh. (%) + ch
s Qn (sh ah
R &. bl) @ oi U/) + ch.
(31)
where
ch = (a @ - ( b) - 10 - (5h a b2).
(32)
Summing
(30 and 31 over 1 k S K, reach at
Σ
K
S 1=11
K
(Qh
R.k
(5 b
R.. (sh, ag. (x) +
E K
k= Sh-
(33)
The key decomposition terms and their bounds in steps and are summarized in Lemmas and respectively.
Lemma
Fix 8 (0, 1). Suppose that ab > is some sufficiently large constant. Then with
probability at least 8, one has
Σ K
k (i()
Lt S D1 DD D2 D3.
(34)
where
D
11
1+
1 h-1
2HSAB -IGAAA
1 log SABT RK
-
ch
(35a)
h=l
H
k=
H
1
Ex
R.K. (BR (sh ah, (%)) + R (s at bh)) bi))
D2
1+ H
(35b)
h=l
D3
"
K
N ((p)
- -h.st ) (Vitt=-V R.k
- - )
-5-PPaane Photiaatt at
(iiti
LR
T=
Not (sh
V (shti))
Pink
Phhittaaa aaa og h+1
2
1=11
1=1
Nē (s)x bli
Σm
(
(y n,k' (shit2)
R.k P Ph al oy Kb+i)
11
K
1/b
(35c)
h=1
1=
No (oh, ali Mt)
with
1 h-1
N (sk
Σ
N ( Th (xt
(36)
Lemma 6 With any 8 (0, 1), the following upper bounds hold with probability least
8:
SABT
SABT
D s V H2SABT log
+ 4.5 log2
(37)
8
SABT
SABT
S V HSSABT log
+ H log
(38)
8
SABT
SABT
D3 S / H!'SABT log
1 log
(39)
8
16

---

Published as a conference paper at ICLR 2024
B FREEDMAN'S INEQUALITY
B.1 A USER-FRIENDLY VERSION OF FREEDMAN'S INEQUALITY
Before proceeding to the analysis that follows, we first introduce the well-known Freedman's inequality (Freedman] 1975] Tropp Jan. 2011), which extends Bernstein's s inequality to accommodate martingales and exactly matched with the Markovian structure of our problem. We first provide
user-friendly version of the Freedman inequality introduced in (Li et al. 2023
Section C).
Theorem (Freedman's inequality) Consider a filtration Fo C Fi C F2 C ... and let Ea
stand for the expectation conditioned on Fk. Suppose that Yn Ek=1 real-valued scalar sequence obeying
Xx E, where {Xx} is
[ S R and
Ex-1[Xa]= =0 =0
for all k: 21
for some quantity Dc. also define
F. Fn= Σ
Bk-1 [X
In addition, suppose that Fy S a holds deterministically for some given quantity 162 < oc. Then for any positive integer 2 1, with probability at least 1 5 one has
8 max { Fnn
3/2
2m
2m
Yrl <
log
R log
(40)
2m
8
3
8
B.2 APPLICATION OF FREEDMAN'S INEQUALITY
Before diving into the subsequent proof, we first introduce two lemmas based on Friedman's 's inequality. Our first result is concerned with martingale concentration bound as follows.
Lemma' Let { R I K, < < и + 1] and (Gr a,
a, (s,,,,, K, < h < H +1 be the collections of vectors and scalars, respectively, and suppose that they
E R R
obey the following properties:
rk is fully determined by the samples collected up to the end of the (h - 1)-th step of the i-th episode:
|F S C;;
Gh(ss, a, N) fully determined by the samples collected up the end of the (h - 1)-th step of the i-th episode, and given positive integer N E [K];
0. (,, S Cgi
0 Ng G (l(..b)))
b, b, 2.
In addition, for S K. consider the following sequence
X b,, = G a, b, () .h.....)) F (x ah b))) = (s, b)b)
(41)
with Ph defined in 15 Consider any 6 E (0, 1). Then with probability at least - 6,
X as $ Cg log²
SABT
(g(a,,)) un
(s. 6,
(W- (s.aa))
C Ce
SABT 8
CgCc+VVN
log
(42)
holds simultaneously for all (k. h, 8, 8, a, N,
K
A A
x
S
17

---

Published as a conference paper at ICLR 2024
Proof B.1 On non-ambiguous basis, will abbreviate Xx(s, b, h. N) as X, throughout the proof of this lemma. The main idea of our proof to control the Σ X; term by Freedman's inequality (see Theorem
Consider any given (k,h,s,o,b,N)) [K]
H
x A B [K]. It can be easily verified that S
Bx-1
[x =
where Ek-1 denotes the expectation conditioned on everything happening up to the end of the (h 1)-th step of the k-th episode. Furthermore, under the assumptions [| I Cr, 0 S as,,,,, S Cg. and the basic facts ||P/ =|Ph.aall 1, we have the following crude
bound:
X & G (s, a, b, N) (PA - Phos,att Fhtt
S a N)
(1 + Ph 1 s 20,0g
(43)
Under the definition of the variance parameter in 16 we obtain
Xx 2 = Σ b,, ( oh b, (1% - Phoat))Ftt 12]
Bk-1
Σ
(G
(s, (s,a,b, Varannn (F h+1
n=1
(x.a.)
Σ
(bsa | ( 11
2CCg
(44)
where the inequalities hold true due the assumptions |1 S Cr. 05 Ch(s,,,b,,) S C. and 0 $ > (s.a,b) k (x...b) (s,a, b, N) < 2. (s,
Armed with (43) and 44), we can invoke Theorem (with m = [lgg, N1) and take the union bound
over all (Js, h, a, a, N) E K H x S A x K] show that: with probability least 1
SABT log N
Xx
log
(T(s.,b) (s.o
(WAR(ssa)))
C2 N
SABT² log N
max
Cg
Un
bs,
log
(o,o,))) Σ
< V
log
SABT
Un
(g(saab))
(s, NiVar.. (W (s,,,)))
C CB
SABT
+...tt+ VN
log
holds simultaneously for all (ks, h, a, b, E K H S AxBx
Lemma Let {N(s, a, b, h) E [K]
(s, a, b. h) E x Ax B x [H]} be a collection of positive Ch Se h [M]] be a collection of fixed and bounded universal constants.
integers, and let {ch
Moreover, let { FQ E R$ 1 < K, h H + 1} and ( a bf) E R 1 $ i <
K, H +1} represent respectively collection of random vectors and sealars, which obey the following properties.
Fh is fully determined by the samples collected up to the end of the (h - 1) step of the k-th episode;
>F S Ct and Fi 0:
18

---

Published as a conference paper at ICLR 2024
Gh ohi bl.) is fully determined by the integer N( o bh h) and all samples collected up to the end of the (h 1)-th step of the k-th episode:
0 Gh & bn) S Cg.
Consider any 8 E (0, 1), and introduce the the following sequences
XA,4 (s a (P) Phatt 02 ( Fi+11
1 I
(45)
Yk,h cn (Pr Phoet (i Fh+11
1 <
(46)
Then with probability at least
H
K
H
THSAB
Xb.h
S
C2
h [(et Phankat, ))
||]
2
log
4=1k=1
THSAB
+ CgCr
5
K
THSAB
THSAB
CgC
[ log
Cr log
8
5
1=1 k=1
H K Yo
TC log
8 + Ct log 8
4=IK=
hold simultaneously for all possible collections (N(s, a,ls,,,b,l
x
Proof B.2 This lemma can also be proved by Freedman's 's inequality (ef. Theorem
We start by controlling the first term Ex=1 Ek=r Xk.h- It is readily seen that for any given a,, E S x A B HH), we have
E [
E Gh ah (Ph og = O,
where Ek.b-1 denotes the expectation conditioned on everything happening before step h of the k-th episode. In addition, make note of the following crude bound:
XEE s (s at b/h (Ph - Phist Fitz
< of, b (1IP/11: 1I. 1 20,
(47)
which arises from the assumptions the basic fact [1
[| llo0 Cr. 0 (s b, N) S Cg together with 1. Additionally, we can calculate that
P t. ak og 1I
E [|xx.nl
Σ
(G at 2 [(pPk
Phott Fitt {]
11
K
Ek (PP) Pmogiati ) 2
(48)
h=1 k=1
K
C
Ex
F pok
(49)
1=1
19

---

Published as a conference paper at ICLR 2024
where the first inequality comes from the assumption 0 1 (sh oh b%, I Cg. Further- more, (49 can be expressed as
1
Px (F% )"
h
K
h=
k=1
H
F BA Wh
1=
k=1
Σ
ER [P
(50)
1 K
(d) S H (51)
DE
k=li=1
Notably, (a) comes from the fact that Ph only has one non-zero entry (ef. 15 J. (b) holds due to the assumption that Fl is non-negative, whereas (c) and (d) rely on Fr I Cr.
With 477. 50, and (57), can invoke Theorem 4 (with m [log2 T1) and take the union bound over all possible collections {N(s, a, b, h) E [K] (s, b, S x A x B x [H] which have most K KSSAB possibilities, show that: with probability at least 6,
H
K HSAB log T
X1.
S CR log
5
km
H
K
TC2C 2
KHSAB log T
max
C
Eg
[1 (Pth- -
2
log
6
K
THSAB
TSAB
B
(Pt
F h+l
2
log
CgC log
8
4=
H K
THSAB
THAB
C2
Σ
E
[Ph
Fk
log
+ +CCC 5
h+1
h=1km1
holds simaltaneously for all (,,), [K] Exx [I]
* Then we turn to control the second term EHH K Ya,h of interest. Similar to
Σ hh=1 EK ) we have
Yk.a S 2eCr.
B |Ya. 12] < <TTTCF.
Invoke Theorem (with m = to arrive at
h Σ
+ C log 1
YK. S
TC log x
(52)
C PROOF OF KEY LEMMAS IN SECTION A.3.1
C.I PROOF OF LEMMA 2
The proof is by backward induction. Suppose the bounds hold for the Q-values in the (h + 1)-th step. now establish the bounds for the V-values in the (h 1)-th step and Q-values in the h-th step.
20

---

Published as a conference paper at ICLR 2024
For any state s,
V (+) Daf. x (h+1)())) 2 max Femes (8,
(1)
max BBnakt oh
ghat (s, a,a
h+1
(53)
where (i) comes from the property 10a of CCE. Similarly, we can show 1h+t(() S Vrhts (s). Therefore, we have: for all 8.
(*+1()) 2 12
(s) (o+
V v (6) LK)
h+1
Now consider an arbitrary triple (s, a, b) in the h-th step. We have
2t (s, (s,a,, (s, s'~Pa(ls,a.)
vitfft (5') (5)) Vh+t (6) 2 0.
E
(54)
Similarly, we can show a, S a'(s,,,b) To complete the induction argument, we should prove
as,
(s, a, b) 2 2 (s,a, b).
(55)
which we shall further accomplish by induction. When
1, (55) holds since that the initialization
obeys h H 2 Q (s, a, b) for all (h, a. s. E [H] x S x A B. Next, under the assumption
that (55) holds up to the k-th episode, we wish to get it for the (A: + 1)-th episode to get Lemma 2
According to line 11 and lines 13-14 of Algorithm it suffices justify
RRR. min
R.k+ Qh
(s, a, b). Qh
UCB.K+ (s,a,) Qt (s,
(56)
In order to get 556 need prove that
h
UCB.A+1
(s, Qi+." (s)
(57)
and
R,++ (s, 2 Q1:.t (s,
h
(58)
For the sake of convenience, suppose QUCB, (sh a bb) and Qh RRK (s an 6%) are latest updated in the k-th episode with &o s W,, it suffices to verify
Q QUBAkt oh b/) 2 Qi:ah" (sh at, bh),
and
Qn R.++1 (oh an bi) Ql.ek (shi (hi Ut.).
First, the proof of (57 is performed.
Step 1: decomposing Qu UCB,k+1
(s) a. by) > Qt: (5h b/)))) Firstly, according to the
definition of NŁ and ksth in Appendix A.1 obtain
Qu UCB
(sh, o
Qh
UCB.
UCB ACB,
+1 (s at bh),
(59)
since V. ( k. According to the update rule (i.e., line 2 in Algorithm 2 and line 8 in Algorithm 3). we obtain
2n UCB.b+1 (st a b/t)
Qu QUBBA.M. ah
(s ar b):)
SART H3 log
(I-1Nx) QUBBAA (s) at, bb) + ANZ
Th rn( ai (1) V +ob
h
-(1-NNe)Q UC (1- (stt ati 1/h +nng
rh ( (shhi ton
H log 8
SABT
N
21

---

Published as a conference paper at ICLR 2024
where the last identity again follows from our argument for for justifving (59). Applying this relation recursively and combining with the definitions no and 1/2 in 17 we obtain
On 2 UCB,
A & b/))
N
10 log SABT
= 1/0
N
Qh
UCB.1 (sh a b% +
Σ n=1
N nm
(
az bf) + V ( + tob/
6
(60)
No With 7/
+ Σ
No No in 17
and 18). there is
n=
No Σ Un
Qla +1 (sh k b/)) = n1 No Quaek -1 (sh at (/)
No
Q
ag bb).
(61)
Combining 660 and (6T). can further get
Qn QUBBA+1 (sh ohe bb:) Qleck" (sh oh bb)
Na (Q
(sh, ah, b/:) - Qi.ek (sh. bk))
170
N raloh ah bht Vh (o)+1)) + onl
1 log SABT
Qie (ohi ab) 0b0 }. (62)
To continue, invoking the Bellman optimality equation
viti Qliek (sh oh bb) rr ah 1ht) + ah t My h+l
(63)
we have
rn(s ah,, b/t + Vh" h4 (+ - Qu. +2 (sh an, b//) = V 1nti(ssh - Phing Phankaat ah Vitt ti
-Phh" P Phisting af MR
ylug + Ph" (Vh". ytthh (64)
where Pk is defined in 15 Bringing 664 into (62) yields
QUB,++1 (s oh, b
Q Qiee "(s ah, bht) = = Ni (Q UCB, (sh, at b/))
Qlu (st at bti)
(ph" Phottat V + pp" (V
vith 1'+1
H3 18 log SABT
h+1
+ co1
n=1
(65)
Step 2: two key quantities for lower bounding Qn UCB.++1 (s a (/) 2 Q1o (sf
"( .
In order to develop lower bound on Q) UCB.++1 (sh, a bt) > Quoek" " at, bt) based on the decomposition 65 we make note of several simple facts follows.
(a) The initialization satisfies
1 ax bR)
Qti (st (2) 20 0.
(b) According to (53 monotonicity of V in 23 and k < k, we can obtaion
kn (
+1 1. h+1 h+1
(66)
(c) By the Azuma--Heffüee incquality and a union bound, we have that with probability at least 1 - 6, one has
(Px Phist ag. h+1
H3 log
SABT
S Ch
(67)
n1
Thus, Q UCBBK+1 k k the proof of (58)
a bt) 2 Qt"""t((sa,) 2 and we have concluded the proof of 57 Next
(s.
22

---

Published as a conference paper at ICLR 2024
Step 1: decomposing Qh
R. (s af. bB) Qio (s a b8)- Similar to (59). we can get
Qn
R
(s 4 b//) = Qh R. R (s h: 0%))-
(68)
According to the update rule (i.e., line 6 in Algorithm 2 and line in Algorithm 3 we obtain
Qn R.++1 (sh at bl)) Qn R.
R.
(sh ahs bh) (1 UNN 2n
(0h (
+NNg ra(s ob Uh) +
h+1 (3/ v. h+1 (0h=1) + 4%
+1 (6 a bl) + bn
n.68% +1
=1 (1 N 1Q R ++1 (sh, ai. 1%:
2 + h+1 (s
R.AA h+1 (s
+ - +1 (s oh b%) + bn
RR, +1
= -1N ra oh b))
where the last identity again follows from our argument for justifying (68). Applying this relation recursively and invoking the definitions of v/ and n/ in (7). we are left with
2n
R.t+1
(0% ak, bh)
No
Qh
R.1, (0% 0h b%)
No
No 1m r (h nh
h+1 (sh+1)
=I Whit (s on (sh ah o. D/
-RA"+1
(69)
Additionally, 61 combined with 669 leads to
@hett
(s ah, bit) - Ql.eh (s ah, b = =
R1, No (Qh (sh, az b/:) Qi:ek "(hhs"hhh az. bk:))
N
N
(rh(s afi, bh) + Vhn ( - -VRA""
h+1 (8h-1))
+
nn
N
Th
No
4h
+1
(0% ah b7t)
bn
RR
Qiih
(s ah bi)
(70)
To continue, invoking the Bellman optimality equation (63) and using the construction of Φn in
line 12 of Algorithm (which is the running mean of V..11. reach
The (sh ah. bn) +
Vha (n+1(s/411 V.R.A"
R, (o
+
-1,"+1
Φn
(o ah b%) - Qt. +1 (sh, ah bh)
V.R h+1
(s
= h+ (o RuAa"" (sh i==
Pmish at 1+1
(71)
n
Next, combined with the definition of
1 n (Pk Phott,ak hti
(Ph Phint
bb (V h+1
V
R,
V R,
(72)
n
we can obtain
R. }
Eizl P
Prisaaaa of
h+11)
Vink Phi at of h+1
Ph.et
h+t
+
n
R h+1
Vink h+1
h-1
(73)
n
with the notation ph defined in 15 Putting
73
into
70
together gives
Qn
nn,++1 ( aft btt) Qtiek" 11 (s/) at, btt)
= 1io Nt
(Qh
R.1
(s at bb,) Qliek
(s at bl.)
No mm n=1
N
Vh" Vitn
h+1
+
Ein
h+t - h+1
RRK
+ bn
RRA"+1
+ w j.
(74)
23

---

Published as a conference paper at ICLR 2024
Step 2: two key quantities for lower bounding Oh 2h (sh: ah
RRk+1
a.. bl) Qua (s af. b/)). In
order to develop lower bound on Qh @ (s a (if) - Q (s a bf) based on the decom-
position (44, make note of several simple facts as follows.
(a) The initialization satisfies Qn (sh ar (/)
Qt
(0h at 1%) 2 O.
(b) For any & k" S k', one has
h+1 V
h+1
(75)
owing to the induction hypotheses of Q-values the (h + 1) 1)-th step and (53) that holds up to k.
(c) For all 0 S i S and any E S, one has
B, h+1
R,A" 4+1 2 0,
(76)
which holds since the reference value A (s) monotonically non-increasing in view the monotonicity (+) in (23 and the update rule in line 17 of Algorithm
Based on the three statements above, we can simplify 774
NY
R.++1 @n
(5h, oh, bl
Que (sh oh
b 2
Mn
No R1
(D)
+ twrh)
(77)
n=1
In the sequel, we aim to establish Qn As it turns out, if one could show that
R,k+I (s ah, bit 2 Q1iak 12
(sh a b//) based on this inequality
N Σ
Mn
No
mo
Σ
Jn
No R1
Dp
(78)
n=1
n=1
we claim that
77 satisfies
N
N
R.k Dh Qhat-1shh
(sh oh (i))
Quo
(sh ah
No. R. 7/m
Up
0.
(79)
where the first inequality comes from the triangle inequality. As a result, the remaining steps come down justifying the assumption (78). And thus, need to control the following two quantities (in view of (72)
N
W1
No Tn
(Ph"
Phittatt (Vh", h-1 h+1)
(80a)
N
12
W₂
Tp
N
(Ph
R,K h+1
(80b)
71
separately, which constitute the next two steps. As will be seen momentarily, these two terms can be controlled in similar fashion using Freedman's inequality.
Step 3: controlling Wt. In the following, we intend to invoke Lemma 7 to control term W2 defined in (80a) To begin with, consider any (N, h) [K] x [H], and introduce
F h+
R h+1
and
Gf, a, N) = 7 (s,a,)) 2 0.
N
(81)
2+1
Accordingly, we can derive and define the following two equations:
1
S | +
+IVRR
R.k /
2H Ct.
(82)
2H
max
Cg
(83)
N. K
N
24

---

Published as a conference paper at ICLR 2024
where the last inequality comes from
2H S
if & (s, b) N; if (s, N, along with Lemma and the definition in
N (.).,))
N
N (s.a.b) O,
Moreover, observed from 18
we have
kh (x,a,)
(s) = nh
(84)
1=1
==1
holds for all (N, s, a. b) E [K] S x A x B. Therefore, applying Lemma with the quantities 81 and (N, 8, a, b) (N st of b implies that, with probability least
Wi = Σ
No
(Ph Phott by h+1 - T
Mm
N
SABT
2 V Cx log 8
G (sh an by Varn oh w41)
CgCs+ + V V Cr
SABT
+
log"
H SABT NZ
N
N Vh
Var s. 86 (Vh+1 h+1 vleA") +
2 log²
SABT
log
(85)
h
where the second equation comes from (s an by h, N2)
Thi No (Ph"
ah Mt. (v
h+1
R,
Furthermore, (85
can be simplified to
H
log 2 SABT
a.k MR
H² H² log" SABT
885
(0h a b/2) (on
(s at b2))
(N/)3/4
h
(86)
where the proof 86 is postponed to Appendix C.I.I to streamline the presentation.
Step controlling W2. In the following, our aim is to the quantity Wa defined 80b Rearrang- ing terms in (80b). we obtain
W
N/
7n
No.
Σ (Ph
Ph. n
R
h+1
Σ
N
Th
N
(ph
Phist
V
h+1:
which can again be controlled by Lemma 7 And thus, we abuse the notation by taking
Fh
V
R h-11
and
Gh b)) =
Σ
nn
0.
(87)
n
n= Ng
These quantities satisfy
| 1loo S [
= Ct,
(88)
N
2
max (al.aaa.bb(KXx(]xxxxxxx
Cg.
(89)
n
n
N
n= (e.
where 889 holds according to Lemma seen from 889 that
Then for all ANs, b) E [K]
A x B, it is readily
0
h
A (m..a))))
(s, N) <
2
2.
(90)
N
1
25

---

Published as a conference paper at ICLR 2024
With the above relations in mind, taking s, a, b) w.r.t. quantities
(N 1 at b8)) and applying Lemma 7
(8) reveals that, with probability exceeding
N
No (Ph
h
Xi(s% a b% h N3)
W22
Phock 1+1
(91)
n=1
/ Cg log²
SABT
N
he h
(5% a bn N, Var Varn. ak Ni. (F
n=1
C N
SABT 6
C + V
log²
SABT
SABT
S
log 2
Var Varn,s ah.0t (V )+ +
log²
(92)
N
5
NE
No.
8
where the second comes from X((s), 1 by N%) EmI In wa
(Ph
Phist az b/
R.
h+1 and
k No. Moreover, (22
can be simplified to
log" 2 SABT
h+t (6 (0h) ag b1))²+
H SABT
122 S
No
5
4h
(5h ah b%)) -6
(NK)3/4
log"
8
(93)
where the proof (93) is postponed to Appendix C.1.2 to streamline the presentation.
Step 5: combining the above bounds. Combining with the results in (86 and 93 obtain an
upper bound on
>
NW n=
Un
No
h
k" as follows:
mh
h
S Wil + Wil
H N
2 SABT
log
th
(on
(ot b/))
log²
SABT
V/
II hi +1
(s ati, b%)
(on
-0. +1
(s at 2²))²+
2 log² SABT
No
(N/)3/4
122 log" SABT
B
h
ah b%
+ cb
(N/)3/44
(94)
for some sufficiently large constant ob > where the last inequality follows from the definition of By n
(sf (( at bb) in line 15 of Algorithm
In order establish the desired bound
78). we still need control the sum Σ Ex-17 7m
D
+1
Towards this end, the definition of bh
Bt,k"
(resp. ohh in line (resp. line 16) of Algorithm yields
b/
R.
( R.K" (s
ah & blt
+ B R, (s a bb) + n3/4
1 B
SABT 11 log
(95)
Th
This taken collectively with the definition
17) of n allows us expand
No
N
No Un
7/
N
bp
3/4
2 log
SABT
n=1
N
N
II (1 mh (11
R B
(s a b)) +
1 R.
Bh (sh ai b2)
(96)
mm
n=l
i==+1
26

---

Published as a conference paper at ICLR 2024
And thus, reach
N
N
96
II (1-n)) ne) (-(1- 1hr Bh
R.k"
(5 oh bl))
BB
(sh ah bR))
s=n+1
N
No
II (1 Br R
k (s ane
II m:) n
R
(s oh b%:)
(97)
n=1
1=++1
Under the fact that BR.
(0% h: b//)
O, we can reach
N
No N
II (1 1h)) BB BR R1
(8 + b%
B)
R,K"
(sh a b%
1=++1
n= i=
N N
N
N
Σ
II (1 17) BB
R
(6/ 2/.
Σ II (1- B1 R, (8% ah. b%
(=++
=BA
-B
R
(5 o b
(98)
where the second equality follows from the fact that
N N BLA"" (sh, at 1
No
N
-11a-m
#)
II (1 - (1-t)) RK
(sh, b2. bit
2=2i=n
im++1
No 1
No
Σ
II (1 (1-
(1
B. (s% at b.).
RI
=
i=++1
To be specific, the first relation can be seen by replacing n with n + 1, and the last relation holds true since the state-action pair (sf at, bit)) has not been visited at step lt between the (A-" + 1)-th episode and the (b=+1 1)-th episode. Combining the above identity 988) with the following property (see Lemma
2
S
(N4)3/4
3/4
(N/433/4
==
we can immediately demonstrate that
1 +1 (sh, ati. U/) + cb (Nk)3/4
2 log² SAT 8
N
Nk +IA++1
Bn
Th
Un
R
H2 log SABT
h
(5 Ani b%) + 2ch
(99)
(N
Taking 944 and
(99
collectively demonstrates that
H2 log² SABT 3
N
Σ
nn
B
R.A
h1
(8
+ Cb
(Nk)3/1
7m
No +1
bn
(100)
===
n=1
as claimed in
78
We have thus concluded the proof of Lemma]
based on the argument in Step 2.
C.I.1
PROOF OF INEQUALITY
(66
In order to establish inequality 86). suffices to look at the following term
NZ
No Mm
(Vh h+1 R.A") -th (s ab - 2i +0x (sh at bt))²
-
W3=
Varn. Ne
(101)
27

---

Published as a conference paper at ICLR 2024
which forms the main content of this subsection.
a.k"t]
a.4+t1
First of all, according to the update rules 0% and vn in lines 13-14 of Algorithm can get & b(:) = 0h (sh: ah ohh b%)
we
Ph
a
ahe
a.k"
Tark" (sh b/.) The (Vhr (Vnil(hht))) - -VR. (sh+1)),
= -1 - 1m -n
Jakn 2n
(5h, o b/))
= 1// (sh: a42. bl)))
-a,k+
= -1 ak
(sh ans bh) + no (++i($h++)) - RR, (sh+1))²
Applying this relation recursively and invoking the definitions of n/ (resp. P in 17 (resp. 15 there is
N
k +1
①
No (V
(V
V.AAA (bh+1))
(0h 4/
b%)
N
Ni.
Pk
(V
(102a)
n=1
N
(sh 1.
ahe bk)
No h"
(
R₁K" V h+l 1))
Th
n=1
Nº
Mm
No
Ph"
(vhit, h+1
(102b)
Recognizing that >m Th expressions (i) and (ii) to yield
No No
1 (see (18
we can immediately apply Jensen's inequality to the
-
(sh at b%))
Oh
(s at, 61))
(103)
Further, in view of definition (6).. we have
(Vh" Varn.eg of h+1
RR,k"
h+1
P Phee of h+1
(v
(Phott P
(V h+1
R.R ))
which allows one to decompose and bound W3 as follows
N
W3
Th
Na
P
(Thi
Un
Nh
ph.
(vhi
F.R
h+1
m=1
No
Tm
No (vh"
ph
h+1
h+t1
mp
Na by
(Phott
(V h+1
h+1 )
n=1
(104)
And thus, (104) reaches to
W' S W3,1 + W3.2
(105)
where
Wa,1 =
Σ
mn
No
(ph
of (V h44 - -..A"
and
N
N²
(vh"
R,
N (Phoot
(V
h+1 - RR
h+1 ))
W3.2
h+1
h+1
It then boils down control the above two terms in (05 separately.
28

---

Published as a conference paper at ICLR 2024
Step 1: bounding Ws,
To upper bound the term 1s,1 in (104). resort to Lemma 7 by setting
Fh+1
(VR+1 x
and
G,, = - (N
(106)
According to 83
it is easily seen that
|1 (IIVital)) |[ h+1 100
)=
2
S < Cr.
(107)
2H
max be (M] (s.a)))
N
Cr.
(108)
N
Armed with the properties (17) and (08)) and recalling
90 we can invoke Lemma
w.r.t (106, (s a 6h h, NN, Th No (P% P Phook
V W )z and set (NV s, a)
1+1
(Nk hhe on bft) to yield, with probability at least 1 -
N
W3.1 =
Σ
No (Ph"
SABT
V Cg log
Σ
h
(sh
M/ No Var af of (Wh+)
(109)
5
n=1
Cg N
SABT 8
CgCr+ +
Ci
log²
2
H
log?
SABT
Σ
N
not Varn,
th (Vhi - W441 )²) H log SABT
(110)
No
8
N
With
Tn
< 1 (see
(18) and the following trivial result:
(T h+1
(RA") s |1( 1+ - ) I 16H
Var h ak
(111)
We can further obtain
H
SABT
H
SABT
W3,1 S
log2
log²
(112)
No
8
N
8
Step bounding 3. Jensen's inequality tells us that
Nº
N Taa
a og (Vh*,
Ph.
h+11
2
(1/1
No.
1/2
(111
No 1/2
Ph. at (Vh+1
N
N
Nk
Σ
No
(Phistiot of (Vhi, - V.R.A
2
Un
mm
h+1
n=1
W - (R-41) )²
Tm
(Prot af of
(113)
n=1
where the last line arises from (8) Substitution into Wa,2 (cf.
(104)
gives
No
No
h+1 (RA 1)
W3.2 <
Mm
ph"
(Vh+
N mn
P
ak
(vh" h+1
h+1
n=1
No
N
Mm
No
(11)" -Phot ( (Vh+1-12
(v
-VRAA h+1
R,An
Th
No
(1h
+Phist
(v
h+1 V R,K"
(114)
29

---

Published as a conference paper at ICLR 2024
In what follows, we would like to this relation to show that
H
SABT
H
SABT log"
W3.2 S Cs2
{V
log"
(115)
No
N
5
for some universal constant C32 > 0.
If 3.2 S 0, then (115) holds true trivially. Consequently, is sufficient to study the case where
Wa.2 >> 0. To this end, we first note that the term in the first pair of curly brakets of (114 is exactly
Wi (see (80a), which can be bounded by recalling 85
W
H N
log
SABT 5
N
Nà Th
My (V
h41 V
B,ke" h-1)
H log" SABT
(116)
N
with probability at least 8. According to the property that
Var h. of, o W+t
R.A" A+1
< |1(V h+ - 2 S $4H2
(117)
And thus, 116 can be simplified as
WilS
H
log
2 SABT
Σ
No
H² log
SSAT
H
log
2
SABT
H² SABT
log 6
N
5
N
NE
5
N
n=1
(118)
whereas the last inequality (118) holds result of the fact Σ
N Th
< 1 (see (88)
Moreover, the term in the second pair of curly brakets of (114) can be bounded straightforwardly as follows
No Σ
Nu (Ph"
oh (vh",, -VRA"
+
n=1
N
(11PA" 11 + | 11a l
RRA"" h41 11 2H,
(119)
n=1
where we have made use property 188, as well as the elementary facts 1.
V R,k" h+1
I| S H
h++
and pba ll = |l I|, = 1. Substituting the above two results
118) and 119 back into
(14). arrive the bound (115) as long as W3,2 > 0. Putting all cases together, we have established the claim (115).
Step putting all this together. can conclude that
To finish up. plugging the bounds 112 and 115) into 104 we
W3 < Wo.1 + W322 S Csf Coty
H
SABT
H
SABT
log?
log²
N
5
No
8
for some constant C3 > This together with definition
101) of Wa results in
x Un
N
Var
af (Vh+)
V-LA"
(- wh +1
(0h
hs an b1:))
?}
Wh
H1
SABT
113
N log² SABT
Cs
(V
log²
Noh
5
8
30

---

Published as a conference paper at ICLR 2024
which combined with the elementary inequality Vu vutos S Vu + vo for any u. 2 0 and (103) yields
N
No
Var
(V
h+1
Vllkk") h+1
}
1/2
{
hh
(sh:
oh b%:)
(0h
(sh at , bb))) }
1/2
H5/4
SABT log!/2
H3/2
SABT
+
1/2
log
(Nz)
1/4
(NK)
1/2
8
Substitution into 85 establishes the desired result (86).
C.1.2 PROOF OF INEQUALITY (93)
In order to prove inequality (93) it suffices to look at the following term
W4
1
Var of oy (V R.k"
)
V/
r. v
+1
2 (0 aii bk)
(
(oh a atk. 1))) (120)
NO.
I
+ in lines 11-12 of Algorithm
In view of the update rules of Oh
and wh
we have T h+1 (sh+1);
-I,k" +
(5 o: (/) (1
_t,k" Ph (sh. at. b
Ph
- (sh ah bb)
(sh ai b/))
IIK"" kn
(5h, an bb.
1
(Vhih"
h+1 (sh
n
Through simple recursion, these identities together with definition
15 of Ph lead to N
N
(sh.
R.K" h+1
(bh+1)
R, Vhti,
(121a)
N
N n=1
N
N
Mr +1 1
(sh
(i)
h+1
(s
1))
pk
(121b)
No. n=1
n=1
Expressions (i) and (ii) combined with Jensen's 's inequality give
Vb
-r,
+1
(sh, ah bh) 2
On
(sh, an utt ?
(122)
Taking these together with the definition
(VRA"") = Ph.st M8
h+11) (P (Phitt RB,b" )
Var of of
obtain
N
W4
1
o (V W
(P (Photaat
V R. of h+1 )2)
N+
2
Ph"
h+1 2+
Σ
pf V v
(123)
N
N
And thus, 124
reaches to
W4 = W4,1 + W4,2-
(124)
where
N
W4,1
1
Σ
( Ph.st
Pk" (TR.)") )²
N
and
W4
N
N
Pk
h+1
R.N
2
N
Σ
N
Ph.ee a by
V R
h+1
In what follows, we shall bound terms W4,1 and W4 in
24 separately.
31

---

Published as a conference paper at ICLR 2024
Step 1: bounding W.11. According Lemma 7 the first term Wa,1 in 124 be bounded in an almost identical fashion as W1,1 in (12). Specifically, let us set
F h+1
(VR1)) h+1)2
1 b, and
N
which clearly obey
| h+1 xx S =H= Ct
and
(,,
N = Cg.
Thus, for all s,,s,a, E [K] x S Ax B, there is
N
k" (s,o,)) hh
(s,a,b,
Σ
& Hence, we can take (N, 8, a. b) = (N s/. an b))) and apply Lemma 7 to yield, with probability at least 1
1 N
W4.1
PP
Phott
R. h+1 )
Xu(sh ar b%, Nb)
N
n=1
N
SABT 5
$
Og log?
G (sh ag by, N Var at af (WArt)
n=1
CgC++ + V C log SABT
11 log? SABT N
1 log² SABT
$
(125)
N
where the first inequality comes from
( ah by, N =
1 (P)." - Pmasa
R.6" (Vh+1)
NE
h+1
with is 1 and the last inequality results from the fact that Ng.
Va at (W h++) s || S 11.
Step 2: bounding W4 We now turn to the other term W4.2 defined in 124). Towards this, we first make the observation that
2
Pric at by
Rit h+1
(Priet at or
R. 2 h+1
(126)
N
==1
which follows from Jensen's inequality. Based on this relation, we can upper bound W4,2 as
Nt
N
2
W4.2 -
1
pk
n.K" h+1
Σ
Phott af M
RAA" h+1
N
NE n=l
n=l
N
N (P +
(Pk
R h+l
V ht1 s. (127)
Ph
a
n=1
n=1
In the following, we would like to apply this relation to prove
41 N2
SABT
2
SABT
Wa & Caz
(v
log²
No log²
(128)
8
5
32

---

Published as a conference paper at ICLR 2024
for constant C22 0.
When W4,2 S O, the claim (128) holds trivially. As a result, we shall focus on the case where W1,2 > O. Let us begin with the term in the first pair of curly brackets of (17). Toward this, let us abuse the notation and set
R.k Ph+1 = h+1
1 b), = N and
which satisfy
1l - Cr
and (s, N Cg.
Akin to our argument for bounding W4,1. invoking Lemma and setting (N, s, a, (N sh ah, b)) imply that, with probability at least there is
No Phonk
H2 log SABT N
H log SABT 5 N
(PA N
R.
h+1
In addition, under the fact that || second pair of curly brackets of (12
R.,"" h+1
P 1 Phat can be straightly bounded by
H and
1, the term in the
N Σ
Σ (Ph + Phistt V
R,K"
(1)
11 +
P
R.K" V+t 1l.o S 2H.
h+1
NE a=1
We have thus finished the proof of the claim
(28)..
Step putting all pieces together.
Combining the results 125 and 128 with 124
yields
W < [aal + W42 S Cif
H
SABT
H
SABT
log2
log
N
5
NE
8
for some constant C4 > O. Taking the definition 120) of Wa together, this bound gives
N
Var a o (V
Rin"" Whtt1
{
( 4h
+1 (s) an
k
bb:) - (ōh
1 +1
(s of
caf
H4
SABT
H²
SABT
+
log²
log² 8
No.
5
NE
Invoke the elementary inequality vutu u S Vu + v for any u, v 2 0 and use the property 122 to obtain
N
Var at ot (V..A=))
1/2
S
Un
(sh an. bl:)
(3h
(s an 0h:))
1/2
N
H
log 1/2 SABT
H
SABT
log
(N
(N
Substitution into 92 directly establishes the desired result 93
C.2 PROOF OF LEMMA 3
Before the proof of 25 present the following Lemma for auxiliary illustration. is worth noting that, similar to Yang et al. 2021] Lemma 4.2) (see also (Jin et al.) 2018b] Lemma C.7)), Lemma 9 is essentially algebraic result leveraging certain relations, w.r.t. the Q-value estimates.
33

---

Published as a conference paper at ICLR 2024
Lemma 9 Assume there exists a constant [H), it holds that
such that for all (s,a.b,k, {x
0 5 Vi(s) - (1) & (x a. -2, a, Sh.
H3 log SABT 5 + th.
H+ Σ
(Th+i(5hitt))
vh (hia() + 40b1
I 1/
nj
(s,
(129)
Consider any E E (0, H.. Then for all 8= ==1,... 1..... logg H c
one has
H Σ h=
H log
SABT 8
ΣEL
V (sh) (*() e [20- 2,,,)
(130)
g
The proof of lemma Wwill be carried in Appendix C We first show how to justify 130 holds. As can be seen, the fact (30 immediately leads
25 if inequality
K
(Vi oh b ( ag b/ =E)
1=1
logg R!
H log
SABT
H SABIA log
SABT
6
(131)
g
2₂
p=1
as desired.
C.2.1 PROOF LEMMA
We first return justify the claim (129). Lemma and Lemma SatamamBdirccee directly verify the left-hand side of since
129
(s, 2 Qi(s,,,b) 2 (s, for all (s, k, e S K x [H]. (132)
The remainder of the proof is thus devoted justifying the upper bound (s,a,b) Q in 129p. Then we reach
Q k+1
(s, a, b)
In x
(s, 2 (s, (s,abt(s,,,b))
Q UCB (s, LLBBAM (s)
-1 - (NN (Q) (OBBAAt (s, Q
A (s, as)
V.ii s.Nt+1+1 h+1 h41
VaNt ( + (Pos.a. - Ph"))
(w vh+i )
7Nt
h+1 (s
where we abbreviate
N No (s. a, b) throughout this subsection long it is clear from the context.
Applying this relation recursively leads to the desired result
k
a) - * (s, b) n/o NO (Q (s, 100-1),.BB1 (s,
Q
N
No
h+1 (11+ (s + (Phiaa - -Ph")
(ver h+1 -
+
7n
h+
H3 H3log SABT
1
H
Σ
Nk
(T
( vhe (oht 4001
Nk
n=1
34

---

Published as a conference paper at ICLR 2024
Here, the last line is valid due to the property (s, and (1 a. H.
H log SABT
(hnaaa - Pk"
S sab
N
and
1 log SABT
(Pr.aa - Pht")
V h++
S Cb
N
based on the Azuma- coama-Hoffdding inequality and union bound, and the following fact
H log
SABT
H log SABT
Cb
N
S 20b
No.
12:1
which is immediate consequence of the elementary property Combined with
Σn vn
S
2 VN
(see Lemma
(s
(shh) S Qn (sh ah b)) 2n (sh an
bb) + Sh.
this establishes the condition 129
Afterwards we prove 130). Accounting for the difference between our algorithm and the one in
Yang et al. 2221), ), paraphrase (Yang al. 2021 Definition 4.2) into the following form that is
convenient for our purpose.
Definition 3 (CC. w) -Seuuenee)) A sequence heksk is called (C, w)-Sequnnce if S wk S w for all and Σx Wk S.C. C.
Combining with 119 we have
wk (V
(V)(s,a,b)
v)(,,,,))) S
Σ wi (Qh(s,,,b) -x, c
()
No (x,ab)) Mm
(Vh 1
Wk 170
H +
km
H log SABT & (s,
WkSh
AwaCb/
(s.aa,)))
wk (s,a,))
H +
Wk Σ n=1
(The (V - 1
K
H log
SABT
WkSA
+
WkCb
(133)
(s,
k=1
For the first term of 133
Nk (s, (s, a, b) is at most once for every state-action pair, and we always have
uk S W. Thus
wkl
(s.a.))))
H
Σ we H1 (N = 0) < wSABH.
(134)
For the second term in
133 we exchange the order of summation and obtain
K
(s.
Na (s,a,))
Vh ( - Vhi (shtt
Wkk
nn
K
NR (ohiah
V Th41(sh/1) - V42 Vh+r
Wy Ty
1=1
+=N
35

---

Published as a conference paper at ICLR 2024
Then for 1 E [K], we let Wi = Σ Ni M)) be
j==N whe Ty and further simplify the above equation to
K
No (s,a,b)
(), (v (4tz(sh4t)) Vha (
K
(V, V (s,
(135)
l=1
Next, we use Lemma
to verify that [whET is a (C, (1 + # sequuuneene
Ny. (sh
S w
Σ
S w
1N S
1
H w,
J=
J2N
No (ch.aa
K
K
K
K Wk S C.
Wi
WHS
=
Wk
1/e
(136)
For the third term of 133). we know that ç is martingale difference sequence (w.r.t both h and k),
and Skl 4H. Hence, by the Hoeffding inequality, have with probability least 1 8/2,
SABT s
CHH log 8
SABT
w I
H log
(137)
The last term of (13) can be bounded by the following inequalities with respective reasons listed below:
3 log SABT
H log SABT
-4 -
WKCb
(138)
(5, a,
N (s.
(maa,) ao (,,)
N (x.a.))
_co H Hogog
SABT
Wk
(139)
(s.0,b)
x=1
[C...b//)) /w]l
SABT
40b
3 log
(140)
(8,0,b)
(1))
SABT 5
S 10cb
H3 log
Cs
(141)
(s.a,))
SABT 10cb H3SABC log 8
(142)
where (i) follows from a rearrangement inequality with Csaab defined Cs,a,b Σi Wknn
(s.a.))
and we always keep mind that 0 < wgn S w, (ii) follows from the integral conversion of E, 1/vi, and (iii) is true because of Cauchy-Schward inequality with Es,,,)) C.a. = Σk wh C.
Plugging the upper bounds of three separate terms in (14). 135 gives us
137 and (42) back into 133
K
SABT
wk
& WSABH + 10cb / HASABC log
SABT
K
+ CH2 log
Wi
(s, a) (1,, (143)
1=1
36

---

Published as a conference paper at ICLR 2024
where the third term is weighted sum of learning errors of the same format, but taken at level h 1. In addition, it has weights [W]K[K] being a (C, (1 + H su)-sequence. Under recursing, the above analysis will also yield
k
wh -V Va(s,,,b)
(SABH(L+ + IM w + c log
SABT
h
SABT
+ +100g HASABC(1 + H
1w log 8
SH <H(SABHew + VCH log 8
SABT
SABT
+ 10cs
H3S log
(144)
5
For every E [V], h [H]
(n.h) wk
1 (v -b (sh ars by) 1, 2*)
(145)
K
((n.k)
Σ
wk
(n,h)
{ k: (vi- v2) (s of b/t) E 20--,,,"' 2,
(146)
By definition, vh E [H]] and [N], (w( J is (C(n.h), ( -)-seqeence. Now consider
bounding Σ wk (n.)) (v+. - vh) (sh an, bb) from both sides. On the one hand, by 144
(m.h) k (Vh, vš) (st a bk) SH / HAC(m.h) log 6
SABT
SABT
+10cs V eH log 8
(n.h)
On the other hand, according to the definition of wi
(n.)) (V%- 1x) (st a bt) (2n-1e)
wk
Combining these sides, we obtaion the following inequality of ((a.h);
(2--1e)((aM)) <eH2SAB+ + V HACCm.))og
log
SABT
100b SABCt log 8
SABT
and thus,
H log
SABT
((mM) S
4n
Finally, we observe that
"
a (2) ( at, bt) E e, 29
1=
H
HOSABIA log SABT ((aN) E
-C(D)
8
(147)
48
h=1
Thus obtain 1130 and conclude the proof of the inequality in Lemma
37

---

Published as a conference paper at ICLR 2024
C.3 PROOF OF LEMMA 4
C.3.1 PROOF OF THE INEQUALITY 27
Consider any state that has been visited at least once during the K episodes. Throughout this proof, we shall adopt the shorthand notation
k' =;,0)
which denotes the index of the episode in which state s is visited for the i-th time at step h. Given that (s) and V (s) are only updated during the episodes with indices coming from {i 1 S k s K). it suffices to show that for any s and the corresponding 1 I k² I K, the claim (27 holds in the sense that
(s) V R. (s) 2
(148)
Towards this end, we look at three scenarios separately.
Case 1. Suppose that kt obeys
V (8) (8)>1 >
(149)
or
Vh +1 + (s) S 1 and 2 (s) True.
(150)
h
The above conditions correspond the ones in line 17 and line 19 of Algorithm 3 which means that Vill is updated during the - episode. Thus, it results in
+1 V
V
(8)
This satisfies (48) obviously.
Case 2. Suppose that kio is the first time such that 149) and (15)) are violated, namely,
= min
+1 (s) - w +1 (s) and u (s) = False
(151)
We make several observations. Firstly, combined with the update rules (lines 16-19 of Algorithm B the definition [51] reveals that V has been updated in the 1 episode, thus indicating that
R (s) R (s) Vhh t0
(8) h (s).
(152)
Additionally, V (s) is not updated during the 1:f0-th episode according to the definition (151). namely,
R R +1 (s) = V h
Vh
(153)
Therefore, the definition of k indicates that either 149 or 150 is satisfied in the previous episode k k in which was visited. If (149) is satisfied, then lines 18-19 in Algorithm tell us that
True t (s)
".
k (s),
(154)
which, however, contradicts the assumption to (s) = False 151p. Therefore, in the 1 1 episode, (150) is satisfied, thus leading to
(s)
+1 (s) h
+1)()) S 1.
(155)
b
From 152
153 and
155
see that
R, +1 k00 +1
(s)
(s)
R.A
h (s) - kx
110+1
(s) = h (s) - -
100
100+1 (s)
(156)
h
8'0 (s) V
1.
(157)
38

---

Published as a conference paper at ICLR 2024
4 +1 2 (8) 2 V (s), and (ii) follows from (155).
where (i) holds since make note of the fact that
In addition, we
h
R
+'0+1 (s) = V (s) V
(s)
(158)
which follows from (156) and the monotonicity of V (8) in k. With the above results in place, arrive at the advertised bound (148) when ig-
Case 3.
Consider any i> io- It is easy verify that
Vh +1
(s) (s)
1 (s) 11 and
# u (s)
False.
(159)
It then follows that
R. (1) Vil
+1
(ii)
(ii)
V. +1(+++)())))))))))) +
(160)
Here, (i) holds due to the monotonicity of V and V consequence of (157), (iii) comes from the definition [15]] of to. Further, according to see Lemma and Lemma [60 can be expressed as
(see line of Algorithm 3). (ii)
FR,K" +1 (s)
(s) +
(161)
where the first inequality arises since V, is lower bound Vi (see Lemma B and the last inequality is valid since V k'+1
(s) (see Lemma 2) In addition, view of the monotonicity
of V (see line 15 of Algorithm and the update rule line 17 of Algorithm we know that
F IL.k' +1 (s)
2 V (s).
The preceding two bounds taken collectively demonstrate that
= VRR (8) V (8) 22
R. +1
thus justifynng [18 for this case.
Therefore, we have established
(188) for all cases, and hence 27 also holds for all cases.
C.3.2 PROOF OF THE INEQUALITY 28 Suppose that
R. holds for some K. Then there are two possible scenarios to look at:
V
R.K
*
(162)
Case 1. If the condition in line 16 and line 18 of Algorithm are violated at step of the k-th episode, this means that we have
VA (st) V v (st) S and ut False
(163)
in this case. Then for any A/' > ki one necessarily has
(x < V (st) ( S 1,
(164)
(s xf (s False.
where the first property makes use of the monotonicity of V and V (see (23) turn, Condition 164 implies that V will no longer be updated after the k-th episode (see line 16 of Algorithm 3). thus indicating that
RA
($
V.R.
R.
(s
V.RK (s))
(165)
This, however, contradicts the assumption 162
39

---

Published as a conference paper at ICLR 2024
Case 2. If the condition in either line 16 or line 18 of Algorithm iss satisfied at step h of the k-th episode, then the update rule line 16 Algorithm implies that
V (5%)
V (sh) >1 1,
(166)
or
(5 V (5h) 1
and u/ (s%) True.
(167)
To summarize, the above argument demonstrates that 162 can only occur if either (166) holds. With the above observation in place, we can proceed with the following decomposition:
(167
K
V.R
R.K (0%)
1=1 k=1
V
R.N
(sh))
VR (s%) 1 V Rik (s%)
VR.
(sh) x0) wi + #22
(168)
where
Vi (sht)
V v...k (sh))
(v k+1 (sh) ( 1 and 2. True)
W1
and
K
(5h)
LR (bh)) 11 -
W2
h
1=1
k=1
Regarding w1 in (668,, it is readily seen that for all S
K
Σ
(V Vi
( (s) - (s) S and (s) = True $
(169)
which arises since, for each E S, the above condition is satisfied in at most one episode, owing to the monotonicity property of V ho Vr, and the update rule for u, in line 18 of Algorithm As result, one has
W1 < H 1= 1=
(v
k+1 (of) (x+) S 1 and (x True)
H (s) S 1 and (s) True) s
H ΣΣΣ>>>> (r
Σ
H2S,
#ES
I| VR. 1100 I H. Substitution into
where the first inequality holds since
(168
yields
"
ΣΣ
(())))))))))))))))))))
VR
R.K (s < H2S w2.
(170)
h
h=1k=1
To complete the proof, it boils down to bounding the term wy defined in 168 To begin with, note that
R.K (xt) 2 V/ (s 2 (>4))
where we make use of the optimism of V
RR, (sf) stated in Lemma (cf. (20) and the pessimism of
V, Lemma
(see As a result, we can obtain
K
(V(())) - 1 (eei)(((vvv (V (h(st) > 1).
W2 <
(171)
k=
40

---

Published as a conference paper at ICLR 2024
Further, let us make note of the following elementary identity
(s oh 5%) S 1 I b/. (o oh. t)at.
This allows us to obtain
H K
1(V at b/) - bkt > t)at
W2 S
(Vi of 08) - ( ath
b/) > 1
x I
K
af af (/ - (oh, ari Uk) > 1 1)dd.
k=
With the property (25 in Lemma
3
we can further obtain
5 SABT
SABT
8
dt S SAB log
(172)
12
8
Combining the above bounds
171 and
172
with 170 establishes
H
R.k. (5
V
(8h)) S
H
SABlog
SABT
H SAB log
SABT
8
8
h=1k= ==1
as claimed.
D PROOF OF LEMMA 5
A starting point for proving this lemma is the upper bound already derived in (31) and we in- tend further bound the first term on the right-hand side of BT.. Recalling the expression of @h RRt+1 (sh at, bl)) in 70p and (71. we can derive
In (0h, A (/)) Qi (sh ahs b%t) = On n -h
RKK
(o Oh:
k 1/)
@h ah b7,
(173)
N
(s) at
170
No (sh (h
(ht
R.1 (s oti 0%) (5% aj, bl))
The
No. (s aa
bn
R
No
Σ
No. (0
Vh ( - v.l.A" (obit1)
On
N (oh
+
na
(st No.
1
R
h+1
(s - ah Viita)
Specifically, according to 19 with B there is
R +1
Rtk B
and the initialization the
a ot, = H.
R.k (s)
an
k by.)
(5 *
on: (b))
(174)
No- (sf. 1b2) H +
BRA (shi ari bit) + ( Ot bbt) 3/4
20p 20,H2
SABT
5110
log
8
NK- (sh
No. 2ooh
Vic ( - F.R.e"
h+1 (shit1)
mp
N ([skaakk. b
No. (s
V
R,K'
h+1 (6h - Phist att o8 Vh+t1
n1
41

---

Published as a conference paper at ICLR 2024
We also demonstrate
(s ahi b%) Qn (sh ah, b%) = R. n (oR (sh oli b/))
Q%
ah b%) (175)
N
( ($h an b%) Q% (s/ ar, b/))
R..
= 1/0
No (s
Σ
No
( - LRA (oftt1)
On
N
(0% 6/.
(0)
n
R h+1 (s
Ph.st bf Viiii)
n
Similarly with BR.
Bh* and the initialization 2h (s bb) H. there is
2 (sh & b/:) Qh (3 a b()
(176)
H2
SABT
2 - 700
H BR (s) az. b%)
(Nh- att bb)) 3/4 log
8
(sh
No
(s of
1/ 1ht (iit((hhtt)) - B.K (shit2)
7n
No
No-
- (2
RR,k' h+1 (sh+1) - Phisk al dh Vi+t1
Summing over all 1 S k S K, taking 174 and 1766 collectively demonstrates that
K
(sh at b
2h.
R. (s bf))
K
No "
+ Br Rik (shn ah, bt) + B.k (sh -h)
2/11
K
4o,
SABT
log
(N (sh, abs bkt)
3/4
5
1=
Nok (6.))
No (th
(hh h+1 (s
(s
h+1
No
N (s8,
(sh+t:) )
-
h+1
shutt)
N
No. (sh
R.k" ke h+1
1
R
dt ((itt)) (177)
+
Th
8/11)
h+1
1=1
Next, we control each term in 177 separately.
Regarding the first term of 177). we make two observations. To begin with,
No. (
Σ
Th S SABB
(178)
(xx
42

---

Published as a conference paper at ICLR 2024
where the last inequality follows since n/ 0 for all n observed that
0 (see 17
Next, it is also
N (x.aa
Σ
N (sh at b/1))
To3/1
( Σ
4(N (s, a, b)) b))
4(SAB))/4114
(x.x.))5xAA33
(179)
where the last inequality comes from Holder's inequality
Σ
(N
(N,
(xxx,))5xxAxB
3/4
1/4 N (s,a,) S(SABB3/ARA4
Σ
Σ
(xxx,))ESxxxx
(xxo,))ESxxxx
Combining above bounds yields
K
N (sh,
+ BiRk (sh a b/:)) + R (sh ah 6%)
211
K
40,
SABT
log 5
(Nr (st ot, 0/;)) 3/4
R.k (sh an (SAA ///4///////""""/ 2 SABT <2HSAB+B, (sh ar b%. +13
(180)
We turn the second term of 177 A little algebra gives
K No-1
No (0%
(V N+t (shiti) khit1 At" (shh.))
Th
K
af
T (M (Vnil(hh1)) - Vhet (sh+1)))
(181)
1=1 (
where the second line replaces kn (resp. n) with (resp. N/. (s// d,))). Combined with the property EN., vi 51+ 1/H (see Lemma 1.. we get
Vl (htz(sh+1) 1h4r
181
1 +
H
(v+ ( (
(182)
where the last relation replaces / with k.
43

---

Published as a conference paper at ICLR 2024
When it comes to the last term of 177 based on Vi+t1 (0%+1) = Phish by. h+1 we can
derive
K
No
(
1/n
No
R.R. (shitz)
-
V
h+1
(hita)
k=
No
(oh (hh
n V
R.
s/+ )
n2 Σ
RR
h+1 (shtt))
N
(+h (8)
No.
(sh.oh
(Vitz (shitz)
V Vh+11 nm
(shtt) )
17n
K
NK- (sh
1
Rik
(slitt)
- P Phott aa of bh Vieta
h+1
K
Σ
No
(Vi++ (shit.)
vh+1
(shtt1)
==1
N (f),
K
N
n Σ
RR h+1
(sitt)
Phi Viita
n
(183)
No (1 N (M there is
With A =Ik
* ((P) Pnott ) (Viter - -bBAA) - (PA ok (Vāun vRat)) No (3b
183
Vilkk' (shims)
Phiott FRRi
Di=l
+ A
No (s% aji bl:)
Σ No (shi
h+1 (shit1)
V.R.k
Gi=l
1
N (sk att b%)
Here, the first equality holds since Vitz(stt h+11 (oft)1=== PA" (Vi.n h41 (in view of the definition of pk in (15). the final equality can be seen via simple rearrangement of the terms, while in the last line we replace hn (resp. n) with k (resp. N/Cs (s/; at ()))
44

---

Published as a conference paper at ICLR 2024
Taking the above bounds together with (77) and (31) rearrange terms reach
(5 (shh)
k
Qh
R
(s 1/) - 2 a b//) + (h)
k=1
[
(+
( + +Bn
(sh at by)) + Btt afh bh)
SABT
K
+ 2HSAB + 16 (SAB) // log
Σ
ch
k=1 (Ph Phisk
+ N ((p PhottiatM
(vh-i - -V h+1l
(Viti ((tt))) (184)
Σ
Nh (62 02)
Villk' (shitt))
Phistiat ih by.
V.Rk h+1
+ A
No. (sh ahi
Σ Nu (f i=
(vRR'
h+1 (sh+1)
R.R Phint alt
1et1
A
(185)
N (sh, ah 6%)
Thus far, we have established crucial connection between Σ (Vx(s)) v((o))) at step ( at step h 1. Clearly, the term Σ (V (5)+1)
and 2k=1 (V (
1 15)++)) can be further bounded in the same manner. As a result, by recursively applying
the above relation (185) over the time steps h 1,2,... H and using the terminal condition
v VH+1= = VH+1 O, we can immediately arrive at the advertised bound in Lemma 5
E PROOF OF LEMMA 6
E. BOUNDING THE TERM D
First of all, let us look at the first two terms of Di in (35a). Recognizing the following elementary inequality
(1+))*
(1+ 1 H Se for all h 1,2, +
(186)
are allowed to upper bound the first two terms in 35a as follows:
h-1
SABT
2HSAB 16c, H² (SAB) K log
SABT
SABT
HPSAB 3 (SAB))1 K/4 log
< 5.
SAB log
VI
SAB SABT
VH'SABT,
(187)
8
where the last inequality can be shown using the AM-GM inequality follows:
SABT
SABT
3/A 1// log
SAB log
(HASAB))/
8
SABT
< H log
VH3SSAK.
45

---

Published as a conference paper at ICLR 2024
We now left with the last term of D1 in (35a). Towards this, we know that S is martingale difference sequence (w.rt both h and k),, and 5h I 4H. Hence by the Azuma-Hoeffure inequality
and union bound, we have with probability at least 1 - 5/2,
H
A-1
SABT HKlog log
SABT
HK
2
H2T H2Tlog
(188)
H
5
h=1
h=1
with probability exceeding
8.
Combining 187) and (88) with the definition (35a) of D2 immediately leads to the claimed bound.
E.2 BOUNDING THE TERM 22
In view of the definition of B (sho b decompose D2 (cf. (35b) as follows:
R.k
bk) (resp. BR. ai b/)) in line 15 Algorithm can
11
SABT
K
Vh (s) a b/) - ( (s oh 6/))²
a.
D2= =
log
H
N/ (5% at. b%.)
h=1
H
h-1
SABT
K
4 (s att b
(on 2 (s ar b/))2
++
H
cb
log
( ott 6%,)
h=1
H
1
h-1
SABT 8
K
wi at bb) ( (s at b2))²
1+ H
cb
H log
( ot b(:)
h=1
k=1
H
h-1
SABT
2h (st ati 6/)
(shh ah, 0121)
1 1
H
Cb
log
(s ah 6%)
A=1
SABT
H
K
aak
Vh
(sh at M//)
(o) a (sh at 0t:))
H log
No ax. b%)
k=1
SABT
H
K
Wh (sh at bb)
(oh r
(sh at 12))²
log
(189)
8
(s bt)
where the last relation holds due to (186) and the symmetry of [15" (6), 10 260 1 In what follows, we intend to bound these two terms separately.
and ( 17
Step 1: upper bounding the first term in 189
Towards this, we make the observation that
K
a, Wh
(sh at, bt)) - ai (sh ar b
a.k Un (sh at, by:)
( ot b7,)
(s at 6%)
K
N att Σ
h-1 (s (st44))
n= Mm
(190)
a 1i)
aak
where the second line follows from the update rule of V. in 102
Combining the relation
V with
R.R.A ( (s+) < 2 (cf. (27) and the property Σ co
(oh a b.)
Min
(o of b.b))
< 1 (cf. 18)
1900) yields
K
a,k Vh
(sk k by:) - (0% 2 (stt ah, (/)))
K
4
< 4VSAAK. (191)
No. (s) a b%.)
N ( of
46

---

Published as a conference paper at ICLR 2024
Here, the last inequality holds due the following fact:
N (a.a.))
S2
Σ
V (s,,,)))
( az b7)
(xxx,))
n=1
(s..
2
Σ
Σ
(5, = 2VSA
(xxx)))SXAxX
(sxx,))SSxxx
(192)
where the last line arises from Cauchy-Schwarz, and the basic fact that E(.a,)) No (s, = K.
J.k
J.k
Step upper bounding the second term in
189
Recalling the update rules of o
and &h in
121
we have
K
Th (0% at 0%) (0h k (sh ah. b8))²
R
(193)
(sh 242
N at, 67,
with
af (f) Σ - (vtt kn 1)
Na MD V. (2htta) 2
R
(s ah b)))
(1 az (%)
Additionally, the quantity T2t defined in (93) obeys
Σ N (oR. )
(V
R.A h+1
())+)))²
(s
2
(S a22 b))
D (o b/) (Vi+i (2htt))²
N (oh n=1
V Vi+ (8%+t1)
)
2
S Li + L2,
(s o bk)
( k b))
(194)
which arises from the fact that 2 V R,k""
h+1 2 Vi++ 2 0 for all kn s K, and
L Σ No (h. kh)
2H (V
R.A."
h+1 (sftm) - (+
(195)
N ah b/))
L E ENEro 1h
E Mh M/ V (ohtt)))))))
(196)
( ahh. b%))
(s at bn
Therefore, we have
(VRA" (shtt1))² (Vit
(VRAl (sh + V (s (V Rin (st" - V
S 2H 2H (V h+1 (o - Vitt (s
With 194h in mind, we shall proceed bound each term in 194 separately.
The first term L1 can be straightforwardly bounded as follows
NO al (%) V'1 ('(v''' 33 + + at bi:)
1= = 2H
Σ
( of
2H
S 6H + (* a b
(i at bt).
(197)
where (s at, b))) is defined as
N
* (
an bh)
Σ VI(('>3)
(198)
with V =V-lk"" h+1 (0/+1) Vita Vitt(sh++) (3t771)
47

---

Published as a conference paper at ICLR 2024
When it comes to the second term L2, claim that
log² SABT
L2 S Var h.ot ok on (V++1) + H²
(199)
(# of b8)
which will be justified Appendix E.2.1
Plugging 197 and 199) into 1944) and 193)
allows one demonstrate that
n k.k (sh, ah; bt,) (op (sk ax 0/ 2
(s at 6%)
K
11 H (s), ot bt),
log SAT
ea of (Vi+t2) +112,
(s oh, b%)) \
N (sh aft b%)
NK ( ax b%)
H
H (sh an 6%)
Var ah (Vi+1)
H log' 1/2 SABT
(o a b))
(s ab b%))
(o 0%)
(N a b)) 3/4 (200)
Combined with
192 and
179
there is
( oh.
200 S v HSABK
(5 (2)
K
of (Vi+1) ( a bp)
+ H(SB))3/4 (Klog² SABT 1/4
(201)
8
Step putting together the preceding results.
Finally, the above results in 191 and 201 taken
collectively with 119) lead to
SABT 8
SABT
(sh ali 07) (ox (sh at b/))2
D2
H3SABK log
log
(5 an, bt)
SABT
SABT
H3SABK log
K (SAB) 3/1
log
8
log
SABT
ΣΣ
K
Varn at or (V+++)
H log
SABT
V ( ok) ( a by.)
(s o bi)
A=1k=1
Furthermore, we claimed two inequalities as follows:
K Varn.eg of on (Vi+1)
SABT
SABT
& H'SABT log
+ 3.5 3.B. log
(202)
( af b9)
H K
( ai b S H 3/2 SABT
(203)
(5) at, bt)
8
1= 1=
whose proofs are postponed Appendix E.2.2 and Appendix E.2.3 respectively. Thus, there is
SABT
SABT
HABBBlog SABT
D25 /
HSSABK log
H2 (SAB)) 12/4
log
SABT
SABT 6
H3SABK log
SAB log
SABT 8
SABT
H2SABT log
+ SHB log
8
48

---

Published as a conference paper at ICLR 2024
where the second line above is valid since
(S(AA))0 K 1/4
log
5/4
SABT
(SAB() log
SABT)
(I&SABK log 8
SABT
1/4
8
SABT
SABT HASABK log 6
2 H22 log
5
SABT
SABT
-22. log
HASABT log
5
due to the Cauchy-Schwand inequality. This concludes the proof of the advertised upper bound on D2.
E.2.1 PROOF OF THE INEQUALITY (99
Akin to the proof of W4,1 in (125 let
1 and bi(,,,,b,)) N
F
(Vi+1)² )
By observing and setting
1 Cg =
1F S H² C₁,
N
we can apply Lemma 7 to yield
N
(Vh+i (sh
Phott at (Vi+1)²
N
N
log SABT N
Σ
(Ph - (Vitz)) S H2
HPV
N
with probability at least 1 5. Similarly, by applying the trivial bound |I S H and Lemma 7 we can obtain
N
log SABT N
Σ (o N 1=1
Ph. 12 Vitt
Σ
[(ph -Phot
Vit1 S
1=1
with probability at least - 8. Recalling from (6) the definition
Varn, a of (V Pa.ag.at at My (Vi+1)² (Pr. at 1i
we can use the preceding two bounds and the triangle inequality to show that: with probability at least 1 5, there is
V (5 22
Vitn (
Varn,sk af of (Vitt)
N 1=1
N n=1
N
V Vi (ofitt)) 1
N
V (s ( 2- 2- at (Vini)²
Σ n=1
-Phietiaat 12
N
n=1
N
N Viuu (f ) a Via
log SABT Nk
Vian (s ) Phisk Phokkatt Vi+i
H2
NE m=1
And thus, with the fact that 1V < H, we get
No
log² SABT 5
V 12
V
Varn (Vitt)
S 112
NE
NE n=l
Nk
49

---

Published as a conference paper at ICLR 2024
E.2.2 PROOF OF THE INEQUALITY (022)
To begin with, we make the observation that
K
Varn.t (Vi+1) (o 0 Uk)
N (s.a.))
Σ (s,a,b)ESxAx3 AxB
Σ
n
7=
2
Σ
NK (s, a, Varh (Vitz))
(xxx.b)ESxAX
which relies on the fact that Σn
It then follows that
H K
Varn at (V/+1)
( ob.b%)) b/)
1=
R=
2
Σ
N (s, aa
(s.0,b)
Σ
Σ
1.
Σ
E
N% (s, a, Var (Vi+1)
A=1
(sx
A=1 xxxx
K
2v HSAB
Σ
Varn.et of 1)
(204)
h=1k=1
where the second inequality invokes the Cauchy-Schwarz inequality.
The rest of the proof is then dedicated to bounding 204 Towards this end, we first decompose
,, at Mi (i++))
H
H
K
Var h at bE (Vitt))
Var (Vi+t)
Var of (Vitz)
h=1
H
SABT 8
SHT + Holog
Varn,s (Vi+1)
Varn af (
(205)
h=
where the last inequality follows from (Jin et 2018b Lemma C.5) for formal proof. The second term on the right-hand side of (205) can be bounded as follows
Varn,et, ah (Vi+1) Var (Vitta)
H
K
Ph.ct ot (Vitz)² (Ph.ot Viita)² at or (vxt))++
1(p+(PPnng (Print (Pnottaaee of vatt)
h=
#
K
Phottett of (VVit Virii (Vhi1 + vati))
#=1
(Phitt Vinm)? (Phot vitta²
(206)
50

---

Published as a conference paper at ICLR 2024
Before next proof, we first state that
Phost, (Viitz - vitta (Vi+t + virta)
Phist, ag on (Vh+i - vatti (11Vit1l + 1| s 2H P Phott of (Vi+1 - vati)
(Phot a Vitt)² (Phsti (itti)?
Ph of (Vh+1 Vitti P Phoetot of or. (Vi41 + viti) 2H P (Vi+1 - viti)
And thus, there is
H
206
4H
P (Vi+t vatta)
h=10
H
K
Pr at of (V v(+ta)
2
4H
1=1
k=1
K
V (+ Vh ( + (Protaat.t h+1 {
4H
K
S
(8h+1 + x
h=1k=1
SABT
SABT
2 Tlog
V HTSABTTog log 8
H SAB
SAT
HSSBTllg log
SAB.
(207)
where we define
41 = -V - v (
X = (Phot,aa,ot -hh) (V (Vtt(())))) - vh+1).
(208)
shall take a moment to explain how we derive 207). The inequality (ii) valid since V S
V S Vh+1 and Vi+1 S V < V4t1i and (iii) results from the following two bounds:
H
K
11
SABT 8
SABT
Σ
SH + H
10cb V CHSSABT log
b+1
8
h=1k=1
h=1
SABT
H SABAB log
+ SAB
(209a)
SABT
ΣΣ l=
X H
HVTlog Tlog
(209b)
where the first inequality in (09g) comes from (44) with Wi = and C' < K, and 209b) comes from the Azuma-Hoeffdin inequality and union bound.
51

---

Published as a conference paper at ICLR 2024
As consequence, substituting 200 and (207
into 204
we reach
Var of of (Vi++)
(1) ai 0%
SABT HASAB
X VHSABY HT + H log
& VH'SABTT + (SAB))) Tog SABT 1/4
HH2
VH'SSBT + (HSSBB log
SABT 1/4
(H²& 1/2 + H2B
SABT
SABT
2 V HPSABTIO log 8
HABSABBB log
8
where we have applied the basic inequality 2ab S a² + b² for any a,b 0.
E.2.3 PROOF OF THE INEQUALITY 2003)
First, it observed that
K O og. bt)
N (s.0.))
(s, a.
E
(* af, bf)
n
(sx,,))
Σ
No (s.a.))
(ogg, S
SAB
Σ (sa.))SSxxx
N (s.a,))
log
(xx..))Exxxx
(210)
Here, the first inequality holds by the monotonicity property of ( as) with respect to k (see its definition in (188) due to the same property of 1i+1 while the second incquality comes from Cauchy-Schwart
To continue, with V V R.A"" h+1 (5h+11) - Vi++1 (s/ note that
K Σ
No (s.a,b) (s,
(V))
x
H
K
Vv h+1 (sh
Vir (oh+))))))) 1 (v V ( + 1b ( >
h=1
H
K
V Vh+ (s (s ( - ( > 1)
H
K
V Thtz(sh44) (sftz1)) (V ( - V/ (
1=1
H K
S VH
3 Vh ( - Vh ( (vh+z(of+p)) - ( > 1)) (211)
h=1k=1
where the first inequality follows from Lemma 4 (cf. 27 and Lemma 2 (so that V (()
(sh < V (* + 2 (s
1), the penultimate inequality holds since S
Vi Th (s
when 1 (vi ( v (s/+1) > 1) * O. and the last inequality (s -V
is consequence of the Cauchy-Schwarc inequalitt.
52

---

Published as a conference paper at ICLR 2024
Combining the above relation with 171 and applying the triangle inequality, demonstrate that
(a.. (8,0,b) V HiSABlog 5
SABT
(x.,,))ESxAxB
where the inequality follows directly from 28 Substitution into
210 gives
( af, by:) ( a% bg)
s(VSABlogT)
SABT
xH SAB log SABT
H H7SAB log
thus concluding the proof.
E.3 BOUNDING THE TERM 2)
First of all, there is
NA
X/
1 H
Σ
1+ (1+
1+
111 H
se (212)
N= (6
where the first inequality in 212 follows from the property Σn=n The
N < 1 + 1/H in Lemma and
the last inequality in (212 results from 186). Then we could decompose the expression of D3 in (35c as follows
D3 Da, + D3.2 Da.3 Dz,4
with
H
D&11
Σ
Σ
M Ph.et.at (Vitz VR+41)
(213)
hm km
H
K
E Eisntor F-- (5 Photiate ok th
FR.
D,,2
(214)
No at 1/))
h=1 k=1
H
D3.3
(Ph Ph (Vi+1 V.R.A.
(215)
h=1 k=1
H
(L
R.k* (s% 1)- P
Prost.at.d o k4t1)
R.
D3,
(216)
NY. ( anc, b%)
h=1k=1
In the sequel, shall control each of these two terms separately.
Step 1: upper bounding P3,1 and D3.3- We plan control this term by means of Lemma For notational simplicity, let us define
N(s.a,b,h) = N
(s. a,
and set
h-1 N(ch
1
Flin
h+1 Vi and (s = X
E
H
n=
Given the fact that R.k h+1 (s), Vhin (s) E (0. H and the condition 212). it is readily seen that
pb h+1 Il < H = C₁ and G at, 1/ S = Cs.
53

---

Published as a conference paper at ICLR 2024
Apply Lemma 8 to yield, with probability at least 8/2, there is
H K
[Da.1] =
ΣΣ
ahint.ag.0 b4 (Vi+1 v
h=1 k=1
K + C.CCHSAB log
K
CCCBAS
B [P log 8
8
24
Ph (R h+l Vitni HSAB B
log 8
T + HHBSBBlo log
T 8
H2SAB
K Σ
Phist of oy
(V R.A.
h+1
Vitti) log
T + HHSAB log
T
(217)
h=1k=1
with Xx, (P Phot (Vi++ (V
It then comes down to controlling the sum Σi= E Phott.af at o h+1 Vi++).
R.
Towards this
end, we first single out the following useful fact: with probability least 1 8/4.
ΣΣ pk
H K
(V h+1
Vi+t)
(1)
ΣΣ
H K
Pk (v
h+1
+2 +2-Vi+t)
1=1k=1
4=1k=1
< 21KK
K
(v* ( - Vh- (+++a)))))
S 11
SABK log 8
SABT
SAB+BHK
h=1k=1
(218)
where (i) holds according 27 and (ii) is valid since
H
K
H
K
(
Vitt (s
Vk (5h+t) - Vh vh+1(sh+1)
1=11 1=1
SABT H
S H V
SABK log
where the first inequality follows since Vi41 V/ and the second inequality comes from 209a Additionally, invoking Freedman's 's inequality (see Lemma 8 with ca. 1 and W h+1 (so that S (s)))= < H) directly leads to
R,k
H
K
(Ph
Ph.ntt ( Vitt)
h+i
S V TH log
H log
x
H K log
with probability at least 5/4, which which taken collectively with 218 reveals that
H K
R,k (hat - Vitti)
Pa Pat
K
H K
R.k h+1
- Vitt)
(Pk P Pag.ati 1.) (V Vitta)
1=1 R=1
h= k=1
SABT
SH SABK log
+ SAB + HK
(219)
8
54

---

Published as a conference paper at ICLR 2024
with probability at least 8/2. Substitution into 217 then gives
H
[Da,1]
(Pk Ph.ot.at ag.. 02 (Vitt
R.k vi+1)
k=1
H
K
T Ph Ph,s by (Viti vi++i) log 8
T 8
H
+ SAB log
h=1k= 1=
SABT
T SAB log 8
HSSA
H
SABK log 5
+ H + HK
log 8
+
According to the Cauchy-Schward inequality, there is
SABT
SABT
SABT
SABA log
H log
VHK S SA log
+ HK,
8
8
and then we can further obtain
SABT
T
T
[Da,1
HSSAB
Bog
+ H HH
log 8
+ H' log
5
SABT
SABT
HASABKlog 8
+ H3B log
8
SABT
SABT
H'SABT log
HAS log 8
(220)
8
Similarly, (Da.3 S / HHSSABTlo SABT H8BSAB log SABT
Step 2: upper bounding Da.2 and D3,4. According to the monotonicity property h+1 2
RR,++1 h+1
2 Whtt we make the following observation:
D3.2 I
Σ
(Vhit' (sh+1) Phintiat of
V..K)
(S k
K
No
y ( (5/44)) - ( (sh+ + (Ph Ph My v
R.K
a ME)
( (ah (f dil) 1 < log T and X/ s e (cf. (112), there is
And with the facts that Σ
D==N N (of a bit)
H
(VR. R. (5)+1) VRi (s
D3.2 ("
H
K
K
bk
N (Ph Phott ) Vitz
h= k=
# N
(Ph Ph (Vl.K Vitt).
(221)
n
A=1 1=1k=1n=Nhhe .o bt)
In what follows, we shall control the three terms in 221 separately.
* The first term in
(221
can be controlled by Lemma (cf. (28 as follows:
(cf.
ΣΣ
H K
R.k (
V R. h+t (sf+z)) S H SAB log 8
SABT
(222)
4=1
t=1
with probability least 1 5/3.
55

---

Published as a conference paper at ICLR 2024
To control the second term in 221 abuse the notation by setting
N(s, a, b. h) = N k 11 (s,, a, b)
and
Ph+1
V
and
Ch ahe bk) b/)==
Σ
(
which clearly satisty
N(ch Nf
|| S H =:=GG Cr and [C at, bx) S
Σ
1
e elog T C...
n
n= (0) aj
No (sh
Here, we have made use of the properties Σ
S log X S
n= (.)
(ef. (222 ). With these in place, applying Lemma reveals that, with probability least
8/3.
H K N a
X (Ph
H
Σ
Pr.et. Vit1
X
T
NE (5 (
h=1k=1
CHSSB Ei [1(P% Phisi at WW
K
log T
T +C,CHHABB log
T Var h of (V (Vitt) HSAB log σ H'SABloog T 8'
Loh.ok A (Ph - Ph,et at Vi44 and the last line comes from where NEA En= No of the definition in (6). Therefore, we have
N ( Σ
X (Ph Phist Vh+i Vi+t
N
SABT
T + SAB log
HSAB(HT SH + H*SAB) log*
8
5
SABT
T
HSAA H + HASAB) log' 8
+ 22 SAB log
HSSABTlo SABT
SABT
H log² 8
(223)
where the second line holds due to 205 and
207 and the last line is valid since
HT + VHTSABT HT + HASAB VHT & HT + H SAB
due the Sauchy-Schwarr inequality.
Turning attention the third term of (221). need to properly cope with the dependency kl Towards this, shall resort the standard epsilon-net argument
between pk and A+l (see, e.g., Tao 2012)), which will be presented in Appendix E.3. The final bound reads
like
Ak (P)
Σ
Ph.ot (VR.K
Vi+1)
n
m=
SABT
SABT (224)
H33.8
11SABBK log
56

---

Published as a conference paper at ICLR 2024
Combining (222
223 and (24 with (211)
the union bound to demonstrate
that
SABT
HASABTlog SABT
2,,2 S C3 H SAB log"
(225)
with probability at least 1 ó, where C3 > is some constant.
Similarly, Da,4 I C3,4 H SAB log SABT
H2SABT log" SABT
with probability at least
1 6, where C3,4 is constant.
Step 3: final bound of D3- Putting the above results (200) and 225
together, we immediately
arrive at
SABT
SABT
D3 $ [3.1|+ + Pas.3 -3,44 S Cr,3 H lo
H'SABT
(226)
with probability least 1 26, where C.,3 > 0 is some constant. This immediately concludes the proof.
E.3.1
PROOF OF (224
Step 1: concentration bounds for fixed group of vectors.
Consider a fixed group of vectors
{V E R < h < H} obeying the following properties:
Vit S Vh+1 S H
for < shsn H.
(227)
We intend control the following sum
H
N
2 (Ph Ph.tt at up) (V7 Vū+1).
Aumm R=m
To do so, we shall resort to Lemma
For the moment, let us take N(s,, a, h)) = N NKK (s, a, and
(( b.. X
F = V
Viti
and
Ch a =
n
It is easy to see that
Ni a
(1))s Se
Σ
S Telogg =: C.
and | H SH= Ct,
n
N= af
which hold due the facts A (f
log and X (cf. (212))
well as the
(e af Mg)
property that Vid (s),,,,, (s+ E [0, H). Thus, invoking Lemma 8 yields
H K
NR
X (Ph ah (V Vi+t)
Σ
Xk.h
Am
hml km
H K C2
KHSAB
KSABB
S
E
P log
+ Cr log
50
80
h=1 1=1
H
K
KHSAB
K KHABB
S
H
Ph (V Vitta) (log" T) log
+ H (log log
60
60
(228)
with probability at least Ep. where the choice of da will be revealed momentarily.
57

---

Published as a conference paper at ICLR 2024
Step 2: constructing and controlling epsilon net. Our argument in Step is only applicable to a fixed group of vectors. The next step is then to construct an epsilon net that allows one to cover the set of interest. Specifically, let construct epsilon net Wh (the value of a will be specified shortly) for each E [H] such that:
a) For any Va+1 [0, H] one can find a point V441 NN+11, obeying
S Vh+1(() h+11 (s) S a
for all 8 E S;
b) Its cardinality obeys
H
Nit1aa -
(229)
(1
Clearly, this also means that
H HH.0 (a)
su
N2 x Na.a x ... ....X.M NN &
Set 6 ( H) SH Taking 228
together the union bound implics that: with probability at least
1 60 H SH
= 1 - 5/6, one has
H
K No
(oh (
N (Ph Phoefiat (Va41 Vit1)
Σ
k=
NY. M
H K
KHSAB 80
K HSSAB
H
Protiatt (Vuet Vitti (log2 T) log
+ (log 7) log
80
1=1
H K
SAT da + +H
SABT
H'SAB Σ>
Σ im1
Prot ot (Vrrt Vittz) (log² T) log
8a
(230)
simultaneously for all (Vuet | h H) obeying Vd E NN (h [H).
Step 3: obtaining uniform bounds. We are now positioned to establish uniform bound over the
entire set of interest. Consider an arbitrary group of vectors {VT_ R | < h < H) obeying
227 By construction, one can find group of points {vnet E W E [H]} such that
0 S Vh+1 (s) Vhat (8) S
for all (h, S x [H].
(231)
readily seen that
1Pt Pn.et at of.)) o;) (Viit1 vieet)
n
No (st (4.
N (
|| + +|I V Vitti
n=
< 2e
(232)
58

---

Published as a conference paper at ICLR 2024
where the last inequality follows from Σn=y; af. Ng (of (f.66
S log and X S (cf. (212).. Conse-
quently, by taking a = 1/(SBBT) we can deduce that
K
N
N (Pr - Phist at - Vh+t)
Σ
A=1 k= (
K
N
(P* - P (V - Vi++1)
n
N
N (Ph Phott Mb (V Vx41)
Σ
n
hml N
H K NK- (SR
2A
Σ
(Ph P Phist at (V - Vitt) + HHKalog?
1= k=
SABT da
HSSAB Σ
P Phitt
h+1 Vi+t) (log* T) log
SABT
+ SABlog 8a
Hog
SABT
SABT
H2SAB
Σ>
Σ
Pa Pa
(Vi+1
Vitt) (log* T) log SH log²
8
k=1
(233)
where the last line holds due the condition (231 and our choice a. To summarize, with probability exceeding 5/6, the property (233) holds simultaneously for all (vh+1 E R | < H} obeying 227
Step 4: controlling the original term of interest. ready to control the original term of interest
With the above union bound in hand, we are
H K
N
ΣΣ
Σ
(Ph P Phottattet)
R.K Vh+1).
(234)
To begin with, it can be easily verified using 26 that
R. h+1
B.K
H
for all 1 1 < H.
(235)
4+1
Moreover, we make the observation that
K
R.K
Vitt))
(
H
K
Pr.eg (V -Vit1)
(ii)
SABT
HOSABK log
H HK
(236)
with probability exceeding 1- 8/6, where (i) holds because V VR is monotonically non-increasing (in view of the monotonicity of Vs(s) in (23 and the update rule in line 17 of Algorithm 3 and (ii)
59

---

Published as a conference paper at ICLR 2024
follows from 219 Substitution into 233 yields
N
(PR
Phoog u/ h+1
(VR. R.K
Vi+ta)
Krmm
H2SAB Σ
H K
E
(v VVita) (log" T) log
SABT
+ SAB log
SABT
8
5
h=1 1m1
SABT
SABT
HSSAB
H log
+ H HK) (log" T) log
5
8
SABT
+ SABBBloG log 5
According to the fact that
HSSABK log SABT
SABT 5
SABT
HASAB log
VHK S SAB log
+ HK,
8
we have
ak. Σ
X
(Ph af (VR+4 V(+1)
n
N=NN (o)
SABT
SABT 8
SABT
$ H2SAB H'SAB log
H3SAB + HK
log
+
SAB log²
5
8
SABT
H log SABT
I H3 log
(237)
5
F MULTIPLAYER GENERAL-SUM MARKOV GAMES
In this section, extend ME-Nash-QU to the setting of multiplayer general-sum Markov games and present the corresponding theoretical guarantees.
F.1 PROBLEM FORMULATION
general-sum Markov game (general-suy sum MG) tuple M(S. [A H, (Ph)-=1 (ry He) with m players, where denotes the state space and H is the horizon length. We have m different action spaces, where A, is the action space for the th player and [A| = A,. We let A . . denote the joint action space, and let a (aI.... am) E A denote the (tuple of) joint actions by all m players. { (IgHH] is a collection of transition matrices, so that (a a) gives the distribution of the next state actions a are taken at state step h, and r; = frr, heem is a collection of reward functions for the 7th player, so that (s, a) gives the reward received by the 7th player actions are taken at state at step h.
The policy of the tth player is denoted as n. := {mA. + A., A he(m)] We denote the product
policy of all players as π := कi x... X Tas and denote the policy of all players except the 7th player as π- We define VT, (s) the expected cumulative reward that will be received by the 7t player if starting at state at step h and all players follow policy т. For any strategy -- there also exists a best
response of the ,th player, which a policy yr (m satisfying Vu (r. +). =).m *(x) = supx, V (s)
for any (s, S [H]. For convenience, we denote vit.=-+ == v/al ( The f-fuctiions of the best response be defined similarly.
In general, there are three versions of equilibrium for general-sum MGs: Nash equilibrium (NE), correlated equilibrium (CE), and coarse correlated equilibrium (CCE), all being standard solution
60

---

Published as a conference paper at ICLR 2024
notions in games (Nisan et al. 2007). These three notions coincide in two-player zemo-sum games, but are not equivalent to each other in multi-player general-sum games; any one them could be desired depending the application hand. In this section, we first consider CCE and then extend to NE and CE the final of Section F2
The CCE is relaxed version of Nash equilibrium in which consider general correlated policies instead of product policies.
Definition 4 (CCE in general-sum MGs) (correlated) policy {ma(s) AA (h, [H] x S} is CCE if [mX]e[m] Vhs (s) S (s) all (s, h) [H].
V
Compared with a Nash equilibrium, a CCE is not necessarily a product policy, that is, we may not have (s) E AA, x x... Am.. Similarly, we also define e-approximate CCE and CCE-regret as below.
Definition 5 (e-approximate CCE in general-sum MGs) A policy π := (s)(s) E EA:: (4, [H] x S} is an c-approximate CCE if 1 K Ek=1 max4e[m] (V1, (st. Sc.
Algorithm 4: Multi-player Memory-Efficient Nash Q-Learning (Multi-MB-Nash-QUL
Parameter: some universal constant c > 0 and probability of failure E (0, 1)
Initialize: (s a), Qui (s, a), o (n, a), + H: (s, a). Q (s, a), Q (s, a) 0; (3, a), (s,
N, (s)(s), V (s)+ H: (s. 00
1.r b, (s, a), (s, a). oh (s, a), (3. (s. [,..
e (s. a), B (s.
BR (s, a) - 0; and ur, True for all (s, a E Ax [M].
for Episode
I...., .,. K do Set initial state 81 st. for Step h h= 1,,,... H do
Take action a₁ Tn (-(ss)) and draw sh+1 Phl. I Sh. an).
(s, az) + N,, (3), ax)
+ +; n + (N an): Th + #+1 m do (8h, an) f- update-q ()
H4n'
for player i = 1,2,
QUCB QLCB
(sh; an) f update-ur ().
10
2h, (sh, an) update-Ir() ().
4 (sh; an) + min ( an), Qu (sh, ), (sn an)).
② (Sh, ah) max {2 (sh, ax): QLCB (sh. an), 2n, (sh, an)}.
if (s, an) min (Q,, an), QUCB (sh, an)) and
2,, (5h, ax) = max (Q), (sk, an), QLCB (sh, an)) then
(n(-15)) f CCE(Q,,, (sh, :), ... 10 1 ()...)). Vn,((on) f- min Qn (sn). (o,()))); (sh) f max(((D,, Qn (sn), (sn))
15
16
17
18
(sh) (s)) > then (st) V (sn): (R)(sh) (sn)
20
else if (sh) True then
(sn) + (s,(( ( < (n.(sa); (r,((n) = False.
Output: H
61

---

Published as a conference paper at ICLR 2024
Definition 6 (CCE-regred in general-sum MGs) Let policy x" denote the (correlated) policy de- ployed by the algorithm in the kth episode. After a total of K episodes, the regret is defined as
K
Regret (K) =
Σ
max mm(m)
(vti**
Vi. (01)
(238)
In addition, for general-sum MGs. we have {NE} C {CE} C {CCE), so that they form nested set of notions equilibria (Nisan et 2007). Finally, since Nash equilibrium always exists, so CE
and CCE equilibrium always exist.
Algorithm 5: Auxiliary functions of Multi-ME-Nash-QL.
Function update-st a QUBB (8h: an) 6
Q QLCB)
(5%, an), [VA+LA Kati,d (sn+1)):
(1-1)) Que (sh, an) +Mmn (rh, (sh, an) Votia (8h+1) / 113 113 $11.", A.T
Q (5ho a,, +
(1 - nn) QLB (sh; ax) +Mpn
This (sh, an) + VVnii (8h+1) 1 173 HH3log
8 $11." A,T
Function update-ur
If
Phiti B Tnd (sh, as): (s))
[ h411. V
Votii (ou+1))
=R]
Onu (sh: (s):)))) Dn,i
[ Ohhir Whii -a Phiis Whiir Biid (sh, (n..aa))(( an). V htt1 Vatia (onti)):
update-q- bonus
The (sh, (sh,an) and + (1 - mm) This (sh. an) + The The (sh, an) + VntLA ($1+1) Veti, (sh+1) + Th,s (sh, an) + bn.))
VR
Function
update- 1x ((on Lh. (sh: (4hh:a))::)))))))))))))))) an), RR
hos wer
da
BR
(sh, ax), ( [VR Katiad (sh+1)): Snn
hor h
h,r
updato-q-bonun
Li. Ui. BR.d) (sh, an), [ Vanial (8h-1)):
QR, (sh, an) + (1 (m) Qli (sn, an) +
Vn The (Sh, and + Entii (8h+1) Vhtta (8h+1) + Lh. (sh, and - -Lhis)
10 Function
update-q-bonus q----u-buuus
d h, Whe 2i wh BR. Th.s (sh, an) (1 1) Sh.s (sh, an) + n V (sh+z);
(Nh, an),
12 Vnttes (onti)):
11
1h, (sh, an) -- (1 1) wh. (Sh, an)
VR
4t1, (8h+1))
12
Th. (sh; an) f- (1 - -m)) th.s (Sh, an) 7p (V+ (88+1) - Vi 1. (8b+1))
13
vhf (sh, (n))
mm) vif (shs an)
+ Th VV+1. (88+1) V. (sh+1)
log² $11 A:T
Vh.s (Sh, an) - (8h, (Sh, an) 2 +
temp (s), an) f- cb
15
Co loga 8 $11m" 1,
/H V V/... (sh, an)
(ff, (sh, an))
Phh (Sh, an)) +- Bremp (sh: an) - BR, (5h. a;))
h, (3h, a%) &- Dremp (5h, ax);
17
PR (sn.a)))
H² log" [1 A,T
BR BR (sh, an) mm)
Cb
On
62

---

Published as a conference paper at ICLR 2024
F.2 MULLI--E-NNAH-OAO
Here we present the Multi-ME-Nash-QL algorithm in Algorithm 4 which is an extension of Algo- for multi-player general-sum Markov games.
Remarkably, the CCE operation line 15 Algorithm M could be replaced by NE or CE operation which finds the NE or CE for one-step games. When using NE operation, the worst-case computational complexity will be PPAD-hard. When using CE or CCE, it can be solved in polynomial time using linear programming. However, the policies found are not guaranteed to be a product policy. We remark that in Algorithm [ee we used the CCE subroutine for finding Nash in two-player zero-sum games, which seemingly contrasts the principle of using the NE subroutine for finding the Nash equilibrium, but nevertheless works as the Nash equilibrium and CCE are equivalent in zero-sum games.
F.3 ANALYSIS OF MULTI-ME-NASH- QL
Similar to Lemma in Appendix A.3.1 we can obtain the In this section, we prove Theorem 3
properties the Q-estimate and V-estimate, as asserted by the following lemma.
Lemma 10 Consider any d E (0, 1). Suppose that cb > O is some sufficiently large constant. Then with probability at least -
R.k (s, a) 2 Qh (s. a) 2 1 a), Vh, 2 v (s), The
*
(239)
(s, a) < a* h.
(s. a) s (s)
(x) s (s)
(240)
hold simultaneously for all (s, a, hi) E Ax [M].
Step 1: regret decomposition. Firstly, we can apply Lemma 10 to reformulate (238)
Regret(K) = Σ
max
(ptor=
VI (x1) S
max (vi, ki.)) (01)
(241)
1==1
According to lines 13-14 in Algorithm
we obtain
R.k (s, a) 2 Qn, (s. a),
2n (s, a) s (s, QLCB (s, (s, a) < 0² as.
(242)
UCB. (s. a) 2 (s,
(243)
Based on this relation, we notice the following propagation by lines 18-21 in Algorithm 4 and update rules in Algorithm with cb ULCR cov A H log $ I A.T.
(Q - - (v, a) < (Q - O..BBA)) (s.a),
(QUCRR I.TP.)) (s, =(1 =[1 (Q
I.B..)) his
(s, a)
(244)
+1 ((V h411, - vk V (sk + 2c 2LLLB)
(Th., vhh)) (s) (s)= Den (oh.. -Q%.)) ) (s).
We can define (s), (s), @h(s,a) a). @h(s, a), ( a) and 2) recursively by
Vrk (s) 0 and (8) 0, and there is
@ @%) (s,a)= = (Qu QUCBA GIC.B.)) (s, a),
(QU (2C.BBB (s, = =[1- (1mmm) mn) @ (LCBB.) (s, a)
(245)
+ 1m ((1t) h++ - vx++1) (sh+t) 1) + 20 (LCBB
(v/* v/h) (s) = Drn (2% - (1t) (8).
63

---

Published as a conference paper at ICLR 2024
Similarly, we also have the following definitions.
h
(s, a) =
1
h
2r (s, a) +
1 R.R.k (s),
n
1 R. (s),
(s, a)
1 n
4
ge.k (s, a)
+
n
knl ()
1
-
-
1
4 (8, a)
+
1
R. (s)
n
1 kr +1 (s
1
(s, a)
1
R.Rkk (s)
30 3a. (s. (1 mm. hh (s.a) + 1m
ka.k
A+1 (5)
1 (8)
0 Ja.k+1 11 (s. a) (1 mn ) 4h (8,a) + T/
a
(Vi+1 (6)
V (8)
2a k2, (s, = (1 mm Ba.k (s, a) + Tm (v/++ h+1 (s) 1 (s)
1/ Ja (s, = (1 - mm0) vi (s, a) + 7m
[h+ (s)
V.R (8)
log $11. A,T
B kt (s,a) co/
x
n
(Vegstn (s, - (3h (s,a)) 2
+ Van Whatt (s) - -(ottt)) (s,a)) 2)
+
VH
2a.--1 (5, - (s)))t))))))
2 +
*1 1/h
Ja.+1 (8, - (#x (s,
Ph
RR,+1
as
B Btemp,k+] (s.a)
Blikk (s)
Bi RR,
(s, B3 plemp.tt1 (8)
RR,
a)
22 log?
SI1 A,T
b
RR,++1
=By BR. (s.a) + (1 mm0)
Ph
-2cb
8
17
123/4
@R (s, a) = =(1 -11-mm) Qh. (s, a)
mn)
+ Tm
(b) [R,k+1 + (vit - Vitt1) (s) - (VRRA
v (8) +
2h - (s.a)):
(246)
where f. and V. are associated with (s) and (s)(s and updated similar to lines 18-21 in Algorithm Then we can prove inductively that for any k. h, and a,
T h1i (s) S (/)(s)) (s).
(247)
Therefore, we only need to bound Σ -=
(V/(()) - (s)ss that is,
K
K
(Tr 1,1 vt.) (st) =
Regret (K) <
max
-
(248)
k=1
1=1
To continue, we intend to examine the following decomposition:
(v/- V/tt (s%) across all time steps S h S H, which admits
(* V/ < E Ba (0) 2% a) Qh ( -hh at) + c
s t (sh ali) + shi
R.
(249)
where
ct ; E Banat @Qh (s a) - -Q²t - Q8)((%)aa))
(250)
64

---

Published as a conference paper at ICLR 2024
Summing (248) and 249 over 1 S k I K, reach at
K
Regret S
R (s
a + Σ St.
(251)
k=1
Step 2: managing regret by recursion. The regret can be further manipulated by leveraging the update rule of Qhath and 2h.a. which is similar to that of Qhi and Q This leads to key decomposition as summarized as follows. The proof of Lemma is similar to that of Lemma and is omitted here.
Lemma 11 Fix 8 E (0, 1). Suppose that ab > O is a sufficiently large constant. Then with probability least 8, one has
K (x
(x+) S H1 + H2 + H3.
(252)
where
H
h-1
m
SII
A,T
K
H1
Σ h=1
1 1
2HS II
A + 160b (S II
A 3/4 122 log
Σ
5h
H
6
1=1
k=1
(253a)
H
h-1 K
H2
1+ H
Σ k=1
B (sh ahi)
(253b)
h=1
H
K
H33 =
Pk
Ph.st,aa)
h+1
h= k=
(
B. Pring Puikgaa .a, h+1
Et=1
h+1
No (st a4i.)
Σ 1=1
RR
(shit))
R.R.K Phist ag h+1
h+1
(253c)
No (s% a²
1=1
with
No (( Σ NN (ck TNN (el
\/ 1 H
(254)
Step 3: controlling the terms in Step 2 separately. Each of the terms in Step 2 can be well controlled. To derive the above bounds, the main strategy is apply the Bernstein-type concentration inequalities carefully, and to upper bound the sum variance. We provide the bounds for these terms Lemma 12 The proof is similar to that of Lemma aanda6aand is omitted here.
Lemma 12 With any 5 (0, 1). the following upper bounds hold with probability at least 1 5:
S A,T
SII m
A,T
H11 <
S II
A,
H S II
A log
(255)
8
8
1=1
1=1
SII
A,T
A,T
H2. S
H2S II
A,T log
H
A log
i==1
(256)
8
8
1=1
1=1
S SI
A&T
S II A,T
H43 S
H2S II
A,T log
HOS II
A, log
(257)
8
8
1=1
1=1
65

---

Published as a conference paper at ICLR 2024
Step 4: putting all this together. We now establish our main result. Taking the bounds in Step together with Step 2, we see that with probability at least and constant Co > 0, one has
Regret(K) K) - H1 + H2 + Hss
mN sII A + H II A, log" s
I Co
H2S II
A,Tlog' $
$ A (258)
Theorem is proved under sample complexity with E average regret (i.c., 1 Notably, the sample complexity is proportional to [ A,, which increases exponentially as the number of players increases.
K Regret(K) S E).
66


Reviews:
[{"review_id": "5vLCXCTyJC", "reviewer": "Reviewer_Pgbr", "summary": "This paper proposes a model-free algorithm for learning Nash policy in Two-player Zero-sum Markov Game. The authors prove that this algorithm enjoy many benign properties, including outputting Markov policy, low computational/sample/space complexity in certain regime and low burn-in cost.", "questions": "1. There are many elements mentioned in the paper, such as complexity, burn-in cost, Nash policy, Markov policy etc. While I understand that no prior algorithm surpassing this algorithm in every aspect, I wonder what do the authors think is the most important aspect/what is the main focus?\n2. Can the authors explain what is the most salient algorithmic novelty to the newly proposed algorithm?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The proposed algorithm enjoys several benign properties, as mentioned in the summary. In particular, the algorithm perform well when the horizon is very long while retaining other nice properties such as Markov output policy and low burn-in cost.", "weaknesses": "1. The proposed algorithm does not break the curse of multi-agent. Although the authors argue that there are many scenarios where horizon length is very long, I still feel that this is not general enough. I personally would still be more interested in algorithms that have $O(A+B)$ dependence in complexity.\n2. The algorithmic novelty is a bit unclear to me.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9Oiq9kvNwl", "reviewer": "Reviewer_3yJL", "summary": "This paper introduces a model-free algorithm for two-player zero-sum Markov game, which enjoys low sample complexity and computational/space complexity. The resulting algorithm has optimal dependency on S and H but sub-optimal dependence on the number of actions. The algorithm design features the early-settlement method and the reference-advantage decomposition technique.", "questions": "+ Regarding my point in weakness section, is there any other technical contributions besides reference-advantage decomposition and early-settlement design?\n\n+ Is it possible to obtain similar result for learning CCE in multi-agent general-sum Markov games?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ The paper is well written and easy to follow. \n+ The proposed algorithm outperforms existing algorithms in terms of space complexity and computational complexity.", "weaknesses": "- My main concern is the technical novelty. The reference-advantage decomposition technique has already been incorporated in two-player zero-sum Markov game by Feng el al (2023) (not cited by this work), which achieves a regret in \\tilde{O}(\\sqrt{H^2SABT}) and matches with the regret bound in this work. The main novelty of the algorithm design thus lies in the early-settlement design in order to reduce the burn-in cost, which is not new in the literature.\n\nFeng, S., Yin, M., Wang, Y. X., Yang, J., & Liang, Y. (2023). Model-Free Algorithm with Improved Sample Efficiency for Zero-Sum Markov Games. arXiv preprint arXiv:2308.08858.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kaULO911yx", "reviewer": "Reviewer_M7D7", "summary": "This paper studies two-player zero-sum Markov games (TZMG). It proposes the model-free algorithm Memory-Efficient Nash Q-Learning (ME-Nash-QL), which achieves state-of-the-art space and computational complexity, nearly optimal sample complexity, and the best burn-in cost compared to previous results with the same sample complexity. Moreover, the proposed algorithm generates a single Markov and Nash policy rather than a nested mixture of Markov policies, by computing a relaxation of the Nash equilibrium instead, i.e. Coarse Correlated Equilibrium (CCE).", "questions": "- How is $\\operatorname{CCE}(\\bar{Q}, Q)$ compuated? I was anticipating a detailed introduction to its calculation to ensure the paper's comprehensiveness. An explicit explanation would greatly contribute to the paper's self-containment.\n- Is the achievement of the space complexity independent of $T$ attributed to the fact that the output policy is a single Markov policy? In this context, do the authors consider the CCE as an essential relaxation for realizing such space complexity?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "# Originality\n- The related works are covered in detail.\n# Quality\n- The theoretical proofs seem to be rigorous. \n# Clarity\n- This paper is in general well-written and easy to follow. The design idea of the algorithm is clearly explained.\n# Significance\n- The theoretical results of this work are strong. It achieves state-of-the-art space and computational complexity, nearly optimal sample complexity, and the best burn-in cost compared to previous results with the same sample complexity.\n- TZMG is foundational and critically significant for MARL. This research has the potential to establish a new benchmark, providing a foundation for further studies in the related literature.", "weaknesses": "- Although the proposed algorithm is compared to Nash-VI (Liu et al., July 2021) and V-learning (Jin et al., 2022) in detail, the design idea of the proposed algorithm seems to share certain similarities with those from the two works. For example, they all compute a CCE policy and take the marginal policies; the choice of learning rate $\\frac{H+1}{H+N}$, the form of bonus terms, and the update of lower and upper bounds for Q-functions are similar. The originality of this paper could be significantly enhanced if the authors could discuss thoroughly the fundamental distinctions between the ideas of the proposed algorithm and the aforementioned Nash-VI and V-learning.\n- The theoretical findings are limited to the TZMG and CCE setting, which somewhat diminishes the overall contribution of this paper.\n- The auxiliary functions in Algorithm 2 are too nested, making it hard to read.\n### Minor:\n- There seems to be a blank section A.3.1 on page 14.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Eoakc2sjo4", "reviewer": "Reviewer_nN5J", "summary": "This paper studies provably efficient reinforcement learning in two-player zero-sum Markov games, an important special case of multi-agent RL. This paper improves existing results in the following directions: sample complexity, memory efficiency, Markov output policy, and burn-in cost.", "questions": "1.\tCould you please point me to the proofs of Theorem 3? Also what is the algorithm for this theorem (as I assume that Algorithm 1 only applies to two-player zero-sum games)? I do not think the extension from zero-sum to multi-player general-sum is straightforward and would hope to see a more detailed discussion.\n\n2.\tSince you now also consider multi-player general-sum games, it is probably helpful to include related works for learning in general-sum games, especially those using Nash V-learning (to name a few):\n\na. Song, Ziang, Song Mei, and Yu Bai. \"When can we learn general-sum Markov games with a large number of players sample-efficiently?.\" arXiv preprint arXiv:2110.04184 (2021).\n\nb. Mao, Weichao, and Tamer Başar. \"Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Games.\" arXiv preprint arXiv:2110.05682 (2021).\n\nc. Daskalakis, Constantinos, Noah Golowich, and Kaiqing Zhang. \"The complexity of markov equilibrium in stochastic games.\" The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.\n\n3.\tFrom what I understsand, the new major results compared to the NeurIPS submission are Theorems 2 and 3. Could you please let me know if there are any other new results that I am missing?\n\n4.\tIn your future work, you mentioned the possibility of achieving A+B sample complexity instead of AB. Does the Nash V-Learning algorithm help with this?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper studies an important topic in MARL theory. The proposed algorithm simultaneously achieved state-of-the-art results in all the aspects it considers: It matches the best sample complexity bounds, reduces the burn-in cost, and improves the space complexity while still outputting a Markov policy. The theoretical analysis looks solid.", "weaknesses": "I reviewed this paper at NeurIPS 2023. My concern was about the technical novelty of the paper because the proposed algorithm follows the mature framework of Nash Q-learning. The improved sample complexity is achieved by also following an existing reference-advantage decomposition technique. \n\nIn terms of the bounds, the biggest improvements that this paper makes over existing works are regarding the space complexity and burn-in cost. In my opinion, these are less important metrics compared to sample complexity or time complexity, yet this work has to optimize these metrics at the cost of a much more complicated algorithm and proof procedure. \nWhile I still hold most of my previous opinions, I appreciate the authors’ effort in improving their work and would like to increase my score compared to my NeurIPS evaluation. \n\nCompared to the NeurIPS submission, the new major results are Theorems 2 and 3. I found that the extension to multi-player general-sum games (Theorem 3) particularly interesting, but I was not able to find any algorithm or proof for this theorem. What is the learning target for general-sum games, Nash or correlated equilibria?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)