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: Beyond Cumulative Reward
In many industrial settings, such as a technology company evaluating a stream of innovation proposals, the objective is not just to maximize total reward but to maximize the Return on Investment (ROI). Each proposal requires costly evaluation (e.g., A/B testing) before a decision to implement can be made. Traditional Multi-Armed Bandit (MAB) frameworks typically focus on cumulative reward, which fails to account for the finite nature of resources and the ratio-based nature of ROI.
The true goal in these scenarios is to maximize the ratio of total reward to total cost. However, ROI is not additive; a single high-cost, low-reward decision can significantly degrade the global performance of a sequence of decisions. This global sensitivity necessitates a new approach to online learning.
The Challenge of Biased Estimation
A fundamental technical hurdle identified in this research is that running a decision policy does not provide an unbiased estimate of its performance. Because a policy's stopping rule $\tau$ (when to stop gathering data) often depends on the data observed so far, the resulting reward estimates are inherently biased. The authors formally prove in Lemma 9 that it is mathematically impossible to define an unbiased estimator of a policy's reward using only the samples that the policy itself chose to collect. This "bias problem" makes standard off-the-shelf bandit algorithms inapplicable to ROI maximization.
The CAPE and ESC-CAPE Algorithms
To overcome the bias problem, the authors introduce Capped Policy Elimination (CAPE). The core innovation of CAPE is a "time machine" approach via oversampling. During the exploration phase, the algorithm draws more samples than any single policy would typically require. This allows the algorithm to simulate "alternate timelines" and construct unbiased estimates for multiple policies simultaneously, enabling the safe elimination of suboptimal candidates.
For scenarios involving infinitely many policies (e.g., any possible threshold for an A/B test), the authors propose ESC-CAPE (Extension to Countable - CAPE). This version includes a preprocessing step called ESC that identifies a policy with a positive reward to "bracket" the search space, reducing an infinite set to a manageable finite set guaranteed to contain the optimal policy.
Theoretical Results and Convergence
The authors provide rigorous mathematical proofs for the efficiency of their algorithms:
- Finite Policy Sets: CAPE converges to the optimal policy at a rate of $O(\min\{1/(N\Delta^2), N^{-1/3}\})$, where $N$ is the number of innovations and $\Delta$ is the suboptimality gap.
- Infinite Policy Sets: ESC-CAPE achieves a convergence rate of $O(N^{-1/3})$.
These rates demonstrate that the approach is significantly more efficient than standard A/B testing metrics like False Discovery Rate (FDR), which often ignore the relative values of the innovations being tested.
Limitations and Future Outlook
While this framework provides a robust theoretical foundation for ROI maximization, several avenues for future work remain:
- I.I.D. Assumption: The current theory assumes innovation quality comes from a fixed, stationary distribution, whereas real-world quality may fluctuate or decline over time.
- Lower Bounds: While the $N^{-1/3}$ rate is conjectured to be optimal, a formal lower bound proof for this specific ROI problem is still pending.
- Decision Complexity: The framework currently focuses on binary (accept/reject) decisions; extending this to multi-choice or continuous investment levels is an open challenge.
Summary updated