Probabilistic Temporal Logic for Reasoning about Bounded Policies

Nima Motamed, Natasha Alechina, Mehdi Dastani, Dragan Doder, Brian Logan

Research output: Chapter in Book/Report/Conference proceedingConference Article in proceedingAcademicpeer-review


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. Toward 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.

Original languageEnglish
Title of host publicationProceedings of the 32nd International Joint Conference on Artificial Intelligence, IJCAI 2023
EditorsEdith Elkind
Number of pages8
ISBN (Electronic)9781956792034
Publication statusPublished - 2023


Dive into the research topics of 'Probabilistic Temporal Logic for Reasoning about Bounded Policies'. Together they form a unique fingerprint.

Cite this