Infinite Action Contextual Bandits with Reusable Data Exhaust

Mark Rucker, Yinglun Zhu, Paul Mineiro

Abstract

In the domain of infinite action contextual bandits, smoothed regret and reduction to regression have established state-of-the-art online performance. However, these methods often generate data exhaust lacking well-defined importance weights, which prevents critical downstream tasks like offline model selection. This paper introduces CappedIGW, an algorithm that maintains smoothed regret guarantees while generating reusable data with well-defined importance weights. By replacing the traditional arg-min oracle with a benchmark-based approach and utilizing betting martingales for efficiency, CappedIGW removes a significant barrier to the adoption of smoothed regret in production environments.

Introduction

Contextual bandits are a cornerstone of modern machine learning, used in applications ranging from personalized recommendations to dynamic pricing. While finite action sets are well-studied, many real-world scenarios involve infinite or continuous action spaces—such as selecting a precise location on a map or determining an optimal price point.

The current state-of-the-art for these problems, SmoothIGW, achieves impressive online performance. However, it suffers from a significant drawback for production systems: it produces "bad" data. To optimize performance, SmoothIGW frequently samples the single "best" predicted action with a specific probability (a delta mass). This makes the resulting data exhaust impossible to use for Importance Weighting, the standard technique for offline model selection and counterfactual evaluation. Without the ability to test new models on historical data, deploying updates becomes a high-risk endeavor.

The CappedIGW Algorithm

To address the limitations of existing methods, we propose CappedIGW (Capped Inverse Gap Weighting). This algorithm ensures that the data collected during online learning remains fully usable for future offline analysis without sacrificing regret performance.

1. Capped Sampling Density

Unlike previous methods that mix a smooth distribution with a "spike" at the greedy action, CappedIGW employs a density function that is "capped" at a maximum value. This ensures the distribution is absolutely continuous with respect to a reference measure. Consequently, every action has a well-defined probability of being chosen, allowing for the calculation of valid importance weights for any policy.

2. Eliminating the Arg-Min Oracle

Traditional infinite-action algorithms often rely on an "arg-min oracle"—a computationally intensive component required to find the absolute best action within the infinite space. CappedIGW replaces this requirement with a parameter $\beta_t$ that serves as a benchmark. This shift significantly reduces the computational burden and simplifies the implementation of the algorithm in complex action spaces.

3. Efficiency via Betting Martingales

To maintain computational efficiency while finding the correct normalization parameters for the distribution, CappedIGW utilizes a novel technique based on betting martingales. This allows the algorithm to stop the sampling process early once it has sufficient evidence that the parameters are accurate. The resulting computational cost scales with the "smoothness" of the problem rather than the size or dimensionality of the action space.

Experimental Evaluation

The performance of CappedIGW was evaluated using 20 regression datasets from the OpenML repository, converted into contextual bandit problems via a "supervised-to-bandit" transformation. The action space was defined as the unit interval $[0, 1]$, and the feedback was based on the distance between the chosen action and the true label. For larger datasets, random subsets of 80,000 examples were used to ensure consistency.

Online Performance

In head-to-head comparisons, CappedIGW demonstrated superior online performance. Across the 20 datasets, CappedIGW outperformed SmoothIGW on 14 datasets, tied on 5, and underperformed on only 1. This confirms that the modifications required to ensure data reusability do not come at the cost of online reward.

Offline Utility and Data Usability

The primary advantage of CappedIGW is the quality of its data exhaust. When training new models using the logged data:

  • Model Accuracy: Models trained on CappedIGW data showed statistically significant lower average loss on 12 out of 20 datasets compared to those trained on SmoothIGW data.
  • Weight Validity: By the 1,000th iteration, over 80% of the actions played by SmoothIGW were "greedy" actions with no usable importance weights. In contrast, 100% of the data generated by CappedIGW remained usable for importance-weighted analysis.

Conclusion

CappedIGW provides what can be described as a "statistical free lunch": it matches or exceeds the online performance of state-of-the-art infinite action bandits while ensuring that the resulting data is fully reusable for offline data science processes. By making the computational complexity dependent on smoothness rather than action space cardinality, CappedIGW offers a viable, production-ready solution for high-dimensional continuous bandit problems. Future work will focus on refining the estimation of the normalization constant $\kappa_t$ to further enhance the precision of importance weights.

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