In this paper we consider the dynamic assortment selection problem under an uncapacitated multinomial-logit (MNL) model. By carefully analyzing a revenue potential function, we show that a trisection based algorithm achieves an item-independent regret bound of @math , which matches information theoretical lower bounds up to iterated logarithmic terms. Our proof technique draws tools from the unimodal convex bandit literature as well as adaptive confidence parameters in minimax multi-armed bandit problems.
Motivated by the large-scale online retailing, researchers start to relax the assumption on prior knowledge of customers' choice behavior. The question of optimization of assortments has received increasing attention in both the machine learning and operations management society @cite_19 @cite_4 @cite_10 @cite_9 @cite_3 , where the mean utilities of products are unknown and have to be learnt on the fly. Motivated by fast-fashion retailing, the work by @cite_19 was the first to study dynamic assortment planning problem, which assumes that the demand for product is independent of each other. The work @cite_4 and @cite_10 incorporate choice models of MNL into dynamic assortment planning and formulate the problem into a online regret minimization problem.
@cite_4 @cite_9 @cite_3 @cite_19 @cite_10
2117923605 2493059808 2124832196 2169572553
We consider an assortment optimization problem where a retailer chooses an assortment of products that maximizes the profit subject to a capacity constraint. The demand is represented by a multinomial logit choice model. We consider both the static and dynamic optimization problems. In the static problem, we assume that the parameters of the logit model are known in advance; we then develop a simple algorithm for computing a profit-maximizing assortment based on the geometry of lines in the plane and derive structural properties of the optimal assortment. For the dynamic problem, the parameters of the logit model are unknown and must be estimated from data. By exploiting the structural properties found for the static problem, we develop an adaptive policy that learns the unknown parameters from past data and at the same time optimizes the profit. Numerical experiments based on sales data from an online retailer indicate that our policy performs well. 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 O(√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. Companies such as Zara and World Co. have recently implemented novel product development processes and supply chain architectures enabling them to make more product design and assortment decisions during the selling season, when actual demand information becomes available. How should such retail firms modify their product assortment over time in order to maximize overall profits for a given selling season? Focusing on a stylized version of this problem, we study a finite horizon multiarmed bandit model with several plays per stage and Bayesian learning. Our analysis involves the Lagrangian relaxation of weakly coupled dynamic programs (DPs), results contributing to the emerging theory of DP duality, and various approximations. It yields a closed-form dynamic index policy capturing the key exploration versus exploitation trade-off and associated suboptimality bounds. In numerical experiments its performance proves comparable to that of other closed-form heuristics described in the literature, but this policy is particularly easy to implement and interpret. This last feature enables extensions to more realistic versions of the motivating dynamic assortment problem that include implementation delays, switching costs, and demand substitution effects. We study a family of stylized assortment planning problems, where arriving customers make purchase decisions among offered products based on maximizing their utility. Given limited display capacity and no a priori information on consumers' utility, the retailer must select which subset of products to offer. By offering different assortments and observing the resulting purchase behavior, the retailer learns about consumer preferences, but this experimentation should be balanced with the goal of maximizing revenues. We develop a family of dynamic policies that judiciously balance the aforementioned trade-off between exploration and exploitation, and prove that their performance cannot be improved upon in a precise mathematical sense. One salient feature of these policies is that they “quickly” recognize, and hence limit experimentation on, strictly suboptimal products.