Spectral Thompson Sampling

Thompson Sampling (TS) has surged a lot of interest due to its good empirical performance, in particular in the compu-tational advertising. Though successful, the tools for its per-formance analysis appeared only recently. In this paper, we describe and analyze SpectralTS algorithm for a bandit prob-lem, where the payoffs of the choices are smooth given an underlying graph. In this setting, each choice is a node of a graph and the expected payoffs of the neighboring nodes are assumed to be similar. Although the setting has application both in recommender systems and advertising, the traditional algorithms would scale poorly with the number of choices. For that purpose we consider an effective dimension d, which is small in real-world graphs. We deliver the analysis show-ing that the regret of SpectralTS scales as d T lnN with high probability, where T is the time horizon and N is the number of choices. Since a d T lnN regret is comparable to the known results, SpectralTS offers a computationally more efficient alternative. We also show that our algorithm is com-petitive on both synthetic and real-world data