Importance Weighted Actor-Critic for Optimal Conservative Offline Reinforcement Learning
Authors: Hanlin Zhu
Paria Rashidinejad
Jiantao Jiao
Venue: NeurIPS 2023 poster (2023)
Keywords: offline RL
actor-critic
l_2 single-policy concentrability
average bellman error
TL;DR: We propose a statistically optimal offline RL algorithm based on marginalized importance sampling  and actor-critc method, which is computationally efficient and requires minimal dataset coverage assumptions.

Abstract: We propose A-Crab (Actor-Critic Regularized by Average Bellman error), a new practical algorithm for offline reinforcement learning (RL) in complex environments with insufficient data coverage. Our algorithm combines the marginalized importance sampling framework with the actor-critic paradigm, where the critic returns evaluations of the actor (policy) that are pessimistic relative to the offline data and have a small average (importance-weighted) Bellman error. Compared to existing methods, our algorithm simultaneously offers a number of advantages:
(1) It achieves the optimal statistical rate of $1/\sqrt{N}$---where $N$ is the size of offline dataset---in converging to the best policy covered in the offline dataset, even when combined with general function approximators.
(2) It relies on a weaker \textit{average} notion of policy coverage (compared to the $\ell_\infty$ single-policy concentrability) that exploits the structure of policy visitations.
(3) It outperforms the data-collection behavior policy over a wide range of specific hyperparameters.
 We provide both theoretical analysis and experimental results to validate the effectiveness of our proposed algorithm. The code is available at https://github.com/zhuhl98/ACrab.

Importance Weighted Actor-Critic for Optimal Conservative Offline Reinforcement Learning
Hanlin Zhu EECS, UC Berkeley
Paria Rashidinejad EECS, UC Berkeley
hanlinzhuuberkeleyy edu
parile.raahhddnaaaa@eeeeee...... edu
Jiantao Jiao
EECS and Statistics, UC Berkeley j jianta@berreeeey.o edu edu
Abstract
We propose A-Crab (Actor-Critic Regularized by Average Bellman error), a new practical algorithm for offline reinforcement learning (RL) in complex environ- ments with insufficient data coverage. Our algorithm combines the marginalized importance sampling framework with the actor- actor-critic paradigm, where the critic returns evaluations of the actor (policy) that are pessimistic relative to the offline data and have small average (importance- (importanc--wiihhee)) weighted) Bellman error. Compared
to existing methods, our algorithm simultaneously offers a number of advantages: (1) It achieves the optimal statistical rate of 1/VN-W// where N is the size offline dataset-in converging the best policy covered in the offline dataset, even when combined with general function approximators. (2) It relies on a weaker average notion of policy coverage (compared to the for single-policy concentrability) that exploits the structure of policy visitations. (3) It outper- forms the data-collection behavior policy parameters. We provide both theoretical analysis and experimental results to validate the effectiveness of our proposed algorithm. The code is available petpp://github. ceithuu.com/zhuhiiii. wwt.cc//wm///CCtt...
wide range of specific hyper-
1 Introduction
Offline reinforcement learning (RL) algorithms aim learning good policy based only on historical
interaction data. This paradigm allows for leveraging previously-collecte data in learning policies while avoiding possibly costly and dangerous trial and errors and finds applications in a wide range of domains from precision medicine (Tang et al. 2022) 2 robotics (Sinha et al. (0222) to climate (Rolnick) ct al. 2022). Despite wide applicability, offline RL has yet to achieve success stories akin to those observed in online settings that allow for trials and errors (Mnih et al. 2013 Silver al. 2016 Ran
ct al. 2019 Mirhoseini et al. 2020 Oh et al. 2020 Fawzi et al. 2022 Degrave et al. 2022).
Enabling offline RL for complex real-world problems requires developing algorithms that first, handle complex high-dimensional observations and second, have minimal requirements on the data coverage and "best" exploit the information available in data. Powerful function approximators such as deep neural networks are observed to effective in handling complex environments and deep RL algorithms have been behind the success stories mentioned above. This motivates us to investigate provably optimal offline RL algorithms that can be combined with general function approximators and have minimal requirements the coverage and size of the offline dataset.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

In RL theory, the data coverage requirements are often characterized by concentrability defini- tions (Munos 2007 Scherrer 2014). For a policy x, the ratio of the state-action occupancy distribu- tion d' of π to the dataset distribution μ4, denoted by w" = = /u, is used to define concentrability. The most widely-used definition is lo concentrability, defined as the infinite norm of w", i.e., CT =I|="| || oc. Many earlier works on offline RL, require all all-policy foo concentrability (i.e.. C7 is bounded for all candidate policy π (Scherrer 2014 [Lu et al. 2019a Chen and Jiang 2019 Jiang
2019; Wang et al., 2019 Liao al. [2020; Zhang et al., 2020a) stronger assumptions such as a uniform lower bound on ((a (Xie and Jiang] (021)) However, such all-policy concentrability assumptions often violated in practical scenarios, and in most cases, only partial dataset coverage
is guaranteed.
To deal with partial data coverage, recent works use conservative algorithms, which try to avoid policies not well-covered by the dataset, to learn good policy with much weaker dataset coverage requirements (Kumar et al., 2020; Jin et al. (021). In particular, algorithms developed based on the face of uncertainty are shown to find the best covered policy
the principle of pessimism
(or sometimes they require coverage of the optimal policy) (e.g., Rashidinejjad et al. (2021 2022);
Zhan et al. (2022); (Chn and Jiang (2022)) However, most of these works use too concentrability to characterize the dataset coverage. This could still be restrictive even if we only require single- policy concentrability, since the lo definition characterizes coverage in terms of the worst-case maximum ratio over all states and actions. Other milder variants of the single-policy concentrability coefficient are proposed by Xie et al. ( Uchara and Sun (202I) which consider definitions that exploit the structure of the function class to reduce the coverage requirement and involve taking maximum over the functions in the hypothesis class instead of all states and actions. However, as show in Section 2.4 when the function class is very expressive, these variants will degenerate to foo concentrability. Moreover, previous algorithms requiring milder variants of single-policy concentrability are either computationally intractable (Xie et al. [022] Uehara and Sun [02[ or suffer suboptimal rate of suboptimality (Cheng et al. 2022). Therefore, natural and important question is raised:
Is there a computationally efficient and statistically optimal algorithm that can be combined with general function approximators and have minimal requirements on dataset coverage?
gencrtofunntton
We answer this question affirmatively by proposing novel algorithm named A-Crab (Actor- Critii Regularized by Average Bellman crror). We also discuss more related works in Appendix A
Table 1: Comparison of provable offline RI algorithms with general function approximation.
Algorithm
Computation
Any covered policy
Coverage assumption
Policy improvement
Suhoptimality
Xie et al.
2021
Intractable
Yes
single-policy. Chaltm
Yes
Uchara and Sun
2021
Intractable
Yes
single-policy, and &
Yes
Chen and Jiang
2022
Intructable
No
single cocilepplly... Aou. two-policy, &xp singlo-policy, Chettaa
No
Zhan et al.
2022
Efficient
Yes
Yes
0
yyrre
Cheng et
2022
Efficient
Yes
Yos & Robust
0
(izz
Rashidinejad et
2022
Efficient
single-policy, fox
Oodaglar al.
2022
Efficient
No
single-policy, &oo
No
0 VR
A-Crab (this work)
Efficient
Yos
single-policy. &2
Yos & Robust
1.1 Contributions
In this paper, we build on the adversarially trained actor-critic (ATAC) algorithm of Cheng et al. (2022) and combine with the marginalized importance sampling (MIS) framework (Xie et al.. 2019 Chen and Jiang 2022; Rashidinejad et al.) (022). In particular, we replace the squared Euclidean norm the Bellman--onsistency error term in the critic's objective of the ATAC algorithm with an importance- importance-weighted average Bellman error term. We prove that this simple yet critical modification of the ATAC algorithm enjoys the properties highlighted below (see Table I for comparisons with previous works).

---

concentrability
C Eoo
IT Bellman
Cτ
complexity of F
Figure I: An intuitive comparison of CT C%, and Bellman for fixed policy æ. Note that OZ,, CF independent of the function class F, and Cj always smaller thanC" Bellman grows F gets richer and converges to O
1. Optimal statistical rate in competing with the best covered policy: In Theorem I we prove that our A-Crab algorithm, which uses average Bellman error, enjoys an optimal statistical rate of 1/v.N In contrast, we prove in Proposition that the ATAC algorithm, which uses the squared Bellman error, fails to achieve the optimal rate in certain offline learning instances. As et al. (2022) explains, the squared Bellman-ente error regularizer appears to be the culprit behind the suboptimal rate of ATAC being 1/N1/3, Moreover, our algorithm improves is in contrast to the recent work Rashidinejad et al. (2022), which proposes an algorithm based on the MIS framework that achieves the 1/VN rate only when the optimal policy (i.c. the policy with the highest expected rewards) is covered in the data.
any policy covered in the data. This
2. A weaker notion of data coverage that exploits visitation structure: As we discussed earlier, foc concentrability notion is used in many prior works (Rashidinejad et al. [021: Chen and Jiang 2022 Ozdaglar et al., 2022 Rashidinejad et al. 2022). Our suportance-weigntee average Bellman error as well as using Bernstein inequality in the proof relies guarantees in terms of f2 single-policy concentrability notion that weaker than the fo variant. In particular, we have CT = || lloc and C = ||=" I|,,0. where || l|a, is the weighted 2-norm w.r.t. the dataset distribution μ. The latter implies that the coverage coefficient only matters much it is covered by the dataset. Moreover, by the definition of w",, we can obtain that (C7,)² Ex [w= (s, a)]. which provides another explanation of &a concentrability that the coverage coefficient only matters much is actually visited by the policy. There are also other notions of single-policy concentrability exploiting function approximation structures make the coverage coefficient smaller (e.g., Be Xie et al.) (202T)). However, these notions degenerate to O, as the function class gets richer (see Figure for an intuiiive comparison of different notions of concentrability and Section 2.4 for a rigorous proof).
3. Robust policy improvement: Policy improvement (PI) refers to the property that an offline RL algorithm (under careful choice of specific hyperparameters) can always improve upon the behavior policy that is used to collect the data. In particular, robust policy improvement (RPI) means the PI property holds under wide range of the choice of specific hyperparameters (Cheng 2002 Xie et al. 2022). Similar to the ATAC algorithm in Cheng et al. 2022), our approach enjoys the robust policy improvement guarantee shown in Theorem
Inheriting many other benefits of adversarially-trained actor-critic: Since our algorithm is based ATAC with different choice of regularizer, it can be easily implemented as ATAC to be applied to practical scenarios, and we provide experimental results Section Also, our algorithm robust to model misspecification and does not require the completeness assumption (Assumption in Cheng et al. (2022)) on the value function class, which makes it more practical. Moreover, our algorithm can learn a policy that outperforms any other policies well covered by the dataset.
2 Background
Notation. We use A(X) to denote the probability simplex over set X' and use Unif(X') to denote the uniform distribution over X. We denote by || I|a. VE,,(-)' the Euclidean norm weighted

---

by distribution μr. We use the notation x S y when there exists constant c >> 0 such that S cy and x 2 y if y S and denote x y if y and y S hold simultaneously. We also use standard O(+) notation to hide constants and use (-) to suppress logarithmic factors.
2.1 Markov decision process
An infinite-horizon discounted MDP is described by a tuple M = (. p).
where S is the
state space, AA is the action space, P : 8 x A + (8)) is the transition kernel, R: Sxx x A A(O0, 1)) encodes family of reward distributions with S x A + [0, 1] as the expected reward function, Y E [0, 1) is the discount factor and p S + [0, 1] is the initial state distribution. We assume A is finite while allowing S to be arbitrarily complex. A stationary (stochastic) policy : S + (AA) specifies distribution over actions each state. Each policy induces a (discounted) occupancy
density over Mate-action pairs d= S x A + [0. 1] defined as d' (s, a) == (1 - 7) Ei= 7 P(( s. a, a; T), where Ps(s; s, ar = a; x denotes the visitation probability of state-action pair (s, a) at time step t, starting at so ~ p(-) and following ग. We also write d' (s) = Eeead d" d= a) to denote the (discounted) state occupancy, and use [-] as shorthand of (ss.a)-a' [-] or Bond" H.
The value function of policy is the discounted cumulative reward gained by executing that policy (*((s == E 1I So = 8, 04 ~ T(-(s)), V 2 0] starting at state & E S where define Q function of policy the expected cumulative re-
rs R(st, dt). Similarly, ward gained by executing that policy starting from a state-action pair (s. a), i.e., @ a). = E E y'r, 80 s, Gg a, 0r (-(ss)), A tt 0J. We write (Tr = (1 - E)
(e,,)~= [r(8, a)] to represent the (normalized) average value of policy т. We denote by n² the optimal policy that maximizes the above objective and use the shorthand V = V= -- = Q to denote the optimal value function and optimal Q function respectively.
2.2 Function approximation
In modern RL, the state space S is usually large or infinite, making the classic tabular RI. algorithms not scalable since their sample complexity depends on the cardinality of S. Therefore, (general) function approximation is necessary for real-world scenarios with huge state space. In this paper, we assume access to three function classes: a function class F C (f S models the (approximate) Q-functions of policies, function class W C {w S x A that represents marginalized importance weights with respect to data distribution, and a policy class Il ( S + ( consisting of candidate policies. Our framework combines the marginalized importance sampling framework (e.g., Zhan et al. (2022); Rashidinjjjd et al. (2022)) with actor methods (Xie et al. [2211; [heng et al.) 2022). which improves and selects among set of candidate policies by successive computation of their Q-functions.
- [0, V max]] that
00, 1
For any function f E F and any policy π E IT, we denote f(. = ((lss( for any E S and denote Bellman operator T SB + R
(T" f) a) = r(s, a) + (s. [f((', .T)].
(1)
Note that solving the fixed point equation ( for f finds the Q-function of policy π.
We make the following assumption on the expressivity of our function classes.
Assumption 1 (Approximate Realizability). Assume there exists EF 2 0, s.t. for any policy e 11. minyer maXadmissible ||f - f12,,, S EF, where admissible v is defined by v E {d"l E I1].
This assumption is also required for Xie et al. (001)) Cheng et al. (2022). Note that when || T fll2., is small for all admissible v, we have ~ Q Therefore, Assumption] 1 assumes that for any policy n, QT is "approximatly" realized F. In particular, when e, = 0, Assumption is equivalent to Q" E F for any II.
2.3 Offline reinforcement learning
In this paper, we study offline RL where we assume access only to a previously-colletted and fixed dataset of interactions D {(s;, a;, rs, N where ~ R(s;, a:), si ~ P(. 8; 0z).
Without loss of generality, always assume that the all-one function is contained in W.

---

To streamline the analysis. we assume that (s),4;) pairs are generated i..d. according to a data distribution μ E (S x A). We make the common assumption that the dataset is collected by a behavior policy, i.e., Jr is the discounted visitation probability of a behavior policy, which we also denote by μ.. For convenience, we assume the behavior policy μ E IT. The goal of offline RI. is to learn good policy & (a policy with high J(f)) using the offine dataset. Also, for any function f that takes (s, a, r. as input, we define the expectation w.r.t. the dataset DD (or empirical expectation)
as Ep [f] N L ((:0)))))) (si, Oig 5.).
Marginalized importance weights. We define the marginalized importance weights of any policy T to be the ratio between the discounted state-action occupancy of и and the data distribution w (8, a) == d" (s.a). Such weights have been defined in prior works theoretical RI. (Xie and Jiang
p(x.a)
2020: Zhan et al. 2022 Rashidinejad et al.] 20022] Ozdaglar al. 2022) well as practical RL
algorithms (Nachum et al. 22019 b. Zhang et al. 2020b c Lee et al. 2021
2.4
Coverage of offline dataset
We study offline RL with access to dataset with partial coverage. We measure the coverage of policy I in the dataset using the weighted lz pagle-policy concentrability coefficient defined below.
Definition (l2 concentrability). Given a policy n. define Cy2 || = ||dd /ullz,.
This definition is much weaker than the all-policy concentrability conventionally used in offline RL (Scherrer 2014 Liu et al., 2019a Chen and Jiang 2019 Jiang 2019; Wang et al.] 2019 Liao
to be bounded for all E S and et al. 2020; Zhang et al. 2020a), which requires the ratio p(s,a)
(s,a
E as well as all policies л. The following proposition compares two variants of single-policy concentrability definition that appeared in recent works Rashidinejad et al. (202T); [Xie et al. 20021)
with the l variant defined in Definition [] see Appendix [A. for more discussion on different concentrability definitions in prior work. To our knowledge, the &g version of concentrability definition has been only used in offline RL with all-policy coverage (Farahmand al., 2010 Xie and Jiang 2020). In the context of partial coverage, [Uehara and Sun (2021) used lg version in a model-basee setting, but their algorithms are computationally intractable. Recent works Xie et al.) (0021); Cheng et al. (2022) use another milder version of concentrability than Loo, and we compare different concentrability versions in Proposition 2.1 An intuitive comparison presented in Figure ! Proposition 2.1 (Comparing concentrability definitions). Define the fox single-policy concentrabil- ity (Rashidinejad et al. 2021) as C = ||dT / /ulloc and the
single-policy concen-
trability (ie al. 2021 as Cheltman = max | f12,,= Then, it always holds (CT,)² S CTa
11 CT C. and there exist offline RL instances where (C7,) C
Reliman CT S
Vellmon
A proof for Proposition 2.1 is presented in Appendix B It is easy to show that the la variant is be bounded while
bounded by foo variant of concentrability as the former requires Eg- [s" a) I provides a concrete the latter requires un (s, a) to be bounded for any s E S and E A. Example example that C% is bounded by a constant while CT_ could be arbitrarily large.
Example (Arbitrarily large foo concentrability with constant lz concentrability). Consider the simplest two-arm bandit settings, where the dataset distribution is u((a)) = =1-2 m(az) = è for an arbitrarily small e 0. Let π be a policy s.t. x(a,) d (a1) 1 c, T(a2) d= (ag) =
Then one can calculate that un (a1) 1-2- I 1 and w" (az) e- Therefore, C22 v2 while
CT_ can be arbitrarily large.
Furthermore, the Bellman-consistern variant can exploit the structure in the Q-function class F for smaller concentrability coefficient. However, in situations where the class F is highly expressive, C Ceellman could be close to CV and thus possibly larger than Cg.
Finally, we make a boundedness assumption on our marginalized importance weight function class W in terms of Eg concentrability and single-policy realizability assumption.
Assumption 2 (Boundedness in la norm of W). Assume 1 S Ci, for all w E W.
Assumption (Single-policy realizability of wx). Assume nhd E W for some policy a E TI that we aim to compete with.
5

---

The definition of Cτ is similar to Xie and Jiang (2020) but they need u" E W for all и E II. which much stronger than our singleppoicyy realizabilityy assumption for W.
3 Actor-Critic Regularized by Average Bellman Error
In this section, we introduce our main algorithm named A-Crab (Actor-Critic Regularized by A Average Bellman error, Algorithm|] [ and compare it with the previous ATAC algorithm (Cheng et al., (202)). In Section 4 we will provide theoretical guarantees of A-Crab and discuss its advantages.
3.1 From Actor-Critic to A-Crab
Our algorithm design builds upon the actor-critic method, in which we iteratively evaluate a policy and improve the policy based on the evaluation. Consider the following actor-critic example:
म² E: arg max, (so: T), f" E arg min / - T (s a))²),
where we assume so is the fixed initial state in this example and recall that f(s, .T) EGEAT [{ a). Here, the policy is evaluated by the function that minimizes the squared Bellman error. However, insufficient data coverage may lead the critic to give an unreliable evaluation of the policy. To address this, the critic compute Bellman-consistenu pessimistic evaluation of π (Xie et al.) 2021), which picks the most pessimistic f E FF that approximately satisfies the Bellman equation. Introducing hyperparameter 33 2 0 tradeoff between pessimism and Bellman consistency yields the following criteria for the critic:
f arg min men πT + [(f {))
Cheng et al. 22022) argue that instead of the above absolute pessimism, a relative pessimism approach of optimizing the performance of relative to the behavior policy, results in an algorithm that improves over the behavior policy for any B 2 (i.c., robust policy improvement). Incorporating relative pessimism in the update rule gives the ATAC algorithm (Cheng et al. 2022);
πt E arg max ET (8, - 1 (s,
f" E arg aig f - fs, a)] +
Finally, we introduce the importance weights (s,, a) and change the squared Bellman regularizer an ampportance-wiigtee average Bellman error to arrive at:
** E arg max fT), TEll
f arg min (T( f) + (x, JEF
(2)
where
Cu(T, = Eulf(s, -
(3)
(x, max EB ((s.)))))))))))
wEW
Maximization in the importance-weightee average Bellman regularizer in (4) ensures that the Bellman error is small when averaged over measure w for any w E W, which turns out be sufficient to control the suboptimality of the learned policy as the performance difference decomposition Lemma shows.
Squared Bellman error v.s. importance-weighted average Bellman error. Unlike our ap- proach, the ATAC algorithm in Cheng et al. (2022) uses squared Bellman error, wherein direct empirical approximation leads to overestimating the regularization term To obtain an unbiased empirical estimator, Cheng et al. (022)) uses Ep [[f(s, a) - 7J (
minges Ep [g(s, a) - 7 ("s'ss'))''' +]) as the empirical estimator which subtracts the overesti- mation. Yet, we later see in Proposition even with this correction, ATAC fails to achieve the optimal statistical rate of I/VN in certain offline learning instances. In contrast, the importance- weighted average Bellman error in our algorithm is unbiased (as it involves no non-linearity). This makes our theoretical analysis much simpler and leads to achieving an optimal statistical rate of 1/VN as shown in Theorem
Such importance- minimax formulations of Bellman have been used in prior work
off pollcy evaluation (Uehara 2020) and offline RL with all policy coverage (Xie and Jiang 2020 'This is closely related to the infamous double-samplin issue; see Section 3.1 in Chen and Jiang 2019 for detailed discussion.

---

3.2 Main algorithms
Since we do not have direct access to the dataset distribution μa, our algorithm instead solves an empirical version of ( which can be formalized as
t arg max f"), s.t. f arg f)
(E
(5)
Fe
where
[D(T, =Bp[Ss,,T) [(),a)), a) -r -
(6)
fD( = max
(7)
weW
Algorithm 1 Actor-Critic Regularized by Average Bellman error (A-CRAB)
1: Input: Dataset D = {(s,, as. Ti, >>> value function class F, importance weight function
class W, no-regret policy optimization oracle PO (Definition 2).
2: Initialization: тı uniform policy, 8: hyperparameter.
3: for k 1, ..2,...; K do
4: SA < arg JEF LD(TT,, + (ET( where Lp and Ep are defined in 6
5: TT++1 + PO( (TT D).
6: end for
7: Output: म = Unif (
Similar to Cheng al. (2022), view program (5) as a Stackelberg game and solve it using no-regret oracle as shown Algorithm [ At each step k. the critic minimizes the objective defined by w.r.t Th, and πTy+1 is generated by no-regret policy optimization oracle, given below.
Definition 2 (No-regret policy optimization oracle). An algorithm PO is defined as no-regret policy optimization oracle if for any (adversarial) sequence of functions fI, fe.....Ja fK E where fo S x A + [0, Vmaxl, Yk [K], the policy sequence TT, TT, ... TKK produced by PO satisfies that for any policy π E II, it holds that Cap ΣK
D (f X) fie(s, [x)] o(1).
Among the well-known instances of the above no-regret policy optimization oracle is natural policy gradient (Kkkade, 2001) of the form T (a|s) TT (a]s) exp(1f (s, a)) with 7)
log [AI 2V K (Even-
Dar et al. 2009] Agarwal et al., 2021| Xic et al. 2021 Cheng et al. 2022). A detailed discussion
of the above policy optimization oracle can be found in Cheng ct al. (022)). Utilizing the no-regret
oracle in solving the Stackelberg optimization problem in (5) yields Algorithm
remark on critic's optimization problem. our algorithm, for any given æ, the critic needs to solve min max optimization problem, whereas in ATAC (Cheng et al. (022), the critic needs to solve a minfer maxge. problem. Since we only assume single-policy realizability for the class W (Assumption 3) but assume all-policy realizability for F (Assumption (T) (and Cheng assumption over which is much stronger), in
al. (2022) even requires the gellman-completenne general, the cardinality of W could be much smaller than F, which makes the optimization region of the critic's optimization problem our algorithm x smaller than F x in ATAC.
4 Theoretical Analysis
In this section, we show the theoretical guarantee of our main algorithm (Algorithm D. which is statistically optimal in terms of N.
4.1 Performance guarantee of the A-Crab algorithm
We first formally present our main theorem, which provides a theoretical guarantee of our A-Crab algorithm (Algorithm T). proof sketch is provided Section and the complete proof is deferred to Appendix C.3
7

---

Theorem 1 (Main theorem). Under Assumptions and and let E II be any policy satisfying Assumption 3 then with probability at least 1 8.
( (T) O (Ester + C2 VFF
2 opp
where Estat x Vmax Ci,
and π. returned by Algorithm log( J [1| (1 Vinax B., [
N
with the choice of? [
Below we discuss the advantages of our approach shown in the above theorem.
Optimal statistical rate and computational efficiency. When exr = O (i.e., there is no model misspecification), and when
x² is of the optimal policies, the output policy म achieves 0(1/ suboptimality rate which is optimal in N dependence (as long as K is large enough). This improves the O(1/N1/3) rate of the previous algorithm (Cheng et al. 2022). Note that the algorithm of Xie et al. 20021) can also achieve the optimal O N)) rate but their algorithm involves hard constraints of squared lg Bellman error and thus is computationally intractable. [heng et al. (2022) convert the hard constraints a regularizer, making the algorithm computationally tractable while degenerating the statistical rate. Our algorithm is both statistically optimal and computationally efficient, which improves upon both Xie al. (202I): Cheng et al.) (2022) simultaneously.
Competing with any policy. Another advantage of our algorithm is that it can compete with any policy TI long w dd /p contained in W. In particular, the importance ratio of the behavior policy w = d /p- /1/1s =| 1 is always contained in W, which implies that our algorithm satisfies robust policy improvement (see Theorem 2 for details).
Robustness to model misspecification. Theorem also shows that our algorithm robust to model misspecification on realizability assumption. Note that our algorithm does not need completeness assumption, while Xie et al. (2021): [Chng et al. (2022) both require the (approximate) completeness assumption.
Removal of the completeness assumption on F. Compared to our algorithm. Cheng et al. (2022) additionally need completeness assumption on F, which requires that for any / E F and E II, approximately holds that T f E F. They need this completeness assumption because they use the estimator ED [(f(s. - r >f((s T) T]} -mingeF ED [(g(s, a) - -ff(s', (s','s)))) ])) to address the over-estimation issue caused by their squared & Bellman error regularizer, and to make this 7f , π) )) to be small, which can be implied by the (approximate) completeness assumption. our algorithm, thanks to the nice property of the weighted average Bellman error regularizer which can be estimated by simple and unbiased estimator, we can get rid of this strong assumption.
estimator accurate, they need mingerFF Ep [g(s, a)
4.2 A-Crab for robust policy improvement
Robust policy improvement (RPI) refers to the property of offline RL algorithm that the learned policy (almost) always improves upon the behavior policy used to collect data over a wide range of the choice of some specific hyperparameters (in this paper, the hyperparameter is 3) (Cheng et al.
2022). Similar to ATAC in Cheng et al. 20022, our A-Crab also enjoys the RPI property. Theorem 2 implies that as long as 3 of N). our algorithm can learn a policy with vanishing suboptimality compared the behavior policy with high probability. The proof is deferred to Appendix
Theorem 2 (Robust policy improvement). Under Assumptions and 2 1-6, 8,
with probability at least
J(p) - J(T) S (3 () + Ci vEF) E
where Esta x Viaa Ci with the choice of any 2 0.
log([F [II (6
Vm
and R is returned by Algorithm
N
4.3 Suboptimality of squared 1o norm of Bellman error as regularizers
The ATAC algorithm of Cheng al. (2022) suffers suboptimal statistical rate O due to the squared & Bellman error regularizrr Intuitively, in Cheng et al. (2022), they use Lemma I to
8

---

decompose the performance difference and use - - to upper bound In T {s, a)l, which causes suboptimality since in general the former could be much larger than the latter. To overcome this suboptimal step, in our algorithm, we use weighted version of [2 T f) a)] as our regularizer instead of -f f22,,,, Proposition 4.1 shows that ATAC indeed statistically suboptimal even under their optimal choice of the hyperparameter 3 ((N2/5). The proof is deferred to Appendix E.II
Proposition 4.1 (Suboptimality ATAC). Ie change the regularizer s.t.
min C(g, f. f. D), f) Ilf T" fl2,, and ED( f. (enD))mmminCCc
geF
where fl n. D) Epllg(s, - - ))) then under all policy realizability (Q" E for all ग E 11) and completeness assumption f F for all т 1l and f & F), with their optimal choice of 3 ((N2/3) (Cheng et al. 2022), there exists instance s.t. the suboptimality of the returned policy of 5 (i.e., the output policy by ATAC) is (11/N1/3) with at least constant probability.
Proof Sketch
We provide proof sketch of our main theorem (Theorem in this section. The key lemma of the proof is presented Lemma I
Lemma 1 (Performance difference decomposition, Lemma 12 in Cheng et al. (2022 ) For any n, & 11, and any f A we can decompose ((x) ((+t as
E,,( T (), a)] + E, (TT (s, E, x) f(s, ft C Q*).
Note that the first two terms in the RHS of the decomposition are average Bellman errors of f and î w.r.t j and d=, Based on this lemma, we can directly use the average Bellman error as the regularizer instead of the squared Bellman error, which could be much larger and causes suboptimality.
Proof sketch of Theorem 7 For simplicity, we assume realizability of Q", i.c., eF O. By Lemmal and the definition of n, we have (Tx) - J(+) = 1 (J(T) - (TT)),, which equals to
E Iife - T fn. ET fu (s,
K
(a)
+ E. [ (s, TT - fu(s, TR)] + CT fc) - (TR, Q*+)).
(c)
By the concentration argument, with high probability, we have (T f) = E (D( f) estat and (T f) (D(T, esar for all E Il and f E F. Combining the fact that d 1a W. one can show that (a) + (b) < (T f&) S ( fk) + (Esaa) Therefore,
(TT (a) (b) (d) (TR, (&) 2 fs) + ( (T ²T*)
( ft) + 20 fi)) + O(Caa)) - LD (Tk: QTTA.
CDD(TA Q² + 28 Ta. 2²²² ( CD(TT xx²)
<0(cum)) + 2 Q (Caaae);
where the third inequality holds by the optimality of fg. and the last equality holds since the Bellman error of Q" w.r.t. is O. Therefore, with high probability,
( - (TT) < O (Estar) + Eppt
6 Experiments
In this section, we conduct experiments of our proposed A-Crab algorithm (Algorithm I using selection of the Mujoco datasets (v2) from D4RL offline RL benchmark (Fu et al., 2020). In particular, we compare the performances of A-Crab and ATAC, since ATAC the state-of the-arrttttttttt algorithm on range of continuous control tasks (Cheng et al. 2022).

---

A more practical version of weighted average Bellman error. Recall the definition of our proposed weighted average Bellman error regularizer
Ep f) = max [EI[w(s, (o)lu(ss))((()) a)(f(s -r - rf +))l
weW
Since the calculation of (TT f) requires solving an optimization problem w.r.t importance weights w, for computational efficiency, we choose W = [0, Cx as in Hong et al. 2023). and thus Coc max(Ex([J(sss)) a) - x =))=), 7f(s's (s';" T. a))++)) (8) where (.)+ = max(-, 0} and Coc can be viewed as a hyperparameter. We also observed that using a combination of squared Bellman enror and our average Bellman error achieves better performance in practice, and we conjecture the reason is that the squared Bellman error regularizer is computationally efficient and statistically suboptimal, while our average Bellman error regularizer is statistically optimal while computationally less efficient, and thus the combination of these two regularizers can benefit the training procedure.
(T, (T,
The practical implementation of our algorithm is nearly identical to (a lightweight version of) ATAC (Cheng al. 2022). except that we choose
(2 + SEDII(f - (T ()),
2
as the regularizer, while ATAC uses 3Epl((f - T" All hyperparameters are the same as ATAC, including 3. For the additional hyperparamter Coc, we do grid search on {1, 5, 10, 20, 50, 100, 200}.
Figure e compares the performance of ACrab and ATAC during training. It shows that A-Crab has higher returns and smaller deviations than ATAC in various settings mwalker2d-randon halfcheetah- medium- replay, hopper-mediung medium-expert). We provide more details and results in Appendix F.] We also observed that in most settings, A-Crab has smaller variance, which shows that the training procedure of A-Crab more stable. We provide the choice of B and C.o. for each setting in Table F3 Note that we use the same value of /3 as in ATAC.
walker2d-rand
hallcheetah-mee-rrpllay
hopper-med-exp
ACrab
500
return
ATAC
ATAC
ACrab
ACrab
steps
steps
Steps 10"3)
(a) walker2d-rand
(b) malfehectah-mme--rpphh
(c) hopper-med-ext
Figure 2: Comparison of A-Crab and ATAC. For each algorithm, we run 8 copies with random seeds 0-7 and plot the mean and standard deviation. We the same pre-training method ATAC for 100 epochs, and the plot starts after pre- trainiii
Discussion
We present new offline RL algorithm called A-Crab (Algorithm I that can be combined with general function approximators and handle datasets with partial coverage. A-Crab is an actor-critic method, where the critic finds relatively pessimistic evaluation of the actor while minimizing an importance- weighted average Bellman eтror. We prove that A-Crab achieves the optimal statistical rate of 1/ // converging to the best policy "covered" in the data. Importantly, the notion of coverage here is weaker & variant of the single-policy concentrability, which only requires the average marginalized importance weights over visitations of the target policy to bounded. Also, A-Crab enjoys robust policy improvement that consistently improves over the data-collection behavior policy. Moreover, we empirically validated the effectiveness of A-Crab in the D4RL. benchmark. Interesting avenues for future work include combining A-Crab's 's offline learning with an online fine-tuning algorithm with a limited and--or budget and developing new measures for single-policy coverage that leverage both the visitation and hypothesis class structures.
10

---

Acknowledgements
This work is partially supported by NSF Grants IIS-1901252 and CCF-1909499, The work was done when HZ was a visiting researcher at Meta.
References
Alckh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. J. Mach. Learn. Res., 22(98): 1-76, 2021.
Andras Antos, Rémi Munos, and Csaba Szepesvari. Fitted Q-iteration continuous action-space mdps. In Neural Information Processing Systems, 2007.
András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with Bellman- residual minimization based fitted policy iteration and single sample path. Machine Learning, 71 (1):89-129, 2008
Jinglin Chen and Nan Jiang. Information theoretic considerations in batch reinforcement learning. arXiv preprint 1XX5v:995.00333 2019.
-teeoretion-hhorrttic
Jinglin Chen and Nan Jiang. Offline reinforcement learning under value and density-ratio realizability: The power of gaps. In The 38th Conference Uncertainty in Artificial Intelligence, 2022.
Ching-An Cheng, Tengyang Xie, Nan Jiang, and Alekh Agarwal. Adversarially trained actor critic for offline reinforcement learning. In Proceedings of the 39th International Conference on Machine Learning, volume 162, 2022.
Jonas Degrave, Federico Felici, Jonas Buchli, Michael Neunert, Brendan Tracey, Francesco Carpanese, Timo Ewalds, Roland Hafner, Abbas Abdolmaleki, Diego de Las Casas, et al. Magnetic control of tokamak plasmas through deep reinforcement learning. Nature, 602((897):414 (4-99):):44449999 1494 2022.
Eyal Even-Dar, Sham M Kakade, and Yishay Mansour. Online markov decision processes. Mathe-
matics of Operations Research, 34(3):726-736, 2009.
Amir Massoud Farahmand, Rémi Munos, and Csaba Szepesvári. Error propagation for approximate policy and value iteration. In Advances in Neural Information Processing Systems, 2010.
Alhussein Fawzi, Matej Balog, Aja Huang. Thomas Hubert, Bernardino Romera-Paredes, Moham- madamin Barckatain, Alexander Novikov, Francisco J R Ruiz, Julian Schrittwieser, Grzegorz Swirszez, et al. Discovering faster matrix multiplication algorithms with reinforcement learning. Nature, 610(7930):4--3,, 2022.
Yihao Feng, Lihong Li, and Qiang Liu. A kernel loss for solving the Bellman equation. arXiv preprint arXiv:1905. 10506, 2019.
Justin Fu, Aviral Kumar, Ofrr Nachum, George Tucker, and Sergey Levine. D4RL: Datasets for deep data-driven reinforcement learning. arXiv preprint arXiv:2004.07219, 2020.
Scott Fujimoto and Shixiang Shane Gu. A minimalist approach to offline reinforcement learning. Advances in neural information processing systems, 34:20132-201 2021.
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.
Seyed Kamyar Seyed Ghasemipour, Dale Schuurmans, and Shixiang Shane Gu. EMaQ: Expected- max Q-learning operator for simple yet effective offline and online RL. arXiv preprint 1rXiv:2007.11091, 2020.
Kaiyang Guo, Yunfeng Shao, and Yanhui Geng. Model-based offline reinforcement learning with pessimism-modulatee dynamics belief. arXiv preprint arXiv:2210.06669) 2022.
Kihyuk Hong, Yuhang Li, and Ambuj Tewari, primal-dual-critcc algorithm for offline constrained reinforcement learning. arXiv preprint ar arXiv:2306.07818. 2023.

---

Natasha Jaques, Asma Ghandeharioun, Judy Hanwen Shen, Craig Ferguson, Agata Lapedriza, Noah Jones, Shixiang Gu, and Rosalind Picard. Way off-po batch deep reinforcement learning of implicit human preferences in dialog. arXiv preprint arXiv: 1907.00406 2019.
Nan Jiang. On value functions and the agent-environment boundary. arXiv preprint arXiv:1905113341 2019.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline RL? In International Conference Machine Learning, pages 5084-5096. PMLR, 2021.
Sham M Kakade. A natural policy gradient. Advances in neural information processing systems, 14, 2001.
Rahul Kidambi, Aravind Rajeswaran, Praneeth Netrapalli, and Thorsten Joachims. MOReL: Model- based offline reinforcement learning. arXiv preprint arXiv:2005.05951, 2020.
Ilya Kostrikov, Rob Fergus, Jonathan Tompson, and Ofir Nachum. Offline reinforcement learning with Fisher divergence critic regularization. In International Conference on Machine Learning, pages 5774-5783, PMLR, 2021.
Aviral Kumar, Justin Fu, George Tucker, and Sergey Levine. Stabilizing off-policy Q-learning via bootstrapping error reduction. arXiv preprint 1rXiv:1906.0000 00949, 2019.
Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative Q-learning for offline reinforcement learning. arXiv preprint (tti:20000047779 2020.
Aviral Kumar, Joey Hong, Anikait Singh, and Sergey Levine. Should I run offline reinforcement learning or behavioral cloning? In International Conference on Learning Representations, 2021.
Jongmin Lee, Wonseok Jeon, Byungjun Lee, Joelle Pineau, and Kee-Eung Kim. OptiDICE: Offline
policy optimization via stationary distribution correction estimation. In International Conference on Machine Learning, pages 6120-6130. PMLR, 2021.
Peng Liao, Zhengling Qi, and Susan Murphy. Batch policy learning in average reward Markov decision processes. arXiv preprint arXiv:2007.11771, 2020.
Boyi Liu, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural trust region/proximal policy optimization attains globally optimal policy. In Neural Information Processing Systems, 2019a.
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Off-policy policy gradient with state distribution correction. arXiv preprint wwXiv:1904.08... 2019b.
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Provably good batch reinforce- ment learning without great exploration. arXiv preprint arXiv:2007.08202. 2020.
Jiří Matoušek and Jan Vondrák. The probabilistic method. Lecture Notes, Department of Applied Mathematics, Charles University, Prague, 2001.
Azalia Mirhoseini, Anna Goldie, Mustafa Yazgan, Joe Jiang, Ebrahim Songhori, Shen Wang. Young- Joon Lee, Eric Johnson, Omkar Pathak, Sungmin Bae, al. Chip placement with deep reinforce- ment learning. arXiv preprint arXiv:2004. 10746, 2020.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing Atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602, 2013.
Rémi Munos. Performance bounds in norm for approximate value iteration. SIAM journal on control and optimization, 46(2):541-55 -511,16111111 2007.
Ofrr Nachum, Yinlam Chow, Bo Dai, and Lihong Li. DualDICE: Behavior-agnostic estimation of discounted stationary distribution corrections. In Advances in Neural Information Processing Systems, pages 2325, 2019a.
Ofir Nachum, Bo Dai, Ilya Kostrikov, Yinlam Chow, Lihong Li, and Dale Schuurmans. AlgaeDICE: Policy gradient from arbitrary experience. arXiv preprint arXiv:1912.02074, 2019b.
12

---

Ashvin Nair, Murtaza Dalal, Abhishek Gupta, and Sergey Levine. Accelerating online reinforcement learning with offline datasets. arXiv preprint htt::20000093559 2020.
Junhyuk Oh, Matteo Hessel, Wojciech M Czarnecki, Zhongwen Xu, Hado P van Hasselt, Satinder Singh, and David Silver. Discovering reinforcement learning algorithms. Advances in Neural Information Processing Systems, 33: 10:100000,7, 2020.
Asuman Ozdaglar, Sarath Pattathil, Jiawei Zhang, and Kaiqing Zhang. Revisiting the linear- programming framework for offiin RL with general function approximation. arXiv preprint arXiv:2212.13861, 2022.
Xue Bin Peng, Aviral Kumar, Grace Zhang, and Sergey Levine. Advantage-wiighted regression: Simple and scalable off-policy reinforcement learning. arXiv preprint arXiv: arXiv: 2019 2019.
Yongyi Ran, Han Hu, Xin Zhou, and Yonggang Wen. Deepee: Joint optimization of job scheduling and cooling control for data center energy efficiency using deep reinforcement learning. In 2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS), pages 645-655. IEEE, 2019.
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline rein- forcement learning and imiitaion learning: A tale of pessimism. Advances in Neural Information Processing Systems, 34:1 17771 2021.
Paria Rashidinejad, Hanlin Zhu, Kunhe Yang, Stuart Russell, and Jiantao Jiao. Optimal conserva- tive offline RL with general function approximation via augmented Lagrangian. arXiv preprint (tfi:2211.007//1 2022.
Shideh Rezaeifar, Robert Dadashi, Nino Vieillard, Léonard Hussenot, Olivier Bachem, Olivier Pietquin, and Matthieu Geist. Offline reinforcement learning as anti-exploration. In Proceedings of the AAAI Conference Artificial Intelligence, pages 8106 -81 14, 2022.
Mare Rigter, Bruno Lacerda, and Nick Hawes. RAMBO-RL: Robust adversarial model-based offline reinforcement learning. arXiv preprint arXiv:2204. /2581, 2022.
David Rolnick, Priya L Donti, Lynn H Kaack, Kelly Kochanski, Alexandre Lacoste, Kris Sankaran, Andrew Slavin Ross, Nikola Hilojevic-Dupont, Natasha Jaques, Anna Waldman-Brows al. Tackling climate change with machine learning. ACM Computing Surveys (CSUR), 1-(2): 2022.
Bruno Scherrer. Approximate policy iteration schemes: comparison. In International Conference on Machine Learning, pages 1314-1322, 2014.
Laixi Shi and Yuejie Chi. Distributionally robust model-based offline reinforcement learning with near-optimal sample complexity. arXiv preprint arXiv:2208.0576) 2022.
Noah Siegel, Jost Tobias Springenberg, Felix Berkenkamp, Abbas Abdolmaleki, Michael Neunert, Thomas Lampe, Roland Hafner, and Martin Riedmiller. Keep doing what worked: Behavioral modelling priors for offline reinforcement learning. arXiv preprint arXiv:2002.0839; 2020.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schritwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of Go with deep neural networks and tree search. nature, 529(7587):444-88, 2016.
Samarth Sinha, Ajay Mandlekar, and Animesh Garg. S4RL: Surprisingly simple self-supervision for offline reinforcement learning in roboties. In Conference on Robot Learning, pages 907-917. PMLR, 2022.
Yuda Song, Yifei Zhou, Ayush Sekhari, J Andrew Bagnell, Akshay Krishnamurthy, and Wen Sun. Hy- brid RL:: Using both offline and online data can make RL. efficient. arXiv preprint arXiv:22 2022.
Adith Swaminathan and Thorsten Joachims. Batch learning from logged bandit feedback through counterfactual risk minimization. The Journal of Machine Learning Research, 16(1):1331-1755, 2015.
13

---

Csaba Szepesvári and Rémi Munos. Finite time bounds for sampling based fitted value iteration. In Proceedings of the 22nd international conference on Machine learning, pages 880-887, 2005.
Shengpu Tang. Maggie Makar, Michael Sjoding, Finale Doshi-Velez and Jenna Wiens. Leveraging factored action spaces for efficient offline reinforcement learning in healthcare. Advances Neural Information Processing Systems, 2022.
Masatoshi Uehara and Wen Sun. Pessimistic model-based offline reinforcement learning under partial coverage. In International Conference Learning Representations, 2021.
Masatoshi Uchara, Jiawei Huang, and Nan Jiang. Minimax weight and Q-function learning for off- policy evaluation. In International Conference Machine Learning, pages 9659-9668 PMLR, 2020.
Masatoshi Uchara, Xuezhou Zhang, and Wen Sun. Representation learning for online and offline RL in low-rank MDPs. arXiv preprint arXiv:2 10.00665,, 2021.
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates of convergence. In International Conference on Learning Representations, 2019.
Xinqi Wang, Qiwen Cui, and Simon S Du. On gap-dependent bounds for offline reinforcement learning, arXiv preprint arXiv:2206.001/ 2022.
Yifan Wu, George Tucker, and Ofir Nachum. Behavior regularized offline reinforcement learning, 2019.
arXiv preprint arXiv:1911.1II
Tengyang Xie and Nan Jiang. Q* approximation schemes for batch reinforcement learning: A theoretical comparison. In Conference on Uncertainty Artificial Intelligence, pages 550-559. PMLR, 2020.
Tengyang Xie and Nan Jiang. Batch value-function approximation with only realizability. In International Conference Machine Learning, pages 11404-11413, PMLR, 2021.
Tengyang Xie, Yifei Ma, and Yu-Xiang Wang. Towards optimal off-policy evaluation for reinforce- ment learning with marginalized importance sampling. Advances in Neural Information Processing Systems, 32, 2019.
Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-ccnsistent pessimism for offline reinforcement learning. Advances in neural information processing systems, 34:6683-6694 2021.
Tengyang Xie, Mohak Bhardwaj,, Nan Jiang, and Ching-An Cheng. Armor: A model- based framework for improving arbitrary baseline policies with offline data. arXiv preprint arXiv:2211.04533 2022.
Yuling Yan, Gen Li, Yuxin Chen, and Jianqing Fan. The efficacy of pessimism in asynchronous Q-learning. arXiv preprint vrXiv:2203.0736. 2022.
Ming Yin and Yu-Xiang Wang. Towards instance-optimal offline reinforcement learning with pessimism. Advances neural information processing systems, 34:4065-4078, 2021.
Ming Yin, Yaqi Duan, Mengdi Wang, and Yu-Xiang Wang. Near-optimal offline reinforcement learning with linear representation: Leveraging variance information with pessimism. arXiv preprint arXiv:2203.052 2022.
Tianhe Yu, Garrett Thomas, Lantao Yu. Stefano Ermon, James Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma. MOPO: Model- offline policy optimization. arXiv preprint 20X.:20005..2.39, 2020.
Tianhe Yu, Aviral Kumar, Rafael Rafailov, Aravind Rajeswaran, Sergey Levine, and Chelsea Finn. COMBO: Conservative offline model-hased policy optimization. arXiv preprint a3X::32102.08363, 2021.
14

---

Andrea Zanette, Martin Wainwright, and Emma Brunskill. Provable benefits of actor-critic methods for offline reinforcement learning. Advances neural information processing systems, 34:13626- 13640, 2021.
Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason Lee. Offline reinforcement learning with realizability and single-polie polecy concentrability. In Conference on Learning Theory, pages 2730-220000 2775. PMLR, 2022.
Junyu Zhang, Alec Koppel, Amrit Singh Bedi, Csaba Szepesvari, and Mengdi Wang. Varia- tional policy gradient method for reinforcement learning with general utilities. arXiv preprint arXiv:2007.02155, 2020a.
Ruiyi Zhang, Bo Dai, Lihong Li, and Dale Schuurmans. GenDICE: Generalized offline estimation of stationary values. In International Conference on Learning Representations, 2020b.
Shantong Zhang, Bo Liu, and Shimon Whiteson. GradiemtDICE: Rethinking generalized offline estimation of stationary values. arXiv preprint arXiv:2001. 2020c.
Xuezhou Zhang. Yiding Chen, Xiaojin Zhu, and Wen Sun. Corruption offline reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 5757-5773. PMLR, 2022.
15

---

A Related Work
In this section, we review additional related literature not covered in the introductions.
A.1 Dataset Coverage Assumptions
One central challenge of offline RL is the insufficient coverage of the dataset. In RL theory, concen-
trability is often used to characterize dataset coverage (Munos) 2007: Scherrer] 2014). For example.
many earlier works require all all-policy fo concentrability (Scherrer 2014]Liu
al. 2019a Chen
and Jiang 2019] Jiang. 2019; Waan et al. 2019: Liao et al.) 2020; Zhang et al.) 2020a). Some
works even require the ratio between occupancy probability induced by polices and the dataset
distribution to be bounded for every time step (Szepesvári and Munos 2005 Munos 2007 Antos
al. 2008 Farahmand et al., 2010; Antos et al. (007). The work Xie and Jiang (2021) makes
stronger assumptions such as requiring lower bound on conditionals ju(a(s).
Since the all-policy concentrability assumption is strong and often be violated in practice, recent algorithms requiring only partial data coverage assumptions are developed based on aanle-policy to concentrability (Rashidinejad et al.] 202T Zhan et al.) 2022 Rashidinejad al. 2022 Chen and Jiang, 2022, Ozdaglar et al., (022). However, This could still be restrictive even if only single-policy
concentrability is required since the eo concentrability is upper bound of density ratios over all state-action pairs.
Milder versions of Loo concentrability have been studied in both all-policy concentrability frame-
2020) or and single-policy work (Xie and Jiang] 2020, [20TT] Feng et al.] 2019 Uehara et al.
concentrability (Uehara and Sun 2021; Xie al. 2021] Song al. 2022, Cheng et al.. 2022). However, these works based on milder versions of lo single-policy concentrability are either com-
putationally intractable (Uchara and Sun 2021 Xie et al. 2021 suffer a suboptimal statistical rate (Cheng et al. 2022).
Our work uses &2 concentrability version, which also appears in Xie and Jiang (020). In particular, they also use weighted average Bellman error their algorithm. However, their algorithm requires all-policy concentrability assumptions and thus cannot deal with partial dataset coverage. To the best of our knowledge among previous works, only [Uehara and Sun (00II) used la single-policy concentrability to characterize data coverage, but their algorithm is designed for model-based settings and are computationally intractable. Another closely related work is Uehara et al. (2020), which also uses weighted average Bellman error. However, their algorithm is in the off off-policy evaluation (OPE) framework, and they use lo concentrability version to characterize dataset coverage.
A.2 Conservative offline reinforcement learning
To address partial dataset coverage in offline RI., line of recent applied works studies conservative algorithms, which can be divided into several categorics.
The first category enforces the learned policy to be close to the behavior policy (or equivalently, dataset), which ensures that candidate policies not well covered by the dataset are eliminated. This can be accomplished by either adding constraints explicitly (Fujimoto et al., 2019 Kumar et al.
2019; Wu et al. | [Jaques et al., 2019: Siegel al.) 2020 Ghasemipour et al. 2020 Fujimoto and Gu 2021 ), implicitly (Peng et al.) 2019 Nair et al.] (020). or by importance sampling with
bounded ratio Swaminathan and Joachims 2015 Liu et al. 2019b; Nachum et al. 201 Zhang
et al. 2020c by Lee et al. 2021).
The second category consists of model- based methods such as adversarial model lcarning Riigter ct al., (2022), learning pessimistic models (Kidambi et al.] 20200] Guo et al.) 2022). using model ensembles to form penalties (Yu et al. (020)) or combining model and values (Yu al. 2021).
The last category aims to learn conservative values such as fitted Q-iteration using conservative update (Liu al. 2020), conservative Q-learning (CQL) (Kumar et al. 2020), critic regularization (Kostrikov et al. 2021). and subtracting penalties (Rezaeifar et al.) 20022).
On the theoretical side, many works use some form of uncertainty quantification to design to
ensure pessimism (Yin and Wang 202T Kumar et al. 2021 Uehara et al. 202T Yin et al.] 2022]
Zhang et al. 2022 Yan et al. 2022 Shi and Chi 2022
Wang et al.) 2022
Except for uncertainty
16

---

quantification, in linear function approximation settings, Zanette et al. (021)) uses value function perturbation combined with the actor-critic method. Recent ad vances in the theory pessimistic algorithms include MIS (Zhan et al. 2022 Chen and and.Jigg] 2022) and adversarially trained actor-critic (ATAC) (Cheng et al. 2022). particular, our algorithm built based on MIS combined with the actor-critic method.
B Proof of Proposition 2.1
The first part of the proposition easy to see:
d= (=)))a) Ey Ci
dc (s, ((s,a)
(CH,) = 11w0 -Epl(w
(s, (s,
C. Ep
Cia
p(s,a)
C = 1|| / C
For the second part, consider the case where for fixed policy and for any S, A, there exists f F such that f), a) is non-zero only at (s, a) and zero otherwise. The Bellman-consistent concentrability defines C Rellman to be the smallest constant that
fl T fl1,,0
max JEF
f T fl12,p I C
Bellman
(f f'² add (s,
max
(s - TT () ()((s) S C
Rellman
8,0
d' (s)
max
C Bellman
6.0
u(s,a)
which makes it equal to the foo variant. On the other hand, the la variant only requires the average importance weights to be bounded:
d' ((,aa) 2 ((s,a))
dd (s
Σ S,0
((s,a)= -Ed
p(s,a) S (C,)))
C Theoretical Analysis of the Main Theorem
In this section, we provide theoretical proof of our main theorem (Theorem) I. We first present two key lemmas in Appendix C.I and then prove the main theorem in Appendix C.3 For convenience, we always assume Assumptions to hold.
C.1
Key lemmas
The first lemma shows that with high probability, the population version of our weighted average Bellman error regularizer is close to the empirical version.
Lemma 2 (Concentration of the empirical regularizer). With probability at least 1 - for any f E F, II. we have
(m, ED(TT, fll < Crar-
Proof. We condition on the high probability event in Lemma 4 For any F and æ E II define
w arg max (T( f) arg max [w, of T TT f)(s a)]l and define wx,f
17

---

arg maxwEw & arg maX
ELCardoee " - -f(s', m)) Then
-
=I (0, (8, (S - T (s,, a)]l
Σ
N
(s,0,,,)))
- aS - T (s, [))]
|By (8,
(8 ('8
+ W a) (s.
Σ
wn (n. (r.
N (s,0,T,e')E
20 Esta -stat
where the inequality holds by the optimality of wa, and Lemma Similarly, ft f)
(s. - (s)
1
Σ
wh -
N
w -
-r
N (s,0,,,'))D
Σ in (3) - - -
N
(s,ana))
Sestat + 0 Estats
where the inequality holds by the optimality 0x.f and Lemma
The next lemma provides a high pigh-probability upper bound of the empirical weighted average Bellman error of fx w.r.t π,, where fa is the (approximate) Q-function of
Lemma (Empirical weighted average Bellman error approximate Q function). With probability at least - 8, for any E 11, we have
ED(T,, fx) Ci VEF + Caua-
where Ja arg min maxadmissible
|| - I1,,
Proof. We condition the high probability event in Lemma Since
(T,
max [w,, a) T (s,,))))))) weW
< max 1 -T* f211,, weW W
<C VEF.
where the first inequality is by definition of fa and Assumption [
inequality and the second inequality is by the we can immediately obtain that
Ep(n, fn) s (TT, + Caat Ci ver + Cata-
C.2 Complementary lemmas
We provide two complementary lemmas in this section, which are both high-probabiliiyy concentration incqualities.
18

---

Lemma 4 (Concentration of weighted average Bellman error). With probability at least for any f E F, π E II and w E W. we have
BU - [w]]
Σ
w(8; ((s,,))
-r-
N
(s.D)))))
log( FIIIW///
Vax Bud log | [1
<0
Vina Cis
N
N
Proof. It suffices bound
ExI(f - TT N
Σ -
(s.0.r,e")DD
for any fixed F, E II, w E W, and union bound and the triangle inequality conclude.
Note that
Ep
Σ (f(s,a) - rf (s)
N
(s.0,r,0))
[[[ r - x))((() a]] - Brops (1 [[[(s,)) - 75(6, T))
=E -ls.aaprrrrrtte)e
=
= (s.)) [ff a) f ())
Then by Bernstein's 's inequality, we have that with probability at least - 8,
- -T Ep1(--"
Σ (DDD),
(f(s, -
a) r - (T)((()))))ss.0)))
Var Vfrul[f-Te log (1/0)
Vmax Bar log log(1/6)
<0
Since
Var, -T- S - - O(V nax /w112 S OVV2 Faax (Ct) )2)
we can obtain that
E Ip - flw]
Σ
(f(s, - - ((s,a)---af(6 +))w(s,a)
N
(s.0,T,8))
log(1/8)
V Vmax Bug (og(1/0))
50
Vmax Ci,
N
N
which implies the result.
Lemma 5 (Concentration of the actor's objective). With probability at least 8, for any f F, π II, we have
log(1
[I
[c. CD(T, f)l fll 5
|Vmax
< Estat
N
where Extat is defined in Lemma 4
Proof. Note that E,, (,, []] = ( (T, f) and ()( s(s, a)l S O(Vmax). Applying a Hoeffd- ing's 's inequality for any fixed f. and union bound over all f F. II, we can obtain that with probability at least 1 - 6, it holds that
(x, (0(,, s ((Vmax
log((F1111188)
for all f E F and II.
19

---

C.3
Proof of Theorem 1
Now we are able to prove our main theorem equipped with lemmas in previous sections.
Proof of Theorem
By Lemma
1 and the definition of म, we have
1 (((N))
- -
K k=1
[lfk - T fk) TThh
+ ExI(T** fo (s,)
(a)
(6)
[=((f((s fa (s,(5TT))) mT)] Lu(TA, sk) f (TT))
(d)
Now we condition on the high probability event in Lemma and Lemma 5 simultaneously and rescale 5 by 1/2 and apply union bound. Note that d"/p E W, which implies that (a) + (6) N
(T,, fx) < 2E (TTe: fk) + 2Estat. where the last inequality holds by Lemma 2 By Lemma 13 of
Cheng et al. (022). we can obtain that
[ )* (Tk fnx)l ml - -T 122, + llf -T fm 112,0r S ((VCF),
where fFA - arg fer maXadmissille 1lf - T f1.... Also, by Lemma we have
(T f1)) LD(TE, fa)l + (Tkk) - LD(TT, ((sum).
Therefore,
(a) + (b) + (d) (Tp(kk fk) (T fk) + 26 Cp + <LD(TT fk) + ( fk) ( - CD( ++ +
<CD(TT fre) + 28 fxe) O(Esa)) - (m) O(VEF) <0(Euu + C%2 VEF).
where the third inequality holds by the optimality of fk. and the last inequality holds by Lemma Therefore,
[(T) J(#) < (Estat + C%2 CFFVEF) + Cap
D Analysis of Robust Policy Improvement
Proof of Theorem
2 By Lemma [and the definition of H, we have
1 J(k) J(ā)=
2 J(Tx)
K
K
I(fx - Thh fa)
+ B,T fo fs)(s,a)
(a)
(0)
Eg [f - fa mK)] CT fu) Cu(TNo (=(x):(*+)) Q*+)).
(d)
Now condition the high probability event in Lemma 2 and Lemma simultancously and rescale 5 by 1/2 and apply a union bound. Note that (a) + (b) 0. By Lemma 13 of Cheng et al. (2022).
obtain that
(TR. T* L, (T fx. S Ilfa, - T Sax 12 + Il5m - = fa. 12.0 S (((FF).
(9)
20

---

where fmz _ arg migminge SEr fER max llf - f4 Also, by Lemma 5 we have
( (1e CD(T sall (T Sma] CD(Tk fmi)l ((esm))
(10)
Therefore,
(TK fk) C )
S (Tp(T fk) + (T fk: - C Q²t))
(Eb(s,) 2 0)
(T fk) + BED(TK: fie) C Q(=²) 3ED(TT:
+ 80% Vez + -.seu
(Leema 3
(T fk) + (T (TttTT fu) (D(TTA fmx) (T
+ (3 + () + Ci2 VEF)
<(3 + 1) (F + C2 vey).
(Optimality of fx)
Therefore,
J(n) J(a) S (8+1) 11(sm C(.EEF) Caps
E Analysis of the Suboptimality of ATAC
In this section, prove Proposition 4.1 in Appendix E. For convenience, Ber((p) to denote Bernoulli variable with parameter p, and use (in () to denote a binomial variable with parameters and p.
E.1 Proof of Proposition 4.1
Construction of a two-arm bandit example. Assume there are two arms a1 02. Assume 3 = Õ(Na) where a >> 2. Note that this is a more general case than 3 = ((N2/3) as stated in the proposition. Let A min 1/10). Assume the reward of the first
is deterministic, i.e.,
r(a,) = 1/2 + A, and r(a2)= = Berm(122) Let II = { T2). where πı (a1) = 1, T (a2) = 0, and Also, let F {fi. f2). where fa 1/2 + A, (02) 1/2 and fz(a1) = 1/2 A, f2((2) = 1/2 + 2A. Finally, the dataset distribution satisfies ((02) NA ((()) = p(az). Note that in bandit settings, for any policy æ and any function f. we have Q fff = Therefore, the example above satisfies both completeness and realizability assumptions.
T2(a1) 0, T2 (a2)
Proof of the suboptimality of ATAC. [fT (T) (a))
The ATAC algorithm is simplified to
arg max nell
s.t. f" E arg min E, (f( - f(a)] + IE, - (a))
fef
in bandit settings.
For convenience, we assume that (a = = Pa a1). Note that by anti-concentration of the binomial distribution (Lemma 6), we have that with constant probability, it holds that f(az) 2 VNll22) 2A.
Conditioned on this event, we compute f and - separately, We have
C1(=1,f1) - =E, - (a)) = (m)) -aaaa/aaaaaaaaaaaaaaaaaaaaaaa--- (((a))( (a)) CD(TI, -,,[/((m))
1 N - [2(0) [2(m1) u(a1))2(a1)) -1(a2)/2(2) =p(oz)(f((a1) fe(02)) 1
NA
21

---

and
(1) { 2 Bu((z)
[ED(TI, fi) = 30 - (a)) By(a2)
2)
[ED(TI, (2) 10,21 (a)))]
-
1
2
( + + )
=Bp(a2)
f(a2)
24
+ (1 - -f(az))
2
(7) -24 24 (2 + +222) )²)
(1
<3p(a2)
+ 24
24
2
2
2
(1)
<8p(az)
(2
2
3p(a2)
B
4
4
N
Also, we have
-B,,)(()))(( fi)) (1(T2) ((ai)Si(ar) (a())/ m(a2)5i(u2))
=m(())(({(02) (1((11)
NA A.
CD(T2, f2) -B,lf2(TT) fe(a]] =2((T2) ((a1) (a1) ((a2))f((2))
=m(an)(f2(aa) fa(a1)) 1 N A.
and
BE f1) = (8p(T1 f1) B3((22)
B1((2)
4 B
(T, f2) = (8p ( f2) S
N
Since 3/N > A, we can obtain that LD f1) + (ED f1) (2) f2), which
implies that _ S2. Finally, note that
CD fT2) CD(T2, fe)
2 NA [CD(TT1, fT
we have A Therefore, for any a > 1/2, there exists an instance s.t. ATAC cannot achieve the optimal rate O(1/VN). In particular, when 3 ((N2/3), we have J(m1) ( A 1/1
π2 by ATAC algorithm. Note that J(m)) J( r(m) r(T2) A > ((I/N).
E.2 Complementary lemma
Lemma 6 (Anti-come concentration of Binomial distribution, adapted from Proposition 7.3.2 of Matoušek and Vondrák (2001)). Let Bin(n, 5) be a binomial random variable with mean μ !! Then
we have that for any E [0, } and universal constants C1 C2.
Pr(X 2 μ + 2 e Pata
F Additional Experimental Details and Results
F1 More implementation details
Our implementation is nearly identical to ATAC, except that we use a different regularizer for the critic. More details can be found in Cheng et al. (2022).
22

---

walker2d-med
wallke2d--me--rplaay
walker2d-med-ee
ACrab
ACrab
ACrabo
steps
steps
steps
(a) walker2d-med
(b) walker2d-med med-laplay
(c) walker2d-med-exy
halfcheetah-rand
haffcheetah-med
haffcheetah-med-exp
ATAC
ACrab
returm
retum
ATAC
ATAC
ACrab
ACrab
10
(x 10"3)
steps (x 10"3)
(d) halfcheetah-rand
(e) halicheetah-med
(1) halfcheetah-mmed-cy
hopper-rand
hopper-med
hopper-med-replay
ATAC
ACrab
retur
ATAC
ATAC
ACrab
steps (x 10"3)
steps (x 10"3)
steps Ix 10"3)
g hoper-rand
(h) hopper-med
hopper-med-rephe
Figure Comparison of A-Crab and ATAC in more different settings.
F22
Comparision of A-Crab and ATAC in different settings
In this section, we show comparisons of A-Crab and ATAC more different settings in Figure
F33
Value of 8 and C.c for each setting
In this section, we show our choices of 8 and Coc for each setting in Table F3 Note that we directly choose the same value as in ATAC, and select Co by grid search over
{1, 2, 5, 10, 20, 50, 100, 200}.
23

---

Table 2: Choices of /3 and Coc for each setting. The value of is the same in ATAC CCheng et al. 2022) and Coo is chosen by grid search.
8
Coc
walker2d-ramdom
64
50
walker2d-mmdium
64
1
walker2d-mediim--rppay
64
5
wallerr2l-medium--xpprr
64
2
hupper-random
64
2
hopper-medium
64
1
repper-
16
hopper--medium-exppert
halfcheetah-random
16
10
1
halfcheetah- medium-replay
2
halfchhetah-mmciiu---eyyy mediim-expperr
0.062
5
24


Reviews:
[{"review_id": "INKdJ0vFdb", "reviewer": "Reviewer_W5Wf", "summary": "This paper proposes a novel algorithm called A-Crab (Actor-Critic Regularized by Average Bellman Error) for offline reinforcement learning (RL) in complex environments with insufficient data coverage. The algorithm combines the marginalized importance sampling framework with the actor-critic paradigm and addresses the challenges of handling high-dimensional observations and minimal data coverage. The paper presents sufficient theoretical analysis to demonstrate the advantages of the proposed algorithm over existing methods.", "questions": "- There seems to be a lack of comparison between $C_{\\text{bellman}}$ and $C_{l_2}$ : How to show $C_{l_2}$ is a weaker assumption than $C_{\\text{bellman}}$?\n- How can the A-Crab algorithm shed light on the design of practical algorithms?", "limitations": "References\n\n[1] Kumar, Aviral, Abhishek Gupta, and Sergey Levine. \"Discor: Corrective feedback in reinforcement learning via distribution correction.\" Advances in Neural Information Processing Systems 33 (2020): 18560-18572.\n\n[2] Liu, Xu-Hui, et al. \"Regret minimization experience replay in off-policy reinforcement learning.\" Advances in Neural Information Processing Systems 34 (2021): 17604-17615.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper proposes a novel algorithm that combines various techniques to address the challenges of offline RL in complex environments. The use of marginalized importance sampling and the average Bellman error regularization in the critic's objective are innovative and practical.\n- The theoretical analysis provides insights into the statistical properties of the proposed algorithm, with a focus on achieving the optimal statistical rate in converging to the best policy covered in the offline dataset.\n- The paper provides a comparison with existing provable offline RL algorithms, highlighting the strengths and advantages of the proposed A-Crab algorithm.\n", "weaknesses": "- The paper provides no empirical evaluations or demonstrations of the proposed algorithm. Neither does it shed light on the design of practical algorithms.\n- There remain some issues unsolved in the paper. See the questions for details.\n- Some related works [1,2] use a similar optimization problem as Eq. (2) and also focus on computing an prioritization weight $w$ for Bellman error. They should be cited and discussed.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the helpful and insightful comments. Below are our responses.\n\n>The paper provides no empirical evaluations or demonstrations of the proposed algorithm. Neither does it shed light on the design of practical algorithms.\n\nWe showed empirical evaluation results to demonstrate that our A-Crab algorithm is practical. See the “global” response for details.\n\n>There seems to be a lack of comparison between $C_{bellman}$ and $C_{\\ell_2}$:  How to show $C_{\\ell_2}$ is a weaker assumption than $C_{bellman}$?\n\nIn Figure 1, page 3 of the paper, we provided an intuitive comparison of $C_{bellman}$ and $C_{\\ell_2}$, where for any fixed policy $\\pi$, $C_{\\ell_2}$ remains unchanged while $C_{bellman}$ goes larger as the function class $\\mathcal{F}$ gets richer. When $\\mathcal{F}$ is extremely expressive, $C_{bellman}$ can be as large as $C_{\\infty}$ and thus can be much larger than $C_{\\ell_2}$. For an arbitrary $\\mathcal{F}$, it is hard to compare $C_{bellman}$ and $C_{\\ell_2}$. However, they are both smaller than the previously widely-used coverage notion $C_{\\ell_\\infty}$.\n\n>Some related works [1,2] use a similar optimization problem as Eq. (2) and also focus on computing an prioritization weight $w$ for Bellman error. They should be cited and discussed.\n\nThanks for pointing out. We will cite these two related works and add a discussion.\n"}, {"review_id": "YjmfYWLe5M", "reviewer": "Reviewer_PQdU", "summary": "The paper introduces A-Crab, which combines marginalized importance sampling with the actor-critic paradigm to achieve optimal statistical rate in offline RL. Fm theoretical analysis, this algorithm is also more computationally efficient and relies on a weaker average notion of policy coverage compared to prior work.", "questions": "1. In Line 224, where does the overestimation come from? Please provide clarification.\n2. In Line 248, why does ATAC need to optimize two functions, f and g? The previous mention in Line 214 only refers to f.\n3. In Line 280, how does the theorem also demonstrate robustness against model mismatch? Please elaborate on this point.", "limitations": "Please refer to the weaknesses section.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written, effectively summarizing prior work and building upon it to propose the new algorithm. The notations are clear and consistent.\n2. The algorithm itself exhibits strong theoretical properties, such as optimal statistical rate and efficiency, making it promising for offline RL problems.\n\n", "weaknesses": "1. The empirical evaluation of the algorithm is a major concern. Since the theory only requires general function approximators, the gap between theory and practice may not be substantial. Experimental results help demonstrate the algorithm's effectiveness on computation cost and learning speed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the helpful and insightful comments. Below are our responses.\n\n>The empirical evaluation of the algorithm is a major concern.\n\nWe provided empirical results to demonstrate the algorithm’s effectiveness. See the “global” response for details.\n\n>In Line 224, where does the overestimation come from?\n\nThe overestimation is caused when directly using the empirical version $\\mathbb{E}\\_{\\mathcal{D}} \\left[(f(s,a)-r - \\gamma f(s', \\pi))^2\\right]$ to estimate the term $\\mathbb{E}\\_\\mu [((f - \\mathcal{T}^\\pi f)(s,a))^2]$. To better illustrate, we use a simpler example. Assume there are two random variables $X$, $Y$, and we want to estimate \n$\\mathbb{E}[ ( X - \\mathbb{E}[Y|X])^2]$ \n(note that $\\mathcal{T}^\\pi f(s,a)$ is also an expectation conditioned on $f(s,a)$). If we have $n$ samples of $(X\\_i, Y\\_i)$ pairs, and directly use $\\frac{1}{n}\\sum\\_{i=1}^n (X\\_i - Y\\_i)^2$ as an empirical estimator, then it is an overestimation of $\\mathbb{E}[(X - \\mathbb{E}[Y|X])^2]$ since $\\mathbb{E}[\\frac{1}{n}\\sum\\_{i=1}^n (X\\_i - Y\\_i)^2] = \\mathbb{E}[(X-Y)^2] \\geq \\mathbb{E}[(X-\\mathbb{E}[Y|X])^2]$. This is essentially the same as the overestimation in Line 224.\n\n>In Line 248, why does ATAC need to optimize two functions, f and g? \n\nThis is highly related to the previous question. The reason ATAC needs another function $g$ is to address the overestimation issue. As we already discussed, $\\mathbb{E}\\_{\\mathcal{D}} \\left[(f(s,a)-r - \\gamma f(s', \\pi))^2\\right]$ is an overestimate of $\\mathbb{E}\\_\\mu [((f - \\mathcal{T}^\\pi f)(s,a))^2]$, and the amount of the overestimation is roughly equal to $\\min\\_{g \\in \\mathcal{F}} \\mathbb{E}\\_{\\mathcal{D}} \\left[(g(s,a)-r - \\gamma f(s', \\pi))^2\\right]$. Therefore, one should use  $\\mathbb{E}\\_{\\mathcal{D}} \\left[(f(s,a)-r - \\gamma f(s', \\pi))^2\\right] - \\min\\_{g \\in \\mathcal{F}} \\mathbb{E}\\_{\\mathcal{D}} \\left[(g(s,a)-r - \\gamma f(s', \\pi))^2\\right]$ as an unbiased estimator as also mentioned in Line 225 and 226.\n\n>In Line 280, how does the theorem also demonstrate robustness against model mismatch?\n\nIn Theorem 1, the upper bound of the suboptimality contains a term $C^\\star_{\\ell_2} \\sqrt{\\epsilon_\\mathcal{F}}$ where $\\epsilon_\\mathcal{F}$ quantifies the model mismatch, which is defined in Assumption 1 (Line 137). Note that when $\\epsilon_\\mathcal{F} = 0$, there is no model mismatch; when $\\epsilon_\\mathcal{F} > 0$, the additional suboptimality caused by model mismatch is at most $C^\\star_{\\ell_2} \\sqrt{\\epsilon_\\mathcal{F}}$, which means that our algorithm is robust against model mismatch.\n"}, {"review_id": "zrNQLIHko2", "reviewer": "Reviewer_htrq", "summary": "The paper proposes an offline reinforcement learning algorithm called Actor-Critic Regularized by Average Bellman error (A-Crab). A-Crab modifies the pessimistic offline RL framework by replacing the usual squared TD error with an importance sampled TD error. Due to the linearity of the importance sampled TD error, overestimation does not occur, allowing the removal of the correction term. A-Crab achieves the optimal suboptimality rate with weaker assumptions and is computationally efficient. An improvement over the behavior policy is also guaranteed under a wide range of hyperparameters.", "questions": "Line 70 states that the A-Crab enjoys an optimal statistical rate of $1/\\sqrt{N}$. Does this mean the optimality of $O(1/\\sqrt{N})$ is theoretically proved? Or does this just mean that it is the best suboptimality rate to be discovered?", "limitations": "The authors do not address the limitations of their work. Assumptions on the finiteness of the action space, the policy space, the importance sampling weight function space, and the value function space can be viewed as limitations of this work. I believe this work does not have a potential negative societal impact.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "### Originality\nThe authors introduced a novel technique using the importance sampled TD error instead of the squared TD error. Due to its linearity, the correction for overestimation is unnecessary, allowing better suboptimality bounds and weaker assumptions. The analysis also becomes very simple with the help of Cauchy–Schwarz inequality.\n### Quality\nI could not find any technical flaws in the arguments presented in the paper.\n### Clarity\nThe paper is overall well-written and easy to understand.\n### Significance\nA-Crab achieves the optimal statistical rate of $1/\\sqrt{N}$ with assumptions that are weaker compared to other provable offline RL algorithms. Also, using importance sampling instead of squaring can be useful in areas other than offline RL theory.", "weaknesses": "1. The authors unrealistically assume the action space, the policy space, the importance sampling weight function space, and the value function space to be finite.\n2. Experimental verification of the performance bounds on a simple toy example would be interesting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the helpful and insightful comments. Below are our responses.\n\n>The authors unrealistically assume the action space, the policy space, the importance sampling weight function space, and the value function space to be finite.\n\n\nThe finite cardinality assumption on all the above function classes was made only for convenience. Actually, we can instead replace the finite cardinality assumption with the bounded log covering-number assumption. The replacement is straightforward and is basically the same as Appendix B in [1].\n\n>Experimental verification of the performance bounds on a simple toy example would be interesting.\n\nWe included experimental verification in the “global” response.\n\n>Line 70 states that the A-Crab enjoys an optimal statistical rate of $1/\\sqrt{N}$. Does this mean the optimality of \n$O(1/\\sqrt{N})$ is theoretically proved? Or does this just mean that it is the best suboptimality rate to be discovered?\n\nAn $O(1/\\sqrt{N})$ rate is the best one can hope in terms of $N$, and this is due to the intrinsic statistical error. For example, when we want to estimate the expectation of a random variable $X$ using $N$ i.i.d. samples $X_1, \\ldots, X_N$, with constant probability, $|\\bar X - \\mathbb{E}[X]| \\geq \\Omega(1/\\sqrt{N})$ where $\\bar X = \\frac{1}{N} \\sum_{i=1}^N X_i$ is the empirical mean. This means the best rate of error one can hope is $O(1/\\sqrt{N})$. Similarly, it can be proved that there is a lower bound $\\Omega(1/\\sqrt{N})$ of the suboptimality of the learned algorithm, which means $O(1/\\sqrt{N})$ is optimal in terms of $N$.  \n\n**References:**\n\n[1] Cheng, C. A., Xie, T., Jiang, N., & Agarwal, A. (2022, June). Adversarially trained actor critic for offline reinforcement learning. In International Conference on Machine Learning (pp. 3852-3878). PMLR.\n"}, {"review_id": "NB5fHM4mnH", "reviewer": "Reviewer_22cc", "summary": "This paper introduces A-Crab, an offline RL algorithm derived from ATAC, which incorporates a modified loss function for the Q-function. Instead of employing the square Bellman error used in ATAC, A-Crab utilizes the importance-weighted Bellman error. With this modified loss function, A-Crab effectively addresses some disadvantages of ATAC. These include alleviating the visitation coverage assumption, enhancing the suboptimality rate, and simplifying the minimax optimization process. Additionally, A-Crab inherits several benefits from ATAC. Theoretical findings presented in this paper demonstrate the superior advantages of A-Crab in comparison to ATAC.", "questions": "1. [Regarding Weakness 1] Would it be possible for you to present empirical results on D4RL datasets that compare the performance of A-Crab with that of ATAC?", "limitations": "The only limitation of this paper is the absence of empirical results. However, the implementation of A-Crab appears to be relatively straightforward, as it can be achieve by replacing the squared Bellman error in ATAC's implementation with the importance-weighted averaged Bellman error. Given that the implementation of ATAC is already available on GitHub, there is an opportunity to enhance this paper by presenting empirical results that compare the performance of A-Crab with that of ATAC.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. This paper is well-organized, presenting a table that compares provable offline RL algorithms, outlining the key distinctions of the proposed algorithm, A-Crab, in contrast to ATAC, and highlighting the advantages brought about by these modifications.\n2. By simply incorporating the importance sampling ratio from the loss function of ATAC, A-Crab exhibits significantly improved characteristics, namely: 1) relaxation of the visitation coverage assumption, 2) enhancement of the suboptimal rate, and 3) simplification of the minimax problem into a maximization problem. These advancements result from non-trivial steps and can be accomplished by making only a few adjustments to the terms in the loss functions of ATAC.", "weaknesses": "1. Despite the noteworthy novelty of this paper in terms of presenting theoretical advantages of A-Crab, the absence of empirical results diminishes its impact. I acknowledge that it is common to solely provide theoretical results in the realm of provable offline RL. However, considering that A-Crab is built upon ATAC, which offers both theoretical and numerical results, it would be feasible to compare the performance of A-Crab with that of ATAC. I believe that including such results would significantly enhance the paper.\n2. The importance sampling ratio in offline RL can become excessively large due to the limited coverage of the state-action space in the offline dataset and substantial differences between the current policy and the dataset policy. Consequently, the A-Crab algorithm may encounter instability when attempting to learn a robust policy in practical scenarios. However, if this paper addresses this issue, it would substantially strengthen its credibility.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the helpful and insightful comments. Below are our responses.\n\n>Would it be possible for you to present empirical results on D4RL datasets that compare the performance of A-Crab with that of ATAC?\n\nYes. Please see the “global” response for details.\n\n>The importance sampling ratio in offline RL can become excessively large due to the limited coverage of the state-action space in the offline dataset and substantial differences between the current policy and the dataset policy. Consequently, the A-Crab algorithm may encounter instability when attempting to learn a robust policy in practical scenarios.\n\nNote that our algorithm only requires that the dataset covers the policy we aim to learn ( the goal policy), instead of covering all policies. In other words, we only require that the importance sampling ratio of the goal policy be bounded in a weighted $\\ell_2$ sense. It does not matter whether the current policy is well covered by the dataset or has a bounded importance sampling ratio since our algorithm does not require computing the ratio for the current policy. Also, in our practical implementation, we can avoid using the $w$ function by using a computationally more efficient approximation of the importance-weighted Bellman error (see “global” response for details).\n"}]

Author rebuttal:
We thank all the reviewers for their helpful and insightful comments. Below we first address common issues. Since all the reviewers mentioned that adding experimental results would make our theoretical results more solid and significantly enhance our paper, we compared our A-Crab algorithm to the previous ATAC algorithm on 12 Mujoco datasets (v2) from D4RL offline RL benchmark (the same as the datasets used in the ATAC paper for their main results). The attached pdf file contains plots showing the performance of ACrab and ATAC during training. Each curve is averaged over 8 random seeds (we choose 0-7 as random seeds), and each training step corresponds to a batch size of 256 (10^6 steps is roughly 1000 epochs). It shows that our A-Crab has higher returns and smaller variance (which indicates a more stable training procedure) than ATAC in various environments and has at least comparable results to ATAC for almost all environments. 

Now we discuss some details of the implementation of A-Crab. Since it is straightforward to implement our algorithm based on ATAC, and nearly all the hyperparameters we used are the same as ATAC, we mainly emphasize the difference between A-Crab and ATAC in implementation. 

Note that we only need to replace the squared Bellman error regularizer for the critic in ATAC with our proposed weighted average Bellman error regularizer. Recall the definition of our proposed weighted average Bellman error regularizer
   $\mathcal{E}\_\mathcal{D}(\pi, f) = \max\_{w \in \mathcal{W}} \left| \mathbb{E}\_\mathcal{D}[w(s,a)(f(s,a)-r-\gamma f(s',\pi))]\right|. $
Since the calculation of $\mathcal{E}\_\mathcal{D}(\pi, f)$ requires solving an optimization problem w.r.t. importance weights $w$, for computational efficiency, we choose $\mathcal{W} = [0, C\_\infty]^{\mathcal{S} \times \mathcal{A}}$, and thus

 $ \mathcal{E}\_{\mathcal{D}}^{\text{app}}(\pi, f) = C\_\infty\max$ { $  \mathbb{E}\_{\mathcal{D}}[(f(s,a)-r-\gamma f(s',\pi))\_+],  \mathbb{E}\_{\mathcal{D}}[(r+\gamma f(s',\pi)-f(s,a))\_+] $ },

where $(\cdot)\_+ = \max\$ { $\cdot, 0$ } and $C_\infty$ can be viewed as a  hyperparameter. We also observed that using a combination of squared Bellman error and our average Bellman error achieves better performance in practice, and we conjecture the reason is that the squared Bellman error regularizer is computationally more efficient and statistically suboptimal, while our average Bellman error regularizer is statistically optimal while computationally less efficient, and thus the combination of these two regularizers can benefit the training procedure. Specifically, in implementation, we choose
   $ \frac{1}{2}\left(2\mathcal{E}\_\mathcal{D}^{\text{app}}(\pi, f)  + \beta \mathbb{E}\_\mathcal{D} [((f - \mathcal{T}^\pi f)(s,a))^2] \right)$
as the regularizer, while ATAC uses  $\beta \mathbb{E}\_\mathcal{D} [((f - \mathcal{T}^\pi f)(s,a))^2]$.
All hyperparameters are the same as ATAC, including $\beta$. For the additional hyperparameter $C\_\infty$, we do a grid search on { $1, 2, 5, 10, 20, 50, 100, 200$ }.


Meta-review: Weighting the pros and cons, overall, the reviewers believe this paper should be accepted.
Decision: Accept (poster)