acceptodds
Withdrawn from ICLR 2027

Catching a Moving Subspace: Low-Rank Bandits Beyond Stationarity

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

272 views

Abstract

Many real bandit deployments (recommendation, ad targeting) share two structural facts handled only in isolation by prior work. Rewards live on a low-dimensional latent subspace, and that subspace drifts. Stationary low-rank bandits exploit the rank but assume a fixed subspace. Nonstationary linear bandits adapt to drift but their rates grow with the ambient dimension . We study *piecewise-stationary low-rank* linear contextual bandits with scalar rewards whose parameter factors as , where is an orthonormal basis for the rank- latent reward subspace in segment and is the time-varying latent state. The subspace is constant within each of unknown segments and may shift at the boundaries. The learner is a bandit with a sensing channel. Besides choosing actions, it may spend a round on a *probe*, a query drawn from a known exploration law that need not be a feasible action, and it pays for each probe its forgone reward plus a fee . We give three results. **(i) The identification boundary** (when the moving subspace can be recovered). With one scalar reward per round, isotropic probes drawn independently of the noise recover the moving subspace, or the part of it that the latent state excites, through quadratic functionals of rewards. The noise variance need not be known. Probes that miss a direction cannot recover the subspace. If the noise may depend on the probe direction, identification can fail even with full coverage. **(ii) Algorithm and dynamic regret.** **SPSC** (Single-Play Subspace-Calibrated Optimism) interleaves isotropic probes with optimistic windowed ridge regression inside the learned -dimensional subspace, given the segment boundaries. An adaptive variant detects them online. Measured against the best action for the mean reward vector, with probe costs charged, the dynamic regret over rounds is when the mean reward vector is constant within segments. The term depends on the rank , and the ambient dimension enters only the additive cost of learning the subspace. Drift within segments adds the usual window tradeoff. **(iii) Empirics.** Against eleven baselines on nine benchmarks, including UCI datasets, images, MovieLens and production logs, an SPSC variant has the lowest regret in 51 of 58 real-data (dataset, , ) cells. On a 40-cell synthetic grid, a rule of thumb suggested by the theory, that SPSC wins once , picks the winner in 39 cells.

Primary area:
reinforcement learning
Keywords:
low-rank linear bandits, non-stationary linear bandits, dynamic regret, subspace estimation, quadratic measurements, change-point detection, online learning, sequential decision-making

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_GaYwOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies piecewise-stationary low-rank linear contextual bandits, where the reward parameter lies in an unknown rank-rr subspace that can change over time. The authors introduce a probing-permitted setting in which the learner can occasionally issue costly sensing queries outside the feasible action set. Using squared probe rewards, the method estimates the current reward subspace through quadratic measurements, and then performs windowed optimistic linear bandit learning in the estimated low-dimensional representation. The proposed SPSC algorithm achieves a dynamic regret bound of O~(rKT+(rd)1/3K1/3T2/3)\widetilde{O}(r\sqrt{KT} + (rd)^{1/3}K^{1/3}T^{2/3}). The paper also provides identifiability results for moving-subspace recovery and extensive synthetic and real-data experiments.

Critical strengths
  1. Relatively complete theoretical development. The paper provides an identification analysis for recovering the moving subspace, a dynamic regret guarantee for SPSC, and an adaptive variant for unknown change points. This breadth makes the theoretical contribution fairly complete and is an important positive factor in my overall assessment.

  2. Extensive empirical evaluation. The paper evaluates the method on a broad range of synthetic and real-data benchmarks, compares against multiple low-rank and nonstationary baselines, and includes several ablation and control experiments. Overall, the empirical study is relatively thorough and supports the claimed advantages of the proposed method.

Critical weaknesses
  1. Strong probing assumption. The learner may issue probes outside the feasible action set, and the theoretical construction uses isotropic probes whose norm can be substantially larger than that of ordinary actions. While such a sensing channel is plausible for simulators or survey-style queries, it is less clear how it can be realized in recommendation or advertising systems, where actions are typically constrained to an available catalog. Since the main identifiability and regret improvements rely critically on this additional capability, this modeling assumption is the main reason for my weak-reject assessment.

  2. Restrictive theoretical conditions. The principal theorem assumes, among other conditions, constant mean rewards within segments, sufficiently well-conditioned projected designs, and known segment boundaries; the adaptive variant removes the last assumption but introduces additional requirements on effective rank, excitation, change magnitude, and segment length. These conditions limit the generality of the result.

Questions for authors
  1. Can the authors provide a concrete real-world application in which the probing-permitted model can be naturally implemented? In particular, what does an out-of-action-set probe correspond to operationally, and what would happen if probes were constrained to the feasible action set and the same norm bound as ordinary actions?

  2. Although the paper includes several real-data benchmarks, many of them are converted into bandit environments using fitted linear reward models or synthetic probe responses. Can the authors provide additional evidence in a setting where both the rewards and probing interactions arise naturally from real user or system feedback? Such an evaluation would better support the practical relevance of the proposed sensing model.

Reviewer_3WrzOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies a nonstationary low-rank bandit problem over TT rounds. At round tt, the learner either picks a feasible action xt∈At⊂Rdx_t\in\mathcal A_t\subset\mathbb R^d or a probe xt=utx_t=u_t, potentially outside At\mathcal A_t, for an additional cost, and observes a reward yt=xt⊤Bk⋆wt+εty_t=x_t^\top B_k^\star w_t+\varepsilon_t, where Bk⋆∈Rd×rB_k^\star\in\mathbb R^{d\times r} is constant on intervals IkI_k, with k=1,…,Kk=1,\ldots,K. The authors identify when the subspace spanned by Bk⋆B_k^\star can be learned and design an algorithm, SPSC, which uses the probes to estimate this subspace and uses projected ridge-UCB on the other rounds. The authors provide a regret guarantee O~(rKT+(rd)1/3K1/3T2/3)\widetilde O(r\sqrt{KT}+(rd)^{1/3}K^{1/3}T^{2/3}) under assumptions including known interval boundaries and a constant mean reward vector within each interval. The authors additionally evaluate their method on synthetic data and real-world classification, recommendation, and advertising datasets.

Critical strengths

The nonstationary low-rank bandit problem considered is relevant, and to my knowledge, under-studied. The analysis identifying when the subspace can be recovered is interesting.

The experiments include useful comparisons with algorithms receiving the same probes, which provides evidence that the benefits of SPSC are not only attributable to access to additional measurements.

Critical weaknesses
  1. I found the practical motivation for the probing mechanism insufficiently supported. It is not clear to me in what practical situations probing would be available in the first place, and to my knowledge, this mechanism is not standard in the low-rank or nonstationary linear bandit literature. In Appendix A.4 (“Costly information and probing”), the authors cite works where the learner pays to receive reward feedback, but this is not directly related to the probing mechanism considered. The examples of lines 185–187 would benefit from a more detailed explanation of how they provide the assumed queries and responses. The authors also both argue that i) probing is needed to recover the subspace (lines 71–77) ii) a suitable sampling design within the feasible action sets could replace the probes (lines 187–188). It is unclear to me under what conditions probing outside the feasible action sets is needed for their guarantees.

  2. More importantly, I have concerns about both the theoretical and empirical comparisons with baselines.

On the theoretical side, I am not convinced that the main regret guarantee of Theorem 4.1 improves on direct mean estimation. If we denote by μk\mu_k the mean on IkI_k, and set μ^j=j−1∑i=1juiyi\widehat\mu_j=j^{-1}\sum_{i=1}^j u_i y_i for the first jj probes in IkI_k, we should have E[uy]=μk\mathbb{E}[uy]=\mu_k and E∣μ^j−μk∣2≲d/j\mathbb{E}\\|\widehat\mu_j-\mu_k\\|^2\lesssim d/j. Selecting xt∈arg⁡max⁡x∈Atx⊤μ^jx_t\in\arg\max_{x\in\mathcal A_t}x^\top\widehat\mu_j should thus incur expected regret O(d/j)O(\sqrt{d/j}), while each probe contributes O(1)O(1) expected regret. With mkm_k evenly spaced probes in IkI_k, this yields O(mk+∣Ik∣d/mk)O(m_k+|I_k|\sqrt{d/m_k}) expected regret for interval IkI_k, which I believe after optimizing over mkm_k and summing over kk yields O(d1/3K1/3T2/3)O(d^{1/3}K^{1/3}T^{2/3}) expected regret. This appears to improve on the stated O~(rKT+(rd)1/3K1/3T2/3)\widetilde O(r\sqrt{KT}+(rd)^{1/3}K^{1/3}T^{2/3}) bound. I would therefore like to understand what advantage subspace estimation provides over this baseline in the main theorem's setting.

On the empirical side, the comparisons with BOSS [1] and the “Jedra” [2] baseline, which I assume should be RS-RMIN, are difficult to interpret, because the authors' adaptations seem to depart substantially from the original algorithms. The authors state in Appendix F.2 (lines 2018–2020) that both implementations learn a subspace in their first 200 rounds and then run projected LinUCB. From looking at the code provided by the authors, the BOSS adaptation seems to replace its mechanism for learning a shared representation across tasks with SPSC’s estimator. Additionally, the RS-RMIN adaptation does not appear to retain its key principle, which is a reduction to a misspecified linear bandit. The paper would benefit from explaining more clearly how these baselines have been adapted to the present setting.

[1] Thang Duong, Zhi Wang, and Chicheng Zhang. Beyond task diversity: provable representation transfer for sequential multitask linear bandits. Advances in Neural Information Processing Systems, 37:37791--37822, 2024

[2] Yassir Jedra, William Réveillard, Stefan Stojanovic, and Alexandre Proutiere. Low-rank bandits via tight two-to-infinity singular subspace recovery. In International Conference on Machine Learning, pp. 21430–21485. PMLR, 2024.

Questions for authors
  1. Can you describe in more detail in what practical settings your probing model is justified?
  2. Did I miss something in the direct-mean estimation regret argument above? If not, how does this baseline compare with SPSC on the reported benchmarks?
  3. Can you provide more details on how BOSS and RS-RMIN have been adapted to the setting of the paper?
Reviewer_iN7YOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

The paper considers a linear bandit variant where the true θ\theta lies in an unknown low rank subspace (dimension rr where the ambient dimension is dd) which changes every now and then. The learner can probe the subspace for a fee and a turn. The result is a d1/3T2/3+rTd^{1/3}T^{2/3} + r\sqrt{T} regret based on an algorithm that probes the subspace isotropically and independently of the noise.

Critical strengths

I believe the claims are sound.

Critical weaknesses

The d1/3T2/3d^{1/3}T^{2/3} term is described as an "additive term" in the abstract, yet traditionally would be considered to be the dominant term in the regret - not only does it have a dd dependence, it is also a worse exponent for TT. The statement that the T\sqrt{T} only depends on rr is actually the worse case scenario in that sense.

I am not clear on the motivation. What is the motivation for being able to probe this subspace?

The paper can benefit from a rewrite. Some sections are worded strangely, for instance, there is subsection of the experiments

SPSC beats LinUCB on 37 of the 40 cells, losing only at the smallest dimensions The 40 points are chosen somewhat arbitrarily - it might make more sense to just characterize which (r,d)(r,d) win over LinUCB - there need not be such a graphic and the statistic 37/40 is unnecessary here.

Questions for authors

Why is the probe norm d\sqrt{d}? I think this is to make it informative on average, but it makes it even harder to appreciate the motivation.

What happens when the actions space is just the unit ball? This makes it such that one can directly trade off the probe actions as regular actions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.