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

arXiv: https://arxiv.org/abs/2402.01995 · HTML: https://mlsanity.com/paper/2402.01995/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 28 references that are in the map.
- First posted on arXiv 3 Feb 2024.

## Builds on (most cited first, 7 of 7)

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [The Primal-Dual method for Learning Augmented Algorithms](https://mlsanity.com/paper/2010.11632/) (2020)
- [Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms](https://mlsanity.com/paper/2010.11443/) (2020)
- [Assessing Time-Varying Causal Effect Moderation in Mobile Health](https://mlsanity.com/paper/1601.00237/) (2016)
- [Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Model](https://mlsanity.com/paper/2206.11397/) (2022)
- [Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysis](https://mlsanity.com/paper/2302.06832/) (2023)
- [Stateful Offline Contextual Policy Evaluation and Learning](https://mlsanity.com/paper/2110.10081/) (2021)

## Abstract (arXiv)

Motivated by applications in digital health, this work studies the novel problem of online uniform sampling (OUS), where the goal is to distribute a sampling budget uniformly across unknown decision times. In the OUS problem, the algorithm is given a budget b and a time horizon T, and an adversary then chooses a value τ^* ∈ [b,T], which is revealed to the algorithm online. At each decision time i ∈ [τ^*], the algorithm must determine a sampling probability that maximizes the budget spent throughout the horizon, respecting budget constraint b, while achieving as uniform a distribution as possible over τ^*. We present the first randomized algorithm designed for this problem and subsequently extend it to incorporate learning augmentation. We provide worst-case approximation guarantees for both algorithms, and illustrate the utility of the algorithms through both synthetic experiments and a real-world case study involving the HeartSteps mobile application. Our numerical results show strong empirical average performance of our proposed randomized algorithms against previously proposed heuristic solutions.