PaperlayerView exact revision on arXiv

Source-linked AI summary

MNL-Bandit: A Dynamic Learning Approach to Assortment Selection

Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, Assaf Zeevi

arXiv:1706.03880v2cs.LG

TL;DR

The paper studies how to learn unknown MNL choice parameters while selecting revenue-maximizing assortments over time. It proposes an online, adaptive exploration-exploitation policy based on unbiased sampling and optimistic assortment selection, with regret guarantees that do not depend on separability and are near-optimal relative to a matching lower bound. Its scope is limited by the setting assumptions, including that every product is subject to the considered availability framework.

  • Problem

    Retailers must learn unknown MNL choice parameters while maximizing cumulative revenue from dynamically selected assortments.

  • Method

    The paper develops an efficient online policy that simultaneously explores and exploits using unbiased parameter estimates and optimistic assortment selection.

  • Results

    The policy is supported by a lower-bound comparison establishing near-optimal regret performance.

  • Takeaways & Limitations

    The approach avoids prior knowledge of instance parameters and adaptively balances exploration with exploitation.

  • Takeaways & Limitations

    The paper focuses on a setting where every product satisfies the considered availability condition.

Abstract

from arXiv · show

We consider a dynamic assortment selection problem, where in every round the retailer offers a subset (assortment) of $N$ substitutable products to a consumer, who selects one of these products according to a multinomial logit (MNL) choice model. The retailer observes this choice and the objective is to dynamically learn the model parameters, while optimizing cumulative revenues over a selling horizon of length $T$. We refer to this exploration-exploitation formulation as the MNL-Bandit problem. Existing methods for this problem follow an "explore-then-exploit" approach, which estimate parameters to a desired accuracy and then, treating these estimates as if they are the correct parameter values, offers the optimal assortment based on these estimates. These approaches require certain a priori knowledge of "separability", determined by the true parameters of the underlying MNL model, and this in turn is critical in determining the length of the exploration period. (Separability refers to the distinguishability of the true optimal assortment from the other sub-optimal alternatives.) In this paper, we give an efficient algorithm that simultaneously explores and exploits, achieving performance independent of the underlying parameters. The algorithm can be implemented in a fully online manner, without knowledge of the horizon length $T$. Furthermore, the algorithm is adaptive in the sense that its performance is near-optimal in both the "well separated" case, as well as the general parameter setting where this separation need not hold.

1. Introduction

The paper studies dynamic assortment selection under MNL choice, where retailers must learn preferences while maximizing revenue. It replaces parameter-dependent explore-then-exploit methods with an online policy that balances exploration and exploitation without prior instance knowledge.

  • Problem: The MNL-Bandit problem requires selecting assortments over time while learning consumer preferences and maximizing cumulative expected revenue.The retailer observes choices from substitutable products and seeks low regret relative to an oracle knowing the instance parameters.
  • Prior approaches: Existing methods explore predetermined assortments until parameter estimates reach a target accuracy, then exploit the estimated optimal assortment.Their exploration duration depends on prior knowledge of the separation between the optimal and second-best assortments.
  • Contribution: The proposed approach simultaneously explores and exploits without requiring a priori knowledge or assumptions about instance parameters.It adaptively selects assortments using observed demand information, making the approach broader in scope.
  • Technical challenge: The policy addresses the combinatorial assortment space, where treating every assortment as a separate bandit arm would create exponentially many arms.Standard linear and generalized linear bandit formulations do not apply directly because assortment revenue is nonlinear in the model parameters.
  • Results: The algorithm achieves a worst-case regret bound of O(√NT log NT) under a mild assumption and remains bounded across varying separability levels.For some separability values, the explore-then-exploit approach can incur linear regret, whereas the proposed algorithm is reported to have sub-linear performance.
  • Results: The paper establishes a non-asymptotic lower bound of Ω(√NT/K) for cardinality-constrained MNL-Bandit instances.Here K bounds the number of products that can be offered in an assortment, and the upper bound is reported to be within a factor of the lower bound.

2. Problem formulation

The problem is to design history-dependent assortment decisions under an MNL choice model when product attraction parameters are unknown. The policy should maximize cumulative expected revenue, or equivalently minimize regret relative to the optimal assortment.

  • Decision process: At each time t, the seller selects an assortment St and observes whether the consumer purchases a product or chooses no purchase.The no-purchase alternative is always available.
  • Choice model: Consumer choices follow an MNL model with attraction parameters vi that are unknown to the seller.Choices are conditionally independent over time given the offered assortment, and v0 is normalized to 1 for no purchase.
  • Objective and constraints: The seller chooses a sequence of feasible assortments S1,...,ST to maximize cumulative expected revenue over the planning horizon.Feasibility can include cardinality, partition matroid, joint display-assortment, and more general totally unimodular constraints.
  • Performance measure: Regret measures the gap between the policy’s performance and that of an oracle that knows the instance parameters and offers the optimal assortment.The optimal assortment is the revenue-maximizing feasible assortment under the true MNL parameters.

3. The proposed policy

The proposed policy extends upper-confidence-bound learning to MNL assortment selection by exploiting the model’s dependence structure. It uses repeated offers, unbiased parameter estimates, and optimistic revenue maximization to adapt exploration and exploitation online.

  • Challenges and overview: Standard bandit methods cannot treat products as independent arms because a consumer’s response depends on the entire offered assortment.The policy therefore uses the dependence structure of the MNL model to construct an efficient algorithm.
  • Challenges and overview: The policy repeatedly offers an assortment until no purchase occurs, making the average number of purchases of each product an unbiased estimate of its MNL parameter.This sampling procedure addresses the lack of a direct unbiased product-demand observation from a single assortment offer.
  • Policy design: The algorithm maintains upper confidence bounds for product attraction parameters and selects the feasible assortment with the highest optimistic revenue.MNL structure makes the optimistic assortment computable through a static assortment optimization problem rather than enumerating all assortments.
  • Policy design: Epochs end after a no-purchase outcome, after which the algorithm updates product statistics and chooses the next assortment using the updated estimates.The epoch length is random because it depends on the no-purchase probability of the offered assortment.
  • Universality: The algorithm does not require prior knowledge of the problem parameters beyond an initial boundedness assumption, unlike prior separation-gap methods.It adaptively offers assortments based on observed choices rather than forcing exploration of a predetermined set.
  • Estimation approach: The sampling-based confidence bounds avoid the finite-time and unknown-parameter issues associated with standard maximum-likelihood confidence regions.The method uses unbiased estimates and simple bookkeeping to obtain parameter-independent confidence regions.

4. Main results

The paper analyzes an online optimistic algorithm under explicit MNL and assortment-family assumptions, proving parameter-independent regret bounds through unbiased estimates and upper confidence bounds. Its analysis shows these estimates converge and supports the algorithm's revenue guarantees.

  • Assumptions: The analysis assumes vi ≤ v0 = 1 and a downward-closed feasible assortment family.The first assumption means no purchase is most likely; removing products preserves feasibility, covering cardinality and matroid constraints.
  • Main guarantee: Theorem 1 gives Algorithm 1 a regret bound with absolute constants independent of problem parameters.The stated bound contains terms involving N, T, and logarithmic factors.
  • Proof outline: The algorithm constructs independent unbiased product-parameter estimates by repeatedly offering an assortment until no purchase occurs.These estimates are geometric with mean vi, enabling multiplicative concentration bounds.
  • Optimistic selection: At each epoch, Algorithm 1 uses upper confidence bounds to choose the feasible assortment with the highest estimated revenue.The estimated revenue is an upper confidence bound on the optimal expected revenue with high probability.
  • Regret analysis: The regret analysis combines optimistic revenue estimates with convergence of product estimates and a Lipschitz bound on revenue differences.The resulting loss is controlled through individual parameter-estimation errors.
  • Scope: The paper clarifies that monotonicity applies to the optimal expected-revenue value, not to the expected-revenue function for every assortment.The first assumption is described as simplifying presentation rather than being central to deriving regret bounds.

5. Lower bounds and near-optimality of the proposed policy

The paper establishes lower bounds for MNL-Bandit learning and uses them to assess the proposed policy's near-optimality. A reduction from a parametric MAB problem shows that any policy must incur nontrivial regret, while the proposed policy matches the lower-bound dependence in key settings.

  • Cardinality constraints: Under cardinality constraints, Algorithm 1 is nearly optimal when K is treated as a problem parameter.Its upper bound is within a factor of K of the lower bound, and the paper suggests optimal K-dependence when K < N/4.
  • Lower bound: Theorem 2 constructs an MNL-Bandit instance showing that every policy with assortments of size at most K must incur a lower-bound regret.The hard instance has one randomly selected group of better products and reduces the result to a parametric MAB lower bound.
  • Near-optimality: Theorem 2 establishes optimality of Algorithm 1 under the paper's stated K-dependent comparison.This conclusion follows from the lower-bound construction and the policy's corresponding regret guarantee.
  • Unconstrained setting: For the unconstrained setting K = N, the paper states that Algorithm 1 can be improved to a bound involving the optimal assortment size.The paper also states a matching lower-bound order for the unconstrained assortment problem.
  • Reduction: The lower-bound proof reduces the MNL-Bandit problem to a Bernoulli multi-armed bandit through a black-box simulation.The constructed MAB algorithm simulates assortment choices and supplies feedback with the appropriate purchase probabilities.
  • Reduction analysis: The reduction compares upper regret bounds for the simulated MAB algorithm with lower regret bounds inherited by the MNL algorithm.The proof relates the simulated horizon and the number of MNL calls to derive a contradiction if MNL regret were too small.

6. Extensions

The paper extends Algorithm 1 with improved logarithmic regret guarantees for well-separated instances and a modified policy for general MNL parameters without the no-purchase assumption.

  • 6.2. Relaxing the “no purchase” assumption: For general MNL parameters, Algorithm 3 relaxes the no-purchase assumption and retains a regret bound for all instances.The modified policy uses a small mandatory initial exploration period, then continues to explore and exploit simultaneously.
  • 6.1. Improved regret bounds for “well-separated” instances: For well-separated instances, Algorithm 1 achieves an O(log T) regret bound dependent on the separation parameter.The separation parameter is the revenue gap between the optimal and second-best assortments.
  • 6.1. Improved regret bounds for “well-separated” instances: The well-separated guarantee applies only to instances having sufficient separation between the optimal and second-best assortments.The bound is contrasted with the worst-case guarantee that holds for all instances satisfying the stated assumption.
  • 6.1. Improved regret bounds for “well-separated” instances: After each product is offered in sufficiently many good epochs, Algorithm 1 identifies an optimal assortment.The analysis bounds sub-optimal offers in good epochs by Nτ.
  • 6.1. Improved regret bounds for “well-separated” instances: Algorithm 1 offers sub-optimal assortments in at most Nτ good epochs, yielding an O(N^2 log T) regret bound.For cardinality constraints, the bound improves to O(NK log T).
  • 6.1. Improved regret bounds for “well-separated” instances: The improved bound is similar to Sauré and Zeevi’s when K is fixed and better than the O(N^2 log^2 T) bound of Rusmevichientong et al.Algorithm 1 does not require prior knowledge of the separation parameter Δ(v).
  • 6.2. Relaxing the “no purchase” assumption: Algorithm 3’s initial exploratory period is constant across problem instances and independent of instance parameters.This differs from prior approaches whose exploration periods depend on estimated separability or other instance information.

7. Computational study

The computational study evaluates Algorithm 1 across separation levels and against an explore-then-exploit method. Its regret remains sub-linear across tested instances, while the comparison method is sensitive to the exploration period and separation.

  • 7.1. Robustness of Algorithm 1: Across separation gaps ϵ = 0.05, 0.1, 0.15, and 0.25, Algorithm 1 exhibits sub-linear regret growth.The experiments use 100 independent simulations with standard errors within 2%.
  • 7.1. Robustness of Algorithm 1: As separation increases, Algorithm 1’s regret decreases, while its performance remains consistent across tested separation values.The experiments vary ϵ, where larger values represent larger separation and an easier instance.
  • 7.2. Comparison with existing approach: Against Sauré and Zeevi (2013), Algorithm 1 performs better for ϵ = 0.05, 0.1, and 0.15, while Sauré and Zeevi performs better for ϵ = 0.25.The comparison uses an exploration period of 20logT and horizon T = 10^6.
  • 7.2. Comparison with existing approach: Sauré and Zeevi identified the optimal assortment in 7%, 40%, 61%, and 97% of simulations for ϵ = 0.05, 0.1, 0.15, and 0.25, respectively.The results show sensitivity to the separation parameter and the chosen exploration period.
  • 7.3. Performance on simulated real data: On simulated real-world data, Sauré and Zeevi’s regret initially grows more slowly but then becomes linear, whereas Algorithm 1 remains sub-linear.The comparison is presented as evidence about the limitations of an explore-then-exploit approach requiring prior parameter knowledge.

8. Conclusions and future work

The paper presents an efficient policy that learns MNL choice parameters while maximizing cumulative revenue, without prior instance knowledge, and adapts its learning rate to problem separability. Future work addresses richer product-feature structure, heterogeneous consumers, and Thompson Sampling.

  • The policy simultaneously learns choice parameters and maximizes cumulative revenue in the parametric multi-arm bandit formulation.
  • The computationally efficient algorithm has nearly-optimal regret and adapts to instance complexity through item separability.
  • Its rate of learning is faster for problem instances described as less complex.
  • The current formulation estimates a separate utility parameter for every product, whereas many settings use a small number of product features.
  • A proposed extension would exploit product-feature relations to obtain regret depending on feature dimensionality rather than the number of products.
  • Other future directions include parameter-independent learning for heterogeneous consumers with low-rank structure and theoretically analyzable Thompson Sampling.

A. Proof of Theorem 1

The proof of Theorem 1 is organized into supporting lemmas whose results are combined to establish the theorem.

  • The proof completes Lemma 4.1, proves Lemmas 4.2 and 4.3, and then uses these results to complete Theorem 1.

A.1. Properties of estimates vUCB

The appendix establishes the distributional and concentration properties of the MNL parameter estimates, then uses monotonicity and optimistic estimates to support assortment analysis.

  • Distributional properties: The epoch length n_l is geometric with success probability p0(S_l), enabling moment-generating-function calculations for the estimates.The analysis derives the relevant geometric moment-generating function from the no-purchase probability.
  • Distributional properties: The estimates v_hat_i,l are i.i.d. geometric random variables with parameter 1/(1+v_i) and are unbiased for v_i.Corollary A.1 states E_pi(v_hat_i,l) = v_i for every epoch and product.
  • Concentration bounds: Geometric tails permit Chernoff-Hoeffding-style concentration bounds even though individual estimates are unbounded.The appendix notes that standard bounded-sample assumptions fail, but geometric variables have extremely small tails.
  • Revenue comparison: The analysis proves that expected revenue for the optimal assortment is monotone in the MNL parameters and bounds estimated optimal revenue against true optimal revenue.These auxiliary results support the use of optimistic parameter estimates in assortment selection.

A.3. Putting it all together: Proof of Theorem 1

The proof combines epoch-level regret decomposition, concentration events, and bounds on random epoch lengths to obtain the policy’s worst-case regret guarantee.

  • Regret decomposition: The regret analysis decomposes performance across epochs and products, with each epoch ending after a no-purchase event.Conditioned on the offered assortment, epoch length is geometric with success probability equal to the no-purchase probability.
  • Regret decomposition: The analysis separates low-probability estimation failures from the high-probability event where optimistic revenue estimates control epoch regret.The proof uses union bounds, concentration inequalities, and the monotonicity result for the optimal assortment.
  • Final bound: The resulting worst-case regret is Reg_pi(T,v) = O(sqrt(NT log NT) + N log^2 NT).This bound is obtained by maximizing the intermediate regret bound subject to the analysis constraints.

A.4. Improved regret bounds for the unconstrained MNL-Bandit

For the unconstrained problem, the proof shows that the algorithm concentrates on products in the optimal assortment and derives a sharper regret bound based on its size.

  • Optimal-assortment structure: With high probability, the assortment selected in each epoch is a subset of the optimal assortment in the unconstrained case.This follows because products can be added or removed whenever doing so improves expected revenue.
  • Improved regret bound: The sharper analysis replaces the ambient product count N with the optimal-assortment size |S*| in the leading term.The appendix explicitly notes that the proof can be followed with N replaced by |S*|.
  • Improved regret bound: The unconstrained-case bound has the form |S*|T log NT + C2N log NT.The displayed bound is stated for instances satisfying r_i in [0,1] and v0 >= v_i.

B. Proof of Theorem 4

The proof of Theorem 4 controls exploratory epochs, establishes valid upper confidence bounds, and combines these ingredients to derive regret under bounded parameter ratios.

  • Exploratory epochs: Exploratory epochs are those in which at least one offered product has been offered fewer than the required number of times.Their number is bounded by 48N log NT, after which every product has received sufficient exploratory exposure.
  • Exploratory epochs: Epoch lengths during exploration are geometric, allowing the proof to bound the expected duration and regret of the exploratory phase.Under v_i <= Bv0, the conditional expectation of an epoch length is bounded using a success probability at least 1/(B|S_l| + 1).
  • Final bound: Under v_i <= Bv0, the worst-case regret is O(sqrt(BNT log NT) + N log^2 NT + BN log NT).The bound is obtained by combining exploration, concentration, and optimistic-assortment analyses.
  • Confidence intervals: The updated upper confidence bounds satisfy vUCB2_i,l >= v_i with probability at least 1 - 6/N_l for every product.Additional concentration results establish convergence rates for the confidence intervals and optimistic revenue estimates.

C. Improved regret bounds for “well separated” instances

The appendix develops improved regret bounds for well-separated instances through an inductive analysis of sub-optimal assortments and supporting concentration arguments. It bounds how often products or assortments violate the relevant conditions and uses these bounds to control cumulative regret.

  • Inductive regret analysis: The proof bounds the number of good epochs offering sub-optimal products by Nτ.The induction assumes the bound for up to M products and extends it to M + 1 products.
  • Resulting bound: Corollary C.1 bounds the number of epochs offering a product that does not satisfy the condition by O(N log NT).This corollary is obtained by following the proof of Lemma 6.2.
  • Inductive regret analysis: The analysis separates regret from good and bad epochs, bounding bad epochs probabilistically and sub-optimal assortments among good epochs.The proof uses Lemma 4.1 for bad epochs and Lemma 6.2 for good epochs offering sub-optimal assortments.
  • Concentration analysis: The concentration analysis derives bounds for geometric random variables using Markov’s inequality, Taylor expansions, and separate cases for μ below or above one.The proof treats both one-sided inequalities and distinguishes μ ∈ (0,1) from μ ≥ 1.
  • Concentration analysis: The appendix adapts prior results to obtain sharper bounds for the estimates used in the analysis.It specifically adapts a corollary from Babaioff et al. and Kleinberg et al.

E.1. Lower Bound for the unconstrained MNL-Bandit problem (K = N)

This section establishes a lower bound for the unconstrained MNL-Bandit problem by constructing two nearby instances whose optimal assortments differ. Distinguishing them requires many observations, forcing regret while the algorithm learns which instance it faces.

  • Hard instance: The optimal assortment is either {1} or {1,2}, depending on the parameter value.The construction also shows that adding products i ≥ 3 outside the assortment lowers revenue in the stated setting.
  • Information requirement: Approximately 1/ϵ^2 observations are needed to distinguish the two parameter values with high probability.The lower-bound intuition then associates each of these observations with regret of order ϵ.
  • Formal proof: The proof compares the distributions of observed consumer choices under the two instances using KL divergence and Pinsker’s inequality.It applies the chain rule for KL divergence to the feedback sequence generated by an adaptive algorithm.
Loading 1706.03880v2…