Overview
In the realm of multi-armed bandits, standard "principled" approaches like Thompson Sampling can sometimes prove suboptimal in highly structured environments. The paper "Bandit Phase Retrieval" tackles a challenging variant of the linear bandit problem, revealing that optimal performance requires an adaptive exploration strategy that "learns to learn" faster over time. The authors provide the first minimax optimal algorithm for this setting, successfully closing a long-standing theoretical gap.
The Problem: Bandit Phase Retrieval
In a standard linear bandit, a learner chooses an action vector $A_t$ and receives a reward proportional to its inner product with an unknown parameter vector $\theta_*$. In Bandit Phase Retrieval, the reward is instead the square of that inner product: $X_t = \langle A_t, \theta_* \rangle^2 + \eta_t$.
This model is a specific instance of "low-rank bandits" and draws inspiration from classical phase retrieval in signal processing, where only the intensity (magnitude squared) of a signal is observed, not its phase.
The core challenge lies in the information structure. Because the reward is squared, actions that are nearly orthogonal to the target $\theta_*$ provide very little information due to a low signal-to-noise ratio. Prior to this work, the best upper bounds for cumulative regret were $O(d^{3/2}\sqrt{n})$, while lower bounds suggested $O(d\sqrt{n})$ should be achievable. This paper successfully closes that $\sqrt{d}$ gap.
Methodology: Adaptive Explore-then-Commit
The authors depart from standard "optimistic" or "posterior sampling" methods, which are difficult to prove optimal for this specific quadratic structure. Instead, they utilize a sophisticated Explore-then-Commit (ETC) framework featuring a novel Adaptive Exploration phase.
- Iterative Refinement: Rather than sampling randomly, the exploration phase iteratively builds an estimate of $\theta_*$. It begins with a rough guess and uses that estimate to select subsequent actions that are more likely to yield high-quality information—a process akin to a "noisy power method."
- Constrained Least Squares: In each iteration, the learner solves a constrained least-squares problem to continuously refine the estimate of the unknown parameter.
- Curvature Exploitation: Once a "constant-factor optimal" action is found (one reasonably aligned with $\theta_*$), the algorithm switches to a commitment phase. Because the quadratic reward function has "curvature," the learner can achieve the optimal $\sqrt{n}$ regret rate even with a simple ETC structure, provided the initial exploration was sufficiently targeted.
Key Theoretical Insights
- Information Acceleration: A critical insight is that the rate of information gain is not constant. As the learner's actions become better aligned with the true $\theta_*$, they learn about $\theta_*$ at an increasingly faster rate. Non-adaptive exploration strategies, which sample directions uniformly, fail to exploit this acceleration.
- Adaptivity is Mandatory: The authors prove that for "pure exploration" or "simple regret" (finding the best action at the end of the game), adaptive policies are strictly better than non-adaptive ones by a factor of $\sqrt{d}$.
- Heuristics Can Be Misleading: The paper demonstrates that a common heuristic for guessing lower bounds—comparing signal-to-noise ratios—leads to an incorrect $\Omega(d^{3/2}\sqrt{n})$ conjecture. A more rigorous information-theoretic analysis reveals the true bound is lower.
Main Results
The paper's primary theoretical contributions are summarized in the table below, comparing their newly established bounds against previous state-of-the-art methods.
- Minimax Cumulative Regret: The authors prove an upper bound of $\tilde{O}(d\sqrt{n})$, matching the known lower bound up to logarithmic factors and yielding a $\sqrt{d}$ improvement over previous work.
- Minimax Simple Regret: They establish that the optimal simple regret is $\tilde{\Theta}(d/\sqrt{n})$.
- Non-adaptive Gap: They formally prove the necessity of adaptive exploration by showing that any non-adaptive policy must suffer a simple regret of at least $\Omega(d^{3/2}/\sqrt{n})$.
Limitations and Future Directions
While theoretically robust, the proposed algorithm requires solving a constrained least-squares problem, which is non-convex for phase retrieval. The theoretical guarantees rely on finding the global optimum, though heuristics like "Wirtinger flow" might be used in practice. Additionally, the strategy relies on "warm-starting" an estimate, which may lack robustness in adversarial settings where the target $\theta_*$ can change. Finally, generalizing these adaptive techniques to more complex low-rank bandit problems (where the hidden matrix has a rank $p > 1$) remains an open question for future research.
Summary updated