Learning when to stop

Guillaume Maillard

► To cite this version:

Guillaume Maillard. Learning when to stop. 2025. hal-05385959

HAL Id: hal-05385959

https://hal.science/hal-05385959v1

Preprint submitted on 27 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Learning when to stop

Guillaume Maillard

November 2025

## Abstract

On computers as in life, some tasks just take too long. When the resource consumption of the task outweighs its potential benefits, it should be interrupted - but when? The problem of designing an optimal *interruption mechanism* comes up in the literature in diverse applications, from *restarting algorithms* to contractual hiring and telecommunications. Here, we focus more specifically on the problem of maximizing the number of completed tasks, with a penalty or constraint on the total time spent. Due to its reliance on generic "bandits" methodology, existing work on this subject did not fully address some interesting theoretical issues specific to the interruption mechanism, such as the problem of heavy tails. Since the *whole point* of the interruption mechanism is to protect against heavy-tails of the random times, *known to occur in applications*, one would like to avoid any kind of moment assumption on task duration. In this article, we conduct the first dedicated theoretical investigation of the interruption mechanism, characterizing the minimax regret up to polylog factors. In particular, we show that moment assumptions of any kind are unnecessary. Thus, the interruption mechanism appears to be a fully generic method of guarding oneself against tail risk.

## 1 Introduction

In the field of statistics, *bandit problems* have attracted a great deal of attention as the paradigmatic example of an *online learning* problem. They confront the learning agent with a number of different options, called "arms" *j*, each of which yield a random reward or cost ("negative reward") at each time step. The agent must optimize the total reward over a given period by learning the best arm, i.e finding the arm with the greatest mean reward. This is not always possible, however: it is known that one cannot construct a non-trivial confidence interval, estimator or test for the mean of an arbitrary distribution [3]. Thus, even "robust" bandit methods require some *a priori* assumption on the reward distribution, such as an upper bound on the variance for the "Robust UCB" algorithm of [5] - which may not be available in practice. The issue is particularly significant when the "reward" can be a *cost*, i.e can be negative, since in that case ignoring the tail results in a potentially infinite loss rather than a gain. However, in many practical situations, the agent's *exposure to a loss* is under
his - or her - control, since it results from the agent's spending of some resource over time. The agent can then, at any time, choose to cut his - or her- losses by simply interrupting the flow of this resource. For example, an investor can pull out of a given market, a programmer can terminate a hung program, and a lost man looking for his keys can give up and call a locksmith.

This interruption mechanism provides a means whereby the impact of heavy tails can be mitigated and controlled. Its first formal introduction seems to be in [7], where it is combined with multi-armed bandits in a framework named Bandits with Interrupts. Many applications have been considered in subsequent publications, including SAT competitions [8], contractual hiring [9], search strategies [10] [17] and telecommunications [18], among others. In these settings, interrupting excessively long tasks can improve overall performance, due to the heavy-tailed nature of the delays in such systems [7, 12, 9].

Though these articles demonstrate the practical relevance of the interruption mechanism, their theoretical analysis of it suffers from some defects, such as residual moment assumptions and, in all but one case, a restriction to a finite set of interruption times. The exception is [8], in which several more distributional assumptions are made to compensate. In this article, we take the view that the interruption mechanism is of intrinsic interest and that it should open the way for the removal of all a priori moment assumptions on the cost. To this end, we focus specifically on the problem of learning the optimal interruption policy, in the online setting where the learning agent must both make the decisions (select the deadlines) and attempt to adapt to the unknown distribution of the costs.

More precisely, we consider a decision problem in which the agent is presented with a sequence of tasks which each net a fixed reward after some random time and must choose how long to wait to complete each task before moving on to the next one. The agent either has a fixed deadline - known as a knapsack constraint in the bandit setting [2] - (problem (3)) or pays a cost proportional to the total amount of time spent (problem (1)). At the probabilistic level, problem (3) is closely related to optimal restarts [19], in which the interruption mechanism is used to speed up the completion time of a randomized (Las-Vegas) algorithm by restarting it on the same instance. Instead of maximizing the number of completed tasks within a given deadline, an optimal restart policy aims to complete at least one task in the least possible time. Under certain conditions, the optimal (distribution-dependent) solutions to both problems coincide, see section 2.2 and [21]. A single instance of "optimal restarts" does not allow learning, as only a single task is completed, yielding a single observation. In that case, a universal strategy can be used, which is optimal up to a logarithmic factor [19]. If instead, a sample is available from a given population of problem instances, it is possible to estimate the policy which is optimal on average over the population [11]. Our solution to problem (3) yields a method for learning this policy, under a global time constraint on the learning process. The practical utility of this "statistical" approach was demonstrated by Gagliolo and Schimdhuber [11], who empirically studied a combined strategy made of a learned "population" policy "interleaved" with Luby et al.'s universal strategy [19]. On a database of SAT problems, they showed significant improvements
compared to the universal strategy.

Thus, a solution to problem (3) can be used as a cost-management mechanism in bandit problems or as a population-optimal restart policy. In addition, problems (3) and (1) can be seen as special cases of the more general problem of learning an optimal stopping rule under a constraint (or a penalty) on the total "amortized" time. As a first step towards such problems, we conduct in this article an in-depth theoretical investigation of the optimal interruption of tasks, with the goal of shedding light on the specific challenges and basic design principles necessary to construct an optimal interruption policy that can be robust to heavy tails. For example, unlike previous work, we make no moment assumptions (and in the penalized version, no assumption at all) on the distribution of the waiting times.

From the mathematical viewpoint, the problem is surprisingly rich despite its apparent simplicity and presents a number of novel challenges that distinguish it from the mainstream bandits literature. Firstly, as an optimal stopping problem, it naturally gives rise to a specific, asymmetric information structure in which longer deadlines predict the outcome of shorter deadlines [8] - in contrast to the usual discrete bandit setting in which only the outcome of the selected "arm" is observed. By intelligently exploiting this information structure, we obtain rates of order $\sqrt{n} \log^{3/2} n$ in the penalized problem - equivalent to MAB with only a logarithmic number of arms [6], despite the arm set in our problem being a continuum. This is accomplished by systematically selecting the biggest deadline belonging to a confidence region for the optimal deadline, an approach we call "UCST" (upper confidence stopping time).

Secondly, the possibility of heavy tails forces the learning agent to exercise some caution when exploring. Even if the set of deadlines were discretized, an optimistic agent could fail due to systematically selecting the biggest deadline - where uncertainty is highest - and thus incurring maximal cost. Thus, there is an exploration-robustness tradeoff in addition to the usual exploration-exploitation dynamic. An interesting and convenient feature of our problem is that the (unknown) optimal arm $\tau_*$ is such that the associated cost variable, $\min(X, \tau_*)$ is light-tailed. Thus, by carefully limiting exploration to well-chosen initial segments of $\mathbb{R}_+$ and using concentration inequalities based on the properties of the optimal "stopped" waiting times, we are able to avoid making any moment assumptions on the random variables.

The structure of the paper is the following. First, section 2 gives a mathematical definition and some probabilistic properties of the problem, in both its penalized (sub-section 2.1) and constrained (sub-section 2.2) forms. Section 3 focuses on learning the optimal policy, with the goal of controlling the minimax regret. Subsection 3.1 deals with the penalized problem, while sub-section 3.2 deals with the constrained problem. In each case, both minimax upper bounds (Theorems 3.3 and 3.9) and lower bounds (Theorems 3.4 and 3.10) are presented, which match up to polylog factors. Our estimators rely on confidence bands for the cumulative distribution function, the construction of which is detailed in section 4. Since the "natural" mathematical definitions of our estimators do not readily suggest ways to compute them, algorithms are
worked out in a separate section (Section 5). Finally, the conclusion (section 6) gives some perspectives for future work.

# 2 Some res resource allocation problems: proba-bilistic aspects

## 2.1 Penalized version

Consider the following decision problem. There is a sequence of $n$ tasks to ac-complish, which each require an unknown, random amount $X_i$ of some resource (time, money, data..) in order to complete. Upon completing the task, the agent gains a constant reward $a$ and pays a cost $bX_i$ proportional to the amount of resource used. If a task seems too costly, the agent may at any time choose to interrupt it and move on to the next one. In that case, the agent does not obtain any reward but still pays a cost proportional to the amount of resource used up to that time. In the following, for convenience we shall assume this resource to be time. Let $\tau_i$ be the time at which the agent decides that task $i$ has taken too long and decides to interrupt it.

The only information available to the agent when working on task $j$ is comprised of the time spent and reward gained on each previous task $i \in \{1, \dots, j-1\}$. Thus, $\tau_j$ must only depend on the variables

$$ (X_i \wedge \tau_i, \mathbb{I}\{X_i \le \tau_i\})_{1 \le i \le j-1}. $$

In other words, $\tau_j$ must be measurable with respect to the sigma-algebra

$$ \mathcal{F}_j = \sigma (X_i \wedge \tau_i, \mathbb{I}\{X_i \le \tau_i\})_{1 \le i \le j-1}. $$

Thus, the agent's strategy can be characterized by a sequence of random times $(\tau_j)_{1 \le j \le n}$ which is adapted with respect to the filtration $(\mathcal{F}_j)_{1 \le j \le n}$. The perfor-mance of each strategy is evaluated using the expected value of the total reward (i.e the reward minus the cost).

This leads to the following optimization problem:

$$ \max_{\tau} \left\{ \mathbb{E} \left[ \sum_{i=1}^{n} a \mathbb{I}\{X_i \le \tau_i\} - b(X_i \wedge \tau_i) \right] \right\}, $$

where the maximum is taken over all adapted sequences of stopping times. Factoring by $a$, we can assume without loss of generality that $a = 1$, so that we deal with the optimization problem

$$ \max_{\tau} \left\{ \mathbb{E} \left[ \sum_{i=1}^{n} \mathbb{I}\{X_i \le \tau_i\} - c(X_i \wedge \tau_i) \right] \right\}. \quad (1) $$

Assume that the random times $X_i$ are independent and identically distributed, with common distribution function $F$. Let $G$ be the function

$$ G(\tau) = \mathbb{E}[X_1 \wedge \tau] = \int_0^\tau [1 - F(t)] dt. $$
It is easy to see that

$$ \mathbb{E} \left[ \sum_{i=1}^{n} a \mathbb{I}\{X_i \le \tau_i\} - b(X_i \wedge \tau_i) \right] = \sum_{i=1}^{n} F(\tau_i) - cG(\tau_i) $$

for any sequence $(\tau_i)$ which is adapted to the filtration $(\mathcal{F}_i)$. Thus, if the distribution of $X_1$ is known, then an optimal strategy is to take $\tau_i$ equal to any constant

$$ \tau_c^* \in \underset{\tau \in [0; +\infty]}{\operatorname{argmax}} \{F(\tau) - cG(\tau)\} $$

and the mean reward is then $nV_c^*(F)$, where

$$ V_c^*(F) = \sup_{\tau \in [0; +\infty]} \{F(\tau) - cG(\tau)\}. $$

Let us first examine some interesting properties of the optimal strategy. The mean reward per task $V_c^*(F)$ is clearly non-negative (since one may always take $\tau = 0$). The value $V_c^*(F)$ need not be positive for all values of $c$; however, it is always positive at least for $c$ in a neighbourhood of 0. More precisely, we have the following proposition.

**Proposition 2.1.** Let $F$ be a cumulative distribution function such that $F(0) < 1$ and $F(x) = 0$ for all $x < 0$. Define

$$ \alpha_*(F) = \sup_{\tau>0} \left\{ \frac{F(\tau)}{G(\tau)} \right\} \in (0; +\infty]. \qquad (2) $$

Note that this quantity may be infinite but is always positive. We have that $V_c^*(F) > 0$ if and only if $c < \alpha_*$.

Remark that for a non-negative random variable $X$, the assumptions on $F$ simply exclude the trivial case $X = 0$. Another natural question concerns the necessity of early stopping, i.e whether $\tau_c^*$ can be taken equal to $+\infty$ or not. For some distributions, such as the Uniform or the exponential families, one can prove that an optimal choice is $\tau_c^* \in \{0; +\infty\}$ for all $c$, which means that the task either should be carried out to the end, or should not be attempted at all. On the other hand, if $X$ is very heavy tailed, it is clear that early stopping is necessary in order to protect against tail risk: for example, if $\mathbb{E}[X_1] = +\infty$, then taking $\tau = +\infty$ yields an infinite loss. In fact, the following proposition shows that all heavy tailed distributions require early stopping.

**Proposition 2.2.** If there exists some $t_0 \ge 0$ such that, for all $t \ge t_0$,

$$ F(t) - cG(t) \le 1 - c\mathbb{E}[X_1], $$

then $X_1$ is sub-exponential with parameter $c$: i.e there exists some constant $\kappa \ge 0$ such that

$$ \mathbb{P}(X_1 > t) \le \kappa e^{-ct} $$

for all $t$ large enough. Equivalently, if $X_1$ is not sub-exponential with parameter $c$, then

$$ \tau_c^* \le \sup_{\tau > 0} \{F(\tau) - cG(\tau)\} < +\infty. $$
Thus, early stopping is required for all distributions that are not sub-exponential, including for example the log-normal and Pareto families. This is not a necessary condition and we can also find examples of light-tailed distributions (such as some Gamma distributions) which seem to require early stopping (based on numerical calculations).

## 2.2 Constrained version

Thus far, we have formulated the optimal stopping problem as a trade-off between a reward and a cost proportional to the total time spent. In practice, there are situations where the limit on resource use takes the form of a hard deadline or fixed budget.

Mathematically, this corresponds to the constrained optimization problem:

$$V_n(P, T) = \max_{\tau.} \left\{ \mathbb{E} \left[ \sum_{i=1}^{n} \mathbb{I}_{X_i \le \tau_i} \right] : \sum_{i=1}^{n} X_i \wedge \tau_i \le T \text{ a.s.} , \right\} \quad (3)$$

where $n \in \mathbb{N}$ is the number of tasks, $P$ is the distribution of $X_1$ and $T > 0$ is the budget. As before, the maximum runs over all adapted sequences with respect to the filtration $(\mathcal{F}_i)_{1 \le i \le n}$. If $(\hat{\tau}_i)_{1 \le i \le n}$ is an adapted sequence, there is a generic way to enforce the knapsack constraint: simply replace $\hat{\tau}_i$ by

$$\hat{\tau}'_i = \hat{\tau}_i \wedge (T - T_{i-1})_+, \text{ where } T_{i-1} = \sum_{k=1}^{i-1} X_k \wedge \hat{\tau}_k.$$

For this reason, in the following, we will ignore the knapsack constraint when defining the sequence $(\hat{\tau}_j)_{1 \le j \le n}$, with the understanding that the above transformation is applied to it. Unlike the penalized case, there does not seem to be any simple, explicit solution to equation (3). Instead, following the literature on bandits with knapsacks [2, 1], we shall use the following LP relaxation.

**Definition 2.3.** Let $P$ be a probability distribution supported on $\mathbb{R}_+$. Let $F$ be its probability distribution function, $G$ be the function defined by $G(\tau) = \int (x \wedge \tau)dP(x)$. Let then

$$\bar{V}_n(P,t) = n \sup \left\{ \mathbb{E}[F(Z)] : \mathbb{E}[G(Z)] \le \frac{T}{n} \right\} \quad (4)$$

where the supremum is taken over all non-negative random variables $Z$ satisfying the constraint.

This problem is the "constrained version" of problem (1) in the sense that problem (1) is the Lagrangian relaxation of problem (4). As in the bandits with knapsacks setting, $\bar{V}_n(P,T)$ provides an upper bound on $V_n(P,T)$ (see Theorem 2.7 and its proof). Thus, to show the near-optimality of a policy $\hat{\tau}$, it suffices to show that its mean reward is at least $w(\bar{V}_n(P,T))$ for some non-decreasing function $w$ such that $w(x) \sim x$ for large $x$. This is what will be done
in the next section. For now, let us examine the behaviour of $\overline{V}_n(P,T)$ as a function of $n, T$.

$\overline{V}_n(P,T)$ is defined as the solution to an infinite-dimensional convex optimization problem over the class of probability distributions. Actually, since there is a single constraint, it can be proved that some solution $Z$ lies among the two-point distributions: $Z = \theta\delta_x + (1-\theta)\delta_y$, where $\theta \in [0; 1]$ and $x \le y$ are non-negative reals. When $n$ is large, $x$ can be taken equal to 0 and the problem simplifies further.

**Proposition 2.4.** Let $P$ be a probability distribution on $\mathbb{R}_+$ with distribution function $F$. Assume that $F(0) = 0$. Let $G: x \mapsto \int (t \wedge x)dP(t)$. Define

$$ \tau_*(P) = \sup \operatorname{argmax}_{t>0} \left\{ \frac{F(t)}{G(t)} \right\}. \qquad (5) $$

We have that $\overline{V}_n(P,T) \le \alpha_*(P)T$, with equality if and only if

$$ G(\tau_*(P)) \ge \frac{T}{n}. $$

In that case, any random variable $Z$ with distribution

$$ \frac{T}{nG(\tau_*(P))} \delta_{\tau_*(P)} + \left( 1 - \frac{T}{nG(\tau_*(P))} \right) \delta_0 $$

solves the optimization problem defining $\overline{V}_n(P,T)$. In general, we have the formula

$$ \overline{V}_n(P,T) = \sup_{G(x) < \frac{T}{n} \le G(y)} \left\{ \frac{T - nG(x)}{G(y) - G(x)} F(y) + \frac{nG(y) - T}{G(y) - G(x)} F(x) \right\}. $$

**Proposition 2.4** exhibits a phase transition in the behaviour of $\overline{V}_n(P,T)$. When $n$ is larger than $\frac{T}{G(\tau_*(P))}$, $\overline{V}_n(P,T)$ stops depending on $n$ and becomes proportional to $T$, with constant $\alpha_*(P)$. In that case, the optimal distribution for $Z$ is supported on two points $0, \tau_*(P)$ which do not depend on $T, n$ and we can therefore speak of an "optimal deadline" $\tau_*(P)$. This situation is analogous to the "best-arm optimal" instances of bandits with knapsacks defined in [20]. The constrained problem is then similar to the penalized version (equation (1)) in that the reward function can be parametrized by a single real number. Moreover, the parameters $\alpha_*(P)$ of the constrained version and $V_c^*(P)$ of the penalized version can be related by Lagrange duality, see Proposition 2.1. As a consequence of this relation and of Proposition 2.2, we can deduce that early stopping is required ($\tau_*(P) < +\infty$) whenever $P$ is not sub-exponential. Thus, heavy-tailed distributions require early stopping, as remarked by Cayci et al. [7].

Problem (3) is closely related to optimal restarting in the probabilistic setting. More precisely, equation (1) of [21] shows that the objective in that problem is to maximize $\frac{G}{F}$, which is equivalent to equation (5). Thus, several interesting bounds on $\alpha_*(P)$ follow directly from the results of [21]. For example,
one has that

$$ \frac{1}{2m} \le \alpha_*(P) \le \frac{4}{M}, $$

where m is a median of P and M is the left-most mode of P.

The case $n < \frac{T}{G(\tau_*(P))}$ appears to be more complicated. The optimal distribution is then supported on two points instead of 1, the optimal reward is lower and they depend on both n and T (in general).

Let us now return to the optimal reward $V_n(P,T)$ of a general dynamic policy in problem (3). It follows from Theorem 2.7 that

$$ V_n(P,T) \le \bar{V}_n(P,T) \le \alpha_*(P)T $$

for any $n, T$. If $\frac{T}{G(\tau_*(P))} \le n$, then Proposition 2.4 yields $\bar{V}_n(P,T) = \alpha_*(P)T$. Actually, for slightly larger $n$ one can show that $V_n(P,T)$ too is close to $\alpha_*(P)T$.

**Proposition 2.5.** Let P be a distribution supported on $\mathbb{R}_+$, let $\alpha_* = \alpha_*(P)$, $\tau_* = \tau_*(P)$ and let F, G be associated to P as in Proposition 2.4. For any $T > 0$ and any integer

$$ n \ge \frac{T}{G(\tau_*)} + 2\sqrt{\log(\alpha_*T)}\sqrt{\frac{T}{G(\tau_*)}} + 3\log(\alpha_*T), $$

the optimum reward $V_n(P,T)$ satisfies the bound

$$ \alpha_*T - \alpha_*\tau_* - 1 \le V_n(P,T) \le \alpha_*T. $$

More precisely, the constant strategy equal to $\tau_*$ satisfies this bound.

Thus, for $n$ large enough, $\alpha_*T - V_n(P,T)$ is actually bounded by a constant, as long as $\alpha_*$ and $\tau_*$ are both finite. The case $\tau_* < +\infty$ corresponds to early stopping being necessary, conditions for which we already discussed. The condition $\alpha_* < +\infty$ holds provided for example that the duration of the tasks is bounded from below, which should be the case in any realistic scenario. As mentioned above, Proposition 2.5 is not needed to prove the near-optimality of our methods. However, it is useful in establishing minimax lower bounds.

## 2.3 Effect of allowing the agent to switch tasks

Notice that we have implicitly assumed that the agent cannot return to a previously interrupted task. In fact, allowing him (or her) to do so does not bring any benefit, as we now show. Let us assume that the agent gets to choose the next task among all of the tasks, including those previously interrupted, and sets a new deadline $\tau_j$ for that task. This introduces a new sequence of variable, $\eta(j) \in \{1, \dots, n\}$, representing the task chosen at step j. The index j belongs to the set $\{1, \dots, m\}$, where $m \in \{n, n+1, \dots, \}$ is a bound (if any) on the number of times that the agent can change tasks. The information available up to step j is then

$$ \mathcal{F}_j^{rep} = \sigma (X_{\eta(i)} \wedge \tau_i, \mathbb{I}\{X_{\eta(i)} \le \tau_i\})_{1 \le i \le j-1}, $$
and we require $\eta(j)$, $\tau_j$ to be measurable with respect to this sigma-algebra. For each $i \in \{1, \dots, n\}$, the total time spent on task $i$ is

$$ \bar{\tau}_i = \max_{j=1,\dots,m} \{\tau_j \mathbb{I}\{\eta(j) = i\}\}. $$

Thus, $\bar{\tau}_i$ replaces $\tau_i$ in the formula for the risk, for example

$$ \mathbb{E} \left[ \sum_{i=1}^{n} a \mathbb{I}\{X_i \le \bar{\tau}_i\} - b(X_i \wedge \bar{\tau}_i) \right] $$

in the penalized version.

While it seems that for $j \ge n$, the variables $\tau_j, \eta_j$ may depend on all of the $X_i$, they in fact remain independent from unobserved values of $X_i$, in a sense made precise in the following claim.

**Claim 2.5.1.** Define for any $i \in \{1, \dots, n\}$ and $j \in \{1, \dots, m\}$,

$$ \bar{\tau}_{i,j} = \max_{1 \le k \le j} \{\tau_k \mathbb{I}\{\eta(k) = i\}\}. $$

For any $i \in \{1, \dots, n\}$ and any $j \in \{1, \dots, m\}$, there exists a measurable function $f_{i,j}: \mathbb{R}^{n-1} \to \mathbb{R} \times \{1, \dots, n\}$ such that

$$ (\tau_j, \eta_j) \mathbb{I}\{X_i > \bar{\tau}_{i,j-1}\} = f_{i,j}(\mathbf{X}^{(i)}) \mathbb{I}\{X_i > \bar{\tau}_{i,j-1}\}, $$

where $\mathbf{X}^{(i)} = (X_j)_{j \neq i}$.

It follows that the variable $\bar{\tau}_i$ behave as if they were independent of $X_i$, at least where the reward is concerned.

**Claim 2.5.2.** For all $i, j$, there exists a measurable function $g_{i,j}: \mathbb{R}^{n-1} \to \mathbb{R}_+$ such that with probability one,

$$ \mathbb{I}\{X_i > \bar{\tau}_{i,j}\} = \mathbb{I}\{X_i > g_{i,j}(\mathbf{X}^{(i)})\} \quad (6) $$

$$ \bar{\tau}_{i,j} \mathbb{I}\{X_i > \bar{\tau}_{i,j}\} = g_{i,j}(\mathbf{X}^{(i)}) \mathbb{I}\{X_i > g_{i,j}(\mathbf{X}^{(i)})\}, \quad (7) $$

where $\mathbf{X}^{(i)} = (X_j)_{j \neq i}$. In particular,

$$ \mathbb{E}[\mathbb{I}\{X_i \le \bar{\tau}_i\}] = \mathbb{E}[F(\bar{\tau}_i)] $$

$$ \mathbb{E}[X_i \wedge \bar{\tau}_i] = \mathbb{E}[G(\bar{\tau}_i)], $$

where $F, G$ are as defined previously.

The above claim immediately yields the following bound on the reward in the penalized case.

**Theorem 2.6.** Let $(X_i)_{1 \le i \le n}$ be i.i.d random variable with cumulative distribution function $F$. Let $m \ge n$ be an integer. Let $(\eta(j), \tau_j)_{1 \le j \le m}$ be an adapted sequence with respect to the filtration $(\mathcal{F}_j^{\text{rep}})_{1 \le j \le m}$, where $\tau_j \in \mathbb{R}_+$ and
$\eta(j) \in \{1, \dots, n\}$ for all $j \in \{1, \dots, m\}$. For any $c > 0$, the reward of this strategy satisfies the bound

$$ \mathbb{E} \left[ \sum_{i=1}^{n} \mathbb{I}\{X_i \le \bar{\tau}_i\} - c(X_i \wedge \bar{\tau}_i) \right] \le n V_c^*(F) $$

where, as above,

$$ \bar{\tau}_i = \max_{1 \le j \le m} \{\tau_j \mathbb{I}\{\eta(j) = i\}\}. $$

Thus, allowing the agent to return to a previous task is not advantageous since it does not increase the optimal reward.

Consider now the constrained case. Let $m \ge n$ be the number of times that the agent may switch from one task to another. The optimization problem becomes

$$ V_{n,m}(P,T) = \max_{\tau, \eta} \left\{ \mathbb{E} \left[ \sum_{i=1}^{n} \mathbb{I}_{X_i \le \bar{\tau}_i} \right] : \sum_{i=1}^{n} X_i \wedge \bar{\tau}_i \le T \text{ a.s.} \right\} \quad (8) $$

where

$$ \bar{\tau}_i = \max_{1 \le j \le m} \tau_j \mathbb{I}\{\eta(j) = i\}, $$

and the maximum runs over all sequences $(\tau_j, \eta_j)_{1 \le j \le m}$ which are adapted with respect to the filtration

$$ \mathcal{F}_j^{rep} = \sigma (X_{\eta(i)} \wedge \tau_i, \mathbb{I}\{X_{\eta(i)} \le \tau_i\})_{1 \le i \le j-1} $$

The following Theorem compares $V_{n,m}$ with $V_n$ and $\bar{V}_n$.

**Theorem 2.7.** Let $P$ be a probability distribution supported on $\mathbb{R}_+$, $n, m$ be integers such that $m \ge n$. Then

$$ V_n(P,T) \le V_{n,m}(P,T) \le \bar{V}_n(P,T). $$

Thus, $V_{n,m}$ is always sandwiched between $V_n$ and $\bar{V}_n$. It follows that the potential advantage provided by switching back to a previous task, measured by $V_{n,m} - V_n$, is negligible, at least when $n$ is large enough (greater than $(1 + o(1))\frac{T}{G(\tau_*)}$, by Proposition 2.5). We shall therefore focus on solving problems (1) and (3).

# 3 Statistical version of the problem

In problems (1) and (3), the optimal reward and optimal policy both depend on the underlying distribution $P$. In applications, $P$ is generally unknown, so the optimal policy is inapplicable. In this section, we consider the problem of defining *adaptive policies* that yield a near-optimal reward while not relying on the knowledge of $P$.
More precisely, the measurability assumption on $\hat{\tau}$ means that $\hat{\tau}_j$ can be written as a measurable function of the vector $D_j = (X_i \wedge \hat{\tau}_i, \mathbb{I}\{X_i \le \hat{\tau}_i\})_{1 \le i \le j-1}$. A policy can therefore be identified with a collection of measurable functions $\hat{\tau} = (\hat{\tau}_j)_{1 \le j \le n}$, where $\hat{\tau}_1$ is constant and $\hat{\tau}_j : \mathbb{R}^{j-1} \to \mathbb{R}$ for $j \ge 2$. As is standard practice in statistics, we will often abuse notation by writing $\hat{\tau}_j$ instead of $\hat{\tau}_j(D_j)$, whenever this does not create confusion. Let now

$$ \psi_{\hat{\tau},j}(X_1, \dots, X_n) = (X_i \wedge \hat{\tau}_i, \mathbb{I}\{X_i \le \hat{\tau}_i\})_{1 \le i \le j}, $$

the function $\psi_{\hat{\tau},j}$ is measurable and can be defined recursively as

$$ \begin{aligned} \psi_{\hat{\tau},0}(x) &= 0 \\ \psi_{\hat{\tau},1}(x) &= (\min(x_1, \hat{\tau}_1), \mathbb{I}\{x_1 \le \hat{\tau}_1\}) \\ \psi_{\hat{\tau},j+1}(x) &= (\psi_{\hat{\tau},j}(x), (\min(x_{j+1}, \hat{\tau}_{j+1}(\psi_{\hat{\tau},j}(x))), \mathbb{I}\{x_{j+1} \le \hat{\tau}_{j+1}(\psi_{\hat{\tau},j}(x))\})) \end{aligned} $$

The goal of adaptation is to design a universal (distribution-independent) policy $\hat{\tau}$ which performs almost as well as the distribution-dependent optimal policy. Thus, an *adaptive policy* should be purely data-driven, its only parameters being $n, c$ (in problem (1)) or $n, T$ (in problem (3)), which are assumed to be known to the decision-maker. The performance of a policy $\hat{\tau}$ for a given distribution $P$ is measured by its *regret*, which is the gap between the reward obtained by $S$ and the optimal reward for $P$:

$$ R_{n,c}^{\text{pen}}(P, \hat{\tau}) = nV_c^*(P) - \mathbb{E}_{\mathbf{X} \sim P^{\otimes n}} \left[ \sum_{j=1}^{n} \mathbb{I}\{X_j \le \hat{\tau}_j(\psi_{\hat{\tau},j-1}(\mathbf{X}))\} - c \min(X_j, \hat{\tau}_j(\psi_{\hat{\tau},j-1}(\mathbf{X}))) \right] \quad (9) $$

$$ R_{n,T}^{\text{bgt}}(P, \hat{\tau}) = V_n(P, T) - \mathbb{E}_{\mathbf{X} \sim P^{\otimes n}} \left[ \sum_{j=1}^{n} \mathbb{I}\{X_j \le \hat{\tau}_j(\psi_{\hat{\tau},j-1}(\mathbf{X}))\} \right] \quad (10) $$

$$ \text{where } \sum_{j=1}^{n} x_j \wedge S_j(\psi_{S,j-1}(x)) \le T \text{ for all } x \in \mathbb{R}^n \quad (11) $$

Qualitatively speaking, an adaptive policy is good if the reward it yields is close to optimal, i.e if its regret is small relative to the reward, when the reward is large enough. This goal can be quantified in various ways. For a fixed distribution $P$, the reward scales proportionally to $n$ in problem (1) and to $T$ in problem (3) (when $n$ is large enough), so a natural requirement is to have $R_{n,c}^{\text{pen}}(P, S) = \mathcal{O}(n^\gamma)$ in problem (3) and $R_{n,T}^{\text{bgt}}(P, S) = \mathcal{O}(T^\gamma)$ in problem (3), with best possible rate $\gamma$. This notion is called "sub-linear regret" in the bandit literature. Note that since the arms form a continuum, a logarithmic regret is generally impossible in this problem since the optimality gap is 0 (for a continuous distribution), unlike the finitely armed setting. In this "instance-dependent" approach, the constant in the $\mathcal{O}$ notation may depend on $P$ and so there may not be any non-trivial guarantee for a fixed $n, T$ when $P$ is arbitrary.
A stronger performance criterion is provided by the uniform rate of convergence over a class of distributions $\mathcal{P}$, which is defined by the formula

$$R_{n,c}^{\text{pen}}(\mathcal{P}, S) = \sup_{P \in \mathcal{P}} \{R_{n,c}^{\text{pen}}(P, S)\}$$

(which has an obvious analogue in the constrained problem). A policy $\hat{\tau}$ is said to be minimax (or worst-case) optimal over the class $\mathcal{P}$ (up to $\gamma_{n,c,T}$-factor) if its uniform rate of convergence over $\mathcal{P}$ is best-possible (up to a factor proportional to $\gamma_{n,c,T}$). Minimax optimality is a strong guarantee, but its defect is that it only considers the worst-case scenario within the class $\mathcal{P}$. Thus, uniformity comes at the expense of precision. This can be remedied by replacing the single class $\mathcal{P}$ with a parametrized family $(\mathcal{P}_{\theta})_{\theta \in \Theta}$ and requiring simultaneous minimax optimality over each class $\mathcal{P}_{\theta}$. A policy $\hat{\tau}$ which satisfies this property is called minimax-adaptive and may not always exist (depending on $(\mathcal{P}_{\theta})_{\theta \in \Theta}$). In this article, we shall only consider adaptivity with respect to the reward, in keeping with the principle that the regret should be small when the reward is large. This corresponds to taking $\theta$ to be an upper bound on the optimal reward $(nV_c^*(P)$ or $V_n(P, T))$.

The central statistical tool for our methods is a collection of nested non-parametric confidence bands for the cumulative distribution function, for which we introduce some general notation. The specific construction used is detailed in section 4. Let $\mathcal{F}$ be the set of non-decreasing functions from $\mathbb{R}_+$ to $[0; 1]$ (for technical reasons, we do not impose right-continuity). For any two functions $l, u: \mathbb{R} \to [0; 1]$, denote by $[l; u]$ the subset of $f \in \mathcal{F}$ such that $l \le f \le u$. Let $\tilde{F}_{n,\eta}$, $\tilde{F}_{n,\eta}^+$: $\bigcup_{k \in \mathbb{N}} \mathbb{R}^k \to [0; 1]^\mathbb{R}$ be two functions such that

$$\mathbb{P}(\exists j \in \{0, \dots, n-1\} : F \notin [\tilde{F}_{n,\eta}^{-}(X_1, \dots, X_j); \tilde{F}_{n,\eta}^{+}(X_1, \dots, X_j)]) \le \eta \quad (12)$$

for any cdf $F$ and any i.i.d vector $X_1, \dots, X_n$ with common cdf $F$. Note that we allow $j = 0$, in which case we set $\tilde{F}_{n,\eta}^{-}(\emptyset) = 0$ and $\tilde{F}_{n,\eta}^{+}(\emptyset) = 1$.

We assume $\tilde{F}_{n,\eta}^{-}, \tilde{F}_{n,\eta}^{+}$ to be of the form

$$\tilde{F}_{n,\eta}^{-}(x_1, \dots, x_j) = w_{j,\eta}^{-} \circ \tilde{F}, \quad \tilde{F}_{n,\eta}^{+}(x_1, \dots, x_j) = w_{j,\eta}^{+} \circ \tilde{F}, \quad (13)$$

where $w_{j,\eta}^{-}, w_{j,\eta}^{+}$ are functions from $[0; 1]$ to $[0; 1]$ and $\tilde{F}: \bigcup_{k \in \mathbb{N}} \mathbb{R}^k \to \mathcal{F}$ is the empirical cdf functional defined by

$$\tilde{F}(x_1, \dots, x_k) : \tau \mapsto \frac{1}{k} \sum_{i=1}^{k} \mathbb{I}\{x_i \le \tau\}.$$

When $j = 0$, $w_{0,\eta}^{-} = 0$, $w_{0,\eta}^{+} = 1$ and $\tilde{F}(\emptyset)$ may be chosen arbitrarily in $[0; 1]$. For example, the DKW inequality, together with a union bound, shows that equation (12) holds for $w_{j,\eta}^{-}, w_{j,\eta}^{+}$ defined by

$$w_{j,\eta}^{-}(t) = \left( t - \sqrt{\frac{1}{2j} \log \left( \frac{2n}{\eta} \right)} \right)_{+}, \quad w_{j,\eta}^{+}(t) = \min \left( 1, t + \sqrt{\frac{1}{2j} \log \left( \frac{2n}{\eta} \right)} \right).$$
Beyond these general features, problems (1) and (3) behave quite differently and we now discuss them separately.

## 3.1 The penalized optimal stopping problem (1)

In order to take into account the observational structure, we introduce a new upper confidence stopping time heuristic which consists in choosing at each step j the upper bound of some confidence region $\mathcal{X}_j$ for the optimal deadline $\tau_c^*(P)$. The confidence regions are constructed such that they are nested, i.e $\mathcal{X}_{j+1} \subset \mathcal{X}_j$, which results in a non-increasing sequence of thresholds. This means that at each step j, all of the past data is available to estimate the mean reward of any $\tau \in \mathcal{X}_j$ and hence to construct the confidence subset $\mathcal{X}_{j+1} \subset \mathcal{X}_j$. Since this heuristic can select very large, even infinite deadlines when j is small, we truncate the deadlines in order to limit tail risk and to optimize the aforementioned "robustness-exploration" tradeoff.

The construction of the confidence regions $\mathcal{X}_j$ relies on confidence bands for the distribution function $F$ of the form $[\hat{F}_j^-; \hat{F}_j^+]$. Our confidence band $[\hat{F}_j^-; \hat{F}_j^+]$ must be measurable with respect to the censored data up to time j. To this end, we introduce the set

$$ \mathcal{I}(j, \tau) = \{i \in \{1, \dots, j-1\} : \hat{\tau}_i \ge \tau\} $$

and let $\hat{F}_j^-, \hat{F}_j^+$ be defined by $\hat{F}_1^- = 0, \hat{F}_1^+ = 1$ and

$$ \hat{F}_j^- : \tau \mapsto \max_{1 \le k \le j} \tilde{F}_{n,\eta}^{-}((X_i)_{i \in \mathcal{I}(k, \tau)})(\tau) \quad (14) $$

$$ \hat{F}_j^+ : \tau \mapsto \min_{1 \le k \le j} \tilde{F}_{n,\eta}^{+}((X_i)_{i \in \mathcal{I}(k, \tau)})(\tau) \quad (15) $$

for all $j \in \{1, \dots, n\}$ and some $\eta$ to be chosen later. It follows from this definition that the confidence bands $[\hat{F}_j^-; \hat{F}_j^+]$ are nested. We can now define the following universal strategy.

**Definition 3.1.** Let $\tau_1 \ge 0$ be deterministic. For all $j \in \{2, \dots, n\}$, let

$$ \hat{\tau}_j = \sup_{f \in [\hat{F}_j^-, \hat{F}_j^+]} \sup_{t \in [0; \hat{\tau}_{j-1}]} \underset{\tau \in \mathcal{I}(k, \tau)}{\operatorname{argmax}} \left\{ f(t) - c \int_0^t (1 - f(s))ds \right\}. \quad (16) $$

The policy given by Definition 3.1 implements the upper confidence stopping time heuristic with $\mathcal{X}_j$ equal to the set of optimal deadlines for all functions f belonging to the confidence band $[\hat{F}_j^-; \hat{F}_j^+]$. By construction, the sequence $(\hat{\tau}_j)$ is non-increasing and bounded by some pre-determined threshold $\tau_1$, which is a free parameter. It follows that the confidence bands $[\hat{F}_j^-; \hat{F}_j^+]$ have nominal coverage.

**Lemma 3.2.** Let $(X_i)_{1 \le i \le n}$ be i.i.d random variables with common cdf $F$. For the strategy $(\hat{\tau}_j)_{1 \le j \le n}$ given by definition 3.1 and $\hat{F}_j^-, \hat{F}_j^+$ given by equations
(14), (15), the probability that $F \in [\hat{F}_j^-; \hat{F}_j^+]$ for all $j \in \{1, \dots, n\}$ is at least $1 - \eta$.

Overall, the policy given by Definition 3.1 has two free parameters: $\eta$ (the confidence level) and $\tau_1$. Theorem 3.3 below gives a uniform upper bound on the regret of this strategy, for an appropriate choice of $\eta$, $\tau_1$ and $\hat{F}_{n,\eta}^{\pm}$.

**Theorem 3.3.** Fix $n \in \mathbb{N}$ and $c > 0$. Let $\hat{F}_{n,\eta}^{\pm}$ be constructed as in section 4. Let $\hat{\tau} = (\hat{\tau}_j)_{1 \le j \le n}$ be the strategy given by Definition 3.1, with

$$ \eta = \frac{1}{n}, \quad \tau_1 = \frac{\sqrt{n}}{c(1 + \log n)}. $$

There exists a numerical constant $\kappa$ such that for any distribution $P$ supported on $\mathbb{R}_+$,

$$ R_{n,c}^{\text{pen}}(P, \hat{\tau}) \le \kappa \sqrt{n} \log n, \quad (17) $$

Theorem 3.3 states that the minimax regret over the class of all probability distributions supported on $\mathbb{R}_+$ is at most of order $\sqrt{n}$, up to a logarithmic factor. This may seem surprising - how is it possible to estimate $G$ well-enough without moment assumptions on $X_1$? Indeed, for some distributions, $\text{Var}(X_1 \wedge t)/G(t)^2$ may grow without bound, so $G(t)$ cannot be estimated at rate $\frac{1}{\sqrt{n}}$ uniformly over $t$. The answer lies in the specific properties of the optimum parameter $\tau_c^*(P)$, which in particular always belongs to the set

$$ \{t \in \mathbb{R} : \text{Var}(X_1 \wedge t) \le G(t)^2 \text{ and } G(t) \le \frac{1}{c}\} $$

where $X_1 \wedge t$ is well-concentrated and $G(t)$ is bounded by a constant. Crucially, it can be shown that the confidence band $[\hat{G}_j^-; \hat{G}_j^+]$ on $G$ associated with $[\hat{F}_j^-; \hat{F}_j^+]$ is adequately "narrow" at $t \in \{\tau_c^*, \hat{\tau}_j\}$ in the sense that

$$ \hat{G}_j^+(t) - \hat{G}_j^-(t) \le \frac{\kappa_1}{c} \sqrt{\frac{\log n}{j-1}} + \kappa_2 \frac{\log n}{j-1} \hat{\tau}_j $$

for some numerical constants $\kappa_1, \kappa_2$ (see Proposition 4.6 and claim C.2.1). Together with the bound $\hat{\tau}_j \le \frac{\lambda}{c}$, this result substitutes for the missing uniform bound on $\hat{G}_j^+ - \hat{G}_j^-$.

The resulting rate, $\sqrt{n}$ (ignoring log terms), is similar to the worst-case slow rates of batch M-estimators problem in statistical learning. The following Theorem shows that it is minimax optimal.

**Theorem 3.4.** For any $\varepsilon > 0$, let $\mathcal{P}_\varepsilon$ denote the class of distributions

$$ \mathcal{P}_\varepsilon = \{Q : V_c^*(Q) \le \varepsilon\}. $$

For any integer $n$ such that $n \ge \frac{0.05}{\varepsilon^2}$ and any strategy $S$,

$$ \sup_{P \in \mathcal{P}_\varepsilon} \{R_{n,c}^{\text{pen}}(P, S)\} \ge 0.033\sqrt{n} - 0.02. $$
Theorem 3.4 is proved using the two-hypothesis method applied to the batch estimation problems:

$$ \text{maximize } x \mapsto F(x) - c \int_{0}^{x} (1 - F(t))dt \text{ given } X_{1}, \dots, X_{j} \text{ i.i.d.} \sim F $$

for $j \in \{1, \dots, n\}$. Thus, the hardness of this ordinary M-estimation problem (with $j = n$) differs from that of the online "bandit" problem (1) by at most a logarithmic term. The online-to-batch conversion and two-hypothesis method seem too crude to recover the logarithmic terms exactly; a more involved analysis would be required.

The lower bound of Theorem 3.4 does not depend on $\varepsilon$ for $n$ large enough, larger than $\frac{0.05}{\varepsilon^2}$. Thus, strategy (3.1) is trivially adaptive with respect to $V_c^*(P)$, at least when $n$ is large enough. Theorem 3.4 actually shows that the regret of a universal strategy $S$ cannot be a sub-linear function of the reward only. To see this, suppose that $R_{n,c}^{\text{pen}}(P, S) \le w(nV_c^*(P))$ for a non-decreasing function $w$ and all distributions $P$. By Theorem 3.4, for all $n \in \mathbb{N}^*$ and $\varepsilon \ge \sqrt{\frac{0.05}{n}}$, there exists $Q \in \mathcal{P}_\varepsilon$ such that

$$ 0.033\sqrt{n} - 0.02 \le R_{n,c}^{\text{pen}}(Q, S) \le w(nV_c^*(Q)) \le w(n\varepsilon). $$

It follows that for all $n \ge 1$, $w(\sqrt{0.05n}) \ge 0.033\sqrt{n} - 0.02$, so $w(t) \ge \lambda t$ for some $\lambda > 0$ and all $t$ larger than some constant. In particular, $w$ cannot be sub-linear. This situation is in sharp contrast with the constrained case, as we shall now see.

## 3.2 The constrained optimal stopping problem (3)

In problem (3) in which the optimal reward $V_n(P, T)$ is a function of two parameters $n, T$, the ideal would be a regret bound of the form $V_n(P, T)^\gamma$ (up to log terms), with $\gamma$ as small as possible. For general $n, T$ and arbitrary $P$, the optimal strategy and the optimal value of $\gamma$ remain unclear. In this article, we focus on the case $n \ge \frac{T}{G(\tau_*)}$, where the optimal policy is (loosely speaking) characterized by a single optimal deadline $\tau_*(P)$ and the optimal reward by a single parameter $\alpha_*(P)$ (Proposition 2.4). In this case, a provably optimal universal policy (up to log terms) can be constructed with rate $\gamma = \frac{1}{2}$. The problem consists in maximizing the function $\frac{F}{G}$ while carefully managing the trade-off between exploration, exploitation and robustness to extreme values of $X_i$.

To this end, the *upper confidence stopping time* policy is, by itself, inadequate. Its main limitation is that it uses an equal number of observations to estimate the reward of each potentially optimal arm $\tau \in \mathcal{X}_j$. In problem (1), this is fine because exploration is only limited by the number of observations, $n$. In problem (3) and for $n \ge \frac{T}{G(\tau_*(P))}$ however, it is the time constraint and not the number of tasks which mainly limits exploration. For a given number of observations $j$, exploring arm $\tau$ takes less time when $\tau$ is smaller; the average time taken is $jG(\tau)$, on average. By always selecting the most expensive arms
to explore, the upper confidence stopping time policy fails to efficiently explore the small values of $\tau$, which suggests that it is sub-optimal for problem (3). In fact, heuristic calculations based on the form of the confidence regions for $F$ and $G$ suggest that the optimal policy should allocate exploration time approximately equally to each deadline $\tau \in [T/n; T]$. This could be done explicitly, but it would be complicated and result in an excessively ad-hoc methodology, highly specific to problem (3). A more elegant and general approach, in our view, is to combine upper confidence stopping time with UCB. This combined policy can be described as follows:

* Form a finite partition of the set of arms, $(B_j)_{1\le j\le K}$

* Use UCB to select a block $\hat{B}$ of the partition.

* Use $ucst$ within the chosen block to choose an arm $\hat{b} \in \hat{B}$.

Roughly speaking, step 2 is a many-armed "bandits with knapsacks" problem [2], for which UCB is known to be optimal up to logarithmic factors [20]. In step 3, $ucst$ is used to select among the arms belonging to the optimal block $\hat{B}$ of the partition. This will succeed if the arms in $\hat{B}$ are "similar enough" in the sense that they require a similar number of samples for optimal exploration. If this number is $j$, the "equal exploration time" heuristic yields $jG(t) \approx jG(s)$ for all $s, t \in \hat{B}$, i.e $G$ should not increase by more than a constant factor over $\hat{B}$. This is the case if $B_j = (t_{j+1}; t_j]$ for some decreasing geometric sequence $(t_j)_{1\le j\le K}$. As for $ucst$, the policy must be supplemented with an adaptive thresholding rule in order to protect against extreme values. The optimal threshold depends on $\alpha_*(P)$ and must therefore be estimated online.

Let us now explicitly construct the optimal universal policy. For any $k \in \mathbb{Z}$, let $t_k = T2^{-k}$, $B_k = (t_{k+1}; t_k]$ and for any $j \in \{1, \dots, n\}$, $\tau > 0$, let

$$ \mathcal{I}(k, j, \tau) = \{i \in \{1, \dots, j-1\} : \hat{\tau}_i \in B_k \cap [\tau; +\infty)\} \quad (18) $$

Let $K = \lfloor \log_2 n \rfloor + 1$ and $\eta' = \eta/K$. Define $\hat{F}_j^-, \hat{F}_j^+$ by

$$ \hat{F}_j^- : \tau \mapsto \max_{1 \le r \le j} \max_{0 \le k \le K-1} \tilde{F}_{n, \eta'}((X_i)_{i \in \mathcal{I}(k, r, \tau)})(\tau) \quad (19) $$

$$ \hat{F}_j^+ : \tau \mapsto \min_{1 \le r \le j} \min_{0 \le k \le K-1} \tilde{F}_{n, \eta'}((X_i)_{i \in \mathcal{I}(k, r, \tau)})(\tau) \quad (20) $$

for all $j \in \{1, \dots, n\}$. From the confidence band $[\hat{F}_j^-; \hat{F}_j^+]$, a confidence region for the pair $(F, G)$ can be derived.

**Definition 3.5.** For any $j \ge 1$, let $\mathbb{H}_j$ be the set of pairs $(f, g)$ where $f \in [\hat{F}_j^-; \hat{F}_j^+]$ is a cdf, $g$ is the function $t \mapsto \int_0^t (1 - f(s))ds$ and $(f, g)$ satisfies the constraint

$$ g\left(\sup_{t>0} \operatorname{argmax} \left\{\frac{f(t)}{g(t)}\right\}\right) \ge \frac{T}{n}. $$
$\mathbb{H}_j$ is a confidence region for $(F, G)$ based on the observations up to index $j-1$. The constraint in the definition of $\mathbb{H}_j$ plays an important role, since $\tau \in \operatorname{argmax}\{\frac{F}{G}\}$ is not optimal when $G(\tau) < \frac{T}{n}$ - this is because the resulting policy does not use all the available time. Note that $(F, G) \in \mathbb{H}_j$ exactly when $F \in [\hat{F}_j^{-}; \hat{F}_j^{+}]$, under the assumption that $G(\tau_{*}(P)) \ge \frac{T}{n}$. In particular, $\mathbb{H}_j$ is then non-empty. Let us now define the quantities related to the UCB heuristic.

**Definition 3.6.** For any $j \ge 1$, let

$$ \hat{\alpha}_j^+ = \sup_{(f,g) \in \mathbb{H}_j} \sup_{t>0} \left\{ \frac{f(t)}{g(t)} \right\}. $$

Fix $\varepsilon \in (0; 2(\sqrt{2} - 1)]$, let

$$ O_j = \left\{ (f,g) \in \mathbb{H}_j : \sup_{t>0} \left\{ \frac{f(t)}{g(t)} \right\} \ge \frac{\hat{\alpha}_j^+}{\rho_j} \right\}, $$

where

$$ 0 < 1 - \frac{1}{\rho_j} \le \frac{\varepsilon}{\left(1 + 2\sqrt{\hat{\alpha}_j^+ T}\right)^3}. \quad (21) $$

Choose

$$ \tau_j^* = \sup_{t \in (0; +\infty]} \operatorname{argmax} \left\{ \frac{f(t)}{g(t)} \right\} \quad \text{for some } (f,g) \in O_j. $$

$\tau_j^*$ is the deadline selected by UCB based on the confidence region $\mathbb{H}_j$ for $F, G$ using the observations up to index $j-1$. $\tau_j^*, \hat{\alpha}_j^+$ are well-defined as long as $\mathbb{H}_j$ is non-empty, which is true when $F \in [\hat{F}_j^{-}; \hat{F}_j^{+}]$, i.e when the confidence band is valid. Since the supremum in $(f, g)$ in the definition of $\hat{\alpha}_j^+$ is not necessarily attained on $\mathbb{H}_j$, we introduce a set $O_j$ of approximate maxima. The condition on $\rho_j$ ensures that this does not significantly affect our theoretical guarantees. Let us finally define the sequence $(\hat{\tau}_j)_{1 \le j \le n}$.

**Definition 3.7.** If $\mathbb{H}_j = \emptyset$, let $\hat{\tau}_j = \hat{\tau}_{j-1}$. Otherwise, let $k_j, K_j, \hat{\tau}_j$ be defined as follows.

$$ K_j = \max \left\{ k \in \mathbb{N} : t_k \ge \min \left( T, \sqrt{\frac{T}{\hat{\alpha}_j^+ \log n}} \right) \right\} \quad (22) $$

$$ k_j = \max \{k \in \mathbb{Z} : t_k \ge \tau_j^*\} \quad \text{with} \quad \max \emptyset = -\infty \quad (23) $$

If $k_j \ge K_j$, then

$$ \hat{\tau}_j = \sup_{f \in [\hat{F}_j^{-}; \hat{F}_j^{+}]} \sup_{t \in (0; t_{k_j}]} \operatorname{argmax} \left\{ \frac{f(t)}{\int \min(x, t) df(x)} \right\}. \quad (24) $$
If $k_j < K_j$, then

$$ \hat{\tau}_j = \begin{cases} t_{K_j} & \text{if } \{\hat{\tau}_i : i \le j - 1\} \cap (t_{K_j+1}; t_{K_j}] = \emptyset \\ \min\{\hat{\tau}_i : i \le j - 1\} \cap (t_{K_j+1}; t_{K_j}] & \text{otherwise.} \end{cases} \quad (25) $$

Note that $\hat{F}_1^- = 0$ and $\hat{F}_1^+ = 1$, hence $\mathbb{H}_1$ is the (non-empty) set of all $(f, g)$ associated with distributions $Q$ such that $g(\tau_*(Q)) \ge \frac{T}{n}$. In particular, Definition 3.7 works when $j = 1$. It follows by induction that the sequence $(\hat{\tau}_j)_{1 \le j \le n}$ is well-defined. Its construction guarantees that for any $k \in \mathbb{N}$, the sub-sequence

$$ (\hat{\tau}_i)_{i \in I(k)}, \quad I(k) = \{i \in \{1, \dots, n\} : \hat{\tau}_i \in B_k\} $$

is non-increasing. This is due to the confidence bands $[\hat{F}_j^-; \hat{F}_j^+]$ being nested. As a consequence, it can be shown that the confidence bands $[\hat{F}_j^-; \hat{F}_j^+]$ have coverage at least $1 - \eta$.

**Lemma 3.8.** Let $(X_i)_{1 \le i \le n}$ be i.i.d random variables with common cdf $F$. For the strategy $(\hat{\tau}_j)_{1 \le j \le n}$ given by definition 3.6, the probability that $F \in [\hat{F}_j^-; \hat{F}_j^+]$ for all $j \in \{1, \dots, n\}$ is at least $1 - \eta$.

It follows that the confidence region $\mathbb{H}_j$ for $(F, G)$ has the expected coverage $1 - \eta$ provided that $G(\tau_*(P)) \ge \frac{T}{n}$, which we assumed a priori. The performance of the strategy given by Definition 3.7 depends on the shape of the confidence bands, i.e on the choice of functions $w_{\eta,j}^-, w_{\eta,j}^+$ such that equation (12) holds. The following theorem is stated for $w_{\eta,j}^-, w_{\eta,j}^+$ given by Definition 4.1 of section 4. In fact, an examination of the proof (which can be found in section D) shows that similar results hold for any confidence region of Bernstein type, i.e such that

$$ w_{\eta,j}^{+}(u) - w_{\eta,j}^{-}(u) \le \frac{a_0}{\sqrt{j}} \sqrt{(\log n - \log \eta)u(1-u)} + \frac{b_0}{j}(\log n - \log \eta) $$

for some numerical constants $a_0, b_0$ and all $j \in \{1, \dots, n\}, u \in [0; 1]$.

**Theorem 3.9.** Let $P$ be a distribution supported on $\mathbb{R}_+$ such that $\alpha_*(P) < +\infty$. Let $(X_i)_{1 \le i \le n}$ be i.i.d random variables with distribution $P$, with $n$ such that

$$ \mathbb{E}[\min(X_1, \tau_*(P))] \ge \frac{T}{n}. \quad (26) $$

Let $T_1 = 0$ and for any $j \in \{2, \dots, n\}$, let

$$ T_j = \sum_{i=1}^{j-1} X_i \wedge \hat{\tau}_i $$
the time spent in the first j steps. Strategy $\hat{\tau} = (\hat{\tau}_j)_{1\le j\le n}$ given by Definition 3.7 with $\eta = \frac{1}{\sqrt{n}}$ and $w_{j,\eta}^-, w_{j,\eta}^+$ given by Definition 4.1 has reward at least

$$ \mathbb{E}\left[\sum_{j=1}^{n} \mathbb{I}\{X_j \le \min(\hat{\tau}_j, T - T_j)\}\right] \ge \left(\alpha_*(P)T - 59 \log^{3/2} n \sqrt{\alpha_*(P)T}\right)_+ . $$

Moreover, its regret is at most

$$ R_{n,T}^{\text{bgt}}(P, \hat{\tau}) \le 59 \log^{3/2} n \sqrt{V_n(P, T)}. $$

The only assumption made in Theorem 3.9 is that $G(\tau_*(P)) \ge \frac{T}{n}$, which is precisely the condition given by Proposition 2.4 under which $\bar{V}_n(P,T) = \alpha_*T$ and under which the LP-optimal distribution (in the sense of [2]) is supported on $\{0; \tau_*(P)\}$, a situation known as best-arm optimality in the literature on bandits with knapsacks [1]. Thus, Theorem 3.9 shows that whenever $n$ is large enough that $\bar{V}_n(P,T)$ saturates at $\alpha_*T$, the adaptive policy 3.7 attains the optimal reward $\alpha_*T$ up to an error of order $\log^{3/2}(n)\sqrt{\alpha_*T}$. This regret bound is almost the same as that of [2] in the many-armed bandits with knapsacks problem for a fixed number of arms and costs and rewards belonging to $[0; 1]$ - the only difference being that our bound lacks the term corresponding to $\frac{\text{OPT}}{\sqrt{B}}$, which translates to $\frac{\alpha_*T}{\sqrt{T}} = \alpha_*\sqrt{T}$ in the framework of this article. This is in spite of the set of arms being a continuum and the costs being arbitrarily heavy tailed! The reason why our bound lacks the $\frac{\text{OPT}}{\sqrt{B}}$ remainder term - known to be unavoidable in the bandits with knapsacks setting [2] - is not entirely clear, but it seems to be due to the additional structure of problem (3), which at least prevents the counterexample of [2] from working: no two arms $t_1, t_2$ may have deterministic rewards $\mathbb{I}\{X \le t_i\} = 1$ and different costs $G(t_1), G(t_2)$. In any case, it is not due to the best-arm optimality assumption, since the lower bound of [2] is in fact first proved for $n = +\infty$.

Compared to previous appearances of the interruption mechanism in the bandits literature [7, 8, 9], Theorem 3.9 requires much weaker assumptions on the cost variable $X_i$. Firstly, unlike Theorem 3.9, all these articles assume the finiteness of a moment of order at least $1 + \delta$. Moreover, [7] and [9] restrict the problem to a finite set of deadlines and have a bound which depends polynomially on the cardinality of this set. Only [8] considers the continuous setting, but at the price of more distributional assumptions, including for example a unimodality assumption on $\frac{F}{G}$. Finally, all these authors work in a setting where $n = +\infty$, so that our assumption $n \ge \frac{T}{G(\tau_*(P))}$ is trivially verified. Of course, these authors consider more complicated problems in which there are multiple "arms" as well as a random reward $Y$, while Theorem 3.9 focuses on the cost variable and interruption mechanism. Improving their results along the lines of Theorem 3.9 would take further research, but we do believe that it can be done for bounded $Y$, as discussed in greater detail in the conclusion.

Let us now state a minimax lower for problem (3).
**Theorem 3.10.** Let $\mathcal{P}_\alpha$ be the class of all distributions on $\mathbb{R}_+$ such that

$$ \alpha(P) = \alpha, G_P(\tau_*(P)) \geq \frac{0.28}{\alpha} \text{ and } \tau_*(P) \leq \frac{1}{\alpha}, $$

where $G_P$ denotes the function

$$ x \mapsto \int_{0}^{+\infty} \min(x, t) dP(t). $$

For any policy $S$, any $T > 0$ and any integer $n \geq 1$, there exists some distribution $P \in \mathcal{P}_\alpha$ such that the expected reward of $S$ on an $n$-sample from $P$ is at most

$$ \alpha T - 0.003\sqrt{\alpha T}. $$

Moreover, for any $T > 0$ and $n \in \mathbb{N}$ such that

$$ n \geq 3.6\alpha T + 3.8\sqrt{\alpha T \log(\alpha T)} + 3\log(\alpha T), $$

the minimax regret is at least

$$ \sup_{P \in \mathcal{P}_\alpha} R_{n,T}^{\text{bgt}}(P, S) \geq 0.003\sqrt{V_n(P, T)} - 3. \quad (27) $$

If $n \geq 3.6\alpha T$, the policy given by Definition 3.7 satisfies equation (26) of Theorem 3.9. It follows from Theorem 3.10 above that for such $n, T$, policy 3.7 is minimax optimal up to a logarithmic term. For smaller $n$, the upper bound on the reward given by Theorem 3.10 is still valid, but it may not be sharp since the gap between the optimal reward $V_n(P, T)$ and its upper bound $\alpha T$ may be larger than $\sqrt{\alpha T}$. It is because of this issue that the minimax lower bound on the regret (equation (27)) is stated only under the assumption that $n$ is large enough: this allows to compare $V_n(P, T)$ with $\alpha T$ using Proposition 2.5.

The proof of Theorem 3.10 (which can be found in section E) gives some indication on the nature of the worst-case distributions for problem (3). They arise as small perturbations of the exponential distribution with parameter $\alpha$. Exponential distributions yield a constant ratio $\frac{F}{G}$ - hence, the location of $\tau_*(P)$, the argmax of $\frac{F}{G}$, is particularly unstable to small perturbations around these particular distributions. Thus, strategies can fail to concentrate around $\tau_*(P)$, and this failure of localization results in a regret of square-root order. The fact that this rate is expressed as a function of the reward rather than $n$ is where problem (3) differs from problem (1). This phenomenon is due to the knapsack constraint and is also observed in the finitely armed bandits with knapsacks setting [2]. The knapsack constraint limits the number of observations so that the "effective sample size" becomes proportional to the reward; in our case, the number of uncensored observations. For a precise information-theoretic statement, see Proposition E.1 in the appendix.
## 4 Exact, adaptive confidence bands for the distribution function

Following ideas from the literature on goodness of fit testing [4, 13, 14], we define tight confidence bands for the distribution function based on Beta quantiles. We slightly modify the approach in order to obtain bounds that are valid uniformly in the sample size $j$, for $j \le n$. Let us first describe the shape of the confidence band, before explaining how to calibrate its width in order to achieve exact coverage.

For any $\alpha, \beta \in (0; +\infty)$ and any $\lambda \in (0; 1)$, let $q_\lambda(\alpha, \beta)$ denote the $\lambda$-quantile of the Beta distribution $B(\alpha, \beta)$.

**Definition 4.1.** Fix an integer $n$. For all $j \in \{1, \dots, n-1\}$ and all $\eta \in (0; 1)$, let $w_{j,\eta}^{-}$, $w_{j,\eta}^{+}$ be defined by

$$w_{j,\eta}^{-}(u) = q_{\lambda_n(\eta)}(ju, j(1-u) + 1), \quad w_{j,\eta}^{+}(u) = q_{1-\lambda_n(\eta)}(ju + 1, j(1-u))$$

for all $u \in [0; 1]$ and some $\lambda_n(\eta)$ to be defined later. Let then $\tilde{F}_{n,\eta}^{-}$, $\tilde{F}_{n,\eta}^{+}$: $\bigcup_{k \in \mathbb{N}} \mathbb{R}^k \to [0; 1]^\mathbb{R}$ be defined by

$$\tilde{F}_{n,\eta}^{\pm} : (x_1, \dots, x_j) \mapsto w_{j,\eta}^{\pm} \circ \tilde{F}(x_1, \dots, x_j).$$

$\lambda_n(\eta)$ is defined to be such that equation (12) holds with equality for i.i.d uniform $(X_i)_{1 \le i \le n}$.

This definition is based on the fact that for any continuous distribution $P$ with cdf $F$, $F(X_{i:j})$ follows the Beta distribution $B(i, j - i + 1)$ distribution, where $X_{i:j}$ denotes the order statistic of an i.i.d sample of size $j$ from $P$. $\lambda_n(\eta)$ is a fixed function of the sample size $n$ and the confidence level $\eta$; it can be estimated through Monte-Carlo simulations. For theoretical purposes, we shall only use the following bound.

**Lemma 4.2.** For any $n \ge 1$ and any $\eta \in (0; 1)$, $\lambda_n(\eta) \ge \frac{\eta}{n(n-1)}$.

Though $\lambda_n(\eta)$ is calculated only for the uniform distribution, the confidence band given by Definition 4.1 is universally valid in the sense that it satisfies equation (12) for any i.i.d sample.

**Proposition 4.3.** For $\tilde{F}_{n,\eta}^{-}$, $\tilde{F}_{n,\eta}^{+}$ given by Definition 4.1,

$$\mathbb{P} \left( \exists j \in \{1, \dots, n-1\} : F \notin [\tilde{F}_{n,\eta}^{-}(X_1, \dots, X_j); \tilde{F}_{n,\eta}^{+}(X_1, \dots, X_j)] \right) \le \eta$$

for any i.i.d sample $X_1, \dots, X_n$ with cdf $F$. Moreover, the above bounds hold with equality when $F$ is continuous.

The functions $w_{j,\eta}^{-}$, $w_{j,\eta}^{+}$ are non-explicit since they depend on the Beta quantiles $q_\lambda(\alpha, \beta)$ which cannot be expressed in closed-form. To carry-out the proofs of Theorems 3.3 and 3.9, we need to upper bound $w_{j,\eta}^{+}$ and lower bound $w_{j,\eta}^{-}$.
The following proposition compares the confidence band from Definition 4.1 with confidence bands of Hoeffding and Bernstein type, which are easier to work with mathematically.

**Proposition 4.4.** Fix some $\eta \in (0; \frac{1}{2}]$ and let $y = 2 \log n - \log \eta$. For all $j \in \{1, \dots, n\}$ and all $u \in [0; 1]$,

$$u \le w_{j,\eta}^{+}(u) \le u + \sqrt{\frac{2y}{j}} \sqrt{u(1-u)} + (1-2u)_{+} \frac{4y}{3j} \quad (28)$$

$$u \ge w_{j,\eta}^{-}(u) \ge u - \sqrt{\frac{2y}{j}} \sqrt{u(1-u)} - (1-2u)_{-} \frac{4y}{3j}. \quad (29)$$

Moreover, for all $j \in \{1, \dots, n\}$ and all $u \in [0; 1]$,

$$w_{j,\eta}^{+}(u) \le u + \sqrt{\frac{y}{2j}} \quad (30)$$

$$w_{j,\eta}^{-}(u) \ge u - \sqrt{\frac{y}{2j}}. \quad (31)$$

The proof of proposition 4.4 is based on estimates of Beta quantiles due to Henzi et al. [16]. It can be found in section B.2. A direct use of proposition 4.4 leads to bounds of $f \in [w_{j,\eta}^{-} \circ f_0; w_{j,\eta}^{+} \circ f_0]$ expressed in terms of $f_0$. In practice, it is often more interesting to bound $f$ by some other $f_1 \in [w_{j,\eta}^{-} \circ f_0; w_{j,\eta}^{+} \circ f_0]$, such as the theoretical distribution function $F$. The following lemma provides such a bound.

**Lemma 4.5.** Let $f, f_1$ belong to $[w_{m,\eta}^{-} \circ f_0; w_{m,\eta}^{+} \circ f_0]$ for some function $f_0: \mathbb{R}_{+} \to [0; 1]$ and some integer $m \in \{1, \dots, n-1\}$. Let $z = 2 \log n - \log \eta$, then

$$f \ge f_1 - 2\sqrt{\frac{2z}{m}}\sqrt{f_1} - \frac{4z}{3m}$$

Moreover,

$$f_1 \le f + 2\sqrt{\frac{2z}{m}}\sqrt{1-f} + \frac{9z}{m}.$$

In addition to the cumulative distribution function $F$, the function $G: t \mapsto \int_{0}^{t}(1-F(s))ds$ plays a key role in problems (1) and (3). By monotony of the functional which maps $F$ to $G$, a confidence band on $F$ yields a confidence band on $G$, but the precision of the bounds depends on the point $t \in \mathbb{R}$. In the proposed strategies solving problems (1) and (3), deadlines $\tau$ are chosen so as to maximize $f - cg$ in problem (1) and $f/g$ in problem (3), for some $f$ in the confidence band and $g: t \mapsto \int_{0}^{t}(1-f(s))ds$. This leads to the property

$$r(g(\tau) - g(t)) \le 1 - f(t) \quad \text{for all } t \in [0; \tau], \quad (32)$$

where $r = c$ in problem (1) and $r = \frac{1}{g(\tau)}$ in problem (3). The following proposition shows that our confidence bands are tight around such points.
**Proposition 4.6.** Let $f_0 : [0; +\infty) \to [0; 1]$ be a measurable function and $g_0 : t \mapsto \int_0^t (1 - f_0(s))ds$ on $\mathbb{R}_+$. Let $m : \mathbb{R}_+ \to \mathbb{N}$ be a non-increasing function. Let

$$f \in [w_{m,\eta}^{-} \circ f_0; w_{m,\eta}^{+} \circ f_0] \quad \text{and} \quad g : t \mapsto \int_{0}^{t} (1 - f(s))ds,$$

where by definition,

$$w_{m,\eta}^{\pm} \circ f_0 : t \mapsto w_{m(t),\eta}^{\pm}(f_0(t)).$$

Let $y = 2 \log n - \log \eta$. If $t \ge 0$ is such that for all $s \le t$,

$$r(g(t) - \rho g(s)) \le 1 - f(s) + \delta, \quad (33)$$

for some $\rho \ge 1, r > 0$ and $\delta \ge 0$, then for any $f_1 \in [w_{m,\eta}^{-} \circ f_0; w_{m,\eta}^{+} \circ f_0]$

$$g_1(t) \le g_0(t) + 3\sqrt{\frac{yg(t)}{rm(t)}} + \frac{3t}{4}\sqrt{\frac{\delta y}{m(t)}} + \sqrt{2.3y\left(1 - \frac{1}{\rho}\right)}\sqrt{\frac{tg(t)}{m(t)}} + 5\frac{yt}{m(t)}$$

and

$$g_1(t) \ge g_0(t) - 3\sqrt{\frac{yg(t)}{rm(t)}} - \frac{3t}{4}\sqrt{\frac{\delta y}{m(t)}} - \sqrt{2.3y\left(1 - \frac{1}{\rho}\right)}\sqrt{\frac{tg(t)}{m(t)}} - 5\frac{yt}{m(t)},$$

where $g_1 : t \mapsto \int_0^t (1 - f_1(s))ds$.

Note that the above bound is wholly deterministic. On the event that $F$ belongs to the confidence band, proposition 4.6 may be applied to show that $G$ is well approximated by the functions of the form $g_2$, for any $f_2$ in the confidence band. Proposition 4.6 also treats the case where equation (32) holds only approximately, such as when $t$ is an approximate maximizer of $f - cg$ (in problem (1)) or $f/g$ (in problem (3)) for some $f \in [f_1; f_u]$. The bound depends continuously on the approximation errors $\delta, \rho - 1$.

# 5 Algorithms

For conceptual clarity and to convey the intuition behind our estimators, we first defined them as solutions to certain optimization problems over *confidence bands* of the form $[f_1; f_u]$, for two piecewise constant functions from $\mathbb{R}_+$ to $[0; 1]$, with $O(n)$ constant pieces. These definitions do not make clear whether, or how fast, solutions to these problems can be computed. This question is particularly important when the resource $T$ is time, since the time spent to compute $\hat{\tau}$ will then have to be deducted from the budget $T$. The purpose of this section is to describe reasonably fast algorithms solving these optimization problems.

Our approach is to construct algorithms "testing" for the inequality $\hat{\tau} \ge \tau$, where $\hat{\tau}$ is the estimator to be computed and $\tau$ is some non-negative real. $\hat{\tau}$ can then be approximated to the desired precision by dichotomy, using a logarithmic number of tests. Since our tests have linear complexity, the computation
at step j takes "time" $O(j \log n)$, and the whole policy can be computed in complexity $O(n^2 \log n)$. Comparisons on a computer can only be made up to a finite precision $\delta$. To address this issue, we introduce the following notation for a "$\delta$-accurate comparison".

**Definition 5.1.** Let $<_{\delta}^{a}, <_{\delta}^{g}$ satisfy the following properties

* Correctness: $x <_{\delta}^{a} y \implies x < y$ and $x <_{\delta}^{g} y \implies x < y$

* Precision: $(1 + \delta)x \le y \implies x <_{\delta}^{g} y$ and $x + \delta \le y \implies x <_{\delta}^{a} y$.

Otherwise $<_{\delta}^{a}, <_{\delta}^{g}$ are non-deterministic i.e can yield different values for the same pair $x, y$.

This represents the result of a comparison between approximations of $x, y$ obtained in some arbitrary manner (hence the non-determinism). We assume that piecewise constant functions $f$ are represented digitally by vectors $x, y$, where $x$ is a sorted vector collecting the breakpoints (discontinuities of $f$) and $y$ collects the values of $f$ at and between the breakpoints. This allows many operations on such $f$s to be performed efficiently. Pointwise binary operations such as the sum or maximum can be performed in linear time relative to the size of $x, y$. A piecewise affine representation of $g: t \mapsto \int_{0}^{t} (1 - f(s))ds$ - with the same breakpoints as $f$ - can be computed in linear time. Moreover, $f_l, f_g$ can be replaced by

$$t \mapsto \sup_{s \le t} f_l(s) \text{ and } t \mapsto \inf_{s \ge t} f_l(s)$$

- which can also be computed in linear time - without changing the set $[f_l; f_u]$. Thus, in the following, we assume without loss of generality that $f_l, f_u$ are non-decreasing. A representation of $\hat{F}_j^-$, $\hat{F}_j^+$ given by equations (19) and (20) can be computed in linear time at each time step $j$ by inserting the new break-points $\hat{\tau}_j$ and $\min(X_j, \hat{\tau}_j)$ in the sorted list of past break-points representing

$$\hat{F}_{n,\eta}^{\pm}((X_i)_{i \in \mathcal{I}(k_j, j-1,0)}),$$

updating the frequencies accordingly and taking the pointwise maximum/minimum with $\hat{F}_{j-1}^{\pm}$.

The rest of this section focuses on the "difficult part", which is the computation of $\hat{\tau}_j$ from a piecewise constant representation of $f_l = \hat{F}_j^-$ and $f_u = \hat{F}_j^+$. Where exact computations are impossible (using standard functions), we analyze suitable approximate versions of the ideal (infinite precision) algorithms. Let us first introduce some notation. Given a confidence band $[f_l; f_u]$, we let

$$g_l : t \mapsto \int_0^t (1 - g_u(s))ds$$

$$g_u : t \mapsto \int_0^t (1 - g_l(s))ds$$

which provide upper and lower confidence bands on $G$. The following differential equation plays a crucial role.
**Definition 5.2.** For any positive reals $t, \alpha, \lambda$, let $\psi_t(\alpha, \lambda, \cdot)$ be the solution on $[0; t]$ of the following initial value problem:

$$ \psi_t(\alpha, \lambda, 0) = 0 \quad \text{and} \quad \frac{d}{ds} \psi_t(\alpha, \lambda, s) = \max(1 - f_u(t-s), 1 - \lambda + \alpha \psi_t(\alpha, \lambda, s)), \quad (34) $$

in the sense that $\psi_t(\alpha, \lambda, \cdot)$ is absolutely continuous, satisfies the initial condition and is such that the differential equation holds almost everywhere on $[0; t]$.

The right-hand side of equation (34) satisfies the conditions of [15, Theorem 5.3] and so $\psi_t(\alpha, \lambda, \cdot)$ is uniquely defined. Moreover, $\psi_t(\alpha, \lambda, \cdot)$ can be computed inductively in linear time and can be represented exactly as a continuous and piecewise differentiable function made of affine and exponential pieces.

## 5.1 Algorithms to compute $\hat{\tau}_j$ from Definition 3.1

The problem consists in computing

$$ \hat{\tau}_{\max}(c, \tau_M) = \sup_{f \in [f_l; f_u]} \sup_{t \in [0; \tau_M]} \operatorname{argmax} \left\{ f(t) - c \int_0^t (1 - f(s)) ds \right\}, $$

given two non-decreasing, piecewise constant functions $f_l, f_u$ with at most $m$ constant pieces. From a numerical point of view, this definition is problematic since the $\sup \operatorname{argmax}$ is very sensitive to small perturbations of $f$ (for example if the global maximum of $f$ is reached at two points $x < y$). However, what is important is matching the characteristic properties of $\hat{\tau}_c$ to (arbitrary) precision $\delta$ and this does turn out to be possible. More precisely, we shall construct an upper bound $\hat{\tau}_{c, \delta} \ge \hat{\tau}_c$ which is an approximate maximum of $f - cg$ for some $f \in [f_l; f_u]$. Let us introduce the following function.

$$ W_u(t, \tau_M) = \sup_{s \in [t; \tau_M]} \left\{ f_u(t) - c \int_{\tau}^{t} (1 - f_u(s)) ds \right\}. \quad (35) $$

Since $f_u$ is piecewise constant, the supremum in equation (35) can be replaced by a maximum over the finite set containing $t$ and the break-points of $f_u$ which belong to $(t; \hat{\tau}_M]$. $W_u(t, \tau_M)$ can therefore be computed in linear time. The following function will be used to test for the location of $\hat{\tau}_{c, \delta}$ in binary search.

**Definition 5.3.** For any $\eta \ge 0$ and $t \in (0, \tau_M]$, let

$$ \hat{r}_c(t, \tau_M) = W_u(t, \tau_M) - \sup_{s \in (0; t)} \left\{ c\psi_{\tau}(c, W_u(t, \tau_M), s) + \tilde{f}_l(t-s) \right\}, $$

where $\tilde{f}_l$ denotes the left-continuous version of $f_l$,

$$ \tilde{f}_l : t \mapsto \sup_{s<t} \{f_l(s)\}. $$
Since $\tilde{f}_l$ is piecewise constant and $\psi_\tau$ is non-decreasing in its third variable (by Definition 5.2), the supremum in the definition of $\hat{r}_c(\tau)$ is in fact a maximum over at most $m+1$ points (where $m$ is the number of break-points of $f_l$), which can be computed in time $O(m)$. Algorithm 5.1 uses the finite-precision test $0 < \frac{\delta}{\hat{r}_c(\tau)}$ to conduct a binary search for $\hat{\tau}_c$. When the finite precision test fails

<caption>**Algorithm 1** UCST for problem (1)</caption>

**Require:** $f_l, f_u, c, \delta, \tau_M$, break-points $x_1, \dots, x_m$ of $f_u$
$\varepsilon \leftarrow \frac{\delta}{c}$
$\hat{t}_L \leftarrow 0$
$\hat{t}_U \leftarrow \tau_M$
**if** $\hat{r}_c(\hat{t}_U, \tau_M) < \frac{\delta}{c}$ **then**
**while** $\hat{t}_L + \varepsilon < \frac{\delta}{c} \hat{t}_U$ **do**
$\hat{t}_m \leftarrow \frac{\hat{t}_L + \hat{t}_U}{2}$
**if** $\hat{r}_c(\hat{t}_m, \tau_M) < \frac{\delta}{c}$ **then**
$\hat{t}_U \leftarrow \hat{t}_m$
**else**
$\hat{t}_L \leftarrow \hat{t}_m$
**end if**
**end while**
**end if**
$\hat{\tau}_{c, \delta} \leftarrow \varepsilon + \min \operatorname{argmax} \{ \tilde{f}_u(t) - cg_l(t) : t \in \{\hat{t}_U\} \cup \{x_i : \hat{t}_U < x_i \le \tau_M\} \}$
**return** $\hat{\tau}_{c, \delta}$

to give a definitive answer, Algorithm 5.1 chooses the larger interval in order to guarantee an upper bound on $\hat{\tau}_c$. By construction, Algorithm 5.1 terminates in at most $O(\log(c\tau_M/\delta))$ iterations, each of which has linear complexity. Therefore 3.3 suggests taking $\tau_1 \le \frac{\sqrt{n}}{c}$ in definition 3.1, which yields $c\tau_M \le \sqrt{n}$ and hence a number of iterations of order $\log(n/\delta)$. Proposition 5.4 shows that this yields an optimization accuracy of order $\delta$.

**Proposition 5.4.** $\hat{\tau}_{c,\delta}$ computed by algorithm 5.1 is such that

$$ \tau_M \ge \hat{\tau}_{c,\delta} \ge \hat{\tau}_{\max}(c, \tau_M) $$

and moreover, there exists $f \in [f_l; f_u]$ such that

$$ f(\hat{\tau}_{c,\delta}) - cg(\hat{\tau}_{c,\delta}) \ge \sup_{t \in [0; \tau_M]} \{f(t) - cg(t)\} - 3\delta $$

where as usual, $g : t \mapsto \int_0^t (1 - f(s))ds$.

The characteristic property of $t = \hat{\tau}_{\max}(c, \tau_M)$ is that it optimizes $f - cg$ over $[0; \tau_M]$ for some $f$ in the confidence band and is the maximal such $t$. In comparison, $\hat{\tau}_{c,\delta}$ is a $\delta$-approximate optimum of $f - cg$ for some $f$ in the confidence band that upper bounds all the exact optima. This is sufficient for statistical purposes when $\delta$ is small enough (for example, of order $\frac{1}{n}$).
## 5.2 Algorithm to compute $\hat{\tau}_j$ from equation (24)

The goal is to compute

$$ \hat{\tau}_{\max}(\tau_M) = \sup_{f \in [f_l; f_u]} \sup_{t \in (0; \tau_M]} \left\{ \frac{f(t)}{\int_0^t (1-f(s))ds} \right\}. $$

The same remarks apply as in the previous sub-section and we shall content ourselves with an upper-bound on $\hat{\tau}_{\max}(\tau_M)$ that is an approximate maximizer of $\frac{f}{g}$ for some $f \in [f_l; f_u]$. To decide whether $\hat{\tau}_{\max}(\tau_M) \ge t$ for some test point $t \le \tau_M$, we rely on the sufficient condition

$$ \sup \operatorname{argmax} \phi \ge t \implies \sup_{s<t} \phi(s) \le \sup_{s \ge t} \phi(s). $$

To verify this for some $f$ in the confidence band, the left-hand side should be as small as possible and the right-hand side should be as large as possible, which leads to the following definition.

**Definition 5.5.** For any non-negative $\tau$, $y$ and any $t \in [0; \tau]$, let

$$ \hat{\alpha}_{\tau}^{+}(t, y) = \sup_{s \in [t; \tau]} \left\{ \frac{f_u(s)}{y + g_l(s) - g_l(t)} \right\}. \quad (36) $$

Let also

$$ \hat{\alpha}_{t}^{-} = \sup_{s<t} \frac{f_{l}(s)}{g_{u}(s)} \quad (37) $$

Since $f_u$ is piecewise constant, $g_u$ is piecewise affine on the same partition and therefore the supremum in equation (36) is in reality a maximum over the break-points of $f_u$, involving the values of the right-limit of $f_u$ at the break points. This can be computed in linear time given the representation described in previously. The same argument applies to the supremum in equation (37).

$\hat{\alpha}_{\tau}^{+}(t, y)$ is clearly a non-increasing function of $y$, so to favour a larger optimum, $y$ should be as small as possible. The lower bound on $y$ is given by the following definition.

**Definition 5.6.** For any positive $\alpha, t$, let $y_{\min}(\alpha, t)$ be the smallest $y \ge 0$ such that

$$ \psi_t(\alpha, \alpha y, t) \le y \quad (38) $$

and

$$ \max(1 - f_u(t - s), 1 - \alpha y + \alpha \psi_t(\alpha, \alpha y, s)) \le 1 - f_l(t - s) \quad (39) $$

for almost all $s \in [0; t]$.

By Definition 5.2, $\psi_t(\alpha, \alpha y, s)$ is obviously non-increasing in $y$. It follows that $y_{\min}(\alpha, t)$ is well-defined and that equations (38) and (39) are satisfied if and only if $y \ge y_{\min}(\alpha, t)$. Equations (38) and (39) can be checked by integrating equation (34) defining $\psi_t(\alpha, \alpha y, \cdot)$, which can be done in linear time (note that
equation (39) being valid for almost all s is equivalent to it being valid with $f_l$ replaced by its left-continuous version, which is piecewise-constant on the same partition). Thus, $y_{\min}(\alpha, t)$ can be computed by binary search. To initialize this binary search, upper and lower bounds on $y_{\min}(\alpha, t)$ are required. The following lemma deals with the case $\alpha = \hat{\alpha}_t^-$ which is of interest in this section.

**Lemma 5.7.** For any $t \ge 0$,

$$ (1 - e^{-1}) \min \left( t, \frac{1}{\hat{\alpha}_t^-} \right) \le y_{\min} (\hat{\alpha}_t^-, t) \le g_u(t). $$

Under the assumptions of section 3.2, the upper and lower bounds differ by a factor of at most $\hat{\alpha}_t^- t \le \alpha_* T \le n$ on the "clean event" of lemma 3.8. It follows that a binary search with at most

$$ \mathcal{O}(\log_2 \log n - \log_2(1 + \delta)) $$

steps yields $y_{\min}(\hat{\alpha}_t^-, t)$ up to a factor $1 + \delta$, on the event of lemma 3.8. The definition of $y_{\min}$ is justified by the following key property.

**Claim 5.7.1.** Let $y \in [0; g_u(t)]$ and $\alpha \ge \hat{\alpha}_t^-$. Then $y \ge y_{\min}(\alpha, t)$ if and only if there exists $f \in [f_l; f_u]$ such that

$$ g(t) = y \quad \text{and} \quad \sup_{s \in (0; t)} \frac{f(s)}{g(s)} \le \alpha, $$

where as usual, $g$ denotes the function $s \mapsto \int_0^s (1 - f(x))dx$.

The following Proposition essentially yields a linear-time test for the inequality $\hat{\tau}_{\max}(\tau_M) \ge t$.

**Proposition 5.8.** For any $t \in (0; \tau]$,

$$ \hat{\rho}_{\tau}(t) = \frac{\hat{\alpha}_{\tau}^{+}(t, y_{\min}(\hat{\alpha}_{t}^{-}, t))}{\hat{\alpha}_{t}^{-}} $$

is the smallest constant $\rho \ge 0$ such that for all $f \in [f_l; f_u]$,

$$ \sup_{s \in [t; \tau]} \left\{ \frac{f(s)}{g(s)} \right\} \le \rho \sup_{s < t} \left\{ \frac{f(s)}{g(s)} \right\}, $$

and equality is attained in this equation for some $f \in [f_l; f_u]$. In particular, if $\hat{\rho}_{\tau}(t) < 1$, then $\hat{\tau}_{\max}(\tau) \le t$ and if $\hat{\rho}_{\tau}(t) > 1$, then $\hat{\tau}_{\max}(\tau) \ge t$.

Algorithm 5.2 computes an approximation to $\hat{\tau}_{\max}(\tau_M)$ using binary search.

If $\hat{\tau}_{\max}(\tau_M) \ge \frac{\tau_M}{2}$ (which is the case in Definition 3.7), algorithm 5.2 terminates in at most $\mathcal{O}(|\log \delta|)$ iterations. The output of algorithm 5.2 with a finite precision $\delta > 0$ satisfies the following properties, which are analogous to those of $\hat{\tau}_{\max}(\tau_M)$ in the (theoretical) infinite precision setting.
**Algorithm 2** UCST for problem (3)

**Require:** $f_l, f_u, \tau = \tau_M$, break-points $x_1, \dots, x_m$ of $f_u$

$\hat{t}_L \leftarrow 0, \hat{t}_U \leftarrow \tau$

if $\neg((1 + \delta)\hat{\rho}_{\tau}(\tau) < g_{\delta}^g 1)$ then

$\hat{t}_L \leftarrow \tau$

end if

while $(1 + \delta)\hat{t}_L < g_{\delta}^g \hat{t}_U$ do

$\hat{t}_m \leftarrow \frac{\hat{t}_L + \hat{t}_U}{2}$

if $(1 + \delta)\hat{\rho}_{\tau}(\hat{t}_m) < g_{\delta}^g 1$ then

$\hat{t}_U \leftarrow \hat{t}_m$

else

$\hat{t}_L \leftarrow \hat{t}_m$

end if

end while

$\hat{\tau}_{\delta} \leftarrow (1 + \delta)^2 \min \arg\max \left\{ \frac{\hat{f}_u(t)}{g(\hat{t}_L) + g_l(t) - g_l(\hat{t}_L)} : t \in \{\hat{t}_L\} \cup \{x_i : \hat{t}_L < x_i \le \tau\} \right\}$

return $\hat{\tau}_{\delta}$

**Proposition 5.9.** The output $\hat{\tau}_{\delta}$ of algorithm 5.2 satisfies the following properties.

* For every $f \in [f_l; f_u]$, $g : t \mapsto \int_0^t (1 - f(s))ds$ and $t > 0$,

$$ \frac{f(t)}{g(t)} \ge \frac{1}{1 + \delta} \sup_{s \in (0; \tau_M]} \left\{ \frac{f(s)}{g(s)} \right\} \implies t \le \hat{\tau}_{\delta}. $$

In particular, $\hat{\tau}_{\max}(\tau_M) \le \hat{\tau}_{\delta}$.

* There exists some $f \in [f_l; f_u]$ such that

$$ \frac{f(\hat{\tau}_{\delta})}{g(\hat{\tau}_{\delta})} \ge \frac{1}{(1 + \delta)^4} \sup_{t \in (0; \tau_M]} \left\{ \frac{f(t)}{g(t)} \right\} $$

where as always, $g : t \mapsto \int_0^t (1 - f(s))ds$.

For small enough $\delta > 0$, the second property shows that $\hat{\tau}_{\delta}$ is near-optimal, up to the uncertainty represented by the confidence band. This allows the application of Proposition 4.6 to $t = \hat{\tau}_{\delta}$, with $r = \frac{1}{g(t)}$ and $\rho = (1 + \delta)$. The second property allows the iterative construction of a non-increasing sequence of near-optimal stopping times, by replacing $\tau_M$ by $\hat{\tau}_{\delta}$ and updating $f_l, f_u$ at each iteration.

## 5.3 Algorithm to compute $\tau_j^*$ from Definition 3.6

Definition 3.6 is convenient for conceptual understanding and statistical analysis, but it is not very stable: if $\frac{f}{g}$ has two global maxima $\tau_1 < \tau_2$ then an
arbitrary small perturbation can shift the argmax from $\tau_2$ to $\tau_1$, potentially violating the constraint

$$g\left(\sup \operatorname{argmax}\left\{\frac{f}{g}\right\}\right) \geq \frac{T}{n}.$$

To deal with the issue of finite numerical precision, we shall introduce a suitable notion of "approximate UCB" which recovers the same bounds as those of Theorem 3.9 when the precision parameter, $\delta$, tends to 0. Let us start with the following Definition.

**Definition 5.10.** Let $\mathbb{H} = \mathbb{H}(f_l, f_u)$ be the set of all pairs $(f,g)$ where $f \in [f_l; f_u]$, $g: t \mapsto \int_0^t (1-f(s))ds$ and

$$\sup_{t: g(t) \geq \frac{T}{n}} \left\{ \frac{f(t)}{g(t)} \right\} \geq \sup_{t: g(t) < \frac{T}{n}} \left\{ \frac{f(t)}{g(t)} \right\}.$$

This is analogous to definition 3.5 but allows the supremum not to be attained, including cases where the argmax is empty. Hence, the set $\mathbb{H}(f_l, f_u)$ includes the set corresponding to definition 3.5. The first goal of this section is to compute

$$\hat{\alpha}_u = \sup_{(f,g) \in \mathbb{H}} \sup_{t>0} \left\{ \frac{f(t)}{g(t)} \right\}. \qquad (40)$$

To give a more explicit characterization of $\hat{\alpha}_u$, let us introduce the following functions.

**Definition 5.11.** For any $t > 0$, let

$$\hat{\alpha}_{+}(t) = \hat{\alpha}_{\infty}^{+}\left(t, \frac{T}{n}\right) = \sup_{s \ge t} \left\{ \frac{f_{u}(s)}{\frac{T}{n} + g_{l}(s) - g_{l}(t)} \right\}.$$

Let also

$$\tau_{id}(t) = \min \operatorname{argmax}_{s \ge t} \left\{ \frac{\tilde{f}_u(s)}{\frac{T}{n} + g_l(s) - g_l(t)} \right\}, \qquad (41)$$

where $\tilde{f}_u$ is the right-continuous version of $f_u$.

If $f_u$ is piecewise constant with $m$ break-points, then $\hat{\alpha}_+(t)$ and $\tau_{id}(t)$ can be computed in time $O(m)$ using the fact that

$$s \mapsto \frac{\tilde{f}_u(s)}{\frac{T}{n} + g_l(s) - g_l(t)}$$

is non-increasing between two break-points (since $\tilde{f}_u$ is constant on these intervals). It follows that the maximum in equation (41) is attained at one of the break-points, or at the point $t$. The point of this is that $\hat{\alpha}_u$ can be expressed as $\hat{\alpha}_+(t_*)$ for some $t_*$ which can be characterized using the function $y_{\min}$ introduced in definition 5.6.
**Proposition 5.12.** There exists $t_* \in [0; +\infty]$ such that

$$ \{t \ge 0 : y_{\min}(\hat{\alpha}_+(t), t) \le \frac{T}{n}\} = [0; t_*]. $$

Moreover, if $f_u = 1$ on $[T; +\infty)$, then $t_* = +\infty$ if and only if $t_* \ge T$.

Assuming infinite precision, $t_*$ can be calculated by dichotomy, using the fact that $t \le t_*$ if and only if $y_{\min}(\hat{\alpha}_+(t), t) \le \frac{T}{n}$ which is in turn equivalent to $\psi_t(\hat{\alpha}_+(t), \hat{\alpha}_+(t)\frac{T}{n}, \cdot)$ satisfying the two properties of definition 5.6. This can be checked in linear time by integrating the differential equation defining $\psi_t$ (Definition 5.2). The complications related to finite numerical precision will be dealt with later. First, let us state the following proposition.

**Proposition 5.13.** $\mathbb{H}$ is non-empty if and only if $g_u(t_*) \ge \frac{T}{n}$ and

$$ \hat{\alpha}_+(t_*) \ge \sup_{t>0} \left\{ \frac{f_l(t)}{g_u(t)} \right\} = \hat{\alpha}_-. $$

In that case, $\hat{\alpha}_u = \hat{\alpha}_+(t_*)$. If $t_* < +\infty$, the supremum in equation (40) is attained for some $(f, g) \in \mathbb{H}$ such that $f = f_u$ on $[t_*; +\infty)$.

Proposition 5.13 gives an explicit formula for $\hat{\alpha}_u$ and solves also the questions of existence ($\mathbb{H} \ne \emptyset$) and attainment of the supremum on $\mathbb{H}$ in equation (40). The supremum is not necessarily attained as a function of $t$ unless $f_u$ is right-continuous. However, if $t_*$ is known, then an approximate maximizer can be constructed very simply, as the following Corollary shows.

**Corollary 5.14.** Let

$$ \tau_{\delta} = (1 + \delta)\tau_{id}(t_{*}). $$

Then there exists $(f, g) \in \mathbb{H}$ such that

$$ \frac{f(\tau_{\delta})}{g(\tau_{\delta})} \ge \frac{\hat{\alpha}_u}{1 + \delta}. $$

*Proof.* Let $(f, g) \in \mathbb{H}$ be as in proposition 5.13. The $f = f_u$ on $[t_*; +\infty)$ and
$g(t_*) = \frac{T}{n}$, so

$$
\begin{align*}
\frac{f(\tau_\delta)}{g(\tau_\delta)} &= \frac{f_u(\tau_\delta)}{g(\tau_\delta)} \\
&\ge \frac{\tilde{f}_u(\tau_{id}(t_*))}{g(\tau_\delta)} \\
&\ge \frac{1}{1+\delta} \frac{\tilde{f}_u(\tau_{id}(t_*))}{g(\tau_{id}(t_*))} \\
&= \frac{1}{1+\delta} \frac{\tilde{f}_u(\tau_{id}(t_*))}{\frac{T}{n} + g_l(\tau_{id}(t_*)) - g_l(t_*)} \\
&\ge \frac{1}{1+\delta} \sup_{t \ge t_*} \left\{ \frac{\tilde{f}_u(t)}{\frac{T}{n} + g_l(t) - g_l(t_*)} \right\} \\
&\ge \frac{\hat{\alpha}_+(t_*)}{1+\delta} \\
&= \frac{\hat{\alpha}_u}{1+\delta}
\end{align*}
$$

by proposition 5.13.

<figure><img src="image_2.png" /></figure>

In practice, $t_*$ cannot be calculated exactly because a binary search only takes a finite number of steps. Moreover, the comparisons used in binary search have limited numerical precision. Algorithm 5.3 below formalizes, in pseudocode, a "true" algorithm to compute $\hat{\alpha}_u, \tau_*$ using finite precision arithmetic and with a bounded time complexity.

Since $\hat{t}_L, \hat{t}_U$ are initialized such that $\hat{t}_U \le n\hat{t}_L$, the main loop in algorithm 5.3 runs at most

$$[\log_2 \log n - \log_2 \log(1 + \delta)]$$

times. Each evaluation of the loop conditional requires calculating $\hat{\alpha}_+(t)$ (which can be done in linear time) and testing whether $y_{\min}(\hat{\alpha}_+(t), t) \le \frac{T}{n}$ - which can be done in linear time by integrating the differential equation defining $\psi_t(\alpha, \alpha \frac{T}{n}, \cdot)$ (Definition 5.2) and checking the conditions of definition 5.6. As we shall see below, a polynomial precision ($\delta = O(\frac{1}{n^k})$) is enough for statistical purposes. Thus, the whole computation takes time at most $O(n \log n)$.

The following Proposition details in what sense Algorithm 5.3 provides an approximate solution to the optimization problem defining $\hat{\alpha}_u$ (equation (40)).

**Proposition 5.15.** Assume that $f_u = 1$ on $[T; +\infty)$. Let $\hat{\alpha}_{u,\delta}, \hat{\tau}_\delta$ be the output of Algorithm 5.3, assuming that no exception is thrown. If $\mathbb{H} \ne \emptyset$, then Algorithm 5.3 terminates without throwing an exception and yields $\hat{\alpha}_{u,\delta} \ge \hat{\alpha}_u$. Assume now that no exception is thrown (but $\mathbb{H}$ may be empty). If $t_* \ge T$, then $\hat{\tau}_\delta \ge T$, otherwise there exists $f \in [f_t; f_u]$ such that

$$g(\hat{\tau}_{\delta}) \ge \frac{T}{(1+\delta)^3 n} \quad \text{and} \quad \frac{f(\hat{\tau}_{\delta})}{g(\hat{\tau}_{\delta})} \ge \max \left( \frac{\hat{\alpha}_{u,\delta}}{(1+\delta)^4}, \frac{1}{(1+\delta)^7} \sup_{s>0} \left\{ \frac{f(s)}{g(s)} \right\} \right) \quad (42)$$
<caption>**Algorithm 3** UCB for problem (3)</caption>

**Require:** $n, T, f_l, f_u$
$\hat{t}_L \leftarrow \frac{T}{n}$
$\hat{t}_U \leftarrow T$
**if** $\left(\frac{T}{n} <_{\delta} y_{\min}(\hat{\alpha}_{+}(T), T)\right)$ **then**
$\hat{\alpha}_{u, \delta} \leftarrow \frac{n}{T}$
$\hat{\tau}_{\delta} \leftarrow T$
**else**
while $(1 + \delta)\hat{t}_L <_{\delta} \hat{t}_U$ do
$\hat{t}_m \leftarrow \sqrt{\hat{t}_L \hat{t}_U}$
**if** $\frac{T}{n} <_{\delta} y_{\min}(\hat{\alpha}_{+}(\hat{t}_m), \hat{t}_m)$ **then**
$\hat{t}_U \leftarrow \hat{t}_m$
**else**
$\hat{t}_L \leftarrow \hat{t}_m$
**end if**
**end while**
**end if**
$\hat{\alpha}_{u, \delta} \leftarrow \hat{\alpha}_{+}(\hat{t}_U)$
**if** $\hat{t}_U = T$ **then**
$t \leftarrow +\infty$
**else**
$t \leftarrow \hat{t}_U$
**end if**
**if** $\hat{\alpha}_{u, \delta} <_{\delta} \hat{\alpha}_{-}$ or $\lim_{s \to t} g_u(s) <_{\delta} \frac{T}{n}$ **then** return "error: $\mathbb{H}$ is empty"
**end if**
$\hat{\tau}_{\delta} \leftarrow (1 + \delta)\tau_{id}(\hat{t}_U)$
**return** $\hat{\alpha}_{u, \delta}, \hat{\tau}_{\delta}$
where as usual, $g: t \mapsto \int_{0}^{t} (1 - f(s))ds$.

The properties provided by proposition 5.15 are precisely those required to recover Theorem 3.9 when $\delta \to 0$. By equation (42) and since $\hat{\alpha}_{u,\delta} \ge \alpha_*$, the same sorts of bound hold for $\hat{\tau}_\delta$ as for UCB, up to the factor $(1+\delta)^4$. The fact that $\hat{\tau}_\delta$ maximizes $\frac{f}{g}$ up to a factor $1+\varepsilon$ (for some small $\varepsilon$) allows to apply Proposition 4.6 bounding $g_u - g_l$. Finally, the lower bound $g(\hat{\tau}_\delta) \ge \frac{T}{(1+\delta)^{3n}}$ guarantees the near-optimality of $\hat{\tau}_\delta$ in the case where the number of tasks, $n$, proves to be the limiting factor instead of the deadline $T$ (see section D.4). These bounds hold under the assumption that $t_* \in [0; T]$, which by Proposition 5.12 is equivalent to $t_* < +\infty$. Otherwise (assuming $\mathbb{H} \ne \emptyset$), the supremum in equation (40) is attained over $[T; +\infty)$, beyond the cut-off of the policy given by Definition 3.7. Since $\hat{\tau}_\delta \ge T$ also, we may (formally) replace $\tau_j^*$ with $\hat{\tau}_\delta$ without altering the policy on this event. As a result, the value of $\hat{\tau}_\delta$ does not matter in that case.

# 6 Conclusion

In both the penalized and constrained settings (problems (1) and (3), respectively), it is possible to learn the optimal interruption policy with square-root regret, up to log terms, without moment assumptions on the random variables. In the penalized case, the result is completely distribution free while in the constrained case, we assume $n$ to be large enough such that the optimal distribution-dependent policy has a simple approximation (by Proposition 2.4). Minimax lower bounds show that these results are optimal up to polylog factors. The proposed policies are based on the combination of UCB with a new heuristic, UCST (upper confidence stopping time) which leverages the information structure of the problem. Heavy tails are dealt with by restricting the deadlines to a bounded interval of the form $[0; \tau_M]$, where $\tau_M$ can be chosen a priori in problem (1) and must be estimated in problem (3).

We expect the ideas of this article to be applicable beyond the setting of problems (1) and (3). A first, logical generalization is the Bandits with Interrupts setting [7], in which the interruption mechanism analyzed in this article is used to control the tail risk in bandit problems. Definition 3.7 could be adapted for this problem by using UCB to select among the $k$ arms, as well as among the partition ($B_j$) for each arm. Compared to our setting, the biggest difference is the presence of a random reward $Y$ in addition to the random cost $X$: this requires the construction of two separate confidence bands, one for $G(t) = E[\min(X, t)]$ and one for $S(t) = E[Y \mid \{X \le t\}]$. If $Y \in [0; 1]$, the properties of $S$ are quite similar to those of the distribution function $F$: for example, one can prove an analogous result to lemma D.2 and hence use Proposition 4.6 to control the size of the confidence bands for $G$ at the chosen deadlines. For this reason, we expect worst-case bounds similar to Theorem 3.9 to hold in this case. If $Y$ is itself heavy-tailed, the problem appears significantly more complicated and there may not be any distribution-free guarantees. However,
let us remark on an important asymmetry between the impact of heavy tails on X and Y: since X is a cost and Y a reward, heavy-tailed behavior of X is detrimental while heavy-tailed behaviour of Y is beneficial. Thus, ignoring the tail behavior of Y appears less harmful than for X.

A second potential application is *optimal restarts*: in that problem, the optimal policy, on average over a population, is constant equal to $\tau_*$ - the maximizer of $\frac{F}{G}$, where $F, G$ are associated with the distribution of the average completion time over the population. This is precisely the quantity that Definition 3.7 is designed to estimate! Thus, Theorem 3.9 gives learning rates for this policy under a time constraint on the learning process. The learned, constant deadline could be combined with Luby et al's universal strategy [19] for a "best of both worlds" type approach, as in Gagliolo et al. [11].

More generally, the *upper confidence stopping time* idea (with or without cut-off) makes sense in any problem in which a stochastic process is observed up to some deadline chosen by the agent: for example, an optimal stopping problem. This includes problems with large or infinite arm sets for which UCB is not appropriate.

# A Proofs of section 2

## A.1 Proof of Proposition 2.1

On the one hand, for all $\tau \ge 0$,

$$F(\tau) - cG(\tau) = G(\tau) \left( \frac{F(\tau)}{G(\tau)} - c \right) \le G(\tau)(\alpha_* - c) \le 0$$

if $c \ge \alpha_*$. On the other hand, if $0 < c < \alpha_*$, then by definition there exists some $\tau > 0$ such that

$$\frac{F(\tau)}{G(\tau)} > c.$$

This implies that

$$V_c^*(F) \ge F(\tau) - cG(\tau) = G(\tau) \left( \frac{F(\tau)}{G(\tau)} - c \right) > 0$$

since for all $t > 0$,

$$G(t) = \mathbb{E}[\min(X, t)] \ge \sup_{s \le t} \mathbb{E}[s\mathbb{I}\{X > s\}] = \sup_{s \le t} \{s(1 - F(s))\} > 0$$

as $F(0) < 1$ and $F$ is right-continuous.
## A.2 Proof of Proposition 2.2

Using the probability-integral transform, remark that

$$ \mathbb{E}[X_1] = \int_{0}^{+\infty} (1-F(t))dt $$

$$ \mathbb{E}[X_1 \wedge t] = \int_{0}^{t} (1-F(s))ds. $$

For all $t \ge t_0$, by assumption, we have that

$$ 1-F(t) \ge c(\mathbb{E}[X_1]-G(t)) = c\int_{t}^{+\infty}(1-F(s))ds. $$

Define the function $g(t) = \int_{t}^{+\infty} (1-F(s))ds$ for all $t > t_0$. The previous equation yields

$$ -g'(t) \ge cg(t) \iff g'(t) \le -cg(t) $$

for all $t > t_0$. By Grönwall's lemma,

$$ g(t) \le g(t_0)e^{-c(t-t_0)} $$

for all $t \ge t_0$. Moreover,

$$ g(t) = \mathbb{E}[X_1 - X_1 \wedge t] = \mathbb{E}[(X_1 - t)_+], $$

so by Markov's inequality,

$$ \mathbb{P}(X_1 \ge t) = \mathbb{P}(1 \le (X_1 - (t-1))_+ \le g(t-1) \le g(t_0)e^c e^{-ct}) $$

for all $t \ge t_0 + 1$. This proves the sub-exponentiality of $X_1$.

Assume now that $X_1$ is not sub-exponential with parameter c. If $\arg\max\{F-cG\}$ were unbounded, then one could choose a sequence $t_k \to +\infty$ such that for all k,

$$ F(t_k) - cG(t_k) = V_c^*(F). $$

Then, by monotone convergence, we would have

$$ V_c^*(F) = \lim_{t \to +\infty} \{F(t) - cG(t)\} = 1 - c\mathbb{E}[X_1], $$

contradicting the previous result, since by definition of $V_c^*(F)$,

$$ 1 - c\mathbb{E}[X_1] = V_c^*(F) \ge F(t) - cG(t) $$

for all $t > 0$.
## A.3 Proof of Proposition 2.4

Fix a distribution $P$, let $\alpha_* = \alpha_*(P)$ and $\tau_* = \tau_*(P)$. If $G(\tau_*) \ge \frac{T}{n}$, then taking $Z$ with the proposed distribution yields $\mathbb{E}[G(Z)] = \frac{T}{n}$ and

$$ \mathbb{E}[F(Z)] = \frac{T}{nG(\tau_*)} F(\tau_*) = \alpha_* \frac{T}{n} $$

which yields $\bar{V}_n(P, T) \ge \alpha_*T$. On the other hand, for any random variable $Z$ such that $\mathbb{E}[G(Z)] \le \frac{T}{n}$,

$$ \begin{aligned} \mathbb{E}[F(Z)] &= \mathbb{E}\left[\frac{F(Z)}{G(Z)}G(Z)\right] \\ &\le \alpha_* \mathbb{E}[G(Z)] \\ &\le \frac{\alpha_* T}{n}. \end{aligned} $$

The inequality is strict unless $\mathbb{E}[G(Z)] = \frac{T}{n}$. If $G(\tau_*) < \frac{T}{n}$ and $\mathbb{E}[G(Z)] = \frac{T}{n}$, then necessarily,

$$ \mathbb{E}[G(Z)\mathbb{I}\{Z > \tau_*\}] > 0 $$

and hence, by definition of $\tau_*$,

$$ \mathbb{E}[F(Z)\mathbb{I}\{Z > \tau_*\}] = \mathbb{E}\left[\frac{F(Z)}{G(Z)}G(Z)\mathbb{I}\{Z > \tau_*\}\right] < \mathbb{E}[G(Z)\mathbb{I}\{Z > \tau_*\}], $$

so the inequality is always strict in that case.

## A.4 Proof of Proposition 2.5

Assume that $T > \tau_*$, otherwise the bound is trivial. We consider the strategy $\hat{\tau} = (\hat{\tau}_j)_{1 \le j \le n}$, where

$$ \hat{\tau}_j = \tau_* \mathbb{I}\{T_{j-1} \le T - \tau_*\} \text{ where} $$

$$ T_j = \sum_{i=1}^{j} X_i \wedge \hat{\tau}_i $$

$$ T_1 = 0. $$
By construction, $\sum_{i=1}^{n} X_i \wedge \hat{\tau}_i \le T$ so this strategy is valid. Moreover, since the $\hat{\tau}_j$ are stopping times valued in $\{0, \tau_*\}$,

$$ 
\begin{aligned}
V_n(P, T) &\ge \mathbb{E} \left[ \sum_{j=1}^{n} \mathbb{I}\{X_i \le \hat{\tau}_i\} \right] \\
&= \mathbb{E} \left[ \sum_{j=1}^{n} F(\hat{\tau}_i) \right] \\
&= \mathbb{E} \left[ \sum_{j=1}^{n} \alpha_* G(\hat{\tau}_i) \right] \\
&= \alpha_* \mathbb{E} \left[ \sum_{j=1}^{n} X_i \wedge \hat{\tau}_i \right].
\end{aligned}
$$

If $\sum_{k=1}^n X_k \wedge \tau_* \ge T - \tau_*$, there exists some $i \in \{1, \dots, n\}$ such that

$$ T_{i-1} \le \sum_{k=1}^{i-1} X_k \wedge \tau_* < T - \tau_* \le \sum_{k=1}^{i} X_k \wedge \tau_* $$

which yields

$$ \sum_{k=1}^{n} X_k \wedge \hat{\tau}_k \ge \sum_{k=1}^{i} X_k \wedge \tau_* \ge T - \tau_* $$

It follows that

$$ V_n(P, T) \ge \alpha_*(T - \tau_*) \mathbb{P} \left( \sum_{k=1}^{n} X_k \wedge \tau_* \ge T - \tau_* \right) \ge \alpha_* T \mathbb{P} \left( \sum_{k=1}^{n} X_k \wedge \tau_* > T \right) - \alpha_* \tau_* $$

Now, the random variables $X_k \wedge \tau_*$ are non-negative and i.i.d. It follows by Bennett's inequality that for all $t > 0$,

$$ \mathbb{P} \left( \sum_{k=1}^{n} X_k \wedge \tau_* - nG(\tau_*) \le -t \right) \le \exp \left( - \frac{t^2}{2n \mathbb{E} \left[ (X_1 \wedge \tau_*)^2 \right]} \right). $$

Moreover, since $1 - F(t) \ge 1 - F(\tau_*) \frac{G(t)}{G(\tau_*)} \ge \frac{G(\tau_*) - G(t)}{G(\tau_*)}$ for all $t \le \tau_*$,

$$ 
\begin{aligned}
\mathbb{E}[(X_1 \wedge \tau_*)^2] &= \int_0^{+\infty} 2t \mathbb{P}(X_1 \wedge \tau_* > t) dt \\
&= \int_0^{\tau_*} 2t(1 - F(t)) dt \\
&= [-2t(G(\tau_*) - G(t))] + \int_0^{\tau_*} 2(G(\tau_*) - G(t)) dt \\
&\le 2G(\tau_*) \int_0^{\tau_*} (1 - F(t)) dt \\
&= 2G(\tau_*)^2.
\end{aligned}
$$
Thus, for all $t > 0$,

$$ \mathbb{P}\left(\sum_{k=1}^{n} X_k \wedge \tau_* - nG(\tau_*) \le -t\right) \le \exp\left(-\frac{t^2}{4nG(\tau_*)^2}\right). $$

In particular,

$$ \mathbb{P}\left(\sum_{k=1}^{n} X_k \wedge \tau_* < T\right) \le \exp\left(-\frac{(nG(\tau_*) - T)^2}{4nG(\tau_*)^2}\right). $$

Write $n$ as $\frac{T}{G(\tau_*)} + \delta_T$ where $\delta_T > 0$. Thus,

$$ \mathbb{P}\left(\sum_{k=1}^{n} X_k \wedge \tau_* < T\right) \le \exp\left(-\frac{\delta_T^2}{4\left(\frac{T}{G(\tau_*)} + \delta_T\right)}\right). $$

For any $\lambda > 0$,

$$ \begin{aligned} \frac{\delta_T^2}{4\left(\frac{T}{G(\tau_*)} + \delta_T\right)} \ge \lambda &\iff \delta_T^2 - 4\lambda\delta_T - 4\frac{\lambda T}{G(\tau_*)} \ge 0 \\ &\iff \delta_T \ge \frac{1}{2}\left(4\lambda + 4\sqrt{\lambda\left(\lambda + \frac{T}{G(\tau_*)}\right)}\right) \\ &\iff \delta_T \ge 2\lambda + 2\sqrt{\lambda\left(\lambda + \frac{T}{G(\tau_*)}\right)}. \end{aligned} $$

Let $\lambda = \log(\alpha_* T)$, then

$$ \begin{aligned} \sqrt{\lambda\left(\lambda + \frac{T}{G(\tau_*)}\right)} &= \sqrt{\lambda\frac{T}{G(\tau_*)}}\sqrt{1 + \frac{\lambda G(\tau_*)}{T}} \\ &\le \sqrt{\lambda\frac{T}{G(\tau_*)}}\left(1 + \frac{\lambda G(\tau_*)}{2T}\right) \\ &= \sqrt{\lambda\frac{T}{G(\tau_*)}} + \frac{\lambda}{2}\sqrt{\frac{\lambda G(\tau_*)}{T}}. \end{aligned} $$

Since $1 \le \alpha_* T \le \frac{T}{G(\tau_*)}$, we have that

$$ \frac{\lambda G(\tau_*)}{T} \le \sup_{t \ge 1} \frac{\log t}{t} = \frac{1}{e}. $$

Thus,

$$ 2\lambda + 2\sqrt{\lambda\left(\lambda + \frac{T}{G(\tau_*)}\right)} \le 2\lambda + 2\sqrt{\lambda\frac{T}{G(\tau_*)}} + \frac{\lambda}{\sqrt{e}} \le \delta_T. $$
This yields

$$ \mathbb{P}\left(\sum_{k=1}^{n} X_k \wedge \tau_* < T\right) \le \exp(-\lambda) = \frac{1}{\alpha_* T} $$

and finally

$$ V_n(P, T) \ge \alpha_* T \left(1 - \frac{1}{\alpha_* T}\right) - \alpha_* \tau_* \ge \alpha_* T - \alpha_* \tau_* - 1. $$

## A.5 Proof of claim 2.5.1

By assumption, $\tau_1, \eta(1)$ are measurable with respect to $\mathcal{F}_1 = \{\emptyset, \Omega\}$, in other words they are deterministic. This establishes the claim for $j = 1$. Proceed now by induction on $j$ for some fixed $i$. Let $j \ge 2$. By the measurability assumption, there exists some measurable function $g_j : \mathbb{R}^{j-1} \to \mathbb{R} \times \{1, \dots, n\}$ such that $(\tau_j, \eta(j)) = g_j(Y_j)$, where

$$ Y_j = (Y_{j,1}, \dots, Y_{j,j-1}) = (X_{\eta(k)} \wedge \tau_k, \mathbb{I}\{X_{\eta(k)} > \tau_k\})_{1 \le k \le j-1}. $$

Moreover, for any $k \in \{1, \dots, j-1\}$, by induction and definition of $\bar{\tau}_{i,j-1}$, on the event $\{X_i > \bar{\tau}_{i,j-1}\}$,

$$ \begin{aligned} Y_{j,k} &= (\tau_k, 1)\mathbb{I}\{\eta(k) = i\} + \sum_{j \ne i} (X_j \wedge \tau_k, \mathbb{I}\{X_j > \tau_k\})\mathbb{I}\{\eta(k) = j\} \\ &= (f_{i,k}^0(\mathbf{X}^{(i)}), 1)\mathbb{I}\{f_{i,k}^1(\mathbf{X}^{(i)}) = i\} + \sum_{j \ne i} (X_j \wedge f_{i,k}^0(\mathbf{X}^{(i)}), \mathbb{I}\{X_j > f_{i,k}^1(\mathbf{X}^{(i)})\})\mathbb{I}\{f_{i,k}^1(\mathbf{X}^{(i)}) = j\}, \end{aligned} $$

where $f_{i,j}^0$ and $f_{i,j}^1$ denote the two components of $f_{i,j}$. It follows that $Y_j$ is a measurable function of $X^{(i)}$ on the event $\{X_i > \bar{\tau}_{i,j-1}\}$. Hence, so is the pair $(\tau_j, \eta(j))$, which completes the induction step.

## A.6 Proof of claim 2.5.2

Since $\tau_0, \eta(0)$ are deterministic, the claim is true for $j = 0$. Assume that it is true at step $j-1$. By definition of $\bar{\tau}_{i,j}$

$$ \mathbb{I}\{X_i > \bar{\tau}_{i,j}\} = \mathbb{I}\{X_i > \bar{\tau}_{i,j-1}\}\mathbb{I}\{X_i > \tau_j\}\mathbb{I}\{\eta(j) = i\}. $$

Thus, by the previous claim 2.5.1,

$$ \mathbb{I}\{X_i > \bar{\tau}_{i,j}\} = \mathbb{I}\{X_i > \bar{\tau}_{i,j-1}\}\mathbb{I}\{X_i > f_{i,j}^0(\mathbf{X}^{(i)})\}\mathbb{I}\{f_{i,j}^1(\mathbf{X}^{(i)}) = i\}. $$

By the induction hypothesis,

$$ \mathbb{I}\{X_i > \bar{\tau}_{i,j}\} = \mathbb{I}\{X_i > g_{i,j-1}(\mathbf{X}^{(i)})\}\mathbb{I}\{X_i > f_{i,j}^0(\mathbf{X}^{(i)})\}\mathbb{I}\{f_{i,j}^1(\mathbf{X}^{(i)}) = i\} = \mathbb{I}\{X_i > g_{i,j}(\mathbf{X}^{(i)})\}, $$

where the function $g_{i,j} : \mathbb{R}^{n-1} \to \mathbb{R}_+$ is defined by

$$ g_{i,j} : x \mapsto \max(g_{i,j-1}(x), f_{i,j}^0(x)\mathbb{I}\{f_{i,j}^1(x) = i\}) $$
This proves the induction step for the first equation. Consider now the second equation. By claim .. and the induction hypothesis,

$$
\begin{align*}
\bar{\tau}_{i,j} \mathbb{I}\{X_i > \bar{\tau}_{i,j}\} &= \max(\bar{\tau}_{i,j-1}, \tau_j \mathbb{I}\{\eta(j) = i\}) \mathbb{I}\{X_i > \bar{\tau}_{i,j}\} \mathbb{I}\{X_i > \bar{\tau}_{i,j-1}\} \\
&= \max(g_{i,j-1}(\mathbf{X}^{(i)}), f_{i,j}^0(\mathbf{X}^{(i)}) \mathbb{I}\{f_{i,j}^1(\mathbf{X}^{(i)}) = i\}) \mathbb{I}\{X_i > \bar{\tau}_{i,j-1}\} \mathbb{I}\{X_i > \bar{\tau}_{i,j}\} \\
&= g_{i,j}(\mathbf{X}^{(i)}) \mathbb{I}\{X_i > \bar{\tau}_{i,j}\} \\
&= g_{i,j}(\mathbf{X}^{(i)}) \mathbb{I}\{X_i > g_{i,j}(\mathbf{X}^{(i)})\} \text{ by the first equation.}
\end{align*}
$$

Thus, the induction step works for both equations (6) and (7). By induction, these equations hold true for all $j$ and in particular for $\bar{\tau}_i = \bar{\tau}_{i,n}$.

## A.7 Proof of Theorem 2.7

To see that $V_n \le V_{n,m}$ when $m \ge n$, consider that, for any sequence $(\tau_j)_{1 \le j \le n}$ satisfying the constraints of problem (3), we can set $\eta_j = j \wedge n$, $\tau_j = \tau_{j \wedge n}$ for all $j \in \{1, \dots, m\}$ in problem (8) and obtain a value not less than that of problem (3) for sequence $(\tau_j)_{1 \le j \le n}$. We now have to bound $V_{n,m}(P,T)$ by $\bar{V}_n(P,t)$. Let $(\tau_j, \eta(j))_{1 \le j \le m}$ solve problem (8) up to a small constant $\delta > 0$.

Almost surely, by definition,

$$T \ge \sum_{i=1}^{n} X_i \wedge \bar{\tau}_i$$

and in particular,

$$T \ge \sum_{i=1}^{n} \mathbb{E}[X_i \wedge \bar{\tau}_i].$$

It follows from claim 2.5.2 that

$$T \ge \mathbb{E} \left[ \sum_{i=1}^{n} G(g_{i,n}(\mathbf{X}^{(i)})) \right] \quad (43)$$

for some measurable functions $g_{i,n}$, where $\mathbf{X}^{(i)} = (X_k)_{k \ne i}$ for any $i \in \{1, \dots, n\}$. By the same argument,

$$V_{n,m}(P,T) - \delta \le \mathbb{E} \left[ \sum_{i=1}^{n} \mathbb{I}\{X_i \le \bar{\tau}_i\} \right] = \sum_{i=1}^{n} \mathbb{E} \left[ F(g_{i,n}(\mathbf{X}^{(i)})) \right]. \quad (44)$$

Let $U \sim \text{Unif}(\{1, \dots, n\})$ be independent from $(X_1, \dots, X_n)$ and define

$$Z = g_{U,n}(\mathbf{X}^{(U)})$$

By equation (43),

$$n \mathbb{E}[G(Z)] \le T.$$

Hence, by equation (44) and definition of $\bar{V}_n(P,T)$,

$$V_{n,m}(P,T) \le n \mathbb{E}[F(Z)] + \delta \le \bar{V}_n(P,T) + \delta.$$

Since $\delta > 0$ was arbitrary, this proves theorem 2.7.
# B Proofs of section 4

## B.1 Proof of lemma 4.2 and Proposition 4.3

Let $U_1, \dots, U_n$ be an i.i.d sample from the Uniform distribution (on $[0; 1]$) and, for all $j \in \{1, \dots, n\}$, let

$$U_{j,(1)}, \dots, U_{j,(j)}$$

be the order statistics of the sub-sample $U_1, \dots, U_j$. Let $F_{j,i}^{\beta}$ denote the distribution function of the Beta$(i, j - i + 1)$ distribution.

Let us introduce the following definition.

**Definition B.1.** *Define the random variables*

$$M_n^+ = \min_{1 \le j \le n-1} \min_{1 \le i \le j} F_{j,i}^{\beta} (U_{j,(i)}) \quad (45)$$

$$M_n^- = \min_{1 \le j \le n-1} \min_{1 \le i \le j} (1 - F_{j,i}^{\beta}) (U_{j,(i)}) \quad (46)$$

$$M_n = \min (M_n^+, M_n^-), \quad (47)$$

where $(U_{j,(i)})_{1 \le i \le j}$ are the order statistics of an i.i.d sample from the beta distribution.

Let us first make the definition of $\lambda_n(\eta)$ more explicit.

**Proposition B.2.** For any $\eta \in [0; 1]$, $\lambda_n(\eta)$ is the $\eta$ quantile of the distribution of $M_n$, i.e

$$\mathbb{P}(M_n < \lambda_n(\eta)) = \eta.$$

*Proof.* Consider the event

$$\Omega_{\eta} = \{M_n \ge \lambda_n(\eta)\}.$$

This can be rewritten as

$$\begin{aligned} \Omega_{\eta} &= \{\forall j, i, \lambda_n(\eta) \le F_{j,i}^{\beta} (U_{j,(i)}) \le 1 - \lambda_n(\eta)\} \\ &= \{\forall j, i, q_{\lambda_n(\eta)}(i, j - i + 1) \le U_{j,(i)} \le q_{1-\lambda_n(\eta)}(i + 1, j - i)\}. \end{aligned}$$

For any $j \in \{1, \dots, n-1\}$, $i \in \{2, \dots, j-1\}$ and $x \in [U_{j,(i)}; U_{j,(i+1)})$,

$$\tilde{F}(U_1, \dots, U_j)(x) = \frac{i}{j}$$

and hence

$$q_{\lambda_n(\eta)}(i, j - i + 1) = w_{n,\eta}^{-} (\tilde{F}(U_1, \dots, U_j)(x)) = \tilde{F}_{n,\eta}^{-} (U_1, \dots, U_j)(x),$$

$$q_{1-\lambda_n(\eta)}(i, j - i + 1) = w_{n,\eta}^{+} (\tilde{F}(U_1, \dots, U_j)(x)) = \tilde{F}_{n,\eta}^{+} (U_1, \dots, U_j)(x).$$
Thus,

$$x \in [\tilde{F}_{n,\eta}^{-}(U_1, \dots, U_j)(x); \tilde{F}_{n,\eta}^{+}(U_1, \dots, U_j)(x)] \text{ for all } x \in [U_{j,(i)}; U_{j,(i+1)}]$$

if and only if

$$q_{\lambda_n(\eta)}(i, j - i + 1) \le U_{j,(i)} \text{ and } U_{j,(i+1)} \le q_{1-\lambda_n(\eta)}(i, j - i + 1).$$

Reasoning similarly for $x < U_{j,(1)}$ and $x \ge U_{j,(j)}$, it can be seen that

$$\{F \in [\tilde{F}_{n,\eta}^{-}(U_1, \dots, U_j)(x); \tilde{F}_{n,\eta}^{+}(U_1, \dots, U_j)(x)] \text{ for all } j \in \{1, \dots, n\} \} = \{M_n \ge \eta\}.$$

Thus, by definition of $\lambda_n(\eta)$,

$$\eta = \mathbb{P}(M_n \ge \eta).$$

Since $M_n$ is the minimum of a finite number of continuous random variables, its distribution is also continuous. This finally yields

$$\eta = \mathbb{P}(M_n > \eta),$$

as claimed.

<figure><img src="image_3.png" /></figure>

Lemma 4.2 follows from Proposition B.2: since $M_n$ is the minimum of $n(n-1)$ uniformly-distributed random variables, the union bound yields

$$\eta = \mathbb{P}(M_n < \lambda_n(\eta)) \le n(n-1)\lambda_n(\eta).$$

Let us now prove Proposition 4.3.

Let $(X_i)_{1 \le i \le n}$ be an i.i.d sample with common cdf $F$. By the probability integral transform, we may assume that $X_i = F^{\leftarrow}(U_i)$, where $F^{\leftarrow} : [0; 1] \to \mathbb{R}$ is the right-continuous inverse, defined by

$$F^{\leftarrow}(y) = \inf \{x \in \mathbb{R} : F(x) \ge y\}.$$

Let also $F_g(x) = F(x^-) = \sup_{z<x}\{F(z)\}$. By right continuity of $F$, we have that

$$F(F^{\leftarrow}(y)) \ge y \qquad (48)$$

$$F_g(F^{\leftarrow}(y)) \le y \qquad (49)$$

for all $y \in [0; 1]$. Consider the event

$$\Omega_{\eta} = \{M_n > \lambda_n(\eta)\}.$$

By definition of $\lambda_n(\eta)$, this event has probability $1 - \eta$, moreover

$$\begin{aligned} \Omega_{\eta} &= \{\forall j, i, \lambda_n(\eta) < F_{j,i}^{\beta}(U_{j,(i)}) < 1 - \lambda_n(\eta)\} \\ &= \{\forall j, i, q_{\lambda_n(\eta)}(i, j - i + 1) < U_{j,(i)} < q_{1-\lambda_n(\eta)}(i, j - i + 1)\}. \end{aligned}$$
For all $j \in \{1, \dots, n-1\}$, let $(X_{j,(i)})_{1\le i\le j}$ denote the order statistics of the sub-sample $X_1, \dots, X_j$. Let $j \in \{1, \dots, n-1\}$ and $x \in \mathbb{R}$. If $t < X_{j,(1)}$, then on $\Omega_\eta$,

$$
\begin{align*}
0 &= \tilde{F}_{n,\eta}^{-}(X_1, \dots, X_j)(t) \\
  &\le F(t) \\
  &\le F_g(X_{j,(1)}) = F_g(F^{\leftarrow}(U_{j,(1)})) \\
  &\le U_{j,(1)} \\
  &< q_{1-\lambda_n(\eta)}(1, j) \\
  &= w_{n,\eta}^{+}(0) \\
  &= \tilde{F}_{n,\eta}^{+}(X_1, \dots, X_j)(t).
\end{align*}
$$

If $x \in [X_{j,(i)}; X_{j,(i+1)})$ for some $i \in \{1, \dots, n-2\}$, then on $\Omega_\eta$,

$$
\begin{align*}
\tilde{F}_{n,\eta}^{-}(X_1, \dots, X_j)(x) &= w_{n,\eta}^{-} \left(\frac{i}{j}\right) \\
&= q_{\lambda_n(\eta)}(i, j - i + 1) \\
&< U_{j,(i)} \\
&\le F(F^{\leftarrow}(U_{j,(i)})) = F(X_{j,(i)}) \\
&\le F(x) \\
&\le F_g(X_{j,(i+1)}) = F_g(F^{\leftarrow}(U_{j,(i+1)})) \\
&\le U_{j,(i+1)} \\
&\le q_{1-\lambda_n(\eta)}(i+1, j - i) \\
&= w_{n,\eta}^{+} \left(\frac{i}{j}\right) = \tilde{F}_{n,\eta}^{+}(X_1, \dots, X_j)(x).
\end{align*}
$$

Finally, if $x \ge X_{j,(j)}$, then on $\Omega_\eta$,

$$
\begin{align*}
\tilde{F}_{n,\eta}^{-}(X_1, \dots, X_j)(x) &= w_{n,\eta}^{-}(1) \\
&= q_{\lambda_n(\eta)}(j, 1) \\
&< U_{j,(j)} \\
&\le F(F^{\leftarrow}(U_{j,(j)})) = F(X_{j,(j)}) \\
&\le F(x) \\
&\le 1 = w_{n,\beta}^{+}(1) \\
&= \tilde{F}_{n,\eta}^{-}(X_1, \dots, X_j)(x).
\end{align*}
$$

This proves that on $\Omega_\eta$, for all $j \in \{1, \dots, n-1\}$,

$$
F \in [\tilde{F}_{n,\beta}^{-}(X_1, \dots, X_j); \tilde{F}_{n,\beta}^{+}(X_1, \dots, X_j)]
$$

which proves the proposition.
## B.2 Proof of Proposition 4.4

We now state Hoeffding and Bernstein type bounds on the confidence intervals. First, we will need the following lemma.

**Lemma B.3.** For any $u \in [0; 1]$ and any $j \ge 1$,

$$ \mathrm{Med}(\mathrm{Beta}(ju, j(1-u) + 1)) \le u \quad (50) $$

$$ \mathrm{Med}(\mathrm{Beta}(ju + 1, j(1-u))) \ge u, \quad (51) $$

where $\mathrm{Med}(Q)$ denotes the median of a distribution $Q$.

*Proof.* If $1 < a < b$, the mode-median-mean inequality implies that

$$ \mathrm{Mode}(\mathrm{Beta}(a, b)) = \frac{a-1}{a+b-2} \le \mathrm{Med}(\mathrm{Beta}(a, b)) \le \frac{a}{a+b} = \mathrm{Mean}(\mathrm{Beta}(a, b)). $$

If $1 < b < a$, the inequality goes in the other direction:

$$ \mathrm{Mode}(\mathrm{Beta}(a, b)) \ge \frac{a-1}{a+b-2} \ge \mathrm{Med}(\mathrm{Beta}(a, b)) \ge \frac{a}{a+b} = \mathrm{Mean}(\mathrm{Beta}(a, b)). $$

Thirdly, if $a = b$, then the beta-distribution is symmetric, so that

$$ \mathrm{Med}(\mathrm{Beta}(a, b)) = \frac{a}{a+b} = \frac{1}{2}. $$

Thus, in all of these cases, we have that

$$ \min \left( \frac{a-1}{a+b-2}, \frac{a}{a+b} \right) \le \mathrm{Med}(\mathrm{Beta}(a, b)) \le \max \left( \frac{a-1}{a+b-2}, \frac{a}{a+b} \right). $$

Taking $a = ju, b = j(1-u) + 1$ yields

$$ \begin{aligned} \frac{a-1}{a+b-2} &= \frac{ju-1}{j-1} \\ &\le \frac{ju-u}{j-1} \\ &= u \end{aligned} $$

$$ \begin{aligned} \frac{a}{a+b} &= \frac{ju}{j+1} \\ &\le u \end{aligned} $$

which yields

$$ \mathrm{Med}(\mathrm{Beta}(ju, j(1-u) + 1)) \le u. $$
Taking $a = ju + 1, b = j(1 - u)$ yields

$$ \frac{a-1}{a+b-2} = \frac{ju}{j-1} \\ \geq u $$

$$ \frac{a}{a+b} = \frac{ju+1}{j+1} \\ \geq \frac{ju+u}{j+1} \\ = u $$

which yields

$$ \mathrm{Med}(\mathrm{Beta}(ju + 1, j(1 - u))) \geq u. $$

If $a = ju \le 1$, then $b \ge 1$ and the probability density of $\mathrm{Beta}(a, b)$ is non-increasing, which implies that

$$ \mathrm{Med}(\mathrm{Beta}(a, b)) \le \frac{a}{a+b} \le u. $$

Symmetrically, if $b = j(1 - u) \le 1$, then the probability density of $\mathrm{Beta}(a, b)$ is non-decreasing, which yields

$$ \mathrm{Med}(\mathrm{Beta}(a, b)) \geq \frac{a}{a+b} \geq u, $$

as desired.

□

By lemma 4.2,

$$ \eta \ge \lambda_n(\eta) \ge \frac{\eta}{n(n-1)} \ge \exp(-y). \qquad (52) $$

Define the function

$$ h(q, x) = \frac{(x - q)^2}{2\left(\frac{2x}{3} + \frac{q}{3}\right)\left(1 - \frac{2x}{3} - \frac{q}{3}\right)} \qquad (53) $$

for all $q, x \in [0; 1]^2$. Define also the functions

$$ b_{\eta}(q) = \inf \left\{ x \in [0; 1] : h(q, x) \le -\frac{\log \lambda_n(\eta)}{j} \right\} \qquad (54) $$

$$ B_{\eta}(q) = \sup \left\{ x \in [0; 1] : h(q, x) \le -\frac{\log \lambda_n(\eta)}{j} \right\}. \qquad (55) $$

Let $u \in [0; 1]$ and $j \in \{1, \dots, n\}$. Consider first the lower bound. By [16, Corollary 8] with $a = ju, b = j(1 - u) + 1$ and $p_l = \frac{a}{a+b-1} = u$, for any random variable $Z$ with distribution $\mathrm{Beta}(u, j(1 - u) + 1)$, we have that

$$ \mathbb{P}(Z \le x) \le \exp(-jh(u, x)) $$
for all $x \ge 0$. Thus, by definition of $b_\alpha$, if $x < b_\eta(u)$, then

$$ \mathbb{P}(Z \le x) < \lambda_n(\eta). $$

Hence, by definition of $w_{j,\eta}^{-}$,

$$ w_{j,\eta}^{-}(u) = q_{\lambda_n(\eta)}(ju, j(1-u) + 1) \ge b_{\eta}(u). $$

On the other hand, since $\lambda_n(\eta) \le \eta \le \frac{1}{2}$, by lemma B.3,

$$ w_{j,\eta}^{-}(u) = q_{\lambda_n(\eta)}(ju, j(1-u) + 1) \le u. $$

The proof of the second equation is similar. By [16, Corollary 8] with $a = ju + 1, b = j(1-u)$ and $p_r = \frac{a-1}{a+b-1} = u$, for any random variable $Z$ with distribution $\text{Beta}(ju + 1, j(1-u))$, we have that

$$ \mathbb{P}(Z > x) \le \exp(-jh(u, x)) $$

for all $x \ge 0$. Thus, by definition of $B_\alpha$, if $x > B_\alpha(u)$, then

$$ \mathbb{P}(Z \le x) > 1 - \lambda_n(\eta). $$

Hence, by definition of $w_{j,\eta}^{+}$,

$$ w_{j,\eta}^{+}(u) = q_{1-\lambda_n(\eta)}(ju + 1, j(1-u)) \le B_{\eta}(u). $$

Moreover, since $\lambda_n(\eta) \le \eta \le \frac{1}{2}$, by lemma B.3,

$$ w_{j,\eta}^{+}(u) = q_{1-\lambda_n(\eta)}(ju, j(1-u) + 1) \ge u. $$

We have proved that for all $u \in [0; 1]$ and all $j \le n$,

$$ b_{\eta}(u) \le w_{j,\eta}^{-}(u) \le u \le w_{j,\eta}^{+}(u) \le B_{\eta}(u). \quad (56) $$

Now, to deduce the Hoeffding-type bound, remark that by equation (53) and since $u(1-u) \le \frac{1}{4}$ for all $u$,

$$ h(u, x) \ge 2(x - q)^2 $$

for all $x, u \in [0; 1]$. Thus, by equations (54) and (55) defining $b_\eta, B_\eta$,

$$ u - \sqrt{\frac{-\log \lambda_n(\eta)}{2j}} \le b_\eta(u) \le B_\eta(u) \le u + \sqrt{\frac{-\log \lambda_n(\eta)}{2j}}. $$

Equations (30), (31) then follows from equation (52).

Finally, let us derive the Bernstein-type bound. Let $q \in [0; 1]$ and $t \in [-q; 1-q]$. By equation (53),

$$ \begin{aligned} h(q, q + t) &= \frac{t^2}{2 \left(q + \frac{2t}{3}\right) \left(1 - q - \frac{2t}{3}\right)} \\ &= \frac{t^2}{2q(1-q) + (1-2q)\frac{4t}{3} - \frac{4t^2}{3}} \\ &\ge \frac{t^2}{2q(1-q) + (1-2q)\frac{4t}{3}}. \end{aligned} \quad (57) $$
If $t \in [0; 1-q]$, we have that

$$h(q, q + t) \geq \frac{t^2}{2q(1-q) + (1-2q)_+ \frac{4t}{3}}.$$

It follows that when

$$t > \sqrt{2q(1-q)x} + \frac{4x}{3}(1-2q)_+$$

for some $x \geq 0$, then

$$h(q, q + t) > \frac{2q(1-q)x + (1-2q)_+ \frac{8x}{3} \sqrt{2q(1-q)x} + (1-2q)_+^2 \frac{16x^2}{9}}{2q(1-q) + (1-2q)_+ \frac{4}{3} \sqrt{2q(1-q)x} + (1-2q)_+^2 \frac{16x}{9}} > x.$$

It follows from equation (55) defining $B_\eta$ that

$$B_{\eta}(u) \leq u + \sqrt{2u(1-u)} \sqrt{\frac{-\log \lambda_{n}(\eta)}{j}} + (1-2u)_+ \frac{4 \log \lambda_{n}(\eta)}{3j}$$

for any $u \in [0; 1]$. Equation (28) then follows from equations (56) and (52).

The lower bound is derived by a similar argument. If $t \in [0; q]$, then by equation (57),

$$h(q, q - t) \geq \frac{t^2}{2q(1-q) + (1-2q)_- \frac{4t}{3}}$$

so when

$$t > \sqrt{2q(1-q)x} + \frac{4x}{3}(1-2q)_-$$

for some $x \geq 0$, then $h(q, q - t) > x$ (by the same calculation as above). Thus, by equation (54) defining $b_\eta$,

$$b_{\eta}(u) \geq u - \sqrt{2u(1-u)} \sqrt{\frac{-\log \lambda_{n}(\eta)}{j}} - (1-2u)_- \frac{4 \log \lambda_{n}(\eta)}{3j}.$$

Equation (29) then follows from equations (56) and (52).

## B.3 Proof of lemma 4.5

Fix some $t \geq 0$. If $f_1(t) \geq f_0(t)$, then by Proposition 4.4,

$$\begin{align*}
f(t) &\geq f_1(t) - (w_{m,\eta}^{+} - w_{m,\eta}^{-})(f_0(t)) \\
&\geq f_1(t) - 2\sqrt{\frac{2z}{m}}\sqrt{f_0(t)} - \frac{4z}{3m} \\
&\geq f_1(t) - 2\sqrt{\frac{2z}{m}}\sqrt{f_1(t)} - \frac{4z}{3m}.
\end{align*}$$
If $f(t) \le f_1(t) \le f_0(t)$, then

$$f(t) \ge w_{m,\eta}^{-}(f_0(t)) \ge w(f_0(t))$$

where $w$ is the function

$$w : u \mapsto \left( u - \sqrt{\frac{2zu}{m} - \frac{4z}{3m}} \right)_+ .$$

This function is non-decreasing since $w(u) > 0$ implies $u > \frac{2z}{m}$, in which case

$$w'(u) = 1 - \sqrt{\frac{z}{2um}} \ge 1 - \sqrt{\frac{1}{4}} \ge \frac{1}{2} > 0.$$

It follows that

$$f(t) \ge w(f_1(t)) = f_1(t) - \sqrt{\frac{2z}{m}}\sqrt{f_1(t)} - \frac{4z}{3m}.$$

Thus, in all cases,

$$f_0(t) \ge f_1(t) - 2\sqrt{\frac{2z}{m}}\sqrt{f_1(t)} - \frac{4z}{3m}.$$

Consider now the second bound. Fix some $t \ge 0$, then

$$f_1(t) \le w_{m,\eta}^{+}(f_0(t)) \le w_{m,\eta}^{-}(f_0(t)) + 2\sqrt{\frac{2z}{m}(1-f_0(t))} + \frac{4z}{3m}.$$

Since $f_0(t) \ge w_{m,\eta}^{-}(f_0(t))$,

$$f_1(t) \le w_{m,\eta}^{-}(f_0(t)) + 2\sqrt{\frac{2z}{m}(1 - w_{m,\eta}^{-}(f_0(t)))} + \frac{4z}{3m}$$

so

$$f_1(t) \le w(f_1(t))$$

where $w$ is the function defined on $\mathbb{R}_+$ by

$$w : u \mapsto \min \left( 1, u + 2\sqrt{\frac{2z}{m}(1-u)} + \frac{4z}{m} \right).$$

The function $w$ is non-decreasing since $w(u) < 1$ implies $1 - u > 4\frac{2z}{m}$, in which case

$$w'(u) = 1 - \sqrt{\frac{2z}{m(1-u)}} \ge \frac{1}{2} > 0.$$

Thus, since $f(t) \ge w_{m,\eta}^{-}(f_0(t))$,

$$f_1(t) \le w(f_1(t)) = f_1(t) + 2\sqrt{\frac{2z}{m}(1 - f_1(t))} + \frac{4z}{3m}.$$
Writing $y = f_1(t) - f(t)$, $a = \frac{8z}{m}$, $\sigma^2 = 1 - f_1(t)$ and $b = \frac{4z}{3m}$ yields the inequality

$$y \le \sqrt{a(\sigma^2 + y)} + b \iff (y \le b) \lor ((y-b)^2 \le a\sigma^2 + ay).$$

The second condition yields

$$y^2 - (2b + a)y + b^2 - a\sigma^2 \le 0.$$

The discriminant to this inequality is

$$\Delta = 4b^2 + 4ab + a^2 - 4(b^2 - a\sigma^2) = 4a\sigma^2 + 4ab + b^2$$

which yields

$$y \le y_+ = \frac{1}{2} \left( 2b + a + \sqrt{4a\sigma^2 + 4ab + b^2} \right) \le a\sigma + \frac{1}{2} \left( 2b + a + \sqrt{4ab + b^2} \right).$$

Replacing $a, b, \sigma$ by their values yields

$$\frac{1}{2} (2b + a + \sqrt{4ab + b^2}) = \frac{z}{2m} \left( \frac{8}{3} + 8 + \sqrt{8 \times \frac{16}{3} + \frac{16}{9}} \right) = \frac{z}{m} \left( \frac{16}{3} + \sqrt{\frac{100}{9}} \right) = \frac{26z}{3m}$$

and hence

$$f_1(t) - f(t) \le 2\sqrt{\frac{2z}{m}(1 - f_1(t))} + \frac{9z}{m}.$$

## B.4 Proof of Proposition 4.6

**Lemma B.4.** For all $u \ge 0$ and $\delta \ge 0$,

$$0 \le \sqrt{u} - \frac{u}{\sqrt{u} + \delta} \le \frac{1}{2}\sqrt{\delta}$$

*Proof.* The lower bound is obvious. Consider now the upper bound. For any such $u, \delta$,

$$\begin{aligned} \sqrt{u} - \frac{u}{\sqrt{u} + \delta} &= \sqrt{u} - \frac{u + \delta}{\sqrt{u} + \delta} + \frac{\delta}{\sqrt{u} + \delta} \\ &= \sqrt{u} - \sqrt{u + \delta} + \frac{\delta}{\sqrt{u + \delta}}. \end{aligned}$$

Now, by concavity of the square root, $\sqrt{1+x} \le 1 + \frac{x}{2}$ for any $x \in [-1; +\infty)$. It follows that

$$\begin{aligned} \sqrt{u} - \sqrt{u + \delta} &= \sqrt{u + \delta} \left( \sqrt{\frac{u}{u + \delta}} - 1 \right) \\ &= \sqrt{u + \delta} \left( \sqrt{1 - \frac{\delta}{u + \delta}} - 1 \right) \\ &\le -\sqrt{u + \delta} \frac{\delta}{2(u + \delta)} \\ &= -\frac{\delta}{2\sqrt{u + \delta}}. \end{aligned}$$
This yields

$$ \sqrt{u} - \frac{u}{\sqrt{u} + \delta} \leq -\frac{\delta}{2\sqrt{u} + \delta} + \frac{\delta}{\sqrt{u} + \delta} = \frac{\delta}{2\sqrt{u} + \delta} \leq \frac{1}{2}\sqrt{\delta}, $$

as claimed.

<figure><img src="image_4.png" /></figure>

By Proposition 4.4, for all $s \leq t$, since $m$ is non-increasing,

$$ \begin{aligned} f_1(s) &\geq w_{m(s),\eta}^{-}(f_0(s)) \\ &\geq f_0(s) - \sqrt{\frac{2y}{m(s)}} \sqrt{f_0(s)(1-f_0(s))} - \frac{4y}{3m(s)} \\ &\geq f_0(s) - \sqrt{\frac{2y}{m(t)}} \sqrt{f_0(s)(1-f_0(s))} - \frac{4y}{3m(t)}, \end{aligned} $$

and

$$ \begin{aligned} f_1(s) &\leq w_{m(s),\eta}^{+}(f_0(s)) \\ &\leq f_0(s) + \sqrt{\frac{2y}{m(s)}} \sqrt{f_0(s)(1-f_0(s))} + \frac{4y}{3m(s)} \\ &\leq f_0(s) + \sqrt{\frac{2y}{m(t)}} \sqrt{f_0(s)(1-f_0(s))} + \frac{4y}{3m(t)}, \end{aligned} $$

from which it follows that

$$ g_1(t) \leq g_0(t) + \sqrt{\frac{2y}{m(t)}} \int_0^t \sqrt{1 - f_0(s)} ds + \frac{4yt}{3m(t)} \quad (58) $$

$$ g_1(t) \geq g_0(t) - \sqrt{\frac{2y}{m(t)}} \int_0^t \sqrt{1 - f_0(s)} ds - \frac{4yt}{3m(t)}. \quad (59) $$

Moreover, for all $s \leq t$,

$$ \begin{aligned} 1 - f_0(s) &= 1 - f(s) + f(s) - f_0(s) \\ &\leq 1 - f(s) + w_{m(s),\eta}^{+}(f_0(s)) - f_0(s) \\ &\leq 1 - f(s) + \sqrt{\frac{2y}{m(s)}} \sqrt{1 - f_0(s)} + \frac{4y}{3m(s)} \end{aligned} $$

Let $\theta \in (0; 1)$ to be chosen later.

$$ 1 - f_0(s) \leq 1 - f(s) + \theta (1 - f_0(s)) + \frac{y}{2\theta m(s)} + \frac{4y}{3m(s)}, $$

which implies that

$$ 1 - f_0(s) \leq \frac{1 - f(s)}{1 - \theta} + \frac{y}{(1 - \theta)m(s)} \left( \frac{1}{2\theta} + \frac{4}{3} \right) $$
and, using the sub-additivity of the square-root,

$$ \sqrt{1 - f_0(s)} \le \frac{\sqrt{1 - f(s)}}{\sqrt{1 - \theta}} + \sqrt{\frac{y}{(1 - \theta)m(s)}} \sqrt{\frac{1}{2\theta}} + \frac{4}{3}. $$

Thus,

$$ \int_{0}^{t} \sqrt{1 - f_{0}(s)} ds \le \frac{\int_{0}^{t} \sqrt{1 - f(s)} ds}{\sqrt{1 - \theta}} + \frac{t \sqrt{y}}{\sqrt{(1 - \theta)m(t)}} \sqrt{\frac{1}{2\theta}} + \frac{4}{3}. $$

Let $t_{\rho} \le t$ be such that $g(t_{\rho}) = \frac{t}{\rho}$. $t_{\rho}$ exists by the intermediate value theorem. By equation (33) and lemma B.4,

$$ \begin{aligned} \int_{0}^{t_{\rho}} \sqrt{1 - f(s)} ds &\le \int_{0}^{t_{\rho}} \frac{1 - f(s)}{\sqrt{1 - f(s) + \delta}} ds + \int_{0}^{t_{\rho}} \frac{1}{2} \sqrt{\delta} ds \\ &\le \int_{0}^{t_{\rho}} \frac{1 - f(s)}{\sqrt{r(g(t) - \rho g(s))}} ds + \frac{t_{\rho}}{2} \sqrt{\delta}. \end{aligned} $$

Since $\frac{d}{ds}[g(t) - \rho g(s)] = -\rho(1 - f(s))$, this yields

$$ \int_{0}^{t_{\rho}} \sqrt{1 - f(s)} ds \le \frac{1}{\sqrt{r}} \left[ -\frac{2}{\rho} \sqrt{g(t) - \rho g(s)} \right]_{0}^{t_{\rho}} + \frac{t_{\rho}}{2} \sqrt{\delta} = \frac{2}{\rho} \sqrt{\frac{g(t)}{r}} + \frac{t_{\rho}}{2} \sqrt{\delta}. $$

Moreover, by the Cauchy-Schwarz inequality,

$$ \int_{t_{\rho}}^{t} \sqrt{1 - f(s)} ds \le \sqrt{t - t_{\rho}} \left( \int_{t_{\rho}}^{t} (1 - f(s)) ds \right)^{1/2} = \sqrt{t - t_{\rho}} \sqrt{g(t) - g(t_{\rho})} \le \sqrt{\left(1 - \frac{1}{\rho}\right) tg(t)} $$

and hence

$$ \int_{0}^{t} \sqrt{1 - f_{0}(s)} ds \le \sqrt{\frac{4g(t)}{(1 - \theta)\rho r}} + \frac{t}{2}\sqrt{\frac{\delta}{1 - \theta}} + \sqrt{\frac{(\rho - 1)tg(t)}{\rho(1 - \theta)}} + \frac{t\sqrt{y}}{\sqrt{(1 - \theta)m(t)}} \sqrt{\frac{1}{2\theta}} + \frac{4}{3}. $$

Combining this bound with equations (58) and (59) finally yields

$$ g_2(t) \le g_0(t) + \frac{\sqrt{y} \left( 2\sqrt{2g(t)} + t\sqrt{\frac{r\delta}{2}} \right)}{\sqrt{(1-\theta)rm(t)}} + \sqrt{\frac{2(\rho-1)ytg(t)}{\rho(1-\theta)m(t)}} + \frac{yt}{m(t)} \left( \frac{4}{3} + \frac{1}{\sqrt{1-\theta}} \sqrt{\frac{8}{3} + \frac{1}{\theta}} \right) $$

and

$$ g_2(t) \ge g_0(t) - \frac{\sqrt{y} \left( 2\sqrt{2g(t)} + t\sqrt{\frac{r\delta}{2}} \right)}{\sqrt{(1-\theta)rm(t)}} - \sqrt{\frac{2(\rho-1)ytg(t)}{\rho(1-\theta)m(t)}} - \frac{yt}{m(t)} \left( \frac{4}{3} + \frac{1}{\sqrt{1-\theta}} \sqrt{\frac{8}{3} + \frac{1}{\theta}} \right), $$

from which the result follows by taking $\theta = \frac{1}{9}$.
C Proofs of subsection 3.1

In this section, we shall denote by $E_\eta$ the event on which $F \in [\hat{F}_j^-; \hat{F}_j^+]$ for all $j \in \{1, \dots, n\}$. For any $j \in \{1, \dots, n\}$ and $t \ge 0$, let

$$ \hat{m}_j(t) = |\mathcal{I}(j, t)| = \sum_{i=1}^{j-1} \mathbb{I}\{t \le \hat{\tau}_i\} $$

be the sample size available to estimate $F(t)$ at step $j$.

C.1 Preliminary results

First, we will need the following technical result, which proves that the supremum in equation (16) is in fact attained.

**Lemma C.1.** Let $[l; u]$ be a bracket in the set of non-decreasing functions bounded by 0 and 1. Then for any $T \ge 0$, the set

$$ \mathcal{X} = \bigcup_{f \in [l; u]} \operatorname{argmax}_{t \in [0; T]} \left\{ f(t) - c \int_0^t (1 - f(s)) ds \right\} $$

is right-closed, i.e for any bounded non-decreasing sequence $(t_k)_{k \ge 1}$ in $\mathcal{X}$,

$$ \lim_{k \to +\infty} t_k = \sup_{k \ge 1} \{t_k\} \in \mathcal{X}. $$

*Proof.* Let $(t_k)_{k \ge 1}$ be a bounded non-decreasing sequence in $\mathcal{X}$ and let $\tau$ be its limit. For every $k \ge 1$, let $f_k \in [l; u]$ be such that

$$ t_k \in \operatorname{argmax}_{t \in [0; T]} \left\{ f_k(t) - c \int_0^t (1 - f_k(s)) ds \right\}. $$

By Helly's selection theorem, we may assume without loss of generality that $(f_k)_{k \ge 1}$ converges pointwise to a monotone function $f$. Then $f \in [l; u]$ since $f_k(x) \in [l(x); u(x)]$ for all $k$ and $x$. By dominated convergence, we also have

$$ \int_0^t (1 - f_k(s)) ds \to \int_0^t (1 - f(s)) ds $$

for all $t \in [0; T]$. Fix some such $t$, then

$$ \begin{aligned} f(t) - c \int_0^t (1 - f(s)) ds &= \lim_{k \to +\infty} \left\{ f_k(t) - c \int_0^t (1 - f_k(s)) ds \right\} \\ &\le \limsup_{k \to +\infty} \left\{ f_k(t_k) - c \int_0^{t_k} (1 - f_k(s)) ds \right\}. \end{aligned} $$

Moreover, for any $k$, since $f_k$ is non-decreasing and $t_k \le \tau$,

$$ f_k(t_k) - c \int_0^{t_k} (1 - f_k(s)) ds \le f_k(\tau) - c \int_0^{t_k} (1 - f_k(s)) ds \le f_k(\tau) - c \int_0^{\tau} (1 - f_k(s)) ds + c(\tau - t_k) $$
It follows that

$$ \limsup_{k \to +\infty} \left\{ f_k(t_k) - c \int_0^{t_k} (1 - f_k(s)) ds \right\} \le f(\tau) - c \int_0^{\tau} (1 - f(s)) ds. $$

This proves that

$$ f(t) - c \int_0^t (1 - f(s)) ds \le f(\tau) - c \int_0^\tau (1 - f(s)) ds. $$

Since $t$ was arbitrary, it follows that

$$ \tau \in \operatorname{argmax}_{t \in [0; T]} \left\{ f(t) - c \int_{0}^{t} (1 - f(s)) ds \right\}. $$

Since $f \in [l; u]$, this proves that $\tau \in \mathcal{X}$. $\square$

Let us now prove lemma 3.2.

*Proof.* Observe first that since the policy $\hat{\tau}$ is given by Definition 3.1, the sequence $(\hat{\tau}_i)_{1 \le i \le n}$ is surely non-increasing (in particular, with probability 1). Let $E_\eta^0$ be the event given by equation (12). Fix some $k \in \{1, \dots, n\}$ and some $t \ge 0$. Since the sequence $(\hat{\tau}_i)_{1 \le i \le n}$ is non-increasing, there exists some integer $m \le k$ such that

$$ \mathcal{I}(k, t) = \{i \in \{1, \dots, k-1\} : \hat{\tau}_i \ge t\} = \{1, \dots, m\} $$

(with the convention that the above set is empty if $m=0$). Thus, on $E_\eta^0$,

$$ \tilde{F}_{n,\eta}^{-}((X_i)_{i \in \mathcal{I}(k,t)}) (t) = \tilde{F}_{n,\eta}^{-} (X_1, \dots, X_m) (t) \le F(t). $$

Similarly,

$$ \tilde{F}_{n,\eta}^{+}((X_i)_{i \in \mathcal{I}(k,t)}) (t) = \tilde{F}_{n,\eta}^{+} (X_1, \dots, X_m) (t) \ge F(t) $$

Thus,

$$ \tilde{F}_{n,\eta}^{-}((X_i)_{i \in \mathcal{I}(k,t)}) (t) \le F(t) \le \tilde{F}_{n,\eta}^{+}((X_i)_{i \in \mathcal{I}(k,t)}) (t) $$

for any $k \in \{1, \dots, n\}$, so

$$ \hat{F}_j^{-}(t) = \max_{1 \le k \le j} \left\{ \tilde{F}_{n,\eta}^{-}((X_i)_{i \in \mathcal{I}(k,t)}) (t) \right\} \le F(t) $$

and

$$ F(t) \le \min_{1 \le k \le j} \left\{ \tilde{F}_{n,\eta}^{+}((X_i)_{i \in \mathcal{I}(k,t)}) (t) \right\} = \hat{F}_{j}^{+}(t) $$

for all $j \in \{1, \dots, n\}$. $\square$

The following property is crucial.
**Proposition C.2.** Let

$$ \bar{\tau} = \sup \underset{t \in [0; \tau_1]}{\operatorname{argmax}} \{F(t) - cG(t)\} $$

On the event $E_\eta$, for all $j \le n$,

$$ \hat{\tau}_j \ge \hat{\tau}_n \ge \bar{\tau}. $$

*Proof.* By induction. On $E_\eta$, by definition, $F \in [\hat{F}_j^-; \hat{F}_j^+]$ for all $j \le n$. By definition, $\tau_1 \ge \bar{\tau}$. Assume by induction that $\hat{\tau}_{j-1} \ge \bar{\tau}$, then since $\hat{\tau}_{j-1} \le \tau_1$

$$ \bar{\tau} \in \underset{t \in [0; \hat{\tau}_{j-1}]}{\operatorname{argmax}} \{F(t) - cG(t)\}. $$

Since $F \in [\hat{F}_j^-; \hat{F}_j^+]$, it follows that

$$ \bar{\tau} \le \sup_{f \in [\hat{F}_j^-; \hat{F}_j^+]} \sup_{t \in [0; \hat{\tau}_{j-1}]} \underset{\tau_j \in [0; \bar{\tau}_j]}{\operatorname{argmax}} \left\{ f(t) - c \int_0^t (1 - f(s))ds \right\} = \hat{\tau}_j $$

which completes the induction step.

□

Finally, let us state a corollary of Proposition 4.6 for approximate maximizers of $f - cg$.

**Claim C.2.1.** Let $y = 2 \log n - \log \eta$. Let $f \in [\hat{F}_j^-; \hat{F}_j^+]$ and let $g : t \mapsto \int_0^t (1 - f(s))ds$. Let $\tau \in [0; \tau_M]$ be such that

$$ f(\tau) - cg(\tau) \ge \sup_{t \in [0; \tau_M]} \{f(t) - cg(t)\} - \delta. $$

Then for any $t \le \tau$,

$$ \hat{G}_j^+(t) - \hat{G}_j^-(t) \le \frac{6}{c} \sqrt{\frac{y(1+\delta)}{\hat{m}_j(t)}} + \frac{3t}{2} \sqrt{\frac{\delta y}{\hat{m}_j(t)}} + \frac{10yt}{\hat{m}_j(t)}. $$

*Proof.* Let

$$ f_0 : t \mapsto \tilde{F}((X_i)_{i \in \mathcal{I}(j,t)}) (t), $$

then by equations (19), (20) defining $\hat{F}_j^-, \hat{F}_j^+$,

$$ (w_{\hat{m}_j(t), \eta}^- \circ f_0)(t) = \tilde{F}_{n, \eta}^-((X_i)_{i \in \mathcal{I}(j,t)})(t) \le \hat{F}_j^-(t) $$

and

$$ \hat{F}_j^+(t) \le \tilde{F}_{n, \eta}^+((X_i)_{i \in \mathcal{I}(j,t)})(t) = (w_{\hat{m}_j(t), \eta}^+ \circ f_0)(t) $$
for all $t \ge 0$. Thus, $f \in [w_{\hat{m}_j, \eta}^{-} \circ f_0; w_{\hat{m}_j, \eta}^{+} \circ f_0]$. Moreover, by definition of $\tau$, for all $s \le \tau$,

$$f(s) - cg(s) \le f(\tau) - cg(\tau) + \delta$$

hence

$$c(g(\tau) - g(s)) \le f(\tau) - f(s) + \delta \le 1 - f(s) + \delta.$$

In particular, for all $s \le t$,

$$c(g(t) - g(s)) \le c(g(\tau) - g(s)) \le 1 - f(s) + \delta.$$

Thus, by proposition 4.6 with $r = c$, $\delta = \delta$ and $m = \hat{m}_j$,

$$\hat{G}_j^+(t) \le g_0(t) + 3\sqrt{\frac{yg(t)}{c\hat{m}_j(t)}} + \frac{3t}{4}\sqrt{\frac{\delta y}{\hat{m}_j(t)}} + 5\frac{yt}{\hat{m}_j(t)}$$

$$\hat{G}_j^-(t) \ge g_0(t) - 3\sqrt{\frac{yg(t)}{c\hat{m}_j(t)}} - \frac{3t}{4}\sqrt{\frac{\delta y}{\hat{m}_j(t)}} - 5\frac{yt}{\hat{m}_j(t)}$$

where $g_0 : t \mapsto \int_0^t (1 - f_0(s))ds$. It follows that

$$\hat{G}_j^+(t) - \hat{G}_j^-(t) \le 6\sqrt{\frac{yg(t)}{c\hat{m}_j(t)}} + \frac{3t}{2}\sqrt{\frac{\delta y}{\hat{m}_j(t)}} + \frac{10yt}{\hat{m}_j(t)}$$

To conclude, remark that by optimality of $\tau$,

$$0 \le f(0) = f(0) - cg(0) \le f(\tau) - cg(\tau) + \delta$$

from which it follows that

$$g(t) \le g(\tau) \le \frac{f(\tau) + \delta}{c} \le \frac{1 + \delta}{c}.$$

□

## C.2 Proof of Theorem 3.3

Let us now analyze the regret of policy 3.1. Let $y = -\log \eta + 2\log n$. First, consider the event $E_\eta$. Let

$$\bar{\tau} = \sup \underset{t \in [0; \tau_1]}{\operatorname{argmax}} \{F(t) - cG(t)\}.$$

By Proposition C.2, on $E_\eta$, $\hat{\tau}_j \ge \bar{\tau}$ for all $j$. Since the sequence $(\hat{\tau}_j)_{1 \le j \le n}$ is adapted with respect to the filtration $(\mathcal{F}_j)_{1 \le j \le n}$, we have that $X_j$ is independent from $\hat{\tau}_j$ for all $j$ and in particular,

$$\mathbb{E} \left[ \sum_{j=1}^{n} \mathbb{I}\{X_j \le \hat{\tau}_j\} - c(X_j \wedge \hat{\tau}_j) \right] = \mathbb{E} \left[ \sum_{j=1}^{n} F(\hat{\tau}_j) - cG(\hat{\tau}_j) \right]. \quad (60)$$
Fix some $j \in \{2, \dots, n\}$. By definition of $\hat{\tau}_j$ and lemma C.1, there exists $\overline{F}_j \in [\hat{F}_j^-; \hat{F}_j^+]$ such that

$$ \hat{\tau}_j \in \operatorname{argmax}_{t \in [0; \hat{\tau}_{j-1}]} \left\{ \overline{F}_j(t) - c \int_0^t (1 - \overline{F}_j(s)) ds \right\}. $$

Define the function

$$ \overline{G}_j : t \mapsto \int_0^t (1 - \overline{F}_j(s)) ds. $$

Write

$$ F(\hat{\tau}_j) - cG(\hat{\tau}_j) = (F - \overline{F}_j)(\hat{\tau}_j) + (\overline{F}_j(\hat{\tau}_j) - c\overline{G}_j(\hat{\tau}_j)) + c(\overline{G}_j(\hat{\tau}_j) - G(\hat{\tau}_j)). $$

On $E_\eta, \bar{\tau} \in [0; \hat{\tau}_{j-1}]$, so by definition of $\hat{\tau}_j$,

$$ \begin{aligned} F(\hat{\tau}_j) - cG(\hat{\tau}_j) &\ge (F - \overline{F}_j)(\hat{\tau}_j) + (\overline{F}_j(\bar{\tau}) - c\overline{G}_j(\bar{\tau})) + c(\overline{G}_j - G)(\hat{\tau}_j) \\ &= (F(\bar{\tau}) - cG(\bar{\tau})) + (F - \overline{F}_j)(\hat{\tau}_j) + (\overline{F}_j - F)(\bar{\tau}) \\ &\quad + c(G - \overline{G}_j)(\bar{\tau}) + c(\overline{G}_j - G)(\hat{\tau}_j) \\ &\ge (F(\bar{\tau}) - cG(\bar{\tau})) - 2 \sup_{t \le \hat{\tau}_{j-1}} |(F - \overline{F}_j)(t)| + c(G - \overline{G}_j)(\bar{\tau}) + c(\overline{G}_j - G)(\hat{\tau}_j). \end{aligned} $$

On $E_\eta$, we have that $F, \overline{F}_j \in [\hat{F}_j^-; \hat{F}_j^+]$, so

$$ \begin{aligned} \sup_{t \le \hat{\tau}_{j-1}} |(F - \overline{F}_j)(t)| &\le \sup_{t \le \hat{\tau}_{j-1}} |\hat{F}_j^+(t) - \hat{F}_j^-(t)| \\ &\le \sup_{t \le \hat{\tau}_{j-1}} \|w_{\hat{m}_j(t), \eta}^+ - w_{\hat{m}_j(t), \eta}^-\|_{\infty} \text{ by equations (13), (14) and (15)} \\ &\le \sqrt{\frac{2y}{\hat{m}_j(\hat{\tau}_{j-1})}} \text{ by Proposition 4.4} \\ &= \sqrt{\frac{2y}{j-1}} \text{ since } (\hat{\tau}_i)_{1 \le i \le n} \text{ is non-increasing} \end{aligned} $$

Thus,

$$ F(\hat{\tau}_j) - cG(\hat{\tau}_j) \ge F(\bar{\tau}) - cG(\bar{\tau}) - 2\sqrt{\frac{2y}{j-1}} + c(G - \overline{G}_j)(\bar{\tau}) + c(\overline{G}_j - G)(\hat{\tau}_j). \tag{61} $$

Moreover, $\overline{F}_j \in [\hat{F}_j^-; \hat{F}_j^+]$ by definition and, on $E_\eta$, $F \in [\hat{F}_j^-; \hat{F}_j^+]$ also. It follows from claim C.2.1 that on $E_\eta$,

$$ (G - \overline{G}_j)(\hat{\tau}_j) \le (\hat{G}_j^+ - \hat{G}_j^-)(\hat{\tau}_j) \le \frac{6}{c} \sqrt{\frac{y}{j-1}} + 10 \frac{y \hat{\tau}_j}{j-1} $$

and

$$ (\overline{G}_j - G)(\bar{\tau}) \le (\hat{G}_j^+ - \hat{G}_j^-)(\bar{\tau}) \le \frac{6}{c} \sqrt{\frac{y}{j-1}} + 10 \frac{y \bar{\tau}}{j-1}. $$
and hence

$$c(G - \bar{G}_j)(\hat{\tau}_j) + c(\bar{G}_j - G)(\bar{\tau}) \le 12\sqrt{\frac{y}{j-1}} + 20\frac{yc\tau_1}{j-1}$$

on $E_\alpha$.

Let $\tau_1 = \frac{\lambda}{c}$. It follows from equation (61) that

$$F(\hat{\tau}_j) - cG(\hat{\tau}_j) \ge F(\bar{\tau}) - cG(\bar{\tau}) - (12 + 2\sqrt{2})\sqrt{\frac{y}{j-1}} - 20\frac{\lambda y}{j-1}.$$

When $j = 1$, we have that

$$F(\tau_1) - cG(\tau_1) \ge -c\tau_1 \ge -\lambda \ge V_c^*(F) - (\lambda + 1).$$

If $\tau_c^* \le \bar{\tau}$, then by definition of $\bar{\tau}$,

$$F(\bar{\tau}) - cG(\bar{\tau}) \ge F(\tau_c^*) - cG(\tau_c^*) = V_c^*(F).$$

Otherwise, $\tau_c^* \ge \tau_1$ and

$$F(\bar{\tau}) - cG(\bar{\tau}) \ge F(\tau_1) - cG(\tau_1).$$

Since $\tau_1 \le \tau_c^*$, we have that

$$\frac{1}{c} \ge G(\tau_c^*) \ge G(\tau_1) \ge \tau_1(1 - F(\tau_1))$$

which implies that

$$1 - F(\tau_1) \le \frac{1}{c\tau_1} = \frac{1}{\lambda}$$

and yields

$$F(\bar{\tau}) - cG(\bar{\tau}) \ge 1 - \frac{1}{\lambda} - cG(\tau_1) \ge F(\tau_c^*) - \frac{1}{\lambda} - cG(\tau_c^*) \ge V_c^*(F) - \frac{1}{\lambda}.$$

It follows that in either case,

$$F(\bar{\tau}) - cG(\bar{\tau}) \ge V_c^*(F) - \frac{1}{\lambda}.$$

Thus, on the event $E_\eta$,

$$\begin{aligned} \sum_{j=1}^{n} F(\hat{\tau}_j) - cG(\hat{\tau}_j) &\ge nV_c^*(F) - \frac{n}{\lambda} - (\lambda + 1) - (12 + 2\sqrt{2})\sqrt{y} \sum_{j=1}^{n-1} \frac{1}{\sqrt{j}} - 20\lambda y \sum_{j=1}^{n-1} \frac{1}{j} \\ &\ge V_c^*(F) - \frac{n}{\lambda} - 2(12 + 2\sqrt{2})\sqrt{yn} - 1 - \lambda - 20y\lambda(1 + \log n) \end{aligned}$$

Outside $E_\eta$,

$$\sum_{j=1}^{n} F(\hat{\tau}_j) - cG(\hat{\tau}_j) \ge -c \sum_{j=1}^{n} G(\hat{\tau}_j) \ge -ncG(\tau_1) \ge -nc\tau_1 = -\lambda n.$$
Since $V_c^*(F) \le 1$, the regret is at most

$$R_{n,c}^{\text{pen}}(P, \hat{\tau}) \le \frac{n}{\lambda} + (24 + 4\sqrt{2})\sqrt{yn} + 20\lambda y(1 + \log n) + \lambda + 1 + \eta n(\lambda + 1)$$

Take then

$$\eta = \frac{1}{n}$$
$$\lambda = \frac{\sqrt{n}}{1 + \log n}.$$

In particular, $y = 3 \log n$. The above bounds then yield

$$R_{n,c}^{\text{pen}}(P, \hat{\tau}) \le \sqrt{n}(1 + \log n) + (24 + 4\sqrt{2})\sqrt{3n \log n} + 60 \log n \sqrt{n} + \frac{2\sqrt{n}}{1 + \log n} + 2.$$

It is easy to see that each of the terms is at most of order $\sqrt{n} \log n$.

### C.3 Proof of Theorem 3.4

Let $\delta \in [0; 1)$ be a parameter, to be chosen later. Let $P$ denote the exponential distribution with parameter $c$. Let $Q_0$ be the uniform distribution on $[0; \frac{4}{3c}]$ and $Q_1$ be the uniform distribution on $[\frac{2}{3c}; \frac{2}{c}]$. Define the two hypotheses

$$P_0 = (1 - \delta)P + \delta Q_0 \quad (62)$$

$$P_1 = (1 - \delta)P + \delta Q_1. \quad (63)$$

For $\eta \in \{0; 1\}$, let $F_\eta$ be the cumulative distribution function of $P_\eta$ and let $G_\eta$: $t \mapsto \int_0^t (1 - F_\eta(s))ds$. Let $f_\eta, g_\eta$ denote the corresponding functions associated with the uniform distribution $Q_\eta$. Elementary computations yield

$$\begin{align*}
f_0(t) &= \min\left(\frac{3}{4}ct, 1\right) \\
g_0(t) &= \min\left(t - \frac{3}{8}ct^2, \frac{2}{3c}\right) \\
f_1(t) &= \min\left(\frac{1}{2}\left(\frac{3c}{2}t - 1\right)_+, 1\right) \\
g_1(t) &= \min\left(t - \frac{3c}{8}\left(t - \frac{2}{3c}\right)_+^2, \frac{4}{3c}\right).
\end{align*}$$

Define the objective function

$$M_\eta = F_\eta - cG_\eta$$

and remark that

$$M_\eta = \delta(f_\eta - c g_\eta) \text{ and } V_c^*(P_\eta) = \sup M_\eta = \delta V_c^*(Q_\eta)$$
Let $P_\eta$, $E_\eta$ denote probabilities and expectations taken with respect to an i.i.d sample $(X_i)_{1\le i\le n}$ drawn from $P_\eta$.

Since $f_0$ is linear on $[0; 1/c)$, $M_0$ is convex on this interval and

$$ \sup_{t \in [0; \frac{1}{c}]} M_0(t) = \max \left( M_0(0); M_0\left(\frac{1}{c}\right) \right) = \frac{\delta}{8} \le M_0\left(\frac{4}{3c}\right) = \frac{\delta}{3}. $$

It follows that

$$ \mathbb{E}_0 [V_c^*(P_0) - M_0(\hat{\tau}_j)] \ge \frac{\delta}{5} \mathbb{P}_0 \left( \hat{\tau}_j < \frac{1}{c} \right). $$

Similarly, $M_1$ is convex on $[\frac{1}{c}; \frac{2}{c}]$ and constant on $[\frac{2}{c}; +\infty)$, so

$$ \sup_{t \ge \frac{1}{c}} M_1(t) = \max \left( M_1\left(\frac{1}{c}\right), M_1\left(\frac{2}{c}\right) \right) = \delta \max \left( -\frac{3}{4} + \frac{1}{24}, -\frac{1}{3} \right) = -\frac{\delta}{3}. $$

which yields

$$ \mathbb{E}_1 [V_c^*(P_1) - M_1(\hat{\tau}_j)] \ge \frac{\delta}{3} \mathbb{P}_1 \left( \hat{\tau}_j \ge \frac{1}{c} \right). $$

Since $\hat{\tau}_j$ is a measurable function of $X_1, \dots, X_{j-1}$, it follows that

$$ \begin{aligned} \mathbb{E}_0 [V_c^*(P_0) - M_0(\hat{\tau}_j)] + \mathbb{E}_1 [V_c^*(P_1) - M_0(\hat{\tau}_j)] & \\ & \ge \frac{\delta}{5} \left( \mathbb{P}_0 \left( \hat{\tau}_j < \frac{1}{c} \right) + \mathbb{P}_1 \left( \hat{\tau}_j \ge \frac{1}{c} \right) \right) \\ & \ge \frac{\delta}{5} \left( 1 - d_{TV} \left( P_0^{\otimes(j-1)}, P_1^{\otimes(j-1)} \right) \right). \end{aligned} $$

By Pinsker's inequality,

$$ \mathbb{E}_0 [V_c^*(P_0) - M_0(\hat{\tau}_j)] + \mathbb{E}_1 [V_c^*(P_1) - M_0(\hat{\tau}_j)] \ge \frac{\delta}{5} \psi((j-1)D_{\text{KL}}(P_0||P_1)) \quad (64) $$

where $\psi(x) = 1 - \sqrt{\frac{x}{2}}$. Remark that

$$ \frac{dP_0}{dP_1} = \frac{(1-\delta)ce^{-ct} + \frac{3c}{4}\delta}{(1-\delta)ce^{-ct}} \mathbb{I}\left\{\left[0; \frac{2}{3c}\right]\right\} + \frac{(1-\delta)ce^{-ct}}{(1-\delta)ce^{-ct} + \frac{3c}{4}\delta} \mathbb{I}\left\{\left[\frac{4}{3c}; \frac{2}{c}\right]\right\} \\ + \mathbb{I}\left\{\left(\frac{2}{3c}; \frac{4}{3c}\right) \cup \left[\frac{2}{c}; +\infty\right)\right\} $$

which yields

$$ \begin{aligned} D_{\text{KL}}(P_0||P_1) = & \int_0^{\frac{2}{3c}} \log \left( 1 + \frac{3\delta e^{ct}}{4(1-\delta)} \right) \left( (1-\delta)ce^{-ct} + \frac{3c}{4}\delta \right) dt \\ & - \int_{\frac{4}{3c}}^{\frac{2}{c}} \log \left( 1 + \frac{3\delta e^{ct}}{4(1-\delta)} \right) (1-\delta)ce^{-ct} dt. \end{aligned} $$
Setting $\lambda = \frac{3\delta}{4(1-\delta)}$ and using the elementary inequalities $\frac{u}{u+1} \le \log(1+u) \le u$ yields

$$
\begin{align*}
D_{\text{KL}}(P_0||P_1) &\le \frac{3c}{4}\delta \int_0^{\frac{2}{3c}} \log\left(1 + \frac{3\delta e^{ct}}{4(1-\delta)}\right) dt + \lambda c(1-\delta)\frac{2}{3c} - c(1-\delta) \int_{\frac{4}{3c}}^{\frac{2}{c}} \frac{\lambda}{1+\lambda e^{ct}} dt \\
&\le \frac{3c\delta}{4}\lambda \int_0^{\frac{2}{3c}} e^{ct} dt + \lambda c(1-\delta) \int_{\frac{1}{3c}}^{\frac{2}{c}} \frac{\lambda e^{ct}}{1+\lambda e^{ct}} dt \\
&\le \frac{9\delta^2}{16(1-\delta)} (e^{\frac{2}{3}} - 1) + \lambda^2(1-\delta) \int_{\frac{4}{3c}}^{\frac{2}{c}} c e^{ct} dt \\
&\le \frac{9}{16} \frac{\delta^2}{1-\delta} (e^{\frac{2}{3}} - 1 + e^2 - e^{\frac{4}{3}})
\end{align*}
$$

Let $\mu = \frac{9}{16}(e^2 - e^{\frac{4}{3}} + e^{\frac{2}{3}} - 1)$ and fix some $\theta > 0$ (to be chosen later). Choosing

$$
\delta \le \sqrt{\frac{\theta}{\mu n}} \left( \sqrt{1 + \frac{\theta}{4\mu n}} - \frac{1}{2}\sqrt{\frac{\theta}{\mu n}} \right)
$$

yields

$$
D_{\text{KL}}(P_0||P_1) \leq \mu \frac{\delta^2}{1-\delta} \leq \frac{\theta}{n}
$$

and hence, by equation 64,

$$
\begin{align*}
R_{n,c}^{\text{pen}}(P_0, \hat{\tau}) + R_{n,c}^{\text{pen}}(P_1, \hat{\tau}) &= \sum_{j=1}^{n} \mathbb{E}_0 [V_c^*(P_0) - M_0(\hat{\tau}_j)] + \mathbb{E}_1 [V_c^*(P_1) - M_0(\hat{\tau}_j)] \\
&\geq \frac{\delta}{5} \sum_{j=1}^{n} \psi \left( \theta \frac{j-1}{n} \right) \\
&\geq \frac{1}{5} \left( \sqrt{\frac{\theta}{\mu n}} - \frac{1}{2} \frac{\theta}{\mu n} \right) \sum_{j=1}^{n} \psi \left( \theta \frac{j-1}{n} \right) \\
&= \frac{1}{5} \left( \sqrt{\frac{\theta}{\mu} n} - \frac{1}{2} \frac{\theta}{\mu} \right) \frac{1}{n} \sum_{j=1}^{n} \psi \left( \theta \frac{j-1}{n} \right) \\
&\geq \frac{1}{5} \left( \sqrt{\frac{\theta}{\mu} n} - \frac{1}{2} \frac{\theta}{\mu} \right) \int_0^1 \psi(\theta x) \, dx \quad \text{since } \psi \text{ is non-increasing} \\
&= \frac{1}{5} \left( \sqrt{\frac{n}{\mu \theta}} - \frac{1}{2\mu} \right) \int_0^\theta \left(1 - \sqrt{\frac{s}{2}}\right) \, ds \\
&= \frac{1}{5} \left( \sqrt{\frac{n}{\mu \theta}} - \frac{1}{2\mu} \right) \left( \theta - \frac{\sqrt{2}}{3} \theta \sqrt{\theta} \right).
\end{align*}
$$
The leading term reaches its maximum at $\theta = \frac{9}{8}$, hence

$$ 
\begin{aligned}
R_{n,c}^{\text{pen}}(P_0, \hat{\tau}) + R_{n,c}^{\text{pen}}(P_1, \hat{\tau}) &\ge \frac{1}{5} \left( \frac{3\sqrt{n}}{4\sqrt{2\mu}} - \frac{9}{32\mu} \right) \\
&\ge \frac{1}{5} (0.33\sqrt{n} - 0.2).
\end{aligned}
$$

This yields the result since

$$ \max_{P \in \mathcal{P}_{\varepsilon}} R_{n,c}^{\text{pen}}(P_0, \hat{\tau}) \ge \max_{\eta \in \{0;1\}} R_{n,c}^{\text{pen}}(P_{\eta}, \hat{\tau}) \ge \frac{1}{10} (0.33\sqrt{n} - 0.2) $$

whenever

$$ \max_{\eta \in \{0,1\}} V_c^*(P_\eta) = \delta \max_{\eta \in \{0,1\}} V_c^*(Q_\eta) = \frac{\delta}{3} \le \frac{1}{3} \sqrt{\frac{\theta}{\mu n}} \le \varepsilon, $$

i.e whenever

$$ n \ge \frac{\theta}{9\mu\varepsilon^2} = \frac{1}{8\mu\varepsilon^2}. $$

## D Proof of Theorem 3.9

If $\alpha_* T \le 59\sqrt{\alpha_* T \log^3 n}$, the bound of Theorem 3.9 is trivial. Otherwise, we have that

$$ \sqrt{n} \ge \sqrt{\alpha_* T} \ge 59 \log^{3/2} n \qquad (65) $$

which means that

$$ n \ge n_0 = \min \left\{ k \in \mathbb{N} : \frac{k}{\log^3(k)} \ge 3481 \right\} = 15864471. \qquad (66) $$

We therefore assume that $n \ge n_0$, so as to simplify the second-order terms. Then

$$ z = 2 \log n - \log \eta + \log(K) \le \frac{5}{2} \log n + \log \left( \frac{\log n}{\log 2} + 1 \right) \le 2.7 \log n \qquad (67) $$

and

$$ zK \log n \le 2.7 \log^2 n \left( \frac{\log n}{\log 2} + 1 \right) \le \log^3 n \left( 3.9 + \frac{2.7}{\log(n_0)} \right) \le 4.1 \log^3 n. \qquad (68) $$

Introduce first the following notation that will be used throughout the proof.

$$ \rho_j = \left( 1 - \frac{\varepsilon}{\left(1 + 2\sqrt{\hat{\alpha}_j^+ T}\right)^3} \right)^{-1}. $$
Let

$$ \hat{n}_t = \max \left\{ j \le n : \sum_{i=1}^{j-1} X_i \wedge \hat{\tau}_i \le T - t_{K_j} \right\}. $$

Since $(t_{K_j})$ is a non-decreasing sequence,

$$ \sum_{i=1}^{j-1} X_i \wedge \hat{\tau}_i \le T - t_{K_j} $$

for all $j \le \hat{n}_t$. Let also

$$ \hat{n}_{cb} = \max \{ j \le n : F \in [\hat{F}_j^{-}; \hat{F}_j^{+}] \}. $$

Since the confidence bands $[\hat{F}_j^{-}; \hat{F}_j^{+}]$ are nested, $j \le \hat{n}_{cb}$ if and only if $F \in [\hat{F}_j^{-}; \hat{F}_j^{+}]$. Let $E_\eta$ denote the event $\{\hat{n}_{cb} = n\}$, which by equation (12) has probability $P(E_\eta) \ge 1 - \eta$. Remark that both $\hat{n}_t$ and $\hat{n}_{cb}$ are stopping times with respect to the natural filtration $\sigma(X_1, \dots, X_j)_{j \ge 1}$. Let $\hat{n} = \min(\hat{n}_t, \hat{n}_{cb})$.

For all $j \in \{1, \dots, n\}$, let

$$ m_j = \max_{0 \le k \le K-1} |\mathcal{I}(k, j, \hat{\tau}_j)|. $$

Similarly, for all $t \ge 0$, let

$$ m_j(t) = \max_{0 \le k \le K-1} |\mathcal{I}(k, j, t)|. $$

Note that by definition, $m_j(t)$ is non-increasing in $t$ and non-decreasing in $j$. Moreover, we have that for all $t \ge 0$ and $j$,

$$ w_{m_j(t), \eta}^{-}(\tilde{f}_j(t)) \le \hat{F}_j^{-}(t) \le \hat{F}_j^{+}(t) \le w_{m_j(t), \eta}^{+}(\tilde{f}_j(t)), \quad (69) $$

where

$$ \tilde{f}_j : t \mapsto \tilde{F}((X_i)_{i \in \mathcal{I}(k(t), j, t)}) \text{ with } k(t) \in \operatorname*{argmax}_{0 \le k \le K-1} |\mathcal{I}(k, j, t)|. $$

Define also the sets

$$ J_r = \{j \le \hat{n} : m_j \ge r\}. $$

## D.1 Preliminary results

Let us first show that the supremum is attained in the definition of $\hat{\tau}_j$.

**Lemma D.1.** Let $[f_l; f_u]$ be a bracket in the set of non-decreasing functions bounded by 0 and 1. For any $\tau \ge 0$, the set

$$ \mathcal{X}_{\tau} = \bigcup_{f \in [f_l; f_u]} \operatorname*{argmax}_{t \in (0; \tau]} \left\{ \frac{f(t)}{\int_0^{+\infty} \min(s, t) df(s)} \right\} $$
is right-closed, i.e for any bounded non-decreasing sequence $(t_k)_{k \ge 1}$ in $\mathcal{X}_\tau$,

$$ \lim_{k \to +\infty} t_k = \sup_{k \ge 1} \{t_k\} \in \mathcal{X}_\tau. $$

*Proof.* Similar to that of lemma C.1. If $\mathcal{X}_\tau$ is empty, it is closed. Otherwise, $(t_k)_{k \ge 1}$ be a non-decreasing sequence in $(0; \tau]$ and let $t_\infty$ be its limit. For each positive integer $k$, let $(f_k, g_k)$ be such that

$$ t_k \in \underset{t \in [0; \tau]}{\operatorname{argmax}} \left\{ \frac{f_k(t)}{g_k(t)} \right\} \quad \text{and} \quad g_k(t) = \int_0^{+\infty} \min(s, t) df_k(s) = \int_0^t (1-f_k(s)) ds \quad \text{for all } t \in [0; \tau]. $$

By Helly's selection theorem, we may extract a pointwise convergent sub-sequence $(f_{\phi(k)})$. Let $f$ be its limit, $f$ is a non-decreasing function. Let

$$ g : t \mapsto \int_0^t (1 - f(s)) ds. $$

By the dominated convergence theorem, it follows that $(g_{\phi(k)})_{k \ge 1}$ converges pointwise to $g$. Moreover, for any $t \in [0; \tau]$ and $k \in \mathbb{N}^*$,

$$ \frac{f_k(t)}{g_k(t)} \le \frac{f_k(t_k)}{g_k(t_k)} \le \frac{f_k(t_\infty)}{g_k(t_k)} = \frac{g_k(t_\infty)}{g_k(t_k)} \frac{f_k(t_\infty)}{g_k(t_\infty)} \le \frac{t_\infty}{t_k} \frac{f_k(t_\infty)}{g_k(t_\infty)} $$

Taking a limit along the subsequence $(\phi(k))_{k \ge 1}$ yields

$$ \frac{f(t)}{g(t)} \le \frac{f(t_\infty)}{g(t_\infty)} $$

by pointwise convergence of $(f_{\phi(k)})$ and $(g_{\phi(k)})$. $\square$

The following bounds play an important role throughout the proof.

**Claim D.1.1.** Let $r \ge 1$ be an integer. Let $X$ be a non-negative random variable,

$$ g : t \mapsto \mathbb{E}[\min(X, t)] \quad \text{and} \quad v : t \mapsto \operatorname{Var}(\min(X, t)). $$

Then

$$ \begin{aligned} \sum_{j=1}^{\hat{n}} \mathbb{I}\{j \notin J_r\} &\le rK \\ \sum_{j=1}^{\hat{n}} g(\hat{\tau}_j) \mathbb{I}\{j \notin J_r\} &\le 2r \sqrt{\frac{T}{\alpha_*}} \\ \sum_{j=1}^{\hat{n}} v(\hat{\tau}_j) \mathbb{I}\{j \notin J_r\} &\le \frac{8}{3} r \frac{T}{\alpha_*}. \end{aligned} $$
Proof. Let $a \in \{0, 1, 2\}$ and

$$ \hat{k} = \min \{K_j : 1 \le j \le \hat{n}\}. $$

For any $k \in \{0, \dots, K-1\}$ and any $j \in \{1, \dots, \hat{n}\}$, let

$$ S_{k,j} = \sum_{i=1}^{j-1} \mathbb{I}\{\hat{\tau}_i \in B_k\}. $$

Since the sequence $(\hat{\tau}_i)_{1 \le i \le \hat{n}}$ is non-increasing on each set $B_k$, it follows that

$$ \hat{\tau}_j \in B_k \implies m_j \ge S_{k,j}. $$

For any $j \le \hat{n}$, $\hat{\tau}_j \le t_{K_j} \le t_{\hat{k}}$, hence $\hat{\tau}_j \in B_k$ for some $k \ge \hat{k}$. It follows that

$$ \begin{aligned} \sum_{j=1}^{\hat{n}} \hat{\tau}_j^a \mathbb{I}\{j \notin J_r\} &= \sum_{k=\hat{k}}^{K-1} \sum_{j=1}^{\hat{n}} \hat{\tau}_j^a \mathbb{I}\{\hat{\tau}_j \in B_k\} \mathbb{I}\{S_{k,j} < r\} \\ &\le \sum_{k=\hat{k}}^{K-1} t_k^a \sum_{j=1}^{\hat{n}} \mathbb{I}\{\hat{\tau}_j \in B_k\} \mathbb{I}\{S_{k,j} \le r-1\} \\ &\le \sum_{k=\hat{k}}^{K-1} r t_k^a. \end{aligned} $$

If $a=0$, this yields

$$ \sum_{j=1}^{\hat{n}} \mathbb{I}\{j \notin J_r\} \le rK. $$

If $a > 0$, then

$$ \begin{aligned} \sum_{j=1}^{\hat{n}} \hat{\tau}_j^a \mathbb{I}\{j \notin J_r\} &\le r t_{\hat{k}}^a \sum_{k=0}^{+\infty} 2^{-ak} \\ &\le \frac{2^a r}{2^a - 1} t_{\hat{k}}^a. \end{aligned} $$

Now, by definition, for any $j \le \hat{n}$, $(F, G) \in \mathbb{H}_j$ and hence

$$ t_{K_j} = 2t_{K_{j+1}} \le 2\sqrt{\frac{T}{\hat{\alpha}_j^+}} \le 2\sqrt{\frac{T}{\alpha_*}}. $$

This yields

$$ \sum_{j=1}^{\hat{n}} \hat{\tau}_j^a \mathbb{I}\{j \notin J_r\} \le \frac{4^a r}{2^a - 1} \left(\frac{T}{\alpha_*}\right)^{\frac{a}{2}}. $$

To conclude remark that

$$ g(t) \le t \text{ and } v(t) \le tg(t) - g(t)^2 = g(t)(t - g(t)) \le \frac{t^2}{2}. $$

□
The following bounds deal with sums of inverse powers of $m_j$ which appear in confidence bounds.

**Claim D.1.2.** For any $r \ge 1$,

$$ \sum_{j \in J_r} \frac{1}{\sqrt{m_j}} \le 2\sqrt{K(n-K)}. $$

For any $r \ge 1$

$$ \sum_{j \in J_r} \frac{1}{m_j} \le K \log n \quad (70) $$

and for any $r \ge 2$ and $a \ge 1$,

$$ \sum_{j \in J_r} \frac{\hat{\tau}_j^a}{m_j} \le \frac{4^a}{2^a - 1} \log(\hat{n}) \left( \frac{T}{\alpha_* \log n} \right)^{a/2} $$

*Proof.* Let $a \in \{0, 1, 2\}$ and

$$ \hat{k} = \min \{K_j : 1 \le j \le \hat{n}\}. $$

For any $j \le \hat{n}$, $\hat{\tau}_j \le t_{K_j} \le t_{\hat{k}}$, hence $\hat{\tau}_j \in B_k$ for some $k \ge \hat{k}$. For any $k \le \hat{k}$, let $n_k$ be the number of indices $j \le \hat{n}$ such that $\hat{\tau}_j \in (t_{k+1}; t_k]$. Let $(\hat{\tau}_{k,i})_{1 \le i \le m_k}$ be those thresholds, ordered as in the sequence $(\hat{\tau}_j)_{1 \le j \le n}$ - that is to say, in non-increasing order. Let $j(k, i)$ be the index corresponding to $\hat{\tau}_{k,i}$. Then by definition of $\mathcal{I}(k, j, t)$,

$$ \hat{m}_{j(k,i)} \ge i - 1. $$

It follows that

$$ \begin{aligned} \sum_{j \in J_r} \frac{1}{\sqrt{m_j}} &\le \sum_{k=0}^{K-1} \sum_{i=r+1}^{n_k} \frac{1}{\sqrt{i-1}} \\ &\le \sum_{k=0}^{K-1} \sum_{i=r+1}^{n_k} \int_{i-2}^{i-1} \frac{dt}{\sqrt{t}} \\ &\le \sum_{k=0}^{K-1} \int_{r-1}^{n_k-1} \frac{dt}{\sqrt{t}} \\ &\le 2 \sum_{k=0}^{K-1} (\sqrt{n_k-1} - \sqrt{r-1})_+ \\ &\le 2\sqrt{K(n-K)} \end{aligned} $$
and that

$$ 
\begin{aligned}
\sum_{j \in J_r} \frac{\hat{\tau}_j^a}{m_j} &\le \sum_{k=\hat{k}}^{K-1} \sum_{i=r+1}^{n_k} \frac{\hat{\tau}_{k,i}^a}{i-1} \\
&\le \sum_{k=\hat{k}}^{K-1} t_k^a \sum_{i=r}^{n_k-1} \frac{1}{i}.
\end{aligned}
$$

For $a = 0$, it follows that

$$ 
\begin{aligned}
\sum_{j \in J_r} \frac{\hat{\tau}_j^a}{m_j} &\le \sum_{k=\hat{k}}^{K-1} \left( \frac{1}{r} + \sum_{i=r}^{n_k-1} \int_i^{i+1} \frac{dt}{t} \right) \\
&\le \frac{K}{r} + \sum_{k=0}^{K-1} \log \left( \frac{n_k}{r} \right)_+ \\
&\le \frac{K}{r} + \max_{j \le K} j \log \left( \frac{n}{rj} \right)
\end{aligned}
$$

by concavity of the logarithm. Note that the function $\lambda \mapsto \lambda \log(\frac{n}{\lambda})$ is non-decreasing on $(0; \frac{n}{e}]$. Assume that $r = 1$. If $2^{j_0} \ge \lambda j_0$ for some natural number $j$, then the same holds for all $j \ge j_0$ by induction. Letting $\lambda = 2e$ and $j_0 = 5$, we find that $2^5 = 32 \ge 10e = \lambda j_0$ and hence

$$ \frac{n}{e} \ge \log_2 \left( 2e \frac{n}{e} \right) = \log_2(n) + 1 $$

for all $n \ge 15 \ge e j_0$. For such $n$,

$$ \sum_{j \in J_r} \frac{1}{m_j} \le K + K \log \left( \frac{n}{K} \right) \le K \log n. $$

Now, for $a \ge 1$ and $r \ge 2$,

$$ 
\begin{aligned}
\sum_{j \in J_r} \frac{\hat{\tau}_j^a}{m_j} &\le \sum_{k=\hat{k}}^{K-1} t_k^a \log(n_k) \\
&\le \log(\hat{n}) \sum_{k=\hat{k}}^{K-1} t_k^a \\
&= t_{\hat{k}}^a \log(\hat{n}) \sum_{k=0}^{+\infty} 2^{-ka} \\
&\le 2^a \log(\hat{n}) \left( \frac{T}{\alpha_* \log n} \right)^{\frac{a}{2}} \frac{2^a}{2^a - 1}
\end{aligned}
$$
since by definition,

$$ t_{\hat{k}} = \max \{t_{K_j} : j \le \hat{n}\} \le 2 \max \left\{ \sqrt{\frac{T}{\hat{\alpha}_j^+ \log n}} : j \le n, F \in [\hat{F}_j^-; \hat{F}_j^+] \right\} \le 2 \sqrt{\frac{T}{\alpha_* \log n}}. \quad \square $$

Let us now establish some properties of $\hat{\alpha}_j^+$, $\mathbb{H}_j$ and $\tau_j^*$.

**Claim D.1.3.** Assume $\mathbb{H}_j$ is non-empty. Let $F_0 \in [\hat{F}_j^-; \hat{F}_j^+]$ and $G_0 : t \mapsto \int_0^t (1-F_0(s))ds$. There exists $(f_i, g_i)_{i \in \{1,2\}} \in O_j$ such that

$$ \begin{aligned} \min_{i \in \{1;2\}} f_i(\tau_j^*) &\ge F_0(\tau_j^*) \\ \min_{i \in \{1;2\}} \frac{f_i(\tau_j^*)}{g_i(\tau_j^*)} &\ge \frac{\hat{\alpha}_j^+}{\rho_j} \\ g_1(\tau_j^*) &\le \rho_j \left( G_0(\tau_j^*) + \frac{T}{n} \right) \\ g_2 &\le G_0 + \frac{T}{n} \end{aligned} $$

and

$$ \sup \operatorname{argmax}_{t>0} \left\{ \frac{f_1}{g_1} \right\} \ge \tau_j^*. $$

*Proof.* Let $(f,g) \in O_j$ be such that

$$ \tau_j^* = \sup \operatorname{argmax}_{t>0} \left\{ \frac{f(t)}{g(t)} \right\}. $$

Define

$$ f_1 : t \mapsto \begin{cases} f(t) & \text{if } t < \tau_j^* \\ \max(f(t), F_0(t)) & \text{if } t \ge \tau_j^* \end{cases} $$

Clearly, $f_1 \in [\hat{F}_j^-; \hat{F}_j^+]$ and is a cdf, as a result of the same properties being true for $f, F_0$. Let $g_1$ be defined in the usual manner, then for all $t < \tau_j^*$,

$$ \frac{f_1(t)}{g_1(t)} = \frac{f(t)}{g(t)} \le \frac{f(\tau_j^*)}{g(\tau_j^*)} \le \frac{f_1(\tau_j^*)}{g(\tau_j^*)} = \frac{f_1(\tau_j^*)}{g_1(\tau_j^*)} $$

which implies that

$$ \sup \operatorname{argmax}_{t>0} \left\{ \frac{f_1(t)}{g_1(t)} \right\} \ge \tau_j^* $$

and in particular that

$$ g_1 \left( \sup \operatorname{argmax}_{t>0} \left\{ \frac{f_1(t)}{g_1(t)} \right\} \right) \ge g_1(\tau_j^*) = g(\tau_j^*) \ge \frac{T}{n} $$
since $(f,g) \in \mathbb{H}_j$. Thus, $(f_1, g_1) \in \mathbb{H}_j$. Moreover, $f_1(\tau_j^*) \geq F_0(\tau_j^*)$ and

$$ \frac{f_1(\tau_j^*)}{g_1(\tau_j^*)} = \frac{f_1(\tau_j^*)}{g(\tau_j^*)} \geq \frac{f(\tau_j^*)}{g(\tau_j^*)} \geq \frac{\hat{\alpha}_j^+}{\rho_j} $$

since $(f,g) \in O_j$.

Since $g$ is continuous and $g(0) = 0$, there exists some $t_j \in [0; \tau_j^*]$ such that $g(t_j) = \frac{T}{n}$. Define

$$ f_2 : t \mapsto \begin{cases} f(t) & \text{if } t < t_j \\ \max(f(t), F_0(t)) & \text{if } t \geq t_j \end{cases} $$

and let $g_2 : t \mapsto \int_0^t (1 - f_2(s))ds$. Since $\tau_j^* \geq t_j$ and

$$ \sup_{t<t_j} \frac{f_2(t)}{g_2(t)} = \sup_{t<t_j} \frac{f(t)}{g(t)} \leq \frac{f(\tau_j^*)}{g(\tau_j^*)}, $$

it follows that

$$ g_2 \left( \sup \operatorname{argmax}_{t>0} \frac{f_2(t)}{g_2(t)} \right) \geq g_2(t_j) = g(t_j) \geq \frac{T}{n} $$

and hence that $(f_2, g_2) \in \mathbb{H}_j$. Since $\tau_j^* \geq t_j$,

$$ f_2(\tau_j^*) = \max(f(\tau_j^*), F_0(\tau_j^*)) \geq F_0(\tau_j^*). $$

Since $f_2 \geq f$, $g_2 \leq g$ and hence

$$ \frac{f_2(\tau_j^*)}{g_2(\tau_j^*)} \geq \frac{f(\tau_j^*)}{g(\tau_j^*)} \geq \frac{\hat{\alpha}_j^+}{\rho_j}. $$

Consider now the upper bound on $g_2$. First, for all $t \leq t_j$,

$$ g_2(t) \leq g_2(t_j) = \int_0^{t_j} (1 - f(s))ds = g(t_j) = \frac{T}{n} $$

and for all $t \geq t_j$,

$$ \begin{aligned} g_2(t) &= \int_0^{t_j} (1 - f(s))ds + \int_{t_j}^t (1 - \max(f(s), F_0(s)))ds \\ &\leq g(t_j) + \int_0^t (1 - F_0(s))ds \\ &= \frac{T}{n} + G_0(t). \end{aligned} $$

This yields $g_2 \leq G_0 + \frac{T}{n}$. Finally, consider the upper bound on $g_1$ at $\tau_j^*$. Since $(f_2, g_2) \in \mathbb{H}_j$,

$$ \frac{f_1(\tau_j^*)}{g_1(\tau_j^*)} = \frac{\max(f(\tau_j^*), F_0(\tau_j^*))}{g_1(\tau_j^*)} \geq \frac{\hat{\alpha}_j^+}{\rho_j} \geq \frac{1}{\rho_j} \frac{f_2(\tau_j^*)}{g_2(\tau_j^*)} = \frac{\max(f(\tau_j^*), F_0(\tau_j^*))}{\rho_j g_2(\tau_j^*)} $$
which yields

$$g_1(\tau_j^*) \le \rho_j g_2(\tau_j^*) \le \rho_j \left( \frac{T}{n} + G_0(\tau_j^*) \right).$$

We have proved all the properties stated in claim D.1.3.

□

**Lemma D.2.** Let $f: \mathbb{R}_+ \to [0; 1]$ be a non-decreasing function, not identically equal to 1. Let $g: \mathbb{R}_+ \to \mathbb{R}_+$ be defined by

$$g(t) = \int_{0}^{t} (1 - f(s))ds$$

for all $t \ge 0$ and let $\tau \in [0; \tau_M]$ be such that

$$\frac{f(\tau)}{g(\tau)} \ge \frac{1}{\rho} \sup_{t \in (0; \tau_M]} \left\{ \frac{f(t)}{g(t)} \right\}$$

for some $\rho \ge 1$. Then for any $t \in [0; \tau]$ and any $s \in [0; t]$,

$$\frac{1}{g(t)}(g(t) - \rho g(s)) \le 1 - f(s).$$

*Proof.* By assumption, $f < 1$ on some neighbourhood of 0, hence $g$ is positive on $(0; +\infty)$. It follows by definition of $\tau$ that $f/g$ is bounded. If $f = 0$ on $[0; \tau_M]$, then $g(t) = t$ and the conclusion of the lemma is true since

$$\frac{g(t) - \rho g(s)}{g(t)} = \frac{t - \rho s}{t} \le 1 = 1 - f(s).$$

Otherwise, there exists $t \in [0; \tau_M]$ such that $f(t) > 0$ and it follows that $f(\tau) > 0$. By definition of $\tau$, for any $s \in [0; t] \subset [0; \tau_M]$,

$$\frac{f(s)}{g(s)} \le \rho \frac{f(\tau)}{g(\tau)}$$

which implies that

$$\frac{f(s)}{f(\tau)} \le \rho \frac{g(s)}{g(\tau)}$$

and hence

$$1 - \frac{f(s)}{f(\tau)} \ge 1 - \rho \frac{g(s)}{g(\tau)}.$$

Since $g$ is non-decreasing and $f(\tau) \in (0; 1]$,

$$\begin{aligned} 1 - f(s) &\ge 1 - \frac{f(s)}{f(\tau)} \\ &\ge 1 - \rho \frac{g(s)}{g(\tau)} \\ &\ge 1 - \rho \frac{g(s)}{g(t)} \\ &= \frac{1}{g(t)}(g(t) - \rho g(s)) \end{aligned}$$
which proves the result.

□

## D.2 Proof of lemma 3.8

Due to censoring, there are some theoretical subtleties involved in deriving coverage bounds for these estimators, which seem to require additional assumptions on the sequence $\hat{\tau}_i$. The following proposition will be sufficient for our purpose.

**Lemma D.3.** Let $(X_j)_{j \ge 1}$ be infinite i.i.d sequence with common distribution P. Let $(I_j)_{j \ge 1}$ be an increasing sequence of stopping times with respect to the filtration

$$ (\mathcal{G}_j)_{j \ge 2} = (\sigma(X_1, \dots, X_{j-1}))_{j \ge 2} $$

The sequence

$$ (X_{I_j})_{j \ge 1} $$

is also i.i.d with distribution P.

*Proof.* Let $f,g$ be measurable functions respectively on $\mathbb{R}$ and $\mathbb{R}^j$. For any positive integer $r$, since the sequence $(I_j)_{j \ge 1}$ increases,

$$ \begin{aligned} & \mathbb{E}[f(X_{I_{j+1}})g(X_{I_1}, \dots, X_{I_j}) \mathbb{I}\{I_{j+1} = r\} | \mathcal{G}_r] \\ &= \mathbb{E}[f(X_r)g(X_{I_1}, \dots, X_{I_j}) \mathbb{I}\{I_{j+1} = r\} \mathbb{I}\{I_1 < r, \dots, I_j < r\} | \mathcal{G}_r] \\ &= g(X_{I_1}, \dots, X_{I_j}) \mathbb{I}\{I_{j+1} = r\} \mathbb{E}[f(X_r) | \mathcal{G}_r] \end{aligned} $$

by the defining property of stopping times. Since $X_r$ is independent from $\mathcal{G}_r$, we have that

$$ \mathbb{E}[f(X_{I_{j+1}})g(X_{I_1}, \dots, X_{I_j}) \mathbb{I}\{I_{j+1} = r\} | \mathcal{G}_r] = \mathbb{E}[f(X_r)]g(X_{I_1}, \dots, X_{I_j}) \mathbb{I}\{I_{j+1} = r\} $$

and hence

$$ \mathbb{E}[f(X_{I_{j+1}})g(X_{I_1}, \dots, X_{I_j})] = \mathbb{E}[f(X_1)]\mathbb{E}[g(X_{I_1}, \dots, X_{I_j}) \mathbb{I}\{I_{j+1} = r\}]. $$

Taking a sum over all integers $r$ yields

$$ \mathbb{E}[f(X_{I_{j+1}})g(X_{I_1}, \dots, X_{I_j})] = \mathbb{E}[f(X_1)]\mathbb{E}[g(X_{I_1}, \dots, X_{I_j})] $$

which implies independence by induction.

□

We can now prove lemma 3.8. Let

$$ \mathcal{X}_j = \bigcup \left\{ \underset{t>0}{\operatorname{argmax}} \left\{ \frac{f(t)}{g(t)} \right\} : (f,g) \in \mathbb{H}_j \right\}. $$

By construction, $\hat{\tau}_j \le T$ for all $j$. Moreover, by definition, for all $j \ge 2$, $\tau_j^* \in \mathbb{H}_j$ and either $\hat{\tau}_j = t_{K_j}$ or $\hat{\tau}_j \ge \tau_j^*$. Thus,

$$ \hat{\tau}_j \ge \min \left( t_{K_j}, \min_{1 \le i \le j-1} \hat{\tau}_i, \inf \mathcal{X}_j \right) \ge \min \left( \frac{T}{n}, \min_{1 \le i \le j-1} \hat{\tau}_i \right) $$
since $\hat{\alpha}_j^+ \le \frac{n}{T}$ and since for all $t \in \mathcal{X}_j$, there exists $f \in \mathcal{F}$ such that

$$t \ge \int_{0}^{t} (1 - f(s))ds \ge \frac{T}{n}.$$

It follows by induction that $\hat{\tau}_j \ge \frac{T}{n}$ for all $j \in \{1, \dots, n\}$. For any $k \in \{0, \dots, K-1\}$, let $(I(k, 1), \dots, I(k, n_k))$ be the unique increasing (possibly empty) integer sequence such that

$$\{i \in \{1, \dots, n\} : \hat{\tau}_i \in B_k\} = (I(k, i) : 1 \le i \le n_k).$$

Let $(X_{k,j}^*)_{1 \le k \le K, 1 \le j \le n}$ be i.i.d copies of $(X_1, \dots, X_n)$. For all $k \in \{1, \dots, K\}$ and $j \in \{1, \dots, n\}$, let

$$X_{k,j} = \begin{cases} X_{I(k,j)} & \text{if } j \le n_k \\ X_{k,j}^* & \text{if } j > n_k. \end{cases}$$

It follows from lemma D.3 that $(X_{k,j})_{1 \le j \le n}$ are i.i.d vectors for all $k$. Let $E_\eta$ be the event on which

$$F \in [\tilde{F}_{n,\eta'}^{-}(X_{k,1}, \dots, X_{k,j}) ; \tilde{F}_{n,\eta'}^{+}(X_{k,1}, \dots, X_{k,j})] \text{ for all } k \in \{0, \dots, K-1\}, j \in \{1, \dots, n\}.$$

By equation (12) and a union bound, this event has probability at least $1 - \eta$. Now, for any $\tau > 0$, $k \in \{0, \dots, K-1\}$ and $r \in \{1, \dots, n\}$, since $\frac{T}{n} \le \hat{\tau}_i \le T$ for all $i$ and since the sequence $(\hat{\tau}_i)_i$ is non-increasing on each interval $B_k$,

$$\mathcal{I}(k, j, \tau) = \{i \in \{1, \dots, j-1\} : \hat{\tau}_i \in B_k \cap [\tau; +\infty)\} = \{I(k, r) : 1 \le r \le m(j, \tau)\}$$

where

$$m(j, \tau) = \max \{1 \le r \le n_k : I(k, r) \le j-1 \text{ and } \hat{\tau}_{I(k,r)} \ge \tau\}.$$

It follows that on $E_\eta$,

$$F(\tau) \in [\tilde{F}_{n,\eta'}^{-}((X_i)_{i \in \mathcal{I}(k,j,\tau)}) (\tau); \tilde{F}_{n,\eta'}^{+}((X_i)_{i \in \mathcal{I}(k,j,\tau)}) (\tau)]$$

for all $j \in \{1, \dots, n\}$, $k \in \{0, \dots, K-1\}$ and $\tau > 0$. It follows by equation (19), (20) defining $\hat{F}_j^-, \hat{F}_j^+$ that on $E_\eta$, $F \in [\hat{F}_j^-; \hat{F}_j^+]$ for all $j \in \{1, \dots, n\}$.

## D.3 Bounding the variance

**Proposition D.4.** Let $f \in [w_{m,\eta}^- \circ f_0; w_{m,\eta}^+ \circ f_0]$ for some $f_0 : \mathbb{R} \to [0; 1]$ and a non-increasing function $m : \mathbb{R}_+ \to \mathbb{N}$. Let $J \subset \mathbb{R}_+$ be an interval containing 0. Define

$$g : t \mapsto \int_{0}^{t} (1 - f(s))ds.$$
Let $v$ denote the function

$$s \mapsto \mathrm{Var}(X \wedge s)$$

where $X$ follows some distribution $Q$ with cdf $F \in [w_{m,\eta}^{-} \circ f_0; w_{m,\eta}^{+} \circ f_0]$. Let $\tau \in J$ be such that

$$\frac{f(\tau)}{g(\tau)} \geq \frac{1}{\rho} \sup_{t \in J} \frac{f(t)}{g(t)}.$$

For any $t \leq \tau$, $v(t)$ is such that

$$v(t) \leq \frac{2}{\rho} g(t)^2 \left( 1 + \frac{8}{\rho} \sqrt{\frac{2z}{m(t)}} \right) - G(t)^2 + 2 \left( 1 - \frac{1}{\rho} \right) \operatorname{tg}(t) \\ + \frac{4}{\sqrt{3}} t^{3/2} \sqrt{\left(1 - \frac{1}{\rho}\right) g(t)} \sqrt{\frac{2z}{m(t)}} + \frac{9zt^2}{m(t)}.$$

*Proof.* For any $t \leq \tau$,

$$1 - f(t) \geq 1 - \rho g(t) \frac{f(\tau)}{g(\tau)} \geq 1 - \rho \frac{g(t)}{g(\tau)}.$$

Fix some $t \leq \tau$. For any $s \leq t$, since $g(t) \leq g(\tau)$,

$$1 - f(s) \geq 1 - \rho \frac{g(s)}{g(\tau)} \geq 1 - \rho \frac{g(s)}{g(t)},$$

hence for any $s \leq t$,

$$\frac{g(t) - \rho g(s)}{g(t)} \leq 1 - f(s). \qquad (71)$$

Remark that

$$\mathbb{E}[(X \wedge t)^2] = \int_0^t \frac{d}{ds} \mathbb{E}[(X \wedge s)^2] ds = \int_0^t 2s(1 - F(s)) ds.$$

Let $m = m(t)$ for short. Thus, by lemma 4.5,

$$\begin{align*}
\mathbb{E}[(X \wedge t)^2] &= \int_0^t 2s(1-f(s))ds + \int_0^t 2s(f-F)(s)ds \\
&\leq \int_0^t 2s(1-f(s))ds + 2 \int_0^t 2s \sqrt{\frac{2z}{m(s)}} \sqrt{1-f(s)}ds + \int_0^t 2s \frac{9z}{m(s)}ds \\
&\leq \int_0^t 2s(1-f(s))ds + 2 \sqrt{\frac{2z}{m}} \int_0^t 2s \sqrt{1-f(s)}ds + \frac{9zt^2}{m}.
\end{align*}$$
As a result of equation (71), by integration by parts,

$$
\begin{align*}
\int_0^t 2s(1-f(s))ds &= [-2s(g(t)-g(s))]_0^t + 2\int_0^t (g(t)-g(s))ds \\
&= 2\int_0^t (g(t)-g(s))ds \\
&= \frac{2}{\rho}\int_0^t (g(t)-\rho g(s))ds + 2\left(1-\frac{1}{\rho}\right)\operatorname{tg}(t) \\
&\le \frac{2}{\rho}g(t)\int_0^t (1-f(s))ds + 2\left(1-\frac{1}{\rho}\right)\operatorname{tg}(t) \\
&\le \frac{2}{\rho}g(t)^2 + 2\left(1-\frac{1}{\rho}\right)\operatorname{tg}(t).
\end{align*}
$$

Let $t_\rho$ be such that $g(t) = \rho g(t_\rho)$. Again by integration by parts.

$$
\begin{align*}
\int_0^{t_\rho} 2s\sqrt{1-f(s)}ds &= \int_0^{t_\rho} 2s \frac{1-f(s)}{\sqrt{1-f(s)}}ds \\
&\le \int_0^{t_\rho} 2s(1-f(s))\sqrt{\frac{g(t)}{g(t)-\rho g(s)}}ds \\
&= \left[-4\frac{s}{\rho}\sqrt{g(t)(g(t)-\rho g(s))}\right]_0^{t_\rho} + \frac{4}{\rho}\int_0^{t_\rho} \sqrt{g(t)(g(t)-\rho g(s))}ds \\
&= \frac{4}{\rho}\int_0^{t_\rho} \sqrt{g(t)(g(t)-\rho g(s))}ds \\
&\le \frac{4}{\rho}g(t)\int_0^{t_\rho} \sqrt{1-f(s)}ds \\
&\le \frac{4}{\rho}g(t)\int_0^{t_\rho} (1-f(s))\sqrt{\frac{g(t)}{g(t)-\rho g(s)}}ds \\
&\le \frac{4}{\rho^2}g(t)[-2\sqrt{g(t)(g(t)-\rho g(s))}]_0^{t_\rho} \\
&\le \frac{8}{\rho^2}g(t)^2.
\end{align*}
$$

Finally, by the Cauchy-Schwarz inequality,

$$
\begin{align*}
\int_{t_\rho}^{t} 2s\sqrt{1-f(s)}ds &\le 2 \left(\int_{t_\rho}^{t} s^2 ds\right)^{1/2} \left(\int_{t_\rho}^{t} (1-f(s))ds\right)^{1/2} \\
&\le \frac{2}{\sqrt{3}} t^{3/2} \sqrt{g(t)-g(t_\rho)} \\
&= \frac{2}{\sqrt{3}} t^{3/2} \sqrt{g(t)} \sqrt{1-\frac{1}{\rho}}.
\end{align*}
$$
Thus,

$$v(t) + G(t)^2 \leq \frac{2}{\rho} g(t)^2 \left(1 + \frac{8}{\rho} \sqrt{\frac{2z}{m}}\right) + 2 \left(1 - \frac{1}{\rho}\right) tg(t) \\ + \frac{4}{\sqrt{3}} t^{3/2} \sqrt{\left(1 - \frac{1}{\rho}\right) g(t)} \sqrt{\frac{2z}{m}} + \frac{9z}{m} t^2.$$

□

Let us now conclude the study of the variance process with the following claim.

**Claim D.4.1.** The total variance satisfies the bound

$$\mathbb{E}\left[\sum_{j=1}^{\hat{n}} v(\hat{\tau}_j)\right] \leq \frac{2T}{\alpha_*} \left(9 + 45z^{1/3} + \frac{\varepsilon}{2\alpha_*T} + 96z + \frac{4}{3}\right).$$

where $z = 2 \log n - \log \beta$.

*Proof.* Fix an index $j \in J$. If $\tau_j^* > t_{K_j}$, let $(\overline{F}_j^*; \overline{G}_j^*) = (f_2, g_2)$ given by claim D.1.3, for $F_0 = F$. then $\tau_j^* > t_{K_j} \geq \hat{\tau}_j$ so by equation (69) and Proposition D.4,

$$v(\hat{\tau}_j) \leq \frac{2}{\rho_j} \overline{G}_j^*(\hat{\tau}_j)^2 \left(1 + \frac{8}{\rho_j} \sqrt{\frac{2z}{m_j}}\right) - G(\hat{\tau}_j)^2 + 2 \left(1 - \frac{1}{\rho_j}\right) \hat{\tau}_j \overline{G}_j^*(\hat{\tau}_j) \\ + \frac{4}{\sqrt{3}} \hat{\tau}_j^{3/2} \sqrt{\left(1 - \frac{1}{\rho_j}\right) \overline{G}_j^*(\hat{\tau}_j)} \sqrt{\frac{2z}{m_j}} + \frac{9z \hat{\tau}_j^2}{m_j}.$$

Moreover, for all $t > 0$,

$$\frac{\overline{G}_j^*(t)}{t} \geq \max \left( 1 - \overline{F}_j^*(t), \frac{\overline{F}_j^*(t)}{t \hat{\alpha}_j^+} \right) \geq \min_{u \in [0;1]} \max \left( 1 - u, \frac{u}{t \hat{\alpha}_j^+} \right) \geq \frac{1}{1 + \hat{\alpha}_j^+ t}.$$

By construction,

$$\hat{\tau}_j \leq t_{K_j} \leq 2t_{K_{j+1}} \leq 2\sqrt{\frac{T}{\hat{\alpha}_j^+}}$$

which yields

$$\frac{\overline{G}_j^*(\hat{\tau}_j)}{\hat{\tau}_j} \geq \frac{1}{1 + 2\sqrt{\hat{\alpha}_j^+ T}}.$$
It follows from equation (21) defining $\rho_j$ that

$$ 
\begin{aligned}
\left(1 - \frac{1}{\rho_j}\right) \hat{\tau}_j \overline{G}_j^*(\hat{\tau}_j) &\le \frac{\varepsilon \hat{\tau}_j \overline{G}_j^*(\hat{\tau}_j)}{\left(1 + 2\sqrt{\hat{\alpha}_j^+ T}\right)^2} \frac{\overline{G}_j^*(\hat{\tau}_j)}{\hat{\tau}_j} \\
&\le \frac{\varepsilon \overline{G}_j^*(\hat{\tau}_j)^2}{4\hat{\alpha}_j^+ T} \\
\hat{\tau}_j^{3/2} \sqrt{\left(1 - \frac{1}{\rho_j}\right) \overline{G}_j^*(\hat{\tau}_j)} &\le \varepsilon \left(\frac{\overline{G}_j^*(\hat{\tau}_j)}{\hat{\tau}_j}\right)^{3/2} \hat{\tau}_j^{3/2} \sqrt{\overline{G}_j^*(\hat{\tau}_j)} \\
&\le \varepsilon \overline{G}_j^*(\hat{\tau}_j)^2
\end{aligned}
$$

Thus,

$$ v(\hat{\tau}_j) \le \frac{2}{\rho_j} \overline{G}_j^*(\hat{\tau}_j)^2 \left( 1 + \left( 8 + \frac{4\varepsilon\rho_j}{\sqrt{3}} \right) \sqrt{\frac{2z}{m_j}} + \frac{\varepsilon}{4\hat{\alpha}_j^+ T} \right) + \frac{36zT}{m_j\hat{\alpha}_j^+} $$

where $\rho_j \le \frac{1+2\mu_0}{1+2\mu_0-\varepsilon}$ with $\mu_0 = 59 \log^{3/2}(n_0)$ by equations (65) and (66). Since $\hat{\tau}_j \le \tau_j^*$,

$$ \overline{G}_j^*(\hat{\tau}_j) \le \overline{G}_j^*(\tau_j^*) \le \frac{\overline{G}_j^*(\tau_j^*)}{\overline{F}_j^*(\tau_j^*)} \le \frac{\rho_j}{\hat{\alpha}_j^+}. $$

Hence,

$$ v(\hat{\tau}_j) \le \frac{2}{\hat{\alpha}_j^+} \overline{G}_j^*(\hat{\tau}_j) \left( 1 + 9\sqrt{\frac{2z}{m_j}} + \frac{\varepsilon}{4\hat{\alpha}_j^+ T} \right) + \frac{9z\hat{\tau}_j^2}{m_j}. $$

By claim D.1.3, $\overline{G}_j^* \le G + \frac{T}{n}$, thus

$$ v(\hat{\tau}_j) \le \frac{2}{\hat{\alpha}_j^+} \left( G(\hat{\tau}_j) + \frac{T}{n} \right) \left( 1 + 9\sqrt{\frac{2z}{m_j}} + \frac{\varepsilon}{4\hat{\alpha}_j^+ T} \right) + \frac{9z\hat{\tau}_j^2}{m_j}. \quad (72) $$

If $\tau_j^* \le t_{K_j}$, then since $\hat{\tau}_j \le \min(2\tau_j^*, t_{K_j})$,

$$ v(\hat{\tau}_j) \le 4\mathbb{E}\left[(X_j \wedge \tau_j^* \wedge \frac{t_{K_j}}{2})^2\right] - G(\hat{\tau}_j)^2. $$

Let $(\overline{F}_j^*, \overline{G}_j^*) = (f_1, g_1)$ given by claim D.1.3. Since

$$ \tau_j^* \le \sup \operatorname{argmax}_{t>0} \frac{\overline{F}_j^*(t)}{\overline{G}_j^*(t)}, $$

by equation (69) and Proposition D.4,

$$ v(\hat{\tau}_j) \le 8\overline{G}_j^*(\tau_j^*)^2 \left( 1 + 8\sqrt{\frac{2z}{m}} \right) + \frac{36z\hat{\tau}_j^2}{m_j} - G(\hat{\tau}_j^2). $$
By definition,

$$ \overline{G}_j^*(\tau_j^*) \le \frac{\overline{G}_j^*(\tau_j^*)}{\overline{F}_j^*(\tau_j^*)} \le \frac{\rho_j}{\hat{\alpha}_j^+} $$

It follows from claim D.1.3 that

$$ v(\hat{\tau}_j) \le \frac{8\rho_j^2}{\hat{\alpha}_j^+} \left( G(\tau_j^*) + \frac{T}{n} \right) \left( 1 + 8\sqrt{\frac{2z}{m_j}} \right) + \frac{36z\hat{\tau}_j^2}{m_j}. $$

Since $\tau_j^* \le \hat{\tau}_j$ we have that,

$$ v(\hat{\tau}_j) \le \frac{8\rho_j^2}{\hat{\alpha}_j^+} \left( G(\hat{\tau}_j) + \frac{T}{n} \right) \left( 1 + 8\sqrt{\frac{2z}{m_j}} \right) + \frac{36z\hat{\tau}_j^2}{m_j}. $$

Now, since $\sqrt{\hat{\alpha}_j^+ T} \ge 59 \log^{3/2}(n_0)$, $\rho_j$ given by equation (21) is less than $\frac{9}{8}$ for every $\varepsilon \in [0; 1]$. Combining with the first case (for which equation (72) holds) yields that for all $j \in J_r$,

$$ \begin{aligned} v(\hat{\tau}_j) & \le \frac{1}{\hat{\alpha}_j^+} \left( 9 + 72\sqrt{\frac{2z}{r}} + \frac{2\varepsilon}{4\hat{\alpha}_j^+ T} \right) \left( G(\hat{\tau}_j) + \frac{T}{n} \right) + \frac{36z\hat{\tau}_j^2}{m_j} \\ & \le \frac{1}{\alpha_*} \left( 9 + 72\sqrt{\frac{2z}{r}} + \frac{2\varepsilon}{4\alpha_* T} \right) \left( G(\hat{\tau}_j) + \frac{T}{n} \right) + \frac{36z\hat{\tau}_j^2}{m_j} \end{aligned} $$

since $(F, G) \in \mathbb{H}_j$ for all $j \in J_r$. Moreover, since $\hat{n}$ is a stopping time,

$$ \mathbb{E} \left[ \sum_{j \in J_r} G(\hat{\tau}_j) \right] \le \mathbb{E} \left[ \sum_{j=1}^{\hat{n}} G(\hat{\tau}_j) \right] = \mathbb{E} \left[ \sum_{j=1}^{\hat{n}} X_j \wedge \hat{\tau}_j \right] \le T $$

and hence, by claim D.1.2,

$$ \mathbb{E} \left[ \sum_{j \in J_r} v(\hat{\tau}_j) \right] \le \frac{2T}{\alpha_*} \left( 9 + 72\sqrt{\frac{2z}{r}} + \frac{2\varepsilon}{4\alpha_* T} + 96z \right). $$

Combining this bound with claim D.1.1 yields

$$ \mathbb{E} \left[ \sum_{j=1}^{\hat{n}} v(\hat{\tau}_j) \right] \le \frac{2T}{\alpha_*} \left( 9 + 72\sqrt{\frac{2z}{r}} + \frac{2\varepsilon}{4\alpha_* T} + 96z + \frac{4r}{3} \right). $$

Optimizing over integers $r \ge 1$ finally yields

$$ \mathbb{E} \left[ \sum_{j=1}^{\hat{n}} v(\hat{\tau}_j) \right] \le \frac{2T}{\alpha_*} \left( 9 + 45z^{1/3} + \frac{2\varepsilon}{4\alpha_* T} + 96z + \frac{4}{3} \right). $$

□
### D.4 The case where no tasks remain

Fix some $j \le \hat{n}$ and let $(\overline{F}_j^*, \overline{G}_j^*) \in O_j$ be such that

$$ \tau_j^* = \sup \operatorname{argmax} \left\{ \frac{\overline{F}_j^*}{\overline{G}_j^*} \right\}. $$

Since $F \in [\hat{F}_j^-; \hat{F}_j^+]$, by equation (69) and lemma 4.5, for any $\theta \ge 0$,

$$ \begin{aligned} F(\hat{\tau}_j) &= F(\hat{\tau}_j) \\ &\ge \overline{F}_j^*(\hat{\tau}_j) - 2\sqrt{\frac{2z}{m_j}}\sqrt{\overline{F}_j^*(\hat{\tau}_j)} - \frac{4z}{3m_j} \\ &\ge (1-\theta)\overline{F}_j^*(\hat{\tau}_j) - \frac{z}{m_j}\left(\frac{2}{\theta} + \frac{4}{3}\right). \end{aligned} \quad (73) $$

By construction,

$$ \overline{F}_j^*(\hat{\tau}_j) \ge \overline{F}_j^*(\tau_j^* \wedge t_{K_{j+1}}). $$

There are two possibilities. If $\tau_j^* > t_{K_j}$, then by definition,

$$ t_{K_{j+1}}(1 - \overline{F}_j^*(t_{K_{j+1}})) \le \overline{G}_j^*(\tau_j^*) = \frac{\overline{F}_j^*(\tau_j^*)}{\hat{\alpha}_j^+} \le \frac{1}{\hat{\alpha}_j^+} $$

which implies that

$$ 1 - \overline{F}_j^*(t_{K_{j+1}}) \le \frac{1}{\hat{\alpha}_j^+ t_{K_{j+1}}} \le \frac{2}{\hat{\alpha}_j^+} \sqrt{\frac{\hat{\alpha}_j^+ \log n}{T}} = \frac{2\sqrt{\log n}}{\sqrt{\hat{\alpha}_j^+ T}} \le \frac{2\sqrt{\log n}}{\sqrt{\alpha_* T}}. $$

As a result, since $\hat{\tau}_j \in (t_{K_{j+1}}; t_{K_j}]$ in that case,

$$ \overline{F}_j^*(\hat{\tau}_j) \ge \overline{F}_j^*(t_{K_{j+1}}) \ge 1 - \frac{2\sqrt{\log n}}{\sqrt{\alpha_* T}} \ge F(\tau_*) \left(1 - 2\sqrt{\frac{\log n}{\alpha_* T}}\right). $$

By assumption, $\frac{F(\tau_*)}{\alpha_*} = G(\tau_*) \ge \frac{T}{n}$ and hence $F(\tau_*) \ge \alpha_* \frac{T}{n}$, which yields

$$ \overline{F}_j^*(\hat{\tau}_j) \ge \frac{\alpha_* T}{n} \left(1 - 2\sqrt{\frac{\log n}{\alpha_* T}}\right). $$
Now, if $\tau_j^* \le t_{K_j}$, then since $(\overline{F}_j^*, \overline{G}_j^*) \in \mathbb{H}_j$ as well as $(F,G) \in \mathbb{H}_j$ and by definition of $\tau_j^*$,

$$
\begin{align*}
\overline{F}_j^*(\hat{\tau}_j) &\ge \overline{F}_j^*(\tau_j^*) \\
&= \frac{\overline{F}_j^*(\tau_j^*)}{\overline{G}_j^*(\tau_j^*)} \overline{G}_j^*(\tau_j^*) \\
&= \hat{\alpha}_j^+ \overline{G}_j^*(\tau_j^*) \\
&\ge \hat{\alpha}_j^+ \frac{T}{n} \\
&\ge \alpha_* \frac{T}{n}.
\end{align*}
$$

Combining this with the previous case yields

$$
\overline{F}_j^*(\hat{\tau}_j) \geq \alpha_* \frac{T}{n} \left( 1 - 2\sqrt{\frac{\log n}{\alpha_* T}} \right)_+
$$

for any $j \in \{1, \dots, \hat{n}\}$. It follows that

$$
\sum_{j \in J_1} \overline{F}_j^*(\hat{\tau}_j) \geq \frac{|J_1|}{n} \alpha_* T \left( 1 - 2\sqrt{\frac{\log n}{\alpha_* T}} \right) \geq \frac{|J|}{n} \alpha_* T - 2\sqrt{\alpha_* T \log n}.
$$

It follows from equation (73), claim D.1.1 and claim D.1.2 that for any $\theta \ge 0$,
on the event $\{\hat{n} = n\}$,

$$
\begin{align*}
\sum_{j=1}^{\hat{n}} F(\hat{\tau}_j) &= \sum_{j=1}^{n} F(\hat{\tau}_j) \\
&\ge \sum_{j \in J} F(\hat{\tau}_j) \\
&\ge (1-\theta) \sum_{j \in J} \overline{F}_j^*(\tau_j^*) - z \left(\frac{2}{\theta} + \frac{4}{3}\right) \sum_{j \in J} \frac{1}{m_j} \\
&\ge (1-\theta) \alpha_* T - K \frac{\alpha_* T}{n} - 2\sqrt{\alpha_* T \log n} - zK \log n \left(\frac{4}{3} + \frac{2}{\theta}\right)
\end{align*}
$$

Replacing $\theta$ with $4\theta$ and dividing by the leading order $\sqrt{\alpha_* T \log^3 n}$ yields

$$
\sum_{j=1}^{\hat{n}} F(\hat{\tau}_j) \ge (1 - 4\theta)\alpha_* T - \frac{zK}{2\theta} \log n - w_0(\log n)\sqrt{\alpha_* T \log^3 n},
$$

for all $n \ge n_0$, where by equations (65) and (68),

$$
w_0(x) = \frac{4}{3} \times \frac{4.1}{59} + \frac{2}{x} + \frac{1}{59 \log(2)x^2} + \frac{1}{59x^3}.
$$
Since $n \ge n_0$, taking expectations yields

$$ \mathbb{E} \left[ \left| \mathbb{I}\{\hat{n} = n\} \sum_{j=1}^{\hat{n}} F(\hat{\tau}_j) \right| \right] \ge \mathbb{P}(\hat{n} = n) \left( (1-4\theta)\alpha_*T - \frac{zK}{2\theta} \log n - 0.22\sqrt{\alpha_*T \log^3 n} \right) \quad (74) $$

which concludes the analysis of the case $\hat{n} = n$.

## D.5 The case where time runs out

Let us now analyze the case $\hat{n} < n$, or more precisely the event $E \cap \{\hat{n}_t < n\}$ where "time runs out", but the confidence bands are valid. Fix some $j \le \hat{n}$. As before, let $(\overline{F}_j^*, \overline{G}_j^*) \in O_j$ be such that

$$ \tau_j^* = \sup \operatorname{argmax}_{t \in (0; +\infty]} \frac{\overline{F}_j^*(t)}{\overline{G}_j^*(t)}. $$

There are two cases. If $\tau_j^* > t_{K_j} \ge \hat{\tau}_j$, then by equation (69) and lemma 4.5, for any $\theta > 0$,

$$ \begin{aligned} F(\hat{\tau}_j) &\ge \overline{F}_j^*(\hat{\tau}_j) - 2\sqrt{\frac{2z}{m_j}} \sqrt{\overline{F}_j^*(\hat{\tau}_j)} - \frac{4z}{3m_j} \\ &\ge (1-\theta)\overline{F}_j^*(\hat{\tau}_j) - \frac{z}{m_j} \left( \frac{2}{\theta} + \frac{4}{3} \right) \\ &= (1-\theta)\frac{\overline{F}_j^*(\hat{\tau}_j)}{\overline{G}_j^*(\hat{\tau}_j)}\overline{G}_j^*(\hat{\tau}_j) - \frac{z}{m_j} \left( \frac{2}{\theta} + \frac{4}{3} \right). \end{aligned} $$

If $\overline{G}_j^*(\hat{\tau}_j) \ge G(\hat{\tau}_j)$, then

$$ F(\hat{\tau}_j) \ge (1-\theta) \frac{\overline{F}_j^*(\hat{\tau}_j)}{\overline{G}_j^*(\hat{\tau}_j)} G(\hat{\tau}_j) - \frac{z}{m_j} \left( \frac{2}{\theta} + \frac{4}{3} \right). \quad (75) $$

Otherwise, by equation (69), lemma D.2 and Proposition 4.6, since $\hat{\tau}_j \le \tau_j^*$,

$$ \overline{G}_j^*(\hat{\tau}_j) \ge G(\hat{\tau}_j) - 6\sqrt{\frac{z}{m_j}}\overline{G}_j^*(\hat{\tau}_j) - 10\frac{z\hat{\tau}_j}{m_j} $$

which yields

$$ F(\hat{\tau}_j) \ge (1-\theta) \left( \frac{\overline{F}_j^*(\hat{\tau}_j)}{\overline{G}_j^*(\hat{\tau}_j)} \left( G(\hat{\tau}_j) - 10 \frac{z \hat{\tau}_j}{m_j} \right) - 6 \sqrt{\frac{z}{m_j}} \overline{F}_j^*(\hat{\tau}_j) \right)_+ - \frac{z}{m_j} \left( \frac{2}{\theta} + \frac{8}{3} \right). $$

Since by assumption $\overline{G}_j^*(\hat{\tau}_j) < G(\hat{\tau}_j)$,

$$ 6\sqrt{\frac{z}{m_j}}\overline{F}_j^*(\hat{\tau}_j) \le 6\sqrt{\frac{z}{m_j}}\sqrt{\frac{\overline{F}_j^*(\hat{\tau}_j)}{\overline{G}_j^*(\hat{\tau}_j)}}G(\hat{\tau}_j) \le \theta\frac{\overline{F}_j^*(\hat{\tau}_j)}{\overline{G}_j^*(\hat{\tau}_j)}G(\hat{\tau}_j) + \frac{9z}{\theta m_j} $$
which, together with equation (75), implies that in either case,

$$F(\hat{\tau}_j) \geq (1 - \theta) \frac{\overline{F}_j^*(\hat{\tau}_j)}{\overline{G}_j^*(\hat{\tau}_j)} \left( (1 - \theta)G(\hat{\tau}_j) - 10 \frac{z\hat{\tau}_j}{m_j} \right)_+ - \frac{z}{m_j} \left( \frac{11}{\theta} + \frac{8}{3} \right).$$

By definition and since $t_{K_j+1} \le \hat{\tau}_j \le \tau_j^*$,

$$\begin{aligned} \frac{\overline{F}_j^*(\tau_j^*)}{\overline{G}_j^*(\tau_j^*)} - \frac{\overline{F}_j^*(\hat{\tau}_j)}{\overline{G}_j^*(\hat{\tau}_j)} &\le \frac{\overline{F}_j^*(\tau_j^*)}{\overline{G}_j^*(\hat{\tau}_j)} - \frac{\overline{F}_j^*(\hat{\tau}_j)}{\overline{G}_j^*(\hat{\tau}_j)} \\ &\le \frac{1 - \overline{F}_j^*(\hat{\tau}_j)}{\overline{G}_j^*(\hat{\tau}_j)} \\ &\le \frac{1 - \overline{F}_j^*(\hat{\tau}_j)}{\hat{\tau}_j (1 - \overline{F}_j^*(\hat{\tau}_j))} \\ &\le \frac{1}{\hat{\tau}_j} \\ &\le 2\sqrt{\frac{\hat{\alpha}_j^+ \log n}{T}}. \end{aligned}$$

It follows that

$$\frac{\overline{F}_j^*(\hat{\tau}_j)}{\overline{G}_j^*(\hat{\tau}_j)} \ge \left( \hat{\alpha}_j^+ - 2\sqrt{\frac{\hat{\alpha}_j^+ \log n}{T}} \right)_+ \ge \left( \alpha_* - 2\sqrt{\frac{\alpha_* \log n}{T}} \right)_+.$$

As a result,

$$F(\hat{\tau}_j) \ge \left( \alpha_* - 2\sqrt{\frac{\alpha_* \log n}{T}} \right)_+ (1 - 2\theta)G(\hat{\tau}_j) - 10\alpha_* \frac{z\hat{\tau}_j}{m_j} - \frac{z}{m_j} \left( \frac{11}{\theta} + \frac{8}{3} \right). \quad (76)$$

Now, if $\tau_j^* \le t_{K_j}$, then $k_j \ge K_j$ and

$$\hat{\tau}_j \ge \sup_{t \in (0; t_{k_j}]} \operatorname{argmax} \left\{ \frac{\overline{F}_j^*(t)}{\overline{G}_j^*(t)} \right\} = \tau_j^*$$

since by definition,

$$\tau_j^* \in (t_{k_j+1}; t_{k_j}].$$

By definition of $\hat{\tau}_j$ and lemma D.2, we may choose $\overline{F}_j \in [\hat{F}_j^-; \hat{F}_j^+]$ such that

$$\hat{\tau}_j = \sup_{t \in (0; t_{k_j}]} \operatorname{argmax} \left\{ \frac{\overline{F}_j(t)}{\overline{G}_j(t)} \right\}$$
where as usual, $\overline{G}_j(t) = \int_0^t (1 - \overline{F}_j(s)) ds$. Both $F$ and $\overline{F}_j$ belong to $[\overline{F}_j^-, \overline{F}_j^+]$, hence by equation (69) and lemma 4.5,

$$ 
\begin{aligned}
F(\hat{\tau}_j) &\ge \overline{F}_j(\hat{\tau}_j) - 2\sqrt{\frac{2z}{m_j}\sqrt{\overline{F}_j(\hat{\tau}_j)}} - \frac{4z}{3m_j} \\
&\ge (1 - \theta)\overline{F}_j(\hat{\tau}_j) - \frac{2z}{\theta m_j} - \frac{4z}{3m_j}
\end{aligned} 
\quad (77) $$

for all $\theta \in [0; 1]$. Now, by definition of $\hat{\tau}_j$,

$$ \overline{F}_j(\hat{\tau}_j) = \frac{\overline{F}_j(\hat{\tau}_j)}{\overline{G}_j(\hat{\tau}_j)} \overline{G}_j(\hat{\tau}_j) \ge \frac{\overline{F}_j(\tau_j^*)}{\overline{G}_j(\tau_j^*)} \overline{G}_j(\hat{\tau}_j). $$

By lemma 4.5 applied to $\overline{F}_j$ and $\overline{F}_j^*$,

$$ \overline{F}_j(\hat{\tau}_j) \ge \frac{\overline{F}_j^*(\tau_j^*)}{\overline{G}_j(\tau_j^*)} \overline{G}_j(\hat{\tau}_j) - 2\sqrt{\frac{2z}{m_j}\frac{\sqrt{\overline{F}_j^*(\tau_j^*)}}{\overline{G}_j(\tau_j^*)}} \overline{G}_j(\hat{\tau}_j) - \frac{4z}{3m_j\overline{G}_j(\tau_j^*)} \overline{G}_j(\hat{\tau}_j). $$

Since

$$ \frac{\overline{G}_j(\hat{\tau}_j)}{\overline{G}_j(\tau_j^*)} \le \frac{\hat{\tau}_j}{\tau_j^*} \le \frac{t_{k_j}}{t_{k_j+1}} = 2, $$

it follows that

$$ 
\begin{aligned}
\overline{F}_j(\hat{\tau}_j) &\ge \frac{\overline{F}_j^*(\tau_j^*)}{\overline{G}_j(\tau_j^*)} \overline{G}_j(\hat{\tau}_j) - 4\sqrt{\frac{z}{m_j}\frac{\overline{F}_j^*(\tau_j^*)}{\overline{G}_j(\tau_j^*)} \overline{G}_j(\hat{\tau}_j)} - \frac{8z}{3m_j} \\
&\ge (1 - \theta)\frac{\overline{F}_j^*(\tau_j^*)}{\overline{G}_j(\tau_j^*)} \overline{G}_j(\hat{\tau}_j) - \left(\frac{4}{\theta} + \frac{8}{3}\right) \frac{z}{m_j} \\
&\ge (1 - \theta)\frac{\overline{F}_j^*(\tau_j^*)}{\overline{G}_j(\tau_j^*)} \overline{G}_j(\hat{\tau}_j) - \left(\frac{4}{\theta} + \frac{8}{3}\right) \frac{z}{m_j},
\end{aligned} $$

where $\hat{G}_j^+ : t \mapsto \int_0^t (1 - \hat{F}_j^-(s)) ds$.

Now, either $\overline{G}_j(\hat{\tau}_j) \ge G(\hat{\tau}_j)$ or by equation 69, lemma D.2 and Proposition 4.6,

$$ \overline{G}_j(\hat{\tau}_j) \ge G(\hat{\tau}_j) - 6\sqrt{\frac{z}{m_j}}\overline{G}_j(\hat{\tau}_j) - 10\frac{z\hat{\tau}_j}{m_j} \ge G(\hat{\tau}_j) - 6\sqrt{\frac{z}{m_j}}G(\hat{\tau}_j) - 10\frac{z\hat{\tau}_j}{m_j} $$

and in either case,

$$ \overline{G}_j(\hat{\tau}_j) \ge G(\hat{\tau}_j) - 6\sqrt{\frac{z}{m_j}}G(\hat{\tau}_j) - 10\frac{z\hat{\tau}_j}{m_j} $$
which yields

$$ \frac{\overline{F}_j^*(\tau_j^*)}{\hat{G}_j^+(\tau_j^*)} \overline{G}_j(\hat{\tau}_j) \ge \frac{\overline{F}_j^*(\tau_j^*)}{\hat{G}_j^+(\tau_j^*)} G(\hat{\tau}_j) - 6\sqrt{\frac{z}{m_j}} \frac{\overline{F}_j^*(\tau_j^*)}{\hat{G}_j^+(\tau_j^*)} G(\hat{\tau}_j) - 10 \frac{z \hat{\tau}_j}{m_j} \frac{\overline{F}_j^*(\tau_j^*)}{\hat{G}_j^+(\tau_j^*)} $$

Since

$$ \frac{G(\hat{\tau}_j)}{\hat{G}_j^+(\tau_j^*)} \le \frac{G(\hat{\tau}_j)}{G(\tau_j^*)} \le \frac{\hat{\tau}_j}{\tau_j^*} \le 2, $$

this implies

$$ \begin{aligned} \frac{\overline{F}_j^*(\tau_j^*)}{\hat{G}_j^+(\tau_j^*)} \overline{G}_j(\hat{\tau}_j) &\ge \frac{\overline{F}_j^*(\tau_j^*)}{\hat{G}_j^+(\tau_j^*)} G(\hat{\tau}_j) - 6 \sqrt{\frac{2z}{m_j} \frac{\overline{F}_j^*(\tau_j^*)}{\hat{G}_j^+(\tau_j^*)} G(\hat{\tau}_j)} - 10 \hat{\alpha}_j^+ \hat{\tau}_j \frac{z}{m_j} \\ &\ge (1-\theta) \frac{\overline{F}_j^*(\tau_j^*)}{\hat{G}_j^+(\tau_j^*)} G(\hat{\tau}_j) - \frac{z}{m_j} \left( \frac{18}{\theta} + 10 \hat{\alpha}_j^+ \hat{\tau}_j \right) \end{aligned} $$

and hence

$$ \overline{F}_j(\hat{\tau}_j) \ge (1 - 2\theta) \frac{\overline{F}_j^*(\tau_j^*)}{\hat{G}_j^+(\tau_j^*)} G(\hat{\tau}_j) - \frac{z}{m_j} \left( \frac{22}{\theta} + \frac{8}{3} + 10 \hat{\alpha}_j^+ \hat{\tau}_j \right). \quad (78) $$

Now, by equation (69), lemma D.2 and Proposition 4.6,

$$ G_j^+(\tau_j^*) \le \overline{G}_j^*(\tau_j^*) \left( 1 + 6\sqrt{\frac{z}{m_j}} + \frac{10z\tau_j^*}{m_j \overline{G}_j^*(\tau_j^*)} \right) $$

which implies that

$$ \begin{aligned} \frac{1}{\hat{G}_j^+(\tau_j^*)} &\ge \frac{1}{\overline{G}_j^*(\tau_j^*)} - \frac{1}{\overline{G}_j^*(\tau_j^*)} \frac{6\sqrt{\frac{z}{m_j}} + 10\frac{z\tau_j^*}{m_j \overline{G}_j^*(\tau_j^*)}}{1 + 6\sqrt{\frac{z}{m_j}} + 10\frac{z\tau_j^*}{m_j \overline{G}_j^*(\tau_j^*)}} \\ &\ge \frac{1}{\overline{G}_j^*(\tau_j^*)} - \frac{6\sqrt{\frac{z}{m_j}} + 10\frac{z\tau_j^*}{m_j \overline{G}_j^*(\tau_j^*)}}{\hat{G}_j^+(\tau_j^*)}. \end{aligned} $$

As a consequence,

$$ \frac{\overline{F}_j^*(\tau_j^*)}{\hat{G}_j^+(\tau_j^*)} G(\hat{\tau}_j) \ge \frac{\hat{\alpha}_j^+}{\rho_j} G(\hat{\tau}_j) - 6 \sqrt{\frac{z}{m_j} \frac{\overline{F}_j^*(\tau_j^*)}{\hat{G}_j^+(\tau_j^*)} G(\hat{\tau}_j)} - 10 \hat{\alpha}_j^+ \tau_j^* \frac{z}{m_j} \frac{G(\hat{\tau}_j)}{\hat{G}_j^+(\tau_j^*)} $$

Using the fact that

$$ \frac{G(\hat{\tau}_j)}{\hat{G}_j^+(\tau_j^*)} \le \frac{\hat{G}_j^+(\hat{\tau}_j)}{\hat{G}_j^+(\tau_j^*)} \le \frac{\hat{\tau}_j}{\tau_j^*} \le 2, $$
this yields

$$
\begin{align*}
\frac{\bar{F}_j^*(\tau_j^*)}{\hat{G}_j^*(\tau_j^*)} G(\hat{\tau}_j) &\ge \frac{\hat{\alpha}_j^+}{\rho_j} G(\hat{\tau}_j) - 6 \sqrt{\frac{2z}{m_j} \frac{\bar{F}_j^*(\tau_j^*)}{\hat{G}_j^*(\tau_j^*)} G(\hat{\tau}_j)} - 10 \hat{\alpha}_j^+ \hat{\tau}_j \frac{z}{m_j} \\
&\ge \frac{\hat{\alpha}_j^+}{\rho_j} G(\hat{\tau}_j) - 6 \sqrt{\frac{2z}{m_j} \frac{\hat{\alpha}_j^+}{\rho_j} G(\hat{\tau}_j)} - 10 \hat{\alpha}_j^+ \hat{\tau}_j \frac{z}{m_j} \\
&\ge (1-\theta) \frac{\hat{\alpha}_j^+}{\rho_j} G(\hat{\tau}_j) - \frac{z}{m_j} \left( \frac{18}{\theta} + 10 \hat{\alpha}_j^+ \hat{\tau}_j \right).
\end{align*}
$$

Now, by equation (21) defining $\rho_j$,

$$
\frac{\hat{\alpha}_j^+}{\rho_j} \geq \hat{\alpha}_j^+ - \frac{\varepsilon \hat{\alpha}_j^+}{(1 + 2\sqrt{\hat{\alpha}_j^+ T})^3} \geq \hat{\alpha}_j^+ - \frac{\varepsilon \hat{\alpha}_j^+}{4\hat{\alpha}_j^+ T} \geq \hat{\alpha}_j^+ - \frac{\varepsilon}{4T}.
$$

Combining this with equation (78) above yields

$$
\bar{F}_j(\hat{\tau}_j) \ge \left( (1-3\theta) \left( \hat{\alpha}_j^+ - \frac{\varepsilon}{4T} \right) G(\hat{\tau}_j) - \frac{z}{m_j} \left( \frac{40}{\theta} + 20\hat{\alpha}_j^+ \hat{\tau}_j + \frac{8}{3} \right) \right)_+ .
$$

Since $j \le \hat{n}_{cb}$, $\hat{\alpha}_j^+ \ge \alpha_*$, hence

$$
\bar{F}_j(\hat{\tau}_j) \ge (1 - 3\theta) \left( \alpha_* - \frac{\varepsilon}{4T} \right) G(\hat{\tau}_j) - \frac{20z}{m_j} \left( \frac{2}{\theta} + \alpha_* \hat{\tau}_j + \frac{2}{15} \right) \quad (79)
$$

It follows from equation (77) that

$$
F(\hat{\tau}_j) \ge (1 - 4\theta) \left( \alpha_* - \frac{\varepsilon}{4T} \right) G(\hat{\tau}_j) - \frac{z}{m_j} \left( \frac{42}{\theta} + 20\alpha_* \hat{\tau}_j + 4 \right) \quad (80)
$$

when $\tau_j^* < t_{K_j}$. When $\tau_j^* \ge t_{K_j}$, equation (76) holds. Combining both cases yields

$$
F(\hat{\tau}_j) \ge (1 - 4\theta) \left( \alpha_* - 2\sqrt{\frac{\alpha_* \log n}{T}} - \frac{\varepsilon}{4T} \right)_+ G(\hat{\tau}_j) - \frac{z}{m_j} \left( \frac{42}{\theta} + 20\alpha_* \hat{\tau}_j + 4 \right) \quad (81)
$$

for any $j \le \hat{n}$. Let $r \ge 1$ be an integer, then by claim D.1.2,

$$
\sum_{j \in J_r} F(\hat{\tau}_j) \ge (1-4\theta) \left( \alpha_* - 2\sqrt{\frac{\alpha_* \log n}{T}} - \frac{\varepsilon}{4T} \right) \sum_{+} G(\hat{\tau}_j) - zK \log n \left( \frac{42}{\theta} + 4 \right) \\
- 80\sqrt{\alpha_* T \log n}.
$$

Using claim D.1.1, it follows that

$$
\sum_{j \in J_r} F(\hat{\tau}_j) \ge (1-4\theta) \left( \alpha_* - 2\sqrt{\frac{\alpha_* \log n}{T}} - \frac{\varepsilon}{4T} \right)_+ \sum_{+} \hat{n} G(\hat{\tau}_j) - \left( 80\sqrt{\log n} + 2r \right) \sqrt{\alpha_* T} \\
- zK \log n \left( \frac{42}{\theta} + 4 \right).
$$
Now,

$$ \mathbb{E} \left[ \mathbb{I}_{E_\eta} \mathbb{I}\{\hat{n}_t < n\} \sum_{j=1}^{\hat{n}} G(\hat{\tau}_j) \right] \geq \mathbb{E} \left[ \mathbb{I}_{E_\eta} \mathbb{I}\{\hat{n}_t < n\} \sum_{j=1}^{\hat{n}} X_j \wedge \hat{\tau}_j \right] - \mathbb{E} \left[ \left\| \sum_{j=1}^{\hat{n}} X_j \wedge \hat{\tau}_j - G(\hat{\tau}_j) \right\| \right]. $$

On the one hand,

$$ \begin{aligned} \mathbb{E} \left[ \mathbb{I}_{E_\eta} \mathbb{I}\{\hat{n}_t < n\} \sum_{j=1}^{\hat{n}_t} X_j \wedge \hat{\tau}_j \right] &\geq \mathbb{E} \left[ \mathbb{I}_{E_\eta} \mathbb{I}\{\hat{n}_t < n\} \left( T - \sqrt{\frac{T}{\hat{\alpha}_{\hat{n}_t+1}^+}} \right)_+ \right] \\ &\geq \left( T - \sqrt{\frac{T}{\alpha_* \log n}} \right)_+ \mathbb{P}(E_\eta \cap \{\hat{n}_t < n\}). \end{aligned} $$

On the other hand, by Jensen's inequality, the martingale property and since $\hat{n}$ is a stopping time,

$$ \mathbb{E} \left[ \left\| \sum_{j=1}^{\hat{n}} X_j \wedge \hat{\tau}_j - G(\hat{\tau}_j) \right\| \right] \leq \mathbb{E} \left[ \left\| \sum_{j=1}^{\hat{n}} v(\hat{\tau}_j) \right\|^{1/2} \right]. $$

From claim D.4.1, it follows that

$$ \mathbb{E} \left[ \mathbb{I}_{E_\eta} \mathbb{I}\{\hat{n}_t < n\} \sum_{j=1}^{\hat{n}} G(\hat{\tau}_j) \right] \geq \left( T - \sqrt{\frac{T}{\alpha_* \log n}} \right)_+ \mathbb{P}(E_\eta \cap \{\hat{n}_t < n\}) - \sqrt{\frac{T}{\alpha_*}} \sqrt{21 + 90z^{1/3} + 96z + \frac{\varepsilon}{\alpha_* T}}. $$

Thus,

$$ \begin{aligned} \mathbb{E} \left[ \mathbb{I}\{\hat{n} < n\} \sum_{j=1}^{\hat{n}} F(\hat{\tau}_j) \right] &\geq \left( (1 - 4\theta)\alpha_*T - 84\sqrt{\alpha_*T \log n} - zK \log n \left(\frac{42}{\theta} + 4\right) \right)_+ \mathbb{P}(E_\eta \cap \{\hat{n}_t < n\}) \\ &\quad - \frac{\varepsilon}{4} - \sqrt{\alpha_*T} \sqrt{21 + 90z^{1/3} + 96z + \frac{\varepsilon}{\alpha_*T}} \end{aligned} $$

It follows by equations (65), (67) and (68) that

$$ \begin{aligned} \mathbb{E} \left[ \mathbb{I}\{\hat{n} < n\} \sum_{j=1}^{\hat{n}} F(\hat{\tau}_j) \right] &\geq \left( (1 - 4\theta)\alpha_*T - w_1(\log n)\sqrt{\alpha_*T \log^3 n} - \frac{42}{\theta}zK \log n \right) \mathbb{P}(E_\eta \cap \{\hat{n}_t < n\}) \\ &\quad - \sqrt{\varepsilon} - \frac{\varepsilon}{4} - w_2(\log n)\sqrt{\alpha_*T \log^3 n} \end{aligned} $$

where

$$ w_1(x) = 0.278 + \frac{85}{x}, w_2(x) = \sqrt{\frac{21}{x^3} + \frac{126}{x^{8/3}} + \frac{260}{x^2}}. $$

Since $n \geq n_0$ and $w$ is non-increasing,

$$ w_1(\log n) \leq w_1(\log n_0) \leq 5.41 \text{ and } w_2(\log n) \leq w_2(\log n_0) \leq 1.011 $$
which yields

$$ \mathbb{E} \left[ \mathbb{I}\{\hat{n} < n\} \sum_{j=1}^{\hat{n}} F(\hat{\tau}_j) \right] \ge \left( (1-4\theta)\alpha_*T - 5.41\sqrt{\alpha_*T \log^3 n} - \frac{42}{\theta}zK \log n \right) \mathbb{P}(E_\eta \cap \{\hat{n}_t < n\}) \\ - \sqrt{\varepsilon} - \frac{\varepsilon}{4} - 1.011\sqrt{\alpha_*T \log^3 n}. \tag{82} $$

## D.6 Conclusion

Since

$$ \begin{aligned} \mathbb{P}(\hat{n} = n) + \mathbb{P}(E_\eta \cap \{\hat{n}_t < n\}) &= \mathbb{P}(E_\eta \cap \{\hat{n}_t = n\}) + \mathbb{P}(E_\eta \cap \{\hat{n}_t < n\}) \\ &= \mathbb{P}(E_\eta) \\ &\ge 1 - \frac{1}{\sqrt{n}}, \end{aligned} $$

combining equation (82) with equation (74) yields

$$ \begin{aligned} \mathbb{E} \left[ \sum_{j=1}^{\hat{n}} F(\hat{\tau}_j) \right] &\ge \left(1 - \frac{1}{\sqrt{n}}\right) \left( (1-4\theta)\alpha_*T - 5.41\sqrt{\alpha_*T \log^3 n} - \frac{42}{\theta}zK \log n \right) \\ &\quad - \sqrt{\varepsilon} - \frac{\varepsilon}{4} - 1.011\sqrt{\alpha_*T \log^3 n} \\ &\ge (1-4\theta)\alpha_*T - \sqrt{\alpha_*T} - \frac{42}{\theta}zK \log n - \sqrt{\varepsilon} - \frac{\varepsilon}{4} - 6.421\sqrt{\alpha_*T \log^3 n} \\ &\ge (1-4\theta)\alpha_*T - \frac{42}{\theta}zK \log n - \sqrt{\varepsilon} - \frac{\varepsilon}{4} - 6.43\sqrt{\alpha_*T \log^3 n} \end{aligned} $$

Optimizing over $\theta > 0$ finally yields

$$ \begin{aligned} \mathbb{E} \left[ \sum_{j=1}^{\hat{n}} F(\hat{\tau}_j) \right] &\ge \alpha_*T - 4\sqrt{42\alpha_*TzK \log n} - 6.43\sqrt{\alpha_*T \log^3 n} - \sqrt{\varepsilon} - \frac{\varepsilon}{4} \\ &\ge \alpha_*T - 59\sqrt{\alpha_*T \log^3 n} - \sqrt{\varepsilon} - \frac{\varepsilon}{4} \quad \text{by equation (68).} \end{aligned} $$

## E Proof of Theorem 3.10

The point of this section is to prove a minimax lower bound in the budge-constrained case. First, let us estimate the amount of information provided by the censored variables.

**Proposition E.1.** For any $j \in \{1, \dots, n\}$ let $\hat{\tau}_j : \mathbb{R}^{j-1} \to \mathbb{R}_+$ be a measurable function. For any $j \le n$ and $x \in \mathbb{R}^j$ let $\psi_j(x)$ denote the censored sample based
on the j first observations $x_1, \dots, x_j$. Formally, the function $\psi_j : \mathbb{R}^j \to \mathbb{R}^j$ is
defined recursively by $\psi_1(x) = \min(x, \hat{\tau}_1)$ and

$$
\psi_{j+1}(x, t) = (\psi_j(x), \min(t, \hat{\tau}_{j+1}(\psi_j(x))))
$$

Let P, Q be two continuous distributions on $\mathbb{R}_+$ with probability densities p, q
such that

$$
\left\| \frac{p}{q} - 1 \right\|_{\infty} \leq \delta.
$$

Let X, Y be two i.i.d random vectors of length n with common distribution P and Q. For any j ∈ {1, ..., n}, let P_j, Q_j be the distribution of ψ_j(X_1, ..., X_j) and ψ_j(Y_1, ..., Y_j) (respectively). Then

$$
D_{\text{KL}}(P_j || Q_j) \leq 2\delta^2(1 + \delta)\mathbb{E}\left[\sum_{k=1}^{j} \mathbb{I}\{X_k \leq \hat{\tau}_k(\psi_{k-1}(X_1, \dots, X_{k-1}))\}\right].
$$

Proof. We begin with the following lemma.

**Lemma E.2.** For any $\tau \ge 0$, let $P_\tau, Q_\tau$ be the distributions of $\min(X_1, \tau)$ and $\min(Y_1, \tau)$, respectively. Then

$$
D_{\mathrm{KL}}(P_{\tau} || Q_{\tau}) \leq 2\delta^2 Q([0; \tau]).
$$

Proof. We write $p = (1+\delta h)q$ where $h$ is a measurable function valued in $[-1; 1]$.
The distribution $P_\tau$ of the random variable $X \wedge \tau$ can be written as a mixture

$$
P_{\tau} = p\mathbb{I}_{[0;\tau]}\lambda + (1 - F_{P}(\tau))\delta_{\tau},
$$

where $\lambda$ is Lebesgue measure, $F_P$ is the cumulative distribution function of $P$
and $\delta_\tau$ is the Dirac mass on $\tau$. Similarly,

$$
Q_{\tau} = q \mathbb{I}_{[0;\tau]} \lambda + (1 - F_{Q}(\tau)) \delta_{\tau}.
$$

The measure $\mu = \lambda + \delta_{\tau}$ dominates both $P_{\tau}$ and $Q_{\tau}$ and we can set

$$
\frac{dP_{\tau}}{d\mu} = p_{\tau} : x \mapsto p(x) \mathbb{I}_{[0;\tau)}(x) + (1 - F_{P}(\tau)) \mathbb{I}\{x = \tau\}
$$

$$
\frac{dQ_{\tau}}{d\mu} = p_{\tau} : x \mapsto q(x) \mathbb{I}_{[0;\tau)}(x) + (1 - F_{Q}(\tau)) \mathbb{I}\{x = \tau\}.
$$

This yields

$$
D_{\text{KL}}(P_{\tau} || Q_{\tau}) = \int p_{\tau} \log \left( \frac{p_{\tau}}{q_{\tau}} \right) d\mu = \int_{0}^{\tau} p(t) \log \left( \frac{p(t)}{q(t)} \right) dt + (1 - F_{P}(\tau)) \log \left( \frac{1 - F_{P}(\tau)}{1 - F_{Q}(\tau)} \right).
$$

Using the elementary upper bound $\log(1+u) \le u$ yields

$$
\begin{align*}
\int_0^\tau p(t) \log \left( \frac{p(t)}{q(t)} \right) dt &= \int_0^\tau q(t) (1 + \delta h(t)) \log (1 + \delta h(t)) dt \\
&\le \int_0^\tau q(t) (1 + \delta h(t)) \delta h(t) dt \\
&\le \delta \int_0^\tau q(t) h(t) dt + \delta^2 \int_0^\tau h(t)^2 q(t) dt.
\end{align*}
$$
Now,

$$1 - F_P(\tau) = \int_{\tau}^{+\infty} q(t)(1 + \delta h(t))dt = 1 - F_Q(\tau) + \delta \int_{\tau}^{+\infty} h(t)q(t)dt$$

which yields

$$(1 - F_P(\tau)) \log \left( \frac{1 - F_P(\tau)}{1 - F_Q(\tau)} \right) = \left( 1 - F_Q(\tau) + \delta \int_{\tau}^{+\infty} h(t)q(t)dt \right) \log \left( 1 + \delta \frac{\int_{\tau}^{+\infty} h(t)q(t)dt}{1 - F_Q(\tau)} \right) \\ \leq \delta \int_{\tau}^{+\infty} h(t)q(t)dt + \delta^2 \frac{\left( \int_{\tau}^{+\infty} h(t)q(t)dt \right)^2}{1 - F_Q(\tau)}.$$

Combining both bounds and using the fact that $\int_{0}^{+\infty} h(t)q(t)dt = 0$ yields

$$D_{\text{KL}}(P_{\tau} || Q_{\tau}) \leq \delta^2 \int_{0}^{\tau} h(t)^2 q(t) dt + \delta^2 \frac{\left( \int_{\tau}^{+\infty} h(t)q(t)dt \right)^2}{1 - F_Q(\tau)}.$$

Since $h$ is valued in $[-1; 1]$,

$$D_{\text{KL}}(P_{\tau} || Q_{\tau}) \leq \delta^2 Q([0; \tau]) + \delta^2 \left| \int_{\tau}^{+\infty} h(t)q(t)dt \right|.$$

Since also $\int_{0}^{+\infty} h(t)q(t)dt = 0$,

$$\left| \int_{\tau}^{+\infty} h(t)q(t)dt \right| = \left| \int_{0}^{\tau} h(t)q(t)dt \right| \leq Q([0; \tau])$$

which finally yields the result. $\square$

<figure><img src="image_5.png" /></figure>

For any $j \leq n$ and any $z \in \mathbb{R}^j$, let $P_z^{(j)}$ and $Q_z^{(j)}$ denote the distributions of $\min(X_j, \hat{\tau}_j(z))$ and $\min(Y_j, \hat{\tau}_j(z))$ (respectively). By the chain rule for Kullback-Leibler divergence,

$$D_{\text{KL}}(P_{j+1} || Q_{j+1}) = D_{\text{KL}}(P_j || Q_j) + \mathbb{E}_{Z \sim P_j} \left[ D_{\text{KL}} \left( P_Z^{(j+1)} || Q_Z^{(j+1)} \right) \right].$$

Using the previous lemma yields

$$D_{\text{KL}} \left( P_Z^{(j+1)} || Q_Z^{(j+1)} \right) \leq \delta^2 Q \left( [0; \hat{\tau}_{j+1}(Z)] \right) \leq \delta^2 (1 + \delta) P \left( [0; \hat{\tau}_{j+1}(Z)] \right)$$

from which it follows that

$$\mathbb{E}_{Z \sim P_j} \left[ D_{\text{KL}} \left( P_Z^{(j+1)} || Q_Z^{(j+1)} \right) \right] \leq \delta^2 (1 + \delta) \mathbb{P} \left( X_{j+1} \leq \hat{\tau}_{j+1}(\psi_j(X_1, \dots, X_j)) \right).$$

The result follows by induction. $\square$

<figure><img src="image_6.png" /></figure>

Let us now define the hypotheses.