Infinite Action Contextual Bandits with Reusable Data Exhaust

Mark Rucker, Yinglun Zhu, Paul Mineiro

In the domain of recommendation systems and automated pricing, "infinite action" contextual bandits represent the cutting edge. Rather than selecting from a discrete set of options—such as five movies or three price tiers—these algorithms operate within continuous spaces, enabling precise decisions like exact ad coordinates or specific discount percentages.

However, a significant rift has persisted between theoretical advancements and production readiness. Theoretical state-of-the-art algorithms often generate data logs (the "exhaust") that are mathematically impossible to reuse for offline experiments. The paper "Infinite Action Contextual Bandits with Reusable Data Exhaust" bridges this gap by introducing CappedIGW, a computationally efficient algorithm that provides near-optimal "smoothed regret" while generating fully reusable data logs for offline policy evaluation.

The Challenge: Non-Reusable Data Exhaust

To iteratively improve machine learning systems, data scientists rely on Counterfactual Risk Minimization. This process involves taking historical logs from an existing algorithm and asking, "What would have happened if we had deployed this new strategy instead?" Answering this requires importance weighting, a technique that depends on knowing the exact probability the historical algorithm had of selecting a specific action.

Previously, the gold standard for infinite action spaces was SmoothIGW. It achieved excellent online performance by occasionally placing a "delta mass" (100% probability) on the single best-predicted action.

The Catch: When the algorithm selects an action using a delta mass, the probability of picking any other nearby action effectively drops to zero. During subsequent offline evaluation, calculating importance weights requires dividing by these probabilities. Dividing by zero breaks the mathematics, rendering the data "non-reusable." In practice, after just 1,000 interactions, SmoothIGW can render up to 80% of its own logged data useless for offline data science.

The Solution: CappedIGW

To resolve the division-by-zero problem without sacrificing online performance, the authors propose CappedIGW (Capped Inverse Gap Weighting). The algorithm introduces three key methodological shifts:

  1. Capped Density: Instead of relying on a delta mass, CappedIGW utilizes a sampling density that is inversely proportional to the "loss gap" (the performance difference between an action and a benchmark, $\beta_t$). Crucially, this density is "capped" and normalized, ensuring that every region of the action space maintains a non-zero probability of selection.
  2. No "Arg Min" Oracle: Traditional bandit algorithms often assume the existence of an optimization "oracle" capable of instantly finding the absolute minimum of a complex loss function. CappedIGW replaces this unrealistic requirement with a Sampling Oracle. It only requires the ability to draw random samples from the action space, making it highly compatible with complex, modern architectures like Deep Neural Networks.
  3. Betting Martingales: To maintain computational efficiency, the authors leverage "betting martingales" to rapidly compute the normalization constants required for their probability distributions. This technique allows the algorithm to "early-exit" when the mathematical conditions are simple, saving significant computational overhead.

Experimental Setup

The researchers evaluated CappedIGW using 20 regression datasets from OpenML (including elevators, pol, and wine_quality).

  • These datasets were converted into contextual bandit problems where the "action" is a continuous value within the unit interval $[0, 1]$.
  • The "loss" was defined as the absolute difference between the algorithm's chosen value and the true label in the dataset.
  • This methodology closely mimics real-world continuous control scenarios, such as dynamic bid pricing or continuous ranking scores.

Key Findings and Insights

  • The "Statistical Free Lunch": Historically, researchers assumed a strict tradeoff: generating better offline data (which requires more exploration) inherently degrades online performance (regret). This paper demonstrates that for infinite action spaces, this tradeoff is largely an artifact of prior algorithm design. CappedIGW achieves data reusability without sacrificing theoretical regret bounds.
  • Online Performance: In head-to-head empirical tests across the 20 datasets, CappedIGW matched or slightly outperformed the previous state-of-the-art (SmoothIGW) in 14 cases. This proves that reusability does not have to come at the cost of online performance.
  • Offline Utility: When researchers used the generated logs to train new models offline, models trained on CappedIGW data were significantly more accurate. The improvement was statistically significant on 12 of the 20 datasets.
  • Reliability: While SmoothIGW's data rapidly became 80% unusable, CappedIGW maintained 100% usable importance weights throughout the entirety of the experiments.
  • Smoothness as a Resource: The computational cost of CappedIGW scales with the "smoothness" of the regret guarantee rather than the dimensionality of the action space, making it uniquely suited for high-dimensional continuous problems.

Limitations and Future Directions

While CappedIGW represents a major step forward for productionizing infinite action bandits, the authors note a few limitations:

  • Computational Overhead: Although efficient compared to exhaustive search, CappedIGW is more computationally demanding than simpler discrete methods, as it requires multiple samples from a reference measure to calculate its internal benchmark parameter ($\beta_t$).
  • Hyperparameter Sensitivity: The algorithm introduces a new parameter, $\kappa_\infty$ (an upper bound on the normalization constant). While empirical results show the algorithm is relatively robust to this choice, it remains an additional hyperparameter for practitioners to tune.
  • Weight Estimation: The current implementation uses a "naive" estimate for importance weights during offline reuse. Developing more sophisticated, lower-variance estimators tailored to these specific weights remains a promising avenue for future research.

Summary updated

Abstract

For infinite action contextual bandits, smoothed regret and reduction to regression results in state-of-the-art online performance with computational cost independent of the action set: unfortunately, the resulting data exhaust does not have well-defined importance-weights. This frustrates the execution of downstream data science processes such as offline model selection. In this paper we describe an online algorithm with an equivalent smoothed regret guarantee, but which generates well-defined importance weights: in exchange, the online computational cost increases, but only to order smoothness (i.e., still independent of the action set). This removes a key obstacle to adoption of smoothed regret in production scenarios.
BibTeX
@inproceedings{rucker2023infinite,
  author = {Mark Rucker and Yinglun Zhu and Paul Mineiro},
  title = {{Infinite Action Contextual Bandits with Reusable Data Exhaust}},
  booktitle = {International Conference on Machine Learning},
  year = {2023},
  url = {https://openreview.net/forum?id=07397vy8ZX},
}
Figure