Optimal Gradient-based Algorithms for Non-concave Bandit Optimization
Authors: Baihe Huang
Kaixuan Huang
Sham M. Kakade
Jason D. Lee
Qi Lei
Runzhe Wang
Jiaqi Yang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Nonlinear bandit
zeroth-order optimization
algebraic variety

Abstract: Bandit problems with linear or concave reward have been extensively studied, but relatively few works have studied bandits with non-concave reward. This work considers a large family of bandit problems where the unknown underlying reward function is non-concave, including the low-rank generalized linear bandit problems and two-layer neural network with polynomial activation bandit problem.
For the low-rank generalized linear bandit problem, we provide a minimax-optimal algorithm in the dimension, refuting both conjectures in \cite{lu2021low,jun2019bilinear}. Our algorithms are based on a unified zeroth-order optimization paradigm that applies in great generality and attains optimal rates in several structured polynomial settings (in the dimension). We further demonstrate the applicability of our algorithms in RL in the generative model setting, resulting in improved sample complexity over prior approaches.
Finally, we show that the standard optimistic algorithms (e.g., UCB) are sub-optimal by dimension factors. In the neural net setting (with polynomial activation functions) with noiseless reward, we provide a bandit algorithm with sample complexity equal to the intrinsic algebraic dimension. Again, we show that optimistic approaches have worse sample complexity, polynomial in the extrinsic dimension (which could be exponentially worse in the polynomial degree).

Optimal Gradient-based Algorithms for Non-concave Bandit Optimization
Baihe Huang", Kaixuan Huang"", Shamm M. Kakade Jason D. Lee²*
Qi Lei Runzhe Wang"*, ,Jiqq Yang**
Peking University
Princeton University University of Harvard Microsofft Research
TTinnghua University
Abstract
Bandit problems with linear or concave reward have been extensively studied, but relatively few works have studied bandits with non-concave reward. This work considers large family bandit problems where the unknown underlying reward function is non-concave, including the low-rank generalized linear bandit problems and two-layer neural network with polynomial activation bandit problem. For the low-rank generalized linear bandit problem, we provide minimax-optimes algorithm the dimension, refuting both conjectures in [55] 43 Our algorithms are based on unified zeroth-order optimization paradigm that applies in great generality and attains optimal rates in several structured polynomial settings (in the dimension). We further demonstrate the applicability of our algorithms in RL in the generative model setting, resulting in improved sample complexity over prior approaches. Finally, we show that the standard optimistic algorithms (c.g.. UCB) are sub-optimal by dimension factors. In the neural net setting (with polynomial activation functions) with noiseless reward, we provide bandit algorithm with sample complexity equal to the intrinsic algebraic dimension. Again, we show that optimistic approaches have worse sample complexity, polynomial in the extrinsic dimension (which could be exponentially worse in the polynomial degree).
1 Introduction
Bandits 51 are a class of online decision-making problems where an agent interacts with the environment, only receives scalar reward, and aims maximize the reward. In many real-world applications, bandit and RI. problems are characterized by large or continuous action space. To encode the reward information associated with the action, function approximation for the reward function is typically used, such as linear bandits (20]. Stochastic linear bandits assume the mean reward be the inner product between the unknown model parameter and the feature vector associated with the action. This setting has been extensively studied, and algorithms with optimal regret are
known 20 51 13
However, linear bandits suffer from limited representation power unless the feature dimension is prohibitively large. A comprehensive empirical study [60) found that real-world problems required non-limear models and thus non-concave rewards to attain good performance on a testbed of bandit problems. To take step beyond the linear setting, it becomes
challenging to design optimal algorithms. Unlike linear bandits, more sophisticated algorithms beyond optimism are necessary. For instance, natural first step look quadratic 44 and higher-order polynomial (35 reward. In
Alphabetical order. Correspondence to: Qi Lei, gilei@princeton.edd edu. Jason D. Lee, jasonlee@
print princeto ponceton.c edu
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

the context of phase retrieval, which is special case for the quadratic bandit, people have derived However, the
algorithms that achieve minimax risks in the statistical learning setting 52 T5
straightforward adaptation of these algorithms results in sub-optimal dimension dependency.
In the bandit domain, existing analysis the nonlinear setting includes eluder dimension subspace climination [55] 43), etc. Their results also suffer from larger dimension dependency than the best known lower bound in many settings. (See Table and Section 3 for detailed discussion of
[2]
these results.) Therefore in this paper, we are interested in investigating the following question:
What the optimal regret for non-concave bandit problems, including structured polynomials (low-rank etc.)? Can we design algorithms with optimal dimension dependency?
Contributions: In this paper, we answer the questions and close the gap (in problem dimension) for various non-linear bandit problems.
1. First, we design stochastic zeroth-order gradient-like ascent algorithms to attain minimax re- gret for a large class of structured polynomials. The class of structured polynomials contains bilinear and low-rank linear bandits and symmetric and asymmetric higher-orde' homoge- neous polynomial bandits with action dimension d. Though the reward is non-concave, we combine techniques from two bodies of work, non-convex optimization and numerical linear algebra, to design robust gradient- algorithms are also computationally efficient, practical, and easily implementable. In all cases, algorithms attain the optimal dependence dimension d, which was not previously attainable using existing optimism techniques. As a byproduct, our algorithm refiutes] the conjecture from 43] on the bilinear bandit, and the conjecture from [55 on low-rank linear bandit by giving an algorithm that attains the optimal dimension dependence.
algorithms that converge to global maxima. Our
2. We demonstrate that our techniques for non-concave bandits extend to RL in the generative setting, improving upon existing optimism techniques.
3. When the reward is general polynomial without noise, we prove that solving polynomial equations achieves regret equal to the intrinsic algebraic dimension of the underlying polynomial class, which is often linear in d for interesting cases. In general, this complexity cannot be further improved.
4. Furthermore, we provide lower bound showing that all UCB algorithms have sample complexity of (dd)), where p is the degree of the polynomial. The dimension of all homogeneous polynomials of degree p in dimension d is dP, showing that UCB is oblivious to the polynomial class and highly sub-optimal even in the noiseless setting.
1.1 Related Work
Linear Bandits. Linear bandit problems and their variants are studied in 20
33
The matching upper bound and minimax lower bound achieves O(dv T) regret. Structured linear
bandits, including sparse linear bandit 3 which developed an online-to tonnee-t-connee to-ooooidence-seeee technique.
This technique yields the optimal O( ((sdTT) rate for sparse linear bandit. However (55] employed
the same technique for low-rank linear bandits giving algorithm with regret O( O( (k)y(
which we improve to O /d (p)olyk))T) which meets the lower bound given in (55).
Eluder Dimension. [62 proposed the eluder dimension as a general complexity measure for nonlinea bandits. However, the eluder dimension is only known to give non-trivial bounds for linear function classes and monotone functions of linear function classes. For structured polynomial classes, the eluder dimension simply embeds into an ambient linear space of dimension dP, where d is the dimension and is the degree. This parallels the linearization/TTK line in supervised learning
71 30 7 which show that linearization also incurs a similarly large penalty of dP sample complexity,
and more advanced algorithm design is need to circumvent linearization [0
25
72
27
59 29
57 36 68 19].
Non-concave Bandits. To our knowledge, there is general study of non-concave bandits, likely due to the difficulty of globally maximizing non-concave functions. A natural starting point of
"Our algorithm estimates the gradient, but with some irreducible bias for the tensor case. Note that our algorithms converge linearly despite the bias.
3 Both papers conjectured regret of the form ddppolyykk)) based on convincing but potentially mislead- ing heuristics.
2

---

studying the non-concave setting are quadratic rewards such as the Rayleigh quotient, or namely bandit PCA 47 28 In the bilinear [43] and low-rank linear setting [55] with rank parameter
matrices achieved Ō poly(k)T) regret. Other literature considered related but different settings that are not comparable least (VVTT)) This includes the subspace exploration and refinement algorithms from 4 55),
results
48 We note that the regret of all previous work is
or from eluder dimension [62 Recently (35] considers online problem with a low-rank tensor associated with axis-aligned set of arms, which corresponds to finding the largest entry of the tensor.
Finally, [47] study the bandit PCA problem in the adversarial setting, attaining regret of O(vdTT).
We leave adapting our results to the adversarial setting as an open problem.
Due to space limitation we defer the discussion of some equally important literature the appendix.
2 Preliminaries
2.1 Sctup: Structured Polynomial Bandit
We study structured polynomial bandit problems where the reward function from a class of structured polynomials (see below). A player plays actions for T rounds; at each round / E [T]. the player chooses one action a, from the feasible action set A and receives the reward ry afterward.
We consider both the stochastic case where r = === fe(a,) + T/s where 1/2 is the random noise, and the noiseless case r; fa()).. Specifically the function fe is unknown the player. but lies in known function class F. We use the notation vec( to denote the vectorization of matrix or a tensor M, and & to denote the p-order tensor product of a vector v. For vectors use || ||- ||2 denote its l2 norm. For matrices || ||2 or stands for its spectral norm, and || || is Frobenius norm. For integer n, [n] denotes set {1, .. n). n.) For cleaner presentation, in the main paper we use O θ or to hide universal constants, polynomial factors in and polylog factors in dimension d, error E, eigengap A, total round number T or failure rate 5.
to
We now present the outline with the settings considered in the paper:
The stochastic bandit eigenvector case, FEV, considers action set A = {a E Rdd ||a|/2 S 1] as shown in Section 3.1 and
fola) Ma, M Σ NooouJ, for orthonormal by M Rddd 12 x 2 A2 2 ... 2 Axx
FEV
The stochastic low-rank linear reward case, FLr considers action sets on bounded matrices A = {A Rdxd ||ll| S 1} in Section 3.2 and
A) vec(M) vec (A), M E Rdddd rank rank(M) = k. M = M
M $ }
FLR
We illustrate how to apply the established bandit oracles attain better sample complexity for RL. problems with the simulator in Section 3.2.1
The stochastic homogeneous polynomial reward case is presented in Section
3.3 For the
symmetric case in Section 3.3.1 the action sets are A {a E Rd ||a|| S 1}, and
fo(a) Σ 12r rd X1 Ael 2 ... 2 |Ax
(1 a) for orthonormal my.
FSYM
in the asymmetric case in Section D.3.1 the action sets are A {a- = a(1) @ (2)) 8 ... ( (p) E Rdd
Vgg [p]. (g)(2 S 1}, and
FASYM { fe(a) Ex X II T (v) T a())) for orthonormal vy(4) for each g, 12r" = A > A2 2 ...
In the above settings, there is stochastic noise on the observed rewards. We also consider noiseless settings as below:
The noiseless polynomial reward case presented Section 3.4 The action sets A are subsets of
Rdd and Fp (fe(a) (0, a. @r) 0 E V. 11a J 1441188 oo is an algebraic variety].
3

---

Pars
HBB Oid ke
7B Ola
Fi
Upper Bound from LinUUCBleluder
Oiderin he "ee""xe yk pl OlNokk -3 (oven OldPke (add p) 1M
Oia
Gap-dependent
NIA ŌUCKKPP SHA
Olads ( Ö(min (etenddf -. (1a"e"
OldPhh 222 $c-)
NPM
Resalts
Gap independent
NIA
Lower bounds
18/d"1-r->>
Table 1: Baselines and Our Main Results (for stochastic settings). Eigengap A
A \1/A. C' is a constant that depends on failure probability, The result with * is from [55
122
Additionally, FF needs be admissible (Definition 3.20p. This class includes two-layer neural networks with polynomial activations (i.e. structured polynomials We study the fundamental limits of all UCB algorithms in Section G.O.1 as they are Q2dd worse than our algorithm presented in Section 3.4.1
In the above settings, we are concerned with the cumulative regret R(T) for T rounds. Let fō
sup (a). (T) Σ (fa fo(a.)). Since the parameters can be chosen adversarially, aEA
bounding R[T)- = sup, RT" in this paper. In all the stochastic settings above, we make the standard assumption on stochasticity that vi is conditionally zero-mean I-sub-Gaussian random variable regarding the randomness before
2.2 Warm-up: Adapting Existing Algorithms
In all of the above settings, the function class can be viewed as a generalized linear function. Namely, there is fixed feature maps v ø so that fe(a) = (00)TT(() Thus it straightforward to adapt linear bandit algorithms like the renowned LinUCB [53 to our settings. Furthermore, another baseline is given by the eluder dimension argument 162 67 which gives explicit upper bounds for general function classes. We present the best upper bound by adapting these methods as a baseline in Table [ together with our newly-derived lower bound and upper bound in this paper. The best-known statistical rates are based on the following result.
Theorem 2.1 (Proposition 4 in (22). With a O(T-2) appropriately small, given the o-covering- number N (under (1-lloe) and the a-elluder-dimension dg of the function class F, Eluder UCB (Algorithm 2) achieves regret O(ddgTlog
In the first row of Table I we further elaborate on the best results obtained from Theorem 2.1 in individual settings. More details can be found in Appendix B
3
Main results
We now present our main results. We consider different stochastic settings (see Table I and one noiseless setting with structured polynomials. In the cases of stochastic reward, all our algorithms can be unified as gradient- based optimization. At
each stage with a candidate action a, we define the estimator G,, (a) == 1 (f
2)),, with 2, A/ o2Ia) and proper step-size (26] Therefore Ez (Ga)) o
()a)+ +0(3))(()) = ((1 ((1-c)=-o 2V with enough samples, we are able to implement noisy gradient ascent with bias.
V fo(a) +((2) for p-th order homogeneous polynomials. Therefore
In the noiseless setting, our algorithm solves for the parameter O with randomly sampled actions
{ar} and the noiseless reward (fo(a:)), and then determines the optimal action by computing arg max (o(a).
3.1 Stochastic Eigenvalue Reward (FRv)
Now consider bandits with stochastic reward r(a) a Ma + with action set A {all|a/|z $ 1}.
M Em_ Acoruu is symmetric and satisfies y* Ai |aal 2 |all... (Ar], ~ -N (0,
Denote by a" the optimal action (++,), the leading eigenvector of M, (a*) Ma" >1. Let
A = A D22 > 0 be the eigengap and == A1/A be the condition number.
Remark 3.1 (Negative leading eigenvalue). For a symmetric matrix M, we will conduct noisy power method to recover its leading eigenvector, and therefore require its leading eigenvalue X

---

to be positive. It is straightforward to extend to the setting where the nonzero eigenvalues satisfy:
X1 > X2 X > A1+1... >xs and [>g] > A1. For this problem. we can shift M to get M + [ and the eigen-spectrum now becomes X1 + X2 + D ... therefore, we can still recover the optimal action with dependence on the new condition number (>1 + pxx))(A X2).
Remark 3.2 (Asymmetrie matrix). Our algorithm naturally extends to the asymmetric setting: f(a1, 02) af Mas, where M = -UEV. T. This setting can be reduced to the symmetric case via defining
0 M
M T 0
V U
V -U
E
0
V
V V -U]
M
= 2
-
U
which is symmetric matrix, and its eigenvalues are to; (M), the singular values of M. Therefore our analysis on symmetric matrices also applies to the asymmetric setting and will equivalently depend the gap between the top singular values of M. A formal asymmetric symmetric conversion algorithm is presented in Algorithm 1 128).
Algorithm. We note that by conducting zeroth-order gradient estimate 1/n Σ. E/ (fa/2++))))))) 77:)2 with step-size 1/2 [26] and sample size n. we get an estimate for (f,==(((a//+/22++t)
a² Ma when z (O, )²). Therefore we are able use noisy power method recover the top 2
eigenvector. We present the complete algorithm in Algorithm and attain gap-dependent risk bound:
Algorithm 1 Noisy power method for bandit eigenvalue problem.
1: Input: Quadratic function f A -> IR with noisy reward, failure probability 5, error e.
2: Initialization: Initial action an E Rd randomly sampled on the unit sphere gd-1, We set
a = D2e/Aul, sample size per iteration n = C, [Or log(d/=)
22,2, sample variance
m dd (n/oo)/)))..) total iteration
3: for Iteration / from 1 to L do
n. 4: Sample 2, (0, 1/mJa), 1,2, .. (Re-sample the whole batch if exists 2; with
norm greater than 1.)
5: Noisy power method:
6: Take actions a. a 1 and observe r; f(a,) + 77, E [n]
7: Update normalized action a + m E TiZt, and normalize a; at a1/l|ail2.
8: Output: az.
Theorem 3.3 (Regret bound for noisy power method (NPM)). In Algorithm ! set s E (0, 1/2), = (.1/(LoS) and let Ct., Cs, Ca, Om be large enough universal constants. Then with high probability 0.9 we have: the output a satisfies tan A(a", .a)) S and yields r* r'ttimmt reward: and the total number of actions we take Ö sd By explore-then-come (ETC) the cumulative
regret is at most O(V))d'T)
All proofs in this subsection are in Appendix
Remark 3.4 (Intuition of 43 and how to overcome the conjectured lower bound via the design of adaptive algorithms). Let us consider the rank 1 case r( (a (a"@" 0² + 77. A random action Uni has f(a) 1/d2, and the noise has standard deviation O(1). Thus the signal- co-noise-ratio is O(1/d²) and the optimal action H" requires d bits to encode. If we were to play non-adaptively, this would require (dd)) queries and result in regret VdTT which matches the result of 143).
To go beyond this, we must design algorithms that are adaptive, meaning the information in f(a) + +n strictly larger than 1 z- As an illustration of why this possible, consider batching the time- steps into d stages so that each stage decode bit of 6" At the first stage, random exploration Uni gives signal-to-noice noise-raaiio O (1//d)). Suppose bits of 0 are decoded k-th stage by Ô, adaptive al algorithms can boost the signal-to-noised
to O(k/d by using ① as bootstrap (e.g. exploring with 0 + where is random exploration in the unexplored subspace). In this way
5

---

adaptive algorithmss only need d² queries in (k + 1-t stage and so the total number of queries sums up to Ex_ d ls= de log d.
Gradient descent and power method offer a computationally efficient and seamless way to implement the above intuition. For every iterate action we estimate Ma from noisy observations and take as our next action at. With df /(>²e²) samples, noisy power method enjoys linear progress tan O(a p()" S max maax(aannaa a, a ),),), where < is a constant that depends x1 X2. and E. Therefore even though every step costs d² samples, overall we only need logarithmic (in d,E,21, x2)
iterations to find an E-optimal action.
Remark 3.5 (Connection to phase retrieval and eluder dimension). For rank- I case M = xx the bilinear bandits can be viewed phase retrieval. where observes y, (a,- x)² a, Ma, plus some noise Vrr ~ -N(,000 o²). The optimal (among non-adaptive algorithms) sample complexity to recover x: is o² o²d/e2 2 [16 [5) where they play a. from random Gaussian (0, I). However, in bandit, we need to set the variance of a to at most 1/d to ensure ||a]]= S 1. Our problem is equivalent to observing b-/d where their a/ /d ~ NO, (001//dI) and noise level nr /d ~ -N(0,1) 1), i.e., o² = d? Therefore one gets d'fe f2² even for the rank-1 problems. On the other hand, for all rank-1 M the condition number K = 1; and thus our results match the lower bound (see Section (.3.2) up to logarithmic factors, and also have fundamental improvements for phase retrieval problems by leveraging adaptivity.
For UCB algorithms based on eluder dimension, the regret upper bound is O( (og())) =
O(Vd'T) as presented in Theorem 2.1 where the dependence on d is consistent with [43 555 and is non-optimal.
The previous result depends on the eigen-gap When the matrix is ill-conditioned, i.e., A1 is very close to A2, we can obtain gap-free versions with a modification: The first idea stems from finding higher reward instead of recovering the optimal action. Therefore when ) and X2 are very close (gap being smaller than desired accuracy E), acceptable to find any direction in the span of (#1, 22). More formally, we care about the convergence speed of identifying any action in the space spanned by any top eigenvectors (whose associated eigenvalues are higher than λ - E). Therefore the convergence speed will depend on e instead of X A2-
Corollary 3.6 (Gap-free regret bound). For positive semi-definite matrix M, by setting a = 1- e² /2 in Algorithm 7 and performing ETC afterwards, one can obtain cunulative regret of (/1///2//5//55 4//574/55.
Again, the PSD assumption is not essential. For general symmetric matrices with a1 2 Ao .... 0 > Ay. We can still conduct shifted power method on M >xdL. yielding cumulative regret of (A1
Another novel gap-free algorithm requires to identify any top eigenspace Vaa, I E [A]: Vna is the column span of (v), 12 v.). Notice that in traditional subspace iteration, the convergence rate of recovering Vi depends on the eigengap A := | 1. Meanwhile, since Σ/= A x at least one eigengap is larger or equal to Az/k. /k. Suppose A, 2 λ1/k; we can, therefore, set = 1/k and recover the top subspace up to A1 error, which will give an c-optimal reward in the end. We don't t know 1* beforehand and will try recovering the top subspace V1, V2 V& respectively. which will only lose a ie factor. With the existence of 1*, at least one trial (on recovering Vi-) will be successful with the parameters of our choice, and we simply output the best action among all trials.
Theorem 3.7 (Informal statement: (gap-free) subspace iteration). By running subspace iteration (Al- gorithm with proper choices of parameters, we attain a cumulative regret of ((x) 1/3////// ( 2/7) Algoritlum with another set of parameters can also recover the whole eigenspace, and achieve cumulative regret of (() where k = >1/Duul
3.2 Stochastic Low-rank Linear Bandits (FIR)
In the low-rank linear bandit, the reward function is s(A) = (A, M), with noisy observations r; = f(A) + n7, and the action space is {A E Rdxdd ||A|]] F S 1}. Without loss of generality we assume k, the rank of M satisfies & < g. since when is of the same order as d, the known upper and lower bound are both Vd O D(v ((voTT) [55] and there is room for improvement. We

---

Frv
LB (k
143
NPM
Gap-free NPM
Subspace Iteration min(k (dT))/s .tpp/ssss/. 1//3 (xdd)))8)))
Regret
VdeT
VROdT
///5////
FLR
LB (155))
UB (1551)
Subspace Iteration
Regret
TT)
Vd or / /d TT
min( ( d 2T, (dkTT)2/3)
Table 2: Summary of results for quadratic reward. All red expressions are our results. LB, UB, NPM stands for lower bound, upper bound, and noisy power method respectively. A X [Agl is the eigengap, and = \1 /, K = >1 are the condition numbers. The result with * is not computationally tractable. For low-rank setting in this table, treat || Fr constant for simplicity and leave its dependence in the theorems. Our upper bounds match the lower bound in terms of dimension and substantially improve over existing algorithms that are computationally efficient.
write r" = || I 1, therefore the optimal action is A M/r". r. In this section, we write X to be the s-th column of any matrix X.
As presented in Algorithm 4 we conduct noisy subspace iteration to estimate the right eigenspace of M. Subspace iteration requires calculating M.,, every step. This can be done by considering a change of variable of gXX) := f(XX)
(XX .M) whose gradienf is Vg(X): = 2M X. The zeroth-order gradient estimator can then be employed to stochastically estimate MX. We instantiate the analysis with symmetric M while extending to asymmetric setting is straightforward
since the problem can be reduced symmetric setting (suggested in Remark 3.2).
With stochastic observations and randomly sampled actions, we achieve the next iterate Y that satisfies M X E E|]i in Algorithm 4 Let M VEVT, With proper concentration bounds presented in the appendix, we can apply the analysis of noisy power method (37] and get:
Theorem 3.8 (Informal statement; sample complexity for low-rank linear reward). With Algorithum + XL satisfies || Xx VII S e/4, and output À satisfies ||
11 |||M[| with sample
size O( 2-2).
We defer the proof' for low-rank linear reward in Appendix
Corollary 3.9 (Regret bound for low-rank linear reward). We first call Algorithm with ea ( to obtain A; we then play A for the remaining steps. The cumulative regret satisfies
R(T) S 2 (kkrt)xx,
with high probability 0.9.
To be more precise, we need 7 2 (ddk/ for Algorithm to take sufficient actions; however, the conclusion still holds for smaller T. Since simply playing O for all T actions will give sharper
bound of R)T) < T < Ö(r VdRkX (T)). For cleaner presentation, won't stress this for every statement.
Notice that l < | M //A S kx is order k. Thus for well-conditioned matrices M, our upper bound of Ö( M /ETTT matches the lower bound / VPPP except for logarithmic factors.
In the previous setting with the bandit eigenvalue problem, estimating M up to e-error (measured by operator norm) gives us an e-optimal reward. Therefore the sample complexity for eigenvalue re- ward with similar subspace iteration is M |Bdk///
In this section, on the other hand, we need ()
Frobenius norm bound Ar. A S e; naturally the complexity becomes
Theorem 3.10 (Regret bound for low-rank linear reward: gap-free case). Set g e (+=)))
n = θ ( = (log(d/E)) and k' = 2k in Algorithm and get A. Then we play it for the remaining steps, the cumulative regret satisfies:
R(T)- < (3
'Direetly performing projected gradient descent on fAA would work, since this is not an adaptive
algorithm the gradient of linear function is constant. This would incur regret /dd poly(.....
7

---

We summarize all our results and prior work for quadratic reward in Table 2
3.2.1 RL with Simulator: Q-function is Quadratic and Bellman Complete
In this section we demonstrate how our results for non-concave bandits also apply to reinforcement learning. Let Ty be the Bellman operator applied to the Q-function Qh+1 defined as:
() a) ra(s, a) + (( [max Qh+i(s',
Definition 3.11 (Bellman complete). Given MDP M (S,A, H), function class Fn SSxA R. h E [H] is called Bellman complete if for all h E [H] and Qh+1 E Fi+1, Th (Qn+1) E Fr.
Assumption 3.12 (Bellman complete for low-rank quadratic reward). We assume the function class Fu+- = {fm= : fs,(s, a) = Φ( a) M a), MM) S k, and < (mi)) S }. is class of quadratic function and the MDP is Bellman complete. Here f' (M((0())) =
Σj=1 2o (,, a)), when M M= = Σ Ayu,oJ. Write Q% = -[M; E Fr.
Observation: When querying 01-1, we observe s ~ (P(1sh-1,aRk- and reward Th- Th-1(sh-1,0 ah-1).
Oracle recover parameter M: Given n 2 (M))E" if one can play 2 n samples a; and observe yi a. Ma; + 7, E [n]] with I-sub-gaussian and mean-zero noise 1,, we can recover M = (f(a,,)))) 9:){) such that || I M|l S E. This oracle is implemented via our analysis from the bandit setting.
With the oracle, time step H. can estimate Mf that is e/H close Mj in spectral norm through noisy observations from the reward function with Ö d2 122 /²2 samples. Next, for each time step h = H - H, 1,... 1, sample s P(-|s, a), we define T7. max,' fM (5/, a') Eg--P()ss,a) maxo fM... a')) 8): is mean-zero and -ub-suuggan since is bounded. Denote M, as the matrix that satisfies fM, := Tf which is well-defined due to Bellman completeness.
We estimate Mr from the noisy observations y: (s, a) max. M (5%, a') TS
Th =: fM, + Th. Therefore with the oracle, we can estimate M,, such that [M - M, lll2 S e/H with @ df H²²H²(²² bandits. More details are deferred to Algorithm and the Appendix. We state the theorem on sample complexity of finding e-optimal policy here:
Theorem 3.13. Suppose F is Bellman complete associated with parameter With probability 1 6.
Algorithm 5 learns an c-optimal policy x with T (2) samples.
Existing approaches require (d H2/222 222) trajectories, equivalently H(/21)/22 samples though
they operate in the online RL setting 75 23 41). which is worse by a factor of d.
It is open problem to attain d sample complexity in the online RL setting, The quadratic Bellman complete setting can also be casily extended to any of the polynomial settings of Section 3.3
3.3
Stochastic High-order Homogeneous Polynomial Reward
Next move to homogeneous high-order polynomials.
3.3.1 The symmetric setting
Let reward function be p-th order stochastic polynomial function f A + E, where the action set A : ( {a E Rd ||||| < I.). f(a) Taa @ r f(a) + T/t where T = Σド X,u @p is an orthogonally decomposable rank-k tensor. {u..... ..) form orthonormal basis. Optimal reward nM satisfies 2 ," = X₁ 2 |A2l ... ... |Ael. Noise 7/ ~ (0,
In this setting, the problem is fundamentally more challenging than quadratic reward functions. On the one hand, it has a higher noise-to-signal ratio with larger p. One can tell from the rank-1 setting where T A d For a randomly generated action a on the unit ball, Ellla v [| = 1/d. Therefore on average the signal strength is only (a T ";)² ~ d-p/2, much smaller than the noise level 1. Intuitively this demonstrates why higher complexity is needed for high-order polynomials. On the
8

---

other hand, it is also technically more challenging. Unlike the matrix case, the expected zeroth-order update is no longer equal to any tensor product. Therefore existing tensor decomposition arguments do not apply. Fortunately, we prove that zeroth-order optimization still pushes the iterated actions toward the optimal action with linear convergence, given good initialization. We show the bandit optimization procedure in @gorithmm[jand present the result in Theorem 3.14
Theorem 3.14 (Staged progress). For each stage s. with high probability A, is not empty; and at least one action a E As satisfies: lan a(a, a*) S &.- = 2
We defer the proofs together with formal statements to Appendix [DI.1] and D.I
Remark 3.15 (Choice of step-size). Here we choose step-size Ç 1/2p. Note that Ely] = (lL-))"'Vaaff (a)). The scaling (1- 2 v/ ensures the signal to noise ratio not too small. The choice of weighted action is delicate balance between making progress in optimization and controlling the noise to signal ratio.
Corollary 3.16 (Regret bound for tensors). Algorithm 6 yields an regret of: R(T) S 5
with high probability.
Corollary 3.17 (Regret bound with burn-in period). In Algorithm O we first set E 1/p, nss
(dP/ /2)). We can first estimate the action a such that i 2 1 1- 1/p with (kkd (X?) samples. Next we change
[xf==227] in Algorithm 6 This procedure suffices to find X1e2 -optmml reward with Okdd² /2P=²) samples in the candidate set with size at most Ōkk). Finally with the UCB algorithm altogether we have a regret bound of: Ō kd + vkdT).
and ng
A
In Section 3.3.2 we also demonstrate the necessity of the sample complexity in this burn-in period.
3.3.2 Lower Bounds for Stochastic Polynomial Bandits
In this section we show lower bound for stochastic polynomial bandits.
f(a) = [I a) + n, where ((,, 1a,l I 1 and f(a) S 1.
(I)
8=1
Theorem 3.18. Define minimax regret as follow
T ΣII 10 a0n)
R(d, p,7) = -inf sup Eio.....gg o,)
T mmax II a)
(0.....0p)
1=1 1 T rounds, we have R(d. p. T)> 2
t=
For all algorithms A that adaptively interact with bandit (Eq Q(vdrT/1) /p²).
From the theorem, we can see even when the problem is rank-1, any algorithm incurs at least ((VdTT/pb) /p") regret. This further implies algorithm requires sample complexity of ((d/p2)) 22) to attain e-optimal reward. This means our regret upper bound obtained in Corollary 3.16]is optimal in terms of dependence on d. In Appendix G we also show a ((VdeT) lower bound for asymmetric actions setting, which our upper bound up to poly-logarithmic factors.
We note that with burn-in period, our algorithm also obtains a cumulative regret of kd! / + VRPT. as shown in Corollary (.17] Here for a fixed A and very large T, this is better result than the previous upper bound. We note that there is no contradiction with the lower bound above, since this worst case is achieved with a specific relation between 7 and A1.
The burn-in period requires k:d />/ samples get a constant of r". We want investigate whether our dependence on A = r² is optimal. Next we show a gap-dependent lower bound for finding an arm that is close the optimal arm by constant factor.
Theorem 3.19. For all algorithms A that adaptively interact with bandit (Eq for T rounds and outpul vector (T) E IRd, it requires at least T = a(d /||0|| (2) rounds to find an arm (T) E Bd
such that 11 (0, TaTata (T)) Z - maxx 11 a).
In the rank-1 setting r* = 000P and the lower bound for achieving a constant approximation for the optimal reward is (d( h (2) Therefore our burn-in sample complexity also optimal in the dependence on d and r".

---

3,4 Noiseless Polynomial Reward
In this subsection, we study the regret bounds for learning bandits with noiseless polynomial rewards. First we present the definition of admissible polynomial families.
Definition 3.20 (Admissible Polynomial Family). For E Rd, define ā = [1, a For algebraic variety V - (Rd+1)) define Ry := (re(a) (0, ā @ 0 E V) the polynomial family with parameters in V. We define the dimension of the family Ry as the algebraic dimension of V. Next, define X' a o a E R.). An polynomial family Ry is said to be admissible w.r.t. N' if for any 0 E V, dim(A' n EX EX: (X,0) = 0))) < dim(A') = d.
3.4.1 Upper Bounds via Solving Polynomial Equations
We show that the action set A is of positive measure with respect to the Lebesgue measure μe. then by playing actions randomly, we can uniquely solve for the ground-truth reward function re(a) almost surely with samples of size that scales with the intrinsic algebraic dimension of V. provided that V is an admissible algebraic variety.
Theorem 3.21. Assume that the reward function class an admissible polynomial family Ry, and the maximum reward is upper bounded by 1. If (({A) > O, where μ is the Lebesgue meaure, then by randomly sample actions a1....y QT from IP Pa-N((a. E A), when T 2 2dim(V), we can uniquely solve for the ground-truth 0 and thus determine the optimal action almost surely. Therefore, the cumulative regret round T can be bounded as
R(T) I min(T, 2dim(V)).
We state two important examples of admissible polynomial families with (dd) dimensions.
Example 3.22 (low-rank polynomials). The function class Ry of possibly inhomogeneous degree-p polynomials with & summands Ry {r(a) Σ
--=1 (vi, a)": X; E R. E Rd) is admissible
with dim (Ry) I dk, where = ma Neural network with monomial/polynomiial activation functions are low-rank polynomials.
Example 3.23 (18). The function class Ry (r(a) (Ua)) U kkxd deg q()) $ p} is
admissible with dVm I dk + (k: + 1)P.
4 Conclusion
In this paper, design minimax-optima algorithms for broad class of bandit problems with non-concave rewards. For the stochastic setting, our algorithms and analysis cover the low-rank linear reward setting, bandit eigenvector problem, and homogeneous polynomial reward functions. We improve the best-known regret from prior work and attain the optimal dependence on problem dimension d. Our techniques naturally extend to RL in the generative model settings. Furthermore, we obtain the optimal regret, dependent on the intrinsic algebraic dimension, for general polynomial reward without noise. Our regret bound demonstrates the fundamental limits of UCB algorithms, being (dd=-1) worse than our result for cases of interest.
We leave to future work several directions. First, the gap-free free algorithms for the low-rank linear and bandit eigenvector problem do not attain VT regret. We believe Vd²T regret without any dependence on gap is impossible, but do not have lower bound. Secondly, our study of degree polynomials only covers the noiseless setting or orthogonal tensors with noise. We believe entirely new algorithms are needed for general polynomial bandits to surpass eluder dimension. As a first step, designing optimal algorithms would require understanding the stability of algebraic varieties under noise, we leave this as difficult future problem. Finally, we conjecture our techniques can be used to design optimal algorithms for representation learning in bandits and MDPs 774 39
Acknowledgment
JDL acknowledges support of the ARO under MURI Award 191INF-I1-1-0300 the Sloan Research Fellowship. NSF CCF 2002272, and ONR Young Investigator Award. QL is supported by NSF
'Ituitivelly admissibility means the dimension of X decreases by one when there is an additional linear constraint (0 0
10

---

2030859 and the Computing Research Association for the CIFellows Project. SK acknowledges funding from the NSF Award CCF-1703572 and the ONR award N00014-18-1-2447. The authors would like to thank Qian Yu for numerous conversations regarding the lower bound in Theorem 3.23. JDL would like to thank Yuxin Chen and Anru Zhang for several conversations on tensor power iteration, Simon S. Du and Yangyi Lu for explaining to him to the papers of [43 [55. and Max Simchowitz and Chao Gao for several conversations regarding adaptive lower bounds.
References
[1] Yasin Abbasi- Yadkori, Peter L. Bartlett, and Alan Malek. Linear programming for large-scale Markov decision problems. arXiv preprint arXiv:1402.6763, 2014.
[2] Yasin Yadkor, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In NIPS, volume 11, pages 2312-2320, 2011.
[3] Yasin Abbasi- Yadkori, David Pal, and Csaba Szepesvari. Online-to-comfidence-s conversions and application to sparse stochastic bandits. In Artificial Intelligence and Statistics, pages 1-9. PMLR, 2012.
[4] Alekh Agarwal, Dean P Foster, Daniel Hsu, Sham M Kakade, and Alexander Rakhlin. Stochastic convex optimization with bandit feedback. arXiv preprint arXiv: 1744, 2011.
[5] Alekh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, 2019.
[6] Zeyuan Allen-Zhu and Yuanzhi Li. First efficient convergence for streaming k-pea: a global, gap-freee and near-optimal rate. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 487-492. IEEE, 2017.
[7] Zeyuan Allen-Zhu and Yuanzhi Li. What can resnet learn efficiently, going beyond kernels? arXiv preprint arXiv: 10337,2019,
[8] Animashree Anandkumar, Rong Ge. Daniel Hsu, Sham M Kakade, and Matus Telgarsky. Tensor decompositions for learning latent variable models. Journal of machine learning research, 15:2773 28322, 2014.
[9] Ery Castro, Emmanuel Candes, and Mark Davenport. On the fundamental limits of adaptive sensing. IEEE Transactions Information Theory, 59(1):772-481, 2012.
[10] Yu Bai and Jason D. Lee. Beyond linearization: On quadratic and higher-order approximation of wide neural networks. In International Conference on Learning Representations, 2020.
[11] Maria-Florina Balcan, Simon Shaolei Du, Yining Wang, and Adams Wei Yu. An improved gap-dependency analysis of the noisy power method. In Conference on Learning Theory, pages 284-309. PMLR, 2016.
[12] Jacek Bochnak, Michel Coste. and Marie- Auric-Françoise Roy. Real algebraic geometry, volume 36. Springer Science & Business Media, 2013.
[13] Sebastien Bubeck and Nicolo Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning. 5(1), 2012.
[14] Sébastien Bubeck, Yin Tat Lee, and Ronen Eldan. Gernel-based methods for bandit convex optimization. In Proceedings of the 49th Annual ACM SIGACT Symposium Theory of Computing, pages 72-85, 2017.
[15] T Tony Cai, Xiaodong Li, Zongming Ma. et al. Optimal rates of convergence for noisy sparse phase retrieval via thresholded wirtinger flow. The Annals of Statistics, 44(5):221122511, 2016.
[16] Emmanuel J Candes, Xiaodong Li, and Mahdi Soltanolkotabi. Phase retrieval via wirtinger flow: Theory and algorithms. IEEE Transactions on Information Theory, 61 6144::1885-200 2015.
11

---

[17] Minshuo Chen, Yu Bai, Jason D Lee, Tuo Zhao, Huan Wang, Caiming Xiong, and Richard Socher. Towards understanding hierarchical learning: Benefits of neural representatios Neural Information Processing Systems (NeurIPS), 2020.
[18] Sitan Chen and Raghu Meka. Learning polynomials in few relevant dimensions. In Conference on Learning Theory, pages 1161-1221 PMLR, 2020.
[19] Alex Damian, Tengyu Ma, and Jason Lee. Label noise sgd provably prefers flat global minimiz- ers. arXiv preprint arXiv:2 06530, 2021.
[20] Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. The 21st Annual Conference on Learning Theory, 2008.
[21] Kefan Dong, Jiaqi Yang, and Tengyu Ma. Provable model-based nonlinear bandit and reinforce- ment learning: Shelve optimism, embrace virtual curvature. arXiv preprint arXiv:2 2eXii:2102.000 168, 2021.
[22] Simon S Du, Wei Hu, Sham M Kakade, Jason D Lee, and Qi Lei. Few-shot learning via learning the representation, provably. arXiv preprint arXiv:2002.09434 2020.
[23] Simon S Du, Sham M Kakade, Jason D Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in RL. arXiv preprint arXiv:2103.10889 2021.
[24] Simon S Du, Jason D Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning. pages 1675-1685, 2019.
[25] Cong Fang, Jason Lee, Pengkun Yang, and Tong Zhang. Modeling from features: a mean- ffeld framework for over-parameterized deep neural networks. arXiv preprint arXiv:2007.01452. 2020.
[26] Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex opti- mization in the bandit setting: gradient descent without a gradient. arXiv preprint cs/0408007, 2004.
[27] Ruiqi Gao, Tianle Cai, Haochuan Li, Liwei Wang, Cho-Jui Hsieh, and Jason Lee. Convergence of adversarial training in overparametrized networks. Neural Information Processing Systems (NeurIPS), 2019.
[28] Dan Garber, Elad Hazan, and Tengyu Ma. Online learning of eigenvectors. In International Conference on Machine Learning, pages 560-568. PMLR, 2015.
[29] Rong Ge, Jason D Lee, and Tengyu Ma. Learning one-hidden-layer neural networks with landscape design. International Conference on Learning Representations (ICLR), 2018.
[30] Behrooz Ghorbani, Song Mei, Theodor Misiakiewiez, and Andrea Montanari. Linearized two-layers neural networks in high dimension. arXiv preprint 1rX11:1904.22111, 2019.
[31] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Linearized two-layers neural networks in high dimension. The Annals of Statistics, 49(2):1029-1054, 2021.
[32] Aditya Gopalan, Oddaric-Ammbren Maillard, and Mohammadi Zaki. Low-rank bandits with latent mixtures. arXiv preprint arXiv: 0008000 2016.
[33] Botao Hao, Tor Lattimore, Csaba Szepesvári, and Mengdi Wang. Online sparse reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 316-324. PMLR, 2021.
[34] Botao Hao, Tor Lattimore, and Mengdi Wang. High-dimensional sparse linear bandits. arXiv preprint arXiv:2011.00 04020, 2020.
[35] Botao Hao, Jie Zhou, Zheng Wen, and Will Wei Sun. Low-rank tensor bandits. arXiv preprint 2rXiv:2007.15788 2020.
12

---

[36] Jeff Z. HaoChen, Colin Wei, Jason D. Lee, and Tengyu Ma. Shape matters: Understanding the implicit bias of the noise covariance. arXiv preprint arXiv:2006.08680 08680. 2020.
[37] Moritz Hardt and Eric Price. The noisy power method: meta algorithm with applications. Advances in neural information processing systems, 27:2861-2888 2269,, 2014.
[38] Elad Hazan and Yuanzhi Li. An optimal algorithm for bandit convex optimization. arXiv preprint arXiv: 1603.6660.0000 04350, 2016.
[39] Jiachen Hu, Xiaoyu Chen, Chi Jin, Lihong Li, and Liwei Wang. Near-optimal representation learning for linear bandits and linear rl, 2021.
[40] Arthur Jacot, Clément Hongler, and Franck Gabriel. Neural tangent kernel: Convergence and generalization neural networks. In NeurIPS, 2018.
[41] Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. arXiv preprint arXiv:2102.00815, 2021.
[42] Nicholas Johnson, Vidyashankar Sivakumar, and Arindam Banerjee. Structured stochastic linear bandits, arXiv preprint arXiv:1606. 05603,,,.6,.... 2016
[43] Kwang-Sung Jun, Rebecca Willett, Stephen Wright, and Robert Nowak. Bilinear bandits with low-rank structure. In International Conference on Machine Learming, pages 3163-3172. PMLR, 2019.
[44] Sumeet Katariya, Branislav Kveton, Csaba Szepesvari, Claire Vernade, and Zheng Wen. Stochas- tic rank-1 bandits. In Artificial Intelligence and Statistics, pages 392-401. PMLR, 2017.
[45] Joe Kileel, Matthew Trager, and Joan Bruna. On the expressive power of deep polynomial neural networks. Advances in Neural Information Processing Systems, 32, 2019.
[46] Robert Kleinberg. Nearly tight bounds for the continuum-armed bandit problem. Advances in Neural Information Processing Systems, 17:697-704, 2004.
[47] Wojciech Kotlowski and Gergely Neu, Bandit principal component analysis. In Conference On Learning Theory, pages
PMLR, 2019.
[48] Sahin Lale, Kamyar Azizzadenesheli, Anima Anandkumar, and Babak Hassibi. Stochastic linear bandits with hidden low rank structure. arXiv preprint Nkkiv:9901,0900 2019.
[49] Tor Lattimore. Improved regret for zeroth-order adversarial bandit convex optimisation, 2020.
[50] Tor Lattimore and Botao Hao. Bandit phase retrieval. arXiv preprint arXiv:2106.01660, 2021.
[51] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[52] Guillaume Lecué and Shahar Mendelson. Minimax rate of convergence and the performance of erm in phase recovery. arXiv preprint arXiv:1311.5000 2013.
[53] Lihong Li, Wei Chu, John Langford, and Robert H. Schapire. A contextual-bandi approach to personalized news article recommendation. Proceedings of the 19th international conference on World wide web, pages 661-670 2010.
[54] Yuanzhi Li and Yingyu Liang. Learning overparameterizet neural networks via stochastic gradient descent on structured data. In Advances Neural Information Processing Systems, pages 8157-8166 8166. 2018.
[55] Yangyi Lu, Amirhossein Meisami, and Ambuj Tewari. Low-rank generalized linear bandit problems. In International Conference on Artificial Intelligence and Statistics, pages 460-468.
PMLR, 2021.
[56] James S. Milne. Algebraic geometry (v6.02), 2017. Available at www.jmiine.org/male
[57] Edward Moroshko, Suriya Gunasekar, Blake Woodworth, Jason D Lee, Nathan Srebro, and Daniel Soudry. Implicit bias deep linear classification: Initialization scale vs training accuracy. Neural Information Processing Systems (NeurIPS), 2020.
13

---

[58] Cameron Musco and Christopher Musco. Randomized block krylov methods for stronger and faster upproximate singular value decomposition. arXiv preprint arXiv:1504.05477, 2015.
[59] Mor Shpigel Nacson, Suriya Gunasekar, Jason Lee, Nathan Srebro, and Daniel Soudry. Lexico- graphic and depth-sensitive margins in homogeneous and non-homogeneous deep models. In International Conference on Machine Learning, pages 4683-4692. PMLR, 2019.
[60] Carlos Riquelme, George Tucker, and Jasper Snoek. Deep bayesian bandits showdown: An empirical comparison of bayesian deep networks for thompson sampling, 2018.
[61] Paat Rusmevichientong and John N Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395 2010.
[62] Dan Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. In Advances in Neural Information Processing Systems, pages 2256-2264, 2013.
[63] Maziar Sanjabi, Sina Baharlouei, Meisam Razaviyayn, and Jason D Lee. When does non-orthogonal tensor decomposition have no spurious local minima? arXiv preprint arXiv:1911.09815. 2019.
[64] Igor R Shafarevich. Basic Algebraic Geometry 1: Varieties in Projective Space. Springer Science & Business Media, 2013.
[65] Joel A Tropp. User-friendly tail bounds for sums of random matrices. Foundations of computa- tional mathematics, 12(4))389 434, 2012.
[66] Michal Valko, Nathaniel Korda, Rémi Munos, Ilias Flaounas, and Nelo Cristianini. Finite-time analysis of kernelised contextual bandits. arXiv preprint arXiv:1309.6869, 2013.
[67] Ruosong Wang, Russ R Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 53:6123-6135, 2020.
[68] Xiang Wang, Chenwei Wu, Jason D Lee, Tengyu Ma, and Rong Ge. Beyond lazy training for over-parameterizee tensor decomposition. Neural Information Processing Systems (NeurIPS), 2020.
[69] Yang Wang and Zhiqiang Xu. Generalized phase retrieval: measurement number, matrix recovery and beyond. Applied and Computational Harmonic Analysis, 47(2):423 -46, 2019.
[70] Yining Wang and Animashree Anandkumar. Online and differentially--rivate tensor decompo- sition. arXiv preprint arXiv: 160Xvv:/606.0655 06237, 2016.
[71] Colin Wei, Jason Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets vs their induced kernel. In Advances in Neural Information Processing Systems, pages 9709-9721, 2019.
[72] Blake Woodworth, Suriya Genesekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Kernel and deep regimes in overparametrized models. In Conference on Learning Theory (COLT), 2019.
[73] Pan Xu. Zheng Wen, Handong Zhao, and Quanquan Gu. Neural contextual bandits with deep representation and shallow exploration. arXiv preprint arXiv:20/2.0/7880 2020.
[74] Jiaqi Yang, Wei Hu, Jason Lee, and Simon S Du. Provable benefits of representation learning in linear bandits. arXiv preprint arXiv:2010.06531, 2020.
[75] Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent Bellman error. In International Conference on Machine Learning, 2020.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] Our abstract and introduction accurately reflect our main contribution, which is also summarized in Table [
(b) Did you describe the limitations of your work? [Yes] In the Preliminary section clearly state the settings we considered and when our results apply.
(c) Did you discuss any potential negative societal impacts of your work? [No] Our work theoretical and generally will not have negative social impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] The assump- tions clearly included in every theorem lemma.
(b) Did you include complete proofs of theoretical results? [Yes] All proofs can be found in the appendix
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "Zlcp6NHuXs1", "reviewer": "Reviewer_3PPq", "summary": "The paper studies nonlinear bandit optimization with structured polynomial reward functions, with a focus on the pure exploration setting. The paper proposes some stochastic zeroth-order gradient ascent algorithms with phase elimination and show that they attain minimax sample complexity (in terms of $1/\\epsilon$ and the dimension $d$) for a class of structured polynomial reward functions (i.e., stochastic low-rank linear reward function, stochastic bilinear reward function, stochastic bilinear reward reward function). The sample complexity bounds usually improve upon the bounds obtained via existing techniques (i.e., LinUCB and eluder dimension-based arguments) by a $O(d)$ factor. Combined with matching lower bounds, these results help to reveal the right role of $d$ in the minimax complexity of the considered problems. The paper also shows the suboptimality of UCB algorithms (in terms of $d$) by proving a $\\Omega(d^p)$-type lower bound for UCB in the noise-less polynomial reward case (for which solving polynomial equations usually leads to $O(d)$-type sample complexity).", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "*In the discussion phase, the area chair raised the issue that the presentation of the paper may require some improvement. I agree with this point and add some suggestions at the end of my review.*\n\nThe paper makes important contributions to nonlinear bandit optimization by illustrating the optimality of zeroth order gradient ascent for several natural structured polynomial reward functions. While existing techniques (i.e., LinUCB and eluder dimension-based arguments) are usually able to provide sample complexity that is tight in terms of $1/\\epsilon$, the algorithms and techniques introduced in this paper provide improved sample complexity that is usually better by a $O(d)$ factor. Such improvements also lead to non-trivial consequences for simulator-based RL and phase retrieval. In the noise-less polynomial reward case, the paper gives an interesting result: UCB may suffer from $\\Omega(d^p)$-type sample complexity, while solving polynomial equations may enable $O(d)$-type sample complexity. Overall, the results in this paper may lead to deeper understanding of nonlinear bandit optimization (in the stochastic and pure exploration case).\n\nI have some questions/comments on the paper.\n1. In line 53-54, the authors say that \"Our algorithms are also computationally efficient, bringing more practical advantages.\" However, there is no explicit description of the computational complexity of the algorithm. Can the authors provide such descriptions (even informal)? In particular, a comparison with existing algorithms from a computational perspective would be very helpful.\n2. The shorthand \"NPM\" appears in Table 1 without any explanation, which may cause confusion (I see that there is an explanation under Table 2, but that appears after Table 1).\n3. Table 1 list results in the order of HPS, HPA, B, LL, which is different from the order of presentation. Maybe it is better to make them consistent?\n4. For the case of HPS, one has a gap-dependent bound for even $p$ and a gap-free bound for odd $p$. Can the authors provide some insights on why even $p$ and odd $p$ are fundamentally different? For example, why is it difficult to obtain gap-free bound for even $p$?\n5. Line 214: \"Let ... is defined as:\" should be changed to \"Let ... be defined as:\".\n6. Line 238-239: Can the authors explain why the techniques in this paper can only extended to simulator-based RL? What is the difficulty to extend these techniques to online RL?\n7. Line 255-256: \"We now the bandit optimization procedure\" --- something is missing.\n8. Footnote 1: Why does this footnote appear under Corollary 3.12, but not in a place where this notation first appears?\n9. Section 3.4.1: Is the procedure of solving polynomial equations computationally tractable ? If not, this should be clearly mentioned. Also, how would zeroth order gradient ascent performs in this case? Something needs to be explained here (e.g., how the results can be related to zeroth order gradient ascent); otherwise, Section 3.4 seems quite isolated from other parts.\n\nMoreover, the paper's presentation can be improved. I have the following suggestions.\n1. As some reviewers have pointed out, the paper should spend more time providing high-level intuition at the beginning. The current introduction comes in a very technical way, with many terminologies directly appearing without further explanations (e.g., phase retrieval, eluder dimension). If the authors want to directly use these technical terms at the beginning, then some background of phase retrieval and some intuition on the eluder dimension may be helpful.\n2. The current Section 2 uses a quite non-standard structure --- it merges the problem setting (which is technical) and the paper outline (which needs to be clear and easy to find) together. I am fine with this structure, but is there any way to make it clearer?\n3. The two tables in the paper are difficult to understand without additional efforts. I have pointed out two issues in my review:\n- The shorthand \"NPM\" appears in Table 1 without explanations, which may cause confusion.\n- Table 1 lists results in the order of HPS, HPA, B, LL, which is different from the order of presentation.\n4. Section 3 contain lots of lemmas, theorems, definitions and assumptions. The presentation is split by multiple \"paragraph titles\", which makes the flow fragmented. My personal suggestion is to remove Section 3.2.1 (RL with simulator) from the main text and defer it to the appendix, as it is almost impossible to clearly explain the RL setting (which involves many concepts that require familiarity of the field, e.g., Bellman complete) in such a small space, and the RL setting departs from the nonlinear bandit setting which is more central in the paper. I also find the RL results to be extensions of the bandit results, so I feel that they can be deferred to the appendix.\n5. As another reviewer and I have pointed out, Section 3.4 seems to be quite isolated from other parts in the main paper, and the results are of somehow different favors (the setting is noiseless, and the upper bound is provided by a computational-inefficient polynomial solving procedure rather than gradient ascent). It is also possible to defer this part to the appendix, but I do not have a strong opinion because the results seem to be also interesting.\n\nAfter some removal of non-essential results, the authors should be able to save quite some space, and they can use such space to add clear explanations to their key results, as well as providing more high-level intuition. I hope that the authors can improve the presentation such that readers can better appreciate the theoretical contributions of the paper.\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I have pointed out some places where the authors can make some improvement in terms of presentation.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "SOAHB3LFnf", "reviewer": "Reviewer_FgrR", "summary": "This paper studies the zeroth-order optimization methods for the nonlinear bandit problem. It studies PAC bounds for bandit problems where the reward function is structured polynomials, including a low-rank generalized linear bandit problem and a two-layer neural network with polynomial activations bandit problem. In the low-rank generalized linear bandit setting, the authors provide a minimax optimal algorithm improving the results in [28, 35]. They further apply their algorithms in the RL with the generative model setting, achieving improved sample complexity. In the neural net setting, they propose a bandit algorithm that has sample complexity equal to the intrinsic algebraic dimension. \nThey also show that the standard optimistic algorithms are sub-optimal for both settings.\n", "questions": "", "limitations": "", "rating": 7, "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": "In general, this work is well organized and the results as well as the related comparisons are clearly presented. \n\nThe theoretical contributions of this work are significant. The authors not only provide the near-optimal upper bounds and the lower bounds, but also shows the analysis of the sub-optimality of the optimistic algorithms.  \n\nThe basic idea of this work is based on the noisy power iteration and conversion of the zeroth order information to the function gradient by perturbation noise. However, it is interesting to see that this idea can be applied to the structured nonlinear bandit problem and can further improve the existing results.\n\nCurrently, I do not find any major weakness in this work. There are some minor comments:\n1. The details of the parameter setting are missing in Algorithm 1, which makes it look too simplified. It would be clearer if the authors can move Theorem B.2 to the main text. \n2. In the Line 13 of Algorithm 2, the left half of parenthesis is missing in the equation\n3. Can the authors provide some intuitions or point out the main techniques that lead to the improvement of the existing results in [28,35] by the noisy power iteration?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "Qr-eQEHKvmR", "reviewer": "Reviewer_VuTE", "summary": "This work proposed algorithms based on zeroth-order optimization scheme for structure polynomial reward function in multi armed bandit problems. Solid theoretical results are presented in the paper. \n\n\n", "questions": "", "limitations": "", "rating": 5, "confidence": 1, "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": "This work proposed algorithms based on zeroth-order optimization scheme for structure polynomial reward function in multi armed bandit problems. Solid theoretical results are presented in the paper. \n\nThe paper is difficult to understand. \n\n1.\tIn the contribution statement, the authors say “Rather than looking at the expected regret, we are concerned with the PAC bounds on the sample complexity to identify an _-optimal arm”. Why PAC is adopted instead of expected regret.\n2.\tThe reviewer failed to understand the main results. The reason may be twofold: first, the reviewer has a weak background on this topic; and second, his paper presents many theoretical results, which are lack of explanation. The theoretical analysis may be sound, but the reviewer suggest that the paper present the results from a higher level, or be more concentrated on some main points, so the paper is less heavy and more friendly to the readers.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No  negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "Q-UDMgr0jy", "reviewer": "Reviewer_zjCr", "summary": "This paper studied a fundamental question in non-linear bandit: suppose the mean reward function f_\\theta in the model r_t = f_\\theta(a_t) + noise is non-linear or only linear after some high-dimensional reparametrization of \\theta, is there a good bandit algorithm to find near-optimal policies with sample complexities dictated by the intrinsic dimension? In this paper, the authors investigated the following examples: \n\n1. low-rank linear reward; \n2. bilinear reward (or RL with quadratic Bellman-complete Q-function); \n3. homogeneous polynomial reward; \n4. noiseless polynomial reward. \n\nIn first three examples, the zeroth-order gradient ascent algorithm achieves a PAC sample complexity with the optimal dependence on the dimension d, strictly better than the upper bound given by LinUCB when viewed as a generalized linear model, as well as the eluder dimension argument. In the last example, there is an instance where solving polynomial equations after random sampling only has sample complexity O(d), but any UCB algorithm incurs a sample complexity O(d^p).", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is a really nice paper. In my opinion, the authors look into an important problem in bandits, and obtain satisfactory answers to several important examples. The key message that for non-linear rewards, one can do much better than LinUCB or eluder dimension arguments, is an important addition to the bandit literature, and provides useful tools to study future non-linear bandits. It is also a nice discovery that the zeroth-order gradient ascent could achieve the optimal dimension dependence in several examples. \n\nIf I have to list some limitations: \n\n1. The applicable range of the zeroth-order gradient ascent remains unclear - in the examples where it works, this method typically turns into other known methods such as noisy subspace iteration or power methods. Also, the analysis tools are pretty ad-hoc, so the possibility that this tool is only tailored for specific problems such as sparsity or PCA cannot be ruled out. \n\n2. The noiseless polynomial reward example seems to be disparate from other examples. First the noise-free property is crucial in solving polynomial equations; second only random sampling is needed. Of course this is a really nice example to provably establish the separation compared to UCB, but I am not sure how much intuition is provided here. \n\n3. The dependence of the sample complexity on other parameters (k, \\varepsilon) is often not tight, leaving interesting questions on whether new algorithms should be used. \n\nSome additional comments: \n\n1. An interesting observation is that, in Table 1, the improvement on d compared with the LinUCB/eluder upper bound is always linear in d. I would greatly appreciate it if there is some intuitive explanations. \n\n2. Line 122: argmax should be max. \n\n3. Line 303: I think a factor of p is missing in the characterization of dim(R_V). \n\nPost-rebuttal feedback: \n\nI thank the authors for the response and I also looked at other reviewers' comments. I retain my opinion that this paper is a valuable contribution to the bandit community and studies a fundamental question in contextual bandits, and therefore my ratings. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers are in agreement that this paper provides important fundamental results on non-linear bandit problems.  The only score below the acceptance threshold gives the lowest possible confidence, and was accordingly downweighted to form the final decision.

Despite the general positive assessment, all reviewers agreed that the paper could be quite difficult to read for many readers.  I ask that in the camera-ready version, the authors very carefully incorporate the reviewer suggestions on improving clarity.  Here are some excerpts from the reviewer discussion, in case they were missed in the reviews:
- "the current Section 2 uses a quite non-standard structure --- it merges the problem setting (which is technical) and the paper outline (which needs to be clear and easy to find) together. The notations are also quite complicated"
- "the two tables in the paper are difficult to understand without additional efforts. I have pointed out two issues in my review"
- ", Section 3 contain lots of lemmas, theorems, definitions and assumptions. The presentation is split by multiple "paragraph titles", which makes the flow fragmented"
- "Section 3.4 seems to be quite isolated from other parts in the main paper, and the results are of somehow different favors" [and could be moved to the appendix]
- "After some removal of non-essential results, the authors should be able to save quite some space, and they should use such space to add clear explanations to their key results, as well as providing more high-level intuition."

In addition, based on the reviewer discussion and my own reading, I will mention the following (these are just examples and are far from exhaustive):
- Terms like "eluder dimension" should always be defined clearly.  For terms that are uncommon but not as central to your paper, you can consider defining them in an appendix, and cross-referencing that appendix in the main text.
- Be careful with the consistency of explanations and notation, e.g., Line 146 doesn't quite match Line 8 of Algorithm 1, and T(.) in Algorithm 2 may not have been defined
- Consider adding more citations (and possibly mentioning the main differences) when similar ideas have appeared previously, e.g., phased elimination
- Be careful for English grammar issues, e.g., wording of Theorem 3.13
Decision: Accept (Poster)