marginparsep has been altered.
topmargin has been altered.
marginparpush has been altered.
The page layout violates the ICML style. Please do not change the page layout,
or include packages like geometry, savetrees, or fullpage, which change it for
you. We’re not able to reliably undo arbitrary changes to the style. Please
remove the offending package(s), or layout-changing commands and try again.

Online Uniform Risk Times Sampling: First Approximation Algorithms, Learning
Augmentation with Full Confidence Interval Integration

Xueqing Liu 1  Kyra Gan 2  Esmaeil Keyvanshokooh 3  Susan Murphy 4

††footnotetext:  1Duke-NUS Medical School 2Cornell Tech 3Texas A&M 4Harvard
University.

###### Abstract

In digital health, the strategy of allocating a limited treatment budget
across available risk times is crucial to reduce user fatigue. This strategy,
however, encounters a significant obstacle due to the unknown actual number of
risk times, a factor not adequately addressed by existing methods lacking
theoretical guarantees. This paper introduces, for the first time, the online
uniform risk times sampling problem within the approximation algorithm
framework. We propose two online approximation algorithms for this problem,
one with and one without learning augmentation, and provide rigorous
theoretical performance guarantees for them using competitive ratio analysis.
We assess the performance of our algorithms using both synthetic experiments
and a real-world case study on HeartSteps mobile applications.

##  1 Introduction

The efficacy of digital health interventions depends not only on the content
of the treatment but also on the timing and frequency of delivery.
Administering interventions at inappropriate or low-risk times, such as when
users are driving or asleep, can significantly increase mental burden and
hinder engagement (Li et al., 2020; Nahum-Shani et al., 2018; Wen et al.,
2017; McConnell et al., 2017; Mann & Robinson, 2009). Here, we define _risk
times_ as times when the patient is susceptible for a negative event, such as
a relapse to smoking. Moreover, existing studies (Heckman et al., 2015;
Klasnja et al., 2008; Dimitrijević et al., 1972) establish a positive
correlation between excessive digital interventions and heightened user
fatigue, suggesting a threshold beyond which intervention effectiveness may be
compromised by excessive frequency. For example, in the Heartsteps V2 study
(Spruijt-Metz et al., 2022), anti-sedentary messages are triggered when
sedentary behavior is detected, and in the Sense2Stop study (Battalio et al.,
2021), reminders for stress management practices are activated in response to
detected stress. Both studies deliberately limit intervention frequency to
address potential user burden and habituation.

A strategy, rooted in the ecological momentary assessment (EMA) literature and
proven effective in mitigating user fatigue, _involves allocating a fixed and
limited budget for treatments delivered to the patient and delivering the
treatment with a uniform distribution across all available risk times_ (e.g.,
Liao et al. 2018; Dennis et al. 2015; Rathbun et al. 2013; Scott et al. 2017a;
b; Shiffman et al. 2008; Stone et al. 2007). Here, the _available risk times_
represent risk times when the patient is available for intervention. This
approach to uniform sampling offers three advantages. First, the definition of
_available risk times_ prevents the delivery of text messages at inappropriate
times, lessening the user’s mental burden. Second, it introduces uncertainty
in treatment delivery timings, effectively reducing user habituation
(Dimitrijević et al., 1972). Third, the non-zero probability of sending
interventions at _any_ available risk time enhances the estimation of causal
effects in various contexts (Liao et al., 2018). However, uniform sampling
across risk times poses a significant challenge because the underlying true
number of available risk times per decision period is _unknown_ (Liao et al.,
2018). That is, the problem is inherently online and stochastic, with
information about the underlying risk level and the availability at each
decision time being sequentially received in real time. We refer to the
resulting problem as the “ _online uniform risk times sampling_ ” problem.

The algorithmic development for this problem is intricately connected to the
domain of online approximation algorithms. Within this field, the
effectiveness of algorithms is commonly assessed using the concept of a
competitive ratio. This metric compares the performance of an online algorithm
to that of an offline clairvoyant benchmark, where we presume the unknown
parameter is revealed to the clairvoyant in advance. Note that, in practical
applications, no online algorithm can attain the same level of performance as
the offline clairvoyant benchmark.

In this paper, we provide the _first_ formulation of the online uniform risk
time sampling problem within the framework of approximation algorithms. We
propose a randomized approximation algorithm that enjoys robust theoretical
guarantees across all problem instances or sample paths. Notably, this marks
the _first_ algorithm with theoretical guarantees for the problem of online
uniform risk times sampling. Although online approximation algorithms may
exhibit conservative behavior, our numerical experiments illustrate that our
algorithm, on average, outperforms the naive benchmark.

Next, we extend our algorithm to the setting where a confidence interval for
the true risk time is provided, potentially through a machine learning (ML)
algorithm. To the best of our knowledge, this is the _first_ learning-
augmented approximation algorithm that integrates the entire confidence
interval rather than a single point estimate. We conduct the competitive ratio
analysis for our proposed learning-augmented approximation algorithm,
demonstrating its consistency in the strong sense—optimal performance is
achieved when the confidence interval width is zero—and robustness—the
learning-augmented algorithm performs no worse than the non-learning augmented
counterpart. We validate our theoretical results with numerical experiments.

The rest of the paper is organized as follows. We first introduce the
formalization of the online uniform risk times sampling problem in Section 2.
We introduce our randomized algorithm without learning augmentation in Section
3. This algorithm is segmented into three distinct cases based on the time
horizon length, with a competitive ratio established for each. In Section 4,
we develop a learning-augmented algorithm that integrates a prediction
interval and offers theoretical justifications for its effectiveness. The
efficacy of these algorithms is initially assessed through synthetic
experiments, followed by their application in practical scenarios, as
presented in Section 5.

###  1.1 Related Work

Uniform Risk Times Sampling  Existing methodologies, predominantly sourced
from the EMA literature, typically address the challenges of self-report
requests via mobile devices, constrained by budget and uniformity
considerations to minimize user burden and accurately reflect user conditions
across diverse contexts (Dennis et al., 2015; Rathbun et al., 2013; Scott et
al., 2017a; b). However, these approaches do not specifically address the
distribution of a limited treatment budget uniformly over available risk
times, especially when the exact count of these times remains unknown. While
Liao et al. (2018) have developed a heuristic algorithm targeting this issue,
its effectiveness heavily relies on the accuracy of predicting the number of
available risk times. Moreover, in the absence of a reliable predictor, these
algorithms lack robust theoretical guarantees. Consequently, there is a
pressing need for a more comprehensive theoretical analysis and understanding
of this problem.

Online Optimization  The development of worst-case algorithms, processing
online inputs across multiple time steps with irreversible decisions, is a key
focus in existing literature (Mehta et al., 2013). Our work particularly
relates to the multi-option ski-rental problem (Zhang et al., 2011; Shin et
al., 2023), where the number of snowy days is unknown. This scenario presents
customers with varied ski rental options, differing in cost and duration. The
primary objective is to minimize costs while ensuring ski availability on each
snowy day. Shin et al. (2023) introduced the first randomized approximation
algorithm for the multi-option ski rental problem, achieving an
$e$-competitive ratio. In their algorithm, a random variable $B$ is introduced
as a proxy for the unknown true horizon $T$. Initially, $B$ is set to
$\alpha$, following a density function $1/\alpha$ within $[1,e)$. The
algorithm iteratively solves an optimization problem to identify an optimal
set of rental options within budget $B$, maximizing day coverage. Customers
sequentially utilize the options until depletion, at which point $B$ is
increased by a factor of $e$, and the process is repeated. Our study builds
upon the foundational work of Shin et al. (2023), introducing a novel
randomized algorithm tailored to the non-learning augmented online uniform
risk times sampling problem.

Learning-Augmented Online Algorithms  Many online algorithms now incorporate
ML predictions about future behaviors to enhance their worst-case performance
guarantees, as demonstrated in recent studies (Purohit et al., 2018; Bamas et
al., 2020; Wei & Zhang, 2020; Jin & Ma, 2022). Typically, these algorithms are
accompanied by a confidence level linked to the ML predictions. When this
confidence level is high, the algorithm’s performance aligns closely with
these predictions; conversely, the algorithm’s performance does not fall below
the established worst-case guarantee. We note that when the quality of the
point estimate is poor, most existing algorithms do not guarantee that the
learning-augmented algorithm will perform better than the non-learning
counterpart (Bamas et al., 2020). Notably, in practice, prediction intervals
are often generated instead of point estimates (Shafer & Vovk, 2008). Our work
presents the first integration of these prediction intervals into online
algorithms, enabling our proposed algorithms to surpass the performance of
their non-learning counterparts, even in cases where the prediction interval
is wide.

##  2 Problem Framework

In the context of digital interventions, we define the online uniform risk
times sampling problem as presented by Liao et al. (2018). Let $T$ denote the
total number of decision points within a decision period, such as a day in the
context of digital interventions. At each time $t$, the algorithm observes the
patient’s current risk level $R_{t}$ and the intervention availability
indicator $I_{t}\in\\{0,1\\}$,111For example, if patients are driving or
sleeping at time $t$, they are not available for intervention at $t$.
utilizing sensor data collected from wearable devices. The risk level $R_{t}$
can take $K+1$ possible values, where $R_{t}=0$ indicates not at risk and
$R_{t}=k\in\\{1,\cdots,K\\}$ indicates the arrival of risk level $k$ at time
$t$.222For example, the higher the risk level, the more likely the patient
will experience a negative event, such as relapse to smoking. The algorithm is
equipped with two actions $A_{t}\in\\{0,1\\}$ to take at any given time $t$,
where $A_{t}=0$ implies no treatment, and $A_{t}=1$ represents sending a
treatment that is thought to be effective. The distributions of intervention
availabilities and risk levels are allowed to change _arbitrarily_ across
decision periods. We allow risk level distribution to change across decision
periods because we anticipate that the treatment will reduce subsequent risk.

Now, within each decision period (e.g., within each day), we solve a new
online uniform risk times sampling problem. At each risk level $k$, let
$\tau_{k}^{*}$ be the _unknown_ _true_ number of available decision times,
defined as $\tau_{k}^{*}=\sum_{t=1}^{T}\mathbbm{1}_{\\{R_{t}=k,I_{t}=1\\}}$.
We define $p_{k,i_{k}}\in(0,1)$ to be the treatment probability at risk level
$k\in[K]$ at time $i_{k}\in[\tau_{k}^{*}]$ when treatment is feasible. Note
that the treatment probabilities are indexed by $i_{k}$ instead of $t$,
representing the $i_{k}$-th time when the patient is at risk level $k$ and
available for treatment. We preclude the possibility that $p_{k,i_{k}}=0$ or
$p_{k,i_{k}}=1$ to facilitate after-study inference Boruvka et al. (2018);
Zhou et al. (2023); Kallus & Zhou (2022).

The algorithm is provided with a _soft_ budget of $b_{k}$, representing the
total _expected_ number of interventions allowed to be delivered at risk level
$k$ within each decision period. We assume $\tau_{k}^{*}>b_{k}$ for technical
convenience, and as evident in practice Liao et al. (2018). Then at each
decision time $t$, if the patient is available for intervention (i.e.,
$I_{t}=1$), the algorithm observes the patient’s current risk level $R_{t}=k$
and decides the intervention probability $p_{k,i_{k}}$. If $I_{t}=0$, no
treatment may be given. As evident in prior work (see e.g., Liao et al. 2018;
Dennis et al. 2015; Rathbun et al. 2013; Scott et al. 2017a; b; Shiffman et
al. 2008; Stone et al. 2007), for every risk level $k\in[K]$, the objectives
of the online uniform risk times sampling problem are to 1) assign the
intervention probabilities $\\{p_{k,i_{k}}\\}_{i_{k}\in[\tau_{k}^{*}]}$ as
uniform as possible across _available_ risk times at level $k$, and 2)
maximize the sum of intervention probabilities across available risk times
while adhering to the budget constraint $b_{k}$.

It is important to note that $\tau_{k}^{*}$ is stochastic and is revealed
_only_ at the end of the horizon $T$, corresponding to the last decision time
in the decision period. _Without additional information on $\tau_{k}^{*}$_,
the two objectives compete with each other. A naive solution to fulfill the
first objective is to set $p_{k,i_{k}}=b_{k}/T$ for each risk level $k$,
which, however, fails to maximize the sum of intervention probabilities.
Conversely, if we set $p_{k,i_{k}}$ to be a large value and keep it constant,
there is a risk of depleting the budget before the end of the horizon, thus
failing to achieve the uniformity objective. Therefore, the optimality of the
two objectives cannot be simultaneously achieved in the absence of additional
information on $\tau_{k}^{*}$. Liao et al. (2018) provided a heuristic
algorithm for online uniform risk times sampling in the presence of a point
estimate of $\tau_{k}^{*}$. The algorithm’s performance is significantly
influenced by the accuracy of this forecast.

In scenarios where a precise prediction of $\tau_{k}^{*}$ is available, we
expect the algorithm to perform near optimally. However, such accuracy is not
always attainable. In instances lacking reliable predictions, an algorithm
that maintains a robust worst-case guarantee is indispensable. Addressing this
need, we introduce our algorithms designed for scenarios both with and without
learning augmentation, detailed in Sections 3 and 4, respectively.

###  2.1 Optimization Framework: Balancing Objectives

Without additional information on $\tau_{k}^{*}$, achieving the uniformity
objective is impossible. Therefore, rather than setting uniformity as the
primary objective in our optimization problem, we introduce it as a penalty
term. This approach facilitates the assessment of various approximation
algorithms, allowing us to evaluate their overall performance, including the
achievement of uniformity, by directly comparing their objective function
values.

For every risk level $k\in[K]$, we aim to find a sequence of treatment
probability assignments $\\{p_{k,i_{k}}\\}_{i_{k}\in[\tau_{k}^{*}]}$ that
achieves the following two objectives:

  1. 1.

Maximizes the sum of treatment probabilities across available risk times,
subject to the “soft” budget $b_{k}$;

  2. 2.

Penalizes changes in treatment probabilities within each risk level.

Formally, for each risk level $k\in[K]$, we define the following optimization
problem:

$\displaystyle\max\sum_{i_{k}=1}^{\tau_{k}^{*}}p_{k,i_{k}}$
$\displaystyle-\frac{1}{\tau_{k}^{*}}\ln\left(\frac{\max_{i_{k}\in[\tau_{k}^{*}]}p_{k,i_{k}}}{\min_{i_{k}\in[\tau_{k}^{*}]}p_{k,i_{k}}}\right)$
$\displaystyle\text{s.t. }\mathbb{E}\Bigg{[}\sum_{i_{k}=1}^{\tau_{k}^{*}}$
$\displaystyle p_{k,i_{k}}\Bigg{]}\leq b_{k}$ $\displaystyle p_{k,i_{k}}$
$\displaystyle\in(0,1)\quad\forall i_{k}\in[\tau_{k}^{*}],$ (1)

where the expectation in the budget constraint is taken over the randomness in
the algorithm. This budget constraint is “soft” in the sense that if we have
multiple decision periods (which is the case in digital health), we should
satisfy the budget constraint in expectation.

We note that in Problem (2.1), the penalty term for the uniformity objective
is represented by:

$\frac{1}{\tau_{k}^{*}}\ln\left(\frac{\max_{i_{k}\in[\tau_{k}^{*}]}p_{k,i_{k}}}{\min_{i_{k}\in[\tau_{k}^{*}]}p_{k,i_{k}}}\right).$
(2)

The penalty term (2) is inspired by the entropy change concept from
thermodynamics Smith (1950). It has several nice properties: a) it equals to 0
if and only if $\\{p_{k,i_{k}}\\}_{i_{k}\in[\tau_{k}^{*}]}$ are identical, b)
it increases with the maximum difference in
$\\{p_{k,i_{k}}\\}_{i_{k}\in[\tau_{k}^{*}]}$, and c) it tends towards infinity
as the value of $p_{k,i_{k}}$ approaches to zero, penalizing scenarios where
the expected budget is depleted before the horizon ends.

###  2.2 Offline Clairvoyant and Competitive Ratio

In the _offline clairvoyant_ benchmark, the clairvoyant possesses knowledge of
$\tau_{k}^{*}$ for all $k\in[K]$. When provided with these values, the optimal
solution of Problem (2.1) is to set $p_{k,i_{k}}=b_{k}/\tau_{k}^{*}$ for each
risk level $k\in[K]$. Let $\text{OPT}(\tau_{k}^{*})$ represent the optimal
value of the objective function,

$\sum_{i=1}^{\tau_{k}^{*}}p_{k,i_{k}}-\frac{1}{\tau_{k}^{*}}\ln\left(\frac{\max_{i_{k}\in[\tau_{k}^{*}]}p_{k,i_{k}}}{\min_{i_{k}\in[\tau_{k}^{*}]}p_{k,i_{k}}}\right),$

in Problem (2.1) within the clairvoyant benchmark. Then, $\forall
k\in[K],\text{OPT}(\tau_{k}^{*})=b_{k}$. It is important to highlight that the
offline clairvoyant benchmark serves as an upper bound on the best achievable
performance for any _online_ algorithm without knowledge of
$\\{\tau_{k}^{*}\\}_{k\in[K]}$. In practice, no online algorithm can attain
$\text{OPT}(\tau_{k}^{*})$.

Let $\text{SOL}_{k}$ be the objective value of Problem (2.1) achieved by an
_online_ algorithm at risk level $k$, we say that

######  Definition 2.1 ($\gamma$-competitive).

An algorithm is $\gamma$-competitive if
$\mathbb{E}[\text{SOL}_{k}]\geq\gamma\cdot\text{OPT}(\tau_{k}^{*})$ for all
$k\in[K]$.

The key difficulty in solving Problem (2.1) in the online setting arises due
to the unknown nature of $\\{\tau_{k}^{*}\\}_{k\in[K]}$. Inspired by the
randomized algorithm proposed by Shin et al. (2023), we introduce the first
approximation algorithm for the online uniform risk times sampling problem.

###  2.3 With Learning Augmentation

In the _learning-augmented_ problem setting, we are additionally given
prediction intervals $\\{[L_{k},U_{k}]\\}_{k\in[K]}$, each containing the
unknown _true_ $\tau_{k}^{*}$. Here, we assume $\tau_{k}^{*}$ is contained
within the prediction interval for simplicity, with our result generalizing to
the cases where the prediction interval contains $\tau_{k}^{*}$ with high
probability. We measure the performance of the learning-augmented algorithm by
the standard consistency-robustness analysis. Specifically, an algorithm is
said to be $\lambda$-consistent if it achieves
$\mathbb{E}[\text{SOL}_{k}]\geq\lambda\cdot\text{OPT}(\tau_{k}^{*})$ when the
prediction is perfect, i.e., when $L_{k}=U_{k}$, indicating a zero-length
interval. Conversely, we say an algorithm is $\rho$-robust if it satisfies
$\mathbb{E}[\text{SOL}_{k}]\geq\rho\cdot\text{OPT}(\tau_{k}^{*})$ regardless
of the width of the prediction interval $[L_{k},U_{k}]$ (e.g., the prediction
interval might very well be $[b_{k},T]$). In Section 4, we establish that our
proposed learning-augmented algorithm is $1$-consistent, achieving the optimal
solution when the confidence interval width is zero, and the competitive ratio
of our learning-augmented algorithm is no worse than that of the non-learning
augmented counterpart.

##  3 Randomized Algorithm

Algorithm 1 Randomized Online Algorithm

1: Input: $T$, $\\{b_{k}\\}_{k=1}^{K}$

2: Initialize: $\\{i_{k}=0\\}_{k=1}^{K}$, $\\{j_{k}=1\\}_{k=1}^{K}$, we sample
$\alpha\in[b_{k},b_{k}e]$ from a distribution with p.d.f.
$f(\alpha)=1/\alpha$, and initialize $\\{\tilde{\tau}_{k}=\alpha\\}_{k=1}^{K}$

3: for $t=1,...,T$ do

4: On each iteration $t$, a new risk level $R_{t}=k$ and intervention
indicator, $I_{t}$, arrive.

5: if $I_{t}=1$ then

6: Update $i_{k}=i_{k}+1$

7: else

8: No intervention and skip to the next iteration.

9: end if

10: Given $i_{k}$, $b_{k}$, $\tilde{\tau}_{k}$, and $T$, we calculate:

11:
$\mathrm{Int}(\tilde{\tau}_{k})=\left\\{\begin{array}[]{ll}\lfloor\tilde{\tau}_{k}\rfloor&w.p.\quad\lceil\tilde{\tau}_{k}\rceil-\tilde{\tau}_{k}\\\
\lceil\tilde{\tau}_{k}\rceil&w.p.\quad\tilde{\tau}_{k}-\lfloor\tilde{\tau}_{k}\rfloor\end{array}\right.$

12: if $T\leq b_{k}e$ then

13: Update parameters and set $p_{k,i_{k}}$ using Subrtn. 1

14: else if $b_{k}e<T\leq b_{k}e^{2}$ then

15: Update parameters and set $p_{k,i_{k}}$ using Subrtn. 2

16: else

17: Update parameters and set $p_{k,i_{k}}$ using Subrtn. 3

18: end if

19: Deliver treatment with probability $p_{k,i_{k}}$

20: end for

In this section, we introduce our randomized algorithm, Algorithm 1, designed
for the online uniform risk times sampling without learning augmentation. This
algorithm was inspired by the randomized algorithm proposed by Shin et al.
(2023), originally devised for the _multi-option ski rental_ problem (see
detailed description in Section 1.1). Our proposed algorithm differs in the
following ways:

  * •

In the multi-option ski rental problem, there is a single decision period, and
thus there is no upper bound on the length of the horizon. In contrast, in our
problem, the decision periods are repeated over time, and each decision period
has the same fixed length $T$.

  * •

The randomness in Shin et al. (2023) is introduced through an artificial
variable “budget”, acting as a proxy for the number of snow days. Whereas in
our problem, the randomness is introduced directly through $\tau_{k}^{*}$.
Moreover, we have an explicit budget constraint that must be satisfied.

The proposed algorithm, Algorithm 1, provides a feasible solution to Problem
(2.1). At its core, our algorithm assigns the treatment probabilities in a
monotonically non-increasing fashion over time. To address different decision
period horizons relative to the size of the budget $b_{k}$, we designed
specialized approximation algorithms for three possible scenarios: 1) $T\leq
b_{k}e$ (Subroutine 1), 2) $b_{k}e<T\leq b_{k}e^{2}$ (Subroutine 2), and 3)
$T>b_{k}e^{2}$ (Subroutine 3).

We maintain a running “guess” of $\tau_{k}^{*}$, denoted by
$\tilde{\tau}_{k}$. We initialize $\tilde{\tau}_{k}$ to be $\alpha$, where
$\alpha\sim[b_{k},b_{k}\cdot e]$ with density $1/\alpha$, and $e$ represents
the Euler’s number. If the current _available_ time for risk level $k$ is
within our running guess $\tilde{\tau}_{k}$, then we do not change the current
treatment assignment probability. Otherwise, we update $\tilde{\tau}_{k}$ as
$\tilde{\tau}_{k}=\tilde{\tau}_{k}e$ and update the treatment probability
according to Algorithm 1, depending on the length of the horizon $T$ relative
to $b_{k}$.

Subroutine 1 ($i_{k}$, $b_{k}$, $\tilde{\tau}_{k}$, $T$,
$\mathrm{Int}(\tilde{\tau}_{k})$)

1: if $i_{k}>\mathrm{Int}(\tilde{\tau}_{k})$ then

2: Update $\tilde{\tau}_{k}=\tilde{\tau}_{k}e$

3: end if

4: Set $p_{k,i_{k}}=\frac{b_{k}}{\min(T,\tilde{\tau}_{k}(e-1))}$

Subroutine 2 ($i_{k}$, $b_{k}$, $\tilde{\tau}_{k}$,
$\mathrm{Int}(\tilde{\tau}_{k})$)

1: if $i_{k}>\mathrm{Int}(\tilde{\tau}_{k})$ then

2: $j_{k}=j_{k}+1$

3: Update $\tilde{\tau}_{k}=\tilde{\tau}_{k}e$

4: end if

5: if $j_{k}\geq 3$ then

6: Set $p_{k,i_{k}}=\frac{b_{k}}{\tilde{\tau}_{k}e}$

7: else

8: Set $p_{k,i_{k}}=\frac{b_{k}}{\tilde{\tau}_{k}(e-1)}$

9: end if

Subroutine 3 ($i_{k}$, $b_{k}$, $\tilde{\tau}_{k}$,
$\mathrm{Int}(\tilde{\tau}_{k})$)

1: if $i_{k}>\mathrm{Int}(\tilde{\tau}_{k})$ then

2: $j_{k}=j_{k}+1$

3: Update $\tilde{\tau}_{k}=\tilde{\tau}_{k}e$

4: if $j_{k}\geq 3$ then

5: Update $b_{k}=b_{k}(1-\frac{1}{e})$

6: end if

7: end if

8: Set $p_{k,i_{k}}=\frac{b_{k}}{\tilde{\tau}_{k}e}$

We first illustrate the feasibility of our proposed solution, i.e., the
treatment assignment probabilities outputted from Algorithm 1 satisfies the
budget constraint in Problem (2.1):

######  Lemma 3.1.

The solution of Algorithm 1 always satisfies the budget constraint in
expectation, where the expectation is taken over the randomness of the
algorithm.

Next, we observe that due to the monotonically non-increasing nature of the
treatment probabilities, the objective in Problem (2.1) simplifies to

$\max\sum_{i_{k}=1}^{\tau_{k}^{*}}p_{k,i_{k}}-\frac{1}{\tau_{k}^{*}}\ln\left(\frac{p_{k,1}}{p_{k,\tau_{k}^{*}}}\right).$
(3)

Using Equation (3), we compute the competitive ratio:

######  Theorem 3.2.

Algorithm 1 is $\mathcal{X}(T)$-competitive, where $\mathcal{X}$ is defined as
follows:

$\displaystyle\mathcal{X}(T):=\left\\{\begin{array}[]{ll}\frac{1}{e}\left(\ln(e-1)+\frac{1}{e-1}\right)&\text{if}\quad
T\leq b_{k}e,\\\ \frac{1}{e}&\text{if}\quad b_{k}e<T\leq b_{k}e^{2},\\\
\frac{1}{e}-\frac{1}{e^{2}}&\text{if}\quad T>b_{k}e^{2}.\end{array}\right.$

The above competitive ratio is conservative by design: it was derived by
taking the worst-case over _unknown_ $\tau_{k}^{*}$ and horizon length $T$
within each case. The proof of Theorem 3.2 in Appendix A.2 outlines the
competitive ratio as a function of $\tau_{k}^{*}$ and $T$. In addition, in
Section 5 we explore the impact of varying $\tau_{k}^{*}$ while keeping the
horizon length fixed, providing a numerical illustration of how the expected
competitive ratio changes. We note that the expected competitive ratio,
averaged over the unknown $\tau_{k}^{*}$, is much better than our theoretical
competitive ratio illustrated above. Based on our theoretical competitive
ratio in Theorem 3.2, we recommend choosing the horizon length $T$ relative to
the budget $b_{k}$ to be between $b_{k}e$ and $b_{k}e^{2}$, which aligns with
our empirical results in Section 5 (see Remark 5.1 for details).

##  4 Learning-Augmented Algorithm

Algorithm 2 Randomized Online Algorithm With Predictions

1: Input: $T$, $\\{b_{k}\\}_{k=1}^{K}$, $\\{[L_{k},U_{k}]\\}_{k=1}^{K}$

2: Initialize: $\\{i_{k}=0\\}_{k=1}^{K}$, $\\{j_{k}=1\\}_{k=1}^{K}$, sample
$\alpha\in[b_{k},b_{k}e]$ from a distribution with p.d.f.
$f(\alpha)=1/\alpha$, and initialize $\\{\tilde{\tau}_{k}=\alpha\\}_{k=1}^{K}$

3: for $t=1,...,T$ do

4: On each iteration $t$, new risk level $R_{t}=k$ and intervention indicator,
$I_{t}$, arrive.

5: if $I_{t}=1$ then

6: Update $i_{k}=i_{k}+1$

7: else

8: No intervention and skip to the next iteration.

9: end if

10: Given $i_{k}$, $b_{k}$, $L_{k}$, $U_{k}$ $\tilde{\tau}_{k}$, and $T$, we
calculate:

11:
$\mathrm{Int}(\tilde{\tau}_{k})=\left\\{\begin{array}[]{ll}\lfloor\tilde{\tau}_{k}\rfloor&w.p.\quad\lceil\tilde{\tau}_{k}\rceil-\tilde{\tau}_{k}\\\
\lceil\tilde{\tau}_{k}\rceil&w.p.\quad\tilde{\tau}_{k}-\lfloor\tilde{\tau}_{k}\rfloor\end{array}\right.$

12: if $U_{k}\leq b_{k}e$ then

13: Update parameters and set $p_{k,i_{k}}$ using Subrtn. 4

14: else if $b_{k}e<U_{k}\leq b_{k}e^{2}$ then

15: if $U_{k}-L_{k}\leq b_{k}(e-1)$ then

16: Update parameters and set $p_{k,i_{k}}$ with Subrtn. 4

17: else

18: Update parameters and set $p_{k,i_{k}}$ with Subrtn. 2

19: end if

20: else

21: if $U_{k}-L_{k}\leq b_{k}(e+1)$ then

22: Update parameters and set $p_{k,i_{k}}$ with Subrtn. 5

23: else

24: Update parameters and set $p_{k,i_{k}}$ with Subrtn. 6

25: end if

26: end if

27: Deliver treatment with probability $p_{k,i_{k}}$

28: end for

Subroutine 4 ($i_{k}$, $b_{k}$, $\tilde{\tau}_{k}$, $L_{k}$, $U_{k}$,
$\mathrm{Int}(\tilde{\tau}_{k})$)

1: if $i_{k}>\mathrm{Int}(\tilde{\tau}_{k})+L_{k}$ then

2: Update $\tilde{\tau}_{k}=\tilde{\tau}_{k}e$

3: end if

4: Set $p_{k,i_{k}}=\frac{b_{k}}{\min(U_{k},\tilde{\tau}_{k}+L_{k})}$

Subroutine 5 ($i_{k}$, $b_{k}$, $\tilde{\tau}_{k}$, $L_{k}$, $U_{k}$,
$\mathrm{Int}(\tilde{\tau}_{k})$)

1: if $i_{k}>\mathrm{Int}(\tilde{\tau}_{k})+L_{k}$ then

2: Update $\tilde{\tau}_{k}=\tilde{\tau}_{k}e$

3: end if

4: Set $p_{k,i_{k}}=\frac{b_{k}}{\min(U_{k},\tilde{\tau}_{k}e+L_{k})}$

Subroutine 6 ($i_{k}$, $b_{k}$, $\tilde{\tau}_{k}$, $L_{k}$, $U_{k}$,
$\mathrm{Int}(\tilde{\tau}_{k})$)

1: if $i_{k}>\mathrm{Int}(\tilde{\tau}_{k})+L_{k}$ then

2: $j_{k}=j_{k}+1$

3: if $j_{k}=2$ then

4:  _agent_ updates
$b_{k}=b_{k}(1-\frac{\tilde{\tau}_{k}+L_{k}-b_{k}}{\tilde{\tau}_{k}(e-1)+L_{k}})$

5: else

6:  _agent_ updates $b_{k}=b_{k}(1-\frac{1}{e})$

7: end if

8:  _agent_ updates $\tilde{\tau}_{k}=\tilde{\tau}_{k}e$

9: end if

10: if $j_{k}=1$ then

11:  _agent_ set $p_{k,i_{k}}=\frac{b_{k}}{\tilde{\tau}_{k}(e-1)+L_{k}}$

12: else

13:  _agent_ set $p_{k,i_{k}}=\frac{b_{k}}{\tilde{\tau}_{k}e}$

14: end if

In this section, we propose a new approximation algorithm, Algorithm 2, under
the learning-augmented setting, where we are provided with prediction
intervals $\\{[L_{k},U_{k}]\\}_{k\in[K]}$ for each unknown $\tau_{k}^{*}$. Our
proposed Algorithm 2 builds upon the non-learning counterpart, Algorithm 1,
utilizing the given prediction interval for optimization. Similar to Algorithm
1, we initialize $\alpha\sim[b_{k},b_{k}e]$ with density $1/\alpha$, and the
current “guess” of $\tau_{k}^{*}$ is reflected by $\tilde{\tau}_{k}+L_{k}$.

In Algorithm 2, the three scenarios differ from those in Algorithm 1. Here,
the distinction is based on the relationship between the upper bound of the
prediction interval, $U_{k}$, and the budget $b_{k}$. The three scenarios are
1) $U_{k}\leq b_{k}e$ (Subroutine 4), 2) $b_{k}e<U_{k}\leq b_{k}e^{2}$,
further divided into 2a) $U_{k}-L_{k}\leq b_{k}(e-1)$ (Subroutine 4), and 2b)
$U_{k}-L_{k}>b_{k}(e-1)$ (Subroutine 2), and 3) $U_{k}>b_{k}e^{2}$, further
divided into 3a) $U_{k}-L_{k}\leq b_{k}(e+1)$ (Subroutine 5), and 3b)
$U_{k}-L_{k}>b_{k}(e+1)$ (Subroutine 6).

Similar to Algorithm 1, we first illustrate that Algorithm 2 produces a
feasible solution to Problem (2.1):

######  Lemma 4.1.

The solution of Algorithm 2 always satisfies the budget constraint in
expectation, where the expectation is taken over the randomness of the
algorithm.

The proof of Lemma 4.1 is deferred to Appendix B.1.

######  Theorem 4.2.

This algorithm is $1$-consistent and $\mathcal{X}(L_{k},U_{k})$-robust, where
$\mathcal{X}(U_{k})$ is defined as follows:

$\displaystyle\mathcal{X}(U_{k}):=\left\\{\begin{array}[]{ll}\ln
2+\frac{e-1}{e}\ln\frac{e-1}{e}&\text{if}\quad U_{k}\leq b_{k}e,\\\
\frac{1}{e}&\text{if}\quad b_{k}e<U_{k}\leq b_{k}e^{2},\\\
2-\ln(e^{2}-e+1)&\text{if}\quad U_{k}>b_{k}e^{2}.\end{array}\right.$

We first note that Algorithm 2 is $1$-consistent, achieving the performance of
the offline clairvoyant when the prediction is perfect. The proof of Theorem
4.2 in Appendix B.2 details the competitive ratio as influenced by
$\tau_{k}^{*}$, $L_{k}$, and $T$. Additionally, Section 5 demonstrates how
varying the prediction interval width $U_{k}-L_{k}$, while maintaining a
constant $\tau_{k}^{*}$, affects performance. Notably, when comparing Theorem
4.2 with Theorem 3.2, we observe that Algorithm 2 almost always outperforms
its non-learning augmented equivalent across different interval widths. We
defer the discussion of the design choice of $T$ relative to $b_{k}$ in the
presence of prediction intervals to Remark 5.2.

Figure 1: Average competitive ratio under non-learning augmented setting.
Left: $T=8$; Middle: $T=22$; Right: $T=100$.

##  5 Experiments

In this section, we assess the performance of our proposed algorithms through
numerical experiments conducted on both synthetic and real-world datasets. The
metric used for evaluation is the average competitive ratio.

###  5.1 Synthetic Experiments

To simplify representation, we consider binary risk levels, i.e.,
$R_{t}\in\\{0,1\\}$ with $K=1$, representing the patient is either at risk
($R_{t}=1$) or not at risk ($R_{t}=0$). In the latter case, no intervention is
needed. To streamline notation, we drop the subscript $k$, e.g., we use $b$ to
represent the total expected number of interventions when the patient is at
risk.

Benchmarks  In the setting without learning augmentation, we compare Algorithm
1 against a simple benchmark that achieves the uniformity objective without
depleting the budget: it delivers treatments with a constant probability
$b/T$. In the learning-augmented setting, we introduce a known interval
$[L,U]$ containing $\tau^{*}$. We compare Algorithm 2 with a benchmark that
delivers interventions with a constant probability $b/U$. In addition, we
compare our learning augmented algorithm, Algorithm 2 with our non-learning
augmented algorithm, Algorithm 1.

Without Learning Augmentation  In this setting, we test the performance of
Algorithm 1 across all three scenarios listed in Theorem 3.2. To do this, we
fix the budget level $b=3$, and alter the horizon lengths, $T$, to correspond
with each case. For Scenarios 1 and 2, we set $T$ to be the maximum possible
length in each scenario with $b=3$, with $T=8$ and $22$ respectively in Figure
1 (left and middle). Scenario 3 in Algorithm 1 allows $T$ to grow to infinity
asymptotically. We set $T=100$ for simplicity (Figure 1 right). To simulate
risk occurrences, we randomly draw an integer $\tau^{*}$ from the interval
$[b,T-1]$ and randomly select $\tau^{*}$ time points from $T$, assigning
$R_{t}=1$ to these points. The rest are designated as $R_{t}=0$.

Figure 1 shows the average competitive ratio over a range of $\tau^{*}$
values. In Figure 1 (left), we observe that our randomized algorithm
outperforms the benchmark by a constant competitive ratio across all values of
$\tau^{*}$ in Scenario 1. In Figure 1 (middle), our randomized algorithm
increasingly outperforms the benchmark particularly as $\tau^{*}$ deviates
away from the horizon length $T$ in Scenario 2. We note that in Figure 1
(middle), when $\tau^{*}=22$, the competitive ratio slightly exceeds 1. This
is attributed to our algorithm utilizing a slightly higher budget in
expectation. We provide detailed insights into this observation in Appendix
A.1, where we demonstrate that the worst-case budget spent is $1.044b_{k}$,
slightly surpassing the allocated budget.

In Figure 1 (right), as $T$ grows, the average competitive ratio of our
algorithm would remain the same as in Figure 1 (right).333This is because when
$b$ is fixed, the treatment assignment probability is independent of $T$.
Here, we conclude that our algorithm increasingly outperforms the benchmark as
$T$ grows to infinity.

######  Remark 5.1 (Design choice of $b_{k}$ and $T$ in absence of prediction
intervals).

In real-world applications, the budget for intervention at each risk level is
often fixed. Yet, there remains the design question of $T$, i.e., how granular
to discretize the decision period. From Figure 1, We note that although
Scenario 3 yields the largest possible improvement in algorithm performance
when compared with the benchmark as $T$ grows to infinity, our randomized
algorithm has the highest competitive ratios across all $\tau^{*}$ in Scenario
2. Thus, in the absence of prediction intervals, we recommend setting $T$ to
be in between $b_{k}e$ and $b_{k}e^{2}$. This recommendation changes when a
prediction interval is presented.

Figure 2: Average competitive ratio under learning-augmented setting. Left:
$T=8$; Middle: $T=22$; Right: $T=100$. Figure 3: Average competitive ratio
across user days under various prediction interval widths on HeartSteps V1
dataset. The shaded area indicates the $\pm 1.96$ standard error bounds across
user days.

With Learning Augmentation  In this setting, we examine the performances of
Algorithm 1 and Algorithm 2 under varying prediction interval widths. Similar
to the non-learning augmented setting, we keep the budget fixed at $b=3$ and
examine the performance of our learning-augmented algorithm under $T=8,22,$
and $100$, corresponding to the three scenarios in Algorithm 2.

For enhanced comparability across various confidence widths, we maintain
constant risk occurrences, $\tau^{*}=\text{Int}[0.5(T+b)]$, across all
simulations shown in Figure 2.444If we allow $\tau^{*}$ to change across
different simulations, then the difference that we observe in competitive
ratio might be due to this change in $\tau^{*}$. The confidence intervals are
randomly generated based on the given width, and they must contain $\tau^{*}$.

The average competitive ratio of each algorithm against a range of prediction
interval widths is plotted in Figure 2. In all plots within Figure 2, we
observe that the naive benchmark (where $p_{i}=b/U$ for all $i\in[\tau^{*}]$)
consistently outperforms the randomized algorithm (which does not have access
to the prediction interval) when the confidence interval is narrow. However,
as the confidence interval widens, our randomized algorithm outperforms the
naive benchmark. In addition, we observe that our learning-augmented algorithm
performs no worse than both the naive benchmark and the randomized algorithm.
In particular, the advantage of our algorithm is the largest when in Scenario
3.

We include additional experimental results where $\tau^{*}$ is small in
Appendix C.1. We note that as $\tau^{*}$ decreases, the advantage of our
algorithm in Scenario 2 increases. In addition, we provide the competitive
ratio figures in the absence of the penalization term in Problem (2.1) in
Appendix C.2. This measures the fraction of the budget spent by our
algorithms.

######  Remark 5.2 (Design choice of $b_{k}$ and $T$ in presence of prediction
intervals).

In the presence of a prediction interval, if we expect the value of $\tau^{*}$
to be small, we recommend setting $T$ to be in Scenario 2. If we expect a
reasonably large value of $\tau^{*}$, we recommend setting a large value for
$T$ such that the algorithm operates under Scenario 3.

###  5.2 Real-World Experiments on HeartSteps V1

Our research is inspired by the Heartsteps V1 mobile health study, which aims
to enhance physical activity, specifically through regular walking, among
sedentary individuals Klasnja et al. (2019). The study involved 37
participants over a follow-up period of six weeks, gathering detailed data on
step counts on a minute-by-minute basis. To ensure the reliability of the step
count data, our analysis was restricted to the hours from 9 am to 9 pm, with a
decision time frequency set at five-minute intervals Liao et al. (2018).
Consequently, this led to the accumulation of $1585$ instances of 12-hour
user-days, giving rise to a time horizon of $T=144$.

At each decision time point $t$, we define the risk variable $R_{t}$ with a
binary classification: $R_{t}=1$ indicates a sedentary state, identified by
recording fewer than 150 steps in the prior 40 minutes, and $R_{t}=0$
signifies a non-sedentary state. Additionally, the availability for
intervention, $I_{t}$, is contingent on recent messaging activity: if the user
has received an anti-sedentary message within the preceding hour, $I_{t}$ is
set to 0; otherwise, it is set to 1. The primary objective of this strategy is
to uniformly distribute around $b=1.5$ interventions during sedentary times
each day.

In addition to the naive benchmark $b_{k}/U$, our study also includes
evaluations of Algorithms 1 and 2 against the SeqRTS algorithm, as introduced
by Liao et al. (2018). A detailed description of the SeqRTS method is included
in the Appendix D. Under SeqRTS, the budget may be depleted before allocating
for all available risk times. When this happens, a minimum probability of
$1\times 10^{-6}$ is assigned to the remaining times when calculating the
objective in Problem (2.1), as illustrated in Figure 3. To better understand
the behavior of SeqRTS, we set the minimum probability to $0$ in Figure 8 in
Appendix D. The performances are measured by competitive ratio averaged across
user days.

In Figure 3, Algorithm 2, which incorporates a prediction interval, invariably
outperforms the non-learning counterpart, the SeqRTS approach, and the naive
benchmark $b_{k}/U$. Moreover, our algorithms exhibit superior uniformity in
risk times sampling, evidenced by reduced entropy change compared to both the
non-learning algorithm and SeqRTS, as further detailed in Figure 7 (Appendix
D). Figure 8 illustrates that SeqRTS could deplete its budget even when the
prediction is fairly accurate, highlighting the robustness of our algorithms
under adversarial risk level arrivals. Further implementation details are
included in Appendix D.

Conclusion and Future Works  This paper marks the first attempt to study the
online uniform risk times sampling problem within the framework of
approximation algorithms. We introduce two novel online algorithms—either
incorporating learning augmentation or not—backed by rigorous theoretical
guarantees and empirical results. Future works include adapting existing
algorithms to scenarios where prediction intervals improve over time.

## Broader Impact

The rapid advancement of digital health technologies demands innovative
strategies for optimal treatment timing, specifically addressing the challenge
posed by the online uniform risk times sampling problem to enhance treatment
efficacy. Our research introduces online approximation algorithms augmented
with ML predictions, ideally suited for scenarios where future behavior can be
predicted using either real-time data accumulation or initial study results,
while also ensuring the maintenance of reliable worst-case performance
guarantees. Significantly, our work pioneers the integration of ML prediction
intervals—widely recognized in the field—with online algorithms. This novel
approach expands the applicability of a broader spectrum of ML approaches and
sets a precedent for their use in diverse problem-solving contexts.

## References

  * Bamas et al. (2020) Bamas, E., Maggiori, A., and Svensson, O.  The primal-dual method for learning augmented algorithms.  _Advances in Neural Information Processing Systems_ , 33:20083–20094, 2020.
  * Battalio et al. (2021) Battalio, S. L., Conroy, D. E., Dempsey, W., Liao, P., Menictas, M., Murphy, S., Nahum-Shani, I., Qian, T., Kumar, S., and Spring, B.  Sense2stop: a micro-randomized trial using wearable sensors to optimize a just-in-time-adaptive stress management intervention for smoking relapse prevention.  _Contemporary Clinical Trials_ , 109:106534, 2021.
  * Boruvka et al. (2018) Boruvka, A., Almirall, D., Witkiewitz, K., and Murphy, S. A.  Assessing time-varying causal effect moderation in mobile health.  _Journal of the American Statistical Association_ , 113(523):1112–1121, 2018.
  * Dennis et al. (2015) Dennis, M. L., Scott, C. K., Funk, R. R., and Nicholson, L.  A pilot study to examine the feasibility and potential effectiveness of using smartphones to provide recovery support for adolescents.  _Substance abuse_ , 36(4):486–492, 2015.
  * Dimitrijević et al. (1972) Dimitrijević, M. R., Faganel, J., Gregorić, M., Nathan, P., and Trontelj, J.  Habituation: effects of regular and stochastic stimulation.  _Journal of Neurology, Neurosurgery & Psychiatry_, 35(2):234–242, 1972.
  * Heckman et al. (2015) Heckman, B. W., Mathew, A. R., and Carpenter, M. J.  Treatment burden and treatment fatigue as barriers to health.  _Current opinion in psychology_ , 5:31–36, 2015.
  * Jin & Ma (2022) Jin, B. and Ma, W.  Online bipartite matching with advice: Tight robustness-consistency tradeoffs for the two-stage model.  _Advances in Neural Information Processing Systems_ , 35:14555–14567, 2022.
  * Kallus & Zhou (2022) Kallus, N. and Zhou, A.  Stateful offline contextual policy evaluation and learning.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 11169–11194. PMLR, 2022.
  * Klasnja et al. (2008) Klasnja, P., Harrison, B. L., LeGrand, L., LaMarca, A., Froehlich, J., and Hudson, S. E.  Using wearable sensors and real time inference to understand human recall of routine activities.  In _Proceedings of the 10th international conference on Ubiquitous computing_ , pp. 154–163, 2008.
  * Klasnja et al. (2019) Klasnja, P., Smith, S., Seewald, N. J., Lee, A., Hall, K., Luers, B., Hekler, E. B., and Murphy, S. A.  Efficacy of contextually tailored suggestions for physical activity: a micro-randomized optimization trial of heartsteps.  _Annals of Behavioral Medicine_ , 53(6):573–582, 2019.
  * Li et al. (2020) Li, S., Psihogios, A. M., McKelvey, E. R., Ahmed, A., Rabbi, M., and Murphy, S.  Microrandomized trials for promoting engagement in mobile health data collection: Adolescent/young adult oral chemotherapy adherence as an example.  _Current opinion in systems biology_ , 21:1–8, 2020.
  * Liao et al. (2018) Liao, P., Dempsey, W., Sarker, H., Hossain, S. M., Al’absi, M., Klasnja, P., and Murphy, S.  Just-in-Time but Not Too Much: Determining Treatment Timing in Mobile Health.  _Proceedings of the ACM on interactive, mobile, wearable and ubiquitous technologies_ , 2(4):179, December 2018.  ISSN 2474-9567.  doi: 10.1145/3287057.
  * Mann & Robinson (2009) Mann, S. and Robinson, A.  Boredom in the lecture theatre: An investigation into the contributors, moderators and outcomes of boredom amongst university students.  _British Educational Research Journal_ , 35(2):243–258, 2009.
  * McConnell et al. (2017) McConnell, M. V., Shcherbina, A., Pavlovic, A., Homburger, J. R., Goldfeder, R. L., Waggot, D., Cho, M. K., Rosenberger, M. E., Haskell, W. L., Myers, J., et al.  Feasibility of obtaining measures of lifestyle from a smartphone app: the myheart counts cardiovascular health study.  _JAMA cardiology_ , 2(1):67–76, 2017.
  * Mehta et al. (2013) Mehta, A. et al.  Online matching and ad allocation.  _Foundations and Trends® in Theoretical Computer Science_ , 8(4):265–368, 2013.
  * Nahum-Shani et al. (2018) Nahum-Shani, I., Smith, S. N., Spring, B. J., Collins, L. M., Witkiewitz, K., Tewari, A., and Murphy, S. A.  Just-in-time adaptive interventions (jitais) in mobile health: key components and design principles for ongoing health behavior support.  _Annals of Behavioral Medicine_ , pp. 1–17, 2018.
  * Purohit et al. (2018) Purohit, M., Svitkina, Z., and Kumar, R.  Improving online algorithms via ml predictions.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Rathbun et al. (2013) Rathbun, S. L., Song, X., Neustifter, B., and Shiffman, S.  Survival analysis with time varying covariates measured at random times by design.  _Journal of the Royal Statistical Society Series C: Applied Statistics_ , 62(3):419–434, 2013.
  * Scott et al. (2017a) Scott, C. K., Dennis, M. L., Gustafson, D., and Johnson, K.  A pilot study of the feasibility and potential effectiveness of using smartphones to provide recovery support.  _Drug and Alcohol Dependence_ , 100(171):e185, 2017a.
  * Scott et al. (2017b) Scott, C. K., Dennis, M. L., and Gustafson, D. H.  Using smartphones to decrease substance use via self-monitoring and recovery support: study protocol for a randomized control trial.  _Trials_ , 18(1):1–11, 2017b.
  * Shafer & Vovk (2008) Shafer, G. and Vovk, V.  A tutorial on conformal prediction.  _Journal of Machine Learning Research_ , 9(3), 2008.
  * Shiffman et al. (2008) Shiffman, S., Stone, A. A., and Hufford, M. R.  Ecological momentary assessment.  _Annu. Rev. Clin. Psychol._ , 4:1–32, 2008.
  * Shin et al. (2023) Shin, Y., Lee, C., Lee, G., and An, H.-C.  Improved learning-augmented algorithms for the multi-option ski rental problem via best-possible competitive analysis.  _arXiv preprint arXiv:2302.06832_ , 2023.
  * Smith (1950) Smith, J. M.  Introduction to chemical engineering thermodynamics, 1950.
  * Spruijt-Metz et al. (2022) Spruijt-Metz, D., Marlin, B. M., Pavel, M., Rivera, D. E., Hekler, E., De La Torre, S., El Mistiri, M., Golaszweski, N. M., Li, C., Braga De Braganca, R., et al.  Advancing behavioral intervention and theory development for mobile health: the heartsteps ii protocol.  _International journal of environmental research and public health_ , 19(4):2267, 2022.
  * Stone et al. (2007) Stone, A., Shiffman, S., Atienza, A., and Nebeling, L.  _The science of real-time data capture: Self-reports in health research_.  Oxford University Press, 2007.
  * Wei & Zhang (2020) Wei, A. and Zhang, F.  Optimal robustness-consistency trade-offs for learning-augmented online algorithms.  _Advances in Neural Information Processing Systems_ , 33:8042–8053, 2020.
  * Wen et al. (2017) Wen, C. K. F., Schneider, S., Stone, A. A., and Spruijt-Metz, D.  Compliance with mobile ecological momentary assessment protocols in children and adolescents: a systematic review and meta-analysis.  _Journal of medical Internet research_ , 19(4):e132, 2017.
  * Zhang et al. (2011) Zhang, G., Poon, C. K., and Xu, Y.  The ski-rental problem with multiple discount options.  _Information Processing Letters_ , 111(18):903–906, 2011.
  * Zhou et al. (2023) Zhou, Z., Athey, S., and Wager, S.  Offline multi-action policy learning: Generalization and optimization.  _Operations Research_ , 71(1):148–183, 2023.

##  Appendix A Proof for Algorithm 1

###  A.1 Proof of Lemma 3.1: Budget constraint

###### Proof.

We prove that the budget constraint is satisfied in expectation under each
subroutine in Algorithm 1.

Subroutine 1

Recall that $\tau_{k}^{*}$ is the true number of available risk times at risk
level $k$. Here, we suppose $\tau_{k}^{*}=\beta e^{j^{*}}$ for some
$j^{*}\in\mathbb{Z}^{+}$ and $\beta\in[b_{k},b_{k}e]$. Since $T\leq b_{k}e$,
we have that $j^{*}=0$.

In this analysis, our focus is solely on the worst-case scenario, where both
$T$ and $\tau_{k}^{*}$ are very close to $b_{k}e$. Assuming $\eta>b_{k}$
(where $\eta=\frac{T}{e-1}$), if this is not the case, the algorithm uniformly
sets $p_{k,i_{k}}=\frac{b_{k}}{T}$ throughout.

When $\eta>b_{k}$ and $\alpha$ falls in the range of $[b_{k},\eta]$, the
algorithm starts with $p_{k,i_{k}}=\frac{b_{k}}{\alpha(e-1)}$, then
transitions to $p_{k,i_{k}}=\frac{b_{k}}{T}$ for the second phase; otherwise,
it consistently uses $p_{k,i_{k}}=\frac{b_{k}}{T}$. Therefore, we have

$\displaystyle\mathbb{E}[\operatorname{Budget}_{k}]$
$\displaystyle=\int_{\eta}^{b_{k}e}\frac{b_{k}}{T}\beta\frac{1}{\alpha}d\alpha+\int_{b_{k}}^{\eta}\Big{[}\frac{b_{k}}{\alpha(e-1)}\alpha+\frac{b_{k}}{T}(\beta-\alpha)\Big{]}\frac{1}{\alpha}d\alpha$
$\displaystyle=\frac{b_{k}\beta}{T}\ln\frac{b_{k}e}{\eta}+\frac{b_{k}}{e-1}\ln\frac{\eta}{b_{k}}+\frac{b_{k}\beta}{T}\ln\frac{\eta}{b_{k}}-\frac{b_{k}}{T}(\eta-
b_{k})$
$\displaystyle=\frac{b_{k}\beta}{T}+\frac{b_{k}}{e-1}\ln\frac{\eta}{b_{k}}-\frac{b_{k}\eta}{T}+\frac{b_{k}^{2}}{T}$
$\displaystyle\leq
b_{k}+\frac{b_{k}}{e-1}\ln\frac{T}{b_{k}(e-1)}-\frac{b_{k}}{e-1}+\frac{b_{k}^{2}}{T}\quad\text{increasing
with}~{}\beta~{}(\beta=T)$ $\displaystyle\leq
b_{k}-\frac{b_{k}}{e-1}+\frac{b_{k}}{e-1}\quad\text{increasing
with}~{}T~{}(T=b_{k}e)$ $\displaystyle\leq b_{k}.$

Subroutine 2

Reiterating our initial assumption, we set $\tau_{k}^{*}=\beta e^{j^{*}}$. The
condition $b_{k}e<T\leq b_{k}e^{2}$ limits $j^{*}$ to either $0$ or $1$.
However, our analysis is particularly concerned with the worst-case scenario,
hence we consider only the case where $j^{*}=1$. The expected budget is
therefore

$\displaystyle\mathbb{E}\left[\operatorname{Budget}_{k}\right]$
$\displaystyle=\int_{\beta}^{b_{k}e}\left[\frac{b_{k}}{\alpha(e-1)}\alpha+\frac{b_{k}}{\alpha
e(e-1)}(\beta
e-\alpha)\right]\frac{1}{\alpha}d\alpha+\int_{b_{k}}^{\beta}\left[\frac{b_{k}}{\alpha(e-1)}\alpha+\frac{b_{k}}{\alpha
e(e-1)}(\alpha e-\alpha)+\frac{b_{k}}{\alpha e^{3}}(\beta e-\alpha
e)\right]\frac{1}{\alpha}d\alpha$
$\displaystyle=\frac{b_{k}}{e-1}+\frac{b_{k}\beta}{e-1}(\frac{1}{\beta}-\frac{1}{b_{k}e})-\frac{b_{k}}{e(e-1)}\ln\frac{b_{k}e}{\beta}+\frac{b_{k}}{e}\ln\frac{\beta}{b_{k}}+\frac{b_{k}\beta}{e^{2}}(\frac{1}{b_{k}}-\frac{1}{\beta})-\frac{b_{k}}{e^{2}}\ln\frac{\beta}{b_{k}}$
$\displaystyle=\frac{b_{k}}{e-1}+\frac{b_{k}}{e-1}-\frac{\beta}{e(e-1)}+\frac{\beta}{e^{2}}-\frac{b_{k}}{e^{2}}-\frac{b_{k}}{e(e-1)}+(\frac{b_{k}}{e}+\frac{b_{k}}{e(e-1)}-\frac{b_{k}}{e^{2}})\ln\frac{\beta}{b_{k}}$
$\displaystyle=\frac{b_{k}}{e-1}+\frac{b_{k}}{e}-\frac{b_{k}}{e^{2}}-\frac{\beta}{e^{2}(e-1)}+(\frac{b_{k}}{e-1}-\frac{b_{k}}{e^{2}})\ln\frac{\beta}{b_{k}}$
$\displaystyle\leq\frac{b_{k}}{e-1}+\frac{b_{k}}{e}-\frac{b_{k}}{e^{2}}-\frac{b_{k}e}{e^{2}(e-1)}+(\frac{b_{k}}{e-1}-\frac{b_{k}}{e^{2}})\ln\frac{b_{k}e}{b_{k}}\quad\text{increasing
with}~{}\beta~{}(\beta=b_{k}e)$
$\displaystyle=\frac{2b_{k}}{e}+\frac{b_{k}}{e-1}-\frac{2b_{k}}{e^{2}}\leq
b_{k}$

Subroutine 3

Under the assumption of $\tau_{k}^{*}=\beta e^{j^{*}}$, and given the
condition $T>b_{k}e^{2}$, it is possible for $j^{*}$ to be $0$ or to extend
towards infinity. Our focus, however, is confined to the worst-case scenarios,
particularly those where $j^{*}\geq 1$.

$\displaystyle\mathbb{E}\left[\operatorname{Budget}_{k}\right]$
$\displaystyle=\int_{\beta}^{b_{k}e}\left[\frac{b_{k}}{\alpha
e}\alpha+\sum_{i=2}^{j^{*}}\frac{b_{k}(1-1/e)^{j-2}}{\alpha e^{j}}(\alpha
e^{j-1}-\alpha e^{j-2})+\frac{b_{k}(1-1/e)^{j^{*}-1}}{\alpha
e^{j^{*}+1}}(\beta e^{j^{*}}-\alpha
e^{j^{*}-1})\right]\frac{1}{\alpha}d\alpha$
$\displaystyle\quad+\int_{b_{k}}^{\beta}\left[\frac{b_{k}}{\alpha
e}\alpha+\sum_{j=2}^{j^{*}+1}\frac{b_{k}(1-1/e)^{j-2}}{\alpha e^{j}}(\alpha
e^{j-1}-\alpha e^{j-2})+\frac{b_{k}(1-1/e)^{j^{*}}}{\alpha e^{j^{*}+2}}(\beta
e^{j^{*}}-\alpha e^{j^{*}})\right]\frac{1}{\alpha}d\alpha$
$\displaystyle=\int_{\beta}^{b_{k}e}\left[\frac{b_{k}}{e}+b_{k}(1-\frac{1}{e}-(1-\frac{1}{e})^{j^{*}})+\frac{b_{k}(e-1)^{j^{*}-1}}{e^{j^{*}+1}}\frac{\beta
e-\alpha}{\alpha}\right]\frac{1}{\alpha}d\alpha$
$\displaystyle\quad+\int_{b_{k}}^{\beta}\left[\frac{b_{k}}{e}+b_{k}(1-\frac{1}{e}-(1-\frac{1}{e})^{j^{*}+1})+\frac{b_{k}(e-1)^{j^{*}}}{e^{j^{*}+2}}\frac{\beta-\alpha}{\alpha}\right]\frac{1}{\alpha}d\alpha$
$\displaystyle=\frac{b_{k}}{e}+b_{k}(1-\frac{1}{e})-b_{k}(1-\frac{1}{e})^{j^{*}}\ln\frac{b_{k}e}{\beta}-b_{k}(1-\frac{1}{e})^{j^{*}+1}\ln\frac{\beta}{b_{k}}$
$\displaystyle\quad+\frac{b_{k}(e-1)^{j^{*}-1}}{e^{j^{*}+1}}\left[e-\frac{\beta}{b_{k}}+\ln\frac{\beta}{b_{k}e}\right]+\frac{b_{k}(e-1)^{j^{*}}}{e^{j^{*}+2}}\left[\frac{\beta}{b_{k}}-1+\ln\frac{b_{k}}{\beta}\right]$
$\displaystyle\leq
b_{k}-b_{k}(1-\frac{1}{e})^{j^{*}+1}\ln\frac{b_{k}e}{b_{k}}+\frac{b_{k}(e-1)^{j^{*}}}{e^{j^{*}+2}}\left[\frac{b_{k}e}{b_{k}}-1+\ln\frac{b_{k}}{b_{k}e}\right]\quad\text{increasing
with}~{}\beta~{}(\beta=b_{k}e)$
$\displaystyle=b_{k}-b_{k}(1-\frac{1}{e})^{j^{*}+1}+\frac{b_{k}(e-1)^{j^{*}}(e-2)}{e^{j^{*}+2}}\leq
b_{k}$

By combining the above results, we establish Lemma 3.1. ∎

###  A.2 Proof of Theorem 3.1: Competitive Ratio

###### Proof.

In what follows we derive the competitive ratio under each subroutine.

Subroutine 1

Recall that $\tau_{k}^{*}$ represents the actual number of available risk
times at risk level $k$, we assume $\tau_{k}^{*}=\beta e^{j^{*}}$, where
$j^{*}\in\mathbb{Z}^{+}$ and $\beta\in[b_{k},b_{k}e]$. It’s evident that when
$T\leq b_{k}e$, $j^{*}=0$ follows naturally.

Defining $\eta=T/(e-1)$, let’s consider the case where $\eta\leq b_{k}$,
leading to $T\leq b_{k}(e-1)$. Given that
$p_{k,i_{k}}=\frac{b_{k}}{\min(T,\tilde{\tau}_{k}(e-1))}$, it follows that the
algorithm consistently sets $p_{k,i_{k}}=\frac{b_{k}}{T}$. Consequently, we
derive:

$\displaystyle\mathbb{E}[\operatorname{SOL}_{k}]$
$\displaystyle=\frac{b_{k}}{T}\beta\geq\frac{b_{k}}{b_{k}(e-1)}\beta\geq\frac{b_{k}}{e-1}.$

Further, if $\eta>b_{k}$ and $\alpha$ falls within $[b_{k},\eta]$, the
algorithm initiates with $p_{k,i_{k}}=\frac{b_{k}}{\alpha(e-1)}$, then adjusts
to $p_{k,i_{k}}=\frac{b_{k}}{T}$ in the subsequent round if $\tau_{k}^{*}$ is
large enough; otherwise, it consistently uses $p_{k,i_{k}}=\frac{b_{k}}{T}$.
We focus on two cases: (1) $\beta<\eta$ and (2) $\beta\geq\eta$.

When $\beta<\eta$, if $\alpha>\beta$, the algorithm stops on the first round;
otherwise, it continues to the second round.

$\displaystyle\mathbb{E}[\operatorname{SOL}_{k}]$
$\displaystyle=\int_{\eta}^{b_{k}e}\frac{b_{k}}{T}\beta\frac{1}{\alpha}d\alpha+\int_{b_{k}}^{\beta}\Big{[}\frac{b_{k}}{\alpha(e-1)}\alpha+\frac{b_{k}}{T}(\beta-\alpha)-\frac{1}{\beta}\ln\frac{T}{\alpha(e-1)}\Big{]}\frac{1}{\alpha}d\alpha+\int_{\beta}^{\eta}\frac{b_{k}}{\alpha(e-1)}\beta\frac{1}{\alpha}d\alpha$
$\displaystyle=\frac{b_{k}\beta}{T}\ln\frac{b_{k}e}{\eta}+\frac{b_{k}}{e-1}\ln\frac{\beta}{b_{k}}+\frac{b_{k}\beta}{T}\ln\frac{\beta}{b_{k}}-\frac{b_{k}}{T}(\beta-
b_{k})+\frac{1}{2\beta}(\ln(\frac{T}{\beta(e-1)})^{2}-\ln(\frac{T}{b_{k}(e-1)})^{2})+\frac{b_{k}\beta}{e-1}(\frac{1}{\beta}-\frac{1}{\eta})$
$\displaystyle\geq\frac{b_{k}^{2}}{T}\ln\frac{b_{k}e(e-1)}{T}+\frac{b_{k}}{e-1}-\frac{b_{k}^{2}}{T}\quad\text{increasing
with}~{}\beta~{}(\beta=b_{k})$
$\displaystyle\geq\frac{b_{k}}{e}\ln(e-1)+\frac{b_{k}}{e(e-1)}\quad\text{decreasing
with}~{}T~{}(T=b_{k}e).$

When $\beta\geq\eta$, indicating that $\beta$ consistently surpasses $\eta$,
it follows that the algorithm always proceeds to the second round.
Consequently, we have

$\displaystyle\mathbb{E}[\operatorname{SOL}_{k}]$
$\displaystyle=\int_{\eta}^{b_{k}e}\frac{b_{k}}{T}\beta\frac{1}{\alpha}d\alpha+\int_{b_{k}}^{\eta}\Big{[}\frac{b_{k}}{\alpha(e-1)}\alpha+\frac{b_{k}}{T}(\beta-\alpha)-\frac{1}{\beta}\ln\frac{T}{\alpha(e-1)}\Big{]}\frac{1}{\alpha}d\alpha$
$\displaystyle=\frac{b_{k}\beta}{T}\ln\frac{b_{k}e}{\eta}+\frac{b_{k}}{e-1}\ln\frac{\eta}{b_{k}}+\frac{b_{k}\beta}{T}\ln\frac{\eta}{b_{k}}-\frac{b_{k}}{T}(\eta-
b_{k})+\frac{1}{2\beta}(\ln(\frac{T}{\eta(e-1)})^{2}-\ln(\frac{T}{b_{k}(e-1)})^{2})$
$\displaystyle\geq\frac{b_{k}}{e-1}\ln\frac{b_{k}e}{\eta}+\frac{2b_{k}}{e-1}\ln\frac{T}{b_{k}(e-1)}-\frac{b_{k}}{e-1}+\frac{b_{k}^{2}}{T}-\frac{e-1}{2T}\ln(\frac{T}{b_{k}(e-1)})^{2}$
$\displaystyle\quad\text{increasing with}~{}\beta~{}(\beta=\eta=T/(e-1))$
$\displaystyle\geq\frac{2b_{k}}{e-1}-\frac{b_{k}}{e-1}\ln(e-1)-\frac{b_{k}}{e(e-1)}-\frac{e-1}{2b_{k}e}\ln(\frac{e}{e-1})^{2}\quad\text{decreasing
with}~{}T~{}(T=b_{k}e).$

Subroutine 2

Recall that for $b_{k}e<T\leq b_{k}e^{2}$, $j^{*}$ is restricted to being
either $0$ or $1$. Below we separately consider these two cases.

In the case where $j^{*}=0$, it follows that

$\displaystyle\mathbb{E}[\operatorname{SOL}_{k}]$
$\displaystyle=\int_{\beta}^{b_{k}e}\frac{b_{k}}{\alpha(e-1)}\beta\frac{1}{\alpha}d\alpha+\int_{b_{k}}^{\beta}\left[\frac{b_{k}}{\alpha(e-1)}\alpha+\frac{b_{k}}{\alpha
e(e-1)}(\beta-\alpha)-\frac{1}{\beta}\ln(e)\right]\frac{1}{\alpha}d\alpha$
$\displaystyle=\frac{b_{k}\beta}{e-1}\left(\frac{1}{\beta}-\frac{1}{b_{k}e}\right)+\frac{b_{k}}{e-1}\left(\ln\beta-\ln
b_{k}\right)+\frac{b_{k}\beta}{e(e-1)}\left(\frac{1}{b_{k}}-\frac{1}{\beta}\right)$
$\displaystyle\quad-\frac{b_{k}}{e(e-1)}\left(\ln\beta-\ln
b_{k}\right)-\frac{1}{\beta}\ln\frac{\beta}{b_{k}}$
$\displaystyle=\frac{b_{k}}{e}+\frac{b_{k}}{e}\ln\frac{\beta}{b_{k}}-\frac{1}{\beta}\ln\frac{\beta}{b_{k}}$
$\displaystyle\geq\frac{b_{k}}{e}\quad\text{increasing
with}~{}\beta~{}(\beta=b_{k}).$

In the scenario where $j^{*}=1$, we observe that

$\displaystyle\mathbb{E}[\operatorname{SOL}_{k}]$
$\displaystyle=\int_{\beta}^{b_{k}e}\left[\frac{b_{k}}{\alpha(e-1)}\alpha+\frac{b_{k}}{\alpha
e(e-1)}(\beta e-\alpha)-\frac{1}{\beta e}\ln e\right]\frac{1}{\alpha}d\alpha$
$\displaystyle\quad+\int_{b_{k}}^{\beta}\left[\frac{b_{k}}{\alpha(e-1)}\alpha+\frac{b_{k}}{\alpha
e(e-1)}(\alpha e-\alpha)+\frac{b_{k}}{\alpha e^{3}}(\beta e-\alpha
e)-\frac{1}{\beta e}\ln\frac{e^{3}}{e-1}\right]\frac{1}{\alpha}d\alpha$
$\displaystyle=\frac{b_{k}}{e-1}\ln\frac{b_{k}e}{\beta}+\frac{b_{k}\beta}{e-1}\left(\frac{1}{\beta}-\frac{1}{b_{k}e}\right)-\frac{b_{k}}{e(e-1)}\ln\frac{b_{k}e}{\beta}-\frac{1}{\beta
e}\ln\frac{b_{k}e}{\beta}$
$\displaystyle\quad+\frac{b_{k}}{e-1}\ln\frac{\beta}{b_{k}}+\frac{b_{k}}{e}\ln\frac{\beta}{b_{k}}+\frac{b_{k}\beta}{e^{2}}\left(\frac{1}{b_{k}}-\frac{1}{\beta}\right)-\frac{b_{k}}{e^{2}}\ln\frac{\beta}{b_{k}}-\frac{1}{\beta
e}\ln\frac{e^{3}}{e-1}\ln\frac{\beta}{b_{k}}$
$\displaystyle=\frac{b_{k}}{e}\ln\frac{b_{k}e}{\beta}+\frac{b_{k}}{e-1}-\frac{\beta}{e(e-1)}-\frac{1}{\beta
e}\ln\frac{b_{k}e}{\beta}$
$\displaystyle\quad+\frac{b_{k}}{e-1}\ln\frac{\beta}{b_{k}}+\frac{b_{k}}{e}\ln\frac{\beta}{b_{k}}+\frac{\beta}{e^{2}}-\frac{b_{k}}{e^{2}}-\frac{b_{k}}{e^{2}}\ln\frac{\beta}{b_{k}}-\frac{1}{\beta
e}\ln\frac{e^{3}}{e-1}\ln\frac{\beta}{b_{k}}$
$\displaystyle\geq\frac{b_{k}}{e}+\frac{b_{k}}{e-1}-\frac{b_{k}}{e(e-1)}-\frac{1}{b_{k}e}\quad\text{increasing
with}~{}\beta~{}(\beta=b_{k})$
$\displaystyle=\frac{2b_{k}}{e}-\frac{1}{b_{k}e}.$

Subroutine 3

In the scenarios where $T>b_{k}e^{2}$, we consider two cases: (1) $j^{*}\geq
1$ and (2) $j^{*}=0$.

Let us first consider the case where $j^{*}\geq 1$. If $\alpha\geq\beta$, the
algorithm stops at the $j^{*}+1$th round by design of the algorithm ($\alpha
e^{j^{*}}\geq\beta e^{j^{*}}$); on the other hand, if $\alpha<\beta$, the
algorithm stops at the $j^{*}+2$th round ($\alpha e^{j^{*}+1}\geq\beta
e^{j^{*}}$). The objective function when $\alpha\geq\beta$ is

$\displaystyle\text{SOL}_{k,1}$
$\displaystyle=\sum_{j=1}^{j^{*}}\frac{b_{k}\left(1-\frac{1}{e}\right)^{j-2}}{\alpha
e^{j}}\left(\alpha e^{j-1}-\alpha
e^{j-2}\right)+\frac{b_{k}\left(1-\frac{1}{e}\right)^{j^{*}-1}}{\alpha
e^{j^{*}+1}}\left(\beta e^{j^{*}}-\alpha e^{j^{*}-1}\right)-\frac{1}{\beta
e^{j^{*}}}\ln\frac{e^{2j^{*}-1}}{(e-1)^{j^{*}-1}}$
$\displaystyle=\sum_{j=1}^{j^{*}}\frac{b_{k}(e-1)^{j-1}}{e^{j}}+\frac{b_{k}(e-1)^{j^{*}-1}}{e^{j^{*}+1}}\frac{\beta
e-\alpha}{\alpha}-\frac{1}{\beta
e^{j^{*}}}\ln\frac{e^{2j^{*}-1}}{(e-1)^{j^{*}-1}}$
$\displaystyle=b_{k}\left(1-\left(1-\frac{1}{e}\right)^{j^{*}}\right)+\frac{b_{k}(e-1)^{j^{*}-1}}{e^{j^{*}+1}}\frac{\beta
e-\alpha}{\alpha}-\frac{1}{\beta
e^{j^{*}}}\ln\frac{e^{2j^{*}-1}}{(e-1)^{j^{*}-1}}.$

The objective function when $\alpha<\beta$ is

$\displaystyle\text{SOL}_{k,2}$
$\displaystyle=\sum_{j=1}^{j^{*}+1}\frac{b_{k}\left(1-\frac{1}{e}\right)^{j-2}}{\alpha
e^{j}}\left(\alpha e^{j-1}-\alpha
e^{j-2}\right)+\frac{b_{k}\left(1-\frac{1}{e}\right)^{j^{*}}}{\alpha
e^{j^{*}+2}}\left(\beta e^{j*}-\alpha e^{j*}\right)-\frac{1}{\beta
e^{j^{*}}}\ln\frac{e^{2j^{*}+1}}{(e-1)^{j^{*}}}$
$\displaystyle=\sum_{j=1}^{j^{*}+1}\frac{b_{k}(e-1)^{j-1}}{e^{j}}+\frac{b_{k}(e-1)^{j*}}{e^{j^{*}+2}}\frac{\beta-\alpha}{\alpha}-\frac{1}{\beta
e^{j^{*}}}\ln\frac{e^{2j^{*}+1}}{(e-1)^{j^{*}}}$
$\displaystyle=b_{k}\left(1-\left(1-\frac{1}{e}\right)^{j^{*}+1}\right)+\frac{b_{k}(e-1)^{j^{*}}}{e^{j^{*}+2}}\frac{\beta-\alpha}{\alpha}-\frac{1}{\beta
e^{j^{*}}}\ln\frac{e^{2j^{*}+1}}{(e-1)^{j^{*}}}.$

The expected value of our solution is

$\mathbb{E}[\operatorname{SOL}_{k}]=\int_{\beta}^{b_{k}e}\operatorname{SOL}_{k,1}f(\alpha)d\alpha+\int_{b_{k}}^{\beta}\operatorname{SOL}_{k,2}f(\alpha)d\alpha.$
(4)

Notice that

$\displaystyle\int_{\beta}^{b_{k}e}\operatorname{SOL}_{k,1}f(\alpha)d\alpha$
$\displaystyle=b_{k}\left(1-\left(1-\frac{1}{e}\right)^{j^{*}}\right)\int_{\beta}^{b_{k}e}\frac{1}{\alpha}d\alpha+\frac{b_{k}(e-1)^{j^{*}-1}}{e^{j^{*}+1}}\int_{\beta}^{b_{k}e}\frac{\beta
e-\alpha}{\alpha}\frac{1}{\alpha}d\alpha$ $\displaystyle-\left[\frac{1}{\beta
e^{j^{*}}}\ln\frac{e^{2j^{*}-1}}{(e-1)^{j^{*}-1}}\right]\int_{\beta}^{b_{k}e}\frac{1}{\alpha}d\alpha$
$\displaystyle=b_{k}\left(1-\left(1-\frac{1}{e}\right)^{j^{*}}\right)\ln\frac{b_{k}e}{\beta}+\frac{b_{k}(e-1)^{j^{*}-1}}{e^{j^{*}+1}}\left(e-\frac{\beta}{b_{k}}-\ln\frac{b_{k}e}{\beta}\right)$
$\displaystyle-\left[\frac{1}{\beta
e^{j^{*}}}\ln\frac{e^{2j^{*}-1}}{(e-1)^{j^{*}-1}}\right]\ln\frac{b_{k}e}{\beta}.$

and

$\displaystyle\int_{b_{k}}^{\beta}\operatorname{SOL}_{k,2}f(\alpha)d\alpha$
$\displaystyle=b_{k}\left(1-\left(1-\frac{1}{e}\right)^{j^{*}+1}\right)\int_{b_{k}}^{\beta}\frac{1}{\alpha}d\alpha+\frac{b_{k}(e-1)^{j^{*}}}{e^{j^{*}+2}}\int_{b_{k}}^{\beta}\frac{\beta-\alpha}{\alpha}\frac{1}{\alpha}d\alpha$
$\displaystyle-\left[\frac{1}{\beta
e^{j^{*}}}\ln\frac{e^{2j^{*}+1}}{(e-1)^{j^{*}}}\right]\int_{b_{k}}^{\beta}\frac{1}{\alpha}d\alpha$
$\displaystyle=b_{k}\left(1-\left(1-\frac{1}{e}\right)^{j^{*}+1}\right)\ln\frac{\beta}{b_{k}}+\frac{b_{k}(e-1)^{j^{*}}}{e^{j*+2}}\left(\frac{\beta}{b_{k}}-1-\ln\frac{\beta}{b_{k}}\right)$
$\displaystyle-\left[\frac{1}{\beta
e^{j^{*}}}\ln\frac{e^{2j^{*}+1}}{(e-1)^{j^{*}}}\right]\ln\frac{\beta}{b_{k}}.$

Hence,

$\displaystyle\mathbb{E}[\operatorname{SOL}_{k}]$
$\displaystyle=b_{k}\left(1-\left(1-\frac{1}{e}\right)^{j^{*}}\right)\ln\frac{b_{k}e}{\beta}+b_{k}\left(1-\left(1-\frac{1}{e}\right)^{j^{*}+1}\right)\ln\frac{\beta}{b_{k}}$
$\displaystyle+\frac{b_{k}(e-1)^{j^{*}-1}}{e^{j^{*}+1}}\left(e-\frac{\beta}{b_{k}}-\ln\frac{b_{k}e}{\beta}\right)+\frac{b_{k}(e-1)^{j^{*}}}{e^{j*+2}}\left(\frac{\beta}{b_{k}}-1-\ln\frac{\beta}{b_{k}}\right)$
$\displaystyle-\left[\frac{1}{\beta
e^{j^{*}}}\ln\frac{e^{2j^{*}-1}}{(e-1)^{j^{*}-1}}\right]\ln\frac{b_{k}e}{\beta}-\left[\frac{1}{\beta
e^{j^{*}}}\ln\frac{e^{2j^{*}+1}}{(e-1)^{j^{*}}}\right]\ln\frac{\beta}{b_{k}}$
$\displaystyle=b_{k}-b_{k}\left(1-\frac{1}{e}\right)^{j^{*}}\left[\ln\frac{b_{k}e}{\beta}+\left(1-\frac{1}{e}\right)\ln\frac{\beta}{b_{k}}\right]$
$\displaystyle+\frac{b_{k}(e-1)^{j^{*}-1}}{e^{j^{*}+1}}\left[e-\frac{\beta}{b_{k}}-\ln\frac{b_{k}e}{\beta}+\frac{e-1}{e}\left(\frac{\beta}{b_{k}}-1-\ln\frac{\beta}{b_{k}}\right)\right]$
$\displaystyle-\left[\frac{1}{\beta
e^{j^{*}}}\ln\frac{e^{2j^{*}-1}}{(e-1)^{j^{*}-1}}\right]\ln\frac{b_{k}e}{\beta}-\left[\frac{1}{\beta
e^{j^{*}}}\ln\frac{e^{2j^{*}+1}}{(e-1)^{j^{*}}}\right]\ln\frac{\beta}{b_{k}}$
$\displaystyle\geq
b_{k}-b_{k}\left(1-\frac{1}{e}\right)^{j^{*}}+b_{k}\left(1-\frac{1}{e}\right)^{j^{*}}\frac{e-2}{e(e-1)}-\frac{1}{b_{k}e^{j^{*}}}\ln\frac{e^{2j^{*}-1}}{(e-1)^{j^{*}-1}}\quad\text{increasing
with}~{}\beta~{}(\beta=b_{k}).$

For the cases where $j^{*}=0$, it follows that

$\displaystyle\mathbb{E}[\operatorname{SOL}_{k}]$
$\displaystyle=\int_{\beta}^{b_{k}e}\frac{b_{k}}{\alpha
e}\beta\frac{1}{\alpha}d\alpha+\int_{b_{k}}^{\beta}\left[\frac{b_{k}}{\alpha
e}\alpha+\frac{b_{k}}{\alpha e^{2}}(\beta-\alpha)-\frac{1}{\beta}\ln
e\right]\frac{1}{\alpha}d\alpha$
$\displaystyle=\frac{b_{k}\beta}{e}(\frac{1}{\beta}-\frac{1}{b_{k}e})+\frac{b_{k}}{e}\ln\frac{\beta}{b_{k}}+\frac{b_{k}\beta}{e^{2}}(\frac{1}{b_{k}}-\frac{1}{\beta})-\frac{b_{k}}{e^{2}}\ln\frac{\beta}{b_{k}}-\frac{1}{\beta}\ln\frac{\beta}{b_{k}}$
$\displaystyle=\frac{b_{k}}{e}-\frac{\beta}{e^{2}}+\frac{\beta}{e^{2}}-\frac{b_{k}}{e^{2}}+(\frac{b_{k}}{e}-\frac{b_{k}}{e^{2}})\ln\frac{\beta}{b_{k}}-\frac{1}{\beta}\ln\frac{\beta}{b_{k}}$
$\displaystyle\geq
b_{k}\left(\frac{1}{e}-\frac{1}{e^{2}}\right)\quad\text{increasing
with}~{}\beta~{}(\beta=b_{k}).$

By combining the above results, we establish Theorem 3.2. ∎

##  Appendix B Proof for Algorithm 2

###  B.1 Proof of Lemma 4.1: Budget constraint

###### Proof.

We prove that the budget constraint is satisfied in expectation under each
subroutine in Algorithm 2.

Subroutine 4

Let us suppose that $\tau_{k}=L_{k}+\beta e^{j^{*}}$ for some
$j^{*}\in\mathbb{Z}^{+}$ and $\beta\in[b_{k},b_{k}e]$. Note that this
implicitly implies that $\tau_{k}\geq L_{k}+b_{k}$, as we only consider the
worst case where $\tau_{k}^{*}$ is large enough. Further, under the condition
$U_{k}\leq b_{k}e$ or $\delta\leq b_{k}(e-1)$, we have $j^{*}=0$.

Let $\delta=U_{k}-L_{k}$. We consider the cases $\delta>b_{k}$, and if this is
not the case, the algorithm would consistently use
$p_{k,i_{k}}=\frac{b_{k}}{U_{k}}$. When $\delta>b_{k}$ and
$\alpha\in[b_{k},\delta]$, the algorithm begins by setting
$p_{k,i_{k}}=\frac{b_{k}}{\alpha+L_{k}}$ and then continue with
$p_{k,i_{k}}=\frac{b_{k}}{U_{k}}$ for the second round if $\tau_{k}^{*}$ is
large enough; otherwise, the algorithm sets $p_{k,i_{k}}=\frac{b_{k}}{U_{k}}$
all the time. We therefore have

$\displaystyle\mathbb{E}[\operatorname{Budget}_{k}]$
$\displaystyle=\int_{b_{k}}^{\beta}\left[\frac{b_{k}}{L_{k}+\alpha}(L_{k}+\alpha)+\frac{b_{k}}{U_{k}}(L_{k}+\beta-
L_{k}-\alpha)\right]\frac{1}{\alpha}d\alpha+\int_{\beta}^{\delta}\frac{b_{k}}{L_{k}+\alpha}(L_{k}+\beta)\frac{1}{\alpha}d\alpha+\int_{\delta}^{b_{k}e}\frac{b_{k}}{U_{k}}(L_{k}+\beta)\frac{1}{\alpha}d\alpha$
$\displaystyle=b_{k}\ln\frac{\beta}{b_{k}}+\frac{b_{k}\beta}{U_{k}}\ln\frac{\beta}{b_{k}}-\frac{b_{k}}{U_{k}}(\beta-
b_{k})+\frac{b_{k}(L_{k}+\beta)}{L_{k}}(\ln\frac{\delta}{\beta}-\ln\frac{L_{k}+\delta}{L_{k}+\beta})+\frac{b_{k}(L_{k}+\beta)}{U_{k}}\ln\frac{b_{k}e}{\delta}$
$\displaystyle\leq
b_{k}\ln\frac{U_{k}-L_{k}}{b_{k}}+\frac{b_{k}(U_{k}-L_{k})}{U_{k}}\ln\frac{U_{k}-L_{k}}{b_{k}}-\frac{b_{k}}{U_{k}}(U_{k}-L_{k}-b_{k})+\frac{b_{k}U_{k}}{U_{k}}\ln\frac{b_{k}e}{\delta}\quad\text{increasing
with}~{}\beta~{}(\beta=U_{k}-L_{k})$ $\displaystyle\leq
b_{k}\ln(e-1)+\frac{b_{k}(b_{k}(e-1))}{L_{k}+b_{k}(e-1)}\ln(e-1)-\frac{b_{k}^{2}}{L_{k}+b_{k}(e-1)}(e-2)+b_{k}\ln\frac{b_{k}e}{b_{k}(e-1)}$
$\displaystyle\quad\text{increasing with}~{}U_{k}~{}(U_{k}=L_{k}+b_{k}(e-1))$
$\displaystyle\leq
b_{k}\ln(e-1)+b_{k}\frac{e-1}{e}\ln(e-1)-\frac{b_{k}}{e}(e-2))+b_{k}\ln\frac{e}{e-1}\quad\text{decreasing
with}~{}L_{k}~{}(L_{k}=b_{k})$ $\displaystyle\leq
b_{k}+b_{k}(\frac{e-1}{e}\ln(e-1)-\frac{e-2}{e})$ $\displaystyle\approx b_{k}$

Subroutine 5

Similarly, we assume $\tau_{k}^{*}=L_{k}+\beta e^{j^{*}}$. Under the condition
that $\delta\leq b_{k}(e+1)$, we have $j^{*}=1$ or $j^{*}=0$. We only consider
the worst case $j^{*}=1$.

Let $\kappa=\frac{\delta}{e}$. Note that, when $\alpha\in[b_{k},\kappa)$, the
algorithm first sets $p_{k,i_{k}}=\frac{b_{k}}{L_{k}+\alpha e}$, and then
transits to $p_{k,i_{k}}=\frac{b_{k}}{U_{k}}$ at the second stage. However,
when $\alpha\in[\kappa,b_{k}e]$, the algorithm keeps setting
$p_{k,i_{k}}=\frac{b_{k}}{U_{k}}$. We therefore have

$\displaystyle\mathbb{E}[\operatorname{Budget}_{k}]$
$\displaystyle=\int_{b_{k}}^{\kappa}\left[\frac{b_{k}}{L_{k}+\alpha
e}(L_{k}+\alpha)+\frac{b_{k}}{U_{k}}(L_{k}+\beta
e-L_{k}-\alpha)\right]\frac{1}{\alpha}d\alpha+\int_{\kappa}^{b_{k}e}\frac{b_{k}}{U_{k}}(L_{k}+\beta
e)\frac{1}{\alpha}d\alpha$
$\displaystyle=b_{k}\left(\ln\frac{\kappa}{b_{k}}+(\frac{1}{e}-1)\ln\frac{L_{k}+\kappa
e}{L_{k}+b_{k}e}\right)+\frac{b_{k}}{U_{k}}\beta
e\ln\frac{\kappa}{b_{k}}-\frac{b_{k}}{U_{k}}(\kappa-b_{k})+\frac{b_{k}(\beta
e+L_{k})}{U_{k}}\ln\frac{b_{k}e}{\kappa}$ $\displaystyle\leq
b_{k}\left(\ln\frac{\kappa}{b_{k}}+(\frac{1}{e}-1)\ln\frac{L_{k}+\kappa
e}{L_{k}+b_{k}e}\right)+\frac{b_{k}}{U_{k}}(U_{k}-L_{k})\ln\frac{\kappa}{b_{k}}-\frac{b_{k}}{U_{k}}(\kappa-
b_{k})+b_{k}\ln\frac{b_{k}e}{\kappa}$ $\displaystyle\quad\text{increasing
with}~{}\beta~{}(\beta=(U_{k}-L_{k})/e)$ $\displaystyle\leq
b_{k}+b_{k}(\frac{1}{e}-1)\ln\frac{L_{k}+b_{k}(e+1)}{L_{k}+b_{k}e}+\frac{b_{k}^{2}}{L_{k}+b_{k}(e+1)}(e+1)\ln\frac{e+1}{e}-\frac{b_{k}^{2}}{L_{k}+b_{k}(e+1)}(\frac{e+1}{e}-1)$
$\displaystyle\quad\text{increasing with}~{}U_{k}~{}(U_{k}=L_{k}+b_{k}(e+1))$
$\displaystyle\leq
b_{k}+b_{k}(\frac{1-e}{e}\ln\frac{e+2}{e+1}+\frac{e+1}{e+2}\ln\frac{e+1}{e}-\frac{1}{e(e+2)})\quad\text{decreasing
with}~{}L_{k}~{}(L_{k}=b_{k})$ $\displaystyle\approx b_{k}$

Subroutine 6

Under the assumption of $\tau_{k}^{*}=L_{k}+\beta e^{j^{*}}$, and given the
condition $U_{k}>b_{k}e^{2}$, it is possible for $j^{*}$ to be $0$ or to
extend to infinity. We only focus on the worst-case scenario, i.e., $j^{*}\geq
1$.

$\displaystyle\mathbb{E}[\operatorname{Budget}_{k}]$
$\displaystyle=\int_{\beta}^{b_{k}e}\Bigg{[}\frac{b_{k}}{L_{k}+\alpha(e-1)}(L_{k}+\alpha)+b_{k}\left(1-\frac{L_{k}+\alpha-
b_{k}}{L_{k}+\alpha(e-1)}\right)\sum_{j=2}^{j^{*}}\frac{(1-1/e)^{j-2}}{\alpha
e^{j}}(\alpha e^{j-1}-\alpha e^{j-2})$
$\displaystyle\quad+b_{k}\left(1-\frac{L_{k}+\alpha-
b_{k}}{L_{k}+\alpha(e-1)}\right)\frac{(1-1/e)^{j^{*}-1}}{\alpha
e^{j^{*}+1}}(L_{k}+\beta e^{j^{*}}-L_{k}-\alpha
e^{j^{*}-1})\Bigg{]}\frac{1}{\alpha}d\alpha$
$\displaystyle\quad+\int_{b_{k}}^{\beta}\Bigg{[}\frac{b_{k}}{L_{k}+\alpha(e-1)}(L_{k}+\alpha)+b_{k}\left(1-\frac{L_{k}+\alpha-
b_{k}}{L_{k}+\alpha(e-1)}\right)\sum_{j=2}^{j^{*}+1}\frac{(1-1/e)^{j-2}}{\alpha
e^{j}}(\alpha e^{j-1}-\alpha e^{j-2})$
$\displaystyle\quad+b_{k}\left(1-\frac{L_{k}+\alpha-
b_{k}}{L_{k}+\alpha(e-1)}\right)\frac{(1-1/e)^{j^{*}}}{\alpha
e^{j^{*}+2}}(L_{k}+\beta e^{j^{*}}-L_{k}-\alpha
e^{j^{*}})\Bigg{]}\frac{1}{\alpha}d\alpha$ $\displaystyle\leq
b_{k}\left(\ln\frac{b_{k}e}{\beta}+(\frac{1}{e-1}-1)\ln\frac{L_{k}+b_{k}e(e-1)}{L_{k}+\beta(e-1)}\right)+b_{k}(1-\frac{1}{e}-(1-\frac{1}{e})^{j^{*}})\frac{e-2}{e-1}\ln\frac{L_{k}+b_{k}e(e-1)}{L_{k}+\beta(e-1)}$
$\displaystyle\quad+b_{k}(1-\frac{1}{e}-(1-\frac{1}{e})^{j^{*}})\frac{b_{k}}{L_{k}}\left(\ln\frac{b_{k}e}{\beta}-\frac{L_{k}+b_{k}e(e-1)}{L_{k}+\beta(e-1)}\right)$
$\displaystyle\quad+b_{k}\beta
e^{j^{*}}\frac{(e-1)^{j^{*}}}{e^{2j^{*}}}\frac{1}{L_{k}}\left(\ln\frac{b_{k}e}{\beta}-\ln\frac{L_{k}+b_{k}e(e-1)}{L_{k}+\beta(e-1)}\right)-b_{k}\frac{(e-1)^{j^{*}-1}}{e^{j^{*}+1}}\ln\frac{L_{k}+b_{k}e(e-1)}{L_{k}+\beta(e-1)}$
$\displaystyle\quad+b_{k}\left(\ln\frac{\beta}{b_{k}}+(\frac{1}{e-1}-1)\ln\frac{L_{k}+\beta(e-1)}{L_{k}+b_{k}(e-1)}\right)+b_{k}(1-\frac{1}{e}-(1-\frac{1}{e})^{j^{*}+1})\frac{e-2}{e-1}\ln\frac{L_{k}+\beta(e-1)}{L_{k}+b_{k}(e-1)}$
$\displaystyle\quad+b_{k}(1-\frac{1}{e}-(1-\frac{1}{e})^{j^{*}})\frac{b_{k}}{L_{k}}\left(\ln\frac{\beta}{b_{k}}-\frac{L_{k}+\beta(e-1)}{L_{k}+b_{k}(e-1)}\right)$
$\displaystyle\quad+b_{k}\beta
e^{j^{*}}\frac{(e-1)^{j^{*}+1}}{e^{2j^{*}+2}}\frac{1}{L_{k}}\left(\ln\frac{\beta}{b_{k}}-\ln\frac{L_{k}+\beta(e-1)}{L_{k}+b_{k}(e-1)}\right)-b_{k}\frac{(e-1)^{j^{*}}}{e^{j^{*}+2}}\ln\frac{L_{k}+\beta(e-1)}{L_{k}+b_{k}(e-1)}$
$\displaystyle\leq
b_{k}\left(1+(\frac{1}{e-1}-1)\ln\frac{L_{k}+b_{k}e(e-1)}{L_{k}+b_{k}(e-1)}\right)+b_{k}(1-\frac{1}{e}-(1-\frac{1}{e})^{j^{*}+1})\frac{e-2}{e-1}\ln\frac{L_{k}+b_{k}e(e-1)}{L_{k}+b_{k}(e-1)}$
$\displaystyle\quad+b_{k}(1-\frac{1}{e}-(1-\frac{1}{e})^{j^{*}})\frac{b_{k}}{L_{k}}\left(1-\frac{L_{k}+b_{k}e(e-1)}{L_{k}+b_{k}(e-1)}\right)$
$\displaystyle\quad+b_{k}^{2}\frac{(e-1)^{j^{*}+1}}{e^{j^{*}+1}}\frac{1}{L_{k}}\left(1-\ln\frac{L_{k}+b_{k}e(e-1)}{L_{k}+b_{k}(e-1)}\right)-b_{k}\frac{(e-1)^{j^{*}}}{e^{j^{*}+2}}\ln\frac{L_{k}+b_{k}e(e-1)}{L_{k}+b_{k}(e-1)}$
$\displaystyle\quad\text{increasing with}~{}\beta~{}(\beta=b_{k}e)$
$\displaystyle\leq
b_{k}\left(1+(\frac{1}{e-1}-1)\ln\frac{L_{k}+b_{k}e(e-1)}{L_{k}+b_{k}(e-1)}\right)+b_{k}\frac{e-2}{e}\ln\frac{L_{k}+b_{k}e(e-1)}{L_{k}+b_{k}(e-1)}+b_{k}(1-\frac{1}{e})\frac{b_{k}}{L_{k}}\left(1-\ln\frac{L_{k}+b_{k}e(e-1)}{L_{k}+b_{k}(e-1)}\right)$
$\displaystyle\approx b_{k}$

Combining the above results with the proof of Subroutine 2, presented in
Appendix A.1, establishes Lemma 4.1. ∎

###  B.2 Proof of Theorem 4.2: Consistency and Robustness

###### Proof.

We begin with the proof of consistency and then proceed to the analysis of
robustness.

Consistency Analysis It is straightforward to show that our algorithm is $1$\-
consistent. When the width of the predictive interval is zero, meaning that
$L_{k}=U_{k}=\tau_{k}^{*}$, we have

$\displaystyle\mathbb{E}[\operatorname{SOL_{k}}]=\frac{b_{k}}{U_{k}}\tau_{k}^{*}=b_{k}.$

Robustness Analysis Below we show the robustness of our algorithm under each
subroutine.

Subroutine 4

For cases where $\delta=U_{k}-L_{k}\leq b_{k}$, the algorithm proceeds with
$p_{k,i_{k}}=\frac{b_{k}}{U_{k}}$. Hence, we have

$\displaystyle\mathbb{E}[\operatorname{SOL_{k}}]=\frac{b_{k}}{U_{k}}\beta\geq\frac{b_{k}}{L_{k}+b_{k}}L_{k}\geq\frac{b_{k}}{2}.$

Next, we consider the case where $b_{k}(e-1)\geq\delta>b_{k}$, further divided
into $\tau_{k}^{*}<L_{k}+b_{k}$ and $\tau_{k}^{*}\geq L_{k}+b_{k}$.

For the situation where $\tau_{k}^{*}<L_{k}+b_{k}$, the algorithm stops at the
first stage. If $\delta>\alpha$, the algorithm uses
$p_{k,i_{k}}=\frac{b_{k}}{L_{k}+\alpha}$, and if $\delta\leq\alpha$, the
algorithm sets $p_{k,i_{k}}=\frac{b_{k}}{U_{k}}$. Therefore, we have

$\displaystyle\mathbb{E}[\operatorname{SOL_{k}}]$
$\displaystyle=\int_{b_{k}}^{\delta}\left[\frac{b_{k}}{L_{k}+\alpha}\tau_{k}^{*}\right]\frac{1}{\alpha}d\alpha+\int_{\delta}^{b_{k}e}\frac{b_{k}}{U_{k}}\tau_{k}^{*}\frac{1}{\alpha}d\alpha$
$\displaystyle=\frac{b_{k}\tau_{k}^{*}}{L_{k}}\left(\ln\frac{\delta}{b_{k}}-\ln\frac{L_{k}+\delta}{L_{k}+b_{k}}\right)+\frac{b_{k}\tau_{k}^{*}}{U_{k}}\ln\frac{b_{k}e}{\delta}$
$\displaystyle\geq
b_{k}\left(\ln\frac{\delta}{b_{k}}-\ln\frac{L_{k}+\delta}{L_{k}+b_{k}}\right)+\frac{b_{k}L_{k}}{U_{k}}\ln\frac{b_{k}e}{\delta}\quad\text{increasing
with}~{}\tau_{k}^{*}~{}(\tau_{k}^{*}=L_{k})$ $\displaystyle\geq
b_{k}\left(\ln(e-1)-\ln\frac{L_{k}+b_{k}(e-1)}{L_{k}+b_{k}}\right)+\frac{b_{k}L_{k}}{L_{k}+b_{k}(e-1)}\ln\frac{e}{e-1}\quad\text{decreasing
with}~{}U_{k}~{}(U_{k}=L_{k}+b_{k}(e-1))$ $\displaystyle\geq
b_{k}\left(\ln(e-1)-\ln\frac{e}{2}\right)+b_{k}\frac{1}{e}\ln\frac{e}{e-1}\quad\text{increasing
with}~{}L_{k}~{}(L_{k}=b_{k})$
$\displaystyle=b_{k}\left(\ln\frac{2(e-1)}{e}+\frac{1}{e}\ln\frac{e}{e-1}\right)$

For cases where $\tau_{k}^{*}\geq L_{k}+b_{k}$, let us suppose
$\tau_{k}^{*}=L_{k}+\beta e^{j^{*}}$ where $\beta\in[b_{k},b_{k}e]$. Under the
condition $U_{k}\leq b_{k}e$ or $\delta\leq b_{k}(e-1)$, we have $j^{*}=0$.
Further, since $L_{k}+\beta\leq U_{k}$, we have $\beta\leq U_{k}-L_{k}$. It
follows that

$\displaystyle\mathbb{E}[\operatorname{SOL_{k}}]$
$\displaystyle=\int_{b_{k}}^{\beta}\left[\frac{b_{k}}{L_{k}+\alpha}(L_{k}+\alpha)+\frac{b_{k}}{U_{k}}(L_{k}+\beta-
L_{k}-\alpha)-\frac{1}{L_{k}+\beta}\ln\frac{U_{k}}{L_{k}+\alpha}\right]\frac{1}{\alpha}d\alpha$
$\displaystyle\quad+\int_{\beta}^{\delta}\frac{b_{k}}{L_{k}+\alpha}(L_{k}+\beta)\frac{1}{\alpha}d\alpha+\int_{\delta}^{b_{k}e}\frac{b_{k}}{U_{k}}(L_{k}+\beta)\frac{1}{\alpha}d\alpha$
$\displaystyle=b_{k}\ln\frac{\beta}{b_{k}}+\frac{b_{k}\beta}{U_{k}}\ln\frac{\beta}{b_{k}}-\frac{b_{k}}{U_{k}}(\beta-
b_{k})-\frac{1}{L_{k}+\beta}\ln\frac{e}{2}\ln\frac{\beta}{b_{k}}+\frac{b_{k}(L_{k}+\beta)}{L_{k}}(\ln\frac{\delta}{\beta}-\ln\frac{L_{k}+\delta}{L_{k}+\beta})+\frac{b_{k}(L_{k}+\beta)}{U_{k}}\ln\frac{b_{k}e}{\delta}$
$\displaystyle\geq\frac{b_{k}(L_{k}+b_{k})}{L_{k}}\left(\ln\frac{U_{k}-L_{k}}{b_{k}}-\ln\frac{U_{k}}{L_{k}+b_{k}}\right)+\frac{b_{k}(L_{k}+b_{k})}{U_{k}}\ln\frac{b_{k}e}{U_{k}-L_{k}}\quad\text{increasing
with}~{}\beta~{}(\beta=b_{k})$
$\displaystyle\geq\frac{b_{k}(L_{k}+b_{k})}{L_{k}}\left(\ln(e-1)-\ln\frac{L_{k}+b_{k}(e-1)}{L_{k}+b_{k}}\right)+\frac{b_{k}(L_{k}+b_{k})}{L_{k}+b_{k}(e-1)}\ln\frac{e}{e-1}$
$\displaystyle\quad\text{decreasing with}~{}U_{k}~{}(U_{k}=L_{k}+b_{k}(e-1))$
$\displaystyle\geq
2b_{k}\ln\frac{2(e-1)}{e}+b_{k}\frac{2}{e}\ln\frac{e}{e-1}\quad\text{increasing
with}~{}L_{k}~{}(L_{k}=b_{k})$
$\displaystyle=b_{k}(2\ln\frac{2(e-1)}{e}+\frac{2}{e}\ln\frac{e}{e-1})$

Subroutine 5

For the situation where $\delta=U_{k}-L_{k}\leq b_{k}e$, the algorithm’s
procedure involves setting $p_{k,i_{k}}=\frac{b_{k}}{U_{k}}$. Hence, we have

$\displaystyle\mathbb{E}[\operatorname{SOL_{k}}]=\frac{b_{k}}{U_{k}}\tau_{k}^{*}\geq\frac{b_{k}}{L_{k}+b_{k}e}L_{k}\geq\frac{b_{k}}{e+1}.$

Next, we consider the case where $b_{k}(e+1)\geq\delta>b_{k}e$, further
divided into $\tau_{k}^{*}<L_{k}+b_{k}$ and $\tau_{k}^{*}\geq L_{k}+b_{k}$. We
first discuss the situation under $\tau_{k}^{*}<L_{k}+b_{k}$, where

$\displaystyle\mathbb{E}[\operatorname{SOL_{k}}]$
$\displaystyle=\int_{b_{k}}^{\kappa}\left[\frac{b_{k}}{L_{k}+\alpha
e}\tau_{k}^{*}\right]\frac{1}{\alpha}d\alpha+\int_{\kappa}^{b_{k}e}\frac{b_{k}}{U_{k}}\tau_{k}^{*}\frac{1}{\alpha}d\alpha$
$\displaystyle=\frac{b_{k}\tau_{k}^{*}}{L_{k}}\left(\ln\frac{\kappa}{b_{k}}-\ln\frac{L_{k}+\kappa
e}{L_{k}+b_{k}e}\right)+\frac{b_{k}\tau_{k}^{*}}{U_{k}}\ln\frac{b_{k}e}{\kappa}$
$\displaystyle\geq b_{k}\left(\ln\frac{\kappa}{b_{k}}-\ln\frac{L_{k}+\kappa
e}{L_{k}+b_{k}e}\right)+\frac{b_{k}L_{k}}{U_{k}}\ln\frac{b_{k}e}{\kappa}\quad\text{increasing
with}~{}\tau_{k}^{*}~{}(\tau_{k}^{*}=L_{k})$ $\displaystyle\geq
b_{k}\left(\ln\frac{e+1}{e}-\ln\frac{L_{k}+b_{k}(e+1)}{L_{k}+b_{k}e}\right)+\frac{b_{k}L_{k}}{L_{k}+b_{k}(e+1)}\ln\frac{e^{2}}{e+1}\quad\text{decreasing
with}~{}U_{k}~{}(U_{k}=L_{k}+b_{k}(e+1))$ $\displaystyle\geq
b_{k}\left(\ln\frac{e+1}{e}-\ln\frac{e^{2}}{e^{2}-1}\right)+b_{k}\frac{e^{2}-e-1}{e^{2}}\ln\frac{e^{2}}{e+1}\quad\text{increasing
with}~{}L_{k}~{}(L_{k}=b_{k}(e^{2}-e-1))$
$\displaystyle=b_{k}\left(\ln\frac{e+1}{e}-\ln\frac{e^{2}}{e^{2}-1}+\frac{e^{2}-e-1}{e^{2}}\ln\frac{e^{2}}{e+1}\right)$

For situations with $\tau_{k}^{*}\geq L_{k}+b_{k}$, suppose
$\tau_{k}^{*}=L_{k}+\beta e^{j^{*}}$ where $\beta\in[b_{k},b_{k}e]$. Notice
that when $j^{*}\geq 1$ or $\beta\geq\kappa$, Algorithm 2 first assign
$p_{k,i_{k}}=\frac{b_{k}}{L_{k}+\alpha e}$ for a time length of
$L_{k}+\alpha$, and then proceeds with $p_{k,i_{k}}=\frac{b_{k}}{U_{k}}$.
Therefore, the expected solution of our algorithm is

$\displaystyle\mathbb{E}[\operatorname{SOL_{k}}]$
$\displaystyle=\int_{b_{k}}^{\kappa}\left[\frac{b_{k}}{L_{k}+\alpha
e}(L_{k}+\alpha)+\frac{b_{k}}{U_{k}}(\beta
e^{j^{*}}+L_{k}-L_{k}-\alpha)-\frac{1}{\beta
e^{j^{*}}+L_{k}}\ln\frac{U_{k}}{L_{k}+\alpha
e}\right]\frac{1}{\alpha}d\alpha+\int_{\kappa}^{b_{k}e}\frac{b_{k}}{U_{k}}(\beta
e^{j^{*}}+L_{k})\frac{1}{\alpha}d\alpha$ $\displaystyle\geq
b_{k}\left(\ln\frac{\kappa}{b_{k}}+(\frac{1}{e}-1)\ln\frac{L_{k}+\kappa
e}{L_{k}+b_{k}e}\right)+\frac{b_{k}}{U_{k}}\beta
e^{j^{*}}\ln\frac{\kappa}{b_{k}}-\frac{b_{k}}{U_{k}}(\kappa-
b_{k})-\frac{1}{\beta
e^{j^{*}}+L_{k}}\ln\frac{e+2}{e+1}\ln\frac{\kappa}{b_{k}}+\frac{b_{k}(\beta
e^{j^{*}}+L_{k})}{U_{k}}\ln\frac{b_{k}e}{\kappa}$ $\displaystyle\geq
b_{k}\left(\ln\frac{\kappa}{b_{k}}+(\frac{1}{e}-1)\ln\frac{L_{k}+\kappa
e}{L_{k}+b_{k}e}\right)+\frac{b_{k}}{U_{k}}\kappa\ln\frac{\kappa}{b_{k}}-\frac{b_{k}}{U_{k}}(\kappa-
b_{k})-\frac{1}{\kappa+L_{k}}\ln\frac{e+2}{e+1}\ln\frac{\kappa}{b_{k}}+\frac{b_{k}(\kappa+L_{k})}{U_{k}}\ln\frac{b_{k}e}{\kappa}$
$\displaystyle\quad\text{increasing
with}~{}\beta,j^{*}~{}(\beta=\kappa,j^{*}=0)$ $\displaystyle\geq
b_{k}\left(\ln\frac{e+1}{e}-\frac{e-1}{e}\ln\frac{L_{k}+b_{k}(e+1)}{L_{k}+b_{k}e}\right)+\frac{b_{k}^{2}(e+1)}{Le+b_{k}e(e+1)}\ln\frac{e+1}{e}-\frac{b_{k}}{L_{k}+b_{k}(e+1)}(\frac{b_{k}(e+1)}{e}-b_{k})$
$\displaystyle\quad-\frac{1}{\frac{b_{k}(e+1)}{e}+L_{k}}\ln\frac{e+2}{e+1}\ln\frac{e+1}{e}+\frac{b_{k}(L_{k}+\frac{b_{k}(e+1)}{e}}{L_{k}+b_{k}(e+1)}\ln\frac{e^{2}}{e+1}\quad\text{decreasing
with}~{}U_{k}~{}(U_{k}=L_{k}+b_{k}(e+1))$ $\displaystyle\geq
b_{k}(\ln\frac{e+1}{e}-\frac{e-1}{e}\ln\frac{e^{2}}{e^{2}-1})+\frac{b_{k}(e+1)}{e^{3}}\ln\frac{e+1}{e}-b_{k}\frac{1}{e^{2}}\frac{1}{e}-\frac{1}{\frac{b_{k}(e+1)}{e}+b_{k}(e^{2}-e-1)}\ln\frac{e+2}{e+1}\ln\frac{e+1}{e}$
$\displaystyle\quad+b_{k}\frac{e^{2}-e-1+\frac{(e+1)}{e}}{e^{2}}\ln\frac{e^{2}}{e+1}\quad\text{increasing
with}~{}L_{k}~{}(L_{k}=b_{k}(e^{2}-e-1))$
$\displaystyle=b_{k}\left(\ln\frac{e+1}{e}-\frac{1}{e^{3}}-\frac{e-1}{e}\ln\frac{e^{2}}{e^{2}-1}+\frac{e^{2}-e-1}{e^{2}}\ln\frac{e^{2}}{e+1}\right)+b_{k}\frac{1+\frac{1}{e}}{e^{2}}-\frac{1}{b_{k}(e^{2}-e+1/e)}\ln\frac{e+2}{e+1}\ln\frac{e+1}{e}$
$\displaystyle=b_{k}\left((1+\frac{1}{e^{2}})\ln(e+1)-1-\frac{1}{e^{2}}+\frac{e-1}{e}\ln(e-1)\right)-\frac{e}{b_{k}(e^{3}-e^{2}+1)}\ln\frac{e+2}{e+1}\ln\frac{e+1}{e}$

However, when $j^{*}=0$ and $\beta<\kappa$, we have

$\displaystyle\mathbb{E}[\operatorname{SOL_{k}}]$
$\displaystyle=\int_{b_{k}}^{\beta}\left[\frac{b_{k}}{L_{k}+\alpha
e}(L_{k}+\alpha)+\frac{b_{k}}{U_{k}}(\beta+L_{k}-L_{k}-\alpha)-\frac{1}{\beta+L_{k}}\ln\frac{U_{k}}{L_{k}+\alpha
e}\right]\frac{1}{\alpha}d\alpha$
$\displaystyle\quad+\int_{\beta}^{\kappa}\frac{b_{k}}{L_{k}+\alpha
e}(L_{k}+\beta)\frac{1}{\alpha}d\alpha+\int_{\kappa}^{b_{k}e}\frac{b_{k}}{U_{k}}(L_{k}+\beta)\frac{1}{\alpha}d\alpha$
$\displaystyle=b_{k}\left(\ln\frac{\beta}{b_{k}}+(\frac{1}{e}-1)\ln\frac{L_{k}+\beta
e}{L_{k}+b_{k}e}\right)+\frac{b_{k}}{U_{k}}\beta\ln\frac{\beta}{b_{k}}-\frac{b_{k}}{U_{k}}(\beta-
b_{k})-\frac{1}{\beta+L_{k}}\ln\frac{e^{2}}{e^{2}-1}\ln\frac{\beta}{b_{k}}$
$\displaystyle\quad+\frac{b_{k}(L_{k}+\beta)}{L_{k}}\left(\ln\frac{\kappa}{\beta}-\ln\frac{L_{k}+\kappa
e}{L_{k}+\beta
e}\right)+\frac{b_{k}(L_{k}+\beta)}{U_{k}}\ln\frac{b_{k}e}{\kappa}$
$\displaystyle\geq\frac{b_{k}(L_{k}+\beta)}{L_{k}}\left(\ln\frac{\kappa}{\beta}-\ln\frac{L_{k}+\kappa
e}{L_{k}+\beta
e}\right)+\frac{b_{k}(L_{k}+\beta)}{U_{k}}\ln\frac{b_{k}e}{\kappa}\quad\text{increasing
with}~{}\beta~{}(\beta=b_{k})$
$\displaystyle\geq\frac{b_{k}(L_{k}+b_{k})}{L_{k}}\left(\ln\frac{b_{k}(e+1)}{b_{k}e}-\ln\frac{L_{k}+b_{k}(e+1)}{L_{k}+b_{k}e}\right)+\frac{b_{k}(L_{k}+b_{k})}{L_{k}+b_{k}(e+1)}\ln\frac{e^{2}}{e+1}\quad\text{decreasing
with}~{}U_{k}~{}(U_{k}=L_{k}+b_{k}(e+1))$ $\displaystyle\geq
b_{k}\frac{e^{2}-e}{e^{2}-e-1}\left(\ln\frac{e+1}{e}-\ln\frac{e^{2}}{e^{2}-1}\right)+\frac{e^{2}-e}{e^{2}}\ln\frac{e^{2}}{e+1}$
$\displaystyle\quad\text{increasing with}~{}L_{k}~{}(L_{k}=b_{k}(e^{2}-e-1))$
$\displaystyle\geq
b_{k}\left(\frac{e^{2}-e}{e^{2}-e-1}\ln\frac{(e+1)^{2}(e-1)}{e^{3}}+\frac{e-1}{e}\ln\frac{e^{2}}{e+1}\right).$

Subroutine 6

In this scenario, our algorithm initiates with
$p_{k,i_{k}}=\frac{b_{k}}{L_{k}+\alpha(e-1)}$, subsequently updating
$\tilde{\tau}_{k}$ and $b_{k}$ after each iteration. We analyze two cases: one
where $\tau_{k}^{*}<L_{k}+b_{k}$, and the other where $\tau_{k}^{*}\geq
L_{k}+b_{k}$.

For the first situation where $\tau_{k}^{*}<L_{k}+b_{k}$, we have

$\displaystyle\mathbb{E}[\operatorname{SOL_{k}}]$
$\displaystyle=\int_{b_{k}}^{b_{k}e}\frac{b_{k}}{L_{k}+\alpha(e-1)}\tau_{k}^{*}\frac{1}{\alpha}d\alpha$
$\displaystyle=\frac{b_{k}\tau_{k}^{*}}{L_{k}}\left(\ln\frac{b_{k}e}{b_{k}}-\ln\frac{L_{k}+b_{k}e(e-1)}{L_{k}+b_{k}(e-1)}\right)$
$\displaystyle\geq\tau_{k}^{*}\left(1-\ln\frac{e^{2}-e+1}{e}\right)\quad\text{increasing
with}~{}L_{k}~{}(L_{k}=b_{k})$ $\displaystyle\geq
b_{k}\left(2-\ln(e^{2}-e+1)\right)$

Next, we consider the case where $\tau_{k}^{*}\geq L_{k}+b_{k}$. We suppose
that $\tau_{k}^{*}=L_{k}+\beta e^{j^{*}}$ where $\beta\in[b_{k},b_{k}e]$.

When $j^{*}\geq 1$, the objective function when $\alpha\geq\beta$ is

$\displaystyle\operatorname{SOL}_{k,1}$
$\displaystyle=\frac{b_{k}}{L_{k}+\alpha(e-1)}(L_{k}+\alpha)+b_{k}\left(1-\frac{L_{k}+\alpha-
b_{k}}{L_{k}+\alpha(e-1)}\right)\sum_{j=2}^{j^{*}}\frac{(1-1/e)^{j-2}}{\alpha
e^{j}}(\alpha e^{j-1}-\alpha e^{j-2})$
$\displaystyle\quad+b_{k}\left(1-\frac{L_{k}+\alpha-
b_{k}}{L_{k}+\alpha(e-1)}\right)\frac{(1-1/e)^{j^{*}-1}}{\alpha
e^{j^{*}+1}}(L_{k}+\beta e^{j^{*}}-L_{k}-\alpha
e^{j^{*}-1})-\frac{1}{L_{k}+\beta e^{j^{*}}}\ln\frac{\alpha
e^{2j^{*}+1}}{(\alpha(e-2)+b_{k})(e-1)^{j^{*}-1}}$

The objective function when $\alpha<\beta$ is

$\displaystyle\operatorname{SOL}_{k,2}$
$\displaystyle=\frac{b_{k}}{L_{k}+\alpha(e-1)}(L_{k}+\alpha)+b_{k}\left(1-\frac{L_{k}+\alpha-
b_{k}}{L_{k}+\alpha(e-1)}\right)\sum_{j=2}^{j^{*}+1}\frac{(1-1/e)^{j-2}}{\alpha
e^{j}}(\alpha e^{j-1}-\alpha e^{j-2})$
$\displaystyle\quad+b_{k}\left(1-\frac{L_{k}+\alpha-
b_{k}}{L_{k}+\alpha(e-1)}\right)\frac{(1-1/e)^{j^{*}}}{\alpha
e^{j^{*}+2}}(L_{k}+\beta e^{j^{*}}-L_{k}-\alpha
e^{j^{*}})-\frac{1}{L_{k}+\beta e^{j^{*}}}\ln\frac{\alpha
e^{2j^{*}+2}}{(\alpha(e-2)+b_{k})(e-1)^{j^{*}}}$

The expected solution is

$\displaystyle\mathbb{E}[\operatorname{SOL}_{k}]$
$\displaystyle=\int_{\beta}^{b_{k}e}\operatorname{SOL_{k}}_{1}\frac{1}{\alpha}d\alpha+\int_{b_{k}}^{\beta}\operatorname{SOL_{k}}_{2}\frac{1}{\alpha}d\alpha$
$\displaystyle\geq
b_{k}\left(\ln\frac{b_{k}e}{\beta}+(\frac{1}{e-1}-1)\ln\frac{L_{k}+b_{k}e(e-1)}{L_{k}+\beta(e-1)}\right)+b_{k}(1-\frac{1}{e}-(1-\frac{1}{e})^{j^{*}})\frac{e-2}{e-1}\ln\frac{L_{k}+b_{k}e(e-1)}{L_{k}+\beta(e-1)}$
$\displaystyle\quad+b_{k}^{2}(1-\frac{1}{e}-(1-\frac{1}{e})^{j^{*}})\frac{1}{L}\left(\ln\frac{b_{k}e}{\beta}-\ln\frac{L_{k}+b_{k}e(e-1)}{L_{k}+\beta(e-1)}\right)$
$\displaystyle\quad+b_{k}\beta
e^{j^{*}}\frac{(e-1)^{j^{*}-1}}{e^{2j^{*}}}\frac{e-2}{L_{k}}\left(\ln\frac{b_{k}e}{\beta}-\ln\frac{L_{k}+b_{k}e(e-1)}{L_{k}+\beta(e-1)}\right)-b_{k}\frac{(e-1)^{j^{*}-1}}{e^{j^{*}+1}}\frac{e-2}{e-1}\ln\frac{L_{k}+b_{k}e(e-1)}{L_{k}+\beta(e-1)}$
$\displaystyle\quad-\frac{1}{L_{k}+\beta
e^{j^{*}}}\ln\frac{e^{2j^{*}+2}}{(e-1)^{j^{*}+1}}\ln\frac{b_{k}e}{\beta}$
$\displaystyle\quad+b_{k}\left(\ln\frac{\beta}{b_{k}}+(\frac{1}{e-1}-1)\ln\frac{L_{k}+\beta(e-1)}{L_{k}+b_{k}(e-1)}\right)+b_{k}(1-\frac{1}{e}-(1-\frac{1}{e})^{j^{*}+1})\frac{e-2}{e-1}\ln\frac{L_{k}+\beta(e-1)}{L_{k}+b_{k}(e-1)}$
$\displaystyle\quad+b_{k}^{2}(1-\frac{1}{e}-(1-\frac{1}{e})^{j^{*}+1})\frac{1}{L}\left(\ln\frac{\beta}{b_{k}}-\ln\frac{L_{k}+\beta(e-1)}{L_{k}+b_{k}(e-1)}\right)$
$\displaystyle\quad+b_{k}\beta
e^{j^{*}}\frac{(e-1)^{j^{*}}}{e^{2j^{*}+2}}\frac{e-2}{L_{k}}\left(\ln\frac{\beta}{b_{k}}-\ln\frac{L_{k}+\beta(e-1)}{L_{k}+b_{k}(e-1)}\right)-b_{k}\frac{(e-1)^{j^{*}}}{e^{j^{*}+2}}\frac{e-2}{e-1}\ln\frac{L_{k}+\beta(e-1)}{L_{k}+b_{k}(e-1)}$
$\displaystyle\quad-\frac{1}{L_{k}+\beta
e^{j^{*}}}\ln\frac{e^{2j^{*}+3}}{(e-1)^{j^{*}+2}}\ln\frac{\beta}{b_{k}}$
$\displaystyle\geq
b_{k}\left(1+(\frac{1}{e-1}-1)\ln\frac{L_{k}+b_{k}e(e-1)}{L_{k}+b_{k}(e-1)}\right)+b_{k}(1-\frac{1}{e}-(1-\frac{1}{e})^{j^{*}})\frac{e-2}{e-1}\ln\frac{L_{k}+b_{k}e(e-1)}{L_{k}+b_{k}(e-1)}$
$\displaystyle\quad+b_{k}^{2}(1-\frac{1}{e}-(1-\frac{1}{e})^{j^{*}})\frac{1}{L}\left(1-\ln\frac{L_{k}+b_{k}e(e-1)}{L_{k}+b_{k}(e-1)}\right)$
$\displaystyle\quad+b_{k}^{2}e^{j^{*}}\frac{(e-1)^{j^{*}-1}}{e^{2j^{*}}}\frac{e-2}{L_{k}}\left(1-\ln\frac{L_{k}+b_{k}e(e-1)}{L_{k}+b_{k}(e-1)}\right)-b_{k}\frac{(e-1)^{j^{*}-1}}{e^{j^{*}+1}}\frac{e-2}{e-1}\ln\frac{L_{k}+b_{k}e(e-1)}{L_{k}+b_{k}(e-1)}$
$\displaystyle\quad-\frac{1}{L_{k}+b_{k}e^{j^{*}}}\ln\frac{e^{2j^{*}+2}}{(e-1)^{j^{*}+1}}\quad\text{increasing
with}~{}\beta~{}(\beta=b_{k})$ $\displaystyle\geq
b_{k}\left(1+(\frac{1}{e-1}-1)\ln\frac{b_{k}(e^{2}-e+1)}{b_{k}+b_{k}(e-1)}\right)+b_{k}(1-\frac{1}{e}-(1-\frac{1}{e})^{j^{*}})\frac{e-2}{e-1}\ln\frac{b_{k}(e^{2}-e+1)}{b_{k}+b_{k}(e-1)}$
$\displaystyle\quad+b_{k}(1-\frac{1}{e}-(1-\frac{1}{e})^{j^{*}})\left(1-\ln\frac{e^{2}-e+1}{e}\right)$
$\displaystyle\quad+b_{k}e^{j^{*}}\frac{(e-1)^{j^{*}-1}}{e^{2j^{*}}}(e-2)\left(1-\ln\frac{b_{k}(e^{2}-e+1)}{b_{k}+b_{k}(e-1)}\right)-b_{k}\frac{(e-1)^{j^{*}-1}}{e^{j^{*}+1}}\frac{e-2}{e-1}\ln\frac{e^{2}-e+1}{e}$
$\displaystyle\quad-\frac{1}{b_{k}+b_{k}e^{j^{*}}}\ln\frac{e^{2j^{*}+2}}{(e-1)^{j^{*}+1}}\quad\text{increasing
with}~{}L_{k}~{}(L_{k}=b_{k})$
$\displaystyle=b_{k}\left(1+(\frac{1}{e-1}-1)\ln\frac{e^{2}-e+1}{e}\right)+b_{k}(1-\frac{1}{e}-(1-\frac{1}{e})^{j^{*}})\frac{e-2}{e-1}\ln\frac{e^{2}-e+1}{e}$
$\displaystyle\quad+b_{k}(1-\frac{1}{e}-(1-\frac{1}{e})^{j^{*}})\left(1-\ln\frac{e^{2}-e+1}{e}\right)$
$\displaystyle\quad+b_{k}\frac{(e-1)^{j^{*}-1}}{e^{j^{*}}}(e-2)\left(1-\ln\frac{e^{2}-e+1}{e}\right)-b_{k}\frac{(e-1)^{j^{*}-1}}{e^{j^{*}+1}}\frac{e-2}{e-1}\ln\frac{e^{2}-e+1}{e}-\frac{1}{b_{k}+b_{k}e^{j^{*}}}\ln\frac{e^{2j^{*}+2}}{(e-1)^{j^{*}+1}}$

For the case where $j^{*}=0$, we have

$\displaystyle\mathbb{E}[\operatorname{SOL}_{k}]$
$\displaystyle=\int_{b_{k}}^{\beta}\left[\frac{b_{k}}{L_{k}+\alpha(e-1)}(L_{k}+\alpha)+b_{k}\left(1-\frac{L_{k}+\alpha-
b_{k}}{L_{k}+\alpha(e-1)}\right)\frac{1}{\alpha e^{2}}(L_{k}+\beta-
L_{k}-\alpha)-\frac{1}{L_{k}+\beta}\ln\frac{\alpha
e^{2}}{\alpha(e-2)+b_{k}}\right]\frac{1}{\alpha}d\alpha$
$\displaystyle\quad+\int_{\beta}^{b_{k}e}\frac{b_{k}}{L_{k}+\alpha(e-1)}(L_{k}+\beta)\frac{1}{\alpha}d\alpha$
$\displaystyle\geq
b_{k}\left(\ln\frac{\beta}{b_{k}}-\frac{e-2}{e-1}\ln\frac{L_{k}+\beta(e-1)}{L_{k}+b_{k}(e-1)}\right)-\frac{b_{k}\beta}{e^{2}}\frac{e-2}{L_{k}}\left(\ln\frac{\beta}{b_{k}}-\ln\frac{L_{k}+\beta(e-1)}{L_{k}+b_{k}(e-1)}\right)-\frac{b_{k}}{e^{2}}\frac{e-2}{e-1}\ln\frac{L_{k}+\beta(e-1)}{L_{k}+b_{k}(e-1)}$
$\displaystyle\quad-\frac{1}{L_{k}+\beta}\ln\frac{e^{3}}{(e-1)^{2}}\ln\frac{\beta}{b_{k}}+\frac{b_{k}(L_{k}+\beta)}{L_{k}}\left(\ln\frac{b_{k}e}{\beta}-\ln\frac{L_{k}+b_{k}e(e-1)}{L_{k}+\beta(e-1)}\right)$
$\displaystyle\geq\frac{b_{k}(L_{k}+b_{k})}{L_{k}}\left(1-\ln\frac{L_{k}+b_{k}e(e-1)}{L_{k}+b_{k}(e-1)}\right)\quad\text{increasing
with}~{}\beta~{}(\beta=b_{k})$ $\displaystyle\geq
2b_{k}\left(1-\ln\frac{b_{k}(e^{2}-e+1)}{b_{k}+b_{k}(e-1)}\right)\quad\text{increasing
with}~{}L_{k}~{}(L_{k}=b_{k})$
$\displaystyle=2b_{k}\left(2-\ln(e^{2}-e+1)\right).$

Combining the above results with the proof of Subroutine 2, presented in
Appendix A.2, establishes Theorem 4.2. ∎

##  Appendix C Additional Synthetic Experiments

###  C.1 Performance under Small $\tau^{*}$

In this section, we examine the performances of the algorithms under the
learning-augmented setting where $\tau^{*}$ is small. Specifically, we set the
number of risk occurrences $\tau^{*}=\text{Int}[0.2(T+b)]$ for scenarios with
horizon lengths $T=22$ and $T=100$, and $\tau^{*}=\text{Int}[0.1(T+b)]$ for
scenario $T=100$. Figure 4 presents the average competitive ratio against a
range of prediction interval widths.

Figure 4: Average competitive ratio under learning-augmented setting. Left:
$T=22$, $\tau^{*}=\text{Int}[0.2(T+b)]$; Middle: $T=100$,
$\tau^{*}=\text{Int}[0.2(T+b)]$; Right: $T=100$,
$\tau^{*}=\text{Int}[0.1(T+b)]$.

###  C.2 Budget Utilization by Each Algorithm

To assess the budget utilization by each algorithm, we eliminate the penalty
term from the objective in Problem 2.1. Figures 5 and 6 display the average
competitive ratios in scenarios without and with learning augmentation,
respectively. We note that in Figure 5 (middle), when $\tau^{*}=22$, the
competitive ratio slightly exceeds 1. This is attributed to our algorithm
utilizing a slightly higher budget in expectation. We provide detailed
insights into this observation in Appendix A.1, where we demonstrate that the
worst-case budget spent is about $1.044b_{k}$, slightly surpassing the
allocated budget.

Figure 5: Average competitive ratio under non-learning augmented setting.
Left: $T=8$; Middle: $T=22$; Right: $T=100$.

Figure 6: Average competitive ratio under learning-augmented setting. Left:
$T=8$, $\tau^{*}=\text{Int}[0.5(T+b)]$; Middle: $T=22$,
$\tau^{*}=\text{Int}[0.5(T+b)]$; Right: $T=100$,
$\tau^{*}=\text{Int}[0.5(T+b)]$.

##  Appendix D Additional Results on HeartSteps V1 Study

In the HeartSteps V1 application, we implement four algorithms: our randomized
and learning-augmented algorithms (Algorithms 1 and 2, respectively), the
SeqRTS strategy proposed by Liao et al. (2018), and a benchmark method
($b/U$).

Rather than devising a tailored prediction model, we generate prediction
intervals by randomly selecting from a range of $[2,144]$, which contains
$\tau^{*}$, with intervals of varying widths. This approach allows us to
assess the performance of different algorithms under varying qualities of
forecast accuracy.

We adopt the SeqRTS method to include prediction intervals, ensuring a
balanced comparison with our algorithms. At the start of each user day, a
number is randomly selected from the interval $[L,U]$ to estimate the number
of available risk times. Should the budget be exhausted before allocating for
all available risk times, a minimum probability of $1\times 10^{-6}$ is
assigned to the remaining times. For additional information on the SeqRTS
method, readers are referred to Liao et al. (2018).

Figure 7 illustrates the average entropy change across user days. It is
evident that SeqRTS exhibits the highest entropy change, suggesting non-
uniform distribution behavior. In contrast, our learning-augmented algorithm
demonstrates superior uniformity, outperforming the randomized algorithm. The
benchmark method records an entropy of zero, attributed to its conservative
strategy of assigning a constant probability of $b/U$.

Figure 8 shows the average competitive ratio and entropy change across user
days, considering the scenario where SeqRTS assigns a minimum probability of
$0$ to remaining risk times once the budget is depleted. Owing to the
Penalization term 2, this results in the objective function being negative
infinity and the entropy change reaching infinity.

Figure 7: Entropy change averaged across user days under various prediction
interval widths on the HeartSteps V1 dataset. The shaded area represents the
$\pm 1.96$ standard error bounds across user days.

Figure 8: Competitive ratio and entropy change averaged across user days under
various prediction interval widths on the HeartSteps V1 dataset. The shaded
area represents the $\pm 1.96$ standard error bounds across user days. Note:
For SeqRTS, a minimum probability of $0$ is assigned to the remaining times
when the budget is exhausted.