Bandit Phase Retrieval
This work addresses a theoretical problem in online learning for researchers, providing improved regret bounds and insights into algorithm design, though it is incremental as it builds on existing bandit and phase retrieval frameworks.
The paper tackles the bandit phase retrieval problem by proving a minimax cumulative regret of ̃Θ(d√n), improving previous bounds by a factor of √d, and shows that minimax simple regret is ̃Θ(d/√n), achievable only by adaptive algorithms.
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, θ_\star\rangle^2$ where $θ_\star \in \mathbb R^d$ is an unknown parameter vector. We prove that the minimax cumulative regret in this problem is $\smash{\tilde Θ(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 Θ(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.