betaFeedback

WorksComputer Science

Online Learning with LLM Experts from Limited Feedback

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 with KK actions that represent experts and dd features that encode prompts, over a horizon of TT rounds. We propose algorithms that strategically select and observe rewards to minimize regret. In the full-information setting, we achieve a regret of O~(dT/m)\tilde{O}(d T / \sqrt{m}), while in the bandit setting we achieve O~(dTK/m)\tilde{O}(d T \sqrt{K / m}), where m≪Tm \ll T is a budget on feedback. Our experiments show that we efficiently learn high-quality routing strategies across diverse LLMs from limited feedback.

Introduction

Large language models (LLMs) are pervasive nowadays. OpenAI’s GPT models ([41]), LLaMA3 ([18]), and Mistral AI ([37]) have been successfully used to solve many tasks, such as document processing and code generation. Different LLMs have different costs and capabilities ([7]). The diversity of costs, even within the same family of models, can be stark ([40]). The diverse capabilities of LLMs are obvious from public datasets. For instance, the Nectar dataset ([31]) contains responses to 183k 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 are 0.182, 0.091, 0.203, 0.319, 0.073, and 0.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 have KK different LLMs and interact with them sequentially over TT rounds. 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 ([32], [35]). This feedback is expensive, either because of human labor or computation cost, and thus we can only use it m≪Tm \ll T times, where mm is 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 ([28]; [33]; [29]) with KK experts, 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 mm rewards out of TT can 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 Section C. 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 Section C. We make the following contributions:

  1. We study the full-information setting (Section 3), 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 is O~(dT/m)\widetilde{O}(dT/\sqrt{m}), which matches our lower bound up to d\sqrt{d}. Note that the bound is O~(T)\widetilde{O}(\sqrt{T}) when m=Ω(T)m = \Omega(T).

  1. We also study the bandit setting (Section 4), 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 is O~(dTK/m)\widetilde{O}(dT\sqrt{K/m}). The additional K\sqrt{K} factor comparing to the full-information setting is due KK times less feedback.

  1. 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 Section A.

  1. We evaluate all algorithms empirically on the Nectar dataset [?] 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 (Section 5).

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.

Problem Setting

Outline: In Section 2, we state our problem and define our model. In Sections 3 and 4, we describe our algorithms for the full-information and bandit settings, respectively, along with providing theoretical guarantees. In Section A, we extend our bandit algorithm to the setting with varying costs of evaluating experts. In Section 5, we provide empirical results using our algorithms. Finally, in Section B, we provide detailed proofs for all our results.

Notation: We denote by [K][K] the set {1,2,…,K}\{1,2,\ldots,K\}. We denote scalars and vectors by lowercase letters (say xx). We denote matrices and fixed global parameters by capital letters (say XX). For a vector xx, xix_i denotes its ithi^{\text{th}} entry. For an indexed vector xjx_j, xj,ix_{j,i} denotes its ithi^{\text{th}} entry. We let ∥x∥A\lVert x\rVert_A be the weighted 2-norm xTAx\sqrt{x^{T}Ax} with respect to a positive semi-definite matrix AA. We define the corresponding inner product as ⟨x,y⟩A=xTAy\langle x,y\rangle_A=x^{T}Ay. 0d0_d and IdI_d are the zero vector and identity matrix in dd dimensions, respectively. N(0d,Σ)\mathcal{N}(0_d,\Sigma) is the Gaussian distribution in dd-dimensions with zero mean and covariance matrix Σ\Sigma. For a matrix AA, we write AiA_i to denote its ithi^{\text{th}} column. Let Bd≡{x∈Rd∣∥x∥2≤1}B^d \equiv\{x \in\mathbb{R}^{d} \mid\lVert x\rVert_2 \le1\} be the unit ball in dd dimensions.

Problem Formulation: We introduce our setting as a variant of a classic linear bandit [2]. We have TT rounds and KK LLM experts. Each expert is indexed by a∈[K]a \in[K] and associated with an unknown parameter vector θa∈Bd\theta_a \in B^d. At each round t∈[T]t \in[T], a prompt arrives and we denote it by xt∈L⋅Bdx_t \in L \cdot B^d for some L>0L > 0. The prompt is then treated as context at round tt.

Given a prompt xt∈Rdx_t \in\mathbb{R}^d, the algorithm chooses an expert at∈[K]a_t \in[K] and obtains its response. In the linear model, the expected reward for the response of expert aa in round tt is ⟨θa,xt⟩\langle\theta_a,x_t\rangle. We denote the vector of all stochastic rewards in round tt by rt=(rt,a)a=1Kr_t=(r_{t,a})_{a=1}^{K} and define each reward as

rt,a=⟨θa,xt⟩+ηa,t.(1)r_{t,a}=\langle\theta_a,x_t\rangle+\eta_{a,t}. \tag*{(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 proxy 1. 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 expert aa. This is standard in reward modeling, with the only distinction being that we do not fine-tune the embeddings.

Further, at each round tt, the context xtx_t arrives, the algorithm selects an expert ata_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 selecting ata_t, by looking back at past contexts similar to xtx_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 constraint m≪Tm \ll T. Our formulation instead leverages past feedback frugally: routing decisions are made with whatever has been learned up to round tt, 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 ([32]), due to time or monetary constraints2, and thus limited. In the classic linear bandit, the noisy reward is typically observed partially or completely at each round tt. The key difference in our setting is that the reward vector generated at any round tt is not immediately observed. However, feedback—provided as observations of rewards—is crucial for improving the selection of experts over successive rounds ([29]).

The algorithm has a budget of m<Tm < T observations, meaning that it can observe at most mm rewards, 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 round t∈[T]t \in[T], the algorithm decides to collect feedback, it may choose any round st≤ts_t \le t and observe the noisy reward vector rstr_{s_t} or its entry rst,astr_{s_t,a_{s_t}}. Many prior works in the bandit literature studied limited feedback (Section C). 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 round tt given the prompt xtx_t is

at∗=arg⁡max⁡a∈[K]⟨θa,xt⟩.a_t^* = \mathop{\arg\max}_{a \in[K]} \langle\theta_a, x_t \rangle.

We define the cumulative regret in TT rounds as

Reg⁡(T)=E[∑t=1T⟨θat∗,xt⟩−∑t=1T⟨θat,xt⟩].(2)\operatorname{Reg}(T) = \mathbb{E}\left[\sum_{t=1}^{T} \langle\theta_{a_t^*}, x_t \rangle- \sum_{t=1}^{T} \langle\theta_{a_t}, x_t \rangle\right]. \tag*{(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.

Full-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 Section 4, 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.

Algorithm

Our algorithm LimFullFeed is presented in Algorithm 1 and we describe it next. The inputs are KK LLM experts, the number of rounds TT, the feedback budget mm, and a hyperparameter λ\lambda. We also initialize all statistics for tracking reward models of all experts online (Section 2), such as the common covariance matrix V0V_0 and ordinary least squares (OLS) estimates θ^0,a\hat{\theta}_{0,a} for all experts.

In any round t∈[T]t \in[T], LimFullFeed observes a prompt xtx_t and chooses the best expert ata_t based on its estimated mean reward in eq:3. LimFullFeed may decide to obtain feedback. The feedback is obtained when ⌊b(t−1)⌋<⌊bt⌋\lfloor b(t-1) \rfloor< \lfloor bt \rfloor holds. Roughly speaking, this happens every T/mT/m rounds since b=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 by St⊆[t]S_t \subseteq[t] and let the algorithm choose any round in [t]∖St[t] \setminus S_t. We denote the chosen round by st∈[t]∖Sts_t \in[t] \setminus S_t and the observed rewards by rstr_{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\hat{\theta}_{t,a} in (5).

The technical novelty in our algorithm design is in how sts_t is chosen. We consider all past prompts {xs}s≤t\{x_s\}_{s \le t} and choose the one that maximally increases the determinant of the covariance matrix in eq:4. 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 LimFullFeed. First, the best expert in eq:3 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 (Section 4), we account for non-uniform data collection across the experts. Second, a naive implementation of LimFullFeed has a O(d3)O(d^3) per-round time complexity, due to inverting d×dd \times d matrices and computing their determinants. This can be reduced to O(d2)O(d^2) by using the Sherman-Morrison formula for the former and the matrix determinant lemma for the latter.

Main Results

Our goal is to minimize regret under the constraint of obtaining feedback at most m≤Tm \le T times. The constraint is satisfied trivially (Section 3.1). Therefore, we only need to prove a regret bound. We start by borrowing standard assumptions from linear bandit analyses [30], Chapter 19).

Assumption 3.1. All expert parameters {θa}a∈[K]\{\theta_a\}_{a \in[K]} satisfy ∥θa∥2≤1\lVert\theta_a\rVert_2 \le1. All prompts {xt}t=1T\{x_t\}_{t=1}^{T} satisfy ∥xt∥2≤L\lVert x_t\rVert_2 \le L. We also assume that max⁡a,b∈[K],t∈[T]⟨θa−θb,xt⟩≤1\max_{a,b \in[K],t \in[T]} \langle\theta_a-\theta_b,x_t\rangle\le1.

Theorem 3.2. Choose any KK experts, dd features, horizon TT, budget m<Tm < T, and λ>0\lambda> 0. Suppose that Theorem 3.1 holds. Then the regret of LimFullFeed is Reg⁡(T)=O(dTm−1/2log⁡(TL))\operatorname{Reg}(T)=O(dT m^{-1/2}\log(TL)).

Due to space constraints, we only sketch the proof. The detailed proof is in Section B.1.

Proof Sketch. Consider a fixed expert a∈[K]a \in[K] with unknown θa\theta_a and a prompt xtx_t at round tt. Using the OLS estimate θ^t,a\hat{\theta}_{t,a} for θa\theta_a, the error in estimated mean reward given by ⟨θa−θ^t,a,xt⟩\langle\theta_a-\hat{\theta}_{t,a},x_t\rangle scales as ∥xt∥Vt−1\lVert x_t\rVert_{V_{t}^{-1}}. This error can be rewritten as log⁡det⁡(Vt+xtxtT)−log⁡det⁡Vt\log\det(V_t+x_tx_t^{T})-\log\det V_t. In standard linear bandits, we update the covariance matrix Vt+1=Vt+xtxtTV_{t+1}=V_t+x_tx_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 LimFullFeed where we look back to update VtV_t with the prompt that increases its determinant most. Hence we can still bound log⁡det⁡(Vt+xtxtT)−log⁡det⁡Vt\log\det(V_t+x_tx_t^{T})-\log\det V_t from above by log⁡det⁡Vt+1−log⁡det⁡Vt\log\det V_{t+1}-\log\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 of T/mT/m rounds. Therefore we still get a telescoping sum after adding the errors but the limited feedback leads to an extra multiplicative factor of T/mT/m in the telescoping sum. This leads to an additional multiplicative factor of T/m\sqrt{T/m} in the regret bound.

Note that regret does not depend on the number of experts KK since in the full-information setting, we obtain responses for all experts jointly. Therefore, when m=Tm=T, we can obtain feedback for all rounds and the regret guarantee that is achieved is O(dTlog⁡T)O(d\sqrt{T}\log T). This is reminiscent of the standard regret guarantee achieved for linear bandits [30]. The additional cost of limited feedback arises in the form of a multiplicative factor of T/m\sqrt{T/m} leading to higher cost with lesser feedback. We also prove the following lower bound (detailed proof is in Section B.4).

Theorem 3.3. Consider the online expert selection problem with limited full information feedback, dd features, KK experts, horizon TT, feedback budget of m<Tm<T. Suppose all observations are Gaussian random variables with noise variance 1. 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

Reg⁡(T)≥Tdexp⁡(−4)8m.\operatorname{Reg}(T) \ge\frac{T\sqrt{d}\exp(-4)}{8\sqrt{m}}.

Discussion: Note that there is a gap of d\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 rounds tt we need to bound ⟨θa−θ^t,a,x⟩\langle\theta_a-\hat{\theta}_{t,a},x\rangle for all possible prompts x∈Rdx\in\mathbb{R}^{d} and all experts a∈[K]a\in[K]. Such bounds are obtained in online settings with correlated observed random variables via a tail inequality on self-normalized martingales [3].

Intuitively, ensuring the error bound is small for all vectors in the dd-dimensional space leads to a union bound over dd dimensions that in turn leads to the additional d\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 TT vectors instead of all vectors in Rd\mathbb{R}^{d}. This removes the additional d\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 in mm. 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 subset SS of mm most-informative prompts, obtain feedback, and learn the expert parameters from them. The regret of this approach would be O(Tmax⁡t∈[T]∥xt∥V−1)O(T\max_{t\in[T]}\|x_t\|_{V^{-1}}), where max⁡t∈[T]∥xt∥V−1\max_{t\in[T]}\|x_t\|_{V^{-1}} is the maximum confidence interval width and V=∑i∈SxixiTV=\sum_{i\in S}x_ix_i^{T}. An optimal solution to this problem is known as the G-optimal optimal design [30], Chapter 21 and its maximum confidence interval width is O(d/m)O(\sqrt{d/m}). This leads to a regret of O(Td/m)O(T\sqrt{d/m}) over TT rounds 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 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.

Bandit 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

Here we describe our proposed algorithm LimBanFeed (Algorithm 2) that chooses experts to generate response in the bandit feedback setting. Since different experts can potentially get feedback different number of times, LimBanFeed Algorithm 2 LimBanFeed: Limited bandit feedback for expert selection.

  1. Initialize z←T/mz \leftarrow T/m, V0,a←λIdV_{0,a} \leftarrow\lambda I_d, S0,a←∅S_{0,a} \leftarrow\emptyset; and y0,a←0dy_{0,a} \leftarrow0_d, θ^0,a←0d\hat{\theta}_{0,a} \leftarrow0_d for all a∈[K]a \in[K].

  2. for rounds t=1,2,…,Tt = 1, 2, \ldots, T do

  3. Obtain prompt xtx_t, choose expert ata_t and increase its counter by 1.

at=arg⁡max⁡a∈[K]⟨θ^t−1,a,xt⟩+β∥xt∥Vt−1,a−1(3)a_t = \arg\max_{a \in[K]} \langle\hat{\theta}_{t-1,a}, x_t \rangle+ \beta\lVert x_t \rVert_{V_{t-1,a}^{-1}} \tag*{(3)}

nat←nat+1n_{a_t} \leftarrow n_{a_t} + 1

  1. if nat≥zn_{a_t} \ge z then

  2. Find the most informative past observation for the expert ata_t. Reset its counter.

st=arg⁡max⁡s∈{s∈[t]:as=at}∖St−1,atdet⁡(Vt−1,at+xsxsT)(4)s_t = \arg\max_{s \in\{s \in[t]:a_s=a_t\}\setminus S_{t-1,a_t}} \det\left(V_{t-1,a_t} + x_s x_s^{T}\right) \tag*{(4)}

nat←0n_{a_t} \leftarrow0

  1. Observe reward rst,atr_{s_t,a_t} for the expert ata_t and update the corresponding statistics for ata_t.

Vt,at←Vt−1,at+xstxstT,St,at←St−1,at+{st}V_{t,a_t} \leftarrow V_{t-1,a_t} + x_{s_t}x_{s_t}^{T}, \quad S_{t,a_t} \leftarrow S_{t-1,a_t} + \{s_t\}
∀a∈[K]:yt,at←yt−1,at+rst,atxst,θ^t,at←Vt,at−1yt,at(5)\forall a \in[K]: y_{t,a_t} \leftarrow y_{t-1,a_t} + r_{s_t,a_t}x_{s_t}, \quad\hat{\theta}_{t,a_t} \leftarrow V_{t,a_t}^{-1}y_{t,a_t} \tag*{(5)}
  1. else

  2. Update Vt,a←Vt−1,a,yt,a←yt−1,a,θ^t,a=θ^t−1,aV_{t,a} \leftarrow V_{t-1,a}, y_{t,a} \leftarrow y_{t-1,a}, \hat{\theta}_{t,a} = \hat{\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].

adaptively 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.

LimBanFeed takes as input the same parameters as LimFullFeed along with the additional hyperparameter β\beta corresponding to the confidence width. In the bandit setting, we initialize the covariance matrix V0,aV_{0,a} along with other hyperparameters separately for each expert a∈[K]a \in[K]. In Line 2, we also initialize a variable zz which is set to be the average number of rounds between feedback, namely T/mT/m.

At each round tt, the prompt xtx_t arrives as context. Given the input prompt xtx_t, LimBanFeed chooses the expert ata_t in (3) 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 counter nan_a for every expert a∈[K]a \in[K] that keeps track of the number of times an expert is chosen for generating response. Once an expert has been used zz times, 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 of zz helps respect the overall feedback budget of mm rounds. The number of rounds where an expert a∈[K]a \in[K] has been used to generate a response in the time horizon TT is ∣ST,a∣\lvert S_{T,a}\rvert, hence the number of times the atha^{\mathrm{th}} expert has been evaluated is ⌊∣ST,a∣/z⌋\lfloor\lvert S_{T,a}\rvert/ z \rfloor.

Setting z≥T/mz \ge T/m helps satisfy the feedback budget mm:

∑a∈[K]⌊∣ST,a∣z⌋≤∑a∈[K]∣ST,a∣z=Tz≤m  ⟹  z≥Tm.\sum_{a \in[K]} \left\lfloor\frac{\lvert S_{T,a}\rvert}{z} \right\rfloor\le\sum_{a \in[K]} \frac{\lvert S_{T,a}\rvert}{z} = \frac{T}{z} \le m \implies z \ge\frac{T}{m}.

For getting feedback for an expert aa, LimBanFeed chooses a prompt index among the past prompts that maximizes the increase in the determinant of the covariance matrix for the expert aa (see (4)). We only choose prompts that have not yet been evaluated.

We update the OLS estimate of the parameter vector θ^t,a\hat{\theta}_{t,a} for expert ata_t (see (5)) by using the observed scalar reward rst,ar_{s_t,a} for the chosen prompt.

Main Results

We show our main result below:

Theorem 4.1. Consider the online expert selection problem with limited bandit feedback, KK experts, dd features, horizon TT and feedback budget m<Tm < T. Suppose Assumption 3.1 is true. Then for any λ≥0\lambda\ge0 and β=λ+6log⁡T+dlog⁡(1+TL2/d)\beta= \sqrt{\lambda} + \sqrt{6\log T + d\log(1 + TL^2/d)}, the regret of LimBanFeed is

Reg⁡(T)=O(dTK1/2m−1/2log⁡(TL)).\operatorname{Reg}(T) = O(dTK^{1/2}m^{-1/2}\log(TL)).

The detailed proof is provided in Appendix B.2, 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 round tt for expert aa, 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\lVert x_t\rVert_{V_{t-1,a}} from above. Additionally, in our analysis, we use the fact that each expert is updated after being used z=⌈T/m⌉z = \lceil T/m\rceil times. 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 is KK times 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 of K\sqrt{K}.

Further, when m=Tm = T that is, we can obtain feedback for all rounds, Algorithm 2 achieves a regret guarantee of O(dTKlog⁡(TL))O(d\sqrt{TK}\log(TL)). As in the full-information setting, the cost of limited feedback is a multiplicative factor of T/m\sqrt{T/m}. Next, we prove a lower bound on the regret in the bandit feedback setting (detailed proof is in Section B.4):

Theorem 4.2. Consider the online expert selection problem with limited bandit feedback, dd features, KK experts, horizon TT, feedback budget of m<Tm < T. Suppose all observations are Gaussian random variables with noise variance 1. 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

Reg⁡(T)≥TKexp⁡(−4)8m\operatorname{Reg}(T) \ge\frac{TK\exp(-4)}{8\sqrt{m}}

There is a gap of d/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 a KK-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 Ω(TK/m)\Omega(T\sqrt{K/m}), which is looser by a factor of K\sqrt{K}. Similar to the full-information setting, the upper bound includes an additional factor of d\sqrt{d} due to the algorithm’s lack of knowledge about the prompt vectors, requiring a union bound over all vectors in the dd-dimensional space. This extra factor can be eliminated if the algorithm has prior knowledge of the prompts. The remaining gap of d/K\sqrt{d/K} persists because the lower bound analysis is based on hypothesis testing with KK vectors and may be further improved. It will be an interesting direction of future work to improve the lower bound in the bandit setting.

Experiments

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

Datasets and Baselines. We consider two widely used routing benchmarks: RouterBench[22] and Nectar[?] . 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. NoLookBack requests 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. AllFeedback assumes access to feedback at every round and serves as a performance upper bound.

We simulate an online routing process over a fixed horizon TT, with a feedback budget m≪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.

Main Results. Figure 1 and Figure 2 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 LimFullFeed consistently outperforms 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), LimFullFeed achieves noticeably lower regret than 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, LimFullFeed reduces uncertainty more efficiently and accelerates learning. In contrast, NoLookBack queries feedback only at the current round, which leads to less informative data collection and slower error reduction. We also observe that the variance of AllFeedback is consistently smaller across rounds. This is expected, as AllFeedback has access to substantially more feedback, resulting in more stable estimates and reduced variability across runs.

Algorithm 1 LimFullFeed: Limited full-information feedback for expert selection.

Figure 1.

Results comparing regret across feedback settings

Figure 1. Results comparing our approaches to the other methods (RouterBench): (a) NoLookBack (evaluates prompt at round when feedback is requested) and (b) AllFeedback (observes feedback at all rounds). Clearly, LimFullFeed has better regret guarantees than NoLookBack by careful choice of feedback. AllFeedback suffers the smallest regret due to more data.

Full Information Setting plot

(a) Full Information Setting

Bandit Setting plot

(b) Bandit Setting

Figure 2. Results comparing our approaches to the other methods (Nectar): (a) NoLookBack (evaluates prompt at round when feedback is requested) and (b) AllFeedback (observes feedback at all rounds). Clearly, LimFullFeed has better regret guarantees than NoLookBack by careful choice of feedback. AllFeedback suffers the smallest regret due to more data.

The same trend holds in the bandit setting, where LimBanFeed consistently achieves lower regret than NoLookBack, with the gap increasing over time. As in the full-information setting, AllFeedback exhibits 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 shows that regret decreases as mm increases, consistent with the T/m\sqrt{T}/m dependence in our theory. In the bandit setting, LimBanFeed consistently outperforms NoLookBack, with the gap widening for larger mm. In the full-information setting, the gap is smaller for small mm, since each feedback reveals all experts, but LimFullFeed becomes competitive as mm increases.

Full-informationBandit
mmLimFullFeedNoLookBackLimBanFeedNoLookBack
1000672.9 ± 37.4631.6 ± 22.13583.4 ± 68.03789.6 ± 30.4
2000441.4 ± 42.6408.0 ± 26.23084.1 ± 25.63580.0 ± 73.3
5000214.1 ± 7.7218.7 ± 10.62295.7 ± 42.33020.7 ± 17.2
10000128.0 ± 8.7129.0 ± 11.01839.1 ± 29.12538.4 ± 22.2
2000073.6 ± 6.075.8 ± 6.11567.9 ± 13.42090.7 ± 21.2

Table 1. Cumulative regret with respect to feedback budget mm on Nectar (K=6K=6, d=40d=40, T=60000T=60000).

Runtime Analysis. Table 2 shows that both methods scale approximately linearly with TT. LimBanFeed scales linearly with KK, while LimFullFeed is largely independent of KK due to its shared covariance structure.

AxisValueLimBanFeedLimFullFeed
KK22.67±0.022.67 \pm0.021.73±0.341.73 \pm0.34
64.30±0.034.30 \pm0.031.49±0.011.49 \pm0.01
105.93±0.045.93 \pm0.041.47±0.011.47 \pm0.01
168.36±0.028.36 \pm0.021.49±0.041.49 \pm0.04
209.97±0.009.97 \pm0.001.47±0.001.47 \pm0.00
dd84.25±0.004.25 \pm0.001.49±0.041.49 \pm0.04
244.24±0.004.24 \pm0.001.46±0.001.46 \pm0.00
404.27±0.044.27 \pm0.041.47±0.001.47 \pm0.00
964.34±0.004.34 \pm0.001.51±0.011.51 \pm0.01
1284.34±0.004.34 \pm0.001.54±0.041.54 \pm0.04
TT5000.41±0.000.41 \pm0.000.15±0.000.15 \pm0.00
1,0000.82±0.000.82 \pm0.000.29±0.000.29 \pm0.00
5,0004.27±0.044.27 \pm0.041.47±0.001.47 \pm0.00
10,0008.89±0.028.89 \pm0.022.98±0.052.98 \pm0.05
15,00014.35±0.0314.35 \pm0.034.47±0.034.47 \pm0.03

Table 2. Runtime in seconds with respect KK, dd, and TT on Nectar.

Conclusions

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.

Bandit Feedback with Variable Costs

We can also extend Algorithm 2 to the setting where the KK experts have different costs of being evaluated and there is a budget on the overall cost. More precisely, suppose the total cost budget is mm and the cost of evaluation of the jthj^{\text{th}} expert is z~j\tilde{z}_j. Without loss of generality, we can assume that z~1≥z~2≥⋯≥z~K\tilde{z}_1 \ge\tilde{z}_2 \ge\cdots\ge\tilde{z}_K. For the expert jj with cost z~j\tilde{z}_j, we evaluate it after it has been used z~j⋅z~\tilde{z}_j \cdot\tilde{z} times for some z~≥0\tilde{z} \ge0.

In other words, the experts is evaluated with a frequency that is proportional to their cost. In Algorithm 2, each expert had the same cost and therefore, the strategy of evaluation is identical for every expert. Now, given the budget on the feedback rounds mm, z~\tilde{z} can be computed as follows: Again, recall that the number of rounds where the expert aa has been used to generate a response in the entire time horizon is ∣ST,a∣\lvert S_{T,a}\rvert. In that case, the number of times the atha^{\text{th}} expert has been evaluated is ⌊∣ST,a∣z~j⋅z~⌋\left\lfloor\frac{\lvert S_{T,a}\rvert}{\tilde{z}_j \cdot\tilde{z}}\right\rfloor. We need the total cost to be smaller than mm, hence,

∑j⌊∣ST,a∣z~j⋅z~⌋⋅z~j≤∑j∣ST,a∣z~j⋅z~⋅z~j=∑j∣ST,a∣z~=Tz~≤m⟹z~≥Tm.\sum_j \left\lfloor\frac{\lvert S_{T,a}\rvert}{\tilde{z}_j \cdot\tilde{z}}\right\rfloor\cdot\tilde{z}_j \le\sum_j \frac{\lvert S_{T,a}\rvert}{\tilde{z}_j \cdot\tilde{z}} \cdot\tilde{z}_j = \sum_j \frac{\lvert S_{T,a}\rvert}{\tilde{z}} = \frac{T}{\tilde{z}} \le m \Longrightarrow\tilde{z} \ge\frac{T}{m}.

Now the entire analysis proceeds in the same way as the proof for Theorem 4.1. The only difference lies in the non-uniform rate at which each expert is updated. More precisely, instead of a common interval length of zz for every expert a∈[K]a \in[K] as in Algorithm 2, now we have an interval length of za⋅z~z_a \cdot\tilde{z} for the atha^{\text{th}} expert. Going through the same set of calculations, we can show that the regret guarantee in this case is going to be

Reg⁡(T)=O(Tm−1/2dβ(∑jzj)log⁡(dλ+md)).\operatorname{Reg}(T) = O\left(Tm^{-1/2}\sqrt{d\beta\left(\sum_j z_j\right)\log\left(\frac{d\lambda+ m}{d}\right)}\right).

Substituting the value of βm/K\beta_{m/K} as in Theorem 4.1, the final regret guarantee can be written as

Reg⁡(T)=O(dTm−1/2(∑jzj)1/2log⁡T).\operatorname{Reg}(T) = O\left(dTm^{-1/2}\left(\sum_j z_j\right)^{1/2}\log T\right).

Notice that when all the costs are 11, we get the same regret guarantee as in Theorem 4.1. Further, as is common in this framework, the additional cost of limited feedback comes in the form of a multiplicative factor of T/m\sqrt{T/m}.

Detailed Proofs

Proof of Theorem 3.2

Proof of Theorem 3.2. Notations: We start by setting up some notations. Let Ot⊆[t]O_t \subseteq[t] denote the set of rounds until (including) round tt in which the algorithm chooses to get feedback. Note that Ot⊆Ot′O_t \subseteq O_{t'} for all t′≥tt' \ge t. For the set of prompts evaluated until round tt, recall StS_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 \land(\ell- 1) \notin O_t\} denote the last round before round tt when the experts were updated. We denote a∧b=min⁡(a,b)a \land b = \min(a,b).

We can decompose the RHS in (2) 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⟩.\sum_{t=1}^{T}\langle\theta_{a_t^*},x_t\rangle-\sum_{t=1}^{T}\langle\theta_{a_t},x_t\rangle =\sum_{t=1}^{T}\langle\theta_{a_t^*}-\widehat{\theta}_{t,a_t^*},x_t\rangle+\sum_{t=1}^{T}\langle\widehat{\theta}_{t,a_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 index αt\alpha_t at each round tt such that ⟨θ^t,at⋆−θ^t,at,xt⟩≤0\langle\hat{\theta}_{t,a_t^\star} - \hat{\theta}_{t,a_t}, x_t \rangle\le0. 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 round tt by Vt−1V_{t-1}. Recall that feedback is solicited at every interval of T/mT/m rounds. 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 [30]), we have the following at every round t∈[T]t \in[T] and every expert a∈[K]a \in[K] with probability at least 1−o(T−2)1-o(T^{-2}):

∥θt−θ^t,a∥Vt−1≤β where β=λ+6log⁡T+dlog⁡(dλ+mL2dλ).(6)\left\|\theta_t-\hat{\theta}_{t,a}\right\|_{V_{t-1}} \le\beta\text{ where } \beta= \sqrt{\lambda}+\sqrt{6\log T+d\log\left(\frac{d\lambda+mL^2}{d\lambda}\right)}. \tag*{(6)}

Denote the event E\mathcal{E} where (6) is true for all rounds t∈[T]t \in[T] and all experts a∈[K]a \in[K]. Moving forward, we can now condition on the above high probability event E\mathcal{E}. We now show the following for any round tt:

⟨θat⋆,xt⟩−⟨θat,xt⟩≤∥θat⋆−θ^t,at⋆∥Vt−1−1∥xt∥Vt−1+∥θ^t,at−θat∥Vt−1−1∥xt∥Vt−1≤2β∥xt∥Vt−1=2β∥xt∥Vτt−1.(7)\langle\theta_{a_t^\star},x_t\rangle-\langle\theta_{a_t},x_t\rangle\le\left\|\theta_{a_t^\star}-\hat{\theta}_{t,a_t^\star}\right\|_{V_{t-1}^{-1}}\|x_t\|_{V_{t-1}}+\left\|\hat{\theta}_{t,a_t}-\theta_{a_t}\right\|_{V_{t-1}^{-1}}\|x_t\|_{V_{t-1}} \le2\beta\|x_t\|_{V_{t-1}}=2\beta\|x_t\|_{V_{\tau_t}^{-1}}. \tag*{(7)}

The last step follows from the fact that by definition τt,at\tau_{t,a_t} is the last round (before round tt) when the expert ata_t had been updated. Note that for each round tt, we also have ⟨θat⋆,xt⟩−⟨θat,xt⟩≤1\langle\theta_{a_t^\star},x_t\rangle-\langle\theta_{a_t},x_t\rangle\le1 from the assumption in theorem statement. Therefore, we can combine to show

∑t=1T⟨θat⋆,xt⟩−∑t=1T⟨θat,xt⟩≤2β∑t=1T(1∧∥xt∥Vτt−1)≤2Tβ∑t=1T(1∧∥xt∥Vτt−12)\sum_{t=1}^{T}\langle\theta_{a_t^\star},x_t\rangle-\sum_{t=1}^{T}\langle\theta_{a_t},x_t\rangle\le2\beta\sum_{t=1}^{T}\left(1\wedge\|x_t\|_{V_{\tau_t}^{-1}}\right)\le2\sqrt{T\beta\sum_{t=1}^{T}\left(1\wedge\|x_t\|_{V_{\tau_t}^{-1}}^2\right)}

where the final step follows from application of Cauchy-Schwarz inequality. Now, continuing from (7), for any round tt, we use the fact that for any u≥0u\ge0, we have u∧1≤2log⁡(1+u)u\wedge1\le2\log(1+u):

1∧∥xt∥Vτt−12≤log⁡(1+∥xt∥Vτt−12)=log⁡det⁡(I+Vτt−1/2xtxtTVτt−1/2)=log⁡det⁡(Vτt+xtxtT)−log⁡det⁡Vτt\begin{aligned} 1\wedge\|x_t\|_{V_{\tau_t}^{-1}}^2\le\log\left(1+\|x_t\|_{V_{\tau_t}^{-1}}^2\right)=\log\det\left(I+V_{\tau_t}^{-1/2}x_tx_t^{\mathsf{T}}V_{\tau_t}^{-1/2}\right) \\ &=\log\det\left(V_{\tau_t}+x_tx_t^{\mathsf{T}}\right)-\log\det V_{\tau_t} \end{aligned}

Now, consider a round t∈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, recall that sts_t was the prompt chosen at round t∈OTt\in O_T for feedback following which we had updated Vt−1=Vτt+xstxstTV_{t-1}=V_{\tau_t}+x_{s_t}x_{s_t}^{\mathsf{T}}. Further, recall that the prompt index sts_t at round tt was chosen in the following way:

st=arg⁡max⁡ℓ∈[t]∖St−1det⁡(Vt−1+xℓxℓT)=arg⁡max⁡ℓ∈[t]∖St−1det⁡(Vτt+xℓxℓT)s_t=\mathop{\arg\max}_{\ell\in[t]\setminus S_{t-1}}\det\left(V_{t-1}+x_\ell x_\ell^{\mathsf{T}}\right)=\mathop{\arg\max}_{\ell\in[t]\setminus S_{t-1}}\det\left(V_{\tau_t}+x_\ell x_\ell^{\mathsf{T}}\right)

implying that the prompt sts_t increases the determinant of the covariance matrix VτtV_{\tau_t} the most. Thus, for every round r∈[τt+1,t]r\in[\tau_t+1,t], we must have det⁡(Vr+xrxrT)=det⁡(Vτt+xrxrT)≤det⁡(Vτt+xstxstT)\det(V_r+x_rx_r^{\mathsf{T}})=\det(V_{\tau_t}+x_rx_r^{\mathsf{T}})\le\det(V_{\tau_t}+x_{s_t}x_{s_t}^{\mathsf{T}}). Hence, we have

∑r∈[τt+1,t]log⁡det⁡(Vr+xrxrT)≤⌈T/m⌉log⁡det⁡(Vτt+xstxstT)=⌈T/m⌉log⁡det⁡Vt−1.\sum_{r\in[\tau_t+1,t]}\log\det(V_r+x_rx_r^{\mathsf{T}})\le\lceil T/m\rceil\log\det(V_{\tau_t}+x_{s_t}x_{s_t}^{\mathsf{T}})=\lceil T/m\rceil\log\det V_{t-1}.

Therefore, using the fact that the covariance matrix remains unchanged for T/mT/m rounds, we can write

∑t=1T(1∧∥xt∥Vτt−12)≤⌈T/m⌉∑t∈OT(log⁡det⁡Vt−log⁡det⁡Vτt)+Tm−1=⌈T/m⌉(log⁡det⁡VT−log⁡det⁡V0)+Tm−1.\begin{aligned} \sum_{t=1}^{T}\left(1\wedge\|x_t\|_{V_{\tau_t}^{-1}}^2\right)\le\lceil T/m\rceil\sum_{t\in O_T}\left(\log\det V_t-\log\det V_{\tau_t}\right)+Tm^{-1} \\ &=\lceil T/m\rceil\left(\log\det V_T-\log\det V_0\right)+Tm^{-1}. \end{aligned}

Notice that Vt−1=∑t∈OTxtxtTV_{t-1} = \sum_{t \in O_T} x_t x_t^{T}, ∣OT∣=m|O_T| = m (since we are getting feedback for mm rounds). Moreover, for all prompts {xt}t∈[T]\{x_t\}_{t \in[T]}, we have Tr⁡(xtxtT)=∥xt∥22≤1\operatorname{Tr}(x_t x_t^{T}) = \|x_t\|_2^2 \le1 since all prompts are within the unit ball. Now, we use the AM-GM inequality and linearity of trace operation to show

det⁡VT≤(d−1Tr⁡(VT))d≤(d−1(Tr⁡(V0)+m))d\det V_T \le\left(d^{-1}\operatorname{Tr}(V_T)\right)^d \le\left(d^{-1}\left(\operatorname{Tr}(V_0)+m\right)\right)^d

We have Tr⁡(V0)≤dλ\operatorname{Tr}(V_0) \le d\lambda and therefore, we bound the regret conditioned on the event E\mathcal{E} (denote by Reg⁡(T)∣E\operatorname{Reg}(T) \mid\mathcal{E}) as

Reg⁡(T)∣E=O(Tm−1/2dβlog⁡(dλ+md))\operatorname{Reg}(T) \mid\mathcal{E} = O\left(Tm^{-1/2}\sqrt{d\beta\log\left(\frac{d\lambda+m}{d}\right)}\right)

When the event E\mathcal{E} is false, then the regret can be bounded by the 2T2T (worst-case). Therefore the final regret can be written as

Reg⁡(T)=Reg⁡(T)∣E+2TPr⁡(Ec)=Reg⁡(T)∣E+o(T−1).\operatorname{Reg}(T) = \operatorname{Reg}(T) \mid\mathcal{E} + 2T\Pr(\mathcal{E}^{c}) = \operatorname{Reg}(T) \mid\mathcal{E} + o(T^{-1}).

Now, we can substitute the value for β\beta to obtain the final theorem statement.

Proof of Theorem 4.1

Proof of Theorem 4.1. Notations: We start by introducing new notations. For any expert a∈[K]a \in[K], let Ot,a⊆[t]O_{t,a} \subseteq[t] denote the set of rounds until round tt in which the algorithm has opted to obtain a feedback for expert aa. As before, for any a∈[K]a \in[K], we have Ot,a⊆Ot′,aO_{t,a} \subseteq O_{t',a} for all t′≥tt' \ge t. Similar to full-information, for the set of prompts evaluated until round tt, define StS_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} \land(\ell-1) \notin O_{t,a}\} denote the last round before round tt when the expert aa was updated.

As in the proof of Theorem 3.2, we will exploit standard guarantees on confidence sets regarding the OLS estimator in the linear model. We have the following at every round t∈[T]t \in[T] and every expert a∈[K]a \in[K] with probability at least 1−o(T−2)1-o(T^{-2}):

∥θt−θ^t,a∥Vt−1,a≤β where β=λ+6log⁡T+dlog⁡(dλ+mL2dλ).(8)\left\|\theta_t-\widehat{\theta}_{t,a}\right\|_{V_{t-1,a}} \le\beta\text{ where } \beta= \sqrt{\lambda}+\sqrt{6\log T+d\log\left(\frac{d\lambda+mL^2}{d\lambda}\right)}. \tag*{(8)}

Denote the event E\mathcal{E} where (8) is true for all rounds t∈[T]t \in[T] and all experts a∈[K]a \in[K]. For any prompt xtx_t at round tt, 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⟩.\widetilde{\theta}_{t,a} = \sup_{\phi\in\left\|\phi-\widehat{\theta}_{t,a}\right\|_{V_{t-1,a}}\le\beta} \langle\phi,x_t\rangle.

and therefore, the expert ata_t to generate the response is chosen as max⁡a∈[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 [30])

at=arg⁡max⁡a∈[K] ⟨θ^t,a,xt⟩+β⋅∥xt∥Vt−1,a−1a_t = \underset{a\in[K]}{\arg\max}\ \langle\widehat{\theta}_{t,a},x_t\rangle+\beta\cdot\|x_t\|_{V_{t-1,a}^{-1}}

Now, we can decompose the RHS in (2) for any round t∈[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⟩\langle\theta_{a_t^\star},x_t\rangle-\langle\theta_{a_t},x_t\rangle\le\langle\widehat{\theta}_{a_t^\star},x_t\rangle+\beta\|x_t\|_{V_{t,a_t^\star}^{-1}}-\langle\theta_{a_t},x_t\rangle\le\langle\widehat{\theta}_{a_t},x_t\rangle+\beta\|x_t\|_{V_{t,a_t}^{-1}}-\langle\theta_{a_t},x_t\rangle

For the first inequality we bound the reward for the expert at⋆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_t^\star}-\widetilde{\theta}_{t,a_t},x_t\rangle\le0. This is because, by choice of our algorithm, we have picked the expert index ata_t at each round tt having the largest upper confidence reward on prompt xtx_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 expert a∈[K]a \in[K] at round tt by Vt−1,aV_{t-1,a}. Again, recall that feedback is solicited for expert aa after the expert aa has been used to generate a response zz times. Now, we can show the following for any round tt

⟨θat∗,xt⟩−⟨θat,xt⟩≤β∥xt∥Vt−1,at+∥θ^t,at−θat∥Vt,at∥xt∥Vt,at−1≤2β∥xt∥Vt,at−1\langle\theta_{a_t^*}, x_t\rangle- \langle\theta_{a_t}, x_t\rangle\le\beta\lVert x_t\rVert_{V_{t-1,a_t}} + \lVert\widehat{\theta}_{t,a_t} - \theta_{a_t}\rVert_{V_{t,a_t}} \lVert x_t\rVert_{V_{t,a_t}^{-1}} \le2\beta\lVert x_t\rVert_{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=∑a=1K∑t=1T∥xt∥Vt,at−11[at=a]≤∑a=1K∑t=1T(1∧∥xt∥Vt,at−1)1[at=a]≤T∑a=1K∑t=1T(1∧∥xt∥Vt,at−12)1[at=a]\begin{aligned} \sum_{t=1}^{T} \lVert x_t\rVert_{V_{t,a_t}^{-1}} = \sum_{a=1}^{K}\sum_{t=1}^{T} \lVert x_t\rVert_{V_{t,a_t}^{-1}} \mathbf{1}[a_t=a] \\ &\le\sum_{a=1}^{K}\sum_{t=1}^{T} \left(1 \wedge\lVert x_t\rVert_{V_{t,a_t}^{-1}}\right)\mathbf{1}[a_t=a] \\ &\le\sqrt{T\sum_{a=1}^{K}\sum_{t=1}^{T}\left(1 \wedge\lVert x_t\rVert_{V_{t,a_t}^{-1}}^2\right)\mathbf{1}[a_t=a]} \end{aligned}

In the pre-final step, we used that in each round tt, we also have ⟨θat∗,xt⟩−⟨θat,xt⟩≤1\langle\theta_{a_t^*}, x_t\rangle- \langle\theta_{a_t}, x_t\rangle\le1 from the assumption in theorem statement. In the final step, we used the Cauchy-Schwarz inequality. Note that there are only TT terms in the RHS since at each round, only a single expert is chosen. Consider a particular expert a∈[K]a \in[K] - it is chosen for obtaining feedback after being used for generating responses zz times since the last time feedback was obtained for expert aa.

At any round tt, recall τt,a=max⁡{ℓ∈[t−1]:ℓ∈Ot,a∧(ℓ−1)∉Ot,a}\tau_{t,a} = \max\{\ell\in[t-1] : \ell\in O_{t,a} \land(\ell-1) \notin O_{t,a}\} denote the last round from tt when the expert aa was chosen for obtaining feedback (after the counter for expert areacheda reachedz).Foranyround). For any roundt \in O_{t,a},asperournotation,recallthat, as per our notation, recall thatV_{t-1,a}isthecovariancematrixfortheexpertis the covariance matrix for the expertaatroundat roundt.Then. Then\tau_{t-1,a}isthepreviousroundwhentheexpertis the previous round when the expertawas updated. For any round t\text{was updated. For any round } tt,wecanusethefactthatforany, we can use the fact that for anyu \ge 0,wehave, we haveu \wedge 1 \le 2\log(1+u)$,

1∧∥xt∥Vt,at−12≤log⁡(1+∥xt∥Vt,at−12)=log⁡det⁡(I+Vt,at−1/2xtxtTVt,at−1/2)=log⁡det⁡(Vt,at+xtxtT)−log⁡det⁡Vt,at=log⁡det⁡(Vτt,at,at+xtxtT)−log⁡det⁡Vτt,at,at\begin{aligned} 1 \wedge\lVert x_t\rVert_{V_{t,a_t}^{-1}}^2 \le\log\left(1+\lVert x_t\rVert_{V_{t,a_t}^{-1}}^2\right) = \log\det\left(I+V_{t,a_t}^{-1/2}x_tx_t^{T}V_{t,a_t}^{-1/2}\right) \\ &= \log\det\left(V_{t,a_t}+x_tx_t^{T}\right)-\log\det V_{t,a_t} = \log\det\left(V_{\tau_{t,a_t},a_t}+x_tx_t^{T}\right)-\log\det V_{\tau_{t,a_t},a_t} \end{aligned}

Now for a fixed expert a∈[K]a \in[K], consider a round t∈OT,at \in O_{T,a} where feedback has been observed for some prompt in the history of expert aa. As we defined before, τt−1,a\tau_{t-1,a} corresponds to the previous round in history (relative to round tt) where feedback has been observed for expert aa. From Algorithm 2, recall that sts_t was the prompt chosen at round t∈Ot,at \in O_{t,a} for feedback following which we had updated Vt−1,a=Vτt−1,a+xstxstTV_{t-1,a} = V_{\tau_{t-1,a}} + x_{s_t}x_{s_t}^{T}. Further, recall that the prompt index sts_t at round tt was chosen in the following way:

st=arg⁡max⁡s∈{s∈[t]:as=a}∖St−1,a det⁡(Vt−1,a+xsxsT)=arg⁡max⁡s∈{s∈[t]:as=a}∖St−1,a det⁡(Vτt−1,a,a+xsxsT)s_t = \underset{s\in\{s\in[t]:a_s=a\}\setminus S_{t-1,a}}{\arg\max}\ \det(V_{t-1,a}+x_sx_s^{T}) = \underset{s\in\{s\in[t]:a_s=a\}\setminus S_{t-1,a}}{\arg\max}\ \det(V_{\tau_{t-1,a},a}+x_sx_s^{T})

implying that the prompt sts_t was responded to by the expert ata_t and further, the prompt sts_t increases the determinant of the covariance matrix Vτt−1,a,aV_{\tau_{t-1,a},a} the most. Thus, for every round r∈[τt−1,a+1,t]r \in[\tau_{t-1,a}+1,t] satisfying 1[ar=a]\mathbf{1}[a_r=a], we must have det⁡(Vr,a+xrxrT)=det⁡(Vτt−1,a,a+xrxrT)≤det⁡(Vτt−1,a,a+xstxstT)\det(V_{r,a}+x_rx_r^{T}) = \det(V_{\tau_{t-1,a},a}+x_rx_r^{T}) \le\det(V_{\tau_{t-1,a},a}+x_{s_t}x_{s_t}^{T}). Hence, we have

∑r∈[τt−1,a+1,t]log⁡det⁡(Vr,a+xrxrT)≤c⋅log⁡det⁡(Vτt−1,a,a+xstxstT)=⌈T/m⌉log⁡det⁡Vt−1,a.(9)\sum_{r\in[\tau_{t-1,a}+1,t]} \log\det(V_{r,a}+x_rx_r^{T}) \le c\cdot\log\det(V_{\tau_{t-1,a},a}+x_{s_t}x_{s_t}^{T}) = \lceil T/m\rceil\log\det V_{t-1,a}. \tag*{(9)}

In the last step, we used the threshold on zz that would meet the feedback budget mm. As we had shown, it is sufficient to have z≥T/mz \ge T/m so that the total amount of feedback rounds is at most mm. Therefore, by combining all of these, we get

T∑a=1K∑t=1T(1∧∥xt∥Vt−1,at−12)1[at=a]=T∑a=1K(z∑t∈OT,a(log⁡det⁡Vt−1,a−log⁡det⁡Vτt−1,a,a)+c)(10)\sqrt{T\sum_{a=1}^{K}\sum_{t=1}^{T}\left(1\wedge\lVert x_t\rVert^2_{V_{t-1,a_t}^{-1}}\right)\mathbf{1}[a_t=a]}=\sqrt{T\sum_{a=1}^{K}\left(z\sum_{t\in O_{T,a}}\left(\log\det V_{t-1,a}-\log\det V_{\tau_{t-1,a,a}}\right)+c\right)} \tag*{(10)}
≤Tm−1/2∑j=1K(log⁡det⁡(Vt−1,a−log⁡det⁡V0,a)+cKT.(11)\leq Tm^{-1/2}\sqrt{\sum_{j=1}^{K}\left(\log\det(V_{t-1,a}-\log\det V_{0,a}\right)+\sqrt{cKT}.} \tag*{(11)}

For a fixed expert a∈[K]a\in[K], notice that Vt−1,a=∑t∈OT,axstxstTV_{t-1,a}=\sum_{t\in O_{T,a}}x_{s_t}x_{s_t}^{\mathsf{T}}, ∣OT∣≤m|O_T|\leq m (since we are getting feedback for at most mm rounds for any expert). Moreover, for all prompts {xt}t∈[T]\{x_t\}_{t\in[T]}, we have Tr⁡(xtxtT)=∥xt∥22≤1\operatorname{Tr}(x_tx_t^{\mathsf{T}})=\lVert x_t\rVert^2_2\leq1 since all prompts are within the unit ball. Now, we use the AM-GM inequality and linearity of trace operation to show

det⁡Vt−1,a≤(d−1Tr⁡(Vt−1,a))d≤(d−1(Tr⁡(V0,a)+m))d.\det V_{t-1,a}\leq\left(d^{-1}\operatorname{Tr}(V_{t-1,a})\right)^d\leq\left(d^{-1}\left(\operatorname{Tr}(V_{0,a})+m\right)\right)^d.

We have Tr⁡(V0,a)≤dλ\operatorname{Tr}(V_{0,a})\leq d\lambda and therefore, we bound the regret conditioned on the event E\mathcal{E} (denote by Reg⁡(T)∣E\operatorname{Reg}(T)\mid\mathcal{E}) as

Reg⁡(T)∣E=O(TK1/2m−1/2dβlog⁡(dλ+md)).\operatorname{Reg}(T)\mid\mathcal{E}=O\left(TK^{1/2}m^{-1/2}\sqrt{d\beta\log\left(\frac{d\lambda+m}{d}\right)}\right).
Reg⁡(T)=Reg⁡(T)∣E+2TPr⁡(Ec)=Reg⁡(T)∣E+o(T−1).\operatorname{Reg}(T)=\operatorname{Reg}(T)\mid\mathcal{E}+2T\Pr(\mathcal{E}^{c})=\operatorname{Reg}(T)\mid\mathcal{E}+o(T^{-1}).

Now, we can substitute the value for β\beta to obtain the final theorem statement.

Proof of Theorem 3.3

Proof of Theorem 3.3. Consider number of rounds TT, a feedback budget of mm (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 X⊂{−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,y)(x,y), we can define the Hamming distance dh(x,y)=∑i=1d1[sign⁡(xi)≠sign⁡(yi)]d_h(x,y)=\sum_{i=1}^{d}\mathbf{1}[\operatorname{sign}(x_i)\ne\operatorname{sign}(y_i)].

Fix a vector x∈{−1,+1}dx\in\{-1,+1\}^d. Now, we define an instance in the full-information expert selection setting as follows: for each of the TT rounds, a single prompt x∈Xx\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)\leq1\}. In other words, the set of allowed experts have feature embedding which are within a Hamming distance of 1 from the prompt embedding vector xx. Given this environment, . Recall that the expert chosen at round tt is denoted by ata_t. Now, we define dd alternate learning instances as follows: in each alternate instance, a vector x′x' satisfying dh(x,x′)=1d_h(x,x')=1 is demonstrated at all rounds while the set of model features T(x)\mathcal{T}(x) remain the same. Therefore, the set of prompts across the d+1d+1 instances is X≡{y∈{−1,+1}d∣dh(y,x)≤1}\mathcal{X}\equiv\{y\in\{-1,+1\}^d\mid d_h(y,x)\leq1\}. Since the distinction between the instances is only in the prompt (the expert features θ\theta remain same in all instances), we denote by Py\mathbb{P}_y and Ey\mathbb{E}_y the probability and expectation of events under a fixed policy for instance defined by prompt y∈Xy\in\mathcal{X}.

Consider the environment defined by the prompt xx. Let us define the following event which is true when the number of times the sign of the ithi^{\text{th}} entry of the prompt and algorithm output (observation of history’s actions) differs is at least T/2T/2

Ex,i=1[∑t=1Tsign⁡(xi)≠sign⁡(ati)≥T/2]\mathcal{E}_{x,i} = \mathbf{1}\left[\sum_{t=1}^{T} \operatorname{sign}(x_i) \ne\operatorname{sign}(a_{t i}) \ge T/2\right]

and the corresponding probability to be px,i=Px(Ex,i)p_{x,i} = \mathbb{P}_{x}(\mathcal{E}_{x,i}). Now consider the alternate instance with prompt x′∈Xx' \in\mathcal{X} where xj′=xjx'_j = x_j for all j≠ij \ne i and xi′=−xix'_i = -x_i. Therefore, xx and x′x' have a Hamming distance of 1 and differ in sign at the index ii. Note that the event Ex′,i\mathcal{E}_{x',i} is the complement of the event Ex,i\mathcal{E}_{x,i}. We have

px,i+px′,i=Px(Ex,i)+Px′(Ex,ic)≥12exp⁡(−DKL(Px∥Px′))p_{x,i} + p_{x',i} = \mathbb{P}_{x}(\mathcal{E}_{x,i}) + \mathbb{P}_{x'}(\mathcal{E}_{x,i}^{c}) \ge\frac{1}{2} \exp\left(-D_{\mathrm{KL}}(\mathbb{P}_{x}\|\mathbb{P}_{x'})\right)

Above, we used the Bretagnolle Huber inequality (see [30]) and DKLD_{\mathrm{KL}} is the Kullback-Leibler Divergence. It is given by

DKL(Px∥Px′)=mEx[DKL(N(θ⋅x,Id+1)∥N(θ⋅x′,Id+1))]=m∥θ(x−x′)∥22=mδ2(d+1).D_{\mathrm{KL}}(\mathbb{P}_{x}\|\mathbb{P}_{x'}) = m\mathbb{E}_{x}\left[D_{\mathrm{KL}}\left(\mathcal{N}(\theta\cdot x, I_{d+1})\|\mathcal{N}(\theta\cdot x', I_{d+1})\right)\right] = m\left\|\theta(x-x')\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 get px,i+px′,i≥exp⁡(−1)/2p_{x,i} + p_{x',i} \ge\exp(-1)/2. Now, we want to extend the analysis to environments defined by prompts y∈X∖{x}y \in\mathcal{X} \setminus\{x\}. Fix such a prompt yy and define the event which is true when the number of times the sign of the iith entry of the prompt and the expert differs is at least T/2T/2

Ey,i=1[∑t=1Tsign⁡(yi)≠sign⁡(ati)≥T/2]\mathcal{E}_{y,i} = \mathbf{1}\left[\sum_{t=1}^{T} \operatorname{sign}(y_i) \ne\operatorname{sign}(a_{t i}) \ge T/2\right]

Without loss of generality, assume that the index where yy and xx differs in sign is j≠ij \ne i (otherwise the alternate instance trivially becomes the environment defined by xx). In that case, consider the alternate instance defined by prompt y′y' such that ys′=xsy'_s = x_s for all s≠is \ne i and yi′=−xiy'_i = -x_i (y′y' and xx differs in sign at the index ii). Therefore, yy and y′y' have a Hamming distance of 2 and differ in sign at the indices i,ji,j. However, note that the event Ey′,i\mathcal{E}_{y',i} is the complement of the event Ey,i\mathcal{E}_{y,i}. By a similar analysis as above, we have

py,i+py′,i≥12exp⁡(−DKL(Py∥Py′))=12exp⁡(−m∥θ(y−y′)∥22)≥12exp⁡(−4mδ2(d+1)).p_{y,i} + p_{y',i} \ge\frac{1}{2}\exp\left(-D_{\mathrm{KL}}(\mathbb{P}_{y}\|\mathbb{P}_{y'})\right) = \frac{1}{2}\exp\left(-m\left\|\theta(y-y')\right\|_{2}^{2}\right) \ge\frac{1}{2}\exp\left(-4m\delta^{2}(d+1)\right).

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.p_{y,i} + p_{y',i} \ge\exp(-4)/2.

Since there are d+1d+1 possibilities of the prompt xx, we can have

1∣X∣∑x∈X∑i=1dpx,i=1∣X∣∑i=1d∑x∈Xpx,i≥dexp⁡(−4)4.\frac{1}{|\mathcal{X}|}\sum_{x\in\mathcal{X}}\sum_{i=1}^{d}p_{x,i} = \frac{1}{|\mathcal{X}|}\sum_{i=1}^{d}\sum_{x\in\mathcal{X}}p_{x,i} \ge\frac{d\exp(-4)}{4}.

Hence, there must exist a prompt y∈Xy \in\mathcal{X} for which ∑i=1dpy,i≥dexp⁡(−4)/4\sum_{i=1}^{d}p_{y,i} \ge d\exp(-4)/4. For this instance defined by the prompt yy and expert features θ\theta, we have

Reg⁡(T)=Ey[∑t=1T⟨y,δ⋅y−at⟩]=Ey[∑t=1T⟨y,δy−At⟩]=Ey[∑t=1T∑i=1dyi(δyi−ati)]=2δEy[∑t=1T∑i=1d1[sign⁡(yi)≠sign⁡(ati)]]=2δ∑i=1dEy[∑t=1T1[sign⁡(yi)≠sign⁡(ati)]]=δT∑i=1dPyi≥δdTexp⁡(−4)4≥Tdexp⁡(−4)8m.\begin{aligned} \operatorname{Reg}(T) = \mathbb{E}_{y}\left[\sum_{t=1}^{T}\langle y,\delta\cdot y-a_t\rangle\right] \\ &= \mathbb{E}_{y}\left[\sum_{t=1}^{T}\langle y,\delta y-A_t\rangle\right] = \mathbb{E}_{y}\left[\sum_{t=1}^{T}\sum_{i=1}^{d}y_i(\delta y_i-a_{t i})\right] = 2\delta\mathbb{E}_{y}\left[\sum_{t=1}^{T}\sum_{i=1}^{d}\mathbf{1}[\operatorname{sign}(y_i)\ne\operatorname{sign}(a_{t i})]\right] \\ &= 2\delta\sum_{i=1}^{d}\mathbb{E}_{y}\left[\sum_{t=1}^{T}\mathbf{1}[\operatorname{sign}(y_i)\ne\operatorname{sign}(a_{t i})]\right] = \delta T\sum_{i=1}^{d}\mathbb{P}_{y_i} \ge\frac{\delta dT\exp(-4)}{4} \ge\frac{T\sqrt{d}\exp(-4)}{8\sqrt{m}}. \end{aligned}

This completes the proof of the theorem.

Proof of Theorem 4.2

Proof of Theorem 4.2. The proof of the lower bound for the bandit setting follows on similar lines as the proof in Theorem 3.3. Consider number of rounds TT, a feedback budget of mm and number of experts to be KK and 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 X⊂{−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 vectors x,yx,y, we can define the Hamming distance

dh(x,y)=∑i=1d1[sign⁡(xi)≠sign⁡(yi)].d_{h}(x,y) = \sum_{i=1}^{d} 1[\operatorname{sign}(x_{i}) \ne\operatorname{sign}(y_{i})].

Fix a prompt vector xx to be the dd-dimensional all ones vector. For simplicity assume that dd is divisible by KK. Now, we define an instance in the bandit feedback setting as follows: for each of the TT rounds, the single prompt x∈Xx \in\mathcal{X} is going to be demonstrated at all rounds and the set of expert parameters is given by a fixed set of KK vectors from the set θ≡{θ∈{−δ,+δ}d∣dh(θ,x)≤1}\theta\equiv\{\theta\in\{-\delta,+\delta\}^{d} \mid d_{h}(\theta,x) \le1\}. Without loss of generality, let {θa}a∈[K]\{\theta_{a}\}_{a \in[K]} be the set of parameter vectors which has its sign flipped from xx in one of the first KK entries.

Now, we can define KK alternate learning instances as follows: in each alternate instance, a vector x′x' satisfying dh(x,x′)=1d_{h}(x,x') = 1 is demonstrated at all rounds while the set of expert features T(x)\mathcal{T}(x) remain the same. Further x′x' has its sign changed only among the first KK entries of xx. Therefore the last d−Kd-K indices are inconsequential and we basically have a KK-dimensional problem. Now, we go through the same steps as in the proof of Theorem 3.3. 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 is O(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:

Reg⁡(T)≥TKexp⁡(−4)8m.\operatorname{Reg}(T) \ge\frac{TK\exp(-4)}{8\sqrt{m}}.

There are many notions of limited feedback and resource constraints that have been studied in the past. Partial monitoring ([5], [10], [9]) and learning to rank ([43], [26, 27], [34]) 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 ([?], [?]), 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 [2]). 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 ([?], [6]). 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 ([?], [25]), 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 ([13]), 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 ([12], [4], [44]). 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 ([46], [45]). 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 ([17], [46], [47], [36], [20], [39], [45]). 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 ([38]) 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 ([?]) predicts the increase of model performances due to training or finetuning and efficiently balances exploration and exploitation in model selection. ([14]) 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 ([23]) focused on selecting a set of LLMs under a given cost budget to maximize performance. ([42]) 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, ([19]) investigated model selection under contextual bandit feedback whereas ([1]) framed online model selection as a rested bandit problem. Further, [24] leverages active learning to identify the best model from a pool of pretrained classifiers. Other recent work has focused on the orthogonal problem of leveraging LLMs for model selection ([?]). 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 [21]}. [11] proved a Tlog⁡K/mT\sqrt{\log K}/m regret bound for the exponentially-weighted forecaster, where KK is the number of experts. [8] derived a TK(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 rounds TT and observation budget mm is similar to our work. The closest related work in the stochastic bandit setting is [?]. 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.

Implementation Details

For our experiments, we use the RouterBench ([22]) which is a high-quality routing benchmark consisting a diverse set of 11 Large Language Models. There are approximately 405k405k prompts and for each prompt, responses from the 11 models are evaluated and normalized to 0 and 1. We randomly chose a subset of 10k10k prompts out of the total pool of 405k405k prompts. We found no model dominates the others more than a third of the time (Section 1). Thus, we have K=11K = 11 experts in this setting. For each of the 10k10k prompts, we create its 384 dimensional embedding using the bge-small-en-v1.5 model ([?]). Next we do PCA to reduce the dimension to 40, capturing 50% of the feature variance, resulting in a 10000×4010000 \times40 sized 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 of 10k10k prompts and create a one-hot vector of dimension 11. In this vector, only the model whose response has been selected as best is assigned 1 and we have 0 everywhere else. Therefore we have a response vector of dimension 10000×1110000 \times11. 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.

References

  1. [1]in the bandit setting to refine regret minimization strategies. formulation. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 1362–1372. PMLR.
  2. [2]Yasin Abbasi-Yadkori, David Pal, and Csaba Szepesvari. 2011. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems 24, pages 2312–2320.
  3. [3]Yasin Abbasi-Yadkori, David Pal, and Csaba Szepesvari. 2012. Online-to-confidence-set conversions and application to sparse stochastic bandits. In Artificial Intelligence and Statistics, pages 1–9. PMLR.
  4. [4]Pranjal Aggarwal, Aman Madaaan, Ankit Anand, Srividya Pranavi Potharaju, Swaroop Mishra, Pei Zhou, Aditya Gupta, Dheeraj Rajagopal, Karthik Kappaganthu, Yiming Yang, and 1 others. 2023. Automix: Automatically mixing language models. arXiv preprint arXiv:2310.12963.arxiv.org/abs/2310.12963
  5. [5]Rajeev Agrawal, Demosthenis Teneketzis, and Venkatachalam Anantharam. 1989. Asymptotically efficient adaptive allocation schemes for controlled i.i.d. processes: Finite parameter space. IEEE Transactions on Automatic Control, 34(3):258–267.DOI
  6. [6]Shipra Agrawal and Nikhil Devanur. 2016. Linear contextual bandits with knapsacks. In Advances in Neural Information Processing Systems 29.
  7. [7]Artificial Analysis. 2025. LLM leaderboard.
  8. [8]Jean-Yves Audibert and Sebastien Bubeck. 2010. Regret bounds and minimax policies under partial monitoring. Journal of Machine Learning Research, 11(94):2785–2836.
  9. [9]Gabor Bartok, Dean Foster, David Pal, Alexander Rakhlin, and Csaba Szepesvari. 2014. Partial monitoring - classification, regret bounds, and algorithms. Mathematics of Operations Research, 39(4):967–997.DOI
  10. [10]Gabor Bartok and Csaba Szepesvari. 2012. Partial monitoring with side information. In Proceedings of the 23rd International Conference on Algorithmic Learning Theory, pages 305–319.DOI
  11. [11]Nicolo Cesa-Bianchi, Gabor Lugosi, and Gilles Stoltz. 2005. Minimizing regret with label efficient prediction. IEEE Transactions on Information Theory, 51(6):2152–2162.
  12. [12]Lingjiao Chen, Matei Zaharia, and James Zou. 2023. Frugalgpt: How to use large language models while reducing cost and improving performance. arXiv preprint arXiv:2305.05176.arxiv.org/abs/2305.05176
  13. [13]Corinna Cortes, Giulia DeSalvo, Claudio Gentile, Mehryar Mohri, and Scott Yang. 2018. Online learning with abstention. In Proceedings of the 35th International Conference on Machine Learning.
  14. [14]Xiangxiang Dai, Jin Li, Xutong Liu, Anqi Yu, and John Liu. 2024. Cost-effective online multi-llm selection with versatile reward models. arXiv preprint arXiv:2405.16587.arxiv.org/abs/2405.16587
  15. [15]Databricks. 2025a. How quality, cost, and latency are assessed by agent evaluation.
  16. [17]Dujian Ding, Ankur Mallick, Chi Wang, Robert Sim, Subhabrata Mukherjee, Victor Rühle, Laks VS Lakshmanan, and Ahmed Hassan Awadallah. Hybrid llm: Cost-efficient and quality-aware query routing. In The Twelfth International Conference on Learning Representations ICLR 2024, Vienna, Austria, May 7-11, 2024.arxiv.org/abs/2404.14618
  17. [18]Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Ayesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, and 1 others. 2024. The llama 3 herd of models. arXiv preprint arXiv:2407.21783.arxiv.org/abs/2407.21783
  18. [19]Dylan J Foster, Akshay Krishnamurthy, and Haipeng Luo. 2019. Model selection for contextual bandits. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc.
  19. [20]Surya Narayanan Hari and Matt Thomson. 2023. Tryage: Real-time, intelligent routing of user prompts to large language model. arXiv preprint arXiv:2308.11601.arxiv.org/abs/2308.11601
  20. [21]David Helmbold and Sandra Panizza. 1997. Some label efficient learning results. In Proceedings of the 10th Annual Conference on Computational Learning Theory, pages 218–230.DOI
  21. [22]Qitian Jason Hu, Jacob Bieker, Xiuyu Li, Nan Jiang, Benjamin Keigwin, Gaurav Ranganath, Kurt Keutzer, and Shivash Kaushtubh Upadhyay. 2024. Routerbench: A benchmark for multi-llm routing system. Preprint, arXiv:2403.12031.arxiv.org/abs/2403.12031
  22. [23]Keke Huang, Yimin Shi, Dujian Ding, Yifei Li, Yang Fei, Laks Lakshmanan, and Xiaokui Xiao. 2025. Thriftllm: On cost-effective selection of large language models for classification queries. arXiv preprint arXiv:2501.04901.arxiv.org/abs/2501.04901
  23. [24]Mohammad Reza Karimi, Nezihe Merve Gürel, Bojan Karlaš, Johannes Rausch, Ce Zhang, and Andreas Krause. 2021. Online active model selection for pre-trained classifiers. In International Conference on Artificial Intelligence and Statistics, pages 307–315. PMLR.arxiv.org/abs/2010.09818
  24. [25]Abbas Kazerouni, Mohammad Ghavamzadeh, Yasin Abbasi-Yadkori, and Benjamin Van Roy. 2017. Conservative contextual linear bandits. In Advances in Neural Information Processing Systems 30.arxiv.org/abs/1611.06426
  25. [26]Branislav Kveton, Csaba Szepesvari, Zheng Wen, and Azin Ashkan. 2015a. Cascading bandits: Learning to rank in the cascade model. In Proceedings of the 32nd International Conference on Machine Learning.arxiv.org/abs/1502.02763
  26. [27]Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvari. 2015b. Combinatorial cascading bandits. In Advances in Neural Information Processing Systems 28, pages 1450–1458.
  27. [28]John Langford and Tong Zhang. 2008. The epoch-greedy algorithm for contextual multi-armed bandits. In Advances in Neural Information Processing Systems 20, pages 817–824.
  28. [29]Tor Lattimore and Csaba Szepesvari. 2019. Bandit Algorithms. Cambridge University Press.DOI
  29. [30]Tor Lattimore and Csaba Szepesvári. 2020. Bandit algorithms. Cambridge University Press.DOI
  30. [31]Dawei Li, Bohan Jiang, Liangjie Huang, Alimohammad Beigi, Chengshuai Zhao, Zhen Tan, Amrita Bhattacharjee, Yuxuan Jiang, Canyu Chen, Tianhao Wu, Kai Shu, Lu Cheng, and Huan Liu. 2024a. From generation to judgment: Opportunities and challenges of llm-as-a-judge. arXiv preprint arXiv:2411.16594.arxiv.org/abs/2411.16594
  31. [32]Haitao Li, Qian Dong, Junjie Chen, Huixue Su, Yujia Zhou, Qingyao Ai, Ziyi Ye, and Yiqun Liu. 2024b. Llms-as-judges: A comprehensive survey on llm-based evaluation methods. arXiv preprint arXiv:2412.05579.arxiv.org/abs/2412.05579
  32. [33]Lihong Li, Wei Chu, John Langford, and Robert Schapire. 2010. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th International Conference on World Wide Web.DOI
  33. [34]Shuai Li, Baoxiang Wang, Shengyu Zhang, and Wei Chen. 2016. Contextual combinatorial cascading bandits. In Proceedings of the 33rd International Conference on Machine Learning, pages 1245–1253.
  34. [35]LLM-as-a-Judge. 2025. LLM as a judge.
  35. [36]Keming Lu, Hongyi Yuan, Runji Lin, Junyang Lin, Zheng Yuan, Chang Zhou, and Jingren Zhou. 2024. Routing to the expert: Efficient reward-guided ensemble of large language models. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pages 1964–1974.
  36. [37]Mistral AI. 2025. Mistral AI.
  37. [38]Quang H Nguyen, Duy C Hoang, Juliette Decugis, Saurav Manchanda, Nitesh V Chawla, and Khoa D Doan. 2024. Metallm: A high-performance and cost-efficient dynamic framework for wrapping llms. arXiv preprint arXiv:2407.10834.arxiv.org/abs/2407.10834
  38. [39]Isaac Ong, Amjad Almahairi, Vincent Wu, Wei-Lin Chiang, Tianhao Wu, Joseph E Gonzalez, M Waleed Kaddour, and Ion Stoica. 2024. Routellm: Learning to route llms with preference data. arXiv preprint arXiv:2406.18665.arxiv.org/abs/2406.18665
  39. [40]OpenAI. 2025. OpenAI API pricing.
  40. [41]OpenAI, Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilige Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, and 1 others. 2023. Gpt-4 technical report. arXiv preprint arXiv:2303.08774.arxiv.org/abs/2303.08774
  41. [42]Abraham Toluwase Owodunni and Chris Chinenye Emezue. 2023. Koya: A recommender system for large language model selection. In 4th Workshop on African Natural Language Processing.
  42. [43]Filip Radlinski, Robert Kleinberg, and Thorsten Joachims. 2008. Learning diverse rankings with multi-armed bandits. In Proceedings of the 25th International Conference on Machine Learning, pages 784–791.DOI
  43. [44]Guillem Ramirez, Alexandra Birch, and Ivan Titov. 2024. Optimising calls to large language models with uncertainty-based two-tier selection. arXiv preprint arXiv:2405.02134.arxiv.org/abs/2405.02134
  44. [45]Marija Šakota, Maxime Peyrard, and Robert West. 2024. Fly-swat or cannon? cost-effective language model choice via meta-modeling. In Proceedings of the 17th ACM International Conference on Web Search and Data Mining, pages 606–615.DOI
  45. [46]Shivanshu Shekhar, Tanishq Dubey, Koyel Mukherjee, Apoorv Saxena, Atharv Tyagi, and Nishanth Kotla. 2024. Towards optimizing the costs of llm usage. arXiv preprint arXiv:2402.01742.arxiv.org/abs/2402.01742
  46. [47]Tal Shnitzer, Anthony Ou, Mirian Silva, Kate Soule, Yuekai Sun, Justin Solomon, Neil Thompson, and Mikhail Yurochkin. 2023. Large language model routing with benchmark datasets. arXiv preprint arXiv:2309.15789.arxiv.org/abs/2309.15789

Paper details

vlnc:W_9hmetj6m
Version
v1 · latest
Published
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents