Research

We study stochastic dynamic resource allocation with continuously distributed rewards. We develop an analytical framework that bounds the additive performance loss of threshold policies directly against the dynamic-programming (DP) optimum. The framework reduces this comparison to controlling the Bellman residual of a tractable value approximation and the discrepancy between its induced thresholds and those used by the policy. Applying this framework, we show that the classical certainty-equivalent (CE) policy incurs a constant expected loss, independent of the time horizon, under suitable regularity and non-degeneracy conditions. We showcase the power of this framework in the multi-secretary problem with our guarantee covering i.i.d., independent but non-identically distributed, and Markov-modulated rewards. We also provide an extension to online linear programming problem, demonstrating its capability of handling multi-dimensional problems beyond multi-secretary. Together, these results sharpen our understanding of CE and establish its near-optimality for dynamic resource allocation problems across a substantially broader class of stochastic models.

Bandit algorithms generate data for downstream inference, but adaptive sampling biases post-bandit sample means. We analyze this bias for stable index algorithms, including UCB1 and its generalizations, and derive sharp leading-order expressions for the sample-mean bias and expected $Z$-statistic. Our characterization reveals the algorithmic origin of bias through a key index-function-dependent quantity, which we term effective exploration rate. For example, under UCB1, the effective exploration rate is of order $\sqrt{\log T}$, and the standardized bias of any arm (that is not uniquely optimal) decays at the extremely slow rate $1/\sqrt{\log T}$. We also show how the choice of the index function affects both regret and bias, which reveals a regret-bias trade-off: more exploratory algorithm reduces bias but increases regret. Our sharp characterization for bias uses a novel empirical fluid approximation of the algorithm’s sampling dynamics, which may be of independent interest.

When multi-armed bandit (MAB) algorithms allocate pulls among competing arms, the resulting allocation can exhibit huge variation. This is particularly harmful in modern applications such as learning-enhanced platform operations and statistical inference using bandit-collected data. Thus motivated, we introduce a new performance metric of MAB algorithms termed allocation variability, which is the largest (over arms) standard deviation of an arm’s number of pulls. We establish a fundamental trade-off between allocation variability and regret, the canonical performance metric of reward maximization. In particular, for any algorithm, the worst-case regret $R_T$ and worst-case allocation variability $S_T$ must satisfy $R_T S_T=\Omega(T^{3/2})$ as $T \to \infty$, as long as $R_T=o(T)$. This indicates that any minimax regret-optimal algorithm must incur worst-case allocation variability $\Theta(T)$, the largest possible scale; while any algorithm with sublinear worst-case regret must necessarily incur $S_T= \omega(\sqrt{T})$. We further show that this lower bound is essentially tight, and that any point on the Pareto frontier $R_T S_T=\Theta(T^{3/2})$ can be achieved (up to a polylogarithmic factor in T) by a simple tunable algorithm UCB-f, a generalization of the classic UCB1. Finally, we discuss implications for platform operations and for statistical inference, when bandit algorithms are used. As a byproduct of our result, we resolve an open question of Praharaj and Khamaru (2025).

We characterize a joint CLT of the number of pulls and the sample mean reward of the arms in a stochastic two-armed bandit environment under UCB algorithms. Several implications of this result are in place: (1) a nonstandard CLT of the number of pulls hence pseudo-regret that smoothly interpolates between a standard form in the large arm gap regime and a slow-concentration form in the small arm gap regime, and (2) a heuristic derivation of the sample bias up to its leading order from the correlation between the number of pulls and sample means. Our analysis framework is based on a novel perturbation analysis, which is of broader interest on its own.

There has been a growing interest in studying online stochastic packing under more general correlation structures, motivated by the complex data sets and models driving modern applications. Several past works either assume correlations are weak or have a particular structure, have a complexity scaling with the number of Markovian ‘states of the world’ (which may be exponentially large e.g. in the case of full history dependence), scale poorly with the horizon T, or make additional continuity assumptions. Surprisingly, we show that for all 𝜖, the online stochastic packing linear programming problem with general correlations (suitably normalized and with sparse columns) has an approximately optimal policy (with optimality gap $\epsilon T$) whose per-decision runtime scales as the time to simulate a single sample path of the underlying stochastic process (assuming access to a Monte Carlo simulator), multiplied by a constant independent of the horizon or number of Markovian states.We derive analogous results for network revenue management, and online bipartite matching and independent set in bounded-degree graphs, by rounding. Our algorithms implement stochastic gradient methods in a novel on-the-fly/recursive manner for the associated massive deterministic-equivalent linear program on the corresponding probability space.

The Certainty Equivalent (CE) heuristic is a widely-used algorithm for various dynamic resource allocation problems in OR and OM. Despite its popularity, existing theoretical guarantees of CE are limited to settings satisfying restrictive fluid regularity conditions, particularly, the non-degeneracy conditions, under the widely held belief that the violation of such conditions leads to performance deterioration and necessitates algorithmic innovation beyond CE. In this work, we conduct a refined performance analysis of CE within the general framework of online linear programming. We show that CE achieves uniformly near-optimal regret (up to a polylogarithmic factor in T) under only mild assumptions on the underlying distribution, without relying on any fluid regularity conditions. Our result implies that, contrary to prior belief, CE effectively beats the curse of degeneracy for a wide range of problem instances with continuous conditional reward distributions, highlighting the distinction of the problem’s structure between discrete and non-discrete settings. Our explicit regret bound interpolates between the mild $(\log T)^2$ regime and the worst-case $\sqrt{T}$ regime with a parameter $\beta$ quantifying the minimal rate of probability accumulation of the conditional reward distributions, generalizing prior findings in the multisecretary setting. To achieve these results, we develop novel algorithmic analytical techniques. Drawing tools from the empirical processes theory, we establish strong concentration analysis of the solutions to random linear programs, leading to improved regret analysis under significantly relaxed assumptions. These techniques may find potential applications in broader online and offline stochastic decision-making contexts.

The increasingly prevalent ‘fulfillment by platform‘ practice in the digital economy presents platforms with the unique challenge of managing their third-party sellers’ autonomous inventory decision-making. In this work, we explore a novel idea to mitigate this challenge through nudging demand among sellers, which reshapes their perceived demand and incentivizes them to make platform-favorable inventory decisions. To this end, we study a stylized Stackelberg game between a platform and a continuum of third-party sellers selling substitutable products on the platform. The platform aims to design a demand nudging policy to maximize her profit, while the sellers, in response, determine their inventory according to the post-nudge demand in a newsvendor manner. We establish in closed form the platform’s optimal policy. It employs a simple cut-off structure called defluctuating and resembles risk pooling in the centralization setting where the platform can make joint demand-substitution and inventory decisions. Despite the power of this control on the off-equilibrium path, we show that it is Pareto-improving for both the platform and the sellers under a mild condition. Furthermore, when the products are substitutable enough, the platform can achieve the centralization benchmark. On the contrary, if the products are not substitutable enough, the platform’s service level to the customers may, in certain primitive regimes, decrease.

• ACM EC'24 version [link]

The optimal stopping (OS) problem is important to multiple academic communities and applications. Modern OS tasks often have long horizon and complicated, high-dimensional dynamics, making them especially challenging. Standard dynamic programming (DP) formulation has computational cost scaling exponentially in the horizon and the underlying dimension, suffering from the curse of dimensionality. In this work, we develop a novel expansion representation of the optimal stopping value that deviates from the DP formulation. Truncating this expansion yields a simulation-based algorithm that returns an  -optimal solution (both stopping policies and approximate optimal values) with computational complexity scaling polynomially in the time horizon and the underlying dimension. Our approach is closely related to the martingale duality of OS, which may be of independent theoretical interest.

• First Place, 2019 INFORMS Nicholson Student Paper Competition
• Finalist, 2018 INFORMS Section on Finance Student Best Paper Award

Resource pooling improves system efficiency drastically in large stochastic systems, but its effective implementation in decentralized systems remains relatively underexplored. This paper studies how to incentivize resource pooling when agents are self-interested, and their states are private information. Our primary motivation is applications in the design of decentralized computing markets, among others. We study a standard multi-server queueing model in which each server is associated with an M/M/1 queue and aims to minimize its time-average job holding and processing costs. We design a simple token-based mechanism where servers can earn tokens by offering help and spend tokens to request help from other servers, all in their self-interest. The mechanism induces a complex game among servers. We employ the fluid mean-field equilibrium (FMFE) concept to analyze the system, combining mean-field approximation with fluid relaxation. This framework enables us to derive a closed-form characterization of servers’ FMFE strategies. We show that these FMFE strategies approximate well the servers’ rational behavior. We leverage this framework to optimize the design of the mechanism and present our main results: As the number of servers increases, the proposed mechanism incentivizes complete resource pooling—that is, the system dynamics and performance under our mechanism match those under centralized control. Finally, we show that our mechanism achieves the first-best performance even when helping others incurs higher job processing costs and remains nearly optimal in settings with heterogeneous servers.

• First Place, 2024 INFORMS JFIG Best Paper Competition
• First Prize, 2024 CSAMSE Best Paper Award

• MSOM Service Management SIG 2024
• ACM EC'24 version [link]

Motivated by matching platforms that match agents in a centralized manner, we study dynamic two-sided matching in a setting where both customers (demand) and service providers (supply) are heterogeneous and the pool of service providers is limited. We model heterogeneity on the two sides of the market by demand weight vectors drawn i.i.d. from some distribution, and supply feature vectors drawn i.i.d. from a (possibly) different distribution. The matching of a demand-supply pair generates a matching value that depends on their weight and feature vectors. We adopt a notion of regret, specifically the additive loss relative to the value (per match) achievable in the limiting hindsight optimum as our performance metric for matching policies. Simple myopic policies suffer non-vanishing regret in large markets. We propose a forward-looking supply-aware policy dubbed Simulate-Optimize-Assign-Repeat (SOAR) which balances between producing high match value for the current match and preserving valuable supply for future customers. We prove that SOAR achieves the optimal regret scaling under different assumptions on the demand and supply distributions. En-route to proving our guarantees we develop a novel framework for analyzing the performance of our SOAR policy which may be of broader interest. As a corollary of our techniques, we also resolve an open problem posed in Kanoria [2022].

• First Place, 2024 INFORMS RMP Jeff McGill Student Paper Competition (awarded to Akshit Kumar)
• Third Place, 2025 Michael H. Rothkopf Junior Research Paper Prize (awarded to Akshit Kumar)

• ACM EC'23 version [link] | Nick Arnosti's blog