# ROI Maximization in Stochastic Online Decision-Making

arXiv: https://arxiv.org/abs/1905.11797 · HTML: https://mlsanity.com/paper/1905.11797/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 May 2019.

## Built on by (most cited first, 3 of 3)

- [Online Decision Deferral under Budget Constraints](https://mlsanity.com/paper/2409.20489/) (2024)
- [Cost-Efficient Online Decision Making: A Combinatorial Multi-Armed Bandit Approach](https://mlsanity.com/paper/2308.10699/) (2023)
- [An Application of Online Learning to Spacecraft Memory Dump Optimization](https://mlsanity.com/paper/2202.06617/) (2022)

## Abstract (arXiv)

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 minbig1/(NDelta2),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.