Timezone: »

 
Spotlight
Deep Hierarchy in Bandits
Joey Hong · Branislav Kveton · Sumeet Katariya · Manzil Zaheer · Mohammad Ghavamzadeh

Thu Jul 21 01:25 PM -- 01:30 PM (PDT) @ Ballroom 3 & 4
in T: Online Learning and Bandits »

Mean rewards of actions are often correlated. The form of these correlations may be complex and unknown a priori, such as the preferences of users for recommended products and their categories. To maximize statistical efficiency, it is important to leverage these correlations when learning. We formulate a bandit variant of this problem where the correlations of mean action rewards are represented by a hierarchical Bayesian model with latent variables. Since the hierarchy can have multiple layers, we call it deep. We propose a hierarchical Thompson sampling algorithm (HierTS) for this problem and show how to implement it efficiently for Gaussian hierarchies. The efficient implementation is possible due to a novel exact hierarchical representation of the posterior, which itself is of independent interest. We use this exact posterior to analyze the Bayes regret of HierTS. Our regret bounds reflect the structure of the problem, that the regret decreases with more informative priors, and can be recast to highlight reduced dependence on the number of actions. We confirm these theoretical findings empirically, in both synthetic and real-world experiments.

Keywords: T: Online Learning and Bandits · MISC: Online Learning, Active Learning and Bandits

Author Information

Joey Hong (Berkeley)
Branislav Kveton (Google Research)
Sumeet Katariya (UW-Madison and Amazon)
Manzil Zaheer (Google Research)
Mohammad Ghavamzadeh (Google Research)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors