Mehdi Dastani

Reward machines have recently been proposed as a means of encoding team tasks in cooperative multi-agent reinforcement learning. The resulting multi-agent reward machine is then decomposed into individual reward machines, one for each member of the team, allowing agents to learn in a decentralised manner while still achieving the team task. In this paper, we show how multi-agent reward machines for team tasks can be synthesised automatically from an abstraction of the environment in which the agents act and a high-level specification of the desired team behaviour expressed in a fragment of Alternating-time Temporal Logic. We present results from a number of benchmarks which suggest that our automated approach performs as well or better than reward machines in the literature.

Until recently the game industry heavily relied on manual playtesting to test the games it produces. Even if the benefits of introducing automated testing are acknowledged, it is rarely done in practice. Some of the main hurdles include the lack of automated testing tools that can target computer games as well as the complexity of automated game plays which are much more difficult to program than typical simple test sequences. This article presents an agent-based testing framework called aplib that comes with a Domain Specific Language (DSL) that allows complex playtests to be programmed more abstractly. A so-called goal structure is used to abstractly formulate a playtest scenario in terms of main goals and their decomposition into subgoals. Scenarios that are not too complicated can be formulated using static goal structures. More complex scenarios may need a test agent that can dynamically adapt its play according to the situation that evolves during the play. To handle such cases, aplib allows dynamic goals to be expressed as well. Invariants and pre-/post-conditions are used to assert the properties that a play is expected to satisfy. They include differential properties that allow constraints on the current state to be related to that of past states. Three case studies are included in the article. The first one aims to evaluate the performance of playtests programmed with aplib . The second shows that the approach can also be combined with other automated testing approaches, in this case reinforcement learning. The third shows the applicability of such playtests in a 3D setup and for non-functional testing.

In multi-agent deep reinforcement learning (MADRL), agents can communicate with one another to perform a task in a coordinated manner. When multiple tasks are involved, agents can also leverage knowledge from one task to improve learning in other tasks. In this paper, we propose Multi-task Communication Skills (MCS), a MADRL with communication method that learns and performs multiple tasks simultaneously, with agents interacting through learnable communication protocols. MCS employs a Transformer encoder to encode task-specific observations into a shared message space, capturing shared communication skills among agents. To enhance coordination among agents, we introduce a prediction network that correlates messages with the actions of sender agents in each task. We adapt three multi-agent benchmark environments to multi-task settings, where the number of agents as well as the observation and action spaces vary across tasks. Experimental results demonstrate that MCS achieves better performance than multi-task MADRL baselines without communication, as well as single-task MADRL baselines with and without communication.

In multi-agent deep reinforcement learning (MADRL), agents can learn to communicate to broaden their view and understanding of the environment and their teammates. Previous works on communication in MADRL mainly rely on centralized or independent value functions for learning communication, which cannot differentiate how communicating agents individually contribute to the overall learning process. Moreover, continuous environments that incorporate continuous state/action spaces have received limited attention in previous research. In this paper, we propose a novel architecture for communicating agents and apply centralized but factorized value functions to differentiate how each agent contributes to learning during communication, along with gradient backpropagation. Additionally, to address the complexity introduced by communication, we investigate the use of an attention mechanism that aggregates messages, enabling policies to maintain a fixed input length. We then present a new policy gradient method termed communication with factorized policy gradients (CFPG), featuring full backpropagation from factorized value functions to communicating agents’ architecture. We demonstrate that CFPG can enhance performance and accelerate learning in continuous predator–prey scenarios and multi-agent MuJoCo, when compared to other learning communication methods.

Training cooperative agents in sparse-reward scenarios poses significant challenges for multi-agent reinforcement learning (MARL). Without clear feedback on actions at each step in sparse-reward setting, previous methods struggle with precise credit assignment among agents and effective exploration. In this paper, we introduce a novel method to deal with both credit assignment and exploration problems in reward-sparse domains. Accordingly, we propose an algorithm that calculates the Influence Scope of Agents (ISA) on states by taking specific value of the dimensions/attributes of states that can be influenced by individual agents. The mutual dependence between agents' actions and state attributes are then used to calculate the credit assignment and to delimit the exploration space for each individual agent. We then evaluate ISA in a variety of sparse-reward multi-agent scenarios. The results show that our method significantly outperforms the state-of-art baselines.

Structural equation models (SEM) are a standard approach to representing causal dependencies between variables. In this paper we propose a new interpretation of existing formalisms in the field of Actual Causality in which SEM's are viewed as mechanisms transforming the dynamics of exogenous variables into the dynamics of endogenous variables. This allows us to combine counterfactual causal reasoning with existing temporal logic formalizms, and to introduce a temporal logic, CPLTL, for causal reasoning about such structures. Then, we demonstrate that the standard restriction to so-called recursive models (with no cycles in the dependency graphs) is not necessary in our approach. This fact provides us extra tools for reasoning about mutually dependent processes and feedback loops. Finally, we introduce the notions of model equivalence for temporal causal models and show that CPLTL has an efficient model-checking procedure.

Causality plays an important role in daily processes, human reasoning, and artificial intelligence. There has however not been much research on causality in multi-agent strategic settings. In this work, we introduce a systematic way to build a multi-agent system model, represented as a concurrent game structure, for a given structural causal model. In the obtained so-called causal concurrent game structure, transitions correspond to interventions on agent variables of the given causal model. The Halpern and Pearl framework of causality is used to determine the effects of a certain value for an agent variable on other variables. The causal concurrent game structure allows us to analyse and reason about causal effects of agents' strategic decisions. We formally investigate the relation between causal concurrent game structures and the original structural causal models.

Modern computer games have become very complex, so they can benefit from automated testing. However, their huge and fine grained interaction space makes them very challenging for automated testing algorithms. Having a model of a system would greatly improve the effectiveness of a testing algorithm. However, manually constructing a model is expensive and time‐consuming. This paper proposes an online agent‐based search approach to solve common testing tasks for computer games, in particular games that involve elements of world navigation and exploration. On the fly, the approach also constructs a model of the system, which is then exploited to solve the given testing task. The effectiveness of the approach is studied via a case study called Lab Recruits and its simulation of another game called Dungeons and Dragons Online. The study showed that the approach is superior in its ability to complete testing tasks and its completion time compared to evolutionary algorithm, Q‐learning and MCTS. This paper extends a previous work presented in ATEST by including evaluation on large game levels, evaluation of the achieved coverage and fault detection and the aforementioned comparison with other algorithms.

In decentralized multi-agent deep reinforcement learning (MADRL), communication can help agents to gain a better understanding of the environment to better coordinate their behaviors. Nevertheless, communication may involve uncertainty, which potentially introduces variance to the learning of decentralized agents. In this paper, we focus on a specific decentralized MADRL setting with communication and conduct a theoretical analysis to study the variance that is caused by communication in policy gradients. We propose modular techniques to reduce the variance in policy gradients during training. We adopt our modular techniques into two existing algorithms for decentralized MADRL with communication and evaluate them on multiple tasks in the StarCraft Multi-Agent Challenge and Traffic Junction domains. The results show that decentralized MADRL communication methods extended with our proposed techniques not only achieve high-performing agents but also reduce variance in policy gradients during training.

Improving sample efficiency of Reinforcement Learning (RL) in sparse-reward environments poses a significant challenge. In scenarios where the reward structure is complex, accurate action evaluation often relies heavily on precise information about past achieved subtasks and their order. Previous approaches have often failed or proved inefficient in constructing and leveraging such intricate reward structures. In this work, we propose an RL algorithm that can automatically structure the reward function for sample efficiency, given a set of labels that signify subtasks. Given such minimal knowledge about the task, we train a high-level policy that selects optimal subtasks in each state together with a low-level policy that efficiently learns to complete each sub-task. We evaluate our algorithm in a variety of sparse-reward environments. The experiment results show that our method significantly outperforms the state-of-art baselines as the difficulty of the task increases.