# Continuous Time Bandits With Sampling Costs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 43 references that are in the map.
- First posted on arXiv 12 Jul 2021.

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

- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/1507.06738/) (2015)
- [Adversarial Bandits with Knapsacks](https://mlsanity.com/paper/1811.11881/) (2018)
- [Online Learning with Switching Costs and Other Adaptive Adversaries](https://mlsanity.com/paper/1302.4387/) (2013)
- [Bandits with Switching Costs: T^{2/3} Regret](https://mlsanity.com/paper/1310.2997/) (2013)
- [Recovering Bandits](https://mlsanity.com/paper/1910.14354/) (2019)
- [Stochastic Bandits with Delay-Dependent Payoffs](https://mlsanity.com/paper/1910.02757/) (2019)
- [Combinatorial Semi-Bandits with Knapsacks](https://mlsanity.com/paper/1705.08110/) (2017)
- [Bandits with Feedback Graphs and Switching Costs](https://mlsanity.com/paper/1907.12189/) (2019)
- [On Finding the Largest Mean Among Many](https://mlsanity.com/paper/1306.3917/) (2013)
- [Cheap Bandits](https://mlsanity.com/paper/1506.04782/) (2015)
- [Cost-aware Cascading Bandits](https://mlsanity.com/paper/1805.08638/) (2018)
- [Routing and Staffing when Servers are Strategic](https://mlsanity.com/paper/1402.3606/) (2014)

## Abstract (arXiv)

We consider a continuous-time multi-arm bandit problem (CTMAB), where the learner can sample arms any number of times in a given interval and obtain a random reward from each sample, however, increasing the frequency of sampling incurs an additive penalty/cost. Thus, there is a tradeoff between obtaining large reward and incurring sampling cost as a function of the sampling frequency. The goal is to design a learning algorithm that minimizes regret, that is defined as the difference of the payoff of the oracle policy and that of the learning algorithm. CTMAB is fundamentally different than the usual multi-arm bandit problem (MAB), e.g., even the single-arm case is non-trivial in CTMAB, since the optimal sampling frequency depends on the mean of the arm, which needs to be estimated. We first establish lower bounds on the regret achievable with any algorithm and then propose algorithms that achieve the lower bound up to logarithmic factors. For the single-arm case, we show that the lower bound on the regret is Omega((log T)2/μ), where μ is the mean of the arm, and T is the time horizon. For the multiple arms case, we show that the lower bound on the regret is Omega((log T)2 μ/Delta2), where μ now represents the mean of the best arm, and Delta is the difference of the mean of the best and the second-best arm. We then propose an algorithm that achieves the bound up to constant terms.