Offline Minimax Soft-Q-learning Under Realizability and Partial Coverage
Authors: Masatoshi Uehara
Nathan Kallus
Jason D. Lee
Wen Sun
Venue: NeurIPS 2023 poster (2023)
Keywords: Reinforcement learning theory
PAC RL
Offline Reinforcement learning
TL;DR: Value-based offline RL under single realizability, single-policy coverage, and without explicit pessimism

Abstract: We consider offline reinforcement learning (RL) where we only have only access to offline data. In contrast to numerous offline RL algorithms that necessitate the uniform coverage of the offline data over state and action space, we propose value-based algorithms with PAC guarantees under partial coverage, specifically, coverage of offline data against a single policy, and realizability of soft Q-function (a.k.a., entropy-regularized Q-function) and another function, which is defined as a solution to a saddle point of certain minimax optimization problem). Furthermore, we show the analogous result for Q-functions instead of soft Q-functions. To attain these guarantees, we use novel algorithms with minimax loss functions to accurately estimate soft Q-functions and Q-functions with 
-convergence guarantees measured on the offline data. We introduce these loss functions by casting the estimation problems into nonlinear convex optimization problems and taking the Lagrange functions.

Offline Minimax Soft-Q-learning Under Realizability and Partial Coverage
Masatoshi Uehara Genentech uehara www.amattttttseeeeeeeeeoo com
Nathan Kallus Cornell University
Kallus@cornell.ee edu
Jason D. Lee
Wen Sun
Princeton University
Cornell University ws455@cornell.c
jasonlee@ppzinceton..eee
Abstract
offline RL, we have no opportunity to explore so we must make assumptions that the data is sufficient to guide picking good policy, and we want to make these assumptions as harmless as possible. this work, we propose value-based algorithms for offline RL with PAC guarantees under just partial coverage, specif- ically, coverage of just a single comparator policy, and realizability rantopy-regullarized Q-function of the single policy and related function defined as a saddle point of certain minimax optimization problem. This offers refined and generally more lax conditions for offline RL. We further show analogous result for vanilla Q- Q-functions under soft margin condition. To attain these guarantees, we leverage novel minimax learning algorithms and analyses accurately estimate either soft or vanilla Q-functions with strong 1.2-covergence guarantees. Our algorithms' loss functions arise from casting the estimation problems nonlinear convex optimization problems and Lagrangiffing. Surprisingly we handle partial coverage even without explicitly enforcing pessimism.
the soft
Introduction
In offline Reinforcement Learning (RL), we must learn exclusively from offline data and are unable actively interact with the environment (Levine al., 2020). Offline RI. has garnered considerable interest in a range of applications where experimentation may be prohibitively costly or risky.
Offline RL is generally based on two types of assumptions: sufficient coverage in the offline data and sufficient function approximation. For instance, classical Fitted---iteration (Antos et al., 2008; Chen and Jiang, 2019) requires (a) full coverage in the offline data, max(s,a) di. (8, a)/ (s, a) co for any policy where Pr, (s, a) is the offline data's distribution on the states and actions and dr,po (s, a) the state-action occupancy distribution under a policy æ and initial-state distribution Mo(s); (b) realizability of the Q" Q"-function in a hypothesis class; and (c) Bellman completeness, iee. the Bellman operator applied to any function the hypothesis class remains in the class. Full coverage (a) and Bellman completeness (c) can be particularly stringent because offline data is often insufficiently exploratory and Bellman completeness significantly restricts transition dynamics.
To overcome these challenges, we here propose algorithms with guarantees under realizability of single functions and refined partial coverage of single policies, and without Bellman completeness. We tackle this by introducing two novel value-based algorithms. The first algorithm, MSQP (mimimax soft-Q fet----leanning with penalization). comprises of two steps: learning soft Q-functions (a.k.a., entropy-
'This work done Comell University
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table 1: Summary of partial-coveragelype guarantees with model-free general function approxima- tion. Here, w* := dr _uo Pb where wo is the occupancy distribution under the optimal policy nt starting from AA and Po is the distribution over the offline data. A function Vi; is a regularized marginal density ratio that satisfies 2 wº. Functions q", 92 97 are the optimal Qf*ffnncton, the soft Q-function, and the Q-function under a policy т, respectively. Functions vx 1 are Lagrange multipliers of specific minimax optimization problems. The operator BT is a Bellman operator under policy л. Function classes W, 2, L, V consist of functions that map states (and actions) to real numbers. Note the guarantees provided by Jiang and Huang (2020); Xie et al. (2021) are more general than the below in that the output policy can compete with any policy in the policy class II. For simplicity, we set the comparator policy to be the optimal policy π in this table. Note that other studies (Ozdaglar et al., 2023; Rashidinejad et al., 2022; Zhu et al., 2023) proposing model-free general function approximation under partial coverage rely on the completeness-tyy assumption as in (Xie et al., 2021) or realizability for any æ in Jiang and Huang (2020).
Primary Assumptions
Jiang and Huang (2020)
w" E W, 4rr V E II Ix E Q C El "2 W, va EV
Xie et al. (2021)
Zhan et al. (2022)
MSQP
La E 2, l EL
Chen and Jiang (2022)
Hard margin, w" W. q" EQ Soft margin, q" E 2
MQP
regularized Q-functions, as defined in Fox et al., 2015; Schulman et al., 2017) from offline data, and using the softmax policies of the learned soft f-functions. The second algorithm, MQP (mimimax Q-learning with penalization), consists of two steps: learning standard Q-functions from offline data and employing the greedy policy of the learned Q function on the offline data.
two algorithms,, we attain PAC guarantees under partial coverage and realizability, yet without Bellman completeness. In particular, in MSQP using soft Q-functions, we ensure strong performance under the realizability of ga, t and the (density-ratio-base)) coverage (ax(s.a) dn (s, a) (Po a) oc. Here 9 is soft Q-function, 1 is a function that possesses certain dual relation to Lop Taa is the soft-max optimal policy, and a is the temperature parameter for the entropy-rege reauoy-reullaizzation Notably, max(s.a) d=g wo (s, a) (s a) < 00 is signifi- cantly less stringent than the uniform coverage in that the coverage is only imposed against a policy T; In MQP using Q-functions, we similarly ensure strong performance under a soft margin, the realizability of q², 1", and the partial coverage max() dx. wno (s. a) (s, a) < o0. Here g" is the vanilla Q-function and 1* is a function that possesses a certain dual relation to q", and " is the usual optimal policy. Note the soft margin is introduced to allow realizability on standard Q- functions rather than soft Q-functions. However, the conditions m dx; to (s, (), a) < oo or max d (s, / (s, a) < oo may still be strong as these marginal density ratios may not exist in large-scale MDPs. For example, this condition is easily violated when the initial distribution 140 is not covered by Ps (i.e., max, ( = oo where Pa(s) = E. (s(s, a)). Therefore, as an additional innovation, in our algorithms we can further relax these density-ratio-base partial coverage conditions. Specifically, we can demonstrate results under a refined partial coverage, which is adaptive to Q-function classes, even when the initial distribution Ho is not covered by Ps.
Using the
partial
The primary challenge lies in the design of loss functions for effectively learning soft Q-functions and vanilla fuuutioos from offline data without Bellman completness. To tackle this, we devise new minimax loss functions with certain regularization terms to achieve favorable L=-convereence rates on the offline data (i.e., in terms of B(s.a)-P,, 1f9. - 4)² (s. a)l given an estimator q). This result serves as the key building block for obtaining refined partial coverage under realizability and is of independent interest in its own right. Existing results are often constrained to specific models, such as linear models (Shi et al., 2022a), or they require Bellman completeness (Antos et al., 2008; Chen and Qi, 2022; Chen and Jiang, 2019). In contrast, our guarantee is applicable to any function
"Note μi and P. could be generally different even in the contextual bandit setting. This important setting often considered in the literature on external validity/transpottaailty in causal inference, as results of randomized clinical trials cannot be directly transported because covariate distributions in offline data and target data are different (Cole and Stuart, 2010; Pearl and Bareinboim, 2014; Dahabreh et al., 2019).

---

approximation method, without the need for Bellman completeness. To the best of our knowledge, this is the first guarantee of its kind.
Our work exhibits marked improvements over two closely related studies (Zhan et al., 2022; Chen and Jiang, 2022). Similar to our work, they propose algorithms that operate under the realizability of specific functions and partial coverage, yet without Bellman completeness. Zhan et al. (2022) ensures PAC guarantee under (a') partial coverage in the offline data ma dx; no (s, / (s, a) < co where Ta is a Specific near-optimal policy under the regularization, which differs from the soft /
optimal policy, and (b') realizability of de: P. and the regularized value function. However, unlike MSQP, it is unclear how to refine the abovementioned coverage, i.e., the guarantee could be vacuous when the initial distribution is not covered by offline data. A similar guarantee, but without regularization, is obtained under the additional hard margin (a.k.a., gap) condition in Chen and Jiang (2022). Our soft margin is a strict relaxation of the hard margin, which important because, unlike the soft margin, the hard margin generally does not hold in continuous state spaces and involves very large constants in discrete state spaces. Lastly, although Chen and Jiang (2022); Zhan al. (2022) use completely different algorithms and attain guarantees for regularized value-functtios and non non-regularized value functions, respectively, our guarantee can afford guarantees for regularized and non-regularized value-functions in unified manner since MQP can be seen as a limit of MSQP when a goes to O.
Our contributions are summarized below and in Table 1.
1. We establish that the optimal policy can be learned under partial coverage and realizabilitty of the optimal soft Q-function and its dual. Notably, we abstain from the use of possibly stronger conditions in offline RL, such full coverage, Bellman completeness, and uniform realizability over the policy class (such as 4T E Q for any π as in Jiang and Huang. 2020). In particular, while similar guarantee is provided in Zhan et al. (2022), guarantee has an advantage in that we are able to potentially accommodate scenarios where the initial distribution is not covered by P.. This is feasible because our algorithm is value- based in nature, which allows us to leverage the structure of the Q-function classes and refine the coverage condition.
partial coverage
2.
We demonstrate that the optimal policy can be learned under partial coverage, realizability of the Q-function and its dual, and soft margin. While a similar guarantee is obtained in Chen and Jiang (2022), our guarantee has the advantage that the soft margin is significantly less stringent than the hard margin required therein.
1.1 Related Works
We summarize related works as follows. Further related works is discussed in Section A.
Offline RL under partial coverage. There is growing number of results under partial coverage following the principle of pessimism in offline RL (Yu et al., 2020; Kidambi et al., 2020). In comparison to works that focus tabular (Rashidinejad et al., 2021; Li et al., 2022: Shi al., 2022b; Yin and Wang, 2021) or linear models (Jin et al., 2020; Chang et al., 2021; Zhang et al., 2022: ggayen-Tang et al., 2022; Bai et al., 2022), our emphasis is on general function approximation (Jiang and Huang, 2020; Uehara and Sun, 2021; Xie et al., 2021; Zhan et al., 2022; Zhu et al., 2023; Rashidinejad al., 2022: Zanette and Wainwright, 2022: Ozdaglar et al., 2023). Among them, we specifically focus on model-free methods. The representative work is summarized in Table 1.
Soft (entropy-regularize) Q-functions. Soft Q-functions are utilized in various contexts in RL (Geist et al., 2019; Neu et al., 2017). They have been shown to improve performance in online RL settings, as demonstrated in Soft Q-Learning (Fox et al., 2015; Schulman et al., 2017) and Soft Actor Critic (Haarnoja et al., 2018).
the field of imitation learning, they play a crucial role in Maximum Entropy IRL (Ziebart et al., 2008, 2010). Furthermore, within the realm of offline RL, these soft Q-functions are utilized to make the learned policy and behavior policy sufficiently similar (Wu et al., 2019; Fakoor et al., 2021). However, to the best of the authors' knowledge, none of these proposals the context of offline RL have provided sample comeeeeoooppeii complexity results under partial coverage.
Lagrangian view of offline RI. In the realm of offline policy evaluation (OPE), Nachum and Dai (2020); Yang et al. (2020); Huang and Jiang (2022) have formulated the problem as constrained
3

---

linear optimization problem. Notably, within the context of policy optimization, Zhan et al. (2022) have proposed estimators for regularized density ratios with L'-convereeece guarantees. which is a crucial step in obtaining near-optimal policy. Our work is similarly motivated, but with a key distinction: our target functions are the soft Q-function and Q-function, rather than the regularized density ratio, which presents additional analytical challenges due to the nonlinear constraint.
Preliminaries
We consider an infinite-horizon discounted MDP M = (S, P.r. P.r. P.r.7:P)) (o) where S is the state space, A is the finite action space, ? E [0, 1) is the discount factor, reward r is a random variable following P. | ss s,a) on [miin ]mma]] (Rmin 0), 14o is the initial distribution. A policy a map from the state to the distribution over actions. We denote the discounted state-action occupancy distribution under policy starting from initial distribution Mo by dz a). With slight abuse of notation, we denote dx = -o ug a). We define the value under и as J(x) = E En 7'F(s;; az)] where the expectation is taken under и. We denote the optimal policy arg max; (TT) by 't' and its Q-function E,, (E,,,,ifii. 7Ff(s,, a,) 80 8, 0,00 = a) by q" (s,
S + ((A)
In offline RL, using offline data D {(ss; at ri, s() i I.....n.. n), we search for the policy n' that maximizes the policy value. We suppose each (s;, as, T2, s() is sampled i.id. from ~ Po, a; ~ T6(- s) P. St, (r), s P(- st, a;). We denote the sample average of f by E,, [f(s, a, s - - [88, (e,, Ta, 8(), and the expectation of f with respect the offline data distribution by [s a, s')l (without any scripts). The policy no used to collect data is typically referred to as a behavior policy. With slight abuse of notation, we denote Pa a) = (s) s).
Notation. We denote the support of Po(-) by (S x A)b, and the - -nor on (S x A); by |1- The L -norm on (S A) is denoted by || 1loo We define wn (s. a) too (s, / a) (if exists).
exp(h(s.a)) We define sofmax(()) (h) Σ. exp(h(s.a)) and ||A/|2 Ps,a) [h2 (s, 1/2 for h S x A + IR. We denote universal constants by c1 .2..... We use the convention a/0 = do when a * 0 and 0/0 = O.
3 Algorithms
In this section, we present two algorithms. The first algorithm aims to estimate the soft optimal policy by first estimating a soft Q-function. The second algorithm estimates the optimal policy after estimating the Q-function.
3.1 Minimax Soft- loft-Q-learning with Penalization
Our ultimate aim is to mimic the optimal policy π-. As first step, we begin by finding a policy that maximizes the following regularized objective: arg max, (a()) where for we define
Ja (T) = (1 - -
|r a log(m(a | s)/=a(a s)}]
KL ponalty (between x and ms)
This objective function is used in a variety of contexts in RL. as mentioned in Section 1.1. The optimal policy that maximizes (T) with respect to π is
= softmax(g,//o + To).
where La S A + R is the soft Q-functon uniquely characterized by the soft Bellman equation: Egr::(/rPPP..... prle::/B....p(.a///P/e......
(s') + r- - (s, 8, a) = 0, where Pa,m [8 x A + R SS + R] has Pa (g)(s a log E. (exp(((ss a')/a)/((d (a' $)}. As opposed to the standard objective function with = 0, the KL penalty term serves as regularization term that renders : sufficiently proximate to Ty. As a approaches oc, the optimal policy , approaches тe- On the other hand, when = 0, x is n*. Thus, in order to compete with .. is necessary to keep a sufficiently small. We elaborate on this selection procedure in Section
The natural method for offline RL using this formulation involves learning z from the offline data and plugging into (I). The question that remains is how accurately learn da from the offline data. We consider the following optimization problem:
arg minge or 0.5 (. (2, a)]
(2)

---

Algorithm MSQP (Minimax Soft-Q-learning with Penalization)
1: Require: Parameter a R+, Models C (S A RR.
2: Estimate la as follows:
da E arg min max En (s, (y (1) + ((s,(((s)))((s,)))
(5)
gE@ lE2
3: Estimate the soft optimal policy: n. = softmax(Qa mo)
Algorithm 2 MQP (Minimax Q*-learning with Penalization)
1: Require: Models Q, C C [8 x A A
2: Estimate q² as follows:
f ÿo arg arg max E, 99t (s. a2/2 + tymaxq(s' d') +r -((( NEQ IEC
(8)
3: Estimate the optimal policy: fo s) = arg max (ax
where O' consists of all functions q: : x A IR satisfying
Be (s0) (g)(s') ( as, 8, a V(s,a) E (8 A)a-
Here, because of the constraint (3), the solution is g. Furthermore, we use q² a) in (2) because this choice relaxes the equality in (3) inequality 0 as will demonstrate in Section B. Consequently, the entire optimization problem outlined in (2) and (3) transforms into a convex optimization problem.
Then, using the method of Lagrange multipliers, (2) is transformed into min, maxi La (q, Lo (q. =- [q (s, a2 + {yla, (0)(s')))))))))))))))))))))))( + a)s
Being motivated by the above formulation, our MSQP algorithm, specified in Algorithm 1, approxi- mates this formulation by replacing expectations with sample averages and restricting optimization to function classes with bounded complexity.
Remark 1 (Computation). Although minimax optimization is generally difficult to solve, it is compu- tationally feasible when we choose RKHS or linear function classes for C. In this case, we can solve the inner maximization problem analytically closed form, as the objective function is linear in l. As a result, the minimax optimization problem reduces to empirical risk minimization.
3.2 Minimax Q Q'-learning with Penalization
Next, examine a policy learning algorithm utilizing Qt-functions. To learn Q*, our objective function is derived from the constrained optimization problem:
arg min 2- (e) (g"(s,
(6)
where O consists of all functions g
TR satisfying
Y(s,a) (S A)s; (. by m q(', d') +r g(s, a) a. =.
Next, again using the method of Lagrange multipliers, (6) is transformed into
min, max Lu(g, 1), Lo(g, 1) := E[q² (s, a)/2 + fy max, q(s', a') + g(s, ((),,
(7)
Note Lg is the limit of La as a +
Our MQP algorithm, specified in Algorithm 2, similarly approximates this formulation by replacing expectations with sample averages and restricting optimization to function classes with bounded complexity. Our final policy is greedy with respect to the learned Q-function but restricting to the support of the offline data in order to avoid exploiting regions not covered by the offline data.
Remark 2 (Prominent differences). There exist several other minimax estimators for Q" including BRM (Antos el al., 2008) and MABO (Xie and Jiang, 2020). Although these ensure convergence guarantees in terms of Bellman residual errors, they do not ensure the guarantee in terms of I,?. errors, which our focus. Our minimax objective function differs significantly from that of the aforementioned approaches, and its unique design plays pivotal role in enabling L rates.
5

---

L' converegeeeee Rates for Soft Q-functions and Q* Q*-functions
To analyze our Q-estimators arg menge maxier (g. on the support (S x A)s. Building on this, we prove coneerereee rates for do and ÿo- These L==convergence guarantees are subsequently translated into performance guarantees of the policies we output in Section 5.
first establish conditions that ensure q
4.1 Identification of Soft Q-functions
Consider an -pacee H. where the inner product is define as (h1, h2) = (e..)) (ha a)h2(s, a)]. Then we define two operators and key function:"
Pa H Eg B.s If(s'' (f(
= E H.
(PaT H I + S P(. 8, a))))(( (ss,)))ds a) H.
(-atm:)) (P.(a))) (xao))
(s, E (8 A)b: (s,a) * (8 A)b-
(1,
(s(sa)
These satisfy key adjoint property, which we leverage to show (%, is saddle point of La (g 1).
Lemma 1. Vig E H. we have (1a, (T - p2) (ga: 4)H
Our first assumption ensures that 1a exists.
Assumption 1. Suppose Idz;; Poloo < 00. Note the infinity norm
lla is over S x A.
Proposition Under Assumption 1, we have |1tilloo oo oc.
Proposition is immediate noting that (I - {( (P = ?(PPa)
and recalling the discounted occupancy measure under T. with initial distribution po is written as dwg, (1 (1 - )(P:)T) T) (mo). Hence, ||(5 S (1 -)- Rmax Rmaxllds; /Po loc. Note that |dd;; | so crucially differs with the standard density-ratio-brn basid concentrability coefficient [|d=; Ho/ /Poloc in offline RL. Unlike ||d=; /s/ /ooloo the value of [|dx;
Ho./ / Polloo can be infinite when the initial distribution No is not covered by offline data P. as the practical motivating example is explained in the footnote in Section I and Example
Our next assumption ensures La 2 0, which also guarantees that 1 2 0.
Assumption 2. Suppose log || mbllo I Rminn
Assumption 2 can be satisfied by rescaling reward (i.e., rescaling Rmin) as long || / is finite. Hence, it is very mild. Putting Lemma together with our assumptions we have the following.
Lemma 2. Suppose Assumptions and 2 hold. Then, (ga, (x) is a saddle point of La Lg l) over q E H. E H, i.e., La 12) Lalga, 15) 2 Lalga, 1) Vq E H, VI E H.
Recall that point (7.1) is saddle point if and only if the strong duality holds, and ğ E arg arg SuPIEM (g. 1), E arg max1eR inf (g, using the general characterization (Bertsekas, 2009). Hence, Lemma 2 ensures 4% E arg mingen maxie La(q.
Next, we consider the constrained optimization problem when we use function classes Q C H, L c H. As long as the saddle point included in (Ω, L), we can prove that g¹, is unique minimaxer.
Lemma Suppose Assumptions I and hold, 4: Q, and 1 E L. Then, we have that g arg min suPiec (g, 1) on the support (S x A)s-
This establishes that realizability (g E Q, 12 E L) is sufficient to identify qtt on the offline data distribution. high level. g arg min supiec La (q. () is established through the invariance of saddle points, i.e., saddle points over original sets remain saddle points over restricted sets. Its uniqueness verified by the strong convexity in q of L. (g. 1) induced by P( (2, a)).
We use the notation because P= is interpreted as the adjoint operator in the non woightett L sssse

---

4.2 Le-convereeece Rate for Soft Q-estimators
Based on the population-level results in Section 4.1, we give a finite-sample error analysis Åa Assumption (Realizability of soft Q-function), Suppose %% E Q and 1l I B2 4q E Q Assumption (Realizability of Lagrange multiplier). Suppose 1a2 and || bc S Be E.
It is natural to set Be = (1 -1 Rmax and Bc = (1 (1-7) (1ax)) Polooolo but letting these be arbitrary offers further flexibility our results.
Theorem (Le=convereence of soft Q-estimators). Suppose Assumptions 3, and hold. Then, with probability 6, the error 1l - 9all2 is upper-bounded by
BB% BoBa(a Im(A4))) 1/2 (In(1@)12//0/mm)44
Our result significant as it relies realizability-typp conditions rather than Bellman closedness. Since the majority of existing works focus on non-regularized Q-functions, we postpone the com- parison to these existing works to the next section. Note when Q and L are infinite, replace 1Ω], [C] with their -covernng numbers following Uehara et al. (2021). Details are given in the appendix.
easily
4.3 L d'-covvergence Rate for Q*-functions
Next, we give analogous finite-sample error analysis of do leveraging the same reasoning. Assumption (Realizability of Q*-functions). Suppose q" E Q and || S Bo Va E Q
Next, we define the Lagrange multiplier:
(P')T : HH 5 /
E H.
While involves the density ratio, this is always well-defined as long as || Ps Polloo oc. Then, it can be similarly established that (q" (*) ( is saddle point of Lo(g. over E H.l E H as we show Lemma We lastly require its realizability.
and l* L. Assumption 6 (Realizability of Lagrange multiplier). Suppose p, Further suppose ~0 < Bg vI E L.
Theorem 2 (L2 convergence of Q-estimators). Suppose Assumptions 5 and 6 hold. Then, with probability - 8, the -eror 1l90 92112 is upper-bounded by
cB + BBBB) 1/2 (n(())(((/))/m)))
To the best of our knowledge, this is the first guarantee on L errors for learning 9" using general function approximation without relying on Bellman completeness. This is highly nontrivial, and we have carefully crafted our algorithm to obtain this guarantee. Existing results often specific to particular models, such as linear models (Shi et al., 2022a), or they require Bellman completeness (Chen and Jiang, 2019; Chen and Qi, 2022), or they are limited to offline policy evaluation scenarios (Huang and Jiang, 2022) (i.e., cases involving linear Bellman operators, but nonlinear Bellman operators). Actually, seems that even under the assumption of Bellman completeness, obtaining an L2 guarantee without strong coverage assumptions remains unclear. A detailed comparison among these different approaches is presented in Section A.
5 Finite Sample Guarantee of MSQP
In this section, we present our primary sample complexity guarantee for MSQP algorithm under the assumptions realizability of g, and i;, and partial coverage. We first show the learned policy #. can compete with n Finally we show 7., can compete with x by selecting properly.
We first introduce the flattened behavior policy =g. which is uniform on the support m. We use technical device to define model-free concentrability coefficient following Xie et al. (2021).
7

---

Definition (Model-free free concentrability coefficient). Define
E Band, g ag (1 a) 8a (s)
Co.d.g.0o = =sup VEQ
1I [(s [Ilg(s, a) - q% (s, a)l
10
( 8) the flattened behavior policy.
where 7g(. s) 11/1fa E A| mo(a 8) > 0}l
(- 8) >
Clearly, c is smaller than density-ration ratio-baseod concentrability coefficient, in other words,
dag.no(8)mT (s) (o(
Co.dra Po
S <max (x,0)
Here, we always have ||0//mol| oo even if To(a 8) is 0 for some (s. a). In the special case where Ta(a s) 2 1/C" for any (s, a). we have CQ.d. I C C'Ildag Pollollso The coefficient Co.d,; a refined concentrability coefficient, which adapts to function class Q. For example, in linear MDPs, it reduces a relative condition number as follows. Similar properties are obtained in related works (Xie et al., 2021; Uehara and Sun, 2021).
Example 1 (Linear MDPs). A linear MDP is one such that, for a known feature vector o: S x A + R. the true density satisfies P(s') 8, 8,a) (u"(''), (s'), Ō(s, a)} for some μ² : S > BR and the reward function satisfies E[[ s.a] = 10r,00(s.. ((s,))))))) for some 0, E Rdd.
In linear MDPs, Lo is clearly linear in d(s, a). Hence, the natural function class is (0, ((,,a) ||0|| & B} for a certain B E RR. Then, we have
x Eawday my ( a)
Co.degin
sup zボ0 x' ( lo(s, a),,
We are now prepared to present our main result, which states that given the realizability of the soft Q-function 9.2 and Lagrange multiplier 1ü it is possible to compete with πa under the coverage condition Co.d < 0o, Idd., PPllooo < cc.
Theorem 3 a can compete with T,)), Fix a > O. Suppose Assumptions 1, 2, 3, and 4 hold. With probability 8, the regret J(x²) -(aa)
) upper-bounded by
[11|c]| 8
1/4PPoly (2, Be, Co.dezino
Rmax
The proof mainly consists of two steps: (1) obtaining -errrrs of previously demonstrated in Theorem 1, (2) translating this error into the error of a.. the second step. the Lipshitz continuity of the softmax function plays crucial role. If there is regularization (a 0) and the greedy policy of % is utilized, the second step does not proceed (without any further additional assumptions).
Our ultimate goal is to compete with n² Theorem 3 serves the primary foundation for this goal. The remaining task is to analyze the approximation error J(x='( JJ J(x2). Fortunately, this term can be controlled through and the density ratio between n7 and mb. Then, by properly controlling a, we can obtain the following sample complexity result.
Theorem 4 (PAC guarantee of #t). Fix any 0. Suppose Assumptions 1, 2, 3, and 4 hold for //8 and ||TT mb Co. Co.drg co. Then, if n is at least
PPoly Al, Be, Be, Ce,dug wo In(1@)[C//6) (1 Inn)),)) -,,,,, Rmax).
with probability at least 8, we can ensure J (TT) J ((ta) S.
In summary, the realiazability of qa 1t, per-step coverage || Tel < oo and partial coverage Co.d....o < oo, ||d=;./r// Polllc < oc are sufficient to compete with n² This is novel and attractive result. Firstly, if we solely use the naïve FQI or Bellman residual minimization, existing PAC results require the global coverage |/da,po/ /Poll < oo for any possible policy (Munos and Szepesvári, 2008; Antos et al., 2008). Our result only requires coverage under single policy = (near-optimal policy). Secondly, we only require the realizability of two functions, and we do not necessitate

---

realizability--yy conditions for all policies in the policy class or Bellman completeness, unlike existing works with partial coverage (Xie al., 2021; Jiang and Huang, 2020).
The most similar result is Zhan et al. (2022). However, our guarantee possesses a certain advantage over their guarantee follows. They demonstrate the realizability of certain functions i Va and partial coverage ||da...p/ /Poll < oo are sufficient conditions in offline RL, where W = di. no PP (To is a certain regularized optimal policy, but fundamentally distinct from TTa) and va is near- optimal regularized value function parameterized by a. Here, we have " = w", % = v². Our guarantee has similar flavor in the sense that it roughly illustrates realizability and partial coverage are sufficient conditions. However, the meanings of realizability and partial coverage are significantly different. In particular, by employing our algorithm. we can ensure PAC guarantees under the boundedness of the refined concentrability coefficient Cg.d. < D0 (and Id /Pll through Bz). As result, the L -norm of the density- ratio-rttooouoi basid concentrability coefficient |d==2.oo Po oo can even be infinite. More specifically, can permit situations where max, Mo (s)) (s(s) oo as we will see the practical example soon. Conversely, Zhan et al. (2022) excludes this possibility since the algorithm explicitly estimates the density ratio 2
Example (Contextual bandit under external validity). We consider the contextual bandit setting where want optimize J(x) = Es-pi Es=-io,-=7()))--- (...__ [r] using offtine data s Pa, a To(s),r~ P(s, a). This is the simplest RL setting with O. Here, note po could be different from Po. This case often happens in practice as discussed in the literature on causal inference related to external validity (Pearl and Bareinboim, 2014; Dahabreh et al., 2019; Uehara al., 2020), which refers to the shift between the target population and the offline data. Here, our PAC guarantee does not require that pu(s) is covered by Po(s) in terms of the density ratio as long the relative condition number is upper-bounded when we use linear models. On the other hand, Zhan et al. (2022) excludes this possibility.
Despite the aforementioned advantage of our approach, unfortunately, our sample complexity of O(1/E5) is slower compared to that of ((1/e)) ) in Zhan et al. (2022). In the following, we demonstrate that MQP, which is a special version of MSQP when a - 0, can achieve a faster rate of O()
6 Finite Sample Guarantee of MQP
In this section, building upon the convergence result of qu. we demonstrate the finite sample guarantee of our MQP algorithm under partial coverage. We first introduce the soft margin.
Assumption (Soft margin). For any a' E A, there exists to E R
, E (0, oo) such that
P Pandar..o .no (0 < 19 (s, n (s)) qn
(s.aa)) a')l < S (t/to)a
for any t O. Here, we use the convention x 0 if0 < x < 1 and x ~0 30 if >
In the extreme case, there exists a gap in q" (also known as a hard margin) so that the best action is always better than the second-best by some lower bounded amount, then the soft margin is satisfied with 3 = co. Thus, the soft margin is more general than the gap condition used in Simchowitz and Jamieson (2019); Wu et al. (2022). Crucially, gap generally does not exist in continuous state spaces unless Q-functions are discontinuous or one action is always option, or gap involves a large to constant in discrete state spaces with bad dependence on the number of states. In contrast, a soft margin with some 3 > 0 generally holds (see, e.g., lemma 4 in Hu et al., 2021). The soft margin widely used in the literature on classification, decision making, and RL (Audibert and Tsybakov, 2007; Perchet and Rigollet, 2013; Luedtke and Chambaz, 2020; Hu et al., 2021, 2022).
Theorem 5 (PAC guarantee of fro). Suppose Assumptions and 7 hold and || /Tollo S Co. Fix
any > 0. Then, if is at least
1 (2 4429 Poly (to') BA, Be, CQ wo In ( (1 (1-77) (1--7)-,,n((O) Rmax)
with probability at least 1- we can ensure J(TT) - J (fto)= S
The proof mainly consists of two steps: (1) obtaining L -erorr of go as demonstrated in Theorem 2, (2) translating this error into the error of ft. In the second step, the soft margin plays erucial role.
These theorems indicate that the realizability of the Q-function qº and Lagrange multiplier 1*, and the soft margin are sufficient for the PAC guarantee under partial coverage CQ.der 00.

---

|| Poloo < 30. Our algorithm is agnostic to 3 and operates under any value of 3. In particular, when there is gap (3 = oc), we can achieve sample complexity of ((1/²²) In comparison to Theorem although we additionally use the soft margin, the realizability in Theorem appealing since it is imposed on the standard Q-function q". The closest guarantee to our work can be found in Chen and Jiang (2022), which demonstrates that the existence of the gap in q", the realizabilitty of q", w" (:= dx- . P. and partial coverage || < oc are sufficient conditions. similar comparison is made Ozdaglar et (2023). comparison to their work, we use the soft margin, which is significantly less stringent.
more
7 Conclusions
We propose two value-basse based algorithms, MSQP and MQP, that operate under realizability of certain functions and partial coverage (i.e., lingle-poliyy-covrrase
Notably, our guarantee does not require the policy class. While guarantees with Bellman completeness and uniform-type realizability similar flavors are obtained in Zhan et al. (2022); Chen and Jiang (2022). MSQP can potentially relax the density-ratio-basee
partial coverage regarding the initial distribution opposed to Zhan al. (2022), and MQP can operate under the soft-margin, which is less stringent than the hard margin imposed in Chen and Jiang (2022). Moreover, both algorithms work Q-functions, which are more commonly used in practice.
Acknowledgements
This material is based upon work supported by the National Science Foundation under Grant Nos. IIS 1846210, CCF 2002272, IIS 2107304, CIF 2212262,, IIS 2144994, IIS 2154711.
JDL acknowledges support of the ARO under MURI Award W91 INN-I1----000 the Sloan Research Fellowship, ONR Young Investigator Award, and NSF CAREER Award 2144994.
References
András Antos, Csaba Szepesvári, and Rémi Munos. Learning near- mear-optimal policies with bellman- residual minimization based fitted policy iteration and single sample path. Machine Learning, 71 (1):89-129, 2008
Yves Audibert and Alexandre B Tsybakov. Fast learning rates for plug-in classifiers. The Annals of statistics, 35(2):608-6)) 633, 2007.
Chenjia Bai, Lingxiao Wang, Zhuoran Yang, Zhihong Deng, Animesh Garg, Peng Liu, and Zhaoran Wang. Pessimistic bootstrapping for uncertainty-driver offline reinforcement learning. arXiv preprint arXiv:2202.11566. 2022.
Dimitri Bertsekas. Convex optimization theory, volume 1. Athena Scientific, 2009.
Jonathan Chang, Masatoshi Uehara, Dhruv Sreenivas, Rahul Kidambi, and Wen Sun. Mitigating covariate shift imitation learning via offline data with partial coverage. Advances in Neural Information Processing Systems, 34:965-979, 2021.
Jinglin Chen and Nan Jiang. Information--heeorti considerations batch reinforcement learning. In International Conference Machine Learning, pages 1042-1051. PMLR, 2019.
Jinglin Chen and Nan Jiang. Offline reinforcement learning under value and density-ratio realizability: the power of gaps. arXiv preprint arXiv:2203.13933 2022.
Xiaohong Chen and Zhengling Qi. On well-posedness and minimax optimal rates of nonparametric q-function estimation in off off-po evaluation. arXiv preprint arX1v:2001.06169, 2022.
Stephen R Cole and Elizabeth A Stuart. Generalizing evidence from randomized clinical trials to
target populations: the actg 320 trial. American journal of epidemiology, 172(1):107-111, 2010.
"Similar to the findings in Wang et al. (2022), in general offline RL, we may potentially achieve result of ((1/)). We leave room for further enhancements in future research.
10

---

Issa J Dahabreh, Sarah E Robertson, Eric J Tchetgen, Elizabeth A Stuart, and Miguel A Hernán. Generalizing causal inferences from individuals in randomized trials to all trial-eligible individuals. Biometrics, 75(2):685 694, 2019.
Rasool Fakoor, Jonas W Mueller, Kavosh Asadi, Pratik Chaudhari, and Alexander J Smola. Continu- ous doubly constrained batch reinforcement learning. Advances in Neural Information Processing Systems, 34:1 2221111012222 1273, 2021.
Roy Fox, Ari Pakman, and Naftali Tishby. Taming the noise in reinforcement learning via soft updates, arXiv preprint 151..08522. 2015.
Bolin Gao and Lacra Pavel. On the properties of the softmax function with application in game theory and reinforcement learning. arXiv preprint arXiv:1704.00800 00805, 2017.
Matthieu Geist, Bruno Scherrer, and Olivier Pietquin. A theory of regularized markov decision processes. In International Conference on Machine Learning, pages 2160-2169. PMLR, 2019.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International conference on machine learning, pages 1861-1870. PMLR, 2018.
Yichun Hu, Nathan Kallus, and Masatoshi Uehara. Fast rates for the regret of offline reinforcement learning, arXiv preprint arXiv:2102.00479, 2021.
Yichun Hu, Nathan Kallus, and Xiaojie Mao. Fast rates for contextual linear optimization. Manage- ment Science, 68(6):4236442455 2022.
Audrey Huang and Nan Jiang. Beyond the return: Off- function estimation under user-specified error- mror-measuring distributions. In Neurips, 2022.
Nan Jiang and Jiawei Huang. Minimax value interval for off-policy evaluation and policy optimization. Advances in Neural Information Processing Systems, 33:2747-2753 2020.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline ri? arXiv preprint urXiv:2012.15083 2020.
Rahul Kidambi, Aravind Rajeswaran, Praneeth Netrapalli, and Thorsten Joachims. Morel: Model- based offline reinforcement learning. In Advances in Neural Information Processing Systems, volume 33, pages 21810-21823. Curran Associates, Inc., 2020.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives open problems. arXiv preprint wwXiv:2005.01643 2020.
Gene Li, Cong Ma, and Nathan Srebro. Pessimism for offline linear contextual bandits using Ip confidence sets. arXiv preprint arXiv:2205. 10671, 2022.
Alex Luedtke and Antoine Chambaz. Performance guarantees for policy learning. In Annales de I'IHP Probabilites statistiques, volume 56, page 2162. NIH Public Access, 2020.
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 95). 2008.
Ofir Nachum and Bo Dai. Reinforcement learning via frnchel-rockafellaa duality. arXiv preprint arXiv:2001.0186., 2020.
Gergely Neu, Anders Jonsson, and Vicenç Gómez. A unified view of retropy-re markov decision processes. arXiv preprint arXiv:1705.07799 2017.
Thanh Nguyen- Tang, Ming Yin, Sunil Gupta, Svetha Venkatesh, and Raman Arora. On instance- dependent bounds for offline reinforcement learning with linear function approximation. arXiv preprint arXiv:2211.1322 2022.
Asuman E Ozdaglar, Sarath Pattathil, Jiawei Zhang, and Kaiqing Zhang. Revisiting the linear- programming framework for offline with general function approximation. International Conference Machine Learning, pages 26769-2679) PMLR, 2023.

---

Judea Pearl and Elias Bareinboim. External validity: From do-calculus to transportability across populations. In Statistical Science, pages 451-482. 2014.
Vianney Perchet and Philippe Rigollet. The multi-armed bandit problem with covariates. The Anmals of Statistics, 1121) 2013.
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline rein- forcement learning and imitation learning: A tale of pessimism. arXiv preprint 211v:2103..2021,, 2021.
Paria Rashidinejad, Hanlin Zhu, Kunhe Yang. Stuart Russell, and Jiantao Jiao. Optimal conser- vative offline with general function approximation via augmented lagrangian. arXiv preprint arXiv:2211.000 2022.
John Schulman, Xi Chen, and Pieter Abbeel. Equivalence between policy gradients and soft q-leaniing arXiv preprint (eXXi:/704.0644000 2017.
Chengehun Shi, Sheng Zhang, Wenbin Lu, and Rui Song. Statistical inference of the value function for reinforcement learning in horizon settings. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(3):665-79, 2022a.
Laixi Shi, Gen Li, Yuting Wei, Yuxin Chen, and Yuejie Chi. Pessimistic q-learning for offline reinforcement learning: Towards optimal sample complexity. arXiv preprint 17X. 2022b.
Max Simchowitz and Kevin G Jamieson. Non-asymptotic gap-dependent regret bounds for tabular mdps. Advances in Neural Information Processing Systems, 32, 2019.
Masatoshi Uchara and Wen Sun. Pessimistic model-based offline reinforcement learning under partial coverage. ICLR 2022, 2021.
Masatoshi Uchara, Masahiro Kato, and Shota Yasui. Off-policy evaluation and learning for external validity under covariate shift. Advances in Neural Information Processing Systems, 33:49-61 61, 2020.
Masatoshi Uehara, Masaaki Imaizumi, Nan Jiang, Nathan Kallus, Wen Sun, and Tengyang Xie. Finite sample analysis of minimax offline reinforcement learning: Completeness, fast rates and first-order efficiency. arXiv preprint arXiv:2102.02981 2021.
Xinqi Wang, Qiwen Cui, and Simon S Du. On gap-dependent bounds for offline reinforcement learning. Advances in Neural Information Processing Systems, 35: 15:14565-14877, 2022.
Jingfeng Wu, Vladimir Braverman, and Lin Yang. Gap-dependent unsupervised exploration for reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 4131-4131. PMLR, 2022.
Yifan Wu, George Tucker, and Ofir Nachum. Behavior regularized offline reinforcement learning. arXiv preprint arXiv: 1911:1911.1130 2019.
Tengyang Xie and Nan Jiang. Q approximation schemes for batch reinforcement learning: A theoretical comparison. In Conference Uncertainty in Artificial Intelligence, pages 550-559, PMLR, 2020.
Tengyang Xie, Ching-An An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consistemn pessimism for offline reinforcement learning. Advances in neural information processing systems, 34:6683-6694, 2021.
Mengjiao Yang. Ofir Nachum, Bo Dai, Lihong Li, and Dale Schuurmans. Off- evaluation via the regularized lagrangian. Advances in Neural Information Processing Systems, 33:6551-65611 2020.
Ming Yin and Yu-Xiang Wang. Towards instance-optimal offline reinforcement learning with pessimism. Advances in neural information processing systems, 34:4065-4078, 2021.
12

---

Tianhe Yu, Garrett Thomas, Lantao Yu, Stefano Ermon, James Y Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma. Mopo: Model-based offline policy optimization. In Advances in Neural Information Processing Systems, volume 33, pages 14129-14142, 2020.
Andrea Zanette and Martin J Wainwright, Bellman residual orthogonalization for offline reinforce- ment learning. arXiv preprint vrXiv22003.12786 2022.
Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason Lee. Offline reinforcement learning with realizability and single-policy concentrability. In Conference Learning Theory, pages 2730-2775. PMLR, 2022.
Xuezhou Zhang, Yiding Chen, Xiaojin Zhu, and Wen Sun. Corruption-rouus offline reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 5757-5773. PMLR, 2022.
Hanlin Zhu, Paria Rashidinejad, and Jiantao Jiao. Importance weighted actor-critic for optimal conservative offline reinforcement learning. arXiv preprint arXiv:2301. 12714, 2023.
Brian Ziebart, Andrew L Maas, J Andrew Bagnell, Anind K Dey, et al. Maximum entropy inverse reinforcement learning. In Aaai, volume 8, pages 1433-1438. Chicago, IL. USA. 2008.
Brian D Ziebart, J Andrew Bagnell, and Anind K Dey. Modeling interaction via the principle of maximum causal entropy. In ICML, 2010.
13


Reviews:
[{"review_id": "OrfVrCkDx8", "reviewer": "Reviewer_oZk7", "summary": "This paper studies offline reinforcement learning and proposes a soft Q-learning algorithm based on reformulating the solution to the Bellman equation as a saddle point of a certain minimax optimization problem. The authors then provide PAC guarantees for estimating the entropy-regularized Q-function, which in turn gives the sample complexity bounds. A key feature of this work is that it requires weaker assumptions (only partial coverage assumption is required) compared with existing literature.", "questions": "See the weakness section.", "limitations": "No negative societal impact.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Theoretical analysis of Q-learning with function approximation is one of the key topics in reinforcement learning (RL). This paper provides a sample complexity bound of soft Q-learning under only a partial coverage assumption, which might be of interest to the broad community of RL.", "weaknesses": "I have two major concerns about this work.\n\n(1) I am confused about the reformulation of solving the Bellman equation as a minimax optimization problem. It is well-known that both the vanilla Bellman operator and the entropy regularized Bellman operator are contraction mappings, which imply the uniqueness of both $q^*$ and $q_\\alpha^*$. In that case, it is unclear what Eq. (2) means since there is really no optimization problem here. Am I missing anything?\n\n(2) I read the proof of Theorem 5 and have some questions. In the second inequality in line 637, the event $q^*(s,a')-q^*(s,\\pi^*(s))\\leq 0$ happens surely because the optimal policy is greedy with respect to the optimal Q-function. In that case, why do we need to add this event to the indicator? In addition, since $q^*(s,a')-q^*(s,\\pi^*(s))\\leq 0$ happens surely, the first term on the right-hand side of the first inequality in line 638 is exactly equal to $1$. As a result, the bound seems to be meaningless and Assumption 7 is redundant. What am I missing here?\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our draft! \n\n**Q.**  I am confused about the reformulation of solving the Bellman equation as a minimax optimization problem...\n\n**A.** As you rightly pointed out, the solution to the Bellman equation (3) is unique, giving the soft Q-functions $q^*_\\alpha$, and therefore the feasible set of the optimization problem (2) is a singleton, but the Lagrangification of this optimization problem in equation (4) which is yet another reformulation of $q^*_\\alpha$ is instructive for developing our algorithm. When dealing with finite samples, however, a challenge is to construct a loss function to target learning the soft Q-functions directly, since the soft Bellman equation (3) is not known exactly and the state-action space is infinite. Therefore, the point of the optimization problem in equations (2) and (4) is to give an equivalent formulation of $q^*_\\alpha$ that then inspires our estimation algorithm: take our equation (4) and replace expectations with sample averages and restrict functions $q$ and $l$ to some function classes, as noted in Lines 151-152. The reformulation in equation (2) is trivial and works for any choice of objective function since the feasible set is the singleton $\\{q^*_\\alpha\\}$, but the reformulation in equation (4) is useful because the optimization is now unrestricted and the resulting algorithm (once we replace expectations with sample averages and restrict to function classes) does very heavily depend on the choice of objective in equation (2) and that choice is key to making our results work (we could likely employ any strongly convex function, but the square is easiest to deal with; we utilize the strong convexity in Sec 4 to establish statistical convergence as we mention in Line 212). We will make this intent clearer up front in Line 146 when first introducing the optimization, rather than explaining it only after.\n\nIn summary, the optimization problem in equation (2), albeit trivial as an optimization over a singleton, serves as motivation for how our construction of the loss function in equation (5) of our Algorithm 1, which of course can only use finite samples (offline data) rather than population distributions. We will clarify the point of equation (2) up front upon revising. If you have any follow up questions regarding our explanation, we would be delighted to discuss and clarify further. \n\n\n\n**Q.** I read the proof of Theorem 5 and have some questions...\n\n\n**A.**  Thank you for the question and thank you for reviewing our proofs. There is indeed a small typo in the proof, but the proof is otherwise correct and the result does hold and Assumption 7 does play a crucial role. The issue is that optimal actions should have been excluded in the sum in the last inequality in line 637. That is, in all the sums over $a'$ in this proof, we should only sum over $a'$ that are sub-optimal at $s$.\n\nNamely, the event you mention $q^*(s,a')-q^*(s,\\pi^*(s))\\leq 0$ should have in fact been $q^*(s,a')-q^*(s,\\pi^*(s))< 0$, meaning in words the event that $a'$ is a suboptimal action at state $s$. Indeed, the final bound in line 637 should very simply read, in words, the indicator that $\\pi^*$ and $\\hat\\pi$ disagree (at $s$) is bounded by the number of actions that appear optimal under $\\hat q$ but are in fact suboptimal under $q^*$ (at $s$).\n\nThe argument then proceeds in line 638 by splitting the range of $\\hat q(s,a')-\\hat q(s,\\pi^*(s)$ in this indicator from $(-\\infty,0)$ into the mutually exclusive $(-\\infty,-t)$ and $[-t,0)$ and then, after obtaining two indicators, getting a bound by omitting certain restrictions in the first indicator and others restrictions in the second, resulting in the two terms on the right-hand side of line 638. \n\nThe term you mention (the first term on the right-hand side of the first inequality in line 638) should in fact have had a $0>$ in front of $q^*$ so that the indicator there reads $I(0>q^*(s,a')-q^*(s,\\pi^*(s))\\geq -t)$ (currently, the \"$0>$\" in front is missing). Note that the event $0>q^*(s,a')-q^*(s,\\pi^*(s))\\geq -t$ can be read as, $a'$ is suboptimal and $q^*(s,a')-q^*(s,\\pi^*(s))\\geq -t$ holds. That is, another way to fix the term you mention (the first term on the right-hand side of the first inequality in line 638) is to restrict the sum to actions $a'$ that are sub-optimal at $s$. Since $t>0$ and $a'$ is suboptimal, the latter is non-trivial and does _not_ hold surely. In particular, for $t=0$ the event is surely false and as $t\\to0$ the probability goes to 0 by continuity of probability. We bound the (non-trivial) probability of this event in line 639 using Assumption 7, which plays a very crucial role. We then choose $t$ to balance the two terms in line 641 to obtain the final bound.\n\nLuckily, the proof is otherwise correctly written as though the the missing \"$0>$\" were in fact there in line 639. So everything is correct except for the fact that we are missing this \"$0>$\", which we will of course add so the sums over $a'$ are restricted to suboptimal actions. We will further add some in-words explanations for the each line in the derivation along the lines of the above explanation. Thanks again for helping us locate this typo."}, {"review_id": "masPxXAyCb", "reviewer": "Reviewer_4xjy", "summary": "This submission studies offline RL with function approximation. Under the relatively mild assumption of partial coverage and realizability of the function approximations, the paper proposes the algorithm M(S)QP that approximates the (soft-)Q-function by solving a minimax optimization problem, and establishes guarantees of $L^2$-convergence of the Q-function estimator and the sub-optimality gap of the learned policy. ", "questions": "(1) In Remark 1, the authors remark that the minimax optimization is computationally feasible when $\\mathcal{L}$ is chosen to be RKHS or linear function classes. I would like to know if there is a concrete class of offline RL problems where such a choice of $\\mathcal{L}$ satisfies realizability, or otherwise this remark is vacuous.\n\n(2) The bounds presented in this paper seem to be far from optimal (e.g. $O(n^{-1/4})$ convergence or $O(\\epsilon^{-8})$ rate), and they are also worse than the results in previous works (e.g. the case $\\alpha=0$ requires an extra assumption). I wonder if this is an artifact of the analysis or a price of milder assumptions.\n\n(3) Line 303: \"In the following, we demonstrate that MQP, which is a special version of MSQP when $\\alpha \\rightarrow 0$, can achieve a faster rate of $O\\left(1 / \\epsilon^2\\right)$.\"\n\nIn my opinion, this remark is slightly misleading, because the faster $O\\left(1 / \\epsilon^2\\right)$ rate is achieved under a stronger assumption of \"soft margin\". For example, in tabular offline RL with gap $\\Delta>0$ and single policy concentrability $C^*$, the minimax optimal sample complexity is of order $\\frac{SC^*}{\\Delta\\epsilon}$ (Wang et al., ignoring the horizon factor), which is better than the gap-independent sample complexity $\\frac{SC^*}{\\epsilon^2}$ as $\\epsilon\\to 0$. \n\nXinqi Wang, Qiwen Cui, and Simon S. Du. \"On Gap-dependent Bounds for Offline Reinforcement Learning.\"\n\n(4) Writing:\n\n(a) The notation $\\left\\|d\\_{\\pi\\_\\alpha^{\\star}, P\\_b} / P\\_b\\right\\|\\_{\\infty}$ is ambiguous, because the measure $d\\_{\\pi\\_\\alpha^{\\star}, P\\_b}$ is defined on both the space $\\mathcal{S}$ and the space $\\mathcal{S}\\times\\mathcal{A}$, and so does the measure $P\\_b$.\n\n(b) Line 187 & 188 (typos): $d\\_{\\pi\\_{\\alpha^*, P\\_b}}$ -> $d\\_{\\pi\\_\\alpha^*, P\\_b} $\n", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "A novelty of this work is that it studies offline RL based on soft-Q-function, while previous works mostly focus on the standard Q-function or the LP formulation. There are also several technical improvements compared to prior works, including $L^2$-convergence of the estimators and slightly milder technical assumptions.", "weaknesses": "(1) The proposed schemes are based on minimax optimization and hence are mainly of theoretical interest, and the dual function $l$ is hard to interpret. \n\n(2) The bounds on PAC sample complexity are either worse than the results in related literatures, or require an extra margin condition.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**(1) In Remark 1, the authors remark that the minimax optimization is computationally feasible when $L$ is chosen to be RKHS or linear function classes. I would like to know if there is a concrete class of offline RL problems where such a choice of $L$ satisfies realizability, or otherwise this remark is vacuous.**\n\nA. Thank you for the question. The purpose of Remark 1, as we will certainly make more explicit in the text, is to emphasize the practicality of our algorithm, rather than to suggest any theoretical result. Notably, this choice for $\\mathcal L$ allows us to employ standard empirical risk minimization techniques without needing solve a minimax problem. Since the implementability of our algorithm may be of interest to the reader we do not think the remark is vacuous, but its non-theoretical purpose should be clarified. Please let us know if you agree.\n\nWhile we do not believe it is relevant to Remark 1 as explained above, we do believe we also understand your question and can offer a response to it. As we understand, you are inquiring whether the realizability condition for $\\mathcal L$ (our Assumption 4 or 6, for the case of soft-$Q$ or $Q^*$, respectively) can be shown to be satisfied for certain choices of $\\mathcal L$ (e.g., linear functions) when the MDP is assumed to belong to a certain MDP model classes that have been recently studied in RL theory, such as linear MDPs. This is an open question, which we will state and suggest that it deserves future attention. Nonetheless, the perspective we take is that, as compared to RL theory work that starts with such model assumptions, our work is line with literature looking at model-free RL based on function approximation, where abstract function realizability are themselves the primitive assumptions about the MDP instance, rather than a model assumption. For the very particular case of realizability of weight functions, this is line with the works of Jiang and Huang (2020) and Zhan et al. (2022) which similarly require such weight-function realizability (see Table 1).\n\n**(2) $O(1/\\epsilon^8)$ I wonder if this is an artifact of the analysis or a price of milder assumptions.**\n \nA.  This is a very interesting point. We are of the opinion that this could be attributed to the price of milder assumptions as we strive to attain the refined rate. However, we have no lower bound to establish this formally at the moment. We will note this interesting question and the possible avenue for future work on lower bounds.\n\n**(3) $\\alpha \\to 0$, the standard fast rate would be $O(1/\\epsilon)$**\n\nA. Thank you for your valuable insight. We concur with your observation. To address this, we will include a remark and reference mentioning the standard fast rates with the gap being $O(1/\\epsilon)$.\n\nRegarding the two latter points, we will add discussion regarding the rates and highlight that their optimality is in question, our primary focus on getting _some_ polynomial convergence under very mild assumptions, and that related work with similarly mild assumptions also has unappealing rates (e.g., Zhan et al., 2022, who like us focus on _some_ convergence).\n\n**Notation $|d_{\\pi^\\ast_\\alpha,P_b}/P_b|_{\\infty}$ is ambiguous**\n\nThank you for bringing this to our attention. We concur with your observation, and we will introduce subscripts $\\mathcal S$ and $\\mathcal S\\times\\mathcal A$ to disambiguate."}, {"review_id": "NRGPRZLaKT", "reviewer": "Reviewer_6n4K", "summary": "This paper proposed value-based algorithms for offline RL without Bellman completeness and full coverage of data support. By proposing the optimization objective of selecting the soft-Q from the set, where element in set satisfies the empirical soft-Bellman operator and the selected Q should minimize the square value under the expectation of behavior data distribution, and transforming it into a minimax problem, MSQP and MSQ could provide the property of convergence and sample complexity guarantee only with partial coverage and realizability.", "questions": "1. Could the author explain more about the intuitions of the proposed learning objective in Equation 2, though the convergence and sample complexity guarantee is provided?", "limitations": "It could be better if empirical results beyond tabular are provided.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. This paper propose novel offline algorithms without the assumption of full coverage and Bellman completeness.\n2. The proposed algorithms are in a value-based manner, and avoid the assumption of initial distribution of ground truth MDP.\n3. The proposed algorithms could have the property of convergence and sample complexity guarantee under more related assumptions.\n4. This paper is well written and easy to follow.", "weaknesses": "1. There lack some intuitions for the proposed learning objective in Equation 2. and Equation 3., since the square value of Q is not an explicit constraint for offline learning problem. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Could the author explain more about the intuitions of the proposed learning objective in Equation 2, though the convergence and sample complexity guarantee is provided?**\n\nThis is an excellent point. We will certainly provide a more detailed explanation in the revised draft. Let us offer an intuitive explanation. There are two primary reasons why in equation (2) we use the objective $\\mathbb E[q^2(s,a)]$: it is strictly monotonic and it is strongly convex. Here is why these properties are important:\n\n* This choice of a strictly monotonic objective makes it so that the optimization problem in equation (2), with the feasible set in equation (3), is equivalent to a relaxed optimization problem in equation (10) in Appendix B where the equality constraints are replaced by inequalities, as we prove in Lemma 5 of Appendix B. Here any objective that is strictly monotonic in $q$ would have worked (i.e., $q\\leq q'$ and $q\\neq q'$ (mod $P_b$) implies that $q$ has a smaller objective than $q'$). \n\n  * The result is important because the constraints in equation (3) are not convex as they involve an equality of a max over optimization variables (note the lack of convexity is regarding each constraint for each $s,a$; the feasible set in equation (3) is a singleton which is trivially convex). When we relax this to an inequality, the constraints becomes convex and easy to deal with analytically.\n\n* Once we have these convex constraints, using the objective $\\mathbb E[q^2(s,a)]$ gives a convex optimization problem. Crucially, the objective we use is _strongly_ convex which helps ensure that we obtain a _unique_ saddle point when considering the Lagrangian version of the problem. Here any strongly convex objective would have worked.\n\n  * Although this point is briefly mentioned in Line 208, we acknowledge that the paper would benefit from a clearer motivation upfront when first introducing equation (2), mentioning both strict monotonicity and strong convexity. We will add this."}, {"review_id": "qB7uS4d0z4", "reviewer": "Reviewer_3Bh2", "summary": "This paper proposes a q-learning based algorithm for solving offline minimax problem in reinforcement learning. Under certain partial coverage and realizability assumption for the regularized problem, they prove $O(1/\\epsilon^4)$ sample complexity.", "questions": "None", "limitations": "None", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This is the first paper for minimax problem in offline RL that only requires realizability assumption and partial data coverage (without completeness and all-policy concentrability).", "weaknesses": "Weakness and comments:\n1. The partial data coverage and realizability assumptions are made for the regularized problem instead of the original problem. It is unclear what the relationship  between these assumptions with the standard partial coverage and realizability assumptions for the original problem as in ``Revisiting the linear-programming framework for offline rl with general function approximation''.\n2. The technique seems to  be similar to paper ``Refined value-based offline rl under realizability and partial coverage\n''. The authors should explain more about the novelty.\n3. References missing: ``Revisiting the linear-programming framework for offline rl with general function approximation'' also proposes an algorithm which requires $1/\\epsilon^2$ sample complexity without completeness assumption for offline RL.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comparison with ``Revisiting the linear-programming framework for offline rl with general function approximation'' by Ozdaglar et al.**\n\nThank you for bringing this paper to our attention. We will certainly cite and discuss it. Here is the comparison, which we will incorporate into the main text. The primary difference lies in our focus on assuming _only_ mild single-policy realizability assumptions, and in particular avoiding Bellman completeness assumptions (e.g., $\\mathcal B^\\pi \\mathcal Q\\subset \\mathcal Q~\\forall \\pi\\in\\Pi$ as in the second line of Table 1). There are two cases considered in Ozdaglar et al. Their Case I (their Sec 3) involves completeness, therefore involving fundamentally different primitive assumptions. Their Case II (their Sec 4) avoids completeness but leverages a gap (hard margin), like Chen and Jiang (2022; see 5th line in our Table 1). In comparison, we avoid completeness and/or uniform-over-policy assumptions in the regularized soft-Q setting, and in a more similar setting where we similarly focus on the _non-regularized_ problem, using our MQP algorithm we only need to use a soft margin condition, which we argue is much more likely to hold than a gau / hard margin, especially in settings with continuous state spaces where a hard margin must imply discontinuous jumps to avoid zero. Aside from these differences, there are of course important similarities in that we both focus on single-policy concentrability. Our results offer the further opportunity to leverage a _refined_ concentrability coefficient that adapts to the $\\mathcal Q$ class (see Definition 1 and discussion thereafter). We will add all of this discussion and the citation to Ozdaglar et al. to the paper."}, {"review_id": "iBV34oGe1u", "reviewer": "Reviewer_CJ1Z", "summary": "This paper presents algorithms based on soft Q-learning for offline RL with finite-sample guarantees. The guarantees are given for general function approximation hold under weaker requirements such as a (partially) weaker variant of single-policy concentrability and avoids the Bellman-completeness assumption. ", "questions": "Please refer to the questions in the above segment.", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The paper proposes algorithms based on soft Q-learning that only requires single-policy concentrability and realizability, without Bellman completeness. While a couple of recent papers such as Zhan et al. 2022 have also accomplished this, the guarantees presented in this work hold under a weaker single-policy coverage requirement and the MQP algorithm avoids the realizability of regularized optimal solutions, unlike the PRO-RL algorithm of Zhan et al. 2022.\n- The proposed algorithms appear to be implementable compared to prior works such as Chen and Jiang. ", "weaknesses": "- The dual variables $l(s,a)$ here seems to be closely connected to importance weights $w(s,a)$. The Bellman consistency term in (4) seems to be similar to the importance weighted regularization considered in Zhu et al. 2023, in which there is a max_w. The main difference is using $\\Omega$ here. In that paper, the variable $w(s,a)$ are importance weights, which ensure that the average Bellman error is small under relevant distributions (including the data and optimal distributions). Would you please provide a comparison between the two objectives and comment on the connections between the variable $l(s,a)$ in your paper vs. $w(s,a)$ in their paper? Does the function $\\Omega$ contribute to avoiding the Bellman completeness assumption? What is the key factor in your proposed objective or analysis that removes the need for Bellman completeness compared to Zhu et al?\n- Convergence rates are slower than 1/sqrt{N} (or involve the gap), which are achieved by some of the recent works such as Zhu et al. 2023.\n\n\n**References**\n\nZhu, Hanlin, et al. \"Importance Weighted Actor-Critic for Optimal Conservative Offline Reinforcement Learning.\" arXiv preprint arXiv:2301.12714 (2023)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Would you please provide a comparison between the two objectives and comment on the connections between the variable  in your paper vs. in their paper (Zhu et al)? Does the function $\\Omega$ contribute to avoiding the Bellman completeness assumption? What is the key factor in your proposed objective or analysis that removes the need for Bellman completeness compared to Zhu et al?**\n \nWe appreciate your insightful suggestion. Here, we summarize the comparison, which we will incorporate into a revised draft along with a citation to Zhu et al. \n \n* It appears that Zhu et al. share a similar flavor with Jiang and Huang (2020), to which we compare in Table 1. If we understand correctly, Zhu et al. can be regarded as a computationally efficient version of Jiang and Huang (2020). Essentially, both works, Jiang and Huang (2020) and Zhu et al., require the realizability of Q-functions for all policies; a primary objective in our paper is to avoid such policy-uniform assumptions and have only single-policy assumptions. While, similarly to us, they do not need Bellman completeness. These policy optimization results are built upon the off-policy evaluation (OPE) findings, such as Uehara et al. (2020), which demonstrate that we only need realizability of the weight $w_{\\pi}$ and $q_{\\pi}$ to estimate the value of a policy $\\pi$. Our approach is entirely different in the sense that we directly tackle the policy optimization problem by estimating soft Q-functions or optimal Q-functions without performing policy evaluation as an intermediate step. This stems from our goal of constructing methods that do not demand realizability for any policies $\\pi$.\n\n* As a result, the function $w_{\\pi}(s,a)$ in Jiang and Huang (2020) and Zhu et al. is very different from our $l_*(s,a)$ (and $l^*_{\\alpha}(s,a)$). Using our notation, we can write $w_{\\pi}(s,a) = d_{\\pi,\\mu_0}(s,a) / P_b(s,a)$ where $d_{\\pi,\\mu_0}$, that is, the discounted occupancy distribution induced by a policy $\\pi$ when the initial distribution is $\\mu_0 \\times \\pi$. On the other hand, $l_*$ is equal to $d_{\\pi^*,P_b}(s,a) / P_b(s,a)$ where $P_b$ in $d_{\\pi^*,P_b}(s,a)$ is the initial distribution. Here, the crucial difference is the initial distributions. \n\n* The reason we do not need Bellman completeness is because we leverage the characterization of saddle points in the convex optimization problem in equation (4) as we explain in Section 4. When our goal is to estimate the value of a policy $\\pi$ (offline policy evaluation), we can similarly take an approach and ensure the statistical guarantee under realizability of $q_{\\pi}$ and $w_{\\pi}$ by considering the following optimization problem: \n$$ \\min_q E_{(s,a)\\sim \\mu_0\\times \\pi}[q(s,a)] $$ \nsuch that\n$$  E[\\gamma q(s',\\pi)+r-q(s,a)|s,a]=0.$$\nThen, the saddle point of the Lagrangian version of the above optimization problem is $(q_{\\pi},w_{\\pi})$ (Q-functions and weights functions for a policy $\\pi$). This implies that we can estimate the value of a policy $\\pi$ under realizability of $(q_{\\pi},w_{\\pi})$ without Bellman completeness. Indeed, this leads to the proposal in Jiang and Huang (2020). However, to achieve our goal (removing realizability for any policy $\\pi$), we need to devise a different optimization problem as in our equations (2)-(4). Furthermore, even from a technical point of view, compared to the above optimization problem and the one in Zhan et al. (2022), our formulation is interesting since the above formulation is a linear convex optimization problem; while, our formulation is nonlinear nonconvex and equivalent to a nonlinear _convex_ optimization problem obtained from relaxing the equality constraints in equation (3) to inequalities (see Lemma 5 in Appendix B). \n\n\nUehara, Masatoshi, Jiawei Huang, and Nan Jiang. \"Minimax weight and q-function learning for off-policy evaluation.\" International Conference on Machine Learning. PMLR, 2020.\n"}]

Author rebuttal:

Meta-review: The paper considers finding good policy without employing pessimism and by using a certain single-policy realizability notion.

The reviewers had several question regarding the appendix, the intuition behind the work as well as a comparison with existing works.
Nonetheless, the paper makes an import contribution in the theory of RL with single policy realizability and concentrability.
Decision: Accept (poster)