Author name cluster

David Leslie

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

NeurIPS Conference 2021 Conference Paper

Decentralized Q-learning in Zero-sum Markov Games

Muhammed Sayin
Kaiqing Zhang
David Leslie
Tamer Basar
Asuman Ozdaglar

We study multi-agent reinforcement learning (MARL) in infinite-horizon discounted zero-sum Markov games. We focus on the practical but challenging setting of decentralized MARL, where agents make decisions without coordination by a centralized controller, but only based on their own payoffs and local actions executed. The agents need not observe the opponent's actions or payoffs, possibly being even oblivious to the presence of the opponent, nor be aware of the zero-sum structure of the underlying game, a setting also referred to as radically uncoupled in the literature of learning in games. In this paper, we develop a radically uncoupled Q-learning dynamics that is both rational and convergent: the learning dynamics converges to the best response to the opponent's strategy when the opponent follows an asymptotically stationary strategy; when both agents adopt the learning dynamics, they converge to the Nash equilibrium of the game. The key challenge in this decentralized setting is the non-stationarity of the environment from an agent's perspective, since both her own payoffs and the system evolution depend on the actions of other agents, and each agent adapts her policies simultaneously and independently. To address this issue, we develop a two-timescale learning dynamics where each agent updates her local Q-function and value function estimates concurrently, with the latter happening at a slower timescale.

PDF Details

NeurIPS Conference 2020 Conference Paper

BOSS: Bayesian Optimization over String Spaces

Henry Moss
David Leslie
Daniel Beck
Javier González
Paul Rayson

This article develops a Bayesian optimization (BO) method which acts directly over raw strings, proposing the first uses of string kernels and genetic algorithms within BO loops. Recent applications of BO over strings have been hindered by the need to map inputs into a smooth and unconstrained latent space. Learning this projection is computationally and data-intensive. Our approach instead builds a powerful Gaussian process surrogate model based on string kernels, naturally supporting variable length inputs, and performs efficient acquisition function maximization for spaces with syntactic constraints. Experiments demonstrate considerably improved optimization over existing approaches across a broad range of constraints, including the popular setting where syntax is governed by a context-free grammar.

PDF Details

NeurIPS Conference 2018 Conference Paper

Bandit Learning in Concave N-Person Games

Mario Bravo
David Leslie
Panayotis Mertikopoulos

This paper examines the long-run behavior of learning with bandit feedback in non-cooperative concave games. The bandit framework accounts for extremely low-information environments where the agents may not even know they are playing a game; as such, the agents’ most sensible choice in this setting would be to employ a no-regret learning algorithm. In general, this does not mean that the players' behavior stabilizes in the long run: no-regret learning may lead to cycles, even with perfect gradient information. However, if a standard monotonicity condition is satisfied, our analysis shows that no-regret learning based on mirror descent with bandit feedback converges to Nash equilibrium with probability 1. We also derive an upper bound for the convergence rate of the process that nearly matches the best attainable rate for single-agent bandit stochastic optimization.

PDF Details

RLDM Conference 2013 Conference Abstract

Changing decision criteria in sequential decision making

Gaurav Malhotra
David Leslie
Rafal Bogacz

When making a sequence of decisions in a fixed amount of time, people need to decide how much evidence to accumulate before making each decision. Do people accumulate evidence to a fixed decision- criterion before making a decision or can this criterion change with time? What is the optimal shape of the decision criterion and how does this compare to the decision bounds adopted by people? We developed a theoretical model using average reward dynamic programming, that optimises the reward per unit time and shows that the optimal shape of the decision threshold is constant when all decisions in a sequence have a known difficulty. But in case of mixed difficulties, the model shows that optimal thresholds should change with time. We then conducted an experiment with human participants that parallels this model and found that decisions made by participants qualitatively matched this optimal model showing that participants infer the amount of evidence in perceptual stimuli and adjust their decision criterion based on this inference.

PDF Details