Queueing Theory

Follow this topic Ask about this topic

Latest papers

18 papers3 papers in the last four weeks, against 2 the four weeks before. 0.0% of all new papers.

Oct 13, 2026

Learning in Strategic Queuing with Geometric Recharge: From Bandits to Systems

We study packet routing in queuing systems where queues act as selfish, myopic agents that use no-regret learning algorithms to select servers with unknown service rates. To model the small buffers used in data centers, we assume that each server has a single-packet buffer. Even such a tiny buffer already captures the features of buffering: routers can exploit multiple servers while accepted packets remain in service, but packets can occupy servers for multiple rounds, complicating future service and learning. We first analyze a single queue routing packets to

m

buffered servers with service rates

μ_1, \dots, μ_m

. This setting is equivalent to an instance of the recharging bandits problem with geometric recharge. We prove that any no-regret learner achieves a long-run average throughput of at least the Hamacher sum of the server rates, and that this bound is tight. Consequently, a single no-regret queue is stable if and only if its arrival rate is below the Hamacher sum of the server rates. Moreover, comparing against an optimal policy, we show that any no-regret learner is at least

0.77

-competitive, which is also tight. We then study multi-queue systems where

n

queues with arrival rates

λ_1, \dots, λ_n

, each at most

λ_{\max}

, compete for service from

m

buffered servers. We show that the smallest overprovisioning factor that guarantees the system to be stable under high-probability no-regret learning is

\frac{1}{1-λ_{\max}}

. Equivalently, in terms of the total arrival and service rates, the condition

\sum_{i=1}^n λ_i < (1-λ_{\max})\sum_{j=1}^m μ_j

is sufficient, and sometimes necessary, for stability under no-regret learning. In particular, for

λ_{\max} = 1/2

, this improves the upper bound of Abel et al. (EC 2026) from

3

to

2

, matching their lower bound and resolving their open question.

Cristian Palma Foster, Eva Tardos

Cornell University

Queueing Theory Regret Minimization

Oct 5, 2026

Learning While Scheduling Jobs under Context-Dependent Service Rates: An Anytime Rate-Optimal Algorithm

We study contextual queueing bandits, where a learner schedules jobs while learning unknown service rates modeled by logistic functions of job-server features. Performance is measured by queue length regret, the expected excess queue length at round

t

relative to an oracle that knows the service rates. Existing decaying-regret guarantees either have a suboptimal decay rate or require a known fixed horizon. They also assume context-wise slack and a strictly positive minimum eigenvalue of the feature covariance. In this paper, we propose WISE (Widest Interval Selection with Elimination), achieving rate-optimal

\widetilde{\mathcal O}(t^{-1/2})

queue length regret at every sufficiently large time without knowing the horizon. We assume capacity slack, meaning that expected incoming workload under best-server service is below service capacity, and impose no covariance lower bound. Our analysis uses a workload potential measuring the expected service attempts needed by waiting jobs on their best servers. Its drift on nonempty rounds combines a negative term ensured by capacity slack with errors from suboptimal service choices. Then an elliptical potential count bounds how often WISE selects wide confidence intervals, thereby limiting the number of rounds with large service errors. We also sharpen the arrival-rate dependence of an existing lower bound and make its dependence on feature dimension and server count explicit. We prove another lower bound that quantifies the increase in regret as the normalized capacity slack decreases; to our knowledge, this is the first such lower bound for CQB. Simulations show small regret even when context-wise slack fails.

Seoungbin Bae, Dabeen Lee

Department of Industrial & Systems Engineering, KAIST · Department of Mathematical Sciences, Seoul National University

Multi-Armed Bandits Contextual Bandits Generalized Linear Bandits Queueing Theory

Sep 29, 2026

Nonpreemptive Scheduling While Learning Context-Dependent Service Rates

We study nonpreemptive contextual queueing bandits in a single-server system. Each job is represented by a

d

-dimensional context vector; in each round, a job may arrive with its context drawn from an unknown distribution

\mathcal{D}

, and its departure probability is determined by a logistic model of that context vector with an unknown parameter

θ^*

. The server learns from service outcomes while deciding which waiting job to serve and whether to idle, aiming to minimize queue-length regret, the gap between its expected terminal queue length and the minimum achievable by an admissible policy. Once selected, a job must be served until completion, and we refer to this as the nonpreemptive setting. A central challenge is that, even with full model knowledge, the optimal policy cannot in general be characterized by a simple myopic rule, since the optimal action can change with the remaining horizon at the same queue state. Nevertheless, when the model and horizon are known, the optimal action can be obtained through a finite-horizon Bellman recursion. Motivated by this, we propose Learn--Clear--Plan (LCP), which estimates the system and uses the resulting Bellman recursion to make horizon-dependent decisions. LCP achieves

\widetilde{O}(\sqrt{d/T})

queue-length regret, while a lower-bound construction gives

Ω(\min\{1/\sqrt{d},\sqrt{d/T}\})

regret for every learning policy on some instance, establishing optimality up to polylogarithmic factors when

T\ge d^2

. When the horizon is unknown, no horizon-independent policy achieves vanishing regret against the finite-horizon optimum. We therefore use SEPT, the policy that serves a waiting job with the highest probability of departure, as a fixed reference, and suggest an estimated-SEPT algorithm that achieves a tracking error of

\widetilde{O}(\sqrt{d/t})

without knowing the model.

Wansoo Choi, Seoungbin Bae, Dabeen Lee

Department of Mathematical Sciences, Seoul National University · Department of Industrial & Systems Engineering, KAIST

Queueing Theory Contextual Bandits Real-Time Scheduling

Sep 7, 2026

Learning Adaptive SED for heterogeneous load balancing

We study a two-server load balancing system with heterogeneous service rates that are a priori unknown to the dispatcher. The goal is to route customers according to the Shortest--Expected--Delay (SED) policy, but this requires knowledge of the service rates. Empirical policies that route based on estimates perform poorly: due to estimation error, the empirical policy disagrees with the oracle on an infinite region of the state space. We propose an online learning algorithm that converges to SED while learning the service rates. The algorithm carefully balances empirical SED routing with forced exploration phases that guarantee sufficient sampling of both servers. We prove that our algorithm achieves finite regret; this differs from classical Multi-Armed Bandit settings where regret typically grows logarithmically in time. Finally, numerical experiments demonstrate the performance of our algorithm and highlight the regimes in which forced exploration is especially beneficial.

Sanne van Kempen, Jaron Sanders, Fiona Sloothaak +1

Queueing Theory Online Resource Allocation Exploration-Exploitation Tradeoff

Aug 25, 2026

The Shadow Price of Intelligence: Quality Degradation in LLM Inference as a Supply Chain Problem

Large language model providers are compute constrained, and a common response to congestion is to degrade service. A degraded answer fails with some probability, and a failed answer either returns as a retry or departs as churn, destroying LTV on an unaccounted ledger. We model inference allocation as a newsvendor whose stockout cost is churned lifetime value, a geometric retry multiplier in which the recycled product is dissatisfaction, and a two-regime transient fluid queue whose arrival rate is made endogenous by retries. Statically, there is a regime in which a cheaper model saves energy per initiated task while consuming strictly more capacity per initiated task, so the discount inverts when capacity binds. Dynamically, a reactive throttle fired during a surge can cross an ignition threshold beyond which it manufactures more traffic than it sheds, and a release rule set below the degraded equilibrium converts a transient surge into a permanent degraded regime. With heterogeneous customers, throttling is a transportation problem in retry-inflated load whose optimal policy rations intelligence by critical ratio, and whose dual, the shadow price of intelligence, prices a marginal query by class and by hour. Under congestion, throttling is not a cost lever but a demand lever.

Elioth Sanabria

Department of Decision and Technology Analytics Lehigh University - College of Business

Queueing Theory LLM Serving LLM Inference Scheduling Cost-Aware Inference

Jul 30, 2026

Reflected UAS: Corrected Deterministic Stability and Direct CTMC Drift Calculation

We analyze Reflected UAS routing for heterogeneous multi-server queues at fixed parameters under subcritical load. The deterministic surrogate is a reflected ODE on the nonnegative orthant, not the unconstrained drift equation. This reflected ODE has a unique boundary equilibrium characterized by a scalar consistency equation and a convex-potential representation; all trajectories converge to it. The older argument lifting deterministic Lyapunov descent to CTMC stability fails: the exact generator applied to the deterministic potential produces a boundary term absent from the reflected-ODE descent identity. We give a direct Foster-Lyapunov drift inequality for the CTMC using a weighted-quadratic function, bypassing the failed lift. At the benchmark parameter point, the boundary equilibrium matches the numerical attractor to machine precision, and the default Reflected UAS policy has lower mean queue length than UAS and JSSQ across independent seed blocks.

Krishna Subedi

Neryva

Dynamical Systems Lyapunov Stability Queueing Theory

Jun 18, 2026

Optimal Scheduling in a Question-Answering Forum of Knowledge Workers

As individuals turn to the Internet to find answers to questions they may have, several Question Answering (QA) forums have evolved, where users knowledgeable in certain topics can contribute their expertise to answering these requests for information. While these are currently volunteer based, we consider a future version employing knowledge workers who are experts in certain topics. In such a system, the request-answer processes forming the queuing system may utilize schedulers that assign requests in different topics to the experts in the forum, who may be able to answer them according to their expertise levels in different topics. With this model, we calculate the capacity of the system for handling the requests while keeping the system stable, and design schedulers that achieve capacity. We also investigate how collaboration between experts in answering requests can potentially increase capacity.

Rohit Negi, Mustafa Yilmaz

Carnegie Mellon University

Expert Load Balancing Question Answering Expert Routing Queueing Theory

Jun 16, 2026

Finite-Time Queue Peak Laws in Stochastic Networks: Logarithmic Scaling After Geometric Thresholds

We study finite-horizon queue peaks in generalized switches, a standard stochastic-network model in which many queues share constrained service resources. Arrivals may be dependent, nonstationary, and responsive to the system history; the only load condition is uniform interior slack, meaning the conditional mean arrival vector stays in a fixed contraction of the capacity region. We show that this slack reshapes the finite-time peak law for drift-minimizing scheduling policies such as MaxWeight. The square-root envelope that is sharp without slack persists only up to a geometry-dependent threshold; beyond that threshold, the running maximum grows only logarithmically with the horizon, both with high probability and in expectation. The mechanism is self-normalization: in the current queue direction, the projected fluctuation scale is normalized by the stabilizing drift scale. This removes capacity geometry from the logarithmic coefficient, while geometry remains in the threshold. Matching lower bounds show that both the logarithmic term and a geometric threshold are unavoidable. When finite-time state-space collapse is available, the threshold can be sharpened using local bottleneck geometry. For generalized input-queued switches, we obtain finite-time peak bounds with tight logarithmic coefficients. Simulations illustrate the two-phase envelope, local geometric refinements, and variance-sensitive improvements predicted by the theory.

Hao Liang, Cheng Tang, Yunzong Xu

University of Illinois Urbana–Champaign

Queueing Theory

Jun 8, 2026

Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret

Contextual queueing bandits provide a framework for learning to schedule heterogeneous jobs under unknown context-dependent service rates. Under stochastic contexts, existing algorithms achieve

\widetilde{\mathcal{O}}(T^{-1/4})

queue length regret, defined as the expected difference between the learner's and oracle's queue lengths at horizon

T

. In this paper, we improve this rate to

\widetilde{\mathcal{O}}(T^{-1/2})

. The key observation is that random exploration is needed only up to a carefully chosen cutoff round, rather than throughout the entire horizon. We propose CQB-

η

-2, a three-phase algorithm: (i) pure random exploration to construct an initial estimator, (ii)

η

-random exploration combined with a UCB rule to continue learning while maintaining negative drift, and (iii) pure UCB after the exploration cutoff. Our proof decomposes the queue length regret at the cutoff round. Before the cutoff, negative drift suppresses queue length differences caused by suboptimal choices. After the cutoff, the first two phases provide sufficient random exploration samples, ensuring that UCB decisions incur small departure-rate gaps. Combining these two bounds yields queue length regret of order

\widetilde{\mathcal{O}}(T^{-1/2})

. We further prove a minimax lower bound of order

Ω(T^{-1/2})

. The proof constructs two hard instances that are statistically indistinguishable up to the final service decision, and uses a queue-specific coupling argument to convert the resulting testing error into queue length regret. Together, our upper and lower bounds characterize the minimax dependence on the horizon

T

up to logarithmic factors.

Seoungbin Bae, Dabeen Lee

Department of Industrial & Systems Engineering, KAIST · Department of Mathematical Sciences, Seoul National University

Exploration-Exploitation Tradeoff Regret Minimization Contextual Bandits UCB Algorithms Queueing Theory

May 22, 2026

Identifying and Mitigating Systemic Measurement Bias in Production LLM Inference Benchmarks

As Large Language Models (LLMs) transition from research environments to production deployments, evaluating their performance against strict Service Level Objectives (SLOs) has become critical. However, current evaluation methodologies suffer from severe measurement bias at scale. We demonstrate that widely used benchmarking utilities rely on single-process, asyncio-driven architectures that introduce fundamental client-side queuing bottlenecks under high concurrency. By modeling the benchmarking client as an

M/G/1

queue, we mathematically demonstrate how the Python Global Interpreter Lock (GIL) artificially inflates Time to First Token (TTFT) and Time Per Output Token (TPOT) metrics as request rates scale. To resolve this systematic inaccuracy, we propose an unbiased, multi-process evaluation framework that effectively distributes client-side load, ensuring negligible queuing overhead. Furthermore, we formalize a composite metric, Normalized Time Per Output Token (NTPOT), to robustly amortize end-to-end latency, including prefill and scheduling delays across sequence lengths. Our empirical evaluation demonstrates that this methodology successfully isolates pure serving engine performance, enabling accurate, reproducible profiling of LLMs at production scales exceeding thousands of queries per second.

Ashok Chandrasekar, Jason Kramberger

Google

LLM Evaluation LLM Serving LLM Inference Benchmark Design Queueing Theory

Apr 12, 2026

A Queueing-Theoretic Framework for Dynamic Attack Surfaces: Data-Integrated Risk Analysis and Adaptive Defense

We develop a queueing-theoretic framework to model the temporal evolution of cyber-attack surfaces, where the number of active vulnerabilities is represented as the backlog of a queue. Vulnerabilities arrive as they are discovered or created, and leave the system when they are patched or successfully exploited. Building on this model, we study how automation affects attack and defense dynamics by introducing an AI amplification factor that scales arrival, exploit, and patching rates. Our analysis shows that even symmetric automation can increase the rate of successful exploits. We validate the model using vulnerability data collected from an open source software supply chain and show that it closely matches real-world attack surface dynamics. Empirical results reveal heavy-tailed patching times, which we prove induce long-range dependence in vulnerability backlog and help explain persistent cyber risk. Utilizing our queueing abstraction for the attack surface, we develop a systematic approach for cyber risk mitigation. We formulate the dynamic defense problem as a constrained Markov decision process with resource-budget and switching-cost constraints, and develop a reinforcement learning (RL) algorithm that achieves provably near-optimal regret. Numerical experiments validate the approach and demonstrate that our adaptive RL-based defense policies significantly reduce successful exploits and mitigate heavy-tail queue events. Using trace-driven experiments on the ARVO dataset, we show that the proposed RL-based defense policy reduces the average number of active vulnerabilities in a software supply chain by over 90% compared to existing defense practices, without increasing the overall maintenance budget. Our results allow defenders to quantify cumulative exposure risk under long-range dependent attack dynamics and to design adaptive defense strategies with provable efficiency.

Jihyeon Yun, Abdullah Yasin Etcibasi, Ming Shi +1

University at Buffalo (SUNY), USA.

Long-Range Dependency Modeling Queueing Theory Cybersecurity Autonomous Cyber Defense Software Supply Chain Security

Apr 4, 2026

Regime-Calibrated Fleet Repositioning with a Spatial Queue-Regret Decomposition

Ride-hailing and autonomous mobility-on-demand operators reposition idle supply before future demand is fully observed. We study a retrieval-calibrated predict-then-optimize approach for this problem: historical demand regimes are matched to the current query block, combined into a calibrated demand prior, and passed to a fleet-balancing controller. The paper makes three contributions. First, we train a leakage-safe similarity gate whose objective penalizes demand error, pickup spatial mismatch, and queue shortage risk rather than retrieval rank alone. Second, we develop a spatial queue-regret decomposition for a stable queueing surrogate, linking demand-field error to wait through queueing sensitivity, allocator sensitivity, and Wasserstein pickup mismatch. Third, we evaluate learned retrieval and external-style rebalancing baselines in a common simulator. In the calibrated-demand gate experiment, across eight New York City scenarios and ten seeds, the spatial gate reduces mean wait to 82.3s, compared with 85.3s for hand-tuned similarity and 85.8s for a distributional-only baseline. In a separate replay-demand controller comparison, a scenario chance-MPC analog and a share-target transportation LP improve on Wen-style rebalancing (92.2s/92.2s vs. 100.1s), a reduced GPR chance-MPC comparator is intermediate at 94.4s, and an oracle MPC diagnostic is 91.3s.

Indar Kumar, Akanksha Tiwari

Queueing Theory Vehicle Routing

Apr 4, 2026

Multi-Robot Multi-Queue Control via Exhaustive Assignment Actor-Critic Learning

We study online task allocation for multi-robot, multi-queue systems with asymmetric stochastic arrivals and switching delays. We formulate the problem in discrete time: each location can host at most one robot per slot, servicing a task consumes one slot, switching between locations incurs a one-slot travel delay, and arrivals at locations are independent Bernoulli processes with heterogeneous rates. Building on our previous structural result that optimal policies are of exhaustive type, we formulate a discounted-cost Markov decision process and develop an exhaustive-assignment actor-critic policy architecture that enforces exhaustive service by construction and learns only the next-queue allocation for idle robots. Unlike the exhaustive-serve-longest (ESL) queue rule, whose optimality is known only under symmetry, the proposed policy adapts to asymmetry in arrival rates. Across different server-location ratios, loads, and asymmetric arrival profiles, the proposed policy consistently achieves lower discounted holding cost and smaller mean queue length than the ESL baseline, while remaining near-optimal on instances where an optimal benchmark is available. These results show that structure-aware actor-critic methods provide an effective approach for real-time multi-robot scheduling.

Mohammad Merati, H. M. Sabbir Ahmad, Wenchao Li +1

Divisions of Systems Engineering, Boston University, 8 St Mary’s St, Boston, MA 02215, United States. · Department of Electrical and Computer Engineering, Boston University, 8 St Mary’s St, Boston, MA 02215, United States.

Multi-Robot Task Allocation Robot Policy Learning Queueing Theory Actor-Critic Methods Markov Decision Processes

Mar 30, 2026

From Simulation to Deep Learning: Survey on Network Performance Modeling Approaches

Network performance modeling is a field that predates early computer networks and the beginning of the Internet. It aims to predict the traffic performance of packet flows in a given network. Its applications range from network planning and troubleshooting to feeding information to network controllers for configuration optimization. Traditional network performance modeling has relied heavily on Discrete Event Simulation (DES) and analytical methods grounded in mathematical theories such as Queuing Theory and Network Calculus. However, as of late, we have observed a paradigm shift, with attempts to obtain efficient Parallel DES, the surge of Machine Learning models, and their integration with other methodologies in hybrid approaches. This has resulted in a great variety of modeling approaches, each with its strengths and often tailored to specific scenarios or requirements. In this paper, we comprehensively survey the relevant network performance modeling approaches for wired networks over the last decades. With this understanding, we also define a taxonomy of approaches, summarizing our understanding of the state-of-the-art and how both technology and the concerns of the research community evolve over time. Finally, we also consider how these models are evaluated, how their different nature results in different evaluation requirements and goals, and how this may complicate their comparison.

Carlos Güemes-Palau, Miquel Ferriol-Galmés, Jordi Paillisse-Vilanova +2

Universitat Politècnica de Catalunya (UPC), Barcelona, Catalonia, Spain

Queueing Theory

Mar 11, 2026

A Learning-Based Superposition Operator for Non-Renewal Arrival Processes in Queueing Networks

The superposition of arrival processes is a fundamental yet analytically intractable operation in queueing networks when inputs are general non-renewal streams. Classical methods either reduce merged flows to renewal surrogates, rely on computationally prohibitive Markovian representations, or focus solely on mean-value performance measures. We propose a scalable data-driven superposition operator that maps low-order moments and autocorrelation descriptors of multiple arrival streams to those of their merged process. The operator is a deep learning model trained on synthetically generated Markovian Arrival Processes (MAPs), for which exact superposition is available, and learns a compact representation that accurately reconstructs the first five moments and short-range dependence structure of the aggregate stream. Extensive computational experiments demonstrate uniformly low prediction errors across heterogeneous variability and correlation regimes, substantially outperforming classical renewal-based approximations. When integrated with learning-based modules for departure-process and steady-state analysis, the proposed operator enables decomposition-based evaluation of feed-forward queueing networks with merging flows. The framework provides a scalable alternative to traditional analytical approaches while preserving higher-order variability and dependence information required for accurate distributional performance analysis.

Eliran Sherzer

Industrial Engineering, Ariel University, Ramat HaGolan St 65, Ariel, 4070000, Israel.

Queueing Theory Temporal Point Processes Neural Surrogate Modeling

Feb 16, 2026

Noncooperative Virtual Queue Coordination via Uncertainty-Aware Correlated Equilibria

Collaborative virtual queueing has been proposed as a mechanism to mitigate airport surface congestion while preserving airline autonomy over aircraft-level pushback decisions. A central coordinator can regulate aggregate pushback capacity but cannot directly control which specific aircraft are released, limiting its ability to steer system-level performance. We propose a noncooperative coordination mechanism for collaborative virtual queueing based on the correlated equilibrium concept, which enables the coordinator to provide incentive-compatible recommendations on aircraft-level pushback decisions without overriding airline autonomy. To account for uncertainty in airlines' internal cost assessments, we introduce chance constraints into the correlated equilibrium formulation. This formulation provides explicit probabilistic guarantees on incentive compatibility, allowing the coordinator to adjust the confidence level with which airlines are expected to follow the recommended actions. We further propose a scalable algorithm for computing chance-constrained correlated equilibria by exploiting a reduced-rank structure. Numerical experiments demonstrate that the proposed method scales to realistic traffic levels up to 210 eligible pushbacks per hour, reduces accumulated delay by up to approximately 8.9% compared to current first-come-first-served schemes, and reveals a trade-off between confidence level, deviation robustness, and achievable cost efficiency.

Jaehan Im, David Fridovich-Keil, Ufuk Topcu

Department of Aerospace Engineering, The University of Texas at Austin, Austin, Texas, USA

Air Traffic Management Multi-Agent Coordination Queueing Theory Game Theory Chance-Constrained Optimization

Aug 5, 2025

Reinforcement Learning in MDPs with Information-Ordered Policies

Many operational Markov decision processes provide structured information where a trajectory generated under one policy may also reveal how other policies would have performed. We formalize this through an information order over a parameterized policy class, writing

π_{θ'} \preceq π_θ

when data collected under

π_θ

can be used to estimate the long-run average cost of

π_{θ'}

. We develop an epoch-based reinforcement learning algorithm for infinite-horizon average-cost MDPs with continuous state and action spaces that exploits this order through counterfactual inference. For a

d

-dimensional policy class whose information order has width

w

, the algorithm achieves

\widetilde O(H\sqrt{wdT/α})

regret relative to the optimal policy in the class, where

H

is a bias span upper bound and

α

denotes an "information ratio". Thus, the width captures the effective exploration complexity of the problem, interpolating between full counterfactual feedback and unstructured policy learning. We instantiate the framework in lost-sales inventory systems with positive lead times, dual-sourcing systems governed by dual-index policies, and queues with state-dependent service rates. These applications yield new regret guarantees without requiring global convexity of the average-cost function or specialized arrival-rate structure. Numerical experiments show that exploiting the information order substantially improves learning performance over existing general-purpose and problem-specific benchmarks.

Zhongjun Zhang, Shipra Agrawal, Ilan Lobel +2

Department of Industrial Engineering and Management Sciences, Northwestern University · Department of Industrial Engineering and Operations Research, Columbia University · Technology, Operations, and Statistics, Stern School of Business, New York University +1

Queueing Theory Policy Learning Regret Minimization in RL Average-Reward RL Counterfactual Learning

Dec 13, 2021

Learning to Schedule in Parallel-Server Queues with Stochastic Bilinear Rewards

We consider the problem of scheduling in multi-class, parallel-server queuing systems with uncertain rewards from job-server assignments. In this scenario, jobs incur holding costs while awaiting completion, and job-server assignments yield observable stochastic rewards with unknown mean values. The mean rewards for job-server assignments are assumed to follow a bilinear model with respect to features that characterize jobs and servers. Our objective is to minimize regret by maximizing the cumulative reward of job-server assignments over a time horizon, while keeping the total job holding cost bounded to ensure the stability of the queueing system. This problem is motivated by applications requiring resource allocation in network systems. A central challenge is to control the tradeoff between reward maximization and fair allocation for the stability of the underlying queuing system (i.e., maximizing network throughput). To address this challenge, we propose a scheduling algorithm based on a weighted proportional fair criteria augmented with marginal costs for reward maximization, incorporating a bandit algorithm tailored for bilinear rewards. Our algorithm admits a regret--queue length tradeoff. For any fixed control parameter

V>0

, it ensures a uniform expected queue length and time-average holding-cost bounds. For a target horizon

T

, choosing

V_T=Θ(\sqrt{IT})

at initialization yields

\widetilde O((\sqrt I+d^2)\sqrt T+1/δ)

regret. Under this regret-optimized tuning, the corresponding expected queue length and time-average holding-cost bounds remain uniform over the execution time and scales as

O(\sqrt{IT}+1/δ)

and

O(\sqrt{IT}/δ)

, respectively.

Jung-hun Kim, Milan Vojnovic

CREST, ENSAE Paris, France · London School of Economics, United Kingdom

Multi-Armed Bandits Online Resource Allocation Queueing Theory