Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimes

In many domains, including healthcare and e-commerce, we frequently encounter the following decision-making problem: we sequentially and repeatedly receive context information X (e.g., features of patients or users), need to choose an action A { 1, 1} (e.g., whether to treat a patient with invasive therapy or whether expose a user to our ad), and receive a reward Y ( A) (e.g., patient's health outcome or user's click minus ad spot costs) corresponding to the chosen action. Our goal is to collect the most reward over time. When contexts X and potential rewards Y ( 1),Y ( 1) are drawn from a stationary, but unknown, distribution, this setting is modeled by the stochastic bandit problem (Bubeck and Cesa-Bianchi, 2012, Wang et al., 2005). A special case is the multi-armed bandit (MAB) problem where there is no contextual information (Auer et al., 2002, Lai and Robbins, 1985). In these problems, we quantify the quality of an algorithm for choosing actions based on available historical data in terms of its regret for every horizon T: the expected additional cumulative reward up to time T that we would obtain if we had full knowledge of the stationary context-reward distribution (but not the realizations). The minimax regret is the best (over algorithms) worst-case regret (over problem instances).