Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settings
Year: 2021

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Π |Q − Q̂| < is a stronger measure than the point-wise OPE and ensures offline learning when Π contains all policies (the global class). In this paper, we establish an Ω(HS/dm ) 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 to all near-empirically optimal policies for the MDPs with stationary transition. Here dm is the minimal marginal state-action probability. Critically, the highlight in achieving the optimal rate Õ(H/dm ) is our design of 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 Õ(H log(K)/dm ) (K is the number of tasks) and Õ(HS/dm ) respectively. These results provide a unified solution for simultaneously solving different offline RL problems.

heading: 1 Introduction
text: Offline reinforcement learning (offline RL) targets at learning a reward-maximizing policy in an unknown Markov Decision Process (MDP) using a static data generated by running a behavior policy [Lange et al., 2012, Levine et al., 2020]. This framework is widely applicable in applications where online exploration is demanding but historical data are plentiful. Examples include medicine [Liu et al., 2017] (safety concerns limit the applicability of unproven treatments but electronic records are abundant) and autonomous driving [Codevilla et 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 a 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 Uehara, 2020, 2019, Uehara and Jiang, 2019, Nachum et al., 2019, Xie et al., 2019, Yin and Wang, 2020, Duan et al., 2020, Wang et al., 2021, Zhang et al., 2021a] and offline (policy) learning which intends to output a near-optimal policy [Chen and Jiang, 2019, Le et al., 2019, Xie and Jiang, 2021, 2020, Liu et al., 2020b, Hao et al., 2020, Zanette, 2021, Jin et al., 2020c, Hu et al., 2021, Yin et al., 2021b, Rashidinejad et 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 (NeurIPS 2021).
given a policy class Π and offline data with n episodes, uniform OPE seeks to coming up with OPE estimators V̂ π1 and Q̂ π 1 satisfy supπ∈Π ||Q̂π1 −Qπ1 ||∞ < . The task is to achieve this with the optimal episode complexity: the “minimal” number of episodes n needed as a function of , failure probability δ, the parameters of the MDP as well as the behavior policy µ 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-Shwartz et al., 2010]. In offline RL, the natural counterpart is the empirical optimal policy π̂? := argmaxπ V̂ π 1 and with uniform OPE it further ensures π̂? is a near-optimal policy for the offline learning via:
0 ≤ Qπ ? 1 −Qπ̂ ? 1 = Q π? 1 − Q̂π ? 1 + Q̂ π? 1 − Q̂π̂ ? 1 + Q̂ π̂? 1 −Qπ̂ ? 1 ≤ 2 sup π |Qπ1 − Q̂π1 |. (1)
On the policy evaluation side, there is often a need to evaluate the performance of a data-dependent policy. Uniform OPE suffices for this purpose since it will allow us to evaluate policies selected by safe-policy improvements, proximal policy optimization, UCB-style exploration-bonus as well as any 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 Πg (contains all (deterministic) policies) and local policy class Πl (contains policies near the empirical optimal one, see Section 2.1). We ask the following question:
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 Ω(H2S/dm
2)1 for the family of model-based approach and the local uniform OPE can achieve Õ(H2/dm
2) 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-agnostic learning and offline reward-free learning. See Section 1.2.

heading: 1.1 Related works
text: Offline reinforcement learning.2 Information-theoretical considerations for offline RL are first proposed 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,b].
For the finite horizon case, Yin et al. [2021a] first achieves Õ(H3/dm 2) complexity under nonstationary transition but their results cannot further improve in the stationary setting. Recently, Yin et al. [2021b] designs the offline variance reduction algorithm for achieving the optimal Õ(H2/dm 2) rate. Their result is 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, Ren et al. [2021] considers the horizon-free setting but does not provide uniform convergence guarantee.
Model-based approaches with minimaxity. It is known model-based methods are minimax-optimal for online RL with regret Õ( √ HSAT ) (e.g. Azar et al. [2017], Efroni et al. [2019]). In the generative model setting, Agarwal et al. [2020] shows model-based approach is still minimax optimal Õ((1− γ)−3SA/ 2) 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 et al., 2020a] and linear MDPs [Cui and Yang, 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 Õ(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
1Here dm is the minimal marginal state-action occupancy, see Assumption 2.4. 2We only provide a short discussion of the most related works due to the space constraint. A detailed
discussion can be found in Appendix A.
reward function. Later, Kaufmann et al. [2020], Menard et al. [2020] establish the Õ(H3S2A/ 2) complexity and Zhang et al. [2020c] further tightens the dependence to Õ(H2S2A/ 2). Recently, Zhang et al. [2020b] proposes the task-agnostic setting where one needs to use exploration data to simultaneously learn K tasks and proves an upper bound Õ(H5SA log(K)/ 2). However, although these settings remain critical in the offline regime, no statistical result has been derived so far.

heading: 1.2 Our contribution
text: Optimal local uniform OPE. First and foremost, we derive the Õ(H2/dm 2) optimal episode complexity for local uniform OPE (Theorem 4.1) 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] (Õ(H3/dm 2)) non-trivially through our new singleton-absorbing MDP technique.
Information-theoretical characterization of the global uniform OPE. We characterize the statistical limit for the global uniform convergence by proving a minimax lower bound Ω(H2S/dm 2) (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 a 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 Õ(H2 log(K)/dm 2) (Theorem 5.3) and Õ(H2S/dm 2) (Theorem 5.4) complexities for offline task-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 P̂s,a and V̂ , Agarwal et al. [2020] uses a s-absorbing MDP V̂s (in lieu of V̂ ) of each state for the independence. To control the error propagation between V̂s and V̂ , they use the -net covering such that the value of V̂s traverse the evenly-spaced grids in [0, (1− γ)−1]. However, when applied to finite horizon case, the complexity increases as there are H different quantities (V1, ..., VH ) and the -nets need to cover the H-dimensional space [0, H]H . This result in a exponential-H covering number and the metric entropy blows up by a factor H , which yields suboptimal result. In contrast, the singleton-absorbing MDP technique designs a single absorbing MDP that can also control the error propagation sufficiently well. This sharp analysis tool negates the conjecture of Cui 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-agnostic and offline reward-free learning into the identical learning pattern. Considering these tasks were originally proposed in the online regime under different contexts, such a unified view from the model-based perspective offers a new angle for understanding offline RL.

heading: 2 Problem setup
text: Episodic stationary reinforcement learning. A finite-horizon Markov Decision Process (MDP) is denoted by a tuple M = (S,A, P, r,H, d1), where S and A are finite state action spaces with S := |S|, A := |A|. A stationary (time-invariant) transition kernel has the form P : S ×A× S 7→ [0, 1] with P (s′|s, a) representing the probability transition from state s, action a to next state s′. Besides, r : S × A 7→ R is the expected reward function and given (s, a) which satisfies 0 ≤ r ≤ 1 and assumed known. d1 is the initial state distribution and H is the horizon. At time t, a policy π = (π1, ..., πH) assigns each state s ∈ S a probability distribution πt(s) over
∗ K is the number of tasks for Task-agnostic setting and βµ, C and 1/dm are data coverage parameters that measure the state-action dependence and are qualitative similar under their respective assumptions.
actions. For a policy π, a random trajectory s1, a1, r1, . . . , sH , aH , rH , sH+1 is generated as follows: s1 ∼ d1, at ∼ π(·|st), rt = r(st, at), st+1 ∼ P (·|st, at),∀t ∈ [H]. For any policy π and any h ∈ [H], value function V πh (·) ∈ RS and Q-value functionQπh(·, ·) ∈ RS×A are defined as: V πh (s) = Eπ[ ∑H t=h rt|sh = s], Q π h(s, a) = Eπ[ ∑H t=h rt|sh, ah = s, a], ∀s, a ∈ S,A.
The goal of RL is to find a policy π? such that vπ := Eπ [∑H t=1 rt ]
is maximized, which is equivalent to simultaneously maximize V π1 (s) (or Q π 1 (s, a)) for all s (or s, a) [Sutton and Barto, 2018]. Therefore,
for a targeted accuracy > 0 it suffices to find a policy πalg such that ∥∥Q?1 −Qπalg1 ∥∥∞ ≤ . We denote V πh , Q π h as column vectors and Ps,a as the row vector. In particular, we denote the average marginal
state-action occupancy dπ(s, a) as: dπ(s, a) := 1H ∑H t=1 P[st = s|s1 ∼ d1, π] · πt(a|s).
Offline setting. The offline RL assumes that episodes D = {( s (i) t , a (i) t , r (i) t , s (i) t+1 )}t∈[H] i∈[n]
are rolling from some behavior policy µ a priori. In particular, we do not assume the knowledge of µ.
Model-based RL. We focus our attention on the model-based methods, which has witnessed numerous successes and is one of the most critical components of theoretical RL as a whole (as reviewed in Section 1.1). 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-based approaches in general (e.g. Jaksch et al. [2010], Ayoub et al. [2020], Kidambi et al. [2020]) follow the procedure of modeling the full MDP M = (S,A, P, r,H, d1) instead of only the transition P . Nevertheless, we (by convention) assume the mean reward function is known and the initial state distribution d1 will not affect the choice of optimal policy π?. Thus, Definition 2.1 suffices for our purposes.

heading: 2.1 Uniform convergence in offline RL
text: We study offline RL from the uniform OPE perspective. Concretely, uniform OPE extends the point-wise (fixed target policy) OPE to a family of policies Π. The goal is to construct estimator Q̂π1 such that supπ∈Π ∥∥∥Qπ1 − Q̂π1∥∥∥ < , which automatically ensures point-wise OPE for any π ∈ Π. More importantly, uniform OPE directly implies offline learning when Π contains optimal policies. As explained in Section 1, let π̂? := argmaxπ V̂ π 1 be the empirical optimal policy for some OPE estimator v̂π , then by (1) π̂? 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 Πg consists of all the non-stationary (deterministic) policies.
It is well-known [Sutton and Barto, 2018] there exists at least one (deterministic) optimal policy, therefore Πg is sufficiently rich for evaluating algorithms that aim at learning the optimal policy. Definition 2.3 (The local policy class). Given empirical MDP M̂ and V̂ πh is the value under M̂ . Let π̂? := argmaxπ V̂ π 1 be the empirical optimal policy, then the local policy class Πl is defined as:
Πl := { π : s.t. ∥∥∥V̂ πh − V̂ π̂?h ∥∥∥ ∞ ≤ opt , ∀h ∈ [H] } where opt ≥ 0 is a parameter.
In above M̂ uses P̂ in lieu of P where P̂ (s′|s, a) = ns′,s,ans,a if ns,a > 0 and 1/S otherwise. 3 This class
characterizes policies in the neighborhood of empirical optimal policy. Given P̂ , it is efficient to obtain π̂? using Value / Policy Iteration, therefore it is more practical to consider the neighborhood of π̂? (instead of π?) since practitioners can use data D to really check Πl whenever needed. Next we present the regularity assumption required for uniform convergence OPE problem. Assumption 2.4 (Exploration requirement). Logging policy µ obeys that mins dµ(s) > 0, for any state s that is “accessible”. Moreover, we define the quantity dm := mins,a{dµ(s, a) : dµ(s, a) > 0} (recall dµ(s, a) in Section 2) to be the minimal average marginal state-action probability.
State s is “accessible” means there exists a policy π so that dπ(s) > 0. If for any policy π we always have dπ(s) = 0, then state s can never be visited in the given MDP. Note this is weaker than Yin et al. [2021a] since dµ(s) is the average version of dµt (s). Assumption 2.4 is the minimal assumption needed for the consistency of uniform OPE task and is qualitatively similar to the concentrability assumption [Munos, 2003]. This assumption can be potentially relaxed for pure offline learning problems, e.g. Liu et al. [2019], Rashidinejad et al. [2021], where they only require dµ(s)(dµ(s, a)) > 0 for any state s (s, a) satisfies dπ ? (s)(dπ ? (s, a)) > 0.

heading: 3 Statistical Hardness for Model-based Global Uniform OPE
text: From (1) and Definition 2.2, it is clear the global uniform OPE implies offline RL, therefore it 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̃(H3S/dm 2) upper bound and Ω(H3/dm 2) lower bound for global uniform OPE, but it is unclear whether the additional S is essential. We answer the question affirmatively by providing a tight lower bound result with a concise proof to show no model-based algorithm can surpass Ω(S/dm 2) information-theoretical limit. Theorem 3.1 (Minimax lower bound for global uniform OPE). Let dm be a parameter such that 0 < dm ≤ 1SA . Let the problem class beMdm := {(µ,M) | mint,st,at d µ t (st, at) ≥ dm}. Then there exists universal constants c, C, p > 0 such that: for any n ≥ cS/dm · log(SAp),
inf Q̂1,mb sup Mdm
Pµ,M  sup π∈Πg ∥∥∥Q̂π1,mb −Qπ1∥∥∥∞ ≥ C √ H2S ndm  ≥ p, where Q̂1,mb is the output of any model-based algorithm and Πg is defined in Definition 2.2.
By setting := √
H2S ndm , Theorem 3.1 establishes the global uniform convergence lower bound
of Ω(H2S/dm 2) over model-based methods, which builds the hard statistical threshold between the global uniform OPE and the local uniform OPE tasks by a factor of S since the local case has achievable Õ(1/dm 2) rate on the dependence for state-actions. This result also reveals the global uniform convergence bound in Yin et al. [2021a] (Õ(H3S/dm 2)) is essentially minimax rate-optimal for their non-stationary setting4 and complements the story on the optimality behavior for global uniform OPE. Moreover, from the generative model view the lower bound degenerates to S/dm
2 ≈ Θ(S2A/ 2) which is linear in the model size S2A. 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.
Proof Sketch. We only explain the case where H = 2 in this proof sketch. Our proof relies on the following novel reduction to l1 density estimation
sup π∈Πg ∥∥∥Q̂π1 −Qπ1∥∥∥∞ ≥ sups,a 12 ∥∥∥P̂ (·|s, a)− P (·|s, a)∥∥∥ 1
3Here ns,a is the number of pair (s, a) being visited among n episodes. ns′,s,a is defined similarly. 4To be rigorous, we ramark that it is rate-optimal since for the non-stationary setting the dependence for
horizon is higher by a factor H .
and leverages the Minimax rate for estimating discrete distribution under l1 loss is O( √ S/ns,a)
[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πH+1 = 0 for any π, then by Bellman equation Q̂πh = rh + P̂
πh+1Q̂πh+1, ∀h ∈ [H]. In particular, Q̂πH+1 = QπH+1 = 0, and this implies Q̂πH = Q π H = rH . Now, again by definition of Bellman equation Q̂ π H−1 = rH−1 + P̂ πH Q̂πH = rH−1 + P̂ πH rH and QπH−1 = rH−1 + P πH rH , therefore (recall H = 2 and note rH ∈ RS·A, rπHH ∈ RS )
sup π∈Πg ∥∥∥Q̂πH−1 −QπH−1∥∥∥∞ = supπ∈Πg ∥∥∥(P̂πH − PπH) rH∥∥∥ ∞ = sup π∈Πg ∥∥∥(P̂ − P) rπHH ∥∥∥∞ ≈ sup r∈{0,1}S ∥∥∥(P̂ − P) r∥∥∥ ∞ ≥ sup s,a 1 2 ∥∥∥P̂ (·|s, a)− P (·|s, a)∥∥∥ 1 ≥ O( √ S/ns,a);
Lastly, using exponential tail bound to obtain O( √ S/ns,a) & O( √ S/ndm) with high probability. See Appendix C for how to prove the result for the general H .

heading: 4 Optimal local uniform OPE via model-based plug-in method
text: 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 state-action size Õ(1/dm) in the policy evaluation. Yin et al. [2021a] Theorem 3.7 first obtains the Õ(H3/dm 2) local uniform convergence for Πl (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 Õ(H2/dm
2). To this end, we design the new singleton-absorbing MDP to handle the challenge in the stationary transition setting, which uses the absorbing MDP with one single H-dimensional reference point and is our major technical contribution. The singleton-absorbing 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.5

heading: 4.1 Model-based Offline Plug-in Estimator
text: Recall ns,a := ∑n i=1 ∑H h=1 1[s (i) h , a (i) h = s, a] be the total counts that visit (s, a) pair, then the model-based offline plug-in estimator constructs estimator P̂ as: P̂ (s′|s, a) =∑n i=1 ∑H h=1 1[(s (i) h+1,a (i) h ,s (i) h )=(s ′,s,a)]
ns,a , if ns,a > 0 and P̂ (s′|s, a) = 1S if ns,a = 0. As a conse-
quence, the estimators Q̂πh, V̂ π h are computed as: Q̂ π h = r + P̂ πh+1Q̂πh+1 = r + P̂ V̂ π h+1, with the
initial distribution d̂1(s) = ns/n. Under the above setting, we can define the empirical Bellman optimality equations (as well as the population version for completeness) as ∀s ∈ S, h ∈ [H]:
V ?h (s) = max a
{ r(s, a) + P (·|s, a)V ?h+1 } , V̂ ?h (s) = max
a
{ r(s, a) + P̂ (·|s, a)V̂ ?h+1 } .
Now we can state our local uniform OPE result with this construction.

heading: 4.2 Main results for local uniform OPE and offline learning
text: Recall π̂? := argmaxπ V̂ π 1 is the empirical optimal policy and the local policy class Πl := {π : s.t. ∥∥∥V̂ πh − V̂ π̂?h ∥∥∥∞ ≤ opt ,∀h ∈ [H]}.
5See their Section 7, first bullet point for a discussion.
Theorem 4.1 (optimal local uniform OPE). Let opt ≤ √ H/S and denote ι = log(HSA/δ). For any δ ∈ [0, 1], there exists universal constants c, C such that when n > cH · log(HSA/δ)/dm, with probability 1− δ,
sup π∈Πl ∥∥∥Q̂π1 −Qπ1∥∥∥ ∞ ≤ C [√ H2ι ndm + H2.5S0.5ι ndm ] .
Theorem 4.1 establishes the Õ(H2/dm 2) complexity bound and directly implies the upper bound for supπ∈Πl ||V̂ π 1 − V π1 ||∞ with the same rate. This result improves the local uniform convergence rate Õ(H3/dm 2) in Yin et al. [2021a] (Theorem 3.7) by a 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 Πl) is more flexible than characterizing the distance between policies themselves (e.g. via total variation). This is because: if 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 Πl is generic and conceptually reflects the fundamental principle of RL: as long as two policies yield the same value, they are considered “equally good”, no matter how different they are.6
Most importantly, Theorem 4.1 guarantees near-minimax optimal offline learning: Corollary 4.2 (optimal offline learning). If opt ≤ √ H/S and that supt ||V̂ π̂t − V̂ π̂ ?
t ||∞ ≤ opt , when n > O(H · ι/dm), then with probability 1− δ, element-wisely,
V ?1 − V π̂1 ≤ C [√ H2ι
ndm + H2.5S0.5ι ndm
] 1 + opt 1.
Corollary 4.2 first establishes the minimax rate for offline learning for any policy π̂ with the measurable gap opt ≤ √ H/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 (Õ √ H2/ndm + opt )-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 empirical MDP for planning and, on the contrary, Yin et al. [2021b] uses data-splitting (split data into mini-batches and only apply each mini-batch at 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. [2021b], our Corollary 4.2 is near minimax optimal. Theorem 4.3 (Theorem 4.2. Yin et al. [2021b]). LetMdm be the same as Theorem 3.1. There exists universal constants c1, c2, c, p (with H,S,A ≥ c1 and 0 < < c2) such that when n ≤ cH2/dm 2,7
inf V πalg 1 sup (µ,M)∈Mdm
Pµ,M ( ||V ?1 − V πalg 1 ||∞ ≥ ) ≥ p.
For the rest of the section, we explain the proving ideas by introducing the singleton-absorbing MDP technique and the full proofs of Theorem 4.1, Corollary 4.2 can be found in Appendix B, D.

heading: 4.3 Singleton absorbing MDP for finite horizon MDP
text: For the ease of illustration, we explain our idea via bounding ||Q̂π̂?h − Qπ̂ ? h ||∞ (instead of supπ∈Πl ||Q̂ π 1 − Qπ1 ||∞) and choose related quantity π̂? (instead of π̂) and V̂ ?h (instead of V̂ π̂h ) to discuss. Essentially, the key challenge in obtaining the optimal dependence in stationary setting is the need to decouple the dependence between P − P̂ and V̂ ?h as we aggregate all data for constructing both P̂ and V̂ ?h . This issue is not encountered in the non-stationary setting in general due to the flexibility to estimate different transition Pt at each time [Yin et al., 2021a] and P̂t and V̂ ?t+1 preserve conditional independence. However, when confined to stationary case, their complex Õ(H3/dm 2) becomes suboptimal. Moreover, the direct use of s-absorbing MDP in Agarwal et al. [2020] does
6We 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.
7The original Theorem uses v? but we use V ?1 here. It does not matter since we can manually add a default state at the beginning of the MDP and obtain the result for our version.
not yield tight bounds for the finite horizon stationary setting, as it requires s-absorbing MDPs with H-dimensional fine-grid cover to make sure V̂ ?h is close to one of the elements in the cover (which has size ≈ HH and it is not optimal Cui and Yang [2020]). We overcome this hurdle by choosing only one delicate absorbing MDP to approximate V̂ ?h 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 et 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 as follows: for a fixed state s and a sequence {ut}Ht=1, MDP Ms,{ut}Ht=1 is identical to M for all states except s, and state s is absorbing in the sense PM
s,{ut}Ht=1 (s|s, a) = 1 for all a, and
the instantaneous reward at time t is rt(s, a) = ut for all a ∈ A, t ∈ [H]. For convenience, we use the shorthand notation V π{s,ut} to denote V π s,M
s,{ut}Ht=1 and similarly for Qt, r and transition P . Also,
V ?{s,ut} (Q ? {s,ut}) is the optimal value under Ms,{ut}Ht=1 .
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. V ?t (s)− V ?t+1(s) ≥ 0, ∀s ∈ S, t ∈ [H]. Lemma 4.5. Fix a state s. If we choose u?t := V ?t (s)− V ?t+1(s), then we have the following vector form equation
V ?h,{s,u?t } = V ? h,M ∀h ∈ [H].
Similarly, if we choose û?t := V̂ ? t (s)− V̂ ?t+1(s), then V̂ ?h,{s,û?t } = V̂ ? h,M , ∀h ∈ [H].
The proofs are deferred to Appendix B. Note by Lemma 4.4 the assignment of u?t (:= rt,{s,u?t }) is well-defined. Lemma 4.5 is crucial since, under the specification of u?t , the optimal value in Ms,{u?t }Ht=1 is identical to the optimal value in original M . Based on these, we can define the following: Definition 4.6 (Singleton-absorbing MDP). For each state s, the singleton-absorbing MDP is chosen to be Ms,{u?t }Ht=1 , where u ? t := V ? t (s)− V ?t+1(s) for all t ∈ [H].
Using Definition 4.6, for each (s, a) row the term (P̂s,a − Ps,a)V̂ ?h can be substituted by (P̂s,a − Ps,a)V̂
? h,{s,u?t } , where P̂s,a and V̂ ?h,{s,u?t } are independent by construction and Bernstein concentration
applies. Furthermore, by the selection of u?t , we can control the error of ||V̂ ?h − V̂ ?h,{s,u?t }||∞ to have rate O( √
1 n ) which forces the term (P̂s,a − Ps,a)(V̂ ? h − V̂ ?h,{s,u?t }) to have higher order error. These
are the critical building blocks for bounding ||Q̂π̂?h −Qπ̂ ? h ||∞.
Indeed, by Bellman equations we have the decomposition: Q̂π̂ ? h − Qπ̂ ? h = . . . =∑H t=h Γ π̂? h+1:t ( P̂ − P ) V̂ ?t+1, where Γπh+1:t = ∏t i=h+1 P
πi is multi-step state-action transition and Γh+1:h := I . Then for each (s, a) row
(P̂s,a − Ps,a)V̂ ?h = (P̂s,a − Ps,a)(V̂ ?h − V̂ ?h,{s,u?t }) + (P̂s,a − Ps,a)V̂ ? h,{s,u?t }
.||P̂s,a − Ps,a||1||V̂ ?h − V̂ ?h,{s,u?t }||∞ + √√√√Vars,a(V̂ ?h,{s,u?t }) ns,a . √ S ns,a ∥∥∥V̂ ?h − V̂ ?h,{s,u?t }∥∥∥∞ + √ Vars,a(V̂ ?h ) ns,a (?) (2) where (?) is the place where the traditional technique uses the union bound over their exponential large -net and we do not have it! Next, by Lemma 4.5 and Lemma B.2 in Appendix
||V̂ ?h − V̂ ?h,{s,u?t }||∞ = ||V̂ ? h,{s,û?t } − V̂ ? h,{s,u?t }||∞ ≤ H maxt |û ? t − u?t | ≤ 2H max t |V̂ ?t − V ?t |,
by a crude bound (Lemma J.10), maxt |V̂ ?t − V ?t | . H2 √ S ns,a which makes √ 1 ns,a ||V̂ ?h −
V̂ ?h,{s,u?t } ||∞ have order 1/ns,a. Finally, to reduce the horizon dependence we apply∑H
t=h Γ π h+1:t √ Vars,a ( V πt+1 ) ≤ √ (H − h)3 for any π. This (informally) bounds Q̂π̂?h − Qπ̂ ? h by
||Q̂π̂?h −Qπ̂ ? h ||∞ . √ H3 ns,a + Poly(H,S)ns,a . Lastly, use mins,a ns,a & H · dm to finish the proof.
Remark 4.7. We emphasize the appropriate selection of Ms,{u?t }Ht=1 (M̂s,{u?t }Ht=1) is the key for achieving optimality. It guarantees two things: 1. V̂ ?h,{s,u?t } approximates V̂ ? h with sufficient accuracy
(has rate √
1/ns,a); 2. it avoids the fine-grid design with exponential union bound in the dominate term ( √
Vars,a(V̂ ?h ) log(|Us,a|/δ) N with |Us,a| to be at least H H Cui and Yang [2020].)

heading: 5 New settings: offline Task-agnostic and offline Reward-free learning
text: From Corollary 4.2, our model-based offline learning algorithm has two steps: 1. constructing offline empirical MDP M̂ using the offline dataset D = {(s(i)t , a (i) t , r(s (i) t , a (i) t ), s (i) t+1)} t∈[H] i∈[n] ; 2. performing any accurate black-box planning algorithm and returning π̂?(or π̂) as the final output. However, the only effective data (data that contains stochasticity) is D′ = {(s(i)t , a (i) t )} t∈[H] i∈[n] . 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 in mind, it is natural to ask: given only the offline exploration data D′, can we efficiently learn a set of potentially conflicting K tasks (K rewards) simultaneously? Even more, can we efficiently learn all tasks simultaneously? This brings up the following definitions.
Definition 5.1 (Offline Task-agnostic Learning). Given a offline exploration datatset D′ = {(s(i)t , a (i) t )} t∈[H] i∈[n] by µ with n episodes. Given K tasks with reward {rk} K k=1 and the corresponding K MDPs Mk = (S,A, P, rk, H, d1). Can we use D′ to output π̂1, . . . , π̂K such that P [ ∀rk, k ∈ [K],
∥∥∥V ?1,Mk − V π̂k1,Mk∥∥∥∞ ≤ ] ≥ 1− δ? Definition 5.2 (Offline Reward-free Learning). Given a offline exploration datatset D′ = {(s(i)t , a (i) t )} t∈[H] i∈[n] by µ with n episodes. For any reward r and the corresponding MDP M =
(S,A, P, r,H, d1). Can we use D′ to output π̂ such that P [ ∀r, ∥∥V ?1,M − V π̂1,M∥∥∞ ≤ ] ≥ 1− δ?
Definition 5.1 and Definition 5.2 are the offline counterparts of Zhang et al. [2020b] 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 to 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(i)t , a (i) t )} t∈[H] i∈[n] by µ. Given K tasks with reward {rk}Kk=1 and the corresponding K MDPs Mk = (S,A, P, rk, H, d1). Denote ι = log(HSA/δ). Let π̂?k := argmaxπ V̂ π 1,Mk ∀k ∈ [K], when n > O(H · [ι+ log(K)]/dm), then
with probability 1−δ, ∥∥∥V ?1,Mk − V π̂?k1,Mk∥∥∥∞ ≤ O [√ H2(ι+log(K)) ndm + H 2.5S0.5(ι+log(K)) ndm ] ∀k ∈ [K]. Theorem 5.4 (optimal offline reward-free learning). Given D′ = {(s(i)t , a (i) t )} t∈[H] i∈[n] by µ. For any reward r denote the corresponding MDP M = (S,A, P, r,H, d1). Denote ι = log(HSA/δ). Let π̂?M := argmaxπ V̂
π 1,M ∀r, when n > O(HS · ι/dm), then with probability 1 − δ,∥∥∥V ?1,M − V π̂?M1,M∥∥∥∞ ≤ O [√H2S·ιndm + H2S·ιndm ] , ∀r,M.
By a direct translation of both theorems, we have sample complexity of order Õ(H2 log(K)/dm 2) and Õ(H2S/dm 2). All the parameters have the optimal rates, see the lower bounds in Zhang et al. [2020b] and Jin et al. [2020a].8 The higher order dependence in Theorem 5.4 is 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 to these harder problems would not affect the optimal statistical efficiency of the model-based approach.
8We add a discussion in Appendix G to explain more clearly why our rates are optimal for these problems.

heading: 6 Extension to linear MDP with anchor representations
text: The principle of our Singleton absorbing MDP technique (with model-based construction) in decoupling the dependence between P̂s,a and V̂ ? is not confined to tabular MDPs and therefore it is natural to generalize such idea for the episodic stationary transition setting for other problems. As an example, we further present a sharp result for the setting of finite horizon linear MDP with anchor points. We narrate by assuming a generative oracle (that allows sampling from s′ ∼ P (·|s, a)) for the ease 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) spaces. Assume there is feature map φ : S ×A → RK (where K |S|), i.e. φ(s, a) = [φ1(s, a), . . . , φK(s, a)]. Transition P admits a linear representation: P (s′|s, a) = ∑ k∈[K] φk(s, a)ψk(s
′) where ψ1(·), . . . , ψK(·) are unknowns. We further assume there exists a set of anchor state-action pairs K such that any (s, a) can be represented as a convex combination of the anchors {(sk, ak)|k ∈ K}:
∃ {λs,ak } : φ(s, a) = ∑ k∈K λs,ak φ (sk, ak) , ∑ k∈K λs,ak = 1, λk ≥ 0, ∀k ∈ K, (s, a) ∈ (S,A).
Under the definition, denote N be the number of samples at each anchor pairs. Then we have the following (see Appendix H for the proof): Theorem 6.2 (Optimal sample complexity). Under Definition 6.1, let π̂? = argmaxπ V̂ π1 . Then if N ≥ cH2|S| log(KH/δ), we have with probability 1− δ, ||Q?1 −Qπ̂ ? 1 ||∞ ≤ Õ( √ H3/N).
Comparing to Theorem 4 of Cui and Yang [2020], Theorem 6.2 removes the additional dependence min{|S|,K,H}. In term of the total sample complexity, Theorem 6.2 gives Õ(KH3/ 2) while Cui and Yang [2020] has Õ(KH4/ 2) (see their Section 7, first bullet point). Our result again reveals the model-based method is statistically optimal for the current setting. Remark 6.3. The rate Õ(KH3/ 2) with anchor point assumption has the linear dependence on K and for the standard linear bandit [Lattimore and Szepesvári, 2020] Ω( √ d2T ) or the linear (mixture) MDP [Jin et al., 2020b, Zhou et al., 2020] Ω( √ d2H2T ) the lower bound dependence on the feature dimension d is quadratic. We believe one reason for this to happen is that anchor representations assumption is somewhat strong as it abstracts the whole state action space by only finite points (via convex combination).

heading: 7 Conclusion and Future Works
text: This work studies the uniform convergence problems for offline policy evaluation (OPE) and provides complete answers for their optimality behaviors. We achieve the optimal sample complexity for stationary-transition 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 of 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 √ HS dependence in the higher order error term and we cannot further remove it based on our current technique. Nevertheless, this is already among the best higher order results to our knowledge. In fact, most state-of-the-art works (e.g. Azar et al. [2017], Dann et al. [2019], Zhang et al. [2021b]) have additional S dependence in the higher order and Jin et al. [2018] has only extra √ S in the higher order term but it also has additional √ A (see Table 1 of Zhang et al. [2021b] for a clear reference). How to obtain optimality not only for the main term but also for the higher order error terms remains elusive for the community.
Uniform OPE and beyond. The current study of uniform OPE derives results with expression using parameter dependence and deriving instance-dependent uniform convergence result will draw a 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.

heading: Acknowledgment
text: The research is partially supported by NSF Awards #2007117 and #2003257. MY would like to thank Simon S. Du, Zihan Zhang for explaining a question in Zhang et al. [2020c]; and Tongzheng Ren for the helpful discussions.

Review summaries:
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). The 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.  Next, 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.