Direct Sample-Average Learning for Queueing Control: Gradient-Free Top-K Coarse-to-Fine Optimization
Abstract
We study steady-state queueing control when decisions must be learned from a single persistent operating trajectory: only the implemented action produces data, and the queue is not reset when the action changes. Fixed-event-count cycles yield a direct ratio-of-totals sample-average approximation (SAA) of each action's steady-state cost rate. A Top-K coarse-to-fine search ranks these estimates, retains several promising refinement paths, and concentrates later operation on finer candidate sets, without requiring gradients, convexity, or differentiability. We decompose direct-SAA error into accumulated conditional transient bias and martingale fluctuation. For regenerative queues, a bias-function representation reduces transient effects within contiguous action blocks to boundary terms. Finite-sample stagewise bounds then link estimation accuracy to master-grid identification through guardian retention, and the required queueing and sampling conditions are verified for a persistent-workload M/M/1 implementation. At a common active set, Top-K has a weakly larger guardian margin than Top-1, and an exact-objective example shows Top-1 can discard the optimal refinement branch. Numerical experiments delineate scope rather than universal dominance: Top-K improves terminal identification in the reported LiQUAR and mixed staffing comparisons, while LiQUAR can have lower cumulative learning cost, and GOLiQ is markedly stronger on a smooth benchmark with reliable queueing sensitivities. Direct ranking is therefore best viewed as a complementary method when model-specific gradients are unavailable, inconvenient, or poorly matched to the decision space.
Related
- An Adaptive Projected-Gradient Algorithm for Sample-Average Approximations of Stochastic Multi-Objective Optimization
- State-Dependent Phase-Type Queueing Networks for Urban Traffic Signal Control
- Average Energy Dissipation Rates of Implicit-Explicit Runge-Kutta Methods for Gradient Flow Problems
- A Particle-Swarm-Assisted Gradient Meta-Learning Algorithm for Joint Transmit Precoding and STAR-RIS Coefficient Optimization
- Exact Average Consensus under Noisy Communication Links: A Decentralized Gradient Perspective
BibTeX
@misc{yazdi2026direct,
title = {{Direct Sample-Average Learning for Queueing Control: Gradient-Free Top-$K$ Coarse-to-Fine Optimization}},
author = {Mehrdad Nozohour Yazdi and Yiqiang Q. Zhao},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.26653},
eprint = {2610.26653},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.26653},
}
RIS
TY - UNPB
TI - Direct Sample-Average Learning for Queueing Control: Gradient-Free Top-K Coarse-to-Fine Optimization
AU - Mehrdad Nozohour Yazdi
AU - Yiqiang Q. Zhao
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.26653
UR - https://arxiv.org/abs/2610.26653
AB - We study steady-state queueing control when decisions must be learned from a single persistent operating trajectory: only the implemented action produces data, and the queue is not reset when the action changes. Fixed-event-count cycles yield a direct ratio-of-totals sample-average approximation (SAA) of each action's steady-state cost rate. A Top-K coarse-to-fine search ranks these estimates, retains several promising refinement paths, and concentrates later operation on finer candidate sets, without requiring gradients, convexity, or differentiability. We decompose direct-SAA error into accumulated conditional transient bias and martingale fluctuation. For regenerative queues, a bias-function representation reduces transient effects within contiguous action blocks to boundary terms. Finite-sample stagewise bounds then link estimation accuracy to master-grid identification through guardian retention, and the required queueing and sampling conditions are verified for a persistent-workload M/M/1 implementation. At a common active set, Top-K has a weakly larger guardian margin than Top-1, and an exact-objective example shows Top-1 can discard the optimal refinement branch. Numerical experiments delineate scope rather than universal dominance: Top-K improves terminal identification in the reported LiQUAR and mixed staffing comparisons, while LiQUAR can have lower cumulative learning cost, and GOLiQ is markedly stronger on a smooth benchmark with reliable queueing sensitivities. Direct ranking is therefore best viewed as a complementary method when model-specific gradients are unavailable, inconvenient, or poorly matched to the decision space.
ER -