`

Timezone: »

 
Poster
Understanding Bandits with Graph Feedback
Houshuang Chen · zengfeng Huang · Shuai Li · Chihao Zhang

Thu Dec 09 12:30 AM -- 02:00 AM (PST) @
The bandit problem with graph feedback, proposed in [Mannor and Shamir, NeurIPS 2011], is modeled by a directed graph $G=(V,E)$ where $V$ is the collection of bandit arms, and once an arm is triggered, all its incident arms are observed. A fundamental question is how the structure of the graph affects the min-max regret. We propose the notions of the fractional weak domination number $\delta^*$ and the $k$-packing independence number capturing upper bound and lower bound for the regret respectively. We show that the two notions are inherently connected via aligning them with the linear program of the weakly dominating set and its dual --- the fractional vertex packing set respectively. Based on this connection, we utilize the strong duality theorem to prove a general regret upper bound $O\left(\left(\delta^*\log |V|\right)^{\frac{1}{3}}T^{\frac{2}{3}}\right)$ and a lower bound $\Omega\left(\left(\delta^*/\alpha\right)^{\frac{1}{3}}T^{\frac{2}{3}}\right)$ where $\alpha$ is the integrality gap of the dual linear program. Therefore, our bounds are tight up to a $\left(\log |V|\right)^{\frac{1}{3}}$ factor on graphs with bounded integrality gap for the vertex packing problem including trees and graphs with bounded degree. Moreover, we show that for several special families of graphs, we can get rid of the $\left(\log |V|\right)^{\frac{1}{3}}$ factor and establish optimal regret.

Author Information

Houshuang Chen (Shanghai Jiao Tong University)
zengfeng Huang (Fudan University)
Shuai Li (Shanghai Jiao Tong University)
Chihao Zhang (Shanghai Jiao Tong University)

More from the Same Authors

  • 2021 : User-in-the-Loop Named Entity Recognition via Counterfactual Learning »
    Tong Yu · Junda Wu · Ruiyi Zhang · Handong Zhao · Shuai Li
  • 2021 : Sim-to-Real Interactive Recommendation via Off-Dynamics Reinforcement Learning »
    Junda Wu · Zhihui Xie · Tong Yu · Qizhi Li · Shuai Li
  • 2021 Poster: BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation »
    Mingguo He · Zhewei Wei · zengfeng Huang · Hongteng Xu
  • 2021 Poster: The Hardness Analysis of Thompson Sampling for Combinatorial Semi-bandits with Greedy Oracle »
    Fang Kong · Yueran Yang · Wei Chen · Shuai Li
  • 2020 Poster: Online Influence Maximization under Linear Threshold Model »
    Shuai Li · Fang Kong · Kejie Tang · Qizhi Li · Wei Chen
  • 2019 : Poster and Coffee Break 2 »
    Karol Hausman · Kefan Dong · Ken Goldberg · Lihong Li · Lin Yang · Lingxiao Wang · Lior Shani · Liwei Wang · Loren Amdahl-Culleton · Lucas Cassano · Marc Dymetman · Marc Bellemare · Marcin Tomczak · Margarita Castro · Marius Kloft · Marius-Constantin Dinu · Markus Holzleitner · Martha White · Mengdi Wang · Michael Jordan · Mihailo Jovanovic · Ming Yu · Minshuo Chen · Moonkyung Ryu · Muhammad Zaheer · Naman Agarwal · Nan Jiang · Niao He · Nikolaus Yasui · Nikos Karampatziakis · Nino Vieillard · Ofir Nachum · Olivier Pietquin · Ozan Sener · Pan Xu · Parameswaran Kamalaruban · Paul Mineiro · Paul Rolland · Philip Amortila · Pierre-Luc Bacon · Prakash Panangaden · Qi Cai · Qiang Liu · Quanquan Gu · Raihan Seraj · Richard Sutton · Rick Valenzano · Robert Dadashi · Rodrigo Toro Icarte · Roshan Shariff · Roy Fox · Ruosong Wang · Saeed Ghadimi · Samuel Sokota · Sean Sinclair · Sepp Hochreiter · Sergey Levine · Sergio Valcarcel Macua · Sham Kakade · Shangtong Zhang · Sheila McIlraith · Shie Mannor · Shimon Whiteson · Shuai Li · Shuang Qiu · Wai Lok Li · Siddhartha Banerjee · Sitao Luan · Tamer Basar · Thinh Doan · Tianhe Yu · Tianyi Liu · Tom Zahavy · Toryn Klassen · Tuo Zhao · Vicenç Gómez · Vincent Liu · Volkan Cevher · Wesley Suttle · Xiao-Wen Chang · Xiaohan Wei · Xiaotong Liu · Xingguo Li · Xinyi Chen · Xingyou Song · Yao Liu · YiDing Jiang · Yihao Feng · Yilun Du · Yinlam Chow · Yinyu Ye · Yishay Mansour · · Yonathan Efroni · Yongxin Chen · Yuanhao Wang · Bo Dai · Chen-Yu Wei · Harsh Shrivastava · Hongyang Zhang · Qinqing Zheng · SIDDHARTHA SATPATHI · Xueqing Liu · Andreu Vall
  • 2019 Poster: Optimal Sparsity-Sensitive Bounds for Distributed Mean Estimation »
    zengfeng Huang · Ziyue Huang · Yilei WANG · Ke Yi
  • 2018 Poster: TopRank: A practical algorithm for online stochastic ranking »
    Tor Lattimore · Branislav Kveton · Shuai Li · Csaba Szepesvari