Moise Blanchard

Bandit PCA with Minimax Optimal Regret

An adaptive adversary is constructed that refines a hidden large-reward subspace based on the learner's actions, in such a way that low regret is impossible without estimating the subspace; as a result, lower-bounding the regret reduces to studying the arising subspace estimation problem.