Bandit Phase Retrieval
Authors: Tor Lattimore
Botao Hao
Venue: NeurIPS 2021 Poster (2021)
Keywords: Bandit phase retrieval
minimax regret

Abstract: We study a bandit version of phase retrieval where the learner chooses actions $(A_t)_{t=1}^n$ in the $d$-dimensional unit ball and the expected reward is $\langle A_t, \theta_\star \rangle^2$ with $\theta_\star \in \mathbb R^d$ an unknown parameter vector. We prove an upper bound on the minimax cumulative regret in this problem of $\smash{\tilde \Theta(d \sqrt{n})}$, which matches known lower bounds up to logarithmic factors and improves on the best known upper bound by a factor of $\smash{\sqrt{d}}$. We also show that the minimax simple regret is $\smash{\tilde \Theta(d / \sqrt{n})}$ and that this is only achievable by an adaptive algorithm. Our analysis shows that an apparently convincing heuristic for guessing lower bounds can be misleading and that uniform bounds on the information ratio for information-directed sampling (Russo and Van Roy, 2014) are not sufficient for optimal regret.

Bandit Phase Retrieval
Tor Lattimore DeepMind, London lattimore@deepmindd com com
Botao Hao DeepMind, London hacbotao000@gmail. com
Abstract
We study bandit version of phase retrieval where the learner chooses actions (Ar)==1 in the d-dimensional unit ball and the expected reward is (A,, 8.)² with 0. E R.d an unknown parameter vector. We prove an upper bound on the minimax cumulative regret in this problem of (dy/n, which matches known lower bounds up to logarithmic factors and improves on the best known upper bound by a factor of d. We also show that the minimax simple regret is (d/ /r) and that this is only achievable by an adaptive algorithm. Our analysis shows that an apparently convincing heuristic for guessing lower bounds be misleading and that uniform bounds on the information ratio for inffrmmtiiondiiretee sampling [Russo and Van Roy, 2014] are not sufficient for optimal regret.
Introduction
We study an instantiation of the low-rank bandit problem [Jun al., 2019] that in the statistical setting is called phase retrieval. Although this model is interesting in its own right, our main focus is on the curious information structure of this problem and how impacts algorithm design choices. Notably, we were not able to prove optimal regret for standard approaches based on optimism, Thompson sampling or even cnormattiondiieetter sampling. Instead, our algorithm variant of applore-teen-comae with an adaptive exploration phase that learns to gain information at faster rate than what achievable with non-adaptive exploration.
Problem setting Let || be the standard euclidean norm and B = (x E Rd |||||| < r) and ot (Ir E Rd ||ж||| = -r.. At the start of the game the environment secretly chooses vector 0. E S with r [0,1] constant that is known to the learner. The assumption that is known can be relaxed at essentially no cost (Section 8). The game then proceeds over n rounds. In round / the learner chooses an action A, E By and observes a reward
X, (A., +
where (nx)²=1 is sequence of independent standard Gaussian random variables. As is standard bandit problems, the conditional law A, should chosen as a (measurable) function of the previous actions (A,) and rewards (x.)s=l and possibly an exogenous source of randomness. The performance of policy is measured in terms of the expected regret,
Ri (I,, 0.) max E
Σ (l), 0.)² (A.,))))) nr²
E
Σ (A, 0,)2
aE
The minimax regret , supreja.1] inf,, sup,, es! (T, 0.), where the infimum over all policies.
We also study the pure exploration setting, where at the end of the game the learner uses the observed data (A.)__ and (X,)=_ to make prediction A, TB| of the optimal action. The simple regret of
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

policy π is
(T(T,,0) max E (a, (A,,,(A,,)) 03) = -2 [ 0.)2 (x))
aEBf
As expected, the minimax simple regret is = suPrejo.1] inl, suppsestt Fn (T, 0.).
Contributions Our main contribution is an upper bound on R that matches existing lower bounds up to logarithmic factors. For the simple regret we provide near-optimal upper bound and lower bound showing that non non-adaptive policies must be least a factor of S V suboptimal. In all the following, const is universal non-negative constant that may vary from one expression to the next.
Theorem 1. R% I const d log(n) log(d).
A corollary of the proof of the lower bound by Kottowski and Neu [2019] shows that the minimax regret is at least ((dvn), the minimax regret for bandit phase retrieval is now known up to logarithmic factors. For the simple regret we provide the following upper and lower bounds:
Theorem 2. r S const d //og(n) log(d)/n.
Theorem 3. Assume that n 2 d 2 8. Then there exists an r E [0, 1] such that for all policies a with (A))=1 independent of (X+)==1, supo.est-1 [T 8.) 2 const /d/n.
We also show that worst-case bounds on the information ratio for information-dires sampling are sufficient to achieve optimal regret. Our results suggest that the conjectured lower bounds for low-rank bandits [Jun et al., 2019, Lu et al., 2021] are not true and that existing upper bounds may be loose. The same phenomenon may explain the gap between upper and lower bounds for bandit principle component analysis [Kotlowski and Neu, 2019], as we discuss in Section 8.
Notation The first integers are [m] {1, 2, ............ n and the standard basis vectors in Rd are e1...., Cd. The span collection of vectors is denoted by span U1, 2m) and the orthogonal complement of a linear subspace V C IRd is V- {ar E Rd (x,, y) = 0 for all y E Vj. The mutual information between random elements X and Y on the same probability space is [[X; Y) and the relative entropy between probability measures P and Q on the same measurable space is KL(P, Q). The dimension of set O c IRd is defined as the dimension of the affine hull of O.
Related work
The most related work is by Huang al. [2021]. As happens surprisingly often, this is case where multiple groups tackled the same problem and developed similar methods to arrive at approximately the same solution. Their work provides the same upper bound in the cumulative regret setting we do using an explore-then-comme setting consider higher powers. For example, when the reward is (A,,0.)3. What is different is that we use a more ad-hoc (but still interesting) construction during the exploration period and our work is more focussed the information-theorett implications.
principle and the noisy power method. They also generalise the
classical problem signal processing and statistics [Candès et al., 2015b,a, Cai et al., 2016, Chen and Candès, 2017, Chen et al., 2019, Sun et al., 2018]. These works are focused on learning 0, where the covariates (At)i= are uncontrolled, either random or fixed design.
Phase retrieval Phase retrieval
Linear bandits Our problem can be written stochastic linear bandit by noticing that (A,, 0_)² (A.AT, 0,OT), where the inner product between matrices the right-hand side should be interpreted coordinate-wel wise and the action set is {aa linear bandits [Auer, 2002, Dani et al., 2008, Rusmevichientong and Tsitsiklis, 2010b, Chu et al., 2011, Abbasi Yadkori et al., 201 I]. This reduction immediately yields upper bound the minimax regret of ( log(
(B There is enormous literature stochastic
Low-rank bandits Low-rank bandits are a kind of linear bandit where the environment is determined by an unknown matrix and the actions of the learner are also matrices. Let & C dh x and A C Rdi Xd2, A low-rank bandit problem over & and with actions A is characterised by matrix O, E The learner plays actions A, E A and the reward is X, (A,, O.) + 1)t, where 7)2 noise and the inner product between matrices is interpreted coordinate-wise So far this is nothing more than

---

Table 1:
For the low-rank bandits column, p is the rank. We ignore logarithmic factors and universal constant. Note, the dpyn lower bound derived by Lu et al. [2021] does not apply to bandit phase retrieval because it makes use of the richer structure of the more general model.
Upper bounds
Bandit phase retrieval
Low-rank bandits
Pure exploration
Abbasi Yadkori et [2011]
O(dvu)
Old
N/A
Jun et (2019), Lu al. [2021]
O(d% vpm)
N/A
This work
Oldy/)
NIA
Old/ /n)
Lower bounds
(2021]
NIA
Didpyss)
N/A
Kotlowski and Neu [2019)
M(dan
N/A
N/A
This work
NIA
Q(dyn)
1td/ vnj
This work (non-adaptive learning)
N/A
N/A
((d"1+///))
complicated way of defining a linear bandit. The name comes from the fact that in general elements of E are assumed to be low-rank. The precise nature of the problem is determined by assumptions on & and the action set A. Our setup is recovered by assuming that & {xx x S and A {ax]
T E [.
Jun et al. [2019] assume that & consists of rank p matrices and A = {ay x E N.y E y} for some reasonably bounded sets X' C Rdi and y C 12 They prove that the regret is bounded by Ö(d) + dz) /pn). These results cannot be applied directly to the phase retrieval bandit because of the product assumption on the action set. Lu et al. [2021] retain the assumption that & consists of rank-p matrices, but relax the product form of the action set (while also allowing for generalised linear models). Relying only on mild boundedness assumptions, they show that the regret can be bounded by Ö(di, + ) / /pn). For the bandit phase retrieval problem, dj dg d and p 1, so this algorithm yields an upper bound on the regret for bandit phase retrieval of (dd vn). Both Jun et al. [2019] and Lu et al. [2021] conjecture that their upper bounds are optimal. Our results show that this is not true for this sub- bobbrroblem despite the fact that the heuristic argument used by these authors holds in this case, we explain in Section 3. We summarize these comparisons in Table 1.
Some authors use a model where the noise is in the parameter rather than additive, which means the reward is (A,, θ2) with (O.) an independent and identically distributed sequence of low-rank matrices (with unknown distribution). For example, Katariya al. [2017b,a] and Trinh et al. [2020] assume that O is rank-1 almost surely and A = [e:e] 1 < i d}. which means the learner is trying to identify the largest entry in a matrix.
Adversarial setting A similar problem has been studied in the adversarial framework by Kotlowski and Neu [2019]. They assume that (0,)=- is sequence of vectors chosen in secret by an adversary at the start of the game and the learner observes (Ae, 6,) They design an algorithm for which the regret is at most ((d/n), while the best lower bound is Q ddn).
3 Information-theoreti heuristics and information-directed sampling
Jun et al. [2019, $5] argue by comparing the signal to noise ratios between linear and low-rank bandits that the minimax regret for problems like bandit phase retrieval should be lower bounded by /n). We make this argument a little more formal and explain why it does not yield the right answer in this instance. Let À be the uniform (rotational invariant) measure on s and suppose that 0, is sampled from X. The learner takes an action A E B& and observes X = =(A, 0.)2 + 7 with n sampled from standard Gaussian. What is the information gained by the learner? By symmetry, all actions on the unit sphere have the same information gain, so let's 's just fix arbitrary A e s Let
3

---

Po be Gaussian with mean (A, 0) and variance 1. Then,
/ ge
Po (odd
= /
f
Po Pods(o) dd(a)
1(0+;x)= =
KL Po.,
KL Pa. Js
KL (Pa Po) ()
((A,0)² - (A, d)(a)
Dr
11
3
1
(1)
2
d2 +
2d
d2
d2
where the first incquality follows from convexity of the relative entropy. Note that & log(n) bits needed to code 0, to reasonable accuracy. So we presume that the rate of information learned stays the same throughout the learning process, then over n rounds the learner can only obtain O /d²) bits by Eq. (1). By setting ,² d /log(n)/n one could be led believe that the learner cannot identify the optimal direction and the regret would be M(rr") = Mdd V log(n)). The main point is that the rate of information accumulated by careful learner increases over time.
Inforeetion-direetedd sampling The combination of our upper bound and the observation above has an important implication. Suppose as above that 8, is sampled uniformly from 8 and let A be possibly randomised action. Since the learner cannot know the realisation 0, initially, her expected
regret for any action E B is A(a) = r² B( 0_)9] = r2(1 - ||/l3/ /d) 2 r²(1 1/d). On the other hand, as outlined above, the information gain about 0, about r /d Together these results show that the information ratio is bounded by
V A ([A())) = ((d)).
T(e,; X, A)
Since the entropy of a suitable approximation of the optimal action is about log(n)) an application of the information theoretic analysis by Russo and Van Roy [2014] suggests that the Bayesian regret can be bounded by (dd// / log(n)). which is suboptimal. This time the problem is that we have used the worst-case bound on the information ratio, without taking into account the possibility that the information ratio might decrease over time. We should mention here that a decreasing information ratio was exploited by Devraj et al. [2021] in a recent analysis of Thompson sampling for finite-armer bandits, but there the gain was less dramatic (a logarithm of the number of arms) and no changes to the algorithm were required.
4 Algorithm for bandit phase retrieval
We start by showing that Theorem holds if the learner is given an action that is constant-factor optimal. In the next section we explain how such action can be identified with low regret. Our algorithm uses the -pplore-teen-commii design principle, which is usually only sufficient for ( regret. The reason we are able to obtain O(n regret because of the curvature of the action set, property that has been exploited in similar way in variety of settings [Rusmevichientonn and Tsitsiklis, 2010a, Huang et al., 2017, Kirschner et al., 2020].
Theorem 4. Suppose the learner is given an action A. E By such that (Aw, 02)² 2 or² for some universal constant E (0, 1}. Then there exists a policy n for which the regret at most R, (T, 0.) S const -d n log(n).
Proof. By choosing the sign of 0,, assume without loss of generality that (Aw, 0,) 2 rva. Let
Va 2 4
m = 4d n log(())/²* /r2
and A min
If m 2 n, then the regret of any policy is upper bounded nr < const d log(n), so for the rest of the proof we assume that m < n. For the first m rounds the policy cycles over the 2d actions {(1 A, + xeg+ k E [d]) The constrained least squares estimator of 0, based on the data collected over m rounds is
i = arg min [(()) : 0 E B and (Â,, 0) 2 rvat,
(2)

---

where [()) [X= - (A,.
(Xe
For the remaining n m rounds the algorithm plays
A, À 0/1101. Then,
8 _ 9 + d (ogg(9)m)
(3)
m
2
AA, 0 (A,, 0 0aa²
(by Corollary 10)
10.11
m
Σ (Ae, 0 - -0,)²
(4)
a
10.12
m
1)
|10 0,113
2
(5)
2
2d
where in Eq. (4) we used that for some ls E [d].
(A,, 0.) = ((1 - A) + xek, 0 + 0.) 2 (1 - A) + 0.) - All + 0.1l
va
2 2(1 a) - 22r
|0.11
(by definition of X)
2
Eq. (5) follows because for any E {(d].
Σ ()- + σdex, 0 -0.²² = =2(1 (),
0- 0.)² + 2X (ex, 0 0.)²
2 2x2 0 -0,32
which implies that
m
Σ AA, -
2x (x (Ex, 0 0.)²) 2 21²
2d 1) 110 111
2d
Rearranging Eq. (5) and using the definition of shows that
|10 0.13] S a>31
23
d (m)) m mi|00.1 1
I const
28
Letting a, = 0./110.1| be the optimal action, the regret is bounded by
Rt 0.) S ml|0, 12 + +E
(..,0.}² (A, 0.)
= =m|l0, 12 + nE
(a. A, 0,) - A, 0..))
< ml|0.1 12 + 2nl
[100 - A, 0.) [10.1]
I ml|0.1 12 + 4nE
||0_ - 011
(by Lemma 6)
ndd2 log(m)
< m. + const.
const d/ (/nloo))
m 0m|0
Finding a constant-factor optimal action
To establish Theorem we show there exists algorithm that interacts with the bandit for random number of rounds and outputs action A. that with high probability satisfies (Aw: 0_)² 2 2 /64. Furthermore, the procedure suffers small regret in expectation.
Theorem 5.
be the random number of rounds that Algorithm interacts with the bandit, which cannot more than n, and let An ES--1 be its output. Then,
& 1. [T < const f log(n) log(d).
2. With probability at least 1 1/n, either T = (Aw, 0.),,, 2 69.
5

---

-=
r/va and m = y log (2n²)
do
3 sample v uniformly from 81 gd-1
4 play A for m rounds and compute average reward X
5 loop until 2
= [uVX}
for h 2 to d
3 9 log(n)) and 64d
and Ewee
by
12 w
do
10
sample v uniformly from (pan(E)-ns))
play Ar (u- for 3m rounds find least squares estimator 0 constrained B loop until (1,0)22+* 14
11
12
13
E 0)
15
if Ewee ||w||2 2 1/116 break
end for 16
17
return Av
Ewee" a Twue w1
The procedure operates in d iterations. The first iteration is implemented Lines 1-5 and the remaining 1 iterations in Lines 7-15.
Algorithm 1:
What is interesting about Algorithm 1 is that it uses what it has learned in early iterations to increase the statistical efficiency of its estimation.
Proof. Note that the vectors u and computed in each iteration are orthogonal, which means that [[ + v)/v21 = [1( v) /)/v2 ||a|| 1. Hence the actions of the algorithm are always in By The main argument of the proof is based on an induction to show that with high probability when the exccution of the algorithm ends, there exists
{+1} such that for all E,
(a) w E E, ||li| 2 r2 and (b) s(w, 0-) [ || [|3]
We proceed in five steps. First, prove that if the above holds and the algorithm halts before rounds are over, then the vector returned suitable approximation 0./||0,]| Second, we upper bound the probability of certain bad events. In the third and fourth steps prove the base case and induction step for (a) and (b). In the last step we bound the expected running time.
Step 1: Correctness Suppose that (a) and (b) above hold and the algorithm halts at the end of iteration k. Then,
(
Σ Ewec 0, ( w|l'
0.)²
|
64
ME
where the first inequality follows from orthogonality of w E E and (b) above. The second inequality follows from the stopping condition in Line 15 of Algorithm 1, (a) above and the definition of т. Part (2) of the theorem follows by showing that (a) and (b) above hold with probability at least 1/n.
Step Failure events The algorithm computes some kind estimator the end each do/loop. Since the algorithm cannot play more than n actions, the number of estimators computed is naively upper bounded by n. union bound over all estimates and the concentration bounds in Lemma and Corollary 10 show that with probability at least 1 1/n the following both hold:

---

For all e sampled in the first iteration and corresponding average rewards X,
2 (2g(
7² 2
[X - (u,
(6)
m
where m is defined in Line Algorithm
1.
Let D (Ag)s be the actions played in the inner loop of some iteration & 2 2 and & be the corresponding least-squares estimator. Then,
Σ (a.0 (a) 0 0,)² 9log((98) log(n)) - B.
We assume both of the above hold in all relevant iterations for the remainder.
Step 3: Base case The step is show that (a) and (b) hold with high probability after the first iteration. Consider the operation of the algorithm in the inner loop. After sampling E 8 the algorithm plays for m rounds and computes the average reward. Let v be the last sampled action before the iteration halts and vv By the stopping condition in Line 5, ||w]|² = X 2 x3. Without loss of generality, we choose the sign of 0, so that (ve, 0.) 2 0. Then by Eq. (6),
(w, 0.) = V X (v,0.) E
W 1 2
2
This establishes the base case.
Step 4: Inductive step Assume that (a) and (b) above hold for at the end of iteration k. Let u be the value computed in Line 8 of Algorithm 1. Then,
E (w, 0.) 1
TVK 2
(u, (,)
V wEe |
21
WEE
Let A = {(u + v)/ (u 1- v)/ v}, which is the set of actions played in the inner loop of iteration k + after sampling for the last time. Let 0 be the corresponding least-squares estimate. We consider cases. First, if (u, 0 0.) 2 (v, 0.)l, then by Eq. (7),
B
>
(a, 0. (a, 0- 02
aEA
(u + 0, - ( 0,) + (u v,0, ( 0,)²
16
16
1
2r
(u, -) 0.)² >
{v, 0. 0)2
8
16d
Rearranging shows that
16d3 72 mkr
0, 0)2 <
<
(8)
4
For the second case, (u, 0 + 0.) < (v, + 0.)l Then,
3
Σ (a, 0, -,, 0)2 > 7 (v, 0 aEA
1
0.)
kr 8d {v. 02 -
And again, Eq. (8) holds. Summarising, (v, 0} is an estimator of (v. 0.) up to accuracy 7/2. By the definition of the algorithm, the iteration only ends if Kv, 0)1 2 r. Therefore, with = (v. 0)v, we have || (u, 0)2 ? Furthermore, (w, 0.) (v, (v. 0.) [|| 2 /2, ||] Therefore if
(a) and (b) hold for computed after iteration k. they also hold for computed after iteration + 1.
Step 5: Running time The length of an iteration is determined by the corresponding value of m and the number of samples of v. The former is an iteration veration-dependent constant, while the latter depends principally on how many samples needed before (c, 0.)l is suitably large. The law of is the
7

---

uniform distribution on $i 1 (E) which is the uniform distribution on sphere of dimension d - 1 [8] embedded in RR The squared norm of the projection of 0, onto span(E) is
(0+: w)
r²
|10.11
||0||
WEE
WEE
where we used (a) of the induction and the stopping condition in Line 15. Therefore, when is sampled uniformly from S n span(E)+ by Lemma 8,
3r2
0l), 37 (2) (v, (,,
const > 0,
2d
Furthermore, by the concentration analysis in the previous step, an iteration will end once a v has been sampled for which 0.)2 2 //. Hence, the expected number of times the algorithm samples e per iteration is constant and a simple calculation using the definition of m in Lines and shows that the expected number of rounds used by the algorithm is most
d² S const ,
log (n) log(d).
6 Proof of Theorem and Theorem 2
Proof of Theorem I. Run Algorithm 1 and halts, feed the returned action to the input of the explore-then-cone thencmmmie algorithm analysed in Theorem Algorithm 1 fails to return suitable action with probability at most 1 I/n, so the contribution of this event to the regret is negligihle. By Theorem 5, the regret incurred by Algorithm 1 is bounded by
T
E
(r2 Σ 1=1
(A),
< E
I min nr² const & f log(d) log(n)
S const d log log(n).
Combining this with the regret bound established in Theorem yields the result.
Proof of Theorem 2. We standard reduction [Lattimore and Szepesvári, 2020, Chapter 33]. Let be the policy used in the proof of Theorem with A, sampled uniformly from (A))_ By Theorem 1,
Rr (T, 0.) const d log(n) log(d)
(T, 0.)
nr²
E
(A,, 0.)
7 Proof of Theorem 3
Let æ be a fixed policy and for Id let IPy be the measure on sequence of outcomes H, (Ai, XI,..., Xn,) induced by the interaction between and the phase retrieval model determined by 0. Let IE, denote subsequently and be the uniform (Haar) measure S -p--_ Let Q f Pe (0) be the Bayesian
expectation with respect to PP.. Let r be positive constant to tuned
mixture measure. For 0 IRd let Eg be the event given
Eg 0) 2
3 2
By Fano's incquality [Gerchinovitz et al., 2020, Lemma 5].
f 1- Po(E6) Po(Es)do do < log 2 + Sag KL(Pe, Q)) (o
(9)
log (Se-- Q(Ea) do)

---

We now bound the numerator and denominator in Eq. (9) to show that the right-hand side is at most 1/2 and then complete the proof using the definition of the regret and Eg.
Step I: Bounding the denominator in Eq. (9) By exchanging the order of integrals the denomi- nator of Eq. (9), it follows that
-log ( ((E)) -log log lc, do dQ
(10)
U sampled uniformly from si-1 then by a concentration bound for spherical measures [Dasgupta and Gupta, 2003, Lemma 2.2].
P (UP 2 5/d) I exp(-6/4) for all 5 > 6.
By scaling and rotating and choosing 5 = d.., it follows that for any A, E By,
Set.. (1), do S e-p3-3d/100
3r
Therefore, by Eq. (10),
log Q(E,) (((()))(()))
3d
16
Step 2: Bounding the numerator in Eq. (9) By the convexity Kl.diieegeece,
KL(Pe, Q) do) = KL
Po.
Fa dor(a) do
KL
(o)
By the chain rule of KL-diiergence,
KL (Po, P.) = Eg
-LL -1AA))
A straightforward computation leads to
((AT0) (AT
KL (PPo = EEg
1=1
aa) +4TTa))
Eg
1=1
Since (A:) are independent of (X.) we can interchange the expectation and integral such that
KI.(Po, Q)) do)
Σ 1=1
E
2(4T0))(AT ((400))) + (ATa)) + da du(o))
where the expectation is with respect (A,) which does not depend 0 by assumption. When 0 is uniformly on S and A B is arbitrary.
[ (A 0)
3
and fec (A,
1
d2 + 2d
d2
where the expectation is taken with respect to 0. Therefore,
(L Q) (o) < 3nr
(11)
sd
d²

---

Step 3: Lower bounding the regret Let /d (32m) Combining the previous two steps shows that
16nr Po(Eg) do -
d3
2
Therefore there exists a 0 E 8 with Po(Es) s 1/2. which implies that
d/2
(T =r² Eo (A,, 0/2]
const
Vn
8
Discussion
Unknown radius The assumption that r = ||0_1| is known to the learner easily relaxed by estimat- ing ||0_||- Note first that all our analysis holds with only trivial modifications if [ 00 ||0+ II]- Next, if A is sampled uniformly from Si gd-1 and = ( A, 02)2 + y and is a standard Gaussian, then 2(d - ()/(P 2 @(1). Therefore ||+|| can be estimated to within an arbitrary multiplicative factor and at confidence level - 1/n using const de /|10, I| log(n) interactions with the bandit.
E[X] 2110_ 2|2 and V[x]=
Computation complexity The only computational challenge is finding the least squares estimates, which is non-convex optimisation problem. Candès et al. [2015b] proposed Wirtinger flow algorithm that starts with a spectral initialization, and then refines this initial estimate using local update like gradient descent. The computational complexity of the Wirtinger flow algorithm with e-accuracy is (ndd log(1/e)) where n is the number of samples.
Adversarial setting Kotlowski and Neu [2019] study the adversarial version of this problem, where the learner observes (A,, 0,)² and (0,)²_ is an adversarially sequence with 0, E IB for all t. They prove upper bound of Ri (d log(n)) and lower bound of 12( dn). Natural attempts at improving the lower bound all fail. believe that the upper bound is loose, but proving this remains delicate. No warm starting procedure will work anymore because the information gained may be useless in the presence of a change point. New ideas are needed.
Rank-p Perhaps the most natural open question is whether or not our analysis can be extended to the low rank bandit problem without our particular assumptions on the action set and environments matrices.
Principled algorithms Can optimism information-directed sampling be made work? The main challenge is to understand the sample paths of these algoritms before learning takes place.
References
Y. Abbasi-Yadkori, D. Pál, and Cs. Szepesvári. Improved algorithms for linear stochastic bandits, In Advances in Neural Information Processing Systems, pages 2312-2320, 2011.
P. Auer. Using confidence bounds for exploitation-exxlorrtion trade-offs. Journal of Machine Learning Research, 3(Nov):397-422 2002.
S. Boucheron, G. Lugosi, and P. Massart, Concentration inequalities: A nonasymptotic theory of independence. OUP Oxford, 2013.
T. Cai, X. Li, and Z. Ma. Optimal rates of convergence for noisy sparse phase retrieval via thresholded wirtinger flow. The Annals of Statistics, 44(5):2221-225)) 2016.
E. J. Candès, Y. C. Eldar, T. Strohmer, and Voroninski. Phase retricval via matrix completion. SIAM review, 57(2):225-21,, 2015a.
E. J. Candès, X. Li, and M. Soltanolkotabi. Phase retrieval via Wirtinger flow: Theory and algorithms. IEEE Transactions Information Theory, 6184 2015b.
Y. Chen and E. J. Candès. Solving random quadratic systems of equations nearly as easy as solving linear systems. Communications on pure and applied mathematics, 70(5):822-888 2017.
10

---

Y. Chen, Y. Chi, J. Fan, and C. Ma. Gradient descent with random initialization: Fast global convergence for nonconvex phase retrieval. Mathematical Programming. 176(1):5-37, 2019.
W. Chu, L. Li, L. Reyzin, and R. Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statisties, pages 208-22 214, 2011.
Dani, T. Hayes, and Kakade. Stochastic linear optimization under bandit feedback. 2008.
S. Dasgupta and A. Gupta. An elementary proof of a theorem of johnson and lindenstrauss. Random Structures & Algorithms, 22(1) (2(1):60-66 2003.
A. M. Devraj, B. Van Roy, and K. Xu. A bit better? quantifying information for bandit learning. arXiv preprint arX1v:2102.09488 2021.
S. Gerchinovitz, P. Ménard, and G. Stoltz. Fano's inequality for random variables. Statistical Science, 35(2):178-25) 2018 2020.
B. Huang, K. Huang, S. Kakade, J. Lee, Q. Lei, R. Wang, and J. Yang. Optimal gradient- based algorithms for non-concave bandit optimization. arXiv preprint arXiv:2107.04511 045188 2021.
R. Huang, T. Lattimore, A. György, and Cs. Szepesvári. Following the leader and fast rates in online linear prediction: Curved constraint sets and other regularities. Journal of Machine Learning Research, 18:1-31, 2017.
K-S Jun, R. Willett, S. Wright, and R. Nowak. Bilinear bandits with low-rank structure. In International Conference Machine Learning, pages 3163-3172 PMLR, 2019.
S. Katariya, B. Kveton, Cs. Szepesvári, C. Vernade, and Z. Wen. Bernoulli rank-1 bandits for click feedback. In Proceedings of the 26th International Joint Conference on Artificial Intelligence, pages 2001-2007, 2017a.
S. Katariya, B. Kveton, Cs. Szepesvári, C. Vernade, and Z. Wen. Stochastic rank-1 bandits. In Artificial Intelligence and Statistics, pages 392-401. PMLR, 2017b.
Kirsehner, T. Lattimore, and A. Krause. Information directed sampling for linear partial monitoring. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learming Research, pages 2328-2369. PMLR, 2020.
W. Kotlowski and G. Neu. Bandit principal component analysis. Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Secone Conference on Learning Theory. volume 99 of Proceedings of Machine Learning Research, pages 1994-2024, Phoenix, USA, 25-28 Jun 2019. PMLR.
Lattimore and Cs. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
B. Laurent and P. Massart. Adaptive estimation of a quadratic functional by model selection. Annals of Statistics, pages 1302-1338, 2000.
Y. Lu, A. Meisami, and A. Tewari. Low-rank generalized linear bandit problems. In International Conference on Artificial Intelligence and Statistics, pages 460-468. PMLR, 2021.
P. Rusmevichientong and N. Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395-411 2010a.
P. Rusmevichientong and N. Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 3512):395-411, 2010b.
D. Russo and B. Van Roy. Learning to optimize via information-direeted sampling. In Advances in Neural Information Processing Systems, pages 1583-1591. Curran Associates, Inc., 2014.
Ju Sun, Qing Qu, and John Wright. A geometric analysis of phase retrieval. Foundations of Computational Mathematics, 18(5):1131 131-11988.11.11 2018.
C. Trinh, E. Kaufmann, C. Vernade, and R. Combes. Solving bernoulli rank-one bandits with unimodal thompson sampling. 31st International Conference on Algorithmic Learning Theory, pages 1-28, 2020.


Reviews:
[{"review_id": "brYyWo48Df", "reviewer": "Reviewer_gkvs", "summary": "The paper studies a stochastic bandit optimization problem in which the expected reward can be expressed as $\\langle a , \\theta_\\star \\rangle^2$,\nwhere $\\theta_\\star$ is an unknown parameter.\nThe authors provides an algorithm that achieve a nearly tight (up to logarithmic factors) cumulative regret bounds.\nNearly tight bounds for simple regret have been shown as well.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: \n\nThe problem formulation is not very original because it is a special case of existing study,\ne.g.,\nlinear bandits [APS11] and Bilinear bandits [JWWN19].\nThe proposed algorithm is based on the well-known explore-then-commit framework.\nOn the other hand,\nthe analysis contains non-trivial arguments in contrast to the standard analysis in the explore-then-commit framework, \nwhich play an important role in achieving $O(\\sqrt{n})$-regret.\n\nI am a little skeptical that the lower bound (Theorem 2) is really a new result\nas the proof of Theorem 8 in [KN19] provides $\\Omega(d \\sqrt{n / \\log n})$ lower bounds \nwith stochastic losses expressed by a rank-1 matrix plus a noise term.\nI guess that the models w.r.t.~noise are slightly different.\nI would appreciate it if the authors could explain if there is an intrinsic difference.\n\n\n\nQuality: \n\nAs far as I can see, no technical errors have been found.\nI think the authors are careful and honest about evaluating both the strengths and weaknesses of their work.\n\nClarity:\n\nThe main part of the paper is clearly written.\nOne thing that was not clear to me was the relationship between this study and the existing studies [KN19] on the adversarial model.\nCan the former be considered a special case of the latter?\n\nThe proof of Lemma 7 could not be found in the cited literature.\nIt would be nice to have more explicit pointers (I don't doubt the correctness of the claim).\n\nSignificance:\n\nAs the authors argue in Section 3, an analogy based on some existing studies suggests that the tight bound would be $\\sim O(d^{3/2} \\sqrt{n})$.\nTherefore,\nI think that the proved bound of $\\tilde{\\Theta}( d\\sqrt{n} )$ is surprising and has a certain impact on the research community on bandit algorithms.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think limitations and societal impact have been well discussed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "QaNA6IHKO3x", "reviewer": "Reviewer_3qPJ", "summary": "This paper studies the phase retrieval problem under bandit feedback. Regret bounds for this problem can be obtained from prior work by casting the problem as a low-rank bandit, which yields a $\\tilde{O}(d^{3/2} \\sqrt{n})$ regret upper bound. While several authors have conjectured that the upper bound for low-rank bandits is tight using information-theoretic heuristics, and these heuristics carry over also to the phase retrieval setting, this paper shows that these heuristics can be quite misleading. Indeed, this paper proves that the optimal regret for this setting is $\\Theta(d \\sqrt{n})$ (providing matching upper and lower bounds on the regret), which they obtain by ensuring that their algorithm can _increase_ the rate of information accumulated over time (thus circumventing the information-theoretic heuristics of prior works).\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I quite enjoyed both the results and the presentation of this paper.  The authors spend a significant portion of the paper devoted to discussing what is known about the bandit phase retrieval problem from prior work, and even sketch some heuristic arguments that were present in prior works, and why these arguments fail to give the correct answer in this setting. I found this discussion very enjoyable. The discussion here seems quite related to the separation in sample complexity between adaptive and non-adaptive algorithms for sparse recovery (see, e.g., “On the power of adaptivity in sparse recovery” by Indyk-Price-Woodruff in FOCS'11). It seems to me (at least at a high level), the reasons that the information-theoretic arguments for the phase retrieval setting fail are effectively the same reason why adaptive algorithms perform better in the sparse recovery setting. Perhaps this could be an additional discussion point in this section.\n\nRegarding the analysis of the algorithm, I found the overall organization and flow to be relatively easy to follow. However, I think that adding some text explaining some intuition behind some of the steps involved in the proofs would improve the readability. For instance, (i) in the text preceding Theorem 5 (l.  124-125), the authors mention that they obtain $O(\\sqrt{n})$ instead of $O(n^{2/3})$ scaling due to the curvature of the action set. As I understand it, I believe this is essentially lines 139-141, but it would be quite useful if the authors could highlight this in their analysis, and perhaps mention what would happen if the action set did not have the nice structure.  Additionally, (ii) a point that I found slightly subtle in the analysis, and perhaps could be useful to clarify, is that the result of Theorem 5 needs to hold _conditioned_ on the output of Algorithm 1 returning a good solution. This conditioning does not affect the application of Corollary 11 in the proof of Theorem 5, since the bandit feedback ensures the noise at each round is independent of the past. I suppose this is also a reason not to expect these ideas to carry over easily to the adversarial setting.\n\nIn summary, I think this paper would be a very nice addition to this year's conference. The ideas are interesting and somewhat surprising, the analysis is fairly simple, and the results are presented, for the most part, quite well.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, adequately addressed.\n", "review_text": "", "extra_scores": {"ethical_concerns": "No\n", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "I2mqArqeQrv", "reviewer": "Reviewer_fRir", "summary": "\nThe paper studies the quadratic bandit problem, where the reward at time $t$ is given by $\\langle \\theta_\\star, a_t \\rangle^2 + \\varepsilon_t$, where $\\varepsilon_t$ is i.i.d. gaussian noise, $\\theta_\\star$ is an unknown $d$-dimensional vector and $a$ is the action. The action set is fixed to be the unit ball, and the learner can choose any action $a_t \\in \\mathbb R^d$ such that $\\lVert a_t \\rVert_2 \\le 1$. The norm of the unknown vector $\\lVert \\theta_\\star \\rVert$ is revealed to the learner at the beginning of the bandit. (This assumption can be removed, as discussed in the final section.) The main contributions are as follows.\n\n1. The paper proves tight up to log factors upper and lower regret bounds $\\tilde{\\Theta}(d \\sqrt n)$ for the quadratic bandit problem (Theorems 1, 2, respectively).\n2. The paper extends the regret results to the pure exploration settings (Theorem 3).\n3. The paper suggests that optimal regret is not attainable by fixed policies (Theorem 4).\n\nThe paper concludes that standard algorithms in bandits literature, including UCB, Thompson sampling, and information-directed sampling, might be insufficient for the quadratic bandit. Furthermore, the paper refutes previous regret lower bound conjecture, suggesting that naive guess based on signal-to-noise (SNR) ratio is wrong. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nBandit with non-linear rewards is attracting increasing interests from the research society of bandits and RL, partly due to its close connection to deep RL. However, current research in this direction is quite limited. This paper studies the simplest task, namely the quadratic bandit, and gives near-optimal regret analyses. The paper conveys the important message that standard optimistic algorithms might be insufficient for quadratic bandit, and discovers the unusual fact that the SNR ratio might vary, and successfully exploits this fact to derive a near-optimal algorithm. \n\nThe paper designs a novel algorithm, which is a combination of a novel initialization stage (Alg. 1) ahead of the classical Explore-Then-Commit algorithm, to achieve optimal regret. The paper is well-written and the proofs are easy to follow. The authors are honest about their weakness about their results in the final section. However, I have some concerns on the paper. First, the related works might have been cited adequately, but the authors could have done better comparing with them. Second, there is a concurrent paper that covers many of the results in this paper. I vote for a weak reject.\n\n---\n\nThe concurrent paper shall not be a concern. After discussion I would raise my vote to accept.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "### Limitations\n\n1. The recent paper [1] studies the more general tensor bandit, where the reward function can be more general low-rank p-tensors. In particular, the $p=2$ case in [1] seems cover the main contributions (Theorem 1-3) in this paper. Besides, Algs. 1 and 2 in [1] look quite similar to Alg. 1 in the submission, but the ones in [1] are much more general. For example, the ones in [1] can solve general $\\langle \\theta_\\star, a_t \\rangle^p$ reward, while the submission only studies $\\langle \\theta_\\star, a_t \\rangle^2$. The authors may need to compare their results with those in [1]. \n2. The lower bound (Theorem 2) seems to be the same as [2, Theorem 6] by putting $r=1$. The authors might need to point it out more explicitly, and it would be strange to list it as a contribution.\n\n### Other Comments\n\n1. Line 72, what is $xx$?\n2. At Line 125, the idea of using curvature to obtain sqrt regret for ETC could date back to even earlier papers, such as [3].\n\n\n### Societal Impact\n\nThe paper is mainly theoretical, and I don't see any potential negative societal impact.\n\n### Bibliography\n\n[1] Huang, Baihe, Kaixuan Huang, Sham M. Kakade, Jason D. Lee, Qi Lei, Runzhe Wang, and Jiaqi Yang. \"Optimal Gradient-based Algorithms for Non-concave Bandit Optimization.\" arXiv preprint arXiv:2107.04518 (2021).\n\n[2] Lu, Yangyi, Amirhossein Meisami, and Ambuj Tewari. \"Low-rank generalized linear bandit problems.\" In International Conference on Artificial Intelligence and Statistics, pp. 460-468. PMLR, 2021.\n\n[3] Rusmevichientong, Paat, and John N. Tsitsiklis. \"Linearly parameterized bandits.\" Mathematics of Operations Research 35, no. 2 (2010): 395-411.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "9QRHcStJXRi", "reviewer": "Reviewer_A8GD", "summary": "This paper studied the bandit phase retrieval problem that can also be framed as a low-rank bandit problem where the actions and the unknown coefficient are rank-1 matrices. Their algorithm achieves a \\tilde{O}(d\\sqrt{n}) regret that matches their lower bound result up to log factors. By a simple conversion, they prove a \\tilde{O}(d/\\sqrt{n}) simple regret and show this can only be achieved by adaptive algorithms.", "questions": "", "limitations": "", "rating": 7, "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 paper has strong theoretical results. \nFor low rank bandit problems (rank-1 action space and rank-1 unknown coefficient), they first develop an algorithm achieving \\sqrt{T} regret that is only linear in d. Comparing to the results in Jun et. al and Lu et. al, their regret improves by a factor of \\sqrt{d}. Their approach is also novel. But I don't think the author can claim the conjectured lower bounds in Jun et. al and Lu et. al are not true based on their \\tilde{O}(d\\sqrt{n}) regret upper bound. Because in both works of Jun et. al and Lu et. al, actions either have higher ranks or the action space doesn't have to be an exact Euclidean ball, which means their settings are more general and may have larger lower bounds. \n\nI suggest the author re-write Section 3, include explanations for your arguments. Currently it's not easy to understand for people outside of non-information theory. \n\nMinor comments:\n1. equation below line 25: should be nr^2, not r^2\n2. line 72: xx^T\n3. equation below line 100: I(\\theta_*; X)\n\nOverall I think the theoretical contribution is strong and I recommend an acceptance.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the bandit phase retrieval problem and establishes a sharp minimax regret bound of d\sqrt{n}, which improves on previous  work based on low rank bandit approaches. The proof is enlightening and the paper is well-written, making nice connections to related work. All reviewers were positive on the paper, and so we advocate acceptance. 

As I mentioned in our discussion, I do think it would be worthwhile to add some discussion of the recent/concurrent paper of Huang et al to the final manuscript. 
Decision: Accept (Poster)