p_{t_{l+2}+1}-\sum_{v=1}^{l}x_{v,t_{l+2}+1}\Rightarrow\sum_{v=1}^{l+1}x_{v,t_{l+2}+1}\leq\theta\cdot
p_{t_{l+2}+1}$

Also, note that

$0\leq x_{l+1,t_{l+2}}=\theta\cdot p_{t_{l+2}}-\sum_{v=1}^{l}x_{v,t_{l+2}}\leq
p_{t_{l+2}}\cdot\sum_{\tau=1}^{t_{l+2}-1}(x_{l,\tau}-x_{l+1,\tau})$

we get that

$x_{l+1,t_{l+2}+1}/p_{t_{l+2}+1}=\sum_{\tau=1}^{t_{l+2}}(x_{l,\tau}-x_{l+1,\tau})\geq\sum_{\tau=1}^{t_{l+2}-1}(x_{l,\tau}-x_{l+1,\tau})-x_{l+1,t_{l+2}}\geq(1-p_{t_{l+2}})\cdot\sum_{\tau=1}^{t_{l+2}-1}(x_{l,\tau}-x_{l+1,\tau})$

Thus, we proved that $0\leq x_{l+1,t_{l+2}+1}$ and
$\sum_{v=1}^{l+1}x_{v,t_{l+2}+1}\leq\theta\cdot p_{t_{l+2}+1}$. Now suppose
that for a $t$ such that $t_{l+2}+1\leq t\leq T$, it holds that $0\leq
x_{l+1,t}$ and $\sum_{v=1}^{l+1}x_{v,t}\leq\theta\cdot p_{t}$. Then we have
that

$\sum_{v=1}^{l+1}x_{v,t+1}/p_{t+1}=1-\sum_{\tau=1}^{t}x_{l+1,\tau}\leq
1-\sum_{\tau=1}^{t-1}x_{l+1,\tau}=\sum_{v=1}^{l+1}x_{v,t}/p_{t}\leq\theta$

Also, note that $0\leq
x_{l+1,t}=p_{t}\cdot\sum_{\tau=1}^{t-1}(x_{l,\tau}-x_{l+1,\tau})$, we have
that

$x_{l+1,t+1}/p_{t+1}=\sum_{\tau=1}^{t}(x_{l,\tau}-x_{l+1,\tau})\geq\sum_{\tau=1}^{t-1}(x_{l,\tau}-x_{l+1,\tau})-x_{l+1,\tau}=(1-p_{t})\cdot\sum_{\tau=1}^{t-1}(x_{l,\tau}-x_{l+1,\tau})\geq
0$

Thus, we have proved that $0\leq x_{l+1,t+1}$ and
$\sum_{v=1}^{l+1}x_{v,t+1}\leq\theta\cdot p_{t+1}$. From the induction on $t$,
we can conclude that for any $1\leq t\leq T$, it holds that $0\leq x_{l+1,t}$
and $\sum_{v=1}^{l+1}x_{v,t}\leq\theta\cdot p_{t}$. Again, from the induction
on $l$, we can conclude that for any $1\leq l\leq k$ and any $1\leq t\leq T$,
it holds that $0\leq x_{l,t}$ and $\sum_{v=1}^{l}x_{v,t}\leq\theta\cdot
p_{t}$, which completes our proof. ∎

Now we are ready to prove Lemma 9.

###### Proof.

Proof of Lemma 9: When $\\{x_{l,t}(\theta)\\}$ is feasible to
$\text{Dual}(\bm{p},k)$ in (9), we get from constraint (9b) and (9c) that

$x_{1,T}(\theta)\leq
p_{T}\cdot(1-\sum_{t=1}^{T-1}x_{1,t}(\theta))\text{\leavevmode\nobreak\
\leavevmode\nobreak\ and\leavevmode\nobreak\ \leavevmode\nobreak\
}x_{l,T}(\theta)\leq
p_{T}\cdot\sum_{t=1}^{T-1}(x_{l-1,t}(\theta)-x_{l,t}(\theta))\leavevmode\nobreak\
\leavevmode\nobreak\ \forall l=2,\dots,k$

Summing up the above inequalities, we get

$\sum_{l=1}^{k}x_{l,T}(\theta)\leq
p_{T}\cdot(1-\sum_{t=1}^{T-1}x_{k,t}(\theta))$

Further note that by definition, we have
$\sum_{l=1}^{k}x_{l,T}(\theta)=\theta\cdot p_{T}$. Thus, we show that
$\\{x_{l,t}(\theta)\\}$ is feasible implies that
$\sum_{t=1}^{T-1}x_{k,t}(\theta)\leq 1-\theta$.

Now we prove the reverse direction. Note that from the definition of
$\\{x_{l,t}(\theta)\\}$, we have that $x_{l,t}(\theta)\leq
p_{t}\cdot\sum_{\tau=1}^{t-1}(x_{l-1,\tau}(\theta)-x_{l,\tau}(\theta))$ holds
for any $1\leq l\leq k-1$ and any $1\leq t\leq T$, where we set
$\sum_{\tau=1}^{t-1}x_{0,\tau}(\theta)=1$ for any $t$ for simplicity. Also,
$\\{x_{l,t}(\theta)\\}$ are nonnegative as shown by Lemma 11. Thus, we have
that

$\\{x_{l,t}(\theta)\\}\text{\leavevmode\nobreak\ is\leavevmode\nobreak\
feasible\leavevmode\nobreak\ }\Leftrightarrow x_{k,t}(\theta)\leq
p_{t}\cdot\sum_{\tau=1}^{t-1}(x_{k-1,\tau}(\theta)-x_{k,\tau}(\theta))\text{\leavevmode\nobreak\
holds\leavevmode\nobreak\ for\leavevmode\nobreak\ any\leavevmode\nobreak\
}t_{k}+1\leq t\leq T$

Moreover, note that from definition, for $t_{k}+1\leq t\leq T$, we have that
$x_{l,t}(\theta)=p_{t}\cdot\sum_{\tau=1}^{t-1}(x_{l-1,\tau}(\theta)-x_{l,\tau}(\theta))$
when $1\leq l\leq k-1$. Thus, for $t_{k}+1\leq t\leq T$, we have that

$x_{k,t}(\theta)\leq
p_{t}\cdot\sum_{\tau=1}^{t-1}(x_{k-1,\tau}(\theta)-x_{k,\tau}(\theta))\Leftrightarrow\theta=\sum_{v=1}^{k}x_{v,t}/p_{t}\leq
1-\sum_{\tau=1}^{t-1}x_{k,\tau}(\theta)$

From the nonnegativity of $\\{x_{l,t}(\theta)\\}$, we know that
$\sum_{\tau=1}^{t-1}x_{k,\tau}(\theta)$ is monotone increasing with $t$. Thus,
it holds that

$\\{x_{l,t}(\theta)\\}\text{\leavevmode\nobreak\ is\leavevmode\nobreak\
feasible\leavevmode\nobreak\ }\Leftrightarrow\theta\leq
1-\sum_{t=1}^{T-1}x_{k,t}(\theta)$

which completes our proof. ∎

###  B3 Proof of Lemma 10

###### Proof.

Proof: For any fixed $\theta\in[0,1]$ and any fixed $\Delta\geq 0$ such that
$\theta+\Delta\in[0,1]$, we compare between $\\{x_{l,t}(\theta)\\}$ and
$\\{x_{l,t}(\theta+\Delta)\\}$. Since we consider for a fixed $\theta$ and
$\Delta$, for notation brevity, we will omit $\theta$ and $\Delta$ by
substituting $\\{x_{l,t}\\}$ for $\\{x_{l,t}(\theta)\\}$ and substituting
$\\{x^{\prime}_{l,t}\\}$ for $\\{x_{l,t}(\theta+\Delta)\\}$. Respectively, we
denote $y_{l,t}=\sum_{\tau=1}^{t-1}x_{l,\tau}$ and
$y^{\prime}_{l,t}=\sum_{\tau=1}^{t-1}x^{\prime}_{l,\tau}$. Also, we denote
$\\{t_{l}\\}$ to be the time indexes associated with $\\{x_{l,t}\\}$ in the
definition of $\\{x_{l,t}\\}$ and $\\{t^{\prime}_{l}\\}$ to be the time
indexes associated with $\\{x^{\prime}_{l,t}\\}$. We will use induction to
show that for each $l$, we have that $y_{l,t}\leq y^{\prime}_{l,t}$ and
$\sum_{v=1}^{l}y^{\prime}_{v,t}\leq\sum_{v=1}^{l}y_{v,t}+\Delta\cdot\sum_{\tau=1}^{t}p_{\tau}$
hold for each $t$.

For the case $l=1$, obviously we have that $t_{2}^{\prime}\leq t_{2}$. When
$1\leq t\leq t_{2}^{\prime}$, from definition, it holds that $y_{1,t}\leq
y^{\prime}_{1,t}\leq y_{1,t}+\Delta\cdot\sum_{\tau=1}^{t}p_{\tau}$. We now use
induction on $t$ for $t^{\prime}_{2}+1\leq t\leq t_{2}$. When
$t=t^{\prime}_{2}+1$, note that

$x^{\prime}_{1,t^{\prime}_{2}+1}=p_{t^{\prime}_{2}+1}\cdot(1-y^{\prime}_{1,t^{\prime}_{2}})\leq(\theta+\Delta)\cdot
p_{t^{\prime}_{2}+1}\text{\leavevmode\nobreak\ \leavevmode\nobreak\
and\leavevmode\nobreak\ \leavevmode\nobreak\
}x_{1,t^{\prime}_{2}+1}=\theta\cdot p_{t^{\prime}_{2}+1}\leq
p_{t^{\prime}_{2}+1}\cdot(1-y_{1,t^{\prime}_{2}})$

we have that

$y_{1,t^{\prime}_{2}+1}=y_{1,t^{\prime}_{2}}+x_{1,t^{\prime}_{2}+1}\leq
p_{t^{\prime}_{2}+1}+(1-p_{t^{\prime}_{2}+1})\cdot y_{1,t^{\prime}_{2}}\leq
p_{t^{\prime}_{2}+1}+(1-p_{t^{\prime}_{2}+1})\cdot
y^{\prime}_{1,t^{\prime}_{2}}=y^{\prime}_{1,t^{\prime}_{2}+1}$

and

$y^{\prime}_{1,t^{\prime}_{2}+1}=y^{\prime}_{1,t^{\prime}_{2}}+x^{\prime}_{1,t^{\prime}_{2}+1}\leq
y_{1,t^{\prime}_{2}}+\Delta\cdot\sum_{t=1}^{t^{\prime}_{2}}p_{t}+(\theta+\Delta)\cdot
p_{t^{\prime}_{2}+1}=y_{1,t^{\prime}_{2}+1}+\Delta\cdot\sum_{t=1}^{t^{\prime}_{2}+1}p_{t}$

Now suppose for a fixed $t$ satisfying $t^{\prime}_{2}+1\leq t\leq t_{2}-1$,
it holds $y_{1,t}\leq y^{\prime}_{1,t}\leq
y_{1,t}+\Delta\cdot\sum_{\tau=1}^{t}p_{\tau}$. From definition, note that

$x^{\prime}_{1,t+1}=p_{t+1}\cdot(1-y^{\prime}_{1,t})\leq(\theta+\Delta)\cdot
p_{t+1}\text{\leavevmode\nobreak\ \leavevmode\nobreak\ and\leavevmode\nobreak\
\leavevmode\nobreak\ }x_{1,t+1}=\theta\cdot p_{t+1}\leq
p_{t+1}\cdot(1-y_{1,t})$

we have

$y_{1,t+1}=y_{1,t}+x_{1,t+1}\leq p_{t+1}+(1-p_{t+1})\cdot y_{1,t}\leq
p_{t+1}+(1-p_{t+1})\cdot y^{\prime}_{1,t}=y^{\prime}_{1,t+1}$

and

$y^{\prime}_{1,t+1}=y^{\prime}_{1,t}+x^{\prime}_{1,t+1}\leq
y_{1,t}+\Delta\cdot\sum_{\tau=1}^{t}p_{\tau}+(\theta+\Delta)\cdot
p_{t+1}=y_{1,t+1}+\Delta\cdot\sum_{\tau=1}^{t+1}p_{\tau}$

Thus, from induction on $t$, we conclude that $y_{1,t}\leq
y^{\prime}_{1,t}\leq y_{1,t}+\Delta\cdot\sum_{\tau=1}^{t}p_{\tau}$ holds for
any $t^{\prime}_{2}+1\leq t\leq t_{2}$. Finally, when $t\geq t_{2}+1$, note
that

$y_{1,t}=p_{t}+(1-p_{t})\cdot y_{1,t-1}\text{\leavevmode\nobreak\
\leavevmode\nobreak\ and\leavevmode\nobreak\ \leavevmode\nobreak\
}y^{\prime}_{1,t}=p_{t}+(1-p_{t})\cdot y^{\prime}_{1,t-1}$

which implies that

$y^{\prime}_{1,t}-y_{1,t}=(1-p_{t})\cdot(y^{\prime}_{1,t-1}-y_{1,t-1})=\dots=(y^{\prime}_{1,t_{2}}-y_{1,t_{2}})\cdot\prod_{\tau=t_{2}+1}^{t}(1-p_{\tau})$

Thus, we prove that for any $1\leq t\leq T$, it holds that $y_{1,t}\leq
y^{\prime}_{1,t}\leq y_{1,t}+\Delta\cdot\sum_{\tau=1}^{t}p_{\tau}$.

Suppose that for a fixed $1\leq l\leq k$, $y_{l,t}\leq y^{\prime}_{l,t}$ and
$\sum_{v=1}^{l}y^{\prime}_{v,t}\leq\sum_{v=1}^{l}y_{v,t}+\Delta\cdot\sum_{\tau=1}^{t}p_{\tau}$
hold for each $t$. We now consider the case for $l+1$. When
$t\leq\min\\{t_{l+2},t^{\prime}_{l+2}\\}$, from definition, we have that

$\sum_{v=1}^{l+1}y^{\prime}_{v,t}=(\theta+\Delta)\cdot\sum_{\tau=1}^{t}p_{\tau}\leavevmode\nobreak\
\leavevmode\nobreak\ \text{and}\leavevmode\nobreak\ \leavevmode\nobreak\
\sum_{v=1}^{l+1}y_{v,t}=\theta\cdot\sum_{\tau=1}^{t}p_{\tau}$

which implies that
$\sum_{v=1}^{l+1}y^{\prime}_{v,t}\leq\sum_{v=1}^{l+1}y_{v,t}+\Delta\cdot\sum_{\tau=1}^{t}p_{\tau}$.
Also, we have

$y^{\prime}_{l+1,t}-y_{l+1,t}=\Delta\cdot\sum_{\tau=1}^{t}p_{\tau}-\left(\sum_{v=1}^{l}y^{\prime}_{v,t}-\sum_{v=1}^{l}y_{v,t}\right)\geq
0$

where the last inequality holds from induction condition. Thus, we prove that
$y_{l+1,t}\leq y^{\prime}_{l+1,t}$ and
$\sum_{v=1}^{l+1}y^{\prime}_{v,t}\leq\sum_{v=1}^{l+1}y_{v,t}+\Delta\cdot\sum_{\tau=1}^{t}p_{\tau}$
hold for each $1\leq t\leq\min\\{t_{l+2},t^{\prime}_{l+2}\\}$. Moreover, note
that $t_{l+2}$ is defined as the first time that $\theta>1-y_{l+1,t_{l+2}}$
while $t^{\prime}_{l+2}$ is defined as the first time that
$\theta+\Delta>1-y^{\prime}_{l+1,t^{\prime}_{l+2}}$. Since
$y^{\prime}_{l+1,t}\geq y_{l+1,t}$ when
$t\leq\min\\{t_{l+2},t^{\prime}_{l+2}\\}$, we must have $t^{\prime}_{l+2}\leq
t_{l+2}$. Then we use induction on $t$ for $t^{\prime}_{l+2}+1\leq t\leq
t_{l+2}$. When $t=t^{\prime}_{l+2}+1\leq t_{l+2}$, from definition, we have

$x^{\prime}_{l+1,t^{\prime}_{l+2}+1}=p_{t^{\prime}_{l+2}+1}\cdot(y^{\prime}_{l,t^{\prime}_{l+2}}-y^{\prime}_{l+1,t^{\prime}_{l+2}})\Rightarrow
y^{\prime}_{l+1,t^{\prime}_{l+2}+1}=p_{t^{\prime}_{l+2}+1}\cdot
y^{\prime}_{l,t^{\prime}_{l+2}}+(1-p_{t^{\prime}_{l+2}+1})\cdot
y^{\prime}_{l+1,t^{\prime}_{l+2}}$

and

$x_{l+1,t^{\prime}_{l+2}+1}\leq
p_{t^{\prime}_{l+2}+1}\cdot(y_{l,t^{\prime}_{l+2}}-y_{l+1,t^{\prime}_{l+2}})\Rightarrow
y_{l+1,t^{\prime}_{l+2}+1}\leq p_{t^{\prime}_{l+2}+1}\cdot
y_{l,t^{\prime}_{l+2}}+(1-p_{t^{\prime}_{l+2}+1})\cdot
y_{l+1,t^{\prime}_{l+2}}$

Note that $y^{\prime}_{l,t^{\prime}_{l+2}}\geq y_{l,t^{\prime}_{l+2}}$ and
$y^{\prime}_{l+1,t^{\prime}_{l+2}}\geq y_{l+1,t^{\prime}_{l+2}}$, we get
$y^{\prime}_{l+1,t^{\prime}_{l+2}+1}\geq y_{l+1,t^{\prime}_{l+2}+1}$.
Moreover, note that from the definition of $t^{\prime}_{l+2}$, we have

$\sum_{v=1}^{l+1}x^{\prime}_{v,t^{\prime}_{l+2}+1}\leq
p_{t^{\prime}_{l+2}+1}\cdot(\theta+\Delta)=\sum_{v=1}^{l+1}x_{v,t^{\prime}_{l+2}+1}+\Delta\cdot
p_{t^{\prime}_{l+2}+1}$

which implies that

$\displaystyle\sum_{v=1}^{l+1}y^{\prime}_{v,t^{\prime}_{l+2}+1}$
$\displaystyle=\sum_{v=1}^{l+1}y^{\prime}_{v,t^{\prime}_{l+2}}+\sum_{v=1}^{l+1}x^{\prime}_{v,t^{\prime}_{l+2}+1}\leq\sum_{v=1}^{l+1}y_{v,t^{\prime}_{l+2}}+\Delta\cdot\sum_{j=1}^{t^{\prime}_{l+2}}p_{j}+\sum_{v=1}^{l+1}x_{v,t^{\prime}_{l+2}+1}+\Delta\cdot
p_{t^{\prime}_{l+2}+1}$
$\displaystyle=\sum_{v=1}^{l+1}y_{v,t^{\prime}_{l+2}+1}+\Delta\cdot\sum_{j=1}^{t^{\prime}_{l+2}+1}p_{j}$

Then suppose for a fixed $t$ satisfying $t^{\prime}_{l+2}+1\leq t\leq
t_{l+2}-1$, it holds that $y_{l+1,t}\leq y^{\prime}_{l+1,t}$ and
$\sum_{v=1}^{l+1}y^{\prime}_{v,t}\leq\sum_{v=1}^{l+1}y_{v,t}+\Delta\cdot\sum_{\tau=1}^{t}p_{\tau}$.
From definition, we have

$x^{\prime}_{l+1,t+1}=p_{t+1}\cdot(y^{\prime}_{l,t}-y^{\prime}_{l+1,t})\Rightarrow
y^{\prime}_{l+1,t+1}=p_{t+1}\cdot y^{\prime}_{l,t}+(1-p_{t+1})\cdot
y^{\prime}_{l+1,t}$

and

$x_{l+1,t+1}\leq p_{t+1}\cdot(y_{l,t}-y_{l+1,t})\Rightarrow y_{l+1,t+1}\leq
p_{t+1}\cdot y_{l,t}+(1-p_{t+1})\cdot y_{l+1,t}$

Note that $y^{\prime}_{l,t}\geq y_{l,t}$ and $y^{\prime}_{l+1,t}\geq
y_{l+1,t}$, we have $y^{\prime}_{l+1,t+1}\geq y_{l+1,t+1}$. Also, from the
definition of $t^{\prime}_{l+2}$, we have

$\sum_{v=1}^{l+1}x^{\prime}_{v,t+1}\leq
p_{t+1}\cdot(\theta+\Delta)=\sum_{v=1}^{l+1}x_{v,t+1}+\Delta\cdot p_{t+1}$

which implies that

$\displaystyle\sum_{v=1}^{l+1}y^{\prime}_{v,t+1}$
$\displaystyle=\sum_{v=1}^{l+1}y^{\prime}_{v,t}+\sum_{v=1}^{l+1}x^{\prime}_{v,t+1}\leq\sum_{v=1}^{l+1}y_{v,t}+\Delta\cdot\sum_{\tau=1}^{t}p_{\tau}+\sum_{v=1}^{l+1}x_{v,t+1}+\Delta\cdot
p_{t+1}$
$\displaystyle=\sum_{v=1}^{l+1}y_{v,t+1}+\Delta\cdot\sum_{\tau=1}^{t+1}p_{\tau}$

Thus, from induction on $t$, we prove that $y_{l+1,t}\leq y^{\prime}_{l+1,t}$
and
$\sum_{v=1}^{l+1}y^{\prime}_{v,t}\leq\sum_{v=1}^{l+1}y_{v,t}+\Delta\cdot\sum_{\tau=1}^{t}p_{\tau}$
hold for any $t^{\prime}_{l+2}+1\leq t\leq t_{l+2}$. Finally, when $t\geq
t_{l+2}+1$, note that

$y_{l+1,t}=p_{t}\cdot y_{l,t-1}+(1-p_{t})\cdot
y_{l+1,t-1}\text{\leavevmode\nobreak\ \leavevmode\nobreak\
and\leavevmode\nobreak\ \leavevmode\nobreak\ }y^{\prime}_{l+1,t}=p_{t}\cdot
y^{\prime}_{l,t-1}+(1-p_{t})\cdot y^{\prime}_{l+1,t-1}$

which implies that

$y^{\prime}_{l+1,t}-y_{l+1,t}=p_{t}\cdot(y^{\prime}_{l,t-1}-y_{l,t-1})+(1-p_{t})\cdot(y^{\prime}_{l+1,t-1}-y_{l+1,t-1})$

It is direct to show inductively on $t$ such that $y_{l+1,t}\leq
y^{\prime}_{l+1,t}$ and
$\sum_{v=1}^{l+1}y^{\prime}_{v,t}\leq\sum_{v=1}^{l+1}y_{v,t}+\Delta\cdot\sum_{\tau=1}^{t}p_{\tau}$
hold for any $t\geq t_{l+2}+1$.

Thus, we have proved that for any $1\leq t\leq T$, we have $y_{l+1,t}\leq
y^{\prime}_{l+1,t}$ and
$\sum_{v=1}^{l+1}y^{\prime}_{v,t}\leq\sum_{v=1}^{l}y_{v,t}+\Delta\cdot\sum_{\tau=1}^{t}p_{\tau}$.
By the induction on $l$, we finally prove that for any $1\leq l\leq k$,
$y_{l,t}\leq y^{\prime}_{l,t}$ and
$\sum_{v=1}^{l}y^{\prime}_{v,t}\leq\sum_{v=1}^{l}y_{v,t}+\Delta\cdot\sum_{\tau=1}^{t}p_{\tau}$
hold for any $1\leq t\leq T$. In this way, we prove that $y_{l,t}(\theta)$ is
monotone increasing with $\theta$ for any $l,t$. Moreover, note that since
$\sum_{\tau=1}^{T}p_{\tau}\leq k$, we have that $y_{l,t}(\theta+\Delta)\leq
y_{l,t}(\theta)+k\cdot\Delta$ hold for any $\theta,\Delta$ and any $l,t$.
Thus, $y_{l,t}(\theta)$ is a continuous function on $\theta$, which completes
our proof. ∎

###  B4 Construction of $\\{\beta^{*}_{l,t},\xi^{*}_{t}\\}$ and Proof of
Theorem 1

Given Lemma 4, in order to prove Theorem 1, it is enough for us to construct a
feasible solution $\\{\beta^{*}_{l,t},\xi^{*}_{t}\\}$ to
$\text{Primal}(\bm{p},k)$ in (10) such that the primal-dual pair
$\\{\theta^{*},x_{l,t}(\theta^{*})\\}$ and $\\{\beta^{*}_{l,t},\xi^{*}_{t}\\}$
satisfies the complementary slackness conditions. Specifically, we will
construct a feasible solution $\\{\beta^{*}_{l,t},\xi^{*}_{t}\\}$ to
$\text{Primal}(\bm{p},k)$ satisfying the following conditions:

$\displaystyle\beta^{*}_{1,t}\cdot\left(x_{1,t}(\theta^{*})-p_{t}\cdot(1-\sum_{\tau<t}x_{1,\tau}(\theta^{*}))\right)=0,\leavevmode\nobreak\
\leavevmode\nobreak\ \forall t=1,\dots,T$ (27)
$\displaystyle\beta^{*}_{l,t}\cdot\left(x_{l,t}(\theta^{*})-p_{t}\cdot\sum_{\tau<t}(x_{l-1,\tau}(\theta^{*})-x_{l,\tau}(\theta^{*}))\right)=0,\leavevmode\nobreak\
\leavevmode\nobreak\ \forall t=1,\dots,T,\forall l=2,\dots,k$ $\displaystyle
x_{l,t}(\theta^{*})\cdot\left(\beta^{*}_{l,t}+\sum_{\tau>t}p_{\tau}\cdot(\beta^{*}_{l,\tau}-\beta^{*}_{l+1,\tau})-\xi^{*}_{t}\right)=0,\leavevmode\nobreak\
\leavevmode\nobreak\ \forall t=1,\dots,T,\forall l=2,\dots,k$ $\displaystyle
x_{k,t}(\theta^{*})\cdot\left(\beta^{*}_{k,t}+\sum_{\tau>t}p_{\tau}\cdot\beta^{*}_{k,\tau}-\xi^{*}_{t}\right)=0,\leavevmode\nobreak\
\leavevmode\nobreak\ \forall t=1,\dots,T$

Note that from definitions, $\\{x_{l,t}(\theta^{*})\\}$ satisfies the
following conditions:

$\displaystyle x_{l,t}(\theta^{*})=0\leq
p_{t}\cdot\sum_{\tau=1}^{t-1}(x_{l-1,\tau}(\theta^{*})-x_{l,\tau}(\theta^{*})),\leavevmode\nobreak\
\leavevmode\nobreak\ \forall t\leq t_{l}$ $\displaystyle
x_{l,t}(\theta^{*})=\theta^{*}\cdot
p_{t}-\sum_{v=1}^{l-1}x_{v,t}(\theta^{*})\leq
p_{t}\cdot\sum_{\tau=1}^{t-1}(x_{l-1,\tau}(\theta^{*})-x_{l,\tau}(\theta^{*}))\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \text{for\leavevmode\nobreak\
}t_{l}+1\leq t\leq t_{l+1}$

where $\\{t_{l}\\}$ are the time indexes associated with the definition of
$\\{x_{l,t}(\theta^{*})\\}$ and we define $t_{1}=0$, $t_{k+1}=T-1$. For
simplicity, we also denote $\sum_{\tau=1}^{t-1}x_{0,\tau}(\theta^{*})=1$ for
any $t$. Thus, in order for $\\{\beta^{*}_{l,t},\xi^{*}_{t}\\}$ to satisfy the
conditions in (27), it is enough for $\\{\beta^{*}_{l,t},\xi^{*}_{t}\\}$ to be
feasible to $\text{Primal}(\bm{p},k)$ and satisfy the following conditions:

$\displaystyle\beta^{*}_{l,t}=0\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \text{for\leavevmode\nobreak\ }t\leq t_{l+1}$ (28)
$\displaystyle\beta^{*}_{l,t}+\sum_{\tau=t+1}^{T}p_{\tau}\cdot(\beta^{*}_{l,\tau}-\beta^{*}_{l+1,\tau})=\xi^{*}_{t}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \text{for\leavevmode\nobreak\ }t\geq
t_{l}+1$ (29)

where we denote $\beta^{*}_{k+1,t}=0$ for notation simplicity. We now show the
construction of the solution $\\{\beta^{*}_{l,t},\xi^{*}_{t}\\}$ to
$\text{Primal}(\bm{p},k)$. Define the following constants for each
$l,q\in\\{1,2,\dots,k\\}$:

$B_{l,q}=\sum_{t_{l}+1\leq j_{1}<j_{2}<\dots<j_{q}\leq
t_{l+1}}\frac{p_{j_{1}}p_{j_{2}}\dots
p_{j_{q}}}{(1-p_{j_{1}})(1-p_{j_{2}})\dots(1-p_{j_{q}})}\cdot\prod_{w=t_{l}+1}^{t_{l+1}}(1-p_{w})$

and we set $B_{l,0}=\prod_{w=t_{l}+1}^{t_{l+1}}(1-p_{w})$. We also define the
following terms for each $l,q\in\\{1,2,\dots,k\\}$ and each
$t\in\\{t_{l}+1,\dots,t_{l+1}\\}$, where $\\{t_{l}\\}$ are the time indexes
defined in the construction of $\\{\theta^{*},x_{l,t}(\theta^{*})\\}$ and we
define $t_{1}=0$, $t_{k+1}=T-1$:

$A_{l,q}(t)=\sum_{t+1\leq j_{1}<j_{2}<\dots<j_{q}\leq
t_{l+1}}\frac{p_{j_{1}}p_{j_{2}}\dots
p_{j_{q}}}{(1-p_{j_{1}})(1-p_{j_{2}})\dots(1-p_{j_{q}})}\cdot\prod_{w=t+1}^{t_{l+1}}(1-p_{w})$

and we set $A_{l,0}(t)=\prod_{w=t+1}^{t_{l+1}}(1-p_{w})$. Then our
construction of the solution $\\{\beta^{*}_{l,t},\xi^{*}_{t}\\}$ can be fully
described as follows:

$\displaystyle\xi^{*}_{T}=\beta^{*}_{l_{1},T}=R,\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \forall l_{1}=1,2,\dots,k$ (30)
$\displaystyle\beta^{*}_{l_{1},t}=0,\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \forall l_{1}=1,2,\dots,k,\forall t\leq t_{l_{1}+1}$
$\displaystyle\xi^{*}_{t}=\phi_{l}\cdot p_{T}R,\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \forall l=1,2,\dots,k,\forall
t_{l}+1\leq t\leq t_{l+1}$
$\displaystyle\beta^{*}_{l_{1},t}=p_{T}R\cdot\sum_{w=l_{1}}^{l_{2}-1}\delta_{w,l_{2}}\cdot
A_{l_{2},w-l_{1}}(t),\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \forall l_{1}=1,2,\dots,k,\forall
l_{2}=l_{1}+1,\dots,k,\forall t_{l_{2}}+1\leq t\leq t_{l_{2}+1}$

where the parameters $\\{\phi_{l},\delta_{l_{1},l_{2}},R\\}$ are defined as:

$\displaystyle\delta_{l,k}=1\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \forall
l=1,2,\dots,k-1$ $\displaystyle\delta_{l,l}=0\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \forall l=1,2,\dots,k$
$\displaystyle\delta_{l_{1},l_{2}}=\sum_{w_{0}=l_{1}+1}^{l_{2}}\sum_{w_{1}=w_{0}}^{l_{2}+1}\sum_{w_{2}=w_{1}}^{l_{2}+2}\dots\sum_{w_{k-1-l_{2}}=w_{k-2-l_{2}}}^{k-1}B_{l_{2}+1,w_{1}-w_{0}}\cdot
B_{l_{2}+2,w_{2}-w_{1}}\dots B_{k-1,w_{k-1-l_{2}}-w_{k-2-l_{2}}}\cdot
B_{k,k-w_{k-1-l_{2}}},$ $\displaystyle\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \forall
l_{2}=1,2,\dots,k-1\text{\leavevmode\nobreak\ and\leavevmode\nobreak\
}l_{1}=1,2,\dots,l_{2}-1$ $\displaystyle\phi_{k}=1$
$\displaystyle\phi_{l}=\sum_{q=l+1}^{k}\sum_{w=l+1}^{q}(\delta_{w-1,q}-\delta_{w,q})\cdot(1-\sum_{v=0}^{w-l-1}B_{q,v})\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \forall l=1,2,\dots,k-1$

and $R$ is a positive constant such that
$\sum_{t=1}^{T}p_{t}\cdot\xi^{*}_{t}=1$. We then prove the feasibility of
$\\{\beta^{*}_{l,t},\xi^{*}_{t}\\}$ and the conditions (28), (29) are
satisfied. Obviously, from definition, $\beta^{*}_{l,t}$ is nonnegative for
each $l$ and each $t$. We first prove that $\xi^{*}_{t}$ is also nonnegative
for each $t$.

###### Lemma 12

For each $l_{2}=1,2,\dots,k$ and each $l_{1}=1,2,\dots,l_{2}-1$, we have that
$\delta_{l_{1},l_{2}}\geq\delta_{l_{1}+1,l_{2}}$.

###### Proof.

Proof: Note that when $l_{2}=k$, we have that $\delta_{l,k}=1$ for each
$l=1,2,\dots,k-1$, thus it holds that $\delta_{l,k}\geq\delta_{l+1,k}$. When
$l_{2}\leq k-1$, from definitions, we have that for each
$l_{1}=1,2,\dots,l_{2}-1$

$\delta_{l_{1},l_{2}}-\delta_{l_{1}+1,l_{2}}=\sum_{w_{1}=l_{1}+1}^{l_{2}+1}\sum_{w_{2}=w_{1}}^{l_{2}+2}\dots\sum_{w_{k-1-l_{2}}=w_{k-2-l_{2}}}^{k-1}B_{l_{2}+1,w_{1}-l_{1}-1}\cdot
B_{l_{2}+2,w_{2}-w_{1}}\dots B_{k-1,w_{k-1-l_{2}}-w_{k-2-l_{2}}}\cdot
B_{k,k-w_{k-1-l_{2}}}$

which completes our proof. ∎

We then show that the term $1-\sum_{w=0}^{q}B_{l,w}$ is nonnegative for each
$l$ and each $q$. Note that the following lemma essentially implies that
$\sum_{t=t_{l}+1}^{t_{l+1}}p_{t}\cdot A_{l,q}(t)=1-\sum_{w=0}^{q}B_{l,w}$, by
replacing $i_{1}$ with $t_{l}$ and $i_{2}$ with $t_{l+1}$ in (31), which
establishes the nonnegativity of the term $1-\sum_{w=0}^{q}B_{l,w}$.

###### Lemma 13

For each $q\in\\{1,2,\dots,k\\}$ and any $1\leq i_{1}+1\leq i_{2}\leq T$, it
holds that

$\displaystyle\sum_{t=i_{1}+1}^{i_{2}}p_{t}\cdot\sum_{t+1\leq
j_{1}<j_{2}<\dots<j_{q}\leq i_{2}}\frac{p_{j_{1}}p_{j_{2}}\dots
p_{j_{q}}}{(1-p_{j_{1}})(1-p_{j_{2}})\dots(1-p_{j_{q}})}\cdot\prod_{v=t+1}^{i_{2}}(1-p_{v})$
(31) $\displaystyle=1-\sum_{w=0}^{q}\sum_{i_{1}+1\leq
j_{1}<j_{2}<\dots<j_{w}\leq i_{2}}\frac{p_{j_{1}}p_{j_{2}}\dots
p_{j_{w}}}{(1-p_{j_{1}})(1-p_{j_{2}})\dots(1-p_{j_{w}})}\cdot\prod_{v=i_{1}+1}^{i_{2}}(1-p_{v}),$

###### Proof.

Proof: We will do induction on $q$ from $q=0$ to $q=k$ to prove (31). When
$q=0$, we have that

$\displaystyle\sum_{t=i_{1}+1}^{i_{2}}p_{t}\cdot\prod_{v=t+1}^{i_{2}}(1-p_{v})$
$\displaystyle=\sum_{t=i_{1}+1}^{i_{2}}(1-(1-p_{t}))\cdot\prod_{v=t+1}^{i_{2}}(1-p_{v})=\sum_{t=i_{1}+1}^{i_{2}}\left(\prod_{v=t+1}^{i_{2}}(1-p_{v})-\prod_{v=t}^{i_{2}}(1-p_{v})\right)$
$\displaystyle=1-\prod_{v=i_{1}+1}^{i_{2}}(1-p_{v})$

Thus, we have (31) holds for $q=0$. Suppose (31) holds for $1,2,\dots,q-1$, we
consider the case for $q$. For any $1\leq i_{1}+1\leq i_{2}\leq T$, we have
that

$\displaystyle\sum_{t=i_{1}+1}^{i_{2}}p_{t}\cdot\sum_{t+1\leq
j_{1}<j_{2}<\dots<j_{q}\leq i_{2}}\frac{p_{j_{1}}p_{j_{2}}\dots
p_{j_{q}}}{(1-p_{j_{1}})(1-p_{j_{2}})\dots(1-p_{j_{q}})}\cdot\prod_{v=t+1}^{i_{2}}(1-p_{v})$
$\displaystyle=\sum_{t=i_{1}+1}^{i_{2}}p_{t}\cdot\sum_{j_{1}=t+1}^{i_{2}}\sum_{j_{1}<j_{2}<\dots<j_{q}\leq
i_{2}}\frac{p_{j_{1}}p_{j_{2}}\dots
p_{j_{q}}}{(1-p_{j_{1}})(1-p_{j_{2}})\dots(1-p_{j_{q}})}\cdot\prod_{v=t+1}^{i_{2}}(1-p_{v})$
$\displaystyle=\sum_{j_{1}=i_{1}+2}^{i_{2}}\sum_{t=i_{1}+1}^{j_{1}-1}p_{t}\cdot\frac{p_{j_{1}}}{1-p_{j_{1}}}\cdot\sum_{j_{1}<j_{2}<\dots<j_{q}\leq
i_{2}}\frac{p_{j_{2}}\dots
p_{j_{q}}}{(1-p_{j_{2}})\dots(1-p_{j_{q}})}\cdot\prod_{v=t+1}^{i_{2}}(1-p_{v})$
$\displaystyle=\sum_{j_{1}=i_{1}+2}^{i_{2}}\frac{p_{j_{1}}}{1-p_{j_{1}}}\cdot\sum_{j_{1}<j_{2}<\dots<j_{q}\leq
i_{2}}\frac{p_{j_{2}}\dots
p_{j_{q}}}{(1-p_{j_{2}})\dots(1-p_{j_{q}})}\cdot\prod_{v=j_{1}}^{i_{2}}(1-p_{v})\cdot\sum_{t=i_{1}+1}^{j_{1}-1}p_{t}\cdot\prod_{v=t+1}^{j_{1}-1}(1-p_{v})$

where the second equality holds by exchanging the order of summation. Note
that for induction purpose, we assume (31) holds for $q=0$, which implies that
$\sum_{t=i_{1}+1}^{j_{1}-1}p_{t}\cdot\prod_{v=t+1}^{j_{1}-1}(1-p_{v})=1-\prod_{v=i_{1}+1}^{j_{1}-1}(1-p_{v})$.
Then we have

$\displaystyle\sum_{j_{1}=i_{1}+2}^{i_{2}}\frac{p_{j_{1}}}{1-p_{j_{1}}}\cdot\sum_{j_{1}<j_{2}<\dots<j_{q}\leq
i_{2}}\frac{p_{j_{2}}\dots
p_{j_{q}}}{(1-p_{j_{2}})\dots(1-p_{j_{q}})}\cdot\prod_{v=j_{1}}^{i_{2}}(1-p_{v})\cdot\sum_{t=i_{1}+1}^{j_{1}-1}p_{t}\cdot\prod_{v=t+1}^{j_{1}-1}(1-p_{v})$
$\displaystyle=\sum_{j_{1}=i_{1}+2}^{i_{2}}p_{j_{1}}\cdot\sum_{j_{1}<j_{2}<\dots<j_{q}\leq
i_{2}}\frac{p_{j_{2}}\dots
p_{j_{q}}}{(1-p_{j_{2}})\dots(1-p_{j_{q}})}\cdot\prod_{v=j_{1}+1}^{i_{2}}(1-p_{v})\cdot\left(1-\prod_{v=i_{1}+1}^{j_{1}-1}(1-p_{v})\right)$
$\displaystyle=\sum_{j_{1}=i_{1}+1}^{i_{2}}p_{j_{1}}\cdot\sum_{j_{1}<j_{2}<\dots<j_{q}\leq
i_{2}}\frac{p_{j_{2}}\dots
p_{j_{q}}}{(1-p_{j_{2}})\dots(1-p_{j_{q}})}\cdot\prod_{v=j_{1}+1}^{i_{2}}(1-p_{v})\cdot\left(1-\prod_{v=i_{1}+1}^{j_{1}-1}(1-p_{v})\right)$

where the second equality holds by noting that when $j_{1}=i_{1}+1$, we have
$1-\prod_{v=i_{1}+1}^{j_{1}-1}(1-p_{v})=0$. Thus, it holds that

$\displaystyle\sum_{t=i_{1}+1}^{i_{2}}p_{t}\cdot\sum_{t+1\leq
j_{1}<j_{2}<\dots<j_{q}\leq i_{2}}\frac{p_{j_{1}}p_{j_{2}}\dots
p_{j_{q}}}{(1-p_{j_{1}})(1-p_{j_{2}})\dots(1-p_{j_{q}})}\cdot\prod_{v=t+1}^{i_{2}}(1-p_{v})$
$\displaystyle=\sum_{j_{1}=i_{1}+1}^{i_{2}}p_{j_{1}}\cdot\sum_{j_{1}<j_{2}<\dots<j_{q}\leq
i_{2}}\frac{p_{j_{2}}\dots
p_{j_{q}}}{(1-p_{j_{2}})\dots(1-p_{j_{q}})}\cdot\prod_{v=j_{1}+1}^{i_{2}}(1-p_{v})\cdot\left(1-\prod_{v=i_{1}+1}^{j_{1}-1}(1-p_{v})\right)$

Note that for the induction purpose, we assume that (31) holds for $q-1$.
Then, we have that

$\displaystyle\sum_{j_{1}=i_{1}+1}^{i_{2}}p_{j_{1}}\cdot\sum_{j_{1}<j_{2}<\dots<j_{q}\leq
i_{2}}\frac{p_{j_{2}}\dots
p_{j_{q}}}{(1-p_{j_{2}})\dots(1-p_{j_{q}})}\cdot\prod_{v=j_{1}+1}^{i_{2}}(1-p_{v})$
$\displaystyle=\sum_{t=i_{1}+1}^{i_{2}}p_{t}\cdot\sum_{t+1\leq
j_{1}<j_{2}<\dots<j_{q-1}\leq i_{2}}\frac{p_{j_{1}}p_{j_{2}}\dots
p_{j_{q-1}}}{(1-p_{j_{1}})(1-p_{j_{2}})\dots(1-p_{j_{q-1}})}\cdot\prod_{v=t+1}^{i_{2}}(1-p_{v})$
$\displaystyle=1-\sum_{w=0}^{q-1}\sum_{i_{1}+1\leq j_{1}<j_{2}<\dots<j_{w}\leq
i_{2}}\frac{p_{j_{1}}p_{j_{2}}\dots
p_{j_{w}}}{(1-p_{j_{1}})(1-p_{j_{2}})\dots(1-p_{j_{w}})}\cdot\prod_{v=i_{1}+1}^{i_{2}}(1-p_{v})$

where the second equality holds from replacing the index $j_{l+1}$ with
$j_{l}$ for $l=2,\dots,q$ and replace the index $j_{1}$ with $t$. Also, note
that

$\displaystyle\sum_{j_{1}=i_{1}+1}^{i_{2}}p_{j_{1}}\cdot\sum_{j_{1}<j_{2}<\dots<j_{q}\leq
i_{2}}\frac{p_{j_{2}}\dots
p_{j_{q}}}{(1-p_{j_{2}})\dots(1-p_{j_{q}})}\cdot\prod_{v=j_{1}+1}^{i_{2}}(1-p_{v})\cdot\prod_{v=i_{1}+1}^{j_{1}-1}(1-p_{v})$
$\displaystyle=\sum_{i_{1}+1\leq j_{1}<j_{2}<\dots<j_{q}\leq
i_{2}}\frac{p_{j_{1}}p_{j_{2}}\dots
p_{j_{q}}}{(1-p_{j_{1}})(1-p_{j_{2}})\dots(1-p_{j_{q}})}\cdot\prod_{v=i_{1}+1}^{i_{2}}(1-p_{v})$

Thus, we have that

$\displaystyle\sum_{t=i_{1}+1}^{i_{2}}p_{t}\cdot\sum_{t+1\leq
j_{1}<j_{2}<\dots<j_{q}\leq i_{2}}\frac{p_{j_{1}}p_{j_{2}}\dots
p_{j_{q}}}{(1-p_{j_{1}})(1-p_{j_{2}})\dots(1-p_{j_{q}})}\cdot\prod_{v=t+1}^{i_{2}}(1-p_{v})$
$\displaystyle=\sum_{j_{1}=i_{1}+1}^{i_{2}}p_{j_{1}}\cdot\sum_{j_{1}<j_{2}<\dots<j_{q}\leq
i_{2}}\frac{p_{j_{2}}\dots
p_{j_{q}}}{(1-p_{j_{2}})\dots(1-p_{j_{q}})}\cdot\prod_{v=j_{1}+1}^{i_{2}}(1-p_{v})\cdot\left(1-\prod_{v=i_{1}+1}^{j_{1}-1}(1-p_{v})\right)$
$\displaystyle=1-\sum_{w=0}^{q}\sum_{i_{1}+1\leq j_{1}<j_{2}<\dots<j_{w}\leq
i_{2}}\frac{p_{j_{1}}p_{j_{2}}\dots
p_{j_{w}}}{(1-p_{j_{1}})(1-p_{j_{2}})\dots(1-p_{j_{w}})}\cdot\prod_{v=i_{1}+1}^{i_{2}}(1-p_{v})$

which completes our proof by induction on $q$. ∎

Combining Lemma 12 and Lemma 13, we draw the following conclusion.

###### Lemma 14

For each $l=1,2,\dots,k$ and each $t=1,2,\dots,T$, we have that
$\beta^{*}_{l,t}\geq 0$ and $\xi^{*}_{t}\geq 0$.

###### Proof.

Proof: Note that from definition, $\beta^{*}_{l,t}\geq 0$ for each $l$ and
$t$. We then show the non-negativity of $\xi^{*}_{t}$ for each $t$. Note that
Lemma 12 shows that $\delta_{l_{1},l_{2}}\geq\delta_{l_{1}+1,l_{2}}$ for each
$l_{2}=1,2,\dots,k$ and each $l_{1}=1,2,\dots,l_{2}-1$. It only remains to
show the non-negativity of the term $1-\sum_{w=0}^{q}B_{l,w}$, which can be
directly established by Lemma 13. Specifically, by replacing $i_{1}$ with
$t_{l}$ and $i_{2}$ with $t_{l+1}$ in (31), we have
$1-\sum_{w=0}^{q}B_{l,w}=\sum_{t=t_{l}+1}^{t_{l+1}}p_{t}\cdot A_{l,q}(t)\geq
0$. ∎

From the definition of $\\{\beta^{*}_{l,t},\xi^{*}_{t}\\}$, condition (28)
holds obviously. We then prove that condition (29) is satisfied.

###### Lemma 15

For each $l=1,2,\dots,k$ and each $t\geq t_{l}+1$, it holds that

$\beta^{*}_{l,t}+\sum_{j=t+1}^{T}p_{j}\cdot(\beta^{*}_{l,j}-\beta^{*}_{l+1,j})=\xi^{*}_{t}$

where we denote $\beta^{*}_{k+1,t}=0$ for notation simplicity.

###### Proof.

Proof: When $l=k$, from definition, we have $\beta^{*}_{l,j}=0$ for each
$j\leq t_{l+1}=T-1$ and $\beta^{*}_{l,T}=R$, thus the lemma holds directly.
When $t=T$, it is also direct to show from definition that the lemma holds. We
then focus on the case where $l\leq k-1$ and $t\leq T-1$.

For a fixed $l\leq k-1$ and a fixed $t_{l}+1\leq t\leq T-1$, we denote an
index $l_{1}\geq l$ such that $t_{l_{1}}+1\leq t\leq t_{l_{1}+1}$. We then
consider the following cases separately based on the value of $l_{1}$.

(i). When $l_{1}\leq k-1$, we have that

$\beta^{*}_{l,t}=p_{T}R\cdot\sum_{w=l}^{l_{1}-1}\delta_{w,l_{1}}\cdot
A_{l_{1},w-l}(t)$ (32)

also, for any $t+1\leq j\leq t_{l_{1}+1}$, we have that

$\beta^{*}_{l,j}-\beta^{*}_{l+1,j}=p_{T}R\cdot\sum_{w=l}^{l_{1}-1}(\delta_{w,l_{1}}-\delta_{w+1,l_{1}})\cdot
A_{l_{1},w-l}(j)$

which implies that

$\sum_{j=t+1}^{t_{l_{1}+1}}p_{j}\cdot(\beta^{*}_{l,j}-\beta^{*}_{l+1,j})=p_{T}R\cdot\sum_{w=l}^{l_{1}-1}(\delta_{w,l_{1}}-\delta_{w+1,l_{1}})\cdot\sum_{j=t+1}^{t_{l_{1}+1}}p_{j}\cdot
A_{l_{1},w-l}(j)$

Note that from (31), it holds that $\sum_{j=t+1}^{t_{l_{1}+1}}p_{j}\cdot
A_{l_{1},w-l}(j)=1-\sum_{q=0}^{w-l}A_{l_{1},q}(t)$. Thus, we have that

$\displaystyle\sum_{j=t+1}^{t_{l_{1}+1}}p_{j}\cdot(\beta^{*}_{l,j}-\beta^{*}_{l+1,j})$
$\displaystyle=p_{T}R\cdot\sum_{w=l}^{l_{1}-1}(\delta_{w,l_{1}}-\delta_{w+1,l_{1}})\cdot\left(1-\sum_{q=0}^{w-l}A_{l_{1},q}(t)\right)$
(33)
$\displaystyle=p_{T}R\cdot\delta_{l,l_{1}}-p_{T}R\cdot\sum_{w=l}^{l_{1}-1}\delta_{w,l_{1}}\cdot
A_{l_{1},w-l}(t)$

where the last equality holds from $\delta_{l_{1},l_{1}}=0$. Similarly, for
any $l_{2}\geq l_{1}+1$ and any $t_{l_{2}}+1\leq j\leq t_{l_{2}+1}$, we have
that

$\beta^{*}_{l,j}-\beta^{*}_{l+1,j}=p_{T}R\cdot\sum_{w=l}^{l_{2}-1}(\delta_{w,l_{2}}-\delta_{w+1,l_{2}})\cdot
A_{l_{2},w-l}(j)$

which implies that

$\sum_{j=t_{l_{2}}+1}^{t_{l_{2}+1}}p_{j}\cdot(\beta^{*}_{l,j}-\beta^{*}_{l+1,j})=p_{T}R\cdot\sum_{w=l}^{l_{2}-1}(\delta_{w,l_{2}}-\delta_{w+1,l_{2}})\cdot\sum_{j=t_{l_{2}}+1}^{t_{l_{2}+1}}p_{j}\cdot
A_{l_{2},w-l}(j)$

Note that from Lemma 13, we have that
$\sum_{j=t_{l_{2}}+1}^{t_{l_{2}+1}}p_{j}\cdot
A_{l_{2},w-l}(j)=1-\sum_{q=0}^{w-l}B_{l_{2},q}$. Thus, we have that

$\displaystyle\sum_{j=t_{l_{1}+1}+1}^{t_{k+1}}p_{j}\cdot(\beta^{*}_{l,j}-\beta^{*}_{l+1,j})$
$\displaystyle=\sum_{l_{2}=l_{1}+1}^{k}\sum_{j=t_{l_{2}}+1}^{t_{l_{2}+1}}p_{j}\cdot(\beta^{*}_{l,j}-\beta^{*}_{l+1,j})$
(34)
$\displaystyle=\sum_{l_{2}=l_{1}+1}^{k}p_{T}R\cdot\sum_{w=l}^{l_{2}-1}(\delta_{w,l_{2}}-\delta_{w+1,l_{2}})\cdot(1-\sum_{q=0}^{w-l}B_{l_{2},q})$
$\displaystyle=p_{T}R\cdot\sum_{l_{2}=l_{1}+1}^{k}\sum_{w=l+1}^{l_{2}}(\delta_{w-1,l_{2}}-\delta_{w,l_{2}})\cdot(1-\sum_{q=0}^{w-l-1}B_{l_{2},q})$

Combining (32), (33) and (34), we have that

$\beta^{*}_{l,t}+\sum_{j=t+1}^{T}p_{j}\cdot(\beta^{*}_{l,j}-\beta^{*}_{l+1,j})=p_{T}R\cdot\delta_{l,l_{1}}+p_{T}R\cdot\sum_{l_{2}=l_{1}+1}^{k}\sum_{w=l+1}^{l_{2}}(\delta_{w-1,l_{2}}-\delta_{w,l_{2}})\cdot(1-\sum_{q=0}^{w-l-1}B_{l_{2},q})$
(35)

Note that

$\xi^{*}_{t}=p_{T}R\cdot\sum_{l_{2}=l_{1}+1}^{k}\sum_{w=l_{1}+1}^{l_{2}}(\delta_{w-1,l_{2}}-\delta_{w,l_{2}})\cdot(1-\sum_{q=0}^{w-l_{1}-1}B_{l_{2},q})$

in order to show
$\beta^{*}_{l,t}+\sum_{j=t+1}^{T}p_{j}\cdot(\beta^{*}_{l,j}-\beta^{*}_{l+1,j})=\xi^{*}_{t}$,
it is enough to prove that

$\delta_{l,l_{1}}+\sum_{l_{2}=l_{1}+1}^{k}\sum_{w=l+1}^{l_{2}}(\delta_{w-1,l_{2}}-\delta_{w,l_{2}})\cdot(1-\sum_{q=0}^{w-l-1}B_{l_{2},q})=\sum_{l_{2}=l_{1}+1}^{k}\sum_{w=l_{1}+1}^{l_{2}}(\delta_{w-1,l_{2}}-\delta_{w,l_{2}})\cdot(1-\sum_{q=0}^{w-l_{1}-1}B_{l_{2},q})$
(36)

Further note that

$\displaystyle\sum_{l_{2}=l_{1}+1}^{k}\sum_{w=l+1}^{l_{2}}(\delta_{w-1,l_{2}}-\delta_{w,l_{2}})\cdot(1-\sum_{q=0}^{w-l-1}B_{l_{2},q})$
$\displaystyle=$
$\displaystyle\sum_{l_{2}=l_{1}+1}^{k}\sum_{w=l+1}^{l_{2}}(\delta_{w-1,l_{2}}-\delta_{w,l_{2}})-\sum_{l_{2}=l_{1}+1}^{k}\sum_{w=l+1}^{l_{2}}\sum_{q=0}^{w-l-1}B_{l_{2},q}\cdot(\delta_{w-1,l_{2}}-\delta_{w,l_{2}})$
$\displaystyle=$
$\displaystyle\sum_{l_{2}=l_{1}+1}^{k}\delta_{l,l_{2}}-\sum_{l_{2}=l_{1}+1}^{k}\sum_{q=0}^{l_{2}-l-1}B_{l_{2},q}\cdot\delta_{q+l,l_{2}}$

and similarly, note that

$\sum_{l_{2}=l_{1}+1}^{k}\sum_{w=l_{1}+1}^{l_{2}}(\delta_{w-1,l_{2}}-\delta_{w,l_{2}})\cdot(1-\sum_{q=0}^{w-l_{1}-1}B_{l_{2},q})=\sum_{l_{2}=l_{1}+1}^{k}\delta_{l_{1},l_{2}}-\sum_{l_{2}=l_{1}+1}^{k}\sum_{q=0}^{l_{2}-l_{1}-1}B_{l_{2},q}\cdot\delta_{q+l_{1},l_{2}}$

in order to prove (36), it is enough to show that

$\sum_{l_{2}=l_{1}}^{k}\delta_{l,l_{2}}-\sum_{l_{2}=l_{1}+1}^{k}\sum_{q=0}^{l_{2}-l-1}B_{l_{2},q}\cdot\delta_{q+l,l_{2}}=\sum_{l_{2}=l_{1}+1}^{k}\delta_{l_{1},l_{2}}-\sum_{l_{2}=l_{1}+1}^{k}\sum_{q=0}^{l_{2}-l_{1}-1}B_{l_{2},q}\cdot\delta_{q+l_{1},l_{2}}$
(37)

When $l_{1}=l$, it is direct to check that (37) holds. The proof of (37) when
$l_{1}\geq l+1$ is relegated to Lemma 16. Thus, we prove that when $l_{1}\leq
k-1$, it holds that
$\beta^{*}_{l,t}+\sum_{j=t+1}^{T}p_{j}\cdot(\beta^{*}_{l,j}-\beta^{*}_{l+1,j})=\xi^{*}_{t}$.

(ii). When $l_{1}=k$, we have that

$\beta^{*}_{l,t}=p_{T}R\cdot\sum_{w=l}^{k-1}A_{k,w-l}(t)$

and for each $t+1\leq j\leq T-1$, it holds that

$\beta^{*}_{l,j}-\beta^{*}_{l+1,j}=p_{T}R\cdot\left(\sum_{w=l}^{k-1}A_{k,w-l}(j)-\sum_{w=l+1}^{k-1}A_{k,w-l-1}(j)\right)=p_{T}R\cdot
A_{k,k-1-l}(j)$

Note that $\beta^{*}_{l,T}=\beta^{*}_{l+1,T}=R$, we have

$\beta^{*}_{l,t}+\sum_{j=t+1}^{T-1}p_{j}\cdot(\beta^{*}_{l,j}-\beta^{*}_{l+1,j})=p_{T}R\cdot\left(\sum_{w=l}^{k-1}A_{k,w-l}(t)+\sum_{j=t+1}^{T-1}p_{j}\cdot
A_{k,k-1-l}(j)\right)$

Note that from (31), it holds that $\sum_{j=t+1}^{T-1}p_{j}\cdot
A_{k,k-1-l}(j)=1-\sum_{q=0}^{k-1-l}A_{k,q}(t)$. Thus, we have that

$\beta^{*}_{l,t}+\sum_{j=t+1}^{T-1}p_{j}\cdot(\beta^{*}_{l,j}-\beta^{*}_{l+1,j})=p_{T}R=\xi^{*}_{t}$

which completes our proof. ∎

###### Lemma 16

For each $l=1,2,\dots,k-1$ and each $l_{1}=l,l+1,\dots,k-1$, it holds that

$\sum_{l_{2}=l_{1}}^{k}\delta_{l,l_{2}}-\sum_{l_{2}=l_{1}+1}^{k}\sum_{q=0}^{l_{2}-l-1}B_{l_{2},q}\cdot\delta_{q+l,l_{2}}=\sum_{l_{2}=l_{1}+1}^{k}\delta_{l_{1},l_{2}}-\sum_{l_{2}=l_{1}+1}^{k}\sum_{q=0}^{l_{2}-l_{1}-1}B_{l_{2},q}\cdot\delta_{q+l_{1},l_{2}}$
(38)

###### Proof.

Proof: We now prove (38) by induction on $l$ from $l=k-1$ to $l=1$. When
$l=k-1$, we must have $l_{1}=k-1=l$, then (38) holds obviously. Suppose that
there exists a $1\leq l^{\prime}\leq k-2$ such that for any $l$ satisfying
$l^{\prime}+1\leq l\leq k-1$, (38) holds for each $l_{1}$ such that $l\leq
l_{1}\leq k-1$, then we consider the case when $l=l^{\prime}$. For this case,
we again use induction on $l_{1}$ from $l_{1}=k-1$ to
$l_{1}=l+1=l^{\prime}+1$. When $l_{1}=k-1$, we have that

$\sum_{l_{2}=l_{1}}^{k}\delta_{l,l_{2}}-\sum_{l_{2}=l_{1}+1}^{k}\sum_{q=0}^{l_{2}-l-1}B_{l_{2},q}\cdot\delta_{q+l,l_{2}}=\delta_{l,k-1}+\delta_{l,k}-\sum_{q=0}^{k-l-1}B_{k,q}\cdot\delta_{q+l,k}$

and

$\sum_{l_{2}=l_{1}+1}^{k}\delta_{l_{1},l_{2}}-\sum_{l_{2}=l_{1}+1}^{k}\sum_{q=0}^{l_{2}-l_{1}-1}B_{l_{2},q}\cdot\delta_{q+l_{1},l_{2}}=\delta_{k-1,k}-B_{k,0}\cdot\delta_{k-1,k}$

Further note that from definition, $\delta_{v,k}=1$ for each $v\leq k-1$ and
$\delta_{l,k-1}=\sum_{w_{0}=l+1}^{k-1}B_{k,k-w_{0}}=\sum_{q=1}^{k-l-1}B_{k,q}$,
it is obvious that (38) holds when $l_{1}=k-1$. Now suppose that (38) holds
for $l_{1}+1$ (we assume $l_{1}\geq l+1$ since when $l_{1}=l$, it is direct
from definition that (38) holds), we consider the case for $l_{1}$. Note that

$\text{LHS\leavevmode\nobreak\ of\leavevmode\nobreak\
}\eqref{007}=\delta_{l,l_{1}}-\sum_{q=0}^{l_{1}-l}B_{l_{1}+1,q}\cdot\delta_{q+l,l_{1}+1}+\sum_{l_{2}=l_{1}+1}^{k}\delta_{l,l_{2}}-\sum_{l_{2}=l_{1}+2}^{k}\sum_{q=0}^{l_{2}-l-1}B_{l_{2},q}\cdot\delta_{q+l,l_{2}}$

and

$\text{RHS\leavevmode\nobreak\ of\leavevmode\nobreak\
}\eqref{007}=\delta_{l_{1},l_{1}+1}-\sum_{l_{2}=l_{1}+1}^{k}B_{l_{2},l_{2}-l_{1}-1}\cdot\delta_{l_{2}-1,l_{2}}+\sum_{l_{2}=l_{1}+2}^{k}\delta_{l_{1},l_{2}}-\sum_{l_{2}=l_{1}+2}^{k}\sum_{q=0}^{l_{2}-l_{1}-2}B_{l_{2},q}\cdot\delta_{q+l_{1},l_{2}}$

Since we suppose for induction that (38) holds for $l_{1}+1$, we have that

$\eqref{007}\text{\leavevmode\nobreak\ holds\leavevmode\nobreak\
for\leavevmode\nobreak\
}(l,l_{1})\Leftrightarrow\delta_{l,l_{1}}-\sum_{q=0}^{l_{1}-l}B_{l_{1}+1,q}\cdot\delta_{q+l,l_{1}+1}=\delta_{l_{1},l_{1}+1}-\sum_{l_{2}=l_{1}+1}^{k}B_{l_{2},l_{2}-l_{1}-1}\cdot\delta_{l_{2}-1,l_{2}}$

Further note that we have supposed for induction that (38) holds for
$(l+1,l_{1})$, which implies

$\delta_{l+1,l_{1}}-\sum_{q=0}^{l_{1}-l-1}B_{l_{1}+1,q}\cdot\delta_{q+l+1,l_{1}+1}=\delta_{l_{1},l_{1}+1}-\sum_{l_{2}=l_{1}+1}^{k}B_{l_{2},l_{2}-l_{1}-1}\cdot\delta_{l_{2}-1,l_{2}}$

Thus, it holds that

$\eqref{007}\text{\leavevmode\nobreak\ holds\leavevmode\nobreak\
for\leavevmode\nobreak\
}(l,l_{1})\Leftrightarrow\delta_{l,l_{1}}-\delta_{l+1,l_{1}}=\sum_{q=0}^{l_{1}-l}B_{l_{1}+1,q}\cdot(\delta_{q+l,l_{1}+1}-\delta_{q+l+1,l_{1}+1})$

Finally, from definition, we have

$\delta_{l,l_{1}}-\delta_{l+1,l_{1}}=\sum_{w_{1}=l+1}^{l_{1}+1}\sum_{w_{2}=w_{1}}^{l_{1}+2}\dots\sum_{w_{k-1-l_{1}}=w_{k-2-l_{1}}}^{k-1}B_{l_{1}+1,w_{1}-l-1}\cdot
B_{l_{1}+2,w_{2}-w_{1}}\dots B_{k-1,w_{k-1-l_{1}}-w_{k-2-l_{1}}}\cdot
B_{k,k-w_{k-1-l_{1}}}$

and

$\delta_{q+l,l_{1}+1}-\delta_{q+l+1,l_{1}+1}=\sum_{w_{2}=q+l+1}^{l_{1}+2}\dots\sum_{w_{k-1-l_{1}}=w_{k-2-l_{1}}}^{k-1}B_{l_{1}+2,w_{2}-q-l-1}\dots
B_{k-1,w_{k-1-l_{1}}-w_{k-2-l_{1}}}\cdot B_{k,k-w_{k-1-l_{1}}}$

which implies that

$\delta_{l,l_{1}}-\delta_{l+1,l_{1}}=\sum_{q=0}^{l_{1}-l}B_{l_{1}+1,q}\cdot(\delta_{q+l,l_{1}+1}-\delta_{q+l+1,l_{1}+1})$
(39)

Thus, from induction, we prove that (38) holds for each $l_{1}\geq l+1$. Note
that (38) holds obviously for $l_{1}=l$, (38) holds for each $l_{1}\geq l$.
From the induction on $l$, we know that (38) holds for each $1\leq l\leq k-1$
and each $l\leq l_{1}\leq k-1$, which completes our proof. ∎

Finally, we only need to prove feasibility of
$\\{\beta^{*}_{l,t},\xi^{*}_{t}\\}$ in the following lemma.

###### Lemma 17

For each $l=1,2,\dots,k$ and each $t=1,2,\dots,t_{l}$, it holds that

$\beta^{*}_{l,t}+\sum_{j=t+1}^{T}p_{j}\cdot(\beta^{*}_{l,j}-\beta^{*}_{l+1,j})\geq\xi^{*}_{t}$

where we denote $\beta^{*}_{k+1,t}=0$ for notation simplicity.

###### Proof.

Proof: Note that from Lemma 12, we have
$\delta_{w,l_{2}}\geq\delta_{w+1,l_{2}}$, which implies that
$\beta^{*}_{l,j}\geq\beta^{*}_{l+1,j}$ for each $l$ and $j$. Thus, we have
that for each $t=1,2,\dots,t_{l}$, it holds that

$\beta^{*}_{l,t}+\sum_{j=t+1}^{T}p_{j}\cdot(\beta^{*}_{l,j}-\beta^{*}_{l+1,j})\geq\beta^{*}_{l,t_{l}+1}+\sum_{j=t_{l}+2}^{T}p_{j}\cdot(\beta^{*}_{l,j}-\beta^{*}_{l+1,j})$

Further note that Lemma 15 implies that

$\beta^{*}_{l,t_{l}+1}+\sum_{j=t_{l}+2}^{n}p_{j}\cdot(\beta^{*}_{l,j}-\beta^{*}_{l+1,j})\geq\xi^{*}_{t_{l}+1}$

Thus, it is enough to show that $\xi^{*}_{i}\leq\xi^{*}_{t_{l}+1}$ for each
$t=1,2,\dots,t_{l}$. From the definition of $\xi^{*}_{i}$, it is enough to
show that $\phi_{l}\leq\phi_{l+1}$. When $l=k-1$, we have
$\phi_{l+1}=\phi_{k}=1$ and $\phi_{l}=\phi_{k-1}=1-B_{k,0}$, which implies
that $\phi_{k-1}\leq\phi_{k}$. When $l\leq k-2$, from definition, we have

$\phi_{l}-\phi_{l+1}=\sum_{q=l+1}^{k}(\delta_{l,q}-\delta_{l+1,q})\cdot(1-B_{q,0})-\sum_{q=l+2}^{k}\sum_{w=l+2}^{q}(\delta_{w-1,q}-\delta_{w,q})\cdot
B_{q,w-l-1}$

Note that in the proof of Lemma 16, we proved (39), then when $k-1\geq q\geq
l+1$, we have

$\delta_{l,q}-\delta_{l+1,q}=\sum_{w=0}^{q-l}B_{q+1,w}\cdot(\delta_{w+l,q+1}-\delta_{w+l+1,q+1})=\sum_{w=l+1}^{q+1}B_{q+1,w-l-1}\cdot(\delta_{w-1,q+1}-\delta_{w,q+1})$

Thus, it holds that

$\displaystyle\phi_{l}-\phi_{l+1}$
$\displaystyle=-\sum_{q=l+1}^{k-1}(\delta_{l,q}-\delta_{l+1,q})\cdot
B_{q,0}+\sum_{q=l+1}^{k-1}\sum_{w=l+1}^{q+1}B_{q+1,w-l-1}\cdot(\delta_{w-1,q+1}-\delta_{w,q+1})$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
-\sum_{q=l+2}^{k}\sum_{w=l+2}^{q}(\delta_{w-1,q}-\delta_{w,q})\cdot
B_{q,w-l-1}$
$\displaystyle=-\sum_{q=l+1}^{k-1}(\delta_{l,q}-\delta_{l+1,q})\cdot
B_{q,0}+\sum_{q=l+1}^{k-1}B_{q+1,0}\cdot(\delta_{l,q+1}-\delta_{l+1,q+1})$
$\displaystyle=-B_{l+1,0}\cdot\delta_{l,l+1}\leq 0$

which completes our proof. ∎

Together, Lemma 14, Lemma 15, and Lemma 17 establish the feasibility of
$\\{\beta^{*}_{l,t},\xi^{*}_{t}\\}$. Then, from the definition of
$\\{\beta^{*}_{l,t},\xi^{*}_{t}\\}$, obviously condition (28) is satisfied and
from Lemma 15, condition (29) is satisfied. Thus, we finish the proof of
Theorem 1.

###  B5 Proof of Lemma 5

###### Proof.

Proof: Since we have $\text{Dual}(\bm{p},k)=\text{Primal}(\bm{p},k)$, it is
enough to consider the primal LP $\text{Primal}(\bm{p},k)$ in (10) and prove
that $\text{Primal}(\bm{p},k)\geq\text{Primal}(\tilde{\bm{p}},k)$. Suppose the
optimal solution of $\text{Primal}(\bm{p},k)$ is denoted as
$\\{\beta^{*}_{l,t},\xi^{*}_{t}\\}$, as constructed in (30), we then construct
a feasible solution $\\{\tilde{\beta}_{l,t},\tilde{\xi}_{t}\\}$ to
$\text{Primal}(\tilde{\bm{p}},k)$ as follows:

$\displaystyle\tilde{\xi}_{t}=\xi^{*}_{t}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \forall 1\leq
t<q,\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
\tilde{\xi}_{q}=\tilde{\xi}_{q+1}=\xi^{*}_{q},\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\tilde{\xi}_{t+1}=\xi^{*}_{t}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \forall q+1\leq t\leq T$
$\displaystyle\tilde{\beta}_{l,t}=\beta^{*}_{l,t}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \forall l=1,\dots,k,\forall 1\leq
t<q$
$\displaystyle\tilde{\beta}_{l,q}=\tilde{\beta}_{l,q+1}=\beta^{*}_{l,q}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \forall l=1,\dots,k$
$\displaystyle\tilde{\beta}_{l,t+1}=\beta^{*}_{l,t}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \forall l=1,\dots,k,\forall q+1\leq
t\leq T$

Note that we have

$\text{Primal}(\bm{p},k)=\sum_{t=1}^{T}p_{t}\cdot\beta^{*}_{1,t}=\sum_{t=1}^{T+1}\tilde{p}_{t}\cdot\tilde{\beta}_{1,t}$

it is enough to prove that $\\{\tilde{\beta}_{l,t},\tilde{\xi}_{t}\\}$ is
feasible to $\text{Primal}(\tilde{\bm{p}},k)$. Obviously, we have
$\\{\tilde{\beta}_{l,t},\tilde{\xi}_{t}\\}$ are non-negative and
$\sum_{t=1}^{T+1}\tilde{p}_{t}\cdot\tilde{\xi}_{t}=\sum_{t=1}^{T}p_{t}\cdot\xi^{*}_{t}=1$,
then we only need to check whether the following constraint is satisfied:

$\tilde{\beta}_{l,t}+\sum_{\tau>t}\tilde{p}_{\tau}\cdot(\tilde{\beta}_{l,\tau}-\tilde{\beta}_{l+1,\tau})-\tilde{\xi}_{t}\geq
0,\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \forall
l=1,\dots,k,\forall t=1,\dots,T+1$ (40)

where we denote $\tilde{\beta}_{k+1,t}=0$ for notation simplicity. Note that
when $t\geq q+1$, we have that

$\tilde{\beta}_{l,t}+\sum_{\tau>t}\tilde{p}_{\tau}\cdot(\tilde{\beta}_{l,\tau}-\tilde{\beta}_{l+1,\tau})-\tilde{\xi}_{t}=\beta^{*}_{l,t}+\sum_{\tau>t}p_{\tau}\cdot(\beta^{*}_{l,\tau}-\beta^{*}_{l+1,\tau})-\xi^{*}_{t}\geq
0,\leavevmode\nobreak\ \leavevmode\nobreak\ \forall l=1,\dots,k$

and when $1\leq t\leq q-1$, we also have

$\tilde{\beta}_{l,t}+\sum_{\tau>t}\tilde{p}_{\tau}\cdot(\tilde{\beta}_{l,\tau}-\tilde{\beta}_{l+1,\tau})-\tilde{\xi}_{t}=\beta^{*}_{l,t}+\sum_{\tau>t}p_{\tau}\cdot(\beta^{*}_{l,\tau}-\beta^{*}_{l+1,\tau})-\xi^{*}_{t}\geq
0,\leavevmode\nobreak\ \leavevmode\nobreak\ \forall l=1,\dots,k$

by noting $\tilde{p}_{q}+\tilde{p}_{q+1}=p_{q}$. Now we consider the case when
$t=q$, then for each $l=1,\dots,k$, we have

$\displaystyle\tilde{\beta}_{l,q}+\sum_{j=q+1}^{T+1}\tilde{p}_{j}\cdot(\tilde{\beta}_{l-1,j}-\tilde{\beta}_{l,j})-\tilde{\xi}_{q}$
$\displaystyle=\tilde{\beta}_{l,q}+\sum_{j=q+2}^{T+1}\tilde{p}_{j}\cdot(\tilde{\beta}_{l-1,j}-\tilde{\beta}_{l,j})-\tilde{\xi}_{q}+\tilde{p}_{q+1}\cdot(\tilde{\beta}_{l-1,q+1}-\tilde{\beta}_{l,q+1})$
$\displaystyle=\beta^{*}_{l,q}+\sum_{j=q+1}^{T}p_{j}\cdot(\beta^{*}_{l-1,j}-\beta^{*}_{l,j})-\xi^{*}_{q}+p_{q}\cdot(1-\sigma)\cdot(\beta^{*}_{l-1,q}-\beta^{*}_{l,q})$
$\displaystyle\geq
p_{q}\cdot(1-\sigma)\cdot(\beta^{*}_{l-1,q}-\beta^{*}_{l,q})$

Thus, it is enough to show that $\beta^{*}_{l-1,q}\geq\beta^{*}_{l,q}$ to
prove feasibility. Note that from Lemma 12, for each $l_{2}=1,2,\dots,k$ and
each $l_{1}=1,2,\dots,l_{2}-1$, we have
$\delta_{l_{1},l_{2}}\geq\delta_{l_{1}+1,l_{2}}$, then, it is direct to show
that $\beta^{*}_{l-1,q}\geq\beta^{*}_{l,q}$ from the construction (30), which
completes our proof. ∎

###  B6 Proof of Proposition 1

###### Proof.

Proof: We consider the following problem instance $\mathcal{H}$. At the
beginning, there are two queries arriving deterministically with a reward $1$.
Then, over the time interval $[0,1]$, there are queries with reward $r_{1}>1$
arriving according to a Poisson process with rate $\lambda$. At last, there is
one query with a reward $\frac{r_{2}}{\epsilon}$ arriving with a probability
$\epsilon$ for some small $\epsilon>0$.

Obviously, since $r_{1}>1$ and $\epsilon$ is set to be small, the prophet will
first serve the last query as long as it arrives, and then serve the queries
with a reward $r_{1}$ as much as possible, and at least serve the first two
queries. Then, we have that

$\mathbb{E}_{\bm{I}\sim\bm{F}}[V^{\text{off}}(\bm{I})]=\hat{V}:=r_{2}+2\cdot\exp(-\lambda)+(r_{1}+1)\cdot\lambda\cdot\exp(-\lambda)+2r_{1}\cdot(1-(\lambda+1)\cdot\exp(-\lambda)+O(\epsilon)$

Moreover, for any online algorithm $\pi$, we consider the following situations
separately based on the number of the first two queries that $\pi$ will serve.
(i). If $\pi$ will always serve the first two queries, then it is obvious that
$\mathbb{E}_{\pi,\bm{I}\sim\bm{F}}[V^{\pi}(\bm{I})]=2$.
(ii). If $\pi$ serves only one of the first two queries, then the optimal way
for $\pi$ to serve the second query will depend on the value of $r_{1}$ and
$r_{2}$. To be more specific, if $r_{1}\geq r_{2}$, then the optimal way is to
serve the query with reward $r_{1}$ as long as it arrives, and if
$r_{1}<r_{2}$, then the optimal way is to reject all the arriving queries with
reward $r_{1}$ and only serve the last query. Thus, it holds that

$\mathbb{E}_{\pi,\bm{I}\sim\bm{F}}[V^{\pi}(\bm{I})]\leq
V(1):=1+\exp(-\lambda)\cdot
r_{2}+(1-\exp(-\lambda))\cdot\max\\{r_{1},r_{2}\\}+O(\epsilon)$

(iii). If $\pi$ rejects all the first two queries, then conditioning on there
are more than one queries with reward $r_{1}$ arriving during the interval
$[0,1]$, the optimal way for $\pi$ is to serve both queries with reward
$r_{1}$ if $r_{1}\geq r_{2}$ and only serve one query with reward $r_{1}$ if
$r_{1}<r_{2}$. Then, it holds that

$\mathbb{E}_{\pi,\bm{I}\sim\bm{F}}[V^{\pi}(\bm{I})]\leq
V(2):=\exp(-\lambda)\cdot
r_{2}+\lambda\cdot\exp(-\lambda)\cdot(r_{1}+r_{2})+(1-(\lambda+1)\cdot\exp(-\lambda)\cdot(r_{1}+\max\\{r_{1},r_{2}\\})$

Thus, we conclude that for any online algorithm $\pi$, it holds that

$\frac{\mathbb{E}_{\pi,\bm{I}\sim\bm{F}}[V^{\pi}(\bm{I})]}{\mathbb{E}_{\bm{I}\sim\bm{F}}[V^{\text{off}}(\bm{I})]}\leq
g(r_{1},r_{2},\lambda):=\frac{\max\\{V(1),V(2),2\\}}{\hat{V}}$

where we can neglect the $O(\epsilon)$ term by letting $\epsilon\rightarrow
0$. In this way, we can focus on the following optimization problem

$\inf_{r_{1}>1,r_{2}>1,\lambda}g(r_{1},r_{2},\lambda)$

to obtain the upper bound of the guarantee of any online algorithm relative to
the prophet’s value. We can numerically solve the above problem and show that
when $r_{1}=r_{2}=1.4119$, $\lambda=1.2319$, the value of
$g(r_{1},r_{2},\lambda)$ reaches its minimum and equals $0.6269$, which
completes our proof. ∎

###  B7 Proof of Theorem 2

###### Proof.

Proof: For each $\bm{p}=(p_{1},\dots,p_{T})$ satisfying
$\sum_{t=1}^{T}p_{t}=k$, since each irrational number can be arbitrarily
approximated by a rational number, we assume without loss of generality that
$p_{t}$ is a rational number for each $t$, i.e., $p_{t}=\frac{n_{t}}{N}$ where
$n_{t}$ is an integer for each $t$ and $N$ is an integer to denote the common
denominator. We first split $p_{1}$ into $\frac{1}{N}$ and $\frac{n_{1}-1}{N}$
to form a new sequence
$\tilde{\bm{p}}=(\frac{1}{N},\frac{n_{1}-1}{N},\frac{n_{2}}{N},\dots,\frac{n_{T}}{N})$.
From Lemma 5, we know
$\text{Dual}(\bm{p},k)\geq\text{Dual}(\tilde{\bm{p}},k)$. We then split
$\frac{n_{1}-1}{N}$ into $\frac{1}{N}$ and $\frac{n_{1}-2}{N}$ and so on. In
this way, we split $p_{1}$ into $n_{1}$ copies of $\frac{1}{N}$ to form a new
sequence
$\tilde{\bm{p}}=(\frac{1}{N},\dots,\frac{1}{N},\frac{n_{2}}{N},\dots,\frac{n_{T}}{N})$
and Lemma 5 guarantees that
$\text{LP}(\bm{p},k)\geq\text{LP}(\tilde{\bm{p}},k)$. We repeat the above
operation for each $t$. Finally, we form a new sequence of arrival
probabilities, denoted as
$\bm{p}^{N}=(\frac{1}{N},\dots,\frac{1}{N})\in\mathbb{R}^{Nk}$, and we have
$\text{Dual}(\bm{p},k)\geq\text{Dual}(\bm{p}^{N},k)$.

From the above argument, we know that for each $\bm{p}=(p_{1},\dots,p_{T})$
satisfying $\sum_{t=1}^{T}p_{t}=k$, there exists an integer $N$ such that
$\text{Dual}(\bm{p},k)\geq\text{Dual}(\bm{p}^{N},k)$, which implies that

$\inf_{\bm{p}:\sum_{t}p_{t}=k}\leavevmode\nobreak\
\text{Dual}(\bm{p},k)=\liminf_{N\rightarrow\infty}\text{Dual}(\bm{p}^{N},k)$

Thus, it is enough to consider
$\liminf_{N\rightarrow\infty}\text{Dual}(\bm{p}^{N},k)$.

We denote
$\tilde{\bm{y}}_{\theta}(t)=(\tilde{y}_{1,\theta}(t),\dots,\tilde{y}_{k,\theta}(t))$.
We define a function
$\bm{f}_{\theta}(\cdot)=(f_{1,\theta}(\cdot),\dots,f_{k,\theta}(\cdot))$,
where we denote $\tilde{y}_{0,\theta}(t)=1$ and for each $l=1,\dots,k-1$

$f_{l,\theta}(\tilde{y}_{1,\theta},\dots,\tilde{y}_{k,\theta},t)=\left\\{\begin{aligned}
&0,\leavevmode\nobreak\ \leavevmode\nobreak\ &&\text{if\leavevmode\nobreak\
}\tilde{y}_{l-1,\theta}(t)\leq 1-\theta\\\
&\tilde{y}_{l-1,\theta}(t)-(1-\theta),\leavevmode\nobreak\
\leavevmode\nobreak\ &&\text{if\leavevmode\nobreak\
}\tilde{y}_{l,\theta}(t)\leq 1-\theta\leq\tilde{y}_{l-1,\theta}(t)\\\
&\tilde{y}_{l-1,\theta}(t)-\tilde{y}_{l,\theta}(t),\leavevmode\nobreak\
\leavevmode\nobreak\ &&\text{if\leavevmode\nobreak\
}\tilde{y}_{l,\theta}(t)\geq 1-\theta\\\ \end{aligned}\right.$

and

$f_{k,\theta}(\tilde{y}_{1,\theta},\dots,\tilde{y}_{k,\theta},t)=\left\\{\begin{aligned}
&0,\leavevmode\nobreak\ \leavevmode\nobreak\ &&\text{if\leavevmode\nobreak\
}\tilde{y}_{k-1,\theta}(t)\leq 1-\theta\\\
&\tilde{y}_{k-1,\theta}(t)-(1-\theta),\leavevmode\nobreak\
\leavevmode\nobreak\ &&\text{if\leavevmode\nobreak\
}\tilde{y}_{k-1,\theta}(t)\geq 1-\theta\\\ \end{aligned}\right.$

Moreover, variable $(\tilde{y}_{1},\dots,\tilde{y}_{k},t)$ belongs to the
feasible set of the function $f_{l,\theta}(\cdot)$ if and only if $y_{v-1}\geq
y_{v}$ for $v=1,\dots,k-1$. Then, for each $\theta\in[0,1]$, the function
$\tilde{\bm{y}}_{\theta}(t)$ in Definition 4 should be the solution to the
following ordinary differential equation (ODE):

$\frac{d\tilde{\bm{y}}_{\theta}(t)}{dt}=\bm{f}_{\theta}(\tilde{\bm{y}}_{\theta},t)\text{\leavevmode\nobreak\
\leavevmode\nobreak\ for\leavevmode\nobreak\
}t\in[0,k]\text{\leavevmode\nobreak\ with\leavevmode\nobreak\
starting\leavevmode\nobreak\ point\leavevmode\nobreak\
}\tilde{\bm{y}}_{\theta}(0)=(0,\dots,0)$ (41)

For each integer $N$ and $\bm{p}^{N}=(\frac{1}{N},\dots,\frac{1}{N})$ where
$\|\bm{p}^{N}\|_{1}=k$, for any fixed $\theta\in[0,1]$, we denote
$\\{x_{l,t}(\theta,N)\\}$ as the variables constructed in Definition 3 under
the arrival probabilities $\bm{p}^{N}$, where $l=1,\dots,k$ and
$t=1,\dots,Nk$. We further denote
$y_{l,\theta,N}(\frac{t}{N})=\sum_{\tau=1}^{t}x_{l,\tau}(\theta,N)$ and denote
$\bm{y}_{\theta,N}(\cdot)=(y_{1,\theta,N}(\cdot),\dots,y_{k,\theta,N}(\cdot))$.
It is direct to check that for each $t=1,\dots,Nk$, it holds that

$(\bm{y}_{\theta,N}(\frac{t}{N})-\bm{y}_{\theta,N}(\frac{t-1}{N}))/(\frac{1}{N})=\bm{f}_{\theta}(\bm{y}_{\theta,N},\frac{t-1}{N})$

Thus, $\\{\bm{y}_{\theta,N}(t)\\}_{\forall t\in[0,k]}$ can be viewed as the
result obtained from applying Euler’s method (Butcher and Goodwin, 2008) to
solve ODE (41), where there are $Nk$ discrete points uniformly distributed
within $[0,k]$. Note that for each $\theta\in[0,1]$, the function
$\bm{f}_{\theta}(\cdot)$ is Lipschitz continuous with a Lipschitz constant $2$
under infinity norm. Moreover, it is direct to note that for each
$\theta\in[0,1]$ and each $t\in[0,k]$, it holds that
$\|\bm{f}_{\theta}(\tilde{\bm{y}},t)\|_{\infty}\leq 1$. Then, for each
$\theta\in[0,1]$, each $t_{1},t_{2}\in[0,k]$ and each $l=1,\dots,k$, we have

$|\frac{d\tilde{y}_{l,\theta}(t_{1})}{dt}-\frac{d\tilde{y}_{l,\theta}(t_{2})}{dt}|\leq
2\cdot\|\tilde{\bm{y}}_{\theta}(t_{1})-\tilde{\bm{y}}_{\theta}(t_{2})\|_{\infty}\leq
2\cdot|t_{1}-t_{2}|$

Thus, we know that

$|\tilde{y}_{l,\theta}(t_{1})-\tilde{y}_{l,\theta}(t_{2})-\frac{d\tilde{y}_{l,\theta}(t_{2})}{dt}\cdot(t_{1}-t_{2})|\leq
2\cdot(t_{1}-t_{2})^{2}$

We can apply the global truncation error of Euler’s method (Theorem 212A
(Butcher and Goodwin, 2008)) to show that $\bm{y}_{\theta,N}(k)$ converges to
$\tilde{\bm{y}}_{\theta}(k)$ when $N\rightarrow\infty$. Specifically, we have

$\|\bm{y}_{\theta,N}(k)-\tilde{\bm{y}}_{\theta}(k)\|_{\infty}\leq(\exp(2k)-1)\cdot\frac{1}{N},\leavevmode\nobreak\
\leavevmode\nobreak\ \forall\theta\in[0,1]$ (42)

Now we define $Y(\theta)=\tilde{y}_{k,\theta}(k)$ as a function of
$\theta\in[0,1]$ and for each $N$, we define $Y_{N}(\theta)=y_{k,\theta,N}(k)$
as a function of $\theta\in[0,1]$. (42) implies that the function sequence
$\\{Y_{N}\\}_{\forall N}$ converges uniformly to the function $Y$ when
$N\rightarrow\infty$. Note that for each $N$, the function $Y_{N}(\theta)$ is
continuously monotone increasing with $\theta$ due to Lemma 10, then from
uniform limit theorem, $Y(\theta)$ must be a continuously monotone increasing
function over $\theta$. Thus, the equation $Y(\theta)=1-\theta$ has a unique
solution, denoted as $\gamma^{*}_{k}$. For each $N$, we denote
$\theta^{*}_{N}$ as the unique solution to the equation
$Y_{N}(\theta)=1-\theta$, where we have that
$\theta^{*}_{N}=\text{Dual}(\bm{p}^{N},k)$. Since $\\{Y_{N}\\}_{\forall N}$
converges uniformly to the function $Y$, it must hold that
$\gamma^{*}_{k}=\lim_{N\rightarrow\infty}\theta^{*}_{N}$, which completes our
proof. ∎

##  9 Proofs in Section 5

###  C1 Proof of Proposition 2

###### Proof.

Proof: The proof is the same as the proof of Proposition 3.1 in Jiang et al.
(2022).

Consider a problem setup $\hat{\mathcal{H}}$ with 4 queries and

$(\hat{r}_{1},p_{1},d_{1})=(r,1,\epsilon),\leavevmode\nobreak\
\leavevmode\nobreak\
(\hat{r}_{2},p_{2},d_{2})=(\hat{r}_{3},p_{3},d_{3})=(r,\frac{1-2\epsilon}{1+2\epsilon},\frac{1}{2}+\epsilon),\leavevmode\nobreak\
\leavevmode\nobreak\ (\hat{r}_{4},p_{4},d_{4})=(r/\epsilon,\epsilon,1)$

for $r>0$ and some $\epsilon>0$. Obviously, if the policy $\pi$ only serves
queries with a size greater than 1/2, then the expected total reward is
$V^{\pi}_{L}=r+O(\epsilon)$. If the policy $\pi$ only serves queries with a
size no greater than 1/2, then the expected total reward is $V^{\pi}_{S}=r$.
Thus, the expected total reward of the policy $\pi$ is

$V^{\pi}=\max\\{V^{\pi}_{L},V^{\pi}_{S}\\}=r+O(\epsilon)$

Moreover, it is direct to see that $\sum_{t=1}^{4}p_{t}\cdot d_{t}=1$, then,
we have $\text{UP}(\hat{\mathcal{H}})=4r$. Thus, the guarantee of $\pi$ is
upper bounded by $1/4+O(\epsilon)$, which converges to $1/4$ as
$\epsilon\rightarrow 0$. ∎

###  C2 Proof of Theorem 3

###### Proof.

Proof: It is enough to prove that the threshold policy $\pi_{\gamma}$ is
feasible when $\gamma=\frac{1}{3+e^{-2}}$. In the remaining proof, we set
$\gamma=\frac{1}{3+e^{-2}}$. For a fixed $t$, and any $a$ and $b$, denote
$\mu_{t,\gamma}(a,b]=P(a<\tilde{X}_{t,\gamma}\leq b)$ assuming
$\tilde{X}_{t,\gamma}$ is well-defined, it is enough to prove that
$\mu_{t,\gamma}(0,1]\leq 1-\gamma$ thus the random variable
$\tilde{X}_{t+1,\gamma}$ is well-defined.

We define $U_{t}(s)=\mu_{t,\gamma}(0,s]$ for any $s\in(0,1]$. Note that by
definition, we have
$\mathbb{E}[\tilde{X}_{t,\gamma}]=\gamma\cdot\sum_{\tau=1}^{t}p_{\tau}\cdot
d_{\tau}\leq\gamma$. From integration by parts, we have that

$\gamma\geq\mathbb{E}[\tilde{X}_{t,\gamma}]=\int_{s=0}^{1}sdU_{t}(s)=U_{t}(1)-\int_{s=0}^{1}U_{t}(s)ds$
(43)

We then bound the term $\int_{s=0}^{1}U_{t}(s)ds$. Now suppose
$U_{t}(1)\geq\gamma$, otherwise $U_{t}(1)<\gamma$ immediately implies that
$U_{t}(1)\leq 1-\gamma$, which proves our result. Then there must exists a
constant $u^{*}\in(0,1)$ such that $\gamma\cdot
u^{*}-\gamma\cdot\ln(u^{*})=U_{t}(1)$. We further define

$s^{*}=\left\\{\begin{aligned} &\min\\{s\in(0,1/2]:U_{t}(s)\geq\gamma\cdot
u^{*}\\},\leavevmode\nobreak\ \leavevmode\nobreak\
&\text{if\leavevmode\nobreak\ }U_{t}(\frac{1}{2})\geq\gamma\cdot u^{*}\\\
&\frac{1}{2},&\leavevmode\nobreak\ \leavevmode\nobreak\
\text{if\leavevmode\nobreak\ }U_{t}(\frac{1}{2})<\gamma\cdot
u^{*}\end{aligned}\right.$

Denote $U_{t}(s^{*}-)=\lim_{s\rightarrow s^{*}}U_{t}(s)$, it holds that

$\displaystyle\int_{s=0}^{1}U_{t}(s)ds$
$\displaystyle=\int_{s=0}^{s^{*}-}U_{t}(s)ds+\int_{s=s^{*}}^{1/2}U_{t}(s)ds+\int_{s=1/2}^{1-s^{*}}U_{t}(s)ds+\int_{s=1-s^{*}}^{1}U_{t}(s)ds$
$\displaystyle\leq
s^{*}\cdot(U_{t}(s^{*}-)+U_{t}(1))+\int_{s=s^{*}}^{1/2}U_{t}(s)ds+\int_{s=1/2}^{1-s^{*}}U_{t}(s)ds$
$\displaystyle\leq s^{*}\cdot(2\gamma
u^{*}-\gamma\cdot\ln(u^{*}))+\int_{s=s^{*}}^{1/2}(2U_{t}(s)-\gamma\cdot\ln(\frac{U_{t}(s)}{\gamma}))ds$

where the last inequality holds by noting that $U_{t}(s^{*}-)\leq\gamma u^{*}$
and for any $s\in[s^{*},1/2]$, from Lemma 6, we have
$\frac{U_{t}(s)}{\gamma}\leq\exp(-\frac{U_{t}(1-s)-U_{t}(s)}{\gamma})$, which
implies that
$\frac{U_{t}(1-s)}{\gamma}\leq\frac{U_{t}(s)}{\gamma}-\ln(\frac{U_{t}(s)}{\gamma})$.
Note that for any $s\in[s^{*},1/2]$, we have that $\gamma\cdot u^{*}\leq
U_{t}(s^{*})\leq U_{t}(s)\leq U_{t}(1/2)\leq\gamma$, where
$U_{t}(1/2)\leq\gamma$ holds directly from Lemma 6. Further note that the
function $2x-\gamma\cdot\ln(x/\gamma)$ is a convex function, thus is quasi
convex. Then, for any $s\in[s^{*},1/2]$, it holds that

$2U_{t}(s)-\gamma\cdot\ln(\frac{U_{t}(s)}{\gamma})\leq\max\\{2\gamma
u^{*}-\gamma\cdot\ln(u^{*}),2\gamma\\}$

Thus, we have that

$\displaystyle\int_{s=0}^{1}U_{t}(s)ds$ $\displaystyle\leq s^{*}\cdot(2\gamma
u^{*}-\gamma\cdot\ln(u^{*}))+(1/2-s^{*})\cdot\max\\{2\gamma
u^{*}-\gamma\cdot\ln(u^{*}),2\gamma\\}$

If $2\gamma u^{*}-\gamma\cdot\ln(u^{*})\leq 2\gamma$, we have
$\int_{s=0}^{1}U_{t}(s)ds\leq 2s^{*}\gamma+\gamma-2s^{*}\gamma=\gamma$. From
(43), we have that $U_{t}(1)\leq 2\gamma<1-\gamma$.
If $2\gamma u^{*}-\gamma\cdot\ln(u^{*})>2\gamma$, we have
$\int_{s=0}^{1}U_{t}(s)ds\leq\gamma u^{*}-\frac{\gamma}{2}\cdot\ln(u^{*})$.
From (43) and the definition of $u^{*}$, we have that

$U_{t}(1)=\gamma u^{*}-\gamma\cdot\ln(u^{*})\leq\gamma+\gamma
u^{*}-\frac{\gamma}{2}\cdot\ln(u^{*})$

which implies that $u^{*}\geq\exp(-2)$. Note that the function $x-\ln(x)$ is
non-increasing on $(0,1)$, we have
$U_{t}(1)\leq\gamma\cdot\exp(-2)+2\gamma=1-\gamma$, which completes our proof.
∎

###  C3 Proof of Theorem 4

###### Proof.

Proof: It is enough to consider a special case of our problem where the size
of each query is deterministic. Then the proof is the same as the proof of
Theorem 3.1 in Jiang et al. (2022).

We denote by $d_{t}$ the size of query $t$. Then, we have
$\bm{p}=(p_{1},\dots,p_{t})$ and $\bm{D}=(d_{1},\dots,d_{T})$. Due to Lemma 3,
it is enough to construct a $\bm{p}$ and $\bm{D}$ satisfying
$\sum_{t=1}^{T}p_{t}\cdot d_{t}\leq 1$, such that
$\text{Dual}(\bm{p},\bm{D})\leq\frac{1}{3+e^{-2}}$. For each $\epsilon>0$, we
consider the following $\bm{p}$ and $\bm{D}$:

$\displaystyle(p_{1},d_{1})=(1,\epsilon),\leavevmode\nobreak\
\leavevmode\nobreak\
(p_{t},d_{t})=(\frac{1-2\epsilon}{(T-2)(\frac{1}{2}+\epsilon)},\frac{1}{2}+\epsilon)\text{\leavevmode\nobreak\
\leavevmode\nobreak\ for\leavevmode\nobreak\ all\leavevmode\nobreak\ }2\leq
t\leq T-1\text{\leavevmode\nobreak\ \leavevmode\nobreak\
and\leavevmode\nobreak\ \leavevmode\nobreak\ }(p_{T},d_{T})=(\epsilon,1)$

It is direct to check that $\sum_{t=1}^{T}p_{t}\cdot d_{t}=1$. Now denote by
$\\{\theta^{*},\alpha^{*}_{t}(c_{t})\\}$ the optimal solution to
$\text{Dual}(\bm{p},\bm{D})$ (we omit $d_{t}$ in the expression
$\alpha(d_{t},c_{t})$ since now $d_{t}$ takes a single value). We further
denote $\mu_{t}=\sum_{c_{t}:d_{t}\leq c_{t}<1}\alpha^{*}_{t}(c_{t})$ for each
$2\leq t\leq T-1$. Then, constraint (8a) implies that

$\alpha^{*}_{t}(1)\geq\theta^{*}\cdot p_{t}-\mu_{t},\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \forall 2\leq t\leq T-1$

Thus, we have that

$\theta^{*}\cdot p_{T}\leq\alpha^{*}_{T}(1)\leq
p_{T}\cdot(1-\alpha^{*}_{1}(1)-\sum_{t=2}^{T-1}\alpha^{*}_{t}(1))\Rightarrow\theta^{*}\cdot(1+\sum_{t=2}^{T-1}p_{t})\leq
1-\alpha^{*}_{1}(1)+\sum_{t=2}^{T-1}\mu_{t}$

We then consider the term $\sum_{t=2}^{T-1}\mu_{t}$ to upper bound
$\theta^{*}$. Note that since $d_{t}>1/2$ for all $2\leq t\leq T-1$,
constraint (8b) implies that

$\alpha^{*}_{t}(c_{t})\leq
p_{t}\cdot(\alpha_{1}^{*}(c_{t}+d_{1})-\sum_{\tau=2}^{t-1}\alpha^{*}_{\tau}(c_{t})),\leavevmode\nobreak\
\leavevmode\nobreak\ \forall d_{t}\leq c_{t}<1$

Further note that $\alpha_{1}^{*}(c)=0$ when $c<1$, we must have that
$\alpha^{*}_{t}(c_{t})=0$ when $c_{t}\neq 1-d_{1}$. Then, we have
$\mu_{t}=\alpha^{*}_{t}(1-d_{1})$ and

$\mu_{t}\leq
p_{t}\cdot(\alpha_{1}^{*}(1)-\sum_{\tau=2}^{t-1}\mu_{\tau}),\leavevmode\nobreak\
\leavevmode\nobreak\ \forall 2\leq t\leq T-1$

We then inductively show that for any $2\leq t\leq T-1$, we have

$\sum_{\tau=2}^{t}\mu_{t}\leq(1-\prod_{\tau=2}^{t}(1-p_{\tau}))\cdot\alpha^{*}_{1}(1)$
(44)

When $t=2$, (44) holds obviously. Now suppose that (44) holds for $t-1$, we
have

$\displaystyle\sum_{\tau=2}^{t}\mu_{t}$
$\displaystyle=\sum_{\tau=2}^{t-1}\mu_{\tau}+\mu_{t}\leq\alpha^{*}_{1}(1)\cdot
p_{t}+(1-p_{t})\cdot\sum_{\tau=2}^{t-1}\mu_{\tau}\leq\alpha^{*}_{1}(1)\cdot
p_{t}+(1-p_{t})\cdot(1-\prod_{\tau=2}^{t-1}(1-p_{\tau}))\cdot\alpha^{*}_{1}(1)$
$\displaystyle=\alpha^{*}_{1}(1)\cdot(1-\prod_{\tau=2}^{t}(1-p_{\tau}))$

Thus, (44) holds for all $2\leq t\leq T-1$ and we have

$\sum_{t=2}^{T-1}\mu_{t}\leq\alpha^{*}_{1}(1)\cdot(1-\prod_{t=2}^{T-1}(1-p_{t}))=\alpha^{*}_{1}(1)\cdot(1-(1-\frac{1-2\epsilon}{(T-2)(\frac{1}{2}+\epsilon)})^{T-2})\leq\alpha^{*}_{1}(1)\cdot(1-\exp(-2))+O(\epsilon)$

which implies that

$3\theta^{*}+O(\epsilon)=\theta^{*}\cdot(1+\sum_{t=2}^{T-1}p_{t})\leq
1-\alpha^{*}_{1}(1)+\sum_{t=2}^{T-1}\mu_{t}\leq
1-\alpha^{*}_{1}(1)\cdot\exp(-2)+O(\epsilon)$

Moreover, note that constraint (8a) requires
$\alpha^{*}_{1}(1)\geq\theta^{*}$, we have that
$\theta^{*}\leq\frac{1}{3+e^{-2}}+O(\epsilon)$. The proof is finished by
taking $\epsilon\rightarrow 0$. ∎

##  10 Proofs in section 6

###  D1 Proof of Lemma 7

###### Proof.

Proof: We prove (18) by induction on $t$. When $t=0$, since
$\mu_{0,\gamma}(0,b]=0$ for any $0<b\leq 1/2$, (18) holds trivially. Now
suppose that (18) holds for $t-1$, we consider the case for $t$. Denote
$\mathcal{F}_{t}$ as the support of $\tilde{d}_{t}$ and for each
$d_{t}\in\mathcal{F}_{t}$, we denote $\eta_{t,\bm{\gamma}}(d_{t})$ as the
threshold defined in (17). Then we define the following division of
$\mathcal{F}_{t}$:

$\displaystyle\mathcal{F}_{t,1}:=\\{d_{t}\in\mathcal{F}_{t}:\eta_{t,\bm{\gamma}}(d_{t})=0\text{\leavevmode\nobreak\
and\leavevmode\nobreak\ }d_{t}\leq b\\}$
$\displaystyle\mathcal{F}_{t,2}=\\{d_{t}\in\mathcal{F}_{t}:\eta_{t,\bm{\gamma}}(d_{t})=0\text{\leavevmode\nobreak\
and\leavevmode\nobreak\ }b<d_{t}\leq 1-b\\}$
$\displaystyle\mathcal{F}_{t,3}=\\{d_{t}\in\mathcal{F}_{t}:\eta_{t,\bm{\gamma}}(d_{t})>0\text{\leavevmode\nobreak\
and\leavevmode\nobreak\ }d_{t}\leq 1-b\\}$
$\displaystyle\mathcal{F}_{t,4}=\\{d_{t}\in\mathcal{F}_{t}:\eta_{t,\bm{\gamma}}(d_{t})=0\text{\leavevmode\nobreak\
and\leavevmode\nobreak\ }1-b<d_{t}\\}$
$\displaystyle\mathcal{F}_{t,5}=\\{d_{t}\in\mathcal{F}_{t}:\eta_{t,\bm{\gamma}}(d_{t})>0\text{\leavevmode\nobreak\
and\leavevmode\nobreak\ }1-b<d_{t}\\}$

Note that for each $d_{t}\in\mathcal{F}_{t}$, $\eta_{t,\bm{\gamma}}(d_{t})=0$
implies that a measure
$p(d_{t})\cdot(\gamma_{t}-\mu_{t-1,\bm{\gamma}}(0,1-d_{t}])$ of empty sample
paths will be moved to $d_{t}$ due to the inclusion of realization $d_{t}$
when defining $\tilde{X}_{t,\bm{\gamma}}$. More specifically, the movement of
sample paths due to the inclusion of each realization
$d_{t}\in\mathcal{F}_{t}$ can be described as follows:
(i). For each $d_{t}\in\mathcal{F}_{t,1}$, obviously,
$p(d_{t})\cdot(\gamma_{t}-\mu_{t-1,\bm{\gamma}}(0,1-d_{t}])$ measure of sample
paths, which is upper bounded by
$p(d_{t})\cdot(\gamma_{t}-\mu_{t-1,\bm{\gamma}}(0,1-b])$, will be moved from
$0$ to the range $(0,b]$, while $p(d_{t})\cdot\mu_{t-1,\bm{\gamma}}(0,b]$
measure of sample paths will be moved out of the range $(0,b]$. Moreover, at
most $p(d_{t})\cdot\mu_{t-1,\bm{\gamma}}(0,b]$ measure of sample paths will be
moved into the range $(b,1-b]$.
(ii). For each $d_{t}\in\mathcal{F}_{t,2}$,
$p(d_{t})\cdot\mu_{t-1,\bm{\gamma}}(0,b]$ measure of sample paths will be
moved out of the range $(0,b]$. Moreover,
$p(d_{t})\cdot(\gamma_{t}-\mu_{t-1,\bm{\gamma}}(0,1-d_{t}])$ measure of sample
paths, which is upper bounded by
$p(d_{t})\cdot(\gamma_{t}-\mu_{t-1,\bm{\gamma}}(0,b])$, will be moved from $0$
into the range $(b,1-b]$, while at most
$p(d_{t})\cdot\mu_{t-1,\bm{\gamma}}(0,b]$ measure of sample paths will be
moved from $(0,b]$ into $(b,1-b]$. Thus, the measure of new sample path that
is moved into the range $(b,1-b]$ is upper bounded by $\gamma_{t}\cdot
p(d_{t})$.
(iii). For each $d_{t}\in\mathcal{F}_{t,3}$, then at most
$p(d_{t})\cdot\mu_{t-1,\bm{\gamma}}(0,b]$ measure of sample paths is moved out
of the range $(0,b]$, and at most $p(d_{t})\cdot\mu_{t-1,\bm{\gamma}}(0,b]$
measure of sample paths is moved into the range $(b,1-b]$.
(iv). For each $d_{t}\in\mathcal{F}_{t,4}$ or $d_{t}\in\mathcal{F}_{t,5}$,
since $d_{t}>1-b$, obviously, no new sample path will be added to the range
$(b,1-b]$ due to the inclusion of such realization $d_{t}$ when defining
$\tilde{X}_{t,\bm{\gamma}}$, while the measure of the sample paths within the
range $(0,b]$ can only become smaller.
To conclude, denoting

$\hat{p}_{1}=\sum_{d_{t}\in\mathcal{F}_{t,1}}p(d_{t})\text{\leavevmode\nobreak\
\leavevmode\nobreak\ and\leavevmode\nobreak\ \leavevmode\nobreak\
}\hat{p}_{2}=\sum_{d_{t}\in\mathcal{F}_{t,2}}p(d_{t})\text{\leavevmode\nobreak\
\leavevmode\nobreak\ and\leavevmode\nobreak\ \leavevmode\nobreak\
}\hat{p}_{3}=\sum_{d_{t}\in\mathcal{F}_{t,3}}p(d_{t})$

we have that

$\displaystyle\mu_{t,\bm{\gamma}}(0,b]\leq$
$\displaystyle\mu_{t-1,\bm{\gamma}}(0,b]+(\gamma_{t}-\mu_{t-1,\bm{\gamma}}(0,1-b]-\mu_{t-1,\bm{\gamma}}(0,b])\cdot\hat{p}_{1}-\mu_{t-1,\bm{\gamma}}(0,b]\cdot\hat{p}_{2}-\mu_{t-1,\bm{\gamma}}(0,b]\cdot\hat{p}_{3}$
(45)

and

$\mu_{t,\bm{\gamma}}(b,1-b]\leq\mu_{t-1,\bm{\gamma}}(b,1-b]+\mu_{t-1,\bm{\gamma}}(0,b]\cdot\hat{p}_{1}+\gamma_{t}\cdot\hat{p}_{2}+\mu_{t-1,\bm{\gamma}}(0,b]\cdot\hat{p}_{3}$
(46)

Moreover, it holds that $\hat{p}_{1}+\hat{p}_{2}+\hat{p}_{3}\leq 1$. We now
consider the following two cases separately.
Case 1: If $\hat{p}_{1}>0$, then we must have
$\gamma_{t}\geq\mu_{t-1,\bm{\gamma}}(0,1-b]$. Notice that $\hat{p}_{1}\leq
1-\hat{p}_{2}$, from (45), we have

$\displaystyle\mu_{t,\bm{\gamma}}(0,b]$
$\displaystyle\leq\mu_{t-1,\bm{\gamma}}(0,b]+(\gamma_{t}-\mu_{t-1,\bm{\gamma}}(0,1-b])\cdot\hat{p}_{1}-\mu_{t-1,\bm{\gamma}}(0,b])\cdot\hat{p}_{1}-\mu_{t-1,\bm{\gamma}}(0,b]\cdot\hat{p}_{2}-\mu_{t-1,\bm{\gamma}}(0,b]\cdot\hat{p}_{3}$
$\displaystyle\leq\mu_{t-1,\bm{\gamma}}(0,b]+(\gamma_{t}-\mu_{t-1,\bm{\gamma}}(0,1-b])\cdot(1-\hat{p}_{2})-\mu_{t-1,\bm{\gamma}}(0,b])\cdot\hat{p}_{1}-\mu_{t-1,\bm{\gamma}}(0,b]\cdot\hat{p}_{2}-\mu_{t-1,\bm{\gamma}}(0,b]\cdot\hat{p}_{3}$
$\displaystyle=(\gamma_{t}-\mu_{t-1,\bm{\gamma}}(b,1-b])\cdot(1-\hat{p}_{2})-\mu_{t-1,\bm{\gamma}}(0,b])\cdot\hat{p}_{1}-\mu_{t-1,\bm{\gamma}}(0,b]\cdot\hat{p}_{3}$
$\displaystyle\leq(\gamma_{1}-\mu_{t-1,\bm{\gamma}}(b,1-b])\cdot(1-\hat{p}_{2})-\mu_{t-1,\bm{\gamma}}(0,b])\cdot\hat{p}_{1}-\mu_{t-1,\bm{\gamma}}(0,b]\cdot\hat{p}_{3}$
(47)

where the last inequality holds from $\gamma_{1}\geq\gamma_{t}$. Moreover,
from (46), we have that

$\displaystyle\exp(-\frac{1}{\gamma_{1}}\cdot\mu_{t,\bm{\gamma}}(b,1-b])$
$\displaystyle\geq\exp(-\frac{1}{\gamma_{1}}\cdot\mu_{t-1,\bm{\gamma}}(b,1-b]-\frac{\gamma_{t}\hat{p}_{2}}{\gamma_{1}})\cdot\exp(-\frac{1}{\gamma_{1}}\cdot\mu_{t-1,\bm{\gamma}}(0,b]\cdot\hat{p}_{1}-\frac{1}{\gamma_{1}}\cdot\mu_{t-1,\bm{\gamma}}(0,b]\cdot\hat{p}_{3})$
$\displaystyle\geq\exp(-\frac{1}{\gamma_{1}}\cdot\mu_{t-1,\bm{\gamma}}(b,1-b]-\hat{p}_{2})\cdot\exp(-\frac{1}{\gamma_{1}}\cdot\mu_{t-1,\bm{\gamma}}(0,b]\cdot\hat{p}_{1}-\frac{1}{\gamma_{1}}\cdot\mu_{t-1,\bm{\gamma}}(0,b]\cdot\hat{p}_{3})$
$\displaystyle\geq\exp(-\frac{1}{\gamma_{1}}\cdot\mu_{t-1,\bm{\gamma}}(b,1-b]-\hat{p}_{2})\cdot(1-\frac{1}{\gamma_{1}}\cdot\mu_{t-1,\bm{\gamma}}(0,b]\cdot\hat{p}_{1}-\frac{1}{\gamma_{1}}\cdot\mu_{t-1,\bm{\gamma}}(0,b]\cdot\hat{p}_{3})$
$\displaystyle=\exp(-\frac{1}{\gamma_{1}}\cdot\mu_{t-1,\bm{\gamma}}(b,1-b]-\hat{p}_{2})$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
-\exp(-\frac{1}{\gamma_{1}}\cdot\mu_{t-1,\bm{\gamma}}(b,1-b]-\hat{p}_{2})\cdot(\frac{1}{\gamma_{1}}\cdot\mu_{t-1,\bm{\gamma}}(0,b]\cdot\hat{p}_{1}+\frac{1}{\gamma_{1}}\cdot\mu_{t-1,\bm{\gamma}}(0,b]\cdot\hat{p}_{3})$
$\displaystyle\geq\exp(-\frac{1}{\gamma_{1}}\cdot\mu_{t-1,\bm{\gamma}}(b,1-b]-\hat{p}_{2})-\frac{1}{\gamma_{1}}\cdot\mu_{t-1,\bm{\gamma}}(0,b]\cdot\hat{p}_{1}-\frac{1}{\gamma_{1}}\cdot\mu_{t-1,\bm{\gamma}}(0,b]\cdot\hat{p}_{3}$
(48)

where the second inequality holds from $\gamma_{1}\geq\gamma_{t}$, the third
inequality holds from $\exp(-x)\geq 1-x$ for any $x\geq 0$ and the last
inequality holds from $\exp(-x)\leq 1$ for any $x\geq 0$. Further note that

$\exp(-\frac{1}{\gamma_{1}}\cdot\mu_{t-1,\bm{\gamma}}(b,1-b]-\hat{p}_{2})=\exp(-\frac{1}{\gamma_{1}}\cdot\mu_{t-1,\bm{\gamma}}(b,1-b])\cdot\exp(-\hat{p}_{2})\geq(1-\frac{1}{\gamma_{1}}\cdot\mu_{t-1,\bm{\gamma}}(b,1-b])\cdot(1-\hat{p}_{2})$

From (47) and (48), we have

$\displaystyle\exp(-\frac{1}{\gamma_{1}}\cdot\mu_{t,\bm{\gamma}}(b,1-b])$
$\displaystyle\geq(1-\frac{1}{\gamma_{1}}\cdot\mu_{t-1,\bm{\gamma}}(b,1-b])\cdot(1-\hat{p}_{2})-\frac{1}{\gamma_{1}}\cdot\mu_{t-1,\bm{\gamma}}(0,b]\cdot\hat{p}_{1}-\frac{1}{\gamma_{1}}\cdot\mu_{t-1,\bm{\gamma}}(0,b]\cdot\hat{p}_{3}$
$\displaystyle\geq\frac{1}{\gamma_{1}}\cdot\mu_{t,\bm{\gamma}}(0,b]$

Case 2: If $\hat{p}_{1}=0$, then we have

$\mu_{t,\bm{\gamma}}(0,b]\leq\mu_{t-1,\bm{\gamma}}(0,b]-\mu_{t-1,\bm{\gamma}}(0,b]\cdot\hat{p}_{2}-\mu_{t-1,\bm{\gamma}}(0,b]\cdot\hat{p}_{3}$
(49)

and

$\mu_{t,\bm{\gamma}}(b,1-b]\leq\mu_{t-1,\bm{\gamma}}(b,1-b]+\gamma_{t}\cdot\hat{p}_{2}+\mu_{t-1,\bm{\gamma}}(0,b]\cdot\hat{p}_{3}\leq\mu_{t-1,\bm{\gamma}}(b,1-b]+\gamma_{1}\cdot\hat{p}_{2}+\mu_{t-1,\bm{\gamma}}(0,b]\cdot\hat{p}_{3}$

Thus, it holds that

$\displaystyle\exp(-\frac{1}{\gamma_{1}}\cdot\mu_{t,\bm{\gamma}}(b,1-b])$
$\displaystyle\geq\exp(-\frac{1}{\gamma_{1}}\cdot\mu_{t-1,\bm{\gamma}}(b,1-b]-\hat{p}_{2})\cdot\exp(-\frac{1}{\gamma_{1}}\cdot\mu_{t-1,\bm{\gamma}}(0,b]\cdot\hat{p}_{3})$
$\displaystyle\geq\exp(-\frac{1}{\gamma_{1}}\cdot\mu_{t-1,\bm{\gamma}}(b,1-b]-\hat{p}_{2})\cdot(1-\frac{1}{\gamma_{1}}\cdot\mu_{t-1,\bm{\gamma}}(0,b]\cdot\hat{p}_{3})$
$\displaystyle\geq\exp(-\frac{1}{\gamma_{1}}\cdot\mu_{t-1,\bm{\gamma}}(b,1-b]-\hat{p}_{2})-\frac{1}{\gamma_{1}}\cdot\mu_{t-1,\bm{\gamma}}(0,b]\cdot\hat{p}_{3}$
$\displaystyle\geq\exp(-\frac{1}{\gamma_{1}}\cdot\mu_{t-1,\bm{\gamma}}(b,1-b])\cdot(1-\hat{p}_{2})-\frac{1}{\gamma_{1}}\cdot\mu_{t-1,\bm{\gamma}}(0,b]\cdot\hat{p}_{3}$
$\displaystyle\geq\frac{1}{\gamma_{1}}\cdot\mu_{t-1,\bm{\gamma}}(0,b]\cdot(1-\hat{p}_{2})-\frac{1}{\gamma_{1}}\cdot\mu_{t-1,\bm{\gamma}}(0,b]\cdot\hat{p}_{3}$
(50)

where the third inequality holds from $\exp(-a)\leq 1$ for any $a\geq 0$ and
the last inequality holds from induction hypothesis. Our proof is completed
immediately by combining (49) and (50). ∎

###  D2 Proof of Theorem 5

###### Proof.

Proof: For each fixed $t$, we define
$U_{t}(s)=\mu_{t,\bm{\gamma}}(0,s]=P(0<\tilde{X}_{t,\bm{\gamma}}\leq s)$ for
any $s\in(0,1]$. Note that by Algorithm 2, we have
$\mathbb{E}[\tilde{X}_{t,\bm{\gamma}}]=\sum_{\tau=1}^{t}\gamma_{\tau}\cdot\psi_{\tau}$.
From integration by parts, we have that

$\sum_{\tau=1}^{t}\gamma_{\tau}\cdot\psi_{\tau}=\mathbb{E}[\tilde{X}_{t,\bm{\gamma}}]=\int_{s=0}^{1}U_{t}(s)ds=U_{t}(1)-\int_{s=0}^{1}U_{t}(s)ds$
(51)

We then bound the term $\int_{s=0}^{1}U_{t}(s)ds$. If $U_{t}(1)<\gamma_{1}$,
then we immediately have

$P(\tilde{X}_{t,\bm{\gamma}}=0)>1-\gamma_{1}\geq
1-\gamma_{1}-\sum_{\tau=1}^{t}\gamma_{\tau}\cdot\psi_{\tau}$

which proves (19). Thus, in the remaining part of the proof, it is enough for
us to only focus on the case $U_{t}(1)\geq\gamma_{1}$.

If $U_{t}(1)\geq\gamma_{1}$, then there must exists a constant $u^{*}\in(0,1)$
such that

$\gamma_{1}\cdot u^{*}-\gamma_{1}\cdot\ln(u^{*})=U_{t}(1).$

We further define

$s^{*}=\left\\{\begin{aligned} &\min\\{s\in(0,1/2]:U_{t}(s)\geq\gamma_{1}\cdot
u^{*}\\},\leavevmode\nobreak\ \leavevmode\nobreak\
&\text{if\leavevmode\nobreak\ }U_{t}(\frac{1}{2})\geq\gamma_{1}\cdot u^{*}\\\
&\frac{1}{2},&\leavevmode\nobreak\ \leavevmode\nobreak\
\text{if\leavevmode\nobreak\ }U_{t}(\frac{1}{2})<\gamma_{1}\cdot
u^{*}\end{aligned}\right.$

Following the proof of Theorem 3, we can show that

$\displaystyle\int_{s=0}^{1}U_{t}(s)ds$ $\displaystyle\leq
s^{*}\cdot(2\gamma_{1}\cdot
u^{*}-\gamma_{1}\cdot\ln(u^{*}))+(1/2-s^{*})\cdot\max\\{2\gamma_{1}\cdot
u^{*}-\gamma_{1}\cdot\ln(u^{*}),2\gamma_{1}\\}$

We further simplify the above expression separately by comparing the value of
$2\gamma_{1}\cdot u^{*}-\gamma_{1}\cdot\ln(u^{*})$ and $2\gamma_{1}$.
Case 1: If $2\gamma_{1}\cdot u^{*}-\gamma_{1}\cdot\ln(u^{*})\leq 2\gamma_{1}$,
we have $\int_{s=0}^{1}U_{t}(s)ds\leq
2s^{*}\gamma_{1}+\gamma_{1}-2s^{*}\gamma_{1}=\gamma_{1}$. From (51), we have
that

$U_{t}(1)\leq\gamma_{1}+\sum_{\tau=1}^{t}\gamma_{\tau}\cdot\psi_{\tau}$

Case 2: If $2\gamma_{1}\cdot u^{*}-\gamma_{1}\cdot\ln(u^{*})>2\gamma_{1}$, we
have $\int_{s=0}^{1}U_{t}(s)ds\leq\gamma_{1}\cdot
u^{*}-\frac{\gamma_{1}}{2}\cdot\ln(u^{*})$. From (51) and the definition of
$u^{*}$, we have that

$U_{t}(1)=\gamma_{1}\cdot
u^{*}-\gamma_{1}\cdot\ln(u^{*})\leq\sum_{\tau=1}^{t}\gamma_{\tau}\cdot\psi_{\tau}+\gamma_{1}\cdot
u^{*}-\frac{\gamma_{1}}{2}\cdot\ln(u^{*})$

The above inequality implies that

$u^{*}\geq\exp(-\frac{2}{\gamma_{1}}\cdot\sum_{\tau=1}^{t}\gamma_{\tau}\cdot\psi_{\tau})$

Note that the function $x-\ln(x)$ is non-increasing on $(0,1)$, hence we have

$U_{t}(1)\leq
2\cdot\sum_{\tau=1}^{t}\gamma_{\tau}\cdot\psi_{\tau}+\gamma_{1}\cdot\exp(-\frac{2}{\gamma_{1}}\cdot\sum_{\tau=1}^{t}\gamma_{\tau}\cdot\psi_{\tau})$

Combing the above two cases, we conclude that

$U_{t}(1)\leq\max\\{\gamma_{1}+\sum_{\tau=1}^{t}\gamma_{\tau}\cdot\psi_{\tau},\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
2\cdot\sum_{\tau=1}^{t}\gamma_{\tau}\cdot\psi_{\tau}+\gamma_{1}\cdot\exp(-\frac{2}{\gamma_{1}}\cdot\sum_{\tau=1}^{t}\gamma_{\tau}\cdot\psi_{\tau})\\}$

Note that $P(\tilde{X}_{t,\bm{\gamma}}=0)=1-U_{t}(1)$, we conclude that

$P(\tilde{X}_{t,\bm{\gamma}}=0)\geq\min\\{1-\gamma_{1}-\sum_{\tau=1}^{t}\gamma_{\tau}\cdot\psi_{\tau},\leavevmode\nobreak\
\leavevmode\nobreak\
1-2\cdot\sum_{\tau=1}^{t}\gamma_{\tau}\cdot\psi_{\tau}-\gamma_{1}\cdot\exp(-\frac{2}{\gamma_{1}}\cdot\sum_{\tau=1}^{t}\gamma_{\tau}\cdot\psi_{\tau})\\}$

which completes our proof. ∎

###  D3 Proof of Lemma 8

###### Proof.

Proof: Since the function $h_{\gamma_{0}}(\cdot)$ is non-increasing and non-
negative over $[0,1]$, it is direct to see that

$1\geq\hat{\gamma}_{1}\geq\dots\geq\hat{\gamma}_{T}\geq 0$

Note that for each $t=1,\dots,T$, we have

$\int_{\tau=0}^{k_{t}}h_{\gamma_{0}}(\tau)d\tau=\sum_{\tau=1}^{t}\hat{\gamma}_{\tau}\cdot\psi_{\tau}$

and $\gamma_{0}\geq\hat{\gamma}_{1}$. Then, for each $t=1,\dots,T-1$ and each
$\tau\in[k_{t},k_{t+1}]$, it holds that

$h_{\gamma_{0}}(\tau)\leq
1-\gamma_{0}-\int_{\tau^{\prime}=0}^{\tau}h_{\gamma_{0}}(\tau^{\prime})d\tau^{\prime}\leq
1-\gamma_{0}-\int_{\tau^{\prime}=0}^{k_{t}}h_{\gamma_{0}}(\tau^{\prime})d\tau^{\prime}\leq
1-\hat{\gamma}_{1}-\sum_{\tau^{\prime}=1}^{t}\hat{\gamma}_{\tau^{\prime}}\cdot\psi_{\tau^{\prime}}$

which implies that

$\hat{\gamma}_{t+1}\leq
1-\hat{\gamma}_{1}-\sum_{\tau^{\prime}=1}^{t}\hat{\gamma}_{\tau^{\prime}}\cdot\psi_{\tau^{\prime}}$

since $\hat{\gamma}_{t+1}$ is defined as the average of function
$h_{\gamma_{0}}(\cdot)$ over $[k_{t},k_{t+1}]$ in (23).

Similarly, note that the function
$2x+\gamma_{0}\cdot\exp(-\frac{2}{\gamma_{0}}\cdot x)$ is monotone increasing
when $x\geq 0$. Then, for each $t=1,\dots,T-1$ and each
$\tau\in[k_{t},k_{t+1}]$, we have

$\displaystyle h_{\gamma_{0}}(\tau)$ $\displaystyle\leq
1-2\cdot\int_{\tau^{\prime}=0}^{\tau}h_{\gamma_{0}}(\tau^{\prime})d\tau^{\prime}-\gamma_{0}\cdot\exp(-\frac{2}{\gamma_{0}}\cdot\int_{\tau^{\prime}=0}^{\tau}h_{\gamma_{0}}(\tau^{\prime})d\tau^{\prime})$
$\displaystyle\leq
1-2\cdot\int_{\tau^{\prime}=0}^{k_{t}}h_{\gamma_{0}}(\tau^{\prime})d\tau^{\prime}-\gamma_{0}\cdot\exp(-\frac{2}{\gamma_{0}}\cdot\int_{\tau^{\prime}=0}^{k_{t}}h_{\gamma_{0}}(\tau^{\prime})d\tau^{\prime})$
$\displaystyle=1-2\cdot\sum_{\tau^{\prime}=1}^{t}\hat{\gamma}_{\tau^{\prime}}\cdot\psi_{\tau^{\prime}}-\gamma_{0}\cdot\exp(-\frac{2}{\gamma_{0}}\cdot\sum_{\tau^{\prime}=1}^{t}\hat{\gamma}_{\tau^{\prime}}\cdot\psi_{\tau^{\prime}})$

which implies that

$\hat{\gamma}_{t+1}\leq
1-2\cdot\sum_{\tau^{\prime}=1}^{t}\hat{\gamma}_{\tau^{\prime}}\cdot\psi_{\tau^{\prime}}-\gamma_{0}\cdot\exp(-\frac{2}{\gamma_{0}}\cdot\sum_{\tau^{\prime}=1}^{t}\hat{\gamma}_{\tau^{\prime}}\cdot\psi_{\tau^{\prime}})$

since $\hat{\gamma}_{t+1}$ is defined as the average of function
$h_{\gamma_{0}}(\cdot)$ over $[k_{t},k_{t+1}]$ in (23). Thus, we conclude that
$\\{\hat{\gamma}_{t}\\}_{t=1}^{T}$ is a feasible solution to
$\text{OP}(\bm{\psi})$. ∎

###  D4 Proof of Proposition 3

It is enough for us to consider a problem setup $\mathcal{H}$ with $T$
queries, where each query has a deterministic size $\frac{1}{2}+\frac{1}{T}$
and is active with probability $\frac{2}{T}$. It is clear that
$\textbf{UP}(\mathcal{H})=1$. However, any online algorithm $\pi$ can serve at
most one query, given at least one query has arrived. Then, the expected
capacity utilization of any online algorithm $\pi$ is upper bound by

$(\frac{1}{2}+\frac{1}{T})\cdot(1-(1-\frac{2}{T})^{T})=\frac{1-e^{-2}}{2}+O(\frac{1}{T})$

This implies an upper bound $\frac{1-e^{-2}}{2}$ as $T\rightarrow\infty$.