Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery
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 two-phase spectral-then-misspecified-linear-bandit algorithms for contextual low-rank bandits, using tight two-to-infinity subspace recovery guarantees to get near-minimax policy evaluation and best policy identification and improved regret.
Problem
Contextual low-rank bandits where the learner observes noisy entries of an unknown low-rank reward matrix; the goal is policy evaluation, best policy identification, and regret minimization with optimal dependence on matrix size.
Approach
Estimate left and right singular subspaces via spectral truncation with tight two-to-infinity norm error bounds, then reformulate the low-rank bandit as a misspecified linear bandit of dimension r(m+n)-r^2 whose misspecification is controlled by the subspace error; a SupLinUCB variant solves the second phase.
Key results
- Policy evaluation and best policy identification sample complexity typically scales as r(m+n)/epsilon^2 log(1/delta), nearly minimax optimal under homogeneity.
- RS-SupLinUCB regret scales as r^{5/4}(m+n)^{3/4} sqrt(T), improving over prior low-rank bandit algorithms and beating unstructured sqrt(mnT) in the homogeneous case.
- Lower bounds show sample complexity of any PAC policy evaluation estimator is at least order (m+n)/(omega_max mn eps^2) kl(delta,1-delta) for some homogeneous instance.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use two-phase RSPE instead of single-stage DSMPE | Policy evaluation · Policy evaluation (homogeneous M and ω) | sample complexity: \frac{\sigma^2(m+n)}{\varepsilon^2} \log(1/{\delta}) vs. {L^2(m+n)\over \varepsilon^2}\log^3(1/\delta) | Helped |
| exploit low-rank structure with RSPE rather than unstructured policy evaluation | Policy evaluation · Policy evaluation | sample complexity: {mn\over \varepsilon^2}\log(1/\delta) to \frac{\sigma^2(m+n)}{\varepsilon^2} \log(1/{\delta}) | Helped |
| use two-phase RSBPI rather than prior contextual low-rank BPI | Best policy identification · Best policy identification | sample complexity: {m+n\over \varepsilon^{2+r}}\log(1/\delta) to {r(m+n)\over \varepsilon^2}\log(1/\delta) | Helped |
| use RSLin to exploit low-rank structure instead of an unstructured bandit algorithm | Regret minimization · Regret minimization (homogeneous) | regret: \widetilde{O}(\sqrt{mnT}) vs. \widetilde{O}\left(Lr^{5/4} n^{3/4}\sqrt{T} \right) | Helped |
| use RSLin rather than the prior contextual low-rank regret algorithm | Regret minimization · Contextual low-rank bandits | regret: \widetilde{O}((m+n)^{\frac{1}{3r+2}} T^{\frac{3r+1}{3r+2}}) to \widetilde{O}(r^{5/4}(m+n)^{3/4}\sqrt{T}) | Helped |
| use two-phase RSPE rather than DSMPE | Policy evaluation · Numerical experiments (Appendix) | performance | Helped |
| use two-phase RSBPI rather than DSMBPI | Best policy identification · Numerical experiments (Appendix) | performance | Helped |
Surprising findings
- Direct spectral (DSM) estimators are reported to be much worse experimentally than the two-phase RS methods, despite similar minimax guarantees.
- The regret bound is strictly smaller than unstructured sqrt(mnT) for all T when m=Theta(n), the first such guarantee to the authors' knowledge.
Limitations
- Dependence on L = max(||M||_max, sigma) rather than sigma due to spectral truncation bias; not exact recovery as sigma goes to 0.
- Regret minimax rate r^{5/4}(m+n)^{3/4}sqrt(T) does not reach sqrt(poly(r)(m+n)T) conjectured optimum.
- Guarantees rely on homogeneity assumptions for the tightest minimax statements and assume known sampling distribution omega.
Experimental setup
Metrics: sample complexity regret policy value error
Baselines: DSM-PE / DSM-BPI (direct spectral estimate) ESTR G-ESTT UCB OCTAL context-lumpable bandit algorithms
Builds on: SupLinUCB Poisson approximation leave-one-out analysis ESTR (bilinear bandits)
Closest papers by meaning
- Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems (NeurIPS 2022 · similarity 0.92)
- Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning (NeurIPS 2023 · similarity 0.91)
- Efficient Low-Rank Matrix Estimation, Experimental Design, and Arm-Set-Dependent Low-Rank Bandits (ICML 2024 · similarity 0.91)
- Linear Bandits with Partially Observable Features (ICML 2025 · similarity 0.89)
- Generalized Linear Bandits with Limited Adaptivity (NeurIPS 2024 · similarity 0.89)
- Symmetric Linear Bandits with Hidden Symmetry (NeurIPS 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.