Neurosymbolic Reasoning with Incremental Knowledge for Sample Efficient Hierarchical Reinforcement Learning

# Neurosymbolic Reasoning with Incremental Knowledge for Sample Efficient Hierarchical Reinforcement Learning
Source: [https://arxiv.org/html/2608.02993](https://arxiv.org/html/2608.02993)
11institutetext:CCDS, NTU Singapore11email:\{subratpr001@e\.,arvinde@\}ntu\.edu\.sg22institutetext:CNRS@CREATE, Singapore22email:blaise\.genest@cnrsatcreate\.sg33institutetext:IPAL, CNRS, France###### Abstract

\(Flat\) Reinforcement Learning \(RL\) agents face significant challenges in environments with sparse rewards that require long\-horizon reasoning\. A compelling approach to improve sample efficiency is to incorporate knowledge into learning and decision\-making\. In standard Hierarchical RL \(HRL\), knowledge is encoded in a fixed, non\-updatable form, such as architectural choices, and remains unchanged throughout learning\. With fixed HRL, reasoning with incremental knowledge learned during exploration is impractical before sufficient environmental knowledge is acquired, leading to poor sample efficiency\. In this work, we propose neurosymbolic HRL withIncremental Knowledge \(InK\): symbolic high\-level components performsymbolic planning\(e\.g\. usingD∗D^\{\*\}\) on an updatable representation of current InK, while low\-level goal\-conditioned neural modules learn motion primitives through experience using reward shaping\. Experiments on navigation tasks demonstrate that incorporating InK substantially improves sample efficiency\. Additionally, to performoptimalsymbolic planning givenpriorknowledge about the world, we develop Belief World Tree Search\. The code is available at[https://github\.com/CPS\-research\-group/ink\_bwts](https://github.com/CPS-research-group/ink_bwts)\.

## 1Introduction

Deep RL \(DRL\) has shown remarkable success in high\-dimensional control problems, yet in domains requiring long\-horizon planning and sparse rewards, purely end\-to\-end approaches suffer from prohibitive sample complexity\[zhao2024learning,goal\-misgeneralization22\]\. Hierarchical RL \(HRL\) mitigates this by decomposing tasks across abstraction levels\[hrl\_survey21\], with most approaches using neural network \(NN\) policies at both levels\. More recent work explores neurosymbolic approaches\[acharya2023neurosymbolic\], where the high\-level component is symbolic and the low\-level component remains neural\. In these approaches, the symbolic high\-level maintains an abstract world model over which planning is performed, while the neural low\-level executes the resulting subgoals through goal\-conditioned policies\. For instance, methods such as SoRB\[eysenbach2019sorb\]and RGL\[rgl2024\]first learn a full abstract graph over the state space through extensive exploration, after which planning is performed over the learned graph for deployment\. This non\-incremental knowledge \(non\-InK\) paradigm assumes the world model must be fully constructed before any goal\-directed behavior begins, requiring the agent to exhaustively explore the environment upfront, regardless of the actual goal, making these methods fundamentally inefficient\.

In contrast, classical robotics planning often adopts incremental knowledge \(InK\), where the abstract world model is updated during execution, for example from execution traces\[ng2019incremental\]\. A simple example is Active SLAM\[cadena2016slam\], where newly discovered obstacles trigger replanning as the map is incrementally updated\. Algorithms such asD∗D^\{\*\}\(DynamicA∗A^\{\*\}\) replan paths using the current InK, incorporating newly detected obstacles\[stentz1995focussed,stentz1994optimal,koenig2003performance\]\. The closest line of work to HRL arises in Task and Motion Planning \(TAMP\), where motion constraints discovered by the motion planner \(low level\) are incrementally incorporated into task planning \(high level\)\[tamper24,noseworthy2021active\]\. Similarly,\[lyu2019sdrl\]learns a meta\-policy to constrain plan feasibility when composing low\-level policies\. However, these approaches typically assume symbolic components at both high and low levels\.

In neurosymbolic HRL, by contrast, the low\-level controller is typically a neural policy with unknown dynamics, often pretrained independently of the target environment, e\.g\., a policy trained in an obstacle\-free maze deployed in a maze with walls\. This creates a semantic gap between the high\-level abstract model and the low\-level policy: what the high\-level planner assumes feasible may be impossible to execute\. So, high\-level plans can become infeasible at execution due to incomplete knowledge, stochastic effects, or misdetected obstacles\. Such failures highlight the need for InK to update the abstract world model based on execution feedback\. Incorporating InK better reflects human reasoning\[sharma2022map\], where agents act with partial knowledge, update it as new information is acquired, and refine their decisions accordingly, rather than exhaustively exploring the environment upfront\. However, existing non\-incremental neurosymbolic HRL approaches are structurally unable to capture this policy\-dependent world model update, and classical InK approaches assume symbolic components at both levels, leaving the use of InK in neurosymbolic HRL underexplored\.

Furthermore, using InK in HRL enables incorporating structural knowledge into the high\-level abstract world model\. Since knowledge is partial at any time, planning must consider multiple possible belief worlds \(a set of possible abstract world models consistent with the knowledge acquired thus far\) to account for uncertainty\[sharma2022map\]\. While planning under uncertainty is often cast as a Partially Observable MDP \(POMDP\), where the transition model is known but states are hidden, InK differs fundamentally: states are fully observable, but the world dynamics are unknown and discovered incrementally\. BAMDPs address unknown dynamics by reducing to a POMDP over augmented belief states; BAMCP\[bamdp2013\], which adapts POMCP\[pomcp\_nips10\]to this reduction, models uncertainty using Bayesian priors over transition probabilities but assumes independence across states\. However, some structural knowledge cannot be captured under independence assumptions: for instance, knowing that “there is exactly one wall at an unknown location” means that discovering a wall at one location immediately constrains all other locations\. As a result, these approaches cannot effectively exploit such prior structural constraints, and simple incremental replanning algorithms likeD∗D^\{\*\}do not readily incorporate this knowledge\. Although these algorithms provide strong worst\-case performance\[koenig2003performance\], they are not optimal when averaged over belief worlds\.

In this work, we propose neurosymbolic HRL with InK to address these challenges\. At the high level, a symbolic planner maintains an updatable abstract world model, replanning withD∗D^\{\*\}\(it could be any other incremental planner\) as new information arrives from low\-level execution\. At the low level, a goal\-conditioned neural policy handles continuous motion control and acts as a sensor: its successes and failures directly inform abstract world model updates\. This tight coordination eliminates the costly upfront exploration phase of non\-InK methods, enabling goal\-directed behavior from the very first episode\. To further exploit structural prior knowledge over possible worlds, we introduce Belief World Tree Search \(BWTS\), which adapts MCTS\[browne2012survey\]to plan optimally on average over all worlds consistent with the structural priors, addressing the fundamental limitations of both incremental planners likeD∗D^\{\*\}and prior\-based planners such as BAMCP in the InK setting\.

Our Main Contributions:

- •We propose a neurosymbolic HRL for continuous control problems, incorporating structural InK through an updatable symbolic representation\.
- •We develop the BWTS algorithm converging towards anoptimalpolicy for unknown environments among a set of possible worlds capturingpriorstructural knowledge\.
- •We empirically demonstrate, using navigation task as a case study, that InK HRL outperforms non\-InK HRL in sample efficiency\.

## 2Related Work

Hierarchical RL \(HRL\)\.End\-to\-end flat DRL has been developed for long\-horizon reasoning using memory, auxiliary losses, or reward shaping\[mirowski2017learning,zhu2017target,zhao2024learning\]\. These techniques can become inefficient for complex tasks\[nachum2020why\]\. HRL mitigates this by structuring policies across abstraction levels, improving exploration and scalability in sparse\-reward settings\[hutsebaut2022hierarchical\]\. Foundational options and feudal frameworks introduce temporally extended actions\[sutton1999between\]\. Goal\-conditioned HRL refines this by letting high\-level policies set subgoals\[nasiriany2019planning,nachum2018data,levy2017learning,lei2025goalconditioned\]\. However, most HRL approaches lack explicit symbolic knowledge representations\.

Graph Neurosymbolic HRL\.In graph\-based methods such as SoRB\[eysenbach2019sorb\], the high\-level is a graph on which planning is done and low\-level is a NN\. Similar hierarchical formulations can be found in landmark\-guided HRL\[huang2019mapping,kim2021landmarkguided\], world graphs\[shang2020learning,savinov2018semiparametric\], abstract/refinement of world model with AI2 tool\[zadem2024reconciling\], state\-space partitioning\[shah2024hierarchical\], probabilistic road maps\[prm\_rl,cprm\_rl\], PAHRL\[gieselmann2021planning\], RL\-RRT\[rrt\-rl\], and RGL\[rgl2024\]\. It typically follows a non\-InK paradigm in which a complete model must be acquired before reasoning\.

Incremental Knowledge\.The overarching idea of InK appears in classical symbolic planning, where it is used to refine domain definitions or augment them with constraints derived from execution traces\[ng2019incremental,tamper24,noseworthy2021active\]\. In this work, we apply a similar idea to HRL to improve sample efficiency\. In the RL setting, incremental learning\[khetarpal2022towards,meng2025preserving\]has been used to learn parametric transition functions; however, incorporating explicit structural knowledge requires an updatable symbolic representation, which is the focus of this work\. BAMCP\[bamdp2013\]proposes to incorporate such knowledge incrementally in symbolic domain, but assumes independence between probability distributions of different state\-action pairs: an assumption that does not hold in our setting, as we demonstrate experimentally\.

Other Neurosymbolic Approaches\.Neural and symbolic components can be combined in multiple ways\. One common approach uses symbolic planning at a high level to guide exploration and direct low\-level policy learning\[lyu2019sdrl,kokel2021deep,mayr2022combining\]\[garrett2020pddlstream,guan2022leveraging,prakash2022towards\]\. Closely related,\[mao2023pdsketch\]learns an abstract world model from demonstrations, but assumes a symbolic low\-level policy \(geometric motion planning\)\. In contrast, our approach incrementally learns the abstract world model from real execution traces given a neural low\-level policy, making the abstract world model policy\-dependent and reducing the semantic gap between high\-level abstractions and actual low\-level behavior\.

Monte Carlo Tree Search\.Monte Carlo Tree Search \(MCTS\) is a dominant paradigm forplanningin graphs, combining stochastic rollouts with tree expansion to approximate values without requiring a full transition model of the environment\[coulom2006efficient,kocsis2006bandit\], with success in complex domains, e\.g\. \(2 player\) games\[browne2012survey\]\. POMCP\[pomcp\_nips10\]solves POMDPs where the transition model is known but states are partially observable, using particle filtering to maintain beliefs over hidden states\. BAMCP\[bamdp2013\]extends this to unknown transitions by casting the problem as a BAMDP, which reduces to a POMDP over an augmented state space encoding beliefs over transition parameters, and then applies POMCP\-style tree search; however, this reduction requires independence across state\-action pairs, preventing it from capturing structural constraints \(e\.g\., “exactly one wall at an unknown location”\)\. In contrast, BWTS addresses a fully observable but unknown setting: it maintains beliefs over structured sets of possible worlds without independence assumptions and uses strategic rather than probabilistic rollouts\.

## 3Setting and Methodology

### 3\.1The Incremental Knowledge Setting

We introduce first the \(structural\)Incremental Knowledge \(InK\)setting: the agent evolves in a worldWtrueW\_\{\\text\{true\}\}that it does not know\. To model everything that it believes could happen, we consider a set𝒲0\\mathcal\{W\}\_\{0\}of possible worlds, withWtrue∈𝒲0W\_\{\\text\{true\}\}\\in\\mathcal\{W\}\_\{0\}: the agent knows that the possible outcomes of an actionaaafter observationsρ\\rhoare exactly those compatible with some worldW∈𝒲0W\\in\\mathcal\{W\}\_\{0\}\. This set𝒲0\\mathcal\{W\}\_\{0\}also serves to define the average reward over all the possible choices ofW∈𝒲0W\\in\\mathcal\{W\}\_\{0\}\. Last, the choice of𝒲0\\mathcal\{W\}\_\{0\}encodes any \(structural\)prior knowledgeon the world\.

A Belief World Process is a tupleℳ=\(𝒲0,𝒮,\\mathcal\{M\}=\(\\mathcal\{W\}\_\{0\},\\mathcal\{S\},𝒜,\(𝒯W\)W∈𝒲0,C\)\\mathcal\{A\},\(\\mathcal\{T\}\_\{W\}\)\_\{W\\in\\mathcal\{W\}\_\{0\}\},C\), where𝒲0\\mathcal\{W\}\_\{0\}is a finite set of all possible worlds,𝒮⊆ℝn\\mathcal\{S\}\\subseteq\\mathbb\{R\}^\{n\}is the commonstate spaceof all the worlds, and𝒜\\mathcal\{A\}the commonaction spaceof all the worlds\. Thetransition dynamicsdepends upon the worlds: givenW∈𝒲0W\\in\\mathcal\{W\}\_\{0\}, we have𝒯W:𝒮×𝒜×𝒮→\[0,1\]\\mathcal\{T\}\_\{W\}:\\mathcal\{S\}\\times\\mathcal\{A\}\\times\\mathcal\{S\}\\rightarrow\[0,1\], denoting the probability to reach stateS′S^\{\\prime\}after trying actionaafrom stateSSin worldWW\. It is deterministic if for allS,aS,a, we have𝒯W​\(S,a,S′\)=1\\mathcal\{T\}\_\{W\}\(S,a,S^\{\\prime\}\)=1for a unique stateS′S^\{\\prime\}, and 0 for otherS′′S^\{\\prime\\prime\}\. Thecost functionisC:𝒮×𝒜→ℝ≥0C:\\mathcal\{S\}\\times\\mathcal\{A\}\\rightarrow\\mathbb\{R\}^\{\\geq 0\}, where the costC​\(S,a\)=0C\(S,a\)=0only ifSSis in the goal regionG⊂𝒮G\\subset\\mathcal\{S\}, whereGGis an attractor w\.r\.t\.𝒯W\\mathcal\{T\}\_\{W\}for allWW\(fromGG, all forthcoming costs are0\)\. Some information on the real worldWtrueW\_\{\\text\{true\}\}can be extracted from the observed historyρ=S0,…,Sn−1\\rho=S\_\{0\},\\ldots,S\_\{n\-1\}: if this sequence has probability0in a worldWW, thenWtrue≠WW\_\{\\text\{true\}\}\\neq W\.

A policyπ\\pichooses actionana\_\{n\}from historyρ=S0,a1,…,Sn−1\\rho=S\_\{0\},a\_\{1\},\\ldots,S\_\{n\-1\}, that isπ​\(ρ\)=an\\pi\(\\rho\)=a\_\{n\}\. We denote byC​\(π,W\)∈ℝ≥0∪\{\+∞\}C\(\\pi,W\)\\in\\mathbb\{R\}^\{\\geq 0\}\\cup\\\{\+\\infty\\\}the cumulative cost to reach the goal in worldW∈𝒲0W\\in\\mathcal\{W\}\_\{0\}when policyπ\\piis used\. We then denoteC​\(π\)C\(\\pi\)the average ofC​\(π,W\)C\(\\pi,W\)over all the worldsW∈𝒲0W\\in\\mathcal\{W\}\_\{0\}\. We denote byC∗C^\{\*\}the optimal cost in𝒲0\{\\mathcal\{W\}\}\_\{0\}:

C∗=infπC​\(π\)=infπ∑W∈𝒲0\[C​\(π,W\)\]\|𝒲0\|C^\{\*\}=\\inf\_\{\\pi\}C\(\\pi\)=\\inf\_\{\\pi\}\\;\\frac\{\\sum\_\{W\\in\\mathcal\{W\}\_\{0\}\}\\\!\\left\[C\(\\pi,W\)\\right\]\}\{\|\\mathcal\{W\}\_\{0\}\|\}\(1\)TheInK problemconsists in computing a strategyπ\\piso as to minimizeC​\(π\)C\(\\pi\)\.

### 3\.2A Neurosymbolic Hierarchical RL for InK

Solving the RL problem end\-to\-end is particularly challenging in sparse\-reward settings\. We therefore adopt a hierarchical decomposition with symbolic planning directing continuous control\. At a high level, the state space𝒮\\mathcal\{S\}and action space𝒜\\mathcal\{A\}are abstracted into a finite set of symbolic \(discrete\) statesVV\(vertices in the discrete state graph\) and a finite set of symbolic actionsAA, respectively\. Planning is performed in this abstracted space, where the high\-level model maintains a world modelMM, which is an updatable representation that uses InK\. We execute the loop, as also illustrated in Fig\.[1](https://arxiv.org/html/2608.02993#S3.F1):

1. 1\.Symbolic planning is performed overMMusingD∗D^\{\*\}from current configurationssto reachGGin an optimal way\. Letggbe the first intermediate goal from the symbolic plan\.
2. 2\.Direct the low\-level to achieve the goalgg\.
3. 3\.Upon receiving new information from the low\-level monitor, update \(the InK in\)MM\.

![Refer to caption](https://arxiv.org/html/2608.02993v1/x1.png)Figure 1:A Neurosymbolic HRL for InKAt the low level, a goal\-conditioned policyπl\\pi\_\{l\}considers the current states∈𝒮s\\in\\mathcal\{S\}and the goalggfrom the high level, and inductively executes a sequenceρ\\rhowith low\-level actionsπl​\(s,g\)\\pi\_\{l\}\(s,g\)in the environment untilggis reached or fails\. A monitorm​o​nmonmonitorsρ\\rhoto detect environmental information\. Upon returning, the low\-level reportsssandm​o​n​\(ρ\)mon\(\\rho\)to the high\-level\.

##### Coordination between levels\.

The high\-level and low\-level components interact through a tight coordination mechanism\. The high\-level maintains the symbolic representationMM, for instance, a set of predicates, as well as the set of possible high\-level abstract actionsAA\. Each action is associated with a set of possible outcomes, and for each outcome we have the cost\. At first, all outcomes are believed possible, but from real execution traces, it can learn some abstract actions are not possible\. Symbolic planning is performed to reachGG, either by taking an optimistic semantic \(the best outcome will happen\), or using stochastic models taking into account the probabilities\. In this work, we useD∗D^\{\*\}as the incremental planner for its simplicity in analysis\.

### 3\.3A∗A^\{\*\}and DynamicA∗A^\{\*\}\(D∗D^\{\*\}\)

A∗A^\{\*\}performs heuristic\-guided search over the symbolic graph defined by the generative actions, expanding only the most promising nodes without constructing the full graph\.DynamicA∗A^\{\*\}\(D∗D^\{\*\}\)\[stentz1995focussed,stentz1994optimal\]extendsA∗A^\{\*\}to the InK setting: it plans using the current knowledge, and upon action failure, updates the graph and replans\. Originally developed for discrete navigation,D∗D^\{\*\}is known to be close to optimalin the worst case\(by a factor at mostO​\(\|V\|\)O\(\\sqrt\{\|V\|\}\), where\|V\|\|V\|is the number of graph vertices or abstract states\)\[koenig2003performance\]\. However, no theoretical guarantees existon average over all possible worlds\. Critically,D∗D^\{\*\}does not consider the belief set𝒲0\\mathcal\{W\}\_\{0\}, making it unable to exploit prior knowledge\. We address this limitation in Section[4](https://arxiv.org/html/2608.02993#S4)with an algorithm that isoptimal on averageover𝒲0\\mathcal\{W\}\_\{0\}\.

## 4Belief World Tree search \(BWTS\)

As the incremental plannerD∗D^\{\*\}does not consider the belief set𝒲0\\mathcal\{W\}\_\{0\}, it cannot exploit structural prior knowledge, making it suboptimal on average over possible worlds\. We propose BWTS, an algorithm that isoptimal on averageover𝒲0\\mathcal\{W\}\_\{0\}, particularly effective when structural prior knowledge is available\. We use maze navigation as a running example to illustrate BWTS throughout this section\. BWTS is developed to provideoptimalsolutions fordiscrete \(symbolic\) graphs\(V,A,τu,C\)\(V,A,\\tau\_\{u\},C\), whereVVis the set of vertices \(representing discrete abstract states\),AAis the finite set of actions,τu:V×A→V\\tau\_\{u\}:V\\times A\\to Vis the unobstructed transition function, andC​\(v,a\)C\(v,a\)is the cost of taking actionaafrom vertexvv, considering the set𝒲0\{\\mathcal\{W\}\}\_\{0\}of possible worlds\. In each worldW∈𝒲0W\\in\\mathcal\{W\}\_\{0\}, actionaafromvveither reachesv′=τu​\(v,a\)v^\{\\prime\}=\\tau\_\{u\}\(v,a\)if unobstructed, or loops back tovvif a wall blocksv′v^\{\\prime\}\. BWTS computes a policyπ\\pi, mapping historyρ\\rhoto actionπ​\(ρ\)=a\\pi\(\\rho\)=a, minimizing the cumulative cost averaged over worldsW∈𝒲0W\\in\\mathcal\{W\}\_\{0\}\(Eq\. \([1](https://arxiv.org/html/2608.02993#S3.E1)\)\)\. We writeva=τu​\(v,a\)v^\{a\}=\\tau\_\{u\}\(v,a\); e\.g\.,\(2,3\)right=\(3,3\)\(2,3\)^\{\\text\{right\}\}=\(3,3\)\.

BWTS will maintain a belief set𝒲ρ⊆𝒲0\\mathcal\{W\}\_\{\\rho\}\\subseteq\\mathcal\{W\}\_\{0\}of worlds in𝒲0\\mathcal\{W\}\_\{0\}compatible with historyρ\\rhoending invv\. The belief set after historyρ′=ρ,a,v′\\rho^\{\\prime\}=\\rho,a,v^\{\\prime\}is𝒲ρ′=𝒲ρ−=\{W∈𝒲ρ∣there is a wall in position​va\}\\mathcal\{W\}\_\{\\rho^\{\\prime\}\}=\\mathcal\{W\}\_\{\\rho\}^\{\-\}=\\\{W\\in\\mathcal\{W\}\_\{\\rho\}\\mid\\text\{ there is a wall in position \}v^\{a\}\\\}ifv′=vv^\{\\prime\}=v; otherwise𝒲ρ′=𝒲ρ\+=\{W∈𝒲ρ∣\\mathcal\{W\}\_\{\\rho^\{\\prime\}\}=\\mathcal\{W\}\_\{\\rho\}^\{\+\}=\\\{W\\in\\mathcal\{W\}\_\{\\rho\}\\midthere is no wall in positionva=v′\}v^\{a\}=v^\{\\prime\}\\\}\. That is,𝒲ρ=𝒲ρ\+⊔𝒲ρ−\\mathcal\{W\}\_\{\\rho\}=\\mathcal\{W\}\_\{\\rho\}^\{\+\}\\sqcup\\mathcal\{W\}\_\{\\rho\}^\{\-\}is partitioned into two sets\.

![Refer to caption](https://arxiv.org/html/2608.02993v1/x2.png)\(a\)BWTS Nodes
![Refer to caption](https://arxiv.org/html/2608.02993v1/x3.png)\(b\)BWTS Learning stages

Figure 2:BWTS node types in \(a\) and learning stages in \(b\): 1\. Selection \(tree policy\)→\\to2\. Expansion \(unvisited nodes\)→\\to3\. Rollout \(value estimate\)→\\to4\. Backpropagation\. Repeat these four stages over iterations to grow the tree\.### 4\.1The complete BWTS tree

We now describe BWTS trees\. The root is\(v0,𝒲0\)\(v\_\{0\},\\mathcal\{W\}\_\{0\}\), withv0v\_\{0\}the initial state and𝒲0\\mathcal\{W\}\_\{0\}the set of all possible worlds\. Nodes are either decision nodes or chance nodes as illustrated in Fig\.[2\(a\)](https://arxiv.org/html/2608.02993#S4.F2.sf1)\.*Decision nodes*represent choices of actions and are denoted by\(v,𝒲\)\(v,\\mathcal\{W\}\)\. A decision node\(v,𝒲\)\(v,\\mathcal\{W\}\)has\|A\|\|A\|\(chance nodes\) children\(v,a,𝒲\)\(v,a,\\mathcal\{W\}\), one per actiona∈Aa\\in A\. A chance node\(v,a,𝒲\)\(v,a,\\mathcal\{W\}\)has two \(decision nodes\) children\(v,𝒲−\)\(v,\\mathcal\{W\}^\{\-\}\)and\(v′,𝒲\+\)\(v^\{\\prime\},\\mathcal\{W\}^\{\+\}\)representing whether the unblocked successorvav^\{a\}fromvvplayingaais a wall or not\. Decision nodes\(v,𝒲\)\(v,\\mathcal\{W\}\)where\|𝒲\|=1\|\\mathcal\{W\}\|=1, i\.e\.𝒲=\{W\}\\mathcal\{W\}=\\\{W\\\}for someWW, have no successor\. The world is fully known to beWW, and a shortest\-path algorithm \(e\.g\.,A∗A^\{\*\}or Dijkstra\) can be run onWW\. Notice that the path from the root to a node\(vn,𝒲n\)\(v\_\{n\},\\mathcal\{W\}\_\{n\}\)of the tree describes the historyρ=v0,a1,…,vn\\rho=v\_\{0\},a\_\{1\},\\ldots,v\_\{n\}, and we have𝒲n=𝒲ρ\\mathcal\{W\}\_\{n\}=\\mathcal\{W\}\_\{\\rho\}\. If the BWTS iscomplete, that is unfolded until all the leaves\(v,𝒲\)\(v,\\mathcal\{W\}\)are associated with belief𝒲\\mathcal\{W\}with a unique world, then we can associate each node with its cost, from the leaves to the root: The costC​\(v,\{W\}\)C\(v,\\\{W\\\}\)of a leaf\(v,\{W\}\)\(v,\\\{W\\\}\)is the cost of the shortest path inWWto the goal\.

Then we inductively compute bottom up: for a chance node\(v,a,𝒲\)\(v,a,\\mathcal\{W\}\)with two children\(v1,𝒲1\)\(v\_\{1\},\\mathcal\{W\}\_\{1\}\),\(v2,𝒲2\)\(v\_\{2\},\\mathcal\{W\}\_\{2\}\), its cost is:

C​\(v,a,𝒲\)=\|𝒲1\|​C​\(v1,𝒲1\)\+\|𝒲2\|​C​\(v2,𝒲2\)\|𝒲1\|\+\|𝒲2\|=\|𝒲\|C\(v,a,\\mathcal\{W\}\)=\\frac\{\|\\mathcal\{W\}\_\{1\}\|C\(v\_\{1\},\\mathcal\{W\}\_\{1\}\)\+\|\\mathcal\{W\}\_\{2\}\|C\(v\_\{2\},\\mathcal\{W\}\_\{2\}\)\}\{\|\\mathcal\{W\}\_\{1\}\|\+\|\\mathcal\{W\}\_\{2\}\|=\|\\mathcal\{W\}\|\}\(2\)
For a decision node\(v,𝒲\)\(v,\\mathcal\{W\}\), we define:

C​\(v,𝒲\)=mina∈A⁡C​\(v,a\)\+C​\(v,a,𝒲\)C\(v,\\mathcal\{W\}\)=\\min\_\{a\\in A\}C\(v,a\)\+C\(v,a,\\mathcal\{W\}\)\(3\)
###### Theorem 4\.1

The policyπ∗\\pi^\{\*\}choosing in\(v,𝒲\)\(v,\\mathcal\{W\}\)actionaaminimizingC​\(v,a,𝒲\)C\(v,a,\\mathcal\{W\}\)has average costC​\(π∗\)=C​\(v0,𝒲0\)C\(\\pi^\{\*\}\)=C\(v\_\{0\},\\mathcal\{W\}\_\{0\}\)\. Further,C​\(π∗\)=C∗C\(\\pi^\{\*\}\)=C^\{\*\}the optimal cost of the InK problem\.

Evaluation of the size of the full BWTS tree:Assuming𝒲=𝒲\+⊔𝒲−\\mathcal\{W\}=\\mathcal\{W\}^\{\+\}\\sqcup\\mathcal\{W\}^\{\-\}always partitions the belief set𝒲\\mathcal\{W\}into two sets of the same size, the number of nodes of the full BWTS tree is at least\|𝒲0\|×\|A\|log⁡\|𝒲0\|\>108\|\\mathcal\{W\}\_\{0\}\|\\times\|A\|^\{\\log\{\|\\mathcal\{W\}\_\{0\}\|\}\}\>10^\{8\}for\|𝒲0\|=128\|\\mathcal\{W\}\_\{0\}\|=128and\|A\|=8\|A\|=8\. The proofs of Theorem[4\.1](https://arxiv.org/html/2608.02993#S4.Thmtheorem1)\(by induction over the size of\|𝒲0\|\|\\mathcal\{W\}\_\{0\}\|\) and the evaluation can be found in the supplementary material\.

### 4\.2The BWTS algorithm

Constructing the complete BWTS tree becomes intractable as the size of\|𝒲0\|\|\\mathcal\{W\}\_\{0\}\|grows \(there is one node per history till a leaf\)\. With good heuristics selecting promising actions, we can open only the most promising actions, and this will be sufficient to obtain an efficient policyπ\\pi\. Similar to Monte\-Carlo Tree Search \(MCTS\), we approximate the cost of nodes without expanding them, and only expand the most promising ones, as illustrated in Fig\.[2](https://arxiv.org/html/2608.02993#S4.F2)\. Unlike MCTS, which relies on random rollouts to evaluate the value of a node:

Strategic rollouts:Definekkfixed strategiesσ1,…,σk\\sigma\_\{1\},\\ldots,\\sigma\_\{k\}to reach the goal from any statevvand any belief set𝒲\\mathcal\{W\}\.D∗D^\{\*\}is one such strategy\. Variants can be used, like fixing the direction to favor when an obstacle is encountered, or targeting a particular sequence of intermediate subgoals\. To evaluate any decision node\(v,𝒲\)\(v,\\mathcal\{W\}\), we evaluate the costC​\(σi,v,W\)C\(\\sigma\_\{i\},v,W\)of every strategyσi\\sigma\_\{i\},i≤ki\\leq kfromvvin every worldW∈𝒲W\\in\\mathcal\{W\}\. The valueQ​\(v,𝒲\)Q\(v,\\mathcal\{W\}\)we associate with\(v,𝒲\)\(v,\\mathcal\{W\}\)is then:

Q​\(v,𝒲\)=mini≤k⁡∑W∈𝒲C​\(σi,v,W\)\|𝒲\|≥0Q\(v,\\mathcal\{W\}\)=\\min\_\{i\\leq k\}\\frac\{\\sum\_\{W\\in\\mathcal\{W\}\}C\(\\sigma\_\{i\},v,W\)\}\{\|\\mathcal\{W\}\|\}\\geq 0\(4\)
We evaluateQ​\(v,a,𝒲\)Q\(v,a,\\mathcal\{W\}\)for chance nodes by computation from the valuation of its two \(decision nodes\) children\. Strategic rollouts have two advantages over standard Monte\-Carlo rollouts: first, they limit the occurrence of loops around states\. Also, rather than the average value of random rollouts, we consider a min over strategies of the average over worlds, closely matching the cost to evaluate, though we evaluate only a few strategies instead of the full BWTS\.

Exploration bonus for chance nodes:Notice that forkkfixed strategies,Q​\(v,a,𝒲\)Q\(v,a,\\mathcal\{W\}\)is a fixed evaluation of the cost of a node\(v,a,𝒲\)\(v,a,\\mathcal\{W\}\)\. Hence it is important to provide a way to not starve some nodes\(v,a,𝒲\)\(v,a,\\mathcal\{W\}\)from being explored, because although their valuation seems less promising than a node\(v,a′,𝒲\)\(v,a^\{\\prime\},\\mathcal\{W\}\), they may ultimately lead to the optimal strategy\. This is done by giving an advantage to chance nodes\(v,a,𝒲\)\(v,a,\\mathcal\{W\}\)whose visit countN​\(v,a,𝒲\)N\(v,a,\\mathcal\{W\}\)— the number of times the node has been selected during search — is much smaller than the visit countN​\(v,𝒲\)N\(v,\\mathcal\{W\}\)of its parent decision node\. We use the same formula as in MCTS based on Lower Confidence Bound \(LCB\) rule\[browne2012survey\]\. First, we fix an exploration hyperparameterce\>0c\_\{e\}\>0to control the exploration–exploitation trade\-off: largercec\_\{e\}encourages more exploration \(potentially better solutions\) at the cost of additional compute\. The actionα​\(v,𝒲\)\\alpha\(v,\\mathcal\{W\}\)that will be explored by the BWTS algorithm at a decision node\(v,𝒲\)\(v,\\mathcal\{W\}\)will be

α​\(v,𝒲\)∈arg⁡mina∈A⁡\(Q​\(v,a,𝒲\)−ce​ln⁡N​\(v,𝒲\)N​\(v,a,𝒲\)\)\.\\alpha\(v,\\mathcal\{W\}\)\\;\\in\\;\\arg\\min\_\{a\\in A\}\\Big\(Q\(v,a,\\mathcal\{W\}\)\\;\-\\;c\_\{e\}\\sqrt\{\\tfrac\{\\ln N\(v,\\mathcal\{W\}\)\}\{N\(v,a,\\mathcal\{W\}\)\}\}\\Big\)\.\(5\)
Selection of decision nodes:At a chance node\(v,a,𝒲\)\(v,a,\\mathcal\{W\}\), both decision\-node children\(v,𝒲−\)\(v,\\mathcal\{W\}^\{\-\}\)and\(v′,𝒲\+\)\(v^\{\\prime\},\\mathcal\{W\}^\{\+\}\)should be opened to have a value to node\(v,a,𝒲\)\(v,a,\\mathcal\{W\}\)\. However, we know that the subtree with more worlds in the belief set𝒲−\\mathcal\{W\}^\{\-\}or𝒲\+\\mathcal\{W\}^\{\+\}will need more explorations to find an efficient strategy than the one with fewer worlds, because evaluatingonecomplete strategy in BWTS requires opening of a number of branches linear in the number of worlds in the belief set\. We have𝒲=𝒲−⊔𝒲\+\\mathcal\{W\}=\\mathcal\{W\}^\{\-\}\\sqcup\\mathcal\{W\}^\{\+\}\. We write\(T,𝒳\)\(T,\\mathcal\{X\}\)for either of the two children of\(v,a,𝒲\)\(v,a,\\mathcal\{W\}\)\. From\(v,a,𝒲\)\(v,a,\\mathcal\{W\}\), the BWTS algorithm will explore\(T,𝒳\)\(T,\\mathcal\{X\}\)following the selection rule:

ω​\(v,a,𝒲\)\\displaystyle\\omega\(v,a,\\mathcal\{W\}\)=arg⁡min\(T,𝒳\)⁡\(N​\(T,𝒳\)​\|𝒲∖𝒳\|\)\.\\displaystyle=\\arg\\min\_\{\(T,\\mathcal\{X\}\)\}\\Big\(N\(T,\\mathcal\{X\}\)\|\\mathcal\{W\}\\setminus\\mathcal\{X\}\|\\Big\)\.\(6\)
Stages of BWTS Construction:Every iteration of the BWTS starts at the root, which is a decision node\(v0,𝒲0\)\(v\_\{0\},\\mathcal\{W\}\_\{0\}\)\. We adopt in Algorithm[2](https://arxiv.org/html/2608.02993#alg2)the standard MCTS\[browne2012survey\]stages \(selection, expansion, rollout, and backpropagation\) with modifications to 3\. Rollouts \(see above\), and to 4\. Backpropagation \(see below\)\.

Algorithm 1Belief World Tree search1:root decision node

\(v0,𝒲0\)\(v\_\{0\},\\mathcal\{W\}\_\{0\}\), total number of iterations

II, exploration constant

cec\_\{e\}, rollout policies

\(σi\)1≤k\(\\sigma\_\{i\}\)\_\{1\\leq k\}\.

2:

r​o​o​t←\(v0,𝒲0\)root\\leftarrow\(v\_\{0\},\\mathcal\{W\}\_\{0\}\)
3:for

i∈\{0,…,I\}i\\in\\\{0,\\dots,I\\\}do⊳\\trianglerightiterateIItimes

4:\#1\. Selection

5:

u←r​o​o​tu\\leftarrow root
6:while

uuis fully expandeddo

7:if

uuis a decision nodethen

8:

a←α​\(u\)a\\leftarrow\\alpha\(u\);

u←Child​\(u,a\)u\\leftarrow\\text\{Child\}\(u,a\)⊳\\trianglerightEq\.[5](https://arxiv.org/html/2608.02993#S4.E5)

9:else

10:

u←ω​\(u\)u\\leftarrow\\omega\(u\)⊳\\trianglerightEq\.[6](https://arxiv.org/html/2608.02993#S4.E6)

11:

\(v,𝒲\)←u\(v,\\mathcal\{W\}\)\\leftarrow u
12:\#2\. Expansion

13:randomly sample a child

\(v,a,𝒲\)\(v,a,\\mathcal\{W\}\)that does not exist in the tree and attach it to the tree

14:attach

\(v,𝒲−\)\(v,\\mathcal\{W\}^\{\-\}\)and

\(v′,𝒲\+\)\(v^\{\\prime\},\\mathcal\{W\}^\{\+\}\)to the tree

15:\#3\. Rollouts

16:Compute

Q​\(v′,𝒲\+\)Q\(v^\{\\prime\},\\mathcal\{W\}^\{\+\}\)and

Q​\(v,𝒲−\)Q\(v,\\mathcal\{W\}^\{\-\}\)⊳\\trianglerightEq\.[4](https://arxiv.org/html/2608.02993#S4.E4)

17:\#4\. Backpropagation

18:

v←\(v,𝒲\)v\\leftarrow\(v,\\mathcal\{W\}\)
19:while

v≠r​o​o​tv\\neq rootdo

20:update

Q​\(v\)Q\(v\)⊳\\trianglerightEq\.[0\.B](https://arxiv.org/html/2608.02993#Pt0.A2.Ex4)and[0\.B](https://arxiv.org/html/2608.02993#Pt0.A2.Ex5)

21:

v←p​a​r​e​n​t​\(v\)v\\leftarrow parent\(v\)return

r​o​o​troot

*4\. Backpropagation\.*After computing the evaluationsQ​\(v′,𝒲\+\)Q\(v^\{\\prime\},\\mathcal\{W\}^\{\+\}\)andQ​\(v,𝒲−\)Q\(v,\\mathcal\{W\}^\{\-\}\), we backtrack inductively from the bottom to the root and update the values of ancestor nodes\. For chance nodes\(v,a,𝒲\)\(v,a,\\mathcal\{W\}\)with children\(v,𝒲−\),\(v′,𝒲\+\)\(v,\\mathcal\{W\}^\{\-\}\),\(v^\{\\prime\},\\mathcal\{W\}^\{\+\}\), we set as in Eq\. \([2](https://arxiv.org/html/2608.02993#S4.E2)\):

Q​\(v,a,𝒲\)=\|𝒲1\|​Q​\(v1,𝒲1\)\+\|𝒲2\|​Q​\(v2,𝒲2\)\|𝒲1\|\+\|𝒲2\|=\|𝒲\|Q\(v,a,\\mathcal\{W\}\)=\\frac\{\|\\mathcal\{W\}\_\{1\}\|Q\(v\_\{1\},\\mathcal\{W\}\_\{1\}\)\+\|\\mathcal\{W\}\_\{2\}\|Q\(v\_\{2\},\\mathcal\{W\}\_\{2\}\)\}\{\|\\mathcal\{W\}\_\{1\}\|\+\|\\mathcal\{W\}\_\{2\}\|=\|\\mathcal\{W\}\|\}\(7\)
For decision nodes\(v,𝒲\)\(v,\\mathcal\{W\}\), we set as in Eq\. \([3](https://arxiv.org/html/2608.02993#S4.E3)\):

Q​\(v,𝒲\)←mina∈A⁡\(C​\(v,a\)\+Q​\(v,a,𝒲\)\)Q\(v,\\mathcal\{W\}\)\\;\\leftarrow\\;\\min\_\{a\\in A\}\(C\(v,a\)\\;\+\\;Q\(v,a,\\mathcal\{W\}\)\)\(8\)
*BWTS PolicyπI\\pi\_\{I\}*:Afteriiiterations, the strategyπi\\pi\_\{i\}is the following: at each decision node, pick the action with the smallestQ​\(v,a,𝒲\)Q\(v,a,\\mathcal\{W\}\)\. We show in Theorem[0\.A\.2](https://arxiv.org/html/2608.02993#Pt0.A1.Thmtheorem2)thatπi\\pi\_\{i\}converges to an optimal policy for the \(symbolic\) InK problem\.

###### Theorem 4\.2\(Convergence of BWTS to Full\-Tree\)

Let\(πi\)i∈ℕ\(\\pi\_\{i\}\)\_\{i\\in\\mathbb\{N\}\}be the sequence of policies produced by the BWTS algorithm\. Then the sequenceC​\(πi\)i∈ℕC\(\\pi\_\{i\}\)\_\{i\\in\\mathbb\{N\}\}converges towardsC∗C^\{\*\}, the optimal cost of the \(discrete symbolic\) InK problem\.

The proof can be found in the supplementary materials\. Sketch: LetB​W​T​SiBWTS\_\{i\}be the tree afteriiiterations of Algorithm[2](https://arxiv.org/html/2608.02993#alg2)for alli∈ℕi\\in\\mathbb\{N\}\. We prove that there exists a numberIIof iterations after whichB​W​T​Si,i\>IBWTS\_\{i\},i\>Iis the complete BWTS tree\. Henceforth,C​\(πi\)=C∗,i\>IC\(\\pi\_\{i\}\)=C^\{\*\},i\>I, following Theorem[4\.1](https://arxiv.org/html/2608.02993#S4.Thmtheorem1)\. Compared to the full BWTS tree, the smallest number of iterations \(resp\. nodes\) isI0=\|A\|×\|𝒲0\|I\_\{0\}=\|A\|\\times\|\\mathcal\{W\}\_\{0\}\|\(resp\. min\_nodes=3​I0=3I\_\{0\}\), to reach the leaves \(and thus evaluate the cost\) on all the \(uncontrollable\) chance branches\. Branches from decision nodes are only sparsely explored\. The algorithm needsO​\(I×k×\|V\|×\|𝒲0\|\)O\(I\\times k\\times\|V\|\\times\|\\mathcal\{W\}\_\{0\}\|\)operations to computeπI\\pi\_\{I\}\.

## 5Experimental Evaluation

In this section, we outline the experimental setup and evaluate the performance of InK in comparison to the non\-InK approach\. All experiments were implemented in Python/PyTorch and run on Ubuntu 20\.04\.6 LTS on a machine with 8P\+12E CPU cores \(Intel i7\-14700KF\) and 64 GB of RAM\. Source code is available at[https://github\.com/CPS\-research\-group/ink\_bwts](https://github.com/CPS-research-group/ink_bwts)\. To evaluate InK on HRL tasks, we consider a setting where the low\-level policy is pre\-trained independently before being used to learn the abstract world model\. We use the maze navigation task from\[rgl2024\], where a goal\-conditioned low\-level policy pre\-trained in a clean maze learns the full abstract world model\. Unlike InK, this baseline requires extensive exploration\. Note that we selectedD∗D^\{\*\}because the domain is a navigation task; it can be replaced with any other incremental planner depending on the task\. Concretely, we investigate the following:

InK vs\. Non\-InK\.We examine the performance, sample efficiency, and execution time of our proposed InK neurosymbolic HRL in a continuous physical environment, usingD∗D^\{\*\}as the high\-level symbolic planner, and compare it with a non\-InK HRL approach, RGL\[rgl2024\], which first learns a full model of the concrete system before planning \(Section[5\.1](https://arxiv.org/html/2608.02993#S5.SS1)\)\. We compare on the RGL environments and report only the RGL results, since it is the state\-of\-the\-art non\-InK approach\.

Comparison of symbolic planners\.We evaluateD∗D^\{\*\}, BWTS, and BAMCP\[bamdp2013\]on small symbolic environments\. We analyze the impact of prior knowledge, and test also in an InK complex continuous environment in Section[5\.2](https://arxiv.org/html/2608.02993#S5.SS2)\.

### 5\.1InK vs\. Non\-InK

We experiment on three noisy physical Point\-Maze environments from RGL\[rgl2024\]: Four Rooms, Medium Maze, and Hard Maze, where a point agent navigates a planar maze\. The action is a continuous 2D position incrementa∈\[−1,1\]2a\\in\[\-1,1\]^\{2\}, transitions are stochastic with additive Gaussian noise, and the state is the agent’s Cartesian positions∈ℝ2s\\in\\mathbb\{R\}^\{2\}\. We pretrain the low\-level goal\-reaching policy in an obstacle\-free environment, following the experimental setup of RGL\[rgl2024\]\. Both InK and RGL share the same low\-level policy\. The key difference lies in high\-level planning, where non\-InK methods construct a complete world graph upfront \(training\) in RGL, whereas InK usesD∗D^\{\*\}planning at the high\-level, and can start reaching a goal from scratch \(∅\\emptyset\)\. No prior knowledge is used\.

We use five different seeds to train the low\-level policy \(for both InK and non\-InK\), and for each seed we sample ten random start–goal pairs\. We average over these 50 experiments\. We first compare in Table[1](https://arxiv.org/html/2608.02993#S5.T1)the number of steps \(and time\) required to reach the goal for the first time, either from scratch \(∅\\emptyset\), meaning in the training part for RGL\. We also compare after training for RGL \(which takes extensive time≥500​s,100000\\geq 500s,100000samples\), and after7575random goals have been sampled and reached for InK, which prebuilds a knowledge base, and is much more efficient \(<1​s,5000<1s,5000samples\)\. Furthermore, we demonstrate the applicability of InK to an even more complex, high\-dimensional domain \(29 dimensions\): the AntMaze U\-Room environment\[todorov2012mujoco\], in which an ant agent with multiple actuated joints \(from MuJoCo\) navigates a U\-shaped corridor\. The low\-level goal\-reaching policy is pre\-trained in the same manner as described above\.

Discussion:InK requires 30 to 100 times fewer samples than RGL to reach the goal from scratch \(∅\\emptyset\), and after “training" \(reaching 75 goals\), InK remains more efficient than RGL in both number of samples \(18% less\) and time \(20x\)\. Moreover, the “training” phase of InK itself is more sample\-efficient than RGL training\. Over a sequence of goals, which RGL is specifically designed to optimize for, RGL initially benefits from its learned structure, as shown by the initial dip in Fig\.[3](https://arxiv.org/html/2608.02993#S5.F3)\. However, after approximately 25 goals, InK becomes as efficient as RGL and then increasingly more efficient, with the cumulative sample gap exceeding 100,000 and growing further in the case of Hard Maze\. InK is consistently better than RGL, even on RGL environments without prior knowledge\.

Table 1:InK vs RGL number of samples \(& runtime\),↓\\downarrowlower is better, to reach goal from start for 50 different start\-goal pairs\.MethodFour RoomsMedium MazeHard MazeRGL from scratch \(∅\\emptyset\)2080±7012080\\pm 70110412±366210412\\pm 366217456±558517456\\pm 5585\(96\.48​s±32\.38\)\(96\.48s\\pm 32\.38\)\(1436​s±608\)\(1436s\\pm 608\)\(1018​s±362\)\(1018s\\pm 362\)InK from scratch \(∅\\emptyset\)64\.90±9\.17\\mathbf\{64\.90\\pm 9\.17\}147\.82±28\.29\\mathbf\{147\.82\\pm 28\.29\}208\.92±41\.20\\mathbf\{208\.92\\pm 41\.20\}\(0\.02​𝐬±0\.00\)\\mathbf\{\(0\.02s\\pm 0\.00\)\}\(0\.05​𝐬±0\.01\)\\mathbf\{\(0\.05s\\pm 0\.01\)\}\(0\.04​𝐬±0\.01\)\\mathbf\{\(0\.04s\\pm 0\.01\)\}RGL after train40\.08±2\.9740\.08\\pm 2\.9748\.32±4\.3848\.32\\pm 4\.3869\.82±20\.7469\.82\\pm 20\.74\(0\.34​s±0\.02\)\(0\.34s\\pm 0\.02\)\(0\.28​s±0\.01\)\(0\.28s\\pm 0\.01\)\(0\.21​s±0\.01\)\(0\.21s\\pm 0\.01\)InK after 75 goals31\.28±8\.59\\mathbf\{31\.28\\pm 8\.59\}40\.36±21\.06\\mathbf\{40\.36\\pm 21\.06\}58\.16±18\.74\\mathbf\{58\.16\\pm 18\.74\}\(after “train”\)\(0\.01​𝐬±0\.002\)\\mathbf\{\(0\.01s\\pm 0\.002\)\}\(0\.01​𝐬±0\.006\)\\mathbf\{\(0\.01s\\pm 0\.006\)\}\(0\.01​𝐬±0\.003\)\\mathbf\{\(0\.01s\\pm 0\.003\)\}RGL full training100000100000150000150000300000300000\(498\.63​s±59\.56\)\(498\.63s\\pm 59\.56\)\(1167\.48​s±77\.82\)\(1167\.48s\\pm 77\.82\)\(6022\.96​s±2063\.39\)\(6022\.96s\\pm 2063\.39\)InK completing 75 goals2936\.0±334\.36\\mathbf\{2936\.0\\pm 334\.36\}3095\.4±251\.20\\mathbf\{3095\.4\\pm 251\.20\}4651\.2±1396\.33\\mathbf\{4651\.2\\pm 1396\.33\}\(“training”\)\(0\.84​𝐬±0\.22\)\(\\mathbf\{0\.84s\\pm 0\.22\)\}\(0\.87​𝐬±0\.176\)\(\\mathbf\{0\.87s\\pm 0\.176\}\)\(0\.83​𝐬±0\.25\)\(\\mathbf\{0\.83s\\pm 0\.25\}\)![Refer to caption](https://arxiv.org/html/2608.02993v1/x4.png)\(a\)Four Rooms
![Refer to caption](https://arxiv.org/html/2608.02993v1/x5.png)\(b\)Medium Maze
![Refer to caption](https://arxiv.org/html/2608.02993v1/x6.png)\(c\)Hard Maze

Figure 3:Sample\-efficiency gain of InK over RGL \(\>\>100K environment steps\) in the Point Maze environment\. Pre\-Training: learning the low\-level neural module \(same\); RGL Training: learning the full knowledge of the concrete world\.InK in Ant\-Maze U\-Room: InK can handle efficiently even more challenging environments, such as a MuJoCo Ant agent in a U\-shaped maze, namely the Ant\-Maze U\-Room\[todorov2012mujoco\]\. Compared with the previous benchmark, the \(neural\) low\-level policy has to handle a much more complex physical environment \(29 dimensions\)\. We pretrain this neural low\-level policy and use the same low\-level policy for both InK and non\-InK\. As above, Non\-InK requires an overwhelming number of samples \(∼\\sim10K\) to build the full graph of the abstract world, whereas InK reaches the goal while building a goal\-directed InK abstract world using around 1507 steps \(with aD∗D^\{\*\}high\-level planner and even less, 1134 steps, with a BWTS high\-level planner\)\.

![Refer to caption](https://arxiv.org/html/2608.02993v1/figs/ant_maze/ant_maze_rgl.png)\(a\)Non\-InK \(RGL\)
![Refer to caption](https://arxiv.org/html/2608.02993v1/x7.png)\(b\)InK\-D∗D^\{\*\}
![Refer to caption](https://arxiv.org/html/2608.02993v1/x8.png)\(c\)InK\-BWTS

Figure 4:Ant\-Maze U\-Room RL environment\.Bluedot: start;reddot: goal\.
### 5\.2Comparison between symbolic planners

In this section, we compare symbolic plannersD∗D^\{\*\}, BWTS, and BAMCP\[bamdp2013\], with and without prior structural knowledge\. We first consider simple synthetic environments with the full set𝒲0\\mathcal\{W\}\_\{0\}of possible worlds:10×1010\\times 10grids with a single horizontal or vertical wall, each having one opening\. Let𝒲h\\mathcal\{W\}\_\{h\}be10×1010\\times 10worlds with a horizontal wall at each admissible row \(y=1y=1–88, excluding0,90,9for start and goal\) and an opening at each wall position \(x=0x=0–99\), giving\|𝒲h\|=80\|\\mathcal\{W\}\_\{h\}\|=80\. The vertical\-wall set𝒲v\\mathcal\{W\}\_\{v\}is defined analogously, and𝒲h​v=𝒲h∪𝒲v\\mathcal\{W\}\_\{hv\}=\\mathcal\{W\}\_\{h\}\\cup\\mathcal\{W\}\_\{v\}\. Details on belief set construction are in the supplementary materials\.

For BWTS, we use an exploration bonus ofce=1\.5c\_\{e\}=1\.5andI=200000I=200000iterations for all belief sets\. The rollout strategiesσk\\sigma\_\{k\}combine five primary targets \(the goal or one of four border midpoints\) with two wall\-sweeping variants, yielding1010strategies in total\. For comparison, we runD∗D^\{\*\}independently on each belief world\. For BAMCP, the structural knowledge of𝒲h,v,h​v\\mathcal\{W\}\_\{h,v,hv\}is particularly hard to encode, with strong dependencies between different positions in the grid: if there is a wall in cell\(3,3\)\(3,3\), then there cannot be a wall in cell\(7,7\)\(7,7\)\. We first experimented with a prior distribution with probability0\.90\.9to not be a wall and0\.10\.1to be a wall, matching the probabilities in𝒲h,v,h​v\\mathcal\{W\}\_\{h,v,hv\}\. However, stochastic rollouts in such an open environment seldom find the goal \(lots of loops\), and BAMCP is very unstable \(examples in supplementary material\)\. Remember BWTS usesstrategicrollouts instead of stochastic rollouts\. The probabilities we use are\.6/\.4\.6/\.4for a cell to be no wall/ a wall\. The average results over all the belief worlds are summarized in Table[2](https://arxiv.org/html/2608.02993#S5.T2)\. AsD∗D^\{\*\}is deterministic, results are always the same on these deterministic symbolic environments\. For BWTS and BAMCP, we report the mean±\\pmstandard deviation over 10 different random seeds\.

Table 2:Expected number of steps \(& runtime\),↓\\downarrowlower is better, for the BWTS\-learned policy, BAMCP, andD∗D^\{\*\}\.Belief Worlds𝒲h\\mathcal\{W\}\_\{h\}𝒲v\\mathcal\{W\}\_\{v\}𝒲h​v\\mathcal\{W\}\_\{hv\}D∗D^\{\*\}24\.5624\.5623\.1923\.1923\.8823\.88\(0\.01​𝐬\)\\mathbf\{\(0\.01s\)\}\(0\.01​𝐬\)\\mathbf\{\(0\.01s\)\}\(0\.01​𝐬\)\\mathbf\{\(0\.01s\)\}BWTS21\.22±0\.20\\mathbf\{21\.22\\pm 0\.20\}21\.22±0\.16\\mathbf\{21\.22\\pm 0\.16\}23\.36±0\.08\\mathbf\{23\.36\\pm 0\.08\}\(1\.05​s±\.13\)\(1\.05s\\pm\.13\)\(1\.06​s±\.1\)\(1\.06s\\pm\.1\)\(52​s±1\.6\)\(52s\\pm 1\.6\)BAMCP28\.42±1\.1628\.42\\pm 1\.1628\.89±1\.2928\.89\\pm 1\.2940\.42±1\.3940\.42\\pm 1\.39\(30\.88​s±1\.65\)\(30\.88s\\pm 1\.65\)\(28\.9​s±1\.05\)\(28\.9s\\pm 1\.05\)\(92\.1​s±2\.19\)\(92\.1s\\pm 2\.19\)Discussion: Table[2](https://arxiv.org/html/2608.02993#S5.T2)shows that BWTS achieves lowest expected cost\. The gains are largest for belief worlds with only horizontal \(15\.7%15\.7\\%vsD∗D^\{\*\}\) or vertical walls \(9\.3%9\.3\\%vsD∗D^\{\*\}\)\. For𝒲h​v\\mathcal\{W\}\_\{hv\}, the margin becomes negligible, at2\.2%2\.2\\%\. To understand the source of performance gain for BWTS in𝒲h\\mathcal\{W\}\_\{h\}, we analyzed the trajectories \(from start to goal\) for two belief worlds \(one in blue and one in black\) in𝒲h\\mathcal\{W\}\_\{h\}as shown in Fig\.[5](https://arxiv.org/html/2608.02993#S5.F5)\. These examples demonstrate that BWTS exploits belief over possible doorway locations: the agent proceeds straight and initiates a directed wall sweep from the start, probing for the opening without costly backtracking\. In a single instance like the blue world in Fig\.[5](https://arxiv.org/html/2608.02993#S5.F5),D∗D^\{\*\}may appear optimal because it commits to the correct sweep direction\. However, in the black world,D∗D^\{\*\}chooses the wrong initial sweep and then must backtrack, incurring extra cost\. By planning over belief worlds, BWTS avoids this return sweep by adopting a probing strategy that minimizes expected cost*before*the opening is revealed\. In𝒲h​v\\mathcal\{W\}\_\{hv\}, there is no efficient “no backtracking” strategy, and the runtime of BWTS becomes excessive for the negligible gain in number of steps\.

![Refer to caption](https://arxiv.org/html/2608.02993v1/x9.png)

![Refer to caption](https://arxiv.org/html/2608.02993v1/x10.png)

![Refer to caption](https://arxiv.org/html/2608.02993v1/x11.png)

Figure 5:D∗D^\{\\ast\}, BWTS, and BAMCP forW∈𝒲hW\\in\\mathcal\{W\}\_\{h\}onBlueand Black Worlds\. Greyed\-out walls: unseen; highlighted walls: discovered en route\.BAMCP reveals a stochastic and inconsistent strategy, sometimes making unnecessary detours, with an expected cost exceeding 28 steps compared toD∗D^\{\*\}’s average of under 25 steps, and a prohibitive runtime\.

Table 3:InK\-BWTS vs InK\-D∗D^\{\*\}number of samples \(& runtime\) to reach goal from start for 10 different start\-goal pairs\.MethodPhysical RGL EnvironmentsInK\-D∗D^\{\*\}87\.70±15\.3687\.70\\pm 15\.36\(0\.02​𝐬±0\.00\)\(\\mathbf\{0\.02s\\pm 0\.00\}\)InK\-BWTS no prior Knowledge86\.97±13\.21\\mathbf\{86\.97\\pm 13\.21\}\(62\.56​s±30\.3\)\(62\.56s\\pm 30\.3\)InK\-BWTS w/ prior Knowledgeconstruction time: \(2\.66​s±0\.882\.66s\\pm 0\.88\) \+45\.97±22\.97\\mathbf\{45\.97\\pm 22\.97\}\(0\.01​𝐬±0\.01\)\(\\mathbf\{0\.01s\\pm 0\.01\}\)We finally compare in Table[3](https://arxiv.org/html/2608.02993#S5.T3)bothD∗D^\{\*\}and BWTS as symbolic planners in the high\-level of InK, onresizedphysical environments of RGL \(so that the 3 point mazes have the same size\)\. We compared without prior knowledge, with BWTS using the symbolic set𝒲h​v\\mathcal\{W\}\_\{hv\}of worlds to encode the position of the next wall \(when a wall is met, we rerun BWTS from the full set𝒲h​v\\mathcal\{W\}\_\{hv\}to model the position of the following wall\)\. InK\-BWTS is slightly more efficient than InK\-D∗D^\{\*\}, although runtime is much longer, consistent with Table[2](https://arxiv.org/html/2608.02993#S5.T2)\(𝒲h​v\\mathcal\{W\}\_\{hv\}\)\. With prior knowledge, BWTS is initialized with the set𝒲3\\mathcal\{W\}\_\{3\}consisting of three worlds: 4 Rooms, Medium Maze, and Hard Maze\. With𝒲3\\mathcal\{W\}\_\{3\}, BWTS is constructed only once, and it is then used across the mazes with much faster execution time \(2\.66​s2\.66s\)\. With prior knowledge, InK\-BWTS is much more efficient than InK\-D∗D^\{\*\}, halving the number of samples\. Overall, when there isnoprior structural knowledge, InK\-D∗D^\{\*\}is preferable\. With prior structural knowledge, InK\-BWTS is more efficient due to BWTS’s optimality, at the cost of increased run time\.

## 6Conclusion

This paper proposes aneurosymbolicHRL framework with incremental knowledge \(InK\), where a symbolic high\-level planner guides a neural low\-level controller\. The high\-level planner uses InK for planning \(e\.g\. withD∗D^\{\*\}\), and directs the low\-level controller to associated subgoals\. It combines the advantages of purely symbolic InK framework \(e\.g\. Geometric Motion Planners\[tamper24,noseworthy2021active\]\) in terms of sample complexity, and of non\-InK neurosymbolic framework \(e\.g\. SORB\[eysenbach2019sorb\]and RGL\[rgl2024\]\) that can handle complex model\-free physical environments\. It generates optimal strategies in complex physical environments with sparse\-reward \(e\.g\. a MuJoCo ant agent navigating a Maze\), while staying efficient in terms of number of samples\. Further, when prior knowledge on the world is available, we develop the BWTS algorithm, which searches for an optimal policy averaged over belief sets\. Empirically, in terms of sample efficiency, InK\(\-D∗D^\{\*\}\) outperforms RGL, a non\-InK method, from scratch \(∅\\emptyset\), asymptotically, and in terms of training, without using prior knowledge\. When prior knowledge is available, InK\-BWTS further outperforms InK\-D∗D^\{\*\}, with increased compute time as a trade\-off\. Overall, these results demonstrate that neurosymbolic HRL with InK provides a practical approach to sample\-efficient learning, yielding gains exceeding 100K environment steps in Point Maze\. We demonstrated the advantage of InK using navigation as a case study\. For future work, we plan to extend InK to other domains such as manipulation using PDDL\-based incremental planners\. Additionally, while BWTS handles structural prior knowledge and BAMCP handles probabilistic priors, neither addresses both; combining these complementary strengths into a unified algorithm \(as BAWMCP\) is a promising direction\.

\{credits\}

#### 6\.0\.1Acknowledgements

This research was conducted as part of the DesCartes program and was supported by the National Research Foundation, Prime Minister’s Office, Singapore, under the Campus for Research Excellence and Technological Enterprise \(CREATE\) program\. This research/project is also supported by the National Research Foundation, Singapore and DSO National Laboratories under the AI Singapore Programme \(AISG Award No: AISG2\-RP\-2020\-017\)\. The second author is partly supported by ANR\-23\-PEIA\-0006 SAIF\.

#### 6\.0\.2\\discintname

The authors have no competing interests to declare that are relevant to the content of this article\.

## References

## Appendix 0\.ATheoretical Analysis on BWTS

###### Theorem 0\.A\.1

The policyπ∗\\pi^\{\*\}choosing in\(v,𝒲\)\(v,\\mathcal\{W\}\)actionaaminimizingC​\(v,a,𝒲\)C\(v,a,\\mathcal\{W\}\)has average costC​\(π∗\)=C​\(v0,𝒲0\)C\(\\pi^\{\*\}\)=C\(v\_\{0\},\\mathcal\{W\}\_\{0\}\)\. Further,C​\(π∗\)=C∗C\(\\pi^\{\*\}\)=C^\{\*\}the optimal cost of the InK problem\.

###### Proof\(Sketch of Proof of Theorem 1\.\)

The proof is by induction on\|𝒲\|\|\\mathcal\{W\}\|\. For\|𝒲\|=1\|\\mathcal\{W\}\|=1, the proof is trivial\.

For the inductive step:π∗\\pi^\{\*\}plays in decision nodes\(v,𝒲\)\(v,\\mathcal\{W\}\)the actionaato minimizeC​\(v,a,𝒲\)C\(v,a,\\mathcal\{W\}\)\. Consider the chance node\(v0,a0,𝒲0\)\(v\_\{0\},a\_\{0\},\\mathcal\{W\}\_\{0\}\)witha0a\_\{0\}picked byπ∗\\pi^\{\*\}, and its two decision node children\(v0,𝒲0−\)\(v\_\{0\},\\mathcal\{W\}\_\{0\}^\{\-\}\)and\(v0a0,𝒲0\+\)\(v\_\{0\}^\{a\_\{0\}\},\\mathcal\{W\}\_\{0\}^\{\+\}\)\. We can apply the induction hypothesis on both𝒲0−\\mathcal\{W\}\_\{0\}^\{\-\}and𝒲0\+\\mathcal\{W\}\_\{0\}^\{\+\}which are strictly smaller than𝒲0\\mathcal\{W\}\_\{0\}, to obtain thatπ∗\\pi^\{\*\}is optimal on both subtrees\. By definition, we haveC​\(π∗\)=C​\(v0,𝒲0\)C\(\\pi^\{\*\}\)=C\(v\_\{0\},\\mathcal\{W\}\_\{0\}\)\.

Take any strategyπ′\\pi^\{\\prime\}\. Then consider the actiona′a^\{\\prime\}picked byπ′\\pi^\{\\prime\}at the root, andaapicked byπ∗\\pi^\{\*\}\. IfC​\(v0,a′,𝒲0\)=C​\(v0,a,𝒲0\)C\(v\_\{0\},a^\{\\prime\},\\mathcal\{W\}\_\{0\}\)=C\(v\_\{0\},a,\\mathcal\{W\}\_\{0\}\), then we can changeπ∗\\pi^\{\*\}to pickinga′a^\{\\prime\}at the root instead ofaawithout changingC​\(π∗\)C\(\\pi^\{\*\}\)\. So we can assume wlog thata=a′a=a^\{\\prime\}\. We can then apply the induction hypothesis to both subtrees of\(v0,a′,𝒲0\)\(v\_\{0\},a^\{\\prime\},\\mathcal\{W\}\_\{0\}\)to find thatC​\(π′\)≥C​\(π∗\)C\(\\pi^\{\\prime\}\)\\geq C\(\\pi^\{\*\}\)\. The last case is thatC​\(v0,a′,𝒲0\)\>C​\(v0,a,𝒲0\)C\(v\_\{0\},a^\{\\prime\},\\mathcal\{W\}\_\{0\}\)\>C\(v\_\{0\},a,\\mathcal\{W\}\_\{0\}\), by choice ofπ∗\\pi^\{\*\}minimizingC​\(v0,a,𝒲0\)C\(v\_\{0\},a,\\mathcal\{W\}\_\{0\}\)\. Again, applying the induction hypothesis on both subtrees ofC​\(v0,a′,𝒲0\)C\(v\_\{0\},a^\{\\prime\},\\mathcal\{W\}\_\{0\}\), we obtain that the best policy forC​\(v0,a′,𝒲0\)C\(v\_\{0\},a^\{\\prime\},\\mathcal\{W\}\_\{0\}\)is strictly worse than forC​\(v0,a,𝒲0\)C\(v\_\{0\},a,\\mathcal\{W\}\_\{0\}\), andC​\(π′\)\>C​\(π∗\)C\(\\pi^\{\\prime\}\)\>C\(\\pi^\{\*\}\)\. SoC∗=infπ′C​\(π′\)≥C​\(π∗\)≥C∗C^\{\*\}=\\inf\_\{\\pi^\{\\prime\}\}C\(\\pi^\{\\prime\}\)\\geq C\(\\pi^\{\*\}\)\\geq C^\{\*\}and we are done\.

Evaluation of the size of the full BWTS tree:Assuming𝒲=𝒲\+⊔𝒲−\\mathcal\{W\}=\\mathcal\{W\}^\{\+\}\\sqcup\\mathcal\{W\}^\{\-\}always partitions the belief set𝒲\\mathcal\{W\}into two sets of the same size, the number of nodes of the full BWTS tree is at least\|𝒲0\|×\|A\|log⁡\|𝒲0\|\>108\|\\mathcal\{W\}\_\{0\}\|\\times\|A\|^\{\\log\{\|\\mathcal\{W\}\_\{0\}\|\}\}\>10^\{8\}for\|𝒲0\|=128\|\\mathcal\{W\}\_\{0\}\|=128and\|A\|=8\|A\|=8\.

Consider the skeleton of the full BWTS tree, with only chance nodes: the tree is a balanced complete binary tree of depthlog⁡\|𝒲0\|\\log\{\|\\mathcal\{W\}\_\{0\}\|\}, because afterlog⁡\|𝒲0\|\\log\{\|\\mathcal\{W\}\_\{0\}\|\}chance nodes, there is a unique worldWWand the node is a leaf\. With all decision possibilities, there are\|A\|\|A\|choice nodes children of the first chance node\. Assuming after one choice there is a partition of𝒲\\mathcal\{W\}, we have\|A\|\|A\|times the skeleton of depthlog⁡\|𝒲0\|−1\\log\{\|\\mathcal\{W\}\_\{0\}\|\-1\}\. At this end, it gives at least\|𝒲0\|×\|A\|log⁡\|𝒲0\|=\|𝒲0\|1\+log⁡\(\|A\|\)\|\\mathcal\{W\}\_\{0\}\|\\times\|A\|^\{\\log\{\|\\mathcal\{W\}\_\{0\}\|\}\}=\|\\mathcal\{W\}\_\{0\}\|^\{1\+\\log\(\|A\|\)\}nodes\.

The less optimistic case is that a choice node does not provide any new information and the set𝒲\\mathcal\{W\}stays the same\. We can regroup different nodes with the same\(v,𝒲\)\(v,\\mathcal\{W\}\), as they will have the same future\. So there can be at most\|V\|\|V\|nodes\(v,𝒲\)\(v,\\mathcal\{W\}\)with the same belief set𝒲\\mathcal\{W\}\. This gives at most\|𝒲0\|×\|V\|log⁡\|𝒲0\|=\|𝒲0\|1\+log⁡\(\|V\|\)\|\\mathcal\{W\}\_\{0\}\|\\times\|V\|^\{\\log\{\|\\mathcal\{W\}\_\{0\}\|\}\}=\|\\mathcal\{W\}\_\{0\}\|^\{1\+\\log\(\|V\|\)\}nodes\.

###### Theorem 0\.A\.2\(Convergence of BWTS to Full\-Tree\)

Let\(πi\)i∈ℕ\(\\pi\_\{i\}\)\_\{i\\in\\mathbb\{N\}\}be the sequence of policies produced by the BWTS algorithm\. Then the sequenceC​\(πi\)i∈ℕC\(\\pi\_\{i\}\)\_\{i\\in\\mathbb\{N\}\}converges towardsC∗C^\{\*\}, the optimal cost of the \(discrete symbolic\) InK problem\.

###### Proof\(Proof of Theorem 2\.\)

LetB​W​T​SiBWTS\_\{i\}be the tree afteriiiterations of the BWTS algorithm, for alli∈ℕi\\in\\mathbb\{N\}\. We will prove that there exists a numberIIof iterations after whichB​W​T​SiBWTS\_\{i\}is the complete BWTS tree for alli\>Ii\>I\. Henceforth,πi\\pi\_\{i\}will satisfyC​\(πi\)=C∗C\(\\pi\_\{i\}\)=C^\{\*\}for alli\>Ii\>I, following Theorem 1\.

We claim that for allii, all nodes ofB​W​T​SiBWTS\_\{i\}will be visited in the selection step of Algorithm 1 infinitely many times\. We reason by contradiction: it means that there exists a nodeuuand an indexIuI\_\{u\}after whichuuis not visited\. Among all such nodesuu, consider a nodeu0u\_\{0\}closest to the root, andU0≠∅U\_\{0\}\\neq\\emptysetthe finite set of siblings ofu0u\_\{0\}\(includingu0u\_\{0\}\) which are visited only finitely many times\. There existsI0I\_\{0\}so that afterI0I\_\{0\}, no node fromU0U\_\{0\}is visited anymore\. Letv0v\_\{0\}be the parent ofu0u\_\{0\}\. By choice ofu0u\_\{0\},v0v\_\{0\}is visited infinitely many times\.

Ifv0v\_\{0\}is a chance node, thenu0u\_\{0\}is a decision node with only one siblingu0′u^\{\\prime\}\_\{0\}\. Asv0v\_\{0\}is seen infinitely often andu0u\_\{0\}is not seen afterI0I\_\{0\}, it means thatu0′u^\{\\prime\}\_\{0\}is seen infinitely often\. SoN​\(u0\)N\(u\_\{0\}\)will be fixed afterI0I\_\{0\}, whileN​\(u0′\)N\(u^\{\\prime\}\_\{0\}\)will be increasing towards\+∞\+\\infty\. Following Eq\. \(6\), the argmin will eventually selectω​\(v0\)=u0\\omega\(v\_\{0\}\)=u\_\{0\}afterI0I\_\{0\}, a contradiction withu0u\_\{0\}is not visited afterI0I\_\{0\}\.

Similarly, ifv0v\_\{0\}is a decision node, thenU0U\_\{0\}is a set of chance nodes\.N​\(v\)N\(v\)tends towards∞\\infty\. For allu∈U0u\\in U\_\{0\},N​\(u\)N\(u\)andQ​\(u\)Q\(u\)are constant afterI0I\_\{0\}\. HenceQ​\(u\)−Ce​ln⁡N​\(v\)N​\(u\)Q\(u\)\-C\_\{e\}\\sqrt\{\\frac\{\\ln N\(v\)\}\{N\(u\)\}\}converges towards−∞\-\\infty\. On the other hand, for everyu′∉U0u^\{\\prime\}\\notin U\_\{0\}sibling ofu0u\_\{0\},N​\(u′\)N\(u^\{\\prime\}\)tends towards∞\\infty\. At least oneu0′u\_\{0\}^\{\\prime\}hasN​\(u0′\)\>1\|A\|​N​\(v\)N\(u\_\{0\}^\{\\prime\}\)\>\\frac\{1\}\{\|A\|\}N\(v\)\. AsQ​\(u0′\)\>0Q\(u^\{\\prime\}\_\{0\}\)\>0, there existsI1I\_\{1\}withQ​\(u0′\)−Ce​ln⁡N​\(v\)N​\(u0′\)\>−1Q\(u^\{\\prime\}\_\{0\}\)\-C\_\{e\}\\sqrt\{\\frac\{\\ln N\(v\)\}\{N\(u^\{\\prime\}\_\{0\}\)\}\}\>\-1for alli\>I1i\>I\_\{1\}\. Hence there exists anI2\>max⁡\(I0,I1\)I\_\{2\}\>\\max\(I\_\{0\},I\_\{1\}\), such that for alli\>I2i\>I\_\{2\}, for allu∈U0u\\in U\_\{0\},Q​\(u\)−Ce​ln⁡N​\(v\)N​\(u\)<−1Q\(u\)\-C\_\{e\}\\sqrt\{\\frac\{\\ln N\(v\)\}\{N\(u\)\}\}<\-1\. Asu0′u^\{\\prime\}\_\{0\}is visited infinitely often \(u0′∉U0u^\{\\prime\}\_\{0\}\\notin U\_\{0\}\), there is an indexi\>I2i\>I\_\{2\}so thatα\\alphaselectsu0′u^\{\\prime\}\_\{0\}at indexii\. This is a contradiction with the argmin of Eq\. \(5\), as any nodeu∈U0u\\in U\_\{0\}has lowerQ​\(u\)−Ce​ln⁡N​\(v\)N​\(u\)<−1<Q​\(u0′\)−Ce​ln⁡N​\(v\)N​\(u0′\)Q\(u\)\-C\_\{e\}\\sqrt\{\\frac\{\\ln N\(v\)\}\{N\(u\)\}\}<\-1<Q\(u^\{\\prime\}\_\{0\}\)\-C\_\{e\}\\sqrt\{\\frac\{\\ln N\(v\)\}\{N\(u^\{\\prime\}\_\{0\}\)\}\}\.

So in both cases, we get a contradiction, proving that for alliiall nodes ofB​W​T​SiBWTS\_\{i\}will be visited infinitely often\. We claim then that there exists aniiso thatB​W​T​SiBWTS\_\{i\}is the complete BWTS\. Again, we prove that by contradiction\. If this is not the case, then there is a node of the complete BWTS that is in noB​W​T​SiBWTS\_\{i\}\. Take suchuua node the closest to the root\. It means by definition that its parentvvis in someB​W​T​SiBWTS\_\{i\}\. Hence by the above,vvis visited infinitely often, and with the same reasoning as above,uuwill be eventually added to the tree, a contradiction\. Hence there exists someIIso thatB​W​T​SiBWTS\_\{i\}is full for alli\>Ii\>I\. In this case, the definition of the backpropagation forVVbeing the same as for the costCC, the strategy forB​W​T​SiBWTS\_\{i\}is the same as for the complete BWTS\.

Evaluation of the complexity:Compared to the full BWTS tree, the smallest number of iterations \(resp\. nodes\) isI0=\|A\|×\|𝒲0\|I\_\{0\}=\|A\|\\times\|\\mathcal\{W\}\_\{0\}\|\(resp\. min\_nodes=3​I0=3I\_\{0\}\), 1024 for our example , to reach the leaves \(and thus evaluate the cost\) on all the \(uncontrollable\) chance branches\. Branches from decision nodes are only sparsely explored\. The algorithm needsO​\(I×k×\|V\|×\|𝒲0\|\)O\(I\\times k\\times\|V\|\\times\|\\mathcal\{W\}\_\{0\}\|\)operations to computeπI\\pi\_\{I\}\.

Compared with the full BWTS, we do not need to explore all decision\-nodes, but only a few\. The skeleton with only chance nodes is a binary balanced tree of depthlog⁡\|𝒲0\|\\log\{\|\\mathcal\{W\}\_\{0\}\|\}\. With only one decision explored, it gives2log⁡\|𝒲0\|=\|𝒲0\|2^\{\\log\{\|\\mathcal\{W\}\_\{0\}\|\}\}=\|\\mathcal\{W\}\_\{0\}\|nodes, times\|A\|\|A\|possible nodes for their children\. Concerning the complexity: rollouts takeO​\(k​\|V\|​\|𝒲0\|\)O\(k\|V\|\|\\mathcal\{W\}\_\{0\}\|\)operations for eachii: for each ofkksimple strategies, each world in𝒲0\\mathcal\{W\}\_\{0\}, each state inVVis accessedO​\(1\)O\(1\)times\. The backpropagation needsO​\(log⁡\(\|𝒲0\|\)\)O\(\\log\(\|\\mathcal\{W\}\_\{0\}\|\)\)operations, which is negligible\.

## Appendix 0\.BDescription of all the stages of BWTS

Stages of BWTS Construction:Every iteration of the BWTS algorithm starts at the root, which is a decision node\(v0,𝒲0\)\(v\_\{0\},\\mathcal\{W\}\_\{0\}\)\. We adopt in Algorithm[2](https://arxiv.org/html/2608.02993#alg2)the standard MCTS stages \(selection, expansion, rollout, and backpropagation\) with modifications to 3\. Rollouts \(see above\), and to 4\. Backpropagation detailed below\.

Algorithm 2Belief World Tree search1:root decision node

\(v0,𝒲0\)\(v\_\{0\},\\mathcal\{W\}\_\{0\}\), total number of iterations

II, exploration constant

cec\_\{e\}, rollout policies

\(σi\)1≤k\(\\sigma\_\{i\}\)\_\{1\\leq k\}\.

2:

r​o​o​t←\(v0,𝒲0\)root\\leftarrow\(v\_\{0\},\\mathcal\{W\}\_\{0\}\)
3:for

i∈\{0,…,I\}i\\in\\\{0,\\dots,I\\\}do⊳\\trianglerightiterateIItimes

4:\#1\. Selection

5:

u←r​o​o​tu\\leftarrow root
6:while

uuis fully expandeddo

7:if

uuis a decision nodethen

8:

a←α​\(u\)a\\leftarrow\\alpha\(u\);

u←Child​\(u,a\)u\\leftarrow\\text\{Child\}\(u,a\)⊳\\trianglerightEq\. \(5\)

9:else

10:

u←ω​\(u\)u\\leftarrow\\omega\(u\)⊳\\trianglerightEq\. \(6\)

11:

\(v,𝒲\)←u\(v,\\mathcal\{W\}\)\\leftarrow u
12:\#2\. Expansion

13:randomly sample a child

\(v,a,𝒲\)\(v,a,\\mathcal\{W\}\)that does not exist in the tree and attach it to the tree

14:attach

\(v,𝒲−\)\(v,\\mathcal\{W\}^\{\-\}\)and

\(v′,𝒲\+\)\(v^\{\\prime\},\\mathcal\{W\}^\{\+\}\)to the tree

15:\#3\. Rollouts

16:Compute

Q​\(v′,𝒲\+\)Q\(v^\{\\prime\},\\mathcal\{W\}^\{\+\}\)
17:and

Q​\(v,𝒲−\)Q\(v,\\mathcal\{W\}^\{\-\}\)⊳\\trianglerightEq\. \(4\)

18:\#4\. Backpropagation

19:

v←\(v,𝒲\)v\\leftarrow\(v,\\mathcal\{W\}\)
20:while

v≠r​o​o​tv\\neq rootdo

21:update

Q​\(v\)Q\(v\)⊳\\trianglerightEq\. \(7\) and \(8\)

22:

v←p​a​r​e​n​t​\(v\)v\\leftarrow parent\(v\)
23:return

r​o​o​troot

The four stages are repeated for iterationsi∈\{0,1,…,I\}i\\in\\\{0,1,\\dots,I\\\}, where the hyperparameterIIdenotes the total number of iterations \(compute budget\) to construct BWTS\. We say that a decision node\(v,𝒲\)\(v,\\mathcal\{W\}\)is*incomplete*if there is an actiona∈Aa\\in Awithout chance node\(v,a,𝒲\)\(v,a,\\mathcal\{W\}\)\. At each iteration, one incomplete decision node\(v,𝒲\)\(v,\\mathcal\{W\}\)isselected, one chance node\(v,a,𝒲\)\(v,a,\\mathcal\{W\}\)is added as well as its two \(decision nodes\) children\(v′,𝒲\+\)\(v^\{\\prime\},\\mathcal\{W\}^\{\+\}\)and\(v,𝒲−\)\(v,\\mathcal\{W\}^\{\-\}\)\(expansionstage\)\.

*\(1\) Selection\.*Starting from the root\(v0,𝒲0\)\(v\_\{0\},\\mathcal\{W\}\_\{0\}\), we descend the tree using the rulesα,ω\\alpha,\\omegadefined in Eq\. \(5\),\(6\), until we reach an incomplete decision node\(v,𝒲\)\(v,\\mathcal\{W\}\)\(or a depth/horizon cut\-off\)\. We increment the number of visits counterNNfor each node visited during the descent\.

The score at a decision node\(vt,𝒲t\)\(v\_\{t\},\\mathcal\{W\}\_\{t\}\)depends on the visit count of the node,N​\(vt,𝒲t\)N\(v\_\{t\},\\mathcal\{W\}\_\{t\}\), and the visit count of each actiona∈Aa\\in A,N​\(vt,a,𝒲t\)N\(v\_\{t\},a,\\mathcal\{W\}\_\{t\}\)\. An exploration hyperparametercec\_\{e\}controls the exploration–exploitation trade\-off: largercec\_\{e\}encourages more exploration \(potentially better solutions\) at the cost of additional compute\. Eq\. \(5\) defines the tree policyπt​r​e​e\\pi\_\{tree\}at decision nodes\.

a⋆∈arg⁡mina∈A⁡\(Q​\(vt,a,𝒲t\)−ce​ln⁡N​\(vt,𝒲t\)N​\(vt,a,𝒲t\)\)\.a^\{\\star\}\\;\\in\\;\\arg\\min\_\{a\\in A\}\\Big\(Q\(v\_\{t\},a,\\mathcal\{W\}\_\{t\}\)\\;\-\\;c\_\{e\}\\sqrt\{\\tfrac\{\\ln N\(v\_\{t\},\\mathcal\{W\}\_\{t\}\)\}\{N\(v\_\{t\},a,\\mathcal\{W\}\_\{t\}\)\}\}\\Big\)\.At chance nodes, the tree policyπtree\\pi\_\{\\mathrm\{tree\}\}is probabilistic\. Let the two child decision nodes have belief subsets𝒲\+\\mathcal\{W\}^\{\+\}and𝒲−\\mathcal\{W\}^\{\-\}\(with parent set𝒲\\mathcal\{W\}\)\. We select the child\(v,𝒲\+\)\(v,\\mathcal\{W\}^\{\+\}\)with probability:

πtree​\(\(v,𝒲\+\)∣\(v,a;𝒲\)\)\\displaystyle\\pi\_\{\\mathrm\{tree\}\}\\\!\\big\(\(v,\\mathcal\{W\}^\{\+\}\)\\mid\(v,a;\\mathcal\{W\}\)\\big\)=\|𝒲\+\|\|𝒲\|,\\displaystyle=\\frac\{\|\\mathcal\{W\}^\{\+\}\|\}\{\|\\mathcal\{W\}\|\},πtree​\(\(v,𝒲−\)∣\(v,a;𝒲\)\)\\displaystyle\\pi\_\{\\mathrm\{tree\}\}\\\!\\big\(\(v,\\mathcal\{W\}^\{\-\}\)\\mid\(v,a;\\mathcal\{W\}\)\\big\)=\|𝒲−\|\|𝒲\|\.\\displaystyle=\\frac\{\|\\mathcal\{W\}^\{\-\}\|\}\{\|\\mathcal\{W\}\|\}\.
This cardinality\-based sampling biases visits toward children with larger belief set𝒲\\mathcal\{W\}, which typically require more iterations to expand due to a larger number of potential leaf nodes\.

*\(2\) Expansion\.*Upon reaching incomplete node\(v,𝒲\)\(v,\\mathcal\{W\}\), we pick at random one actiona∈Aa\\in Asuch that\(v,a,𝒲\)\(v,a,\\mathcal\{W\}\)does not yet exist in the tree\. We add it to the tree, as well as its two children\(v′,𝒲\+\)\(v^\{\\prime\},\\mathcal\{W\}^\{\+\}\)and\(v,𝒲−\)\(v,\\mathcal\{W\}^\{\-\}\)\. When adding a new node, we ensure that the same configuration\(v,𝒲\)\(v,\\mathcal\{W\}\)does not already appear along the ancestor path \(cycle avoidance\)\. If this is the case, then this action is known not to be optimal, and the associated cost is fixed to\+∞\+\\infty\. Both chance nodes\(v′,𝒲\+\)\(v^\{\\prime\},\\mathcal\{W\}^\{\+\}\)and\(v,𝒲−\)\(v,\\mathcal\{W\}^\{\-\}\)are evaluated usingrollouts\.

*\(3\) Rollout\.*We compute the evaluationQ​\(v′,𝒲\+\)Q\(v^\{\\prime\},\\mathcal\{W\}^\{\+\}\)andQ​\(v,𝒲−\)Q\(v,\\mathcal\{W\}^\{\-\}\)of the cost of\(v′,𝒲\+\)\(v^\{\\prime\},\\mathcal\{W\}^\{\+\}\)and\(v,𝒲−\)\(v,\\mathcal\{W\}^\{\-\}\), based on Eq\. \(4\)\.

Designing effective rollouts in BWTS is crucial as rollout returns directly affect the current value estimates and, consequently, future selections under the tree policyπt​r​e​e\\pi\_\{tree\}\. Naive \(random\) rollouts, as commonly used in MCTS, can be uninformative in some domains \(such as mazes\) where loops and dead\-ends induce high variance and may bias exploration toward undesirable, suboptimal policies\. To reduce variance and stabilize backups, we propose*strategic rollouts*instead of purely random ones\.

At each AND node, we evaluate a fixed set of ten rollout strategies\{σk\}k=110\\\{\\sigma\_\{k\}\\\}\_\{k=1\}^\{10\}\. For a given strategyσk\\sigma\_\{k\}and each belief setWi∈𝒲tW\_\{i\}\\in\\mathcal\{W\}\_\{t\}present at the current node, we execute the same strategy policy and obtain a return costck​\(Wi\)=C​\(\(vt,…,g\);σk,Wi\)c^\{k\}\(W\_\{i\}\)=C\(\(v\_\{t\},\\dots,g\);\\sigma\_\{k\},W\_\{i\}\)\. We then compute the probability\-weighted average

ca​v​gk=∑ip​\(Wi\)​ck​\(Wi\),c^\{k\}\_\{avg\}=\\sum\_\{i\}p\(W\_\{i\}\)\\,c^\{k\}\(W\_\{i\}\),and use the minimum across strategies,cr​o​l​l=mink∈\{1,…,10\}⁡ca​v​gkc\_\{roll\}=\\min\_\{k\\in\\\{1,\\dots,10\\\}\}c^\{k\}\_\{avg\}, as the rollout estimate for that node\.

We now define each rollout strategyσk\\sigma\_\{k\}\. Each strategy has two components: \(i\) a primary target has one of five choices: move toward the midpoint of each border \(four choices\) or move toward the goal; and \(ii\) a sweep rule when encountering a blocking wall: perform a directed sweep along the wall to find an opening, with two variants, left\-priority vs\. right\-priority \(for vertical walls, these correspond to up\-first vs\. down\-first; for horizontal walls, left\-first vs\. right\-first\)\. Combining the55primary targets with the22sweep variants yields5×2=105\\times 2=10rollout strategies in total\. These strategic rollouts lower variance, stabilize AND/OR backups, and reduce the number of iterations required to grow a useful search tree\.

*\(4\) Backpropagation\.*After computing the evaluationsQ​\(v′,𝒲\+\)Q\(v^\{\\prime\},\\mathcal\{W\}^\{\+\}\)andQ​\(v,𝒲−\)Q\(v,\\mathcal\{W\}^\{\-\}\), we backtrack inductively from the bottom to the root and update the values of ancestor nodes\. For chance nodes\(v,a,𝒲\)\(v,a,\\mathcal\{W\}\)with children\(v,𝒲−\),\(v′,𝒲\+\)\(v,\\mathcal\{W\}^\{\-\}\),\(v^\{\\prime\},\\mathcal\{W\}^\{\+\}\), we set as in Eq\. \(2\):

Q​\(v,a,𝒲\)=\|𝒲1\|​Q​\(v1,𝒲1\)\+\|𝒲2\|​Q​\(v2,𝒲2\)\|𝒲1\|\+\|𝒲2\|=\|𝒲\|Q\(v,a,\\mathcal\{W\}\)=\\frac\{\|\\mathcal\{W\}\_\{1\}\|Q\(v\_\{1\},\\mathcal\{W\}\_\{1\}\)\+\|\\mathcal\{W\}\_\{2\}\|Q\(v\_\{2\},\\mathcal\{W\}\_\{2\}\)\}\{\|\\mathcal\{W\}\_\{1\}\|\+\|\\mathcal\{W\}\_\{2\}\|=\|\\mathcal\{W\}\|\}
For decision nodes\(v,𝒲\)\(v,\\mathcal\{W\}\), we set as in Eq\. \(3\):

Q​\(v,𝒲\)←mina∈A⁡\(C​\(v,a\)\+Q​\(v,a,𝒲\)\)Q\(v,\\mathcal\{W\}\)\\;\\leftarrow\\;\\min\_\{a\\in A\}\(C\(v,a\)\\;\+\\;Q\(v,a,\\mathcal\{W\}\)\)
These four stages are repeated for a given iteration budget\.

## Appendix 0\.CBAMCP Discussion

BAMCP is a symbolic planner used at the high level in neurosymbolic HRL frameworks and also allows the incorporation of prior knowledge\. It provides an approximate solution to the Bayesian Adaptive Markov Decision Process \(BAMDP\), which formulates the MDP objective over all possible transition probability distributions\. Solving the BAMDP exactly is intractable, as it requires integrating over all such distributions\. BAMCP addresses this by assuming independence across state–action pairs: for each pair \(s,as,a\), it models a distribution over next states \(s′s^\{\\prime\}\) independently of other pairs\. This is typically implemented using a Dirichlet prior over transition probabilities, where the posterior is updated only from observed tuples \(s,a,s′s,a,s^\{\\prime\}\)\. Consequently, BAMCP captures prior knowledge solely at the level of one\-step transition dynamics\. However, in the Belief World Problem, knowledge is structural, hence it creates dependencies across positions\. For instance, we know there is a \(horizontal or vertical\) wall, but we do not know where\. This creates dependencies e\.g\. between cells\(3,3\)\(3,3\)and\(7,7\)\(7,7\)that cannot have a wall at the same time\. Such dependencies cannot be represented under independent transition model of BAMCP\. The core novelty of BWTS is to explicitly model and reason over structural knowledge, and handle dependencies between positions\.

Still, we attempted to incorporate structural knowledge into BAMCP and conduct various experiments, reported in Table[4](https://arxiv.org/html/2608.02993#Pt0.A3.T4)\. A naive prior is to assume that, for every unexplored cell, there is no wall with probability one \(so the agent moves withpmove=1p\_\{\\text\{move\}\}=1\) and a wall with probability zero \(sopstay=0p\_\{\\text\{stay\}\}=0\)\. Once a wall is detected in positionXX, these probabilities are reversed for positionXX, i\.e\.,pmove=0p\_\{\\text\{move\}\}=0andpstay=1p\_\{\\text\{stay\}\}=1\. Indeed, this is exactly the assumption made byD∗D^\{\*\}, which plans under the belief that all cells are initially free and replans in the next cycle using the updated knowledge after wall detection\. We also experimented with a priorpmove=0\.9p\_\{\\text\{move\}\}=0\.9andpstay=0\.1p\_\{\\text\{stay\}\}=0\.1to reflect the proportion of walls from𝒲h,𝒲v,𝒲h​v\\mathcal\{W\}\_\{h\},\\mathcal\{W\}\_\{v\},\\mathcal\{W\}\_\{hv\}\.

BAMCP performs poorly under both priors, incurring roughly twice the cost ofD∗D^\{\*\}\(Table 1\)\. The reason is tied to the use of stochastic rollouts, which guide the agent’s exploration\. With prior \(pmove=0\.9p\_\{\\text\{move\}\}=0\.9,pstay=0\.1p\_\{\\text\{stay\}\}=0\.1\) or \(pmove=1p\_\{\\text\{move\}\}=1,pstay=0p\_\{\\text\{stay\}\}=0\), each rollout generates a world where10%10\\%of the cells is a wall on average\. This allows a lot of possible trajectories for the rollouts, including a lot of looping, as illustrated on Fig\.[6](https://arxiv.org/html/2608.02993#Pt0.A3.F6), and very few rollouts reach the goal \(both rollout 1 and 2 fail to reach the goal after 120 steps\)\. This is a key reason why we use strategic rollouts in BWTS\.

Table 4:Expected\-cost \(Total run time for solving all grid configuration\), lower is better, for the BWTS\-learned policy, BAMCP \(pm​o​v​e/ps​t​a​yp\_\{move\}/p\_\{stay\}\), andD∗D^\{\*\}across \(𝒲h\\mathcal\{W\}\_\{h\}\), \(𝒲v\\mathcal\{W\}\_\{v\}\), and \(𝒲h​v\\mathcal\{W\}\_\{hv\}\)\.Belief Worlds𝒲h\\mathcal\{W\}\_\{h\}𝒲v\\mathcal\{W\}\_\{v\}𝒲h​v\\mathcal\{W\}\_\{hv\}D∗D^\{\*\}24\.5624\.5623\.1923\.1923\.8823\.88\(0\.03​𝐬\)\\mathbf\{\(0\.03s\)\}\(0\.03​𝐬\)\\mathbf\{\(0\.03s\)\}\(0\.06​𝐬\)\\mathbf\{\(0\.06s\)\}BWTS21\.22±0\.20\\mathbf\{21\.22\\pm 0\.20\}21\.22±0\.16\\mathbf\{21\.22\\pm 0\.16\}23\.36±0\.08\\mathbf\{23\.36\\pm 0\.08\}\(84\.51​s±12\.24\)\(84\.51s\\pm 12\.24\)\(84\.28​s±9\.58\)\(84\.28s\\pm 9\.58\)\(834\.24​s±196\.96\)\(834\.24s\\pm 196\.96\)BAMCP \(1\.0/0\.0\)49\.61±1\.4949\.61\\pm 1\.4954\.76±5\.5854\.76\\pm 5\.5850\.81±1\.5950\.81\\pm 1\.59\(4313\.19​s±116\.40\)\(4313\.19s\\pm 116\.40\)\(4814\.18​s±378\.05\)\(4814\.18s\\pm 378\.05\)\(8733\.22​s±230\.11\)\(8733\.22s\\pm 230\.11\)BAMCP \(0\.9/0\.1\)45\.85±2\.6945\.85\\pm 2\.6950\.55±2\.1050\.55\\pm 2\.1050\.70±2\.4350\.70\\pm 2\.43\(4215\.38​s±348\.65\)\(4215\.38s\\pm 348\.65\)\(4667\.55​s±225\.59\)\(4667\.55s\\pm 225\.59\)\(9089\.90​s±522\.40\)\(9089\.90s\\pm 522\.40\)BAMCP \(0\.6/0\.4\)28\.42±1\.16\\mathbf\{28\.42\\pm 1\.16\}28\.89±1\.29\\mathbf\{28\.89\\pm 1\.29\}40\.42±1\.39\\mathbf\{40\.42\\pm 1\.39\}\(2469\.89​s±132\.08\)\(2469\.89s\\pm 132\.08\)\(2312\.52​s±83\.85\)\(2312\.52s\\pm 83\.85\)\(7367\.34​s±351\.41\)\(7367\.34s\\pm 351\.41\)

![Refer to caption](https://arxiv.org/html/2608.02993v1/x12.png)Figure 6:Samples of random rollout trajectories of length around120120, starting from thegreen dotat\(5,9\)\(5,9\)under BAMCP\(0\.9/0\.1\)\(0\.9/0\.1\), fail to reach the goalred dotat\(9,9\)\(9,9\)\.![Refer to caption](https://arxiv.org/html/2608.02993v1/x13.png)\(a\)Trajectory
![Refer to caption](https://arxiv.org/html/2608.02993v1/x14.png)\(b\)BAMCP root node at location \(5,6\)

Figure 7:The agent oscillates between moving up at\(5,6\)\(5,6\)and moving down again for BAMCP \(0\.6/0\.4\) due to difficulties due to stochastic setting ofpm​o​v​e=0\.6p\_\{move\}=0\.6andps​t​a​y=0\.4p\_\{stay\}=0\.4\.The best\-performing prior we found was settingpmove=0\.6p\_\{\\text\{move\}\}=0\.6andpstay=0\.4p\_\{\\text\{stay\}\}=0\.4, which is closer toD∗D^\{\*\},20%20\\%less sample efficient thanD∗D^\{\*\}\. With40%40\\%of walls, the space is more constrained, there are fewer loops, and more stochastic rollouts find the goal\. The execution time is substantially higher thanD∗D^\{\*\}, and even higher than BWTS, which computes the optimal policy, whereas BAMCP is even less efficient thanD∗D^\{\*\}: for structural knowledge, BAMCP is just not adequate\. We finally illustrate that the strategy found by BAMCP is also random and does not follow any pattern like inD∗D^\{\*\}and BWTS \(see main paper\)\. As shown in Fig\.[7](https://arxiv.org/html/2608.02993#Pt0.A3.F7), the agent can oscillate between two cells incurring unnecessary cost, which is avoided by the more strategic methodsD∗D^\{\*\}and BWTS\.

## Appendix 0\.DExperiment Details and Additional Results

The maps for the Point Maze environments used in our experiments are illustrated in Fig\.[8](https://arxiv.org/html/2608.02993#Pt0.A4.F8)\. Each environment consists of a continuous two\-dimensional navigation domain, requiring the agent to reach a goal from a start point\. The low\-level policy is trained following the same procedure as in RGL \(using SAC\), where a continuous control policy is optimized to navigate between locally specified subgoals in an obstacle\-free environment\. The low\-level training uses a curriculum reward shaping in which the goal distance for each episode is randomized and gradually increased over training episodes\. The resulting training reward curve is shown in Fig\.[9](https://arxiv.org/html/2608.02993#Pt0.A4.F9), demonstrating stable convergence of the low\-level controller\.

![Refer to caption](https://arxiv.org/html/2608.02993v1/x15.png)\(a\)Four Rooms
![Refer to caption](https://arxiv.org/html/2608.02993v1/x16.png)\(b\)Medium Maze
![Refer to caption](https://arxiv.org/html/2608.02993v1/x17.png)\(c\)Hard Maze

Figure 8:Point Maze Environment Maps![Refer to caption](https://arxiv.org/html/2608.02993v1/x18.png)

![Refer to caption](https://arxiv.org/html/2608.02993v1/x19.png)

Figure 9:Low\-level policy training curve of point maze agent\. Percentage of successful goals in each episode\. The environment is sparse reward and gets 1 after reaching the goal, 0 otherwise\.InK in PointMaze FourRooms: We illustrate this on Fig\.[10](https://arxiv.org/html/2608.02993#Pt0.A4.F10)with one average case on the 4 room environment\.

![Refer to caption](https://arxiv.org/html/2608.02993v1/x20.png)\(a\)
![Refer to caption](https://arxiv.org/html/2608.02993v1/x21.png)\(b\)

Figure 10:Runs of InK \(∅\\emptyset\) vs RGL training in 4 rooms\.InK in Ant\-Maze U\-Room: We demonstrate in Fig\.[11](https://arxiv.org/html/2608.02993#Pt0.A4.F11)that InK can handle even more challenging environments, such as the Ant\-Maze U\-Room\. Here, the difference lies only in the low\-level policy, while high\-level planning is performed using InK symbolic planners\.

![Refer to caption](https://arxiv.org/html/2608.02993v1/x22.png)\(a\)InK\-D∗D^\{\*\}\(1507 Steps\)
![Refer to caption](https://arxiv.org/html/2608.02993v1/x23.png)\(b\)InK\-BWTS \(1134 Steps\)

Figure 11:Ant\-Maze U\-Room RL Environment\.
## Appendix 0\.EInK\-BWTS for RL Environments

We provide here more explanation for line 569\-571, about when BWTS is used without prior knowledge as the symbolic planner\. Then, the set of all mazes is too large to be used as belief set𝒲0\\mathcal\{W\}\_\{0\}\. So we use a subset of𝒲h​v\\mathcal\{W\}\_\{hv\}as a representative set of the next wall to be encountered\.

InK alternates between high\-level planning and low\-level execution while incrementally updating knowledge about the environment which is shown in Algorithm 2\.

When BWTS is used as the symbolic planner, planning is restricted to a relevant subregion determined by a provisional path computed under current knowledge \(line 3 and 4\), different at each iteration\. Within this region, a belief set is generated using simple wall primitives \(horizontal and vertical\), reflecting the intuition that complex maze layouts are composed of elementary horizontal or vertical walls with openings \(line 5\)\. High\-level symbolic planning is then performed using BWTS \(Algorithm 1\) to select an intermediate subgoal \(line 6\), which is executed by a low\-level controller with monitoringm​o​nmon\(line 8\)\. Newly discovered obstacles update the knowledge mapMM, and the process repeats until the goal is reached\.

Algorithm 3InK\-BWTS with a representative set𝒲b​b\\mathcal\{W\}\_\{bb\}1:Current abstract knowledge map

MM, start state

s0s\_\{0\}, goal state

gg, low\-level policy

πℓ\\pi\_\{\\ell\}
2:Agent reaches goal

gg
3:Initialize current state

s←s0s\\leftarrow s\_\{0\}
4:while

s≠gs\\neq gdo

5:Run A\* on current knowledge

MMfrom

ssto

ggto obtain provisional path

PP
6:Compute the smallest axis\-aligned bounding box

BBenclosing

PP
7:

𝒲b​b←GenerateBeliefSet​\(M,B\)\\mathcal\{W\}\_\{bb\}\\leftarrow\\textsc\{GenerateBeliefSet\}\(M,B\)
8:Run BWTS

\(𝒲b​b,s,g\)\(\\mathcal\{W\}\_\{bb\},s,g\)to construct BWTS tree

9:Extract next high\-level subgoal

s^\\hat\{s\}from the root of BWTS tree

10:Execute low\-level policy

πl\\pi\_\{l\}from

sstoward

s^\\hat\{s\}with collision monitoring \(

m​o​nmon\)

11:ifunexpected wall encountered during executionthen

12:Update knowledge map

MMwith detected obstacle

13:else

14:Update current state

s←s^s\\leftarrow\\hat\{s\}
15:returnsuccess

![Refer to caption](https://arxiv.org/html/2608.02993v1/x24.png)\(a\)Horizontal Walls
![Refer to caption](https://arxiv.org/html/2608.02993v1/x25.png)\(b\)Vertical Walls

Figure 12:Belief Worlds Generation for Maze Environment\.### 0\.E\.1Belief Set Generation for InK\-BWTS

The belief set construction is designed to encode a structural prior over maze layouts while remaining computationally tractable which is provided in Algorithm 3\. The set of belief worlds is composed of environments containing a*single horizontal*or a*single vertical*wall, each with exactly one opening\. This design reflects the intuition that complex maze structures can be decomposed into compositions of such primitive wall elements\. As illustrated in Fig\.[12](https://arxiv.org/html/2608.02993#Pt0.A5.F12), for a10×1010\\times 10grid we generate horizontal\-wall belief worlds by placing a horizontal wall at each admissible row and inserting a single opening\. The start row \(y=0y=0\) and goal row \(y=9y=9\) are excluded from wall placement to ensure feasibility of trivial paths\. This yields88admissible wall rows; for each row, the opening may be placed in any of the1010columns, giving rise to\|𝒲h\|=80\|\\mathcal\{W\}\_\{h\}\|=80horizontal\-wall belief worlds \(Fig\.[12\(a\)](https://arxiv.org/html/2608.02993#Pt0.A5.F12.sf1)\)\.

Algorithm 4GenerateBeliefSet𝒲b​b\\mathcal\{W\}\_\{bb\}1:Current knowledge map

MM, bounding box

BB
2:Belief\-world set

𝒲b​b\\mathcal\{W\}\_\{bb\}
3:Initialize

𝒲b​b←∅\\mathcal\{W\}\_\{bb\}\\leftarrow\\emptyset
4:Restrict knowledge map

MMto region inside

BBto obtain

MBM\_\{B\}
5:Add

MBM\_\{B\}to

𝒲b​b\\mathcal\{W\}\_\{bb\}
6:for allwall orientation

o∈\{horizontal,vertical\}o\\in\\\{\\text\{horizontal\},\\text\{vertical\}\\\}do

7:for allwall offsets

d∈\{2,…,8\}d\\in\\\{2,\\dots,8\\\}within

BBdo⊳\\trianglerightfor reduced set offset is\{1,2,5,9\}\\\{1,2,5,9\\\}

8:Place a wall of orientation

ooat offset

dd
9:for allvalid opening positions along the walldo

10:Construct belief world

WWby inserting the wall with a single opening into

MBM\_\{B\}
11:Add

WWto

𝒲b​b\\mathcal\{W\}\_\{bb\}
12:return

𝒲b​b\\mathcal\{W\}\_\{bb\}

Vertical\-wall belief sets are constructed analogously by placing a vertical wall at each admissible column except the start column \(x=0x=0\) and goal column \(x=9x=9\), again with a single opening per wall\. This produces\|𝒲v\|=80\|\\mathcal\{W\}\_\{v\}\|=80vertical\-wall belief worlds \(Fig\.[12\(b\)](https://arxiv.org/html/2608.02993#Pt0.A5.F12.sf2)\)\. We further define the combined belief set as𝒲h​v=𝒲h∪𝒲v\\mathcal\{W\}\_\{hv\}=\\mathcal\{W\}\_\{h\}\\cup\\mathcal\{W\}\_\{v\}\.

In the full InK\-BWTS pipeline, belief sets are not generated over the entire grid\. Instead, they are constructed only within a dynamically computed bounding box \(BB\) that encloses the provisionalA∗A^\{\*\}path\. That is, the planner crops the relevant section of the map for belief\-world construction rather than operating over the full grid\. This design is particularly beneficial for larger grid sizes, as it significantly accelerates BWTS construction\.

Additionally, we may not want to place walls at every possible horizontal or vertical position\. Instead, walls are generated only at selected positions to construct the belief set, as done in line 5 of Algorithm[4](https://arxiv.org/html/2608.02993#alg4), where the wall location is chosen by selecting an offset from the agent toward the goal\. To further restrict the belief space, we reduce the number of possible wall openings for walls that are far from the agent\. For example, in a10×1010\\times 10grid with a single wall at offset 9, instead of considering all 10 possible configurations corresponding to different opening locations, we consider only alternate positions, reducing the number of openings to 5\.