Timezone: »
Games with continuous strategy sets arise in several machine learning problems (e.g. adversarial learning). For such games, simple no-regret learning algorithms exist in several cases and ensure convergence to coarse correlated equilibria (CCE). The efficiency of such equilibria with respect to a social function, however, is not well understood. In this paper, we define the class of valid utility games with continuous strategies and provide efficiency bounds for their CCEs. Our bounds rely on the social function satisfying recently introduced notions of submodularity over continuous domains. We further refine our bounds based on the curvature of the social function. Furthermore, we extend our efficiency bounds to a class of non-submodular functions that satisfy approximate submodularity properties. Finally, we show that valid utility games with continuous strategies can be designed to maximize monotone DR-submodular functions subject to disjoint constraints with approximation guarantees. The approximation guarantees we derive are based on the efficiency of the equilibria of such games and can improve the existing ones in the literature. We illustrate and validate our results on a budget allocation game and a sensor coverage problem.
Author Information
Pier Giuseppe Sessa (ETH Zürich)
More from the Same Authors
-
2023 : DISTRIBUTIONALLY ROBUST MODEL-BASED REINFORCEMENT LEARNING WITH LARGE STATE SPACES »
Shyam Sundhar Ramesh · Pier Giuseppe Sessa · Yifan Hu · Andreas Krause · Ilija Bogunovic -
2023 : Optimistic Games for Combinatorial Bayesian Optimization with Applications to Protein Design »
Melis Ilayda Bal · Pier Giuseppe Sessa · Mojmir Mutny · Andreas Krause -
2023 Poster: Multitask Learning with No Regret: from Improved Confidence Bounds to Active Learning »
Pier Giuseppe Sessa · Pierre Laforgue · Nicolò Cesa-Bianchi · Andreas Krause -
2022 Poster: Movement Penalized Bayesian Optimization with Application to Wind Energy Systems »
Shyam Sundhar Ramesh · Pier Giuseppe Sessa · Andreas Krause · Ilija Bogunovic -
2020 Poster: Contextual Games: Multi-Agent Learning with Side Information »
Pier Giuseppe Sessa · Ilija Bogunovic · Andreas Krause · Maryam Kamgarpour -
2020 Poster: Learning to Play Sequential Games versus Unknown Opponents »
Pier Giuseppe Sessa · Ilija Bogunovic · Maryam Kamgarpour · Andreas Krause -
2019 Poster: No-Regret Learning in Unknown Games with Correlated Payoffs »
Pier Giuseppe Sessa · Ilija Bogunovic · Maryam Kamgarpour · Andreas Krause