  Contextual bandit algorithms are commonly used in digital health to recommend
personalized treatments. However, to ensure the effectiveness of the
treatments, patients are often requested to take actions that have no immediate
benefit to them, which we refer to as pro-treatment actions. In practice,
clinicians have a limited budget to encourage patients to take these actions
and collect additional information. We introduce a novel optimization and
learning algorithm to address this problem. This algorithm effectively combines
the strengths of two algorithmic approaches in a seamless manner, including 1)
an online primal-dual algorithm for deciding the optimal timing to reach out to
patients, and 2) a contextual bandit learning algorithm to deliver personalized
treatment to the patient. We prove that this algorithm admits a sub-linear
regret bound. We illustrate the usefulness of this algorithm on both synthetic
and real-world data.
