02/02/2021

Stochastic Bandits with Graph Feedback in Non-Stationary Environments

Shiyin Lu, Yao Hu, Lijun Zhang

Keywords:

Abstract Paper Similar Papers

Abstract: We study a variant of stochastic bandits where the feedback model is specified by a graph. In this setting, after playing an arm, one can observe rewards of not only the played arm but also other arms that are adjacent to the played arm in the graph. Most of the existing work assumes the reward distributions are stationary over time, which, however, is often violated in common scenarios such as recommendation systems and online advertising. To address this limitation, we study stochastic bandits with graph feedback in non-stationary environments and propose algorithms with graph-dependent dynamic regret bounds. When the number of reward distribution changes L is known in advance, one of our algorithms achieves an Õ(√(αLT)) dynamic regret bound. We also develop an adaptive algorithm that can adapt to unknown L and attain an Õ(√(θLT)) dynamic regret. Here, α and θ are some graph-dependent quantities and T is the time horizon.

The video of this talk cannot be embedded. You can watch it here:
https://slideslive.com/38949063
(Link will open in new window)
 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at AAAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 17:05 
 0
 0
 0
 0
 12:51 
 0
 0
 0
 0
 19:29 
 0
 0
 0
 0
 12:28 
 0
 0
 0
 0
 14:52 
 0
 0
 0
 0
 2:47 
 0
 0
 0
 0
 13:14 
 0
 0
 0
 0
 17:09 
 0
 0
 0
 0
 14:14 
 0
 0
 0
 0
 14:17 
 0
 0
 0
 0
 15:41 
 0
 0
 0
 0
 3:18 
 0
 0
 0
 0
 5:09 
 0
 0
 0
 0
 14:46 
 0
 0
 0
 0
 3:10 
 0
 0
 0
 0
 3:19 
 0
 0
 0
 0
 3:22 
 0
 0
 0
 0
 13:07 
 0
 0
 0
 0
 9:20 
 0
 0
 0
 0
 2:10 
 0
 0
 0
 0
 16:44 
 0
 0
 0
 0
 3:02 
 0
 0
 0
 0
 12:07 
 0
 0
 0
 0
 15:20 
 0
 0
 0
 0
 7:32 
 0
 0
 0
 0
 4:53 
 0
 0
 0
 0
 14:00 
 0
 0
 0
 0
 2:43 
 0
 0
 0
 0
 20:29 
 0
 0
 0
 0
 13:22 
 0
 0
 0
 0
 5:15 
 0
 0
 0
 0
 18:32 
 0
 0
 0
 0
 13:06 
 0
 0
 0
 0
 13:49 
 0
 0
 0
 0
 5:12 
 0
 0
 0
 0
 5:53 
 0
 0
 0
 0
 6:05 
 0
 0
 0
 0
 18:34 
 0
 0
 0
 0
 20:14 
 0
 0
 0
 0
 5:18