Year: 2021

Abstract:
Offline policy learning (OPL) leverages existing data collected a priori for policy optimization without any active exploration. Despite the prevalence and recent interest in this problem, its theoretical and algorithmic foundations in function approximation settings remain under-developed. In this paper, we consider this problem on the axes of distributional shift, optimization, and generalization in offline contextual bandits with neural networks. In particular, we propose a provably efficient offline contextual bandit with neural network function approximation that does not require any functional assumption on the reward. We show that our method provably generalizes over unseen contexts under a milder condition for distributional shift than the existing OPL works. Notably, unlike any other OPL method, our method learns from the offline data in an online manner using stochastic gradient descent, allowing us to leverage the benefits of online learning into an offline setting. Moreover, we show that our method is more computationally efficient and has a better dependence on the effective dimension of the neural network than an online counterpart. Finally, we demonstrate the empirical effectiveness of our method in a range of synthetic and real-world OPL problems.

heading: 1 INTRODUCTION
text: We consider the problem of offline policy learning (OPL) (Lange et al., 2012; Levine et al., 2020) where a learner infers an optimal policy given only access to a fixed dataset collected a priori by unknown behaviour policies, without any active exploration. There has been growing interest in this problem recently, as it reflects a practical paradigm where logged experiences are abundant but an interaction with the environment is often limited, with important applications in practical settings such as healthcare (Gottesman et al., 2019; Nie et al., 2021), recommendation systems (Strehl et al., 2010; Thomas et al., 2017), and econometrics (Kitagawa & Tetenov, 2018; Athey & Wager, 2021).
Despite the importance of OPL, theoretical and algorithmic progress on this problem has been rather limited. Specifically, most existing works are restricted to a strong parametric assumption of environments such as tabular representation (Yin & Wang, 2020; Buckman et al., 2020; Yin et al., 2021; Yin & Wang, 2021; Rashidinejad et al., 2021; Xiao et al., 2021) and more generally as linear models (Duan & Wang, 2020; Jin et al., 2020; Tran-The et al., 2021). However, while the linearity assumption does not hold for many problems in practice, no work has provided a theoretical guarantee and a practical algorithm for OPL with neural network function approximation.
In OPL with neural network function approximation, three fundamental challenges arise:
Distributional shift. As OPL is provided with only a fixed dataset without any active exploration, there is often a mismatch between the distribution of the data generated by a target policy and that of the offline data. This distributional mismatch can cause erroneous value overestimation and render many standard online policy learning methods unsuccessful (Fujimoto et al., 2019). To guarantee an efficient learning under distributional shift, common analyses rely on a sort of uniform data coverage assumptions (Munos & Szepesvári, 2008; Chen & Jiang, 2019; Brandfonbrener et al., 2021; Nguyen-Tang et al., 2021) that require the offline policy to be already sufficiently explorative over the entire state space and action space. To mitigate this strong assumption, a pessimism principle that constructs a lower confidence bound of the reward functions for decision-making (Rashidinejad et al., 2021) can reduce the requirement to a single-policy concentration condition that requires the
coverage of the offline policy only on the target policy. However, Rashidinejad et al. (2021) only uses this condition for tabular representation and it is unclear whether complex environments such as ones that require neural network function approximation can benefit from this condition. Moreover, the single-policy concentration condition still requires the offline policy to be stationary (e.g., the actions in the offline data are independent and depend only on current state). However, this might not hold for many practical scenarios, e.g., when the offline data was collected by an active learner (e.g., by an Q-learning algorithm). Thus, it remains unclear what is a minimal structural assumption on the distributional shift that allows a provably efficient OPL algorithm.
Optimization. Solving OPL often involves in fitting a model into the offline data via optimization. Unlike in simple function approximations such as tabular representation and linear models where closed-form solutions are available, OPL with neural network function approximation poses an additional challenge that involves a non-convex, non-analytical optimization problem. However, existing works of OPL with function approximation ignore such optimization problems by assuming free access to an optimization oracle that can return a global minimizer (Brandfonbrener et al., 2021; Duan et al., 2021; Nguyen-Tang et al., 2021) or an empirical risk minimizer with a pointwise convergence bound at an exponential rate (Hu et al., 2021). This is largely not the case in practice, especially in OPL with neural network function approximation where a model is trained by gradient-based methods such as stochastic gradient descents (SGD). Thus, to understand OPL in more practical settings, it is crucial to consider optimization in design and analysis. To our knowledge, such optimization problem has not been studied in the context of OPL with neural network function approximation.
Generalization. In OPL, generalization is the ability to generalize beyond the states (or contexts as in the specific case of stochastic contextual bandits) observed in the offline data. In other words, an offline policy learner with good generalization should obtain high rewards not only in the observed states but also in the entire (unknown) state distribution. The challenge of generalization in OPL is that as we learn from the fixed offline data, the learned policy has highly correlated structures where we cannot directly use the standard concentration inequalities (e.g. Hoeffding’s inequality, Bernstein inequality) to derive a generalization bound. The typical approaches to overcome this difficulty are data splitting and uniform convergence. While data splitting splits the offline data into disjoint folds to break the correlated structures (Yin & Wang, 2020), uniform convergence establishes generalization uniformly over a class of policies learnable by a certain model (Yin et al., 2021). However, in the setting where the offline data itself can have correlated structures (e.g., an offline action can depend on the previous offline data) and the model used is sufficiently large that renders a uniform convergence bound vacuous, neither the data splitting technique in (Yin & Wang, 2020) nor the uniform convergence argument in (Yin et al., 2021) yield a good generalization. Thus, it is highly non-trivial to guarantee a strong generalization in OPL with neural network function approximation from highly correlated offline data.
In this paper, we consider the problem of OPL with neural network function approximation on the axes of distributional shift, optimization and generalization via studying the setting of stochastic contextual bandits with overparameterized neural networks. Specifically, we make three contributions toward enabling OPL in more practical settings:
• First, we propose an algorithm that uses a neural network to model any bounded reward function without assuming any functional form (e.g., linear models) and uses a pessimistic formulation to deal with distributional shifts. Notably, unlike any standard offline learning methods, our algorithm learns from the offline data in an online-like manner, allowing us to leverage the advantages of online learning into offline setting.
• Second, our theoretical contribution lies in making the generalization bound of OPL more realistic by taking into account the optimization aspects and requiring only a milder condition for distributional shifts. In particular, our algorithm uses stochastic gradient descent and updates the network completely online, instead of retraining it from scratch for every iteration. Moreover, the distributional shift condition in our analysis, unlike in the existing works, does not require the offline policy to be uniformly explorative or stationary. Specifically, we prove that, under mild conditions with practical considerations above, our algorithm learns the optimal policy with an expected error of Õ(κd̃1/2n−1/2), where n is the number of offline samples, κ measures the distributional shift, and d̃ is an effective dimension of the neural network that is much smaller than the network capacity (e.g., the network’s VC dimension and Rademacher complexity).
• Third, we evaluate our algorithm in a number of synthetic and real-world OPL benchmark problems, verifying its empirical effectiveness against the representative methods of OPL.
Notation. We use lower case, bold lower case, and bold upper case to represent scalars, vectors and matrices, respectively. For a vector v = [v1, . . . , vd]T ∈ Rd and p > 1, denote ∥v∥p = ( ∑d
i=1 v p i ) 1/p and let [v]j be the jth element of v. For a matrix A = (Ai,j)m×n, denote ∥A∥F =√∑ i,j A 2 i,j , ∥A∥p = maxv:∥v∥p=1 ∥Av∥p, ∥A∥∞ = maxi,j |Ai,j | and let vec(A) ∈ Rmn be
the vectorized representation of A. For a square matrix A, a vector v, and a matrix X , denote ∥v∥A = √ vTAv and ∥X∥A = ∥ vec(X)∥A. For a collection of matrices W = (W1, . . . ,WL)
and a square matrix A, denote ∥W ∥F = √∑L l=1 ∥Wl∥2F , and ∥W ∥A = √∑L
l=1 ∥Wl∥2A. For a collection of matrices W (0) = (W (0)1 , . . . ,W (0) L ), denote B(W (0), R) = {W = (W1, . . . ,WL) : ∥Wl −W (0)l ∥F ≤ R}. Denote [n] = {1, 2, . . . , n}, and a ∨ b = max{a, b}. We write Õ(·) to hide logarithmic factors in the standard Big-Oh notation, and write m ≥ Θ(f(·)) to indicate that there is an absolute constant C > 0 that is independent of any problem parameters (·) such that m ≥ Cf(·).

heading: 2 BACKGROUND
text: In this section, we provide essential background on offline stochastic contextual bandits and overparameterized neural networks.

heading: 2.1 STOCHASTIC CONTEXTUAL BANDITS
text: We consider a stochastic K-armed contextual bandit where at each round t, an online learner observes a full context xt := {xt,a ∈ Rd : a ∈ [K]} sampled from a context distribution ρ, takes an action at ∈ [K], and receives a reward rt ∼ P (·|xt,at). A policy π maps a full context (and possibly other past information) to a distribution over the action space [K]. For each full context x := {xa ∈ Rd : a ∈ [K]}, we define vπ(x) = Ea∼π(·|x),r∼P (·|xa)[r] and v∗(x) = maxπ vπ(x), which is attainable due to the finite action space.
In the offline contextual bandit setting, the goal is to learn an optimal policy only from an offline data Dn = {(xt, at, rt)}nt=1 collected a priori by a behaviour policy µ. The goodness of a learned policy π̂ is measured by the (expected) sub-optimality the policy achieves in the entire (unknown) context distribution ρ:
SubOpt(π̂) := Ex∼ρ[SubOpt(π̂;x)], where SubOpt(π̂;x) := v∗(x)− vπ̂(x).
In this work, we make the following assumption about reward generation: For each t, rt = h(xt,at)+ξt, where h : Rd → [0, 1] is an unknown reward function, and ξt is a R-subgaussian noise conditioned on (Dt−1,xt, at) where we denote Dt = {(xτ , aτ , rτ )}1≤τ≤t,∀t. The R-subgaussian noise assumption is standard in stochastic bandit literature (Abbasi-Yadkori et al., 2011; Zhou et al., 2020; Xiao et al., 2021) and is satisfied e.g. for any bounded noise.

heading: 2.2 OVERPARAMETERIZED NEURAL NETWORKS
text: To learn the unknown reward function without any prior knowledge about its parametric form, we approximate it by a neural network. In this section, we define the class of overparameterized neural networks that will be used throughout this paper. We consider fully connected neural networks with depth L ≥ 2 defined on Rd as
fW (u) = √ mWLσ (WL−1σ (. . . σ(W1u) . . .)) ,∀u ∈ Rd, (1)
where σ(·) = max{·, 0} is the rectified linear unit (ReLU) activation function, W1 ∈ Rm×d,Wi ∈ Rm×m,∀i ∈ [2, L − 1],WL ∈ Rm×1, and W := (W1, . . . ,WL) with vec(W ) ∈ Rp where p = md+m+m2(L−2). We assume that the neural network is overparameterized in the sense that the width m is sufficiently larger than the number of samples n. Under such an overparameterization regime, the dynamics of the training of the neural network can be captured in the framework of socalled neural tangent kernel (NTK) (Jacot et al., 2018). Overparameterization has been shown to be effective to study the interpolation phenomenon and neural training for deep neural networks (Arora et al., 2019; Allen-Zhu et al., 2019; Hanin & Nica, 2019; Cao & Gu, 2019; Belkin, 2021).
Algorithm 1 NeuraLCB Input: Offline data Dn = {(xt, at, rt)}nt=1, step sizes {ηt}nt=1 , regularization parameter λ > 0,
confidence parameters {βt}nt=1. 1: Initialize W (0) as follows: set W (0)l = [W̄l, 0;0, W̄l],∀l ∈ [L− 1] where each entry of W̄l
is generated independently from N (0, 4/m), and set W (0)L = [wT ,−wT ] where each entry of w is generated independently from N (0, 2/m). 2: Λ0 ← λI . 3: for t = 1, . . . , n do 4: Retrieve (xt, at, rt) from Dn. 5: π̂t(x) ← argmaxa∈[K] Lt(xa), for all x = {xa ∈ Rd : a ∈ [K]} where Lt(u) =
fW (t−1)(u)− βt−1∥∇fW (t−1)(u) ·m−1/2∥Λ−1t−1 ,∀u ∈ R d
6: Λt ← Λt−1 + vec(∇fW (t−1)(xt,at)) · vec(∇fW (t−1)(xt,at))T /m. 7: W (t) ← W (t−1) − ηt∇Lt(W (t−1)) where Lt(W ) = 12 (fW (xt,at) − rt)
2 + mλ2 ∥W − W (0)∥2F .
8: end for Output: Randomly sample π̂ uniformly from {π̂1, . . . , π̂n}.

heading: 3 ALGORITHM
text: In this section, we present our algorithm, namely NeuraLCB (which stands for Neural Lower Confidence Bound). A key idea of NeuraLCB is to use a neural network fW (xa) to learn the reward function h(xa) and use a pessimism principle based on a lower confidence bound (LCB) of the reward function (Buckman et al., 2020; Jin et al., 2020) to guide decision-making. The details of NeuraLCB are presented in Algorithm 1. Notably, unlike any other OPL methods, NeuraLCB learns in an online-like manner. Specifically, at step t, Algorithm 1 retrieves (xt, at, rt) from the offline dataDn, computes a lower confidence bound Lt for each context and action based on the current network parameter W (t−1), extracts a greedy policy π̂t with respect to Lt, and updates W (t) by minimizing a regularized squared loss function Lt(W ) using stochastic gradient descent. Note that Algorithm 1 updates the network using one data point at time t, does not use the last sample (xn, an, rn) for decision-making and takes the average of an ensemble of policies {π̂t}nt=1 as its returned policy. These are merely for the convenience of theoretical analysis. In practice, we can either use the ensemble average, the best policy among the ensemble or simply the latest policy π̂n as the returned policy. At step t, we can also train the network on a random batch of data from Dt (the “B-mode” variant as discussed in Section 6).

heading: 4 GENERALIZATION ANALYSIS
text: In this section, we analyze the generalization ability of NeuraLCB. Our analysis is built upon the neural tangent kernel (NTK) (Jacot et al., 2018). We first define the NTK matrix for the neural network function in Eq. (1).
Definition 4.1 (Jacot et al. (2018); Cao & Gu (2019); Zhou et al. (2019)). Denote {x(i)}nKi=1 = {xt,a ∈ Rd : t ∈ [n], a ∈ [K]}, H̃(1)i,j = Σ (1) i,j = ⟨x(i),x(j)⟩, and
A (l) i,j =
[ Σ
(l) i,i Σ (l) i,j
Σ (l) i,j Σ (l) j,j
] , Σ
(l+1) i,j = 2E(u,v)∼N (0,A(l)i,j) [σ(u)σ(v)] ,
H̃ (l+1) i,j = 2H̃ (l) i,jE(u,v)∼N (0,A(l)i,j) [σ ′(u)σ′(v)] +Σ (l+1) i,j .
The neural tangent kernel (NTK) matrix is then defined as H = (H̃(L) +Σ(L))/2.
Here, the Gram matrix H is defined recursively from the first to the last layer of the neural network using Gaussian distributions for the observed contexts {x(i)}nKi=1. Next, we introduce the assumptions for our analysis. First, we make an assumption about the NTK matrix H and the input data.
Assumption 4.1. ∃λ0 > 0,H ⪰ λ0I , and ∀i ∈ [nK], ∥x(i)∥2 = 1. Moreover, [x(i)]j = [x(i)]j+d/2,∀i ∈ [nK], j ∈ [d/2].
The first part of Assumption 4.1 assures that H is non-singular and that the input data lies in the unit sphere Sd−1. Such assumption is commonly made in overparameterized neural network literature (Arora et al., 2019; Du et al., 2019b;a; Cao & Gu, 2019). While the non-singularity is satisfied when e.g. any two contexts in {x(i)} are not parallel, the unit sphere condition is merely for the sake of analysis and can be relaxed to the case that the input data is bounded in 2-norm. As for any input data point x such that ∥x∥2 = 1 we can always construct a new input x′ = 1√2 [x,x]
T , the second part of Assumption 4.1 is mild and used merely for the theoretical analysis (Zhou et al., 2019). In particular, under Assumption 4.1 and the initialization scheme in Algorithm 1, we have fW (0)(x
(i)) = 0,∀i ∈ [nK]. Next, we make an assumption on the data generation.
Assumption 4.2. ∀t,xt is independent of Dt−1, and ∃κ ∈ (0,∞), ∥∥∥ π∗(·|xt)µ(·|Dt−1,xt)∥∥∥∞ ≤ κ,∀t ∈ [n].
The first part of Assumption 4.2 says that the full contexts are generated by a process independent of any policy. This is minimal and standard in stochastic contextual bandits (Lattimore & Szepesvári, 2020; Rashidinejad et al., 2021; Papini et al., 2021), e.g., when {xt}nt=1
i.i.d.∼ ρ. The second part of Assumption 4.2, namely empirical single-policy concentration (eSPC) condition, requires that the behaviour policy µ has sufficient coverage over only the optimal policy π∗ in the observed contexts. Our data coverage condition is significantly milder than the common uniform data coverage assumptions in the OPL literature (Munos & Szepesvári, 2008; Chen & Jiang, 2019; Brandfonbrener et al., 2021; Jin et al., 2020; Nguyen-Tang et al., 2021) that requires the offline data to be sufficiently explorative in all contexts and all actions. Moreover, our data coverage condition can be considered as an extension of the single-policy concentration condition in (Rashidinejad et al., 2021) where both require coverage over the optimal policy. However, the remarkable difference is that, unlike (Rashidinejad et al., 2021), the behaviour policy µ in our condition needs not to be stationary and the concentration is only defined on the observed contexts; that is, at can be dependent on both xt and Dt−1. This is more practical as it is natural that the offline data was collected by an active learner such as a Q-learning agent (Mnih et al., 2015).
Next, we define the effective dimension of the NTK matrix on the observed data as d̃ = log det(I+H/λ) log(1+nK/λ) . This notion of effective dimension was used in (Zhou et al., 2019) for online neural contextual bandits while a similar notion was introduced in (Valko et al., 2013) for online kernelized contextual bandits, and was also used in (Yang & Wang, 2020; Yang et al., 2020) for online kernelized reinforcement learning. Although being in offline policy learning setting, the online-like nature of NeuraLCB allows us to leverage the usefulness of the effective dimension. Intuitively, d̃ measures how quickly the eigenvalues of H decays. For example, d̃ only depends on n logarithmically when the eigenvalues of H have a finite spectrum (in this case d̃ is smaller than the number of spectrum which is the dimension of the feature space) or are exponentially decaying (Yang et al., 2020). We are now ready to present the main result about the sub-optimality bound of NeuraLCB. Theorem 4.1. For any δ ∈ (0, 1), under Assumption 4.1 and 4.2, if the network width m, the regularization parameter λ, the confidence parameters {βt} and the learning rates {ηt} in Algorithm 1 satisfy m ≥ poly(n,L,K, λ−1, λ−10 , log(1/δ)), λ ≥ max{1,Θ(L)},
βt = √ λ+ C23 tL · (t1/2λ−1/2 + (nK)1/2λ −1/2 0 ) ·m−1/2 for some absolute constant C3,
ηt = ι√ t , where ι−1 = Ω(n2/3m5/6λ−1/6L17/6 log1/2 m) ∨ Ω(mλ1/2 log1/2(nKL2(10n+ 4)/δ)),
then with probability at least 1 − δ over the randomness of W (0) and Dn, the sub-optimality of π̂ returned by Algorithm 1 is bounded as
n · E [SubOpt(π̂)] ≤ κ √ n √ d̃ log(1 + nK/λ) + 2 + κ √ n+ 2 + √ 2n log((10n+ 4)/δ),
where d̃ is the effective dimension of the NTK matrix, and κ is the empirical single-policy concentration (eSPC) coefficient in Assumption 4.2.
Table 1: The SOTA generalization theory of OPL with function approximation. Here the distributional shift measure κ can be defined differently in different works.
Work Function Type Optimization Sub-optimality Data Coverage Data Gen. Yin & Wang (2020)a Tabular Greedy Analytical Õ (√ |X | ·K · n−1/2 ) Uniform I
Rashidinejad et al. (2021) Tabular Pessimism Analytical Õ (√ |X | · κ · n−1/2 ) SPC I
Duan & Wang (2020)b Linear Greedy Analytical Õ ( κ · n−1/2 + d · n−1 ) Uniform I
Jin et al. (2020) Linear Pessimism Analytical Õ ( d · n−1/2 ) Uniform I
Nguyen-Tang et al. (2021) Narrow ReLU Greedy Oracle Õ (√ κ · n− α 2(α+d) ) Uniform I
This work Wide ReLU Pessimism SGD Õ(κ · √
d̃ · n−1/2) eSPC I/D a,b The bounds of these works are for off-policy evaluation which is generally easier than OPL problem. Our bound can be further simplified as E[SubOpt(π̂)] = Õ(κ ·max{ √
d̃, 1} · n−1/2). A detailed proof for Theorem 4.1 is omitted to Section A. We make several notable remarks about our result. First, our bound does not scale linearly with p or √ p as it would if the classical analyses (Abbasi-Yadkori et al., 2011; Jin et al., 2020) had been applied. Such a classical bound is vacuous for overparameterized neural networks where p is significantly larger than n. Specifically, the online-like nature of NeuraLCB allows us to leverage a matrix determinant lemma and the notion of effective dimension in online learning (Abbasi-Yadkori et al., 2011; Zhou et al., 2019) which avoids the dependence on the dimension p of the feature space as in the existing OPL methods such as (Jin et al., 2020). Second, as our bound scales linearly with √ d̃ where d̃ scales only logarithmically with n in common cases (Yang et al., 2020), our bound is sublinear in such cases and presents a provably efficient generalization. Third, our bound scales linearly with κ which does not depend on the coverage of the offline data on other actions rather than the optimal ones. This eliminates the need for a strong uniform data coverage assumption that is commonly used in the offline policy learning literature (Munos & Szepesvári, 2008; Chen & Jiang, 2019; Brandfonbrener et al., 2021; Nguyen-Tang et al., 2021). Moreover, the online-like nature of our algorithm does not necessitate the stationarity of the offline policy, allowing an offline policy with correlated structures as in many practical scenarios. Fourth, compared to the regret bound for online learning setting in (Zhou et al., 2019), we achieve an improvement by a factor of √ d̃ while reducing the computational complexity from O(n2) to O(n). On a more technical note, a key idea to achieve such an improvement is to directly regress toward the optimal parameter of the neural network instead of toward the empirical risk minimizer as in (Zhou et al., 2019).
Finally, to further emphasize the significance of our theoretical result, we summarize and compare it with the state-of-the-art (SOTA) sub-optimality bounds for OPL with function approximation in Table 1. From the leftmost to the rightmost column, the table describes: the related works – the function approximation – the types of algorithms where Pessimism means a pessimism principle based on a lower confidence bound of the reward function while Greedy indicates being uncertaintyagnostic (i.e., an algorithm takes an action with the highest predicted score in a given context) – the optimization problems in OPL where Analytical means optimization has an analytical solution, Oracle means the algorithm relies on an oracle to obtain the global minimizer, and SGD means the optimization is solved by stochastic gradient descent – the sub-optimality bounds – the data coverage assumptions where Uniform indicates sufficiently explorative data over the context and action spaces, SPC is the single-policy concentration condition, and eSPC is the empirical SPC – the nature of data generation required for the respective guarantees where I (Independent) means that the offline actions must be sampled independently while D (Dependent) indicates that the offline actions can be dependent on the past data. It can be seen that our result has a stronger generalization under the most practical settings as compared to the existing SOTA generalization theory for OPL. We also remark that the optimization design and guarantee in NeuraLCB (single data point SGD) are of independent interest that do not only apply to the offline setting but also to the original online setting in (Zhou et al., 2019) to improve their regret and optimization complexity.

heading: 5 RELATED WORK
text: OPL with function approximation. Most OPL works, in both bandit and reinforcement learning settings, use tabular representation (Yin & Wang, 2020; Buckman et al., 2020; Yin et al., 2021; Yin
& Wang, 2021; Rashidinejad et al., 2021; Xiao et al., 2021) and linear models (Duan & Wang, 2020; Jin et al., 2020; Tran-The et al., 2021). The most related work on OPL with neural function approximation we are aware of are (Brandfonbrener et al., 2021; Nguyen-Tang et al., 2021). However, Brandfonbrener et al. (2021); Nguyen-Tang et al. (2021) rely on a strong uniform data coverage assumption and an optimization oracle to the empirical risk minimizer. Other OPL analyses with general function approximation (Duan et al., 2021; Hu et al., 2021) also use such optimization oracle, which limit the applicability of their algorithms and analyses in practical settings.
To deal with nonlinear rewards without making strong functional assumptions, other approaches rather than neural networks have been considered, including a family of experts (Auer, 2003), a reduction to supervised learning (Langford & Zhang, 2007; Agarwal et al., 2014), and nonparametric models (Kleinberg et al., 2008; Srinivas et al., 2009; Krause & Ong, 2011; Bubeck et al., 2011; Valko et al., 2013). However, they are all in the online policy learning setting instead of the OPL setting. Moreover, these approaches have time complexity scaled linearly with the number of experts, rely the regret on an oracle, and have cubic computational complexity, respectively, while our method with neural networks are both statically and computationally efficient where it achieves a √ n-type suboptimality bound and only linear computational complexity.
Neural networks. Our work is inspired by the theoretical advances of neural networks and their subsequent application in online policy learning (Yang et al., 2020; Zhou et al., 2019; Xu et al., 2020). For optimization aspect, (stochastic) gradient descents can provably find global minima of training loss of neural networks (Du et al., 2019a;b; Allen-Zhu et al., 2019; Nguyen, 2021). For generalization aspect, (stochastic) gradient descents can train an overparameterized neural network to a regime where the neural network interpolates the training data (i.e., zero training error) and has a good generalization ability (Arora et al., 2019; Cao & Gu, 2019; Belkin, 2021).
Regarding the use of neural networks for policy learning, NeuraLCB is similar to the NeuralUCB algorithm (Zhou et al., 2019), that is proposed for the setting of online contextual bandits with neural networks, in the sense that both algorithms use neural networks, learn with a streaming data and construct a (lower and upper, respectively) confidence bound of the reward function to guide decision-making. Besides the apparent difference of offline and online policy learning problems, the notable difference of NeuraLCB from NeuralUCB is that while NeuralUCB trains a new neural network from scratch at each iteration (for multiple epochs), NeuraLCB trains a single neural network completely online. That is, NeuraLCB updates the neural network in light of the data at a current iteration from the trained network of the previous iteration. Such optimization scheme in NeuraLCB greatly reduces the computational complexity from O(n2) 1 to O(n), while still guaranteeing a provably efficient algorithm. Moreover, NeuraLCB achieves a suboptimality bound with a better dependence on the effective dimension than NeuralUCB.

heading: 6 EXPERIMENTS
text: In this section, we evaluate NeuraLCB and compare it with five representative baselines: (1) LinLCB (?), which also uses LCB but relies on linear models, (2) KernLCB, which approximates the reward using functions in a RKHS and is an offline counterpart of KernelUCB (Valko et al., 2013), (3) NeuralLinLCB, which is the same as LinLCB except that it uses ϕ(xa) = vec(∇fW (0)(xa)) as the feature extractor for the linear model where fW (0) is the same neural network of NeuraLCB at initialization, (4) NeuralLinGreedy, which is the same as NeuralLinLCB except that it relies on the empirical estimate of the reward function for decision-making, and (5) NeuralGreedy, which is the same as NeuraLCB except that NeuralGreedy makes decision based on the empirical estimate of the reward. For more details and completeness, we present the pseudo-code of these baseline methods in Section D. Here, we compare the algorithms by their generalization ability via their expected suboptimality in the context distribution. For each algorithm, we vary the number of (offline) samples n from 1 to T where T will be specified in each dataset, and repeat each experiment for 10 times. We report the mean results and their 95% confidence intervals.
Approximation. To accelerate computation, we follow (Riquelme et al., 2018; Zhou et al., 2019) to approximate large covariance matrices and expensive kernel methods. Specifically, as NeuraLCB
1In practice, at each time step t, NeuralUCB trains a neural network for t epochs using gradient descent in the entire data collected up to time t.
and NeuralLinLCB involve computing a covariance matrix Λt of size p× p where p = md+m+ m2(L − 2) is the number of the neural network parameters which could be large, we approximate Λt by its diagonal. Moreover, as KernLCB scales cubically with the number of samples, we use KernLCB fitted on the first 1, 000 samples if the offline data exceeds 1, 000 samples.
Data generation. We generate offline actions using a fixed ϵ-greedy policy with respect to the true reward function of each considered contextual bandit, where ϵ is set to 0.1 for all experiments in this section. In each run, we randomly sample nte = 10, 000 contexts from ρ and use this same test contexts to approximate the expected sub-optimality of each algorithm.
Hyperparameters. We fix λ = 0.1 for all algorithms. For NeuraLCB, we set βt = β, and for NeuraLCB, LinLCB, KernLCB, and NeuralLinLCB, we do grid search over {0.01, 0.05, 0.1, 1, 5, 10} for the uncertainty parameter β. For KernLCB, we use the radius basis function (RBF) kernel with parameter σ and do grid search over {0.1, 1, 10} for σ. For NeuraLCB and NeuralGreedy, we use Adam optimizer (Kingma & Ba, 2014) with learning rate η grid-searched over {0.0001, 0.001} and set the l2-regularized parameter to 0.0001. For NeuraLCB, for each Dt, we use π̂t as its final returned policy instead of averaging over all policies {π̂τ}tτ=1. Moreover, we grid search NeuraLCB and NeuralGreedy over two training modes, namely {S-mode,B-mode} where at each iteration t, Smode updates the neural network for one step of SGD (one step of Adam update in practice) on one single data point (xt, at, rt) while B-mode updates the network for 100 steps of SGD on a random batch of size 50 of data Dt (details at Algorithm 7). We remark that even in the B-mode, NeuraLCB is still more computationally efficient than its online counterpart NeuralUCB (Zhou et al., 2019) as NeuraLCB reuses the neural network parameters from the previous iteration instead of training it from scratch for each new iteration. For NeuralLinLCB, NeuralLinGreedy, NeuraLCB, and NeuralGreedy, we use the same network architecture with L = 2 and add layer normalization (Ba et al., 2016) in the hidden layers. The network width m will be specified later based on datasets.

heading: 6.1 SYNTHETIC DATASETS
text: For synthetic experiments, we evaluate the algorithms on contextual bandits with the synthetic nonlinear reward functions h used in (Zhou et al., 2019):
h1(u) = 10(u Ta)2, h2(u) = u TATAu, h3(u) = cos(3u Ta),
where a ∈ Rd is randomly generated from uniform distribution over the unit sphere, and each entry of A ∈ Rd×d is independently and randomly generated from N (0, 1). For each reward function hi, rt = hi(xt,at) + ξt where ξt ∼ N (0, 0.1). The context distribution ρ for three cases is the uniform distribution over the unit sphere. All contextual bandit instances have context dimension d = 20 and K = 30 actions. Moreover, we choose the network width m = 20 and the maximum number of samples T = 10, 000 for the synthetic datasets.

heading: 6.2 REAL-WORLD DATASETS
text: We evaluate the algorithms on real-world datasets from UCI Machine Learning Repository (Dua & Graff, 2017): Mushroom, Statlog, and Adult, and MNIST (LeCun et al., 1998). They represent a good range of properties: small versus large sizes, dominating actions, and stochastic versus
deterministic rewards (see Section E in the appendix for details on each dataset). Besides the Mushroom bandit, Statlog, Adult, and MNIST are K-class classification datasets, which we convert into K-armed contextual bandit problems, following (Riquelme et al., 2018; Zhou et al., 2019). Specifically, for each input x ∈ Rd in a K-class classification problem, we create K contextual vectors x1 = (x,0, . . . ,0), . . . ,xK = (0, . . . ,0,x) ∈ RdK . The learner receives reward 1 if it selects context xy where y is the label of x, and receives reward 0 otherwise. Moreover, we choose the network width m = 100 and the maximum sample number T = 15, 000 for these datasets.

heading: 6.3 RESULTS
text: Figure 1 and 2 show the expected sub-optimality of all algorithms on synthetic datasets and realworld datasets, respectively. First, due to the non-linearity of the reward functions, methods with linear models (LinLCB, NeuralLinLCB, NeuralLinGreedy, and KernLCB) fail in almost all tasks (except that LinLCB and KernLCB have competitive performance in Mushroom and Adult, respectively). In particular, linear models using neural network features without training (NeuralLinLCB and NeuralLinGreedy) barely work in any datasets considered here. In contrast, our method NeuraLCB outperforms all the baseline methods in all tasks. We remark that NeuralGreedy has a substantially lower sub-optimality in synthetic datasets (and even a comparable performance with NeuraLCB in h1) than linear models, suggesting the importance of using trainable neural representation in highly non-linear rewards instead of using linear models with fixed feature extractors. On the other hand, our method NeuraLCB outperforms NeuralGreedy in real-world datasets by a large margin (even though two methods are trained exactly the same but different only in decision-making), confirming the effectiveness of pessimism principle in these tasks. Second, KernLCB performs reasonably in certain OPL tasks (Adult and slightly well in Statlog and MNIST), but the cubic computational complexity of kernel methods make it less appealing in OPL with offline data at more than moderate sizes. Note that due to such cubic computational complexity, we follow (Riquelme et al., 2018; Zhou et al., 2019) to learn the kernel in KernLCB for only the first 1, 000 samples and keep the fitted kernel for the rest of the data (which explains the straight line of KernLCB after n = 1, 000 in our experiments). Our method NeuraLCB, on the other hand, is highly computationally efficient as the computation scales only linearly with n (even in the B-mode – a slight modification of the original algorithm to include batch training). In fact, in the real-world datasets above, the S-mode (which trains in a single data point for one SGD step at each iteration) outperforms the B-mode, further confirming the effectiveness of the online-like nature in NeuraLCB. In Section F, we reported the performance of S-mode and B-mode together and evaluated the compared methods on dependent offline data.

heading: 7 CONCLUSION
text: In this paper, we proposed NeuraLCB, a new algorithm for offline contextual bandits with neural network function approximation and pessimism principle. We proved that our algorithm achieves a sub-optimality bound of Õ(κ · d̃ · n−1/2) under our new data coverage condition that is milder than the existing ones. This is also the first provably efficient result of OPL with neural network function approximation that considers practical optimization. The promising empirical results in both synthetic and real-world datasets suggested the effectiveness of our algorithm in practice.

heading: A PROOF OF THEOREM 4.1
text: In this section, we provide the proof of Theorem 4.1.
Let Dt = {(xτ , aτ , rτ )}1≤τ≤t. Note that π̂t returned by Algorithm 1 is Dt−1-measurable. Denote Et[·] = E[·|Dt−1,xt]. Let the step sizes {ηt} defined as in Theorem 4.1 and the confidence trade-off parameters {βt} defined as in Algorithm 1, we present main lemmas below which will culminate into the proof of the main theorem. Lemma A.1. There exists absolute constants C1, C2 > 0 such that for any δ ∈ (0, 1), if m satisfies
m ≥ max { Θ(nλ−1L11 log6 m),Θ(L6n4K4λ−40 log(KL(5n+ 1)/δ))
Θ(L−1λ1/2(log3/2(nKL2(5n+ 1)/δ) ∨ log−3/2 m)) } ,
then with probability at least 1− δ, it holds uniformly over all t ∈ [n] that SubOpt(π̂t;xt) ≤ 2βt−1Ea∗t∼π∗(·|xt) [ ∥∇fW (t−1)(xt,a∗t ) ·m −1/2∥Λ−1t−1 |Dt−1,xt ]
+ 2C1t 2/3m−1/6 log1/2 mL7/3λ−1/2 + 2 √ 2C2 √ nKλ −1/2 0 m −11/6 log1/2 mt1/6L10/3λ−1/6.
Lemma A.1 gives an upper bound on the sub-optimality of the returned step-dependent policy π̂t on the observed context xt for each t ∈ [n]. We remark that the upper bound depends on the rate at which the confidence width of the NTK feature vectors shrink along the direction of only the optimal actions, rather than any other actions. This is an advantage of pessimism where it does not require the offline data to be informative about any sub-optimal actions. However, the upper bound depends on the unknown optimal policy π∗ while the offline data has been generated a priori by a different unknown behaviour policy. This distribution mismatch is handled in the next lemma. Lemma A.2. There exists an absolute constant C3 > 0 such that for any δ ∈ (0, 1), if m and λ satisfy
λ ≥ max{1,Θ(L)}, m ≥ max { Θ(nλ−1L11 log6 m),Θ(L6n4K4λ−40 log(nKL(5n+ 2)/δ))
Θ(L−1λ1/2(log3/2(nKL2(5n+ 2)/δ) ∨ log−3/2 m)) } ,
then with probability at least 1− δ, we have
1
n n∑ t=1 βt−1Ea∗t∼π∗(·|xt) [ ∥∇fW (t−1)(xt,a∗t ) ·m −1/2∥Λ−1t−1 |Dt−1,xt ] ≤ √ 2βnκ√ n √ d̃ log(1 + nK/λ) + 1 + 2C2C23n 3/2m−1/6(logm)1/2L23/6λ−1/6 + βnκ(C3/ √ 2)L1/2λ −1/2 0 log 1/2((5n+ 2)/δ),
where C2 is from Lemma A.1. We also remark that the upper bound in Lemma A.2 scales linearly with √ d̃ instead of with √ p if a standard analysis were applied. This avoids a vacuous bound as p is large with respect to n.
The upper bounds in Lemma A.1 and Lemma A.2 are established for the observed contexts only. The next lemma generalizes these bounds to the entire context distribution, thanks to the onlinelike nature of Algorithm 1 and an online-to-batch argument. In particular, a key technical property of Algorithm 1 that makes this generalization possible without a uniform convergence is that π̂t is Dt−1-measurable and independent of (xt, at, rt). Lemma A.3. For any δ ∈ (0, 1), with probability at least 1−δ over the randomness ofDn, we have E [SubOpt(π̂)] ≤ 1n ∑n t=1 SubOpt(π̂t;xt) + √ 2 n log(1/δ).
We are now ready to prove the main theorem.
Proof of Theorem 4.1. Combining Lemma A.1, Lemma A.2, and Lemma A.3 via the union bound, we have
n · E[SubOpt(π̂)] ≤ κ √ nΓ1 √ d̃ log(1 + nK/λ) + Γ2 + κ √ nΓ3 + Γ4 + Γ5 + √ 2n log((10n+ 4)/δ),
≤ κ √ n √ d̃ log(1 + nK/λ) + 2 + κ √ n+ 2 + √ 2n log(10n+ 4)/δ)
where m is chosen to be sufficiently large as a polynomial of (n,L,K, λ−1, λ−10 , log(1/δ)) such that
Γ1 := 2 √ 2 √ λ+ C23nL(n 1/2λ1/2 + (nK)1/2λ −1/2 0 ) ·m−1/2 ≤ 1
Γ2 := 1 + 2C2C 2 3n 3/2m−1/6(logm)1/2L23/6λ−1/6 ≤ 2 Γ3 := Γ1 √ n(C3/ √ 2)L1/2λ −1/2 0 log
1/2((10n+ 4)/δ) ≤ 1 Γ4 := 2C1n 5/3m−1/6(logm)1/2L7/3λ−1/2 ≤ 1 Γ5 := 2 √ 2C2(nK) 1/2λ −1/2 0 m −11/6(logm)1/2n7/6L10/3λ−1/6 ≤ 1.

heading: B PROOF OF LEMMAS IN SECTION A
text: B.1 PROOF OF LEMMA A.1
We start with the following lemmas whose proofs are deferred to Appendix B.
Lemma B.1. Let h = [h(x(1)), . . . , h(x(nK))]T ∈ RnK . There exists W ∗ ∈ W such that for any δ ∈ (0, 1), if m ≥ Θ(L6n4K4λ−40 log(nKL/δ)), with probability at least 1 − δ over the randomness of W (0), it holds uniformly for all i ∈ [nK] that
∥W ∗ −W (0)∥F ≤ √ 2m−1/2∥h∥H−1 ,
⟨∇fW (0)(x(i)),W ∗ −W (0)⟩ = h(x(i)).
Remark B.1. Lemma B.1 shows that for a sufficiently wide network, there is a linear model that uses the gradient of the neural network at initialization as a feature vector and interpolates the reward function in the training inputs. Moreover, the weights W ∗ of the linear model is in a neighborhood of the initialization W (0). Note that we also have
S := ∥h∥H−1 ≤ ∥h∥2 √ ∥H−1∥2 ≤ √ nKλ −1/2 0 ,
where the second inequality is by Assumption 4.1 and Cauchy-Schwartz inequality with h(x) ∈ [0, 1],∀x. Lemma B.2. For any δ ∈ (0, 1), if m satisfies
m ≥ Θ(nλ−1L11 log6 m) ∨Θ(L−1λ1/2 log3/2(3n2KL2/δ)),
and the step sizes satisfy
ηt = ι√ t where ι−1 = Ω(n2/3m5/6λ−1/6L17/6 log1/2 m) ∨ Ω(Rmλ1/2 log1/2(n/δ))
then with probability at least 1 − δ over the randomness of W (0) and D, it holds uniformly for all t ∈ [n], l ∈ [L] that
∥W (t)l −W (0) l ∥F ≤
√ t
mλL , and ∥Λt∥2 ≤ λ+ C23 tL,
where C3 > 0 is an absolute constant from Lemma C.2.
Remark B.2. Lemma B.2 controls the growth dynamics of the learned weights Wt around its initialization and bounds the spectral norm of the empirical covariance matrix Λt when the model is trained by SGD. Lemma B.3 (Allen-Zhu et al. (2019, Theorem 5), Cao & Gu (2019, Lemma B.5)). There exist an absolute constant C2 > 0 such that for any δ ∈ (0, 1), if ω satisfies
Θ(m−3/2L−3/2(log3/2(nK/δ)) ∨ log−3/2 m) ≤ ω ≤ Θ(L−9/2 log−3 m),
with probability at least 1 − δ over the randomness of W (0), it holds uniformly for all W ∈ B(W (0);ω) and i ∈ [nK] that
∥∇fW (x(i))−∇fW (0)(x(i))∥F ≤ C2 √ logmω1/3L3∥∇fW (0)(x(i))∥F .
Remark B.3. Lemma B.3 shows that the gradient in a neighborhood of the initialization differs from the gradient at the initialization by an amount that can be explicitly controlled by the radius of the neighborhood and the norm of the gradient at initialization. Lemma B.4 (Cao & Gu (2019, Lemma 4.1)). There exist an absolute constant C1 > 0 such that for any δ ∈ (0, 1) over the randomness of W (0), if ω satisfies
Θ(m−3/2L−3/2 log3/2(nKL2/δ)) ≤ ω ≤ Θ(L−6 log−3/2 m),
with probability at least 1− δ, it holds uniformly for all W ,W ′ ∈ B(W (0);ω) and i ∈ [nK] that |fW ′(x(i))− fW (x(i))− ⟨∇fW (x(i)),W ′ −W ⟩| ≤ C1 · ω4/3L3 √ m logm.
Remark B.4. Lemma B.4 shows that near initialization the neural network function is almost linear in terms of its weights in the training inputs.
Proof of Lemma A.1. For all t ∈ [n],u ∈ Rd, we define
Ut(u) = fW (t−1)(u) + βt−1∥∇fW (t−1)(u) ·m−1/2∥Λ−1t−1 Lt(u) = fW (t−1)(u)− βt−1∥∇fW (t−1)(u) ·m−1/2∥Λ−1t−1 Ūt(u) = ⟨∇fW (t−1)(u),W (t−1) −W (0)⟩+ βt−1∥∇fW (t−1)(u) ·m−1/2∥Λ−1t−1 L̄t(u) = ⟨∇fW (t−1)(u),W (t−1) −W (0)⟩ − βt−1∥∇fW (t−1)(u) ·m−1/2∥Λ−1t−1 Ct = {W ∈ W : ∥W −W (t−1)∥Λt−1 ≤ βt−1}.
Let E be the event in which Lemma B.1, Lemma B.3, Lemma B.3 for all ω ∈{√ i mλL : 1 ≤ i ≤ n } , and Lemma B.4 for all ω ∈ {√ i mλL : 1 ≤ i ≤ n } hold simultaneously.
Under event E , for all t ∈ [n], we have ∥W ∗ −W (t)∥Λt ≤ ∥W ∗ −W (t)∥F √ ∥Λt∥2
≤ (∥W ∗ −W (0)∥F + ∥W (t) −W (0)∥F ) √ ∥Λt∥2 ≤ ( √ 2m−1/2S + t1/2λ−1/2m−1/2) √ λ+ C23 tL = βt,
where the second inequality is by the triangle inequality, and the third inequality is by Lemma B.1 and Lemma B.2. Thus, W ∗ ∈ Ct,∀t ∈ [n]. Denoting a∗t ∼ π∗(·|xt) and ât ∼ π̂t(·|xt) , under event E , we have
SubOpt(π̂t;xt) = Et[h(xt,a∗t )]− Et[h(xt,ât)] (a) = Et [ ⟨∇fW (0)(xt,a∗t ),W ∗ −W (0)⟩ ] − Et [ ⟨∇fW (0)(xt,ât),W ∗ −W (0)⟩ ] (b)
≤ Et [ ⟨∇fW (t−1)(xt,a∗t ),W ∗ −W (0)⟩ ] − Et [ ⟨∇fW (t−1)(xt,ât),W ∗ −W (0)⟩ ]
+ ∥W ∗ −W (0)∥F · Et [ ∥∇fW (t−1)(xt,a∗t )−∇fW (0)(xt,a∗t )∥F
+ ∥∇fW (t−1)(xt,ât)−∇fW (0)(xt,ât)∥F ]
(c) ≤ Et [ ⟨∇fW (t−1)(xt,a∗t ),W ∗ −W (0)⟩ ] − Et [ ⟨∇fW (t−1)(xt,ât),W ∗ −W (0)⟩ ] + 2 √ 2C2Sm −11/6 log1/2 mt1/6L10/3λ−1/6
(d) ≤ Et [ Ūt(xt,a∗t ) ] − Et [ L̄t(xt,ât) ] + 2 √ 2C2Sm −11/6 log1/2 mt1/6L10/3λ−1/6
= Et [ Ut(xt,a∗t ) ] − Et [Lt(xt,ât)]
+ Et [ ⟨∇fW (t−1)(xt,a∗t ),W (t−1) −W (0)⟩ − fW (t−1)(xt,a∗t ) + fW (0)(xt,a∗t ) ]
+ Et [ fW (t−1)(xt,ât)− fW (0)(xt,ât)− ⟨∇fW (t−1)(xt,ât),W (t−1) −W (0)⟩ ] −Et [ fW (0)(xt,a∗t ) ] + Et [fW (0)(xt,ât)]︸ ︷︷ ︸
=0 by symmetry at initialization
+2 √ 2C2Sm −11/6 log1/2 mt1/6L10/3λ−1/6
(e) ≤ Et [ Ut(xt,a∗t ) ] − Et [ Lt(xt,a∗t ) ] + ( Et [ Lt(xt,a∗t ) ] − Et [Lt(xt,ât)] )︸ ︷︷ ︸ ≤0 by pessimism
+ 2C1t 2/3m−1/6 log1/2 mL7/3λ−1/2 + 2 √ 2C2Sm −11/6 log1/2 mt1/6L10/3λ−1/6
(f) ≤ Et [ Ut(xt,a∗t ) ] − Et [ Lt(xt,a∗t ) ] + 2C1t 2/3m−1/6 log1/2 mL7/3λ−1/2 + 2 √ 2C2Sm −11/6 log1/2 mt1/6L10/3λ−1/6
= 2βt−1Et [ ∥∇fW (t−1)(xt,a∗t ) ·m −1/2∥Λ−1t−1 ]
+ 2C1t 2/3m−1/6 log1/2 mL7/3λ−1/2 + 2 √ 2C2Sm −11/6 log1/2 mt1/6L10/3λ−1/6
where (a) is by Lemma B.1, (b) is by the triangle inequality, (c) is by Lemma B.1, Lemma B.2, and Lemma B.3, (d) is by W ∗ ∈ Ct, and by that maxu:∥u−b∥A≤γ⟨a,u−b0⟩ = ⟨a, b−b0⟩+γ∥a∥A−1 , and minu:∥u−b∥A≤γ⟨a,u − b0⟩ = ⟨a, b − b0⟩ − γ∥a∥A−1 , (e) is by Lemma B.4 and by that fW (0)(x
(i)) = 0,∀i ∈ [nK], and (f) is by that ât is sampled from the policy π̂t which is greedy with respect to Lt.
By the union bound and the choice of m, we conclude our proof.
B.2 PROOF OF LEMMA A.2
We first present the following lemma. Lemma B.5. For any δ ∈ (0, 1), if m satisfies
m ≥ max { Θ(nλ−1L11 log6 m),Θ(L−1λ1/2(log3/2(nKL2(n+ 2)/δ) ∨ log−3/2 m)),
Θ(L6(nK)4 log(L(n+ 2)/δ)) } ,
and λ ≥ max{C23L, 1}, then with probability at least 1− δ, it holds simultaneously that t∑
i=1
∥∇fW (i−1)(xi,ai) ·m−1/2∥2Λ−1i−1 ≤ 2 log det(Λt)
det(λI) ,∀t ∈ [n],∣∣∣∣ log det(Λt)det(λI) − log det(Λ̄t)det(λI) ∣∣∣∣ ≤ 2C2C23 t3/2m−1/6(logm)1/2L23/6λ−1/6,∀t ∈ [n], log det(Λ̄n)
det(λI) ≤ d̃ log(1 + nK/λ) + 1,
where Λ̄t := λI + ∑t
i=1 vec(∇fW (0)(xi,ai)) · vec(∇fW (0)(xi,ai))T /m, and C2, C3 > 0 are absolute constants from Lemma B.3 and Lemma B.2, respectively.
We are now ready to prove Lemma A.2.
Proof of Lemma A.2. First note that ∥Λt−1∥2 ≥ λ, ∀t. Let E be the event in which Lemma B.2, Lemma C.2 for all ω ∈ {√ i mλL : 1 ≤ i ≤ n }
, and Lemma B.5 simultaneously hold. Thus, under event E , we have
∥∇fW (t−1)(xt,at) ·m−1/2∥Λ−1t−1 ≤ ∥∇fW (t−1)(xt,at) ·m −1/2∥F √ ∥Λ−1t−1∥2 ≤ C3L1/2λ−1/2,
where the second inequality is by Lemma B.2 and Lemma C.2.
Thus, by Assumption 4.2, Hoeffding’s inequality, and the union bound, with probability at least 1− δ, it holds simultaneously for all t ∈ [n] that
2βt−1Ea∗t∼π∗(·|xt) [ ∥∇fW (t−1)(xt,a∗t ) ·m −1/2∥Λ−1t−1 |Dt−1,xt ]
≤ 2βt−1κEa∼µ(·|Dt−1,xt) [ ∥∇fW (t−1)(xt,a) ·m−1/2∥Λ−1t−1 |Dt−1,xt ] ≤ 2βt−1κ∥∇fW (t−1)(xt,at) ·m−1/2∥Λ−1t−1 + βt−1κ √ 2C3L 1/2λ−1/2 log1/2((5n+ 2)/δ).
Hence, for the choice of m in Lemma A.2, with probability at least 1− δ, we have 1
n n∑ t=1 βt−1Ea∗t∼π∗(·|xt) [ ∥∇fW (t−1)(xt,a∗t ) ·m −1/2∥Λ−1t−1 |Dt−1,xt ]
≤ βnκ n n∑ t=1 ∥∇fW (t−1)(xt,at) ·m−1/2∥Λ−1t−1 + C3√ 2 βnκL 1/2λ −1/2 0 log 1/2((5n+ 2)/δ)
≤ βnκ n √ n √√√√ n∑ t=1 ∥∇fW (t−1)(xt,at) ·m−1/2∥2Λ−1t−1 + C3√ 2 βnκL 1/2λ −1/2 0 log 1/2((5n+ 2)/δ) ≤ √ 2βnκ√ n √ log det(Λn) det(λI) + C3√ 2 βnκL 1/2λ −1/2 0 log 1/2((5n+ 2)/δ) ≤ √ 2βnκ√ n √ log det(Λ̄n) det(λI) + 2C2C23n 3/2m−1/6(logm)1/2L23/6λ−1/6 + C3√ 2 βnκL 1/2λ −1/2 0 log 1/2((5n+ 2)/δ) ≤ √ 2βnκ√ n √ d̃ log(1 + nK/λ) + 1 + 2C2C23n 3/2m−1/6(logm)1/2L23/6λ−1/6
+ C3√ 2 βnκL 1/2λ −1/2 0 log 1/2((5n+ 2)/δ),
where the first inequality is by βt ≤ βn,∀t ∈ [n], the second inequality is by Cauchy-Schwartz inequality, the second inequality and the third inequality are by Lemma B.5.
B.3 PROOF OF LEMMA A.3
Proof of Lemma A.3. We follow the same online-to-batch conversion argument in (Cesa-Bianchi et al., 2004). For each t ∈ [n], define
Zt = SubOpt(π̂t)− SubOpt(π̂t;xt). Since π̂t is Dt−1-measurable and is independent of xt, and xt are independent of Dt−1 (by Assumption 4.2), we have E [Zt|Dt−1] = 0,∀t ∈ [n]. Note that −1 ≤ Zt ≤ 1. Thus, by the Hoeffding-Azuma inequality, with probability at least 1− δ, we have
E[SubOpt(π̂)] = 1
n n∑ t=1 SubOpt(π̂t) = 1 n n∑ t=1 SubOpt(π̂t;xt) + 1 n n∑ t=1 Zt
≤ 1 n n∑ t=1 SubOpt(π̂t;xt) +
√ 2
n log(1/δ).

heading: C PROOF OF LEMMAS IN SECTION B
text: C.1 PROOF OF LEMMA B.1
We first restate the following lemma. Lemma C.1 (Arora et al. (2019)). There exists an absolute constant c1 > 0 such that for any ϵ > 0, δ ∈ (0, 1), if m ≥ c1L6ϵ−4 log(L/δ), for any i, j ∈ [nK], with probability at least 1 − δ over the randomness of W (0), we have
|⟨∇fW (0)(x(i)),∇fW (0)(x(j))⟩/m−Hi,j | ≤ ϵ.
Lemma C.1 gives an estimation error between the kernel constructed by the gradient at initialization as a feature map and the NTK kernel. Unlike Jacot et al. (2018), Lemma C.1 quantifies an exact non-asymptotic bound for m.
Proof of Lemma B.1. Let G = m−1/2 ·[vec(∇fW (0)(x(1))), . . . , vec(∇fW (0)(x(nK)))] ∈ Rp×nK . For any ϵ > 0, δ ∈ (0, 1), it follows from Lemma C.1 and union bound, if m ≥ Θ(L6ϵ−4 log(nKL/δ)), with probability at least 1− δ, we have
∥GTG−H∥F ≤ nK∥GTG−H∥∞ = nKmax i,j |m−1⟨∇fW (0)(x(i)),∇fW (0)(x(j))⟩ −Hi,j |
≤ nKϵ.
Under the event that the inequality above holds, by setting ϵ = λ02nK , we have
H −GTG ⪯ ∥H −GTG∥2I ⪯ ∥H −GTG∥F I ⪯ λ0 2 I ⪯ 1 2 H. (2)
Let G = PΛQT be the singular value decomposition of G where P ∈ Rp×nK ,Q ∈ RnK×nK have orthogonal columns, and Λ ∈ RnK×nK is a diagonal matrix. Since GTG ⪰ 12H ⪰ λ0 2 I is positive definite, Λ is invertible. Let W ∗ ∈ W such that vec(W ∗) = vec(W (0)) + m−1/2 · PΛ−1QTh, we have
m1/2 ·GT (vec(W ∗)− vec(W (0))) = QΛP TPΛ−1QTh = h. Moreover, we have
m∥W ∗ −W (0)∥2F = m∥ vec(W ∗)− vec(W (0))∥22 = hTQΛ−1P TPΛ−1QTh = hTQΛ−2QTh = hT (GTG)−1h ≤ 2hTH−1h,
where the inequality is by Equation (2).
C.2 PROOF OF LEMMA B.2
We present the following lemma that will be used in this proof. Lemma C.2 (Cao & Gu (2019, Lemma B.3)). There exist an absolute constant C3 > 0 such that for any δ ∈ (0, 1) over the randomness of W (0), if ω satisfies
Θ(m−3/2L−3/2 log3/2(nKL2/δ)) ≤ ω ≤ Θ(L−6 log−3 m),
with probability at least 1− δ, it holds uniformly for all W ∈ B(W (0);ω), i ∈ [nK], l ∈ [L] that
∥∇lfW (x(i))∥F ≤ C3 · √ m.
Proof of Lemma B.2. Let δ ∈ (0, 1). Let Lt(W ) = 12 (fW (xt,at) − rt) 2 + mλ2 ∥W −W (0)∥2F be the regularized squared loss function on the data point (xt,at , rt). Recall that W
(t) = W (t−1) − ηt∇Lt(W (t−1)). By Hoelfding’s inequality and that rt is R-subgaussian, for any t ∈ [n], with probability at least 1− δ, we have
|rt| ≤ |Et[rt]|+R √ 2 log(2/δ) = |E [E[rt|Dt−1,xt, at]] |+R √ 2 log(2/δ)
= E [h(xt,at)|Dt−1,xt, at] +R √ 2 log(2/δ) ≤ 1 +R √ 2 log(2/δ). (3)
By union bound and (3), for any sequence {ωt}t∈[n] such that Θ(m−3/2L−3/2 log3/2(3n2KL2/δ)) ≤ ωt ≤ Θ(L−6 log−3 m) ∧ Θ(L−6 log−3/2 m),∀t ∈ [n], with probability at least 1− δ, it holds uniformly for all W ∈ B(W (0);ωt), l ∈ [L], t ∈ [n] that
∥∇lLt(W )∥F = ∥∇lfW (xt,at)(fW (xt,at)− rt) +mλ(Wl −W (0) l )∥F
= ∥∇lfW (xt,at)(fW (xt,at)− fW (0)(xt,at)− ⟨∇fW (0)(xt,at),W −W (0)⟩) +∇lfW (xt,at)fW (0)(xt,at) +∇lfW (xt,at)⟨∇fW (0)(xt,at),W −W (0)⟩
− rt∇lfW (xt,at) +mλ(Wl −W (0) l )∥F
≤ ∥∇lfW (xt,at)(fW (xt,at)− fW (0)(xt,at)− ⟨∇fW (0)(xt,at),W −W (0)⟩)∥F + ∥∇lfW (xt,at)fW (0)(xt,at)∥F︸ ︷︷ ︸
=0
+∥∇lfW (xt,at)⟨∇fW (0)(xt,at),W −W (0)⟩∥F
+ |rt|∥∇lfW (xt,at)∥F +mλ∥Wl −W (0) l ∥F
≤ C1C3ω4/3t L3m log 1/2 m+ C3m 1/2(1 +R √ 2 log(6n/δ)) + C23Lmω +mλωt,
(4) where the first inequality is triangle’s inequality, and the second inequality is by Lemma B.4, Lemma C.2 and (3).
We now prove by induction that under the same event that (4) with ωt = √ t mλL holds, W (t) ∈
B(W (0); √
t mλL ),∀t ∈ [n]. It trivially holds for t = 0. Assume W
(i) ∈ B(W (0); √
i mλL ),∀i ∈ [t − 1], we will prove that W (t) ∈ B(W (0); √
t mλL ). Indeed, it is easy to verify that there ex-
ist absolute constants {Ci}2i=1 > 0 such that if m satisfies the inequalities in Lemma B.2, then Θ(m−3/2L−3/2 log3/2(3n2KL2/δ)) ≤ √ i
mλL ≤ Θ(L −6 log−3 m) ∧ Θ(L−6 log−3/2 m),∀i ∈
[n]. Thus, under the same event that (4) holds, we have
∥W (t)l −W (0) l ∥F ≤ t∑ i=1 ∥W (i)l −W (i−1) l ∥F = t∑ i=1 ηi∥∇lLi(W (i−1))∥F
≤ ιtC1C3m1/3λ−2/3L7/3n1/6 log1/2 m+ ιtm−1/2λ−1/2L−1/2(C23L+ λ) + 2C3ι √ tm1/2(1 +R √ 2 log1/2(6n/δ))
≤ 1 2
√ t
mλL +
1
2
√ t
mλL =
√ t
mλL ,
where the first inequality is by triangle’s inequality, the first equation is by the SGD update for each W (i), the second inequality is by (4) and the last inequality is due to ι be chosen asι −1 ≥ 4C3mλ1/2L1/2 ( 1 +R √ 2 log1/2(6n/δ) ) ι−1 ≥ 2n1/2m1/2λ1/2L1/2 ( C1C3m 1/3λ−2/3L7/3n1/6 log1/2 m+m−1/2λ−1/2L−1/2(C23L+ λ) ) ,
which is satisfied for ι−1 = Ω(n2/3m5/6λ−1/6L17/6 log1/2 m) ∨ Ω(Rmλ1/2 log1/2(n/δ)). For the second part of the lemma, we have
∥Λt∥2 = ∥λI + t∑
i=1
vec(∇fW (i−1)(xi,ai)) · vec(∇fW (i−1)(xi,ai))T /m∥2
≤ λ+ t∑
i=1
∥∇fW (i−1)(xi,ai)∥2F /m ≤ λ+ C23 tL,
where the first inequality is by triangle’s inequality and the second inequality is by ∥W (i) − W (0)∥F ≤
√ i
mλ ,∀i ∈ [n] and Lemma C.2.
C.3 PROOF OF LEMMA B.5
Proof of Lemma B.5. Let E(δ) be the event in which the following (n + 2) events hold simultaneously: the events in which Lemma B.3 for each ω ∈ {√ i mλL : 1 ≤ i ≤ n } holds, the event in which Lemma C.1 for ϵ = (nK)−1 holds, and the event in which Lemma C.2 holds.
Under event E(δ), we have
∥∇fW (t−1)(xt,at) ·m−1/2∥F ≤ C3L1/2,∀t ∈ [n].
Thus, by (Abbasi-Yadkori et al., 2011, Lemma 11), if we choose λ ≥ max{1, c26L}, we have t∑
i=1
∥∇fW (i−1)(xi,ai) ·m−1/2∥2Λ−1i−1 ≤ 2 log det(Λt) det(λI) .
For the second part of Lemma B.5, for any t ∈ [n], we define
M̄t = m −1/2 · [vec(∇fW (0)(x1,a1)), . . . , vec(∇fW (0)(xt,at))] ∈ Rp×t, Mt = m −1/2 · [vec(∇fW (t−1)(x1,a1)), . . . , vec(∇fW (t−1)(xt,at))] ∈ Rp×t.
We have Λ̄t = λI + M̄tM̄Tt and Λt = λI +MtM T t , and∣∣∣∣ log det(Λt)det(λI) − log det(Λ̄t)det(λI) ∣∣∣∣ = | log det(I +MtMTt /λ)− log det(I + M̄tM̄Tt /λ)| = | log det(I +MTt Mt/λ)− log det(I + M̄Tt M̄t/λ)| ≤ max{∥⟨(I +MTt Mt/λ)−1,MTt Mt − M̄Tt M̄t⟩∥, ∥⟨(I + M̄Tt M̄t/λ)−1,MTt Mt − M̄Tt M̄t⟩∥} = ∥⟨(I +MTt Mt/λ)−1,MTt Mt − M̄Tt M̄t⟩∥ ≤ ∥(I +MTt Mt/λ)−1∥F · ∥MTt Mt − M̄Tt M̄t∥F ≤ √ t∥(I +MTt Mt/λ)−1∥2 · ∥MTt Mt − M̄Tt M̄t∥F
≤ √ t∥MTt Mt − M̄Tt M̄t∥F ≤ √ tt max
1≤i,j≤t m−1 · ∣∣∣∣⟨∇fW (t−1)(xi,ai),∇fW (t−1)(xj,aj )⟩ − ⟨∇fW (0)(xi,ai),∇fW (0)(xj,aj )⟩∣∣∣∣ ≤ t3/2m−1 max
1≤i,j≤t (∣∣∣∣⟨∇fW (t−1)(xi,ai)−∇fW (0)(xi,ai),∇fW (t−1)(xj,aj )⟩∣∣∣∣ +
∣∣∣∣⟨∇fW (t−1)(xj,aj )−∇fW (0)(xj,aj ),∇fW (t−1)(xi,ai)⟩∣∣∣∣) ≤ 2t3/2m−1 max
i ∥∇fW (t−1)(xi,ai)−∇fW (0)(xi,ai)∥F ·max i ∥∇fW (t−1)(xi,ai)∥F
≤ 2C2C23 t3/2m−1/6(logm)1/2L23/6λ−1/6
where the second equality is by det(I + AAT ) = det(I + ATA), the first inequality is by that log det is convex concave, the third equality is assumed without loss of generality, the second inequality is by that ⟨A,B⟩ ≤ ∥A∥F ∥B∥F , the third inequality is by that ∥A∥F ≤ √ t∥A∥2 for A ∈ Rt×t, the fourth inequality is by that I + MTt Mt/λ ⪰ I , the fifth inequality is by that ∥A∥F ≤ t∥A∥∞ for A ∈ Rt×t, the sixth inequality is by the triangle inequality, and the last inequality is by Lemma B.3, and Lemma C.2.
The third part of Lemma B.5 directly follows the argument in (Zhou et al., 2019, (B.18)) and uses Lemma C.1 for ϵ = (nK)−1.
Finally, it is easy to verify that the condition of m in Lemma B.5 satisfies the condition of m for E(δ/(n+ 2)), and union bound we have P(E(δ/(n+ 2))) ≥ 1− δ.

heading: D DETAILS OF BASELINE ALGORITHMS IN SECTION 6
text: In this section, we present the details of each representative baseline methods and of the B-mode version of NeuraLCB in Section 6. We summarize the baseline methods in Table 2.
Algorithm 2 LinLCB Input: Offline data Dn = {(xt, at, rt)}nt=1, reg. parameter λ > 0, confidence parameters β > 0.
1: Λn ← λI + ∑n t=1 xt,atx T t,at
2: θ̂n ← Λ−1n ∑n
t=1 xt,atrt 3: L(u)← ⟨θ̂n,u⟩ − β∥u∥Λ−1n ,∀u ∈ R d
Output: π̂(x)← argmaxa∈[K] L(xa)
Algorithm 3 KernLCB Input: Offline data Dn = {(xt, at, rt)}nt=1, reg. parameter λ > 0, confidence parameters β > 0,
kernel k : Rd × Rd → R. 1: kn(u)← [k(u,x1,a1), . . . , k(u,xn,an)]T ,∀u ∈ Rd 2: Kn ← [k(xi,ai ,xj,aj )]1≤i,j≤n 3: yn ← [r1, . . . , rn]T 4: L(u)← kn(u)T (Kn + λI)−1yn − β √ k(u,u)− kTn (u)(Kn + λI)−1kn,∀u ∈ Rd
Output: π̂(x)← argmaxa∈[K] L(xa)
Algorithm 4 NeuralLinLCB Input: Offline dataDn = {(xt, at, rt)}nt=1, regularization parameter λ > 0, confidence parameters
β > 0. 1: Initialize the same neural network with the same initialization scheme as in NeuraLCB to obtain
the neural network function fW (0) at initialization 2: ϕ(u)← vec(∇fW (0)(u)) ∈ Rp,∀u ∈ Rd 3: Λn ← λI + ∑n t=1 ϕ(xt,at)ϕ(xt,at) T
4: θ̂n ← Λ−1n ∑n
t=1 ϕ(xt,at)rt 5: L(u)← ⟨θ̂n, ϕ(u)⟩ − β∥ϕ(u)∥Λ−1n ,∀u ∈ R d
Output: π̂(x)← argmaxa∈[K] L(xa)
Algorithm 5 NeuralLinGreedy Input: Offline data Dn = {(xt, at, rt)}nt=1, regularization parameter λ > 0.
1: Initialize the same neural network with the same initialization scheme as in NeuraLCB to obtain the neural network function fW (0) at initialization 2: ϕ(u)← vec(∇fW (0)(u)) ∈ Rp,∀u ∈ Rd 3: θ̂n ← Λ−1n ∑n t=1 ϕ(xt,at)rt
4: L(u)← ⟨θ̂n, ϕ(u)⟩,∀u ∈ Rd Output: π̂(x)← argmaxa∈[K] L(xa)
Algorithm 6 NeuralGreedy Input: Offline data Dn = {(xt, at, rt)}nt=1, step sizes {ηt}nt=1 , regularization parameter λ > 0.
1: Initialize W (0) as follows: set W (0)l = [W̄l, 0;0, W̄l],∀l ∈ [L− 1] where each entry of W̄l is generated independently from N (0, 4/m), and set W (0)L = [wT ,−wT ] where each entry of w is generated independently from N (0, 2/m). 2: for t = 1, . . . , n do 3: Retrieve (xt, at, rt) from Dn. 4: π̂t(x)← argmaxa∈[K] fW (t−1)(xa),∀x. 5: W (t) ← W (t−1) − ηt∇Lt(W (t−1)) where Lt(W ) = 12 (fW (xt,at) − rt)
2 + mλ2 ∥W − W (0)∥2F .
6: end for Output: Randomly sample π̂ uniformly from {π̂1, . . . , π̂n}.
Algorithm 7 NeuraLCB (B-mode) Input: Offline data Dn = {(xt, at, rt)}nt=1, step sizes {ηt}nt=1 , regularization parameter λ > 0,
confidence parameters {βt}nt=1, batch size B > 0, epoch number J > 0. 1: Initialize W (0) as follows: set W (0)l = [W̄l, 0;0, W̄l],∀l ∈ [L− 1] where each entry of W̄l
is generated independently from N (0, 4/m), and set W (0)L = [wT ,−wT ] where each entry of w is generated independently from N (0, 2/m).
2: Λ0 ← λI . 3: for t = 1, . . . , n do 4: Retrieve (xt, at, rt) from Dn. 5: Lt(u)← fW (t−1)(u)− βt−1∥∇fW (t−1)(u) ·m−1/2∥Λ−1t−1 ,∀u ∈ R d 6: π̂t(x)← argmaxa∈[K] Lt(xa), for all x = {xa ∈ Rd : a ∈ [K]}. 7: Λt ← Λt−1 + vec(∇fW (t−1)(xt,at)) · vec(∇fW (t−1)(xt,at))T /m. 8: W̃ (0) ←W (t−1) 9: for j = 1, . . . , J do
10: Sample a batch of data Bt = {xtq,atq , rtq} B q=1 from Dt 11: L(j)t (W )← ∑B q=1 1 2B (fW (xtq,atq )− rtq ) 2 + mλ2 ∥W −W (0)∥2F 12: W̃ (j) ← W̃ (j−1) − ηt∇L(j)t (W̃ (j−1)) 13: end for 14: W (t) ← W̃ (J) 15: end for Output: Randomly sample π̂ uniformly from {π̂1, . . . , π̂n}.

heading: E DATASETS
text: We present a detailed description about the UCI datasets used in our experiment.
• Mushroom data: Each sample represents a set of attributes of a mushroom. There are two actions to take on each mushroom sample: eat or no eat. Eating an editable mushroom
We summarizes the statistics of the above datasets in Table 3.

heading: F ADDITIONAL EXPERIMENTS
text: In this section, we complement the experimental results in the main paper with additional experiments regarding the learning ability of our algorithm on dependent data and the different behaviours of S-mode and B-mode training.
F.1 DEPENDENT DATA
As the sub-optimality guarantee in Theorem 4.1 does not require the offline policy to be stationary, we evaluate the empirical performance of our algorithm and the baselines on a new setup of offline data collection that represents dependent actions. In particular, instead of using a stationary policy to collect offline actions as in Section 6, here we used an adaptive policy µ defined as
µ(a|Dt−1,xt) = (1− ϵ) ∗ π∗(a|xt) + ϵ ∗ πLinUCB(a|Dt−1,xt),
where π∗ is the optimal policy and πLinUCB is the linear UCB learner (Abbasi-Yadkori et al., 2011). This weighted policy makes the collected offline data at dependent on Dt−1 while making sure that the offline data has a sufficient coverage over the data of the optimal policy, as LinUCB does not perform well in several non-linear data. We used ϵ = 0.9 in this experiment.
The results on Statlog and MNIST are shown in Figure 3. We make two important observations. First, on this dependent data, the baseline methods with linear models (LinLCB, NeuralLinLCB and NeuralLinGreedy) 2 perform almost as bad as when they learn on the independent data in Figure 2, suggesting that linear models are highly insufficient to learn complex rewards in real-world data, regardless of how offline data were collected. Secondly, the main competitor of our method, NeuralGreedy suffers an apparent performance degradation (especially in a larger dataset like MNIST) while NeuraLCB maintains a superior performance, suggesting the effectiveness of pessimism in our method on dealing with offline data and the robustness of our method toward dependent data.
2KernLCB also does not change its performance much, but its computational complexity is still an major issue.
F.2 S-MODE VERSUS B-MODE TRAINING
As in Section 6 we implemented two different training modes: S-mode (Algorithm 1) and B-mode (Algorithm 7). We compare the empirical performances of S-mode and B-mode on various datasets. As this variant is only applicable to NeuralGreedy and NeuraLCB, we only depict the performances of these algorithms. The results on Cosine (synthetic dataset), Statlog, Adult and MNIST are shown in Figure 4.
We make the following observations, which are consistent with the conclusion in the main paper while giving more insights. While the B-mode outperforms the S-mode on Cosine, the S-mode significantly outperforms the B-mode in all the tested real-world datasets. Moreover, the B-mode of NeuraLCB outperforms or at least is compatible to the S-mode of NeuralGreedy in the realworld datasets. First, these observations suggest the superiority of our method on the real-world datasets. Second, to explain the performance difference of S-mode and B-mode on synthetic and real-world datasets in our experiment, we hypothesize that the online-like nature of our algorithm tends to reduce the need of B-mode in practical datasets because B-mode in the streaming data might cause over-fitting (as there could be some data points in the past streaming that has been fitted for multiple times). In synthetic and simple data such as Cosine, over-fitting tends to associate with strong prediction of the underlying reward function as the simple synthetic reward function such as Cosine is sufficiently smooth, unlike practical reward functions in the real-world datasets.

Review summaries:
This paper proposes a neural network based contextual bandit algorithm in the offline setting where a dataset of contexts and rewards are given by a logging policy. The goal of the proposed algorithm is to learn an optimal policy from the offline dataset. The proposed algorithm NeuralLCB is similarly structured as the NeuralUCB algorithm (Zhou et a., 2019) in the online setting. The difference is that it uses a lower confidence bound for estimating the reward function instead of an upper confidence bound, and that the optimization procedure for learning the neural network representation is based on the loss on one data point instead of the whole historical data. The authors established an upper bound of the optimal gap of the learned policy and evaluated the algorithm on both simulation and UCI datasets.  

~~~~~~~~~~~~~~ Thank the authors for the clarification. Some of my former comments were nicely addressed and hence I am willing to increase my rating to 6.  ~~~~~~~~~~~~~~ This paper considers the offline setting of the contextual bandit with neural network function approximation. The key idea of the proposed NeuraLCB is to use neural network to learn the reward function and use a pessimism principle via a lower confidence bound (LCB) for decision making. In theory, the proposed approach is shown to learn the optimal policy with an error bound $O(\kappa \tilde{d}^{1/2} n^{-1/2})$ where $\kappa$ measures the distributional shift and $\tilde{d}$ is an effective dimension of the neural network. The empirical effectiveness of the proposed method is shown in a range of synthetic and real-world off-policy learning problems.  

This paper is the first study considers offline policy learning for contextual bandits with neural networks. The authors proposed NeuraLCB algorithm that used neural network to model the rewards and followed pessimism principle with lower confidence bound in policy learning. It is a very intuitive combination. The algorithm works with mild assumptions with theoretical guarantee on its suboptimality. Experiments also showed that NeuraLCB outperforms other baselines.

The paper studies the problem of offline contextual bandits, where policy learning can only leverage a fixed dataset collected a priori by behavior policies. Using a pessimism principle, the authors propose a new algorithm called NeuralLCB with overparameterized neural networks and provide theoretical regret guarantees based on the analysis framework of the neural tangent kernel. Experiments on both synthetic and real-world data are conducted, which confirms the theoretical results.