Bayesian optimization devolves the global optimization of a costly objective function to the global optimization of a sequence of acquisition functions. This inner-loop optimization can be catastrophically difficult if it involves posterior sample paths, especially in higher dimensions. We introduce an efficient global optimization strategy for posterior samples based on global rootfinding. It provides gradient-based optimizers with two sets of judiciously selected starting points, designed to combine exploration and exploitation. The number of starting points can be kept small without sacrificing optimization quality. Remarkably, even with just one point from each set, the global optimum is discovered most of the time. The algorithm scales practically linearly to high dimensions, breaking the curse of dimensionality. For Gaussian process Thompson sampling (GP-TS), we demonstrate remarkable improvement in both inner- and outer-loop optimization, surprisingly outperforming alternatives like EI and GP-UCB in most cases. Our approach also improves the performance of other posterior sample-based acquisition functions, such as variants of entropy search. Furthermore, we propose a sample-average formulation of GP-TS, which has a parameter to explicitly control exploitation and can be computed at the cost of one posterior sample.

Understanding driver behavior in on-demand mobility services is crucial for designing efficient and sustainable transport models. Drivers’ delivery strategy is well understood, but their search strategy and learning process still lack an empirically validated model. Here we provide a game-theoretic model of driver search strategy and learning dynamics, interpret the collective outcome in a thermodynamic framework, and verify its various implications empirically. We capture driver search strategies in a multi-market oligopoly model, which has a unique Nash equilibrium and is globally asymptotically stable. The equilibrium can therefore be obtained via heuristic learning rules where drivers pursue the incentive gradient or simply imitate others. To help understand city-scale phenomena, we offer a macroscopic view with the laws of thermodynamics. With 870 million trips of over 50k drivers in New York City, we show that the equilibrium well explains the spatiotemporal patterns of driver search behavior, and estimate an empirical constitutive relation. We find that new drivers learn the equilibrium within a year, and those who stay longer learn better. The collective response to new competition is also as predicted. Among empirical studies of driver strategy in on-demand services, our work examines the longest period, the most trips, and is the largest for taxi industry.

Travel decisions are fundamental to understanding human mobility, urban economy, and sustainability, but measuring it is challenging and controversial. Previous studies of taxis are limited to taxi stands or hail markets at aggregate spatial units. Here we estimate the dynamic demand and supply of taxis in New York City (NYC) at street segment level, using in-vehicle Global Positioning System (GPS) data which preserve individual privacy. To this end, we model taxi demand and supply as non-stationary Poisson random fields on the road network, and pickups result from income-maximizing drivers searching for impatient passengers. With 868 million trip records of all 13,237 licensed taxis in NYC in 2009 - 2013, we show that while taxi demand are almost the same in 2011 and 2012, it declined about 2% in spring 2013, possibly caused by transportation network companies (TNCs) and fare raise. Contrary to common impression, street-hail taxis out-perform TNCs such as Uber in high-demand locations, suggesting a taxi/TNC regulation change to reduce congestion and pollution. We show that our demand estimates are stable at different supply levels and across years, a property not observed in existing matching functions. We also validate that taxi pickups can be modeled as Poisson processes. Our method is thus simple, feasible, and reliable in estimating street-hail taxi activities at a high spatial resolution; it helps quantify the ongoing discussion on congestion charges to taxis and TNCs.