acceptodds
Under review as a conference paper at ICLR 2027

Nested Model Selection in Linear Contextual Bandits via Exploration and Comparison

Abstract

We study nested model selection in stochastic linear contextual bandits with an unknown intercept for each arm and an unknown contextual parameter. The contextual parameter may be zero, may lie in a low-dimensional subspace, or may require the full -dimensional space, and the goal is to achieve regret comparable to an oracle that knows the smallest subspace containing this parameter. The main challenge is that arm selection depends on the observed contexts, which can bias the data used for model selection. We first show that the assumptions used in prior work do not prevent this issue, and construct an instance on which the prior method incurs linear regret. To address this challenge, we propose two algorithms, SST-UCB and SSC-UCB, that use uniform exploration to obtain reliable observations for estimating the contextual parameter. SST-UCB selects the smallest subspace that is compatible with the observations, while SSC-UCB further compares the rewards obtained by learners at different levels and can control regret without identifying the true subspace exactly. For arms and horizon , both algorithms retain the standard regret when contexts do not affect rewards, while adapting their leading regret term to the dimension of the smallest valid subspace when contexts matter. We further prove lower bounds showing that the guarantee of SSC-UCB is optimal up to logarithmic factors when the dimension of the smallest valid subspace does not exceed the number of arms.

Primary area:
learning theory
Keywords:
multi-armed bandits, linear bandits, model selection

Reviews

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

This work studies nested model selection in stochastic linear contextual bandits with arm-specific intercepts and a shared contextual parameter, assuming a known hierarchy of nested subspaces. The authors identify two issues with OSOM. The first is that adaptively selected contexts need not preserve the marginal covariance structure used in OSOM's analysis, and the second is that context-dependent arm selection can bias estimates of arm intercepts. They provide counterexamples, including an instance where OSOM incurs linear regret.

To address these two issues, the authors propose SST-UCB and SSC-UCB, both using uniform exploration to obtain reliable observations. SST-UCB selects the smallest subspace compatible with a confidence set, while SSC-UCB additionally compares the rewards obtained by learners at different candidate levels, without exact identification of the true subspace. Both achieve regret bounds whose leading terms depend on the unknown true subspace dimension dℓ∗d_{\ell^\ast} rather than the full contextual dimension dd. Specifically, SSC-UCB achieves a subspace-gap independent bound that matches the presented lower bound up to logarithmic factors when dℓ∗≤Kd_{\ell^*} \le K.

Critical strengths
  • The work identifies substantive issues in OSOM and shows that the algorithm can incur linear regret even under its original assumptions. In particular, the authors show how context-dependent arm selection can bias intercept estimates and lead to algorithmic failure. This can be an important contribution because it shows that the problem is not just a gap in the previous analysis, but an actual limitation of the existing algorithm.

  • SSC-UCB, one of the proposed algorithms, provides a regret bound that is independent of the subspace gap without requiring exact identification of the true subspace. Its leading regret term depends on the unknown true subspace dimension rather than the potentially much larger full contextual dimension. The bound also matches the paper's minimax lower bound up to logarithmic factors when dℓ∗≤Kd_{\ell^*}\le K. This can be a significant contribution, even though the nested subspace hierarchy is assumed to be known, because the proposed algorithm is well motivated and provides a near-optimal regret guarantee in this setting.

Critical weaknesses
  • The experimental evaluation does not sufficiently address the setting where model selection could provide the greatest benefit. All experiments use K=100K=100 and d=20d=20, with true subspace dimensions of 0, 5, and 20. The work does not explore settings with a substantially larger gap between the full contextual dimension and the true subspace dimension, particularly when d>Kd>K. In the paper's setting, full-dimensional SupLinUCB already achieves the same theoretical regret order as a learner using the true subspace dimension, and it outperforms SSC-UCB in both contextual experiments. I would have found an evaluation in such a high-dimensional regime more informative as it seems especially relevant to demonstrating the practical benefit of the proposed method.

  • The released experimental configuration appears to differ from Section 7. The paper reports 10 seeds and randomly generated Gaussian parameters, while the supplementary code uses 5 seeds and fixed sparse parameters. Unless I am missing a separate configuration used for Figure 1, these differences raise concerns about the reproducibility of the experiments.

Questions for authors
  • How do the authors expect SSC-UCB to benefit from model selection in finite-sample settings similar to those in Section 7, but with dd much larger (e.g., d=200d=200) than the true subspace dimension, particularly when d>Kd>K?

  • Could the authors clarify the discrepancy between Section 7, which reports 10 seeds and randomly generated Gaussian parameters, and the released code, which appears to use 5 seeds and fixed sparse parameters?

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

The paper studies nested model selection for linear contextual bandits with an unknown intercept per arm. It first argues that the context distribution assumptions used by OSOM do not justify the selected-design argument and that the intercept estimator can be biased. It then proposes SST-UCB and SSC-UCB, which use uniform exploration and compare learners at different subspace levels. The main results are regret bounds adapting to the true dimension and matching lower bounds in a certain regime.

Critical strengths

The most interesting part is the OSOM discussion. The observation that selecting an arm after seeing its context can invalidate the marginal covariance argument seems real, and the linear-regret example for the biased intercept estimate is a useful warning. SSC-UCB also makes sense conceptually: it avoids insisting on identifying the exact subspace when a smaller model already makes nearly the same decisions.

Critical weaknesses

The comparison with prior model-selection work is too thin for the claim being made. Foster et al. 2019, Muthukumar & Krishnamurthy 2022, and Ghosh et al. 2024 are mentioned in one short paragraph. I need an explicit table of assumptions and rates to understand whether the improvement comes from the algorithm or from the stronger assumptions here, especially the known fixed subspaces and well-conditioned marginal contexts.

The experiments also do not show where this method is supposed to win. With K=100 and true dimension 5, full-dimensional SupLinUCB still has the lowest regret, so the adaptive advantage is not visible. There is no small-gap study, no model-selection accuracy, and no comparison to the closest prior algorithms. I would at least want a setting with d_true much smaller than d and a regime where SupLinUCB is clearly paying for the ambient dimension.

Questions for authors
  1. Can you compare your assumptions and rates directly with Foster et al. 2019, Muthukumar & Krishnamurthy 2022, and Ghosh et al. 2024?
  2. Which part of the improvement is due to the uniform-exploration design and which is due to the stronger fixed-subspace assumptions?
  3. Can you add experiments with d_true << d, smaller K, and a sweep over the subspace gap, and report how often the correct level is retained?
  4. Does the lower bound use one instance with both difficulties, or combine two separate hard instances?
Reviewer_vzbtOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies nested model selection in stochastic linear contextual bandits. At each round, the learner observes a dd-dimensional context for each of KK arms, chooses one arm, and observes its reward. The expected reward is μi+⟨θ⋆,αi,t⟩\mu_i + \langle \theta^{\star}, \alpha_{i,t} \rangle, where μi\mu_i is an arm-specific baseline and θ⋆\theta^{\star} is an unknown shared parameter. The learner is given a sequence of known nested subspaces and aims to adapt to the smallest one containing θ⋆\theta^{\star}.

The authors identify a flaw in the prior OSOM algorithm and construct a counterexample where it incurs linear regret. They propose two algorithms, SST-UCB and SSC-UCB, both achieving O~(Kn)\widetilde{O}(\sqrt{Kn}) regret when θ⋆=0\theta^{\star}=0. Their stronger algorithm, SSC-UCB, achieves O~((K+d⋆)n)\widetilde{O}(\sqrt{(K+d^{\star})n}) regret when d⋆≤Kd^{\star} \leq K, where d⋆d^{\star} is the dimension of the smallest valid subspace. This matches their minimax lower bound up to logarithmic factors, without dependence on the separation between models.

Critical strengths

S1 — Counterexample to a prior theoretical guarantee

The paper identifies a flaw in OSOM (Chatterji et al., 2020), which claimed simultaneous gap-dependent logarithmic regret for ordinary multi-armed bandits and O~((K+d)n)\widetilde{O}(\sqrt{(K+d)n}) regret for linear contextual bandits. The authors provide a counterexample satisfying OSOM's original assumptions on which the algorithm incurs linear regret, invalidating its contextual regret guarantee. This is a substantive correction to a previously published theoretical result.

S2 — Near-optimal regret for nested model selection

The authors propose SSC-UCB, which achieves O~((K+d⋆)n)\widetilde{O}(\sqrt{(K+d^{\star})n}) regret when d⋆≤Kd^{\star} \leq K, matching the regret rate achievable when the correct subspace is known in advance. The guarantee is independent of the separation between candidate models and matches the paper's minimax lower bound up to logarithmic factors. This strengthens earlier results for nested model selection that incurred separation-dependent regret penalties.

Critical weaknesses

W1 — Missing comparisons with prior nested model-selection algorithms

The experiments in Section 7 compare against OSOM, UCB, and SupLinUCB, but omit existing nested model-selection algorithms, particularly ALB-Dim (Ghosh et al., 2024) and the nested-model extension of Muthukumar and Krishnamurthy (2022). Direct theoretical and empirical comparisons are important for establishing the significance of the proposed improvement, especially as model separation varies.

W2 — Significance of the optimality regime

The main separation-free regret guarantee is minimax optimal when d⋆≤Kd^{\star} \leq K. However, if this inequality is known, one can simply run SupLinUCB on the largest candidate subspace of dimension at most KK, obtaining the same O~(Kn)\widetilde{O}(\sqrt{Kn}) regret order without model selection. The value of adaptation is therefore in handling both small and large true dimensions without knowing the regime in advance. Yet when d⋆>Kd^{\star}>K, the separation-free guarantee is no longer minimax optimal. Moreover, the experiments use d=20<K=100d=20<K=100, where full-dimensional SupLinUCB already achieves the oracle-order rate and empirically outperforms SSC-UCB. This leaves the practical advantage of nested adaptation insufficiently demonstrated.

Questions for authors

Q1. Could the authors provide theoretical and empirical comparisons with existing nested model-selection algorithms, particularly ALB-Dim (Ghosh et al., 2024) and the nested-model extension of Muthukumar and Krishnamurthy (2022), including varying the separation between models?

Q2. Could the authors clarify the advantage of SSC-UCB over a fixed-subspace strategy when d⋆≤Kd^{\star}\leq K, and provide experiments with d≫Kd\gg K and true dimensions on both sides of KK? Such experiments would help establish the benefit of adapting to an unknown model complexity.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.