# Lifted Forward Planning in Relational Factored Markov Decision Processes with Concurrent Actions

arXiv: https://arxiv.org/abs/2505.22147 · HTML: https://mlsanity.com/paper/2505.22147/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 46 references that are in the map.
- First posted on arXiv 28 May 2025.

## Builds on (most cited first, 6 of 6)

- [The Complexity of Decentralized Control of Markov Decision Processes](https://mlsanity.com/paper/1301.3836/) (2013)
- [Parallelizing the dual revised simplex method](https://mlsanity.com/paper/1503.01889/) (2015)
- [Tractability through Exchangeability: A New Perspective on Efficient Probabilistic Inference](https://mlsanity.com/paper/1401.1247/) (2014)
- [Lifted Variable Elimination: Decoupling the Operators from the Constraint Language](https://mlsanity.com/paper/1402.0565/) (2014)
- [Model Reduction Techniques for Computing Approximately Optimal Solutions for Markov Decision Processes](https://mlsanity.com/paper/1302.1533/) (2013)
- [pyRDDLGym: From RDDL to Gym Environments](https://mlsanity.com/paper/2211.05939/) (2022)

## Built on by (most cited first, 1 of 1)

- [The Curious Case of Exploding DecPOMDPs: Containing the Fire through Policy Counting](https://mlsanity.com/paper/2608.17749/) (2026)

## Abstract (arXiv)

When allowing concurrent actions in Markov Decision Processes, whose state and action spaces grow exponentially in the number of objects, computing a policy becomes highly inefficient, as it requires enumerating the joint of the two spaces. For the case of indistinguishable objects, we present a first-order representation to tackle the exponential blow-up in the action and state spaces. We propose Foreplan, an efficient relational forward planner, which uses the first-order representation allowing to compute policies in space and time polynomially in the number of objects. Thus, Foreplan significantly increases the number of planning problems solvable in an exact manner in reasonable time, which we underscore with a theoretical analysis. To speed up computations even further, we also introduce an approximate version of Foreplan, including guarantees on the error. Further, we provide an empirical evaluation of both Foreplan versions, demonstrating a speedup of several orders of magnitude. For the approximate version of Foreplan, we also empirically show that the induced error is often negligible.