Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors try to model how humans explore novel environments. The main hypothesis tested in the paper is that humans think of maps of unseen places as compositions of submaps in observed areas. Towards this, the authors propose a new "Map Induction Task" (MIT) to study how humans explore novel maps. Additionally, they try to model the exploration behavior exhibited by humans as a hierarchical bayesian generative framework which generates a distribution over possible maps given past observations, and use this distribution to plan. They present results on their  task (MIT) which validate the aforementioned hypothesis
main_review: **Strengths:**

- While there are multiple heuristic / learnt models for exploration of novel spaces, modeling how humans explore novel environments is an interesting area of research. In this paper, the authors present an interesting take on this problem by treating it as program induction — inferring the program that will lead to a correct map of the environment based on past observations.
- The experimental setup and inferences made through the experiments were easy to grasp and made sense to me. The experiments were designed to test the two main hypothesis (1. Does humans rely on some sort of map induction for exploration as opposed to uniformly visiting all the map regions? 2) Do humans seek information about the task to score different possible map completion hypotheses?)

**Weaknesses:**

- A major concern for this paper is that the task was designed keeping the hypothesis is mind. For instance, the maps and 3D environments are synthetically constructed such that they have repeated blocks. Given that the environments were created to have repeatability, humans performing the task will obviously pickup on that signal. It would have been better if the experiment was conducted using publicly available layouts (3D scans like Gibson, Matterport etc).
- On a related note, the environments are composed of simple units and are almost grid-world like. For such environments, production rules (Table 1) used to generate map hypotheses are simple. Can the authors comment on how this will generalize to generic environments which might have fairly arbitrary layouts?

**Updates after Rebuttal**
Thank you authors for your responses and clarifications to my concerns. I think the hypotheses presented in the paper are interesting and are tested appropriately. Even though the paper lacks experiments on more complicated environments such as Gibson, Matterport, I think the ideas presented in the paper are good first steps and might be useful to the broader community (including myself). Thus, I am happy to update my scores. 
summary_of_the_review: The authors present an interesting hypothesis regarding modeling human exploration behavior. However, I am not convinced that the experimental setup captures general human exploration. The experimental setup were synthetically created to have repeatability and doesn't capture the general layouts (of indoor spaces or otherwise). Thus, I am not convinced that these hypotheses will hold true when tested on realistic environments.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work is motivated by the hypothesis that humans maintain a hierarchical spatial representation when exploring new environments, such that shared patterns (due to the hierarchy) between spatial regions can be used to predict how still unvisited places would look. A simple discrete 2D computational model based on probabilistic program induction is proposed for predicting the map at yet unseen places. The model assumes a discrete set of possible transformations (flips, rotations, concatenations, etc.) of small extracted regions (submaps of previous observations), based on which a distribution over possible completions of empty map regions can be formulated.

A control task is then considered, in which an agent needs to explore a completely new environment and collect rewards (tokens) in the process. Under strong structural assumptions for the test environments (e.g. it is ensured that patterns actually repeat in a very uniform way, rooms look the same, rewards are placed consistently, etc.), it is shown that model-based planning under the map-induction model results in more efficient exploration & reward-collection behavior. Furthermore, a study with actual human subjects is conducted where they need to solve the same task. Results suggest that real-life exploration behavior is consistent with the most expressive version of the proposed computational model, where a full distribution over possible map completions is maintained (as opposed to a MAP estimate or an uninformed model).

main_review: ## Strengths

- The experiments are tailored to the main hypothesis of the paper and manage to highlight the argued points well. It is evident that exploration is more efficient under the assumed computational model when solving the reward collection task, which indicates that the map induction is indeed informing the planner.
- The conducted real-life study also seems well-constructed. The results in fig. 4, d) and fig. 5, d) support the idea that a fully-probabilistic map induction model comes closer to human behavior than an uninformed / a point-estimated (MAP) one.
- The presented figures are legible and convey the message of the paper well.

## Weaknesses

- The considered environments are very simplified and exhibit very regular structures (repeating patterns). This is understandable, they are tailored to the proposed hypothesis and highlight the arguments made in the paper, they are also useful for comparing human behavior to the computational model. However, I cannot judge how well the presented arguments would extrapolate to more realistic (natural) environments, where e.g. repetition patterns & regularities are much less obvious.
- I find the claim in the abstract that the proposed approach outperforms state-of-the-art planning algorithms to be overstated (largely because of the previous point).
- Since everything is discrete and because of the combinatorial nature of map induction, the cardinality of the space over possible maps will quickly explode. This is acknowledged in the conclusion, but I am not sure if a discretized approach like program induction will scale well, even if shorter programs are considered (it can hurt planning performance). Have you considered some form of continuous relaxations?
- I think the section on the assumed computational model can be improved, right now it lacks a rigorous specification of the assumed joint distribution / probabilistic model of all variables in question (e.g. how the factorization looks, initial prior on the map, etc.).
- In section 3.1.4, the POMDP is introduced with a state-space that captures both agent states & map hypotheses. In that context, I find the verbal description of the assumed transition model confusing: it implies normalizing the map hypothesis distribution after a movement action is executed. Can you clarify why this is necessary? I think the clarity of this section would be better if the assumed transition model is explicitly specified (in terms of a conditional distribution).
- Is the likelihood in section 3.1.3. a well-defined distribution? It needs to integrate to 1 over the space of possible observations D (which should be discrete), but based on the description it seems like there can be many observations for which it evaluates to 1 (e.g. if $\beta$ and $\gamma$ are 0).
- Ideally, I would like to see visitation heatmaps from the computational model next to the ones in fig. 4 and fig. 5 from the real-life study, to judge whether the visitation patterns are similar / where they differ. The aggregated results in fig 4. c) d) and fig 5. c) d) somewhat obfuscate the comparison.

summary_of_the_review: I find the idea of the paper interesting, and I think the selected suite of experiments highlights the points the paper makes rather well. However, I cannot tell if the insights about map induction would extrapolate to more realistic cases, as the considered environments are very regular & specific in their repeating patterns, applicability might be limited. I also think the clarity of the model specification & the assumed probabilistic assumptions can be improved, I listed my main concerns in the main review.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper tests a hypothesis of how humans choose the path to explore and maximize reward in unvisited space based on their past experience. The central hypothesis is that human uses program induction to generate prediction of possible spatial map. Based on human behavior in two experiments, the paper further compared different models of map prediction, and demonstrated that humans actually consider the distribution of possible maps instead of only consider the most likely map.


main_review: Although it is a work focused on how humans plan and predict unseen space, it provides good inspiration for artificial intelligence. The work is novel, as program induction has not been applied to map prediction and spatial planning before. I believe it will also inspire much more in-depth experimental works.
One minor concern I have is about the experimental design and analysis: when participants visit mirrored environments, they may recognize it is an mirror image of a previously learned environment, and thus the predicted distribution of map may be different from when they first see that environment. It was not clear to me whether mirroring of a previously learned environment is part of the program induction, as I suppose most of the modeling is performed within game instead of across game. Please clarify this. 
Further, due to the above reason, it seems less justified to combine the result of first visit of an environment and the visit of its mirror environment. It would be good to plot heatmaps for them separately in the appendix.

An illustration of how the authors manually breaking each map into a set of convex rooms is necessary for understanding the model fitting. Is the model likelihood geometric or arithmetic average of the predicted probability of humans' next room visitation across all convex rooms (last sentence of A.3)?


It was not super intuitive for me why D-POMCP would predict better than MAP-POMCP in experiment 2. Is it mainly because the reward locations themselves cannot be deterministically predicted as in Experiment 1? 
Is there any component of softmax in the model's policy for choosing routes? If not, where does stochasticity come from in the predicted distribution of visitation by the models? If yes, will D-POMCP still win when the softmax temperature or epsilon-greedy are free parameters?

Are there any free parameters being tuned to fit data? If yes, what are they?
summary_of_the_review: The paper appears to be generally interesting and novel. Perhaps because of the page limit, not enough details that would be expected for a human behavioral modeling are provided, and I hope they can be added during revision.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper investigates the concept of map induction for exploration in novel environments. This is an important problem for robotics applications, relevant for scaling up navigation of autonomous systems to large environments and for exploring unknown environments. 

The article's main contribution is a new task and a set of experiments to evaluate the central hypothesis: "that humans use program induction to infer possible maps of unseen spaces, as made up of submaps encountered in the observed areas".

This is evaluated by proposing a novel map induction task that is the main contribution of the paper, as well as a set of probabilistic models that implement the different hypotheses considered in the paper. 
main_review: The article is well written and clear, providing a good motivation for the work and an good review of the related literature. I have on the other hand some concerns about the suitability of this paper for this conference and the methodology. 

Although the author claim the dual goal of: "(1) to empirically study how humans learn spatial representations using a novel experimental Map Induction Task, and (2) describe a computational model of map induction that can be leveraged to optimize exploration in AI", point (2) is not really elaborated in the paper, nor does the paper provide experimental evidence to this claim.

Therefore, my first concern with this paper, is that this is effectively a Psychology article. There is nothing wrong with that of course, but the hypothesis, its relation to prior literature and methodology ought to be reviewed by an expert in the field.
For example, it is difficult for me to judge how well the results obtained on the proposed task would apply more broadly to human cognition in the real world. Although the literature review is generally good, a better discussion of how the paper's hypothesis fits with existing theories and previous experimental results would be useful. 

The second concern is methodoligical. Although several hypotheses are mentioned in the text of the article, it is not clear how those hypotheses are supported from either the literature or experiments. For example: 
- "We hypothesize that humans represent survey knowledge as composed of regions" [p. 3]
- "We hypothesize that while navigating novel environments, humans approximately infer a posterior distribution p(M|D) over its possible maps..." [p.5]
- "humans prefer map completions that are maximally descriptive of unseen portions of the environment" [p.6]
- "humans prefer map hypotheses that are minimally contradictory with previous observations." [p.6]
How confident are the authors that those assumptions hold, and what would be the consequence for their experimental results if they did not? 

Moreover, the experimental results do not seem to clearly provide the evidence to support or discard the hypothesis. No hypothesis testing is provided. Concerning the number of participants in each experiment: Why using such a small number of participants if using Amazon mechanical Turk? Are the authors confident that this number is sufficient to prove/disprove the hypothesis? 
summary_of_the_review: In summary, the paper is generally well written and tackling and interesting question. The proposed task is interesting, but I am concerned that the paper does not provide a clear argument that the proposed methodology and analysis actually prove the hypothesis. 
- This paper is mainly a Psychology study (as the computational model for AI part of the claims is not really demonstrated), and ought to be reviewed by an expert in experimental psychology. 
- The analysis of the result does not provide clear evidence that the hypothesis is true
- The hypothesis should be framed more clearly with the existing literature, existing hypotheses of human spatial cognition and prior experimental evidence using established tasks.
review_title: null

Meta-review: This paper presents a hierarchical Bayesian approach to exploration in grid worlds.  The paper considers the hypothesis that humans maintain a hierarchical representation when exploring a space, where the distribution over unknown space can be modeled with a structured probabilistic program.  The paper compares the behavior of people during exploration tasks to the behavior of a Bayesian model under different distributional approximations.  The results indicate that people can behave similarly to a sophisticated Bayesian model on small grid world domains.

The reviews highlighted several concerns about the paper.  One initial concern was that the experimental domain is too simple and small compared to real world environments encountered by robots or humans.  However, this work is similar in scope to other exploration work in reinforcement learning and psychology studies, where tiny grid worlds are still commonly used to gather insight.  Thus, this concern does not reduce the potential contribution of the paper.  The reviewers raised several other concerns about the work that were largely addressed by the author response.  The remaining reviewer concerns centered on the limited strength of the evidence in the experiments, but the reviewers expect the paper will still be of interest to the broader research community.

Four reviewers indicate to accept this paper for its contribution of a study into the use of probabilistic program induction to infer possible completions of maps in small environments.  The paper is therefore accepted.
Decision: Accept (Poster)