Nearly Horizon-Free Offline Reinforcement Learning
Year: 2022

Abstract:
We revisit offline reinforcement learning on episodic time-homogeneous Markov Decision Processes (MDP). For tabular MDP with S states and A actions, or linear MDP with anchor points and feature dimension d, given the collected K episodes data with minimum visiting probability of (anchor) state-action pairs dm, we obtain nearly horizon H-free sample complexity bounds for offline reinforcement learning when the total reward is upper bounded by 1. Specifically: • For offline policy evaluation, we obtain an Õ ⇣q 1 Kdm ⌘ error bound for the plug-in estimator, which matches the lower bound up to logarithmic factors and does not have additional dependency on poly (H,S,A, d) in higher-order term. • For offline policy optimization, we obtain an Õ ⇣q 1 Kdm + min(S,d) Kdm ⌘ suboptimality gap for the empirical optimal policy, which approaches the lower bound up to logarithmic factors and a high-order term, improving upon the best known result by [1] that has additional poly (H,S, d) factors in the main term. To the best of our knowledge, these are the first set of nearly horizon-free bounds for episodic time-homogeneous offline tabular MDP and linear MDP with anchor points. Central to our analysis is a simple yet effective recursion based method to bound a “total variance” term in the offline scenarios, which could be of individual interest.

text: ⇣q 1
Kdm
⌘ error bound for the
plug-in estimator, which matches the lower bound up to logarithmic factors and does not have additional dependency on poly (H,S,A, d) in higher-order term.
• For offline policy optimization, we obtain an Õ ⇣q 1
Kdm + min(S,d) Kdm
⌘ sub-
optimality gap for the empirical optimal policy, which approaches the lower bound up to logarithmic factors and a high-order term, improving upon the best known result by [1] that has additional poly (H,S, d) factors in the main term.
To the best of our knowledge, these are the first set of nearly horizon-free bounds for episodic time-homogeneous offline tabular MDP and linear MDP with anchor points. Central to our analysis is a simple yet effective recursion based method to bound a “total variance” term in the offline scenarios, which could be of individual interest.

heading: 1 Introduction
text: Reinforcement Learning (RL) aims to learn to make sequential decisions to maximize the long-term reward in unknown environments, and has demonstrated success in game-playing [2, 3], robotics [4], and automatic algorithm design [5]. These successes rely on being able to deploy the algorithms in a way that directly interacts with the respective environment, allowing them to improve the policies in a trial-and-error way. However, such direct interactions with real environments can be expensive or even impossible in other real-world applications, e.g., education [6], health and medicine [7, 8], conversational AI [9] and recommendation systems [10]. Instead, we are often given a collection of logged experiences generated by potentially multiple and possibly unknown policies in the past.
This lack of access to real-time interactions with an environment led to the field of offline reinforcement learning [11]. Within this, offline policy evaluation (OPE) focuses on evaluating a policy, and offline policy optimization (OPO) focuses on improving policies; both rely only upon the given fixed past experiences without any further interactions. OPE and OPO are in general notoriously difficult, as unbiased estimators of the policy value can suffer from exponentially increasing variance in terms of horizon in the worst case [12, 13].
To overcome this “curse of horizon” in OPE, [14, 15] first introduced marginalized importance sampling (MIS) based estimators. They showed that if (1) all of the logged experiences are generated
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
from the same behavior policy, and (2) the behavior policy is known, then the exponential dependency on horizon can be improved to polynomial dependency. Subsequently, [16–18] showed that the polynomial dependency could be achieved even without assumptions (1) and (2). The basic idea for these MIS-based estimators is estimating the marginal state-action density ratio between the target policy and the empirical data, so as to adjust the distribution mismatch between them. On the algorithmic side, marginal density ratio estimation can be implemented by either plug-in estimators [15, 19], temporal-difference updates [20, 21], or solving a min-max optimization [16, 17, 22, 18]. These OPE estimators can also be used as one component for OPO, resulting in the algorithms in [23–25], which also inherit the polynomial dependency on horizon.
In a different but related line of work, [26, 27] recently showed that, for the online episodic timehomogeneous tabular Markov Decision Process (MDP) that allows for the interactions with environments, the sample complexity only has poly log dependency on the horizon. This motivates us to consider the following question:
Can offline reinforcement learning escape from the polynomial dependency on the horizon?
In this paper, we provide an affirmative answer to this question. Specifically, considering the episodic time-homogeneous tabular MDP with S states, A actions and horizon H , or the linear MDP with anchor points and feature dimension d, assuming the total reward for any episode is upper bounded by 1 almost surely, we obtain the following nearly H-free bounds:
• For offline policy evaluation (OPE), we show that the plug-in estimator has a finite-sample error of eO ⇣q 1
Kdm
⌘ (Theorem 1 and 5), where K is the number of episodes and dm is the minimum
visiting probability of (anchor) state-action pairs, that matches the lower bound up to logarithmic factors. We emphasize that the bound has no additional poly (H,S,A, d) dependency in the higher order term, unlike the known results of [19, 24].
• For offline policy optimization (OPO), we show that the policy obtained by model-based planning on empirical MDP has a sub-optimality gap of eO ⇣q 1
Kdm + min{S,d} Kdm
⌘ (Theorem 3 and 6), which
matches the lower bound up to logarithmic factors and a high-order term. This also improves upon the best known result from [1] by removing additional poly (H,S, d) factors in the main term.
To the best of our knowledge, these are the first set of nearly horizon-free bounds for both OPE and OPO on time-homogeneous tabular MDP and linear MDP with anchor points. To achieve such sharp bounds, we propose a novel recursion based method to bound a “total variance” term (introduced below) that is broadly emerged in the offline reinforcement learning, which could be of individual interest.
Technique Overview. With a sequence of fairly standard steps in the literature, we can bound the error of the plug-in estimator via terms related to the square root of the “total variance” (also known as the Cramer-Rao type lower bound illustrated in [13]) qP h2[H] P s,a ⇠⇡ h (s, a)VarP (s,a) V ⇡ h+1 (s0)
where ⇠⇡ is the reaching probability, P is the transition and V ⇡ is the value function under policy ⇡. (For a more formal definition, see Section 3.). An improper bound of this term will introduce unnecessary dependency on the horizon, either in the main term or in the higher-order term. We instead bound this term with a recursive method, by observing that this “total variance” term can be approximately upper bounded by the square root of the “total variance of value square” P
h2[H] P s,a ⇠⇡ h (s, a)VarP (s,a) h V ⇡ h+1 (s0) 2i and some remaining term (see Lemma 1 and Lemma 3 for the detail). Applying this argument recursively, we can finally obtain a poly logH upper bound on the total variance, which eventually gets rid of the polynomial dependency on H .
The idea of higher order expansion has been investigated in [28, 27]. We notice that the recursion introduced in [28] was designed for the infinite horizon setting, and how to generalize their technique to finite horizon setting is still unclear. Our recursion is conceptually more similar to the recursion in [27]. However, [27] considered the online setting, where we only need to bound the error on the visited state-action pairs. For the offline setting, we need to bound the error on every state-action pair that can be touched by the policy ⇡. This introduces the reaching probability ⇠⇡ in the “total variance” term, which we need to deal with using the MDP structure. As a result, our recursion is significantly different from their counterpart, especially in the case of linear MDP.
Organization. Our paper is organized as follows: in Section 2, we review the related literature on offline reinforcement learning, and then briefly introduce the problem we consider in Section 3. In Section 4 and Section 5, we show our results of offline policy evaluation and offline policy optimization on tabular MDP correspondingly, and in Section 6, we show how to generalize our results to linear MDP with anchor points. We finally conclude and discuss our results in Section 7.

heading: 2 Related Work
text: In this section, we briefly discuss the related literature in three categories, i.e., offline policy evaluation, offline policy optimization, and horizon-free online reinforcement learning. Notice that, for the setting that assumes an additional generative model, typical model-based algorithms first query equal number of data from each state-action pair, then perform offline policy evaluation/optimization based on the queried data. Thus we view the reinforcement learning with generative model as a special instance of offline reinforcement learning. To make the comparison fair, for method and analysis that do not assume Assumption 1, we scale the error and sample complexity, by assuming per-step reward is upper bounded by 1 and 1/H under infinite-horizon and finite-horizon setting correspondingly.
Offline Policy Evaluation. For OPE in infinite horizon tabular MDP, [28] showed that plug-in estimator can achieve the error of eO ⇣q 1
dm(1 )
⌘ under Assumption 1, which matches the lower
bound in [29] up to logarithmic factors. For OPE in finite horizon time-inhomogeneous tabular MDP, [19, 24] provided an error bound of eO ⇣q 1
Kdm +
p SA Kdm ⌘ under the uniform reward assumption,
which matches the lower bound [13] up to logarithmic factors and an additional higher-order term. We here consider the time-homogeneous MDP, and obtain an error bound of Õ( q 1
Kdm ), that does
not have the additional p SA in higher-order term, which is different from [19, 24].
Beyond the tabular setting, [30] considered the performance of plug-in estimator with linear function approximation under the assumption of linear MDP without anchor points, and [31, 32] provided more detailed analyses on the statistical properties of different kinds of estimators under different assumptions, which are not directly comparable to our work. Recently, there are also works [e.g. 33] focusing on the interval estimation of the policy for practical application.
Offline Policy Optimization. Offline policy optimization for infinite horizon MDP can date back to [35]. [28] recently showed that a perturbed version of model-based planning can find ✏-optimal policy within eO ⇣ 1
dm(1 )✏2
⌘ queries of transitions in infinite horizon tabular MDP when the total reward is
upper bounded by 1, that matches the lower bound up to logarithmic factors. For the finite horizon time-inhomogeneous tabular MDP setting, [24] showed that model-based planning can identify ✏-optimal policy with eO ⇣ H
dm✏ 2
⌘ episodes, that matches the lower bound for time-inhomogeneous
MDP up to logarithmic factors. When it comes to finite horizon time-homogeneous tabular MDP and linrar MDP with anchor points, [1] provided a eO ⇣ min{H,S,d}
dm✏ 2
⌘ episode complexity for model-based
planning, which is min{H,S, d} away from the lower bound. We provide a eO ⇣ 1
dm✏ 2 + min{S,d} dm✏
⌘
episode complexity, that matches the lower bound up to logarithm factors and a higher order term.
A recent work [36] considered solving the offline policy optimization with model-free Q-learning with variance reduction. Although their algorithm can match the sample complexity lower bound ⌦ ⇣ H 2
dm✏ 2
⌘ when per-step reward is upper bounded by 1, model-free algorithms generally need at
least ⌦(H 2
dm ) episodes of data to finish the algorithm (a.k.a the sample size barrier in [28]) and it is
unclear how to translate their results to the setting with total reward upper bounded by 1.
Horizon-Free Online Reinforcement Learning. There are several works obtained nearly horizonfree sample complexity bounds for online reinforcement learning. In the time-homogeneous setting, whether the sample complexity needs to scale polynomially with H was an open problem raised by [37]. The problem was first addressed by [26] who proposed an ✏-net over the optimal policies and a simulation-based algorithms to obtain a sample complexity that only scales logarithmically with H , though their dependency on S,A and ✏ is not optimal and their algorithm is not computationally efficient. The sample complexity bound was later substantially improved by [27] who obtained an eO ⇣ SA
✏2 + S
2 A ✏
⌘ bound, which nearly matches the contextual bandits (tabular MDP with H = 1)
lower bound ⌦ SA
✏2
up to an S
2 A ✏ factor [38]. Their key ideas are (1) a new bonus function and
(2) a recursion-based approach to obtain a tight bound on the sample complexity. Such kind of recursion-based approach cannot be directly applied to the offline setting, and we develop a novel recursion method to suit the offline scenarios.

heading: 3 Problem Setup
text: Notation: Throughout this paper, we use [N ] to denote the set {1, 2, · · · , N} for N 2 Z+, (E) to denote the set of the probability measure over the event set E. Moreover, for simplicity, we use ◆ to denote polylog (S,A,H, d, 1/ ) factors (that can be changed in the context), where is the failure probability. We use eO and e⌦ to denote the upper bound and lower bound up to logarithm factors.

heading: 3.1 Markov Decision Process
text: Markov Decision Process (MDP) is one of the most standard models studied in the reinforcement learning, usually denoted as M = (S,A, R, P, µ), where S is the state space, A is the action space, R : S ⇥A ! (R+) is the reward, P : S ⇥A ! (S) is the transition, and µ is the initial state distribution. We additionally define r : S ⇥A ! R+ to denote the expected reward.
We focus on the episodic MDP with the horizon1 H 2 Z+ and time-homogeneous setting2 that P and R do not depend on the level h 2 [H]. A (potentially non-stationary) policy ⇡ is defined as ⇡ = (⇡1,⇡2, · · ·⇡H), where ⇡h : S ! (A), 8h 2 [H]. Following the standard definition, we define the value function V ⇡
h (s) := EP,⇡[
P H
t=h R(st, at)|sh = s] and the action-value function
(i.e. the Q-function) Q⇡ h (s, a) := EP,⇡[
P H
t=h R(st, at)|(sh, ah) = (s, a)], which are the expected
cumulative rewards under the transition P and policy ⇡ starting from sh = s and (sh, ah) = (s, a). Notice that, even though P and R keep invariant under the change of h, V and Q always depend on h in the episodic setting, which introduces additional technical difficulties compared with the infinite horizon setting.
The expected cumulative reward under policy ⇡ is defined as: v⇡ := Eµ [V ⇡1 (s)] , and our ultimate goal is finding the optimal policy ⇡⇤ of M, which can be written as: ⇡⇤ = argmax
⇡ (v⇡) . We
additionally define the reaching probabilities ⇠⇡ h (s) = Pµ,P,⇡(sh = s), ⇠⇡h (s, a) = Pµ,P,⇡(sh = s, ah = a), that represent the probability of reaching state s and state-action pair (s, a) at time step h. Obviously we have P s ⇠⇡ h (s) = 1, P s,a ⇠⇡ h (s, a) = 1, 8h 2 [H], and we also have the following relations between ⇠⇡ h (s) and ⇠⇡ h (s, a): ⇠⇡ h (s, a) = ⇠⇡ h (s)⇡(a|s), ⇠⇡ h+1 (s0) = P s,a ⇠⇡ h (s, a)P (s0|s, a).
With ⇠⇡ h
at hand, we can write v⇡ in an equivalent way: v⇡ = P
s,a ⇣⇣P h2[H] ⇠ ⇡ h (s, a) ⌘ r(s, a) ⌘ ,
which provides a dual perspective on the policy evaluation [18].

heading: 3.2 Offline Reinforcement Learning
text: Generally, P and r are not revealed to the learner, which means we can only learn about M and identify the optimal policy ⇡⇤ with data from different kinds of sources. In offline reinforcement learning, the learner can only have access to a collection of data D = {(si, ai, ri, s0i)}i2[n] where ri ⇠ R(si, ai) and s0i ⇠ P (·|si, ai), that is collected in K episodes with (known or unknown) behavior policy (so that n = KH), For simplicity, define n(s, a) as the number of data that (si, ai) = (s, a), while n(s, a, s0) is the number of data that (si, ai, s0i) = (s, a, s0).
With D, the learner is generally asked to do two kinds of tasks. The first one is the offline policy evaluation (a.k.a off-policy evaluation), that aims to estimate v⇡ for the given ⇡. The second one is the offline policy optimization, that aims to find the ⇡̂⇤ that can perform well on M. We are interested in the statistical limit due to the limited number of data, and how to approach this statistical limit with simple and computationally efficient algorithms.

heading: 4 Offline Policy Evaluation
text: In this section, we first consider the offline policy evaluation for tabular MDP with number of state S = |S| < 1, number of action A = |A| < 1, which is the basis for the more general settings. We first introduce the plug-in estimator we consider, which is equivalent to different kinds of estimators that are widely used in practice. Then we describe the assumptions we use, show the error bound of the plug-in estimator, and provide the proof sketch of the error bound.

heading: 4.1 The Plug-in Estimator
text: Here we introduce the plug-in estimator. We first build the empirical MDP cM with the data: P̂ (s0|s, a) = n(s,a,s 0 )
n(s,a) , r̂(s, a) =
P i2[n] ri1(si,ai)=(s,a)
n(s,a) , where 1 is the indicator function. Then we
correspondingly define Q̂⇡ h , V̂ ⇡ h and finally the estimator v̂⇡, 8h 2 [H], by substituting the P and r
1A common belief is that we can always reproduce the results between episodic time-homogeneous setting and infinite horizon setting via substitute the horizon H in episodic setting with the “effective horizon” 11 in episodic setting. However, this argument does not always hold, for example the dependency decouple technique used in [34, 28] cannot be directly applied in the episodic setting.
2Some previous work consider time-inhomogeneous setting [e.g. 39], where P and R can be varied for different h 2 [H]. It is noteworthy that we need an additional H factor in the sample complexity to identify ✏-optimal policy for time-inhomogeneous MDP compared with time-homogeneous MDP. Transforming the improvement analysis from time-homogeneous setting to time-inhomogeneous setting is trivial (we only need to replace S with HS), but not vice-versa, as the analysis for time-inhomogeneous setting probably do not exploit the invariant transition sufficiently.
in Q⇡ h , V ⇡ h and v⇡ with P̂ and r̂. Such computation can be efficiently implemented with dynamic programming. We also introduce the reaching probabilities ⇠̂⇡
h (s) = P µ,P̂ ,⇡ (sh = s), ⇠̂⇡h (s, a) =
P µ,P̂ ,⇡ (sh = s, ah = a) in the empirical MDP cM, which will be helpful in our analysis.
The plug-in estimator has been studied in [30] under the assumption of linear transition. It’s known that the plug-in estimator is equivalent to the MIS estimator proposed in [19] and a certain version of DualDICE estimator with batch update is proposed in [16], due to the observation that v̂⇡ = P s,a ⇣⇣P h2[H] ⇠̂ ⇡ h (s, a) ⌘ r̂(s, a) ⌘ .

heading: 4.2 Theoretical Guarantee
text: Here we first summarize the assumptions we use for the tabular MDP. Assumption 1 (Bounded Total Reward). 8⇡, we have P h2[H] rh  1 almost surely, where s1 ⇠ µ, ah ⇠ ⇡(·|sh), rh ⇠ R(sh, ah) and sh+1 ⇠ P (·|sh, ah), 8h 2 [H]. This also means P(r ⇠ R(s, a)|r > 1) = 0, 8(s, a). This is the key assumption used in [26, 27] to escape the polynomial dependence of horizon in episodic setting. As discussed in [37, 26, 27], this assumption is also more general than the uniformly bounded reward assumption: 8(s, a), r(s, a)  1/H . Thus, all of the results in this paper can be generalized to the uniformly bounded reward with a proper scaling of the bounded total reward. Assumption 2 (Data Coverage). 8(s, a), n(s, a) ndm. This assumption has been used in [19, 24] and is similar to concentration coefficient assumption originated from [40]. Intuitively, the performance of the offline reinforcement learning should depend on dm, since the state-action pair with less visitation will introduce more uncertainty.
Notice that, dm 2 0, (SA) 1 ⇤ . Assuming access to the generative model, we can query equal number of samples from each state action pair, where dm = (SA) 1. For the offline data sampled with a fixed behavior policy ⇡BEH, we can view dm ⇡ 1H mins,a P h2[H] ⇠ ⇡BEH h (s, a), which measures the quality of exploration for ⇡BEH. When the number of episodes K = e⌦ (1/dm), by standard concentration, we know mins,a n(s, a) ⇡ ndm = HKdm. We remark that, some of the recent Liu et al. [41], Yin et al. [36] define the data coverage via the coverage on the visitation of the optimal policy when considering offline policy optimization. This kind of data coverage can be covered by our Assumption 2, by considering the sub-MDP which only consists of the state-action pair that can be visited by the optimal policy. As we already know that the optimal policy will not leave this sub-MDP, any near-optimal policy on this sub-MDP will be near-optimal on the original MDP, and hence our results can be directly applied under this alternative definition of data coverage.
With these assumptions at hand, we can present our main results. Theorem 1. Under Assumption 1 and Assumption 2, suppose K = e⌦ (1/dm), then
|v⇡ v̂⇡|  q ◆
Kdm
holds with probability at least 1 , where K is the number of episodes, dm is the minimum visiting probability and ◆ absorbs the poly log factors. To demonstrate the tightness of our upper bound, we provide a minimax lower bound in Theorem 23. Theorem 2. There exists a pair of MDPs M1 and M2, and offline data D with |D| = KH and minimum visiting probability dm, such that for some absolute constant c0, we have
inf v̂⇡ supMi2{M1,M2} PMi ⇣ |v̂⇡(D) v⇡| > c0p
Kdm
⌘ > 0.25,
where v̂⇡ is any estimator that takes D as input.
Remark Theorem 1 and 2 show that, even with the simplest plug-in estimator, we can match the minimax lower bound ⌦ ⇣q 1
Kdm
⌘ for offline policy evaluation in time-homogeneous MDP up to
logarithmic factors. As a result, we can conclude that time-homogeneous MDP is not harder than the bandits in offline policy evaluation.
3To the best of our knowledge, no lower bound has been provided for finite horizon time-homogeneous setting, so here we provide a minimax lower bound, and the proof can be found in Appendix B.
Remark The assumption that K = e⌦ (1/dm) is a mild and necessary assumption, as with only o (1/dm) episodes, there can exist some under-explored state-action pair which unavoidably leads to constant error (this is also how we construct the hard instance for the minimax lower bound).
Remark Central to our analysis is a recursion based upper bound on the “total variance” term (see Lemma 1), which enables us to have a sharper bound for the plug-in estimator compared with previous work [e.g. 19, 24] that include the unnecessary poly(S,A) factors in the higher-order term.

heading: 4.3 Proof Sketch
text: The detailed proof can be found in Appendix A, and here we sketch our proof in short. With the value difference lemma (see Lemma 4 in the Appendix A), we need to focus on bounding the term:
P h2[H] P s,a ⇠̂⇡ h (s, a) hP s0 ⇣ P (s0|s, a) P̂ (s0|s, a) ⌘ V ⇡ h+1 (s0) i ,
which, by Bernstein’s inequality and Cauchy-Schwartz inequality associated with the Assumption 1 and Assumption 2, can be upper bounded by the following term with high probability:
q ◆
Kdm
qP h2[H] P s,a ⇠̂⇡ h (s, a)VarP (s,a)(V ⇡h+1(s 0)) + ◆ Kdm
To bound the “total variance” term P h2[H] P s,a ⇠̂⇡ h (s, a)VarP (s,a)[V ⇡ h+1 (s0)], we use a novel recursion-based method based on the following observation: Lemma 1 (Variance Recursion For Evaluation). For the value function V ⇡
h (s) induced by any ⇡, we
have that X
h2[H]
X
s,a
⇠̂⇡ h (s, a)VarP (s,a) h Vh+1(s 0)2 i i
 X
h2[H]
X
s,a
⇠̂⇡ h (s, a)
" X
s0
⇣ P (s0|s, a) P̂ (s0|s, a) ⌘ Vh+1(s 0)2 i+1 # + 2i+1 (1)
Here the term in (1) can be bounded with P h2[H] P s,a ⇠̂⇡ h (s, a)VarP (s,a) h Vh+1(s0)2 i+1 i , the total variance of higher-order value function via Bernstein’s inequality. Thus Lemma 1 can be applied iteratively to obtain a tight bound for the “total variance” term. Define
1(i) =
X
h2[H]
X
s,a
⇠̂⇡ h (s, a)
" X
s0
⇣ P (s0|s, a) P̂ (s0|s, a) ⌘ V ⇡ h+1 (s0)2 i # .
Applying Lemma 1 with V ⇡ h (s), we can write the following recursion:
1(i)  q ◆
Kdm ( 1(i+ 1) + 2i+1) +
◆
Kdm .
Solve this recursion, and we can obtain the results in Theorem 1.

heading: 5 Offline Policy Optimization
text: In this section, we further consider the offline policy optimization for tabular MDP, which is the ultimate goal for offline reinforcement learning. We first introduce the model-based planning algorithm, which is probably the simplest algorithm for offline policy optimization. Then we analyze the performance gap between the policy obtained by model-based planning and the optimal policy.

heading: 5.1 Model-Based Planning
text: We consider the optimal policy on the empirical MDP cM, which can be defined as ⇡̂⇤ = argmax
⇡ v̂⇡. (2)
Here ⇡̂⇤ can be obtained by dynamic programming with the empirical MDP, which is also known as model-based planning. We remark that our analysis is independent to the algorithm used for solving (2). In other words, the result also applies to the optimization-based planning with the empirical MDPs [42, 43], as long as it solves (2).

heading: 5.2 Theoretical Guarantee
text: Theorem 3 provides an upper bound on the sub-optimality of ⇡̂⇤. Theorem 3. Under Assumption 1 and Assumption 2, suppose that K = e⌦ (1/dm), and then
v⇡⇤ v⇡̂⇤ 
q ◆
Kdm + S◆ Kdm ,
holds with probability at least 1 , where K is the number of episodes, dm is the minimum visiting probability and ◆ absorbs the poly log factors.
We also provide a minimax lower bound under the finite horizon time-homogeneous setting. Theorem 4. There exists a pair of MDPs M1 and M2, and offline data D with |D| = KH and minimum state-action pair visiting frequency dm, such that for some absolute constant c0, we have
inf v̂⇡ supMi2{M1,M2} PMi ⇣ v⇡̂(D) v⇡⇤ > c0p Kdm ⌘ > 0.25,
where ⇡̂ is any planning algorithm that takes D as input.
Remark Theorem 3 provides a bound approaching the minimax lower bound in Theorem 4 up to logarithmic factors and a higher-order term, which shows that the error of offline policy optimization does not scale polynomially on the horizon. Notice that if dm = ⌦ 1
SA
, we can obtain an error
bound of eO ⇣q SA
K + S
2 A K
⌘ , which can be translated to sample complexity eO ⇣ SA
✏2 + S
2 A ✏
⌘ that
matches the best known result of sample complexity for online finite-horizon time-homogeneous setting [27]. We conjecture that the additional S factor in the higher-order term is only an artifact (see Lemma 2) and can be eliminated with more delicate analysis. We leave this as an open problem.
Remark There are also works considering local policy optimization [e.g. 44–46] when the offline data are not sufficient exploratory. We want to emphasize that, as Theorem 4 suggests, to identify the global optimal policy, we need the offline data sufficient exploratory.

heading: 5.3 Proof Sketch
text: The detailed proof can be found in Appendix A, and here we sketch our proof in short. Notice that
v⇡ ⇤ v⇡̂⇤ =v⇡ ⇤ v̂⇡ ⇤ + v̂⇡ ⇤ v̂⇡̂ ⇤
| {z } 0
+v̂⇡̂ ⇤ v⇡̂ ⇤
 v⇡ ⇤ v̂⇡ ⇤
| {z } Error on Fixed Policy
+ v̂⇡̂ ⇤ v⇡̂ ⇤
| {z } Error on Data Dependent Policy
. (3)
We can directly apply Theorem 1 to bound the error on fixed policy. For the error on data-dependent policy, since the policy ⇡̂⇤ depends on data, we need to consider
X
h2[H]
X
s,a
⇠̂⇡ h (s, a)
" X
s0
⇣ P (s0|s, a) P̂ (s0|s, a) ⌘ V ⇡̂ ⇤
h+1 (s0)
#
= X
h2[H]
X
s,a
⇠̂⇡ h (s, a)
" X
s0
⇣ P (s0|s, a) P̂ (s0|s, a) ⌘ V ⇡ ⇤
h+1 (s0)
# (4)
+ X
h2[H]
X
s,a
⇠̂⇡ h (s, a)
" X
s0
⇣ P (s0|s, a) P̂ (s0|s, a) ⌘⇣ V ⇡̂ ⇤
h+1 (s0) V ⇡̂
⇤
h+1 (s0)
⌘# . (5)
As ⇡⇤ is independent of P̂ , the term in (4) can be similarly handled with the techniques used in offline policy evaluation. However, due to the dependency of ⇡̂⇤ and P̂ , we need to deal with the term in (5) more carefully. To decouple the dependency of ⇡̂⇤ and P̂ , we first introduce the following lemma: Lemma 2. 8Vh(s) 2 [0, 1], 8h 2 [H], s 2 S , then we have that with high probability,
P
s0
⇣ P (s0|s, a) P̂ (s0|s, a) ⌘ Vh(s0)  q S·VarP (s,a)[Vh(s0)]◆ n(s,a) + S◆ n(s,a) .
Remark Lemma 2 has been widely used in the design and analysis of online reinforcement learning algorithms, [e.g. 27]. It holds even Vh(s) depends on P̂ (s0|s, a), however, at the cost of an additional S factor. This is the source of the additional S factor in the higher-order term, and we believe a more fine-grained analysis can help avoid this additional S factor.
We also have the following recursion for (4) and (5):
Lemma 3 (Variance Recursion For Optimization). For Vh(s) = V ⇡ ⇤ h (s) and Vh(s) = V ⇡ ⇤ h (s) V ⇡̂ ⇤
h (s), we have that
X
h2[H]
X
s,a
⇠̂⇡̂ ⇤
h (s, a)VarP (s,a) h Vh+1(s 0)2 i i
 X
h2[H]
X
s,a
⇠̂⇡̂ ⇤
h (s, a)
" X
s0
⇣ P (s0|s, a) P̂ (s0|s, a) ⌘ Vh+1(s 0)2 i+1 # (6)
+ 2i+1 " X
s
µ(s)V1(s) + X
h2[H]
X
s,a
⇠̂⇡̂ ⇤
h (s, a)
X
s0
h P (s0|s, a) P̂ (s0|s, a) i Vh+1(s 0) # . (7)
Denote
2(i) =
X
h2[H]
X
s,a
⇠̂⇡ h (s, a)
" X
s0
⇣ P (s0|s, a) P̂ (s0|s, a) ⌘ V ⇡ ⇤
h+1 (s0)2
i # ,
3(i) =
X
h2[H]
X
s,a
⇠̂⇡ h (s, a)
" X
s0
⇣ P (s0|s, a) P̂ (s0|s, a) ⌘⇣ V ⇡ ⇤
h+1 (s0) V ⇡̂
⇤
h+1 (s0)
⌘2i #
.
Applying Bernstein inequality or Lemma 2, and then Lemma 3, we have that:
2(i)  r ◆
Kdm ( 2(i+ 1) + 2i+1(v⇡
⇤ + 2(0))) + ◆
Kdm
3(i)  r S◆
Kdm ( 2(i+ 1) + 2i+1(v⇡
⇤ v⇡̂⇤ + 3(0))) + S◆
Kdm .
With Assumption 1, we know v⇡ ⇤  1. Also, with (3) and (4), we have that v⇡⇤ v⇡̂⇤  3(0) +
O ⇣q ◆
Kdm
⌘ . Solve this recursion, then we can obtain the results in Theorem 3.

heading: 6 Extensions to Linear MDP with Anchor Points
text: In this section, we first introduce the definition of the linear MDP with anchor points [47, 1], and then generalize our results of offline policy evaluation and optimization to this setting. Definition 1 (Linear MDP with Anchor Points [47, 1]). For the MDP M = (S,A, R, P, µ), assume there is a feature map : S ⇥A ! Rd, such that r and P admits a linear representation:
r(s, a) = h (s, a), ✓ri P (s0|s, a) = h (s, a), µ(s0)i,
where µ is an unknown (signed) measure of S . Furthermore, we assume there exists a set of anchor state-action pairs K, such that 8(s, a) 2 S ⇥A, 9{ s,a
k }k2K,
(s, a) = P
k2K s,a k (sk, ak), P k2K s,a k = 1, s,a k 0, 8k 2 K.
With the definition of Linear MDP as well as the anchor points assumption, we can find that r(s, a) = P k2K s,a k r(sk, ak), P (s0|s, a) = P k2K s,a k P (s0|sk, ak), which can lead to an empirical estimation of P̂ and r̂ by replacing {r(sk, ak)}k2K, {P (s0|sk, ak)}k2K with the empirical counterpart {r̂(sk, ak)}k2K, {P̂ (s0|sk, ak)}k2K estimated from the offline data. Following [47, 1], we additionally make the following assumption on the offline data:
Assumption 3 (Anchor Point Data [47, 1]). Assume |K| = d. For the offline data D = {(si, ai, ri, s0i)}i2[n], (si, ai) 2 {(sk, ak)}k2K, 8i 2 [n]. Furthermore, 8k 2 K, n(sk, ak) ndm.
We now present the main theorem on the offline policy evaluation and offline policy improvement on the linear MDP with anchor points. Theorem 5. Under Assumption 1 and Assumption 3, suppose n = e⌦ (H/dm), and then for a given policy ⇡, the plug-in estimator v̂⇡ satisfies
|v⇡ v̂⇡|  q H◆
ndm
with probability at least 1 , where n is the number of offline data, dm is the minimum visiting probability of anchor points and ◆ absorbs the polylog factors. Theorem 6. Under Assumption 1 and Assumption 3, suppose that n = e⌦ (H/dm), and then for the ⇡̂⇤ obtained by model-based planning,
v⇡⇤ v⇡̂⇤ 
q H◆
ndm + dH◆ ndm ,
holds with probability at least 1 , where n is the number of offline data, d is the feature dimension, dm is the minimum visiting probability of anchor points and ◆ absorbs the polylog factors.
Proof of both theorems can be found in Appendix C. From a high-level perspective, we observe that for the unseen state-action pair, we still have Bernstein-type concentration bound and a lemma similar to Lemma 2. Hence we can apply our recursion introduced in Lemma 1 and use the similar techniques for tabular MDP to obtain the desired results. We want to remark that such results demonstrate the broad applicability of our recursion-based analysis in different kinds of offline scenarios.
Remark Compared with the results in [1], we remove the additional dependency of min{H, |S|, d} in the main term and approach the optimal complexity shown in the [47] up to logarithmic factors, which shows that model-based planning is minimax optimal for Linear MDP with anchor points and demonstrates the effectiveness of our recursion-based analysis.
Remark Here we do not directly replace the term n/H with K, as we make relatively strong assumption on all of the offline data are sampled from the anchor points. One potential question is how general the anchor point assumption is. We notice that, as [30] showed, the popular FQI algorithm for linear MDP provides an estimate of P̂ as
P̂ (s0|s, a) = (s, a)>⇤̂ 1 P
i2[n] (si, ai)1s0=s0i ,
where ⇤̂ = P
i2[n] (si, ai) (si, ai) >. As P s0 P (s 0|s, a) = 1, by Definition 1,
1 = P
s0 P (s 0|s, a) = (s, a)> P s0 µ(s 0) = (s, a)>⇤̂ 1 ⇣P i2[n] (si, ai) ⌘ .
Thus, if (s, a)⇤̂ 1 (si, ai) 0, 8(s, a), i, then it forms a linear MDP with anchor points with K = {(si, ai)}i2[n], s,ak = (s, a)⇤̂ 1 (sk, ak) and our analysis can be simply adapted to this case where ndm is replaced with min(⇤̂) using Freedman’s inequality [48], and min(⇤̂) denotes the minimum eigenvalue of ⇤̂. We notice that if (s, a)⇤̂ 1 (si, ai) < 0, and s0i are distinct for each i (which is probable for exponential large |S|), then P̂ (s0
i |s, a) < 0, which can be pathological for the
algorithm and analysis. We expect a well-behaved transition estimation (i.e.P̂ ) for linear MDP shares the similar results, even without anchor point assumptions. We leave this as an open problem.

heading: 7 Conclusion
text: In this paper, we revisit the offline reinforcement learning on episodic time-homogeneous MDP. We show that, if the total reward is properly normalized, offline reinforcement learning is not harder than the offline bandits counterparts. Specifically, we provide performance guarantee for algorithms based on empirical MDPs, that match the lower bound up to logarithmic factors for offline policy evaluation, and up to logarithmic factors and a higher-order term for offline policy optimization, and both do not have polynomial dependency on H . There are still several open problems. For example, can we provide a sharper analysis for the policy obtained by model-based planning without any additional factors on higher-order term? Can we extend to MDP with more general assumption? We leave these problems as future work.

heading: Acknowledgement
text: The authors thank the anonymous reviewer for their constructive feedback. TR would like to thank for the helpful discussion with Ming Yin and Yu Bai. SS gratefully acknowledges the funding from NSF grants 1564000 and 1934932, and SSD gratefully acknowledges the funding from NSF Award’s IIS-2110170 and DMS-2134106.

Review summaries:
The paper analyzes the plug-in approach to off-policy evaluation and optimization in reinforcement learning, and sharpens some of the sample complexity bounds (assuming sufficiently exploratory data, time-homogenous MDPs). The key novelty is in upper-bounding the variance of estimated values cleverly by using higher-order powers of appropriate values. By doing so, the paper's derived bounds do not directly depend on the horizon of the MDP. One benefit of the proposed analysis is that a very similar line of reasoning is sufficient to derive horizon-independent bounds for both evaluation and optimization, as well as for tabular MDPs as well as linear MDPs with additional structure.