Pure Exploration in Multi-armed Bandits with Graph Side Information

The multi-armed bandit has emerged as an important paradigm for modeling sequential decision making and learning under uncertainty with multiple practical applications such as design policies for sequential experiments [30], combinatorial online leaning tasks [6], collaborative learning on social media networks [21, 2], latency reduction in cloud systems [18] and many others [5, 41, 36]. In the traditional multi-armed bandit problem, the goal of the agent is to sequentially choose among a set of actions (or arms) to maximize a desired performance criterion (or reward). This objective demands a delicate tradeoff between exploration (of new arms) and exploitation (of promising arms). An important variation of the reward maximization problem is the identification of arms with the highest (or near-highest) expected reward. This best arm identification [28, 8] problem, which is one of pure exploration, has a wide range of important applications like identifying molecules and drugs to treat infectious diseases like COVID-19, finding relevant users to run targeted ad campaigns, hyperparameter optimization in neural networks and recommendation systems. The broad range of applications of this paradigm is unsurprising given its ability to essentially model any optimization problem of black-box functions on discrete (or discretizable) domains with noisy observations. While the bandit pure exploration problems harbor considerable promise, there is a significant catch. In modern applications, one is often faced with a tremendously large number of options (sometimes in the millions) that need to be considered rapidly before making a decision. Pulling each bandit arm even once could be intractable.