Timezone: »
Poster
A Gang of Adversarial Bandits
Mark Herbster · Stephen Pasteris · Fabio Vitale · Massimiliano Pontil
We consider running multiple instances of multi-armed bandit (MAB) problems in parallel. A main motivation for this study are online recommendation systems, in which each of $N$ users is associated with a MAB problem and the goal is to exploit users' similarity in order to learn users' preferences to $K$ items more efficiently. We consider the adversarial MAB setting, whereby an adversary is free to choose which user and which loss to present to the learner during the learning process. Users are in a social network and the learner is aided by a-priori knowledge of the strengths of the social links between all pairs of users. It is assumed that if the social link between two users is strong then they tend to share the same action. The regret is measured relative to an arbitrary function which maps users to actions. The smoothness of the function is captured by a resistance-based dispersion measure $\Psi$. We present two learning algorithms, GABA-I and GABA-II, which exploit the network structure to bias towards functions of low $\Psi$ values. We show that GABA-I has an expected regret bound of $\mathcal{O}(\sqrt{\ln(NK/\Psi)\Psi KT})$ and per-trial time complexity of $\mathcal{O}(K\ln(N))$, whilst GABA-II has a weaker $\mathcal{O}(\sqrt{\ln(N/\Psi)\ln(NK/\Psi)\Psi KT})$ regret, but a better $\mathcal{O}(\ln(K)\ln(N))$ per-trial time complexity. We highlight improvements of both algorithms over running independent standard MABs across users.
Author Information
Mark Herbster (University College London)
Stephen Pasteris (University College London)
Fabio Vitale (University of Lille)
Massimiliano Pontil (IIT & UCL)
More from the Same Authors
-
2021 : Linear Convergence of Batch Greenkhorn for Regularized Multimarginal Optimal Transport »
Vladimir Kostic · Saverio Salzo · Massimiliano Pontil -
2022 Poster: Conditional Meta-Learning of Linear Representations »
Giulia Denevi · Massimiliano Pontil · Carlo Ciliberto -
2023 Poster: Sharp Spectral Rates for Koopman Operator Learning »
Vladimir Kostic · Karim Lounici · Pietro Novelli · Massimiliano Pontil -
2023 Poster: Estimating Koopman operators with sketching to provably learn large scale dynamical systems »
Giacomo Meanti · Antoine Chatalic · Vladimir Kostic · Pietro Novelli · Massimiliano Pontil · Lorenzo Rosasco -
2023 Poster: Transfer learning for atomistic simulations using GNNs and kernel mean embeddings »
John Falk · Luigi Bonati · Pietro Novelli · Michele Parrinello · Massimiliano Pontil -
2023 Poster: Nearest Neighbour with Bandit Feedback »
Stephen Pasteris · Chris Hicks · Vasilios Mavroudis -
2022 Spotlight: Conditional Meta-Learning of Linear Representations »
Giulia Denevi · Massimiliano Pontil · Carlo Ciliberto -
2022 Spotlight: Lightning Talks 3B-1 »
Tianying Ji · Tongda Xu · Giulia Denevi · Aibek Alanov · Martin Wistuba · Wei Zhang · Yuesong Shen · Massimiliano Pontil · Vadim Titov · Yan Wang · Yu Luo · Daniel Cremers · Yanjun Han · Arlind Kadra · Dailan He · Josif Grabocka · Zhengyuan Zhou · Fuchun Sun · Carlo Ciliberto · Dmitry Vetrov · Mingxuan Jing · Chenjian Gao · Aaron Flores · Tsachy Weissman · Han Gao · Fengxiang He · Kunzan Liu · Wenbing Huang · Hongwei Qin -
2022 Spotlight: A gradient estimator via L1-randomization for online zero-order optimization with two point feedback »
Arya Akhavan · Evgenii Chzhen · Massimiliano Pontil · Alexandre Tsybakov -
2022 Poster: A gradient estimator via L1-randomization for online zero-order optimization with two point feedback »
Arya Akhavan · Evgenii Chzhen · Massimiliano Pontil · Alexandre Tsybakov -
2022 Poster: Learning Dynamical Systems via Koopman Operator Regression in Reproducing Kernel Hilbert Spaces »
Vladimir Kostic · Pietro Novelli · Andreas Maurer · Carlo Ciliberto · Lorenzo Rosasco · Massimiliano Pontil -
2022 Poster: Group Meritocratic Fairness in Linear Contextual Bandits »
Riccardo Grazzi · Arya Akhavan · John IF Falk · Leonardo Cella · Massimiliano Pontil -
2021 Poster: Concentration inequalities under sub-Gaussian and sub-exponential conditions »
Andreas Maurer · Massimiliano Pontil -
2021 Poster: Improved Regret Bounds for Tracking Experts with Memory »
James Robinson · Mark Herbster -
2021 Poster: The Role of Global Labels in Few-Shot Classification and How to Infer Them »
Ruohan Wang · Massimiliano Pontil · Carlo Ciliberto -
2021 Poster: Cooperative Stochastic Bandits with Asynchronous Agents and Constrained Feedback »
Lin Yang · Yu-Zhen Janice Chen · Stephen Pasteris · Mohammad Hajiesmaili · John C. S. Lui · Don Towsley -
2021 Poster: Distributed Zero-Order Optimization under Adversarial Noise »
Arya Akhavan · Massimiliano Pontil · Alexandre Tsybakov -
2020 Poster: Online Matrix Completion with Side Information »
Mark Herbster · Stephen Pasteris · Lisa Tse -
2020 Poster: Exploiting MMD and Sinkhorn Divergences for Fair and Transferable Representation Learning »
Luca Oneto · Michele Donini · Giulia Luise · Carlo Ciliberto · Andreas Maurer · Massimiliano Pontil -
2020 Poster: Fair regression with Wasserstein barycenters »
Evgenii Chzhen · Christophe Denis · Mohamed Hebiri · Luca Oneto · Massimiliano Pontil -
2020 Poster: Fair regression via plug-in estimator and recalibration with statistical guarantees »
Evgenii Chzhen · Christophe Denis · Mohamed Hebiri · Luca Oneto · Massimiliano Pontil -
2020 Oral: Fair regression via plug-in estimator and recalibration with statistical guarantees »
Evgenii Chzhen · Christophe Denis · Mohamed Hebiri · Luca Oneto · Massimiliano Pontil -
2020 Poster: Online Multitask Learning with Long-Term Memory »
Mark Herbster · Stephen Pasteris · Lisa Tse -
2019 Poster: Leveraging Labeled and Unlabeled Data for Consistent Fair Binary Classification »
Evgenii Chzhen · Christophe Denis · Mohamed Hebiri · Luca Oneto · Massimiliano Pontil -
2019 Poster: Online Prediction of Switching Graph Labelings with Cluster Specialists »
Mark Herbster · James Robinson -
2018 Poster: Differential Properties of Sinkhorn Approximation for Learning with Wasserstein Distance »
Giulia Luise · Alessandro Rudi · Massimiliano Pontil · Carlo Ciliberto -
2018 Poster: Empirical Risk Minimization Under Fairness Constraints »
Michele Donini · Luca Oneto · Shai Ben-David · John Shawe-Taylor · Massimiliano Pontil -
2016 Poster: Mistake Bounds for Binary Matrix Completion »
Mark Herbster · Stephen Pasteris · Massimiliano Pontil -
2015 Poster: Online Prediction at the Limit of Zero Temperature »
Mark Herbster · Stephen Pasteris · Shaona Ghosh -
2012 Poster: Online Sum-Product Computation »
Mark Herbster · Fabio Vitale · Stephen Pasteris -
2008 Poster: Fast Prediction on a Tree »
Mark Herbster · Massimiliano Pontil · Sergio Rojas Galeano -
2008 Oral: Fast Prediction on a Tree »
Mark Herbster · Massimiliano Pontil · Sergio Rojas Galeano -
2008 Poster: On-Line Prediction on Large Diameter Graphs »
Mark Herbster · Massimiliano Pontil · Guy Lever -
2006 Poster: Prediction on a Graph with a Perceptron »
Mark Herbster · Massimiliano Pontil -
2006 Spotlight: Prediction on a Graph with a Perceptron »
Mark Herbster · Massimiliano Pontil