← Back to papers
2019 UAI UAI 2019

Problem-dependent Regret Bounds for Online Learning with Feedback Graphs

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.

🚀 Conference Pioneer — UAI 2019
🐣 Hot Topic Early Bird — multi-armed bandit
🐝 Cross-Pollinator — Artificial Intelligence, Computer Science, Data Science & Analytics, Deep Learning, Interdisciplinary, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning, Robotics, Security & Privacy
🌉 Interdisciplinary Bridge — Machine Learning and Mathematics & Optimization

Authors

Bingshan Hu , Nishant A. Mehta , Jianping Pan

Topics

Machine Learning > Optimization & Theory > Learning Theory Mathematics & Optimization > Optimization > Online Algorithms Machine Learning > Learning Types > Online Learning Machine Learning > Optimization & Theory > Stochastic Methods Machine Learning > Learning Types > Multi-Armed Bandits

Keywords

ucb algorithm thompson sampling multi-armed bandit regret bound stochastic bandit feedback graph
Download PDF

Related papers

Fisher-Bures Adversary Graph Convolutional Networks 2019
Augmenting and Tuning Knowledge Graph Embeddings 2019
Learning Factored Markov Decision Processes with Unawareness 2019
Expressive Priors in Bayesian Neural Networks: Kernel Combinations and Periodic Functions 2019
Countdown Regression: Sharp and Calibrated Survival Predictions 2019