2025/12/12 by Mevan Wijewardena, Wijewardena, Mevan, Kamiar Asgari +3
Business, Management and Accounting · Computer Science · Engineering · #60K25 #60K30 #68M20 #90B22 #Advanced Queuing Theory Analysis #Advanced Wireless Network Optimization #Age of Information Optimization #FOS: Computer and information sciences #FOS: Electrical engineering #G.3 #Information Theory (cs.IT) #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2512.12016
openalex publication_date 2025/12/12 · openalex created_date 2025/12/17 · openalex updated_date 2026/07/28
This paper considers the problem of obtaining bounded time-average expected queue sizes in a single-queue system with a partial-feedback structure. Time is slotted; in slot t the transmitter chooses a rate V(t) from a continuous interval. Transmission succeeds if and only if V(t)≤ C(t), where channel capacities \C(t)\ and arrivals are i.i.d. draws from fixed but unknown distributions. The transmitter observes only binary acknowledgments (ACK/NACK) indicating success or failure. Let ε>0 denote a sufficiently small lower bound on the slack between the arrival rate and the capacity region. We propose a phased algorithm that progressively refines a discretization of the uncountable infinite rate space and, without knowledge of ε, achieves a O (log3.5(1/ε)/ε3) time-average expected queue size uniformly over the horizon. We also prove a converse result showing that for any rate-selection algorithm, regardless of whether ε is known, there exists an environment in which the worst-case time-average expected queue size is Ω(1/ε2). Thus, while a gap remains in the setting without knowledge of ε, we show that if ε is known, a simple single-stage UCB type policy with a fixed discretization of the rate space achieves O (log(1/ε)/ε2), matching the converse up to logarithmic factors.