Be Greedy: How Chromatic Number meets Regret Minimization in Graph Bandits.

We study the classical linear bandit problem on graphs modeling arm rewards through an underlying graph structure \(G\)(\(V\),\(E\)) such that rewards of neighboring nodes are similar. Previous attempts along this line have primarily considered the arm rewards to be a smooth function over graph Laplacian, which however failed to characterize the inherent problem complexity in terms of the graph structure.%, where lies the primary motivation of this work. We bridge this gap by showing a regret guarantee of \(\tO(\chi(\overline{G})\sqrt{T})\) \footnote{\(\tO(\cdot)\) notation hides dependencies on \(\log T\).} that scales only with the chromatic number of the complement graph \(\chi(\overline{G})\), assuming the rewards to be a smooth function over a general class of graph embeddings—Orthonormal Representations. Our proposed algorithms yield a regret guarantee of \(\tilde O(r\sqrt T)\) for any general embedding of rank \(r\). Moreover, if the rewards correspond to a minimum rank embedding, the regret boils down to \(\tO(\chi(\overline{G})\sqrt{T})\)–none of the existing works were able to bring out such influences of graph structures over arm rewards. Finally, noting that computing the above minimum rank embedding is NP-Hard, we also propose an alternative \(O(|V| + |E|)\) time computable embedding scheme—{\it Greedy Embeddings}—based on greedy graph coloring, with which our algorithms perform optimally on a large family of graphs, e.g. \hspace{-8pt} union of cliques, complement of \(k\)-colorable graphs, regular graphs, trees etc, and are also shown to outperform state-of-the-art methods on real datasets. Our findings open up new roads for exploiting graph structures on regret performance.