What do you know? Bayesian knowledge inference for navigating agents

We sincerely thank the reviewer for the thoughtful and constructive feedback. We are pleased that the clarity, novelty, and systematic experimentation of the paper were appreciated. Below, we respond to the reviewer’s specific comments and suggestions.

Scope and spatial assumptions

We agree that our formulation makes use of the spatial structure, which makes it particularly suited for navigation tasks. This structure is useful for two reasons: First, it provides a natural way to define optimistic planning over unknown transitions, enabling efficient inference. Second, it allows the use of heuristic search methods such as D* lite or A*, where spatial distance provides an effective heuristic. While the referenced work by Zhi-Xuan et al. (2020) uses a more general formalism based on PDDL, their approach also makes use of a spatial heuristic by using A* for planning and to limit search depth in their bounded rational planning model. Thus, both approaches implicitly exploit structured environments, though to different extents.

While the spatial domain already offers a wide range of applications for our approach, we agree that extending our method to non-spatial domains could be an interesting and important future direction. We will note this in the revised future work section.

Spatial prior

The spatial prior captures the intuition that knowledge (or awareness/memory) of neighboring fields is likely to be correlated. For example, if a human knows one field in a corridor, they are likely to know neighboring fields as well. This prior allows the incorporation of the structure of the agent's knowledge without significantly increasing computational cost, as its computation cost is negligible compared to planning during inference.

Importantly, our approach does not depend on the spatial prior. We have now conducted an ablation using a uniform prior and found that results were qualitatively very similar, but the relative improvements between the baseline and our method were on average half as large (average factor 1.991). This suggests that while the prior has some influence, it is not essential for the effectiveness of our method. We will include this ablation in the appendix of the final version. Nevertheless, in Bayesian inference, providing the flexibility to specify prior knowledge is conceptually important to ensure meaningful posterior beliefs.

The hyperparameter of the prior was selected manually to produce moderately connected knowledge regions (neither fully fragmented nor overly clustered). The same hyperparameters were used both for generating the ground-truth knowledge values in the experiment (the fields initially displayed to the participants) and for inference. We will clarify this procedure in the appendix.

Hierarchical Bayesian Inference

We fully agree with the reviewer that human participants may perform higher-level reasoning about the structure of the tasks across and within environments, such as estimating the likelihoods of dead ends. As mentioned in our future work section, such hierarchical learning may account for the variability in our experimental data, including trajectories that appear irrational at first glance.

Our work provides a foundational step to understand observed learning behavior by making inference about latent knowledge tractable for a relatively simple learning model. Hierarchical learning would considerably increase complexity, but could be a promising direction for future work. We will add this point to the future work section. This suggestion also aligns well with our broader research goals, which include investigating how subjects generalize knowledge across environments and whether parameters like $q$ (the belief over transition probability) change across maze topologies.

Lines in Figure 4 and 5

We appreciate the reviewer's comment that the black line connecting medians may be misleading, which was also noted by reviewer Sttp. We will remove it in the final version.

Choice of hyperparameter $q$

For the gridworld experiments, we set $q=0.5$ without tuning, to model an equal chance for success and failure for unknown transitions. In the parking experiment, we used $q=0.3$, which corresponds to the true probability of a parking spot being available (as used for generating the environments). This value was manually chosen to produce meaningful behavior when using the optimal policy: the agent should neither always park at the first nor last opportunity. We will clarify this setting in the final version.

We thank the reviewer for the thoughtful and constructive feedback, as well as for the positive evaluation of our contribution. Below we address each of the reviewer's points and hope these clarify the reviewer's questions.

Clarification of "low-dimensionality"

In our context, "low-dimensionality" refers to settings where the number of latent knowledge configurations (i.e., belief states) is small enough to allow for exact Bayesian inference. Although we cannot define a universal threshold, in practice this typically means fewer than ~5 states in the underlying MDP. For example, in Bayesian inverse planning (ref. [5,6] in the paper), the food truck example involves 3 trucks at 3 locations, resulting in only 6 combinations = belief states. We also use this terminology to describe BEETLE. This method is applied to MDPs with up to 9 states, but it only solves the (forward) planning problem for a BAMDP, which is only a part of the knowledge inference problem. In contrast, we applied our method to problems with up to 169 states, corresponding to a latent belief space of size $2^{169}$. We will clarify these distinctions in the final version of the paper to make our use of the word "low-dimensional" more precise.

Relation to graph learning

As discussed in the paper, deterministic planning problems are equivalent to shortest path problems. Our approach can therefore be interpreted as learning properties about the given graph (i.e., the knowledge variables). However, our approach differs from standard graph learning, which typically reconstructs the actual environment graph from data. Instead, our goal is to reason over an agent's subjective knowledge of the graph's edges. This requires modeling both partial knowledge and adaptive planning under uncertainty. Standard graph learning approaches typically do not capture such subjective, temporally-updated knowledge states. We will use the additional page of the camera-ready version to include this relation in the final version.

Computational complexity

We agree that a more detailed discussion of complexity provides additional value. For exact inference, as in Bayesian inverse planning, we must consider all $2^N$ combinations of values of $K$, where $N$ is the number of states. For each configuration, computing the agent's policy and likelihood results in a complexity of $O(2^n \cdot C_\text{planning})$. Planning in the belief space using value iteration has complexity $O(|S|^2 \cdot |A| / \epsilon) = O(2^{2N} \cdot 4 / \epsilon)$, with $\epsilon$ the precision of value iteration, since the belief MDP has $2^N$ states. Additionally, planning has to be performed up to $N$ times for each configuration, as the agent is assumed to replan along the trajectory (and then all fields have been visited, including the goal). The results in a total complexity for inference of $O(N \cdot 2^{3N} / \epsilon)$.

In contrast, our Gibbs-sampling-based approach scales linearly with the number of variables: we sample each $K_i$ conditioned on all others, leading to a complexity of $O(L \cdot N \cdot C_\text{planning})$, where $L$ is the number of samples. Our planning approximation avoids the complete belief space and uses the shortest path algorithm $D^*$ lite, which has worst-case complexity similar to Dijkstra, $O(|E| + |V| \log |V|) = O(4 \cdot N + N \log N) = O(N \log N)$. Similar to Bayesian inverse planning, planning needs to be done $N$ times per sample. Therefore, the total cost is $O(L \cdot N \cdot N \cdot N \log N) = O(L \cdot N^3 \cdot \log N)$. In the final version of the paper, we will complement our runtime comparison with this analysis.

Evaluation measures and visualizations

We used the KL divergence in the parking evaluation to quantify how closely different planning approximations match the optimal Bayesian planner and to measure their influence on the inference results. We could use this metric only for this problem, as it is one of the few cases where the exact Bayesian-optimal policy under epistemic uncertainty is computable. For the gridworld experiment, we instead used the log-likelihood of human trajectories under each model, as ground truth policies are not available and we are given experimental data.

Regarding visualizations: the grey lines connect data points from the same trajectory. We agree that the black line connecting medians may be misleading and will remove it. We will use the additional space in the camera-ready version to expand the description on this.

Practical usability compared to simpler methods

This may reflect a misunderstanding. The only existing simpler method is to do exact planning and/or inference (i.e., Bayesian inverse planning), which is only feasible for very small environments (such as the parking task). Alternatively, one could craft rules by hand, as we did for the baselines in the gridworld tasks, where we assumed no knowledge in case of turn-arounds. In our experiments, we use the optimistic planning model as an ablation to justify a potential cost for uncertainty, but it does not make the inference problem easier: We still need to solve the high-dimensional inference problem and find in each iteration the shortest path for solving the planning problem approximately.

Figure placement and referencing statistical analyses

We agree that figure placement is not optimal for reading. Due to space constraints, we had to distribute figures across pages. In the final version, due to the extra page, figures will land one page later, which should solve this issue. Additionally, as suggested, we will reference and briefly discuss the statistical analysis results from the appendix to improve clarity.

Figure 3 labeling and caption

As also noted by Reviewer 93XY, we will add a colorbar label to improve clarity. Our intention in using detailed figure captions was to make the paper easier to interpret through visual inspection. If clarity would be improved by integrating these details into the main text, we are happy to make that revision.

Definition of BAMDPs in Section 2.2

We based our definition of BAMDPs on the original work by Duff [1] and the survey by Ghavamzadeh et al. [2]. Both define BAMDPs in terms of uncertainty over transition dynamics. We agree that BAMDPs can be generalized to include uncertainty over other model parameters (e.g., rewards).

Relations to incremental state revelation

We agree with the reviewer that our formulation, in which states become "known" upon visitation, is indeed similar to incremental state revelation mechanisms used in exploration-focused RL algorithms such as $E^3$. We clarified this connection also in the comment to reviewer 93XY. The most important differences are that we consider the inverse problem and that, in our case, model uncertainty leads to aversion. We will make this connection clearer in the final version.

Clarifying "knowledge" as edges/transitions

Yes, "knowledge" in our model refers to information about the transitions (edges) in the environment. In many cognitive tasks, the goal (e.g., a target location) is explicit and known. The challenge lies in discovering or reasoning about how to reach them. Modeling knowledge over transitions allows us to infer what structural information agents incorporated into their plans. This enables us, for example, to investigate how topology influences awareness or memory in human planning. With that, our approach complements approaches like inverse RL, which aims at inferring goals. We will clarify this in the revised text.

References

[1] M. Duff (2002). Optimal Learning: Computational procedures for Bayes-adaptive Markov decision processes. PhD thesis, University of Massachusetts Amherst

[2] M. Ghavamzadeh, S. Mannor, J. Pineau, & A. Tamar (2015). Bayesian reinforcement learning: A survey. Foundations and Trends in Machine Learning, 8(5-6), 359-483

We thank the reviewer for their thoughtful and encouraging review. Below, we address the main concerns in detail.

Purpose and applicability of the results

We appreciate this opportunity to clarify the motivation and intended use of our method. Our work is situated in computational cognitive science, where the central goal is to explain observed behavior through computational models, and not just predict it. In many controlled navigation tasks, the goal is known, but the structure of the environment is either unknown, must be memorized, or is too complex for precise planning. As researchers interested in human planning, we would like to decode the information of the environment that is relevant for the specifically followed trajectory of a subject. With this, we can gain insights about transferability (which information did subjects transfer between tasks), spatial memory (which parts of the environment were present in the subject's memory), or awareness of certain parts of the environment when planning. Our method serves as a tool to infer precisely this information. As a concrete example, we are actively using this inference framework in ongoing work to analyze how subjects' awareness depends on topological features such as corridors or junctions when solving a maze under time pressure. Further, the method could be concretely used for investigating spatial memory by investigating which parts of a larger maze a subject remembered based on its local structure.

Generality and scalability

We acknowledge that our approach is scoped to discrete MDPs with uncertainty over transitions. However, to the best of our knowledge, this is the first approach that enables inference over high-dimensional knowledge states from behavioral data. In our experiments, we applied the method to a task with 169 binary latent variables, which corresponds to a belief space of size $2^{169}$. This is significantly beyond what existing knowledge inference techniques, such as Bayesian inverse planning, can handle. As mentioned above, this scalability allows practical application in controlled behavioral experiments. Smaller continuous domains could also be addressed via discretization. While scaling to more complex continuous environments remains an open challenge, we believe our work lays important groundwork for doing so.

Comparison to IRL

We did not include a direct comparison to IRL because our method and IRL infer fundamentally different quantities: IRL estimates preferences (e.g., a cost function), while our approach infers latent knowledge (i.e., beliefs about world structure). These are not directly comparable, especially since beliefs and rewards live in different spaces. That said, in terms of trajectory likelihoods ("performance"), we expect that IRL fits the observed trajectories equally well by assigning high rewards to visited states (e.g., when the agent turns). However, most would agree that this explanation would be less appropriate, as similarly illustrated by the airport example in our introduction. If the reviewer feels it would be helpful, we are happy to include a learned cost function plot via IRL in the appendix of the final version to further illustrate this point.

Clarification of Figure 3

Thank you for pointing out the missing label for the colorbar in Figure 3. We will add it in the revised version to improve clarity.

Posterior Variance in Figure 4

We already briefly discussed the high variance of likelihoods in the evaluation and future work section. The variance arises from the behavioral variability in the human experiment, which could be caused by inattentiveness, exploratory behavior, or higher-level learning. In Figure 13 (last three columns) in the appendix, we show representative examples of the collected human data. Many participants especially in worlds 6 and 7 do not follow the most "obvious" or direct path. This could be explained by the experience that these paths were oftentiimes blocked in previous mazes, so they avoided them. To minimize such effects, we included a diverse set of gridworlds (e.g., world 6, where the direct path is indeed the shortest) and introductory trials. Nevertheless, we were surprised by the high variability of behavior and consider this an interesting direction for future investigation.

We thank the reviewer for the detailed comments and the opportunity to clarify our contributions and modeling choices. We believe most concerns stem from a misunderstanding, and we are happy to clarify them below.

Dirichlet beliefs for exact inference about $K$

We appreciate the reviewer's thoughtful suggestion to use a Dirichlet prior over transitions, which is indeed the classical Bayesian RL approach for modeling planning under transition uncertainty. Our main goal, however, is not to model how the agent learns about the environment, but rather to infer what the agent already knew at the start of a given trajectory, which makes it an inverse problem.

In the reviewer's suggested formulation, our goal would be to infer the prior (which we term "knowledge") about state transitions based on a given trajectory, which the reviewer proposed to set to $\alpha_0 \ll 1$. This would require inference over the space of prior distributions, making the posterior a distribution over Dirichlet parameters. This inference problem cannot be addressed by conjugacy as the likelihood non-trivially depends on the initial knowledge via the agent's policy. With this formulation, it is not even clear how the agent's policy under the Dirichlet belief can be computed, which is required for evaluating the likelihood.

To avoid this complexity, we consider a simplified model: Instead of Dirichlet beliefs for each transition, we assume binary knowledge for each state: each state is either fully known or unknown (with respect to its transitions). In addition to the lower-dimensionality of the representation, this model is structurally advantageous for computation: First, since our belief about the agent's knowledge is modeled as Bernoulli random variables, we can evaluate the conditional distributions of one belief variable, given all the others, enabling the use of Gibbs sampling. Second, we can efficiently solve the planning problem by modeling it as a shortest path problem. Third, the combination of Gibbs sampling and shortest path formulation with dynamic shortest path algorithms ($D^*$ lite) can be leveraged to reuse intermediate results in the sampling process.

In summary:

• The prior $p(K)$ is over the agent’s initial knowledge $K$.
• The likelihood depends on the agent’s policy given that knowledge, which involves solving a planning problem.
• This planning problem depends non-trivially on the structure of $K$, making exact Bayesian inference intractable.
• We use Gibbs sampling not because information has been discarded, but because evaluating the posterior over knowledge states requires marginalizing over a large space.

Use of a single parameter $q$

The choice of a single parameter $q$ to model the probability of traversability of an unknown transition results from the simplified modeling choice that each state is either known (and its transitions are deterministic) or unknown (and transitions succeed with probability $q$). While this is a simplification, it is sufficient for many cognitive modeling tasks where we are interested in whether a subject takes into account certain information or not. Extending the model to allow an individual value for each transition would lead to the Dirichlet model again, which is not tractable. Nevertheless, in some cases, we can lift the restriction of a single $q$ to a certain degree, for example, when using different values for different structures in the maze, such as corridors and junctions.

Airport Example

We appreciate the feedback on the airport example in the introduction. The purpose of the example is not to argue that the environment is partially observable, but rather to illustrate why inferring the agent's prior knowledge is crucial for interpreting behavior. The external observer has access to the complete environment, including the construction blockage. However, the agent's detour into the blocked road only makes sense in this environment if we assume that the agent did not know about the construction in advance. This illustrates the type of inference our method performs.

Typo in line 129

Thank you for pointing this out. Indeed, $s'$ should be $s_j$ to correctly reference the knowledge of that state. It captures the idea that either the predecessor or successor must be known to know a transition.

Connection to $E^3$ algorithm

We appreciate the reviewer's insight regarding the connection to the $E^3$ algorithm. Our planning model indeed shares the idea of separating known and unknown states, but there are also important differences: In $E^3$, unknown states lead to an absorbing state with maximal reward, which incentivizes exploration. In our model, in contrast, unknown states are traversable with probability $q$, while with probability $1 - q$, the agent stays in the same state. This leads to uncertainty aversion, rather than exploration. We will include this comparison in the revised version to help readers better contextualize our approach.

Suitability for NeurIPS

We respectfully disagree with the claim that our work is a poor fit for NeurIPS. NeurIPS has long welcomed interdisciplinary contributions that combine machine learning with cognitive science, neuroscience, and related fields. As stated in the call for papers, topics include "Neuroscience and cognitive science (e.g., neural coding, brain-computer interfaces)" alongside "Reinforcement learning (e.g., decision and control, planning, hierarchical RL, robotics)". Our work lies at the intersection of reinforcement learning, Bayesian inference, and cognitive modeling. Several recent NeurIPS papers (see references [1-4] below) tackle similar questions on models for navigation and control. We therefore believe it contributes meaningfully to the NeurIPS community.

References

[1] Zhi-Xuan, T., Mann, J., Silver, T., Tenenbaum, J., & Mansinghka, V. (2020). Online Bayesian goal inference for boundedly rational planning agents. Advances in neural information processing systems, 33, 19238-19250.

[2] Binz, M., & Schulz, E. (2022). Modeling human exploration through resource-rational reinforcement learning. Advances in neural information processing systems, 35, 31755-31768.

[3] Chandra, K., Chen, T., Li, T. M., Ragan-Kelley, J., & Tenenbaum, J. (2023). Inferring the future by imagining the past. Advances in Neural Information Processing Systems, 36, 21196-21216.

[4] Damiani, F., Anzai, A., Drugowitsch, J., DeAngelis, G., & Moreno Bote, R. (2024). Stochastic optimal control and estimation with multiplicative and internal noise. Advances in Neural Information Processing Systems, 37, 123291-123327.