嵌入模型路由的策略遗憾：具有低秩专家的上下文赌博机

# 嵌入模型路由的策略遗憾：具有低秩专家的上下文赌博机  
来源：https://arxiv.org/html/2606.14929  
Negin Golrezaei  
斯隆管理学院，麻省理工学院。邮箱：[email protected]。  
Patrick Jaillet  
电气工程与计算机科学系，麻省理工学院。邮箱：[email protected]。  

###### 摘要  

现代推荐系统越来越依赖将多样化查询动态路由到多个嵌入模型。尽管具有实际意义，但在对抗性查询、赌博机反馈和模型有限可观测性等现实条件下，这一问题仍未得到充分理解。我们将嵌入模型路由形式化为一个具有低秩专家的对抗性上下文线性赌博机问题，其中上下文是查询，动作是物品，专家是工作在低秩潜在表示空间上的嵌入模型。我们首先证明，标准遗憾概念存在结构性错配或统计上不可处理的问题，并确定了一个*对数二次*策略类，该类别具有足够表达能力以捕获查询相关的模型路由，同时又足够结构化以支持高效在线学习。其次，我们提出了一种名为“超熵策略梯度”（HPG）的策略梯度算法。该算法能自适应地适应不完全信息下的未知低秩结构，并达到~\(s\sqrt{MT}\)的线性化策略遗憾——其中\(s\)、\(M\)和\(T\)分别是专家的内在秩、模型数量和轮次——从而避免了维数灾难。最后，我们还提供了HPG的一个计算高效且无需参数的实现。  

## 1 引言  

现代推荐系统和搜索引擎严重依赖密集嵌入模型进行信息检索（yi2019sampling, karpukhin2020dense）。这些模型将查询和物品映射到低维“嵌入空间”，基于相似度分数（即内积）实现高效检索。然而，在单一嵌入空间内表示截然不同的用户查询的全部多样性存在根本性局限：由于模型固有的低维结构，没有一个单一的嵌入模型能在所有查询类型上一致最优（weller2025theoretical）。这一局限在实践中有所体现。阿里巴巴和Meta的大规模工业电商平台部署多个嵌入模型以捕获查询的不同语义方面（li2019multi, huang2020embedding）。类似地，近期检索增强生成（RAG）方法将查询路由到训练于特定领域语料库（如代码、金融或医学数据）的专用“专家模型”（lee2025routerretriever, zhao2026r）。这些进展指向一个挑战：如何动态地将每个传入查询路由到最合适的嵌入模型？  

为了数值说明这一挑战，图1（https://arxiv.org/html/2606.14929#S1.F1）比较了语义嵌入（miniLM; wang2020minilm）和问答模型（msmarco; reimers2019sentence）在亚马逊数据集（collins2022abo）上的排序与LLM生成的地面真值。每个点代表一个单独物品。灰点表示高质量候选（LLM前25%）。彩色点突出显示“专属优质”物品：被一个模型成功检索（前30，如虚线所示）但被另一个模型遗漏的高质量候选。详细实验设置见附录A（https://arxiv.org/html/2606.14929#A1）。图1（https://arxiv.org/html/2606.14929#S1.F1）中的互斥错误和优势证实了*没有单一模型压倒另一个*，这使得自适应路由至关重要。这引出了我们的主要问题：*在线学习器如何自适应地将查询路由到嵌入模型，仅利用来自所路由模型的反馈，以获得可证明的性能保证？*  

为了从理论上扎实地回答这个问题，我们做出了以下主要贡献：  

##### 建模（第2节（https://arxiv.org/html/2606.14929#S2））。  
我们将在线嵌入模型路由问题框架化为一个\(T\)轮、具有低秩专家的对抗性上下文线性赌博机：在第\(t\)轮，学习器观察到对抗性查询\(q_t \in \mathbb{R}^{d_q}\)作为*上下文*，并面对一个物品集\(\mathcal{A} \subseteq \mathbb{R}^{d_a}\)作为*动作*。\(M\)个嵌入模型作为*专家*，每个模型通过一个维数\(s \ll \min(d_q, d_a)\)的潜在嵌入空间隐含地在\(\mathcal{A}\)上有一个分布。学习器只能选择*一个*模型\(m_t\)进行路由，观察所选模型的推荐，并接收一个诱导出的含噪奖励。目标是竞争一个固定的路由策略类。这一形式化抓住了现实推荐系统的主要挑战：对抗性查询序列、赌博机奖励反馈以及模型输出的部分可观测性。  

##### 遗憾概念（第3节（https://arxiv.org/html/2606.14929#S3））。  
一个关键挑战是为该问题确定一个合适的性能基准。我们发现标准遗憾概念不充分：竞争最佳固定模型（即专家遗憾）忽略了查询异质性，而竞争任意查询相关策略（即上下文遗憾）则不可处理。常用的对数线性策略类也无法适应嵌入模型的底层结构。相反，我们的主要洞见是，在嵌入模型的潜在几何结构下，每个模型的期望奖励近似是查询的*低秩二次*函数（命题1（https://arxiv.org/html/2606.14929#Thmtheorem1））。这引出了我们的对数二次策略类：表达能力足以捕获接近最优的路由，同时又适合高效学习。在表2（https://arxiv.org/html/2606.14929#S3.T2）中，我们在亚马逊ESCI数据集（reddy2022shopping）上数值验证了我们的主张。  

##### 算法设计（第4节（https://arxiv.org/html/2606.14929#S4））。  
由于参数空间二次庞大，原始的vanilla策略梯度会遭受\(\widetilde{\mathcal{O}}(d_q \sqrt{MT})\)的线性化策略遗憾（一种解决softmax非凸性的替代指标；见第3.2节（https://arxiv.org/html/2606.14929#S3.SS2））。为了避免\(d_q\)依赖性，我们提出了超熵策略梯度（HPG）。通过自动适应嵌入模型的未知低秩结构，HPG可证明达到\(\widetilde{\mathcal{O}}(s \sqrt{MT})\)的线性化策略遗憾，从而避免了维数灾难。  

##### 实际实现（第5节（https://arxiv.org/html/2606.14929#S5））。  
我们的算法基于在线镜像下降（OMD），由于Bregman投影，通常计算成本较高。令人惊讶的是，我们证明了HPG中的投影步骤可以在\(\mathcal{O}(d_q^2 M)\)时间内实现（定理4（https://arxiv.org/html/2606.14929#Thmtheorem4））；这是因为超熵正则化与核范数诱导的参数空间相结合。我们进一步展示了HPG可以无需参数地实现，即无需低秩参数\(s\)。  

### 1.1 相关文献  

##### 模型路由。  
在大规模工业推荐系统或搜索引擎中，为了提高性能，开发了多嵌入框架（li2019multi, huang2020embedding）。自然语言处理文献中提出了混合专家（MoE）架构，以聚合表示并捕获语义意图（shazeer2017outrageously, ma2018modeling, lepikhin2021gshard, fedus2022switch, zhou2022mixture）。在大语言模型（LLM）时代，提出了动态模型路由（也称为模型级联或LLM路由）以平衡生成质量和推理成本（jiang2023llm, shnitzer2023large, chen2024frugalgpt, ong2025routellm）。与我们嵌入模型的上下文更相关的是，现代检索增强生成（RAG）流水线越来越多地将查询路由到专门的专家检索器（mallen2023not, jeong2024adaptive, lee2025routerretriever, zhao2026r）。几项先前工作通过将模型路由视为（在线或离线）上下文赌博机来得出启发式方法（nguyen2024metallm, ong2025routellm, hu2025an, tsiourvas2025causal, jitkrittum2026universal, zu2026barouter, poon2026multillm），但它们将底层嵌入模型视为完全黑箱。另一方面，在本文中，我们严格地将嵌入模型路由建模为具有低秩专家的对抗性上下文线性赌博机，并设计了一种具有可证明遗憾保证、计算成本界限和无需参数实现的策略梯度算法。  

##### 带专家建议的赌博机。  
带专家建议的赌博机（定义1（https://arxiv.org/html/2606.14929#Thmdefinition1））首先由auer2002nonstochastic研究，他们提出了EXP4算法，达到\(\mathcal{O}(\sqrt{KT \log M})\)的专家遗憾，其中\(K, T, M\)分别是臂数、轮数和专家数。beygelzimer2011contextual提出了EXP4.P，以高概率实现相同界限。seldin2013open提出了有限观测设置——每轮只能查询\(N\)个专家——作为COLT开放问题。在完全信息下，可以达到\(\widetilde{\mathcal{O}}(\sqrt{MT/N})\)的专家遗憾（seldin2014prediction）；在赌博机反馈下，kale2014multiarmed给出了\(\widetilde{\mathcal{O}}(\sqrt{\min(N,K)MT/N})\)的专家遗憾和一个接近匹配的下界。无限观测设置最近重新引起兴趣，针对不同适应性水平的学习者建立了\(\Omega(\sqrt{KT \log(M/K)})\)的下界（ito2024minimax, cesa2025improved, chase2025tight）。  

##### （上下文）线性赌博机。  
线性赌博机由dani2008stochastic研究，上下文版本（定义2（https://arxiv.org/html/2606.14929#Thmdefinition2））由chu2011contextual和abbasi2011improved在对抗性上下文-随机奖励（“A-S”）机制下研究。对抗性上下文-对抗性奖励（“A-A”）机制不可处理（kanade2014learning, hazan2016computational, neu2020efficient），因此agarwal2014taming和syrgkanis2016efficient选择了策略遗憾。随机上下文-对抗性奖励（“S-A”）机制由neu2020efficient在已知上下文分布假设下提出。后续工作（neu2021online, luo2021policy, dai2023refined, sherman2023improved, kong2024improved）专注于更一般的线性马尔可夫决策过程（MDP）设置；当特化为赌博机时，它们需要额外假设或给出次优遗憾。liu2023bypassing提出了一种高效的\(\widetilde{\mathcal{O}}(d^2 \sqrt{T})\)算法和一种低效的\(\widetilde{\mathcal{O}}(d \sqrt{T})\)算法，其中\(d\)是维度，\(T\)是轮数。ito2024minimax考虑了有限臂情况，van2025improved refined了计算成本。线性赌博机中的错配问题已有研究，例如gopalan2016low, ghosh2017misspecified, foster2020adapting, dong2023does, liu2024corruption，我们在等式2（https://arxiv.org/html/2606.14929#S2.E2）和4（https://arxiv.org/html/2606.14929#S2.E4）中采用了这些研究。更丰富的非线性机制也在文献中有所研究（russo2013eluder, foster2018practical, foster2020beyond, li2022understanding），这超出了本文的范围。  

##### 策略梯度方法。  
策略梯度（PG）方法是强化学习和控制的基础（williams1992simple, sutton1999policy, kakade2001natural）。PG方法在对数线性策略类上的全局收敛由fazel2018global在控制理论中和bhandari2024global在强化学习中开创。agarwal2021theory和mei2020global提出了梯度支配条件以建立表格设置中的精确收敛率，但对数线性策略类仍然开放（见第B.4节（https://arxiv.org/html/2606.14929#A2.SS4））。策略梯度也经常从OMD角度设计（geist2019theory, shani2020adaptive），其中存在各种熵正则化器（alfano2023novel, cichocki2025mirror）。然而，我们不知道有现有的工作利用策略梯度中的超熵来促进所学参数的低秩性。  

##### 无参数在线学习。  
无参数在线学习无需关于比较器的先验信息即可达到接近最优的遗憾（chaudhuri2009parameter, streeter2012no, orabona2013dimension, mcmahan2014unconstrained）。orabona2016coin提出了一个“coin-betting”框架，使得在更丰富的机制中能够实现无参数在线学习的黑箱框架（cutkosky2018black）。更一般地，对例如最优动作损失（freund1997decision, allenberg2006hannan, allen2018make）、反馈延迟（zimmert2020optimal, gyorgy2021adapting, huang2023banker）或损失分布性质（huang2022adaptive, genalti2024varepsilon, chen2025uniinf）的自适应性，已在赌博机或在线学习中得到广泛研究。  

## 2 设置：具有低秩专家的上下文赌博机  

##### 符号。  
对于整数\(n \in \mathbb{Z}_+\)，\([n]\)表示集合\(\{1,2,\ldots,n\}\)。我们用\(\mathcal{O}\)隐藏绝对常数，用\(\widetilde{\mathcal{O}}\)额外隐藏多项式对数因子。令\(\mathbb{S}^n \subseteq \mathbb{R}^{n \times n}\)为对称\(n \times n\)实矩阵的空间。对于\(X \in \mathbb{S}^n\)，\(\lambda_i(X)\)表示\(X\)的第\(i\)大特征值。令\(\lVert X \rVert_* := \sum_i |\lambda_i(X)|\)为核范数，\(\lVert A \rVert_2 := \max_i |\lambda_i(X)|\)为谱范数。  

考虑一个学习器与环境之间的\(T\)轮博弈。在每一轮\(t\)，一个嵌入到\(d_q\)维欧几里得空间的*查询*，即\(q_t \in \mathcal{Q} := \mathbb{R}^{d_q}\)，作为上下文呈现给学习器。我们允许\(q_t\)是任意的，即可能由自适应对手选择。尽管真实查询可以是自然语言，但在实际模型路由场景中，查询通常首先输入一个“基础编码器”并嵌入到有限维空间（例如，参见lee2025routerretriever）。学习器有一个大的候选*物品*集，嵌入到\(d_a\)维欧几里得空间，记为\(\mathcal{A} \subseteq \mathbb{R}^{d_a}\)，对应于赌博机中的动作集。学习器旨在推荐一个最能回答查询\(q_t\)的物品\(a_t \in \mathcal{A}\)，以期望*奖励*\(r(q_t, a_t)\)衡量。在第2.1节（https://arxiv.org/html/2606.14929#S2.SS1）中，我们将奖励\(r\)建模为物品与查询在潜在空间上的相似度分数。学习器不直接查看动作集\(\mathcal{A}\)，而是配备了\(M\)个嵌入*模型*（也称为专家）。每个模型\(m\)对查询\(q_t\)有一个推荐分布\(\xi_m(q_t)\)——由其潜在内部结构诱导——我们将在第2.2节（https://arxiv.org/html/2606.14929#S2.SS2）中形式化。然而，正如tsiourvas2025causal所论证的，鉴于因果... （此处原文似乎中断，但按原文保留）