Multi-Armed Bandits on Partially Revealed Unit Interval Graphs

Abstract

A stochastic multi-armed bandit problem with side information on the similarity and dissimilarity across different arms is considered. The action space of the problem can be represented by a unit interval graph (UIG) where each node represents an arm and the presence (absence) of an edge between two nodes indicates similarity (dissimilarity) between their mean rewards. Two settings of complete and partial side information based on whether the UIG is fully revealed are studied and a general two-step learning structure consisting of an offline reduction of the action space and online aggregation of reward observations from similar arms is proposed to fully exploit the topological structure of the side information. In both cases, the computation efficiency and the order optimality of the proposed learning policies in terms of both the size of the action space and the time length are established.

arXiv commentParts of the work have been presented at the 36th IEEE Military Communication Conference (MILCOM), October, 2017 and the 52nd Asilomar Conference on Signals, Systems and Computers, October, 2018

References in corpus (7)

• Analysis of Thompson Sampling for the multi-armed bandit problem
• Unbiased Offline Evaluation of Contextual-bandit-based News Article Recommendation Algorithms
• Further Optimal Regret Bounds for Thompson Sampling
• Spectral bandits for smooth graph functions
• Unimodal Bandits: Regret Lower Bounds and Optimal Algorithms
• Adaptive Shortest-Path Routing under Unknown and Stochastically Varying Link States
• Bandits on graphs and structures