Continuous-Time Multi-Armed Bandits with Controlled Restarts

Abstract

Time-constrained decision processes have been ubiquitous in many fundamental applications in physics, biology and computer science. Recently, restart strategies have gained significant attention for boosting the efficiency of time-constrained processes by expediting the completion times. In this work, we investigate the bandit problem with controlled restarts for time-constrained decision processes, and develop provably good learning algorithms. In particular, we consider a bandit setting where each decision takes a random completion time, and yields a random and correlated reward at the end, with unknown values at the time of decision. The goal of the decision-maker is to maximize the expected total reward subject to a time constraint $\tau$. As an additional control, we allow the decision-maker to interrupt an ongoing task and forgo its reward for a potentially more rewarding alternative. For this problem, we develop efficient online learning algorithms with $O(\log (\tau ))$ and $O(\sqrt{\tau \log (\tau )})$ regret in a finite and continuous action space of restart strategies, respectively. We demonstrate an applicability of our algorithm by using it to boost the performance of SAT solvers.

References in corpus (7)

• First-passage times in complex scale-invariant media
• First Passage Under Restart
• First order transition for the optimal search time of Lévy flights with resetting
• Knapsack based Optimal Policies for Budget-Limited Multi-Armed Bandits
• Unimodal Bandits: Regret Lower Bounds and Optimal Algorithms
• Thompson Sampling for Budgeted Multi-armed Bandits
• Budget-Constrained Bandits over General Cost and Reward Distributions