Kernel $\epsilon$-Greedy for Contextual Bandits

Sequential decision-making in real time is increasingly becoming important in various applications, such as clinical trials (Bather, 1985; Villar et al., 2015), news article recommendation (Li et al., 2010) and mobile health (Nahum-Shani et al., 2017). In all such problems, the decision-maker is faced with several alternatives, from which they have to make a series of choices (referred to as arms) sequentially, based on the information available at any given time. In doing so, the decision-maker takes into account additional information or covariates (characteristics) which help in making informed decisions. This framework is popularly known as the contextual bandit problem (Langford and Zhang, 2007). In a treatment allocation problem, this can be described as follows: given finitely many competing treatments for a disease, the decision-maker (physician) chooses the treatment best suited for individual patients as they arrive, and each allocated treatment results in a reward (outcome). While doing so, the decision-maker takes into account the patient's covariates and information available about previous patients with the same disease, with the eventual goal of maximizing the total reward accumulated over a period of time. The technical challenge in achieving this is two-fold: 1) learning the relationship between the covariates and optimal arms, and, 2) balancing the exploration-exploitation trade-off, which arises due to the sequential (or online) nature of the problem. In other words, in a sequential setup, at each time point the physician has to effectively identify the best treatment (exploration) and treat patients as effectively as possible during the trial (exploitation).