ROI Maximization in Stochastic Online Decision-Making

Nicolò Cesa‐Bianchi, Tommaso Cesari, Yishay Mansour, Vianney Perchet

Abstract

We introduce a novel theoretical framework for Return On Investment (ROI) maximization in repeated decision-making. Our setting is motivated by the use case of companies that regularly receive proposals for technological innovations and want to quickly decide whether they are worth implementing. We design an algorithm for learning ROI-maximizing decision-making policies over a sequence of innovation proposals. Our algorithm provably converges to an optimal policy in class $\Pi$ at a rate of order $\min\{1/(N\Delta^2), N^{-1/3}\}$, where $N$ is the number of innovations and $\Delta$ is the suboptimality gap in $\Pi$. A significant hurdle of our formulation, which sets it aside from other online learning problems such as bandits, is that running a policy does not provide an unbiased estimate of its performance.

Introduction

In modern industrial environments, decision-makers are often presented with a continuous stream of "innovation proposals," ranging from software feature updates to new pharmaceutical compounds. Each proposal requires an evaluation phase—typically involving costly data collection or A/B testing—followed by a binary decision to either implement or reject the innovation. The overarching goal is to maximize the global ROI: the total value derived from all accepted innovations divided by the total cost incurred during the evaluation phases.

While this problem resembles the classic Multi-Armed Bandit (MAB) framework, it introduces two unique challenges:

  1. Non-Additivity of Rewards: Unlike standard MAB problems where rewards are additive, ROI is a ratio. A decision that yields a positive reward might still decrease the global ROI if the cost of evaluation was excessively high.
  2. The Selection Bias Problem: In sequential testing, the decision to stop sampling often depends on the observed data (e.g., stopping when a positive trend is detected). This creates a fundamental bias: the samples used to make the stopping decision cannot be reused to form an unbiased estimate of the innovation's true value.

Methodology: The CAPE Algorithm

To overcome these hurdles, we introduce the Capped Policy Elimination (CAPE) algorithm. A policy in this framework consists of a stopping rule and a decision rule. CAPE addresses the bias problem through a novel oversampling technique.

Algorithm 1: Capped Policy Elimination (CAPE) for ROI maximization.

As detailed in Algorithm 1, CAPE draws twice as many samples as a policy's stopping rule requires. The first half of these samples is used to determine whether to accept or reject the innovation, while the second half is used exclusively to construct an unbiased estimate of the reward. This decoupling ensures that the feedback loop causing selection bias is broken. The algorithm maintains a set of candidate policies $C_n$ and iteratively eliminates those whose performance, based on constructed confidence intervals, is provably inferior to the current best candidate.

For scenarios involving infinite (but countable) sets of policies, we propose ESC-CAPE. This version incorporates a preprocessing step called Extension to Countable (ESC), which identifies a finite "shortlist" of policies. This prevents the learner from wasting resources on policies that might require infinite testing time.

Theoretical Results

The primary contribution of this work is the rigorous proof of convergence for these algorithms.

  • Convergence Rates: In the finite policy case, CAPE converges to the optimal policy at a rate of $O(N^{-1/3})$ in the worst-case scenario. When a suboptimality gap $\Delta$ exists between the optimal and sub-optimal policies, the rate improves significantly to $O(1/(N\Delta^2))$.
  • Infinite Policy Sets: ESC-CAPE successfully extends these guarantees to countable policy sets, maintaining the $O(N^{-1/3})$ rate provided the optimal policy has a finite expected cost.
  • Efficiency: The algorithms are computationally efficient, utilizing simple elimination rules based on concentration inequalities rather than complex non-convex optimization.

Discussion and Future Work

While this framework provides a robust theoretical basis for ROI maximization, several avenues for future research remain. The current model assumes that innovation quality is independent and identically distributed (i.i.d.) over time. In practice, environments may be non-stationary; for instance, a company might exhaust "easy" innovations, leading to a shift in the underlying distribution. Extending CAPE to handle such non-stationarity is a key priority. Furthermore, while the $O(N^{-1/3})$ rate is conjectured to be optimal based on its relationship to weakly-observable bandits, a formal lower bound proof is still required. Finally, adapting the oversampling logic to accommodate batch-sampling constraints—common in fields like clinical trials—would enhance the algorithm's practical applicability.

Summary updated

Abstract

We introduce a novel theoretical framework for Return On Investment (ROI) maximization in repeated decision-making. Our setting is motivated by the use case of companies that regularly receive proposals for technological innovations and want to quickly decide whether they are worth implementing. We design an algorithm for learning ROI-maximizing decision-making policies over a sequence of innovation proposals. Our algorithm provably converges to an optimal policy in class $Π$ at a rate of order $\min\big\{1/(NΔ^2),N^{-1/3}\}$, where $N$ is the number of innovations and $Δ$ is the suboptimality gap in $Π$. A significant hurdle of our formulation, which sets it aside from other online learning problems such as bandits, is that running a policy does not provide an unbiased estimate of its performance.
BibTeX
@inproceedings{cesabianchi2021roi,
  author = {Nicolò Cesa‐Bianchi and Tommaso Cesari and Yishay Mansour and Vianney Perchet},
  title = {{ROI Maximization in Stochastic Online Decision-Making}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=4idcxaFrEw},
}
Figure