114:00 — A Better Match for Everyone, Reinforcement Learning for Ridesharing

I teamed up with Lyft, a popular ridesharing platform, to improve its online matching system for drivers and riders. To create a more efficient algorithm that can quickly adapt to changing conditions, we introduced a novel online reinforcement learning approach with a hierarchical linear approximation of the platform's state space adapted to a nonstationary environment. This overhaul of Lyft’s core system resulted in millions of additional rides and more than \$30 million in extra revenue annually. Our approach is the first documented implementation of a ridesharing matching algorithm that can adapt to a nonstationary environment, and our experiments proved that this change benefits everyone involved - drivers, riders, and the platform. However, it was difficult for a large organization to trust an algorithm that can change itself.

214:30 — Branch-and-price for prescriptive contagion analytics

Predictive contagion models are ubiquitous in epidemiology, social sciences, engineering, and management. This paper formulates a prescriptive contagion analytics model where a decision-maker allocates shared resources across multiple segments of a population, each governed by continuous-time dynamics. We define four real-world problems under this umbrella: vaccine distribution, vaccination centers deployment, content promotion, and congestion mitigation. These problems feature a large-scale mixed-integer non-convex optimization structure with constraints governed by ordinary differential equations, combining the challenges of discrete optimization, non-linear optimization, and continuous-time system dynamics. This paper develops a branch-and-price methodology for prescriptive contagion analytics based on: (i) a set partitioning reformulation; (ii) a column generation decomposition; (iii) a state-clustering algorithm for discrete-decision continuous-state dynamic programming; and (iv) a tri-partite branching scheme to circumvent non-linearities. Extensive experiments show that the algorithm scales to very large and otherwise-intractable instances, outperforming state-of-the-art benchmarks. Our methodology provides practical benefits in contagion systems; in particular, it can increase the effectiveness of a vaccination campaign by an estimated 12-70\%, resulting in 7,000 to 12,000 extra saved lives over a three-month horizon mirroring the COVID-19 pandemic.

315:00 — Heterogeneous Treatment Effects In Matching Marketplaces Under Interference: From Estimation to Decision

Marketplace companies routinely use randomized experiments to make operational decisions. Randomized controlled trials are often used to decide whether a specific intervention should be rolled out. Because rollouts can be global (affecting all users) or partial (targeting some users), it is important to measure the effect of the treatment intervention on specific sub-populations of users, also known as heterogeneous treatment effect analysis. However, marketplace experiments suffer from interference, where the treatment status of one unit can affect the outcome of another unit. We first establish that heterogeneous treatment effects are not necessarily uniquely defined in the presence of marketplace interference. We then distinguish two cases: when the heterogeneous treatment effect on a subset of users is uniquely defined, we show that a ``shadow price estimator'' based on linear programming duality can provably reduce bias from the standard estimator. When the heterogeneous treatment effect is not uniquely defined, we recast the problem of estimating the impact of treatment on each group of users as the problem of deciding whether or not to roll out the treatment to each group of users. We use the shadow price estimator to design a robust decision rule, which we show is more effective and less conservative than a similarly robust decision rule based on the standard estimator. We verify our theoretical results with numerical experiments on synthetic data.

415:30 — Modeling and Optimizing Large-Scale Inventory Routing in East Africa: A Data-Driven Optimization Approach

We investigate a large-scale inventory routing problem in the context of distributing clean cooking stoves in East Africa. Using a comprehensive dataset from an industry partner, we develop a stochastic model that accounts for significant supply and demand fluctuations, censored and incomplete data, and store substitution patterns and propose novel data-driven approaches to solve the resulting problem at scale. Our numerical results demonstrate that the proposed method yields significant improvements over the status quo, leading to significant cost savings and improved accessibility to clean cooking solutions.