Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning
Authors: Andrea Zanette
Martin Wainwright
Emma Brunskill
Venue: NeurIPS 2021 Poster (2021)
Keywords: Actor-critic
batch RL
offline RL
natural policy gradient
mirror descent
pessimism
policy learning
linear value functions

Abstract: Actor-critic methods are widely used in offline reinforcement learning
practice, but are not so well-understood theoretically. We propose a new
offline actor-critic algorithm that naturally incorporates the pessimism principle, leading to several key advantages compared to the state of the art. 
The algorithm can operate when the Bellman evaluation operator is closed with respect to the action value function of the actor's policies; this is a more general setting than the low-rank MDP model. Despite the added generality, the procedure is computationally tractable as it involves the solution of a sequence of second-order programs.
We prove an upper bound on the suboptimality gap of the policy returned by the procedure that depends on the data coverage of any arbitrary, possibly data dependent comparator policy.
The achievable guarantee is complemented with a minimax lower bound that is matching up to logarithmic factors.

operate when Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning
Andrea Zanette" University of Californi, Berkeley zanette@berkeley. edu
Martin Wainwright University of California, Berkeley
wainvrigöberkeley. edu edu
Emma Brunskill Stanford University
ebrun@stanform edu
Abstract
Actor-critic methods are widely used in offline reinforcement learning practice, but are not so well-understood theoretically. We propose new offline actor-critic algorithm that naturally incorporates the pessimism principle, Icading to several key advantages compared the state of the art. The algorithm the Bellman evaluation operator is closed with respect to the action value func- tion of the actor's policies; this is more general setting than the low-rank MDP model. Despite the added generality, the procedure computationally tractable involves the solution upper bound on the suboptimality gap of the policy returned by the procedure that depends on the data coverage of any arbitrary, possibly data dependent comparator policy. The achievable guarantee is complemented with minimax lower bound that matching up logarithmic factors.
sequence of second-order programs. We prove an
Introduction
The problem learning a near-optimal policy is a core challenge reinforcement learning (RL). In many settings, beneficial be able to learn good policy using only a pre-collected set of data, without further exploration with the environment; this problem is known as offline or batch policy learning. The offline setting has unique challenges due to the incomplete information about the Markov decision process (MDP) encoded in the available dataset. For example, due to maxi- mization bias, naive offline algorithm can return a policy with a severely overestimated value. In order to avoid such undesirable behavior, researchers have introduced the idea of pessimism under uncertainty, and there now a growing literature (e.g., Liu et al. (2020); Jin et al. (20205); [Buck-] man et al. (2020); Kumar et al. (2019); KKddmbi et al. (2020); Yu et al. (2020) on different ways in which pessimism can incorporated. See Appendix for additional references and discussion of this body of work.
At high level, incorporating pessimism prevents algorithms from settling down on uncertain poli- cies whose value might be misleadingly high under the current dataset due to statistical errors. By using pessimism, uncertain policies are penalized statistical errors are returned. The principle can be implemented in at least two different ways: (a) by penalizing policies that are far from the one that generated the dataset; or (b) by penalizing the value functions of policies not well covered by the dataset. In this paper, we take the latter avenue.
such way that only those policies robust to
"This work was fully completed while Andrea Zanette was PhD candidate at Stanford University. Future updates of this work will be available https: https://aaee //arr/aaa.v.//// http:://wwwwwww/a/////////// orggabs////aeeee/ 2881/
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

1.1 Overview and our contributions
Implementing pessimism with function approximation is challenging for several reasons. First, un- certainty must be estimated with particular care. On one hand, underestimating it can fail to correct the coverage problem. On the other hand, overestimating it leads to policies that are too conserva- tive and thus underperform. Second, the incorporation of pessimism may introduce complex, higher order perturbations into the value function class handled by the algorithm. Similar issues can arise when adding optimistic bonuses in the exploration. The increased complexity of the function class often requires additional assumptions on the model, because the new class needs to interact "nicely" with the Bellman operator. Prior art pessimism with function approximation has by-passed this problem by making strong model assumptions, such as low-rank transitions/ Jin et al. (020b) or algorithm-specific assumptions Liu et al. (2020).
Actor-critic methods: Most past theoretical work on offline reinforcement learning finding with high probability the policy with the highest performance has focused on algorithms that are either model or value-based" Liu et 2020): Jiin et al. (2020b); [Buckman et al. (2020); Kidambi eet al. (2020); Yu et al. (2020); these often incorporate pessimism into the estimates of the policy performance. Actor-critic methods are hybrid class of methods that mitigate some deficiencies of methods that are either purely policy or purely value-based Konda and Tsitsiklis 20000 2003);;
Heess al. (2015); Haarnoja et al. (2017) 2018;; in modern RL, they are widely used in practice (e.g.]Leviie et ( Wu et al. 2019 2021] Kumar et al. (2019) 2020). An actor-critic method generally consists of an actor that changes the policy in order maximize its value as estimated by the critic. Given their popularity, is natural to ask the following question: do actor-critic methods provably offer any advantage in offline RL? The main contribution of this paper is to give a positive answer to this question: by separating the policy optimization from the policy evaluation, both tasks become simpler to design and the pessimism principle can be incorporated more naturally.
Contributions: More specifically, we study the problem of policy learning using linear function approximation in the offline setting. We assume that we are given a batch data set D, in which each sample consists of a quadruple. The first two components to the state in which a given action was taken, and the last two components correspond to a noisy observation of the reward, and successor state drawn from the appropriate transition function. Our theory allows for a very general dependence structure among the the state-action pairs in these samples; when the data is ordered according how the samples were collected (which need not be related to a trajectory), we allow the state-action pair at any given instant to depend on all past samples. This set-up allows from data collected from arbitrary policies, mixtures of policies, generative models or even in adversarial manner.
the state-action pair, corresponding
Given such data set, our objective is to find the policy that performs best in the face of uncertainty. In particular, we need to account for the fact that the optimal policy x¹ for the underlying MDP may not be well covered by the dataset D, in which case the associated uncertainty would be prohibitive. In order to achieve this goal, we design an actor-critic procedure that iteratively optimizes a lower bound on the value of the optimal policy. Suppose that function at some given initial $1- Our strategy works as follows: for any given policy ग, we construct family M(T) of "statistically plausible" MDPs, and use them to define a simple second-order cone program. By solving this convex program, we obtain value function estimate Vās (s1) = arg Min VTT (s1) that-for an appropriately constructed family M(r)-is guaranteed be a lower bound on the true value function of π in the unknown MDP that generated the dataset. Given a procedure for producing such lower bounds, it is then natural to maximize these lower bounds over some family II of policies. This combination leads to the saddle- -oint problem
interested in optimizing the value
max min (s1). TEll MEM(=)
(1)
Note that actor-critic methods fit naturally in this framework: the critic provides pessimistic eval- uation of any given policy म, and the actor solves the outer maximization problem over policies.
2 Exceptions to this include importance sampling based approaches to selecting among a finite set of policies (e.g. Mandel et al. 4 Thomas et al. (2015) 2019)): however, such approaches have focused on operating without a Markov assumption and inherently provide much looser guarantees than the ones we and others consider for the Markov setting.

---

This decoupling lends itself to computationally tractable implementation. along with an analysis of the procedure. particular, we show that the actor's sequence of estimated policies enjoys online learning-styll guarantees with respect to sequence of pessimistic MDPs implicitly identified by the critic.
The way in which we introduce pessimism is a second key component of the algorithmic framework. In particular, in line with our previous paper Zanette al. (2020b), we do without enlarging the prescribed classes of functions and policies. We do so by a direct perturbation of the value functions examined by the critic; there is no addition of pessimistic bonuses or absorbing states. Since the class of value functions is not altered, this method has two main advantages. First, there are no additional model assumptions compared the standard -tar non- pon--pesimistic-weeee
of the actor-critic method. Second, the complexity of the underlying classes is not increased. thereby allowing us to construct tight confidence intervals and estimation error bounds that are minimax optimal up to logarithmic factors.
The remainder of this paper is organized as follows. We begin in Section 2 with background on MDPS, and then introduce the modeling assumptions that underlie the analysis of this paper. In Section 3 we introduce the algorithm studied in this paper, namely the Pessimistic Actor Critic for Learning without Exploration (for short, PACLE) algorithm. Section 4 provides statements of our main results and discussion of their consequences, including an upper bound on the PACLE algorithm in Theorem []] and a minimax lower bound in Theorem 2 In Section A we provide an outline of the proof of Theorem [I] with various technical details as well as the proof of Theorem deferred to the appendices. We conclude with a discussion in Section 5
1.2 Notation
For the reader's 's convenience, we summarize here some notation used throughout the paper. We let (a(r) = {a E Rd ||>||| I r denote the Euclidean ball of radius r E R in dimension d; we simply write B when there is no possibility of confusion. For vector x IRd, we use [ar]; to denote its gth component. We use the notation to denote an upper bound that holds up to constants and log factors in the input parameters (,, d, H). The notation means an upper bound that holds up to constant, with an analogous definition for Z.
Background and problem formulation
We begin by providing some background, before introducing the assumptions that underlie our problem formulation.
2.1 Markoy decision processes
In this paper, we focus on finite-horizon Markov decision processes, for which we provide a very brief introduction here. See the books Puterman| 1994); Bertsekas and Tsitsiklis (196)); Bertsekas [19ttc and Barto (018)) for more background and detail. A finite-horizon MDP is specified by positive integer H. and events take place
sequence of stages indexed by the time step [H] def {l,..., H). The underlying dynamics involve state space S, and are controlled by actions that take values some action set A. In this paper, we allow the state space to be arbitrary (continous discrete), whereas analysis applies to discrete action spaces. For each time step E [H] there is a reward function FΛ : SS x A + R, and for every time step h and state-action transition function F- 8, a). When horizon h, if the agent takes action
pair (s, a), there in state 8, it receives a random reward drawn from a distribution [s, a) with mean rn (s, a), and it then transitions randomly
state s+ drawn from the transition function (. 8, s,a).
A policy n at stage h is a mapping from the state space S to the action space A. Given a full policy (TT (T....... TH), the state-action value function at time step f is given by
H
(s, a) (s) + (
Σ
re(Se, (S)),,
(2)
(=++1
where the expectation over the trajectories induced by и upon starting from the pair (s, a). When omit the starting state-action pair (s, a), the expectation is intended to start from fixed state
3

---

where is the total sample size. For each [n] {1, 2, ............ ...., the tuple (8,, az) corresponds to a state-action pair associated with some time step h4- We let Fj be the o-field generated by the denoted by The value function associated to is (s) = (s)) For given policy ;, we define the Bellman evaluation operator
Th (Q,+1)(s, a) (n a) + (s. Ba Q h (S', A').
Under some regularity conditions Pattnnssstttnnnnnt (1994): Shreve and Bertsekas (1978), there always exists an optimal policy x² whose value and action-value functions are defined as
(s) V (s) sup VĀ (s), and (%(s.a) = Q% (s, sup (s.a).
2.2 Assumptions on data generation
In this paper, we study a model in which we observe a dataset of the form D (88, 04, Tiy & ))
samples {(s}, az. ry, 3)) that are the "past" relative index i. With this notation, we impose
the following condition:
Assumption 1 (Data generation). For each i E [n], the pair (st, ai) is measurable with respect to Fi Conditionally on a given pair (s), the random variable rs is drawn from a reward distribution Ra, (8i, 0z) that is I-sab-Gaussian; and the next state 8; drawn from the distribution Ph; (8i, ai).
Note that the measurability condition allows the choice of (st, a,) to depend arbitrarily on any of the past data with indices j < i. The mild assumption allows for considerable freedom. For example, the state-action pairs may be chosen from (mixture) policies, or they can be generated by an adversarial procedure that changes the data acquisition strategy as feedback is received.
For each h E [ we let I, denote the subset of observation indices i E [m]] such that h; = h. These index sets define the sub-datasets Dn, {(s;, ag Ti, s i E ],} associated with all samples that based on state-action pairs at time step h. We define ni, = [Dr]. so that our total sample size can H
be written
Eh=1 Tif-
2.3 Policy and function classes
Next we define the policy space II and the action value function space Q over which we seek solutions. Let é A Rd be a d-dimensional feature mapping. We assume throughout that these feature mappings are normalized such that [|o(s,a)llz < 1 uniformly for all (s, a)-pairs. We consider action-value functions that are linear in @, and families of the form
2("") def {(s,a) (ő(s, w)
||l|2 S p').
(3a)
where pd E (0, 1] is a user-defined radius. For policies, we consider the associated loft-max class
((M())) 8) e(o(s,a))0)
[po) def
[10||2 S pp"
(3b)
Σ BEA
where p² > 0 is second radius.
In the context of our actor-critic algorithm, the weight radius n remains fixed for all updates. On the other hand, the actor produces a sequence of soft-max radii {e] [ indexed by the iterations & of the actor. This sequence is produced via the update rule in Line 5 of Algorithm The policy radius can be large p" > 1 but we constrain pd < 1 so that the critic's s estimate Qw = (ø(s, a), w) bounded by one. i.e., sup(s.a, w) (s, a)l 1.
Recall that our MDP consists of sequence of H distinct stages. Our algorithm and theory allows for the possibility of different feature extractors at each step h [H], even with possibly differ- ent dimensions. Consequently, in implementing and analyzing the algorithm, there are actually H (possibly different) functional spaces !H { along with the associated soft-max policy classes (TT, ) So as to simplify notation, we drop the dependence on the radii when referring to the functional spaces, and implicitly assume that the terminal value function is zero.

---

2.4 A range of function class assumptions
In this section, we discuss a range of assumptions that might be imposed on class action- value functions. This discussion serves as motivation for the particular assumption (Bellman restricted closedness-cff Assumption 3 that underlies our analysis.
We begin with the least restrictive condition, which is very natural starting point in our given set-up. If seek to find the policy т E with the highest value function, seems reasonable to require that the following representation condition (approximately) holds.
Assumption (Linear action-value functions )*), The MDP admits a linear action-value function representation for all policies II, meaning that for each policy æ II and time step h. [H] there exists vector Wh such that
(7, (sn(s, w.)
(4)
This assumption alone turns out to be inadequate to ensure that effective learning is possible; indeed, the recent papers Zanette| (2020); Weisz al. (2020) establish that even under this con- dition, there are instances that require exponentially many samples to do better than a random policy.
Given this fact, if one is interested in procedures with polynomial complexity (in both sample size and running time), stronger conditions need be imposed. In general, the Bellman evaluation operator, even when applied to linear action-value function, will return a nonlinear value function. The analysis of this paper is based on bounding the Bellman error in the sense sup-norm deviation from linearity:
Assumption 3 (Bellman Restricted Closedness). The policy and value function spaces (II, Q) are closed up to V E R error in the sup-norm if there a non-negative sequence {vr}-= such that
for each h E [H), we have
sup 1 QuEO. 1h
inf 11Qh TT Qutilloo v/.
(5)
The restricted closedness assumption measures how well can fit the action-value function resulting from the application the Bellman evaluation operator to an action value function Q and for policy in II. It enables the analysis of least-squares policy evaluation (e.g.. Nedić and Bertsekas (003)), which will be our starting point when constructing the critic.
Finally, for understanding connections to past work, relevant to compare to the low-rank MDP assumption that has been analyzed in recent work Jin et al. (2020a): Yang and Wang (2020), in- cluding in offline RL. with pessimismistic guarantees et al. (2020b), well in various online settings Agarwal et al. (2020a); Modi et al. (202I); Zanette al. (2020a).
Assumption 4 (Low-Rank MDP). An MDP is low-rank if for all h E [I1], there exists reward
parameter Rd and component-wise positive mapping th S + Ri such that [| for all s E S, and
ra(s, a) = (sn a), wa).
(s' 8, a) = (on(s, a), (n(ss)))
V(s,a,h,s')
(6)
The following proposition explicates the nested relationship between these three conditions, showing that the low-rank MDP condition is the most restrictive:
Proposition 1 (Low Rank C. Restricted Closedness C Linear QT), For any fixed state-action space, horizon, and feature extractor:
(a) The class of low-rank MDPs is a strict subset of the class of MDPs that satisfy Bellman restricted closedness.
(b) The class of MDPs that satisfy Bellman restricted closedness is a strict subset of the linear Q" MDP class.
5

---

See Appendix C for the proof of this claim.
we see that any analysis based on assuming Bellman restricted closedness also fortiori applies to MDPs that satisfy the more stringent low-rank MDP condition.
Based on Proposition 1
3 The Pessimistic Actor-Critic
Given the set-up thus far, we are now ready to describe the actor-critic algorithm that we analyze in this paper. We refer to it as the Pessimistic Actor Critic for Learning without Exploration, PACLE for short. We first describe the critic Section and then the actor in Section 3.2 We summarize the actor and critic algorithms, respectively, in pseudocode form in Algorithm and Algorithm 2
3.1 The Critic: Pessimistic Least Square Policy Evaluation
The purpose of the critic is to provide pessimistic value function estimates corresponding to the policy x under consideration by the actor. Monte Carlo with importance sampling (IS) is not desir- able in this setting, as the policy distribution that generated the dataset might be unknown and estimation errors on the distribution can accumulate exponentially with the horizon in IS estima- tors (see e.g. Liu et al. (2018b)). Instead, we use least-squares temporal difference method for policy evaluation, but suitably perturbed to return pessimistic estimates- lower bounds on the true value function of the given policy и. Our method is based on directly perturbing the regression parameters in the least-square estimate. In contrast to bonus- based approaches, this method has the important advantage of ensuring that the action-valus function remains linear. The purpose of the perturbations is to compensate for possible statistical errors in estimating the regression parameter due to poor coverage of the given dataset.
Let us now give a precise description of the critic. Given policy π = (TI..... RH), the goal of the critic is to minimize the quantity
Ex'wa, (o(s1, A'), wi) Σ Ti(a s1) (0i(s), w1), aEA
which is an estimate of the value function (*1( for the policy π at the initial state 81- The parameter Wi E Rd is a vector to be adjusted, one that is determined by a backwards-running sequence of regression problems from h H down h = 1.
We introduce the pessimistic perturbations directly to the solution of these regression problems. They involve norm defined by the cumulative covariance matrix. Recall that I, indexes the subset of observations associated with state-action pairs at time step h. For each E [H] and E In- let us write the associated sample the quadruple (Shi, Ohi, This 1.+1. Introducing the shorthand notation d% = on (Shs, ans), we define the cumulative covariance matrix
Σn
def
(E )nnohhss Idxds VET
where laxd denotes the d-dimensional identity matrix. Notice that the cumulative covariance grows the number of samples in I, increases; we do not normalize it by the local sample size n, [Z,] |- so that Σn effectively represents the amount of information contained in the sub-dataset Dr. at time step h.
Since E, is strictly positive definite by construction, it defines a pair of norms
| def Vu Enu, and ||||s, def V (En)
Consider the regression problem that is solved moving backward from time step h + to h. Given the weight vector wh+11 at time step h + 1, the regularized least-squares estimate of wa is given by
def
Σ KEI.
FAk + Σ Th=i(a (al 8h+1.)) (0n+1 (S141,, a), wn+1)
wh
2
Φnk
A

---

We introduce pessimism by directly perturbing the weight vectors themselves that is, we search for weight vector Wn, such that wh. & + Wh. where the pessimism vector En I2 satisfies bound of the form 1[A,,,,, ar, for user-defined parameter on.
In detail, the critic takes input the dataset D, policy म, sequence of tolerance parameters = (a1,...,aa weight radii p" = (p'..... PH) with each Pk E (0, 1]. The optimization variables consist of the regression vectors to = (wi...., ,,) (R4) and the pessimism vectors & = (E1....,,Er) E (Rd) The critic then solves the convex program
(5"
w
def
min Σ Tiaa s1) (01(51, w1) &E(R") H WE(Rd) AEA
(10a)
with the terminal condition w#+1 +1+1=---- 0, and subject the constraints
wh = Eb + 2
Σ
Ohk
Thk + Σ
Th+i sh+1k) (dn+1 1, a), wh+1)
and
kEIA
(10b)
1E S oz
|| 12 S (o%)
(10c)
for all h E [H]. Here the matrices En were previously defined in equation 8
The convex program 100 consists of linear objective subject quadratic constraints; it a special case of a second order cone program, and can be efficiently solved with standard convex solvers.
Algorithm ACTOR (MIRROR DESCENT)
1: Input: Dataset D, starting state 81.
Algorithm 2 CRITIC (PLSPE)
learning rate 7)
1: Input: Dataset D, target policy x, start- ing state 81, critic radii {p% hh=1.... and parameters {au (oi,......
2: Set 01 (O.....
3: for = 1, 2....... do
4: W/ < CRITIC(D, mo. $1)
2: Solve the optimization program 10
5:
0.+1 = 01 + 178,
Return: Optimal weight vector w
6: end for
7: Return: Mixture policy ,0,.... T0r
3.2 The Actor: Mirror Descent
We now turn to the behavior of the actor. applies the mirror descent algorithm based on the Kullback Leibler (KL) divergence Bubeec (2014). This combination leads to the exponentiated gradient update rule in every timestep [H], so that the soft-max policy in moving from iteration I to 1. + is updated as
(a s) x (e,n(a ().a)) for each (s, S A.
(11)
Here 7) is stepsize parameter, and our theory specifies suitable choice.
the Q-value above from the critic lives in Q, then is possible to show that F1+1.hh E II, and the update rule takes much simpler and computationally more efficient form (cf. Line of Algo- rithm(I), where w, is the gradient the value function on the pessimistic MDP implicitly identified by the critic. In this case, the spaces (Q, II) are said to be compatible Sutton et al. (1999); Kakade [200[;[Agawwa: et al. (2020b); Raskutti and Mukherjee (2015) and the resulting algorithm is often called the Natural Policy Gradient (NPG) (see also Geist et al. 2019); Shani al. (2020)) By construction, the critic maintains a linear action value function even after pessimistic perturbations. As consequence, the actor policy space is the simple softmax policy class IT and the easier update rule can be used. As we explain the analysis, this has important statistical benefits.
After T rounds of updates, the mirror descent algorithm that we use here readily achieves online regret rates (in the optimization setting with exact feedback) ~ 1/T or 1/VT depending on the analysis Agarwal et al. (2020b) and the learning rate, although we mention that these rates could potentially be improved Khodadadian et al. (2021) Lan 202
Bhandari and Russo (2020).

---

Main results
We now turn to the statement of bound on the performance of the policy Talo returned by PACLE. This upper bound involves three terms: an optimization eτтоr, an uncertainty term, and model mis-specification term. The optimization error is given by C(T) def 4H V /loggA1 it captures the rate which the error decreases as function of the iterations of the actor. The siscsspccfiiatiin enror Emp()) def 2h=11 Mh is simply the sum of all the stage-wise missspecifiiation enrors; notice that the mis-specification error does depend on the choice of the radii for the critic .-.-... P'
in a problem dependent way (ef. Assumption 3 Finally, for each h, define the vector dz def As (Sh, An)], where the expectation is over the state-action (Sp, encountered at timestep h upon following policy æ. In terms of these vectors, the uncertainty error is given by
a(TTa) def 2
> on Io = 2 > as aan (0)) Σn %% 1
(12)
hm
A=1
where the cumulative covariance matrix En was defined in equation
The amount of information from the dataset D is fully encoded in the uncertainty function // through the sequence of cumulative covariance matrices {E,, H and parameters ] The more data are available, the more positive definite M' is and the smaller the uncertainty function U(;; a) becomes for a fixed policy π. If the sampling distribution that generates the dataset fixed, then we can write (((;aa) a)) & c/ / where does not depend n and can be interpreted the coverage of the sampling distribution with respect to policy т.
4.1 A guarantee for PACLE
Our main result holds under Assumption 1 on the data collection process. It is based on radii {p%) jh=1 for the action value functior that lie in the interval (0, 1], and it provides a guarantee relative to the class II of all stochastic policies.
Theorem 1 (An achievable guarantee). Suppose that we are given data set D collected in way that respects Assumption /
Then there are pessimism vectors bounded as an = =O(vd log 1/)) +
Uh y Th such that, after running T 2 log log|A) rounds of the actor with stepsize rj log |A| the PACLE procedure returns a policy TALG for which
H
(s - ViTuU( a)) +
Σ
Uh + 4H
uniformly over all π E Iaa (13)
T
1=1
Emp (M)
C(T)
with probability exceeding 1 8.
The result provides a family of upper bounds on the sub-optimality of the learned policy TaLGs indexed by the choice of comparator policy π, and embodies tradeoff between the sub-optimality of the comparator and its uncertainty U(TT; a). Note that the optimization error C(T) can be reduced arbitrarily, while a (and thus U(T; a)) increase only logarithmically with T. As a special case, if we set π s² and assume that there no mis-specification error, then we obtain that the learned policy satisfies bound of the form
VF' (s)) VITAL((s)) ((<=:a))++ CCT)
(14)
with probability at least 1 - 8. Since C(T) is well-controleed, this guarantee is satisfied whenever the uncertainty term U (T= a) is small.
More generally, the guarantee (13) is significantly stronger than most prior work as PACLE competes not just with the optimal policy but with all comparator policies simultaneously. Such compara- tor policies need not necessarily be in the prescribed policy class II. To highlight the strength of this
'This represents setting where both the reward and the value function can be as large as 1 in absolute value. One easily recovers the setting with value functions in [0, H) using rescaling argument.
8

---

generality, suppose that the uncertainty U(x;;; a:) of the optimal x² is nor small it could in fact be infinite. In this case, the bound (T4p would not be useful.
However, suppose that there exists a near-optimal molicy-meaning a policy n+ such that VT (81) N (s1( - с for some small c- e-that is well-covered by the dataset (i.e., for which U(T+;a)) R 0). this case, Theorem ensures with high probability VAAL(())) Z (ai - 6. In contrast, traditional analyses that use only the optimal policy nt as comparator- opposed to also allowing near-optimal policies policies-cannott return meaningful guarantees. We note also that the papers Yu al. (2020); Liu et al. (2200); Kidambi et al. (2020) provide results of similar flavor.
These types of guarantees are also provided by some concurrent works Uchara and Sun 2021 Xie
et al. (202I).
should also be noted that Theorem 1 provides a family of results indexed by the choice of the
critic's radii {ph / This choice is modeling decision: increasing the radii increases both the approximation power of the function class 2n used for regression, but also increases the complexity of the function class Qh-11 to represent (cf. Assumption 3 thus, the choice of the radii affects the
approximation error Emp(() in a problem dependent way.
4.2 A lower bound
Thus far, we have stated an upper bound on the quality of the returned policy for given procedure. Central this upper bound is the uncertainty function ((T;; a). In this section, we show that term of this form is unavoidable for any procedure. In particular, working within the well-specified setting, we prove lower bound in terms of the quantity (T;; vd) v vd 11 "| Recalling
that our choice of a scales with vd (along with other logarithmic factors), this lower bound shows that our result is tight up to logarithmic factors.
We show that the lower bound actually holds in setting that is easier for the learner, in the sense that (1) we restrict to low-rank MDPs, where there is no spiciipeciiiattionn error; and (2) the mechanism that generates the dataset is non-adaptive, and so certainly satisfies Assumption [
Theorem (Information-theoree theoretic lower bound). For a given horizon H and dimension d, consider sample size 2d H3 There is class M of low-rank MDPs and data generating procedure satisfying Assumption 7 such for any policy Aaa we have
sup EM MEM
(ii - V (s)) cU(TTVV)
uniformly over all π E II
(15)
where e >> 0 is a universal constant.
When H the above result gives sample complexity lower bound for learning near optimal policy from batch data in a linear bandit instance.
4.3 Comparison to related work
Theorem automatically implies the typical bound P[V/TA > (1 [(T=;;(;;;; ax) 1 1-6 6 when the comparator policy is the optimal policy π e.g., Jin et al. (2020b): Rashidinejad et al. (2021); Kidambi et al. (2020); Kumar al. (219); Buckman et al. (2020). The guarantee can (11 - C/vn where n is the number of samples and C is the (scaled) condition number of Σj," One could interpret C' as a concentrability coefficient that ex- presses the coverage of dataset dataset-througgh Σ, with respect to the average direction in feature space As)a; (Ø(S,, Ax)] of the optimal policy π². As in the paper Jin et al. (2020b), such a factor can be small even when traditional concentrability coefficients are large because they depend on state-action visit ratios (see the literature in Appendix B c.g.. Chen and Jiang 2019)).
be written as V ALG ($1) 2
With reference the results in the paper Jin et al. (2020b), our work provides improvements two distinct ways. First, their upper and lower bounds exhibit gap of the order d.H. which our analysis closes. Second, our analysis holds under the more permissive Assumption [3 3IABllmann Restricted Closednesss) which includes low-rank MDPs. Of this improvement, a factor of vd is due to the algorithm that we use, and the remainder is due to a more refined construction to certify optimality in Theorem? 2 To be clear, our upper and lower bounds differ from theirs by factor of H due to different normalization in the value function). We also note that the result of Liu et all Liu et al.

---

(2220) can be specialized to the low-rank MDP setting; however, even in this simpler setting, the results would be sub-optimal and also require additional density estimates.
Deriving a computationally tractable model-free algorithm without low-rank dynamics but subject to value function perturbations (e.g., optimistic pessimistic perturbations) is open problem even in the more heavily studied online exploration setting: there the current state-of-the art Zanette al. (2020b); Jin et al. (202T) Du et al. (202T); ; Jiang al. (2017) only present computationally intractable algorithms with the exception of Zanette et al. (2020c) for a PAC setting with low in-
herent Bellman error which however requires an additional "explorability" condition. Due to space
constraints, the proof outline is deferred to Appendix
5
Discussion
In this paper, we have developed and analyzed an actor-critic method procedure, designed for find- ing near-optimal policies the offline setting. The PACIEE procedure introduces pessimism into the critic's evaluation of a given policy's value function, thereby ensuring that, under suitable parameter choices and assumptions, it maintains (with high probability) a lower bound on the true value func- tion. The actor then performs form of mirror ascent to maximize the value of these lower bounds.
An important feature of our method is that it introduces pessimism via direct perturbations of the pa- rameter vectors in linear function approximation scheme. In this way, we avoid having to impose additional model assumptions; moreover, the pessimism does not substantially increase the com- plexity of our under value/policy classes, which allows us to provide minimax-optimal guarantees. We note that similar approaches have appeared before in the exploration setting; for example, see the recent papers Zanette et al. (020b); JJin et al. 2: Du et al. (202T). These methods enjoy similar advantages in terms of theoretical guarantees, but at the expense of computational tractability. In contrast, the method of this paper entails solving low-dimensional second-order cone program, a simple class of convex programs for which there exist many polynomial-time algorithms. We enjoy this advantage due to some key differences between the offline and online settings of RL. In the offline setting, it is possible to keep the actor's update cleanly separated from the evaluation step of the critic, as we have done here; this separation underlies the computational tractability.
Our work leaves open number of interesting questions for future work. First, it would be interesting to provide some numerical studies of the PACLE'S performance, so as understand its practical behavior relative to the theoretical guarantees provided here. Also, our analysis here has focused purely on approximation using linear basis expansions; extension to more general function classes is an important next step. Finally, it will be interesting to see to what extent these ideas can be translated to the more challenging setting of exploration.
Acknowledgements
This work was partially supported by NSF-DMS grant 2015454, NSF- grant 1909365, and NSF- FODSI grant 2023505 to MJW, a Stanford Artificial Intelligence Laboratory Toyota gift to EB, and a Office of Naval Research grant N000041--0001--18--1 1--6-- to MJW.
References
Abbasi- Yadkori, Y., Pal, D., and Szepesvari, C. (2011). Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems (NIPS).
Agarwal, A., Kakade, S., Krishnamurthy, A., and Sun, W. (2020a). Flambe: Structural complexity and representation learning of low rank mdps. arXiv preprint arXiv:2006. 10814.
Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan. G. (2020b). Optimality and approximation with policy gradient methods in markov decision processes. In Conference on Learning Theory, pages 64-66.
Agarwal, R., Schuurmans, D., and Norouzi, M. (2020c). An optimistic perspective on offline rein- forcement learning. In International Conference Machine Learning, pages 104-114. PMLR.
10

---

Antos, A., Munos, R., and Szepesvári, C. (2007). Fitted q q-iteration in continuous action-space mdps.
Antos, A., Szepesvári, C., and Munos, R. (2008), Learning near-optimal policies with bellman- residual minimization based fitted policy iteration and single sample path. Machine Learning, 71(1):89-129,
Bertsekas, D. P. (1995). Dynamic programming and stochastic control, volume 1. Athena Scientific, Belmont, MA.
Bertsekas, D. P. and Tsitsiklis, J. N. (1996). Neuro-dynamic programming. Athena Scientific.
Bhandari, J. and Russo, D. (2020). A note on the linear convergence of policy gradient methods. arXiv preprint urXiv:2007.11/20
Bubeck, S. (2014). 1r05.41405.4998.
Convex optimization: Algorithms and complexity.
arXiv preprint
Buckman, J., Gelada, C., and Bellemare, M. G. (2020). The importance of pessimism in fixed- dataset policy optimization. arXiv preprint arXiv:2009.06799
Chen, and Jiang, N. (2019). theeooicio considerations in batch reinforcement learning. In International Conference on Machine Learning, pages 1042-1051.
de Pena, V. H., Lai, T. L., and Shao, Q M. (2009). Self-normalized processes. Springer.
Du, S. S., Kakade, S. M., Lee, J. D., Lovett, S., Mahajan, G., Sun, W., and Wang, R. (2021). Bilinear classes: A structural framework for provable generalization in rl. arXiv preprint arXiv:2103.10897
Duan, Y., Jin, C., and Li, Z. (2021). Risk bounds and rademacher complexity in batch reinforcement learning. arXiv preprint arXiv:2103.13883
Duan, Y. and Wang, M. (2020). Minimax-optimal off- aff-policy evaluation with linear function approx- imation. arXiv preprint arXiv:2002.09576.
Fan, J., Wang, Z., Xie, Y., and Yang, Z. (2020). A theoretical analysis of deep q-learning. In Learning for Dynamics and Control, pages 489-489. PMLR.
Farahmand, A.mm., Ghavamzadeh, M., Szepesvári, C., and Mannor, S. (2016). Regularized pol- icy iteration with nonparametric function spaces. The Journal of Machine Learning Research, 17(1):4809-488 4874.
Farahmand, A.m.., Szepesvári, C., and Munos, R. (2010). Error propagation for approximate policy and value iteration. In Advances in Neural Information Processing Systems (NIPS).
Farajtabar, M., Chow, Y., and Ghavamzadeh, M. (2018). More robust doubly robust off-policy evaluation. In International Conference Machine Learning, pages 1447-1456. PMLR.
Fu, Z.,, Yang, Z., and Wang. 7. (2020). Single-timescale actor-critic provably finds globally optimal policy, arXiv preprint arXiv:2008.000 00483.
Geist, M.. Scherrer, B., and Pietquin, O. (2019). A theory of regularized markov decision processes. In International Conference on Machine Learning, pages 2160-2169. PMLR.
Haarnoja, T., Tang, H., Abbeel, P., and Levine, S. (2017). Reinforcement learning with deep energy- based policies. In International Conference Machine Learning, pages 1352-1361. PMLR.
Haarojja, T., Zhou, A., Abbeel, P., and Levine, S. (2018). Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor.
Hao, B., Ji, X., Duan. Y., Lu, H., Szepesvári, C., and Wang, M. (2021). Bootstrapping statistical inference for off off-policy evaluation. arXiv preprint arXiv:2102.00 03.00007
Heess, N., Wayne, G., Silver, D., Lillicrap, T., Tassa, Y., and Erez, (2015). Learning continuous control policies by stochastic value gradients.

---

Jaques, N., Ghandeharioun, A., Shen, J. H., Ferguson, C., Lapedriza. A., Jones, N.. Gu, S., and Pi- card, R. (2019). Way ofl-po batch deep reinforcement learning of implicit human preferences in dialog. arXiv preprint arXiv: 2ttv:/900.000 004.00
Jiang, N. and Huang. J. (2020). Minimax value interval for off off-policy evaluation and policy opti- mization. arXiv preprint arXiv:2002.02081.
Jiang, N., Krishnamurthy, A., Agarwal, A., Langford, J., and Schapire, R. (2017). Contextual decision processes with low Bellman rank are PAC-learnable. In Precup, D. and Teh, Y. W., editors, International Conference on Machine Learning (ICML), volume 70 of Proceedings of Machine Learning Research, pages 1704-1713, International Convention Centre. Sydney, Aus- tralia. PMLR.
Jiang, N. and Li, L.. (2016). Doubly robust off-policy value evaluation for reinforcement learning. In International Conference on Machine Learning, pages 652-661. PMLR.
Jin, C., Liu, Q. and Miryoosefi, S. (2021). Bellman eluder dimension: New rich classes of problems, and sample-efficient algorithms. arXiv preprint arXiv:2102.00815
Jin, C., Yang, Z., Wang, Z., and Jordan, M. I. (2020a). Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory.
Jin, Y., Yang, Z., and Wang, Z. (2020b). Is pessimism provably efficient for offline rI? arXiv preprint arXiv:2012.15085.
Kakade, S. M. (2001). natural policy gradient. Advances in neural information processing sys- lems, 14.
Kakade, S. M. et al. (2003). On the sample complexity of reinforcement learning. PhD thesis, University of London London, England.
Kallus, N. and Uehara, M. (2019). Efficiently breaking the curse of horizon in off-policy evaluation with double reinforcement learning. arXiv preprini (909:0/990.05580
Khodadadian, S., Jhunjhunwala, P. R., Varma, S. M., and Maguluri, S. T. (2021). On the linear
convergence of natural policy gradient algorithm. arXiv preprint arXiv:2105.01224.
Kidambi, R., Rajeswaran, A., Netrapalli, P., and Joachims, T. (2020). Morel: Model- offline reinforcement learning. arXiv preprint arXiv:200S.0599
Konda, V. R. and Tsitsiklis, N. (2000), Actor-critic algorithms. In Advances in neural information processing systems, pages 1008-1014.
Konda, V. R. and Tsitsiklis, J. N. (2003). On actor-critic algorithms. SIAM Jour. Opt. Control, 4234):1143-1166.
Kumar, A., Fu, J., Tucker, G., and Levine, S. (2019). Stabilizing off-policy q-learning via bootstrap- ping error reduction. arXiv preprint arXiv: 0060009499
Kumar, A., Zhou, A., Tucker, G., and Levine, S. (2020), Conservative q-learning for offline rein- forcement learning, arXiv preprint 047779.006.0777.
Lan, G. (2021). Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. arXiv preprint arXiv:2102.00135.
Laroche, R., Trichelair, P., and Des Combes, R. T. (2019). Safe policy improvement with baseline bootstrapping. In International Conference Machine Learning, pages 3652-3661. PMLR.
Levine, S., Kumar, A., Tucker, G., and Fu, (2020). Offline reinforcement learning: Tutorial, review, and perspectives open problems, arXiv preprint arXiv:2005.01643.
Liao, P., Qi, Z., and Murphy, (2020). Batch policy learning in average reward markov decision processes, arXiv preprint ar71v:200..11771
12

---

Liu, Q. Li, L., Tang, Z., and Zhou, D. (2018a). Breaking the curse of horizon: Infinite-horizon pof-py estimation. In Advances Neural Information Processing Systems, pages 5356-5366.
Liu, Y. Gottesman, O., Raghu, A., Komorowski, M., Faisal, A. A., Doshi-Velez, F., and Brunskill, E. (2018b). Representation balancing mdps for off-policy policy evaluation. Advances in Neural Information Processing Systems, 31:2644-2655
Liu, Y., Swaminathan, A., Agarwal, A., and Brunskill, E. (2020). Provably good batch reinforcement learning without great exploration. arXiv preprint arXiv:2007.08202.
Mandel, T., Liu, Y-E.,, Levine, S., Brunskill, E.,, and Popovic, Z. (2014). Offline policy evaluation across representations with applications to educational games. In AAMAS, volume 1077.
Modi, A., Chen, J., Krishnamurthy, A., Jiang, NN,, and Agarwal, A. (2021). Model-free representation learning and exploration in low-rank mdps. arXiv preprint arXiv:2102.07033.
Munos, R. (2003). Error bounds for approximate policy iteration. In JCML, volume 3, pages 560- 567.
Munos, R. (2005). Error bounds for approximate value iteration. In AAAI Conference on Artificial Intelligence (AAAI).
Nachum, O., Chow, Y., Dai, B., and Li, L. (2019a). Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections. arXiv preprint arXiv:1906.04733.
Nachum, O. and Dai, B. (2020). Reinforcement learning via fenchel-rockafellaa duality. arXiv preprint arXiv:2001.01866
Nachum, O., Dai, B., Kostrikov, I., Chow, Y., Li, L., and Schuurmans, D. (2019b). Algaedice: Policy gradient from arbitrary experience. arXiv preprint arXiv:1912.02074.
Nair, A., Dalal, M., Gupta, A., and Levine, S. (2020). Accelcrating online reinforcement learning with offline datasets. arXiv preprint arXiv:2006. 09359.
Nedić, A. and Bertsekas, D. (2003). Least squares policy evaluation algorithms with linear func- tion approximation. Discrete Event Dynamic Systems, 13(1):79-110.
Puterman, M. L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., New York, NY, USA.
Rashidinejad, P., Zhu, B., Ma. C., Jiao, J., and Russell, S. (2021). Bridging offline reinforcement learning and imitation learning: tale of pessimism. arXiv preprint arXiv:2103.12022
Raskutti, G. and Mukherjee, S. (2015). The information geometry of mirror descent. IEEE Trans- actions on Information Theory, 1551:1445
Shani, L., Efroni, Y., and Mannor, (2020). Adaptive trust region policy optimization: Global convergence and faster rates for regularized mdps. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5668-5675.
Shreve, S. and Bertsekas, D. P. (1978). Alternative theoretical frameworks for finite horizon discrete-time stochastic optimal control. SIAM Journal on control and optimization, 16(6):953- 978.
Siegel, N. Y., Springenberg. J. T., Berkenkamp. F., Abdolmaleki, A., Neunert, M., Lampe, T., Hafner, R., Heess, N., and Riedmiller, M. (2020). Keep doing what worked: Behavioral modelling priors for offline reinforcement learning. arXiv preprint arXiv:2002.00 08396.
Sutton, R. S. and Barto, A. G. (2018). Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA, 2nd edition.
Sutton, R. S., McAllester, D. A., Singh, S. P., Mansour, Y., et al. (1999). Policy gradient methods for reinforcement learning with function approximation. In NIPs, volume 99, pages 1057-1063. Citeseer.
13

---

Tang, Z., Feng, Y., Li, L.. Zhou, D., and Liu, Q. (2019). Doubly robust bias reduction in infinite horizon off off-po estimation. arXiv preprint urXiv:1910.07/33
Thomas, P. and Brunskill, E. (2016). Data-efficient off-policy policy evaluation for reinforcement learning. In International Conference Machine Learning, pages 2139-2148.
Thomas, P., Theocharous, G., and Ghavamzadeh, M. (2015). High confidence policy improvement. In International Conference on Machine Learning, pages 2380-2388.
Thomas, P. S., da Silva, B. C., Barto, A. G., Giguere, S., Brun, Y., and Brunskill, E. (2019). Pre- venting undesirable behavior of intelligent machines. Science, 366966468)
Tsybakov, A. B. (2009). Introduction Nonparametric Estimation. Springer, New York.
Uehara, M., Huang, J., and Jiang. N. (2020). Minimax weight and q-function learning for off-policy evaluation. In International Conference on Machine Learning, pages 9659-9668. PMLR.
Uehara, M. and Sun, W. (2021). Pessimistic model-based offline rl: Pac bounds and posterior sampling under partial coverage.
Voloshin, C., Jiang, N., and Yue. Y. (2021). Minimax model learning. In International Conference on Artificial Intelligence and Statistics, pages 1612-1620. PMLR.
Wainwright, M. J. (2019). High-dimensional statistics: A non-asymptotic viewpoint, volume 48.
Cambridge University Press.
Wang, L., Cai, Q., Yang, Z., and Wang, Z. (2019). Neural policy gradient methods: Global optimal- ity and rates of convergence. arXiv preprint 19X1:1199..0150..
Wang, Z., Novikov, A., Zoina, K., Springenberg, J. T., Reed, S., Shahriari, B., Siegel, N., Merel, J., Gulcehre, C., Heess, N., et al. (2020). Critic regularized regression. arXiv preprint arXiv:2006.1513:
Weisz, G., Amortila, P., and Szepesvári, C. (2020). Exponential lower bounds for planning in mdps with realaaly optimal action-vales functions. arXiv preprint arXiv:2010.01.74.
Wu, Y., Tucker, G., and Nachum, O. (2019). Behavior regularized offline reinforcement learning. arXiv preprint 111.1.191..1136.
Wu, Y., Zhai, S., Srivastava, N., Susskind, J., Zhang, J., Salakhutdinov, R., and Goh, H. (2021). Uncertainty weighted actor-critic for offline reinforcement learning. arXiv preprint arXiv:2105.08144
Xie, T., Cheng, C.-A., Jiang, N., Mineiro, P., and Agarwal, A. (2021), Bellman-consistent pessimism for offline reinforcement learning.
Xie, T. and Jiang, (2020a). Batch value-function approximation with only realizability. arXiv preprint XXXv:2008.004990
Xie, T. and Jiang, N. (2020b). Q approximation schemes for batch reinforcement learning: A theoretical comparison. volume 124 of Proceedings of Machine Learning Research, pages 550- 559, Virtual. PMLR.
Xie, T., Ma. Y., and Wang, Y.-X. (2019). Towards optimal off-policy evaluation for reinforcement learning with marginalized importance sampling. In Advances in Neural Information Processing Systems, pages 9668-9673
Yang, L. and Wang, M. (2020). Reinforcement leaning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning (ICML).
Yang, M., Nachum, O., Dai, B., Li, L.., and Schuurmans, D. (2020). Off-policy evaluation via the regularized lagrangian. arXiv preprint arXiv:2007.03433.
Yin, M., Bai, Y., and Wang, Y.-X. (2020). Near optimal provable uniform convergence off-policy evaluation for reinforeement learning, arXiv preprint arXiv:2007.03760
14

---

Yin, M. and Wang, Y.-.. (2020). Asymptotically efficient off off-policy evaluation for tabular rein- forcement learning. In International Conference on Artificial Intelligence and Statistics, pages 3948-3958 PMLR.
Yu, T., Thomas, G., Yu, L., Ermon, S., Zou, J., Levine, S., Finn, C., and Ma, T. (2020). Mopo: Model-based offline policy optimization. arXiv preprint arXiv:2005. 13239.
Zanette, A. (2020). Exponential lower bounds for batch reinforcement learning: Batch can be exponentially harder than online rl. arXiv preprint arXiv:2012.08005.
Zanette, A., Brandfoobrener, D., Pirotta, M., and Lazaric, A. (2020a). Frequentist regret bounds for randomized least-squares value iteration. In AISTATS.
Zanette, A., Lazaric, A., Kochenderfer, M., and Brunskill, E. (2020b). Learning near optimal poli- cies with low inherent bellman error. International Conference on Machine Learning (ICML).
Zanette, A., Lazaric, A., Kochenderfer, M. J., and Brunskill, (2020c). Provably efficient reward- agnostic navigation with linear value iteration. In Advances in Neural Information Processing Systems.
Zhang, J., Koppel, A., Bedi, A. S., Szepesvari, C., and Wang, M. (2020a). Variational policy gradient method for reinforcement learning with general utilities. arXiv preprint arXiv:2007.02155.
Zhang, R., Dai, B., Li, L., and Schuurmans, D. (2020b). Gendice: Generalized offline estimation of stationary values. arXiv preprint arXiv:2002.09072.
15


Reviews:
[{"review_id": "oFL0-mGNEkA", "reviewer": "Reviewer_3ZfY", "summary": "The authors propose a new actor-critic method for offline RL which is based on pessimism through perturbations applied to the weights. The authors prove a lower bound on the performance of the policy, while noting their approach requires fewer assumptions on function class and MDP, as well as computational cost, than previous methods with similar theoretical guarantees. ", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I'm not particularly knowledgeable about the theoretical aspects of this area. I'm going to comment on the practical implications of this work regardless, but my impression is that this work doesn't need to have immediate empirical benefits to provide value to authors working on related topics. My confidence score reflects my level of expertise in this area and I recommend the AC puts little emphasis on my final score.\n\nAre there practical benefits/observations/analysis for somebody who's objective is performance (i.e. leveraging state-of-the-art deep RL methods), in this paper? Probably not.\n- The obvious reason is the limitations due to necessary assumptions made by the authors + the lack of empirical results, as pointed out by the authors themselves, means the practical benefits of the proposed algorithm are difficult to evaluate or extend to existing algorithms. \n- One claim the authors make is that the paper analyzes actor-critic methods in the context of offline RL. This claim isn't really reflected in the content of the paper, which is more about the proposed algorithm, rather than an analysis on actor-critic methods as a whole. It doesn't seem like we could take this analysis and extend it to existing actor-critic approaches such as BCQ [1] or CQL [2].\n- I think an underappreciated limitation is on the data generation process. The practical side of offline RL really centers around the use of a finite-sized dataset. \n- To the best of my knowledge, the use of parameter perturbation to induce pessimism for offline RL is novel in context of the deep RL, but has been used previously for exploration [3,4]. And the connection between pessimism and exploration has been noted (i.e. [1,5,6]), so I wouldn't consider this a significant algorithmic novelty. \n\nComments on clarity:\n- I think the paper would benefit from more guiding statements. For example, section 3 jumps immediately into algorithm description, without providing any overview. This also applies to section 4. \n\nComments on prior work:\n- The author mentions pessimism as a common approach in offline RL, but in the deep RL literature, policy constraint approaches are vastly more popular (such as [1,7,8,9]). \n\nI'll re-iterate that much what I've discussed should not necessarily be considered relevant, but I'll leave it to the AC to determine what should be considered. I've left my score as positive as I believe the authors have achieved what they have set out to do.\n\nReferences\n- [1] Fujimoto, Scott, David Meger, and Doina Precup. \"Off-policy deep reinforcement learning without exploration.\" International Conference on Machine Learning. PMLR, 2019.\n- [2] Kumar, Aviral, et al. \"Conservative q-learning for offline reinforcement learning.\" arXiv preprint arXiv:2006.04779 (2020).\n- [3] Fortunato, Meire, et al. \"Noisy Networks For Exploration.\" International Conference on Learning Representations. 2018.\n- [4] Plappert, Matthias, et al. \"Parameter Space Noise for Exploration.\" International Conference on Learning Representations. 2018.\n- [5] Laroche, Romain, Paul Trichelair, and Remi Tachet Des Combes. \"Safe policy improvement with baseline bootstrapping.\" International Conference on Machine Learning. PMLR, 2019.\n- [6] Buckman, Jacob, Carles Gelada, and Marc G. Bellemare. \"The Importance of Pessimism in Fixed-Dataset Policy Optimization.\" International Conference on Learning Representations. 2020.\n- [7] Kumar, Aviral, et al. \"Stabilizing Off-Policy Q-Learning via Bootstrapping Error Reduction.\" Advances in Neural Information Processing Systems 32 (2019): 11784-11794.\n- [8] Wu, Yifan, George Tucker, and Ofir Nachum. \"Behavior regularized offline reinforcement learning.\" arXiv preprint arXiv:1911.11361 (2019).\n- [9] Kostrikov, Ilya, et al. \"Offline reinforcement learning with fisher divergence critic regularization.\" International Conference on Machine Learning. PMLR, 2021. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I believe the authors have addressed the limitations adequately. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "g9Jbo0UGupA", "reviewer": "Reviewer_Vb58", "summary": "The paper presents a theoretical study on -- quote – “Do actor-critic methods provably offer any advantage in offline RL?” This is a fundamental question to offline RL, and the authors give a positive answer to that question. Compared to Jin et al. 2020b which uses value-based RL method (PVEI), the main result of the paper is i) a tighter gap between the lower and upper bounds of the value functions obtained by their proposed Pessimistic Least Square Policy Evaluation method and ii) relaxed assumptions about the MDP (restricted closeness vs linear MDP). Actor critic RL is a predominant method in RL, and thus the new findings in this paper are really impressive and encouraging.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is very well written in general, with a nice layout beginning with explicit definition of the problem setting and line of assumptions, ending with main result and its implications, as well as the key ingredients of proof. \nDetailed comments:\n1)\tThe performance guarantee of actor critic methods in offline RL is a fundamental problem.\n2)\tThe main results are positive and encouraging.\n3)\tThe implications of the results are well discussed.\n4)\tThe pessimistic perturbation of the critic instead of using additive bonuses or absorbing states, so that by the carefully constructed value and policy function classes, the linearity of the action value function is maintained, which is critical to the proof.\n5)\tThe line of research has been comprehensively discussed, and the new contribution in this paper has been clearly pointed out and well highlighted. E.g., the comparison against Jin et al. 2020b clearly shows the new advantage of actor critic methods over pessimistic value iteration methods. \n\nA limitation in my opinion is the assumption of functional spaces which is a key ingredient in guaranteeing the performance bound. However, I think the assumption is still reasonable by large.\nA minor point – a typo in Line 157: “cf. Line 1”-> “cf. Line 5”\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "A limitation in my opinion is the assumption of functional spaces which is a key ingredient in guaranteeing the performance bound. However, I think the assumption is still reasonable by large. I understand that it is challenging to obtain performance guarantee without such assumptions.", "review_text": "", "extra_scores": {"ethical_concerns": "n/a", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7 hours"}, "extra_text": {}}, {"review_id": "Uoc8wkfcSqy", "reviewer": "Reviewer_rEwm", "summary": "This paper presents actor-critic methods for offline RL. Specific aspects of the problem addressed by the paper include being able to achieve pessimism without adding in pessimism based bonuses or through defining absorbing states. This allows the approach to work with the original value function class without modifications. The paper also presents distinctions between standard assumptions used in both online/offline RL literature relating to low rank MDPs, restricted closeness, and linear Q^\\pi assumption.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The result presented by this paper appears to be novel, and the algorithm is computationally efficient. What I like about the main result is that  it tends to obtain a result that is competitive with all policies (beyond ones in the policy class considered), such that modulo optimization error, the algorithm finds a policy competitive with the one with the best value subtracted by some form of uncertainty function defined according to the dataset. This result is complemented by an upper-bound that shows that this cannot really be improved upon beyond some constant factors and log factors.\n\nMinor comments:\n- note that in the work of Kidambi et al. 2020, the comparator policy can be an arbitrary policy (not necessarily the optimal policy), albeit, this paper's result is stronger for reasons mentioned above. Could the authors verify if this is the case with the other works they mention below Theorem 2?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3-4"}, "extra_text": {}}, {"review_id": "DSFIbg_ThxQ", "reviewer": "Reviewer_Zu4e", "summary": "This paper investigates whether the actor-critic methods have probable advantages compared to the model or value-based approaches in the offline reinforcement learning (RL) setting. Recent work on offline RL propose to incorporate pessimism into the procedure and this work argues that the actor-critic methods can naturally achieve so by separating the policy optimization from the policy evaluation. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, this work chooses an important problem to work on and have shown certain advantages of actor-critic methods in the offline RL setting. There is a re-surging interest in offline RL. While most recent work focues on the model or value-based methods, this work instead explore the popular actor-critic methods given only logged data, which may motivate further investigation along this line.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There are a few limitations in the current version. In particular, it is not clear whether designing the goal as finding the policy with highest minimum value function is the best choice (or a better choice than alternative choices) in the offline RL setting. Actually, while it is desirable to introduce pessimism into the framework in face of uncertainty, the design of the goal itself in this work could be too restrictive. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes an actor-critic style algorithm for solving the offline RL problem. The key contribution is in showing that pessimism can be naturally incorporated in this framework, designing an efficient algorithm with provable performance guarantees. At the same time, the reviewers also point out limitations/points of discussion such as whether the goal of finding the policy with highest minimum value function is the best choice (or a better choice than alternative choices) in the offline RL setting, discussion of assumptions on functional space and data generation process -- having a discussion around these and other points in the reviews would improve the quality of paper.

Overall, since all reviewers agree that this paper makes a good theoretical contribution to the offline RL problem, I am recommending acceptance.
Decision: Accept (Poster)