Probabilistic Temporal Logic for Reasoning about Bounded Policies

Nima Motamed, Natasha Alechina, Mehdi Dastani, Dragan Doder, Brian LoganIJCAI 2023 · OpenReview

TL;DR

This paper introduces PLBP, a novel probabilistic temporal logic designed to reason about the uncertain outcomes of agent policies in stochastic environments. PLBP allows for explicit reasoning about actions, their preconditions, and their probabilistic postconditions, enabling verification of agent intentions and policies with strong computational guarantees (PSPACE-complete model checking and decidable satisfiability).

What Problem Does This Paper Address?

Designing intelligent agents that can operate effectively in real-world, uncertain environments requires a formal framework to reason about their decision-making processes. Specifically, when agents act in stochastic environments, their actions don't always lead to predictable outcomes. This uncertainty makes it challenging to predict and verify an agent's behavior, especially when considering their intentions and how they might revise them. Existing probabilistic temporal logics often lack the expressiveness to reason about specific actions, their preconditions, and their multiple possible outcomes, or they suffer from high computational complexity (undecidable model checking). This paper aims to bridge this gap by proposing a logic that balances expressive power for practical AI applications with manageable computational complexity.

Methods

The core contribution is the introduction of Probabilistic Logic of Bounded Policies (PLBP). PLBP is a probabilistic temporal logic designed for Markov Decision Processes (MDPs). Key features include:

  • Reasoning about Actions: PLBP explicitly incorporates actions, their preconditions (conditions that must be met for an action to be executable), and their probabilistic postconditions (the possible outcomes of an action).
  • Bounded Policies: The logic focuses on "bounded policies," which are strategies for agents that operate for a finite, specified number of timesteps. This is a practical constraint that helps manage complexity.
  • Finite Traces: PLBP is interpreted over finite traces (sequences of states and actions), which are more natural for many AI applications than infinite traces.
  • Syntax and Semantics: The logic has a defined syntax for state formulas (reasoning about states) and path formulas (reasoning about sequences of states and actions). The semantics are defined recursively over states and paths.
  • Model Checking Algorithm: The paper presents a nondeterministic algorithm for model checking that runs in polynomial space, leading to a PSPACE-complete complexity for the model checking problem.
  • Satisfiability Procedure: A decision procedure for satisfiability is outlined, leveraging a small model property and reducing the problem to first-order logic over real closed fields, resulting in a 2EXPSPACE complexity.

Datasets

Not discussed in the paper. The paper focuses on defining a logic and its theoretical properties within the context of Markov Decision Processes, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Bridging Expressiveness and Tractability: The central insight is that by focusing on bounded policies and finite traces, it's possible to develop a probabilistic temporal logic that is both expressive enough for practical agent reasoning (including intentions and action outcomes) and computationally tractable.
  • Action-Centric Reasoning: Explicitly modeling action preconditions and postconditions is crucial for reasoning about agent behavior and intention coherence, a capability often missing in other probabilistic logics.
  • Small Model Property: The proof that satisfiability holds in a "small model" (a tree-shaped structure with limited depth) is a significant theoretical result, simplifying the decision procedure.
  • Practical Implications for Intention Revision: The logic is directly motivated by the need to build theories of intention revision for agents. Its ability to reason about probabilistic outcomes and action specifics is essential for formalizing concepts like intention coherence.

Key Results

  • Decidable Model Checking: The model checking problem for PLBP is decidable and proven to be PSPACE-complete.
  • Decidable Satisfiability: The satisfiability problem for PLBP is decidable with a 2EXPSPACE algorithm.
  • Small Model Property: If a PLBP formula is satisfiable, it is satisfiable in an MDP with a state space bounded by the formula's policy depth.
  • Expressive Power: PLBP can express properties related to action executability, probabilistic outcomes, and bounded policies, which are not directly expressible in many existing probabilistic temporal logics like PCTL or pCTL*.

Limitations and Future Work

  • Bounded Policies: While a strength for tractability, the focus on bounded policies might be a limitation for scenarios requiring reasoning about infinitely long-term strategies. However, the authors note that this is sufficient for their intended applications.
  • Deterministic Policies: The current definition focuses on deterministic policies, though the authors mention that their work extends to state-action histories.
  • Future Work:
    • Intention Revision Theory: The primary future direction is to use PLBP to build a formal theory of intention revision under uncertainty, extending existing AGM-style belief revision frameworks.
  • Reinforcement Learning: Applying PLBP to reinforcement learning, potentially incorporating reward signals and imperfect information.
  • Expressive Power Analysis: Investigating the expressive power of PLBP further, possibly through bisimulation relations.
  • Axiomatization: Developing a sound and complete axiomatization for PLBP.

Summary updated

Abstract

To build a theory of intention revision for agents operating in stochastic environments, we need a logic in which we can explicitly reason about their decision-making policies and those policies' uncertain outcomes. Towards this end, we propose PLBP, a novel probabilistic temporal logic for Markov Decision Processes that allows us to reason about policies of bounded size. The logic is designed so that its expressive power is sufficient for the intended applications, whilst at the same time possessing strong computational properties. We prove that the satisfiability problem for our logic is decidable, and that its model checking problem is PSPACE-complete. This allows us to e.g. algorithmically verify whether an agent's intentions are coherent, or whether a specific policy satisfies safety and/or liveness properties.
BibTeX
@inproceedings{motamed2023probabilistic,
  author = {Nima Motamed and Natasha Alechina and Mehdi Dastani and Dragan Doder and Brian Logan},
  title = {{Probabilistic Temporal Logic for Reasoning about Bounded Policies}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  url = {https://openreview.net/forum?id=a5WmUmF098},
}
Figure