Applied Probability Society Student Paper Competition: Abstracts of 2020 Finalists

The 2020 prize winners are as follows:

First Prize

Asymptotic Optimality of the Binomial-Exhaustive Policy for Polling Systems with Large Switchover Times

Yue Hu, Columbia University

Finalists (in alphabetical order according to student’s last name):

Smooth Contextual Bandits: Bridging the Parametric and Nondifferentiable Regret Regimes

Yichun Hu and Xiaojie Mao, Cornell University

Sparsity-Agnostic Lasso Bandit

Min-hwan Oh, Columbia University

Correlated Randomly Growing Graphs

Anirudh Sridhar, Princeton University

Asymptotic Optimality of the Binomial-Exhaustive Policy for Polling Systems with Large Switchover Times

Yue Hu

Columbia University, [email protected]

Advisors: Jing Dong, Columbia University;

Ohad Perry, Northwestern University

We study an optimal-control problem of polling systems with large switchover times when a holding cost is incurred on the queues. In particular, we consider a stochastic network with a single server that switches between several buffers (queues) according to a prespecified order, assuming that the switchover times between the queues are large relative to the processing times of individual jobs. Due to its complexity, computing an optimal control for such a system is prohibitive, so we instead search for an asymptotically optimal control. To this end, we first solve an optimal control problem for a deterministic relaxation (namely, for a fluid model), that is represented as a hybrid dynamical system. We then translate the solution to that fluid problem to a binomial-exhaustive policy for the underlying stochastic system, and prove that this policy is asymptotically optimal in a large-switchover-time scaling regime, provided a certain uniform integrability (UI) condition holds. Finally, we demonstrate that the aforementioned UI condition holds in the following cases: (i) the holding cost has (at most) linear growth, and all service times have finite second moments; (ii) the holding cost grows at most at a polynomial rate (of any degree), and the service-time distributions possess finite moment generating functions. Our proofs that the UI condition holds in these two cases may be of independent interest.

Smooth Contextual Bandits: Bridging the Parametric and Nondifferentiable Regret Regimes

Yichun Hu

Cornell University, [email protected]

Xiaojie Mao

Cornell University, [email protected]

Advisor: Nathan Kallus, Cornell University

We study a nonparametric contextual bandit problem where the expected reward functions belong to a Hölder class with smoothness parameter $\beta$. We show how this interpolates between two extremes that were previously studied in isolation: nondifferentiable bandits ($\beta \le 1$), where rate-optimal regret is achieved by running separate noncontextual bandits in different context regions, and parametric-response bandits (satisfying $\beta =\infty$), where rate-optimal regret can be achieved with minimal or no exploration due to infinite extrapolatability. We develop a novel algorithm that carefully adjusts to all smoothness settings and we prove its regret is rate-optimal by establishing matching upper and lower bounds, recovering the existing results at the two extremes. In this sense, our work bridges the gap between the existing literature on parametric and nondifferentiable contextual bandit problems and between bandit algorithms that exclusively use global or local information, shedding light on the crucial interplay of complexity and regret in contextual bandits.

Sparsity-Agnostic Lasso Bandit

Min-hwan Oh

Columbia University, [email protected]

Advisors: Garud Iyengar, Columbia University;

Assaf Zeevi, Columbia University

We consider a stochastic contextual bandit problem where the dimension $d$ of the feature vectors is potentially large, however, only a sparse subset of features of cardinality $s_0\ll d$ affect the reward function. Essentially all existing algorithms for sparse bandits require a priori knowledge of the value of the sparsity index $s_0$. This knowledge is almost never available in practice, and misspecification of this parameter can lead to severe deterioration in the performance of existing methods. The main contribution of this paper is to propose an algorithm that does not require prior knowledge of the sparsity parameter $s_0$ and establish tight regret bounds under mild conditions. We comprehensively evaluate our proposed algorithm numerically and show that it consistently outperforms existing methods, even when the correct sparsity parameter is revealed to these methods but is kept hidden from our algorithm.

Correlated Randomly Growing Graphs

Anirudh Sridhar

Princeton University, [email protected]

Advisor: Miklós K. Rácz, Princeton University

We introduce a new model of correlated randomly growing graphs and study the fundamental questions of detecting correlation and estimating aspects of the correlated structure. The model is simple and starts with any model of randomly growing graphs, such as uniform attachment (UA) or preferential attachment (PA). Given such a model, a pair of graphs $(G1,G2)$ is grown in two stages: until time $t_{\mathrm{\star }}$ they are grown together (i.e., $G_1=G_2$), after which they grow independently according to the underlying growth model.

We show that whenever the seed graph has an influence in the underlying graph growth model—this has been shown for PA and UA trees and is conjectured to hold broadly—then correlation can be detected in this model, even if the graphs are grown together for just a single time step. We also give a general sufficient condition (which holds for PA and UA trees) under which detection is possible with probability going to 1 as $t_{\mathrm{\star }}\to 1$. Finally, we show for PA and UA trees that the amount of correlation, measured by $t_{\mathrm{\star }}$, can be estimated with vanishing relative error as $t_{\mathrm{\star }}\to \infty$.