Exploring Offline Policy Evaluation for the Continuous-Armed Bandit Problem

Jules Kruijswijk, Petri Parvinen, Maurits KapteinarXiv 2019 · arXiv

Abstract

Offline Policy Evaluation (OPE) is essential for testing decision-making strategies without the costs or risks of live deployment. However, standard OPE "replay" methods are designed for discrete actions and fail in Continuous-Armed Bandit (CAB) settings, where the probability of a logged action exactly matching a policy recommendation is zero. This paper proposes a "fuzzy matching" approach using a distance threshold $\delta$ to enable OPE for CAB. We demonstrate that while this method introduces a downward bias in reward estimation, it maintains a consistent ranking of policies, allowing researchers to reliably identify the best-performing strategy from historical data.

Introduction

In Reinforcement Learning, OPE allows for the evaluation of a new policy using data collected by a different, historical policy. For discrete action spaces, this is typically achieved by filtering logs for instances where the historical action matches the new policy's suggestion. In continuous action spaces—common in applications like dynamic pricing or medical dosing—this exact matching is impossible. If a policy suggests a 15.55% discount but the log records 15.54%, traditional methods discard the data point. This paper addresses this "zero-probability match" problem by introducing a proximity-based acceptance criterion.

Methodology: Fuzzy Matching with $\delta$

The proposed method extends the classic replay algorithm by introducing a tuning parameter, $\delta$. A logged data point $(h, a, r)$ is accepted for evaluation if the distance between the logged action $a$ and the policy's suggested action $\Pi(h)$ is within the threshold: $$|a - \Pi(h)| < \delta$$

This approach introduces a fundamental trade-off:

  • Large $\delta$: Increases the sample size $T$ by accepting more "near-miss" data points, reducing variance but increasing bias and noise.
  • Small $\delta$: Reduces bias by ensuring accepted actions are very close to the policy's intent, but results in a smaller sample size and higher variance.

The authors posit that for policy selection, ranking consistency is more critical than unbiased estimation. As long as the offline evaluation correctly identifies which policy is superior, the absolute reward estimate is secondary.

Datasets and Simulation Setup

The method was validated across three scenarios:

  1. Simple Simulation: A unimodal reward function (parabola) with Gaussian noise.
  2. Complex Simulation: A bimodal reward function with local optima, testing the method's ability to navigate more difficult landscapes.
  3. Field Evaluation: A real-world dataset from an online rebate company (2,448 points), where the action was a commission split percentage and the reward was revenue.
Bimodal reward function used in the complex simulation study to evaluate policy performance in non-trivial environments.

Key Results

The primary finding is that the relative ranking of policies—Uniform Random (UR), $\epsilon$-First (EF), Lock-in Feedback (LiF), and Thompson Bandit Learner (TBL)—remains stable across different values of $\delta$.

Comparison of online regret vs. offline regret estimates across various delta thresholds.

As shown in the figure above, as $\delta$ decreases from 0.5 to 0.01, the offline regret curves increasingly resemble the "Online" ground truth. Crucially, even when the absolute regret values differ, the order of the policies (e.g., TBL outperforming UR) is preserved. In the field evaluation, the method successfully identified that an $\epsilon$-first policy would likely outperform the company's existing heuristic, providing a data-driven path for optimization.

Discussion and Future Work

While effective, the $\delta$-threshold approach has limitations. It currently relies on a "hard" cutoff; future work could explore "soft" weighting using kernels to give more importance to closer matches. Additionally, the method's scalability to multi-dimensional continuous action spaces remains an open question. Despite these challenges, the shift in focus from unbiasedness to ranking consistency provides a practical framework for applying OPE to a wide range of continuous real-world problems.

Conclusion

By relaxing the requirement for exact matches, the fuzzy matching OPE method bridges the gap between discrete and continuous bandit problems. The stability of policy rankings across varying thresholds demonstrates that historical data can be a powerful tool for continuous optimization, even when exact replication of policy actions is impossible.

Summary updated

Abstract

The (contextual) multi-armed bandit problem (MAB) provides a formalization of sequential decision-making which has many applications. However, validly evaluating MAB policies is challenging; we either resort to simulations which inherently include debatable assumptions, or we resort to expensive field trials. Recently an offline evaluation method has been suggested that is based on empirical data, thus relaxing the assumptions, and can be used to evaluate multiple competing policies in parallel. This method is however not directly suited for the continuous armed (CAB) problem; an often encountered version of the MAB problem in which the action set is continuous instead of discrete. We propose and evaluate an extension of the existing method such that it can be used to evaluate CAB policies. We empirically demonstrate that our method provides a relatively consistent ranking of policies. Furthermore, we detail how our method can be used to select policies in a real-life CAB problem.
BibTeX
@misc{kruijswijk2019exploring,
  author = {Jules Kruijswijk and Petri Parvinen and Maurits Kaptein},
  title = {{Exploring Offline Policy Evaluation for the Continuous-Armed Bandit Problem}},
  year = {2019},
  eprint = {1908.07808},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1908.07808},
}

Loading related content...

Figure