Online Learning with LLM Experts from Limited Feedback
Wang Wei, Soumyabrata Pal, Koyel Mukherjee, Franck Dernoncourt, Ryan A. Rossi, Branislav Kveton, Hoda Eldardiry
Virginia Tech · Adobe Research
Published September 5, 2026 · on the feed September 14, 2026 · ▲ 6 · arXiv 2609.05820
The 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 O(d T / m), while in the bandit setting we achieve O(d T 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.
The Brief
1:44A short podcast summary of the paper. Written and voiced by AI.
Transcript
Online Learning with LLM Experts from Limited Feedback. By Wang Wei and six others, from Virginia Tech and Adobe Research. Published on the fifth of September. No code repository is linked to it.
The problem is routing. Prompts arrive online, and each has to be sent to one of several large language model experts, with the aim of maximizing response quality. Feedback is the scarce resource. The authors cast this as a bandit problem: K actions, one for each expert, and d features that encode each prompt, over a horizon of T rounds. On top sits a budget m on feedback, much smaller than T, which caps how many rewards can be observed at all.
They propose algorithms that choose strategically, both which expert to select and when to observe a reward, so as to minimize regret. Two bounds follow. In the full-information setting, regret is of order d times T over m. In the bandit setting, a factor of K for the number of experts enters as well, giving order d times T times K over m.
The lever is the decision about when to look. With feedback budgeted far below the number of rounds, which rewards to observe becomes part of the algorithm's own strategy, chosen together with which expert to select.
The bounds live inside the formulation: prompts described by d features, a fixed set of K experts, a known horizon of T rounds, and a feedback budget much smaller than that horizon. The two settings differ in what is revealed when feedback is taken, and the bandit setting pays for revealing less with its extra factor of K.
Experiments across diverse language models show high-quality routing strategies being learned efficiently from limited feedback. When judging a response is expensive, a router has to budget its looking as carefully as its choosing.
Paper Quest · 7 chapters · about 41 min
Play this paper
Learn it by doing: make the calls the authors made, guess the result before you see it, and defend it in a viva graded on your own words. Chapter 1 is right here.
Chapter 1 🧩 · The problem
Many models, endless prompts, and almost no ratings. Where would you spend them?
Prompts arrive one by one, and you must send each to one of several language models. No model is best everywhere, so the right choice depends on the prompt.
The road ahead
- 1 · The problem ~7 min Each arriving prompt must go to one of several language models, but learning which model suits which prompt needs ratings you can rarely afford.
- 2 · What came before ~3 min
- 3 · The key idea ~9 min Besides choosing a model, the algorithm chooses when to buy feedback and which past prompt to get rated, picking the most informative one.
- 4 · Choose your own research ~3 min
- 5 · Build the method ~8 min Each round: embed the prompt, route it to the expert with the best estimate, maybe buy feedback on a chosen past prompt, then update the estimates.
- 6 · The experiment ~6 min You’ll guess: The authors prove regret bounds for a full-information setting and a bandit setting. Which bound is larger?
- 7 · The viva ~5 min Three questions from the examiners, answered in your own words. Win it for the paper’s trophy.
Free, with Google or an email address. Your stars and progress are kept.