Online Learning with LLM Experts from Limited Feedback

• URL: http://arxiv.org/abs/2609.05820v1
• Date: Sat, 05 Sep 2026 02:30:59 GMT
• Title: Online Learning with LLM Experts from Limited Feedback
• Abstract summary: We study adaptive routing of prompts to large language model (LLM) experts to maximize response quality in an online setting with limited feedback.<n>We propose algorithms that strategically select and observe rewards to minimize regret.
• Score: 91.92265248492875
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• UCB-type Algorithm for Budget-Constrained Expert Learning [71.67657715154034]
  algnameM-LCB is a UCB-style meta-algorithm that provides emphanytime regret guarantees<n>We show how algnameM-LCB extends the classical bandit paradigm to the more realistic scenario of coordinating stateful, self-learning experts under limited resources.
  arXiv  Detail & Related papers  (2025-10-26T12:36:17Z)
• Online Learning with Sublinear Best-Action Queries [15.625072719419727]
  We study the power of emphbest-action queries, which reveal beforehand the identity of the best action at a given time step. We prove that in the full feedback model, $k$ queries are enough to achieve an optimal regret of $Thetaleft(minleftsqrt T, frac Tkrightright)$.
  arXiv  Detail & Related papers  (2024-07-23T09:59:43Z)
• Can Large Language Models Play Games? A Case Study of A Self-Play Approach [61.15761840203145]
  Large Language Models (LLMs) harness extensive data from the Internet, storing a broad spectrum of prior knowledge. Monte-Carlo Tree Search (MCTS) is a search algorithm that provides reliable decision-making solutions. This work introduces an innovative approach that bolsters LLMs with MCTS self-play to efficiently resolve turn-based zero-sum games.
  arXiv  Detail & Related papers  (2024-03-08T19:16:29Z)
• Learning Thresholds with Latent Values and Censored Feedback [18.129896050051432]
  We show a problem where the unknown reward $g(gamma, v)$ depends on the proposed threshold $gamma$ and latent value $v$ and it can be $only$ achieved if the threshold is lower than or equal to the unknown latent value. This problem has broad applications in practical scenarios, e.g., reserve price optimization in online auctions, online task assignments in crowdsourcing, setting recruiting bars in hiring.
  arXiv  Detail & Related papers  (2023-12-07T19:30:08Z)
• Contextual Bandits and Imitation Learning via Preference-Based Active Queries [17.73844193143454]
  We consider the problem of contextual bandits and imitation learning, where the learner lacks direct knowledge of the executed action's reward. Instead, the learner can actively query an expert at each round to compare two actions and receive noisy preference feedback. The learner's objective is two-fold: to minimize the regret associated with the executed actions, while simultaneously, minimizing the number of comparison queries made to the expert.
  arXiv  Detail & Related papers  (2023-07-24T16:36:04Z)
• $k\texttt{-experts}$ -- Online Policies and Fundamental Limits [8.84337023214151]
  This paper studies the $textttExperts$ problem. The learner selects a subset of $k$ experts from a pool of $N$ experts at each round. The reward obtained by the learner at any round depends on the rewards of the selected experts.
  arXiv  Detail & Related papers  (2021-10-15T06:30:15Z)
• Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
  We study a novel variant of online finite-horizon Markov Decision Processes with adversarially changing loss functions and initially unknown dynamics. In each episode, the learner suffers the loss accumulated along the trajectory realized by the policy chosen for the episode, and observes aggregate bandit feedback. Our main result is a computationally efficient algorithm with $O(sqrtK)$ regret for this setting, where $K$ is the number of episodes.
  arXiv  Detail & Related papers  (2021-01-31T16:49:07Z)
• Impact of Representation Learning in Linear Bandits [83.17684841392754]
  We study how representation learning can improve the efficiency of bandit problems. We present a new algorithm which achieves $widetildeO(TsqrtkN + sqrtdkNT)$ regret, where $N$ is the number of rounds we play for each bandit.
  arXiv  Detail & Related papers  (2020-10-13T16:35:30Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  We study a constrained contextual linear bandit setting, where the goal of the agent is to produce a sequence of policies. We propose an upper-confidence bound algorithm for this problem, called optimistic pessimistic linear bandit (OPLB)
  arXiv  Detail & Related papers  (2020-06-17T22:32:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.