INFORMS 2021 Program Book

INFORMS Anaheim 2021

SC34

3 - Multiple Objectives in Online Problems Alberto Vera, Amazon, Seattle, WA, 10016, United States We consider an online problem where resources and customers arrive over time and we must allocate resources to customers. The traditional objective is maximizing reward, given by the customers’ preferences over products. On the other hand, it is also interesting to consider the minimization of holding cost. We present an algorithm that, when correctly tuned, achieves good performance on both objectives simultaneously. SC33 CC Room 209A In Person: Experimental Design in Marketplaces General Session Chair: Hannah Li, Stanford University, Palo Alto, CA, 94306-3949, United States Chair: Yonatan Gur, Stanford University, Stanford, CA, 94305-7216, United States 1 - Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability Yunzong Xu, Massachusetts Institute of Technology, Cambridge, MA, United States, David Simchi-Levi We consider the general (stochastic) contextual bandit problem under the realizability assumption, i.e., the expected reward, as a function of contexts and actions, belongs to a general function class F. We design a fast and simple algorithm that achieves the statistically optimal regret with only O(log T) calls to an offline regression oracle across all T rounds. Our results provide the first universal and optimal reduction from contextual bandits to offline regression, solving an important open problem in the contextual bandit literature. A direct consequence of our results is that any advances in offline regression immediately translate to contextual bandits, statistically and computationally. This leads to faster algorithms and improved regret guarantees for broader classes of contextual bandit problems. 2 - Experimental Design in Two-sided Platforms Hannah Li, Stanford University, Stanford, CA, 94306-3949, United States, Ramesh Johari, Inessa Liskovich, Gabriel Weintraub, Geng Zhao Two-sided marketplace platforms often run experiments to test the effect of an intervention before launching it platform-wide. It is well known that estimates of the treatment effect obtained in these experiments can be biased, due to interference arising from marketplace competition. We develop market models to capture such dynamics and use the model to investigate the effect of competition on the bias and variance of different designs and estimators. First, we show that the bias of commonly used estimators (in demand-side and supply-side randomized designs) depends on market balance. Second, we introduce a novel class of experimental designs based on two-sided randomization (TSR) and propose estimators with lower bias across wide ranges of market balance. Finally, we study how platforms can minimize both bias and variance through their choices in experiment designs. SC34 CC Room 209B In Person: Data Analytics and Simulation General Session Chair: Ankit Shah, University of South Florida, Tampa, FL, 33620, United States 1 - A Simulation-based Movement Intelligence Model for Building Threat Intelligence Jalal Ghadermazi, University of South Florida, Tampa, FL, United States, Ankit Shah Recently, advancements in the development of Intelligence, Surveillance, and Reconnaissance systems have seen a significant increase. The bottleneck in this process is the cognitive overload on the analysts to find patterns and connections to identify suspicious activities. There exists a critical need to develop a decision- support methodology that can assist the analysts in building this threat intelligence. In this study, first, we develop a discrete-event simulation model for the generation of the movement intelligence (MOVINT) data and social intelligence (SOCINT) data. Next, we propose a machine learning-based methodology to build threat intelligence from the collected data. In this talk, we will demonstrate the effectiveness of our approach in the detection of threat signals using the MOVINT and SOCINT data.

SC31 CC Room 208A

In Person: Analysis of Sensor Networks with High- dimensional Data for Data-driven Decision Raking General Session Chair: Ana Maria Estrada-Gomez, Georgia Institute of Technology, Atlanta, GA, 30318, United States 1 - Adaptive Partially-observed Sequential Change Point Detection for Covid-19 Hotspots Detection Jiuyun Hu, Arizona State University, Tempe, AZ, United States, Hao Yan The authors derive an algorithm to detect the hotspots in Covid-19 case. The challenge is the limited resources and how to distribute next day’s tests based on previous data. The algorithm uses Bayesian weighted update to get the posterior distribution of test statistics, then use Upper Confidence Bounds (UCB) to get the optimal distribution of next day, and finally use CUSUM statistics to detect the hotspots. The authors also compare the algorithm to the benchmark of evenly distributed tests and distribute all tests once a county. In Washington State example, the hotspot detected is Yakima County. 2 - Online Monitoring of Dynamic Spectral Functional Graphical Models Ana M. Estrada Gomez, Georgia Institute of Technology, Atlanta, GA, 30318, United States, Kamran Paynabar Many important problems can be modeled as a system of interconnected entities producing time-dependent streaming data. In these problems, it is critical to learn the complex cross-correlation structure between the system’s entities and to monitor for changes in the structure due to system evolution. In this paper, we propose an online structural change-point detection methodology. We exploit the spectral information contained in the data to learn sparse functional probabilistic graphical models over time. We enforce the similarity of the graphs to detect structural changes in the system. An efficient method based on ADMM is proposed for online optimization and change-point detection. The effectiveness of the proposed methodology is demonstrated through a simulation study and a real case study using neurological data. SC32 CC Room 208B In Person: Coupling Techniques for Online Decision-Making General Session Chair: Siddhartha Banerjee, Cornell University, Ithaca, NY, 14853- 3801, United States 1 - Sequential Fair Allocation: The Envy-Efficiency Uncertainty Principle Sean Sinclair, Cornell University, Ithaca, NY, 14853, United States We consider the problem of dividing limited resources to individuals arriving over T rounds. Each round has a random number of individuals arrive, and individuals can be characterized by their type. A standard notion of fairness in this setting is that an allocation simultaneously satisfy envy-freeness and efficiency.We show that in the online setting, the two desired properties are in direct contention, in that any algorithm achieving additive envy-freeness up to a factor of L_T necessarily suffers an efficiency loss of at least 1 / L_T. We complement this uncertainty principle with a simple algorithm, HopeGuardrail, which allocates resources based on an adaptive threshold policy. 2 - Overbooking with Bounded Loss Jiayu Zhao, PhD Student, MIT, Cambridge, MA, 611700, United States, Daniel Freund We study a classical problem in revenue management: quantity-based single- resource revenue management with no-shows. In this problem, a firm observes a sequence of T customers drawn independently from a known distribution of k different types, and the firm needs to decide whether to accept or reject in an online fashion given resource capacity B. Each accepted service request yields a type-dependent revenue and has a type-dependent probability of requiring a resource (or, be a no-show) once all arrivals have occurred. If the number of resources required exceeds B at the end of the horizon, the firm pays a fixed compensation for each unfulfilled request. With a clairvoyant, that knows all arrivals ahead of time, as a benchmark, we provide an algorithm with a uniform additive loss bound (i.e., independent of B and T). This improves upon prior works achieving Ω ( √ ;) guarantees.

25