ROBUST BOUNDS AND OPTIMIZATION AT THE LARGE DEVIATIONS SCALE FOR QUEUEING MODELS VIA RENYI DIVERGENCE

• 成果类型: Article
• 署名作者: Atar, Rami; Budhiraja, Amarjit; Dupuis, Paul; Wu, Ruoyu
• 署名单位: Technion Israel Institute of Technology; University of North Carolina; University of North Carolina Chapel Hill; Brown University; Iowa State University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/20-AAP1613
• 发表日期: 2021
• 页码: 1061-1099
• 关键词: sensitivity-analysis; relative entropy; fluid limits; server; networks; systems; queues

摘要

This paper develops tools to obtain robust probabilistic estimates for queueing models at the large deviations (LD) scale. These tools are based on the recently introduced robust Renyi bounds, which provide LD estimates (and more generally risk-sensitive (RS) cost estimates) that hold uniformly over an uncertainty class of models, provided that the class is defined in terms of Renyi divergence with respect to a reference model and that estimates are available for the reference model. One very attractive quality of the approach is that the class to which the estimates apply may consist of hard models, such as highly non-Markovian models and ones for which the LD principle is not available. Our treatment provides exact expressions as well as bounds on the Renyi divergence rate on families of marked point processes, including as a special case renewal processes. Another contribution is a general result that translates robust RS control problems, where robustness is formulated via Renyi divergence, to finite dimensional convex optimization problems, when the control set is a finite dimensional convex set. The implications to queueing are vast, as they apply in great generality. This is demonstrated on two non-Markovian queueing models. One is the multiclass single-server queue considered as a RS control problem, with scheduling as the control process and exponential weighted queue length as cost. The second is the many-server queue with reneging, with the probability of atypically large reneging count as performance criterion. As far as LD analysis is concerned, no robust estimates or non-Markovian treatment were previously available for either of these models.