Bandit PCA with Minimax Optimal Regret

2026-07-14 · Source: stat.ML updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Mathematics & Computational Sciences, Quantum Information Science · Depth: Expert, extended

Summary

The paper introduces a novel algorithm for Bandit Principal Component Analysis (Bandit PCA), a matrix-valued online learning problem where a learner selects unit vectors and receives scalar rewards from an adversary-controlled positive-semidefinite gain matrix. This work establishes the minimax optimal regret for rank-r Bandit PCA, achieving O(r*sqrt(dT)*log^3(edT)). This significantly improves upon previous bounds by Kotłowski and Neu (2019), which had an upper bound of O(d*sqrt(rT*log T)) and a lower bound of Omega(r*sqrt(T/log T)). The new algorithm combines online mirror descent with a multiscale exploration scheme, featuring a layered sampling approach that groups eigenvectors by eigenvalue magnitude and an epoch-based gain estimator with batching. The total runtime is O(d^2*T*log(ed)).

Key takeaway

For Research Scientists developing online learning algorithms for matrix-valued bandit problems, this work demonstrates that O(r*sqrt(dT)) regret is achievable for Bandit PCA. You should investigate layered sampling and epoch-based gain estimation techniques to improve regret bounds, especially when dealing with evolving principal components. While the O(d^2*T*log d) runtime is higher than some prior methods, the significant regret improvement makes this approach critical for applications requiring minimax optimality.

Key insights

A novel algorithm achieves minimax optimal regret for Bandit PCA by combining online mirror descent with layered, epoch-based exploration.

Principles

• Online Mirror Descent (OMD) on spectrahedron is effective for matrix-valued bandit problems.
• Multiscale exploration, updating eigenspaces at different rates, can bridge regret gaps.
• Batching gain matrix estimations over epochs significantly reduces variance for off-diagonal blocks.

Method

The algorithm partitions OMD matrix eigenvectors into L=O(log(dT)) layers by eigenvalue magnitude. It then samples a layer and uniformly explores within its span, using epoch-based batching to estimate gain matrices and lazily updating layers.

In practice

• Consider layered sampling for online learning problems involving evolving spectral properties.
• Implement epoch-based batching for variance reduction in matrix estimation tasks.

Topics

• Bandit Principal Component Analysis
• Online Mirror Descent
• Regret Bounds
• Quantum Tomography
• Matrix-valued Bandits
• Subspace Estimation

Best for: AI Scientist, Research Scientist

Related on AIssential

• Optimal last-iterate convergence in matrix games with bandit feedback using the log-barrier — Log-barrier regularization enables optimal last-iterate convergence in uncoupled zero-sum matrix games.
• Adversarial Bandit Optimization with Globally Bounded Perturbations to Convex Losses — This work extends adversarial bandit optimization to general convex and β-smooth losses with globally bounded post-action perturbations.
• Catching a Moving Subspace: Low-Rank Bandits Beyond Stationarity — Scalar rewards enable quadratic measurements for changing low-rank subspace recovery in non-stationary bandits.
• Nonlinear Bandit — Huber loss-based algorithms provide robust, computationally efficient solutions for heavy-tailed generalized linear and nonlinear bandits.
• Provably Optimal Learning Algorithms for Assistance Games — Provably efficient learning algorithms for human-assistant interaction achieve near-optimal regret in online assistance games.
• Any-Time Regret-Guaranteed Algorithm for Control of Linear Quadratic Systems — Adaptive exploration-exploitation and relaxed stability criteria enable efficient, regret-guaranteed control for unknown linear quadratic systems.

See Counsel's argued verdicts on the open AI decisions leaders are weighing →

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by stat.ML updates on arXiv.org.