CS Paper Radar

Online Learning with LLM Experts from Limited Feedback

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

cs.LG stat.ML ·submitted 2026-09-05 02:30 UTC · v1

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.

Comment
21 pages, 4 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Ballad: Bandit-Based LLM Routing for Automated Heuristic Discovery

cs.AI ·2026-11-12 ·Samidha Verma, Ankit Anand, Sayan Ranu
similarity 0.73
Abstract

Modern automated heuristic discovery (AHD) systems increasingly rival hand-crafted heuristics by leveraging Large Language Models (LLMs) to iteratively mutate and refine solutions. A natural assumption is that more powerful and more expensive models consistently yield better heuristics. We challenge this empirically: across multiple NP-hard combinatorial optimization problems, we find no consistent advantage for larger, costlier models. This raises a deeper question: given a pool of LLMs spanning frontier and freely hosted or open-weight models, how should one adaptively select which model to invoke at each step of the search? The challenge is non-trivial. The optimal LLM may shift over the course of a run, and because one LLM's output seeds the context for subsequent calls, each model's reward signal is non-stationary and entangled across the heuristic population, thus violating the independence assumptions of classical online decision-making settings. We address this through Ballad (Bandit-based LLM Routing for Automated Heuristic Discovery), an online bandit algorithm that learns to orchestrate a pool of LLMs into an ensemble that matches or exceeds what any soloist LLM achieves alone. This orchestration is powered by an LLM selection policy that favors rare, high-scoring heuristics over stable averages, a DAG-based credit propagation mechanism through the genealogy of the heuristic population, and discounting of stale observations to remain attuned to each model's current utility. Across five NP-hard combinatorial optimization problems and a pool of four models of varying capability and cost, Ballad not only matches the best individual LLM in hindsight but, in several cases, surpasses every individual model while reducing API cost by up to 65.6% relative to always using the strongest model.

0.08

Multinomial Subset Routing with Sum-Max Rewards and Operational Constraints

cs.LG cs.AI ·2026-08-17 ·Quan Zhou, Yiyan Huang
similarity 0.72
Abstract

We study online routing to subsets of experts under aggregate bandit feedback and long-run operational constraints. Expert contributions can be complementary: for each task dimension, the best selected expert determines the contribution, and the total reward aggregates these dimension-wise maxima. At the same time, capacity, budget, and fairness requirements impose lower and upper bounds on long-run expert activation frequencies. A fixed deterministic subset cannot generally satisfy such heterogeneous requirements, motivating a stochastic routing policy. We formalize this problem as Multinomial Subset Routing (MSR). The learner maintains a distribution \(q\) over \(K\) experts, samples an expert independently \(M\) times from \(q\), and routes each task to the distinct sampled experts. We propose OMD-Approachability, which combines online mirror descent with Blackwell's approachability to optimize MSR under two-sided operational constraints. We establish \(O(T^{-1/2})\) average reward regret and expected constraint violation. We also quantify the approximation gap induced by a linear surrogate, and evaluate the approach on a real-world crowdsourcing dataset.

0.09

Dynamic Minimax Regret Optimization for Robust LLM Post-Training

cs.LG ·2026-10-05 ·Chengbo Zang, Haoyu Dong, Mehmet Kerem Turkcan, Gil Zussman, Zoran Kostic +1 more
theory similarity 0.71
Abstract

Modern LLM training increasingly relies on heterogeneous data sources spanning different domains, tasks, preference distributions, and difficulty levels. We study dynamic minimax regret for group-distributionally robust LLM post-training under instantaneous mini-batch-only bandit feedback. The framework views the training as a two-player sampler-optimizer process: a sampler adaptively selects among data sources using bandit feedback, while an optimizer updates the model parameters using stochastic gradients from the selected source. We focus on the practically restrictive setting where source losses evolve with model training but historical data are not re-evaluated, requiring the sampler to track instantaneous worst-sources from stale partial feedback. We propose DUCB-OGD, a simple and scalable algorithm that couples a Discounted Upper-Confidence-Bound sampler with an Online Gradient Descent optimizer. The sampler maintains exponential moving average loss estimates and confidence radii based on discounted effective sample sizes, avoiding costly re-evaluation of past data or intrusive changes to standard training pipelines. For $K$ data sources and $T$ training steps, we prove that DUCB-OGD achieves a dynamic minimax regret of $\tilde{O}(K^{1/4}T^{3/4})$, which is optimal up to logarithmic factors for the undiscounted objective under our feedback model. Extensive experiments across supervised fine-tuning, preference optimization, and reinforcement learning show that DUCB-OGD integrates seamlessly into modern LLM training pipelines and improves worst-group robustness with negligible computational overhead compared with standard sampling baselines.

0.24

AFA-BANDIT: Provably Near-Optimal Online Multi-Feature Classification Under Budget Constraints

cs.LG ·2026-10-06 ·AbdAlRahman Odeh, Teng-Hui Huang, Hesham El Gamal
theory similarity 0.71
Abstract · 10 pages, 3 figures

Active Feature Acquisition (AFA) is a classification problem in which an agent decides which costly features to acquire before predicting each sample's label. Unlike batch AFA, which trains a fixed policy and classifier offline on fully observed data, online AFA updates its predictor from revealed labels as samples arrive. Existing online methods either use deep reinforcement learning (RL) without performance guarantees or maximize cost-adjusted reward rather than enforce a global budget. We formulate online AFA as a combinatorial Bandits with Knapsacks (BwK) problem that couples acquisition and prediction. Unlike prior bandit-based AFA and classical BwK, our setting has combinatorial complexity, evolving rewards, a global budget, and structured side information. We obtain an improved regret upper bound over standard BwK bounds in this framework, leveraging a cardinality-aware confidence bound and the subset update structure. To avoid an exponentially large action space, we propose \emph{LP-Chain}, a variant that searches a cost-aware chain of feature subsets with a size that grows linearly with the number of features. While the regret upper bound is specific to the combinatorial framework, \emph{LP-Chain} empirically achieves comparable predictive performance. On synthetic data, \emph{LP-Chain} outperforms HEDGE-based BwK and deep RL-based online AFA baselines and scales favorably to more features.

0.26

Generalized Prediction Set with Bandit Feedback

cs.LG stat.ML ·2026-11-16 ·Zhou Wang, Xingye Qiao
publishedtheory similarity 0.71
Abstract

In high-stakes environments where uncertainties abound, set-valued prediction offers a cautious and robust mechanism by presenting multiple potential labels as the prediction for each test instance to mitigate the potential risk associated with prediction errors. Yet, integrating this paradigm with out-of-distribution (OOD) detection remains scarcely explored in such settings as online learning with bandit feedback. The bandit feedback mechanism informs the learner about the correctness of the pulled arm/action instead of the explicit ground truth label, leaving the true class label unknown when an incorrect action is taken. To address this challenge, we introduce BanditGPS which conducts set-valued prediction with OOD detection in the bandit feedback setting, using an estimation to the ground truth of class labels. BanditGPS achieves three objectives: render small/informative prediction sets, enhance the OOD detection performance, and control the recall for all normal classes to meet prescribed requirements. Our approach is characterized by the loss function, which trades off between high OOD detection and small prediction sets. Theoretically, we prove that the convergence rate of the regret is $\tilde{\mathcal{O}}(T^{-1/2})$. The empirical results further show that BanditGPS effectively controls the recalls with promising performances on OOD detection and informative prediction.

0.19

Chance-Constrained Personalized LLM Routing with Online Preference Learning

cs.LG stat.AP ·2026-10-15 ·Ameya Anjarlekar, Rasoul Etesami, R Srikant
similarity 0.70
Abstract · 18 pages, 8 figures, 1 table

We study personalized LLM routing, where a router selects among heterogeneous models with different costs and capabilities. The router must minimize cumulative inference cost while ensuring reliable realized response quality, even though user preferences are unknown and must be learned from feedback during deployment. We formulate this problem as a constrained contextual bandit and develop an algorithm that learns preferences while balancing cost and quality. Under a logistic preference model and a strict-feasibility condition, we establish sublinear expected cost regret relative to an optimal stationary randomized contextual oracle and a high-probability guarantee on realized cumulative satisfaction. The framework extends beyond LLM routing to broader online model-selection problems with reliability requirements.

0.27

Efficient Online Submodular Maximization with Bandit Feedback

cs.LG ·2026-11-09 ·Iasonas Nikolaou, Evimaria Terzi
similarity 0.70
Abstract · 31 pages

We study online monotone submodular maximization under a cardinality constraint with bandit feedback. On each round, the learner selects at most $k$ elements from a ground set of size $n$ and observes only the value of the selected set. We develop an efficient algorithm achieving $O\!\left(k\sqrt{nT\log(n/k)}\right)$ expected $(1-1/e)$-regret over $T$ rounds. To our knowledge, this is the first polynomial-time algorithm with $\sqrt{T}$ dependence on the horizon for arbitrary monotone submodular functions in the bandit setting. Our approach uses randomized sampling and a carefully constructed potential to reduce online submodular maximization to online linear optimization over the probability simplex.

0.12

Contextual Non-Convex Bandit Optimization with Two-Point Feedback

cs.LG ·2026-11-13 ·Khaled Eldowa, Pierre Gaillard
similarity 0.70
Abstract

We study a non-stochastic contextual bandit problem with Lipschitz losses. At every round, the learner observes the context then picks two actions, observes the difference between their losses, and incurs their mean. The aim is to minimize the regret against a generic non-parametric comparator class of policies mapping contexts to actions; for example, Lipschitz policies and Hölder-smooth policies. We show how relying on a hierarchical discretization technique allows us to improve upon the regret rates achievable under one-point feedback, and even recover the full-information rate in some cases; notably, for sufficiently smooth policy classes or low-dimensional instances. Additionally, for Lipschitz policies, we present an algorithm whose per-round computational complexity is only logarithmic in the time horizon.

0.13