Skip to main content
Kent Academic Repository

Branching Time Active Inference: empirical study and complexity class analysis

Champion, Théophile, Bowman, Howard, Grzes, Marek (2022) Branching Time Active Inference: empirical study and complexity class analysis. Neural Networks, 152 . pp. 450-466. ISSN 0893-6080. (doi:10.1016/j.neunet.2022.05.010) (KAR id:98200)


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 (space and time) 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 (Champion, Bowman, Grześ, 2021), which enables compositional construction of Bayesian networks foractive 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 the approach (Champion, Grześ, Bowman, 2021) 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 (Silver and Veness, 2010) 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.

Item Type: Article
DOI/Identification number: 10.1016/j.neunet.2022.05.010
Uncontrolled keywords: Active inference; Variational message passing; Tree search; Planning; Free energy principle
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming, > QA76.87 Neural computers, neural networks
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Funders: University of Kent (
Depositing User: Marek Grzes
Date Deposited: 21 Nov 2022 09:46 UTC
Last Modified: 22 Nov 2022 12:42 UTC
Resource URI: (The current URI for this page, for reference purposes)

University of Kent Author Information

Champion, Théophile.

Creator's ORCID:
CReDIT Contributor Roles:

Bowman, Howard.

Creator's ORCID:
CReDIT Contributor Roles:

Grzes, Marek.

Creator's ORCID:
CReDIT Contributor Roles:
  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.