Online LLM Selection via Constrained Bandits with Time-Varying Demand

• URL: http://arxiv.org/abs/2606.17489v1
• Date: Tue, 16 Jun 2026 03:58:48 GMT
• Title: Online LLM Selection via Constrained Bandits with Time-Varying Demand
• Abstract summary: Large Language Models (LLMs) are increasingly deployed in edge-cloud systems to handle diverse user tasks with heterogeneous accuracy, latency, and cost profiles.<n>We formulate this problem as a constrained bandit learning task, where the learner sequentially selects models under both packing-type (hard) and covering-type (soft) constraints.<n>We develop a novel online learning algorithm that leverages confidence-bound estimates and demand predictions to balance reward with long-term satisfaction.
• Score: 11.284703747922757
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Large Language Models (LLMs) are increasingly deployed in edge-cloud inference systems to handle diverse user tasks with heterogeneous accuracy, latency, and cost profiles. Selecting the appropriate LLM for each incoming task is critical for ensuring service quality and efficient resource utilization. However, model heterogeneity, stochastic and unknown performance characteristics, and time-varying task demands make static selection strategies inadequate. Real-world deployments often impose hard resource budgets such as monetary expenditure limits, along with soft service-level requirements such as latency guarantees. These constraints introduce additional challenges for online decision-making. We formulate this problem as a constrained stochastic bandit learning task, where the learner sequentially selects models under both packing-type (hard) and covering-type (soft) constraints, while adapting to time-varying task demand. The learner operates without access to the underlying reward, cost, or latency distributions and must rely on partial feedback. We develop a novel online learning algorithm that leverages confidence-bound estimates and demand predictions to balance reward maximization with long-term constraint satisfaction. We provide theoretical guarantees showing sublinear regret and sublinear covering constraint violations compared to an offline benchmark with full information. Experimental results on synthetic workloads demonstrate the effectiveness and robustness of our approach in dynamic, resource-constrained environments.

Related papers

• CDCP: Conditional Diffusion Model with Contextual Prompts for Multi-task Offline Safe Reinforcement Learning [63.5739698095413]
  Multi-task offline safe reinforcement learning (RL) promises to learn a shared optimal safe policy from offline data across multiple tasks.<n>However, the triple challenges of multi-tasking, safety constraints, and out-of-distribution actions pose a significant hurdle for existing methods.<n>We propose a Conditional Diffusion model with Contextual Prompts (CDCP) to address these challenges.
  arXiv  Detail & Related papers  (2026-07-04T14:57:35Z)
• Reliable LLM-Based Edge-Cloud-Expert Cascades for Telecom Knowledge Systems [54.916243942641444]
  Large language models (LLMs) are emerging as key enablers of automation in domains such as telecommunications.<n>We study an edge-cloud-expert cascaded LLM-based knowledge system that supports decision-making through a question-and-answer pipeline.
  arXiv  Detail & Related papers  (2025-12-23T03:10:09Z)
• Adaptive Neighborhood-Constrained Q Learning for Offline Reinforcement Learning [52.03884701766989]
  offline reinforcement learning (RL) algorithms typically impose constraints on action selection.<n>We propose a new neighborhood constraint that restricts action selection in the Bellman target to the union of neighborhoods of dataset actions.<n>We develop a simple yet effective algorithm, Adaptive Neighborhood-constrained Q learning (ANQ), to perform Q learning with target actions satisfying this constraint.
  arXiv  Detail & Related papers  (2025-11-04T13:42:05Z)
• BOTS: A Unified Framework for Bayesian Online Task Selection in LLM Reinforcement Finetuning [82.925106913459]
  Reinforcement finetuning (RFT) is a key technique for aligning Large Language Models (LLMs) with human preferences and enhancing reasoning.<n>We introduce BOTS, a unified framework for Bayesian Online Task Selection in RFT reinforcement finetuning.
  arXiv  Detail & Related papers  (2025-10-30T11:15:23Z)
• MESS+: Dynamically Learned Inference-Time LLM Routing in Model Zoos with Service Level Guarantees [17.478510146434218]
  Open-weight large language model (LLM) zoos provide access to numerous high-quality models.<n>Most users simply want factually correct, safe, and satisfying responses without concerning themselves with model technicalities.<n>We introduce MESS+, an optimization algorithm for cost-optimal LLM request routing.
  arXiv  Detail & Related papers  (2025-05-26T13:11:08Z)
• Offline Critic-Guided Diffusion Policy for Multi-User Delay-Constrained Scheduling [29.431945795881976]
  We propose a novel offline reinforcement learning-based algorithm, named underlineScheduling.<n>It learns efficient scheduling policies purely from pre-collected emphoffline data.<n>We show that SOCD is resilient to various system dynamics, including partially observable and large-scale environments.
  arXiv  Detail & Related papers  (2025-01-22T15:13:21Z)
• MUSBO: Model-based Uncertainty Regularized and Sample Efficient Batch Optimization for Deployment Constrained Reinforcement Learning [108.79676336281211]
  Continuous deployment of new policies for data collection and online learning is either cost ineffective or impractical. We propose a new algorithmic learning framework called Model-based Uncertainty regularized and Sample Efficient Batch Optimization. Our framework discovers novel and high quality samples for each deployment to enable efficient data collection.
  arXiv  Detail & Related papers  (2021-02-23T01:30:55Z)
• Coordinated Online Learning for Multi-Agent Systems with Coupled Constraints and Perturbed Utility Observations [91.02019381927236]
  We introduce a novel method to steer the agents toward a stable population state, fulfilling the given resource constraints. The proposed method is a decentralized resource pricing method based on the resource loads resulting from the augmentation of the game's Lagrangian.
  arXiv  Detail & Related papers  (2020-10-21T10:11:17Z)
• Regularized Online Allocation Problems: Fairness and Beyond [7.433931244705934]
  We introduce the emphregularized online allocation problem, a variant that includes a non-linear regularizer acting on the total resource consumption. In this problem, requests repeatedly arrive over time and, for each request, a decision maker needs to take an action that generates a reward and consumes resources. The objective is to simultaneously maximize additively separable rewards and the value of a non-separable regularizer subject to the resource constraints.
  arXiv  Detail & Related papers  (2020-07-01T14:24:58Z)
• Group-Fair Online Allocation in Continuous Time [27.32936573198251]
  We consider continuous-time online learning problem with fairness considerations. We show that this formulation recovers reward-maximizing, max-min fair and proportionally fair allocation rules. We propose a novel online learning algorithm based on dual ascent optimization for time averages.
  arXiv  Detail & Related papers  (2020-06-11T21:56:53Z)

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.