Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
Authors: Kefan Dong
Jiaqi Yang
Tengyu Ma
Venue: NeurIPS 2021 Poster (2021)
Keywords: bandit theory
online learning
reinforcement learning theory
deep reinforcement learning theory
sequential Rademacher complexity

Abstract: This paper studies model-based bandit and reinforcement learning (RL) with nonlinear function approximations. We propose to study convergence to approximate local maxima because we show that global convergence is statistically intractable even for one-layer neural net bandit with a deterministic reward. For both nonlinear bandit and RL, the paper presents a model-based algorithm, Virtual Ascent with Online Model Learner (ViOlin), which provably converges to a local maximum with sample complexity that only depends on the sequential Rademacher complexity of the model class. Our results imply novel global or local regret bounds on several concrete settings such as linear bandit with finite or sparse model class, and two-layer neural net bandit. A key algorithmic insight is that optimism may lead to over-exploration even for two-layer neural net model class. On the other hand, for convergence to local maxima, it suffices to maximize the virtual return if the model can also reasonably predict the gradient and Hessian of the real return.

Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
Kefan Dong Stanford University kef andong@stanf oord edu
Jiaqi Yang Tsinghua University yangjq176gmail.com com
Tengyu Ma Stanford University tengymma@stanford edu
Abstract
This paper studies model-based bandit and reinforcement learning (RL) with non- linear function approximations. We propose study convergence approximate local maxima because we show that global convergence is statistically intractable even for one-layer neural net bandit with deterministic reward. For both non- linear bandit and RL, the paper presents a mosel-based algorithm, Virtual Ascent with Online Model Learner (ViOlin), which provably converges to local max- imum with sample complexity that only depends on the sequential Rademacher complexity the model class. Our results imply novel sample complexity bounds several concrete settings such as linear bandit with finite or sparse model class, and two-layer neural net bandit. A key algorithmic insight that optimism may lead to over-exploration even for two-layer neural net model class. On the other hand, for convergence to local maxima, it suffices to maximize the virtual return if the model can also reasonably predict the gradient and Hessian of the real return.
Introduction
Recent progresses demonstrate many successful applications of deep reinforcement learning (RL) in robotics [49], games [7, 66), computational biology [56], etc. However, theoretical understanding of deep RL algorithms is limited. Last few years witnessed plethora of results linear function approximations in RL [80. 65, 40, 73, 71, 19, 3. 32], but the analysis techniques appear to strongly rely on (approximate) linearity and hard to generalize neural networks.
The goal of this paper is to theoretically analyze model-based nonlinear bandit and RL with neural approximation, which achieves amazing sample-efficiency in practice (see e.g., [37, 10, 30, 31, 12]). We focus on the setting where the state and action spaces are continuous.
Past theoretical work model-based RL studies families of dynamics with restricted complexity measures such as Eluder dimension [60], witness rank [68], the linear dimensionality [77], and others [58, 42, 17). Implications of these complexity measures have been studied, e.g., finite mixture of dynamics [6] and linear models [64] have bounded Eluder dimensions. However, it turns out that none of the complexity measures upply the family of MDPs with even barely nonlinear dynamics, e.g., MDPs with dynamics parameterized by all one-layer neural network with a single activation unit (and with bounded weight norms). For example, in Theorem 5.2, will prove that one-layer neural nets do not have allynomially-boundde Eluder dimension. (See more evidence below.)
The limited progress on neural net approximation is to some extent not surprising. Given determin- istic dynamics with known neural net parameters, finding the best parameterized policy still involves optimizing a complex non-concave function, which is in general computationally intractable. More
This result also proved by the concurrent Li et al. [50. Theorem 8] independently.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

fundamentally, we find that it is also statistically intractable for solving the one-hidden-layee neural net bandit problem (which is a strict sub-case of deep RL). In other words, it requires exponential (in the input dimension) samples to find the global maximum (see Theorems 5.1). This also shows that conditions past work that guarantee global convergence cannot apply to neural nets.
Given these strong impossibility results, we propose to reformulate the problem to finding an ap- proximate local maximum policy with guarantees. This is in the same vein as the recent fruitful paradigm in non-convex optimization where researchers disentangle the problem into showing that all local minima are good and fast convergence to local minima (e.g.. see [28, 26, 27, 29, 48)). In RL, local maxima can often be global as well for many cases [4].
Zero-order optimization or policy gradient algorithms natural potential competitors. They are widely believed to be less sample-efficient than the model- based approach because the latter can leverage the extrapolation power of the parameterized models. Theoretically, our formulation aims to characterize this phenomenon with results showing that the model-based approach's is sample complexity mostly depends (polynomially) on the complexity of the model class, whereas policy gradient algorithmss sample complexity polynomially depend on the dimensionality of policy parameters (in RL) or actions (in bandit). Our technical goal is to answer the following question:
converge local maxima and become
Can we design algorithms that converge to approximate local maxima with sample complexities that depend only and polynomially the complexity measure of the dynamics/reward class?
We note that this question is open even if the dynamics hypothesis class is finite, and the complexity measure is the logarithm of its size. The question is also open even for nonlinear bandit problems (where dynamics class is replaced by reward function class), with which we start our research.
We consider first nonlinear bandit with deterministic reward where the reward function is given by n0, a) for action E A under instance 0 E O. We use sequential Rademacher complexity [62, 63] to capture the complexity of the reward function r7. Our main result for nonlinear bandit is stated as follows.
Theorem 1.1 (Informal version of Theorem 3.1). Suppose the sequential Rademacher complexity of a loss function class (defined later) induced by the reward function class (n(0,.) : E θ} is bounded by / ([o))pooyyog((T) Then, there exists an algorithm (ViOlin, Alg. 1) that finds an e-approximate local maximum with Ö(R(O)e- samples.
In contrast to zero-order optimization, which does not use the parameterization of and has a sample complexity depending on the action dimension, our bound only depends on the complexity of the reward function class. This suggests that our algorithm exploits the extrapolation power of the reward function class. To the best of our knowledge, this the first action-dimennionnfiee result for both linear and nonlinear bandit problems. More concretely, we instantiate our theorem to the following settings and get new results that leverage the model complexity (more in Section 3.1).
1. Linear bandit with finite parameter space O. Because 1j concave in action a, our result leads to a sample complexity Opoly 6), 1/e)) for finding an e-approximate optimal action. In this case both zero-order optimization and the SquareCB algorithm in Foster, Rakhlin [24] have sample complexity/regret that depend on the dimension of action space d
2. Linear bandit with s-sparse or structured instance parameters. Our algorithm ViOlin achieves an O(poly (s, 1/e)) sample complexity when the instance/model parameter is s-sparse and the reward is deterministic. The sample complexity of zero-order optimization depends polynomi- ally on d' Carpentier, Munos [9] achieve a stronger Ö(sVT) regret bound for s-sparse linear bandits with actions set A 5dd-1, In contrast, our ViOlin algorithm applies more generally to any structured instance parameter set. Other related results either leverage the rather strong cnti-concettattoon assumption on the action set [72], or have implicit dimension dependency [33, Remark 4.3].
3. Two-layer neural nets bandit. Our algorithm finds an e-approximate local maximum O(poly(L/e)). Zero-order optimization can also find local maximum but with l(dxx) samples.
'The loocallmaxima-aee are global condition only needs to hold to the ground truth total expected reward function. This potentially can allow disentangled assumptions on the ground truth instance and the hypothesis class.
2

---

Optimistic algorithms in this case have an exponential sample complexity (see Theorem 5.3). Moreover, when the second layer of the ground truth network contains all negative weights and the activation is convex and monotone, all local maxima are global because the reward is concave in the input (action) [5].
The results for bandit can be extended model-based RL with deterministic nonlinear dynamics and deterministic reward.
Theorem 1.2 (Informal version of Theorem 4.4). Consider RL problems with deterministic dy- namics class and stochastic policy class that satisfy some Lipschitz properties. Suppose the sequential Rademacher complexity of the lz losses for learning the dynamics is bounded by /R(O)) polyloogT) Then, ViOlin for RL (Alg. 2) finds e-approximate local maximum policy with ((H(O)E $) samples.
To the best of our knowledge, this is the first model-based RL algorithms with provable finite sample complexity guarantees (for local convergence) for general nonlinear dynamics. The work of [55] is the closest prior work which also shows local convergence, but its conditions likely cannot be satisfied by any parameterized models (including linear models). We also present concrete example of RL problems with nonlinear models satisfying our Lipschitz assumptions in Example 4.3 of Section 4, which may also serve testbed for future model-based deep RL analysis. Other prior works on model-based RL do not apply to one- cee-hiddee-llaye llyer neural nets because they conclude global convergence which is not possible for meehidden-laae layer neural nets in the worst case.
Technical novelty: exploring by model-based curvature estimate. The main challenge is that the wwwpiss-----na-o-----eeeeeee
exploration principle seems to be too aggressive for non- linear model class, even if the ground-truth model is linear, optimistic exploration leads to expo- nentially large model cumulative prediction errors and exponential sample complexity (see Theo- rem 5.3). We use an online learning oracle to learn the dynamics, which can dramatically reduce the model prediction errors by hedging the risks. However, now, choosing actions or policies by maximizing virtual return may lack exploration. The main novelty of our algorithm is that we aug- ment the online learning loss with gradient and Hessian estimation errors. The key insight is that, in order to ensure sufficient exploration for converging to local maxima, it suffices for the model to predict the virtual return, its gradient and Hessian reasonably accurately. We refer to the approach as "model-based curvature estimate". Our algorithm alternates between maximizing virtual return (over action or policy) and learning the model parameters by an online learner.
Because the algorithm leverages model extrapolation, the sample complexity of model-based cur- vature prediction depends on the model complexity instead of action dimension the zero- optimization approach. Foster, Rakhlin [24] also propose algorithms that do not rely on UCB- their exploration strategy either relies on the finite discrete action space, or leverages the linear structure in the action space and has action-dimentn exploration relies more on the learning of the model. Consequently, our sample complexity can be
dependency. In contrast, our algorithms'
2 Problem Setup and Preliminaries
In this section, we first introduce our problem setup for nonlinear bandit and reinforcement learning, and then the preliminary for online learning and sequential Rademacher complexity.
2.1 Nonlinear Bandit Problem with Deterministic Reward
We consider deterministic nonlinear bandits with continuous actions. Let 0 E θ be the parameter that specifies the bandit instance, Ed the action, and 17(8, a) E [0, 1] the reward function. Let Ø* denote the unknown ground -ruth parameter. Throughout the paper, we work under the realizabiliry assumption that 6* e. A bandit algorithm aims maximize y q). Let a* argmax, n a) be the optimal action (breaking tie arbitrarily). Let || || be the spectral norm of matrix H. We assume that the reward function, its gradient and Hessian matrix are Lipschitz, which are standard in the optimization literature (e.g.. Johnson, Zhang [41], Ge al. [26]).
3

---

Assumption 2.1. We assume that for all o E O, sup, |an(t. S Eo and sup, Van(0, a)]les S Sh. For every 0 E θ and 01,02 Rda, [an(0, a1) Van(0, a2) s
Sard ||0 - 1021-2
As motivation to consider deterministic rewards, we prove in Theorem B.1 for special case that no algorithm can find local maximum in less than v A steps. The result implies that an action- dimension- free sample complexity bound is impossible with standard sub- Sab-Gaussian noise." 3
Approximate local maxima. In this paper, we aim find local maximum of the real reward function 1700". -). A point I is an (Eg. aap-pproxxim local maximum of a twice-differentiable function f(x) if fx))ll I Eg. and Amaz ( fz)) S ch. As argued Sec. and proved in Sec. 5, because reaching global maximum is computational and statistically intractable for nonlinear problems, we only aim to reach local maximum.
Sample complexity and local regret for converging to local maxima. Let a be the action that the algorithm takes at time step t. The sample complexity for converging to approximate local maxima is defined to be the minimal number of steps T such that there exists t [T] where aę is an (eg, 6.) approximate local maximum with probability at least 1 1-d 6. We also define the "local regret" by comparing with an approximate local maximum. We defer the discussion to Appendix C.5.
2.2 Reinforcement Learning
A finite horizon Markov decision process (MDP) with deterministic dynamics is defined by a tuple (T,r, H. p1). Let S and A be the state and action spaces. The dynamics T' S x A + S gives next state, r S x A - [0, 1] is the reward function. H and μl denote the horizon and distribution of initial state respectively. Without loss of generality, we assume that the state space is disjoint for different time steps. That is, there exists disjoint sets ,H such that = U S any 8h E a. E a, T(s,, an) E Sa+1-
Sp. and for
We consider parameterized policy and dynamics. Let IT {TT th v be the policy class and (To 0 E }} the dynamics class. The value function is V7 (sh) E|E r(sw, ax²) ]. where T(s,, an). Sharing the notation with the bandit setting, let 17(8, v/) Esy=ai Ve (s1) be the expected return of policy Te under dynamics Tg. Let pij be the distribution of state action pairs when running policy æ in dynamics T. For simplicity, we do not distinguish bb, 8 from Tv, Te when the context is clear. For example, we write Vi = =VA.
an x(- sh,,, Sh++1
2.3 Preliminary on Online Learning with Stochastic Input Components
Consider prediction problem where we aim to leam function that maps from X' to y parame- terized by parameters in O. Let {((x, y): f) be a loss function that maps (X' x )) x e - R,. An online learner R aims to solve the prediction tasks under the presence of an adversarial nature iteratively. At time step i, the following happens.
The learner computes a distribution p. = R(((2, )=) over the parameter space e. The adversary selects a point ā. E (which may depend on pt) and generates sample & from some fixed distribution q. Let v, A (æ., &.). and the adversary picks a label yı: V.
3. The data point (Iz; ys) is revealed to the online learner.
The online learner aims to minimize the expected regret in rounds of interactions, defined as
REGOL
OL
E Deng.
ΣS (((x):))) infoce Σi ((<x,,8)):0)
VISIST
The difference of the formulation from the most standard online learning setup is that the & part of the input is randomized instead of adversarially chosen (and the learner knows the distribution of & before making the prediction p.). It was introduced by Rakhlin et al. [61], who considered more generalized setting where the distribution q in round t can depend on ".. 1.-1).
We rely on deterministic reward to estimate the gradient by finite difference. This method can be extended stochastic rewards with multiple-poin -oint feedback [54].

---

We adopt the notation from Rakhlin et al. [61, 62] to define the (distribution-depeddeen) sequential
Rademacher complexity of the loss function class L = {xx,y) + (); : E } For any set 2, a Z-valued tree with length 7' is set of functions {2, {+1]--1 + _) For sequence of Rademacher random variables e = (c1,-.., and for every S S T, we denote
ze(e) - 2₁ (EI. Et-1). 1). For any X-valued tree æ and any V-valued tree y, we define the sequential
Rademacher complexity as
(r y) A E Be sup LEE
Ei= (l(((((()))) v(())
(2)
We also define RC - sup,, Ar C; x. y), where the supremum taken over all X'vuuueed and V'-valued trees. Rakhlin et al. [6]] proved the existence of an algorithm whose online learning regret satisfies REG v (C).
3 Model-based Algorithms for Nonlinear Bandit
We first study model-based algorithms for nonlinear continuous bandits problem, which is a simpli- fication of model-basee reinforcement learning. We use the notations and setup in Section 2.1.
Abstraction of analysis for model-based algorithms. Typically, model-based algorithm ex- plicitly maintains an estimated model l, and sometimes maintains a distribution, posterior, or confi- dence region of d.. We will call 17(6", a) the real reward of action a, and r7(O), a) the virtual reward. Most analysis for model-based algorithms (including UCB and ours) can be abstracted as showing the following two properties:
(i the virtual reward n/0,,, a+) sufficiently high.
(ii) the virtual reward 17(0,, at) is close to the real reward ry(" a²) in the long run.
One can expect that a proper combination of property (i) and (ii) leads to showing the real reward n(0", a,) is high in the long run. Before describing our algorithms, we start by inspecting and summarizing the pros and cons of UCB from this viewpoint.
Pros and cons of UCB. The UCB algorithm chooses an action a and an estimated model 6g that maximize the virtual reward 1)(0,, az) among those models agreeing with the observed data. The pro is that it satisfies property (i) by definition-nn(A. a.) is higher than the optimal real reward n(0",a*). The downside is that ensuring (ii) is challenging and often requires strong complexity measure bound such Eluder dimension (which is not polynomial for even barely nonlinear models, as shown in Theorem 5.2). The difficulty largely stems from our very limited control of Ó, except its consistency with the observed data. To bound the difference between the real and virtual rewards, we essentially require that any model that agrees with the past history should extrapolate to any future data accurately (as quantitatively formulated in Eluder dimension). Moreover, the difficulty of satisfying property (ii) fundamentally caused by the over-exploration of UCB- -As shown in the Theorem 5.3, UCB suffers from bad sample complexity with barely nonlinear family of models.
Our key idea: natural exploration via model-based curvature estimate. We deviate from UCB by readjusting the priority of the two desiderata. We prioritize ensuring property (ii) on large model class. We leverage strong online learning algorithm to predict O, with the objective that n(O,, a;) matches n1(0",,)) As a result, the difference between the virtual and real reward depends on the online learnability or the sequential Rademacher complexity of the model class. Sequen- tial Rademacher complexity turns out to be fundamentally more relaxed complexity measure than Eluder dimension e.g., two-layer neural networks' sequential Rademacher complexity is polyno- mial in parameter norm and dimension, but the Eluder dimension is at least exponential in dimension (even with a constant parameter norm). However, an immediate consequence of using online-learned 0, is that we lose optimism/explorraion that ensured property (i).* 4
'More concretely, the algorithm can get stuck when (1) is optimal for ô.. (2) ò, fits actions (and history) accurately, but (3) 9, does not fit a' (because online learner never sees a²). The passivity of online learning formulation causes this issue the online learner is only required to predict well for the point that it saw and will see, but not for those points that it never observes.
5

---

Our approach realizes property (i) in sense that the virtual reward will improve iteratively if the real reward is not yet near a local maximum. This is much weaker than what UCB offers (i.e., that the virtual reward is higher than the optimal real reward), but suffices to show the convergence to local maximum of the real reward function. We achieve this by demanding the estimated model 0, not only to predict the real reward accurately. but also to predict the gradient V Van((", a) and Hessian other words, we augment the loss functionn for the online learner so that the estimated model satisfies 17( aq) =e n)(0",,, at), Van(O,, ay) = V V oz). and (2ny(ee, a²) s Van(t*, .a) in the long run. This implies that when a is not local maximum of the real reward Algorithm ViOlin: Virtual Ascent with Online Model Learner (for Bandit)
1: Set parameter 61 = 2g and R2 6400/2cn. Let Ho = 0 choose ag E arbitrarily.
2: for = 1,2, ... ...d... do
3: Run online learner R on H4-1 with loss function & (defined in equation (5)) and obtain
Pr R(H,--)).
4:
Let 0r + argmax, Eg [n,,,,[((0;;.
5:
Sample We, 12 (0, Iaaxxxx independently.
6:
Let & = (2: v2), Ht = (at, a,-1), and 2, = (t)
7:
Compute Y1
im(0", at), n(0", a1-1), (Van((",a)) un), (Van(0" (1-1)) Ut)1 E R=
by applying a finite number of actions in the real environments using equation (3) and (4).
8:
Update H, = H4-1 U { 31))
Van(0", a) accurately.
function 17(0") +), then it's not at a maximum of the virtual reward n7(0,.)) and hence the virtual reward will improve in the next round if we take the greedy action that maximizes it.
Estimating projections of gradients and Hessians. To guide the online learner to predict Van(0*, .x)) correctly, need a supervision for it. However, we only observe the reward n) a.). Leveraging the deterministic reward property, we use rewards at a and a + aju to estimate the projection of the gradient at random direction
(Vnn(0 ,a,, u) = lim (1)(0", a + a '7(00, .a) for
(3)
It turns out that the number of random projections (Van(0", a), u) needed for ensuring a large virtual gradient does not depend on the dimension, because we only use these projections estimate the norm of the gradient but not necessarily the exact direction of the gradient (which may require samples.) Similarly, we can also estimate the projection of Hessian to two random directions u, E d by:
(22n(0",a),,, = lim ((V (Van(0",ec a a2y), u) - -(Van(0", ()) /02 a2-3
(4)
lim lim (1n(0*, + a a2u) n70 a az")) (n7(0, a + aqu) n100, a))) (a)
ag a1
Alg Algorithmically, we can choose infinitesimal on and o2 Note that an should be at least an order smaller than 02 because the limitations are taken sequentially.
We create the following prediction task for an online learner: Ict be the parameter, x = (a, a', u, v) be the input, y = [n((", a), (80 a'), (Van(0" d'), u), (V2100 a') j'),, e)] E R4 be the supervision, and the loss function be
(n, a), (0, a"), (Van(0, a'), u), (Van(0, (0, a' a')u, o)] e R* be the output, and
e(((a, a', u, v): - ([}] - (v])) + +[0]2 - l112] + min [x], (Viss - [vla)
+ min ( ([i)4 [m]4)²)
(5)
Here used [y]: to denote the i-th coordinate of TRd to avoid confusing with ye (the supervision at time f.) Our algorithm is formally stated in Alg. 1 with its sample complexity bound below.
Theorem 3.1. Suppose the sequential Rademacher complexity of the loss function (defined in Eq. (5)) is bounded by / polyoooo))) The sample complexity of Alg. (for finding an (e, 6. (aV//aaae)aaaa apprrxxiait local maximum) is bounded by Ö(C R(O) max ( -9)

---

We present a proof sketch in Appendix C.I. Proof of Theorem 3.1 is deferred to Appendix C.4. We can also boost the success probability by running Alg. multiple times. In addition, we can prove that our algorithm enjoys sublinear local regret. The theorem statement and proof is shown in Appendix C.5 and Appendix C.6 respectively.
3.1 Instantiations of Theorem 3.1
In the sequel we sketch some instantiations of our main theorem, whose proofs are deferred to Appendix C.7.
Linear bandit with finite model class. Consider a linear bandit problem with action set A= = fa e Rd ||a|/25 }} and finite model class C (0 E R2 ||0||== 1}. Let () a) (0, a) be the reward. We deal with the constrained action set by using a surrogate loss r7(0, a) & (0, a) - [aal and apply Theorem C.3 with reward rj. We claim that the sample complexity (of finding an e-suboptimal action
for n)(0", a)) is bounded by (logg 8)5 Note that the bound independent of the dimension d. By contrast, the SquareCB algorithm [24] depends polynomially on (see Theorem 7 of [24]). Zero-order optimization approach [20] in this case also gives poly (c) regret bound.
Linear bandit with sparse structured model vectors. We consider the deterministic linear bandit setting where the model class = {0 E R |01los s, 0/100[=== 1} consists of all s-sparse vectors on the unit sphere. Similarly to finite hypothesis case, we claim that the sample complexity of Alg. 1 is O(log - poly The sample complexity of algorithm only depends on the sparsity level s (up to logarithmic factors), whereas the Eluder dimension of sparse linear hypothesis still ((d) (see Lemma C.4). Lattimore, Szepesvári [46] show l(d)) sample complexity lower bound for the sparse linear bandit problem with stochastic reward. But here we only consider a deterministic reward and continuous action.
Moreover, we can further extend the result to other linear bandit settings where 0 has an additional structure. Suppose @ {0 <(2)
R²} for some Lipschitz funetion &. Then, simlar approach gives sample complexity bound that only depends on s but not d (up to logarithmic factors).
Our results can also be extended to non-linear bandits such deterministic logistic bandits.
Two-layer neural nets.
We consider the reward function given by two-layer neural networks with width For matrices W1 E R and W₂ E IR 1xm. let n7(W,, W2),
a) = W2o(WWa for some nonlinear link function o R + [0, 1] with bounded derivatives up to the third order. Re- call that the (1, -noomm of WTT is defined by max;e [m] E [W]]s That is, the max 1-norm of the rows W1. Let the model hypothesis space be e = ((W1, W2) : ||WTT 1l.. S 1, 1|22l S 13 local maximum in
lall
and 0 A (W1, W2). We claim that Alg .I finds an (c. (ardaaa)appppoooa D(c-"polylog) dd) steps. To the best of our knowledge, this is the first result analyzing nonlin- bandit with neural network parameterization. The result follows from analyzing the sequential Rademacher complexity for y7. (V.7, u). and (u, V2n (....)). and finally the resulting loss function f. See Theorem C.6 in Section C.7 for details. We remark here that zero-order optimization in this case has a poly(d) sample complexity. In addition, if the second layer of the neural network W2 contains all negative entries, and the activation function is monotone and convex, then r/(,,, W2), a) is concave in the action. (This is a special case of input convex neural networks [5].) In this case, Alg. finds an e-suboptimal action (see Theorem C.6).
4 Model-based Reinforcement Learning
In this section, we extend the results in Section 3 to model-based reinforcement learning with deter- ministic dynamics and reward function.
We can always view model-based reinforcement learning problem with parameterized dynamics and policy as a nonlinear bandit problem in the following way. The policy parameter vp corresponds to the action a in bandit, and the dynamics parameter 9 corresponds to the model parameter 0 in
Recall that in bandit literature, action is an e-approximate optimal action if ry(0", a0) 2 n10 ,a")
7

---

bandit. The expected total return n70, 2b) = Ba ( is the analogue of reward function in bandit. We intend to make the same regularity assumptions on 1j as the bandit case (that is, Assumption 2.1) with a being replaced by sh. However, when the policy is deterministic, the reward function yj has Lipschitz constant with respect to io that exponential in H (even if dynamies and policy are both deterministic with good Lipschitzness). This prohibits efficient optimization over policy parameters. Therefore we focus on stochastic policies in this section, for which we expect and its derivatives to be Lipschitz with respect to v.
Blindly treating RL as a bandit only utilizes the reward but not the state observations. In fact, one major reason why based methods are more sample efficient is that it supervises the learning of dynamics by state observations. To reason about the learning about local steps and the dynamics, we make the following additional Lipschitzness of value functions w.r. to the states and Lipschitz- ness of policies w.r.t to its parameters, beyond those assumptions for the total reward 17(0, v) in Assumption 2.1.
Assumption 4.1. We assume the following (analogous to Assumption 2.1) on the value function: Vyb E L f E O, s, E S we have Vo (s) VV" & Lolls - 8'112: V (s) V. (s')
Lills s' l2: IIV V (s) Vi (s L2Ils s'112-
Assumption 4.2. We assume the following Lipschitzness assumptions on the stochastic poli-
cies parameterization Tg. (Baatoo(-ss)( o (V) v log Tola | s)) Illap Xgi
[ log Ta 8))) Xfi [|Bavaa(ee)( ( (V) & log T 8)) IIlapp Xh-
Our results depends polynomially on the parameters Lo, L1, L2, Xa. Xs and XA- To demonstrate that the Assumption 4.1 and 4.2 contain interesting RL problems with nonlinear models and stochastic policies, we give the following example where these parameters are all on the order of (1).
Example 4.3. Let state space be the unit ball in Rdd and action spuce A be RRd, The (determin- istic) dynamics T is given by T(s, a) Ne (s + a), where N is nonlinear model parameterized by 8, e.g., a neural network. We assume that belongs to a finite hypothesis class @ that satisfies |[No(s + a)ll S 1 for all I θ, E S.a E A. Assume that the reward function r(s, a) is L,- Lipschitz w.el fz-norm, that is, satisfying [r(s1, a1) - r(82, a2)l S [, #2112 + ||a a2ll2)- We consider a family of stochastic Gaussian policies with the mean being linear in the state: (s) = N(bss, o²T), parameterized by 3/ E Rdxdd with [|'lop S 1. We consider a E (0,1) as a small constant on the order of 1.
In this setting, Assumption 2.1. 4.1, and 4.2 hold with all parameters Sg. Sto Szed, Lo, L1, L2, Xg. XI and Xh bounded by poly(a, 1/a, H, T..).
Bounding the Lipschitz parameters is highly nontrivial and deferred to Appendix E.
We show that the difference of gradient and Hessian of the total reward can be upper-bounded by the difference of dynamics. Let = ($1, a1. SH. az)) be a trajectory sampled from policy Tt. under the real dynamics Tg.. Similarly [79], when the value function is Lipschitz, we upper bound A,, = (n, 2 n)(",, e by the one-step model prediction errors. Similarly, we can upper bound the gradient and Hessian errors by model prediction errors. As result, the loss function
simply can be set to
(((TE, 0)):0)
Σ (BE
[T((n, - To- (SE, an 01)111++
Σ (5)
(Ta( - To- wh2l (6)
for two trajectories T sampled from policy Tah and Tw-- respectively. Compared to Alg. 1, the loss function is here simpler without relying on finite difference techniques to query gradients projections. Our algorithm for RL is analogous to Alg. 1 by using the loss function in Eq. (6). Our algorithm is presented in Alg. in Appendix D. Main theorem for Alg. is shown below.
Theorem 4.4. Let 01
L Xt. + AH*x, + 2H²x,, X, + 1) + HLH + 2) + 4HL3 Suppose the sequential Rademacher complexity of the loss function (defined and C = 2 + "
Sa.
'Recall that the injective norm of a k-th order tensor A E RdSA is defined as ||
supresd-1 (A, OA).
8

---

in Eq. (6)) is bounded by / polyoooo)y The sample complexity of Alg. 2 (for finding an (e, (3ddt -apro))-appoxxmaaee local maximum) is bounded by ((GC max ( <and "))
Instantiation of Theorem 4.4 on Example 4.3.
Applying Theorem 4.4 to the Example 4.3 with (1) we get the sample complexity upper bound (poly(a, 1/a, H, L,) log|@]e (
Comparison with policy gradient. To the best of our knowledge, the best analysis for policy gradient [74] shows convergence to a local maximum with a sample complexity that depends poly- nomially on v/V log (a 8)](2 [4]. For the instance in in Example 4.3, this translates to sample complexity guarantee on the order of vd/a. In contrast, our sample complexity is independent of the dimension d. Instead, our bound depends the complexity of the model family Q which could be much smaller than the ambient dimension this demonstrates that we leverage the model extrapolation.
Lower Bounds
We prove several lower bounds to show (a) the hardness of finding global maxima, and (b) the inefficiency of using optimism in nonlinear bandit.
Hardness of Global Optimality. In the following theorem, we show it statistically intractable to find the global optimal policy when the function class is chosen to be the neural networks with ReLU activation. That is, the reward function can be written in the form of ( b), a) = ReLU((w, a} + b). Note that the reward function can also be made smooth by replacing the activation by smoothed version. For example, r7(w, b), a) = ReLU((w, a) + b)2.
Theorem 5.1. When the function class is chosen to be one-layer neural networks with ReLU acti- vation, the minimax sample complexity 92(e (((=-(d2)).
We can also prove that the eluder dimension of the constructed reward function class is exponential.
Theorem 5.2. The s-eluder dimension of one-layer neural networks at least (d=-1d)..
This result is concurrently established by Li et al. [50, Theorem 8]. The proofs both theorems deferred to Appendices B.1 and B.2, respectively. We also note that Theorem 5.1 does require ReLU activation, because the ReLU function is replaced by a strictly monotone link function with bounded derivatives (up third order), then this is the setting of deterministic generalized linear bandit problem, which does allow a global regret that depends polynomially on dimension [23, 14, 52]. In this case, our Theorem C.3 can also give polynomial global regret result: because all local maxima of the reward function is global maximum [34, 43] and it also satisfies the strict- saddle property [26], the local regret result translates global regret result. This shows that our framework does separate the intractable cases from the tractable by the notions of local and global regrets.
With two-layer neural networks, we can relax the use of ReLU two-layer neural networks and Seaky-ReLL activations [75] because ((1) Leaky-ReLU can imple- ment ReLU activation. We conjecture that with more layers, the impossibility result also holds for broader sets of activations.
5.2 holds with
Inefficiency caused by optimism in nonlinear models. The next theorem states that the UCB al- gorithm that uses optimism- in even if the ground-truth is simple. In fact the UCB algorithm will keep exploring for an exponen- tial number of steps. So, UCB doesn't 't even converge to local max, indicating more sophisticated algorithms like ours are necessary. Proof of the theorem is deferred to Appendix B.3.
principle can overly explore in the action space,
Theorem 5.3. Consider the case where the ground- truth reward function is linear: (8" a)) and the action set a E Sd-1, the hypothesis is chosen to be two-layer neural network with width d, UCB algorithm with tightest upper confidence bound suffers exponential sample complexity.

---

Additional Related Work
There are several provable efficient algorithms without optimism for contextual bandits. Most of the results achieve a action-dimension dependent regret bound for contextual bandits [21, 1, 76, 45]. Foster, Rakhlin [24] and Simchi-Levi, Xu [67] exploit the exploration probability inversely depends on the empirical gap. The SquareCB algorithm [24] also extends to infinite actions with linear struc- ture. but the regret depends on the action dimension. The exploration strategy in Foster, Rakhlin [24] and Simchi-Levi, Xu [67] relies on the structure in the action space whereas ours exploits the ex- trapolation in the model space. Recently, Foster et [25] prove an instance-dependent regret bound for contextual bandit. Zhou et al. [81] also consider non-linear contextual bandits and propose the NeuralUCB algorithm by leveraging the NTK approach. It converges to globally optimal solution with number of samples polynomial in the number of contexts and the number of actions. For non- linear bandit problems with continuous actions, the sample complexity depends on the "effective dimension" of some kernel matrix. Because no algorithm can find the global maximum for the hard instances in Theorem 5.1 with polynomial samples, the effective dimension should be exponential in dimension for the hard instances.
Deterministic nonlinear bandits can also be formulated as zero-order optimization without noise (see Duchi et al. [20], Liu et al. [54] and references therein), where the reward is assumed to be any 1-Lipscchtzz function. In contrast, our algorithm exploits the knowledge of the reward function pa- rameterization and achieves an action-dimensionnfree sample complexity. For stochastic nonlinear bandit, Filippi et al. [23] consider generalized linear model. Valko et al. [70], Zhou et al. [81] focus on rewards in RKHS or NTK. Yang et al. [78] extends this approach to reinforcement learning.
Another line of research focuses on solving reinforcement learning by optimization on the policy space. Agarwal et al. [4] prove that natural policy gradient can solve tabular MDPs efficiently. Cai et al. [8] incorporate exploration bonus in proximal policy optimization algorithm and achieves polynomial regret in linear MDP setting.
Beyond linear function approximations, there also extensive studies on various settings that allow efficient algorithms. For example, rich observation MDPs [44, 11, 18, 57], state aggregation [16, 51J, Bellman rank [38, 13] and others [17, 53, 59, 80, 42].
Conclusion
In this paper, we design new algorithms whose local regrets are bounded by the sequential Rademacher complexity of particular loss functions. By rearranging the priorities of exploration versus exploitation, our algorithms avoid over-aggressive explorations caused by the optimism in the face of uncertainty principle, and hence apply to nonlinear models and dynamics.
We raise the following questions as future works:
1. Since we mainly focus on proving regret bound that depends only on the complexity of dynamics/reward class, our convergence rate in T likely not minimax optimal. Can our algorithms (or analysis) be modified to achieve minimax optimal regret for some of the instantiations such as sparse linear bandit and linear bandit with finite model class?
2. In the bandit setting, we focus on deterministic reward because ViOlin algorithm relies on finite difference to estimate the gradient and Hessian of reward function. In fact, The- B.1 shows that action-dimension-feee regret bound for linear models is impossible under standard Gaussian noise. Can we extend our algorithm to stochastic environments with additional assumptions noises?
3. In the reinforcement learning setting, we use policy gradient lemma to upper bound the gradient/Hessian loss by the dynamics loss, which inevitable require the policies being stochastic. Despite the success of stochastic policies in deep reinforcement learning, the optimal policy may not be stochastic, Can we extend the ViOlin algorithm reinforcement learning problems with deterministic policy hypothesis?
10

---

Acknowledgment
The authors would like thank Yuanhao Wang, Daogao Liu, Zhizhou Ren, Jason D. Lee, Colin Wei, Akshay Krishnamurthy, Alekh Agarwal and Csaba Szepesvári for helpful discussions. TM also partially supported by the Google Faculty Award, Lam Research, Toyota research, JD.com, NSF IIS 2045685, the Sloan Fellowship.
References
[1] Agarwal Alekh, Hsu Daniel, Kale Satyen, Langford John, Li Lihong, Schapire Robert. Taming the monster: fast and simple algorithm for contextual bandits International Conference on Machine Learning. 2014. 1638-1646.
[2] Agarwal Alekh, Jiang Nan, Kakade Sham M. Reinforcement learning: Theory and algorithms If CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep. 2019.
[3] Agarwal Alekh, Kakade Sham, Krishnamurthy Akshay, Sun Wen. FLAMBE: Structural com- plexity and representation learning of low rank MDPs // arXiv preprint arXiv:2006.108) 10114. 2020.
[4] Agarwal Alekh, Kakade Sham M, Lee Jason D, Mahajan Gaurav. Optimality and Approxi- mation with Policy Gradient Methods in Markov Decision Processes // Proceedings of Thirty Third Conference on Learning Theory. 125. 09-12 Jul 2020, 64-66. (Proceedings of Machine Learning Research).
[5] Amos Brandon, Xu Lei. Kolter J Zico. Input convex neural networks // International Conference on Machine Learning. 2017. 146-155.
[6] Ayoub Alex, Jia Zeyu, Szepesvari Csaba, Wang Mengdi, Yang Lin Model-Based Rein- forcement Learning with Value-Targeted Regression // Proceedings of the 37th International Conference on Machine Learning. 2020.
[7] Berner Christopher, Brockman Greg. Chan Brooke, Cheung Vicki. Debiak Przemyslaw, Denni- son Christy, Farhi David, Fischer Quirin, Hashme Sharig, Hesse Chris, others Dota 2 with large scale deep reinforcement learning // arXiv preprint 1xXiv:1912.06681 2019.
[8] Cai Qi. Yang Zhuoran, Jin Chi, Wang Zhaoran. Provably efficient exploration in policy opti- mization // International Conference on Machine Learning. 2020. 1283-1294.
[9] Carpentier Alexandra, Munos Rémi. Bandit theory meets compressed sensing for high dimen- sional stochastic linear bandit // Artificial Intelligence and Statistics. 2012. 190-198.
[10] Clavera Ignasi, Fu Yao, Abbeel Pieter. Model-Augmenter Actor-Critic: Backpropagating through Paths // International Conference on Learning Representations. 2019.
[11] Dann Christoph, Jiang Nan, Krishnamurtky Akshay, Agarwal Alekh, Langford John, Schapire Robert E. On
PAC-RL with Rich Observations // Advances in Neural Infor- mation Processing Systems. 2018.
[12] Dong Kefan, Luo Yuping, Yu Tianhe, Finn Chelsea, Ma Tengyu. On the expressivity of neural networks for deep reinforcement learning // International Conference on Machine Learning. 2020. 2627-2637.
[13] Dong Kefan, Peng Jian, Wang Yining, Zhou Yuan. Root-n-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rank // Conference Learning Theory. 2020. 1554-1557.
[14] Dong Shi, Ma Tengyu, Van Roy Benjamin. On the Performance Thompson Sampling on Logistic Bandits // Conference Learning Theory. 2019. 1158-1160.
[15] Dong Shi, Van Roy Benjamin. An information theorreti analysis for thompson sampling with many actions arXiv preprint arXiv:1805.1 1845. 2018.
[16] Dong Shi, Van Roy Benjamin, Zhou Zhengyuan. Provably efficient reinforcement learning with aggregated states /l arXiv preprint arXiv:1912.06346 2019.
[17] Du Simon S, Kakade Sham M, Lee Jason D, Lovelt Shachar, Mahajan Gaurav, Sun Wen, Wang Ruosong. Bilinear Classes: A Structural Framework for Provable Generalization in RI. Xix preprint arXiv:2 10890 2021.
11

---

[18] Du Simon S. Krishnamurthy Akshay, Jiang Nan, Agarwal Alekh, Dudik Miroslav, Langford John. Provably efficient RL with Rich Observations via Latent State Decoding // International Conference on Machine Learning. 2019. 1665-1674.
[19] Du Simon S, Luo Yuping, Wang Ruosong, Zhang Hanrui. Provably efficient Q-learning with function approximation via distribution shift error checking oracle // Advances in Neural In- formation Processing Systems. 2019. 8058-8068.
[20] Duchi John C, Jordan Michael I, Wainwright Martin J. Wibisono Andre. Optimal rates for zero-order convex optimization: The power of two function evaluations // IEEE Transactions on Information Theory. 2015. 61, 5. 2788-2806.
[21] Dudik Miroslav, Hsu Daniel, Kale Satyen, Karampatziakis Nikos, Langford John, Reyzin Lev, Zhang Tong. Efficient optimal learning for contextual bandits // arXiv preprint
2369. 2011.
[22] Faury Louis, Abeille Marc, Calauzènes Clément, Fercoq Olivier. Improved optimistic algo- rithms for logistic bandits // International Conference on Machine Learning. 2020. 3052-3060.
[23] Filippi Sarah, Cappé Olivier, Garivier Aurélien, Szepesvári Csaba. Parametric bandits: the Generalized Linear case // Proceedings of the 23rd International Conference on Neural Infor- mation Processing Systems-Volume 1. 2010. 586-594.
[24] Foster Dylan, Rakhlin Alexander. Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles // Proceedings of the 37th International Conference Machine Learning. 119. 13-18 Jul 2020. 3199-3210. (Proceedings of Machine Learning Research).
[25] Foster Dylan J, Rakhlin Alexander, Simchi-Lev David, Xu Yunzong. restance-dependee com- plexity of contextual bandits and reinforcement learning: A disagreement-basee perspective // arXiv preprint arXiv:2010.031 2020.
[26] Ge Rong, Huang Furong, Jin Chi, Yuan Yang. Escaping from saddle points-online stochastic gradient for tensor decomposition // Conference on Learning Theory. 2015. 7915.797-84 797-842.
[27] Ge Rong, Jin Chi, Zheng Yi. No Spurious Local Minima in Nonconvex Low Rank Problems: Unified Geometric Analysis // arXiv preprint teXiv:1704.00700 2017.
[28] Ge Rong, Lee Jason D, Ma Tengyu. Matrix completion has no spurious local minimum Advances in Neural Information Processing Systems. 2016. 2973-2981.
[29] Ge Rong, Ma Tengyu. On the optimization landscape of tensor decompositions // Mathematical Programming. 2020. 1-47.
[30] Hafner Danijar, Lillicrap Timothy, Bu Jimmy, Norouzi Mohammad. Dream to Control: Learn- ing Behaviors by Latent Imagination International Conference on Learning Representations. 2019.
[31] Hafner Danijar, Lillicrap Timothy, Fischer Ian, Villegas Ruben, Ha David, Lee Honglak, Davidson James. Learning latent dynamies for planning from pixels // International Con- ference on Machine Learning. 2019. 2555-2565.
[32] Hao Botao, Lattimore Tor, Szepesvári Csaba, Wang Mengdi. Online Sparse Reinforcement Learning/ // International Conference on Artificial Intelligence and Statistics. 2021. 316-324.
[33] Hao Botao, Lattimore Tor, Wang Mengdi. nigh-Dimensional Sparse Linear Bandits // arXiv preprint arXiv:201 1,04020. 2020.
[34] Hazan Elad, Levy Kfir, Shalev-Shwariz Shai. Beyond convexity: Stochastic quasi-convex opti- mization // Advances in Neural Information Processing Systems. 2015. 1594-1602.
[35] Hazan Elad, Singh Karan, Zhang Cyril. Efficient regret minimization in non-convex games // International Conference on Machine Learning. 2017. 1433-1441.
[36] Hsu Daniel, Kakade Sham, Zhang Tong, others A tail inequality for quadratic forms of subgaussian random vectors // Electronic Communications in Probability. 2012. 17.
[37] Janner Michael, Fu Justin, Zhang Marvin, Levine Sergey. When to trust your model: Model- based policy optimization // arXiv preprint 1iXiv:1906008255: 2019.
[38] Jiang Nan, Krishnamurthy Akshay, Agarwal Alekh, Langford John, Schupire Robert E. Con- textual Decision Processes with Low Bellman Rank are PAC-Learnable arxiv preprint arXiv:1610.09512. 2016.
12

---

[39] Jin Chi, Allen-Zhu Zeyuan, Bubeck Sebastien, Jordan Michael 1. Is Q-learning provably effi- cient? Proceedings of the 32nd International Conference on Neural Information Processing Systems. 2018. 4868 -878.
[40] Jin Chi, Yang Zhuoran, Wang Zhaoran, Jordan Michael I. Provably efficient reinforcement learning with linear function approximation // Conference on Learning Theory. 2020. 2137- 2143.
[41] Johnson Rie, Zhang Tong. Accelerating stochastic gradient descent using predictive variance reduction // Advances in Neural Information Processing Systems. 2013. 315-323.
[42] Kakade Sham, Krishnamurthh Akshay, Lowrey Kendall, Ohnishi Motoya, Sun Wen. Informa- tion theoretic regret bounds for online nonlinear control // arXiv preprint 12X1:2000..12666 2020.
[43] Kakade Sham M, Kanade Varun, Shamir Ohad, Kalai Adam. Efficient learning of generalized linear and single index models with isotonic regression Advances in Neural Information Processing Systems. 2011. 927-935.
[44] Krishnamurthy Akshay, Agarwal Alekh, Langford John. PAC reinforcement learning with rich observations // Advances in Neural Information Processing Systems. 2016. 1840-1848.
[45] Krishnamurthy Sanath Kumar, Hadad Vitor, Athey Susan. Adapting to misspecification in contextual bandits with offline regression oracles // Proceedings the 38th International Con- ference on Machine Learning. 139, 18-24 Jul 2021. 5805-5814, (Proceedings of Machine Learning Research).
[46] Lattimore Tor, Szepesvári Csaba. Bandit algorithms. 2020.
[47] Laurent Beatrice, Massart Pascal. Adaptive estimation of a quadratic functional by model selection // Annals of Statistics. 2000. 1302-1338.
[48] Lee Jason D, Simchowitz Max, Jordan Michael I, Recht Benjamin. Gradient descent only converges to minimizers // Conference on learning theory. 2016. 1246-1257.
[49] Levine Sergey, Finn Chelsea, Darrell Trevor, Abbeel Pieter. End-to-end training of deep visuo- motor policies // The Journal of Machine Learning Research. 2016. 17, 1. 1334-1373.
[50] Li Gene, Kamath Pritish, Foster Dylan J., Srebro Nathan. Eluder Dimension and Generalized Rank. 2021.
[51] Li Lihong. A unifying framework for computational reinforcement learning theory. 2009.
[52] Li Lihong, Lu Yu, Zhou Dengyong. Provably optimal algorithms for generalized linear contex-
tual bandits // International Conference on Machine Learning. 2017. 2071-2080.
[53] Litmman Michael L, Sutton Richard S, Singh Satinder P. Predictive representations of state. // NIPS. 14, 1555. 2001. 30.
[54] Liu Sijia, Chen Pin-Yu, Kailkhura Bhavya, Zhang Gaoyuan, Hero III Alfred O, Varshney Pramod K. A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learn- ing: Principals, Recent Advances, and Applications // IEEE Signal Processing Magazine. 2020. 37, 43-54.
[55] Luo Yuping, Xu Huazhe, Li Yuanzhi, Tian Yuandong, Darrell Trevor, Ma Tengyu. Algorithmic Framework for Model-based Deep Reinforcement Learning with Theoretical Guarantees International Conference on Learning Representations. 2019.
[56] Mahmud Mufti, Kaiser Mohammed Shamim, Hussain Amir, Vassanelli Stefano. Applications of deep learning and reinforcement learning biological data // IEEE transactions on neural networks and learning systems. 2018. 29, 6. 2063-2079.
[57] Misra Dipendra, Henaff Mikael, Krishnamurthy Akshay, Langford John. Kinematic state ab- straction and provably efficient rich-observation reinforcement learning // International con- ference on machine learning. 2020. 6961-6971.
[58] Modi Adirya, Jiang Nan, Tewari Ambuj. Singh Satinder. Sample complexity of reinforcement learning using linearly combined model ensembles // International Conference on Artificial Intelligence and Statistics. 2020. 2010-2020.
[59] Munos Rémi Error bounds for approximate value iteration Proceedings of the National Conference on Artificial Intelligence. 2005. 1006.
13

---

[60] Osband lan. Roy Benjamin Van. Model-based reinforcement learning and the eluder dimen- sion // Proceedings of the 27th International Conference on Neural Information Processing Voltum 1. 2014. 1466-1474.
[61] Rakhlin Alexander, Sridharan Karthik, Tewari Ambuj. Online learning: stochastic, constrained, and smoothed adversaries Proceedings of the 24th International Conference on Neural In- formation Processing Systems. 2011. 1764-1772
[62] Rakhlin Alexander, Sridharan Karthik, Tewari Ambuj. Online Learning via Sequential Com- plexities // Journal of Machine Learning Research. 2015. 16, 6. 155-186.
[63] Rakhlin Alexander, Sridharan Karthik, Tewari Ambuj. Sequential complexities and uniform martingale laws of large numbers // Probability Theory and Related Fields. 2015, 161, 1-2. 111-153.
[64] Russo Daniel, Roy Benjamin Van. Eluder dimension and the sample complexity of optimistic exploration // Proceedings of the 26th International Conference on Neural Information Pro- cessing SystemssVolume 2. 2013. 2256-2264.
[65] Shariff Roshan, Szepesvári Csaba. Efficient planning in large MDPs with weak linear function approximation // arXiv preprint arXiv:2007 www:2007.06184 2020.
[66] Silver David, Schrittwieser Julian, Simonyan Karen, Antonoglou loannis, Huang Aja, Guez Arthur, Hubert Thomas, Baker Lucas, Lai Matthew, Bolton Adrian, others. Mastering the game of Go without human knowledge // Nature. 2017. 550, 7676. 354.
[67] Sivchi-Levi David, Xu Yunzong. Bypassing the Monster: A Faster and Simpler Optimal Algo- rithm for Contextual Bandits under Realizability // arviv preprint arXiv:2003. 12699. 2020.
[68] Sun Wen, Jiang Nan, Krishnamurthy Akshay, Agarwal Alekh, Langford John. Model-based in contextual decision processes: Pac bounds and exponential improvements over model-free approaches // Conference on Learning Theory. 2019. 2898-2933.
[69]
Reinforcement learning: An introduction. 2011.
[70]
Valko Michul, Korda Nathan, Munos Rémi, Flaounas Iias, Cristianini Nello. Finite-time anal- ysis of kernelised contextual bandits // Proceedings of the TWenty-Ninth Conference on Un- certainty in Artificial Intelligence. 2013. 654-663.
[71] Wang Ruosong, Salakhutdinov Ruslan, Yang Lin F. Provably Efficient Reinforcement Learning with General Value Function Approximation // Advances in Neural Information Processing Systems. 2020.
[72] Wang Yining, Chen Yi, Fang Ethan X. Wang Zhaoran, Li Runze. Nearly Dimension- Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection arXiv preprint 20Xi::000900200: 2020.
[73] Wang Yining, Wang Ruosong. Du Simon S. Krishnamurthy Akshay. Optimism in Rein- forcement Learning with Generalized Linear Function Approximation // arXiv preprint
arXiv:1912.04136. 2019.
[74] Williams Ronald Simple statistical gradient-following algorithms for connectionist rein- forcement learning // Machine learning. 1992. 8, 3-4. 229-256.
[75] Xu Bing, Wang Naiyan, Chen Tianqi, Li Mu. Empirical Evaluation of Rectified Activations in Convolutional Network. 2015.
[76] Xu Yunbei, Zeevi Assaf. Upper counterfactual confidence bounds: a new optimism principle for contextual bandits // arXiv preprint arXiv:2007.0733 2020.
[77] Yang Lin, Wang Mengdi. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound // International Conference on Machine Learning. 2020. 10746-10756.
[78] Yang Zhuoran, Jin Chi, Wang Zhaoran, Wang Mengdi, Jordan Michael I. Bridging exploration and general function approximation in reinforcement learning: Provably efficient kemnel and neural value iterations // arXiv preprint arXiv:201 1eXi:22011.046222 1.04622. 2020.
[79] Yu Tianhe, Thomas Garrett, Yu Lantao, Ermon Stefano, Zou James, Levine Sergey, Finn Chelsea, Ma Tengyu. MOPO: Model-hased Offline Policy Optimization arXiv preprint arXiv:2005.13255 13239. 2020.
14

---

[80] Zanette Andrea, Lazaric Alessandro, Kochenderfer Mykel, Brunskill Emmaa Learning Near Optimal Policies with Low Inherent Bellman Error International Conference on Machine Learning. 2020.
[81] Zhou Dongruo, Li Lihong, Gu Quamquan. Neural contextual bandits with UCB-based explo- ration // International Conference Machine Learning. 2020. 11492-11502.
15


Reviews:
[{"review_id": "a2ekU0QLKMt", "reviewer": "Reviewer_n7MF", "summary": "The paper proposes new nonlinear bandit and reinforcement learning algorithms whose sample complexity toward local maxima are bounded by the sequential Rademacher complexity of particular loss functions (and do not depend on the action dimension). An interesting insight obtained in this paper is that when dealing with nonlinear models and dynamics (in settings where the action dimension may be very large), maximizing the virtual return suggested by a strong online learner (with carefully augmented loss) may lead to good convergence guarantees to local maxima.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written. The theoretical results are sound and the proofs are correct. The problem studied in this paper is well-motivated and very interesting. The main algorithmic idea of augmenting the loss function of the online learner is quite clever. I recommend  acceptance.\n\nOn the downside, I would like to say that the algorithms and results in this paper are more like \"proofs of concept\", and some places of the paper are still clunky. I discuss several limitations and provide some suggestions below.\n\n1. The paper seems to mainly focus on the \"pure exploration\" or PAC setting of bandits and RL. While there is some discussion on the \"local regret\" in Appendix D.5, it is just a slightly different analysis of the same algorithm (without additional efforts tailored for the regret setting). Do the authors have any ideas on whether one can get substantially better regret bounds by incorporating additional considerations for the regret setting? By the way, an interesting thing that I find in this paper is that the current algorithm already tries to avoid \"over exploration\", even in a \"pure exploration\" setting --- is it because of the fact that the paper only asks for convergence to local maxima? Do the authors have any ideas on whether the notion of \"local regret\" would encourage certain behavior of learning algorithms?\n\n2. The assumptions on deterministic reward and deterministic dynamics are restrictive. While the authors provide some impossibility results on the noisy reward setting, a framework that can only deal with deterministic reward and dynamics are far from being practical. I would encourage the authors to improve their framework and try to understand this issue better in future work.\n\n3. The theoretical bounds proved in this paper have a much worse dependence on $\\epsilon$ compared with existing dimension-dependent bounds. This may make the statistical guarantees undesirable compared with dimension-dependent or specialized algorithms in many cases.\n\n4. Since the algorithms need to *augment the loss functions to be non-standard ones* (see equation (5)), the tasks of bounding the sequential Rademacher complexity and designing computationally efficient online learners both become more challenging. \n\nI notice that the authors actually have some very related discussions in Appendix B. It would be good if some key points of the discussions can also be mentioned in the main text.\n\nMinor comments: \n1. In lines 145-146, the notation $[T]$ appears without any definition (I understand what $[T]$ means but it is good to write everything clearly).\n2. I find the following two references also relevant.\n[1] Xu, Y., & Zeevi, A. (2020). Upper counterfactual confidence bounds: a new optimism principle for contextual bandits. arXiv preprint arXiv:2007.07876.\n[2] Foster, D. J., Gentile, C., Mohri, M., & Zimmert, J. (2020). Adapting to misspecification in contextual bandits. NeurIPS. \nBoth [1] and [2] consider model-based nonlinear (contextual) bandits with infinite actions and obtain regret bounds that depend on the action dimension.\n\n======update after rebuttal======\n\nThank you for the feedback. I keep my positive rating and vote for accepting the paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have discussed the potential negative societal impact in their Appendix A.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "Cu9rp-qpnAx", "reviewer": "Reviewer_uBiC", "summary": "This paper studies model-based nonlinear bandit and reinforcement learning and proposes the ViOlin algorithm (Virtual Ascent with Online Model Learner). The main contributions are as follows.\n\n1) For bandit problems, with deterministic reward functions satisfying Assumption 2.1 (Lipschitz over continuous actions, smooth over actions, and the third order derivative over action is bounded), and with sublinear sequential Rademacher complexity, they show that the ViOlin algorithm achieves an $\\epsilon$ approximate local maximum using $\\tilde{O}(\\epsilon^{-8})$ iterations, which does not depend on the dimension of action space.\n\nSome instantiations are shown, including linear bandit with finite model class, with sparse or structured model vectors, and two-layer neural nets, which is the first result of non-linear bandit with neural network parameterization.\n\nThe main idea is to fit the estimation of gradient and Hessian, and show that the current greedy action can be improved until the parameter is close enough to an approximate local maximum.\n\n2) For RL, with deterministic transition, and Assumptions 4.1 and 4.2 (regularity of value function and policy), they show that the similar ViOlin (Algorithm 2) achieves an $\\epsilon$ approximate local maximum using also sublinear iterations.\n\nThe difference with bandit design is that the loss function is using one-step model prediction errors rather than gradient and Hessian.\n\n3) The authors show some lower bound results. In particular, (i) using ReLU activations in one-layer neural network bandits, finding global optimal action takes exponentially large iterations. (ii) the failure of Eluder dimension: one-layer neural networks has its Eluder dimensions exponentially large. (iii) the failure of UCB: with linear reward function, and two-layer neural network as the hypothesis function class, UCB would take exponential sample complexity to find the optimal action.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, this is a good paper, making good contributions to RL theory community. The presentation of the main paper is clear and easy to follow. The intuition is very well explained. There are following questions I would ask the authors to clarify.\n\n1) In lower bound results, it is mentioned (at least for one layer NNs) ReLU is needed. Does the \"Two-layer neural nets\" instantiation also apply to NNs with ReLU activations? It seems from \"link function with bounded derivatives up to the third order\", it does not apply to ReLU.\n\nThen is it possible that for the link functions with \"bounded derivatives up to the third order\", finding a global optimal solution is also possibly efficient?\n\n2) Is Hessian used for eliminating saddle points? What kind of results can be obtained if just using gradient?\n\n3) The deterministic reward and deterministic transition assumption makes the algorithm kind of restrictive. Any idea how to remove those assumptions?\n\nMinors:\n\n4) What is the meaning of $\\mathcal{R}$ in Algorithm 1 (line 3)?\n\n5) What is the definition of $\\mathfrak{A}$ in line 887? Does this mean the approximate local minima set?\n\n======update after rebuttal======\n\nThank you for the feedback. I would keep my current rating and vote for accepting the paper.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper is mainly theoretical and the algorithm is not implemented. There is no specific potential negative societal impact of this work. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "CmJv3wYdmr2", "reviewer": "Reviewer_SzXN", "summary": "This work investigates model-based bandit and RL under non-linear function approximations. In particular, it focuses on convergence to approximate local maxima under deterministic reward (and deterministic dynamics for RL). Several technical results are derived showing that the presented model-based algorithm can have a favorable sample complexity that only depends on the sequential Rademacher complexity of the model class. The paper also contains some hardness results to better contextualize the contribution of this work.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is technically dense but the authors manage to provide enough intuition and explanation for the results. There are generally enough context for one to understand the corresponding results. I didn't go into the technical details, but the contributions seem solid, and the results and technical novelty could be interesting for the theoretical community.\n\nOne question I have is that to what extend, the results depend on the deterministic assumptions (deterministic dynamics and reward). The technical novelty as claimed by the authors is to explore with model-based curvature estimates. To achieve this, it seems from page 6 that the algorithm leverages the deterministic property to estimate the projections. The authors also mention some motivation for considering deterministic rewards (lines 136 -138). Overall, I would appreciate a concrete remark on both the deterministic dynamics and reward, explaining the potential difficulties/extensions of the current framework. \n\n========after response======\nI thank the authors for the response. I'm happy to keep my positive evaluation and hope that the authors could also include few sentences in the final version to clarity the assumptions.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5h"}, "extra_text": {}}, {"review_id": "7qva9C-cM9", "reviewer": "Reviewer_XRrF", "summary": "This paper considers learning in deterministic bandit and reinforcement learning problems with function approximation. They quantify the complexity of the function class using the sequential Rademacher complexity of a related loss function (although in some settings, it is not super clear how this relates to the complexity of the reward/value function). In the bandit setting, they provide a general regret bound and instantiate this for various different assumptions on the model, including two layer neural networks, which is a nice result. To extend their results to reinforcement learning some assumptions are made so that the value function can be written as a non-linear function of the policy parameters and optimized accordingly. They then provide a slightly simpler loss function and show that the sample complexity can be bounded in terms of the sequential Rademacher complexity of this. Finally, the authors provide some interesting lower bounds showing that finding a global maximum is exponentially hard, and motivating them to study the sample complexity to find an approximate local maximum.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The discussion of the pros/cons of the UCB algorithm in lines 198-208 is nice as is the non-technical motivation of the algorithm in lines 219-228. However, I have very little intuition about why the loss function and definition of y_t used are the most appropriate/natural. It is nice to see a general result bounding the sample complexity in terms of the sequential Rademacher complexity in Theorem 1. In the examples following Theorem 3.1, it always seems that zeta_h^4 epsilon^{-8}> zeta^2_{3rd} epsilon^{-6}. Are there any realistic cases where the converse is true? Does their result ever lead to epsilon^{-6} rather than epsilon^{-8} complexity? The epsilon^{-8} dependence seems sub-optimal, I imagine it should be epsilon^{-2}  but do the authors have any intuition/lower bound to indicate what the optimal dependence on epsilon is in this setting? In the discussion about the application of their results for linear bandit in Section 3.1, it would be helpful to also include the dependence on epsilon of some of the other algorithms. It is difficult to compare fairly when the authors only highlight the terms that their algorithm improves on. In some cases it may be that d<1/epsilon so a worse dependence on d would be preferred to a worse dependence on epsilon in such a case. I am also curious about the results for sparse linear bandits when Theta is infinite? In such a case I imagine we may replace |Theta| with the covering number, which would then lead to linear dependence on d, do other approaches have worse dependence on d in that case too?\n\nIt is nice that there is an extension to reinforcement learning. The assumptions made in the extension to model-based reinforcement learning seem to reformulate the problem as a contextual bandit problem, thus making the extension simpler. However they seem quite strong, even though the authors give a simple example where they are satisfied. The loss function for the reinforcement learning setting seems slightly more natural than that in the bandit case. I would appreciate more discussion of how this is calculated within the algorithm though (e.g. in round t, do we need to play according to both policies pi_t and pi_{t-1}?) The loss function depends mainly on the transition, and so the sample complexity depends on the difficulty of learning some function of the transition function. However, the introduction to section 4 is written as if we can make an assumption on the value function only, but this may not necessarily lead to having a transition function st the Rademacher complexity of the loss is small. Instead it seems that the idea is that we assume the dynamics are members of some function class and then show that this leads to a value function of the desired form as in example 4.3. It would be helpful to clarify this.\n\nThe lower bounds in Section 5 are nice. In particular, the result in Theorem 5.1 showing that the sample complexity can be exponential in d when comparing to global maximum for one-layer neural networks is nice, and well motivates comparing to local maxima as is done in this paper. Similarly the result in theorem 5.2 is also nice (although it is proved concurrently in another paper). In theorem 5.3, is the sample complexity exponential when compared to the local maximum or global maximum? And is the only reason for the exponential sample complexity the fact that the action set is chosen to be exponentially large?\n\nLots of content seems to be deferred to the appendix making the main paper hard to follow at times.\n\nMinor comments:\n- It would be good to have a more thorough discussion of [54]. Saying the conditions can ‘likely’ not be satisfied is not rigorous enough.\n- the discussion in lines 136-138 is incomplete and needs expanding upon. I thought the remark was to motivate the need to consider deterministic rewards, but Appendix C.1 seems to be about the difficulty of finding a global maximum. It is not clear to me how this relates to considering local maxima in a noisy setting.\n- I don’t follow the discussion of why the number of random projections in line 234 does not depend on the dimension, can more details be given?\n- I’m not sure what the ‘local regret’ means in line 21 is nor where it is defined.\n- the definition of the loss function in (5) is quite involved. I therefore have no intuition for how difficult this will be to learn as a function of the original parameters of the problem and why this is an appropriate loss definition. Also what is kappa here?\n- A couple of times in Section 3.1, the authors ‘claim’ that the sample complexity is bounded by XXX. Is this just a claim or is it proven?\n- I don’t follow why it is beneficial to consider stochastic policies in Section 4, could more details be provided on this?\n\n\n=========\nAfter response:\nThank you to the authors for answering most of my questions. I hope that for the final version of the paper the authors clarify some of the discussions and add further details about the dependence on epsilon and the construction of the exponential lower bound.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Some limitations discussed but not in huge detail. There is no discussion of societal impact but since this is a theoretical paper, that is probably OK.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper takes a new approach to the theory of exploration in reinforcement learning with function approximation, with the main insight being to aim for local optimality rather than global optimality. The reviewers agree that the paper is well-motivated, technically interesting, 
 and fairly creative result that will likely inspire further research along this direction in RL. While there are many directions in which the technical results themselves can likely be improved (e.g., moving beyond deterministic dynamics), it seems appropriate to leave this for future work.

The authors are encouraged to incorporate the clarifications suggested by the reviewers.
Decision: Accept (Poster)