A Translation of Probabilistic Event Calculus into Markov Decision Processes

Reasoning about actions and their effects in dynamic, uncertain environments is a fundamental challenge in Artificial Intelligence (AI). The importance of narrative reasoning – the ability to represent and reason about sequences of events and their causal relationships over time – has been recognised since the early days of AI, leading to various temporal reasoning formalisms [10, 1, 5, 12]. Building on these early foundations, the Probabilistic Event Calculus (PEC) [3] has emerged as a powerful framework for representing and reasoning about uncertain scenarios. PEC extends the Event Calculus (EC) [5, 11], to provide an “action-language” style framework for modelling actions, their effects, and the evolution of world states over time under uncertainty. PEC-style frameworks offer highly interpretable and flexible representations of complex narratives, with demonstrated applications in domains such as medicine, environmental monitoring, and commonsense reasoning [2, 3]. Markov Decision Processes (MDPs), meanwhile, have established themselves as a powerful framework for modelling time-evolving systems controlled by an agent. MDPs and their variants are widely used across AI for decision-making under uncertainty and serve as the foundation for many statistical and reinforcement learning algorithms. While MDPs excel at control optimisation problems, PEC and its variants offer superior narrative interpretability but lack mechanisms for learning goal-directed behaviour.

A translation between these frameworks presents a compelling opportunity to bridge this gap, combining PEC’s human-readable representation with MDP’s computational efficiency and reinforcement learning capabilities. Such a bridge would allow for both efficient PEC implementation and the application of statistical learning techniques to narrative reasoning tasks. Towards this goal, we have developed a novel translation of PEC into an MDP framework, termed the PEC-MDP. This translation preserves the core assumptions and semantics of PEC while enabling the application of a wide range of MDP-based algorithms to PEC’s human-readable domains.

The key contributions of our work include:

• $\mathrm{■}$

  A formal translation of PEC domains to PEC-MDPs, with a Python implementation made available through a shared repository.

• $\mathrm{■}$

  An approach for performing temporal projection via the PEC-MDP formalism.

• $\mathrm{■}$

  A novel approach to planning under uncertainty in PEC domains.

A translation of PEC domains into a MDP-derivative requires reconciliation of several key differences between the two frameworks: i. PEC dynamics operate on fluents (properties of the environment), while the MDP operates directly on environment states without internal structure; ii. PEC does not model rewards; iii. PEC assumes a progression of time independent to actions and environmental changes, while the MDP assumes a direct correspondence of each discrete time step to each episode of agent-state interaction; iv. PEC allows for simultaenous action-taking while the MDP does not; v. Action-taking in PEC conditions obligatorily on time-instants and optionally on specific partial fluent conditions, while the MDP’s standard stationary policy which conditions only on the state an agent resides in.

Given that PEC’s action-taking is conditioned on time, a non-stationary policy [6] is adopted to model time-dependent policies while maintaining stationary transition dynamics. The reward component of the MDP framework is omitted in the initial translation of PEC domains as PEC domains are without inherent reward signals. The PEC-MDP formalism is thus a reward-free MDP with a non-stationary policy.

To allow for efficient matrix operations, we translate PEC’s natural language components into 0-based numerical encodings while maintaining bidirectional mappings to preserve interpretability. This encoding assigns each element an index based on arbitrary orderings over PEC fluents $ℱ$, values $𝒱$, and actions $𝒰$. The PEC-MDP state space is constructed through a two-step process: first, PEC fluent states are mapped to vector representations of fluent value indices (i.e. $(x_0,x_1,x_2,\mathrm{\dots })$ where $x_j$ denotes that the index of the value taken by the fluent of index $j$); next, these vectors are mapped to integers for a more compact representation, acting as the base unit of a PEC-MDP state. The vector representation allows access to specific fluents, enabling two crucial functions: i. the mapping of a partial fluent state $\tilde{X}$ to a set of PEC-MDP states in which fluents in $\tilde{X}$ are entailed; ii. the update of a PEC-MDP state with the effect of a partial fluent state $\tilde{X}$ by modifying fluent elements affected by $\tilde{X}$ but retaining those which are not.

Next, to accommodate PEC’s more flexible action-taking mechanisms into the MDP’s rigid framework, we introduce action-taking situations composing single, composite, and null actions to simulate time-points at which agents perform one action, multiple actions simultaneously, or do not take any actions, respectively. The set of action-taking situations is determined by referring to p-propositions, to find all possible action combinations that may be taken at one time, including the null action situation where no action is taken.

Time instants are normalised to begin at 0 while preserving temporal ordering. The initial distribution is retrieved from PEC’s i-propositions, as a probability distribution over PEC-MDP states mapped from fluent states. Transition probabilities are derived from c-propositions, where the effects of an action-taking situation are aggregated from its composite actions. The fluent state update operation associates a current state to an updated state given some effect $\tilde{X}$ with its corresponding probability. Finally, a non-stationary policy captures PEC’s time-conditioned action probabilities from p-propositions, representing distributions over action-taking situations rather than individual actions.

The PEC-MDP translation has been fully implemented in Python and may be found here. For a comprehensive overview of the functionalities, example domains, and usage instructions, readers are directed to the repository’s README file.

The PEC-MDP enables applying MDP techniques to PEC domains, most notably reinforcement learning for optimal decision-making, while preserving PEC’s original capability for temporal projection in narrative reasoning.

Previous implementations of temporal reasoning for PEC predominately calculate probabilities through summing over all possible worlds [3], or through approximate sampling [2]. Our proposed approach provides an exact solution through efficient matrix operations. We define policy-weighted transition matrices to propagate the initial distribution over PEC-MDP states forward to the queried time, to retrieve the distribution over states at that time. The probability that $\tilde{X}$ holds then is computed by summing probabilities over all fluent states that entail $\tilde{X}$. While a formal efficiency experiment has yet to be conducted, this method avoids the combinatorial explosion that comes with the computation of all possible worlds.

Next, to apply objective-directed strategies for the PEC-MDP, a desirability criterion must first be established in the form of an MDP reward function to guide agent behaviour. Once an appropriate quantitative reward signal is defined over outcomes, actions, or transitions, suitable reinforcement learning methods can be applied to discover optimal policies for the narrative domain. To preserve the interpretability advantages of PEC’s original formalism, learned policies may be translated back into human-readable p-propositions. This requires deterministic policies since action-taking situations must be separated into individual actions for p-propositions, meaning that probabilistic dependencies between actions cannot be preserved.

The mapping of a policy over action-taking situations is trivial where each action in a situation is performed at the corresponding instant where the fluent state holds. However, as this generates a large number of p-propositions, refinements can be applied to reduce this set for interpretability while maintaining semantic equivalence. These include eliminating p-propositions for unreachable state-time combinations and generalising fluent state conditions to their minimal distinguishing features.

The complete formal translation of the PEC-MDP may be found at [15], alongside a more detailed outline of temporal reasoning and objective-directed strategies.

Finally, let us note that other probabilistic extensions of the Event Calculus have been proposed, focusing on event recognition using probabilistic logic programming and learning from noisy data in both offline and online settings, i.e., [14, 13, 8, 4, 7]. In contrast, our PEC-MDP framework inherits the main features of PEC, which is more expressive (see [2] for a comparison), compiling it into an MDP. This shift lays the groundwork for reinforcement learning, positioning our work toward goal-driven reasoning and policy optimisation.

While our current work focuses on the PEC-MDP’s application to temporal projection and objective-directed learning, the PEC-MDP framework lays the groundwork for further applications that leverage MDP-based techniques within narrative domains. Beyond these broader applications, future work will include formal efficiency analyses and extending the framework to the Epistemic Probabilistic Event Calculus (EPEC) [2].