Bi-Level Offline Policy Optimization with Limited Exploration
Authors: Wenzhuo Zhou
Venue: NeurIPS 2023 poster (2023)
Keywords: Offline Reinforcement Learning
Sample Efficiency
Regret Bound
Data Coverage
TL;DR: We develop a novel model-free offline policy optimization algorithm for fixed datasets without sufficient exploration.

Abstract: We study offline reinforcement learning (RL) which seeks to learn a good policy based on a fixed, pre-collected dataset. A fundamental challenge behind this task is the distributional shift due to the dataset lacking sufficient exploration, especially under function approximation. To tackle this issue, we propose a bi-level structured policy optimization algorithm that models a hierarchical interaction between the policy (upper-level) and the value function (lower-level). The lower level focuses on constructing a confidence set of value estimates that maintain sufficiently small weighted average Bellman errors, while controlling uncertainty arising from distribution mismatch. Subsequently, at the upper level, the policy aims to maximize a conservative value estimate from the confidence set formed at the lower level. This novel formulation preserves the maximum flexibility of the implicitly induced exploratory data distribution, enabling the power of model extrapolation. In practice, it can be solved through a computationally efficient, penalized adversarial estimation procedure. Our theoretical regret guarantees do not rely on any data-coverage and completeness-type assumptions, only requiring realizability. These guarantees also demonstrate that the learned policy represents the ``best effort'' among all policies, as no other policies can outperform it. We evaluate our model using a blend of synthetic, benchmark, and real-world datasets for offline RL, showing that it performs competitively with state-of-the-art methods.

Bi-eevel Offline Policy Optimization with Limited Exploration
Wenzhuo Zhou Department of Statistics University of California Irvine venzhuz3Quci. .dd
Abstract
We study offline reinforcement learning (RL) which seeks to learn a good policy based on a fixed, pre-collected dataset. A fundamental challenge behind this task is the distributional shift due to the dataset lacking sufficient exploration, espe- cially under function approximation. To tackle this issue, propose bi-level structured policy optimization algorithm that models a hierarchical interaction between the policy (upper-level) and the value function (lower-level). The lower level focuses on constructing a confidence set of value estimates that maintain sufficiently small weighted average Bellman errors, while controlling uncertainty arising from distribution mismatch. Subsequently, at the upper level, the policy aims maximize conservative value estimate from the confidence set formed at the lower level. This novel formulation preserves the maximum flexibility of the implicitly induced exploratory data distribution, enabling the power of model extrapolation. In practice, it can be solved through computationally efficient, penalized adversarial estimation procedure. Our theoretical regret guarantees do not rely on any catt-coverage and completeness-tye assumptions, only requiring realizability. These guarantees also demonstrate that the learned policy represents the "best effort" among all policies, as other policies can outperform it. We eval- uate our model using blend of synthetic, benchmark, and real-world datasets for offline RI, showing that it performs competitively with state-of-the-an methods.
1 Introduction
Offline reinforcement learning (RL) is a task to learn a good policy using only a pre-collected, fixed dataset, without further exploration with the environment. This distinctive characteristic positions offline RL as a promising approach for solving real-world sequential decision-makin problems in healthcare [35, 61], financial marketing [46], roboties [47] and education [32], as acquiring diverse or expert-quality data in these fields can be costly or practically unattainable.
Arguably, two of the biggest challenges in offline RL are the distributional shift between the data- generating distribution and those induced by candidate policies, and the stringent requirements on the properties of function approximation [28]. It has been observed that, in practice, the distributional mismatch often results in unsatisfactory performance of many existing algorithms, and even amplify- ing with function approximation [18, 27]. Many prior works [39, 13, 14] crucially rely a global data-coverage assumption and completeness-type function approximation condition in a technical sense. The former necessitates that the dataset contain any state-action pair with lower bounded probability so that the distributional shift can be well calibrated. The latter requires the function class be closed under Bellman updates. Both assumptions are particularly strong and are likely to be violated in practice [58]. Consequently, algorithms that depend on these assumptions may experience performance degradation and instability [52]. Therefore, erucial to develop novel algorithms that relax these assumptions, offering robust and widely applicable solutions for real-world scenarios.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

To address the aforementioned challenges in offline settings, one fundamental principle is the concept of pessimism, which aims to maximize rewards in the worst possible MDP consistent with the offline dataset [18, 53]. In practice, these methods have generally been shown to be more robust when coverage assumptions are violated [27].
Although many such pessimistic algorithms have been developed, very few works can tackle data- coverage and function approximation issues simultancously, while establishing strong regret guaran- lees. For instance, deep offline RL algorithms [18, 25, 23J exhibit impressive empirical performance, but their theoretical consisteney guarantees are limited tabular Markov decision processes (MDPs). The works of [30, 41, 22, 53, 56, 58, 10] relax the global coverage to partial coverage condition, wherein the offline data only covers a single comparator policy. However, all of these methods require Bellman completeness for the function class. The most recent works [9, 59] take a significant step towards relaxing Bellman completeness to realizability, that the function class can capture the target ground-truth function. Nonetheless, these algorithms are unable to provide meaningful regret guarantee without any data-coverage assumption (when both global and partial coverage fails), and also empirical evaluations are absent. Even without additional conditions, the learned policies of these algorithms can only compete with the (Bellman flow) optimal policy, resulting in lack of robustness when the optimal policy is not covered by data, a situation that frequently occurs. Due to page limit, we have only discussed the closest related work here, and the rest is deferred to Appendix.
Our contribution. In this paper. we develop a provably sample-efiie cemlee-efficien offline RL framework. Our coommation-theoretee algorithm is designed based on the concept of bi-level (upper and lower level) structured optimization, which leads to hierarchical interpretation and naturally enjoys learning stability and algorithmic convergence from a game-theoretic perspective. In particular, at the lower level, one component is to construct a confidence set with consistent value estimates regarding the appropriately small weighted average Bellman error, effectively preventing overly pessimistic evaluation. Meanwhile, the second component, which deals with uncertainty control, implicitly enhances the power of model extrapolation. In addition to the information-theorete algorithm, we also develop computationally efficient counterpart that is solved by a penalized adversarial estimation algorithm with proximal-mappe mapping updating, allowing both non-linear and linear function approximation. From theoretical standpoint, we establish strong regret guarantee for both information- taterrrictttortccallll...l and practical algorithms under only realizability without requiring any data-coverage (neither global nor partial coverage) and completeness-tyne assumptions. As a special case study, we further refine our developed mixture density ratio-based concentrability coefficient relative condition number in linear MDP settings. The sample complexity of our regret bound improves or at least matches the prior results in the fully exploratory or partial coverage holds. Notably, compared with existing works, either
settings where the focusing on theoretical or empirical development, we provide a comprehensive theoretical analysis of the proposed framework and also conduct synthetic, benchmark, and real data experiments for empirical evaluation.
2 Preliminaries and Notations
Markoy decision process. We consider an infinite-horiin horizzn- discounted MDP M (S.A,P sO} [40], where S is the state space, A is the action space, P S x A -> ASS) is the Markov transition
kernel for some probabilistic simplex A, r S x A + [0, Rt] is the reward function for R 2 O.
y E (0,1) is the discounted factor and 5 is the initial state. A policy π -S- - A(A) induces a
distribution of the trajectory s", a², ,0, s st,..,, where a' ~ T--ls),, r a'), P(-|ss. aa)) for any t 2 O. The expected discounted return of a policy is defined as J(T) -E discounted return when the trajectory starts with (s.a) a) and all remaining actions are taken according to π is called q- g-function qt S AA- - [0. V1. The qº' is the unique fixed point of the Bellman operator 8", satisfying the Bellman equation [45]: 1 q[s a) == r(s, a) B.BB,.P((aaa))( (q(s', x)]. Here q(s', x)) is denoted as shorthand for (eawa(())e") [q (s', aa)), and we define P PM a) == BP--P(-)e.) [1 (8/, x)]. g (sO, T). Another important notion is the normalized discounted visitation of n. defined as d (s. a) = (1 (1-7) 2 7 a), where dz,
>"r"\ >'r"[m]. The
Additionally, it is helpful to remember that J (TT)
is the marginal acte-n distribution at the time-step t.
Offline RL under function approximation. In the offline RL setting, there exists an unknown offline data- Bata-generating distribution μ induced by behavior policies. Despite the unknowns of μ., we can observe a set of transition pairs, as offline dataset Disn. == (8i, ai, ri, s =- sampling from μ. For a given policy ग, the density-ratio (importance-weignt) Ta,/p(s, a) dd (s,a)/u(s,, a), measures how
2

---

effectively μ covers the visitation induced by я. The primary objective of offline policy optimization to learn an optimal policy that maximizes the returm, [T),, using the offline dataset. Under the function approximation setting, we assume access to two function classes Q : 8 x A - IR and Q: x A + R. which are utilized to capture q" and Td./u= respectively.
Exploration and coverage. In general, when saying an offline dataset is well-explored, it means that well-designed behavior policy has been executed, allowing for comprehensive exploration of the MDP environment. As a result, the dataset is likely to contain possibly all state-action pairs. This implicitly requires 4 has the global coverage [18, 49]. In this context, the global coverage means that the density ratio-based concentrability coefficient, sups,a (dz (s. a) (1/ps. is upper-bounded by constant e E IR+ for all policies
IT, where IT is some policy class. This condition is frequently employed in offline RI. [2, 8, 12]. However, in practice, this assumption may not hold true, as devising exploratory policy is challenging task for large-scale RL problems. Instead, our goal to learn a good policy with strong theoretical guarantees that can compete against any arbitrarily covered comparator policy under much weaker conditions than the global coverage.
Bi-Level Offline Policy Optimization Algorithm
In this section, we introduce our bi-level offline policy optimization framework. The development of the framework consists of three major steps.
Step 1: robust interval learning. In this step, we aim to provide robust off off-policy interval evalua- tion. The major advantage of this interval formulation is its robustness to the modee--mispeecficatoon of the importance-weighh class Ω2 and the encoding of distributional-shift information in the policy evaluation process. First, we define a detection function D(-), which is used measure the degree of the distributional-shifff in terms of density ratio.
C22 Definition 3.1. For x. C2,22, C E R++ and C 1, the detection function TD-)) satisfies the following
conditions: (I) 1-minimum: D(1) = 0. (2) Non-negativity: (Dxx) 2 0. (3) Boundedness on first-order
derivative: (x)) S c2 if E [0, C7. (4) Boundedness on value: [ID(x)] S 0₁ for x E [0, C). (5)
Strong convexity: D(x) is M-strongly convex with respect to x.
The family of Rényi entropy [42]. Bhattacharyya distance [11]. and simple quadratic form functions [60]all satisfy the conditions outlined in Definition 3.1. Under this definition, it can easily observe that ID) has a convex conjugate funetion [6], D. with ID. (ax.) = sup, {a x. (x)), that satisfies D. = O. It follows from Bellman equation 83 (= a) = q=((sa) a) for any s, a, then J(T) = q (5", TT + E,,, [AD. (("T.(("""""s,,., a) - q² (s, a)/A))((L - 7)] for À 2 0. Applying Fenchel-Legendre transformation [36. 21]. and model in a restricted importance weight class Q for any 8, a, we obtain (TT) ((m)=1((6 (s", - E2 (sup x (8*'"(ss,a)
(s,a)) AD())/(111111
(5" n - (x, ()(r 7u (s', m) - x- (s. - (s, a))]/(1 - 7)-
(2)
Suppose q" is well-sepcified, i.e., 9º e Q. we can find lower bound of (2), which is valid for any T E Ω2 via replacing 9²' with inf as follows:
J(T) 2 inf ge@
(E,, ((., 1g(p x) q(s. + ()s))
((T...))
1/(1- ((1-7)BB (,,
== AD(T)T)
After following a similar derivation, we can establish an upper bound for ((T) as well, and thus construct value interval for JTT). This interval holds for any 7 and is therefore robust against moseel-mispeecificatio of Ω. In order to obtain a tighter interval, we can shrink the interval width by maximizing the lower bound and minimizing the upper bound, both with respect to r. This procedure can be interpreted as searching for some good 7 E Ω to minimize the function approximation error.
( E sup inf H(T, 4, T) XE(D, inf sup (I +E(D))))))))))))))
q
rER
While the interval offers a robust method for dealing with the bias introduced by function approxima- tion when estimating (TT), it lacks a crucial and non-trivial step for handling statistical uncertainty.
3

---

Step 2: uncertainty quantification. In this step, we quantify the uncertainty of the interval (3), and establish con-asymptotic confidence interval (CI) for J(TT) which integrates bias and uncertainty quantifications in single interval inspired by [60]. Given offline data Di... our formal result for quantifying sampling uncertainty in order to establish the CI for J(r).
Theorem 3.1 (Non-asymptotic confidence interval). For target policy и, the return (T) is within CI for any Ω with probability at least 1 - ö, i.e., J(x E [5 (TT; T), Jr (T: for
r;T (s as)
Jr (m;
sup M₁ (- - (ID, nm
11
qE@
n reT (st, as)
T (T;
+
sup Mn (q. 7) (Dn, o
(4)
1-7
nEQ
if the uncertainty deviation on satisfies
P sup TER
n11 - Σ (ss a.) (r: (5 R) 9" - S son) 2
1
where Mn r) = E. T(s a.).).)))(((())))))))))))))))))(
q a.)a/(( 7)n + g(3 x))
Similar to the value interval, the CI [ز (T; J Jtt (T; 7) also holds for any E Ω. Therefore, we can optimize the confidence lower and upper bounds in (4) over T E Q to tighten the CI, and obtain:
P P(J(T)
(sup Jr (I;T), inf Jr (T: E [Jn (TT; T), J (T: 2 1-6. TEN
rell
Step 3: bridge policy evaluation to policy optimization. In this step, we aim to formulate a policy optimization based on the derived high-confidence policy evaluation from the previous steps. Given the consistent CI estimation of (x), we can naturally incorporate the pessimism principle, i.e., using the CI lower bounds of ((x as the value estimate of the policy evaluation of [22]. With such
procedure, our objective is to maximize these lower bounds over some family II of policies:
max sup n (T;;) TET
(5)
TER
Although (5) is algorithmically feasible for obtaining policy solver 7. it lacks direct interpretation without taking advantage of the bi-level optimization structure in hindsight. Therefore, propose to reformulate (5) via a dual-to-pi to--rime conversion (shown Theorem 3.2), which naturally lends itself to lower-upper optimization with guaranteed convergence. Specifically, we formulate (5) bi-level framework problem:
(Upper Level)
min --- (s" m) Tlll
(6)
(Lower Level)
s.t. qºh arg min qs .T,, gee..
(7)
Consistency
Qup {q E Q: sup
n
7(s ar) + rg(s), g(s,, a:l) s sen).
r
Tz = -
Uncertainty Control:
To/ sup ||Tolla for To e EΩ: En E. To)) s 5. T.E
At the upper level, the learned policy मे attempts to maximize the value estimate qd over some policy class II, while at the lower level, g is to seek the f-function with the pessimistic policy evaluation value from the confidence set Q.,, with consistency guarantee and uncertainty control. For consistency, whenever qº' or its good approximator is included in Q (realizability for Q class is satisfied),, the set Qe, ensures the estimation consistency of qº' in terms of "sufficently small"
weighted average Bellman error. For uncertainty control, the constrained set ft. attempts to control the uncertainty arising from distributional shift via user spersspccfiic thresholding hyperparameter ō.. The feasible (uncertainty controllable) candidates 7 E J, are used as weights for the average Bellman error, helping to construct the consistent set Q., Risk-averse users can specify a lower value for the thresholding hyperparameter or consider a higher ãn to tolerate a larger distribution shift. In other words, the chosen value of on depends on the degree of pessimism users want incorporate in the policy optimization.

---

Theorem 3.2. There must exist some threshold values En, and on, the return policy of (5) ā satisfies the minimization problem in (6), indicating the solution of the optimization (5) and (6) is equivalent.
Interestingly. the new form in (6) characterizes our policy optimization framework as a two-player general-sum game [16], which a sequential game involving two players. Each player aims to maximize their own payoffs while considering the decisions of other players. Our bi-level optimization framework has been demonstrated to improve learning stability and ensure algorithmic convergence, benefiting from the existence of a local equilibrium [51].
To close this section, we remark that the establishment of consistency with respect the weighted average Bellman error is the key point for us to relax the completeness-typp assumptions. In the famous APt/AVI-type algorithms [13, 14, 81, they target to minimize a squared or minimax Bellman error for finding 9 E Q so that ||g 8 all 0=1ll [ا(ي)) R 0 to obtain q = q". Unfortunately, even with the infinite amount of data, the empirical estimate of ||g 8 alli., (10) i.e., squared empirical Bellman error) is biased due to the appearance of unwanted conditional variance, i.e., the double sampling issue [3]. The APL/AVI-type algorithms need a separate helper function class Q for modeling 8 q. and [8] has shown that when the class Q realizes the Bayes optimal regressor By (Bellman- deelman-ccomllteness condition), the estimation consistent and unbiased. In contrast, thanks not using the squared loss, our weighted average Bellman error can be estimated from an unbiased estimate without concern about the double sampling issue, and thus no need for any cmpleteness-type conditions.
Information-Theored Results
In this section, we provide theoretical analyses of our algorithm, which reveals the advantages of the proposed policy optimization method from a technical standpoint.
Notably, to the best of our knowledge, Theorem 1 is the first result of regret guarantee under only realizability without requiring any data coverage or completeness-tppe assumptions. Additionally, in contrast to most existing works that assume finite function classes, we carefully quantify the space complexities for infinite function classes (e.g., a class of real-valued functions generated by neural networks) using Pollard's pseudo-dimension [38]. The formal definition is provided in Appendix. notices that the pseudo-dimension is a generalization of the well-known VC dimension [50]. In the following, we first introduce the necessary assumptions before presenting the guarantees for our algorithm.
Assumption 1 (Realizability for q-function class). For any policy π II, we have qº' Q. When this assumption holds approximately, we measure violation by inf sup, Ty [g a) 1 qss a))² EQ where EQ 2 0 and p is some data distribution such that p E {ds : E II).
We would like to emphasize that we do not require Bellmann-ommpltteess condition [53, 58), which much stronger than the realizability condition. In addition, we do not impose realizability on the importance-weigg weight class Ω2 thereby allowing model misspecification on Q. Having stated the major assumptions, we now turn to the routine ones on boundedness before presenting the main results.
Assumption 2 (Boundedness on Q). There exists a non-negative constant V < co, the function qss, a) E [0, V), Aq E Q, S. A.
Assumption 3 (Boundedness T(s, a) E [0, U.,, VT E 2, E S, a E A.
Q). There exists a non-negative constant S U co, the function
Theorem 4.1. Under Assumptions 1-3 and denote supremum of p-weighted L2 norm of Z. i.e., suprea [|, (m) as U5. Let मे be the output of solving (6) when we set En = Onn-//zg ( (vIn Vol(O)/ō]+ /EQ) and ōn = (0m'mmn//p LoVon((ol
1))),
thenfor any policy π é II and some constant Ułz E (1,215) ). w.p. 2 8.
In (Vol(O))// nM
Cuz M max 1/2 (60)3/1)
-
1-7 δ usev
Fair
yy Bidt-p)) 1 -PT) rr (5, + 1 LusoEp In (nVo)(())/))
min e suz}
5

---

(=) -s for qt := arg max Se.. g(5", and of == arg mig eE,, q(5", x). For Pollard's pseudo-dimension Da, De. Du, Vol(O) = (e max Do Dm) + ()1 L with the effective pseudo dimension D Dg De + Du, where is Lipsehitz constant of M Msstrongly convex function (-)). Moreover C. and Ö denote constant terms depending on z, and big-Ol Oh notation ignoring high-order terms, respectively.
Here (
In the upper bound of Theorem 4.1, we split the regret into four different parts: the on-support intrinsic uncertainty c.. the on-support bias éb. the violation of realizability émis, and the off-support extrapolation error Coff- Recall that require 9dd E Q as in Assumption in fact, relax the condition to requiring q" to be in the linear hull of Q [48], which is more robust to the realizability enror émis. In the following. we focus on investigating the roles of the on-support and off-support error terms in the regret bound.
further
On-support errors: bias and uncertainty tradeoff. The on-support error consists of two terms: c and Gg. The on-support uncertainty deviation, Co. is scaled by a weighted Ly-based concentrability coefficient Un :- llp/ p0 (ل(ي) which measures the distribution mismatch between the implicit exploratory data distribution and the baseline data distribution μ.. Meanwhile, E depends on the probability mass of (dx p)+ us-0, and represents the bias weighted by the probability mass difference between dz and in the support region of μ. In general, a small value of 24 necessitates choice of the distribution p to be closer to j which reduces Eg. reducing eg but potentially increasing the on-support bias E, due to the possible mismatch between de and p. Consequently, within the on-support region, there is a trade-off between 6, and <b, which is adjusted through UZz
Off-support error: enhanced model extrapolation. One of our main algorithmic contributions is that the support extrapolation error con can be minimized by selecting the best possible without worrying about balancing the error trade-off, unlike the on-support scenario. This desirable property is essential for allowing the model to harness its extrapolation capabilities to minimize coff, while simultaneously achieving a good on-support estimation error. As a result, the model attains a small regret. Recall the bi-level formulation; at the lower level, (7) addresses uncertainty arising from the distributional shift using L2(μ) control rather than Lx control. This plays an important role in enhancing the power of the model extrapolation. In particular, Specifically, there exists an implicit exploratory data distribution o with on-support behavior (p'l close to μu, such that Ip/ fp/pll L (m)) is small. On the other hand, its off-support behavior (pll x0)) can be arbitrarily flexible, ensuring that d, -= is close to p1 == Consequently, (dz - pp 1,= is small, as is con-
When a dataset with partial coverage, indicated in [49], it is necessary to provide guarantee: learn the policy with "best efforts" which competitive to any policy as long as is covered. Before we state the near-optimal regret guarantee of our algorithm, we formally define a notion of covered policies according to a newly-defined concentrability coefficient.
Definition 4.1 (215 -overrd policy class). Let II(25)) denote the Ug- -oveered policy class of μ for uz 2 1, defined as
as)
SUZ and sup dx ((s,)))p(saa) }
m(45)) = π T
p(s, a)
p(s.a)
L2(2)
Note that this mixture density ratio concentrability coefficient is always bounded by the Loo based concentrability coefficient. Thus such single-policy concentrability assumption in terms of the mixture density ratio is weaker than the standard Lox density ratio-based assumption.
Corollary 4.1 (Near-optimal regret). Under Assumptions 1-3 with e E [0, 1), and we set En, on as in Theorem 4. I, then for any good comparator policy x² E ((T))) (not necessary the optimal policy
T² ), w.p. 21 1 1 8, the output policy âे of (6) satisfies
Inf [o(())())/))
J (( - ((F) S 1-7 δ Uz(v + (g(V+D)V
+ (1+ (UL
nM
A close prior result to Corollary 4.1 is that of [9], which develops pessimistic algorithm based on a nontrivial performance gap condition. Their regret guarantees only hold if the data covers the optimal policy n², in particular, requiring bounded Lox single-policy concentrability with respect to x² In comparison, our guarantee can still provide a meaningful guarantee even when x² not covered by data. In the following, we include the sample complexity of our algorithm when sQ 0.

---

Corollary 4.2 (Polynomial sample complexity). Under the conditions in Corollary 4.1, the output policy के of solving (6) satisfies J (TT) ( S w.p. 2 1 6, if
n n= - ( + L)/MM²²
(V + L)
U + L)
In Vol(
c2(1-7)
e el.33 1).3
c(1 (1--7)
The sample complexity consists of three terms corresponding the slow rate O(n-1/3 and the two faster rate (nn=)) and O(n-//1) terms in Corollary 4.1. When Ug and Un
much larger
than L4, the fast rate terms are dominated, and the sample complexity is of order ((1/=²), which is much faster than (1)/e)) in the close work of [59]. is worth noting that even in exploratory settings where the global coverage assumption holds, our sample complexity rate matches the fast rate in popular offline RL frameworks with general function approximation [8, 54, 12].
In addition to the near-optimal regret guarantee, in safety-critical applications, an offline RL algorithm should consistently improve upon the baseline (behavior) policies that collected the data [19, 26]. Our algorithm also achieves this improvement guarantee with respect to the baseline policy.
Theorem 4.2 (Baseline policy improvement). Under Assumptions 1-3 with EQ 0 and set En, or as in Theorem 4. Suppose 1 E Ω and the baseline policy Ty E II such that d = μs, then the regret ()] (b) ( for the oulpul policy मे of solving (6), w.p. 2 8, is upper bounded by
o ( (V + Ln (O)())))
(V3 + V2L)
Inn (ol())))))
+ (V + L) Inf (ol(
nM
M
72
n
The aforementioned information theooretcc results enhance the understanding of the developed algo- rithm, in terms of the function approximation and coverage conditions, sample complexity, horizon dependency, and bound tightness. In practice, although the tioomattion-therrttiic algorithm offers feasible solution to the problem, it is not yet tractable and computationally efficient due to the need to solve constrained optimization. In the following section, develop a practical algorithm computationally efficient counterpart for the information-theoreiie algorithm.
Penalized Adversarial Estimation Algorithm
Although the information theorrtic algorithm offers feasible solution the problem, it is not yet tractable and computationally efficient due to the need to solve constrained optimization. In this section, develop adversarial estimation proximal-mapping algorithm that still adheres to the pessimism principle, but through penalization. Specifically, the adversarial estimation loss is constructed follows: maxminL(gr T, c,,,) for solving
n D(T (ir(ss, oi))
(s5 1) ym
c- Σ
(s, ai) (q(s), Ti (g(s),
We observe that the inner minimization for solving g is relatively straightforward. as we can obtain closed-form global solver using the maximum mean discrepancy principle [20, 44]. In contrast, optimizing Ty is more involved, often requiring a sufficiently expressive non-linear function ap- proximation class, e.g., neural networks. However, concavity typically does not hold for such class of functions [21]. From this perspective, our problem can be viewed as solving non-concave maximization problem, conditional on the solved global optimizer q == arg arg min, L(g, 7, ,,,",, c", A)- At each iteration, we propose to update 7 by solving the proximal mapping [37] using the Fuclidean distance to reduce the computational burden. As result, the pre-iteration computation is quite low.
Algorithm 1 Adversarial proximal-mappinng algorithm
1: Input observed data Di... {(s,, 0,, $0) and parameters qº, 79, x c², À and Ç.
2: For A 1 K:
3: Update rK and gh by solving maxmin Llg, = ,,,, 9
4: Update * by solving (*(+ss) = argmax ( (.)),, (-1s)) - DiiegFommpy (T(-)s), x (-1s))
5: Return the policy म, which randomly selects policy from the 1 1km1
7

---

Once q and T are solved, we apply mirror descent in terms of the negative entropy DNogEnnopy [5]. That is, given a stochastic gradient direction of we solve the prox-mapping each iteration as outlined in step 4 of Algorithm I. A detailed version of Algorithm 1 with extended discussions on convergence and complexity is provided Appendix. In the following, we establish the regret guarantee for the policy output by Algorithm 1.
Theorem 5.1. Under Assumptions 1-3 with sQ = O, we properly choose X = X(15), ie., X well depends on U2 and c² (OVnV/VVV/a /ALU5 In /ol(()))6))) After running K 2 log [A] rounds of Algorithm with the stepsize Ç = v oog (2V( for any policy a E II, the output policy ß of the algorithm, w.p 2 1 8, satisfies.
( In(Vol(Ot)/0)
V log |A| K
((x)) J(F) < 1-7
n
R
In(Vol(Ot)/0) C V.A
1
min Becr-peet -xe+ 11a=0 g (((,a) + 1oom PLEA
K
n
where Du; == {pw (L((()) < <2ih C V,A. A.A.I. are some constant terms, and the function class complexity Vol(Ot) = (eD max Dr. De. Dn) (1) 2D for = + De + Pn-
Trajectory-adaptie exploratory data distribution. Similar to Theorem 4.1, the penalized al- gorithm also exhibits a desirable extrapolation property for minimizing extrapolation error while simultaneously preserving small on-support estimation errors. This is achieved through adaptations of the implicit exploratory data distributions, Pk for & E [K]. In contrast to the information information-theoreticc theoretic algorithm, the automatic splitting by Pk now depends on the optimization trajectory. At each iteration k, the penalized algorithm allows each implicit exploratory data distribution Ps: to adapt to the com- parator policy и. This results in more flexible adaptation than the one in the informatioon-hhoretii algorithm, either for balancing the trade-off between on-support bias and uncertainty incurred by the distributional mismatch between dx and Pk: or for selecting the best implicit exploratory minimize model extrapolation error.
Opimization error. Blessed by the reparametrization in the proximal-mapping mapping policy update, which projects the mixture policies into the parametric space 1lw the complexity of the restricted policy class is independent of the class of Q and the horizon optimization trajectory K. As result, the optimization error O( ((VV log |A|/ K) can be reduced arbitrarily by increasing the maximum number of iterations, K, without sacrificing overall regret to balance statistical error and optimization error. This allows for the construction of tight regret bounds. This distinguishes our algorithm from API-style algorithms, which do not possess policy class that is independent of Q [2, 43, 53].
5.1 An Application to Linear MDPs with Refined Concentrability Coefficient
In this section, we conduct a case study in linear MDPs with insufficient data coverage. The concept of the linear MDP initially developed in the fully exploratory setting [55]. Let Φ S x - IRdd be a d- dimensional feature mapping. We assume throughout that these feature mappings are normalized, such that [|o[s, a) Lt < 1 uniformly for all (s. a) E S x A. We focus on action-value functions that are linear in and consider families of the following form: Qq := {(s, a) + (ø(s, a), |10||z, co ). where co E [o. V7. For stochastic policies, we consider the soft-max policy class II, := (als) x elo(s,a).)) ||w|| < ) where e E (0, oo). Note that the softmax policy class is consistent with the implicit policy class produced by the mirror descent updates with negative entropy in Algorithm 1, where the exponentiated gradient update rule is applied in each iteration. For the importance-weighh class, we also consider the following form: 2x := {s, a) - (ő(s, a), 15) || S c.)) where Gp E (0. oo). To simplify the analysis, we assume the realizability condition for 2o is exactly met. In this linear MDP setting. we further refine the density ratio relative condition number to characterize partial coverage. This concept is recently introduced in the policy gradient literature [1] and is consistently upper-bounded by the -ased density ratio concentrability coefficient.
Definition 5.1 (Relative condition number). For any policy π E Il and behavior policy vy such that xTBs, (o(s,a))(s,a)"
dr, = u, the relative condition number is defined as ((dr, (1) = suppERd x ET ((na))((.))
Assumption 4 (Bounded relative condition number). For any π E Hy e(da, p) < co.
8

---

Intuitively, this implies that as long as high-quality comparator policy exists, which only visits the subspace defined by the feature mapping & and is covered by the offline data, our algorithm can effectively compete against it [49]. This partial coverage assumption, in terms of the relative condition number, is considerably weaker than density ratio-based assumptions. In the following, we present our main near-optimal guarantee in linear MDPs. In addition, we design and conduct numerical experiments to empirically validate Theorem 5.2 in terms of the regret rate of convergence. Theorem 5.2. Under Assumption 4, if we set propertly choose X = M(a) and e* = D(/n/dln + ev/((1 V c)Vcccw)/8)) and suppose H" is returned by Algorithm I with linear function approxiamiton after running K >> log [A] rounds, then for any policy in æ E (w for Ug= 2 1, w.p. 2 1- - 6, ((x) - ((*") is bounded by min 2 dul,, (dd
e C + +eva(Tv V L V) (
1-? where k = trace(Ey (0l, a)o(s, a) T) and ce (2)) = (v:lle])((sa)) will 2gg0 ug) |
To the best of our knowledge, this is the first result PAC guarantees for an offline model-free RL algorithm in linear MDPs, requiring only realizability and single- -poiicpppoyyyy concentrability. The regret bound we obtain is at least linear and, at best, sub-linear with respect to the feature dimension d. Our approach demonstrates a sample complexity improvement in terms of feature dimension compared to prior work by [22], with complexity of ((d2/2) versus Odd. It is worth noting that [22] only establishes results that compete with the optimal policy, and when specialized to linear MDPs, assumes the offline data has global coverage. Another previous study by [53] achieves similar sub- linear rate in d as our approach: however, their algorithm is computationally intractable, relying on much stronger Bellman-come coommaanoomletenesss assumption and requiring small action space.
6 Experiments
In this section, we evaluate the performance our practical algorithm by comparing to the model-free offline RL baselines including CQL [25], BEAR [24], BCQ [18], OptiDICE [27], ATAC [10]. IQL [23], and TD3+BC [17]. We also compete with a popular model-based approach COMBO [57].
Synthetic data. We consider two synthetic environments: a synthetic CartPole environment from the OpenAl Gym [7] and a simulated environment. Detailed discussions on the ex- perimental designs are deferred to the Appendix. In both settings, following [48], we first learn a sub-optimal policy using DQN [34] and then apply softmax to its q-function, divided by a temperature parameter o to set the action probabilities to define behavior policy ne. A smaller a implies n, is less explored, and thus the support of μ dm, is rel- atively small. We vary different val- ues of a for evaluating the algorithm performance in "low", "medium" and "relatively high" offline data exploration scenarios. We use 7 = 0.95 with the sample-size
Simuisted
CarPole
Mathods
Proposed
OptDIcE
ATAC
ICL
COL
BCO
1500 in all experi- ments. Tuning parameter selection is an open problem in offline policy opti- mization. Fortunately, Theorem 5.2 sug- gests an offline selection rule for hyper- parameters X and c². In the following experiments, we set the hyper-parameters satisfying the condition O( that our algorithm almost consistently outperforms competing methods in different settings. This performance mainly benefits from the advantages exposed in our theoretical analysis, such as model extrapolation enhancement, relaxation of completeness-ty -tpe assumptions on function approximation, etc. The only exception is the slightly poorer performance compared to COMBO in high exploration setting, where COMBO may learn a good dynamic model with relatively sufficient exploration. We provide the experiment details in Appendix due to page limit.
TDS+8C
Modium m1
Foduliviy 15gh
Madium Hi Haratweyy Pign
Exploration Degrew
Degre
Figure 1: The boxplot of the discounted return over 50 repeated experiments
dogg(V Vnj/ ). Figure shows
1/4
Benchmark data. We evaluate our proposed approach on the D4RL benchmark of OpenAl Gym locomotion (walker2d, hopper, halfcheetah) and Maze2D tasks [15], which encompasses a variety

---

of dataset settings and domains and positions our algorithm within the existing baselines. We take the results of COMBO, OptiDICE and ATAC from their original pupers for Gym locomotion, and run COMBO and ATAC using author-provided implementations for Maze2I). The results of BCQ, BEAR methods from the D4RL. original paper. In addition, CQI., IQL. and TD3+BC are re-run to ensure fair evaluation process for all tasks. As shown in Table 1, the proposed algorithm achieves the best performance in 7 tasks and is comparable to the baselines in the remaining tasks. In addition to the evaluation of the policy performance, we also conduct sensitivity analyses on the apperparameter-tningg and study the regret rate of convergence.
Table 1: The normalized score of the policy at the last iteration of training, averaged over 5 random seeds. The highest performing scores are highlighted. The med, med-rep, and med-exp is shorthand for medium, medium-replay, and medium-expent respectively.
Tasks
Propused
COMBO
BCQ
BEAR
OpEDDCE
ATAC
COL
IQL
TD3+BC
walker2d med
80.8 1 5.1
81.9 1 2.8
53.1
59.1
21.8
1 7.1
89.6
17.2 1
4.2
78.3
1 4.3
81.7
2.3
hopper-med
94.9 + 4.3
97.2 2.2
54.5
52.1
94.1
= 3.7
85.6
74.3
66.3
98.4
hallchhetall med
58.1 + 1.4
54.2 14.2115. 1.5
40.7
41.7
38.2
= 0.1
53.3
37.2 + 0.3
47.4
1.1
27.8
0.7
walker2d-med--op
99.6
8.6
15.0
19.2
21.6=111
92.5
20.8
73.9
288
31.
1.2
hopper-med-ngg
113.0 2.1
89.5 89.5 1.8
33.1
33.7
36.4
102.5
32.6
94.7
1.5
44.4 = 3.7
halfchectah-med-rep
49.3 2.1
55.1
38.2
38.6
0.3
48.0
41.9 1.1
44.2
=
108.2 waldor2d-med-opp
103.3
57.5
10.1
71.8
9.2
114.2
6.9
1.9
1.000
hopper-med-oxp
117.8
111.1
110.9
96.3
0.6
119.2
111.4
1.2
91.5
22 112.4
mifehhorahhmmddoxp
98.5 +: 3.8
5.6
64.7
53.4
3.7
94.8
66.7 + 8.9
86.7
3.0 96.9 =
walker2d random
11.2 1: 3.8
7.0 1 3.6
4.9
7.3
4.3
6.8
4.7
1
1.5
5.8
1.8
3.4
hopper-random
18.7 18.7:1.55
1.4
10.6
11.4
11:=1.
17.5
10.7
10.8
11.1
hallcheetah random
37,6 2.4
38.8
3.7
2.2
25.1
11.6
= 1.2
3.9
26.7
+ 1.4
22.4
18 26.1
1.8
maze2d umazze
96.5 1. 27.8
34.2
1
8.6
12.8
3.4
111.0
1 8.3
84.4
1.
24.8
50.5
1
7.9
41.5
1
4.7 13.8
1 22.8
maze2d-med
137.5 +: 18.9
49.9
13.9
8.3
29.0
145.2
= 17.5152
34.6
28.6
+ 9.2
38.5
+ 4.2
59.1
+ 44.7
maze2d large
15.2
128.2
6.2
33.4
142.1
33.8
16.254.2
18.187.6
15.4
Real-world application. The Ohio Type Diabetes (OhioT1DM) dataset [33] comprises cohort of patients with Type-1 diabetes, where each patient exhibits different dynamics and 8 weeks of life-event data, including health status measurements and insulin injection dosages. Clinicians aim to adjust insulin injection dose levels [33, 4] based on a patient's ' health status in order to maintain glucose levels within a specific range for safe dose recommendations. The state variables consist of health status measurements, and the action space is a bounded insulin dose range. The glycemic index serves a reward function to assess the quality of dose suggestions. Since the data- metta-genrating process is unknown, we follow [31, 29] to utilize the Monte Carlo approximation of the estimated value function on the initial state of each trajectory to evaluate the performance of each method. The mean and standard deviation of the improvements on the Monto Carlo discounted returns presented in Table 2. As result, our algorithm achieves the best performance for almost all patients, except for Patient 552. The main reason for the desired performance in real data is from the enhanced model extrapolation and relaxed function approximation requirements and outperforms the competing methods. This finding is consistent with the results in the synthetic and benchmark datasets, demonstrating the potential applicability of the proposed algorithm in real-world environments.
Table 2: The baseline policy improvements over 50 repeated experiments in the OhioT IDio dataset.
Patient
Preposed
COMBO
BCQ
BEAR
OptiDICE
ATAC
COL.
IQL.
TD3+BC
596
6.5
4.1 4.1:0.0.
3.8
2.7
4.7
5.1
4.6
0.4
4.8 1.3
584
33.1
13.1188 1.8
27.0 1.3
20.3
1.2
22,9
1.6 27.7
1.9
26.9
21,6
22.7
22.4
1.7
567
36.9
1: 1.3
2.0
1.4
25.6
- 1.4
28.8
1
22
29.7
26.5
25.8
27.8
1 1.5
552
0.9
0.8
5.5
5.0
8.1
1.2
6.7
6.1
7.4
544
13.2
1.9
1.8
7.5
2.5
5.9
1.8
10.3
118118
10.12:1
8.7
1.0
7.8
9.7
540
20.4
1 0.5
17.5
17.5-0.9
0.9
14.3
1 0.6
12.7
2 0.5
17.9
17.9
18.2
1.4
0.5
14.0
0.6
17.1 0.8
7
Conclusion
We study offline RL with limited exploration in function approximation settings. We propose level policy optimization framework, which can be further solved by a computationally practical penalized adversarial estimation algorithm, offering strong theoretical and empirical guarantees. Regarding limitations and future work, while the penalized adversarial estimation is more computationally efficient than the previously constrained problem, it may still be more challenging to solve than single- stage optimization problems. Another future direction is to explore environments with unobservable confounders. It will be interesting to address these limitations in future works.
10

---

8 Acknowledments
The author is grateful the five anonymous reviewers and the area chair for their valuable comments and suggestions.
References
[1] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. Optimality and approxi- mation with policy gradient methods in markov decision processes. In Conference on Learning Theory, pages 64 66. PMLR, 2020.
[2] András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with bellman-residual minimization based fitted policy iteration and a single sample path. Machine Learning, (1(1):89-112) 2008
[3] Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Machine Learning Proceedings 1995, pages 30-37. Elsevier, 1995.
[4] Jiansong Bao, Heather R Gilbertson, Robyn Gray, Diane Munns, Gabrielle Howard, Peter Petocz, Stephen Colagiuri, and Jennie Brand-Miller. Improving the estimation of mealtime insulin dose in adults with type 1 diabetes: the normal insulin demand for dose adjustment (nidda) study. Diabetes Care,
2151, 2011.
[5] Amir Beck. First-order methods in optimization. SIAM, 2017.
[6] Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
[7] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint
2016.
[8] Jinglin Chen and Nan Jiang. Information-theorrtic considerations in batch reinforcement learning. In International Conference Machine Learning, pages 1042-1051. PMLR, 2019,
[9] Jinglin Chen and Nan Jiang. Offline reinforcement learning under value and density-ratio realizability: the power of gaps. In Uncertainty in Artificial Intelligence, pages 378-388. PMLR, 2022.
[10] Ching-An Cheng, Tengyang Xie, Nan Jiang, and Alekh Agarwal. Adversarially trained actor critic for offline reinforcement learning. In International Conference on Machine Learning, pages 3852-3878. PMLR, 2022.
[11] Euisun Choi and Chulhee Lee. Feature extraction based on bhattacharyya distance. Pattern Recognition, 16(8):1703-1700 2003.
[12] Yaqi Duan, Zeyu Jia, and Mengdi Wang. Minimax- oottmal off- off-policy evaluation with linear function approximation. In International Conference on Machine Learning, pages 2701-2709. PMIR, 2020.
[13] Damien Ernst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 6:503-556 2005.
[14] Amir-massoue Farahmand, Mohammad Ghavamzadeh, Csaba Szepesvári, and Shie Mannor. Regularized policy iteration with nonparametric function spaces. The Journal of Machine Learning Research, 17(1):4809-448 2016.
[15] Justin Fu, Aviral Kumar, Ofir Nachum, George Tucker, and Sergey Levine. D4rl: Datasets for deep data-driven reinforcement learning. arXiv preprint arXiv:2004.07219, 2020.
[16] Drew Fudenberg and Jean Tirole. Game theory. MIT press, 1991.
[17] Scott Fujimoto and Shixiang Shane Gu. A minimalist approach to offline reinforcement learning. Advances in neural information processing systems, 34:20132-20144 2021.

---

[18] Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. In International Conference on Machine Learning, pages 2052-2062. PMLR, 2019.
[19] Mohammad Ghavamzadeh, Marek Petrik, and Yinlam Chow. Safe policy improvement by minimizing robust baseline regret. Advances in Neural Information Processing Systems, 29, 2016.
[20] Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola. kernel two-sample test. The Journal of Machine Learning Research, 13(1):723-773, 2012.
[21] Nan Jiang and Jiawei Huang. Minimax value interval for off-policy evaluation and policy optimization. Advances in Neural Information Processing Systems, 33:2747-2758, 2020.
[22] Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline rI? In International Conference Machine Learning, pages 5084-5096. PMLR, 2021.
[23] Ilya Kostrikov, Ashvin Nair, and Sergey Levine. Offline reinforcement learning with implicit q-learming, arXiv preprint wrXiv:2110.06/11 2021.
[24] Aviral Kumar, Justin Fu, Matthew Soh, George Tucker, and Sergey Levine. Stabilizing off- policy q-learning via bootstrapping error reduction. Advances in Neural Information Processing Systems, 32, 2019.
[25] Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative q-learning for offline reinforcement learning. Advances in Neural Information Processing Systems, 33:1 179- 1191, 2020.
[26] Romain Laroche, Paul Trichelair, and Remi Tachet Des Combes. Safe policy improvement with baseline bootstrapping. In International conference machine learning, pages 8652-3661. PMLR, 2019.
[27] Jongmin Lee, Wonseok Jeon, Byungjun Lee, Joelle Pineau, and Kee-Eung Kim. Optidice: Offline policy optimization via stationary distribution correction estimation. In International Conference Machine Learning, pages 6120-6130. PMLR, 2021.
[28] Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643, 2020.
[29] Yuhan Li, Wenzhuo Zhou, and Ruoqing Zhu. Quasi-optimal reinforcement learning with continuous actions. In The Eleventh International Conference Learning Representations, 2023.
[30] Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Provably good batch off- off-policy reinforcement learning without great exploration. Advances in neural information processing systems, 33:1264 1274, 2020.
[31] Daniel J Luckett, Eric B Laber, Anna R Kahkoska, David M Maahs, Elizabeth Mayer-Davis and Michael R Kosorok. Estimating dynamic treatment regimes mobile health using v-learning. Journal of the American Statistical Association, 115(530):692-776, 2020.
[32] Travis Mandel, Yun-En Liu, Sergey Levine, Emma Brunskill, and Zoran Popovic. Offline policy evaluation across representations with applications to educational games. In AAMAS, volume 1077, 2014.
[33] Cindy Marling and Razvan Bunescu. The ohiotldm dataset for blood glucose level prediction: Update 2020. KHD@ IJCAI, 2020.
[34] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning, nature, 51897540):599-53,, 2015.
12

---

[35] Susan A Murphy, Mark van der Laan, James M Robins, and Conduct Problems Prevention Re- search Group. Marginal mean models for dynamic regimes. Journal of the American Statistical Association, 96(456):1400-122, 2001.
[36] Ofir Nachum and Bo Dai. Reinforcement learning via fenchel-rockafellan duality. arXiv preprint arXiv:2001.01866. 2021.
[37] Neal Parikh, Stephen Boyd, et al. Proximal algorithms. Foundations and trends in Optimiza- fion, 1(3):127-239) 2014.
[38] David Pollard. Empirical processes: theory and applications. Ims, 1990.
[39] Doina Precup. Eligibility traces for off-pollcy policy evaluation. Computer Science Department Faculty Publication Series, page 80, 2000.
[40] Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
[41] Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline reinforcement learning and imitation learning: tale of pessimism. Advances in Neural Information Processing Systems, 34:1 1702-11716, 2021.
[42] Alfréd Rényi. On measures of entropy and information. In Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume Contributions the Theory of Statistics, volume 4. pages 547-562. University of California Press, 1961.
[43] Bruno Scherrer and Boris Lesner. On the use of non-stationary policies for stationary infinite- horizon markov decision processes. Advances Neural Information Processing Systems, 25, 2012.
[44] Chengchun Shi, Masatoshi Uehara, Jiawei Huang, and Nan Jiang. A minimax learning approach to off off-policy evaluation in confounded partially observable markov decision processes. In International Conference on Machine Learning, pages 20057-20088 PMLR, 2022.
[45] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[46] Georgios Theocharous, Yash Chandak, Philip S Thomas, and Frits de Nijs. Reinforcement learning for strategic recommendations. arXiv preprint arXiv:2009.078: 2020.
[47] Philip Thomas, Georgios Theocharous, and Mohammad Ghavamzadeh. High-confidence off- policy evaluation. Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
[48] Masatoshi Uehara, Jiawei Huang, and Nan Jiang. Minimax weight and q-function learning for off-policy evaluation. In International Conference on Machine Learning, pages 9659-9668. PMLR, 2020.
[49] Masatoshi Uehara and Wen Sun. Pessimistic model-based offline reinforcement learning under partial coverage. In International Conference on Learning Representations, 2022.
[50] Vladimir N Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Measures of Complexity: Festschrifi for Alexey Chervonenkis, pages 11-30, 2015.
[51] Heinrich Von Stackelberg. Market structure and equilibrium. Springer Science Business Media, 2010,
[52] Ruosong Wang, Yifan Wu, Ruslan Salakhutdinov, and Sham Kakade. Instabilities of offline with pre-trained neural representation. In International Conference on Machine Learning, pages 10948-10960. PMLR, 2021.
[53] Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman- consistent pessimism for offline reinforcement learning. Advances neural information processing systems, 34, 2021.
13

---

[54] Tengyang Xie and Nan Jiang. Qa approximation schemes for batch reinforcement learning: A theoretical comparison. In Conference on Uncertainty in Artificial Intelligence, pages 550-559. PMLR, 2020.
[55] Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning, pages 10746-10756. PMLR, 2020.
[56] Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal offline reinforcement learning via double variance reduction. Advances in neural information processing systems, 34:7677-7688, 2021.
[57] Tianhe Yu, Aviral Kumar, Rafael Rafailov, Aravind Rajeswaran, Sergey Levine, and Chelsea Finn. Combo: Conservative offline model-based policy optimization. Advances neural information processing systems, 34:28954 28967, 2021.
[58) Andrea Zanette, Martin J Wainwright, and Emma Brunskill. Provable benefits of actor-critic methods for offline reinforcement learning. Advances neural information processing systems, 34:13626-13640, 2021.
[59] Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason Lee. Offline reinforcement learning with realizability and single-policy concentrability. Conference on Learning Theory, pages 2730-2773 PMLR, 2022.
[60] Wenzhuo Zhou, Yuhan Li, Ruoqing Zhu, and Annie Qu. Distributional shift-aware off-policy interval estimation: A unified error quantification framework. arXiv preprint arXiv:2309. 13278, 2023.
[61] Wenzhuo Zhou, Ruoqing Zhu, and Annie Qu Estimating optimal infinite horizon dynamic treatment regimes via pt-learning. Journal of the American Statisfical Association, pages 1-14, 2022.
14


Reviews:
[{"review_id": "oNn7fjz4xQ", "reviewer": "Reviewer_75WN", "summary": "This paper addresses the problem of offline reinforcement learning (RL). Offline RL involves computing a policy based on a static/pre-collected dataset, with no further interaction with the environment permitted. A significant hurdle in offline RL is the distributional shift resulting from insufficient exploration within the dataset. Moreover, previous work may necessitate the assumption of Bellman completeness for the utilized function class.  To overcome these challenges, the authors propose a bi-level structured policy optimization algorithm. This algorithm models a hierarchical interaction between the policy and the value function. At the lower level, the focus is on constructing a set of confident value estimates. The upper level, in contrast, aims to maximize a conservative estimate derived from this confidence set. The algorithm can be solved efficiently through a penalized adversarial estimation procedure. The authors provide theoretical regret guarantees for their algorithm and assess its performance using both synthetic and real-world datasets. Performance is compared against several well-known offline RL algorithms, such as CQL, IQL, and COMBO.", "questions": "See Weakness.", "limitations": "See Weakness.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Strengths:\n\n1. The concept of optimizing the confidence lower and upper bounds in equation (4) over τ within Ω, with the aim of tightening the Confidence Interval (CI), is intriguing and holds potential for generating a more precise confidence interval.\n\n2. The paper, overall, is well-written and well-structured, demonstrating a clear and logical progression of ideas.\n\n3. The authors have given a comprehensive view of their algorithm by providing both theoretical analysis and empirical versions. Additionally, the experimental results demonstrate the effectiveness of the proposed algorithm, as shown on various synthetic datasets as well as a real-world dataset.", "weaknesses": "\nWeaknesses:\n\n1. Complexity: The algorithm, in comparison to alternatives such as IQL and COMBO, is notably more complex. It employs a game-theoretical formulation and requires the resolution of two optimization problems at each iteration. This results in an increase in both the number of hyperparameters that require tuning and the overall computational cost, and potentially instability in the optimization (i.e., convergence).\n\n2. Ambiguities and Clarifications in Section 3 (Lines 119 to 126): \n   - Shouldn't $G (x_∗) = \\sup_x \\{x \\cdot x_∗ − G(x)\\}$ be revised to $G_* (x_∗) = \\sup_x \\{x \\cdot x_∗ − G(x)\\}$?\n   - For $J(\\pi) = q_\\pi(s_0, a) + E_\\mu[\\lambda G_*((B^\\pi q^\\pi (s, a) − q^\\pi (s, a))/(1 − \\gamma))]$, where $\\lambda \\geq 0$, the initial term appears as if it should be $q_{\\pi}(s_0, \\pi)$. Additionally, could you explain how $\\lambda$ is typically chosen? Does the choice of $\\lambda$ significantly impact the algorithm's performance?\n   - The derivation from $J(\\pi) = q_\\pi(s_0, a) + E_\\mu[\\lambda G_*((B^\\pi q^\\pi (s, a) − q^\\pi (s, a))/(1 − \\gamma))]$ to equation (1) is unclear. Why is $\\lambda$ merely a coefficient of $G(x)$? Shouldn't it also be a coefficient of  $x · (B^\\pi q^\\pi (s, a) − q^\\pi(s, a))$?\n   - The terms L(τ,q,π) and ξ(G,τ) require explicit definitions.\n\n3. Justification for Assumption 2: The justifiability of Assumption 2 is uncertain. It appears to be more of a requirement for feasible derivation rather than a naturally occurring condition. Can it be guaranteed that $\\tau(s,a)$ won't reach infinity in real-world problems? More justification on this point would be appreciated.\n\n4. Need for Intuition: More insight into why your framework doesn't require the Bellman completeness assumption would be beneficial.\n\n5. Additional Evaluations: It would be helpful if you could evaluate your proposed algorithm using more standard benchmarks, such as D4RL. This would significantly aid in positioning your work within the existing literature.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank the reviewer for the suggestive feedback, which greatly improves our paper! We address the reviewer's comments point by point below.\n\n> **Weakness 1: Complexity of the algorithm**\n\nThanks for raising this point. We would like to make a discussion on the three aspects. \n\n**Complexity**: we agree with the reviewer that our algorithm is more complex than the minimalist baselines, e.g., IQL, but the complexity of our algorithm is still handleable due to a two-fold reason. First, the mirror descent (step 4 of Algorithm 1) has a closed-form\nexponential update rule. It follows from [1], we have the analytical update rule as  $\\pi^{{k}}(\\cdot|s) \\propto \\pi^{{k-1}}\\exp(\\zeta q^{k}(s,\\cdot))$. Thus, the computational cost for the policy update is minimal. Second, the inner optimization in step 3 of Algorithm 1 is easy to solve. On the one hand, it could yield a closed-form global solver using the maximum mean discrepancy principle [2]. On the other hand, one can utilize the feature mapping class for approximation, which is computationally efficient and can be solved by various algorithms [3]. From this perspective, the computational burden for the inner optimization is light, making the minimax problem predominantly a maximization problem. For more details, please refer to Appendix A in the supplementary materials. Numerically, in **Table 2** of the global response PDF, we test the runtime of our algorithm and prior works, which shows our algorithm is comparable to other baselines.  \n\n**Convergence**: Theoretically, in Theorem A.1 of Appendix A, we show that our algorithm is provably convergent and realizes a fast sublinear rate $\\mathcal{O}(1/T)$ even under non-linear settings. Numerically, we plot the policy performance across optimization epochs of our algorithm in **Figure 3 (a)** in the global response PDF, illustrating the numerical convergence and stability of our algorithm (Algo: BC+UC). \n\n**Hyperparameter-tuning**: Indeed, tuning parameters selection is an open problem in offline policy optimization. Fortunately, our algorithm has desired robustness to choices of hyperparameters, when we set the hyperparameters satisfying the conditions in Theorem 5.2, i.e., $\\mathcal{O}(\\frac{n^{1/4}}{d\\log(\\bar{V}\\sqrt{n})})$. We follow your suggestion to conduct sensitivity analyses on the walker2d, hopper, and halfcheetah datasets. In **Figure 2** of the global response PDF (we only report for halfcheetah in the PDF due to page limit), it shows that our policy performance is robust over a wide value range of parameters ($\\lambda, c^* \\in [1,0.01]$), and the performance of under our choice $(c^*=0.1,\\lambda=0.1)$ is close the best. \n\n> **Weakness 2: Clarifications in Section 3**\n\nThanks for your careful reading. Accordingly, we have corrected the typos: $q^\\pi(s^0,\\pi)$, $\\mathbb{G}_{*}(x)$, and \n\n$$E_\\mu[\\lambda\\mathbb{G}_*((\\mathcal{B}^{\\pi}q^{\\pi}(s,a)- q^{\\pi}(s,a))/\\lambda)/(1-\\gamma)].$$ \n\nIn addition, we explicitly define $L(\\tau,q,\\pi)$ and $\\lambda \\xi(\\mathbb{G},\\tau)$. For the choice and sensitivity analysis of $\\lambda$, please see our last response (hyperparameter-tuning). \n\n\n> **Weakness 3: Assumption 2** \n\nThank you for pointing this out! First, we note that this boundedness condition on $\\Omega$-class is standard in literature when modeling marginalized importance weight (MIW), e.g., [2]. Also, since the $\\Omega$-class is user-specified, intending to model the true MIW, the boundedness condition is not really an assumption\nbecause the users can make a choice of $\\Omega$-class to satisfy it. \nIn our paper, we leave it as a formal assumption to keep the analysis general. Second, unlike the $\\Omega$-class, the MIW\nindeed might go to $+\\infty$, e.g., in poor coverage scenarios. In this case, using a bounded class to model an unbounded MIW may cause trouble due to model misspecification. Fortunately, our robust interval learning is motivated to solve this issue, and robust to the misspecification of $\\Omega$ class (lines 128-133 of the main paper). \n\n> **Weakness 4: Bellman completeness** \n\nIntuitively, the key insight is that we develop a weighted average Bellman error to establish the Bellman consistency (line 153: Consistency). This distinguished our algorithm from the famous API/AVI-type algorithms, e.g., [4,5,6], which rely on a squared or minimax Bellman error. It requires finding $f \\in \\mathcal{F}$ to minimize  $||f-\\mathcal{B}f ||^{2}_{L_2(\\mu)} \\approx 0$  to obtain $f \\approx q^{\\pi}$. Unfortunately, the empirical squared Bellman error is biased due to the *double-sampling* issue. They need a separate helper function class $\\mathcal{G}$ to model $\\mathcal{B}f$, and it has been shown by [6] that only when the class $\\mathcal{B}f \\in \\mathcal{G}$ (Bellman-completeness), the estimation is consistent and unbiased. In contrast, thanks to not using the squared loss, our weighted average Bellman error (use MIW as the weight to mimic the data collected by different exploration policies) is allowed to be estimated by an unbiased sample estimate (i.e., no *double-sampling* issue).\n\n> **Weakness 5: D4RL benchmarks**\n\nThanks for your great suggestion!  We evaluate our algorithm on D4RL benchmarks (walker2d, hopper, halfcheetah, and maze2d). The results of our algorithm and baselines are summarized in **Table 1** of the global response PDF. \n\n**References:**\n\n[1] Parikh, et al. (2014), Proximal algorithms, Foundations and trend in Optimization.\n\n[2] Uehara, M., Huang, J. and Jiang, N. (2020), Minimax weight and q-function learning for off-policy evaluation, ICML.\n\n[3] Sriperumbudur, B. K., et al. (2011), Universality, characteristic kernels and RKHS embedding of measures, JMLR.\n\n[4] Munos, R. et al. (2008), Finite-time bounds for fitted value iteration, JMLR.\n\n[5] Xie, T., et al. (2021), Bellman-consistent pessimism for offline reinforcement learning, Neurips. \n\n[6] Chen, J. and Jiang, N. (2019), Information-theoretic considerations in batch reinforcement learning, ICML.\n"}, {"review_id": "24DgAsxQwP", "reviewer": "Reviewer_7QtD", "summary": "This paper proposed a pessimistic offline RL method. Different from the previous method in the function approximation setting, the method proposed in this paper does not require coverage and completeness assumption. Moreover, in terms of algorithm design, this paper derives a lower confidence bound for RL objective function and explicitly optimizes it to obtain the policy, which is the first attempt in this direction. Both theoretical and empirical results are presented to support the effectiveness of this algorithm design.", "questions": "(1) If $\\mathcal{U}^\\tau_{\\infty}=+\\infty$, then how would the constant $\\mathcal{U}^\\tau_2$ and $\\mathcal{U}^*_2$ look like, will them become unbounded as well? If that is the case, then the proposed algorithm still needs completeness assumption and coverage assumption to derive the bound in Theorem 5.1.? I don't think requiring coverage assumption for this paper should be a reason for rejection since this paper already made a lot of contributions, but the author needs to provide a clear discussion for this part otherwise it will be somehow misleading since it is not obvious how to achieve global optimal policy without any coverage requirements.\n\n(2) In linear MDP the algorithm complexity is $n^{-1/4}$? If so then why the algorithm has worse dependence on $n$? Can the author also provide some high-level explanation?\n\n(3) OptDICE has been proven to outperform CQL and other baselines (see the original paper of OptiDICE, why OptiDICE performs much worse than CQL?\n\nI will raise my score if the author can answer the above questions appropriately.", "limitations": "No limitation.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) This paper proposes a novel algorithm design to address the offline policy optimization problem by explicitly optimizing a lower bound of RL objective function. This design is first proposed to my best knowledge, which is valuable.\n(2) The algorithm design proposed in this paper has a very global optimality guarantee under weaker assumptions compared with previous works.\n(3) The author also derives a practical version of the algorithm which also has a theoretical guarantee. Moreover, to demonstrate the effectiveness of this practical version, several experiment results are presented.", "weaknesses": "The experiment is not very strong:\n(1) Most of the standard simulation experiments are not considered thus the practical effectiveness of the algorithm is not convincing. The author might need to include more experiments are also included in OptiDICE paper (hopper, walker, halfcheetah, maze etc)\n(2) I was also wondering how the algorithm proposed in this paper compared most recent baseline such as TD3 + BC?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the suggestive feedback, which greatly improves our paper! We address the reviewer's comments point by point below.\n\n> **Weakness 1: Experiments**\n\nThanks for the suggestion! We evaluate our algorithm on walker2d, hopper, halfcheetah, and maze2D D4RL benchmarks. The results are reported in **Table 1** of the global response PDF. In addition, we add the baseline TD3+BC for comparison in both D4RL datasets and the original datasets (**Table 3** in the global response PDF). \n\n> **Question 1 (a): Boundedness of $\\mathcal{U}^\\tau_{2}$ and $\\mathcal{U}^\\star_{2}$ when $\\mathcal{U}^{\\tau}_{\\infty} = +\\infty$**\n\nThanks for raising this point. First, we would like to clarify that $\\Omega$-class is user-specified, intending to model the true marginalized importance weight (MIW). Thus, the boundedness of $\\Omega$-class, i.e., $\\mathcal{U}^\\tau_{\\infty}$ is determined by users. In practice, the existing works tend to consider $\\Omega$ in a bounded class  ($\\mathcal{U}^\\tau_{\\infty} < \\infty$) [1]. Second, unlike the $\\Omega$-class, the MIW might go to $+\\infty$, e.g., in poor coverage scenarios. In this case, using a bounded class to model an unbounded MIW, may cause trouble due to model misspecification. Fortunately, our robust interval learning is motivated to solve this issue, and robust to the misspecification of $\\Omega$ (lines 128-133). Third, even if setting $\\mathcal{U}^\\tau_{\\infty} = +\\infty$, the $\\mathcal{U}^\\tau_{2}$ and $\\mathcal{U}^\\star_{2}$ could be still finite. Essentially,  $||\\tau(s,a)||_{L_2(\\mu)}$ is indirectly controlled by the $\\widetilde{\\sigma}_n$ \n via $\\xi_n(\\mathbb{G}, \\tau)$. The user can specify a finite $\\widetilde{\\sigma}_n$ to make $\\mathcal{U}^\\tau_2$ finite as well in any case. \n\n> **Question 1 (b): Necessities of the completeness and coverage assumption for Theorem 5.1.**\n\nThanks for this insightful question. \n\n**For Bellman-completeness**: Intuitively, the key point of why our algorithm can relax the Bellman-completeness condition is due to our developed weighted average Bellman error. We use this type of Bellman error to establish the Bellman consistency (line 153: Consistency), instead of using a squared or minimax Bellman error in the famous API/AVI-type algorithms, e.g., [2,3,4]. Their algorithm require finding $f \\in \\mathcal{F}$ to minimize  $||f-\\mathcal{B}f ||^{2}_{L_2(\\mu)} \\approx 0$ to obtain $f \\approx q^{\\pi}$. Unfortunately, the empirical squared Bellman error is biased due to the \"double-sampling\" issue. They need a separate helper class $\\mathcal{G}$ to model $\\mathcal{B}f$. It has been shown by [4], only when the class $\\mathcal{B}f \\in \\mathcal{G}$ (Bellman-completeness), their estimation is unbiased. In contrast, thanks to not using the squared loss, our weighted average Bellman error can be estimated from an unbiased estimate without concern about the \"double sampling\" issue. \n\n**For coverage assumptions**: To derive Theorem 5.1, we indeed do not make any coverage assumptions. This is attributed to our novel error decomposition analysis (Equations I.19 to I.24 on p.53-p.54 of Appendix), which is one of the theoretic contributions of our work. In comparison to prior works, e.g., [5,6], our decomposition analysis makes the off-support errors explicitly analyzed in the regret bound, and further facilitate uncovering nice properties of our algorithm, e.g., the enhanced off-support model extrapolation which improves the applicability of our algorithm in poor coverage scenarios. Moreover, we should notice that the regret in Theorem 5.1 might not be near-optimal since the off-support error is not accessible without any coverage information. To achieve near-optimal regret with a \"best-effort\" guarantee (for global optimal policy), we still require some minimum partial coverage assumption, e.g., as used in Corollary 4.1. Note that our partial coverage condition (Definition 4.1) is weaker than the existing ones. Numerically, in **Figure 1** of the global response PDF, we study our regret convergence rate when competing with the global optimal policy.\n\n\n> **Question 2: Sample complexity**\n\nThis is a good point! Yes, the sample complexity of our practical algorithm is $\\mathcal{O}(n^{-1/4})$ which is worse than $\\mathcal{O}(n^{-1/2})$ in the information-theoretic algorithm. \n The worse dependence arises from the use of regularization. To achieve computational efficiency and tractability, our practical algorithm performs uncertainty control and Bellman consistency (line 153) via regularization instead of constrained optimization. The strength of regularization needs to be controlled for balancing the bias-variance trade-off. When setting the regularization coefficients of order ${\\mathcal{O}}\\big(\\sqrt[4]{{n}}\\big)$ as stated in Theorem 5.2, the sample complexity degrades from a minimax rate $\\mathcal{O}(n^{-1/2})$ to $\\mathcal{O}(n^{-1/4})$. The sample complexity degradation due to the regularization can be also found in prior works [3,6]. In **Figure 1** of the global response PDF, our numerical regret analysis confirms the $\\mathcal{O}(n^{-1/4})$ rate.  \n\n> **Question 3: OptDICE vs CQL**\n\nIt seems there may have been a misunderstanding regarding the results. In our paper, the average policy performance of OptiDICE is consistently better than the performance of CQL in both synthetic and real datasets.\n\n**Reference:**\n\n[1] Uehara, M., et al. (2020), Minimax weight and q-function learning for off-policy evaluation, ICML.\n\n[2] Munos, R. and Szepesvari, C. (2008), Finite-time bounds for fitted value iteration, JMLR.\n\n[3] Xie, T., et al. (2021), Bellman-consistent pessimism for offline reinforcement learning, Neurips. \n\n[4] Chen, J. and Jiang, N. (2019), Information-theoretic considerations in batch reinforcement learning, ICML.\n\n[5] Jin, Y., et al. (2021), Is pessimism provably efficient for offline rl, ICML.\n\n[6] Zhan, W., et al. (2022), Offline reinforcement learning with realizability and single-policy concentrability, COLT. \n"}, {"review_id": "aHX9rOXmv3", "reviewer": "Reviewer_UsZq", "summary": "This paper presents a bi-level structured policy optimization algorithm for offline reinforcement learning (RL). The algorithm aims to address the distributional shift and function approximation challenges in offline RL by modeling a hierarchical interaction between the policy and the value function. The lower level focuses on constructing a confidence set of value estimates to control uncertainty arising from distribution mismatch, while the upper level aims to maximize a conservative value estimate. The paper provides theoretical guarantees for the algorithm and evaluates its performance on both synthetic and real-world datasets.\n", "questions": "- At the lower level, how can the confidence set, which constraints model learning, effectively prevent overly pessimistic evaluation?\n- How can the proposed algorithm build on weaker conditions than the global data coverage? Does it benefit from the occupancy distribution estimation?\n", "limitations": "Yes", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper proposes a novel bi-level structured policy optimization algorithm that addresses the challenges of distributional shift and function approximation in offline RL. This algorithm offers a comprehensive solution for real-world scenarios.\n- The algorithm preserves the flexibility of the exploratory data distribution and enables model extrapolation, enhancing its power.\n- The paper provides theoretical regret guarantees for the proposed algorithm without relying on data-coverage and completeness-type assumptions, increasing its applicability.\n", "weaknesses": "- There is only a weak connection between several parts of the paper. It is hard to find a central claim that supports the logical flow.\n- There remain some issues unsolved in the paper. See the questions for details.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the suggestive feedback, which greatly improves our paper! We address the reviewer's comments point by point below.\n\n**Weakness 1: Connection and central claim**\n\nWe feel sorry for the confusion and thanks for helping us improve the readability of the paper. The offline policy optimization with limited exploration we study is a very challenging and complicated problem, especially when requiring sample efficiency and strong theoretic regret guarantees.  Reaching the ultimate algorithms necessarily involves numerous intermediary steps and thorough analysis. The central claim of our paper is that we propose a novel framework with strong theoretical guarantees without requiring coverage and Bellman completeness conditions, demonstrating the potential applicability in the limited-explored real-world datasets. The logical flow of the paper can be shortly summarized as: 1) we propose a bi-level structured algorithm in limited data exploration scenarios, which is bridged from a novel robust off-policy confidence interval evaluation. 2) We make great efforts to establish the theoretic regret guarantee for this algorithm, and analyze its regret without requiring coverage and completeness-type assumptions. 3) To implement the developed algorithm and practically solve it, we further construct a penalized adversarial estimation procedure. Within this framework, we still provide the regret analysis for this practical algorithm as well as obtain a strong theoretical guarantee with the relaxed assumption (relative condition number) in a linear MDP case study. 4) We empirically evaluate our practical algorithm via synthetic and real datasets, and compete with the state-of-the-art models. In the updated manuscript, we have made revisions to further improve the readability and strength the connections between several parts, we add and polish the transitional paragraphs that clearly show how one part leads to the next.\nThroughout the paper, we regularly remind the reader of how each part is connected to the central claim. We would also try to include more motivation for each support step and model. Due to the page limit, we might not be fully able to include them, but we tried our best to give more motivation in this revision. \n\n\n> **Question 1: Prevent overly pessimistic evaluation**\n\nThanks for raising this good question. The reason for preventing overly pessimistic evaluation is two-fold: First, we implement pessimism on a consistent confidence set, regarding a sufficiently small weighted average Bellman error (line 153: Consistency). This is ensured via $\\varepsilon_{n}$ as well as the concentration of empirical measures\nThis procedure ensures any function in the set is consistent with the Bellman equations, which limits the possibility of picking up a function with an overly pessimistic evaluation. More importantly, according to Theorem 3.1, the confidence set at the lower level is evaluated directly for $J(\\pi)$,  i.e., the value function at the initial state $q^{\\pi}(s^{0},\\pi)$. This distinguished us from the pointwise pessimistic penalties used in some close works [1]. They require the uncertainty lower bound of value function holds for any $(s,a) \\in \\mathcal{S} \\times \\mathcal{A}$ (see Definition 4.1 in [1]) instead of the initial state, and thus is more likely to cause overly pessimistic reasoning. Numerically, we conduct an ablation study on the lower-level components in **Figure 3** of the global response PDF. Figure 3 (a) shows that when we remove the Bellman consistency component, our algorithm with only uncertainty control (Algo: UC) is quite unstable without a consistent estimation guarantee on $q^{\\pi}$,  and suffers great performance degradation due to potentially overly pessimistic.   \n\n\n> **Question 2: Weaker assumption and occupancy distribution**\n\nThank you for raising that point. Yes, the concept of the occupancy distribution estimation closely connects the marginalized importance weights (the ratio between the occupancy distribution between offline dataset and target/exploration policy) [2]. They play important roles in our proposed algorithms. First, by leveraging the marginalized importance weights, we propose a robust confidence interval estimation (Theorem 3.1) for $J(\\pi)$ to construct a Bellman consistency set (line 153: Consistency). Once this consistency set is realized, we can then aim to maximize the rewards the trained agent would obtain in the worst possible MDP that is consistent with the observed dataset (Equation 6), i.e., performing pessimistic extrapolation from offline data without global coverage [3]. Second, the key component in our algorithm: the uncertainty control, essentially constrains the deviation from the occupancy distribution of the offline dataset to the occupancy distribution of the exploration policies via the developed discrimination function which takes the marginalized important weights as input. Thanks to this, our algorithm essentially eliminates the need to evaluate out-of-distribution actions, thus avoiding the problematic overestimation of values in poor (non-global) data coverage scenarios [5]. Note that if performing the above-mentioned uncertainty control in the space of policies [6] rather than in the space of occupancy distribution, it may fail to avoid over-estimation issues.\n\n**References:**\n\n[1] Jin, Y., Yang, Z. and Wang, Z. (2021), Is pessimism provably efficient for offline rl?, ICML.\n\n[2] Liu, Q., et al. (2018), Breaking the curse of horizon: Infinite-horizon off-policy estimation, Neurips.\n\n[3] Uehara, M. and Sun, W. (2022), Pessimistic model-based offline reinforcement learning under\npartial coverage, ICLR.\n\n[4] Lee, J., et al. (2021), Optidice: Offline policy optimization via stationary distribution correction estimation, in ICML.\n\n[5] Wu, Y., Tucker, G. and Nachum, O. (2019), Behavior regularized offline reinforcement learning,\narXiv preprint arXiv:1911.11361.\n"}, {"review_id": "HB2x6YKNBU", "reviewer": "Reviewer_C4A2", "summary": "Offline Reinforcement Learning suffers from distribution shift, arising as a consequence of limited exploration and function approximation. The paper aims to address these two challenges by proposing a bi-level hierarchical framework for policy optimization. The upper-level optimizes a policy improvement objective using a pessimistic value function. The lower level learns a conservative estimate of the value function by maintaining a confidence set for the upper level. Development of the framework is carried out by first constructing robust intervals for addressing approximation bias and then using these intervals in uncertainty quantification. Motivated by its theoretical results, the work further proposes an empirical penalized adversarial estimation algorithm which incorporates the bi-level objective using an adversarial estimation loss. While the lower level is optimized efficiently using maximum mean discrepancy principle, the upper level utilizes function approximation for learning the proximal mapping.\n", "questions": "* Can the empirical evaluation demonstrate the bounds of Theorem 4.1 and Theorem 5.2? Can experiments show the benefit of bi-level approach in tackling distribution shift (i.e- comparing with and without upper/lower levels)?\n* Can you please explain how are the Information Theoretic results useful? Are these results used to generate the penalized adversarial estimation algorithm? If not, then how should one interpret Theorem 4.1 and Corollary 4.1?\n* What is the optimal $\\tilde{\\sigma_{n}}$? Is there a criterion for setting $\\tilde{\\sigma_{n}}$?\n", "limitations": "Authors have discussed limitations and future work.", "rating": 7, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 4, "strengths": "* The paper is well written and organized. Specifically, the paper builds the framework in a structured way.\n* While the paper borrows from past results in tackling distribution shift and constrained optimization, the bi-level approach and its abstraction between policy and value objectives is novel.\n", "weaknesses": "* **Empirical Evaluation:** My main concerns are centered at the empirical evaluation and experiments carried out to assess the bi-level framework. Experiments do not validate the theoretical claims of the work and only evaluate the performance of the framework. Ideally the empirical evaluation should validate whether regret bounds of Theorem 4.1, Theorem 5.1 or Theorem 5.2 would hold or not. Authors can compare empirically whether the bound of Theorem 5.2 is tight and that if $\\lambda$ and $c^{*}$ are chosen as per the set criteria, regret is close to the bound of Theorem 5.2. Similarly, experiments do not demonstrate the benefits of bi-level approach in addressing distribution shift. It would be worthwhile to compare the performance with and without the upper/lower levels and assess if regret bounds still hold.\n* **Significance of Information-Theoretic Results:** Section 4 appears to be disconnected from the rest of the paper. While the Information Theoretic algorithm does not provide an empirically feasible method, it produces a baseline policy improvement scheme using bias and uncertainty errors. However, the significance of these results is unclear. To the best of my knowledge, the information theoretic results are not used to generate the penalized adversarial estimation algorithm. Neither they are used in the empirical evaluation or in producing a tighter regret bound. It would be helpful if the authors could explain the significance and utility of these results and how they should be interpreted. It would also be helpful if the paper could throw light on the benefit of near-optimal regret in Corollary 4.1.\n* **Utility of $\\tilde{\\sigma_{n}}$:** From my understanding, $\\tilde{\\sigma_{n}}$ trades off pessimism for policy improvement. This indicates that the utility of $\\tilde{\\sigma_{n}}$ is not well understood. Setting $\\tilde{\\sigma_{n}}$ to a lower value can hinder policy performance as the lower level will yield an overly conservative value function. On the other hand, setting $\\tilde{\\sigma_{n}}$ to a higher value leads to distribution shift. It would be helpful to have an optimal value of $\\tilde{\\sigma_{n}}$ characterized or a criterion for selecting $\\tilde{\\sigma_{n}}$ based on policy performance or pessimism.\n\n## Minors\n\n* line 29: amplifying -> amplifies\n* line 32: to contain -> contains\n* line 79: discounted -> discount\n* line 125: sepcified -> specified\n* line 137: established the CI for $J(\\pi)$ is presented in Theorem 3.1.\n* line 234: concentrability -> concentratibility\n* line 275: conditional -> conditioned\n* line 329: set propertly choose -> properly choose\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the suggestive feedback, which greatly improves our paper! We address the reviewer's comments point by point below.\n\n\n> **Weakness and Question 1:  Empirical evaluation**\n\nThanks for your great suggestions! \n\n**For regret validation**: \nWe first would like to clarify that it is hard to conduct empirical evaluations for Theorem 4.1 since it is for our information-theoretic algorithm. Even when considering our practical algorithm, empirically validating the tightness of the bound is still not easy. This is because some key components, e.g., concentrability coefficient, universal constants, and function class complexity in the regret bound, are difficult to (accurately) estimate from datasets. Nevertheless, following your suggestion, we empirically verify the convergence rate of regret bound in Theorem 5.2: \n\nTypically, we lack information regarding the optimal policy and its coverage within offline datasets, making it challenging to accurately compute the regret. Therefore, we carefully design a synthetic environment. We only briefly describe the environment due to word limit: the reward $r(s, a)=(a-\\beta s)^{\\top} \\Lambda(a-\\beta s)$ with coefficient matrix $\\beta$ and the negative definite matrix $\\Lambda$. Therefore, the optimal policy has an analytical form $\\pi^{\\star}(s)=s^{\\top} \\beta$, which is important to calculate precise regret. The dataset is generated following $\\pi_b$ such that $a = \\beta s + \\mathcal{N}\\left(0, \\sigma_0^2 I \\right)$, indicating the data is less explored when $\\sigma_0$ is small. In **Figure 1** of the global response PDF, we study the convergence rate of regret, which validates the  $\\mathcal{O}(n^{-1/4})$ rate in Theorem 5.2.  \n\n**For framework validation**: Given that the upper level is performed for policy updating, it cannot be removed. \nThus, we guess that you may suggest studying the effectiveness of the lower-level components (line 153): uncertainty control (UC) and Bellman consistency (BC). To this end, we evaluate the policy performance across the optimization epochs and the regret. The results are provided in **Figure 3** of the global response PDF. **Figure 3 (a)** shows that the algorithm only with UC is quite unstable due to inconsistent estimation on $q^{\\pi}$; the algorithm only with BC is relatively stable but suffers performance degradation due to over-estimation issues and insufficient model extrapolation. **Figure 3 (b)** indicates the sub-optimal regret and slow convergence rate  when either UC or BC is absent.  \n\n> **Weakness and Question 2: Significance of Information-Theoretic Results**\n\nThis is a great point! Yes, the information-theoretic results are not directly used to generate the later practical algorithm. However, their utility is threefold. First, they provide rigorous guarantees for our information-theoretic algorithm, particularly under the scenario where no coverage and completeness-type conditions hold. \nSecond, in the development of the theorems, we propose a novel error decomposition analysis (Equations I.19 to I.24 on p.53-p.54 of Appendix), which is one of the theoretic contributions of our work. In comparison to existing works, e.g., [1,2], our decomposition analysis makes the off-support errors explicitly analyzed in the regret, and better characterizes the roles of on-supports and off-support errors. \nThird, with these results, we can well-understand and uncover some hidden nice properties of our algorithm: enhanced off-support model extrapolation. This motivates us to design and implement our practical algorithm. In particular, Corollary 4.1 \nprovide a stronger regret guarantee than Theorem 4.1, and position our work within the existing literature [1,2]. Under a weak partial coverage assumption, our algorithm achieves ``best efforts'' guarantee, indicating no other policy covered by the dataset is better than our learned policy. To the best of our knowledge, this is the strongest regret result in the existing literature.  \n\nWe also note that Theorem 4.1 do have a tighter bound than the bound in Theorem 5.1 (for our practical algorithm). Theorem 4.1 has a fast rate $\\mathcal{O}(n^{-1/2})$ compared to $\\mathcal{O}(n^{-1/4})$ in Theorem 5.1. Essentially, our practical algorithm trade-off some sample efficiency to gain great computational efficiency.  \n\n> **Weakness and Question 3: Utility of of $\\widetilde{\\sigma}_n$**\n\nThanks for raising this point. Theoretically speaking, the $\\widetilde{\\sigma}_n$ can be set by the condition in Theorem 4.1. However, in practice, it is quite challenging to find a universal rule to identify the optimal threshold. As you mentioned, it depends on how much pessimism the users would like to consider and how well the dataset is explored. We follow the convention [2,3] to set $\\widetilde{\\sigma}_n$ with a certain rate according to our theoretical results. For implementing our practical algorithm, we set $\\lambda$ be of order $\\mathcal{O}(\\frac{n^{1/4}}{d\\log(\\bar{V}\\sqrt{n})})$ (the effect of $\\widetilde{\\sigma}_n$ is transferred to $\\lambda$ in the practical algorithm). Fortunately, our algorithm has desired robustness to choices of hyperparameters. It has been shown from our \nsensitivity analyses on the walker2d, hopper, and halfcheetah datasets in **Figure 2** of the global response PDF (we only report halfcheetah due to page limits). The policy performance is robust over a wide value range ($\\lambda,c^*$ in $[1,0.01]$), and the performance under our choice $(c^*=0.1,\\lambda=0.1)$ is close to the best.   \n\n> **Minors**\n\nThanks for your careful review, we have corrected the typos. \n\n**References:**\n\n[1] Jin, Y., Yang, Z. and Wang, Z. (2021), Is pessimism provably efficient for offline rl?, ICML\n\n[2] Lee, J., et al. (2021), Optidice: Offline policy optimization via stationary distribution correction estimation, ICML\n\n[3] Ma, J. Y., et al. (2022), Offline goal-conditioned reinforcement learning via f-advantage regression, Neurips. "}, {"review_id": "txyc2fuOGH", "reviewer": "Reviewer_q6tp", "summary": "This manuscript proposes a bi-level structure for solving offline RL problem. The authors design the lower level constructing a set of value estimates, while the upper level maximizing the conservative value estimate. Specifically, the author provides a penalized adversarial estimation algorithm. The superiority of the proposed method is shown from both real world and synthetic data.   ", "questions": "1. There are some confusion in understanding the definition of Consistency  above line 154, should the $\\mathcal{Q}_{\\epsilon_n}$ be related with policy $\\pi$?\n2. In line 3 of Algorithm 1, it is required to solve a maxmin problem with iterative method, so how is the time consumption of the proposed method? Could the author provides some experiment study or conceptual analysis on this issue?\n3. Any practical suggestions on selecting $\\mathbb{G}(x)$ and the initial function of $\\tau(s,a)$? The author also mentions the proposed method does not require data-coverage, could this issue be demonstrated from experiments? Say using a biased policy as behavior policy to generate data to learn offline RL policies.", "limitations": "see questions and limitations", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The hierarchical structure for solving offline RL problem is very interesting.\n2. The proposed method considers a confidence set of value estimates as well as the uncertainty, and it effectively prevents from being too pessimistic.\n3. The manuscript provides solid theoretical results, and it shows the proposed method could work without requiring data-coverage, which sounds quite useful in offline RL scenario.", "weaknesses": "1.  It is suggested to add some important steps in Algorithm 1 from Line 270 ~ Line 281, otherwise the Algorithm 1 is too simple while there are many details in 270 ~ Line 281, which is somehow difficult to read.\n\n2. The authors considers the synthetic data (CarPole) and real-world data (Type I Diabetes), as a common benchmark in offline RL research, the D4RL tasks are widely studied in offline RL experiments. It is suggested to consider some D4RL task in the experiment. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank the reviewer for the suggestive feedback, which greatly improves our paper! We address the reviewer's comments point by point below.\n\n> **Weakness 1: Algorithm 1**\n\nWe feel sorry for the misleading. Due to the page limit, we actually provide a comprehensive discussion of Algorithm 1 in Appendix A of the supplementary materials. It includes a detailed version of Algorithm 1, a discussion on solving maximin problem (line 3 of Algorithm 1), a closed-form update rule for mirror descent (line 4 of Algorithm 1), as well as a convergence analysis of the algorithm and its technical proofs.  \n\n\n> **Weakness 2: D4RL tasks**\n\nThank you for your suggestions! We follow your suggestion to evaluate our algorithm on walker2d, hopper, halfcheetah, and maze2D D4RL benchmarks. The results are reported in **Table 1** of the global response PDF. Our algorithm achieves the best performance in 7 tasks and is comparable to the baselines in the remaining tasks.  \n\n> **Question 1:  $\\mathcal{Q}_{\\varepsilon_n}$ indexed by $\\pi$**\n\n Thanks for pointing this out. Yes, the Bellman consistency set $\\mathcal{Q}_{\\varepsilon_n}$ defined in line 154 is dependent on $\\pi$. We aim to construct a set of functions that is consistent with the q-function under the policy $\\pi$, i.e., $q^{\\pi}$. \n\nTo avoid any confusion, we modify the notation to $\\mathcal{Q}^\\pi_{\\varepsilon_n},$ to reflect its dependency on $\\pi$.\n\n> **Question 2: Time consumption of the maximin problem**\n\nThank you for arising this point. In the following response, we follow your suggestions to study the time complexity/consumption from both theoretical and numerical perspectives.\n\nFor the maximin problem, the inner optimization is easy to solve. On the one hand, it could yield a closed-form global solver using the maximum mean discrepancy principle [1,2]. On the other hand, one can utilize the feature mapping class for approximation, which is computationally efficient and can be solved by various algorithms [3]. From this perspective, the computational burden for the inner optimization is light, and the maximin problem is essentially a maximization problem. For more details, please see Appendix A of the supplementary materials. \n\nTheoretically, we study the time complexity of the optimation presented by Theorem A.1 in Appendix A, which shows that our maximin optimization realizes a fast sublinear rate $\\mathcal{O}(1/T)$ even under non-linear settings. Numerically, we test the runtime of our algorithm in comparison to the prior works. We report the results in **Table 2** of the global response PDF,\nwhich shows our algorithm is comparable to other baselines. \n\n> **Question 3 (a): Practical choices on $\\mathbb{G}(x)$ and $\\tau(s,a)$**\n\nThanks for your question. There are many choices for $\\mathbb{G}(x)$, e.g., Bhattacharyya distance [4], $f$-divergence [5], as well as simple quadratic form functions which we used in our work (see Appendix B.2 in the supplementary materials). In practice, we prefer to select a simple but optimization-friendly choice for the $\\mathbb{G}(x)$. The quadratic form function is one of the best choices and has been widely used in the machine learning community [6,7,8]. \n\nFor the choice of $\\tau \\in \\Omega$, we first note that $\\tau$ is for modeling the importance weights. Due to the complex structure of the marginalized importance weight, it demands a sufficiently flexible non-linear function approximation class, e.g., Reproducing Kernel Hilbert Spaces (RKHS), deep neural networks, for optimization [9]. In most of our experiments, to ensure the flexibility of $\\tau$, we model $\\tau$ by a two-layer feedforward neural network with the layer width $256$ and use ReLU as the activation function. Additionally, the weights are initialized in accordance with the Xavier initialization [10].\n  \n> **Question 3 (b): Data-coverage experiments**\n\nThank you for your suggestions. In our original experiments, we control the $\\alpha$ for simulating the scenarios with varying data coverage levels (poor, medium, relatively high). In practice, it's unfeasible to generate an offline dataset with absolute zero data coverage. This is because whenever a policy is rolled out in an interactive environment, the generated datasets inevitably exhibit some coverage. Nevertheless, by setting $\\alpha =0.1$, our \"poor coverage\" scenario is quite close to a \"no coverage\" situation.\n\nWe guess that by \"biased policy,\" you might be referring to a random or non-optimal policy. In our new experiments on the D4RL benchmark, we used offline datasets generated by a randomly initialized policy (which can be considered a biased policy), e.g., halfcheetah-random. These results can be found in **Table 1** of the global response PDF. We can observe that our algorithm is comparable to other baselines in such settings. \n\n**References:** \n\n[1] Gretton, A., et al. (2012), A kernel two-sample test, The Journal of Machine Learning Research.\n\n[2] Shi, C., et al. (2022), A minimax learning approach to off-policy\nevaluation in confounded partially observable Markov decision processes, ICML. \n\n[3] Sriperumbudur, B. K., et al. (2011), Universality, characteristic kernels and rkhs embedding of measures, JMLR.\n\n[4] Choi, E. and Lee, C. (2003), Feature extraction based on Bhattacharyya distance, Pattern Recognition.\n\n[5] Sason, I. and Verdu, S. (2016), f-divergence inequalities, IEEE Transactions on Information\nTheory.\n\n[6] Belousov, B. and Peters, J. (2017), f-divergence constrained policy improvement, arXiv preprint\narXiv:1801.00056.\n\n[7] Tao, C., et al. (2018), Chi-square generative adversarial\nnetwork, ICML. \n\n[8] Nachum, O., et al. (2019), Algaedice: Policy gradient from arbitrary experience. arXiv preprint arXiv:1912.02074.\n\n[9] Uehara, M., Huang, J. and Jiang, N. (2020), Minimax weight and q-function learning for off-policy\nevaluation, ICML.\n\n[10] Glorot, X. and Bengio, Y. (2010), Understanding the difficulty of training deep feedforward neural\nnetworks, AISTAT.\n"}]

Author rebuttal:
We are grateful to all reviewers for taking the time to review our paper and sharing insightful and positive feedback. We are encouraged that they found the submitted work to be novel (7QtD,UsZq,C4A2) and interesting (75WN, q6tp), addressing a challenging and meaningful research problem (7QtD,UsZq), with a well-written and structured presentation (75WN, C4A2), solid and useful theoretical analyses (7QtD,75WN,q6tp,UsZq), as well as demonstrating algorithm's effectiveness in various datasets empirically (75WN, 7QtD).

We appreciate all reviewers’ constructive comments and questions; We have revised our paper based on their suggestions, which greatly improve our paper. We summarize all the major changes that we have made below. All changes have been reflected in our updated main manuscript and supplementary materials.

* We have conducted additional experiments on D4RL benchmarks (walker2d, hopper, halfcheetah, and maze2D) for better positioning our work within the existing literature. Additionally, we have added a strong baseline TD3+BC [1] for comparison. The results are provided in Table 1 and Table 3 of the attached one-page PDF, respectively.  
* We have performed ablation studies on investigating the effect of algorithm components: uncertainty control and Bellman consistency. Please see Figure 3 of the attached one-page PDF for detailed results.
* We have strengthened arguments on the choice of hyperparameters and conducted the corresponding sensitivity analysis. The results are included in Figure 2 of the attached one-page PDF. 
* We have conducted numerical experiments to empirically validate our theoretical results. Please see Figure 1 of the attached one-page PDF for detailed results. 
* We have extended the explanation and interpretation of assumptions, conditions, and theoretical results.  

**Reference:**

[1] Fujimoto, S., and Gu, S. S. (2021). A minimalist approach to offline reinforcement learning. Advances in neural information processing systems, 34, 20132-20145.


Meta-review: This paper introduces a bi-level framework for offline reinforcement learning (RL) to tackle the challenges of distributional shift and function approximation. Unlike previous methods, it does not require coverage and completeness assumptions. The framework consists of two levels: the lower level focuses on creating a confidence set for value estimates to manage uncertainty due to distribution mismatch, while the upper level aims to optimize a policy using a pessimistic value function. Theoretical guarantees are provided, and the effectiveness of the algorithm is empirically validated. The authors have provided a detailed response to the concerns raised by the reviewers. We encourage the authors to add the new discussion regarding the significance of the regret and new empirical results into the revised final version of the paper.
Decision: Accept (poster)