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.

研究了具有相似性和不相似性的测臂的随机多臂赌博问题，并提出了一种基于在线汇总奖励观察结果的离线行动空间缩减及在线聚合的通用两步学习结构，旨在充分利用侧面信息的拓扑结构。验证了学习策略的计算效率和顺序最优性，无论是在行动空间大小还是时间长度上。