Bandit Phase Retrieval

Tor Lattimore, Botao Hao

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$ where $\theta_\star \in \mathbb R^d$ is an unknown parameter vector. We prove that the minimax cumulative regret in this problem is $\smash{\tilde \Theta(d \sqrt{n})}$, which improves on the best known bounds 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 are not sufficient for optimal regret.

Introduction

Phase retrieval is the classical problem of recovering a hidden signal $\theta_\star$ from the magnitude of its linear measurements. In the bandit setting, this translates to a learner choosing actions $A_t$ from a $d$-dimensional unit ball and receiving rewards $Y_t = \langle A_t, \theta_\star \rangle^2 + \eta_t$, where $\eta_t$ is Gaussian noise. The objective is to minimize cumulative regret over $n$ rounds. This problem is a specific instance of "low-rank bandits," characterized by a non-linear and symmetric reward function that poses unique challenges for standard bandit assumptions.

Methodology

The core of the proposed approach is a sophisticated Explore-Then-Commit (ETC) framework that utilizes a novel Adaptive Exploration strategy.

Adaptive Exploration

Unlike standard ETC algorithms that rely on fixed or random designs, the proposed algorithm iteratively refines its exploration. It begins by sampling directions uniformly to obtain a coarse estimate of $\theta_\star$. Subsequently, it selects new directions orthogonal to the current subspace of knowledge, effectively "filling in" the dimensions of the hidden vector. This adaptive process exploits the fact that as the estimate improves, the cost of acquiring new information decreases—a phenomenon termed Information Acceleration.

Estimation

To estimate $\theta_\star$, the learner solves a constrained least-squares problem. Although the objective is non-convex due to the squared inner product, the authors demonstrate that for regret minimization, it is sufficient to find an estimate close to either $\theta_\star$ or $-\theta_\star$. The inherent symmetry of the problem ensures that phase ambiguity does not hinder performance, as both vectors yield the same optimal action.

Key Results

The paper establishes tight minimax bounds for Bandit Phase Retrieval, significantly improving upon previous conjectures and closing the gap left by prior literature.

Summary of upper and lower bounds established in this work compared to prior literature.

Minimax Regret

The authors prove that the minimax cumulative regret is $\Theta(d\sqrt{n})$. This result improves upon previous work that suggested a dependency of $O(d^{1.5}\sqrt{n})$. The improvement by a factor of $\sqrt{d}$ stems from the adaptive exploration strategy that avoids the "heuristic trap" of assuming a constant rate of information gain.

The Necessity of Adaptivity

A critical finding is the fundamental gap between adaptive and non-adaptive algorithms. The paper proves that any non-adaptive policy—one that determines all exploration actions before observing any rewards—must suffer a simple regret of at least $\Omega(d^{1.5}/\sqrt{n})$. In contrast, the proposed adaptive algorithm achieves a simple regret of $\Theta(d/\sqrt{n})$, demonstrating that "learning while exploring" is essential for efficiency in phase retrieval.

Discussion and Future Work

While this work settles the minimax rates for the rank-1 case, several avenues for future research remain. The estimation step involves non-convex optimization; while heuristics like Wirtinger flow are promising, a globally optimal, low-complexity implementation for all steps remains a practical challenge. Furthermore, extending these tight bounds to general rank-$p$ low-rank bandits and investigating adversarial settings where $\theta_\star$ may change over time are natural next steps.

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$ where $\theta_\star \in \mathbb R^d$ is an unknown parameter vector. We prove that the minimax cumulative regret in this problem is $\smash{\tilde \Theta(d \sqrt{n})}$, which improves on the best known bounds 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 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