Bandit PCA with Minimax Optimal Regret

Bandit Principal Component Analysis (Bandit PCA) is a sequential decision-making problem where a learner chooses a unit vector in each round to maximize a reward determined by an unknown, rank-constrained, positive-semidefinite gain matrix. The learner only observes the scalar reward, not the gain matrix itself. The goal is to minimize regret—the difference between the cumulative reward of the learner's choices and the best fixed direction in hindsight. This paper addresses the gap between existing upper and lower bounds for this problem.

The authors propose a novel algorithm that combines Online Mirror Descent (OMD) on the spectrahedron of density matrices with a sophisticated multiscale exploration scheme. Key innovations include:

• Layered Sampling: The algorithm partitions the eigenspaces of the OMD iterate into layers based on eigenvalue magnitude and samples exploration vectors uniformly within these subspaces.
• Epoch-based Estimation: Gain matrices are estimated using a hierarchical, epoch-based batching strategy that reduces the variance of off-diagonal block estimates, which are critical for tracking rotations in the principal components.
• Adaptive Adversary: To prove the lower bound, the authors construct an adaptive adversary that forces the learner to solve a subspace estimation problem, demonstrating that the O(rsqrt(dT)) regret is fundamentally unavoidable.

The paper proves that the minimax regret for rank-r Bandit PCA is indeed O(rsqrt(dT)) (up to polylogarithmic factors). This result is significant because it bridges the gap between the previous O(dT)) upper bound and the lower bound of Omega(r*sqrt(T)). The findings show that for small rank (r=O(1)), the problem is as hard as multi-armed bandits, while for large rank (r=O(d)), the complexity is dominated by the ambient dimension.