Your A/B Test Is Still Warming Up When the Catalog Changes Underneath It

Based on the research ofBayati, Cao and Chen, "Speed Up the Cold-Start Learning in Two-Sided Bandits with Many Arms," Management Science, 2026

That is the blunt implication of a new paper by Mohsen Bayati, Junyu Cao, and Wanning Chen in Management Science. Bandits exist to beat randomized A/B testing: rather than splitting traffic evenly for the whole run, they shift traffic toward whatever is winning as soon as they sense a signal. But at the very start, before a bandit knows anything, it has to behave like a randomized experiment anyway, that's the cold-start problem, and the data collection phase it forces is the burn-in period. The authors' finding is that when the catalog has a two-sided structure and refreshes often, burn-in is not a minor inefficiency to tolerate. It can be the entire experiment, with a naive bandit spending nearly all its traffic finding nothing before the catalog moves on.

The Burn-In Bill Scales With Everything You Don't Control

Picture a driver-rider matching policy, a set of ad creatives shown to audience segments, or a grid of new marketplace listings. A standard bandit treats each combination as its own independent arm: driver-configuration 14 with rider-segment 9 is one arm, driver-configuration 14 with rider-segment 10 is another. If one side of the catalog has d_r options and the other has d_c options, the number of arms is d_r times d_c, and burn-in needs to sample a meaningful fraction of all of them before it can tell which pairing is best. The paper shows burn-in cost scales with that full product, which explodes fast: 50 driver configurations and 50 rider segments is already 2,500 arms, far more than most teams would guess before being asked to randomize traffic across every one.

The part that makes this dangerous rather than merely inefficient is timing. Most of these catalogs don't sit still. New ad creatives rotate, new listings post, new driver-rider configurations appear as supply and demand shift by city and hour. If the experiment's time horizon is short relative to d_r × d_c, the bandit is still in forced-exploration mode, behaving exactly like a plain randomized test, when the catalog refreshes and the whole product set it was studying no longer exists. All that traffic bought nothing durable. The paper is explicit that this cost is the dominant one precisely "when there is limited experimentation time along with a large product set", which, for anyone running weekly catalog refreshes against a sprawling combinatorial space, is the normal condition, not an edge case.

Most "New" Products Are Just Points in a Matrix

The authors' fix starts from a reframing: many things that look like thousands of unrelated new products are actually two-sided products, meaning their reward can be written as one entry in a matrix whose rows are one side and whose columns are the other. The paper's own running examples make the pattern concrete: an ad campaign that pairs a user segment with a content-creator segment, a homepage pairing a headline with an image, Airbnb experiences pairing an activity with a location, Stitch Fix styling pairing a top with a pair of pants, Expedia pairing a hotel with a flight. In every case, the "product" that looks brand new and totally unknown is really just an unobserved cell in a matrix whose rows and columns you have already seen many versions of.

That reframing is what breaks the d_r × d_c burn-in. If the reward matrix has a low-rank structure, meaning the rewards for different rows and columns are driven by a much smaller number of latent features, r, where r is far smaller than either dimension, then you don't need to sample every cell to estimate the whole matrix. A relatively small, randomly sampled set of pairs is enough to fit a low-rank estimate of all the rewards at once, because what you're learning is shared structure (what kind of rider-configuration tends to work well with what kind of driver-configuration), not d_r × d_c unrelated facts. The authors build a two-phase algorithm around this: a pure-exploration phase that forces a small sample for the low-rank matrix estimate, followed by a targeted exploration-and-exploitation phase that runs a standard Upper Confidence Bound procedure, but only over the much smaller set of candidates the matrix estimate flagged as plausible winners. The expensive part of a naive bandit, proving every arm is bad one at a time, gets replaced by inference across arms instead of within each one.

Long, Short, and Ultra-Short Horizons Are Three Different Businesses

The sharpest operational contribution of the paper is that it doesn't recommend one algorithm. It characterizes three distinct regimes, defined by how the experimentation horizon T compares with the catalog's scale, and shows the right move changes in each one.

When the horizon is long relative to catalog size, the structured algorithm performs no worse than a standard bandit, and the fancy machinery buys you little you couldn't already get by waiting. When the horizon is merely short, the structured, two-phase approach strictly outperforms a standard bandit, because there's just enough time to do the cheap matrix-estimation step and then exploit the targeted set it finds. When the horizon is ultra-short, even the structured algorithm collapses toward pure forced sampling, there isn't enough time for a second phase at all, and the paper's answer is to subsample a smaller slice of the matrix and concentrate the entire procedure there, which can still beat flailing across the whole catalog.

Your testing method should depend on how long you actually get to run the experiment before refresh, not on which algorithm is trendiest.

This is a decision rule an operator can act on without reading the theorems: measure your refresh cycle against your catalog's effective row and column counts before you choose a testing method. A platform with a slow-moving catalog and a generous testing window can keep using whatever it already has. A platform with a fast-refreshing, large two-sided catalog and a short window needs the matrix-factoring step, not a better exploration schedule. And a platform where the window is so short that the catalog will be gone before any phased algorithm finishes needs to accept that it is sampling a slice of the problem, deliberately, rather than pretending it is testing the whole thing.

Where the Underlying Machinery Already Runs

None of this requires inventing new infrastructure from scratch; the component pieces already run at scale on platforms with large, fast-refreshing catalogs, even where this paper's specific matrix estimation hasn't been adopted. Uber's Experimentation Platform runs continuous, bandit-based experiments, Thompson sampling, Upper Confidence Bound, and Bayesian optimization with contextual bandits, across its driver, rider, Eats, and Freight apps, with more than 1,000 experiments live at any time, including a ranking model for the Uber Eats restaurant feed tuned via contextual bandits because a full A/B test on every candidate was too time-intensive. DoorDash built a dedicated multi-armed-bandit platform, described by its engineers in December 2025, explicitly to replace fixed-horizon A/B tests that force experimenters to "tolerate the opportunity cost... of serving traffic to suboptimal variants until the planned end date," and the team behind it frames its work around DoorDash's own "three-sided marketplace" of merchants, consumers, and dashers.

Netflix's artwork-personalization system is the clearest cold-start case: it moved to contextual bandits because a new title's optimal thumbnail can't wait for a full batch A/B test to conclude, and needs to "rapidly figure out the optimal personalized artwork selection" the moment a title launches, when nothing is yet known about it. And Spotify Research, describing a contextual-bandit system deployed to its homepage in March 2025, sits in exactly the industry the Bayati-Cao-Chen paper validates against: beyond synthetic data, the paper's own empirical test uses a real-world data set from a music streaming service, where Spotify is now running live contextual-bandit experiments to calibrate how much music versus podcasts versus audiobooks to recommend each listener in each context.

None of these companies' public writing describes adopting the specific low-rank, two-phase matrix algorithm from this paper. What their own blogs do confirm is the underlying condition the paper addresses: large catalogs, short testing windows relative to catalog size, and an explicit, acknowledged cost to treating every new item as a stranger worth studying from scratch. That is the gap the two-sided framing is built to close.

The Decision Rule

Consider a hypothetical, illustrative case: a platform launching 5,000 new driver-rider configuration pairs a week, with a testing window of a few days before the next refresh. A naive bandit treating each pairing as an independent arm would need to sample a meaningful share of those 5,000 arms just to finish burn-in, traffic spent discovering facts about configurations that will not exist by the following week. A structured, two-sided bandit instead spends a small forced sample estimating a shared low-rank model of driver effects and rider effects, narrows to a handful of promising pairings, and runs the UCB phase only on those. The number isn't from any company's reported figures; it's there to make the scaling concrete, because the mechanism, burn-in cost scaling with the full product of catalog dimensions, not with available time, is exactly what the paper proves.

The operator-level rule, then, is not "adopt bandits" or "adopt this specific algorithm." It is to first check whether your catalog has a two-sided structure at all, most matching, recommendation, and auction-style products do, and then measure your actual experimentation horizon against the scale of that structure before picking a method. Long horizon relative to catalog size: a standard bandit is fine. Short horizon: build the matrix-factoring step. Ultra-short horizon: subsample deliberately rather than spreading thin across everything. The catalog is going to refresh regardless of which method you pick. The only question the paper leaves open to you is whether your testing method learns something durable before that happens, or just finds out, too late, which parts of the deleted catalog it never got around to.