Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game
Authors: Wei Xiong
Han Zhong
Chengshuai Shi
Cong Shen
Liwei Wang
Tong Zhang
Venue: ICLR 2023 poster (2023)
Keywords: RL theory

Abstract: Offline reinforcement learning (RL) aims at learning an optimal strategy using a pre-collected dataset without further interactions with the environment. While various algorithms have been proposed for offline RL in the previous literature, the minimax optimality has only been (nearly) established for tabular Markov decision processes (MDPs). In this paper, we focus on offline RL with linear function approximation and propose a new pessimism-based algorithm for offline linear MDP. At the core of our algorithm is the uncertainty decomposition via a reference function, which is new in the literature of offline RL under linear function approximation. Theoretical analysis demonstrates that our algorithm can match the performance lower bound up to logarithmic factors. We also extend our techniques to the two-player zero-sum Markov games (MGs), and establish a new performance lower bound for MGs, which tightens the existing result, and verifies the nearly minimax optimality of the proposed algorithm. To the best of our knowledge, these are the first computationally efficient and nearly minimax optimal algorithms for offline single-agent MDPs and MGs with linear function approximation.

Published as a conference paper at ICLR 2023
NEARLY MINIMAX OPTIMAL OFFLINE REINFORCE- MENT LEARNING WITH LINEAR FUNCTION APPROXI- MATION: SINGLE-AGENT MDP AND MARKOV GAME
Wei Xiong", Han Zhong"?, Chengshuai Shi', Cong Shen", Liwei Wang4.5, 4.5, Tong Zhang Department of Mathematics, The Hong Kong University of Science and Technology Center for Data Science, Peking University? Department of Electrical and Computer Engineering, University of Virginia* National Key Laboratory of General Artificial Intelligence, Peking University4 School of Intelligence Science and Technology, Peking University"
Department of Computer Science and Engineering, The Hong Kong University of Science and Technology 6 (wxiongae, tongzhang {cs y cong) @v1 rging n a edu; wangl we c s. pku edu.cn
} @ust hk; hanzhong pku. edu. en;
ABSTRACT
Offline reinforcement learning (RL) aims at learning an optimal strategy using a pre-collected dataset without further interactions with the environment. While various algorithms have been proposed for offline RL in the previous literature, the minimax optimality has only been (nearly) established for tabular Markov decision processes (MDPs). In this paper, we focus on offline RL with linear function approximation and propose a new pessimism-basee linear MDP. At the core of our algorithm is the uncertainty decomposition via a reference function, which is new in the literature of offline RL under linear function approximation. Theoretical analysis demonstrates that our algorithm performance lower bound up to logarithmic factors. We also extend our techniques to the two- two-player zero-sum Markov games (MGs), and establish new performance lower bound for MGs, which tightens the existing result, and verifies the nearly minimax optimality of the proposed algorithm. To the best of our knowledge, these are the first computationally efficient and nearly minimax optimal algorithms for offline single-agent MDPs and MGs with linear function approximation.
algorithm for offline
match the
INTRODUCTION
Reinforcement learning (RL) has achieved tremendous empirical success in both single-agent (Kober et al., 2013) and multi-agent scenarios (Silver et al., 201 6; 2017). Two components play critical role function approximations and efficient simulators. For RL problems with a large (or even infinite) number of states, storing a table as in classical Q-learning generally infeasible. In these cases, practical algorithms (Mnih et al., 2015; Lillicrap al., 2015; Schulman et al., 2015; 2017; Haarnoja et al., 2018) approximate the true value function or policy by a function class (c.g., neural networks). Meanwhile, efficient simulator allows for learning a policy in online trial-and-error fashion using millions or even billions of trajectories. However, due to the limited availability of data samples in many practical applications, e.g., healthcare (Wang et al., 2018) and autonomous driving (Pan et al., 2017), instead of collecting new trajectories, we may have to extrapolate knowledge only from past experiences, i.e., pre-collected dataset. This type of RL problems is usually referred as offline RL or batch RL (Lange et al., 2012; Levine et al., 2020).
An offline RL algorithm usually measured by its sample complexity to achieve the desired statistical accuracy. A line of works (Xie et al., 202 Shi et al., 2022; Li et al., 2022) demonstrates that near- optimal sample complexity in tabular single-agent MDPs is attainable. However, these algorithms cannot solve the problem with large or infinite state spaces where function approximation is involved. To our best knowledge, existing algorithms cannot attain the statistical limit even for linear function
"The first authors contribute equally.

---

Published as a conference paper at ICLR 2023
approximation, which is arguably the simplest function approximation setting. Specifically, for linear function approximation, Jin et al. (2021c) proposes the first efficient algorithm for offline linear MDPs, but their upper bound is suboptimal compared with the existing lower bounds in Jin et al. (2021c); Zanette et al. (2021). Recently, Yin et al. (2022) tries to improve the result by incorporating variance information in the algorithmic design of offline MDPs with linear function approximation. However, a careful examination reveals a technical gap, and some additional assumptions may be needed to fix it (ef. Section 3 and Section 5). Beyond the single-agent MDPs, Zhong et al. (2022) studies the Markov games (MGs) with linear function approximation and provides the only provably efficient algorithm with suboptimal result. Therefore, the following problem remains open:
Can we design computationally efficient offline RL algorithms for problems with linear function approximation that are nearly minimax optimal?
In this paper, we first answer this question affirmatively under linear MDPs (Jin et al., 2020) and then extend our results to the two-player zero-sum Markov games (MGs) (Xie et al., 2020). Our contributions are summarized as follows:
We identify an implicit and restrictive assumption required by existing approaches in the literature, which originates from omitting the complicated temporal dependency between different time steps. See Section 3 for a detailed explanation.
We handle the temporal dependency by an uncertainty decomposition technique via reference function, thus closing the gap to the information-theoret lower bound without the restrictive independence assumption. The uncertainty decomposition serves to avoid a y'd-amplification of the value function error and also the measurability issue from incorporating variance information to improve the /l-dependence, where d and H are the feature dimension and planning horizon, respectively. To the best of our knowledge, this technique new in the literature of offline learning under linear function approximation.
We further generalize the developed techniques to two-player zero-sum linear MGs (Xie al.. 2020), thus demonstrating the broad adaptability of our methods. Meanwhile, we establish new performance lower bound for MGs, which tightens the existing results, and verifies the nearly minimax optimality of the proposed algorithm.
1.1 RELATED WORK
Due to space limit, we defer comprehensive review of related work to Appendix A.2 but focus on the works that are most related to the problem setup and our algorithmic designs.
Offline RL with Linear Function Approximation. Jin et al. (2021c) and Zhong et al. (2022) provide the first results for offline linear MDPs and two-player zero-sum linear MGs, respectively. However, their algorithms are based on Least-Squares Value Iteration (LSVI), and establish pessimism by adding bonuses at every time step thus suffering from /ddamplification to the lower bound (Zanette et al., 2021; Zhong et al., 2022). The amplification results from the statistical dependency between different time steps. After these, Min et al. (2021) studies the offline policy evaluation (OPE) in linear MDP with an additional independence assumption that the data samples between different time steps independent thus circumventing this core issue. Yin et al. (2022) studies the policy optimization in linear MDP, which also (implicitly) require the independence assumption. Another line of work addresses the error amplification from temporal dependency with different algorithmic designs. Zanette et al. (2020) designs an actor-critic-basc algorithm and establishes pessimism via direct perturbations of the parameter vectors in linear function approximation scheme. Xie et al. (2021a); Uchara and Sun (2021) establish pessimism only at the initial state but at the expense of computational tractability. These algorithmic ideas are fundamentally different from ours and do not apply to the LSVI-type algorithms. We will compare the proposed algorithms with them in Section 5.
2 OFFLINE LINEAR MARKOV DECISION PROCESS
Notations.
Given semi-definite matrix A and vector u, denote Vu Au as [|u]], The 2- norm of a vector w is ||//|2- We also denote (A) as the smallest eigenvalue of the matrix A. The subscript of [x) means that clip the value f(x:) to the range of [0, MJ, i.e.,
2

---

Published as a conference paper at ICLR 2023
M. mix, f()))) (())) Given set X, define the set of probability measure on it by Ax- We will use the shorthand notations Φn = ((T,, (s), 07 0(277 (,)), Th = ra ( ax), and r = [r a)) (formally defined the next subsection). With a slight abuse of notations, we also use similar notations (e.g. 6n o( ah. by) )) for MGs, which shall be clear from the context.
Y X X means Y < CX for some constant C' > 0. To improve readability, we also provide a summary of notations in Appendix A.
Markov Decision Process. We consider an episodic MDP, denoted as M(S. A. H, r), where S and A are the state space and action space, H is the episode length, IP = (Px k=] and r {rx are the state transition kernels and reward functions, respectively. For each h E [H] PA. (- pr. a) is
the distribution of the next state given the state-action pair (I, a) step h, rh (3, a) E [0, 1] is the deterministic reward given the state-action pair (z, a) at step h.
Policy and Value function. A policy π = { is a collection of mappings from a state E S to distribution of action space (-(x)x) E AA. For any policy we define the Q-value function Q7, (ax a) EE The (ww, (2 an) = (z) and the V-value function [g[(() (z) E, 1 h Th (ahi, ax) 2 x]. where an The (-Iaw) and #6441 ~
For any
function V: S + IR, we denote the conditional mean as (I,, a) := Eves Pn z a) V<r')
and conditional variance as [Var, (1, a) == (r, a) (( (a,, a))?. The Bellman operator is defined as (T)V) a) == ra(2, a) + (z,
We consider the MDPs whose rewards and transitions possess linear structure (Jin et al., 2020).
Definition 1 (Linear MDP). MD A, H,P,r) is linear MDP with (known) feature map Φb ::S x A - TRd, for any h E [H). there exist d unknown signed measures phn = (14 : :.. 1 (2) over S and an unknown vector On E Rd_ such that for any (I, a) E S x A. we have P. I, a) = (Ø(z, a), un (-)) rh (x, a) (Ø(x, , a), On). With loss of generality, we assume that [|ob(r, a) S 1 for
all (x, a) E S x A, and max (1) [10x1]] S for all h E [H].
For linear MDP, we have the following result, whose proof can be found in Jin al. (2020). Lemma 1. For any Sunction V S - [0, Vmaa - 1] and h E [H], there exist vectors Ba, Wh E TRd with [|Bx < [|wll S VdV maxo such that V(z, a) E S x such that the conditional expectation and Bellman equation are both linear in the feature:
(FAV) a) = 6xx, a) Bn, and (TaV) =((r), a) wn-
Offline RL. In offline RL, the algorithm needs learn near-optimal policy or to approximate Nash Equilibrium (NE) from a pre-collected dataset without further interacting with the environment. We suppose that we have access to a batch dataset D {a% 47,, r/f h E [H) T E [K]]. where each trajectory is independently sampled by a behavior policy μ.. The induced distribution of the state- action pair at step h is denoted as dh. We make the following standard dataset coverage assumption for offline RL with linear function approximation (Wang et al., 2020; Duan et al., 2020):
Assumption 1. We assume min Amiin (Ba,, [0(a,, ())(z, T)) 0 for MDPs.
This assumption requires the behavior policy to explore the state-action space well and is not information--heoortie as Jin et al. (2021c) does not necessarily require it. However, we make this assumption so that we employ the variance information, which seems challenging otherwise. We remark the assumption is also made by the existing works that employ the variance information for the offline RL problems with linear function approximation (Min et al., 2021; Yin al., 2022).
PRELIMINARIES AND TECHNICAL CHALLENGES
Pessimistic Value Iteration (PEVI) is proposed in the seminal work of Jin et al. (2021c), which constructs the value function estimations (L) and Q-value estimations (Qx (,, ) back- ward from h = H to h 1, with the initialization V = 0. Specifically, given 1h+1. PEVI
'The results readily generalize to the stochastic reward as the uncertainty of reward is non-dominating compared with that of state transition.
3

---

Published as a conference paper at ICLR 2023
approximates the Bellman equation by ridge regression:
Qu(I, a) V - -B110(z,)))aa;
where the linear approximation Tn 7. (1. = ((:, TTan is the solution of:
hh
arg min
Σ
P - (oñ) (dh)"w) w) 11100 ATT Σ
pT + ( (2)
wERd
TED
FED
where A₁ ETED (1) (1 ah) + Ala (2( (1 a) IlA," is bonus function such that (TT Tn (z, a)l S ( a) for all (s, E S x with high probability. Intuitively, pessimism means that we use lower confidence bound by subtracting the bonus (::)))
penalize the uncertainty so that (u a) < Th V (I, a). If pessimism is achieved for all steps E [H), then we have the following key result (formally presented in Lemma 2):
H E. (T)))))))))) x].
(()) V
x
S
(3)
h=1
Therefore, to establish a sharper suboptimality bound, it suffices to construct a smaller bonus function T that can ensure pessimism. There remains, however, a gap of ((VHH) between the suboptimality bound of PEVI and the minimax lower bound in Zanette et al. (2021).
Self-normalized Process and Uniform Concentration. Given a function fE+1, to construct the bonus function, we can bound [Tafu+1 Trafntil as follows (formally presented in Lemma 3):
(Thfats)( (Trfa+)((raa)) $
Σ & (#h, o (l((a-1) rED
llØ( o)ll
(4)
(A) B
where (f(++))):= := (n+ (Thfft+1) a.). Bounding (A. is referred to as the concentration self-normalized process the literature (Abbasi- Yadkori et al., 2011). For any fixed VA+1. Lemma ensures a high-probabillty upper bound Õ(H Vd) for (A). However, in the backward iteration, V is computed by ridge regression in later steps [/ + 1, H]] and thus inevitably depends on {2% 1 TED. which is also used to estimate the Bellman equation step Consequently, the concentration inequality cannot directly be applied since the martingale filtration in Lemma 9 is not well-defined. To resolve the above measurability issue, the standard approach is establish
uniform concentration result over an e-covering of the following function class of Vn+1:
Vx+1 == max((((;)) w + 3 [ a))l || < R, 3 E [0, B], X 10,
Then, the self-normalized process is bounded by the uniform bound the e-covering, plus some approximation error. We can tune the parameter >> 0 and obtain that ((B.20) of Jin et al. (2021c)):
Σ sah am) 57 (Vtt++ & cH2 (log (H))++(e)/0) + d dlog(1 + K) + d²) TED
S SHH
Uniform conver. Conver. lixed
Apgroximation errer
where we use an upper bound of the covering number (Lemma 11), and omit all the logarithmic terms for clear comparison. Therefore, we conclude that the uniform concentration leads an extra v'd from the logarithmic covering number log (c). The prior work Yin et (2022) omits the dependency between Vh+1 and {aī, 4j, >re. TED.. thus circumventing the uniform concentration. To fix this gap, one might make an additional assumption that the dataset is independent across different time steps h as Min et al. (2021), which is not realistic in practice because the behavior policy collects the trajectories by playing the episode starting from the initial state.
4

---

Published as a conference paper at ICLR 2023
4 RETERENCE-ADVAATTAG DECOMPOSITION UNDER LINEAR FUNCTION APPROXIMATION
In this section, introduce the reference-adven reference-advantagge decomposition under linear function approxima- tion, which serves to avoid Vd amplification of the error due to the uniform concentration.
We first define (-.g--(-->)) to be an estimator of the conditional expectation, which is obtained by setting r% = 0 in (1g We observe that the following affine properties hold:
oh(h + (n+1(1R+1))) + o(.)) "AT"" (Ta(Ja+1 + sm+1)) (4)) = =(.))) Σ
Σ
+igh (4T
TED
TED
-Tas++((s-) + Pngh+i(:s-),
(Th (fu+1 + gn+1)) = (0(0, 0n) + Jut1 (x') fn+1(x') (),, + gh+t (4++ (o(x, dp)x)z)))
= -Tifi+i(ss)) -) Proh+1(s-).
Instead of directly bounding the uncertainty as in Eqn. (4), we now make the following decomposition:
T V (x, a) To (z,
(Tn Vi+1 Vit+1) (c,, a) (Tr Vh+1 vitt1) (æ, a)
( VhV + PP (z,+)) a) PA (V (z,
Reference uncertainty & do.s (2,
Advantage uncertainty & (1,((x,
(5)
We have the following key observations about the reference part and the advantage part.
Circumventing the Uniform Concentration for Reference Function. As Vi+1 is deterministic, we can directly invoke standard concentration inequality (Lemma 3 and 9) to set (2, a) = Ö(VCH) [, a))l,,, which avoids a vdd amplification due to uniform concentration.
High-order Error from Correlated Advantage Function. Although we still need the standard uniform concentration argument to analyze the advantage function and obtain sub-optimal d- dependency, under Assumption 1, by a carefully-crafted induction procedure, we can show that [| 1lo Ō( ((/HH²) The much smaller range implies that invoke Lemma 9 to set (1, a) = Ō (2/22H² JKK
[1ő(2, (a(a,,))l,, which is non-dominating when K 2 á (dHH/K)) The detailed proof can be found in Appendix D.
VK*
Based on the above reasoning, we conclude that we can set = 110(,, A)lA, in the original PEVI algorithm (Jin et al., 2021c) and obtain algorithm referred to as LinPEVI-ADV. Together with a refined analysis, we have the following theoretical guarantee.
Theorem 1 (LinPEVI-ADV), Under the Assumptions I, and K > 52dd2 /K), if we set X = 1 and 31 = Ö(VHH) in Algorithm 2, then, with probability at least 1 5, for any E S we have
(x(x) V7()) 5 (VVaH)
Σ E [10(r,)))ls
1 ==]=
where A₁ = ETED o(z 0f (1 TT) + Ala-
We remark that LinPEVI-ADV shares the same pseudo code with PEVI, except for Vd-improvement in the choice of B. For completeness, we present the code in Algorithm 2.
Compared to Xie et (2021b). To the best of our knowledge, the diference-advantage decomposi- tion is new in the literature of offline linear MDP, but it is relatively well-studied in tabular MDPs (Azar al., 2017: Zanette and Brunskill, 2019; Zhang et al., 2020; Xie al., 2021b). Among them, Xie et al. (2021b) studies the offline tabular MDP and is most related to ours. While we share similar algorithmic ideas terms of uncertainty decomposition, we comment on our differences as follows. First, in terms of algorithmic design, Xie et al. (2021b) uses an independent dataset to explicitly construct reference Dref but only Vit in the theoretical analysis. Second, in terms of the
5

---

Published as a conference paper at ICLR 2023
Algorithm LinPEVI-ADV+
1: Initialize: Input datasets D, D', and S2; Vi++ 0.
2: Construct variance estimator 0% (17 0%) as in Section 5 with D'.
3: for h H, - do
4: En EEED 6( (7)(2 o ( + Mai
5:
T6 - ΣTED 6(2% o (1(2%105)
6: Ta(:,)) - 32 32116(',))) "<<ا""
7:
Qn(,))) t :)(:,)) Twh -a(.
8:
(.)-) + arg max (Qn(..),, (n( Vx()) - (Qn())) m. 1-)).
9: end for
10: Output: के = { 1
uncertainty estimation, Xie et al. (2021b) estimates the uncertainty separately of each state-action pair by counting its frequency. On the contrary, in the linear setting, we deal with the regression and the state-action pairs coupled with each other because the analysis of the self-normalized process involves the estimated covariance matrix thus all the samples at step / (4), This brings distinct challenges the linear setting, both terms of the analysis and the coverage condition for achieving sharp bound. Finally, the theoretical analyses are distinctly different due to the previous two points. For instance, we adopt carefully-crane craffedd induction procedure control the advantage function, while Xie et al. (2021b) further introduces some dataset splitting techniques to handle the temporal dependency in the advantage function. Moreover, for linear MDP, the way in which the variance is introduced is also different (see Section 5).
LEVERAGE THE VARIANCE INFORMATION
The variance- variance-weighted ridge regression technique was introduced by Zhou et al. (2021) in the literature of RL and was later firstly adapted by Min et (2021); Yin al. (2022) to offline RL under linear function approximation. Specifically, given a fixed function fn-1 S + [0, H as the target, we perform the following variance-weise weighted ridge regression to estimate Sn as:
[(TT] T w rT. Saz (xT+1))²
(g) (r% + fat1 (1 (0 47,)
argmin Σ WERd
+ AllwolB En
Σ
(7 ()
(6)
where Σn EtED estimator. In this case, we can bound the uncertainty by Lemma 3 as follows:
di oi Ala and ( H3) is independent variance of (.)
[Taf+t1 (n &
1 ④ (2), (z) - (f(f++))lss (1((,,))
FED
with (fhh+1))= = + 1 (Ta (1)
The high-level idea is that the normalized E (fh+1) of a conditional variance (11) and the Bernstein-type inequality (Lemma 10) gives a bound of 32 = Ö(Vd) for the nefmaizzml process instead of 31 = Õ(H from the Hoeffding- type one. Therefore, instead of depending on the planning horizon H explicitly, for B3 (10(2, a) |xx,, the
0x(2).97)
H factor is "hidden" in the covariance matrix Σ₁. Furthermore, Σ 2 H2 the new bonus function never worse because 3z (1 S B1 a) Combining this observation with (3), we conclude that the PEVI with variance- variance-weighted regression is superior as long as we can construct an independent and approximately accurate variance estimator (..)). To this end, we also carefully handle the temporal dependency due to the following two reasons: (i) we need to avoid the measurability issue as described in Section 4; and (ii) the estimation of the conditional variance of E (f++1) will be hard otherwise. To further illustrate the idea, now discuss the limitations of existing approaches when we do not omit the temporal dependency, thus motivating our corresponding modifications.
know that

---

Published as a conference paper at ICLR 2023
Limitation of the Existing Approach. Yin et al. (2022) constructs the variance estimator (, and estimate the Bellman equation both with the target function Vh+1- As discussed in Section oz is statistically dependent with the dataset D == {02 } ]= due to temporal dependency. Therefore, a)) Jr=1 are dependent so the concentration of the covariance matrix the random variables { (,,2) of
Yin al. (2022)) does not apply. Moreover, a similar measurability issue arises from the statistical dependency between the ū ()))) and DD, so the concentration of the self-normalized process also fails. Finally, the conditional variance of Vi++1 (2)1)) (1)) is hard to control because the numerator and denominator are tightly coupled with each other.
with Lemma 12 (Lemma C.3
a7)
Variance Estimator. Equipped with the reference-advantaae decomposition, it suffices to focus on the reference function Vi+1- If we can construct a (+))) that is independent of 'D, then (V +V (0% (1) (T.V. (ork)))) will be independent with each other and easy to deal (1
with. To this end, first use independent dataset D' to run Algorithm 2 and construct (V/)= (this only incurs factor of 2 in the final sample complexity). Then, by Lemma I, we know that there exist 1,,1 3p.2 E Rd such that (V (zx, a) = (ø(z, a), 3h and Vi (z, a)))² = [((r, a), 1) Similarly, we can approximate Br,, and ,2,1 via ridge regression:
3..2 = argmin Σ ag3d
(0 (1), .) - (V441) [1] A113/2.
TED!
f,,1 argmin
Σ
(0 (2%, at) - Tian (oh+1) + *1
AgEd
We then employ the following variance estimator:
d.H3
1 ( a) max { [0(z, a) Sh.21 [0,11]] (0(x, 1 [0.11
Ō
(8)
VKK
With proof essentially similar to that of PEVI, can show that with high probability (cf. Lemma 5),
dH's
IV (z) -
VKR (VRR)
S ()r,aa) S (VaVi=il(a,,a))
(x. where V 1 a) = max [Var, Vi+1l(x, a)} is the truncated variance of V (-). Therefore, (.,-)) defined in (8) approximates the conditional variance of & (V%+1) well when K exceeds threshold. Moreover, since the target function Vit is deterministic thus measurable, we know that
Viti(=Ttta) (n (g)
(i+1(#T++))
Var o ( ae a 1hi1
Vara, 1
Varay, 12g, VW (xT++1)
0(1),
2h (x%,
1:r-1 short for {(1%, af)) Sii: : Therefore, where x/ 0i , 1 the high-level idea stated at the beginning of this section is realized by the variance estimator defined by (8). Combining the variance-weighted regression with the reference-advat adaattge decomposition, we propose LinPEVI-ADV+ (Algorithm 1), which enjoys the following theoretical guarantee.
Theorem 2 (Li))EVV-ADV+), Under Assumption for K 2 (dd (o /n), if we set À 1/H² and 32 = Ö(Vd) Algorithm I, then, we have with probability least 6, for any x E S, we have
H Σ E., h=1l
- vP()) ( Ō(VV)
[Io(Z an Ilsgg- |21 =x]
where 27 = ETED (727% a /L Vi 07) + Ala-
Interpretation of the result. Since M.Vi E [1, H²), we know that Σズ ~ A This implies that LinPEVI-ADV+ is never worse than LinPEVI-ADV thus also superior to the PEVI. Such an improvement is indeed strict when it reduces to the tabular setting. Specifically, let d (z. a) denote the distribution of visitation of (xr, a) step h under the optimal policy n". LinPEVI-ADV gives
7

---

Published as a conference paper at ICLR 2023
Independence Assumption
Suboptimality Bound
Jin et al. (2021c)
X
((dH) Σ h= Ex (Ilo(x,
121 =
Yin et al. (2022)
O(va) 2h=l R ( (n)
[r]
Theorem
X
Ó(VaH) Σ h= E 11 a))
A
21
Theorem
Ó(Vd) Ex= Ex O (In, an 1xx--
[1
Table 1:
comparison with existing results. Here An ETED (17 ()), a7)T + Xaa and E -EEED 6( [2) az) sents the assumption that the data samples are independent across different time steps h. We also remark that, in the new version of Jin et al. (2021c), they adopt dataset splitting technique to split the dataset into H independent subsets. This technique essentially shares the same spirit with the assumption and is at the expense of an additional H factor in the final sample complexity.
Vi+iiiii a7)) + Ald. The independence assumption repre-
bound Ö(váH En,z, dz V)
Kdj [u.o] which has horizon dependence of H² On the other
hand, LinPEVI-ADV;, gives bound of the form Ö(v (2, a)
Kdg Kdf (x.0) 1 which
11/2),
has horizon dependence of 3/322 by law of total variance. Meanwhile, LinPEVI-ADV+ enjoys the same rate as the VAPVI (Yin et al., 2022) without an additional independence assumption on the offline dataset, as summarized in the Table
Compared to other methods. Zanette et al. (2020) and Xie et al. (2021a) also achieve a vd improvement the algorithmic ideas are fundamentally different from ours. In specific, the actor- critic-based Zanette et al. (2020) establishes pessimism via direct perturbations of the parameter vectors Xie et al. (2021a) establishes pessimism only at the initial value and is only information- theoretic. We develop techniques to resolve the issue in the LSVI framework because it possesses an appealing feature that we can assign sample-dependent weights in the regression thus obtaining sharp H -edependence. To the best of our knowledge, no similar result is available in the other two frameworks. When rescaling the range of V-value to [0, H). their bounds will be sub-optimal. Moreover, their bounds depend the cardinality of the action space, while the LSVI-based one deal with an infinite action space.
To further interpret our result, state the following lower bound for offline linear MDP.
Theorem (Lower Bound for MDP). For fixed episode length H, dimension d, probability 5, and sample size K 2 (dd)). There exists class M of linear MDPs and an offline dataset 'D with [D] = K, such that for any policy म, holds with probability at least 8 that for some universal constant e 0, we have
sup EM (T) Vi (21)) ovd Σ E [|o(nn, an)ll; MEM
The lower bound matches Theorem 2, thus establishing the optimality of LinPEVI-ADV+ for sufficiently large K. We also remark that Yin et al. (2022) establishes the lower bound cvd. Σl [Er- an) dn)sss-- which is smaller than our lower bound due to Jensen's inequality.
6 EXTENSIONS
6.1 LINEAR MDP WITH FINITE FEATURE SET
As shown in the seminal work of linear contextual bandit Chu et al. (2011), one can further improve the suboptimality bound by factor of Vd, when the action set is finite. Equipped with the technique developed above, we can obtain a similar improvement in the case of finite features.
Assumption (Finite Feature Set). We assume that H a) E Rdd S. E A}|= M ao.
"See page 17 of Zanette et al. (2020) for discussion about the error amplification issue.
8

---

Published as a conference paper at ICLR 2023
We start with bounding
(TaVi
Vht 11 which is the key to establishing the bonus function:
(2) Σ TED
a) ob) (Vi41) (4) S (o(x,)))la;;
(TrVites Ta (
Σ (olla) TED
constant
inequality. The reasoning proceeds as follows. The key observation is that since V is deterministic, (V are independent conditioned on Dr (()),,)))re TED thus the classic Hoeffding's 's inequality applies. To get a high-probabilltty bound for all features, Assumption allows us to bound the middle term directly by paying for a log(M [M) from a union bound argument, instead of vd from Lemma 9. We remark that the decomposition trick is necessary for the above reasoning. One cannot take condition on Dr otherwise because this will influence the distribution of (5% (V)+1))=ED. Combining this with (3), we have the following result.
where we prove (a) in Appendix and (b) follows from
Theorem 4 (LinPEVI-ADV with Finite Feature Set). Suppose Assumplions I and 2 hold. If K 2 H(ddH3/x)) and we set B1 = O (Vlog (o and x = 1/d in Algorithm 2, then, with probability at least - for any x E S, with A. ΣTED ( 0,)0(27, o7) + Ald. we have
H
(\))) log (/6] 1/)
Σ
Er. [1((z) | = x].
h=1
6.2 LINEAR TWO-PLAYER ZERO-SUN MARKOV GAME
In the two-player zero-sum MGs (Xie et al., 2020) where at each step, there is another player taking action simultaneously from another action space B and the reward function and transition kernel are linear in a feature map (<x, a, b) S x A x B - Rdd The learning objective is to approximate
the Nash equilibrium (NE): (T", ,D") such that V .2' (z) = max, miny (z), where the V-value function is now defined as Vi (ar) = ET,, EE The jx = x). With slight abuse of notation, we can define the Bellman operator for the two-player zero-sum MG follows:
(Tn (z, ())
Σ P, a'ES
g(2, wk.
where the linear structure of the Bellman equation (i.e. the existence of wn E Rd) follows from the linearity of reward and transition. The Pessimistic Minimax Value Iteration (PMVT) proposed in Zhong et al. (2022) also establishes pessimism at every step and we have
V Vi(x)) - min (x)
(x) 2sup Σ E La 21 = x], h=1
(10)
Gap to the Value
where Ig (z, a, b) is a bonus function such that Th M (z, a, b) V 1 (I, a, b)] $ [2, a, b) with high probability and Va+1 is the estimated NE value of the first agent at step h 1. Although the learning objective is different, the suboptimality bound essentially also reduces to the uncertainty estimation at each step, and Zhong al. (2022) suffers from exactly the same challenge from the
statistical dependency between 14 and the data samples used to construct (T V. 1+ Therefore, our techniques can be readily extended to this the MG setting and improve the result in Zhong et al. (2022). We defer the details to Appendix
7 CONCLUSION
In this paper, we study the linear MDPs in the offline setting. We identify the complicated statistical dependency between different time steps as the bottleneck of the algorithmic design and theoretical analysis. To address this issue, we develop new dnderence-advantteee decomposition technique under the linear function approximation, which serves to avoid a vdd-apliffiction of the value function error due to temporal dependency and is also critical for leveraging the variance information to achieve sharp dependence the planning horizon H. We further generalize the developed techniques to the linear MDP with finite features and also the two-player zero-sum MGs, which demonstrate the broad adaptability of methods.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
Wei Xiong and Tong Zhang acknowledge the funding supported by the GRF 16310222 GRF 16201320. Chengshuai Shi and Cong Shen acknowiedge the funding support by the US National Science Foundation under Grant Bloomberg Data Science Ph.D. Fellowship. Liwei Wang supported by National Key R&D Program of China (2022ZD01 14900) and National Science Foundation of China (NSFC62276005).
ECCS-2033671, ECCS-2143559, CNS-2002902, and the
REFERENCES
Abbasi- Abbasi-Yadkori, Y., Pál, D., and Szepesvári, C. (2011). Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24.
Antos, A., Szepesvári, C., and Munos, (2008). Learning near-optimal policies with bellman- residual minimization based fitted policy iteration and a single sample path. Machine Learning. 11(1):89-129.
Azar, M. G., Osband, I., and Munos, R. (2017). Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263-272. PMLR.
Chen, M. Li, Y., Wang, E.,, Yang, Z., Wang. Z., and Zhao, T. (2021). Pessimism meets invariance: Provably efficient offline mean-ficll multi-agent rl. Advances in Neural Information Processing Systems, 34.
Chen, Z., Zhou, D., and Gu, Q. (2022). Almost optimal algorithms for two-player zero-sum linear mixture markov games. In International Conference on Algorithmic Learning Theory, pages 227-261. PMLR.
Chu, W., Li, L., Reyzin, L., and Schapire, R. (2011). Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 208 214. JMLR Workshop and Conference Proceedings.
Cui, Q. and Du, S. S. (2022). When offline two-player zero-sum markov game solvable? arXiv preprint arXiv:2201.03522
Dann, C., Mohri, M., Zhang, T., and Zimmert, J. (2021). A provably efficient model-free posterior sampling method for episodic reinforcement learning. Advances in Neural Information Processing Systems, 34.
Du, S., Kakade, S., Lee, J., Lovett, S., Mahajan, G., Sun, W., and Wang, R. (2021). Bilinear classes: A structural framework for provable generalization in rl. In International Conference on Machine Learning, pages 1226-2836. PMLR.
Duan, Y., Jia, Z.,, and Wang, M. (2020). Minimax-optimal off-policy evaluation with linear function approximation. In International Conference on Machine Learning, pages 2701-2709. PMLR.
Foster, J., Kakade, S. M., Qian, J., and Rakhlin, A. (2021). The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.
Haarnoja, T., Zhou, A., Hartikainen, K., Tucker, G., Ha. S., Tan, Kumar, V., Zhu, H., Gupta, A., Abbeel, P. et al. (2018). Soft actor-critic algorithms and applications. arXiv preprint arXiv:1812.05900.
Hu, P., Chen, Y., and Huang, L. (2022). Nearly minimax optimal reinforcement learning with linear function approximation. arXiv.
Huang, B., Lee, J. D., Wang. 7., and Yang, Z. (2021). Towards general function approximation in zero-sum markov games. arXiv preprint arXiv:2107.14700
Jiang, N., Krishnamurthy, A., Agarwal, A., Langford, J., and Schapire, R. E. (2017). Contextual decision processes with low Bellman rank are PAC-learnable. In Proceedings of the 34th Interna- tional Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1704-1713, PMLR.
10

---

Published as a conference paper at ICLR 2023
Jin, C., Liu, Q., and Miryoosefi, S. (2021a). Bellman eluder dimension: New rich classes of rl problems, and sample-effieien algorithms. Advances in Neural Information Processing Systems, 34.
Jin, C., Liu, Q., and Yu, т. (2021b). The power of exploiter: Provable multi-agent rl in large state spaces. arXiv preprint arXiv:2106.0333
Jin, C., Yang, Z., Wang, Z., and Jordan, M. I. (2020). Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143. PMLR.
Jin, Y., Yang. Z., and Wang. Z. (2021c). Is pessimism provably efficient for offline r!? In International Conference on Machine Learning, pages 5084-5096. PMLR.
Kober, J., Bagnell, J. A., and Peters, J. (2013). Reinforcement learning in robotics: A survey, The International Journal of Robotics Research, (2(11):1238-121
Lange, S., Gabel, T., and Riedmiller, M. (2012). Batch reinforcement learning. In Reinforcement learning, pages 45-73. Springer.
Levine, S., Kumar, A., Tucker, G., and Fu, J. (2020). Offline reinforcement learning: Tutorial, review, and perspectives on open problems, arXiv preprint arXiv:2005. 20X.0:2005.01643.
Li G., Shi, L., Chen, Y., Chi, Y., and Wei, Y. (2022). Settling the sample complexity of model-based offline reinforcement learning, arXiv preprint arXiv:2204.05275.
Lillicrap. T. P., Hunt, J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., and Wierstra, D. (2015). Continuous control with deep reinforcement learning. arXiv preprini arXiv: 1509.00970
Min, Y., Wang, T., Zhou, D., and Gu, Q. (2021). Variance-aware off-policy evaluation with linear function approximation. Advances in neural information processing systems, 34.
Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., et al. (2015). Human-level control through deep reinforcement learning. nature, 518(7540):529-533
Pan, Y., Cheng, C.-A., Saigol, K., Lee, K., Yan, X., Theodorou, E., and Boots, B. (2017). Agile autonomous driving using end-to-end deep imitation learning. arXiv preprint arXiv:1709.07174.
Precup, D. (2000). Eligibility traces for off- off-policy policy evaluation. Computer Science Department Faculty Publication Series, page 80.
Rashidinejad, P., Zhu, B., Ma, C., Jiao, J., and Russell, S. (2021). Bridging offline reinforcement learning and imitation learning: tale of pessimism. arXiv preprint arXiv:2 12021..
Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P. (2015). Trust region policy optimiza- tion. In International conference machine learning, pages 1889-1897. PMLR.
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. (2017). Proximal policy
optimization algorithms. arXiv preprint arXiv: 7707066377
Shi, L., Li, G., Wei, Y., Chen, Y., and Chi, Y. (2022). Pessimistic q-learning for offline reinforcement learning: Towards optimal sample complexity. arXiv preprint 238.:
Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittiiserr, J., Antonoglou, I., Panneershelvan V., Lanctot, M., et al. (2016). Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484 489.
Silver, D., Schritwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., et al. (2017). Mastering the game of go without human knowledge. nature, 550(7676):354-55,
Tsybakov, A. B. (2009), Introduction to Nonparametric Estimation. Springer New York.
Uchara, M. and Sun, W. (2021). Pessimistic model-based offline reinforcement learning under partial coverage. arXiv preprint arXiv:2107.0622
11

---

Published as a conference paper at ICLR 2023
Uehara, M., Zhang, X., and Sun, W. (2021). Representation learning for online and offline rl in low-rank mdps. arXiv preprint
Wainwright, M. (2019). High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge University Press.
Wang, I.., Zhang, W., He, X., and Zha, H. (2018). Supervised reinforcement learning with recurrent neural network for dynamic treatment recommendation. In Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 2447-2456.
Wang, R., Foster, D. P., and Kakade. S. M. (2020). What are the statistical limits of offline rl with linear function upproximation? arXiv preprint arXiv:2010. 1189..
Xie, Q.. Chen, Y., Wang, Z., and Yang. (2020). Learning zero-sum simultancous-move markov games using function approximation and correlated equilibrium. In Conference on learming theory, pages 3674-3682. PMLR.
Xie, T., Cheng, C.-A,, Jiang, N., Mineiro, P., and Agarwal, A. (2021a). Bellman-consistent pessimism for offline reinforcement learning, arXiv preprint arXiv:2106.00 069226
Xie, T., Jiang, N., Wang. H., Xiong, C., and Bai, Y. (2021b). Policy finetuning:
Bridging sample-
efficient offline and online reinforcement learning. Advances in neural information processing systems, 34.
Xiong, W., Zhong, H., Shi, C., Shen, C., and Zhang, T. (2022). A self self-play posterior sampling algorithm for zero-sum markov games. In International Conference Machine Learming, pages 24523. PMLR.
Yin, M., Duan, Y., Wang, M., and Wang, Y.-. (2022). Near-optimal offline reinforcement learning with linear representation: Leveraging variance information with pessimism. arXiv preprint arXiv:2203.05880
Yin. M. and Wang. Y.-X. (2021). Towards instance-optimal offline reinforcement learning with pessimism. Advances in neural information processing systems, 34.
Zanette, A. and Brunskill, E. (2019). Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pages 7304-7312. PMLR.
Zanette, A., Lazaric, A., Kochenderfer, M., and Brunskill, E. (2020). Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning, pages 10978- 10989, PMLR.
Zanette, A., Wainwright, M. J., and Brunskill, E. (2021). Provable benefits of actor-critic methods for offline reinforcement learning. Advances neural information processing systems, 34.
Zhang. Z., Yang, J., Ji, X., and Du, S. S. (2021). Variance-aware confidence set: Variance- dependent bound for linear bandits and horizon-fin frre bound for linear mixture mdp. arXiv preprint 21Xiv:2101.12745.
Zhang, Z. Zhou, Y., and Ji, X. (2020). Almost optimal model-free reinforcement learningvia veference-advantage decomposition. Advances in Neural Information Processing Systems, 33:15198 1121779--17777..
Zhong, H., Xiong, W., Tan, J., Wang. L., Zhang, T., Wang, Z., and Yang, Z. (2022). Pessimistic minimax value iteration: Provably efficient equilibrium learning from offline datasets. arXiv preprint arXiv:2202.07511.
Zhong, H., Yang, 7., Wang, 7., and Jordan, M. I. (2021). Can reinforcement learning find stackelberg-nash equilibria in general-sum markov games with myopic followers? arXiv preprint arXiv:2/12.13522
Zhou, D., Gu, Q. and Szepesvari, C. (2021). Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory, pages 4532-4576. PMLR.
12

---

Published as a conference paper at ICLR 2023
A NOTATION TABLE AND COMPARISONS
A.1 NOTATIONS TABLE
We summarize the notations used this paper in the Table 2.
Notation
Explanation
R mi Amin (Ea (a '))
Assumption (MDP) and 3 (MG)
(PAV) a) Exes Pa(el,,,
conditional expectation
Var (I
PA (A, (1x,)(())))"
conditional variance
(T (AV)(z
(x. (z. + (PAV)
Bellman equation and Bellman operator empirical variance estimator clipped conditional variance of V regular covariance estimator
0 (:s)) E 1, H²)
WnVhtal (I) max 1, Varn Vittalle (z, a)}
A E TED 6(2% of (2 0%
+ Ala
ala Jo(r "a))" + Ala
Mn ΣIED R,, a
variance-weighted covariance estimator
Σj ΣTED
dir Dere ".p + Ala
variance-weighted covariance matrix
IV hha (1t aT)
11th++10 ( (-
(Th (a (.
(f(+1)))
noise in the self-normalized process
Table 2: A summary of notations used in this paper. With slight abuse of notations, the notations for MGs are defined similarly but we replace (zz a) with (æ,, a, b) and replace (2%, a,) with (2%, a7, 67) accordingly.
A.2 ADDITIONAL RELATED WORK
We review existing works that are closely related to our paper in this section.
Offline RL. The principle of pessimism is first used by Jin et al. (2021c) empower efficient offline learning under only partial coverage. It shows that we can design an efficient offline RL algorithm with only sufficient coverage over the optimal policy, instead of the previous uniform one required by Precup (2000); Antos et al. (2008); Levine et al. (2020). After that, line of work (Rashidinejad al., 2021; Yin and Wang. 2021; Uchara al., 2021: Zanette et al., 2021; Xie et al., 2021a; Uchara and Sun, 2021; Shi et al., 2022; Li et al., 2022) leverages the principle of pessimism, either in the tabular case or in the case with function approximation, and we elaborate them separately.
Offline tabular RL. For tabular MDP, a line of works has incorporated the principle of pessimism to design efficient offline RL algorithms (Rashidinejad et al., 2021; Yin and Wang, 2021; Xie et al., bb; Shi et al., 2022; Li et al., 2022). In particular, Xie et al. (2021b) proposes variance-reduction offline RL algorithm for tabular MDP which is nearly optimal after the total sample size exceeds certain threshold. After that, Li et al. (2022) proposed an algorithm that is nearly optimal by introducing a novel subsampling trick to cancel the temporal dependency among time steps. Shi et al. (2022) proposed the first nearly optimal model-free offline RI. algorithm.
Offline RL with function approximation. For RL problems with linear function approximation, Jin et al. (2021c) designs the first pessimism-basee efficient offline algorithm for linear MDP. After that, Min et al. (2021) considers offline policy evaluation problem under linear MDP and designs novel offline algorithm which incorporates the variance information of the value function to improve the sample efficiency. This technique is later adopted by Yin et al. (2022). However, Min et al. (2021); Yin et al. (2022) depend (explicitly or implicitly) on an assumption that the data samples are independent across different time steps h so they do not need to handle the temporal dependency, which considerably complicates the analysis. Moreover, such an assumption is not very realistic when the dataset is collected by some behavior policy by interacting with the underlying MDP. Therefore, remains open whether we can design computationally efficient algorithms that achieve minimax optimal sample efficiency for offline learning with linear MDP. Beyond the linear function approximation, Xie et al. (2)21a); Uchara and Sun (2021) propose pessimistic offline RL algorithms with general function approximation. However, their works are only information-theortticc as they require an optimization subroutine over the general function class which is computationally intractable in general.
13

---

Published as a conference paper at ICLR 2023
Algorithm 2 PEVI (LinPEVI-ADV)
1: Initialize: Input dataset D, B1; (+++()) =.
2: for h = H...., do
3: An EnED h a (1) at) + Naa:
4: TR t An A
(ETDD (2%- o% (r% + (x1+))
5:
Tx(+--) t 31 ()ll((:-)]lA;
6:
Qn(,)) ()(:))) TTWn
wh Tx(: -
7: T (x(+1))+ arg max (: :), (n( 1)), Pa()) + (Q.()))) m. 1.))a.
8: end for
9: Output: के = ( J and V = (V))
Offline MGs. The existing works studying sample-efficient equilibrium finding in offline MARL include Zhong et al. (2021); Chen et al. (2021); Cui and Du (2022); Zhong et al. (2022). Among these works, Cui and Du (2022) and Zhong et al. (2022) are most closely related to our algorithm where they study the offline two wooplayeer zero-sung MGs in the tabular and linear case, respectively. In terms of the minimal dataset coverage assumption, both of them identify that the unilateral concentration, i.e., good coverage on the {(TT" v), (T, =²): (x1", " is an NE and (T,, v) is arbitrary. is necessary and sufficient for efficient offline learning. In terms of sample complexity, similarly, while for the tabular game, Cui and Du (2022) is nearly optimal in terms of the dependency on the number of states, there is a Ó(VdHt gap between the upper and lower bounds for linear MG (Zhong et al., 2022).
Online RL with function approximation. Jin et al. (2020) and Xie et al. (2020) propose the first provably efficient algorithm for online linear MDP and linear MG, respectively. However, there is gap between their regret bounds and existing lower bounds where we remark that similar issues of temporal dependency also cxist in the analysis of online algorithms for linear MDP and linear MG. For instance, in Lemma C.3 of Jin et al. (2020), they also need to analyze the self-normalized process where the uniform concentration leads to an extra factor of Vd. The recent work Hu et al. (2022) leverages similar ideas of reference-advantage decomposition, trying to improve the regret bound for the linear MDP but focus on the online setting, whose algorithmic design (optimism v.s. pessimism, choices of weights) and proof techniques (online v.s. offline) are different from ours. Chen al. (2022) considers the linear mixture MG, which is different from the model considered in this paper. Beyond the linear function approximation, several works on MDP (Jiang et al., 2017: Jin al., 2021a; Dann et al., 2021; Du et al., 2021; Foster et al., 2021) and MG (Jin et al., 202 Huang et al., 2021; Xiong et al., 2022) design algorithms in the online setting with general function approximation. When applied to the linear setting, though their regret bounds are sharper than that of Jin et al. (2020); Xie et al. (2020), their algorithms are only information-theoreti and are computationally inefficient.
Varihnee-weighted Regression. It is known that variance information is essential for sharp horizon dependence (Azar et al., 2017; Zhang et al., 2020; 2021; Zhou et al., 2021). Particularly, for online linear mixture MDP, Zhou al. (2021) develops the eariance-weighte minimax optimal regret bound: Zhang et al. (2021) considers the home-homogeneous setting and achieves horizon-free guarantee. This innovative idea is first introduced to the offline setting by Min et al. (2021) and Yin et al. (2022). In this paper, we mainly generalize this technique to the more challenging offline setting without the additional independence assumption required in the existing approaches. See Section for details.
regression and achieves the
B RESULTS FOR MARKOV GAME
We extend our techniques to the linear Markov games this section.
B.
PROBLEM SETUP
We introduce the two-player zero-sum Markov games (MGs) with notations similar to single-agent MDPs, which is slight abuse of notation but should be clear from the context.
14

---

Published as a conference paper at ICLR 2023
Two-player Zero-sum Markov Game with Linear Function Approximation is defined by tuple A, B3 H, IP r), where S denotes the state space, AA and are the action spaces for the two players, H is the length of each episode, P = {Px : S x A B - As As}l= is the transition {rn S A x B - [0, 1]} is the reward function. The first player (referred
kernel, and to as the max-player) takes action from A aiming to maximize the cumulative reward, while the second player (referred as the min-player) want to minimize it. The policy of the max-player is defined as π. = {Th : :S - AAIKE Analogously, the policy for the min-player is defined by - S AB).
Value Function and Nash Equilibrium. For any fixed policy pair (Tt, v), we define the value function V/A V. and the Q-function 0% as
H
H
V (z) = EST.
Σ Th Th = x|,,
(x a, Ba,
Σ
Tw (a an, bn) = (x, a, 6)].
h/=h
h/=h
For any function V S 3 R. we also define the shorthand notations for the conditional mean. conditional variance, and Bellman operator as follows:
(PA. (P,
Σ (,,'"l,,,,
[Vara v)(,,,, = [P,V (IP. ((,,
Z'ES
(TxV) a. b) = (z, + (PxV)
For any max- max-player's policy オ, we define the best-response as br(r) = argmin, (x) for all
(x, h) E S x H Similarly, we can define br(v) by br(v) = argmax, Va ((x) for all (x. h) S x [H] We say (T","* 1/" is a Nash equilibrium (NE) if TT" and v^ are the best response to each other.
For simplicity,
denote V/ Vi br(=)(( V/"" v-b((v), and (x)
V/" ,"' (xr). It is well V. (r). Then we can measure the optimality of
known that (x")"") is the solution to max, min, V,
policy pair (It, v) by the duality gap, which is defined in Zhong et al. (2022); Xie et al. (2020) as follows:
Gap((T, v). = -
(11)
We consider the linear MG (Xie et al., 2020), which generalizes the definition of linear MDP.
Definition 2 (Linear MG). MG(S, A, Pr))
a linear MG with (known) feature map d (d)
S x Ax R&,, for any h [H]. there exist d unknown signed measures pa (P , over S and an unknown vector 0n E Id, such that for any (z, a)
(1)
14
A. we have
Pal: x, u. = (0(x1, a, b), b),un())) (1 a, b) = (0(x, a, b), 0n)
(12)
We assume that [, a, b)ll < for all (x,a, E S Ax B, and max [11m (S) 10 S vd for all h E (H].
With slight abuse of notation, make the following coverage assumption for MGs. Assumption 3. We assume minβe[H] Amnn((E [Ā(2, a, ())((,,,)))))))d,) T)T > 0 for MGs.
B.2 LINPMVI-ADV+
LinPMVI-ADV+ (Algorithm 3) variant of pessimistic minimax value iteration (PMVI) from (Zhong et al., 2022). At high level, LinPMVI-ADV+ constructs pessimistic estimations of the Q-functions for both players and outputs a policy pair by solving two Nash Equilibrium (NE) based on these two estimated value functions. For linear MG, these also be done by regressions. Suppose we have constructed value functions (V, (V.+1. 11+1 at (h + 1)-th step, and two independent variance estimators of and o7, which are constructed similarly to Section 5. For now, let us focus on the main components of Algorithm 3 and defer the construction of the variance estimators to next subsection.
Given (9), we approximate the Bellman equations TvV4+1 and TA V V41 by solving the following regression problems:
1rg V n4 (1h+1) (0%) u/? + Al[w[[a. and T VAVK (0) 6(0) Wk
W argmin WERd
(2 af,, b%,
TED
(13)
In V h+ (1h++1 (0%) w/² Allwa and TAV (0) == ((o) Wr
Wr < argmin WCRd
o. ,,,, 0%, (%)
TED
15

---

Published as a conference paper at ICLR 2023
Algorithm 3 LinPMVI-ADV++
1: Initialize: Input datasets D, D', and 83; V VH+1()) V (+) = 0.
2 2: Construct variance estimator 0i and o as in Appendix B.3 with D'
3: for = H...., do
CR( 4: Σs EED [ ATa, En E "
Ala:
5:
En - (ErED ' (r), + V (144((1++)) Wh = En (TED (r + V (n+1(1T++1)
6:
[a(:..)) B
- [b(())) - B3 1oo |
7:
(,(1)) + (d()..)) (((),.)))))).)))))))))))))))))))
8:
T +
9:
(F1,,(55 ):: K.() <
(+5,)),,, 1//( (Axx
(T).(-1)..% + NE(Qu V.() - (u(())), (.1))))))) 0)((11-))xxB.
11: end for
Output: (f = [ (
where (o) is short for a, b), and P.gh+1 Pa9h++ be obtained by setting rí. 0 in Tigh+1 + ALa, and En,
and T91+1. Denoting the covariance estimators as En ΣTED g (1
d((e))
ErED " bD Ala, can estimate the Q-functions by LCB for the max-player and UCB for the min-player, respectively:
(0 + ((o) w, - [A(x, b),,
Ox(o) + ( + (In b).
(14)
where remark that they are pessimistic for the max-player and the min-player, respectively. Next, we solve the matrix games with payoffs Q, and Qn
(+ (, + NE(Q,( (), and
(1)11)) + NE(Qu6.;)). (15)
The V-functions estimations VA, and Vn are then given by
Vn- = (.B.aaa())))bbae (11-) Q, (3 a,
and
V = E Ea (1 a,,a, a,
(16)
After H steps, the algorithm outputs the policy pair (f ( ( and value functions (V = (VW)),, V (V.)
Similar to the linear MDP, a sharper uncertainty bonus leads to a smaller suboptimality gap. The tech- niques developed for MDPs can be separately applied the max-player and min-player. Specifically, given (V.+1: V W1),), if we denote the Nash Value as V4+1 we can decompose the uncertainties as follows:
T.KK (0) Vr (0) TAVE+ I, I, (0) + PA Vo) (. Vo)+)(o), TvVa+1 (0) TA VVin+ 1 T PA(Vati (o)1)(o) PA(V (o).
Reference Part
Then, similar the single-agent MDP, for sufficiently large K, the uncertainty is dominated by the reference part with Vi Moreover, when the independent variance estimators could approximate the conditional variance well, set I (z, a, b) Ô (vd) [,0(z, b) b||ا, and L. (I.
Ô (vd) (vd [,0(z, a, b) The full pseudo code is presented in Algorithm 3 and we have the following theoretical guarantee.
Theorem 5 (LinPMVI-ADV+) Under Assumption 1, for K (/d2H//M /R), if we set 0 < <
and Bg Ö(vd) in Algorithm 3, then with probability at least 1 8, have
B
(x) - Vi (x) S Ō(Vā).
(max Σ Emt Illo( on bn) 11sg + max h=1
Σ
Em.-- 1 Mo an bn) bwlls
where (xx v²²) is NE and Ej ETED (T(())
/V oh b%) Xla
16

---

Published as a conference paper at ICLR 2023
Algorithm 4 PMVI (LinPMVI-ADV)
1: Initialize: Input dataset D, P3; V V--((-) VH++ O.
2: for h H..... .1 do
3: An 2 TD p1 a 10(% 07 b/) AI.
4: Th A (E (T Th (n) [rī Luti (1)+
5:
Th
- An (ErED @ (Th o ( [r + V (++1(27+11
6:
[a(:,))) + Bg (al A o6. ()
7:
2,(,5)) +- ((6))))(())))))))))))))))))))))) (o()))) Wh (o
8:
( Th (Tn(r:)looo--
9:
-.) N
(55)))
10:
11:
V,() (1,))))
(1))))x
Va(+) - (2,(())),)
D AXB.
13:
end for
14:
Output: (f ( M M
(
Similar with the single-agent MDPs, LinPMVI-ADV+ replace an explicit dependence on the planning horizon H in PMVI (Zhong al., 2022) with instance-dependen characterization through Σ The mestance-dependenn bound of LinPMVI-ADV+ never worse than that of PMVI, and the improvement is strict when specialized the special case of tabular setting.
tighter lower bound. To further interpret the result, we establish the following nearly matching lower bound which tightens that in Zhong al. (2022).
Theorem 6 (Lower Bound for MG). Fix horizon H, dimension d, probability 8 >> O, and sample size K (ddd).. There exists a class M of linear MGs and an offline dataset 'D with [D] for any policy pair (R, D), it holds with probability at least 5 that
K, such that
sup (xllVi'((z)) (xi)) ovd. ( (max) Σ E IloallE; + max Σ En |oólll 1). MEM
where Dj = EEED 07 (T()N) / /V Th bh) + ATa and > is a universal constant.
As (V+++tal):.))) 2 1, it holds that [ιő(х,, on, bn. >b>>== 2 1 an by. bll Therefore, The- orem 6 improves the lower bound Zhong et al. (2022) at least by a factor of vd. Moreover, LinPMVI-ADV+ matches this lower bound up logarithmic factor thus is nearly minimax optimal when exceeds the threshold specified in the theorem.
B.3 LINPMVI-ADV
In this subsection, we first present the full pseudo code of PMVI (Zhong et al., 2022). We first follow the reasoning in last subsection but with naive variance 1, and thus with the regular ridge regression. Then, the reference-advantage decomposition allows to improve PMVI by a factor of vd by invoking Lemma 9 without uniform concentration in the reference part. The resulting bonus is 5 Ō(VdH) ( >)
LinPMVI-ADV admits the following theoretical guarantee:
Theorem 7 (LinPMVI-ADV). Under Assumption 1, for K > 01 (2d(H2//n H²/K), if we set À = and 34 = Ō(VáH) in Algorithm 4, then with probability at least 1 - 8, we have
VR (x) (x)
Ō(VVH)
max E E.r.wlllalll IIlaall,,
max Σ E Ex ll (onla,.)). (17)
where (xt" (=',"") v²) ) is an NE and A = Erep di aho b,) 0% DT) + Ala-
17

---

Published as a conference paper at ICLR 2023
We now proceed to construct the variance estimator for Algorithm 3.
Construction of the Variance Estimators. To begin with, we run Algorithm to construct
(V,, Vi with an independent dataset DD. This will only incur factor of 2 in the final sample complexity. Similar Lemma I, we can show that there exist Br,, (V h-1) and 3h,2 (V h+1) such that
(P (+1)),))) a) (á(2, a); (V.2(V b+1)) and [P V M+il(,,, approximate them via ridge regression with D):
(6(x, a) Bp, (V m+1)). We
B argmin Σ
(0h. 8) -V (V1+1)² (11+1)) (1TT+)))))))
+ 21
BER
TED'
Ba,
argmin
(0h 8) Vn+1 (1h+1)
+ 2l1111k
BERd
TED"
Then, the variance estimator is then constructed as
(x, a) max { 1, (622, a) 3h.2
1 -Ö
dH3
(b(a, a) ,B,,3
[0,H²)
(0.1]]
VKR
Similarly, we can construct the variance estimator o (z, a) with 1'++1 and dataset D', In particular, as (:.-) and (::-) only depend on the dataset D', they are independent of D. The variance estimation error is characterized in Lemma and the proof of MGs is presented in Appendix F.
C AUXILIARY LEMMAS
In this section, we provide several useful lemmas to facilitate the proof of linear MDP. The first lemma states that if we adopt the principle of pessimism, the suboptimality bound essentially reduces to the the uncertainty estimation, i.e., construction of the bonuses.
Lemma 2 (Regret Decomposition Lemma for MDP). Under the condition that with probability at least 1 8, the functions F S x A R in Algorithms 2 and 1 (Tn. bo,h bi satisfying
ITA VT (x, a) - Pn+ (ar, a)l S (), V(I,a,h) ESX Ax [H)
we have that with probability at least 1 5, for Algorithm 2 and Algorithm I that for any x E S,
H
(x) - V < (i()) 11(2) < > E. (.
z].
Proof. See Lemma 3.1 and Theorem 4.2 in Jin al. (2021c) for detailed proof.
Lemma (Decomposition). For a function fh+1, suppose that Trfh+11(;.)) ((.,)) wh- (r where (2 ah) can be either (for reg- (1105,00))
With wn - ΣTED
ular ridge regression) or the estimated variance (for variance-weighted ridge regression) and "
En ErED
0f (1 (9)) + Ala- Then, have the following decomposition:
(Tahhi1- - Thinttt (x) = dbxx, a) wh -6(x, a)
o (1% a ET (f [I a))xx @n a7)
(18)
S <A1lwnllz ||0(1, a))
110(I, a)1 +
where E7, ([++1) rT (3+144105441 -Ta Tn In particular, if fb+al is bounded by H - 1 and
(x(3%,08))
((xI.0%) || ETED (a)) (T.( S 8, then we can set X sufficiently small so that v < 3. In
this case, the second term dominating, Pr Printal))) admits similar results by setting Th 0.
Proof. See Appendix for detailed proof.
18

---

Published as a conference paper at ICLR 2023
D PROOFS OF LINPEVI-ADV
D.1 PROOF OF THEOREM 1
The proof requires a more refined induction analysis to deal with the temporal dependency. For instance, when analyzing the h-step, cannot take the condition that V - is small, which is required to make sure that the uncertainty of the advantage function is non non- conn-mminnning.. This is because due to the temporal dependency, taking condition on Vh+1 may influence the distribution at step h. carefully crafted induction analysis employed to solve the challenge.
Proof of Theorem 1. We will prove the theorem by induction. For f = H, for a function Il S R 1, we invoke Lemma 3:
Thgh+1 Thhn+1 (z, S VAdR (1)(2,
Σ d (x),aT) TED
(T(()+2)
|
(a)
(b)
For the reference part with 9h+1 = Vi since V independent of D, we can directly apply
Lemma 9 with À = 1 to obtain that with probability at least - би = =1 8/H².
TuV# TaVi+ (x,a) s Villz,))
where . log(2H²K/0) 2 1. To simplify the proof, we set bo a) 3VdH a)ll to further capture the uncertainty of (a) from the advantage function. Then, we can focus on the analysis of (b) for the advantage function. By construction, we have EH+1 10 S
Vū+1 - Vn+1 S &.ālI-0Vi holds with probability 1. By Lemma 9, suffices to set (1, VKK
8/8/2 ((o(z,)))lx, It follows that can set
VK*
(3vauvi+ (bb 3d0/2H22 [16(,-)]l;; S 4VdHH Vi (6((,-)lx;
= bo.Hb....... [-
VKx
where we use K 2 (2 to obtain the last inequality. If pessimism at step is achieved, we know that
(Tv=))=TVin= 2 TH THV 2 Qn a), S A,
where the last step is due to (z, to (H+i(x,))) S (x, This implies that (x) 2 (x) for all S and proceed bound the error follows:
(x) (x(x)= (Q Qu(a, ), )+)))))))))))))))))))))))))))) + (2, ).
7H (-(()
< Th VH42(x,)) FH / (1+111,,)) (,, ). + (Ta(Vitt) - (,
< 2 [T 21H x] + 0,
SvdH 1Vi == RH. Vx E S
VKR
where the last inequality uses Lemma 13. To summarize, the event En = (0 < (z) (x) s Rg Vx E S} holds with probability at least 1 6н = 1- - H This is the base case. Now suppose that the event E = {0 & Vitn (z) (x) s RA+1 == BvāH(H-A)yf Vr E S} holds with vKx
probability at least 8n+1- We are going establish the result for step Clearly, we can still set ().) 3v / Ill,,, 1. remains to determine (:.)( for (b) of the advantage function and to ensure that it is non -oniinmin., We need to deal with the temporal dependency, which requires more involved analysis. We first state the following lemma.
19

---

Published as a conference paper at ICLR 2023
Lemma 4 (Lemma B.2 of Jin et al. (2021c)). Ler : [0, R 1] be any fixed function. For any E (0, 1), we have
(2(2l0g()) + d + K X 1) s Σ % (E TED
P
However, (Vi+1- 1)) is correlated {(r oh, -DD.D. we need uniform concentration
argument. In particular, we remark that we cannot take condition that Vhtt Vn+1 S Ra+1 directly, We consider the function class
(D, B, = 0, :5 - H] with ||0||
X. 13:
where (,;10,,,2) = max aEA d Volz,a)2>-((s,a) (0.H-h+1)
(19)
With 141
Pa+1 denoted as we can estimate D as follows:
A
Σ
b0h (r% + f(xh+1))
TED
S Σ
V 0107 a TA 1/2 AT, A 112 O a7))
TED
K
S
baT a7)) T A 15700007 (7))
TED
K
Kd
H
Tr (AT -aa) s H /
follows that
f= Vh+t Bnui E FF41 [Vh+1 Vh41 Vh- E Vn+ (Do, Bo,
where Do = H Kd A - 1, and B 8VdH VT. For any e > O, we denote the c-cover of Fi+1 with respect to the supremum norm as (e) (short for Ne; D, B)) and its e-covering number as ( For each f E Fa41, we can find fe E NN+1 (e), such that supzes lf(x) - fc(x) s e. follows that
Σ hh {f) TED
1 Illf S RB413
A,
2
<
Σ
% (T((e)
1 (lleell < (Re+1 +c]] +2
Σ TED
th (ET() ((C)))
TED
A5
2
Σ
Th. (f(f))
1 fll.fello $ (Re41 c)} 2 A
TED
where the first inequality uses [llfllo I R441) implies {llfello (Ra+1 E)} and the second inequality is because the following estimation of the second term:
K
2
Σ
Φh (ET(() (f.))
< 2
Jo,A,
22 | | ||44 1l.p
T,
< 2 K2 ///
20

---

Published as a conference paper at ICLR 2023
where Il-llop denotes the operator norm and |A7/ll.,, S x-1 With union bound over No+1 and
Lemma 4, we obtain that
ΣΦi oh (Le)
P
sup A.NN4+1le)
1 {llfello S Rat1 + >
TED
H W ) d + K [)1 58/11.
(R + +)
8
With probability at least 1 - -5/H2, for all ʃ Frt1, we have
Σ TED
9K
(f)
1llf Ra+11}
A7
8VdH' VL VK*
H [Ni+a
+dlog(1+ )) + 222K2// 12 /1
inf <>0
+e)
2 22og
8
(20)
1
512K
2d
2 2l0 + 4d log
+
KR
d3/2
Kr
2
512K
2 log H1 112 18)++ + 4d² log
KR
/अ/2
where the second inequality is because the covering number of Fh+1 is bounded by that of Vh+i (B, and by Lemma 11, can take / //////////// (K3/2 Vk) to obtain
4K2VR, + d log(1+ d2/2 S 2d log( d3/2
512K
512K
log (c+ S dllog11 + dH
where the second inequality holds when K (128(128/FL)) As 1 and log S 6, it further holds that
(256dH)) (210g(E12/0) + 4d log( d3/2 KR
512
256dH
(2t + 4e (1+ log (312), + 3t))
KR
8704d H+?²
KR
To summarize, it suffices to set b1,b 94/8/2
|(bb(r,))lla a)l and we have
VKK
94d3/2 H2
Σ (LTT(Vi+1
VKr
Σ PT - Phtzi 1 [ Vitall I RRt1]
94d3/2 H2
VKr
TED
Viti - Pati/l BBrr))
+
< 6//H² + 6p+1 == Sh.
where 6p41 is the failure probability at step h + 1. AS >>K>>> (KPHH))), we can set
24d/2222 |l((, [1((,)))x, S
Ta(:)5 (3VTH
VKr
With RA = wvaH(H-htlyy VK
we proceed to analyze the failure probability of E,, = 10 S (x)- V S Rh, Vo E S). First of all, if Th Vn- 7, V.+ $ Tn and event Ex41 holds, we know
that
(), =T,V Vo.Va (x, 2 Ta Vn- (x, > @n(2, V(,, ESXA,
21

---

Published as a conference paper at ICLR 2023
and thus (x) (x) for all x E S. We also have
(x) (x(x)) (Qī(e,)) :) Qu(x, ) mi (+x)) (Qn (z, m,(()))))))))))))))))))) (-((12))
Th (x,, In Vn+ 1 (x, + FA (z. ) TH (11)11)))))))(()())) (Tn ),
S 2. (ih(--)(20 x] + Ri++1:
8VaH (H h)vT = RA: Vzz E S.
VKn
Therefore, the failure probability at step can be upper bounded as
8
PP (EE) S TP ( E141 n (Ta(:.) does not ensures pessimism}) S 8h+1 1 +
on.
H
Therefore, we have shown that with probability at least ò₁ 8 1 H² pessimism is achieved at step h and & holds with probability at least - 5n. By induction, and a union bound over h E [H], we know that if we set L'x = 4vdll v (l0(=:)) then with probability at least 6H(H+1) 1 - 6, 1Th V.+1 Tn A.Vn4llee ( a) S (2, a) holds for all 2H1
1- (6H +... 81) (h,2,0) a) E [H] x x A. The theorem then follows from Lemma 2.
D.2 PROOF OF THEOREM 4
Proof of Theorem 4. The proof basically follows the same arguments of that of Theorem 1 except that we can leverage the finite feature condition to derive different bonus term for the dominating reference function. We focus on deriving the (; -) and omit other details for simplicity.
We first elaborate Eqn. (6. 1) via the proof of Lemma (see Section for details):
Th Vi+ti+1 - - Vitz a) S VAdH [0( a) lls + Σ (o(1, A
0%) (T(V)-1).
TED
(a)
(b)
where (](Vi41) = r% + Vit+1 (1%+1) Tn Vitt (2% a.). We will bound (b) by 3 llo(2, a) with some 3 > 0 and we can set À sufficiently small so that v VdHH+ < 3. Therefore, we can focus on the analysis of (b).
We denote the state-action pairs at step / as D, = {x TED.. The key is that because Vi is deterministic, conditioned on Dr, the only randomness from 2/ and W independent and bounded random variables. In particular, for any fixed Dj, = D₁, and fixed o(x, a). by the Hoeffding's 's inequality, with probability at least HM we have
DTED are still
2H²M
(b) -
H² a), 6007 a log Σ TED
=HV
Al10(1 a)l log a) a)1 (10(0
22HM
(2HRM)
S H log
( (I), [M],
where in the equality, we use
Σ (5lz, a), A 222 o
Σ p(a,a) a) T 1 (l(z%//))60 M af) A ())
TED
TED
= ||b(,, a) 0)1 - > a) T (A )2 2
Then, if we denote the event
2H²M (
En (x. = Σ
(0(x,a), (7)
(T (V(V)))) > H. log
TED
22

---

Published as a conference paper at ICLR 2023
then it follows that
5
(T,(),a)) = 7 (E)((z,))DD = Di) &
H
where the last inequality holds for any fixed Dn. By union bound over all oxx, a), we know that with probability at least 66/HH² for (x, a) E A, have
(2H2M
Σ (b(z, 26) (L(V S H| log TED
(10(2, a)
By similar induction procedure, we can set -- = H1 Vloog (2Hg
| ()A,, where
we require K 2 Ô (2L and X = 1/d to make the advantage function and (a) non-dominating. Then, the theorem follows from Lemma 2.
E PROOF OF LINPEVI-ADV+
In this section, we present the proof of Theorem 2.
E.1 ANALYSIS OF THE VARIANCE ESTIMATION ERROR
First, we analyze the estimation error of the conditional variance estimator. We recall that we estimate V 1 a) based on dataset DD' as
(x, max 1, (oTKoT(0,00 (2, [0,113] - (x)),,.),,
(,, )) (0.11)
-ō
dH'
KK
Ba(x,a)
Lemma (Variance Estimator). Under Assumption 1, if 2 2(d2H' /x), then with probability at least 1 - for all (x, a, h) E S A x [H.), we have
dH
[V (V δ
S (x, S (VaVita(x,,))
(21)
VKK
Proof. We first bound the difference between 13 a) and [Var, 1 V (z,
- -[ ax), Bn. 3n.. )² 10,H]
(on, an), Bn.2 An..
(
(Ih,
(1P (# an)))
10,H31
+ [K (E). an), 3n.1 ))2 [0.H]
T (oh, an), 3n.2)
[P (2 an)
([I Vh (In, an)))
[0.H2]
(zh, Bn.2
+2H
(Ø (xn, (zh. Bn.1) [P (2h,
(a)
We note that both (a) and (b) are analysis of the regular value-targed target ridge regression, with target 12 2 and (V%+1): respectively. The analysis thus follows the same line of those presented in Appendix D when we deal with the correlated advantage part, except that we invoke Lemma 9 with range H for Vi+, and H for (V/+1)² We omit the details here for simplicity and present the results directly: with probability at least - 6/2, for all (I, h) S x Ax x [H].
dH²
(x, a) - [Var, V/o a)) $ (a) + 2H(b) & δ
(22)
VKK
23

---

Published as a conference paper at ICLR 2023
We then use Theorem 2 and Lemma 13 to show that with probability least 1 - 8/2, for all (z, a, h) E S A x [H],
Vara 1/41
Vara V/
(x; a)
s | ((Ph+1)2 - (Viit222 )
(Ir, (I) a) + + / -
(Ph (PhVittz) (1)
(23)
VdH+s
22H V/41 Vitta
(xr, (x, a) s (z, (x, 21l PA D/ Pa Pa
VKK
With a union bound over the estimations in Eqn. (22) and Eqn. (23), we know that with probability at least 1 - 5, the following derivations hold. First, by triangle inequality, we have
|| | Vara Vi++ (z, a) $ [Bx - -Var, Phtn (z, + Var, 1 - Vara Vi+ (1,
< <ō (
dH3
VKK
where we use Eqn. (22) and Eqn. (23) in the last inequality. This shows that (v, 0
AH3
<
VK*
[Vara 1 a) and the second inequality of the lemma follows from the fact that max 3 preserves the order of two numbers. On the other hand, we note that max is non-expansive, meaning that mmx 1, a} max 631 I la b). Then, we have
| - Va (z. a) &
V/ h+1
(zr + | Vhthh
[Vn Vi+ (x,
dH3
- Vara 1itt1
(Ir +
Vara 1/41 Varn Vi+ (I,
VK
dH²
dH3
dd3
+
+
VKK
(VK
VKK
dH3
VKK
where the third inequality follows from Eqn. (22) and Eqn. (23).
E.2 PROOF OF THEOREM 2
The proof idea is similar that of LinPEVI-ADV, except that need additionally estimate the conditional variance and apply the Bernstein-type Lemma 10 for the reference function. To simplify the presentation, we will focus on the uncertainty of the reference function is dominating, and focus on determining the threshold. To this end, we will omit the constants and logarithmic terms by Ô (-) throughout the proof.
Proof of Theorem 2. We still start with the following decomposition: for function 11gh+11l20 S R - 1, we invoke Lemma 3:
To.gh+1 Tngh+1 (a, a)
(1%, a.))
$ A|dR|lo(zz a|lxs,
ET (gh+1)
a)((,, a)
(V 14 ah)
TED
(a)
(b)
Similarly, we set À 1/H² to ensure that (a) < B2 l1o(2, Ô (vá) lé(z, so we focus on the analysis of (b). For the reference function, as [V Vi I ah) 2 we know that (VVV)))) < H. Then we consider the filtration Fr U (1/,, (1
where a(.) denotes the alalgebra generated by the
24

---

Published as a conference paper at ICLR 2023
V random variables. As \V A+ (2 a,,)) is independent of D, -, We proceed to estimate the conditional variance:
S% (V is mean-zero conditioned on
D- 1--1A (11+1))
VAVA (1%
11
VV Wa (10% 1%)
V V 1
dHaa
VKR
$ +1+
VV M..hiil h+1l 0%
- -
dH3
VKK
dH3
S 11+20
O(1),
VKK
where in the first equality, we use the fact that [V 1 is independent of DD and in the last
inequality, we use K 2 2 (d (d9 H*/K] /k) to ensure that v V (27 o7)) - Ô
d VKK
2 3 Then, we
can directly invoke Lemma 10 obtain that:
Σ (R) (I(VE+1) TED
2ō (vVV)
Similar to the proof of LinPEVI-ADV, the uncertainty of the advantage function is non-dominating for sufficiently large K (determined later) we can
0 |1 a)ls,"
Moreover, by Lemma 5, we have A
P/ 14 a7))) S IV Vitille o7) S H2, which implies that
Σ
(T(N) (V Pea ag)
+ +ll
-1
Σ
(T
+ +Ala)
3 H
Σ (K + Ala
V. 1
This implics that
|1 ") < [1, 0)1s;;-1 S H (1
V(x,a)
Following the same induction analysis procedure of the proof of Theorem 1, we know that Using the standard e-covering argument and Lemma 9, we know
Vu41 Vi+1 S that we set
vdd² VKx
(1, = 0 /d2/2
|ςő( a)ll,,
VKK
To make non-dominating, we require that K á (df /xx. Moreover, make (a) v [|o(,, a)lss, non-dominating, we set A = 1/H2. Then, the theorem follows from Lemma 2.
F PROOF OF MARKOV GAME
Proof of Theorem 5. The techniques developed for MDPs are readily extended to the MGs by decou- pling the estimations into the max-player part and min-player part start with the following lemma, which a counterpart Lemma 2.
Lemma 6 (Decomposition Lemma for MG). Under the condition that the functions Ia SxAxB ER in Algorithms 3 and 4 satisfying
T
- (I, (
T V (2,
b)) TT,
25

---

Published as a conference paper at ICLR 2023
for any
E 8 E Ax B [H). then for Algorithms 4 and 3, we have
H
(x) (z) (2)) - (1()) V/] S ssup
E (T a) x1 z],
hml
H
-V - - Vi - (x) S 2sup
E
E [n x1 z].
h=1
Furthermore, we can obtain that for any S.
Vi" (x) Vi (2)
Vi (x) (z) + Vi( V1""'(x'
H
H B Lx(
S 2sup
E (x a, b) #1 x] + 2 ssu
A=1
Proof. See Appendix A in Zhong et al. (2022) for detailed proof.
Therefore. it suffices to determine the + that establishes pessimism. Before continuing, we first prove Theorem 7, which required our subsequent analysis.
Proof of Theorem 7. We first note that Lemma 3 is constructed for (weighted) ridge regression and can be applied to linear MG by replacing ((x, a) E IRd with p(x, a, b) accordingly. Therefore, for function g S A B [0, H - 1}. we have
o ( % bn) Tn og by)
Thgh+1 - Th9ht1 (z,a,b) 24
Σ
En(ont))
| =
(24)
o (2h, aje 67) Tn (0% 071 b)))
[Tigh+1 - T n9h+11 (x,
Σ
E (9n+2))
11 a)l
TED
where En ETED d(1 oi La (R)
Alas (l 11 Ta 10 (x
(nj, (6,)
and Mn, (gh+1) are defined similarly for g. (.,))) Moreover, we again omit the VdHH as we can set À sufficiently small (determined later).
For LinPMVI-ADV, we set decomposition for MG (Eqn. (B.2)), it suffices to focus on the reference function with the Nash value Vit1 where Lemma 9 can be applied directly:
an so En En An. By the reference-advantage
(Th V h+1 (4)) (z, b) 2 ( [,(o,, a (n(x,,,b),
(TrV 4+1 - v. (z, a, b)] S ( 10(2, a. b)ll,, a,,
We follow the same induction analysis procedure of Theorem to obtain that [+ - Vitallso S Ô H(H-A) and || Vitilloo < Ô H(H-M) By standard e-covering argument and
VK* Lemma 9, we can set
VKK
(.2H2, (18P2PP)) |1 a, b)ll
(1, 0
VKK
To make it non donommmmnnnnng,. we require that K 2 õd(d H2 /R). Also, make VXdH Ô (VaH). it suffices to set À = 1. Now we invoke Lemma 6 with lA = FA = L. to obtain that for any x E S,
VI (z) (x:)
11
< 2 sup D
Ex [T (x, b) 21 x] + 2sup Σ E E [T(2 ()) 21 =x]
4=1
H maxx Σ
H
< (((dH)
Em E (lo(1n an, bu)lla + max Σ
E ||0(In an, bn) (a,)))
h=1
26

---

Published as a conference paper at ICLR 2023
With Theorem 7 in hand, similar to Lemma 5, we have the following lemma to control the variance estimation етrоr and we omit the proof for simplicity.
Lemma 7 (Variance Estimation Error for MGs). Under Assumption 1, in Algorithm 3, if K > (d /n), then with probability at least 6, for all (I, a, b) E S x A x [H]. we have
dH3
S 50
V [2z b)
VKR
dH3
() δ
S Sg. (1 - V V (1, a,
VKK
Similar to the proof of Theorem 2, K K 2 0 (d 11 /n), the conditional variances of E, (Vh+1)
and (Vi+i) are O(1) so it suffices to set (t = Ô (vv)) |T((,, and (n(:))) = (vd) |00 ". Moreover, because V V h+1 (2,, a, b) S H2, we have
3
&
H2 A
Eh 3 E
1 H2A, A,²²
We can similarly establish VV+1 h+1 Vi 0
vVHH) and
V N41 Vi SO (V() VKx
VKxx
respectively. suffices to set (1, = Ō d/2 222 Kk ||,(, and ())
(8/2
ò 0 (d/223/VKK) (o(.,:;))l>> where K 2 ((d /K) is sufficient to make them non-
dominating. Moreover, we need to set A = 1/11² to make vddH S Ô (vd). The theorem then follows from Lemma 6.
G PROOF OF LOWER BOUNDS
We only provide the proof of the lower bound for MGs, and the lower bound for MDP follows from the similar argument (see Remark for details). In particular, we remark that the Vd-dependency does not contradict Theorem 4 as the feature size of the constructed instances is exponentially in
Proof of Theorem 6. Our proof largely follows Zanette et al. (2021); Yin al. (2022). We construct a family of MGs M = (Muhuezs where U/ = {uu (uI..... uH) un E {-1, vh E [H]) For any fixed u E U, the associated MDP M,, is defined by
State space. The state space S = (-1, +1).
Action space. The action space A= B (-1,0,1)d-2
Feature map. The feature map @ x A B + Rd defined by
2d
bl, =
Rd
d(-1,a,b)
0
E Rd
VT
1
V2
Transition kernel. Let
0g-2
pm pm (m()-)
E Rdd
v/2
By the assumption that Ps s,a, (ø(s, a, b). (s))), we know the MDP reduces homogeneous Markov chain with transition matrix
P
R 2x2
27

---

Published as a conference paper at ICLR 2023
Reward observation. Let
Cup v
Ou, =
E ERa
v3
where Ç [0, V3d" By the assumption that rn(s, a, b) (d(s, a, b), 0n), we have
(u, v6
(a, un)
V2d
We further assume the reward observation follows Gaussian distribution:
(8, ~
v6 +
(a, un).
V2d
Date collection process. Let fer, e2, ed-2) be the canonical bases of Rd-2
and 0a-2 E RR-2
be the zero vector. The behavior policy μ 8 + AAx is defined
1 d' Vj E [d - 2]:
plej, Oa 8) 1==
02-2 18) d'
By construction, Nash equilibrium of My is (T*,"") :*) satisfying (+)+ up and --)() Wn Since the reward and transition are irrelevant with the min-playerss policy, we use the notation u" (u. ..... uig (sign(E, [a1]), ... sign(E, (axl)). Moreover, for any vector v, denote by its i-th element uli). By the proof of Lemma 9 in Zanette et al. (2021) we know
H
V - VI
ΣΣ
Hugl] - un|
22
h=1i=
<
Du (u),
(25)
2d
By Assouad's method (cf. Lemma 2.12 in Tsybakov (2009)), we have
(d H
sup Eu[H u)] 2 well
min 2 w.a (=(
inf[Pa(W + u) + (1 + v')l,
where vi is the test function mapping from observations to {u, u'}. Furthermore, by Theorem 2.12 in Tsybakov (2009), we have
1/2 (T((2)l
min u.w (u
inf
# n2')22 u,a (u((ux))=11
(26)
where Qu takes form
K e II
H (
(
1/ [Bu, (5 ar b/)] (ri) Ph. (si+n af. bl)
k=1
A=1
where & = [ 1 is the initial distribution.
KL(Q..lQ..) = K
E. [oog[[ao,, at, (R))()))(Bw..nl at. (()()
K d-2
Σ
KL
(N
S
(eyj un)) 1
(ee, ( (e3,
d
22d
22d
1=1
K
(N({5
[N(
( ||
S
-5
2K
KT.
(27)
d
28

---

Published as a conference paper at ICLR 2023
where the third equality uses the fact that DH (u, u() 1. Choosing Ç = ((d/VK) (25), (26), and (27) imply that
dvdH VK
inf max [V
(28)
a, well
Here K 2 ((dd)
ensures that S
On the other hand, we have v3d
1
Var V4+ (s,, a,
(-+1(-1)- -
1
1/ (-1)(-
12 1
V Vh+t(++)) (Vi+1(+1) + Vi+i (-1)(-11))
1
+
1 (+1, ( 21t,,,41,,,, Th+1 (-1, u441, 1,,,, un+1))
2
2
6'
where the second equality follows from Bellman equation, and the last inequality uses the facts that "u, a. b) ratt+1 (-1, a)
2 By calculation, we have
v6
3K ΕΣ
d
La-
dva (d-2)xx
E Rdddd
2
2x
1
dvd
By Gaussian elimination, know (EEE/K) d. For all h E [H], (s, and K 2
Q(d log(2Hd/6)). holds with probability - that
11o(,, a, b) 1
I 2. 11,1o,ss b)]lE));) 11
4 d
1
d
d-
3K 4 a
Il-2
(d-2)xx
1d-20
- 2
2(d - 2)
2(d 2)
4 {d
d
1)
+
(1 1 )
+
3K
4
4(d - 2)
4
4
[ddd
2)
d
(1- 12)2
+ 4(d - 2)
+
3K
4
4
d(d
2)
d(d 1)2
1
d2
2
3K
4
4(d 2)
4
K
where the first inequality uses Lemma 13. Hence, we have
H
" Er. (| an, bn) S dH
max Σ El.,r an, bn) b(2 + max
Σ
(29)
VK"
h=1
for any u E U. Combining (28), (29), and the fact that IV V we have with probability at least 5 that
[V V for any u Ut
inf max E, V**. weld
V=.*]
H
2 cvd. ( (max
Σ
Ser, an, bn bb)ll()))) + max
Σ 1=1
En @ an, bn)l (2))))
h=1
which concludes our proof.
Remark 1. our construction, the min-player will not affect the rewards and transitions. So by the similar derivations of (28) and (29), we can obtain inf, max.eu EulV, - -V71 dyah and
vK
Σ"_ E,, (s, an) (n)p))))>> S dH VK"
Hence, establish the lower bound for MDP desired.
29

---

Published as a conference paper at ICLR 2023
H NUMERICAL SIMULATIONS
For completeness, we adopt a similar synthetic linear MDP instance that is also used in Min al. (2021) and Yin et al. (2022), and redo the experiments to verify the theoretical findings. The adopted MDP has {1, 2), A {0,.... represent A by IR For the last two bits of the feature, we define 6(r,a) 1 = 0, 0)
..... 99), and d 10. For the feature, we apply binary encoding to
where 1 is the indicator function. Then, the MDP is characterized as follows.
PEVI LinPEVI-ADV
PEVI LinPEVI.ADV
ADV+
LiD+EVI-DDV+
Suboptimality
Suboptimality
10a
10-1
10
10"2.
10-2
6000 7000
10-2
6000
400016000110000
K
K
(a) Horizon H 20.
(b) Horizon H 40.
Figure 1: Suboptimality v.s. The number of trajectories K. The results are averaged aver 100 independent trails and the mean result is plotted as solid lines. The error bar area corresponds to the standard deviation.
Feature mapping:
Φ(z,a) = (aT 1 eRd
True measure Phc
2y (x) (0, (0. (
an $ an).
where {au ME(A a sequence of integers taking values in 0 or generated randomly and fixed, and @ the XOR operator. The tranision is given by Pa (x'| a) = (Ø(x, a), (x))).
Reward function: we define
0₂ = ... (0,, 18
with = 0.9 to obtain the mean reward TA a) = (ó(z, a), On). Thr reward is then generated Bernoulli random variable.
Behavior policy: always choose with probability p, and other actions uniformly with (1 p)999. We choose = 0.5.
The initial state is chosen uniformly from
The regularization parameter À is set to be 0.1 suggested by Yin et al. (2022) and estimate the value of the learned policy by 1000 i.i.d. trajectories where we also set the reward to be its mean during the this evaluation process.
Figure 1(a) and Figure 1(b) match our theoretical findings that sharper bonus function leads to smaller suboptimality. Therefore, LinPEVI-ADV+ achieves the best sample complexity, and PEVI performs worst. In particular, as increases, we can see that both LinPEVI-ADV and PEVI perform worse significantly, while the convergence rate of LinPEVI-ADV+ is rather stable. This demonstrates the power variance information, which has been observed by the previous work on offline linear MDP (Min al., 2021; Yin et al., 2022).
30

---

Published as a conference paper at ICLR 2023
1 PROOF OF AUXILIARY LEMMAS
Proof of Lemma 3. We add and subtract p(x, a) " 2n (En - -dd))u in the second equality to obtain
that
(Tnf (Tnfnnr)) (x) a((,,a) (wn (Wp)
(rh + fnt11 (1h+1))
[) wn -(( 'np"
Σ %h
FED
= a)" wh (1( a) a
--- (En
Ma) wh
67 (0,))
(1ī + fn+i (xh+1))
+ 111 a) "
Σ
(10 - En
Σ 0
(1/ (7p)
Wh
o2 o1h) fi+t1 (27(+77+)1)
TED
TED
=ho(a, a) 2 wi + Φl a) 1
Σ
%%
(Tnfit1 a7
Th
0
(1% 07))
TED
<> sAllwalls, | a1l
Σ
(T(+1)))
(1(x, a) a
hh (o), x
This proves the first part of the lemma. Now suppose that [fh+1| is bounded by H - 1. We have,
| || = On + /
S + max Jn+1 HVd,
x'
and
w/ < |wall V E S A | VX VAdH, A w 27 ww
where we use Amiu (E)) S -- Therefore, by setting sufficiently small such that vddH & 3, (i) non-dominating and we can focus on bounding (ii).
J TECHNICAL LEMMAS
Lemma (Hoeffding's inequality (Wainwright, 2019)). Let X1, ,,, be mean-zero independent
random variables such that [X,] S & almost surely. Then, for any t 0, we have
12
2n²
IP
Σ X1 2
< exp
Lemma 9 (Hoeffding-type inequality for self-normalized process Yadkori et al. (201 1)). Let 1i be real-valued stochastic process and let {Fili be a filtration such that ni is Fi- measurable. Let (2 be -a-uul stochastic process where is Fi-1 measurable and |,,,|| S L.. Let A₂ MI. + D F. Assume that conditioned on Ft Tp is mean-zero and R-subGaussian. Then for any 0, with probability at least 1 - for all > O, we have
Σ Doll
< RR dlog +1+ (1L))
& Rg dlog
A + IT.
Ô (RVa).
X8
AT
Lemma 10 (Bernstein-type inequality for self self-normalized process Zhou et al. (2021)). Let { be a real-valued stochastic process and let {Fi) be filtration such that T). F.-measurable. Let (xx (2 be an Rdd -valued stochastic process where In is F.-1 measurable and || S L. Let
A = XT Ei= FzD. Assume that
Imal S R, 1mm O, E. F o².
Then for any > O. with probability at least - 5, for all 1> O, we have
112
412
412 =0 (ova)
Σ x
s 80
dlog (1+ Ad
1+
log
+ 4R Rlo
88) (5))
8
A
31

---

Published as a conference paper at ICLR 2023
Lemma 11 (e-Covering Number (Jin et al., 2021c)). For all h E [H] and all e <>> 0, let N(+) be the covering number of the function space specified in (19), we have
log (e; R. X) & d log(1 + 4R/c) + de log(1 + 82 B² (c2
Lemma 12 (Lemma H.4 of Min et al. (2021)), Let : A A- - TRd satisfying 1|o,,, a)ll S C for all (x,, a) E x A. For any K > O and X > 0, define Gx = - Φ( an ) ax) axxT= + Ala where (It, ak)'s 's are Lid. samples from some distribution over S A. Let G B, a)o(z, J.
Then, for any 8 E (0, 1), with probability at least
holds that
G K
GK
4V202 VK
log
2d 8
1/2
Egl
Lemma 13 (Lemma H.5 of Min et al. (2021)). Let : 8 x A + R2 satisfying ||o( a)ll S C for all (z, S x A. For any K >> 0 and X > O. define GK = Σ k=1 Φ ax (x) ax) T + Als where (IX, ak) 's are ii.d samples from some distribution Then, for any 5 E (0,1), 1), if K satisfies that
S A. Let G E.lő(a, (2)(2)))0)))))))) T.
K 2 max 512C*
|G log
2d
4A G
|
(30)
Then with probability at least 1 8, it holds simultaneously for all E IRd that
|luloz S VK
11lll-1.
32


Reviews:
[{"review_id": "ucaTtSTh_DZ", "reviewer": "Reviewer_iMxh", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents algorithms for offline RL combined with linear function approximation. They consider both MDP and Markov games scenarios. They combine two techniques: reference-advantage decomposition and variance-reweighted ridge regression which have been previously used in offline RL literature.  The authors then establish matching lower bounds for the proposed algorithms. The proposed algorithms are computationally efficient while having the tighter theoretical guarantees.\n", "summary_of_the_review": "This paper presents algorithms for offline MDP and MG using pessimism in a variance-reduction manner and variance-reweighted ridge regression. The presented bounds are tighter and matches the lower bounds. The techniques used in this paper have been used previously in offline RL.", "strength_and_weaknesses": "\n1. The paper is very well written; the contribution is clear. \n2. The algorithm is very similar to Yin et. al (2022), is the difference only in the analysis to consider temporal dependency?\n3. While the proposed algorithms are efficient in terms of sample complexity, it is not clear to me how would one test the algorithm numerically. For example, the algorithm takes in the input $\\beta_1 = \\mathcal{O}(\\sqrt{dH})$, is it just an artifact of the analysis and it can been any number say in [0,1].\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "YRrcIeQlG7", "reviewer": "Reviewer_NJRa", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies offline reinforcement learning problem for linear MDPs. In such a setting, the controller is given a trace of execution of the MDP with a fixed exploration policies. The controller uses this trace to compute a near-optimal policy. The objective of this paper is to provide an algorithm with provable regret guarantee. The authors study both the classical MDP setting and the two-player zero-sum Markov games.\n\nFor MDP, such an algorithm already exists in the literature but the authors of the current paper argue that their analysis do not hold. The authors therefore propose a new algorithm that fixes the bugs.  This algorithm is the adapted to the two player zero-sum Markov game.\n", "summary_of_the_review": "The paper proposes an algorithm for offline RL. This algorithm is claimed to correct a bug from previous work. This result seems strong but the writing quality is insufficient.", "strength_and_weaknesses": "This paper proposes to correct an existing algorithm for offline MDP.  This seems a valid contribution if the result holds. I must admit, however, that I found the paper very hard to read, with lots of technical details and notations. This might be because I am not that familiar with the previous paper but I also think that it is because the paper wants to present too many results. Hence, it is not really self-contained and the results are barely commented or described.\n\nFor instance, the authors choose to add an extension to two-player zero-sum Markov games. I do not think that this brings new insight nor original ideas compared to the MDP case but that takes an extra 2 pages. As a result, there is no related work in the paper, and no real comment or explanation around the results.\n\nSince this paper is mostly a theoretical paper that aims at correcting a bug in a previous analysis, I think that this analysis should be made clear. In the current version, I cannot be sure that the authors are also overlooking some steps of the proofs.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "3gjxwkBThXw", "reviewer": "Reviewer_BwgL", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposed minimax near-optimal algorithms and matching lower bounds for linear function approximation in MDPs and MGs. In particular, it removes the independent assumption of sampling across different time steps as in Yin et al. (2022).", "summary_of_the_review": "The paper proposed minimax near-optimal algorithms and matching lower bounds for linear function approximation in MDPs and MGs, and also removes some (explicit or implicit) assumptions in the literature. However, the writing needs to be improved before I recommend accepting.", "strength_and_weaknesses": "The result is sharp and improves upon the best-known results so far. However, I think the current writing hurt the quality of the paper a lot. Before recommending to accept, I think the following aspects need to be handled properly.\n1. What's the point of Section 4? According to my understanding, it behaves worse than the algorithm introduced later in the next section, and also the algorithmic form looks very standard, if not totally the same as Jin et al. (2021c). Actually, I think the algorithmic idea here has already been covered in that paper. If I have misunderstood anything, please correct me by explicitly adding some discussion on this difference. \n2. Regarding Section 5, it seems to me the main technical contribution is to remove the additional (implicit) assumption in Yin et al. (2022). Am I understanding this correctly? If so I think this is something the authors may want to emphasize earlier in the paper. Actually, it would be very helpful to add a table comparing the result in all the related work in offline RL with linear function approximation.\n3. The authors may also want to highlight some of the technical contributions of this paper, and make a sharp distinction between the existing techniques and the ones you proposed (or improved). For example, I think the advantage decomposition has already been used by Jin et al. (2021c). As a classic technique, the authors may even want to put this into the preliminaries section and only keep the very original part in the remaining sections. This not only helps the readers to place the current paper in the whole literature but also makes it easier to evaluate the value of the paper.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster