Timezone: »
We consider the problem of learning to play a repeated multi-agent game with an unknown reward function. Single player online learning algorithms attain strong regret bounds when provided with full information feedback, which unfortunately is unavailable in many real-world scenarios. Bandit feedback alone, i.e., observing outcomes only for the selected action, yields substantially worse performance. In this paper, we consider a natural model where, besides a noisy measurement of the obtained reward, the player can also observe the opponents' actions. This feedback model, together with a regularity assumption on the reward function, allows us to exploit the correlations among different game outcomes by means of Gaussian processes (GPs). We propose a novel confidence-bound based bandit algorithm GP-MW, which utilizes the GP model for the reward function and runs a multiplicative weight (MW) method. We obtain novel kernel-dependent regret bounds that are comparable to the known bounds in the full information setting, while substantially improving upon the existing bandit results. We experimentally demonstrate the effectiveness of GP-MW in random matrix games, as well as real-world problems of traffic routing and movie recommendation. In our experiments, GP-MW consistently outperforms several baselines, while its performance is often comparable to methods that have access to full information feedback.
Author Information
Pier Giuseppe Sessa (ETH Zürich)
Ilija Bogunovic (ETH Zurich)
Maryam Kamgarpour (ETH Zürich)
Andreas Krause (ETH Zurich)
More from the Same Authors
-
2020 Poster: Adaptive Sampling for Stochastic Risk-Averse Learning »
Sebastian Curi · Kfir Y. Levy · Stefanie Jegelka · Andreas Krause -
2020 Poster: Contextual Games: Multi-Agent Learning with Side Information »
Pier Giuseppe Sessa · Ilija Bogunovic · Andreas Krause · Maryam Kamgarpour -
2020 Poster: Coresets via Bilevel Optimization for Continual Learning and Streaming »
Zalán Borsos · Mojmir Mutny · Andreas Krause -
2020 Poster: Gradient Estimation with Stochastic Softmax Tricks »
Max Paulus · Dami Choi · Daniel Tarlow · Andreas Krause · Chris J. Maddison -
2020 Oral: Gradient Estimation with Stochastic Softmax Tricks »
Max Paulus · Dami Choi · Daniel Tarlow · Andreas Krause · Chris J. Maddison -
2020 Poster: Efficient Model-Based Reinforcement Learning through Optimistic Policy Search and Planning »
Sebastian Curi · Felix Berkenkamp · Andreas Krause -
2020 Poster: Learning to Play Sequential Games versus Unknown Opponents »
Pier Giuseppe Sessa · Ilija Bogunovic · Maryam Kamgarpour · Andreas Krause -
2020 Spotlight: Efficient Model-Based Reinforcement Learning through Optimistic Policy Search and Planning »
Sebastian Curi · Felix Berkenkamp · Andreas Krause -
2020 Poster: Safe Reinforcement Learning via Curriculum Induction »
Matteo Turchetta · Andrey Kolobov · Shital Shah · Andreas Krause · Alekh Agarwal -
2020 Spotlight: Safe Reinforcement Learning via Curriculum Induction »
Matteo Turchetta · Andrey Kolobov · Shital Shah · Andreas Krause · Alekh Agarwal -
2019 Poster: Efficiently Learning Fourier Sparse Set Functions »
Andisheh Amrollahi · Amir Zandieh · Michael Kapralov · Andreas Krause -
2019 Spotlight: Efficiently Learning Fourier Sparse Set Functions »
Andisheh Amrollahi · Amir Zandieh · Michael Kapralov · Andreas Krause -
2019 Poster: Stochastic Bandits with Context Distributions »
Johannes Kirschner · Andreas Krause -
2019 Poster: A Domain Agnostic Measure for Monitoring and Evaluating GANs »
Paulina Grnarova · Kfir Y. Levy · Aurelien Lucchi · Nathanael Perraudin · Ian Goodfellow · Thomas Hofmann · Andreas Krause -
2019 Poster: Teaching Multiple Concepts to a Forgetful Learner »
Anette Hunziker · Yuxin Chen · Oisin Mac Aodha · Manuel Gomez Rodriguez · Andreas Krause · Pietro Perona · Yisong Yue · Adish Singla -
2019 Poster: Adaptive Sequence Submodularity »
Marko Mitrovic · Ehsan Kazemi · Moran Feldman · Andreas Krause · Amin Karbasi -
2019 Poster: Safe Exploration for Interactive Machine Learning »
Matteo Turchetta · Felix Berkenkamp · Andreas Krause -
2018 Poster: Provable Variational Inference for Constrained Log-Submodular Models »
Josip Djolonga · Stefanie Jegelka · Andreas Krause -
2018 Poster: Efficient High Dimensional Bayesian Optimization with Additivity and Quadrature Fourier Features »
Mojmir Mutny · Andreas Krause -
2018 Spotlight: Efficient High Dimensional Bayesian Optimization with Additivity and Quadrature Fourier Features »
Mojmir Mutny · Andreas Krause -
2018 Poster: Fairness Behind a Veil of Ignorance: A Welfare Analysis for Automated Decision Making »
Hoda Heidari · Claudio Ferrari · Krishna Gummadi · Andreas Krause -
2017 Workshop: Discrete Structures in Machine Learning »
Yaron Singer · Jeff A Bilmes · Andreas Krause · Stefanie Jegelka · Amin Karbasi -
2017 Poster: Interactive Submodular Bandit »
Lin Chen · Andreas Krause · Amin Karbasi -
2017 Poster: Safe Model-based Reinforcement Learning with Stability Guarantees »
Felix Berkenkamp · Matteo Turchetta · Angela Schoellig · Andreas Krause -
2017 Poster: Differentiable Learning of Submodular Functions »
Josip Djolonga · Andreas Krause -
2017 Spotlight: Differentiable Learning of Submodular Functions »
Josip Djolonga · Andreas Krause -
2017 Poster: Non-monotone Continuous DR-submodular Maximization: Structure and Algorithms »
Yatao Bian · Kfir Levy · Andreas Krause · Joachim M Buhmann -
2017 Poster: Stochastic Submodular Maximization: The Case of Coverage Functions »
Mohammad Karimi · Mario Lucic · Hamed Hassani · Andreas Krause -
2016 Poster: Variational Inference in Mixed Probabilistic Submodular Models »
Josip Djolonga · Sebastian Tschiatschek · Andreas Krause -
2016 Poster: Truncated Variance Reduction: A Unified Approach to Bayesian Optimization and Level-Set Estimation »
Ilija Bogunovic · Jonathan Scarlett · Andreas Krause · Volkan Cevher -
2016 Poster: Cooperative Graphical Models »
Josip Djolonga · Stefanie Jegelka · Sebastian Tschiatschek · Andreas Krause -
2016 Poster: Fast and Provably Good Seedings for k-Means »
Olivier Bachem · Mario Lucic · Hamed Hassani · Andreas Krause -
2016 Oral: Fast and Provably Good Seedings for k-Means »
Olivier Bachem · Mario Lucic · Hamed Hassani · Andreas Krause -
2016 Poster: Safe Exploration in Finite Markov Decision Processes with Gaussian Processes »
Matteo Turchetta · Felix Berkenkamp · Andreas Krause -
2015 Poster: Distributed Submodular Cover: Succinctly Summarizing Massive Data »
Baharan Mirzasoleiman · Amin Karbasi · Ashwinkumar Badanidiyuru · Andreas Krause -
2015 Poster: Sampling from Probabilistic Submodular Models »
Alkis Gotovos · Hamed Hassani · Andreas Krause -
2015 Spotlight: Distributed Submodular Cover: Succinctly Summarizing Massive Data »
Baharan Mirzasoleiman · Amin Karbasi · Ashwinkumar Badanidiyuru · Andreas Krause -
2015 Oral: Sampling from Probabilistic Submodular Models »
Alkis Gotovos · Hamed Hassani · Andreas Krause -
2014 Workshop: NIPS’14 Workshop on Crowdsourcing and Machine Learning »
David Parkes · Denny Zhou · Chien-Ju Ho · Nihar Bhadresh Shah · Adish Singla · Jared Heyman · Edwin Simpson · Andreas Krause · Rafael Frongillo · Jennifer Wortman Vaughan · Panagiotis Papadimitriou · Damien Peters -
2014 Workshop: Discrete Optimization in Machine Learning »
Jeffrey A Bilmes · Andreas Krause · Stefanie Jegelka · S Thomas McCormick · Sebastian Nowozin · Yaron Singer · Dhruv Batra · Volkan Cevher -
2014 Poster: Efficient Sampling for Learning Sparse Additive Models in High Dimensions »
Hemant Tyagi · Bernd Gärtner · Andreas Krause -
2014 Poster: From MAP to Marginals: Variational Inference in Bayesian Submodular Models »
Josip Djolonga · Andreas Krause -
2014 Poster: Efficient Partial Monitoring with Prior Information »
Hastagiri P Vanchinathan · Gábor Bartók · Andreas Krause -
2013 Workshop: Machine Learning for Sustainability »
Edwin Bonilla · Thomas Dietterich · Theodoros Damoulas · Andreas Krause · Daniel Sheldon · Iadine Chades · J. Zico Kolter · Bistra Dilkina · Carla Gomes · Hugo P Simao -
2013 Workshop: Bayesian Optimization in Theory and Practice »
Matthew Hoffman · Jasper Snoek · Nando de Freitas · Michael A Osborne · Ryan Adams · Sebastien Bubeck · Philipp Hennig · Remi Munos · Andreas Krause -
2013 Workshop: Discrete Optimization in Machine Learning: Connecting Theory and Practice »
Stefanie Jegelka · Andreas Krause · Pradeep Ravikumar · Kazuo Murota · Jeffrey A Bilmes · Yisong Yue · Michael Jordan -
2013 Poster: High-Dimensional Gaussian Process Bandits »
Josip Djolonga · Andreas Krause · Volkan Cevher -
2013 Poster: Distributed Submodular Maximization: Identifying Representative Elements in Massive Data »
Baharan Mirzasoleiman · Amin Karbasi · Rik Sarkar · Andreas Krause -
2012 Workshop: Discrete Optimization in Machine Learning (DISCML): Structure and Scalability »
Stefanie Jegelka · Andreas Krause · Jeffrey A Bilmes · Pradeep Ravikumar -
2011 Workshop: Discrete Optimization in Machine Learning (DISCML): Uncertainty, Generalization and Feedback »
Andreas Krause · Pradeep Ravikumar · Stefanie S Jegelka · Jeffrey A Bilmes -
2011 Oral: Scalable Training of Mixture Models via Coresets »
Dan Feldman · Matthew Faulkner · Andreas Krause -
2011 Poster: Scalable Training of Mixture Models via Coresets »
Dan Feldman · Matthew Faulkner · Andreas Krause -
2011 Poster: Contextual Gaussian Process Bandit Optimization »
Andreas Krause · Cheng Soon Ong -
2011 Poster: Crowdclustering »
Ryan G Gomes · Peter Welinder · Andreas Krause · Pietro Perona -
2010 Workshop: Discrete Optimization in Machine Learning: Structures, Algorithms and Applications »
Andreas Krause · Pradeep Ravikumar · Jeffrey A Bilmes · Stefanie Jegelka -
2010 Spotlight: Efficient Minimization of Decomposable Submodular Functions »
Peter G Stobbe · Andreas Krause -
2010 Poster: Discriminative Clustering by Regularized Information Maximization »
Ryan G Gomes · Andreas Krause · Pietro Perona -
2010 Poster: Efficient Minimization of Decomposable Submodular Functions »
Peter G Stobbe · Andreas Krause -
2010 Poster: Near-Optimal Bayesian Active Learning with Noisy Observations »
Daniel Golovin · Andreas Krause · Debajyoti Ray -
2009 Workshop: Discrete Optimization in Machine Learning: Submodularity, Polyhedra and Sparsity »
Andreas Krause · Pradeep Ravikumar · Jeffrey A Bilmes -
2009 Poster: Online Learning of Assignments »
Matthew Streeter · Daniel Golovin · Andreas Krause -
2009 Spotlight: Online Learning of Assignments »
Matthew Streeter · Daniel Golovin · Andreas Krause -
2007 Spotlight: Selecting Observations against Adversarial Objectives »
Andreas Krause · H. Brendan McMahan · Carlos Guestrin · Anupam Gupta -
2007 Poster: Selecting Observations against Adversarial Objectives »
Andreas Krause · H. Brendan McMahan · Carlos Guestrin · Anupam Gupta