A New Theoretical Framework for Fast and Accurate Online Decision-Making

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

Overview

This paper introduces a formal theoretical framework for maximizing Return on Investment (ROI) in repeated decision-making scenarios, such as a company deciding which technological innovations to adopt. The authors develop the CAPE (Capped Policy Elimination) and ESC-CAPE algorithms, which are the first to provide provable convergence rates for ROI optimization. Crucially, these algorithms overcome the "biased feedback" hurdle that makes standard multi-armed bandit techniques inapplicable to this domain.

The Challenge of ROI Maximization

In the tech industry, companies are constantly bombarded with proposals for new features. To decide if an innovation is worthwhile, they run tests (like A/B tests). However, testing incurs costs—both direct financial costs and opportunity costs (the time spent testing a mediocre idea could have been spent testing a great one).

The traditional machine learning goal is often to maximize total reward. In this real-world context, however, the objective shifts to ROI maximization: maximizing the ratio of total value gained to total cost spent.

This objective presents two major technical challenges:

  1. Non-Additivity: Unlike standard "regret" in bandit problems, ROI is a ratio. Performance cannot simply be summed up round-by-round; the system must be analyzed globally.
  2. The Bias Trap: If a "stopping rule" is used (e.g., stopping a test as soon as a feature looks slightly positive), the collected data is inherently biased. It is impossible to form an unbiased estimate of a policy's performance merely by running that policy.

Methodology: Overcoming Biased Feedback

To find the optimal decision-making policy, the authors propose a novel two-stage algorithmic approach:

1. CAPE (Capped Policy Elimination)

Designed for scenarios with a finite number of possible policies, CAPE's core mechanism is oversampling. To evaluate a policy that would normally stop after $k$ samples, the algorithm intentionally draws extra samples. This allows the learner to build an unbiased estimate of the reward, effectively "peeking" further into the data than the policy itself would. These unbiased estimates are then used to systematically eliminate sub-optimal policies over time.

2. ESC (Extension to Countable)

To handle infinitely many possible policies, the authors introduce a preprocessing step called ESC. It acts as a filter, testing policies with shorter durations first. It establishes a "budget" based on the best-performing policies found so far and uses it to prune the infinite set down to a finite, manageable group guaranteed to contain the optimal policy.

Key Insights and Theoretical Results

The paper argues that in high-volume decision environments, the speed of decision-making is just as critical as accuracy. Maximizing the "flow" of improvement is central to the ROI objective. By connecting this problem to "bandits with weakly observable feedback graphs," the authors establish strong theoretical guarantees:

  • Convergence Rates: For a finite set of $K$ policies, the CAPE algorithm converges to the optimal policy at a rate of $\mathcal{O}(N^{-1/3})$, where $N$ is the number of innovations.
  • Gap-Dependent Bound: If there is a clear suboptimality gap ($\Delta$) between the best policy and the rest, the algorithm converges at a much faster rate of $\mathcal{O}(1/(\Delta^2 N))$.
  • Infinite Scalability: The combined ESC-CAPE algorithm successfully handles infinite policy classes while maintaining the $\mathcal{O}(N^{-1/3})$ convergence rate, proving that ROI maximization is theoretically achievable even in boundless search spaces.

Limitations and Future Work

As a purely theoretical framework, the paper focuses on mathematical proofs and algorithmic design rather than empirical datasets. The authors note several areas for future exploration:

  • The I.I.D. Assumption: The current theory assumes the quality of incoming innovations remains stable over time (independent and identically distributed). Extending this framework to non-stationary environments where the "pool" of ideas fluctuates is a key next step.
  • Lower Bounds: While the authors conjecture that their $N^{-1/3}$ rate is optimal, a formal mathematical proof for the lower bound remains an open problem.
  • Computational Efficiency: Implementing these algorithms for massive, complex policy spaces in real-time production environments presents a significant engineering challenge.

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 $\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.
BibTeX
@inproceedings{cesabianchi2021new,
  author = {Nicolò Cesa-Bianchi and Tommaso Cesari and Yishay Mansour and Vianney Perchet},
  title = {{A New Theoretical Framework for Fast and Accurate Online Decision-Making}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=4idcxaFrEw},
}
Figure