Pasar al contenido principal

APRENDIZAJE Y PLANIFICACION CONTINUA

PID2019-108141GB-I00

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Convocatoria Proyectos de I+D+i (Generación de Conocimiento y Retos Investigación)
Año convocatoria 2019
Plan Estatal 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSITAT POMPEU FABRA CCT

Resultados relacionados

Resultados totales (Incluyendo duplicados): 25
Encontrada(s) 1 página(s)

Repositorio Digital de la UPF
Publicación Contribución de congreso (ConferenceOutput)

Hierarchical width-based planning and learning

  • Junyent Barbany, Miquel
  • Gómez, Vicenç
  • Jonsson, Anders, 1973-
Comunicació presentada a: ICAPS2021 celebrat del 2 a 13 d'agost de 2021 a Guangzhou, Xina., 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., V. Gómez has received funding from “La Caixa” Foundation (100010434), under the agreement LCF/PR/PR16/51110009 and is supported by the Ramon y Cajal program RYC-2015-18878 (AEI/MINEICO/FSE,UE). A. Jonsson is partially supported by Spanish grants PID2019-108141GB-I00 and PCIN-2017-082.
Repositorio Digital de la UPF
Publicación Contribución de congreso (ConferenceOutput)

Hierarchies of reward machines

  • Furelos Blanco, Daniel
  • Law, Mark
  • Jonsson, Anders
  • Broda, Krysia
  • Russo, Alessandra
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 longhorizon 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., Anders Jonsson is partially funded by TAILOR, AGAUR SGR and Spanish grant PID2019-108141GB-I00
Repositorio Digital de la UPF
Publicación Contribución de congreso (ConferenceOutput)

Generalized planning as heuristic search

  • Segovia-Aguas, Javier
  • Jiménez, Sergio
  • Jonsson, Anders, 1973-
Comunicació presentada a ICAPS2021, celebrat del 2 a 13 d'agost de 2021 de manera virtual., 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., Javier Segovia-Aguas is supported by TAILOR, a project funded by EU H2020 research and innovation programme no. 952215, an ERC Advanced Grant no. 885107, and grant TIN-2015-67959-P from MINECO, Spain. Sergio Jiménez is supported by the Ramon y Cajal program, RYC-2015-18009, the Spanish MINECO project TIN2017-88476-C2-1-R. Anders Jonsson is partially supported by Spanish grants PID2019-108141GB-I00 and PCIN-2017-082.
Repositorio Digital de la UPF
Publicación Artículo científico (JournalArticle)

Induction and exploitation of subgoal automata for reinforcement learning

  • Furelos Blanco, Daniel
  • Law, Mark
  • Jonsson, Anders, 1973-
  • Broda, Krysia
  • Russo, Alessandra
In this paper we present ISA, an approach for learning and exploiting subgoals in episodic reinforcement learning (RL) tasks. ISA interleaves reinforcement learning with the induction of a subgoal automaton, an automaton whose edges are labeled by the task’s subgoals expressed as propositional logic formulas over a set of high-level events. A subgoal automaton also consists of two special states: a state indicating the successful completion of the task, and a state indicating that the task has finished without succeeding. A state-of-the-art inductive logic programming system is used to learn a subgoal automaton that covers the traces of high-level events observed by the RL agent. When the currently exploited automaton does not correctly recognize a trace, the automaton learner induces a new automaton that covers that trace. The interleaving process guarantees the induction of automata with the minimum number of states, and applies a symmetry breaking mechanism to shrink the search space whilst remaining complete. We evaluate ISA in several gridworld and continuous state space problems using different RL algorithms that leverage the automaton structures. We provide an in-depth empirical analysis of the automaton learning performance in terms of the traces, the symmetry breaking and specific restrictions imposed on the final learnable automaton. For each class of RL problem, we show that the learned automata can be successfully exploited to learn policies that reach the goal, achieving an average reward comparable to the case where automata are not learned but handcrafted and given beforehand., The authors would like to thank the anonymous reviewers for their helpful comments and suggestions. Anders Jonsson is partially supported by the Spanish grants PCIN-2017-082 and PID2019-108141GB-I00.
Repositorio Digital de la UPF
Publicación Contribución de congreso (ConferenceOutput)

Provably efficient offline reinforcement learning in regular decision processes

  • Cipollone, Roberto
  • Ronca, Alessandro
  • Jonsson, Anders
  • Sadegh Talebi, Mohammad
This paper deals with offline (or batch) Reinforcement Learning (RL) in episodic Regular Decision Processes (RDPs). RDPs are the subclass of Non-Markov Decision Processes where the dependency on the history of past events can be captured by a finite-state automaton. We consider a setting where the automaton that underlies the RDP is unknown, and a learner strives to learn a near-optimal policy using pre-collected data, in the form of non-Markov sequences of observations, without further exploration. We present RegORL, an algorithm that suitably combines automata learning techniques and state-of-the-art algorithms for offline RL in MDPs. RegORL has a modular design allowing one to use any off-the-shelf offline RL algorithm in MDPs. We report a non-asymptotic high-probability sample complexity bound for RegORL to yield an ε-optimal policy, which makes appear a notion of concentrability relevant for RDPs. Furthermore, we present a sample complexity lower bound for offline RL in RDPs. To our best knowledge, this is the first work presenting a provably efficient algorithm for offline learning in RDPs., Roberto Cipollone is partially supported by the EU H2020 project AIPlan4EU (No. 101016442), the ERC-ADG White-Mech (No. 834228), the EU ICT-48 2020 project TAILOR (No. 952215), the PRIN project RIPER (No. 20203FFYLK), and the PNRR MUR project FAIR (No. PE0000013). Anders Jonsson is partially supported by the EU ICT-48 2020 project TAILOR (No. 952215), AGAUR SGR, and the Spanish grant PID2019-108141GB-I00. Alessandro Ronca is partially supported by the ERC project WhiteMech (No. 834228), and the ERC project ARiAT (No. 852769). Mohammad Sadegh Talebi is partially supported by the Independent Research Fund Denmark, grant number 1026-00397B.
Repositorio Digital de la UPF
Publicación Artículo científico (JournalArticle)

Hierarchical average-reward linearly-solvable Markov decision processes

  • Infante Molina, A. Guillermo
  • Jonsson, Anders, 1973-
  • Gómez Cerdà, Vicenç
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., Anders Jonsson is partially funded by TAILOR (EU H2020 #952215), AGAUR SGR and Spanish grant PID2019-108141GB-I00. This publication is part of the action CNS2022-136178 financed by MCIN/AEI/10.13039/501100011033 and by the European Union Next Generation EU/PRTR.
Repositorio Digital de la UPF
Publicación Artículo científico (JournalArticle)

Generalized planning as heuristic search: a new planning search-space that leverages pointers over objects

  • Segovia-Aguas, Javier
  • Jiménez, Sergio
  • Jonsson, Anders, 1973-
Planning as heuristic search is one of the most successful approaches to classical planning but unfortunately, it does not trivially extend to Generalized Planning (GP); GP aims to compute algorithmic solutions that are valid for a set of classical planning instances from a given domain, even if these instances differ in their number of objects, the initial and goal configuration of these objects and hence, in the number (and possible values) of the state variables. State-space search, as it is implemented by heuristic planners, becomes then impractical for GP. In this paper we adapt the planning as heuristic search paradigm to the generalization requirements of GP, and present the first native heuristic search approach to GP. First, the paper introduces a new pointer-based solution space for GP that is independent of the number of classical planning instances in a GP problem and the size of those instances (i.e. the number of objects, state variables and their domain sizes). Second, the paper defines an upgraded version of our GP algorithm, called Best-First Generalized Planning (BFGP), that implements a best-first search in our pointer-based solution space for GP. Lastly, the paper defines a set of evaluation and heuristic functions for BFGP that assess the structural complexity of the candidate GP solutions, as well as their fitness to a given input set of classical planning instances. The computation of these evaluation and heuristic functions does not require grounding states or actions in advance. Therefore our GP as heuristic search approach can handle large sets of state variables with large numerical domains, e.g. integers., This work has been co-funded by MCIN/AEI /10.13039/501100011033 under the Maria de Maeztu Units of Excellence Programme (CEX2021-001195-M), TAILOR (H2020 #952215) and AIPlan4EU (H2020 #101016442) projects. Javier Segovia-Aguas is also supported by AGAUR SGR and the Spanish grant PID2019-108141 GB-I00. Sergio Jiménez is supported by the Spanish MINECO project PID2021-127647NB-C22. Anders Jonsson is partially supported by Spanish grant PID2019-108141 GB-I00.
Repositorio Digital de la UPF
Publicación Contribución de congreso (ConferenceOutput)

Bisimulation metrics are optimal transport distances, and can be computed efficiently

  • Calo Oliveira, Sergio
  • Jonsson, Anders
  • Neu, Gergely
  • Schwartz, Ludovic
  • Segovia-Aguas, Javier
We propose a new framework for formulating optimal transport distances between Markov chains. Previously known formulations studied couplings between the entire joint distribution induced by the chains, and derived solutions via a reduction to dynamic programming (DP) in an appropriately defined Markov decision process. This formulation has, however, not led to particularly efficient algorithms so far, since computing the associated DP operators requires fully solving a static optimal transport problem, and these operators need to be applied numerous times during the overall optimization process. In this work, we develop an alternative perspective by considering couplings between a “flattened” version of the joint distributions that we call discounted occupancy couplings, and show that calculating optimal transport distances in the full space of joint distributions can be equivalently formulated as solving a linear program (LP) in this reduced space. This LP formulation allows us to port several algorithmic ideas from other areas of optimal transport theory. In particular, our formulation makes it possible to introduce an appropriate notion of entropy regularization into the optimization problem, which in turn enables us to directly calculate optimal transport distances via a Sinkhorn-like method we call Sinkhorn Value Iteration (SVI). We show both theoretically and empirically that this method converges quickly to an optimal coupling, essentially at the same computational cost of running vanilla Sinkhorn in each pair of states. Along the way, we point out that our optimal transport distance exactly matches the common notion of bisimulation metrics between Markov chains, and thus our results also apply to computing such metrics, and in fact our algorithm turns out to be significantly more efficient than the best known methods developed so far for this purpose., Neu was supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 950180). Anders Jonsson is partially supported by the EU ICT-48 2020 project TAILOR (No. 952215), AGAUR SGR, and the Spanish grant PID2019-108141GB-I00. Javier Segovia-Aguas is supported by MCIN/AEI /10.13039/501100011033 under the Maria de Maeztu Units of Excellence Programme (CEX2021-001195-M).
Repositorio Digital de la UPF
Publicación Contribución de congreso (ConferenceOutput)

Reinforcement learning for active modality selection during diagnosis

  • Bernardino Perez, Gabriel
  • Jonsson, Anders, 1973-
  • Loncaric, Filip
  • Martí Castellote, Pablo Miki
  • Sitges, Marta
  • Clarysse, Patrick
  • Duchateau, Nicolas
Comunicació presentada a 25th International Conference on Medical Image Computing and Computer Assisted Intervention (MICCAI 2022), celebrat del 18 al 22 de setembre de 2022 a Sentosa, Singapur., Diagnosis through imaging generally requires the combination of several modalities. Algorithms for data fusion allow merging information from different sources, mostly combining all images in a single step. In contrast, much less attention has been given to the incremental addition of new data descriptors, and the consideration of their costs (which can cover economic costs but also patient comfort and safety). In this work, we formalise clinical diagnosis of a patient as a sequential process of decisions, each of these decisions being whether to take an additional acquisition, or, if there is enough information, to end the examination and produce a diagnosis. We formulate the goodness of a diagnosis process as a combination of the classification accuracy minus the cost of the acquired modalities. To obtain a policy, we apply reinforcement learning, which recommends the next modality to incorporate based on data acquired at previous stages and aiming at maximising the accuracy/cost trade-off. This policy therefore performs medical diagnosis and patient-wise feature selection simultaneously. We demonstrate the relevance of this strategy on two binary classification datasets: a subset of a public heart disease database, including 531 instances with 11 scalar features, and a private echocardiographic dataset including signals from 5 standard image sequences used to assess cardiac function (2 speckle tracking, 2 flow Doppler and tissue Doppler), from 188 patients suffering hypertension, and 60 controls. For each individual, our algorithm allows acquiring only the modalities relevant for the diagnosis, avoiding low-information acquisitions, which both resulted in higher stability of the chosen modalities and better classification performance under a limited budget., The authors acknowledge the partial support from the French ANR (LABEX PRIMES of Univ. Lyon [ANR-11-LABX-0063] and the JCJC project “MIC-MAC” [ANR-19-CE45-0005]) and the Spanish AEI [PID2019-108141GB-I00].
Repositorio Digital de la UPF
Publicación Contribución de congreso (ConferenceOutput)

Synthesis of procedural models for deterministic transition systems

  • Segovia-Aguas, Javier
  • Ferrer Mestres, Jonathan
  • Sergio, Jiménez
Comunicació presentada a la 26th European Conference on Artificial Intelligence, celebrada del 30 de setembre al 4 d'octubre de 2023 a Kraków, Poland., This paper introduces a general approach for synthesizing procedural models of the state-transitions of a given discrete system. The approach is general in that it accepts different target languages for modeling the state-transitions of a discrete system; different model acquisition tasks with different target languages, such as the synthesis of STRIPS action models, or the update rule of a cellular automaton, fit as particular instances of our general approach. We follow an inductive approach to synthesis meaning that a set of examples of state-transitions, represented as (pre-state, action, post-state) tuples, are given as input. The goal is to synthesize a structured program that, when executed on a given pre-state, outputs its associated post-state. Our synthesis method implements a combinatorial search in the space of well-structured terminating programs that can be built using a Random-Access Machine (RAM), with a minimalist instruction set, and a finite amount of memory. The combinatorial search is guided with functions that asses the complexity of the candidate programs, as well as their fitness to the given input set of examples., This work is supported by the H2020 AIPLAN4EU project #101016442. Javier Segovia-Aguas is funded by TAILOR, AGAUR SGR and the Spanish grant PID2019-108141GB-I00. Jonathan Ferrer-Mestres is supported by the CSIRO MLAI Future Science Platform. Sergio Jiménez is funded by the Spanish MINECO project PID2021-127647NB-C22.
Repositorio Digital de la UPF
Publicación Contribución de congreso (ConferenceOutput)

State representation learning for goal-conditioned reinforcement learning

  • Steccanella, Lorenzo
  • Jonsson, Anders, 1973-
Comunicació presentada a European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD 2022), celebrat del 19 al 23 de setembre de 2022 a Grenoble, França., This paper presents a novel state representation for reward-free Markov decision processes. The idea is to learn, in a self-supervised manner, an embedding space where distances between pairs of embedded states correspond to the minimum number of actions needed to transition between them. Compared to previous methods, our approach does not require any domain knowledge, learning from offline and unlabeled data. We show how this representation can be leveraged to learn goal-conditioned policies, providing a notion of similarity between states and goals and a useful heuristic distance to guide planning and reinforcement learning algorithms. Finally, we empirically validate our method in classic control domains and multi-goal environments, demonstrating that our method can successfully learn representations in large and/or continuous domains., Anders Jonsson is partially funded by the Spanish grant PID2019-108141GB-I00 and the European project TAILOR (H2020, GA 952215).
Repositorio Digital de la UPF
Publicación Contribución de congreso (ConferenceOutput)

Fast active learning for pure exploration in reinforcement learning

  • Ménard, Pierre
  • Darwiche Domingues, Omar
  • Kaufmann, Emilie
  • Jonsson, Anders
  • Leurent, Édouard
  • Valko, Michal
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 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 theoreticallybacked exploration strategies on the other. Many of them are incarnated by intrinsic motivation and in particular explorations bonuses. A common choice is to use 1/√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 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 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., The research presented was supported by European CHIST-ERA project DELTA, French Ministry of Higher Education and Research, Nord-Pas-de-Calais Regional Council, French National Research Agency project BOLD (ANR19-CE23-0026-04). Anders Jonsson is partially supported by the Spanish grants PID2019-108141GBI00 and PCIN-2017-082. Pierre Ménard is supported by the SFI Sachsen-Anhalt for the project RE-BCI ZS/2019/10/102024 by the Investitionsbank SachsenAnha
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Generalized planning as heuristic search: A new planning search-space that leverages pointers over objects

  • Segovia-Aguas, Javier
  • Jonsson, Anders
  • Jiménez-Celorrio, Sergio|||0000-0003-0561-4880
[EN] Planning as heuristic search is one of the most successful approaches to classical planning but unfortunately, it does not trivially extend to Generalized Planning (GP); GP aims to compute algorithmic solutions that are valid for a set of classical planning instances from a given domain, even if these instances differ in their number of objects, the initial and goal configuration of these objects and hence, in the number (and possible values) of the state variables. State -space search, as it is implemented by heuristic planners, becomes then impractical for GP. In this paper we adapt the planning as heuristic search paradigm to the generalization requirements of GP, and present the first native heuristic search approach to GP. First, the paper introduces a new pointerbased solution space for GP that is independent of the number of classical planning instances in a GP problem and the size of those instances (i.e. the number of objects, state variables and their domain sizes). Second, the paper defines an upgraded version of our GP algorithm, called Best -First Generalized Planning (BFGP), that implements a best -first search in our pointer -based solution space for GP. Lastly, the paper defines a set of evaluation and heuristic functions for BFGP that assess the structural complexity of the candidate GP solutions, as well as their fitness to a given input set of classical planning instances. The computation of these evaluation and heuristic functions does not require grounding states or actions in advance. Therefore our GP as heuristic search approach can handle large sets of state variables with large numerical domains, e.g. integers., This work has been co-funded by MCIN/AEI/10.13039/501100011033 under the Maria de Maeztu Units of Excellence Programme (CEX2021-001195-M) , TAILOR (H2020 #952215) and AIPLAN4EU (H2020 #101016442) projects. Javier Segovia-Aguas is also supported by AGAUR SGR and the Spanish grant PID2019-108141 GB-I00. Sergio Jimenez is supported by the Spanish MINECO project PID2021-127647NB-C22. Anders Jonsson is partially supported by Spanish grant PID2019-108141 GB-I00.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Hierarchical width-based planning and learning

  • Junyent Barbany, Miquel
  • Gómez, Vicenç
  • Jonsson, Anders, 1973-
Comunicació presentada a: ICAPS2021 celebrat del 2 a 13 d'agost de 2021 a Guangzhou, Xina., 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., V. Gómez has received funding from “La Caixa” Foundation (100010434), under the agreement LCF/PR/PR16/51110009 and is supported by the Ramon y Cajal program RYC-2015-18878 (AEI/MINEICO/FSE,UE). A. Jonsson is partially supported by Spanish grants PID2019-108141GB-I00 and PCIN-2017-082.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

State representation learning for goal-conditioned reinforcement learning

  • Steccanella, Lorenzo
  • Jonsson, Anders, 1973-
Comunicació presentada a European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD 2022), celebrat del 19 al 23 de setembre de 2022 a Grenoble, França., This paper presents a novel state representation for reward-free Markov decision processes. The idea is to learn, in a self-supervised manner, an embedding space where distances between pairs of embedded states correspond to the minimum number of actions needed to transition between them. Compared to previous methods, our approach does not require any domain knowledge, learning from offline and unlabeled data. We show how this representation can be leveraged to learn goal-conditioned policies, providing a notion of similarity between states and goals and a useful heuristic distance to guide planning and reinforcement learning algorithms. Finally, we empirically validate our method in classic control domains and multi-goal environments, demonstrating that our method can successfully learn representations in large and/or continuous domains., Anders Jonsson is partially funded by the Spanish grant PID2019-108141GB-I00 and the European project TAILOR (H2020, GA 952215).
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Provably efficient offline reinforcement learning in regular decision processes

  • Cipollone, Roberto
  • Ronca, Alessandro
  • Jonsson, Anders
  • Sadegh Talebi, Mohammad
This paper deals with offline (or batch) Reinforcement Learning (RL) in episodic Regular Decision Processes (RDPs). RDPs are the subclass of Non-Markov Decision Processes where the dependency on the history of past events can be captured by a finite-state automaton. We consider a setting where the automaton that underlies the RDP is unknown, and a learner strives to learn a near-optimal policy using pre-collected data, in the form of non-Markov sequences of observations, without further exploration. We present RegORL, an algorithm that suitably combines automata learning techniques and state-of-the-art algorithms for offline RL in MDPs. RegORL has a modular design allowing one to use any off-the-shelf offline RL algorithm in MDPs. We report a non-asymptotic high-probability sample complexity bound for RegORL to yield an ε-optimal policy, which makes appear a notion of concentrability relevant for RDPs. Furthermore, we present a sample complexity lower bound for offline RL in RDPs. To our best knowledge, this is the first work presenting a provably efficient algorithm for offline learning in RDPs., Roberto Cipollone is partially supported by the EU H2020 project AIPlan4EU (No. 101016442), the ERC-ADG White-Mech (No. 834228), the EU ICT-48 2020 project TAILOR (No. 952215), the PRIN project RIPER (No. 20203FFYLK), and the PNRR MUR project FAIR (No. PE0000013). Anders Jonsson is partially supported by the EU ICT-48 2020 project TAILOR (No. 952215), AGAUR SGR, and the Spanish grant PID2019-108141GB-I00. Alessandro Ronca is partially supported by the ERC project WhiteMech (No. 834228), and the ERC project ARiAT (No. 852769). Mohammad Sadegh Talebi is partially supported by the Independent Research Fund Denmark, grant number 1026-00397B.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Induction and exploitation of subgoal automata for reinforcement learning

  • Furelos Blanco, Daniel
  • Law, Mark
  • Jonsson, Anders, 1973-
  • Broda, Krysia
  • Russo, Alessandra
In this paper we present ISA, an approach for learning and exploiting subgoals in episodic reinforcement learning (RL) tasks. ISA interleaves reinforcement learning with the induction of a subgoal automaton, an automaton whose edges are labeled by the task’s subgoals expressed as propositional logic formulas over a set of high-level events. A subgoal automaton also consists of two special states: a state indicating the successful completion of the task, and a state indicating that the task has finished without succeeding. A state-of-the-art inductive logic programming system is used to learn a subgoal automaton that covers the traces of high-level events observed by the RL agent. When the currently exploited automaton does not correctly recognize a trace, the automaton learner induces a new automaton that covers that trace. The interleaving process guarantees the induction of automata with the minimum number of states, and applies a symmetry breaking mechanism to shrink the search space whilst remaining complete. We evaluate ISA in several gridworld and continuous state space problems using different RL algorithms that leverage the automaton structures. We provide an in-depth empirical analysis of the automaton learning performance in terms of the traces, the symmetry breaking and specific restrictions imposed on the final learnable automaton. For each class of RL problem, we show that the learned automata can be successfully exploited to learn policies that reach the goal, achieving an average reward comparable to the case where automata are not learned but handcrafted and given beforehand., The authors would like to thank the anonymous reviewers for their helpful comments and suggestions. Anders Jonsson is partially supported by the Spanish grants PCIN-2017-082 and PID2019-108141GB-I00.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Bisimulation metrics are optimal transport distances, and can be computed efficiently

  • Calo Oliveira, Sergio
  • Jonsson, Anders
  • Neu, Gergely
  • Schwartz, Ludovic
  • Segovia-Aguas, Javier
We propose a new framework for formulating optimal transport distances between Markov chains. Previously known formulations studied couplings between the entire joint distribution induced by the chains, and derived solutions via a reduction to dynamic programming (DP) in an appropriately defined Markov decision process. This formulation has, however, not led to particularly efficient algorithms so far, since computing the associated DP operators requires fully solving a static optimal transport problem, and these operators need to be applied numerous times during the overall optimization process. In this work, we develop an alternative perspective by considering couplings between a “flattened” version of the joint distributions that we call discounted occupancy couplings, and show that calculating optimal transport distances in the full space of joint distributions can be equivalently formulated as solving a linear program (LP) in this reduced space. This LP formulation allows us to port several algorithmic ideas from other areas of optimal transport theory. In particular, our formulation makes it possible to introduce an appropriate notion of entropy regularization into the optimization problem, which in turn enables us to directly calculate optimal transport distances via a Sinkhorn-like method we call Sinkhorn Value Iteration (SVI). We show both theoretically and empirically that this method converges quickly to an optimal coupling, essentially at the same computational cost of running vanilla Sinkhorn in each pair of states. Along the way, we point out that our optimal transport distance exactly matches the common notion of bisimulation metrics between Markov chains, and thus our results also apply to computing such metrics, and in fact our algorithm turns out to be significantly more efficient than the best known methods developed so far for this purpose., Neu was supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 950180). Anders Jonsson is partially supported by the EU ICT-48 2020 project TAILOR (No. 952215), AGAUR SGR, and the Spanish grant PID2019-108141GB-I00. Javier Segovia-Aguas is supported by MCIN/AEI /10.13039/501100011033 under the Maria de Maeztu Units of Excellence Programme (CEX2021-001195-M).
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Generalized planning as heuristic search

  • Segovia-Aguas, Javier
  • Jiménez, Sergio
  • Jonsson, Anders, 1973-
Comunicació presentada a ICAPS2021, celebrat del 2 a 13 d'agost de 2021 de manera virtual., 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., Javier Segovia-Aguas is supported by TAILOR, a project funded by EU H2020 research and innovation programme no. 952215, an ERC Advanced Grant no. 885107, and grant TIN-2015-67959-P from MINECO, Spain. Sergio Jiménez is supported by the Ramon y Cajal program, RYC-2015-18009, the Spanish MINECO project TIN2017-88476-C2-1-R. Anders Jonsson is partially supported by Spanish grants PID2019-108141GB-I00 and PCIN-2017-082.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Hierarchies of reward machines

  • Furelos Blanco, Daniel
  • Law, Mark
  • Jonsson, Anders
  • Broda, Krysia
  • Russo, Alessandra
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 longhorizon 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., Anders Jonsson is partially funded by TAILOR, AGAUR SGR and Spanish grant PID2019-108141GB-I00
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Synthesis of procedural models for deterministic transition systems

  • Segovia-Aguas, Javier
  • Ferrer Mestres, Jonathan
  • Sergio, Jiménez
Comunicació presentada a la 26th European Conference on Artificial Intelligence, celebrada del 30 de setembre al 4 d'octubre de 2023 a Kraków, Poland., This paper introduces a general approach for synthesizing procedural models of the state-transitions of a given discrete system. The approach is general in that it accepts different target languages for modeling the state-transitions of a discrete system; different model acquisition tasks with different target languages, such as the synthesis of STRIPS action models, or the update rule of a cellular automaton, fit as particular instances of our general approach. We follow an inductive approach to synthesis meaning that a set of examples of state-transitions, represented as (pre-state, action, post-state) tuples, are given as input. The goal is to synthesize a structured program that, when executed on a given pre-state, outputs its associated post-state. Our synthesis method implements a combinatorial search in the space of well-structured terminating programs that can be built using a Random-Access Machine (RAM), with a minimalist instruction set, and a finite amount of memory. The combinatorial search is guided with functions that asses the complexity of the candidate programs, as well as their fitness to the given input set of examples., This work is supported by the H2020 AIPLAN4EU project #101016442. Javier Segovia-Aguas is funded by TAILOR, AGAUR SGR and the Spanish grant PID2019-108141GB-I00. Jonathan Ferrer-Mestres is supported by the CSIRO MLAI Future Science Platform. Sergio Jiménez is funded by the Spanish MINECO project PID2021-127647NB-C22.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Hierarchical average-reward linearly-solvable Markov decision processes

  • Infante Molina, A. Guillermo
  • Jonsson, Anders, 1973-
  • Gómez Cerdà, Vicenç
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., Anders Jonsson is partially funded by TAILOR (EU H2020 #952215), AGAUR SGR and Spanish grant PID2019-108141GB-I00. This publication is part of the action CNS2022-136178 financed by MCIN/AEI/10.13039/501100011033 and by the European Union Next Generation EU/PRTR.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Reinforcement learning for active modality selection during diagnosis

  • Bernardino Perez, Gabriel
  • Jonsson, Anders, 1973-
  • Loncaric, Filip
  • Martí Castellote, Pablo Miki
  • Sitges, Marta
  • Clarysse, Patrick
  • Duchateau, Nicolas
Comunicació presentada a 25th International Conference on Medical Image Computing and Computer Assisted Intervention (MICCAI 2022), celebrat del 18 al 22 de setembre de 2022 a Sentosa, Singapur., Diagnosis through imaging generally requires the combination of several modalities. Algorithms for data fusion allow merging information from different sources, mostly combining all images in a single step. In contrast, much less attention has been given to the incremental addition of new data descriptors, and the consideration of their costs (which can cover economic costs but also patient comfort and safety). In this work, we formalise clinical diagnosis of a patient as a sequential process of decisions, each of these decisions being whether to take an additional acquisition, or, if there is enough information, to end the examination and produce a diagnosis. We formulate the goodness of a diagnosis process as a combination of the classification accuracy minus the cost of the acquired modalities. To obtain a policy, we apply reinforcement learning, which recommends the next modality to incorporate based on data acquired at previous stages and aiming at maximising the accuracy/cost trade-off. This policy therefore performs medical diagnosis and patient-wise feature selection simultaneously. We demonstrate the relevance of this strategy on two binary classification datasets: a subset of a public heart disease database, including 531 instances with 11 scalar features, and a private echocardiographic dataset including signals from 5 standard image sequences used to assess cardiac function (2 speckle tracking, 2 flow Doppler and tissue Doppler), from 188 patients suffering hypertension, and 60 controls. For each individual, our algorithm allows acquiring only the modalities relevant for the diagnosis, avoiding low-information acquisitions, which both resulted in higher stability of the chosen modalities and better classification performance under a limited budget., The authors acknowledge the partial support from the French ANR (LABEX PRIMES of Univ. Lyon [ANR-11-LABX-0063] and the JCJC project “MIC-MAC” [ANR-19-CE45-0005]) and the Spanish AEI [PID2019-108141GB-I00].
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Generalized planning as heuristic search: a new planning search-space that leverages pointers over objects

  • Segovia-Aguas, Javier
  • Jiménez, Sergio
  • Jonsson, Anders, 1973-
Planning as heuristic search is one of the most successful approaches to classical planning but unfortunately, it does not trivially extend to Generalized Planning (GP); GP aims to compute algorithmic solutions that are valid for a set of classical planning instances from a given domain, even if these instances differ in their number of objects, the initial and goal configuration of these objects and hence, in the number (and possible values) of the state variables. State-space search, as it is implemented by heuristic planners, becomes then impractical for GP. In this paper we adapt the planning as heuristic search paradigm to the generalization requirements of GP, and present the first native heuristic search approach to GP. First, the paper introduces a new pointer-based solution space for GP that is independent of the number of classical planning instances in a GP problem and the size of those instances (i.e. the number of objects, state variables and their domain sizes). Second, the paper defines an upgraded version of our GP algorithm, called Best-First Generalized Planning (BFGP), that implements a best-first search in our pointer-based solution space for GP. Lastly, the paper defines a set of evaluation and heuristic functions for BFGP that assess the structural complexity of the candidate GP solutions, as well as their fitness to a given input set of classical planning instances. The computation of these evaluation and heuristic functions does not require grounding states or actions in advance. Therefore our GP as heuristic search approach can handle large sets of state variables with large numerical domains, e.g. integers., This work has been co-funded by MCIN/AEI /10.13039/501100011033 under the Maria de Maeztu Units of Excellence Programme (CEX2021-001195-M), TAILOR (H2020 #952215) and AIPlan4EU (H2020 #101016442) projects. Javier Segovia-Aguas is also supported by AGAUR SGR and the Spanish grant PID2019-108141 GB-I00. Sergio Jiménez is supported by the Spanish MINECO project PID2021-127647NB-C22. Anders Jonsson is partially supported by Spanish grant PID2019-108141 GB-I00.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Fast active learning for pure exploration in reinforcement learning

  • Ménard, Pierre
  • Darwiche Domingues, Omar
  • Kaufmann, Emilie
  • Jonsson, Anders
  • Leurent, Édouard
  • Valko, Michal
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 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 theoreticallybacked exploration strategies on the other. Many of them are incarnated by intrinsic motivation and in particular explorations bonuses. A common choice is to use 1/√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 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 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., The research presented was supported by European CHIST-ERA project DELTA, French Ministry of Higher Education and Research, Nord-Pas-de-Calais Regional Council, French National Research Agency project BOLD (ANR19-CE23-0026-04). Anders Jonsson is partially supported by the Spanish grants PID2019-108141GBI00 and PCIN-2017-082. Pierre Ménard is supported by the SFI Sachsen-Anhalt for the project RE-BCI ZS/2019/10/102024 by the Investitionsbank SachsenAnha