Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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).
main_review: 
Overall I thought the paper was interesting and studied an interesting problem statement. I did have a few concerns. 

1. 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? 

2. 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?

3. 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.


limitations_and_societal_impact: Please see above.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies the problem of Return On Investment (ROI) maximization in repeated decision-making. The main contributions are as follows.

The 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$.

When 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.

When 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.


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.

Overall, 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.

I have the following questions that I would ask the authors to clarify.

1. I am confused with the assumption/setting of "the value $\mu_n$ of the current innovation is drawn i.i.d. according to $\mu$". 

Does 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?

2. 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.

3. 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.

Therefore 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.

Given 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.

4. 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?


limitations_and_societal_impact: The results are theoretical, and I did not see any potential negative societal impact of this work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.

A 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. 

In 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.
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). 

Strengths
- Proposed a compelling problem setting
- Connections to related work is comprehensive as far as I am aware
- Clever algorithm to design that combines clearly described concepts
- Generality of policy set

Weaknesses:
- Restrictiveness of policy set?
- Sample complexity seems to have a bad dependence on K. But without a lower bound it is impossible to know. 
- Potentially vacuous result in the countable policy class setting.  
 

The 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. 

The 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.

Comments requested from authors:
- 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?
- 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? 
- 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. 

I 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. 
limitations_and_societal_impact: N/A
review_title: null

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)