Semi-Parametric Contextual Bandits with Graph-Laplacian Regularization
This work addresses non-stationarity and social network effects in contextual bandits, which is incremental as it combines existing semi-parametric and graph-based approaches.
The authors tackled the problem of non-stationarity and social interactions in contextual bandits by proposing SemiGraphTS, a novel algorithm that integrates graph-based semi-parametric reward modeling, achieving a cumulative regret bound dependent on graph structure and model order.
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.