Assaf Zeevi

We consider a finite horizon optimal stopping problem for a sequence of independent and identically distributed random variables, where the objective is to design stopping rules that attempt to select the random variable with the highest value in the sequence. The performance of any stopping rule may be benchmarked relative to the selection of a ‘prophet’ that has perfect foreknowledge of the largest value. Such comparisons are typically stated in the form of ‘prophet inequalities’. We develop a game-theoretic characterization that supports a principled approach for deriving sharp non-asymptotic prophet inequalities for single-threshold stopping rules. We demonstrate that sharp constants in the ratio- and difference-type prophet inequalities are determined by the optimal values of an infinite two-person zero-sum game on the unit square with particular payoff kernels, while the solutions to the game provide optimal stopping rules and least favorable distributions. Among other things, this formulation also allows a systematic way to tackle restricted classes of distributions. The proposed framework leads to a numerically efficient algorithmic paradigm that allows the computing of sharp constants in prophet inequalities with any prescribed level of accuracy.

We consider a dynamic combinatorial optimization problem where at each time step, the decision maker selects a subset of cardinality K from N possible items and observes a feedback in the form of the index of one of the items in the said subset or none. Each of the N items is ascribed a certain value (reward), which is collected if the item is chosen. This problem is motivated by that of assortment selection in online retail, where items are products. Akin to that literature, it is assumed that the choice of the item given the subset is governed by a multinomial logit (MNL) choice model whose parameters are a priori unknown. The objective of the decision maker is to maximize the expected cumulative rewards over a finite horizon T or alternatively, minimize the regret relative to an oracle that knows the MNL choice model parameters. We formulate this problem as a multiarmed bandit problem that we refer to as the MNL-bandit problem. We present a Thompson sampling-based algorithm for this problem and show that it achieves near-optimal regret as well as attractive empirical performance. Funding: S. Agrawal is supported in part by the Division of Civil, Mechanical and Manufacturing Innovation [NSF Grant 1846792]. V. Goyal is supported in part by the Division of Civil, Mechanical and Manufacturing Innovation [NSF Grants 1351838 and 1636046]. A. Zeevi is supported in part by the Division of Computer and Network Systems [NSF Grant 0964170] and the United States-Israel Binational Science Foundation [Grant 2010466].

We develop a general theory to optimize the frequentist regret for sequential learning problems, from which efficient bandit and reinforcement learning algorithms can be derived via unified Bayesian principles. Building on the recent Decision-Estimation Coefficient (DEC) framework, we propose a novel optimization approach to generate “algorithmic beliefs” at each round and use Bayesian posteriors for decision-making. The optimization objective, termed “Algorithmic Information Ratio” (AIR), represents an intrinsic complexity measure that effectively characterizes the frequentist regret of any algorithm. Although AIR’s minimax regret aligns with that provided by DEC, it additionally offers an algorithm-dependent perspective–distinct from a minimax complexity–facilitating algorithm design and analysis. Specifically, AIR enables deriving explicit algorithms via belief parameterization and provides clear approximation guidelines with provable guarantees. Moreover, the resulting algorithms have a simple structure and are computationally efficient for several representative problems. We illustrate our framework with a novel algorithm for multi-armed bandits that performs strongly across stochastic, adversarial, and non-stationary environments, and demonstrate applicability to linear bandits, convex bandits, and reinforcement learning.

Thompson Sampling is one of the most widely used and studied bandit algorithms, known for its simple structure, low regret performance, and solid theoretical guarantees. Yet, in stark contrast to most other families of bandit algorithms, the exact mechanism through which posterior sampling (as introduced by Thompson) is able to "properly" balance exploration and exploitation, remains a mystery. In this paper we show that the core insight to address this question stems from recasting Thompson Sampling as an online optimization algorithm. To distill this, a key conceptual tool is introduced, which we refer to as "faithful" stationarization of the regret formulation. Essentially, the finite horizon dynamic optimization problem is converted into a stationary counterpart which "closely resembles" the original objective (in contrast, the classical infinite horizon discounted formulation, that leads to the Gittins index, alters the problem and objective in too significant a manner). The newly crafted time invariant objective can be studied using Bellman's principle which leads to a time invariant optimal policy. When viewed through this lens, Thompson Sampling admits a simple online optimization form that mimics the structure of the Bellman-optimal policy, and where greediness is regularized by a measure of residual uncertainty based on point-biserial correlation. This answers the question of how Thompson Sampling balances exploration-exploitation, and moreover, provides a principled framework to study and further improve Thompson's original idea.

We consider a class of sequential learning problems where a decision maker must learn the unknown statistical characteristics of a finite set of alternatives (or systems) using sequential sampling to ultimately select a subset of “good” alternatives. A salient feature of our problem is that system performance is governed by a set of features. The decision maker postulates the dependence on these features to be linear, but this model may not precisely represent the true underlying system structure. We show that this misspecification, if not managed properly, can lead to suboptimal performance because of a phenomenon identified as sample-selection endogeneity. We propose a prospective sampling principle—a new approach that eliminates the adverse effects of misspecification as the number of samples grows large. The proposed principle applies across a very general class of widely used sampling policies, enjoys strong asymptotic performance guarantees, and exhibits effective finite-sample performance in numerical experiments. This paper was accepted by Vivek Farias, data science. Funding: This work was supported by the United States-Israel Binational Science Foundation [Grant 2020063] and the Hong Kong Research Grant Council [GRF Grant 16501821 and ECS Grant 24210420]. Supplemental Material: The online appendix and data files are available at https://doi.org/10.1287/mnsc.2022.00328 .

We study problem-dependent rates, that is, generalization errors that scale near-optimally with the variance, effective loss, or gradient norms evaluated at the “best hypothesis.” We introduce a principled framework dubbed “uniform localized convergence” and characterize sharp problem-dependent rates for central statistical learning problems. From a methodological viewpoint, our framework resolves several fundamental limitations of existing uniform convergence and localization analysis approaches. It also provides improvements and some level of unification in the study of localized complexities, one-sided uniform inequalities, and sample-based iterative algorithms. In the so-called “slow rate” regime, we provide the first (moment-penalized) estimator that achieves the optimal variance-dependent rate for general “rich” classes; we also establish an improved loss-dependent rate for standard empirical risk minimization. In the “fast rate” regime, we establish finite-sample, problem-dependent bounds that are comparable to precise asymptotics. In addition, we show that iterative algorithms such as gradient descent and first order expectation maximization can achieve optimal generalization error in several representative problems across the areas of nonconvex learning, stochastic optimization, and learning with missing data. Supplemental Material: The online appendix is available at https://doi.org/10.1287/moor.2021.0076 .

The principle of optimism in the face of uncertainty is one of the most widely used and successful ideas in multi-armed bandits and reinforcement learning. However, existing optimistic algorithms (primarily UCB and its variants) often struggle to deal with general function classes and large context spaces. In this paper, we study general contextual bandits with an offline regression oracle and propose a simple, generic principle to design optimistic algorithms, dubbed "Upper Counterfactual Confidence Bounds" (UCCB). The key innovation of UCCB is building confidence bounds in policy space, rather than in action space as is done in UCB. We demonstrate that these algorithms are provably optimal and computationally efficient in handling general function classes and large context spaces. Furthermore, we illustrate that the UCCB principle can be seamlessly extended to infinite-action general contextual bandits, provide the first solutions to these settings when employing an offline regression oracle.

This paper investigates the problem of information sharing between a retail platform and a manufacturer in a supply chain. We develop a stylized model salient to which is that the product’s quality is a priori unknown to customers, who can infer it from customer-generated reviews. The platform, in turn, has access to private information concerning the relationship between quality and demand, and the manufacturer can choose to acquire said information to help determine the quality of its product accordingly. Our analysis yields three main insights. First, information sharing in and of itself induces the manufacturer to improve quality. Second, under a wholesale price contract, information sharing and product reviews together have a negative effect on product quality: When each firm is able to adjust its price in response to the quality signal, it benefits the manufacturer and hinders the platform. Consequently, the presence of reviews discourages the platform from sharing information, and the manufacturer tends to produce a lower-quality product. Finally, the negative effect of product reviews on the supply chain can be mitigated when the platform can share less accurate information or when the platform and manufacturer make a commission contract, rather than a wholesale price contract. This paper was accepted by Jayashankar Swaminathan, operations management. Funding: D. Shin received financial support from the Hong Kong University of Science and Technology [grant IGN17BM09]. Supplemental Material: The online appendix and data are available at https://doi.org/10.1287/mnsc.2023.4746 .

We develop a general theory to optimize the frequentist regret for sequential learning problems, where efficient bandit and reinforcement learning algorithms can be derived from unified Bayesian principles. We propose a novel optimization approach to generate "algorithmic beliefs" at each round, and use Bayesian posteriors to make decisions. The optimization objective to create "algorithmic beliefs," which we term "Algorithmic Information Ratio," represents an intrinsic complexity measure that effectively characterizes the frequentist regret of any algorithm. To the best of our knowledge, this is the first systematical approach to make Bayesian-type algorithms prior-free and applicable to adversarial settings, in a generic and optimal manner. Moreover, the algorithms are simple and often efficient to implement. As a major application, we present a novel algorithm for multi-armed bandits that achieves the "best-of-all-worlds" empirical performance in the stochastic, adversarial, and non-stationary environments. And we illustrate how these principles can be used in linear bandits, bandit convex optimization, and reinforcement learning.

Due to numerous applications in retail and (online) advertising the problem of assortment selection has been widely studied under many combinations of discrete choice models and feasibility constraints. In many situations, however, an assortment of products has to be constructed gradually and without accurate knowledge of all possible alternatives; in such cases, existing offline approaches become inapplicable. We consider a stochastic variant of the assortment selection problem, where the parameters that determine the revenue and (relative) demand of each item are jointly drawn from some known item-specific distribution. The items are observed sequentially in an arbitrary and unknown order; upon observing the realized parameters of each item, the decision-maker decides irrevocably whether to include it in the constructed assortment, or forfeit it forever. The objective is to maximize the expected total revenue of the constructed assortment, relative to that of an offline algorithm which foresees all the parameter realizations and computes the optimal assortment. We provide simple threshold-based online policies for the unconstrained and cardinality-constrained versions of the problem under a natural class of substitutable choice models; as we show, our policies are (worst-case) optimal under the celebrated Multinomial Logit choice model. We extend our results to the case of knapsack constraints and discuss interesting connections to the Prophet Inequality problem, which is already subsumed by our setting.