Networked Restless Bandits with Positive Externalities

Many user- and article-level interventions have been proposed to combat the dissemination of misinformation over social networks, including inoculation (exposing users to weaker forms of misinformation), shifting user attention to accuracy, publicizing consensus, fact-checking, using source credibility (while controlling for political polarization), and flagging or providing warnings about an article. Cost pressures and user-engagement risks typically preclude the widespread application of such interventions and motivate a constrained resource allocation-based approach. Restless bandits have been used to model such allocation problems; however, prior work assumes that individual arms only benefit if they receive the resource directly. We note that misinformation-related intervention allocation tasks occur within communities and may be characterized by externalities that allow arms to derive partial benefit when their neighbor(s) receive the resource. We introduce networked restless bandits, a novel multi-armed bandit setting in which arms are both restless and embedded within a directed graph. We then present Greta, a graph-aware, Whittle index-based heuristic algorithm that can be used to efficiently construct a constrained reward-maximizing action vector at each timestep.