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

# Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Experts
Source: [https://arxiv.org/html/2606.14929](https://arxiv.org/html/2606.14929)
Negin GolrezaeiSloan School of Management, MIT\. Email:golrezae@mit\.edu\.Patrick JailletDepartment of EECS, MIT\. Email:jaillet@mit\.edu\.

###### 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\. Second, 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\)\\widetilde\{\\mathcal\{O\}\}\(s\\sqrt\{MT\}\)linearized policy regret – wheres,Ms,M, andTTare the intrinsic rank of the experts, the number of models, and the number of rounds – thus avoiding a curse of dimensionality\. Finally, we also provide an computationally efficient and parameter\-free implementation of HPG\.

## 1Introduction

Modern recommendation systems and search engines rely heavily on dense embedding models for information retrieval\(yi2019sampling,karpukhin2020dense\)\. These models map queries and items into low\-dimensional “embedding spaces,” enabling efficient retrieval based on the similarity scores \(i\.e\., inner products\)\. However, representing the full diversity of distinct user queries within a single embedding space is fundamentally limited: Due to models’ intrinsic low\-dimensional structures, no single embedding model can be uniformly optimal across all types of queries\(weller2025theoretical\)\.

This limitation is reflected in practice\. Large\-scale industrial e\-commerce platforms by Alibaba and Meta deploy multiple embedding models to capture different semantic aspects of queries\(li2019multi,huang2020embedding\)\. Similarly, recent approaches in Retrieval\-Augmented Generation \(RAG\) route queries to specialized “expert models” trained on domain\-specific corpora, such as code, finance, or medical data\(lee2025routerretriever,zhao2026r\)\. These developments point to a challenge: How to dynamically route each incoming query to the most appropriate embedding model?

To numerically illustrate this challenge,[Figure˜1](https://arxiv.org/html/2606.14929#S1.F1)compares the rankings from a semantic embedding\(miniLM;wang2020minilm\)and a Q&A model\(msmarco;reimers2019sentence\)against an

![Refer to caption](https://arxiv.org/html/2606.14929v1/x1.png)Figure 1:miniLMvsmsmarcoLLM\-generated ground\-truth on an Amazon dataset\(collins2022abo\)\. Each point is a single item\. Gray dots denote high\-quality candidates \(LLM top\-25%\)\. Colored dots highlight “exclusively good” items: high\-quality candidates that are successfully retrieved by one model \(top\-30, as indicated by the dashed line\) but missed by the other\. The detailed experimental setup can be found in[Appendix˜A](https://arxiv.org/html/2606.14929#A1)\. The mutually exclusive errors and strengths in[Figure˜1](https://arxiv.org/html/2606.14929#S1.F1)confirm*no single model dominates the other*, making adaptive routing essential\.

This gvies our main question:How can an online learner adaptively route queries to embedding models, using feedback only from the routed models, to achieve provable performance guarantees?Towards answering this question in a theoretically grounded way, we make the following main contributions:

##### Modeling \([Section˜2](https://arxiv.org/html/2606.14929#S2)\)\.

We frame the online embedding model routing problem as aTT\-round adversarial contextual linear bandit with low\-rank experts: In roundtt, the learner observes an adversarial queryqt∈ℝdqq\_\{t\}\\in\\mathbb\{R\}^\{d\_\{q\}\}as*context*and faces an item set𝒜⊆ℝda\\mathcal\{A\}\\subseteq\\mathbb\{R\}^\{d\_\{a\}\}as*actions*\.MMembedding models, as*experts*, each implicitly has a distribution over𝒜\\mathcal\{A\}via a latent embedding space of dimensions≪min⁡\(dq,da\)s\\ll\\min\(d\_\{q\},d\_\{a\}\)\. The learner can only choose*one*modelmtm\_\{t\}to route, observe the selected model’s recommendation, and receive an induced noisy reward\. The goal is to compete with a fixed class of routing policies\. This formulation captures the main challenges in realistic recommendation systems: adversarial query sequences, bandit reward feedback, and partial observability of model outputs\.

##### Regret Notion \([Section˜3](https://arxiv.org/html/2606.14929#S3)\)\.

A key challenge is identifying an appropriate performance benchmark for this problem\. We find standard regret notions inadequate: competing with the best fixed model \(i\.e\., expert regret\) ignores query heterogeneity, while competing with arbitrary query\-dependent policies \(i\.e\., contextual regret\) is intractable\. The commonly used log\-linear policy class also fails to fit the underlying structures of embedding models\. Instead, our main insight is, under the latent geometry of embedding models, the expected reward of each model is approximately a*low\-rank quadratic*function of the query \([Proposition˜1](https://arxiv.org/html/2606.14929#Thmtheorem1)\)\. This leads to our log\-quadratic policy class: expressive enough to capture near\-optimal routing, while remaining amenable to efficient learning\. In[Table˜2](https://arxiv.org/html/2606.14929#S3.T2), we numerically justify our claims on an Amazon ESCI dataset\(reddy2022shopping\)\.

##### Algorithm Design \([Section˜4](https://arxiv.org/html/2606.14929#S4)\)\.

Because of the quadratically large parameter space, a vanilla policy gradient suffers from𝒪~⁡\(dq​M​T\)\\operatorname\{\\widetilde\{\\operatorname\{\\mathcal\{O\}\}\}\}\(d\_\{q\}\\sqrt\{MT\}\)linearized policy regret \(a surrogate metric to resolve the non\-convexity of softmax; see[Section˜3\.2](https://arxiv.org/html/2606.14929#S3.SS2)\)\. To avoid thedqd\_\{q\}dependency, we propose Hypentropy Policy Gradient \(HPG\)\. By automatically adapting to the unknown low\-rank structure of embedding models, HPG provably attains𝒪~⁡\(s​M​T\)\\operatorname\{\\widetilde\{\\operatorname\{\\mathcal\{O\}\}\}\}\(s\\sqrt\{MT\}\)linearized policy regret, thus avoiding the curse of dimensionality\.

##### Practical Implementation \([Section˜5](https://arxiv.org/html/2606.14929#S5)\)\.

Our algorithm builds upon Online Mirror Descent \(OMD\), which is typically computationally expensive due to a Bregman projection\. Perhaps surprisingly, we prove that our projection step in HPG can be implemented in𝒪⁡\(dq2​M\)\\operatorname\{\\mathcal\{O\}\}\(d\_\{q\}^\{2\}M\)time \([Theorem˜4](https://arxiv.org/html/2606.14929#Thmtheorem4)\); this is because of the combination of hypentropy regularization and nuclear\-norm\-induced parameter space\. We further show HPG can be implemented parameter\-freely, i\.e\., without the low\-rank parameterss\.

### 1\.1Related Literature

##### Model Routing\.

In large\-scale industrial recommendation systems or searching engines, multi\-embedding frameworks were developed for better performance\(li2019multi,huang2020embedding\)\. Mixture\-of\-Experts \(MoE\) architectures were proposed in the natural language processing literature to aggregate representations and capture semantic intents\(shazeer2017outrageously,ma2018modeling,lepikhin2021gshard,fedus2022switch,zhou2022mixture\)\. In the era of large language models \(LLMs\), dynamic model routing \(also known as model cascading or LLM routing\) was proposed to balance the generation quality and the inference cost\(jiang2023llm,shnitzer2023large,chen2024frugalgpt,ong2025routellm\)\. More closely related to our context of embedding models, modern Retrieval\-Augmented Generation \(RAG\) pipelines increasingly route queries to specialized expert retrievers\(mallen2023not,jeong2024adaptive,lee2025routerretriever,zhao2026r\)\. Several prior works also drew heuristics by viewing model routing as \(online or offline\) contextual bandits\(nguyen2024metallm,ong2025routellm,hu2025an,tsiourvas2025causal,jitkrittum2026universal,zu2026barouter,poon2026multillm\), but they treated the underlying embedding models as complete black\-boxes\. On the other hand, in this paper, we model the embedding model routing rigorously as an adversarial contextual linear bandit with low\-rank experts, and design a policy gradient algorithm with provable regret guarantee, computational cost bound, and parameter\-free implementation\.

##### Bandits with Expert Advice\.

Bandits with expert advice \([Definition˜1](https://arxiv.org/html/2606.14929#Thmdefinition1)\) were first studied byauer2002nonstochastic, who proposed the EXP4 algorithm for𝒪⁡\(K​T​log⁡M\)\\operatorname\{\\mathcal\{O\}\}\(\\sqrt\{KT\\log M\}\)expert regret whereK,T,MK,T,Mare the numbers of arms, rounds, and experts\.beygelzimer2011contextualproposed EXP4\.P, achieving the same bound with high probability\.seldin2013openraised the limited observation setup – where each round onlyNNexperts can be queried – as a COLT open problem\. With full information,𝒪~⁡\(M​T/N\)\\operatorname\{\\widetilde\{\\operatorname\{\\mathcal\{O\}\}\}\}\(\\sqrt\{MT/N\}\)expert regret is possible\(seldin2014prediction\); under bandit feedback,kale2014multiarmedgave𝒪~⁡\(min⁡\(N,K\)​M​T/N\)\\operatorname\{\\widetilde\{\\operatorname\{\\mathcal\{O\}\}\}\}\(\\sqrt\{\\min\(N,K\)MT/N\}\)expert regret and a near\-matching lower bound\. The unlimited observation setup has recently regained interest, withΩ​\(K​T​log⁡\(M/K\)\)\\Omega\(\\sqrt\{KT\\log\(M/K\)\}\)lower bounds established for learners with different levels of adaptivity\(ito2024minimax,cesa2025improved,chase2025tight\)\.

##### \(Contextual\) Linear Bandits\.

Linear bandit was studied bydani2008stochastic, and the contextual version \([Definition˜2](https://arxiv.org/html/2606.14929#Thmdefinition2)\) was studied bychu2011contextualandabbasi2011improvedunder the adversarial\-context stochastic\-reward \(“A\-S”\) regime\. The adversarial\-context and adversarial\-reward \(“A\-A”\) regime is intractable\(kanade2014learning,hazan2016computational,neu2020efficient\), thusagarwal2014tamingandsyrgkanis2016efficientopted for policy regret\.

The stochastic\-context adversarial\-reward \(“S\-A”\) regime was proposed byneu2020efficientunder the known context distribution assumption\. Subsequent works\(neu2021online,luo2021policy,dai2023refined,sherman2023improved,kong2024improved\)focused on the more general linear Markov decision process \(MDP\) setup; when specialized to bandits, they require extra assumptions or give sub\-optimal regret\.liu2023bypassingproposed an efficient𝒪~⁡\(d2​T\)\\operatorname\{\\widetilde\{\\operatorname\{\\mathcal\{O\}\}\}\}\(d^\{2\}\\sqrt\{T\}\)algorithm and an inefficient𝒪~⁡\(d​T\)\\operatorname\{\\widetilde\{\\operatorname\{\\mathcal\{O\}\}\}\}\(d\\sqrt\{T\}\)algorithm, withddbeing the dimension andTTbeing the number of rounds\.ito2024minimaxconsidered a finite\-arm case andvan2025improvedrefined the computational cost\.

Misspecification in linear bandits were studied by, for example,gopalan2016low,ghosh2017misspecified,foster2020adapting,dong2023does,liu2024corruption, which we adopt in[Equations˜2](https://arxiv.org/html/2606.14929#S2.E2)and[4](https://arxiv.org/html/2606.14929#S2.E4)\. Richer non\-linear regimes were also studied in the literature\(russo2013eluder,foster2018practical,foster2020beyond,li2022understanding\), which are beyond the scope of this paper\.

##### Policy Gradient Methods\.

Policy gradient \(PG\) methods are foundational for reinforcement learning and control\(williams1992simple,sutton1999policy,kakade2001natural\)\. Global convergence of PG methods for the log\-linear policy class was initiated byfazel2018globalin control theory andbhandari2024globalin reinforcement learning\.agarwal2021theoryandmei2020globalproposed gradient dominance conditions to establish exact convergence rates in tabular settings, but the log\-linear policy class remains open \(see[Section˜B\.4](https://arxiv.org/html/2606.14929#A2.SS4)\)\. Policy gradient is also frequently designed from an OMD perspective\(geist2019theory,shani2020adaptive\), where various entropy regularizers exist\(alfano2023novel,cichocki2025mirror\)\. However, we are unaware of existing works utilizing hypentropy in policy gradient to promote low\-rankness of the learned parameter\.

##### Parameter\-Free Online Learning\.

Parameter\-free online learning attains near\-optimal regret without prior information on the comparator\(chaudhuri2009parameter,streeter2012no,orabona2013dimension,mcmahan2014unconstrained\)\.orabona2016coinproposed a “coin\-betting” framework, which enables black\-box frameworks for parameter\-free online learning in richer regimes\(cutkosky2018black\)\. More generally, adaptivity to, e\.g\., optimal action’s loss\(freund1997decision,allenberg2006hannan,allen2018make\), feedback delays\(zimmert2020optimal,gyorgy2021adapting,huang2023banker\), or properties of loss distributions\(huang2022adaptive,genalti2024varepsilon,chen2025uniinf\), has been widely studied in bandits or online learning\.

## 2Setup: Contextual Bandits with Low\-Rank Experts

##### Notations\.

For an integern∈ℤ\+n\\in\\mathbb\{Z\}\_\{\+\},\[n\]\[n\]denotes the set\{1,2,…,n\}\\\{1,2,\\ldots,n\\\}\. We use𝒪\\operatorname\{\\mathcal\{O\}\}to hide absolute constants, and use𝒪~\\operatorname\{\\widetilde\{\\operatorname\{\\mathcal\{O\}\}\}\}to additionally hide poly\-logarithmic factors\. Let𝕊n⊆ℝn×n\\mathbb\{S\}^\{n\}\\subseteq\\mathbb\{R\}^\{n\\times n\}be the space of symmetricn×nn\\times nreal matrices\. ForX∈𝕊nX\\in\\mathbb\{S\}^\{n\},λi​\(X\)\\lambda\_\{i\}\(X\)denotes theii\-th largest eigenvalue ofXX\. Let∥X∥∗:=∑i\|λi​\(X\)\|\\lVert X\\rVert\_\{\\ast\}:=\\sum\_\{i\}\\lvert\\lambda\_\{i\}\(X\)\\rvertbe the nuclear norm and∥A∥2:=maxi⁡\|λi​\(X\)\|\\lVert A\\rVert\_\{2\}:=\\max\_\{i\}\\lvert\\lambda\_\{i\}\(X\)\\rvertbe the spectral norm\.

Consider aTT\-round game between a learner and the environment\. In each roundtt, a*query*embedded into thedqd\_\{q\}\-dimensional Euclidean space, namelyqt∈𝒬:=ℝdqq\_\{t\}\\in\\mathcal\{Q\}:=\\mathbb\{R\}^\{d\_\{q\}\}, is presented to the learner as a context\. We allowqtq\_\{t\}to be arbitrary, i\.e\., it may be chosen by an adaptive adversary\. Although real queries can be in natural language, in practical model routing scenarios, queries are usually first fed into a “base encoder” and embedded into a finite\-dimensional space\(see, e\.g\.,lee2025routerretriever\)\.

The learner has a large set of candidate*items*embedded into thedad\_\{a\}\-dimensional Euclidean space, denoted by𝒜⊆ℝda\\mathcal\{A\}\\subseteq\\mathbb\{R\}^\{d\_\{a\}\}, corresponding to the action set in bandits\. The learner aims to recommend an itemat∈𝒜a\_\{t\}\\in\\mathcal\{A\}that best answers the queryqtq\_\{t\}, measured in terms of expected*reward*r​\(qt,at\)r\(q\_\{t\},a\_\{t\}\)\. In[Section˜2\.1](https://arxiv.org/html/2606.14929#S2.SS1), we model rewardrras the similarity score between items and queries on a latent space\.

Instead of directly looking into the action set𝒜\\mathcal\{A\}, the learner is equipped withMMembedding*models*\(also known as experts\)\. Each modelmmhas a recommendation distributionξm​\(qt\)\\xi\_\{m\}\(q\_\{t\}\)– induced by its latent internal structure – to the queryqtq\_\{t\}, which we formalize in[Section˜2\.2](https://arxiv.org/html/2606.14929#S2.SS2)\. However, as argued bytsiourvas2025causal, given the cost of invoking large models, the learner can only query*one*modelmtm\_\{t\}for an itemat,mta\_\{t,m\_\{t\}\}, thus giving limited observability\. The learner only receives bandit feedback on the induced reward\. The interaction protocol and feedback model will be detailed in[Section˜2\.3](https://arxiv.org/html/2606.14929#S2.SS3)\.

### 2\.1Misspecified Adversarial Contextual Linear Bandit

For each queryq∈𝒬q\\in\\mathcal\{Q\}and candidate itema∈𝒜a\\in\\mathcal\{A\}, we assume the expected rewardr​\(q,a\)r\(q,a\)is roughly their*similarity score*\(inner product\) on a high\-dimensional latent spaceℝmax⁡\(da,dq\)\\mathbb\{R\}^\{\\max\(d\_\{a\},d\_\{q\}\)\}\. Specifically, there are fixed but unknown linear mapsU∗∈ℝmax⁡\(da,dq\)×dqU^\{\\ast\}\\in\\mathbb\{R\}^\{\\max\(d\_\{a\},d\_\{q\}\)\\times d\_\{q\}\}andV∗∈ℝmax⁡\(da,dq\)×daV^\{\\ast\}\\in\\mathbb\{R\}^\{\\max\(d\_\{a\},d\_\{q\}\)\\times d\_\{a\}\}, such that

r​\(q,a\)=⟨U∗​q,V∗​a⟩\+ν​\(q,a\),∀q∈𝒬,a∈𝒜,r\(q,a\)=\\bigl\\langle U^\{\\ast\}q,V^\{\\ast\}a\\bigr\\rangle\+\\nu\(q,a\),\\quad\\forall q\\in\\mathcal\{Q\},a\\in\\mathcal\{A\},\(1\)whereν\\nuis a misspecification term capturing the non\-linearity\. We assume∥ν∥∞:=supq,a\|ν​\(q,a\)\|≤ϵ\\lVert\\nu\\rVert\_\{\\infty\}:=\\sup\_\{q,a\}\\lvert\\nu\(q,a\)\\rvert\\leq\\epsilonfor some fixed but unknownϵ∈\[0,1\)\\epsilon\\in\[0,1\), a standard way of modeling misspecification in linear bandits\(gopalan2016low,ghosh2017misspecified,foster2020adapting,dong2023does\)or linear Markov decision processes\(du2020good,jin2023provably,vial2022improved\)\. All components in[Equation˜1](https://arxiv.org/html/2606.14929#S2.E1)– linear mapsU∗U^\{\\ast\},V∗V^\{\\ast\}, misspecification functionν\\nu, and misspecification boundϵ\\epsilon– are all unknown\.

Using the Frobenius inner product notation⟨A,B⟩F:=Tr\(A𝖳​B\)\\langle A,B\\rangle\_\{F\}:=\\operatornamewithlimits\{\\mathrm\{Tr\}\}\(A^\{\\mathsf\{T\}\}B\), whereA,BA,Bare two matrices of the same size, we equivalently writer​\(q,a\)=⟨\(V∗\)𝖳​U∗,a​q𝖳⟩Fr\(q,a\)=\\langle\(V^\{\\ast\}\)^\{\\mathsf\{T\}\}U^\{\\ast\},aq^\{\\mathsf\{T\}\}\\rangle\_\{F\}\. Thus the reward function in[Equation˜1](https://arxiv.org/html/2606.14929#S2.E1)admits ada×dqd\_\{a\}\\times d\_\{q\}\-dimensional linear structure \(with a misspecification up toϵ\\epsilon\), namely

r​\(q,a\)=⟨Ψ∗,a​q𝖳⟩F\+ν​\(q,a\),where kernel​Ψ∗:=\(V∗\)𝖳​U∗∈ℝda×dq\.r\(q,a\)=\\bigl\\langle\\Psi^\{\\ast\},aq^\{\\mathsf\{T\}\}\\bigr\\rangle\_\{F\}\+\\nu\(q,a\),\\quad\\text\{where kernel \}\\Psi^\{\\ast\}:=\(V^\{\\ast\}\)^\{\\mathsf\{T\}\}U^\{\\ast\}\\in\\mathbb\{R\}^\{d\_\{a\}\\times d\_\{q\}\}\.\(2\)

### 2\.2Embedding Models as Low\-Rank Experts

As standard both in practical recommendation systems and theoretical research, we model embedding models via the two\-tower architecture\(huang2013learning\): Each modelm∈\[M\]m\\in\[M\]projects queries and items independently onto its own embedding spaceℝsm\\mathbb\{R\}^\{s\_\{m\}\}, and recommends items to queries according to the softmax of similarity scores onℝsm\\mathbb\{R\}^\{s\_\{m\}\}\. As observed byweller2025theoretical, embedding models work in very low\-dimensional representation spaces, hence we assumesm≪da,dqs\_\{m\}\\ll d\_\{a\},d\_\{q\}\. When presented with queryq∈𝒬q\\in\\mathcal\{Q\}, modelmm’s*recommendation distribution*over the item set𝒜⊆ℝda\\mathcal\{A\}\\subseteq\\mathbb\{R\}^\{d\_\{a\}\}is:111While embedding models – from lightweight encoders to large LLMs – employ highly non\-linear internal structures such as GeLU activations\(hendrycks2016gaussian,devlin2019bert\), the linear form in[Equation3](https://arxiv.org/html/2606.14929#S2.E3)is backed by recent findings: The Platonic representation hypothesis\(huh2024position\)and representation alignment literature\(lenc2015understanding,kornblith2019similarity\)demonstrate that latent spaces across heterogeneous neural networks – spanning lightweight encoders like BERT, massive LLMs like LLaMA, and even computer vision models – are globally isomorphic and can be mapped to one another via*linear*transformations\. Furthermore,wang2020understandingprove that contrastive learning, a common paradigm in embedding model training, explicitly enforces an*inner\-product*\-based geometry\. Thus, the learned embeddings naturally possess a linear structure, allowing the misspecification functionμm\\mu\_\{m\}to rigorously absorb any residual non\-linearities\.

ξm​\(a∣q\)∝exp⁡\(⟨Um​q,Vm​a⟩\+μm​\(q,a\)\),∀a∈𝒜,\\xi\_\{m\}\(a\\mid q\)\\propto\\exp\\Bigl\(\\bigl\\langle U\_\{m\}q,V\_\{m\}a\\bigr\\rangle\+\\mu\_\{m\}\(q,a\)\\Bigr\),\\quad\\forall a\\in\\mathcal\{A\},\(3\)which is in a form that is very similar to[Equation˜1](https://arxiv.org/html/2606.14929#S2.E1):Um∈ℝsm×dqU\_\{m\}\\in\\mathbb\{R\}^\{s\_\{m\}\\times d\_\{q\}\}andVm∈ℝsm×daV\_\{m\}\\in\\mathbb\{R\}^\{s\_\{m\}\\times d\_\{a\}\}are two fixed but unknown linear maps, andμm​\(q,a\)\\mu\_\{m\}\(q,a\)is a misspecification function capturing the non\-linearity in the embedding model\. We assume∥μm∥∞:=supq,a\|μm​\(q,a\)\|≤ϵ\\lVert\\mu\_\{m\}\\rVert\_\{\\infty\}:=\\sup\_\{q,a\}\\lvert\\mu\_\{m\}\(q,a\)\\rvert\\leq\\epsilonfor the same constantϵ∈\[0,1\)\\epsilon\\in\[0,1\)\.

The key difference between[Equations˜1](https://arxiv.org/html/2606.14929#S2.E1)and[3](https://arxiv.org/html/2606.14929#S2.E3)is thatUm∈ℝsm×dqU\_\{m\}\\in\\mathbb\{R\}^\{s\_\{m\}\\times d\_\{q\}\}andVm∈ℝsm×daV\_\{m\}\\in\\mathbb\{R\}^\{s\_\{m\}\\times d\_\{a\}\}are low\-rank\. For notational simplicity, we defines:=maxm⁡sms:=\\max\_\{m\}s\_\{m\}and omit the subscriptmminsms\_\{m\}\. Consequently, when defining the*model kernel*Ψm:=Vm𝖳​Um\\Psi\_\{m\}:=V\_\{m\}^\{\\mathsf\{T\}\}U\_\{m\}similar to[Equation˜2](https://arxiv.org/html/2606.14929#S2.E2), we haverank\(Ψm\)≤s\\operatornamewithlimits\{\\mathrm\{rank\}\}\(\\Psi\_\{m\}\)\\leq sand

ξm​\(a∣q\)∝exp⁡\(⟨Ψm,a​q𝖳⟩F\+μm​\(q,a\)\),where kernel​Ψm:=Vm𝖳​Um​has a rank≤s\.\\xi\_\{m\}\(a\\mid q\)\\propto\\exp\\Bigl\(\\bigl\\langle\\Psi\_\{m\},aq^\{\\mathsf\{T\}\}\\bigr\\rangle\_\{F\}\+\\mu\_\{m\}\(q,a\)\\Bigr\),\\quad\\text\{where kernel \}\\Psi\_\{m\}:=V\_\{m\}^\{\\mathsf\{T\}\}U\_\{m\}\\text\{ has a rank\}\\leq s\.\(4\)We emphasize that all components in[Equation˜4](https://arxiv.org/html/2606.14929#S2.E4), namelyΨm,μm\\Psi\_\{m\},\\mu\_\{m\}, andss, are unknown to the learner\. The name low\-rank “experts” come from the bandits with expert advice literature\(auer2002nonstochastic\)\.

##### Regularity Assumptions\.

We assume that all the embeddings areℓ2\\ell\_\{2\}\-normalized as∥q∥2,∥a∥2≤1\\lVert q\\rVert\_\{2\},\\lVert a\\rVert\_\{2\}\\leq 1,∀q∈𝒬,a∈𝒜\\forall q\\in\\mathcal\{Q\},a\\in\\mathcal\{A\}; all model kernels ensure∥Ψm∥2≤ϵ\\lVert\\Psi\_\{m\}\\rVert\_\{2\}\\leq\\sqrt\{\\epsilon\}; and the reward kernel satisfies∥Ψ∗∥2≤1\\lVert\\Psi^\{\\ast\}\\rVert\_\{2\}\\leq 1\.222The first condition is a standard practice in contrastive learning\(wang2020understanding, §3\)\. The second condition arises because, prior to computing a softmax over inner products, practitioners usually divide the logits by a large normalization or temperature parameter\. This technique is very common in Transformers\(vaswani2017attention\), knowledge distillation\(hinton2015distilling\), and model calibration\(guo2017calibration\)\. Should this condition fail to hold, our main result in[Section3](https://arxiv.org/html/2606.14929#S3)– namely the quadratic leading term identified in[Proposition1](https://arxiv.org/html/2606.14929#Thmtheorem1)– would still hold, albeit with a larger misspecification gap\. The third condition ensures bounded rewards and is standard in bandits and reinforcement learning\(jin2023provably,luo2021policy\)\.

### 2\.3Interaction Protocol, Feedback Model, and Policy Regret

Before the game, the environment fixes the reward kernelΨ∗\\Psi^\{\\ast\}, model kernels\{Ψm\}m\\\{\\Psi\_\{m\}\\\}\_\{m\}, and misspecification functionsν\\nuandμm\\mu\_\{m\}in[Equations˜2](https://arxiv.org/html/2606.14929#S2.E2)and[4](https://arxiv.org/html/2606.14929#S2.E4)\. The learner only knows the query space𝒬=ℝdq\\mathcal\{Q\}=\\mathbb\{R\}^\{d\_\{q\}\}, item set𝒜⊆ℝda\\mathcal\{A\}\\subseteq\\mathbb\{R\}^\{d\_\{a\}\}, number of modelsMM, and number of roundsTT\.333While practical hard constraints may make the item set time\-varying\(covington2016deep,wang2018billion,huang2020embedding\), incorporating such non\-stationarity via sleeping bandits\(kleinberg2010regret,kanade2009sleeping\)is orthogonal to our primary focus\. We assume a stationary item set𝒜\\mathcal\{A\}to isolate our core challenge of online embedding model routing\. The knowledge ofTTis for the ease of presentation, which can be relaxed via the standard doubling trick\(auer2002nonstochastic,besson2018doubling\)\. We remark that the low\-rank parameters=maxm⁡sms=\\max\_\{m\}s\_\{m\}– defined in[Equation4](https://arxiv.org/html/2606.14929#S2.E4)– is also unknown\.In each roundt=1,2,…,Tt=1,2,\\ldots,T:

1. 1\.the environment arbitrarily \(perhaps adaptively adversarially\) decides a queryqt∈𝒬q\_\{t\}\\in\\mathcal\{Q\};
2. 2\.each modelm∈\[M\]m\\in\[M\], observing the queryqtq\_\{t\}, crafts its distributionξm​\(qt\)\\xi\_\{m\}\(q\_\{t\}\)via[Equation˜4](https://arxiv.org/html/2606.14929#S2.E4);
3. 3\.the learner, observing queryqtq\_\{t\}but not the distributions, chooses an modelmt∈\[M\]m\_\{t\}\\in\[M\]to invoke;
4. 4\.the item recommended for this round is sampled from modelmtm\_\{t\}’s distribution asat,mt∼ξmt​\(qt\)a\_\{t,m\_\{t\}\}\\sim\\xi\_\{m\_\{t\}\}\(q\_\{t\}\);
5. 5\.the learner observes a noisy rewardrt=r​\(qt,at,mt\)\+ηtr\_\{t\}=r\(q\_\{t\},a\_\{t,m\_\{t\}\}\)\+\\eta\_\{t\}, wherert​\(q,a\)r\_\{t\}\(q,a\)is defined in[Equation˜2](https://arxiv.org/html/2606.14929#S2.E2)\. We assumeηt\\eta\_\{t\}is a zero\-mean and conditionally 1\-sub\-Gaussian noise\(abbasi2011improved\)\.

We remark that the feedback available to the learner is very limited\. First,*bandit reward feedback*: only the \(noisy\) reward induced by the actually recommended itemat,mta\_\{t,m\_\{t\}\}is revealed\. While this is a common challenge in both practical recommendation systems\(li2010contextual,chapelle2011empirical\)and theoretical bandits with expert advice\(auer2002nonstochastic,beygelzimer2011contextual\), the extremely*limited expert observability*is unique in the context of model routing: Only an item sampled from the chosen model’s distribution, namelyat,mta\_\{t,m\_\{t\}\}, is observable\. This, therefore, induces two layers of unobservability\. First, for each unselected modelm≠mtm\\neq m\_\{t\}, the learner does not know which item it would have recommended; second, for modelmtm\_\{t\}, only the recommended item – instead of the full distributionξmt​\(qt\)\\xi\_\{m\_\{t\}\}\(q\_\{t\}\)– is observed\. This challenge arises from the prohibitively large cost of invoking multiple models in practice: As argued bytsiourvas2025causalandzu2026barouter, it is unrealistic to assume counterfactual information from those unselected models\. In[Sections˜3](https://arxiv.org/html/2606.14929#S3.SS0.SSS0.Px2)and[3](https://arxiv.org/html/2606.14929#S3.SS0.SSS0.Px3), we will see how the limited observability and bandit feedback together constitute significant challenges\.

We consider the policy regret\(agarwal2014taming,syrgkanis2016efficient\), which compares our learner to a fixed class of model routing policies\. Formally, a*policy*is a mapping from query set𝒬\\mathcal\{Q\}to the probability simplex over all models, i\.e\.,△:=\{p∈\[0,1\]M∣∑m=1Mpm=1\}\\triangle:=\\\{p\\in\[0,1\]^\{M\}\\mid\\sum\_\{m=1\}^\{M\}p\_\{m\}=1\\\}\. The space of all policies is△𝒬\\triangle^\{\\mathcal\{Q\}\}\. The policy regret is defined w\.r\.t\. a fixed subset of policies, namelyΠ⊆△𝒬\\Pi\\subseteq\\triangle^\{\\mathcal\{Q\}\}, as:444Despite allowing an adaptive adversary, theqtq\_\{t\}’s in[Equation5](https://arxiv.org/html/2606.14929#S2.E5)are those queries actually realized under the learner’s policies \(that is, fixing the same query sequenceq1,q2,…,qTq\_\{1\},q\_\{2\},\\ldots,q\_\{T\}and finding the hindsight optimal policyπ∗∈Π\\pi^\{\\ast\}\\in\\Pi\)\. As proved byarora2012online, the*strict policy regret*– where the reference policyπ∗\\pi^\{\\ast\}is evaluated on its own induced queriesq1∗,q2∗,…,qT∗q\_\{1\}^\{\\ast\},q\_\{2\}^\{\\ast\},\\ldots,q\_\{T\}^\{\\ast\}– must beΩ​\(T\)\\Omega\(T\)\. We further remark that for the non\-convex policy classes like log\-linear and log\-quadratic, the literature instead studies*linearized*versions of the policy regret; see[Table1](https://arxiv.org/html/2606.14929#S3.T1),[Section3\.2](https://arxiv.org/html/2606.14929#S3.SS2), and[SectionsB\.4](https://arxiv.org/html/2606.14929#A2.SS4)and[B\.5](https://arxiv.org/html/2606.14929#A2.SS5)for more details\.

ℜT​\(Π\):=supπ∗∈Π𝔼\[∑t=1T𝔼m∼π∗​\(qt\)\[𝔼a∼ξm​\(qt\)\[r​\(qt,a\)\]\]−∑t=1Tr​\(qt,at\)\]\.\\mathfrak\{R\}\_\{T\}\(\\Pi\):=\\sup\_\{\\pi^\{\\ast\}\\in\\Pi\}\\operatornamewithlimits\{\\mathbb\{E\}\}\\left\[\\sum\_\{t=1\}^\{T\}\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{m\\sim\\pi^\{\\ast\}\(q\_\{t\}\)\}\\left\[\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{a\\sim\\xi\_\{m\}\(q\_\{t\}\)\}\[r\(q\_\{t\},a\)\]\\right\]\-\\sum\_\{t=1\}^\{T\}r\(q\_\{t\},a\_\{t\}\)\\right\]\.\(5\)Properly decidingΠ\\Pirecovers several commonly used regret metrics: WhenΠ=△𝒬\\Pi=\\triangle^\{\\mathcal\{Q\}\}takes the full policy space, it recovers the contextual regret, which is unfortunately intractable; whenΠ\\Pirestricts all queries to a fixed modelm∗∈\[M\]m^\{\\ast\}\\in\[M\], it reduces to the expert regret, which essentially ignores the heterogeneity of queries; whenΠ=Πlin\\Pi=\\Pi\_\{\\text\{lin\}\}is the standard log\-linear policy class, it turns out to be structurally misaligned with the underlying problem structure\. In[Section˜3](https://arxiv.org/html/2606.14929#S3), we study the first question of this paper: what is the most appropriate choice ofΠ\\Pifor embedding model routing?

## 3Policy Class: Tradeoff between Alignment and Tractability

Instead of more common policy classes \(discussed later in this section\), as a main contribution of this paper, we argue that the most appropriate choice ofΠ\\Piis the following*log\-quadratic*policy class:

Πquad:=\{π\(m∣q\)∝exp\(q𝖳Wmq\),∀q∈𝒬\|Wm∈𝕊dq,∀m∈\[M\]\},\\Pi\_\{\\text\{quad\}\}:=\\bigl\\\{\\pi\(m\\mid q\)\\propto\\exp\(q^\{\\mathsf\{T\}\}W\_\{m\}q\),\\forall q\\in\\mathcal\{Q\}\\mathrel\{\\big\|\}W\_\{m\}\\in\\mathbb\{S\}^\{d\_\{q\}\},\\forall m\\in\[M\]\\bigr\\\},\(6\)where𝕊dq\\mathbb\{S\}^\{d\_\{q\}\}is the space of symmetricdq×dqd\_\{q\}\\times d\_\{q\}matrices\.Πquad\\Pi\_\{\\text\{quad\}\}defines a parametric class of model routing policies: The probability of routing a queryqqto a modelmmis determined by a softmax distribution over the*quadratic score*q𝖳​Wm​qq^\{\\mathsf\{T\}\}W\_\{m\}q\(hence the name\)\. We first justify that this log\-quadratic class is well\-aligned with the underlying structure of the embedding model routing problem\.

##### Log\-Quadratic Class\.

In[Proposition˜1](https://arxiv.org/html/2606.14929#Thmtheorem1), we establish that in embedding model routing, the expected reward of any modelmmunder any queryqqis governed by a*low\-rank quadratic*structure:

###### Proposition 1\(True Rewards are Roughly Low\-Rank Quadratic\)\.

Given a queryq∈𝒬=ℝdqq\\in\\mathcal\{Q\}=\\mathbb\{R\}^\{d\_\{q\}\}, the expected reward of any modelm∈\[M\]m\\in\[M\]is approximated by a low\-rank quadratic form inqq, namely

Rm​\(q\):=𝔼a∼ξm​\(q\)\[r​\(q,a\)\]=C​\(q\)\+q𝖳​Wm∗​q\+δm​\(q\),∀m∈\[M\],q∈𝒬⊆ℝdq,R\_\{m\}\(q\):=\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{a\\sim\\xi\_\{m\}\(q\)\}\[r\(q,a\)\]=C\(q\)\+q^\{\\mathsf\{T\}\}W\_\{m\}^\{\\ast\}q\+\\delta\_\{m\}\(q\),\\quad\\forall m\\in\[M\],q\\in\\mathcal\{Q\}\\subseteq\\mathbb\{R\}^\{d\_\{q\}\},whereC​\(q\)C\(q\)is a constant shared across all models,Wm∗∈𝕊dqW\_\{m\}^\{\\ast\}\\in\\mathbb\{S\}^\{d\_\{q\}\}is a symmetric matrix with∥Wm∗∥∗≤rank\(Wm∗\)≤2​s\\lVert W\_\{m\}^\{\\ast\}\\rVert\_\{\\ast\}\\leq\\operatornamewithlimits\{\\mathrm\{rank\}\}\(W\_\{m\}^\{\\ast\}\)\\leq 2s, andδm​\(q\)\\delta\_\{m\}\(q\)is an𝒪⁡\(ϵ\)\\operatorname\{\\mathcal\{O\}\}\(\\epsilon\)misspecification gap due to the non\-linearity ofν\\nuandμm\\mu\_\{m\}\.

The proof is in[Section˜B\.1](https://arxiv.org/html/2606.14929#A2.SS1)\. In light of Proposition[1](https://arxiv.org/html/2606.14929#Thmtheorem1), let us consider the following family of score\-based embedding model router: Upon receiving a queryqq, the router calculates a scoresm​\(q\)s\_\{m\}\(q\)for each modelmm, and performs routing via a softmax over scores with some temperaturec−1c^\{\-1\}\. Such an architecture is ubiquitous in classification or model routing systems\(devlin2019bert,fedus2022switch\)\. The optimal score\-based routing policy is setting the score as the true reward, i\.e\.,

π∗​\(m∣q\)=exp⁡\(c​Rm​\(q\)\)∑m′=1Mexp⁡\(c​Rm′​\(q\)\)≈exp⁡\(c​q𝖳​Wm∗​q\)∑m′=1Mexp⁡\(c​q𝖳​Wm′∗​q\)∝exp⁡\(q𝖳​\(c​Wm∗\)​q\),∀m,\\pi^\{\\ast\}\(m\\mid q\)=\\frac\{\\exp\\bigl\(cR\_\{m\}\(q\)\\bigr\)\}\{\\sum\_\{m^\{\\prime\}=1\}^\{M\}\\exp\\bigl\(cR\_\{m^\{\\prime\}\}\(q\)\\bigr\)\}\\approx\\frac\{\\exp\\bigl\(cq^\{\\mathsf\{T\}\}W\_\{m\}^\{\\ast\}q\\bigr\)\}\{\\sum\_\{m^\{\\prime\}=1\}^\{M\}\\exp\\bigl\(cq^\{\\mathsf\{T\}\}W\_\{m^\{\\prime\}\}^\{\\ast\}q\\bigr\)\}\\propto\\exp\\Bigl\(q^\{\\mathsf\{T\}\}\\bigl\(cW\_\{m\}^\{\\ast\}\\bigr\)q\\Bigr\),\\penalty 10000\\ \\forall m,\(7\)
[Proposition˜1](https://arxiv.org/html/2606.14929#Thmtheorem1)and[Equation˜7](https://arxiv.org/html/2606.14929#S3.E7)thus suggest that optimal model routing policies are naturally approximated by our log\-quadratic class in[Equation˜6](https://arxiv.org/html/2606.14929#S3.E6), namelyΠquad=\{π\(m∣q\)∝exp\(q𝖳Wmq\)∣Wm∈𝕊dq,∀m\}\\Pi\_\{\\text\{quad\}\}=\\\{\\pi\(m\\mid q\)\\propto\\exp\(q^\{\\mathsf\{T\}\}W\_\{m\}q\)\\mid W\_\{m\}\\in\\mathbb\{S\}^\{d\_\{q\}\},\\forall m\\\}\. In addition to well\-aligned with the underlying structure of embedding model routing,Πquad\\Pi\_\{\\text\{quad\}\}is also tractable enough for learning: In[Section˜4](https://arxiv.org/html/2606.14929#S4), we design a computationally efficient policy gradient algorithm, HPG, that attains𝒪~⁡\(s​M​T\)\\operatorname\{\\widetilde\{\\operatorname\{\\mathcal\{O\}\}\}\}\(s\\sqrt\{MT\}\)*linearized*policy regret \(a surrogate metric we study; see[Section˜3\.2](https://arxiv.org/html/2606.14929#S3.SS2)\) w\.r\.t\.Πquad\\Pi\_\{\\text\{quad\}\}\. We thus conclude that, the log\-quadraticΠquad\\Pi\_\{\\text\{quad\}\}*offers an ideal trade\-off for embedding model routing*: well\-approximating the optimal policies, while enabling efficient learning\.

Having investigated our log\-quadratic class, we examine why standard policy classes fall short\. As depicted in[Table˜1](https://arxiv.org/html/2606.14929#S3.T1), we consider the following policy classes; detailed discussions are in[Appendix˜B](https://arxiv.org/html/2606.14929#A2)\.

Table 1:Comparison between Different Policy Classes or Regret Notions
##### Constant Class is Non\-Adaptive \([Section˜B\.2](https://arxiv.org/html/2606.14929#A2.SS2)\)\.

WhenΠ=Πconst\\Pi=\\Pi\_\{\\text\{const\}\}only contains constant policies, i\.e\.,π​\(q\)≡m\\pi\(q\)\\equiv mfor some fixedmm, we recover the*expert regret*for bandits with expert advice\. While simple, this metric is unfavorable for model routing: The benchmark is using the*same*model to answer all queries, while modern recommendation systems direct queries to distinct expert models for better performance\. We further justify thatℜT​\(Πconst\)\\mathfrak\{R\}\_\{T\}\(\\Pi\_\{\\text\{const\}\}\)fails to capture the structure of model routing problems: In[Theorem˜6](https://arxiv.org/html/2606.14929#Thmtheorem6), we establishℜT​\(Πconst\)=Ω​\(M​T/log⁡da\)\\mathfrak\{R\}\_\{T\}\(\\Pi\_\{\\text\{const\}\}\)=\\Omega\(\\sqrt\{MT/\\log d\_\{a\}\}\), which holds even if the learner observes all models’ recommendations\. Thus, a black\-box EXP3\(auer2002nonstochastic\), by entirely ignoring linear rewards and low\-rank model structures, is already near\-optimal w\.r\.t\.Πconst\\Pi\_\{\\text\{const\}\}\.

##### Unrestricted Class gives “Curse of Dimensionality” \([Section˜B\.3](https://arxiv.org/html/2606.14929#A2.SS3)\)\.

The other extreme is the unrestrictedΠ=△𝒬\\Pi=\\triangle^\{\\mathcal\{Q\}\}, resembling the contextual regret in contextual bandits\. This is favorable because the learner competes with*any*query\-adaptive routing policy\. However, this class remains notorious even under two assumptions:\(A1\)no misspecification and\(A2\)known model kernels\.

Under these two assumptions, we first reduceℜT​\(△𝒬\)\\mathfrak\{R\}\_\{T\}\(\\triangle^\{\\mathcal\{Q\}\}\)to ada​dqd\_\{a\}d\_\{q\}\-dimensional contextual linear bandit\. The VCL\-SupLinUCB algorithm\(li2019nearly\)attainsℜTC=𝒪⁡\(da​dq​T​log⁡M​log⁡T\)\\mathfrak\{R\}\_\{T\}^\{C\}=\\operatorname\{\\mathcal\{O\}\}\(\\sqrt\{d\_\{a\}d\_\{q\}T\\log M\\log T\}\)regret at a per\-round computational cost of𝒪⁡\(da2​dq2​M\)\\operatorname\{\\mathcal\{O\}\}\(d\_\{a\}^\{2\}d\_\{q\}^\{2\}M\)\. Neither the regret nor computational cost is acceptable: In embedding model routing, the dimensions of query and item spaces are both large\. For example,RouterRetriver\(lee2025routerretriever\)embeds queries and items intodq=da=768d\_\{q\}=d\_\{a\}=768\-dimensional spaces viaContriever\(izacard2022unsupervised\)\. Hence ifT/\(log⁡M​log⁡T\)≤7682≈5×105T/\(\\log M\\log T\)\\leq 768^\{2\}\\approx 5\\times 10^\{5\}, the regret bound becomes vacuous\. The per\-round per\-modelda2​dq2≈3×1011d\_\{a\}^\{2\}d\_\{q\}^\{2\}\\approx 3\\times 10^\{11\}computation cost is also unbearable\. Such a*“curse of dimensionality”*\(Footnote[5](https://arxiv.org/html/2606.14929#footnote5)\) thus makes this algorithm impractical\.

In[Section˜B\.3](https://arxiv.org/html/2606.14929#A2.SS3), we discuss why other seemingly more promising reductions \(e\.g\., todad\_\{a\}\-dimensional adversarial contextual linear bandits\) fail to refine the regret: Even if assuming i\.i\.d\. queries – in addition to assumptions\(A1\)and\(A2\)– the correlation between recommendation distributionsξm\(⋅∣qt\)\\xi\_\{m\}\(\\cdot\\mid q\_\{t\}\)and rewardsr​\(qt,⋅\)r\(q\_\{t\},\\cdot\)still makes existing algorithms inapplicable \(see[Section˜B\.3\.3](https://arxiv.org/html/2606.14929#A2.SS3.SSS3)\)\.

##### Log\-Linear Class is Misaligned \([Section˜B\.4](https://arxiv.org/html/2606.14929#A2.SS4)\)\.

In reinforcement learning, another commonly used policy class is the*log\-linear*classΠlin:=\{π\(m∣q\)∝exp\(θm𝖳q\)∣θm∈ℝdq,∀m\}\\Pi\_\{\\text\{lin\}\}:=\\\{\\pi\(m\\mid q\)\\propto\\exp\(\\theta\_\{m\}^\{\\mathsf\{T\}\}q\)\\mid\\theta\_\{m\}\\in\\mathbb\{R\}^\{d\_\{q\}\},\\forall m\\\}\(agarwal2021theory,mei2020global\)\. The parameter space ofΠlin\\Pi\_\{\\text\{lin\}\}, namelyΘ=\(ℝdq\)M\\Theta=\(\\mathbb\{R\}^\{d\_\{q\}\}\)^\{M\}, is of dimensionM​dqMd\_\{q\}, which is much smaller than that of ourΠquad\\Pi\_\{\\text\{quad\}\}\. Based on Natural Policy Gradient \(NPG;kakade2001natural\),agarwal2021theoryattain𝒪⁡\(dq​M​T​log⁡T\)\\operatorname\{\\mathcal\{O\}\}\(\\sqrt\{d\_\{q\}MT\\log T\}\)*linearized*policy regret w\.r\.t\.Πlin\\Pi\_\{\\text\{lin\}\}at a per\-round computational cost of𝒪⁡\(dq2​M2\)\\operatorname\{\\mathcal\{O\}\}\(d\_\{q\}^\{2\}M^\{2\}\)\.777The regret notionagarwal2021theoryused for the log\-linear policy class also adopts linearization to handle the non\-convexity of softmax\. However, we remark that their linearization happens in a different space to ours\. We direct the readers to[Section3\.2](https://arxiv.org/html/2606.14929#S3.SS2)and[SectionsB\.4](https://arxiv.org/html/2606.14929#A2.SS4)and[B\.5](https://arxiv.org/html/2606.14929#A2.SS5)for detailed discussions\.Compared to the unrestricted class, under the samedq=da=768d\_\{q\}=d\_\{a\}=768example, the vacuous regret regime only lasts for768⋅M768\\cdot Mrounds, and the per\-round computational cost reduces to6×105⋅M26\\times 10^\{5\}\\cdot M^\{2\}\. Given its simplicity,Πlin\\Pi\_\{\\text\{lin\}\}is already used in practical model routing:RouterRetriever\(lee2025routerretriever\)routes queries based on the cosine similarity between the queryqtq\_\{t\}and models’ “representative training data,” thus essentially resembling theθm𝖳​q\\theta\_\{m\}^\{\\mathsf\{T\}\}q\.

However, despite its tractability and popularity,Πlin\\Pi\_\{\\text\{lin\}\}is structurally misaligned: As established in[Proposition˜1](https://arxiv.org/html/2606.14929#Thmtheorem1), the true rewards are governed by a*quadratic*structureq𝖳​Wm∗​qq^\{\\mathsf\{T\}\}W\_\{m\}^\{\\ast\}q\. A linear scoreθm𝖳​q\\theta\_\{m\}^\{\\mathsf\{T\}\}qthus*fails*to capture the interactions between different dimensions ofqq\. Consequently, even with optimal policy regret w\.r\.t\.Πlin\\Pi\_\{\\text\{lin\}\}, the learner remains sub\-optimal in actual model routing tasks\.

### 3\.1Numerical Verification on Amazon ESCI Dataset

In[Table˜2](https://arxiv.org/html/2606.14929#S3.T2), we consider four policy classes – the constantΠconst\\Pi\_\{\\text\{const\}\}, the log\-linearΠlin\\Pi\_\{\\text\{lin\}\}, the log\-quadraticΠquad\\Pi\_\{\\text\{quad\}\}, and the unrestricted△𝒬\\triangle^\{\\mathcal\{Q\}\}– over the Amazon ESCI dataset\(reddy2022shopping\)\. This dataset benchmarks 97,345 difficult search queries in e\-commerce: Each consumer query is associated with several candidate products \(18\.68 on average\) with titles, descriptions, and keywords, all in natural language\. Each query\-action pair is annotated with one of E\(xact\), S\(ubstitute\), C\(omplement\), or I\(rrelevant\), which we convert into numerical values as the reward functionr:𝒬×𝒜→\[0,1\]r\\colon\\mathcal\{Q\}\\times\\mathcal\{A\}\\to\[0,1\]\.

We considerM=8M=8lightweight embedding models as candidate experts, spanning symmetric semantic encoders likeminiLM\(wang2020minilm,wang2021minilmv2\), asymmetric search models likemsmarco\-distilbert\(reimers2019sentence\), and modern prompt\-driven encoders\(wang2022text,xiao2024c\)\. The detailed experimental setup, as well as more discussions, can be found in[Appendix˜C](https://arxiv.org/html/2606.14929#A3)\.

To facilitate model routing, we embed queries and items into 768\-dimensional vector spaces viaContriever\(izacard2022unsupervised\)before feeding them to the learner; this follows the practice ofRouterRetriever\(lee2025routerretriever\)\.888While expert models generate recommendations based on the similarity score between embeddings \(see[AppendixC](https://arxiv.org/html/2606.14929#A3)\), the learner*cannot*access such embeddings\. The reason is two\-fold: As argued bytsiourvas2025causalandzu2026barouter, it is impractical to feed every incoming query into every candidate model; hence the learner can only choose one model, observe its recommendation, and collect its reward \(see[Section2\.3](https://arxiv.org/html/2606.14929#S2.SS3)\)\. Moreover, models’ embeddings lie in different spaces and are incomparable with each other; we hence need a single embedding to define the policy classes\.We denote an embedded query byq∈ℝdqq\\in\\mathbb\{R\}^\{d\_\{q\}\}and an embedded item bya∈ℝdaa\\in\\mathbb\{R\}^\{d\_\{a\}\}, withdq=da=768d\_\{q\}=d\_\{a\}=768\. We then find the optimal routing policy from each policy class: the constantΠconst\\Pi\_\{\\text\{const\}\}, the log\-linearΠlin\\Pi\_\{\\text\{lin\}\}, our log\-quadraticΠquad\\Pi\_\{\\text\{quad\}\}, and the unrestrictedΔ𝒬\\Delta^\{\\mathcal\{Q\}\}\.

For any routing policyπ:𝒬→△\\pi\\colon\\mathcal\{Q\}\\to\\triangle, we define it sub\-optimality gap on the ESCI dataset as follows:

Gap​\(π\):=𝔼q\[maxm∈\[M\]​𝔼a∼ξm​\(q\)\[r​\(q,a\)\]−𝔼m∼π​\(q\)\[𝔼a∼ξm​\(q\)\[r​\(q,a\)\]\]\],∀π∈△𝒬,\\text\{Gap\}\(\\pi\):=\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{q\}\\left\[\\max\_\{m\\in\[M\]\}\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{a\\sim\\xi\_\{m\}\(q\)\}\[r\(q,a\)\]\-\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{m\\sim\\pi\(q\)\}\\left\[\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{a\\sim\\xi\_\{m\}\(q\)\}\[r\(q,a\)\]\\right\]\\right\],\\quad\\forall\\pi\\in\\triangle^\{\\mathcal\{Q\}\},\(8\)where𝔼q\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{q\}is taken w\.r\.t\. the uniform distribution over all ESCI queries \(i\.e\., the average sub\-optimality on each query\), and recall that the rewardr​\(q,a\)r\(q,a\)is constructed using the E, S, C, and I labels in the dataset\.Gap​\(π\)\\text\{Gap\}\(\\pi\)hence comparesπ\\pito the best adaptive policy mapping any query to any model\.

Table 2:Sub\-Optimality Gap of Different Policy Classes on Amazon ESCI DatasetQueryNum ofΠconst\\Pi\_\{\\text\{const\}\}Πlin\\Pi\_\{\\text\{lin\}\}Πconst\\Pi\_\{\\text\{const\}\}→\\toΠlin\\Pi\_\{\\text\{lin\}\}Πquad\\Pi\_\{\\text\{quad\}\}Πlin\\Pi\_\{\\text\{lin\}\}→\\toΠquad\\Pi\_\{\\text\{quad\}\}CategoryQueriesGap \(↓\\downarrow\)Gap \(↓\\downarrow\)Improvement \(↑\\uparrow\)Gap \(↓\\downarrow\)Improvement \(↑\\uparrow\)all97,3450\.0780\.06516\.4%0\.02168\.0%\[1pt/3pt\]nlqec1690\.1090\.00397\.4%<0\.00199\.8%behavioral1,2530\.0670\.01282\.3%<0\.00199\.4%parse\-pattern4,2500\.0640\.02462\.2%0\.00293\.3%negations2,8990\.1320\.06054\.6%0\.00788\.9%other88,7740\.0740\.06019\.1%0\.01771\.4%In[Table˜2](https://arxiv.org/html/2606.14929#S3.T2), we report the following quantities about the optimal policy from each class:999In addition to the first row evaluating on the full ESCI dataset, we also evaluate them on a few “query categories,” provided byreddy2022shoppingas exceptionally hard queries; more details and discussions are in[AppendixC](https://arxiv.org/html/2606.14929#A3)\.

- •Πconst\\Pi\_\{\\text\{const\}\}gap, which is the sub\-optimality gap of the best constant policyπconst∗∈Πconst\\pi\_\{\\text\{const\}\}^\{\\ast\}\\in\\Pi\_\{\\text\{const\}\}\(mapping all queries to a fixed expert model\)\. This quantity measures the necessity and difficulty of model routing: A largeπconst∗\\pi\_\{\\text\{const\}\}^\{\\ast\}implies that no single model dominates the others on \(most of\) the queries\.
- •Πlin\\Pi\_\{\\text\{lin\}\}gap and its improvement overΠconst\\Pi\_\{\\text\{const\}\}\. We find the best routing policyπlin∗\\pi\_\{\\text\{lin\}\}^\{\\ast\}in the log\-linear classΠlin=\{π\(m∣q\)∝exp\(θm𝖳q\)∣θm∈ℝdq,∀m\}\\Pi\_\{\\text\{lin\}\}=\\\{\\pi\(m\\mid q\)\\propto\\exp\(\\theta\_\{m\}^\{\\mathsf\{T\}\}q\)\\mid\\theta\_\{m\}\\in\\mathbb\{R\}^\{d\_\{q\}\},\\forall m\\\}, and calculate sub\-optimalityGap​\(πlin∗\)\\text\{Gap\}\(\\pi\_\{\\text\{lin\}\}^\{\\ast\}\)according to[Equation˜8](https://arxiv.org/html/2606.14929#S3.E8)\. We then report1−Gap​\(πlin∗\)/Gap​\(πconst∗\)1\-\\text\{Gap\}\(\\pi\_\{\\text\{lin\}\}^\{\\ast\}\)/\\text\{Gap\}\(\\pi\_\{\\text\{const\}\}^\{\\ast\}\)as the improvement ofΠlin\\Pi\_\{\\text\{lin\}\}overΠconst\\Pi\_\{\\text\{const\}\}\.
- •Πquad\\Pi\_\{\\text\{quad\}\}gap and its improvement overΠlin\\Pi\_\{\\text\{lin\}\}\. This is almost similar to the previous metric, except that we now compare our proposed log\-quadratic policyπquad∗∈Πquad\\pi\_\{\\text\{quad\}\}^\{\\ast\}\\in\\Pi\_\{\\text\{quad\}\}to the log\-linear policyπlin∗\\pi\_\{\\text\{lin\}\}^\{\\ast\}\.

From[Table˜2](https://arxiv.org/html/2606.14929#S3.T2), we see thatΠquad\\Pi\_\{\\text\{quad\}\}is indeed well\-suited for the problem of embeddig model routing: Over the full ESCI dataset \(row “all”\), the constant policy suffers a sub\-optimality gap of0\.0780\.078, and the log\-linear policy still has a gap of0\.0650\.065\(only16\.4%16\.4\\%improvement\)\. On the other hand, our log\-quadratic policy reduces the gap to 0\.021, which is a68\.0%68\.0\\%improvement over the log\-linear policy\. For various harder categories – likenlqecandnegations– the constant policy suffers from a significantly larger sub\-optimality gap \(compared to the full\-dataset average, i\.e\., these categories are indeed harder\), but our log\-quadratic policy improves the gaps significantly\.

To conclude, by comparing different policy classes,[Table˜2](https://arxiv.org/html/2606.14929#S3.T2)demonstrates not only the necessity of dynamic model routing, but also the low misspecification of our log\-quadratic policy classΠquad\\Pi\_\{\\text\{quad\}\}\.

### 3\.2Additional Notations and Linearized Policy Regret

We therefore focus on our log\-quadraticΠquad\\Pi\_\{\\text\{quad\}\}class\. To facilitate subsequent algorithm design, we give a few extra notations: Since each policy is parameterized byMMsymmetricdq×dqd\_\{q\}\\times d\_\{q\}matrices, we collect them into a single diagonal block matrix𝑾=diag⁡\(W1,W2,…,WM\)∈𝕊M​dq\\bm\{W\}=\\operatorname\{\\mathrm\{diag\}\}\(W\_\{1\},W\_\{2\},\\ldots,W\_\{M\}\)\\in\\mathbb\{S\}^\{Md\_\{q\}\}, which we call a*parameter*\. We use boldface letters for parameters\. The parameter space𝕎⊆𝕊M​dq\\mathbb\{W\}\\subseteq\\mathbb\{S\}^\{Md\_\{q\}\}then has a dimension ofM​dq2Md\_\{q\}^\{2\}\. According to[Equation˜6](https://arxiv.org/html/2606.14929#S3.E6), each parameter𝑾∈𝕎\\bm\{W\}\\in\\mathbb\{W\}induces a model routing policy:

π𝑾​\(m∣q\):=exp⁡\(q𝖳​Wm​q\)∑m′=1Mexp⁡\(q𝖳​Wm′​q\),∀m=1,2,…,M\.\\pi\_\{\\bm\{W\}\}\(m\\mid q\):=\\frac\{\\exp\(q^\{\\mathsf\{T\}\}W\_\{m\}q\)\}\{\\sum\_\{m^\{\\prime\}=1\}^\{M\}\\exp\(q^\{\\mathsf\{T\}\}W\_\{m^\{\\prime\}\}q\)\},\\quad\\forall m=1,2,\\ldots,M\.\(9\)For each roundt∈\[T\]t\\in\[T\], define the expected loss \(negative reward\) suffered by any parameter𝑾\\bm\{W\}as

ℒt​\(𝑾\):=−𝔼m∼π𝑾​\(qt\)\[𝔼a∼ξm​\(qt\)\[r​\(qt,a\)\]\],∀t∈\[T\],𝑾∈𝕎\.\\mathcal\{L\}\_\{t\}\(\\bm\{W\}\):=\-\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{m\\sim\\pi\_\{\\bm\{W\}\}\(q\_\{t\}\)\}\\left\[\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{a\\sim\\xi\_\{m\}\(q\_\{t\}\)\}\\left\[r\(q\_\{t\},a\)\\right\]\\right\],\\quad\\forall t\\in\[T\],\\bm\{W\}\\in\\mathbb\{W\}\.\(10\)Then the policy regret w\.r\.t\.Πquad\\Pi\_\{\\text\{quad\}\}, namelyℜT​\(Πquad\)\\mathfrak\{R\}\_\{T\}\(\\Pi\_\{\\text\{quad\}\}\), issup𝑾∗∈𝕎𝔼\[∑t=1Tℒt​\(𝑾t\)−ℒt​\(𝑾∗\)\]\\sup\_\{\\bm\{W\}^\{\\ast\}\\in\\mathbb\{W\}\}\\operatornamewithlimits\{\\mathbb\{E\}\}\[\\sum\_\{t=1\}^\{T\}\\mathcal\{L\}\_\{t\}\(\\bm\{W\}\_\{t\}\)\-\\mathcal\{L\}\_\{t\}\(\\bm\{W\}^\{\\ast\}\)\]\. From[Proposition˜1](https://arxiv.org/html/2606.14929#Thmtheorem1), we assume that an optimal𝑾∗∈𝕎\\bm\{W\}^\{\\ast\}\\in\\mathbb\{W\}ensures∥Wm∗∥∗≤rank\(Wm∗\)≤2​s\\lVert W\_\{m\}^\{\\ast\}\\rVert\_\{\\ast\}\\leq\\operatornamewithlimits\{\\mathrm\{rank\}\}\(W\_\{m\}^\{\\ast\}\)\\leq 2s,∀m\\forall m\.

Unfortunately, since softmax is non\-convex, neither policy \([Equation˜9](https://arxiv.org/html/2606.14929#S3.E9)\) nor loss \([Equation˜10](https://arxiv.org/html/2606.14929#S3.E10)\) is convex\. Consistent with previous policy gradient analysis \(detailed in[Section˜B\.4](https://arxiv.org/html/2606.14929#A2.SS4);agarwal2021theory\), we define a surrogate metric for the policy regretℜT​\(Πquad\)\\mathfrak\{R\}\_\{T\}\(\\Pi\_\{\\text\{quad\}\}\)via a*local linearization*\. Specifically, we perform linearization on the parameter space𝕎\\mathbb\{W\}and consider the following linearized policy regret:

ℜ~T​\(Πquad\):=sup𝑾∗∈𝕎𝔼\[∑t=1T⟨∇ℒt​\(𝑾t\),𝑾t−𝑾∗⟩F\]\.\\widetilde\{\\mathfrak\{R\}\}\_\{T\}\(\\Pi\_\{\\text\{quad\}\}\):=\\sup\_\{\\bm\{W\}^\{\\ast\}\\in\\mathbb\{W\}\}\\operatornamewithlimits\{\\mathbb\{E\}\}\\left\[\\sum\_\{t=1\}^\{T\}\\Bigl\\langle\\nabla\\mathcal\{L\}\_\{t\}\(\\bm\{W\}\_\{t\}\),\\bm\{W\}\_\{t\}\-\\bm\{W\}^\{\\ast\}\\Bigr\\rangle\_\{F\}\\right\]\.\(11\)Each term in the sum of[Equation˜11](https://arxiv.org/html/2606.14929#S3.E11)recovers the Frank\-Wolfe gap in online non\-convex optimization\(lafond2015online,reddi2016stochastic\), commonly used for, e\.g\., online submodular optimization\(hassani2017gradient,chen2018online,zhang2019online\)\. See[Section˜B\.5](https://arxiv.org/html/2606.14929#A2.SS5)for a more technical comparison betweenℜT​\(Πquad\)\\mathfrak\{R\}\_\{T\}\(\\Pi\_\{\\text\{quad\}\}\)and our linearizedℜ~T​\(Πquad\)\\widetilde\{\\mathfrak\{R\}\}\_\{T\}\(\\Pi\_\{\\text\{quad\}\}\)\. While we considerℜ~T\\widetilde\{\\mathfrak\{R\}\}\_\{T\}as a surrogate metric to handle non\-convexity, tackling policy regret exactly remains an important open question\.

## 4Hypentropy Policy Gradient \(HPG\) for Model Routing

We now introduce our algorithm for the log\-quadratic policy classΠquad\\Pi\_\{\\text\{quad\}\}\. Moving from the log\-linear classΠlin\\Pi\_\{\\text\{lin\}\}toΠquad\\Pi\_\{\\text\{quad\}\}improves approximation accuracy \(see[Proposition˜1](https://arxiv.org/html/2606.14929#Thmtheorem1)and[Equation˜7](https://arxiv.org/html/2606.14929#S3.E7)\), but comes at a cost: The parameter space dimension increases fromdim\(Θ\)=dq​M\\dim\(\\Theta\)=d\_\{q\}Mtodim\(𝕎\)=dq2​M\\dim\(\\mathbb\{W\}\)=d\_\{q\}^\{2\}M\. Hence, naively flattening𝕎\\mathbb\{W\}into adq2​Md\_\{q\}^\{2\}M\-dimensional vector space and applying policy gradient methods gives𝒪⁡\(dq​M​T​log⁡T\)\\operatorname\{\\mathcal\{O\}\}\(d\_\{q\}\\sqrt\{MT\\log T\}\)regret and requires𝒪⁡\(dq4​M\)\\operatorname\{\\mathcal\{O\}\}\(d\_\{q\}^\{4\}M\)computation per round\(agarwal2021theory\)\. Similar to the unrestricted class discussed in[Section˜3](https://arxiv.org/html/2606.14929#S3), both bounds can be probitively large\.

Fortunately, because embedding models operate on low\-dimensional representation spaces,[Proposition˜1](https://arxiv.org/html/2606.14929#Thmtheorem1)shows that the optimal parameter𝑾∗\\bm\{W\}^\{\\ast\}also contains only low\-rank matrices\. This observation is key to bypassing the curse of dimensionality: If we restrict learning to those low\-rankWmW\_\{m\}’s, the effective parameter dimension reduces toΘ​\(s​dq​M\)\\Theta\(sd\_\{q\}M\)\. But this is challenging: the reward kernelΨ∗\\Psi^\{\\ast\}in[Equation˜2](https://arxiv.org/html/2606.14929#S2.E2)is*not*low\-rank, so standard low\-rank or sparse regression approaches \(e\.g\., ridge or lasso\) do not apply\. That is, the low\-rank structure only lies in the*parameter*space, not in the*reward*space\.

Standard policy gradient methods also inherently fail to exploit this hidden structure\. Indeed, NPG – which is equivalent to Online Mirror Descent \(OMD\) equipped with a KL\-divergence regularizer\(geist2019theory\)– is isotropic across directions and thus does not adapt to the rank\.101010In fact, vanilla NPG is only defined on the flattened vector space, where the low\-rank structure of𝑾∗\\bm\{W\}^\{\\ast\}is lost\. Exploiting low\-rankness requires working with matrix spaces, but the matrix analogue of NPG – OMD with von Neumann entropyΦ​\(X\)=Tr\(X​log⁡X−X\)\\Phi\(X\)=\\operatornamewithlimits\{\\mathrm\{Tr\}\}\(X\\log X\-X\)– is only defined for*positive semi\-definite*matrices\(tsuda2005matrix\)\.We thus instead use the hypentropy regularizer\(ghai2020exponentiated\)to promote low\-rankness; see[Section˜4\.1](https://arxiv.org/html/2606.14929#S4.SS1)\.

In addition to this new regularizer, due to our challenge of bandit feedback and partial observability, we also design a REINFORCE\-style gradient estimator; see[Section˜4\.2](https://arxiv.org/html/2606.14929#S4.SS2)\. These together giveHypentropyPolicyGradient \(HPG\) in[Algorithm˜1](https://arxiv.org/html/2606.14929#alg1)\. We remark this estimator’s effect is two\-fold: First, as standard in the literature, it is unbiased and low\-variance, thus allowing provable performances under incomplete information \([Theorem˜3](https://arxiv.org/html/2606.14929#Thmtheorem3)\); second, which is unique to our log\-quadratic policy classΠquad\\Pi\_\{\\text\{quad\}\}, it can reduce the computational cost of OMD\. Indeed, as we discuss in[Section˜5](https://arxiv.org/html/2606.14929#S5), our HPG admits computationally efficient – only𝒪⁡\(dq2​M\)\\operatorname\{\\mathcal\{O\}\}\(d\_\{q\}^\{2\}M\)runtime per round – and parameter\-free implementations\.

### 4\.1Nuclear\-Norm Ball, Hypentropy, and Online Mirror Descent

Algorithm 1HypentropyPolicyGradient \(HPG\) for Model Routing1:Game lengthTT, query set𝒬⊆ℝdq\\mathcal\{Q\}\\subseteq\\mathbb\{R\}^\{d\_\{q\}\}, candidate item set𝒜⊆ℝda\\mathcal\{A\}\\subseteq\\mathbb\{R\}^\{d\_\{a\}\}, number of modelsMM\.Hypentropy parameterβ\>0\\beta\>0, learning rateη\>0\\eta\>0, nuclear norm boundτ\>0\\tau\>0\.

2:Initialize𝑾1\\bm\{W\}\_\{1\}as theM​dq×M​dqMd\_\{q\}\\times Md\_\{q\}all\-zero matrix, which is a diagonal block matrix in𝕊M​dq\\mathbb\{S\}^\{Md\_\{q\}\}\.

3:fort=1,2,…,Tt=1,2,\\ldots,Tdo

4:Observe queryqtq\_\{t\}\. Decide modelmtm\_\{t\}according toπ𝑾t​\(qt\)\\pi\_\{\\bm\{W\}\_\{t\}\}\(q\_\{t\}\)⊳\\trianglerightπ𝐖\\pi\_\{\\bm\{W\}\}is in[Equation˜9](https://arxiv.org/html/2606.14929#S3.E9)

5:Observe modelmtm\_\{t\}’s recommendationat,mt∼ξmt​\(qt\)a\_\{t,m\_\{t\}\}\\sim\\xi\_\{m\_\{t\}\}\(q\_\{t\}\)⊳\\trianglerightξm\\xi\_\{m\}is in[Equation˜4](https://arxiv.org/html/2606.14929#S2.E4)

6:Recommend itemat,mta\_\{t,m\_\{t\}\}\. Observert=r​\(qt,at,mt\)\+ηtr\_\{t\}=r\(q\_\{t\},a\_\{t,m\_\{t\}\}\)\+\\eta\_\{t\}⊳\\trianglerightr​\(q,a\)r\(q,a\)is in[Equation˜2](https://arxiv.org/html/2606.14929#S2.E2)

7:Construct gradient estimator𝑮^t\\widehat\{\\bm\{G\}\}\_\{t\}usingqt,mt,rtq\_\{t\},m\_\{t\},r\_\{t\}⊳\\triangleright𝐆^t\\widehat\{\\bm\{G\}\}\_\{t\}is in[Equation˜15](https://arxiv.org/html/2606.14929#S4.E15)

8:Perform an Online Mirror Descent \(OMD\) step over𝔹∗M​\(τ\)\\mathbb\{B\}\_\{\\ast\}^\{M\}\(\\tau\)\.⊳\\triangleright[Equations˜12](https://arxiv.org/html/2606.14929#S4.E12),[13](https://arxiv.org/html/2606.14929#S4.E13)and[14](https://arxiv.org/html/2606.14929#S4.E14)

We introduce the first component of our algorithm: a hypentropy\-regularized OMD\. Since the optimal parameter𝑾∗\\bm\{W\}^\{\\ast\}is low\-rank, we restrict our parameter space to a*product nuclear\-norm ball*:

𝔹∗M\(τ\):=\{diag\(W1,W2,…,WM\)\|Wm∈𝕊dq,∥Wm∥∗≤τ,∀m\}\.\\mathbb\{B\}\_\{\\ast\}^\{M\}\(\\tau\):=\\bigl\\\{\\operatorname\{\\mathrm\{diag\}\}\(W\_\{1\},W\_\{2\},\\ldots,W\_\{M\}\)\\mathrel\{\\big\|\}W\_\{m\}\\in\\mathbb\{S\}^\{d\_\{q\}\},\\lVert W\_\{m\}\\rVert\_\{\\ast\}\\leq\\tau,\\forall m\\bigr\\\}\.\(12\)
Theτ≥0\\tau\\geq 0is a parameter to be determined later, and∥⋅∥∗\\lVert\\cdot\\rVert\_\{\\ast\}is the matrix nuclear norm \(sum of absolute eigenvalues\) that serves as a convex surrogate for matrix rank\. According to[Proposition˜1](https://arxiv.org/html/2606.14929#Thmtheorem1), we know∥Wm∗∥∗≤rank\(Wm∗\)∥Wm∗∥2≤2s\\lVert W\_\{m\}^\{\\ast\}\\rVert\_\{\\ast\}\\leq\\operatornamewithlimits\{\\mathrm\{rank\}\}\(W\_\{m\}^\{\\ast\}\)\\lVert W\_\{m\}^\{\\ast\}\\rVert\_\{2\}\\leq 2s, which means𝑾∗∈𝔹∗M​\(2​s\)\\bm\{W\}^\{\\ast\}\\in\\mathbb\{B\}\_\{\\ast\}^\{M\}\(2s\)\. For the ease of presentation, for now, we assume the low\-rank parameterssis known; we will drop this assumption in[Section˜5\.2](https://arxiv.org/html/2606.14929#S5.SS2)\.

Given a properly chosen parameterτ\\tau, our HPG algorithm performs OMD on𝔹∗M​\(τ\)\\mathbb\{B\}\_\{\\ast\}^\{M\}\(\\tau\)\. The regularizer we use is the hyperbolic entropy \(*hypentropy*;ghai2020exponentiated\), which is strongly convex with respect to the nuclear norm, making it well\-suited for promoting low\-rank structures in the parameter space\.111111The connection between hypentropy and low\-rankness has been exploited bywoodworth2020kernel,pesme2021implicit,li2022implicit,varre2023spectral, andjacobs2025mirrorto understand the implicit bias/regularization in neural network training, bywu2020continuous,wu2023nearlyin sparse phase retrieval problems, and bywu2021implicitfor low\-rank matrix sensing\. However, we are unaware of existing works using this property for policy regret, bandit feedback, or embedding model routing\.Formally, for a parameterβ\>0\\beta\>0to be specified later, theβ\\beta\-hypentropy of𝑾∈𝕊M​dq\\bm\{W\}\\in\\mathbb\{S\}^\{Md\_\{q\}\}is defined as

Φβ​\(𝑾\):=∑i=1M​dq\(λi​arcsinh⁡λiβ−λi2\+β2\),∀𝑾∈𝕊M​dq,\\Phi\_\{\\beta\}\(\\bm\{W\}\):=\\sum\_\{i=1\}^\{Md\_\{q\}\}\\left\(\\lambda\_\{i\}\\operatorname\{\\mathrm\{arcsinh\}\}\\frac\{\\lambda\_\{i\}\}\{\\beta\}\-\\sqrt\{\\lambda\_\{i\}^\{2\}\+\\beta^\{2\}\}\\right\),\\quad\\forall\\bm\{W\}\\in\\mathbb\{S\}^\{Md\_\{q\}\},\(13\)whereλ1≥λ2≥⋯≥λM​dq\\lambda\_\{1\}\\geq\\lambda\_\{2\}\\geq\\cdots\\geq\\lambda\_\{Md\_\{q\}\}are the eigenvalues of𝑾\\bm\{W\}in non\-increasing order\. UsingΦβ\\Phi\_\{\\beta\}as the regularizer, the OMD update of HPG over the product ball𝔹∗M​\(τ\)\\mathbb\{B\}\_\{\\ast\}^\{M\}\(\\tau\)takes the following form:

𝑾t\+1=argmin𝑾∈𝔹∗M​\(τ\)\(η​⟨𝑾,𝑮^t⟩F\+DΦβ​\(𝑾∥𝑾t\)\),∀t=1,2,…,T,\\bm\{W\}\_\{t\+1\}=\\operatornamewithlimits\{\\mathrm\{argmin\}\}\_\{\\bm\{W\}\\in\\mathbb\{B\}\_\{\\ast\}^\{M\}\(\\tau\)\}\\Bigl\(\\eta\\bigl\\langle\\bm\{W\},\\widehat\{\\bm\{G\}\}\_\{t\}\\bigr\\rangle\_\{F\}\+D\_\{\\Phi\}^\{\\beta\}\(\\bm\{W\}\\\|\\bm\{W\}\_\{t\}\)\\Bigr\),\\quad\\forall t=1,2,\\ldots,T,\(14\)whereη\>0\\eta\>0is a parameter to be determined;𝑮^t\\widehat\{\\bm\{G\}\}\_\{t\}is the \(estimated\) gradient defined in[Section˜4\.2](https://arxiv.org/html/2606.14929#S4.SS2); andDΦβ​\(𝑾∥𝑾′\):=Φβ​\(𝑾\)−Φβ​\(𝑾′\)−⟨∇Φβ​\(𝑾′\),𝑾−𝑾′⟩FD\_\{\\Phi\}^\{\\beta\}\(\\bm\{W\}\\\|\\bm\{W\}^\{\\prime\}\):=\\Phi\_\{\\beta\}\(\\bm\{W\}\)\-\\Phi\_\{\\beta\}\(\\bm\{W\}^\{\\prime\}\)\-\\langle\\nabla\\Phi\_\{\\beta\}\(\\bm\{W\}^\{\\prime\}\),\\bm\{W\}\-\\bm\{W\}^\{\\prime\}\\rangle\_\{F\}\(detailed in[Section˜D\.1](https://arxiv.org/html/2606.14929#A4.SS1)\)\. As we see in[Section˜5\.1](https://arxiv.org/html/2606.14929#S5.SS1), this Bregman projection – usually computationally expensive – is implementable in𝒪⁡\(dq2​M\)\\operatorname\{\\mathcal\{O\}\}\(d\_\{q\}^\{2\}M\)time thanks to the choice of hypentropy regularizerΦβ\\Phi\_\{\\beta\}and nuclear\-norm ball𝔹∗M​\(τ\)\\mathbb\{B\}\_\{\\ast\}^\{M\}\(\\tau\)\.

### 4\.2Gradient Estimation and Policy Regret Bound

The other component of HPG is the gradient estimator𝑮^t\\widehat\{\\bm\{G\}\}\_\{t\}\. In standard OMD with full information feedback, one directly uses the true gradient∇ℒ​\(𝑾t\)\\nabla\\mathcal\{L\}\(\\bm\{W\}\_\{t\}\)in place of𝑮^t\\widehat\{\\bm\{G\}\}\_\{t\}for the OMD update in[Equation˜14](https://arxiv.org/html/2606.14929#S4.E14)\. However, in our bandit feedback and partial observability setup, we cannot directly compute this gradient: In each round, we only observe one itemat,mta\_\{t,m\_\{t\}\}sampled from the selected modelξmt​\(qt\)\\xi\_\{m\_\{t\}\}\(q\_\{t\}\)and a noisy rewardrt=r​\(qt,at,mt\)\+ηtr\_\{t\}=r\(q\_\{t\},a\_\{t,m\_\{t\}\}\)\+\\eta\_\{t\}\. We must estimate∇ℒ​\(𝑾t\)\\nabla\\mathcal\{L\}\(\\bm\{W\}\_\{t\}\)only from this limited information\. We design a REINFORCE\-style gradient estimator: let𝑮^t=diag⁡\(G^t,1,G^t,2,…,G^t,M\)\\widehat\{\\bm\{G\}\}\_\{t\}=\\operatorname\{\\mathrm\{diag\}\}\(\\widehat\{G\}\_\{t,1\},\\widehat\{G\}\_\{t,2\},\\ldots,\\widehat\{G\}\_\{t,M\}\), where

G^t,m=−rt​\(𝟙​\[mt=m\]−π𝑾t​\(m∣qt\)\)​qt​qt𝖳,∀m=1,2,…,M\.\\widehat\{G\}\_\{t,m\}=\-r\_\{t\}\\bigl\(\\mathbbm\{1\}\[m\_\{t\}=m\]\-\\pi\_\{\\bm\{W\}\_\{t\}\}\(m\\mid q\_\{t\}\)\\bigr\)q\_\{t\}q\_\{t\}^\{\\mathsf\{T\}\},\\quad\\forall m=1,2,\\ldots,M\.\(15\)
[Lemma˜2](https://arxiv.org/html/2606.14929#Thmtheorem2)below indicates that the𝑮^t\\widehat\{\\bm\{G\}\}\_\{t\}is conditionally unbiased and admits constant second\-order moments\. While similar estimators and properties have been widely used in reinforcement learning and policy gradient methods\(see, e\.g\.,williams1992simple,sutton1999policy\), in our log\-quadratic policy classΠquad\\Pi\_\{\\text\{quad\}\}, we have yet another unique property: TheG^t,m\\widehat\{G\}\_\{t,m\}in[Equation˜15](https://arxiv.org/html/2606.14929#S4.E15)is*rank\-one*\. As we will see shortly in[Section˜5\.1](https://arxiv.org/html/2606.14929#S5.SS1), this is pivotal for the computational efficiency of our HPG algorithm\.

###### Lemma 2\(Gradient Estimation\)\.

Let𝔼t\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{t\}be the expectation taken only w\.r\.t\. the randomness in roundtt\. Then we have𝔼t\[𝐆^t∣qt\]=∇𝐖ℒt​\(𝐖t\)\\operatornamewithlimits\{\\mathbb\{E\}\}\\nolimits\_\{t\}\[\\widehat\{\\bm\{G\}\}\_\{t\}\\mid q\_\{t\}\]=\\nabla\_\{\\bm\{W\}\}\\mathcal\{L\}\_\{t\}\(\\bm\{W\}\_\{t\}\)\. Furthermore,∑m=1M∥G^t,m∥22≤2\\sum\\nolimits\_\{m=1\}^\{M\}\\lVert\\widehat\{G\}\_\{t,m\}\\rVert\_\{2\}^\{2\}\\leq 2almost surely\.

Combining this gradient estimator with OMD updates yields the full HPG algorithm \(see[Algorithm˜1](https://arxiv.org/html/2606.14929#alg1)\)\. We now state the regret guarantee of HPG, which shows that it adapts to the problem’s intrinsic low\-rank structure and avoids linear dependence on the high\-dimensional query space\.

###### Theorem 3\(Regret Bound\)\.

Assume that the optimal𝐖∗∈𝕎\\bm\{W\}^\{\\ast\}\\in\\mathbb\{W\}ensures∥Wm∗∥∗≤2​s\\lVert W\_\{m\}^\{\\ast\}\\rVert\_\{\\ast\}\\leq 2s,∀m\\forall m\. When settingτ=2​s\\tau=2s,β=2​s/dq\\beta=2s/d\_\{q\}andη=\(M​log⁡dq\)/T\\eta=\\sqrt\{\(M\\log d\_\{q\}\)/T\}, HPG givesℜ~T​\(Πquad\)=𝒪⁡\(s​M​T​log⁡dq\)\\widetilde\{\\mathfrak\{R\}\}\_\{T\}\(\\Pi\_\{\\text\{quad\}\}\)=\\operatorname\{\\mathcal\{O\}\}\(s\\sqrt\{MT\\log d\_\{q\}\}\)\.

[Theorem˜3](https://arxiv.org/html/2606.14929#Thmtheorem3)indicates that if the low\-rank parameterssis known to the learner, the HPG algorithm attains𝒪~⁡\(s​M​T\)\\operatorname\{\\widetilde\{\\operatorname\{\\mathcal\{O\}\}\}\}\(s\\sqrt\{MT\}\)linearized policy regret, thus provably adapts to the underlying low\-rank structures of embedding models\. In[Section˜5\.2](https://arxiv.org/html/2606.14929#S5.SS2), we further show that when the low\-rank parameterssis unknown, the HPG algorithm is still implementable in a*parameter\-free*way that attains an almost identical regret bound\. The full proofs of[Lemma˜2](https://arxiv.org/html/2606.14929#Thmtheorem2)and[Theorem˜3](https://arxiv.org/html/2606.14929#Thmtheorem3)are deferred to[Sections˜D\.3](https://arxiv.org/html/2606.14929#A4.SS3)and[D\.4](https://arxiv.org/html/2606.14929#A4.SS4)\.

## 5Practical Implementation of the HPG Algorithm

While attaining𝒪~⁡\(τ​M​T\)\\operatorname\{\\widetilde\{\\operatorname\{\\mathcal\{O\}\}\}\}\(\\tau\\sqrt\{MT\}\)regret, two issues present before implementing HPG for realistic model routing: the computational cost of the Bregman projection step in[Equation˜14](https://arxiv.org/html/2606.14929#S4.E14), and the knowledge ofssin[Theorem˜3](https://arxiv.org/html/2606.14929#Thmtheorem3)\. We resolve both issues in this section, thus demonstrating the practibility of HPG\.

### 5\.1Computationally Efficient Implementation

In each roundtt, the OMD framework performs a Bregman projection step, as we demonstrated in[Equation˜14](https://arxiv.org/html/2606.14929#S4.E14)\. Solving a convex optimization problem is in general computationally expensive: In our case, the underlying space𝕊M​dq\\mathbb\{S\}^\{Md\_\{q\}\}is of dimensionM2​dq2M^\{2\}d\_\{q\}^\{2\}, hence a generic interior point method takes𝒪⁡\(\(M2​dq2\)3\)=𝒪⁡\(M6​dq6\)\\operatorname\{\\mathcal\{O\}\}\(\(M^\{2\}d\_\{q\}^\{2\}\)^\{3\}\)=\\operatorname\{\\mathcal\{O\}\}\(M^\{6\}d\_\{q\}^\{6\}\)time per step\(boyd2004convex\)\. Withdq=768d\_\{q\}=768as inRouterRetriver\(lee2025routerretriever\), this means2×1017⋅M2\\times 10^\{17\}\\cdot Mfloating point operations per round\.

Fortunately, since the hypentropyΦβ\\Phi\_\{\\beta\}and nuclear\-norm ball𝔹∗M​\(τ\)\\mathbb\{B\}\_\{\\ast\}^\{M\}\(\\tau\)are both defined w\.r\.t\. eigenvalues, and diagonal block matrices preserve eigenvalues, we establish a*direct sum property*\([Lemma˜12](https://arxiv.org/html/2606.14929#Thmtheorem12)in[Section˜D\.2](https://arxiv.org/html/2606.14929#A4.SS2)\)\. This allows us to treat each model’s parameter separately\. Furthermore, we prove that eachmmonly requires𝒪⁡\(dq2\)\\operatorname\{\\mathcal\{O\}\}\(d\_\{q\}^\{2\}\)time per round by maintaining an eigen\-decomposition ofWt,mW\_\{t,m\}:

Wt,m=Ut,m​diag⁡\(λt,m\)​Ut,m𝖳,∀t∈\[T\],W\_\{t,m\}=U\_\{t,m\}\\operatorname\{\\mathrm\{diag\}\}\(\\lambda\_\{t,m\}\)U\_\{t,m\}^\{\\mathsf\{T\}\},\\quad\\forall t\\in\[T\],\(16\)whereUt,m∈ℝdq×dqU\_\{t,m\}\\in\\mathbb\{R\}^\{d\_\{q\}\\times d\_\{q\}\}andλt,m∈ℝdq\\lambda\_\{t,m\}\\in\\mathbb\{R\}^\{d\_\{q\}\}\. Indeed, utilizing the rank\-one property of𝑮^t\\widehat\{\\bm\{G\}\}\_\{t\}\(see[Equation˜15](https://arxiv.org/html/2606.14929#S4.E15)\), we decompose the Bregman projection onto𝔹∗​\(τ\)\\mathbb\{B\}\_\{\\ast\}\(\\tau\)in[Equation˜14](https://arxiv.org/html/2606.14929#S4.E14)into 4 computationally easy steps:

1. 1\.ConvertWt\\bm\{W\}\_\{t\}to Mirror Space\.LetYt,m=∇Φβ​\(Wt,m\)Y\_\{t,m\}=\\nabla\\Phi\_\{\\beta\}\(W\_\{t,m\}\), which, as detailed in[Section˜D\.1](https://arxiv.org/html/2606.14929#A4.SS1), is applyingarcsinhβ​\(⋅\)\\frac\{\\operatorname\{\\mathrm\{arcsinh\}\}\}\{\\beta\}\(\\cdot\)to all the eigenvalues\. HenceYt,mY\_\{t,m\}is derived in𝒪⁡\(dq\)\\operatorname\{\\mathcal\{O\}\}\(d\_\{q\}\)time from[Equation˜16](https://arxiv.org/html/2606.14929#S5.E16)\.
2. 2\.Gradient Descent Update\.In the mirror space, perform gradient descentY~t\+1,m=Yt,m−η​G^t,m\\widetilde\{Y\}\_\{t\+1,m\}=Y\_\{t,m\}\-\\eta\\widehat\{G\}\_\{t,m\}\. While eigen\-decomposingY~t\+1,m\\widetilde\{Y\}\_\{t\+1,m\}in general takes𝒪⁡\(dq3\)\\operatorname\{\\mathcal\{O\}\}\(d\_\{q\}^\{3\}\)time, ourG^t,m\\widehat\{G\}\_\{t,m\}is*rank\-one*\([Equation˜15](https://arxiv.org/html/2606.14929#S4.E15)\)\. Hence*eigen\-updating*fromYt,mY\_\{t,m\}toY~t\+1,m\\widetilde\{Y\}\_\{t\+1,m\}only takes𝒪⁡\(dq2\)\\operatorname\{\\mathcal\{O\}\}\(d\_\{q\}^\{2\}\)time\(see, e\.g\.,bunch1978rank\)\.
3. 3\.ConvertY~t\+1\\widetilde\{\\bm\{Y\}\}\_\{t\+1\}to Primal Space\.LetW~t\+1,m=\(∇Φβ\)−1​\(Y~t\+1,m\)\\widetilde\{W\}\_\{t\+1,m\}=\(\\nabla\\Phi\_\{\\beta\}\)^\{\-1\}\(\\widetilde\{Y\}\_\{t\+1,m\}\), which is the same as Step 1\.
4. 4\.Projection onto𝔹∗​\(τ\)\\mathbb\{B\}\_\{\\ast\}\(\\tau\)based onDΦβD\_\{\\Phi\}^\{\\beta\}\.This is another step that is \(usually\) computationally expensive\. But our𝔹∗​\(τ\)\\mathbb\{B\}\_\{\\ast\}\(\\tau\)andΦβ\\Phi\_\{\\beta\}both only depend on the*eigenvalues*\. Hence, equipped withW~t\+1,m\\widetilde\{W\}\_\{t\+1,m\}’s eigen\-decomposition, we can derive from von Neumann’s trace inequality that Wt\+1,m=Ut\+1,m​diag⁡\(λt\+1,m\)​Ut\+1,m𝖳,λt\+1,m=argmin∥λ∥1≤τ​∑i=1dqDϕβ​\(λi∥λ~t\+1,m,i\),W\_\{t\+1,m\}=U\_\{t\+1,m\}\\operatorname\{\\mathrm\{diag\}\}\(\\lambda\_\{t\+1,m\}\)U\_\{t\+1,m\}^\{\\mathsf\{T\}\},\\quad\\lambda\_\{t\+1,m\}=\\operatornamewithlimits\{\\mathrm\{argmin\}\}\_\{\\lVert\\lambda\\rVert\_\{1\}\\leq\\tau\}\\sum\_\{i=1\}^\{d\_\{q\}\}D\_\{\\phi\}^\{\\beta\}\(\\lambda\_\{i\}\\\|\\widetilde\{\\lambda\}\_\{t\+1,m,i\}\),\(17\)whereDϕβD\_\{\\phi\}^\{\\beta\}is the Bregman divergence ofϕβ​\(x\)=x​arcsinh⁡xβ−x2\+β2\\phi\_\{\\beta\}\(x\)=x\\operatorname\{\\mathrm\{arcsinh\}\}\\frac\{x\}\{\\beta\}\-\\sqrt\{x^\{2\}\+\\beta^\{2\}\}\. Thus the projection to𝔹∗​\(τ\)\\mathbb\{B\}\_\{\\ast\}\(\\tau\)reduces to adqd\_\{q\}\-dimensional convex optimization, which is solvable in𝒪⁡\(dq​log⁡dq\)\\operatorname\{\\mathcal\{O\}\}\(d\_\{q\}\\log d\_\{q\}\)time\.

In[Section˜E\.1](https://arxiv.org/html/2606.14929#A5.SS1), we prove[Equation˜14](https://arxiv.org/html/2606.14929#S4.E14)is equivalent to these 4 steps\. This gives the following theorem:

###### Theorem 4\(Computational Cost\)\.

HPG is implementable in𝒪⁡\(dq2​M\)\\operatorname\{\\mathcal\{O\}\}\(d\_\{q\}^\{2\}M\)time complexity per round\.

We remark that in practice, one can sharpen the𝒪⁡\(dq2\)\\operatorname\{\\mathcal\{O\}\}\(d\_\{q\}^\{2\}\)computational bound even more: In the proof of[Theorem˜4](https://arxiv.org/html/2606.14929#Thmtheorem4)\(detailed in[Section˜E\.1](https://arxiv.org/html/2606.14929#A5.SS1)\), we will see that the optimization problem in[Equation˜17](https://arxiv.org/html/2606.14929#S5.E17)of Step 4 induces a*low\-rank*structure\. Thus, if we only keep the top\-τ\\taueigenvalues ofWt\+1,mW\_\{t\+1,m\}\(i\.e\., eigen\-truncation\),λt\+1,m\\lambda\_\{t\+1,m\}becomesτ\\tau\-dimensional andUt\+1,mU\_\{t\+1,m\}becomesdq×τd\_\{q\}\\times\\tau; the eigen\-update in Step 2 thus takes𝒪⁡\(τ​dq\)\\operatorname\{\\mathcal\{O\}\}\(\\tau d\_\{q\}\)time\. One can further batch OMD updates by performing an aggregated gradient step in the mirror space for enhanced efficiency, though sacrifising the strict regret guarantee\.

### 5\.2Parameter\-Free Implementation

Yet another issue is the hyper\-parameterτ\\tauin[Algorithm˜1](https://arxiv.org/html/2606.14929#alg1), which controls the nuclear\-norm truncation\.[Theorem˜3](https://arxiv.org/html/2606.14929#Thmtheorem3)setsτ=2​s\\tau=2swheressis the*unknown*rank of the model kernelsΨm\\Psi\_\{m\}\(recall[Section˜2\.2](https://arxiv.org/html/2606.14929#S2.SS2)\)\. Fortunately, utilizing the parameter\-free online learning technique\(cutkosky2018black\), HPG algorithm can be implemented without*any*prior information while enjoying a similar regret guarantee\. This gives[Theorem˜5](https://arxiv.org/html/2606.14929#Thmtheorem5)\. The detailed algorithm description and proof is in[Section˜E\.2](https://arxiv.org/html/2606.14929#A5.SS2)\.

###### Theorem 5\(Parameter\-Free HPG\)\.

Assume that the optimal𝐖∗∈𝕎\\bm\{W\}^\{\\ast\}\\in\\mathbb\{W\}ensures∥Wm∗∥∗≤2​s\\lVert W\_\{m\}^\{\\ast\}\\rVert\_\{\\ast\}\\leq 2s,∀m\\forall m, but the low\-rank parameterssis unknown\. Then the parameter\-free HPG algorithm \([Algorithm˜2](https://arxiv.org/html/2606.14929#alg2)in[Section˜E\.2](https://arxiv.org/html/2606.14929#A5.SS2)\) ensures a linearized policy regret bound ofℜ~T​\(Πquad\)=𝒪⁡\(s​M​T​log⁡\(dq​T\)\)\\widetilde\{\\mathfrak\{R\}\}\_\{T\}\(\\Pi\_\{\\text\{quad\}\}\)=\\operatorname\{\\mathcal\{O\}\}\(sM\\sqrt\{T\}\\log\(d\_\{q\}T\)\)\.

Compared to theℜ~T​\(Πquad\)=𝒪⁡\(s​M​T​log⁡dq\)\\widetilde\{\\mathfrak\{R\}\}\_\{T\}\(\\Pi\_\{\\text\{quad\}\}\)=\\operatorname\{\\mathcal\{O\}\}\(s\\sqrt\{MT\\log d\_\{q\}\}\)bound in[Theorem˜3](https://arxiv.org/html/2606.14929#Thmtheorem3), this bound is slightly inferior by aM\\sqrt\{M\}factor and a few poly\-logarithmic dependencies\. However, the most favorable properties of HPG algorithm – automatically adapting to the unknown low\-rank structure of embedding models, avoidingpoly​\(dq\)\\text\{poly\}\(d\_\{q\}\)dependencies, and admitting efficient implementations – remain true in[Theorem˜5](https://arxiv.org/html/2606.14929#Thmtheorem5)\.

## References

\\appendixpage

## Appendix ASetup of[Figure˜1](https://arxiv.org/html/2606.14929#S1.F1)and More Discussions

In[Figure˜1](https://arxiv.org/html/2606.14929#S1.F1), we consider a recommendation system scenario over the Amazon Berkeley Objects \(ABO\) dataset\(collins2022abo\)\. Based on the “keywords” in the ABO dataset, we randomly picked 500 items with one of the following keywords:*‘sofa’, ‘couch’, ‘chair’, ‘loveseat’, ‘ottoman\.’*We consider the following specific user prompt, which is generated by a Large Language Model \(LLM\) API, Gemini\-2\.5\-pro, to mimic a typical customer that has a diverse range of requirements: “*Looking for a modern, dark\-colored lounge sofa \(not a chair\)\. Definitely NOT leather\. Prefer fabric or linen with a cozy but structural design\.*” It contains various components: vague style descriptions \(modern, cozy but structural\), color \(dark\-colored\), object category \(lounge sofa, not a chair\), and material constraints \(NOT leather, prefer fabric or linen\)\.

In industrial recommendation systems like Youtube\(covington2016deep\), Alibaba e\-commerce\(wang2018billion\), and Facebook\(huang2020embedding\), a filter step taking care of hard constraints is implemented independent of the embedding models\. We capture this by invoking Gemini\-2\.5\-pro with the following prompt: “*You are a strict data filter for a recommendation system\. A user has provided the following search query:\{user\_prompt\}Task: 1\. Identify any STRICT negative constraints or hard requirements in the user’s query \(e\.g\., if they explicitly say "NOT X", then X is a hard constraint\)\. 2\. Evaluate the following items\. If an item clearly violates a strict negative constraint from the query, it fails the filter\. 3\. Return ONLY a valid JSON dictionary where keys are Item IDs and values are boolean ‘true‘ \(passes constraints, or no strict constraints violated\) or ‘false‘ \(fails strict constraints\)\.*” The items satisfying all hard constraints in the user prompt stated above – 131 out of 500 – are passed onto the next stage of recommendation\.

For the recommendation stage, we use two lightweight embedding models pre\-trained using different methodologies:\(i\)theminiLMmodel bywang2020minilm,wang2021minilmv2, whose embeddings are optimized so that semantically similar sentences have high cosine similarity; and\(ii\)themsmarcomodel byreimers2019sentence, an asymmetric retrieval model trained on a large\-scale dataset built from Bing search queries\(bajaj2016ms\)\. Prior benchmarks show that text embedding models are strongly task\-dependent: models optimized for semantic similarity and models optimized for query\-document retrieval perform differently across downstream retrieval and similarity tasks\(thakur2021beir,muennighoff2023mteb\)\. Thus, using one symmetric semantic model and one asymmetric retrieval model is expected to produce different rankings over the same candidate items\.

To evaluate these two models, we again called the LLM API, Gemini\-2\.5\-pro, with the following prompt: “*You are a recommendation system evaluator\. A user queried:\{user\_prompt\}Note: All items below have already passed the hard filter constraints of the query\. Evaluate how perfectly each item satisfies the remaining soft constraints \(modern, dark\-colored, cozy but structural, fabric/linen\)\. Task: Score each item from 0 to 100\. Return ONLY a valid JSON dictionary where keys are Item IDs and values are integer scores\.*” The resulting ranking is treated as the ground\-truth\.

In[Figure˜1](https://arxiv.org/html/2606.14929#S1.F1), we visualize the rankings using a 2D scatter plot, with the x\-axis and y\-axis representing the ranks assigned byminiLMandmsmarco, respectively\. To show the discrepancy between different models without visual clutter, low\-relevance items \(ground\-truth rank\>40\>40, which is roughly 25%\) are plotted as faint crosses, while high\-quality items \(ground\-truth rank≤40\\leq 40\) are shown as gray dots\. Furthermore, we also highlight representative “exclusively good” items identified as follows: An item ranked in the top tier by both the LLM ground\-truth and one embedding model, while simultaneously being penalized by the other embedding model\. Green dots are items uniquely captured byminiLM, and red dots are items uniquely captured bymsmarco\. This gives our main motivation: No single model dominates the other, and hence dynamic model routing is necessary\.

## Appendix BMore Discussions on Policy Classes and Regret Notions

### B\.1Log\-Quadratic Policy Class \([Proposition˜1](https://arxiv.org/html/2606.14929#Thmtheorem1)\)

###### Proof of[Proposition˜1](https://arxiv.org/html/2606.14929#Thmtheorem1)\.

We begin by defining the ideal \(non\-misspecified\) recommendation distribution for expertmm, which removes the misspecification functionμm\\mu\_\{m\}in[Equation˜4](https://arxiv.org/html/2606.14929#S2.E4):

ξm∗​\(a∣q\)=exp⁡\(⟨Ψm,a​q𝖳⟩\)∑a′∈𝒜exp⁡\(⟨Ψm,a′​q𝖳⟩\),∀m∈\[M\],q∈𝒬,a∈𝒜\.\\xi\_\{m\}^\{\\ast\}\(a\\mid q\)=\\frac\{\\exp\\bigl\(\\langle\\Psi\_\{m\},aq^\{\\mathsf\{T\}\}\\rangle\\bigr\)\}\{\\sum\_\{a^\{\\prime\}\\in\\mathcal\{A\}\}\\exp\\bigl\(\\langle\\Psi\_\{m\},a^\{\\prime\}q^\{\\mathsf\{T\}\}\\rangle\\bigr\)\},\\quad\\forall m\\in\[M\],q\\in\\mathcal\{Q\},a\\in\\mathcal\{A\}\.Given the bounded misspecification∥μm∥∞≤ϵ\\lVert\\mu\_\{m\}\\rVert\_\{\\infty\}\\leq\\epsilonin[Equation˜4](https://arxiv.org/html/2606.14929#S2.E4), the ratio between the actual distribution and the ideal distribution is strictly bounded\. Specifically, for anya∈𝒜a\\in\\mathcal\{A\}:

ξm​\(a∣q\)ξm∗​\(a∣q\)\\displaystyle\\frac\{\\xi\_\{m\}\(a\\mid q\)\}\{\\xi\_\{m\}^\{\\ast\}\(a\\mid q\)\}=exp⁡\(μm​\(q,a\)\)​∑a′∈𝒜exp⁡\(⟨Ψm,a′​q𝖳⟩\)∑a′∈𝒜exp⁡\(⟨Ψm,a′​q𝖳⟩\+μm​\(q,a′\)\)\\displaystyle=\\exp\\bigl\(\\mu\_\{m\}\(q,a\)\\bigr\)\\frac\{\\sum\_\{a^\{\\prime\}\\in\\mathcal\{A\}\}\\exp\\bigl\(\\langle\\Psi\_\{m\},a^\{\\prime\}q^\{\\mathsf\{T\}\}\\rangle\\bigr\)\}\{\\sum\_\{a^\{\\prime\}\\in\\mathcal\{A\}\}\\exp\\bigl\(\\langle\\Psi\_\{m\},a^\{\\prime\}q^\{\\mathsf\{T\}\}\\rangle\+\\mu\_\{m\}\(q,a^\{\\prime\}\)\\bigr\)\}≤exp⁡\(ϵ\)​∑a′∈𝒜exp⁡\(⟨Ψm,a′​q𝖳⟩\)exp⁡\(−ϵ\)​∑a′∈𝒜exp⁡\(⟨Ψm,a′​q𝖳⟩\)=exp⁡\(2​ϵ\)\.\\displaystyle\\leq\\exp\(\\epsilon\)\\frac\{\\sum\_\{a^\{\\prime\}\\in\\mathcal\{A\}\}\\exp\\bigl\(\\langle\\Psi\_\{m\},a^\{\\prime\}q^\{\\mathsf\{T\}\}\\rangle\\bigr\)\}\{\\exp\(\-\\epsilon\)\\sum\_\{a^\{\\prime\}\\in\\mathcal\{A\}\}\\exp\\bigl\(\\langle\\Psi\_\{m\},a^\{\\prime\}q^\{\\mathsf\{T\}\}\\rangle\\bigr\)\}=\\exp\(2\\epsilon\)\.By symmetry, the lower bound isexp⁡\(−2​ϵ\)\\exp\(\-2\\epsilon\)\. Consequently, the total variation distance is bounded by

DTV​\(ξm,ξm∗\)≤12​∑aξm∗​\(a∣q\)​\|exp⁡\(2​ϵ\)−1\|=𝒪⁡\(ϵ\)\.D\_\{\\text\{TV\}\}\(\\xi\_\{m\},\\xi\_\{m\}^\{\\ast\}\)\\leq\\frac\{1\}\{2\}\\sum\_\{a\}\\xi\_\{m\}^\{\\ast\}\(a\\mid q\)\\lvert\\exp\(2\\epsilon\)\-1\\rvert=\\operatorname\{\\mathcal\{O\}\}\(\\epsilon\)\.
We therefore compare the expected action of modelmmwhen answering queryqq, namelya¯m​\(q\):=𝔼a∼ξm\[a\]\\overline\{a\}\_\{m\}\(q\):=\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{a\\sim\\xi\_\{m\}\}\[a\], to that under the idealξm∗\\xi\_\{m\}^\{\\ast\}, namelya¯m∗​\(q\):=𝔼a∼ξm∗\[a\]\\overline\{a\}\_\{m\}^\{\\ast\}\(q\):=\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{a\\sim\\xi\_\{m\}^\{\\ast\}\}\[a\]\. We have

∥a¯m\(q\)−a¯m∗\(q\)∥2=∥∑a∈𝒜a\(ξm\(a∣q\)−ξm∗\(a∣q\)\)∥2≤maxa∈𝒜∥a∥2⋅∑a∈𝒜\|ξm−ξm∗\|≤𝒪\(ϵ\),\\lVert\\overline\{a\}\_\{m\}\(q\)\-\\overline\{a\}\_\{m\}^\{\\ast\}\(q\)\\rVert\_\{2\}=\\Bigl\\lVert\\sum\_\{a\\in\\mathcal\{A\}\}a\\bigl\(\\xi\_\{m\}\(a\\mid q\)\-\\xi\_\{m\}^\{\\ast\}\(a\\mid q\)\\bigr\)\\Bigr\\rVert\_\{2\}\\leq\\max\_\{a\\in\\mathcal\{A\}\}\\lVert a\\rVert\_\{2\}\\cdot\\sum\_\{a\\in\\mathcal\{A\}\}\\lvert\\xi\_\{m\}\-\\xi\_\{m\}^\{\\ast\}\\rvert\\leq\\operatorname\{\\mathcal\{O\}\}\(\\epsilon\),where we invoked the regularity assumption that∥a∥2≤1\\lVert a\\rVert\_\{2\}\\leq 1\([Section˜2\.2](https://arxiv.org/html/2606.14929#S2.SS2)\)\. Asξm∗\\xi\_\{m\}^\{\\ast\}belongs to the exponential family, the expected action is the gradient of the log\-partition function atΨm​q\\Psi\_\{m\}q, i\.e\.,

a¯m∗​\(q\)=𝔼a∼ξm∗\[a\]=∇A​\(Ψm​q\),where​A​\(z\):=log​∑a∈𝒜exp⁡\(⟨z,a⟩\)\.\\overline\{a\}\_\{m\}^\{\\ast\}\(q\)=\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{a\\sim\\xi\_\{m\}^\{\\ast\}\}\[a\]=\\nabla A\(\\Psi\_\{m\}q\),\\quad\\text\{where \}A\(z\):=\\log\\sum\_\{a\\in\\mathcal\{A\}\}\\exp\(\\langle z,a\\rangle\)\.
Expand∇A​\(z\)\\nabla A\(z\)aroundz=0z=0to the second order as∇A​\(z\)=∇A​\(0\)\+∇2A​\(0\)​z\+R2​\(z\)\\nabla A\(z\)=\\nabla A\(0\)\+\\nabla^\{2\}A\(0\)z\+R\_\{2\}\(z\)where∥R2​\(z\)∥2≤𝒪⁡\(∥z∥22\)\\lVert R\_\{2\}\(z\)\\rVert\_\{2\}\\leq\\operatorname\{\\mathcal\{O\}\}\(\\lVert z\\rVert\_\{2\}^\{2\}\)\. Due to the log\-partition function,∇A​\(0\)=1\|𝒜\|​∑a∈𝒜a:=μ𝒜\\nabla A\(0\)=\\frac\{1\}\{\\lvert\\mathcal\{A\}\\rvert\}\\sum\_\{a\\in\\mathcal\{A\}\}a:=\\mu\_\{\\mathcal\{A\}\}is the mean of all items, and∇2A​\(0\)=1\|𝒜\|​∑a∈𝒜\(a−μ𝒜\)​\(a−μ𝒜\)𝖳:=Σ𝒜\\nabla^\{2\}A\(0\)=\\frac\{1\}\{\\lvert\\mathcal\{A\}\\rvert\}\\sum\_\{a\\in\\mathcal\{A\}\}\(a\-\\mu\_\{\\mathcal\{A\}\}\)\(a\-\\mu\_\{\\mathcal\{A\}\}\)^\{\\mathsf\{T\}\}:=\\Sigma\_\{\\mathcal\{A\}\}is the covariance\.

Now plug inz=Ψm​qz=\\Psi\_\{m\}q\. By the regularity conditions that∥q∥2≤1\\lVert q\\rVert\_\{2\}\\leq 1and∥Ψm∥2≤ϵ\\lVert\\Psi\_\{m\}\\rVert\_\{2\}\\leq\\sqrt\{\\epsilon\}, we have∥z∥2≤ϵ\\lVert z\\rVert\_\{2\}\\leq\\sqrt\{\\epsilon\}\. Thus the remainder is bounded by∥R2​\(z\)∥2≤𝒪⁡\(ϵ\)\\lVert R\_\{2\}\(z\)\\rVert\_\{2\}\\leq\\operatorname\{\\mathcal\{O\}\}\(\\epsilon\)\. Combining it with the total variational bound betweena¯m​\(q\)\\overline\{a\}\_\{m\}\(q\)anda¯m∗​\(q\)\\overline\{a\}\_\{m\}^\{\\ast\}\(q\), we have

a¯m∗​\(q\)=μ𝒜\+Σ𝒜​Ψm​q\+e~m​\(q\),a¯m​\(q\)=μ𝒜\+Σ𝒜​Ψm​q\+em​\(q\),\\overline\{a\}\_\{m\}^\{\\ast\}\(q\)=\\mu\_\{\\mathcal\{A\}\}\+\\Sigma\_\{\\mathcal\{A\}\}\\Psi\_\{m\}q\+\\widetilde\{e\}\_\{m\}\(q\),\\quad\\overline\{a\}\_\{m\}\(q\)=\\mu\_\{\\mathcal\{A\}\}\+\\Sigma\_\{\\mathcal\{A\}\}\\Psi\_\{m\}q\+e\_\{m\}\(q\),where∥e~m​\(q\)∥2,∥em​\(q\)∥2≤𝒪⁡\(ϵ\)\\lVert\\widetilde\{e\}\_\{m\}\(q\)\\rVert\_\{2\},\\lVert e\_\{m\}\(q\)\\rVert\_\{2\}\\leq\\operatorname\{\\mathcal\{O\}\}\(\\epsilon\)\. Substitutinga¯m​\(q\)\\overline\{a\}\_\{m\}\(q\)into the true reward function in[Equation˜2](https://arxiv.org/html/2606.14929#S2.E2),

𝔼a∼ξm​\(q\)\[r​\(q,a\)\]\\displaystyle\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{a\\sim\\xi\_\{m\}\(q\)\}\[r\(q,a\)\]=𝔼a∼ξm​\(q\)\[q𝖳​\(Ψ∗\)𝖳​a\+ν​\(q,a\)\]=q𝖳​\(Ψ∗\)𝖳​a¯m​\(q\)\+𝔼a∼ξm\[ν​\(q,a\)\]\\displaystyle=\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{a\\sim\\xi\_\{m\}\(q\)\}\\bigl\[q^\{\\mathsf\{T\}\}\(\\Psi^\{\\ast\}\)^\{\\mathsf\{T\}\}a\+\\nu\(q,a\)\\bigr\]=q^\{\\mathsf\{T\}\}\(\\Psi^\{\\ast\}\)^\{\\mathsf\{T\}\}\\overline\{a\}\_\{m\}\(q\)\+\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{a\\sim\\xi\_\{m\}\}\[\\nu\(q,a\)\]=q𝖳​\(Ψ∗\)𝖳​μ𝒜⏟constantC​\(q\)\+q𝖳​\(Ψ∗\)𝖳​Σ𝒜​Ψm​q⏟quadraticq𝖳​Wm​q\+q𝖳​\(Ψ∗\)𝖳​em​\(q\)\+𝔼a∼ξm\[ν​\(q,a\)\]⏟residualδm​\(q\)\.\\displaystyle=\\underbrace\{q^\{\\mathsf\{T\}\}\(\\Psi^\{\\ast\}\)^\{\\mathsf\{T\}\}\\mu\_\{\\mathcal\{A\}\}\}\_\{\\text\{constant $C\(q\)$\}\}\+\\underbrace\{q^\{\\mathsf\{T\}\}\(\\Psi^\{\\ast\}\)^\{\\mathsf\{T\}\}\\Sigma\_\{\\mathcal\{A\}\}\\Psi\_\{m\}q\}\_\{\\text\{quadratic $q^\{\\mathsf\{T\}\}W\_\{m\}q$\}\}\+\\underbrace\{q^\{\\mathsf\{T\}\}\(\\Psi^\{\\ast\}\)^\{\\mathsf\{T\}\}e\_\{m\}\(q\)\+\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{a\\sim\\xi\_\{m\}\}\[\\nu\(q,a\)\]\}\_\{\\text\{residual $\\delta\_\{m\}\(q\)$\}\}\.
We first focus on the quadratic termq𝖳​Wm​qq^\{\\mathsf\{T\}\}W\_\{m\}qwhereWm:=\(Ψ∗\)𝖳​Σ𝒜​ΨmW\_\{m\}:=\(\\Psi^\{\\ast\}\)^\{\\mathsf\{T\}\}\\Sigma\_\{\\mathcal\{A\}\}\\Psi\_\{m\}\. Since the quadratic form only depends on the symmetric part, we defineWm∗=12​\(Wm\+Wm𝖳\)∈𝕊dqW\_\{m\}^\{\\ast\}=\\frac\{1\}\{2\}\(W\_\{m\}\+W\_\{m\}^\{\\mathsf\{T\}\}\)\\in\\mathbb\{S\}^\{d\_\{q\}\}\. It is also low\-rank:

rank\(Wm∗\)=rank\(12​Wm\+12​Wm𝖳\)≤rank\(Wm\)\+rank\(Wm𝖳\)≤2​rank\(Ψm\)≤2​sm≤2​s\.\\operatornamewithlimits\{\\mathrm\{rank\}\}\(W\_\{m\}^\{\\ast\}\)=\\operatornamewithlimits\{\\mathrm\{rank\}\}\\left\(\\frac\{1\}\{2\}W\_\{m\}\+\\frac\{1\}\{2\}W\_\{m\}^\{\\mathsf\{T\}\}\\right\)\\leq\\operatornamewithlimits\{\\mathrm\{rank\}\}\(W\_\{m\}\)\+\\operatornamewithlimits\{\\mathrm\{rank\}\}\(W\_\{m\}^\{\\mathsf\{T\}\}\)\\leq 2\\operatornamewithlimits\{\\mathrm\{rank\}\}\(\\Psi\_\{m\}\)\\leq 2s\_\{m\}\\leq 2s\.
Consequently, we have the following nuclear\-norm bound:

∥Wm∗∥∗≤rank\(Wm∗\)×∥Wm∗∥2≤2​s×12​\(∥Wm∥2\+∥Wm𝖳∥2\)≤2​s×1×1×ϵ=2​s,\\lVert W\_\{m\}^\{\\ast\}\\rVert\_\{\\ast\}\\leq\\operatornamewithlimits\{\\mathrm\{rank\}\}\(W\_\{m\}^\{\\ast\}\)\\times\\lVert W\_\{m\}^\{\\ast\}\\rVert\_\{2\}\\leq 2s\\times\\frac\{1\}\{2\}\\left\(\\lVert W\_\{m\}\\rVert\_\{2\}\+\\lVert W\_\{m\}^\{\\mathsf\{T\}\}\\rVert\_\{2\}\\right\)\\leq 2s\\times 1\\times 1\\times\\sqrt\{\\epsilon\}=2s,where the last step uses the regularity conditions that∥Φ∗∥2≤1\\lVert\\Phi^\{\\ast\}\\rVert\_\{2\}\\leq 1,∥a∥2≤1\\lVert a\\rVert\_\{2\}\\leq 1for alla∈𝒜a\\in\\mathcal\{A\}, and∥Ψm∥2≤ϵ≤1\\lVert\\Psi\_\{m\}\\rVert\_\{2\}\\leq\\sqrt\{\\epsilon\}\\leq 1\. For the residual termδm​\(q\)\\delta\_\{m\}\(q\), because∥q∥2≤1\\lVert q\\rVert\_\{2\}\\leq 1,∥Ψ∗∥2≤1\\lVert\\Psi^\{\\ast\}\\rVert\_\{2\}\\leq 1, and\|ν\|≤ϵ\\lvert\\nu\\rvert\\leq\\epsilon,

\|δm​\(q\)\|≤∥q∥2⋅∥Ψ∗∥2⋅∥em​\(q\)∥2\+supa∈𝒜ν​\(q,a\)≤1⋅1⋅𝒪⁡\(ϵ\)\+ϵ=𝒪⁡\(ϵ\)\.\\lvert\\delta\_\{m\}\(q\)\\rvert\\leq\\lVert q\\rVert\_\{2\}\\cdot\\lVert\\Psi^\{\\ast\}\\rVert\_\{2\}\\cdot\\lVert e\_\{m\}\(q\)\\rVert\_\{2\}\+\\sup\_\{a\\in\\mathcal\{A\}\}\\nu\(q,a\)\\leq 1\\cdot 1\\cdot\\operatorname\{\\mathcal\{O\}\}\(\\epsilon\)\+\\epsilon=\\operatorname\{\\mathcal\{O\}\}\(\\epsilon\)\.
This finishes the proof: We have𝔼a∼ξm​\(q,a\)=C​\(q\)\+q𝖳​Wm∗​q\+δm​\(q\)\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{a\\sim\\xi\_\{m\}\(q,a\)\}=C\(q\)\+q^\{\\mathsf\{T\}\}W\_\{m\}^\{\\ast\}q\+\\delta\_\{m\}\(q\), such thatWm∗∈𝕊dqW\_\{m\}^\{\\ast\}\\in\\mathbb\{S\}^\{d\_\{q\}\}∥Wm∗∥∗≤rank\(Wm∗\)≤2​s\\lVert W\_\{m\}^\{\\ast\}\\rVert\_\{\\ast\}\\leq\\operatornamewithlimits\{\\mathrm\{rank\}\}\(W\_\{m\}^\{\\ast\}\)\\leq 2s, and that\|δm​\(q\)\|≤𝒪⁡\(ϵ\)\\lvert\\delta\_\{m\}\(q\)\\rvert\\leq\\operatorname\{\\mathcal\{O\}\}\(\\epsilon\)\. ∎

### B\.2Constant Policy Class and Expert Regret

When picking the reference policy class as the constant class, the policy regret recovers the expert regret in the problem of bandits with expert advice \(BwE\)\. We begin by defining the BwE problem\.

###### Definition 1\(Bandits with Expert Advice;auer2002nonstochastic\)\.

Consider aTT\-roundKK\-armed bandit between a learner and an environment\. In each roundt∈\[T\]t\\in\[T\], the learner observesMMexperts adviceξt,1,ξt,2,…,ξt,M\\xi\_\{t,1\},\\xi\_\{t,2\},\\ldots,\\xi\_\{t,M\}, which are probability distributions over\[K\]\[K\]\. The learner chooses one expertmtm\_\{t\}and plays according to their advice, i\.e\.,at∼ξt,mta\_\{t\}\\sim\\xi\_\{t,m\_\{t\}\}\. The learner suffers an adversarial lossℓt,at\\ell\_\{t,a\_\{t\}\}\. The learner minimizes*expert regret*, the sub\-optimality gap compared to the optimal expert in hindsight:

ℜTE:=maxm∗∈\[M\]​𝔼\[∑t=1T\(ℓt,at−𝔼a∼ξt,m∗\[ℓt,a\]\)\]\.\\mathfrak\{R\}\_\{T\}^\{E\}:=\\max\_\{m^\{\\ast\}\\in\[M\]\}\\operatornamewithlimits\{\\mathbb\{E\}\}\\left\[\\sum\_\{t=1\}^\{T\}\\left\(\\ell\_\{t,a\_\{t\}\}\-\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{a\\sim\\xi\_\{t,m^\{\\ast\}\}\}\[\\ell\_\{t,a\}\]\\right\)\\right\]\.\(18\)
In the more restrictive*limited observability*setup\(seldin2013open,kale2014multiarmed\), there is a parameterN≤MN\\leq M\. The learner can only pick a size\-NNsubset of experts in each round to observe their advices\. Everything else, including the performance metric of expert regret in[Equation˜18](https://arxiv.org/html/2606.14929#A2.E18), remains the same\.

In our embedding model routing problem \([Section˜2](https://arxiv.org/html/2606.14929#S2)\), if pickingΠ\\Pias the class of constant policies:

Πconst:=\{π​\(m∣q\)=𝟙​\[m=m0\],∀q∈𝒬\|m0∈\[M\]\},\\Pi\_\{\\text\{const\}\}:=\\bigl\\\{\\pi\(m\\mid q\)=\\mathbbm\{1\}\[m=m\_\{0\}\],\\forall q\\in\\mathcal\{Q\}\\mathrel\{\\big\|\}m\_\{0\}\\in\[M\]\\bigr\\\},\(19\)which is parameterized by a single parameterm0∈\[M\]m\_\{0\}\\in\[M\], our problem is almost[Definition˜1](https://arxiv.org/html/2606.14929#Thmdefinition1)withN=1N=1: LetK=\|𝒜\|K=\\lvert\\mathcal\{A\}\\rvert, i\.e\., each itema∈𝒜a\\in\\mathcal\{A\}is an arm\. View each model as an expert, with the round\-ttadviceξt,m\\xi\_\{t,m\}defined according to theξm\(⋅∣qt\)\\xi\_\{m\}\(\\cdot\\mid q\_\{t\}\)in[Equation˜4](https://arxiv.org/html/2606.14929#S2.E4)\. The loss of armaain roundttis the−r​\(qt,a\)\-r\(q\_\{t\},a\)in[Equation˜2](https://arxiv.org/html/2606.14929#S2.E2)\. The reason why we say “almost” is the correlation between expert advice and losses: In standard bandits with expert model\(see, e\.g\.,kale2014multiarmed, Footnote 2\), the advices and losses must be independent conditional on the history \(i\.e\., they can both be adaptive to the history, but cannot be correlated to each other\)\. Fortunately, our claims in[Section˜3](https://arxiv.org/html/2606.14929#S3.SS0.SSS0.Px4)still holds\.

On the upper bound side, we ignore the “experts” structure and apply an EXP3 algorithm\(auer2002nonstochastic\): In roundtt, the learner chooses one betweenMMmodels, namelymtm\_\{t\}, and the loss of modelmmin roundtthas a mean𝔼a∼ξm​\(qt\)\[r​\(qt,a\)\]\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{a\\sim\\xi\_\{m\}\(q\_\{t\}\)\}\[r\(q\_\{t\},a\)\], which is bounded by\[−1,1\]\[\-1,1\]\. Since EXP3 allows adaptive losses, its policy regret w\.r\.t\.Πconst\\Pi\_\{\\text\{const\}\}is𝒪⁡\(M​T​log⁡M\)\\operatorname\{\\mathcal\{O\}\}\(\\sqrt\{MT\\log M\}\)\(auer2002nonstochastic, Corollary 3\.2\)\.

On the lower bound side, we translate the construction ofkale2014multiarmedinto our setting:

###### Theorem 6\(Regret Lower Bound w\.r\.t\.Πconst\\Pi\_\{\\text\{const\}\}\)\.

There exists a group of instances withda≫Md\_\{a\}\\gg M,dq=M​dad\_\{q\}=Md\_\{a\}, ands=das=d\_\{a\}, such that the policy regret w\.r\.t\.Πconst\\Pi\_\{\\text\{const\}\}must beΩ​\(M​T/log⁡da\)\\Omega\(\\sqrt\{MT/\\log d\_\{a\}\}\)\. Moreover, even if we allow the learner to query multipleN≤MN\\leq Mmodels per round, the same bound remains\.

The proof of[Theorem˜6](https://arxiv.org/html/2606.14929#Thmtheorem6)is presented at the end of this section\. We hence conclude that the constant policy class and the induced expert regret are inappropriate for embedding model routing: A black\-box EXP3 ignoring the linear reward structures in[Equation˜2](https://arxiv.org/html/2606.14929#S2.E2)and the low\-rank model structures in[Equation˜4](https://arxiv.org/html/2606.14929#S2.E4)attains near\-optimal regret\. This lower bound holds even with full observability on models \(as long asM≤daM\\leq d\_\{a\}, which is typically true sinceda=768d\_\{a\}=768inRouterRetriver;lee2025routerretriever\)\.

We give two more remarks before concluding this section\. First, one may ask with full observability, whether the Hedge algorithm\(freund1997decision\)– attaining𝒪⁡\(T​log⁡M\)\\operatorname\{\\mathcal\{O\}\}\(\\sqrt\{T\\log M\}\)regret – becomes applicable\. The answer is no: while full observability on models are obtained, the reward feedback is still bandit \(see[Section˜2\.3](https://arxiv.org/html/2606.14929#S2.SS3)\)\. Second, noticing that thessin[Theorem˜6](https://arxiv.org/html/2606.14929#Thmtheorem6)is chosen to be the same asdad\_\{a\}, one may ask whether the low\-rank bilinear or matrix bandit algorithms\(jun2019bilinear,jang2021improved,lu2021low,kang2022efficient\)can be used to derive sharpened regret bounds and bypass theΩ​\(M​T/log⁡da\)\\Omega\(\\sqrt\{MT/\\log d\_\{a\}\}\)lower bound\. The answer is again no: the reward kernelΨ∗\\Psi^\{\\ast\}in[Equation˜2](https://arxiv.org/html/2606.14929#S2.E2)can be general \(i\.e\., having a rank as large asdd\), and the learner has no control over the queryqtq\_\{t\}\.

#### B\.2\.1Lower Bound on Policy Regret w\.r\.t\. Constant Policy Class

###### Proof of[Theorem˜6](https://arxiv.org/html/2606.14929#Thmtheorem6)\.

Writedq=M​Kd\_\{q\}=MKandda=Kd\_\{a\}=K\. Let𝒜=\{e1,e2,…,eK\}∈ℝK\\mathcal\{A\}=\\\{e\_\{1\},e\_\{2\},\\ldots,e\_\{K\}\\\}\\in\\mathbb\{R\}^\{K\}be unit vectors in the item space\. For each roundt∈\[T\]t\\in\[T\], the adversary sampleskt,1,kt,2,…,kk,Mk\_\{t,1\},k\_\{t,2\},\\ldots,k\_\{k,M\}uniformly random at from\[M\]\[M\]\. The query is given asqt=1M​\[ekt,1𝖳,ekt,2𝖳,…,ekt,M𝖳\]𝖳∈ℝM​Kq\_\{t\}=\\frac\{1\}\{\\sqrt\{M\}\}\[e\_\{k\_\{t,1\}\}^\{\\mathsf\{T\}\},e\_\{k\_\{t,2\}\}^\{\\mathsf\{T\}\},\\ldots,e\_\{k\_\{t,M\}\}^\{\\mathsf\{T\}\}\]^\{\\mathsf\{T\}\}\\in\\mathbb\{R\}^\{MK\}\. Each expertm∈\[M\]m\\in\[M\]has the following kernel \(MMmatrices in total, and𝑰K×K\\bm\{I\}\_\{K\\times K\}appears as themm\-th\):

Ψm=α​M​\[𝟎K×K⋯𝟎K×K𝑰K×K𝟎K×K⋯𝟎K×K\]∈ℝK×M​K,\\Psi\_\{m\}=\\alpha\\sqrt\{M\}\[\\bm\{0\}\_\{K\\times K\}\\quad\\cdots\\quad\\bm\{0\}\_\{K\\times K\}\\quad\\bm\{I\}\_\{K\\times K\}\\quad\\bm\{0\}\_\{K\\times K\}\\quad\\cdots\\quad\\bm\{0\}\_\{K\\times K\}\]\\in\\mathbb\{R\}^\{K\\times MK\},whereα\\alphais a parameter controlling the softmax temperature in[Equation˜4](https://arxiv.org/html/2606.14929#S2.E4)\. The rank ofΨm\\Psi\_\{m\}isKK\. Setting misspecificationμm≡0\\mu\_\{m\}\\equiv 0, the modelmmwith very high probability recommends the itemkt,mk\_\{t,m\}:

ξm​\(ek∣qt\)=exp⁡\(⟨Ψm,ek​qt𝖳⟩F\)∑k′=1Kexp⁡\(⟨Ψm,ek′​qt𝖳⟩F\)=exp⁡\(α​𝟙​\[k=kt,m\]\)\(K−1\)\+exp⁡\(α\),∀k∈\[M\]\.\\xi\_\{m\}\(e\_\{k\}\\mid q\_\{t\}\)=\\frac\{\\exp\(\\langle\\Psi\_\{m\},e\_\{k\}q\_\{t\}^\{\\mathsf\{T\}\}\\rangle\_\{F\}\)\}\{\\sum\_\{k^\{\\prime\}=1\}^\{K\}\\exp\(\\langle\\Psi\_\{m\},e\_\{k^\{\\prime\}\}q\_\{t\}^\{\\mathsf\{T\}\}\\rangle\_\{F\}\)\}=\\frac\{\\exp\(\\alpha\\mathbbm\{1\}\[k=k\_\{t,m\}\]\)\}\{\(K\-1\)\+\\exp\(\\alpha\)\},\\quad\\forall k\\in\[M\]\.
It only remains to construct the true rewards\. Following the construction bykale2014multiarmed, the environment picks a “good” expertm∗∈\[M\]m^\{\\ast\}\\in\[M\]uniformly at random before the game, and set

Ψ∗=δ​M​\[𝟎K×K⋯𝟎K×K𝑰K×K𝟎K×K⋯𝟎K×K\]∈ℝK×M​K,\\Psi^\{\\ast\}=\\delta\\sqrt\{M\}\[\\bm\{0\}\_\{K\\times K\}\\quad\\cdots\\quad\\bm\{0\}\_\{K\\times K\}\\quad\\bm\{I\}\_\{K\\times K\}\\quad\\bm\{0\}\_\{K\\times K\}\\quad\\cdots\\quad\\bm\{0\}\_\{K\\times K\}\]\\in\\mathbb\{R\}^\{K\\times MK\},where there areMMmatrices in total and𝑰K×K\\bm\{I\}\_\{K\\times K\}appears as them∗m^\{\\ast\}\-th, and theδ\>0\\delta\>0is a paremeter enabling information theoretic arguments\. ThisΨ∗\\Psi^\{\\ast\}ensuresr​\(qt,ek\)=δ​𝟙​\[k=kt,m∗\]r\(q\_\{t\},e\_\{k\}\)=\\delta\\mathbbm\{1\}\[k=k\_\{t,m^\{\\ast\}\}\]\. That is, only the item recommended by them∗m^\{\\ast\}\-th expert has a reward ofδ\\delta, whereas all others have zero reward\.

We therefore resemble the hard instance constructed bykale2014multiarmedby setting ourα\\alphaandδ\\deltaaccording to theirϵ\\epsilon\.kale2014multiarmedproved that in bandits with expert advice with limited observability, one suffers an expert regret lower bound of \(with notations from[Definition˜1](https://arxiv.org/html/2606.14929#Thmdefinition1)\)

ℜTE=Ω​\(min⁡\(K,N/log⁡K\)N​M​T\)\.\\mathfrak\{R\}\_\{T\}^\{E\}=\\Omega\\left\(\\sqrt\{\\frac\{\\min\(K,N/\\log K\)\}\{N\}MT\}\\right\)\.Plugging in our configuration thatN≤M≪da=KN\\leq M\\ll d\_\{a\}=K, we come at the conclusion that, even if we allow full observability on models, the policy regret w\.r\.t\.Πconst\\Pi\_\{\\text\{const\}\}\([Equation˜19](https://arxiv.org/html/2606.14929#A2.E19)\) is still at least

ℜT​\(Πconst\)=Ω​\(N/log⁡daN​M​T\)=Ω​\(M​Tlog⁡da\)\.∎\\mathfrak\{R\}\_\{T\}\(\\Pi\_\{\\text\{const\}\}\)=\\Omega\\left\(\\sqrt\{\\frac\{N/\\log d\_\{a\}\}\{N\}MT\}\\right\)=\\Omega\\left\(\\frac\{MT\}\{\\log d\_\{a\}\}\\right\)\.\\qed

### B\.3Unrestricted Policy Class and Contextual Regret

Similar to[Section˜B\.2](https://arxiv.org/html/2606.14929#A2.SS2), we begin by defining the problem of contextual linear bandits and contextual regret\. We use the adversarial formulation byliu2023bypassingto ease subsequent discussions\.

###### Definition 2\(Adversarial Contextual Linear Bandit;liu2023bypassing\)\.

Consider aTT\-round game between a learner and an environment\. In roundtt, a context, or equivalently, an action setAt⊆ℝdA\_\{t\}\\subseteq\\mathbb\{R\}^\{d\}, is presented to the learner\. The learner picks actionat∈Ata\_\{t\}\\in A\_\{t\}\. At the same time, the environment \(without observingata\_\{t\}\) chooses a loss vectorℓt∈ℝd\\ell\_\{t\}\\in\\mathbb\{R\}^\{d\}\. The learner incurs and observes a noisy sample of the loss⟨ℓt,at⟩\\langle\\ell\_\{t\},a\_\{t\}\\rangle\. The learner minimizes the contextual regret, defined as

ℜTC:=supπ∗𝔼\[∑t=1T\(⟨ℓt,at⟩−𝔼a∼π∗​\(At\)\[⟨ℓt,a⟩\]\)\],\\mathfrak\{R\}\_\{T\}^\{C\}:=\\sup\_\{\\pi^\{\\ast\}\}\\operatornamewithlimits\{\\mathbb\{E\}\}\\left\[\\sum\_\{t=1\}^\{T\}\\left\(\\langle\\ell\_\{t\},a\_\{t\}\\rangle\-\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{a\\sim\\pi^\{\\ast\}\(A\_\{t\}\)\}\[\\langle\\ell\_\{t\},a\\rangle\]\\right\)\\right\],\(20\)whereπ∗\\pi^\{\\ast\}is any policy that maps a subsetA⊆ℝdA\\subseteq\\mathbb\{R\}^\{d\}to a \(possibly randomized\) actiona∈Aa\\in Atherein\.

To illustrate the hardness of matching the unrestricted policy class△𝒬\\triangle^\{\\mathcal\{Q\}\}via reduction to[Definition˜2](https://arxiv.org/html/2606.14929#Thmdefinition2), throughout this section, we make the following two assumptions as mentioned in[Section˜3](https://arxiv.org/html/2606.14929#S3):

1. A1\.There is no misspecification in rewards or recommendation distributions so that everything is perfectly linear, i\.e\.,ν​\(q,a\)=μm​\(q,a\)=0\\nu\(q,a\)=\\mu\_\{m\}\(q,a\)=0for allq∈𝒬q\\in\\mathcal\{Q\}anda∈𝒜a\\in\\mathcal\{A\}in[Equations˜2](https://arxiv.org/html/2606.14929#S2.E2)and[4](https://arxiv.org/html/2606.14929#S2.E4)\.
2. A2\.The low\-rank recommendation kernels of each model, namely theΨm\\Psi\_\{m\}in[Equation˜4](https://arxiv.org/html/2606.14929#S2.E4), is also known to the learner in advance\. This allows the learner to calculate the following*expected recommendation*: a¯m​\(qt\):=𝔼a∼ξm​\(qt\)\[a\]∈ℝda,∀m∈\[M\],\\overline\{a\}\_\{m\}\(q\_\{t\}\):=\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{a\\sim\\xi\_\{m\}\(q\_\{t\}\)\}\[a\]\\in\\mathbb\{R\}^\{d\_\{a\}\},\\quad\\forall m\\in\[M\],which means this is an even stronger assumption than full observability on models \([Theorem˜6](https://arxiv.org/html/2606.14929#Thmtheorem6)\)\.

Since these two assumptions strictly ease learning, but matching the unrestricted policy class remains notoriously hard as we detail in subsequent sections, this metric is only harder in the original setup\.

#### B\.3\.1Unrestricted Policy Class→\\toA\-S Contextual Linear Bandit

The first reduction, as sketched in[Section˜3](https://arxiv.org/html/2606.14929#S3.SS0.SSS0.Px3)in the main text, is to the adversarial\-context stochastic\-loss \(“A\-S”\) contextual linear bandit problem\. Specifically, take theddin[Definition˜2](https://arxiv.org/html/2606.14929#Thmdefinition2)asd=da​dqd=d\_\{a\}d\_\{q\}\. The round\-ttaction set \(or context\) is given as

At=\{vec​\(a¯m​\(qt\)​qt𝖳\)\|m∈\[M\]\}⊆ℝd=ℝda​dq,A\_\{t\}=\\bigl\\\{\\text\{vec\}\(\\overline\{a\}\_\{m\}\(q\_\{t\}\)\\penalty 10000\\ q\_\{t\}^\{\\mathsf\{T\}\}\)\\mathrel\{\\big\|\}m\\in\[M\]\\bigr\\\}\\subseteq\\mathbb\{R\}^\{d\}=\\mathbb\{R\}^\{d\_\{a\}d\_\{q\}\},where thevec​\(⋅\)\\text\{vec\}\(\\cdot\)means flattering aℝm×n\\mathbb\{R\}^\{m\\times n\}matrix into aℝm​n\\mathbb\{R\}^\{mn\}vector:Ai,j=vec​\(A\)i×n\+jA\_\{i,j\}=\\text\{vec\}\(A\)\_\{i\\times n\+j\}\. Note that, assumption \(A2\) is used to ensure that the learner can calculate the action setAtA\_\{t\}in each roundtt\.

When choosing actiona=vec​\(a¯m​\(qt\)​qt𝖳\)∈Ata=\\text\{vec\}\(\\overline\{a\}\_\{m\}\(q\_\{t\}\)\\penalty 10000\\ q\_\{t\}^\{\\mathsf\{T\}\}\)\\in A\_\{t\}in roundtt, which is equivalent to choosing modelmmin roundtt, the expected loss \(i\.e\., negative\-reward\) is

−𝔼a∼ξm​\(qt\)\[r​\(qt,a\)\]=−⟨Ψ∗,𝔼a∼ξm​\(qt\)\[a\]⁡qt𝖳⟩F=−⟨vec​\(Ψ∗\),vec​\(a¯m​\(qt\)​qt𝖳\)⟩,\-\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{a\\sim\\xi\_\{m\}\(q\_\{t\}\)\}\[r\(q\_\{t\},a\)\]=\-\\Bigl\\langle\\Psi^\{\\ast\},\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{a\\sim\\xi\_\{m\}\(q\_\{t\}\)\}\[a\]\\penalty 10000\\ q\_\{t\}^\{\\mathsf\{T\}\}\\Bigr\\rangle\_\{F\}=\-\\Bigl\\langle\\text\{vec\}\(\\Psi^\{\\ast\}\),\\text\{vec\}\(\\overline\{a\}\_\{m\}\(q\_\{t\}\)\\penalty 10000\\ q\_\{t\}^\{\\mathsf\{T\}\}\)\\Bigr\\rangle,\(21\)where the first step uses the definition ofr​\(q,a\)r\(q,a\)in[Equation˜2](https://arxiv.org/html/2606.14929#S2.E2)and also assumption \(A1\) to ensure the linearity, and the second step uses the property that for two matricesA,B∈ℝm×nA,B\\in\\mathbb\{R\}^\{m\\times n\},

⟨A,B⟩F:=Tr\(A𝖳​B\)=∑i=1m∑j=1nAi,j​Bi,j=⟨vec​\(A\),vec​\(B\)⟩\.\\langle A,B\\rangle\_\{F\}:=\\operatornamewithlimits\{\\mathrm\{Tr\}\}\(A^\{\\mathsf\{T\}\}B\)=\\sum\_\{i=1\}^\{m\}\\sum\_\{j=1\}^\{n\}A\_\{i,j\}B\_\{i,j\}=\\langle\\text\{vec\}\(A\),\\text\{vec\}\(B\)\\rangle\.
Therefore, the loss vector in[Definition˜2](https://arxiv.org/html/2606.14929#Thmdefinition2)is always chosen asℓt=−vec​\(Ψ∗\)\\ell\_\{t\}=\-\\text\{vec\}\(\\Psi^\{\\ast\}\)\. This consequently reduces to an adversarial\-context \(becauseAtA\_\{t\}’s depend onqtq\_\{t\}and are thus adversarial\) and stochastic\-loss \(becauseℓt\\ell\_\{t\}is stationary\) contextual linear bandit problem\. We list a few available algorithms:

- •OFUL\(abbasi2011improved\):𝒪⁡\(d​T​log⁡T\)\\operatorname\{\\mathcal\{O\}\}\(d\\sqrt\{T\}\\log T\)contextual regret with𝒪⁡\(\|At\|​d2\)\\operatorname\{\\mathcal\{O\}\}\(\\lvert A\_\{t\}\\rvert d^\{2\}\)computation per round\. A faster “rarely switching” implementation is available, but the regret is the same\.
- •SupLinUCB\(chu2011contextual\):𝒪⁡\(d​T​log3⁡\(\|A\|​T\)\)\\operatorname\{\\mathcal\{O\}\}\\left\(\\sqrt\{dT\\log^\{3\}\(\\lvert A\\rvert T\)\}\\right\)contextual regret \(where\|A\|:=maxt⁡\|At\|\\lvert A\\rvert:=\\max\_\{t\}\\lvert A\_\{t\}\\rvert; in our case we thus have\|A\|=M\\lvert A\\rvert=M\) with𝒪⁡\(\|A\|​d2​log⁡T\)\\operatorname\{\\mathcal\{O\}\}\(\\lvert A\\rvert d^\{2\}\\log T\)computation per round\.
- •VCL\-SupLinUCB\(li2019nearly\):𝒪⁡\(d​T​log⁡T​log⁡\|A\|\)\\operatorname\{\\mathcal\{O\}\}\(\\sqrt\{dT\\log T\\log\\lvert A\\rvert\}\)contextual regret with𝒪⁡\(\|A\|​d2​log⁡T\)\\operatorname\{\\mathcal\{O\}\}\(\\lvert A\\rvert d^\{2\}\\log T\)computation per round\.

As we argued in[Section˜3](https://arxiv.org/html/2606.14929#S3), whend=dq​dqd=d\_\{q\}d\_\{q\}andda=dq=768d\_\{a\}=d\_\{q\}=768\(lee2025routerretriever,izacard2022unsupervised\), none of these regret bounds or computational cost guarantees are acceptable\.

#### B\.3\.2Unrestricted Policy Class→\\toA\-A Contextual Linear Bandit

A seemingly more promising reduction is rewriting[Equation˜21](https://arxiv.org/html/2606.14929#A2.E21)as adad\_\{a\}\-dimensional inner product:

−𝔼a∼ξm​\(qt\)\[r​\(qt,a\)\]=−⟨Ψ∗,𝔼a∼ξm​\(qt\)\[a\]⁡qt𝖳⟩F=−⟨Ψ∗​qt,a¯m​\(qt\)⟩,\-\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{a\\sim\\xi\_\{m\}\(q\_\{t\}\)\}\[r\(q\_\{t\},a\)\]=\-\\Bigl\\langle\\Psi^\{\\ast\},\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{a\\sim\\xi\_\{m\}\(q\_\{t\}\)\}\[a\]\\penalty 10000\\ q\_\{t\}^\{\\mathsf\{T\}\}\\Bigr\\rangle\_\{F\}=\-\\langle\\Psi^\{\\ast\}q\_\{t\},\\overline\{a\}\_\{m\}\(q\_\{t\}\)\\rangle,which corresponds to[Definition˜2](https://arxiv.org/html/2606.14929#Thmdefinition2)with round\-ttaction setAt=\{a¯m​\(qt\)\|m∈\[M\]\}⊆ℝdaA\_\{t\}=\\bigl\\\{\\overline\{a\}\_\{m\}\(q\_\{t\}\)\\mathrel\{\\big\|\}m\\in\[M\]\\bigr\\\}\\subseteq\\mathbb\{R\}^\{d\_\{a\}\}and loss vectorℓt=−Ψ∗​qt∈ℝda\\ell\_\{t\}=\-\\Psi^\{\\ast\}q\_\{t\}\\in\\mathbb\{R\}^\{d\_\{a\}\}\. While reducing the problem dimension greatly, the adversarialqtq\_\{t\}– appearing in both action set𝒜t\\mathcal\{A\}\_\{t\}and loss vectorℓt\\ell\_\{t\}– makes this problem intractable: Adversarial\-context adversarial\-loss \(so\-called “A\-A”\) contextual linear bandits are computationally infeasible\(kanade2014learning\), admitΩ​\(\|△𝒬\|\)\\Omega\(\\lvert\\triangle^\{\\mathcal\{Q\}\}\\rvert\)oracle\-complexity lower bounds\(hazan2016computational\), and are conjectured to bearΩ​\(T\)\\Omega\(T\)regret lower bounds\(neu2020efficient\)\.

#### B\.3\.3Unrestricted Policy Class with i\.i\.d\. Query→\\toS\-A Contextual Linear Bandit

Given the intractability comes from the fact that both the action setAtA\_\{t\}and the loss vectorℓt\\ell\_\{t\}are adversarial, what if we assume queries are i\.i\.d\. in addition to the assumptions \(A1\) and \(A2\)?

1. A3\.Assume that all queriesqtq\_\{t\}are i\.i\.d\. samples from a fixed but unknown distributionℚ∈△​\(𝒬\)\\mathbb\{Q\}\\in\\triangle\(\\mathcal\{Q\}\)\.

This assumption is justified by, e\.g\., in large\-scale e\-commerce systems, it is acceptable to expect customers come uniformly at random from a large population\. Now the action setAt=\{a¯m​\(qt\)\|m∈\[M\]\}A\_\{t\}=\\bigl\\\{\\overline\{a\}\_\{m\}\(q\_\{t\}\)\\mathrel\{\\big\|\}m\\in\[M\]\\bigr\\\}is i\.i\.d\., and only the loss vectorℓt=−Ψ∗​qt\\ell\_\{t\}=\-\\Psi^\{\\ast\}q\_\{t\}is time\-varying, does it fall into the tractable category of stochastic\-context adversarial\-loss \(“S\-A”\) contextual linear bandits? \(Whileℓt\\ell\_\{t\}is also stochastic, a stochastic\-loss setup requires a stationaryℓt\\ell\_\{t\}\.\) This is because S\-A contextual linear bandits admits an efficient algorithm with𝒪~⁡\(d2​T\)\\operatorname\{\\widetilde\{\\operatorname\{\\mathcal\{O\}\}\}\}\(d^\{2\}\\sqrt\{T\}\)contextual regret\(liu2023bypassing\)\. In our case where action sets have bounded sizes,𝒪⁡\(d​T​log⁡\|A\|\)\\operatorname\{\\mathcal\{O\}\}\(\\sqrt\{dT\\log\\lvert A\\rvert\}\)regret is also possible\(ito2024minimax\)\.

However, the answer is negative\. This is because all “S\-A” contextual linear bandit algorithms require the “ghost sample” technique proposed byneu2020efficient\. Roughly speaking, via the independence between losses and contexts, this technique allows one to analyze the contextual regret by “fixing” a singleq0∈ℚq\_\{0\}\\in\\mathbb\{Q\}throughout the game\. However, ourqtq\_\{t\}presents both in𝒜t=\{a¯m​\(qt\)\}m\\mathcal\{A\}\_\{t\}=\\\{\\overline\{a\}\_\{m\}\(q\_\{t\}\)\\\}\_\{m\}and inℓt=−Ψ∗​qt\\ell\_\{t\}=\-\\Psi^\{\\ast\}q\_\{t\}, thus inducing correlation\. All existing algorithms are hence inapplicable\(neu2020efficient,olkhovskaya2023first,liu2023bypassing,ito2024minimax,van2025improved\)\.

To conclude, matching the unrestricted policy class△𝒬\\triangle^\{\\mathcal\{Q\}\}or minimizing the contextual regretℜTC\\mathfrak\{R\}\_\{T\}^\{C\}is desirable for embedding model routing\. However, it is intractable – even after making the unrealistic assumptions of knowing model kernels and no misspecification – due to the extreme flexibility ofπ∗∈△𝒬\\pi^\{\\ast\}\\in\\triangle^\{\\mathcal\{Q\}\}, which can impose an*arbitrary*decision boundary when routing𝒬\\mathcal\{Q\}to△\\triangle\.

### B\.4Log\-Linear Policy Class and Linearization in Policy Regret

The log\-linear policy class is formally defined as follows:

Πlin:=\{π\(m∣q\)∝exp\(θm𝖳q\),∀q∈𝒬\|θm∈ℝdq,∀m∈\[M\]\}\.\\Pi\_\{\\text\{lin\}\}:=\\bigl\\\{\\pi\(m\\mid q\)\\propto\\exp\(\\theta\_\{m\}^\{\\mathsf\{T\}\}q\),\\forall q\\in\\mathcal\{Q\}\\mathrel\{\\big\|\}\\theta\_\{m\}\\in\\mathbb\{R\}^\{d\_\{q\}\},\\forall m\\in\[M\]\\bigr\\\}\.\(22\)
It assumes the routing policy is parameterized byMMdqd\_\{q\}\-dimensional vectors,𝜽=\(θ1,θ2,…,θM\)∈\(ℝdq\)M\\bm\{\\theta\}=\(\\theta\_\{1\},\\theta\_\{2\},\\ldots,\\theta\_\{M\}\)\\in\(\\mathbb\{R\}^\{d\_\{q\}\}\)^\{M\}\. We callΘ:=\(ℝdq\)M\\Theta:=\(\\mathbb\{R\}^\{d\_\{q\}\}\)^\{M\}the parameter space\. The policy induced by parameter𝜽∈Θ\\bm\{\\theta\}\\in\\Thetais thus

π𝜽​\(m∣q\)=exp⁡\(θm𝖳​q\)∑m′=1Mexp⁡\(θm′𝖳​q\),∀m∈\[M\],q∈𝒬\.\\pi\_\{\\bm\{\\theta\}\}\(m\\mid q\)=\\frac\{\\exp\(\\theta\_\{m\}^\{\\mathsf\{T\}\}q\)\}\{\\sum\_\{m^\{\\prime\}=1\}^\{M\}\\exp\(\\theta\_\{m^\{\\prime\}\}^\{\\mathsf\{T\}\}q\)\},\\quad\\forall m\\in\[M\],q\\in\\mathcal\{Q\}\.
Equivalently, we can view𝜽\\bm\{\\theta\}as a concatenatedM​dqMd\_\{q\}\-dimensional vector and let

ϕ​\(q,m\)=\[0𝖳⋯0𝖳q𝖳0𝖳⋯​0𝖳\]\\phi\(q,m\)=\[0^\{\\mathsf\{T\}\}\\quad\\cdots\\quad 0^\{\\mathsf\{T\}\}\\quad q^\{\\mathsf\{T\}\}\\quad 0^\{\\mathsf\{T\}\}\\quad\\cdots 0^\{\\mathsf\{T\}\}\]be the concatenation ofMMdqd\_\{q\}\-dimensional vectors with themm\-th one beingqqand all remaining ones being0\. Thusθm𝖳​q=𝜽𝖳​ϕ​\(q,m\)\\theta\_\{m\}^\{\\mathsf\{T\}\}q=\\bm\{\\theta\}^\{\\mathsf\{T\}\}\\phi\(q,m\), recovering the log\-linear class byagarwal2021theory\.

As discussed byagarwal2021theory,Πlin\\Pi\_\{\\text\{lin\}\}is much harder than the*tabular*softmax policy classΠtab\\Pi\_\{\\text\{tab\}\}, where each policyπ​\(m∣q\)∝exp⁡\(θq,m′\)\\pi\(m\\mid q\)\\propto\\exp\(\\theta^\{\\prime\}\_\{q,m\}\)for some𝜽′∈Θ′:=ℝM​\|𝒬\|\\bm\{\\theta\}^\{\\prime\}\\in\\Theta^\{\\prime\}:=\\mathbb\{R\}^\{M\\lvert\\mathcal\{Q\}\\rvert\}\. Indeed, forΠtab\\Pi\_\{\\text\{tab\}\}, it is possible to exactly handle the policy regret\(agarwal2021theory, Theorems 5\.1 and 5\.4\)\. However, for the log\-linear policy classΠlin\\Pi\_\{\\text\{lin\}\}, where the policyπ​\(m∣q\)∝exp⁡\(𝜽𝖳​ϕ​\(q,m\)\)\\pi\(m\\mid q\)\\propto\\exp\(\\bm\{\\theta\}^\{\\mathsf\{T\}\}\\phi\(q,m\)\)for some𝜽∈Θ:=ℝM​dq\\bm\{\\theta\}\\in\\Theta:=\\mathbb\{R\}^\{Md\_\{q\}\},agarwal2021theoryinstead considered a*linearized surrogate regret notion*instead of the policy regret\. We now introduce their notations and results in more details\. Since they focus on stochastic MDPs, we also assume i\.i\.d\. queries \(that is,qt∼ℚq\_\{t\}\\sim\\mathbb\{Q\}with some fixed but unknownℚ\\mathbb\{Q\}\) in this section\.

For any parameter𝜽∈Θ\\bm\{\\theta\}\\in\\Theta, letϕ¯𝜽​\(q,m\)=∇𝜽log⁡π𝜽​\(m∣q\)\\overline\{\\phi\}\_\{\\bm\{\\theta\}\}\(q,m\)=\\nabla\_\{\\bm\{\\theta\}\}\\log\\pi\_\{\\bm\{\\theta\}\}\(m\\mid q\)\. Now consider a roundt∈\[T\]t\\in\[T\]with parameter𝜽t∈Θ\\bm\{\\theta\}\_\{t\}\\in\\Theta\. For each modelm∈\[M\]m\\in\[M\], define the advantage under𝜽t\\bm\{\\theta\}\_\{t\}as

A𝜽t​\(q,m\)=𝔼a∼ξm​\(q\)\[r​\(q,a\)\]−∑m′=1Mπ𝜽t​\(m′∣q\)​𝔼a∼ξm′​\(q\)\[r​\(q,a\)\]\.A\_\{\\bm\{\\theta\}\_\{t\}\}\(q,m\)=\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{a\\sim\\xi\_\{m\}\(q\)\}\[r\(q,a\)\]\-\\sum\_\{m^\{\\prime\}=1\}^\{M\}\\pi\_\{\\bm\{\\theta\}\_\{t\}\}\(m^\{\\prime\}\\mid q\)\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{a\\sim\\xi\_\{m^\{\\prime\}\}\(q\)\}\[r\(q,a\)\]\.
The natural policy gradient \(NPG\) step in roundttis then given as\(agarwal2021theory, §6\.1\.1\)

𝒘t:=argmin𝒘∈Θ𝔼q∼ℚ,m∼π𝜽t\(⋅∣q\)\[\(A𝜽t​\(q,m\)−𝒘𝖳​ϕ¯𝜽t​\(q,m\)\)2\]\.\\bm\{w\}\_\{t\}:=\\operatornamewithlimits\{\\mathrm\{argmin\}\}\_\{\\bm\{w\}\\in\\Theta\}\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{q\\sim\\mathbb\{Q\},m\\sim\\pi\_\{\\bm\{\\theta\}\_\{t\}\}\(\\cdot\\mid q\)\}\\left\[\\left\(A\_\{\\bm\{\\theta\}\_\{t\}\}\(q,m\)\-\\bm\{w\}^\{\\mathsf\{T\}\}\\overline\{\\phi\}\_\{\\bm\{\\theta\}\_\{t\}\}\(q,m\)\\right\)^\{2\}\\right\]\.\(23\)agarwal2021theorydefined the following*transfer error*ϵbias\\epsilon\_\{\\text\{bias\}\}, and had a final bound scaling withϵbias×T\\sqrt\{\\epsilon\_\{\\text\{bias\}\}\}\\times T:121212The bound ofagarwal2021theoryis stated w\.r\.t\. single\-round sub\-optimality gaps, hence a linear dependency onTTarises when converting to our cumulative regret setup\. As an additional remark, theirγ\\gammais the discount factor that only applies to multi\-stage MDPs; in our bandit setup, we haveγ=0\\gamma=0\.

ϵbias\\displaystyle\\epsilon\_\{\\text\{bias\}\}:=maxt∈\[T\]​𝔼q∼ℚ,m∼π𝜽∗\(⋅∣q\)\[\(A𝜽t​\(q,m\)−𝒘t𝖳​ϕ¯𝜽t​\(q,m\)\)2\]\.\\displaystyle:=\\max\_\{t\\in\[T\]\}\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{q\\sim\\mathbb\{Q\},m\\sim\\pi\_\{\\bm\{\\theta\}^\{\\ast\}\}\(\\cdot\\mid q\)\}\\left\[\\left\(A\_\{\\bm\{\\theta\}\_\{t\}\}\(q,m\)\-\\bm\{w\}\_\{t\}^\{\\mathsf\{T\}\}\\overline\{\\phi\}\_\{\\bm\{\\theta\}\_\{t\}\}\(q,m\)\\right\)^\{2\}\\right\]\.
Let the expected reward – when takingq∼ℚq\\sim\\mathbb\{Q\}into consideration – of policyπ𝜽t\\pi\_\{\\bm\{\\theta\}\_\{t\}\}beJ​\(𝜽t\)J\(\\bm\{\\theta\}\_\{t\}\), defined as

J​\(𝜽t\):=𝔼q∼ℚ\[𝔼m∼π𝜽t​\(q\)\[𝔼a∼ξm​\(q\)\[r​\(q,a\)\]\]\]\.J\(\\bm\{\\theta\}\_\{t\}\):=\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{q\\sim\\mathbb\{Q\}\}\\left\[\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{m\\sim\\pi\_\{\\bm\{\\theta\}\_\{t\}\}\(q\)\}\\left\[\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{a\\sim\\xi\_\{m\}\(q\)\}\[r\(q,a\)\]\\right\]\\right\]\.
By direct arithmetic calculation \(which is the famous Performance Difference Lemma specialized to bandits;kakade2002approximately\), the one\-step true policy regret inℜT​\(Πlin\)\\mathfrak\{R\}\_\{T\}\(\\Pi\_\{\\text\{lin\}\}\)decomposes as

J​\(𝜽∗\)−J​\(𝜽t\)=𝔼q∼ℚ\[∑m=1Mπ𝜽∗​\(m∣q\)​A𝜽t​\(q,m\)\]\\displaystyle\\quad J\(\\bm\{\\theta\}^\{\\ast\}\)\-J\(\\bm\{\\theta\}\_\{t\}\)=\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{q\\sim\\mathbb\{Q\}\}\\left\[\\sum\_\{m=1\}^\{M\}\\pi\_\{\\bm\{\\theta\}^\{\\ast\}\}\(m\\mid q\)A\_\{\\bm\{\\theta\}\_\{t\}\}\(q,m\)\\right\]=𝔼q∼ℚ\[∑m=1Mπ𝜽∗​\(m∣q\)​𝒘t𝖳​ϕ¯𝜽t​\(q,m\)\]\+𝔼q∼ℚ\[∑m=1Mπ𝜽∗​\(m∣q\)​\(A𝜽t​\(q,m\)−𝒘t𝖳​ϕ¯𝜽t​\(q,m\)\)\]\.\\displaystyle=\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{q\\sim\\mathbb\{Q\}\}\\left\[\\sum\_\{m=1\}^\{M\}\\pi\_\{\\bm\{\\theta\}^\{\\ast\}\}\(m\\mid q\)\\bm\{w\}\_\{t\}^\{\\mathsf\{T\}\}\\overline\{\\phi\}\_\{\\bm\{\\theta\}\_\{t\}\}\(q,m\)\\right\]\+\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{q\\sim\\mathbb\{Q\}\}\\left\[\\sum\_\{m=1\}^\{M\}\\pi\_\{\\bm\{\\theta\}^\{\\ast\}\}\(m\\mid q\)\\left\(A\_\{\\bm\{\\theta\}\_\{t\}\}\(q,m\)\-\\bm\{w\}\_\{t\}^\{\\mathsf\{T\}\}\\overline\{\\phi\}\_\{\\bm\{\\theta\}\_\{t\}\}\(q,m\)\\right\)\\right\]\.
Instead of tacklingJ​\(𝜽∗\)−J​\(𝜽t\)J\(\\bm\{\\theta\}^\{\\ast\}\)\-J\(\\bm\{\\theta\}\_\{t\}\)directly,agarwal2021theorycontrolled the second term via Cauchy\-Schwartz asϵbias\\sqrt\{\\epsilon\_\{\\text\{bias\}\}\}and instead studied the first term\. For log\-linear policy class, we haveϕ¯𝜽t​\(q,m\)=ϕ​\(q,m\)−𝔼m′∼π𝜽t\(⋅∣q\)\[ϕ​\(q,m′\)\]\\overline\{\\phi\}\_\{\\bm\{\\theta\}\_\{t\}\}\(q,m\)=\\phi\(q,m\)\-\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{m^\{\\prime\}\\sim\\pi\_\{\\bm\{\\theta\}\_\{t\}\}\(\\cdot\\mid q\)\}\[\\phi\(q,m^\{\\prime\}\)\]\(agarwal2021theory, §6\.1\.1\)\. Thus, we know

𝒘t𝖳​ϕ¯𝜽t​\(q,m\)=wt,m𝖳​q−∑m′=1Mπ𝜽t​\(m′∣q\)​wt,m′𝖳​q\.\\bm\{w\}\_\{t\}^\{\\mathsf\{T\}\}\\overline\{\\phi\}\_\{\\bm\{\\theta\}\_\{t\}\}\(q,m\)=w\_\{t,m\}^\{\\mathsf\{T\}\}q\-\\sum\_\{m^\{\\prime\}=1\}^\{M\}\\pi\_\{\\bm\{\\theta\}\_\{t\}\}\(m^\{\\prime\}\\mid q\)w\_\{t,m^\{\\prime\}\}^\{\\mathsf\{T\}\}q\.Plugging this back into the first term and using the fact that∑m=1M𝜽∗​\(m∣q\)=1\\sum\_\{m=1\}^\{M\}\\bm\{\\theta\}^\{\\ast\}\(m\\mid q\)=1, we obtain:

𝔼q∼ℚ\[∑m=1Mπ𝜽∗​\(m∣q\)​𝒘t𝖳​ϕ¯𝜽t​\(q,m\)\]\\displaystyle\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{q\\sim\\mathbb\{Q\}\}\\left\[\\sum\_\{m=1\}^\{M\}\\pi\_\{\\bm\{\\theta\}^\{\\ast\}\}\(m\\mid q\)\\bm\{w\}\_\{t\}^\{\\mathsf\{T\}\}\\overline\{\\phi\}\_\{\\bm\{\\theta\}\_\{t\}\}\(q,m\)\\right\]=𝔼q∼ℚ\[∑m=1Mπ𝜽∗​\(m∣q\)​wt,m𝖳​q−∑m′=1Mπ𝜽t​\(m′∣q\)​wt,m′𝖳​q\]\\displaystyle=\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{q\\sim\\mathbb\{Q\}\}\\left\[\\sum\_\{m=1\}^\{M\}\\pi\_\{\\bm\{\\theta\}^\{\\ast\}\}\(m\\mid q\)w\_\{t,m\}^\{\\mathsf\{T\}\}q\-\\sum\_\{m^\{\\prime\}=1\}^\{M\}\\pi\_\{\\bm\{\\theta\}\_\{t\}\}\(m^\{\\prime\}\\mid q\)w\_\{t,m^\{\\prime\}\}^\{\\mathsf\{T\}\}q\\right\]=𝔼q∼ℚ\[∑m=1M\(π𝜽∗​\(m∣q\)−π𝜽t​\(m∣q\)\)​wt,m𝖳​q\],\\displaystyle=\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{q\\sim\\mathbb\{Q\}\}\\left\[\\sum\_\{m=1\}^\{M\}\\left\(\\pi\_\{\\bm\{\\theta\}^\{\\ast\}\}\(m\\mid q\)\-\\pi\_\{\\bm\{\\theta\}\_\{t\}\}\(m\\mid q\)\\right\)w\_\{t,m\}^\{\\mathsf\{T\}\}q\\right\],
agarwal2021theorythen proved that NPG attainsT\\sqrt\{T\}\-style regret under this*linearized surrogate regret*, but suffering a linearϵbias×T\\sqrt\{\\epsilon\_\{\\text\{bias\}\}\}\\times Toverhead in the true policy regret\. We remark that, however, their linearization happens in a different space from ourℜ~T​\(Π\)\\widetilde\{\\mathfrak\{R\}\}\_\{T\}\(\\Pi\)defined in[Equation˜11](https://arxiv.org/html/2606.14929#S3.E11): their linearization happens in the action space \(the probability simplex\), whereas ours happen in the parameter space \(the𝑾∈𝕎\\bm\{W\}\\in\\mathbb\{W\}, defined in[Section˜3\.2](https://arxiv.org/html/2606.14929#S3.SS2)\)\. It remains open whether these two linearized surrogate regret notions for the policy regret can be transformed to each other\.

### B\.5Log\-Quadratic Policy Class and Linearized Policy Regret

###### Proposition 7\(Linearized Policy Regret vs Policy Regret\)\.

Consider the log\-quadratic policy classΠquad\\Pi\_\{\\text\{quad\}\}parameterized by𝐖∈𝕎\\bm\{W\}\\in\\mathbb\{W\}; see[Section˜3\.2](https://arxiv.org/html/2606.14929#S3.SS2)\. For each roundt∈\[T\]t\\in\[T\]and modelm∈\[M\]m\\in\[M\], letπt,m:=π𝐖t​\(m∣qt\)\\pi\_\{t,m\}:=\\pi\_\{\\bm\{W\}\_\{t\}\}\(m\\mid q\_\{t\}\),πt,m∗:=π𝐖∗​\(m∣qt\)\\pi\_\{t,m\}^\{\\ast\}:=\\pi\_\{\\bm\{W\}^\{\\ast\}\}\(m\\mid q\_\{t\}\), andrt,m:=𝔼a∼ξm​\(qt\)\[r​\(qt,a\)\]r\_\{t,m\}:=\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{a\\sim\\xi\_\{m\}\(q\_\{t\}\)\}\[r\(q\_\{t\},a\)\]\. Then the one\-step regret in the policy regret w\.r\.t\.Πquad\\Pi\_\{\\text\{quad\}\}is \(whereℒt\\mathcal\{L\}\_\{t\}is defined in[Equation˜10](https://arxiv.org/html/2606.14929#S3.E10)\)

ℒt​\(𝑾t\)−ℒt​\(𝑾∗\)=∑m=1Mπt,m∗​\(rt,m−∑m′=1Mπt,m′​rt,m′\),\\mathcal\{L\}\_\{t\}\(\\bm\{W\}\_\{t\}\)\-\\mathcal\{L\}\_\{t\}\(\\bm\{W\}^\{\\ast\}\)=\\sum\_\{m=1\}^\{M\}\\pi\_\{t,m\}^\{\\ast\}\\left\(r\_\{t,m\}\-\\sum\_\{m^\{\\prime\}=1\}^\{M\}\\pi\_\{t,m^\{\\prime\}\}r\_\{t,m^\{\\prime\}\}\\right\),while that in the linearized policy regretℜ~T​\(Πquad\)\\widetilde\{\\mathfrak\{R\}\}\_\{T\}\(\\Pi\_\{\\text\{quad\}\}\)\(defined in[Equation˜11](https://arxiv.org/html/2606.14929#S3.E11)\) is

⟨∇𝑾ℒt​\(𝑾t\),𝑾t−𝑾∗⟩F=∑m=1Mπt,m​\(rt,m−∑m′=1Mπt,m′​rt,m′\)​log⁡πt,m∗πt,m\.\\Bigl\\langle\\nabla\_\{\\bm\{W\}\}\\mathcal\{L\}\_\{t\}\(\\bm\{W\}\_\{t\}\),\\bm\{W\}\_\{t\}\-\\bm\{W\}^\{\\ast\}\\Bigr\\rangle\_\{F\}=\\sum\_\{m=1\}^\{M\}\\pi\_\{t,m\}\\left\(r\_\{t,m\}\-\\sum\_\{m^\{\\prime\}=1\}^\{M\}\\pi\_\{t,m^\{\\prime\}\}r\_\{t,m^\{\\prime\}\}\\right\)\\log\\frac\{\\pi\_\{t,m\}^\{\\ast\}\}\{\\pi\_\{t,m\}\}\.

Given the very similar forms in[Proposition˜7](https://arxiv.org/html/2606.14929#Thmtheorem7), it is tempting to claim that these two regret notions are multiplicatively close to each other via a*gradient dominance condition*, it unfortunately fails\. The gradient dominance condition is given as follows\.131313This type of condition, also known as Łojasiewicz condition, has been developed byagarwal2021theoryandmei2020globalto exactly control the policy regret of NPG w\.r\.t\. the tabular softmax classΠtab:=\{π​\(m∣q\)∝exp⁡\(θq,m′\)∣𝜽′∈ℝM​\|𝒬\|\}\\Pi\_\{\\text\{tab\}\}:=\\\{\\pi\(m\\mid q\)\\propto\\exp\(\\theta^\{\\prime\}\_\{q,m\}\)\\mid\\bm\{\\theta\}^\{\\prime\}\\in\\mathbb\{R\}^\{M\\lvert\\mathcal\{Q\}\\rvert\}\\\}; see more in[SectionB\.4](https://arxiv.org/html/2606.14929#A2.SS4)\. We also remark their analysis only works with i\.i\.d\. queries\.Due to the projection onto the product nuclear\-norm ball𝔹∗M​\(τ\)\\mathbb\{B\}\_\{\\ast\}^\{M\}\(\\tau\), the maximum and minimum possible coefficient of a modelmmunder anyWm∈𝔹∗​\(τ\)W\_\{m\}\\in\\mathbb\{B\}\_\{\\ast\}\(\\tau\)are similar, hence givingmaxm⁡πm∗πm≤exp⁡\(2​τ\)\\max\_\{m\}\\frac\{\\pi\_\{m\}^\{\\ast\}\}\{\\pi\_\{m\}\}\\leq\\exp\(2\\tau\)\. But the other term,log⁡πm∗πm\\log\\frac\{\\pi\_\{m\}^\{\\ast\}\}\{\\pi\_\{m\}\}, is problematic: both it and the\(rm−∑m′=1Mπm′​rm′\)\(r\_\{m\}\-\\sum\_\{m^\{\\prime\}=1\}^\{M\}\\pi\_\{m^\{\\prime\}\}r\_\{m^\{\\prime\}\}\)term \(also known as the*advantage function*in reinforcement learning\) can be negative, hence the true policy regret is*not*automatically bounded byexp⁡\(2​τ\)\\exp\(2\\tau\)times the linearized policy regret\. We leave the exact policy regret for future research\.

###### Proof of[Proposition˜7](https://arxiv.org/html/2606.14929#Thmtheorem7)\.

For notational simplicity, we focus on a single roundt∈\[T\]t\\in\[T\]and omit all the subscripttt’s\. By definition ofℒt\\mathcal\{L\}\_\{t\}in[Equation˜10](https://arxiv.org/html/2606.14929#S3.E10), the one\-step regret inℜT​\(Πquad\)\\mathfrak\{R\}\_\{T\}\(\\Pi\_\{\\text\{quad\}\}\)\([Equation˜5](https://arxiv.org/html/2606.14929#S2.E5)\) is

ℒt​\(𝑾t\)−ℒt​\(𝑾∗\)\\displaystyle\\mathcal\{L\}\_\{t\}\(\\bm\{W\}\_\{t\}\)\-\\mathcal\{L\}\_\{t\}\(\\bm\{W\}^\{\\ast\}\)=∑m=1M\(πm∗−πm\)​rm​=\(a\)​∑m=1M\(πm∗−πm\)​rm−∑m=1M\(πm∗−πm\)​\(∑m′=1Mπm′​rm′\)\\displaystyle=\\sum\_\{m=1\}^\{M\}\(\\pi\_\{m\}^\{\\ast\}\-\\pi\_\{m\}\)r\_\{m\}\\overset\{\(a\)\}\{=\}\\sum\_\{m=1\}^\{M\}\(\\pi\_\{m\}^\{\\ast\}\-\\pi\_\{m\}\)r\_\{m\}\-\\sum\_\{m=1\}^\{M\}\(\\pi\_\{m\}^\{\\ast\}\-\\pi\_\{m\}\)\\left\(\\sum\_\{m^\{\\prime\}=1\}^\{M\}\\pi\_\{m^\{\\prime\}\}r\_\{m^\{\\prime\}\}\\right\)=\(b\)​∑m=1Mπm∗​\(rm−∑m′=1Mπm′​rm′\)−∑m=1Mπm​rm\+∑m′=1Mπm′​rm′\\displaystyle\\overset\{\(b\)\}\{=\}\\sum\_\{m=1\}^\{M\}\\pi\_\{m\}^\{\\ast\}\\left\(r\_\{m\}\-\\sum\_\{m^\{\\prime\}=1\}^\{M\}\\pi\_\{m^\{\\prime\}\}r\_\{m^\{\\prime\}\}\\right\)\-\\sum\_\{m=1\}^\{M\}\\pi\_\{m\}r\_\{m\}\+\\sum\_\{m^\{\\prime\}=1\}^\{M\}\\pi\_\{m^\{\\prime\}\}r\_\{m^\{\\prime\}\}=∑m=1Mπm∗​\(rm−∑m′=1Mπm′​rm′\)\.\\displaystyle=\\sum\_\{m=1\}^\{M\}\\pi\_\{m\}^\{\\ast\}\\left\(r\_\{m\}\-\\sum\_\{m^\{\\prime\}=1\}^\{M\}\\pi\_\{m^\{\\prime\}\}r\_\{m^\{\\prime\}\}\\right\)\.where \(a\) uses the fact that∑m\(πm∗−πm\)​C=\(1−1\)​C=0\\sum\_\{m\}\(\\pi\_\{m\}^\{\\ast\}\-\\pi\_\{m\}\)C=\(1\-1\)C=0for anyCCand \(b\) uses∑mπm=1\\sum\_\{m\}\\pi\_\{m\}=1\.

For the linearized policy regretℜ~T​\(Πquad\)\\widetilde\{\\mathfrak\{R\}\}\_\{T\}\(\\Pi\_\{\\text\{quad\}\}\)in[Equation˜11](https://arxiv.org/html/2606.14929#S3.E11), we have

⟨∇𝑾ℒt​\(𝑾t\),𝑾t−𝑾∗⟩F\\displaystyle\\Bigl\\langle\\nabla\_\{\\bm\{W\}\}\\mathcal\{L\}\_\{t\}\(\\bm\{W\}\_\{t\}\),\\bm\{W\}\_\{t\}\-\\bm\{W\}^\{\\ast\}\\Bigr\\rangle\_\{F\}=\(a\)​∑m=1M⟨−∑m′=1Mπm′​rm′​\(𝟙​\[m′=m\]−πm\)​qt​qt𝖳,Wt,m−Wm∗⟩F\\displaystyle\\overset\{\(a\)\}\{=\}\\sum\_\{m=1\}^\{M\}\\left\\langle\-\\sum\_\{m^\{\\prime\}=1\}^\{M\}\\pi\_\{m^\{\\prime\}\}r\_\{m^\{\\prime\}\}\\bigl\(\\mathbbm\{1\}\[m^\{\\prime\}=m\]\-\\pi\_\{m\}\\bigr\)q\_\{t\}q\_\{t\}^\{\\mathsf\{T\}\},W\_\{t,m\}\-W\_\{m\}^\{\\ast\}\\right\\rangle\_\{F\}=∑m=1M\(πm​rm−πm​∑m′=1Mπm′​rm′\)​qt𝖳​\(Wm∗−Wt,m\)​qt\\displaystyle=\\sum\_\{m=1\}^\{M\}\\left\(\\pi\_\{m\}r\_\{m\}\-\\pi\_\{m\}\\sum\_\{m^\{\\prime\}=1\}^\{M\}\\pi\_\{m^\{\\prime\}\}r\_\{m^\{\\prime\}\}\\right\)q\_\{t\}^\{\\mathsf\{T\}\}\\left\(W\_\{m\}^\{\\ast\}\-W\_\{t,m\}\\right\)q\_\{t\}=\(b\)​∑m=1Mπm​\(rm−∑m′=1Mπm′​rm′\)​log⁡πm∗πm,\\displaystyle\\overset\{\(b\)\}\{=\}\\sum\_\{m=1\}^\{M\}\\pi\_\{m\}\\left\(r\_\{m\}\-\\sum\_\{m^\{\\prime\}=1\}^\{M\}\\pi\_\{m^\{\\prime\}\}r\_\{m^\{\\prime\}\}\\right\)\\log\\frac\{\\pi\_\{m\}^\{\\ast\}\}\{\\pi\_\{m\}\},where \(a\) uses the direct sum property in[Lemma˜12](https://arxiv.org/html/2606.14929#Thmtheorem12)\(proved in[Section˜D\.2](https://arxiv.org/html/2606.14929#A4.SS2)\) and∇ℒt​\(𝑾\)\\nabla\\mathcal\{L\}\_\{t\}\(\\bm\{W\}\)derived in[Equation˜27](https://arxiv.org/html/2606.14929#A4.E27)\(rewritten using theπm\\pi\_\{m\}andrmr\_\{m\}notations\), and \(b\) uses the definition ofπ𝑾\\pi\_\{\\bm\{W\}\}:

log⁡π𝑾∗​\(m∣qt\)π𝑾t​\(m∣qt\)=log⁡\(exp⁡\(qt𝖳​Wm∗​qt\)∑m′=1Mexp⁡\(qt𝖳​Wm′∗​qt\)\)/\(exp⁡\(qt𝖳​Wt,m∗​qt\)∑m′=1Mexp⁡\(qt𝖳​Wt,m′​qt\)\)\\displaystyle\\quad\\log\\frac\{\\pi\_\{\\bm\{W\}^\{\\ast\}\}\(m\\mid q\_\{t\}\)\}\{\\pi\_\{\\bm\{W\}\_\{t\}\}\(m\\mid q\_\{t\}\)\}=\\log\\left\(\\frac\{\\exp\(q\_\{t\}^\{\\mathsf\{T\}\}W\_\{m\}^\{\\ast\}q\_\{t\}\)\}\{\\sum\_\{m^\{\\prime\}=1\}^\{M\}\\exp\(q\_\{t\}^\{\\mathsf\{T\}\}W\_\{m^\{\\prime\}\}^\{\\ast\}q\_\{t\}\)\}\\right\)\\Bigg/\\left\(\\frac\{\\exp\(q\_\{t\}^\{\\mathsf\{T\}\}W\_\{t,m\}^\{\\ast\}q\_\{t\}\)\}\{\\sum\_\{m^\{\\prime\}=1\}^\{M\}\\exp\(q\_\{t\}^\{\\mathsf\{T\}\}W\_\{t,m^\{\\prime\}\}q\_\{t\}\)\}\\right\)=log⁡exp⁡\(qt𝖳​Wm∗​qt\)exp⁡\(qt𝖳​Wt,m​qt\)\+log⁡∑m′=1Mexp⁡\(qt𝖳​Wm′∗​qt\)∑m′=1Mexp⁡\(qt𝖳​Wt,m′​qt\)=qt𝖳​\(Wm∗−Wt,m\)​qt\+C,\\displaystyle=\\log\\frac\{\\exp\(q\_\{t\}^\{\\mathsf\{T\}\}W\_\{m\}^\{\\ast\}q\_\{t\}\)\}\{\\exp\(q\_\{t\}^\{\\mathsf\{T\}\}W\_\{t,m\}q\_\{t\}\)\}\+\\log\\frac\{\\sum\_\{m^\{\\prime\}=1\}^\{M\}\\exp\(q\_\{t\}^\{\\mathsf\{T\}\}W\_\{m^\{\\prime\}\}^\{\\ast\}q\_\{t\}\)\}\{\\sum\_\{m^\{\\prime\}=1\}^\{M\}\\exp\(q\_\{t\}^\{\\mathsf\{T\}\}W\_\{t,m^\{\\prime\}\}q\_\{t\}\)\}=q\_\{t\}^\{\\mathsf\{T\}\}\(W\_\{m\}^\{\\ast\}\-W\_\{t,m\}\)q\_\{t\}\+C,whereCCis \(another\) constant independent tommthat automatically vanishes because

C​∑m=1Mπm​\(rm−∑m′=1Mπm′​rm′\)=C​∑m=1Mπm​rm−C​\(∑m=1Mπm\)​∑m′=1Mπm′​rm′=0\.∎C\\sum\_\{m=1\}^\{M\}\\pi\_\{m\}\\left\(r\_\{m\}\-\\sum\_\{m^\{\\prime\}=1\}^\{M\}\\pi\_\{m^\{\\prime\}\}r\_\{m^\{\\prime\}\}\\right\)=C\\sum\_\{m=1\}^\{M\}\\pi\_\{m\}r\_\{m\}\-C\\left\(\\sum\_\{m=1\}^\{M\}\\pi\_\{m\}\\right\)\\sum\_\{m^\{\\prime\}=1\}^\{M\}\\pi\_\{m^\{\\prime\}\}r\_\{m^\{\\prime\}\}=0\.\\qed

## Appendix CSetup of[Table˜2](https://arxiv.org/html/2606.14929#S3.T2)and More Discussions

As mentioned in the main text, we first encode every natural language query and item into 768\-dimensional vector spaces viaContriever\(izacard2022unsupervised\)\. For each embedded queryq∈ℝ768q\\in\\mathbb\{R\}^\{768\}and associated itema∈ℝ768a\\in\\mathbb\{R\}^\{768\}, the ESCI dataset labels it with one of four relevance scores: E \(Exact\), S \(Substitute\), C \(Complement\), or I \(Irrelevant\)\. We convert the four ordinal ESCI labels into numerical rewards asE=0\.95E=0\.95,S=0\.70S=0\.70,C=0\.30C=0\.30, andI=0\.05I=0\.05\(i\.e\., the reward functionr​\(q,a\)r\(q,a\)defined in[Equation˜1](https://arxiv.org/html/2606.14929#S2.E1)\)\. The specific values are a modeling choice that preserves the ordering of the labels and treats non\-exact but related products \(i\.e\., categories S and C\) as partially useful\.

We considerM=8M=8lightweight embedding models as candidate experts, spanning three distinct methodologies:\(i\)symmetric semantic encoders capturing similarities \(all\-MiniLM\-L6,\-L12, andparaphrase\-MiniLM;wang2020minilm,wang2021minilmv2\);\(ii\)asymmetric search models trained on Q&A datasets \(multi\-qa\-MiniLM,msmarco\-MiniLM, andmsmarco\-distilbert;reimers2019sentence,bajaj2016ms\); and\(iii\)modern prompt\-driven encoders dynamically adapting to different tasks \(e5\-small\-v2andbge\-small\-en\-v1\.5;wang2022text,xiao2024c\)\.

The recommendation distribution of each modelm∈\[M\]m\\in\[M\]on a queryq∈𝒬q\\in\\mathcal\{Q\}, namely theξm​\(q\)\\xi\_\{m\}\(q\)in[Equation˜4](https://arxiv.org/html/2606.14929#S2.E4)but instead supported on the candidate items corresponding to this query, is the softmax over the query\-item similarity scores induced by this model\. We then calculate the model’s expected rewardRm​\(q\)=𝔼a∼ξm​\(q\)\[r​\(q,a\)\]R\_\{m\}\(q\)=\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{a\\sim\\xi\_\{m\}\(q\)\}\[r\(q,a\)\]and find the optimal model routing policies within each class:141414Note that instead of online learning the optimal policies within different classes, in[Table2](https://arxiv.org/html/2606.14929#S3.T2)we perform offline optimization in order to verify the structural alignment of each class\.

- •πconst∗∈Πconst\\pi\_\{\\text\{const\}\}^\{\\ast\}\\in\\Pi\_\{\\text\{const\}\}maps each query to the best fixed modelm∗=argmaxm𝔼q\[Rm​\(q\)\]m^\{\\ast\}=\\operatornamewithlimits\{\\mathrm\{argmax\}\}\_\{m\}\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{q\}\[R\_\{m\}\(q\)\], where the expectation is taken over the uniform distribution over all queries in the ESCI dataset;
- •πlin∗∈Πlin\\pi\_\{\\text\{lin\}\}^\{\\ast\}\\in\\Pi\_\{\\text\{lin\}\}is the best log\-linear routing policy, i\.e\., in the form ofπ​\(m∣q\)∝exp⁡\(θm𝖳​q\)\\pi\(m\\mid q\)\\propto\\exp\(\\theta\_\{m\}^\{\\mathsf\{T\}\}q\)for some𝜽=\(θ1,θ2,…,θM\)∈\(ℝ768\)M\\bm\{\\theta\}=\(\\theta\_\{1\},\\theta\_\{2\},\\ldots,\\theta\_\{M\}\)\\in\(\\mathbb\{R\}^\{768\}\)^\{M\};
- •πquad∗∈Πquad\\pi\_\{\\text\{quad\}\}^\{\\ast\}\\in\\Pi\_\{\\text\{quad\}\}is the best log\-quadratic routing policy, i\.e\., in the form ofπ​\(m∣q\)∝exp⁡\(q𝖳​Wm​q\)\\pi\(m\\mid q\)\\propto\\exp\(q^\{\\mathsf\{T\}\}W\_\{m\}q\)for some𝑾=\(W1,W2,…,WM\)∈\(ℝ768×768\)M\\bm\{W\}=\(W\_\{1\},W\_\{2\},\\ldots,W\_\{M\}\)\\in\(\\mathbb\{R\}^\{768\\times 768\}\)^\{M\}; and
- •π∗:𝒬→△\\pi^\{\\ast\}\\colon\\mathcal\{Q\}\\to\\triangleis the best unrestricted policy, mapping any queryqqto the model that performs the best\. This, by definition, is the best model routing policy that one can possibly hope for\.

In[Table˜2](https://arxiv.org/html/2606.14929#S3.T2), we report the expected reward gap of each policy compared toπ∗\\pi^\{\\ast\}, i\.e\., theGapdefined in[Equation˜8](https://arxiv.org/html/2606.14929#S3.E8)\. We also report the relative improvement ofπlin∗\\pi\_\{\\text\{lin\}\}^\{\\ast\}overπconst∗\\pi\_\{\\text\{const\}\}^\{\\ast\}and that ofπquad∗\\pi\_\{\\text\{quad\}\}^\{\\ast\}overπlin∗\\pi\_\{\\text\{lin\}\}^\{\\ast\}\. We see thatGap​\(πconst∗\)=0\.078\\text\{Gap\}\(\\pi\_\{\\text\{const\}\}^\{\\ast\}\)=0\.078,Gap​\(πlin∗\)=0\.065\\text\{Gap\}\(\\pi\_\{\\text\{lin\}\}^\{\\ast\}\)=0\.065, andGap​\(πquad∗\)=0\.021\\text\{Gap\}\(\\pi\_\{\\text\{quad\}\}^\{\\ast\}\)=0\.021\(which, are all pretty small because the expert embedding models we chose are quite powerful\)\. We therefore observe that the improvement ofπlin∗\\pi\_\{\\text\{lin\}\}^\{\\ast\}overπconst∗\\pi\_\{\\text\{const\}\}^\{\\ast\}is incremental \(16\.4%\), whereas our proposed log\-quadratic policyπquad∗\\pi\_\{\\text\{quad\}\}^\{\\ast\}yields a68\.0%68\.0\\%improvement overπlin∗\\pi\_\{\\text\{lin\}\}^\{\\ast\}\(and,73\.1%73\.1\\%overπconst∗\\pi\_\{\\text\{const\}\}^\{\\ast\}\)\. This indicates that our analysis[Proposition˜1](https://arxiv.org/html/2606.14929#Thmtheorem1)is robust to the two discrepancies arising in the realistic ESCI dataset:\(i\)the reward functionr​\(q,a\)r\(q,a\)is not generated according to the bilinear structure in[Equation˜2](https://arxiv.org/html/2606.14929#S2.E2), and\(ii\)the misspecification in recommendation model distributions – in[Equation˜4](https://arxiv.org/html/2606.14929#S2.E4)– can be large\.

The ESCI dataset additionally includes several categories of challenging queries, where different embedding models are expected to exhibit different failure modes, making model routing more important\. For example,nlqecconsists of long natural\-language search queries\(papenmeier2021dataset\)\. On this category, the best constant policy incurs an expected sub\-optimality gap of0\.1090\.109\(where the expectation is taken uniformly over allnlqecqueries\), larger than the0\.0780\.078gap over the full reduced ESCI dataset; hence this category is indeed harder for any fixed expert model\. The log\-linear class reduces the gap to0\.0030\.003, closing97\.4%97\.4\\%of the constant\-policy gap, while our log\-quadratic class nearly closes the gap entirely by another99\.8%99\.8\\%improvement\.

Another category isnegations, which contains negation words such as “without\.” This category is not only hard for constant policies, but also hard for log\-linear policies: the bestπlinnegations∈Πlin\\pi\_\{\\text\{lin\}\}^\{\\texttt\{negations\}\}\\in\\Pi\_\{\\text\{lin\}\}still incurs a sub\-optimality gap of0\.0600\.060, whereas our log\-quadratic policy reduces it to0\.0070\.007, an88\.9%88\.9\\%reduction relative to the log\-linear gap\. Similar patterns hold forbehavioral, where queries are selected because their clicks or purchases have non\-representative distributions, andparse\-pattern, where queries exhibit linguistic complexity such as quantities or multiple modifiers\.

## Appendix DOmitted Proofs for Hypentropy Policy Gradient

### D\.1Matrix Functions and Convex Analysis

We first state a few properties of matrix functions and convex analysis without proof, mainly fromkakade2012regularization\. Since our matrices are always symmetric, we restrict our definitions to the symmetric matrix space𝕊n\\mathbb\{S\}^\{n\}, though most of them can be seamlessly extended to rectangular matrices\.

##### Convex Analysis\.

We view𝕊n\\mathbb\{S\}^\{n\}as an2n^\{2\}\-dimensional vector space equipped with the inner product:

⟨X,Y⟩F=Tr\(X𝖳​Y\)=∑i=1n∑j=1dXi,j​Yi,j,∀X,Y∈𝕊n\.\\langle X,Y\\rangle\_\{F\}=\\operatornamewithlimits\{\\mathrm\{Tr\}\}\(X^\{\\mathsf\{T\}\}Y\)=\\sum\_\{i=1\}^\{n\}\\sum\_\{j=1\}^\{d\}X\_\{i,j\}Y\_\{i,j\},\\quad\\forall X,Y\\in\\mathbb\{S\}^\{n\}\.Over a convex domain𝒦⊆𝕊n\\mathcal\{K\}\\subseteq\\mathbb\{S\}^\{n\}, a functionf:𝒦→ℝf\\colon\\mathcal\{K\}\\to\\mathbb\{R\}isα\\alpha\-strongly convex w\.r\.t\. some norm∥⋅∥\\lVert\\cdot\\rVertif

f​\(X\)−f​\(Y\)−∇f​\(Y\)​\(X−Y\)≥α2​∥X−Y∥2,∀X,Y∈𝕊n\.f\(X\)\-f\(Y\)\-\\nabla f\(Y\)\\penalty 10000\\ \(X\-Y\)\\geq\\frac\{\\alpha\}\{2\}\\lVert X\-Y\\rVert^\{2\},\\quad\\forall X,Y\\in\\mathbb\{S\}^\{n\}\.\(24\)Whenα=0\\alpha=0,[Equation˜24](https://arxiv.org/html/2606.14929#A4.E24)recovers the standard definition of convexity\. For a functionf:𝒦→ℝf\\colon\\mathcal\{K\}\\to\\mathbb\{R\}that is only \(strongly\) convex over a sub\-domain𝒦⊆𝕊n\\mathcal\{K\}\\subseteq\\mathbb\{S\}^\{n\}, we equivalently definef¯:𝕊n→ℝ∪\{∞\}\\overline\{f\}\\colon\\mathbb\{S\}^\{n\}\\to\\mathbb\{R\}\\cup\\\{\\infty\\\}asf¯​\(X\)=\{f​\(X\),X∈𝒦\+∞,X∉𝒦\\overline\{f\}\(X\)=\\begin\{cases\}f\(X\),&X\\in\\mathcal\{K\}\\\\ \+\\infty,&X\\not\\in\\mathcal\{K\}\\end\{cases\}, which is \(strongly\) convex over𝕊n\\mathbb\{S\}^\{n\}\. Its Fenchel dual is defined as

f∗​\(Z\):=supX∈𝕊n\(⟨X,Z⟩F−f¯​\(X\)\),∀Z∈𝕊n\.f^\{\\ast\}\(Z\):=\\sup\_\{X\\in\\mathbb\{S\}^\{n\}\}\\Bigl\(\\langle X,Z\\rangle\_\{F\}\-\\overline\{f\}\(X\)\\Bigr\),\\quad\\forall Z\\in\\mathbb\{S\}^\{n\}\.

##### Matrix Functions\.

For any symmetric real matrixX∈𝕊nX\\in\\mathbb\{S\}^\{n\}, it can always be eigen\-decomposed as

X=U​diag⁡\(λ​\(X\)\)​U𝖳,λ​\(X\):=\[λ1,λ2,…,λn\],X=U\\operatorname\{\\mathrm\{diag\}\}\(\\lambda\(X\)\)U^\{\\mathsf\{T\}\},\\quad\\lambda\(X\):=\[\\lambda\_\{1\},\\lambda\_\{2\},\\ldots,\\lambda\_\{n\}\],withλ1≥λ2≥⋯≥λn\\lambda\_\{1\}\\geq\\lambda\_\{2\}\\geq\\cdots\\geq\\lambda\_\{n\}being the eigenvalues ofXXandUUbeing an orthogonal matrix\. The following trace inequality will be used in analyzing the computational complexity \([Section˜E\.1](https://arxiv.org/html/2606.14929#A5.SS1)\):

###### Lemma 8\(Trace Inequality\(von1937some,fan1949theorem\)\)\.

ForX,Y∈𝕊nX,Y\\in\\mathbb\{S\}^\{n\}, we have⟨X,Y⟩F≤⟨λ​\(X\),λ​\(Y\)⟩\\langle X,Y\\rangle\_\{F\}\\leq\\langle\\lambda\(X\),\\lambda\(Y\)\\rangle\. The equality holds if and only if there exists an orthogonal matrixUUsuch that

X=U​diag⁡\(λ​\(X\)\)​U𝖳,Y=U​diag⁡\(λ​\(Y\)\)​U𝖳\.X=U\\operatorname\{\\mathrm\{diag\}\}\(\\lambda\(X\)\)U^\{\\mathsf\{T\}\},\\quad Y=U\\operatorname\{\\mathrm\{diag\}\}\(\\lambda\(Y\)\)U^\{\\mathsf\{T\}\}\.

A vector functionf:ℝn→ℝ∪\{∞\}f\\colon\\mathbb\{R\}^\{n\}\\to\\mathbb\{R\}\\cup\\\{\\infty\\\}is symmetric iff​\(x\)f\(x\)is invariant under any permutations of the components ofxx\. Any such function can be lifted to𝕊n\\mathbb\{S\}^\{n\}as aF:𝕊n→ℝ∪\{∞\}F\\colon\\mathbb\{S\}^\{n\}\\to\\mathbb\{R\}\\cup\\\{\\infty\\\}, defined as

F​\(X\):=f​\(λ​\(X\)\),∀X=U​diag⁡\(λ​\(X\)\)​U𝖳∈𝕊n\.F\(X\):=f\(\\lambda\(X\)\),\\quad\\forall X=U\\operatorname\{\\mathrm\{diag\}\}\(\\lambda\(X\)\)U^\{\\mathsf\{T\}\}\\in\\mathbb\{S\}^\{n\}\.
###### Lemma 9\(kakade2012regularization, Theorem 28\)\.

LetF:𝕊n→ℝ∪\{∞\}F\\colon\\mathbb\{S\}^\{n\}\\to\\mathbb\{R\}\\cup\\\{\\infty\\\}be lifted from a symmetricf:ℝn→ℝ∪\{∞\}f\\colon\\mathbb\{R\}^\{n\}\\to\\mathbb\{R\}\\cup\\\{\\infty\\\}\. The Fenchel dual ofFF, namelyF∗F^\{\\ast\}, is equal to the Fenchel dual offflifted to𝕊n\\mathbb\{S\}^\{n\}\.

###### Lemma 10\(kakade2012regularization, Theorem 30\)\.

LetF:𝕊n→ℝ∪\{∞\}F\\colon\\mathbb\{S\}^\{n\}\\to\\mathbb\{R\}\\cup\\\{\\infty\\\}be lifted from a symmetricf:ℝn→ℝ∪\{∞\}f\\colon\\mathbb\{R\}^\{n\}\\to\\mathbb\{R\}\\cup\\\{\\infty\\\}\. The gradient ofFFis given as

∇F​\(X\)=U​diag⁡\(∇f​\(λ​\(X\)\)\)​U𝖳,∀X=U​diag⁡\(λ​\(X\)\)​U𝖳∈𝕊n\.\\nabla F\(X\)=U\\operatorname\{\\mathrm\{diag\}\}\\bigl\(\\nabla f\(\\lambda\(X\)\)\\bigr\)U^\{\\mathsf\{T\}\},\\quad\\forall X=U\\operatorname\{\\mathrm\{diag\}\}\(\\lambda\(X\)\)U^\{\\mathsf\{T\}\}\\in\\mathbb\{S\}^\{n\}\.

After defining gradients, we can define the Bregman divergence for anyF:𝕊n→ℝ∪\{∞\}F\\colon\\mathbb\{S\}^\{n\}\\to\\mathbb\{R\}\\cup\\\{\\infty\\\}:

DF​\(X∥Y\):=F​\(X\)−F​\(Y\)−⟨∇F​\(Y\),X−F⟩F,∀X,Y∈𝕊n\.D\_\{F\}\(X\\\|Y\):=F\(X\)\-F\(Y\)\-\\langle\\nabla F\(Y\),X\-F\\rangle\_\{F\},\\quad\\forall X,Y\\in\\mathbb\{S\}^\{n\}\.\(25\)

##### Hypentropy Properties\.

We now move on to theβ\\beta\-Hypentropy functionΦβ:𝕊n→ℝ\\Phi\_\{\\beta\}\\colon\\mathbb\{S\}^\{n\}\\to\\mathbb\{R\}used in our HPG algorithm, which is defined as\(ghai2020exponentiated\):

Φβ​\(X\):=∑i=1n\(λi​arcsinh⁡λiβ−λi2\+β2\),∀X∈𝕊n,\\Phi\_\{\\beta\}\(X\):=\\sum\_\{i=1\}^\{n\}\\left\(\\lambda\_\{i\}\\operatorname\{\\mathrm\{arcsinh\}\}\\frac\{\\lambda\_\{i\}\}\{\\beta\}\-\\sqrt\{\\lambda\_\{i\}^\{2\}\+\\beta^\{2\}\}\\right\),\\quad\\forall X\\in\\mathbb\{S\}^\{n\},wherearcsinh⁡\(x\)=ln⁡\(x\+x2\+1\)\\operatorname\{\\mathrm\{arcsinh\}\}\(x\)=\\ln\(x\+\\sqrt\{x^\{2\}\+1\}\)\. It is lifted from the following vector functionϕβ:ℝn→ℝ\\phi\_\{\\beta\}\\colon\\mathbb\{R\}^\{n\}\\to\\mathbb\{R\}:

ϕβ​\(x\):=∑i=1n\(xi​arcsinh⁡xiβ−xi2\+β2\),∀x∈ℝn\.\\phi\_\{\\beta\}\(x\):=\\sum\_\{i=1\}^\{n\}\\left\(x\_\{i\}\\operatorname\{\\mathrm\{arcsinh\}\}\\frac\{x\_\{i\}\}\{\\beta\}\-\\sqrt\{x\_\{i\}^\{2\}\+\\beta^\{2\}\}\\right\),\\quad\\forall x\\in\\mathbb\{R\}^\{n\}\.
We have∂∂xi​ϕβ​\(x\)=arcsinh⁡xiβ\\frac\{\\partial\}\{\\partial x\_\{i\}\}\\phi\_\{\\beta\}\(x\)=\\operatorname\{\\mathrm\{arcsinh\}\}\\frac\{x\_\{i\}\}\{\\beta\}\. According to[Lemma˜10](https://arxiv.org/html/2606.14929#Thmtheorem10), for anyX∈𝕊nX\\in\\mathbb\{S\}^\{n\}, we have

∇Φβ​\(X\)=U​diag⁡\(arcsinh⁡λ​\(X\)β\)​U𝖳,∀X=U​diag⁡\(λ​\(X\)\)​U𝖳∈𝕊n\.\\nabla\\Phi\_\{\\beta\}\(X\)=U\\operatorname\{\\mathrm\{diag\}\}\\left\(\\operatorname\{\\mathrm\{arcsinh\}\}\\frac\{\\lambda\(X\)\}\{\\beta\}\\right\)U^\{\\mathsf\{T\}\},\\quad\\forall X=U\\operatorname\{\\mathrm\{diag\}\}\(\\lambda\(X\)\)U^\{\\mathsf\{T\}\}\\in\\mathbb\{S\}^\{n\}\.\(26\)Plugging[Equation˜26](https://arxiv.org/html/2606.14929#A4.E26)into[Equation˜25](https://arxiv.org/html/2606.14929#A4.E25)defines the Bregman divergence induced byΦβ\\Phi\_\{\\beta\}, namelyDΦβD\_\{\\Phi\}^\{\\beta\}\.

Finally, we include the following lemma, which ensures the hypentropy in𝕊n\\mathbb\{S\}^\{n\}is strongly convex w\.r\.t\. the nuclear norm∥⋅∥∗\\lVert\\cdot\\rVert\_\{\\ast\}over any nuclear\-norm ball\.

###### Lemma 11\(ghai2020exponentiated, Theorem 14\)\.

On the nuclear\-norm ball\{W∈𝕊n∣∥W∥∗≤τ\}\\\{W\\in\\mathbb\{S\}^\{n\}\\mid\\lVert W\\rVert\_\{\\ast\}\\leq\\tau\\\},Φβ\\Phi\_\{\\beta\}is\(2​\(τ\+β​n\)\)−1\\bigl\(2\(\\tau\+\\beta n\)\\bigr\)^\{\-1\}\-strongly convex w\.r\.t\. the nuclear norm∥⋅∥∗\\lVert\\cdot\\rVert\_\{\\ast\}\. That is,

Φβ​\(X\)−Φβ​\(Y\)−∇Φβ​\(Y\)​\(X−Y\)≥\(2​\(τ\+β​n\)\)−12​∥X−Y∥∗2,∀X,Y∈𝔹∗​\(τ\)\.\\Phi\_\{\\beta\}\(X\)\-\\Phi\_\{\\beta\}\(Y\)\-\\nabla\\Phi\_\{\\beta\}\(Y\)\\penalty 10000\\ \(X\-Y\)\\geq\\frac\{\\bigl\(2\(\\tau\+\\beta n\)\\bigr\)^\{\-1\}\}\{2\}\\lVert X\-Y\\rVert\_\{\\ast\}^\{2\},\\penalty 10000\\ \\penalty 10000\\ \\forall X,Y\\in\\mathbb\{B\}\_\{\\ast\}\(\\tau\)\.

### D\.2Direct Sum Property

###### Lemma 12\(Direct Sum Property\)\.

For any diagonal block matrix𝐖=diag⁡\(W1,W2,…,WM\)\\bm\{W\}=\\operatorname\{\\mathrm\{diag\}\}\(W\_\{1\},W\_\{2\},\\ldots,W\_\{M\}\),

Φβ\(𝑾\)=∑m=1MΦβ\(Wm\),∥𝑾∥∗=∑m=1M∥Wm∥∗,∥𝑾∥2=maxm∈\[M\]∥Wm∥2,\\Phi\_\{\\beta\}\(\\bm\{W\}\)=\\sum\_\{m=1\}^\{M\}\\Phi\_\{\\beta\}\(W\_\{m\}\),\\penalty 10000\\ \\lVert\\bm\{W\}\\rVert\_\{\\ast\}=\\sum\_\{m=1\}^\{M\}\\lVert W\_\{m\}\\rVert\_\{\\ast\},\\penalty 10000\\ \\lVert\\bm\{W\}\\rVert\_\{2\}=\\max\_\{m\\in\[M\]\}\\lVert W\_\{m\}\\rVert\_\{2\},which impliesDΦβ​\(𝐖∥𝐖′\)=∑m=1MDΦβ​\(Wm∥Wm′\)D\_\{\\Phi\}^\{\\beta\}\(\\bm\{W\}\\\|\\bm\{W\}^\{\\prime\}\)=\\sum\_\{m=1\}^\{M\}D\_\{\\Phi\}^\{\\beta\}\(W\_\{m\}\\\|W\_\{m\}^\{\\prime\}\)\. Moreover, over the product nuclear\-norm ball𝔹∗M\(τ\):=\{𝐖∈𝕎\|∥Wm∥∗≤τ,∀m\}\\mathbb\{B\}\_\{\\ast\}^\{M\}\(\\tau\):=\\bigl\\\{\\bm\{W\}\\in\\mathbb\{W\}\\mathrel\{\\big\|\}\\lVert W\_\{m\}\\rVert\_\{\\ast\}\\leq\\tau,\\forall m\\bigr\\\},Φβ\\Phi\_\{\\beta\}is block\-wise\(2​\(τ\+β​dq\)\)−1\\bigl\(2\(\\tau\+\\beta d\_\{q\}\)\\bigr\)^\{\-1\}\-strongly convex\.

###### Proof\.

Letλ​\(X\)\\lambda\(X\)denote the multiset of eigenvalues of a symmetric matrixXX\. Since𝑾=diag⁡\(W1,W2,…,WM\)∈𝕎\\bm\{W\}=\\operatorname\{\\mathrm\{diag\}\}\(W\_\{1\},W\_\{2\},\\dots,W\_\{M\}\)\\in\\mathbb\{W\}is a block\-diagonal symmetric matrix, its eigenvalues are exactly the union of the eigenvalues of its diagonal blocks, i\.e\.,λ​\(𝑾\)=⋃m=1Mλ​\(Wm\)\\lambda\(\\bm\{W\}\)=\\bigcup\_\{m=1\}^\{M\}\\lambda\(W\_\{m\}\)\.

Because the nuclear norm∥⋅∥∗\\lVert\\cdot\\rVert\_\{\\ast\}, the spectral norm∥⋅∥2\\lVert\\cdot\\rVert\_\{2\}, and the hypentropy potentialΦβ\\Phi\_\{\\beta\}are all spectral functions \(i\.e\., defined w\.r\.t\. eigenvalues\), they can be decomposed into blocks:

∥𝑾∥∗\\displaystyle\\lVert\\bm\{W\}\\rVert\_\{\\ast\}=∑λ∈λ​\(𝑾\)\|λ\|=∑m=1M∑λ∈λ​\(Wm\)\|λ\|=∑m=1M∥Wm∥∗,\\displaystyle=\\sum\_\{\\lambda\\in\\lambda\(\\bm\{W\}\)\}\|\\lambda\|=\\sum\_\{m=1\}^\{M\}\\sum\_\{\\lambda\\in\\lambda\(W\_\{m\}\)\}\|\\lambda\|=\\sum\_\{m=1\}^\{M\}\\lVert W\_\{m\}\\rVert\_\{\\ast\},∥𝑾∥2\\displaystyle\\lVert\\bm\{W\}\\rVert\_\{2\}=maxλ∈λ​\(𝑾\)\|λ\|=maxm∈\[M\]maxλ∈λ​\(Wm\)\|λ\|=maxm∈\[M\]∥Wm∥2,\\displaystyle=\\max\_\{\\lambda\\in\\lambda\(\\bm\{W\}\)\}\|\\lambda\|=\\max\_\{m\\in\[M\]\}\\max\_\{\\lambda\\in\\lambda\(W\_\{m\}\)\}\|\\lambda\|=\\max\_\{m\\in\[M\]\}\\lVert W\_\{m\}\\rVert\_\{2\},Φβ​\(𝑾\)\\displaystyle\\Phi\_\{\\beta\}\(\\bm\{W\}\)=∑λ∈λ​\(𝑾\)\(λ\+β\)​log⁡\(λ\+β\)=∑m=1M∑λ∈λ​\(Wm\)\(λ\+β\)​log⁡\(λ\+β\)=∑m=1MΦβ​\(Wm\)\.\\displaystyle=\\sum\_\{\\lambda\\in\\lambda\(\\bm\{W\}\)\}\(\\lambda\+\\beta\)\\log\(\\lambda\+\\beta\)=\\sum\_\{m=1\}^\{M\}\\sum\_\{\\lambda\\in\\lambda\(W\_\{m\}\)\}\(\\lambda\+\\beta\)\\log\(\\lambda\+\\beta\)=\\sum\_\{m=1\}^\{M\}\\Phi\_\{\\beta\}\(W\_\{m\}\)\.
From[Lemma˜10](https://arxiv.org/html/2606.14929#Thmtheorem10), the gradient of a spectral function evaluated at a block\-diagonal matrix remains block\-diagonal, i\.e\.,∇Φβ​\(𝑾′\)=diag⁡\(∇Φβ​\(W1′\),…,∇Φβ​\(WM′\)\)\\nabla\\Phi\_\{\\beta\}\(\\bm\{W\}^\{\\prime\}\)=\\operatorname\{\\mathrm\{diag\}\}\\bigl\(\\nabla\\Phi\_\{\\beta\}\(W\_\{1\}^\{\\prime\}\),\\dots,\\nabla\\Phi\_\{\\beta\}\(W\_\{M\}^\{\\prime\}\)\\bigr\)\. Further using the additivity ofΦβ\\Phi\_\{\\beta\}and the fact that the Frobenius inner product also decomposes into the sum of block\-wise inner products, the Bregman divergence decomposes as:

DΦβ​\(𝑾∥𝑾′\)\\displaystyle D\_\{\\Phi\}^\{\\beta\}\(\\bm\{W\}\\\|\\bm\{W\}^\{\\prime\}\)=Φβ​\(𝑾\)−Φβ​\(𝑾′\)−⟨∇Φβ​\(𝑾′\),𝑾−𝑾′⟩F\\displaystyle=\\Phi\_\{\\beta\}\(\\bm\{W\}\)\-\\Phi\_\{\\beta\}\(\\bm\{W\}^\{\\prime\}\)\-\\langle\\nabla\\Phi\_\{\\beta\}\(\\bm\{W\}^\{\\prime\}\),\\bm\{W\}\-\\bm\{W\}^\{\\prime\}\\rangle\_\{F\}=∑m=1M\(Φβ​\(Wm\)−Φβ​\(Wm′\)−⟨∇Φβ​\(Wm′\),Wm−Wm′⟩F\)=∑m=1MDΦβ​\(Wm∥Wm′\)\.\\displaystyle=\\sum\_\{m=1\}^\{M\}\\left\(\\Phi\_\{\\beta\}\(W\_\{m\}\)\-\\Phi\_\{\\beta\}\(W\_\{m\}^\{\\prime\}\)\-\\langle\\nabla\\Phi\_\{\\beta\}\(W\_\{m\}^\{\\prime\}\),W\_\{m\}\-W\_\{m\}^\{\\prime\}\\rangle\_\{F\}\\right\)=\\sum\_\{m=1\}^\{M\}D\_\{\\Phi\}^\{\\beta\}\(W\_\{m\}\\\|W\_\{m\}^\{\\prime\}\)\.
From[Lemma˜11](https://arxiv.org/html/2606.14929#Thmtheorem11), over thedqd\_\{q\}\-dimensional nuclear\-norm ball𝔹∗​\(τ\)\\mathbb\{B\}\_\{\\ast\}\(\\tau\), the hypentropy potentialΦβ\\Phi\_\{\\beta\}is\(2​\(τ\+β​dq\)\)−1\\bigl\(2\(\\tau\+\\beta d\_\{q\}\)\\bigr\)^\{\-1\}\-strongly convex\. For any𝑾∈𝔹∗M​\(τ\)\\bm\{W\}\\in\\mathbb\{B\}\_\{\\ast\}^\{M\}\(\\tau\), we haveWm∈𝔹∗​\(τ\)W\_\{m\}\\in\\mathbb\{B\}\_\{\\ast\}\(\\tau\)for allm∈\[M\]m\\in\[M\]\. SinceΦβ​\(𝑾\)=∑m=1MΦβ​\(Wm\)\\Phi\_\{\\beta\}\(\\bm\{W\}\)=\\sum\_\{m=1\}^\{M\}\\Phi\_\{\\beta\}\(W\_\{m\}\), the Hessian∇2Φβ​\(𝑾\)\\nabla^\{2\}\\Phi\_\{\\beta\}\(\\bm\{W\}\)is block\-diagonal where each block∇2Φβ​\(Wm\)\\nabla^\{2\}\\Phi\_\{\\beta\}\(W\_\{m\}\)satisfiesα\\alpha\-strong convexity\. Thus,Φβ\\Phi\_\{\\beta\}is block\-wiseα\\alpha\-strongly convex over𝔹∗M​\(τ\)\\mathbb\{B\}\_\{\\ast\}^\{M\}\(\\tau\)\. ∎

### D\.3Gradient Estimation \([Lemma˜2](https://arxiv.org/html/2606.14929#Thmtheorem2)\)

###### Proof of[Lemma˜2](https://arxiv.org/html/2606.14929#Thmtheorem2)\.

Recall that the round\-ttloss function for parameter𝑾\\bm\{W\}, namelyℒt​\(𝑾\)\\mathcal\{L\}\_\{t\}\(\\bm\{W\}\), is

ℒt​\(𝑾\)=−𝔼m′∼π𝑾​\(qt\)\[𝔼a∼ξm′​\(qt\)\[r​\(qt,a\)\]\],∀t∈\[T\],𝑾∈𝕎,\\mathcal\{L\}\_\{t\}\(\\bm\{W\}\)=\-\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{m^\{\\prime\}\\sim\\pi\_\{\\bm\{W\}\}\(q\_\{t\}\)\}\\left\[\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{a\\sim\\xi\_\{m^\{\\prime\}\}\(q\_\{t\}\)\}\[r\(q\_\{t\},a\)\]\\right\],\\quad\\forall t\\in\[T\],\\bm\{W\}\\in\\mathbb\{W\},whereπ𝑾\\pi\_\{\\bm\{W\}\}is the log\-quadratic policy induced by𝑾\\bm\{W\}\(see[Equation˜9](https://arxiv.org/html/2606.14929#S3.E9)\)\. We intentionally changed allmm’s in the original definition tom′m^\{\\prime\}, so that we can take the partial derivative w\.r\.t\. anym∈\[M\]m\\in\[M\]as:

∂∂Wm​ℒt​\(𝑾\)=−∑m′=1M\(𝔼a∼ξm′​\(qt\)\[r​\(qt,a\)\]⁡∂∂Wm​π𝑾​\(m′∣qt\)\)\.\\frac\{\\partial\}\{\\partial W\_\{m\}\}\\mathcal\{L\}\_\{t\}\(\\bm\{W\}\)=\-\\sum\_\{m^\{\\prime\}=1\}^\{M\}\\left\(\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{a\\sim\\xi\_\{m^\{\\prime\}\}\(q\_\{t\}\)\}\[r\(q\_\{t\},a\)\]\\penalty 10000\\ \\frac\{\\partial\}\{\\partial W\_\{m\}\}\\pi\_\{\\bm\{W\}\}\(m^\{\\prime\}\\mid q\_\{t\}\)\\right\)\.By definition ofπ𝑾\\pi\_\{\\bm\{W\}\}in[Equation˜9](https://arxiv.org/html/2606.14929#S3.E9), we have by the definition of softmax that

∂∂Wm​π𝑾​\(m′∣qt\)=∂∂Wm​exp⁡\(qt𝖳​Wm′​qt\)∑m′′exp⁡\(qt𝖳​Wm′′​qt\)=π𝑾​\(m′∣qt\)​\(𝟙​\[m′=m\]−π𝑾​\(m∣qt\)\)​qt​qt𝖳\.\\frac\{\\partial\}\{\\partial W\_\{m\}\}\\pi\_\{\\bm\{W\}\}\(m^\{\\prime\}\\mid q\_\{t\}\)=\\frac\{\\partial\}\{\\partial W\_\{m\}\}\\frac\{\\exp\(q\_\{t\}^\{\\mathsf\{T\}\}W\_\{m^\{\\prime\}\}q\_\{t\}\)\}\{\\sum\_\{m^\{\\prime\\prime\}\}\\exp\(q\_\{t\}^\{\\mathsf\{T\}\}W\_\{m^\{\\prime\\prime\}\}q\_\{t\}\)\}=\\pi\_\{\\bm\{W\}\}\(m^\{\\prime\}\\mid q\_\{t\}\)\\left\(\\mathbbm\{1\}\[m^\{\\prime\}=m\]\-\\pi\_\{\\bm\{W\}\}\(m\\mid q\_\{t\}\)\\right\)q\_\{t\}q\_\{t\}^\{\\mathsf\{T\}\}\.Therefore, we have for anym∈\[M\]m\\in\[M\]that

∂∂Wm​ℒt​\(𝑾\)=−𝔼m′∼π𝑾​\(qt\)\[𝔼a∼ξm′​\(qt\)\[r​\(qt,a\)\]⁡\(𝟙​\[m′=m\]−π𝑾​\(m∣qt\)\)​qt​qt𝖳\]\.\\frac\{\\partial\}\{\\partial W\_\{m\}\}\\mathcal\{L\}\_\{t\}\(\\bm\{W\}\)=\-\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{m^\{\\prime\}\\sim\\pi\_\{\\bm\{W\}\}\(q\_\{t\}\)\}\\left\[\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{a\\sim\\xi\_\{m^\{\\prime\}\}\(q\_\{t\}\)\}\[r\(q\_\{t\},a\)\]\\penalty 10000\\ \\left\(\\mathbbm\{1\}\[m^\{\\prime\}=m\]\-\\pi\_\{\\bm\{W\}\}\(m\\mid q\_\{t\}\)\\right\)q\_\{t\}q\_\{t\}^\{\\mathsf\{T\}\}\\right\]\.\(27\)
Hence conditional on the history before roundttand the round\-ttqueryqtq\_\{t\}, the expectation ofG^t,m\\widehat\{G\}\_\{t,m\}in[Equation˜15](https://arxiv.org/html/2606.14929#S4.E15)– taken w\.r\.t\.mt∼π𝑾t​\(qt\)m\_\{t\}\\sim\\pi\_\{\\bm\{W\}\_\{t\}\}\(q\_\{t\}\),at∼ξmt​\(qt\)a\_\{t\}\\sim\\xi\_\{m\_\{t\}\}\(q\_\{t\}\), andrt=r​\(qt,at\)\+ηtr\_\{t\}=r\(q\_\{t\},a\_\{t\}\)\+\\eta\_\{t\}– is given as

𝔼t\[G^t,m∣qt\]=𝔼t\[−rt​\(𝟙​\[mt=m\]−π𝑾t​\(m∣qt\)\)​qt​qt𝖳\|qt\]\\displaystyle\\quad\\operatornamewithlimits\{\\mathbb\{E\}\}\\nolimits\_\{t\}\[\\widehat\{G\}\_\{t,m\}\\mid q\_\{t\}\]=\\operatornamewithlimits\{\\mathbb\{E\}\}\\nolimits\_\{t\}\\Bigl\[\-r\_\{t\}\\bigl\(\\mathbbm\{1\}\[m\_\{t\}=m\]\-\\pi\_\{\\bm\{W\}\_\{t\}\}\(m\\mid q\_\{t\}\)\\bigr\)q\_\{t\}q\_\{t\}^\{\\mathsf\{T\}\}\\mathrel\{\\Big\|\}q\_\{t\}\\Bigr\]=𝔼mt∼π𝑾t​\(qt\)\[𝔼at∼ξmt​\(qt\)\[𝔼ηt\[−rt​\(𝟙​\[mt=m\]−π𝑾t​\(m∣qt\)\)​qt​qt𝖳\|qt,mt,at\]\|qt,mt\]\]\\displaystyle=\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{m\_\{t\}\\sim\\pi\_\{\\bm\{W\}\_\{t\}\}\(q\_\{t\}\)\}\\left\[\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{a\_\{t\}\\sim\\xi\_\{m\_\{t\}\}\(q\_\{t\}\)\}\\left\[\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{\\eta\_\{t\}\}\\Bigl\[\-r\_\{t\}\\bigl\(\\mathbbm\{1\}\[m\_\{t\}=m\]\-\\pi\_\{\\bm\{W\}\_\{t\}\}\(m\\mid q\_\{t\}\)\\bigr\)q\_\{t\}q\_\{t\}^\{\\mathsf\{T\}\}\\mathrel\{\\Big\|\}q\_\{t\},m\_\{t\},a\_\{t\}\\Bigr\]\\mathrel\{\\Big\|\}q\_\{t\},m\_\{t\}\\right\]\\right\]=𝔼mt∼π𝑾t​\(qt\)\[𝔼at∼ξmt​\(qt\)\[−r​\(qt,at\)​\(𝟙​\[mt=m\]−π𝑾t​\(m∣qt\)\)​qt​qt𝖳\|qt,mt\]\]\\displaystyle=\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{m\_\{t\}\\sim\\pi\_\{\\bm\{W\}\_\{t\}\}\(q\_\{t\}\)\}\\left\[\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{a\_\{t\}\\sim\\xi\_\{m\_\{t\}\}\(q\_\{t\}\)\}\\left\[\-r\(q\_\{t\},a\_\{t\}\)\\bigl\(\\mathbbm\{1\}\[m\_\{t\}=m\]\-\\pi\_\{\\bm\{W\}\_\{t\}\}\(m\\mid q\_\{t\}\)\\bigr\)q\_\{t\}q\_\{t\}^\{\\mathsf\{T\}\}\\mathrel\{\\Big\|\}q\_\{t\},m\_\{t\}\\right\]\\right\]=𝔼mt∼π𝑾t​\(qt\)\[−𝔼at∼ξmt​\(qt\)\[r​\(qt,at\)\]⁡\(𝟙​\[mt=m\]−π𝑾t​\(m∣qt\)\)​qt​qt𝖳\],\\displaystyle=\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{m\_\{t\}\\sim\\pi\_\{\\bm\{W\}\_\{t\}\}\(q\_\{t\}\)\}\\left\[\-\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{a\_\{t\}\\sim\\xi\_\{m\_\{t\}\}\(q\_\{t\}\)\}\[r\(q\_\{t\},a\_\{t\}\)\]\\bigl\(\\mathbbm\{1\}\[m\_\{t\}=m\]\-\\pi\_\{\\bm\{W\}\_\{t\}\}\(m\\mid q\_\{t\}\)\\bigr\)q\_\{t\}q\_\{t\}^\{\\mathsf\{T\}\}\\right\],which is exactly the RHS of[Equation˜27](https://arxiv.org/html/2606.14929#A4.E27)\. Thus we have𝔼t\[𝑮^t∣qt\]=∇𝑾ℒ​\(𝑾t\)\\operatornamewithlimits\{\\mathbb\{E\}\}\_\{t\}\[\\widehat\{\\bm\{G\}\}\_\{t\}\\mid q\_\{t\}\]=\\nabla\_\{\\bm\{W\}\}\\mathcal\{L\}\(\\bm\{W\}\_\{t\}\)unbiased\. Furthermore,

∑m=1M∥G^t,m∥22\\displaystyle\\sum\_\{m=1\}^\{M\}\\lVert\\widehat\{G\}\_\{t,m\}\\rVert\_\{2\}^\{2\}=rt2​∑m=1M\(𝟙​\[mt=m\]−π𝑾t​\(m∣qt\)\)2​∥qt∥22\\displaystyle=r\_\{t\}^\{2\}\\sum\_\{m=1\}^\{M\}\\bigl\(\\mathbbm\{1\}\[m\_\{t\}=m\]\-\\pi\_\{\\bm\{W\}\_\{t\}\}\(m\\mid q\_\{t\}\)\\bigr\)^\{2\}\\lVert q\_\{t\}\\rVert\_\{2\}^\{2\}≤\(1−π𝑾t​\(mt∣qt\)\)2\+∑m=1Mπ𝑾t2​\(m∣qt\)≤2,\\displaystyle\\leq\(1\-\\pi\_\{\\bm\{W\}\_\{t\}\}\(m\_\{t\}\\mid q\_\{t\}\)\)^\{2\}\+\\sum\_\{m=1\}^\{M\}\\pi\_\{\\bm\{W\}\_\{t\}\}^\{2\}\(m\\mid q\_\{t\}\)\\leq 2,where the first inequality uses\|rt\|≤1\\lvert r\_\{t\}\\rvert\\leq 1and∥qt∥2≤1\\lVert q\_\{t\}\\rVert\_\{2\}\\leq 1, and the second inequality uses the fact thatπ𝑾t​\(qt\)∈△\\pi\_\{\\bm\{W\}\_\{t\}\}\(q\_\{t\}\)\\in\\triangleis a probability distribution \(hence∑mπ𝑾t2​\(m∣qt\)≤∑mπ𝑾t​\(m∣qt\)=1\\sum\_\{m\}\\pi\_\{\\bm\{W\}\_\{t\}\}^\{2\}\(m\\mid q\_\{t\}\)\\leq\\sum\_\{m\}\\pi\_\{\\bm\{W\}\_\{t\}\}\(m\\mid q\_\{t\}\)=1\)\. ∎

### D\.4Linearized Policy Regret Bound of HPG \([Theorem˜3](https://arxiv.org/html/2606.14929#Thmtheorem3)\)

###### Proof of[Theorem˜3](https://arxiv.org/html/2606.14929#Thmtheorem3)\.

According to the assumption that the optimal𝑾∗∈𝕎\\bm\{W\}^\{\\ast\}\\in\\mathbb\{W\}ensures∥Wm∗∥∗≤τ\\lVert W\_\{m\}^\{\\ast\}\\rVert\_\{\\ast\}\\leq\\tau,∀m\\forall m, we have𝑾∗∈𝔹∗M​\(τ\)\\bm\{W\}^\{\\ast\}\\in\\mathbb\{B\}\_\{\\ast\}^\{M\}\(\\tau\)\(recall[Equation˜12](https://arxiv.org/html/2606.14929#S4.E12)\)\. Recall the OMD one\-step update rule in[Equation˜14](https://arxiv.org/html/2606.14929#S4.E14):

𝑾t\+1=argmin𝑾∈𝔹∗M​\(τ\)\(η​⟨𝑾,𝑮^t⟩F\+DΦβ​\(𝑾∥𝑾t\)\)\.\\bm\{W\}\_\{t\+1\}=\\operatornamewithlimits\{\\mathrm\{argmin\}\}\_\{\\bm\{W\}\\in\\mathbb\{B\}\_\{\\ast\}^\{M\}\(\\tau\)\}\\Bigl\(\\eta\\bigl\\langle\\bm\{W\},\\widehat\{\\bm\{G\}\}\_\{t\}\\bigr\\rangle\_\{F\}\+D\_\{\\Phi\}^\{\\beta\}\(\\bm\{W\}\\\|\\bm\{W\}\_\{t\}\)\\Bigr\)\.Using the direct sum property[Lemma˜12](https://arxiv.org/html/2606.14929#Thmtheorem12)later proved in[Section˜D\.2](https://arxiv.org/html/2606.14929#A4.SS2), this is equivalent to

Wt\+1,m=argminW∈𝔹∗​\(τ\)\(η​⟨W,G^t,m⟩F\+DΦβ​\(W∥Wt,m\)\),∀m∈\[M\],W\_\{t\+1,m\}=\\operatornamewithlimits\{\\mathrm\{argmin\}\}\_\{W\\in\\mathbb\{B\}\_\{\\ast\}\(\\tau\)\}\\Bigl\(\\eta\\bigl\\langle W,\\widehat\{G\}\_\{t,m\}\\bigr\\rangle\_\{F\}\+D\_\{\\Phi\}^\{\\beta\}\(W\\\|W\_\{t,m\}\)\\Bigr\),\\quad\\forall m\\in\[M\],\(28\)where we recall that𝔹∗​\(τ\):=\{W∈𝕊d1∣∥W∥∗≤τ\}\\mathbb\{B\}\_\{\\ast\}\(\\tau\):=\\\{W\\in\\mathbb\{S\}^\{d\_\{1\}\}\\mid\\lVert W\\rVert\_\{\\ast\}\\leq\\tau\\\}is the nuclear\-norm ball in𝕊d1\\mathbb\{S\}^\{d\_\{1\}\}\. The rest of the proof follows from standard OMD analysis\. Since∇DΦβ​\(W∥Wt,m\)=∇Φβ​\(W\)−∇Φβ​\(Wt,m\)\\nabla D\_\{\\Phi\}^\{\\beta\}\(W\\\|W\_\{t,m\}\)=\\nabla\\Phi\_\{\\beta\}\(W\)\-\\nabla\\Phi\_\{\\beta\}\(W\_\{t,m\}\)\(by definition ofDΦβD\_\{\\Phi\}^\{\\beta\}in[Equation˜25](https://arxiv.org/html/2606.14929#A4.E25)\),[Equation˜28](https://arxiv.org/html/2606.14929#A4.E28)gives the first\-order optimality condition of

⟨η​G^t,m\+∇Φβ​\(Wt\+1,m\)−∇Φβ​\(Wt\),W−Wt\+1,m⟩F≥0,∀W∈𝔹∗​\(τ\)\.\\Bigl\\langle\\eta\\widehat\{G\}\_\{t,m\}\+\\nabla\\Phi\_\{\\beta\}\(W\_\{t\+1,m\}\)\-\\nabla\\Phi\_\{\\beta\}\(W\_\{t\}\),W\-W\_\{t\+1,m\}\\Bigr\\rangle\_\{F\}\\geq 0,\\quad\\forall W\\in\\mathbb\{B\}\_\{\\ast\}\(\\tau\)\.More specifically, for themm\-th parameter in the optimum, namelyWm∗∈𝔹∗​\(τ\)W\_\{m\}^\{\\ast\}\\in\\mathbb\{B\}\_\{\\ast\}\(\\tau\), we have

⟨η​G^t,m,Wt\+1,m−Wm∗⟩F\\displaystyle\\langle\\eta\\widehat\{G\}\_\{t,m\},W\_\{t\+1,m\}\-W\_\{m\}^\{\\ast\}\\rangle\_\{F\}≤⟨∇Φβ​\(Wt\+1,m\)−∇Φβ​\(Wt\),W−Wt\+1,m⟩F\\displaystyle\\leq\\Bigl\\langle\\nabla\\Phi\_\{\\beta\}\(W\_\{t\+1,m\}\)\-\\nabla\\Phi\_\{\\beta\}\(W\_\{t\}\),W\-W\_\{t\+1,m\}\\Bigr\\rangle\_\{F\}=DΦβ​\(Wm∗∥Wt,m\)−DΦβ​\(Wm∗∥Wt\+1,m\)−DΦβ​\(Wt\+1,m∥Wt,m\),\\displaystyle=D\_\{\\Phi\}^\{\\beta\}\(W\_\{m\}^\{\\ast\}\\\|W\_\{t,m\}\)\-D\_\{\\Phi\}^\{\\beta\}\(W\_\{m\}^\{\\ast\}\\\|W\_\{t\+1,m\}\)\-D\_\{\\Phi\}^\{\\beta\}\(W\_\{t\+1,m\}\\\|W\_\{t,m\}\),where the second step is the standard three\-point identity\(orabona2019modern, Lemma 6\.7\)\. Adding⟨η​G^t,m,Wt,m−Wt\+1,m⟩F\\langle\\eta\\widehat\{G\}\_\{t,m\},W\_\{t,m\}\-W\_\{t\+1,m\}\\rangle\_\{F\}on both sides and summing up fromt=1,2,…,Tt=1,2,\\ldots,T, we have

∑t=1T⟨G^t,m,Wt,m−Wm∗⟩F\\displaystyle\\sum\_\{t=1\}^\{T\}\\langle\\widehat\{G\}\_\{t,m\},W\_\{t,m\}\-W\_\{m\}^\{\\ast\}\\rangle\_\{F\}≤DΦβ​\(Wm∗∥W1,m\)−DΦβ​\(Wm∗∥Wt\+1,m\)η\\displaystyle\\leq\\frac\{D\_\{\\Phi\}^\{\\beta\}\(W\_\{m\}^\{\\ast\}\\\|W\_\{1,m\}\)\-D\_\{\\Phi\}^\{\\beta\}\(W\_\{m\}^\{\\ast\}\\\|W\_\{t\+1,m\}\)\}\{\\eta\}\+∑t=1T⟨η​G^t,m,Wt,m−Wt\+1,m⟩F−DΦβ​\(Wt\+1,m∥Wt,m\)η\.\\displaystyle\\quad\+\\sum\_\{t=1\}^\{T\}\\frac\{\\langle\\eta\\widehat\{G\}\_\{t,m\},W\_\{t,m\}\-W\_\{t\+1,m\}\\rangle\_\{F\}\-D\_\{\\Phi\}^\{\\beta\}\(W\_\{t\+1,m\}\\\|W\_\{t,m\}\)\}\{\\eta\}\.For the first term on the RHS, sinceW1,mW\_\{1,m\}is initialized as the all\-zero matrix \([Algorithm˜1](https://arxiv.org/html/2606.14929#alg1)\) and Bregman divergences are non\-negative for convex functions \(cf\.[Equations˜24](https://arxiv.org/html/2606.14929#A4.E24)and[25](https://arxiv.org/html/2606.14929#A4.E25)\), we have

DΦβ​\(Wm∗∥W1,m\)−DΦβ​\(Wm∗∥Wt\+1,m\)≤Φβ​\(Wm∗\)−Φβ​\(0\)\+0\\displaystyle\\quad D\_\{\\Phi\}^\{\\beta\}\(W\_\{m\}^\{\\ast\}\\\|W\_\{1,m\}\)\-D\_\{\\Phi\}^\{\\beta\}\(W\_\{m\}^\{\\ast\}\\\|W\_\{t\+1,m\}\)\\leq\\Phi\_\{\\beta\}\(W\_\{m\}^\{\\ast\}\)\-\\Phi\_\{\\beta\}\(0\)\+0=∑i=1dq\(λi​\(Wm∗\)​arcsinh⁡λi​\(Wm∗\)β−λi​\(Wm∗\)2\+β2\+β\)\\displaystyle=\\sum\_\{i=1\}^\{d\_\{q\}\}\\left\(\\lambda\_\{i\}\(W\_\{m\}^\{\\ast\}\)\\operatorname\{\\mathrm\{arcsinh\}\}\\frac\{\\lambda\_\{i\}\(W\_\{m\}^\{\\ast\}\)\}\{\\beta\}\-\\sqrt\{\\lambda\_\{i\}\(W\_\{m\}^\{\\ast\}\)^\{2\}\+\\beta^\{2\}\}\+\\beta\\right\)≤∑i=1dq\|λi​\(Wm∗\)\|​arcsinh⁡\|λi​\(Wm∗\)\|β≤∥Wm∥∗​log⁡3​∥Wm∥∗β,\\displaystyle\\leq\\sum\_\{i=1\}^\{d\_\{q\}\}\\lvert\\lambda\_\{i\}\(W\_\{m\}^\{\\ast\}\)\\rvert\\operatorname\{\\mathrm\{arcsinh\}\}\\frac\{\\lvert\\lambda\_\{i\}\(W\_\{m\}^\{\\ast\}\)\\rvert\}\{\\beta\}\\leq\\lVert W\_\{m\}\\rVert\_\{\\ast\}\\log\\frac\{3\\lVert W\_\{m\}\\rVert\_\{\\ast\}\}\{\\beta\},where the second to last step uses the fact thatarcsinh\\operatorname\{\\mathrm\{arcsinh\}\}is an odd function, and the last step usesx2\+β2\+x≤2\+1\\sqrt\{x^\{2\}\+\\beta^\{2\}\}\+x\\leq\\sqrt\{2\}\+1for\|x\|≤1\\lvert x\\rvert\\leq 1\(ghai2020exponentiated, Eq\. \(12\)\)and∥Wm∥∗:=∑i=1dq\|λi\(Wm∗\)\|\\lVert W\_\{m\}\\rVert\_\{\\ast\}:=\\sum\_\{i=1\}^\{d\_\{q\}\}\|\\lambda\_\{i\}\(W\_\{m\}^\{\\ast\}\)\\rvert\.

For the second term, by Fenchel\-Young inequality\(orabona2019modern, Lemma 6\.32\)and the block\-wise\(2​\(τ\+β​dq\)\)−1\\bigl\(2\(\\tau\+\\beta d\_\{q\}\)\\bigr\)^\{\-1\}\-strong convexity ofΦβ\\Phi\_\{\\beta\}\(proved in[Lemma˜12](https://arxiv.org/html/2606.14929#Thmtheorem12)\), we have

⟨η​G^t,m,Wt,m−Wt\+1,m⟩F−DΦβ​\(Wt\+1,m∥Wt,m\)≤∥η​G^t,m∥222​\(2​\(τ\+β​dq\)\)−1,\\langle\\eta\\widehat\{G\}\_\{t,m\},W\_\{t,m\}\-W\_\{t\+1,m\}\\rangle\_\{F\}\-D\_\{\\Phi\}^\{\\beta\}\(W\_\{t\+1,m\}\\\|W\_\{t,m\}\)\\leq\\frac\{\\lVert\\eta\\widehat\{G\}\_\{t,m\}\\rVert\_\{2\}^\{2\}\}\{2\\bigl\(2\(\\tau\+\\beta d\_\{q\}\)\\bigr\)^\{\-1\}\},where∥⋅∥2\\lVert\\cdot\\rVert\_\{2\}, the spectral norm of a matrix, is the dual norm of the nuclear norm∥⋅∥∗\\lVert\\cdot\\rVert\_\{\\ast\}\. Hence we have

∑t=1T⟨G^t,m,Wt,m−Wm∗⟩F≤∥Wm∗∥∗η​log⁡3​∥Wm∗∥∗β\+∑t=1T\(τ\+β​dq\)​η​∥G^t,m∥22,∀m∈\[M\]\.\\sum\_\{t=1\}^\{T\}\\langle\\widehat\{G\}\_\{t,m\},W\_\{t,m\}\-W\_\{m\}^\{\\ast\}\\rangle\_\{F\}\\leq\\frac\{\\lVert W\_\{m\}^\{\\ast\}\\rVert\_\{\\ast\}\}\{\\eta\}\\log\\frac\{3\\lVert W\_\{m\}^\{\\ast\}\\rVert\_\{\\ast\}\}\{\\beta\}\+\\sum\_\{t=1\}^\{T\}\(\\tau\+\\beta d\_\{q\}\)\\eta\\lVert\\widehat\{G\}\_\{t,m\}\\rVert\_\{2\}^\{2\},\\quad\\forall m\\in\[M\]\.Summing upm∈\[M\]m\\in\[M\], using the assumption that∥Wm∗∥∗≤τ\\lVert W\_\{m\}^\{\\ast\}\\rVert\_\{\\ast\}\\leq\\tau, and the second part of[Lemma˜2](https://arxiv.org/html/2606.14929#Thmtheorem2),

∑t=1T⟨𝑮^t,𝑾t−𝑾∗⟩F≤M​τη​log⁡3​τβ\+2​\(τ\+β​dq\)​η​T\.\\sum\_\{t=1\}^\{T\}\\Bigl\\langle\\widehat\{\\bm\{G\}\}\_\{t\},\\bm\{W\}\_\{t\}\-\\bm\{W\}^\{\\ast\}\\Bigr\\rangle\_\{F\}\\leq\\frac\{M\\tau\}\{\\eta\}\\log\\frac\{3\\tau\}\{\\beta\}\+2\(\\tau\+\\beta d\_\{q\}\)\\eta T\.\(29\)
By the definition of linearized policy regret in[Equation˜11](https://arxiv.org/html/2606.14929#S3.E11), settingτ=2​s\\tau=2s,β=2​s/dq\\beta=2s/d\_\{q\}, andη=\(M​log⁡dq\)/T\\eta=\\sqrt\{\(M\\log d\_\{q\}\)/T\}therefore gives

ℜ~T​\(Πquad\)=sup𝑾∗∈𝕎\[∑t=1T⟨𝔼t\[𝑮^t∣qt\],𝑾t−𝑾∗⟩F\]≤12​s​M​T​log⁡dq,\\widetilde\{\\mathfrak\{R\}\}\_\{T\}\(\\Pi\_\{\\text\{quad\}\}\)=\\sup\_\{\\bm\{W\}^\{\\ast\}\\in\\mathbb\{W\}\}\\left\[\\sum\_\{t=1\}^\{T\}\\Bigl\\langle\\operatornamewithlimits\{\\mathbb\{E\}\}\\nolimits\_\{t\}\[\\widehat\{\\bm\{G\}\}\_\{t\}\\mid q\_\{t\}\],\\bm\{W\}\_\{t\}\-\\bm\{W\}^\{\\ast\}\\Bigr\\rangle\_\{F\}\\right\]\\leq 12s\\sqrt\{MT\\log d\_\{q\}\},where we used the first part of[Lemma˜2](https://arxiv.org/html/2606.14929#Thmtheorem2)and also the assumption that∥Wm∗∥∗≤2​s\\lVert W\_\{m\}^\{\\ast\}\\rVert\_\{\\ast\}\\leq 2s,∀m\\forall m\. ∎

## Appendix EPractical Implementation of HPG

### E\.1Computational Cost Bound of HPG \([Theorem˜4](https://arxiv.org/html/2606.14929#Thmtheorem4)\)

###### Proof of[Theorem˜4](https://arxiv.org/html/2606.14929#Thmtheorem4)\.

By the standard property of Bregman divergence, the single\-step update of OMD in[Equation˜14](https://arxiv.org/html/2606.14929#S4.E14)is equivalent to the following two step procedure\(orabona2019modern, §6\.4\.3\):

∇Φβ​\(𝑾~t\+1\)=∇Φβ​\(𝑾t\)−η​𝑮^t,𝑾t\+1=argmin𝑾∈𝔹∗M​\(τ\)DΦβ​\(𝑾∥𝑾~t\+1\)\.\\displaystyle\\nabla\\Phi\_\{\\beta\}\(\\widetilde\{\\bm\{W\}\}\_\{t\+1\}\)=\\nabla\\Phi\_\{\\beta\}\(\\bm\{W\}\_\{t\}\)\-\\eta\\widehat\{\\bm\{G\}\}\_\{t\},\\quad\\bm\{W\}\_\{t\+1\}=\\operatornamewithlimits\{\\mathrm\{argmin\}\}\_\{\\bm\{W\}\\in\\mathbb\{B\}\_\{\\ast\}^\{M\}\(\\tau\)\}D\_\{\\Phi\}^\{\\beta\}\(\\bm\{W\}\\\|\\widetilde\{\\bm\{W\}\}\_\{t\+1\}\)\.\(30\)According to[Lemma˜12](https://arxiv.org/html/2606.14929#Thmtheorem12), both steps can be decomposed for each model\. Therefore, we fix a singlem∈\[M\]m\\in\[M\], and suppose we have the eigen\-decomposition ofWt,m∈𝕊dqW\_\{t,m\}\\in\\mathbb\{S\}^\{d\_\{q\}\}available:

Wt,m=Ut,m​diag⁡\(λt,m\)​Ut,m𝖳,∀t∈\[T\],W\_\{t,m\}=U\_\{t,m\}\\operatorname\{\\mathrm\{diag\}\}\(\\lambda\_\{t,m\}\)U\_\{t,m\}^\{\\mathsf\{T\}\},\\quad\\forall t\\in\[T\],\(31\)whereUt,m∈ℝdq×dqU\_\{t,m\}\\in\\mathbb\{R\}^\{d\_\{q\}\\times d\_\{q\}\}andλt,m∈ℝdq\\lambda\_\{t,m\}\\in\\mathbb\{R\}^\{d\_\{q\}\}\. We now prove that we can efficiently compute the eigen\-decomposition ofWt\+1,mW\_\{t\+1,m\}, defined in[Equation˜30](https://arxiv.org/html/2606.14929#A5.E30), via the following steps:

1. 1\.ConvertWt\\bm\{W\}\_\{t\}to Mirror Space\.We findYt,m=∇Φβ​\(Wt,m\)Y\_\{t,m\}=\\nabla\\Phi\_\{\\beta\}\(W\_\{t,m\}\)\. As defined in[Equation˜26](https://arxiv.org/html/2606.14929#A4.E26), we have Yt,m=Ut,m​diag⁡\(γt,m\)​Ut,m𝖳,γt,m,i=arcsinh⁡\(λt,m,i/β\),∀i∈\[dq\]\.Y\_\{t,m\}=U\_\{t,m\}\\operatorname\{\\mathrm\{diag\}\}\(\\gamma\_\{t,m\}\)U\_\{t,m\}^\{\\mathsf\{T\}\},\\quad\\gamma\_\{t,m,i\}=\\operatorname\{\\mathrm\{arcsinh\}\}\(\\lambda\_\{t,m,i\}/\\beta\),\\penalty 10000\\ \\forall i\\in\[d\_\{q\}\]\.\(32\)This element\-wise update on thedqd\_\{q\}eigenvalues takes𝒪⁡\(dq\)\\operatorname\{\\mathcal\{O\}\}\(d\_\{q\}\)time\.
2. 2\.Gradient Descent Update\.In the mirror space, we perform gradient descentY~t\+1,m=Yt,m−η​G^t,m\\widetilde\{Y\}\_\{t\+1,m\}=Y\_\{t,m\}\-\\eta\\widehat\{G\}\_\{t,m\}and obtain the eigen\-decomposition ofY~t\+1,m\\widetilde\{Y\}\_\{t\+1,m\}\. SinceG^t,m\\widehat\{G\}\_\{t,m\}is parallel toqt​qt𝖳q\_\{t\}q\_\{t\}^\{\\mathsf\{T\}\}, it is a rank\-one matrix \(see[Equation˜15](https://arxiv.org/html/2606.14929#S4.E15)\)\. Therefore, eigen\-decomposingY~t\+1,m\\widetilde\{Y\}\_\{t\+1,m\}based on that ofYt,mY\_\{t,m\}in[Equation˜32](https://arxiv.org/html/2606.14929#A5.E32)only takes𝒪⁡\(dq2\)\\operatorname\{\\mathcal\{O\}\}\(d\_\{q\}^\{2\}\)time\(see, e\.g\.,bunch1978rank,gu1994stable\): Y~t\+1,m=Ut\+1,m​diag⁡\(γ~t\+1,m\)​Ut\+1,m𝖳,\\widetilde\{Y\}\_\{t\+1,m\}=U\_\{t\+1,m\}\\operatorname\{\\mathrm\{diag\}\}\(\\widetilde\{\\gamma\}\_\{t\+1,m\}\)U\_\{t\+1,m\}^\{\\mathsf\{T\}\},\(33\)whereUt\+1,m∈ℝdq×dqU\_\{t\+1,m\}\\in\\mathbb\{R\}^\{d\_\{q\}\\times d\_\{q\}\}andγ~t\+1,m∈ℝdq\\widetilde\{\\gamma\}\_\{t\+1,m\}\\in\\mathbb\{R\}^\{d\_\{q\}\}\.
3. 3\.ConvertY~t\+1\\widetilde\{\\bm\{Y\}\}\_\{t\+1\}to Primal Space\.LetW~t\+1,m=\(∇Φβ\)−1​\(Y~t\+1,m\)\\widetilde\{W\}\_\{t\+1,m\}=\(\\nabla\\Phi\_\{\\beta\}\)^\{\-1\}\(\\widetilde\{Y\}\_\{t\+1,m\}\)\. Using[Lemma˜10](https://arxiv.org/html/2606.14929#Thmtheorem10)again, it is equivalent to applying the map\(ϕβ\)−1​\(y\)=β​sinh⁡\(y\)\(\\phi\_\{\\beta\}\)^\{\-1\}\(y\)=\\beta\\sinh\(y\)to all the eigenvalues ofY~t\+1,m\\widetilde\{Y\}\_\{t\+1,m\}\. Therefore, from[Equation˜33](https://arxiv.org/html/2606.14929#A5.E33), we obtain the eigen\-decomposition ofW~t\+1,m\\widetilde\{W\}\_\{t\+1,m\}in𝒪⁡\(dq\)\\operatorname\{\\mathcal\{O\}\}\(d\_\{q\}\)time as W~t\+1,m=Ut\+1,m​diag⁡\(λ~t\+1,m\)​Ut\+1,m𝖳,λ~t\+1,m,i=β​sinh⁡\(γ~t\+1,m,i\),∀i∈\[dq\]\.\\widetilde\{W\}\_\{t\+1,m\}=U\_\{t\+1,m\}\\operatorname\{\\mathrm\{diag\}\}\(\\widetilde\{\\lambda\}\_\{t\+1,m\}\)U\_\{t\+1,m\}^\{\\mathsf\{T\}\},\\quad\\widetilde\{\\lambda\}\_\{t\+1,m,i\}=\\beta\\sinh\(\\widetilde\{\\gamma\}\_\{t\+1,m,i\}\),\\penalty 10000\\ \\forall i\\in\[d\_\{q\}\]\.\(34\)
4. 4\.Projection onto𝔹∗​\(τ\)\\mathbb\{B\}\_\{\\ast\}\(\\tau\)based onDΦβD\_\{\\Phi\}^\{\\beta\}\.Expanding the Bregman divergence defined in[Equation˜25](https://arxiv.org/html/2606.14929#A4.E25), the projection step in[Equation˜30](https://arxiv.org/html/2606.14929#A5.E30)minimizes DΦβ​\(W∥W~t\+1,m\)=Φβ​\(W\)−Φβ​\(W~t\+1,m\)\+⟨∇Φβ​\(W~t\+1,m\),W−W~t\+1,m⟩F\.D\_\{\\Phi\}^\{\\beta\}\(W\\\|\\widetilde\{W\}\_\{t\+1,m\}\)=\\Phi\_\{\\beta\}\(W\)\-\\Phi\_\{\\beta\}\(\\widetilde\{W\}\_\{t\+1,m\}\)\+\\bigl\\langle\\nabla\\Phi\_\{\\beta\}\(\\widetilde\{W\}\_\{t\+1,m\}\),W\-\\widetilde\{W\}\_\{t\+1,m\}\\bigr\\rangle\_\{F\}\.Removing all terms independent toWWand recalling thatY~t\+1,m=∇Φβ​\(W~t\+1,m\)\\widetilde\{Y\}\_\{t\+1,m\}=\\nabla\\Phi\_\{\\beta\}\(\\widetilde\{W\}\_\{t\+1,m\}\), we write Wt\+1,m=argminW∈𝔹∗​\(τ\)\(Φβ​\(W\)−⟨Y~t\+1,m,W⟩F\)\\displaystyle\\quad W\_\{t\+1,m\}=\\operatornamewithlimits\{\\mathrm\{argmin\}\}\_\{W\\in\\mathbb\{B\}\_\{\\ast\}\(\\tau\)\}\\left\(\\Phi\_\{\\beta\}\(W\)\-\\bigl\\langle\\widetilde\{Y\}\_\{t\+1,m\},W\\bigr\\rangle\_\{F\}\\right\)=argmin∥λ∥1≤τargminU𝖳​U=I\(∑i=1dqϕβ​\(λi\)−⟨Ut\+1,m​diag⁡\(γ~t\+1,m\)​Ut\+1,m𝖳,U​diag⁡\(λ\)​U𝖳⟩F\),\\displaystyle=\\operatornamewithlimits\{\\mathrm\{argmin\}\}\_\{\\lVert\\lambda\\rVert\_\{1\}\\leq\\tau\}\\operatornamewithlimits\{\\mathrm\{argmin\}\}\_\{U^\{\\mathsf\{T\}\}U=I\}\\left\(\\sum\_\{i=1\}^\{d\_\{q\}\}\\phi\_\{\\beta\}\(\\lambda\_\{i\}\)\-\\bigl\\langle U\_\{t\+1,m\}\\operatorname\{\\mathrm\{diag\}\}\(\\widetilde\{\\gamma\}\_\{t\+1,m\}\)U\_\{t\+1,m\}^\{\\mathsf\{T\}\},U\\operatorname\{\\mathrm\{diag\}\}\(\\lambda\)U^\{\\mathsf\{T\}\}\\bigr\\rangle\_\{F\}\\right\),where we used the fact that any symmetric matrixW∈𝔹∗​\(τ\)W\\in\\mathbb\{B\}\_\{\\ast\}\(\\tau\)can be written asU​diag⁡\(λ\)​U𝖳U\\operatorname\{\\mathrm\{diag\}\}\(\\lambda\)U^\{\\mathsf\{T\}\}with∥λ∥1≤τ\\lVert\\lambda\\rVert\_\{1\}\\leq\\tau\(definition of nuclear norm\) andU​U𝖳=IUU^\{\\mathsf\{T\}\}=I\(definition of orthogonal matrix\)\. Fixingλ∈ℝdq\\lambda\\in\\mathbb\{R\}^\{d\_\{q\}\}, apply the trace inequality in[Lemma˜8](https://arxiv.org/html/2606.14929#Thmtheorem8)to the second term: the inner product is at most⟨γ~t\+1,m,λ⟩\\langle\\widetilde\{\\gamma\}\_\{t\+1,m\},\\lambda\\rangle, with equality attained if and only ifU=Ut\+1,mU=U\_\{t\+1,m\}\. Therefore, we find argmin∥λ∥1≤τ\(∑t=1dq\(ϕβ​\(λi\)−γ~t\+1,m,i​λi\)\)\.\\operatornamewithlimits\{\\mathrm\{argmin\}\}\_\{\\lVert\\lambda\\rVert\_\{1\}\\leq\\tau\}\\left\(\\sum\_\{t=1\}^\{d\_\{q\}\}\(\\phi\_\{\\beta\}\(\\lambda\_\{i\}\)\-\\widetilde\{\\gamma\}\_\{t\+1,m,i\}\\lambda\_\{i\}\)\\right\)\.For eachi∈\[dq\]i\\in\[d\_\{q\}\], minimizing this is equivalent to minimizing the Bregman divergence induced byϕβ\\phi\_\{\\beta\}\(again, writing out the definition and removing all terms independent toλi\\lambda\_\{i\}\)\. This gives Wt\+1,m=Ut\+1,m​diag⁡\(λt\+1,m\)​Ut\+1,m𝖳,λt\+1,m=argmin∥λ∥1≤τ​∑i=1dqDϕβ​\(λi∥λ~t\+1,m,i\),W\_\{t\+1,m\}=U\_\{t\+1,m\}\\operatorname\{\\mathrm\{diag\}\}\(\\lambda\_\{t\+1,m\}\)U\_\{t\+1,m\}^\{\\mathsf\{T\}\},\\quad\\lambda\_\{t\+1,m\}=\\operatornamewithlimits\{\\mathrm\{argmin\}\}\_\{\\lVert\\lambda\\rVert\_\{1\}\\leq\\tau\}\\sum\_\{i=1\}^\{d\_\{q\}\}D\_\{\\phi\}^\{\\beta\}\(\\lambda\_\{i\}\\\|\\widetilde\{\\lambda\}\_\{t\+1,m,i\}\),\(35\)as claimed in the main text \([Equation˜17](https://arxiv.org/html/2606.14929#S5.E17)\)\. This is implementable in𝒪⁡\(dq​log⁡dq\)\\operatorname\{\\mathcal\{O\}\}\(d\_\{q\}\\log d\_\{q\}\)time as follows: By symmetry, the optimalλi\\lambda\_\{i\}must share the same sign asγ~t\+1,m,i\\widetilde\{\\gamma\}\_\{t\+1,m,i\}\. Letxi=\|λi\|x\_\{i\}=\|\\lambda\_\{i\}\|andzi=\|γ~t\+1,m,i\|z\_\{i\}=\|\\widetilde\{\\gamma\}\_\{t\+1,m,i\}\|, minxi≥0​∑i=1dq\(ϕβ​\(xi\)−zi​xi\)​subject to​∑i=1dqxi≤τ\.\\min\_\{x\_\{i\}\\geq 0\}\\sum\_\{i=1\}^\{d\_\{q\}\}\\left\(\\phi\_\{\\beta\}\(x\_\{i\}\)\-z\_\{i\}x\_\{i\}\\right\)\\text\{ subject to \}\\sum\_\{i=1\}^\{d\_\{q\}\}x\_\{i\}\\leq\\tau\.Introducing a Lagrange multiplierν≥0\\nu\\geq 0for the sum constraint\. Given any multiplierν\\nu, ϕβ′​\(xi\)−zi\+ν≥0⟹xi​\(ν\)=β​max⁡\(sinh⁡\(zi−ν\),0\),\\phi\_\{\\beta\}^\{\\prime\}\(x\_\{i\}\)\-z\_\{i\}\+\\nu\\geq 0\\Longrightarrow x\_\{i\}\(\\nu\)=\\beta\\max\\Bigl\(\\sinh\(z\_\{i\}\-\\nu\),0\\Bigr\),\(36\)and the optimalν∗\\nu^\{\\ast\}is the unique non\-negative number satisfying∑i=1dqxi​\(ν\)≤τ\\sum\_\{i=1\}^\{d\_\{q\}\}x\_\{i\}\(\\nu\)\\leq\\tau\. Sincesinh\\sinhis monotone,ν∗\\nu^\{\\ast\}is found after sorting\{zi\}i\\\{z\_\{i\}\\\}\_\{i\}in𝒪⁡\(dq​log⁡dq\)\\operatorname\{\\mathcal\{O\}\}\(d\_\{q\}\\log d\_\{q\}\)time\. This givesxi​\(ν∗\)x\_\{i\}\(\\nu^\{\\ast\}\)’s and[Equation˜35](https://arxiv.org/html/2606.14929#A5.E35)\.

Therefore, we have proved that moving from the eigen\-decomposition ofWt,mW\_\{t,m\}in[Equation˜31](https://arxiv.org/html/2606.14929#A5.E31)to that ofWt\+1,mW\_\{t\+1,m\}in[Equation˜35](https://arxiv.org/html/2606.14929#A5.E35)takes𝒪⁡\(dq\+dq2\+dq\+dq​log⁡dq\)=𝒪⁡\(dq2\)\\operatorname\{\\mathcal\{O\}\}\(d\_\{q\}\+d\_\{q\}^\{2\}\+d\_\{q\}\+d\_\{q\}\\log d\_\{q\}\)=\\operatorname\{\\mathcal\{O\}\}\(d\_\{q\}^\{2\}\)time\. Since there areMMmodels to update in each round, this gives the claimed per\-round complexity bound of𝒪⁡\(dq2​M\)\\operatorname\{\\mathcal\{O\}\}\(d\_\{q\}^\{2\}M\)\. ∎

In practice, one can sharpen the𝒪⁡\(dq2​M\)\\operatorname\{\\mathcal\{O\}\}\(d\_\{q\}^\{2\}M\)bound via approximation:[Equation˜36](https://arxiv.org/html/2606.14929#A5.E36)induces a low\-rank structure, because the sum ofxi​\(ν∗\)x\_\{i\}\(\\nu^\{\\ast\}\)’s cannot exceedτ\\tau\. Therefore, a good approximation of HPG algorithm is only keeping the top\-τ\\taueigenvalues ofWt\+1,mW\_\{t\+1,m\}\. This makesλt\+1,m\\lambda\_\{t\+1,m\}τ\\tau\-dimensional andUt\+1,mU\_\{t\+1,m\}in the shape ofdq×τd\_\{q\}\\times\\tau\. The rank\-one eigen\-update in[Equation˜33](https://arxiv.org/html/2606.14929#A5.E33)is then solvable in𝒪⁡\(τ​dq\)\\operatorname\{\\mathcal\{O\}\}\(\\tau d\_\{q\}\)time\. Under theτ≈s\\tau\\approx sconfiguration in[Theorem˜3](https://arxiv.org/html/2606.14929#Thmtheorem3), this only takes𝒪⁡\(s​dq​M\)\\operatorname\{\\mathcal\{O\}\}\(sd\_\{q\}M\)time per round\.

### E\.2Parameter\-Free Implementation of HPG \([Theorem˜5](https://arxiv.org/html/2606.14929#Thmtheorem5)\)

Algorithm 2Parameter\-Free Hypentropy Policy Gradient1:InitializeMM1D “coin\-betting” algorithms\(cutkosky2018black, Algorithm 1\)

2:Initialize a HPG algorithm withτ=1,β=dq−1\\tau=1,\\beta=d\_\{q\}^\{\-1\}, andη=\(M​log⁡dq\)/T\\eta=\\sqrt\{\(M\\log d\_\{q\}\)/T\}\([Algorithm˜1](https://arxiv.org/html/2606.14929#alg1)\)

3:fort=1,2,…,Tt=1,2,\\ldots,Tdo

4:Call each coin\-betting algorithm forzt,1,zt,2,…,zt,M∈ℝz\_\{t,1\},z\_\{t,2\},\\ldots,z\_\{t,M\}\\in\\mathbb\{R\}

5:Call HPG algorithm for a𝒘t=diag⁡\(wt,1,wt,2,…,wt,M\)∈𝔹∗M​\(1\)\\bm\{w\}\_\{t\}=\\operatorname\{\\mathrm\{diag\}\}\(w\_\{t,1\},w\_\{t,2\},\\ldots,w\_\{t,M\}\)\\in\\mathbb\{B\}\_\{\\ast\}^\{M\}\(1\)

6:Play according to the parameter𝑾t=diag⁡\(zt,1​wt,1,zt,2​wt,2,…,zt,M​wt,M\)∈𝕎\\bm\{W\}\_\{t\}=\\operatorname\{\\mathrm\{diag\}\}\(z\_\{t,1\}w\_\{t,1\},z\_\{t,2\}w\_\{t,2\},\\ldots,z\_\{t,M\}w\_\{t,M\}\)\\in\\mathbb\{W\}

7:Let𝑮^t=diag⁡\(G^t,1,G^t,2,…,G^t,M\)\\widehat\{\\bm\{G\}\}\_\{t\}=\\operatorname\{\\mathrm\{diag\}\}\(\\widehat\{G\}\_\{t,1\},\\widehat\{G\}\_\{t,2\},\\ldots,\\widehat\{G\}\_\{t,M\}\)be the gradient estimator in[Equation˜15](https://arxiv.org/html/2606.14929#S4.E15)

8:For eachm∈\[M\]m\\in\[M\], pass⟨G^t,m,wt,m⟩F\\langle\\widehat\{G\}\_\{t,m\},w\_\{t,m\}\\rangle\_\{F\}to themm\-th coin\-betting algorithm

9:Pass𝑮^t\\widehat\{\\bm\{G\}\}\_\{t\}to the HPG algorithm as the gradient for the OMD step[Equation˜14](https://arxiv.org/html/2606.14929#S4.E14)

In order to implement the HPG algorithm without knowing sparsity parameterssor the nuclear\-norm parameterτ=maxm∥Wm∗∥∗\\tau=\\max\_\{m\}\\lVert W\_\{m\}^\{\\ast\}\\rVert\_\{\\ast\}, we utilize the parameter\-free online learning technique bycutkosky2018black\. They provide a general framework for online linear optimization in any Banach space \(a vector space with norm, e\.g\., our𝕊n\\mathbb\{S\}^\{n\}equipped with the nuclear norm\)\.

In our context, given the direct sum property in[Lemma˜12](https://arxiv.org/html/2606.14929#Thmtheorem12), we consider a single expertm∈\[M\]m\\in\[M\]\. We now work on thedq2d\_\{q\}^\{2\}\-dimensional vector space equipped with nuclear norm∥⋅∥∗\\lVert\\cdot\\rVert\_\{\\ast\}\. The action in roundttisWt,m∈𝕊dqW\_\{t,m\}\\in\\mathbb\{S\}^\{d\_\{q\}\}, and the loss vector \(from[Equation˜11](https://arxiv.org/html/2606.14929#S3.E11)\) in roundttisGt,m:=∂∂Wm​ℒt​\(𝑾t\)G\_\{t,m\}:=\\frac\{\\partial\}\{\\partial W\_\{m\}\}\\mathcal\{L\}\_\{t\}\(\\bm\{W\}\_\{t\}\)\. The \(unexpected\) regret w\.r\.t\. anyWm0∈𝕊dqW\_\{m\}^\{0\}\\in\\mathbb\{S\}^\{d\_\{q\}\}isRT,m​\(Wm0\):=∑t⟨Gt,m,Wt,m−Wm0⟩FR\_\{T,m\}\(W\_\{m\}^\{0\}\):=\\sum\_\{t\}\\langle G\_\{t,m\},W\_\{t,m\}\-W\_\{m\}^\{0\}\\rangle\_\{F\}\.

cutkosky2018blackdecomposesWt,mW\_\{t,m\}into two parts: a magnitudezt,m=∥Wt,m∥∗z\_\{t,m\}=\\lVert W\_\{t,m\}\\rVert\_\{\\ast\}and a directionwt,m=Wt,m∥Wt,m∥∗w\_\{t,m\}=\\frac\{W\_\{t,m\}\}\{\\lVert W\_\{t,m\}\\rVert\_\{\\ast\}\}\. The decision ofzt,mz\_\{t,m\}is an one\-dimensional decision making overℝ\\mathbb\{R\}, and can be done via the*coin\-betting*algorithm oforabona2016coin\. For the directionwt,mw\_\{t,m\}, which always has norm 1, our HPG algorithm over𝔹∗​\(1\)\\mathbb\{B\}\_\{\\ast\}\(1\)attains good regret\. This gives[Algorithm˜2](https://arxiv.org/html/2606.14929#alg2)\.

###### Proof of[Theorem˜5](https://arxiv.org/html/2606.14929#Thmtheorem5)\.

For the optimal𝑾∗∈𝕎\\bm\{W\}^\{\\ast\}\\in\\mathbb\{W\}such that∥Wm∗∥∗≤2​s\\lVert W\_\{m\}^\{\\ast\}\\rVert\_\{\\ast\}\\leq 2s,∀m\\forall m, we have for anymm:

∑t=1T⟨Gt,m,Wt,m−Wm∗⟩F=∑t=1T\(⟨Gt,m,zt,m​wt,m⟩F−⟨Gt,m,Wm∗⟩F\)\\displaystyle\\quad\\sum\_\{t=1\}^\{T\}\\langle G\_\{t,m\},W\_\{t,m\}\-W\_\{m\}^\{\\ast\}\\rangle\_\{F\}=\\sum\_\{t=1\}^\{T\}\\Bigl\(\\langle G\_\{t,m\},z\_\{t,m\}w\_\{t,m\}\\rangle\_\{F\}\-\\langle G\_\{t,m\},W\_\{m\}^\{\\ast\}\\rangle\_\{F\}\\Bigr\)=∑t=1T\(zt,m​⟨Gt,m,wt,m⟩F−∥Wm∗∥∗​⟨Gt,m,wt,m⟩F\)\+∑t=1T\(∥Wm∗∥∗​⟨Gt,m,wt,m⟩F−⟨Gt,m,Wm∗⟩F\)\.\\displaystyle=\\sum\_\{t=1\}^\{T\}\\Bigl\(z\_\{t,m\}\\langle G\_\{t,m\},w\_\{t,m\}\\rangle\_\{F\}\-\\lVert W\_\{m\}^\{\\ast\}\\rVert\_\{\\ast\}\\langle G\_\{t,m\},w\_\{t,m\}\\rangle\_\{F\}\\Bigr\)\+\\sum\_\{t=1\}^\{T\}\\Bigl\(\\lVert W\_\{m\}^\{\\ast\}\\rVert\_\{\\ast\}\\langle G\_\{t,m\},w\_\{t,m\}\\rangle\_\{F\}\-\\langle G\_\{t,m\},W\_\{m\}^\{\\ast\}\\rangle\_\{F\}\\Bigr\)\.
The first term is the 1D online learning regret ofzt,mz\_\{t,m\}w\.r\.t\.∥Wm∗∥∗\\lVert W\_\{m\}^\{\\ast\}\\rVert\_\{\\ast\}, with the round\-ttloss defined asgt,m:=⟨Gt,m,wt,m⟩Fg\_\{t,m\}:=\\langle G\_\{t,m\},w\_\{t,m\}\\rangle\_\{F\}\. We know\|gt,m\|≤∥Gt,m∥2​∥wt,m∥∗≤1\\lvert g\_\{t,m\}\\rvert\\leq\\lVert G\_\{t,m\}\\rVert\_\{2\}\\lVert w\_\{t,m\}\\rVert\_\{\\ast\}\\leq 1\(see[Lemma˜2](https://arxiv.org/html/2606.14929#Thmtheorem2)\)\. According to the coin\-betting guarantee\(cutkosky2018black, Theorem 1\), this 1D regret is bounded by

∑m=1M∑t=1T\(zt,m−∥Wm∗∥∗\)​⟨Gt,m,wt,m⟩F=∑m=1M𝒪⁡\(∥Wm∗∥∗​T​log⁡\(∥Wm∗∥∗​T\)\)\.\\sum\_\{m=1\}^\{M\}\\sum\_\{t=1\}^\{T\}\\bigl\(z\_\{t,m\}\-\\lVert W\_\{m\}^\{\\ast\}\\rVert\_\{\\ast\}\\bigr\)\\langle G\_\{t,m\},w\_\{t,m\}\\rangle\_\{F\}=\\sum\_\{m=1\}^\{M\}\\operatorname\{\\mathcal\{O\}\}\\left\(\\lVert W\_\{m\}^\{\\ast\}\\rVert\_\{\\ast\}\\sqrt\{T\}\\log\\bigl\(\\lVert W\_\{m\}^\{\\ast\}\\rVert\_\{\\ast\}T\\bigr\)\\right\)\.
The second term, on the other hand, is∥Wm∗∥∗\\lVert W\_\{m\}^\{\\ast\}\\rVert\_\{\\ast\}times the HPG regret w\.r\.t\.Wm∗∥Wm∗∥∗∈𝔹∗​\(1\)\\frac\{W\_\{m\}^\{\\ast\}\}\{\\lVert W\_\{m\}^\{\\ast\}\\rVert\_\{\\ast\}\}\\in\\mathbb\{B\}\_\{\\ast\}\(1\)\. Using[Theorem˜3](https://arxiv.org/html/2606.14929#Thmtheorem3)withτ=1\\tau=1,β=1/dq\\beta=1/d\_\{q\}, andη=\(M​log⁡dq\)/T\\eta=\\sqrt\{\(M\\log d\_\{q\}\)/T\}, we have

∑m=1M\(∥Wm∗∥∗⟨Gt,m,wt,m⟩F−⟨Gt,m,Wm∗⟩F\)≤maxm∈\[M\]∥Wm∗∥∗×𝒪\(M​T​log⁡dq\)\.\\sum\_\{m=1\}^\{M\}\\Bigl\(\\lVert W\_\{m\}^\{\\ast\}\\rVert\_\{\\ast\}\\langle G\_\{t,m\},w\_\{t,m\}\\rangle\_\{F\}\-\\langle G\_\{t,m\},W\_\{m\}^\{\\ast\}\\rangle\_\{F\}\\Bigr\)\\leq\\max\_\{m\\in\[M\]\}\\lVert W\_\{m\}^\{\\ast\}\\rVert\_\{\\ast\}\\times\\operatorname\{\\mathcal\{O\}\}\\bigl\(\\sqrt\{MT\\log d\_\{q\}\}\\bigr\)\.Putting two parts together and using the assumption that∥Wm∗∥∗≤2​s\\lVert W\_\{m\}^\{\\ast\}\\rVert\_\{\\ast\}\\leq 2s,∀m\\forall m, we hence have

ℜ~T​\(Πquad\)=𝔼\[∑t=1T⟨∇ℒt​\(𝑾t\),𝑾t−𝑾∗⟩F\]=𝒪⁡\(M​s​T​log⁡\(s​T\)\+s​M​T​log⁡dq\)\.\\widetilde\{\\mathfrak\{R\}\}\_\{T\}\(\\Pi\_\{\\text\{quad\}\}\)=\\operatornamewithlimits\{\\mathbb\{E\}\}\\left\[\\sum\_\{t=1\}^\{T\}\\Bigl\\langle\\nabla\\mathcal\{L\}\_\{t\}\(\\bm\{W\}\_\{t\}\),\\bm\{W\}\_\{t\}\-\\bm\{W\}^\{\\ast\}\\Bigr\\rangle\_\{F\}\\right\]=\\operatorname\{\\mathcal\{O\}\}\\Bigl\(Ms\\sqrt\{T\}\\log\(sT\)\+s\\sqrt\{MT\\log d\_\{q\}\}\\Bigr\)\.This proves thatℜ~T​\(Πquad\)=𝒪⁡\(s​M​T​log⁡\(dq​T\)\)\\widetilde\{\\mathfrak\{R\}\}\_\{T\}\(\\Pi\_\{\\text\{quad\}\}\)=\\operatorname\{\\mathcal\{O\}\}\(sM\\sqrt\{T\}\\log\(d\_\{q\}T\)\)\(recall from[Section˜2\.2](https://arxiv.org/html/2606.14929#S2.SS2)thats≤dqs\\leq d\_\{q\}\)\. ∎