Nested Model Selection in Linear Contextual Bandits via Exploration and Comparison

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 $d$-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 $K$ arms and horizon $n$, both algorithms retain the standard $\tilde{O}(\sqrt{Kn})$ 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.