Semi-Parametric Contextual Bandits with Graph-Laplacian Regularization
Non-stationarity is ubiquitous in human behavior and addressing it in the
contextual bandits is challenging. Several works have addressed the problem by
investigating semi-parametric contextual bandits and warned that ignoring
non-stationarity could harm performances. Another prevalent human behavior is
social interaction which has become available in a form of a social network or
graph structure. As a result, graph-based contextual bandits have received much
attention. In this paper, we propose "SemiGraphTS," a novel contextual
Thompson-sampling algorithm for a graph-based semi-parametric reward model. Our
algorithm is the first to be proposed in this setting. We derive an upper bound
of the cumulative regret that can be expressed as a multiple of a factor
depending on the graph structure and the order for the semi-parametric model
without a graph. We evaluate the proposed and existing algorithms via
simulation and real data example.