Balancing Risk and Reward: A Batched-Bandit Strategy for Automated Phased Release
Authors: Yufan Li
Jialiang Mao
Iavor Bojinov
Venue: NeurIPS 2023 poster (2023)
Keywords: bandit algorithms
online learning
causality
Bayesian inference
TL;DR: Phased release via Bayesian Batched Bandit

Abstract: Phased releases are a common strategy in the technology industry for gradually releasing new products or updates through a sequence of A/B tests in which the number of treated units gradually grows until full deployment or deprecation. Performing phased releases in a principled way requires selecting the proportion of units assigned to the new release in a way that balances the risk of an adverse effect with the need to iterate and learn from the experiment rapidly. In this paper, we formalize this problem and propose an algorithm that automatically determines the release percentage at each stage in the schedule, balancing the need to control risk while maximizing ramp-up speed. Our framework models the challenge as a constrained batched bandit problem that ensures that our pre-specified experimental budget is not depleted with high probability. Our proposed algorithm leverages an adaptive Bayesian approach in which the maximal number of units assigned to the treatment is determined by the posterior distribution, ensuring that the probability of depleting the remaining budget is low. Notably, our approach analytically solves the ramp sizes by inverting probability bounds, eliminating the need for challenging rare-event Monte Carlo simulation. It only requires computing means and variances of outcome subsets, making it highly efficient and parallelizable.

Balance Risk and Reward: A Batched-Bandit Strategy for Automated Phased Release
Yufan Li",
Jialiang Mao",
lavor Bojinov
Harvard University LLinkedIn Corporation "Harvard Business School yufan 110g. harvard edu, jimao0l inkedin. com, iboj inoinnnvehb..om com
Abstract
Phased releases are a common strategy the technology industry for gradually releasing new products updates through sequence of A/B tests in which the number of treated units gradually grows until full deployment or deprecation. Performing phased releases in principled way requires selecting the proportion units assigned to the new release in a way that balances the risk of an adverse effect with the need to iterate and learn from the experiment rapidly. In this paper, we formalize this problem and propose an algorithm that automatically determines the release percentage each stage in the schedule, balancing the need to control risk while maximizing ramp-ur up speed. Our framework models the challenge as a constrained batched bandit problem that ensures that pre-specified experimental budget not depleted with high probability. Our proposed algorithm leverages an adaptive Bayesian approach in which the maximal number of units assigned to the treatment is determined by the posterior distribution, ensuring that the probability of depleting the remaining budget low. Notably, our approach analytically solves the ramp sizes by inverting probability bounds, eliminating the need for challenging rare-event Monte Carlo simulation. It only requires computing means and variances of outcome subsets, making it highly efficient and parallelizable.
Introduction
Phased release, also known staged rollout, is widely used strategy in the technology industry that involves gradually releasing new product or update to larger audiences over time [17 30) For example, Apple's App Store offers phased release option where application updates are released over 7-day period on a fixed schedule [ Google Play Console provides similar feature with more flexibility in the release schedule [16] Typically, the audiences are randomly selected at each stage from the set of all customers, and so phased releases can be thought of as sequence of A/B tests (or randomized experiments) which the proportion of units assigned the treatment group changes until either the product or update is fully launched or deprecated 26
18
3 33
The process of
combining phased releases with A/B tests often called controlled rollout or iterative experiments and provides companies with an important mechanism to gather feedback early product versions
30 20 5.
The key advantage of phased release is its ability to mitigate risks associated with launching new product or update directly all users. The potential impact of faulty features is limited by releasing the update first to a small percentage of the users (i.e.. the treatment group). However, this risk-averse approach introduces an opportunity cost for slowly launching beneficial features, which quickly adds up for companies that release thousands of features yearly (34). Therefore, when designing a phased release schedule, each stage that balances the need to control risk while maximizing the speed of ramp-up. This paper proposes an algorithm to address this challenge by automatically determining the release
important to determine the release percentage (known as ramp schedule) at
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

percentage for the next phase based on observations from previous stages. Specifically, we frame the challenge as budget-constrained batched bandit problem. For each batch, we aim determine the assignment probabilities of newly arrived users while keeping the probability of depleting pre-specified experimental budget, where the experiment's cost the cumulative treatment effect that are not directly observed. Formally, we derive recursive relations that decompose the risk of ruin (depleting the budget) of a phased release to the individual stages in the sense that the risk of ruin of the entire experiment is controlled if stage-wise ruin probabilities are controlled. Our algorithm is Bayesian the sense that it learns from past observations by computing the posteriors of conjugate Gaussian model and uses these parameters to infer the remaining budget and other cost-related quantities. However, the algorithm is robust to misspecifications and works well even when underlying outcomes are far from Gaussian by law of large number and central limit theorem; nevertheless, in Appendix E. we provide an extension to non-Gaussian outcomes. Finally, the next stage's assignment probabilities are derived from the posterior distribution and the stage-wise risk tolerances. Notably, our approach solves ramp sizes analytically from inverting the ruin probability upper bounds, avoiding challenging rare-event Monte-Carke simulation for budget depletion events and data imputation procedures for unobserved counterfactual outcomes.
1.1 Literature review
While many firms have guidelines on how to conduct phased release process, these guidelines are often ad- ad-hoc and qualitative, making it difficult to create executable ramp schedules. The SQR framework in (34) is the first attempt to address this problem by providing quantitative guidance. Our work differs significantly from SQR. Our algorithm adopts fully Bayesian approach, enabling us to incorporate prior information on the risk of feature in probabilistic manner when initiating a ramp. Additionally, unlike SQR, our approach introduces a "shared budget" over the entire phased release, allowing the budget to be sequentially adjusted based on the observations from prior iterations. Finally, our algorithm is robust to modifications made to the treatment during experiments and different outcome models.
Our work is notably distinct from the risk-averse multiarmed bandit approaches considered in previous research [99 14
10 8) In these approaches, the agent considers the expected variability in expected rewards to identify and avoid less predictable (and therefore risky) actions, without considering budget constraint. related literature focuses on batched and Bayesian variants of these methods in multi-stage clinical trials [4] 27 21 24, 2) While this literature also aims to determine treatment assignment for each stage of the experiment, it differs from our setting two key aspects: (i) the objective is to maximize treatment effect while balancing exploration of treatment arms, rather than rapidly ramping up experiments, and (ii) to the best of our knowledge, no clinical trials paper has addressed the imposition of a budget for potential adverse treatment effects. Hence, bandit approaches developed for clinical trials cannot be directly applied to our setting. To illustrate the difference, we present a numerical simulation of Thompson sampling-based Bayesian bandit from [27] and highlight that budget spent and the aggressiveness of the ramp-up schedule depends on model tuning in very unpredictable way, making the ramp-up schedule far from idcal. Another related literature is budgeted multiarmed bandits [32 31 29 [2]. However, most budgeted bandit algorithms are developed for settings very different from ours and do not consider risk-of-ruin control handle unobserved costs. Therefore, these algorithms cannot be directly applied to our specific scenario.
35
28
23
Notation. Let N be the set of non-negative integers and N. == N \ (0). Let R, R2 denote the set of real numbers and positive real numbers respectively. [N] := ,....,N for N E N4. o() is the generated o-algebra. X E F if random variable X is measurable to F. [X F denotes a random variable with distribution IP E F) for a random variable X and o-algebra
Risk-oofrruin-constraaneed experiment and strategy overview
2.1 Risk-afrruin-constrainedd exxerttr
Consider scenario in which a single feature is released to sequence of subpopulations Mú consisting of N, units at stages / = I..., T, where not necessarily fixed. At each stage, we randomly assign treatment to a group of units denoting the indexing set Te. while the control group with indexing
2

---

set C. The size of the treatment group at stage t is [Ti] = and the size of the control group is |c,l Nr my-
where the potential outcome of each unit i E My during experiment stage under control and treatment are denoted by (0) E IR and (1) E R. respectively]] Appendix E provides the extension to multivariate outcomes. The treatment assignment of unit N₂ stage is denoted by Wi,- Since each unit only receives a single treatment at each stage, we only observe Yi, during the experiment, not the counterfactual (1, Ws,e) (we are explicitly assuming that there is full compliance).
Our paper adopts the Neyman-Rubin framework for causal inference 22 25
be the o-algebra generated by the treatment assignment and the observed experiment outcome in the first t stages, with Fo representing the trivial o-algebra. In our setting, the experimenter aims ramp up the experiment to the "max- power stage" (50% of the population placed in treatment) as quickly as possible while avoiding the risk of large negative business impact (or cost). We define the cost of the experiment as the treatment effect on the treated. See generalized cost in Appendix E
Let F; - ((YT.a kEjo) (Yc,,
Definition 2.1 (Experiment cost). The cost of the experiment from stage E [T) is r EieT, Y,, (1) (O), where = 0 if Ti = 0. The cumulative cost is Rg == ExE(1] Tk.
Throughout, ht < 0 corresponds to a negative business impact; our goal is to control the experiment cost by setting a budget B < 0 and imposing the cost constraint RT B. Since the outcomes stochastic, we require this cost constraint to be satisfied with probability at least 1 - 6 for some ô E [0, 1) set before the experiment. Our goal is then to adaptively determine the size of the treatment group based on the observed data while satisfying our risk constraint. We refer to such an experiment fisk-of-ruin-constraine
(RRC) experiment.
Definition 2.2 (RRC experiment). Fix any B 0, E [0, 1). A (6, B)- experiment running for T stages selects the size of T, before (-th stage of the experiment such that P(Rr > B) 2 1 d.
2.2 Strategy overview
Our goal is to determine the number of users to assign to the treatment m, E [0,, [2,N. such that Σ my is maximized while ensuring that the experiment is (B, -
Our strategy is to decompose the overall constraint (i.e., that the experiment (B, d)-RRC) into a sequence of stage-wise adaptive constraints using Theorem 3.1 below. We then sequentially maximize m, under the stage-wise constraint for the 1-th stage. Under the Gaussian model, the stage-wise constraints can be directly solved using a simple quadratic equation to obtain the maximum mc-
Although our algorithm solves a relaxed version of the original optimization problem, our solution has crucial practical implications. Theorem 3.1 decomposes the (B, RRCCCC constraints in adaptive fashion, i..., if the feature turns out to be safe, the stage-wise constraints will relax in response, and the experiment will ramp up quickly.
3 Model and the algorithm
3.1 Decompose the risk of ruin
Our experimental design is based on the following theorem, which identifies sequence of sufficient conditions for a sequential experiment to be (6, -RRRC. We defer its proof to Apppppiix A
Theorem 3.1. Fix B < 0 and 8 E (0, 1). For any stopping time T 2 1, let (be)te(z) be budget
(1) sequence, such that by 2 B, [T), and (At)tety be a risk tolerance sequence, such that
We are implicitly assuming that there is no interference between experimental units, that is, each unit's outcomes do not depend on any other unit's assignments [

---

(i)) S
A E [0.1), vt E [T] and II== (1 A.)
Then, if (Te)ee(r) is chosen such that for = 1,
p Sb1
(66)
A
and any 1 2,... T, almost surely,
T: 0,
if (R B F(-1) =
(in)
P (Re 5 by Rr B,F(-1)
D.,
otherwise
then P (RT > B) 2 6. This inequality is tight when (i)- are all equalities and rs S 0, VI [T' almost surely. Furthermore, we set To t- 0. TT. (2)
always hold.
Recall, B denotes the budget and 8 E [0.1] 1) is our risk tolerance that controls the risk of ruin (i.e., the probability of exceeding the budget); both need to be fixed priori. In general, smaller 8 leads to more conservative experimentation and slower releases. The sequence (b:)e21 "rations" the budget: setting h4- < B stage reserves B b, budget for later stages, which may be beneficial when the released feature is expected to undergo modifications during the experiment [20]. To quickly scale the experiment,
set b, B, Vt. The sequence (At)221 distributes the overall tolerance d to individual stages by 8 = 1 1 -II (1 - A,) allowing us to customize the tolerance for individual stages. If I is fixed priori, we uniformly distribute the tolerance by setting Vt [T].
A, = 1 (1 8/
Theorem 3.1 breaks the risk constraint P (Ry S B) S ô into stage-wise constraints the form of (. The idea is to control current-stage cumulative experiment cost R2 given past observations Fe and determine the treatment assignment based on posterior inference of the remaining budget. In our setting, the goal is to maximize m, |Te subject to (1). Note that the first line in ( stops the experiment when the model estimates that the budget is exhausted. while the second line sets the stage cost r; below the remaining budget be R with high probability. We require assumptions on the data-generating model to derive an explicit algorithm, which we present in the next sections.
Generally, the total number of stages 7' stage-wise budget and tolerance (be (be)c21. (Az)r21 can be determined dynamically during the process. That is, we can define A, and just before stage as 8 and b, B. If we plan terminate the experiment after stage I, 5 and be 2 attained in which case = f. is also possible to have 7 /"= +oo and [ (1 A,) 1 6. For example, choosing A, (1=/ where 7, is the unique solution sine(7+) (7)
long as I (1 A,)
can define A; such that II. (1 - A,)
8 on [0, (cf. [3 Eq. (1))) satisfy our condition.
Note that the decomposition scheme in Theorem 3.1 is formulated such that I' (Ry S B) < is tight if inequalities (i)-(iv) are tight. Practically, this means that the ramp-up schedules obtained through this approach are typically not overly conservative, unlike approaches that leverage a union- bound for risk decomposition. Finally, Theorem 3.1 holds for a general definition of the cost (Ki.)) Tr) such that Te = 0 if T, = 0. making it useful in other budgeted online problems beyond our setting.
3.2 Gaussian outcome model
For this subsection, make the following model assumptions on the outcomes distribution; appendix E provides the extension to general outcome models.
Definition
3.1 (Conjugate Gaussian outcomes). Let the unknown model parameters
Mine (0), Mmee (1) E R satisfy the prior Mirne (w) ~ N (oo))~~N((ooo (o(w)) for = 0, independently,
where no (0), (1) E IR, (o)))) (1)² E R,, are hyperparameters. The experiment outcome of unit i at stage are distributed independently and identically as
Ye,(0) Yee(1)
) iid N ((( (Mmme Mime (0)
(
(0(0) 01) ))
Murue (1)
(3)
where a(0)2,a(1)) Ry are hyperparameters.

---

The unknown parameters Muue (0) and Paue (1) represent the intrinsic quality of the feature before and after the update, as measured by specific metric. Mrme (1) Muree (0) the feature update is likely to have negative business impact, i.e, Yt,(1) - (0) 0.
To derive the posterior distribution need the following statistics. For 1 1, 0,
(w) = M)(w) =0 (((w) = (w(w) = S (w) = (w)
(4)
pp.==1(w) vo(w), fp.=1(w)2 = oo(w)².
and for t 2, 0,1
(w) = Σ
(u,(w), St (w) = Σ
of (w), (())) =
Σ Ves(w): (ww) =
Σ (
iET.
rE[t]
IEC.
rE(d]
(5a)
[o(w) (u))
I[w = O[= (w) + I(w = 1)sT_1(w)
(p.(w))=
+
(5b)
oo(w)) + Mr [ww)
a(w)
o(w)²
(p.(ww)² (ou(w)-2 + M, M(1) (
(5c)
where M,") Erejj m, and M, Erely N, m, are the cumulative number of users in the treatment and control groups up to stage t, respectively. In (5)), S7 (w) and S (w) represent the cumulative sum of outcomes for w 0, in the treatment and control groups up stage t, while of (w) and of (w) represent the sum of outcomes at stage In equation (5b). Mp.((w) represents the posterior mean of Paue (w), while in equation (5c). (z)) represents the posterior variance of
Mine (w). for w 0, When lacking prior information. we suggest using non-informative priors by setting (0) = [1) = and (0)² (1) sufficiently large.
The model parameters o (0)2 2 and (1)² stage / can be estimated using unbiased and consistent estimators. For w 0, 1 let
Σ Σ aw) +- rE|t-1]EEC,
(Yir(w)-
M. ((m) l(w = 0)8T + llw = 1)5T
(6)
Fort = 1, some prior estimate can be used, either from similar experiment from small-scale pretrial run.
3.3 An algorithm for the sample size in an RRC experiment
We now derive an explicit algorithm from Theorem 3.1 that outputs (m4))211 the treatment group size at stage t, such that, the experiment Is (o, RRCC Recall that for an experiment to be (6, B)- RRC, suffices that ( 2 holds for each
1. Under Definition 3.1 we have that (i) (Y,,),,
are exchangeable random variables (ii) for any 2 2, P(S < (1) B F(-1) > almost surely for any choice of mp-1].. Combining these observations, we get that (T.. (2) hold if for each t 1.
P (
ST (0) Sb
B, B, -
S S...
Lemma 3.2
provides an upper bound of the left hand size of 77) the proof is InpApeendix B Lemma 3.2 (Stochastic domination), Assume the outcomes (0), Yo, (1)) are generated in For any 2 1, almost surely.
Defmition 3.7
P 8s8 [() - ST (0) s b. (T) (1_())-B,FL))) -,FL
(8)
S (T(1) - ST s -- -5((()
5

---

Using Lemma 3.2 for and 2 to hold, it suffices to choose any N such that
S7 - - F(11 S A.
P s (1)
(9)
and set m, = 0 if such m, does not exist. From posterior-predictin formulas for the conjugate Gaus-
sian model in Definition 3.1 (see (3ep.. (5h in Appendix C), we have $ sT S7 (0) Fr-1
(me())), of (m+)), where Dr (m) = ( m - -p. (m + M, Gî (m) == m (1) m o(1) (m M, (0)2 ++++++++++ (m+M,²) o0) (10b)
(10a)
Combining the above with 9 yields the following Lemma.
Lemma 3.3. Assume the outcomes (O), Yı, (L)), are generated as in Definition 3.1 For each
t2 1, the inequality 9 holds if and only if
b -1) jıs (m²) T₁ (m²)
S q =
(11)
where h-1 denotes inverse CDF of the standard normal distribution.
Replace the inequality in with equality and square both sides gives us the quadratic equation A₁ m + B, my + C2 = 0 where
A: = (on (0)) (1mx(1) (n)())))m))))) (0))
B, = of (o(1)) + +0) + (0)
(12)
+2 bb ST Mp. (0)
- (vp:((1)(pp:(0)))
G a== (0) (M)))² + (0) 1000)) (1+=
Algorithm finds the floor transform of the solutions of this equation and chooses m, as the largest, positive integer that satisfies (TT). such a solution cannot found, then either we do not have
enough budget or the cost of the experiment is negligible (this accrues when Mtrue Mtree (0) >> 0),
and the inequality in (T] will be strict for any choice of m,. In the former case, (Tgorithm 1 sets me 0; in the latter case, it sets m, N Therefore, by construction, the sequence output by Algorithm I Igaarantees that (1) and (2) hold, thereby defining (6, B)R experiment. Note that this approach directly solves for from the quadratic equation A.mī + B,m, C. 0, bypassing the challenging task of estimating tail probabilities for potential choices of m, through Monte-Cann Carlo methods. By [Algorithm I, can also conduct posterior inference treatment effect after stage using Mp.c-1 (w)), pp.+1(w)) = 0, and estimate the remaining budget by (0)).
B - E my (Pp(Ppt+1111)
Theorem 3.2. Assume the outcomes (0), (1)) are generated as in Definition 3.1 The experiment by Algorithm is is (6, BR-RRC
Even though our algorithms derived from the conjugate Gaussian model we have found that remains effective for broader outcome models. This is because the learning occurs essentially through computation of the first and second moments of past outcomes as in (5). (6), and Algorithm tends to be successful so long they are predictive of the outcome moments in future stages. The risk of ruin control remains approximately valid due to the law of large numbers and standard central limit theorem under specific conditions; next section.
Finally, in Algorithm I the assumption made that the population size N, for the next stage is known to ensure that m, does not exceed [N./2]. In practice, we recommend estimating N, and using the model output m, to calculate the assignment probability pt = mr/N, the allows the experimenter to assign each incoming user to the treatment group with probability of pt.

---

Algorithm Output ramp size adaptively
Input: B < 0, (0.1)
1: Initialize t 1, IT -= (1 (1) 1-
2: while [I===] A,) ) - do
3: choose A. 0, (1-.) -1 , B
4: estimate data variance o [w))
0, (if unknown) using 66
5: compute (w)) (w). ob. , w 0,1 by (b)). (c))
and qt, Ar, BN, C. by
12
6: if de - I 9t then my [
(22((N./2.
7: else if B 4A,C < 0 then m + 0
8: else
Bi + B?
4A,Ci
Bg F3 44
9:
M.
24,
2A
10:
V1 - m E Me n
[o,
No
D ST_ (1) (m))
S
2
mm(m)
11:
V. + then
12:
my max V4
13:
else
14:
m +- 0
15:
end
16:
end if
17:
Output m, conduct stage 1-experiment and observe outcomes (1),,,
compute M, (0), (1), S? (1), (0) by (5)
19:
update + ++1
20:
end while
3.4
Robustness to non-identically distributed and non-Gaussian outcomes
We now derive conditions for the validity of slAggorithm under the assumption that experiment outcomes are independent.
Definition 3.4. The experiment outcomes (O,,(()), (1)) are independent across different units i and experiment stage
allows (0) and (1) to be dependent and/or discrete-valuce (e.g.. binary out- comes). In addition, the outcome distribution (Y,, (1)( can differ across i, f; for instance, treatment effect may be non-stationary. The validity of Algorithm I Definttoeinnniinn 3,4 now given in Theorem 3.3] we defer the proof to (pppendixx D
Definition 3.4
The experiment by Algorithm 7 is (5, B)-RRC if. for each stage 2 1 where me + the following conditions hold
Theorem 3.3. Assume the outcomes (0), Yr, satisfy Definition 3.4,
S7 (1) ST (0) i
2 P1 f4g
IP
24 Fe-1)
< 4 (z),
(13)
Ōt
0:
ōt
where
(0) [ V (0) Fr 1], = ST. (1)
pre
i4 = E and pa (m = ā. (m.) are defined by
10a).
TOb and s7 (1), ST (0) are defined in (5).
We expect the first condition in 13) hold as a consequence central limit theorem for independent
but non-identical random variables. Suppose A, < 0.5, Vt (ie., < 0). By law of large number for
independent but non-idene indietitical random variables, the second condition in (33 holds if (i) we have chosen prior and model parameters conservatively such that
(1) no (0) < my
Σ (Y., (o) VE
a0) 21)² + m (oo(1)² + ao())))
1 Σ (YY.(( -Y,)))
m TET
7

---

and (ii) if the treatment effects increase or stay roughly constant throughout the experiments
Σ
E Σ (V) (Y, Z _ rEjt-1]iET,
( YY,
my
IET.
and our variance estimates (0)), ,11)² are accurate or conservative in the sense that
00)
Σ Σ (O)) o(0) + +0) rEjt-IJiET-
Σ v (X), - Ye.(0)).
me iET
In summary, under Definition 3.4, the validity of Algorithm depends the accuracy and conser- vatism of the model's 's estimates based on past stages for the true treatment effect and volatility in the next stage. The algorithm's is effectiveness may be compromised when there is sudden decrease in treatment effect or a surge in outcome volatility in the next stage; see discussion in (Appendix D.
4 Numerical and empirical experiments
Simulated ramp schedule We now examine the following three experimental scenarios, for each (x,,()),,,,(());;, are iid sampled from (3) with variance o1)) = o(0)² 10 and means given
below:
PTE: Positive treatment effect, with (Mrse 0, Mone (1) 1;
ii)
NTE: Negative treatment effect, with Járue (0) and Mimee (1) 0;
iii) PNTE: Negative to positive treatment effect, with Mune (1) min (-2 + 0.5(l 1),
For each scenario, we set = 10 with N; = 500, Vt and we choose non non-informative prior (o(w)) = 0, (w)) = 100, w 0, 1. We assume model variance is known; however, using (6) to estimate the variance gives similar results. We repeat each scenario 500 times. Figure (a)-(c) show median, 25% and 75% quantile of the simulated ramp schedules (mz (me) and (h) show the budget surpluses Ere( Eier. (1,,(1) - (0)) B produced given different choices of B, 6, (be (be)se(r)) (A)e
Across the various scenarios, our model gives a reasonable ramp schedule. Large B, typically leads to more treated units and faster ramp-up. For the NPTE scenario, inadequate budget and low ruin tolerance can result in a failure to ramp up to 50% (m, = 250). We also found that reserving the budget for later stages by decreasing be A, in the initial stages leads to a faster ramp-up because more budget is available to support a swift increase when the treatment effect turns positive. This suggests that the experimenter may want consider reserving some budget for later stages if the treatment effect (1)
(1)- - (0) has not stabilized.
For PNTE scenario, compare our method to Thompson-samplinn bandit with tuning parameters and prior (1(1)= 2, no (0) = 0, (0) o1)))² 0.05 (see (27] and Appendix G for details). The prior is chosen so that the bandit can initialize conservatively depending on c. can be seen in Figure (i).(i) that the ramp schedule generated is rather sub-optimal and does not respect the budget. It also follows rigid pattern where with small c, the ramp-up initializes too aggressively, and for large c, the ramp-up proceeds too conservatively. These results demonstrate that our approach significantly outperforms the main existing alternative.
Semi-real Linkedln ramp schedule comparison Appendix F gives group-level statisties from 6-stage phased release run at LinkedIn. Due to privacy constraints, the individual-level data is not available and is simulated from 44) using stage-wise Aree (w), or (ww)(()))))) w = 0, 1 (both unobserved). The ramp-up schedules for different tuning parameters are shown Figure (d). It is noteworthy that the ramp-up schedule employed by Linkedln's 's data scientists, which was chosen without considering a specific budget, is roughly consistent with the budget-rationin schedule denoted as "ration-budger Linkedin" in the caption. Our results suggest that deducing the budget and risk tolerance associated with an experiment retroactively using our method is possible. We also run the experiment using Thompson sampling Bayesian bandit with the same prior as for NPTE above. In Figuue ff),, we again observe the rigidity issue: with small e, the ramp-up initializes too aggressively, and for large e, the ramp-up proceeds too conservatively.
8

---

250
CPOI (32)
60 100 30
200
3800 0.2)
20
(600) 321
Traateent droeg Bise
Trenvent drep Ste
Tremment Goog
150
150
130
125
1123
2122 KLD
2503 (02)
28.9 Sadgu!
(a) Ramp Schedule, PTE
(h) Ramp Schedule, NTE
(c) Ramp Schedule, NPTE
C15RA 201t
0301
ralon safortt sind
6301
Accal Lroddh
192
100
230
2000
(d) Ramp schedule, Linkedln
(e) Ramp Schedule, NPTE, TOM
(f) Ramp schedule, Linkedln, TOM
580
5/22
(-66, (DT) (166 (12)
(123
ED3 0.2)
(666, 01 nalot budgel
01 balgel
Sappe
300
Surpe
40
596
50
200
0050001
(g) Budget surplus, NTE
(h) Budget surplus, NPTE
(i) Budget surplus, NPTE, TOM
(i) nor:1.22%6/5%
(k) worc: 1.5%%
(1) bern: 1. 1.3%%
(m) fat: 1.24%/ % (n) 1e::: /
Line plots (a)-(i) show the median, 25% 75% quantiles of either the treatment group sizes or the budget surplus for the 500 simulations of the different experiment setups (PTE, NTE, NPTE, LinkedIn) using our model and Thompson-sampling Bayesian bandit. Under the legends "(B,d)", we set b. = A, = 1- (1 (1-))//T, Vt. We also use (i) "ration budget" to denote (B.8) = (-500, 0.01), b, = -400 Vt 5, b = -500 Vt > and A, = 1 (1 (1- 8) 1/T Vt; (ii) "ration tolerance" to denote (B, (-500, 0.01), b, -500, Vt and A. 0.0001, Vi < 5, A, 0.0019, Vt > 5 (iii) "actual LinkedIn" to denote the actual ramp up schedule used by Linkedln data
Figure 1:
scientists (iv) "ration-budget Linkedin" denote (B, (- 1500, 0.01), b, = -400, t 2 4, b.
15000, > 4, A, 1 (1- Particularly, (e), (f), (i) results using Thompson-sampinnn Bayesian bandit with different values of tuning parameter c, denoted by "TOM" in sub-caption, for experiment NPTE, Linkedln. We set B 500 produce (h), although the model is not budget-aware. Histograms (i)-(n) show distribution of the budget used over 5000 simulations. The red dashed line marks the budget available B 500. "z% 5%% in the sub-captions denotes that
the actual risk of ruin is 1% and the ruin tolerance is ò = 5%.

---

Budget-spent distribution To explore how our algorithms controls the risk of ruin and budget spending, we simulate following experiments for 5,000 times and plot distribution of the budget spent Ererd LITT (1,,(1) (0)) in Figure 1 ( (n): (i)norm: (Vt,(1), (z)( are sampled
o(1)² 2 = 10; (ii) corr: same as norm except that for each i, t, (1) is correlated with (0) with correlation coefficient 0.8 (ii) bern: jid
iid from (3) with Hare (0) = 0, Puse (1) = 1, (0))
iid (0) iid 6.4Bern(p 0.5786) and (1)) 6.4Bern(p 0.4224); (iv) fat: (0) 1+ /+v5
and (1) iid
/5t (v) dec: same as norm except Mone (1)(t) (t 1). Note that (iii), (iv) is configured so that (1) - (0)] = 1, V (O)) = V (1)) 10. For all the above experiments, we run T 10 stages with N, 500, Vt and we use non-informative prior [w(w) 0, (w)) 100, 0, 1.
As shown in Figure (m) the model successfully controls risk of ruin for (i)-(iv). The actual ruin risk is reasonable level (~ 1.2%) compared to the ruin tolerance given (5%). Note that the actual ruin risk are close for different outcome distribution. This is a consequence of central limit theorem and law of large numbers as discussed in (Secction 3.4 The model fails control risk of ruin for (v) as expected since the treatment effect keeps decreasing and the model assigns treatment based on past stages which leads higher-than-expeer eexeetex costs (cf. [Section 3.4).
(m)
Where t4 is Student-t distribution with degrees of freedom.
10

---

References
[1] Apple. App store: Release a version update in phases, 2023.
[2] Maryam Aziz, Emilie Kaufmann, and KarielKarelle Riviere. On multi-armed bandit designs for dose-finding clinical trials. The Journal of Machine Learning Research, 22(():686-723, 2021.
[3] Eytan Bakshy, Dean Eckles, and Michael Bernstein. Designing and deploying online field experiments. In Proceedings of the 23rd international conference on World wide web, pages 283-292, 2014.
[4] Donald A Berry Modified two-armed bandit strategies for certain clinical trials. Journal of the American Statistical Association, 73(362):33--355, 1978.
[5] lavor Bojinov and Somit Gupta. Online experimentation: Benefits, operational and methodolog- ical challenges, and scaling guide. Harvard Data Science Review, 4(3), 2022.
[6] lavor Bojinov and Karim Lakhani. Experimentation at yelp. Harvard Business School Case 621 226004 2020.
[7] lavor Bojinov and Neil Shephard. Time series experiments and causal estimands: Exact random- ization tests and trading. Journal of the American Statistical Association, page Forthcoming, 2019.
[8] Asaf Cassel, Shie Mannor, and Assaf Zeevi. A general approach to multi-armed bandits under risk criteria. In Conference learning theory, pages 1295-1306, PMLR, 2018.
[9] Semih Cayci, Atilla Eryilmaz, and Rayadurgam Srikant. Budget-constrained bandits over general cost and reward distributions. In International Conference Artificial Intelligence and Statistics, pages 1388-4398 PMLR, 2020.
[10] Joel QL Chang and Vincent YF Tan. A unifying theory of thompson sampling for continuous risk-averse bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 6159-6166, 2022.
[11] David. R. Cox. Plamning of Experiments. John Wiley Sons, New York, 1958.
[12] Debojit Das, Shweta Jain, and Sujit Gujar. Budgeted combinatorial multi-armed bandits. arXiv preprint arXiv:2202.03774, 2022.
[13] WF Eberlein. On euler's infinite product for the sine. Journal of Mathematical Analysis and Applications, 58(1):147-151, 1977.
[14] Nicolas Galichet, Michele Sebag, and Olivier Teytaud. Exploration vs exploitation vs safety: Risk-aware multi-armed bandits. In Asian Conference on Machine Learning, pages 245-260. PMLR, 2013.
[15] Andrew Gelman, John B Carlin, Hal Stern, and Donald Rubin. Bayesian data analysis. Chapman and Hall/CRC, 1995.
[16] Google. Play console help: Release app updates with staged rollouts, 2023.
[17] Jez Humble and David Farley. Continuous delivery: reliable software releases through build, test, and deployment automation. Pearson Education, 2010.
[18] Ron Kohavi, Alex Deng, Brian Frasca, Toby Walker, Ya Xu, and Nils Pohlmann. Online controlled experiments at large scale. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1168-1176, 2013.
[19] Odalric-Ambrym Maillard. Robust risk-averse stochastic multi-armed bandits. In Algorithmic Learning Theory: 24th International Conference, ALT 2013, Singapore, October 6-9, 2013. Proceedings 24, pages 218-233, Springer, 2013.

---

[20] Jialiang Mao and lavor Bojinov. Quantifying the value of iterative experimentation. arXiv preprint arXiv:2111.022 11.02334, 2021.
[21] Vianney Perchet, Philippe Rigollet, Sylvain Chassang, and Erik Snowberg. Batched bandit problems. The Annals of Statistics, pages 660-681, 2016.
[22] Donald B Rubin. Estimating causal effects of treatments in randomized and nonrandomized studies. Journal of educational Psychology, 66(5):688, 1974.
[23] Amir Sani, Alessandro Lazaric, and Rémi Munos. Risk-aversion in multi aaltidarmmd bandits. Advances neural information processing systems, 25, 2012.
[24] Sama Shrestha and Sonia Jain. A bayesian-bandit adaptive design for n-of-1 clinical trials. Statistics in Medicine, 40(7):1825-18444 2021.
[25] Jerzy Splawa-Neyman, Dorota M Dabrowska, and TP Speed. On the application of probability theory to agricultural experiments. essay on principles. section 9, Statistical Science, pages 465-472, 1990.
[26] Diane Tang, Ashish Agarwal, Deirdre O'Brien, and Mike Meyer. Overlapping experiment infrastructure: More, better, faster experimentation. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 17-26, 2010.
[27] Peter F Thall and Kyle Wathen. Practical bayesian adaptive randomisation in clinical trials. European Journal of Cancer, 43(5):859-866, 2007.
[28] Sattar Vakili and Qing Zhao. Risk-averse multi-armed bandit problems under vernnnar measure. IEEE Journal of Selected Topics in Signal Processing, 10(6):1093-111, 2016,
[29] Ryo Watanabe, Junpei Komiyama, Atsuyoshi Nakamura, and Mineichi Kudo. Kl-ucb-based policy for budgeted multi-armed bandits with stochastic action costs. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 100(11):2470- 2486,
2017.
[30] Tong Xia, Sumit Bhardwaj. Pavel Dmitriev, and Aleksander Fabijan. Safe velocity: practical guide to software deployment at scale using controlled rollout. 2019 IEEE/ACM 41st International Conference Software Engineering: Software Engineering in Practice (ICSE-
SEIP), pages 11-20. IEEE, 2019.
[31] Yingce Xia, Wenkui Ding, Xu-Dong Zhang, Nenghai Yu, and Tao Qin. Budgeted bandit problems with continuous random costs. In Asian conference on machine learning, pages 317-332. PMLR, 2016.
[32] Yingce Xia, Haifang Li, Tao Qin, Nenghai Yu, and Tie- Liu. Thompson sampling for budgeted multi-armed bandits. arXiv preprint arXiv:1505.00 150..000454444 46,46,170 2015.
[33] Ya Xu, Nanyu Chen, Addrian Fernandez, Omar Sinno, and Anmol Bhasin. From infrastructure culture: A/b testing challenges large scale social networks. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 2227-2236, 2015.
[34] Ya Xu, Weitao Duan, and Shaochen Huang. Sqr: balancing speed, quality and risk in online experiments. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 895-904, 2018.
[35] Qiuyu Zhu and Vincent Tan. Thompson sampling algorithms for mean-variance variance bandits. In International Conference on Machine Learning, pages 11599-11608, PMLR, 2020.
12

---

A Decompose risk-of-ruin to individual stages
Proof of Theorem 3.7
The last claim is trivial: it is easy to verify that ① and (2) hold if we let
T 0 for all & E [T] Now we prove the first and the second claim. The case for I 1 is trivial.
We assume T 2 2. For any t 2,..., T, we have that
P (Re v B) E|P
(R& B F(-1)]
S RB B Fi-1)
= E
B B P (R+ R
S
(4)
S (Ra-1 - B) - B, R > B Fi-1)]
=
P & B3 +E ((P (R-11 B F1-1) 0)
P (R4 S RA-1 >
-1 > B Fi-1)
+I(P(R(11> B = 0) (R4 S B, > B Fi-)
PR & B) + BB)
| 1 > B| Fr-1 > 0))
x (R, S B R4-1 > B, PP (1 ( > B| Fr
(
S P P S B) + A, T(P > B Fr-1) > 0) (Re-1 >> B BI Fr-1)
= -R S B) + A,P (R > B)
where (b) used that TP (R,-1 > B F(-1) = 0 T = 0 and that (:V,,))). 0) 0. which implies that almost surely
(R > B F(-1) = 0) PP (R, - B, > BB11>BBF--)
= [[P (R > B F(-1) = 0) RR + ((Y,.) IEN .0) B, > B F(-1)
= II( (R,-1> > B F(-1) = 0) P PR S B, R > B F.-1)
=0
and (c) used that b, 2 B, which implies that almost surely
PP P(R, S B R > B,F
< P (R, S b2 R > BiF S A.
Rearranging this, we obtain recurrence relation: for any 2.....? T
PRR > B) 2 (1 Ae) P (R--1 > B).
(14)
Using the recurrence relation repeatedly for all / E [T], we obtain
T
T
P > B) 2 II (1
A) ((1 > bn) 2 II
(1 (1-A4) A.)
1=2
1=1
T
= P(RR < B1 < - II (1 A.) 2
as required. To prove the second claim, observe that equality is attained in all of the above inequalities
if equality is attained in (14), (i), (6i) and (im)) and that equality is attained in (14) if equality is
attained in (a) and (c). Finally, note that equality in (a) is attained if r, S 0, vt E [T] and equality in (c) is attained if equality is attained in (i) and (iv).
B Stochastic domination
Lemma B.1 (Stochastic domination under truncation). For any two independent real random variable
X, Z and real number a, t R such that PXX a) > 0, we have that
IP + z
X
a) < P(X + t)t).
13

---

Proof of Lemma B. 1. Assume that P(X 2 a) > 0, or else the proof is trivial. We first claim that P X Z - 2 N a). Note that this holds if and only if
P(X- 22t
P(X > t - 2, < a)
PP - Z, 2 a)
IN
P(X<aa
P(X N a)
The above holds since its Ihs and rhs satisfies
P(X 2 1 Z, X <a)
P(X 2 1 1- Z, < a, a 2 1 1- 2)
<P(a 21
P X < a)
P(X < a)
P(X 2 1 Z, X 2 a)
P(X 21 - - Z,X 2 a, <1--1-1 7)
+ 2)
P(X 2 a)
P(X 2 a)
It then follows from law of total probability that
P(X + x = PX + 2 | X < <X) < + + /2/ a)P(X 20)
2 P(X + 2 2 t X < aX) <a) + P(X + 22t < a)p(X
= + X <
as required.
Proof of Lemma 3.2
If (
0, (8) holds with equality since 00 < S(1(1)- -
B < O. So, assume _ > 0 from now on. By 15th and the conditional distributions of multivariate Gaussian, we have
7 (T),
1/2 + Vi1 (0) - 14) + (V22 V21 V
where ~ (O, 1) is independent of (0) conditioned on Fi-1 and μ, V are defined (15). Here, we used that Vn since pn o2.r (0)) > by Definition 3.1 and M + Using the above and that S7 (0) o7 (0) - (0), we have
57 (T)
(V21 + 1)55 μ2 VilV 41
(V/2 - V22 Vni - V12)
1/2 V12)
(0),
Since V2, V2 +1> in the above, using also that b, ST (1), B E Fi 1 and that
of (1) is independent of (T), S7 (0). (8) follows from Lemma B.1
C Derivation of the decision rule
Proof of these facts follows from standard Bayesian analysis (see e.g.
15
Lemma C.1 (Posterior distributions). We have for 0, 1, E [T]
Mp.e(1) = E Pirue (1) Fm1
(o(1)
(15a)
(o)2
(1)²
1o( +
a(0)
(0)
(p.c(0) E Mrmoe (0) Fr-1
(15b)
(o)
(0)²
+
eo(
o00
0n,(1)) = v/ M (w) [ (
M, (w) aww)
(15c)
(w)) F1-1 ~ N (Mp,((w)), (p)(())))
(15d)
5f (T))) F(-1 N (Mpe(1).ma me, m m,, (1) + m, =0))²
(15e)
(S[,(0) (0)
(ST
Fr ~ N V).
(15f)
sT (0)
14

---

where
1 (p,((0) -, (p))(0) m
)
M (1) ,,,,
v=
m p.r m. (0)
D Robustness to non-identically distributed and nan-Saussian outcomes
Proof of Theorem 3.3 To show the experiment by Algorithm 1 is (6, B)-RRC under Definition 3.4 suffices to show that (.. 2 hold for each 2 Since U (2)
hold for each / 2 if = 0, we
only need to show that for each t 2 1, if my # 0, almost surely
P (1) 57 (0) > B F()
(16a)
P (1) 57 (0) s 6, F.-1, ST S7,(0) B) S D.
(16b)
Note that for each t 2 1, m, #0,
(T) ST (0) - i4
((S (1) - 5s (0) s b Fi-1) P
Sa 2 Fi-1
87 (1)
St (0) i4
S 21 Fi-1
A where we used first inequality in (3) (a), second inequality in 13 in (b), and 11 in (c).
We now show (16a) by induction. For = 1, if m. * 0. Algorithm ensures that
E (IP (57 (1) - sf (0) - 6, (i)) P (sT - $f (0) bb) < <
by construction, which implies that
((T ST (0) > B Fi) 2 P (8T(1) - 4 (1) >
almost surely. If m, = 0, then (1) - ST > B F.) = since B < 0. This proves the base case. For the inductive case, if m, + 0, Algorithm ensures that
E (P (57 (1) S7 (0) s b. | Fi) Fi-1) P (57 (1) - S7 (0) $ b, Fi $ A <1 by construction, which implies that
P (ST (1) ST (0) > B Fi) 2
P (S - ST 4 ( >0
almost surely. m, 0, we have that
P (ST (1) - ST---TT- (0) > B (1 -1)-()())0 > B F(-) >
from inductive hypothesis. This shows 16a
To show (Tbb), note that under Definition 3.4
[x] - S: (0) Fr. (()
- (7) (F- < S[1(1) B)
On the rhs, sT(1) - s7 (0) is independent of
[s]_(0) S7 < (1) B
and that (T) F1 It follows from these, 16a) and Lemma B.l that
IP (1)-- - ST_, < (()
(0) < sT
(P( ST (0) bb Fr
Therefore, for each
P 2 1, m; #0,
< ([) SA.
required. This concludes the proof.
15

---

When are
13 satisfied
Fix any t 2 1 where my # 0. Note that
8 (0 = Σ
Σ (0, (1,(
-
TT
rE|t-I]
The summands on the rhs are independent random variables under Definition 3.4 that when my or M sufficiently large,
We thus expect
$o (1) S7 (0) - ST Fi-1]
R N()
V (1) (0)) 1
by central limit theorem under mild nooenttgrowth conditions (e.g. Lyapunov's conditions). We thus expect that first condition in 13 holds when my or M are sufficiently large for each t 2 1.
We now focus on the second condition in 13 Suppose that A < 0.5, which implies 2, S 0 by Note that we can write
i = Σ (Y, YY,(0))
E Σ E (x. [Y,(1))
IT
rE(L-1]IET.
0f Σ
(1),,(1)- YY,(
Σ V(Y,((0)) o (X,,(I))
rE[t-1]
ET
and
Pr m. (1p,((1) (0)) (0.:(0)
o, = m. (a(1)² + (00))) + M a(0)² + + opa(1)²+ + (m. + - (0).
For
t= 1,
;== = Σ E (1) (0)), 8.= Σ V(i,(1 - (o)(
TET.
IET
and
e4 = mi (1o(1) - Mo(0)),
o,- = m4 (a(0)² + +1)²) + m (an(1)² oo))))
So, second condition in 13 holds for t = 1 if we have chosen prior and model parameters such that
(1) (0) S
E (1). (0))
iET!
a()) + +1() + m. ( -
Σ v (1)((1) - (,)(
iET
This corresponds to that choose prior and model parameters conservatively in the sense that do not overestimate treatment effect or underestimate its variability. Now fix any 2 2. From the law of large number, expect that for _ sufficiently large
(0)
Σ
Σ
E (0)
M relt
1] iET
Σ
Σ
(Y, Y.)(1)) ~0
Σ
Σ
E (Y)
M rE(t-11 1] TE,
M! rett-1] IET
(p.((1) (0)
Σ
Σ
E (1) (0)
M
rE(t-1
Σ
(V..( (r,(
Σ
Σ
EV (V, (2.())
M
rE(t-1) SET
rE(t-1]EET,
Σ
Σ
(0)
M SET
16

---

So if the treatment effects increase or stay roughly constant throughout the experiments
Σ
(Y). N M rEjt-1]iET.
E Σ E (Y, - Y.)
my
RET.
and our variance estimates a (0)), , are accurate or conservative in the sense that
00)
E E
(O), o00 o01)
1
Σ
(Y,,
-
Y2,(0))
M (1)
rE[t-1JiET,
TET:
the second condition in 13 holds for each 2 2 and the experiment produced by Algorithm (6, B)-RRC.
E Algorithm for general Bayesian models and costs
The following outcome model a generalization of Definition 3.1 Here, experiment outcomes are allowed to be multivariate with each coordinate corresponds different business metric.
Definition E.1 (General Bayesian model). Fix 9 2 1. The model parameter Ouuee E IR9 is generated from certain prior Tn- The experiment outcome of unit at stage are distributed independently and identically
Yr.(()), iid p(Orrue)
where (0), (0) E R29 and p(Oure) is a probability distribution on RRXx.
The following is a generalization Detinitin 2.1 It allows for general experiment cost beyond treatment effect. The cost of treating unit is now bą = (1))).,(1), (1.,... for some function h4 RPx chosen by the user. For instance, h can chosen to compute the worst treatment effect across multiple business metrics.
Definition E.2 (General experiment cost). For each t 2 1, let the experiment cost from stage-f and treated unit be his = h2 (YG,,())), (0)) where h; : RPxp + IR is any user-chosen function. Then define = Lier, hi.. We let Of T. 0. Define the cumulative experiment cost up to stage
t as Rg = _kejg Tk-
We now move to derive an explicit algorithm Algorithm 1 from Theorem 3.1 that output (m²) ) such that the experiment is (8, -RRC.. Compared to Algoorith I| the algorithm developed in this section will require Monte-Carlo simulations and generally gives more conservative ramp schedule.
We first review the Cantelli's inequality, which is an improved version of the well-known Chebyshev's inequality for one-sided tail bounds.
Lemma E.3 (Cantelli's s inequality). For any X N O, and real-valued random variable X with finte variance,
P(X E(X)
N A) < 1+
Given that (i) P (R,-1 2 F(-1) 0 and that (ii) E [[R,) Re-1 B,F.1l 2 be a direct
application of Cantelli's inequality shows that
P R < by R F(-)))
E Rd R > B, F. Rr 2 ER, R B,F-I] - R > B, B,Fl-1) IP
[Re Ri-1 > B- 66)
VRR. R B, B.
where Fo denotes trivial o-algebra.
17

---

Our strategy to construct an algorithm that selects ramp size such that 1 2 hold is as follows: we first verify that condition (i) holds: not, set m, 0 and otherwise find m. such that the following two inequalities hold
Re R 2 F 2 by
(17a)
A.
(17b)
(E Re-1 B.J, BBJ. ) V(Ri Re 1>B,Ft
To accomplish this, note that by exchangeability of the outcomes under Detinition E.1
E R 2 B.
+ + - [ E [r R 2 Bi
R 2 B,
(18)
m, [14=1, Ra-1 2 B, F- E Ri- 2 B, F(-i]
and
V (R, R₁-1 2 B,F--)) = V (r, R 2 B,F,-1 + V (R,-1
R 2 B.F.-))
+ Cov (rt, Rt-1 R4-1 2 B(---1)
m, (h=11 R₂-1 2 F(-1)
+ m. (m, - 1) Cov (hi=1,t: h1=2,1 Ra-1 2 F111-))
+ (R R 2 B, Fi-1) + Cov (ri, Ri-1 Re-1 2 F(-1)
(19)
We thus require a Monte-Carlo procedure to output estimates (0))), .4( for the following posterior quantities the rhs of 18].
19
P PR,-
> B F, + (,(
E (h Rt-1 2 B.)+-1 + (1)
E (R Re-1 2 1, + 4/
(hi=1,t R 2 F.-+)) t g/00)
Cov (hi=1,es h1=2,1 2,t R 2 B, + ((4)
v(R R 2 B, J 1- (3(0)
Cov Oo R₂-1 R 2 F, + $1
where hi=1,t. 24=2, denote costs from treating two units i = 1, 2 at stage t. Recall that under (...). the outcome of the units are exchangeable. So 1, simply refers to any two distinct units. These quan-
tities will be used to construct estimates of E [R, Ri-1 > B, Fr and V (Re R > B, as functions of m, chosen.
We now outline a procedure to construct (0) .... (0)) Firstly, suppose that we can obtain K samples from the posterior distribution
(Xt.: (O), (02)) Xo
(20)
from certain MCMC algorithms. The specific details of the MCMC algorithm will depend on the Bayesian model used, but generating preerito--peiitiveeeee samples while imputing unobserved data, as required in (20). is a common objective of such algorithms (see e.g. [1] Chapter 18]). Let us denote the K samples as
(K) (k) (0)) ( (1), (2, (0), y (1), == K (r (0) JET-.EE(-11] (x
(21)
These will give us K samples from [ h5=2,1 Re-1 Fi-1l as follows:
(2) h 1 12200 ((
ho Ty
y [b} (0) (0)) lo: (y - (K) (0)
ΣΣ hr (y.fh (1) - r v(() (0)) k= 1.1....,KK K r=ieET,
18

---

Then we can estimate P (Rt-1 2 BB Fe-1) by
K
PP (R 11-121 | Fc-1) < (r((0)
1
Σ
[(
B)
K
k=
Let
4. k : B C [
which denotes the subset of the K Monte-Calor samples for which the budgets are not depleted.
If (e(()) 0 = L. 0. we can simply out m4 0 since this corresponds to the case that the condition (i) does not hold, i.. (R, S by R > B, 1(1) 0. Otherwise, we continue to
construct (1)))...... (6, as follows:
E (h R 2 B))--) - (((1) |c
KEC.
(R R 2 B. B-F(-1) (p
1
Σ A(M)
[Cd
REL
1
((h=1, Ro-1 2 B, F1) + &i =
(f)(1))
|cel
REC
Cov (hy 11=2, R 2 F(1))
(22)
+ b
1
1= i 1
- (c((1)
1 Σ M
Le
KEL2
kEC.
V [Be-1 R 2 B,F+- + ((6))
(0)30) )2
Le
REC:
(6) Cov (him1,y Re-1 Rr-1 2 B,F+-) + Pi
[k) fet M (1)+
[eA
REC.
From
18
19 and the Monte-Carle estimates above, then have estimators for
R
R 2 B, F. [R, Ri-1 2 B, in terms of (1)))........).....)..))) (0)) as follows
E [R, Ra-1 2 B, -- my (x) + gt
(2)
v [Re Ra-1 2 BFF,1]++ + (m &
(3)
mc (m+ 1) 1)) ((55) + m (6)
The two inequalities in
17 then become
m4 (.(1) + (((0) b
(23a)
A
(23b)
m. pe -bp
+ ( +m; - -1)
t m
respectively. Assume that A, > O or else set m, = 0 directly. Observe that 23b can be written as, with g: = -,
A + B.m + C. 2 0
where
A. = (0)(1)) ((()(())
B, (1) (z(2) bbi) - -3 q (1) g
(24)
G = p bt) (5)) (5)
Then one can choose m, to be the largest, positive integer in the range defined by
m, (.(1) 6(?2 2 b,, Am + B.m, + C. 2 0
19

---

If the range does not contain any positive integer, we set = 0. Note that the range can be easily identified after solving the quadratic equation A,m; B,m, + C, 0. Algorithm 2 gives the algorithm that outputs ramp sizes adaptively. Note that by construction, it gives a (Ø. RR- experiments if the Monte-Carlo estimators are sufficiently accurate.
Algorithm 2 Output ramp size adaptively
Input: B 0, [0,
1: Initialize 1, II -=1
A,) +
2: while IT:== (1 - A,) 1 do
3: choose A, 0, -= b B
1-5
b.
4: run MCMC to obtain posterior samples in 21 and computes (0x(0)
5: if (0)) then my 0
6:
else
compute (I(1), ..... (()) using 22 and then A,, Br, C. by (2
7:
8:
find V, m E N n [0, N./2] (x +((()
b, A.m² Bmm C. 2 0]
9:
if V. + then
10:
my - max V/
11:
else
12:
my 0- 0
13:
end if
14:
end
15:
Output my and then conduct stage 1-experiment and observe the outcomes
16:
update t 1-t++
end while
We have conducted preliminary simulations of the proposed procedure for multivariate Gaussian outcome model with Gaussian-inverss -nihss prior, and observed satisfactory results. However, we defer presenting numerical results until future work when a more systematic investigation of Monte-Cand Carlo based procedures can be conducted.
F Linkedin experiment data
In Table below, Mhree (w), a (w)) w sample statistics from the actual LinkedIn experiment. Nr are incoming population size reduced by 10a factor for tractability on a personal computer.
Stages t
2
3
4
5
6
Pmree (0)
0.3648
0.3780
0.3752
0.2317
0.4009
0.3930
Prree (1)
0.3659
0.3788
0.3754
0.2317
0.4010
0.3941
(0) 2
2.0993
2.2769
2.0909
1.1165
2.2705
2.3982
(1))
2.0923
2.2248
2.0135
1.0526
2.2476
2.4430
N
10,756
10,460
10,598
7,580
10,550
10,688
Table I: Linkedin experiment data
G Thompson-sampling based Bayesian bandit
This algorithm is developed in 27 Section 4] for clinical trials. The algorithm assigns a user stage 2 1 to treatment with probability
I (frrue (1) Pune (0) Fr-1)
IP (i Ta)
(Muuee (1) Mure (0) Fe-1)² + (Nurue (1) < Pure (0) 1 Fc
20

---

for tuning parameter > 0. Under Detinition 3.1 by (5d). we have that
Hp,(11) - Mp.e(0)
P (Pure (1) > Mtre (0) Fi-1) = db
(0)) + pp.
21


Reviews:
[{"review_id": "GG5wh7GZ0A", "reviewer": "Reviewer_mRfu", "summary": "The authors address the problem of finding a risk-sensitive strategy for phased releases. A model that involves a risk budget is proposed and an algorithm based on Bayesian updates is presented to find a solution. The proposed algorithm is empirically tested on a range of problem setups and is shown to outperform existing bandit algorithms.", "questions": "Page 9 L259 I suppose this is NPTE rather than PNTE. It does make me wonder why there is no PNTE scenarios in the experiments.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem setup and the proposed model for phased release seem novel to me. Although this is arguably a rather narrow and specific problem, the authors do contribute some useful ideas in applying the Bayesian approach to a challenging problem, which could be valuable to the NeurIPS community. The paper is easy to read and overall presentation is clear.\n", "weaknesses": "The proposed model is simple enough to avoid the need for tedious sampling-based solutions. However, one wonders whether some of the parameters (such as the risk budget) can be easily instantiated in real-world scenarios. The i.i.d. assumption simplifies the analysis but again one wonders whether it would lead to overly conservative or overly risky solutions in practice. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time spent reading our paper and encouraging remarks. We would like to take this opportunity to respond to the questions raised. \n\n>\"Although this is arguably a rather narrow and specific problem, the authors do contribute some useful ideas in applying the Bayesian approach to a challenging problem, which could be valuable to the NeurIPS community.\"\n\nWe agree with the reviewer that we are fundamentally solving the phased release problem. It's important to note that phased release stands as a significant challenge in its own right, affecting nearly every tech company due to the widespread use of A/B tests. The reviewer's perception of the problem is narrow and specific might stem from the fact that the bandit community has yet to explore this problem extensively, as most bandit algorithms have been tailored for more \"main-stream\" applications such as the recommender systems. The phased release problem presents a distinctive array of challenges, which renders existing bandit algorithms unsuitable for direct application.\n\nWith that in mind, we would also like to point out that the ideas presented in our paper are valuable in other scenarios where there is a need to adaptively infer an unobserved or partially observed budget whilst not depleting the budget with a high probability. For instance, this often happens in clinical trials, where balancing the trade-off between treating patients and experimenting with different treatment options is critical; our approach can explicitly quantify and control the extent to which subjects' treatment efficacy can be sacrificed (i.e., the budget) in return for more thorough experimentation on underperforming treatment options. \n\n\n>\"However, one wonders whether some of the parameters (such as the risk budget) can be easily instantiated in real-world scenarios.\"\n\nSetting the right budget and risk of ruin parameters is crucial in practical applications. In fact, our approach was motivated by the attempt to quantify \"latent budgets\" that nearly all product teams have in mind when conducting phased release. For example, product teams may terminate the experiment if they observe a large drop in purchases of a certain services upon the feature update (i.e. negative treatment effect). They typically have a rough threshold in mind for how large such negative treatment can be for the different business metrics (e.g., revenue, sales, engagement) before they make a subjective decision to ramp down or terminate the experiment. The risk budget parameter effectively quantifies such thresholds and make it transparent to the management. Overtime, this will be conducive to a firm-wise standard for releasing features of different categories. \n\nWe also note that businesses employing phased releases typically possess a history of experiments with the same set of metrics. The companies can thus leverage historical data to retrospectively test choices of the allocation of budget ($B$) and probabilities of risk ($\\delta$). Such retrospective analysis will yield guidelines for how to select these parameters in a way that leads to logical and favorable business outcomes in future experiments. \n\n>\"The i.i.d. assumption simplifies the analysis but again one wonders whether it would lead to overly conservative or overly risky solutions in practice.\"\n\nWe acknowledge that the i.i.d. assumption can be restrictive in certain practical settings. For example, a main reason the i.i.d. assumption would be violated is when there is interference between experimental units, meaning that one unit's treatment assignment impact's another's outcome. We agree with the reviewer that this work does not account for this type of violation, potentially leading to sub-optimal designs when they occur. However, our work was motivated by the setup in the technology industry where i.i.d. assumptions are common. Properly dealing with interference usually requires much more sophisticated designs and goes beyond the scope of this work. That said, handling interference in our proposed framework would be an exciting area of investigation for future work. \n\n\n>\"Page 9 L259 I suppose this is NPTE rather than PNTE. It does make me wonder why there is no PNTE scenarios in the experiments.\"\n\nWe apologize for the typo. Lines 259 to 265 pertain to NPTE. The PNTE scenarior the reviewer refers to is the case where the feature update become worse and worse throughout the experiment. We omitted ramp schedule for the PNTE scenario due to limited space: PNTE resembles NTE in Figure 1 (b). In both cases, the algorithm ramps up initially to explore true treatment effect, then ramps down as the budget depletes (treatment effect is negative in NTE or goes negative in PNTE). We opted to present the more interesting NPTE case, where the algorithm ramps up for true effect exploration, down for initial adverse effect, and up again as the effect turns positive. \n\nIn practice, NPTE is also much more prevalent than PNTE. The former captures the phenomenon that experimenters can learn from early stages of the experiment and improve their features based on this early feedback. This is indeed a key value in implementing phased release in a product development process. It is very rare for experimenters to actively modify the treatment and make it worse after digesting all the insights in previous iterations.\n\nHowever, we did plot the budget distribution in a adversarial scenario where the feature is persistently negative and deteriorates as the experiment progresses (see Figure 1, (n)) and discussed how our algorithm may yield overly confident ramp in this scenario (Lines 287-292, 238-239). Basically, if the new feature suddenly becomes much worse than in the previous stages, the algorithm will need at least one stage to learn this before it can ramp-down in response.  "}, {"review_id": "gsjdbkUrMw", "reviewer": "Reviewer_m8cf", "summary": "The paper presents an algorithm for conducting automated phased release strategies that balance risk and reward by controlling the risk of ruin while maximizing ramp-up speed. The authors propose a framework that models the problem as a constrained batched bandit problem and uses an adaptive Bayesian approach. The algorithm is designed to be efficient and parallelizable, and is claimed to be robust to model misspecifications.", "questions": "In Figure 1 (b), the line plot does indeed reach close to zero and then increase. This behavior can be attributed to the algorithm adapting to the realized outcomes. When the outcome is negative, the algorithm may still use the remaining budget to explore further, rather than stopping the experiment immediately. It is possible that the algorithm is designed to learn from past observations and adjust treatment assignments accordingly, which could explain this behavior. However, it would be helpful if the authors provided more insights into the reasons behind this behavior and whether any modifications could be made to the algorithm to address this concern.\n\nIn line 172, the mention of \"some prior estimate\" is not specific about which parameter should be determined first. The authors could clarify this by providing examples of which parameters are typically estimated in practice, such as the treatment effect or the variance of outcomes.\n\nIn line 5 of Algorithm 1, it appears to be a typographical error. The correct values for w should be 0 and 1 (i.e., w = 0,1), as these values correspond to the treatment and control groups in the paper. ", "limitations": "Revise Section 3 to provide a clearer problem definition and discuss the objectives of the proposed algorithm in more detail.\n\nExplain the design aspects of the algorithm that contribute to maximizing ramp-up speed, and how these aspects are balanced with the need to control risk. The paper could benefit from additional experimental results that compare the proposed algorithm with baseline methods in terms of ramp-up speed under the same violation rates. This would help demonstrate the algorithm's effectiveness in balancing risk and quickly ramping up compared to other methods. The authors may consider conducting more experiments or simulations to showcase the superiority of their approach in this regard.\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality:\n\nThe tasks and methods presented in the paper are relatively new and provide a novel approach to phased release strategies in the technology industry.\nThe work combines well-known techniques, such as constrained batched bandit problems and adaptive Bayesian approaches, in a unique and valuable way.\n\n\nQuality:\n\nThe submission is technically sound, with the proposed algorithm built upon a solid theoretical foundation.\nThe claims are well supported by both theoretical analysis and experimental results, including simulations and a semi-real LinkedIn data experiment.\n\n\n", "weaknesses": "Clarity in Section 3: The authors introduce the concept of the risk-of-ruin-constrained (RRC) experiment, but the problem definition and objectives of the proposed algorithm are not explicitly presented. In the abstract and introduction, the authors mention to balance risk control and maximize ramp-up speed. However, the paper lacks a clear explanation of how the algorithm's design specifically contributes to maximizing ramp-up speed. The algorithm's goal appears to be to output the treatment group size while satisfying the budget constraint. A clearer problem definition and a more direct explanation of the algorithm's goals would help readers better understand the problem being addressed and the significance of the proposed solution.\n\nMaximizing ramp-up speed: In the experimental results, the authors mention that a larger budget (B) and higher risk tolerance can lead to faster ramp-ups. However, the connection between the algorithm's design and its ability to achieve faster ramp-ups is not explicitly discussed. Upon a closer examination of the paper, the authors propose a decomposition scheme in Theorem 3.1, which breaks the risk constraint into stage-wise constraints. This approach helps control the current-stage cumulative experiment cost, given past observations, and determines the treatment assignment based on the posterior inference of the remaining budget. However, the paper could further elaborate on how these stage-wise constraints or the algorithm's design contribute to optimizing ramp-up speed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's careful reading of our paper. We've addressed their feedback in the responses below. We kindly request the reviewer to reconsider their acceptance opinion, taking into account of the suggested revision and the attached one-page PDF simulations that address their concerns on baseline comparison.\n\n>\"Clarity in Section 3: The authors... proposed solution.\"\n\n>\"Revise Section 3...more detail.\"\n\nTo further clarify the problem definition and the objective of the algorithm, which is to maximize ramp-up speed under budget constraints, we plan to add the following to Section 3:\n\nAt each stage $t=1,...T$, $N_t$ users will enter the experiment; the experimenter must then determine the number of users to be assigned to the treatment, denoted by $m_t\\in [0, N_t/2]$. The objective is to maximize $\\sum_{i=1}^T m_t$ while ensuring that the experiment satisfies the RRC experiment conditions (within budget with high probability by the end of the experiment).\n\nOur strategy is to decompose the overall constraint (i.e., that the experiment is RRC) into a sequence of stage-wise adaptive constraints using Theorem 3.1. Then we solve a sequence of sub-problems: maximize $m_t$ under the stage-wise constraint for the $t$-th stage. These stage-wise constraints simplify to (11) under the Gaussian model, and we can find a maximum $m_t$ satisfying (11) by solving a simple quadratic equation defined in line 193 with coefficients (12). In this sense, our algorithm solves a relaxed version of the original optimization problem of finding an RRC experiment that maximizes $\\sum_{i=1}^T m_t$. We, however, emphasize that the way the original problem is relaxed has crucial practical implications. See next point, as well as our global response.\n\n>\"Maximizing ramp-up speed:...ramp-up speed.\"\n\nThe algorithm will initialize from a conservative prior, which ensures that $m_t$ starts small in first few stages. The algorithm then observes experiment outcomes and updates the prior at each stage. Note that the stage-wise constraints are set up to be adaptive (Eq. (2) conditions on all past information $\\mathcal{F}_{t-1}$ ). So, if the feature turns out to be safe, the stage-wise constraints will relax in response: note that Eq. (11), Eq. (2) under Gaussian model, will hold for larger $m_t$ if posterior treatment effect takes larger, positive value. Since we always choose the largest $m_t$ satisfying the stage-wise constraint, this leads to the ramp-up of $m_t$—--that is, more users assigned to treatment. Note that stage-wise constraints will also accounts for other posterior statistics (e.g. posterior variance, c.f. Eq. (2)) when determining the ramp size. \n\nIn short, our algorithm generates fast ramp up since it maximizes $m_t$ within stage-wise constraints that both uphold the global constraint and incorporate all information collected throughout the experiment. \n\n\n>\"In Figure 1 (b), the line plot...this concern.\"\n\nThe reviewer's assessment is accurate. In Figure 1 (b), we observe how our algorithm's response to an unfavorable released feature. Initially cautious due to conservative prior, the algorithm gradually ramps up as it update the prior. However, the budget eventually depletes due to persistent negative effect, leading to the experiment being ramped down and terminated. \n\nWe clarify that this behavior aligns with our desired objective: utilize the available budget to maximize our precision at estimating the treatment effect, even when it is negative. In other words, the algorithm is designed to allocate as many users to the treatment as the budget allows. Also note that during the release, the product team may update the feature to incorporate the early negative feedback received so far. Therefore, a sub-par release might improve after the initial few stages.\n\n>\"In line 172, the mention ... outcomes.\"\n\nBased on our experience, the algorithm is robust to these choices and performs well as long as these parameters are set conservatively. For instance, one can simply set $\\mu_0(0)=\\mu_0(1)=0$ and $\\sigma_0(0)^2, \\sigma_0(1)^2, \\sigma(0), \\sigma(1)$ to reasonably large values, as we did in the simulation. This ensures that the experiment begins with a small number of users assigned to treatment in the first iteration. \n\n>\"In line 5 of Algorithm 1, it appears to be a typographical... paper.\"\n\nThis is indeed a typo. We thank the reviewer for the careful reading.\n\n>\"Explain the design aspects of the algorithm... this regard.\"\n\nThe baseline algorithm is Thompson sampling-based bandit (Appendix G). Unaware of a budget, it balances risk-reward trade-off using scalar parameter $c$: small $c$ balances user allocation for faster ramp-up, while large $c$ favors better-performing group assignment, reducing risk.\n\nIf we understand correctly, the reviewer suggests that we tune $c$ so that the experiment has the same budget violation probability under both methods and compare whether our algorithm will indeed ramp up faster. We provide such an example in the one-page PDF where we tune $c$ so that the Thompsons sampling bandit's budget violation probability is 3.7% in the adverse NTE setting (Line 245), matching the violation probability achieved by our algorithm in the same setting. Keeping the same tuning parameters, we show that our algorithm indeed ramps up faster in the PTE and NPTE settings (PTE, line 244, NPTE line 246). \n\nWe however stress that the baseline algorithm's main weakness is accurately determining $c$ without oracle knowledge, to achieve a target budget violation probability. In our one-page PDF simulation, finding an optimal $c$ required trial and error, i.e. repeating the same experiments many times (and thus used oracle knowledge). Thus, our manuscript doesn't emphasize comparing ramp-up speeds with an optimally tuned baseline. Instead, we showed how the baseline performs for different $c$ values, and how it is often overly cautious or overly aggressive. "}, {"review_id": "dEkUKiRenk", "reviewer": "Reviewer_hXT6", "summary": "This paper considers the problem of phased releases and formulates the problem into a batched bandit. ", "questions": "no", "limitations": "no", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This paper is very well-written and  the problem very motivated. It is great to see bandit algorithm to solve a real-world application rather than stay in the theory world. The algorithm is fairly simple and this paper is well-executed with theory and experiments. I am glad to see the semi-real linkedIN experiments. \n", "weaknesses": "The algorithm is fairly simple and the theory is routine. Well for an application paper, we should not expect the algorithm to be quite complex. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our gratitude for taking the time to review our paper and for providing your encouraging remarks. We will respond to the following remark given that it is listed as weakness of the paper. \n\n>\"The algorithm is fairly simple and the theory is routine. Well for an application paper, we should not expect the algorithm to be quite complex.\"\n\nThe primary objective behind designing a simple algorithm was to ensure its practicality on a large scale and its user-friendly implementation for practitioners. By maintaining simplicity, our intention was to facilitate its smooth incorporation into current infrastructure, promoting widespread adoption. Tech companies often have access to parallel processing tools like Spark, which can efficiently compute moment information such as sample mean and sample variance. Leveraging these readily available computations, practitioners can effortlessly employ our algorithm without encountering significant technical hurdles.\n\nFurthermore, the simplicity of our approach brings another important advantage: the ability to control the tails of budget spent without resorting to rare event simulation. To keep the cost of the experiment below a set budget with high probability, one typically needs to generate thousands of simulations of how the experiment might unfold, conditioned on the observations collected so far, and adjust the ramp schedule so that budget violation occurs only under a small portion (e.g. 1%) of the generated scenarios. Given the large volume of incoming users, conducting rare-event simulations would be extremely challenging and computationally expensive. Our method circumvents this issue by using only the moment information, and thus provides a practical solution without the need for complex simulations.\n\n>\"the theory is routine...\"\n\nWe believe that our theoretical result Theorem 3.1 could be of interest to Bayesian bandit designs in setting where there is a need to adaptively infer an unobserved or partially observed budget whilst not depleting the budget with a high probability (see the example of clinical trials in our global response). As far as we know, this result represents a novel contribution that could be very useful to practitioners, although we acknowledge that the induction argument used to prove the theorem may not seem very challenging to theorists.\n\nIn contrast to a more routine union-bound based approach where the total budget is partitioned and allocated to each stage a priori (e.g. fix $T$ stages and allocate $B/T$ budget to each stage and apply union bound), our approach involves an adaptive breakdown of the overall risk constraint into stage-wise constraints, as demonstrated in Theorem 3.1. Notably, this adaptive breakdown \n1. allows for carrying over unused budget from previous iterations to future ones, \n2. enables the stage-wise constraints to adapt based on past data (e.g. the constraints will relax as the algorithm learns that the new feature is indeed safe), and \n3. does not require $T$ to be fixed a priori\n4. allows the experimenter to adjust stage-wise budget allocation ($b_t$) and stage-wise tolerance ($\\Delta_t$) on-the-fly while maintaining the global constraint unchanged (e.g. the experimenter may reserve a portion of budget for later if they anticipate more adjustment of the released feature)."}, {"review_id": "iFfI1MoLtF", "reviewer": "Reviewer_8PYx", "summary": "This paper deals with a problem of gradually releasing a resource to a population modeled as a risk-of-ruin constrained experiment. Namely, at every stage $t$ we have an arriving population $\\mathcal{N}_t$, and we need it into a control and treatment groups $\\mathcal{C}_t$ and $\\mathcal{T}_t$ respectively (the treatment group is assumed to be the one receiving the resource). However, this resource allocation can potentially come at some cost, which depends on the population receiving the treatment. The goal of the problem at hand is to keep the overall such cost under a specified threshold (budget constraint), while minimizing the number of rounds/stages it takes to cover at least half of the underlying population.\n\nAs the authors nicely explain, this model has natural applications in the phase release of software products/updates.\n\nFor this problem, the authors give an adaptive Bayesian algorithm that satisfies the budget constraint with probability $1-\\delta$. Namely, given any confidence $\\delta$, the algorithm achieves the desired guarantees with probability $\\geq 1-\\delta$. ", "questions": "Look at the previous section.", "limitations": "N/A", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1) The problem seems well-motivated.\n\n2) The paper presents both sound theoretical results and a validating experimental evaluation.\n\n3) To my understanding (and take this with a grain of salt since I am not knowledgeable in this area) based on what the authors mention in their related work, devising a structured algorithmic way of dealing with the phase release problem in this way is novel. ", "weaknesses": "1) I found the presentation a bit incomplete and difficult to follow at certain points:\n\na) Are the arriving subpopulations between different stages disjoint?\nb) When you say that the \"stopping condition\" is covering half of the population, does that mean half of $\\cup{t \\geq T}\\mathcal{N}_t$?\nc) Besides defining the RRC experiment, it would be useful to formally define the whole problem, including the optimization objective.\nd) It would be nice to give some further motivation behind the experiment cost in Definition 2.1. Why is this cost capturing something meaningful? \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time spent reading our paper and encouraging remarks. We appreciate reviewer's feedback on the points that might be confusing to readers and will incorporate the clarification remarks to these points in future versions of this manuscript. We would also refer the reviewer to our global responses. \n\n>\"I found the presentation a bit incomplete and difficult to follow at certain points:\na) Are the arriving subpopulations between different stages disjoint? b) When you say that the \"stopping condition\" is covering half of the population, does that mean half of \n? c) Besides defining the RRC experiment, it would be useful to formally define the whole problem, including the optimization objective. d) It would be nice to give some further motivation behind the experiment cost in Definition 2.1. Why is this cost capturing something meaningful?\"\n\n\nTo answer reviewer's question:\n* **(a)** Yes, we assume a new batch of users arrive at each time $t$. \n* **(b)** At stage $t$, $N_t$ users arrive. Ideally, the experimenter would like to assign $N_t/2$ of the users to treatment group (they will experience the new feature) and $N_t/2$ of the users to control group (they will continue to use the pre-update version of the software) at each time to yield the most power for statistical testing. However, there is a concern that, if the new feature is sub-optimal, too many incoming users will be negatively affected. Our algorithm thus starts by assigning only a small portion of users to treatment in the first stage and gradually ramp-up to an even-split (i.e., half of incoming users $N_t$) if the new feature is deemed safe. Meanwhile, if the feature is deemed not safe, the experiment could be ramped down and terminate at $m_t=0$. \n* **(c)** We thank the reviewer for comments and suggestions for revision---we agree that readers will benefit from a clearer definition of the problem that highlights the optimization aspect of the approach, such as the objective. We will now briefly explain how the algorithm is designed to maximize ramp-up speed under budget constraints, which we will include in the manuscript. \n\n    At each stage $t=1,...T$, $N_t$ users will enter the experiment; the experimenter must then determine the number of users to be assigned to the treatment, denoted by $m_t\\in [0, N_t/2]$. The objective is to maximize $\\sum_{i=1}^T m_t$ while ensuring that the experiment satisfies the RRC experiment conditions (within budget with high probability by the end of the experiment).\n\n    Our strategy is to decompose the overall constraint (i.e., that the experiment is RRC) into a sequence of stage-wise, adaptive constraints using Theorem 3.1. Then, we solve a sequence of sub-problems: maximize $m_t$ under the stage-wise constraint for the $t$-th stage. These stage-wise constraints simplify to (11) under the Gaussian model, and we can find a maximum $m_t$ satisfying (11) by solving a simple quadratic equation defined in line 193 with coefficients in (12). In this sense, our algorithm solves a relaxed version of the original optimization problem of finding an RRC experiment that maximizes $\\sum_{i=1}^T m_t$. We, however, emphasize that the way the original problem is relaxed has crucial practical implications. In particular, the stage-wise constraints of Eq. (2) in Theorem 3.1 are \\textit{adaptive}: if we observe a feature is not adversely affecting user experience in past stages, the constraints for future stages will relax and thus more users can be assigned to treatment group safely, and vice versa. \n* **(d)** In practice, the experiment cost is quantified with respect to a specific business metric (represented by $Y$ with our notation). For example, user engagement metrics, such as the number of clicks on the organic posts, are often picked as guardrail metrics when optimizing the ads delivery system for the website. Suppose that the treatment simply increases the number of ads on the website. In this case, the organic engagement metric would drop in the experiment, capturing the negative impact of the treatment. Our definition of the experimentation cost is trying to capture the total cost of such impact aggregated over all treatment units across all iterations. Various other business metrics could also be considered, such as the number of website visits, sales of particular products or services, or a combination of multiple metrics. The choice of such business metrics depends on the applications and is beyond the scope of this work."}]

Author rebuttal:
***We provide a one-page PDF of simulation requested by reviewer m8cf in the attachment.**

We extend our gratitude to all the reviewers for their diligent review of our paper, and we highly value the insights they have provided through their feedback. We intend to consolidate our responses into a comprehensive global reply, aiming to offer a synthesized perspective that might be beneficial to the broader readership.

**Broader impact**: Although we are fundamentally solving the the phased release problem (an important problem to tech industry in its own right but largely overlooked by the bandit community), the ideas presented in our paper are valuable in other settings where there is a need to adaptively infer an unobserved or partially observed budget whilst not depleting the budget with a high probability. For instance, this often happens in clinical trials, where balancing the trade-off between treating patients and experimenting with different treatment options is critical; our approach can explicitly quantify and control the extent to which subjects' treatment efficacy can be sacrificed (i.e., the budget) in return for more thorough experimentation on underperforming treatment options. 

**Summary of the setting and the optimization objective**: At each stage $t=1,...T$, $N_t$ users will enter the experiment; the experimenter must then determine the number of users to be assigned to the treatment, denoted by $m_t\in [0, N_t/2]$ ($N_t/2$ since statistical tests have max power under even-split experimentation). The optimization problem is to maximize $\sum_{i=1}^T m_t$ while ensuring that the experiment satisfies the RRC experiment conditions (within budget with high probability by the end of the experiment). 

**Summary of our solution**: Our strategy is to decompose the overall constraint (i.e., that the experiment is RRC) into a sequence of stage-wise adaptive constraints using Theorem 3.1. Then we solve a sequence of sub-problems: maximize $m_t$ under the stage-wise constraint for the $t$-th stage. These stage-wise constraints simplify to (11) under the Gaussian model, and we can find a maximum $m_t$ satisfying (11) by solving a simple quadratic equation defined in line 193 with coefficients (12). In this sense, our algorithm solves a relaxed version of the original optimization problem. We, however, emphasize that the way the original problem is relaxed has crucial practical implications. See next two points. 

**Why our approach can yield fast ramp up**: The algorithm will initialize from a conservative prior, which ensures that $m_t$ starts small in first few stages. The algorithm then observes experiment outcomes and updates the prior at each stage. Note that the stage-wise constraints are set up to be adaptive (Eq. (2) conditions on all past information $\mathcal{F}_{t-1}$ ). So, if the feature turns out to be safe, the stage-wise constraints will relax in response: note that Eq. (11), Eq. (2) under Gaussian model, will hold for larger $m_t$ if posterior treatment effect takes larger, positive value. Since we always choose the largest $m_t$ satisfying the stage-wise constraint, this leads to the ramp-up of $m_t$—--that is, more users assigned to treatment. Note that stage-wise constraints will also accounts for other posterior statistics (e.g. posterior variances accounting for model uncertainty, c.f. Eq. (2)) when determining the ramp size. 

In short, our algorithm generates fast ramp up since it maximizes $m_t$ within stage-wise constraints that both uphold the global constraint and incorporate all information collected throughout the experiment.

**Novelty of Theorem 3.1 as alternative to union bound approach**: We believe that Theorem 3.1 could be of interest to bandit designs in setting where there is a need to adaptively infer an unobserved or partially observed budget whilst not depleting the budget with a high probability.

In contrast to a more routine union-bound based approach where the total budget is partitioned and allocated to each stage a priori (e.g. fix $T$ stages and allocate $B/T$ budget to each stage and apply union bound), our approach involves an adaptive breakdown of the overall risk constraint into stage-wise constraints, as demonstrated in Theorem 3.1. Notably, this adaptive breakdown 
1. allows for carrying over unused budget from previous iterations to future ones, 
2. enables the stage-wise constraints to adapt based on past data (e.g. the constraints will relax as the algorithm learns that the new feature is indeed safe), and 
3. does not require $T$ to be fixed a priori. 

As far as we know, this result represents a novel contribution, although we acknowledge that the induction argument used to prove the theorem may not seem very challenging to theorists.

Meta-review: All reviewers appreciated the theoretical novelty of the adaptive learning based phased release. The paper is also a nice contribution to the budget-constrained bandits literature from a methodological standpoint. Please incorporate all the feedback made by the reviewers, as they are constructive.
Decision: Accept (poster)