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 actions that represent experts and features that encode prompts, over a horizon of rounds. We propose algorithms that strategically select and observe rewards to minimize regret. In the full-information setting, we achieve a regret of , while in the bandit setting we achieve , where 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 different LLMs and interact with them sequentially over 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 times, where 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 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 rewards out of 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:
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 , which matches our lower bound up to . Note that the bound is when .
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 . The additional factor comparing to the full-information setting is due times less feedback.
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.
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 the set . We denote scalars and vectors by lowercase letters (say ). We denote matrices and fixed global parameters by capital letters (say ). For a vector , denotes its entry. For an indexed vector , denotes its entry. We let be the weighted 2-norm with respect to a positive semi-definite matrix . We define the corresponding inner product as . and are the zero vector and identity matrix in dimensions, respectively. is the Gaussian distribution in -dimensions with zero mean and covariance matrix . For a matrix , we write to denote its column. Let be the unit ball in dimensions.
Problem Formulation: We introduce our setting as a variant of a classic linear bandit [2]. We have rounds and LLM experts. Each expert is indexed by and associated with an unknown parameter vector . At each round , a prompt arrives and we denote it by for some . The prompt is then treated as context at round .
Given a prompt , the algorithm chooses an expert and obtains its response. In the linear model, the expected reward for the response of expert in round is . We denote the vector of all stochastic rewards in round by and define each reward as
We assume that the noise 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, is the embedding of the prompt produced by a transformer, and is the linear head for expert . This is standard in reward modeling, with the only distinction being that we do not fine-tune the embeddings.
Further, at each round , the context arrives, the algorithm selects an expert , 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 , by looking back at past contexts similar to 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 . Our formulation instead leverages past feedback frugally: routing decisions are made with whatever has been learned up to round , 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 . The key difference in our setting is that the reward vector generated at any round 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 observations, meaning that it can observe at most 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 , the algorithm decides to collect feedback, it may choose any round and observe the noisy reward vector or its entry . 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 given the prompt is
We define the cumulative regret in rounds as
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 LLM experts, the number of rounds , the feedback budget , and a hyperparameter . We also initialize all statistics for tracking reward models of all experts online (Section 2), such as the common covariance matrix and ordinary least squares (OLS) estimates for all experts.
In any round , LimFullFeed observes a prompt and chooses the best expert based on its estimated mean reward in eq:3. LimFullFeed may decide to obtain feedback. The feedback is obtained when holds. Roughly speaking, this happens every rounds since . 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 and let the algorithm choose any round in . We denote the chosen round by and the observed rewards by . Since we are in the full-information setting, 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, in (5).
The technical novelty in our algorithm design is in how is chosen. We consider all past prompts 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 per-round time complexity, due to inverting matrices and computing their determinants. This can be reduced to 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 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 satisfy . All prompts satisfy . We also assume that .
Theorem 3.2. Choose any experts, features, horizon , budget , and . Suppose that Theorem 3.1 holds. Then the regret of LimFullFeed is .
Due to space constraints, we only sketch the proof. The detailed proof is in Section B.1.
Proof Sketch. Consider a fixed expert with unknown and a prompt at round . Using the OLS estimate for , the error in estimated mean reward given by scales as . This error can be rewritten as . In standard linear bandits, we update the covariance matrix . Hence, we can add up the error over all rounds to obtain a telescoping sum. However, in our setting with limited feedback, 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 with the prompt that increases its determinant most. Hence we can still bound from above by . 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 rounds. Therefore we still get a telescoping sum after adding the errors but the limited feedback leads to an extra multiplicative factor of in the telescoping sum. This leads to an additional multiplicative factor of in the regret bound.
Note that regret does not depend on the number of experts since in the full-information setting, we obtain responses for all experts jointly. Therefore, when , we can obtain feedback for all rounds and the regret guarantee that is achieved is . 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 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, features, experts, horizon , feedback budget of . Suppose all observations are Gaussian random variables with noise variance 1. Let prompts and for . Then there exists an instance such that the regret incurred must satisfy
Discussion: Note that there is a gap of 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 we need to bound for all possible prompts and all experts . 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 -dimensional space leads to a union bound over dimensions that in turn leads to the additional factor in the upper bound. If on the other hand, the prompts was known, then we would only need a union bound over vectors instead of all vectors in . This removes the additional 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 . Suppose that the algorithm knew the prompts in advance and could also decide the order in which to obtain feedback. Then the algorithm would choose a subset of most-informative prompts, obtain feedback, and learn the expert parameters from them. The regret of this approach would be , where is the maximum confidence interval width and . An optimal solution to this problem is known as the G-optimal optimal design [30], Chapter 21 and its maximum confidence interval width is . This leads to a regret of over 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.
Initialize , , ; and , for all .
for rounds do
Obtain prompt , choose expert and increase its counter by 1.
if then
Find the most informative past observation for the expert . Reset its counter.
Observe reward for the expert and update the corresponding statistics for .
else
Update and for all experts .
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 corresponding to the confidence width. In the bandit setting, we initialize the covariance matrix along with other hyperparameters separately for each expert . In Line 2, we also initialize a variable which is set to be the average number of rounds between feedback, namely .
At each round , the prompt arrives as context. Given the input prompt , LimBanFeed chooses the expert 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 for every expert that keeps track of the number of times an expert is chosen for generating response. Once an expert has been used 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 helps respect the overall feedback budget of rounds. The number of rounds where an expert has been used to generate a response in the time horizon is , hence the number of times the expert has been evaluated is .
Setting helps satisfy the feedback budget :
For getting feedback for an expert , LimBanFeed chooses a prompt index among the past prompts that maximizes the increase in the determinant of the covariance matrix for the expert (see (4)). We only choose prompts that have not yet been evaluated.
We update the OLS estimate of the parameter vector for expert (see (5)) by using the observed scalar reward 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, experts, features, horizon and feedback budget . Suppose Assumption 3.1 is true. Then for any and , the regret of LimBanFeed is
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 for expert , 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 from above. Additionally, in our analysis, we use the fact that each expert is updated after being used 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 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 .
Further, when that is, we can obtain feedback for all rounds, Algorithm 2 achieves a regret guarantee of . As in the full-information setting, the cost of limited feedback is a multiplicative factor of . 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, features, experts, horizon , feedback budget of . Suppose all observations are Gaussian random variables with noise variance 1. Let prompts and for . Then there exists an instance such that the regret incurred must satisfy
There is a gap of between the upper and lower bounds in the bandit setting. This arises because the lower-bound analysis reduces to hypothesis testing in a -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 , which is looser by a factor of . Similar to the full-information setting, the upper bound includes an additional factor of due to the algorithm’s lack of knowledge about the prompt vectors, requiring a union bound over all vectors in the -dimensional space. This extra factor can be eliminated if the algorithm has prior knowledge of the prompts. The remaining gap of persists because the lower bound analysis is based on hypothesis testing with 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 , with a feedback budget . 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 (), 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.

Figure 1.

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.

(a) Full Information Setting

(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 increases, consistent with the dependence in our theory. In the bandit setting, LimBanFeed consistently outperforms NoLookBack, with the gap widening for larger . In the full-information setting, the gap is smaller for small , since each feedback reveals all experts, but LimFullFeed becomes competitive as increases.
| Full-information | Bandit | |||
| LimFullFeed | NoLookBack | LimBanFeed | NoLookBack | |
| 1000 | 672.9 ± 37.4 | 631.6 ± 22.1 | 3583.4 ± 68.0 | 3789.6 ± 30.4 |
| 2000 | 441.4 ± 42.6 | 408.0 ± 26.2 | 3084.1 ± 25.6 | 3580.0 ± 73.3 |
| 5000 | 214.1 ± 7.7 | 218.7 ± 10.6 | 2295.7 ± 42.3 | 3020.7 ± 17.2 |
| 10000 | 128.0 ± 8.7 | 129.0 ± 11.0 | 1839.1 ± 29.1 | 2538.4 ± 22.2 |
| 20000 | 73.6 ± 6.0 | 75.8 ± 6.1 | 1567.9 ± 13.4 | 2090.7 ± 21.2 |
Table 1. Cumulative regret with respect to feedback budget on Nectar (, , ).
Runtime Analysis. Table 2 shows that both methods scale approximately linearly with . LimBanFeed scales linearly with , while LimFullFeed is largely independent of due to its shared covariance structure.
| Axis | Value | LimBanFeed | LimFullFeed |
| 2 | |||
| 6 | |||
| 10 | |||
| 16 | |||
| 20 | |||
| 8 | |||
| 24 | |||
| 40 | |||
| 96 | |||
| 128 | |||
| 500 | |||
| 1,000 | |||
| 5,000 | |||
| 10,000 | |||
| 15,000 |
Table 2. Runtime in seconds with respect , , and 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 experts have different costs of being evaluated and there is a budget on the overall cost. More precisely, suppose the total cost budget is and the cost of evaluation of the expert is . Without loss of generality, we can assume that . For the expert with cost , we evaluate it after it has been used times for some .
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 , can be computed as follows: Again, recall that the number of rounds where the expert has been used to generate a response in the entire time horizon is . In that case, the number of times the expert has been evaluated is . We need the total cost to be smaller than , hence,
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 for every expert as in Algorithm 2, now we have an interval length of for the expert. Going through the same set of calculations, we can show that the regret guarantee in this case is going to be
Substituting the value of as in Theorem 4.1, the final regret guarantee can be written as
Notice that when all the costs are , 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 .
Detailed Proofs
Proof of Theorem 3.2
Proof of Theorem 3.2. Notations: We start by setting up some notations. Let denote the set of rounds until (including) round in which the algorithm chooses to get feedback. Note that for all . For the set of prompts evaluated until round , recall to be the set of past rounds when the prompts were provided as input to the algorithm. Let us denote denote the last round before round when the experts were updated. We denote .
We can decompose the RHS in (2) as follows:
Note that the second term is negative. This is because, by choice of our algorithm, we have picked the expert index at each round such that . 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 by . Recall that feedback is solicited at every interval of 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 and every expert with probability at least :
Denote the event where (6) is true for all rounds and all experts . Moving forward, we can now condition on the above high probability event . We now show the following for any round :
The last step follows from the fact that by definition is the last round (before round ) when the expert had been updated. Note that for each round , we also have from the assumption in theorem statement. Therefore, we can combine to show
where the final step follows from application of Cauchy-Schwarz inequality. Now, continuing from (7), for any round , we use the fact that for any , we have :
Now, consider a round where feedback has been observed for some prompt in the history. As we defined before, corresponds to the previous round in history where feedback has been observed. From Algorithm 1, recall that was the prompt chosen at round for feedback following which we had updated . Further, recall that the prompt index at round was chosen in the following way:
implying that the prompt increases the determinant of the covariance matrix the most. Thus, for every round , we must have . Hence, we have
Therefore, using the fact that the covariance matrix remains unchanged for rounds, we can write
Notice that , (since we are getting feedback for rounds). Moreover, for all prompts , we have since all prompts are within the unit ball. Now, we use the AM-GM inequality and linearity of trace operation to show
We have and therefore, we bound the regret conditioned on the event (denote by ) as
When the event is false, then the regret can be bounded by the (worst-case). Therefore the final regret can be written as
Now, we can substitute the value for 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 , let denote the set of rounds until round in which the algorithm has opted to obtain a feedback for expert . As before, for any , we have for all . Similar to full-information, for the set of prompts evaluated until round , define to be the set of past rounds when the prompts were provided as input to the algorithm. We denote denote the last round before round when the expert 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 and every expert with probability at least :
Denote the event where (8) is true for all rounds and all experts . For any prompt at round , the parameter vector in the confidence region that leads to the highest reward is given by
and therefore, the expert to generate the response is chosen as . 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])
Now, we can decompose the RHS in (2) for any round as follows:
For the first inequality we bound the reward for the expert from above by the upper confidence bound on the reward. The second inequality follows from . This is because, by choice of our algorithm, we have picked the expert index at each round having the largest upper confidence reward on prompt .
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 at round by . Again, recall that feedback is solicited for expert after the expert has been used to generate a response times. Now, we can show the following for any round
Now, we need to bound from above the final term on the RHS in terms of the individual experts as follows:
In the pre-final step, we used that in each round , we also have from the assumption in theorem statement. In the final step, we used the Cauchy-Schwarz inequality. Note that there are only terms in the RHS since at each round, only a single expert is chosen. Consider a particular expert - it is chosen for obtaining feedback after being used for generating responses times since the last time feedback was obtained for expert .
At any round , recall denote the last round from when the expert was chosen for obtaining feedback (after the counter for expert zt \in O_{t,a}V_{t-1,a}at\tau_{t-1,a}atu \ge 0u \wedge 1 \le 2\log(1+u)$,
Now for a fixed expert , consider a round where feedback has been observed for some prompt in the history of expert . As we defined before, corresponds to the previous round in history (relative to round ) where feedback has been observed for expert . From Algorithm 2, recall that was the prompt chosen at round for feedback following which we had updated . Further, recall that the prompt index at round was chosen in the following way:
implying that the prompt was responded to by the expert and further, the prompt increases the determinant of the covariance matrix the most. Thus, for every round satisfying , we must have . Hence, we have
In the last step, we used the threshold on that would meet the feedback budget . As we had shown, it is sufficient to have so that the total amount of feedback rounds is at most . Therefore, by combining all of these, we get
For a fixed expert , notice that , (since we are getting feedback for at most rounds for any expert). Moreover, for all prompts , we have since all prompts are within the unit ball. Now, we use the AM-GM inequality and linearity of trace operation to show
We have and therefore, we bound the regret conditioned on the event (denote by ) as
Now, we can substitute the value for to obtain the final theorem statement.
Proof of Theorem 3.3
Proof of Theorem 3.3. Consider number of rounds , a feedback budget of (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 and the set of model features to be for some . For any two vectors , we can define the Hamming distance .
Fix a vector . Now, we define an instance in the full-information expert selection setting as follows: for each of the rounds, a single prompt is going to be demonstrated and the set of expert parameters in this instance is given by . In other words, the set of allowed experts have feature embedding which are within a Hamming distance of 1 from the prompt embedding vector . Given this environment, . Recall that the expert chosen at round is denoted by . Now, we define alternate learning instances as follows: in each alternate instance, a vector satisfying is demonstrated at all rounds while the set of model features remain the same. Therefore, the set of prompts across the instances is . Since the distinction between the instances is only in the prompt (the expert features remain same in all instances), we denote by and the probability and expectation of events under a fixed policy for instance defined by prompt .
Consider the environment defined by the prompt . Let us define the following event which is true when the number of times the sign of the entry of the prompt and algorithm output (observation of history’s actions) differs is at least
and the corresponding probability to be . Now consider the alternate instance with prompt where for all and . Therefore, and have a Hamming distance of 1 and differ in sign at the index . Note that the event is the complement of the event . We have
Above, we used the Bretagnolle Huber inequality (see [30]) and is the Kullback-Leibler Divergence. It is given by
In that case, for the value of , we get . Now, we want to extend the analysis to environments defined by prompts . Fix such a prompt and define the event which is true when the number of times the sign of the th entry of the prompt and the expert differs is at least
Without loss of generality, assume that the index where and differs in sign is (otherwise the alternate instance trivially becomes the environment defined by ). In that case, consider the alternate instance defined by prompt such that for all and ( and differs in sign at the index ). Therefore, and have a Hamming distance of 2 and differ in sign at the indices . However, note that the event is the complement of the event . By a similar analysis as above, we have
In that case, for the value of , we have
Since there are possibilities of the prompt , we can have
Hence, there must exist a prompt for which . For this instance defined by the prompt and expert features , we have
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 , a feedback budget of and number of experts to be 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 and the set of experts features to be for some . For any two vectors , we can define the Hamming distance
Fix a prompt vector to be the -dimensional all ones vector. For simplicity assume that is divisible by . Now, we define an instance in the bandit feedback setting as follows: for each of the rounds, the single prompt is going to be demonstrated at all rounds and the set of expert parameters is given by a fixed set of vectors from the set . Without loss of generality, let be the set of parameter vectors which has its sign flipped from in one of the first entries.
Now, we can define alternate learning instances as follows: in each alternate instance, a vector satisfying is demonstrated at all rounds while the set of expert features remain the same. Further has its sign changed only among the first entries of . Therefore the last indices are inconsequential and we basically have a -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 . Hence, substituting and then resuming the same steps gives us the following lower bound:
Related Work
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 regret bound for the exponentially-weighted forecaster, where is the number of experts. [8] derived a regret bound for the bandit setting. None of these works study the contextual setting. However, their scaling with the number of rounds and observation budget 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 prompts and for each prompt, responses from the 11 models are evaluated and normalized to 0 and 1. We randomly chose a subset of prompts out of the total pool of prompts. We found no model dominates the others more than a third of the time (Section 1). Thus, we have experts in this setting. For each of the 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 sized data matrix. In order to generate the expert parameters , we take the evaluated ranking from GPT-4 for each of 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 . Now we obtain the parameter
for each of the experts by computing the OLS estimate on this dataset.
References
- [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]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]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]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]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]Shipra Agrawal and Nikhil Devanur. 2016. Linear contextual bandits with knapsacks. In Advances in Neural Information Processing Systems 29.
- [7]Artificial Analysis. 2025. LLM leaderboard.
- [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]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]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]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]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]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]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]Databricks. 2025a. How quality, cost, and latency are assessed by agent evaluation.
- [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
- [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
- [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.
- [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
- [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
- [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
- [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
- [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
- [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
- [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
- [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.
- [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.
- [29]Tor Lattimore and Csaba Szepesvari. 2019. Bandit Algorithms. Cambridge University Press.DOI
- [30]Tor Lattimore and Csaba Szepesvári. 2020. Bandit algorithms. Cambridge University Press.DOI
- [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
- [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
- [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
- [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.
- [35]LLM-as-a-Judge. 2025. LLM as a judge.
- [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.
- [37]Mistral AI. 2025. Mistral AI.
- [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
- [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
- [40]OpenAI. 2025. OpenAI API pricing.
- [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
- [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.
- [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
- [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
- [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
- [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
- [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