Anders Jonsson 0001

ECAI Conference 2025 Conference Paper

Concurrent Multiagent Reinforcement Learning with Reward Machines

• Alessandro Trapasso
• Anders Jonsson 0001

Coordinating and synchronizing multiple agents in reinforcement learning (RL) presents significant challenges, particularly when concurrent actions and shared objectives are required. We propose a novel framework that integrates Reward Machines (RMs) with Partial-Order Planning (POP) to enhance coordination in multiagent reinforcement learning (MARL). By transforming high-level POP strategies into individual RMs for each agent, our approach explicitly captures action dependencies and concurrency requirements, enabling agents to learn and execute coordinated plans effectively in complex environments. We validate our approach in a grid-based multiagent domain in which agents have to synchronize actions such as jointly accessing limited pathways or collaboratively manipulating objects. The explicit representation of action dependencies and synchronization points in RMs provides a scalable and flexible mechanism to model concurrent actions, enabling agents to focus on relevant tasks and reducing exploration.

ICLR Conference 2025 Conference Paper

Offline RL in Regular Decision Processes: Sample Efficiency via Language Metrics

• Ahana Deb
• Roberto Cipollone 0002
• Anders Jonsson 0001
• Alessandro Ronca
• Mohammad Sadegh Talebi

This work studies offline Reinforcement Learning (RL) in a class of non-Markovian environments called Regular Decision Processes (RDPs). In RDPs, the unknown dependency of future observations and rewards from the past interactions can be captured by some hidden finite-state automaton. For this reason, many RDP algorithms first reconstruct this unknown dependency using automata learning techniques. In this paper, we consider episodic RDPs and show that it is possible to overcome the limitations of existing offline RL algorithms for RDPs via the introduction of two original techniques: a novel metric grounded in formal language theory and an approach based on Count-Min-Sketch (CMS). Owing to the novel language metric, our algorithm is proven to be more sample efficient than existing results, and in some problem instances admitting low complexity languages, the gain is showcased to be exponential in the episode length. The CMS-based approach removes the need for naïve counting and alleviates the memory requirements for long planning horizons. We derive Probably Approximately Correct (PAC) sample complexity bounds associated to each of these techniques, and validate the approach experimentally.

ECAI Conference 2024 Conference Paper

Hierarchical Average-Reward Linearly-Solvable Markov Decision Processes

• Guillermo Infante
• Anders Jonsson 0001
• Vicenç Gómez

We introduce a novel approach to hierarchical reinforcement learning for Linearly-solvable Markov Decision Processes (LMDPs) in the infinite-horizon average-reward setting. Unlike previous work, our approach allows learning low-level and high-level tasks simultaneously, without imposing limiting restrictions on the low-level tasks. Our method relies on partitions of the state space that create smaller subtasks that are easier to solve, and the equivalence between such partitions to learn more efficiently. We then exploit the compositionality of low-level tasks to exactly represent the value function of the high-level task. Experiments show that our approach can outperform flat average-reward reinforcement learning by one or several orders of magnitude.

ICAPS Conference 2024 Conference Paper

Planning with a Learned Policy Basis to Optimally Solve Complex Tasks

• David Kuric
• Guillermo Infante
• Vicenç Gómez
• Anders Jonsson 0001
• Herke van Hoof

Conventional reinforcement learning (RL) methods can successfully solve a wide range of sequential decision problems. However, learning policies that can generalize predictably across multiple tasks in a setting with non-Markovian reward specifications is a challenging problem. We propose to use successor features to learn a set of local policies that each solves a well-defined subproblem. In a task described by a finite state automaton (FSA) that involves the same set of subproblems, the combination of these local policies can then be used to generate an optimal solution without additional learning. In contrast to other methods that combine local policies via planning, our method asymptotically attains global optimality, even in stochastic environments.

ICML Conference 2023 Conference Paper

Hierarchies of Reward Machines

• Daniel Furelos-Blanco
• Mark Law
• Anders Jonsson 0001
• Krysia Broda
• Alessandra Russo

Reward machines (RMs) are a recent formalism for representing the reward function of a reinforcement learning task through a finite-state machine whose edges encode subgoals of the task using high-level events. The structure of RMs enables the decomposition of a task into simpler and independently solvable subtasks that help tackle long-horizon and/or sparse reward tasks. We propose a formalism for further abstracting the subtask structure by endowing an RM with the ability to call other RMs, thus composing a hierarchy of RMs (HRM). We exploit HRMs by treating each call to an RM as an independently solvable subtask using the options framework, and describe a curriculum-based method to learn HRMs from traces observed by the agent. Our experiments reveal that exploiting a handcrafted HRM leads to faster convergence than with a flat HRM, and that learning an HRM is feasible in cases where its equivalent flat representation is not.

SoCS Conference 2022 Conference Paper

Scaling-Up Generalized Planning as Heuristic Search with Landmarks

• Javier Segovia-Aguas
• Sergio Jiménez Celorrio
• Laura Sebastiá
• Anders Jonsson 0001

Landmarks are one of the most effective search heuristics for classical planning, but largely ignored in generalized planning. Generalized planning (GP) is usually addressed as a combinatorial search in a given space of algorithmic solutions, where candidate solutions are evaluated w. r. t. the instances they solve. This type of solution evaluation ignores any sub-goal information that is not explicit in the representation of the planning instances, causing plateaus in the space of candidate generalized plans. Furthermore, node expansion in GP is a run-time bottleneck since it requires evaluating every child node over the entire batch of classical planning instances in a GP problem. In this paper we define a landmark counting heuristic for GP (that considers sub-goal information that is not explicitly represented in the planning instances), and a novel heuristic search algorithm for GP (that we call PGP) and that progressively processes subsets of the planning instances of a GP problem. Our two orthogonal contributions are analyzed in an ablation study, showing that both improve the state-of-the-art in GP as heuristic search, and that both benefit from each other when used in combination.

ICML Conference 2021 Conference Paper

Fast active learning for pure exploration in reinforcement learning

• Pierre Ménard
• Omar Darwiche Domingues
• Anders Jonsson 0001
• Emilie Kaufmann
• Edouard Leurent
• Michal Valko

Realistic environments often provide agents with very limited feedback. When the environment is initially unknown, the feedback, in the beginning, can be completely absent, and the agents may first choose to devote all their effort on \emph{exploring efficiently. } The exploration remains a challenge while it has been addressed with many hand-tuned heuristics with different levels of generality on one side, and a few theoretically-backed exploration strategies on the other. Many of them are incarnated by \emph{intrinsic motivation} and in particular \emph{explorations bonuses}. A common choice is to use $1/\sqrt{n}$ bonus, where $n$ is a number of times this particular state-action pair was visited. We show that, surprisingly, for a pure-exploration objective of \emph{reward-free exploration}, bonuses that scale with $1/n$ bring faster learning rates, improving the known upper bounds with respect to the dependence on the horizon $H$. Furthermore, we show that with an improved analysis of the stopping time, we can improve by a factor $H$ the sample complexity in the \emph{best-policy identification} setting, which is another pure-exploration objective, where the environment provides rewards but the agent is not penalized for its behavior during the exploration phase.

ICAPS Conference 2021 Conference Paper

Generalized Planning as Heuristic Search

• Javier Segovia-Aguas
• Sergio Jiménez Celorrio
• Anders Jonsson 0001

Although heuristic search is one of the most successful approaches to classical planning, this planning paradigm does not apply straightforwardly to Generalized Planning (GP). Planning as heuristic search traditionally addresses the computation of sequential plans by searching in a grounded state-space. On the other hand, GP aims at computing algorithm-like plans that can branch and loop, and that generalize to a (possibly infinite) set of planning instances. This paper adapts the {\em planning as heuristic search} paradigm to the particularities of GP and presents the first native heuristic search approach to GP. First, the paper defines a novel GP solution space that is independent of the number of planning instances in a GP problem, and the size of these instances. Second, the paper defines several evaluation and heuristic functions, that do not require grounding, for guiding a combinatorial search in the GP solution space, making it possible to handle state variables with large numerical domains (e. g. integers). Lastly, the paper defines an algorithm for GP called Best-First Generalized Planning (BFGP), that implements a best-first search in the solution space guided by our evaluation/heuristic functions.

ICAPS Conference 2021 Conference Paper

Hierarchical Width-Based Planning and Learning

• Miquel Junyent
• Vicenç Gómez
• Anders Jonsson 0001

Width-based search methods have demonstrated state-of-the-art performance in a wide range of testbeds, from classical planning problems to image-based simulators such as Atari games. These methods scale independently of the size of the state-space, but exponentially in the problem width. In practice, running the algorithm with a width larger than 1 is computationally intractable, prohibiting IW from solving higher width problems. In this paper, we present a hierarchical algorithm that plans at two levels of abstraction. A high-level planner uses abstract features that are incrementally discovered from low-level pruning decisions. We illustrate this algorithm in classical planning PDDL domains as well as in pixel-based simulator domains. In classical planning, we show how IW(1) at two levels of abstraction can solve problems of width 2. For pixel-based domains, we show how in combination with a learned policy and a learned value function, the proposed hierarchical IW can outperform current flat IW-based planners in Atari games with sparse rewards.

ICAPS Conference 2019 Conference Paper

Deep Policies for Width-Based Planning in Pixel Domains

• Miquel Junyent
• Anders Jonsson 0001
• Vicenç Gómez

Width-based planning has demonstrated great success in recent years due to its ability to scale independently of the size of the state space. For example, Bandres et al. (2018) introduced a rollout version of the Iterated Width algorithm whose performance compares well with humans and learning methods in the pixel setting of the Atari games suite. In this setting, planning is done on-line using the “screen” states and selecting actions by looking ahead into the future. However, this algorithm is purely exploratory and does not leverage past reward information. Furthermore, it requires the state to be factored into features that need to be pre-defined for the particular task, e. g. , the B-PROST pixel features. In this work, we extend width-based planning by incorporating an explicit policy in the action selection mechanism. Our method, called π-IW, interleaves width-based planning and policy learning using the state-actions visited by the planner. The policy estimate takes the form of a neural network and is in turn used to guide the planning step, thus reinforcing promising paths. Surprisingly, we observe that the representation learned by the neural network can be used as a feature space for the width-based planner without degrading its performance, thus removing the requirement of pre-defined features for the planner. We compare π-IW with previous widthbased methods and with AlphaZero, a method that also interleaves planning and learning, in simple environments, and show that π-IW has superior performance. We also show that π-IW algorithm outperforms previous width-based methods in the pixel setting of Atari games suite.

ICAPS Conference 2017 Conference Paper

Unsupervised Classification of Planning Instances

• Javier Segovia-Aguas
• Sergio Jiménez Celorrio
• Anders Jonsson 0001

In this paper we introduce a novel approach for unsupervised classification of planning instances based on the recent formalism of planning programs. Our approach is inspired by structured prediction in machine learning, which aims at predicting structured information about a given input rather than a scalar value. In our case, each input is an unlabelled classical planning instance, and the associated structured information is the planning program that solves the instance. We describe a method that takes as input a set of planning instances and outputs a set of planning programs, classifying each instance according to the program that solves it. Our results show that automated planning can be successfully used to solve structured unsupervised classification tasks, and invites further exploration of the connection between automated planning and structured prediction.

ECAI Conference 2016 Conference Paper

Constructing Hierarchical Task Models Using Invariance Analysis

• Damir Lotinac
• Anders Jonsson 0001

Hierarchical Task Networks (HTNs) are a common model for encoding knowledge about planning domains in the form of task decompositions. We present a novel algorithm that uses invariant analysis to construct an HTN from the PDDL description of a planning domain and a single representative instance. The algorithm defines two types of composite tasks that interact to achieve the goal of a planning instance. One type of task achieves fluents by traversing invariants in which only one fluent can be true at a time. The other type of task applies a single action, which first involves ensuring that the precondition of the action holds. The resulting HTN can be applied to any instance of the planning domain, and is provably sound. We show that the performance of our algorithm is comparable to algorithms that learn HTNs from examples and use added knowledge.

ICAPS Conference 2016 Conference Paper

Generalized Planning with Procedural Domain Control Knowledge

• Javier Segovia-Aguas
• Sergio Jiménez Celorrio
• Anders Jonsson 0001

Generalized planning is the task of generating a single solution that is valid for a set of planning problems. In this paper we show how to represent and compute generalized plans using procedural Domain Control Knowledge (DCK). We define a divide and conquer approach that first generates the procedural DCK solving a set of planning problems representative of certain subtasks and then compile it as callable procedures of the overall generalized planning problem. Our procedure calling mechanism allows nested and recursive procedure calls and is implemented in PDDL so that classical planners can compute and exploit procedural DCK. Experiments show that an off-the-shelf classical planner, using procedural DCK as callable procedures, can compute generalized plans in a wide range of domains including non-trivial ones, such as sorting variable-size lists or DFS traversal of binary trees with variable size.

ICAPS Conference 2016 Conference Paper

Hierarchical Linearly-Solvable Markov Decision Problems

• Anders Jonsson 0001
• Vicenç Gómez

We present a hierarchical reinforcement learning framework that formulates each task in the hierarchy as a special type of Markov decision process for which the Bellman equation is linear and has analytical solution. Problems of this type, called linearly-solvable MDPs (LMDPs) have interesting properties that can be exploited in a hierarchical setting, such as efficient learning of the optimal value function or task compositionality. The proposed hierarchical approach can also be seen as a novel alternative to solving LMDPs with large state spaces. We derive a hierarchical version of the so-called Z-learning algorithm that learns different tasks simultaneously and show empirically that it significantly outperforms the state-of-the-art learning methods in two classical HRL domains: the taxi domain and an autonomous guided vehicle task.

SoCS Conference 2015 Conference Paper

Computing Plans with Control Flow and Procedures Using a Classical Planner

• Sergio Jiménez Celorrio
• Anders Jonsson 0001

We propose a compilation that enhances a given classical planning task to compute plans that contain control flow and procedure calls. Control flow instructions and procedures allow us to generate compact and general solutions able to solve planning tasks for which multiple unit tests are defined. The paper analyzes the relation between classical planning and structured programming with unit tests and shows how to exploit this relation in a classical planning compilation. In experiments, we evaluate the empirical performance of the compilation using an off-the-shelf classical planner and show that we can compress classical planning solutions and that these compressed solutions can solve planning tasks with multiple tests.

ICAPS Conference 2015 Conference Paper

Temporal Planning With Required Concurrency Using Classical Planning

• Sergio Jiménez Celorrio
• Anders Jonsson 0001
• Héctor Palacios

In this paper we describe two novel algorithms for temporal planning. The first algorithm, TP, is an adaptation of the TEMPO algorithm. It compiles each temporal action into two classical actions, corresponding to the start and end of the temporal action, but handles the temporal constraints on actions through a modification of the Fast Downward planning system. The second algorithm, TPSHE, is a pure compilation from temporal to classical planning for the case in which required concurrency only appears in the form of single hard envelopes. We describe novel classes of temporal planning instances for which TPSHE is provably sound and complete. Compiling a temporal instance into a classical one gives a lot of freedom in terms of the planner or heuristic used to solve the instance. In experiments TPSHE significantly outperforms all planners from the temporal track of the International Planning Competition.

ECAI Conference 2014 Conference Paper

A Single-Agent Approach to Multiagent Planning

• Matthew Crosby
• Anders Jonsson 0001
• Michael Rovatsos

In this paper we present a novel approach to multiagent planning in domains with concurrent actions and associated concurrent action constraints. In these domains, we associate the actions of individual agents with subsets of objects, which allows for a transformation of the problems into single-agent planning problems that are considerably easier to solve. The transformation forces agents to select joint actions associated with a single subset of objects at a time, and ensures that the concurrency constraints on this subset are satisfied. Joint actions are serialised such that each agent performs their part of the action separately. The number of actions in the resulting single-agent planning problem turns out to be manageable in many real-world domains, thus allowing the problem to be solved efficiently using a standard single-agent planner. We also describe a cost-optimal algorithm for compressing the resulting plan, i. e. merging individual actions in order to reduce the total number of joint actions. Results show that our approach can handle large problems that are impossible to solve for most multiagent planners.

ICAPS Conference 2013 Conference Paper

Safe, Strong, and Tractable Relevance Analysis for Planning

• Patrik Haslum
• Malte Helmert
• Anders Jonsson 0001

In large and complex planning problems, there will almost inevitably be aspects that are not relevant to a specific problem instance. Thus, identifying and removing irrelevant parts from an instance is one of the most important techniques for scaling up automated planning. We examine the path-based relevance analysis method, which is safe (preserves plan existence and cost) and powerful but has exponential time complexity, and show how to make it run in polynomial time with only a minimal loss of pruning power.

ICAPS Conference 2013 Conference Paper

When Acyclicity Is Not Enough: Limitations of the Causal Graph

• Anders Jonsson 0001
• Peter Jonsson
• Tomas Lööw

Causal graphs are widely used in planning to capture the internal structure of planning instances. In the past, causal graphs have been exploited to generate hierarchical plans, to compute heuristics, and to identify classes of planning instances that are easy to solve. It is generally believed that planning is easier when the causal graph is acyclic. In this paper we show that this is not true in the worst case, proving that the problem of plan existence is PSPACE-complete even when the causal graph is acyclic. Since the variables of the planning instances in our reduction are propositional, this result applies to STRIPS planning with negative pre-conditions. Having established that planning is hard for acyclic causal graphs, we study a subclass of planning instances with acyclic causal graphs whose variables have strongly connected domain transition graphs. For this class, we show that plan existence is easy, but that bounded plan existence is hard, implying that optimal planning is significantly harder than satisficing planning for this class.

ECAI Conference 2012 Conference Paper

From Macro Plans to Automata Plans

• Christer Bäckström
• Anders Jonsson 0001
• Peter Jonsson

Macros have a long-standing role in planning as a tool for representing repeating subsequences of operators. Macros are useful both for guiding search towards a solution and for representing plans compactly. In this paper we introduce automata plans which consist of hierarchies of finite state automata. Automata plans can be viewed as an extension of macros that enables parametrization and branching. We provide several examples of the utility of automata plans, and prove that automata plans are strictly more expressive than macro plans. We also prove that automata plans admit polynomialtime sequential access of the operators in the underlying "flat" plan, and identify a subset of automata plans that admit polynomial-time random access. Finally, we compare automata plans with other representations allowing polynomial-time sequential access.

ECAI Conference 2012 Conference Paper

Macros, Reactive Plans and Compact Representations

• Christer Bäckström
• Anders Jonsson 0001
• Peter Jonsson

The use and study of compact representations of objects is widespread in computer science. AI planning can be viewed as the problem of finding a path in a graph that is implicitly described by a compact representation in a planning language. However, compact representations of the path itself (the plan) have not received much attention in the literature. Although both macro plans and reactive plans can be considered as such compact representations, little emphasis has been placed on this aspect in earlier work. There are also compact plan representations that are defined by their access properties, for instance, that they have efficient random access or efficient sequential access. We formally compare two such concepts with macro plans and reactive plans, viewed as compact representations, and provide a complete map of the relationships between them.

ICAPS Conference 2011 Conference Paper

Scaling Up Multiagent Planning: A Best-Response Approach

• Anders Jonsson 0001
• Michael Rovatsos

Multiagent planning is computationally hard in the general case due to the exponential blowup in the action space induced by concurrent action of different agents. At the same time, many scenarios require the computation of plans that are strategically meaningful for self-interested agents, in order to ensure that there would be sufficient incentives for those agents to participate in a joint plan. In this paper, we present a multiagent planning and plan improvement method that is based on conducting iterative best-response planning using standard single-agent planning algorithms. In constrained types of planning scenarios that correspond to congestion games, this is guaranteed to converge to a plan that is a Nash equilibrium with regard to agents' preference profiles over the entire plan space. Our empirical evaluation beyond these restricted scenarios shows, however, that the algorithm has much broader applicability as a method for plan improvement in general multiagent planning problems. Extensive empirical experiments in various domains illustrate the scalability of our method in both cases.

ICAPS Conference 2009 Conference Paper

The Influence of k- Dependence on the Complexity of Planning

• Omer Giménez
• Anders Jonsson 0001

A planning problem is k-dependent if each action has at most k pre-conditions on variables unaffected by the action. This concept is well-founded since k is a constant for all but a few of the standard planning domains, and is known to have implications for tractability. In this paper, we present several new complexity results for P(k), the class of k-dependent planning problems with binary variables and polytree causal graphs. The problem of plan generation for P(k) is equivalent to determining how many times each variable can change. Using this fact, we present a polytime plan generation algorithm for P(2) and P(3). For constant k > 3, we introduce and use the notion of a cover to find conditions under which plan generation for P(k) is polynomial.

ICAPS Conference 2008 Conference Paper

In Search of the Tractability Boundary of Planning Problems

• Omer Giménez
• Anders Jonsson 0001

Recently, considerable focus has been given to the problem of determining the boundary between tractable and intractable planning problems. To this end, we present complexity results for two classes of planning problems from the literature. First, we show that approximating a solution to a planning problem in the class 3S to within polynomial factors is NP-hard. We also show that plan existence is NP-hard for planning problems with chain causal graphs and variables with domain size at most 7. In addition to the immediate implications, our results provide some insight into what makes some planning problems intractable.

ICAPS Conference 2007 Conference Paper

On the Hardness of Planning Problems with Simple Causal Graphs

• Omer Giménez
• Anders Jonsson 0001

We present three new complexity results for classes of planning problems with simple causal graphs. First, we describe a polynomial time algorithm that uses macros to generate plans for a class of planning problems with binary state variables and acyclic causal graphs. This implies that plan generation may not be intractable just because a planning problem has exponential length solution. We also prove that the problem of plan existence for planning problems with multi-valued variables and chain causal graphs is NP-hard. Finally, we show that plan existence for planning problems with binary state variables and polytree causal graphs is NP-complete.

ICML Conference 2005 Conference Paper

A causal approach to hierarchical decomposition of factored MDPs

• Anders Jonsson 0001
• Andrew G. Barto