REVIEW 4 major objections 6 minor 27 references
Demonstration of effective UCB-based routing in skill-based queues on real-world data
T0 review · 4 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read A modified upper-confidence-bound routing algorithm learns payoffs and queue rates online and, on a month of real bank call-center data, reaches on average 99.0% of the all-knowing Oracle payoff while cutting waiting times with a…
desk verdict A useful, honest engineering demonstration of UCB-QR on real call-center data, with one load-bearing mismatch: the Oracle benchmark inherits an exponential-service LP while the simulation uses empirical service-time distributions. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The engine is the optimal-transport linear program (1): maximize total expected payoff $\sum_{(ij)\in L} \theta_{ij} x_{ij}$ subject to all customers of each type being routed and each server's load bounded by $1-\varepsilon$. Each episode, UCB estimators $\hat\theta^k_{ij}=\bar\theta_{ij}+\sqrt{\ln k/T_{ij}(k)}$ inflate uncertain payoffs to drive exploration, while a linear-trend forecast predicts the next episode's arrival rates and empirical means estimate service rates; the LP maximizer supplies routing rates. Algorithm 2 dispatches customers to virtual queues according to normalized rates; Algorithm 3 replaces this with a spanning-forest priority rule inspired by JSQ-K, where each server prioritizes child queues and only turns to its parent queue when children are empty. The spanning forest property, which follows because the LP solution is a basic feasible solution, is what lets the heuristic route near the target rates without virtual queues.
What would settle it
Run the same June 2001 scenario twice: once with service times drawn from the empirical distribution and once with exponential service times matched to the same means; if UCB-QR's payoff relative to the Oracle drops substantially, or queues become unstable, then the near-99% result depends on the empirical service distribution and the LP's theoretical optimality does not transfer. A second check: compute the optimal LP value on the true June data parameters and simulate the Oracle; if the simulated departures never reach the LP's predicted payoff, the Oracle benchmark itself overstates what is achievable and the 71.4% gap-closing number would need rescaling.
Extended reading notes
Core claim
The central claim is that UCB-QR, once adapted for practice, is a viable live routing policy for skill-based queues: it learns payoff parameters and queueing parameters online and nearly matches the optimal LP routing rates. The authors establish this through a case study on real call-center data, solving the routing-rate LP (1) directly each episode instead of enumerating basic feasible solutions, adding a fictitious rejection server to restore feasibility, and estimating time-varying arrival and service rates from data. In the representative June 2001 scenario, UCB-QR accumulates on average 99.0% of the Oracle payoff and closes 71.4% of the gap between random routing and the Oracle; with the tree heuristic the empirical routing rates approximate the LP targets and waiting times drop to near FCFS-ALIS levels. The paper also claims the algorithm is not computationally heavy, extends to multiple objectives such as server fairness, and is only mildly sensitive to estimation errors.
Load-bearing premise
The whole demonstration rests on the assumption that solving the planned routing-rate optimization with estimated arrival and service rates still yields near-optimal and stable routing even though the real service times are not exponential and the arrivals are not Poisson, which is what the underlying theory assumes.
Editorial extensions
If this is right
- A queueing system can deploy UCB-QR online: per episode it only needs to solve a small linear program, and a full-day simulation runs in about 20 seconds, roughly twice the benchmark policies' run time.
- Waiting time is not an inherent cost of learning-based payoff maximization: with the tree heuristic delays drop to near FCFS-ALIS while payoff loss stays minimal, so practitioners can have both.
- Secondary objectives such as server load fairness can be folded into the same LP objective with a tuning parameter, giving an explicit payoff-versus-fairness trade-off.
- Accurate arrival and service rate data are not critical: replacing empirical estimators with true rates improves the average payoff by only about 0.1%, which supports using online estimators in practice.
- Bursty surges remain a known weakness: UCB-QR-Tree recovers from artificial surges slower than benchmarks, and the paper identifies episode length and estimator smoothing as the levers to fix it.
Reading between the lines
- Beyond the paper: the same LP-plus-UCB template should transfer to data-center or cloud job routing, where payoff is a quality score rather than a success fraction; the paper's near-constant payoff matrix makes its 71.4% gap-closing number conservative, and a payoff matrix with more variance showed larger gains for UCB-QR.
- The tree heuristic's routing rates are shown in Appendix D not to converge exactly to the LP target, so a formal characterization of the approximation error would let practitioners bound the payoff loss before deployment.
- A testable extension: applying Algorithm 3 to the multi-objective optimization problem (11) would require a spanning-forest analogue for convex objectives, which the paper notes is missing; replacing the quadratic fairness penalty with a linear or tree-compatible surrogate could restore compatibility.
- The episode-length results suggest that an event-based update rule, which the paper names as future work, could eliminate the periodic reshuffling delay spikes visible in the small example.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper presents a practical case study of the UCB–Queue Routing (UCB–QR) algorithm on a large real-world call-center dataset. The authors modify the original algorithm to solve the routing-rate LP directly, to handle temporary infeasibility through a fictitious rejection server, and to estimate time-varying arrival and service rates online. They report that UCB–QR achieves on average 99.0% of an Oracle policy's payoff and closes about 71.4% of the gap left by random routing in a June 2001 scenario. They also propose a tree-based routing heuristic (Algorithm 3) that reduces waiting times to levels close to FCFS-ALIS while preserving most of the payoff, extend the objective to include fairness, and study robustness to bursts, estimation errors, and episode length.
Significance. If the results hold, the paper is a valuable practical validation of a learning-based routing policy in a realistic skill-based queueing system, with public code and data, extensive simulations, and honest reporting of limitations. The proposed tree-based routing heuristic and the multi-objective extension are useful contributions. However, the paper's quantitative headline depends on an Oracle benchmark whose validity under the simulated general service-time distributions is not established, and the pseudocode contains two implementation-level issues (an infinite initial UCB value and a rejection-server normalization that can violate capacity constraints) that need to be resolved before the experiments can be considered fully reproducible.
major comments (4)
- [Algorithm 1, line 1 and Eq. (5)] The initialization \hat\theta_{ij}(0)=\infty for all (ij)\in L makes LP (1) unbounded at the first episode: the objective contains \sum \theta_{ij} x_{ij} with \theta_{ij}=\infty, and constraints (1b) force at least one x_{ij}>0 per customer type. A finite LP solver cannot return a maximizer, so the pseudocode as written is not implementable. The manuscript should specify the finite large value used in the released code (and its tuning), or add a separate exploration rule for the first episode. This matters because the initial optimism controls exploration and therefore the payoff and waiting-time results in Section 4.
- [Section 2, after Eq. (2); Algorithm 2] The handling of the fictitious rejection server z is internally inconsistent: after solving LPa, the routing probabilities are p_{ij}=x_{ij}/\sum_{k\in J}x_{ik}, so the mass x_{iz} is renormalized onto real servers and every arriving customer is still routed. The actual load routed to server j is then \lambda_i x_{ij}/(\lambda_i-x_{iz}), which can exceed the capacity constraint (2c). Thus in overload episodes LPa does not provide the claimed robust stability alternative; it can create temporary overloading of real servers. Please either implement actual rejection (e.g., abandonment or an explicit blocked-customer counter) and use p_{ij}=x_{ij}/\lambda_i, or analyze the effect of renormalization on stability. The paper should also report how often LPa is invoked in the experiments.
- [Section 3.1.3; Eq. (1)] The Oracle and UCB–QR both solve LP (1), whose stability constraint and optimality justification are taken from [13] under Poisson arrivals and exponential service times, while the simulation samples service times from the empirical distribution and uses real arrival traces. The paper gives no argument that the LP value remains an upper bound on the long-run average payoff of any stable policy, or that the Oracle's routing rates are achievable, under these general service-time distributions. Since the headline 'closing 71.4% of the optimality gap' is measured against this Oracle, please either add a short proof or standard argument that the capacity constraints yield an upper bound for general service-time systems, or recharacterize the Oracle as a rate-LP benchmark and adjust the optimality-gap language accordingly.
- [Section 4.1] The gap-closure claim 'closing the optimality gap ... by approximately 71.4%' is computed from the statements that Random accumulates on average 96.5% and UCB–QR 99.0% of the Oracle payoff. It is not stated whether these percentages are pooled totals over the entire month or averages of daily ratios. If they are averages of daily ratios, the arithmetic (99.0−96.5)/(100−96.5) is not the correct fraction of the total optimality gap closed; if they are pooled totals, that should be stated. Please also provide a confidence interval or standard error for the 71.4% figure, since the payoff differences are small and the figure is the paper's main quantitative claim.
minor comments (6)
- [Section 3.1.2] The statement that approximating an M(\lambda)/M(\mu)/n queue by an M(\lambda)/M(n\mu)/1 queue gives stationary probabilities that are 'very close for states with n or more customers' is vague and not supported by the cited reference in the way stated; please clarify the precise approximation argument.
- [Figure 1] The caption says the exponential density has parameter 257, but it is not clear whether 257 is the rate or the scale, and whether the histogram is normalized to a density; please make the units explicit.
- [Section 4.4] The experiment with bursty arrivals only runs UCB–QR–Tree, but the conclusion says 'UCB–QR–Tree (and similarly UCB–QR) are not yet well-suited'; the extrapolation to UCB–QR is not tested and should be phrased as an expectation or tested directly.
- [Section 4.5] The claim that granting true arrival or service rates improves cumulative payoff only 'in the order of 0.1%' is reported without a table or confidence intervals; please give the actual numbers and variability.
- [Appendix D and Section 4.2] Appendix D shows that Algorithm 3's empirical routing rates deviate from the target x by up to roughly 10% (e.g., x_{11}=1 versus 0.863 and x_{22}=3 versus 2.649), yet Section 4.2 calls these 'minor deviations' without quantifying them; please connect the appendix numbers to the claim about payoff loss.
- [References] Reference [13] is cited as an arXiv preprint; if a peer-reviewed version exists, it should be cited in its published form.
Circularity Check
No construction-level circularity: the 71.4% gap-closure is an empirical comparison against an Oracle that shares the same LP but is given true parameters; the only self-citation is the background theory [13], which the experiments do not reduce to.
full rationale
The quantitative headline is not built from a fitted quantity. UCB-QR (Algorithm 1) solves LP (1) with online estimates, while the Oracle is defined as Algorithm 1 with the true theta, lambda, and mu; the reported 99.0% / 96.5% / 71.4% figures are ratios of simulated payoffs, so the "gap closure" is a measurement against a benchmark, not an identity forced by construction. Payoff parameters are defined from empirical success ratios and then learned from Bernoulli samples in the simulator; no parameter is fitted to the target statistic and then reported as a prediction. The only self-citation is [13], which supplies the LP and the regret theory for UCB-QR. This is normal background; the paper's claims of practical effectiveness rest on comparisons with external benchmarks (Random, FCFS-ALIS, Greedy, the theta-mu rule, and the raw data policy) and on waiting-time, load, and runtime observations. In-scope limitations weaken the paper but are not circular: Section 3.1.3 admits service times are probably non-exponential while the LP optimality and stability constraint (1c) come from an exponential-service theory; Section 4.4 admits UCB-QR variants recover slowly from bursts; Appendix D shows Algorithm 3 does not exactly achieve its target routing rates. These are correctness or scope caveats, not derivations that reduce to their own inputs. Score 1 reflects only the presence of the authors' own prior theoretical work as background.
Assumptions & free parameters
free parameters (7)
- Episode length h =
2 minutes (main experiments); 1, 5, 10, 20 in sensitivity analysis
- Penalty p for rejection server =
10^3
- Stability margin epsilon =
10^-6
- Holt smoothing alpha =
0.5
- Holt smoothing beta =
0.2
- Fairness weight gamma =
varied 0, 0.01, 0.1, 1
- Initial service rate estimator value =
10^-3
assumptions (5)
- domain assumption Solving LP (1) with true rates and payoffs identifies the optimal long-run routing policy for the simulated skill-based queue.
- domain assumption The success probabilities theta_ij are fixed, policy-independent attributes of a customer-type/server pair.
- domain assumption Mean service rates are enough to guarantee queue stability via constraint (1c).
- domain assumption Algorithm 3 can realize routing rates close enough to the LP target x to preserve payoff while reducing delay.
- domain assumption The LP solver returns a basic feasible solution so that Algorithm 3's spanning forest construction is valid.
invented entities (1)
-
Fictitious rejection server z
Cite this review
Pith. "Pith review of Demonstration of effective UCB-based routing in skill-based queues on real-world data." pith.science (2026). https://pith.science/paper/A2DLZQIQ
@misc{pith2026250620543,
author = {Pith},
title = {Pith review of: Demonstration of effective UCB-based routing in skill-based queues on real-world data},
year = {2026},
howpublished = {\url{https://pith.science/paper/A2DLZQIQ}},
note = {Machine review of arXiv:2506.20543}
}
read the original abstract
This paper is about optimally controlling skill-based queueing systems such as data centers, cloud computing networks, and service systems. By means of a case study using a real-world data set, we investigate the practical implementation of a recently developed reinforcement learning algorithm for optimal customer routing. Our experiments show that the algorithm efficiently learns and adapts to changing environments and outperforms static benchmark policies, indicating its potential for live implementation. We also augment the real-world applicability of this algorithm by introducing a new heuristic routing rule to reduce delays. Moreover, we show that the algorithm can optimize for multiple objectives: next to payoff maximization, secondary objectives such as server load fairness and customer waiting time reduction can be incorporated. Tuning parameters are used for balancing inherent performance trade--offs. Lastly, we investigate the sensitivity to estimation errors and parameter tuning, providing valuable insights for implementing adaptive routing algorithms in complex real-world queueing systems.
Figures
Figures from the paper (16 more)
Reference graph
Works this paper leans on
-
[13]
Learning payoffs while routing in skill-based queues
Sanne van Kempen, Jaron Sanders, Fiona Sloothaak, and Maarten G Wolf. Learning payoffs while routing in skill-based queues.ArXiv: 2412.10168, 2024
work page Pith review arXiv 2024
-
[1]
Jinsheng Chen, Jing Dong, and Pengyi Shi. A survey on skill-based routing with applications to service operations management.Queueing Systems, 96(1-2):53–82, 2020
work page 2020
-
[2]
Ivo Adan and Gideon Weiss. Exact FCFS matching rates for two infinite multitype sequences.Operations Research, 60(2):475–489, 2012
work page 2012
-
[3]
Ivo Adan and Gideon Weiss. A skill-based parallel service system under FCFS-ALIS — steady state, overloads, and abandonments.Stochastic Systems, 4(1):250–299, 2014
work page 2014
-
[4]
Cambridge University Press, Cambridge, 2021
Gideon Weiss.Scheduling and Control of Queueing Networks. Cambridge University Press, Cambridge, 2021
work page 2021
-
[5]
Wayne E. Smith. Various optimizers for single-stage production.Naval Research Logistics Quarterly, 3:59–66, 1956
work page 1956
-
[6]
Yueyang Zhong, John R. Birge, and Amy Ward. Learning the scheduling policy in time-varying multiclass many server queues with abandonment.SSRN Electronic Journal, (2012), 2022
work page 2012
-
[7]
Subhashini Krishnasamy, Ari Arapostathis, Ramesh Johari, and Sanjay Shakkottai. On learning the cµ rule in single and parallel server networks.2018 56th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2018, pages 153–154, 2018
work page 2018
Show all 27 references
-
[8]
Adaptive matching for expert systems with uncertain task types.Operations Research, 68(5):1403–1424, 2020
Virag Shah, Lennart Gulikers, Laurent Massouli´ e, and Milan Vojnovi´ c. Adaptive matching for expert systems with uncertain task types.Operations Research, 68(5):1403–1424, 2020
2020
-
[9]
J. G. Dai and Mark Gluzman. Queueing Network Controls via Deep Reinforcement Learning.Stochastic Systems, 12(1):30–67, 2022
2022
-
[10]
Reinforcement Learning for Datacenter Congestion Control.SIGMETRICS Performance Evaluation Review, 49(2):43–46, 2022
Chen Tessler, Yuval Shpigelman, Gal Dalal, Amit Mandelbaum, Doron Haritan Kazakov, Benjamin Fuhrer, Gal Chechik, and Shie Mannor. Reinforcement Learning for Datacenter Congestion Control.SIGMETRICS Performance Evaluation Review, 49(2):43–46, 2022
2022
-
[11]
Springer International Publishing, 2020
Sisheng Liang, Zhou Yang, Fang Jin, and Yong Chen.Data Centers Job Scheduling with Deep Reinforcement Learning, volume 12085 LNAI. Springer International Publishing, 2020
2020
-
[12]
C´ eline Comte, Matthieu Jonckheere, Jaron Sanders, and Albert Senen-Cerda. Score-Aware Policy-Gradient Methods and Performance Guarantees using Local Lyapunov Conditions: Applications to Product-Form Stochastic Networks and Queueing Systems.ArXiv: 2312.02804, 2023
2023
-
[14]
Finite-time analysis of the multiarmed bandit problem
Peter Auer, Nicol` o Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2-3):235–256, 2002
2002
-
[15]
Cambridge University Press, Cambridge, 2020
Tor Lattimore and Csaba Szepesv´ ari.Bandit Algorithms. Cambridge University Press, Cambridge, 2020
2020
-
[16]
Joint learning and control in stochastic queueing networks with unknown utilities.Proceedings of the ACM on Measurement and Analysis of Computing Systems, 6(3), 2022
Xinzhe Fu and Eytan Modiano. Joint learning and control in stochastic queueing networks with unknown utilities.Proceedings of the ACM on Measurement and Analysis of Computing Systems, 6(3), 2022
2022
-
[17]
Tsitsiklis.Introduction to Linear Optimization
Dimitris Bertsimas and John N. Tsitsiklis.Introduction to Linear Optimization. Athena scientific, Belmont, MA, 1997
1997
-
[18]
Cohen and Frank P
Joel E. Cohen and Frank P. Kelly. Reversibility and Stochastic Networks, 1981
1981
-
[19]
OTexts, Mel- bourne, 2021
Robin John Hyndman and George Athanasopoulos.Forecasting: Principles and Practice. OTexts, Mel- bourne, 2021
2021
-
[20]
Statistical and economic evaluation of time series models for forecasting arrivals at call centers.Empirical Economics, 57(3):923–955, 2019
Andrea Bastianin, Marzio Galeotti, and Matteo Manera. Statistical and economic evaluation of time series models for forecasting arrivals at call centers.Empirical Economics, 57(3):923–955, 2019
2019
-
[21]
Goldberg, Y
Y. Goldberg, Y. Ritov, and A. Mandelbaum. Predicting the continuation of a function with applications to call center data.Journal of Statistical Planning and Inference, 147:53–65, 2014
2014
-
[22]
Distributional Regression for Data Analysis.Annual Review of Statistics and its Application, 11(1):321–346, 2024
Nadja Klein. Distributional Regression for Data Analysis.Annual Review of Statistics and its Application, 11(1):321–346, 2024. 18
2024
-
[23]
A c/µ-Rule for Job Assignment in Heterogeneous Group-Server Queues.Production and Operations Management, 31(3):1191–1215, 2022
Li Xia, Zhe George Zhang, and Quan Lin Li. A c/µ-Rule for Job Assignment in Heterogeneous Group-Server Queues.Production and Operations Management, 31(3):1191–1215, 2022
2022
-
[24]
The Generalized c/µRule for Queues with Heterogeneous Server Pools.Operations Research, 72(6), 2023
Zhenghua Long, Hailun Zhang, Jiheng Zhang, and Zhe George Zhang. The Generalized c/µRule for Queues with Heterogeneous Server Pools.Operations Research, 72(6), 2023
2023
-
[25]
Ephremides, P
A. Ephremides, P. Varaiya, and J. Walrand. A Simple Dynamic Routing Problem.IEEE Transactions on Automatic Control, 25(4):690–693, 1980
1980
-
[26]
MOSEK Optimizer API for Python
MOSEK ApS. MOSEK Optimizer API for Python. (January), 2023
2023
-
[27]
outcome” encodes the reason why the call ended, such as abandonment or transfer, and “party answered
C. G. Cassandras and S. Lafortune.Introduction to discrete event systems. Springer, Boston, MA, 2008. 19 A Data and simulation description Figure 18: Excerpt of the call log table of the data set. Here, “outcome” encodes the reason why the call ended, such as abandonment or tr...
2008
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.