The objective of the award is to develop effective algorithms for high-dimensional complex stochastic optimization problems involving large structured decision sets and high-volume data streams, with applications to revenue management, dynamic pricing, and resource allocations.  

Intellectual Merits:  During the lifetime of the award, we have developed many innovative algorithms and solution methods for the structured multiarmed bandit problems, dynamic assortment optimization, and the d-level nested logit model.  We will briefly describe each problem and discuss our contributions in each area.

Motivated by applications in online advertising, we consider the structured multiarmed bandit problem where the expected payoff of each decision is unknown a priori, and we only observe noisy samples of the reward.    We assume that the mean reward of each decision is a linear function of the decision’s attributes.  For example, if each decision corresponds to an advertisement to be shown to the user, the attributes of the ad might correspond to its content, popularity, or user ratings.    Our goal is to develop an algorithm for choosing a sequence of decisions that maximizes the total expected reward.  Since the mean reward of each decision is unknown, we need to simultaneously estimate the reward of the arms and choose the best decision based on the available information.  In this ``learning and earning’’ environment, we develop a method that achieves the best possible reward, and they have been applied to problems in online advertising and dynamic assortment optimization.  The results are published in IEEE Transaction on Automatic Control, Mathematics of Operations Research, and Operations Research.

In the dynamic assortment optimization, we consider the problem of real-time optimization of personalized assortments.  This problem is motivated by the availability of real-time data on customer characteristics, we consider the problem of personalizing the assortment of products to each arriving customer. Through actual sales data from an online retailer, we demonstrate that personalization based on each customer's location can lead to over 10% improvements in revenue, compared to a policy that treats all customers the same.  We propose a family of simple and effective algorithms, called Inventory-Balancing, for real-time personalized assortment optimization, that do not require any forecasting: An Inventory-Balancing algorithm, maintains a "discounted-revenue index" for each product, in which the (actual) revenue is multiplied by a (virtual) discount factor that depends on the fraction of the product's remaining inventory. Upon an arrival of each customer, based on the customer's type, the algorithm offers to her the assortment that maximizes the expected discounted revenue.   In addition to personalization, we have also considered the assortment packing problem in which a firm must decide, in advance, the release date of each product in a given collection over a selling season. This problem is motivated by retailers' frequent introduction of new items to refresh product lines and maintain their market share. Our formulation models the trade-offs among profit margins, preference weights, and limited life cycles.  These works result in 2 papers that have been published in Management Science.

Finally, we consider the assortment and price optimization problems under the d-level nested logit model.  We provide a new formulation of the d-level nested logit model using a tree of depth d. Our formulation enables us to study two canonical revenue management problems under this model: finding the optimal assortment assuming fixed prices, and determini...

Please report errors in award information by writing to: awardsearch@nsf.gov.