Multi-armed Bandit Requiring Monotone Arm Sequences
Authors: Ningyuan Chen
Venue: NeurIPS 2021 Poster (2021)
Keywords: multi-armed bandit
optimal regret
continuum-armed bandit
online learning applications

Abstract: In many online learning or multi-armed bandit problems, the taken actions or pulled arms are ordinal and required to be monotone over time. Examples include dynamic pricing, in which the firms use markup pricing policies to please early adopters and deter strategic waiting, and clinical trials, in which the dose allocation usually follows the dose escalation principle to prevent dose limiting toxicities. We consider the continuum-armed bandit problem when the arm sequence is required to be monotone. We show that when the unknown objective function is Lipschitz continuous, the regret is $O(T)$. When in addition the objective function is unimodal or quasiconcave, the regret is $\tilde O(T^{3/4})$ under the proposed algorithm, which is also shown to be the optimal rate. This deviates from the optimal rate $\tilde O(T^{2/3})$ in the continuous-armed bandit literature and demonstrates the cost to the learning efficiency brought by the monotonicity requirement.


Multi-armed Bandit Requiring Monotone Arm Sequences
Ningyuan Chen Rotman School of Management, University of Toronto 105 St George St, Toronto, ON, Canada ningyuan. chen@utoronto.ca
Abstract
In many online learning or multi-armed bandit problems, the taken actions pulled arms are ordinal and required be monotone over time. Examples include dynamic pricing, in which the firms use markup pricing policies to please early adopters and deter strategic waiting, and clinical trials, which the dose allocation usually follows the dose escalation principle to prevent dose limiting toxicities. We consider the continuum-armed bandit problem when the arm sequence is required to be monotone. We show that when the unknown objective function is Lipschitz continuous, the regret is (TT). When in addition the objective function is unimodal or quasiconcave, the regret is ((T3/4) under the proposed algorithm, which is also shown to be the optimal rate. This deviates from the optimal rate ( in the continuous-armed bandit literature and demonstrates the cost to the learning efficiency brought by the monotonicity requirement.
Introduction
In online learning problems such as the multi-armed bandits (MAB). the decision maker chooses from a set of actions/arms with unknown reward. The goal to learn the expected rewards of the arms and choose the optimal one much as possible within a finite horizon. The framework and its many variants have been successfully applied to wide range of practical problems, including news recommendation 31,, dynamic pricing and medical decision-making [8]
Popular algorithms such as UCB 4 and Thompson sampling B 34 typically explore the arms sufficiently and as more evidence is gathered, converge the optimal arm. These algorithms are designed to handle the classic MAB problems, which the arms are discrete and not have any order. However, in some practical problems, the arms are ordinal and even continuous. This is the focus of the study on the so-called continuum-armen bandit 2 26 6 11 38). By discretizing the arm space properly, algorithms such UCB and Thompson sampling can still be applied. Therefore, the continuous decision space has readily been incorporated into the framework.
Another practical issue, which is not studied thoroughly but emerges naturally from some applications, the requirement that the action/arm sequence is has be monotone. Such a requirement usually imposed due to external reasons that cannot be internalized to be part of the regret. We give two concrete examples below.
Dynamic pricing. When launching a new product, how does the market demand reacts to the price typically unknown. Online learning is popular tool for the firm to learn the demand and make profits simultaneously. See (21) for a comprehensive review. In this case, the arms are the prices charged by the firm. However, changing prices arbitrarily over time may have severe adverse effects. First, early adopters of the product are usually loyal customers. Price drops at a later stage may cause a backlash this group of customers, whom the firm is the least willing to offend. Second, customers
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

are usually strategic, as studied extensively in the literature [39 32 44 31 a future discount may make consumers intentionally wait and hurt the revenue. remedy for both issues is markup pricing policy, in which the firm increases the price over time. This is particularly common for digital services growing rapidly: both Drophox and Google Drive went through the phases from free, to low fees, to high fees. In a slightly different context, markup pricing is often used in successful crowdfunding campaigns: to reward early backers, the initial products may be given for free; later after some goals are achieved, backers may get the product at a discount; after the release, the product is sold at the full price. It is not a good idea to antagonize early backers by lowering the price later on. In the language of multi-arme bandit, it is translated to the requirement that the pulled arms in each period are increasing over time.
T6]. The possibility of
Clinical trials. Early stage clinical trials for the optimal dose are usually conducted in Phase I/II trials sequentially. For Phase I, the toxicity of the doses is examined to determine a safe dose range. In this phase, the dose allocation commonly follows the "dose escalation" principle [30] and the "3+3 design" is the most common dose allocation approach. For Phase II, the efficacy of the doses are tested within the safe dose range (by random assignment, for example). Recently, especially in oncology, there are proposals to integrate both phases [42] which is called "seamless Phase I/II trials." In this case, dose escalation has to be observed when looking for the most efficacious dose. Our study is thus motivated by seamless trials. In the online learning framework, the dosage is treated as arms and the efficacy is the unknown reward. Multi-armed bandit has been applied to the dose allocation to identify the optimal dose 77. In particular, after a dose has been assigned to a cohort of patients, their responses are recorded before the next cohort is assigned a higher dose. If any of the patients experiences dose limiting toxicities (DLTs), then the trial stops immediately. The dose escalation principle requires the allocated doses to be increasing over time. A recent paper incorporates the principle in the design of adaptive trials [13]
To accommodate the above applications, in this paper, we incorporate the requirement of monotone arm sequences in online learning, or more specifically, the continuum-armer bandit framework. We consider an unknown continuous function S (xr) and the decision maker may choose an action/arm X, in period t. The observed reward Zg is a random variable with mean ff fX)).. The requirement of monotone arm sequences is translated to X1 S X2 S S XI, where T is the length of the horizon. The goal of the decision maker is to minimize the regret T maaaxx fax Σi= (X:]]
Main results. Next we summarize the main results of the paper informally. We first show that for a general continuous function fz), the extra requirement makes learning impossible.
Result. For the class of continuous functions fz). the regret is at least T/4.
This diverges from the results in the continuum-armen bandit literature. In particular, 226 shows that the optimal regret for continuous functions scales with 2 without the monotonicity requirement. Therefore, to prove meaningful results, we need to restrict the class of functions f()). From both the practical and theoretical points of view, we find that assuming (xx to be unimodal or quasiconcave is reasonable. In practice, for the two applications mentioned above, the revenue function in dynamic pricing typically assumed to be quasiconcave in the price [47]: for clinical trials, the majority of the literature assumes the dose-response curve to be increasing [10), increasing with plateau effect 455. all of which satisfy the assumption. theory, with the additional assumption, we can show that
33 or unimodal
Result. There is an algorithm that has monotone arm sequences and achieves regret Ollog(T)TT)) for continuous and quasiconcave functtion ff f(z).
Note that the rate T3/1 is still different from that in the continuum-armed bandit literature. We then proceed to close the case by arguing that this is the fundamental limit of learning, not due to the design of the algorithm.
Result. No algorithu can achieve less regret than T3/4 /32 for the instances we construct.
The constructed instances that are hard to learn (see Figure 2 are significantly different from the literature. In fact, the classic construction of "needle in haystack" (27 does not leverage the requirement of monotone arm sequences and does not give the optimal lower bound. We prove the lower bound by using a novel random variable that only a stopping time under monotone arm sequences. By studying the Kullback-Leible divergence of the probabilities measures involving
2

---

Table 1: The optimal regret under different settings in the continuum-armed bandit. The regret in
18
achieved under additional assumptions.
Paper
Concavity
Quasiconcavity
Monotone Arm Sequences
Regret
26
N
N
N
This paper
N
Y
O(T)
20
Y
N
(
35
Y
Y
(3
18
Y
N
(
This paper
Y
Y
O(T3/4)
the stopping time, we are able obtain the lower bound. We also show numerical studies that complement the theoretical findings.
Related literature. The framework of this paper similar the continuum-armer bandit problems, which are widely studied in the literature. The earlier studies focus on univariate Lipschitz continuous functions (26) and identify the optimal rate of regret OTT2/5). Later papers study various implications including smoothness 66
15 24 the presence of constraints and convexity [9] [3], contextual information and high dimensions 388 [2). and so on. The typical reduction used in this stream of literature is to adopt proper discretization scheme and translate the problem into discrete arms. In the regret analysis, the Lipschitz continuity or smoothness can be used to control the discretization error. Our setting is similar the study in [26] with quasiconcave objective functions and the additional requirement of monotone arm sequences. The optimal rate of regret, as a result of the difference, deteriorates from 2 to 3/4 This deterioration can be viewed as the cost of the monotonicity requirement.
In recent paper, [35] study a similar problem while assuming the function f (z) is strictly concave. The motivation is from the notion of "fairness" in sequential decision making 46] The concavity
allows them to develop an algorithm based on the gradient information. The resulting regret is O(T4/2), the same as continuum-armed bandit with convexity/concavity [ Comparing this set of results, the strong concavity prevents the deterioration of regret rates under the monotonicity requirement. In contrast,
show that the same rate of regret O(T1/2) can be achieved the function is not strictly concave, but just unimodal quasiconcave, under additional technical assumptions, It is worth noting that many results in this paper are discovered independently in
18 [9]
recent paper 25 The comparison of the regret rates are shown in Table [
Other requirements on the arm sequence motivated by practical problems are also considered the literature. [17 36 37 motivated by similar concern in dynamic pricing: customers are hostile to frequent price changes. They propose algorithms that have limited number switches and study the impact the regret. Motivated by Phase clinical trials, [22] study the best arm identification problem when the reward of the arms are monotone and the goal is to identify the arm closest to a threshold. [14] consider the setting when the reward is nonstationary and periodic, which is typical in the retail industry as demand exhibits seasonality.
Notations. We use E4 and E denote all positive integers and real numbers, respectively. Let E be the length the horizon. Let [m]] == [I,...,m, .. for any m E Z Let x* arg maxx f (xx be the set of maximizers of function f(x) in [0, 1]. The indicator function is represented by 11.
2 Problem Setup
The objective function fx) : [0, 1] - [0, unknown to the decision maker. each period E [T]. the decision maker chooses X, [0, 1] and collects random reward Z, which is independent of everything else conditional on X, and satisfies E E|Z,| X,] = f(X,). After periods, the total (random) reward collected by the decision maker is thus Σx= Z,- Since the decision maker does not know f(x) initially, the arm chosen period only depends on the previously chosen arms and observed rewards. That is, for policy π of the decision maker, we have X; Fe .i...., X,-1, Ze- U2), where

---

Us is an independent random variable associated with the internal randomizer of Te (e.g., Thompson sampling).
Before proceeding, we first introduce a few standard assumptions. Assumption 1. The function {() is e-Lipschitz continuous, i.e.,
(f(x1) - f(22)1 S c/a1 x21
for 1 12 E 1].
This is standard assumption in the cattinuum-ammedd bandit literature 126 without continuity, the decision maker has no hope to learn the objective function well. this study, we do not consider other smoothness conditions.
6 II 38 Indeed,
Assumption 2. The reward Ze is o-subgaussian for all E [T]. That is, conditional on X
Elexp(A(Zz - [(X.))) exp(A2o2/2)
for all À E I.
Subgaussian random variables are the focus of most papers in the literature, due to their benign theoretical properties. See [29] for more details.
We can now define an oracle that has the knowledge of f(x). The oracle would choose arm arg max fz) and collect the total reward with mean T ca f(x). Because of Assumption T the maximum is well defined. We define the regret of a policy x as
T
F (T) = T max f(x)
Σ E(f(x)))
==(0,11
Note that the regret depends on the unknown function f(x), which is not very meaningful. As standard setup in the continuum-armed bandit problem, consider the worst-case regret for all satisfying Assumption 2
R2 (T) max (T)
Next we present the key requirement in this study: the sequence of arms must be increasing. Requirement 1 (Increasing Arm Sequence). The sequence (XI)= must satisfy
X1 S X2 S ... XT
almost surely under æ.
Note that "increasing" can be relaxed to "monotone" without much effort. For the simplicity of exposition, only consider the increasing sequence.
As explained in the introduction, this is practical requirement several applications. In phase I/II clinical trials, the quantity X, is the dose applied to the (-th patient and f(x) is the average efficacy of dose æ. The dose escalation principle protects the patients from DIT's. More precisely, the doses applied to the patients must increase gradually over time such that the trial can be stopped before serious side effects occur to batch of patients under high doses.
In dynamic pricing, X₂ is the price charged for the f-th customer and f(x) is the expected revenue under price x. The increasing arm sequence corresponds a markup pricing strategy that is typical for new products. Because of the increasing price, early adopters, who are usually loyal to the product, wouldn't 't feel betrayed by the firm. Moreover, deters strategic consumer behavior that may cause large number of customers to wait for promotions, hurting the firm's 's profits.
We point that under Assumption [ which typically suffice guarantee sublinear regret, the regret R, (T) at least T/4 under Requirement for all policies n.
Proposition 1. For all satisfying Requirement we have R₂, (T) 2 T/4 under Assumptions
with 2 and Assumption 2
The result can be easily illustrated by the two functions (fi)) in the left and f2(x) in the right) in Figure Because of Requirement I and the fact that fi (z) fa(z) for E [0, 0.5), must have

---

0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
Figure 1: Two functions (fi (x) the left and f2(z) in the right) that any policy cannot differentiate
before any such that X₁ S 0.5 under Requirement
EL 1x, being equal under fi(2)) and fa(x)) for any given policy Moreover, it is easy that
T 2
R (T)
Σ
1x,503:
R(2,x(T) 2
Σ 1 X. 00.
Σ
1x.00.5
Recall the fact Σt= 1u, + + 1x,055 = T. The above inequalities lead to R (T) +
Rf (T) 2 7/2, which implies Proposition
Therefore, to obtain sublinear regret, we need additional assumptions for f(x). In particular, we assume
Assumption 3. The function f(x) is quasiconcave, i.e., any Tı, T2, X [0, 1]. we have f(Ar1 + A)æ2) 2 min [
In other words, a quasiconcave function weakly unimodal and does have multiple separated local maximums. Therefore, f2(x) in Figure is not quasiconcave while fz) is. Note that quasiconcave function may well have a plateau around the local maximum.
We impose Assumption on the function class due to two reasons. First, quasiconcavity is probably come up with that is compatible with Requirement [ It is [35), and it is easy to see from Figure [ that multiple local maximums tend to cause linear regret under Requirement T. Moreover, unimodal functions the focus of other studies in the online learning literature 18 19 Second, objective functions in practice are commonly assumed to be quasiconcave. For the dynamic pricing example, the revenue function is typically assumed to be quasiconcave in the price [47), supported by theoretical and empirical evidence. In
the weakest technical assumption much weaker than concavity
clinical trials, most literature assumes the dose-response curve be quasiconcave [10 45 33].
3 The Algorithm and the Regret Analysis
In this section, we present the algorithm and analyze its regret. We first introduce the high-level idea of the algorithm. The algorithm discretizes [o, 1] into evenly-spaced intervals with end points {0, 1/K, (K- 1)/K, 1}. where K is tunable hyper-parameter. The algorithm pulls arm K/K for m times sequentially for = 0, 1..... for a hyper-parameet batch of m pulls if the reward of arm k/K is not good that of previous arm. More precisely, the stopping criterion is that the upper confidence bound for the average reward arm k/ K less than the lower confidence bound for that of some arm i/K for i < kt When the stopping criterion is triggered, the algorithm always pulls arm k// K afterwards. The detailed steps of the algorithm are shown in Algorithm [
m. stops escalating k after a
The intuition behind Algorithm T is easy to see. Because of Assumption the function f(x) is unimodal. Therefore, when escalating the arms, the algorithm keeps comparing the upper confidence
5

---

Algorithm 1 Increasing arm sequence
Input: K,
Initialize: & <- 0, +- 0,5
while $ =0
Stopping criterion
Choose X =... Xi+m = k/ K and observe rewards Ze+1,-.. Calculate the confidence bounds for arm k/ K
Z++m
1
t+m
2log
UB
Zi oV.
m
m
2 log m
LBg <
74 oV
m
1=++1
U < LB; for some < k then S+1
else
1 m, k + k+1
end if end while
Set X₁ = k/K for the remaining
bound of the current arm k// K with the lower confidence bound of the historically best arm. the upper confidence bound of k/K is lower, then it means k/ K is likely to have passed the "mode" of f(z). At this point, the algorithm stops escalating and keeps pulling k/ K for the rest of the horizon. Clearly, Algorithm I satisfies Requirement]
|
The regret of Algorithm I provided in Theorem 2
Theorem 2. By choosing K
|/4 and m = /2 the regret of Algorithm
satisfies
11 + 4- Vlog T T//4
(T) S 3c +
2
when T 2 16, under Assumptions
to
We note that to achieve the regret in Theorem 2 the algorithm requires the information of T and but not the Lipschitz constant c. The requirement for a may be relaxed using data-dependent confidence intervals such as bootstrap, proposed in (28 233. The requirement for T is typically relaxed using the well-known doubling trick. However, may not work in this case because of Requirement [ once T doubled. the arm cannot start from X, again. It remains open question whether Algorithm
can be extended to the case of unknown T.
Next we introduce the major steps of the proof of Theorem The discretization eтror of pulling arms k/ K, A E {O.... K) }, is of the order O(T/K), Therefore, choosing K = O(T2/4) controls the regret at the desired rate. The total number of pulls "wasted" in this stage is ((m = (334))) We consider the good event, on which [kk/ K) is inside the confidence interval [LB U B&] for all A = 0, 1.... until the stopping criterion is triggered. We choose m such that for given & this happens with probability no less than
((1mm). Therefore, applying the union bound to most K discretized arms, the probability of the good event no less than 1 O(K/m) 1- 1-O(T-1/4) As result, the regret incurred due to the bad event is bounded by TO(T-1/4) O(T3/1), matching the desired rate. On the good event, the stopping criterion is triggered because arm k/ has passed arg max, (x). But is not much worse than the optimal arm because otherwise the stopping criterion would have been triggered earlier. The gap between f(k/ K) and f(=*) is controlled by the width of the confidence interval, (lolog m/m). Multiplying it by T (because k/ is pulled for the rest of the horizon once the stopping criterion is triggered) gives OTT ([T-lo (lgmm/m) 3/1 Vlog T). Putting the pieces together gives the regret bound in Theorem

---

0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
Figure 2: The constructed instances for the lower bound in continuum-armed bandit (left panel) and Theorem (right panel).
4 Lower Bound for the Regret
In the classic continuum- bandit problem, without Requirement[] [ it is well known that there exist policies and algorithms that can achieve regret O(T2/3), which has also been shown to be tight 26 6 38). In this section, show that in the presence of Requirement [ no policies achieve
regret less than 2(T3/4) under Assumptions 1 and
Theorem 3 (Lower Bound). When T 2 16, under Assumption 7 with 1, Assumptions 2 and
we have
RT(T) 2 78/4
for any policy и satisfying Requirement 7
Compared to the literature, Theorem 3 implies that Requirement substantially impedes the learning efficiency by increasing the rate of regret from 2/3 to T3/4 The proof for Theorem B significantly different from that in the literature. In particular, a typical construction for the lower bound in the continuum-arme bandit literature involves class of functions that have "humps" in small interval and are zero elsewhere, as illustrated in the left panel of Figure 2 The idea to make the functions indistinguishable except for small intervals. In our case, is not sufficient to achieve (T74/4). To utilize Requirement [] the constructed functions in the right panel of Figure 2 share the same pattern before reaching the mode. Afterwards, the functions diverge. The objective for the decision maker to decide whether to keep escalating the arm or stop, and punish her severely a wrong decision is made. (Consider stopping the mode of the red function while the actual function is yellow.) Such regret is much larger than the hump functions and thus gives rise to the higher rate.
make it hard
Besides the construction of the instances, the proof relies on the following random time
T = max (t| & a}
for some constant a. Note that 7 is typically not a stopping time for a stochastic process X,, Under Requirement 1 however, it is stopping time. This is the key observation that helps to fully utilize the monotonicity. Technically, this allows us to study the Bellback-Leibler divergence for probability measures
the events (r= 1), (r = 2}, and so on, we can focus on the periods when X, < a, which cannot possibly distinguish functions whose mode are larger than (right panel of Figure 2. This observation and innovation is essential in the proof of Theorem
(X₂, Zi. ....... X,, Zr, T). By decomposing the KL-divergence
Numerical Experiment
In this section, we conduct numerical studies to compare the regret of Algorithm D with a few benchmarks. The experiments are conducted Windows 10 desktop with Intel 10900K CPU.
7

---

To make a fair comparison, we generate the instances randomly so that it doesn't t bias toward our algorithm. In particular, we consider T E {1000, 21000, ..... 101000). For each T. we simulate 100 independent instances. For each instance, we generate 21 (O,,1) 1) and 22 ~ UO0.5,1 1), and let [(x) be the linear interpolation of the three points (0, 0), (I1, x2). and (1, 0). The reward 7 ~ NN(((x)), 0.1) for all instances and 7 We consider the following algorithms for each instance:
1. Algorithm 1 As stated in Theorem we use K [T m [T and 0.1.
2. The classic UCB algorithm for the continuum aandnuum-arrmed bandit. We first discretize the interval
[0, 1] into K + equally spaced grid points, {K/ { k== where K = -T21/3 according to (26. Then we implement the version of UCB Chapter of [9] on the multi-armed bandit problem with K + arms. More precisely, we have
X = arg max (U)
k/K
Tt - 1) = 0 T& - 2
UCBx(1) = 1)) 1) V
(ogg)+)) 1r(1-1)
where px - 1) is the empirical average of arm k. x = k/K, K in the first t periods; Te(tt - 1) is the number that arm k is chosen in the first T - periods. Note that in this benchmark we do not impose Requirement [
3. UCB with Requirement] [ the last benchmark, except that we impose Xx+1 2 X,. That is
We follow the same discretization scheme and UCB definition in
X, = max (x-1 arg max (U)) k/K
4. Deflating UCB with Requirement[ T To improve the performance of UCB with Require- ment [ we need to make the algorithm more likely to stick to the current arm. Moreover, when exploring new arms, we need to encourage the algorithm to explore the arm slightly larger than the current arm. We design heuristic for this purpose by deflating the UCB initialization the arms. More precisely, we let
UCB k/K, (1 =
In this way, the decision maker is encouraged to explore arms with small k first and gradually escalate the arms.
The average regret over the 100 instances is shown in Figure 3 We may draw the following observations from the experiment. First, the regret of UCB is significantly less than the other three algorithms which are constrained by Requirement [ Therefore, the cost brought to the learning efficiency by Requirement [ is huge. Second, simply imposing Requirement to the UCB algorithm Third, the
doesn't 't perform well (the green curve). It more than triples the regret of Algorithm| [ deflating UCB heuristic seems to perform well. Its regret is on par with that of Algorithm T although the trend implies a fast scaling with T. The regret analysis and the optimal choice of the deflating factor remain an open question. Overall, Al Algorithm| | The result is consistent with the theoretical studies.
performs the best among the algorithms that
are constrained by Requirement [
6 Conclusion
In this study, we investigate the online learning or multi-armed bandit problem, when the chosen actions are ordinal and required to be monotone over time. The requirement appears naturally in several applications: firms setting markup pricing policies in order not to antagonize early adopters and clinical trials following dose escalation principles. It turns out that the requirement may severely limit the capability of the decision maker to learn the objective function: the worst-case regret is linear in the length of the learning horizon, when the objective function just continuous. However, we show that if the objective function is also quasiconcave, then the proposed algorithm can achieve
Herre (a, b) denotes a uniform random variable between in [a, b]: (a, b) denotes normal random variable with mean a and standard deviation b.
8

---

10
10
Regret
103
Algorithm !
10a
UCB
UCB Requirement
Deflating UCB
10a
0.2
0.4
0.6
0.8
T
.105
Figure The average regret of Algorithm Jand three benchmarks.
sublinear regret Ö(T3/4). It is still worse than the optimal rate in the continuum-armet bandit literature, but proved to be optimal in this setting.
The study has few limitations and opens up potential research questions. First, since the doubling trick no longer works, the assumption of knowing T advance cannot be simply relaxed. is clear if one can design new algorithm that can achieve the optimal regret even when T is unknown. Second, it is unclear if the monotone requirement can incorporated contextual bandits. This is highly relevant question in clinical trials, which increasingly rely on patient characteristics for the dose allocation. novel framework is needed to study how the dose escalation principle plays out in this setting.
References
[1] Alekh Agarwal, Dean Foster, Daniel Hsu, Sham M Kakade, and Alexander Rakhlin. Stochastic convex optimization with bandit feedback. In J. Shawe-Taylor, R. Zemel, P. Bartlett, Pereira, and K. Q Weinberger, editors, Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011.
[2] Rajeev Agrawal. The continuum armed bandit problem. SIAM journal on control and optimiza- tion, (3(6): 1956, 1995.
[3] Shipra Agrawal and Navin Goyal. Further optimal regret bounds for thompson sampling. In Artificial intelligence and statisties, pages 99-107. PMLR, 2013.
[4] Peter Auer, Using confidence bounds for exploitationnexxllraiio trade-offs. Journal of Machine Learning Research, 3(Nov):397-423 2002.
[5] Peter Auer, Nicolo Cesa-Bianchi. and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2): 2002.
[6] Peter Auer, Ronald Ortner, and Csaba Szepesvári. Improved rates for the stochastic continuum- armed bandit problem. In International Conference on Computational Learning Theory, pages 454 468. Springer, 2007.
Maryam Aziz, Emilie Kaufmann. and Marie-Karelle Riviere. On multi- bandit designs for dose-finding clinical trials. Journal of Machine Learning Research, 22:1-38, 2021.
[8] Hamsa Bastani and Mohsen Bayati. Online decision making with high-dimensional covariates. Operations Research, 68(1):276-294, 2020. 2020.

---

[9] Omar Besbes and Assaf Zeevi. Dynamic pricing without knowing the demand function: Risk bounds and near-optimal algorithms. Operations Research, 57(6):1477-1200, 2009.
[10] Thomas M Braun. The bivariate continual reassessment method: extending the CRM to phase I trials of two competing outcomes. Controlled clinical trials, (3(3):240-2555 2002.
[11] Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvári. X-armed bandits. Journal of Machine Learning Research, 12(5), 2011.
[12] Ningyuan Chen and Guillermo Gallego. Nonparametric pricing analytics with customer covari- ates. Operations Research, Forthcoming.
[13] Ningyuan Chen and Amin Khademi. Adaptive seamless dose- museifinding trials. Working Paper, 2020.
[14] Ningyuan Chen, Chun Wang, and Longlin Wang. Learning and optimization with seasonal patterns. Working paper, 2020.
[15] Qi Chen, Stefanus Jasin, and Izak Duenyas. Nonparametric self-adjusting control for joint learning and optimization of multiproduct pricing with finite resource capacity. Mathematics of Operations Research, 44(2):601-63 2019.
[16] Yiwei Chen and Vivek Farias. Robust dynamic pricing with strategic customers. Mathematics of Operations Research, 13(4):1119-1143) 2018.
[17] Wang Chi Cheung, David Simehi-Levi, and He Wang. Dynamic pricing and demand learning with limited price experimentation. Operations Research, 1726)117,,,, 2017.
[18] Richard Combes and Alexandre Proutiere. Unimodal bandits: Regret lower bounds and optimal algorithms. International Conference on Machine Learning, pages 521-529. PMLR, 2014.
[19] Richard Combes, Alexandre Proutière, and Alexandre Fauquette. Unimodal bandits with continuous arms: Order-optimal regret without smoothness. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 4(1):1-28, 2020.
[20] Eric W Cope. Regret and convergence bounds for class of continuum- bandit problems. IEEE Transactions on Automatic Control, 54((): 1243-123,, 2009.
[21] Arnoud Den Boer. Dynamic pricing and learning: historical origins, current research, and new directions. Surveys in operations research and management science, 20(1):1-18, 2015.
[22] Aurélien Garivier, Pierre Ménard, Laurent Rossi, and Pierre Menard. Thresholding bandit for dose-ranging: The impact of monotonicity. Working puper, 2017.
[23] Botao Hao, Yasin Abbasi-Yadkori Zheng Wen, and Guang Cheng. Bootstrapping upper confidence bound. Working Paper, 2019.
[24] Yichun Hu, Nathan Kallus, and Xiaojie Mao. Smooth contextual bandits: Bridging the paramet- ric and non-differentiable regret regimes. In Conference on Learning Theory, pages 2007-2010. PMLR, 2020.
[25] Su Jia, Andrew Li, and R Ravi. Markdown pricing under unknown demand. Working Paper, 2021.
[26) Robert Kleinberg. Nearly tight bounds for the continuum-armed bandit problem. Advances in Neural Information Processing Systems, 17:697-704, 2004.
[27] Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Multi-armed bandits in metric spaces. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 681 681-690, 2008.
[28] Branislav Kveton, Csaba Szepesvari, Sharan Vaswani, Zheng Wen, Tor Lattimore, and Moham- mad Ghavamzadeh. Garbage in, reward out: Bootstrapping exploration in multi-armed bandits. In International Conference on Machine Learning, pages 3601-3610, PMLR, 2019.
10

---

[29] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[30] Christophe Tourneau, J Jack Lee, and Lillian L Siu. Dose escalation methods in phase cancer clinical trials. JNCI: Journal of the National Cancer Institute, 101(10):708-720, 2009.
[31] Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pages 661-670, 2010.
[32] Qian Liu and Garrett Van Ryzin. Strategic capacity rationing to induce early purchases. Management Science, 14(6):1115-1133) 2008.
[33] MarielKarelle Riviere, Ying Yuan, Jacques- Hentri Jourdan, Frédéric Dubois, and Sarah Zohar. Phase I/II dose-finding design for molecularly targeted agent: plateau determination using adaptive randomization. Statistical methods in medical research, 27(2):466 479, 2018.
[34] Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, and Zheng Wen, A tutorial on thompson sampling. Found. Trends Mach. Learn., 1 11(1):1-96, July 2018.
[35] Jad Salem, Swati Gupta, and Vijay Kamble. Taming wild price fluctuations: Monotone stochastic convex optimization with bandit feedback. Working paper, 2021.
[36] David Simchi-Levi and Yunzong Xu. Phase transitions and cyclic phenomena in bandits with switching constraints. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buu E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[37] David Simchi-Levi, Yunzong Xu, and Jinglong Zhao. Blind network revenue management and bandits with knapsacks under limited switches. Working paper, 2019.
[38] Aleksandrs Slivkins. Contextual bandits with similarity information. Journal of Machine Learning Research, 15(73):2533-2566 2014.
[39] Xuanming Su. Intertemporal pricing with strategic customer behavior. Management Science, 53(5):7267741, 2007.
[40] Alexandre Tsybakov. Introduction to nonparametric estimation. Springer Science & Business Media, 2008.
[41] Soffa S Villar, Jack Bowden, and James Wason. Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges. Statistical science: review journal of the Institute of Mathematical Statistics, 30(2): 2015.
[42] Nolan A Wages and Christopher Tait. Seamless phase i/ii adaptive design for oncology trials of molecularly targeted agents. Journal of biopharmaceutical statistics, 25(5):903-920, 2015.
[43] Zizhuo Wang, Shiming Deng, and Yinyu Ye. Close the gaps: learning- while-doing algorithm for single-product revenue management problems. Operations Research, 62(():318-33) 2014.
[44] Rui Yin, Yossi Aviv, Amit Pazgal, and Christopher Tang. Optimal markdown pricing: Implications of inventory display formats in the presence of strategic customers. Management Science, 55(8):1391-1444 2009.
[45] Wei Zhang, Daniel J Sargent, and Sumithra Mandrekar. An adaptive dose-finding design incorporating both toxicity and efficacy. Statistics in Medicine, 25(14):2365-233) 2006.
[46] Xueru Zhang and Mingyan Liu. Fairness in learning-based sequential decision algorithms: survey. Working puper, 2020.
[47] Serhan Ziya, Hayriye Ayhan, and Robert Foley. Relationships among three assumptions in revenue management, Operations Research, 52(5):804-809 2004.


Reviews:
[{"review_id": "QNw2VIJdW9", "reviewer": "Reviewer_YioK", "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.\nThey 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.\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "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": "Globally, the paper is pleasant to read. The problem solved is rather simple but the treatment is nice and clean.\n  \nThe 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.\n\nProposition 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\".\n\nBut apart from that, I think that the paper has a nice message and seems suited to a publication at a conference.\n\n\nImportant things to correct : \n\n- 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.\n\n- in the supplementary material on line 453, you should recall here what is T_1\n\n- in the supplementary material, there are several problems in the proof of Theorem 3 that need to be fixed: \n\n  * 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). \n \n  *  in the display of line 509, the T_{k,i} term should not be squared. \n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "\nno applicable here", "review_text": "", "extra_scores": {"ethical_concerns": "nothing to say", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "Fyh89xV3Ki4", "reviewer": "Reviewer_BiUb", "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. \nThen 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. \n", "questions": "", "limitations": "", "rating": 6, "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": "Originality, quality, and significance:\n\nThough 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. \n\nClarity: \n\nThe 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.\n\nOther comments: \n\n1.I’m not following your derivations from 156 -- 157, could the authors provide more explanations here?\n\n2.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? \n\n[1]. Jad Salem, Swati Gupta, and Vijay Kamble. Taming wild price fluctuations: Monotone stochastic convex optimization with bandit feedback\n\n===== Post Rebuttal =======\nThanks for the authors' response and clarifications, I increased my score to 6. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "B1iqlQbovZ", "reviewer": "Reviewer_HdAN", "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.\n", "questions": "", "limitations": "", "rating": 6, "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": "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.\n\nThe 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.\n\nIt 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.\n\nA 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. \n\nThere 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. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "-", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "-VwHr03de4K", "reviewer": "Reviewer_P9sB", "summary": "The paper studies a bandit problem where the actions need to be monotone. Precisely, given an\naction space [0, 1], a decision-maker needs to choose actions X_1, ..., X_T, where\nX_1 <= X_2 <= ... <= X_T. The authors first show that in the worst case, O(T) regret is unavoidable.\nUnder a quasi-concavity assumption, they show that T^{3/4} regret is both sufficient and necessary.\n\nOverall, I am ambivalent about the paper. The paper has been written well and while I have not\nchecked the proofs, the results appear correct in hindsight. However, the setting lacks motivation\nand the proof techniques, while not straightforward, are not earth-shattering. \nThis is a fairly subjective assessment, and therefore, I have given a neutral score.\n", "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": "There are many positives in the paper. It is clearly written, easy to read, and the main proof\nintuitions have been conveyed clearly and concisely. \n\nMy main criticism of the paper is that it lacks motivation.  In both examples, while the monotonicity\nconstraint is at best a 'nice to have', and certainly not a hard constraint. \nIn the dynamic pricing example, prices change both upwards/downwards all the time based on demand.\nI can also think of examples where the opposite is true. Companies have a high price in the\nbeginning as a form of price discrimination and then adjust both downwards based on the demand.\nBut there is rarely a hard monotonicity constraint. In the clinical trials example, based on google \nsearch, it seems like dose escalation usually refers to the practice of finding the threshold for\na treatment with potentially toxic side effects. Its usually not the case, that one is\nsimultaneously finding an optimum treatment amount. \n- If the authors can convince me otherwise, I might be willing to bump up my score. For instance, can\nyou point to some real world use cases (not theory papers) where a seller has not reduced the\nprice or a clinical trial where dose escalation was done simultaneously while finding an optimal\ntreatment. \n\nThere are many great theory papers where the use case may not be practically well motivated. However,\nin such papers, the proofs require very novel techniques and future papers can build on such ideas.\nUnfortunately, I don't feel that this paper meets this bar. While the proofs here do require some\nnovelty, it fundamentally builds on well known techniques. \n \nQuestion: How would the results change if you were to allow an epsilon-monotonicity constraint? Say,\nyou are not allowed to make an action now that is more than epsilon less than the previous highest\naction, where epsilon could depend on the Lipschitz constant. \n\n---------------------------------\nPost 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.", "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": "3"}, "extra_text": {}}]

Author rebuttal:

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)