Online Learning with LLM Experts from Limited Feedback

# Online Learning with LLM Experts from Limited Feedback
Source: [https://arxiv.org/html/2609.05820](https://arxiv.org/html/2609.05820)
Soumyabrata PalAffiliation:Adobe ResearchEmail:[hdardiry@vt\.edu](mailto:)Koyel MukherjeeAffiliation:Adobe ResearchFranck DernoncourtAffiliation:Adobe ResearchRyan A\. RossiAffiliation:Adobe ResearchBranislav KvetonAffiliation:Adobe ResearchHoda Eldardiry††thanks:Corresponding author\.Affiliation:Virginia Tech

###### Abstract

We study adaptive routing of prompts to large language model \(LLM\) experts to maximize response quality in an online setting with limited feedback\. We formulate it as a bandit problem withKKactions that represent experts andddfeatures that encode prompts, over a horizon ofTTrounds\. We propose algorithms that strategically select and observe rewards to minimize regret\. In the full\-information setting, we achieve a regret ofO~​\(d​T/m\)\\tilde\{O\}\(dT/\\sqrt\{m\}\), while in the bandit setting we achieveO~​\(d​T​K/m\)\\tilde\{O\}\(dT\\sqrt\{K/m\}\), wherem≪Tm\\ll Tis a budget on feedback\. Our experiments show that we efficiently learn high\-quality routing strategies across diverse LLMs from limited feedback\.

## 1Introduction

*Large language models \(LLMs\)*are pervasive nowadays\. OpenAI’s GPT models\([OpenAI et al\., 2023](https://arxiv.org/html/2609.05820#bib.bib13)\), LLaMA3\([Dubey et al\., 2024](https://arxiv.org/html/2609.05820#bib.bib12)\), and Mistral AI\([Mistral AI, 2025](https://arxiv.org/html/2609.05820#bib.bib14)\)have been successfully used to solve many tasks, such as document processing and code generation\. Different LLMs have different costs and capabilities\([Artificial Analysis, 2025](https://arxiv.org/html/2609.05820#bib.bib16)\)\. The diversity of costs, even within the same family of models, can be stark\([OpenAI, 2025](https://arxiv.org/html/2609.05820#bib.bib15)\)\. The diverse capabilities of LLMs are obvious from public datasets\. For instance, the Nectar dataset\([Zhu et al\., 2024](https://arxiv.org/html/2609.05820#bib.bib56)\)contains responses to183183k prompts of many popular models judged by GPT\-4\. When GPT\-3\.5\-Turbo, GPT\-3\.5\-Turbo\-Instruct, GPT\-4, GPT\-4\-0613, LLaMA\-2\-7B\-Chat, and Mistral\-7B\-Instruct are judged, the win rates of the models are0\.1820\.182,0\.0910\.091,0\.2030\.203,0\.3190\.319,0\.0730\.073, and0\.1320\.132\. Therefore, no model dominates the others more than a third of the time and adaptation is beneficial\.

We formulate the problem of online learning with*LLM experts*as follows\. We haveKKdifferent LLMs and interact with them sequentially overTTrounds\. In each round, a prompt arrives and we route it to one expert, conditioned on the prompt\. The expert responds and its response is associated with some reward, which is unobserved\. This is because the responses of LLMs are generally not evaluated by their users\. Our goal is to learn to route each prompt to the expert with the highest mean reward\. This is impossible without feedback\. Therefore, we make a realistic assumption that we get access to limited feedback that is as good as that from humans\. This could be human feedback or a stronger LLM used as an*LLM judge*\([Li et al\., 2024b](https://arxiv.org/html/2609.05820#bib.bib21);[Li et al\., 2024a](https://arxiv.org/html/2609.05820#bib.bib20);[LLM\-as\-a\-Judge, 2025](https://arxiv.org/html/2609.05820#bib.bib19)\)\. This feedback is expensive, either because of human labor or computation cost, and thus we can only use itm≪Tm\\ll Ttimes, wheremmis determined by the available budget\. The tradeoff between rewards and feedback is not clear a priori\. Therefore, we maximize rewards under the constraint on feedback rather than a linear combination of the two quantities\. Finally, this problem is inherently online since user prompts are revealed only upon interaction, making offline solutions infeasible\. Routing decisions must be made sequentially in real time, with no prior knowledge of the prompt distribution\.

We solve our problem as a*contextual bandit*\([Langford and Zhang, 2008](https://arxiv.org/html/2609.05820#bib.bib37);[Li et al\., 2010](https://arxiv.org/html/2609.05820#bib.bib40);[Lattimore and Szepesvari, 2019](https://arxiv.org/html/2609.05820#bib.bib52)\)withKKexperts, where each LLM is an expert and the context is an embedding of the prompt\. The main difference from all prior work on contextual bandits is that only*mmrewards out ofTTcan be observed*\. The agent can decide*what to observe*and*when to observe it*, as long as it could have observed it before\. The main challenge in the algorithm design is doing it at a near\-optimal rate in a regret minimization setting\. The control over what to observe and when to observe it differentiates our work from other bandit settings that involve partial observations and we discuss these extensively in[AppendixC](https://arxiv.org/html/2609.05820#A3)\. The online setting with limited feedback on LLM response quality differentiates our work from prior LLM optimization approaches, which are typically studied in offline settings or do not directly optimize response quality\. We also discuss them in[AppendixC](https://arxiv.org/html/2609.05820#A3)\. We make the following contributions:

1. 1\.We study the full\-information setting \([Section3](https://arxiv.org/html/2609.05820#S3)\), where the agent can observe the rewards of all experts in any past round\. The key idea in our algorithm is to progressively observe rewards of the experts with the highest information gain\. The algorithm is computationally efficient and its regret isO~​\(d​T/m\)\\tilde\{O\}\(dT/\\sqrt\{m\}\), which matches our lower bound up tod\\sqrt\{d\}\. Note that the bound isO~​\(T\)\\tilde\{O\}\(\\sqrt\{T\}\)whenm=Ω⁡\(T\)m=\\Omega\(T\)\.
2. 2\.We also study the bandit setting \([Section4](https://arxiv.org/html/2609.05820#S4)\), where the agent can only observe at a certain round the reward of the expert who has generated the response for that round\. The key idea in our algorithm is to progressively observe rewards of the experts with the highest information gain, separately for each LLM expert\. The algorithm is computationally efficient and its regret isO~​\(d​T​K/m\)\\tilde\{O\}\(dT\\sqrt\{K/m\}\)\. The additionalK\\sqrt\{K\}factor comparing to the full\-information setting is dueKKtimes less feedback\.
3. 3\.We extend the bandit setting to varying expert costs where the price of evaluating the responses of experts is non\-uniform\. Due to space constraints, this result has been moved to[AppendixA](https://arxiv.org/html/2609.05820#A1)\.
4. 4\.We evaluate all algorithms empirically on the Nectar dataset\([Zhu et al\., 2024](https://arxiv.org/html/2609.05820#bib.bib56)\)and show that they can learn a high\-quality routing agent for many popular LLMs experts, such as GPT\-3\.5, GPT\-4, LLaMA, and Mistral \([Section5](https://arxiv.org/html/2609.05820#S5)\)\.

Technical Novelty:A key challenge in our analysis is bounding the reward gap between the optimal and selected experts for prompts without feedback\. Unlike standard linear bandits, limited feedback prevents immediate updates to the covariance matrix, making it difficult to bound regret using standard techniques\. To address this in the full\-information setting, we introduce a novel feedback strategy: at regular intervals, we select past prompts that maximize the determinant of the covariance matrix\. This approach quickly reduces uncertainty in important directions and allows us to bound regret\. We further show that periodic feedback selection performs nearly as well as hindsight\-optimal choices\. In the bandit setting, we extend this approach by maintaining separate confidence sets per expert to ensure accurate regret guarantees\.

Outline:In[Section2](https://arxiv.org/html/2609.05820#S2), we state our problem and define our model\. In[Sections3](https://arxiv.org/html/2609.05820#S3)and[4](https://arxiv.org/html/2609.05820#S4), we describe our algorithms for the full\-information and bandit settings, respectively, along with providing theoretical guarantees\. In[AppendixA](https://arxiv.org/html/2609.05820#A1), we extend our bandit algorithm to the setting with varying costs of evaluating experts\. In[Section5](https://arxiv.org/html/2609.05820#S5), we provide empirical results using our algorithms\. Finally, in[AppendixB](https://arxiv.org/html/2609.05820#A2), we provide detailed proofs for all our results\.

## 2Problem Setting

Notation:We denote by\[K\]\[K\]the set\{1,2,…,K\}\\\{1,2,\\dots,K\\\}\. We denote scalars and vectors by lowercase letters \(sayxx\)\. We denote matrices and fixed global parameters by capital letters \(sayXX\)\. For a vectorxx,xix\_\{i\}denotes itsi𝗍𝗁i^\{\\mathsf\{th\}\}entry\. For an indexed vectorxjx\_\{j\},xj,ix\_\{j,i\}denotes itsi𝗍𝗁i^\{\\mathsf\{th\}\}entry\. We let\|\|x\|\|A\\left\|\\left\|x\\right\|\\right\|\_\{A\}be the weighted 2\-normxT​A​x\\sqrt\{x^\{T\}Ax\}with respect to a positive semi\-definite matrixAA\. We define the corresponding inner product as⟨x,y⟩A=xT​A​y\\langle x,y\\rangle\_\{A\}=x^\{T\}Ay\.0d0\_\{d\}andIdI\_\{d\}are the zero vector and identity matrix indddimensions, respectively\.𝒩⁡\(0d,Σ\)\\mathcal\{N\}\(0\_\{d\},\\Sigma\)is the Gaussian distribution indd\-dimensions with zero mean and covariance matrixΣ\\Sigma\. For a matrixAA, we writeAiA\_\{i\}to denote itsi𝗍𝗁i^\{\\mathsf\{th\}\}column\. Letℬd≡\{x∈ℝd∣\|\|x\|\|2≤1\}\\mathcal\{B\}^\{d\}\\equiv\\\{x\\in\\mathbb\{R\}^\{d\}\\mid\\left\|\\left\|x\\right\|\\right\|\_\{2\}\\leq 1\\\}be the unit ball indddimensions\.

Problem Formulation:We introduce our setting as a variant of a classic linear bandit\([Abbasi\-Yadkori et al\., 2011](https://arxiv.org/html/2609.05820#bib.bib41)\)\. We haveTTrounds andKKLLM*experts*\. Each expert is indexed bya∈\[K\]a\\in\[K\]and associated with an unknown*parameter vector*θa∈ℬd\\theta\_\{a\}\\in\\mathcal\{B\}^\{d\}\. At each roundt∈\[T\]t\\in\[T\], a*prompt*arrives and we denote it byxt∈L⋅ℬdx\_\{t\}\\in L\\cdot\\mathcal\{B\}^\{d\}for someL\>0L\>0\. The prompt is then treated as*context*at roundtt\.

Given a promptxt∈ℝdx\_\{t\}\\in\\mathbb\{R\}^\{d\}, the algorithm chooses an expertat∈\[K\]a\_\{t\}\\in\[K\]and obtains its response\. In the linear model, the*expected reward*for the response of expertaain roundttis⟨θa,xt⟩\\langle\\theta\_\{a\},x\_\{t\}\\rangle\. We denote the vector of all stochastic*rewards*in roundttbyrt=\(rt,a\)a=1Kr\_\{t\}=\(r\_\{t,a\}\)\_\{a=1\}^\{K\}and define each reward as

rt,a=⟨θa,xt⟩\+ηa,t\.\\displaystyle r\_\{t,a\}=\\langle\\theta\_\{a\},x\_\{t\}\\rangle\+\\eta\_\{a,t\}\\,\.\(1\)We assume that the noise\{ηa,t\}a∈\[K\],t∈\[T\]\\\{\\eta\_\{a,t\}\\\}\_\{a\\in\[K\],t\\in\[T\]\}is independent, both across the experts and rounds, and sub\-Gaussian with a variance proxy11\. The linear model is realistic since the reward is computed as a linear head on top of a frozen transformer embedding\. Specifically,xtx\_\{t\}is the embedding of the prompt produced by a transformer, andθa\\theta\_\{a\}is the linear head for expertaa\. This is standard in reward modeling, with the only distinction being that we do not fine\-tune the embeddings\.

Further, at each roundtt, the contextxtx\_\{t\}arrives, the algorithm selects an expertata\_\{t\}, and feedback is optionally requested afterward\. This ordering reflects a key constraint: feedback is expensive and the decision of whether to query it is made after the action, as part of the exploration strategy\. One may ask whether prompt evaluations could instead be performed before selectingata\_\{t\}, by looking back at past contexts similar toxtx\_\{t\}and leveraging their outcomes to make a more informed decision\. However, doing so would require additional feedback queries at every round, violating the budget constraintm≪Tm\\ll T\. Our formulation instead leverages past feedback frugally: routing decisions are made with whatever has been learned up to roundtt, without retroactive evaluation of past prompts triggered by the current context\. We consider this alternative as the*NoLookBack*baseline in our experiments\.

Limited Feedback:In our setting, the feedback is expensive\([Li et al\., 2024b](https://arxiv.org/html/2609.05820#bib.bib21)\), due to time or monetary constraints111The cost and latency of using LLMs as judges depends on the token counts and pricing of the service provider, such as Azure Databricks\([Databricks, 2025a](https://arxiv.org/html/2609.05820#bib.bib18);[Databricks, 2025b](https://arxiv.org/html/2609.05820#bib.bib17)\), or on the computational resources available to host such LLMs on premise\., and thus limited\. In the classic linear bandit, the noisy reward is typically observed partially or completely at each roundtt\.The key difference in our setting is that the reward vector generated at any roundttis not immediately observed\.However, feedback—provided as observations of rewards—is crucial for improving the selection of experts over successive rounds\([Lattimore and Szepesvari, 2019](https://arxiv.org/html/2609.05820#bib.bib52)\)\.

The algorithm has a budget ofm<Tm<Tobservations, meaning that it can observe at mostmmrewards, either whole vectors or its entries, across the entire time horizon\. Crucially, the algorithm can adaptively decide at which rounds to obtain feedback\. If, at roundt∈\[T\]t\\in\[T\], the algorithm decides to collect feedback, it may choose any roundst≤ts\_\{t\}\\leq tand observe the noisy reward vectorrstr\_\{s\_\{t\}\}or its entryrst,astr\_\{s\_\{t\},a\_\{s\_\{t\}\}\}\. Many prior works in the bandit literature studied limited feedback \([AppendixC](https://arxiv.org/html/2609.05820#A3)\)\. The main difference in our setting is that the algorithm not only selects an expert at each round but also chooses, exploiting the problem structure, when and for which past prompts to collect feedback\.

The expert with the highest expected reward in roundttgiven the promptxtx\_\{t\}is

at⋆=arg​maxa∈\[K\]⁡⟨θa,xt⟩\.\\displaystyle a^\{\\star\}\_\{t\}=\\displaystyle\\argmax\_\{a\\in\[K\]\}\\langle\\theta\_\{a\},x\_\{t\}\\rangle\\,\.We define the*cumulative regret*inTTrounds as

𝖱𝖾𝗀⁡\(T\)=𝔼⁡\[∑t=1T⟨θat⋆,xt⟩−∑t=1T⟨θat,xt⟩\],\\displaystyle\\mathsf\{Reg\}\(T\)=\\mathbb\{E\}\\Big\[\\sum\_\{t=1\}^\{T\}\\langle\\theta\_\{a^\{\\star\}\_\{t\}\},x\_\{t\}\\rangle\-\\sum\_\{t=1\}^\{T\}\\langle\\theta\_\{a\_\{t\}\},x\_\{t\}\\rangle\\Big\]\\,,\(2\)where the expectation is with respect to the randomness of the algorithm\. In the remainder of the paper, we study different forms of limited feedback that can be obtained in practice and analyze regret in these settings\.

## 3Full\-Information Feedback

We start with the full\-information setting, where the agent can observe rewards of all experts at any past round\. While this setting is simpler than the bandit setting in[Section4](https://arxiv.org/html/2609.05820#S4), it already exhibits basic properties of its algorithm design, that the problem can be solved by choosing observations with the highest information gain at regular time intervals\. The former guarantees sub\-linear regret and the latter allows us to trivially satisfy the observation budget\.

### 3\.1Algorithm

Algorithm 1𝙻𝚒𝚖𝙵𝚞𝚕𝚕𝙵𝚎𝚎𝚍\\tt LimFullFeed: Limited full\-information feedback for expert selection\.1:Initialize

b←m/Tb\\leftarrow m/T,

V0←λ​IdV\_\{0\}\\leftarrow\\lambda I\_\{d\},

𝒮0←∅\\mathcal\{S\}\_\{0\}\\leftarrow\\emptyset; and

y0,a←0dy\_\{0,a\}\\leftarrow 0\_\{d\},

θ^0,a←0d\\widehat\{\\theta\}\_\{0,a\}\\leftarrow 0\_\{d\}for all

a∈\[K\]a\\in\[K\]
2:forround

t=1,…,Tt=1,\\dots,Tdo

3:Obtain prompt

xtx\_\{t\}and choose expert

at=arg​maxa∈\[K\]⁡⟨θ^t−1,a,xt⟩\\displaystyle\\textstyle a\_\{t\}=\\argmax\_\{a\\in\[K\]\}\\langle\\widehat\{\\theta\}\_\{t\-1,a\},x\_\{t\}\\rangle\(3\)
4:if

⌊b⁡\(t−1\)⌋<⌊b​t⌋\\lfloor b\(t\-1\)\\rfloor<\\lfloor bt\\rfloorthen

5:Find most informative past observation

st=arg​maxℓ∈\[t\]∖𝒮t−1⁡𝖽𝖾𝗍​\(Vt−1\+xℓ​xℓT\)\\displaystyle\\textstyle s\_\{t\}=\\argmax\_\{\\ell\\in\\,\[t\]\\setminus\\mathcal\{S\}\_\{t\-1\}\\,\}\\mathsf\{det\}\(V\_\{t\-1\}\+x\_\{\\ell\}x\_\{\\ell\}^\{T\}\)\(4\)
6:Observe reward vector

rstr\_\{s\_\{t\}\}and update all statistics

Vt\\displaystyle V\_\{t\}←Vt−1\+xst​xstT,𝒮t←𝒮t−1\+\{st\}\\displaystyle\\leftarrow V\_\{t\-1\}\+x\_\{s\_\{t\}\}x\_\{s\_\{t\}\}^\{T\}\\,,\\quad\\mathcal\{S\}\_\{t\}\\leftarrow\\mathcal\{S\}\_\{t\-1\}\+\\\{s\_\{t\}\\\}∀a∈\[K\]:yt,a\\displaystyle\\forall a\\in\[K\]:y\_\{t,a\}←yt−1,a\+rst,a​xst,θ^t,a←Vt−1​yt,a\\displaystyle\\leftarrow y\_\{t\-1,a\}\+r\_\{s\_\{t\},a\}x\_\{s\_\{t\}\}\\,,\\quad\\widehat\{\\theta\}\_\{t,a\}\\leftarrow V\_\{t\}^\{\-1\}y\_\{t,a\}\(5\)
7:else

8:Update

Vt←Vt−1V\_\{t\}\\leftarrow V\_\{t\-1\},

St←St−1S\_\{t\}\\leftarrow S\_\{t\-1\}; and

yt,a←yt−1,ay\_\{t,a\}\\leftarrow y\_\{t\-1,a\},

θ^t,a←θ^t−1,a\\widehat\{\\theta\}\_\{t,a\}\\leftarrow\\widehat\{\\theta\}\_\{t\-1,a\}for all

a∈\[K\]a\\in\[K\]

Our algorithm𝙻𝚒𝚖𝙵𝚞𝚕𝚕𝙵𝚎𝚎𝚍\\tt LimFullFeedis presented in[Algorithm1](https://arxiv.org/html/2609.05820#alg1)and we describe it next\. The inputs areKKLLM experts, the number of roundsTT, the feedback budgetmm, and a hyperparameterλ\\lambda\. We also initialize all statistics for tracking reward models of all experts online \([Section2](https://arxiv.org/html/2609.05820#S2)\), such as the common covariance matrixV0V\_\{0\}and*ordinary least squares \(OLS\)*estimatesθ^0,a\\widehat\{\\theta\}\_\{0,a\}for all experts\.

In any roundt∈\[T\]t\\in\[T\],𝙻𝚒𝚖𝙵𝚞𝚕𝚕𝙵𝚎𝚎𝚍\\tt LimFullFeedobserves a promptxtx\_\{t\}and chooses the best expertata\_\{t\}based on its estimated mean reward in[Equation3](https://arxiv.org/html/2609.05820#S3.E3)\.𝙻𝚒𝚖𝙵𝚞𝚕𝚕𝙵𝚎𝚎𝚍\\tt LimFullFeedmay decide to obtain feedback\. The feedback is obtained when⌊b⁡\(t−1\)⌋<⌊b​t⌋\\lfloor b\(t\-1\)\\rfloor<\\lfloor bt\\rfloorholds\. Roughly speaking, this happens everyT/mT/mrounds sinceb=m/Tb=m/T\. By following this strategy, we trivially guarantee that the observation budget constraint is satisfied\. When the algorithm decides to obtain feedback, it can select any past unobserved round\. Any round can be observed at most once because two repeated observations would be identical and hence not independent\. More formally, we denote the set of past rounds where the feedback was previously obtained bySt⊆\[t\]S\_\{t\}\\subseteq\[t\]and let the algorithm choose any round in\[t\]∖St\[t\]\\setminus S\_\{t\}\. We denote the chosen round byst∈\[t\]∖Sts\_\{t\}\\in\[t\]\\setminus S\_\{t\}and the observed rewards byrstr\_\{s\_\{t\}\}\. Since we are in the full\-information setting,rstr\_\{s\_\{t\}\}is a vector of the rewards of all experts\. After the feedback is obtained, all statistics are updated, such as the OLS estimates for all experts,θ^t,a\\widehat\{\\theta\}\_\{t,a\}in[Equation8](https://arxiv.org/html/2609.05820#S4.E8)\.

The technical novelty in our algorithm design is in howsts\_\{t\}is chosen\. We consider all past prompts\{xs\}s≤t\\\{x\_\{s\}\\\}\_\{s\\leq t\}and choose the one that maximally increases the determinant of the covariance matrix in[Equation4](https://arxiv.org/html/2609.05820#S3.E4)\. The intuitive idea behind this choice is that this increases all eigenvalues of the covariance matrix uniformly and thus leads to uniformly decreasing confidence intervals in all previously observed directions, encoded by the embeddings of the prompts\. In turn, this yields sub\-linear regret\.

We would like to comment on two more aspects of𝙻𝚒𝚖𝙵𝚞𝚕𝚕𝙵𝚎𝚎𝚍\\tt LimFullFeed\. First, the best expert in[Equation3](https://arxiv.org/html/2609.05820#S3.E3)is chosen using the mean reward estimate\. This is because in the full\-information setting, all experts are trained on the same past prompts and hence have the same covariance matrices\. In the bandit setting \([Section4](https://arxiv.org/html/2609.05820#S4)\), we account for non\-uniform data collection across the experts\. Second, a naive implementation of𝙻𝚒𝚖𝙵𝚞𝚕𝚕𝙵𝚎𝚎𝚍\\tt LimFullFeedhas aO⁡\(d3\)O\(d^\{3\}\)per\-round time complexity, due to invertingd×dd\\times dmatrices and computing their determinants\. This can be reduced toO⁡\(d2\)O\(d^\{2\}\)by using the Sherman\-Morrison formula for the former and the matrix determinant lemma for the latter\.

### 3\.2Main Results

Our goal is to minimize regret under the constraint of obtaining feedback at mostm≤Tm\\leq Ttimes\. The constraint is satisfied trivially \([Section3\.1](https://arxiv.org/html/2609.05820#S3.SS1)\)\. Therefore, we only need to prove a regret bound\. We start by borrowing standard assumptions from linear bandit analyses\([Lattimore and Szepesvári, 2020](https://arxiv.org/html/2609.05820#bib.bib31), Chapter 19\)\.

###### Assumption 3\.1\.

All expert parameters\{θa\}a∈\[K\]\\\{\\theta\_\{a\}\\\}\_\{a\\in\[K\]\}satisfy\|\|θa\|\|2≤1\\left\|\\left\|\\theta\_\{a\}\\right\|\\right\|\_\{2\}\\leq 1\. All prompts\{xt\}t=1T\\\{x\_\{t\}\\\}\_\{t=1\}^\{T\}satisfy\|\|xt\|\|2≤L\\left\|\\left\|x\_\{t\}\\right\|\\right\|\_\{2\}\\leq L\. We also assume thatmaxa,b∈\[k\],t∈\[T\]⁡⟨θa−θb,xt⟩≤1\\max\_\{a,b\\in\[k\],t\\in\[T\]\}\\langle\\theta\_\{a\}\-\\theta\_\{b\},x\_\{t\}\\rangle\\leq 1\.

###### Theorem 3\.2\.

Choose anyKKexperts,ddfeatures, horizonTT, budgetm<Tm<T, andλ\>0\\lambda\>0\. Suppose that[Assumption3\.1](https://arxiv.org/html/2609.05820#S3.Thmtheorem1)holds\. Then the regret of𝙻𝚒𝚖𝙵𝚞𝚕𝚕𝙵𝚎𝚎𝚍\\tt LimFullFeedis𝖱𝖾𝗀\(T\)=O\(dTm−1/2log\(TL\)\)\\mathsf\{Reg\}\(T\)=O\(dTm^\{\-1/2\}\\log\(TL\)\)\.

Due to space constraints, we only sketch the proof\. The detailed proof is in[SectionB\.1](https://arxiv.org/html/2609.05820#A2.SS1)

###### Proof Sketch\.

Consider a fixed experta∈\[K\]a\\in\[K\]with unknownθa\\theta\_\{a\}and a promptxtx\_\{t\}at roundtt\. Using the OLS estimateθ^t,a\\widehat\{\\theta\}\_\{t,a\}forθa\\theta\_\{a\}, the error in estimated mean reward given by⟨θa−θ^t,a,xt⟩\\langle\\theta\_\{a\}\-\\widehat\{\\theta\}\_\{t,a\},x\_\{t\}\\ranglescales as\|\|xt\|\|Vt−1\\left\|\\left\|x\_\{t\}\\right\|\\right\|\_\{V\_\{t\}^\{\-1\}\}\. This error can be rewritten aslog⁡𝖽𝖾𝗍⁡\(Vt\+xt​xtT\)−log⁡𝖽𝖾𝗍​Vt\\log\\mathsf\{det\}\(V\_\{t\}\+x\_\{t\}x\_\{t\}^\{T\}\)\-\\log\\mathsf\{det\}V\_\{t\}\. In standard linear bandits, we update the covariance matrixVt\+1=Vt\+xt​xtTV\_\{t\+1\}=V\_\{t\}\+x\_\{t\}x\_\{t\}^\{T\}\. Hence, we can add up the error over all rounds to obtain a telescoping sum\. However, in our setting with limited feedback,VtV\_\{t\}is not updated at every round and therefore the above does not hold\. The key idea in our proof stems from Line 7 in𝙻𝚒𝚖𝙵𝚞𝚕𝚕𝙵𝚎𝚎𝚍\\tt LimFullFeedwhere we look back to updateVtV\_\{t\}with the prompt that increases its determinant most\. Hence we can still boundlog⁡𝖽𝖾𝗍⁡\(Vt\+xt​xtT\)−log⁡𝖽𝖾𝗍​Vt\\log\\mathsf\{det\}\(V\_\{t\}\+x\_\{t\}x\_\{t\}^\{T\}\)\-\\log\\mathsf\{det\}V\_\{t\}from above bylog⁡𝖽𝖾𝗍​Vt\+1−log⁡𝖽𝖾𝗍​Vt\\log\\mathsf\{det\}V\_\{t\+1\}\-\\log\\mathsf\{det\}V\_\{t\}\. This upper bound is identical for all the rounds between two consecutive feedback and associated updates to the covariance matrix\. Finally, we solicit feedback at regular intervals with interval length ofT/mT/mrounds\. Therefore we still get a telescoping sum after adding the errors but the limited feedback leads to an extra multiplicative factor ofT/mT/min the telescoping sum\. This leads to an additional multiplicative factor ofT/m\\sqrt\{T/m\}in the regret bound\. ∎

Note that regret does not depend on the number of expertsKKsince in the full\-information setting, we obtain responses for all experts jointly\. Therefore, whenm=Tm=T, we can obtain feedback for all rounds and the regret guarantee that is achieved isO⁡\(d​T​log⁡T\)O\(d\\sqrt\{T\}\\log T\)\. This is reminiscent of the standard regret guarantee achieved for linear bandits\([Lattimore and Szepesvári, 2020](https://arxiv.org/html/2609.05820#bib.bib31)\)\. The additional cost of limited feedback arises in the form of a multiplicative factor ofT/m\\sqrt\{T/m\}leading to higher cost with lesser feedback\. We also prove the following lower bound \(detailed proof is in[SectionB\.4](https://arxiv.org/html/2609.05820#A2.SS4)\)\.

###### Theorem 3\.3\.

Consider the online expert selection problem with limited full information feedback,ddfeatures,KKexperts, horizonTT, feedback budget ofm<Tm<T\. Suppose all observations are Gaussian random variables with noise variance11\. Let prompts\{xt\}t=1T∈\{−1,\+1\}d\\\{x\_\{t\}\\\}\_\{t=1\}^\{T\}\\in\\\{\-1,\+1\\\}^\{d\}and\{θa\}a∈\[K\]∈\{−δ,\+δ\}d\\\{\\theta\_\{a\}\\\}\_\{a\\in\[K\]\}\\in\\\{\-\\delta,\+\\delta\\\}^\{d\}forδ=\(md\)−1/2\\delta=\(md\)^\{\-1/2\}\. Then there exists an instance such that the regret incurred must satisfy

𝖱𝖾𝗀⁡\(𝖳\)≥T​d​exp⁡\(−4\)8​m\.\\displaystyle\\mathsf\{Reg\}\(\\mathsf\{T\}\)\\geq\\frac\{T\\sqrt\{d\}\\exp\(\-4\)\}\{8\\sqrt\{m\}\}\.

Discussion:Note that there is a gap ofd\\sqrt\{d\}between the upper and lower bounds\. This gap stems from the fact that we do not know the prompts in advance and therefore, at all roundsttwe need to bound⟨θa−θ^t,a,x⟩\\langle\\theta\_\{a\}\-\\widehat\{\\theta\}\_\{t,a\},x\\ranglefor all possible promptsx∈ℝdx\\in\\mathbb\{R\}^\{d\}and all expertsa∈\[K\]a\\in\[K\]\. Such bounds are obtained in online settings with correlated observed random variables via a tail inequality on self\-normalized martingales[Abbasi\-Yadkori et al\. \(2012\)](https://arxiv.org/html/2609.05820#bib.bib23)\.

Intuitively, ensuring the error bound is small for all vectors in thedd\-dimensional space leads to a union bound overdddimensions that in turn leads to the additionald\\sqrt\{d\}factor in the upper bound\. If on the other hand, the prompts\{xt\}t=1T\\\{x\_\{t\}\\\}\_\{t=1\}^\{T\}was known, then we would only need a union bound over𝖳\\mathsf\{T\}vectors instead of all vectors inℝd\\mathbb\{R\}^\{d\}\. This removes the additionald\\sqrt\{d\}factor from the regret upper bound to make it tight up to logarithmic factors\.

Next we argue that obtaining feedback at regular intervals leads to an optimal regret bound inmm\. Suppose that the algorithm knew the prompts\{xt\}t=1T\\\{x\_\{t\}\\\}\_\{t=1\}^\{T\}in advance and could also decide the order in which to obtain feedback\. Then the algorithm would choose a subsetSSofmmmost\-informative prompts, obtain feedback, and learn the expert parameters from them\. The regret of this approach would beO⁡\(T​maxt∈\[T\]​\|\|xt\|\|V−1\)O\(T\\max\_\{t\\in\[T\]\}\\left\|\\left\|x\_\{t\}\\right\|\\right\|\_\{V^\{\-1\}\}\), wheremaxt∈\[T\]⁡\|\|xt\|\|V−1\\max\_\{t\\in\[T\]\}\\left\|\\left\|x\_\{t\}\\right\|\\right\|\_\{V^\{\-1\}\}is the maximum confidence interval width andV=∑i∈Sxi​xiTV=\\sum\_\{i\\in S\}x\_\{i\}x\_\{i\}^\{T\}\. An optimal solution to this problem is known as the G\-optimal optimal design\([Lattimore and Szepesvári, 2020](https://arxiv.org/html/2609.05820#bib.bib31), Chapter 21\)and its maximum confidence interval width isO⁡\(d/m\)O\(\\sqrt\{d/m\}\)\. This leads to a regret ofO⁡\(T​d/m\)O\(T\\sqrt\{d/m\}\)overTTrounds and completes our argument\.

We can consider a simpler algorithm which does not look back and use past prompts\.

The algorithm requests feedback for the input prompts at the rounds it decided to obtain feedback\. Notice that such a baseline algorithm \(we will call𝙽𝚘𝙻𝚘𝚘𝚔𝙱𝚊𝚌𝚔\\tt NoLookBack\) might suffer linear regret if an adversary provides prompts at the feedback rounds that are in an orthogonal subspace to the prompts in remaining rounds\.

## 4Bandit Setting

In this setting, we consider bandit feedback\. This means that unlike the full information setting, here an agent can observe the reward of only one expert, that which was chosen to generate the response of a prompt at any past round\. Each expert might receive feedback a different number of times \(unlike in the full\-information setting\)\.

We are able to guarantee sub\-linear cumulative regret in this setting as well, while satisfying the budget on feedback trivially, by algorithm design\.

Algorithm 2𝙻𝚒𝚖𝙱𝚊𝚗𝙵𝚎𝚎𝚍\\tt LimBanFeed: Limited bandit feedback for expert selection\.1:Initialize

z←T/mz\\leftarrow T/m,

V0,a←λ​IdV\_\{0,a\}\\leftarrow\\lambda I\_\{d\},

𝒮0,a←∅\\mathcal\{S\}\_\{0,a\}\\leftarrow\\emptyset; and

y0,a←0dy\_\{0,a\}\\leftarrow 0\_\{d\},

θ^0,a←0d\\widehat\{\\theta\}\_\{0,a\}\\leftarrow 0\_\{d\}for all

a∈\[K\]a\\in\[K\]\.

2:forrounds

t=1,2,…,Tt=1,2,\\dots,Tdo

3:Obtain prompt

xtx\_\{t\}, choose expert

ata\_\{t\}and increase its counter by 1\.

at\\displaystyle a\_\{t\}=arg​maxa∈\[K\]⁡⟨θ^t−1,a,xt⟩\+β​\|\|xt\|\|Vt−1,a−1\\displaystyle=\\displaystyle\\argmax\_\{a\\in\[K\]\}\\langle\\widehat\{\\theta\}\_\{t\-1,a\},x\_\{t\}\\rangle\+\\beta\\left\|\\left\|x\_\{t\}\\right\|\\right\|\_\{V\_\{t\-1,a\}^\{\-1\}\}\(6\)nat←nat\+1\\displaystyle n\_\{a\_\{t\}\}\\leftarrow n\_\{a\_\{t\}\}\+1
4:if

nat≥zn\_\{a\_\{t\}\}\\geq zthen

5:Find the most informative past observation for the expert

ata\_\{t\}\. Reset its counter\.

st\\displaystyle s\_\{t\}=arg​maxs∈\{s∈\[t\]:as=a\}∖St−1,a𝖽𝖾𝗍\(Vt−1,at\+xℓxℓT\)\\displaystyle=\\displaystyle\\argmax\_\{s\\in\\\{s\\in\[t\]:a\_\{s\}=a\\\}\\setminus S\_\{t\-1,a\}\}\\mathsf\{det\}\(V\_\{t\-1,a\_\{t\}\}\+x\_\{\\ell\}x\_\{\\ell\}^\{T\}\)\(7\)nat←0\\displaystyle n\_\{a\_\{t\}\}\\leftarrow 0
6:Observe reward

rst,atr\_\{s\_\{t\},a\_\{t\}\}for the expert

ata\_\{t\}and update the corresponding statistics for

ata\_\{t\}\.

Vt,at\\displaystyle V\_\{t,a\_\{t\}\}←Vt−1,at\+xst​xstT,𝒮t,at←𝒮t−1,at\+\{st\}\\displaystyle\\leftarrow V\_\{t\-1,a\_\{t\}\}\+x\_\{s\_\{t\}\}x\_\{s\_\{t\}\}^\{T\}\\,,\\quad\\mathcal\{S\}\_\{t,a\_\{t\}\}\\leftarrow\\mathcal\{S\}\_\{t\-1,a\_\{t\}\}\+\\\{s\_\{t\}\\\}∀a∈\[K\]:yt,at\\displaystyle\\forall a\\in\[K\]:y\_\{t,a\_\{t\}\}←yt−1,at\+rst,at​xst,θ^t,at←Vt,at−1​yt,at\\displaystyle\\leftarrow y\_\{t\-1,a\_\{t\}\}\+r\_\{s\_\{t\},a\_\{t\}\}x\_\{s\_\{t\}\}\\,,\\quad\\widehat\{\\theta\}\_\{t,a\_\{t\}\}\\leftarrow V\_\{t,a\_\{t\}\}^\{\-1\}y\_\{t,a\_\{t\}\}\(8\)
7:else

8:Update

Vt,a←Vt−1,aV\_\{t,a\}\\leftarrow V\_\{t\-1,a\},

yt,a←yt−1,ay\_\{t,a\}\\leftarrow y\_\{t\-1,a\},

θ^t,a=θ^t−1,a\\widehat\{\\theta\}\_\{t,a\}=\\widehat\{\\theta\}\_\{t\-1,a\}and

St,a←St−1,aS\_\{t,a\}\\leftarrow S\_\{t\-1,a\}for all experts

a∈\[K\]a\\in\[K\]\.

### 4\.1Algorithm

Here we describe our proposed algorithm𝙻𝚒𝚖𝙱𝚊𝚗𝙵𝚎𝚎𝚍\\tt LimBanFeed\([Algorithm2](https://arxiv.org/html/2609.05820#alg2)\) that chooses experts to generate response in the bandit feedback setting\. Since different experts can potentially get feedback different number of times,𝙻𝚒𝚖𝙱𝚊𝚗𝙵𝚎𝚎𝚍\\tt LimBanFeedadaptively chooses the experts and the corresponding past prompts \(routed to them\) to collect the feedback\. The key idea is to observe rewards for those experts with highest information gain, by appropriately considering confidence bounds in reward estimates\.

𝙻𝚒𝚖𝙱𝚊𝚗𝙵𝚎𝚎𝚍\\tt LimBanFeedtakes as input the same parameters as𝙻𝚒𝚖𝙵𝚞𝚕𝚕𝙵𝚎𝚎𝚍\\tt LimFullFeedalong with the additional hyperparameterβ\\betacorresponding to the confidence width\. In the bandit setting, we initialize the covariance matrixV0,aV\_\{0,a\}along with other hyperparameters separately for each experta∈\[K\]a\\in\[K\]\. In Line 2, we also initialize a variablezzwhich is set to be the average number of rounds between feedback, namelyT/mT/m\.

At each roundtt, the promptxtx\_\{t\}arrives as context\. Given the input promptxtx\_\{t\},𝙻𝚒𝚖𝙱𝚊𝚗𝙵𝚎𝚎𝚍\\tt LimBanFeedchooses the expertata\_\{t\}in \([6](https://arxiv.org/html/2609.05820#S4.E6)\) to generate the desired response by computing the upper confidence bound on the reward for each expert, given the OLS parameter estimate, and picking the one with the highest upper confidence reward\. We maintain a counternan\_\{a\}for every experta∈\[K\]a\\in\[K\]that keeps track of the number of times an expert is chosen for generating response\. Once an expert has been usedzztimes, feedback is solicited for that expert by choosing a past prompt \(it had served\) appropriately and the counter is reset\.

Clearly, experts that are chosen more frequently will get more feedback\. We show here that the choice ofzzhelps respect the overall feedback budget ofmmrounds\. The number of rounds where an experta∈\[K\]a\\in\[K\]has been used to generate a response in the time horizonTTis\|ST,a\|\\left\|S\_\{T,a\}\\right\|, hence the number of times thea𝗍𝗁a^\{\\mathsf\{th\}\}expert has been evaluated is⌊\|ST,a\|/z⌋\\lfloor\\left\|S\_\{T,a\}\\right\|/z\\rfloor\.

Settingz≥Tmz\\geq\\frac\{T\}\{m\}helps satisfy the feedback budgetmm:

∑a∈\[K\]⌊\|ST,a\|z⌋≤∑a∈\[K\]\|ST,a\|z=Tz≤m⟹z≥Tm\.\\displaystyle\\sum\_\{a\\in\[K\]\}\\lfloor\\frac\{\\left\|S\_\{T,a\}\\right\|\}\{z\}\\rfloor\\leq\\sum\_\{a\\in\[K\]\}\\frac\{\\left\|S\_\{T,a\}\\right\|\}\{z\}=\\frac\{T\}\{z\}\\leq m\\implies z\\geq\\frac\{T\}\{m\}\.
For getting feedback for an expertaa,𝙻𝚒𝚖𝙱𝚊𝚗𝙵𝚎𝚎𝚍\\tt LimBanFeedchooses a prompt index among the past prompts that maximizes the increase in the determinant of the covariance matrix for the expertaa\(see \([7](https://arxiv.org/html/2609.05820#S4.E7)\)\)\. We only choose prompts that have not yet been evaluated\.

We update the OLS estimate of the parameter vectorθ^t,a\\widehat\{\\theta\}\_\{t,a\}for expertata\_\{t\}\(see \([8](https://arxiv.org/html/2609.05820#S4.E8)\)\) by using the observed scalar rewardrst,ar\_\{s\_\{t\},a\}for the chosen prompt\.

### 4\.2Main Results

We show our main result below:

###### Theorem 4\.1\.

Consider the online expert selection problem with limited bandit feedback,KKexperts,ddfeatures, horizonTTand feedback budgetm<Tm<T\. Suppose Assumption[3\.1](https://arxiv.org/html/2609.05820#S3.Thmtheorem1)is true\. Then for anyλ\>0\\lambda\>0andβ=λ\+6​log⁡T\+d​log⁡\(1\+T​L2/d\)\\beta=\\sqrt\{\\lambda\}\+\\sqrt\{6\\log T\+d\\log\(1\+TL^\{2\}/d\)\}, the regret of𝙻𝚒𝚖𝙱𝚊𝚗𝙵𝚎𝚎𝚍\\tt LimBanFeedis

𝖱𝖾𝗀\(T\)=O\(dTK1/2m−1/2log\(TL\)\)\\displaystyle\\mathsf\{Reg\}\(T\)=O\(dTK^\{1/2\}m^\{\-1/2\}\\log\(TL\)\)

The detailed proof is provided in Appendix[B\.2](https://arxiv.org/html/2609.05820#A2.SS2), but we discuss our key ideas here\.

###### Proof Sketch\.

In the bandit setting, the covariance matrix for each expert is updated separately\. However, the key idea for strategically choosing the prompt in history, given the expert, remains the same as in the full\-information setting\. To obtain feedback at roundttfor expertaa, we look back and choose the prompt for which the determinant of the covariance matrix increases the most, allowing us to suitably bound the error\|\|xt\|\|Vt−1,a−1\\left\|\\left\|x\_\{t\}\\right\|\\right\|\_\{V\_\{t\-1,a\}^\{\-1\}\}from above\. Additionally, in our analysis, we use the fact that each expert is updated after being used z =⌈T/m⌉\\lceil T/m\\rceiltimes\. This ensures that the error from an expert decreases over time, with the rate depending on how frequently the expert is invoked\. ∎

Note that the number of feedback observations in the full\-information setting isKKtimes that of the bandit setting for the same number of feedback rounds\. Therefore, roughly speaking, in contrast to the full\-information setting, the regret guarantee with the bandit feedback has an additional multiplicative factor ofK\\sqrt\{K\}\.

Further, whenm=Tm=Tthat is, we can obtain feedback for all rounds, Algorithm[2](https://arxiv.org/html/2609.05820#alg2)achieves a regret guarantee ofO⁡\(d​T​K​log⁡\(T​L\)\)O\(d\\sqrt\{TK\}\\log\(TL\)\)\. As in the full\-information setting, the cost of limited feedback is a multiplicative factor ofT/m\\sqrt\{T/m\}\. Next, we prove a lower bound on the regret in the bandit feedback setting \(detailed proof is in[SectionB\.4](https://arxiv.org/html/2609.05820#A2.SS4)\):

###### Theorem 4\.2\.

Consider the online expert selection problem with limited bandit feedback,ddfeatures,KKexperts, horizonTT, feedback budget ofm<Tm<T\. Suppose all observations are Gaussian random variables with noise variance11\. Let prompts\{xt\}t=1T∈\{−1,\+1\}d\\\{x\_\{t\}\\\}\_\{t=1\}^\{T\}\\in\\\{\-1,\+1\\\}^\{d\}and\{θa\}a∈\[K\]∈\{−δ,\+δ\}d\\\{\\theta\_\{a\}\\\}\_\{a\\in\[K\]\}\\in\\\{\-\\delta,\+\\delta\\\}^\{d\}forδ=\(md\)−1/2\\delta=\(md\)^\{\-1/2\}\. Then there exists an instance such that the regret incurred must satisfy

𝖱𝖾𝗀⁡\(𝖳\)≥T​K​exp⁡\(−4\)8​m\\displaystyle\\mathsf\{Reg\}\(\\mathsf\{T\}\)\\geq\\frac\{TK\\exp\(\-4\)\}\{8\\sqrt\{m\}\}

![Refer to caption](https://arxiv.org/html/2609.05820v1/regret_indomain_full.png)\(a\)Full Information Setting
![Refer to caption](https://arxiv.org/html/2609.05820v1/regret_indomain_new.png)\(b\)Bandit Setting

Figure 1:Results comparing our approaches to the other methods \(RouterBench\): \(a\)𝙽𝚘𝙻𝚘𝚘𝚔𝙱𝚊𝚌𝚔\\tt NoLookBack\(evaluates prompt at round when feedback is requested\) and \(b\)𝙰𝚕𝚕𝙵𝚎𝚎𝚍𝚋𝚊𝚌𝚔\\tt AllFeedback\(observes feedback at all rounds\)\. Clearly,𝙻𝚒𝚖𝙵𝚞𝚕𝚕𝙵𝚎𝚎𝚍\\tt LimFullFeedhas better regret guarantees than𝙽𝚘𝙻𝚘𝚘𝚔𝙱𝚊𝚌𝚔\\tt NoLookBackby careful choice of feedback\.𝙰𝚕𝚕𝙵𝚎𝚎𝚍𝚋𝚊𝚌𝚔\\tt AllFeedbacksuffers the smallest regret due to more data\.There is a gap ofd/Kd/\\sqrt\{K\}between the upper and lower bounds in the bandit setting\. This arises because the lower\-bound analysis reduces to hypothesis testing in aKK\-dimensional subspace\. If we were to ignore the feature structure and treat the experts as arms in a standard multi\-armed bandit setting, we could establish a lower bound ofΩ⁡\(T​K/m\)\\Omega\(T\\sqrt\{K/m\}\), which is looser by a factor ofK\\sqrt\{K\}\. Similar to the full\-information setting, the upper bound includes an additional factor ofd\\sqrt\{d\}due to the algorithm’s lack of knowledge about the prompt vectors, requiring a union bound over all vectors in thedd\-dimensional space\. This extra factor can be eliminated if the algorithm has prior knowledge of the prompts\. The remaining gap ofd/K\\sqrt\{d/K\}persists because the lower bound analysis is based on hypothesis testing withKKvectors and may be further improved\. It will be an interesting direction of future work to improve the lower bound in the bandit setting\.

## 5Experiments

We evaluate our approach on large\-scale LLM routing benchmarks\.

#### Datasets and Baselines\.

We consider two widely used routing benchmarks: RouterBench\([Hu et al\., 2024](https://arxiv.org/html/2609.05820#bib.bib33)\)and Nectar\([Zhu et al\., 2024](https://arxiv.org/html/2609.05820#bib.bib56)\)\. Both datasets provide prompt\-level evaluations across multiple LLM experts, enabling controlled simulation of online routing with ground\-truth rewards\. We follow a standard protocol and sample a subset of prompts to simulate an online interaction stream\.

We compare against two representative baselines\.NoLookBackrequests feedback only for the current round when querying, without leveraging past data\. This corresponds to a naive strategy that ignores the structure of the problem\.AllFeedbackassumes access to feedback at every round and serves as a performance upper bound\.

We simulate an online routing process over a fixed horizonTT, with a feedback budgetm≪Tm\\ll T\. At each round, the algorithm selects an expert based on the observed context, and feedback is collected according to the algorithm’s strategy\. We report cumulative regret with respect to the best expert in hindsight\. All results are averaged over 5 runs\. Details are provided in Appendix[D](https://arxiv.org/html/2609.05820#A4)\.

Table 1:Cumulative regret with respect to feedback budgetmmon Nectar \(K=6K\{=\}6,d=40d\{=\}40,T=60000T\{=\}60000\)\.
#### Main Results\.

Figure[1](https://arxiv.org/html/2609.05820#S4.F1)and[2](https://arxiv.org/html/2609.05820#A4.F2)show the regret as a function of the number of rounds in both the full\-information and bandit settings on RouterBench and Nectar\. We observe that𝙻𝚒𝚖𝙵𝚞𝚕𝚕𝙵𝚎𝚎𝚍\\tt LimFullFeedconsistently outperforms𝙽𝚘𝙻𝚘𝚘𝚔𝙱𝚊𝚌𝚔\\tt NoLookBack\. Interpreting regret as the cumulative number of suboptimal decisions, the gap between the two methods becomes substantial over time\. In particular, by the end of the horizon \(T=60000T=60000\),𝙻𝚒𝚖𝙵𝚞𝚕𝚕𝙵𝚎𝚎𝚍\\tt LimFullFeedachieves noticeably lower regret than𝙽𝚘𝙻𝚘𝚘𝚔𝙱𝚊𝚌𝚔\\tt NoLookBack, indicating a significantly smaller number of mistakes\. This improvement highlights the importance of selecting informative prompts when querying feedback\. By looking back and choosing past observations that maximize information gain,𝙻𝚒𝚖𝙵𝚞𝚕𝚕𝙵𝚎𝚎𝚍\\tt LimFullFeedreduces uncertainty more efficiently and accelerates learning\. In contrast,𝙽𝚘𝙻𝚘𝚘𝚔𝙱𝚊𝚌𝚔\\tt NoLookBackqueries feedback only at the current round, which leads to less informative data collection and slower error reduction\. We also observe that the variance of𝙰𝚕𝚕𝙵𝚎𝚎𝚍𝚋𝚊𝚌𝚔\\tt AllFeedbackis consistently smaller across rounds\. This is expected, as𝙰𝚕𝚕𝙵𝚎𝚎𝚍𝚋𝚊𝚌𝚔\\tt AllFeedbackhas access to substantially more feedback, resulting in more stable estimates and reduced variability across runs\.

The same trend holds in the bandit setting, where𝙻𝚒𝚖𝙱𝚊𝚗𝙵𝚎𝚎𝚍\\tt LimBanFeedconsistently achieves lower regret than𝙽𝚘𝙻𝚘𝚘𝚔𝙱𝚊𝚌𝚔\\tt NoLookBack, with the gap increasing over time\. As in the full\-information setting,𝙰𝚕𝚕𝙵𝚎𝚎𝚍𝚋𝚊𝚌𝚔\\tt AllFeedbackexhibits lower variance due to the larger amount of available data\.

Finally, regret in the full\-information setting is uniformly lower than in the bandit setting\. This aligns with our theoretical analysis, as the full\-information setting provides richer feedback per observation, enabling faster reduction of uncertainty\.

Effect of the Feedback Budget\.Table[1](https://arxiv.org/html/2609.05820#S5.T1)shows that regret decreases asmmincreases, consistent with theT/m\\sqrt\{T/m\}dependence in our theory\. In the bandit setting,𝙻𝚒𝚖𝙱𝚊𝚗𝙵𝚎𝚎𝚍\\tt LimBanFeedconsistently outperforms𝙽𝚘𝙻𝚘𝚘𝚔𝙱𝚊𝚌𝚔\\tt NoLookBack, with the gap widening for largermm\. In the full\-information setting, the gap is smaller for smallmm, since each feedback reveals all experts, but𝙻𝚒𝚖𝙵𝚞𝚕𝚕𝙵𝚎𝚎𝚍\\tt LimFullFeedbecomes competitive asmmincreases\.

Runtime Analysis\.Table[2](https://arxiv.org/html/2609.05820#A4.T2)shows that both methods scale approximately linearly with T\.𝙻𝚒𝚖𝙱𝚊𝚗𝙵𝚎𝚎𝚍\\tt LimBanFeedscales linearly with K, while𝙻𝚒𝚖𝙵𝚞𝚕𝚕𝙵𝚎𝚎𝚍\\tt LimFullFeedis largely independent of K due to its shared covariance structure\.

## 6Conclusions

In this paper, we tackled adaptive prompt routing to LLM experts in an online learning setting with limited feedback\. We framed this as a contextual bandit problem and introduced new algorithms for both full\-information and bandit feedback settings\. Our key innovation is showing when and where to observe feedback, which is expert\-dependent in the bandit setting\. Theoretical guarantees on regret show near\-optimal learning rates, and empirical evaluations confirm our methods’ effectiveness\. Future work could explore dynamic expert availability, varying prompt distributions, and lower bounds in the bandit setting to refine regret minimization strategies\.

## Limitations

We assume that feedback for past prompts can be obtained retrospectively, which may require storing model outputs and relying on noisy human or LLM\-based judgments\. Our experiments use static benchmarks to simulate online routing, which may not fully capture non\-stationary user behavior or deployment constraints\.

## References

- Abbasi\-Yadkoriet al\.\(2011\)Y\. Abbasi\-Yadkori, D\. Pal, and C\. SzepesvariImproved algorithms for linear stochastic bandits\.InAdvances in Neural Information Processing Systems 24,pp\. 2312–2320\.Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p1.1),[§2](https://arxiv.org/html/2609.05820#S2.p2.1)\.
- Abbasi\-Yadkoriet al\.\(2012\)Y\. Abbasi\-Yadkori, D\. Pal, and C\. SzepesvariOnline\-to\-confidence\-set conversions and application to sparse stochastic bandits\.InArtificial Intelligence and Statistics,pp\. 1–9\.Cited by:[§3\.2](https://arxiv.org/html/2609.05820#S3.SS2.p5.1)\.
- Aggarwalet al\.\(2023\)P\. Aggarwal, A\. Madaan, A\. Anand, S\. P\. Potharaju, S\. Mishra, P\. Zhou, A\. Gupta, D\. Rajagopal, K\. Kappaganthu, Y\. Yang,et al\.Automix: automatically mixing language models\.arXiv preprint arXiv:2310\.12963\.Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p3.1)\.
- Agrawalet al\.\(1989\)R\. Agrawal, D\. Teneketzis, and V\. AnantharamAsymptotically efficient adaptive allocation schemes for controlled i\.i\.d\. processes: finite parameter space\.IEEE Transactions on Automatic Control34\(3\),pp\. 258–267\.Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p1.1)\.
- Agrawal and Devanur \(2016\)S\. Agrawal and N\. DevanurLinear contextual bandits with knapsacks\.InAdvances in Neural Information Processing Systems 29,Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p1.1)\.
- Artificial Analysis \(2025\)Artificial AnalysisLLM leaderboard\.External Links:[Link](https://artificialanalysis.ai/leaderboards/models)Cited by:[§1](https://arxiv.org/html/2609.05820#S1.p1.1)\.
- Audibert and Bubeck \(2010\)J\. Audibert and S\. BubeckRegret bounds and minimax policies under partial monitoring\.Journal of Machine Learning Research11\(94\),pp\. 2785–2836\.Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p6.1)\.
- Bartoket al\.\(2014\)G\. Bartok, D\. Foster, D\. Pal, A\. Rakhlin, and C\. SzepesvariPartial monitoring \- classification, regret bounds, and algorithms\.Mathematics of Operations Research39\(4\),pp\. 967–997\.Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p1.1)\.
- Bartok and Szepesvari \(2012\)G\. Bartok and C\. SzepesvariPartial monitoring with side information\.InProceedings of the 23rd International Conference on Algorithmic Learning Theory,pp\. 305–319\.Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p1.1)\.
- Cellaet al\.\(2021\)L\. Cella, M\. Pontil, and C\. GentileBest model identification: a rested bandit formulation\.InProceedings of the 38th International Conference on Machine Learning,M\. Meila and T\. Zhang \(Eds\.\),Proceedings of Machine Learning Research, Vol\.139,pp\. 1362–1372\.Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p5.1)\.
- Cesa\-Bianchiet al\.\(2005\)N\. Cesa\-Bianchi, G\. Lugosi, and G\. StoltzMinimizing regret with label efficient prediction\.IEEE Transactions on Information Theory51\(6\),pp\. 2152–2162\.Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p6.1)\.
- Chenet al\.\(2023\)L\. Chen, M\. Zaharia, and J\. ZouFrugalgpt: how to use large language models while reducing cost and improving performance\.arXiv preprint arXiv:2305\.05176\.Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p3.1)\.
- Corteset al\.\(2018\)C\. Cortes, G\. DeSalvo, C\. Gentile, M\. Mohri, and S\. YangOnline learning with abstention\.InProceedings of the 35th International Conference on Machine Learning,Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p1.1)\.
- Daiet al\.\(2024\)X\. Dai, J\. Li, X\. Liu, A\. Yu, and J\. LuiCost\-effective online multi\-llm selection with versatile reward models\.arXiv preprint arXiv:2405\.16587\.Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p4.1)\.
- Databricks \(2025a\)DatabricksHow quality, cost, and latency are assessed by agent evaluation\.External Links:[Link](https://docs.databricks.com/en/generative-ai/agent-evaluation/llm-judge-metrics.html)Cited by:[footnote 1](https://arxiv.org/html/2609.05820#footnote1)\.
- Databricks \(2025b\)DatabricksMosaic ai agent evaluation\.External Links:[Link](https://www.databricks.com/product/pricing/agent-evaluation)Cited by:[footnote 1](https://arxiv.org/html/2609.05820#footnote1)\.
- \[17\]D\. Ding, A\. Mallick, C\. Wang, R\. Sim, S\. Mukherjee, V\. Rühle, L\. V\. Lakshmanan, and A\. H\. AwadallahHybrid llm: cost\-efficient and quality\-aware query routing\.InThe Twelfth International Conference on Learning Representations ICLR 2024, Vienna, Austria, May 7\-11, 2024,Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p3.1)\.
- Dubeyet al\.\(2024\)A\. Dubey, A\. Jauhri, A\. Pandey, A\. Kadian, A\. Al\-Dahle, A\. Letman, A\. Mathur, A\. Schelten, A\. Yang, A\. Fan,et al\.The llama 3 herd of models\.arXiv preprint arXiv:2407\.21783\.Cited by:[§1](https://arxiv.org/html/2609.05820#S1.p1.1)\.
- Fosteret al\.\(2019\)D\. J\. Foster, A\. Krishnamurthy, and H\. LuoModel selection for contextual bandits\.InAdvances in Neural Information Processing Systems,H\. Wallach, H\. Larochelle, A\. Beygelzimer, F\. d'Alché\-Buc, E\. Fox, and R\. Garnett \(Eds\.\),Vol\.32,pp\.\.Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p5.1)\.
- Hari and Thomson \(2023\)S\. N\. Hari and M\. ThomsonTryage: real\-time, intelligent routing of user prompts to large language model\.arXiv preprint arXiv:2308\.11601\.Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p3.1)\.
- Helmbold and Panizza \(1997\)D\. Helmbold and S\. PanizzaSome label efficient learning results\.InProceedings of the 10th Annual Conference on Computational Learning Theory,pp\. 218–230\.Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p6.1)\.
- Huet al\.\(2024\)Q\. J\. Hu, J\. Bieker, X\. Li, N\. Jiang, B\. Keigwin, G\. Ranganath, K\. Keutzer, and S\. K\. UpadhyayRouterBench: a benchmark for multi\-llm routing system\.External Links:2403\.12031,[Link](https://arxiv.org/abs/2403.12031)Cited by:[Appendix D](https://arxiv.org/html/2609.05820#A4.p1.1),[§5](https://arxiv.org/html/2609.05820#S5.SS0.SSS0.Px1.p1.1)\.
- Huanget al\.\(2025\)K\. Huang, Y\. Shi, D\. Ding, Y\. Li, Y\. Fei, L\. Lakshmanan, and X\. XiaoThriftLLM: on cost\-effective selection of large language models for classification queries\.arXiv preprint arXiv:2501\.04901\.Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p5.1)\.
- Karimiet al\.\(2021\)M\. R\. Karimi, N\. M\. Gürel, B\. Karlaš, J\. Rausch, C\. Zhang, and A\. KrauseOnline active model selection for pre\-trained classifiers\.InInternational Conference on Artificial Intelligence and Statistics,pp\. 307–315\.Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p5.1)\.
- Kazerouniet al\.\(2017\)A\. Kazerouni, M\. Ghavamzadeh, Y\. Abbasi\-Yadkori, and B\. Van RoyConservative contextual linear bandits\.InAdvances in Neural Information Processing Systems 30,Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p1.1)\.
- Kvetonet al\.\(2015a\)B\. Kveton, C\. Szepesvari, Z\. Wen, and A\. AshkanCascading bandits: learning to rank in the cascade model\.InProceedings of the 32nd International Conference on Machine Learning,Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p1.1)\.
- Kvetonet al\.\(2015b\)B\. Kveton, Z\. Wen, A\. Ashkan, and C\. SzepesvariCombinatorial cascading bandits\.InAdvances in Neural Information Processing Systems 28,pp\. 1450–1458\.Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p1.1)\.
- Langford and Zhang \(2008\)J\. Langford and T\. ZhangThe epoch\-greedy algorithm for contextual multi\-armed bandits\.InAdvances in Neural Information Processing Systems 20,pp\. 817–824\.Cited by:[§1](https://arxiv.org/html/2609.05820#S1.p3.1)\.
- Lattimore and Szepesvari \(2019\)T\. Lattimore and C\. SzepesvariBandit algorithms\.Cambridge University Press\.Cited by:[§1](https://arxiv.org/html/2609.05820#S1.p3.1),[§2](https://arxiv.org/html/2609.05820#S2.p5.1)\.
- Lattimore and Szepesvári \(2020\)T\. Lattimore and C\. SzepesváriBandit algorithms\.Cambridge University Press\.Cited by:[§B\.1](https://arxiv.org/html/2609.05820#A2.SS1.p5.1.1),[§B\.2](https://arxiv.org/html/2609.05820#A2.SS2.p2.3.1),[§B\.3](https://arxiv.org/html/2609.05820#A2.SS3.p3.3.1),[§3\.2](https://arxiv.org/html/2609.05820#S3.SS2.p1.1),[§3\.2](https://arxiv.org/html/2609.05820#S3.SS2.p4.1),[§3\.2](https://arxiv.org/html/2609.05820#S3.SS2.p7.1)\.
- Liet al\.\(2024a\)D\. Li, B\. Jiang, L\. Huang, A\. Beigi, C\. Zhao, Z\. Tan, A\. Bhattacharjee, Y\. Jiang, C\. Chen, T\. Wu, K\. Shu, L\. Cheng, and H\. LiuFrom generation to judgment: opportunities and challenges of llm\-as\-a\-judge\.arXiv preprint arXiv:2411\.16594\.Cited by:[§1](https://arxiv.org/html/2609.05820#S1.p2.1)\.
- Liet al\.\(2024b\)H\. Li, Q\. Dong, J\. Chen, H\. Su, Y\. Zhou, Q\. Ai, Z\. Ye, and Y\. LiuLLMs\-as\-judges: a comprehensive survey on llm\-based evaluation methods\.arXiv preprint arXiv:2412\.05579\.Cited by:[§1](https://arxiv.org/html/2609.05820#S1.p2.1),[§2](https://arxiv.org/html/2609.05820#S2.p5.1)\.
- Liet al\.\(2010\)L\. Li, W\. Chu, J\. Langford, and R\. SchapireA contextual\-bandit approach to personalized news article recommendation\.InProceedings of the 19th International Conference on World Wide Web,Cited by:[§1](https://arxiv.org/html/2609.05820#S1.p3.1)\.
- Liet al\.\(2016\)S\. Li, B\. Wang, S\. Zhang, and W\. ChenContextual combinatorial cascading bandits\.InProceedings of the 33rd International Conference on Machine Learning,pp\. 1245–1253\.Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p1.1)\.
- LLM\-as\-a\-Judge \(2025\)LLM\-as\-a\-JudgeLLM as a judge\.External Links:[Link](https://llm-as-a-judge.github.io/)Cited by:[§1](https://arxiv.org/html/2609.05820#S1.p2.1)\.
- Luet al\.\(2024\)K\. Lu, H\. Yuan, R\. Lin, J\. Lin, Z\. Yuan, C\. Zhou, and J\. ZhouRouting to the expert: efficient reward\-guided ensemble of large language models\.InProceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies \(Volume 1: Long Papers\),K\. Duh, H\. Gomez, and S\. Bethard \(Eds\.\),pp\. 1964–1974\.Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p3.1)\.
- Mistral AI \(2025\)Mistral AIMistral AI\.External Links:[Link](https://mistral.ai/)Cited by:[§1](https://arxiv.org/html/2609.05820#S1.p1.1)\.
- Nguyenet al\.\(2024\)Q\. H\. Nguyen, D\. C\. Hoang, J\. Decugis, S\. Manchanda, N\. V\. Chawla, and K\. D\. DoanMetaLLM: a high\-performant and cost\-efficient dynamic framework for wrapping llms\.arXiv preprint arXiv:2407\.10834\.Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p4.1)\.
- Onget al\.\(2024\)I\. Ong, A\. Almahairi, V\. Wu, W\. Chiang, T\. Wu, J\. E\. Gonzalez, M\. W\. Kadous, and I\. StoicaRoutellm: learning to route llms with preference data\.arXiv preprint arXiv:2406\.18665\.Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p3.1)\.
- OpenAIet al\.\(2023\)OpenAI, J\. Achiam, S\. Adler, S\. Agarwal, L\. Ahmad, I\. Akkaya, F\. L\. Aleman, D\. Almeida, J\. Altenschmidt, S\. Altman, S\. Anadkat,et al\.Gpt\-4 technical report\.arXiv preprint arXiv:2303\.08774\.Cited by:[§1](https://arxiv.org/html/2609.05820#S1.p1.1)\.
- OpenAI \(2025\)OpenAIOpenAI API pricing\.External Links:[Link](https://openai.com/api/pricing/)Cited by:[§1](https://arxiv.org/html/2609.05820#S1.p1.1)\.
- Owodunni and Emezue \(2023\)A\. T\. Owodunni and C\. C\. EmezueKoya: a recommender system for large language model selection\.In4th Workshop on African Natural Language Processing,External Links:[Link](https://openreview.net/forum?id=5DGm3lou3z)Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p5.1)\.
- Radlinskiet al\.\(2008\)F\. Radlinski, R\. Kleinberg, and T\. JoachimsLearning diverse rankings with multi\-armed bandits\.InProceedings of the 25th International Conference on Machine Learning,pp\. 784–791\.Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p1.1)\.
- Ramirezet al\.\(2024\)G\. Ramirez, A\. Birch, and I\. TitovOptimising calls to large language models with uncertainty\-based two\-tier selection\.arXiv preprint arXiv:2405\.02134\.Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p3.1)\.
- Šakotaet al\.\(2024\)M\. Šakota, M\. Peyrard, and R\. WestFly\-swat or cannon? cost\-effective language model choice via meta\-modeling\.InProceedings of the 17th ACM International Conference on Web Search and Data Mining,pp\. 606–615\.Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p3.1)\.
- Shekharet al\.\(2024\)S\. Shekhar, T\. Dubey, K\. Mukherjee, A\. Saxena, A\. Tyagi, and N\. KotlaTowards optimizing the costs of llm usage\.arXiv preprint arXiv:2402\.01742\.Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p3.1)\.
- Shnitzeret al\.\(2023\)T\. Shnitzer, A\. Ou, M\. Silva, K\. Soule, Y\. Sun, J\. Solomon, N\. Thompson, and M\. YurochkinLarge language model routing with benchmark datasets\.arXiv preprint arXiv:2309\.15789\.Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p3.1)\.
- Tran\-Thanhet al\.\(2012\)L\. Tran\-Thanh, A\. Chapman, A\. Rogers, and N\. JenningsKnapsack based optimal policies for budget–limited multi–armed bandits\.InProceedings of the 26th AAAI Conference on Artificial Intelligence,pp\. 1134–1140\.Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p1.1)\.
- Tuckeret al\.\(2023\)A\. Tucker, C\. Biddulph, C\. Wang, and T\. JoachimsBandits with costly reward observations\.InProceedings of the 39th Conference on Uncertainty in Artificial Intelligence,Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p6.1)\.
- Vernadeet al\.\(2020\)C\. Vernade, A\. Carpentier, T\. Lattimore, G\. Zappella, B\. Ermis, and M\. BrucknerLinear bandits with stochastic delayed feedback\.InProceedings of the 37th International Conference on Machine Learning,Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p1.1)\.
- Wuet al\.\(2024\)X\. Wu, Y\. Zhong, J\. Wu, B\. Jiang, K\. C\. Tan,et al\.Large language model\-enhanced algorithm selection: towards comprehensive algorithm representation\.Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p5.1)\.
- Wuet al\.\(2016\)Y\. Wu, R\. Shariff, T\. Lattimore, and C\. SzepesvariConservative bandits\.InProceedings of the 33rd International Conference on Machine Learning,pp\. 1254–1262\.Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p1.1)\.
- Xiaet al\.\(2024\)Y\. Xia, F\. Kong, T\. Yu, L\. Guo, R\. A\. Rossi, S\. Kim, and S\. LiWhich llm to play? convergence\-aware online model selection with time\-increasing bandits\.InProceedings of the ACM on Web Conference 2024,pp\. 4059–4070\.Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p4.1)\.
- Xiaoet al\.\(2023\)S\. Xiao, Z\. Liu, P\. Zhang, and N\. MuennighoffC\-pack: packaged resources to advance general chinese embedding\.External Links:2309\.07597Cited by:[Appendix D](https://arxiv.org/html/2609.05820#A4.p1.1)\.
- Zhouet al\.\(2019\)Z\. Zhou, R\. Xu, and J\. BlanchetLearning in generalized linear contextual bandits with stochastic delays\.InAdvances in Neural Information Processing Systems 32,Cited by:[Appendix C](https://arxiv.org/html/2609.05820#A3.p1.1)\.
- Zhuet al\.\(2024\)B\. Zhu, E\. Frick, T\. Wu, H\. Zhu, K\. Ganesan, W\. Chiang, J\. Zhang, and J\. JiaoStarling\-7B: improving helpfulness and harmlessness with RLAIF\.InProceedings of the 1st Conference on Language Modeling,Cited by:[item 4](https://arxiv.org/html/2609.05820#S1.I1.i4.p1.1),[§1](https://arxiv.org/html/2609.05820#S1.p1.1),[§5](https://arxiv.org/html/2609.05820#S5.SS0.SSS0.Px1.p1.1)\.

## Appendix

## Appendix ABandit Feedback with Variable Costs

We can also extend Algorithm[2](https://arxiv.org/html/2609.05820#alg2)to the setting where theKKexperts have different costs of being evaluated and there is a budget on the overall cost\. More precisely, suppose the total cost budget ismmand the cost of evaluation of thej𝗍𝗁j^\{\\mathsf\{th\}\}expert iszjz\_\{j\}\. Without loss of generality, we can assume thatz1≥z2≥⋯≥zKz\_\{1\}\\geq z\_\{2\}\\geq\\dots\\geq z\_\{K\}\. For the expertjjwith costzjz\_\{j\}, we evaluate it after it has been usedzj⋅z~z\_\{j\}\\cdot\\widetilde\{z\}times for somez~\>0\\widetilde\{z\}\>0\.

In other words, the experts is evaluated with a frequency that is proportional to their cost\. In Algorithm[2](https://arxiv.org/html/2609.05820#alg2), each expert had the same cost and therefore, the strategy of evaluation is identical for every expert\. Now, given the budget on the feedback roundsmm,z~\\widetilde\{z\}can be computed as follows: Again, recall that the number of rounds where the expertaahas been used to generate a response in the entire time horizon is\|ST,a\|\\left\|S\_\{T,a\}\\right\|\. In that case, the number of times thea𝗍𝗁a^\{\\mathsf\{th\}\}expert has been evaluated is⌊\|ST,a\|/\(zj⋅z~\)⌋\\lfloor\\left\|S\_\{T,a\}\\right\|/\(z\_\{j\}\\cdot\\widetilde\{z\}\)\\rfloor\. We need the total cost to be smaller thanmm, hence,

∑j⌊\|ST,a\|zj⋅z~⌋⋅zj≤∑j\|ST,a\|zj⋅z~⋅zj\\displaystyle\\sum\_\{j\}\\lfloor\\frac\{\\left\|S\_\{T,a\}\\right\|\}\{z\_\{j\}\\cdot\\widetilde\{z\}\}\\rfloor\\cdot z\_\{j\}\\leq\\sum\_\{j\}\\frac\{\\left\|S\_\{T,a\}\\right\|\}\{z\_\{j\}\\cdot\\widetilde\{z\}\}\\cdot z\_\{j\}=∑j\|ST,a\|z~=Tz~≤m⟹z~≥Tm\.\\displaystyle=\\sum\_\{j\}\\frac\{\\left\|S\_\{T,a\}\\right\|\}\{\\widetilde\{z\}\}=\\frac\{T\}\{\\widetilde\{z\}\}\\leq m\\implies\\widetilde\{z\}\\geq\\frac\{T\}\{m\}\.Now the entire analysis proceeds in the same way as the proof for Theorem[4\.1](https://arxiv.org/html/2609.05820#S4.Thmtheorem1)\. The only difference lies in the non\-uniform rate at which each expert is updated\. More precisely, instead of a common interval length ofzzfor every experta∈\[K\]a\\in\[K\]as in Algorithm[2](https://arxiv.org/html/2609.05820#alg2), now we have an interval length ofza⋅z~z\_\{a\}\\cdot\\widetilde\{z\}for theatha^\{\\text\{th\}\}expert\. Going through the same set of calculations, we can show that the regret guarantee in this case is going to be

𝖱𝖾𝗀\(T\)=O\(Tm−1/2d​β​\(∑jzj\)​log⁡\(d​λ\+md\)\)\\displaystyle\\mathsf\{Reg\}\(T\)=O\\Big\(Tm^\{\-1/2\}\\sqrt\{d\\beta\\Big\(\\sum\_\{j\}z\_\{j\}\\Big\)\\log\\Big\(\\frac\{d\\lambda\+m\}\{d\}\\Big\)\}\\Big\)Substituting the value ofβm/K\\beta\_\{m/K\}as in Theorem[4\.1](https://arxiv.org/html/2609.05820#S4.Thmtheorem1), the final regret guarantee can be written as

𝖱𝖾𝗀\(T\)=O\(dTm−1/2\(∑jzj\)1/2logT\)\.\\mathsf\{Reg\}\(T\)=O\(dTm^\{\-1/2\}\(\\sum\_\{j\}z\_\{j\}\)^\{1/2\}\\log T\)\.Notice that when all the costs are11, we get the same regret guarantee as in Theorem[4\.1](https://arxiv.org/html/2609.05820#S4.Thmtheorem1)\. Further, as is common in this framework, the additional cost of limited feedback comes in the form of a multiplicative factor ofT/m\\sqrt\{T/m\}\.

## Appendix BDetailed Proofs

### B\.1Proof of Theorem[3\.2](https://arxiv.org/html/2609.05820#S3.Thmtheorem2)

###### Proof of Theorem[3\.2](https://arxiv.org/html/2609.05820#S3.Thmtheorem2)\.

Notations:We start by setting up some notations\. LetOt⊆\[t\]O\_\{t\}\\subseteq\[t\]denote the set of rounds until \(including\) roundttin which the algorithm chooses to get feedback\. Note thatOt⊆Ot′O\_\{t\}\\subseteq O\_\{t^\{\\prime\}\}for allt′≥tt^\{\\prime\}\\geq t\. For the set of prompts evaluated until roundtt, recallStS\_\{t\}to be the set of past rounds when the prompts were provided as input to the algorithm\. Let us denoteτt≜max⁡\{ℓ∈\[t−1\]:ℓ∈Ot∧\(ℓ−1\)∉Ot\}\\tau\_\{t\}\\triangleq\\max\\\{\\ell\\in\[t\-1\]:\\ell\\in O\_\{t\}\\wedge\(\\ell\-1\)\\notin O\_\{t\}\\\}denote the last round before roundttwhen the experts were updated\. We denotea∧b=min⁡\(a,b\)a\\wedge b=\\min\(a,b\)\.

We can decompose the RHS in \([2](https://arxiv.org/html/2609.05820#S2.E2)\) as follows:

∑t=1T⟨θat⋆,xt⟩−∑t=1T⟨θat,xt⟩=∑t=1T⟨θat⋆−θ^t,at⋆,xt⟩\+∑t=1T⟨θ^t,at⋆−θ^t,at,xt⟩\+∑t=1T⟨θ^t,at−θat,xt⟩\.\\displaystyle\\sum\_\{t=1\}^\{T\}\\langle\\theta\_\{a^\{\\star\}\_\{t\}\},x\_\{t\}\\rangle\-\\sum\_\{t=1\}^\{T\}\\langle\\theta\_\{a\_\{t\}\},x\_\{t\}\\rangle=\\sum\_\{t=1\}^\{T\}\\langle\\theta\_\{a^\{\\star\}\_\{t\}\}\-\\widehat\{\\theta\}\_\{t,a^\{\\star\}\_\{t\}\},x\_\{t\}\\rangle\+\\sum\_\{t=1\}^\{T\}\\langle\\widehat\{\\theta\}\_\{t,a^\{\\star\}\_\{t\}\}\-\\widehat\{\\theta\}\_\{t,a\_\{t\}\},x\_\{t\}\\rangle\+\\sum\_\{t=1\}^\{T\}\\langle\\widehat\{\\theta\}\_\{t,a\_\{t\}\}\-\\theta\_\{a\_\{t\}\},x\_\{t\}\\rangle\.
Note that the second term is negative\. This is because, by choice of our algorithm, we have picked the expert indexata\_\{t\}at each roundttsuch that⟨θ^t,at⋆−θ^t,at,xt⟩≤0\\langle\\widehat\{\\theta\}\_\{t,a^\{\\star\}\_\{t\}\}\-\\widehat\{\\theta\}\_\{t,a\_\{t\}\},x\_\{t\}\\rangle\\leq 0\. Therefore, we can ignore the second term when bounding the LHS from above and then apply the Cauchy Schwarz inequality

Note that the covariance matrices for all experts remain identical throughout the time horizon\. We denote the covariance matrix of all experts at the beginning of roundttbyVt−1V\_\{t\-1\}\. Recall that feedback is solicited at every interval ofT/mT/mrounds\. Hence, the covariance matrix for all experts remains unchanged between two distinct feedback collections\. From standard guarantees on confidence sets regarding the OLS estimator in the linear model \(see Chapter 19 in[Lattimore and Szepesvári \(2020\)](https://arxiv.org/html/2609.05820#bib.bib31)\), we have the following at every roundt∈\[𝖳\]t\\in\[\\mathsf\{T\}\]and every experta∈\[K\]a\\in\[K\]with probability at least1−o⁡\(T−2\)1\-o\(T^\{\-2\}\):

\|\|θt−θ^t,a\|\|Vt−1≤β​where​β=λ\+6​log⁡T\+d​log⁡\(d​λ\+m​L2d​λ\)\.\\displaystyle\\left\|\\left\|\\theta\_\{t\}\-\\widehat\{\\theta\}\_\{t,a\}\\right\|\\right\|\_\{V\_\{t\-1\}\}\\leq\\beta\\text\{ where \}\\beta=\\sqrt\{\\lambda\}\+\\sqrt\{6\\log T\+d\\log\\Big\(\\frac\{d\\lambda\+mL^\{2\}\}\{d\\lambda\}\\Big\)\}\.\(9\)Denote the eventℰ\\mathcal\{E\}where \([9](https://arxiv.org/html/2609.05820#A2.E9)\) is true for all roundst∈\[T\]t\\in\[T\]and all expertsa∈\[K\]a\\in\[K\]\. Moving forward, we can now condition on the above high probability eventℰ\\mathcal\{E\}\. We now show the following for any roundtt:

⟨θat⋆,xt⟩−⟨θat,xt⟩≤\|\|θat⋆−θ^t,at⋆\|\|Vt−1​\|\|xt\|\|Vt−1−1\+\|\|θ^t,at−θat\|\|Vt−1​\|\|xt\|\|Vt−1−1≤2​β​\|\|xt\|\|Vt−1−1=2​β​\|\|xt\|\|Vτt−1\.\\displaystyle\\langle\\theta\_\{a^\{\\star\}\_\{t\}\},x\_\{t\}\\rangle\-\\langle\\theta\_\{a\_\{t\}\},x\_\{t\}\\rangle\\leq\\left\|\\left\|\\theta\_\{a^\{\\star\}\_\{t\}\}\-\\widehat\{\\theta\}\_\{t,a^\{\\star\}\_\{t\}\}\\right\|\\right\|\_\{V\_\{t\-1\}\}\\left\|\\left\|x\_\{t\}\\right\|\\right\|\_\{V\_\{t\-1\}^\{\-1\}\}\+\\left\|\\left\|\\widehat\{\\theta\}\_\{t,a\_\{t\}\}\-\\theta\_\{a\_\{t\}\}\\right\|\\right\|\_\{V\_\{t\-1\}\}\\left\|\\left\|x\_\{t\}\\right\|\\right\|\_\{V\_\{t\-1\}^\{\-1\}\}\\leq 2\\beta\\left\|\\left\|x\_\{t\}\\right\|\\right\|\_\{V\_\{t\-1\}^\{\-1\}\}=2\\beta\\left\|\\left\|x\_\{t\}\\right\|\\right\|\_\{V\_\{\\tau\_\{t\}\}^\{\-1\}\}\.\(10\)The last step follows from the fact that by definitionτt,at\\tau\_\{t,a\_\{t\}\}is the last round \(before roundtt\) when the expertata\_\{t\}had been updated\. Note that for each roundtt, we also have⟨θat⋆,xt⟩−⟨θat,xt⟩≤1\\langle\\theta\_\{a^\{\\star\}\_\{t\}\},x\_\{t\}\\rangle\-\\langle\\theta\_\{a\_\{t\}\},x\_\{t\}\\rangle\\leq 1from the assumption in theorem statement\. Therefore, we can combine to show

∑t=1T⟨θat⋆,xt⟩−∑t=1T⟨θat,xt⟩≤2​β​∑t=1T\(1∧\|\|xt\|\|Vt−1−1\)≤2​T​β​∑t=1T\(1∧\|\|xt\|\|Vt−1−12\)\\displaystyle\\sum\_\{t=1\}^\{T\}\\langle\\theta\_\{a^\{\\star\}\_\{t\}\},x\_\{t\}\\rangle\-\\sum\_\{t=1\}^\{T\}\\langle\\theta\_\{a\_\{t\}\},x\_\{t\}\\rangle\\leq 2\\beta\\sum\_\{t=1\}^\{T\}\\Big\(1\\wedge\\left\|\\left\|x\_\{t\}\\right\|\\right\|\_\{V\_\{t\-1\}^\{\-1\}\}\\Big\)\\leq 2\\sqrt\{T\\beta\\sum\_\{t=1\}^\{T\}\\Big\(1\\wedge\\left\|\\left\|x\_\{t\}\\right\|\\right\|^\{2\}\_\{V\_\{t\-1\}^\{\-1\}\}\\Big\)\}where the final step follows from application of Cauchy\-Schwarz inequality\. Now, continuing from \([10](https://arxiv.org/html/2609.05820#A2.E10)\), for any roundtt, we use the fact that for anyu≥0u\\geq 0, we haveu∧1≤2​log⁡\(1\+u\)u\\wedge 1\\leq 2\\log\(1\+u\):

1∧\|\|xt\|\|Vτt−12\\displaystyle 1\\wedge\\left\|\\left\|x\_\{t\}\\right\|\\right\|^\{2\}\_\{V\_\{\\tau\_\{t\}\}^\{\-1\}\}≤log\(1\+\|\|xt\|\|Vτt−12\)=log𝖽𝖾𝗍\(I\+Vτt−1/2xtxtTVτt−1/2\)\\displaystyle\\leq\\log\\Big\(1\+\\left\|\\left\|x\_\{t\}\\right\|\\right\|^\{2\}\_\{V\_\{\\tau\_\{t\}\}^\{\-1\}\}\\Big\)=\\log\\mathsf\{det\}\\Big\(I\+V\_\{\\tau\_\{t\}\}^\{\-1/2\}x\_\{t\}x\_\{t\}^\{T\}V\_\{\\tau\_\{t\}\}^\{\-1/2\}\\Big\)=log⁡𝖽𝖾𝗍⁡\(Vτt\+xt​xtT\)−log⁡𝖽𝖾𝗍​Vτt\\displaystyle=\\log\\mathsf\{det\}\\Big\(V\_\{\\tau\_\{t\}\}\+x\_\{t\}x\_\{t\}^\{T\}\\Big\)\-\\log\\mathsf\{det\}V\_\{\\tau\_\{t\}\}Now, consider a roundt∈OTt\\in O\_\{T\}where feedback has been observed for some prompt in the history\. As we defined before,τt\\tau\_\{t\}corresponds to the previous round in history where feedback has been observed\. From Algorithm[1](https://arxiv.org/html/2609.05820#alg1), recall thatsts\_\{t\}was the prompt chosen at roundt∈OTt\\in O\_\{T\}for feedback following which we had updatedVt−1=Vτt\+xst​xstTV\_\{t\-1\}=V\_\{\\tau\_\{t\}\}\+x\_\{s\_\{t\}\}x\_\{s\_\{t\}\}^\{T\}\. Further, recall that the prompt indexsts\_\{t\}at roundttwas chosen in the following way:

st=𝖺𝗋𝗀𝗆𝖺𝗑ℓ∈\[t\]∖𝒮t−1​𝖽𝖾𝗍​\(Vt−1\+xℓ​xℓT\)=𝖺𝗋𝗀𝗆𝖺𝗑ℓ∈\[t\]∖𝒮t−1​𝖽𝖾𝗍​\(Vτt\+xℓ​xℓT\)\\displaystyle s\_\{t\}=\\mathsf\{argmax\}\_\{\\ell\\in\\,\[t\]\\setminus\\mathcal\{S\}\_\{t\-1\}\\,\}\\mathsf\{det\}\(V\_\{t\-1\}\+x\_\{\\ell\}x\_\{\\ell\}^\{T\}\)=\\mathsf\{argmax\}\_\{\\ell\\in\\,\[t\]\\setminus\\mathcal\{S\}\_\{t\-1\}\\,\}\\mathsf\{det\}\(V\_\{\\tau\_\{t\}\}\+x\_\{\\ell\}x\_\{\\ell\}^\{T\}\)implying that the promptsts\_\{t\}increases the determinant of the covariance matrixVτtV\_\{\\tau\_\{t\}\}the most\. Thus, for every roundr∈\[τt\+1,t\]r\\in\[\\tau\_\{t\}\+1,t\], we must have𝖽𝖾𝗍⁡\(Vr\+xr​xrT\)=𝖽𝖾𝗍⁡\(Vτt\+xr​xrT\)≤𝖽𝖾𝗍⁡\(Vτt\+xst​xstT\)\\mathsf\{det\}\(V\_\{r\}\+x\_\{r\}x\_\{r\}^\{T\}\)=\\mathsf\{det\}\(V\_\{\\tau\_\{t\}\}\+x\_\{r\}x\_\{r\}^\{T\}\)\\leq\\mathsf\{det\}\(V\_\{\\tau\_\{t\}\}\+x\_\{s\_\{t\}\}x\_\{s\_\{t\}\}^\{T\}\)\. Hence, we have

∑r∈\[τt\+1,t\]log⁡𝖽𝖾𝗍⁡\(Vr\+xr​xrT\)≤⌈T/m⌉​log⁡𝖽𝖾𝗍⁡\(Vτt\+xst​xstT\)=⌈T/m⌉​log​𝖽𝖾𝗍​Vt−1\.\\displaystyle\\sum\_\{r\\in\[\\tau\_\{t\}\+1,t\]\}\\log\\mathsf\{det\}\(V\_\{r\}\+x\_\{r\}x\_\{r\}^\{T\}\)\\leq\\lceil T/m\\rceil\\log\\mathsf\{det\}\(V\_\{\\tau\_\{t\}\}\+x\_\{s\_\{t\}\}x\_\{s\_\{t\}\}^\{T\}\)=\\lceil T/m\\rceil\\log\\mathsf\{det\}V\_\{t\-1\}\.Therefore, using the fact that the covariance matrix remains unchanged forT/mT/mrounds, we can write

∑t=1T\(1∧\|\|xt\|\|Vτt−12\)\\displaystyle\\sum\_\{t=1\}^\{T\}\\Big\(1\\wedge\\left\|\\left\|x\_\{t\}\\right\|\\right\|^\{2\}\_\{V\_\{\\tau\_\{t\}\}^\{\-1\}\}\\Big\)≤⌈T/m⌉​∑t∈OT\(log⁡𝖽𝖾𝗍​Vt−log⁡𝖽𝖾𝗍​Vτt\)\+T​m−1\\displaystyle\\leq\\lceil T/m\\rceil\\sum\_\{t\\in O\_\{T\}\}\\Big\(\\log\\mathsf\{det\}V\_\{t\}\-\\log\\mathsf\{det\}V\_\{\\tau\_\{t\}\}\\Big\)\+Tm^\{\-1\}=⌈T/m⌉​\(log⁡𝖽𝖾𝗍​VT−log⁡𝖽𝖾𝗍​V0\)\+T​m−1\.\\displaystyle=\\lceil T/m\\rceil\\Big\(\\log\\mathsf\{det\}V\_\{T\}\-\\log\\mathsf\{det\}V\_\{0\}\\Big\)\+Tm^\{\-1\}\.
Notice thatVt−1=∑t∈OTxst​xstTV\_\{t\-1\}=\\sum\_\{t\\in O\_\{T\}\}x\_\{s\_\{t\}\}x\_\{s\_\{t\}\}^\{T\},\|OT\|=m\\left\|O\_\{T\}\\right\|=m\(since we are getting feedback formmrounds\)\. Moreover, for all prompts\{xt\}t∈\[T\]\\\{x\_\{t\}\\\}\_\{t\\in\[T\]\}, we have𝖳𝗋⁡\(xt​xtT\)=\|\|xt\|\|22≤1\\mathsf\{Tr\}\(x\_\{t\}x\_\{t\}^\{T\}\)=\\left\|\\left\|x\_\{t\}\\right\|\\right\|\_\{2\}^\{2\}\\leq 1since all prompts are within the unit ball\. Now, we use the AM\-GM inequality and linearity of trace operation to show

𝖽𝖾𝗍​VT≤\(d−1​𝖳𝗋​\(VT\)\)d≤\(d−1​\(𝖳𝗋⁡\(V0\)\+m\)\)d\\displaystyle\\mathsf\{det\}V\_\{T\}\\leq\\Big\(d^\{\-1\}\\mathsf\{Tr\}\(V\_\{T\}\)\\Big\)^\{d\}\\leq\\Big\(d^\{\-1\}\\Big\(\\mathsf\{Tr\}\(V\_\{0\}\)\+m\\Big\)\\Big\)^\{d\}We have𝖳𝗋⁡\(V0\)≤d​λ\\mathsf\{Tr\}\(V\_\{0\}\)\\leq d\\lambdaand therefore, we bound the regret conditioned on the eventℰ\\mathcal\{E\}\(denote by𝖱𝖾𝗀⁡\(T\)\|ℰ\\mathsf\{Reg\}\(T\)\\mid\\mathcal\{E\}\) as

𝖱𝖾𝗀\(T\)∣ℰ=O\(Tm−1/2d​β​log⁡\(d​λ\+md\)\)\\displaystyle\\mathsf\{Reg\}\(T\)\\mid\\mathcal\{E\}=O\\Big\(Tm^\{\-1/2\}\\sqrt\{d\\beta\\log\\Big\(\\frac\{d\\lambda\+m\}\{d\}\\Big\)\}\\Big\)When the eventℰ\\mathcal\{E\}is false, then the regret can be bounded by the2​T2T\(worst\-case\)\. Therefore the final regret can be written as

𝖱𝖾𝗀⁡\(T\)=𝖱𝖾𝗀⁡\(T\)\|ℰ\+2​T​Pr⁡\(ℰc\)=𝖱𝖾𝗀⁡\(T\)\|ℰ\+o⁡\(T−1\)\.\\displaystyle\\mathsf\{Reg\}\(T\)=\\mathsf\{Reg\}\(T\)\\mid\\mathcal\{E\}\+2T\\Pr\(\\mathcal\{E\}^\{c\}\)=\\mathsf\{Reg\}\(T\)\\mid\\mathcal\{E\}\+o\(T^\{\-1\}\)\.Now, we can substitute the value forβ\\betato obtain the final theorem statement\. ∎

### B\.2Proof of Theorem[4\.1](https://arxiv.org/html/2609.05820#S4.Thmtheorem1)

###### Proof of Theorem[4\.1](https://arxiv.org/html/2609.05820#S4.Thmtheorem1)\.

Notations:We start by introducing new notations\. For any experta∈\[K\]a\\in\[K\], letOt,a⊆\[t\]O\_\{t,a\}\\subseteq\[t\]denote the set of rounds until roundttin which the algorithm has opted to obtain a feedback for expertaa\. As before, for anya∈\[K\]a\\in\[K\], we haveOt,a⊆Ot′,aO\_\{t,a\}\\subseteq O\_\{t^\{\\prime\},a\}for allt′≥tt^\{\\prime\}\\geq t\. Similar to full\-information, for the set of prompts evaluated until roundtt, defineStS\_\{t\}to be the set of past rounds when the prompts were provided as input to the algorithm\. We denoteτt,a≜max⁡\{ℓ∈\[t−1\]:ℓ∈Ot,a∧\(ℓ−1\)∉Ot,a\}\\tau\_\{t,a\}\\triangleq\\max\\\{\\ell\\in\[t\-1\]:\\ell\\in O\_\{t,a\}\\wedge\(\\ell\-1\)\\notin O\_\{t,a\}\\\}denote the last round before roundttwhen the expertaawas updated\.

As in the proof of Theorem[3\.2](https://arxiv.org/html/2609.05820#S3.Thmtheorem2), we will exploit standard guarantees on confidence sets regarding the OLS estimator in the linear model\. We have the following at every roundt∈\[𝖳\]t\\in\[\\mathsf\{T\}\]and every experta∈\[K\]a\\in\[K\]with probability at least1−o⁡\(T−2\)1\-o\(T^\{\-2\}\):

\|\|θt−θ^t,a\|\|Vt−1,a≤β​where​β=λ\+6​log⁡T\+d​log⁡\(d​λ\+m​L2d​λ\)\.\\displaystyle\\left\|\\left\|\\theta\_\{t\}\-\\widehat\{\\theta\}\_\{t,a\}\\right\|\\right\|\_\{V\_\{t\-1,a\}\}\\leq\\beta\\text\{ where \}\\beta=\\sqrt\{\\lambda\}\+\\sqrt\{6\\log T\+d\\log\\Big\(\\frac\{d\\lambda\+mL^\{2\}\}\{d\\lambda\}\\Big\)\}\.\(11\)Denote the eventℰ\\mathcal\{E\}where \([11](https://arxiv.org/html/2609.05820#A2.E11)\) is true for all roundst∈\[T\]t\\in\[T\]and all expertsa∈\[K\]a\\in\[K\]\. For any promptxtx\_\{t\}at roundtt, the parameter vector in the confidence region that leads to the highest reward is given by

θ~t,a=supϕ∈\|\|ϕ−θ^t,a\|\|Vt−1,a≤β⟨ϕ,xt⟩\.\\displaystyle\\widetilde\{\\theta\}\_\{t,a\}=\\sup\_\{\\phi\\in\\left\|\\left\|\\phi\-\\widehat\{\\theta\}\_\{t,a\}\\right\|\\right\|\_\{V\_\{t\-1,a\}\}\\leq\\beta\}\\langle\\phi,x\_\{t\}\\rangle\.and therefore, the expertata\_\{t\}to generate the response is chosen asmaxa∈\[K\]⁡⟨θ~t,a,xt⟩\\max\_\{a\\in\[K\]\}\\langle\\widetilde\{\\theta\}\_\{t,a\},x\_\{t\}\\rangle\. It is interesting to note that the bilinear optimization problem has a nice closed form expression given by \(see Sec 19\.3\.1 in[Lattimore and Szepesvári \(2020\)](https://arxiv.org/html/2609.05820#bib.bib31)\)

at=arg​maxa∈\[K\]⁡⟨θ^t,a,xt⟩\+β⋅\|\|xt\|\|Vt−1,a−1\\displaystyle a\_\{t\}=\\displaystyle\\argmax\_\{a\\in\[K\]\}\\langle\\widehat\{\\theta\}\_\{t,a\},x\_\{t\}\\rangle\+\\beta\\cdot\\left\|\\left\|x\_\{t\}\\right\|\\right\|\_\{V\_\{t\-1,a\}^\{\-1\}\}Now, we can decompose the RHS in \([2](https://arxiv.org/html/2609.05820#S2.E2)\) for any roundt∈\[T\]t\\in\[T\]as follows:

⟨θat⋆,xt⟩−⟨θat,xt⟩≤⟨θ^at⋆,xt⟩\+β​\|\|xt\|\|Vt,at⋆−1−⟨θat,xt⟩≤⟨θ^at,xt⟩\+β​\|\|xt\|\|Vt,at−1−⟨θat,xt⟩\\displaystyle\\langle\\theta\_\{a^\{\\star\}\_\{t\}\},x\_\{t\}\\rangle\-\\langle\\theta\_\{a\_\{t\}\},x\_\{t\}\\rangle\\leq\\langle\\widehat\{\\theta\}\_\{a^\{\\star\}\_\{t\}\},x\_\{t\}\\rangle\+\\beta\\left\|\\left\|x\_\{t\}\\right\|\\right\|\_\{V\_\{t,a^\{\\star\}\_\{t\}\}^\{\-1\}\}\-\\langle\\theta\_\{a\_\{t\}\},x\_\{t\}\\rangle\\leq\\langle\\widehat\{\\theta\}\_\{a\_\{t\}\},x\_\{t\}\\rangle\+\\beta\\left\|\\left\|x\_\{t\}\\right\|\\right\|\_\{V\_\{t,a\_\{t\}\}^\{\-1\}\}\-\\langle\\theta\_\{a\_\{t\}\},x\_\{t\}\\rangle
For the first inequality we bound the reward for the expertat⋆a\_\{t\}^\{\\star\}from above by the upper confidence bound on the reward\. The second inequality follows from⟨θ^t,at⋆−θ^t,at,xt⟩≤0\\langle\\widehat\{\\theta\}\_\{t,a^\{\\star\}\_\{t\}\}\-\\widehat\{\\theta\}\_\{t,a\_\{t\}\},x\_\{t\}\\rangle\\leq 0\. This is because, by choice of our algorithm, we have picked the expert indexata\_\{t\}at each roundtthaving the largest upper confidence reward on promptxtx\_\{t\}\.

The covariance matrices for each of the experts are updated separately in the bandit feedback setting\. Recall that the noisy reward for only a single expert is observed whenever the algorithm opts for a feedback\. We denote the covariance matrix of experta∈\[K\]a\\in\[K\]at roundttbyVt−1,aV\_\{t\-1,a\}\. Again, recall that feedback is solicited for expertaaafter the expertaahas been used to generate a responsezztimes\. Now, we can show the following for any roundtt

⟨θat⋆,xt⟩−⟨θat,xt⟩\\displaystyle\\langle\\theta\_\{a^\{\\star\}\_\{t\}\},x\_\{t\}\\rangle\-\\langle\\theta\_\{a\_\{t\}\},x\_\{t\}\\rangle≤β​\|\|xt\|\|Vt,at−1\+\|\|θ^t,at−θat\|\|Vt,at​\|\|xt\|\|Vt,at−1\\displaystyle\\leq\\beta\\left\|\\left\|x\_\{t\}\\right\|\\right\|\_\{V\_\{t,a\_\{t\}\}^\{\-1\}\}\+\\left\|\\left\|\\widehat\{\\theta\}\_\{t,a\_\{t\}\}\-\\theta\_\{a\_\{t\}\}\\right\|\\right\|\_\{V\_\{t,a\_\{t\}\}\}\\left\|\\left\|x\_\{t\}\\right\|\\right\|\_\{V\_\{t,a\_\{t\}\}^\{\-1\}\}≤2​β​\|\|xt\|\|Vt,at−1\\displaystyle\\leq 2\\beta\\left\|\\left\|x\_\{t\}\\right\|\\right\|\_\{V\_\{t,a\_\{t\}\}^\{\-1\}\}
Now, we need to bound from above the final term on the RHS in terms of the individual experts as follows:

∑t=1T\|\|xt\|\|Vt,at−1\\displaystyle\\sum\_\{t=1\}^\{T\}\\left\|\\left\|x\_\{t\}\\right\|\\right\|\_\{V\_\{t,a\_\{t\}\}^\{\-1\}\}=∑a=1K∑t=1T\|\|xt\|\|Vt,at−1𝟏\[at=a\]\\displaystyle=\\sum\_\{a=1\}^\{K\}\\sum\_\{t=1\}^\{T\}\\left\|\\left\|x\_\{t\}\\right\|\\right\|\_\{V\_\{t,a\_\{t\}\}^\{\-1\}\}\\mathbf\{1\}\[a\_\{t\}=a\]≤∑a=1K∑t=1T\(1∧\|\|xt\|\|Vt,at−1𝟏\[at=a\]\)\\displaystyle\\leq\\sum\_\{a=1\}^\{K\}\\sum\_\{t=1\}^\{T\}\\Big\(1\\wedge\\left\|\\left\|x\_\{t\}\\right\|\\right\|\_\{V\_\{t,a\_\{t\}\}^\{\-1\}\}\\mathbf\{1\}\[a\_\{t\}=a\]\\Big\)≤T∑a=1K∑t=1T\(1∧\|\|xt\|\|2Vt,at−1\)𝟏\[at=a\]\)\\displaystyle\\leq\\sqrt\{T\\sum\_\{a=1\}^\{K\}\\sum\_\{t=1\}^\{T\}\\Big\(1\\wedge\\left\|\\left\|x\_\{t\}\\right\|\\right\|^\{2\}\_\{V\_\{t,a\_\{t\}\}^\{\-1\}\}\\Big\)\\mathbf\{1\}\[a\_\{t\}=a\]\\Big\)\}In the pre\-final step, we used that in each roundtt, we also have⟨θat⋆,xt⟩−⟨θat,xt⟩≤1\\langle\\theta\_\{a^\{\\star\}\_\{t\}\},x\_\{t\}\\rangle\-\\langle\\theta\_\{a\_\{t\}\},x\_\{t\}\\rangle\\leq 1from the assumption in theorem statement\. In the final step, we used the Cauchy\-Schwarz inequality\. Note that there are onlyTTterms in the RHS since at each round, only a single expert is chosen\. Consider a particular experta∈\[K\]a\\in\[K\]\- it is chosen for obtaining feedback after being used for generating responseszztimes since the last time feedback was obtained for expertaa\.

At any roundtt, recallτt,a=max⁡\{ℓ∈\[t−1\]:ℓ∈Ot,a∧\(ℓ−1\)∉Ot,a\}\\tau\_\{t,a\}=\\max\\\{\\ell\\in\[t\-1\]:\\ell\\in O\_\{t,a\}\\wedge\(\\ell\-1\)\\notin O\_\{t,a\}\\\}denote the last round fromttwhen the expertaawas chosen for obtaining feedback \(after the counter for expertaareachedzz\)\. For any roundt∈Ot,at\\in O\_\{t,a\}, as per our notation, recall thatVt−1,aV\_\{t\-1,a\}is the covariance matrix for the expertaaat roundtt\. Thenτt−1,a\\tau\_\{t\-1,a\}is the previous round when the expertaawas updated\. For any roundtt, we can use the fact that for anyu≥0u\\geq 0, we haveu∧1≤2​log⁡\(1\+u\)u\\wedge 1\\leq 2\\log\(1\+u\),

1∧\|\|xt\|\|Vt,at−12\\displaystyle 1\\wedge\\left\|\\left\|x\_\{t\}\\right\|\\right\|^\{2\}\_\{V\_\{t,a\_\{t\}\}^\{\-1\}\}≤log\(1\+\|\|xt\|\|Vt,at−12\)=log𝖽𝖾𝗍\(I\+Vt,at−1/2xtxtTVt,at−1/2\)\\displaystyle\\leq\\log\\Big\(1\+\\left\|\\left\|x\_\{t\}\\right\|\\right\|^\{2\}\_\{V\_\{t,a\_\{t\}\}^\{\-1\}\}\\Big\)=\\log\\mathsf\{det\}\\Big\(I\+V\_\{t,a\_\{t\}\}^\{\-1/2\}x\_\{t\}x\_\{t\}^\{T\}V\_\{t,a\_\{t\}\}^\{\-1/2\}\\Big\)=log⁡𝖽𝖾𝗍⁡\(Vt,at\+xt​xtT\)−log⁡𝖽𝖾𝗍​Vt,at=log⁡𝖽𝖾𝗍⁡\(Vτt,at,at\+xt​xtT\)−log⁡𝖽𝖾𝗍​Vτt,at,at\\displaystyle=\\log\\mathsf\{det\}\\Big\(V\_\{t,a\_\{t\}\}\+x\_\{t\}x\_\{t\}^\{T\}\\Big\)\-\\log\\mathsf\{det\}V\_\{t,a\_\{t\}\}=\\log\\mathsf\{det\}\\Big\(V\_\{\\tau\_\{t,a\_\{t\}\},a\_\{t\}\}\+x\_\{t\}x\_\{t\}^\{T\}\\Big\)\-\\log\\mathsf\{det\}V\_\{\\tau\_\{t,a\_\{t\}\},a\_\{t\}\}
Now for a fixed experta∈\[K\]a\\in\[K\], consider a roundt∈OT,at\\in O\_\{T,a\}where feedback has been observed for some prompt in the history of expertaa\. As we defined before,τt−1,a\\tau\_\{t\-1,a\}corresponds to the previous round in history \(relative to roundOPENt\)t\)where feedback has been observed for expertaa\. From Algorithm[2](https://arxiv.org/html/2609.05820#alg2), recall thatsts\_\{t\}was the prompt chosen at roundt∈Ot,at\\in O\_\{t,a\}for feedback following which we had updatedVt−1,a=Vτt−1,a\+xst​xstTV\_\{t\-1,a\}=V\_\{\\tau\_\{t\-1\},a\}\+x\_\{s\_\{t\}\}x\_\{s\_\{t\}\}^\{T\}\. Further, recall that the prompt indexsts\_\{t\}at roundttwas chosen in the following way:

st=arg​maxs∈\{s∈\[t\]:as=a\}∖St−1,a𝖽𝖾𝗍\(Vt−1,a\+xsxsT\)=arg​maxs∈\{s∈\[t\]:as=a\}∖𝒮t−1,a𝖽𝖾𝗍\(Vτt−1,a,a\+xxxsT\)\\displaystyle s\_\{t\}=\\displaystyle\\argmax\_\{s\\in\\\{s\\in\[t\]:a\_\{s\}=a\\\}\\setminus S\_\{t\-1,a\}\}\\mathsf\{det\}\(V\_\{t\-1,a\}\+x\_\{s\}x\_\{s\}^\{T\}\)=\\displaystyle\\argmax\_\{s\\in\\\{s\\in\[t\]:a\_\{s\}=a\\\}\\setminus\\mathcal\{S\}\_\{t\-1,a\}\\,\}\\mathsf\{det\}\(V\_\{\\tau\_\{t\-1,a\},a\}\+x\_\{x\}x\_\{s\}^\{T\}\)implying that the promptsts\_\{t\}was responded to by the expertata\_\{t\}and further, the promptsts\_\{t\}increases the determinant of the covariance matrixVτt−1,a,aV\_\{\\tau\_\{t\-1,a\},a\}the most\. Thus, for every roundr∈\[τt−1,a\+1,t\]r\\in\[\\tau\_\{t\-1,a\}\+1,t\]satisfying𝟏\[ar=a\]\\mathbf\{1\}\[a\_\{r\}=a\], we must have𝖽𝖾𝗍⁡\(Vr,a\+xr​xrT\)=𝖽𝖾𝗍⁡\(Vτt−1,a,a\+xr​xrT\)≤𝖽𝖾𝗍⁡\(Vτt−1,a,a\+xst​xstT\)\\mathsf\{det\}\(V\_\{r,a\}\+x\_\{r\}x\_\{r\}^\{T\}\)=\\mathsf\{det\}\(V\_\{\\tau\_\{t\-1,a\},a\}\+x\_\{r\}x\_\{r\}^\{T\}\)\\leq\\mathsf\{det\}\(V\_\{\\tau\_\{t\-1,a\},a\}\+x\_\{s\_\{t\}\}x\_\{s\_\{t\}\}^\{T\}\)\. Hence, we have

∑r∈\[τt−1\+1,t\]log⁡𝖽𝖾𝗍⁡\(Vr,a\+xr​xrT\)≤c⋅log⁡𝖽𝖾𝗍⁡\(Vτt−1,a,a\+xst​xstT\)=⌈T/m⌉​log​𝖽𝖾𝗍​Vt−1,a\.\\displaystyle\\sum\_\{r\\in\[\\tau\_\{t\-1\}\+1,t\]\}\\log\\mathsf\{det\}\(V\_\{r,a\}\+x\_\{r\}x\_\{r\}^\{T\}\)\\leq c\\cdot\\log\\mathsf\{det\}\(V\_\{\\tau\_\{t\-1,a\},a\}\+x\_\{s\_\{t\}\}x\_\{s\_\{t\}\}^\{T\}\)=\\lceil T/m\\rceil\\log\\mathsf\{det\}V\_\{t\-1,a\}\.In the last step, we used the threshold onzzthat would meet the feedback budgetmm\. As we had shown, it is sufficient to havez≥T/mz\\geq T/mso that the total amount of feedback rounds is at mostmm\. Therefore, by combining all of these, we get

T∑a=1K∑t=1T\(1∧\|\|xt\|\|2Vt,at−1\)𝟏\[at=a\]\)\\displaystyle\\sqrt\{T\\sum\_\{a=1\}^\{K\}\\sum\_\{t=1\}^\{T\}\\Big\(1\\wedge\\left\|\\left\|x\_\{t\}\\right\|\\right\|^\{2\}\_\{V\_\{t,a\_\{t\}\}^\{\-1\}\}\\Big\)\\mathbf\{1\}\[a\_\{t\}=a\]\\Big\)\}=T​∑a=1K\(z​∑t∈OT,a\(log⁡𝖽𝖾𝗍​Vt−1,a−log⁡𝖽𝖾𝗍​Vτt−1,a,a\)\+c\)\\displaystyle=\\sqrt\{T\\sum\_\{a=1\}^\{K\}\\Big\(z\\sum\_\{t\\in O\_\{T,a\}\}\\Big\(\\log\\mathsf\{det\}V\_\{t\-1,a\}\-\\log\\mathsf\{det\}V\_\{\\tau\_\{t\-1,a\},a\}\\Big\)\+c\\Big\)\}\(12\)≤Tm−1/2∑j=1K\(log⁡𝖽𝖾𝗍⁡\(Vt−1,a−log⁡𝖽𝖾𝗍​V0,a\)CLOSE\+c​K​T\.\\displaystyle\\leq Tm^\{\-1/2\}\\sqrt\{\\sum\_\{j=1\}^\{K\}\\Big\(\\log\\mathsf\{det\}\(V\_\{t\-1,a\}\-\\log\\mathsf\{det\}V\_\{0,a\}\\Big\)\}\+\\sqrt\{cKT\}\.\(13\)
For a fixed experta∈\[K\]a\\in\[K\], notice thatVt−1,a=∑t∈OT,axst​xstTV\_\{t\-1,a\}=\\sum\_\{t\\in O\_\{T,a\}\}x\_\{s\_\{t\}\}x\_\{s\_\{t\}\}^\{T\},\|OT\|≤m\\left\|O\_\{T\}\\right\|\\leq m\(since we are getting feedback for at mostmmrounds for any expert\)\. Moreover, for all prompts\{xt\}t∈\[T\]\\\{x\_\{t\}\\\}\_\{t\\in\[T\]\}, we have𝖳𝗋⁡\(xt​xtT\)=\|\|xt\|\|22≤1\\mathsf\{Tr\}\(x\_\{t\}x\_\{t\}^\{T\}\)=\\left\|\\left\|x\_\{t\}\\right\|\\right\|\_\{2\}^\{2\}\\leq 1since all prompts are within the unit ball\. Now, we use the AM\-GM inequality and linearity of trace operation to show

𝖽𝖾𝗍​Vt−1,a≤\(d−1​𝖳𝗋​\(Vt−1,a\)\)d≤\(d−1​\(𝖳𝗋⁡\(V0,a\)\+m\)\)d\\displaystyle\\mathsf\{det\}V\_\{t\-1,a\}\\leq\\Big\(d^\{\-1\}\\mathsf\{Tr\}\(V\_\{t\-1,a\}\)\\Big\)^\{d\}\\leq\\Big\(d^\{\-1\}\\Big\(\\mathsf\{Tr\}\(V\_\{0,a\}\)\+m\\Big\)\\Big\)^\{d\}We have𝖳𝗋⁡\(V0,a\)≤d​λ\\mathsf\{Tr\}\(V\_\{0,a\}\)\\leq d\\lambdaand therefore, we bound the regret conditioned on the eventℰ\\mathcal\{E\}\(denote by𝖱𝖾𝗀⁡\(T\)\|ℰ\\mathsf\{Reg\}\(T\)\\mid\\mathcal\{E\}\) as

𝖱𝖾𝗀\(T\)∣ℰ=O\(TK1/2m−1/2d​β​log⁡\(d​λ\+md\)\)\\displaystyle\\mathsf\{Reg\}\(T\)\\mid\\mathcal\{E\}=O\\Big\(TK^\{1/2\}m^\{\-1/2\}\\sqrt\{d\\beta\\log\\Big\(\\frac\{d\\lambda\+m\}\{d\}\\Big\)\}\\Big\)𝖱𝖾𝗀⁡\(T\)=𝖱𝖾𝗀⁡\(T\)\|ℰ\+2​T​Pr⁡\(ℰc\)=𝖱𝖾𝗀⁡\(T\)\|ℰ\+o⁡\(T−1\)\.\\displaystyle\\mathsf\{Reg\}\(T\)=\\mathsf\{Reg\}\(T\)\\mid\\mathcal\{E\}\+2T\\Pr\(\\mathcal\{E\}^\{c\}\)=\\mathsf\{Reg\}\(T\)\\mid\\mathcal\{E\}\+o\(T^\{\-1\}\)\.Now, we can substitute the value forβ\\betato obtain the final theorem statement\.

∎

### B\.3Proof of Theorem[3\.3](https://arxiv.org/html/2609.05820#S3.Thmtheorem3)

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

Consider number of roundsTT, a feedback budget ofmm\(full\-information feedback\) and all observations to be Gaussian random variables with unit variance\. While constructing our instances, let us denote the set of prompts we choose from to be𝒳⊂\{−1,\+1\}d\\mathcal\{X\}\\subset\\\{\-1,\+1\\\}^\{d\}and the set of model features to beθ⊂\{−δ,\+δ\}d\\theta\\subset\\\{\-\\delta,\+\\delta\\\}^\{d\}for someδ\>0\\delta\>0\. For any two vectors \(x,yx,y\), we can define the Hamming distancedh\(x,y\)=∑i=1d𝟏\[sign\(xi\)≠sign\(yi\)\]d\_\{h\}\(x,y\)=\\sum\_\{i=1\}^\{d\}\\mathbf\{1\}\[\\text\{sign\}\(x\_\{i\}\)\\neq\\text\{sign\}\(y\_\{i\}\)\]\.

Fix a vectorx∈\{−1,\+1\}dx\\in\\\{\-1,\+1\\\}^\{d\}\. Now, we define an instance in the full\-information expert selection setting as follows: for each of theTTrounds, a single promptx∈𝒳x\\in\\mathcal\{X\}is going to be demonstrated and the set of expert parameters in this instance is given byθ≡\{θ∈\{−δ,\+δ\}d∣dh​\(θ,x\)≤1\}\\theta\\equiv\\\{\\theta\\in\\\{\-\\delta,\+\\delta\\\}^\{d\}\\mid d\_\{h\}\(\\theta,x\)\\leq 1\\\}\. In other words, the set of allowed experts have feature embedding which are within a Hamming distance of11from the prompt embedding vectorxx\. Given this environment, \. Recall that the expert chosen at roundttis denoted byata\_\{t\}\. Now, we defineddalternate learning instances as follows: in each alternate instance, a vectorx′x^\{\\prime\}satisfyingdh​\(x,x′\)=1d\_\{h\}\(x,x^\{\\prime\}\)=1is demonstrated at all rounds while the set of model features𝒯⁡\(x\)\\mathcal\{T\}\(x\)remain the same\. Therefore, the set of prompts across thed\+1d\+1instances is𝒳≡\{y∈\{−1,\+1\}d∣dh​\(y,x\)≤1\}\\mathcal\{X\}\\equiv\\\{y\\in\\\{\-1,\+1\\\}^\{d\}\\mid d\_\{h\}\(y,x\)\\leq 1\\\}\. Since the distinction between the instances is only in the prompt \(the expert featuresθ\\thetaremain same in all instances\), we denote byℙy\\mathbb\{P\}\_\{y\}and𝔼y\\mathbb\{E\}\_\{y\}the probability and expectation of events under a fixed policy for instance defined by prompty∈𝒳y\\in\\mathcal\{X\}\.

Consider the environment defined by the promptxx\. Let us define the following event which is true when the number of times the sign of thei𝗍𝗁i^\{\\mathsf\{th\}\}entry of the prompt and algorithm output \(observation of history’s actions\) differs is at leastT/2T/2

ℰx,i=𝟏\[∑i=1Tsign\(xi\)≠sign\(at​i\)≥T/2\]\\displaystyle\\mathcal\{E\}\_\{x,i\}=\\mathbf\{1\}\[\\sum\_\{i=1\}^\{T\}\\text\{sign\}\(x\_\{i\}\)\\neq\\text\{sign\}\(a\_\{ti\}\)\\geq T/2\]and the corresponding probability to bepx,i=ℙx​\(ℰx,i\)p\_\{x,i\}=\\mathbb\{P\}\_\{x\}\(\\mathcal\{E\}\_\{x,i\}\)\. Now consider the alternate instance with promptx′∈𝒳x^\{\\prime\}\\in\\mathcal\{X\}wherexj′=xjx^\{\\prime\}\_\{j\}=x\_\{j\}for allj≠ij\\neq iandxi′=−xix^\{\\prime\}\_\{i\}=\-x\_\{i\}\. Therefore,xxandx′x^\{\\prime\}have a Hamming distance of11and differ in sign at the indexii\. Note that the eventℰx′,i\\mathcal\{E\}\_\{x^\{\\prime\},i\}is the complement of the eventℰx,i\\mathcal\{E\}\_\{x,i\}\. We have

px,i\+px′,i=ℙx\(ℰx,i\)\+ℙx′\(ℰx,ic\)≥12exp\(−𝖣𝖪𝖫\(ℙx\|\|ℙx′\)\)\\displaystyle p\_\{x,i\}\+p\_\{x^\{\\prime\},i\}=\\mathbb\{P\}\_\{x\}\(\\mathcal\{E\}\_\{x,i\}\)\+\\mathbb\{P\}\_\{x^\{\\prime\}\}\(\\mathcal\{E\}\_\{x,i\}^\{c\}\)\\geq\\frac\{1\}\{2\}\\exp\\Big\(\-\\mathsf\{D\}\_\{\\mathsf\{KL\}\}\(\\mathbb\{P\}\_\{x\}\|\|\\mathbb\{P\}\_\{x^\{\\prime\}\}\)\\Big\)Above, we used the Bretagnolle Huber inequality \(see[Lattimore and Szepesvári \(2020\)](https://arxiv.org/html/2609.05820#bib.bib31)\) and𝖣𝖪𝖫\\mathsf\{D\}\_\{\\mathsf\{KL\}\}is the Kullback\-Leibler Divergence\. It is given by

𝖣𝖪𝖫\(ℙx\|\|ℙx′\)=m𝔼x\[𝖣𝖪𝖫\(𝒩\(θ⋅x,Id\+1\)\|\|𝒩\(θ⋅x′,Id\+1\)\]\)=m\|\|θ\(x−x′\)\|\|22=mδ2\(d\+1\)\.\\displaystyle\\mathsf\{D\}\_\{\\mathsf\{KL\}\}\(\\mathbb\{P\}\_\{x\}\|\|\\mathbb\{P\}\_\{x^\{\\prime\}\}\)=m\\mathbb\{E\}\_\{x\}\\Big\[\\mathsf\{D\}\_\{\\mathsf\{KL\}\}\\Big\(\\mathcal\{N\}\(\\theta\\cdot x,I\_\{d\+1\}\)\|\|\\mathcal\{N\}\(\\theta\\cdot x^\{\\prime\},I\_\{d\+1\}\)\\Big\]\\Big\)=m\\left\|\\left\|\\theta\(x\-x^\{\\prime\}\)\\right\|\\right\|\_\{2\}^\{2\}=m\\delta^\{2\}\(d\+1\)\.In that case, for the value ofδ=1/m⁡\(d\+1\)\\delta=1/\\sqrt\{m\(d\+1\)\}, we getpx,i\+px′,i≥exp⁡\(−1\)/2p\_\{x,i\}\+p\_\{x^\{\\prime\},i\}\\geq\\exp\(\-1\)/2\. Now, we want to extend the analysis to environments defined by promptsy∈𝒳∖\{x\}y\\in\\mathcal\{X\}\\setminus\\\{x\\\}\. Fix such a promptyyand define the event which is true when the number of times the sign of thei𝗍𝗁i^\{\\mathsf\{th\}\}entry of the prompt and the expert differs is at leastT/2T/2

ℰy,i=𝟏\[∑i=1Tsign\(yi\)≠sign\(at​i\)≥T/2\]\\displaystyle\\mathcal\{E\}\_\{y,i\}=\\mathbf\{1\}\[\\sum\_\{i=1\}^\{T\}\\text\{sign\}\(y\_\{i\}\)\\neq\\text\{sign\}\(a\_\{ti\}\)\\geq T/2\]Without loss of generality, assume that the index whereyyandxxdiffers in sign isj≠ij\\neq i\(otherwise the alternate instance trivially becomes the environment defined byxx\)\. In that case, consider the alternate instance defined by prompty′y^\{\\prime\}such that𝐲′​t​h​e=xs\\mathbf\{y^\{\\prime\}\}the=x\_\{s\}for alls≠is\\neq iand𝐲′i=−xi\\mathbf\{y^\{\\prime\}\}\_\{i\}=\-x\_\{i\}\(y′y^\{\\prime\}andxxdiffers in sign at the indexii\)\. Therefore,yyandy′y^\{\\prime\}have a Hamming distance of22and differ in sign at the indicesi,ji,j\. However, note that the eventℰy′,i\\mathcal\{E\}\_\{y^\{\\prime\},i\}is the complement of the eventℰy,i\\mathcal\{E\}\_\{y,i\}\. By a similar analysis as above, we have

py,i\+py′,i≥12exp\(−𝖣𝖪𝖫\(ℙy\|\|ℙy′\)\)=12exp\(−m\|\|θ\(y−y′\)\|\|22\)≥12exp\(−4mδ2\(d\+1\)\)\.\\displaystyle p\_\{y,i\}\+p\_\{y^\{\\prime\},i\}\\geq\\frac\{1\}\{2\}\\exp\\Big\(\-\\mathsf\{D\}\_\{\\mathsf\{KL\}\}\(\\mathbb\{P\}\_\{y\}\|\|\\mathbb\{P\}\_\{y^\{\\prime\}\}\)\\Big\)=\\frac\{1\}\{2\}\\exp\\Big\(\-m\\left\|\\left\|\\theta\(y\-y^\{\\prime\}\)\\right\|\\right\|\_\{2\}^\{2\}\\Big\)\\geq\\frac\{1\}\{2\}\\exp\\Big\(\-4m\\delta^\{2\}\(d\+1\)\\Big\)\.In that case, for the value ofδ=1/m⁡\(d\+1\)\\delta=1/\\sqrt\{m\(d\+1\)\}, we have

py,i\+py′,i≥exp⁡\(−4\)/2\.\\displaystyle p\_\{y,i\}\+p\_\{y^\{\\prime\},i\}\\geq\\exp\(\-4\)/2\.Since there ared\+1d\+1possibilities of the promptxx, we can have

1\|𝒳\|​∑x∈𝒳∑i=1dpx,i=1\|𝒳\|​∑i=1d∑x∈𝒳px,i≥d​exp⁡\(−4\)4\.\\displaystyle\\frac\{1\}\{\\left\|\\mathcal\{X\}\\right\|\}\\sum\_\{x\\in\\mathcal\{X\}\}\\sum\_\{i=1\}^\{d\}p\_\{x,i\}=\\frac\{1\}\{\\left\|\\mathcal\{X\}\\right\|\}\\sum\_\{i=1\}^\{d\}\\sum\_\{x\\in\\mathcal\{X\}\}p\_\{x,i\}\\geq\\frac\{d\\exp\(\-4\)\}\{4\}\.Hence, there must exist a prompty∈𝒳y\\in\\mathcal\{X\}for which∑i=1dpy,i≥d​exp⁡\(−4\)/4\\sum\_\{i=1\}^\{d\}p\_\{y,i\}\\geq d\\exp\(\-4\)/4\. For this instance defined by the promptyyand expert featuresθ\\theta, we have

𝖱𝖾𝗀⁡\(T\)\\displaystyle\\mathsf\{Reg\}\(T\)=𝔼y​\[∑t=1T⟨y,δ⋅y−𝐚t⟩\]\\displaystyle=\\mathbb\{E\}\_\{y\}\\Big\[\\sum\_\{t=1\}^\{T\}\\langle y,\\delta\\cdot y\-\\mathbf\{a\}\_\{t\}\\rangle\\Big\]=𝔼y\[∑t=1T⟨y,δy−At⟩\]=𝔼y\[∑t=1T∑i=1dyi\(δyi−at​i\)\]=2δ𝔼y\[∑t=1T∑i=1d𝟏\[sign\(yi\)≠sign\(at​i\)\]\]\\displaystyle=\\mathbb\{E\}\_\{y\}\\Big\[\\sum\_\{t=1\}^\{T\}\\langle y,\\delta y\-A\_\{t\}\\rangle\\Big\]=\\mathbb\{E\}\_\{y\}\\Big\[\\sum\_\{t=1\}^\{T\}\\sum\_\{i=1\}^\{d\}y\_\{i\}\\Big\(\\delta y\_\{i\}\-a\_\{ti\}\\Big\)\\Big\]=2\\delta\\mathbb\{E\}\_\{y\}\\Big\[\\sum\_\{t=1\}^\{T\}\\sum\_\{i=1\}^\{d\}\\mathbf\{1\}\[\\text\{sign\}\(y\_\{i\}\)\\neq\\text\{sign\}\(a\_\{ti\}\)\]\\Big\]=2δ∑i=1d𝔼y\[∑t=1T𝟏\[sign\(yi\)≠sign\(at​i\)\]\]=δT∑i=1dℙy​i≥δ​d​T​exp⁡\(−4\)4≥T​d​exp⁡\(−4\)8​m\.\\displaystyle=2\\delta\\sum\_\{i=1\}^\{d\}\\mathbb\{E\}\_\{y\}\\Big\[\\sum\_\{t=1\}^\{T\}\\mathbf\{1\}\[\\text\{sign\}\(y\_\{i\}\)\\neq\\text\{sign\}\(a\_\{ti\}\)\]\\Big\]=\\delta T\\sum\_\{i=1\}^\{d\}\\mathbb\{P\}\_\{yi\}\\geq\\frac\{\\delta dT\\exp\(\-4\)\}\{4\}\\geq\\frac\{T\\sqrt\{d\}\\exp\(\-4\)\}\{8\\sqrt\{m\}\}\.This completes the proof of the theorem\. ∎

### B\.4Proof of Theorem[4\.2](https://arxiv.org/html/2609.05820#S4.Thmtheorem2)

###### Proof of Theorem[4\.2](https://arxiv.org/html/2609.05820#S4.Thmtheorem2)\.

The proof of the lower bound for the bandit setting follows on similar lines as the proof in Theorem[3\.3](https://arxiv.org/html/2609.05820#S3.Thmtheorem3)\. Consider number of roundsTT, a feedback budget ofmmand number of experts to beKKand all observations to be Gaussian random variables with unit variance\. Note that in this setting, for a particular prompt, feedback is only provided to the expert that was used to generate a response for that prompt\. As before, we denote the set of prompts to be𝒳⊂\{−1,\+1\}d\\mathcal\{X\}\\subset\\\{\-1,\+1\\\}^\{d\}and the set of experts features to beθ⊂\{−δ,\+δ\}d\\theta\\subset\\\{\-\\delta,\+\\delta\\\}^\{d\}for someδ\>0\\delta\>0\. For any two vectorsx,yx,y, we can define the Hamming distancedh\(x,y\)=∑i=1d𝟏\[sign\(xi\)≠sign\(yi\)\]d\_\{h\}\(x,y\)=\\sum\_\{i=1\}^\{d\}\\mathbf\{1\}\[\\text\{sign\}\(x\_\{i\}\)\\neq\\text\{sign\}\(y\_\{i\}\)\]\.

Fix a prompt vectorxxto be thedd\-dimensional all ones vector\. For simplicity assume thatddis divisible by𝖪\\mathsf\{K\}\. Now, we define an instance in the bandit feedback setting as follows: for each of theTTrounds, the single promptx∈𝒳x\\in\\mathcal\{X\}is going to be demonstrated at all rounds and the set of expert parameters is given by a fixed set ofKKvectors from the setθ≡\{θ∈\{−δ,\+δ\}d∣dh​\(θ,x\)≤1\}\\theta\\equiv\\\{\\theta\\in\\\{\-\\delta,\+\\delta\\\}^\{d\}\\mid d\_\{h\}\(\\theta,x\)\\leq 1\\\}\. Without loss of generality, let\{θa\}a∈\[K\]\\\{\\theta\_\{a\}\\\}\_\{a\\in\[K\]\}be the set of parameter vectors which has its sign flipped fromxxin one of the firstKKentries\.

Now, we can defineKKalternate learning instances as follows: in each alternate instance, a vectorx′x^\{\\prime\}satisfyingdh​\(x,x′\)=1d\_\{h\}\(x,x^\{\\prime\}\)=1is demonstrated at all rounds while the set of expert features𝒯⁡\(x\)\\mathcal\{T\}\(x\)remain the same\. Furtherx′x^\{\\prime\}has its sign changed only among the firstKKentries ofxx\. Therefore the lastd−Kd\-Kindices are inconsequential and we basically have aKK\-dimensional problem\. Now, we go through the same steps as in the proof of Theorem[3\.3](https://arxiv.org/html/2609.05820#S3.Thmtheorem3)\. However, since we are in the bandit feedback setting, we will get after using the Bretagnolle Huber inequality that the KL divergence between data distributions of any two instances isO⁡\(exp⁡\(−m​δ2\)\)O\(\\exp\(\-m\\delta^\{2\}\)\)\. Hence, substitutingδ=1/m\\delta=1/\\sqrt\{m\}and then resuming the same steps gives us the following lower bound:

𝖱𝖾𝗀⁡\(𝖳\)≥T​K​exp⁡\(−4\)8​m\.\\displaystyle\\mathsf\{Reg\}\(\\mathsf\{T\}\)\\geq\\frac\{TK\\exp\(\-4\)\}\{8\\sqrt\{m\}\}\.
∎

## Appendix CRelated Work

There are many notions of limited feedback and resource constraints that have been studied in the past\. Partial monitoring\([Agrawal et al\., 1989](https://arxiv.org/html/2609.05820#bib.bib34);[Bartok and Szepesvari, 2012](https://arxiv.org/html/2609.05820#bib.bib42);[Bartok et al\., 2014](https://arxiv.org/html/2609.05820#bib.bib44)\)and learning to rank\([Radlinski et al\., 2008](https://arxiv.org/html/2609.05820#bib.bib38);[Kveton et al\., 2015a](https://arxiv.org/html/2609.05820#bib.bib45);[Kveton et al\., 2015b](https://arxiv.org/html/2609.05820#bib.bib46);[Li et al\., 2016](https://arxiv.org/html/2609.05820#bib.bib48)\)are bandit problems where the agent observes rewards of taken actions only partially\. In our setting, the agent observes the reward fully but decides what to observe\. In bandits with delayed feedback\([Zhou et al\., 2019](https://arxiv.org/html/2609.05820#bib.bib53);[Vernade et al\., 2020](https://arxiv.org/html/2609.05820#bib.bib54)\), the agent observes rewards of taken action with delays\. The delay is not controlled by the agent\. Our agent observes rewards with delays but decides what to observe, and thus controls the delay\. Further, it is well known that the linear model in bandit algorithms can be updated lazily, whenever the determinant of the covariance matrix increases significantly \(Section 5\.1 in[Abbasi\-Yadkori et al\. \(2011\)](https://arxiv.org/html/2609.05820#bib.bib41)\)\. When the model is updated, all past observations are used\. In our setting, we update the model periodically but only use a subset of past observations selected by the agent\. The knapsack is a popular way of modeling resource constraints in bandits\([Tran\-Thanh et al\., 2012](https://arxiv.org/html/2609.05820#bib.bib43);[Agrawal and Devanur, 2016](https://arxiv.org/html/2609.05820#bib.bib47)\)\. We have a resource constraint but it is significantly simpler\. This is why we can minimize the regret greedily at a near\-optimal rate by periodically taking the most uncertain action in the past\. In conservative bandits\([Wu et al\., 2016](https://arxiv.org/html/2609.05820#bib.bib49);[Kazerouni et al\., 2017](https://arxiv.org/html/2609.05820#bib.bib50)\), the agent takes a greedy exploratory action after accumulating a sufficient exploratory budget\. The regret bound involves an extra term due to taking the safe action\. In our setting, the agent has more control because it can observe the reward of any past action\. Therefore, the extra term does not appear\. In online learning with abstention\([Cortes et al\., 2018](https://arxiv.org/html/2609.05820#bib.bib51)\), the agent decides whether to predict or abstain\. When the agent abstains, it pays a fixed a cost\. We incur regret in each round and decide which past rewards to observe\.

Recently, model selection under resource constraints has been studied in the context of LLMs\. Most techniques aim to reduce the cost of inference by choosing models \(LLMs\) appropriately\. The cost of inference depends on input and output token length and can be either API level cost or the compute cost of hosting and serving LLM\. Note that our notion of cost is different \- we consider the cost of labeling the LLM responses through human or other forms of gold feedback\.

A popular technique towards reducing costs is LLM cascading that invokes LLMs sequentially, progressing to higher cost LLMs, till the response is deemed satisfactory, often by another model\([Chen et al\., 2023](https://arxiv.org/html/2609.05820#bib.bib2);[Aggarwal et al\., 2023](https://arxiv.org/html/2609.05820#bib.bib3);[Ramirez et al\., 2024](https://arxiv.org/html/2609.05820#bib.bib4)\)\. More closely related to our bandit setting is LLM routing that aims to route queries directly to the appropriate model, requiring only a single inference\([Shekhar et al\., 2024](https://arxiv.org/html/2609.05820#bib.bib10);[Šakota et al\., 2024](https://arxiv.org/html/2609.05820#bib.bib9)\)\. One major difference between these works and ours is that while we aim to learn the appropriate models in an online manner \(either full information setting or bandit setting\) by selectively obtaining labels for certain queries, existing works mostly aim to predict the output quality or performance \(either absolute or relative to each other\) of the LLMs for given queries for routing them\([Ding et al\.,](https://arxiv.org/html/2609.05820#bib.bib1);[Shekhar et al\., 2024](https://arxiv.org/html/2609.05820#bib.bib10);[Shnitzer et al\., 2023](https://arxiv.org/html/2609.05820#bib.bib5);[Lu et al\., 2024](https://arxiv.org/html/2609.05820#bib.bib6);[Hari and Thomson, 2023](https://arxiv.org/html/2609.05820#bib.bib7);[Ong et al\., 2024](https://arxiv.org/html/2609.05820#bib.bib8);[Šakota et al\., 2024](https://arxiv.org/html/2609.05820#bib.bib9)\)\. The routing is based on the prediction and other considerations such as cost and latency\.

Some recent works have modeled model selection with cost considerations as a multi armed bandit problem\. MetaLLM\([Nguyen et al\., 2024](https://arxiv.org/html/2609.05820#bib.bib11)\)frames the reward as a linear combination of accuracy and cost of inference and proposes a bandit algorithm for learning the best arm\. Again, the notion of cost and the modeling of the problem are both different in our setting\. Recently, TI\-UCB\([Xia et al\., 2024](https://arxiv.org/html/2609.05820#bib.bib25)\)predicts the increase of model performances due to training or finetuning and efficiently balances exploration and exploitation in model selection\.[Dai et al\. \(2024\)](https://arxiv.org/html/2609.05820#bib.bib24)proposed CSMAB\-V based on combinatorial multi\-armed bandits to select a good LLM combination, which aims to balance cost and rewards\. This is also a different setting compared to ours\.

Other works such as[Huang et al\. \(2025\)](https://arxiv.org/html/2609.05820#bib.bib26)focused on selecting a set of LLMs under a given cost budget to maximize performance\.[Owodunni and Emezue \(2023\)](https://arxiv.org/html/2609.05820#bib.bib29)proposed a recommender system approach called Koya for selecting the best LLM for a given task and language\. There has also been work on online model selection with partial information\. In particular,[Foster et al\. \(2019\)](https://arxiv.org/html/2609.05820#bib.bib30)investigated model selection under contextual bandit feedback whereas[Cella et al\. \(2021\)](https://arxiv.org/html/2609.05820#bib.bib32)framed online model selection as a rested bandit problem\. Further,[Karimi et al\. \(2021\)](https://arxiv.org/html/2609.05820#bib.bib28)leverages active learning to identify the best model from a pool of pre\-trained classifiers\. Other recent work has focused on the orthogonal problem of leveraging LLMs for model selection[Wu et al\. \(2024\)](https://arxiv.org/html/2609.05820#bib.bib27)\. These works focus mostly on leveraging LLMs to capture the structural and semantic properties of the model for better selection\.

Online learning and bandits with observation budget have been studied extensively in the adversarial setting\. This line of work was started by[Helmbold and Panizza \(1997\)](https://arxiv.org/html/2609.05820#bib.bib35)\.[Cesa\-Bianchi et al\. \(2005\)](https://arxiv.org/html/2609.05820#bib.bib36)proved aT​\(log⁡K\)/mT\\sqrt\{\(\\log K\)/m\}regret bound for the exponentially\-weighted forecaster, whereKKis the number of experts\.[Audibert and Bubeck \(2010\)](https://arxiv.org/html/2609.05820#bib.bib39)derived aT​K⁡\(log⁡K\)/mT\\sqrt\{K\(\\log K\)/m\}regret bound for the bandit setting\. None of these works study the contextual setting\. However, their scaling with the number of roundsTTand observation budgetmmis similar to our work\. The closest related work in the stochastic bandit setting is[Tucker et al\. \(2023\)](https://arxiv.org/html/2609.05820#bib.bib55)\. This work proposes a contextual bandit algorithm but it is not analyzed\. The algorithm maximizes the difference of rewards and costs, and is not applicable to our problem because the observation cost and reward are not comparable, and thus cannot be simply subtracted\. We both propose a practical algorithm and analyze it\.

## Appendix DImplementation Details

For our experiments, we use the RouterBench\([Hu et al\., 2024](https://arxiv.org/html/2609.05820#bib.bib33)\)which is a high\-quality routing benchmark consisting a diverse set of 11 Large Language Models\. There are approximately405​k405kprompts and for each prompt, responses from the 11 models are evaluated and normalized to 0 and 1\. We randomly chose a subset of10​k10kprompts out of the total pool of405​k405kprompts\. We found no model dominates the others more than a third of the time \([Section1](https://arxiv.org/html/2609.05820#S1)\)\. Thus, we haveK=11K=11experts in this setting\. For each of the10​k10kprompts, we create its384384dimensional embedding using the bge\-small\-en\-v1\.5 model\([Xiao et al\., 2023](https://arxiv.org/html/2609.05820#bib.bib22)\)\. Next we do PCA to reduce the dimension to4040, capturing50%50\\%of the feature variance, resulting in a10000×4010000\\times 40sized data matrix\. In order to generate the expert parameters\{θa\}a∈\[K\]\\\{\\theta\_\{a\}\\\}\_\{a\\in\[K\]\}, we take the evaluated ranking from GPT\-4 for each of10​k10kprompts and create a one\-hot vector of dimension1111\. In this vector, only the model whose response has been selected as best is assigned11and we have00everywhere else\. Therefore we have a response vector of dimension10000×1110000\\times 11\. Now we obtain the parameter\{θa\}a∈\[K\]\\\{\\theta\_\{a\}\\\}\_\{a\\in\[K\]\}for each of the experts by computing the OLS estimate on this dataset\.

Table 2:Runtime in seconds with respectKK,dd, andTTon Nectar\.![Refer to caption](https://arxiv.org/html/2609.05820v1/Figures/output_full_information2.png)\(a\)Full Information Setting
![Refer to caption](https://arxiv.org/html/2609.05820v1/Figures/output_bandit.png)\(b\)Bandit Setting

Figure 2:Results comparing our approaches to the other methods \(Nectar\): \(a\)𝙽𝚘𝙻𝚘𝚘𝚔𝙱𝚊𝚌𝚔\\tt NoLookBack\(evaluates prompt at round when feedback is requested\) and \(b\)𝙰𝚕𝚕𝙵𝚎𝚎𝚍𝚋𝚊𝚌𝚔\\tt AllFeedback\(observes feedback at all rounds\)\. Clearly,𝙻𝚒𝚖𝙵𝚞𝚕𝚕𝙵𝚎𝚎𝚍\\tt LimFullFeedhas better regret guarantees than𝙽𝚘𝙻𝚘𝚘𝚔𝙱𝚊𝚌𝚔\\tt NoLookBackby careful choice of feedback\.𝙰𝚕𝚕𝙵𝚎𝚎𝚍𝚋𝚊𝚌𝚔\\tt AllFeedbacksuffers the smallest regret due to more data\.