Research

Publications and Accepted Papers

A Single-Sample Polylogarithmic Regret Bound for Nonstationary Online Linear Programming

Haoran Xu, Owen Shen, Peter W. Glynn, Yinyu Ye, and Patrick Jaillet

Accepted at NeurIPS 2026

Under bounded and smooth nonstationarity, when one sample from the request distribution of each period is available in advance, we propose a re-solving policy that achieves O((log⁡n)2) regret in online LP.

Abstract for A Single-Sample Polylogarithmic Regret Bound for Nonstationary Online Linear Programming

We study nonstationary Online Linear Programming (OLP), where n orders arrive sequentially with reward-resource consumption pairs that form a sequence of independent, but not necessarily identically distributed, random vectors. At the beginning of the planning horizon, the decision-maker is provided with a resource endowment that is sufficient to fulfill a significant portion of the requests. The decision-maker seeks to maximize the expected total reward by making immediate and irrevocable acceptance or rejection decisions for each order, subject to this resource endowment. We focus on the challenging single-sample setting, where only one sample from each of the n distributions is available at the start of the planning horizon.

We propose a novel re-solving algorithm that integrates a dynamic programming perspective with the dual-based frameworks traditionally employed in stationary environments. In the large-resource regime, where the resource endowment scales linearly with the number of orders, we prove that our algorithm achieves O((log⁡n)2) regret across a broad class of nonstationary distribution sequences. Our results demonstrate that polylogarithmic regret is attainable even under significant environmental shifts and minimal data availability, bridging the gap between stationary OLP and more volatile real-world resource allocation problems.

A Two-Layer Framework for Joint Online Configuration Selection and Admission Control

Owen Shen, Haoran Xu, Yinyu Ye, Peter W. Glynn, and Patrick Jaillet

ICML 2026 · Proceedings of Machine Learning Research 306:111357–111392

We study the joint configuration selection and admission control problem. The request distributions change endogenously depending on the configuration selection decision. We propose a benchmark that upper bounds the performance of any online policy and design an algorithm having sublinear regret with respect to this benchmark.

Abstract for A Two-Layer Framework for Joint Online Configuration Selection and Admission Control

We study online configuration selection with admission control problem, which arises in LLM serving, GPU scheduling, and revenue management. In a planning horizon with T periods, we consider a two-layer framework for the decisions made within each time period. In the first layer, the decision maker selects one of the K configurations (ex. quantization, parallelism, fare class) which induces distribution over the reward-resource pair of the incoming request. In the second layer, the decision maker observes the request and then decides whether to accept it or not. Benchmarking this framework requires care. We introduce a switching-aware fluid oracle that accounts for the value of mixing configurations over time, provably upper-bounding any online policy. We derive a max-min formulation for evaluating the benchmark, and we characterize saddle points of the max-min problem via primal-dual optimality conditions linking equilibrium, feasibility, and complementarity. This guides the design of SP-UCB–OLP algorithm, which solves an optimistic saddle point problem and achieves O~(KT) regret.

A routing and consolidation decision model for containerized air-land intermodal operations

Kuancheng Huang, Yu-Ting Lee, and Haoran Xu

Computers & Industrial Engineering 141 (2020): 106299

Abstract for A routing and consolidation decision model for containerized air-land intermodal operations

The study aims to provide the decision support for airfreight forwarders regarding the air-land intermodal operation, for which shipments are transported to gateway airports by air transportation and then delivered to final destinations by trucking service. A mixed integer programming model has been formulated to tackle the integrated routing and consolidation decision, given the various types of air containers. This study has designed an approximate solution algorithm based on Lagrangian Relaxation. In the numerical experiment, the solution algorithm can achieve an objective function value very close to optimality or the Lagrangian lower bound within an acceptable computation time.

Papers Under Review

Job Market Paper

Online Linear Programming with Batching

Haoran Xu, Peter W. Glynn, and Yinyu Ye

Under review at Management Science · arXiv preprint, 2024

In the batching operation, the key driver of the regret of online LP is the number of batches. We show that the regret of online LP with batching is logarithmic in the number of batches and independent of the number of orders.

Abstract for Online Linear Programming with Batching

We study Online Linear Programming (OLP) with batching. The planning horizon is cut into K batches, and decisions on orders can be delayed to the end of their associated batch. The ability to delay decisions improves operational performance, as measured by regret. We study two questions: (1) What is a lower bound on the regret as a function of K and the length of the planning horizon? (2) Which algorithms can achieve this regret lower bound? This paper analyzes these questions when the distribution of the reward has a continuous support. We provide an Ω(log⁡K) regret lower bound in the single-resource case, and we provide pricing algorithms having an O(log⁡K) regret in the setting with Poisson arrivals and multiple types of resources. All the algorithms update the prices at most K times and only delay orders of the first and the last batches. All the regret bounds are independent of the length of the planning horizon. Finally, we study a more realistic large support setting where the number of distinct order types is finite but scales with the total number of orders. We prove that our Θ(log⁡K) bounds still hold for the batching operation of a multisecretary problem with discretized uniform rewards in this large support setting, provided the support grows fast enough. This suggests that the continuous support setting that is the paper’s focus serves as a useful theoretical surrogate for the more realistic large finite support setting.

Working Papers

Bridging the Discrete and Continuous Reward Theories for Online Linear Programming: The Key Role Played by the Support Size

Haoran Xu, Peter W. Glynn, and Yinyu Ye

Working paper · SSRN preprint, 2026

We bridge the discrete and continuous reward theories for online LP by studying the joint dependence of regret on the number of requests n and the reward support size S. When there is a single type of resource, we show that the regret of online LP is O(log⁡(min⁡{n,S2})) under appropriate regularity conditions.

Abstract for Bridging the Discrete and Continuous Reward Theories for Online Linear Programming: The Key Role Played by the Support Size

Existing finite support theory for online linear programming gives regret bounds independent of the number of requests but typically polynomial in the reward support size. On the other hand, continuous support theory establishes that the regret is logarithmic in the number of requests. Given the quite different regret behaviors in these two settings, it is natural to study the intermediate regime, where both the number of requests n and the reward-support size S are large but finite. This regime is also important at a practical level, as it describes settings in which the number of customer types and number of requests are both large. We consider the single resource problem with independent and identically distributed requests from a known distribution. Under appropriate regularity conditions, we prove an O(log⁡(min⁡{n,S2})+1/πmin) regret bound for the Fluid Bayes Selector algorithm, where πmin denotes the smallest point mass in the marginal distribution of resource consumption. This bound requires no nondegeneracy assumption on the finite support fluid LP. Under additional conditions, every feasible policy incurs Ω(log⁡(min⁡{n,S2})) regret. We construct two sequences of instances to show that the 1/πmin term is necessary in the worst case but not for every instance. For the multisecretary problem, exact asymptotics under additional smoothness and polynomial support growth establish n as the exact support size scale at which continuous support theory correctly predicts the leading order term of regret of the large support regime. These results quantify the transition between finite and continuous support regret behavior, and clarify the impact of support size on regret.

Work in Preparation

Confidence Bounds of Stochastic Dynamic Programming by Sample Average Approximation and Information Relaxation

with Gerd Infanger and Peter W. Glynn

Incorporating Forecasts into Sequential Decision Making Problems

with Peter W. Glynn

Research Projects

Stanford Campus Cooling and Heating Operations

with Jacques de Chalendar

Description of Stanford Campus Cooling and Heating Operations

This project aims to improve the sustainability of the campus cooling and heating system at Stanford University. A key challenge is uncertainty in cooling and heating demand. Under the existing operating guidelines, maintaining reliable service during extreme weather events may require larger storage facilities, while maintaining larger reserves under normal conditions can increase electricity consumption and carbon dioxide emissions. To address this trade-off between reliability and sustainability, we use models of forecast errors from the literature to characterize the conditional distribution of actual cooling and heating demand given the current forecast, and develop a stochastic model predictive control method that repeatedly solves the remaining control problem using updated forecasts.