Mark Crowley

AAMAS Conference 2023 Conference Paper

Learning from Multiple Independent Advisors in Multi-agent Reinforcement Learning

• Sriram Ganapathi Subramanian
• Matthew E. Taylor
• Kate Larson
• Mark Crowley

Multi-agent reinforcement learning typically suffers from the problem of sample inefficiency, where learning suitable policies involves the use of many data samples. Learning from external demonstrators is a possible solution that mitigates this problem. However, most prior approaches in this area assume the presence of a single demonstrator. Leveraging multiple knowledge sources (i. e. , advisors) with expertise in distinct aspects of the environment could substantially speed up learning in complex environments. This paper considers the problem of simultaneously learning from multiple independent advisors in multi-agent reinforcement learning. The approach leverages a two-level Q-learning architecture, and extends this framework from single-agent to multi-agent settings. We provide principled algorithms that incorporate a set of advisors by both evaluating the advisors at each state and subsequently using the advisors to guide action selection. We also provide theoretical convergence and sample complexity guarantees. Experimentally, we validate our approach in three different test-beds and show that our algorithms give better performances than baselines, can effectively integrate the combined expertise of different advisors, and learn to ignore bad advice.

IJCAI Conference 2023 Conference Paper

Multi-Agent Advisor Q-Learning (Extended Abstract)

• Sriram Ganapathi Subramanian
• Matthew E. Taylor
• Kate Larson
• Mark Crowley

In the last decade, there have been significant advances in multi-agent reinforcement learning (MARL) but there are still numerous challenges, such as high sample complexity and slow convergence to stable policies, that need to be overcome before wide-spread deployment is possible. However, many real-world environments already, in practice, deploy sub-optimal or heuristic approaches for generating policies. An interesting question that arises is how to best use such approaches as advisors to help improve reinforcement learning in multi-agent domains. We provide a principled framework for incorporating action recommendations from online sub-optimal advisors in multi-agent settings. We describe the problem of ADvising Multiple Intelligent Reinforcement Agents (ADMIRAL) in nonrestrictive general-sum stochastic game environments and present two novel Q-learning-based algorithms: ADMIRAL - Decision Making (ADMIRAL-DM) and ADMIRAL - Advisor Evaluation (ADMIRAL-AE), which allow us to improve learning by appropriately incorporating advice from an advisor (ADMIRAL-DM), and evaluate the effectiveness of an advisor (ADMIRAL-AE). We analyze the algorithms theoretically and provide fixed point guarantees regarding their learning in general-sum stochastic games. Furthermore, extensive experiments illustrate that these algorithms: can be used in a variety of environments, have performances that compare favourably to other related baselines, can scale to large state-action spaces, and are robust to poor advice from advisors.

AAAI Conference 2022 Conference Paper

Decentralized Mean Field Games

• Sriram Ganapathi Subramanian
• Matthew E. Taylor
• Mark Crowley
• Pascal Poupart

Multiagent reinforcement learning algorithms have not been widely adopted in large scale environments with many agents as they often scale poorly with the number of agents. Using mean field theory to aggregate agents has been proposed as a solution to this problem. However, almost all previous methods in this area make a strong assumption of a centralized system where all the agents in the environment learn the same policy and are effectively indistinguishable from each other. In this paper, we relax this assumption about indistinguishable agents and propose a new mean field system known as Decentralized Mean Field Games, where each agent can be quite different from others. All agents learn independent policies in a decentralized fashion, based on their local observations. We define a theoretical solution concept for this system and provide a fixed point guarantee for a Q-learning based algorithm in this system. A practical consequence of our approach is that we can address a ‘chicken-and-egg’ problem in empirical mean field reinforcement learning algorithms. Further, we provide Q-learning and actor-critic algorithms that use the decentralized mean field learning approach and give stronger performances compared to common baselines in this area. In our setting, agents do not need to be clones of each other and learn in a fully decentralized fashion. Hence, for the first time, we show the application of mean field learning methods in fully competitive environments, large-scale continuous action space environments, and other environments with heterogeneous agents. Importantly, we also apply the mean field method in a ride-sharing problem using a real-world dataset. We propose a decentralized solution to this problem, which is more practical than existing centralized training methods.

JAIR Journal 2022 Journal Article

Multi-Agent Advisor Q-Learning

• Sriram Ganapathi Subramanian
• Matthew E. Taylor
• Kate Larson
• Mark Crowley

In the last decade, there have been significant advances in multi-agent reinforcement learning (MARL) but there are still numerous challenges, such as high sample complexity and slow convergence to stable policies, that need to be overcome before wide-spread deployment is possible. However, many real-world environments already, in practice, deploy sub-optimal or heuristic approaches for generating policies. An interesting question that arises is how to best use such approaches as advisors to help improve reinforcement learning in multi-agent domains. In this paper, we provide a principled framework for incorporating action recommendations from online suboptimal advisors in multi-agent settings. We describe the problem of ADvising Multiple Intelligent Reinforcement Agents (ADMIRAL) in nonrestrictive general-sum stochastic game environments and present two novel Q-learning based algorithms: ADMIRAL - Decision Making (ADMIRAL-DM) and ADMIRAL - Advisor Evaluation (ADMIRAL-AE), which allow us to improve learning by appropriately incorporating advice from an advisor (ADMIRAL-DM), and evaluate the effectiveness of an advisor (ADMIRAL-AE). We analyze the algorithms theoretically and provide fixed point guarantees regarding their learning in general-sum stochastic games. Furthermore, extensive experiments illustrate that these algorithms: can be used in a variety of environments, have performances that compare favourably to other related baselines, can scale to large state-action spaces, and are robust to poor advice from advisors.

AAMAS Conference 2021 Conference Paper

Partially Observable Mean Field Reinforcement Learning

• Sriram Ganapathi Subramanian
• Matthew E. Taylor
• Mark Crowley
• Pascal Poupart

Traditional multi-agent reinforcement learning algorithms are not scalable to environments with more than a few agents, since these algorithms are exponential in the number of agents. Recent research has introduced successful methods to scale multi-agent reinforcement learning algorithms to many agent scenarios using mean field theory. Previous work in this field assumes that an agent has access to exact cumulative metrics regarding the mean field behaviour of the system, which it can then use to take its actions. In this paper, we relax this assumption and maintain a distribution to model the uncertainty regarding the mean field of the system. We consider two different settings for this problem. In the first setting, only agents in a fixed neighbourhood are visible, while in the second setting, the visibility of agents is determined at random based on distances. For each of these settings, we introduce a 𝑄-learning based algorithm that can learn effectively. We prove that this 𝑄learning estimate stays very close to the Nash 𝑄-value (under a common set of assumptions) for the first setting. We also empirically show our algorithms outperform multiple baselines in three different games in the MAgents framework, which supports large environments with many agents learning simultaneously to achieve possibly distinct goals.

AAMAS Conference 2019 Conference Paper

Training Cooperative Agents for Multi-Agent Reinforcement Learning

• Sushrut Bhalla
• Sriram G. Subramanian
• Mark Crowley

Deep Learning and back-propagation has been successfully used to perform centralized training with communication protocols among multiple agents in a cooperative environment. In this paper we present techniques for centralized training of Multi-Agent (Deep) Reinforcement Learning (MARL) using the model-free Deep Q- Network as the baseline model and message sharing between agents. We present a novel, scalable, centralized MARL training technique, which separates the message learning module from the policy module. The separation of these modules helps in faster convergence in complex domains like autonomous driving simulators. A second contribution uses the centrally trained model to bootstrap training of distributed, independent, cooperative agent policies for execution and thus addresses the challenges of noise and communication bottlenecks in real-time communication channels. This paper theoretically and empirically compares our centralized training algorithms to current research in the field of MARL. We also present and release a new OpenAI-Gym environment which can be used for multi-agent research as it simulates multiple autonomous cars driving cooperatively on a highway.

RLDM Conference 2017 Conference Abstract

Learning Forest Wildfire Dynamics from Satellite Images Using Reinforcement Learning

• Sriram Ganapathi Subramanian
• Mark Crowley

Forest wildfires are a perennial problem in many parts of the world requiring high financial and social costs to measure, predict and control. One key challenge is modelling the dynamics of forest wildfire spread itself which usually relies on computationally expensive, hand crafted physics-based models. The question we ask is: Can we learn a dynamics model by treating wildfire as an agent spreading across a landscape in response to neighbourhood environmental and landscape parameters? The problem is modelled as a Markov Decision Process where fire is the agent at any cell in the landscape and the goal is to learn a policy for fire spreading into neighbouring cells. The set of suitable actions the fire can take from a location at any point of time includes spreading North, South, East, West or stay. Rewards are provided at the end of the epoch based on correctly classifying cells which are on fire or not. We apply two Reinforcement Learning algorithms to this problem: Value Iteration and Asynchronous Advantage Actor-Critic (A3C), which is a recent direct policy search approach that utilizes Deep Learning to perform simultaneous state- space approximation and policy representation. The data for the start state and rewards come solely from satellite images of a region in northern Alberta, Canada, which is prone to large wildfires. Two events are used, the Fort McMurray fire of 2016 which led to the unprecedented evacuation of almost 90, 000 people for several months and the Richardson fire of 2011 which was larger and more dramatic. Experiments are carried out training a wildfire spread policy for one region on multiple time frames as well as testing the ability to apply the learned policy to data from a second region. The results obtained indicate that it is useful to think of fire as a learning agent to understand its characteristics in a spatial environment.

JMLR Journal 2015 Journal Article

PAC Optimal MDP Planning with Application to Invasive Species Management

• Majid Alkaee Taleghan
• Thomas G. Dietterich
• Mark Crowley
• Kim Hall
• H. Jo Albers

In a simulator-defined MDP, the Markovian dynamics and rewards are provided in the form of a simulator from which samples can be drawn. This paper studies MDP planning algorithms that attempt to minimize the number of simulator calls before terminating and outputting a policy that is approximately optimal with high probability. The paper introduces two heuristics for efficient exploration and an improved confidence interval that enables earlier termination with probabilistic guarantees. We prove that the heuristics and the confidence interval are sound and produce with high probability an approximately optimal policy in polynomial time. Experiments on two benchmark problems and two instances of an invasive species management problem show that the improved confidence intervals and the new search heuristics yield reductions of between 8% and 47% in the number of simulator calls required to reach near- optimal policies. [abs] [ pdf ][ bib ] &copy JMLR 2015. ( edit, beta )

IJCAI Conference 2013 Conference Paper

Cyclic Causal Models with Discrete Variables: Markov Chain Equilibrium Semantics and Sample Ordering

• David Poole
• Mark Crowley

We analyze the foundations of cyclic causal models for discrete variables, and compare structural equation models (SEMs) to an alternative semantics as the equilibrium (stationary) distribution of a Markov chain. We show under general conditions, discrete cyclic SEMs cannot have independent noise; even in the simplest case, cyclic structural equation models imply constraints on the noise. We give a formalization of an alternative Markov chain equilibrium semantics which requires not only the causal graph, but also a sample order. We show how the resulting equilibrium is a function of the sample ordering, both theoretically and empirically.

AAAI Conference 2013 Conference Paper

PAC Optimal Planning for Invasive Species Management: Improved Exploration for Reinforcement Learning from Simulator-Defined MDPs

• Thomas Dietterich
• Majid Alkaee Taleghan
• Mark Crowley

Often the most practical way to define a Markov Decision Process (MDP) is as a simulator that, given a state and an action, produces a resulting state and immediate reward sampled from the corresponding distributions. Simulators in natural resource management can be very expensive to execute, so that the time required to solve such MDPs is dominated by the number of calls to the simulator. This paper presents an algorithm, DDV, that combines improved confidence intervals on the Q values (as in interval estimation) with a novel upper bound on the discounted state occupancy probabilities to intelligently choose state-action pairs to explore. We prove that this algorithm terminates with a policy whose value is within ε of the optimal policy (with probability 1 − δ) after making only polynomially-many calls to the simulator. Experiments on one benchmark MDP and on an MDP for invasive species management show very large reductions in the number of simulator calls required.

EWRL Workshop 2013 Workshop Paper

Solving Simulator-Defined MDPs for Natural Resource Management

• Thomas Dietterich
• Majid Alkaee Taleghan
• Mark Crowley
• Sean McGregor

RLDM Conference 2013 Conference Abstract

Using Equilibrium Policy Gradients for Spatiotemporal Planning

• Mark Crowley

Spatiotemporal planning problems require an agent to make choices at multiple locations across space where the dynamics and the utility model being optimized can contain spatial structure. Planning problems in ecology and sustainable resource management provide many challenging problems with with this structure. In Forest Ecosystem Management, the problem is to choose actions for thousands of loca- tions in a forest each year. Actions can include harvesting trees, treatment against fire or pests, or doing nothing. Utility models can include value from sale of resources, costs for actions and constraints on spatial arrangements of actions. The dynamics are generally complex systems built for manual analysis purposes by domain experts so are best treated as a black box. Reinforcement learning is well suited to this problem except that the huge state-action space makes state based methods unusable. We model spatiotemporal planning as a factored Markov decision process where the states, actions and even the policy are factored across space. We present background and motivation for this problem and ongoing research into extending the Equilibrium Policy Gradient (EPG) algorithm to problems with complex spatial dynamics. EPG is a direct policy search method which uses a two part policy: (1) a local, parametrized patch policy defining the distribution over actions at each location given the features and actions at nearby locations; (2) a landscape policy which is defined as the stationary distribution of a Markov chain using (1) to define the transitions. Simulated trajectories of states and actions are sampled from the landscape policy via a form of Gibbs sampling where each cell action is sampled conditioned on fixed actions for all other cells. Ongoing research looks at extending EPG to domains with more spatial dynamics using an improved algorithm and richer feature descriptions of the state.

AAAI Conference 2011 Conference Paper

Policy Gradient Planning for Environmental Decision Making with Existing Simulators

• Mark Crowley
• David Poole