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\big\{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 settings, organizations are often inundated with a continuous stream of proposals for technological innovations, such as new UI features or backend optimizations. Each proposal requires an evaluation—typically via A/B testing—to determine its potential value. However, testing is not free; it consumes finite resources like developer time and computational power. The core challenge lies in balancing the depth of evaluation against the opportunity cost of delaying other potential innovations.
This paper addresses this challenge by shifting the focus from traditional cumulative reward maximization to Return on Investment (ROI) maximization. ROI is defined as the ratio of total value gained to the total cost (samples or time) incurred. We introduce the CAPE (Capped Policy Elimination) and ESC-CAPE algorithms to navigate the unique hurdles of this setting, specifically the "Bias Trap" and the non-additive nature of ROI.
The ROI Maximization Framework
Standard machine learning frameworks, such as Multi-Armed Bandits, typically aim to maximize the sum of rewards. In contrast, ROI maximization considers the efficiency of resource utilization. This introduces two primary mathematical difficulties:
- The Bias Trap: A fundamental "hard truth" proven in this work is that one cannot form an unbiased estimate of a policy's reward using only the samples requested by that policy itself. If you only observe the outcomes of innovations you choose to accept, your data is inherently biased.
- Non-Additivity: Unlike standard "regret" which can be summed round-by-round, ROI is a global ratio. A single poor decision early in the sequence—such as over-investing in a low-value innovation—can disproportionately degrade the ROI for the entire sequence.
Algorithmic Contributions
To address these challenges, we propose two main algorithms:
Capped Policy Elimination (CAPE)
CAPE is designed for scenarios with a finite set of candidate policies. To overcome the bias trap, CAPE employs a strategic oversampling technique. During its exploration phase, it draws twice the number of samples a policy would typically require. These additional samples allow for the construction of unbiased estimates for both rewards and costs across all policies in the set. Policies that are provably suboptimal are then systematically eliminated.
Extension to Countable (ESC)
In practice, policy sets may be infinite (e.g., varying the duration of a test). The ESC algorithm serves as a pre-processing step that identifies a "good enough" policy with a positive reward. By using this policy's performance as a benchmark, ESC can bound the search space and ignore an infinite tail of "too expensive" policies, effectively reducing the problem to a finite set manageable by CAPE.
Theoretical Results and Insights
The effectiveness of these algorithms is demonstrated through rigorous regret bounds, characterizing how quickly the algorithm's ROI approaches that of the optimal policy $\pi_\star$:
- Finite Policy Sets: The ROI converges 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: The ESC-CAPE algorithm achieves a convergence rate of $O(N^{-1/3})$.
- Efficiency: If a clear gap exists between the best policy and its competitors, the algorithm achieves a faster $1/N$ convergence rate compared to the $N^{-1/3}$ worst-case scenario.
Beyond convergence rates, a key insight from this work is that exploration is a global investment. Because ROI is a ratio, the algorithms are designed to "fail fast" on ambiguous innovations to preserve the overall ROI. Furthermore, the authors argue that ROI is a superior metric to the False Discovery Rate (FDR) commonly used in A/B testing, as ROI accounts for the varying magnitudes of gains and costs rather than treating all errors equally.
Limitations and Future Directions
While this framework provides a robust foundation for ROI-driven decision-making, several avenues for future work remain. The current analysis assumes that the quality of incoming innovations is independent and identically distributed (i.i.d.) over time. In practice, distributions may be non-stationary as "low-hanging fruit" is exhausted. Additionally, while the $N^{-1/3}$ rate is conjectured to be optimal, a formal lower bound proof is still needed. Finally, optimizing the computational complexity of the ESC pre-processing for specific industrial policy classes could further enhance practical applicability.
Summary updated