Bandit Phase Retrieval

Tor Lattimore, Botao Hao

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.

  1. 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."
  2. Constrained Least Squares: In each iteration, the learner solves a constrained least-squares problem to continuously refine the estimate of the unknown parameter.
  3. 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.

Comparison of upper and lower bounds for bandit phase retrieval and related problems.
  • 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

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.
BibTeX
@inproceedings{lattimore2021bandit,
  author = {Tor Lattimore and Botao Hao},
  title = {{Bandit Phase Retrieval}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=qTky2i4IpzN},
}
Figure