acceptodds
Under review as a conference paper at ICLR 2027

Partially Linear Contextual Bandits

Abstract

In contextual bandit problems, traditional methods for modeling the context–reward relationship typically employ either fully parametric or nonparametric approaches. Parametric approaches are computationally efficient and simple to implement, but they rely on restrictive assumptions that may not hold in complex real-world scenarios. Nonparametric methods offer greater flexibility, but may not fully leverage clear underlying patterns that could otherwise improve prediction. In this work, we bridge these two paradigms by proposing a partially linear model for the expected reward, in which a designated subset of contextual features influences the reward linearly while the remaining features act on it through an unknown function belonging to a reproducing kernel Hilbert space. We introduce PartLinUCB, an algorithm designed for this partially linear reward model. PartLinUCB naturally encompasses both linear and kernelized bandits as special cases, yielding a unified regret guarantee that recovers the established rates for each when the context–reward relationship is fully linear or fully nonparametric, respectively. We further establish that PartLinUCB is nearly minimax optimal for the radial basis function (RBF) kernel by deriving a lower bound that matches our regret upper bound up to logarithmic factors. Empirical studies demonstrate that PartLinUCB outperforms representative baseline methods and highlight the practical utility of the partially linear approach.

Primary area:
learning theory
Keywords:
Contextual bandits, partially linear reward models, UCB algorithms, kernel methods, regret analysis, minimax optimality

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_5yjkOpenReview ↗
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
  1. Which rate is the intended statement of Theorem 3? Please make the theorem, Remark 3, and the Appendix C derivation agree.
  2. Could you add the additive-kernel UCB baseline and the p=0, q=0, and mispartitioned-feature experiments?
  3. In the synthetic study, can you keep the total signal scale fixed while varying p and q?
  4. For MovieLens, are the 10 candidates drawn from one user, and were the SVD embeddings fitted without using the evaluation interactions?
Reviewer_xVFsOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary
  • This paper studies a contextual bandit problem where the context vector associated with each action is split into two parts: a linear block xt,a∈Rpx_{t,a}\in\mathbb R^p and a nonlinear block zt,a∈Rqz_{t,a}\in\mathbb R^q.

    • The partition into xt,ax_{t,a} and zt,az_{t,a} is assumed to be fixed and known to the learner.
    • The expected reward is modeled as the sum of a linear term ⟨xt,a,θ\*⟩\langle x_{t,a}, \theta_\* \rangle and a nonparametric term f\*(zt,a)f_\*(z_{t,a}), where f∗f_* is an unknown function in the RKHS Hk\mathcal H_k of a known kernel kk.
    • The authors point out that prior work on semiparametric bandits typically treats the nonparametric component as independent of action features (e.g., a global time-varying bias or an arm-specific offset).
    • Instead, because the nonparametric term f\*(zt,a)f_\*(z_{t,a}) here depends explicitly on action-specific features, it varies across actions within a round and cannot be eliminated via action centering.
  • The proposed algorithm, PartLinUCB, jointly estimates (θ\*,f\*)(\theta_\*, f_\*) via double-penalized least squares with separate ridge penalties on θ\theta and ff, yielding the closed-form solution in Theorem 1 (Line 259-268).

    • It then builds confidence sets for both θ\*\theta_\* and f\*f_\* and selects actions optimistically using the UCB bonus defined in Eq. (8) (Line 321).
  • The authors argue that, because the estimators (θ^t,f^t)(\widehat \theta_t, \widehat f_t) are coupled, the standard self-normalized concentration inequality (Abbasi-Yadkori et al., 2011) cannot be applied directly.

    • The analysis therefore residualizes the features and the noise, developing a "compensated self-normalized" supermartingale argument.
    • This argument yields confidence sets for θ\*\theta_\* and f\*f_\* that hold simultaneously on a single event, as presented in Theorem 2 (Line 285-293).
  • The paper establishes a high-probability regret bound of O~(Tmax⁡p,deff(p+deff))\widetilde{O}(\sqrt{T\max\\{p, d_{\mathrm{eff}}\\}(p + d_{\mathrm{eff}})}) for the algorithm PartLinUCB, where deffd_{\mathrm{eff}} is the effective dimension of the kernel.

    • Theorem 4 (Line 363-371) complements this with worst-case expected regret lower bounds for the RBF and Matérn kernels, and the authors claim that their algorithm is nearly minimax optimal for the RBF kernel.
  • Numerical experiments on synthetic problems and the MovieLens 1M dataset show that PartLinUCB consistently achieves lower cumulative regret than the non-oracle baselines.

Critical strengths
  1. The paper clearly explains why a partially linear model is a natural middle ground by contrasting two extremes, a fully linear (or parametric) model and a fully nonparametric model, and pointing out the limitations of each (Line 42-53).

    • Section 2 also clearly distinguishes this setting from prior semiparametric bandit models: because the nonlinear term f\*(zt,a)f_\*(z_{t,a}) varies across actions within a given round, it cannot be eliminated via action centering (Line 139-143).
  2. For the RBF and Matérn kernels, Theorem 4 shows that the minimax regret of the problem considered in this paper is at least of the order of the sum of the lower bounds for pp-dimensional linear bandits and for kernelized bandits.

    • As the authors note, because both the linear and nonlinear components are observed through a single scalar reward, this additive lower bound does not follow trivially from combining existing bounds for each problem (Line 377-384). Instead, the authors construct a joint family of hard instances that perturbs both components simultaneously, and the resulting proof appears sound.
    • For the RBF kernel, this lower bound matches the upper bound up to polylogarithmic factors.
    • The authors provide a general lower bound for kernels and domains admitting a family of well-separated functions in the RKHS ball (Appendix D).
  3. The experimental design is informative: synthetic experiments cover 9 configurations of (p,q)(p,q) and two reward models, and an experiment on a real-world dataset is also included.

Critical weaknesses
  1. The novelty claims are overstated, and related work is partly missing.

    • The authors state that their work brings the partially linear model from the fixed-sample statistical setting to sequential decision-making with adaptively collected data (Line 153-154).
    • However, Bu et al. (2022) already study partially linear models for online decision-making with adaptively collected data in the context of dynamic pricing.
    • Specifically, they model expected demand as either bpt+g(xt)b p_t + g(x_t) with a Hölder function gg or f(pt)+a⊤xtf(p_t) + a^\top x_t with a smooth function ff, establishing regret upper bounds along with matching lower bounds. This work is not cited in the paper.
    • Of course, the settings do differ in that Bu et al. (2022) study dynamic pricing where the action is the posted price itself, the context xtx_t is shared across actions, and the function class is Hölder rather than RKHS as in this work.
    • So I do not think this work is subsumed by Bu et al. (2022). Still, I would ask the authors to reexamine the novelty claims (Line 76-78 and 153-154) and to discuss the relation to their work.
  2. The estimator is the same, and the confidence sets follow from the kernelized bandit problems, so it is unclear to me why the new analysis is needed.

    • Remark 1 (Line 209-215) notes that the model in this work can be viewed as a kernelized bandit with the additive kernel denoted by k+k_+, and that generic kernel-bandit algorithms could be run with k+k_+. However, the paper does not compare against this baseline, and the estimator and confidence sets of PartLinUCB are the same as those of a kernelized bandit with a scaled additive kernel, which reduces to k+k_+.
    • For the estimator, substituting θ′=λθ\theta' = \sqrt{\lambda}\theta and f′=γff' = \sqrt{\gamma}f into Eq. (3) shows that the coupled estimator (θ^t,f^t)(\hat \theta_t, \hat f_t) is exactly the estimator of kernel ridge regression under a kernel defined as k~((x,z),(x′,z′)):=⟨x,x′⟩/λ+k(z,z′)/γ\tilde{k}((x,z),(x',z')) := \langle x, x' \rangle/\lambda + k(z,z')/\gamma. With λ=γ=1\lambda = \gamma = 1, as in the experiments (Line 421), k~=k+\tilde{k} = k_+.
    • For the confidence ellipsoids, I think we can treat (θ,f)(\theta, f) as a single element of the direct sum Rp⊕Hk\mathbb{R}^p \oplus \mathcal{H}_k. Then the corresponding Gram matrix can also be constructed with an augmented feature (xs,ϕ(zs))∈Rp⊕Hk(x_s, \phi(z_s)) \in \mathbb{R}^p \oplus \mathcal{H}_k.
      • Under this joint view, each noise variable is paired with a predictable joint feature. Thus, existing kernelized self-normalized concentration results, such as Theorem 1 and Lemma 1 of Chowdhury & Gopalan (2017), can be applied to the scaled additive kernel.
    • Therefore, I think that the same confidence sets can be obtained by applying existing techniques, contrary to the paper's claim that the standard self-normalized inequality does not apply to the coupled estimator (Line 83-84, 161-163, and 304-307).
    • I do not see what the compensated self-normalized argument provides beyond this joint analysis, i.e., applying the standard self-normalized bound to (θ,f)(\theta, f) as a single element of Rp⊕Hk\mathbb{R}^p \oplus \mathcal{H}_k. If the authors can clarify a concrete advantage, it would help me understand the technical contribution of this work.

References

  • Bu et al., (2022). Context-Based Dynamic Pricing with Partially Linear Demand Model.
  • Chowdhury & Gopalan, (2017). On kernelized multi-armed bandits.
Questions for authors
  1. How do the model and results differ from Bu et al. (2022)?

  2. Would applying the standard kernelized self-normalized concentration bound directly to (θ,f)(\theta, f) as a single element in Rp⊕Hk\mathbb{R}^p \oplus \mathcal{H}_k yield Theorem 2? If not, what technical obstacle prevents this, and what specific advantage does the compensated self-normalized argument offer beyond this joint analysis?

  3. In the experiments, which exact kernel is used for the KernelUCB baseline? If possible, could the authors include KernelUCB with the additive kernel k+k_+ as an empirical baseline?

  4. Eq. (2) defines RegT\mathrm{Reg}_T as an expectation, whereas Theorem 3 (Line 330-336) is a high-probability statement. In Appendix C, Proposition C.6 bounds E[RegT]\mathbb{E}[\mathrm{Reg}_T], which suggests that RegT\mathrm{Reg}_T is treated there as a random quantity.

    • Does Theorem 3 in fact bound the pseudo-regret ∑t=1T(⟨xt,at∗,θ∗⟩+f∗(zt,at∗)−⟨xt,θ∗⟩−f∗(zt))\sum_{t=1}^T \big( \langle x_{t,a_t^\ast}, \theta_\ast \rangle + f_\ast(z_{t,a_t^\ast}) - \langle x_t, \theta_\ast \rangle - f_\ast(z_t) \big)? If so, I suggest defining RegT\mathrm{Reg}_T in Eq. (2) as this pseudo-regret and referring to the expected-regret bound in Proposition C.6 (Line 1347-1356) in the main text.
Reviewer_ze4QOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies contextual bandits with reward mean x⊤θ∗+f∗(z)x^\top\theta_*+f_*(z), where the linear/nonlinear feature partition is known and f∗f_* lies in the RKHS of a known kernel. PartLinUCB combines joint penalized least squares with an optimistic action rule. The analysis gives component confidence sets, a regret upper bound of order O~((p+deff)T)\widetilde O((p+d_{\mathrm{eff}})\sqrt T), and lower bounds combining the linear and kernel components. The main claimed technical contribution is a compensated self-normalized argument for the coupled estimator. My assessment focuses on the theoretical contribution.

Critical strengths

The model is coherent when the feature partition is known. The block formulas make the relation between the two fitted components explicit. The supplementary lower-bound analysis also provides a concrete joint family and a squared-sinc construction with controlled overlap. These are useful derivations, even though I find their theoretical increment limited.

Critical weaknesses
  1. The central estimation and upper-bound results do not establish an advance over applying existing analysis to the additive kernel. Remark 1 acknowledges the kernel representation, but the subsequent comparison to a generic kernel on all coordinates does not address the appropriate baseline. For arbitrary fixed λ,γ>0\lambda,\gamma>0, define

    ψ(x,z)=(x/λ,ϕ(z)/γ),w=(λθ,γf).\psi(x,z)=\left(x/\sqrt\lambda,\phi(z)/\sqrt\gamma\right), \qquad w=(\sqrt\lambda\theta,\sqrt\gamma f).

    Equation (3) is exactly ordinary ridge regression in Rp⊕Hk\mathbb R^p\oplus\mathcal H_k, with kernel

    k~((x,z),(x′,z′))=x⊤x′/λ+k(z,z′)/γ.\widetilde k((x,z),(x',z'))=x^\top x'/\lambda+k(z,z')/\gamma.

    Its Gram matrix satisfies I+K~=M/γI+\widetilde K=M/\gamma, so the usual joint self-normalized bound produces the same log-determinant appearing in (7). The joint feature is predictable, and its covariance grows by one rank-one update per round. The nonpredictable weights arising after profiling out one component therefore do not prevent applying the existing RKHS self-normalized analysis to the joint problem; see Chowdhury and Gopalan (2017, Theorem 1 and Lemma 1). The component ellipsoids in Theorem 2 follow by projecting the joint ellipsoid using Schur complements.

    This also addresses the exploration argument. Appendix C, Lemma C.2, identifies the joint prediction width as at2+ct2\sqrt{a_t^2+c_t^2}, while (8) uses at+cta_t+c_t. The latter is between one and 2\sqrt2 times the former. Thus the proposed bonus is a constant-factor enlargement of the ordinary joint ridge width, rather than a distinct way to overcome a failure of the standard potential argument. Finally,

    log⁡det⁡(I+XX⊤/λ+K/γ)≤log⁡det⁡(I+XX⊤/λ)+log⁡det⁡(I+K/γ)=O~(p+deff).\log\det(I+XX^\top/\lambda+K/\gamma) \le \log\det(I+XX^\top/\lambda)+\log\det(I+K/\gamma) =\widetilde O(p+d_{\mathrm{eff}}).

    Standard optimism and the joint potential argument consequently give the displayed order in Theorem 3. The compensated proof may be an alternative derivation, but the paper has not shown a stronger guarantee, broader assumption class, or necessary new concentration result beyond this reduction. Separate coordinate formulas alone are insufficient to establish the advertised technical advance.

  2. The additive lower bound does not improve on the order already implied by the two known subclasses. Theorem 4 and its discussion explicitly identify the linear and kernel terms as known lower bounds. Let these terms be ATA_T and BTB_T. Setting f=0f=0 gives the linear subclass; setting θ=0\theta=0 gives the kernel subclass on the same product action domain. Hence the minimax regret is already bounded below by max⁡{c1AT,c2BT}\max\{c_1A_T,c_2B_T\}, which is at least min⁡(c1,c2)(AT+BT)/2\min(c_1,c_2)(A_T+B_T)/2. This proves the stated Ω(AT+BT)\Omega(A_T+B_T) order without a joint hard family. The construction in Appendix D.4 does additionally place both contributions under one averaging distribution, but that is a stronger property of the construction, not an improved minimax rate in Theorem 4. The squared-sinc alternatives and the finite/unbounded-domain extensions provide additional derivations, but I do not think these extensions make up for the limited novelty of the main results. In particular, the Matérn upper/lower gap remains, as the paper acknowledges.

References

  • Chowdhury and Gopalan (2017), On Kernelized Multi-armed Bandits, Theorem 1, Lemma 1, and Theorems 2–3. The contextual action sets here require restricting each optimistic maximization to the currently available feature vectors; the joint confidence event and potential argument remain applicable.
  • Scarlett, Bogunovic, and Cevher, Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization, corrected arXiv version dated 31 May 2018, Theorem 2. This is the version supporting the T(log⁡T)q/4\sqrt T(\log T)^{q/4} RBF and T(ν+q)/(2ν+q)T^{(\nu+q)/(2\nu+q)} Matérn terms used here.
Questions for authors
  1. Which conclusion of Theorems 1–3 cannot be obtained by ordinary joint ridge/UCB analysis with k~=x⊤x′/λ+k(z,z′)/γ\widetilde k=x^\top x'/\lambda+k(z,z')/\gamma? Please identify a precise assumption or quantitative guarantee that improves upon this baseline.
  2. Beyond proving both contributions within one hard family, what conclusion of Theorem 4 is stronger than the subclass argument above? If the main novelty is instead a reusable lower-bound construction or a domain extension, what substantial new result does it enable?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.