acceptodds
Withdrawn from ICLR 2027

Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Experts

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Modern recommendation systems increasingly rely on dynamically routing diverse queries to multiple embedding models. Despite its practical significance, this problem remains poorly understood under realistic conditions like adversarial queries, bandit feedback, and limited observability of models. We formalize embedding model routing as an adversarial contextual linear bandit with low-rank experts, where contexts are queries, actions are items, and experts are the embedding models working on low-rank latent representation spaces. We first establish that standard regret notions suffer from structural misspecification or statistical intractability, and we identify a *log-quadratic* policy class that is expressive enough to capture query-dependent model routing, yet structured enough to allow efficient online learning. Focusing on this log-quadratic policy optimization problem under bandit feedback – which is of independent interest – we propose a policy gradient algorithm called Hypentropy Policy Gradient (HPG). It provably adapts to the unknown low-rank structure under incomplete information and attains linearized policy regret – where , and are the intrinsic rank of the experts, the number of models, and the number of rounds – thus avoiding a curse of dimensionality. We provide computationally efficient and parameter-free implementation of HPG.

Primary area:
learning theory
Keywords:
contextual bandits, bandits with experts, policy regret, policy gradient methods, embedding model routing

Reviews

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

This paper studies online embedding-model routing under limited feedback, formulating it as an adversarial contextual bandit with unknown low-rank experts: at each round, the learner selects one model for the query and observes only that model's recommendation and a noisy reward. Under the stated assumptions, the authors derive a low-rank quadratic approximation to each model's expected reward, which motivates a class of softmax routing policies with quadratic scores.

To optimize this class online, the paper proposes Hypentropy Policy Gradient (HPG), which combines a REINFORCE-type gradient estimator with hypentropy mirror descent under a nuclear-norm constraint. For comparators satisfying the corresponding nuclear-norm condition, the authors establish an O~(sMT)\widetilde{O}(s\sqrt{MT}) bound on the linearized policy regret, together with an O(Mdq2)O(Md_q^2) per-round implementation and a variant that does not require knowledge of the rank ss. Offline experiments on Amazon ESCI indicate that quadratic routing achieves a smaller average reward gap than fixed-model and linear routing.

Critical strengths
  1. Well-motivated setting. The single-model-per-round formulation jointly captures adversarial queries, bandit reward feedback, and partial observability of expert outputs, reflecting practical concerns such as invocation cost and missing counterfactual feedback within a clean mathematical framework.

  2. Principled justification for quadratic routing. Proposition 1 links the experts' low-rank structure to their expected rewards, yielding a decomposition into a shared term, a low-rank quadratic term, and a controlled residual. This grounds the choice of quadratic scores in the structure of the experts rather than in empirical expressiveness alone.

  3. Coherent algorithmic design. HPG pairs single-sample gradient estimation with mirror descent suited to nuclear-norm constraints. The authors further exploit rank-one updates and spectral structure for efficiency, and extend the method to the unknown-rank setting.

Critical weaknesses
  1. Scope of the theoretical guarantees. The theorems impose a nuclear-norm condition on the comparator, but the correspondence among the policy class in Eq. (5), the comparator class in Eq. (9), and the constraint used in the proofs could be made more explicit. Since the reward-approximation matrix and the routing parameters play different roles, and the score scaling in Eq. (6) affects the magnitude of the latter, clarifying these relationships would delineate which policies the guarantees cover.

  2. Link to online performance. The authors candidly distinguish linearized regret from true policy regret (§3.2, Appendix C.5). Still, the current guarantees do not directly yield bounds on the true policy regret, i.e., the gap in cumulative expected reward relative to the comparator, and Table 2 evaluates policy-class expressiveness offline rather than the online behavior of HPG. A small-scale online cumulative-reward comparison would help assess the practical effect of the proposed update rule, without requiring the authors to resolve the open theoretical questions they identify.

Questions for authors
  1. Does the comparator class in Eq. (9) include the nuclear-norm constraint, and how does it relate to the "optimal parameter" in Theorem 3? How is the score scaling in Eq. (6) reflected in the nuclear-norm condition required by the analysis: is it a separate assumption on the comparator, or can it be derived from the structural result?

  2. Do the authors have cumulative-reward results for HPG under single-model bandit feedback? If feasible, a small-scale comparison on the existing data against standard (e.g., projected) gradient updates with the same quadratic parameterization and constraint would help isolate the benefit of the proposed update.

  3. Could the authors specify the solution procedure and parameter constraints for each policy in Table 2, and clarify whether the "optimal policy" denotes the numerical solution obtained or rests on a further optimality justification? Is a nuclear-norm constraint imposed on the quadratic policy? This would clarify how the experiment supports the expressiveness of general quadratic policies versus the constrained class considered in the theory.

Reviewer_msx1OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies an online routing problem over TT rounds. At round tt, the learner observes a query qt∈Rdqq_t\in\mathbb R^{d_q}, selects one of MM embedding models, and observes the item at∈Rdaa_t\in \mathbb R^{d_a} recommended by the selected model and a noisy reward. It is assumed that the embedding models map queries and items into spaces of dimension at most s≪min⁡(dq,da)s\ll\min(d_q,d_a). The authors show that each model’s expected reward is nearly quadratic in the query, which, along with empirical evidence that the best log-quadratic policy has a small reward gap to the best unrestricted policy, motivates restricting to a log-quadratic policy class. Their proposed algorithm, HPG, combines a policy-gradient estimator with online mirror descent. Assuming the optimal policy can be represented by matrices with nuclear norm at most 2s2s, they provide a O(sMTlog⁡dq)O(s\sqrt{MT\log d_q}) guarantee for a surrogate version of regret. They also show that HPG can be implemented in O(Mdq2)O(Md_q^2) time per round.

Critical strengths

The routing problem considered is interesting and the exposition is generally clear. In my opinion, the model is well introduced and motivated. In particular, I find the proposed restriction to a log-quadratic policy class insightful, and Proposition 1 and the empirical comparison of Table 2 provide useful motivation for the validity of this restriction.

Critical weaknesses
  1. The theoretical and empirical evidence for HPG’s effectiveness on the routing problem appears limited. Theorems 3 and 5 give guarantees with respect to the linearized policy regret in (9), rather than the actual policy regret in (4) (as acknowledged in the paper). Furthermore, as far as I can tell there are no experiments directly evaluating HPG's regret, or even its linearized policy regret. Either a guarantee for actual regret or an empirical evaluation of the algorithm would be very helpful to assess its performance for the routing problem considered.

  2. The benefit of using hypentropy regularization in step 7 of the algorithm is unclear to me. It seems that replacing this step by ordinary projected gradient descent over the product of Frobenius balls of radius 2s2s, using the same gradient estimator (13), could slightly improve the regret bound of Theorem 3. Indeed, the assumption of Theorem 3 also gives ∥Wm∗∥F≤∥Wm∗∥∗≤2s\Vert W_m^* \Vert_F \le \Vert W_m^* \Vert_{*} \le 2s. By (13), ∥G^t,m∥F=∥G^t,m∥op\Vert \widehat G_{t,m} \Vert_F = \Vert \widehat G_{t,m} \Vert_{\mathrm{op}}, so Lemma 2 implies E[∑m∥G^t,m∥F2]≤10\mathbb{E}[\sum_m \Vert \widehat G_{t,m} \Vert_F^2] \le 10. I would expect that adapting the argument leading to (28) in Appendix E.4 would give a linearized regret bound of order Ms2/η+ηTMs^2/\eta + \eta T, which would yield an O(sMT)O(s\sqrt{M T}) bound after optimizing the learning rate η\eta.

Questions for authors
  1. Could you evaluate HPG's actual routing regret empirically? This could help assess whether the surrogate guarantee translates to good performance for the actual routing objective.

  2. Could you clarify the benefits of hypentropy regularization in the algorithm, and whether the argument above for replacing it with a simpler projected gradient descent step is correct?

  3. In my understanding, it is claimed line 200 that π∗\pi^{\ast} is optimal among policies of the form π(m∣q)∝exp⁡(csm(q))\pi(m | q)\propto\exp(cs_m(q)). In what sense? Wouldn't choosing sm(q)=kRm(q)s_m(q)=kR_m(q) with k>1k>1 improve expected reward by concentrating probability on the best models? Related to this, Theorems 3 and 5 assume that an optimal policy has each parameter matrix bounded in nuclear norm by 2s2s. This assumption is motivated by Proposition 1 (lines 317 and 371–372), but the policy in (6) uses cWm∗cW_m^{\ast} as routing parameters, for which the proposition only gives a bound of 2scρ2sc\rho. Could you clarify how the scaling by cc is accounted for?

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

This paper considers the item selection problem in the context of online advertising, facilitated by the experts' distributions over items. So essentially the action space is in fact the expert, represented by low-rank embeddings. It approaches the problem as a contextual bandit with linear reward functions and arbitrary contexts. To solve the problem, it defines a dynamic regret over a specific class of policies, namely log quadratic policies in the sense that the policy can be expressed as a softmax style function with weights determined by the quadratic form of the context given the unknown parameter matrix. It further proposes a variant of the policy gradient and then performs online mirror descent using hyperbolic entropy. It proves that the policy has a regret of scale sMTs\sqrt{MT} where ss is the low-rank of the embedding space, MM is the number of experts, and TT is the horizon. The paper also suggests some practical implementation of the algorithm building on the existing work.

Critical strengths
  1. The paper considers the model selection problem in online advertising, which by itself is meaningful.

  2. The paper's structure is mostly clear, though some places are hard to parse with very long sentences.

Critical weaknesses
  1. The proposed modeling is not convincing. First, the numerical validation only validates the quadratic form, and many other ingradients do not seem to be addressed. Examples include the low-rank structure, linear reward function, and arbitrary context. Also it is only on one dataset, and it is less convincing. It has many structure assumptions, requiring many different treatments. It is hard to understand how practical it is. Also, while the paper claimed its motivation in the domain, there is no numerical experiment to further validate the idea. This somehow does not support the paper's motivation.

  2. There is limited novelty herein. Many algorithmic ingradients are from the existing work, such as online mirror descent with hyperbolic entropy, policy gradient, and parameter-free implementation. It is unclear where the fundamental novelty lies.

Questions for authors
  1. What is the point of mentioning both bandit feedback and limited observability?

  2. Is one dataset sufficing to claim the modeling?

  3. How practical is the proposed method and what is its advantage compared to the state-of-the-art?

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

Related papers

Discussion (0)

Sign in to comment.