**Definition E.3.** For any $\alpha > 0$, $\delta, \theta \in [0; 1]$ and non-negative reals $a, b, c, d$ such that $a < b$ and $c < d$, let $w = (\alpha, \delta, \theta, a, b, c, d)$ and

$$p_w : x \mapsto (1 - \delta)\alpha e^{-\alpha x} + \theta\delta \frac{\mathbb{I}_{[a;b]}(x)}{b - a} + (1 - \theta)\delta \frac{\mathbb{I}_{[c;d]}(x)}{d - c}$$

be defined on $\mathbb{R}_+$. Let also $F_w$ be the cumulative distribution function associated with the probability density $p_w$, and let $G_w : t \mapsto \int_0^t (1 - F_w(s))ds$.

**Proposition E.4.** Let $w = (\alpha, \delta, \theta, a, b, c, d)$ be as in Definition E.3. Assume moreover that

$$\alpha \frac{b+a}{2} < 1, \theta = \frac{\alpha b}{1 + \alpha \frac{b-a}{2}}, \frac{d-c}{2} \le \frac{1}{\alpha}, \frac{d+c}{2} \ge b + \frac{1}{\alpha}.$$

The function $\frac{F_w}{G_w}$ attains a unique global maximum of $\alpha$ at the point $b$, where

$$G_w(b) = \frac{1 - e^{-\alpha b}}{\alpha} + \frac{\theta \delta}{\alpha} \ge \frac{1}{\alpha} \min(1 - e^{-\alpha b}, \theta).$$

It is non-increasing on intervals $[0; a]$ and $[b; c]$. Moreover,

$$\sup_{t \ge c} \frac{F_w(t)}{G_w(t)} = \frac{F_w(d)}{G_w(d)} < \alpha.$$

In particular, for any $x \in [b; c]$,

$$\sup_{t \notin [a; x]} \left\{ \frac{F_w(t)}{G_w(t)} \right\} = \max \left( (1 - \delta)\alpha, \frac{F_w(x)}{G_w(x)}, \frac{F_w(d)}{G_w(d)} \right)$$

*Proof.* For all $t \ge 0$

$$F_w(t) = (1 - \delta)(1 - e^{-\alpha t}) + \theta \delta \min \left( \frac{(t - a)_+}{b - a}, 1 \right) + (1 - \theta) \delta \min \left( \frac{(t - c)_+}{d - c}, 1 \right). \quad (83)$$

Thus, for all $t \in [0; a]$,

$$\frac{F_w(t)}{G_w(t)} = \frac{(1 - \delta)(1 - e^{-\alpha t})}{\frac{1 - \delta}{\alpha}(1 - e^{-\alpha t}) + \delta t} = \left( \frac{1}{\alpha} + \frac{\delta}{1 - \delta} \frac{t}{1 - e^{-\alpha t}} \right)^{-1}.$$

Since $t \mapsto 1 - e^{-\alpha t}$ is non-negative and concave, $t \mapsto \frac{1 - e^{-\alpha t}}{t}$ is non-increasing and so $\frac{F_w}{G_w}$ is non-increasing on $[0; a]$. For all $t \in [a; b]$,

$$\int_0^t \left[ 1 - \min \left( \frac{(s - a)_+}{b - a}, 1 \right) \right] ds = a + \int_a^t \frac{b - s}{b - a} ds = a + \frac{(b - a)^2}{2(b - a)} - \frac{(b - t)^2}{2(b - a)} = \frac{b + a}{2} - \frac{(b - t)^2}{2(b - a)}.$$

Let $g_{a,b} : t \mapsto \frac{b+a}{2} - \frac{(b-t)^2}{2(b-a)}$ and similarly for $g_{c,d}$. Thus, for all $t \in [a; b]$,

$$\frac{F_w(t)}{G_w(t)} = \frac{(1 - \delta)(1 - e^{-\alpha t}) + \theta \delta \frac{t-a}{b-a}}{(1 - \delta)^{\frac{1}{\alpha}}(1 - e^{-\alpha t}) + \theta \delta g_{a,b}(t) + (1 - \theta) \delta t} = \alpha + \frac{\theta \delta \frac{t-a}{b-a} - \alpha \theta \delta g_{a,b}(t) - \alpha(1 - \theta) \delta t}{(1 - \delta)^{\frac{1}{\alpha}}(1 - e^{-\alpha t}) + \theta \delta g_{a,b}(t)}$$
Since $g_{a,b}$ is a concave function, we have for all $t \in [a; b]$,

$$ \theta \delta \frac{t-a}{b-a} - \alpha \theta \delta g_{a,b}(t) - \alpha(1-\theta)\delta t \leq \max \left( -\alpha \delta a, \delta \left( \theta - \alpha \theta \frac{b+a}{2} - \alpha(1-\theta)b \right) \right) = 0 $$

which is attained at $b$, since

$$ \theta - \alpha \theta \frac{b+a}{2} - \alpha(1-\theta)b = \theta \left( 1 + \alpha \frac{b-a}{2} \right) - \alpha b = 0. $$

It follows that

$$ \begin{aligned} G_w(b) &= (1-\delta)\frac{1}{\alpha}(1-e^{-\alpha b}) + \theta\delta g_{a,b}(b) + (1-\theta)\delta b \\ &= (1-\delta)\frac{1}{\alpha}(1-e^{-\alpha b}) + \theta\delta\frac{b+a}{2} + (1-\theta)\delta b \\ &= (1-\delta)\frac{1}{\alpha}(1-e^{-\alpha b}) + \frac{\delta}{\alpha}\left(\alpha b - \alpha\frac{b-a}{2}\theta\right) \\ &= (1-\delta)\frac{1}{\alpha}(1-e^{-\alpha b}) + \frac{\theta\delta}{\alpha} \\ &\geq \frac{1}{\alpha}\min(1-e^{-\alpha b}, \theta). \end{aligned} $$

For all $t \in (b; c]$,

$$ \begin{aligned} \frac{F_w(t)}{G_w(t)} &= \frac{(1-\delta)(1-e^{-\alpha t}) + \theta\delta}{(1-\delta)\frac{1}{\alpha}(1-e^{-\alpha t}) + \theta\delta\frac{b+a}{2} + (1-\theta)\delta t} \\ &= \alpha + \frac{\theta\delta - \theta\delta\alpha\frac{b+a}{2} - \alpha(1-\theta)\delta t}{(1-\delta)\frac{1}{\alpha}(1-e^{-\alpha t}) + \theta\delta\frac{b+a}{2} + (1-\theta)\delta t} \\ &= \alpha + \frac{-\alpha(1-\theta)\delta(t-b)}{(1-\delta)\frac{1}{\alpha}(1-e^{-\alpha t}) + \theta\delta\frac{b+a}{2} + (1-\theta)\delta t} \end{aligned} $$

which is non-increasing and strictly less than $\alpha$ by concavity of the denominator.

For all $t \in [c; d]$,

$$ \begin{aligned} \frac{F_w(t)}{G_w(t)} &= \frac{(1-\delta)(1-e^{-\alpha t}) + \theta\delta + (1-\theta)\delta\frac{t-c}{d-c}}{(1-\delta)\frac{1}{\alpha}(1-e^{-\alpha t}) + \theta\delta\frac{b+a}{2} + (1-\theta)\delta g_{c,d}(t)} \\ &= \alpha + \frac{\theta\delta(1-\alpha\frac{b+a}{2}) + (1-\theta)\delta\frac{t-c}{d-c} - \alpha(1-\theta)\delta g_{c,d}(t)}{(1-\delta)\frac{1}{\alpha}(1-e^{-\alpha t}) + \theta\delta\frac{b+a}{2} + (1-\theta)\delta g_{c,d}(t)} \\ &= \alpha + \frac{N(t)}{D(t)} \end{aligned} $$

where the numerator $N(t)$ is convex by concavity of $g_{c,d}$. It follows that

$$ N(t) \leq \max(N(c), N(d)). $$
Now, by equation ..,

$$N(c) = \theta\delta\left(1 - \alpha\frac{b+a}{2}\right) - \alpha(1-\theta)\delta c = -\alpha(1-\theta)\delta(c-b) < 0$$

and

$$N(d) = \theta\delta\left(1 - \alpha\frac{b+a}{2}\right) + (1-\theta)\delta - \alpha(1-\theta)\delta\frac{d+c}{2} = N(c) + (1-\theta)\delta - \alpha(1-\theta)\delta\frac{d-c}{2} \geq N(c)$$

since $\frac{d-c}{2} \leq \frac{1}{\alpha}$. Moreover, plugging in the value of $N(c)$ yields

$$\begin{aligned} N(d) &= (1 - \theta)\delta\left(1 - \alpha(c - b) - \alpha\frac{d - c}{2}\right) \\ &= (1 - \theta)\delta\left(1 + \alpha b - \alpha\frac{d + c}{2}\right) \\ &< 0 \text{ since } \frac{d + c}{2} > b + \frac{1}{\alpha}. \end{aligned}$$

Thus, $N(t) \leq N(d) < 0$ for all $t \in [c; d]$. Since $D$ is non-negative and non-decreasing on $[c; d]$, it follows that

$$\frac{F_w(t)}{G_w(t)} = \alpha + \frac{N(t)}{D(t)} \leq \alpha + \frac{N(d)}{D(d)} = \frac{F_w(d)}{G_w(d)} < \alpha.$$

For all $t > d$,

$$\frac{F_w(t)}{G_w(t)} = \frac{(1 - \delta)(1 - e^{-\alpha t}) + \delta}{(1 - \delta)\frac{1}{\alpha}(1 - e^{-\alpha t}) + \theta\delta\frac{b+a}{2} + (1 - \theta)\delta\frac{d+c}{2}} = h(1 - e^{-\alpha t})$$

where $h$ is the rational function

$$h(u) = \frac{(1 - \delta)u + \delta}{\frac{1 - \delta}{\alpha}u + \theta\delta\frac{b+a}{2} + (1 - \theta)\delta\frac{d+c}{2}}$$

which is monotone on $\mathbb{R}_+$ between $h(0) = \frac{1}{\theta\frac{b+a}{2} + (1-\theta)\frac{d+c}{2}}$ and $h(+\infty) = \alpha$. Since

$$0 > N(d) = \theta\delta\left(1 - \alpha\frac{b+a}{2}\right) + (1-\theta)\delta - \alpha(1-\theta)\delta\frac{d+c}{2} = \delta\left[1 - \alpha\left(\theta\frac{b+a}{2} + (1-\theta)\frac{d+c}{2}\right)\right],$$

it follows that $h(+\infty) < h(0)$ and hence $h$ is non-increasing. Thus, $\frac{F_w}{G_w}$ is non-increasing on $[d; +\infty)$. $\square$

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

Let us now conduct the proof of the lower bound. Fix some $\delta \in [0; 1)$ (to be specified later), let

$$a_0 = 0, b_0 = \frac{1}{3\alpha}, \theta_0 = \frac{2\alpha b_0}{2 + \alpha(b_0 - a_0)} = \frac{2}{7} \text{ and } a_1 = \frac{2}{3\alpha}, b_1 = \frac{1}{\alpha}, \theta_1 = \frac{2\alpha b_1}{2 + \alpha(b_1 - a_1)} = \frac{6}{7}.$$
Let $d > c > \frac{2}{\alpha}$ and define $w^i = (\alpha, \delta, \theta_i, a_i, b_i, c, d)$ for $i \in \{0; 1\}$. For $i = 0, 1$, let $P_i$ be the distribution with density $p_i = p_{w_i}$ given by Definition E.3. Similarly, let $F_i = F_{w_i}$ and $G_i = G_{w_i}$. By lemma E.4, $\alpha_*(P_i) = \alpha$ and

$$G_i \left( \sup \operatorname{argmax}_{t>0} \frac{F_i(t)}{G_i(t)} \right) = G_i(b_i) \geq \frac{1}{\alpha} \min (1 - e^{-\alpha b_i}, \theta_i) \geq \frac{0.28}{\alpha}.$$

It follows that $P_i \in \mathcal{P}_\alpha$ for both $i \in \{0; 1\}$.

Let $\mathbb{P}_i$ denote the distribution of

$$(X_1 \wedge \hat{\tau}_1, \dots, X_n \wedge \hat{\tau}_n) = \psi_n(X_1, \dots, X_n)$$

when $X_1, \dots, X_n$ are i.i.d with distribution $P_i$. Similarly, let $\mathbb{E}_i$ denote the expectation taken under this distribution. Since

$$\begin{align*}
\sup_{t>0} \frac{p_0(t)}{p_1(t)} &= \sup_{t \in [a_0; b_0]} \frac{(1-\delta)\alpha e^{-\alpha t} + \frac{\delta}{b_0-a_0}}{(1-\delta)\alpha e^{-\alpha t}} \\
&= 1 + 3 \frac{\delta}{1-\delta} \sup_{t \le \frac{1}{3\alpha}} e^{\alpha t} \\
&\le 1 + 4.2 \frac{\delta}{1-\delta} \\
&\le 1 + 8.4\delta
\end{align*}$$

and

$$\begin{align*}
\inf_{t>0} \frac{p_0(t)}{p_1(t)} &= \inf_{t \in [a_1; b_1]} \frac{(1-\delta)\alpha e^{-\alpha t}}{(1-\delta)\alpha e^{-\alpha t} + \frac{\delta}{b_1-a_1}} \\
&= \inf_{t \in [a_1; b_1]} \frac{1-\delta}{1-\delta + \frac{\delta e^{\alpha t}}{\alpha(b_1-a_1)}} \\
&\ge \frac{1-\delta}{1-\delta + 3\delta e} \\
&\ge 1 - 3e\delta,
\end{align*}$$

it follows from Proposition E.1 that

$$\begin{align*}
D_{\mathrm{KL}}(\mathbb{P}_0 || \mathbb{P}_1) &\le 142\delta^2(1+\delta)\mathbb{E}_0 \left[ \sum_{j=1}^n F_0(\hat{\tau}_j) \right] \\
&\le 142\delta^2(1+\delta)\alpha \mathbb{E}_0 \left[ \sum_{j=1}^n G_0(\hat{\tau}_j) \right] \\
&= 142\delta^2(1+\delta)\alpha \mathbb{E}_0 \left[ \sum_{j=1}^n X_j \wedge \hat{\tau}_j \right] \\
&\le 142\delta^2(1+\delta)\alpha T.
\end{align*}$$
Assume that $\alpha T \ge 1$ (otherwise, the result is trivially true). Fix some $u \in (0; 1)$ and let $\delta = \frac{\sqrt{u}}{\sqrt{142\alpha T}}$, then

$$ \delta = \frac{\sqrt{u}}{\sqrt{142\alpha T}} \quad \text{and} \quad \mathrm{D}_{\mathrm{KL}}(\mathbb{P}_0 || \mathbb{P}_1) \le 1.1u. \qquad (84) $$

Let now $S_0 = [0; \frac{2}{3\alpha})$ and $S_1 = [\frac{2}{3\alpha}; +\infty)$. By Proposition E.4,

$$ \sup_{t \notin S_1} \frac{F_1(t)}{G_1(t)} = \lim_{t \to 0} \frac{F_1(t)}{G_1(t)} = \lim_{t \to 0} \frac{F_1(t)}{t} = p_1(0^+) = (1 - \delta)\alpha. $$

Again by Proposition E.4,

$$ \sup_{t \notin S_0} \frac{F_0(t)}{G_0(t)} = \max \left( \frac{F_0\left(\frac{2}{3\alpha}\right)}{G_0\left(\frac{2}{3\alpha}\right)}, \frac{F_0(d)}{G_0(d)} \right). $$

Note that $\frac{F_0(d)}{G_0(d)} \to 0$ as $d \to \infty$ (remark that $d$ is a parameter of $F_0$ (suppressed by notation)). We choose $d$ large enough such that

$$ \begin{aligned} \sup_{t \notin S_0} \frac{F_0(t)}{G_0(t)} &= \frac{F_0\left(\frac{2}{3\alpha}\right)}{G_0\left(\frac{2}{3\alpha}\right)} \\ &= \frac{(1 - \delta)\left(1 - e^{-\frac{2}{3}}\right) + \frac{2}{7}\delta}{\frac{1 - \delta}{\alpha}\left(1 - e^{-\frac{2}{3}}\right) + \frac{2}{7}\delta\frac{b_0 + a_0}{2} + \frac{5}{7}\delta\frac{2}{3\alpha}} \\ &= \alpha\frac{(1 - \delta)\left(1 - e^{-\frac{2}{3}}\right) + \frac{2}{7}\delta}{(1 - \delta)\left(1 - e^{-\frac{2}{3}}\right) + \frac{11}{21}\delta} \\ &= \alpha - \alpha\frac{\frac{5}{21}\delta}{(1 - \delta)\left(1 - e^{-\frac{2}{3}}\right) + \frac{11}{21}\delta} \\ &\le \alpha - \frac{5}{11}\delta\alpha \text{ since } 1 - e^{-\frac{2}{3}} \le 0.487 < \frac{11}{21}. \end{aligned} $$

For $i = 0, 1$, define the event

$$ B_i = \left\{ \sum_{k=1}^{n} (X_k \wedge \hat{\tau}_k) \mathbb{I}\{\hat{\tau}_k \in S_i\} > \frac{1}{2} \sum_{k=1}^{n} X_k \wedge \hat{\tau}_k \right\}, $$

which is measurable relative to the data $(X_k \wedge \hat{\tau}_k)_{1 \le k \le n}$. Since the sets $S_0, S_1$ are disjoint, so are the events $B_0, B_1$. We can therefore choose a measurable function $\eta(X_1 \wedge \hat{\tau}_1, \dots, X_n \wedge \hat{\tau}_n) \in \{0; 1\}$ such that $\hat{\eta} = 0$ on $B_0$ and $\hat{\eta} = 1$ on $B_1$. By [22, Chapter 2, Theorem 2.2] and equation (84),

$$ \max_{i \in \{0; 1\}} \{\mathbb{P}_i(B_i^c)\} \ge \max_{i \in \{0; 1\}} \{\mathbb{P}_i(\hat{\eta} \ne i)\} \ge \max \left( \frac{1}{4} \exp(-1.1u), \frac{1}{2} - \frac{\sqrt{1.1u}}{2\sqrt{2}} \right). \qquad (85) $$
Moreover, for any $i \in \{0; 1\}$,

$$
\begin{align*}
\mathbb{E}_i \left[ \sum_{k=1}^{n} \mathbb{I}\{X_k \le \hat{\tau}_k\} \right] &= \mathbb{E}_i \left[ \sum_{k=1}^{n} F_i(\hat{\tau}_k) \right] \\
&= \mathbb{E}_i \left[ \sum_{k=1}^{n} F_i(\hat{\tau}_k) \mathbb{I}\{\hat{\tau}_k \in S_i\} + \sum_{k=1}^{n} F_i(\hat{\tau}_k) \mathbb{I}\{\hat{\tau}_k \notin S_i\} \right] \\
&\le \mathbb{E}_i \left[ \alpha \sum_{k=1}^{n} G_i(\hat{\tau}_k) \mathbb{I}\{\hat{\tau}_k \in S_i\} + \alpha \left(1 - \frac{5\delta}{11}\right) \sum_{k=1}^{n} G_i(\hat{\tau}_k) \mathbb{I}\{\hat{\tau}_k \notin S_i\} \right] \\
&= \mathbb{E}_i \left[ \alpha \left(1 - \frac{5\delta}{11}\right) \sum_{k=1}^{n} G_i(\hat{\tau}_k) + \frac{5\delta}{11} \alpha \sum_{k=1}^{n} G_i(\hat{\tau}_k) \mathbb{I}\{\hat{\tau}_k \in S_i\} \right] \\
&= \mathbb{E}_i \left[ \alpha \left(1 - \frac{5\delta}{11}\right) \sum_{k=1}^{n} (X_k \wedge \hat{\tau}_k) + \frac{5\delta}{11} \alpha \sum_{k=1}^{n} (X_k \wedge \hat{\tau}_k) \mathbb{I}\{\hat{\tau}_k \in S_i\} \right]
\end{align*}
$$

By definition of $B_i$, it follows that

$$
\begin{align*}
\mathbb{E}_i \left[ \sum_{k=1}^{n} \mathbb{I}\{X_k \le \hat{\tau}_k\} \right] & \\
&\le \mathbb{E}_i \left[ \alpha \left(1 - \frac{5\delta}{11}\right) \sum_{k=1}^{n} (X_k \wedge \hat{\tau}_k) + \frac{5\delta}{11} \alpha \mathbb{I}_{B_i} \sum_{k=1}^{n} (X_k \wedge \hat{\tau}_k) + \frac{\alpha}{2} \frac{5\delta}{11} \mathbb{I}_{B_i^c} \sum_{k=1}^{n} (X_k \wedge \hat{\tau}_k) \right] \\
&= \mathbb{E}_i \left[ \alpha \left(1 - \frac{5\delta}{22}\right) \sum_{k=1}^{n} (X_k \wedge \hat{\tau}_k) + \frac{5\delta}{22} \alpha \mathbb{I}_{B_i} \sum_{k=1}^{n} (X_k \wedge \hat{\tau}_k) \right] \\
&\le \alpha \left(1 - \frac{5\delta}{22}\right) T + \frac{5\delta}{22} \mathbb{P}_i(B_i) \alpha T \\
&= \alpha T - \frac{5\delta}{22} \mathbb{P}_i(B_i^c) \alpha T.
\end{align*}
$$

Thus,

$$
\min_{i \in \{0;1\}} \mathbb{E}_i \left[ \sum_{k=1}^{n} \mathbb{I}\{X_k \le \hat{\tau}_k\} \right] \le \alpha T - \frac{5\delta}{22} \alpha T \max_{i \in \{0;1\}} \mathbb{P}_i(B_i^c).
$$

By equation (84) defining $\delta$ and equation (85) above, it follows that

$$
\min_{i \in \{0;1\}} \mathbb{E}_i \left[ \sum_{k=1}^{n} \mathbb{I}\{X_k \le \hat{\tau}_k\} \right] \le \alpha T - \frac{5}{22} 0.084 \sqrt{u\alpha T} \max \left( \frac{1}{4} \exp(-1.1u), \frac{1}{2} - \frac{\sqrt{1.1u}}{2\sqrt{2}} \right).
$$

Since $(\hat{\tau}_k)_{1 \le k \le n}$ was arbitrary, this proves the minimax upper bound on the
reward by setting $u = \frac{1}{2\cdot 2}$.
# F Proofs of section 5

## F.1 Characterizing the optimum

**Proposition F.1.** For any $\tau \in [0; \tau_M]$, $\hat{r}_c(\tau, \tau_M) \ge 0$ if and only if there exists $f \in [f_l; f_u]$ such that

$$ \sup_{t<\tau} \left\{ f(t) + c \int_t^\tau (1-f(s))ds \right\} \le W_u(\tau, \tau_M). \quad (86) $$

Moreover, if $\hat{r}_c(\tau, \tau_M) \ge -\delta$, then there exists $f \in [f_l; f_u]$ such that

$$ \sup_{t<\tau} \left\{ f(t) + c \int_t^\tau (1-f(s))ds \right\} \le W_u(\tau, \tau_M) + \delta. \quad (87) $$

*Proof.* Let $\eta = W_u(\tau, \tau_M)$. Fix an $f$ such that equation (86) holds. For any $t \in [0; \tau]$, let

$$ h(t) = \int_{\tau-t}^{\tau} (1-f(s))ds. $$

$h$ is non-decreasing, hence absolutely continuous and

$$ h'(t) = 1 - f(\tau - t) \ge 1 - f_u(\tau - t) $$

at every continuity point of $f(\tau - \cdot)$, in particular almost everywhere on $[0; \tau]$. Moreover, for almost every $t \in [0; \tau]$,

$$ \begin{aligned} (86) \implies & f(\tau - t) + ch(t) \le \eta \\ \implies & 1 - \eta + ch(t) \le 1 - f(\tau - t) \\ \implies & h'(t) \ge \max(1 - \eta + ch(t), 1 - f_u(\tau - t)). \end{aligned} $$

Since also $h(0) = \psi_\tau(0) = 0$, it follows by standard comparison arguments that $h \ge \psi_\tau(c, \eta, \cdot)$. Thus, for almost every $t$,

$$ \begin{aligned} \frac{d}{dt} \psi_\tau(c, \eta, t) &= \max(1 - \eta + c\psi_\tau(c, \eta, t), 1 - f_u(\tau - t)) \\ &\le \max(1 - \eta + ch(t), 1 - f_u(\tau - t)) \\ &\le h'(t) \\ &= 1 - f(\tau - t) \\ &\le 1 - f_l(\tau - t). \end{aligned} $$

Conversely, assume that $\psi_\tau(c, \eta, \cdot)$ is such that

$$ \frac{d}{dt} \psi_\tau(c, \eta, t) \le 1 - f_l(\tau - t) $$

almost everywhere on $[0; \tau]$. Thus, by definition of $\psi_\tau$,

$$ 1 - f_u(\tau - t) \le \frac{d}{dt} \psi_\tau(c, \eta, t) \le 1 - f_l(\tau - t) $$
for a.e $t \in [0; \tau]$. Let then

$$f : t \mapsto \max(\min(\eta - c\psi_{\tau}(c, \eta, \tau - t), f_u(t)), f_l(t)).$$

which belongs to $[f_l; f_u]$ by definition and is equal to

$$1 - \frac{d}{dt}\psi_{\tau}(c, \eta, \tau - t)$$

a.e. It follows that for all $t \in [0; \tau]$,

$$\int_{\tau-t}^{\tau} (1 - f(s))ds = \psi_{\tau}(c, \eta, t) - \psi_{\tau}(c, \eta, 0) = \psi_{\tau}(c, \eta, t).$$

This yields

$$f(\tau - t) + c \int_{\tau-t}^{\tau} (1 - f(s))ds = 1 - \frac{d}{dt}\psi_{\tau}(c, \eta, t) + c\psi_{\tau}(c, \eta, t) \leq \eta$$

a.e on $[0; \tau]$, by definition of $\psi_{\tau}$. Now, by monotony of $f$ and continuity of $t \mapsto \int_{\tau-t}^{\tau} (1 - f(s))ds$, for any $t < \tau$ and any $\delta > 0$, there exists $t' \in [t; \tau)$ such that

$$f(\tau - t) + c \int_{\tau-t}^{\tau} (1 - f(s))ds \leq f(\tau - t') + c \int_{\tau-t'}^{\tau} (1 - f(s))ds + \delta \leq W_u(\tau, \tau_M) + \delta,$$

which proves equation (86). To prove equation (87), remark that $\eta \mapsto \psi_{\tau}(c, \eta, t)$ is non-increasing by Definition 5.2 and hence

$$\inf_{t \in (0; \tau)} \{\eta + \delta - c\psi_{\tau}(c, \eta + \delta, t) - \tilde{f}_l(\tau - t)\} \geq \inf_{t \in (0; \tau)} \{\eta + \delta - c\psi_{\tau}(c, \eta, t) - \tilde{f}_l(\tau - t)\} \geq 0$$

which implies equation (86) with $\eta$ replaced by $\eta + \delta$. $\square$

## F.2 Proof of Proposition 5.4

By construction, either $\hat{t}_U = \tau_M$ or $\hat{r}_c(\hat{t}_U, \tau_M) < \delta$ 0. In the first case, $\hat{t}_U \geq \hat{\tau}_{\max}(c, \tau_M)$ by definition. Let $\tau = \hat{t}_U$. In the second case $\hat{r}_c(\hat{t}_U, \tau_M) < 0$, so for any $f \in [f_l; f_u]$ by Proposition F.1,

$$\begin{aligned} \sup_{t<\tau} \{f(t) + c \int_t^\tau (1-f(s))ds\} &> W_u(\tau, \tau_M) \\ &= \sup_{t \in [\tau; \tau_M]} \{f_u(t) - c \int_\tau^t (1-f_u(s))ds\} \\ &\geq \sup_{t \in [\tau; \tau_M]} \{f(t) - c \int_\tau^t (1-f(s))ds\}. \end{aligned}$$

It follows that

$$\sup_{t \in [0; \tau)} \{f(t) - cg(t)\} > \sup_{t \in [\tau; \tau_M]} \{f(t) - cg(t)\}$$
where $g: t \mapsto \int_{0}^{t}(1-f(s))ds$. This implies that

$$ \operatorname{argmax}_{t \in [0; \tau_M]} \{f(t) - cg(t)\} \subset [0; \tau) $$

By lemma C.1, it follows that

$$ \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\} < \tau $$

which implies in particular that

$$ \hat{\tau}_{c, \delta} \geq \tau = \hat{t}_U \geq \hat{\tau}_{\max}(c, \tau_M). $$

This proves the first point.

Let us prove the second point. Let

$$ \hat{t} = \begin{cases} \hat{t}_L & \text{if } \hat{r}_c(\tau_M, \tau_M) < \delta^a 0 \\ \tau_M & \text{else.} \end{cases} \qquad (88) $$

In either case, $-(\hat{r}_c(\hat{t}, \tau_M) < \delta^a 0)$ and therefore $\hat{r}_c(\hat{t}, \tau_M) \geq -\delta$. By Proposition F.1, there exists some $f_0 \in [f_l; f_u]$ such that

$$ \sup_{t < \hat{t}} \left\{ f_0(t) + c \int_t^{\hat{t}} (1 - f_0(s)) ds \right\} \leq W_u(\hat{t}, \tau_M) + \delta. \qquad (89) $$

Define

$$ f: t \mapsto \begin{cases} f_0(t) & \text{if } t < \hat{t} \\ f_u(t) & \text{if } t \geq \hat{t}. \end{cases} \qquad (90) $$

By definition of $\hat{\tau}_{c,\delta}$ and since $g_l$ is 1-Lipschitz continuous,

$$ \begin{aligned} f(\hat{\tau}_{c,\delta}) - cg(\hat{\tau}_{c,\delta}) &= f_u(\hat{\tau}_{c,\delta}) - cg_l(\hat{\tau}_{c,\delta}) - cg(\hat{t}) + cg_l(\hat{t}) \\ &\geq \sup_{t \in [\hat{t}_U; \tau_M]} \{f_u(t) - cg_l(t)\} - c\epsilon - cg(\hat{t}) + cg_l(\hat{t}). \end{aligned} $$

On the one hand,

$$ f(\hat{\tau}_{c,\delta}) - cg(\hat{\tau}_{c,\delta}) \geq \sup_{t \in [\hat{t}_U; \tau_M]} \{f_u(t) - c(g_l(t) - g_l(\hat{t}) + g(\hat{t}))\} - c\epsilon $$

which yields

$$ f(\hat{\tau}_{c,\delta}) - cg(\hat{\tau}_{c,\delta}) \geq \sup_{t \in [\hat{t}_U; \tau_M]} \{f(t) - cg(t)\} - \delta. \qquad (91) $$

On the other hand,

$$ \begin{aligned} f(\hat{\tau}_{c,\delta}) - cg(\hat{\tau}_{c,\delta}) &\geq \sup_{t \in [\hat{t}_U; \tau_M]} \{f_u(t) - cg_l(t) + cg_l(\hat{t}_U)\} - cg(\hat{t}) + c(g_l(\hat{t}) - g_l(\hat{t}_U)) - c\epsilon \\ &= W_u(\hat{t}_U, \tau_M) - cg(\hat{t}) + c(g_l(\hat{t}) - g_l(\hat{t}_U)) - \delta. \end{aligned} $$
Either $\hat{t} = \tau_M = \hat{t}_U$ or $\hat{t} = \hat{t}_L$ and $\neg (\hat{t}_L + \varepsilon <_{\varepsilon} \hat{t}_U)$, which yields $\hat{t}_U - \hat{t}_L \le 2\varepsilon$.
In either case,

$$g_l(\hat{t}) - g_l(\hat{t}_U) \le 2\varepsilon$$

and so

$$f(\hat{\tau}_{c,\delta}) - cg(\hat{\tau}_{c,\delta}) \ge W_u(\hat{t}_U, \tau_M) - cg(\hat{t}) - 2\delta.$$

Remark that since $f_u, g_l$ are non-decreasing and $\hat{t} \le \hat{t}_U$,

$$\begin{aligned} W_u(\hat{t}_U, \tau_M) &= \sup_{t \in [0; \tau_M]} \{f_u(t) - c(g_l(t) - g_l(\hat{t}_U))_+\} \\ &\ge \sup_{t \in [0; \tau_M]} \{f_u(t) - c(g_l(t) - g_l(\hat{t}))_+\} \\ &= W_u(\hat{t}, \tau_M). \end{aligned}$$

Therefore,

$$f(\hat{\tau}_{c,\delta}) - cg(\hat{\tau}_{c,\delta}) \ge W_u(\hat{t}, \tau_M) - cg(\hat{t}) - 2\delta$$

By equation (89) and definition of $f$, it follows that

$$\begin{aligned} f(\hat{\tau}_{c,\delta}) - cg(\hat{\tau}_{c,\delta}) &\ge \sup_{t \in [0; \hat{t})} \left\{ f(t) + c \int_t^{\hat{t}} (1 - f(s)) ds \right\} - cg(\hat{t}) - 3\delta \\ &= \sup_{t \in [0; \hat{t})} \left\{ f(t) + c(g(\hat{t}) - g(t)) \right\} - cg(\hat{t}) - 3\delta \\ &= \sup_{t \in [0; \hat{t})} \{f(t) - cg(t)\} - 3\delta. \end{aligned}$$

Together with equation (91), this proves that

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

which concludes the proof.

## F.3 Proof of claim 5.7.1

Assume first that $y \ge y_{\min}(\alpha, t)$. For all $s \in [0; t]$, let

$$g_1(s) = y - \psi_t(\alpha, \alpha y, t - s).$$

Then $g_1(t) = y \le g_u(t)$ and by equation (38),

$$g_1(0) = y - \psi_t(\alpha, \alpha y, t) \ge y_{\min}(\alpha, t) - \psi_t(\alpha, \alpha y_{\min}(\alpha, t), t) \ge 0 = g_u(0).$$

By continuity, there exists some $s \in [0; t]$ such that $g_1(s) = g_u(s)$ and we may define

$$s_* = t - \min\{x \in [0; t] : g_1(t - x) = g_u(t - x)\}.$$

Let us define

$$f : s \mapsto \begin{cases} f_l(s) & \text{if } s < s_* \\ \max(f_l(s), \min(\alpha g_1(s), f_u(s))) & \text{if } s \ge s_* \end{cases} \quad (92)$$
Thus, $f \in [f_l; f_u]$ by definition. By equation (39), for almost all $s \in [0; t]$,

$$1 - \alpha g_1(s) = 1 - \alpha y + \alpha \psi_t(\alpha, \alpha y, t - s) \le 1 - f_l(s)$$

which implies that $\alpha g_1(s) \ge f_l(s)$ and hence that $f(s) = \min(f_u(s), \alpha g_1(s))$ for almost all $s \ge s_*$. Let now

$$g : s \mapsto \int_0^s (1 - f(x)) dx.$$

For any $s \le s_*$,

$$g(s) = \int_{0}^{s} (1 - f_{l}(x)) dx = g_{u}(s)$$

while for any $s \ge s_*$,

$$\begin{align*}
g(s) &= g(s_*) + \int_{s_*}^{s} \max(1 - f_u(x), 1 - \alpha g_1(x)) dx \\
&= g_u(s_*) + \int_{s_*}^{s} \max(1 - f_u(x), 1 - \alpha y + \alpha \psi_t(\alpha, \alpha y, t - x)) dx \\
&= g_u(s_*) + \int_{s_*}^{s} -\frac{d}{dx} \psi_t(\alpha, \alpha y, t - x) dx \\
&= g_u(s_*) + \psi_t(\alpha, \alpha y, t - s_*) - \psi_t(\alpha, \alpha y, t - s) \\
&= g_u(s_*) + g_1(s) - g_1(s_*) \\
&= g_1(s)
\end{align*}$$

by definition of $s_*$. It follows that

$$\sup_{s<s_*} \frac{f(s)}{g(s)} = \sup_{s<s_*} \frac{f_l(s)}{g_u(s)} \le \hat{\alpha}_t \le \alpha$$

and that

$$\frac{f(s)}{g(s)} = \frac{\min(f_u(s), \alpha g_1(s))}{g_1(s)} \le \alpha$$

for almost all $s \in [s_*; t]$. In fact, this is true for all $s \in [s_*; t)$. Take some $s \in [s_*; t)$ (assuming this interval is non-empty). There exists a sequence $(s_k)_k$ converging to $s$, such that $s_k \ge s$ for all $k$ and such that

$$\frac{f(s_k)}{g(s_k)} \le \alpha.$$

Since $f$ is non-decreasing, it follows that

$$\frac{f(s)}{g(s)} \le \frac{f(s_k)}{g(s)} \le \alpha \frac{g(s_k)}{g(s)} \to \alpha$$

since $g$ is continuous. This proves that

$$\sup_{s \in [s_*; t)} \frac{f(s)}{g(s)} \le \alpha.$$
Moreover, $g(t) = g_1(t) = y - \psi(\alpha, \alpha y, 0) = y$, which proves the first implication. Conversely, assume that $f \in [f_l; f_u]$ is such that

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

where

$$g : s \mapsto \int_{0}^{s} (1 - f(x)) dx.$$

Then for any $s \in (0; t)$,

$$\begin{aligned} 1 - f(t - s) &\ge 1 - \alpha g(t - s) \\ &= 1 - \alpha g(t) + \alpha [g(t) - g(t - s)] \\ &= 1 - \alpha y + \alpha [g(t) - g(t - s)]. \end{aligned}$$

Since $f \in [f_l; f_u]$, it follows that

$$1 - f(t - s) \ge \max(1 - f_u(t - s), 1 - \alpha y + \alpha[g(t) - g(t - s)]).$$

Defining the function

$$h : s \mapsto g(t) - g(t - s),$$

we obtain the differential inequality

$$h'(s) \ge \max(1 - f_u(t - s), 1 - \alpha y + \alpha h(s))$$

which implies that $h \ge \psi_t(\alpha, \alpha y, \cdot)$ by equation (34) and a comparison argument. In particular,

$$y = g(t) = h(t) \ge \psi_t(\alpha, \alpha y, t)$$

which is equation (38). Moreover, for almost all $s \in (0; t]$,

$$\begin{aligned} 1 - \alpha y + \alpha \psi_t(y, \alpha y, s) &\le 1 - \alpha y + \alpha h(s) \\ &\le h'(s) \\ &= 1 - f(t - s) \\ &\le 1 - f_l(t - s). \end{aligned}$$

Since $f \in [f_l; f_u]$, $f_l \le f_u$ and so equation (39) holds. It follows by definition 5.6 that $y \ge y_{\min}(\alpha, t)$.

## F.4 Properties of $\psi_t$ and $y_{\min}$

**Lemma F.2.** For any $s, t, \lambda \ge 0$ and almost all $\alpha > 0$,

$$\partial_{\alpha} (\alpha \psi_t(\alpha, \lambda, s)) \ge 0$$

and the function $\alpha \mapsto \alpha \psi_t(\alpha, \lambda, s)$ is non-decreasing. The inequality is strict if either $\lambda < 1$ or $f_u(t) < 1$, in which case the function increases.
Proof. $\alpha \mapsto \alpha\psi_t(\alpha, \lambda, s) = h_\alpha(s)$ is globally Lipschitz-continuous for each fixed $t, \lambda$, hence absolutely continuous. Moreover, $h_\alpha$ satisfies the equation

$$h_{\alpha}(s) = \int_{0}^{s} \alpha H(x, h_{\alpha}(x)) dx \text{ where } H(x, z) = \max(1 - f_{u}(t - x), 1 - \lambda + z)$$

and the initial condition $h_\alpha(0) = 0$. If $f_u(t - x) = 1$, the integrand is a.e. differentiable, with

$$\partial_{\alpha}[\alpha H(x, h_{\alpha}(x))] = \partial_{\alpha}[\alpha(1 - \lambda + h_{\alpha}(x))] = 1 - \lambda + h_{\alpha}(x) + \alpha \partial_{\alpha} h_{\alpha}(x).$$

Moreover, $h_\alpha$ increases strictly while $f_u(x) < 1$ which means that the number of solutions to $h_\alpha(x) = f_u(t - x)$ is finite (since $f_u$ is piecewise constant). At each point $s$ such that $h_\alpha(x) \neq f_u(t - x)$ and $h_\alpha$ is differentiable, the integrand is differentiable, with

$$\partial_{\alpha}[\alpha H(x, h_{\alpha}(x))] = H(x, h_{\alpha}(x)) + \alpha \partial_{\alpha} h_{\alpha}(x) \mathbb{I}\{h_{\alpha}(x) < f_u(t - x)\}.$$

As $H$ is 1-Lipschitz and $(\alpha, x) \mapsto h_\alpha(x)$ is Lipschitz, the integrand is a uniformly Lipschitz function of $\alpha$ over $x \in [0; s]$. Thus, one can differentiate under the integral sign, which yields

$$\partial_{\alpha} h_{\alpha}(s) = \int_{0}^{s} [H(x, h_{\alpha}(x)) + \alpha \partial_{\alpha} h_{\alpha}(x) \mathbb{I}\{h_{\alpha}(x) < f_{u}(t - x)\}] dx.$$

Thus, the function $r_\alpha : s \mapsto \partial_\alpha h_\alpha(s)$ is absolutely continuous and satisfies the differential equation

$$r'_{\alpha}(s) = H(s, h_{\alpha}(s)) + \alpha r_{\alpha}(s) \mathbb{I}\{h_{\alpha}(s) < f_{u}(t - s)\}$$

with initial condition $r_\alpha(0) = 0$. It follows that $r_\alpha$ is non-decreasing, hence non-negative on $\mathbb{R}_+$. Since

$$\lim_{s \to 0} H(s, h_{\alpha}(s)) = \max(1 - f_{u}(t), 1 - \lambda) \text{ and } \lim_{s \to 0} r_{\alpha}(s) = 0,$$

$r_\alpha$ is strictly increasing in a neighbourhood of 0, say $[0; \delta)$, if either $\lambda < 1$ or $f_u(t) < 1$. Since it is non-decreasing, it is then positive on $(0; t]$. $\square$

This yields the following corollary.

**Claim F.2.1.** The function $\alpha \mapsto \alpha y_{\min}(\alpha, t)$ is non-decreasing.

Proof. Fix two values of $\alpha, \alpha_0 \le \alpha_1$. Let $\lambda_0 = \alpha_0 y_{\min}(\alpha_0, t)$. By Definition 5.6, there are two possibilities.

* Case 1: Equation (38) fails below $y_{\min}(\alpha_0, t)$: for $\alpha = \alpha_0$ and all $y < y_{\min}(\alpha_0, t)$,

$$\psi_t(\alpha_0, \alpha_0 y, t) > y,$$

i.e for all $\alpha_0 y = \lambda < \lambda_0$,

$$\alpha_0 \psi_t(\alpha_0, \lambda, t) > \lambda.$$
By lemma F.2,

$$ \alpha_1 \psi_t(\alpha_1, \lambda, t) \geq \alpha_0 \psi_t(\alpha_0, \lambda, t) > \lambda $$

for all $\lambda < \lambda_0$ which implies by equation (38) that

$$ y_{\min}(\alpha_1, t) \geq \frac{\lambda_0}{\alpha_1}, \text{ i.e } \alpha_1 y_{\min}(\alpha_1, t) \geq \alpha_0 y_{\min}(\alpha_0, t). $$

* Case 2: Equation (39) fails below $y_{\min}(\alpha_0, t)$: for $\alpha = \alpha_0$ and all $\lambda < \lambda_0$, the set

$$ A_0(\lambda) = \{s \in [0; t] : 1 - \lambda + \alpha_0 \psi_t(\alpha_0, \lambda, s) > 1 - f_l(t - s)\} $$

has positive Lebesgue measure. Now, for any $\lambda < \lambda_0$ and $s \in A_0(\lambda)$, by lemma F.2,

$$ 1 - \lambda + \alpha_1 \psi_t(\alpha_1, \lambda, s) \geq 1 - \lambda + \alpha_0 \psi_t(\alpha_0, \lambda, s) > 1 - f_l(t - s) $$

so the set

$$ \{s \in [0; t] : 1 - \lambda + \alpha_1 \psi_t(\alpha_1, \lambda, s) > 1 - f_l(t - s)\} $$

contains $A_0(\lambda)$ and hence has positive Lebesgue measure. By equation (39), this proves that

$$ y_{\min}(\alpha_1, t) \geq \frac{\lambda_0}{\alpha_1}, \text{ i.e } \alpha_1 y_{\min}(\alpha_1, t) \geq \alpha_0 y_{\min}(\alpha_0, t). $$

In all cases,

$$ \alpha_1 \psi_t(\alpha_1, \lambda, t) \geq \alpha_0 \psi_t(\alpha_0, \lambda, t), $$

which proves the claim.

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

**Lemma F.3.** For any $t \geq 0$, the function $\alpha \mapsto y_{\min}(\alpha, t)$ is non-increasing. Moreover, for any $\delta \geq 0$ and $\alpha > 0$,

$$ |y_{\min}(\alpha, t) - y_{\min}(\alpha + \delta, t)| \leq \frac{\delta}{\alpha} y_{\min}(\alpha, t). $$

*Proof.* Let $\alpha_1 = \alpha + \delta \geq \alpha$ and $y = y_{\min}(\alpha, t)$. By definition 5.6 and since $\psi_t(\alpha, \alpha y, \cdot)$ is non-decreasing, for every $s \in [0; t]$,

$$ \alpha_1 (y - \psi_t(\alpha, \alpha y, s)) \geq \alpha (y - \psi_t(\alpha, \alpha y, s)) $$

By definition 5.2, for a.e $s \in [0; t]$,

$$ \begin{aligned} \frac{d}{ds} \psi_t(\alpha, \alpha y, s) &= \max(1 - f_u(t - s), 1 - \alpha y + \alpha \psi_t(\alpha, \alpha y, s)) \\ &\geq \max(1 - f_u(t - s), 1 - \alpha_1 y + \alpha_1 \psi_t(\alpha, \alpha y, s)). \end{aligned} $$
It follows by a comparison theorem that

$$ \psi_t(\alpha, \alpha y, \cdot) \geq \psi_t(\alpha_1, \alpha_1 y, \cdot). $$

In particular,

$$ \psi_t(\alpha_1, \alpha_1 y, t) \leq \psi_t(\alpha, \alpha y, t) \leq y $$

and for every $s \in [0; t]$,

$$ \begin{aligned} 1 - \alpha_1 y + \alpha_1 \psi_t(\alpha_1, \alpha_1 y, s) &\le 1 - \alpha_1 y + \alpha_1 \psi_t(\alpha, \alpha y, s) \\ &\le 1 - \alpha y + \alpha \psi_t(\alpha, \alpha y, s) \text{ by definition 5.6} \\ &\le 1 - f_l(t-s) \text{ by definition 5.6.} \end{aligned} $$

Thus, by definition 5.6, $y_{\min}(\alpha_1, t) \le y = y_{\min}(\alpha, t)$. Now, by claim F.2.1,

$$ (\alpha + \delta)y_{\min}(\alpha + \delta, t) \geq \alpha y_{\min}(\alpha, t) $$

and hence

$$ y_{\min}(\alpha + \delta, t) \geq \left(1 - \frac{\delta}{\alpha}\right) y_{\min}(\alpha, t) $$

which proves the result.

□

**Lemma F.4.** For any $\alpha > 0$, any $t \ge 0$ and $\delta \ge 0$,

$$ y_{\min}(\alpha, t + \delta) - y_{\min}(\alpha, t) \geq g_l(t + \delta) - g_l(t). $$

*Proof.* Let $y = y_{\min}(\alpha, t + \delta)$ and

$$ y_1 = y - \psi_{t+\delta}(\alpha, \alpha y, \delta). $$

Define the function $\phi : [0; t] \to \mathbb{R}$ by

$$ \phi(s) = \psi_{t+\delta}(\alpha, \alpha y, s + \delta) - \psi_{t+\delta}(\alpha, \alpha y, \delta). $$

Then $\phi(0) = 0$ and by definition 5.2, for almost every $s \in [0; t]$,

$$ \begin{aligned} \phi'(s) &= \max(1 - f_u(t + \delta - (s + \delta)), 1 - \alpha y + \alpha \psi_{t+\delta}(\alpha, \alpha y, s + \delta)) \\ &= \max(1 - f_u(t - s), 1 - \alpha y_1 + \alpha \psi_{t+\delta}(\alpha, \alpha y, s + \delta) - \alpha \psi_{t+\delta}(\alpha, \alpha y, \delta)) \\ &= \max(1 - f_u(t - s), 1 - \alpha y_1 + \alpha \phi(s)). \end{aligned} $$

By definition 5.2, it follows that $\phi = \psi_t(\alpha, \alpha y_1, \cdot)$. Now, by definition 5.6 applied to $y = y_{\min}(\alpha, t + \delta)$, for all $s \in [0; t]$,

$$ \begin{aligned} & \max(1 - f_u(t - s), 1 - \alpha y_1 + \alpha \psi_t(\alpha, \alpha y_1, s)) \\ &= \max(1 - f_u(t - s), 1 - \alpha y_1 + \alpha \phi(s)) \\ &= \max(1 - f_u(t + \delta - (s + \delta)), 1 - \alpha y + \alpha \psi_{t+\delta}(\alpha, \alpha y, s + \delta)) \\ &\le 1 - f_l(t + \delta - (s + \delta)) \\ &= 1 - f_l(t - s). \end{aligned} $$
Moreover,

$$ \psi_t(\alpha, \alpha y_1, t) = \phi(t) = \psi_{t+\delta}(\alpha, \alpha y, t+\delta) - \psi_{t+\delta}(\alpha, \alpha y, \delta) \leq y - \psi_{t+\delta}(\alpha, \alpha y, \delta) = y_1 $$

By definition 5.6, it follows that

$$ y_{\min}(\alpha, t) \leq y_1 = y_{\min}(\alpha, t + \delta) - \psi_{t+\delta}(\alpha, \alpha y, \delta). $$

To conclude, remark that by definition 5.2, for almost all $s \in [0; \delta]$,

$$ \frac{d}{ds} \psi_{t+\delta}(\alpha, \alpha y, s) \geq 1 - f_l(t + \delta - s) $$

and hence

$$ \psi_{t+\delta}(\alpha, \alpha y, \delta) \geq \int_{0}^{\delta} (1 - f_l(t + \delta - s)) ds = g_l(t + \delta) - g_l(t). $$

□

**Lemma F.5.** For any $\alpha, y$ and $s > 0$, the function

$$ t \mapsto \psi_t(\alpha, \alpha y, s) $$

is continuous on $(s; +\infty)$. Moreover, the function

$$ t \mapsto \psi_t(\alpha, \alpha y, t) $$

is also continuous.

*Proof.* Let $t \geq 0$ and $\delta \geq 0$. By definition 5.2, for a.e $s \in [0; t]$,

$$ \begin{aligned} \frac{d}{ds} \psi_{t+\delta}(\alpha, \alpha y, s) &= \max(1 - f_u(t + \delta - s)), 1 - \alpha y + \alpha \psi_{t+\delta}(\alpha, \alpha y, s)) \\ &\leq \max(1 - f_u(t - s)), 1 - \alpha y + \alpha \psi_{t+\delta}(\alpha, \alpha y, s)). \end{aligned} $$

Since $\psi_{t+\delta}(\alpha, \alpha y, 0) = 0$, it follows that

$$ \psi_{t+\delta}(\alpha, \alpha y, \cdot) \leq \psi_t(\alpha, \alpha y, \cdot) \text{ on } [0; t]. $$

Let

$$ h : s \mapsto \psi_t(\alpha, \alpha y, s - \delta) $$

on $[\delta, t + \delta]$. $h$ satisfies a.e the differential equation

$$ h'(s) = \max(1 - f_u(t + \delta - s), 1 - \alpha y + \alpha h(s)) $$

with initial condition $h(\delta) = 0 \leq \psi_{t+\delta}(\alpha, \alpha y, \delta)$. It follows that $h \leq \psi_{t+\delta}(\alpha, \alpha y, \cdot)$ on $[\delta, t + \delta]$. Thus, for any $s \in [0; t]$,

$$ |\psi_t(\alpha, \alpha y, s) - \psi_{t+\delta}(\alpha, \alpha y, s)| \leq \begin{cases} \psi_t(\alpha, \alpha y, \delta) & \text{if } s \leq \delta \\ \psi_t(\alpha, \alpha y, s) - \psi_t(\alpha, \alpha y, s - \delta) & \text{if } s \in [\delta; t]. \end{cases} $$
Clearly, $\psi_t(\alpha, \alpha y, \cdot)$ is continuous (in fact Lipschitz) on $[0; t]$ since it satisfies the differential equation of Definition (5.2). Thus, $t \mapsto \psi_t(\alpha, \alpha y, s)$ is continuous on $[s; +\infty)$. Now, consider the function $t \mapsto \psi_t(\alpha, \alpha y, t)$. We already proved that

$$ \psi_{t+\delta}(\alpha, \alpha y, t + \delta) \geq h(t + \delta) = \psi_t(\alpha, \alpha y, t) $$

so this function is non-decreasing. Fix some interval $[0; T]$ and let

$$ R = \psi_T(\alpha, \alpha y, T). $$

Moreover, we can extend each function to $\psi_t(\alpha, \alpha y, \cdot)$ to $\mathbb{R}_+$ using the natural definition $f_u(x) = 0$ for all $x < 0$. It follows from definition (5.2) that for every $t \le T$, $\psi_t(\alpha, \alpha y, \cdot)$ is Lipschitz-continuous on $[0; T]$ with constant

$$ L = \max(1, 1 - \alpha y + \alpha R). $$

Thus, if $t \le t + \delta \le T$,

$$ \psi_{t+\delta}(\alpha, \alpha y, t + \delta) \le \psi_{t+\delta}(\alpha, \alpha y, t) + L\delta \le \psi_t(\alpha, \alpha y, t) + L\delta $$

which shows the uniform continuity of $t \mapsto \psi_t(\alpha, \alpha y, t)$ on each compact interval of the form $[0; T]$. $\square$

**Lemma F.6.** Let $\alpha : \mathbb{R} \to \mathbb{R}_+$ be a continuous function and let $\tau$ be such that $\alpha(\tau) > 0$. The function

$$ t \mapsto y_{\min}(\alpha(t), t) $$

is left-continuous at $\tau$.

*Proof.* Let $\alpha_0 = \alpha(\tau)$. By claim F.4, $t \mapsto y_{\min}(\alpha_0, t)$ is non-decreasing, let $y$ be its left-limit at $\tau$. Fix a sequence $t_k \to \tau$ where $t_k < \tau$ for all $k$. Fix some $s \in (0; \tau]$. Since $y_k = y_{\max}(\alpha_0, t_k) \le y$, by definition 5.6, for any $\delta > 0$, there exists $s_1 \in (0; s) \cap (s - \delta, s)$ such that for all $k$ large enough, $\tau - t_k \le s - s_1$ and

$$ 1 - \alpha_0 y + \alpha_0 \psi_{t_k}(\alpha_0, \alpha_0 y, s_1) \le 1 - f_l(t_k - s_1) \le 1 - f_l(\tau - s). $$

Thus, by lemma F.5,

$$ 1 - \alpha_0 y + \alpha_0 \psi_{\tau}(\alpha_0, \alpha_0 y, s_1) \le 1 - f_l(\tau - s). $$

Since $s_1$ could be chosen arbitrarily close to $s$ and since $\psi(\alpha_0, \alpha_0 y, \cdot)$ is continuous by definition 5.2,

$$ 1 - \alpha_0 y + \alpha_0 \psi_{\tau}(\alpha_0, \alpha_0 y, s) \le 1 - f_l(\tau - s). $$

Moreover, $1 - f_u(t_k - \cdot) \le 1 - f_l(t_k - \cdot)$ a.e on $[0; t_k]$ i.e $f_l \le f_u$ a.e on $[0; t_k]$ for all $k$, which implies that $f_l \le f_u$ a.e on $[0; \tau]$. Thus, for a.e $s \in (0; \tau]$,

$$ \max(1 - f_u(\tau - s), 1 - \alpha_0 y + \alpha_0 \psi_{\tau}(\alpha_0, \alpha_0 y, s)) \le 1 - f_l(\tau - s). $$
Moreover, by lemma F.5,

$$ \lim_{k \to +\infty} \psi_{t_k}(\alpha_0, \alpha_0 y, t_k) = \psi_{\tau}(\alpha_0, \alpha_0 y, \tau) \le y. $$

Thus by definition 5.6, $y_{\min}(\alpha_0, \tau) \le y = \lim_{k \to +\infty} y_{\min}(\alpha_0, t_k)$. Since $y_{\min}$ is non-decreasing as a function of $t$, this proves that

$$ y = \lim_{k \to +\infty} y_{\min}(\alpha_0, t_k) = y_{\min}(\alpha_0, \tau). $$

Since $\alpha$ is continuous at $\tau$, $\alpha(t_k) \ge \alpha_0 - \delta > 0$ for $k$ large enough and so for all large enough $k$, by lemma F.3,

$$ \begin{aligned} |y_{\min}(\alpha(t_k), t_k) - y_{\min}(\alpha_0, t_k)| &\le \frac{|\alpha(t_k) - \alpha_0|}{\min(\alpha(t_k), \alpha_0)} y_{\min}(\alpha_0 - \delta, t_k) \\ &\le \frac{|\alpha(t_k) - \alpha_0|}{\alpha_0 - \delta} y_{\min}(\alpha_0 - \delta, \tau) \\ &\to 0. \end{aligned} $$

It follows that

$$ \begin{aligned} \limsup_{k \to +\infty} |y_{\min}(\alpha(t_k), t_k) - y_{\min}(\alpha(\tau), \tau)| &\le \limsup_{k \to +\infty} \{|y_{\min}(\alpha(t_k), t_k) - y_{\min}(\alpha(\tau), t_k)|\} \\ &\quad + \limsup_{k \to +\infty} \{|y_{\min}(\alpha(\tau), t_k) - y_{\min}(\alpha(\tau), \tau)|\} \\ &= 0 \end{aligned} $$

which proves the left-continuity of $t \mapsto y_{\min}(\alpha(t), t)$ at $\tau$. $\square$

Finally, let us recall lemma 5.7 and give a proof.

**Lemma F.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). $$

*Proof.* By claim 5.7.1 with $f = f_l$, $\alpha = \hat{\alpha}_t$ and $y = g_u(t)$, it follows that $g_u(t) \ge y_{\min}(\hat{\alpha}_t, t)$.

Consider now the lower bound. Let $\alpha = \hat{\alpha}_t$ and $y = y_{\min}(\alpha, t)$. By Definition (5.2), $\psi_t(\alpha, \alpha y, 0) = 0$ and for almost all $s \in [0; t]$,

$$ \frac{d}{ds} \psi_t(\alpha, \alpha y, s) \ge 1 - \alpha y + \alpha \psi_t(\alpha, \alpha y, s). $$

Since $h: s \mapsto (\frac{1}{\alpha} - y)(e^{\alpha s} - 1)$ solves the initial value problem

$$ h(0) = 0 \text{ and } h'(s) = 1 - \alpha y + \alpha h(s), $$

it follows that $\psi_t(\alpha, \alpha y, \cdot) \ge h$ on $[0; t]$. Thus, by definition 5.6 of $y = y_{\min}(\alpha, t)$,

$$ \left(\frac{1}{\alpha} - y\right) (e^{\alpha t} - 1) = h(t) \le \psi_t(\alpha, \alpha y, t) \le y $$
which yields

$$y \geq \frac{1}{\alpha} (1 - e^{-\alpha t}) \geq (1 - e^{-1}) \min \left( \frac{1}{\alpha}, t \right). \quad \square$$

## F.5 Properties of the functions $\hat{\alpha}_{\tau}^{+}$ and $\hat{\alpha}_{+}$

**Claim F.7.1.** For all $t \leq \tau$, the function

$$\alpha \mapsto \frac{1}{\alpha} \hat{\alpha}_{\tau}^{+}(t, y_{\min}(\alpha, t))$$

is non-increasing on $(0; +\infty)$.

*Proof.* By definition,

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

Each of the functions in the above supremum is a non-increasing function of $\alpha$, by claim F.2. $\square$

We need the following lemmas.

**Lemma F.8.** The function $\hat{\alpha}_{+}$ is non-decreasing.

*Proof.* Rewrite $\alpha_{+}$ as

$$\hat{\alpha}_{+} : t \mapsto \sup_{s>0} \left\{ \frac{f_u(s)}{\frac{T}{n} + (g_l(s) - g_l(t))_+} \right\}$$

and observe that each term in the supremum is a non-decreasing function of $t$. $\square$

**Lemma F.9.** For any $\alpha \geq 0$, the function

$$t \mapsto \hat{\alpha}_{\infty}^{+}(t, y_{\min}(\alpha, t))$$

is non-increasing.

*Proof.* Fix some $t \geq 0$ and $\delta \geq 0$. By lemma F.4,

$$y_{\min}(\alpha, t + \delta) - g_l(t + \delta) \geq y_{\min}(\alpha, t) - g_l(t)$$

and hence

$$\begin{align*}
\hat{\alpha}_{\infty}^{+}(t + \delta, y_{\min}(\alpha, t + \delta)) &= \sup_{s \ge t + \delta} \left\{ \frac{f_u(s)}{y_{\min}(\alpha, t + \delta) + g_l(s) - g_l(t + \delta)} \right\} \\
&\le \sup_{s \ge t + \delta} \left\{ \frac{f_u(s)}{y_{\min}(\alpha, t) + g_l(s) - g_l(t)} \right\} \\
&\le \sup_{s \ge t} \left\{ \frac{f_u(s)}{y_{\min}(\alpha, t) + g_l(s) - g_l(t)} \right\} \\
&= \hat{\alpha}_{\infty}^{+}(t, y_{\min}(\alpha, t)).
\end{align*} \quad \square$$
## F.6 Proof of Proposition 5.8

We are now ready to prove the proposition. Let $f \in [f_l; f_u]$ and define

$$ \alpha = \sup_{s<t} \frac{f(s)}{g(s)} \text{ where } g(s) = \int_{0}^{s} (1-f(x))dx. $$

Since $f \ge f_l$, $\alpha \ge \hat{\alpha}_t^-$ by equation (37) defining $\hat{\alpha}_t^-$. By claim 5.7.1, $g(t) \ge y_{\min}(\alpha, t)$. Now, for any $s \in [t; \tau]$, since $f \le f_u$,

$$ \begin{aligned} \frac{f(s)}{g(s)} &= \frac{f(s)}{g(t) + \int_{t}^{s} (1-f(x))dx} \\ &\le \frac{f_u(s)}{g(t) + \int_{t}^{s} (1-f_u(x))dx} \\ &= \frac{f_u(s)}{g(t) + g_l(s) - g_l(t)} \\ &\le \hat{\alpha}_{\tau}^{+}(t, g(t)) \text{ by definition (36).} \end{aligned} $$

$\hat{\alpha}_{\tau}^{+}(t, y)$ defined in equation (36) is obviously a non-increasing function of $y$, so

$$ \sup_{s \in [t; \tau]} \frac{f(s)}{g(s)} \le \hat{\alpha}_{\tau}^{+}(t, g(t)) \le \hat{\alpha}_{\tau}^{+}(t, y_{\min}(\alpha, t)). $$

Thus, by claim F.7.1,

$$ \begin{aligned} \sup_{s \in [t; \tau]} \frac{f(s)}{g(s)} &\le \frac{\hat{\alpha}_{\tau}^{+}(t, y_{\min}(\alpha, t))}{\alpha} \alpha \\ &\le \frac{\hat{\alpha}_{\tau}^{+}(t, y_{\min}(\hat{\alpha}_{t}^{-}, t))}{\hat{\alpha}_{t}^{-}} \alpha \\ &= \hat{\rho}_{\tau}(t) \sup_{s \in [t; \tau]} \frac{f(s)}{g(s)}. \end{aligned} $$

This proves equation (36) with $\rho = \hat{\rho}_{\tau}(t)$. Now, let us prove that it is the least such $\rho$ by constructing some $f \in [f_l; f_u]$ such that

$$ \sup_{s \in [t; \tau]} \frac{f(s)}{g(s)} = \hat{\rho}_{\tau}(t) \sup_{s<t} \frac{f(s)}{g(s)}. $$

By claim 5.7.1, there exists some $f_0 \in [f_l; f_u]$ such that

$$ \sup_{s<t} \frac{f_0(s)}{g_0(s)} = \hat{\alpha}_t^- \text{ and } g_0(t) = y_{\min}(\hat{\alpha}_t^-, t), $$

where

$$ g_0(s) = \int_{0}^{s} (1 - f_0(x))dx. $$
Let

$$f : s \mapsto \begin{cases} f_0(s) & \text{if } s < t \\ f_u(s) & \text{if } s \ge t. \end{cases} \qquad (93)$$

and

$$g : s \mapsto \int_{0}^{s} (1 - f(x)) dx.$$

Then for all $s \le t$, $g(s) = g_0(s)$ hence

$$\sup_{s<t} \frac{f(s)}{g(s)} = \hat{\alpha}_t^{-}.$$

Moreover,

$$\begin{aligned} \sup_{s \in [t; \tau]} \frac{f(s)}{g(s)} &= \sup_{s \in [t; \tau]} \frac{f_u(s)}{g(t) + \int_{t}^{s} (1 - f_u(x)) dx} \\ &= \hat{\alpha}_{\tau}^{+}(t, g(t)) \\ &= \hat{\alpha}_{\tau}^{+}(t, g_0(t)) \\ &= \hat{\alpha}_{\tau}^{+}(t, y_{\min}(\hat{\alpha}_{t}^{-}, t)) \\ &= \hat{\rho}_{\tau}(t) \hat{\alpha}_{t}^{-} \end{aligned}$$

which proves the minimality of $\hat{\rho}_{\tau}(t)$.

## F.7 Proof of Proposition 5.9

Let $t_0 \in (0; \tau]$ and $f \in [f_l; f_u]$ be such that

$$\frac{f(t_0)}{g(t_0)} \ge \frac{1}{1+\delta} \sup_{s \in (0; \tau]} \left\{ \frac{f(s)}{g(s)} \right\}$$

where $g : s \mapsto \int_{0}^{s} (1 - f(x)) dx$. By definition, either $\hat{t}_U = \tau \ge t_0$ or $(1+\delta)\hat{\rho}_{\tau}(\hat{t}_U) < \delta$ 1 which implies by correctness of $<_{\delta}$ and Proposition 5.8 that

$$\sup_{t \in [\hat{t}_U; \tau]} \left\{ \frac{f(s)}{g(s)} \right\} < \frac{1}{1+\delta} \sup_{t < \hat{t}_U} \left\{ \frac{f(s)}{g(s)} \right\}$$

and hence that $t_0 \le \hat{t}_U$. Now, by definition of algorithm 5.2, $\neg((1+\delta)\hat{t}_L <_{\delta} \hat{t}_U)$ upon terminating, which means that $\hat{t}_U \le (1+\delta)^2 \hat{t}_L$. It follows by definition of $\hat{\tau}_{\delta}$ that

$$\hat{\tau}_{\delta} \ge \hat{t}_{U} \ge t_{0}.$$

In particular, $\hat{\tau}_{\max}(\tau) \le \hat{t}_U$.

Consider now the second claim. By proposition 5.8, there exists $f \in [f_l; f_u]$, $g : t \mapsto \int_{0}^{t} (1 - f(s)) ds$ such that

$$\sup_{s \in [\hat{t}_L; \tau]} \left\{ \frac{f(s)}{g(s)} \right\} = \hat{\rho}_{\tau}(\hat{t}_L) \sup_{s < \hat{t}_L} \left\{ \frac{f(s)}{g(s)} \right\}. \qquad (94)$$
We can assume without loss of generality that $f = f_u$ on $[\hat{t}_L; \tau]$, as this can only increase the left-hand side while leaving the right-hand side unchanged. By definition of $\hat{\tau}_\delta$ and by concavity of $g$,

$$ 
\begin{aligned}
\frac{f(\hat{\tau}_\delta)}{g(\hat{\tau}_\delta)} &= \frac{f_u(\hat{\tau}_\delta)}{g(\hat{t}_L) + g_l(\hat{\tau}_\delta) - g_l(\hat{t}_L)} \\
&\geq \frac{1}{(1+\delta)^2} \sup_{t \in [\hat{t}_L; \tau]} \left\{ \frac{f_u(t)}{g(\hat{t}_L) + g_l(t) - g_l(\hat{t}_L)} \right\} \\
&= \frac{1}{(1+\delta)^2} \sup_{t \in [\hat{t}_L; \tau]} \left\{ \frac{f(t)}{g(t)} \right\} \\
&\geq \frac{\min(1, \hat{\rho}_\tau(\hat{t}_L))}{(1+\delta)^2} \sup_{t \in [0; \tau]} \left\{ \frac{f(t)}{g(t)} \right\}.
\end{aligned}
$$

By construction, $\hat{t}_L$ is such that $\neg ((1+\delta)\hat{\rho}_\tau(\hat{t}_L) <_\delta 1)$ which implies that $\hat{\rho}_\tau(\hat{t}_L) \geq \frac{1}{(1+\delta)^2}$. This finally yields

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

as claimed.

## F.8 Proof of Proposition 5.12

First, remark that the function

$$ \hat{\alpha}_\infty^+(t, y) = \sup_{s \geq t} \left\{ \frac{f_u(s)}{y + g_l(s) - g_l(t)} \right\} $$

is a decreasing function of $y$. Hence, $y_{\min}(\hat{\alpha}_+(t), t) \leq \frac{T}{n}$ if and only if

$$ h(t) = \frac{1}{\hat{\alpha}_+(t)} \hat{\alpha}_\infty^+ (t, y_{\min}(\hat{\alpha}_+(t), t)) \geq 1. $$

Next, let us show that $h$ is non-increasing. Let $t, \delta$ be non-negative. By lemma F.9,

$$ h(t+\delta) = \frac{1}{\hat{\alpha}_+(t+\delta)} \hat{\alpha}_\infty^+ (t+\delta, y_{\min}(\hat{\alpha}_+(t+\delta), t+\delta)) \leq \frac{1}{\hat{\alpha}_+(t+\delta)} \hat{\alpha}_\infty^+ (t, y_{\min}(\hat{\alpha}_+(t+\delta), t)). $$

By lemma F.8, $\hat{\alpha}_+(t+\delta) \geq \hat{\alpha}_+(t)$, hence by claim F.7.1,

$$ h(t+\delta) \leq \frac{1}{\hat{\alpha}_+(t)} \hat{\alpha}_\infty^+ (t, y_{\min}(\hat{\alpha}_+(t), t)) = h(t) $$

which proves that $h$ is non-increasing. It follows that the set

$$ \left\{ t > 0 : y_{\min}(\hat{\alpha}_+(t), t) \leq \frac{T}{n} \right\} = \left\{ t : h(t) \geq 1 \right\} = I $$
is an interval containing 0. Moreover, since $\hat{\alpha}_+$ is a continuous and positive function (by equation 36), lemma F.6 implies that $I$ is right-closed. Thus, either $I = [0; t_*]$ for some real $t_*$ or $I = [0; +\infty)$ (in which case we set $t_* = +\infty$). To prove the last claim, assume that $t_* \ge T$ and that $f_u = 1$ on $[T; +\infty)$. For any $t \ge T$,

$$ \hat{\alpha}_+(t) = \sup_{s \ge t} \left\{ \frac{f_u(s)}{\frac{T}{n} + g_l(s) - g_l(t)} \right\} = \sup_{s \ge t} \left\{ \frac{1}{\frac{T}{n} + 0} \right\} = \frac{n}{T}. $$

Let $\alpha = \frac{n}{T}$ and $y = \frac{T}{n}$. Fix some $t \ge T$ and let

$$ h : s \mapsto \begin{cases} 0 & \text{if } s < t - T \\ \psi_T(\alpha, \alpha y, s - t + T) & \text{if } s \in [t - T; t]. \end{cases} $$

Then for all $s < t - T$,

$$ h'(s) = 0 = \max(0, 1 - \alpha y + \alpha h(s)) = \max(1 - f_u(t - s), 1 - \alpha y + \alpha h(s)) $$

and for all $s \in [t - T; t]$,

$$ \begin{aligned} h'(s) &= \max(1 - f_u(T - (s - t + T)), 1 - \alpha y + \alpha \psi_T(\alpha, \alpha y, s - t + T)) \\ &= \max(1 - f_u(t - s), 1 - \alpha y + \alpha h(s)). \end{aligned} $$

It follows that $h$ solves the initial value problem defining $\psi_t(\alpha, \alpha y, \cdot)$. Hence, $h = \psi_t(\alpha, \alpha y, \cdot)$. Moreover, since $t_* \ge T$, $y \ge y_{\min}(\alpha, t)$ and

$$ \psi_t(\alpha, \alpha y, t) = h(t) = \psi_T(\alpha, \alpha y, T) \le y $$

as well as

$$ 1 - \alpha y + \alpha \psi_t(\alpha, \alpha y, s) = 1 - \alpha y + \alpha \psi_T(\alpha, \alpha y, s - t + T) \le 1 - f_l(T - (s - t + T)) = 1 - f_l(t - s) $$

for a.e $s \in [t - T; T]$. For all $s \in [0; t - T]$,

$$ 1 - \alpha y + \alpha \psi_t(\alpha, \alpha y, s) = 1 - \alpha y + \alpha h(s) = 1 - \alpha y = 0 \le 1 - f_l(t - s). $$

It follows by definition 5.6 that

$$ y_{\min}(\hat{\alpha}_+(t), t) = y_{\min}(\alpha, t) \le y = \frac{T}{n}. $$

This implies by definition that $t_* \ge t$. Since this is true for any $t \ge T$, $t_* = +\infty$.
## F.9 Proof of Proposition 5.13

Assume first that $\mathbb{H}$ is non-empty. Choose some $(f,g) \in \mathbb{H}$. Let $t_0$ be such that $g(t_0) = \frac{T}{n}$. By definition of $\mathbb{H}$,

$$ 
\begin{aligned}
\sup_{t>0} \left\{ \frac{f(t)}{g(t)} \right\} &= \sup_{t:g(t) \ge \frac{T}{n}} \left\{ \frac{f(t)}{g(t)} \right\} \\
&= \sup_{t \ge t_0} \left\{ \frac{f(t)}{\frac{T}{n} + \int_{t_0}^t (1-f(s))ds} \right\} \\
&\le \sup_{t \ge t_0} \left\{ \frac{f_u(t)}{\frac{T}{n} + \int_{t_0}^t (1-f_u(s))ds} \right\} \\
&= \hat{\alpha}_+(t_0).
\end{aligned}
$$

It follows from claim 5.7.1 that $g(t_0) \ge y_{\min}(\hat{\alpha}_+(t_0), t_0)$, hence $t_0 \le t_*$ by proposition 5.12. Thus,

$$ g(t_*) \ge g(t_0) = \frac{T}{n} $$

and since $\hat{\alpha}_+$ is non-decreasing by lemma F.8,

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

Moreover, since $(f,g) \in \mathbb{H}$ was arbitrary, it follows that

$$ \hat{\alpha}_u \le \hat{\alpha}_+(t_*) $$

Assume now that $\hat{\alpha}_+(t_*) \ge \hat{\alpha}_-$ and $g_u(t_*) \ge \frac{T}{n}$. By proposition 5.12 defining $t_*$,

$$ y_{\min}(\hat{\alpha}_+(t_*), t_*) \le \frac{T}{n}. $$

It follows by claim 5.7.1 that there exists some $f_0 \in [f_l; f_u]$ and $g_0 : t \mapsto \int_0^t (1 - f_0(s))ds$ such that

$$ \sup_{s<t_*} \left\{ \frac{f_0(s)}{g_0(s)} \right\} \le \hat{\alpha}_+(t_*) \text{ and } g_0(t_*) = \frac{T}{n}. $$

Let then

$$ f : t \mapsto \begin{cases} f_0(t) & \text{if } t < t_* \\ f_u(t) & \text{if } t \ge t_* \end{cases}. \qquad (95) $$
Let $g: t \mapsto \int_{0}^{t}(1 - f(s))ds$, thus $g = g_0$ on $[0; t_*]$. It follows that

$$
\begin{align*}
\sup_{s<t_*} \left\{ \frac{f(s)}{g(s)} \right\} &\le \hat{\alpha}_+(t_*) \\
&= \sup_{t \ge t_*} \left\{ \frac{f_u(t)}{\frac{T}{n} + g_l(t) - g_l(t_*)} \right\} \\
&= \sup_{t \ge t_*} \left\{ \frac{f(t)}{g(t)} \right\}.
\end{align*}
$$

Since $g(t_*) = g_0(t_*) = \frac{T}{n}$, this proves that

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

and hence that $(f, g) \in \mathbb{H}$. In particular, $\mathbb{H}$ is non-empty and

$$
\hat{\alpha}_u \geq \sup_{t>0} \left\{ \frac{f(t)}{g(t)} \right\} = \hat{\alpha}_+(t_*).
$$

F.10 Proof of proposition 5.15

Assume that $\mathbb{H}$ is not empty. By construction, $\hat{t}_U = T$ or $y_{\min}(\hat{\alpha}_+(\hat{t}_U), \hat{t}_U) > \frac{T}{n}$,
which implies by proposition 5.12 that $\hat{t}_U \ge t_*$. Thus, if $t_* \in [0; T]$, then $\hat{t}_U \ge t_*$. 
By proposition 5.13 and lemma F.8, it follows that

$$
g_u(\hat{t}_U) \geq g_u(t_*) \geq \frac{T}{n} \quad \text{and} \quad \hat{\alpha}_{u,\delta} = \hat{\alpha}_+(\hat{t}_U) \geq \hat{\alpha}_+(t_*) \geq \hat{\alpha}_-.
$$

Thus, Algorithm 5.3 does not return an error in this case. Now, if $t_* > T$, then $y_{\min}(\hat{\alpha}_+(T), T) \le \frac{T}{n}$ and hence $\hat{t}_U = T$. Since $f_u$ is constant equal to 1 on $[T; +\infty)$, $g_l$ is constant on that interval and so is $\hat{\alpha}_+$ (with value $\frac{n}{T}$). Thus,

$$
\hat{\alpha}_{u,\delta} = \hat{\alpha}_+(\hat{t}_U) = \hat{\alpha}_+(t_*) \ge \hat{\alpha}_-
$$

and moreover,

$$
\lim_{t \to +\infty} g_u(t) \geq g_u(t_*) \geq \frac{T}{n}.
$$

Thus, Algorithm 5.3 does not throw an exception if $\mathbb{H} \neq \emptyset$. Moreover, we have shown that $\hat{\alpha}_{u,\delta} \ge \hat{\alpha}_+(t_*) = \hat{\alpha}_u$, as claimed.

Assume now that $t_* \in [0; T]$ and that algorithm 5.3 terminates without returning an error. If $t_* \ge T$, we have shown that $\hat{t}_U = T$, thus $\hat{\tau}_\delta \ge T$. Consider now the case $t_* \in [0; T]$. Since no exception is thrown,

$$
(1 + \delta)\hat{\alpha}_+(\hat{t}_U) \geq \hat{\alpha}_- \quad \text{and} \quad (1 + \delta)g_u(\hat{t}_U) \geq \frac{T}{n}. \qquad (96)
$$

Either $\hat{t}_U = T \ge t_*$ or

$$
y_{\min}(\hat{\alpha}_{+}(\hat{t}_{U}), \hat{t}_{U}) < \frac{T}{n}
$$
which implies by proposition 5.12 that $\hat{t}_U > t_*$. Thus, $\hat{t}_U \ge t_*$ in all cases and it follows by lemma F.8 and proposition 5.13 that

$$ \hat{\alpha}_{u,\delta} = \hat{\alpha}_{+}(\hat{t}_{U}) \geq \hat{\alpha}_{+}(t_{*}). $$

Let us now consider the properties of $\hat{\tau}_{\delta}$. Let

$$ \hat{t} = \begin{cases} \hat{t}_L & \text{if } \frac{T}{n} < \hat{\delta} y_{\min}(\hat{\alpha}_+(T), T) \\ T & \text{else.} \end{cases} $$

Let also

$$ \alpha = \max(\hat{\alpha}_{-}, \hat{\alpha}_{+}(\hat{t}_{L})). $$

If $\hat{t} = T$ or if $\hat{t}_L$ gets assigned a new value during the running of the while loop, then by construction

$$ \neg \left( \frac{T}{n} < \hat{\delta} y_{\min}(\hat{\alpha}_{+}(\hat{t}), \hat{t}) \right) \text{ so } y_{\min}(\hat{\alpha}_{+}(\hat{t}), \hat{t}) \leq (1 + \delta) \frac{T}{n}. $$

Since $\alpha \ge \hat{\alpha}_+$, and since $y_{\min}$ is a non-increasing function of $\alpha$ by lemma F.3,

$$ y_{\min}(\alpha, \hat{t}) \le (1 + \delta) \frac{T}{n}. $$

The other case is that $\hat{t} = \hat{t}_L = \frac{T}{n}$. Now, since by definition of $\alpha$,

$$ \sup_{s < \hat{t}} \left\{ \frac{f_l(s)}{g_u(s)} \right\} \le \hat{\alpha}_{-} \le \alpha, $$

it follows by claim 5.7.1 that in both cases

$$ y_{\min}(\alpha, \hat{t}) \leq g_u(\hat{t}). $$

In particular, if $\hat{t} = \frac{T}{n}$, then

$$ y_{\min}(\alpha, \hat{t}) \leq g_u \left( \frac{T}{n} \right) \leq \frac{T}{n}. $$

Thus, in all cases,

$$ y_{\min}(\alpha, \hat{t}) \le y = \min \left( (1 + \delta) \frac{T}{n}, g_u(\hat{t}) \right). \quad (97) $$

By claim 5.7.1, there exists $f_0 \in [f_l; f_u]$ such that

$$ \sup_{s < \hat{t}} \left\{ \frac{f_0(s)}{g_0(s)} \right\} \le \alpha \text{ and } g_0(\hat{t}) = y, $$

where as usual, $g_0 : t \mapsto \int_0^t (1 - f_0(s))ds$. Let

$$ f : t \mapsto \begin{cases} f_0(t) & \text{if } t < \hat{t} \\ f_u(t) & \text{if } t \ge \hat{t}. \end{cases} \quad (98) $$
Thus, $f \in [f_l; f_u]$. Let $g: t \mapsto \int_0^t (1-f(s))ds$. Since $f = f_0$ on $[0; \hat{t})$, $g_0 = g$ on this interval and

$$ \sup_{s<\hat{t}} \left\{ \frac{f(s)}{g(s)} \right\} \leq \alpha = \max(\hat{\alpha}_+(\hat{t}), \hat{\alpha}_-) . $$

By equation (96) and since $\hat{t}_U \leq (1+\delta)^2\hat{t}_L \leq (1+\delta)^2\hat{t}$,

$$ y = \min \left( (1+\delta) \frac{T}{n}, g_u(\hat{t}) \right) \geq \min \left( \frac{T}{n}, \frac{g_u(\hat{t}_U)}{(1+\delta)^2} \right) \geq \frac{T}{(1+\delta)^3 n} \quad (99) $$

which implies in particular that

$$ g(\hat{\tau}_{\delta}) \geq g(\hat{t}_{U}) \geq g(\hat{t}) = y \geq \frac{T}{(1+\delta)^3 n}. \quad (100) $$

If $\hat{t} = T$, then $\hat{\tau}_{\delta} = \hat{t}_U = T$ and

$$ \frac{f(\hat{\tau}_{\delta})}{g(\hat{\tau}_{\delta})} = \frac{f_u(T)}{g(T)} = \frac{1}{y} \geq \frac{n}{T(1+\delta)} = \frac{1}{1+\delta} \hat{\alpha}_+(T) \geq \frac{\hat{\alpha}_{u,\delta}}{1+\delta}. $$

For all $s \geq \hat{\tau}_{\delta} = T$,

$$ \frac{f(s)}{g(s)} = \frac{1}{g(s)} \leq \frac{1}{g(\hat{\tau}_{\delta})} = \frac{f(\hat{\tau}_{\delta})}{g(\hat{\tau}_{\delta})} $$

while for $s < T = \hat{t}$,

$$ \frac{f(s)}{g(s)} \leq \alpha = \max(\hat{\alpha}_-, \hat{\alpha}_+(\hat{t})) . $$

Since Algorithm 5.3 does not return an error,

$$ \alpha = \max(\hat{\alpha}_-, \hat{\alpha}_+(\hat{t}_U)) \leq \max((1+\delta)\hat{\alpha}_+(\hat{t}_U), \hat{\alpha}_+(\hat{t}_U)) \leq (1+\delta)\hat{\alpha}_{u,\delta} $$

which completes the proof of equation (42) in the case $\hat{t} = T$.

Consider now the case $\hat{t} = \hat{t}_L < T$. Then

$$ \hat{\tau}_{\delta} = (1 + \delta)\tau_{id}(\hat{t}_U) \geq \hat{t}_U \geq \hat{t}_L $$

(by definition 5.11), so

$$ \begin{aligned} \frac{f(\hat{\tau}_{\delta})}{g(\hat{\tau}_{\delta})} &\geq \frac{\tilde{f}_u(\tau_{id}(\hat{t}_U))}{g((1+\delta)\tau_{id}(\hat{t}_U))} \\ &\geq \frac{1}{1+\delta} \frac{\tilde{f}_u(\tau_{id}(\hat{t}_U))}{g(\tau_{id}(\hat{t}_U))} \\ &= \frac{1}{1+\delta} \frac{\tilde{f}_u(\tau_{id}(\hat{t}_U))}{y + g_l(\tau_{id}(\hat{t}_U)) - g_l(\hat{t}_L)}. \end{aligned} $$
Now, by the termination condition, we have that $\neg((1 + \delta)\hat{t}_L <_\delta \hat{t}_U)$ which implies that $\hat{t}_U \le (1 + \delta)^2\hat{t}_L$ and hence that

$$ \frac{g_l(\hat{t}_U)}{g_l(\hat{t}_L)} \le \frac{\hat{t}_U}{\hat{t}_L} \le (1 + \delta)^2 $$

which yields

$$ g_l(\hat{t}_U) - g_l(\hat{t}_L) \le (2\delta + \delta^2)g_l(\hat{t}_L) \le (2\delta + \delta^2)g(\hat{t}_L) = (2\delta + \delta^2)y. $$

It follows that

$$ \begin{aligned} \frac{f(\hat{\tau}_{\delta})}{g(\hat{\tau}_{\delta})} &\ge \frac{1}{1+\delta} \frac{\tilde{f}_u(\tau_{id}(\hat{t}_U))}{(1+2\delta+\delta^2)y + g_l(\tau_{id}(\hat{t}_U)) - g_l(\hat{t}_U)} \\ &\ge \frac{1}{(1+\delta)^3} \frac{\tilde{f}_u(\tau_{id}(\hat{t}_U))}{y + g_l(\tau_{id}(\hat{t}_U)) - g_l(\hat{t}_U)} \\ &\ge \frac{1}{(1+\delta)^4} \frac{\tilde{f}_u(\tau_{id}(\hat{t}_U))}{\frac{T}{n} + g_l(\tau_{id}(\hat{t}_U)) - g_l(\hat{t}_U)} \\ &= \frac{\hat{\alpha}_+(\hat{t}_U)}{(1+\delta)^4} \\ &= \frac{\hat{\alpha}_{u,\delta}}{(1+\delta)^4} \end{aligned} $$

Now, by equation (96) and lemma F.8,

$$ \sup_{s<\hat{t}_L} \left\{ \frac{f(s)}{g(s)} \right\} \le \alpha = \max(\hat{\alpha}_-, \hat{\alpha}_+(\hat{t}_L)) \le (1+\delta)\hat{\alpha}_{u,\delta}. $$

Moreover, by definition 5.11

$$ \begin{aligned} \sup_{s \ge \hat{t}_L} \left\{ \frac{f(s)}{g(s)} \right\} &= \sup_{s \ge \hat{t}_L} \left\{ \frac{f_u(s)}{y + g_l(s) - g_l(\hat{t}_L)} \right\} \\ &\le \frac{T}{ny} \hat{\alpha}_+(\hat{t}_L) \\ &\le \frac{T}{ny} \hat{\alpha}_+(\hat{t}_U) \text{ by lemma F.8} \\ &\le (1+\delta)^3 \hat{\alpha}_{u,\delta} \text{ by equation (99).} \end{aligned} $$

This finally yields

$$ \sup_{s>0} \left\{ \frac{f(s)}{g(s)} \right\} \le (1+\delta)^3 \hat{\alpha}_{u,\delta} \le (1+\delta)^7 \frac{f(\hat{\tau}_{\delta})}{g(\hat{\tau}_{\delta})}, $$

completing the proof of equation (42) in the case $\hat{t} = \hat{t}_L$.
References

[1] Shipra Agrawal and Nikhil R. Devanur. Bandits with concave rewards and convex knapsacks. In *Proceedings of the Fifteenth ACM Conference on Economics and Computation*, EC '14, page 989-1006, New York, NY, USA, 2014. Association for Computing Machinery.

[2] Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knapsacks. In *2013 IEEE 54th Annual Symposium on Foundations of Computer Science*, page 207-216. IEEE, October 2013.

[3] R. R. Bahadur and Leonard J. Savage. The Nonexistence of Certain Statistical Procedures in Nonparametric Problems. *The Annals of Mathematical Statistics*, 27(4):1115–1122, 1956.

[4] Robert H. Berk and Douglas H. Jones. Goodness-of-fit test statistics that dominate the kolmogorov statistics. *Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete*, 47(1):47–59, Jan 1979.

[5] Sebastien Bubeck, Nicolo Cesa-Bianchi, and Gabor Lugosi. Bandits with heavy tail. 59(11):7711-7717, November 2013.

[6] Sébastien Bubeck. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. *Foundations and Trends in Machine Learning*, 5(1):1-122, 2012.

[7] Semih Cayci, Atilla Eryilmaz, and R. Srikant. Learning to control renewal processes with bandit feedback. *SIGMETRICS Perform. Eval. Rev.*, 47(1):41-42, December 2019.

[8] Semih Cayci, Atilla Eryilmaz, and Rayadurgam Srikant. Continuous-time multi-armed bandits with controlled restarts. *ArXiv*, abs/2007.00081, 2020.

[9] Semih Cayci, Swati Gupta, and Atilla Eryilmaz. Group-fair online allocation in continuous time. NIPS '20, Red Hook, NY, USA, 2020. Curran Associates Inc.

[10] Iddo Eliazar, Tal Koren, and Joseph Klafter. Searching circular dna strands. *Journal of Physics: Condensed Matter*, 19(6):065140, jan 2007.

[11] Matteo Gagliolo and Jürgen Schmidhuber. Learning restart strategies. In *International Joint Conference on Artificial Intelligence*, 2007.

[12] Carla P. Gomes, Bart Selman, and Henry Kautz. Boosting combinatorial search through randomization. In *Proceedings of the Fifteenth National/Tenth Conference on Artificial Intelligence/Innovative Applications of Artificial Intelligence*, AAAI '98/IAAI '98, page 431-437, USA, 1998. American Association for Artificial Intelligence.
[13] Veronika Gontscharuk and Helmut Finner. Asymptotics of goodness-of-fit tests based on minimum p-value statistics. *Communications in Statistics - Theory and Methods*, 46(5):2332–2342, 2017.

[14] Veronika Gontscharuk and Helmut Finner. On the asymptotics of a normal beta-transformed empirical process. *Journal of Statistical Planning and Inference*, 193:103–108, 2018.

[15] Jack K Hale. *Ordinary differential equations*. Courier Corporation, 2009.

[16] Alexander Henzi and Lutz Dümbgen. Some new inequalities for beta distributions. *Statistics and Probability Letters*, 195:109783, 2023.

[17] Lukasz Kusmierz, Satya Majumdar, Sanjib Sabhapandit, and Gregory Schehr. First order transition for the optimal search time of lévy flights with resetting. *Physical review letters*, 113, 09 2014.

[18] Qingsong Liu and Zhixuan Fang. Learning to schedule tasks with deadline and throughput constraints. In *IEEE INFOCOM 2023 - IEEE Conference on Computer Communications*, pages 1–10, 2023.

[19] Michael Luby, Alistair Sinclair, and David Zuckerman. Optimal speedup of las vegas algorithms. *Information Processing Letters*, 47(4):173–180, 1993.

[20] Karthik Abinav Sankararaman and Aleksandrs Slivkins. Bandits with knapsacks beyond the worst case. In *Proceedings of the 35th International Conference on Neural Information Processing Systems*, NIPS '21, Red Hook, NY, USA, 2021. Curran Associates Inc.

[21] Dmitry Starkov and Sergey Belan. Universal performance bounds of restart. *Physical Review E*, 107(6), June 2023.

[22] Alexandre B. Tsybakov. *Introduction to Nonparametric Estimation*. Springer New York, 2009.