Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settings 
Authors: Ming Yin
Yu-Xiang Wang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Theory
Reinforcement learning theory
Markov decision process theory

Abstract: This work studies the statistical limits of uniform convergence for offline policy evaluation (OPE) problems with model-based methods (for episodic MDP) and provides a unified framework towards optimal learning for several well-motivated offline tasks. Uniform OPE $\sup_\Pi|Q^\pi-\hat{Q}^\pi|<\epsilon$ is a stronger measure than the point-wise OPE and ensures offline learning when $\Pi$ contains all policies (the global class). In this paper, we establish an $\Omega(H^2 S/d_m\epsilon^2)$ lower bound (over model-based family) for the global uniform OPE and our main result establishes an upper bound of $\tilde{O}(H^2/d_m\epsilon^2)$ for the \emph{local} uniform convergence that applies to all \emph{near-empirically optimal} policies for the MDPs with \emph{stationary} transition. Here $d_m$ is the minimal marginal state-action probability. Critically, the highlight in achieving the optimal rate $\tilde{O}(H^2/d_m\epsilon^2)$ is our design of \emph{singleton absorbing MDP}, which is a new sharp analysis tool that works with the model-based approach. We generalize such a model-based framework to the new settings: offline task-agnostic and the offline reward-free with optimal complexity $\tilde{O}(H^2\log(K)/d_m\epsilon^2)$ ($K$ is the number of tasks) and $\tilde{O}(H^2S/d_m\epsilon^2)$ respectively. These results provide a unified solution for simultaneously solving different offline RL problems.

Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Mask-Agnostic Settings
Ming Yin 1.2 and Yu-Xiang Wang'
Department of Computer Science, UC Santa Barbara Department of Statistics and Applied Probability, UC Santa Barbara Ling-yin@ucsb.. edu yuxiangu@cs. www.uuus.ee.. edu
Abstract
This work studies the statistical limits of uniform convergence for offline policy evaluation (OPE) problems with model-based methods (for episodic MDP) and provides unified framework towards optimal learning for several well-motivated offline tasks. Uniform OPE supm 1Q Q < c is stronger measure than the point-wise OPE and ensures offline learning when II contains all policies (the global class). In this paper, we establish an SHH S/dmm
lower bound (over model-based family) for the global uniform OPE and our main result establishes an upper bound of Ó(H²) /dm, for the local uniform convergence that applies all near-empiry optimal policies for the MDPs with stationary transition. Here dm is the minimal marginal state-action probability. Critically, the highlight achieving the optimal rate DHH2/dme is our design of singleton absorbing MDP, which is new sharp analysis tool that works with the model-based approach. We generalize such a model based framework to the new settings: offline task-agnostic (K is
and the offline reward-free free with optimal complexity Ó(1² loH)) the number of tasks) and Ó(H S/dm=²) respectively. These results provide a unified solution for simultaneously solving different offline RI problems.
1 Introduction
Offline reinforcement learning (offline RL) targets at learning a soward-maximizing policy in an unknown Markov Decision Process (MDP) using static data generated by running behavior policy [Lange et al.] 2012 Levine et al.) 20200 This framework is widely applicable in applications where online exploration demanding but historical data are plentiful. Examples include medicine [Liu ett al. 2017] (safety concerns limit the applicability of unproven treatments but electronic records are abundant) and autonomous driving [Codevilla al. 2018 (building infrastructure for testing new policy is expensive while collecting data from current setting is almost free).
Parallel to its practical significance, recently there is surge of theoretical investigations towards offline RL via two threads: offline policy evaluation (OPE), where the goal is to estimate the value of a
target (fixed) policy V (Jiang and Li 2016)] Liu et al. 2018 Kallus and Uchara 2020 2019 Uehara
and Jiang 2019 Nachum et al. 2019 Xie et al. 20099 Yin and Wang 2020 Duan et al. 2020 Wang
al. [021 Zhang al. 202 and offline (policy) learning which intends to output near-optimal
policy [Chen and Jiang 2019 Le et al. 2019] [ie and Jiang 2021 2020 Liu et al.) 2020h Hao
al. 2020 Zanette 202 Jin al. 2020c Hu et 2021
Yin et 202lb Rashidinejad al.
2021
Yin et al.
2021a initiates the studies for offline RL from the new perspective of uniform convergence
in OPE (uniform OPE for short) which unifies OPE and offline learning tasks. Generally speaking,
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

given a policy class II and offline data with n episodes, uniform OPE seeks to coming up with OPE estimators V/= and QT satisfy sup l|Q Q 1loo < e. The task is achieve this with the optimal episode complexity: the "minimal" number of episodes n needed as a function of e, failure probability 5, the parameters of the MDP well the behavior policy μu in the minimax sense.
To further motivate the readers why uniform OPE should be considered, we state its relation to offline learning, Indeed, uniform OPE to RL is analogous of uniform convergence of empirical risk in statistical learning [Vapnik] 2013]. In supervised learning, it has been proven that almost all learnable problems are learned by an (asymptotic) empirical risk minimizer (ERM) (Shalev-Shwand 2010). In offline RL, the natural counterpart is the empirical optimal policy म* := argmax, V/"" and with uniform OPE it further ensures f* is near-optimal policy for the offline learning via:
et al.
S Q" Q Q" - -Q Qi - oi" + QI" - Qî" sup QQi Q7.
(I)
On the policy evaluation side, there is often a need to evaluate the performance of a data- dependen policy. Uniform OPE suffices for this purpose since it will allow us to evaluate policies selected by safe-policy improvements, proximal policy optimization, UCB-styl (CB-style isploration-bouus heuristic exploration criteria (please refer to Yin et al. [2021a] and the references therein for further discussions). In this paper, we study the uniform OPE problem under the finite horizon stationary MDPs and focus on the model-based approaches. Specifically, we consider two representative class: global policy class II, (contains all (deterministic) policies) and local policy class II; (contains policies near the empirical optimal one, see Section 2.1). We ask the following question:
well as any
What is the statistical limit for uniform OPE and what is its connection to optimal offline learning?
We answer the first part by showing the global uniform OPE requires a lower bound of Q (HH e I for the family of model-based approach and the local uniform OPE can achieve Ó(H² /dm, ²² minimax rate by the model-based plug-in estimator and this implies optimal offline learning. Importantly, the procedure of the model-based approach via learning म* through planning over the empirical MDP has a wider range of use in offline RL as it naturally adapts to the challenging tasks like offline task agn-stico learning and offline reward- free learning. See Section 1.2
1.1 Related works
Offline reinforcement learning Information--theoreiiei considerations for offline RL are first pro- posed for infinite horizon discounted setting via Fitted Q-Iteration (FQI) type function approximation
algorithms [Chen and Jiang 2019 Le et al., 2019 Xie and Jiang 2021 2020] which can be traced
back to Munos 2003 Szepesvári and Munos 2005 Antos et al., 2008a
[021a]] first achieves Ö(H²) =dm=") complexity under non- stationary transition but their results cannot further improve in the stationary setting. Recently, Yin
For the finite horizon case, Yin et al.
et al. [2021b] designs the offline variance reduction algorithm for achieving the optimal /dm=) rate. Their result for a specific algorithm that uses data splitting while our results work for any algorithms that returns a nearly empirically optimal policy via uniform convergence. Our results on the offline task-agnostic and the reward-free settings are entirely new. Concurrently, |en et al. [2021] considers the horizon-free setting but does not provide uniform convergence guarantee.
Model-based approaches with minimaxity. is known model-based methods are minimax-optimal for online RL with regret O(VHSAT) (e.g. Azar et al. (2017), Efroni al. (2019). In the generative model setting, Agarwal et al. 2020) shows model- approach is still minimax optimal 7) AA/e") by using a s-absorbing MDP construction and this model-based technique is later reused for other more general settings (e.g. Markov games (Zhang al. 2020al and linear MDPs [Cui and Yangl 2020) and also for overcoming the sample size barrier [Li et al. 2020). In offline RL,
Yin et al.
2021a uses the model-based methods to achieve Ô(H3) /dm 2 complexity.
Task-agnostic and Reward-free problems. The reward-free problem is initiated in the online RL (Jin et al. 2020a) where the agent needs to efficiently explore an MDP environment without using any reward information. It requires high probability guarantee for learning optimal policy for any
Herr dm the minimal marginal state-action occupancy, see Assumption 2.4 We only provide short discussion of the most related works due to the space constraint. A detailed discussion can be found in Appendix
2

---

reward function. Later, Kaufmann et al. [2020], Menard et al.
(2020) establish the 03
Recently, Zhang et al. [2020b] proposes the fask-agnostic setting where one needs to use exploration data to simultaneously learn K tasks and proves an upper bound O( S S log log(K)/ However, although these settings remain critical in the offline regime, statistical result has been derived so far.
complexity and Zhang et al. [020cc further tightens the dependence to
1.2 Our contribution
Optimal local uniform OPE. First and foremost, we derive the Ó(H² / optimal episode complexity for local uniform OPE (Theorem [4T] via the model- based method and this implies optimal offline learning with the same rate (Corollary 4.2); this result strictly improves upon Yin et al.
2021a (Ö(H3) (Omm+/dmm=")) =)) non-trivially through our new Siingetoon-bsorblee MDP technique.
aeformatiiontheorrticce characterization of the global uniform OPE. We characterize the statisti- cal limit for the global uniform convergence by proving minimax lower bound 52( S/2 S/mmm (over all model-based approaches) (Theorem 3.1). This result answers the question left by Yin et al. (2021a] that the global uniform OPE is generically harder than the local uniform OPE/ / offline learning by factor of S, such a difference will dominate when the state space is exponentially large.
Generalize to the new offline settings. Critically, our model-based frameworks naturally generalize to the more challenging settings like task-agnostic and reward-free settings. In particular, we establish the Ó log(K) K) / ) (Theorem 5.3) and SH²2 (Theorem 5.4) complexities for offline tusk-agnostic learning and offline reward-free learning. Both results are new and optimal.
Singleton-absorbing MDP: a sharp analysis tool for episodic stationary transition case. On the technical end, our major contribution is the novel design of Singleton-absorbing MDP which handles the data-dependence hurdle encountered in the stationary MDPs. To decouple the data-dependence between Ps.a and V. Agarwal et al. 2020] uses a s-absorbing MDP V. (in lieu of V) of each state for the independence. To control the error propagation between V, and V, they use the e-net covering such that the value of V. traverse the evenly-spaced grids in [0, (1 - 2) However, when applied to finite horizon case, the complexity increases as there are H different quantities (V,.... VH) and the e-nets need to cover the !I-dimensional space [0, 1H) H This result in a exponential-Ii covering number and the metric entropy blows up by f'ccorr H, which yields suboptimal result. In contrast, the aaggleton-absorbiin
MDP technique designs single absorbing MDP that can also control the error propagation sufficiently well. This sharp analysis tool negates the conjecture Cf and Yang 2020) that absorbing MDP is not well suitable for finite horizon stationary MDP.
Significance: Unifying different offline settings Beyond the study of statistical limit in uniform OPE, this work solves the sample optimality problems for the local uniform OPE, offline task-agnostic and offline reward-free problems. If we take a deeper look, the algorithmic frameworks utilized are all based on the model-based empirical MDP construction and planning. Therefore, as long as we can analyze such framework sharply (e.g. via novel absorbing- MDP technique), then it is hopeful that our techniques can be generalized to tackle more sophisticated settings. On the other hand, things could be more tricky for online RL since the exploration phases need to be specifically designed for each settings and there may not be one general algorithmic pattern that dominates. Our findings reveal the model-based framework is fundamental for offline RL as it subsumes settings like local uniform OPE, offline task-an agg-ssicc and offline reward-free learning into the identical learning pattern. Considering these tasks were originally proposed in the online regime under different contexts, such unified view from the model-based perspective offers a new angle for understanding offline RL.
2 Problem setup
Episodic stationary reinforcement learning. A finite-horizon Markov Decision Process (MDP) denoted by a tuple M = (S. P.r, di),,, where S and A are finite state action spaces with S := [S).A A := [A]. A stationary (time- (time-invarianl invariant) transition kernel has the form P: S x A X S + [0, 1] with ((s'|s.a) representing the probability transition from state 8, action a to next state s'. Besides, r S x A + R is the expected reward function and given (s, a) which satisfies 0 S r S and assumed known. d, the initial state distribution and H the horizon. At
time t, policy π (TI, TH) assigns each state E S probability distribution (T(s) over
3

---

Figure 1: Related comparisons of sample complexities for offline RL
Resuld/Method
Setting
Type
Complexity
Unilorm guarantee?
Le ct.
2019
oc-horizon
FQI variants
Q((1~>) BB/e))
No
FQI Chen and Jiang
2019
oc-horizon
FQI variants
0(11-))-0//)
No
MSBO/MABO
Xie and Jiang
2020
oc-horizon
FQI variants
( OdHH
No
OPEMA Yin al
2021a
H TT-oorizon
Non-splitting
VH/S-loca uniform
OPDVR Yin
202
H -horizzo
Data splitting
S(HH/dme
Model-based Plug-in (Corollary
4.2
H H-horizon
Non-splitting
((H²1dmm)))
V HH/S-local uniform
Task-Agnostic (Theorem
H H-horizon
Non-splitting
Reward-Free Free (Theorem 5.4]
H H-horizon
Non-splitting
((H-S/dm=²")
K is the number of tasks for Task mask-agnostic setting and 3p.. C and 1/dm data coverage parameters that
mcasure the state-action dependence and are qualitative similar under their respective assumptions.
actions. For a policy random trajectory $1, d1, ................................ 5H, TH $1 ~ d1, a ~ ((-[ss),re F2 = r(s,, 4)), $1+1 ~ (( St, (5,,a)) a.), Vt E [H].
TH 8H+1 is generated as follows:
For any policy π and any h E [H], value function (-) R$ and Q-value function Q% E RS are defined as: (s) = E. Di ri/sa = s]. (5, = E., [- ra|sh, s, s. Vs, E S,A. The goal of RL to find a policy 't such that e* == E. E>= ri is maximized, which equivalent to simultaneously maximize VT (s) (or (T
(,, a)) for all (or 8, (Sutton and Barto 2018). Therefore, Sec. We denote V Q7, column vectors and Ps.a as the row vector. In particular, we denote the average marginal
for targeted accuracy > 0 it suffices to find policy Talg such that [[Q - Q1
state-action occupancy d= (s, a) as: d' (s, = # Σ P(s.- = =//81 ~ d1, T] TT (als).
Offline setting. The offline RL assumes that episodes D some behavior policy 4 a priori. In particular, we do not assume the knowledge of /z.
{(69)at (0. 10 (42 hett are rolling from
Model-based RL. We focus our attention on the model- methods, which has witnessed numer- ous successes and is one of the most critical components of theoretical RL whole (as reviewed in Section L.I). To make the presentation precise, we define the following:
Definition 2.1. Model-based RL: Solving RL problems (either learning or evaluation) through learning / modeling transition dynamic P.
We emphasize that the model- -bade approaches in general (e.g. Jaksch al. [2010], Ayoub jet al. (2020), Kidambi et al.] (2020]) follow the procedure of modeling the full MDP M (S,A, P.r. H, di) instead of only the transition P. Nevertheless, we (by convention) assume the mean reward function is known and the initial state distribution d, will not affect the choice of optimal policy n². Thus, Definition 2.1 suffices for our purposes.
2.1 Uniform convergence in offline RL
We study offline RL from the uniform OPE perspective. Concretely, uniform OPE extends the point-wise (fixed target policy) OPE to family of policies 11. The goal is to construct estimator
Qi such that supsen Qi Qi < e, which automatically ensures point-wise OPE for any x E TI. More importantly, uniform OPE directly implies offline learning when II contains optimal policies. As explained in Section let ~ argmax, V be the empirical optimal policy for some OPE estimator 6 then by ① π is a near-optimal policy given uniform OPE guarantee. We consider the following two policy classes that are of the interests.
Definition 2.2 (The global (deterministic) policy class.). The global policy class 1l, consists of all the non-stationary (deterministic) policies.
is well-known [Sutton and Barto 2018) there exists at least one (deterministic) optimal policy, there- fore I, is sufficiently rich for evaluating algorithms that aim at learning the optimal policy. Definition 2.3 (The local policy class), Given empirical MDP and V. is the value under M. Let .t arginax Vi be the empirical optimal policy, then the local policy class Hl is defined as:
I1 = {T
I Capt Vh E [m}
s.f.
where Eopt 2 0 is parameter.

---

In above M uses P in lieu of P where P(s' a,a) = "y' if Rs,a > 0 and 1/S otherwise This class characterizes policies in the neighborhood of empirical optimal policy. Given P. it is efficient to obtain 7' using Value Policy Iteration, therefore it is more practical consider the neighborhood of H* (instead of π²" since practitioners can use data D to really check I1 whenever needed. Next we present the regularity assumption required for uniform convergence OPE problem.
Assumption 2.4 (Exploration requirement). Logging policy μ. obeys that min, (s) > for any state s that is "accessible" ". Moreover, we define the quantity dm == min,,a {d' (s. a) : d' a) > 0} (recall d' (s.a) in Section 2 to be the minimal average marginal state-action probability.
State 8 is "accessible" means there exists policy so that d= ds(ss) O. If for any policy always have d= (8) 0, then state 8 can never be visited in the given MDP. Note this is weaker than Yin al. 202 since ds) the average version of di (s). Assumption 2.4 the minimal assumption needed for the consistency of uniform OPE task and is qualitatively similar to the concentrabillty assumption [Munos] 2003]. This assumption can be potentially relaxed for pure offline learning problems, e.g. Liu et al. [2019], I, Rashidinejad et al. [2021], where they only require dl (() (d (s, a)) > O for any state 8 (8, a) satisfies d" (d) (8,a) O.
3 Statistical Hardness for Model-based Global Uniform OPE
From 4 and Definition 2.2 it is clear the global uniform OPE implies offline RI., therefore is natural to wonder whether they just are "the same task" (their sample complexities have the same minimax rates). If this conjecture is true, then deriving sample efficient global OPE method is just as important as deriving efficient offline learning algorithm (plus the additional benefit of evaluating data-dependent algorithms)! Yin et al. [2021a] proves the O(HSS/dm upper bound and 9(H /dm=²) lower bound for global uniform OPE, but it is unclear whether the additional S is essential. We answer the question affirmatively by providing tight lower bound result with concise proof to show no model-based algorithm can surpass ((5/dm²)) information- thhoortticaa limit.
Theorem 3.1 (Minimax lower bound for global uniform OPE). Let d be a parameter such that O dm S SA. Let the problem class be Má.. {(u, M) min,, di (s,, az) 2 dm Then there exists universal constants C,p > 0 such that: for any n 2 cS/dm -ogg(SA)),
@T.m - 25 2
H2S ndmm
inf sup Fu,M sup =
2 P.
Qua Mdm
where Q jub is the output of any model-bused algorithm and Hg is defined in Desinition 2.2
Theorem 3.1 establishes the global uniform convergence lower bound of (HH S/dme? over model-based methods, which builds the hard statistical threshold between the global uniform OPE and the local uniform OPE tasks by factor of 5 since the local case has achievable Ó(1/dm.²) rate on the dependence for state-actions. This result also reveals the global uniform convergence bound in Yin et al. [2021a] (Ö(HSS/d ())m))))))))))))))))))))))))))) is essentially minimax rate-optimal for their non-stational stationary setting and complements the story on the optimality behavior for global uniform OPE. Moreover, from the generative model view the lower bound degenerates to S/dme² x O(S A/e) which is linear in the model size 52 This means in order to achieve global uniform convergence any algorithm needs to estimate each coordinate of transition kernel P(s'|s, a) accurately. We now provide the proof sketch and full proof is deferred to Appendix C
By setting 6 =
H2S
ndm.
Proof Sketch. We only explain the case where H = 2 in this proof sketch. Our proof relies on the following novel reduction to 4 density estimation
@ - xlll
sup
sup 3,a 2
1 -((ss.))-((sssa)))
P(.
3 'erre ns.a is the number of pair (s, a) being visited among n episodes. n is defined similarly. "To be rigorous, we ramark that it is rate-optimal since for the non-stationary setting the dependence for horizon is higher by factor H.
5

---

and leverages the Minimax rate for estimating discrete distribution under 1 loss is
Han et al. 2015). Concretely, by Definition 2.1 let P be the learned transition by any arbitrary model-based method. Since we assume r is known and by convention Q#+1 = 0 for any x, then
by Bellman equation 0% Th + pT 0h+1 Vh E [M] In particular, 07+ = 47+ = 0,
and this implies Q7 QH ти. Now, again by definition of Bellman equation QH
TH-1+ + 7MH Q = HH-11 + pMRTH and Qh- = =--11* + parrg, therefore (recall H = 2 and
note TH E ERSAA, AH "H E ER$)
sup r
Qū- Qu-
sup ntll,
(PTN - pru) r=11 = sup xEi1,
(
xH TH
p)r|| 2
r/
1 2
P(-1s, -P(1B.a) 2 Olv S/naa);
sup re(o.1)s
sup s,a
Lastly, using exponential tail bound to obtain O 0(V5/m 2 O00S//nd)) with high probability. See Appendix Cfor how to prove the result for the general H.
4 Optimal local uniform OPE via model-based plug-in method
Global uniform OPE is intrinsically harder than the offline learning problem due to the additional state-space dependence and such a gap will amplify when S is (exponentially) large. This motivates us to switch to the local uniform convergence regime that enables optimal learning but also has sub-linear atateacttion size ((1/d,,) in the policy evaluation. Yin et al. [021a]] Theorem 3.7 first obtains the Ó(H ((H+/ddm²)) =dm local uniform convergence for II, (recall Definition 2.3 and also obtains the same rate for the learning task. Unfortunately, their technique cannot further reduces the dependence of H for stationary transition case. In this section we show the model-based plug-in approach ensures optimal local uniform OPE and further implies optimal offline learning with episode complexity ÓHH² <d) To this end, we design the new Singleton-absorble in the stationary transition setting, which uses the absorbing MDP with one single H-dimensional reference point and is our major technical contribution. The abboobbggg MDP technique avoids the exponential H cover used in Cui and Yang (2020) and answers their conjecture that absorbing MDP is not well suitable for finite horizon stationary MDP
MDP to handle the challenge
4.1 Model-based Offline Plug-in Estimator
1[5 (1) (4) = 8, s.a] be the total counts that visit (8, a) pair,
Recall T2. ==
then the bodel-based offline plug-in estimator constructs estimator P as: ((s'(s,)) =
DM 1((s(()) (0) (a(/ (x - if n2 0 and P(s'|s,a)) a) = if ns,a = 0. As a conse- quence, the estimators Q VetT are computed as: Q = r + p Q7+ - PV with the
12..
initial distribution d n,/n. Under the above setting, we can define the empirical Bellman optimality equations (as well as the population version for completeness) as V E S. E [H]:
ViA (s) = max (r(s.a) a) + a(-1s, Vi((s) = max + P(15,,))
Now we can state our local uniform OPE result with this construction.
4.2 Main results for local uniform OPE and offfine learning
Recall
#* argmax, De is the empirical optimal policy and the local policy class T1 = {T:
s.t. - I Capt vh E [H]}-
SSee their Section 7, first bullet point for discussion.

---

Theorem 4.1 (optimal local uniform OPE). Let Copt S WH/S and denote log(HSA/6), For any E [0, 11. there exists universal constants c, such that when n cH Log(HSA/0)/oe with probability 1 6,
@i - Q. 0 SC
H²L ndm
S0.
sup EETT
Tecl
Theorem 4. establishes the O(H2/dmm complexity bound and directly implies the upper bound for suprem, V - V with the same rate. This result improves the local uniform convergence rate Ó(11 (TLIf/dmee /) ) in Yin al. [021a]] (Theorem 3.7) by factor of H and is near-minimax optimal (up to the logarithmic factor). Such result is first achieved by our novel singleton absorbing MDP technique. We explain this technique in detail in the next section.
On the other hand, characterizing policy class through the distance in value (like II;) more flexible than characterizing the distance between policies themselves (e.g. via total variation). This is because: two policies are "close", then their values are also similar; but the reverse may not be true since two very different policies could possibly generate similar values. Therefore the consideration of I is generic and conceptually reflects the fundamental principle of RL: as long as two policies yield the same value, they considered "equally good", no matter how different they are
Most importantly, Theorem 4.1 guarantees near-minimax optimal offline learning: Corollary 4.2 (optimal offline learning). If cops S VH/S and that sup, I|V 8 V/21 S capt when n > O(H 1/dm), then with probability 6, element-wisely.
Vi' - Vi cc
H' ndm..
H 112.g00.5
Caps
ndm.
Corollary 4.2 first establishes the minimax rate for offline learning for any policy म with the mea- surable gap Eopt S VH/S. This extends the standard concept of offline learning by allowing any empirical planning algorithm (e.g. VI/PI) to find an inexact रे as an (ÓvH2 /ndm faps )-optimal policy (instead of finding exact ") The use of inexact से could encourage early stopping (e.g. for VI/PI) therefore saves computational iterations. Besides, we leverage full data to construct empir- ical MDP for planning and, on the contrary, Yin al.] [2021b] uses data-splitting (split data into mini-batches and only apply each mini-batch each specific iteration) to enable Variance Reduction technique, which could cause inefficient data use for the practical purpose. By the following lower bound result from Yin et al. [2221b) our Corollary 4.2 near minimax optimal. Theorem 4.3 (Theorem 4.2. universal constants C1, C22 c, (with H, A C1 and 0 < C2) such that when I cH? /dme"
Yin et al. (20216). Let Ma... be the same as Theorem 3.1 There exists
inf Vi
sup (e.M)
PM,M (IIVT ViTuto ll 2 2p.
For the rest of the section, we explain the proving ideas by introducing the singleton-abxorbiig MDP technique and the full proofs of Theorem 4.1 Corollary 4.2 can found Appendix B D
4.3 Singleton absorbing MDP for finite horizon MDP
For the ease of illustration, we explain our idea via bounding 11 Q 1| (instead of sup+en, ||QT (bo) and choose related quantity 7* (instead of 7) and V (instead of Vi discuss. Essentially, the key challenge in obtaining the optimal dependence stationary setting the need to decouple the dependence between P P and V, as we aggregate all data for constructing both P and V,- This issue is not encountered in the non-stationary setting in general due to the flexibility estimate different transition P, each time (Yin et al. 2021a and P. and V preserve conditional independence. However, when confined stationary case, their complex Ó(H3) /dm becomes suboptimal. Moreover, the direct use of s-absorbing MDP in Agarwal et al. [2020] does
We recognize that in the specific settings (e.g. safe policy improvement) some of the policies that yield high values are not feasible. These considerations are beyond the scope of this paper.
'The original Theorem uses e" but we use V here. It does not matter since we can manually add a default state the beginning of the MDP and obtain the result for version.
7

---

not yield tight bounds for the finite horizon stationary setting, as it requires s-absorbing MDPs with H. -d-mennsional fine-grid cover to make sure Vi is close to one of the elements in the cover (which has size s !H and it is not optimal Cui and Yang (2020). We overcome this hurdle by choosing only one delicate absorbing MDP to approximate Vi which will not incur additional dependence on horizon H caused by the union bound. We begin with the general definition of absorbing MDP initialized in Agarwal al. 2020) and then introduce the singleton absorbing MDP.
Standard s-absorbing MDP in the finite horizon setting. The general s-absorbing MDP is defined follows: for fixed state and a sequence {ur 1 MDP M Ms.(u.).. is identical to M for all states except 8, and state is absorbing in the sense PM PMr, "( (s|s, = for all a, and the instantaneous reward at time t is rz(s, a) un for all a a A, [H]. For convenience, we use and similarly for Qe, r and transition P. Also, the shorthand notation (e..u.) to denote V fL
(s...) (s.M.)) is the optimal value under M (u.)
Before defining singleton absorbing MDP, we first present the following Lemma 4.4 and Lemma 4.5 which support the our design.
Lemma 4.4. (s) Vi+a(s) 2 O, Vs E S,t [H]]
Lemma 4.5. Fix a state If we choose ut == (s) Viti(s), then we have the following vector form equation
[h ViTM wh [H].
Similarly, if we choose ú, == (s) (s), then V (s,ag) = Vi Ah E [H].
The proofs are deferred to Appendix B Note by Lemma 4.4 the assignment of ut (:= (a.(s.u)) })
well-defined. Lemma 4.5 is crucial since, under the specification of uj the optimal value in
Ma, MM)') is identical to the optimal value in original M. Based on these, we can define the
following:
Definition 4.6 (Singleto--bbsobiing MDP). For each state 8, the singleton-ubsorbing MDP is chosen to be Ma Ma where in == (x) (8) for all t (H].
Using Definition 4.6 for each (s, a) row the term (P... - Vi can be substituted by (P..e- Ps,a) Vi.V ". where Ps.a and V A,,,, are independent by construction and Bernstein concentration applies. Furthermore, by the selection of ut, we can control the error of [|V; Vitte. ylloo have
rate Ol V which forces the term (Ps,a (V, Vii(o,);)) to have higher order error. These are the critical building blocks for bounding 11 - -Q llx.
Indeed, by Bellman equations we have the decomposition:
0% --- Q
EH Dhr (P-P) Vin.. where 17+12= IT pms is multi-step state-action transition and Tht1 = T. Then for each (s,a) row
(Pe.a PP,,) (Pa.a (V
Viltaayy) (Pa.o Pa.a)
E|I 3,a Pr
Pi.comeg)l +1
Vi
Var (hisewsps)
S 11,a
Vi
V
+
Var (VF)
(x)
Yea
(2)
where (*) is the place where the traditional technique uses the union bound over their exponential large e-net and we do not have it! Next, by Lemma 4.5
4.5aand and Lemma in Appendix
1i Villo [[Vhit.,;))
V alo S H max lúg uil < 2H max V0: Vi+l
by a crude bound (Lemma J.10 max, I VA
S
H2
S which makes
Vi Vi.(onng) Iloo have order 1/ 1/n Finally, to reduce the horizon dependence we apply
ΣH Thtis/ Vars,a (VÆ S V(H- - hy3 for any n. This (informally) bounds Q Q by
11"%" - -Q²¹ 11x0 S v
Poly(H.S) Lastly, use mins, nsaa 2 H dm to finish the proof.
Re,a
8

---

Remark 4.7. We emphasize the appropriate selection of M Mot(, (Ma, is the key for achieving optimality. It guarantees two things: 1. Vi, hAsst)) approximates Vž with sufficient accuracy (has rate al/ 2. it avoids the fine-grid design with exponential union bound in the dominate term (V Var. (Vr) log( with [Uaaa to be at least H Cui and Yang (0201.)
N
5 New settings: offline Task-agnostic and offline Reward-free learning
From Corollary 4.2 our model-based offline learning algorithm has two steps: constructing offline
ggjn] 2. performing any accurate black-box planning algorithm and returning "o T)) as the final output. However, the only effective data (data that contains stochasticity) is D' = {(s} (4) )ee This indicates we are essentially using the state-action space exploration data D' to solve the task-specific problem with reward r. With this perspective mind, it natural to ask: given only the offline exploration data D', can we efficiently learn set of potentially conflicting K tasks (K rewards) simultaneously? Even more, can we efficiently learn all tasks simultaneously? This brings up the following definitions.
empirical MDP M using the offline dataset D = {(s)") al r(s)" (1) (1), ) st+1 ( te[#]]
(8)
Definition 5.1 (Offline Task-agnostic Learning). Given a offline exploration datatset D' (( at (0) (E(H] by μ with episodes. Given K tasks with reward {rw] and the corre- sponding K MDPs Mr- = AS Tk. d1). Can we use D' to output , Rx such that P Vra.k & [K]. Vi, Vi Sc 2 87
Definition 5.2 (Offline Reward-free Learning). Given a offline exploration datatset D' ((0()) ( (6) [E( by ye with n episodes. For any reward and the corresponding MDP M
ai
Pr,, H, d1). Can we use D' to oulput र such that P |Vr, |[ VT.M l1x S 1 67
Definition 5.1 and Definition 5.2 the offline counterparts of Zhang et al.) 20206 and Jin et al. (2020a in online RL. Those settings are of practical interests in the offline regime as well since in practice reward functions are often iteratively engineered encourage desired behavior via trial and error and using one shot of offline exploration data D' to tackle problems with different reward functions (different tasks) could help improve sample efficiency significantly.
Our singleton absorbing MDP technique adapts to those settings and we have the following two theorems. The proofs of Theorem 5.3 5.4 can be found in Appendix E
F
Theorem 5.3 (optimal offline task-agnostic learning). Given D'
{(s a, (1) [E[H] by μ. Given
K tasks with reward {rx) and the corresponding K MDPs M₁ A, P, rk; H, di). Denote
1 = log A/55))) Let मे == argmax, 7 Vk E [K], when n > O(H [t + log K) dm). then
with probability 1 5, Vi,MM V.A.
SO H*(++)og(K)) rdd...
+
Wk E [K].
nd...
Theorem 5.4 (optimal offline reward-free learning). Given = {(s()
te|m] Mie[m] by p. For any reward denote the corresponding MDP M (S, A, P.r, H,d,). Denote log( (
Let AM = argmaxx ViT Vr, when > O(HS 1/dm), then with probability 8.
VT.M
Ai L.M
0
H3S. md
H2 md...
Vr, M.
By a direct translation of both theorems, we have sample complexity of order Õ(H² log(K)/dme)
and Ō(H² 5/d,, c/) All the parameters have the optimal rates, see the lower bounds in Zhang et al. 20200b] and Jin et al. [2020a] The higher order dependence in Theorem 5.4 also tight comparing to Theorem 5.3] Such statistically optimal results reveal the model-based methods generalize well to those seemingly challenging problems in the offline regime. Changing these harder problems would not affect the optimal statistical efficiency of the model-based approach.
We add discussion in Appendix G to explain more clearly why our rates optimal for these problems.

---

Extension to linear MDP with anchor representations
The principle of our Singleton absorbing MDP technique (with model-based construction) in de- coupling the dependence between P... and V is not confined to tabular MDPs and therefore is natural to generalize such idea for the episodic stationary transition setting for other problems. As an example, we further present sharp result for the setting of finite horizon linear MDP with anchor points. We narrate by assuming generative oracle (that allows sampling from s' ~ P(|s, a)) for the case of exposition. Definition 6.1 (Linear MDP with anchor points Yang and Wang 2019 Cui and Yang. 2020 ). Let S be the exponential large space and A be the infinite (or even continuous) spuces. Assume there is feature map é S x A - RK (where K & (S), iee $(8. a) = (dn a)...., 0x( a)}. Transition P admits linear representation: P(š'(e,))
EkE[K] Φz a))x)(ss))) where tin (.)....., ..... , are unknowns. We further assume there exists a set of anchor state-action pairs such that any (s, a) can be represented as a convex combination of the anchors {(8x. ax)(k E KC}:
( (ss
Σ kEK
X3 15.0 (8k: ax):
Σ X
1, 2 0, vk (s,a)) E (S,
REK
Under the definition, denote N be the number of samples at each anchor pairs. Then have the following (see Appendix for the proof):
Theorem 6.2 (Optimal sample complexity). Under Definition
6.1 let म* = argmax, Vi. Then if 1l Ö(v HH/)..
N eS
we have with probability 1 - 6, Q
Qi
Comparing to Theorem of Cui and Yang 2020]. Theorem 6.2 removes the additional dependence min K, H In term of the total sample complexity, Theorem 6.2 gives Ö(K /e²) while Cui and Yang 2020 has Ö(K (c²) (see their Section 7, first bullet point). Our result again reveals the basel-based method is statistically optimal for the current setting.
Remark 6.3. The rate O(KH//e /e²) with anchor point assumption has the linear dependence on K and for the standard linear bandit [Lattimore and Szepesvári [020] 12 ((V)TT) or the linear (mixture) MDP (Jin el al. 2020b Zhou et al. 2020 (( the lower bound dependence on the feature dimension d is quadratic. We believe one reason for this happen is that anchor representations assumption is somewhat strong as it abstracts the whole state action space by only finite points (via convex combination).
7 Conclusion and Future Works
This work studics the uniform convergence problems for offline policy evaluation (OPE) and provides complete answers for their optimality behaviors. We achieve the optimal sample complexity for natiinnary-traniitinn case using a novel adaptation of the absorbing MDP trick, which is more generally applicable to the new offline task-agnostic and reward-free settings combining with the model-based approach and we hope it can be applied to a broader range future problems. We end the section by two future directions.
On the higher order error term. Our main result (Theorem 4.1 has an additional v HSS dependence in the higher order error term and we cannot further remove based on our current technique. Nevertheless, this is already among the best higher order results our knowledge. In fact, most state-of-the-ee works (e.g. |Azar et al. [2017] Dann et al. [2019] Zhang et al. (222b]) have additional dependence in the higher order and it also has additional VA (see Table of et al. 2b22 for a clear reference). How to obtain optimality not only for the main term but also for the higher order error terms remains clusive for the community.
Jin Jin et al. 22018 8 has only extra VS in the higher order term but
Uniform OPE and beyond. The current study of uniform OPE derives results with expression using parameter dependence and deriving estance-dependen uniform convergence result will draw clearer picture on the individual behaviors for each policy. Besides, this work concentrates on Tabular MDPs and generalizing uniform convergence to more practical settings like linear MDPs, game environments and multi-agent settings are promising future directions. Specifically, general complexity measure (mirroring VC-dimensions and Rademacher complexities for statistical learning problems) that precisely captures local and global uniform convergence would be of great interest.
10

---

Acknowledgment
The research partially supported by NSF Awards #2007117 and #2003257. MY would like thank Simon S. Du, Zihan Zhang for explaining question in Zhang et al. [2020c]; and Tongzheng Ren for the helpful discussions.
References
Alekh Agarwal, Nan Jiang, and Sham M Kakade. Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, 2019.
Alekh Agarwal, Sham Kakade, and Lin F Yang. Mloeel-bsed reinforcement learning with a generative model minimax optimal. In Conference on Learning Theory, pages 67-83, 2020.
Andras Antos, Remi Munos, and Csaba Szepesvari. Fitted q-iteration continuous action-space mdps. In Advances Neural Information Processing Systems, pages 9-16, 2008a.
András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with bellman- residual minimization based fitted policy iteration and single sample path. Machine Learning, 71 (1):89-129, 2008b.
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, pages 463-474. PMLR, 2020.
Mohammad Gheshlaghi Azar, lan Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In Proceedings the 34th International Conference on Machine Learning Volume 70, pages 263-272. JMLR. org, 2017.
Jinglin Chen and Nan Jiang. information-theoreee considerations in batch reinforcement learning. In International Conference on Machine Learning, pages 1042-1051, 2019.
Herman Chernoff et al. A measure of asymptotic efficiency for tests of hypothesis based on the sum of observations. The Annals of Mathematical Statistics, 23(4):493-50) 1952.
Felipe Codevilla, Antonio M Lopez, Vladlen Koltun, and Alexey Dosovitskiy. On offline evaluation of vision-based driving models. In Proceedings of the European Conference on Computer Vision (ECCV), pages 236-251, 2018.
Qiwen Cui and Lin F Yang. Is plug-in solver sample-efficient for feature-based reinforcement learning? In Advances in neural information processing systems, 2020.
Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill. Policy certificates: Towards accountable reinforcement learning. In International Conference on Machine Learning, pages 1507-1516. PMLR, 2019.
Yaqi Duan, Zeyu Jia, and Mengdi Wang. Minimax-optimal off-policy evaluation with linear function approximation. In International Conference Machine Learning, pages 6334-8342, 2020.
Yonathan Efroni, Nadav Merlis, Mohammad Ghavamzadeh, and Shie Mannor. Tight regret bounds for model-based reinforcement learning with greedy policies. In Advances in Neural Information Processing Systems, 2019.
Yanjun Han, Jiantao Jiao, and Tsachy Weissman. Minimax estimation of discrete distributions under 4 loss. IEEE Transactions on Information Theory, 61(11):6343-633 2015.
Botao Hao, Yaqi Duan, Tor Lattimore, Csaba Szepesvári, and Mengdi Wang. Sparse feature selection makes batch reinforcement learning more sample efficient. arXiv preprint arXiv:2011.04019, 2020.
Yichun Hu, Nathan Kallus, and Masatoshi Uehara. Fast rates for the regret of offline reinforcement learning, arXiv preprint arXiv:2102.00479, 2021.

---

Thomas Jaksch, Ronald Ortner. and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(4). 2010.
Nan Jiang. Notes on tabular methods. 2018.
Nan Jiang and Lihong Li. Doubly robust off- policy value evaluation for reinforcement learning. In Proceedings of the 33rd International Conference on International Conference on Machine Learning- Volume 48, pages 652-661. JMLR. org, 2016.
Chi Jin, Zeyuan Allen- Sebastien Bubeck, and Michael Jordan. Is q-learning provably efficient? In Advances in Neural Information Processing Systems, pages 4863-4873, 2018
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In International Conference on Machine Learning, pages 1870-4879
PMLR, 2020a.
Chi Jin, Zhuoran Yang, Zhaoran Wang. and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143 PMLR, 2020b.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline ri? Interna- tional Conference on Machine Learning, 2020c.
Nathan Kallus and Masatoshi Uchara. Intrinsically efficient, stable, and bounded off off-policy evaluation for reinforcement learning. In Advances in Neural Information Processing Systems, pages 3325- 3334, 2019.
Nathan Kallus and Masatoshi Uehara. Double reinforcement learning for efficient off-policy eval- uation in markov decision processes. In International Conference on Machine Learning, pages 1932-1931, 2020.
Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Edouard Leurent, and Michal Valko. Adaptive reward-free exploration. arXiv preprint arXiv:2006.06294 2020.
Rahul Kidambi, Aravind Rajeswaran, Praneeth Netrapalli, and Thorsten Joachims, Morel: Model- based offline reinforcement learning. Advances in neural information processing systems, 2020.
Sascha Lange, Thomas Gabel, and Martin Riedmiller. Batch reinforcement learning. In Reinforcement learning, pages 45-73. Springer, 2012.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Hoang Le, Cameron Voloshin, and Yisong Yue. Batch policy learning under constraints. In Interna- tional Conference on Machine Learning, pages 3703-3712, 2019.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643 2020.
Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Breaking the sample size barrier in model-based reinforcement learning with generative model. Advances in Neural Information Processing Systems, 33, 2020.
Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou, Breaking the curse of horizon: Infinite- horizon off- off-policy estimation. Advances in Neural Information Processing Systems, pages 5361-5371, 2018.
Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin. A sharp analysis of model- reinforcement learning with self-play. arXiv preprint S.V::20100016044 2020a.
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Off-policy policy gradient with state distribution correction. In Uncertainty in Artificial Intelligence, 2019.
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Provably good batch reinforce- ment learning without great exploration. Advances neural information processing systems, 2020b.
12

---

Ying Liu, Brent Logan, Ning Liu, Zhiyuan Xu, Jian Tang, and Yangzhi Wang. Deep reinforcement learning for dynamic treatment regimes on medical registry data. In 2017 IEEE International Conference on Healthcare Informatics (ICHI), pages 380-385. IEFE, 2017.
Shie Mannor and John N Tsitsiklis. The sample complexity of exploration in the multi-armed bandit problem. Journal of Machine Learning Research, 5(Jun):623-648, 2004.
Pierre Menard, Omar Darwiche Domingues, Anders Jonsson, Emilie Kaufmann, Edouard Leurent, and Michal Valko. Fast active learning for pure exploration in reinforcement learning. arXiv preprint ar 1rXvv22007.13442, 2020.
Rémi Munos. Error bounds for approximate policy iteration. In International Conference on Machine Learning, pages 560-567, 2003.
Ofir Nachum, Yinlam Chow, Bo Dai. and Lihong Li. Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections. arXiv preprint PrXiv:1906.04733. 2019.
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline rein- forcement learning and imitation learning: tale pessimism. arXiv preprint arXiv:2 12021, 2021.
Tongzheng Ren, Jialian Li, Bo Dai, Simon S Du, and Sujay Sanghavi. Nearly horizon-free offline reinforcement learning. Advances in neural information processing systems, 2021.
Shai Shalev- Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. The Journal of Machine Learning Research, 11:2635 2670, 2010.
Karthik Sridharan. A gentle introduction to concentration inequalities. Dept. Comput. Sci., Coreel Univ, Tech. Rep, 2002.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Csaba Szepesvári and Rémi Munos. Finite time bounds for sampling based fitted value iteration. In Proceedings of the 22nd international conference on Machine learning, pages 880-887, 2005.
Joel Tropp et al. Freedman's ' incquality for matrix martingales. Electronic Communications in Probability, 16:262-270, 2011.
Masatoshi Uchara and Nan Jiang. Minimax weight and g-function learning for off-policy evaluation. arXiv preprint arviv: 1910. /2809, 2019.
Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 2013.
Ruosong Wang, Simon S Du, Lin F Yang, and Ruslan Salakhutdinov. On reward-free reinforcement learning with linear function approximation. arXiv preprint arXiv:2006. /274, 2020.
Ruosong Wang, Dean P Foster, and Sham M Kakade. What are the statistical limits of offline rl with linear function approximation? International Conference on Machine Learning, 2021.
Tengyang Xie and Nan Jiang. Q approximation schemes for batch reinforcement learning: A theoretical comparison. In Uncertainty in Artificial Intelligence, pages 550-559, 2020.
Tengyang Xie and Nan Jiang. Batch value-function approximation with only realizability. Interna- fional Conference on Machine Learning, 2021.
Tengyang Xie, Yifei Ma, and Yu-Xiang Wang. Towards optimal off-policy evaluation for rein- forcement learning with marginalized importance sampling. In Advances in Neural Information Processing Systems, pages 9668-9678, 2019.
Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pages 6995-7004. PMLR, 2019.
Ming Yin and Yu-Xiang Wang. Asymptotically efficient off- off-policy evaluation for tabular rein- forcement learning. In International Conference on Artificial Intelligence and Statisties, pages 3948-3958 PMLR. 2020.
13

---

Ming Yin and Yu-Xiang Wang. Towards eestance-optimat offline reinforcement learning with pessimism. Advances neural information processing systems, 2021.
Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal provable uniform convergence offline policy evaluation for reinforcement learning. In International Conference Artificial Intelligence and Statistics, pages 1567-1575. PMLR, 2021a.
Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal offline reinforcement learning via double variance reduction. Advances in neural information processing systems, 2021b.
Tianhe Yu, Garrett Thomas, Lantao Yu, Stefano Ermon, James Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma. Mopo: Model-based offline policy optimization. arXiv preprint arXiv:2005.13239, 2020.
Andrea Zanette. Exponential lower bounds for batch reinforcement learning: Batch can be exponentially harder than online rl. International Conference on Machine Learning, 2021.
Kaiqing Zhang. Sham M Kakade, Tamer Başar, and Lin F Yang. Model-based multi-agent rl in zero-sum markov games with opar-optimal sample complexity. arXiv preprint arXiv:2007.07461, 2020a.
Shangtong Zhang. Yi Wan, Richard Sutton, and Shimon Whiteson. Average-reward off-policy policy evaluation with function approximation. arXiv preprint arXiv:2101.02800 2021a.
Xuezhou Zhang, Adish Singla, et al. Task-agnostic exploration in reinforcement learning. Advances in Neural Information Processing Systems, 2020b.
Zihan Zhang, Simon S Du, and Xiangyang Nearly minimax optimal reward-free reinforcement learning. arXiv preprint arXiv:2010.05901, 2020c.
Zihan Zhang, Xiangyang Ji. and Simon S Du. Is reinforcement learning more difficult than bandits? a ncar-optimal algorithm escaping the curse of horizon. Conference of Learning Theory, 2021b.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. arXiv preprint arXiv:2012.08507, 2020.
14


Reviews:
[{"review_id": "J7eBA1FqWJi", "reviewer": "Reviewer_LF7M", "summary": "In this paper the authors provide uniform convergence results for offline policy evaluation, a minimax lower bound for global uniform OPE and an upper bound for local uniform OPE, with a new design analysis tool called singleton absorbing MDP. Besides, the authors generalize the results to new settings, including offline task-agnostic and offline reward-free rl. ", "questions": "", "limitations": "", "rating": 7, "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": "Originality: The results presented in the paper is new and tighter than the prior works (Yin et.al 2021), and the proving idea of using singleton-absorbing MDP technique is novel.  Also, the new settings proposed in this paper (offline task-agnostic and reward-free rl ) are interesting. \n\nQuality & Clarity: Overall the paper is well-written and results are well-presented. The visualizations of singleton absorbing mdp in the appendix are really nice and provide intuitions for understanding. \n\nSignificance: To me this is a nice theoretical paper and the paper makes contributions to the theoretical offline rl community. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I have two questions regarding the offline new settings presented in this paper:\n\n1. For the offline task-agnostic learning settings, if we using a simple union bound over the K tasks, can we get similar results?\n\n2. For the Offline Reward-free Learning, why this is an interesting settings and what we can benefit if we consider this setting? ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "C7uCfs3d82", "reviewer": "Reviewer_smXo", "summary": "This paper considers uniform convergence in model-based off-policy evaluation and learning in time-homogeneous setting, and provide sharp error bound in different scenarios.", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "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": "The authors considers uniform convergence in model-based offline reinforcement learning, and generalize the results to two slightly different setting, termed as task-agnostic and reward-free reinforcement learning. Central to the analysis is an absorbing MDP technique to decouple the statistical dependency on the empirical and the terms obtained from the empirical model, which is a generalization from the infinite horizon case and eventually lead to a sharp result on the leading term. The results are clearly presented. One minor issue is that, the higher order term are not very satisfactory, especially the results in Theorem 5.6, that need samples proportion to the number of states in linear MDP with anchor points, which should be avoided in the setting with function approximation (as we want to deal with the large state space with function approximation).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have discussed them properly.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "3UvFTACWPFp", "reviewer": "Reviewer_Rbai", "summary": "This paper studies uniform off-policy evaluation in the episodic setting. In particular, the authors consider a stationary episodic setting. The goal is to evaluate the value function corresponding to a given policy, up to some given accuracy, uniformly among all the policies. The idea is that a uniform off-policy evaluation can be used for off-policy learning directly, due to the equation (1).\nThe authors first characterize a minimax lower bound for global uniform OPE, and they show that this lower bound is proportional to the cardinality of the state space. Next they characterize a local uniform upper bound for plug-in estimator for OPE. \nNext, the authors consider offline task-agnostic and offline reward-free learning. They provide the sample complexity of model based methods for these tasks, and they show that these bounds are optimal.", "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": "- My main concern about this paper is on the relation between OPE and off-policy learning. The authors claim that global OPE can be directly translated to off-policy learning by an exhaustive search over space of all the policies. However, Search over space of all the policies is exponentially expensive in the cardinality of state and action space. Am I missing something here?\n- Typo: Line 284: supports our design", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Lack of experimental results.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "0k6fY9dzwXG", "reviewer": "Reviewer_rLZC", "summary": "This work studies uniform convergence for offline policy evaluation (OPE) with model-based methods for episodic MDP. Particularly, uniform convergence for all near-empirically optimal policies is established.", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "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": "The motivation for considering uniform OPE is insufficient, since it is not suitable to studying offline learning. The bound established based on (local) uniform OPE is too loose compared with existing results for offline learning (both model based approach and model free approach, also known as asynchronous Q-learning). Hence, I think this work is of limited importance. In addition, the proof is based on Agarwal et al. 2020. It is not evident to me what new challenges are in the proof. \n\nA. Agarwal, S. Kakade, and L. F. Yang. Model-based reinforcement learning with a generative model is minimax optimal. Conference on Learning Theory, 2020.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the uniform UPE problem in the offline RL setting with both upper and lower bound. Most of the reviewers believe the paper is well-written. There is one major concern about the epsilon range. The current results give the bound for eps<1/sqrt{S}. The paper would be much stronger if results about eps>1/sqrt{S} is also provided. 
Decision: Accept (Poster)