Offline Neural Contextual Bandits: Pessimism, Optimization and Generalization
Authors: Thanh Nguyen-Tang
Sunil Gupta
A. Tuan Nguyen
Svetha Venkatesh
Venue: ICLR 2022 Poster (2022)
Keywords: offline policy learning
offline contextual bandits
neural network function approximation

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.

Published as a conference paper at ICLR 2022
OFFLINE NEURAL CONTEXTUAL BANDITS: PESSIMISM, OPTIMIZATION AND GENERALIZATION
Thanh Nguyen-Tang
Sunil Gupta
A. Tuan Nguyen Department of Engineering Science University of Oxford
Applied AI Institute Deakin University
Applied AI Institute
Deakin University
Svetha Venkatesh
Applied AI Institute Deakin University
ABSTRACT
Offline policy learning (OPL.) leverages existing data collected 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-devcloped. In this paper, consider this problem on the axes of distributional shift, optimization, and generalization offline contextual bandits with neural networks. In particular, we propose prov- ably efficient offline contextual bandit with neural network function approxima- tion that does require any functional assumption the reward. We show that our method provably generalizes over unseen contexts under 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 to leverage the benefits of online learning into an offline setting. Moreover, we show that our method is more computa- tionally efficient and has better dependence on the effective dimension of the neural network than an online counterpart. Finally, we demonstrate the empirical effectiveness of our method a range of synthetic and real-world OPL problems.
INTRODUCTION
We consider the problem of offline policy learning (OPL) (Lange et al., 2012; Levine et al., 2020) where learner infers optimal policy given only access fixed dataset collected priori by unknown behaviour policies, without any active exploration. There has been growing interest in this problem recently,
reflects 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 al., 2019; Nie et al., 2021), recommendation systems (Strehl al., 2010; Thomas et al., 2017), and econometrics (Kitagawa & Tetenov, 2018; Athey & Wager, 2021).
Despite the importance of OPI, theoretical and algorithmic progress on this problem has been rather limited. Specifically, most existing works are restricted to strong parametric assumption of envi- ronments such as tabular representation (Yin & Wang. 2020; Buckman et al., 2020; Yin et al., 2021; Yin & Wang, 2021; Rashidinejad et al., 2021: Xiao al., 2021) and more generally as linear models (Duan Wang, 2020; Jin al., 2020; Tran-The et al., 2021). However, while the linearity assump- tion does not hold for many problems in practice, work has provided 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 fixed dataset without any active exploration, there is often mismatch between the distribution of the data generated by target policy and that of the offline data. This distributional mismatch can cause erroneous value overestimation and render
EEaill: nguyent com.

---

Published as a conference paper at ICLR 2022
many standard online policy learning methods unsuccessful (Fujimoto al., 2019). To guarantee an efficient learning under distributional shift, common analyses rely on a sort of uniform data cov- erage assumptions (Munos & Szepesvári, 2008; Chen & Jiang, 2019; Brandfonbrener et al., 2021; Nguyen-Tani 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, pessimism principle that constructs lower confidence bound of the reward functions for decision-making (Rashidinejad 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 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 offlin 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 minimal structural assumption on the distributional shift that allows a provably efficient OPL algorithm.
Optimization. Solving OPL often involves in fitting 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 addi- tional 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 ac- cess to an optimization oracle that can return a global minimizer (Brandfonbrener et al., 2021; Duan al., 2021; Nguyen-Tani -ang et al., 2021) or an empirical risk minimizer with pointwise convergence bound at an exponential rate (Hu et al., 2021). This is largely not the case in practice, especially in meth-
OPL with neural network function approximation where model is trained by gradient- ods such as stochastic gradient descents (SGD). Thus, to understand OPL in more practical settings, 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 '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 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 uniform convergence bound vacuous, neither the data splitting technique in (Yin & Wang, 2020) nor the uniform convergence argument in (Yin et al., 2021) 1) yield good generalization. Thus, it is highly non- con-trivial to guarantee 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, make three contribu- tions toward enabling OPL in more practical settings:
First, we propose algorithm that uses 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 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 milder con- dition 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
2

---

Published as a conference paper at ICLR 2022
iteration. Moreover, the distributional shift condition in analysis, unlike in the exist- ing works, does not require the offline policy to be uniformly explorative or stationary. Specifically, prove that, under mild conditions with practical considerations above, algorithm learns the optimal policy with expected error of O(sdd/2n - where is the number of offiine samples, K 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 number of synthetic and real-world OPL benchmark problems, verifying its empirical effectiveness against the representative methods of OPL.
Notation. We lower case, bold lower case, and bold iPper case to represent scalars, vectors and matrices, respectively. For a vector v = [ri...., vaa" E IRd and > 1, denote ||æ||p = d 1/8 and let [uly be the 5th element of For matrix A = (Ai.jmmxs mxn. denote |
V E., AP,y Al,, maxp: [|Au]lp> || max;j |Ais and let vec(A) E R be the vectorized representation of A. For a square matrix A, vector u, and a matrix X, denote || VO Av and X A = |eve X) A- For a collection of matrices W = (W1,-- WL)
and a square matrix A, denote || [ || = v E |Will?. and | = / V W l/. For denote ((W (0) ()) . = ( (WI,... W1): I // ||r S R}. Denote [n] = 21, .... n1, and b maxfa, a, b}. We write Ö(-) to hide logarithmic factors in the standard Big-Oh notation, and write m 2 (() to indicate that there is an absolute constant > 0 that is independent of any problem parameters (-) such that m 2 Cf(())
collection of matrices W (W1 1 ..... W 1. (0)
(0)
BACKGROUND
In this section, we provide essential background on offline stochastic contextual bandits and overpa- rameterized neural networks.
2.1 STOCHASTIC CONTEXTUAL BANDITS
We consider stochastic K-armed contextual bandit where each round t, online learner ob- serves a full context 2; == { E Rdd : a E [K]} sampled from a context distribution p. takes an action ag [K], and receives reward Fr P(- A policy π maps a full context (and possibly other past information) to a distribution over the action space [K]. For each full context == {xxa E Fdd a E [K]} we define vd (x: E Pp.- and e (a) = max, t (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 D, {(2x,, dt, F=) collected priori by a behaviour policy The goodness of a learned policy á measured by the (expected) sub-optimality the policy achieves in the entire (unknown) context distribution p:
SubOpt(ft := EE- (SuOOpttt x)], where SubOpt(f;: == v'()) - v. (x).
In this work, we make the following assumption about reward generation: For each f, Yz h(xt,a,) +&,, where h Rd + [0, 1] is an unknown reward function, and & is R-subgaussian noise conditioned on (D,-1, Lt, ar) where we denote D. {(2r, ar, Tr)) Vt. The R-subgaussian noise assumption standard in stochastic bandit literature (Abbasi- Yadkoii al., 2011; 1; Zhou al., 2020: Xiao et al., 2021) and is satisfied e.g. for any bounded noise.
2.2 OVERPARAMETERIAA NEURAL NETWORKS
To learn the unknown reward function without any prior knowledge about its parametric form, we approximate it by 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 2 defined on Rdd as
fw fw( = VmWra (Wi-1a (...o (Wiu). W..)...)) .)) Vu E Rd.
3

---

Published as a conference paper at ICLR 2022
Algorithm 1 NeuraLCB
Input:
Offline data D, (1) step sizes {ne 1e regularization parameter À 0, a,,
confidence parameters (:
I: Initialize ( as follows: set W (0) [Wi, 0,0, Wil. Vl E [L - 1] where each entry of W
is generated independently from (0, 4/m), and set w [w", -w""] where each entry of
w generated independently from (0, m)).
2: Ao f AI.
3: for 1l.. do
4: Retrieve (xt, at, rt) from Dr.
5:
=x(2)) -- arg [a[K] (x( for all x = fan E Rd : a E [K]] where Le(u) =
Swa-D (u) - 3.-1ll fwit-s) (2)) -m- 1/2 A,2.
1 Vu E Rd
6:
A f A + (V I ( (xt,a))) vec(V (ooo///e-nn /
7:
W W(--1) m VL, where Lu (W) ( r2)2 7 W
m2
1 8: end for Output: Randomly sample म uniformly from { }
1.
where (.) maxx {:, 0} is the rectified linear unit (ReLU) activation function, Wi E Rmmdd W; Rmxm Vi E [2, I 1), Wr. E IR=x1, and W == (W,,... ,,,) with vec( E R2 where p= md++m--- m 1- (T. (T.2).. 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 so- called 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
In this section, we present our algorithm, namely NeuraLCB (which stands for Neural Lower Confidence Bound). A key idea of NeuraL.CB is to use a neural network (xx) to learn the reward function h(xx) 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 6, Algorithm retrieves (æt, at. (t,re) from the offline data D,,, computes a lower confidence bound L, for each context and action based on the cur- rent network parameter ( extracts greedy policy मे with respect It, and updates ( by minimizing a regularized squared loss function C.(W) using stochastic gradient descent. Note that Algorithm updates the network using one data point time does not use the last sample (I,,, an, rx)) for decision-making and takes the average of an ensemble of policies { 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 fn as the returned policy. At step I, we can also train the network on random batch of data from D. (the "B-mode" variant as discussed in Section 6).
4 GENERALIZATION ANALYSIS
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. (2020)). Denote (1) (1)
(1())nn Jizl
(ætaa E Rdd :t [m], E []]] H 1.
= i.j = (1) x0)) and
A
Σ ij
((+1) 2
(u.) ((())()()))),
4

---

Published as a conference paper at ICLR 2022
(1+1) The neural tangent kernel (NTK) matrix is then defined as H = (H + 1/2
n =
[o'(w)o' (v)] 2;j
Here, the Gram matrix H is defined recursively from the first the last layer of the neural network using Gaussian distributions for the observed contexts (ax(9) )=s Next, we introduce the assump- tions for our analysis. First, we make an assumption about the NTK matrix H and the input data.
Assumption 4.1. 3AD > 0, H ž AoI, and Vi E [nK], || = 1. Moreover, [ar(0], =
[xx0] I////2 Vi E [nK].j E [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 $6-1, Such assumption is commonly made in overparameterized neural network literature (Arora et al., 2019; Du et al., 2019b;a; Cao & Gu, 2019). The non-singularity is satisfied when e.g. any two contexts in {x)+) are not parallel (Zhou et al., 2020), and our analysis holds regardless of whether λo depends on n. 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 æ such that 1 ||æ|||2 = we can always construct a new input x'' = / (ar, a:] T the second part of Assumption 4.1 is mild and used merely for the theoretical analysis (Zhou et al., 2020). In particular, under Assumption 4.1 and the initialization scheme in Algorithm 1, we have fwoo (x(")) = 0, Vi E [nK].
Next, we make an assumption the data generation.
(+())))))))) Assumption 4.2. Vt, 2 is independent of D:-1, and 3x E (0, oo). a( 1,
Il S n. Vt E [n]]
The first part of Assumption 4.2 says that the full contexts are generated by process independent of any policy. This is minimal and standard in stochastic contextual bandits (Lattimore & Szepesvári,
2020; Rashidinejad et al., 2021; Papini et al., 2021), e-g., when {ax, {a=))__ i.idd
p. The second part of Assumption 4.2, namely empirical single-policy concentration (eSPC) condition, requires that the behaviour policy ju has sufficient coverage over only the optimal policy π in the observed con- texts. Our data coverage condition is significantly milder than the common uniform data coverage assumptions in the OPL. literature (Munos& & Szepesvá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 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, a can be dependent on both æ, and D:-1- This is more practical as it is natural that the offline data was collected by an active learner such as Q-learning agent (Mnih et al., 2015).
Next, we define the effective dimension of the NTK matrix on the observed data as = log det(I++/A) This notion of effective dimension was used in (Zhou et al., 2020) for online neural log(1+ 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 kernel- ized 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 5 E (0, 1), under Assumption 4.1 and 4.2, if the network width m. the regu- larization parameter X, the confidence parameters {Br} and the learning rates {ne) in Algorithm satisfy
m 2 poly(n, (n, K, , Ap log(1/))): X Z max ma
1/2 for some absolute constant Cs, 8 / CatL (12 1/2 + (nK) 1/2) m m1/2
L
where -1 = 2 5/ 17/6 log 1/2 m) V 2/mA1/2 (00mAt/21og"//2 (n + 4)/8)),
T V
5

---

Published as a conference paper at ICLR 2022
then with probability at least 1-6 over the randomness of W and Dn, the sub-optimality of i
returned by Algorithm 1 is bounded as
nL E. [SubOpt(*)] S kVay 0log(1 + nK/A)) 2 RVN + /2n log( (10n + 4)/8),
where d is the effective dimension of the NTK matrix, and K is the empirical single-policy concen- tration (eSPC) coefficient in Assumption 4.2.
Our bound can be further simplified E[SubOpt(#t]] Ö( max max(Vā, n-12)). A detailed proof for Theorem 4.1 is omitted to Section A. We make several notable remarks about our re- sult. First, our bound does not scale linearly with p or vD as it would if the classical analyses (Abbasi- Yadkori et al., 2011; Jin et al., 2020) had been applied. Such a classical bound is vacu- ous for overparameterized neural networks where p significantly larger than n. Specifically, the online-like nature of Neural. LCB allows us to leverage matrix determinant lemma and the notion of effective dimension in online learning (Abbasi- Yadkori et al., 201 I: Zhou et al., 2020) which avoids the dependence on the dimension p of the feature space as in the existing OPL methods such (Jin et al., 2020). Second, as our bound scales linearly with v 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 cov- erage 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 liter- ature (Munos& & Szepesvá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 stationar- ity of the offline policy, allowing an offline policy with correlated structures as in many practical scenarios. Note that Zhan et al. (2021) have also recently addressed the problem of off off-policy eval- uation with such offline adaptive data but used doubly robust estimators instead of direct methods as in our paper. Fourth, compared to the regret bound for online learning setting in (Zhou et al.,
2020), we achieve an improvement by a factor of V while reducing the computational complexity from (n²) to On)). 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., 2020).
Finally, to further emphasize the significance of our theoretical result, we summarize and compare 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 uncertainty- agnostic (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 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 (Dependent) indicates that the offline actions can be dependent on the past data. It can be seen that our result has 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., 2020) to improve their regret and optimization complexity.
RELATED WORK
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 al., 2021; Xiao et al., 2021) and linear models (Duan & Wang.

---

Published as a conference paper at ICLR 2022
Table 1: The SOTA generalization theory of OPL with function approximation.
Work
Function
Type
Optimization
Sub-optimality
Data Coverage
Data Gen.
Yin & Wang (2020)*
Tabular
Groody
Analytical
VIII- - - 1/2 (e-n-1/2 +d.n-))
Uniform
Rashidinejul et al. (2021)
Taabuar
Pessimism
Analytical
SPC
Duan Wang (2020y*
Linear
Greedy
Analytical
Uniform
al. (2020)
Lineur
Pessimism
Analytical
Ö (d-n 1/21
Uniform
Nguyen-Tang Tang et al. (2021)
Narrow ReLU
Greedy
Ornele
δ (VR- selte)
Uniform
This work
Wide ReI.U
Pessimism
SGD
Ó(e Vdl 1d/)
cSPC
LDD
a, The bounds of these works are for off-policy evaluation which is generally easier than OPI, problem.
2020; Jin al., 2020; Tran-The et al., 2021). The most related work OPL with neural function approximation we are aware of are (Brandfonbrener et al., 2021; Nguyen-Tang et al., 2021; Uehara et al., 2021). However, Brandfonbrener et al. (2021); Nguyen-Tang al. (2021); Uehara 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 family of experts (Auer, 2003), 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 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 oracle, and have cubic computational complexity, respectively, while our method with neural networks are both statically and computationally efficient where it achieves /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., 2020; 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;;; Allen et al., 2019; Nguyen, 2021). For generalization aspect, (stochastic) gradient descents can train an overparameterized neural network to 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., 2020), that is proposed for the setting of online contextual bandits with neu- ral networks, in the sense that both algorithms use neural networks, learn with 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 Neural.CB from NeuralUCB is that while NeuralUCB trains new neu- ral network from scratch at each iteration (for multiple epochs), Neural.CB 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 (nn)) to O(n), while still guaran- teeing a provably efficient algorithm. Moreover, NeuraLCB achieves a suboptimality bound with a better dependence on the effective dimension than NeuralUCB.
EXPERIMENTS
In this section, we evaluate NeuraL.CB and compare it with five representative baselines: (1) LinLCB (Jin et al., 2020), which also uses LCB but relies on linear models, (2) KemnLCB, which approximates the reward using functions in RKHS and is an offline counterpart of Ker- nelUCB (Valko et al., 2013), (3) NeuralLinLCB, which is the same as LinLCB except that it uses
In practice, each time step the entire data collected up time f.
f, NeuralUCB trains neural network for f epochs using gradient descent in
7

---

Published as a conference paper at ICLR 2022
20
0.25
2.3
Mec
Sub-qptriatt
Meunatrredd Lit
0.21
Meuraliin
NeuraLCB
Now-LLC Neurlöreed
MeuralinSrwwdy
Slurslyreedy unace
KarnLCD
Laica
0.5
Nour Lincc
6.12
0.0
KomLCB
6.5
2300
6307
5000
5950
2000
4302
0003
1000
2000
5000
6000
5000
Namber of sam plas
Number samples
Namber sampp
(a) h(u) 10(a" u)2
(h) h(u) u² Au
(c) h(u) cos(3a"
Figure 1: The sub-optimality of Neural.CB versus the baseline algorithms on synthetic datasets.
((x.) = vee( Swroo (xx)) (aa)) as the feature extractor for the linear model where fw is the same neural network of CeuraL.B at initialization, (4) NeuralLinGreeddy which the same as Neu- ralLinLCB 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, pseudo-code of these baseline methods in Section D. Here, we compare the algorithms by their generalization ability via their expected sub-optimality. For each algorithm. we vary the number of (offline) samples n from to T where 7 will be specified in each dataset, and repeat each experiment for 10 times. We report the mean results and their 95% confidence intervals."
present the
Approximation. To accelerate computation, we follow (Riquelme et al., 2018; Zhou et al., 2020) approximate large covariance matrices and expensive kernel methods. Specifically, as NeuraLCB and NeuralLinLCC involve computing a covariance matrix A, of size p x where m²(L 2) is the number of the neural network parameters which could be large, we approximate A, by its diagonal. Moreover, as KernLCB scales cubically with the number of samples, we use KernLBB fitted on the first 1, 000 samples if the offline data exceeds 1, 000 samples.
md + m +
Data generation. We generate offline actions using a fixed e-greedy policy with respect to the true reward function of each considered contextual bandit, where c set 0.1 for all experiments in this section. In each run, we randomly sample = 10, 000 contexts from p and use this same test contexts to approximate the expected sub-optimality of each algorithm.
Hyperparameters. We fix X = 0.1 for all algorithms. For NeuraLCB, we set B, = B, and for Neu- rai.CB, LinL.B, KernI.CB, and NeuralL.nnl.CB, we do grid search over {0.01, 0.1 1,5, 10) for the uncertainty parameter B. For KernLCB, parameter a and do grid search over 10.1, 1, 10} for a.. For NeuraLCB and NeuralGreedy, we use Adam optimizer (Kingma& & Ba, 2014) with learning rate 1) grid-searched over (0.0001, 0.001) } and set the lg-regularized parameter to 0.0001. For NeuraLCB, for each Dr, we use f as its final re- turned policy instead of averaging over all policies { 1f 1f-1 Moreover, and NeuralGreedy over two training modes, namely (S-mode, B-mode} where at each iteration i, S- mode updates the neural network for one step of SGD (one step of Adam update in practice) on one single data point (æ,, rz) while B- B-mode updates the network for 100 steps of SGD on a random batch of size 50 of data D, (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., 2020) as Neural reuses the neural network parameters from the previous iteration instead of training from scratch for each new iteration. For NeuralLinI.CB. NeuralLinGrredt Greedy, we use the same network architecture with = and add layer normalization (Ba et al., 2016) in the hidden layers. The network width will be specified later based on datasets.
the radius basis function (RBF) kernel with
grid search NeuraLCB
Neural.CB, CC,, and Neural-
6.1 SYNTHETIC DATASETS
For synthetic experiments, we evaluate the algorithms on contextual bandits with the synthetic non- linear reward functions h used in (Zhou al., 2020):
h1(4) 10(u a) h2(u) u AT A Au, ha(u) cos(3u a),
"Our code repos: https://github. com/ wtw.//////aaaceeeeeeoooeeeeoteet hww.:hhww.....tttmomoooooennnnne
__badits..
8

---

Published as a conference paper at ICLR 2022
0.31
3.A
Lano
(eite
Mevid sirees
1b0 able 18600 30b6
200 128 0b0
180
Lib0 1868
200 Sunber
dai
1900 tie Mnd 15e 1900 uvvn 14100
Horror diamppia
Mushroom
(b) Statlog
(c) Adult
(d) MNIST
Figure 2: The sub-optimality of NeuraLCB versus the baseline algorithms on real-world datasets.
where E Rd is randomly generated from uniform distribution over the unit sphere, and each entry of A E Rexdd is independently and randomly generated from (O, 1). For each reward function h;, & where ~ (0, 0.1). The context distribution p for three cases is the uniform
rt h4 (a. 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.
6.2 REAL-WORLD DATASETS
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 repre- sent 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 Mush- room 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., 2020). Specif- ically, for each input I E Rd in a K-class classification problem, we create K contextual vectors (O..... ... 0, x) RdK The learner receives reward 1 if it selects context xx where is the label of æ, and receives reward otherwise. Moreover, we choose the network width 100 and the maximum sample number T 15, 000 for these datasets.
xx (z, O, ..... 0), ....... x
6.3 RESULTS
Figure I and 2 show the expected sub-optimality of all algorithms on synthetic datasets and real- world datasets, respectively. First, due the non-linearity of the reward functions, methods with linear models (LinLCB, NeuralLinLCCB, NeuralLinGreedu and KernLCB) fail in almost all tasks (except that LinLCB and KemnCB have competitive performance in Mushroom and Adult, respec- tively). In particular, linear models using neural network features without training (NeuralLinI.CB and NeuralLin enrrely barely work any datasets considered here. In contrast, our method Neu- raL.BB outperforms all the baseline methods in all tasks. We remark that NeuralGreedy has sub- stantially lower sub-optimality in synthetic datasets (and even a comparable performance with Neu- raLCB in h1) than linear models, suggesting the importance of using trainable neural representation in highly non-linear rewards instead using linear models with fixed feature extractors. On the other hand, our method NeuraLCB outperforms NeuralGreedy in real-world datasets by a large mar- gin (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 (Aduli and slightly well in Statlog and MNIST), but the cubic com- putational complexity kernel methods make it less appealing 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., 2020) to learn the kernel in KernI.BB for only the first 1, 000 samples and keep the fitted kernel for the rest of the data (which explains the straight line of KernL.B 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 (even in the B-mode 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 each iteration) outperforms the B-mode, fur- ther confirming the effectiveness of the mnline-like nature in NeuraLCB. In Section F, we reported the performance of S-mode and B-mode together and evaluated dependent offline data.
slight modification of the

---

Published as a conference paper at ICLR 2022
7 ACKNOWLEDGEMENT
This research was partially funded by the Australian Government through the Australian Re- search Council (ARC). Prof. Venkatesh is the recipient of an ARC Australian Laureate Fellowship (FL170100006).
REFERENCES
Yasin Abbasi-Yadee Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for lin- ear stochastic bandits. In John Shawe-Taylor, Richard S. Zemel, Peter L. Bartlett, Fer- nando C. N. Pereira, and Kilian Q. Weinberger (eds.), Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Sys- tems 2011. Proceedings of meeting held 12-14 December 2011, Granada, Spain, pp- 2312-2320, 2011, URL https: ptttps://pproceedingg htwp:/eeeeeinnnnneeeieeeeeeeeeee neuriesrsss. wwtpc//pppp///////c/ccppp eobbelccffe 7 4555 Abst html.
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. International Conference on Machine Learning, pp. 1638-1646. PMLR, 2014.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. International Conference on Machine Learning, pp. 222-252. PMLR, 2019.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. arXiv preprint 1904 2019.
Susan Athey and Stefan Wager. Policy learning with observational data. Econometrica, 89(1): 133-161, 2021.
Peter Auer. Using confidence bounds for eeppittttiiieeeplllatttinnoo trade-offs. J. Mach. Learn. Res., 3(mull):397-422 March 2003. ISSN 1532-4435.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey Hinton. Layer normalization. arXiv preprint arXiv:1607.064500, 2016.
Mikhail Belkin. Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation. arXiv preprint arXiv:2105. 11121000.136.... 14368, 2021.
David Brandfonbrener, William Whitney, Rajesh Ranganath, and Joan Bruna. Offline contextual bandits with overparameterized models. In International Conference on Machine Learning, pp- 1049-1058. PMLR, 2021.
Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvári. X-armed bandits. Journal of Machine Learning Research, 12(5), 2011.
Jacob Buckman, Carles Gelada, and Mare Bellemare. The importance of pessimism in fixed- dataset policy optimization. arXiv preprini arXiv:2009.06799 2020.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances Neural Information Processing Systems, 32:10836-10846. 2019.
Nicolò Cesa-Bian Bianchi, Alex Conconi, and Claudio Gentile. On the generalization ability of on-line learning algorithms. IEEE Trans. Inf. Theory, 5009):000--200 2057, 2004. doi: 10. 10.1109/TY12004. 833339. URL https: /tt. org. 110.0.11991111111 1109/TIT. 2004. 833339.
Jinglin Chen and Nan Jiang. Information- considerations in batch reinforcement learning. In ICML, volume 97 of Proceedings of Machine Learning Research, pp. 1042-1051. PMLR, 2019.
Simon S. Du, Jason D. Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai Gradient descent finds global minima of deep neural networks. In JCML, volume 97 of Proceedings of Machine Learning Research, pp. 1675-1685. PMLR, 2019a.
10

---

Published as a conference paper at ICLR 2022
Simon S. Du, Xiyu Zhai, Barnabás Póczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In ICLR (Poster). OpenReview.net, 2019b.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL ics. uci. edu/ml.
Yaqi Duan and Mengdi Wang. Minimax-optimal off-policy evaluation with linear function approx- imation. CoRR, abs/2002.09516. 2020.
Yaqi Duan, Chi Jin, and Zhiyuan Li. Risk bounds and rademacher complexity in batch reinforcement learning. arXiv preprint arXiv:2103. 2021.
Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. International Conference on Machine Learning, pp. 2052-2062. PMLR, 2019.
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(1): 2019.
Boris Hanin and Mihai Nica. Finite depth and width corrections to the neural tangent kernel. arXiv preprint arXiv: Tttv:/900 1wt.i99999.99.... 2019.
Yichun Hu, Nathan Kallus, and Masatoshi Uehara. Fast rates for the regret of offline reinforcement learning. In COLT, volume 134 P Proceedings of Machine Learning Research, pp. 2462. PMLR, 2021.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. arXiv preprint arXiv:1806.07572. 2018
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline r!? CoRR, abs/2012.15085, 2020. URL https: //arxiv/ wwwp//////////oeeeeeae 15085.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Toru Kitagawa and Aleksey Tetenov. Who should be treated? empirical welfare maximiza- tion methods for treatment choice. Econometrica, 86(2):591-616, 2018. doi: https://doi.
09//10..982//CCA112288 URL 3982/ECTA13288
wiley. com/doi/abs/11
Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Multi-armed bandits in metric spaces. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pp. 681-690, 2008.
Andreas Krause and Cheng Soon Ong. Contextual gaussian process bandit optimization. In Nips, pp. 2447-2455, 2011.
Sascha Lange, Thomas Gabel, and Martin Riedmiller. Batch reinforcement learning. Reinforce- ment learning, pp. 45-73. Springer, 2012.
John Langford and Tong Zhang. The epoch-greedy algorithm for contextual multi-armed bandits. Advances in neural information processing systems, 20(1):96-1, 2007.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020. doi: 10.1017/978 108571400
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-333 1998.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tuto- rial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643, 2020.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(7540):52-5333 2015.
11

---

Published as a conference paper at ICLR 2022
Rémi Munos and Csaba Szepesvári. Finite-time time bounds for fitted value iteration. J. Mach. Learn. Res., 9:815-8571 2008.
Quynh Nguyen. On the proof of global convergence of gradient descent for deep relu networks with linear widths. arXiv preprini urXiv:2101.09612 2021.
Thanh Nguyen-Tang, Sunil Gupta, Hung Tran-The, and Svetha Venkatesh. Sample complexity of offline reinforcement learning with deep relu networks, 2021.
Xinkun Nie, Emma Brunskill, and Stefan Wager. Learning when-to-treat policies. Journal of the American Statistical Association, 116(533):392 000224092220 2021.
Matteo Papini, Andrea Tirinzoni, Marcello Restelli, Alessandro Lazaric, and Matteo Pirotta. Lever- aging good representations in linear contextual bandits. arXiv preprint arXiv:2/04.0378/ 2021.
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline rein- forcement learning and imitation learning: A tale of pessimism. arXiv preprint arXiv:2103. 12021, 2021.
Carlos Riquelme, George Tucker, and Jasper Snoek. Deep bayesian bandits showdown: An empirical comparison of bayesian deep networks for thompson sampling. arXiv preprint arXiv: 2018.
Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. cess optimization in the bandit setting: No regret and experimental design. arXiv:0912.3995, 2009.
Gaussian pro- arXiv preprint
Alex Strehl, John Langford, Sham Kakade, and Lihong Li. Learning from logged implicit explo- ration data. arXiv preprint 1003.01 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 on Artificial Intelligence, AAAI' 17, pp. 4740-4745, AAAI Press, 2017.
Hung Tran-The, Sunil Gupta, Thanh Nguyen- Tang, Santu Rana, and Svetha Venkatesh. Combining online learning and offline learning for contextual bandits with deficient support. arXiv preprint arXiv:2107.11 15333, 2021.
Masatoshi Uehara, Masaaki Imaizumi, Nan Jiang, Nathan Kallus, Wen Sun, and Tengyang Xie. Finite sample analysis of minimax offline reinforcement learning: Completeness, fast rates and first-order efficiency. arXiv preprint urXiv:2102.02981, 2021.
Michal Valko, Nathaniel Korda, Rémi Munos, Ilias Flaounas. and Nelo Cristianini. Finite-time analysis of kernelised contextual bandits. arXiv preprint urXiv:/309.688 2013.
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. 11362-11371. PMLR, 2021.
Pan Xu. Zheng Wen, Handong Zhao, and Quanquan Gu. Neural contextual bandits with deep representation and shallow exploration. arXiv preprint arXiv:2012.017800 2020.
Lin Yang and Mengdi Wang, Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning, pp. 10746-10756. PMLR, 2020.
Zhuoran Yang, Chi Jin, Zhaoran Wang, Mengdi Wang, and Michael Jordan. On function approx- imation in reinforcement learning: Optimism in the face of large state spaces. arXiv preprint arXiv:2011.04622 2020.
Ming Yin and Yu-Xiang Wang. Asymptotically efficient off off-policy evaluation for tabular reinforce- ment learning. In AISTATS, volume 108 of Proceedings of Machine Learning Research, pp- PMLR, 2020.
12

---

Published as a conference paper at ICLR 2022
Ming Yin and Yu- Yu-Xiang Wang. Characterizing uniform convergence in offline policy evaluation via model-based approach: Offline learning, task-agnostic and reward-free. 2021.
Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal provable uniform convergence in offline policy evaluation for reinforcement learning. In Arindam Banerjee and Kenji Fukumizu (eds.), The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event, volume 130 of Proceedings of Machine Learning Research, pp. 1567- html.
1575. PMLR, 2021. URL http: http:p://ppoceeingg..... mlr
Ruohan Zhan, Vitor Hadad, David A Hirshberg, and Susan Athey. Off-policy evaluation via adap- tive weighting with data from contextual bandits. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 1125-2135, 2021.
Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-based exploration. In International Conference on Machine Learning, pp. 1 11492-1 1502. PMLR, 2020.
13

---

Published as a conference paper at ICLR 2022
A PROOF OF THEOREM 4.1
In this section, we provide the proof of Theorem 4.1.
Let D, aT; (r)arr: hirgt- Note that f returned by Algorithm 1 is D Denote E = -1, Øe.. Let the step sizes {n,} defined as Theorem 4. and the confidence trade-off parameters { defined in Algorithm I, present main lemmas below which will culminate into the proof of the main theorem.
Lemma A.1. There exists absolute constants Ci, C2 > such that for any E (0, 1), mn satisfies
m 2 max { (0(nA-1 log" m). O(L K Nn (o 1)/6))
O (1og (nK 1)/8) log
1o2- m))
then with probability least 1 - 6, it holds uniformly over all t [n] that
SubOpt(f;;z;) $ 23 10 ( [ [IV + 22 1/6 log 1/2 mL 7/3 /L 1/2 + 2v 22 2 m 11/6 log
[
(I), m A DD 2
122 mlt 1/6 L 10/3 x-133-11/0
Lemma A.I gives upper bound on the sub-optimality of the returned step-dependent policy म. on the observed context æ, for each t E [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 does not require the offline data be informative about any sub-optimal actions. However, the upper bound depends on the unknown optimal policy n while the offline data has been generated a priori by different unknown behaviour policy. This distribution mismatch is handled in the next lemma.
Lemma A.2. There exists absolute constant C3 > 0 such that for any d (0, 1), if m and X satisfy
A M max (1, (()), m max (0(1 log m), O(L" 1 + 2)/8))
9(2-1\1/2(og 3/2 (nK (n 2)/8) log 3/2 m))
then with probability at least 1 - 8, we have
1a (V mm 11/21|, 1
1D
71
23nk / /álog(1+ + + (22
+Bus(Ca/V2) 1/2 log
1/2
(3 1/
+ ())))))8))
where C22 is from Lemma A.
We also remark that the upper bound in Lemma A.2 scales linearly with Vā instead of with vp if standard analysis were applied. This avoids a vacuous bound as p 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 online- argument. In particular, a key technical property
like nature of Algorithm 1 and an of Algorithm that makes this generalization possible without uniform convergence that म, is D. -eesurllee and independent of (It, at, rt).
Lemma A.3. For any d E (0, 1), with probability at least 1- over the randomness of Dnn we have
E [SubOpt(4)] < 1 E SubOpt(ft: x1) + V (1g))
14

---

Published as a conference paper at ICLR 2022
We now ready to prove the main theorem.
Proof of Theorem 4.1. Combining Lemma A.I, Lemma A.2, and Lemma A.3 via the union bound, have
[[)bbpt(ft) S KVTl /llog( + T2 xynla I4 +T + 2 log((10n + 4)/0),
SkVKy dlog(1 + nK/A) + KV + 2n 1onlog(10)) 10n + 4)/6)
where is chosen to be sufficiently large polynomial of (n, L, K, X N1 that
such
1/2 1 T 11=22//A++33 X, m-1121212
+ (nK)
I2 : 10011+2200hh//mmm=00000gm////// 1 2
1/6
F3 LL,Tn(CC/V/2) log 1/2 ((10n 4)/6) $
T4 2C 1/6 77 51
[3 = 2V 1/2 11/6 (log////oooo//g/ 1/2 10/3 s 1.
B PROOF OF LEMMAS IN SECTION A
B.1 PROOF OF LEMMA A.1
We start with the following lemmas whose proofs are deferred Appendix B.
Lemma B.1. Let
[M(x()),, (( E RRnK There exists W W such that for any 8 (0, 1). if m 2 O(L K* X log L/8)), with probability at least over the randomness of ((),, it holds uniformly for all [nk] that
| - ( < /2m 1/2
-2mm-/21lballess 1/21|/2l
(x) W w( h(x(1)).
Remark B.I. Lemma B.I shows that for a sufficiently wide network. there a linear model that uses the gradient of the neural network at initialization function in the training inputs. Moreover, the weights W of the linear model is in a neighborhood of the initialization (0)), Note that we also have
feature vector and interpolates the reward
S | /bll2 1 H- VnkX,
where the second inequality is by Assumption 4.1 and Cauchy-Schwartz inequality with h(() E [0, 1], Va. Lemma B.2. For any 8 E (0, 1), if m satisfies
m 2 O log m) v V (3n
and the step sizes satisfy
T/ where - = (n2 3/6 log m) v 1(RmX-/2 log 1/2 (2
then with probability at least 8 over the randomness of ( (0) and D, it holds uniformly for all t [n], [L] that
|
w( IF
t
and ||A||/2 5 S CaIL
MXI.
where C3 O absolute constant from Lemma C.2.
15

---

Published as a conference paper at ICLR 2022
Remark B.2. Lemma B.2 controls the growth dynamies of the learned weights W, around its ini- tialization and bounds the spectral norm of the empirical covariance matrix A, 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 > such that for any (0, 1). ifw satisfies
((m 1/22 3/2 -/2 3/2 (nK/ V log 3/2 m) I w I ((L 9/2 log m).
with probability at least 1 - å over the randomness of W it holds uniformly for all W E ((W()):) w) and E [nK] that
V fV (x - VSw [Ir S C2 Vlg mw 1/3 V Swin IIl
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 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 8 (0, 1) over the randomness of W if satisfies
(m 3/2 1/2 1.-3/2 3/2 log 3/2 (nKT. /5)) S S ( log m),
with probability at least 5, it holds uniformly for all W. W B(W (0); w) and E [nK] that
lfww - fw (z) fw W' w) - C₁ - w mlogm.
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.I. For all E [n]. Rdd we define
U((u)= Swi (u)) + 3 Vw (1)) m m-21111 11
Luu)) = -wwc-u 3 V Swit (1) m mm2111111 |/21,,,,
(((u) (V.wa-n) (u), ((-1)) W())) + 3 V.f (z) (u)mmm111 -1/21| -1/2||A_1 ||
(u),
(u) (V.wa--) (u), ((-1)) W( 8 V (u) -1/2 A
C. = ( W: W - | S 8-
Let E be the event in which Lemma B.I. Lemma B.3, Lemma B.3 for all w
(V=it MAL 15 n2 and Lemma B.4 for all w E {v mAL :1sism) n) hold simultancously.
Under event &, for all f E [n], we have
| (t)) ll. I | (1 A
< (I w( ( (t) ((0l
3 (22mm 112 +// 1/2 111mmm1122/ -1 CGtL Br,
where the second inequality is by the triangle inequality, and the third inequality is by Lemma B.1 and Lemma B.2. Thus, W' C., Vt E [n).
Denoting at 7" (-|ax,) and à, #e (-(.)))) under event &, have SubOpt(#t; x;) = E, [ )] E, [z(,,,,,).))
(a) E, ( (= w - (w Eg V fW (II,a.): W - -W(0)]
(b)
( W - -w/00)]]
- E, (V/aa) W - [(oow]
E.
16

---

Published as a conference paper at ICLR 2022
+ W - - Ex VV ( - ( (2r,a))
+ V V
V V.wio (21,,)))))
(9)
2 E, ( (V W W w - E, (Vora-D(Eaa) W -W(o))
+ 22 202m0 11/6 log mt I 10/3 >-16
"
2 E. [Ti( )] BB, (20e,
11/6 + 2222225m 110/// log 1/2 m21//1, 1,10333 10003~110 -2/6
= E. ()(()),7)) }] E. (xt,,a))
+ E W/ (Zt.a;)) W(t-1) W( (we-n((ara) + Swi (2) }
+ E fwie- (I),a.) ( (V ( w((-1) w - -W(
E, (w (a) )] + E, (f +2 +2/2C25m 11100 log 1/2 //0 10/3 1 -1/6
log
=U by symmetry at initialization
2 E2 (U((2)ta))) )] 10--A E, [Tx( + R2 (T(( )]
R. [Te (Trt,
50 by pessimism
+ 20, 2//3 /2 1
1/2 mL7133 x -1/2 222222222200 2V2025 -111/00mm111ppmmmm log mt! 1 10 1 X-16
1/2
(
S
E. [Ue(Zrr,;) }] Er (L<r,,));)
+ +0,,1 1/33mm -1/6 log 1/2 ml.7/3 /3 x - 2V222 11/6 log 10
14, | [IV (z),a)) m -1/1111A,1 |
+ +C, 1/6 log 1/2 mL 7/3 // + 2v 20 2025mmmmmmmm 11/6 log" 1/2 ml 16 x-
11/6
where (a) is by Lemma B. (b) is by the triangle inequality, (c) is by Lemma B.1, Lemma B.2, and Lemma B.3, (d) is by W E C,, and by that max / Sy (a, u - bo) = (a, b- -b) +>||a||
and min b (a, u - bo) (a, b b)) >||a|| 1, (e) is by Lemma B.4 and by that S (0) 0, Vi E [nK]. and (ʃ) is by that à, is sampled from the policy *, which is greedy with respect to L.,
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.S. For any 8 E (0, 1), if i' satisfies
m 2 max (o(mA-1 log m), ((L-1 3/2 (n v log 3//2 m)),
+2) }
and X 2 max(C3L, 1}. then with probability at least 1 8, it holds simultaneously that
det(AA)
(f m 1/2 1/ A,
< 2loog det(2I)
Vt E [m].
dct(AA)
loog dct(A,)
log det(AI)
$ 22CgC2/3/2 1/6 13/300 Vt E [n],
det(AI)
det(An)
log det(
< dllogL + nK/)) +1,
17

---

Published as a conference paper at ICLR 2022
where A, = + Ei=1 Ve (w (Zi,a))) veel V fwio ))a 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 || 2 X, Vt. Let be the event in which Lemma B.2, Lemma C.2 for all w E {v MAx. 1 iissin my. and Lemma B.5 simultaneously hold. Thus, under event E, have
WV m 1/2 1 A S ( m 1 |A S C3L
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 - 8, it holds simultaneously for all & [m]] that
||V fw:cn(EEraa) 1m11111,,, 11,,,,,1 (D 21
2,
m.))
[Viwe (xtt,a) m 1/2 mm11// A 1,
$ 2/ V Swa 1 (xtaa)) m - || + 2C, 1/ log' ( + 2)/8).
Hence, for the choice of in Lemma A.2, with probability at least 6, we have
|| [V m m A 1.|1e-1, 1 B1- Ba; ~ (11as)
V (wra) mm
1-111111 1/2
AA +
C3
3 Banl 1/2 1/2 log ((2n + 22/8)
1/2
11
v2
Knk
C3 Ln 1/2 1/2 log 1/2 2/5m + 2)/8)
Vn
(W m m1122112
+
A71
V2
K
log (An) det(AT)
C3 11 1/2 1/2 + 2)/6)
+
Vn
V2"
/28nk
det(An)
C3 3 1/2 1/21og v2
log det(AI)
+ +
log 10gggg//(() 12(nnn + 2)/8)
Vn
V28nk
dlogg1
+ 1 ||
V
C3 1122
12 12 ((5n 2)/5),
/2
where the first inequality by 3r < 3n. Vl E [n). the second inequality is by Cauchy-Schwartz inequality, the second inequality and the third inequality 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 E [n], define
7, = SubOpt(#tt) +t) SubOpt(#t;;;)) m.).
Since 9t is Dt-11-meaaa -meaurbble and is independent of æ,, and æ, independent of D,-1 (by As- sumption 4.2), we have E. [_]] = 0, VI. E [m). Note that -1 S 2r S 1. Thus, by the Sbeffding-Azuma inequality, with probability at least 1 - 5, we have
E[SubOpt(Ft] = Σ SubOpt(#t) = SubOpt(fx;zz) +
1 Σ Zi
t=l
18

---

Published as a conference paper at ICLR 2022
Sub 1 (18)
C PROOF OF LEMMAS IN SECTION B
C.I PROOF OF LEMMA B.1
We first restate the following lemma.
Lemma C.1 (Arora et al. (2019)), There exists an absolute constant ai > 0 such that for any e 0, (0, 1), if m 2 ( for any i.j E [nK], with probability least 1 over the randomness of W((), we have
fV (x (1 Haslse.
Lemma C.I 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.I. Let G= m-1222[[vee)) Swio (x)()),, veo V ww (ax ()) E RXxnK
For any > 0,8 (0, it follows from Lemma C.1 and union bound, if 2 O(L -4 1o)(nLL/0)), with probability least 1 - ò, we have
||G - H|Ie & nk [KK] G H = nK max (m 1mm111p (V fV (x f (x) - Hiyl
b
Snke.
Under the event that the inequality above holds, by setting c 2n we have
-
No G G r
1 H.
(2)
Let G PAQ" be the singular value decomposition of G where P E Rpxnk Q Bnk xnk
have orthogonal columns, and A E Rak is diagonal matrix. Since GT G H An positive definite, A is invertible. Let W W such that vee(W*) voo voc(W(() W()) m 1/2 2 h. we have
Ag
PA- 1
m 1/2 GT (vec(W"))) vec -AA" h. h.
Moreover, have
m W w(0) 12 mll vec (o vec (0)) - h
h hTQAA QA -Q h hTT (G" G) < 2h H
where the inequality 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 d E (0, 1) over the randomness of (()), if w satisfies
(mm 3/2 L
3/2 log 3/2 (nKL2 /0)) S w S O(L "lg m),
with probability at least 5, it holds uniformly for all W E B(W());)) i E [nK], I [7.] that
(z < Cg vn.
19

---

Published as a conference paper at ICLR 2022
Proof of Lemma B.2. Let 8 (0, Let (WW = (f ( -ra)2+ + mA WW w be the regularized squared loss function on the data point (z)). Recall that W w(t-1) "/ (W By Hoelfding's inequality and that ry is R-subgaussian, for any [n]], with probability at least 1 ō, we have
Inal - ER [ra]l + R / 2ogg
E I 3e, a.ll + 2 log
= E [1( ) [D 2t, Ct, ail + 2ogg/lll/////0 - + + RV 2 (2/))
(3)
By union bound
and (3), for any sequence
{wi {w])e(N))
such that
3/2 20 (L22KKL3/000
Wt S O(L $ log -3 m) A O(L log 3/2 m). Vt e [n],
with probability at least - 6, it holds uniformly for all W E ((W())
E [L] E [n] that
(V) = (f
- re) + mm(Wi W ( >|F
(WW.) (at,a)) - Swros (V (a W - )(
Vifw (f w (z). + Vifw (Br W -
Vifw (Z) mA(W; - I
Visw (2 (/ (3),, - Sw (V W W(
V Vifw ( (z) )f (I I
W - 1l
+ Vill: ) IF + md/ W (1 ||
S CiCzu, 2/3 L Lmm log m C/m3/2( + R 2log((n))))) + C3Lms + mXws,
where the first inequality is triangle's inequality, and the second inequality is by Lemma B.4, Lemma C.2 and (3).
holds, W E B B(W(O); AAT.) Vt E [n]. It trivially holds for O. Assume W B (W (0); mAT.). Vi
We now prove by induction that under the same event that (4) with We MAL
A Indeed, it is easy to verify that there ex- ist absolute constants (c,)²=1 > O such that if m satisfies the inequalities in Lemma B.2, then @(m 3-/2
[t 1]. we will prove that (t e ((W(")
3/2 log 3/2 3/2 (3n3)K S mAL I O(L-6106) log 3 m) O(L log 3322 m), Vi e [n]. Thus, under the same event that (4) holds, have
[|
w/ (
W ((( 11 F Σ Th VILL
$ 1tt1Csm 1/3 2/33 7/3 7/3, 1/6 log 1/2 m + itm 1/2 1/2
+ 20 1/2 RV log /2 (6n/8))
t $ 2 mXL 2V mAL mAL' where the first inequality is by triangle's inequality, the first equation is by the SGD update for each W the second inequality is by (4) and the last inequality is due to be chosen
t
N 1/ [ + R log (6(//))
2 1/2 1/2 (C1Cmm - 7/3 1/6 log 1/2 m +m +1-111221112111111(3----
log which is satisfied for -1 2/n m// - 17/6 log 1/2 m) v 10
For the second part of the lemma, we have
|| = JAI+ + Σ
veo ( vec( (V /m/
1=1
20

---

Published as a conference paper at ICLR 2022
S Σ ( & A C3th,
where the first inequality is by triangle's inequality and the second inequality is by | W I mx Vi E [n] and Lemma C.2.
C.3 PROOF OF LEMMA B.5
Proof of Lemma B.5. Let (() be the event in which the following (n + +) events hold simultane- ously: the events which Lemma B.3 for each E {v mAr 1 1 n holds, the event in which Lemma C.1 for (nK)=1 holds, and the event which Lemma C.2 holds.
Under event { we have
VV (x.,,.) m m/-1/111r S CgL Vt E [n].
Thus, by (Abbasi-Yadkori Yadkori et al., 2011, Lemma 11), if we choose À 2 max c,L)) we have
det det(Ai)
(fwo-)(Zs..)) m m1/111 A 2llog det(AI)
A
For the second part of Lemma B.5, for any / [n], define
M, m 1/2 [vec( (V V (211,1 (),ia,))...... veo veo (V/wio) (20t, E BRxxr
M, m 1/2 m1/2, [vec( V fw (2
vec( (fw.enn Rext
We have A₂ = AI + M,M and A, = AI M,M,", and det(As)
log (et( log det( Ar)
log del(I 1 M,M, /A) - log del M.M, /N)I
det( AT)
1log det I M M, (A) log det [I M. M.A))
max((1(( + M Mc (1)- M M. M. M. II([ M,A))-1 MM M.
= -IK(I + M, MM/A)-I,M, M. - M. M.I
$ |I(I M." M,/))""lll |M, M. -
VIII(I M M,/A)- IIM M. M, 14-MM M. M.ll
$ V M, - MA MilFF
Vit max m 15tjst
(Vwccn fw (z),a))) - fV (I)a.)) V (2
3/2mm -1 max iSijst
(2..a) V fwio (Ii,a)) (fwe-n
+ (Vf (Ija,)
f (D),a,) Sw (mtaa))
22 -1 max v f V fw (Zi max V
$ 2C202. m 1/6
23/6 1166
where the second equality is by det([I AAT) det(I ATA), A), the first inequality is by that log det concave, the third equality assumed without loss of generality, the second inequality is by that (A, B) < || B|. F. the third inequality is by that ||A]|] S Af|lA for A E Rtxt the fourth inequality is by that M. M,/X /> > I. the fifth inequality is by that ||ll| S ||] for A E xt the sixth incquality is by the triangle inequality, and the last inequality is by Lemma B.3, and Lemma C.2.
21

---

Published as a conference paper at ICLR 2022
The third part of Lemma B.5 directly follows the argument in (?, (B.18)) and uses Lemma C.I for = (nK) -!
Finally, it is easy to verify that the condition of m in Lemma B.5 satisfies the condition of m for (n + 2)), and union bound we have (6 + 2))) 2 2-8
D DETAILS OF BASELINE ALGORITHMS IN SECTION 6
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.
Table 2: A summary of the baseline methods.
Baseline
Algorithm
Type
Function approximation
LinLCB
Algorithm 2
Pessimism
Linear
KernI.BB
Algorithm
Pessimism Pessimism Greedy
RKSH
NeuralLinLCCK
Algorithm 4
Linear w/ fixed neural features
NeuralLinGreedy
Algorithm 5
Linear w/ fixed neural features
NeuralGreedy
Algorithm 6
Greedy
Neural networks
Algorithm 2 LinLCB
Input: Offline data Dn { de, rt) reg, parameter À > confidence parameters 0.
I: An - AI + Σi= 11 ti.0
0 - A 2t=1 Ft.a,
3: L(u) + (On, u) B1|uel A. Vu E Rd
Output: (xx) t arg m R) L(xa)
Algorithm KernLCB
Input: Offline data Dn { ar, re)) reg, parameter kernel k Rd x Rd IR.
0, confidence parameters 3 0.
1: kn (u) +- [kuu, 01.a))...... k(u, on.on ) yu Yu e Rd
2: Kn + [k( FJ Misisnn
3: Yn + [T.
4: L(u)= + (n)")) (K, + A1) yn -n - BB /kku,, (u) + - Vu Rd
Output: ((x)) <- arg m I(xa)
Algorithm 4 NeuralLinLCB
Input: Offline data D, = (( az, (2) ) regularization parameter À 0, confidence parameters
3>0 3>0.. O.
1: Initialize the same neural network with the same initialization scheme as in NeuraLCB to obtain the neural network function fwi, at initialization
2: ouu) + vec( V fwro (u)) IP, Vuu E Rd
3: An < AI + Em ((Bt,,,))((...
4: 0,, + A 2n ((xt,a,)) )r
5: [uu) < (0n, (du)) - (1))( Vu E Rd
Output: (xx) + arg max K] L(xa)
22

---

Published as a conference paper at ICLR 2022
Algorithm 5 NeuralLinGreedy
Input:
Offline data D, {( de, ro)] regularization parameter À > 0. 1: Initialize the same neural network with the same initialization scheme as in NeuraL to obtain the neural network function Swi, at initialization
2: (u)) < vec( (wo E IRP, Vu E Rd
3: On t A Et ((Ft,,,))
4: L(u) (On, ((u)), Yu Rd
Output: (x)) t arg max Rn ((xa)
Algorithm NeuralGreedy
Input: Offline data D, = {(atr, de,, rz) 1=1 step sizes (me (n+)== regularization parameter À >> 0.
I: Initialize ( as follows: set W [W, 0,0, Wi). VT E [L 1] where each entry of Wi
is generated independently from A00, 4/m) m). and set w (0) [w", _w"] where each entry of
w generated independently from (0, 2/ /m).
2: for t = 1, 1,...,, do
3: Retrieve (xt, ar, (t) from Dn.
4: #x(x)) +- arg m Swie- (wa), Va.
5: W (t-11) T/ VL (W((L1))))) where (WW = [f - rz)² + md W
W 1|
6: end for Output: Randomly sample स uniformly from ( #n).
Algorithm 7 NeuraL.CB (B-mode)
Input:
step sizes {no regularization parameter À 0, confidence parameters {Br] batch size B > O, epoch number J > 0.
Offline data D,, {( dt rt))== (t)
Initialize (0)) as follows: w(O) [Wi, 0; Wi]. VI E [L - 1] where each entry of Wi
is generated independently from A/ 4/ 4/m), and set w ww -ww=) where each entry of
w generated independently from A/(, 2 m).
2: Ao AL.
3: for #rt=ll..... do
4:
Retrieve (x,, ae Te) from D,,.
5: L,(u) t fwi-n (u) Bi-1 V fw(e-)(u) m m-1/111/ 1/ Yu E Rd Az
6:
#t(x) +- arg (egmaxe([1] (xx)), for all (z, Rd : E [K]].
7:
A, < A,-I vec VVc(VV/www-/) (z),a))) /ec(V//ween)) (Kr, ))a /m.
8:
W < W((-1)
9:
for j L....,JJ do
10:
Sample a batch of data B₁ = (Eig T2g B 3-1 from Dj rrg)) )2 md w 10
-(2) (W) - Eg 2B (fw (F (atg
11:
W W nI vCC (W/)-1))
12:
13:
end for
14:
- (J)
15: end for
Output: Randomly sample म uniformly from { #n
E DATASETS
We present detailed description about the UCI datasets used in our experiment.
Mushroom data: Each sample represents set of attributes of a mushroom. There are two actions take on each mushroom sample: eat Eating editable mushroom
23

---

Published as a conference paper at ICLR 2022
Table The real-world dataset statistics
Dataset
Mushroom
Statlog
Adult
MNIST
Context dimension
22
9
94
784
Number of classes
2
7
14
10
Number of instances
8,124
43,500
45,222
70,000
generates a reward of +5 while eating a poisonous mushroom yields a reward of +5 with probability 0.5 and a reward of -35 otherwise. No eating gives a reward of 0.
Statlog data: The shuttle dataset contains the data about a space shuttle flight where the goal is to predict the state of the radiator subsystem of the shuttle. There total K states to predict where approximately 80% of the data belongs to one state. A learner receives reward of if it selects the correct state and 0 otherwise.
The Adult dataset contains personal information from the US Census Bureau database. Following (Riquelme et al., 2018), we use the K 14 different occupations as actions and d = 94 covariates as contexts. As in the Statlog data, learner obtains a reward for making the right prediction, and otherwise.
Adult data:
MNIST data: The MNIST data contains images of various handwritten digits from 0 to 9. We use = 10 different digit classes as actions and d = 784 covariates as contexts. As in the Statlog and Adult data, learner obtains reward of 1 for making the right prediction, and 0 otherwise.
We summarizes the statisties of the above datasets in Table 3.
F ADDITIONAL. EXPERIMENTS
In this section, we complement the experimental results in the main paper with additional experi- ments 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 new setup of offline data collection that represents dependent actions. In particular, instead of using a stationary policy to collect offline actions in Section 6, here we used an adaptive policy defined as
((,, = (1 - c) * n (ala:.) + Miintinn (a DD-1, 2:),,
where n² the optimal policy and MLiaUCB is the linear UCB learner (Abbasi- Yadkori al., 201 1). This weighted policy makes the collected offline data aj dependent on D:-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, this dependent data, the baseline methods with linear models (LinLCB, NeuralLinl.CC and NeuralLinGreedt
perform almost as bad as when they learn on the independent data 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, Neu- ralGreedy suffers apparent performance degradation (especially in larger dataset like MNIST) while NeuraL.B maintains a superior performance, suggesting the effectiveness of pessimism in method dealing with offline data and the robustness of our method toward dependent data.
KernI.C CB also does not change its performance much, but its computational complexity is still major issue.
24

---

Published as a conference paper at ICLR 2022
0.9
NeuraLCB
NeuralGreedy
0.8
LinLCB
0.8
Sub-optimallty
0.7
NeuralLinGreedy KernLCB
NeuralLinLCB
Sub-optimalitt
0.7
0.6
0.5
aCBB
0.5
NeuralGreedy
0.4
0.4
NeuraiLinLCB
0.3
NeuralLinGreedy
0.2
KernLCB
0.2
2000
4000
10000 12000 14000
2000
4000
6000
8000 10000 12000 14000
Number of samples
Number of samples
(a) Statlog
(b) MNIST
Figure 3: The sub-optimality of NeuraLCB versus the baseline algorithms on real-world datasets with correlated structures.
F.2 S-MODE VERSUS B- B-MODE TRAINING
As in Section 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 Cosine (synthetic dataset), Statlog, Adult and MNIST are shown in Figure 4.
We make the following observations. which 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 Neural .CB outperforms or at least is compatible to the S-mode of NeuralGreedy in the real-world datasets. First, these observations suggest the superiority of our method the wol-world datasets. Second, to explain the performance difference of S-mode and B-mode on synthetic and real-world datasets in our experiment, we speculate that the online-like nature of our algorithm tends reduce the need of B-mode in practical datasets because B-mode in the streaming data might cause over- fitting (as there could 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 the simple synthetic reward function such as Cosine sufficiently smooth, unlike practical reward functions in the real-world datasets.
DRV muny
AmenddR muto Aeerallree waro
G18
028
10o Nambarr sumplas
Ramberr surgii
(a) Cosine
(b) Statlog
(c) Adult
(d) MNIST
Figure 4: Comparison of S-mode and B B-mode training.
25


Reviews:
[{"review_id": "ZlqidjSTfvx", "reviewer": "Reviewer_Fwh8", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Some references are repeated in the bibgraph. For example, there are multiple entries for the same papers (Is pessimism provably efficient for offline rl, Gradient descent provably optimizes over-parameterized neural networks, Neural contextual bandits with ucb-based exploration). In the related work, there is another recent paper that studies policy learning in contextual bandit using the same neural network structure as in this paper (Xu, P., Wen, Z., Zhao, H., & Gu, Q. (2020). Neural contextual bandits with deep representation and shallow exploration. arXiv preprint arXiv:2012.01780.). Similar to the claim of the current work, this paper also improves the computational complexity of neural contextual bandits to a large extent. \n\nIn Line 4 of Algorithm 1, are you retrieving the data tuple randomly, sample without replacement, or just in a fixed order? The notation of x_t and x^{(i)}\n\nIn the introduction, the authors stated that “actions in the offline data are independent and depend only on the current state” in Rashidinejad et al. (2021). However, it should be also clearly stated that the current paper did not resolve this problem since by Assumption 4.2 we know that the authors in this paper still need the actions to be independent from each other. \n\nUnder Assumption 4.2, the authors claimed that the data coverage condition is only imposed on the observed feature contexts. However, a significant difference in the setting of this paper from others that rely on uniform coverage is that the total number of arm contexts are fixed as nK (shown in Assumption 4.1), while other papers such as Nguyen-Tang et al., (2021) do not require this condition. Is this the crucial reason for the relaxation of the condition?\n\nIn Theorem 1, it is claimed that the network width m is a polynomial in the number of data n. But it is unclear to me what the exact dependence of m on the number of data n is. In addition, did you also validate the dependency in the experiment settings (m=100, T=15000)?\n\n\n=========after the authors' response========         \nI am satisfied with the responses to my questions. I agree that this paper makes good progress in connecting neural contextual bandits and offline settings. I am willing to increase my score for this paper.", "summary_of_the_paper": "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. \n", "summary_of_the_review": "My recommendation is mainly based on the theoretical novelty and the applicability of the theory. ", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "E8kNTP_siXl", "reviewer": "Reviewer_RvBs", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Pros:\n\na) The paper provides concrete theoretical analysis to support the proposed algorithm. I have not gone through all the derivations, but the overall result looks good.\n\nb) Comprehensive comparisons with other related works are properly presented.\n\nc) The paper is generally well written. The required assumptions are discussed clearly.\n\nCons:\n\na) Apart from theoretical analysis, it would be better if the paper could throw some light on algorithm design consideration beyond LCB-like algorithm.\n\nb) It is not very clear how the improvement of \\sqrt{d} and O(n) is achieved. It would be better to give more concrete discussions.\n", "summary_of_the_paper": "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.", "summary_of_the_review": "Overall the paper studies a new problem and presents a good analysis. Since the technique is quite similar to existing works, it would be much better to present necessary discussions to claim their contributions.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "AuqCGnerAA", "reviewer": "Reviewer_5NdR", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength\n\n- Comparing with existing works, NeuraLCB requires weaker assumptions on data coverage (empirical single-policy concentration condition) and data generation (data can be dependent on history / past data) and I think this is a major contribution of the paper. The weaker assumption makes the algorithm applicable to more practical settings.\n\n- Theoretical analysis on sub-optimality learned by NeuraLCB is provided. The algorithm essentially works in an online fashion that trained on one data point at each iteration. Thus several intermediate results can be directly applied from or very similar to online regret minimization in neural bandits (e.g., NeuralUCB, Zhou et al., 2019). If my understanding is correct, due to the different goal between online and offline policy learning (instead of improved technical lemmas over Zhou et al., 2019), the design of NeuraLCB is very different from NeuralUCB, e.g., single data point SGD verse full gradient descent at every iteration.\n\nI checked the main theorem and several lemmas; they look sound and I only found a few mistakes (see below).\n\nWeakness\n\n- Mistakes in proof of Lemma B.5:\n  - $\\log \\det$ function is concave instead of convex.\n  - When bounding the difference of the $\\log \\det$ functions, the first inequality does not hold. Because log det function is concave, by taylor expansion we have that $\\log \\det(X) - \\log \\det(Y) \\leq <Y^{-1}, X-Y>_F$. But the inequality does not hold when taking the absolute value of both sides, which is the case in current proof. This problem should be fixable and Lemma B.5 should still hold.\n\n- In experiments the authors mentioned a B-mode variant of NeuraLCB (and NeuralGreedy) that update with a small batch of data points at each iteration. The result is reported after grid search over B-mode and S-mode (one step SGD on single data point). I would suggest the authors to report the performance of S-mode and B-mode separately. In experiment on the real-world datasets, the authors observed that S-mode performed better than B-mode (again, both results should be plotted). That's an interesting observation. It would be helpful to provide some explanations over this observation.\n\nOther comments\n\n- Besides the theoretical convenience of learning in an online manner, are there any other reasons to prevent full gradient descent training? It sounds very natural for offline learning. \n\n- The authors mentioned after Assumption 4.2 that NeuraLCB works with depend data: 'the offline data was collected by an active learner such as a Q-learning agent'. Currently the synthetic experiment is on independent data. It would be interesting to see if NeuraLCB could work well with depend data, e.g., use some bandit algorithms to collect the dataset. \n\n\n", "summary_of_the_paper": "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.", "summary_of_the_review": "Overall I think this is a good paper with a straightforward idea of combining pessimism and neural bandits for offline policy learning. I am open to revise my rating if the authors could address the concerns.", "strength_and_weaknesses": "", "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": "7EgzdVra1d", "reviewer": "Reviewer_HWn2", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Pros: \n\n1. The pessimism principle (Kidambi et al., 2020; Buckman et al., 2020; Jin et al., 2020) is a recent idea introduced in off-policy learning to avoid the strong assumption of sufficient coverage of the data. The key idea is to consider a regularization version, i.e. lower confidence bound (LCB). After its introduction, it has been applied in various off-policy RL and off-policy bandit settings. This paper further advances this area by introducing this idea into the neural contextual bandit setting. \n\n\n2. This paper is very well written and is easy to follow.\n\n\nCons: \n\n1. Related to my previous comments on the pessimism principle, the main contribution of this paper is to incorporate the pessimism principle neural contextual bandit setting. It combines the strength of both Rashidinejad et al. (2021) and Zhou et al. (2020), where the former studies the lower confidence bound (pessimism principle) for decision-making in tabular MDP and contextual bandit, and the latter studies neural contextual bandit with upper confidence bound in typical online setting. Therefore, the technical advantages over these existing work are expected and routine. \n\n2. In Algorithm 1, why to randomly sample policy uniformly from $\\hat{\\pi}_1, \\ldots, \\hat{\\pi}_n$? \n\n3. In Theorem 4.1, the error bound $O(\\kappa \\tilde{d}^{1/2} n^{-1/2})$, $\\kappa$ measures the distributional shift and $\\tilde{d}$ is an effective dimension of the neural network. \n\n(1) The Assumption 4.2 requires $\\kappa$ to be a uniform upper bound over all sample size $n$ and all samples $x_t$. $\\kappa$ would be a function of the dimension and the sample size. In this case, the error bound might diverge. It would be more convincing if the authors could provide some justifications or examples when $\\kappa$ would be small.\n\n(2) Similarly, the effective dimension of the neural network $\\tilde{d}$ might be very large. This effective dimension of the neural network was used for online neural contextual bandit (Zhou et al., 2019) and neural MDP (Yang et al., 2020). The authors commented that $\\tilde{d}$ in these references were typically small, in the order of $log(n)$. However, it is unknown whether  $\\tilde{d}$ in the proposed off-policy neural contextual bandit is still small. In order to ensure this, one would inevitably assume conditions on the data generation process to control the decaying speed of eigenvalues of the gram matrix $H$. It would be more convincing if the authors could provide detailed quantification of data generation process. \n", "summary_of_the_paper": "~~~~~~~~~~~~~~\nThank the authors for the clarification. Some of my former comments were nicely addressed and hence I am willing to increase my rating to 6.\n\n~~~~~~~~~~~~~~\nThis 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.\n\n", "summary_of_the_review": "The technical contribution of this paper is OK but not strong. The assumptions and theory of the paper need substantial clarifications. ", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies off-policy learning of contextual bandits with neural network generalization. The proposed algorithm NeuraLCB acts based on pessimistic estimates of the rewards obtained through lower confidence bounds. NeuraLCB is both analyzed and empirically evaluated.

This paper received four borderline reviews, which improved during the rebuttal phase. The main strengths of this paper are that it is well executed and that the result is timely, considering the recent advances in pessimism for offline RL. The weakness is that the result is not very technically novel, essentially a direct combination of pessimism with neural networks. This paper was discussed and all reviewers agreed that the strengths of this paper outweigh its weaknesses. I agree and recommended this paper to be accepted.
Decision: Accept (Poster)