Bandit Phase Retrieval
Year: 2022

Abstract:
We study a bandit version of phase retrieval where the learner chooses actions (At)t=1 in the d-dimensional unit ball and the expected reward is hAt, ✓?i with ✓? 2 Rd an unknown parameter vector. We prove an upper bound on the minimax cumulative regret in this problem of ⇥̃(d p n), which matches known lower bounds up to logarithmic factors and improves on the best known upper bound by a factor of p d. We also show that the minimax simple regret is ⇥̃(d/ p 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.

text: p n), which matches known lower bounds
up to logarithmic factors and improves on the best known upper bound by a factor of p d. We also show that the minimax simple regret is ⇥̃(d/ p 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.

heading: 1 Introduction
text: We study an instantiation of the low-rank bandit problem [Jun et 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 it impacts algorithm design choices. Notably, we were not able to prove optimal regret for standard approaches based on optimism, Thompson sampling or even information-directed sampling. Instead, our algorithm is a variant of explore-then-commit with an adaptive exploration phase that learns to gain information at a faster rate than what is achievable with non-adaptive exploration.
Problem setting Let k · k be the standard euclidean norm and Bdr = {x 2 Rd : kxk  r} and Sd 1r = {x 2 Rd : kxk = r}. At the start of the game the environment secretly chooses a vector ✓? 2 Sd 1r with r 2 [0, 1] a constant that is known to the learner. The assumption that r is known can be relaxed at essentially no cost (Section 8). The game then proceeds over n rounds. In round t the learner chooses an action At 2 Bd1 and observes a reward
Xt = hAt, ✓?i2 + ⌘t ,
where (⌘t)nt=1 is a sequence of independent standard Gaussian random variables. As is standard in bandit problems, the conditional law of At should be chosen as a (measurable) function of the previous actions (As)t 1s=1 and rewards (Xs) t 1 s=1 and possibly an exogenous source of randomness. The performance of a policy ⇡ is measured in terms of the expected regret,
Rn(⇡, ✓?) = max a2Bd1
E " nX
t=1
ha, ✓?i2 hAt, ✓?i2 # = nr2 E " nX
t=1
hAt, ✓?i2 # .
The minimax regret is R?n = supr2[0,1] inf⇡ sup✓?2Sd 1r Rn(⇡, ✓?), where the infimum is over all policies.
We also study the pure exploration setting, where at the end of the game the learner uses the observed data (At)nt=1 and (Xt)nt=1 to make a prediction bA? 2 Bd1 of the optimal action. The simple regret of
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
policy ⇡ is
rn(⇡, ✓?) = max a2Bd1
E h ha, ✓?i2 h bA?, ✓?i2 i = r2 E h h bA?, ✓?i2 i .
As expected, the minimax simple regret is r?n = supr2[0,1] inf⇡ sup✓?2Sd 1r rn(⇡, ✓?).
Contributions Our main contribution is an upper bound on R?n that matches existing lower bounds up to logarithmic factors. For the simple regret we provide a near-optimal upper bound and a lower bound showing that non-adaptive policies must be at least a factor of ⌦( p d) suboptimal. In all of the following, const is a universal non-negative constant that may vary from one expression to the next. Theorem 1. R?n  const d p n log(n) log(d).
A corollary of the proof of the lower bound by Kotłowski and Neu [2019] shows that the minimax regret is at least ⌦(d p n), so 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?n  const d p log(n) log(d)/n.
Theorem 3. Assume that n d 8. Then there exists an r 2 [0, 1] such that for all policies ⇡ with (At)nt=1 independent of (Xt) n t=1, sup✓?2Sd 1r rn(⇡, ✓?) const p d3/n.
We also show that worst-case bounds on the information ratio for information-directed sampling are not 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 [Kotłowski and Neu, 2019], as we discuss in Section 8.
Notation The first n integers are [n] = {1, 2, . . . , n} and the standard basis vectors in Rd are e1, . . . , ed. The span of a collection of vectors is denoted by span(v1, . . . , vm) and the orthogonal complement of a linear subspace V ⇢ Rd is V ? = {x 2 Rd : hx, yi = 0 for all y 2 V }. The mutual information between random elements X and Y on the same probability space is I(X;Y ) and the relative entropy between probability measures P and Q on the same measurable space is KL(P,Q). The dimension of a set ⇥ ⇢ Rd is defined as the dimension of the affine hull of ⇥.

heading: 2 Related work
text: The most related work is by Huang et al. [2021]. As happens surprisingly often, this is a 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 as we do using an explore-then-commit principle and the noisy power method. They also generalise the setting to consider higher powers. For example, when the reward is hAt, ✓?i3. 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 on the information-theoretic implications.
Phase retrieval Phase retrieval is a classical problem in 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 ✓? where the covariates (At)nt=1 are uncontrolled, either random or fixed design.
Linear bandits Our problem can be written as a stochastic linear bandit by noticing that hAt, ✓?i2 = hAtA>t , ✓?✓>? i, where the inner product between matrices on the right-hand side should be interpreted coordinate-wise and the action set is {aa> : a 2 Bd1}. There is an enormous literature on stochastic linear bandits [Auer, 2002, Dani et al., 2008, Rusmevichientong and Tsitsiklis, 2010b, Chu et al., 2011, Abbasi-Yadkori et al., 2011]. This reduction immediately yields an upper bound on the minimax regret of O(d2 p n log(n)).
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 E ⇢ Rd1⇥d2 and A ⇢ Rd1⇥d2 . A low-rank bandit problem over E and with actions A is characterised by a matrix ⇥? 2 E . The learner plays actions At 2 A and the reward is Xt = hAt,⇥?i+ ⌘t, where ⌘t is noise and the inner product between matrices is interpreted coordinate-wise. So far this is nothing more than
a 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 E and the action set A. Our setup is recovered by assuming that E = {xx> : x 2 Sd 1r } and A = {xx> : x 2 Bd1}. Jun et al. [2019] assume that E consists of rank p matrices and A = {xy> : x 2 X , y 2 Y} for some reasonably bounded sets X ⇢ Rd1 and Y ⇢ Rd2 . They prove that the regret is bounded by Õ((d1 + d2)3/2 p 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 E 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 Õ((d1 + d2)3/2 p pn). For the bandit phase retrieval problem, d1 = d2 = d and p = 1,
so this algorithm yields an upper bound on the regret for bandit phase retrieval of Õ(d3/2 p n). 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-problem, despite the fact that the heuristic argument used by these authors holds in this case, as 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 hAt,⇥ti with (⇥t)nt=1 an independent and identically distributed sequence of low-rank matrices (with unknown distribution). For example, Katariya et al. [2017b,a] and Trinh et al. [2020] assume that ⇥t is rank-1 almost surely and A = {eie>j : 1  i, j  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 Kotłowski and Neu [2019]. They assume that (✓t)nt=1 is a sequence of vectors chosen in secret by an adversary at the start of the game and the learner observes hAt, ✓ti2. They design an algorithm for which the regret is at most Õ(d p n), while the best lower bound is ⌦( p dn).

heading: 3 Information-theoretic heuristics and information-directed sampling
text: 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 ⌦(d3/2 p 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 Sd 1r and suppose that ✓? is sampled from . The learner takes an action A 2 Bd1 and observes X = hA, ✓?i2 + ⌘ with ⌘ sampled from a 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 just fix an arbitrary A 2 Sd 11 . Let
P✓ be a Gaussian with mean hA, ✓i2 and variance 1. Then,
I(✓?;X) = E  KL ✓ P✓? , Z
Sd 1r P✓ d (✓)
◆ = Z
Sd 1r KL
✓ P↵, Z
Sd 1r P✓ d (✓)
◆ d (↵)
 Z
Sd 1r
Z
Sd 1r KL (P↵,P✓) d (↵) d (✓) =
1
2
Z
Sd 1r
Z
Sd 1r
hA, ✓i2 hA,↵i2 2 d (↵) d (✓)
= r4
2
✓ 3
d2 + 2d 1 d2
◆  r 4
d2 , (1)
where the first inequality follows from convexity of the relative entropy. Note that d2 log(n) bits are needed to code ✓? to reasonable accuracy. So if 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(nr4/d2) bits by Eq. (1). By setting r2 = d3/2 p log(n)/n one could be led to believe that the learner cannot identify the optimal direction and the regret would be ⌦(nr2) = ⌦(d3/2 p
n log(n)). The main point is that the rate of information accumulated by a careful learner increases over time.
Information-directed sampling The combination of our upper bound and the observation above has an important implication. Suppose as above that ✓? is sampled uniformly from Sd 1r and let A be a possibly randomised action. Since the learner cannot know the realisation of ✓? initially, her expected regret for any action a 2 Bd1 is (a) = r2 E[ha, ✓?i2] = r2(1 kak2/d) r2(1 1/d). On the other hand, as outlined above, the information gain about ✓? is about r4/d2. Together these results show that the information ratio is bounded by
, E[ (A)] 2
I(✓?;X,A) = ⇥(d2) .
Since the entropy of a suitable approximation of the optimal action is about d2 log(n), an application of the information theoretic analysis by Russo and Van Roy [2014] suggests that the Bayesian regret can be bounded by O(d3/2 p n 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-armed bandits, but there the gain was less dramatic (a logarithm of the number of arms) and no changes to the algorithm were required.

heading: 4 Algorithm for bandit phase retrieval
text: We start by showing that Theorem 1 holds if the learner is given an action that is constant-factor optimal. In the next section we explain how such an action can be identified with low regret. Our algorithm uses the explore-then-commit design principle, which is usually only sufficient for O(n2/3) regret. The reason we are able to obtain O(n1/2) regret is because of the curvature of the action set, a property that has been exploited in a similar way in a variety of settings [Rusmevichientong and Tsitsiklis, 2010a, Huang et al., 2017, Kirschner et al., 2020].
Theorem 4. Suppose the learner is given an action bAw 2 Bd1 such that h bAw, ✓?i2 ↵r2 for some universal constant ↵ 2 (0, 1]. Then there exists a policy ⇡ for which the regret is at most Rn(⇡, ✓?)  const ·d p n log(n).
Proof. By choosing the sign of ✓?, assume without loss of generality that h bAw, ✓?i r p ↵. Let
m = l 4d p n log(n)/r2 m and = min
✓ 1
2 ,
p ↵
4
◆ .
If m n, then the regret of any policy is upper bounded nr2  const d p n 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 ) bAw ± ek : k 2 [d]}. The constrained least squares estimator of ✓? based on the data collected over m rounds is
✓̂ = argmin{L(✓) : ✓ 2 Bdr and h bAw, ✓i r p ↵} , (2)
where L(✓) = 12 Pm
t=1(Xt hAt, ✓i2)2. For the remaining n m rounds the algorithm plays At = bA = ✓̂/k✓̂k. Then,
, 9 + d log(98m) (3)
E " mX
t=1
hAt, ✓̂ ✓?i2hAt, ✓̂ + ✓?i2 #
(by Corollary 10)
↵k✓?k 2 4 E " mX
t=1
hAt, ✓̂ ✓?i2 #
(4)
↵ 2k✓?k2
2
⇣m 2d 1 ⌘ E h k✓̂ ✓?k2 i . (5)
where in Eq. (4) we used that for some k 2 [d],
hAt, ✓̂ + ✓?i = h(1 ) bAw ± ek, ✓̂ + ✓?i (1 )h bAw, ✓̂ + ✓?i k✓̂ + ✓?k
2(1 ) p ↵r 2 r
p ↵
2 k✓?k . (by definition of )
Eq. (5) follows because for any k 2 [d], X
2±1 h(1 ) bAw + ek, ✓̂ ✓?i2 = 2(1 )2h bAw, ✓̂ ✓?i2 + 2 2hek, ✓̂ ✓?i2
2 2hek, ✓̂ ✓?i2 , which implies that
mX
t=1
hAt, ✓̂ ✓?i2 jm 2d k dX
k=1
⇣ 2 2hek, ✓̂ ✓?i2 ⌘ 2 2 ⇣m 2d 1 ⌘ k✓̂ ✓?k2 .
Rearranging Eq. (5) and using the definition of shows that
E h k✓̂ ✓?k2 i  2
↵ 2k✓?k2 1 m 2d 1  const d 2 log(m) mk✓?k2 .
Letting a? = ✓?/k✓?k be the optimal action, the regret is bounded by
Rn(⇡, ✓?)  mk✓?k2 + nE h ha?, ✓?i2 h bA, ✓?i2 i
= mk✓?k2 + nE h ha? bA, ✓?iha? + bA, ✓?i i  mk✓?k2 + 2nE h ha? bA, ✓?i k✓?k i  mk✓?k2 + 4nE h k✓? ✓̂k2 i (by Lemma 6)
 mk✓?k2 + const nd2 log(m)
mk✓?k2  const d
p n log(n) .

heading: 5 Finding a constant-factor optimal action
text: To establish Theorem 1 we show there exists an algorithm that interacts with the bandit for a random number of rounds and outputs an action bAw that with high probability satisfies h bAw, ✓?i2 r2/64. Furthermore, the procedure suffers small regret in expectation. Theorem 5. Let T be the random number of rounds that Algorithm 1 interacts with the bandit, which cannot be more than n, and let bAw 2 Sd 11 be its output. Then,
1. E[T ]  const d2r4 log(n) log(d).
2. With probability at least 1 1/n, either T = n or h bAw, ✓?i2 r 2
64 .
1 ⌧ = r/ p d and m = ⌃ 8 ⌧4 log 2n2 ⌥ 2 do 3 sample v u n i f o r m l y from Sd 11 4 p l a y At = v f o r m r o un ds and compute a v e r a g e reward X̄ 5 loop u n t i l X̄ ⌧2 6 E = {v p X̄} 7 f o r k = 2 to d 8 = 9(log(98) + 4 log(n)) and m = ⇠ 64d2
kr4
⇡ and u = P w2E w
k P
w2E wk 9 do
10 sample v u n i f o r m l y from span(E)? \ Sd 11 11 p l a y At 2 {(u+ v)/ p 2, (u v)/ p 2, u} f o r 3m r o un ds 12 f i n d l e a s t s q u a r e s e s t i m a t o r ✓̂ c o n s t r a i n e d to Bd1 13 loop u n t i l hv, ✓̂i2 ⌧2
14 E = E [ {hv, ✓̂iv} 15 i f P w2E kwk2 r2/16 break 16 end f o r 17 re turn bAw = P w2E w k P
w2E wk
Algorithm 1: The procedure operates in d iterations. The first iteration is implemented in Lines 1–5 and the remaining d 1 iterations in Lines 7–15.
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 v computed in each iteration are orthogonal, which means that k(u+ v)/ p 2k = k(u v)/ p 2k = kvk = 1. Hence the actions of the algorithm are always in Bd1. The main argument of the proof is based on an induction to show that with high probability when the execution of the algorithm ends, there exists an s 2 {±1} such that for all w 2 E ,
(a) w 2 E , kwk2 ⌧2; and
(b) shw, ✓?i 2 [ 12kwk 2, 2kwk2].
We proceed in five steps. First, we prove that if the above holds and the algorithm halts before n rounds are over, then the vector returned is a suitable approximation of ✓?/k✓?k. Second, we upper bound the probability of certain bad events. In the third and fourth steps we 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,
h bAw, ✓?i2 = ⌧ P w2E w
k P w2E wk , ✓?
2 1
4
X w2E kwk2 r 2 64 .
where the first inequality follows from orthogonality of w 2 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 1/n. Step 2: Failure events The algorithm computes some kind of estimator at the end of each do/loop. Since the algorithm cannot play more than n actions, the number of estimators computed is naively upper bounded by n. A union bound over all estimates and the concentration bounds in Lemma 7 and Corollary 10 show that with probability at least 1 1/n the following both hold:
• For all v sampled in the first iteration and corresponding average rewards X̄ ,
X̄ hv, ✓?i2 
r 2 log(2n2)
m =
⌧2
2 , (6)
where m is defined in Line 1 of Algorithm 1.
• Let D = (As)s be the actions played in the inner loop of some iteration k 2 and ✓̂ be the corresponding least-squares estimator. Then,
X a2D ha, ✓̂ ✓?i2ha, ✓̂ + ✓?i2  9(log(98) + 4 log(n)) , . (7)
We assume both of the above hold in all relevant iterations for the remainder.
Step 3: Base case The next step is to 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 v 2 Sd 11 , the algorithm plays v for m rounds and computes the average reward. Let v be the last sampled action before the iteration halts and w = v p X̄ . By the stopping condition in Line 5, kwk2 = X̄ ⌧2. Without loss of generality, we choose the sign of ✓? so that hv, ✓?i 0. Then by Eq. (6),
hw, ✓?i = p X̄hv, ✓?i 2  1
2 kwk2, 2kwk2 .
This establishes the base case.
Step 4: Inductive step Assume that (a) and (b) above hold for E at the end of iteration k. Let u be the value computed in Line 8 of Algorithm 1. Then,
hu, ✓?i = P
w2Ehw, ✓?ipP w2E kwk2
1 2
sX
w2E kwk2 ⌧
p k 2 .
Let A = {(u + v)/ p 2, (u v)/ p 2, v}, which is the set of actions played in the inner loop of
iteration k + 1 after sampling v for the last time. Let ✓̂ be the corresponding least-squares estimate. We consider two cases. First, if hu, ✓̂ + ✓?i 2|hv, ✓̂ + ✓?i|, then by Eq. (7),
m X
a2A ha, ✓? ✓̂i2ha, ✓? + ✓̂i2
1 16 hu+ v, ✓? ✓̂i2hu, ✓?i2 + 1 16 hu v, ✓? ✓̂i2hu, ✓?i2
1 8 hv, ✓? ✓̂i2hu, ✓?i2
kr2 16d hv, ✓? ✓̂i2 .
Rearranging shows that
hv, ✓? ✓̂i2  16d mkr2  ⌧
2
4 . (8)
For the second case, hu, ✓̂ + ✓?i  2|hv, ✓̂ + ✓?i|. Then,
m X
a2A ha, ✓? ✓̂i2ha, ✓? + ✓̂i2
1 4 hv, ✓̂ ✓̂i2hu, ✓̂ + ✓?i
kr2
8d hv, ✓? ✓̂i2 .
And again, Eq. (8) holds. Summarising, hv, ✓̂i is an estimator of hv, ✓?i up to accuracy ⌧/2. By the definition of the algorithm, the iteration only ends if |hv, ✓̂i| ⌧ . Therefore, with w = hv, ✓̂iv, we have kwk2 = hv, ✓̂i2 ⌧2. Furthermore, hw, ✓?i = hv, ✓̂ihv, ✓?i 2 [kwk2/2, 2kwk2] . Therefore if (a) and (b) hold for E computed after iteration k, they also hold for E computed after iteration k + 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-dependent constant, while the latter depends principally on how many samples are needed before |hv, ✓?i| is suitably large. The law of ⌫ is the
uniform distribution on Sd 11 \ span(E)?, which is the uniform distribution on a sphere of dimension d 1 |E| embedded in Rd. The squared norm of the projection of ✓? onto span(E)? is
k✓?k2 X
w2E
h✓?, wi2
kwk2 r 2 4
X w2E kwk2 r 2 2 ,
where we used (a) of the induction and the stopping condition in Line 15. Therefore, when v is sampled uniformly from Sd 11 \ span(E)?, by Lemma 8,
P hv, ✓?i2 3⌧2/2 = P ✓ hv, ✓?i2 3r2
2d
◆ const > 0 ,
Furthermore, by the concentration analysis in the previous step, an iteration will end once a v has been sampled for which hv, ✓?i2 3⌧2/2. Hence, the expected number of times the algorithm samples v per iteration is constant and a simple calculation using the definition of m in Lines 1 and 8 shows that the expected number of rounds used by the algorithm is at most
E[T ]  const d 2
r4 log (n) log(d) .

heading: 6 Proof of Theorem 1 and Theorem 2
text: Proof of Theorem 1. Run Algorithm 1 and if it halts, feed the returned action to the input of the explore-then-commit algorithm analysed in Theorem 4. Algorithm 1 fails to return a suitable action with probability at most 1/n, so the contribution of this event to the regret is negligible. By Theorem 5, the regret incurred by Algorithm 1 is bounded by
E " TX
t=1
r2 hAt, ✓?i2 #  r2E[T ]
 min ✓ nr2, const d2
r4 log(d) log(n)
◆
 const d p n log(d) log(n) .
Combining this with the regret bound established in Theorem 4 yields the result.
Proof of Theorem 2. We use a standard reduction [Lattimore and Szepesvári, 2020, Chapter 33]. Let ⇡ be the policy used in the proof of Theorem 1 with bA? sampled uniformly from (At)nt=1. By Theorem 1,
rn(⇡, ✓?) = 1
n
nr2 E
" nX
t=1
hAt, ✓?i2 #! = Rn(⇡, ✓?)
n  const d
r log(n) log(d)
n .

heading: 7 Proof of Theorem 3
text: Let ⇡ be a fixed policy and for ✓ 2 Rd let P✓ be the measure on the sequence of outcomes Hn = (A1, X1, . . . , An, Xn) induced by the interaction between ⇡ and the phase retrieval model determined by ✓. Let E✓ denote the expectation with respect to P✓. Let r be a positive constant to be tuned subsequently and be the uniform (Haar) measure on Sd 1r . Let Q = R P✓ d (✓) be the Bayesian mixture measure. For ✓ 2 Rd, let E✓ be the event given by
E✓ = ⇢ h bA?, ✓i2 3
4 r2 .
By Fano’s inequality [Gerchinovitz et al., 2020, Lemma 5], Z
Sd 1r P✓(E✓) d (✓) 
log 2 + R Sd 1r KL(P✓,Q) d (✓)
log ⇣R Sd 1r Q(E✓) d (✓) ⌘ . (9)
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 E✓. Step 1: Bounding the denominator in Eq. (9) By exchanging the order of integrals in the denominator of Eq. (9), it follows that
log ✓Z
Sd 1r Q(E✓) d (✓)
◆ = log ✓Z Z
Sd 1r 1E✓ d (✓) dQ
◆ . (10)
If U is sampled uniformly from Sd 11 , then by a concentration bound for spherical measures [Dasgupta and Gupta, 2003, Lemma 2.2],
P U21 /d  exp( /4) for all > 6 .
By scaling and rotating and choosing = 34d, it follows that for any bA? 2 B d 1,
Z
Sd 1r 1
✓ h bA?, ✓i2 3r2
4
◆ d (✓)  exp ( 3d/16) .
Therefore, by Eq. (10),
log ✓Z
Sd 1r Q(E✓) d (✓)
◆ 3d
16 .
Step 2: Bounding the numerator in Eq. (9) By the convexity of KL-divergence, Z
Sd 1r KL(P✓,Q) d (✓) =
Z
Sd 1r KL
✓ P✓, Z
Sd 1r P↵ d (↵)
◆ d (✓)
 Z
Sd 1r
Z
Sd 1r KL (P✓,P↵) d (↵) d (✓) .
By the chain rule of KL-divergence,
KL (P✓,P↵) = E✓
" nX
t=1
KL (P✓(Yt = ·|At),P↵(Yt = ·|At)) # .
A straightforward computation leads to
KL (P✓,P↵) = E✓
" nX
t=1
1
2
(A>t ✓) 2 (A>t ↵)2 2 #
= 1
2 E✓
" nX
t=1
(A>t ✓) 4 2(A>t ✓)2(A>t ↵)2 + (A>t ↵)4 # .
Since (At)nt=1 are independent of (Xt)nt=1, we can interchange the expectation and integral such that Z
Sd 1r KL(P✓,Q) d (✓)
 nX
t=1
E Z
✓
Z
↵
(A>t ✓) 4 2(A>t ✓)2(A>t ↵)2 + (A>t ↵)4 d (↵) d⌫(✓) ,
where the expectation is with respect to (At)nt=1, which does not depend on ✓ by assumption. When ✓ is uniformly on Sd 1r and A 2 Bd1 is arbitrary,
Z
Sd 1r hAt, ✓i4 d (✓) =
3r4
d2 + 2d and
Z
Sd 1r hAt, ✓i2 d (✓) =
1
d2 ,
where the expectation is taken with respect to ✓. Therefore, Z
Sd 1✓ KL(P✓,Q) d (✓) 
3nr4
d2 . (11)
Step 3: Lower bounding the regret Let r2 = p d3/(32n) Combining the previous two steps shows that Z
Sd 1r P✓(E✓) d (✓) 
16nr2
d3  1 2 .
Therefore there exists a ✓ 2 Sd 1r with P✓(E✓)  1/2, which implies that
rn(⇡, ✓) = r 2 E✓ h h bA?, ✓i2 i r 2
8 const d
3/2 p n .

heading: 8 Discussion
text: Unknown radius The assumption that r = k✓?k is known to the learner is easily relaxed by estimating k✓?k. Note first that all our analysis holds with only trivial modifications if r 2 [ 12k✓?k, k✓?k]. Next, if A is sampled uniformly from Sd 11 and X = hA, ✓?i2 + ⌘ and ⌘ is a standard Gaussian, then E[X] = 1dk✓?k
2 and V[X] = 1 + 2(d 1)/(d3 + 2d2) = ⇥(1). Therefore k✓?k can be estimated to within an arbitrary multiplicative factor and at confidence level 1 1/n using const d2/k✓?k4 log(n) interactions with the bandit.
Computation complexity The only computational challenge is finding the least squares estimates, which is a non-convex optimisation problem. Candès et al. [2015b] proposed a Wirtinger flow algorithm that starts with a spectral initialization, and then refines this initial estimate using a local update like gradient descent. The computational complexity of the Wirtinger flow algorithm with "-accuracy is O(nd2 log(1/")) where n is the number of samples.
Adversarial setting Kotłowski and Neu [2019] study the adversarial version of this problem, where the learner observes hAt, ✓ti2 and (✓t)nt=1 is an adversarially sequence with ✓t 2 Bd1 for all t. They prove an upper bound of Rn = O(d p n log(n)) and a lower bound of ⌦( p dn). Natural attempts at improving the lower bound all fail. We 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 or information-directed sampling be made to work? The main challenge is to understand the sample paths of these algoritms before learning takes place.

Review summaries:
 The 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.  1. 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). 2. The paper extends the regret results to the pure exploration settings (Theorem 3). 3. The paper suggests that optimal regret is not attainable by fixed policies (Theorem 4).  The 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. 

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.

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). 

The paper studies a stochastic bandit optimization problem in which the expected reward can be expressed as $\langle a , \theta_\star \rangle^2$, where $\theta_\star$ is an unknown parameter. The authors provides an algorithm that achieve a nearly tight (up to logarithmic factors) cumulative regret bounds. Nearly tight bounds for simple regret have been shown as well.