# Branching Time Active Inference: empirical study and complexity class analysis

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 57 references that are in the map.
- First posted on arXiv 22 Nov 2021.

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

- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Tutorial on Variational Autoencoders](https://mlsanity.com/paper/1606.05908/) (2016)
- [Playing FPS Games with Deep Reinforcement Learning](https://mlsanity.com/paper/1609.05521/) (2016)
- [Active inference on discrete state-spaces: a synthesis](https://mlsanity.com/paper/2001.07203/) (2020)
- [Deep active inference agents using Monte-Carlo methods](https://mlsanity.com/paper/2006.04176/) (2020)
- [Sophisticated Inference](https://mlsanity.com/paper/2006.04120/) (2020)
- [Deep Active Inference as Variational Policy Gradients](https://mlsanity.com/paper/1907.03876/) (2019)
- [Whence the Expected Free Energy?](https://mlsanity.com/paper/2004.08128/) (2020)
- [End-to-End Pixel-Based Deep Active Inference for Body Perception and Action](https://mlsanity.com/paper/2001.05847/) (2019)
- [Active Inference and Behavior Trees for Reactive Action Planning and Execution in Robotics](https://mlsanity.com/paper/2011.09756/) (2020)
- [Bayesian model reduction](https://mlsanity.com/paper/1805.07092/) (2018)
- [Learning Perception and Planning with Deep Active Inference](https://mlsanity.com/paper/2001.11841/) (2020)
- [Exploration and preference satisfaction trade-off in reward-free learning](https://mlsanity.com/paper/2106.04316/) (2021)
- [A Factor Graph Approach to Automated Design of Bayesian Signal Processing Algorithms](https://mlsanity.com/paper/1811.03407/) (2018)
- [Learning, Planning, and Control in a Monolithic Neural Event Inference Architecture](https://mlsanity.com/paper/1809.07412/) (2018)
- [Leading or Following? Dyadic Robot Imitative Interaction Using the Active Inference Framework](https://mlsanity.com/paper/2103.02137/) (2021)

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

- [On efficient computation in active inference](https://mlsanity.com/paper/2307.00504/) (2023)
- [Active Inference as a Model of Agency](https://mlsanity.com/paper/2401.12917/) (2024)
- [Supervised structure learning](https://mlsanity.com/paper/2311.10300/) (2023)
- [Geometric Methods for Sampling, Optimisation, Inference and Adaptive Agents](https://mlsanity.com/paper/2203.10592/) (2022)
- [Deconstructing deep active inference](https://mlsanity.com/paper/2303.01618/) (2023)
- [Branching Time Active Inference with Bayesian Filtering](https://mlsanity.com/paper/2112.07406/) (2021)
- [Multi-Modal and Multi-Factor Branching Time Active Inference](https://mlsanity.com/paper/2206.12503/) (2022)
- [Efficient search of active inference policy spaces using k-means](https://mlsanity.com/paper/2209.02550/) (2022)
- [A memory-based active inference model of DishBrain-like adaptive behaviour](https://mlsanity.com/paper/2508.06980/) (2025)

## Abstract (arXiv)

Active inference is a state-of-the-art framework for modelling the brain that explains a wide range of mechanisms such as habit formation, dopaminergic discharge and curiosity. However, recent implementations suffer from an exponential complexity class when computing the prior over all the possible policies up to the time horizon. Fountas et al (2020) used Monte Carlo tree search to address this problem, leading to very good results in two different tasks. Additionally, Champion et al (2021a) proposed a tree search approach based on (temporal) structure learning. This was enabled by the development of a variational message passing approach to active inference, which enables compositional construction of Bayesian networks for active inference. However, this message passing tree search approach, which we call branching-time active inference (BTAI), has never been tested empirically. In this paper, we present an experimental study of BTAI in the context of a maze solving agent. In this context, we show that both improved prior preferences and deeper search help mitigate the vulnerability to local minima. Then, we compare BTAI to standard active inference (AcI) on a graph navigation task. We show that for small graphs, both BTAI and AcI successfully solve the task. For larger graphs, AcI exhibits an exponential (space) complexity class, making the approach intractable. However, BTAI explores the space of policies more efficiently, successfully scaling to larger graphs. Then, BTAI was compared to the POMCP algorithm on the frozen lake environment. The experiments suggest that BTAI and the POMCP algorithm accumulate a similar amount of reward. Also, we describe when BTAI receives more rewards than the POMCP agent, and when the opposite is true. Finally, we compared BTAI to the approach of Fountas et al (2020) on the dSprites dataset, and we discussed the pros and cons of each approach.