Research map / Bandits and online learning / Contextual bandits and Thompson sampling

Efficient Low-Rank Matrix Estimation, Experimental Design, and Arm-Set-Dependent Low-Rank Bandits

ICML 2024 · Bandits and online learning › Contextual bandits and Thompson sampling · approach: Linear and generalized linear bandits · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes LowPopArt, a low-rank matrix trace-regression estimator using Minsker's matrix Catoni-type estimator with a hard-thresholding step, plus an arm-set-dependent design quantity B(Q) for experimental design and low-rank bandit regret bounds.

Problem

Estimating a low-rank matrix Theta* from trace-regression measurements when the covariate distribution is known, and minimizing regret in low-rank matrix bandits whose difficulty depends on the arm set.

Approach

Replaces the per-coordinate Catoni estimates of sparse PopArt with a single call to Minsker's matrix estimator, followed by hard thresholding to rank r, yielding a nuclear-norm error bound and an arm-set-dependent hardness quantity B(Q) that guides optimal design of experiments.

Key results

• LowPopArt's nuclear-norm error bound is claimed to be at least a factor r smaller than Koltchinskii et al. (2011).
• Lemma 3.6 shows the optimal design's B(Q) is never worse than maximizing the minimum eigenvalue and can improve orders-wise in some cases.
• A regret lower bound of order sigma^{2/3} S^{1/3} d^{-1/3} r^{1/3} T^{2/3} B^{1/3} is sketched for arm-set-dependent low-rank bandits.

Surprising findings

• The paper's own discussion indicates the gap between sparse and low-rank models makes the extension non-trivial, with a naive approach requiring e^{Theta(d)} Catoni calls.

Limitations

• Assumes known covariate distribution, so Q(pi) must be controllable and not estimated.
• Requires sample size n0 > (S*)^2 and bounded nuclear norm assumption.
• Experiments limited to a single synthetic instance; hard-thresholding necessity not yet empirically validated in the rebuttal.

Experimental setup

Benchmarks: synthetic low-rank matrix bandit instance

Metrics: estimation error regret

Baselines: PopArt LowOFUL nuclear norm penalized least squares (Koltchinskii et al., 2011) LowESTR

Builds on: PopArt Catoni estimator Minsker matrix estimator LowOFUL Explore-then-commit

Closest papers by meaning

• Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery (ICML 2024 · similarity 0.91)
• GL-LowPopArt: A Nearly Instance-Wise Minimax-Optimal Estimator for Generalized Low-Rank Trace Regression (ICML 2025 · similarity 0.89)
• Symmetric Linear Bandits with Hidden Symmetry (NeurIPS 2024 · similarity 0.87)
• Linear Bandits with Partially Observable Features (ICML 2025 · similarity 0.87)
• New Classes of the Greedy-Applicable Arm Feature Distributions in the Sparse Linear Bandit Problem (AAAI 2024 · similarity 0.86)
• Best Arm Identification in Generalized Linear Bandits via Hybrid Feedback (NeurIPS 2026 · similarity 0.86)