Multi-Armed Bandits on Partially Revealed Unit Interval Graphs
This work addresses bandit problems with structured side information, offering incremental improvements for scenarios where similarity between arms is known.
The paper tackles the stochastic multi-armed bandit problem with side information represented as a unit interval graph, proposing a two-step learning structure for both complete and partially revealed graphs, and establishes computation efficiency and order optimality in terms of action space size and time length.
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.