Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Experts
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 𝒪̃(s√(M T)) linearized policy regret -- where $s, M$, and T 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.
Related
- Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability
- Set Membership Estimation for Stochastic Linear Contextual Bandits
- Meta-LinEXP3: Online-within-Online Learning for Adversarial Linear Contextual Bandits
- Diversified Multinomial Logit Contextual Bandits
- Online Autotuning of Algebraic Multigrid via Contextual Bandits and Reinforcement Learning
BibTeX
@misc{dai2026policy,
title = {{Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Experts}},
author = {Yan Dai and Negin Golrezaei and Patrick Jaillet},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2606.14929},
eprint = {2606.14929},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.14929},
}
RIS
TY - UNPB
TI - Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Experts
AU - Yan Dai
AU - Negin Golrezaei
AU - Patrick Jaillet
PY - 2026
DA - 2026/09/24
PB - arXiv
DO - 10.48550/arxiv.2606.14929
UR - https://arxiv.org/abs/2606.14929
AB - 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 𝒪̃(s√(M T)) linearized policy regret -- where $s, M$, and T 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.
ER -