💻 computer science

Neurosymbolic Reasoning with Incremental Knowledge for Sample Efficient Hierarchical Reinforcement Learning

This paper proposes a neurosymbolic Hierarchical Reinforcement Learning framework that integrates Incremental Knowledge (InK) and Belief World Tree Search to enable updatable symbolic planning and reward-shaped neural learning, thereby significantly improving sample efficiency in sparse-reward, long-horizon navigation tasks.

Original authors: Subrat Prasad Panda, Blaise Genest, Arvind Easwaran

Published 2026-08-05

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Subrat Prasad Panda, Blaise Genest, Arvind Easwaran

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are teaching a robot to navigate a giant, shifting maze. In the world of artificial intelligence, this is a classic challenge known as Reinforcement Learning (RL). Think of it like training a dog: you give it a treat (a reward) when it does something right, and it learns to repeat that action. But here's the catch: if the maze is huge and the treats are hidden very far away, the dog might wander around for a million years before accidentally finding the path. This is the "sample efficiency" problem—how many tries does the AI need to learn?

To fix this, scientists often use "Hierarchical Reinforcement Learning" (HRL). Instead of a robot trying to figure out every single step at once, you give it a boss and a worker. The boss (the high-level planner) decides on big goals, like "go to the kitchen," while the worker (the low-level controller) figures out the tiny muscle movements to get there. Usually, the boss is a rigid, pre-programmed map that never changes. But what if the maze has secret walls that only appear when you bump into them? A rigid boss would keep trying to walk through a wall that just appeared, wasting time. This paper explores a smarter way: a robot that learns the map while it moves, updating its boss's map in real-time based on what the worker discovers.

The Paper's Big Idea: A Robot That Learns as It Goes

The authors, Subrat Prasad Panda and his team, propose a new system called Neurosymbolic HRL with Incremental Knowledge (InK). Let's break down the name: "Neurosymbolic" means they are mixing two types of brains. The "neural" part is a flexible, learning brain (like a deep learning neural network) that handles the physical movements. The "symbolic" part is a logical, rule-based brain that handles the planning, like a chess player thinking ahead.

In traditional systems, the logical brain builds a perfect map of the world before the robot starts moving. It's like trying to memorize the entire London Underground map before you leave your house. If a train line is closed or a new station opens, your map is useless until you start over. The authors argue this is inefficient. Instead, their robot uses Incremental Knowledge (InK). It starts with a blank slate or a rough guess. As the "worker" robot tries to move and hits a wall, it tells the "boss," "Hey, there's a wall here!" The boss immediately updates its map and recalculates the best path. It's like having a GPS that updates your route the second you hit a traffic jam, rather than getting stuck waiting for a new map to be printed.

The "Belief World" and the Tree Search

The paper introduces a clever trick to handle uncertainty. Imagine you are in a dark room and you know there is exactly one wall somewhere, but you don't know where. You could guess it's on the left, or the right, or the middle. The robot doesn't just pick one guess; it keeps a "belief set"—a mental list of all the possible worlds where the wall could be.

To make decisions in this fog of uncertainty, the authors developed an algorithm called Belief World Tree Search (BWTS). Imagine a giant tree growing in your mind. The trunk is your current location. Every time you have to choose a direction, the tree branches out. But here's the twist: instead of just guessing one path, BWTS simulates thousands of possible futures at once. It asks, "If the wall is here, what's the best move? If the wall is there, what's the best move?" It then picks the move that works best on average across all those possibilities.

The paper explicitly argues against using standard "random" guessing methods (like some older algorithms that just roll dice to see what happens). The authors found that random guessing in a maze often leads the robot in circles, wasting time. Instead, BWTS uses "strategic rollouts"—it simulates paths using smart, pre-planned strategies (like "always sweep left if you hit a wall") to quickly figure out the best route without getting lost.

What They Found: Speed and Smarts

The team tested their idea in computer simulations of mazes, ranging from simple grids to complex 3D environments with a virtual "ant" robot that has many joints.

Massive Speed Gains: When compared to the old "build the map first" method (called RGL in the paper), the new InK method was incredibly faster at learning. In a "Four Rooms" maze, the old method needed about 2,080 steps to reach the goal for the first time from scratch. The new InK method needed only 64.9 steps. That's roughly 30 to 100 times fewer tries.
Time Savings: The time difference was even starker. The old method took over 96 seconds just to figure out the first path. The new method did it in 0.02 seconds.
The Power of Prior Knowledge: When the robot was given a hint about the world (like "there is a wall somewhere, but I don't know where"), the BWTS algorithm shined. In these cases, it used half the number of samples (tries) compared to the standard planner, though it took a bit more computer time to do the complex math.
Complex Environments: The system worked even on the "Ant-Maze U-Room," a high-dimensional challenge with 29 dimensions of movement. The old method needed around 10,000 steps to build its map, while the new method reached the goal in about 1,507 steps (or even 1,134 steps with the BWTS planner).

What They Didn't Find (and What They Rejected)

The paper is careful to say what doesn't work well in this specific setup. They tested a popular algorithm called BAMCP, which tries to handle uncertainty by assuming every part of the maze is independent (like assuming the wall in the kitchen has nothing to do with the wall in the bedroom). The authors found this approach failed miserably in their maze tests. Because the walls were structurally linked (if there's a wall here, there can't be one there), the independent assumption led to bad decisions and wasted time. BAMCP took 28 to 40 steps on average where the new method took 21 to 23, and it ran much slower.

The authors also note that while their method is faster, the BWTS algorithm is computationally heavy. If you don't have any prior knowledge about the world, the simpler "D*" planner (a standard incremental planner) is actually faster and good enough. You only need the fancy BWTS tree search if you have specific structural hints about the world to exploit.

The Bottom Line

This paper suggests that by mixing a flexible learning brain with a logical planner that updates its map in real-time, robots can learn to navigate complex, unknown worlds much faster than before. They didn't just simulate a robot; they showed that in these specific maze scenarios, the new method consistently outperforms the old "learn everything first" approach, saving massive amounts of time and effort. It's a step toward robots that can explore a new house, learn where the furniture is, and find the kitchen without needing a manual for every single room.

Technical Summary: Neurosymbolic Reasoning with Incremental Knowledge for Sample Efficient Hierarchical Reinforcement Learning

1. Problem Statement

Deep Reinforcement Learning (DRL) agents struggle in environments characterized by sparse rewards and long-horizon reasoning, often suffering from prohibitive sample complexity. While Hierarchical Reinforcement Learning (HRL) mitigates this by decomposing tasks across abstraction levels, standard approaches typically rely on non-incremental knowledge (non-InK) paradigms. In these methods, such as SoRB and RGL, the high-level symbolic planner requires a complete, static abstract world model to be constructed through exhaustive exploration before any goal-directed behavior can commence. This creates a fundamental inefficiency: the agent must explore the entire environment regardless of the specific goal.

Furthermore, in neurosymbolic HRL, a semantic gap often exists between the high-level symbolic planner and the low-level neural controller. The high-level planner assumes certain actions are feasible, but the low-level neural policy (often trained independently or in a different environment) may fail to execute them due to dynamic constraints, stochasticity, or unmodeled obstacles. Existing neurosymbolic approaches lack mechanisms to update the high-level world model based on low-level execution feedback. Conversely, classical incremental knowledge (InK) approaches in robotics (e.g., Active SLAM, D*) update world models during execution but typically assume symbolic components at both levels, failing to address the policy-dependent dynamics of neural low-level controllers.

Finally, when structural prior knowledge exists (e.g., "there is exactly one wall at an unknown location"), current planning algorithms like D* or Bayesian Adaptive MDP solvers (BAMCP) are suboptimal. D* replans based on current observations but ignores the set of possible worlds (belief set) to optimize average-case performance. BAMCP assumes independence between state-action transitions, which fails to capture structural constraints where the location of one obstacle constrains the possibilities of others.

2. Methodology

The authors propose Neurosymbolic HRL with Incremental Knowledge (InK), a framework that integrates symbolic planning with neural control while continuously updating the world model based on execution traces.

2.1 Neurosymbolic HRL with InK

The framework employs a two-level hierarchy:

High-Level (Symbolic): Maintains an updatable abstract world model ( $M$ ) representing the environment as a set of symbolic states and actions. It performs planning using an incremental planner (e.g., D*) to generate subgoals. Crucially, this model is updated in real-time based on feedback from the low-level execution.
Low-Level (Neural): A goal-conditioned neural policy ( $\pi_l$ ) executes continuous motion control to reach the subgoals provided by the high-level. It acts as a sensor; its successes and failures provide the execution traces ( $\rho$ ) necessary to update the high-level model.
Coordination: The high-level planner directs the low-level agent to a subgoal. If the low-level agent fails (e.g., hits an unexpected wall), the monitor detects this, and the high-level model is updated to reflect the new constraint. The planner then replans. This eliminates the need for upfront exhaustive exploration, allowing goal-directed behavior from the very first episode.

2.2 Belief World Tree Search (BWTS)

To address the limitation of standard incremental planners (like D*) which do not exploit structural prior knowledge over a set of possible worlds ( $W_0$ ), the authors introduce Belief World Tree Search (BWTS).

Problem Formulation: The agent operates in a true world $W_{true} \in W_0$ , where $W_0$ is a finite set of possible worlds encoding structural priors (e.g., "one wall exists, location unknown"). The goal is to find a policy $\pi$ that minimizes the average cost over all worlds in $W_0$ .
Tree Structure: BWTS constructs a search tree with two node types:
- Decision Nodes: Represent the agent's choice of action.
- Chance Nodes: Represent the outcome of an action (e.g., whether a path is blocked by a wall or not), splitting the belief set $W$ into subsets ( $W^-$ where the wall exists, $W^+$ where it does not).
Strategic Rollouts: Unlike standard Monte Carlo Tree Search (MCTS) which uses random rollouts, BWTS employs strategic rollouts. It evaluates fixed, deterministic strategies (e.g., "sweep left," "sweep right," "move to goal") across all worlds in the current belief set to estimate node values. This reduces variance and avoids the loops common in stochastic rollouts.
Selection and Expansion: The algorithm uses an Upper Confidence Bound (UCB) style formula to balance exploration and exploitation. It prioritizes expanding branches with larger belief sets, as these require more exploration to resolve uncertainty.
Convergence: Theoretically, BWTS converges to the optimal policy for the InK problem as the number of iterations increases, provided the tree is fully expanded.

3. Key Contributions

Neurosymbolic HRL with InK: The proposal of a hierarchical framework where a symbolic high-level planner maintains an updatable world model guided by a neural low-level controller. This approach bridges the semantic gap by using low-level execution feedback to refine high-level abstractions, enabling sample-efficient learning without exhaustive upfront exploration.
Belief World Tree Search (BWTS): The development of a planning algorithm that optimizes for average-case performance over a set of possible worlds with structural dependencies. BWTS adapts MCTS to handle fully observable but unknown dynamics with structural priors, overcoming the independence assumptions of BAMCP and the lack of belief-set utilization in D*.
Empirical Validation: Demonstration that InK HRL significantly outperforms non-InK baselines (specifically RGL) in sample efficiency across various navigation tasks, including high-dimensional continuous control (Ant-Maze).

4. Experimental Results

The authors evaluated their approach on navigation tasks using Point-Maze environments (Four Rooms, Medium Maze, Hard Maze) and a high-dimensional Ant-Maze U-Room.

InK vs. Non-InK (RGL):
- Sample Efficiency: InK required 30 to 100 times fewer samples than RGL to reach a goal from scratch (no prior knowledge). For example, in the Hard Maze, InK reached the goal in ~209 steps compared to RGL's ~17,456 steps.
- Training Efficiency: Even after RGL completed its extensive training phase (100k+ samples), InK (after reaching just 75 goals to build its knowledge base) remained more efficient, requiring 18% fewer samples and 20x less time per goal.
- High-Dimensional Control: In the Ant-Maze (29 dimensions), InK reached the goal in ~1,500 steps (using D*) or ~1,134 steps (using BWTS), whereas the non-InK baseline required ~10,000 steps to build a full abstract model.
Symbolic Planner Comparison (D vs. BWTS vs. BAMCP):*
- BWTS vs. D:* In synthetic grid worlds with structural priors (e.g., a single horizontal wall), BWTS achieved a lower expected cost (e.g., 15.7% improvement over D* in horizontal wall scenarios) by exploiting the belief set to avoid costly backtracking. However, in complex scenarios without clear structural advantages (e.g., mixed wall types), the runtime overhead of BWTS was significant for marginal gains.
- BWTS vs. BAMCP: BAMCP performed poorly (often >28 steps vs. D*'s ~24 steps) and was unstable due to its reliance on stochastic rollouts and the inability to model structural dependencies (e.g., "if wall at A, no wall at B"). BWTS's strategic rollouts and explicit modeling of structural constraints yielded superior performance.
- Prior Knowledge: When prior knowledge was available (e.g., a set of three known maze types), InK-BWTS halved the sample count compared to InK-D*, though it incurred higher computational runtime during the planning phase.

5. Significance and Claims

The paper claims that Neurosymbolic HRL with InK provides a practical approach to sample-efficient learning in complex, sparse-reward environments. By combining the structural reasoning of symbolic planners with the adaptability of neural controllers, the framework allows agents to act with partial knowledge and refine their decisions as new information is acquired, mirroring human reasoning.

The authors emphasize that:

Sample Efficiency: The approach yields gains exceeding 100,000 environment steps compared to state-of-the-art non-InK methods in Point Maze environments.
Optimality under Uncertainty: BWTS offers a method to plan optimally on average over belief worlds, addressing a gap left by both incremental replanners (which ignore priors) and Bayesian planners (which assume independence).
Versatility: The framework is applicable to both low-dimensional and high-dimensional continuous control problems, provided a goal-conditioned low-level policy can be pre-trained or learned.

The work concludes that while BWTS introduces computational overhead, the trade-off is justified when structural prior knowledge is available, and the InK framework itself offers substantial efficiency gains even without such priors compared to traditional HRL. Future work is suggested to extend InK to manipulation tasks and to unify structural and probabilistic priors into a single algorithm.