Online Learning with LLM Experts from Limited Feedback

Wang Wei; Soumyabrata Pal; Koyel Mukherjee; Franck Dernoncourt; Ryan A. Rossi; Branislav Kveton; Hoda Eldardiry

cs.LGSep 5, 2026

Online Learning with LLM Experts from Limited Feedback

Authors: Wang Wei, Soumyabrata Pal, Koyel Mukherjee, Franck Dernoncourt, Ryan A. Rossi, Branislav Kveton, Hoda Eldardiry

Organizations: Virginia Tech · Adobe Research

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.

Figures & tables

\displaystyle\textstyle a_{t}=\argmax_{a\in[K]}\langle\widehat{\theta}_{t-1,a},x_{t}\rangle

(3)

Algorithm 1

\tt LimFullFeed

: Limited full-information feedback for expert selection.

	$\displaystyle a_{t}$	$\displaystyle=\displaystyle\argmax_{a\in[K]}\langle\widehat{\theta}_{t-1,a},x_{t}\rangle+\beta\left\|\left\|x_{t}\right\|\right\|_{V_{t-1,a}^{-1}}$		(6)
		$\displaystyle n_{a_{t}}\leftarrow n_{a_{t}}+1$

Algorithm 2

\tt LimBanFeed

: Limited bandit feedback for expert selection.

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

	Full-information		Bandit
$m$	LimFullFeed	NoLookBack	LimBanFeed	NoLookBack
1000	$672.9\pm 37.4$	$\mathbf{631.6\pm 22.1}$	$\mathbf{3583.4\pm 68.0}$	$3789.6\pm 30.4$
2000	$441.4\pm 42.6$	$\mathbf{408.0\pm 26.2}$	$\mathbf{3084.1\pm 25.6}$	$3580.0\pm 73.3$
5000	$\mathbf{214.1\pm 7.7}$	$218.7\pm 10.6$	$\mathbf{2295.7\pm 42.3}$	$3020.7\pm 17.2$
10000	$\mathbf{128.0\pm 8.7}$	$129.0\pm 11.0$	$\mathbf{1839.1\pm 29.1}$	$2538.4\pm 22.2$
20000	$\mathbf{73.6\pm 6.0}$	$75.8\pm 6.1$	$\mathbf{1567.9\pm 13.4}$	$2090.7\pm 21.2$

Table 1: Cumulative regret with respect to feedback budget

m

on Nectar (

K{=}6

d{=}40

T{=}60000

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Axis	Value	LimBanFeed	LimFullFeed
$K$	2	$2.67\pm 0.02$	$1.73\pm 0.34$
	6	$4.30\pm 0.03$	$1.49\pm 0.01$
	10	$5.93\pm 0.04$	$1.47\pm 0.01$
	16	$8.36\pm 0.02$	$1.49\pm 0.04$
	20	$9.97\pm 0.00$	$1.47\pm 0.00$
$d$	8	$4.25\pm 0.00$	$1.49\pm 0.04$

Appendix

Table 2: Runtime in seconds with respect

K

d

, and

T

on Nectar.

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

Explore similar work

WISERouter: LLM Routing with Workload Budget Constraint
Jul 26, 2026Yifei Li, Zihui Gao, Laks V. S. LakshmananLLM Routing Contextual Bandits
The University of British Columbia
OrcaRouter: A Production-Oriented LLM Router with Hybrid Offline-Online Learning
May 29, 2026Zhenghua Bao, Fengya Tian, Chris Zhang +3Model Selection LLM Routing
Continuum AI
Learning to Route and Schedule LLMs from User Retrials via Contextual Queueing Bandits
Feb 2, 2026Seoungbin Bae, Junyoung Son, Dabeen LeeLLM Serving LLM Routing
Department of Industrial & Systems Engineering, KAIST · Graduate School of Data Science, KAIST · Department of Mathematical Sciences, Seoul National University

Jul 26, 2026J/K move · Enter open · S save

WISERouter: LLM Routing with Workload Budget Constraint

Yifei Li, Zihui Gao, Laks V. S. Lakshmanan

The University of British Columbia

LLM Routing Contextual Bandits

Open paper AskPDF arXiv

Large language models (LLMs) achieve impressive performance across multiple domains, but using the most capable model for every query is prohibitive at scale. LLM routing exploits diversity in model capability and cost by assigning each query to a suitable model to balance utility and budget. Current methods have two limitations: (i) they either use heuristics that do not always enforce the budget constraint or impose a fixed per-query budget that cannot adapt across the workload and leads to suboptimal performance; (ii) they require supervised learning on a dense dataset with statistics for every query-model pair, which is expensive to collect. To address these challenges, we formulate LLM routing as a constrained contextual multi-armed bandit problem and introduce WISERouter (WR for short), a framework that supports offline learning from historical interactions as well as online learning with exploration. We further prove that WR-Online achieves a sublinear regret bound of

O(\sqrt{T})

over a time horizon

T

. Empirical results on RouterBench and SWE-Bench demonstrate that (i) WR-Offline surpasses existing baselines in performance under a fixed budget and adheres more closely to budget constraints, and (ii) WR-Online achieves comparable performance to the baselines, while using substantially less exploration data.

Abstract

Explore similar work

WISERouter: LLM Routing with Workload Budget Constraint

OrcaRouter: A Production-Oriented LLM Router with Hybrid Offline-Online Learning

Learning to Route and Schedule LLMs from User Retrials via Contextual Queueing Bandits