United Kingdom

Causal structure discovery from observational data is fundamental to the causal understanding of autonomous systems such as medical decision support systems, advertising campaigns and self-driving cars. This is essential to solve well-known causal decision making and prediction problems associated with those real-world applications. Recently, recursive causal discovery algorithms have gained particular attention among the research community due to their ability to provide good results by using Conditional Independent (CI) tests in smaller sub-problems. However, each of such algorithms needs a refinement function to remove undesired causal relations of the discovered graphs. Notably, with the increase of the problem size, the computation cost (i.e., the number of CI-tests) of the refinement function makes an algorithm expensive to deploy in practice. This paper proposes a generic causal structure refinement strategy that can locate the undesired relations with a small number of CI-tests, thus speeding up the algorithm for large and complex problems. We theoretically prove the correctness of our algorithm. We then empirically evaluate its performance against the state-of-the-art algorithms in terms of solution quality and completion time in synthetic and real datasets.

AAMAS 2021

Accelerating Recursive Partition-Based Causal Structure Learning

AAMAS is the largest and most influential conference in the area of agents and multiagent systems, bringing together researchers and practitioners in all areas of agent technology and providing and internationally renowned high-profile forum for publishing and finding out about the latest developments in the field. AAMAS is the flagship conference of the non-profit International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).  

![](https://assets.underline.io/uploads/markdown_image/1/image/ce4604bd54468a006164d16e080204fb.jpg)

Please click on the button below to register for this event.

If you are registered and see this page please check the account email you are logged in with. It must be the same as for the registration.

If you still have trouble accessing the contact please contact support at aamas2021@underline.io 

technical paper

The introduction of driver-less technologies can improve on-demand transport (ODT) systems and help make passenger transportation and logistics more efficient. Here, we aim to provide a generic model of the online ODT with autonomous vehicles problem and a multi-agent model specific to resource allocation and scheduling in vehicle fleets. Our model considers autonomous vehicles that communicate via peer-to-peer radio channels to meet passenger requirements and satisfy trip requests in an online ODT system. We experiment this model with several allocation mechanisms (mathematical programming, greedy heuristic, distributed constraint optimization, and auctions) and compare their performance on synthetic scenarios on a real-world city road network.

A Generic Multi-Agent Model for Resource Allocation Strategies in Online On-Demand Transport with Autonomous Vehicles

In this work, we investigate the impact of two approaches to agent desynchronization on task allocation in decentralized swarms: variation in response threshold and variation in response duration. We focus on swarms consisting of simple threshold-based stimulus response agents and examine how they respond to dynamically changing task demands in a logistics re-supply problem.

Comparison of Desynchronization Methods for a Decentralized Swarm on a Logistical Resupply Problem

Multi-Agent Path Finding (MAPF) is the challenging problem of computing collision-free paths for a cooperative team of moving agents. Algorithms for solving MAPF can be categorized on a spectrum. At one end are (bounded-sub)optimal algorithms that can find high-quality solutions for small problems. At the other end are unbounded-suboptimal algorithms (including prioritized and rule-based algorithms) that can solve very large practical problems but usually find low-quality solutions. In this paper, we consider a third approach that combines both advantages: anytime algorithms that quickly find an initial solution, including for large problems, and that subsequently improve the solution to near-optimal as time progresses. To improve the solution, we replan subsets of agents using Large Neighborhood Search, a popular meta-heuristic often applied in combinatorial optimization. Empirically, we compare our algorithm MAPF-LNS to the state-of-the-art anytime MAPF algorithm anytime BCBS and report significant gains in scalability, runtime to the first solution, and speed of improving solutions.

Anytime Multi-Agent Path Finding via Large Neighborhood Search

Narrative planning algorithms coordinate the virtual agents of interactive environments. Sabre is a single, centralized, omniscient decision maker that solves a multi-agent problem. It has a system-level author goal it must achieve, but every action taken by an agent must make sense according to that agent's individual intentions and limited, possibly wrong beliefs. We describe our motivation for solving such problems and the difficulties of comparing our planner to existing systems.

The Sabre Narrative Planner: Multi-Agent Coordination with Intentions and Beliefs

Watermarking has become a popular and attractive technique to protect the Intellectual Property (IP) of Deep Learning (DL) models. However, very few studies explore the possibility of watermarking Deep Reinforcement Learning (DRL) models. Common approaches in the DL context embed backdoors into the protected model and use special samples to verify the model ownership. These solutions are easy to be detected, and can potentially affect the performance and behaviors of the target model. Such limitations make existing solutions less applicable to safety- and security-critical tasks and scenarios, where DRL has been widely used.

Temporal Watermarks for Deep Reinforcement Learning Models

In this paper, we study the problem of deceptive reinforcement learning to preserve the privacy of a reward function. Reinforcement learning is the problem of finding a behaviour policy based on rewards received from exploratory behaviour. A key ingredient in reinforcement learning is a 
 which determines how much reward (negative or positive) is given and when. However, in some situations, we may want to keep a reward function private; that is, to make it difficult for an observer to determine the reward function used. We define the problem of privacy-preserving reinforcement learning, and present two models for solving it. These models are based on 
 -- a form of deception that 'hides the truth'. We evaluate our models both computationally and via human behavioural experiments. Results show that the resulting policies are indeed deceptive, and that participants can determine the true reward function less reliably than that of an honest agent.

Deceptive Reinforcement Learning for Privacy-Preserving Planning

Missed connections at transit airports are a source of both poor customer experience   and reduced airline operational efficiency. Airlines typically handle missed connections by rebooking customers. Recently, airlines have started holding departing flights for some time in a rule-based manner to avoid missed connections. However, rule-based heuristics typically use information local to a flight and do not learn in a globally informed way across the entire network. We complement existing approaches by learning a policy for holding a flight to avoid misconnections, using reinforcement learning (RL). The state presented to the RL agent uses forecasted flight-specific context; and measured network-wide context. The reward uses components that trade off the decrease in on-time performance due to the hold decisions, for a decrease in missed connections. We attribute the global rewards to individual local hold actions through a novel delay tree that approximates the network interactions. Multiple flights are handled through the same instance of the agent handling them in sequence with varying state information. We evaluate our approach for two different airlines with training and testing over a microsimulator that uses real-world data for calibration. Across different algorithms (DQN, AC, A2C, DDPG), we find that the best performing RL-based agent is able to reduce significantly more (up to 50%) missed connections for a minimal decrease (~5%) in on-time performance; when compared with a current rule-based heuristic. Further, the approach is tunable and able to transfer learn across different airlines.

To hold or not to hold? - Reducing Passenger Missed Connections in Airlines using Reinforcement Learning

This paper presents an intelligent and adaptive agent that employs deception to recognize a cyber adversary's intent on a honeypot host. Unlike previous approaches to cyber deception, which mainly focus on delaying or confusing the attackers, we focus on engaging with them to learn their intent. We model cyber deception as a sequential decision-making problem in a two-agent context. We introduce factored finitely-nested interactive POMDPs (I-POMDP X ) and use this framework to model the problem with multiple attacker types. Our approach models cyber attacks on a single honeypot host across multiple phases from the attacker's initial entry to reaching its adversarial objective. The defending I-POMDP X -based agent uses decoys to engage with the attacker at multiple phases to form increasingly accurate predictions of the attacker’s behavior and intent. The use of I-POMDPs also enables us to model the adversary's mental state and investigate how deception affects their beliefs. Our experiments in both simulation and with the agent deployed on a host system show that the I-POMDP X -based agent performs significantly better at intent recognition than commonly used deception strategies on honeypots. This emerging application of autonomous agents offers a new approach that contrasts with the traditional action-reaction dynamic that has defined interactions between cyber attackers and defenders for years.

Cyber Attack Intent Recognition and Active Deception using Factored Interactive POMDPs

Evolutionary Game Theory is an application of game theory to evolving populations of organisms. Of recent interest are EGT models situated on structured populations or spatial evolutionary games. Due to the complexity added by introducing a population structure, model analysis is usually performed through agent-based Monte-Carlo simulations. However, it can be difficult to obtain desired quantities of interest from these simulations due to stochastic effects. We define a framework for modeling spatial evolutionary games using Dynamic Bayesian Networks that capture the underlying stochastic process. The resulting Dynamic Bayesian Networks can be queried for quantities of interest by performing exact inference on the network. We then propose a method for producing approximations of the spatial evolutionary game through the truncation of the corresponding DBN, taking advantage of the high symmetry of the model. This method generalizes mean-field and pair approximations in the literature for spatial evolutionary games. Furthermore, we show empirical results demonstrating the capability of the method to obtain much better accuracy than pair approximation with respect to stochastic simulations.

Approximating Spatial Evolutionary Games using Bayesian Networks

In recent work, Gourvès, Lesca, and Wilczynski propose a variant of the classic housing markets model where the matching between agents and objects evolves through Pareto-improving swaps between pairs of adjacent agents in a social network. To explore the swap dynamics of their model, they pose several basic questions concerning the set of reachable matchings. In their work and other follow-up works, these questions have been studied for various classes of graphs: stars, paths, generalized stars (i.e., trees where at most one vertex has degree greater than two), trees, and cliques. For generalized stars and trees, it remains open whether a Pareto-efficient reachable matching can be found in polynomial time.

Accelerating Recursive Partition-Based Causal Structure Learning

Downloads

Next from AAMAS 2021

A Generic Multi-Agent Model for Resource Allocation Strategies in Online On-Demand Transport with Autonomous Vehicles

Similar lecture

Online Learning of Shaping Reward with Subgoal Knowledge

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Accelerating Recursive Partition-Based Causal Structure Learning

.css-70qvj9{display:-webkit-box;display:-webkit-flex;display:-ms-flexbox;display:flex;-webkit-align-items:center;-webkit-box-align:center;-ms-flex-align:center;align-items:center;}Downloads

Next from AAMAS 2021

A Generic Multi-Agent Model for Resource Allocation Strategies in Online On-Demand Transport with Autonomous Vehicles

Similar lecture

Online Learning of Shaping Reward with Subgoal Knowledge

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Downloads