Guy Lever

ICLR Conference 2024 Conference Paper

Generative Adversarial Equilibrium Solvers

• Denizalp Goktas
• David C. Parkes
• Ian Gemp
• Luke Marris
• Georgios Piliouras
• Romuald Elie
• Guy Lever
• Andrea Tacchetti

We introduce the use of generative adversarial learning to compute equilibria in general game-theoretic settings, specifically the generalized Nash equilibrium (GNE) in pseudo-games, and its specific instantiation as the competitive equilibrium (CE) in Arrow-Debreu competitive economies. Pseudo-games are a generalization of games in which players' actions affect not only the payoffs of other players but also their feasible action spaces. Although the computation of GNE and CE is intractable in the worst-case, i.e., PPAD-hard, in practice, many applications only require solutions with high accuracy in expectation over a distribution of problem instances. We introduce Generative Adversarial Equilibrium Solvers (GAES): a family of generative adversarial neural networks that can learn GNE and CE from only a sample of problem instances. We provide computational and sample complexity bounds for Lipschitz-smooth function approximators in a large class of concave pseudo-games, and apply the framework to finding Nash equilibria in normal-form games, CE in Arrow-Debreu competitive economies, and GNE in an environmental economic model of the Kyoto mechanism.

ICLR Conference 2024 Conference Paper

Replay across Experiments: A Natural Extension of Off-Policy RL

• Dhruva Tirumala
• Thomas Lampe
• José Enrique Chen
• Tuomas Haarnoja
• Sandy Han Huang
• Guy Lever
• Ben Moran
• Tim Hertweck

Replaying data is a principal mechanism underlying the stability and data efficiency of off-policy reinforcement learning (RL). We present an effective yet simple framework to extend the use of replays across multiple experiments, minimally adapting the RL workflow for sizeable improvements in controller performance and research iteration times. At its core, Replay across Experiments (RaE) involves reusing experience from previous experiments to improve exploration and bootstrap learning while reducing required changes to a minimum in comparison to prior work. We empirically show benefits across a number of RL algorithms and challenging control domains spanning both locomotion and manipulation, including hard exploration tasks from egocentric vision. Through comprehensive ablations, we demonstrate robustness to the quality and amount of data available and various hyperparameter choices. Finally, we discuss how our approach can be applied more broadly across research life cycles and can increase resilience by reloading data across random seeds or hyperparameter variations.

ICLR Conference 2020 Conference Paper

A Generalized Training Approach for Multiagent Learning

• Paul Muller
• Shayegan Omidshafiei
• Mark Rowland 0001
• Karl Tuyls
• Julien Pérolat
• Siqi Liu 0002
• Daniel Hennes
• Luke Marris

This paper investigates a population-based training regime based on game-theoretic principles called Policy-Spaced Response Oracles (PSRO). PSRO is general in the sense that it (1) encompasses well-known algorithms such as fictitious play and double oracle as special cases, and (2) in principle applies to general-sum, many-player games. Despite this, prior studies of PSRO have been focused on two-player zero-sum games, a regime where in Nash equilibria are tractably computable. In moving from two-player zero-sum games to more general settings, computation of Nash equilibria quickly becomes infeasible. Here, we extend the theoretical underpinnings of PSRO by considering an alternative solution concept, α-Rank, which is unique (thus faces no equilibrium selection issues, unlike Nash) and applies readily to general-sum, many-player settings. We establish convergence guarantees in several games classes, and identify links between Nash equilibria and α-Rank. We demonstrate the competitive performance of α-Rank-based PSRO against an exact Nash solver-based PSRO in 2-player Kuhn and Leduc Poker. We then go beyond the reach of prior PSRO applications by considering 3- to 5-player poker games, yielding instances where α-Rank achieves faster convergence than approximate Nash solvers, thus establishing it as a favorable general games solver. We also carry out an initial empirical validation in MuJoCo soccer, illustrating the feasibility of the proposed approach in another complex domain.

NeurIPS Conference 2019 Conference Paper

Biases for Emergent Communication in Multi-agent Reinforcement Learning

• Tom Eccles
• Yoram Bachrach
• Guy Lever
• Angeliki Lazaridou
• Thore Graepel

We study the problem of emergent communication, in which language arises because speakers and listeners must communicate information in order to solve tasks. In temporally extended reinforcement learning domains, it has proved hard to learn such communication without centralized training of agents, due in part to a difficult joint exploration problem. We introduce inductive biases for positive signalling and positive listening, which ease this problem. In a simple one-step environment, we demonstrate how these biases ease the learning problem. We also apply our methods to a more extended environment, showing that agents with these inductive biases achieve better performance, and analyse the resulting communications protocols.

AAMAS Conference 2019 Conference Paper

The Body is Not a Given: Joint Agent Policy Learning and Morphology Evolution

• Dylan Banarse
• Yoram Bachrach
• Siqi Liu
• Guy Lever
• Nicolas Heess
• Chrisantha Fernando
• Pushmeet Kohli
• Thore Graepel

Reinforcement learning (RL) has proven to be a powerful paradigm for deriving complex behaviors from simple reward signals in a wide range of environments. When applying RL to continuous control agents in simulated physics environments, the body is usually considered to be part of the environment. However, during evolution the physical body of biological organisms and their controlling brains are co-evolved, thus exploring a much larger space of actuator/controller configurations. Put differently, the intelligence does not reside only in the agent’s mind, but also in the design of their body. We propose a method for uncovering strong agents, consisting of a good combination of a body and policy, based on combining RL with an evolutionary procedure. Given the resulting agent, we also propose an approach for identifying the body changes that contributed the most to the agent performance. We use the Shapley value from cooperative game theory to find the fair contribution of individual components, taking into account synergies between components. We evaluate our methods in an environment similar to the the recently proposed Robo-Sumo task, where agents in a software physics simulator compete in tipping over their opponent or pushing them out of the arena. Our results show that the proposed methods are indeed capable of generating strong agents, significantly outperforming baselines that focus on optimizing the agent policy alone. A video is available at: https: //youtu. be/CHlecRim9PI

AAMAS Conference 2018 Conference Paper

Value-Decomposition Networks For Cooperative Multi-Agent Learning Based On Team Reward

• Peter Sunehag
• Guy Lever
• Audrunas Gruslys
• Wojciech Marian Czarnecki
• Vinicius Zambaldi
• Max Jaderberg
• Marc Lanctot
• Nicolas Sonnerat

We study the problem of cooperative multi-agent reinforcement learning with a single joint reward signal. This class of learning problems is difficult because of the often large combined action and observation spaces. In the fully centralized and decentralized approaches, we find the problem of spurious rewards and a phenomenon we call the “lazy agent” problem, which arises due to partial observability. We address these problems by training individual agents with a novel value-decomposition network architecture, which learns to decompose the team value function into agent-wise value functions.

JMLR Journal 2016 Journal Article

Approximate Newton Methods for Policy Search in Markov Decision Processes

• Thomas Furmston
• Guy Lever
• David Barber

Approximate Newton methods are standard optimization tools which aim to maintain the benefits of Newton's method, such as a fast rate of convergence, while alleviating its drawbacks, such as computationally expensive calculation or estimation of the inverse Hessian. In this work we investigate approximate Newton methods for policy optimization in Markov decision processes (MDPs). We first analyse the structure of the Hessian of the total expected reward, which is a standard objective function for MDPs. We show that, like the gradient, the Hessian exhibits useful structure in the context of MDPs and we use this analysis to motivate two Gauss-Newton methods for MDPs. Like the Gauss- Newton method for non-linear least squares, these methods drop certain terms in the Hessian. The approximate Hessians possess desirable properties, such as negative definiteness, and we demonstrate several important performance guarantees including guaranteed ascent directions, invariance to affine transformation of the parameter space and convergence guarantees. We finally provide a unifying perspective of key policy search algorithms, demonstrating that our second Gauss- Newton algorithm is closely related to both the EM-algorithm and natural gradient ascent applied to MDPs, but performs significantly better in practice on a range of challenging domains. [abs] [ pdf ][ bib ] &copy JMLR 2016. ( edit, beta )

AAAI Conference 2016 Conference Paper

Compressed Conditional Mean Embeddings for Model-Based Reinforcement Learning

• Guy Lever
• John Shawe-Taylor
• Ronnie Stafford
• Csaba Szepesvari

We present a model-based approach to solving Markov decision processes (MDPs) in which the system dynamics are learned using conditional mean embeddings (CMEs). This class of methods comes with strong performance guarantees, and enables planning to be performed in an induced finite (pseudo-)MDP, which approximates the MDP, but can be solved exactly using dynamic programming. Two drawbacks of existing methods exist: firstly, the size of the induced finite (pseudo-)MDP scales quadratically with the amount of data used to learn the model, costing much memory and time when planning with the learned model; secondly, learning the CME itself using powerful kernel least-squares is costly – a second computational bottleneck. We present an algorithm which maintains a rich kernelized CME model class, but solves both problems: firstly we demonstrate that the loss function for the CME model suggests a principled approach to compressing the induced (pseudo-)MDP, leading to faster planning, while maintaining guarantees; secondly we propose to learn the CME model itself using fast sparse-greedy kernel regression well-suited to the RL context. We demonstrate superior performance to existing methods in this class of modelbased approaches on a range of MDPs.

ICML Conference 2014 Conference Paper

Deterministic Policy Gradient Algorithms

• David Silver 0001
• Guy Lever
• Nicolas Heess
• Thomas Degris
• Daan Wierstra
• Martin A. Riedmiller

In this paper we consider deterministic policy gradient algorithms for reinforcement learning with continuous actions. The deterministic policy gradient has a particularly appealing form: it is the expected gradient of the action-value function. This simple form means that the deterministic policy gradient can be estimated much more efficiently than the usual stochastic policy gradient. To ensure adequate exploration, we introduce an off-policy actor-critic algorithm that learns a deterministic target policy from an exploratory behaviour policy. Deterministic policy gradient algorithms outperformed their stochastic counterparts in several benchmark problems, particularly in high-dimensional action spaces.

TCS Journal 2013 Journal Article

Tighter PAC-Bayes bounds through distribution-dependent priors

• Guy Lever
• François Laviolette
• John Shawe-Taylor

We further develop the idea that the PAC-Bayes prior can be informed by the data-generating distribution. We use this framework to prove sharp risk bounds for stochastic exponential weights algorithms, and develop insights into controlling function class complexity in this method. In particular we consider controlling capacity with respect to the unknown geometry defined by the data-generating distribution. We also use the method to obtain new bounds for RKHS regularization schemes such as SVMs.

ICML Conference 2012 Conference Paper

Conditional mean embeddings as regressors

• Steffen Grünewälder
• Guy Lever
• Arthur Gretton
• Luca Baldassarre
• Sam Patterson
• Massimiliano Pontil

ICML Conference 2012 Conference Paper

Modelling transition dynamics in MDPs with RKHS embeddings

• Steffen Grünewälder
• Guy Lever
• Luca Baldassarre
• Massimiliano Pontil
• Arthur Gretton

NeurIPS Conference 2008 Conference Paper

Online Prediction on Large Diameter Graphs

• Mark Herbster
• Guy Lever
• Massimiliano Pontil

Current on-line learning algorithms for predicting the labelling of a graph have an important limitation in the case of large diameter graphs; the number of mistakes made by such algorithms may be proportional to the square root of the number of vertices, even when tackling simple problems. We overcome this problem with an efficient algorithm which achieves a logarithmic mistake bound. Furthermore, current algorithms are optimised for data which exhibits cluster-structure; we give an additional algorithm which performs well locally in the presence of cluster structure and on large diameter graphs.