Optimal Exploration of New Products under Assortment Decisions

1. Problem Definition

The paper addresses the problem of online assortment optimization for a platform (e.g., Amazon, Airbnb) that must decide which products to display to customers under a capacity constraint (e.g., only $c$ items can be shown on a search result page).

• Context: The platform manages two types of products:
  • Incumbents: Existing products with known quality (attraction parameters).
  • Entrants: New products with unknown quality.
• Learning Mechanism (Social Learning): Quality information is not known a priori. It is revealed only when a customer purchases an entrant and leaves a review. This creates a feedback loop: to learn about a new product, the platform must "explore" by including it in the assortment.
• The Trade-off:
  • Exploration: Including an entrant generates reviews (learning) but displaces known high-revenue incumbents, causing short-term revenue loss.
  • Exploitation: Showing only known incumbents maximizes immediate revenue but prevents the discovery of potentially superior new products.
• Objective: Minimize regret, defined as the cumulative revenue loss relative to an oracle that knows all product qualities from the start. The setting is an infinite horizon with a Multinomial Logit (MNL) choice model.

2. Methodology and Model

The authors formalize the problem using a sequential decision-making framework:

• Choice Model: Customers choose items based on the Multinomial Logit (MNL) model. The probability of choosing item $i$ from assortment $S$ is $P(i|S) = \frac{w_i}{\sum_{j \in S} w_j + w_0}$, where $w_i$ is the attraction parameter and $w_0$ is the outside option.
• Information State:
  • For incumbents, $w_i$ is known.
  • For entrants, $w_i$ is drawn from a known prior distribution $F$. Before purchase, the platform and customers use a nominal value $h(F)$ (e.g., the mean).
  • Upon purchase, the true $w_i$ is revealed perfectly (noiseless learning assumption).
• Regret Metric: The paper focuses on infinite-horizon regret. Since the horizon is infinite, the platform must eventually explore all entrants to reach the optimal steady state. The goal is to minimize the transient regret incurred during the learning phase.

3. Key Contributions and Results

A. Optimal Policy for a Single Entrant

The paper first analyzes the case of one unknown entrant and multiple incumbents.

• Question: Should the platform offer the entrant alone (maximizing its purchase probability) or alongside top incumbents (maximizing revenue but lowering purchase probability)?
• Result: It is always optimal to pair the new entrant with the $c-1$ most attractive incumbents.
• Intuition: While pairing reduces the immediate probability of the entrant being purchased, it maximizes the revenue generated during the "exploration period" (the time until the entrant is bought). Due to the specific properties of the MNL model (Independence of Irrelevant Alternatives), the expected time to purchase the entrant scales linearly with the sum of attraction parameters of the other items. The revenue gain from including top incumbents outweighs the delay in learning.

B. Optimal Policy for Multiple Entrants (The EFA Algorithm)

The authors generalize the solution to multiple entrants, introducing the Exploration with Fictitious Assortments (EFA) algorithm.

• Core Insight: The optimal number of entrants ($\ell$) to explore simultaneously is determined by a threshold rule.
• Algorithm Logic:
  1. Calculate the Expected Ex-Post Optimum ($OPT_t$): The expected revenue if all unknown parameters were revealed.
  2. Construct Fictitious Assortments: Create hypothetical assortments of known products where the $k$-th best known product is replicated to fill the capacity. Calculate the revenue $\alpha_t(\ell)$ of these assortments.
  3. Decision Rule: If $OPT_t > \text{Revenue of myopic assortment}$, explore. The optimal number of entrants $\ell$ is the largest integer such that the expected future gain ($OPT_t$) exceeds the revenue of the fictitious assortment $\alpha_t(\ell)$.
• Structure: The optimal policy displays $\ell$ unknown entrants alongside the $c-\ell$ most attractive known products.
• Surprising Finding: The optimal number of entrants to explore simultaneously depends on the potential value of the entrants (the prior distribution) but does not depend on their individual nominal purchase probabilities in the way standard heuristics might suggest.

C. Failure of Canonical Bandit Algorithms

The paper demonstrates that standard Multi-Armed Bandit (MAB) algorithms fail in this specific assortment setting:

• UCB (Upper Confidence Bound): Tends to over-explore. It includes too many entrants simultaneously, displacing too many high-revenue incumbents, leading to arbitrarily high regret.
• Thompson Sampling (TS): Tends to under-explore. It often selects assortments with too few entrants (or none) because the sampled parameters do not trigger the "explore" condition often enough, leading to arbitrarily high regret.
• Reason for Failure: These algorithms are designed for the "explore vs. exploit" trade-off (deciding whether to explore). This problem requires optimizing how to explore (structuring the assortment to balance learning speed and revenue loss), a dimension standard bandit algorithms ignore.

D. Extensions

The authors extend their results to more complex settings:

1. Heterogeneous Rewards: When products have different prices/rewards, the optimal policy (HEFA) selects incumbents based on "scaled interim regret" rather than raw attraction parameters.
2. Heterogeneous Priors: When entrants have different prior distributions, the optimal policy depends on a complex interaction between the priors, not just a simple ordering.
3. Noisy Observations: Even when a single purchase does not reveal the true parameter perfectly (noisy learning), the structural result holds: it remains optimal to pair the entrant with the top incumbents.

4. Significance and Implications

• Theoretical Contribution: The paper bridges the gap between Assortment Optimization and Online Learning. It proves that the optimal exploration strategy in a constrained assortment setting has a clean, structural characterization that differs fundamentally from classical bandit solutions.
• Practical Guidance:
  • Platforms should not isolate new products to maximize their visibility. Instead, they should bundle new products with the platform's best-selling items.
  • Platforms should use a threshold-based rule to determine how many new products to test simultaneously, rather than testing them one by one or all at once.
  • Off-the-shelf bandit algorithms (UCB, TS) are likely suboptimal for assortment decisions and require structural modification.
• Methodological Innovation: The use of "fictitious assortments" and the decomposition of regret into "epochs" (periods between learning events) provides a novel analytical framework for problems where learning is driven by the selection of a subset of items rather than a single item.

In summary, the paper provides a rigorous mathematical foundation for how online marketplaces should structure their product listings to efficiently learn about new items while minimizing revenue loss, offering clear, actionable policies that outperform standard machine learning heuristics.