Lifted Model Checking for Relational MDPs

• URL: http://arxiv.org/abs/2106.11735v1
• Date: Tue, 22 Jun 2021 13:12:36 GMT
• Title: Lifted Model Checking for Relational MDPs
• Authors: Wen-Chi Yang, Jean-Fran\c{c}ois Raskin and Luc De Raedt
• Abstract summary: pCTL-REBEL is a lifted model checking approach for verifying pCTL properties on relational MDPs. We show that the pCTL model checking approach is decidable for relational MDPs even for possibly infinite domains.
• Score: 12.574454799055026
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Model checking has been developed for verifying the behaviour of systems with stochastic and non-deterministic behavior. It is used to provide guarantees about such systems. While most model checking methods focus on propositional models, various probabilistic planning and reinforcement frameworks deal with relational domains, for instance, STRIPS planning and relational Markov Decision Processes. Using propositional model checking in relational settings requires one to ground the model, which leads to the well known state explosion problem and intractability. We present pCTL-REBEL, a lifted model checking approach for verifying pCTL properties on relational MDPs. It extends REBEL, the relational Bellman update operator, which is a lifted value iteration approach for model-based relational reinforcement learning, toward relational model-checking. PCTL-REBEL is lifted, which means that rather than grounding, the model exploits symmetries and reasons at an abstract relational level. Theoretically, we show that the pCTL model checking approach is decidable for relational MDPs even for possibly infinite domains provided that the states have a bounded size. Practically, we contribute algorithms and an implementation of lifted relational model checking, and we show that the lifted approach improves the scalability of the model checking approach.

Related papers

• Incorporating Domain Knowledge in Deep Neural Networks for Discrete Choice Models [0.5801044612920815]
  This paper proposes a framework that expands the potential of data-driven approaches for DCM. It includes pseudo data samples that represent required relationships and a loss function that measures their fulfillment. A case study demonstrates the potential of this framework for discrete choice analysis.
  arXiv  Detail & Related papers  (2023-05-30T12:53:55Z)
• Predictable MDP Abstraction for Unsupervised Model-Based RL [93.91375268580806]
  We propose predictable MDP abstraction (PMA) Instead of training a predictive model on the original MDP, we train a model on a transformed MDP with a learned action space. We theoretically analyze PMA and empirically demonstrate that PMA leads to significant improvements over prior unsupervised model-based RL approaches.
  arXiv  Detail & Related papers  (2023-02-08T07:37:51Z)
• When to Update Your Model: Constrained Model-based Reinforcement Learning [50.74369835934703]
  We propose a novel and general theoretical scheme for a non-decreasing performance guarantee of model-based RL (MBRL) Our follow-up derived bounds reveal the relationship between model shifts and performance improvement. A further example demonstrates that learning models from a dynamically-varying number of explorations benefit the eventual returns.
  arXiv  Detail & Related papers  (2022-10-15T17:57:43Z)
• Relational Action Bases: Formalization, Effective Safety Verification, and Invariants (Extended Version) [67.99023219822564]
  We introduce the general framework of relational action bases (RABs) RABs generalize existing models by lifting both restrictions. We demonstrate the effectiveness of this approach on a benchmark of data-aware business processes.
  arXiv  Detail & Related papers  (2022-08-12T17:03:50Z)
• Distributional Depth-Based Estimation of Object Articulation Models [21.046351215949525]
  We propose a method that efficiently learns distributions over articulation model parameters directly from depth images. Our core contributions include a novel representation for distributions over rigid body transformations. We introduce a novel deep learning based approach, DUST-net, that performs category-independent articulation model estimation.
  arXiv  Detail & Related papers  (2021-08-12T17:44:51Z)
• Validation and Inference of Agent Based Models [0.0]
  Agent Based Modelling (ABM) is a computational framework for simulating the behaviours and interactions of autonomous agents. Recent research in ABC has yielded increasingly efficient algorithms for calculating the approximate likelihood. These are investigated and compared using a pedestrian model in the Hamilton CBD.
  arXiv  Detail & Related papers  (2021-07-08T05:53:37Z)
• Control-Oriented Model-Based Reinforcement Learning with Implicit Differentiation [11.219641045667055]
  We propose an end-to-end approach for model learning which directly optimize the expected returns using implicit differentiation. We provide theoretical and empirical evidence highlighting the benefits of our approach in the model misspecification regime compared to likelihood-based methods.
  arXiv  Detail & Related papers  (2021-06-06T23:15:49Z)
• COMBO: Conservative Offline Model-Based Policy Optimization [120.55713363569845]
  Uncertainty estimation with complex models, such as deep neural networks, can be difficult and unreliable. We develop a new model-based offline RL algorithm, COMBO, that regularizes the value function on out-of-support state-actions. We find that COMBO consistently performs as well or better as compared to prior offline model-free and model-based methods.
  arXiv  Detail & Related papers  (2021-02-16T18:50:32Z)
• Improving the Reconstruction of Disentangled Representation Learners via Multi-Stage Modeling [54.94763543386523]
  Current autoencoder-based disentangled representation learning methods achieve disentanglement by penalizing the ( aggregate) posterior to encourage statistical independence of the latent factors. We present a novel multi-stage modeling approach where the disentangled factors are first learned using a penalty-based disentangled representation learning method. Then, the low-quality reconstruction is improved with another deep generative model that is trained to model the missing correlated latent variables.
  arXiv  Detail & Related papers  (2020-10-25T18:51:15Z)
• Control as Hybrid Inference [62.997667081978825]
  We present an implementation of CHI which naturally mediates the balance between iterative and amortised inference. We verify the scalability of our algorithm on a continuous control benchmark, demonstrating that it outperforms strong model-free and model-based baselines.
  arXiv  Detail & Related papers  (2020-07-11T19:44:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.