Problem-dependent Regret Bounds for Online Learning with Feedback Graphs

@InProceedings{pmlr-v115-hu20b,
  title = 	 {Problem-dependent Regret Bounds for Online Learning with Feedback Graphs},
  author =       {Hu, Bingshan and Mehta, Nishant A. and Pan, Jianping},
  booktitle = 	 {Proceedings of The 35th Uncertainty in Artificial Intelligence Conference},
  pages = 	 {852--861},
  year = 	 {2020},
  editor = 	 {Adams, Ryan P. and Gogate, Vibhav},
  volume = 	 {115},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {22--25 Jul},
  publisher =    {PMLR},
  pdf = 	 {http://proceedings.mlr.press/v115/hu20b/hu20b.pdf},
  url = 	 {https://proceedings.mlr.press/v115/hu20b.html},
  abstract = 	 {This paper addresses the stochastic multi-armed bandit problem with an undirected feedback graph. We devise a UCB-based algorithm, UCB-NE, to provide a problem-dependent regret bound that depends on a clique covering. Our algorithm obtains regret which provably scales linearly with the clique covering number. Additionally, we provide problem-dependent regret bounds for a Thompson Sampling-based algorithm, TS-N, where again the bounds are linear in the clique covering number. Finally, we present experimental results to see how UCB-NE, TS-N, and a few related algorithms perform practically.}
}