📊 statistics

Data-Driven Dynamic Assortment in Online Platforms: Learning about Two Sides

This paper introduces a data-driven algorithm for a two-sided dynamic assortment problem with unknown choice parameters on both sides, achieving rate-optimal polylogarithmic regret by simultaneously learning customer and seller preferences while maximizing platform revenue.

Original authors: Rahul Roy, Nur Sunar, Jayashankar M. Swaminathan

Published 2026-06-10

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Rahul Roy, Nur Sunar, Jayashankar M. Swaminathan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are running a bustling digital marketplace, like a high-tech version of a farmers' market or a dating app. You have two groups of people: Customers (who want to buy services) and Sellers (who want to provide them). Your job is to decide which Sellers to show to each Customer who walks through the door.

This paper tackles a very tricky problem: You don't know what anyone likes.

The Core Problem: The "Blind Date" Marketplace

In most online platforms, the system tries to guess what customers want. But in this paper's scenario, the platform is blind in two ways:

It doesn't know what Customers want: Some customers love solar installers; others prefer freelance writers. The platform doesn't know which type of customer is arriving next.
It doesn't know what Sellers want: Even if a customer picks a seller, that seller might say "No thanks." Maybe the seller hates working with that specific type of customer. The platform doesn't know these preferences either.

It's like a blind date setup where the matchmaker doesn't know what the guy likes, and doesn't know what the girl likes. If the guy picks the girl, she might still reject him. If the matchmaker only learns what the guy likes but ignores what the girl likes, they will keep setting up bad dates.

The Cycle of Events

The paper describes a specific rhythm to how this marketplace works:

The Arrival: A customer arrives.
The Menu: The platform shows them a small list (an "assortment") of sellers.
The Proposal: The customer picks one seller from the list (or none).
The Review: The seller gets a batch of proposals. Every few days (a "cycle"), the seller reviews them and picks at most one customer to work with.
The Reward: The platform only gets paid (or gets a "match") if both the customer picked the seller AND the seller picked the customer.

The Challenge: Learning While Doing

The platform manager has to make decisions now without knowing the future. They have to figure out:

"Which sellers does Customer Type A like?"
"Which customer types does Seller Type B accept?"

If the platform just keeps showing the same popular sellers, it never learns if a new seller is actually a great match for a specific customer type. But if it shows too many random sellers, it wastes time and money on bad matches. This is the classic "Exploration vs. Exploitation" dilemma.

The Solution: The "Two-Way Learning" Algorithm

The authors created a smart computer program (an algorithm) called TWL-UCB. Think of it as a super-observant matchmaker who keeps a "confidence score" for every possible pairing.

The Guessing Game: The algorithm starts by guessing how much customers and sellers like each other.
The "What If" Test: It uses a mathematical trick called "Upper Confidence Bound" (UCB). Imagine the algorithm is playing it safe but also taking calculated risks. It thinks: "I'm 90% sure Customer A likes Seller X, but I'm only 50% sure about Seller Y. Let's try Seller Y just to see, because if I'm right, it could be a huge win!"
Double-Checking: Unlike older methods that only watched what customers did, this algorithm watches both sides.
- It updates its guess about what customers like every time a customer makes a choice.
- It updates its guess about what sellers like every time a seller accepts or rejects a proposal.
The Result: Over time, the algorithm gets incredibly good at predicting the perfect match, minimizing the number of failed dates (regret).

The Big Discoveries

The paper proves three main things using math and computer simulations:

1. It Gets Better Fast (The "Polylogarithmic" Win)
The authors proved that their algorithm learns so efficiently that the "mistakes" it makes grow very slowly over time. In math terms, the error grows like the square of a logarithm (a very slow curve).

Analogy: Imagine a student taking a test. Most learning methods make mistakes that pile up like a steep hill. This algorithm makes mistakes that pile up like a gentle slope. It learns the rules of the game much faster than anyone else.

2. You Can't Do Much Better (The "Lower Bound")
The authors also proved that no other possible strategy could learn significantly faster than theirs. They showed that even a "perfect" algorithm would still make a similar number of mistakes in the worst-case scenario.

Analogy: They proved that their algorithm is the "Gold Medalist." You can't win a faster race because the track itself is that fast.

3. Bigger Isn't Always Better (The "Menu Size" Surprise)
They ran simulations to see what happens if the platform shows a huge list of sellers (a big menu) versus a small list.

The Finding: Once the menu gets to a certain size (around 30 sellers in their simulation), making it bigger doesn't help much.
Analogy: Think of a restaurant menu. If you have 5 great dishes, adding 50 more mediocre dishes doesn't make the customer happier; it just confuses them. The platform gets the same number of successful matches with a medium-sized menu as it does with a massive one.

Why This Matters

This paper is the first to solve the puzzle of learning both sides of a marketplace simultaneously when you don't know what either side wants. It shows that by treating the problem as a "two-way" learning challenge rather than just a "customer-choice" challenge, platforms can make much smarter, faster, and more profitable decisions.

In short: To run a successful two-sided marketplace, you can't just guess what the buyer wants; you have to learn what the seller wants, too. And if you do both at the same time with the right math, you win.

Technical Summary: Data-Driven Dynamic Assortment in Online Platforms: Learning about Two Sides

Problem Formulation
The paper addresses a dynamic assortment selection problem on a two-sided service platform operating under incomplete information. Unlike traditional assortment problems where a decision-maker selects products to maximize revenue based solely on customer preferences, this setting involves "active" participants on both the demand (customers) and supply (sellers) sides.

The system operates in discrete time over a horizon of $T$ periods. The platform manages a set of $N$ sellers and encounters a sequence of arriving customers with heterogeneous types. In each period, the platform manager selects an assortment (a subset of sellers of size at most $B$ ) to display to an arriving customer. The customer then chooses at most one seller from the displayed assortment according to a Multinomial Logit (MNL) choice model, governed by unknown preference parameters $v_{z,i}$ (where $z$ is the customer type and $i$ is the seller).

Crucially, a transaction is not finalized upon the customer's choice. Instead, the customer's proposal is held for a fixed duration of $K$ periods. At the end of each epoch (a block of $K$ periods), sellers review the proposals they have received and decide whether to accept at most one customer, based on their own unknown MNL preference parameters $u_{i,z}$ . A transaction (and subsequent reward) occurs only if a seller accepts a proposal. The platform manager's objective is to maximize the total expected reward over the planning horizon.

The core challenge is Two-Way Learning: the platform does not know the choice parameters for either customers ( $V$ ) or sellers ( $U$ ) and must learn them dynamically while simultaneously making assortment decisions. This differs from existing literature, which typically assumes one-way learning (only customer preferences are unknown) or immediate payoff realization.

Methodology
The authors propose a data-driven online algorithm named TWL-UCB (Two-Way Learning via Upper Confidence Bound). The algorithm is designed to balance exploration and exploitation while handling the asynchronous feedback structure of the two-sided market.

Upper Confidence Bound (UCB) Estimates: The algorithm maintains UCB estimates for both customer preference parameters ( $v_{z,i}$ $v_{z, i}$ ) and seller preference parameters ( $u_{i,z}$ $u_{i, z}$ ).
- Customer Updates (Step II): After every period, the platform updates customer estimates based on observed customer choices (proposals) within the offered assortments.
- Seller Updates (Step III): Seller estimates are updated only at the end of each epoch ( $K$ periods), based on observed matching decisions (acceptances/rejections) by sellers.
Assortment Optimization (Step I): In each period, the platform selects an assortment that maximizes the estimated marginal increase in expected matches. This metric, denoted as $\Delta_M$ , captures the expected gain in matches for the current epoch given the current state of proposals and the UCB estimates of both customer and seller preferences.
Regret Minimization: The performance is evaluated using regret, defined as the difference between the total reward achieved by a clairvoyant policy (which knows all parameters and arrival sequences) and the reward achieved by the proposed algorithm.

Key Results and Theoretical Contributions
The paper establishes the theoretical optimality of the TWL-UCB algorithm through matching upper and lower bounds on regret:

Upper Bound (Theorem 1): The authors prove that the worst-case regret of the TWL-UCB algorithm grows polylogarithmically with time: $O(\log^2(NT))$ . This is a significant improvement over the $\tilde{O}(\sqrt{T})$ regret bounds found in existing dynamic assortment literature that focuses on one-way learning.
Lower Bound (Theorem 2): The paper derives a matching lower bound, showing that for any admissible policy, the worst-case regret is at least $\tilde{\Omega}(\log^2(NT))$ .
Rate Optimality: The alignment of the upper and lower bounds establishes that the TWL-UCB algorithm is rate-optimal for the Two-Way Learning problem.
Simulation Findings:
- The TWL-UCB algorithm consistently outperforms adapted versions of one-way learning algorithms (specifically, the UCB algorithm from Agrawal et al., 2019) in two-sided settings. The latter fails because it cannot account for the delayed feedback and seller-side uncertainty.
- The study identifies a threshold effect regarding assortment size: increasing the maximum assortment size ( $B$ ) beyond a certain point (observed around 30 in simulations) yields diminishing returns in total platform reward.

Extensions and Robustness
The paper analyzes two extensions to demonstrate the robustness of the algorithm:

Information Transparency: The algorithm maintains its $O(\log^2(NT))$ regret bound even if the platform manager shares only partial customer-specific information with sellers (Theorem 3).
Customer-Dependent Rewards: The regret bound holds even when the reward for a successful match depends on the specific type of customer matched, rather than being a fixed value per epoch (Theorem 4).

Significance and Claims
The authors claim this is the first study to formulate and analyze a dynamic assortment problem where the decision-maker must learn the choice parameters of both sides of a two-sided market simultaneously.

The significance of the work lies in:

Novelty of the Problem: Moving beyond one-way learning to a "Two-Way Learning" framework that reflects the active nature of participants in modern service platforms (e.g., Airbnb, Upwork, HomeAdvisor).
Algorithmic Advancement: Demonstrating that polylogarithmic regret is achievable in this complex, delayed-feedback setting, whereas one-way learning problems typically suffer from square-root regret.
Practical Insight: Highlighting that algorithms designed for one-sided learning are ineffective in two-sided environments and that platform managers should be cautious about expanding assortment sizes beyond a specific threshold due to diminishing returns.

The paper concludes that the proposed TWL-UCB algorithm provides a theoretically optimal and robust solution for platform managers operating under incomplete information in two-sided markets.