这篇论文把Bandit PCA的遗憾上界从O(d√(rT log T))降到O(r√(dT))，下界也提到Ω(r√(dT))，彻底解决了这个优化问题的理论最优性。
该论文研究在线PCA的bandit反馈版本（Bandit PCA），每一轮t=1,...,T中，对手选择秩至多为r的d×d对称增益矩阵G_t，学习者选择单位向量w_t并接收奖励w_t^T G_t w_t。Kotlowski和Neu(2019)给出遗憾上界O(d√(rT log T))和下界Ω(r√(T/log T))。本文将上界改进至O(r√(dT))（忽略d和T的对数因子），下界提升至Ω(r√(dT))，从而确定了该问题的极小极大最优遗憾。上界算法结合了在密度矩阵谱面上的在线镜像下降与多尺度探索方案。
Bandit PCA with Minimax Optimal Regret
We study the bandit-feedback version of online principal component analysis (Bandit PCA): in each round $t = 1,\dots,T$, the adversary selects a $d \times d$ symmetric gain matrix $G_t$ with spectrum in $[0,1]$ and rank at most $r$; the learner simultaneously selects a unit vector $w_t \in S^{d-1}$ and receives the reward $w_t^\top G_t w_t$. The learner receives no other feedback, and aims to minimize the regret against the best unit vector in hindsight. This problem was introduced by Kotlowski and Neu (2019), who gave an algorithm with regret $O(d\sqrt{rT \log T})$ and showed the lower bound of $Ω(r\sqrt{T/\log T})$. We improve upon both of these bounds and essentially bridge the gap between them, establishing the minimax regret of order $r\sqrt{dT}$ up to polylogarithmic factors in $d$ and $T$. The upper bound is attained by a novel algorithm, which combines online mirror descent on the spectrahedron of (real) density matrices with a multiscale exploration scheme in which the eigenspaces with different spectral magnitudes are updated at different rates. For the lower bound, we construct an adaptive adversary 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. Finally, we discuss connections of Bandit PCA with adaptive-measurement quantum tomography.