- 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 rather than the full contextual dimension . Specifically, SSC-UCB achieves a subspace-gap independent bound that matches the presented lower bound up to logarithmic factors when .
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 . 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 and , 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 . 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 much larger (e.g., ) than the true subspace dimension, particularly when ?
-
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?