We study a \emph{max-risk} objective for active learning in $d$-armed bandits: a learner adaptively allocates a budget of $T$ samples across $d$ groups to minimize the worst-case per-group uncertainty index $\max_{k\in[d]}\sigma_k^2/n_k$. We develop a local minimax framework and prove the first general lower bound for this objective, valid for any finite-variance hypothesis class $\mathcal H$. The bound separates difficulty into three orthogonal factors: a \emph{budget} term, a \emph{heteroscedasticity} index measuring how unevenly the uncertainty is spread across arms, and a model-dependent curvature functional, the \emph{Variance Local Curvature} ($\mathrm{VLC}$), which captures how much information a local change of variance creates inside $\mathcal H$. For smooth classes, the $\mathrm{VLC}$ is a reparametrization of a variance–Fisher information, with closed-form values for common families. Benchmarking against the strongest available upper bound shows near-optimality up to logarithmic factors in broad regimes, and pinpoints a systematic gap in highly heterogeneous instances. Our proof introduces two key ingredients: a loss-induced $\ell_1$ geometry on the decision space, and a representation-based instance generator that reduces hard-instance construction to an explicit random matrix calculation.

We describe a novel framework for discrete choice modeling and price optimization for settings where scheduled service options (often hierarchical) are offered to customers, which is applicable across many businesses including some within Amazon. In such business settings, the customers would see multiple options, often substitutable, with their features and their prices. These options typically vary in the start and/or end time of the service requested, such as the date of service or a service time window. The costs and demand can vary widely across these different options, resulting in the need for different prices. We propose a system which allows for segmenting the marketplace (as defined by the particular business) using decision trees, while using parametric discrete choice models within each market segment to accurately estimate conversion behavior. Using parametric discrete choice models allows us to capture important behavioral aspects like reference price effects which naturally occur in scheduled service applications. In addition, we provide natural and fast heuristics to do price optimization. For one such Amazon business where we conducted a live A/B experiment, this new framework outperformed the existing pricing system in every key metric, increasing our target performance metric by 19%, while providing a robust platform to support future new services of the business. The model framework has now been in full production for this business since Q4 2023.

Data-driven optimization aims to translate a machine learning model into decision-making by optimizing decisions on estimated costs. Such a pipeline can be conducted by fitting a distributional model which is then plugged into the target optimization problem. While this fitting can utilize traditional methods such as maximum likelihood, a more recent approach uses estimation-optimization integration that minimizes decision error instead of estimation error. Although intuitive, the statistical benefit of the latter approach is not well understood yet is important to guide the prescriptive usage of machine learning. In this paper, we dissect the performance comparisons between these approaches in terms of the amount of model misspecification. In particular, we show how the integrated approach offers a “universal double benefit” on the top two dominating terms of regret when the underlying model is misspecified, while the traditional approach can be advantageous when the model is nearly well-specified. Our comparison is powered by finite-sample tail regret bounds that are derived via new higher-order expansions of regrets and the leveraging of a recent Berry-Esseen theorem.

Data-driven stochastic optimization is ubiquitous in machine learning and operational decision-making problems. Sample average approximation (SAA) and model-based approaches such as estimate-then-optimize (ETO) or integrated estimation-optimization (IEO) are all popular, with model-based approaches being able to circumvent some of the issues with SAA in complex context-dependent problems. Yet the relative performance of these methods is poorly understood, with most results confined to the dichotomous cases of the model-based approach being either well-specified or misspecified. We develop the first results that allow for a more granular analysis of the relative performance of these methods under a local misspecification setting, which models the scenario where the model-based approach is nearly well-specified. By leveraging tools from contiguity theory in statistics, we show that there is a bias-variance tradeoff between SAA, IEO, and ETO under local misspecification, and that the relative importance of the bias and the variance depends on the degree of local misspecification. Moreover, we derive explicit expressions for the decision bias, which allows us to characterize (un)impactful misspecification directions, and provide further geometric understanding of the variance.

We consider the problem of pricing a reusable resource service system. Potential customers arrive according to a Poisson process and purchase the service if their valuation exceeds the current price. If no units are available, customers immediately leave without service. Serving a customer corresponds to using one unit of the reusable resource, where the service time has a general distribution. The objective is to maximize the steady-state revenue rate. This system is equivalent to the classical Erlang loss model with price-sensitive customers, which has applications in vehicle sharing, cloud computing, and spare parts management.

We consider a personalized pricing problem in which we have data consisting of feature information, historical pricing decisions, and binary realized demand. The goal is to perform off-policy evaluation for a new personalized pricing policy that maps features to prices. Methods based on inverse propensity weighting (including doubly robust methods) for off-policy evaluation may perform poorly when the logging policy has little exploration or is deterministic, which is common in pricing applications. Building on the balanced policy evaluation framework of Kallus (2018), we propose a new approach tailored to pricing applications. The key idea is to compute an estimate that minimizes the worst-case mean squared error or maximizes a worst-case lower bound on policy performance, where in both cases the worst-case is taken with respect to a set of possible revenue functions. We establish theoretical convergence guarantees and empirically demonstrate the advantage of our approach using a real-world pricing dataset.

We consider a fundamental problem where there are multiple groups whose data distributions are unknown, and an analyst would like to learn the mean of each group. We consider an active learning framework to sequentially collect $T$ samples with bandit, each period observing a sample from a chosen group. After observing a sample, the analyst may update their estimate of the mean and variance of that group and choose the next group accordingly. The objective is to dynamically collect samples to minimize the $p$-norm of the vector of variances of our mean estimators after $T$ rounds. We propose an algorithm, Variance-UCB, that selects groups according to a an upper bound on the variance estimate adjusted to the $p$-norm chosen. We show that the regret of Variance-UCB is $O(T^{-2})$ for finite $p$, and prove that no algorithm can do better. When $p$ is infinite, we recover the $O(T^{-1.5})$ obtained in \cite{activelearning, carpentier2011upper} and provide a new lower bound showing that no algorithm can do better.

Managing player engagement is an important problem in the video game industry, as many games generate revenue via subscription models and microtransactions. We consider a class of online video games whereby players are repeatedly matched by the game to compete against one another. Players have different skill levels which affect the outcomes of matches, and the win-loss record influence their willingness to remain engaged. The goal is to maximize the overall player engagement over time by optimizing the dynamic matchmaking strategy. We propose a general but tractable framework to solve this problem, which can be formulated as an infinite linear program. We then focus on a stylized model where there are two skill levels and players churn only when they experience a losing streak. The optimal policy always matches as many low-skilled players who are not at risk of churning to high-skilled players who are one loss away from churning. In some scenarios when there are too many low-skilled players, high-skilled players are also matched to low-skilled players that are at risk of churning.

We consider the use of decision trees for decision-making problems under the predict-then-optimize framework. That is, we would like to first use a decision tree to predict unknown input parameters of an optimization problem, and then make decisions by solving the optimization problem using the predicted parameters. A natural loss function in this framework is to measure the suboptimality of the decisions induced by the predicted input parameters, as opposed to measuring loss using input parameter prediction error. This natural loss function is known in the literature as the Smart Predict-then-Optimize (SPO) loss, and we propose a tractable methodology called SPO Trees (SPOTs) for training decision trees under this loss. SPOTs benefit from the interpretability of decision trees, providing an interpretable segmentation of contextual features into groups with distinct optimal solutions to the optimization problem of interest. We conduct several numerical experiments on synthetic and real data including the prediction of travel times for shortest path problems and predicting click probabilities for news article recommendation. We demonstrate on these datasets that SPOTs simultaneously provide higher quality decisions and significantly lower model complexity than other machine learning approaches (e.g., CART) trained to minimize prediction error.

In the online video game industry, a significant portion of the revenue is generated from microtransactions, where a small amount of real-world currency is exchanged for virtual items to be used in the game. One popular way to conduct microtransactions is via a loot box, which is a random bundle of virtual items whose contents are not revealed until after purchase. In this work, we consider how to optimally price and design loot boxes from the perspective of a revenue-maximizing video game company, and analyze customer surplus under such selling strategies. Our paper provides the first formal treatment of loot boxes, with the aim to provide customers, companies, and regulatory bodies with insights into this popular selling strategy. We consider two types of loot boxes: a traditional one where customers can receive (unwanted) duplicates, and a unique one where customers are guaranteed to never receive duplicates. We show that as the number of virtual items grows large, the unique box strategy is asymptotically optimal, while the traditional box strategy only garners 36.7% of the optimal revenue. On the other hand, unique box strategies leaves almost zero customer surplus, while traditional box strategies leaves positive surplus. Further, when designing traditional and unique loot boxes, we show it is asymptotically optimal to allocate the items uniformly, even when the item valuation distributions are highly heterogeneous. We also show that when the seller purposely misrepresents the allocation probabilities, then their revenue may increase significantly and thus strict regulation is needed. Finally, we show that even if the seller allows customers to salvage unwanted items, then the customer surplus can only increase by at most 1.4%.

The predict-then-optimize framework is fundamental in many practical settings: predict the unknown parameters of an optimization problem, and then solve the problem using the predicted values of the parameters. A natural loss function in this environment is to consider the cost of the decisions induced by the predicted parameters, in contrast to the prediction error of the parameters. This loss function was recently introduced in [Elmachtoub and Grigas, 2017], which called it the Smart Predict-then-Optimize (SPO) loss. Since the SPO loss is nonconvex and noncontinuous, standard results for deriving generalization bounds do not apply. In this work, we provide an assortment of generalization bounds for the SPO loss function. In particular, we derive bounds based on the Natarajan dimension that, in the case of a polyhedral feasible region, scale at most logarithmically in the number of extreme points, but, in the case of a general convex set, have poor dependence on the dimension. By exploiting the structure of the SPO loss function and an additional strong convexity assumption on the feasible region, we can dramatically improve the dependence on the dimension via an analysis and corresponding bounds that are akin to the margin guarantees in classification problems.