VIPeR: Provably Efficient Algorithm for Offline RL with Neural Function Approximation
Authors: Thanh Nguyen-Tang
Raman Arora
Venue: ICLR 2023 notable top 25% (2023)
Keywords: Offline Reinforcement Learning
Neural Networks

Abstract: We propose a novel algorithm for offline reinforcement learning called Value Iteration with Perturbed Rewards (VIPeR), which amalgamates the pessimism principle with random perturbations of the value function. Most current offline RL algorithms explicitly construct statistical confidence regions to obtain pessimism via lower confidence bounds (LCB), which cannot easily scale to complex problems where a neural network is used to estimate the value functions. Instead, VIPeR implicitly obtains pessimism by simply perturbing the offline data multiple times with carefully-designed i.i.d. Gaussian noises to learn an ensemble of estimated state-action {value functions} and acting greedily with respect to the minimum of the ensemble. The estimated state-action values are obtained by fitting a parametric model (e.g., neural networks) to the perturbed datasets using gradient descent. As a result, VIPeR only needs $\mathcal{O}(1)$ time complexity for action selection, while LCB-based algorithms require at least $\Omega(K^2)$, where $K$ is the total number of trajectories in the offline data. We also propose a novel data-splitting technique that helps remove a factor involving the log of the covering number in our bound. We prove that VIPeR yields a provable uncertainty quantifier with overparameterized neural networks and enjoys a bound on sub-optimality of $\tilde{\mathcal{O}}(  { \kappa H^{5/2}  \tilde{d} }/{\sqrt{K}})$, where $\tilde{d}$ is the effective dimension, $H$ is the horizon length and $\kappa$ measures the distributional shift. We corroborate the statistical and computational efficiency of VIPeR with an empirical evaluation on a wide set of synthetic and real-world datasets. To the best of our knowledge, VIPeR is the first algorithm for offline RL that is provably efficient for general Markov decision processes (MDPs) with neural network function approximation. 

Published as a conference paper at ICLR 2023
VIPER: PROVABLY EFFICIENT ALGORITHM FOR OF- FLINE RL WITH NEURAL FUNCTION APPROXIMATION
Thanh Nguyen-Tang Department of Computer Science Johns Hopkins University Baltimore, MD 21218, USA nguyent jhu. edu
Raman Arora
Department of Computer Science Johns Hopkins University Baltimore, MD 21218, USA arora@cs. Chu.ediy
ABSTRACT
We propose a novel algorithm for offline reinforcement learning called Value Iter- ation with Perturbed Rewards (VIPeR), which amalgamates the pessimism prin- ciple with random perturbations of the value function. Most current offline RL algorithms explicitly construct statistical confidence regions to obtain pessimism via lower confidence bounds (LCB), which cannot easily scale to complex prob- lems where a neural network is used to estimate the value functions. Instead, VIPeR implicitly obtains pessimism by simply perturbing the offline data multi- ple times with carefully-designed i.i.d. Gaussian noises to learn an ensemble of estimated state-action value functions and acting greedily with respect to the min- imum of the ensemble. The estimated state-action values are obtained by fitting a parametric model (e.g., neural networks) to the perturbed datasets using gradient descent, As a result, VIPeR only needs (1) time complexity for action selection, while LCB-based algorithms require at least (((?),, where K is the total number of trajectories in the offline data. We also propose a novel data-splitting technique that helps remove factor involving the log of the covering number in our bound. We prove that VIPeR yields a provable uncertainty quantifier with overparameter- ized neural networks and enjoys a bound on sub-optimality of (kK11//2d/ KK). where d is the effective dimension, H is the horizon length and к measures the distributional shift. We corroborate the statistical and computational efficiency of VIPeR with empirical evaluation on wide set of synthetic and real-world datasets. To the best of our knowledge, VIPeR is the first algorithm for offline RL that is provably efficient for general Markov decision processes (MDPs) with neural network function approximation.
INTRODUCTION
Offline reinforcement learning (offline RI.) (Lange al. 2012 Levine et al.) 2020 is practical paradigm of RL. for domains where active exploration is not permissible. Instead, the learner can access fixed dataset of previous experiences available a priori. Offline RL finds applications in several critical domains where exploration is prohibitively expensive or even implausible, including healthcare (Gottesman al., 2019) Nie al. (02T), recommendation systems (Strehl et al., 2010) Thomas et 2017), and econometrics (Kitagawa & Tetenov 2018 Athey & Wager 2021). among others. The recent surge of interest in this area and renewed research efforts have yielded several
important empirical successes (Chen et al. 2021 Wang et al. 2023 2022
Meng et al. 2021
key challenge in offline RL is to efficiently exploit the given offline dataset to learn an optimal policy in the absence of any further exploration. The dominant approaches to offline RL address this challenge by incorporating uncertainty from the offline dataset into decision-making (Buckman
et al. 202 1 Jin et al. 2021 Xiao et al. 202 Nguyen-Tann et al. 2022a Ghasemipour al. 2022
An et al. 2021 Bai et al. 2022). The main component of these uncertainty- aware approaches to offline RL is the pessimism principle, which constrains the learned policy to the offline data and leads to various lower confidence bound (LCB)- -CCBed algorithms. However, these methods are not easily extended scaled to complex problems where neural function approximation is used estimate

---

Published as a conference paper at ICLR 2023
the value functions. In particular, it is costly explicitly compute the statistical confidence regions of the model or value functions if the class of function approximator is given by overparameterized neural networks. For example, constructing the LCB for neural offline contextual bandits (Nguyen- Tang et al. 2022a) and RL (Xu & Liang, 2022) requires computing the inverse of a large covariance matrix whose size scales with the number of parameters in the neural network. This computational cost hinders the practical application of these provably efficient offline RL algorithmss Therefore. a largely open question is how to design provably computationally efficient algorithms for offline RL with neural network function approximation.
In this work, we present a solution based on a computational approach that combines the pessimism principle with randomizing the value function (Osband et al.] 2016; Ishfag et al., [021]. The algo- rithm strikingly simple: we randomly perturb the offline rewards several times and act greedily with respect to the minimum of the estimated state-action values. The intuition is that taking the min- imum from an ensemble of randomized state-action values can efficiently achieve pessimism with high probability while avoiding explicit computation of statistical confidence regions. We learn the state-action value function by training a neural network using gradient descent (GD). Further, we consider a novel data-splitting technique that helps remove the dependence on the potentially large log covering number in the learning bound. We show that the proposed algorithm yields a provable uncertainty quantifier with overparameterized neural network function approximation and achieves sub-optimality bound of ((sHH//2d /K), where K is the total number of episodes in the offline data, d is the effective dimension, H is the horizon length, and k measures the distributional shift. We achieve computational efficiency since the proposed algorithm only needs (1)) time complexity for action selection, while ICCB-baeed algorithms require O(K2) time complexity. We empirically corroborate the statistical and computational efficiency of our proposed algorithm on wide set of synthetic and real-world datasets. The experimental results show that the proposed algorithm has strong advantage in computational efficiency while outperforming LCB-basc neural algorithms. To the best of our knowledge, ours is the first offline RL algorithm that is both provably and compu- tationally efficient in general MDPs with neural network function approximation.
RELATED WORK
Randomized value functions for RI. For online RI., Oshand et al. (2016] 2019) were the first to explore randomization of estimates of the value function for exploration. Their approach was inspired by posterior sampling for RL (Osband et al., 2013). which samples a value function from posterior distribution and acts greedily with respect to the sampled function. Concretely, Osband et al. (2016) 2019) generate randomized value functions by injecting Gaussian noise into the training data and fitting a model on the perturbed data. Jīa et al.) (2022) extended the idea of perturbing re- wards to online contextual bandits with neural function approximation. Ishfaq et al. (2021) obtained a provably efficient method for online RL. with general function approximation using the perturbed rewards. While randomizing the value function is an intuitive approach to obtaining optimism in online RL, obtaining pessimism from the randomized value functions can be tricky in offline RL. Indeed, Ghasemipour al. (002) point out critical flaw in several popular existing methods for offline RL that update an ensemble of randomized Q-networks toward a shared pessimistic temporal difference target. In this paper, we propose simple fix to obtain pessimism properly by updating each randomized value function independently and taking the minimum over an ensemble of ran- domized value functions to form a pessimistic value function.
Offline RL with function approximation. Provably efficient offline RL has been studied exten- sively for linear function approximation. Jin et al.] (2021) were the first to show that pessimistic value iteration is provably efficient for offline linear MDPs. Xiong et al. (2023): Yin al. (2022) improved upon Jin et al. (202T) by leveraging variance reduction. X et al. (2021) proposed Bellman-conssisenccy -ellman-connisteem assumption with general function approximation, which improves the bound of Jin et al. 2022 by a factor of vd when realized to finite action space and linear MDPs. Wang et al. (2021 Zanette (2021) studied the statistical hardness of offline RL with linear function ap- proximation via exponential lower bound, and Foster et al. (202I) suggested that only realizability efficient offline RL. Beyond linearity, some works study offline RL for general function approximation, both parametric and nonparamet-
and strong uniform data coverage are not sufficient for sample-efficient
ric. These approaches are either based on Fitted-Q Iteration (FQI) (Munos & Szepesvári 2008 Le
2

---

Published as a conference paper at ICLR 2023
et al. 2019 Chen & Jiang 2019 Duan et al. 202 Hu et al. 2021 Nguyen- Tang al. or the pessimism principle (Uehara & Sun 2022: IN guyen- Tang et al. 2022a Jin et al. 2021 While pessimism-basee algorithms avoid the strong assumptions of data coverage used by FQI-based algo- rithms, they require an explicit computation valid confidence regions and possibly the inverse of a large covariance matrix which is computationally prohibitive and does not scale to complex function approximation setting. This limits the applicability of pessimism-basee
2022b
provably efficient offline RL practical settings. A very recent work Bai al. (2022) estimates the uncertainty for construct- ing LCB via the disagreement of bootstrapped Q- Q-functions. However, the uncertainty quantifier is only guaranteed in linear MDPs and must be computed explicitly.
We provide a more detailed discussion of our technical contribution in the context of existing litera- ture Section
PRELIMINARIES
In this section, we provide basic background on offline RL and overparameterized neural networks.
3.1 EPISODIC TIME-INHIOMGEENOU MARKOV DECISION PROCESSES (MDPS)
A finite-horizon Markov decision process (MDP) is denoted as the tuple M = AS, H, di), where S an arbitrary state space, A arbitrary action space, H the episode length, and di the initial state distribution. We assume that SA == |S||A| is finite but arbitrarily large, e.g., it can be as large the total number of atoms the observable universe the set of probability measures over S. A time-inhomogeneous transition kernel TP = (Px } h= where I S A P(S) maps each state-action pair (8h, an) to a probability distribution PA (-1sh, an). Let r [ra) where rh S x A + [0, 1] is the mean reward function at step h. A policy π W assigns each state E S to probability distribution, (-ss), over action space and induces a random trajectory 81, 01, ri,..., 811 HH, T', 88+1 where 81 ~ di. an ~ [s(-) 8h+1 ~ (. (P aa)) We define the state value function V E RR and the action- state value function QT, RSA at each timestep as (T, a) E, I re
10 Let P(S) denote
s, an al, and V (s) = [ss) [Q% (s, a)), where the expectation E,, is taken with respect to the random- ness of the trajectory induced by π. Let Ph denote the transition operator defined as (F,, (s,, (.s.a)) [Vs)). For any V
+ R. we define the Bellman operator timestep as (s, = (s, + (s, The Bellman equations are given as follows. For any (s,a, ESE x x [H].
Qh( a) (B.
= (+)ss) VH= O,
where [H] = {1,2..... H). - and ) denotes the summation over all E A. We define an optimal policy n" as any policy that yields the optimal value function, i.e. V/ (s) sup, Vs)(s) for any (s, h) S x [H]]. For simplicity, we denote V and Q as Vř and Q respectively. The Bellman optimality equation can be written as
(s, a) (BA Vo (s, a), (s) max (h a), ($ =. aEA
Define the occupancy density as dT, a) == ((ss,, an) = (s, (T) which is the probability that we visit state s and take action a at timestep if we follow the policy æ. We denote dj. by d;.
Offline regime. In the offline regime, the learner has access fixed dataset D (1sh ahe rf, of 1) he(r] generated a priori by some unknown behaviour policy = {urn Jeeje- Here, K is the total number of trajectories, and ai
Pa a for any ht, E [K] x [H]. Note that we allow the trajectory at any time E [K] to depend on the tra- jectories at previous times. The goal of offline RL is to learn policy मं, based on (historical data)
D, such that â achieves small sub-optimality, which we define
(f) = Enjadi [SubOpt(#;; 81)], where SubOpt 81) VT (81) (s1).
3

---

Published as a conference paper at ICLR 2023
Algorithm Value lteration with Perturbed Rewards (VIPeR)
Input: Offline data {()) o )
hе[H]* parametric function family F {f(: : W)
W E W} C {X + }RJ (e.g. neural networks), perturbed variances he number of bootstraps M. regularization parameter A, step size 17, number of gradient descent steps and cutoff margin 4), split indices {IA hRE(M)) where In == [[ h)K² + 1...., (H h + 1)K
2: Initialize (+) + 0 and initialize f(.:;; with initial parameter Wo
3: for h = H
do
4: for i
1,........ M do Sample (5h JEZZ ~N(0, of.) and Sh (Gh "eet ~ ~N(0,
5:
6:
Perturb the dataset Dj + (0 a r Vo+i (sh 1) + 5x JEET
Perturbation Optimization
7:
Let W - GradientDescent(/ 7,, J. Di Sh Wo) (Algorithm 2
8:
end for
9: Compute (.).))) t- min (: W,),
h h 1) +
Pessimism
10: Tn arg max (Qn, mh) and Va (0h, 7x)
Greedy
11: end for
12: Output: मे = = hmM])
Notation. For simplicity, we write z1, = (s), a and x (s, a). We write Ö(-) to hide logarith- mic factors of the problem parameters (d, H, K, m, 1/5) in the standard Big-Oh notation. We use (-)) as the standard Omega notation. We write u S e if = O(v) and write u 2 if S u. We write A < B iff B is positive definite matrix. La denotes the d x d identity matrix.
3.2 OVERPARAMETERIUEE NEURAL NETWORKS
In this paper, consider neural function approximation setting where the state-action value func- tion is approximated by a two-layer neural network. For simplicity, we denote X' == x A and view it subset of IRd Without loss of generality, we assume X S == {ir E R | = 1}. We consider standard two-layer neural network: f(x; W, = vm Σi bio (w x). where m
an even number, a(.) max(- 0} the ReLU activation function (Arora al., 2018). and W = (wf ..... wT ) E Rund During the training, we initialize (W, 6) via the symmetric initill- ization scheme (Gao et 2019) as follows: For any I Z. w; wT+ t (0, La/d), and b by+t = -b ~ Unif( 1-1, 1 During the training, we optimize over W while the b, are kept fixed, thus we write f=; W. b) as W)) Denote g(;; W' V (x; W) E TRndd and let Wo be the initial parameters of W. We assume that the neural network is overparameterized, i.e, the width is sufficiently larger than the number of samples K. Overparameterization has been shown to be effective studying the convergence and the interpolation behaviour of neural networks (Arora let al., 2019: Allen-Zhu al.) 2019 Hanin & Nical 2020) Cao & Gul [019 [elkin 2021). Under such an overparameterization regime, the dynamics of the training of the neural network can be captured using the framework of the neural tangent kernel (NTK) (Jacot et al. 2018).
ALGORITHM
In this section, we present the proposed algorithm called Value Iteration with Perturbed Rewards, or VIPeR; see Algorithm for the pseudocode. The key idea underlying VIPeR is to train parametric model (e.g.. neural network) on a perturbed-rewars dataset several times and act pessimistically by picking the minimum over ensemble of estimated state-action value functions. In particular, at each timestep
[H], we draw M independent samples of zero-mean Gaussian noise with variance Tne We use these samples perturb the sum of the observed rewards, rf. and the estimated value function with one-step lookahead, i.c., ( (see 6 Algorithm Dp. The weights W are then updated by minimizing the perturbed regularized squared loss on ( (eEME using gradient descent (Line We pick the value function pessimistically by selecting the minimum
the finite ensemble. The chosen value function is truncated at (H - h + 1) + 2 (see Line 9) where
This symmetric initialization scheme makes (a; Wo) and (g(x:; Wo), Wo) for any
4

---

Published as a conference paper at ICLR 2023
& 2 0 is small cutoff margin (more on this when we discuss the theoretical analysis). The returned policy is greedy with respect to the truncated pessimistic value function (see Line 10).
It is important to note that split the trajec- tory indices [K] evenly into H disjoint buckets
Algorithm 2 GGradientDesceen((2 7, J, Dj Sh. Wo) 1: Input: Regularization parameter X, step size 17, number of gradient descent steps J. perturbed dataset Di = {s a r + V + 5h IREZA, regularization per- turber Ch. initial parameter Wo
[K] Lh where I [( K)K² + 1,..., (H h + 1)K1 for K' := [K/H as illustrated in Figure The estimated @n. is thus obtained only from the offline data with (trajectory) indices from In along with V This novel design removes the data dependence structure in offline RL with function approxi- mation (Nguyen- Seuyen-Tang et al. 2022b) and avoids factor involving the log of the covering num- ber in the bound on the sub-optimality of Algo-
2: L(W) == $ Exez, (f(sh ab: W) - (rft +
1 (++1++00 +5 +x:))) 2
2II + C% Woll2
2
3: for 0, ...,,
J J-1-- do
4: Wj+1 f W - -VVL(W,)
rithm [ as we show in Section D.I
5: end for
6: Output: WJ.
To deal with the non-linearity of the underly- ing MDP, we
two-layer fully connected neural network as the parametric function fam-
ily F in Algorithm [] In other words, we approximate the state-action values: f(x; W) vmm En= (w," x), as described in Section 3.2 We use two-layer neural networks to simplify the computational amalysis. We utilize gradient descent to train the state-action value functions {f(.,:; ; Wi)heemn on perturbed rewards. The use of gradient descent is for the convenience of computational analysis, and our results can be extended to stochastic gradient descent by leveraging recent advances in the theory of deep learning (Allen-Zhu et al. 2019 Cao & Gu 2019), albeit with a more involved analysis.
1
Existing offline RL algorithms utilize estimates of statistical confidence regions achieve pes- simism in the offline setting. Explicitly constructing these confidence bounds is computationally expensive in complex problems where neural network is used for function approximation. For ample, the swwer-confidence-buund bound-basdd algorithms in neural offline contextual bandits (Nguyen- Tang et al. 2022a) and RL (Xu & Liang 2022) require computing the inverse of a large covariance matrix with the size scaling with the number of network parameters. This is computationally pro- hibitive in most practical settings. Algorithm (VIPeR) avoids such expensive computations while still obtaining provable pessimism and guaranteeing rate of Ö( on the sub-optimality, as we show in the next section.
VK
5 SUB-OPTIMALITY ANALYSIS
41
Next, we provide theoretical guarantee on the sub-optimality of VIPeR for the function approximation class, F, represented by (overparameter- ized) neural networks. Our analysis builds on the recent advances in gen- eralization and optimization of deep neural networks (Arora et al. 22019
Allen-Zhu et al. 2019; Hanin & Nica. 2020 Cao Gul 2019 Belkin 2021) that leverage the observation that the dynamics of the neural param- eters learned by (stochastic) gradient descent can be captured by the cor- responding neural tangent kernel (NTK) space (Jacot et al. 2018) when the network is overparameterized
that
Figure 1: Data splitting.
Next, we recall some definitions and state our key assumptions, formally.
Definition (NTK (Jacot al. 2018)). The NTK kernel Kntk X x X + R is defined as
Kna((E,x)) Ew (xo (xo'(w" 2), x' x), (www (w=2)) z2)),
where o' d'(u) 1(u 2 0}.
Withoott loss of generality, we assume K/H E N.
5

---

Published as a conference paper at ICLR 2023
Let Hytk denote the reproducing kernel Hilbert space (RKHS) induced by the NTK, Kitk- SinceKaik universal kernel (Ji et al. tinuous functions on (a compact set) X
2020). we have that Halk is dense in the space of con-
S x A (Rahimi & Recht 2008).
Definition 2 (Effective dimension). For any h [H) the effective dimension of the NTK matrix on data {0 IKez is defined as
dn := logdet(II + Kn/A)
log(1 + /²/
where Kr. = Ktn (4lg MiJeT, is the Gram matrix of Kaik on the data {aktkETy We further
define d == [H] dn.
Remark 1. Intuitively, the effective dimension di measures the number of principal dimensions
over which the projection of the data {ah) IehI the RKHS H.ntk is spread. It was first introduced by Valko et al. (2013) for kernelized contextual bandits and was subsequently adopted by Yang & Wang (2020) and Zhou al. (2020) for kernelized RL and neural contextual bandits, respectively. The effective dimension data detandepnndent and can be bounded by d S K((d+1/((2)) in the worst case (see Section B for more details).
(f(x)) fee e( xo' a))dw: [|efar]lla < B), where c Rd - Rd is any function, Po is the probability density function of sup, [o(w)
Definition 3 (RKHS of the infinite-width NTK). Define :=
N La/d). d), and B is some positive constant.
We make the following assumption about the regularity of the underlying MDP under function approximation.
Assumption 5.1 (Completeness). For any V : S + [0, H + 1] and any h E [H], BAV E O
Assumption 5.1 ensures that the Bellman operator B, can be captured by an infinite-width neural network. This assumption is mild Q* is a dense subset of Hoek (Gao et al.! 2019 Lemma C.1) when B = co, thus Q" is an expressive function class when B is sufficiently large. Morcover, similar assumptions have been used in many prior works on provably efficient RL with function
approximation (Cai et al. 2019 Wang et al. 2020 Yang et al. 2020 Nguyen-Tanne et al. 2022b).
Next, we present bound on the suboptimality of the policy returned by Algorithm 1 Recall that we use the initialization scheme described in Section 3.2
Fix any 8 E (0. 1).
Theorem 1. Let oh = =0: X (H + 1) [dlog(1 + K'/A) + 2 2log(3H/88) Let m = poly(K', H, d, B, d, be some high-order polynomial of the problem parameters, À = Н 1 K. n (A K') Z K' (o + B)), + = 1, and M = log H1SA/oo T- where (b.) is the cumulative distribution function of the standard normal distribution. Then, under Assumption 5.1 with probability at least MHm - 28. for any $1 E S. we have that
SubOpt(#; s1) S s(1 V2log(MSSAH/0) E.r- Σ (s i an; Wo)lla
+ + K"
where Av. Xmma + Exera g(st , at: Wo)g(s a Wo) Bmmdxmdd
Remark 2. Theorem [ shows that the randomized design in our proposed algorithm yields provable uncertainty quantifier even though we do not explicitly maintain any confidence regions in the algorithm. The implicit pessimism via perturbed rewards introduces an extra factor of + log( M A into the confidence parameter
We build upon Theorem D to obtain an explicit bound using the following data coverage assumption.
Assumption 5.2 (Optimal-Poole Concentrability). Ex 00, sup on) &i (s))o))
di (sh.on)
K.
NNte that this is the worst-case bound, and the effective dimension can be significantly smaller in practice. We consider V S + +0,, H + instead of V - (0, H] due the cutoff margin in Algorithm

---

Published as a conference paper at ICLR 2023
work
bound
ii.d? explorative data?
finite spectrum?
matrix inverse?
opt
Jin et al.
2021
Sing #
no yes yes yes
analytical
Yang al.
2020
a vk
no yes
no
yes
oracle
Xu & Liang
2022
dirss δ
yes
yes yes oracle
This work
(22 VK
no no
no
no
GD
Table I: State-of- ahrt results for offline RL with function approximation. The third and the fourth columns ask if the corresponding result needs the data to i.i.d, and well-explored, respectively; the fifth column asks if the induced RKHS needs to have finite spectrum; the sixth column asks if the algorithm needs to invert covariance matrix and the last column presents the optimizer being used. Here ñ is the log of the covering number.
trajectory induced by the optimal policy to be covered by the behavior policy. This data coverage assumption is significantly milder than the uni- form coverage assumptions in many FQI-based offline RL algorithms (Munos Szepesvárj 2008
Assumption 5.2 requires any
Chen & Jiang 2019; Nggyen-Tann et al. 2022b) and is common in pessimism-based algorithms Raahidineeaa et al. 2021 Nguyen-Tany Tang et al. 2022a Chen & Jiang 2022 Zhan et al. 2022).
Theorem 2. For the same parameter settings and the same assumption as in Theorem we have that with probability at least Mmm 50,
2ōkH VK
[20log(1+X11) +/A) +1+
log
16H
log (K' H)
SubOpt(F) <
+
log
+
3K"
8
K
where ā =(11 + 2 (oH(/)A/8)))
Remark 3. Theorem 2 shows that with appropriate parameter choice, VIPeR achieves sub-
optimality ó <>N//> /
Compared to Yang et al. (2000), we improve by a factor
VK
of K K for some 7 (0,1) at the expense of VH. When realized to a linear MDP in Rddiss
d din and our bound reduces into Ô xxHolPdiin) which improves the bound 0 3/2 2/222²² H² /12/VK)
JK
of PEVI (Jin et al. 2021 Corollary 4.6) by factor of d We provide the result summary and comparison in Table 1 and give more detailed discussion in Subsection B.1
6 EXPERIMENTS
In this section, we empirically evaluate the proposed algorithm VIPeR against several state-of-the-as art baselines, including (a) PEVI (Jin et al.) 2021), which explicitly constructs lower confidence bound (LCB) for pessimism in a linear model (thus, we rename this algorithm as LinLCB for convenience in our experiments); (b) NeuraLCB (Nguyen-Tang
al. (022a) which explicitly constructs an LCB using neural network gradients; (c) NeuraLCB (Diag), which is NeuraLCB with diagonal approximation for estimating the confidence set as suggested in NeuraLCB Nggyen-TTan et al. 2022a); (d) Lin-R which is VIPeR realized to the linear function approximation instead of neural network function approximation; (e) NeuralGreedy (LinGreedy, respectively) which uses neural networks (linear models, respectively) to fit the offline data and act greedily with respect to the estimated state-action value functions without any pessimism. Note that when the parametric class, F. in Algorithm| i that of neural networks, we refer to VIPeR as Neural-VIPek We do not utilize data splitting in the experiments. We provide further algorithmic details of the basclines in Section H
We evaluate all algorithms in two problem settings: (1) the underlying MDP is a linear MDP whose reward functions and transition kemnlls are linear in some known feature map (Jin et al.) 2020), and (2) the underlying MDP is non-linear with horizon length H = (i.c., non- non-linear contextual ban- dits) (Zhou et al. 2020), where the reward function is either synthetic constructed from MNIST

---

Published as a conference paper at ICLR 2023
20
Hi 30
H=-50
H-00
LinyPRR (ours)
0-
Lincc
-5
-5
-10
-10
-10
-10
-15
-15
-15
Figure 2: Empirical results of sub-optimality (in log scale) on linear MDPs.
dataset (LeCun et al. 1998) We also evaluate (a variant of) our algorithm and show its strong per- formance advantage in the D4RL benchmark (Fu et al. 2020) in Section A.3 We implemented all
algorithms in Pytorch (Paszke et al. (019)) on server with Intel(R) Xeon(R) Gold 6248 CPU @
2.50GHz, 755G RAM, and one NVIDIA Tesla V100 Volta GPU Accelerator 32GB Graphics Card
6.1 LINEAR MDPs
We first test the effectiveness of pessimism implicit in VIPeR (Algorithm D. To that end, we construct a hard instance of linear MDPs (Yin et al., 2022; Min et al.) (02T); due to page lim- itation, we defer the details of our construction to Section A.I We test for different values of H E (20, 30, 50, 80} and report the sub-optimality of LinLCB, Lin-VIPeR, and LinGreedy, av- eraged over 30 runs, in Figure 2 We find that LinGreedy, which is snvertaintt-agnostte fails to learn from offline data and has poor performance in terms of sub-optimality when compared to pessimism-based algorithms LinL.BB and LineR. Further, LinLCB outperforms Lin-V when K is smaller than 400, but the performance of the two algorithms matches for larger sample sizes, Unlike LinLCB, VIPeR does not construct any confidence regions or require computing and inverting large (covariance) matrices. The Y-axis is in log scale; thus, Lin-VIPeR already has small sub-optimality in the first K z 400 samples. These show the effectiveness of the randomized design for pessimism implicit in Algorithm I
6.2 NEURAL CONTEXTUAL BANDITS
mnhi
log (oubiptt
Iog (uuh0pp)
log (Subd1o0))
Vecraice (olc)
2:25
Neurs Greedy
Barakoredy
RavaL.o
fat
182
2509
X05
100%
6200
(a)
(b)
(c)
Figure 3: Sub-optimality (on log-scale) vs. sample size (K) for neural contextual bandits with fol-
lowing reward functions: (a) r(s,(( cos (.)), (b) r(s,((, a) exp(-10 00000 0,)?), and (c) MNIST.
Next, we compare the performance and computational efficiency of various algorithms against VIPeR when neural networks are employed. For simplicity, we consider contextual bandits, a spe- cial case of MDPs with horizon H 1. Following Zhou et al. (2020); Nguyen-
al. (2022a),
we use the bandit problems specified by the following reward functions: (a) r(s, a) cos(3s (3s 0,, ) exp( (000-10(sf O0))) where and O2 are generated uniformly random from the unit sphere S with d = 16 and = 10; (c) MNIST, where r(s, a) = 1 if a is the true label of the input image s and r(s, a) O, otherwise. To predict the value of different actions from the same state s using neural networks, we transform a state E Rd into d'A-dimensional vec- tors s(4) = (s, 0,..,,,,,,, 0), 8(2) = (0, s,........ map g(a) to r(s, a) given a pair of data (s.a). a). For Neural-VIPeR, NeuralGreedy, Neural.CB, and NeuraLCB (Diag), we use the same neural network architecture with two hidden layers of width m = 64 and train the network with Adam optimizer (Kingma & Ba 2015). Due to page limita-
(b) r(s,a)=
= (O.....O, ., and train the network to
tions, we defer other experimental details and hyperparameter setting to Section A.2 We report the
*Our code is available here: http://pssp.gtoatcccc/c/caaaaaaa
8

---

Published as a conference paper at ICLR 2023
sub-optimality averaged over rums in Figure 3 We see that algorithms that use linear model, i.e., ccural-based algorithms, i.e. NeuralGreedy, NeuraLCB, NeuraLCB (Diag) and Neural- VIPeR, attesting the crucial role neural representations play in RI. for non-linear problems. It is also interesting to observe from the experimental results that Neural.CB does not always outperform its diagonal approximation, Neural.CB (Diag) (e.g.. in Figure B())), putting a question mark on the empirical effectiveness of NTK- based uncertainty for offline RL. Finally, Neural-VIPeR outperforms all algorithms in the tested benchmarks, suggesting the effectiveness of our randomized design with neural function approximation.
LinLCB and Lin-VIPeR significantly underperform
4500
Algotthmm
Action selection time (6)
NeuraLCB
1.500
4000
Sec-oa Lis
NeuraaCS
NeuraLCB (Diag)
8000
4000
Neural-VIPeR
2500
2000
2000
1600
1000
1000
2000
3000
1000
800
05.1 3055
S000 3.42
m:16
m=32
m=54
m=128
Witt
(a)
(b)
Figure 4: Elapsed time (in seconds) for action selection in the contextual bandits problem with
r(s, a) = 10(s" 0,) 2 (a) Runtime of action selection versus the number of (offline) data points K, and (b) runtime of action selection versus the network width m (for K 500).
Figure shows the average runtime for action selection of neural- based algorithms NeuraL.CB. NeuraL.CB (Diag), and Neural-VIPeR. We observe that algorithms that use explicit confidence regions, i.e., NeuraLCB and NeuraLCB (Diag), take significant time selecting action when either the num- ber of offline samples K or the network width m increases. This is perhaps not surprising because NeuraLCB and Neu- raLCB (Diag) need to compute the inverse of a large covari- matrix sample action and maintain the confidence region for each action per state. The diagonal approximation significantly reduces the runtime of NeuraLCB, but the run- time still scales with the number of samples and the network width. In comparison, the runtime for action selection for Neural-VIPel is constant. Since NeuraLCB, NeuraLCB (Diag), and Neural-VIPed use the same neural network architecture, the runtime spent training one model similar. The only difference that Neural-VIPed trains M models while Neural .CB and Neural.CB (Diag) train single model. However, as the perturbed data Algorithm Tare independent, training M models in Neural-VIPeR embarrassingly parallclizable.
0.40
SubOgt
0.35
0.90
00
75
100
125
175 200
M
Figure 5: Sub-optimality of Neural- VIPeR versus different values of M.
Finally, in 5 we study the effect of the ensemble size on the performance of Neural-VIPet We use different values of M {1, 2, 5. 10, 20, 30, 50, 100, 200} for sample size K 1000. We find that the sub-optimality of Neural-VII VIPeR decreases graciously as M increases. Indeed, the grid search from the previous experiment in Figure 3 also yields M = 10 and M 20 from the search space M E {1, 10, 20) as the best result. This suggests that the ensemble size can also play important role as hyperparameter that can determine the amount of pessimism needed in practical setting.
7 CONCLUSION
We propose novel algorithmic approach for offline RL that involves randomly perturbing value functions and pessimism. Our algorithm eliminates the computational overhead of explicitly main- taining valid confidence region and computing the inverse of large covariance matrix for pes- simism. We bound the suboptimality of the proposed algorithm (kH VK). We support our theoretical claims of computational efficiency and the effectiveness our algorithm with exten- sive experiments.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
This research was supported, in part, by DARPA GARD award HR001 12020004, NSF CAREER award IIS- 1943251, award from the Institute Assured Autonomy, and Spring 2022 workshop on "Learning and Games" at the Simons Institute for the Theory of Computing.
REFERENCES
Yasin Abbasi-yadkon Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochas- tic bandits. In J. Shawe- Taylor, R. Zemel, Bartlett, F. Pereira, and K.Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. In International Conference Machine Learning, pp. 242-252. PMLR, 2019.
Gaon An, Seungyong Moon, Jang-Hyun Kim, and Hyun Oh Song. Uncertainty- based offline re- inforcement learning with diversified q-ensemble. Advances in neural information processing systems, 34:7436-7447 2021.
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. In International Conference Learning Representations, 2018.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. Advances in neural information processing systems, 32, 2019.
Susan Athey and Stefan Wager. Policy learning with observational data. Econometrica, 89(1): 133-161, 2021.
Chenjia Bai, Lingxiao Wang, Zhuoran Yang. Zhi-Hong Deng, Animesh Garg, Peng Liu, and Zhao- ran Wang. Pessimistic bootstrapping for uncertainty-drivet offline reinforcement learning. In International Conference on Learning Representations, 2022.
Peter L Bartlett, Olivier Bousquet, and Shahar Mendelson. Local rademacher complexities. The
Annals of Statistics, 33(4):1497-11) 2005.
Mikhail Belkin. Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation. Acta Numerica, 30:203-222 248, 2021.
Alberto Bietti and Julien Mairal. On the inductive bias of neural tangent kernels. Advances Neural Information Processing Systems, 32, 2019.
Jacob Buckman, Carles Gelada, and Mare Bellemare. The importance of pessimism in fixed- dataset policy optimization. In International Conference on Learning Representations, 2021.
Qi Cai, Zhuoran Yang, Jason D Lee, and Zhaoran Wang. Neural temporal-difference learning verges to global optima. Advances in Neural Information Processing Systems, 32, 2019.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks, Advances in Neural Information Processing Systems, 12:10836-10846 2019.
Jinglin Chen and Nan Jiang. Information-theorett considerations in batch reinforcement learning- In International Conference on Machine Learning, pp. 1042-1051. PMLR, 2019.
Jinglin Chen and Nan Jiang. Offline reinforcement learning under value and density-ratio realizabil- ity: the power of gaps. In Uncertainty in Artificial Intelligence, pp. 378-388, PMLR, 2022.
Lili Chen, Kevin Lu, Aravind Rajeswaran, Kimin Lee, Aditya Grover, Misha Laskin, Pieter Abbeel, Aravind Srinivas, and Igor Mordatch. Decision transformer: Reinforcement learning via sequence modeling. Advances in newral information processing systems, 34:15084-15099 2021.
10

---

Published as a conference paper at ICLR 2023
Sayak Ray Chowdhury and Aditya Gopalan. On kemnliieed multi-armes bandits. In International Conference on Machine Learning, Pp. 844-853. PMLR, 2017.
Yaqi Duan, Chi Jin, and Zhiyuan Li. Risk bounds and rademacher complexity in batch reinforcement
learning. In International Conference on Machine Learning, pp. 2892-2902. PMLR, 2021a.
Yaqi Duan, Mengdi Wang, and Martin Wainwright. Optimal policy evaluation using kernel-based temporal difference methods. arXiv preprint (.ti:2209./20022 2021b.
Dylan Foster, Akshay Krishnamurthy, David Simchi-Levi, and Yunzong Xu. Offline rein-
forcement learning: Fundamental barriers for value function approximation. arXiv preprint arXiv:2111.10919 2021.
Justin Fu, Aviral Kumar, Ofir Nachum, George Tucker, and Sergey Levine. D4RL: datasets for deep data-driven reinforcement learning. CoRR, abs/2004.07219, 2020.
Scott Fujimoto and Shixiang Gu. A minimalist approach to offline reinforcement learning. In A. Beygelzimer, Y. Dauphin, Liang, and J. Wortman Vaughan (eds.), Advances Neural In- formation Processing Systems, 2021.
Ruiqi Gao, Tianle Cai, Haochuan Li, Cho-Jui Hsieh, Liwei Wang, and Jason D Lee. Convergence of adversarial training overparametrized neural networks. Advances Neural Information Processing Systems, 32, 2019.
Seyed Kamyar Seyed Ghasemipour, Shixiang Shane Gu, and Ofir Nachum. Why pessimistic? estimating uncertainties for offline RL through ensembles, and why their independence matters. arXiv preprint arXiv:2205.13700 2022.
Omer Gottesman, Fredrik Johansson, Matthieu Komorowski, Aldo Faisal, David Sontag, Finale Doshi-Velez, and Leo Anthony Celi. Guidelines for reinforcement learning in healthcare. Nature medicine, 25 2019.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In International confer- ence on machine learning, pp. 1861-1870. PMLR, 2018.
Boris Hanin and Mihai Nica. Finite depth and width corrections to the neural tangent kernel. In International Conference Learning Representations, 2020.
Yichun Hu, Nathan Kallus, and Masatoshi Uehara. Fast rates for the regret of offline reinforce- ment learning. In Mikhail Belkin and Samory Kpotufe (eds.), Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learming Research, pp. 2462. PMLR, 2021.
Haque Ishfaq, Qiwen Cui, Viet Nguyen, Alex Ayoub, Zhuoran Yang, Zhaoran Wang, Doina Precup, and Lin Yang. Randomized exploration in reinforcement learning with general value function approximation. In International Conference Machine Learning, pp. 4607-4616. PMLR, 2021.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemel: Convergence and gen- eralization in neural networks. Advances in neural information processing systems, 31, 2018.
Ziwei Ji, Matus Telgarsky, and Ruicheng Xian. Neural tangent kernels, transportation mappings, and universal approximation. In International Conference on Learning Representations, 2020.
Yiling Jia, Weitong ZHANG, Dongruo Zhou, Quanquan Gu, and Hongning Wang. Learning neural contextual bandits through perturbed rewards. In International Conference on Learning Repre- sentations, 2022.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference Learning Theory, pp. 2137-2143. PMLR, 2020.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline RL? In International Conference Machine Learning, pp. 5084-5096. PMLR, 2021.

---

Published as a conference paper at ICLR 2023
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA. May 7-9, 2015. Conference Track Proceedings, 2015.
Toru Kitagawa and Aleksey Tetenov. Who should be treated? empirical welfare maximization methods for treatment choice. Econometrica, 86(2):591-616, 2018.
Aviral Kumar, Justin Fu, Matthew Soh, George Tucker, and Sergey Levine. Stabilizing off off-policy q- learning via bootstrapping error reduction. Advances in Neural Information Processing Systems, 32, 2019.
Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative q-learning for offline reinforcement learning. Advances in Neural Information Processing Systems, 33:1 13:1179-1191, 2020.
Sascha Lange, Thomas Gabel, and Martin Riedmiller. Batch reinforcement learning. In Reinforce- ment learning, pp. 45-73. Springer, 2012.
Hoang Minh Le, Cameron Voloshin, and Yisong Yue. Batch policy learning under constraints. In ICML, volume 97 of Proceedings of Machine Learning Research, pp. 3703-3712, PMLR, 2019.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 (66(1)):227-2222) 1998.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tuto- rial, review, and perspectives on open problems. arXiv preprini arXiv:2005.01664 2020.
Linghui Meng, Muning Wen, Yaodong Yang. Chenyang Le, Xiyun Li, Weinan Zhang, Ying Wen, Haifeng Zhang, Jun Wang, and Bo Xu. Offline pre-trained multi-agent decision transformer: One big sequence model conquers all starcraftii tasks. arXiv preprint arXiv:21112.08845, 2021.
Yifei Min, Tianhao Wang, Dongruo Zhou, and Quanquan Gu. Variance-awart off-policy evaluation with linear function approximation. Advances in neural information processing systems, 34, 2021.
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. J. Mach. Learn. Res., 9:815-857, 2008
Thanh Aguyen-Tang Sunil Gupta, A. Tuan Nguyen, and Svetha Venkatesh. Offline neural con- textual bandits: Pessimism, optimization and generalization. In International Conference Learning Representations, 2022a.
Thanh Nguyen-Tang, Sunil Gupta, Hung Tran-The, and Svetha Venkatesh. On sample complexity of offline reinforcement learning with deep reL.U networks besov spaces. Transactions on Machine Learming Research, 2022b. ISSN 2835-8856.
Thanh Nguyen-Tann Ming Yin, Sunil Gupta, Svetha Venkatesh, and Raman Arora. On instance- dependent bounds for offline reinforcement learning with linear function approximation. In Pro- ceedings of the Thirty Seventh AAAI Conference on Artificial Intelligence, 2023.
Xinkun Nie, Emma Brunskill, and Stefan Wager. Learnnng when-to-treat policies. Journal of the
American Statistical Association, 116(533):392-400 2021.
Ian Osband, Daniel Russo, and Benjamin Van Roy. (More) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, 26, 2013.
Ian Osband, Benjamin Van Roy, and Zheng Wen. Generalization and exploration via randomized value functions. In International Conference on Machine Learning, pp. 2377-2386. PMLR, 2016.
Ian Osband, Benjamin Van Roy, Daniel J Russo, Zheng Wen, et Deep exploration via randomized value functions. J. Mach. Learn. Res., 20(1 (111)41:1122 2019.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. Advances in neural information processing systems, 32, 2019.
12

---

Published as a conference paper at ICLR 2023
Ali Rahimi and Benjamin Recht. Uniform approximation of functions with random bases. In 2008 46th Anmual Allerton Conference on Communication, Control, and Computing, pp. 555-561, 2008.
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline rein- forcement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems, 34, 2021.
Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. Gaussian process optimiza- tion in the bandit setting: No regret and experimental design. In Proceedings of the 27th Interna- fional Conference on International Conference Machine Learning, ICML' pp. 1015-1022, Madison, WI, USA, 2010. Omnipress. ISBN 9781 605589077
Ingo Steinwart and Andreas Christmann. Support vector machines. Springer Science & Business Media, 2008.
Alex Strehl, John Langford, Lihong Li, and Sham M Kakade. Learning from logged implicit explo- ration data. Advances in neural information processing systems, 23, 2010.
Philip S. Thomas, Georgios Theocharous, Mohammad Ghavamzadeh, Ishan Durugkar, and Emma Brunskill. Predictive off-policy policy evaluation for nonstationary decision problems, with ap- plications digital marketing. In Proceedings of the Thirty-First AAAI Conference Artificial Intelligence, 17, pp. 4740-4745. AAAI Press, 2017.
Joel Tropp. Freedman's 's inequality for matrix martingales. Electronic Communications in Probabil- ity, 16:262-270, 2011.
Masatoshi Uchara and Wen Sun. Pessimistic model-based offline reinforcement learning under partial coverage. International Conference on Learning Representations, 2022.
Michal Valko, Nathan Korda, Rémi Munos, Ilias Flaounas, and Nello Cristianini. Finite-time anal- ysis of kernelised contextual bandits. In Proceedings of the Twenty-Ninth Conference on Un- certainty in Artificial Intelligence, UAI'13, pp. 654 663, Arlington, Virginia, USA, 2013. AUAI Press.
Kerong Wang, Hanye Zhao, Xufang Luo, Kan Ren, Weinan Zhang, and Dongsheng Li. Bootstrapped transformer for offline reinforcement learning. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022.
Ruosong Wang, Russ Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 0166223-1133 2020.
Ruosong Wang. Dean Foster, and Sham M. Kakade. What the statistical limits of offline RL with linear function approximation? In International Conference on Learning Representations, 2021.
Zhendong Wang, Jonathan J Hunt, and Mingyuan Zhou. Diffusion policies as an expressive policy class for offline reinforcement learning. In The Eleventh International Conference on Learning Representations, 2023.
Yue Wu, Shuangfei Zhai, Nitish Srivastava, Joshua M. Susskind, Jian Zhang, Ruslan Salakhutdinov, and Hanlin Goh. Uncertainty weighted actor-critic for offline reinforcement learning. In ICML, volume 139 of Proceedings of Machine Learning Research, pp. 11319-11328 PMLR, 2021.
Chenjun Xiao, Yifan Wu, Jincheng Mei, Bo Dai, Tor Lattimore, Lihong Li, Csaba Szepesvari, and Dale Schuurmans. On the optimality of batch policy optimization algorithms. In International Conference on Machine Learning, pp. 11 11362-1 1371. PMLR, 2021.
Tengyang Xie, Ching An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. pessimism for offline reinforcement learning. Advances neural information processing systems, 34, 2021.
13

---

Published as a conference paper at ICLR 2023
Wei Xiong, Han Zhong, Chengshuai Shi, Cong Shen, Liwei Wang, and Tong Zhang. Nearly min- imax optimal offline reinforcement learning with linear function approximation: Single-agent MDP and markov game. In International Conference on Learning Representations, 2023.
Tengyu Xu and Yingbin Liang. Provably efficient offline reinforcement learning with trajectory-wise reward. arXiv preprint arXiv:2206.06420 2022.
Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pp. 6995-7004, PMLR, 2019.
Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference Machine Learning, pp. 10746-10756 PMLR, 2020.
Zhuoran Yang. Chi Jin, Zhaoran Wang. Mengdi Wang, and Michael I. Jordan. On function approx- imation in reinforcement learning: Optimism in the face of large state spaces. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS'20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 978 1778171882 111229945...
Ming Yin, Yaqi Duan, Mengdi Wang, and Yu-Xiang Wang. Near-optimal offline reinforcement learning with linear representation: Leveraging variance information with pessimism. Interna- tional Conference on Learning Representations, 2022.
Ming Yin, Mengdi Wang, and Yu-Xiang Wang. Offline reinforcement learning with differentiable function approximation is provably efficient. International Conference on Learning Represen- fations, 2023.
Tianhe Yu, Garrett Thomas. Lantao Yu, Stefano Ermon, James Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma. MOPО: Model-based offline policy optimization. Advances in Neural Information Processing Systems, 13:14129-14143 2020.
Andrea Zanette. Exponential lower bounds for batch reinforcement learning: Batch RL can be exponentially harder than online RL. In International Conference on Machine Learning, pp- 12287-12297. PMLR, 2021.
Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason D. Lee. Offline reinforcement learning with realizability and single-policy concentrability. In Po-Ling Loh and Maxim Raginsky (eds.), Conference on Learning Theory, 2-5 July 2022, London, UK, volume 178 of Proceedings of Machine Learning Research, pp. 7775.2775. PMLR, 2022.
Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with UCB-based explo- ration. In International Conference Machine Learning, pp. 11492-11502. PMLR, 2020.
14

---

Published as a conference paper at ICLR 2023
A EXPERIMENT DETAILS
A.1 LINEAR MDPs
In this subsection, we provide further details to the experiment setup used in Subsection 6.1 We describe in detail a variant of the hard instance of linear MDPs (Yin et al. (022) used in our experi- ment. The linear MDP has S = {0, 1). A = {0, 1,... 99), the feature dimension d = 10. Each action a E [99] = (1...., 99) is represented by its binary encoding vector uh E R with entry being either -1 or I. The feature mapping ((s, a) given by Φ(s, a) [u] (0, a). ( ((s
RR where 0(s, a) 1 if (s. a) (0, 0) and ((s,a) = 0 otherwise. The true measure (%(ss) is given s) + an. 8 and where (anthejt E {0, 1] are generated uni- formly at random and @ is the XOR operator. We define On. [0,... 0,,,1-
by (s) [0.- ........... ,,,,,,,
E IR where 0.99. Recall that the transition follows (s'|s,, a)) (Ø(s, a), ms)) and the mean reward (s, a) = (ø(s, a), 0n). We generated a priori K {l..... 10000 trajectories using the behav- ior policy ns where for any h E [H] we set fu (O)0) (1)0)
P. (a 0, Va >
1; (0)1) = p. pb, (a[1) = - p)/99, Va > 0, where we p
We run over K E {1..... 1000) and H E {20, 30, 50, 80). We set X 0.01 for all algorithms.
For Lin-R we grid searched 0 = E (0.0, 0.1, 0.5, 1.0,2.0, and M E {1, 2. 10, 20.. For LinLCB, we grid searched its uncertainty multiplier B E 00,, is used to compare algorithms. For each H E {20,30 50, 80). each algorithm was executed for 30 times and the averaged results (with std) are reported in Figure
The sub-optimality metric
A.2 NEURAL CONTEXTUAL BANDITS
In this subsection, provide in detail the experimental and hyperparameter setup in our exper- iment in Subsection 6.2 For Neural- VIPeR, NeuralGreedy, NeuraLCB and NeuraLCB (Diag), use the same neural network architecture with two hidden layers whose width the network with Adam optimizer (Kingma & Ba 2015) with learning rate being grid-searched over {0.0001, 0.001, 0.01) } and batch size of 64. For Neural.CB, Neural.CB (Diag), and LinLCB, we grid-searched / over {0.001, 0.01, 0.1, 1,5, 10). For Neural-VIPeR and Lin-VIPed searched a = a over {0.001, 0.01, 0.1, 5, 10} and M over {1, 10, 20). We did not run NeuraLCB in MNIST as the inverse of full covariance matrix in this case is extremely expensive. We fixed the regularization parameter
64, train
we grid-
0.01 for all algorithms. Offline data is generated by the (1 (1pc)map policy which generates non-optimal actions with probability c and optimal actions with probability - 6. We set 0.5 in our experiments. To estimate the expected sub-optimality, we randomly obtain 1, 000 novel samples (i.e. not used in training) to compute the average sub-optimality and keep these same samples for all algorithms.
A.3 EXPERIMENT D4RL BENCHMARK
In this subsection, we evaluate the effectiveness of the reward perturbing design of VIPeR in the Gym domain in the D4RL benchmark (Fu et al. 2020). The Gym domain has three environ- ments (HalfCheetah, Hopper, and Walker2d) with five datasets (random, medium, medium-replay, medium-expert, and expert), making up 15 different settings.
Design. To adapt the design of VIPeR to continuous control, we use the actor-critic framework. Specifically, we have M critics (Q0: he([M] and one actor Tg. where {0' and & are the learn- able parameters for the critics and actor, respectively. Note that the continuous domain, we consider discounted MDP with discount factor 7, instead of finite-time episode MDP as we initially considered in our setting in the main paper. In the presence of the actor Tg, there are two modifica- tions to Algorithm The first modification is that when training the critics (Q' [e]M)) we augment the training loss in Algorithm 2 with new penalization term. Specifically, the critie loss for Qo. on a training sample T = (s, a, 8') (sampled from the offline data D) is
(((':T) = (Qo a) - (r 7Q (5') +))² + 3 Ea Ea [(Qo ((s, (I)
penalization term R(85;a,0)
15

---

Published as a conference paper at ICLR 2023
where 9 has the same value of the current 6' but is kept fixed, Q Σi= Qg: and NO o2) is Gaussian noise, and 3 is penalization parameter (note that 3 here is totally different from the 3 in Theorem D. The penalization term R(6'; s, Φ) discourages overestimation in the value func- tion estimate Q gc for out-of-distribution (OOD) actions a' ~ (-))))). Our design of R(0'; 8, Φ) is initially inspired by the OOD penalization in Bai et al. (2022) that creates pessimistic pseudo target for the values at OOD actions. Note that we do not need any penalization for OOD actions in our experiment for contextual bandits in Section 6.2 This is because in the contextual bandit setting in Section 6.2 the action space is finite and not large, thus the offline data often sufficiently cover all good actions. In the continuous domain such as the Gym domain of D4RL, however, is almost certain that there are actions that are not covered by the offline data since the action space continuous. We also note that the inclusion of the OOD action penalization term R(0'; 8, Φ) in this experiment does not contradict our guarantee in Theorem [ since in the theorem we consider finite action space while in this experiment we consider continuous action space. We argue that the inclusion of some regularization for OOD actions (e.g., R(0"; 5, 6)) is necessary for the continuous domain.
The second modification to Algorithm [ for the continuous domain is the actor training, which is the implementation of policy extraction in line of Algorithm[[ Specifically, to train the actor To given the ensemble of critics (EEME(M)) we use soft actor update in Haarnoja et al. (2018) via
max BaaDaa' min (s; -log To(a')s) (s) @
(E(M]]
which is trained using gradient ascent in practice. Note that in the discrete action domain, we do not efficiently extract the greedy policy with respect to the estimated
need such actor training action-value functions when the action space is finite. Also note that we do not use data splitting and value truncation as in the original design of Algorithm
Hyperparameters. For the ance a = 0.01. For B, we decrease it from 0.5 to 0.2 by linear decay for the first 50K steps and exponential decay for the remaining steps. For the other hyperparameters of actor-critic training, we fix them the same as in Bai et al. (0022). Specifically, the Q-network is the fully connected neural network with three hidden layers all of which has 256 neurons. The learning rate for the actor and the critic are 10 and 3 x 10 respectively. The optimizer is Adam.
of our training, we set M 10 and the noise vari-
Results. We compare VIPeR with several state-of-the-an algorithms, including (i) BEAR (Kumar et al. 2019) that use MMD distance to constraint policy to the offline data, (ii) UWAC (w et al.
1 that improves BEAR using dropout uncertainty, (iii) CQL (Kumar al.. 2020) that mini-
mizes Q-values of OOD actions, (iv) MOPO ( Yu et al., 2020) that uses model--ased uncertainty via ensemble dynamics, (v) TD3-BC (Fujimoto & Guj (021)) that uses adaptive behavior cloning, and (vi) PBRL (Bai et al.) 2022) that use uncertainty quantification via disagreement of bootstrapped Q-functions. We follow the evaluation protocol in Bai et al. (2022). We run our algorithm for five seeds and report the average final evaluation scores with standard deviation. We report the scores of our method and the baselines in Table 2 We can see that our method has a strong advantage of good performance (highest scores) in 11 out of 15 settings, and has good stability (small std) in all settings. Overall, we also have the strongest average scores aggregated over all settings.
B EXTENDED DISCUSSION
Here we provide extended discussion of our result.
B. COMPARISON WITH OTHER WORKS AND DISCUSSION
We provide further discussion regarding comparison with other works in the literature.
'In our experiment, we also observe that without this penalization term, the method struggles to learn any good policy. However, using only the penalization term without the first term in Fq. ( we observe that the method cannot learn either.
16

---

Published as a conference paper at ICLR 2023
BEAR
UWAC
CQL
MOPO
TD3-BC
PBRL
VIPeR
Random
HalfChectah
2.3 #0.0
2.3 #0.0
17.5
35,9 #2.9
11001:1
11.0
14.5 #2.1
Hopper
42.3
2.73
7.9 #0.4
16.7 #12.2
8.5 20.6
26.8 29.3
31.4 #0.0
Walker2d
+10.2
2.04
5.1 +1.3
4.2 #5.7
1,6 11.7
8.1
20.5 #0.5
Medium
HallCheetah
43.0
20.4
47.0
73.1 #2.4
48.3 #0.3
57.9
58,5 #1.1
Hloppe
51.8 +4.0
50.944.4
$3.0 #28.5
38.3 #34.9
59.3 +4.2
75.3 +31.2
99.4 +6.2
Walker2d
+0.2
+3.0
73.3 +17.7
41.2 #30.8
83.7 #2.1
89.6 +0.7
89.6 +1.2
Medium Replay
HaltCheetah
33.3
33.7
45.5
69.2 #1.1
#0.5
45.1 #8.0
45.0 #8.6
Hopper
51.3
25.3 +1.7
88.7
32.7 49.4
60,9 #18.8
100.6 #1.0
100.2 +1.0
Walker2d
7.0
26.6
81.8
73.7 #9.4
81.8 #5.5
77.7 #14.5
83.1 #4.2
Expert Medium Expert
HalfCheetah
46.0
42.7 #0.3
75.6 +25.7
70.3 +21.9
90.7 +4.3
92.3 +1.1
94,2 +1.2
Hopper
50.6 #25.3
44.9 #8.1
105.6 #12.9
60.6 #32.5
98.0 49.4
110.8 +0.8
110.6 1100
Walker2d
22.1 +:4..9
96.5 19.1
107.9 #1.6
77.4 #27.9
110.1 #0.5
110.1 #0.3
109.8 =0.5
IaalsCheeahh
40.6
92.9 #0.6
91.3
81.3 421.8
96.7 #1.1
91.4
97.4
Hopper
#2.6
10.5
96.5 =28.0
62.5 #29.0
107.8 +7
110.5 #0.4
110.8 #0.4
Walker2d
106.6 +6.8
108.4 #0.4
108.5 #0.5
62.4 43.2
110.2 #0.3
108.3 #0.3
108.3 #0.2
Average
38.78 +10.0
50.41 #2.7
67.35 19.1
53.3 +16.3
67.55 +3.8
74.37 +5.3
78.2 +1.9
Table 2: Average normalized score and standard deviation of all algorithms over five seeds in the Gym domain in the "v2" dataset of D4RL (Fu et al.) (202)). The scores for all the baselines are from Table of Bai et al. (2022). The highest scores are highlighted.
Comparing to Jin et al. (2021). When the underlying MDP reduces into linear MDP, if we use the linear model as the plug-in parametric model in Algorithm [ our bound reduces into δ (KHH//2deo which improves the bound Ō H²/ /KK) of PEVI (Jin al. 2021 Corollary 4.6)
VK
by a factor of vdin and worsen by factor of VH due to the data splitting, Thus, our bound is more favorable in the linear MDPs with nigh-dimensional features. Moreover, our bound is guaranteed in more practical scenarios where the offline data can have been adaptively generated and is not required uniformly cover the state-action space. The explicit bound ((d%/2 H //K) of PEVI (Jin et al. | Corollary 4.6) is obtained under the assumption that the offline data have uniform coverage and are generated independently on the episode basis.
Comparing to Yang et al. (2020). Though Yang et al. (2020) work in the online regime, it shares some part of the literature with our work in function approximation for RL. Besides different learn- ing regimes (offline versus online), we offer three key distinctions which can potentially be used the online regime as well: (i) perturbed rewards, (ii) optimization, and (iii) data split. Regard- ing (i), our perturbed reward design can be applied to online RL with function approximation to obtain a provably efficient online RL that computationally efficient and thus remove the need of maintaining explicit confidence regions and performing the inverse of large covariance matrix. Regarding (ii), we incorporate the optimization analysis into our algorithm which makes our algo- rithm and analysis more practical. We also note that unlike ( (Yang al. (020), we do not make any assumption on the eigenvalue decay rate of the empirical NTK kernel as the empirical NTK kernel is data data-dependent. Regarding (iii), our data split technique completely removes the factor / Too..>o. 1/K, B) in the bound at the expense of increasing the bound by factor of VH. In complex models. such log covering number can be excessively larger than the horizon H, making the algorithm too optimistic in the online regime (optimistic in the offline regime, respectively). For example, the target function class is RKHS with 7-polynomial decay, the log covering number scales as (Yang et al. 2020 Lemma D1).
No. (H, 1/K, B) S K म3ं.,
for some a E 10, In the case of two-layer ReLU NTK, 7 d Bietti & Mairal 2019), thus Vlog Nse (H, 1/K, B) S K & which is much larger than / H when the size of dataset is large. Note that data-splitting technique is general that be used in the online regime as well.
Comparing to Xu & Liang 2002).. Xu & Liang (2022) consider a different setting where per- timestep rewards are not available and only the total reward of the whole trajectory is given. Used
17

---

Published as a conference paper at ICLR 2023
with neural function approximation, they obtain (D /VK) where Detr is their effective di- mension. Note that Xu & Liang (202)) do not use data splitting and still achieve the same order of Den as our result with data splitting. It at first might appear that our bound is inferior to their bound as we pay the cost of / H due to data splitting. However, to obtain that bound, they make three crit- ical assumptions: (i) the offline data trajectories are independently and identically distributed (i.i.d.) (see their Assumption 3), (ii) the offline data is uniformly explorative over all dimensions of the fea- ture space (also see their Assumption 3), and (iii) the eigenfunctions of the induced NTK RKHS has finite spectrum (see their Assumption 4). The i.i.d. assumption under the RKHS space with finite dimensions (due to the finite spectrum assumption) and the well-explored dataset is critical in their proof to use a matrix concentration that does not incur an extra factor of /D as would normally do without these assumptions (see Section E., the proof of their Lemma 2). Note that the celebrated ReLU NTK does not satisfy the finite spectrum assumption (Bietti Mairal, 2009). Moreover, we do not make any of these three assumptions above for our bound to hold. That suggests that our bound much more general. In addition, we do not need to compute any confidence regions nor perform the inverse of large covariance matrix.
Comparing to Yin et al. (023).. During the submission of our work, a concurrent work of Yin let al. (202)) appeared online. Yin al. (2023) study provably efficient offline RL with general parametric function approximation that unifies the guarantees of offline RL in linear and generalized linear MDPs, and beyond with potential applications other classes of functions in practice. We remark that the result in Yin et al. (2023) is orthggonal/complleentta to our paper since they consider the parametric class with third-time differentiability which cannot apply to neural networks (not necessarily overparameterized) with non-smooth activation such as ReLU. In addition, they do not consider reward perturbing in their algorithmic design or optimization errors in their analysis.
B.2 WORSE-CASE RATE OF EFFECTIVE DIMENSION
In the main paper, we prove an ① H
sub-optimality bound which depends on the notion of Here we give worst-case rate of the effective dimension d for the two-layer ReLU NTK. We first briefly review the background of RKHS.
effective dimension defined in Definition
2
Let H be an RKHS defined on X' C IRd with kernel function p X' x X + R. Let (., H H R and || || H + R be the inner product and the RKSH norm on H. By the reproducing kernel property of H. there exists a feature mapping Φ : X - H such that fxx (ʃ, d(x)) and p(z, x²) = (Ø(z), (((z))((r))) d(x')) H. We assume that the kernel function p is uniformly bounded, i.c. suPzex p(zr x) < co. Let (²X') be the space of gquare-integral functions on X with respect to the Lebesgue measure and let (z= be the inner product on (2)).. The kernel function p induces an integral operator Tp: (x) + (xx) defined as
TØf(x) = / plz, x') xff (x
By Mercer's theorem (Steinwart& & Christmann 2008 Tр has countable and positive eigenvalues fArh21 and eigenfunctions {14 The kernel function and H can be expressed as
x Σ (x)()))s
(f.v))ce H = (x)
Σ
< cof.
A
Now consider the NTK defined in Definition 1
Kynk (I, x²) = (o (zo' (w" x), x' d'o'(w" (woa'') x²)).
follows from (Bietti& & Mairal 2019 Proposition 1) that X, x i-d Thus, by (rrnnvas et al. 2010 Theorem 5), the data-dependent effective dimension of Haek can be bounded in the worst case by d S K ((d-1)/((2))
18

---

Published as a conference paper at ICLR 2023
We remark that this is the worst-case bound that considers uniformly over all possible realizable of training data. The effective dimension d is on the other hand data-dependent, i.c. its value depends on the specific training data at hand thus d can be actually much smaller than the worst-case rate.
C PROOF OF THEOREM I AND THEOREM 2
In this section, we provide both the outline and detailed proof' of Theorem I and Theorem 2
C.I TECHNICAL REVIEW AND PROOF OVERVIEW
Technical Review. what follows, we provide more detailed discussion when placing our tech- nical contribution in the context of the related literature. Our technical result starts with the value difference lemma in Jin et al.] (202I) to connect bounding the suboptimality of an offline algorithm controlling the uncertainty quantification in the value estimates. Thus, our key technical contri- bution is to provably quantify the uncertainty of the perturbed value function estimates which were obtained via reward perturbing and gradient descent. This problem setting is largely different from the current analysis of overparameterized neural networks for supervised learning which does not require uncertainty quantification.
Our work is not the first to consider uncertainty quantification with overparameterized neural net- works, since it has been studied in Zhou et (2020); Nguyen-Tam et al. (2022a); JJia et al. (2022). However, there are significant technical differences between our work and these works. The work in Zhou et al. 2220);; Nguyen-Tane Tang et al. (2022a) considers contextual bandits with overparameterized neural networks trained by (S)GI) and quantifies the uncertainty of the value function with explicit empirical covariance matrices. We consider general MDP and use reward perturbing to implicitly obtain uncertainty, thus requiring different proof techniques.
Jia et al. (2022) more related to our work since they consider reward perturbing with overparam- eterized neural networks (but they consider contextual bandits). However, our reward perturbing strategy is largely different from that in Jia et al. (2022). Specifically, Dia et al. (2022) perturbs each reward only once while we perturb each reward multiple times, where the number of perturbing times is crucial in our work and needs to be controlled carefully. We show in Theorem that our re- ward perturbing strategy is effective in enforcing sufficient pessimism for offline learning in general MDP and the empirical results in Figure 2 Figure 3 Figure 5) and Table 2 are strongly consistent
with our theoretical suggestion. Thus, our technical proof' are largely different from those of Jia
et al. (0022).
Finally, the idea of perturbing rewards multiple times in our algorithm is inspired by Ishtag et al. (2021). However, [shtag et al.) (2021) consider reward perturbing for obtaining optimism in online RL. While perturbing rewards are intuitive to obtain optimism for online RL, for offline RL, under distributional shift, it can be paradoxically difficult to properly obtain pessimism with randomization and ensemble (Ghasemipour et al.) 2022), especially with neural function approximation. We show affirmatively in our work that simply taking the minimum of the randomized value functions after perturbing rewards multiple times is sufficient to obtain provable pessimism for offline RL. In addi- tion, [shfaq et al. 202I) do not consider neural network function approximation and optimization. Controlling the uncertainty of randomization (via reward perturbing) under neural networks with ex- tra optimization errors induced by gradient descent sets our technical proof significantly apart from that of Ishfaq et al. 2021).
Besides all these differences, in this work, we propose intricately-desiee data splitting tech- nique that avoids the uniform convergence argument and could be of independent interest for study- ing sample-efficient RL with complex function approximation.
Proof Overview. The key steps for proving Theorem | and Theorem D highlighted in Subsec- tion C.2 and Subsection C respectively. Here, we discuss an overview of our proof strategy. The key technical challenge in our proof is to quantify the uncertainty of the perturbed value function estimates. To deal with this, carefully control both the near-tinearity of neural networks in the NTK regime and the estimation error induced by reward perturbing. A key result that we use to con- trol the linear approximation to the value function estimates is Lemma D.3 The technical challenge
and
19

---

Published as a conference paper at ICLR 2023
Parameters
Meaning/Expressionn
m
Network width
X
Regularization parameter
Learning rate
M
Number of bootstraps
{owhneja
Noise variances
J
Number of GD steps
Cutoff margin
K
Number of offline episodes
R
Radius parameter
Failure level
K'
bucket size, K/H
I
index buckets, [[H - h)K + 1, (, - A)K' ....., (H - h + 1)K'
B
Parameter radius of the Bellman operator
(og.Vlog((MM5))
16,1
7422
02 /dogdlo
Bi
x- X- /2K + +) SC,155mm 1/6 /lg
mo mm //og
Bi
2K'(H + + 72,)) X 8C,, Vlog my K (2 /logm
B2
X- 23 /logm
Bm 3m=2/222Vd+ 1221++22llg2222mm0 (o11/8)
10
C,114/3m 110 + C. (Br B2 x- nd) (K' & +m.))² 27712
11
C,R 110g Cg B1 B3 - - ' + ot))
12
10 11 212
BK'
von (2Vd+ lollg 8)) 1/2C, + X
8
+H + w) V // x) K' log 2 2l1g(3H1/8)
Table 3: The problem parameters and the additional parameters that we introduce for our proofs.
Here Ct, C2, and Cg absolute constants independent of the problem parameters.
20

---

Published as a conference paper at ICLR 2023
in establishing Lemma D.3 is how to carefully control and propagate the optimization error incurred by gradient descent. The complete proof of Lemma D.3 is provided Section E.3
The implicit uncertainty quantifier induced by the reward perturbing is established in Lemma D.1 and Lemma D.2] where we carefully design series of intricate auxiliary loss functions and establish the anti-concentrabilityy of the perturbed value function estimates. This requires careful design of the variance of the noises injected into the rewards.
To deal with removing potentially large covering number when quantify the implicit uncer- tainty, we propose our data splitting technique which is validated the proof of Lemma [D]] in Section E. Moreover, establishing Lemma the overparameterization regime induces ad- ditional challenge since standard analysis would result in a vacuous bound that scales with the overparameterization. We avoid this issue by carefully incorporating the use of the effective dimen- sion in Lemma D.1
C.2 PROOF OF THEOREM 1
In this subsection, we present the proof of Theorem We first decompose the suboptimality SubOpt(#;s) s) and present the main lemmas to bound the evaluation error and the summation of the implicit confidence terms, respectively. The detailed proof these lemmas are deferred to Section D For proof convenience, first provide the key parameters that we consistently throughout our proof' in Table
We define the model evaluation error at any (2r, h) E X' [H]
erry ( = (B, V (x).
where B, is the Bellman operator defined in Section 3 and Vn, and Qn the estimated (action-) state value functions returned by Algorithm]] I
Using the standard suboptimality decomposition (Jin
al. 2021 Lemma 3. for any 81 S,
H Σ h=1
SubOpt(#;s1)
Ea |erra (sh, an)l + Σ E. Jerra (s),
Ex
(2n :) (1(0n))) in =n(-1on))
where the third term is non-positive as 7t is greedy with respect to Q.. Thus, for any S, we have
"
SubOpt(#; < Σ
Ex ferr (Sh. an) +
Σ Ex
JerT (sn, ax))
(4)
1=1
h=1
In the following main lemma, bound the evaluation error erra a). In the rest of the proof, consider an additional parameter Rt and fix any E (0, 1).
Lemma C.1. Let
m = 3/22 R log 3/2 (/2 R?)
R = O (m2 log -3 m)
Ω (K + 3/ log log
A>1
(5)
K'C. 2 AR max(4B1, 4B2 2 /2 2 & mn,12 477.2)
75 (A+ KC))
424
6 2,3 E [
21

---

Published as a conference paper at ICLR 2023
where B1. B2, "M. "h2 and are defined in Table 3 Cg is absolute constant given in Lemina G.1 and R. is additional parameter. Let M log & log -- where 4(-) is the cumulative distribution function of the standard normal distribution. With probability at least 1 - M H 2 26, for any (x, h) E X [H]. we have
- - (x) S son(1 2log l1g(;; Wo +
where AG Amn + ENEIA s Wo)g(rk) Wo) R.dddnd
Now can prove Theorem
Proof of Theorem 7 Theorem |
can directly follow from substituting Lemma C.1 into Equation 4
We now only need simplify the conditions in Equation (5). To satisfy Equation (5). set
suffices to
A 1+
v = 1=>>
Th = 3
8C, &C,R4/3m 1016m/m116----
1/6 Vlog m $
x 122 22
B1 S / /2 + + Hh Xrh LVKC, 1/6 Vlog
B2 S K' R'C,R4/33 1/6 Vlog m S 1.
Combining with Equation we have
A +
v = 1 >
Th = B
17 S (A K'y-1
2 max { RR log (H + 1)2
8/2 log // R), K R log" m
[2 + 3 /og K2M/8) do (d M/8) + 1 R log m
4v (H + + 3/log /llggk'k M (6) S R K". K".
(6)
Note that with the above choice of = +
H K
we have
K' log À log(1 + K ) s log <
nk
We further set that m 2 B²K d log (3H (3H/8), /6), we have
BK Vm
8
(2vd+ v 2log(3H x))a -20 + 1/2B
dn log(11 + K' ))+ K' K'log A + 210g((H1/6)
(H + (b)
< 1 1/2 [ log(1
K' xx + 122-2110 2log(3HH/0) o( o(VK').
Thus,
AVK +1 1/100 + Ad M//) <<
for K' large enough. Therefore, there exists R that satisfies Equation verify < 1. We have
We now only need to
in Bm -1/2(2Vd 22lo((31/0) < 1133,
22

---

Published as a conference paper at ICLR 2023
( = Cg 1m mlogm++ (1- (111) xxhh2)) 11/3
(1 (1-1 (1 [1 Blog++ + (Bdllogd(K'1110) $1.
Note that
(1 (1- So +1 ( (/ M/)) &
Thus, Equation is satisfied if
J Alg (K' dog
Finally note that 42 < L1 Rearranging the derived conditions here gives the complete parameter
ditions in Theorem 1 Specifically, the polynomial form of m is Z max log' m, k (H +
1)² log((3 (ogg(3 H/6), /22 1/22-1 log (Vm/ R), K R$ log m. B² " (3) m HH
1 /og (oM(K))))) / + log + 1 8 Rlog m.
C.3 PROOF OF THEOREM 2
In this subsection, we give detailed proof of Theorem 2 We first present intermediate lemmas whose proof's are deferred to Section D For any h [H] and k E Ia [[ - h)K' L...., (H + K'), we define the filtration
Fl = ([(sh2 ohe, rhe Dhem U U(
b+ "h u k+1 k+1 JN
Let
A = X Σ 9( Wo)g(as;
TETS
8 = 3(1 2/
In the following lemma, connect the expected sub-optimality of स to the summation of the un- certainty quantifier at empirical data.
Lemma C.2. Suppose that the conditions in Theorem all hold.
With probability least 1
MHm -2 36,
SubOpt(#) <
2
Ex.
[lo[zn: Wo)llag) Ft k-
s8
+
16
H (ogg(og,
K' h= 1 KETA
3K'
2
+
+ 2t,
K
Lemma C.3. Under Assumption 5.2 for any E [H] and fixed Wo, with probability at least 6,
Σ Be. [loters: Wolllaa
K' (og(1/))
S
<l|g(rn; Wo)llan) + kV X
KET
KEI
Lemma C.4. 1f C2 and m = 2(K'4 log ((H)))). then with probability at least 1 8, for any E [H]. we have
(o)llay S 2d, log(1 + K'/A) +1.
KET.
where dy is the effective dimension defined in Definition
Proof of Theorem 2
Theorem 2 directly follows from Lemma C.2
C.4
using the union bound.
23

---

Published as a conference paper at ICLR 2023
D PROOF OF LEMMA C.1
In this section, we provide the proof for Lemma C.1 We set up preparation for all the results in the rest of the paper and provide intermediate lemmas that to prove Lemma C.I proofs of these intermediate lemmas are deferred to Section
The detailed
D.1 PREPARATION
To prepare for the lemmas and proofs in the rest of the paper, we define the following quantities.
Recall that we use abbreviation = (s, a) X' C Sa-1 and z = (s a X C Sa-1- For any [H] and [M], we define the perturbed loss function
(f(eh: W/ - 1/ ))²))² 2 + I + Sh - Woll2.
(W) = 2
Σ KET
(8)
where
1 r Va+1 (sh+1) + sh.²
Va+1 is computed by Algorithm at Line for timestep h + 1, and {sk and Gt are the Gaussian noises obtained at Line of Algorithm I
Here the subscript and the superscript i in (W) emphasize the dependence the ensemble sample i and timestep h. The gradient descent update rule of (W) is
W+(++) w v)
h
where Wrh.(0) Wo is the initialization parameters. Note that
GradientDescenntAA n). J, Di G. Wo) = W
where WA is returned by Line 7 of Algorithm I
We consider non-perturbed auxiliary loss function
(f(ah: W) vhi)) X 11 -Woll
LA (W)=
Σ
(10)
kEIA
where
a = + + Vn+ (x
Note that (W) is simply non-perturbed version of Σj, (W) where we drop all the noises and }. We consider the gradient update rule for (.W follows
wi(
w v/ L. (W))
(11)
where h Wo is the initialization parameters. To correspond with Wi, denote
Wh. = (.
(12)
We also define the auxiliary loss functions for both non-perturbed and perturbed data in the linear model with feature g(: Wo) as follows
Lilinn (W) = 2
1
Σ
(colti Wo), - - 2
I + C. Woll
(13)
KET
I (W) = Σ
1
(lotah Wo). W) - 222² + wIW - -Wol3.
(14)
2
KET
We consider the auxiliary gradient updates for Σ is.lon (W) as
Wri.lin. W. (in,)i 17 v i i. (W),
(15)
24

---

Published as a conference paper at ICLR 2023
W (in Wilin.(i) 17 R (i (W):
h
(16)
W Wo for all i, h. Finally, we define the least-square solutions to the auxiliary perturbed and non-perturbed loss functions for the linear model as follows
where Wrilbsn(())
Willin arg min Ln
iilión (W),
(17)
WERma
Whth arg min k (W). WERmd
(18)
For any / E [H], we define the auxiliary covariance matrix As as follows
Ab Ammd +
Σ AEZI
g( Wo)g(z);
(19)
It is worth remarking that Algorithm onnly uses Equation and (9) thus does not actually require any of the auxiliary quantities defined in this subsection during its run time. The auxiliary quantities here are only for our theoretical analysis.
D.2 PROOF OF LEMMA
In this subsection, give detailed proof of Lemma C.1 To prepare for proving Lemma C.I first provide the following intermediate lemmas. The detailed proofs of these intermediate lemmas deferred to Section
In the following lemma, we bound the uncertainty f(2; Wx) in estimating the Bellman operator at the estimated state-value function B3 V2+1-
Lemma D.1. Let
A>1 1 m Ω (K +) log(3k 2og(3KK'HH/)))
22
With probability at least 1 Hm 2 26, for any x E Sa-1 and any h E [H].
[x W (B, (B, < 3- (z Wo)lla, + + to.
where Vn+1 is computed by Algorithm for timestep h + 1, Wn. is defined in Equation 12 and 3, l2 and in are defined in Table
In the following lemma, we establish the anti-concentration of Q.- Lemma D.2. Let
m = (63/2R log 3/2 1og ( R O (m//2 log m)
(20)
5 (A + K()))-1
R max 1 2 2 + v + mh,1) + 4
where B,, Bz, th and 2h2 are defined in Table and Cg is constant given in Lemma G.1 Let
M = =log / /log 1-01-1) where (o.) the cumulative distribution function of the standard nor- mal distribution and M is the number of bootstrapped samples in Algorithm Then with probability
1 M for any Sa-1 and [H].
Qn(x) S max (g(a;; Wo). Wrlii
Woll Wo) ( +4 + 12, 12,
where Whin is defined in Equation 18 Qn computed by Line 2 of Algorithm 1 and 4 and 12 are defined in Table
25

---

Published as a conference paper at ICLR 2023
We prove the following linear approximation error lemma.
Lemma D.3. Let
m = Q (d log (v
R= O (m log 3 m),
(21)
11 1 (A K'C, K'
R z max A 2. 2X (H + 7h.1) ) 4n
where B1, B3, th,1 and N,2 are defined in Table 3 and Cg is a constant given in Lemma G.1 probability at least MHm ö, for any (,,2, E Sa-1 x [M] x [J] x [H].
With
(f ((x: Wo), W.. Wo) - (1
where Wh.)), Wh and tı are defined in Equation @ Equation 17 and Table respectively.
In addition, with probability at least Hm for any for any (a, S x [J] x [H],
[s:;; w(() (g(a;; Wo), Whin -Wol 12
where W. Whin, and 12 are defined in Equation 179. Equation 18 and Table respectively.
We now can prove Lemma
Proof of Lemma C.1 Note that the first fourth conditions in Equation ( of Lemma C.1 satisfy Equation (T.. Moreover, the event which the inequality in Lemma D.3 holds already implics the event in which the inequality in Lemma [.I holds (see the proofs of Lemma D.3 and Lemma D.1 in Section D). Now the rest of the proof, we consider the joint event which both the inequality of Lemma D.3 and that of Lemma D.I hold. Then, also have the inequality in Lemma D.
Consider any x E X, h E [.].
It follows from Lemma that
(B,, 1))) 2 Wn) - B- 11a(2; Wo)ll 10
(22)
It follows from Lemma D.2 that
Qn(x)= S max ((((;; Wo), Wh/nn Wo) - Wo)lll;;;W))),," +1 + 12,
(23)
Note that (x) 2 0. (g(2; Wo). Whii
Wo) onllo(z; +4 + S 0, Equation 23
implies that Q (x) = 0 and thus
erra(x) = (B, V,+ (x) - (x)
(Br (x) 2 0.
Otherwise, if (g(2; Wo), Whin Wo) oullg(>; Wo) |A + +1 + 0, Equation 23 implies that
Q (x) < (g Wo), Wilin Wo) - -n Wo Wo)ll + 41 + /2-
(24)
Thus, combining Equation 22 24 and Lemma D.3 with the choice σn 2 8, we have
(rrx(w) == [B (x) 2x(x) 2 -(10 + + +222) -t.
As 2 0, in either case, we have
err == (Bx -
- 2 -
(25)
Note that due to Equation 255
have
(x) < (B, (..1)
- H hh1+
26

---

Published as a conference paper at ICLR 2023
where the last inequality holds due to the choice v0 Thus, have
(x) = minf min f(z; Wi), h + 1 2t} maxf min f(z; WJ), 03. iE[M]
(26)
[E[M]
Substituting Equation 26 into the definition of (rTA(T), we have
(rr (B))))))()) (n(z)
< (BaVa+1)(z) min [(; W%) iE|
(B,Vi+1)(z) f(x; Wv) fz; Wh) - min (a; W;)) iE[Ms]
I 8 -19(a( Wolll + 40 + + f(x; Wn) min f(x; W iE|M]
< 3 (19((a Wo)ll + 22 + (g(2;; Wo), When Wo) +
min (9(:;; Wo), Wri Wo) 1
iE|M]
= 11,, Wo)ll + + 12 + max (g(2; Wo), W/n W. + + i
--9111 Wo)ll 40 +
log
(o)l::WWoolla W +
where the first inequality holds due to Equation (26) the second inequality holds due Lemma D.I
the third inequality holds due to Lemma D.3 and the last inequality holds due to Lemma and Lemma Gi3 the union bound.
D.3 PROOF OF LEMMA
Let Z 10 is the indicator function. have
Proof of Lemma
h= Ey 1h E In Mlgmmm Wolllas)) .lst, F Fk-1 where Under the event which the inequality Theorem holds, we
Σズ
SubOpt(#) < min
H. 9. E,
l1a( Wolll,
+ 2c
min
H, g
(m Wo
2t
K
H
}}
min
H, TE,
1 Inbllo(zn Wollla,
}
K
k=1
K
1 1[k E IoloO Wolllass 115%
1 +
min
H, TT
K
k=
min (H, '13 +
K'
K
E min H, Zg 1| + 21,
(27)
K
1=1
where the first inequality holds due to Theorem and that SubOpt(f; < H. S, the second incquality holds due to min + c} < min(a,b) + c, the third inequality holds due to that A 3 (AA) -1, the fourth incquality holds due to Jensen's inequality for the convex function fxx) min H, )). It follows from Lemma G.9 that with probability at least - 6,
K
K
Σ
E Jmin Z < 2
Z
+
(oH()oogHH//00 H log (KH)/) + 2.
(28)
3
27

---

Published as a conference paper at ICLR 2023
Substituting Equation (28
into Equation (27) and using the union bound complete the proof.
D.4
PROOF OF LEMMA
Proof of Lemma C.3
Let 2
1{k E In)
d, lg(aff Wo) kapp)- We have z is Fl-
measurable, and by Assumption
we have,
(x
| -
Ig(aX: Wol / [[AA)) 11
4 (x <00,
h (1r))
(1n)) (TN)
E ux -d
1ik E Ind
[g{( Wolll
3 F ,99
Thus, by Lemma G.4 for any E [H], with probability at least 8, we have:
k
1fk E Hlo Wo)ll(as) ( off
Band
k=1
(z()) (In)
E (ddt))
11k In}
on on ( Fr .88
K
(1())) (x
K
(1 2 di (=++)
1 [k E In)
11( Wolllaag)-1 + V log(1/0)
1fk E In}
km1
K
K' 1og(11))
S
1k e Imllla(an Wolleay)- vv
K' 1og(1/))
[ga(zn Wollkas> ky
K
A
keTa
D.5 PROOF OF LEMMA
Proof of Lemma C.4 For any fixed h [H], let
U = la( Wollnez, mR
By the union bound, with probability at least 8, for any [H], have
det AA
Σ
l1a Wo)llagy S 2og (At(
K
2ooddt (++
g Wolgs
KEIA
(logdet(T+UU") />)
2logdot(
+ (UT - KW)/A)
< (oogdet(/+XC///) + 2tr (II UUT Kw)/A)
< 2 (VV/A//A)+++((((U UKKll
+ +I, - KKllF
< (oogdet(/+K,///e
< llogdet / + (C,, +1
2dh log(1 K" /A) +1
28

---

Published as a conference paper at ICLR 2023
where the first inequality holds due to À 2 C and (Abbasi-yadkori et al. 2011 Lemma 11), the third equality holds due to that logdet([ + AA4") logdet([ + A'' A). the second inequality holds due to that logdet(A + B) I logdet(AA) + (M(AAIB) B) the result of the convexity of logdet, the third inequality holds due to that (r(AA) < || F. the fourth inequality holds due to 2/K'
F I by the choice of m = 9 K* log( H/))), Lemma G.2 and the union bound, and the last equality holds due to the definition of dz.
E PROOFS OF LEMMAS IN SECTION D
E. PROOF OF LEMMA D.I
In this subsection, we give detailed proof of Lemma D.1 For this, we first provide a lemma about the linear approximation of the Bellman operator. In the following lemma, we show that E, Vi+1 can be well approximated by the class of linear functions with features g(-; Wo) with respect to -orm.
Lemma E.1. Under Assumption 5.1 with probability least 1- over wi.... Wm drawn i.i.d.
from (0, La). for any h E [H), there exist C1,...y Cm where e E IR and ||a]|2 S B such that
Qn(z): =
Σ
c zo (w x)),
1=1
B
BB Vat1 - Qul1=0 S
(2v + /2lg H/0))
mm
Moreover, (1) can be re-written as
Qu(x) = (o),; Wn),
WA == Vmmaic] ..... Om T E mdd and [Whl2 S B.
(29)
We now can prove Lemma D.I
Proof of Lemma D.I We first bound the difference (9(x; Wo), W.) - (0(2;; Wo), Wi:n -Wo):
(0(x; Wo), Wn) - (9(2; Wo). whih
Wo) = g(x; Wo W/ - g(x; W An Σ
Wo)
AET,
-(1; Wo) Wn. g<:; Wo) A
Σ
slatis Wo) (B+T))))
kEZn
+ g(2; Wo)
Σ g( Wo)
[(Bn (h+1) (rā + V
For bounding I,, it follows from Lemma E. that with probability at least 8/3, for any for any S4-1 and any h [H].
[Ba Vo
1 (xx - (0(2; Wo), WaYl S 5.00
where is defined in Table 3 where Wi, is defined in Lemma 8/3, for any for any x E S and any h E [H].
E. Thus, with probability at least
1 = g(;; Wo) Wr g(a; Wo) A
Σ
g(ati Wo) [(B, (.+1)) g(0 Wo) TW,
AEI
-9(2; WW, Ag(2; Wo) Ao
29

---

Published as a conference paper at ICLR 2023
< llg(a; II
Σ 40 2ol1g(1h; (o) +1lg(0;; Wo)ll |W
KEIn
- (10(;; W
1K1oX-1/2C, + A1
(30)
where the first equation holds due to the definition As, and the last inequality holds due to Step with || I VIl4 [W
I
& A/1B
For bounding 12, we have
12 <
Σ
stali Wo) (IBA 1)+1) r - ( 11o(;; Wolllaa)
(31)
KEZ
we directly apply the result Jin et al. 2021 in linear MDP, we would get
12 S dmnH v log (2dm |9(2; Wo) W,
which gives a vacuous bound as m sufficiently larger than K in our problem. Instead, in the following, we present alternate proof that avoids such vacuous bound.
For notational simplicity, we write
c = (Ba (xx - r Vn+1(sh+1);
En = MeNe) I' E RR.
We denote Kinnt = Kotef, Wo), stays: Wo) Wolllesen, as the Gram matrix of the empirical NTK kernel on the data [kEKk We denote
E Rdd ICj = G Go E RK''K"
Go = (g(>); Wo)) KET,
Recall the definition of the Gram matrix Kr, of the NTK kernel the data {ax Jez,, It follows from Lemma G.2 and the union bound that if m = Q log(3K' H/8)) with probability at least 1 - 6/3, for any / e [H].
|
1ci || S V.e..
(32)
We now can bound 13. We have
13
Σ I=
g Wo &
AR
EK GH (A GoGH) - GG
ER GH GolAKK' + G -1
KT (K + +XI)) -1
En
KK + >Ik)) En + ETT (KA, - { -1 K (Xci + ) "En)) (33)
We bound each Ia and Is separately. For bounding 14, applying Lemma G.I with 1 Hm -2 for any h [H].
I4 < [CA(KK + + ( + + -2 -11 En l
= -|(, - (Cimi)(K,, + -I + +Kj ((C), + \ -1 (Ki + xIx)) |
< ||Ko X + ||C//10112 ||ACA Kthit / F
30

---

Published as a conference paper at ICLR 2023
+ K'C2 |K KK 12 Ex 12
X2
22K ( 1
(34)
where the first inequality holds due to the triangle inequality, the second inequality holds due to the triangle inequality, Lemma G.7 and [[KK + > A-1, the third inequality holds due
to ||CC/a 22 S Gall I ||ool
K'C, due to Lemma G.1 the fourth inequality holds due to
|| S (H + v). 2 1, and K'C 2
Substituting Equation 32) in Equation for any h [H].
34
using the union bound, with probability 1-Hm 1amm-_0m0 - -6/33,
4 S
(35)
where the last inequality holds due to the choice of 1/2K (H2 + b/) C and thus
m -2(E 12(E==loge llo(33' Ω (k (H 2 (3Kg H/)))
For bounding 1s as > 1, we have
15 = (K + ATx') FA
- F (Kn + (A - 1)Tx x))x)(((,, (KCr + Alk)) En
E% [(CA + (A - (1-11)/x)---11 + |x.]
En.
(36)
Let (.) be the o-algebra induced by the set of random variables. For any E [M] and & E In = [( h)K² 1,..., (H h + 1)K we define the filtration
F (((s)) oh,, r M U (ss
k+1 k+1 .o
, (ett))hhhi (( ,at 1
which is simply all the data up to episode ho + and timestep but right before r/ k+1 and k+1 are generated (in the offline data). p Note that for any k E In. we have (s% ahs rhe shr1) E Fh, and
Vh+1 E aZ
Neltti..... (
KETy
H1)
C F C
Thus, for any E In, we have
cx = (Br, Vh+1) - r Vn+1(sh Ft.
The key property in our data split design that we nicely have that
VA+1 a (((heea We C F
Thus, conditioned on F Vh41 becomes deterministic. This implies that '] (Bx (n+1)) at - r 15 1 O.
Note that this is only possible with our data splitting technique. Otherwise, et is not zero-mean due the data dependence structure induced in offline RL with function approximation (Nguyen-Tane et al. 2022b). Our data split technique is key to avoid the uniform convergence argument with the log covering number that is often used to bound this term in Jin et al. (202I). which is often large for complex models. For example, in a two-layer ReLU NTK, the eigenvalues of the induced RKHS has d-polynomial decay (Bietti & Mairal 2019), thus its log covering number roughly follows, by Yang et al. 2020 Lemma D1),
! ad-1
log (Hutk, B) S
"To more precise, we need include into filtration randomness from generated noises (4): and (CL) but since these noises are independent of any other randomness, they do not affect any derivations here but only complicate the notations and representations.
31

---

Published as a conference paper at ICLR 2023
for some (0, 1).
Therefore, for any E [H]. { keI, adapted to the filtration {Fr tRzz. Applying Lemma G.5
with Z, = ci (- + +)), H + Vl. o² (H + [++)), p = X 1, for any > O, with probability at
least 1 00/3, for any h E [
E [KC + (A 1)-K) En & (H + logdet (AIx) + K.)) + 2(H + +) (3Hg(H/))
(37)
Substituting Equation 37 into Equation (36). we have
Is S (H + 1 logdet(AAx> + (..)) + 2(H + 4/)² log H/
= [H + ) logdet( Ik + K,/A) + [ + + log X + 2(H + x) log (H/))
(H + dd, log(1 + K" />) + (H - 2 log À + 2(H + 2 log H 5),
(38)
where the last equation holds due to the definition of the effective dimension.
Combining Equations 38 1 Hm -2 8, for any x E S and any h E [F].
and (30) via the union bound, with probability least
Ko(2; Wo), Wa) (o(a;; Wo), Whtn Woll s B. |19(;;;; (o)::WW)lAs"s
where
B: : K' 8 1 B+ (H (H +b) Vogg K(/A) + K' log 2 llo((3H/0))
(39)
Combing with Lemma D.3 using the union bound, with probability least Hm -2 22, for any x E S.-1, and any / E [H.
fa; Wh) (Ba (x) < (0(2; Wo), W Wo) 12
(0(2; Wo), Wn) c0
I B |1:(;; Woll +22
B 11; 1o
+22
where 12, and 3 are defined in Table Similarly, easy to show that
(Bx, (x)) Ww) s 3- 119((; Wo)ll +22 + 10.
E.2 PROOF LEMMA D.2
prove the following intermediate lemmas. The detailed proof's of these intermediate lemmas are deferred to Section
Before proving Lemma D.2
Lemma E.2. Conditioned on all the randomness except ( and (Sh for any i E [M].
Wi
Wiln (0,000A,A
Lemma F.3. If we set M = log HSA log T-T where ((.) is the cumulative distribution func- tion the standard normal distribution, then with probability least 1 for any (x,h) X [H),
min (x(;; Wo), (.,,,Wr,.k Wrilomn < (g(x; Wo), Wh/m)) 0xllg(0; Woll M
We now ready prove Lemma D.2
32

---

Published as a conference paper at ICLR 2023
Proof of Lemma D.2 Note that the parameter condition in Equation 20 of Lemma D.2 satisfies
Equation (11 of Lemma D.3, thus given the parameter condition Lemma D.2 Lemma [D3 holds.
For the rest of the proof,
consider under the joint event in which both the mequality of Lemma
D.3 and that of Lemma F.3 hold. By the union bound, probability that this joint event holds is at least 1
MHm 6. Thus, for any Sa-1, [M] and [M],
min fz; W:) f(;; W.) min (9(0; Wo), Wh Wo) (g(2; Wo), W Wo) + 411 + vE[M]
M
< o (ı Wo A| +
where the first inequality holds due Lemma D.3 and the second inequality holds due Lemma Thus, we have
Qn(z) min min f(; Wh), H h + 1+ + & max min f(;; W,).0 (E[M]
(E|M]
S (ax(( Wo), When Wo) onllg(>; Wo)lla, 1 +4 + 12. 0}.
E.3 PROOF OF LEMMA D.3
In this subsection, provide detailed proof of Lemma D.3 We first provide intermediate lemmas that we use for proving Lemma D.3
The detailed proofs of these intermediate lemmas are deferred
Section F
The following lemma bounds the the gradient descent weight of the perturbed loss function around the linear weight counterpart.
Lemma E.4. Let
Ω (18/2R2-110
m/ log 3/2 ( R?)
R O (12 log m)
(40)
7 (A K' K'C2) 12)-1
RZ m 4B2, 2 2x 2K'1
70,1) 2
where B1, B2, nh,1 and "hh are defined Table and Cg is a constant given in Lemma G.1 With probability at least MM 8, for any (i,j, [M] x [J] x [H], we have
A B(Wo;
1l2 < B1
Bg + (1 nAY (K'H + + m2 + xxh1,))
Similar to Lemma we obtain the following lemma for the gradient descent weights of the non- perturbed loss function.
Lemma E.5. Let
m (3/2
log 3/2 (Vm\
R = (m 1/2 log m)
(41)
5 K -
R Z max (4 4B 2 2X K' +)),
where B1, B2, 7h.1 and "hh2 are defined Table and Cg is a constant given Lemma G.1 With probability least MH 8, for any (i, j, h) [M] x [J] [H), we have
( E B(Wo; Rt).
117/)0 W
B B2 (1 +)
33

---

Published as a conference paper at ICLR 2023
We now can prove Lemma D33
Proof of Lemma D.3 Note that Equation (2 implies both Equation (40) of Lemma E.4 and Equa-
tion (11 of Lemma E.5 thus both Lemma E.4 and Lemma E.5/holdd under Equation
2 Thus, by
the union bound, with probability at least M Mmm ō, for any (i. h) E [M]] x [H]
and Sa-1,
[f(;; (()))) (0(2; Wo), Wh Wo)l
< [f(z; ( (0(2; Wo), Wa - Wo) + (1(2; W, W 1/6 C2 11/6 logm- Cg [B: + Bg + (1- (K' + + + mh.1)² + xri1))
where the first inequality holds due to the triangle inequality, the second inequality holds due to Cauchy-Schwarz inequality, Lemma G.T and Lemma E.4
Similarly, by the union bound, with probability at least 1 - Hm for any (i,j, [M][J] and x E S1-1,
[x; W (g;;; Wo), Wha Woll s (f(;;W - (0(:;; Wo), W Wo)l
+ 19(2;; Wo), 1h W
S CC, mm -1/6 /logm + Cg B1 B2+ R +))) 12:
where the first inequality holds due the triangle inequality, the second inequality holds due to Cauchy-Schwarz inequality, Lemma B.5 and Lemma G.I
F PROOFS OF LEMMAS IN SECTION E
In this section, we provide the detailed proofs of Lemmas in Section t
F.1 PROOF OF LEMMA E.
Proof of Lemma E. have
As BG Vh+1 E Q" by Assumption 5.1 where Q* is defined in Section
fee c(w)² xo' (w" x)dd,
BA V
for some Rd Rd such that sup (a)
[[(())l22
S B. The lemma then directly follows from
approximation by finite sum (Gao et al. 2019
F.2
PROOF OF LEMMA
Proof of Lemma E.2 Let W = W + Sh. and
Li(WW == Σ
(g(a))) Wo), W)
KEIn
where oi r + ( + cx (g( Wo), (.)) We have (W) ( and
arg maxw f.5.i5m (W) = arg maxw (W) Sh both i.j 7. (W)) and T. are convex. Using the regularized least-squares solution,
arg max (W = A7= Σ W
gl Wo)ah
RET
A
Σ
g Wo) Vn+i(sh +
+ Σ wo)l
34

---

Published as a conference paper at ICLR 2023
Σ
al Wo) + (5 + Σ
g(at: Wolg(akk co
KEIn
KEIN
A
Σ
s(axi Wo)(r + Va+i(5h + = + (An smndshh
LEII
Thus, we have
1h = arg max T.I""(())
(W) = arg max (W) Ch
W
W
Σ
g( (o) (5 =x (Ar Nmndlsh Sh
keIn
A
Σ
g Wo) + ( + cx ACh
LkEIa
Wh
Ap
g Wo)sh ACh
By direct computation, it is easy that
W - Wr A7o
Σ
slat:: Woysh - Ach ~ (((0.02A71)
LET
F.3 PROOF OF LEMMA E.3
In this subsection, we provide a proof for E.3 used in Algorithm in the following lemma.
We first provide a bound for the perturbed noises
Lemma F.1. There exist absolute constants C1 > O such that for any > O, event {() holds with probability at least 1 for any (k, h, i) E [ [H] x [M],
ksh I c Cio log( K' H =: 7h.1
|KGl < c20T c2 dlog(dk ' HM/)) =: 7/h22
Proof of Lemma F.I directly follows from the Gaussian concentration inequality in Lemma G.3 and the union bound.
We now can prove Lemma
E.3
Proof of Lemma
E.3
By Lemma
Wri.iin Wrii NN(,0
Using the anti-concentration of Gaussian distribution, for any x (s, S A and any i [M],
PP (Lo(1; Wo), W.A.iin < (o(2; Wo). whii)) on [1:
Wo)lla, (l)l(l (--1) (0,
As [ HEM are independent, using the union bound, with probability at least 1 - SAH(1
Φ 4 for any x = (s, a) E S x A, and h E [H].
min (g(x; Wo), wi (g(x; Wo), wh!" on 0xl1g(>; Woll M
Setting 8 = SAH(1 M completes the proof.
35

---

Published as a conference paper at ICLR 2023
F.4 PROOF OF LEMMA E.4
In this subsection, we provide a detailed proof of Lemma diate lemma whose proof is deferred Subsection E5 Lemma F.2. Let
E.4
We first prove the following interme-
m = Q (d// R log 3/2 (Vmm Rt) R= O (m log 33 m)
and additionally let
1/ S (K'Cg 9 + 1/2)-11
11 S 2x.
Then with probability least B(Wo; R) for any j' E [i], then
MHm for any (i,j,h) E [M] [J] Mn if wh(l)
[155 - 5 z / K'HH + )2 Xr, + (2n)-2 1/6 log m..
We now can prove Lemma E.4
Proof of Lemma E.4
To simplify the notations, we define
A = w,,0)) -W -.).i...))
E g
G3 = (0(02 w KEIN
E mdmdx K
Hy = G Rmddmmd
f = (Jaah: wh()))))))))
E ERA
KEIn
ÿ (h ERK
KEIn
The gradient descent update rule for 177h.10 in Equation 9 can be written as:
W (.+1)
W/.00 17 G, 9) + x(WA + + - -Wo)
The auxiliary updates in Equation
15) can be written as:
Wr di., W.i.iin.. 7 Go GG (W (im...) Wo) b) + X(W + + - -Wo]
Step I: Proving W)7,0)) E B(W;; R) for all j. In the first step, we prove by induction that with h probability least 1 MHm - for any (i,j. h) E [M] x [J] x [H] we have
wr(0 E B(W;: R).
In the rest of the proof, consider under the event that Lemma F2 holds. Note that the condition
in Lemma E. satisfies that of Lemma F.2 and under the above event of Lemma F22 Lemma G.I G.Iandd and Lemma F. both hold. It is trivial that
W Wo E B(W;; R).
For any fix j 2 0, we assume that
W
B(Wo: R), Vj G].
(42)
We will prove that +1)
E B(W; R). We have
36

---

Published as a conference paper at ICLR 2023
(1 nAja, - -n -n(Goll; -
GT -G(Golls-GT(V Wo)) + GoG (W W.llii,.()) + (8z D) - Gol
(I(T n(T+ Hol)a, + nllss 0||l||G Golla + m|lGollal1s, (W (W
Wo)ll2
13
We bound I1 I2 and Is separately. Bounding 4. For bounding 41
[I(I 17(A Ho))
$ - [[T--n(A + Ho)l221Aagll
(1 7/ K2 14,l12
(1 n
where the first inequality holds due to the spectral norm inequality, the second inequality holds due
T(A Ho) 3 7(> || 7(A K' C 1
where the first inequality holds due to that H, < Ho N |Go I the second inequality holds due to that Gooll & VKC, due to Lemma G.1 and the last inequality holds due to the choice of in Equation (40).
Bounding 12. For bounding 12.
1a nlifs 5112||G5 Gollz
$ nIlfs 5ll2 max v WK'll ( Wh())) s(x Wo KEZn
< Si JlllV'' K C R /3 1/6 Vlogm
< ny 2K + + + 12 + Xni, + 8C,R4/3m 1/6 // m/ Vlog
Vlog m
where the first inequality holds due to Cauchy-Schward inequality, the second inequality holds due the induction assumption in Equation (42) and Lemma G.1 and the third inequality holds due to Lemma F22 and the induction assumption in Equation 42
Bounding Iz.
For bounding Iz.
13 n|lGollallss - Wo)ll2 &. whl p( (WW.0) -Wol
< S K" max (1 KEIN
< <nK"C,R"0 Vlg
where the first inequality holds due to Cauchy-Schwarz Schwarz inequality and due to that Golle S VK', and the second inequality holds due the induction assumption in Equation (42) and Lemma G.1 Combining the bounds of I, Iz, Ig above, we have
|| ll2 S (1 - A))lAA + 12 + Tz-
Recursively applying the inequality above for all j. we have
1 + 1
R
R
R 2
|4 12
(43)
n
where the second inequality holds due the choice specified in Equation 40
We also have
A|| W. (i+1) + Ch. Woll2 < 2L),in (W, (in.)l...(+1))) 27 (Wr (U))
37

---

Published as a conference paper at ICLR 2023
Σ TETn
(a(a Wo), Wo) -i
-0 (Uh (2 + 1115211
KEI
S K v + 1) 2 + 27
(44)
, where the first inequality holds due the the definition of f. (Wr (in. )) the second inequality
holds due to the monotonicity of Iii.ii (W) on the gradient descent updates ( (Wri.lin.((") }}- for the I.j
squared loss on a linear model, the third equality holds due to (a(*%; Wo). Wo) = 0 from the
symmetric initialization scheme, and the last inequality holds due to Lemma F.T Thus, we have
[ h
(ii.iin Wolla - V W (i+1 + Ch. Woll3 + 11%
22 BA-IK' K' + 2 + 7h, + 4
V
(45)
2
where the first inequality holds due to Cauchy-Seiie -Schwaz inequality, the second inequality holds due to Equation (44 and Lemma F.I and the last inequality holds due to the choice specified in Equation
40
Combining Equation
43) and Equation
45
we have
(
-Wol s
|| (i++) W
Wo
R = R,
2
2
where the first inequality holds due to the triangle inequality.
Step 2: Bounding [1 W 112. By the standard result of gradient descent on ridge linear regression, Wr((5) converges to Wiidin with the convergence rate,
(0)
W (.6. W.
12 < (1 - nン) A ([(W)) - L(W
$ (1 - イ2>s 2
x ((WW)
$ xx- nal (K' (H + 2 + 7m,2) + Anih.))
Thus, for any have
Wr
112 || W...kin.1) 1|2 1 wi.. W
< (nA)-1(14 (12 - 13) - my (K' + 3 + mh.1) + X)) (46)
where the first inequality holds due to the triangle inequality, the second inequality holds due to Equation 43 and Equation (46).
F.5 PROOF OF LEMMA
Proof of Lemma F.2
We bound this term following the proof flow of (Zhou et al. 2020 Lemma C.3) with modifications for different neural parameterization and noisy targets. Suppose that for some fixed j.
wh.0") E B(Wo: R), Vj' D].
(47)
Let us define
G(W) (a(at) W)) KEIn E mdd
38

---

Published as a conference paper at ICLR 2023
f(W)= ()) ER", e(W', W) == f(w") - f(W) G(W)) [0r W) E R.
To further simplify the notations in this proof, drop i in (W) defined in Equation write (,WW) as L(W) and write W WW= where
to
1 Σ (s(af) W) ) 2 @ + + Woll3
L(W)
2
KEZn
2 ([((W) 0012 + I + 5% - Woll
Suppose that W E B(W;; Rt. By that -1. is 1-smooth,
L(W") L(W) S (f(W) V. f(W') f(W)) +
+ +(W + c - Wo, W - -w) + A S|l - -
2
- =(S()) - 5. G(W)) (W' - -W) + +e(W", W)) + 2
[w'") w) + e(W", w)
+ A(W + ch - Wo, W - -W) + 2l - -W1
-(VLW),, -W) W)
(J(W)- - -.,e W)) + (w'w))(ww'-- w) + e(W", w)) + I| - wlB. (48)
For bounding It.
+ K'C Maleee""))lleeel. - w/B + Ile(W" w)lB + X I - W/
41 S [I(W)- - illalle(W', W)ll [[(WW) (ellal((""))lll++ +
2
W))l2
4/2) w + l|e(W' W)ll.
(49)
where the first inequality holds due to Cauchy-Schward inequality, W E B(W;; It) and Lemma Substituting Equation (49) into Equation (48) with W = W - -vVi.W,,
G.1
L(W") L(W)= < -n(1 (KC) x/2)m) + IIf(W) Ulla|le(W' ,W]l2
+ ||e(W", W)
(50)
By the 1-strong convexity of || 112 for any W'
L(w') - L(w)= 2 (f(W)- ū. f.f'") - f(W)) + X(W + c/ Wo, W -W) + A
2 W' W11
= =(S(W) - 5. G(W) (W' - -W) +e(W', W)) + A(W + +h - Wo, W
W) + 2
W' - W|
= -(Vi(W), W' W) + (f(W) - 8. j.e(W' W)) + 2 I -
/VL(W) (IS(W) "llelle(W', w)ll2.
(51)
2A
where the last inequality holds due to Cauchy-Schwarz inequality. Substituting Equation (51) into Equation (50). for any W".
L(W- - vWW) i(W)
< 21m(1 (KC2 x/2)m) (R(W") i(() + (1f(W) - Vllalee(W', w)lla)
+ -I((W) ollalee(W v/Vi(ww, W) + |le(W - VVWWw. w)lB
39

---

Published as a conference paper at ICLR 2023
a L(W") - L(W)+ + 7i
マ/2 [[](W) - 511 + 271
leeW"', w1
+
22 (lW())) 51l2 +
1
Ie(W- -nvi(w) will + |Ie(W - -vi((v w)ll
2
272
s ((WW)) T.(W) 71 I(W)+ +
271 |e(W",
1
1 lee(W - -/vii(/) w)ll + l - (V),(W),)))
+ 72 (())
(52)
2722
where the second inequality holds due to Cauchy-Schwarz Schwarz inequality for any 71. 72 and the third inequality holds due [[f(W) - E v WW).
Rearranging terms in Equation (2) and setting W = -W W W' = Wo. 7 = = 72 = 7/
L(1 - I(Wo) s (1 a am + +2) - -1- () -11-3 + a ((W)) 2
1 _ [W w,) + ||eeWW j+,, W3)1
+ 2
le(Wo: W,)11
272
(1
(i(W,) - -[(W)) + - ((w) + 2a/le(Wo, Wy)1
2
2
+ (1 + )|e(WW WWy)l
a _ (i(W)) - I(wo)) + a ((w)) + (1 2 a
$ (1
2a)e,
(53)
2
where e := C/3 m 1/6 Vlog m, the last inequality holds due to Equation (47) and Lemma
G.1
Applying Equation (33. we have
2 + 2aje Ż(w,) i(W)) - 2 / - L()W) + +1+
Rearranging the above inequality,
L(W,) & wi) + (
2 + 4)e
+ a²
a
where the last inequality holds due to the choice of 17. Finally, we have
Ils 512 < 2i,
and i(W)) -11011 + SICI (H + 72,)2 2 due Lemma F.1
G SUPPORT LEMMAS
Lemma G.1. Let m = 52 (18/2R-1 1og3/ (v R)) and R = O (m log 3 m). With probabil-
ity at least 1 - -S0ls m) > 1 - m with respect to the random initialization, it holds for any
W, W' E B(W;; R) and æ S that
|1 W)ll2 s Cg,
/ Vlog m If(z; W) - (x) - (g(x:W), w'l = 0 (C,R*/33mmv Vlgm
l1((;; g(:; Wo)lla < (c,, (C,R)//3 11/6
where C2 = (()) is constant independent of d and m. Moreover, without loss of generality, we assume C 1. 1.
Proof of Lemma C.1 Due to Yang et al.) 2020 Lemma C.2) and (Cai et al. 2019 Lemma F.2),
we have the first two incqualities and the following:
[s W) - (0(2; Wo), W - Woll s 50 (C,n2V23 - 1/66 Vlogm
40

---

Published as a conference paper at ICLR 2023
For any W, W E B(W: R),
f(;; W) f(z; W') (o(x; W WW"
f(;; W) - (g(0; Wo), W - -W) -(fE:;") Wo), W -W))
+ (0(0;; Wo) s(2; W Wo - W-W)
Thus,
If(x; f(;; W (9(2; W'), - W')
$ {l{0;; W) - (0(2;; Wo), W +1]1+1/(;;W)) (0(2; Wo), W Woll
11o(1; Wo) ,(x; ( W' (C,R
" 1/6
Vlogm)
Lemma G.2 AAror et al.
2019
Theorem 3)). If m 22( (og([(/))))) then for any a, x' E X C
Sd-1. with probability at least 1 5.
Ko r; Wo), g (x, Wo)) Knek (2, x²)l 5 2c.
Lemma G.3. Let X aA
aA- be d-dimensional normal variable where is a sealar. There exists an absolute constant > 0 such that for any 8 >> 0, with probability at least 1 5,
|| S cv da log(d/8).
For d = 1, c= V2.
Lemma G.4 (A variant of Hoeffding-Azume inequality). Suppose {Z is real-valued {Fx 100 o== i.e. Vk, Za is Fa-measurable. Suppose
stochastic process with corresponding filtration filtraaton
that for any k, Zx] < oc and 1 1
FR
S Og almost surely. Then for all positive
and f, we have:
n
n
t2
Σ
ZE
E ZZ
28
S 2 exx
1=1
Lemma G.5 (Chowdhury & Gopalan 2017 Theorem 1)), Let H be an RKHS defined over X C Rd. Let { be a discrete time stochastic process adapted to filtration {Fi]i=o Let { be a real-valued stochastic process such that Zy. E Fk. and Zy is zero-mean and o-sub Gaussian conditioned on Fk-1- Let Eg (Zi...., Zz-1) RR-1 and Kr be the Gram matrix of H defined on {2t 111----11 For any p > 0 and 8 E 1). with probability at least 1 8,
EY [KC+ + p + Es s o² logdet [[1 [1+ (1+ Kck] + 20 log(1/8).
Lemma G.6. For any matrices A and B where A is invertible,
logdet(A + B) S logdet(A) (A) + -ttrrAA1 B).
Lemma G.7. For any invertible matrices A, B,
||A- Bll2 Amiu Amin(()) (A) (B)
| B 1 S
Proof of Lemma G.7 We have:
A -1
B B- = (AB) B-1
((AB))((AA*" (ABA-I A)
< [[(AB) ([AAB)"'[]]ABAA' - All2
II(AB) '121AABA AAA- 1|2
[[(AB) 112||A(BB AAAA-112
-I(AAB 112 All2
S Amax (A ) (B- B-1))|2]| All2-
41

---

(AHf(K) - -1 thus f(K) 1, Thus, with Published as a conference paper at ICLR 2023
Lemma G.8 (Freedman's inequality (Tropp 2011 Let [Xx]k=1 be real-valued martin-
gale difference sequence with the corresponding filtration [F ie. Xx is Fi-mmasurrable and E [ [R-1]
0. Suppose for any k, Xxl M almost surely and define V
Σ k= E X F For any a, b > O, we have:
1
a
IP
Σ
Xu
2a2 56
S eex 2b + 20M/3
In an alternative form, for any & O. we have:
2Mt
P
Xx
+ 2bt, V $b) Se:
Lemma G.9 (Improved online-to to-batch argument Nguyen- Tang et (2023 Let {Xx} be any
real-vat veal-valued stochastic process adapted to the filtration { L.e Xς is Fa-measurable. Suppose that for any Xx E [0, H] almost surely for some >> For any K O. with probability at least
1 - 6, we have:
K
16 3
E F
<
Σ 1=1
X
H (logg (KH)/0) + +
Proof of Lemma C.9. Let =x and a real-valued difference martingale with the corresponding filtration {F&} and that
E [[ We have Za
K
K
K S
V=
E
E
E [[xx
HJ(K).
k=1
k=1
k=1
Note that IZ
H and f(K)
[H and let
loga (KH). Also note that f(K)
ΣK X
EK
Z 2
E Zz. Thus D K
Zs S 1, we have f(K) 2 1. For any 0,
k=1
leveraging the peeling technique (Barlettt et al. 2005
we have:
2Ht
P
2x
VAHf(K)E-1
K
2HL
7 S
V4HS(KM-11JJCM [1,)
3
K
2Ht
IP
Σ
2x <
( 12')
3
1=1
1=1
m
2HE
Σ PP
Σ
Zk <
V4H2 1, < H2' f(K) 12 22)
3
4=1
7
2Ht
IP
Σ Zx <
V2H2H, V s H2
3
1=1
m
me=
where the first equation is by that ΣK Ze <
K
2ft
the second inequality is by that V < Hf(K), and the last inequality is by Lemma G.8 probability least 1 me we have:
K
2Ht.
Xx Σx
f(K) Σ
Z
VAHf(K)t 1.
The above inequality implies that S(K) < >
k= X + 4H1/3 4HL, due the simple
inequality: if x S a/= b. a² 2b. Then setting &. log(m/8) completes the proof. n
42

---

Published as a conference paper at ICLR 2023
H BASELINE ALGORITHMS
For completeness, we give the definition of linear MDPs as follows.
Definition (Linear MDPs (Yang & Wang 2019 Jin et al. 2020)). An MDP has a linear structure for any (s, s', ft), have:
(h(s, (s, On, Pn (s a)² p)
where Φ S x A - RRdis is a known feature map, On E Rdin is an unknown vector, and S - Rdin unknown signed measures.
We also give the details of the baseline algorithms: LinLCB in Algorithm 3 LinGreedy in Algorithm MiPeR Algorithm 5 NeuraLCB in Algorithm 6 and NeuralGreedy in Algorithm For simplicity, we do not use data split in these algorithms presented here.
Algorithm 3 LinLCB (Jin et al.
2021)
1: Input: Offline data D {(5 ai xn) kE[K]
(M)
uncertainty multiplier (3, regularization parameter
A.
2: Initialize V (.) x 0
3: for H..... do
4: As + Ek=1 @(s . a (ss aft + Xl
5:
On Ex Ex= on ( a (rh + Vn+z(sh+1))
6:
ba(:,)) t (. )bs
7:
Qn(:.)) minf (0) (t. 0n) - -
8:
fn < arg max,, (2., Tn) and V + (2h,
9: end for
Output: (nn nE(H]
Algorithm 4 LinGreedy
[k[[k] straps M, regularization parameter A.
Input: Offline data D ( an ( perturbed variances {or heeBBr number of boot-
2: Initialize VH+1( (-) +
3: for h = HI.... do
4: On Σ- ΣK on (sh (rā Vnti (541
5: Qn(,,)) + minl (on 0,),,, H h + +1+.
6:
#n <- arg max (Qn, Tn) and 1 <- a
7: end for
8: Output: a = (ft [nem
43

---

Published as a conference paper at ICLR 2023
Algorithm Lin-R
1: Input: Offline data D (s a (x)) he(M) perturbed variances far heear. number of boot-
k
straps M, regularization parameter A.
2: Initialize VH++1 (-)
3: for = H..... do
An + ΣK 1= Φ(s a ( aft a + Al
4:
5: for i = 1, 1..... M do
6:
Sample "
breik Solve the perturbed regularized least-squares regression:
NO of) and S "ih
Leeld (00,
7:
K Σ
(10 a),,) 0) - (r% + ( + ) + Allo - 1h11.
0 < arg max
BERd 1=1
8:
end for
9:
Compute (-) t m ().-))))))))))
13
10: TA < arg max (2n, Tn) and VA, + (Qn, 7x)
end for
12:
Output: ă = f [nEm
Algorithm 6 Neural.CB (a modification of Nguyen-Tanng et al. 2022aa)
Input: Offline data D {(s at, 1 Te))) neural networks F {f W) W W) c
ke
(X' + IR). uncertainty multiplier B, regularization parameter X, step size v). number of gradient descent steps
2: Initialize (-) 0 and initialize f(. W) with initial parameter Wo
3: for h H,..., do
4: Wh. + GradientDescent((, n, J, (ss at, (())kE(K)) O, Wo) (Algorithm)
5: A₁ = Ar + +E g( ah; Wa)g(ak; W,)²
6: Compute (- + min(s(, Wn) - 3 1 1]
7: tn < arg ma (Q,, Tn) and V% + (Qn,
8: end for
9: Output: # = ) hE(H)
Algorithm 7 NeuralGreedy
1: Input: Offline data D { at, r kE hE(H) neural networks F (f(.:: W e W) c
(X > RR, uncertainty multiplier 8, step size 1), number of gradient descent steps J
2: Initialize (.)+ +- 0 and initialize [(, W) with initial parameter Wo
3: for = H,..., do
4: Wr, +- GradientDescent((, n) J, (( a r ((]ek) O, Wo) (Algorithm
5: Compute Qn(:,)) <- min(s(, W.), - - 11+
6: tn arg max (Qn, Tn) and V. (A)
7: end for
8: Output: A hneen-
44


Reviews:
[{"review_id": "zbFpx_5OhOH", "reviewer": "Reviewer_Svop", "summary": "", "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": "", "summary_of_the_paper": "This paper proposes the PEturbed-Reward Value Iteration (PERVI) which combines the randomized value function idea with the pessimism principle. PERVI only needs $O(1)$ time complexity for action selection while LCB-based algorithms require at least $\\Omega(K^2)$, where $K$ is the total number of trajectories in the offline data. It proposes a novel data splitting technique that helps remove the potentially large log covering number in the learning bound. PERVI yields a provable uncertainty quantifier with overparameterized neural networks and achieves an $\\tilde{O}(\\frac{\\kappa H^{5/2}\\tilde{d}}{\\sqrt{K}})$ sub-optimality. statistical and computational efficiency of PERVI is validated with an empirical evaluation in a wide set of synthetic and real-world datasets.", "summary_of_the_review": "This paper overall has a high quality and provides complete study of neural network approximation for offline RL. If the authors can address my concern in above, I am happy to keep my score.", "strength_and_weaknesses": "Strength: This paper combines the randomized value function idea and the pessimism principle. In addition, this paper proposes a novel data splitting technique that helps remove the dependence on the potentially large log covering number in the learning bound. The authors empirically corroborate the statistical and computational efficiency of our proposed algorithm in a wide set of synthetic and real-world datasets. \n\nWeakness: 1. Your assumption 5.1 requires for any $H+1$-bounded function, Bellman update maps it to $Q^*$. What will happen if your function has $\\epsilon$-misspecified error, i.e. $\\inf_{V}\\sup_{||V'||_\\infty\\leq H+1}\\|\\|B_h V-V'\\|\\|_\\infty \\leq \\epsilon$, how will the $\\epsilon$ model error affect your results? You don't need to derive the result for this case but explain in a few sentences is fine.\n\n2. While Appendix B.1 already provide a nice comparison with Xu&Liang,2022, they consider a different setting where only trajectory reward is observed. If the per-step award is aware, how would their result be like and how would it compare to PERVI? I am asking this since in your setting per-step reward is aware, so I am wondering which of the two methods would be better under this case.\n\nMinor: The recent paper https://arxiv.org/pdf/2210.00750.pdf also considers the pessimism offline RL with parametric function class. How is your result compared to theirs since both results contain the similar measurement $\\sum_{h=1}^H ||g(x;W_0)||_{\\Lambda_h^{-1}}$ in the suboptimality bound? \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "wDeIGH3AelQ", "reviewer": "Reviewer_69m1", "summary": "", "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": "", "summary_of_the_paper": "This paper looks at the problem of reinforcement learning from offline data.\nThey authors introduce PERVI, which uses \"randomized value functions\" to generate an approximate posterior distribution over value functions, and then acts pessimistically with respect to those estimates for safety.\nThe authors support their new algorithm through an analysis in tabular MDPs, as well as more empirical evaluation with neural network function approximation.", "summary_of_the_review": "This paper presents PERVI, a combination of randomized value functions with pessimism for offline reinforcement learning.\nThe paper takes mostly-existing concepts but combines them in a more elegant and coherent framework than previous papers I have seen.\nThe resultant algorithm is sane and sensible, and the progression of support from intuition to analysis to empirical results is comprehensive.\n\nIn terms of \"the grand challenge\" of offline RL I think this algorithm leaves potentially a lot of value on the table.\nHowever, I do think this is a valuable piece of the literature and will be useful to the conference.", "strength_and_weaknesses": "There are several things to like about this paper:\n- The problem of RL and decision making with offline data is an important one for the community.\n- The PERVI algorithm passes a \"sanity check\" intuitively... by this I mean that it's not just an algorithm for a proof... but you have a sense this is something close to something someone would actually want to use.\n- The quality of the writing and presentation in the paper overall is very high.\n- The paper has a progression of intuition, to hard theoretical guarantees in simple settings, to empirical success in more complex settings. I like the way of analysing problems with overparameterized NTK!\n- Discussion of related work and the key intuitions for the approach appear to be pretty comprehensive for a short paper, although I am likely missing important pieces.\n\nThere are some places where the paper probably could be further strengthened:\n- In some sense, many of the results and analyses are sort of incremental. The application of randomized value functions plus pessimism has existed before, but this is a slightly new twist on that as opposed to a \"game changing\" new perspective.\n- Some of the ways the Theorems are presented are really messy... you need to read through lines and lines of bizarre constants/terms to even get to the result!\n- Something must be missing (at a high level) from these theorems, since they don't really expose clearly a dependence on the *quality* of the offline data... an algorithm should be able to learn very differently when the demonstration data is very good, versus when it is very bad... and a good algorithm should be able to kind of work that out and leverage it.\n- Why do you use the term \"SubOpt\" instead of regret?\n- Does PERVI (pervy?) raise some of the issues that NeurIPS (nips) had to deal with?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "owI-jYTEZ6", "reviewer": "Reviewer_NEMf", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "", "summary_of_the_paper": "The paper studies offline RL problems with perturbed rewards. In particular, the Q function will be parametrized as the minimum of $M$ neural networks, trained on $M$ perturbed datasets. The benefit of the proposed algorithm, compared to the UCB-based method is reducing the time complexity of action selection. On a technical side, the authors propose a data splitting analysis technique to improve dependence on log covering the number in the sample complexity result.", "summary_of_the_review": "The idea of learning Q functions from the perturbed datasets and thus implicitly implementing the pessimism principle is neat. Theoretical analysis and preliminary experiments illustrate the potential usefulness of the proposed algorithm. I suggest a marginally accept. However, I'm not familiar with the main related papers cited in this work, so I choose a confidence score of 2.", "strength_and_weaknesses": "Strength:\n\nThe proposed neural network-based offline RL algorithm is new. In appendix B3 the authors compare with existing literature on the sample complexity results. \n\nWeakness:\n\nI did not spot any major errors in the paper. However, I have several minor technical questions:\n\nQ1. In line 10 of Algorithm 1, shouldn't we take argmax over action space?\n\nQ2. A related question is, how is the argmax implemented in code since we are considering the large space-action space?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ayACPlVnYS", "reviewer": "Reviewer_EhDB", "summary": "", "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": "", "summary_of_the_paper": "This paper proposes a novel approach to pessimism-based offline RL. Instead of the standard practice of explicitly constructing a lower confidence bound for value functions, this new approach uses perturbed rewards to implicitly quantify the training uncertainty and construct lower confidence bounds for the ground truth. Such an approach is argued to improve the practicality of pessimistic offline RL especially in situations where the value functions are approximated by large neural networks, whence the large scale model elucidates traditional theoretical analysis. The theoretical property of this approach is studied in overparametrized neural networks with gradient descent training. Empirical experiments are conducted to show the favorable performance of the proposed approach. ", "summary_of_the_review": "I find this to be a strong paper. The idea of using randomized rewards in pessimism-based offline RL is clever, and the theoretical analysis is nontrivial and solid. Empirical studies are conducted to support the arguments. However, I think the presentation of the results can be improved, and more discussion on the relation to the literature is need. ", "strength_and_weaknesses": "Strengths:\n\n1. A novel algorithm to pessimism. \n\nThis work contributes to the literature of offline RL by proposing a solid and practical approach to constructing confidence lower bounds. This idea is clever and refreshing. It is both practically useful and theoretically interesting. \n\n2. Solid theoretical results.\n\nThis paper provides solid theoretical analysis. It is quite invovled but I think it will be useful for future works in the literature. \n\n\nWeaknesses:\n\n1. Clarity of results. \n\nA drawback (which I think can be resolved to some extent) is that although the overall idea is clean, the presentation is way too overwhelming. For example, it will help the readers if important steps in the algorithms can be explained / highlighed / commented, or given more wording in explaining their roles. Also, Theorem 1 poses a huge challenge to the whole flow as the conditions are too complicated. I will suggest replacing it with an informal theorem, and put all these conditions to the appendix. \n\n2. Relation to the literature. \n\nAlthough the authors generally did a good job in relating to the literature, more discussion on the novelty of this idea can further improve this work and posit this paper appropriately in the literature. For instance, 1) how does the construction of uncertainty quantification differ from that in the online setting (e.g., Jia et al. 2022)? Is there special tricks for dealing with distribution shift? 2) how does the analysis of 2-layer neural networks rely on existing ones, and which parts are specific to the new offline setting? etc.\n\nQuestions:\n\n1. Since $\\mathcal{Q}^*$ is used for fitting the networks, I am curious about the definition of $\\mathcal{Q}^*$. Is it equivalent to the class of 2-layer neural networks with ReLU activation, or is it a superset of it? \n\n2. What is the relationship between $\\mathcal{H}_{ntk}$ and the class of 2-layer NN with ReLU activation? Please clarify this to help the readers.\n\n3. The conditions in Theorem 1 are too lengthy. Is it possible to reduce it to a cleaner version (potentially with some harmless relaxation)?\n\n4. It will help if there is a sketch or overview of the key theoretical techniques in Theorem 1. For example, why do the randomized rewards lead to a valid uncertainty quantifier. \n\nMinor issues: \n\n1. The last sentence in Section 4 is difficult to read. What does it mean by `` with a provable implicit uncertainty quantifier and $\\tilde{\\mathcal{O}}(1/\\sqrt{K})$''?\n\n2. Remark 1 is a bit difficult to read. What does it mean by ``data-dependent quantity that measures the number principle dimensions over which the..\"?\n\n3. What does $\\sigma'$ mean in Definition 1? Please provide a formal definition.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%