Continuous-Time Multi-Armed Bandits with Controlled Restarts
This addresses time-constrained decision processes in fields like physics, biology, and computer science, offering a novel algorithmic approach with provable guarantees, though it is incremental in extending bandit theory to include restart controls.
The paper tackles the problem of maximizing expected total reward under a time constraint in multi-armed bandits with controlled restarts, where tasks have random completion times and correlated rewards, by developing online learning algorithms with O(log(τ)) and O(√(τ log(τ))) regret for finite and continuous action spaces, respectively, and demonstrates applicability by boosting SAT solver performance.
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 $τ$. 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(τ))$ and $O(\sqrt{τ\log(τ)})$ 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.