Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies the continuum-armed bandit problem with additional requirement that the selected arms/actions must be monotone sequences over the course of the game. With this requirement, the authors first show that simply considering a continuous reward function (namely, an unknown function that maps the action to the reward) will suffer linear regrets, in contrast to the sublinear regret $O(T^{2/3})$ in the literature without the monotonicity requirement. 
Then the authors consider a more structured reward function which is quasiconcave. The authors then provide an algorithm and prove that a regret $O(T^{3/4})$ of this algorithm for this class of functions. Furthermore, this regret is tight as authors also provide a matching lower bound. Lastly, the authors conduct numerical studies to compare the regret of proposed algorithm with a few benchmark, validating the analysis. 

main_review: Originality, quality, and significance:

Though motivation behind the problem is well-defined, I’m not sure the setting discussed in this paper is a stand alone contribution as an earlier paper [1] has already studied this setting but with concave reward function and showing a regret with order $O(T^{1/2})$. For this paper, the algorithm, together with the idea, is straightforward, which is nice, and the theoretical analysis seems also to be correct. 

Clarity: 

The paper is overall well written and easy to follow. The authors probably want to consider to move more content in the appendix to the main text as you have enough space.

Other comments: 

1.I’m not following your derivations from 156 -- 157, could the authors provide more explanations here?

2.In your theorem 2, when $\sigma = 0$, meaning that your observation is noiseless, the regret still has the order $O(T^{3/4})$. This seems to suggest a pretty large gap. As when   $\sigma = 0$ and without the monotone sequences action requirement, the problem simply reduces to a binary search, which has a regret of $\log T$. Could the authors briefly comment a little bit on this? 

[1]. Jad Salem, Swati Gupta, and Vijay Kamble. Taming wild price fluctuations: Monotone stochastic convex optimization with bandit feedback

===== Post Rebuttal =======
Thanks for the authors' response and clarifications, I increased my score to 6. 
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a continuum-armed bandit variant, where the arm sequence needs to be increasing. For the case of Lipschitz functions a linear lower bound is provided. When the functions are constrained to be quasi-concave, a simple algorithm is shown to achieve T^3/4 regret, which is shown to be log-optimal.

main_review: While the variant seems interesting, the motivating applications are not exactly good fit for a bandit approach. Allocating the dose in subsequent phases of a clinical trial would involve only a small number of decisions, which is insufficient for a bandit algorithm to use its asymptotic strength. Dynamic pricing (on some products) is more interesting for bandits, but not if it is limited to the initial price setting, where the number of decisions is also more limited. I am not sure, if there are better applications, and for that reason the variant seems more of a theoretical interest rather than practical.

The proposed algorithm is a natural one: estimate at a value, increase the value, and stop the increase, if the maximum is overshot. However, there is not much else that can be done under the monotonic constraint without sufficient smoothness, such as (strong-)concavity.

It is good to see new lower-bound constructions, differing from the standard bump design. The standard KL ideas do come in, but there are some additional ideas as well.

A minor point regarding the regret: multiple times it is mentioned that the monotonic constraint brings the regret from T^2/3 to T^3/4. It is not clear for me if one can achieve T^1/2 (as in Table 1 for [17]) without monotonicity, or one needs more constraint on the function other that quasi-concavity. It would be helpful to clear this confusion in the paper. Obviously, T^2/3 can be achieved with the Lipschitz constraint. 

There are some numerical experiments, but they are not very informative. Being a new variant, there are no real baselines. Perhaps, it would have been useful to have a concave test problem for which [33] would provide a string baseline. Plotting the theoretical bounds would be also useful. 

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies a bandit problem where the actions need to be monotone. Precisely, given an
action space [0, 1], a decision-maker needs to choose actions X_1, ..., X_T, where
X_1 <= X_2 <= ... <= X_T. The authors first show that in the worst case, O(T) regret is unavoidable.
Under a quasi-concavity assumption, they show that T^{3/4} regret is both sufficient and necessary.

Overall, I am ambivalent about the paper. The paper has been written well and while I have not
checked the proofs, the results appear correct in hindsight. However, the setting lacks motivation
and the proof techniques, while not straightforward, are not earth-shattering. 
This is a fairly subjective assessment, and therefore, I have given a neutral score.

main_review: There are many positives in the paper. It is clearly written, easy to read, and the main proof
intuitions have been conveyed clearly and concisely. 

My main criticism of the paper is that it lacks motivation.  In both examples, while the monotonicity
constraint is at best a 'nice to have', and certainly not a hard constraint. 
In the dynamic pricing example, prices change both upwards/downwards all the time based on demand.
I can also think of examples where the opposite is true. Companies have a high price in the
beginning as a form of price discrimination and then adjust both downwards based on the demand.
But there is rarely a hard monotonicity constraint. In the clinical trials example, based on google 
search, it seems like dose escalation usually refers to the practice of finding the threshold for
a treatment with potentially toxic side effects. Its usually not the case, that one is
simultaneously finding an optimum treatment amount. 
- If the authors can convince me otherwise, I might be willing to bump up my score. For instance, can
you point to some real world use cases (not theory papers) where a seller has not reduced the
price or a clinical trial where dose escalation was done simultaneously while finding an optimal
treatment. 

There are many great theory papers where the use case may not be practically well motivated. However,
in such papers, the proofs require very novel techniques and future papers can build on such ideas.
Unfortunately, I don't feel that this paper meets this bar. While the proofs here do require some
novelty, it fundamentally builds on well known techniques. 
 
Question: How would the results change if you were to allow an epsilon-monotonicity constraint? Say,
you are not allowed to make an action now that is more than epsilon less than the previous highest
action, where epsilon could depend on the Lipschitz constant. 

---------------------------------
Post rebuttal: I thank the authors for their response. The authors have convinced me sufficiently of the practical significance of the problem and I encourage them to discuss them in more detail in the paper. I also wish to reiterate that the proof does use some nice ideas. While I am not ready to champion the paper, I think it could be a nice addition to the proceedings. I have updated my score to reflect this.
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the continuous MAB problem under the constraint that the sequence (X_t)_t of chosen arms is non-decreasing. Obtaining non-linear regrets is obviously impossible without restricting the class of candidate functions: the authors focus on the quasi-concave (or unimodal) Lipschitz case.
They show that the monotonicity constraint on the choices of arms causes the regret to grow as O(T^3/4) instead of O(T^2/3) for the Lipschitz case and O(T^1/2) for the quasi-concave case. A rather straightforward algorithm reaches this rate up to logarithmic factors. A T^{3/4}/32 lower bound is proved.


main_review: Globally, the paper is pleasant to read. The problem solved is rather simple but the treatment is nice and clean.
  
The motivation for the problem is somewhat questionable: in clinical trials, it is possible to lower the dose if too high toxicity is detected, and in dynamic pricing experience shows that the sequence of prices is rarely monotonous (even though we would prefer if it were). The justification of this setting in the introduction sounds somewhat naive, and is repeated pretty redundantly in Section 2.

Proposition 1 (the impossibility to have non-linear regrets in general) is pretty obvious, but nicely written. In general, the ideas come very naturally, and are well exposed. There are a number of shortcomings listed below, which absolutely need to be addressed. The main (reasonably simple) thing missing in my view is a lower bound showing the impossibility to have a non-linear regret if the horizon T is unknown (this is cited as an open question after Thm.2). I would suggest to change the name of the paper, which I find slightly misleading, to "escalating bandits".

But apart from that, I think that the paper has a nice message and seems suited to a publication at a conference.


Important things to correct : 

- the sketch of proof after Thm.2 is nice and gives most ideas, except one term which seems to be forgotten: the contribution to the regret of the O(mK) draws to the initial arms before the maximum is reached. This term explains why m should not be chosen to be too large: it is important for the intuition. I hence think that this should be corrected.

- in the supplementary material on line 453, you should recall here what is T_1

- in the supplementary material, there are several problems in the proof of Theorem 3 that need to be fixed: 

  * the sequence of equations after line 506 is not rigorously written: "\mu_{i,i}(x_1,z_1,\dots,x_t,z_t)" is zero everywhere. But since \mu_{i,i} is absolutely continuous with respect to \mu{k,i} (to be justified), the Radon-Nikodym derivative d\mu_{i,i}/d\mu_{k,i} exists. On the third line, it should not be d\mu_{i,i}(\cdot |...) but d\mu_{i,i}(z_1,\dots,z_s |...), and you could use the conditional independence to simplify the expression here. Globally, I think that this entire sequence of equations needs to be rewritten (I know that this type of Lai-Robbins lower bound is a pain to write, but more clarity is still needed). 
 
  *  in the display of line 509, the T_{k,i} term should not be squared. 



limitations_and_societal_impact: 
no applicable here
review_title: null

Meta-review: All reviewers have agreed that the paper is nicely written and presents a proper solution to the problem examined (given the fixes in the proof agreed with the authors in the discussion phase), and hence all of them recommend acceptance. On the other hand, there is also an agreement that the paper lacks proper motivation, as none of the examples mentioned by the authors (including the ones in the discussion) properly fit the framework provided. The paper would be an excellent fit to the conference with a proper motivation, and the authors are highly encouraged to demonstrate the existence of a realistic-looking problem where the framework is indeed applicable (otherwise this will remain a purely mathematical contribution).
Decision: Accept (Poster)