Skip to content

Speakers and abstracts DDQC III

Jose Blanchet (Stanford University)

Understanding Strength in Polymers: A Stochastic Networks Approach
We report results based on joint collaborations with a group of material scientists, including the groups lead by Prof. Wei Cai (Stanford) and Prof. Zhigang Suo (Harvard). The results are motivated (as we shall discuss) by fundamental questions that (surprisingly!) are still not very well understood in polymer science. Understanding what makes a polymer strong has fundamental implications in real life applications (like how to extend the lifetime of vehicle tires and other polymers, which can be a significant source of pollution). Material scientists use data-driven evidence (based on experiments) and computational methods (based on molecular dynamic simulations) to study these questions. While these methods are powerful, they can be expensive, time consuming, and sometimes difficult to interpret. We propose a model based on a network of branching random walks which is validated by coarse-grained molecular dynamic simulations. This model is then used to predict the critical strain at which a polymer network will experience significant deformation. The model helps explain experimental phenomena at the core of questions about the strength of polymers. The results enhance predictions based on other models that are widely used in material science. Our analysis is based on large deviations theory and extends recent results about first passage times for branching random walks.
This is joint work with Wei Cai, Shaswat Mohanty, Zhenyuan Zhang and sponsored by the DoD through a MURI grant.

Arnoud den Boer (University of Amsterdam)

Can price algorithms learn to form a cartel?
Can price algorithms learn to form a cartel instead of compete against each other, potentially leading to higher consumer prices and lower social welfare? The question is controversial among economists and competition policy regulators. One the one hand, concerns have been expressed that self-learning price algorithms do not only make it easier to form price cartels, but also that this can be achieved within the boundaries of current antitrust legislation – raising the question whether the existing competition law needs to be adjusted to mitigate undesired algorithmic collusion. On the other hand, a number of economists believe that algorithms learning to collude is science fiction, except by using forms of signaling or communication that are already illegal, and argue that there is no need to change antitrust laws. Motivated by this discussion, I will present work that shows that under some market conditions, price algorithms can learn to collude. 
(Based on joint work with Janusz Meylahn, Thomas Loots, Maarten Pieter Schinkel, Ali Aouad.)

Richard Combes (Laboratory of Signals and Systems, CentraleSupélec)

An extension of McDiarmid’s inequality
We generalize McDiarmid’s inequality for functions with bounded differences on a high probability set, using an extension argument. Those functions concentrate around their conditional expectations. We illustrate the usefulness of this generalized inequality on a few examples. We further extend the results to concentration in general metric spaces.

Jing Dong (Columbia Business School)

Differentiable Discrete Event Simulation for Queuing Network Control
Queuing network control is a ubiquitous task for managing congestion in job-processing systems, such as service systems, communication networks, manufacturing processes, etc. Recently, there has been a growing interest in applying reinforcement learning (RL) techniques to learn good control policies for general queueing networks. However, queuing network control poses unique challenges when applying standard RL methods. These include (1) high stochasticity, (2) large state and action spaces, and (3) lack of stability guarantees. In this work, we propose a scalable framework for policy optimization in multi-class queuing networks based on differentiable simulation, which tackles the challenges listed above and substantially improves the sample efficiency over existing approaches. This framework is based on a novel approach for computing pathwise gradients for discrete event dynamical systems with auto-differentiation, and we address the non-differentiability of the dynamics through carefully designed smoothing. Our proposed method is easy to train (e.g., not sensitivity to hyper-parameter tuning), highly scalable (e.g., can solve very large-scale problems), and can handle more realistic instances outside the scope of existing RL methods, including systems operating in a non-stationary environment with non-exponential inputs (i.e., interarrival and service times).
This is joint work with Ethan Che and Hongseok Namkoong.

Harsha Honnappa (Purdue University)

Rouba Ibrahim (University College London)

Communication in Social Services Operations
We study the effectiveness of information design as a managerial lever to mitigate the overuse of critical resources in congestion-prone social service systems. Leveraging the service provider’s informational advantage about relevant aspects of the system, effective communication requires the sharing of carefully curated information to persuade low-need customers to forgo service for the benefit of customers with higher service needs. To study whether effective communication can arise in equilibrium,  we design controlled laboratory experiments to test the predictions of a queueing-game theoretic model that endogenizes the implementation of information-sharing policies. Our main result is that communication increases social welfare even when the service provider lacks the ability to formally commit to their information policy (as usually is the case in practical settings), i.e., under conditions where standard theory predicts that communication fails because it lacks credibility and thus fails to affect customer behaviour.
(Joint work with Arturo Estrada Rodriguez and Mirko Kremer.)

Bart van Parys, MIT Sloan School of Management

Alexandre Proutiere (KTH Royal Institute of Technology)

Sanjay Shakkottai (University of Texas at Austin)

On solving inverse problems in computer vision using latent diffusion based generative models
Diffusion models have emerged as a powerful new approach to generative modeling. In this talk, we present the first framework that uses pre-trained latent diffusion models to solve linear inverse problems such as image denoising, inpainting, and super-resolution. Previously proposed algorithms (such as DPS and DDRM) only apply to pixel-space diffusion models. We theoretically analyze our algorithm showing provable sample recovery in a linear model setting. The algorithmic insight obtained from our analysis extends to more general settings often considered in practice. Experimentally, we outperform previously proposed posterior sampling algorithms in a wide variety of problems including random inpainting, block inpainting, denoising, deblurring, destriping, and super-resolution. Next, we present an efficient second-order approximation using Tweedie’s formula to mitigate the bias incurred in the widely used first-order samplers. With this method, we devise a surrogate loss function to refine the reverse process at every diffusion step to address inverse problems and perform high-fidelity text-guided image editing.
Based on joint work with Litu Rout, Negin Raoof, Giannis Daras, Constantine Caramanis, Alex Dimakis, Yujia Chen, Abhishek Kumar, and Wen-Sheng Chu.

Pengyi Shi (Purdue University)

Ran Snitkovsky (Tel Aviv University)

Learning Algorithms for Queues with Strategic Customers
This talk will discuss novel iterative algorithms for computing, or learning, Nash equilibria and optimal regulation in queueing games. The purpose in this line of research is to suggest robust, easy-to-implement algorithms, with theoretical guarantees, that learn customer equilibrium behavior and related quantities based on adaptive simulation of the underlying queueing game. Such algorithms potentially provide a powerful tool to approximate equilibrium strategies and optimal regulation in a broad range of strategic queueing models, in which classical queueing-analytic methods are impractical. In the talk I will introduce the general framework, present several established results, and suggest some promising paths for future research.

R Srikant (University of Illinois at Urbana-Champaign)

Learning and Control in Countable State Spaces
We will consider policy optimization methods in reinforcement learning where the state space is countably infinite. The motivation arises from control problems in communication networks, matching markets, and other queueing systems. We consider an  algorithm called Natural Policy Gradient (NPG), which is a popular algorithm for finite state spaces, and show three results in the context of countable state spaces: (i) in the case where perfect policy evaluation is possible, we show that standard NPG converges with a small modification; (ii) if the error is policy evaluation is within a factor of the true value function, we show that one can obtain bounds on the performance of the NPG algorithms; and (iii) we will discuss the ability of neural network-based function approximations to satisfy the condition in (ii) above.

Neil Walton (University of Durham)

Understanding Waiting List Pressures
NHS waiting lists currently sit at record lengths due to a combination of the immediate impact of the pandemic and, as well as, long-run pressures requiring investment on NHS resources. These factors have left managers and clinicians with increasingly complex decisions when scheduling elective operations. It is imperative that managers understand the basic dynamics, tradeoffs, and pressures when managing waiting lists.
Queueing theory is a key part of operational research, extensively used throughout manufacturing, retail, information technology and other sectors. This article provides an exposition of the theory of queues within the context of the current NHS backlog. With this information a manager will be able understand the demand, queue size, waiting times, capacity requirements and trade-offs for different waiting lists. We describe the metrics and a reporting system developed to understand waiting list pressures in a large NHS trust. Our aim is to enable managers to better understand their waiting lists, to achieve targets and improve health outcomes.

Mengdi Wang (Princeton University)

Weina Wang (Carnegie Mellon University)

Recent Advances in Average-Reward Restless Bandits
We consider the infinite-horizon, average reward restless bandit problem. A central challenge is designing computationally efficient policies that achieve a diminishing optimality gap as the number of arms, N, grows large. Existing policies, including the renowned Whittle index policy, all rely on a uniform global attractor property (UGAP) assumption to achieve asymptotic optimality, which is a complex and difficult-to-verify assumption. In this talk, I will present new, sampling-based policy designs for restless bandits. One of our proposed policies breaks the long-standing UGAP assumption for the first time, and the subsequent policies eliminate the need for the UGAP assumption to achieve asymptotic optimality. Our techniques offer new insights into guaranteeing convergence (avoiding undesirable attractors or cycles) in large stochastic systems.
This talk is based on joint work with Yige Hong (CMU), Qiaomin Xie (UW–Madison), and Yudong Chen (UW–Madison).

Zicheng Wang (The Chinese University of Hong Kong, Shenzhen)

Xiaowei Zhang (Hong Kong University of Science and Technology)

Staffing Under Taylor’s Law
Staffing rules serve as an essential management tool in service industries to attain target service levels. Traditionally, the square-root safety rule, based on the Poisson arrival assumption, has been commonly used. However, empirical findings suggest that arrival processes often exhibit an `over-dispersion’ phenomenon, in which the variance of the arrival exceeds the mean. In this paper, we develop a new doubly stochastic Poisson process model to capture a significant dispersion scaling law, known as Taylor’s law, showing that the variance is a power function of the mean. We further examine how over-dispersion affects staffing, providing a closed-form staffing formula to ensure a desired service level. Interestingly, the additional staffing level beyond the nominal load is a power function of the nominal load, with the power exponent lying between 1/2 (the square-root safety rule) and 1 (the linear safety rule), depending on the degree of over-dispersion. Simulation studies and a large-scale call center case study indicate that our staffing rule outperforms classical alternatives.