Title: Instrument-Armed Bandits,
Abstract: We extend the classic multi-armed bandit (MAB) model to the setting of
noncompliance, where the arm pull is a mere instrument and the treatment
applied may differ from it, which gives rise to the instrument-armed bandit
(IAB) problem. The IAB setting is relevant whenever the experimental units are
human since free will, ethics, and the law may prohibit unrestricted or forced
application of treatment. In particular, the setting is relevant in bandit
models of dynamic clinical trials and other controlled trials on human
interventions. Nonetheless, the setting has not been fully investigate in the
bandit literature. We show that there are various and divergent notions of
regret in this setting, all of which coincide only in the classic MAB setting.
We characterize the behavior of these regrets and analyze standard MAB
algorithms. We argue for a particular kind of regret that captures the causal
effect of treatments but show that standard MAB algorithms cannot achieve
sublinear control on this regret. Instead, we develop new algorithms for the
IAB problem, prove new regret bounds for them, and compare them to standard MAB
algorithms in numerical examples.