{'fraction_non_alphanumeric': 0.039006112511655214, 'fraction_numerical': 0.012086887453810823, 'mean_word_length': 4.329437747308365, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 21, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On Multi-Armed Bandit Designs for Dose-Finding Clinical Trials

We study the problem of finding the optimal dosage in early stage clinical trials through the multi-armed bandit lens. We advocate the use of the Thompson Sampling principle, a flexible algorithm that can accommodate different types of monotonicity assumptions on the toxicity and efficacy of the doses. For the simplest version of Thompson Sampling, based on a uniform prior distribution for each dose, we provide finite-time upper bounds on the number of sub-optimal dose selections, which is unprecedented for dose-finding algorithms. Through a large simulation study, we then show that variants of Thompson Sampling based on more sophisticated prior distributions outperform state-of-the-art dose identification algorithms in different types of dose-finding studies that occur in phase I or phase I/II trials.


Introduction
Multi-armed bandit models were originally introduced in the 1930's as a simple model for a (phase III) clinical trial in which one control treatment is tried against one alternative (Thompson, 1933). While those models are nowadays widely studied with completely different applications in mind, like online advertisement (Chapelle and Li, 2011), recommender systems (Li et al., 2010) or cognitive radios (Anandkumar et al., 2011), there has been a surge of interest in the use of bandit algorithms for clinical trials (see Villar et al. (2015)). More broadly, Adaptive Clinical Trials have received an increased attention (Pallmann et al., 2018) as the Food and Drug Administration recently updated a draft of guidelines for their actual use (Food and Drugs Administration (FDA), 2018). In this paper, we focus on adaptive designs for phase I and phase I/II clinical trials for single-agent in oncology, for which adaptations of the original bandit algorithms may be of interest.
Phase I trials are the first stage of testing in human subjects. Their goal is to evaluate the safety (and feasibility) of the treatment and identify its side effects. For non-life-threatening diseases, phase I trials are usually conducted on human volunteers. In life-threatening diseases such as cancer or AIDS, phase I studies are conducted with patients because of the aggressiveness and possible harmfulness of the treatments, possible systemic treatment effects, and the high interest in the new drug's efficacy in those patients directly. The aim of a phase I dose-finding study is to determine the most appropriate dose level that should be used in further phases of the clinical trials. Traditionally, the focus is on determining the highest dose with acceptable toxicity called the Maximum Tolerated Dose (MTD). Once the initial safety of the drug has been confirmed in phase I trials, phase II trials are performed on larger groups and are designed to establish the efficacy of the drug and confirm the safety identified in phase I. In phase II dose-finding studies, the dose-efficacy relationship is modeled in order to estimate the smallest dose to obtain a desired efficacy, called the minimal effective dose (MED). Approaches that use both efficacy and toxicity to find an optimal dose are called phase I/II designs. If the new potential treatment shows some efficacy in phase II, it is compared to alternative We indeed show that the algorithm can exploit the monotonicity assumption on the toxicity probabilities that are common for MTD identification (Section 4.1), but also deal with more complex assumptions on both the toxicity and efficacy probabilities that are relevant for trials involving MTAs (Section 4.2). Through extensive experiments on simulated clinical trials we show that our Thompson Sampling variants typically outperform state-of-the-art dose-finding algorithms. Finally, we propose a discussion revisiting the treatment versus experimentation trade-off through a bandit lens, and explain why an adaptation of existing best arm identification designs (Audibert et al., 2010;Karnin et al., 2013) seems currently less promising for dose-finding clinical trials.
The paper is structured as follows. In Section 2, we present a multi-armed bandit (MAB) model for the MTD identification problem and introduce the Thompson Sampling algorithm. In Section 3, we propose an analysis of Thompson Sampling with independent Beta priors on the toxicity of each dose: We provide finitetime upper-bounds on the number of sub-optimal selections, which match an (asymptotic) lower bound on those quantities. Then in Section 4, we show that Thompson Sampling can leverage the usual monotonicity assumptions in dose-finding clinical trials. In Section 5, we report the results of a large simulation study to assess the quality of the proposed design. Finally in Section 6, we propose a discussion on the use of alternative bandit methods.

Maximum Tolerated Dose Identification as a Bandit Problem
In this section, we propose a simple statistical model for the MTD identification problem in phase I clinical trials and show that it can be viewed as a particular multi-armed bandit problem.
A dose-finding study involves a number K of dose levels that have been chosen by physicians based on preliminary experiments (K is usually a number between 3 and 10). Denoting by p k the (unknown) toxicity probability of dose k, the Maximum Tolerated Dose (MTD) is defined as the dose with a toxicity probability closest to a target: k * ∈ argmin k∈{1,...,K} where θ is the pre-specified targeted toxicity probability (typically between 0.2 and 0.35). For clinical trials in life-threatening diseases, efficacy is often assumed to be increasing with toxicity, hence the MTD is the most appropriate dose to further investigate in the rest of the trial. However, we shall see in Section 4 that under different assumptions the optimal dose may be defined differently.

A (Bandit) Model for MTD Identification
A MTD identification algorithm proceeds sequentially: at round t a dose D t ∈ {1, . . . , K} is selected and administered to a patient for whom a toxicity response is observed. A binary outcome X t is revealed where X t = 1 indicates that a harmful side-effect occurred and X t = 0 indicates than no harmful side-effect occurred. We assume that X t is drawn from a Bernoulli distribution with mean p Dt and is independent from previous observations. The selection rule for choosing the next dose level to be administered is sequential in that it uses the past toxicity observations to determine the dose to administer to the next patient. More formally, D t is F t−1 -measurable where F t = σ(U 0 , D 1 , X 1 , U 1 , . . . , D t , X t , U t ) is the σ-field generated by the observations made with the first t patients and the possible exogenous randomness used in each round t, U t−1 ∼ U([0, 1]). Along with this selection rule, a (F t -measurable) recommendation rulek t indicates which dose would be recommended as the MTD, if the experiments were to be stopped after t patients.
Usually in clinical trials the total number of patients n is fixed in advance and the first objective is to ensure that the dosek n recommended at the end of the trial is close to the MTD, k * , but there is also an incentive to treat as many patients as possible with the MTD during the trial. Letting N k (t) = t s=1 1 (Ds=k) be the number of time dose k has been given to one of the first t patients, this second objective can be formalized as that of minimizing N k (n) for k = k * . In the clinical trial literature, empirical evaluations of dose-finding designs usually report both the empirical distribution of the recommendation strategyk n (that should be concentrated on the MTD) and estimates of E[N k (n)]/n for all doses k to assess the quality of the selection strategy in terms of allocating MTD as often as possible.
The sequential interaction protocol described above is reminiscent of a stochastic multi-armed bandit (MAB) problem (see Lattimore and Szepesvari (2018) for a recent survey). A MAB model refers to a situation in which an agent sequentially chooses arms (here doses) and gets to observe a realization of an underlying probability distribution (here a Bernoulli distribution with mean being the probability that the chosen dose is toxic). Different objectives have been considered in the bandit literature, but most of them are related to learning the arm with largest mean, whereas in the context of clinical trials we are rather concerned with the arm which is the closest to some threshold.

Thompson Sampling for MTD Identification
Early works on bandit models (Robbins, 1952;Lai and Robbins, 1985) mostly consider a reward maximization objective: The samples (X t ) are viewed as rewards, and the goal is to maximize the sum of these rewards, which boils down to choosing the arm with largest mean as often as possible. This problem was originally introduced in the 1930s in the context of phase III clinical trials (Thompson, 1933). In this context, each arm models the response to a particular treatment, and maximizing rewards amounts to giving the treatment with largest probability of success to as many patients as possible. This suggests a phase III trial is designed for treating as many patients as possible with the best treatment rather than identifying it. The trade-off between treatment and identification is also relevant for MTD identification: besides finding the MTD another objective is to treat as many patients as possible with it during the trial.
Reward maximization in a Bernoulli bandit model is a well-studied problem (Jacko, 2019). In particular, it is known since (Lai and Robbins, 1985) that any algorithm that performs well on every bandit instance should select each sub-optimal arm k more than C k log(n) times, where C k is some constant, in a regime of large values of n. Algorithms with finite-time upper bounds on the number of sub-optimal selections have been exhibited (Auer et al., 2002;Audibert et al., 2009), some of which match the aforementioned lower bound on the number of sub-optimal selections (Cappé et al., 2013). In the context of MTD identification, we are also concerned about minimizing the number of sub-optimal selections but with a different notion of optimal arm: the MTD instead of the arm with largest mean.
Algorithms for maximizing rewards in a bandit model mostly fall in two categories: frequentist algorithms, based on upper-confidence bounds (UCB) for the unknown means of the arms (popularized by Katehakis and Robbins (1995); Auer et al. (2002)) and Bayesian algorithms, that exploit a posterior distribution on the means (see, e.g. Powell and Ryzhov (2012); Kaufmann et al. (2012a)). Among those, Thompson Sampling (TS) is a popular approach, known for its practical successes beyond simple bandit problems (Agrawal and Goyal, 2013b;Agrawal and Jia, 2017). In the context of clinical trials, variants of Thompson Sampling have been notably studied for phase III clinical trials involving two treatments (see Thall and Wathen (2007) and references therein), or for adaptive trials involving interim analyses (Satlin et al., 2016). Strong theoretical properties have also been established for this algorithm in simple models. In particular, Thompson Sampling was proved to be asymptotically optimal for Bernoulli bandit models (Kaufmann et al., 2012b;Agrawal and Goyal, 2013a).
Thompson Sampling, also known as probability matching, implements the following simple Bayesian heuristic. Given a prior distribution over the arms, at each round an arm is selected at random according to its posterior probability of being optimal. In this paper, we advocate the use of Thompson Sampling for dosefinding, using the appropriate notion of optimality. In particular, Thompson Sampling for MTD identification consists of selecting a dose at random according to its posterior probability of being the MTD. Given a prior distribution Π 0 on the vector of toxicity probabilities, p = (p 1 , . . . , p K ) ∈ [0, 1] K , a posterior distribution Π t can be computed by taking into account the first t observations. A possible implementation of Thompson Sampling consists of drawing a sample θ(t) = (θ 1 (t), . . . , θ K (t)) from the posterior distribution Π t and selecting at round t + 1 the dose that is the MTD in the sampled model: D t+1 = argmin k |θ k (t) − θ|. There are several possible choices for the recommendation rulek t , which are discussed in the upcoming sections.

Why Thompson Sampling?
Thompson Sampling is by far not the only existing bandit algorithm, yet other algorithms may not be as easily adaptable to the MTD identification problem, which justifies our focus on this algorithm.
Indeed, Thompson Sampling only requires defining some notion of optimal arm (or arm to discover), which is naturally defined as the arm with mean closest to the threshold θ in the MTD identification problem. Many other popular bandit algorithms instead require a value to be assigned to each sampled arm, and require the optimal arm to be the arm with largest expected value. This is the case for the frequentist optimistic (UCB) algorithms (see, e.g., Auer et al. (2002); Cappé et al. (2013)), which construct confidence intervals on the expected value of each arm and select the arm which has the largest statistically plausible expected value (i.e. the largest Upper Confidence Bound). Adapting this optimism in face of uncertainty principle for MTD identification is not straightforward: one can certainly build confidence intervals on the toxicity probability of each dose (several of them may contain the MTD), but there is no natural way to define a "best plausible value" for each dose in that case.
In the literature on Bayesian ranking and selection, value-based approaches have also been proposed. Some algorithms are indeed based on defining some Expected Value of Information (Chick, 2006). Among those, knowledge gradient methods (Powell and Ryzhov, 2012) are particularly interesting since they permit handling correlations between arms. For example Xie et al. (2016) consider a prior distribution over the arms' means which is a multivariate Gaussian, and Wang et al. (2016) consider a Bayesian logistic model (where a Laplace approximation is used for Bayesian inference). However, the proposed algorithms are both tailored to finding an arm a maximizing E[V (a, D)] for some function V that depends on a random variable D under which the expectation is taken (like other algorithms from the Bayesian Optimization (BO) literature (Brochu et al., 2010)). The MTD identification problem cannot naturally be cast in this framework, and adapting, e.g., knowledge gradient methods would require defining an appropriate notion of value of information in this setting. This is why we focused on a Bayesian approach which is easier to adapt to MTD identification, Thompson Sampling.

Independent Thompson Sampling: an Asymptotically Optimal Algorithm
Inspired by the bandit literature, we introduce the simplest version of Thompson Sampling, that assumes independent uniform prior distributions on the probability of toxicity of each dose. We refer to this algorithm as Independent Thompson Sampling and propose some theoretical guarantees for it.

Algorithm Description
The prior distribution on p = (p 1 , . . . , is a uniform distribution. Letting π t k be the posterior distribution of p k given the observations from the first t patients, the posterior distribution also has a product form, is the sum of rewards obtained from arm k and D s is the dose allocated at time s.
The selection rule of Independent Thompson Sampling is simple: a sample from the posterior distribution on the toxicity probability of each dose is generated, and the dose for which the sample is closest to the threshold is selected: Several recommendation rules may be used for Independent Thompson Sampling. As the randomization induces some exploration, recommendingk t = D t+1 is not a good idea. Inspired by what is proposed by Bubeck et al. (2011) for assigning a recommendation rule to rewards maximizing algorithms, a first idea is to recommendk t = argmin k |μ k (t) − θ|, whereμ k (t) is the empirical mean of dose k after the t-th patient of the study. Leveraging the fact that TS is supposed to allocate the MTD most of the time, we could also select k t = argmax k N k (t) or pickk t uniformly at random among the allocated doses.

Upper Bound on the Number of Sub-Optimal Selections
For the classical rewards maximization problem, the first finite-time analysis of Thompson Sampling for Bernoulli bandits dates back to Agrawal and Goyal (2012) and was further improved by Kaufmann et al. (2012b); Agrawal and Goyal (2013a). In Appendix A, building on the analysis of Agrawal and Goyal (2013a), we prove the following for Thompson Sampling applied to MTD identification.
Theorem 1. Introducing for every k = k * the quantity Independent Thompson Sampling satisfies the following. For all ε > 0, there exists a constant C ε,θ,p (depending on ε, the threshold θ and the toxicity probabilities) such that for all k : Theorem 1 shows that the total number of allocations to a sub-optimal dose in a trial involving n patients is logarithmic in n, which justifies that the MTD is given most of the time, at least in a regime of large values of n (as the second order term can be large). Also, this bounds tells us that in this regime each sub-optimal dose is allocated in inverse proportion of kl(p k , d * k ), which can be seen as a distance between dose k and an optimal dose with toxicity probability d * k which is illustrated in Figure 1. The lower bound given in Theorem 2 below furthermore shows that Independent Thompson Sampling actually achieves the minimal number of sub-optimal allocations when n grows large.
, which is symmetric to the MTD with respect to threshold θ.
Theorem 2. We define a uniformly efficient design as a design satisfying for all possible toxicity probabilities p, for all α ∈]0, 1[, for all k : |θ − p k | = |θ − p k * |, E[N k (n)] = o(n α ) when n goes to infinity. If p k * = θ, any uniformly efficient design satisfies, for all k: .
Theorem 2 can be viewed as a counterpart of the Lai and Robbins lower bound for classical bandits (Lai and Robbins, 1985) and can be easily derived using recent change-of-measure tools (see Garivier et al. (2019b)). Its proof is given in Appendix B for the sake of completeness.

Upper Bound on the Error Probability
If the recommendation rulek n consists of selecting uniformly at random a dose among the doses that were allocated during the trial, {D 1 , . . . , D n }, it follows from Theorem 1 that where D is a (possibly large) problem-dependent constant. Hence finite-time upper bounds on the number of sub-optimal selection lead to non-asymptotic upper bound on the error probability of the design. Note that for the state-of-the-art dose-finding designs it is not known whether such results can be obtained; the only results available provide conditions for consistency. For example Shen and O'Quigley (1996); Cheung and Chappell (2002) exhibit some conditions on the toxicity probabilities under which a classical design called the CRM is such thatk n converges almost surely to k * . This being said, the upper bound (1) is not very informative, as a very large number of patients is needed for the upper bound to be at least smaller than 1, and one could expect to have an upper bound that is exponentially decreasing with n. As we shall see in Section 6, an adaptation of a best arm identification algorithm (Karnin et al., 2013) leads to such an upper bound, but may be less desirable for clinical trials from an ethical point of view. This is why we rather chose to investigate in what follows several variants of Thompson Sampling coupled with an appropriate recommendation rule.
By using uniform and independent priors on each toxicity probability, Independent Thompson Sampling is the simplest possible implementation of Thompson Sampling. We now explain that using a more sophisticated prior distribution allows the algorithm to leverage some particular constraints of the dose-finding problem, like increasing toxicities or a plateau of efficacy.

Exploiting Monotonicity Constraints with Thompson Sampling
Independent Thompson Sampling is an adaptation of a state-of-the-art bandit algorithm for identifying the MTD that does not leverage any prior knowledge on (e.g.) the ordering of the arms' means. While it can be argued that when testing drug combinations no natural ordering between the doses exists (see, e.g., Mozgunov and Jaki (2017)), in most cases monotonicity assumptions can speed up learning.
A typical assumption in phase I studies is that both efficacy and toxicity are increasing with the dose. We show in Section 4.1 that Thompson Sampling using an appropriate prior is competitive with state-of-the-art phase I approaches leveraging the monotonicity. In Section 4.2, we further show that Thompson Sampling is a flexible method that can be useful in phase I/II trials, under more complex monotonicity assumptions on both toxicity an efficacy. More specifically, we show it can handle an efficacy "plateau," where efficacy may be non-increasing after a certain dose level.

Thompson Sampling for Increasing Toxicities: A Phase I Design
In a phase I study in which both toxicity and efficacy are increasing with the dose, the MTD is the most relevant dose to allocate in further stages. We now focus on algorithms leveraging the extra information that p 1 ≤ · · · ≤ p k . To exploit this structure, escalation procedures have been developed in the literature, the most famous being the "3+3" design (Storer, 1989). In this design, adjusted for θ = 0.33, the lowest dose is first given to 3 patients. If no patient experiences toxic effects, one escalates to the next dose and repeats the process. If one patient experiences toxicity, the dose is given to 3 more patients, and if less than two patients among the 6 experience toxicity, one escalates to the next dose. Otherwise the trial is stopped, which is also the case if from the beginning 2 out of the 3 patients experience a toxic effect. Upon stopping, the previous dose is recommended as the MTD, or all doses are deemed too toxic if one stops at the first dose level. Although it is clear that the guarantees in terms of error probability (or sub-optimal selections) are very weak, "3+3" is still often used in practice.
Alternative to this first design are variants of the Continuous Reassessment Method (CRM), proposed by O'Quigley et al. (1990). The CRM uses a Bayesian model that combines a parametric dose/toxicity relationship with a prior on the model parameters. Under this model, CRM appears as a greedy strategy that selects in each round the dose whose expected toxicity under the posterior distribution is closest to the threshold. We propose in this section several variants of Thompson Sampling based on the same Bayesian model, but that favor (slightly) more exploration.
A Bayesian model for increasing toxicities In the CRM literature, several parametric models that yield an increasing toxicity have been considered. In this paper, we choose a two-parameter logistic model that is among the most popular. Under this model, each dose k is assigned an effective dose u k (that is usually not related to a true dose expressed in a mass or volume unit) and the toxicity probability of dose k is given by A typical choice of prior is β 0 ∼ N (0, 100) and β 1 ∼ Exp(1).
It is worth noting that this model also heavily relies on the distinct effective dose levels u 1 , . . . , u K that are usually chosen depending on some prior toxicities set by physicians, p 0 1 ≤ p 0 2 ≤ · · · ≤ p 0 K . Letting β 0 , β 1 be the prior mean of each parameter, the effective doses are calibrated such that for all k, ψ(k, β 0 , β 1 ) = p 0 k . If there is no medical prior knowledge about the toxicity probabilities, some heuristics for choosing them in a robust way have been developed (see Chapter 9 of Cheung (2011)). Under this model, given some observations from the different doses one can compute the posterior distribution over the parameters β 0 and β 1 ; that is, the conditional distribution of these parameters given the observations. Although there is no closed form for these posterior distributions, they can be easily sampled from using Hamiltonian Monte-Carlo Markov Chain algorithms (HMC) as the log-likelihood under these models is differentiable. In practice, we use the Stan implementation of these Monte-Carlo sampler (Stan Development Team, 2015), and use (many) samples to approximate integrals under the posterior when needed.

Thompson Sampling
Thompson Sampling selects a dose at random according to its posterior probability of being the MTD. Under the two-parameter Bayesian logistic model presented above, letting π t denote the posterior distribution on (β 0 , β 1 ) after the first t observations, the posterior probability that dose k is the MTD is A first possible implementation of Thompson Sampling that we use in our experiments consists of computing approximationsq k (t) of the probabilities q k (t) (using posterior samples) and selecting at round t + 1 a dose D t+1 ∼q(t), i.e. such that P (D t+1 = k|F t ) =q k (t). A second implementation of Thompson Sampling (that may be computationally easier) consists of drawing one sample from the posterior distribution of (β 0 , β 1 ), and selecting the MTD in the sampled model: It is easy to see that this algorithm coincides with Thompson Sampling in that P D TS t+1 = k|F t = q k (t). We will present below a variant of Thompson Sampling based on the first implementation (TS A) and a variant based on the second implementation (TS(ε)).
Recommendation rule Due to the randomization, Thompson Sampling performs more exploration than the "greedy" CRM (O'Quigley et al., 1990) method, which selects at time t the MTD under the model parameterized by (β 0 ,β 1 ), the posterior means of the two parameters, given bŷ More precisely, the sampling rule of the CRM is The recommendation rule for CRM after t patients is identical to the next dose that would be sampled under this design, that isk CRM t = D CRM t+1 . For Thompson Sampling, due to the more exploratory nature of the algorithm, we do not want to recommendk TS t = D TS t+1 . Instead, we propose the use of recommendation rulê k TS t = argmin k∈{1,...,K} |θ − p k (β 0 (t),β 1 (t))|, which coincides with that of the CRM.

Two variants of Thompson Sampling
The randomized aspect of Thompson Sampling makes it likely to sample from large or small doses, without respecting some ethical constraints of phase I clinical trials. Indeed, patients should not be exposed to toohigh dose levels; overdosing should be controlled. Hence, we also propose two "regularized" versions of TS. The first depends on a parameter ε > 0 set by the user that ensures that the expected toxicity of the recommended dose remains within ε of the toxicity of the empirical MTD. The second restricts the doses to be tested to a set of admissible doses. These algorithms are formally defined below, and their performance is evaluated in Section 5.

TS(ε)
We first compute the posterior meansβ 0 (t),β 1 (t) from (3) and the toxicity of the dose closest to θ under the model parameterized by (β 0 (t),β 1 (t)) (i.e., the toxicity of the dose selected by the CRM): Next we sampleβ 0 (t),β 1 (t) from the posterior distribution π t and select a candidate dose level D t+1 using (2). If the predicted toxicity level p D t+1 (β 0 (t),β 1 (t)) is not in the interval (p(t) − ε,p(t) + ε), then we reject our values ofβ 0 (t),β 1 (t), draw a new sample from π t and repeat the process. In order to guarantee that the algorithm terminates, we only reject up to 50 samples, after which we use the sample that gives the dose with minimum toxicity among all 50 samples. We choose 50 to limit the computational complexity of the algorithm, but it can also be replaced by a larger value if more computational power is available. TS(ε) can be seen as a smooth interpolation between the CRM (which correspond to ε = 0) and vanilla Thompson Sampling (which corresponds to ε = 1). Regarding the tuning of the parameter ε, large values do not reduce much the amount of exploration while too small values lead to a behavior which is indistinguishable from that of the CRM. We did (large scale) experiments with ε ∈ {0.02, 0.05, 0.1} and we found that the three values lead to comparable performance across the different scenarios we tried. To ease the presentation, we report results for TS(0.05) only in Section 5.
TS A The TS A algorithm limits exploration by enforcing the selected dose to be in some admissible set A t , by sampling from the modified distribution instead of sampling directly fromq(t) as vanilla Thompson Sampling does. The admissible set A t is defined as set of doses that meet the following two criteria: 1. dose k has either already been tested, or is the next-smallest dose which has not yet been tested 2. the posterior probability that the toxicity of dose k exceeds the toxicity of the dose closest to θ is smaller than some threshold: A t is inspired by the admissible set of Riviere et al. (2017) described in detail in the next section.
In our experiments, we tried different values of the parameter c 1 and we found that the performance of TS A is better with values of c 1 that are not too small. In Section 5, we report experiments with c 1 = 0.8, but the performance was comparable for the choices c 1 = 0.6 or 0.9.

Thompson Sampling for Efficacy Plateau Models: A Phase I/II Design
In some particular trials, it has been established that efficacy is not always increasing with the dose. Motivated by some concrete examples discussed in their paper, Riviere et al. (2017) consider a model in which the dose effectiveness can plateau after some unknown level, while toxicity still increases with dose level. In these models, MTD identification is no longer relevant and the objective is rather to identify the smallest dose with maximal efficacy and with toxicity no more than θ. More formally, introducing eff k the efficacy probability of dose k, the Minimal Effective Dose (MED) is In a dose-finding study involving efficacy, at each time step t a dose D t is allocated to the t-th patient, and the toxicity X t is observed, as well as the efficacy Y t . With this two-dimensional observation, assigning a value (or reward) to each sampled arm is even less natural than before. However as one can still define a notion of optimal dose (the MED instead of the MTD), Thompson Sampling can still be applied in this setting. As we shall see, it bears some similarities to the state-of-the-art method developed by Riviere et al. (2017).
A Bayesian model for toxicity and efficacy Thompson Sampling requires a Bayesian model for both the dose/toxicity and the dose/efficacy relationship that enforces an increasing toxicity and a increasing then plateau efficacy. We use the model proposed by Riviere et al. (2017), that we now describe.
Under this model, toxicity and efficacy are assumed to be independent. The (increasing) toxicity follows the two-dimensional Bayesian logistic model with effective doses u k : Efficacy also follows a logistic model, with an additional parameter τ that indicates the beginning of the plateau of efficacy. The efficacy probability of dose level k is with v k the effective efficacy of dose k. Given (t 1 , . . . , t K ) such that K i=1 t i = 1, a probability distribution on {1, . . . , K}, the three parameters (γ 0 , γ 1 , τ ) are independent and drawn from the following prior distribution: The prior on τ may be provided by a physician or set to (1/K, . . . , 1/K) in case one has no prior information. Just like the effective doses u k (that we may now call effective toxicities), the effective efficacies v k are calculated using prior efficacies eff 0 where γ 0 = 0 and γ 1 = 1 are the prior means of the parameters γ 0 and γ 1 .
be the efficacy data gathered in the first t rounds. Generating samples from the posterior distribution of (γ 0 , γ 1 , τ ) given D eff t is a bit more involved than generating posterior samples from (β 0 , β 1 ). Indeed, it cannot be handled directly with HMC given that (γ 0 , γ 1 ) are continuous and τ is discrete. Thus, we proceed in the following way: we first draw samples from p(γ 0 , γ 1 |D eff t ), which can be performed with HMC (and requires marginalizing out the discrete parameter τ , following the example of change point models given in the Stan manual (Stan Development Team , 2015)). Then we sample τ conditionally to γ 0 , γ 1 , D eff t .

Thompson Sampling
Recall that the principle of Thompson Sampling is to randomly select doses according to their posterior probability of being optimal. This idea can also be applied in this more complex model, using the corresponding definition of optimality. Given a vector ψ = (ψ 1 , . . . , ψ K ) of increasing toxicity probabilities and a vector φ = (φ 1 , . . . , φ K ) of increasing then plateau efficacy probabilities, the optimal dose is MED(ψ, φ) := min k : φ k = max :ψ ≤θ φ .
The posterior probability of dose k to be optimal in that case is q k (t) := P ( k = MED (ψ(·, β 0 , β 1 ), φ(·, γ 0 , γ 1 , τ ))| F t ) and in our experiments, we implement Thompson Sampling by computing approximationsq k (t) from the quantities q k (t) (based on posterior samples) and then selecting a dose D t+1 ∼q(t) whereq(t) = (q 1 (t), . . . ,q K (t)). Just like in the previous model, an alternative implementation of Thompson Sampling would sample parameters from their posterior distributions and select the optimal dose in this sampled model. Letting be samples from the posterior distributions after t observations of the toxicity and efficacy parameters respectively, one can computeψ k (t) = ψ(k,β 0 (t),β 1 (t)) andφ k (t) = φ(k,γ 0 (t),γ 1 (t),τ (t)) for every dose k.

A Variant of Thompson Sampling using Adaptive Randomization
Interestingly, the need for randomization in the context of plateau efficacy has already been observed by Riviere et al. (2017). More precisely, as we explain below, the algorithm MTA-RA described in that work can be viewed as an hybrid approach between Thompson Sampling and a CRM approach.
Additionally to the use of adaptive randomization, the MTA-RA algorithm also introduces a notion of admissible set. The set of admissible doses after t patients, denoted by A t , is the set of dose levels k meeting all of the following criteria: 1. dose k has either already been tested, or is the next-smallest dose which has not yet been tested 2. the posterior probability that the toxicity of dose k exceeds θ is smaller than some threshold: 3. if the dose has been tested more than 3 times, the posterior probability that the efficacy is larger than ξ is larger than some threshold: Practical computation of the admissible set can be performed using posterior samples from (β 0 , β 1 ) to check the criterion (4) and posterior samples from (γ 0 , γ 1 , τ ) to check the criterion (5).
The MTA-RA algorithm works in two steps. The first step exploits the posterior distribution of the breakpoint, t k (t) := P τ = k|D eff t , and uses randomization to pick a valueτ (t) close to the mode of this distribution. More precisely, given (t k (t)) k=1,...,K an estimate of the posterior distribution of τ , let .
The threshold s 1 is often adapted such that it is larger in the beginning of the trial when we have high uncertainty about the estimates, but it grows smaller as the trial continues. The second step of MTA-RA doesn't employ randomization. Based on posterior samples from (γ 0 , γ 1 ) conditionally to τ being equal tô τ (t), efficacy estimatesφ k are produced (taking the mean of the values of φ(k,γ 0 ,γ 1 ,τ (t)) for many samples γ 0 ,γ 1 ) and finally the selected dose is Ifτ (t) were replaced by a point estimate (e.g. the mode of the breakpoint posterior distributiont(t)), MTA-RA would be close to a CRM approach that computes estimates of all the parameters and acts greedily with respect to those estimated parameters (with the additional constraint that the chosen dose has to remain in the admissible set). However, the first step of MTA-RA bears similarities with the first step of a Thompson Sampling implementation that would sample a parameter τ from thet(t) (and later sample the other parameters conditionally to that value and act greedily in the sampled model). The difference is the use of adaptive randomization, in which the sample is not exactly drawn fromt(t), but is constrained to fall in some set (here R t ) that depends on previous observations.
The TS A algorithm We believe that using adaptive randomization is a good idea to control the amount of exploration performed by Thompson Sampling, which leads us to propose the TS A algorithm, that incorporates the constraint to select a dose that belongs to the admissible set A t . More formally, TS A selects a dose at random according to where we recall thatq k (t) is an estimate of the posterior probability that dose k is optimal. Compared to the variant of TS A for increasing toxicities that is proposed in Section 4.1, the difference here is the appropriate definition of the admissible set, that involves both toxicity and efficacy probabilities.
Practical remark Approximationst k (t) of the breakpoint distribution can be computed using that where L(D eff t |γ 0 , γ 1 , s) is the likelihood of the efficacy observations when the efficacy model parameters are (γ 0 , γ 1 , s) and p(γ 0 , γ 1 |D eff t ) is the density of the distribution of (γ 0 , γ 1 ) given the observations.t k (t) can be thus be obtained by Monte-Carlo estimation based on samples from p(γ 0 , γ 1 |D eff t ).

Experimental Evaluation
We now present an empirical evaluation of the variants of Thompson Sampling introduced in the paper first in the context of increasing efficacy and then with the presence of a plateau of efficacy. In both groups of experiments, we adjusted our designs to some common practices in dose-finding trials. We used a start-up phase for all designs (starting from the smallest dose and escalating until the first toxicity is observed) and we also used cohorts of patients of size 3. This means that the same dose is allocated to 3 patients at a time and the model is updated after seeing the outcome for these 3 patients.

Phase I: MTD Identification
In this set of experiments, we evaluate the performance of the three algorithms introduced in Section 4.1, TS, TS(ε) and TS A, and compare them to the 3+3 and CRM baselines. We report experiments with the value ε = 0.05 for TS(ε) and c 1 = 0.8 for TS A. We refer the reader to Section 4.1.2 for discussions on the choice of these parameters. We also include Independent TS as proposed in Section 2, which is agnostic to the increasing structure.
In Tables 1 to 3 we provide results  We choose the same prior toxicities for all scenario, that are sometimes close to actual toxicities (e.g. in Scenario 2) and sometimes quite far, in order to showcase the robustness of Bayesian algorithms.
For each scenario and algorithm, we report in the first column of these tables the percentage of allocation to each dose, that is, an estimate of P(k n = k) for each dose k, based on N = 2000 repetitions. In the second column, we report an estimate of the percentage of allocation to each dose during the trial, computed for each dose k as the average value of 100 * N k (n)/n over N = 2000 repetitions. We add in parenthesis the empirical standard deviation of these allocation percentages, as allocations under bandit algorithms are known to have a large variance. For the 3+3 design, only the recommendation percentages are displayed, as the percentage of allocations would be computed based on a number of patients smaller than 36 (as a 3+3 based trial involves some random stopping). This design is also the only one that would stop and recommend none of the doses if they are all judged too toxic: we add this fraction of no recommendation between brackets in the tables.
For each scenario, corresponding to different increasing toxicity probabilities, the MTD is underlined and we mark in bold the fraction of recommendation or allocation of the MTD that are superior to what is achieved by the CRM. We now comment on the performance of the algorithms on those scenarios.
Dose recommendation TS outperforms CRM 3 out of 9 times, TS(ε) does so 5 out of 9 times, and TS A does so 5 out of 9 times. As expected, Independent TS, which does not leverage the increasing structure, does not have a remarkable performance. This algorithm would need a larger budget to have a good empirical performance. With n = 36 in most cases this strategy is not doing much better than selecting the doses uniformly at random. One can also observe that the 3+3 design (that may however require less than 36 patients in the trial) performs very badly in terms of dose recommendation.
Dose allocation While TS A and TS(ε) do not always have higher allocation percentage at the optimal (underlined) dose compared to CRM, a scan of the dose allocation results in Tables 1 to 3 shows that the addition of the admissible set A and ε regularity to the Thompson Sampling method consistently reduces the allocation percentage of higher toxicity doses. TS A performs best in this regard (it is more cautious with allocating higher doses) across all algorithms (e.g. it consistently has superior performance compared to CRM), while TS(ε) has performance better than or comparable to CRM. We believe this result is of interest in trials where toxicity is an ethical concern.

Phase I/II: MED Identification when Efficacy Plateaus
In this set of experiments, we evaluate the performance of the two algorithms introduced in Section 4.2, TS and TS A, and compare them to the MTA-RA algorithm. We use the experimental setup of Riviere et al. In Tables 4 to 6 we provide results for several scenarios with increasing toxicities and efficacy, with efficacy which (quasi) plateaus. We report the percentage of allocation to each dose, the percentage of recommendation of each dose when n = 60, and the percentage of time the trials stopped early (E-Stop), estimated over N = 2000 repetitions. As before, we also report standard deviations for the percentage of allocations to each dose.
Optimal doses are underlined by a plain line while a dashed line identifies doses whose toxicity is larger than θ. We mark in bold cases where our algorithms makes the optimal decision (in terms of the percentage of recommendations) more often than the MTA-RA baseline.
Dose recommendation Recall that the modeling assumption here is that efficacy increases monotonically in toxicity up to a point and then it plateaus. We present experimental results on several scenarios, some of which are borrowed from Riviere et al. (2017), on which this plateau assumption is not always exactly met. In most of these scenarios, TS A outperforms the MTA-RA algorithm.
In scenarios 1 through 4 and in scenarios 12 and 13, there is a plateau of efficacy starting at a reasonable toxicity: in this case the optimal dose corresponds to the plateau breakpoint. Our algorithms make the optimal decision compared to MTA-RA consistently: TS 4 out of 6 times and TS A 5 out of 6 times. In scenarios 5 and 6 the plateau of efficacy starts when the toxicity is already too high, hence the optimal dose is before than the plateau. In scenario 5, TS A and TS both outperform MTA-RA, while on scenario 6 MTA-RA has a slight advantage over TS.
In scenario 7 and 8 there is no true plateau of efficacy, however in both cases there exists a "breakpoint" (underlined) after which the efficacy is increasing very slowly while the toxicity is increasing significantly. This breakpoint can thus be argued to be a good trade-off between efficacy and toxicity and should be investigated in further phases. In these two scenarios TS A identifies this pseudo-optimal dose more often than MTA-RA, while TS has a slightly worse performance.
Lastly, we study the case when there is no clear optimal or near-optimal dose, i.e. scenarios 9-11. In scenario 9 wherein most doses, including the entire quasi-plateau, are too toxic, we would like to stop early or at most recommend dose 1 (the only dose meeting the toxicity constraint but whose efficacy is not very high). Under this interpretation, TS and TS A outperform MTA-RA. Note that our algorithms most often either stop early or recommend dose 1, while in comparison MTA-RA recommends the toxic dose 2 a large fraction of the time (33.1 %). In scenarios 10 and 11 in which all doses are either too toxic or ineffective a good algorithm would stop early with no recommendation. TS A makes this optimal decision more often than MTA-RA in both scenarios and TS in one of the two scenarios.
Dose allocation While TS and TS A have lower allocation percentage at the optimal (underlined) dose compared to MTA-RA, the addition of the admissible set A to the Thompson Sampling method consistently reduces the percentage of dose allocation at doses that are too toxic. Furthermore, TS A is more cautious in allocating higher doses compared to MTA-RA. Our experiments notably reveal that the fraction of allocation to doses whose toxicity is larger than θ (that are underlined with a dashed line) is always smaller for TS A than for MTA-RA. Hence, not only is TS A very good in terms of recommending the right dose, it also manages to avoid too-toxic doses more consistently.

Revisiting the Treatment versus Experimentation Trade-off
Ideally, a good design for MTD identification should be supported by a control of both the error probability e n = P(k n = k * ) and the number of sub-optimal selections E[N k (n)] for k = k * . These two quantities           are respectively useful to check whether the design achieves a good identification of the optimal dose and whether a large number of patients have been treated with the optimal dose. For classical bandits (in which k * is the arm with largest mean instead of the MTD), those two performance measures are known to be antagonistic. Indeed, Bubeck et al. (2011) shows that the smaller the regret (a quantity that can be related to the number of sub-optimal selections), the larger the error probability. Such a trade-off may also exist for the MTD identification problem. However, the precise statement of such a result would be meaningful for large values of the number of patients n, which is of little interest for a real clinical trial as it can only involve a small number of patients. In practice, we showed that adaptations of Thompson Sampling, a bandit design aimed at maximizing rewards, achieve good performance in terms of both allocation and recommendation.
Still, another natural avenue of research is to investigate the adaptation of bandit designs aimed at minimizing the error probability. Minimizing the error probability for MTD can be viewed as a variant of the fixed-budget Best Arm Identification (BAI) problem introduced by Audibert et al. (2010); Bubeck et al. (2011). In contrast to the standard BAI problem that aims to identify the arm with largest mean (which would correspond here to the most toxic dose), the focus is on identifying the arm whose mean is closest to the threshold θ. A state-of-the art fixed-budget BAI algorithm is Sequential Halving (Karnin et al., 2013), and we propose in Algorithm 6 a natural adaptation to MTD identification.
Sequential Halving for MTD identification proceeds in phases. In each of the log 2 (K) phases, all the remaining doses are allocated the same amount of times to patients and their empirical toxicity based on these allocations (that is, the average of the toxicity responses) is computed. At the end of each phase the empirical worst half of the doses is eliminated. For MTD identification, rather than the doses with the smallest empirical means (as the vanilla Sequential Halving algorithm would do), the doses whose empirical toxicity are the furthest away from the threshold θ are eliminated. Observe that by design of the algorithm, the total number of allocated doses is indeed smaller than the prescribed budget n.

Algorithm 1 Sequential Halving for MTD Identification
Input: budget n, target toxicity θ Initialization: Set of dose levels S 0 ← {1, . . . , K}; for r ← 0 to log 2 (K) − 1 do Allocate each dose k ∈ S r to t r = n |Sr| log 2 (K) patients; Based on their response computep r k , the empirical toxicity of dose k based on these t r samples; Compute S r+1 the set of |S r |/2 arms with smallestd r k := |θ −p r k | Output: the unique arm in S log 2 (K) Building on the analysis of Karnin et al. (2013), one can establish the following upper bound on the error probability of Sequential Halving for MTD identification. The proof can be found in Appendix C.
Theorem 3. The error probability of the SH algorithm is upper bounded as A consequence of Theorem 3 is that in a trial involving more than n = 8H 2 (p) log 2 K log (9 log 2 (K)/δ) patients, Sequential Halving is guaranteed to identify the MTD with probability larger than 1 − δ. However, this number is typically much larger than the number of patients involved in a clinical trial. Indeed the complexity term H 2 (p) may be quite large, when some doses have a distance to the threshold θ which is very close to the smallest distance |p k * − θ|.
An important shortcoming of Sequential Halving is that due to the uniform exploration within each phase each dose is selected at least n/(K log 2 (K)) times, even the largest, possibly harmful ones. This is highly unethical in a clinical trial without prior knowledge that too-toxic (or too ineffective) doses have already been eliminated. This problem of allocating too extreme doses is likely to be shared by adaptations of any other BAI algorithm, that are expected to select all the arms a linear number of times. For example the APT algorithm proposed by Locatelli et al. (2016) to identify all arms with mean above a threshold θ using a fixed budget n also selects all arms a linear number of times.
To overcome this problem, an interesting avenue of research would be to try to incorporate monotonicity assumptions in BAI algorithms. Garivier et al. (2019a) recently proposed such an algorithm, in the fixed confidence setting: given a risk parameter δ, the goal is to identify a dosek τ such that P(k τ = k * ) ≤ δ, using as few samples τ as possible. Their analysis identifies a minimal sample complexity E[τ ] that guarantees a δ-correct identification for any increasing toxicities, which can be obtained under an optimal allocation w * (where w * k indicates the fraction of time dose k is allocated). Interestingly, this optimal allocation is supported only on the neighboring doses of the MTD. The fixed-confidence setting requires allowing for random stopping rules τ , i.e. for a dose-finding trial based on an adaptively chosen number of patients. This is not always possible in practice, and it would be interesting to investigate optimal allocations in a fixedbudget setting as well. Yet optimality in the fixed-budget setting is a notoriously hard question already for classical bandits .

Conclusion
Motivated by the literature on multi-armed bandit models, we advocated the use of the powerful Thompson Sampling principle for dose-finding studies. This Bayesian randomized algorithm can be used in different contexts as it can leverage different prior information about the doses. For increasing toxicities and increasing or plateau efficacies, we proposed variants of Thompson Sampling, notably the TS A algorithm that often outperforms our baselines in terms of recommendation of the optimal dose, while significantly reducing the allocation to doses with high toxicity.
We provided theoretical guarantees for the simplest version of Thompson Sampling based on independent uniform priors on each dose toxicity, but advocated the use of more sophisticated priors for practical dosefinding studies. We believe that finding a practical design for which we can also establish non-trivial finitetime performance guarantees is a crucial research question.
Another interesting direction would be taking contextual information (e.g. a patient's medical history and other medications used) into account for a more "personalized" assessment of toxicity and efficacy of a drug. Bayesian methods also seem promising for such an objective, following the success of Thompson Sampling for contextual bandits. A Analysis of Independent Thompson Sampling: Proof of Theorem 1 Fix a sub-optimal arm k. Several cases need to be considered depending on the relative position of p k and p k * with respect to the threshold. All cases can be treated similarly and to fix the ideas, we consider the case p k * ≥ θ > p k , which is illustrated below. In that case d * Let x, y ∈]0, 1[ 2 be such that p k < x < y < d k * , that will be chosen later. Define y = 2θ − y > θ the symmetric of y with respect to the threshold (see the above illustration). We denote byμ k (t) the empirical mean of the toxicity responses gathered from dose k up to the end of round t and recall θ k (t) is the sample from the Beta posterior on p k after t rounds that is used in the Thompson Sampling algorithm. Inspired by the analysis of Agrawal and Goyal (2013a), we introduce the following two events, that are quite likely to happen when enough samples of arm k have been gathered: The expected number of allocations of dose k is then decomposed in the following way Terms (II) and (III) are easily controlled using some concentration inequalities and the so-called Beta-Binomial trick, that is the fact that the CDF of a Beta distribution with parameters a and b, F Beta a,b , is related to the CDF of a binomial distribution with parameter n, x, F B n,x , in the following way: Term (III) is very small as arm k is unlikely to be drawn often while its empirical mean falls above x > p k and term (II) grows logarithmically with T . More precisely, it can be shown using Lemma 3 and 4 in Agrawal and Goyal (2013a) that (II) ≤ log(T ) kl(x, y) + 1 and (III) ≤ 1 kl(x, y) + 1.
The tricky part of the analysis is to control term (I), that is to upper bound the number of selections of dose k when both the empirical mean and the Thompson sample for dose k fall close to the true mean p k . For this purpose, one can prove a counterpart of Lemma 1 in Agrawal and Goyal (2013a) that relates the probability of selecting dose k to that of selecting the MTD k * .
Lemma 4. Define p y (t) := P (θ k * (t) ∈ [y, y ]|F t ), where F s is the filtration generated by the observation up to the end of round s. Then Proof. The proof is inspired of that of Lemma 1 in Agrawal and Goyal (2013a). We introduce the event in which the Thompson sample for dose k is the closest to the threshold θ among all sub-optimal doses: On the one hand, one has On the other hand, it holds that Combining the two inequalities yields Lemma 4.
Using the same steps as Agrawal and Goyal (2013a) yields an upper bound on the first term: where τ j is the time instant at which dose k is selected for the j-th time. The expectation of 1/p y (τ j ) can be explicitly written n,x stands for the pdf of a Binomial distribution and X a,b denotes a random variable that has a Beta(a, b) distribution. The following lemma is crucial to finish the proof. This original result was specifically obtained for the MTD identification problem and is needed to control the probability that a Beta distributed random variable fall inside an interval, that is P (y ≤ X s+1,j−s+1 ≤ y ).
Putting things together, we proved that for every x and y satisfying p k < x < y < d k * , the number of selections of dose k is upper bounded as E[N k (T )] ≤ 1 kl(x, y) log(T ) + C x,y,θ,p for some constant that depends on the toxicity probabilities, the threshold θ and the choice of x and y. Now, picking x and y such that kl(x, y) = kl(p k ,d k * ) 1+ yield the result.
As the function in the left-hand side is non-increasing in s, a sufficient condition is that j satisfies kl y, y ≥ log(2(j + 2)) j + 1 , which is the case for j superior to some j 1 . Thus, for j ≥ j 1 , P y ≤ X s+1,j−s+1 ≤ y ≥ 1 2 P (S j+1,y ≤ s) = 1 2 P (X s+1,j−s+1 ≥ y) .
As the function in the left-hand side is non-decreasing in s, a sufficient condition is that j satisfies kl y , y ≥ log(2(j + 2)) j + 1 , which is the case for j superior to some j 4 . Thus, for j ≥ j 4 , P y ≤ X s+1,j−s+1 ≤ y ≥ 1 2 P S j+1,y ≥ s = 1 2 P X s+1,j−s+1 ≤ y .
Conclusion Letting j 0 = max(j 1 , j 2 , j 3 , j 4 ), for all j ≥ j 0 , for every s ∈ {0, . . . , j}, P y ≤ X s+1,j−s+1 ≤ y ≥ 1 2 min P (X s+1,j+s+1 ≥ y) ; P X s+1,j+s+1 ≤ y B Lower Bound on the Number of Allocation: Proof of Theorem 2 Fix a uniformly efficient algorithm and a vector of toxicity probabilities p. We denote by E p the expectation under the model parameterized by p when this algorithm is used. Letting p be another vector of probabilities, it follows from the change-of-distribution lemma of Garivier et al. (2019b) that for all random variable Z T ∈ Letting k * be a MTD in p, we fix k which is not a MTD (i.e. |p k − θ| > |p k * − θ|) and we prove that .
Recall that we assume p k * = θ. Then one can define the alternative model p in which for all = k, p = p and p k = d * k + if d * k < θ and p k = d * k − if d * k > θ, with small enough such that under p , dose k is the unique MTD (refer to Figure 1 for an illustration).
For this particular choice of alternative model p , (11) becomes (2) Choosing Z T = N k (T ) T , exploiting the fact that the algorithm is uniformly efficient we know that • lim T →∞ E p [Z T ] = 0 as k is a sub-optimal dose under p Letting α go to zero, we obtain lim inf T →∞ E p [N k (T )]kl(p k , d * k ± ) ln(T ) ≥ 1 and (12) follows by letting go to zero.