TL;DR
Researchers from Booking.com have extended the Open Bandit Pipeline (OBP) to bridge the gap between academic bandit theory and the "messy" reality of industrial e-commerce. Their new simulation components allow practitioners to model critical real-world hurdles like concept drift, delayed rewards, and the trade-offs between on-policy and off-policy learning.
What Problem Does This Paper Address?
In textbook multi-armed bandit (MAB) problems, rewards are immediate, environments are stationary, and the agent has full freedom to explore. In the real world—specifically at a scale like Booking.com—these assumptions fall apart.
Practitioners face several "industry challenges":
- Concept Drift: User preferences change (e.g., a sudden shift to domestic travel during a pandemic).
- Delayed Rewards: A user might click an email today but not book a hotel for a week.
- Business Constraints: You can't recommend a hotel that is fully booked, regardless of what the model wants to explore.
- Off-policy vs. On-policy: On-policy learning (learning while interacting) is risky for user experience, but off-policy learning (learning from logs) is technically difficult to debias.
Existing simulation frameworks often lack the documentation or flexibility to model these specific dynamics, making it hard for researchers to know if their algorithms will actually survive a production deployment.
Methods
The authors extended the existing Open Bandit Pipeline (OBP) framework by introducing two primary classes:
BanditEnvironmentSimulator: Generates rounds of contexts and rewards. Crucially, it now supports adelay_functionto simulate rewards that arrive many rounds after an action is taken.BanditPolicySimulator: Handles the interaction between the algorithm and the environment, keeping detailed logs to facilitate off-policy evaluation.
To handle specific industry hurdles, they added:
CoefficientDrifter: A tool to simulate four types of concept drift (sudden, incremental, gradual, and seasonal) by varying reward coefficients over time.ExponentialDelaySampler: This allows for both unbiased delay (randomly sampled) and reward-dependent delay (where, for example, a less desirable recommendation might cause a user to hesitate longer before acting).
Datasets
Rather than introducing a new static dataset, this paper provides a simulation suite built on top of OBP. The experiments described in the paper use these simulated environments (typically with 10 arms) to generate synthetic data that mimics the statistical properties of Booking.com’s production traffic. This allows for controlled experiments where the "ground truth" of the environment (like the exact timing of a drift) is known.
Key Insights and Ideas
- The IPW Advantage: One of the most interesting findings is that Inverse Propensity Weighting (IPW)—an off-policy method—can eventually outperform standard on-policy bandit algorithms if given enough data. As seen in Figure 1, after about 5,000 rounds, the IPW learner overtakes the on-policy competitors.
- Logging Policy Quality Matters: The success of off-policy learning is highly sensitive to the "logging policy" (the algorithm used to collect the initial data). If the logging policy doesn't explore enough, the IPW learner's performance suffers significantly.
- The "Recovery" Myth: Standard bandit algorithms are surprisingly slow to recover from concept drift. The authors found that in many simulated drift scenarios, the algorithms failed to return to their original performance levels within a "reasonable" timeframe.
- Stationary vs. Non-Stationary Delay: In a stationary environment, delayed rewards eventually "catch up," and the model converges to the same performance as a no-delay model. However, in a non-stationary (seasonal) environment, delays significantly degrade the total reward because the model is always learning from "old" news.
Key Results
The authors provided several experimental benchmarks using their new tools:
- Off-Policy Performance: Figure 1 demonstrates that while on-policy bandits start strong, an IPW learner trained on logged data eventually achieves higher average rewards as the number of rounds increases. Comparison of on-policy and off-policy methods
- Drift Impact: In Figure 3, the authors show the devastating effect of abrupt and seasonal drift. All bandit algorithms tested (LinUCB, Thompson Sampling, etc.) lost significant reward when the environment shifted and struggled to recover. Comparing types of drift
- Delay Costs: Experiments showed that reward-dependent delays (where delay is tied to the expected reward) make convergence much slower compared to unbiased delays, highlighting the need for delay-aware algorithms in e-commerce.
Limitations and Future Work
While this extension covers drift and delay, the authors acknowledge that two major industry challenges are still "left for future work":
- Reward Design: Simulating the use of "surrogate rewards" (like clicks) to optimize for a primary metric (like bookings) when the primary metric is too sparse.
- Business Rules: Modeling environments where the available "arms" (recommendations) change constantly due to inventory or business logic.
The team plans to continue extending OBP to include these features and to implement functionality for more complex scenarios like slate recommendations, where multiple items are recommended at once.
Summary updated