Online Uniform Sampling: Randomized Learning-Augmented Approximation Algorithms with Application to Digital Health

We are glad that the reviewer found our paper "well-written with notable clarity and presentation." We thank the reviewer for the valuable feedback and respond them in detail below.

• Proof of Lemmas 3.1 and 4.1 Sorry for the sloppiness in the proofs. To ensure exact satisfaction of $\mathbb{E}\left[\sum_{i=1}^{\tau^*} p_{i}\right] \leq b$, one can appropriately scale the input budget $b$ in Algorithms 1 and 2. For example, for Subroutine 2, the input budget should be set as $b/1.047$. In our experiments, we have implemented this adjustment to guarantee that the budget constraint is strictly satisfied. We will revise the statement of the lemmas and theorems to reflect this.
• Multiple risk levels Binary or categorical risk levels are common in digital health studies. For instance, the HeartSteps study defines risk levels as binary, with fewer than 150 steps in the previous 40 minutes considered "at risk", and otherwise "not at risk". Similarly, in the Sense2Stop Smoking Cessation Study [2], the risk variable takes on three categories: stress, no stress, and unknown. Each distinct risk category typically requires a separate budget input, resulting in independent subproblems. In a truly continuous risk setting, the probability of observing any specific risk value is effectively zero, making the OUS formulation unsuitable. However, a pseudo-continuous setting is feasible by discretizing risk into different levels and applying our proposed methods separately for each category, as described in Appendix A. We provide empirical results demonstrating this approach using the HeartSteps data, categorizing step counts into three levels: fewer than 50, fewer than 100, and fewer than 150 steps. The results suggested that our proposed learning-augmented algorithm in general has the best performance. Figures illustrating these results are available at the following link: https://imgur.com/a/UXRotSQ
• l89, arbitrarily By "arbitrarily," we mean that the distribution of risk levels can change adversarially over time without assuming an underlying structure like an MDP. Since interventions may unpredictably influence future risks, our algorithm is designed to ensure strong performance guarantees even in the worst case. We will clarify this in l89.
• $\rho$-robustness Thank you for the question. Lines 119–122 explicitly state the conditions for achieving $\rho$-robustness. In maximization problems like OUS, the goal is to design an approximation algorithm with the highest possible robustness factor $\rho$. Theorems 3.2 and 4.2 specify the robustness factors that our algorithm can achieve, demonstrating satisfactory performance. Non-trivial robustness levels, such as $\rho > 1-\frac{1}{e}$ are typically challenging or impossible to achieve for maximization problems, as supported by existing literature [3].
• clinical motivation for risk variable Thank you for raising this. Yes, previous clinical studies define sedentary behavior as inactivity having at least 40 minutes of time with fewer than 150 steps. We will include additional reference [1] to reflect this.
• x-axis of Figure 3 Thank you for the question. The x-axis correctly represents "Width," not user-days, as the average competitive ratio shown is computed across user-days for varying widths of the prediction interval. We display results across different confidence interval widths to assess algorithm performance under predictions ranging from extremely good to extremely bad, thereby testing their robustness in practice.

Thank you for catching the typo. We have corrected it.

• [1] Spruijt-Metz, et al. (2022). Advancing behavioral intervention and theory development for mobile health: the HeartSteps II protocol. International journal of environmental research and public health.

• [2] Battalio, S. L., et al. (2021). 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.

• [3] Buchbinder, N., et al. (2007). Online primal-dual algorithms for maximizing ad-auctions revenue. In European Symposium on Algorithms.

We appreciate the reviewer's feedback. We clarify that our work is positioned as an applied paper motivated by digital health applications rather than a purely theoretical paper. Below, we illustrate the type of guarantees that competitive ratios provide, detail the computation of competitive ratios, and explain how this work aligns with the ML community.

• is penalty term negligible Consider your example where the series converges as $p_i \propto \frac{1}{i^2}$. Suppose $b=2$ and $\tau^*=4$. The resulting treatment probability sequence is $1$, $\frac{1}{4}$, $\frac{1}{9}$, $\frac{1}{16}$. Then, the penalty term becomes $\frac{1}{4}\ln \frac{1}{1/16} = \frac{\ln 16}{4}$. The objective function becomes $1+\frac{1}{4}+\frac{1}{9}+\frac{1}{16}-\frac{\ln 16}{4} \approx 0.73$. This yields a competitive ratio of approximately $\frac{0.73}{2} \approx 0.365$. Although as $\tau^*$ grows large, the penalty term $\frac{1}{\tau^*}\ln \frac{1}{1/{\tau^*}^2} = \frac{2\ln \tau^*}{\tau^*}$ becomes negligible, this does not imply that the competitive ratio approaches 1 in general.
  Since our problem makes no assumption on the distribution of $\tau^*$ and the competitive ratio must hold for the worst-case instance, the challenge arises precisely when $\tau^*$ is close to the budget $b$. Thus, the problem remains non-trivial.
• upper bound derivation In our proof, we do not require the policy to be non increasing. Sorry for the typo, we have corrected it as below. To derive the upper bound of 0.504 using Yao's lemma, we constructed a challenging instance and solved the following maximization problem over probabilities $p_1, \dots, p_5$:

$

\arg \max_{p_1, p_2, p_3, p_4, p_5}\pi_1p_1 + \pi_2(p_1+p_2) + \pi_3(p_1+p_2+p_3) + \pi_4(p_1+p_2+p_3+p_4) + \pi_5 b - \pi_2\frac{1}{2} \left|\ln\frac{p_1}{p_2}\right|-\pi_3\frac{1}{3}\left|\ln\frac{p_1}{p_3}\right| - \pi_4\frac{1}{4}\left|\ln\frac{p_1}{p_4}\right| - \pi_5\frac{1}{5}\left|\ln\frac{p_1}{p_5}\right|

$

subject to $p_1+p_2+p_3+p_4+p_5=b$. We mistakenly omitted the absolute value in the current proof. Notably, despite no explicit constraint enforcing a decreasing solution, the optimal solution naturally followed this pattern, suggesting that decreasing or non-increasing probabilities generally improve performance in the OUS problem.

• Doubling trick In our problem formulation, there is no reward learning, so neither our method's inspiration nor our analysis techniques stem from online learning problems. While our algorithm design may resemble the doubling trick used in learning, the analysis objectives and problem complexities are fundamentally different.
• scope of ICML We acknowledge that this paper focuses on online optimization, specifically the design of randomized approximation and learning-augmented algorithms, rather than traditional online learning. Online optimization, especially with prediction augmentation, is actively studied in machine learning. Related works, such as [1] (ICML 2023) and [2] (NeurIPS 2020), demonstrate its relevance in top-tier conferences. Thus, we believe our paper aligns well with ICML's scope.
• parameter choices in algorithm design We chose the distribution $\propto 1/\alpha$ and the constant $e$ for a cleaner analysis of the algorithm’s expected performance, particularly for integration. The choice of $e$ aligns with classical online maximization results where optimal competitive ratios often take the form $1 - 1/e$ [3]. It is further inspired by the randomized algorithm of [1]. We have clarified this in the revised version (l208):

We choose the density $1/\alpha$ and the constant $e$ to simplify the analysis of the algorithm’s expected performance. The choice of $e$ is also motivated by its frequent appearance in upper bounds for online optimization problems.

• l139, $\sigma$: The tunable parameter $\sigma$ is introduced on l139 (right column), allowing us to explore a range of values that penalize non-uniformity at different scales. We have now revised l139:

The tunable parameter $\sigma$ in the penalty term $\sigma \cdot \ln \frac{\max_i p_i}{\min_i p_i}$ serves as a scaling factor to control the strength of the penalty. This allows flexibility in adjusting how strongly non-uniformity is penalized, as further discussed in Remarks 3.2 and 4.2.

See our response to reviewer KP69 for more discussion on $\sigma$.

• [1] Shin, Y., et al. Improved learning-augmented algorithms for the multi-option ski rental problem via best-possible competitive analysis. ICML, 2023.

• [2] Bamas, E., et al. The primal-dual method for learning augmented algorithms. NeurIPS, 2020.

• [3] Buchbinder, N., et al. Online primal-dual algorithms for maximizing ad-auctions revenue. European Symposium on Algorithms, 2007.

We appreciate the reviewer's feedback. Below we address each point in detail to further clarify and strengthen the paper. We have also included SeqRTS as a benchmark in the synthetic experiments. We would be happy to provide further clarification if needed.

• The need for consistency While perfect predictions ($U = L = \tau^*$) could theoretically achieve $\text{OPT}(\tau^*)$, most learning-augmented algorithms sacrifice 1-consistency to maintain robust across prediction uncertainties [1,2]. Regardless of the confidence interval width, the algorithm must ensure an acceptable worst-case guarantee. Although a separate algorithm could be designed for perfect predictions, consistency measures performance as prediction accuracy improves. In contrast, our algorithm is designed to achieve 1-consistency.
• Proof of Lemmas 3.1 and 4.1 Sorry for the sloppiness in the proofs. To ensure exact satisfaction of $\mathbb{E}\left[\sum_{i=1}^{\tau^*} p_{i}\right] \leq b$, one can appropriately scale the input budget $b$ in Algorithms 1 and 2. For example, for Subroutine 2, the input budget should be set as $b/1.047$. In our experiments, we have implemented this adjustment to guarantee that the budget constraint is strictly satisfied. We will revise the statement of the lemmas and theorems to reflect this.
• $\sigma$ in proof of Theorem 3.1 We have revised the text at line 139, c2 to clarify that $\sigma$ acts as a tunable parameter in the penalty term $\sigma \cdot \ln \frac{\max_i p_i}{\min_i p_i}$, scaling the penalty strength to flexibly adjust non-uniformity penalization. We have revised the proof and modified the description in Remark 3.3 accordingly to incorporate the condition on $\sigma$:

In Appendix C.2, we show that for Subroutine 1, Theorem 3.2 holds over a wide range of $\sigma$ values, specifically $\sigma \leq \frac{2b(\ln(e-1)-1+1/(e-1))}{\ln b+2-2\ln(e-1)}$. For Subroutine 2, Theorem 3.2 remains valid when $\sigma \leq \frac{b}{e}$. For subroutine 3 where $\tau^*$ can be unbounded, the theorem holds for $\sigma \leq \frac{1}{2-\ln(e-1)} \frac{1}{e}\left(1-\frac{1}{e}\right)^{j^*+1} b$, ensuring that the penalty term scales similarly to the budget term in the objective.

We clarify that for subroutine 3, only requiring $\sigma \leq b/e-b/e^2$ is not enough for the case where $j^*\geq1$. The stronger condition is necessary to maintain a valid competitive ratio via the monotonic property; otherwise, the competitive ratio may become arbitrarily small.

• Including SeqRTS on synthetic data Thank you for the suggestion. We have now conducted additional synthetic experiments using the SeqRTs algorithm proposed by Liao et al. (2018) with the suggested naive point estimate $(U+L)/2$. The results are provided on https://imgur.com/a/Vs7nDAu. The results suggest that SeqRTS, in general, performs worse compared to our algorithms.
• The role of randomness of Int $\tilde{\tau}$ in algorithms Taking Algorithm 1 as an example, $\text{Int} \tilde{\tau}$ determines whether the current risk time $i$ exceeds the length of the current stage, thereby indicating whether the budget should be updated. Because stage lengths must be integer-valued, $\tilde{\tau}$ must be rounded. To avoid rounding error, we adopt a stochastic rounding method, ensuring that the expectation of the rounded stage length, $\text{Int} \tilde{\tau}$, matches exactly the original value $\tilde{\tau}$. We will further clarify this in our revised paper.

Thank you for catching the typo on online uniform scheduling and suggestions on the figure. We have revised our paper accordingly. Additionally, we will explicitly explain in our proofs the steps that rely on the monotonicity of the functions. Thank you for the suggestion.

• [1] Bamas, E., Maggiori, A., & Svensson, O. (2020). The primal-dual method for learning augmented algorithms. NeurIPS.

• [2] Kevi, E., & Nguyen, K. T. (2023). Primal-dual algorithms with predictions for online bounded allocation and ad-auctions problems. International Conference on Algorithmic Learning Theory.

We thank the reviewer for the positive review and are glad that the reviewer found our work as "a principled approach to the OUS problem and technically nice and non-trivial."

• Weighted risk times: Weighting risk times differently implies varying risk levels, prioritizing higher-risk times. Our approach can naturally handle this by decomposing the problem into independent subproblems for each risk level, see Appendix A.
• Stronger bounds by relaxing budgeting: Relaxing the budget constraint is unlikely to improve upper bounds for OUS. Our proof, using Yao's lemma, constructs a hard instance where all feasible deterministic algorithms perform poorly. Slightly relaxing the budget would not yield large improvements. A similar observation applies to the lower bound, where the budget already holds only in expectation. Further relaxation would make the constraint ineffective.
• Distribution of $\tau^\star$ in experiments: Our proposed algorithms are, by design, independent of the specific distribution of risk times. They determine intervention probabilities solely based on the number of risk times $\tau^*$. Thus, for a fixed $\tau^*$, the results remain the same whether the risk times are uniformly distributed or geometrically spaced.
• Case splitting compared with Shin et al/three regime inherent or analysis artifact? While Shin et al. proposed a single unified randomized algorithm without different regimes, providing guarantees as $T\rightarrow\infty$, we focus on finite-horizon guarantees under the additional budget constraint $b$. For example, our Algorithm 1 considers three regimes: 1) $T \leq be$ (Subrt 1), 2) $be < T \leq be^2$ (Subrt 2), and 3) $T > be^2$ (Subrt 3). Case 3 resembles Shin et al.'s infinite-horizon setting, where both $T$ and $\tau^*$ can be unbounded. However, our budget constraint introduces new challenges, necessitating novel algorithm design. In Case 3, to meet the budget constraint, the algorithm must initially adopt a conservative approach, resulting in a slightly lower competitive ratio. To mitigate this, we introduce specialized algorithms (Subrts 1 and 2) for the first two regimes, achieving higher competitive ratios. Conversely, both Shin et al.'s proof and ours rely on a case-by-case analysis to evaluate the robustness of the learning-augmented algorithm, as computing the expected cost depends on identifying the phase in which the algorithm terminates. We will add the above clarification to our revised paper.
• Model must be spelled out precisely: We revised L81 c2 as follows:

At each decision point $t\in[1, T]$, the algorithm observes the binary risk level $R_t$ associated with the patient. Here, $R_t=1$ indicates a heightened likelihood of an adverse event, such as a relapse into smoking, while $R_t=0$ implies a lower risk level.

• l118 c1 We revised L93 c2 as follows:

Since $R_t$ is revealed to the algorithm online, the total number of risk times throughout the decision period, $\tau^* = \sum_{t=1}^T R_t$, remains unknown until the last decision point $T$.

• 153 c1 L1 distance in penalty term: Our choice of penalty ties to the uniform constraint through the two primary objectives outlined in Section 2.1 L122-124. Other alternative penalty terms that satisfy the properties described in Remark 2.1 could also be considered. However, the proposed L1 distance penalty is not appropriate, as it does not sufficiently penalize cases where probabilities are zero ($p_i=0$), which can result in budget depletion before the final risk time.
• l110 c2 The randomness of the algorithm comes from the initialization step, where $\alpha\in [b,be]$ is sampled from a distribution with probability density function $f(\alpha) = 1/\alpha$. This sampled value $\alpha$ is subsequently used to calculate treatment probabilities. We have further clarified this point on L210.
• l204 c1 consistency tradeoff: Consistency, as defined in L195, is defined relative to a perfect prediction of the risk times, i.e., when $U=L=\tau^*$. Thus, there is no trade-off between consistency and prediction interval width $U-L$. Our algorithm achieves 1-consistency. Further discussion on consistency is included in our response to Reviewer KP69.
• l229 c1 on j: $j$ acts as a stage counter, incrementing when $i > \text{Int}\tilde{\tau}$ and triggering a budget update when $j>3$ to avoid budget depletion before the final risk time. For each problem instance is assigned to a specific subroutine based on $T$, separate counters $j_1$ and $j_2$ for Subrts 2 and 3 are unnecessary.
• Not using all budget: While full budget utilization is ideal for inference, given that $\tau^*$ is random, achieving this under uniform constraints is hard in practice.
• l321 c2 We revised l321c2 as follows:

The evaluation metric is the average competitive ratio computed from 500 experimental replications.

Thank you for catching the typo and redundant texts. These have been fixed.