Online Learning with LLM Experts from Limited Feedback

AI summary

Overview

• Research area: Machine learning — online learning and contextual bandits applied to routing prompts among large language model (LLM) experts under a limited feedback budget.
• Technical level: Intermediate. The paper combines a practical LLM-serving problem with regret analysis; readers benefit from some familiarity with bandits, linear models, and confidence bounds, though the core intuition is explained plainly.
• Scope: The paper formulates prompt routing to LLMs as a bandit problem with K experts, d prompt-embedding features, a horizon of T rounds, and a feedback budget of m ≪ T, then proposes algorithms for full-information and bandit feedback, proves regret bounds and lower bounds, and evaluates on two LLM routing benchmarks.

What This Paper Is About

Different LLMs have different capabilities and costs, and no single model dominates: on the Nectar dataset, when responses to 183k prompts are judged by GPT-4, the highest win rate among the compared models (GPT-4-0613) is 0.319, i.e. no model wins more than about a third of the time. The problem is that an agent must route each arriving prompt to one expert, but the response quality (reward) is usually unobserved — and obtaining human or LLM-judge evaluations is expensive, so only m ≪ T rewards can ever be observed. The goal is to learn a routing policy that maximizes response quality while deciding both what to observe and when to observe it, at a near-optimal regret rate.

Key Contributions

1. Full-information algorithm (LimFullFeed). When the agent can observe the rewards of all experts at any past round, the algorithm progressively queries past prompts that maximize the determinant of the covariance matrix. Its regret is Õ(dT/√m), which matches the paper's lower bound up to a √d factor; when m = Ω(T) the bound becomes Õ(√T).
2. Bandit algorithm (LimBanFeed). When only the reward of the chosen expert can be observed, the algorithm maintains per-expert confidence sets and observes rewards for the experts with the highest information gain, separately for each expert. Its regret is Õ(dT√(K/m)), and the extra √K relative to the full-information setting reflects K times less feedback.
3. Extension to non-uniform evaluation costs. The bandit setting is extended to experts whose evaluation prices differ, with a total cost budget; this result is placed in Appendix A.
4. Empirical evaluation. All algorithms are evaluated on the Nectar dataset with popular expert LLMs including GPT-3.5, GPT-4, LLaMA, and Mistral, and on the RouterBench benchmark.

Main Findings

• Full-information regret bound (Theorem 3.2): For K experts, d features, horizon T, budget m < T, and λ > 0, LimFullFeed achieves Reg(T) = O(dT m^(−1/2) log(TL)). The bound does not depend on K, because in the full-information setting all experts are observed jointly.
• Full-information lower bound (Theorem 3.3): There exists an instance with Gaussian noise of variance 1, binary prompts in {−1,+1}^d, and parameters in {−δ,+δ}^d with δ = (md)^(−1/2), such that Reg(T) ≥ T√d exp(−4) / (8√m). A gap of √d remains between the upper and lower bounds.
• Source of the √d gap: Because prompts are not known in advance, the analysis must bound errors for all vectors in the d-dimensional space, requiring a union bound over d dimensions. If prompts were known ahead of time, only a union bound over T vectors would be needed, removing the extra √d factor.
• Bandit regret bound (Theorem 4.1): With β = √λ + √(6 log T + d log(1 + TL²/d)), LimBanFeed achieves Reg(T) = O(dT K^(1/2) m^(−1/2) log(TL)). When m = T, the guarantee is O(d√(TK) log(TL)).
• Bandit lower bound (Theorem 4.2): There exists an instance with regret Reg(T) ≥ TK exp(−4) / (8√m). The gap between the bandit upper and lower bounds is d/√K; ignoring feature structure and treating experts as arms in a standard multi-armed bandit would give only Ω(T√(K/m)), looser by a factor of √K.
• Cost of limited feedback: In both settings the limited-feedback penalty appears as a multiplicative factor of √(T/m); the paper argues that periodic feedback matches the optimal dependence on m, since an optimal G-optimal design over the m most informative prompts gives a maximum confidence width of O(√(d/m)) and hence O(T√(d/m)) regret.
• Why look-back matters: A simpler baseline that queries feedback only for the prompt at the round when feedback is requested (NoLookBack) can suffer linear regret if an adversary supplies prompts in a subspace orthogonal to the other rounds' prompts.
• Computational cost: A naive implementation of LimFullFeed is O(d³) per round due to inverting d × d matrices and computing determinants; this can be reduced to O(d²) with the Sherman-Morrison formula and the matrix determinant lemma.
• Experiment 1 — regret vs. budget on Nectar (K = 6, d = 40, T = 60000, averaged over 5 runs):
  • m = 1000: full-information LimFullFeed 672.9 ± 37.4, NoLookBack 631.6 ± 22.1; bandit LimBanFeed 3583.4 ± 68.0, NoLookBack 3789.6 ± 30.4.
  • m = 2000: LimFullFeed 441.4 ± 42.6, NoLookBack 408.0 ± 26.2; LimBanFeed 3084.1 ± 25.6, NoLookBack 3580.0 ± 73.3.
  • m = 5000: LimFullFeed 214.1 ± 7.7, NoLookBack 218.7 ± 10.6; LimBanFeed 2295.7 ± 42.3, NoLookBack 3020.7 ± 17.2.
  • m = 10000: LimFullFeed 128.0 ± 8.7, NoLookBack 129.0 ± 11.0; LimBanFeed 1839.1 ± 29.1, NoLookBack 2538.4 ± 22.2.
  • m = 20000: LimFullFeed 73.6 ± 6.0, NoLookBack 75.8 ± 6.1; LimBanFeed 1567.9 ± 13.4, NoLookBack 2090.7 ± 21.2.
  • In the table, NoLookBack has the lower mean regret at m = 1000 and m = 2000 in the full-information setting, while the paper's text states that LimFullFeed consistently outperforms NoLookBack and that the gap between the two in the full-information setting is smaller for small m and that LimFullFeed becomes competitive as m increases. In the bandit setting, LimBanFeed is lower at every listed budget and the gap widens with larger m.
• Experiment 2 — qualitative trends: Regret decreases as m increases, consistent with the √(T/m) dependence in the theory. LimFullFeed and LimBanFeed both outperform NoLookBack over time on RouterBench and Nectar, with the gap interpreted as the cumulative number of suboptimal decisions. AllFeedback (feedback at every round) shows the smallest regret and consistently smaller variance across runs because it has substantially more feedback. Regret in the full-information setting is uniformly lower than in the bandit setting, matching the theory that richer feedback per observation reduces uncertainty faster.
• Runtime scaling (Table 2): Both methods scale approximately linearly with T. LimBanFeed scales linearly with K, while LimFullFeed is largely independent of K due to its shared covariance structure. Specific runtime numbers are not reported in the provided content.
• Budget accounting for the bandit algorithm: With z ≥ T/m, the number of evaluations satisfies Σ_a ⌊|S_{T,a}| / z⌋ ≤ T/z ≤ m, so the feedback budget is respected.

Methodology in Plain English

Each prompt is turned into a numeric embedding, and each LLM expert is modeled as a linear scoring head over that embedding, so the expected quality of expert a on prompt x is the inner product ⟨θ_a, x⟩; the actual observed reward adds independent sub-Gaussian noise with variance proxy 1. At every round the agent sees a prompt, picks an expert, and only afterwards decides whether to spend part of the observe-no-more-than-m budget on feedback for that expert or for some earlier round.

The central trick in both algorithms is what the agent chooses to look back at. Because rewards are revealed only occasionally, the usual bandit bookkeeping (adding each new prompt to the covariance matrix every round) breaks down. Instead, the agent waits until a scheduled feedback moment and then picks the past, not-yet-observed prompt whose inclusion most increases the determinant of the current covariance matrix. Intuitively, this spreads the agent's knowledge out evenly in all directions of the embedding space, shrinking uncertainty everywhere at once. Feedback is requested every roughly T/m rounds, which guarantees the budget is never exceeded.

The full-information variant keeps one shared covariance matrix across all experts, since a single query reveals every expert's reward for the chosen prompt. The bandit variant keeps a separate covariance matrix, estimator and observation set per expert, and uses an upper-confidence-bound rule to pick experts; it counts how often each expert has been used and requests feedback for an expert once that counter reaches about T/m, always choosing the past prompt served by that expert that most increases that expert's determinant. The paper also sketches an extension where experts have different evaluation prices z_j and are queried with a frequency proportional to their cost.

Why This Matters

The paper reframes a practical serving problem — which LLM should answer this prompt, given that nobody is grading the answers — as an online learning problem where the scarce resource is feedback rather than compute or time. It gives a principled rule for spending a fixed evaluation budget, and shows theoretically and empirically that how feedback is spent matters, not just how much.

Real-world applications:

• LLM routing gateways: A service fronting several models could route incoming prompts to the model likely to answer best, learning from a small budget of human or stronger-LLM judgments instead of grading every response.
• Cost-aware model selection: Extending the analysis to experts with different evaluation prices maps onto real price differences among commercial models and providers.
• Evaluation budgeting for LLM judges: Organizations already use expensive LLM-as-a-judge pipelines; the look-back strategy indicates which historical prompt-response pairs are most informative to grade.
• Adaptive assistants in document processing and code generation: These are the task families the paper cites as motivating LLM deployment, where a single routing policy must handle heterogeneous arriving prompts.

Industry relevance: the problem setting — expensive feedback, no ground truth at inference time, and a stream of user prompts — is exactly the operating regime of production model routers and AI platforms that mix first-party and third-party models.

Future Directions

• Close the bandit lower-bound gap. A d/√K gap remains between the bandit upper and lower bounds; the paper states that improving the lower bound is interesting future work, noting the current analysis reduces to hypothesis testing over a K-dimensional subspace.
• Dynamic expert availability. The conclusion lists experts appearing and disappearing as a direction not covered by the static formulation.
• Varying prompt distributions. The current problem assumes prompts arrive without prior knowledge of their distribution; the conclusion proposes studying changing prompt distributions.
• Tighter full-information bounds via known prompts. The √d gap in the full-information setting stems from not knowing prompts in advance; the paper notes the bound would be tight up to logarithmic factors if prompts were known.
• Beyond static benchmarks. The limitations section notes that static benchmarks simulate online routing and may not capture non-stationary user behavior or deployment constraints, and that the approach assumes past responses can be stored and retrospectively judged.

Target Audience

Researchers and practitioners working on bandits, online learning, and regret analysis, as well as engineers building LLM routing, model-selection, or evaluation systems with constrained human- or judge-based feedback budgets. It is also useful for readers interested in how classical linear-bandit machinery adapts when observations are deliberately scarce and chosen rather than automatic.

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