Before revision:  We propose the Functional Sequential Allocation policy, and provide upper bounds on the regretit incurs compared to the oracle policy that knows the best treatment for each individual. These upper bounds increase sublinearly in the number of treatment assignments and we show that this regret guarantee is minimax optimal. In addition, the assumptions under which this regret guarantee is established are as weak as possible --- even a minimal weakening of them will imply non-existence of policies with regret increasing sub-linearly in the number of assignments.
After revision:  We propose the Functional Sequential Allocation policy, and provide upper bounds on maximal expected regret. We first study explore-then-commit (ETC) policies. These are policies, where one initially explores which treatment is of the highest quality, typically through a randomized controlled trial, and subsequently fully commits to the inferred superior treatment. Then, we introduce and study the Functional Upper Confidence Bound (F-UCB) policy, which interweaves exploration and exploitation and is thus not of the assumptions under which this regret guarantee is established are as weak as possible --- even a minimal weakening of them will imply non-existence of policies with regret increasing sub-linearly in the number of assignments.