Forward search algorithms, such as Monte Carlo Tree Search (MCTS), often struggle under the computational constraints of video games and other real-time environments. We address these issues by generating domain-specific macro-actions using evolutionary optimisation. Macro-actions—action abstractions that treat predefined sequences of discrete actions as a single action—can significantly improve the performance of forward search techniques by effectively increasing their look-ahead depth for the same computational cost. Evolved macro-actions can capture important structural aspects of a domain and substantially improve performance, even under tight computational constraints. We present an analysis of an evolved macro-action approach to decision-making with MCTS in real-time video games. We evaluate the effectiveness of this strategy across a large and diverse set of domains from the Arcade Learning Environment (ALE), and assess its generality, strengths, and limitations. Our results show that evolved macro-actions considerably improve performance across all tested domains and are particularly effective in games with a medium decision horizon and predictable dynamics.

This study aims to minimize the influence of fake news on social networks by deploying debunkers to propagate true news. This is framed as a reinforcement learning problem, where, at each stage, one user is selected to propagate true news. A challenging issue is episodic reward where the "net" effect of selecting individual debunkers cannot be discerned from the interleaving information propagation on social networks, and only the collective effect from mitigation efforts can be observed. Existing Self-Imitation Learning (SIL) methods have shown promise in learning from episodic rewards, but are ill-suited to the real-world application of fake news mitigation because of their poor sample efficiency. To learn a more effective debunker selection policy for fake news mitigation, this study proposes NAGASIL - Negative sampling and state Augmented Generative Adversarial Self-Imitation Learning, which consists of two improvements geared towards fake news mitigation: learning from negative samples, and an augmented state representation to capture the "real" environment state by integrating the current observed state with the previous state-action pairs from the same campaign. Experiments on two social networks show that NAGASIL yields superior performance to standard GASIL and state-of-the-art fake news mitigation models.

For an agent in a multi-agent environment, it is often beneficial to be able to predict what other agents will do next when deciding how to act. Previous work in multi-agent intention scheduling assumes a priori knowledge of the current goals of other agents. In this paper, we present a new approach to multi-agent intention scheduling in which an agent uses online goal recognition to identify the goals currently being pursued by other agents while acting in pursuit of its own goals. We show how online goal recognition can be incorporated into an MCTS-based intention scheduler, and evaluate our approach in a range of scenarios. The results demonstrate that our approach can rapidly recognise the goals of other agents even when they are pursuing multiple goals concurrently, and has similar performance to agents which know the goals of other agents a priori.

Recent work in multi-agent intention scheduling has shown that enabling agents to predict the actions of other agents when choosing their own actions can be beneficial. However existing approaches to 'intention-aware' scheduling assume that the programs of other agents are known, or are "similar" to that of the agent making the prediction. While this assumption is reasonable in some circumstances, it is less plausible when the agents are not co-designed. In this paper, we present a new approach to multi-agent intention scheduling in which agents predict the actions of other agents based on a high-level specification of the tasks performed by an agent in the form of a reward machine (RM) rather than on its (assumed) program. We show how a reward machine can be used to generate tree and rollout policies for an MCTS-based scheduler. We evaluate our approach in a range of multi-agent environments, and show that RM-based scheduling out-performs previous intention-aware scheduling approaches in settings where agents are not co-designed

We propose a new approach to intention progression in multi-agent settings where other agents are effectively black boxes. That is, while their goals are known, the precise programs used to achieve these goals are not known. In our approach, agents use an abstraction of their own program called a partially-ordered goal-plan tree (pGPT) to schedule their intentions and predict the actions of other agents. We show how a pGPT can be derived from the program of a BDI agent, and present an approach based on Monte Carlo Tree Search (MCTS) for scheduling an agent's intentions using pGPTs. We evaluate our pGPT-based approach in cooperative, selfish and adversarial multi-agent settings, and show that it out-performs MCTS-based scheduling where agents assume that other agents have the same program as themselves.

Sparse reward games, such as the infamous Montezuma’s Revenge, pose a significant challenge for Reinforcement Learning (RL) agents. Hierarchical RL, which promotes efficient exploration via subgoals, has shown promise in these games. However, existing agents rely either on human domain knowledge or slow autonomous methods to derive suitable subgoals. In this work, we describe a new, autonomous approach for deriving subgoals from raw pixels that is more efficient than competing methods. We propose a novel intrinsic reward scheme for exploiting the derived subgoals, applying it to three Atari games with sparse rewards. Our agent’s performance is comparable to that of state-of-the-art methods, demonstrating the usefulness of the subgoals found.

Aside from hand-coded bots, most of the videogame agents rely on experience in one way or another. Some agents improve over time by adjusting to real experience, while others make projections by leveraging simulated experience. In one sense, human play seems to resemble simulation, in that human players often try to visualize possible trajectories before deciding on a real course of action. However, most of the existing simulation-based agents require precise knowledge of the game's code, and their search depth is limited by the granular time scales encountered in videogames. Human players, on the other hand, appear to visualize plans in terms of abstract “skills,” such as running and jumping. These skills are learned from real experience, so,in this sense, human play resembles learning-based approaches. Motivated by these observations, we propose an approach that bridges the gap between skills, which are uncertain in outcome and duration, and traditional simulation-based planning, which is discrete. We apply this approach to maze-like navigation problems in Infinite Mario. After an initial skill acquisition phase, our agent is capable of navigating new levels without further training and also scales better with goal distance than a granular simulation method that exploits exact knowledge of the game's physics.

Applications of reinforcement learning to continuous control tasks often rely on a steady, informative reward signal. In videogames, however, tasks may be far easier to specify through a binary reward that indicates success or failure. In the absence of a steady, guiding reward, the agent may struggle to explore efficiently, especially if effective exploration requires strong coordination between actions. In this paper, we show empirically that this issue may be mitigated by exploring over an abstract action set, using hierarchically composed parameterized skills. We experiment in two tasks with sparse rewards in a continuous control environment based on the arcade game Asteroids. Compared to a flat learner that explores symmetrically over low-level actions, our agent explores a greater variety of useful actions, and its long-term performance on both tasks is superior.

In platform videogames, players are frequently tasked with solving medium-term navigation problems in order to gather items or powerups. Artificial agents must generally obtain some form of direct experience before they can solve such tasks. Experience is gained either through training runs, or by exploiting knowledge of the game's physics to generate detailed simulations. Human players, on the other hand, seem to look ahead in high-level, abstract steps. Motivated by human play, we introduce an approach that leverages not only abstract "skills", but also knowledge of what those skills can and cannot achieve. We apply this approach to Infinite Mario, where despite facing randomly generated, maze-like levels, our agent is capable of deriving complex plans in real-time, without relying on perfect knowledge of the game's physics.