- Rating
- 1
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
The paper considers a contextual bandit where one known block of features enters linearly and the rest enter through an unknown RKHS function. PartLinUCB estimates both parts with a jointly regularized least-squares problem, uses residualized features for the confidence bound, and selects actions optimistically. The authors claim that the rate recovers the linear and kernel cases and is nearly minimax for the RBF kernel. Experiments are on synthetic problems and MovieLens.
Critical strengths
The model is a sensible extension of linear and kernelized bandits, and the residualization used to get a usable confidence bound is the main technical contribution here. The supplementary material also shows that the proof is developed in detail, rather than just referring to a standard elliptical potential argument. The 20-run synthetic study is a reasonable first check.
Critical weaknesses
The asymptotic statement after Theorem 3 does not match Remark 3. The theorem prints roughly \tilde O(\sqrt{T\max{p,d_{\rm eff}}}(p+d_{\rm eff})), while Remark 3 says the regret is additive: O(p\sqrt T)+O(d_{\rm eff}\sqrt T). The proof in Appendix C seems to lead to the additive form, so I suspect the displayed simplification is wrong, but this is exactly the rate used for the main optimality claim. The paper needs one corrected statement and a clear derivation of the bound from E_T and L_T.
Even setting that aside, the experiments are not very informative about the proposed structure. Remark 1 itself notes that one can use the additive kernel k_+, but there is no additive-kernel UCB baseline. There is also no p=0/q=0 or deliberately mispartitioned case, and varying p and q on the unit sphere changes the scale of the nonlinear component at the same time. I cannot tell how much of the gain is from the partially linear construction versus a favorable kernel scale. MovieLens also needs more detail about whether the 10 candidates are from the same user and how the SVD features were fitted.
Questions for authors
- Which rate is the intended statement of Theorem 3? Please make the theorem, Remark 3, and the Appendix C derivation agree.
- Could you add the additive-kernel UCB baseline and the p=0, q=0, and mispartitioned-feature experiments?
- In the synthetic study, can you keep the total signal scale fixed while varying p and q?
- For MovieLens, are the 10 candidates drawn from one user, and were the SVD embeddings fitted without using the evaluation interactions?