Offline Reinforcement Learning with Additional Covering Distributions
Authors: Chenjie Mao
Venue: Accepted by TMLR ()

Abstract: We study learning optimal policies from a logged dataset, i.e., offline RL, with function general approximation. Despite the efforts devoted, existing algorithms with theoretic finite-sample guarantees typically assume exploratory data coverage or strong realizable function classes (e.g., Bellman-completeness), which is hard to be satisfied in reality. While there are recent works that successfully tackle these strong assumptions, they either require the gap assumptions that could only be satisfied by part of MDPs or use the behavior regularization that makes the optimality of learned policy even intractable. To solve this challenge, we provide finite-sample guarantees for a simple algorithm based on marginalized importance sampling (MIS), showing that sample-efficient offline RL for general MDPs is possible with only a partial coverage dataset (instead of assuming a dataset covering all possible policies) and weak realizable function classes (assuming function classes containing simply one function) given additional side information of a covering distribution. We demonstrate that the covering distribution trades off prior knowledge of the optimal trajectories against the coverage requirement of the dataset, revealing the effect of this inductive bias in the learning processes. Furthermore, when considering the exploratory dataset, our analysis shows that only realizable function classes are enough for learning near-optimal policies, even with no side information on the additional coverage distributions.

Published in Transactions on Machine Learning Research (11/2023)
Offline Reinforcement Learning with Additional Covering Distributions
Chenjie Mao
chenjiema@@hust.eu.co
School of Computer Science and Technology
Huazhong University of Science and Technology
Reviewed on OpenReview: https: // openreview. net/ forun? id=AfX
Abstract
We study learning optimal policies from a logged dataset, i.e., offline RL, with function gen- eral approximation. Despite the efforts devoted, existing algorithms with theoretic finite- sample guarantees typically assume exploratory data coverage or strong realizable function classes (e.g., Beliman-completeusss) which hard be satisfied reality. While there are recent works that successfully tackle these strong assumptions, they either require the gap assumptions that could only be satisfied by part of MDPs or the behavior regularization that needs to be carefully controlled. To solve this challenge, we provide finite-sample guar- antees for simple algorithm based on marginalized importance sampling (MIS), showing that sample-efficient offline RL for general MDPs is possible with only a partial coverage dataset (instead of assuming a dataset covering all possible policies) and weak realizable function classes (assuming function classes containing simply one function) given additional side information of a covering distribution. We demonstrate that the covering distribution trades off prior knowledge of the optimal trajectories against the coverage requirement of the dataset, revealing the effect of this inductive bias in the learning processes. Furthermore, when considering the exploratory dataset, our analysis shows that only realizable function classes are enough for learning near-optimal policies, even with no side information on the additional coverage distributions.
1 Introduction and related works
In offline reinforcement learning (offline RL., also known batch RL), the learner trics to find good policies with pro-collected dataset. This data-driven paradigm climinates the heavy burden of environmental interaction required in online learning, which could be dangerous costly (e.g., in robotics (Kalashnikov et al., 2018; Sinha & Garg, 2021) and healthcare (Gottesman et al., 2018; 2019; Tang et al., 2023)), making offline RL promising approach in real-world applications.
In carly thcoretic studics of offline RL (e.g., Munos (2003; 2005; 2007); Ernst al. (2005); Antos et al. (2007); Munos & Szepesvari (2008); Farahmand et al. (2010)), researchers analyzed the finite-sample behavior of algorithms under the assumptions such erploratory datasets, realizable or Bellman collpan-compltte function classes. However, despite some error propagation bounds and sample complexity guarantees achieved in these works, the strong coverage assumption made on datasets and the non-monotonic assumptions made on function classes which which are always hard to be satisfied in reality-drive people to try to find sample- efficient offline RL algorithms under only weak assumptions about dataset and function classes (Chen & Jiang, 2019).
From the dataset perspective, partial coverage, which means that only some specific (or even nonc) policies are covered by the dataset (Rashidinejad et al., 2021; Xie et al., 2021; Uehara & Sun, 2021; Song el al., 2022), is studied. To address the problem of insufficient information, most algorithms use behavior regularization (c.g. Laroche & Trichelair (2017); Kumar
al. (2019); Zhan et al. (2022)) or pessimism in the face of uncertainty (c.g., Liu al. (2020); Jin et al. (2020); Rashidinejad et al. (2021); Xie al. (2021); Uchara & Sun (2021); Cheng et al. (2022); Zhu et al. (2023)) to constrain the learned policies to be close to the

---

Published in Transactions on Machine Learning Research (11/2023)
behavior policy. Most of the algorithms in this setting (except some that we will discuss later) require function assumptions in some sense of complelencss-Bellneee Bellman-compllteness or strict realization according to another function class (we attribute it as strong realization).
From the function classes perspective, while the primary concern is Bellman-complleennss assumption which is criticized for its non-monotoniccty some recent works (Zhan et al., 2022; Chen & Jiang, 2022; Ozdaglar et al., 2022) have noticed that the realizability according to another function class is also non-monotonic. These non-monotonic properties contradict the intuition in supervised learning that rich function classes perform better (or at least. no worse). Typical examples of these assumptions are the " "realizability of all candidate policies' value functions" (e.g., Jiang & Huang (2020); Zhu et al. (2023)) and the "realizability of all candidate policies' density ratio" (o.g., Xie & Jiang (2020b)). These assumptions are equally strong as Bellman- pellmann-oompetennsss and we classify them "strong realizability" (Zhan et al. (2022); Ozdaglar et al. (2022) attribute it as "completeness-type" for clarification. We also classify assuming that the function class realizes specific elements as "weak realizability" correspondingly (Chen & Jiang (2022) attributes this as "rcalizability-type"" We argue that this taxonomy is justified also because Bellman converted to the realizability assumption between two function classes with the minimax algorithm (Chen & Jiang, 2019). This conversion aligns the bohavior of collman-completeness with strong realizability assump- tions.
Bellman-completene completeness can be
On the one hand, Bellmann-completeness assumption is always made the classical finite-sample analyses of offline RL (e.g., analysis of FQI (Ernst et al., 2005; Antos et al., 2007)) to ensure closed updates of value functions (Sutton & Barto, 2018; Wang al., 2021). This assumption notoriously hard to mitigate, and Foster et al. (2021) even suggests an iiformation-theorttie lower bound stating that without Bellman- completeness, sample-efficient offline RL is impossible even with an exploratory dataset and a function class containing all candidate policies' value functions. Therefore, it is clear that additional assumptions are required to circumvent colplan-cmmpletnnsss.
On the other hand, as marginalized importance sampling (MIS, see, e.g., Liu et al. (2018); Uchara et al. (2019); Jiang & Huang (2020); Huang & Jiang (2022)) has shown its effect of eliminating Bellman- completeness with only a partial coverage dataset by assuming the realizability of density ratios in off-policy evaluation (OPF), there are works try to adapt it to policy optimization. These adaptations retain the elimi- nation of Bellman-commpa compleene,, but most come up with other drawbacks. Some works (e.g., Jiang & Huang (2020); Zhu et al. (2023) use OPE as an intermediate evaluation step for policy optimization yet require the strong realizability assumption on the value function class. The others borrow the idea of discriminators from MIS. Lee et al. (2021); Zhan et al. (2022) take value functions as discriminators for the optimal density ratio, using MIS to approximate the linear programming approach of Markov Decision Processes (Manne, 1960; Puterman, 1994). Nachum et al. (2019); Chen & Jiang (2022); Uehara et al. (2023) take distribution density ratios as discriminators for optimal value function by replacing the Bellman equation in OPE with its optimality variant. While in most cases, thooretic finite-sample guarantees with these discriminators would require strong realizable function classes (e.g,, Rashidinejad et al. (2022)), Zhan el al. (2022); Chen & Jiang (2022); Uehara et al. (2023) avoid this with additional gap assumptions or an alternative criterion of optimality performance degradation w.r.t. the regularized optimal policy. To the best of our knowledge, they are the only works that achieve theoretic sample-efficient guarantees under only weak realizability and partial coverage assumptions. However, on the one hand, the gap (margin) assumption (Chen & Jiang, 2022; Cehara et al., 2023) causes that only some specific Markov decision processes (MDPs) under which the optimal value functions have ularized optimal policy (Zhan et al., 2022) could be meaningless in some cases, and the actual performance of the learned policy requires careful fino-tuning the regularization. Morcover, the sample complexities from Uehara et al. (2023) are polynomial w.r.t. the cardinality of the action space, which cannot handle large action spaces.
can be solved. On the other hand, sub-optimality compared with a reg-
As summarized above, the following question arises:
Is sample-efficient offline RL possible with only partial coverage and weak realizability assumptions for general MDPs?
2

---

Published in Transactions on Machine Learning Research (11/2023)
Table 1: A comparison of offiin RL algorithms without assuming Bellman-completeness and model- realizability. "cone." stands for concentrability. The data assumptions from Xie & Jiang (2020a) require that for all E S, a E A, and s' E S, we have that d (s. a), 1/ma(als), P(''|s,a\/uP(( and n (P(s)/uo()) are lower bounded by a constant (we define 0/0 = 1). C(Q) stands for the convex hull of Q. wa and V are the regularized optima from the original paper. 4 and 2 are the newly defined function classes introduced by Rashidinejad et al. (2022). Uchara et al. (2023) is compromised by two parts for algorithms with or without regularizations. The unregularized algorithm part requires margin assumptions of the optimal value function, and the sample complexities of both parts are polynomial w.r.t. |A]. de is the additional covering distribution introduced by this paper. The definitions of the other notations can be found in the remaining part of this paper.
Algorithm
Data assumptions
Function assumptions
Drawhacks
Jiang & Huang (2020)
optimsl conc.
w' E W, and Vr E I1, Qa E C(Q)
strong realizability
Xie & Jiang (2020a)
conc. w.r.t. P and A
C' 0
strong dataset assumptions
Zhan et sl. (2022)
optimal conc.
wa W, and v/2 E
Use regularization
Chen & Jiang (2022)
optimal conc.
"' W, and Q" Q
assume gap (margin)
Rashidinejad et al. (2022) optimal conc.
"' W, V V. M., E Vw and Sar,0 E Vu
stroug realizability
Zhu et al. (2023)
optimal cone.
"" W; Vn e II, Qr E Q
strong realizability
Cehara et al. (2023)
optimal conc from dD
w² E W, and Q" Q
assume gap (margin)/|A)
Ours (VOPR)
optimal cone. from de
w² W, 8" é B and Q" E Q
assume a covering de
We answer this question in the positive and propose an algorithm that achieves finite-sample guarantees under weak assumptions with the help of an additional covering distribution. We assume that the covering distribution covers all non-stationary near-optimal policies, and the dataset covers the trajectories induced by an optimal policy from it. The covering distribution can be taken as a minimum requirement for accurately estimating the optimal value function Q", and we use it regularizer in our algorithm. It is adaptive such that both "non-stationary" and "near-optimal" above would be alleviated as the gap of optimal value function increases. The covering distribution also gives a trade-off against the data coverage assumption: the more accurate it is, the fewer redundant trajectories are required to be covered by the dataset. Furthermore, we can directly use the data distribution as the covering distribution as done in Uchara et al. (2023), if the near-optimal variant of their data assumptions are also satisfied.
For comparison, we summarize algorithms that do not need Bellman--oompleennes and model realizability (which is even stronger (Chen & Jiang, 2019; Zhan et al., 2022)) in Table 1. Necessary transfers are made to get the sub-optimality bound.
In conclusion, our contributions are as follows:
(Section 3) We identify the novel mechanism of non-stationary near-optimal concentrability in policy optimization under wcak assumptions.
(Section 4) We demonstrate the trade-off brought. by additional covering distríbutions for the cov- erage requirement of the dataset.
(Section 4) We propose the first algorithm that achieves finite-sample guarantees for general MDPs under only weak realizability and partial coverage assumptions.
2
Preliminaries
This section introduces base concepts and notations in oflline RL with function approximation and MIS See Table 2 in Appendix A for a more complete list of definitions of notations.
Markov Decision Processes (MDPs) We consider infinite-horizon discounted MDPs defined as (S,A,, P,R, y, Ho), where is the state space, A is the action space, P: x A + A(S) is the transi- tion probability, R: -> [0, Rmaz] the deterministic reward function, 7 E (0, 1) the discount factor that unravels the problem of infinite horizons, and No E A(S) is the initial state distribution. With pol- iey T: S A(A), we say that it induces random trajectory {so, ao ro, 81, 01 r..... ... Si, (r Ti, 81+1,....
3

---

Published in Transactions on Machine Learning Research (11/2023)
if: so Mu. a; r(-1S:). Pi = R(s,,0) a,) and 8++1 P(-ls;; oz). We define the expected return of policy π as J= = E[ ''r I No: No.T]. We also denote the value function of л as the expected re- turn starting from some specific state or statc-action pair (s, Vi((s) = E -i=oorrr I s, and (r(s,a) E Ei=o (s. We denote the optimal policies that achieve the maximum return J from H4 as II, and its member as n² We say policy is optimal almost everywhere if its state value function is maximiied almost everywhere and denote it as To (T is not always unique). We represent the value functions of Te as V* and Q*. It worth noting that V and Q*, the unique solutions of both Bellman optimality equation and the primal part of LP approach of MDPs (Puterman, 1994), are not the value functions of all optimal policics. For case of discussion, we assume S, A, S x A are compact measurable spaces and, with abuse of notation, we use v to denote the corresponding finite uniform measure on each space (e.g., Lebesgue measure). We use Pa to denote the state-action transition operator for density d P, a') == 1exAT(al P 8, a,a) a)dv(s, a). The induced distribution of policy is defined ds a) = (1 - 7) Eo P(s; = s, a, = also ~ no. a ~ π (-1ss)), and use μx to denote the state margin of dg. We would add subscripts to denote distributions not induced from μo (e.g., dz',)).
Offline policy learning with function approximation In the standard theoretical setup of offine RL, we are given with dataset D consisting of N a,, tuples, which is collected with state distribution u and behavior policy T. such that ,x, a ~ mo(-ls),r = R(s, a), ~ P()s,,).. We use d' == ((s)To(a s) to denote the composed state-action distribution of the dataset. When the state space and action space become rather complex, function approximation is typically used. For this, we assume there are some function classes at hand that satisfy certain assumptions and have limited complexity (measured by cardinality, metric entropy and so forth). The function classes considered in this paper are stale-action value function class _ (8 x x + R), state distribution ratio class W S (8 x A + R), and policy ratio class B C (S A A R).
MIS with density discriminators and 1.2 error bound One of the most popular ways estimate the optimal value function is via the Bellman optimality equation:
Ys Y A, Q(ss.a)=T'Q'(>
(1)
where T')(s,a) = a(s,a) + -Bg-P((s.n) (sa. .)] denotes the Bellman optimality operator. However, when try to utilize the constraints from Eq. (1) (e.g., through the L error ||q - - the ex- pectation in T* would introduce the infamous double-sampling issue (Baird, 1995), making the estimation intractable.
To overcome this, privious works with MIS tried to take weight functions as discriminators and minimize a weighted sum of Eq. (1). In fact, even the L' error itself could be written as a weighted sum with some sign function (Lake 1 if q 2 T and -1 othrrwise (Ozdaglar et al., 2022)). Namely, we approximate Q* through
argmin max Byd ( ()((s,a)) T'q(s, q Q
(2)
weW
Since the weight function class W is marginalized into the state-action space (instead of trajectories). this approach is called marginalized importance sampling (MIS) (Liu et al., 2018). While theoretic guarantees in MIS under weak realizability and partial coverage assumptions are typically made for scalar values (e.g., the return (Uehara el al., 2019; Jiang& & Huang, 2020)), recently, Zhan et al. (2022); Huang & Jiang (2022); Uehara et al. (2023) have gone beyond this and derived L error guarantees for the estimators by using some strongly convex functions. Among them, the optimal value function estimator from Uchara et al. (2023) constructs the base of this work.
3 From Q* to optimal policy, the minimum requirement
Cehara et al. (2023) shows that accurately estimating optimal value function Q' under dd is possible if dP covers the optimal trajectories starting from itself. This "self-covering" assumption could be relieved and
(S (arda)
||ll denotes q weighted Le norm, i.e., ||
4

---

Published in Transactions on Machine Learning Research (11/2023)
generalized if we only require accurate estimator under some state-action distribution de, such that de is absolutely continuous w.r.t. dd, i.e., de < dd (we use Me and Te to denote the state distribution and behaviour policy decomposed from de). In fact, de provides a trade-off for the coverage requirement of the datasot: the fewer state-action pairs on the support of de, the weaker data coverage assumptions we will make. Nevertheless, how much trade-off can de provide while preserving the desired result?
In policy learning, our goal is derive an optimal policy á from the estimated Q" (denoted q). While there are methods (sce Section 4.3 for brief discussion) that induce policies from á by exploiting pessimism or data regularization, one of the most straightforward ways is to take the actions covered by de that achieve the maximum I in each state. This can be done with the help of policy ratio class B, via
B = (pe ((; TT)) and take म = Rtr
BEB
where (a 8) = ms(a 3), a) (normalized if needed). In case of infinite amount of data, we have (= as) on the support of de. With the optimal realizability of B and concentrability of Te: Eq. (3) is actually equivalent to
(oo: (²(, (-,))) =0
(4)
which guides us to exploit the coverage provided by Me: Recall that our goal is to use de trade off the coverage assumption of dº. Therefore, the question left, which forms the primary subject of this section, is
With which Me can we conclude that ât is optimal from (Pe, (,,,, Q' Q'(,, (;, = 0,
and what is the minimum requirement of it!
Since Me and de are to provide additional coverage, we also call them "covering distributions".
The remainder of this section is organized as follows: we first show why single optimal concentrability of μe is not enough in Section 3.1, and then we introduce the alternative "all optimal concentrability" in Section 3.2 and the adapted version of it in Section 3.3 to accommodate statistical errors.
3.1 The dilemma of single optimal contentrability
Single optimal concentrability is standard (Liu al., 2020; Xie al., 2021; Cheng al., 2022) when we try to mitigate exploratory data assumptions (e-g., all-policy concentrability). However, this framework suffers from conundrum if only making weak realizability assumptions: we will know that the learned policy performs well only if we are informed with trajectories induced by it-rather than the ones induced by the covered policy.
More specifically, as the optimality of could be quantified as J JJ the performance gap, we can telescope it through the performance difference lemma.
Lemma 1 (The performance difference lemma). We can decompose the performance gap
(1 (Jm,) - -Jaz)= = (MKI: - (-
Thus, with Eq. (4), if we want J Js (i.e., Js; J+) be equal to zero, it might be necessary to require Pe cover pe (ne >> ua) since the right part of the inner product in Eq. (4) is always non-positive. However, as f is estimated and is even random when considering approximating it from dataset, Me >> μ4 is usually achieved through all-policy comcentrabilityy Me > Pr for all a in the hypothesis class. Single optimal concentrability fails to provide the desired result.
For instance, consider the counterexample in Figure which is adapted from Zhan et al. (2022); Chen & Jiang (2022). Suppose we finally get the following covering distribution and policy:
if
1/2 if = 1
(s(s)
and A(s)
R
if
1/2 s = 2
Random elsewise.
5

---

Published in Transactions on Machine Learning Research (11/2023)
3
+1
5
Figure 1: The above MDP is deterministic, and we initially start from state 1. We can take actions L (left) and R (right) in each state. In states and 3, action (R) will transfer us to its left (right) hand state, and taking actions in other states will only cause a self-loop. We can only obtain non-zero rewards by laking actions in states 2 and 4, with values and 1 correspondingly. There are two trajectories that could lead the optimal 7/(1>>) return: R). } and [(1, (3, L), 4)...... We take y as the discount factor.
7
While Me achieves single optimal concentrabilliy and म achieves the maximized value of Q* in each state on the support of pe. & is not an optimal policy since it would end up with 0 return.
Proposition 2. Assuming that there erist 9, a and a state-action distribution d, such that (i; dataset coverage) d > dy. for an optimal policy x²; (it; performance of the eslimation oraele) l|Q - -qllă 0,2 (tit; export from Q) (ū(,,T)) ((-,*)()))))))) = 0 (cf. Eq. 4; u is the margin of d). There erist MDPs with above properties satisfied such that J,.. Ja 1/(1--1 1/(1-)).
How gap assumptions avoid this While both Chen & Jiang (2022) and Uehara et al. (2023) consider single optimal concentrability and weak realizability assumptions (Uchara et al. (2023) also assumes addi- tional struct ures of the dataset), the gap (margin) assumptions ensure that only laking x² as मे could achieve Eq. (4). Chen & Jiang (2022) also shows that with the gap assumption, we can even use a value-based algo- rithm to derive a near-optimal policy without accurately estimating Q*, Nevertheless, these gap (margin) assumptions only apply for part of MDPs.
Remark 1. While the gap assumption made in Ozdaglar et al. (2022) is applicable to all MDPs, their sample complexity depends on concentration coefficient appearing nowhere in their assumptions. Further, the upper bound of this constant is not even clarified.
3.2 All-optimal concentrability
While single optimal concentrability suffers the hardness revealed before, there is still an alternative for the exploratory covering Me: which is shown in the following lemma:
Lemma 3 (From advantage to optimality). If pe covers all distributions induced by non-stationary optimal policies (i.e., D> Pr for any * and Eq. (4) holds, then â is optimal and Js = J².
Remark 2. Non-stationary policies are frequently employed in the analysis of offline RT (Munos, 2003: 2005; Scherrer Lesner, 2012; Chen & Jiang, 2019; Liu et al., 2020). If we make the gap assumption, the "all non-stationary" requirement is discardable since the action in each state that could lead to the optimal return is unique.
Remark 3. Wang et al. (2022) also utilizes the all-optimal concentrability assumption, but they consider the tabular setting and they require additionally gap assumptions to achieve the near-optimal guarantees.
We now provide a short proof of Lemma 3, showing by induction that मं the non-stationary policy that adopts à at the beginning O-th to i-th (include the i-th) steps and then follows - optimal.
2this is stronger than the I norm

---

Published in Transactions on Machine Learning Research (11/2023)
Proof. We first rewrite the telescoping equation in the performance difference lemma as
(1=2)(Jx; J (1## (; (²(m)²))
(5)
= = 0z (*, (()(( + (uz, 14::00 -
(6)
(P 0:i (-,,;))) - (m)m))))))))
(7)
where 1 denotes the i-th to j-th steps (include the i-th and j-th) part of Pn- Thus, the optimality of fte only depends on the first 0-th to i-th steps, and 4 is optimal if this part is on the support of Me- Now we inductively show that, for any natural number i, the initial 0-th to i-th steps part is covered:
The step-0 part of us (i.e., (1 - =))o)) is on the support of since there is some (non-stationary) optimal policy nt covered by it,
Me 2 Mr 2 44-
Therefore, (0 (*. Q*(, O. From Eq. (7), Ao is optimal.
We next show that ft is optimal (which means that it's covered (e), then the first 0-th to (i+ 1)-th steps part of ps is covered by Pe, which means that ft+1 is optimal. This comes from the fact that the initial 0-th to (i + 1)-th sleps part of the state distribution induced by a policy only depends on its previous 0-th to i-th decisions:
0:++1 0:++1
Me > ua; >>
ps Ps
From Eq. (7), As+1 is optimal.
Thus, for any >> 0, there exists natural mumber 2 log, Vine such that
J S J - S J (J+. - + Vmxx S g max S
where J denotes the i-th to j-th steps part of the return. Therefore, Ω is optimal.
Consequently, instead of the exploratory data assumption, all non-stationary optimal coverage is sufficient for policy optimization.
3.3 Dealing with statistical error
While Lemma 3 is adequate at the population level (i.e., with an infinite amount of data), covering all non- stationary optimal policies is not enough when considering the empirical setting (iee. with finite samples) due to the introduced statistical error. This motivates us to adapt Lemma 3 with a more refined Pe-
Assumption 1 (All near-optimal concentrability). We are given with covering distribution d, such that its state distribution part Pe covers the distributions induced by any non-stationary Ee ncar-optimal policy =:
M5 Mc
S Ce.
Vi
II
(8)
Sc.non
20
We call policy и is near-optimal if - and denote II as the class of all non-stationary near-optimal policies. We also define = suppress the extreme cases, With this refined Me, we can now derive the optimality of a even with some statistical errors.
Lemma 4 (From advantage to optimality, with statistical errors). If (pe, (*(;a) (²(,m²))) 2 and Assumption holds with e, 2 Cae A is C.E near-optimal.
1-7,
1-y
We defer the proof of this lemma to Appendix C.1.
Remark (hh asymptotic property of Ez). One of the most important properties of all near-optimal concentrability is that & depends on the statistical error, which decreases as the amount of data increases.

---

Published in Transactions on Machine Learning Research (11/2023)
4 Algorithm and analysis
After discussing the minimum requirement of estimating Q*, this section will demonstrate how to fulfill it and accomplish the policy learning task. Our algorithm, which is based on the optimal value estimator from Uehara et al. (2023), follows the pseudocode in Algorithm 1.
Algorithm 1: VOPR (Value-Based Offline RL with Policy Ratio)
Input Dataset D value function class 2, distribution density ratio class W, policy ratio function class B, and covering distribution de
Estimate the optimal value function 4 as
i = argmin max [(de, 9, w)
(9)
gE wEW
where
Í(d, q, = 0.5B. (s, + ND (ND)))))
Σ
(y - a(s,a))
(10)
2 Derive the approximated optimal policy ratio:
3 argmax En,
BEB
Output: î = n
We organized the rest of this section follows: first discuss the trade-off provided by the additional covering distribution de and how to deduce de in reality in Section 4.1; we then provide the finito-sample analysis of Algorithm and its proof sketch in Section 4.2; we finally conclude this section by comparing our algorithms with the others in Section 4.3.
We defer the main proofs in this section to Appendix D.
4.1 Data assumptions and trade-off
As investigated in recent works (Huang & Jiang, 2022; Uchara et al., 2023), value function estimation under a given distribution requires a dataset that contains trajectories rolled out from it. Thus, our data assumption is as follows.
Assumption 2 (Partial concentrability from de). The shift from dd to the induced state-action distribution by x² from de is bounded:
dee
S Cp.
(11)
d
It clear that with Assumption 2, de is also covered by dP, Proposition 5. If Assumption 2 holds, by definition of ddc,ny:
de d
ddm.: (11 7)
Co 1 S 1-7
S
d0
We now clarify the order of the learning process: we are first given with a dataset. D with some good properties; then we try to find a d, from the support of the state-action distribution of D through some inductive bias (with necessary approximation); finally, we apply Algorithm 1 with and de.
The choice of de constructs a trade-off between the knowledge about optimal policy and the requirement of data coverage. On the one hand, the most casual choice of d, is dD (as in Uehara al. (2023)), which
8

---

Published in Transactions on Machine Learning Research (11/2023)
means have no prior knowledge about optimal policies. Employing dº as de will not only requires the dataset to cover unnecessary suboptimal trajectories, but also makes the dataset non-monotonic (adding new data points to it would break this assumption). On the other hand, if we have perfect knowledge about optimal policies, Assumption 2 could be significantly alleviated. More concretely, if de strictly consists of the stale-action distribution of trajectories induced by near-optimal policies, our data assumption reduces to the per-step version of near-optimal concentrability.
Lemma 6. If de is linear combination of the state-action distributions induced by non non-stationary e near- optimal policies II E,non under a fized probability measure X:
de = J dzd)()).
(12)
I1j,oon
And dP covers all admissible distributions of II. nnn''
da
A T IT sono iE N,
S SC,
dD
where da denoles the normalized distribulion of the i-th step part of dr. The distribution shift from dp is bounded as
de d
SC.
While the above case is impractical in reality, it reveals the power of this inductive bias: the more auxiliary in- formation we obtain about optimal paths, the weaker coverage assumptions of the dataset are required.
4.2
samile guarantee
We now give the finite-sample guarantee of Algorithm 1, but before proceeding, we should state necessary function class assumptions. The first are the weak realizability assumptions:
Assumption 3 (Realizability of W). There exists state-action distribution density ratio w" W such that w² o d =
Assumption (Realizability of B). There exists policy ratio 3 e such that 3 me oद and for all E SS (s,
Assumption (Realizability of Q). Q contains the optimal value function: Q* e Q.
On the other hand, we gather all the bounding assumptionss ions here.
Assumption (Boundness of Q). For any g Q, we assume q E (8 x A [0, Vmax))
Assumption 7 (Boundness of B). For any 3 E B, we assume 3 E (S x A + [0, Ug)).
Assumption 8 (Boundness of W). For any E W, assume (S x A [0, Uwl).
Remark (Validity). The invertibility -= is shown by Lemma 11 in Appendix B.1. While Assump- tions and actually subsumes Assumption 2, we make it explicit for clarity of explanation. Assumption 4 implicitly assumes that ne covers Tł, this can easily be done by directly choosing π. as ne.
Remark 6. Although we include the normalization step in Assumption 4, this can also be achieved with some preprocessing steps.
Remark 7. There is an overlap in the above assumptions: we can derive policy ratio class B directly from W and Q
With these prerequisites in place, we can finally state finite-sample guarantee.

---

Published in Transactions on Machine Learning Research (11/2023)
Theorem 1 (Sample complexity of learning near-optimal policy). If Assumptions 1, 2, 3, 4, 6, 7 and hold with Ee 2 4C.Uev/Fsar where
2 2log(2(0)W1/5)
Sata Uw Vvvx
ND
then with probability at least - 8, the output a from Algorithm 1 is near-optimal:
4C.UBVEsta
J Jx
Proof sketch of Theorem 1 As can obtain the near-optinality guarantee via Lemma 4, the remaining task is to approximate Eq. (4). This comes from the following two lemmas.
Lemma 7 (L2 error of & under de, adapted from theorem 2 in Uchara et al. (2023)). If Assumptions 2, 8, 5, 6 and 8 hold, with probability at least - 8, the estimaled á from Algorithm satisfies
l Q" lla..2 /
Lemma 8 (From L distance to Eq. (4)). If Assumplions 4 and 7 hold,
(Q"(s (;. 22UB Q l1a,,.
Combine them, we have that with probability at least 6,
(Q"(, (.).) $2UBsl9 Q*Ilaa. 2UB Q*1la.2 S 4U
4.3 Comparison with related works
We now provide a brief comparison of our method with some related algorithms.
Algorithms with gap assumptions Chen & Jiang (2022) and Uchara et al. (2023) assume that there are (soft) gaps in the optimal value function, which only satisfied by part of MDPs, whereas our goal is to deal with general problems. Moreover, while our algorithm is based on the optimal value estimator proposed use the policy ratio to ensure finite distribution shift and our near-optimality
by Uehara et al. (2023), guarantec does not require the soft margin assumption. Besides, Uchara et al. (2023) use d' as de, assuming that the dataset covers the optimal trajectories from itself. This assumption is non-monotonie and hard to satisfied in reality. Instead, we propose using an additional covering distribution de as an alternative, which can effectively utilize the prior knowledge about the optimal trajectorics and trade off the datasct requirement.
Algorithms with behavior regularization Zhan et al. (2022) behavior regularization to ensure that the learned policy is close to the dataset. Nevertheless, the regularization makes the optimality of the learned policy unprovable without careful control on the regularization. The SMQP from Uchara et al. (2023) also uses regularizations, but its sample complexity is polynomial w.r.t. [.A..
Algorithms with pessimism the face of uncertainty These algorithms (e.g., Jiang & Huang (2020); Liu al. (2020); Xie et al. (2021); Cheng et al. (2022); Zhu et al. (2023)) are often closely related approximate dynamic programming (ADP). They "pessimistically" estimate the given policies and update (or choose) policics "pessimistically" with the estimated value functions. However, the evaluation step used in these algorithms always requires the strong realization of all candidate policies' value functions, which algorithm avoids.
Limitations of our algorithm On the one hand, the additional covering distribution may be hard to access in some scenarios, leading back to using d" as de- On the other hand, although mitigated with increasing datasct size, the assumption of covering all ncar-optimal policies is still stronger than the classic single-optimal concentrability. In addition, the "non-stationary" coverage requirement is also somewhat restrictive.
10

---

Published in Transactions on Machine Learning Research (11/2023)
5 Conclusion and further work
This paper present VOPR, new MIS-based algorithm for offline RL with function approximations. VOPR is inspired by the optimal value estimator proposed in Uchara et al. (2023), and it circumvents the soft margin assumption in the original paper with the near-optimal coverage assumption. While it still works if using the data distribution as the covering distribution, VOPR can trade off data assumptions with more refined choices. Compared with other algorithms considcring partial coverage, VOPR does not make strong function class assumptions and works under general MDPs. Finally, despite the successes, a refined additional covering distribution may be difficult to obtain, and the near-optimal coverage assumption is still stronger than single optimal concentrability, We leave them for further investigation.
References
András Antos, Rémi Munos, and Csaba Szepesvári. Fitted q-iteration in continuous action-space mdps. In NIPS, 2007.
Leemon C. Baird. Residual algorithms: Reinforcement learning with function approximation. In Interna- tional Conference on Machine Learnêng, 1995.
Jinglin Chen and Nan Jiang. Information-theoreete considerations in batch reinforcement learning. ArXiv, abs/1905.00360, 2019.
Jinglin Chen and Nan Jiang, Offine reinforcement learning under value and density-ratio realizability; the power of gaps. ArXiv, abs/2203.13935 2022.
Ching-An Cheng, Tengyang Xie, Nan Jiang, and Alekh Agarwal. Adversarially trained actor critic for oflline reinforcement learning. ArXiv, abs/220 2bs/220.002446, 2022.
Damien Erust, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning. J. Mach. Learn. Res., 6:503- 556, 2005.
Amir Massoud Farahmand, Rémi Munos, and Csaba Szepesvari. Error propagation for approximate policy and value iteration. In NIPS, 2010.
Dylan J. Foster, Akshay Krishnamurthy, David Simchi-Tevi, and Yunzong Xu. Offline reinforcement learning: Fundamental barriers for value function approximation. In Annual Conference Computational Learning Theory, 2021.
Omer Gottesman, Fredrik D. Johansson, Joshua Meier, Jack Dent, Donghun Lee, Srivatsan Srinivasan, Linying Zhang, Yi Ding, David Wihl, Xuefeng Peng, Jiayu Yao, Isaac Lage, Christopher Mosch, Li wei H. Lehman, Matthieu Komorowski, A. Aldo Faisal, Leo Anthony Celi, David A. Sontag, and Finale Delhi.Vellz. Evaluating reinforcement learning algorithms in obscrvational health sottings. ArXiv, abs/1805. 01/118551229. 12298, 2018.
Omer Gottesman, Fredrik Johansson, Matthicu Komorowski, Aldo Faisal, David Sontag, Finale Doshi- Volez, and Leo Anthony Celi. Guidelines for reinforcement learning in healthcare. Nature Medicine, 25:16 18, 2019.
Audrey Huang and Nan Jiang. Beyond the return: Off-policy function estimation under user-specified error-measurigg distributions. ArXiv, abs/2210.15543,, 2022.
Nan Jiang and Jiawei Huang. Minimax value interval for off-policy evaluation and policy optimization. arXiv: Learning, 2020.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline rI? In International Conference Machine Learning, 2020.
Dmitry Kalashnikov, Alex Irpan, Peter Pastor, Julian Ibarz, Alexander Herzog, Eric Jang, Deirdre Quillen, Ethan Holly, Mrinal Kalakrishnan, Vincent Vanhoucke, and Sergey Levine. Qt-opt: Scalable deep rein- forcement learning for vision-based robotic manipulation. ArXiv, abs/1806. 10293, 2018.
11

---

Published in Transactions on Machine Learning Research (11/2023)
Aviral Kumar, Justin Fu, G. Tucker, and Sergey Levine. Stabilizing off-policy q-learning via bootstrapping error reduction. In Neural Information Processing Systems, 2019.
Romain Laroche and Paul Trichelair. Safe policy improvement with baseline bootstrapping. ArXiv, abs/1712.06924, 2017.
Jongmin Lee, Wonscok Jeon, Byung-Jun Lee, Joëlle Pincau, and Kce-Eung Kim. Optidice: Offlie policy optimization via stationary distribution correction estimation. In International Conference on Machine Learning, 2021.
Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. Breaking the curse of horizon: Infinito-horizon off-policy estimation. In Neural Information Processing Systems, 2018.
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Provably good batch reinforcement learning without great exploration. ArXiv, abs/2007.0820 082022, 2020.
A.S. Manne. Lincar programming and sequential decisions. In Management Science, volume 6, pp. 259-267, 1960.
Rémi Munos. Error bounds for approximate policy iteration. In International Conference on Machine Learning, 2003.
Rémi Munos. Error bounds for approximate value iteration. In AAAI Conference on Artificial Intelligence, 2005.
Rémi Munos. Performance bounds in Ip-norm for approximate value iteration. SIAM J. Control. Optim.. 46:541-561 -61,, 2007.
Rémi Munos and Csaba Szepesvari. Finite-time bounds for fitted value iteration. J. Mach. Learn. Res., 9: 815 857, 2008.
Ofir Nachum, Bo Dai, Ilya Kostrikov, Yinlam Chow, Lihong Li, and Dale Schuurmans. Algaedice: Policy gradient from arbitrary experience. ArXiv, abs/1912.02074, 2019.
Asuman E. Ozdaglar, Sarath Pattathil, Jiawei Zhang, and K. Zhang. Revisiting the iinear-roggraminn framework for offline rl with general function approximation. ArXiv, abs/2212.13861, 2022.
Martin L. Puterman. Markov decision processes: Discrete stochastic dynamic programming. In Wiley Series Probability and Stalislics, 1994.
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart J. Russell. Bridging offline reinforce- ment learning and imitation learning: A tale of pessimism. IEEE Transactions on Information Theory, 68:8156-8196, 2021.
Paria Rashidinejad, Hanlin Zhu, Kunhe Yang, Stuart J. Russell, and Jiantao Jiao. Optimal conservative offline rl with general function approximation via augmented lagrangian. ArXie, abs/2211.00 1007100016, 2022.
Bruno Scherrer and Boris Lesner. On the use of non-stationary policios for stationary infinite-horizon markov decision processes. In NIPS, 2012.
Samarth Sinha and Animesh Garg, S4rl: Surprisingly simple self-supervision for ofllin reinforcement learn- ing. ArXiv, 0tt/22033.63266 2021.
Yuda Song, Yi Zhou, Ayush Sekhari, J. Andrew Bagnell, Akshay Krishnamurthy, and Wen Sun. Hybrid rl: Using both offline and online data can make efficient. ArXiv, abs/ abs/22210006118 2022.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018.
12

---

Published in Transactions on Machine Learning Research (11/2023)
Shengpu Tang, Maggie Makar, Michael W. Sjoding, Finale Doshi-Velez, and Jenna Wiens. Leveraging factored action spaces for efficient offline reinforcement learning in healthcare. ArXiv, abs/ 2as/2305.01735 2023.
Masatoshi Uehara and Wen Sun. Pessimistic model-based oflline reinforcement learning under partial cov- erage. In International Conference on Learning Representations, 2021.
Masatoshi Uehara, Jiawei Huang, and Nan Jiang. Minimax weight and q-function learning for off-policy evaluation. In International Conference on Machine Learning. 2019.
Masatoshi Uchara, Nathan Kallus, Jason D. Lee, and Wen Sun. Refined value-based offline rl under realiz- ability and partial coverage. ArXiv, (bs/2302.02392, 2023.
Ruosong Wang, Yifan Wu, Ruslan Salakhutdinov, and Sham M. Kakade. Instabilities of offline rl with pre-trained neural representation. In International Conference on Machine Learning, 2021.
Xinqi Wang, Qiwen Cui, and Simon Shaolei Du. On gap-dependent bounds for offline reinforcement learning. Arxi abs/2206.001777, 2022.
Tengyang Xie and Nan Jiang. Batch value-function approximation with only realizability. ArXin, abs/2008.04990, 2020a.
Tengyang Xie and Nan Jiang. Q* approximation schemes for batch reinforcement learning: A theoretical comparison. ArXiv, abs 220//2003.002224 2020b.
Tengyang Xie, Ching-An An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-connsstent pessimism for offline reinforcement learning. In Neural Information Processing Systems, 2021.
Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason D. Lee. Offline reinforcement learning with realizability and singlo-policy concentrability. ArXiu, abs/2202. abs/2202.04633, 2022.
Hanlin Zhu, Paria Rashidinejad, and Jiantao Jiao. Importance weighted actor-critic for optimal conservative offline reinforcement lcarning. Arxiv, hbs/2201..2714, 2023.
13

---

Published in Transactions on Machine Learning Research (11/2023)
A Notations
Table 2: Notations
S
state space
A
action space
Q
state-action value function class
W
state-action distribution ratio function class policy ratio function class
3
members of expected return of the policy и from the initial state distribution μo state value function for policy state-action value function for policy æ optimal state value function optimal state-action value function uniform measure of A, S, or S x A, depending on the context dataset used in the algorithm state-action distribution of dataset.
J.
V
Q
V*
Q
v
d0
state distribution of dataset behaviour policy
de
the additional covering distribution
Pe
state distribution (margin) of the additional covering distribution
Te
policy of the additional covering distribution inner product of a and b, usually as I ab du
(a, b)
fi f2
(fi f2) a) (s, f2,, normalizing it if needed (e.g., density)
p x
(j (s) = (())
T*
Bellman optimality operator, T* = R(s,a) + (BBo (max initial state distribution the i-th to j-th steps part of Pr d2 absolutely continuous w.r.t. d1
po
di >> d2
dr,s
normalize i-th step part of state-action distribution induced by m state-action distribution induced by from d
da,
policy take in the previous 0-th to i-th (include the i-th) steps, and take of after this (a s) (a ()8(s, SA Te(a 8)3(s, a)dv(a)
TT 8,non
the class of all non-stationary near-optimal policies
P.
state-action transition kernel with policy conjucate operator of some operator
O*
While n, ,4 and d are mainly used to denote the Radon Nikodym derivatives of the underlying probability measures w.r.t. V, we sometimes also use them represent the correspondent distribution measure with abuse of notation.
B Helper Lemmas
B.1 Properties of Pr
We first provide some properties of P. (for any policy σ) as an operator on the -pace of S x A, and similar results should also hold for transition operators with policies defined on S. Note that the integrations of the absolute value of the functions considered in this subsection are always finite, which means that we can change the orders of integrations define the inner product (q. d) SSXA q(s, a)d(s, a)).
Fubini's Theorem. As we will consider conjugate operators, we
Lemma 9. Ps is linear.
14

---

Published in Transactions on Machine Learning Research (11/2023)
Proof. Recall the definition of Px:
P) / x(d' s 5,
SSXA
For any d2 (8 A);
Pa(ad11 + a2d2)(6
SSX x(d' (8) | + (zd2)( a)dv(ss)
I ISKA ar P(s (s, + Sxx
a2z((d s | ad)
=a1 x(d') Pss (s, + as 5xA
x(d') s')P(s' s, (, asd))sss))
SSA
-a1 (2di(o',ad) ('') + a2Prdd((s,,a)
This compeletes the proof.
Lemma 10. The adjoint operator of Pa is
())(8,0) = 1 als' d')(aa (s') ss,a)du(s',a)) a²).
SXA
Remark Intuitively, we can see Pad(s', a') as one-step forward of d, such that we start from (s,a) d, transit into s' P( s,a) and lake a' n(. 8)). Also, we view (7 a) one-step backward of g. such that compute the value of as through the step transferred state-action distribution with the help of
Proof. Consider the inner products (g, Pad) and (Pa d), we should prove that these two are equal. By definition,
(g. Pad) = / q(s':a") / F(d'l s') s, a)du(s, adddsss a) du(s',a')
5xA
5XA
1
JSXAU
and
d) = I d(s,a) I/ a(s afdddd)mld Ps) a, ad) du((sa)) (d)duss,)))
JSXA
- ((s,))((ss d')=(d') Ps') Is a)dds (d)(s
-J a(d ( P)) s, a)du(s (dd(s d').
(Fubini's Theorem)
This completes the proof.
Lemma. || = | 1
Remark 9. This upper bound should be intuitive since that Pa can be seen as probability transition kernel from S x A to itself.
15

---

Published in Transactions on Machine Learning Research (11/2023)
Proof. Fix any S, E A, we define p(s',d') P(s' s,a) (s)), By Fubini's theorem, have that
1 SSX
/ pdv
1plli,e
1pldu=
ISXA
S
/ P(s') s, I ('ddedd))drss)
Is P(s' s,,a) [/x vild (d)ddu(ad) du(s')
P(s' |s, (s))))
For another function q on S such that |1 S 1, can use Hölder's inequality, which yields
leullie S lolli, 1. Thus, for any EESa E A, and function q with I|aloo, S1,
=f If a(s'sa')<Ta'' s') I ss a. d') |1q9|1,, S 1.
P) =
SxA
So, we have that
1 = |P
max
| 1 max Ilall 51 ES
Ph $1.
This completes the proof.
Lemma 11. / yr is invertible and
(1 (1-7Pa)-1 Σ (7Pa)'
2=0
Proof. Since | 1, Σ (yPx)' converges. Take multiplication
==0
86
00
(1->Pa)
(7Px) Σ (Y)P)) [()Pa)
1=0
(=0
=(>Pa) =1.
This completes the proof.
Proposition 12. By definition, da, (1 7) 2
((ppa'dd (1
B.2 Other useful lemmas
Lemma (Performance difference lemma). We can decompose the performance gap as
- (Jm) Jaz) (uT, (m)(smm) (. (2))))
16

---

Published in Transactions on Machine Learning Research (11/2023)
Proof. By definition,
(Mm, (. - (x)(1 -B, R(:, + (/ooaa(())ooPPPiaallll0a. T2)) - Qm (2))
-Bgupe [[(;T]]] - Benper [ Q (s', n2)]]
Es [Q (:aaa))))
Esuay
[((:TT)]] + |
Bonunn [mm
Esuper [R(: EBsupe (S, (1 - B (4 (8, T2)]
Egnuen [TTo (::T2))]
= E
[R(. [T] - (1 - (l-mo
-(1 7) Jx2)
The first equality comes from Bellman equation, and the fourth equality comes from the definition of Ma This completes the proof.
C Detailed proofs for Section 3
C.1 Proof of Lemma
Lemma (From advantage to optimality, restatement of Lemma 4), If (Mo, -(,,))(((((())) 2 - and Assumption holds with E 2 I-7'
Cae
$ C.e near-optimal.
C.e ncar-optimal for any i e N: Proof. We begin with using induction to prove that n is 1-7
We first show that mo conclude that
Cet I-
near-optimal. From Assumption 1, we can use any क πT*
Ma/ 1m//1-1)1
Co 1 1-7
S
He
00
Me
Thus, we can the show optimality of fo by the advantage:
(Noo: (,)
#b) ())==)))
= (m 0:0 Q* (²(,z()) 10000 (0(()=)) (,,,z()))
= (u ()) - (²(,=())
= (1 ()o, Q' Q'(mm²))
Ce (Mes (',,, Q*(s -Q*(st)-Q0(, (-)))) is non-positive)
-
Cee.
By performance difference lemma,
(1 (J)R -J²) -(pa, (²( (*(m²)))
Cce.
Cae I- near-optimal, #441 is - near-optinal. Since that मे is C.e. the distribution shift from Pe to pe; is bounded, which means,
Next, we show that Å is
1-y optimal,
0+++1
0i+l
7
Mg.
<
S
Se.
He
He
He
17

---

Published in Transactions on Machine Learning Research (11/2023)
Then, have
(PR ('( - ((()
0it1 Q"(,, Q" + P841 Q(((. Q" (())=()))))))))
= RR
(Matt 0uil (+, - Q(((m)))
(pA maitl (;, (²(s
Coleer Q'(, (²(,)²))
(Q*(; - (-, is non-positive)
Cee.
By performance difference lemma,,
(J=7)(Amm: JJ) --)= 1 (1, (t, (x, - Co
Therefore, #141 is CaE. 1-y near-optimal.
Thus, for any >> O, there exists natural number i 2 log, Umav such that
CrE I-7
C,E tG,
J - Ja S J 0: S J (Js. - - Vimax) S
+ xtt Vmax S
Cat near-optimal. where Jkl denotes the i-th to j-th steps part of the return. Therefore, A I-7
Detailed proofs for Section 4
D.1 Proof of Lemma 6
Lemma (Restatement of Lemma 6). If de is a linear combination of the state-action distributions induced by near-oplimal non-slalionary policies II n, under fired probabilily mensure X:
de = J dxd)(H).
(13)
TT
And dº covers all admissible distributions of II. non'
di
V 7 E II Eoon i i N,
S.
dD
The distribution shift from dD is bounded as
C.
d
Proof. Define the state-action distribution of policy from S, a E A at step i as
(aaa"(saa") P(s, = s',a = a' |so s, = a, P(- so, ao), ~ T(. s1)...
8j P(. 18-111 ~ n( [z)
Also, define the global version of it
(s' (11- -1-) Σ
d daan,i(''
1=0
18

---

Published in Transactions on Machine Learning Research (11/2023)
We can rewrite dde.:; (s as
(M,.=((,,0)
SxA
do (9.00 da da a1 dutss,
JSXA
Jn Ionnddaaonon cattenn dx(=)
(Fubini's Theorem)
(1 (1-
{ dr (s (31, du(s, an) d)(#t)
SXA
= J11 [1 7)
00
(5 an )du((s a1) d2(7))
JSXA
i=0
00
(1
7)
di:oo (s, a) d)(5)..
1=
The last equation comes from that
7² I do (s, (s (s,
SxA
--²² I do (v.00) [/1 de (s1, (2)du((2) (o( du(s), ai)
= / UAA [T*) Sona da a)d (a an) #(02 s2)dv(a2) no (o()))du(s2).
(Fubini's Theorem)
since
7² SxA
JSXA (1-
k=0
20
-(1 7)
SXA d
=(1 7)
-(1 7)
(T ((8,,))
k=1
1:00
02.02. (s)
we get
7¹ { (4
Sxx
d (1, #(22 s2)dv((z) (0
R. (s,a).
1:00
19

---

Published in Transactions on Machine Learning Research (11/2023)
Finally, Vs A,
da ddg (s)
1:00 (8, a)
./1 (1-1)) 7)
d)(#)
d ss a)
<=
/ (1 71
7)
7" d (s, a) d)(z)
( a)
1=0
/ (1 7)
Σ
2
(1 7)
0
dz (8, 0) d2(()
d (s)
i=U
j=i
CCL - 7)
2 dx(#)
( E 11 gonon indicates म, E 11 moo
1=0 j=i
[C0 -7)²
da(#)
11
1=
Cdd(#)
11
-C.
This completes the proof.
D.2 Proof of Lemma 7
Note that the lemmas and proofs of this subsection are mainly adapted from Uchara et al. (2023), similar statements could also be found in the original paper. However, since that we use de to replace d we present them for clarity of explanation and make our paper self-contained. We refer interested readers to the original paper for another detail.
We first define the expected version of Eq. (10) as
L(d,g,w) 00. (s, a)) E (B -0. s, a)] + Ep. [1 max q(s', +r {ss
[ max g(', + [(8,a)]
where d. = dD w, and Ep... denotes taking expectation with respect to the reweighted data collecting process.
Lemma 13 (Expectation). The expected value of L(d, g, w) w.r.t. the data collecting process is [(d, w): Ex(L(d, q. w)] = L(d, w.
Proof. Since only the second term of & is random, we additional define
Ewla, w) ND
Σ
ED wo(s, a)(ss,)(7 max q(s',)) +r q(s,,a))
(s.a,n.)))
We can rearrange the expectation as follows,
EplLid, q, w)] =Ep 0..Eal (s, a)) + Lw(g, w]
(14)
-EE 0.51Ea 2 (s, aل] + ED Ew(e.w) =0.5E (s. a) + Ep [w(
(15)
(16)
20

---

Published in Transactions on Machine Learning Research (11/2023)
Then, by the iid. assumption of samples and linear property of MIS,
Ep|E(d, w)] =0.5 a)] ED
1
Σ
wos a) myxg(((ss))))))))) -
ND
=0 (8, ND
Σ
IDD
q +r a(8,
(sa,))))
=0.5 (s (s, a)] - ED (ss, a) b q - a(s
=0.5 (d (s, a)] - ((aa)dd (- R( w0ss a) B max 2(6 + - q({,
-0.5E, (g a)] + B(aaa)dd w( a) (By- max g(s :)] R(s, a) - {(s
-0.5E, ( a)] = ((aa)
E Es max ((8', -)] + R(s, a) - ((s.a)
-0.5B, ( (g) a)] + aa [ max g(5', t g a)]
-L(d, q, w).
This compeletes the proof.
Lemma 14 (Concentration). For any fired d, with probabilily at least 1 8, for any q E 2, w W,
C(d, q, w) - L(d, w) S Estat-
Proof. The statistical error only comes from Lw, as
[(d, w) - L(d, q, u/)
ED Eol w)] L(d,q, w)
(Lemma 13)
Ep E w]] - Ew(g, w)
(Eq. (16))
Since each entry of Lw is bounded:
Vg W W, [w(s,a) 47 max - s
UniVmxx
can apply Hoeffding's inequality which yields that, for any & E Q, w W, with probability at least 8/(1)))))
2 log 2lg((2(([[W1/8)
ED Lw w)] Lw(g,w) w) Uw Vmax
ND
Finally, we can use union bound, rearranging terms to get that, for any fixed d, with probability at least 8, for any E Q w E W,
2 log Q(1W1/00
L(d, w,) L(d, q, w) S Uwvmmax
Estat
N
This compeletes the proof.
Lemma 15. If w is non-negative v-a.e. (e.g., w E W), for any q: S x A + [0, Vmax),
w(d,g,w) L(d, ((d,Q", w) > 0. (Q*)²) (6> Pr: ryd Q*)
(17)
21

---

Published in Transactions on Machine Learning Research (11/2023)
Proof. This result simply comes from the definition:
g(d,g,w) [(d, Q", w)
-0.5Eal - (s)]
+ BDD max - {ss,a)] - ED_ max (*(s+)))+++++)) +r- Q*(ss
m
-0.5 - (s)]
+DD ED. max +r ((s -ED_ -
20.5E (s) (s)]
+ ED., {bp,,n((s'mm²) + - ((s EE, m²) tr -0 (s,
=0.5 (s))
ED. (') m²) - (s, a)]
=0.5 2² - (Q + (de, (yP=: =5 - 1)(a Q*))
(Rewrite the expectation with inner products)
=0.5(d, (2 + ((>P:: -Na Q*).
(conjugate)
This compeletes the proof.
]
Lemma 16. If Assumption 5 holds, with probability at least 1 - 6, for any w W and any state-action distribution d, we have
[(d. w) - C(d, Q",,,,,, w) S 2Estat.
(18)
Proof. We can docompose Eq. (18) as follows,
Q(d.q.w) C(d, Q* w) [(d, q, w) L(d, L(d, w) L(d. q, w
(1)
(2)
+ (dd, q, (0) - [(d, Q', ((())))))))))))) + A(d, ,0()(())))))))))))))")))(()))))) - C(d, (Q'))
(3)
+ C(d, Q", ((())) - C(d,Q",, ())
(6)
where ((g) = argmax L(d, g, w). For the terms above, we have that:
(2) and (3) are non-positive since the optimization process.
(1) and (4) could be bound by concentration.
For (5), as Bellman optimality equation holds,
vs S, E A, Egr [7 max (=(,)) R(s,a) - (=,))))
We have that
(5) =C(d, 2', (Q))) L(d,)) w)
-0..Ee](("""({,.c)] E DDrrr myxxx +
[0.5Ea((0)) a)) ED_ max ('((') + - Q (s, [s:a)]
r= (7 max Q"((',, ( - (s)
( max Q'(''' + (s( a]]
-B(ss))a
B. Bg mmax (3( 1] + R(s a) (s,
-E( BByr mmax Q'('', )) R(s, a) Q'
=0.
22

---

Published in Transactions on Machine Learning Research (11/2023)
Thus, conclude that with probability at least 1 8,
L(g, w) L(Q", w s C(ū, w) - [)..w) w) ((Q2)((Q")) =(0"))
(1)
(4)
L(.. w) L(i, w)) ,
=((())) ,
sEstat
(Lemma 14)
This compeletes the proof.
With lemmas above, it's time to prove Lemma 7.
Lemma (L22 error of & under de; restatement Lemma 7). If Assumplions 2, 5, 6 and 8 hold, with probabilily at least 1 5, the estimated @ from Algorithm 1 satisfies
l1q - Q" lla.2 S /
Proof. By Assumption 3, d = - de and from Lemma 15 we have
C(de,q. w²) [(de, Q", w²) 20.5(de: - ((1 -P-)x) (Q-0)) Q")) =0.5(de: d² - (Q")²) - (doQ", (g Q²)) =0.5/do. d² - (Q7)²) - (do, (- (²))
=d.5 (9 -Q7)²)
-0.5114 Q 122.22
Together with Lemma 16, with probability at least - 5,
0.51lg - 1' S L(de, G, w²) - [(de, Q,, S statt
Rearrange this and get
114 ll,,2 S 2
This compeletes the proof.
D.3 Proof of Lemma 8
Lemma (Restatement of Lemma 8). If Assumptions 4 and 7 hold,
(Q" (-, (.) 52Ubl14 - Q lla...
Proof. We can rearrange the above term as
(Q*(,= (((, =Q0', m²) A(, (()m))))))) + (2(,=t) -0: 4), (e) (a(: ()) - ().
(10 (s.m)) - Te), He) + (Ā( +) (-, Me)
(Assumption 4)
$ (1((((,)))) -()(,)))0000 - -0, 1l).) [| - Q- (1, (1) p..1
= -1 - 01l..x + 11@ 11
<2U 2|" ill4..1
The distribution shift comes from the fact that
x क
π2
π22 oc
and shifts from ne to म5 and A are both bound by Ug due Assumptions and This completes the proof.
23

---

Published in Transactions on Machine Learning Research (11/2023)
D.4 Proof of Theorem 1
Theorem (Finite sample guarantee of Algorithm 1, restatement of Theorem 1). If Assumptions 1, 2, 3, 4
5, 6, and hold with Ee 2 4C.U8 then with probability at least 8, the output from Algorithm is :car-optimal:
1-7
4C.UBVEstal
J Jx S
Proof. From Lemma 7, we have that with probability least
1 Q7 S ll4 - Q"Ildc12 S Estata
Then apply Lemma to bound the weighted advantage,
(Q" (+. m²) - (:, (m) $2UB Q' S Esta/
Finally, according to Lemma 4, ât is 4C.UB./euu optimal. This completes the proof. 1-7
24


Reviews:
[{"review_id": "eM6jnzgkKQ", "reviewer": "Reviewer_Q8GL", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper introduces a possible inductive bias/side information, which is the covering distribution, and how one can use this information to add to the information covered in the offline dataset.\n- The paper focuses on eliminating the strong realizability assumptions (a.k.a. Bellman completeness) in offline RL with general function approximation with additional assumptions. \n- The paper is well-motivated, well-written, and thoroughly compares with prior work and puts the contribution in perspective. The introduction is particularly nice and insightful, especially for outsiders of the offline RL theory.\n\nWeaknesses:\n- The covering distribution assumption is strong and its relevance to practice is not discussed. What are some practical examples in which this covering distribution is available?\n- It is unclear to me that the algorithms whose performance upper bounds worsen with the gap (such as Chen & Jiang 2022), indeed suffer from this restriction. In other words, is there a performance lower bound on these algorithms that depends on the gap?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents an offline RL algorithm with general function approximation and partial data coverage under weak realizability and additional information of a covering distribution, which covers all non-stationary near-optimal policies. The paper also discusses the tradeoff between the covering distribution accuracy and the coverage of the dataset.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Changes that would strengthen the work:\n- It is better to explain the notion of covering distribution in the abstract. \n- It seems to be helpful if the necessity of the gap assumption without the covering distribution is established (information-theoretic or even lower bound on prior algorithms).", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "hGTgm7uFVb", "reviewer": "Reviewer_phJY", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengthens\n\nTheir findings are novel, and I consider their contribution to be significant within the offline reinforcement learning theory community.\n\n* Compared to Zhan et al. (2022), they do not rely on behavior regularization. \n* Compared to Uehara et al. (2023), they do not rely on soft margins. Algortihmicwise, (2) in the above is different. \n* Compared to most offline theoretical RL works, such as Jiang & Huang (2020) and Zhu et al. (2023), they do not rely on strong realizability. \n\n\nWhile they rely on the additional assumption (a certain distribution covers all near-optimal, possibly non-stationary policies) compared to these two works, I think this additional assumption is still reasonable. \n\nI checked the central part of the proof. They appear to be correct. \n\n### Weakness \n\nIn terms of contributions, the first part of the algorithm (above 1) appears to be a straightforward adaptation of Uehara et al. (2023). Additionally, certain readers may perceive their additional assumption as potentially stringent. However, from my perspective, their core concept remains intriguing and innovative.\n\nThe main weakness of this paper is the presentation style. This paper is written in a rigorous way, and I appreciate it. However, certain sections appear challenging to understand for the majority of readers at first sight.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Their research has introduced a novel PAC offline RL algorithm under \"weak realizability\" (not encompassing realizability for all classes) and \"optimal concentrability\" (the offline distribution covers the distribution induced by the optimal policy) with an additional assumption that a certain distribution (such as the offline distribution) covers all near-optimal potentially non-stationary policies.\n\nTheir proposed method is comprised of two parts: \n* (1): Learn the optimal Q-function so that we can ensure the L2 error guarantee under the covering distribution denoted by $d_c$. \n* (2): Learn the optimal policy by setting a policy class $B$ and taking the best policy under the covering distribution $d_c$.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* Page 1: Abstract: I believe you had better explain more about *“strong realizably function classes”* and *“weak realizably function classes”* since this jargon is still not standard. I also feel that you had better mention what is “partial coverage\" since this usage might not be immediate for most standard readers. \n* Page 2: *“Drawbacks.Some works\"*: I guess you need a space. \n* Page 2: Intro: I feel you had better mention what types of algorithms you use with the covering distribution in the Intro, as I summarized in this review. Otherwise, it is hard to imagine how you use *the covering distribution* from the current intro (before reading the whole paper). \n* Page 2: *“Could be meaningless in some cases, and the actual performance of the learned policy is intractable.\"*: I do not understand what you mean by intractable. They prove that the learned policy is nearly optimal. Would you elaborate on it more? \n* Page 2: Table 1. *“We have removed additional definitions of notations for simplicity and refer the interested reader to the original papers for more detail.\"*  I am not sure this is a good strategy. Generally speaking, I feel the table should be self-contained as much as possible (I assume TMLR does not have limitations for the length of the paper?).\n    * It would be better to mention the meaning of each notation even if formally defining is too much, E.g., I personally don’t know (can't recall) what $C(Q)$ in Table 1 is even if I had read all of the papers before. Moreover, I generally believe you had better mention what each notation $w^*,w^{*}_{\\alpha}, v_{\\alpha},d_c$ roughly means\n    * What is \"Additional structure\"? I think you had probally better say something in the caption that this column corresponds to additionally imposed assumptions on top of *\"weak realizability\"* and *\"optimal concentrability\"*. \n    * Uehara et al. (2023) technically comprised of two parts. They have a result without a soft-margin; but behavior regularization. So, it might be worthwhile to include it. \n    * It might be better to add Xie et.al 2021. \n* Page 3: *“We say that a policy is optimal almost everywhere.\"* Does this mean $\\pi^{*}$ might not maximize the value function at regions whose measure is 0? \n* Page 4: Did you explain the meaning of the notation $\\|...\\|_{1,d}$? \n* Page 4: *\"With assuming the optimal….\"* (before Eq 4), I think there is a certain gap. I guess Eq. (3) where we replace $\\hat q$ with $Q^*$ is actually equivalent to $\\hat \\pi$ in (4). \n* Page 5: Lemma 2: I think you need to define $\\hat \\pi$ in (3) by replacing $\\hat q$ with $Q^*$ (as you have done in Lemma 3). \n* Page 10: *\"Nevertheless, the regularization makes the optimality of the learned policy intractable.\"* Would you elaborate more on what you mean by intractable?", "broader_impact_concerns": "Not applied", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "1wxFdLrcDk", "reviewer": "Reviewer_6vXX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The proposed algorithm provides finite-sample guarantees under weaker conditions compared to prior research.\n\nWeaknesses:\n\n1. The paper's clarity and coherence need improvement, as some parts are challenging to comprehend.\n\n(1) It's unclear why Eq. (3) is equivalent to finding a policy $\\pi$ that satisfies Equation 4. The correctness only seems apparent when $\\hat{q}=Q^*$.\n\n(2) In Lemma 1, there's a lack of definition for the function $J$ and distribution $\\mu_{\\pi}$. It remains unclear whether distribution $\\mu_{\\pi}$ originates from the initial distribution $\\mu_0$, the covering distribution $\\mu_c$, or the data-collection distribution $\\mu_D$.\n\n(3) The notation $\\mu_a >> \\mu_b$ requires further elaboration.\n\n2. The rationale for considering the covering distribution $\\mu_c$ isn't adequately explained and needs more elaboration.\n\n(1) Due to the absence of the function $J$ definition, the clarity of the sub-optimality gap definition is compromised. Consequently, it remains unclear why it's sufficient to seek a policy satisfying Equation (4). The potential influence of states outside the $\\mu_c$ distribution on the sub-optimality gap also remains unaddressed.\n\n(2) How does the covering distribution $\\mu_c$ impact Algorithm 1? It seems that this distribution solely determines the regularization term. It might be more plausible that the covering distribution would further influence the dataset $D$, possibly involving summation over sub-datasets $d_c$.\n\n(3) According to Section 4, the key advantage of the covering distribution $\\mu_c$ arises from Assumption 2. With an appropriate distribution, Assumption 2 can be easily satisfied (given a small $C_D$). However, in prior research, partial concentrability seemed to focus solely on the distribution $d_{\\pi^*}$ (the optimal policy starting at the initial distribution $\\mu_0$), seemingly independent of the dataset $D$ or $d_c$. Could the author provide deeper insights into this assumption?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This study centers around offline reinforcement learning employing general function approximation and introduces a novel algorithm named VOPR. In contrast to prior research, the author incorporates an auxiliary covering distribution that effectively reduces the need for excessive trajectories, thereby facilitating the learning of a nearly optimal policy. Furthermore, the proposed algorithm offers finite-sample guarantees based on relatively lenient conditions, encompassing weak realizability and partial coverage assumptions tied to the selected covering distribution.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See Weakness.", "broader_impact_concerns": "There is no concern about the broader impact.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new analysis of offline RL under weak realizability and optimal concentrability with the new assumption of accessing an additional covering distribution. The reviewers are in consensus that this work relaxes the assumptions in many previous works e.g. Bellman completeness, soft gap assumptions, which is a nice contribution. They agree that this paper should be accepted to TMLR.
Decision: Accept (poster)