ROI Maximization in Stochastic Online Decision-Making
Authors: Nicolò Cesa-Bianchi
Tommaso Cesari
Yishay Mansour
Vianney Perchet
Venue: NeurIPS 2021 Poster (2021)
Keywords: online learning
regret minimization
action elimination
explore-then-commit

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.

ROI Maximization
in Stochastic Online Decision-Making
Nicolò Cesa-Bianchi Università degli Studi di Milano & DSRC nicolo. cesa-baecc sataa-biancchhc @unimi it
Tommaso Cesari Toulouse School of Economics tommaso.. cesari @tse frr.ffr... eu
Yishay Mansour
Vianney Perchet CREST, ENSAE & Criteo Al Lab vianney.perchett www.chettttormmalesu.... org
Tel Aviv University & Google rescarch mansour@tau.aco ac.
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-makinn policies over a sequence of innovation proposals. Our algorithm provably converges to optimal policy in class IT at a rate of order min (1/(NA²), N-1/33, where N is the number of innovations and A is the suboptimality gap in 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 performance.
Introduction
Often, companies have to make yes/no decisions, such as whether to adopt a new technology or retire an old product. However, finding out the best option in all circumstances could mean spending too much time or money in the evaluation process. If the decisions to make are many, one could be better off making more of them quickly and inexpensively, provided that these decisions have an overall positive effect. In this paper, we investigate the problem of determining decision policy to balance the reward over cost ratio optimally (i.e., to maximize the return on investment).
motivating example. Consider a technology company that keeps testing innovations to increase some chosen metric (e.g., benefits, gross revenue, revenue excluding the traffic acquisition cost). Before deploying an innovation, the company wants to figure out whether it is profitable. As long each innovation can be tested i.i.d. samples of users, the company can perform randomized tests and make statistically sound decisions. However, there is an incentive to make these tests run quickly possible because, for example, the testing process is expensive. Another reason could be that keeping a team on project that has negative, neutral, or even borderline positive potential prevents it from testing other ideas that might lead to a significantly better improvement. other words, it is crucial to learn when to drop barely positive innovations in favor of highly positive ones, so increase the overall flow of improvement over time (i.e., the ROI of the tests).
More generally, our framework describes problems where agent faces sequence of decision tasks consisting of either accepting or rejecting an innovation. Before making each decision, the agent can invest resources into reducing the uncertainty objective is to maximize the total ROL. Namely, the ratio between the total value accumulated by accepting innovations and the total cost. For an in-depth discussion on alternative goals, we refer the reader to the Supplementary Material (Section
the value brought by the innovation. The global
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

The model. Each task n in the sequence is associated with pair (Hin, Da) that the learner can never directly observe.
Mn is a random variable representing the (possibly negative) true value of the n-th innovation.
Dn is a probability distribution over the real numbers with expectation Yen modeling the feedback on the 1-th innovation that the learner can gather from testing (see below).
During the n-th task, the learner can draw arbitrarily many i.id. samples X Xn.2 from Dn. accumulating information on the unknown value fn. of the innovation currently being tested. After stopping drawing samples, the learner can decide to either accept the innovation, earning Mn reward, or reject it and gain nothing instead. We measure the agent performance during N tasks as the (expected) total amount of value accumulated by accepting innovations Yo, divided by the (expected) total number of samples requested throughout all tasks. In formulas, the ROI of a strategy is then
E E Pn Im is accepted)]
m==1 numberr of samples requested during the 1--hh task
In Section 3 we present this setting in more detail and introduce the relevant notation.
LLD. assumption. We assume that the value Hn, of the n-th innovation is drawn i..d. from an unknown and fixed distribution. This assumption is meaningful if past decisions do not influence future innovations whose global quality remains stable over time. In particular, it applies whenever innovations can progress in many orthogonal directions, each yielding a similar added value (e.g.. when different teams within the same company test improvements relative to individual aspects of the company). If both the state of the agent and that of the environment evolve, but the ratio of good versus bad innovations remains essentially the same, then this i.i.d. assumption is still justified. In other words, it is not necessarily the absolute quality of the innovations that has to remain stationary, but rather the relative added value of the innovations given the current state of the system. This case is frequent in practice, especially when a system is close to its technological limit. Last but not least, algorithms designed under stochastic assumptions often perform surprisingly well in practice, even if i..d. assumptions are not fully satisfied or simply hard to check.
A baseline strategy and policy classes. A natural, yet suboptimal, approach for deciding if an innovation is worth accepting is to gather samples sequentially, stopping as soon as the absolute value of their running average surpasses a threshold. and then accepting the innovation if and only if the average is positive. The major drawback of this approach is that the value fa, of an innovation n could be arbitrarily close to zero. In this case, the number of samples needed reliably determine its sign (which is of order 1/pΩ) would become prohibitively large. This would result is massive time investment for an innovation whose return negligible at best. In hindsight, it would have been better to reject the innovation early and move on to the next task. For this reason, testing processes in practice needs hard termination rules of the form: if after drawing a certain number of samples confident decision can be taken, then terminate the testing process rejecting the current innovation. Denote by T this capped early stopping rule and by accept. the accept/reject decision rule that comes with it. We say that the pair π = (T, accept) is a policy because it fully characterize the decision decision-making process for an innovation. Policies defined by capped early stopping rules (see (4) for concrete example) are of great practical importance (Johari et al.) 2017 Kohavi et al.) 2013). However, policies can be defined more generally by any reasonable stopping rule and decision function. Given (possibly infinite) set of policies, and assuming that 11, .2,.... are drawn i.i.d. from some unknown but fixed distribution, the goal is to learn efficiently, at the lowest cost, the best policy x, in the set with respect to a sensible metric. Competing against fixed policy classes is common modeling choice that allows to express the intrinsic constraints that are imposed by the nature of the decision-making problem. For example, even if some policies outside of the class could theoretically yield better performance, they might not be implementable because of time, budget, fairness, technology constraints.
Challenges. One of the biggest challenges arising in our framework is that running a decision- making policy generates a collection of samples that -in general cannot be used form an unbiased estimate of the policy reward (see the impossibility result in Section[Ejor of the Supplementary Material). The presence of this bias is a significant departure from settings like multiarmed and firing bandits (Auer et al. 2002 Jain and Jamieson 2018). where the learner observes an unbiased sample of the target quantity at the end of every round (see the next section for additional details). Moreover, contrary to standard online learning problems, the relevant performance measure is neither additive in
2

---

the number of innovations nor in the number of samples per innovation. Therefore, algorithms have to be analyzed globally, and bandit-like techniques -in which the regret is additive over rounds- cannot be directly applied. We argue that these technical difficulties are a worthy price to pay in order to define a plausible setting, applicable to real-life scenarios.
Main contributions. The first contribution of this paper is providing a mathematical formalization of our ROI maximization setting for repeated decision making (Section B3 We then design an algorithm called Capped Policy Elimination (Algorithm{] | CAPE) that applies to finite policy classes (Section 4p. We prove that CAPE converges to the optimal policy at rate //(A/M N), where N the number of tasks and A is the unknown gap between the performance of the two best policies, and at rate --1/3 when A is small (Theorem 1 In Section 5 we tackle the challenging problem of infinitely large policy classes. For this setting, we design a preprocessing step (Algorithm 2 ESC) that leads to the ESC-CAPE algorithm. We prove that this algorithm converges to the optimal policy in an infinite set at a rate of N-1/3 (Theorem 4
I Limitations. Although we do not investigate lower bounds in this paper, we conjecture that our N-1/3 convergence rate it is optimal due to similarities with bandits with weakly observable feedback graphs (see Section [ "Divided we fall"). Another limitation of our theory is that it only applies to i.idd sequences of values jn- It would be interesting to extend our analysis to distributions of f4n that evolve over time. These two intriguing problems are left open for future research.
2 Related Work
Return on Investment (ROI) was developed and popularized by Donaldson Brown in the early Nineties (Flesher and Previts 2013) and it is still considered extremely valuable metric by the overwhelming majority of marketing managers (Farris et al. 2010). Beyond economics, mathematics, and computer science, ROI finds applications in other fields, such as cognitive science and psychology (Chabris) jet al. 2009). Despite this, to the best of our knowledge, no theoretical online learning framework has been developed specifically for ROI maximization. However, our novel formalization of this sequential decision problem does share some similarities with other known online learning settings. In this section, we review the relevant literature regarding these settings and stress the differences with ours.
Correa al. 2019; Alaei et al.] 2012), an agent observes sequentially (usually non-negative) random variables Z Z....., Z, and decides to stop at some time r; the reward is then Z,. Variants include the possibility of choosing more than one random variable (in which case the reward is some function of the selected random variables), and the possibility go back in time (to some extent). The Pandora's 's box problem is slightly different (Weitzman] 1979; Kleinberg et al. 2016)] Esfandiari et al.] [019); in its original formulation, the agent can pay cost Cn 2 0 observe any Zn. After stopping exploring, the agent's final utility is the maximum of the observed Z,, 's minus the cumulative cost (or, in other variants, some function of these). Similarly to the (general) prophet inequality, the agent in our sequential problem faces random variables (Z,, Mn in our notation) and sequentially selects any number of them (possibly with negative values) without the possibility to go back in time and change past decisions. The significant difference is that the agent in our setting never observes the value of fn. In Pandora's 's box, the agent can see this value by paying some price (that approximately scales as 1/e² where @ is the required precision). Finally, the global reward is the cumulative sum (as in prophets) and not the maximum (as in Pandora's box) of the selected variables, normalized by the total cost (as in Pandora's 's box, but our normalization is multiplicative instead of additive, as it represents ROI).
Prophet inequalities and Pandora's box. In prophet inequalities (Lucier 2017
Multi-armed bandits. If we think of the set of all policies used by the agent to determine whether or not to accept innovations as arms, our setting becomes somewhat reminiscent of multi-armed bandits (Slivkins 2019 Bubeck and Cesa-Bianche 2012 Rosenberg et al. (007). However, there are several notable differences between these two problems. In stochastic bandits, the agent observes an unbiased estimate of the expected reward of each pulled arm. In our setting, the agent not only does not see it directly, but it is mathematically impossible to define such an estimator solely with the feedback received (see the impossibility result in Section P of the Supplementary Material), Hence, off-the-shelf bandit algorithms cannot be run to solve our problem. In addition, the objective in bandits is to maximize the cumulative reward, which additive over time, while the ROI is not. Thus, it is unclear how formal guarantees for bandit algorithms would translate to our problem.
3

---

We could also see firing bandits (Jain and Jamieson 2018) as a variant of our problem, where fo belongs to [O, 1]. D, are Bernoulli distribution with parameter Na, and policies have a specific form that allows to easily define unbiased estimates of their rewards (which, we reiterate, is not possible in our setting in general). Furthermore, firing bandits, it is possible to go back and forth in time, sampling from any of the past distributions Dr, and gathering any number of samples from it. This is a reasonable assumption for the original motivations of firing bandits because the authors thought of pn, as the value of project in a crowdfunding platform, and, in their setting, drawing samples from D, corresponds to displaying projects on web pages. However, in our setting, Un represents the theoretical increment (or decrement) of company's profit through given innovation, and it is unlikely that a company would show new interest in investing in a technology that has been tested before and did not prove to be useful (a killed project is seldom re-launched). Hence, when the sampling of DD, stops, an irrevocable decision is made. After that, the learner cannot draw any more samples in the future. Finally, as in multi-armed bandits, the performance criterion in firing bandits is the cumulative reward and not the global ROI.
Another online problem that shares some similarities with ours is bandits with knapsacks (Badani- diyuru et al. 2018). In this problem, playing arm consumes one unit of time together with some other resources, and the learner receives an unbiased estimate of its reward as feedback. The process ends soon time any one of the other resources is exhausted. As usual, the goal is to maximize the cumulative regret. As it turns out, we can also think of our problem as a budgeted problem. In this restatement, there is a budget of samples. The repeated decision-maie making process proceeds as before, but it stops as soon as the learner has drawn a total of T samples across all decision tasks. The goal is again to maximize the total expected reward of accepted innovations divided by T (see Section D of the Supplementary Material for more details on the reduction). As per the other bandit problems, there are two crucial differences. First, running a policy does not reveal an unbiased estimate of its reward. Second, our objective is different, and regret bounds do not directly imply convergence to optimal ROL. For other examples of budget-constrained bandit settings, see also (Cayci et al. 2020 2019).
Repeated A/B testing.
We can view our problem as framework for repeated A/B testing (Tukey
1953
Genovese et al.
2006
Foster and Stine 2008 Heesen and Janssen 2016 Javanmard et al.
2018 Azevedo et al.
2018 Li and Barber 2019 Schmit et al. 2019] Xu et al. 2021: Johari et al.
2021). in which assessing the value of an innovation corresponds to performing an A/B test, and the goal is maximizing the ROL. A popular metric optimize sequential A/B tests is the so-called false discovery rate (FDR) -see (Ramdas et al.) 2017: Yang et al., 2017) and references therein. Roughly speaking, the FDR is the ratio of accepted He,, that are negative over the total number of accepted pa, (or more generally, the number of incorrectly accepted tests over the total number if the metric used at each test changes with time). This, unfortunately, disregards the relative values of tests Hh that must be taken into account when optimizing a single metric (Chen and Kasiviswanathar 2020; Robertson and Wason 2018). Indeed, the effect of many even slightly negative accepted tests could be overcome by few largely positive ones. For instance, assume that the samples Xn,, of any distribution Dr belong {-1, 1). and that their expected value pn is uniformly distributed on {-r,e). To control the FDR, each A/B test should be run for approximately 1/e² times, yielding a ratio of the average value of an accepted test to the number of samples of order e3. A better strategy, using just one sample from each A/B test, is simply to accept (h, if and only if the first sample is positive. Direct computations show that this policy, which fits our setting, achieves a significantly better performance of order E.
Some other A/B testing settings are more closely related to ours, but make stronger additional assumptions or suppose preliminary knowledge: for example, smoothness assumptions can be made on both D, and the distributions of Pa (Azevedo et al. 22018). or the distribution of pa is known, and the distribution of samples belongs to a single parameter exponential family, also known beforehand (Schmit et al. 2019).
A related topic that sits in between multi-armed bandits and repeated A/B testing is best-arm identification-seee e.g., the recent paper (Garivier and Kaufmann 202T) and references therein- where the learner has to minimize the number of observations needed to select a (near)-optimal arm.
Rational metareasoning.
Our setting is loosely related to the Al field of meta-reasoning (Grifithss al. 2019 Hay al. 2012). In metalevel decision problem, determining the utility (or reward) of

---

given action is computationally intractable. Instead, the learner can run simulation, investing computational cost gather information about this hidden value. The high-level idea is then to learn which actions to simulate. After running some simulations, the learner picks an action to play, gains the corresponding (hidden) reward, and the state of the system changes. In rational meta-reasoning, the performance measure is the value of computation (VOC): the difference between the increment in expected utility gained by executing a simulation and the cost incurred by doing so. This setting is not directly comparable to ours for two reasons. First, the performance measure is different, and the additive nature of the difference that defines the VOC gives no guarantees on our multiplicative notion of ROI. Second, in this problem, can pick which actions to simulate, while in settings, innovations come independently of the learner, who has to evaluate them in that order.
3 Setting and Notation
In this section, formally introduce the repeated decision-making protocol for an agent whose goal is to maximize the total return on investment in a sequence of decision tasks.
The only two choices that an agent makes in a decision task are when to stop gathering information on the current innovation and whether or not to accept the innovation based on this information. In other words, the behavior of the agent during each task is fully characterized by the choice of a pair (deiision-mkking) (r, accept) that we call (decision- making) policy (for the interested reader, Section [A of the Supplementary Material contains a short mathematical discussion on policies), where:
Txx), called duration, maps sequence of observations æ (œ1, 22....) to integer d (the no. of observations after which the learner stops gathering info on the current innovation);
accept(d, æ). called decision, maps the firs d observations of sequence to a boolean value in {0, 1] (where represents accepting the current innovation).
(21 .2.
An instance of our repeated decision-making problem is therefore determined by set of admissible policies 11 = {Th J {(T,, accept) Juck (with I. finite or countable) and a distribution D on [-1, 1], modelling the value of innovations Naturally, the former is known beforehand but the latter unknown and should learned.
For fixed choice of II and D, the protocol is formally described below. In each decision task
1. the value Hn, of the current innovation is drawn i.i.d. according to D;
2. X,, n is sequence of i..dd (given (T)) observations with X,,; +1 and E(X,,; | [m.] pni
3. the agent picks kn E K. or, equivalently, a policy Tk., = (Tk.. accept) E II;
4. the agent draws the first dn, Tk. (X,)) samples of the sequence of observations X
5. the basis of these sequential observations, the agent makes the decision accept (dn, xx))
Crucially, un is never revealed to the learner. We say that the agent runs policy ma (Tx, accept) (on a value (n,) when steps 5 occur (with k; <- k). We also say that they accept (resp., rejects) un if their decision at step 5 equal to 1 (resp., 0). Moreover, we say that the reward obtained and the cost I paid by running a policy म = accept) on a value pn are, respectively,
reward(TT,, Mn) = nnn accept (Tx XX n). X.)) {Mm;
cost(ITE, Mn)
(X, E E
(1)
The objective of the agent is to converge the highest ROI of policy in 11, i.e., to guarantee that
N n- 2m E [[ccos(TTa TR. Mm)]]]
E Brewardd(T
Freward
(TKK, Mn)] + 0 as N
Ry sup kEK
(2)
E
(cost(TTin) Mm)]]
where the expectations taken with respect Pas X n. and (possibly) the random choices of kn-
Wee assume that the values of the innovations and the learner's 's observations belong to [-1, 1 and 1 respectively. We do this merely for the sake of readability (to avoid carrying over awkward constants distributions ). With standard argument, both [-1, and {-1, can be extended arbitrary codomains straightforwardly under a mild assumption of subgaussianity.
"Given μo.. the random variable d,, is stopping time w.r.t. the natural filtration associated to X..
'We detine the cost as the duration Tx (X..) of a run. Following our exact proofs, one can see that everything remains true if we define the cost in terms of any increasing function of the duration. This puts no meaningful restrictions cost functions.
5

---

To further lighten notations, we denote the expected reward, cost, and ROI of a policy π by reward( TT = E [re Pn]], cost((T) = E [cost(TT pm)]]: (T = roward(t)/coot(() (3)
respectively and we say that The is an optimal policy if K* E argmax*ex ROI(T)). Note that reward(a) and cost(z) do not depend on because pa is drawn i.idd. according to jr.
For each policy (T. accept) E IT and all tasks n, we allow the agent to reject the value yn regardless of the outcome of the sampling. Formally, the agent can always run the policy (T, 0), where the second component of the pair is the decision identically equal to zero (i.e., the rule "always reject").
We also allow the agent to draw arbitrarily many extra samples in addition to the number rXx,) () that they would otherwise draw when running a policy (T, accept) E on a value fus provided that these additional samples are not taken into account in the decision to either accept or reject Ann Formally, the agent can always draw 7 x.) + k many samples (for any & E N) before making the decision accept (T (T(X (X,.). n). x.... where we stress that the first argument of the decision function accept is ,x,,,) and not r(x,,) + k. Oversampling this way worsens the objective and might seem utterly counterproductive, but it will be crucial for recovering unbiased estimates of pu.
4 Competing Against K policies (CAPE)
As we mentioned in the introduction, in practice the duration of a decision task is defined by a capped early-stopping rule g.... drawing samples until falls outside of a confidence interval around the empirical average, or maximum number of draws has been reached. More precisely, if N tasks have to be performed, one could consider the natural policy class {(Tk. accept) (xpptt))x((1..... kE(1..., K} given by
The (x) = min(k, inf {d E N:N::: Jatal 2 aa))
and accept .) = T (a. 2 ad)
(4)
where Is = (4/) E. Ei I, is the average of the first d elements of the sequence x = (x1, x2, ......) and Og = (1/a)) (K for some e > 0 and 8 E (0, 1). While in this example policies are based on an Hoeffding concentration rule, in principle the learner is free to follow any scheme. Thus, we now generalize this notion and present an algorithm with provable guarantees against these finite families of policies.
Finite sets of policies. In this section, we focus on finite sets of K policies II = (Th (TEEkE(L...... arceatcc)t)):)) keE..... where accept is an arbitrary decision and ....... TK is any sequence of bounded durations (say, Tk for all k) For the sake of convenience, we assume the durations are sorted by index (Th S Th if k < h), so that T1 is the shortest and тк is the longest.
Divided we fall. A common strategy in online learning problems with limited feedback is explore- then-commit (ETC). ETC consists of two phases. In the first phase (explore), each action is played for the same amount of rounds, collecting this way i.i.d. samples of all rewards. In the subsequent commit phase, the arm with the best empirical observations is played consistently. Being very easy to execute, this strategy is popular in practice, but unfortunately, it is theoretically suboptimal in some applications. A better approach is performing action elimination. In typical implementation of this strategy, all actions in a set are played with a round-robin schedule, collecting i.i.d. samples of their rewards. At the end of each cycle, all actions that are deemed suboptimal are removed from the set, and a new cycle begins. Neither one of these strategies can be applied directly because running a policy in our setting does not return an unbiased estimate of its reward (for quick proof of this simple result, see Section El the Supplementary Material). However, it turns out that we can get an i..dd estimate of a policy by playing a different policy n'. Namely, one that draws more samples than R. This is reminiscent of bandits with weakly observable feedback graph. related problem for which the time-averaged regret over T rounds vanishes at a 1133 rate (Alon et al. 2015). Albeit none of these three techniques works on its own, suitably interweaving all of them does.
United we stand. With this in mind, we now present our simple and efficient algorithm (Algo- rithm 1 CAPE) whose ROI converges (with high probability) to the best one in a finite family of policies. We will later discuss how to extend the analysis even further, including countable families of policies. Our algorithm performs policy elimination (lines 5 for a certain number of tasks
"We chose & & for the sake of concreteness. All our results can be straightforwardly extended to arbitrary Th S Dr by simply assuming without loss of generality that & + Dr is monotone and replacing i with Ds.
6

---

(Iine[]) or until single policy is left (line 6
After that, it runs the best policy left in the set (line) 7 breaking ties arbitrarily for all remaining tasks. During each policy elimination step, the algorithm oversamples (line 2) by drawing twice as many samples
it would suffice to take its decision accept [ma (x,, n) x,, (at line These extra samples are used compute rough estimates of rewards and costs of all potentially optimal policies and more specifically to build unbiased estimates of these rewards. The test line 4 has the only purpose of ensuring that the denominators 2,2 (A) at line 5 are bounded away from zero that all quantities are well-defined.
Algorithm 1: Capped Policy Elimination (CAPE)
Input: finite policy set II, number of tasks N, confidence parameter 8, exploration cap Nex Initialization; let C {1..... }} be the set of indices of all currently optimal candidates for task n = ,, Nex do draw the first 2C, samples 1,,1,--- X,, 2m,x((C of X..
make the decision accept(TTaat (Taax(C..) (X x,.)
if ni 2 2K In(K Nox/8) then let Ca+1 f- Cn \. C, where
C² (k On
( (k)
0 and f (k)/2, (k) < (, ()). for some j E Cn)
(k) 0 and Fn (k)/2t (k) <fT(j)/ (i). for some j E CC.)
ma
X X mm,)ax(Cmm)+ accept (Th (Xm): Xm) + V In
2 4KNex
(k)
(5)
π1
max Cm)
1
12
1 4KNx
a (k)
The (x m) + (k: 1)
In
(6)
n2
2n
if |C = then let F+ (k)) + p (k),
No.. (k)) t- (,t (k), CNa+1 &o Cn+1, break
run policy ny for all remaining tasks, where
argmnax (F (K)/ON (k))
if if (k) 0 for some k E CNet+1
EE E
KECNox11
(7)
argmax (F (x) (R:)
if (k) for all E CN.+t1
RECNo+11
As usual in online learning, the gap in performance between optimal and sub-optimal policies is complexity parameter. We define it as = ming4k* (ROI( -RO(())))) where we recall that k E argmax, ROT(TR) is the index of an optimal policy. Conventionally, we set 1/0 = C0.
Theorem 1. If II finite set of K policies, then the ROI of Algorithm 7 run for N tasks with exploration cap Nex | |2/33] and confidence parameter E (0, converges to the optimal ROI(TT-), ), with probability at least 8, at a rate
K
K
Ry δ min
A'N
N1/3
as soon as N 2 K3 (where the δ notation hides only logarithmic terms, including log(1/8) term).
Proof sketch. This theorem relies on four technical lemmas (Lemmas 5 whose proof's are deferred Section B the Supplementary Material.
With concentration argument (Lemma we leverage the definitions of f.# (k), a, (lk) and the i..dd assumptions on the samples Xn,s to show that, with probability at least 8, the event
(k) reward(Mi) S f,t (k)
and दn (k) < cost (Tx)
Moore precisely, ties should be broken in a measurable way, e.g., uniformly at random. We do not insist on this point here, but the interested reader might see (Cesari and Colomboni 2021 Section 2.4) for a more thorough discussion on this topic.
7

---

oceurs simultaneously for all n S Nex and all k S max(Cn). For the rewards, the key is oversam
pling, because accept(TT (Tx m), mm) in eq.q. 5 depends only on the first h: S max(Cm) samples of
Xm m and therefore independent of Xm,max ++ for all Assume now that (8) holds.
If > 0 (i.c., if there is unique optimal policy), we then obtain (Lemma 6 that suboptimal policies
are eliminated after at most Noxx tasks, where N%x I 288 K (n(4 Nexe/ /oss///////// / + +1. To prove it we
show that a confidence interval for ROI(T+)) = reward (T&a) cost (T)) is given by
Py (R:) [ (R) 0} + Pin (2) I(F Cn (h)
(k) < 00, F (k) I[ (R) 2 0
(k)
1 (N) < <0]
En (k)
En (k)
CR (A)
we upper bound its length, and we compute an Nox such that this upper bound is smaller than A/2.
Afterwards, we analyze separately the case in which the test at line 6 is true for some task N'x S Nex
and its complement (i.e., when the test is always false).
In the first case, by 8 there exists unique optimal policy, i.e., we have that A > 0. This is where the policy-elimination analysis comes into play. We can apply the bound above on Nox. obtaining a deterministic upper bound N on the number Nºx of tasks needed to identify the optimal policy. Using this upper bound, writing the definition of Rv and further upper bounding (Lemma yields
(2K + 1)Nex (2K + (288 (K/ A)² (nKK NeeN/N/ /8) + 1)
RN S min
N
N
Finally, we consider the case in which the test at line ils false for all tasks n S Nex. and line is executed with CNa++1 containing two or more policies. This is covered by worst case explore- then-commit analysis. The key idea here is to use the definition of k'' in Equation (7) to lower bound
(oward((Tg)) in terms of reward (T&+) /cost (T This, together with some additional technical
estimations (Lemma 8 leads to the result.
L
As we mentioned in Footnote 4 if we swap the bounds on durations т S k with generic Th S Da (with k r> Dr non-decreasing), the result would still hold, but the right-hand side would scale with DR rather than K. To see why, note that in our current presentation when the policy set II is finite, K plays the role of both the cardinality of IT and a uniform upper bound on their durations, where the latter role the most important. The key intuition on why this is the case is that whenever some data are sufficient to evaluate a policy k, it can also be used to evaluate all policies k' S. k for free. In particular, case where many (even infinitely many, in principle) of the durations of the policies shared the same upper bound DR. our algorithm would have a very easy time in narrowing down the best one because, using only Dj samples, it could keep updated a large number of policy estimators all at once.
5 Competing Against Infinitely Many Policies (ESC-CAPE)
Theorem I provides theoretical guarantees on the convergence rate Ry of CAPE to the best ROI of finite set of policies. Unfortunately, the bound becomes vacuous when the cardinality K of the policy set is large compared to the number of tasks N. It is therefore natural to investigate whether the problem becomes impossible in this scenario.
Infinite sets of policies. With this goal in mind, we now focus on policy sets II Tak = ((Tx, accept) kEe as in the previous section, with K N rather than K {1, K}. (K).
We will show how such a countable set of policies can be reduced to finite one containing all optimal policies with high probability (Algorithm 2 ESC). After this is done, we can run CAPE on the smaller policy set, obtaining theoretical guarantees for the resulting algorithm.
Estimating rewards and costs. Similarly to eqs. (5 and (6), we first introduce estimators for our target quantities. If at least 2k samples are drawn during each of n2 consecutive tasks n + 1,,..., n1 + 722, we can define, for all & >> 0, the following lower confidence bound on reward
P (1L1, 112, 8)
1
mi t
Σ
Xn,k+i k
accept (X,) Xx.) 22
(10)
122
If at least Th Xx,, ) samples are drawn during each of mo consecutive tasks no + +,...., ,...., can define the following empirical average of cost(Te):
no + mg, we
(n mo) (Ta (X x1)+)))+++0)) +... +..++ + (o)) /mo
(11)
8

---

A key observation. The key idea behind Algorithm 2 (ESC) is simple. Since all optimal poli- cies Tg- have to satisfy the relationships reward /o 1 1/cost(TT)), ), then, for all policies Te with positive reward the cost of any optimal policy Tk* must satisfy the relationship cost((T=)) S cost (T&)) /reward((T)))
I reward( //ost)/C v
other words, optimal poli- cies cannot draw too many samples and their cost can be controlled by estimating the reward and cost of any policy with positive reward.
We recall that running policy (r, 0) during a task n means drawing the first r(X,, samples of X, (X,,,, Xn.2....) and always rejecting Mn. regardless of the observations.
Algorithm 2: Extension to Countable (ESC)
Input: countable policy set II, number of tasks N, confidence parameter 6, accuracy levels (En)n
Initialization: for all j, let my + [mm + /2e31 and M, = m2 +... + mj
for j = 1, 1.2.... do
2 run policy (2 20,200 0) for my tasks and compute Fag + F2 (M m, E5) as in (T))
if F2j > 0 then let jo 4 and Ko f- 2/ ......d do
for | jo + 1. jo + 2....
5
run policy (T2,, 0) for my tasks and compute 02' < O21 (Mi-1, (-,1-,,,)) mi) as in
c2 > 2 e1 + ko/fie then let f1 t I and return K <- 2
Thus, Algorithm 2 (ESC) first finds a policy Th, with reward((T.)) > 0 (lines 13 memorizing = 1/ROI( By the argument
an upper estimate RioFFeo of the ratio (os((Ta./rrearrd(ee above, this estimate upper bounds the expected number of samples cost(TTR-) drawn by all optimal policies TT. Then ESC simply proceeds to finding the smallest (up to factor of 2) K such that cost(Tx) 2 Ko/Fk, (lines 6) Being ko/ ko/Fk, 2 cost( /reward((Tk)) 2 cost(Tg-) by construction, the index K determined this way upper bounds ks* for all optimal policies Tg.. (All the previous statements are intended to hold with high probability.) This is formalized in the following key lemma, whose full proof we defer to Section the Supplementary Material.
Lemma 2. Let IT be countable set of policies. If ESC is run with d E (0, 1), E1, E (0, 1). and halts returning K, then 1:* S K for all optimal policies Tg- with probability least 6.
Before proceeding with the main result of this section, we need a final lemma upper bounding the expected cost of our ESC algorithm. This step crucial to control the total ROI because in this setting with arbitrarily long durations, picking the wrong policy even once is, in general, enough to drop the performance of an algorithm down to essentially zero, compromising the convergence to an optimal policy. This is another striking difference with other common online learning settings like stochastic bandits, where single round has negligible influence on the overall performance of an algorithm. To circumvent this issue, we designed ESC so that it tests shorter durations first, stopping as soon as the previous lemma applics, and a finite upper bound K on k* is determined.
Lemma 3. Let IT be a countable set of policies. If ESC is run with d E (0, E1,62,... E (0. 1), and halts returning K, then the total number of samples draws before stopping (i.e., cost) is upper bounded by ((K/2) ((KK/))log()/))))
where = =
Elog, K).
Proof. Note that, by definition, e min(f1,62........ .n > O. Algorithm 2 (ESC) draw samples only when lines 2 or 5 are executed. Whenever line 2 is executed (j 1.....Ju .jo) the algorithm performs m, tasks drawing 2 2 samples each time. Similarly, whenever line 5 is executed (1= jo + ,,...,ji the algorithm draws at most 2' samples during each of the my tasks. Therefore, recalling that j1 = log, K, the total number of samples drawn by ESC before stopping is at most
Σ 2-2 my +
j0
Σ 1=
jn
2'm
2
51 2'm 2
1 2e
In
fi
+ 1)
8
1=1
The ESC-CAPE algorithm. We can now join together our two algorithms obtaining new one, that we call ESC-CAPE, which takes as input countable policy set II, the number of tasks N, confidence parameter 8, some accuracy levels E2, and an exploration cap Nex. The joint

---

algorithm runs ESC first with parameters II, 51, E2,.... Then, if ESC halts returning K, it runs CAPE with parameters {(TE, acceptt)
N, 6, Nex.
Analysis of ESC-CAPE. Since ESC rejects all values pn. the sum of the rewards accumulated during its run is zero. Thus, the only effect that ESC has on the convergence rate Rx of ESC- CAPE is an increment on the total cost in the denominator of its ROI. We control this cost by minimizing its upper bound in Lemma [ This is not a simple matter of taking all E large as possible. Indeed, if all the ej 's are large, the if clause at line 3 might never be verified, because the conditional checks whether a confidence interval (for reward T22) )) of length ((s) sits to the right of the origin. In other words, the returned index K depends on and grows unbounded in general as E approaches 1/2. This follows directly from the definition of our lower estimate on the rewards (TO). Thus, there is a trade-off between having a small K (which requires small E 's) and a small 1/E" to control the cost of ESC (for which we need large E 's). A direct computation shows that picking constant accuracy levels e = N-1/3 for all j achieves the best of both worlds and immediately gives our final result.
Theorem 4. If is a countable set of policies, then the ROI of ESC-CAPE run for N tasks with confidence parameter E (0, 1), constant accuracy levels Ej N W11/3, and exploration cap Nex = [2 converges to the optimal ROI(T()) ), with probability at least 8, at a rate
RN = = ( 1+ KI{ESC halts returning K}
N1/3
where the Ô notation hides only logarithmic terms, including a log(1/5) term.
Note that the previous bound depends on the algorithm- dependent quantity K. While this might seem somewhat nonconventional, simple argument gets rid of this issue. Indeed, if lower bound X on the ROI of an optimal policy were known beforehand, then it would be easy to control K by estimating the cost of policies 2 for increasing values of (as in ESC). In this case, K would be upper bounded by the number of policies whose cost is smaller than 2/A" (say). This quantity is now constant (in N; it depends only on the distribution D and the set of policies II, playing the role of a complexity measure of the problem instance). If X is unknown, one can first estimate it up some multiplicative constant (say, 1/2), with high probability. Again, we can do this at a constant cost (depending only on the instance (TI, D)) via multiplicative Chernoff bound.
6 Conclusions
After formalizing the problem of ROI maximization in repeated decision making, we presented an algorithm (ESC-CAPE) that is competitive against infinitely large policy sets (Theorem[4). For this algorithm, we prove convergence rate of order 1/N1/3 with high probability. To analyze it, we first proved a convergence result for its finite counterpart CAPE (Theorem []. which is of independent interest. Notably, this finite analysis guarantees a significantly faster convergence of order 1/N on easier instances in which there is positive gap in performance between the two best policies.
A Acknowledgments and Disclosure of Funding
An earlier version of this work was done during Tommaso Cesari's Ph.D. at the University of Milan. Nicolò BesacBianchi and Tommaso R. Cesari gratefully acknowledge partial support by Criteo AI Lab through Faculty Research Award and by the MIUR PRIN grant Algorithms, Games, and Digital Markets (ALGADIMAR). Nicolò Cesa-Bianchi was also supported by the COST Action CA16228 "European Network for Game Theory" (GAMENET) and by the EU Horizon 2020 ICT-48 research and innovation action under grant agreement 951847, project ELISE This work has also benefited from the AI Interdisciplinary Institute ANITI ANITI funded by the French "Investing for the Future- PIA3" program under the Grant agreement n. 19R-119-P3A--AA was supported in part by grant from the European Research Council (ERC) under the European Union sHorizon 2020 research and innovation program (grant agreement No. 882396). by the Israel Science Foundation
Yishay Mansour
number 993/17), Tel Aviv University Center for AI and Data Science (TAD), and the Yandex Initiative for Machine Learning at Tel Aviv University. Vianney Perchet was supported by a public grant as part of the Investissement d' d'avenir project, reference ANR-II-LABX- 0056-LMH, LabEx LMH, in a joint call with Gaspard Monge Program for optimization, operations research and their interactions with data sciences. Vianney Perchet also acknowledges the support of the ANR under the grant ANR-19 19-CE23-0026.
10

---

References
Saeed Alaei, MohammadTaghi Hajiaghayi, and Vahid Liaghat. 2012. Online prophet-inequality matching with applications to ad allocation. In Proceedings of the 13th ACM Conference on Electronic Commerce. Association for Computing Machinery, New York, NY, USA, 18-35.
Noga Alon, Nicolò Cesa-Bianchi, Ofer Dekel, and Tomer Koren. 2015. Online Learning with Feedback Graphs: Beyond Bandits. In Proceedings of The 28th Conference on Learning Theory (Proceedings of Machine Learning Research, Vol. 40), Peter Grünwald, Elad Hazan, and Satyen Kale (Eds.). PMLR, Paris, France, 23-35.
Peter Auer, Nicolo Jesa-Bianchi, and Paul Fischer. 2002. Finite-time analysis of the multiarmed bandit problem. Machine learning 47, 2-3 (2002), 235-256.
Eduardo M. Azevedo, Alex Deng, Jose Luis Montiel Olea, Justin Rao, and E. Glen Weyl. 2018. The A/B Testing Problem. In Proceedings of the 2018 ACM Conference on Economics and Computation (Ithaca, NY. USA) (EC 18), Association for Computing Machinery, New York, NY, USA, 461-462. htttps://di..rgg 10. http://ooo1.0001/1001111///11969
Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. 2018. Bandits with knap- sacks. Journal of the ACM (JACM) 65, (2018), 1-55.
Sébastien Bubeck and Nicolo Cesa-Bianchi. 2012. Regret analysis stochastic and nonstochastic multi-armed bandit problems. Foundations and Trendy@ in Machine Learning 5, (2012). 1-122.
Semih Cayci, Atilla Eryilmaz, and Rayadurgam Srikant. 2019. Learning to control renewal processes with bandit feedback. Proceedings of the ACM Measurement and Analysis of Computing Systems 3, 2 (2019), 1-32.
Semih Cayci, Atilla Eryilmaz, and R Srikant. 2020. Budget- Congtt--onsttiined Bandits over General Cost and Reward Distributions. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics (Proceedings of Machine Learning Research, Vol. 108), Silvia Chiappa and Roberto Calandra (Eds.). PMLR, Online, 4388-4398.
Tommaso R Cesari and Roberto Colomboni. 2021. nearest neighbor characterization of Lebesgue points in metric measure spaces. Mathematical Statistics and Learning 3, 1 (2021), 71-112.
Christopher F Chabris, Carrie Morris, Dmitry Taubinsky, David Laibson, and Jonathon Schuldt. 2009. The allocation of time in decision-making. Journal of the European Economic Association 2-3 (2009), 628-637.
Shiyun Chen and Shiva Kasiviswanathan. 2020. Contextual Online False Discovery Rate Control. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics (Proceedings of Machine Learning Research, Vol. 108), Silvia Chiappa and Roberto Calandra (Eds.). PMLR, Online, 952-961.
Jose Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, and Tjark Vredeveld. 2019. Recent developments in prophet inequalities. ACM SIGecom Exchanges 17, (2019), 61-70.
Hossein Esfandiari, MohammadTaghi HajiAghayi, Brendan Lucier, and Michael Mitzenmacher. 2019. Online pandora's boxes and bandits. Proceedings of the AAAI Conference on Artificial Intelligence 33, 01 (2019), 1885-1892.
P.W. Farris, N. Bendle, P.E. Pfeifer, and D. Reibstein. 2010. Marketing Metrics: The Definitive Guide to Measuring Marketing Performance. Pearson Education, New York.
Dale L. Flesher and Gary John Previts. 2013. Donaldson Brown (1885-1965 1965): The power of an individual and his ideas over time. The Accounting Historians Journal 40, 1 (2013), 79-101.
Dean P Foster and Robert A Stine. 2008 a-investing: a procedure for sequential control of expected false discoveries. Journal of the Royal Statistical Society: Series (Statistical Methodology) 70, (2008), 429-444.
11

---

Aurélien Garivier and Emilie Kaufmann. 2021. Nonasympiotic sequential tests for overlapping hypotheses applied to near-optimal arm identification in bandit models. Sequential Analysis 40, (2021), 61-96.
Christopher R Genovese, Kathryn Roeder, and Larry Wasserman. 2006. False discovery control with p-value weighting. Biometrika 93, (2006), 509-524.
Thomas L Griffiths, Frederick Callaway, Michael B Chang, Erin Grant, Paul M Krueger. and Falk Lieder. 2019. Doing more with less: meta-reasoning and meta-learning humans and machines. Current Opinion in Behavioral Sciences 29 (2019), 24-30.
Nicholas Hay, Stuart Russell, David Tolpin, and Solomon Eyal Shimony. 2012. Selecting Computa- tions: Theory and Applications. In Proceedings of the Twenty- Eighth Conference Uncertainty in Artificial Intelligence (Catalina Island, CA) (UAI' 12). AUAI Press, Arlington, Virginia, USA, 355.
Philipp Heesen and Aroold Janssen. 2016. control. Journal of Statistical Planning and Inference 168 (2016), 38-51.
Dynamic adaptive multiple tests with finite sample FDR
Lalit Jain and Kevin Jamieson. 2018. Firing Bandits: Optimizing Crowdfunding, In Proceedings of the 35th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 80), Jennifer Dy and Andreas Krause (Eds.). PMLR. Stockholmsmässan, Stockholm Sweden, 2206-2214.
Adel Javanmard, Andrea Montanari, al. 2018. Online rules for control of false discovery rate and false discovery exceedance. The Annals of statistics 46, 2 (2018), 526-554.
Ramesh Johari, Pete Koomen, Leonid Pekelis, and David Walsh. 2017. Peeking at A/B Tests: Why Matters, and What to Do about It. In Proceedings of the 23rd ACM SIGKDD International Confer- ence on Knowledge Discovery and Data Mining (Halifax, NS, Canada) (KDD 117. Association for Computing Machinery, New York, NY, USA, 1517-1525.
Ramesh Johari, Pete Koomen, Leonid Pekelis, and David Walsh. 2021. Always Valid Inference: Continuous Monitoring of A/B Tests. Operations Research (2021).
Robert Kleinberg, Bo Waggoner, and E. Glen Weyl. 2016. Descending Price Optimally Coordinates Search. In Proceedings of the 2016 ACM Conference on Economics and Computation (Maastricht, The Netherlands) (EC 166.. Association for Computing Machinery, New York, NY, USA, 23
Ron Kohavi, Alex Deng, Brian Frasca, Toby Walker, Ya Xu, and Nils Pohlmann. 2013. Online Controlled Experiments at Large Scale. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (Chicago, Illinois, USA) (KDD '13). Association for Computing Machinery, New York, NY, USA, 1168-1176.
Ang Li and Rina Foygel Barber. 2019. Multiple testing with the structure-adaptive Benjamini- Hochberg algorithm. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 81, 1 (2019), 45-74.
Brendan Lucier. 2017. An economic view of prophet inequalities. ACM SIGecom Exchanges 16, 1 (2017), 24-47.
Aaditya Ramdas, Fanny Yang, Martin J. Wainwright, and Michael I. Jordan. 2017. Online Control of the False Discovery Rate with Decaying Memory. In Proceedings of the 31st International Conference Neural Information Processing Systems (Long Beach, California, USA) (NIPS' 17). Curran Associates Inc., Red Hook, NY, USA, 6655-5664.
David S. Robertson and James M. S. Wason. 2018. Online control of the false discovery rate in biomedical research. arXiv:1809.07292 [s]
Dinah Rosenberg, Filon Solan, and Nicolas Vieille. 2007. Social learning one-arm bandit problems. Econometrica 75, 6 (2007), 1591-1611.
12

---

Sven Schmit, Virag Shah, and Ramesh Johari. 2019. Optimal Testing in the Experiment-rich Regime. In Proceedings of Machine Learning Research (Proceedings of Machine Learning Research, Vol. 89), Kamalika Chaudhuri and Masashi Sugiyama (Eds.). PMLR, Naha, Okinawa, Japan, 626-633.
Aleksandrs Slivkins. 2019. Introduction to Multi-Armed Bandits. Foundations and Trends@ in Machine Learning 12, 1-2 (2019), 1-286.
John Wilder Tukey. 1953. The Problem of Multiple Comparisons.
Abraham Wald. 1944. On cumulative sums of random variables. The Annals of Mathematical Statistics 15, (1944), 283-296.
Martin L. Weitzman. 1979. Optimal Search for the Best Alternative. Econometrica 47, (1979). 641-654.
Ziyu Xu, Ruodu Wang, and Aaditya Ramdas. 2021. unified framework for bandit multiple testing. arXiv preprint arXiv:2107.07322 0 (2021).
Fanny Yang. Aaditya Ramdas, Kevin G Jamieson, and Martin Wainwright. 2017. A framework for ((atia)) Testing with Online FDR Control. In Advances in Neural Information Processing Systems, I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.), Vol. 30. Curran Associates, Inc., Long Beach, CA, USA, 5957-5966.
13

---

Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] [Yes]. [No] or [N/A]. You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
Did you include the license to the code and datasets? [N/A]
Did you include the license the code and datasets? [N/A]
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Introduction
(c) Did you diseuss any potential negative societal impacts of your work? [N/A] We do not believe that theoretical analysis could have any negative impacts on society
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Section describes the setting, finite (resp., infinite) policy sets are introduced at the beginning of Section 4 (resp., Section 5), and everything else is included in the statements of lemmas and theorems
(b) Did you include complete proofs of all theoretical results? [Yes] Some technical details are deferred to the Supplementary Material
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releusing assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
14

---

(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "qX0Vrj6EDkK", "reviewer": "Reviewer_etbW", "summary": "This paper considers a sequential decision process that models that of ideation. At any time an agent has access to a reward distribution and they can either take a sample from the distribution, accept the distribution and receive a reward equivalent to the mean of the distribution, or reject the distribution and receive the reward of 0. The goal of the agent is to find a policy that maximizes their expected ROI, that is the ratio of the total reward of their policies over the total cost (expected number of samples a policy takes).", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nOverall I thought the paper was interesting and studied an interesting problem statement. I did have a few concerns. \n\n1. Organizational comments: I found the background material in Section 2 a bit difficult to parse since I had not fully understood the precise definition of ROI by the time I read this section. Maybe the author can switch the order of 2 and 3? \n\n2. My main theoretical concern is regarding the guarantees of Escape in Theorem 4. The K given in the statement of the upper bound is not explicit and hence the bound seems somewhat useless as a result. I also struggled to understand the tradeoff between $\\epsilon$ and $K$ in ESC. Presumably, it depends on the underlying distribution? Maybe the authors can clarify?\n\n3. Finally, the authors imply that the inability to compute an unbiased estimate of a policy is a significant obstacle to overcome. However, as they show, it’s relatively easy to oversample and build an estimator. This seems more of a remark (albeit an interesting one) than a real obstacle to highlight as a contribution.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please see above. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "FL3A0dipHyf", "reviewer": "Reviewer_2mFe", "summary": "Paper considers a return on investment problem. On round n a task arrives parameterized by a mean parameter mu_n. The learner can observe realizations X_{n} := (X_{n,1},X_{n,2},…) where each is a random variable with mean mu_n as many times as she likes. She uses a policy pi that defines a stopping time tau(X_n) that decides when to stop observing the sequence and then outputs a decision accept(X_n) in {0,1}. The RIO is defined as E[ sum_{n=1}^N mu_n accept(X_n) ] / sum_{n=1}^N E[ tau(X_n) ]. Given a finite set of policies, one can consider the regret as the difference between the optimal policy and the sequence of policies executed by the learner.\n\nA somewhat arbitrary set of policies is considered, with the sole restriction that the kth policy pi_k := (tau_k, accept_k) satisfies tau_k(X_n) <= k almost surely, for all k in a finite set or the natural numbers. The countable set case follows by finding an upper bound K on k*, the index of the optimal policy, and then running their finite set algorithm over K policies. \n\nIn the finite setting, if K = O(N^(1/3)) then their regret goes down like K/N^{1/3}. In the countable setting, the regret also scales like this, where now “K” is a random variable returned by their algorithm.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Apologies in advance for the brevity of this emergency review. I read the main text in full and also looked at select parts of the appendix (mostly focusing on the impossibility result, detailed explanations of policy sets deferred to the appendix, and verifying the logic of the major steps of the proofs). \n\nStrengths\n- Proposed a compelling problem setting\n- Connections to related work is comprehensive as far as I am aware\n- Clever algorithm to design that combines clearly described concepts\n- Generality of policy set\n\nWeaknesses:\n- Restrictiveness of policy set?\n- Sample complexity seems to have a bad dependence on K. But without a lower bound it is impossible to know. \n- Potentially vacuous result in the countable policy class setting.  \n \n\nThe algorithm appears primarily motivated by the impossibility result of appendix E, namely, that there exists a policy for which constructing an unbiased estimator of its value by just inspecting its trajectories is impossible. Consequently, the algorithm rolls out each policy at least twice as long as it needs, using the first set of samples to estimate the behavior of the accept rule, and the second set of samples to estimate the nth tasks mean mu_n. \n\nThe algorithm exploits the fact that the data from k samples can evaluate policy k (since tau_k <= k), but can also be used to evaluate all policies k’ <= k for free. There are a few algorithmic techniques exploited that are well-described in section 4. The novelty is in the algorithm design which combines these different ideas, rather than the straightforward analysis.\n\nComments requested from authors:\n- The expectation of the ratio of rewards to costs seems more natural than the ratio of their expectations. In the IID setting, presumably these are close, did you consider how things would change if the expectation of the ratio were considered instead?\n- The policy set seems both very general (i.e., arbitrary line-crossing stopping times and decision rules) but also restrictive since it is assumed tau_k <= k for all k. Of course, if an infinite set of policies is considered one can always parameterize an arbitrary set of policies by just taking k larger and larger. However, your sample complexity depends on k to have boundedness of the costs, so we cannot actually do this for free. I do not believe Footnote 3, which describes how tau_k <= k can be replaced with tau_k <= D_k fixes this issue since it is not straightforward how the theorems would change if D_k = D_{k’} for many k,k’ and |Pi| >> max_k D_k potentially. The reason why I bring this up is that a class that seems particularly natural would be all stopping times defined by all possible linear boundaries (or monotonically increasing curves), each with their own maximum stopping time D_k. Thus, you may have sub-classes of policies Pi_1,Pi_2,… where the maximum within each sub-class is D_k, but Pi_k may contains many different stopping times. Can you framework be expanded to handle such classes? \n- The result of the infinite setting appears somewhat vacuous to me since the returned K is a random variable. And while it is proved that K >= k*, no upper bound on K appears (e.g., in terms of k*) as far as I know, and this K appears in the final theorem. It is very strange to see a theorem that depends not on parameters of the problem, but the behavior of the particular algorithm. \n\nI like this problem statement a lot and enjoyed reading the paper. Given satisfactory clarifications to the above questions, I would be happy to raise my score. But at this point I’m on the fence if these weaknesses are real. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "95NXvWtSzO_", "reviewer": "Reviewer_secW", "summary": "This paper studies the problem of Return On Investment (ROI) maximization in repeated decision-making. The main contributions are as follows.\n\nThe authors first propose a framework for ROI maximization in Sec. 3. The main contribution here is to formulate an objective/regret in Eq. (2), which is a ratio of reward over cost. The problem is then to maximize the average reward-cost ratio of $N$ tasks, where each task's value is an i.i.d. sample from a true $\\mu$.\n\nWhen the policy class is finite with $K > 0$ policies, the authors propose the Capped Policy Elimination (CAPE) in Algorithm 1, and show that its convergence rate is $\\tilde{O}(1/N^{1/3})$ in Theorem 1. The main idea is to make a decision first, then use oversampling to get i.i.d. samples of the reward and cost, and then use concentration inequality to estimate the performance gap $\\Delta$ of policies to do policy elimination.\n\nWhen the policy class is countably infinite, the authors propose the : Extension to Countable (ESC) in Algorithm 2 to reduce the policy class to finite. The main idea is to estimate the upper bound of the optimal policy's cost, such that any optimal policy would take smaller number of observations. Then CAPE is used on the reduced policy class, and a similar $\\tilde{O}(1/N^{1/3})$ convergence rate upper bound is shown in Theorem 4.\n\n", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Disclaimer: My sincere apologies for the late review, since I have been assigned as an emergency reviewer for this paper. This makes it possible that I could misunderstand some details of this work.\n\nOverall, the presentation is clear and easy to follow. The motivation is clear and the intuition of the algorithm makes sense. The proofs are mostly correct as I have checked.\n\nI have the following questions that I would ask the authors to clarify.\n\n1. I am confused with the assumption/setting of \"the value $\\mu_n$ of the current innovation is drawn i.i.d. according to $\\mu$\". \n\nDoes this mean the $N$ tasks/innovations are actually all copies of a single task with true value $\\mu$, and the goal is then to estimate the one true value $\\mu$? If this is the case, this seems to be easier than a bandit problem, where the true values of all the actions are independent? Or this can be value as a \"weird\" specific bandit problem: we have different actions, but their rewards are all noisy copies of one true value. This assumption seems unnatural to my understanding. Please comment on this and what would be the result if this assumption is removed?\n\n2. There seems to be another possibility of view this problem as an bandit problem: each policy is an action, and each action's value is then the policy's reward-cost ratio. Then the problem is to choose the best action (policy) with the highest true value. This seems to make more sense. Please clarify or correct my understanding.\n\n3. If my understanding is correct, then I feel the techniques are standard and the results are not very surprising. The reward is bounded in between $[-1, 1]$, and the cost is integers. This makes the problem a bit different but very similar to just estimating the reward: since the cost is unbounded positive integer, one just need to estimate the reward when the cost is not too large. Otherwise any large cost would rule out the optimal policy since the reward is a bounded value.\n\nTherefore the optimal ratio can be figured out just using estimation of both the numerator and denominator as the authors did. This makes it like an extension of explore-then-commit strategy, using empirical means and concentration inequalities. Although oversampling is used to get i.i.d. estimation, the main idea is basically do mean estimation for both reward and cost.\n\nGiven there is no lower bound (the authors conjectured that their upper bound is optimal), it would be more convincing if the authors could study other designs similar to the UCB algorithm in bandit to see if a better upper bound could be obtained, or directly show some information-theoretic lower bound using the related results as noted.\n\n4. The ESC strategy looks interesting, but it seems it highly relies on the fact that the reward is bounded and cost is positive integer (as also noted the optimal policy cannot have too large cost). Is it possible that for other cost functions (which are not necessarily like positive integers here), where there are countably infinite actions with both bounded reward and bounded cost, a similar procedure of reducing the policy class to a finite number can be designed?\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The results are theoretical, and I did not see any potential negative societal impact of this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers a variant of a sequential selection problem under "partial feedback." This is formulated and presented as a variant of an ROI problem. The main result is an algorithm for implementing the selection rule and its convergence rate analysis. The main difficulty is discerning when to stop the experimentation and move to the next stage. Two of the reviewers are positive about the paper and one is more negative in his/her remarks. Generally there is an appreciation for the problem being studied and its broad relevance and interest. (A good chance to thank all referees for their invaluable input.)  I think this is an interesting paper and has the potential to be relevant for NeurIPS audience. I will go along with the two more positive reviews, although my personal view on the paper is that it still has some major issues and I believe it to be a borderline accept at best. I hope some of these issues  can be addressed in the revision.

1. In my view the general "motivating story" as well as the selected title overpromises and this sets the tone for the paper.  The sequential technology testing story is indeed something many companies engage in, but I seriously doubt whether any reasonable practical process resembles the objectives in the paper where the company has a pre-defined set of policies and it tries to achieve result close to the "best" in this class. This type of logic, similar to the best action in hindsight, and the "expert" paradigm in ML is more of theoretical analysis value. The latter is a meaningful analysis framework, but connecting it through this motivating example is tenuous at best. It leaves a bit of a sense of an answer searching for a problem. While the paper studies online decision making, certainly the key results only pertain to a rather restricted canvass in that space. For example,  multistage  A/B testing may better reflect what the paper is modeling and analyzing.  I would hope the authors can address this in their revision. 

2. If the idea is to connect to such practical settings, why not take a simple class of parametrized policies and analyze that? The problem can be fairly  easily formulated as a sequential selection problem for which there is rich literature and plenty of heuristics to choose from. For example, in such settings it is common, as in classical PAC learning, to select a tolerance parameter, say delta, and study the run length of sequential experiments needed to conclude with high probability  that the true mean is positive (or exceeds, some epsilon, say). It is then possible to study this as a heuristic with epsilon set to shrink with sampling horizon. This would be somewhat akin to a modified best arm identification problem, but with the added element of having multiple stages in the game (see further comments below).  The current formulation seems to me a bit contrived, especially that it effectively requires a finite cardinality policy class. (The extensions discussed in the paper notwithstanding.) 

3. I also feel the placement of the contribution relative to literature is sketchy in parts. The problem is in essence a sequential selection problem. Perhaps i'm missing something, but I don't see a direct connection to the prophet inequality literature. That literature  either seeks to approximate state-dependent stopping rules with single (or multiple) threshold rules, or attempts to bound losses of expected optimal performance relative to the best offline solution in a horizon independent manner. If this is supposed to represent the sequential selection literature it is not the best connective fabric. There is vast literature on optimal stopping problems that have multiple stages that are far more relevant for example. The connection to the bandit problem is also superficial. Each stage is more connected to a best arm identification in an environment where there is a known alternative that has mean zero. As such the complexity analysis in Emilie  Kauffman's work, in particular the recent paper with Garvier on sequential hypothesis testing with overlapping hypotheses seems more relevant.   Rather than screening less relevant strands I would suggest to focus more on the core areas that intersect with this problem and then clearly explain how the paper adds to existing results. (As an additional example, the recent papers on A/B testing by Schmit et al and Azevedo et al are mentioned in passing only...) 

4.  The absence of a lower bound argument leaves the analysis incomplete (the authors' conjecture aside). But I recognize this is beyond the scope of the revision. 

Finally, in conjunction with 1.) I believe assigning  a more modest (and descriptive)   title and packaging aligned with contribution would also be a welcome modification in the revision. 
Decision: Accept (Poster)