Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
Year: 2022

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 sample complexity 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.

heading: 1 Introduction
text: 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 a plethora of results on 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 to neural networks.
The goal of this paper is to theoretically analyze model-based nonlinear bandit and RL with neural net 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 on 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 apply to 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, we will prove that one-layer neural nets do not have polynomially-bounded Eluder dimension.1 (See more evidence below.)
The limited progress on neural net approximation is to some extent not surprising. Given a deterministic 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
1This result is also proved by the concurrent Li et al. [50, Theorem 8] independently.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
fundamentally, we find that it is also statistically intractable for solving the one-hidden-layer 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 in 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 approximate 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].2
Zero-order optimization or policy gradient algorithms can converge to local maxima and become natural potential competitors. They are widely believed to be less sample-efficient than the modelbased 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 sample complexity mostly depends (polynomially) on the complexity of the model class, whereas policy gradient algorithms’ 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:
Can we design algorithms that converge to approximate local maxima with sample complexities that depend only and polynomially on 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 η(θ, a) for action a ∈ A under instance θ ∈ Θ. We use sequential Rademacher complexity [62, 63] to capture the complexity of the reward function η. 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 {η(θ, ·) : θ ∈ Θ} is bounded by √ R(Θ)Tpolylog(T ). Then, there exists an algorithm (ViOlin, Alg. 1) that finds an
-approximate local maximum with Õ(R(Θ) −8) 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 is the first action-dimension-free 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 Θ. Because η is concave in action a, our result leads to a sample complexity O(poly(log|Θ|, 1/ )) for finding an -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 dA. 2. Linear bandit with s-sparse or structured instance parameters. Our algorithm ViOlin achieves an O(poly(s, 1/ )) sample complexity when the instance/model parameter is s-sparse and the reward is deterministic. The sample complexity of zero-order optimization depends polynomially on dA. Carpentier, Munos [9] achieve a stronger Õ(s √ T ) regret bound for s-sparse linear
bandits with actions set A = Sd−1. In contrast, our ViOlin algorithm applies more generally to any structured instance parameter set. Other related results either leverage the rather strong anti-concentration 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 -approximate local maximum Õ(poly(1/ )). Zero-order optimization can also find a local maximum but with Ω(dA) samples.
2The all-local-maxima-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.
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 to model-based RL with deterministic nonlinear dynamics and deterministic reward.
Theorem 1.2 (Informal version of Theorem 4.4). Consider RL problems with deterministic dynamics class and stochastic policy class that satisfy some Lipschitz properties. Suppose the sequential Rademacher complexity of the `2 losses for learning the dynamics is bounded by√ R(Θ)Tpolylog(T ). Then, ViOlin for RL (Alg. 2) finds an -approximate local maximum policy with Õ(R(Θ) −8) 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 a concrete example of RL problems with nonlinear models satisfying our Lipschitz assumptions in Example 4.3 of Section 4, which may also serve as a testbed for future model-based deep RL analysis. Other prior works on model-based RL do not apply to one-hidden-layer neural nets because they conclude global convergence which is not possible for one-hidden-layer neural nets in the worst case.
Technical novelty: exploring by model-based curvature estimate. The main challenge is that the optimism-in-face-of-uncertainty exploration principle seems to be too aggressive—for a nonlinear model class, even if the ground-truth model is linear, optimistic exploration leads to exponentially large model cumulative prediction errors and exponential sample complexity (see Theorem 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 augment 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 curvature prediction depends on the model complexity instead of action dimension in the zerooptimization 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-dimension dependency. In contrast, our algorithms’ exploration relies more on the learning of the model. Consequently, our sample complexity can be action-dimension-free.

heading: 2 Problem Setup and Preliminaries
text: 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.

heading: 2.1 Nonlinear Bandit Problem with Deterministic Reward
text: We consider deterministic nonlinear bandits with continuous actions. Let θ ∈ Θ be the parameter that specifies the bandit instance, a ∈ RdA the action, and η(θ, a) ∈ [0, 1] the reward function. Let θ? denote the unknown ground-truth parameter. Throughout the paper, we work under the realizability assumption that θ? ∈ Θ. A bandit algorithm aims to maximize η(θ?, a). Let a? = argmaxa η(θ?, a) be the optimal action (breaking tie arbitrarily). Let ‖H‖sp be the spectral norm of a 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 et al. [26]).
Assumption 2.1. We assume that for all θ ∈ Θ, supa ‖∇aη(θ, a)‖2 ≤ ζg and supa ∥∥∇2aη(θ, a)∥∥sp ≤ ζh. For every θ ∈ Θ and a1, a2 ∈ RdA , ∥∥∇2aη(θ, a1)−∇2aη(θ, a2)∥∥sp ≤ ζ3rd ‖a1 − a2‖2.
As a motivation to consider deterministic rewards, we prove in Theorem B.1 for a special case that no algorithm can find a local maximum in less than √ dA steps. The result implies that an actiondimension-free sample complexity bound is impossible with standard sub-Gaussian noise.3
Approximate local maxima. In this paper, we aim to find a local maximum of the real reward function η(θ?, ·). A point x is an ( g, h)-approximate local maximum of a twice-differentiable function f(x) if ‖∇f(x)‖2 ≤ g , and λmax(∇2f(x)) ≤ h. As argued in Sec. 1 and proved in Sec. 5, because reaching a global maximum is computational and statistically intractable for nonlinear problems, we only aim to reach a local maximum.
Sample complexity and local regret for converging to local maxima. Let at 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 at is an ( g, h) approximate local maximum with probability at least 1−δ. We also define the “local regret” by comparing with an approximate local maximum. We defer the discussion to Appendix C.5.

heading: 2.2 Reinforcement Learning
text: A finite horizon Markov decision process (MDP) with deterministic dynamics is defined by a tuple 〈T, r,H, µ1〉. Let S and A be the state and action spaces. The dynamics T : S × A → S gives next state, r : S × A → [0, 1] is the reward function. H and µ1 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 S1, · · · ,SH such that S = ∪Hh=1Sh, and for any sh ∈ S, ah ∈ a, T (sh, ah) ∈ Sh+1. We consider parameterized policy and dynamics. Let Π = {πψ : ψ ∈ Ψ} be the policy class and {Tθ : θ ∈ Θ} the dynamics class. The value function is V πT (sh) , E[ ∑H h′=h r(sh′ , ah′)], where ah ∼ π(· | sh), sh+1 = T (sh, ah). Sharing the notation with the bandit setting, let η(θ, ψ) = Es1∼µ1V πψ Tθ
(s1) be the expected return of policy πψ under dynamics Tθ. Let ρπT be the distribution of state action pairs when running policy π in dynamics T . For simplicity, we do not distinguish ψ, θ from πψ , Tθ when the context is clear. For example, we write V ψ θ = V πψ Tθ .

heading: 2.3 Preliminary on Online Learning with Stochastic Input Components
text: Consider a prediction problem where we aim to learn a function that maps from X to Y parameterized by parameters in Θ. Let `((x, y); θ) be a loss function that maps (X × Y) × Θ → R+. An online learner R aims to solve the prediction tasks under the presence of an adversarial nature iteratively. At time step t, the following happens.
1. The learner computes a distribution pt = R({(xi, yi)}t−1i=1) over the parameter space Θ. 2. The adversary selects a point x̄t ∈ X̄ (which may depend on pt) and generates a sample ξt from
some fixed distribution q. Let xt , (x̄t, ξt), and the adversary picks a label yt ∈ Y . 3. The data point (xt, yt) is revealed to the online learner.
The online learner aims to minimize the expected regret in T rounds of interactions, defined as
REGOLT , E ξt∼q,θt∼pt ∀1≤t≤T
[∑T t=1 `((xt, yt); θt)− infθ∈Θ ∑T t=1 `((xt, yt); θ) ] . (1)
The difference of the formulation from the most standard online learning setup is that the ξt part of the input is randomized instead of adversarially chosen (and the learner knows the distribution of ξt before making the prediction pt). It was introduced by Rakhlin et al. [61], who considered a more generalized setting where the distribution q in round t can depend on {x1, · · · , xt−1}.
3We rely on deterministic reward to estimate the gradient by finite difference. This method can be extended to stochastic rewards with multiple-point feedback [54].
We adopt the notation from Rakhlin et al. [61, 62] to define the (distribution-dependent) sequential Rademacher complexity of the loss function class L = {(x, y) 7→ `((x, y); θ) : θ ∈ Θ}. For any set Z , a Z-valued tree with length T is a set of functions {zi : {±1}i−1 → Z}Ti=1. For a sequence of Rademacher random variables = ( 1, · · · , T ) and for every 1 ≤ t ≤ T, we denote zt( ) , zt( 1, · · · , t−1). For any X̄ -valued tree x and anyY-valued tree y, we define the sequential Rademacher complexity as
RT (L;x,y) , Eξ1,···,ξtE [ sup `∈L ∑T t=1 t`((x( ), ξt),y( )) ] . (2)
We also define RT (L) = supx,yRT (L;x,y), where the supremum is taken over all X̄ -valued and Y-valued trees. Rakhlin et al. [61] proved the existence of an algorithm whose online learning regret satisfies REGOLT ≤ 2RT (L).

heading: 3 Model-based Algorithms for Nonlinear Bandit
text: We first study model-based algorithms for nonlinear continuous bandits problem, which is a simplification of model-based reinforcement learning. We use the notations and setup in Section 2.1.
Abstraction of analysis for model-based algorithms. Typically, a model-based algorithm explicitly maintains an estimated model θ̂t, and sometimes maintains a distribution, posterior, or confidence region of θ̂t. We will call η(θ?, a) the real reward of action a, and η(θ̂t, 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 η(θ̂t, at) is sufficiently high. (ii) the virtual reward η(θ̂t, at) is close to the real reward η(θ?, at) in the long run.
One can expect that a proper combination of property (i) and (ii) leads to showing the real reward η(θ?, at) 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 at and an estimated model θ̂t that maximize the virtual reward η(θ̂t, at) among those models agreeing with the observed data. The pro is that it satisfies property (i) by definition—η(θ̂t, at) is higher than the optimal real reward η(θ?, a?). The downside is that ensuring (ii) is challenging and often requires strong complexity measure bound such as 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 θ̂t 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) is 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 a strong online learning algorithm to predict θ̂t with the objective that η(θ̂t, at) matches η(θ?, at) . 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. Sequential Rademacher complexity turns out to be a fundamentally more relaxed complexity measure than Eluder dimension—e.g., two-layer neural networks’ sequential Rademacher complexity is polynomial 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 θ̂t is that we lose optimism/exploration that ensured property (i).4
4More concretely, the algorithm can get stuck when (1) at is optimal for θ̂t, (2) θ̂t fits actions at (and history) accurately, but (3) θ̂t 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.
Algorithm 1 ViOlin: Virtual Ascent with Online Model Learner (for Bandit)
1: Set parameter κ1 = 2ζg and κ2 = 640 √
2ζh. LetH0 = ∅; choose a0 ∈ A arbitrarily. 2: for t = 1, 2, · · · do 3: Run online learner R on Ht−1 with loss function ` (defined in equation (5)) and obtain pt = R(Ht−1). 4: Let at ← argmaxa Eθt∼pt [η(θt, a)]. 5: Sample ut, vt ∼ N (0, IdA×dA) independently. 6: Let ξt = (ut, vt), x̄t = (at, at−1), and xt = (x̄t, ξt) 7: Compute yt = [η(θ?, at), η(θ?, at−1), 〈∇aη(θ?, at−1), ut〉, 〈∇2aη(θ?, at−1)ut, vt〉] ∈ R4
by applying a finite number of actions in the real environments using equation (3) and (4). 8: UpdateHt = Ht−1 ∪ {(xt, yt)}
Our approach realizes property (i) in a 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 a local maximum of the real reward function. We achieve this by demanding the estimated model θ̂t not only to predict the real reward accurately, but also to predict the gradient∇aη(θ?, a) and Hessian ∇2aη(θ?, a) accurately. In other words, we augment the loss function for the online learner so that the estimated model satisfies η(θ̂t, at) ≈ η(θ?, at), ∇aη(θ̂t, at) ≈ ∇aη(θ?, at), and ∇2aη(θ̂t, at) ≈ ∇2aη(θ?, at) in the long run. This implies that when at is not at a local maximum of the real reward function η(θ?, ·), then it’s not at a maximum of the virtual reward η(θ̂t, ·), 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 ∇aη(θ?, at) correctly, we need a supervision for it. However, we only observe the reward η(θ?, at). Leveraging the deterministic reward property, we use rewards at a and a + α1u to estimate the projection of the gradient at a random direction u:
〈∇aη(θ?, a), u〉 = lim α1→0 (η(θ?, a+ α1u)− η(θ?, a)) /α1 (3)
It turns out that the number of random projections 〈∇aη(θ?, a), u〉 needed for ensuring a large virtual gradient does not depend on the dimension, because we only use these projections to estimate the norm of the gradient but not necessarily the exact direction of the gradient (which may require d samples.) Similarly, we can also estimate the projection of Hessian to two random directions u, v ∈ dA by:〈 ∇2aη(θ?, a)v, u 〉 = lim α2→0 (〈∇aη(θ?, a+ α2v), u〉 − 〈∇aη(θ?, a), u〉) /α2 (4)
= lim α2→0 lim α1→0
((η(θ?, a+ α1u+ α2v)− η(θ?, a+ α2v))− (η(θ?, a+ α1u)− η(θ?, a))) /(α1α2)
Algorithmically, we can choose infinitesimal α1 and α2. Note that α1 should be at least an order smaller than α2 because the limitations are taken sequentially.
We create the following prediction task for an online learner: let θ be the parameter, x = (a, a′, u, v) be the input, ŷ = [η(θ, a), η(θ, a′), 〈∇aη(θ, a′), u〉, 〈∇2aη(θ, a′)u, v〉] ∈ R4 be the output, and y = [η(θ?, a), η(θ?, a′), 〈∇aη(θ?, a′), u〉, 〈∇2aη(θ?, a′)u, v〉] ∈ R4 be the supervision, and the loss function be
`(((a, a′, u, v), y); θ) ,([ŷ]1 − [y]1)2 + ([ŷ]2 − [y]2)2 + min ( κ21, ([ŷ]3 − [y]3) 2 )
+ min ( κ22, ([ŷ]4 − [y]4) 2 )
(5)
Here we used [y]i to denote the i-th coordinate of y ∈ R4 to avoid confusing with yt (the supervision at time t.) 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 √ R(Θ)Tpolylog(T ). The sample complexity of Alg. 1 (for finding an ( , 6 √ ζ3rd )-approximate local maximum) is bounded by Õ(C41R(Θ) max ( ζ4h −8, ζ23rd −6)).
We present a proof sketch in Appendix C.1 . Proof of Theorem 3.1 is deferred to Appendix C.4. We can also boost the success probability by running Alg. 1 multiple times. In addition, we can prove that our algorithm enjoys a sublinear local regret. The theorem statement and proof is shown in Appendix C.5 and Appendix C.6 respectively.

heading: 3.1 Instantiations of Theorem 3.1
text: 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 setA = {a ∈ Rd : ‖a‖2≤ 1} and finite model class Θ ⊂ {θ ∈ Rd : ‖θ‖2= 1}. Let η(θ, a) = 〈θ, a〉 be the reward. We deal with the constrained action set by using a surrogate loss η̃(θ, a) , 〈θ, a〉− 12‖a‖ 2 2 and apply Theorem C.3 with reward η̃. We claim that the sample complexity (of finding an -suboptimal action for η(θ?, a)) is bounded by Õ(log|Θ| −8).5 Note that the bound is independent of the dimension d. By contrast, the SquareCB algorithm [24] depends polynomially on d (see Theorem 7 of [24]). Zero-order optimization approach [20] in this case also gives a poly(d) regret bound.
Linear bandit with sparse or structured model vectors. We consider the deterministic linear bandit setting where the model class Θ = {θ ∈ Rd : ‖θ‖0≤ s, ‖θ‖2= 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|Θ| −8polylog(d)). The sample complexity of our algorithm only depends on the sparsity level s (up to logarithmic factors), whereas the Eluder dimension of sparse linear hypothesis is still Ω(d) (see Lemma C.4). Lattimore, Szepesvári [46] show a Ω(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 θ has an additional structure. Suppose Θ = {θ = φ(z) : z ∈ Rs} for some Lipschitz function φ. Then, a 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 as deterministic logistic bandits.
Two-layer neural nets. We consider the reward function given by two-layer neural networks with width m. For matrices W1 ∈ Rm×d and W2 ∈ R1×m, let η((W1,W2), a) = W2σ(W1a)− 12 ‖a‖ 2 2 for some nonlinear link function σ : R → [0, 1] with bounded derivatives up to the third order. Recall that the (1,∞)-norm ofW>1 is defined by maxi∈[m] ∑d j=1 |[W1]i,j |. That is, the max 1-norm of
the rows of W1. Let the model hypothesis space be Θ = {(W1,W2) : ∥∥W>1 ∥∥1,∞ ≤ 1, ‖W2‖1 ≤ 1} and θ , (W1,W2). We claim that Alg .1 finds an ( , 6 √ ζ3rd )-approximate local maximum in
Õ ( −8polylog(d) ) steps. To the best of our knowledge, this is the first result analyzing nonlinear bandit with neural network parameterization. The result follows from analyzing the sequential Rademacher complexity for η, 〈∇aη, u〉, and 〈u,∇2aη · v〉, and finally the resulting loss function `. 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 η((W1,W2), a) is concave in the action. (This is a special case of input convex neural networks [5].) In this case, Alg. 1 finds an -suboptimal action (see Theorem C.6).

heading: 4 Model-based Reinforcement Learning
text: In this section, we extend the results in Section 3 to model-based reinforcement learning with deterministic dynamics and reward function.
We can always view a model-based reinforcement learning problem with parameterized dynamics and policy as a nonlinear bandit problem in the following way. The policy parameter ψ corresponds to the action a in bandit, and the dynamics parameter θ corresponds to the model parameter θ in
5Recall that in bandit literature, action a is an -approximate optimal action if η(θ?, a) ≥ η(θ?, a?)− .
bandit. The expected total return η(θ, ψ) = Es1∼µ1V πψ Tθ
(s1) is the analogue of reward function in bandit. We intend to make the same regularity assumptions on η as in the bandit case (that is, Assumption 2.1) with a being replaced by ψ. However, when the policy is deterministic, the reward function η has Lipschitz constant with respect to ψ that is exponential in H (even if dynamics 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 ψ.
Blindly treating RL as a bandit only utilizes the reward but not the state observations. In fact, one major reason why model-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.t to the states and Lipschitzness of policies w.r.t to its parameters, beyond those assumptions for the total reward η(θ, ψ) in Assumption 2.1.
Assumption 4.1. We assume the following (analogous to Assumption 2.1) on the value function: ∀ψ ∈ Ψ, θ ∈ Θ, s, s′ ∈ S we have |V ψθ (s)− V ψ θ (s ′)| ≤ L0‖s−s′‖2; ‖∇ψV ψθ (s)−∇ψV ψ θ (s
′)‖2≤ L1‖s− s′‖2; ‖∇2ψV ψ θ (s)−∇2ψV ψ θ (s
′)‖sp≤ L2‖s− s′‖2. Assumption 4.2. We assume the following Lipschitzness assumptions on the stochastic policies parameterization πψ .6 ‖Ea∼πψ(·|s)[(∇ψ log πψ(a | s))(∇ψ log πψ(a | s))>]‖sp≤ χg; ‖Ea∼πψ(·|s)[(∇ψ log πψ(a | s))⊗4]‖sp≤ χf ; ‖Ea∼πψ(·|s)[(∇2ψ log πψ(a | s))(∇2ψ log πψ(a | s))>]‖sp≤ χh.
Our results depends polynomially on the parameters L0, L1, L2, χg, χf and χh. 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 O(1).
Example 4.3. Let state space S be the unit ball in Rd and action space A be Rd. The (deterministic) dynamics T is given by T (s, a) = Nθ(s + a), where N is a nonlinear model parameterized by θ, e.g., a neural network. We assume that θ belongs to a finite hypothesis class Θ that satisfies ‖Nθ(s+ a)‖2 ≤ 1 for all θ ∈ Θ, s ∈ S, a ∈ A. Assume that the reward function r(s, a) is LrLipschitz w.r.t `2-norm, that is, satisfying |r(s1, a1)− r(s2, a2)| ≤ Lr(‖s1 − s2‖2 + ‖a1 − a2‖2). We consider a family of stochastic Gaussian policies with the mean being linear in the state: πψ(s) = N (ψs, σ2I), parameterized by ψ ∈ Rd×d with ‖ψ‖op ≤ 1. We consider σ ∈ (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 ζg, ζh, ζ3rd, L0, L1, L2, χg, χf and χh bounded by poly(σ, 1/σ,H,Lr).
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 τt = (s1, a1, · · · , sH , aH) be a trajectory sampled from policy πψt under the real dynamics Tθ? . Similarly to [79], when the value function is Lipschitz, we upper bound ∆t,1 = |η(θt, ψt) − η(θ?, ψt)| by the one-step model prediction errors. Similarly, we can upper bound the gradient and Hessian errors by model prediction errors. As a result, the loss function simply can be set to
`((τt, τ ′ t); θ) = ∑ (sh,ah)∈τt ‖Tθ(sh, ah)− Tθ?(sh, ah)‖22 + ∑ (s′h,a ′ h)∈τ ′ t ‖Tθ(s′h, a′h)− Tθ?(s′h, a′h)‖ 2 2 (6)
for two trajectories τ, τ ′ sampled from policy πψt and πψt−1 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. 2 in Appendix D. Main theorem for Alg. 2 is shown below.
Theorem 4.4. Let c1 = HL20(4H2χh + 4H4χf + 2H2χg + 1) + HL21(8H2χg + 2) + 4HL22 and C1 = 2 +
ζg ζh . Suppose the sequential Rademacher complexity of the loss function (defined
6Recall that the injective norm of a k-th order tensor A ∈ Rd⊗k is defined as ∥∥A⊗k∥∥
sp = supu∈Sd−1 〈 A, u⊗k 〉 .
in Eq. (6)) is bounded by √ R(Θ)Tpolylog(T ). The sample complexity of Alg. 2 (for finding an ( , 6 √ ζ3rd )-approximate local maximum) is bounded by Õ(c21C41R(Θ) max ( ζ4h −8, ζ23rd
−6)). 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 Õ ( poly(σ, 1/σ,H,Lr) log|Θ| −8 ) .
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 polynomially on ‖∇ψ log πψ(a | s)‖2 [4]. For the instance in in Example 4.3, this translates to a sample complexity guarantee on the order of √ d/σ. In contrast, our sample complexity is independent of the dimension d. Instead, our bound depends on the complexity of the model family Θ which could be much smaller than the ambient dimension—this demonstrates that we leverage the model extrapolation.

heading: 5 Lower Bounds
text: 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 η((w, b), a) = ReLU(〈w, a〉+ b). Note that the reward function can also be made smooth by replacing the activation by a smoothed version. For example, η((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 activation, the minimax sample complexity is Ω(ε−(d−2)).
We can also prove that the eluder dimension of the constructed reward function class is exponential.
Theorem 5.2. The ε-eluder dimension of one-layer neural networks is at least Ω(ε−(d−1)).
This result is concurrently established by Li et al. [50, Theorem 8]. The proofs of both theorems are deferred to Appendices B.1 and B.2, respectively. We also note that Theorem 5.1 does require ReLU activation, because if the ReLU function is replaced by a strictly monotone link function with bounded derivatives (up to 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 strictsaddle property [26], the local regret result translates to a 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 activation—Theorem 5.2 holds with two-layer neural networks and leaky-ReLU activations [75] because O(1) leaky-ReLU can implement a ReLU activation. We conjecture that with more layers, the impossibility result also holds for a broader sets of activations.
Inefficiency caused by optimism in nonlinear models. The next theorem states that the UCB algorithm that uses optimism-in-face-of-uncertainty principle can overly explore in the action space, even if the ground-truth is simple. In fact the UCB algorithm will keep exploring for an exponential number of steps. So, UCB doesn’t even converge to local max, indicating more sophisticated algorithms like ours are necessary. Proof of the theorem is deferred to Appendix B.3.
Theorem 5.3. Consider the case where the ground-truth reward function is linear: 〈θ?, a〉 and the action set is a ∈ Sd−1. If the hypothesis is chosen to be two-layer neural network with width d, UCB algorithm with tightest upper confidence bound suffers exponential sample complexity .

heading: 6 Additional Related Work
text: 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 structure, 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 extrapolation in the model space. Recently, Foster et al. [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 a globally optimal solution with number of samples polynomial in the number of contexts and the number of actions. For nonlinear 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-Lipschitz function. In contrast, our algorithm exploits the knowledge of the reward function parameterization and achieves an action-dimension-free 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 a 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 are also extensive studies on various settings that allow efficient algorithms. For example, rich observation MDPs [44, 11, 18, 57], state aggregation [16, 51], Bellman rank [38, 13] and others [17, 53, 59, 80, 42].

heading: 7 Conclusion
text: 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 a regret bound that depends only on the complexity of dynamics/reward class, our convergence rate in T is 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 our ViOlin algorithm relies on finite difference to estimate the gradient and Hessian of reward function. In fact, Theorem B.1 shows that action-dimension-free regret bound for linear models is impossible under standard Gaussian noise. Can we extend our algorithm to stochastic environments with additional assumptions on 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 to reinforcement learning problems with deterministic policy hypothesis?

heading: Acknowledgment
text: The authors would like to thank Yuanhao Wang, Daogao Liu, Zhizhou Ren, Jason D. Lee, Colin Wei, Akshay Krishnamurthy, Alekh Agarwal and Csaba Szepesvári for helpful discussions. TM is also partially supported by the Google Faculty Award, Lam Research, Toyota research, JD.com, NSF IIS 2045685, the Sloan Fellowship.

Review summaries:
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.  1) 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.  Some 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.  The 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.  2) 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.  The difference with bandit design is that the loss function is using one-step model prediction errors rather than gradient and Hessian.  3) 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.

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.

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.