ROI Maximization in Stochastic Online Decision-Making
  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.
