We consider a generalization of the classical newsvendor problem to a multi-location setting. A seller determines the initial inventory of a product across multiple locations on a metric. Then, the seller decides a fulfillment policy to satisfy uncertain demand that realizes sequentially over time. The goal is to minimize the expected inventory and shipping costs. To address the distributional ambiguity, we consider a distributionally robust model where only the mean and variance of the demand are known and the goal is to minimize costs under the worst-case realization of the demand distribution.

In a recent work, Laforgue et al. introduce the model of last switch dependent (LSD) bandits, in an attempt to capture nonstationary phenomena induced by the interaction between the player and the environment. Examples include satiation, where consecutive plays of the same action lead to decreased performance, or deprivation, where the payoff of an action increases after an interval of inactivity. In this work, we take a step towards understanding the approximability of planning LSD bandits, namely, the (NP-hard) problem of computing an optimal arm-pulling strategy under complete knowledge of the model. In particular, we design the first efficient constant approximation algorithm for the problem and show that, under a natural monotonicity assumption on the payoffs, its approximation guarantee (almost) matches the state-of-the-art for the special and well-studied class of recharging bandits (also known as delay-dependent). In this attempt, we develop new tools and insights for this class of problems, including a novel higher-dimensional relaxation and the technique of mirroring the evolution of virtual states. We believe that these novel elements could potentially be used for approaching richer classes of action-induced nonstationary bandits (e.g., special instances of restless bandits). In the case where the model parameters are initially unknown, we develop an online learning adaptation of our algorithm for which we provide sublinear regret guarantees against its full-information counterpart.

We consider dynamic multi-product pricing and assortment problems under an unknown demand over T periods, where in each period, the seller decides on the price for each product or the assortment of products to offer to a customer who chooses according to an unknown Multinomial Logit Model (MNL). Such problems arise in many applications, including online retail and advertising. We propose a randomized dynamic pricing policy based on a variant of the Online Newton Step algorithm (ONS) that achieves a $O(d\sqrt{T}\log(T))$ regret guarantee under an adversarial arrival model. We also present a new optimistic algorithm for the adversarial MNL contextual bandits problem, which achieves a better dependency than the state-of-the-art algorithms in a problem-dependent constant $\kappa$ (potentially exponentially small). Our regret upper bound scales as $\tilde{O}(d\sqrt{\kappa T}+ \log(T)/\kappa)$, which gives a stronger bound than the existing $\tilde{O}(d\sqrt{T}/\kappa)$ guarantees.

In this paper, we study a dynamic assortment optimization problem under bandit feedback, where a seller with a fixed initial inventory of N substitutable products faces a sequence of i.i.d. customer arrivals (with an unknown distribution) over a time horizon of T periods, and needs to decide in each period on an assortment of products to offer to the customer to maximize the total expected revenue. Such a problem arises in many applications including online retail and recommendations. The seller has initially no (or only limited) information about the customer's preferences and needs to learn them through repeated interaction with the i.i.d. customers. Specifically, in each period, the seller offers an assortment to the customer; the customer makes a choice from the assortment according to the unknown preferences or choice model, and the seller only observes the eventual choice from the given assortment and needs to update the estimate and future actions under this bandit feedback. Therefore, this problem exemplifies the classical trade-off between exploitation and exploration: the seller needs to simultaneously gain information about the customer's preferences and offer revenue-maximizing assortments, while respecting the resource constraints.

In the paper “Online Matching with Stochastic Rewards: Optimal Competitive Ratio via Path-Based Formulation,” the authors develop a novel algorithm analysis approach to address stochastic elements in online matching. The approach leads to several new results that were previously out of reach for a fundamental generalization of online matching. More generally, the approach is useful for analyzing the performance of online algorithms for matching in settings with stochastic uncertainty that manifests after matching decisions are made.

One of the central challenges in online advertising is attribution, namely, assessing the contribution of individual advertiser actions including emails, display ads and search ads to eventual conversion. Several heuristics are used for attribution in practice; however, there is no formal justification for them and many of these fail even in simple canonical settings. The main contribution in this work is to develop an axiomatic framework for attribution in online advertising. In particular, we consider a Markovian model for the user journey through the conversion funnel, in which ad actions may have disparate impacts at different stages. We propose a novel attribution metric, that we refer to as counterfactual adjusted Shapley value, which inherits the desirable properties of the traditional Shapley value. Furthermore, we establish that this metric coincides with an adjusted “unique-uniform” attribution scheme. This scheme is efficiently computable and implementable and can be interpreted as a correction to the commonly used uniform attribution scheme.

We consider a sequential subset selection problem under parameter uncertainty, where at each time step, the decision maker selects a subset of cardinality $K$ from $N$ possible items (arms), and observes a (bandit) feedback in the form of the index of one of the items in said subset, or none. Each item in the index set is ascribed a certain value (reward), and the feedback 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 parameters. We refer to this as the MNL-Bandit problem. This problem is representative of a larger family of exploration-exploitation problems that involve a combinatorial objective, and arise in several important application domains. We present an approach to adapt Thompson Sampling to this problem and show that it achieves near-optimal regret as well as attractive numerical performance.

Affine policies (or control) are widely used as a solution approach in dynamic optimization where computing an optimal adjustable solution is usually intractable. While the worst case performance of affine policies can be significantly bad, the empirical performance is observed to be near-optimal for a large class of problem instances. For instance, in the two-stage dynamic robust optimization problem with linear covering constraints and uncertain right hand side, the worst-case approximation bound for affine policies is $O(\sqrt m)$ that is also tight (see Bertsimas and Goyal (2012)), whereas observed empirical performance is near-optimal. In this paper, we aim to address this stark-contrast between the worst-case and the empirical performance of affine policies. In particular, we show that affine policies give a good approximation for the two-stage adjustable robust optimization problem with high probability on random instances where the constraint coefficients are generated i.i.d. from a large class of distributions; thereby, providing a theoretical justification of the observed empirical performance. On the other hand, we also present a distribution such that the performance bound for affine policies on instances generated according to that distribution is $\Omega(\sqrt m)$ with high probability; however, the constraint coefficients are not i.i.d.. This demonstrates that the empirical performance of affine policies can depend on the generative model for instances.

We consider the assortment optimization problem when customer preferences follow a mixture of Mallows distributions. The assortment optimization problem focuses on determining the revenue/profit maximizing subset of products from a large universe of products; it is an important decision that is commonly faced by retailers in determining what to offer their customers. There are two key challenges: (a) the Mallows distribution lacks a closed-form expression (and requires summing an exponential number of terms) to compute the choice probability and, hence, the expected revenue/profit per customer; and (b) finding the best subset may require an exhaustive search. Our key contributions are an efficiently computable closed-form expression for the choice probability under the Mallows model and a compact mixed integer linear program (MIP) formulation for the assortment problem.

We consider an online assortment optimization problem, where in every round, the retailer offers a K-cardinality subset (assortment) of N substitutable products to a consumer, and observes the response. We model consumer choice behavior using the widely used multinomial logit (MNL) model, and consider the retailer's problem of dynamically learning the model parameters, while optimizing cumulative revenues over the selling horizon T. Formulating this as a variant of a multi-armed bandit problem, we present an algorithm based on the principle of "optimism in the face of uncertainty." A naive MAB formulation would treat each of the N choose K possible assortments as a distinct "arm", leading to regret bounds that are exponential in K. We show that by exploiting the specific characteristics of the MNL model it is possible to design an algorithm with Õ(√NT) regret, under a mild assumption. We demonstrate that this performance is nearly optimal, by providing a (randomized) instance of this problem on which any online algorithm would incur at least ΩOmega(√NT/K) regret.

Assortment planning is an important problem that arises in many industries such as retailing and airlines where one of the key challenges is to identify the "right model" for the consumer preferences and substitution behavior. Distribution over preference lists or permutations is the most general framework for modeling preferences but is intractable in general. In this paper, we present a parsimonious distribution over permutations model that is induced by random swaps from a central preference list (which we also refer to as the prototype list. In particular, a random list from this distribution can be sampled as follows: sample N from a given distribution on the number of swaps and starting from the initial prototype list, perform N random swaps. A random swap operation consists of selecting a random pair of items in the current list and swapping their positions. We consider two types of random swaps: i) swapping an arbitrary pair of items, and $ii)$ swapping an adjacent pair of items. More precisely, a pair is picked uniformly at random out of all n+1\choose 2 possible pairs in i), and out all all $n$ pairs of adjacent items in ii). If the distribution over the number of swaps has sufficient large support, the distribution over permutations has non-zero probability on all preference lists. This model is motivated by practical applications where consumers preferences generally have many common items appear according to the same relative order and differ only in a small number of items. The prototype list used to generate a random preference list can intuitively be thought of as the mode of the distribution implied by the random swap model. This model also captures the well known Mallows distribution over permutation that is specified by a model permutation and a concentration parameter that determines how the probability of permutations decrease as a function of the distance from the modal permutation. Therefore, this is a fairly general model for consumer preferences. This model is motivated by practical applications where consumer preference are more or less similar over most items and differ in the relative order of only a few items.

Assortment planning is an important problem that arises in many industries such as retailing and airlines. One of the key challenges in an assortment planning problem is to identify the "right model" for the substitution behavior of customers from the data. Error in model selection can lead to highly sub-optimal decisions. In this paper, we present a new choice model that is a simultaneous approximation for all random utility based discrete choice models including the multinomial logit, the nested logit and mixtures of multinomial logit models. Our model is based on a new primitive for substitution behavior where substitution from one product to another is modeled as a state transition of a Markov chain. In particular, we consider a Markov chain where there is a state for each product, and model the substitution behavior as follows: a customer arrives in the state corresponding to his most preferred product. If that product is not available, he/she transitions to other product states according to the transition probabilities of the Markov chain. Therefore, the preferences of the customers are approximated by Markovian transitions in this choice model.

Robust optimization has traditionally focused on uncertainty in data and costs in optimization problems to formulate models whose solutions will be optimal in the worst-case among the various uncertain scenarios in the model. While these approaches may be thought of defining data- or cost-robust problems, we formulate a new "demand-robust" model motivated by recent work on two-stage stochastic optimization problems. We propose this in the framework of general covering problems and prove a general structural lemma about special types of first-stage solutions for such problems: there exists a first-stage solution that is a minimal feasible solution for the union of the demands for some subset of the scenarios and its objective function value is no more than twice the optimal. We then provide approximation algorithms for a variety of standard discrete covering problems in this setting, including minimum cut, minimum multi-cut, shortest paths, Steiner trees, vertex cover and un-capacitated facility location. While many of our results draw from rounding approaches recently developed for stochastic programming problems, we also show new applications of old metric rounding techniques for cut problems in this demand-robust setting.