Branching Time Active Inference: empirical study and complexity class analysis

• URL: http://arxiv.org/abs/2111.11276v1
• Date: Mon, 22 Nov 2021 15:30:35 GMT
• Title: Branching Time Active Inference: empirical study and complexity class analysis
• Authors: Th\'eophile Champion, Howard Bowman, Marek Grze\'s
• Abstract summary: We present an experimental study of the branching-time active inference approach (BTAI) in the context of a maze solving agent. We show that both improved prior preferences and deeper search help mitigate the vulnerability to local minima.
• Score: 3.5450828190071655
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 structure learning. This was enabled by the development of a variational message passing approach to active inference (Champion et al., 2021b), 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 the approach (Champion et al., 2021a) 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 (AI) on a graph navigation task. We show that for small graphs, both BTAI and AI successfully solve the task. For larger graphs, AI exhibits an exponential (space) complexity class, making the approach intractable. However, BTAI explores the space of policies more efficiently, successfully scaling to larger graphs.

Related papers

• Tree Search for Language Model Agents [69.43007235771383]
  We propose an inference-time search algorithm for LM agents to perform exploration and multi-step planning in interactive web environments. Our approach is a form of best-first tree search that operates within the actual environment space. It is the first tree search algorithm for LM agents that shows effectiveness on realistic web tasks.
  arXiv  Detail & Related papers  (2024-07-01T17:07:55Z)
• Pangu-Agent: A Fine-Tunable Generalist Agent with Structured Reasoning [50.47568731994238]
  Key method for creating Artificial Intelligence (AI) agents is Reinforcement Learning (RL) This paper presents a general framework model for integrating and learning structured reasoning into AI agents' policies.
  arXiv  Detail & Related papers  (2023-12-22T17:57:57Z)
• Planning to Learn: A Novel Algorithm for Active Learning during Model-Based Planning [6.3318086812818475]
  We present an extension of SI - sophisticated learning (SL) - that more fully incorporates active learning during planning. SL maintains beliefs about how model parameters would change under the future observations expected under each policy. To accomplish these aims, we make use of a novel, biologically inspired environment designed to highlight the problem structure for which SL offers a unique solution.
  arXiv  Detail & Related papers  (2023-08-15T20:39:23Z)
• Multi-Modal and Multi-Factor Branching Time Active Inference [2.513785998932353]
  Two versions of branching time active inference (BTAI) based on Monte-Carlo tree search have been developed. However, those two versions of BTAI still suffer from an exponential complexity class w.r.t the number of observed and latent variables being modelled. In this paper, we resolve this limitation by allowing the modelling of several observations, each of them having its own likelihood mapping. The inference algorithm then exploits the factorisation of the likelihood and transition mappings to accelerate the computation of the posterior.
  arXiv  Detail & Related papers  (2022-06-24T22:07:21Z)
• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
  Machine learning has emerged as a promising paradigm for branching. We propose retro branching; a simple yet effective approach to RL for branching. We outperform the current state-of-the-art RL branching algorithm by 3-5x and come within 20% of the best IL method's performance on MILPs with 500 constraints and 1000 variables.
  arXiv  Detail & Related papers  (2022-05-28T06:08:07Z)
• Branching Time Active Inference: the theory and its generality [3.1542695050861544]
  We present an alternative framework that aims to unify tree search and active inference by casting planning as a structure learning problem. The first propagates the expected free energy forward in time, while the second propagates it backward. Then, we demonstrate that forward and backward propagations are related to active inference and sophisticated inference, respectively, thereby clarifying the differences between those two planning strategies.
  arXiv  Detail & Related papers  (2021-11-22T10:56:03Z)
• Dive into Decision Trees and Forests: A Theoretical Demonstration [0.0]
  Decision trees use the strategy of "divide-and-conquer" to divide a complex problem on the dependency between input features and labels into smaller ones. Recent advances have greatly improved their performance in computational advertising, recommender system, information retrieval, etc.
  arXiv  Detail & Related papers  (2021-01-20T16:47:59Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)
• Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies [76.83991682238666]
  Branch and Bound (B&B) is the exact tree search method typically used to solve Mixed-Integer Linear Programming problems (MILPs) We propose a novel imitation learning framework, and introduce new input features and architectures to represent branching.
  arXiv  Detail & Related papers  (2020-02-12T17:43:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.