  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.
