Adaptive Sequential Experiments with Unknown Information Flows
When information is limited, online recommendation services aim to strike a balance between maximizing immediate payoffs based on available information, and acquiring new information that is essential for maximizing future payoffs. This trade-off is captured by the multi-armed bandit (MAB) framework that has been studied and applied for designing sequential experiments when at each time epoch a single observation is collected on the action that was selected at that epoch. However, in many cases, additional information may become available between decision epochs. We introduce a generalized MAB formulation in which auxiliary information may appear arbitrarily over time. By obtaining matching lower and upper bounds, we characterize the minimax complexity of this family of problems as a function of the information arrival process, and study how salient characteristics of this process impact policy design and achievable performance. 
We establish that while Thompson sampling and UCB policies leverage additional information naturally, other policies, such as epsilon-greedy, do not exhibit such robustness. We introduce a virtual time indexes method for dynamically controlling the exploration rate of policies, and apply it for designing epsilon-greedy-type policies that, without any prior knowledge on the information arrival process, attain the best performance (in terms of regret rate) that is achievable when the information arrival process is a priori known. We use data from a large media site to empirically analyze the value that may be captured in practice by leveraging auxiliary information flows for content recommendations. We further apply our method to a contextual bandit framework that allows for personalized recommendations using idiosyncratic consumer characteristics.