summaries: This paper considers design choices involved in offline RL approaches that consider a reduction to weighted/conditional behavior cloning, a class of approaches referred to as Reinforcement Learning via Supervised Learning (RvS). The paper studies various issues including expressivity of policy architecture, regularization, choice of conditioning variables (e.g. based on goals or rewards).   At a high level, the takeaways are (a) RvS approaches are successful when using neural networks with appropriate capacity and regularization, (b) with appropriate conditioning variables (goal/reward based conditioning), (c) RvS can obtain policies that exhibit compositional behavior by conditioning on appropriate events.

summaries: The paper investigates different variants of behavior cloning. The methods investigated aim at achieving better policies for use in offline RL through supervised learning than the average behavior contained in the data. The methods studied are categorized and examined against three to four benchmark problems.

summaries: The paper studies the behavior cloning based strategies of offline RL algorithms in different type of environments and reports that performance primarily depends on model size and regularization. The results contradict some of the earlier claims, and the authors conjecture that model size and regularization characteristics can explain past results. The paper also discusses additional insights such as the importance of conditioning and simple validation based evaluation fail to generalize.

summaries: This paper studies the importance of the design decisions for supervised learning type reinforcement learning algorithms. Through extensive experiments, find that more complex design choices, such as the large sequence models and value-based weighting schemes used in some prior works, are generally not necessary. Our results show that carefully designed RvS methods can attain results that match or exceed the best prior methods across a range of different offline RL benchmarks, including datasets with little or no optimal data.

abstractText: Offline reinforcement learning (RL) is typically tackled with value-based methods that rely on temporal difference (TD) learning. However, recent work has shown how the offline RL problem can be reduced to weighted, filtered, or conditional behavioral cloning problems. The main idea behind these methods is that data that is suboptimal for one task, such as achieving a certain reward of reaching a certain goal, may nonetheless be useful for learning to solve another task. These methods coerce suboptimal data into a form that allows supervised learning methods to acquire optimal policies. For example, any experience is optimal for learning to reach the final state in that experience. However, it remains unclear which ingredients are essential for such methods to work well, and when these methods do or do not work outperform value-based approximate dynamic programming algorithms. These methods, which we collectively refer to as reinforcement learning via supervised learning (RvS), involve a number of design decisions, such as policy architectures and how the conditioning variable is constructed. Through extensive experiments, this paper studies the importance of these design decisions. The most important design decisions boil down to carefully choosing model capacity (e.g., via regularization or architecture) and choosing which information to condition on (e.g., goals or rewards). Our experiments find that more complex design choices, such as the large sequence models and value-based weighting schemes used in prior work, are often not necessary. Our results show that carefully designed RvS methods can attain results that match or exceed the best prior methods across a range of different offline RL benchmarks, including datasets with little or no optimal data. Our results help to identify the limits of current RvS methods and identify some important open problems.

authors:
Rishabh Agarwal
Dale Schuurmans
Mohammad Norouzi

title: An optimistic perspective on offline reinforcement learning

venue: In International Conference on Machine Learning,

authors:
Michael Ahn
Henry Zhu
Kristian Hartikainen
Hugo Ponte
Abhishek Gupta
Sergey Levine
Vikash Kumar

title: ROBEL: RObotics BEnchmarks for Learning with low-cost robots

venue: In Conference on Robot Learning (CoRL),

authors:
Arthur Argenson
Gabriel Dulac-Arnold

title: Model-based offline planning

venue: arXiv preprint arXiv:2008.05556,

authors:
David Brandfonbrener
William F Whitney
Rajesh Ranganath
Joan Bruna

title: Offline RL without off-policy evaluation

venue: arXiv preprint arXiv:2106.08909,

authors:
Lili Chen
Kevin Lu
Aravind Rajeswaran
Kimin Lee
Aditya Grover
Michael Laskin
Pieter Abbeel
Aravind Srinivas
Igor Mordatch

title: Decision transformer: Reinforcement learning via sequence modeling

authors:
Felipe Codevilla
Matthias Müller
Antonio López
Vladlen Koltun
Alexey Dosovitskiy

title: End-to-end driving via conditional imitation learning

venue: IEEE International Conference on Robotics and Automation (ICRA),

authors:
Stefan Depeweg
José Miguel Hernández-Lobato
Finale Doshi-Velez
Steffen Udluft

title: Learning and policy search in stochastic dynamical systems with bayesian neural networks

venue: In International Conference on Learning Representations (ICLR

authors:
Yiming Ding
Carlos Florensa
Pieter Abbeel
Mariano Phielipp

title: Goal-conditioned imitation learning

venue: In Advances in Neural Information Processing Systems,

authors:
Ben Eysenbach
Russ R Salakhutdinov
Sergey Levine

title: Search on the replay buffer: Bridging planning and reinforcement learning

authors:
Benjamin Eysenbach
Xinyang Geng
Sergey Levine
Ruslan Salakhutdinov

title: Rewriting history with inverse RL: hindsight inference for policy improvement

authors:
Justin Fu
Katie Luo
Sergey Levine

title: Learning robust rewards with adversarial inverse reinforcement learning

venue: arXiv preprint arXiv:1710.11248,

authors:
Justin Fu
Aviral Kumar
Ofir Nachum
George Tucker
Sergey Levine

title: D4rl: Datasets for deep data-driven reinforcement learning

venue: arXiv preprint arXiv:2004.07219,

authors:
Justin Fu
Mohammad Norouzi
Ofir Nachum
George Tucker
ziyu wang
Alexander Novikov
Mengjiao Yang
Michael R Zhang
Yutian Chen
Aviral Kumar
Cosmin Paduraru
Sergey Levine
Thomas Paine

title: Benchmarks for deep off-policy evaluation

venue: In International Conference on Learning Representations,

authors:
Scott Fujimoto
Shixiang Shane Gu

title: A minimalist approach to offline reinforcement learning

venue: arXiv preprint arXiv:2106.06860,

authors:
Scott Fujimoto
David Meger
Doina Precup

title: Off-policy deep reinforcement learning without exploration

authors:
Behrooz Ghorbani
Orhan Firat
Markus Freitag
Ankur Bapna
Maxim Krikun
Xavier Garcia
Ciprian Chelba
Colin Cherry

title: Scaling laws for neural machine translation

venue: arXiv preprint arXiv:2109.07740,

authors:
Dibya Ghosh
Abhishek Gupta
Sergey Levine

title: Learning actionable representations with goal conditioned policies

authors:
Dibya Ghosh
Abhishek Gupta
Ashwin Reddy
Justin Fu
Coline Manon Devin
Benjamin Eysenbach
Sergey Levine

title: Learning to reach goals via iterated supervised learning

authors:
Abhishek Gupta
Vikash Kumar
Corey Lynch
Sergey Levine
Karol Hausman

title: Relay policy learning: Solving long-horizon tasks via imitation and reinforcement learning

venue: In Conference on Robot Learning,

authors:
Jeffrey Hawke
Richard Shen
Corina Gurau
Siddharth Sharma
Daniele Reda
Nikolay Nikolov
Przemysław Mazur
Sean Micklethwaite
Nicolas Griffiths
Amar Shah

title: Urban driving with conditional imitation learning

authors:
Jonathan Ho
Stefano Ermon

title: Generative adversarial imitation learning

venue: Advances in neural information processing systems,

authors:
Michael Janner
Qiyang Li
Sergey Levine

title: Reinforcement learning as one big sequence modeling problem

venue: arXiv preprint arXiv:2106.02039,

authors:
Rahul Kidambi
Aravind Rajeswaran
Praneeth Netrapalli
Thorsten Joachims

title: MOReL: Model-based offline reinforcement learning

venue: arXiv preprint arXiv:2005.05951,

authors:
Aviral Kumar
Aurick Zhou
George Tucker
Sergey Levine

title: Conservative Q-learning for offline reinforcement learning

venue: Advances in Neural Information Processing Systems,

authors:
Timothy P Lillicrap
Jonathan J Hunt
Alexander Pritzel
Nicolas Heess
Tom Erez
Yuval Tassa
David Silver
Daan Wierstra

title: Continuous control with deep reinforcement learning

venue: arXiv preprint arXiv:1509.02971,

authors:
Corey Lynch
Mohi Khansari
Ted Xiao
Vikash Kumar
Jonathan Tompson
Sergey Levine
Pierre Sermanet

title: Learning latent plans from play

authors:
Ashvin V Nair
Vitchyr Pong
Murtaza Dalal
Shikhar Bahl
Steven Lin
Sergey Levine

title: Visual reinforcement learning with imagined goals

authors:
Gerhard Neumann
Jan Peters

title: Fitted Q-iteration by advantage weighted regression

venue: In Advances in Neural Information Processing Systems 21-Proceedings of the 2008 Conference,

authors:
Tom Le Paine
Cosmin Paduraru
Andrea Michi
Caglar Gulcehre
Konrad Zolna
Alexander Novikov
Ziyu Wang
Nando de Freitas

title: Hyperparameter selection for offline reinforcement learning

authors:
Xue Bin Peng
Aviral Kumar
Grace Zhang
Sergey Levine

title: Advantage-weighted regression: Simple and scalable off-policy reinforcement learning

title: Reinforcement learning upside down: Don’t predict rewards–just map them to actions

venue: arXiv preprint arXiv:1912.02875,

authors:
Jian Shen
Mingcheng Chen
Zhicheng Zhang
Zhengyu Yang
Weinan Zhang
Yong Yu

title: Model-based offline policy optimization with distribution correcting regularization

venue: In Joint European Conference on Machine Learning and Knowledge Discovery in Databases,

authors:
Rupesh Kumar Srivastava
Pranav Shyam
Filipe Mutz
Wojciech Jaśkowski
Jürgen Schmidhuber

title: Training agents using upside-down reinforcement learning

authors:
Phillip Swazinna
Steffen Udluft
Thomas Runkler

title: Overcoming model bias for robust offline deep reinforcement learning

venue: Engineering Applications of Artificial Intelligence,

authors:
Michael Tschannen
Josip Djolonga
Paul K. Rubenstein
Sylvain Gelly
Mario Lucic

title: On mutual information maximization for representation learning

authors:
Yue Wu
Shuangfei Zhai
Nitish Srivastava
Joshua Susskind
Jian Zhang
Ruslan Salakhutdinov
Hanlin Goh

title: Uncertainty weighted actor-critic for offline reinforcement learning

venue: arXiv preprint arXiv:2105.08140,

authors:
Tianhe Yu
Garrett Thomas
Lantao Yu
Stefano Ermon
James Zou
Sergey Levine
Chelsea Finn
Tengyu Ma

title: MOPO: Model-based offline policy optimization

venue: arXiv preprint arXiv:2005.13239,

heading: 1 INTRODUCTION

text:
Offline and off-policy reinforcement learning (RL) is typically addressed using value-based methods. While conceptually simple, such methods can be difficult to apply in practice and tend to require a complex tricks to stabilize learning and delicate tuning of many hyperparameters. Recent work has explored an appealing alternative approach: convert the RL problem into a conditional, filtered, or weighted imitation learning problem. Such methods typically use a simple insight: experience that may be suboptimal for one task may be optimal for another task. By conditioning on some piece of information, such as a goal, reward function parameterization, or reward value, such experience can be used for simple behavior cloning (Codevilla et al., 2018; Lynch et al., 2020; Ding et al., 2019; Srivastava et al., 2019; Ghosh et al., 2018; Peng et al., 2019; Neumann et al., 2009; Kumar et al., 2019; Eysenbach et al., 2020; Chen et al., 2021; Janner et al., 2021). We will refer to this set of approaches as RL VIA SUPERVISED LEARNING (RVS). These approaches most commonly conditioning on goals (Lynch et al., 2020; Codevilla et al., 2018; Ghosh et al., 2021) or reward values (Kumar et al., 2019; Srivastava et al., 2019; Chen et al., 2021), though they can also involve reweighting or filtering (Eysenbach et al., 2020; Neumann et al., 2009; Peng et al., 2019; Kumar et al., 2019).
RvS methods are appealing because of their algorithmic simplicity. However, prior works have put forward conflicting hypotheses about which factors are essential for their good performance, including online data (Ghosh et al., 2021), weighting (Kumar et al., 2019), or large Transformer sequence models (Chen et al., 2021). It remains unclear where, how, and why they work well.
Therefore, the first and most important question we aim to study is: what elements are essential for effective RvS learning? Answering this question may help users understand when RvS methods are a generally-applicable replacement for dynamic programming methods. Beyond this, it also remains unclear how or when such methods can effectively exploit temporal compositionality. Dynamic programming methods can make use of this effectively, and it is important for offline RL tasks where few near-optimal trajectories are present in the dataset, as for example in the Ant Maze tasks in D4RL (Fu et al., 2020). Therefore, the second question we aim to answer is: what are the limits of RvS learning, and does it scale effectively to settings that contain few near-optimal trajectories?
Our focus is not on proposing new RvS algorithms, but rather on empirically investigating the design decisions, performance, and limits of such methods. Prior works have proposed a number of factors for improving the performance of RvS learning methods, such as filtering or weighting (Kumar et al., 2019), high-coverage “play” data (Lynch et al., 2020), online collection (Ghosh et al., 2021), or the use of large Transformer models (Chen et al., 2021; Janner et al., 2021). Our first result is that, based mostly on careful adjustment of model capacity (e.g., via regularization), simple feedforward models can match the performance of more complex and computationally expensive sequence models from prior work across a wide range of tasks. Our second result is that choosing to condition on reward values versus goals can have a large effect on performance, with different choices working better in different domains.
The main contribution of this paper is a study of RvS methods on a wide range of offline RL problems, as well as a set of analyses about which design factors matter most for such methods. We show that relatively simple network designs can, in many cases, perform as well (or better than) both state-of-the-art offline RL algorithms and more complex architectures, if tuned correctly to have the right capacity. While this may be unsurprising, it contradicts hypotheses put forward in several prior works (Kumar et al., 2019; Chen et al., 2021). Additionally, to our knowledge the results that we demonstrate exceed, on average, previously reported results for any RvS method, when considered across the full range of tasks. We believe that these findings will be useful to the RL community, because they help to understand the essential ingredients and limitations of RvS methods, and provide a foundation for future work on simple and performant offline RL algorithms.

heading: 2 RELATED WORK

text: Recent offline RL methods use many algorithmic techniques, including value functions (Kumar et al., 2020; Fujimoto et al., 2019), dynamics estimation alongisde value functions (Yu et al., 2020; Shen et al., 2021; Kidambi et al., 2020), dynamics estimation alone (Depeweg et al., 2017; Argenson & Dulac-Arnold, 2020; Swazinna et al., 2021), and uncertainty quantification (Agarwal et al., 2020; Wu et al., 2021; Yu et al., 2020). In this paper, we focus on a class of offline RL methods based on conditional behavior cloning that avoid value functions entirely. The most common instantiation of these methods are goal-conditioned behavior cloning (Ghosh et al., 2021; Lynch et al., 2020; Ding et al., 2019) and reward-conditioned behavior cloning (Kumar et al., 2019; Srivastava et al., 2019; Schmidhuber, 2019). Prior work has also looked at conditioning on different information, such as entire trajectories (Chen et al., 2021; Janner et al., 2021), tasks inferred by inverse RL (Eysenbach et al., 2020), and other task information (Codevilla et al., 2018; Hawke et al., 2020). These methods all eschew value estimation and instead solve a supervised regression problem that resembles behavioral cloning. While these methods can, in theory, be directly applied to the offline RL setting, some prior works only evaluate these methods with combined with iterative data collection (Srivastava et al., 2019; Ghosh et al., 2021), which is not permitted in the typical offline RL setting. Kumar et al. (2019) study reward-conditioned policies and do present experiments in the offline RL setting. However, in contrast with our work, the results from Kumar et al. (2019) suggest that good performance cannot be achieved through RvS learning but only through additional advantageweighting (Neumann et al., 2009; Peng et al., 2019). More recent work (Chen et al., 2021) presents a conditional imitation learning method for the offline RL setting that avoids advantage weighting by introducing a higher capacity, autoregressive Transformer policy. In contrast to these prior works, we find that suitable design decisions in training enable simple conditioning with standard feedforward networks to attain state-of-the-art results across a range of offline RL benchmarks, without advantage weighting or high-capacity sequence models.

heading: 3 REINFORCEMENT LEARNING VIA SUPERVISED LEARNING

text:
Algorithm 1 RvS-Learning 1: Input: Dataset of trajectories, D = {τ} 2: Initialize policy π(a | s, ω). 3: while not converged do 4: Randomly sample trajectories: τ ∼ D. 5: Sample time index for each trajetory, t ∼ [1, H], and
sample a corresponding outcome: ω ∼ f(τt:H). 6: Compute loss: L(ω)← ∑ (st,at,ω)
log πθ(at | st, ω) 7: Update policy parameters: ω ← ω + η∇θL(θ) 8: end while 9: return Conditional policy π(a | s, ω) In this section, we will describe a formulation of reinforcement learning via supervised learning. While we will refer to these methods as “RvS learning” methods, we emphasize that we are not proposing any new algorithm, but rather summarizing existing methods under one common framework. In our experiments section, we will discuss the specific design decisions that we find important to make such methods work well. To formulate RvS methods in a general way, we assume an agent interacts with a Markov decision process with states st, actions at, initial state distribution ps(s1), and dynamics p(st+1 | st, at). We assume that the agent chooses actions using a policy πθ(at | st), parameterized by θ. For simplicity, we assume episodes have fixed length H , and use τ = (s1, a1, r1, s2, a2, r2, · · · ) to denote a trajectory of experience. As some trajectories might be described using multiple outcomes, we will use f(ω | τ) to denote the distribution over outcomes that occur in this trajectory. We will study two types of outcomes. The first type of outcome is a state (ω ∈ S) that the agent visits in the future: f(ω | τt:H) = Unif(st+1, st+2, · · · , sH). We will refer to RvS methods that learn goal-conditioned policies as goal-conditioned behavior cloning (GCBC). The second type of outcome is the average return (ω ∈ R) achieved over some future number of time steps: f(ω | τt:H) = 1(ω = 1H−t+1 ∑H t′=t r(st′ , at′)). We will refer to RvS methods that learn rewardconditioned policies as reward-conditioned behavior cloning (RCBC). It is also possible to condition on other information, such as the parameters of a reward function inferred via inverse RL (Eysenbach et al., 2020) or the parameters of a task, such as turning left or right (Codevilla et al., 2018). We will focus on RvS methods applied to the offline RL setting. These methods take as input a dataset of experience,D = {τ}, and output an outcome-conditioned policy, πθ(at | st, ω), which as in (Ghosh et al., 2021) is the solution to the following optimization problem:
max θ
1
|D|H For all trajectories:∑ τ∈D For all states in that trajectory:∑ 1≤t≤|τ | E For all achieved outcomes: ω∼f(ω|τt:H)[log πθ(at | st, ω)]. (1)
While the basic formulation of this conditional policy is simple, instantiating RvS methods that attain excellent results has proven challenging (Kumar et al., 2019; Srivastava et al., 2019). In the remainder of this paper, we will present an empirical analysis of the design choices in RvS methods. Specifically, we will aim to understand which design choices are needed to make RvS methods perform well on benchmark tasks, including how two different choices for ω (goal and
reward values) compare in practice across diverse tasks and datasets with varying levels of optimality (random, mixed, and expert). We will first describe our tasks and datasets in Section 4, discuss various design choices in Section 5, and then present comparisons and analysis in Section 6.

heading: 4 TASKS AND DATASETS

text:
To provide a detailed and comprehensive empirical study of RvS methods, we selected a broad range of tasks; prior works that proposed various types of RvS or conditional imitation methods typically focused on only a narrow subset of the domains we consider (Kumar et al., 2019; Ghosh et al., 2021; Chen et al., 2021). Our goal will be to include domains and datasets that: (1) are appropriate for different types of conditioning, including goals and rewards; (2) datasets that include different proportions of near-optimal data, ranging from near-expert datasets to ones with very few or no optimal trajectories at all; (3) datasets that run the gamut in terms of task dimensionality; (4) domains that have been heavily studied and compared on by prior value-based offline RL methods, thus offering a calibrated point of comparison.
GCSL is a suite of goal-conditioned environments used by Ghosh et al. (2021) to evaluate GCSL, a goal-conditioned RvS method with online data collection. We adapt these tasks for offline RL by using a random policy to collect training data, which results in suboptimal trajectories. The tasks include 2D navigation with obstacles (FourRooms, Eysenbach et al. (2019)), two end-effector controlled Sawyer robotic arm tasks (Door and Pusher, Nair et al. (2018)), the Lunar Lander video game that requires controlling thrusters to land a simulated Lunar Excursion Module (Lander), and a task that requires rotating a valve with a robotic claw (Claw, Ahn et al. (2019)).
Gym locomotion tasks consist of the HalfCheetah, Hopper, and Walker datasets from the D4RL offline RL benchmark (Fu et al., 2020). We use the random, medium, medium-expert, and medium-replay datasets in our evaluations, which consist of (a mixture of different) policies with different levels of suboptimality. Although these tasks are difficult for direct behavior cloning, they can be solved effectively by both RvS and a more naı̈ve filtered BC method.
Franka Kitchen is a 9-DoF robotic manipulation task, paired with a dataset of human demonstrations. This task originates from Gupta et al. (2020) and was formalized as an offline RL task in D4RL (Fu et al., 2020). Solving these tasks requires composing multi-step behaviors (e.g., open the microwave, then flip a switch) from component skills. This task includes three datasets: complete, which solves all tasks in order, partial, where only a subset of trajectories perform the desired tasks in order, and mixed, which contains all subtasks but never in the right order, requiring generalization and temporal composition. We will see that various methods compare differently on these tasks than on the Gym locomotion tasks.
Antmaze involves controlling a 8-DoF quadruped to navigate from a particular goal state. This benchmark task, from D4RL (Fu et al., 2020), evaluates an agent’s ability to learn trajectory stitching from a non-Markovian demonstrator policy. There are three mazes of increasing size: umaze, medium, and large. The data consists of trajectories that traverse between different start-goal pairs, with medium including few trajectories from the “real” task start to the goal, and large including none at all. Prior work has proposed that, with such tasks, dynamic programming with value-based methods should be particularly important (Fu et al., 2020), as extracting near-optimal behavior requires understanding temporal compositionality (“stitching”). We indeed find that, compared to the other environments, Antmaze results in different tradeoffs between methods.
When applying RvS learning methods, one must choose a particular type of outcome, such as rewards or goals. Whenever possible, we report numbers for both goal conditioning (RvS-G) and reward conditioning (RvS-R). We note that in Kitchen and AntMaze, we condition on the goal state that defines the underlying reward function (all the subtasks completed in the kitchen, and the goal location in the maze); this makes the additional assumption that we know how the reward function is defined, rather than just receiving samples from the reward function. Because GCSL is inherently a multitask, goal-conditioned setup, we omit reward conditioning and only report RvS-G; conversely, because there is no clear way to define performance in Gym w.r.t. a goal, we omit goal conditioning and only report RvS-R. For all tasks, we report scores in the range [0, 100]. For GCSL, the score corresponds to the percentage of episodes in which the agent achieves the goal. In the other environments, we follow Fu et al. (2020) and normalize the score according to 100 · return−randomexpert−random .

heading: 5 ARCHITECTURE, CAPACITY, AND REGULARIZATION

text:
We will instantiate the RvS framework in Section 3 using simple feedforward, fully-connected neural networks, conditioning on either the reward-to-go (Kumar et al., 2019; Srivastava et al., 2019) or a goal state (Lynch et al., 2020; Gupta et al., 2020; Ghosh et al., 2021). Our aim is specifically to identify the essential components of such methods, and we will eschew more complex architectures, such as Transformer sequence models (Chen et al., 2021). We will show that on the tasks we consider, we can achieve competitive performance without these components. However, we will show that a number of seemingly minor choices in the architecture design matter a great deal for final performance. Most of these choices revolve around tuning capacity and regularization, suggesting that overfitting and underfitting are major challenges for RvS; we discuss them below. Additionally, we will discuss in Section 6 how the choice of what to condition on (goals and rewards) also has important and domain-specific repercussions.
Capacity and regularization. In Figure 2, we compare different architecture sizes and regularization settings on a single task arbitrarily chosen from each task suite. The best-performing architectures are generally larger than the architectures used in standard online RL (Lillicrap et al., 2015) and imitation learning (Ho & Ermon, 2016; Fu et al., 2017). This conclusion is intuitive, since RvS policies must learn not only the optimal policy but also the policies for other conditioning values (e.g., other goals or suboptimal rewards). This result may help explain the contradictory conclusions from prior work regarding the importance of more complex design decisions (Kumar et al., 2019; Chen et al., 2021). The results in Figure 2 also highlight the importance of regularization: in some tasks, like pusher and kitchen-complete, dropout improves performance, while for others, like halfcheetah-medium-expert, dropout worsens performance.
Qualitatively, kitchen-complete is the smallest dataset and it contains human demonstrations, which prior work has found is especially hard to fit (relative to artificial demonstrations). On the other hand, halfcheetah-medium-expert is a large dataset that (by construction) only has two modes. So it is not surprising that this data is easiest to fit. While pusher has lots of data, it is of random trajectories. We conjecture that regularization helps smooth out the randomness in the pusher demonstrations. More generally, while our observations about model size and regularization may appear contradictory, we speculate that the issue might come down to the fact that RvS methods must fit a complex action distribution (due to conditioning) while still being regularized well enough to generalize over the goals or reward targets.
Output distributions. The form of the policy’s output distribution also influences the policy’s capacity. With continuous actions, unimodal Gaussians are a common choice,but discretization of
the action space allows representing complex, multi-modal conditional distributions (Lynch et al., 2020; Ghosh et al., 2021). To study the importance of the policy output distribution, we use the lowdimensional GCSL environments, where we can discretize the full action space. Figure 3 shows that discretized output distributions outperform unimodal Gaussian output distributions. These results mirrors those from the previous section in highlighting how increasing the policy’s model capacity can improve performance. Again, our finding stands in contrast to standard RL methods, which work well with unimodal Gaussians.We conjecture that this result is caused because RvS policies must represent both optimal and suboptimal behavior (e.g., high-reward targets and low-reward targets), whereas standard RL policies only need to represent optimal behavior. We conjecture that upweighting better data, as down by previous methods (Kumar et al., 2019), may make it easier for low-capacity policies to fit the data. As increasing model capacity is often simpler than learning value functions, our results suggest an easier approach to achieving similar results.
Tuning with validation loss. Hyperparameter optimization is especially important in the offline RL setting, as evaluating different hyperparameter configurations requires interacting with the environment (Paine et al., 2020). Since RvS methods reduce the RL problem to a supervised learning problem, we conjecture that the validation loss of this supervised learning problem might be an effective metric for tuning important hyperparameters, such as policy capacity and regularization. In Figure 4, we train models on 80% of the training data for each Franka Kitchen dataset with two different hyperparameter settings: a regularized setting with dropout p = 0.1 and small batch size 256, and an unregularized setting without dropout and a large batch size of 16, 384. While in all three cases validation set error does correlate with performance, the strength of
this correlation varies significantly, suggesting that validation loss does not provide a reliable approach for hyperparameter tuning. This suggests that fully automated tuning is an open question. Table 1 summarizes the hyperparameters that we found to work best for each offline RL benchmark.
A recipe for practicioners. Figure 2 indicates that having enough model capacity is important for strong performance, and regularization sometimes also provides a substantial boost. While offline hyperparameter tuning remains an open challenge (Fu et al., 2021; Paine et al., 2020), we suggest the following process for online hyperparameter tuning: incrementally increase network width until performance saturates, and then try adding a bit of dropout regularization (e.g., dropout p = 0.1). If under/overfitting is still an issue, one can also try increasing/decreasing the batch size, respectively.

heading: 6 COMPARING RVS WITH PRIOR OFFLINE RL METHODS

text:
Having identified key design decisions in the implementation of RvS learning methods, we now turn to comparing RvS learning methods to prior offlinr RL methods. We will evaluate both goalconditioned behavioral cloning (RvS-G) and reward-conditioned behavioral cloning (RvS-R) on each of the domains in Section 4, in comparison with relevant baselines and state-of-the-art methods in the literature. We then discuss what these results imply about the performance, design parameters, and limitations of RvS methods. A summary of the results is presented in Figure 5, with detailed task-by-task breakdowns in Appendix A.
Baselines and prior methods. On the D4RL benchmarks, we compare RvS learning to (i) valuebased methods and (ii) prior supervised learning methods and behavioral cloning baselines. For (i), we include CQL (Kumar et al., 2020), with results updated to the v2 D4RL environments for Gym locomotion,1 as well as the more recent TD3+BC (Fujimoto & Gu, 2021) and Onestep RL (Brand-
1Several prior works report results for CQL on the v0 D4RL Gym locomotion environments, which are somewhat harder. We use v2 for all methods for fairness, hence the reported CQL numbers are higher than some prior works.
fonbrener et al., 2021) methods, which involve elements of behavioral cloning as well. For (ii), we include behavioral cloning (BC), which does not perform any conditioning; “10% BC,” which imitates the best 10% of the trajectories; and Decision Transformers (DT) (Chen et al., 2021), which conditions on rewards and uses a large Transformer sequence model. The DT baseline used code released by the authors, which was tuned on Antmaze based on correspondence with the authors; both BC and 10% BC are our own optimized implementations, tuned thoroughly in a similar manner as RvS-R and RvS-G. Due to time constraints, we were unable to adequately tune DT, TD3+BC, and Onestep RL on Kitchen (these numbers are also not available from the authors). On the GCSL benchmarks, we compare to GCSL (Ghosh et al., 2021) using numbers reported by the authors, which use online data. We do not run RvS-G on the Gym locomotion tasks, which are typically expressed as reward-maximization tasks, not goal-reaching tasks.
Overall performance and comparison to prior methods. The results in Figure 5 lead to several conclusions about how our RvS implementations compare to prior value-based and supervised methods. First, on the GCSL, Kitchen, and Gym Locomotion tasks, either RvS-G or RvS-R attains results that are comparable to the best prior method. We will discuss the particular tradeoffs between goals and rewards later. The finding that conditional imitation with standard fully connected networks attains competitive results stands in contrast to conclusions drawn in prior work. As we discussed in Section 5, good performance requires a counterintuitive combination of high capacity and regularization, and it may simply be that this seemingly contradictory combination of components was not adequately explored in prior work. These results suggest that complex sequence model architectures are likely not necessary for these tasks, and the benefits reported by Chen et al. (2021) are likely derived from careful capacity tuning (as we discuss in Section 5) rather than the use of a Transformer.
Subtrajectory stitching. The mixed dataset in Kitchen and all of the Antmaze tasks consist of highly suboptimal trajectories, so expert performance requires recombining parts of these trajectories to attain more optimal behavior. As subtrajectory stitching has usually been viewed as a key benefit of dynamic programming methods, it is not surprising that those baselines that perform dynamic programming (TD3+BC and CQL) perform better than other baselines on this task. In both domains, RvS-G attains relatively good results, matching or outperforming all methods except CQL.
We believe that this observation supports our discussion at the end of Section 4: the choice of conditioning information for RvS communicates prior knowledge, and this prior knowledge can aid in generalization. In this case, conditioning on goals, which are spatially structured, may provide the method with a similar kind of compositionality in space as Bellman backups provide in time for dynamic programming techniques. Note, however, that this observation is likely domain-specific, as we discuss later. BC works well in the Kitchen environment, which we speculate is due to the fact that the actual number of skills is low, so simply imitating all available skills can complete the relevant subtasks with sufficient frequency. This is not the case for Antmaze.
Reaching arbitrary goals. An important capability of RvS-G, compared with more standard offline RL methods, is that it learns a policy that can reach many goals. To test how well RvS-G can learn to reach arbitrary goals from random offline data, we compare to GCSL, an RvS learning method that performs iterative online data collection (Ghosh et al., 2021). We use the same tasks used by GCSL. Each of the tasks in the GCSL suite requires that the agent reach a goal drawn uniformly at random from the set of possible goals. The results shown in Figure 5 indicate that our policy can successfully reach many different goals entirely from randomly collected offline data. Although it may still be that iterative online collection, as proposed in prior work (Ghosh et al., 2021; Srivastava et al., 2019), may be helpful in some domains, in this case simple offline training appears to suffice.
Random datasets. While RvS-R is generally competitive across the Gym Locomotion tasks, TD learning approaches generally have an edge of a few points in the random datasets, with CQL performing especially well in halfcheetah-random. This generally aligns with our expectations, since random datasets provide the most potential for TD methods to improve over conditional behavioral cloning methods. Indeed, we find that the other behavioral cloning methods we consider,
BC and %BC, also have a relatively more difficult time with the random datasets compared to the other dataset types.
Analysis of reward conditioning. Next, we further analyze what RvS-R actually learns, and how it uses the conditioning variable. First, we use the walker2d-medium-expert task to analyze the behavior of RvS-R for different conditioning rewards. This dataset contains two modes (“medium” and “expert”, as shown in Figure 6 (right), and although we can condition the network on any reward value, we see in Figure 6 (left) that the policy actually learns to achieve just the two modes in the dataset; it cannot interpolate between them. In effect, RvS is extracting a subset of the data, but doing so without explicit filtering (as is done in 10% BC).
This analysis highlights the importance of the conditioning variable. It is not obvious a priori that a reward target of 100 will lead to a return of 70, whereas a reward target of 110 will lead to a return of 105. For an apples-to-apples comparison with prior work (Chen et al., 2021), which includes the reward target as a hyperparameter that is tuned for best online performance, we also vary the reward target as a hyperparameter, using the settings in Table 1. However, we believe that this suggests that further investigation into the importance of the conditioning variable, as well as ways to choose hyperparameters in a truly offline setting, is an important problem for future work.

heading: 7 DISCUSSION AND FUTURE WORK

text: We presented a detailed empirical study of offline RL via supervised learning (RvS) methods, which solve RL problems via conditional imitation learning (Codevilla et al., 2018; Lynch et al., 2020; Ghosh et al., 2021; Eysenbach et al., 2020; Kumar et al., 2019; Srivastava et al., 2019; Chen et al., 2021). While prior work is divided on which particular elements of RvS are crucial for good performance, or even how well such methods actually work, our results provide a number of potentially surprising conclusions. First, RvS methods can work well, even with simple fully connected architectures, if capacity and regularization are chosen correctly. Second, RvS methods can often attain results that compare favorably to the best prior methods, but only if the conditioning variable (e.g., goal or reward) is chosen appropriately. Third, RvS methods can enjoy some of the benefits of compositionality (“stitching”), but only for an appropriate choice of conditioning variable. These conclusions imply a number of interesting directions for future work, which we encourage the community to explore. First, as we discuss in Section 5, validation error does not provide a fully reliable metric for tuning capacity, and because capacity and regularization are so important, appropriate offline evaluation techniques may be essential to make full use of RvS for offline RL. Second, as we showed in Section 6, conditioning is important, and developing more general or more automated ways to select what to condition could likely further improve the generality of such methods. Taken together, we believe that our analysis provides clarity on RvS learning methods and also presents a number of avenues for increasing the performance of and further simplifying RvS learning methods.

heading: B THE IMPACT OF MODEL CAPACITY AND REGULARIZATION

text:
As we find in Section 5 that model capacity and regularization are important for performance in seemingly contradictory ways, we hypothesize that this can be explained by validation loss. So, for 5 random seeds in each of the 3 Franka Kitchen datasets (complete, partial, and mixed), we measure validation loss and return throughout training for three different settings of policy hyperparameters: network width 1024 with dropout p = 0.1, network width 1024 with dropout p = 0 (no dropout), and network width 256 with dropout p = 0 (no dropout). We expect that a larger network width leads to better validation loss, explaining its better return. We expect adding regularization also has this pattern of better validation loss and therefore better return.
In Figure 8, we plot the results: validation loss is nearly identical across all of the hyperparameter settings, but return can vary by as much as 1.4x between different hyperparameter settings. We also observe that evaluation return steadily increases even after validation loss has mostly leveled off. This is surprising and refutes our hypothesis; furthermore, it provides the insight that model capacity and dropout are having effects beyond just the validation loss. A similar phenomenon occurs in Neural Machine Translation, where cross entropy loss can decline while the quality of the translation (measured by BLEU score) remains constant (Ghorbani et al., 2021), and in contrastive representation learning, where lower capacity models have worse losses on the test set but still learn better representations for downstream tasks (Tschannen et al., 2020). It is an important open problem for the field to understand why architecture decisions can impact performance beyond validation loss.

heading: C COMPARISON OF CONDITIONING STRATEGIES

text:
To further study how different goal and reward conditioning strategies comparison, in Figure 9a, we show the performance of four strategies: Reward Scalar, Reward Goal, Length Goal, and Optimized Goal. In Reward Scalar, we condition RCBC on various fractions of expert performance. In Reward Goal, we randomly select timesteps near the end of the highest-reward
demonstration trajectories. In Length Goal, we randomly select timesteps near the end of the longest demonstration trajectories. In Optimized Goal, we do a random search over 200 Length Goals and select the highest performing one. Note that these selection strategies require access to the environment, so they are not strictly offline RL. We nevertheless include them here as ablations to provide additional insight into the goal-conditioned policies. Note that, although we can utilize goals with oracle goal selection strategies for the Gym tasks, the performance of these strategies generally does not exceed reward conditioning, since the tasks are inherently not goal-conditioned.


summaries: 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.

summaries: 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).

summaries: 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

summaries: 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.

abstractText: Humans are expert explorers. Understanding the computational cognitive mechanisms that support this efficiency can advance the study of the human mind and enable more efficient exploration algorithms. We hypothesize that humans explore new environments by inferring the structure of unobserved spaces re-using spatial information collected from previously explored spaces. We model this cognitive process computationally through “Map Induction”, which involves the compositional formation of proposed maps of complex spaces based on already-seen spaces through program induction in a Hierarchical Bayesian framework. The model thus explicitly reasons about unseen spaces through a distribution of strong spatial priors. We introduce a new behavioral Map Induction Task, and compare human performance with that of state-of-the-art existing models as well as our Map Induction framework. We show that our computational framework better predicts human exploration behavior than non-inductive models. We also show that Map Induction, when used to augment state-of-the-art approximate planning algorithms, improves their performance.

authors:
Jeremy N Bailenson
Michael S Shum
David H Uttal

title: The initial segment strategy: A heuristic for route selection

venue: Memory & Cognition,

authors:
Jan Balaguer
Hugo Spiers
Demis Hassabis
Christopher Summerfield

title: Neural mechanisms of hierarchical planning in a virtual subway

venue: network. Neuron,

authors:
Andrea Banino
Caswell Barry
Benigno Uria
Charles Blundell
Timothy Lillicrap
Piotr Mirowski
Alexander Pritzel
Martin J Chadwick
Thomas Degris
Joseph Modayil

title: Vector-based navigation using grid-like representations in artificial agents

authors:
Christian Bongiorno
Yulun Zhou
Marta Kryven
David Theurel
Alessandro Rizzo
Paolo Santi
Joshua Tenenbaum
Carlo Ratti

title: Vector-based pedestrian navigation in cities, 2021

authors:
Michael Bosse
Paul Newman
John Leonard
Martin Soika
Wendelin Feiten
Seth Teller

title: An atlas framework for scalable mapping

venue: IEEE International Conference on Robotics and Automation (Cat. No. 03CH37422),

authors:
Scott Camazine
Jean-Louis Deneubourg
Nigel R Franks
James Sneyd
Guy Theraula
Eric Bonabeau

title: Self-organization in biological systems

authors:
Francis Carpenter
Daniel Manson
Kate Jeffery
Neil Burgess
Caswell Barry

title: Grid cells form a global representation of connected environments

venue: Current Biology,

authors:
Dori Derdikman
Jonathan R Whitlock
Albert Tsao
Marianne Fyhn
Torkel Hafting
May-Britt Moser
Edvard I Moser

title: Fragmentation of grid cell maps in a multicompartment environment

venue: Nature neuroscience,

authors:
Daniel D Dilks
Joshua B Julian
Jonas Kubilius
Elizabeth S Spelke
Nancy Kanwisher

title: Mirrorimage sensitivity and invariance in object and scene processing pathways

venue: Journal of Neuroscience,

authors:
Nathaniel Fairfield
David Wettergreen
George Kantor

title: Segmented slam in three-dimensional environments

venue: Journal of Field Robotics,

authors:
Patrick Foo
William H Warren
Andrew Duchon
Michael J Tarr

title: Do humans integrate routes into a cognitive map? map-versus landmark-based navigation of novel shortcuts

venue: Journal of Experimental Psychology: Learning, Memory, and Cognition,

authors:
Sabine Gillner
Hanspeter A Mallot

title: Navigation and acquisition of spatial knowledge in a virtual maze

venue: Journal of cognitive neuroscience,

authors:
Stephen C Hirtle
John Jonides

title: Evidence of hierarchies in cognitive maps

venue: Memory & cognition,

authors:
Leslie Pack Kaelbling
Michael L Littman
Anthony R Cassandra

title: Planning and acting in partially observable stochastic domains

venue: Artificial intelligence,

authors:
Stephen M Kosslyn
Herbert L Pick Jr.
Griffin R Fariello

title: Cognitive maps in children and men

venue: Child development,

authors:
Marta Kryven
Suhyoun Yu
Max Kleiman-Weiner
Joshua Tenenbaum

title: Adventures of human planners in maze search

venue: task. PsyArXiv,

title: The spatial semantic hierarchy

authors:
Benjamin Kuipers
Joseph Modayil
Patrick Beeson
Matt MacMahon
Francesco Savelli

title: Local metrical and global topological maps in the hybrid spatial semantic hierarchy

venue: In IEEE International Conference on Robotics and Automation,

authors:
Benjamin J Kuipers
Todd S Levitt

title: Navigation and mapping in large scale space

venue: AI magazine,

authors:
Brenden M Lake
Steven T Piantadosi

title: People infer recursive visual concepts from just a few examples

venue: Computational Brain & Behavior,

authors:
Brenden M Lake
Ruslan Salakhutdinov
Joshua B Tenenbaum

title: Human-level concept learning through probabilistic program induction

authors:
Steven A Marchette
Lindsay K Vass
Jack Ryan
Russell A Epstein

title: Anchoring the neural compass: coding of local spatial reference frames in human medial parietal lobe

authors:
Robert U Muller
John L Kubie

title: The effects of changes in the environment on the spatial firing of hippocampal complex-spike cells

authors:
Nora Newcombe
Janellen Huttenlocher
Elisabeth Sandberg
Eunhui Lie
Sarah Johnson

title: What do misestimations and asymmetries in spatial judgement indicate about spatial representation

authors:
V Paz-Villagrán
E Save
Bruno Poucet

title: Independent coding of connected environments by place cells

venue: European Journal of Neuroscience,

title: Spatial representation for navigation in animats

venue: Adaptive Behavior,

authors:
Eric Schulz
Nicholas T. Franklin
Samuel J. Gershman

title: Finding structure in multi-armed bandits. bioRxiv, 2018. doi: 10.1101/432534

authors:
Tianmin Shu
Marta Kryven
Tomer D Ullman
Joshua B Tenenbaum

title: Adventures in flatland: Perceiving social interactions under physical dynamics

venue: In 42d Proceedings of the Annual Meeting of the Cognitive Science Society,

authors:
David Silver
Joel Veness

title: Monte-carlo planning in large pomdps

venue: In Advances in Neural Information Processing Systems,

authors:
David Silver
Julian Schrittwieser
Karen Simonyan
Ioannis Antonoglou
Aja Huang
Arthur Guez
Thomas Hubert
Lucas Baker
Matthew Lai
Adrian Bolton

title: Mastering the game of go without human knowledge

authors:
Satinder Singh
Michael James
Matthew Rudary

title: Predictive state representations: A new theory for modeling dynamical systems

venue: arXiv preprint arXiv:1207.4167,

authors:
Albert Stevens
Patty Coupe

title: Distortions in judged spatial relations

venue: Cognitive psychology,

authors:
Andreas Stuhlmuller
Joshua B Tenenbaum
Noah D Goodman

title: Learning structured generative concepts

venue: In 32d Proceedings of the Annual Meeting of the Cognitive Science Society. Cognitive Science Society,

authors:
Richard S Sutton
Doina Precup
Satinder Singh

title: Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning

authors:
Lucas Tian
Kevin Ellis
Marta Kryven
Josh Tenenbaum

title: Learning abstract structure for drawing by efficient motor program induction

authors:
Momchil S Tomov
Samyukta Yagati
Agni Kumar
Wanqian Yang
Samuel J Gershman

title: Discovery of hierarchical representations for efficient planning

venue: PLoS computational biology,

authors:
Jenny Vuong
Andrew W Fitzgibbon
Andrew Glennerster

title: No single, stable 3d representation can explain pointing biases in a spatial updating task

venue: Scientific reports,

authors:
Ranxiao Frances Wang
James R Brockmole

title: Human navigation in nested environments

authors:
William H Warren
Daniel B Rothman
Benjamin H Schnapp
Jonathan D Ericson

title: Wormholes in virtual space: From cognitive maps to cognitive

venue: graphs. Cognition,

authors:
Jan M Wiener
Hanspeter A Mallot

title: fine-to-coarse’route planning and navigation in regionalized environments

venue: Spatial cognition and computation,

authors:
Aaron Wilson
Alan Fern
Prasad Tadepalli

title: Transfer learning in sequential decision problems: A hierarchical bayesian approach

venue: In Proceedings of ICML Workshop on Unsupervised and Transfer Learning,

authors:
Shanjiang Zhu
David Levinson

title: Do people use the shortest path? an empirical test of wardrop’s first principle

venue: PloS one,

heading: 1 INTRODUCTION

text:
Humans efficiently use spatial reasoning to navigate through and forage in new environments. We easily find our way around new buildings, and quickly (without exhaustive search) infer promising foraging locations. Which neurally-informed computational cognitive mechanisms make this possible, and could they be leveraged for better exploration in AI? In this work we empirically study human exploration in novel spaces, and propose a formal computational model that predicts human behaviour by leveraging Bayesian inference about the structure of unobserved space (which we term map induction). We also show that map induction can improve performance of a Partially Observable Markov Decision Process (POMDP) planner during exploration. We begin by reviewing the literature on human spatial cognition involved in exploration, and parallel developments of exploration algorithms, followed by introducing our computational modelling, and experimental results.
Distributed non-metric representations. Human exploration relies on approximate spatial representations (Wang & Brockmole, 2003; Warren et al., 2017; Wiener & Mallot, 2003) that support near-optimal planning in daily life (Bongiorno et al., 2021) while sacrificing global metric accuracy (Vuong et al., 2019; Newcombe et al., 1999; Zhu & Levinson, 2015). These representations are acquired by combining redundant observations of local landmarks, such as views from multiple perspectives (Gillner & Mallot, 1998; Foo et al., 2005). The use of distributed spatial representations for cost-effective navigation also has a long history in AI. Examples include a computational theory of wayfinding based on multiple locally unique but globally similar landmarks (Prescott, 1996), which prioritized error recovery over accuracy. The Spatial Semantic Hierarchy model (Kuipers & Levitt, 1988) used distributed spatial graphs as maps for navigation (Kuipers, 2000; Kuipers et al., 2004). Simultaneous Localization and Mapping (SLAM) algorithms circumvent scale limitations by dividing the world into manageable locally metric submaps with topological relationships between submaps (Bosse et al., 2003; Fairfield et al., 2010). By contrast, recent recurrent neural network models of navigation have focused more closely on the metric structure of explored spaces and global map formation, showing how networks trained on path integration can take shortcuts (Banino et al., 2018).
Hierarchical organization. Humans minimize planning costs by representing spaces hierarchically – based on visible spatial boundaries (Kosslyn et al., 1974), geography (Stevens & Coupe, 1978), or otherwise interpreting spaces as composed of sub-regions (Hirtle & Jonides, 1985). Hierarchical spatial organisation is evident in a tendency to plan paths between regions, before planning subpaths within each region (Bailenson et al., 2000; Newcombe et al., 1999; Wiener & Mallot, 2003; Wang & Brockmole, 2003; Balaguer et al., 2016), and in increased reaction times when switching between hierarchy levels during plan execution (Balaguer et al., 2016; Kryven et al., 2021). Hierarchical state-spaces in non-spatial planning domains include drawing (Tian et al., 2020) inverse inference (Shu et al., 2020), and reasoning about topology (Tomov et al., 2020).
Hierarchical representations in AI are often expressed as options – a hierarchical grouping of actions frequently performed together (Sutton et al., 1999). Assuming that a novel Markov Decision Processes (MDP) is sampled from a family of similar MDPs, its rewards can be learned as hierarchically derived from a parent distribution shared by the MDP family (Wilson et al., 2012). Singh et al. (2012) proposed a computational framework for learning efficient state-space representations by recognizing which sequences of actions lead to identical observations – for example, grouping together paths that lead to observing the same landmark. A principle of grouping game-board states based on rotation and reflection symmetries has been used to optimize state-space representations in the game of Go (Silver et al., 2017).
Shared reference frames. From young children to hunter-gatherers, humans spontaneously organize sensory precepts into patterns (Pitt et al., 2021), and use them to generalize between tasks (Tian et al., 2020; Lake & Piantadosi, 2020; Schulz et al., 2018). Generalization and transfer learning in spatial domains include phenomena such as mirror-invariant neural scene representations (Dilks et al., 2011), and reusing of reference frames across similar environments (Marchette et al., 2014). Shared reference frames may occur in other mammals as well, as suggested by evidence of rodents reusing grid-cell maps between similar parts of environments (Derdikman et al., 2009; Carpenter et al., 2015). However, these studies have neither studied the process of discovering structural patterns during spatial exploration, nor considered formal quantitative models of how structured map knowledge may be built and reused.
Map induction. We propose a map induction hypothesis – that humans optimize exploration of new spaces by representing maps as composed of reusable reference frames – which can be modeled by using program induction to represent unseen space as composed of regions encountered in the observed areas. Program induction generally refers to inferring a program that likely produced a given sequence of observations (Stuhlmuller et al., 2010; Lake et al., 2015). For example, given a sequence of numbers, the inferred program may be an arithmetic progression; given a natural texture the program may be a reaction-diffusion equation (Camazine et al., 2020). Although Bayesian models of concept-learning by probabilistic program induction have been developed for many domains (Stuhlmuller et al., 2010; Lake et al., 2015; Tian et al., 2020), the use of program induction to understand spatial structures and environments is unexplored. In this work map induction refers to inferring program(s) that could have generated environment, given past observations. Given one of such programs, an agent can anticipate the structure of an unseen environment to optimize exploration. For example, we can plan a foraging trip by anticipating that a landscape of hills will
continue in a previously observed pattern, and that the distribution of berries in the unseen space will be similar to the distribution observed so far (see Figure 1).
In this work we adopt a scientific and engineering goal: (1) to empirically study how humans learn spatial representations, and (2) describe a computational model that formalizes human-like map induction and can potentially be leveraged to optimize exploration in AI. We show that a Partially Observed Markov Decision Process (POMDP) planner augmented with a Hierarchical Bayesian map induction predicts human exploration better than a naive, non-inductive, POMDP (Experiment 1). We also show that human exploration relies on probabilistic distributions over likely mapsgenerating programs, as opposed to using only the most likely map (Experiment 2). In the next section, we introduce a novel Map Induction Task, which we use to empirically study exploration. We then give a detailed description of computational models in Section 3. In Section 4, we describe two human experiments, and compare behavioral metrics with our models’ predictions.

heading: 2 MAP INDUCTION TASK

text:
The Map Induction Task (MIT) is designed to present subjects with novel environments and provide a context for learning novel spatial representations. In this work we are especially interested in environments including repeating regions, such that certain parts of the environment can be predicted from incomplete observations. For example, upon entering a unit in an apartment building a human explorer will likely categorize it as a new region, but after exploring several units, one should be able to anticipate the remaining floor-plan, or even consider several possibilities consistent with prior observations – such as, that the right and the left wing of the building could mirror each other, or two types of units could occur in alteration, etc. In nature predictable structures occur in patterns of hills and valleys, branching riverbeds, and plants favoring certain features of the environment (see Figure 1), which in theory can be probabilistic, rather than exactly structured repetitions.
The subjects’ task is to forage for rewards in novel partially observable 3-dimensional environments, which contain multiple rewards. To keep experiment duration under 45 minutes, in the
current version of the MIT task each environment consisted of repeated units – structural blocks repeated throughout the environment with rewards (diamonds) hidden in specific parts of each unit (see Figure 2B). However, in theory the environment structure can also be a probabilistic mixture of predictable and unpredictable layouts.
The subjects have no advance knowledge of environment structure and are instructed to collect all diamonds (see Figure 2 C). Subjects use a keyboard and mouse (or a trackpad) to navigate, which are standard navigation controls in first-person games. The distribution of rewards is initially unknown to the subjects, but can be predicted from the layout of the environment – for example, the rewards may be placed in the same part of a unit each time a given unit occurs. While the MIT task can be completed without map induction, or even without an explicit map representation (e.g. by following a wall) such a naive strategy would take longer than selectively exploring only the parts likely to contain diamonds. Each trial continues either until all diamonds are collected or until a timeout is reached, whichever comes first.

heading: 3 COMPUTATIONAL MODELS

text:
In this section we formalize the map induction hypothesis in order to quantitatively and computationally test its predictions. We first consider computational steps needed to optimize performance in the MIT task: (1) inferring that the environment is composed of repeating units (2) inferring the most likely structure(s) of the environment (3) inferring the distribution of rewards within the environment, and (4) planning the shortest route that collects all rewards. Here (1) and (2) refer to map induction, and (3) may involve further program induction over the distribution of rewards (e.g. the rewards could be placed in the top left corner of every unit, in every odd unit, etc.) The reward-generating program could potentially be arbitrarily complex; however, in the current work we consider short programs for simplicity. Because of uncertainty in the environment, this compu-
tational pipeline is executed in the context of a replanning loop. Finally, step (4) involves solving a Partially Observed Markov Decision Process (POMDP) that uses distribution of hypothetical environments to plan. While it is possible to do (4) without performing the first three steps, this would entail assuming an uninformed prior that any unobserved cell could equally likely be a wall, an empty space, or a reward – which would result in exploring exhaustively.
Formally, we can model this process by a Bayesian generative framework consisting of four computational modules (see Figure 3A) corresponding to the four steps described above. Each module can be independent of the others and can express different modeling assumptions. In the remainder of this section, we discuss the function of each module in detail and define three specific combinations of module implementations, to express three distinct computational hypotheses formalizing the principle of map induction in different ways.

heading: 3.1 MAP INDUCTION THROUGH OBSERVED SPATIAL STRUCTURES

text:
Steps (1) and (2) entail approximate inference of a posterior distribution p(M |D) over possible maps given observation history. In this section we formalize the computations that estimate this posterior distribution (see Figure 3A).
Region Extraction: The region extractor extracts candidate regions (or submaps) Mp from known parts of the map (see Figure 3B for a simple example). The second stage of the hierarchy in Figure 3B shows examples of regions extracted from the observed map, shown above. Note that the term region refers to a hypothetical building block of the environment considered by the model, and is different from the term unit used in the previous section to describe repeating elements in environment design. In theory multiple regions can represent a unit, or a region may comprise several units.
Map Generation: Next, we develop a space of possible map completions using the extracted regions, using a probabilistic generative grammar that combines region primitives into a set of completed maps. If the map currently being explored has dimensions sx, sy , and dx, dy are the dimensions of the extracted regions, then the generative grammar for that map is described as shown in Table 1. The third level of the hierarchy in Figure 3B shows examples of map completions generated using
the Map Generator. The probabilities assigned to the rules in the generative grammar encode priors on coverage and consistency of the generated maps.
Map Inference: We use this probabilistic generative grammar along with the following likelihood over generated maps to form the posterior p(M |D):
l(M ;D) ∝ [ 1− β
sx × sy
] × [ 1− γ
sx × sy ] where γ/sx × sy is the fraction of the map not predicted by a given map completion and β/sx × sy is the fraction of mismatched reward locations relative to the history of observations. At a high level, this likelihood function encodes two simple assumptions: (1) map completions that are maximally descriptive of unseen portions of the environment are more likely; (2) map hypotheses that are minimally contradictory with previous observations are more likely. The posterior distribution p(M |D)
is computed using the above likelihood function, and an initial prior on the map hypotheses p(M) derived from the probabilities assigned to the production rules in the generative grammar listed in
Table 1.1 For simplicity, here we assume a uniform prior over the map hypotheses generated by the Map Generator since the space of possible hypotheses is small.
p(M |D) = l(M ;D)p(M) = p(D|M)p(M)

heading: 3.1.1 PLANNER

text:
We model the exploration problem as a Partially Observable Markov Decision Process (POMDP). In a POMDP, the state is not directly observable by the agent and can only be inferred through sequences of observations in the environment. A POMDP can be described as a tuple 〈S,A, T,R,Ω,O, γ〉 where S is the set of possible states in the world, A is a finite set of actions, T : S×A → Π(S) is a stochastic transition function which maps a state action pair to a distribution over possible next states, R : S×A → R is a reward function that maps state action pairs to a scalar reward, Ω is a set of observations that an agent can experience in the world, O : S × A → Π(Ω) is an observation function which maps a state and action pair to a distribution of possible observations after taking the action, and γ is a discount factor such that 0 < γ < 1. An optimal agent in this formulation acts to maximize the expected discounted reward from the environment.
π∗(s) = arg max a ( E [ ∞∑ k=0 γkR(s, a) ])
For our task, the state space is defined as S = H× [0, 1]|H|×Sa whereH is the set of possible map hypotheses from p(M |D), [0, 1]|H| is the probability associated with each hypothesis, and Sa is a 3-tuple (ax, ay, ar) with dimensions (sx, sy, 4) indicating the index into the grid world state where the agent is positioned and the current direction the agent is facing. The action space is discrete with size 3 for bidirectional rotation and forward movement. We use a reward function R defined by an indicator function over the state space 1(Sg[ax, ay] = reward). The transition function T (s′|s, a) is a stochastic function that maps the given action and the previous state to a new state. There is no closed-form expression for T , but it can be expressed using a generative probabilistic sampler that takes in s, samples a grid from the hypothesis distribution in s, deterministically simulates action a in the sampled grid, and returns a new position, orientation of the agent and an updated hypothesis distribution consistent with the new observations. The observation space Ω(s, a;D) is defined by a surjective line-of-sight (LOS) observation function O that maps from state and action to a deterministic observation. This function casts rays within a 90-degree field of view in the direction of the agent’s orientation. Lastly, we define γ = 0.90 for all of our experiments. Since finding an exact solution is intractable due to the size of the problem (Kaelbling et al., 1998), we search through belief space using an approximate online Partially Observable Monte Carlo Planner (POMCP) (Silver & Veness, 2010).

heading: 3.2 COMPUTATIONAL HYPOTHESES

text:
We compare human performance to three hypotheses (variants of POMCP) to evaluate whether and how human exploration implements the computational steps described in Figure 3A:
1. Uniform Model (Uniform-POMCP): The Uniform model doesn’t use map induction, i.e., it doesn’t learn any inductive priors about spatial structures during exploration outlined in steps (1)-(3). Instead, it assumes a uniform distribution over possible settings for each grid cell (reward, empty, etc.) and uses that for planning as shown in Figure 3C.
2. Maximum A Posteriori Model (MAP-POMCP): The MAP model uses the most likely map from the distribution of induced maps p(M |D) to plan (see Figure 3D).
3. Full Distributional Model (D-POMPC): The Distributional model uses the entire set of induced maps in the distribution p(M |D) to plan (see Figure 3E).
1Given the relatively small environments, we are able to compute the posterior exactly. However, larger and more complex environments (where enumerating all possible map completions is not feasible) would likely require approximate Bayesian inference methods such as Markov Chain Monte Carlo.
Both second and third hypotheses are consistent with the previous studies. They both use the map induction framework that is based on compositionality of space i.e., maps are composed of reusable reference frames. As discussed in Section 1 shared reference frames have been found in both behavioral studies in humans and neural studies of spatial navigation in rodents. Moreover, compositionality implies combining local regions to form the global map instead of learning a global metric representation. Evidence for such distributed representations has been found in numerous studies discussed in Section 1. Furthermore, these models assume a hierarchical organization of space as shown in Figure 3B, that is also supported by existing theories and experimental results mentioned in Section 1. On the other hand, the first hypothesis is inconsistent with the previous literature since it makes no prior assumptions about the organization of space (neither hierarchical organization, nor the use of shared reference frames). Furthermore, it assumes a uniform distribution over the unseen map space which is akin to learning a global map.

heading: 4 BEHAVIORAL EXPERIMENTS

text: Below we describe two human behavioral experiments. Experiment 1 tests whether humans perform map induction, as implemented by the MAP-POMCP and D-POMCP models, in contrast to naive exploration implemented by Uniform-POMCP. The results of the first experiment show that humans indeed rely on map induction and rule out the use of the Uniform model. Experiment 2 tests whether human exploration is best explained by MAP-POMCP or D-POMCP models, and shows that humans plan according to a distribution of hypothetical maps, explicitly gathering information to disambiguate those hypotheses. The number of subjects recruited for both experiments was determined through prior pilot experiments, our goal was to recruit a sufficient number of responses to differentiate between the Uniform-POMCP, MAP-POMCP and D-POMCP.

heading: 4.1 EXPERIMENT 1: USING MAP INDUCTION TO OPTIMIZE EXPLORATION

text:
Method: The experiment was conducted in a web browser, using 3D virtual environments built-in Unity WebGL. Each environment was composed of a corridor connecting five instances of a specific unit. The rewards (diamonds) were placed at identical locations within each unit. An example environment is shown in Figure 2. Each subject performed four practice trials to gain familiarity
with the experimental setup and controls, followed by an instruction quiz and 12 test trials in order randomized between subjects. Subjects who failed the instruction quiz repeated the instructions and practice until they answered the quiz correctly. The timer for the trial and the number of diamonds collected were shown on the upper right corner of the screen (see Figure 2C). See Supplementary Materials for full experimental instructions and screenshots.
Stimuli: The 12 test trials comprised six pairs of unique environments and their reflections. We used the reflected environments to increase the number of trials and control for possible left or right biases in navigation.
Subjects: We recruited 30 subjects via Amazon Mechanical Turk. Subjects were paid for 35 minutes of work and received a monetary bonus for each collected diamond.
Results: Out of the 30 subjects, four subjects explored exhaustively, 2 did not complete the experiment and 24 subjects were able to predict reward placement and reduce exploration time, indicating that humans use map induction. Subjects generally exhaustively explored the first two units upon entering a new environment, followed by partial exploration through the remainder of the trial. Throughout the experiment, the extent to which non-rewarding areas were visited also decreased, indicating that people were increasingly confident about the repeating layout.
Figure 4A shows examples of exploration trajectories of one subject. Subjects generally used identical trajectories to search the reflected pairs of environments, and so we aggregated results for each of the six pairs. Figure 4B illustrates the extent to which three example environments were visited, aggregated across subjects, and across reflected pairs of environments. See the Appendix for a complete plot of all exploration trajectories and heatmaps corresponding to all environments. Figure 4C shows the fractions of each environment observed by humans and models. The areas observed by MAP-POMCP and D-POMCP were similar to humans’, while the area observed by UniformPOMCP was significantly larger. Figure 4D shows the fit of the three models to human behavior, indicating that the MAP-POMCP and D-POMCP models, which implement map induction, explain human behavior better than the Uniform-POMCP model, which makes no predictions about map structure.

heading: 4.2 EXPERIMENT 2: DISTRIBUTIONAL SUB-MAP REPRESENTATIONS

text:
Experiment 2 differentiates between MAP-POMCP and D-POMCP models using color cues to indicate the location of rewards within each unit. This was done by including a ‘cue room’ within each unit – a small room containing information about the location of the reward. The environments were designed so that MAP-POMCP would take a longer exploration path compared to D-POMCP. A planner guided by the MAP-POMCP model ignores the cue rooms and heads toward the part of a unit most likely to contain a diamond based on previous experience. In contrast, the D-POMCP model visits the cue room to gather information about the location of the diamonds.
Method: Experiment 2 followed a procedure similar to Experiment 1, with a different set of environments. Each subject performed five practice trials, followed by an instruction quiz, 12 test trials in order randomized between subjects, and a test of skills using navigation controls. The controls skill test ensured that subjects could navigate in WebUnity without undue difficulty since Experiment 2 used larger environments. Subjects who failed the controls skill test were paid but excluded from the analysis. The instructions were modified to prompt subjects to consider colors as cues to the placement of the reward – see the Appendix for full details.
Stimuli: The 12 test environments comprised six unique environments and their reflections. The color cues were randomized within each environment so that the reflected pairs of environments were colored in different ways and contained rewards in different locations.
Subjects: We recruited 51 subjects via Amazon Mechanical Turk. Each was paid for 35 minutes of work and received a monetary bonus for each collected diamond.
Results: Out of 51 subjects, 35 completed the controls skill test. Of the 35 subjects, all but nine were able to successfully use color cues, as predicted by the D-POMCP model, indicating that the majority took into account the entire distribution of possible maps in contrast to just the most likely map. Example exploration trajectories of one subject and visitation heatmaps are shown in Figure 5 A and B. See the Appendix for more results. Comparing the fractions of environments observed by humans
and models indicates that only the D-POMCP model was comparable to humans (see Figure 5C). D-POMCP model was also best at explaining human behavioral data, as shown in Figure 5D.

heading: 5 DISCUSSION

text:
In this work we proposed a novel map induction hypothesis – that humans use program induction to infer maps of novel environments from partial observations – and use the inferred map distribution to optimize exploration. We formalize this hypothesis computationally, by combining a Bayesian map induction model and an approximate belief-space planner. We present the results of two behavioral experiments that support the map induction hypothesis by demonstrating that our computational model predicts human exploration, and show that the performance of a Partially Observable Monte Carlo Planner can be improved by adding map induction.
While we explored map induction in a simple environment, it is likely to apply more widely – humans not only forage selectively but also consider only plausible theories or explore only a certain part of human-made structures. This may indicate that humans anticipate the structure of abstract search spaces by noticing repetitions and symmetries to simplify hard computing problems in various domains. Using map induction for exploration may not be unique to humans either – the evidence of rodents reusing grid-cell maps in similar parts of environments suggests that grid-cell remapping may be a neural signature of map induction (Derdikman et al., 2009; Carpenter et al., 2015). Hippocampal reuse of place-cell maps in composite environments (Paz-Villagrán et al., 2004), which are invariant to rotation and scaling (Muller & Kubie, 1987), suggests that animals use landmark cues to guide map induction as well.
In future work we intend to study map induction in larger, more naturalistic environments, where more comprehensive generative models may be needed for map induction in order to optimally induce the generative programs used to generate these environments.
Our work takes a step toward understanding efficient exploration in novel environments by modelling map induction. We show that map induction can be used to optimize state-of-the art approximate planning, and may support building better exploration algorithms in AI. It may also have potential applications for fast and generalizable map learning in the field of SLAM.
REPRODUCIBILITY STATEMENT
The source code for the models and the behavioral datasets used for this project are made available at the following GitHub repository, along with instructions on how to use them. https://anonymous.4open.science/r/Map-Induction
The compiled Unity WebGL build packages for both experiments presented in this paper are also provided at the above repository. The builds can be hosted using any web hosting service (e.g., simmer.io) in order to re-run the experiments and reproduce experimental results. The Unity source code used to generate these builds is available on request.
To ensure reproducibility, the behavioral experiments are also explained in detail in the Appendix.
Our institutional IRB approved all experiments.

heading: A APPENDIX

text:
A.1 EXPERIMENT 1
Figure 6 shows the stimuli used in the experiment, with practice stimuli in panel A and test stimuli in panel B. Each of the test stimuli is composed of a corridor connecting five instances of a specific unit. The rewards (diamonds) are placed at identical locations within each unit. The task was to navigate the environments and collect all the diamonds in the least amount of time. At the beginning of each trial, the subject is spawned at a fixed starting location (marked by a red floor-mat) in all environments. The subjects can then use the keyboard and mouse controls to explore the environment and find the diamonds. Note that there are six base test stimuli with the other six as their reflected versions. We use reflected versions to counter-balance the left and right turns required across environments during the experiment and to increase the number of experimental trials while saving effort on environment design. This experimental design can also be used to study how map induction generalizes to transformations of environments (these results are out of the scope of this paper and are therefore not presented). For instance, we noticed that subjects were able to use program induction across environments when they shared similar spatial structures.
Figure 7 shows the scenes displayed during the progression of the experiment. Figure 7A is the welcome scene that subjects see at the beginning of the experiment. Here, we confirm that the subjects consent to participating in the experiment voluntarily, and collect their age and gender information. Figure 7B is the next scene that provides instructions to the subjects about the task and the keyboard/mouse controls that they can use to navigate during the task. Figure 7C shows the first practice trial and is followed by three additional practice trials in the order shown in Figure 6A. At the end of each trial, a “Level Complete” (Figure 7D) or “Out of Time” (Figure 7E) pop-up window is displayed depending on whether the subject collected all the diamonds in the environment or ran
out of time before doing so. Both these pop-ups also specify the ratio of the number of diamonds collected to the total diamonds embedded in the environment. This provides feedback to the subjects about their performance in the trial before they continue to the next trial. At the end of the practice trials, subjects are presented with an instruction quiz as shown in Figure 7F, to ensure that they understand the task. If they answer the instruction quiz incorrectly, they are requested to re-read the instructions and re-do the practice trials, and are sent back to the instructions scene in Figure 7B.
If the subjects answer the instruction quiz correctly, they are presented with the twelve test trials (see Figure 6B) in succession. An example test trial is shown in Figure 7G. The test stimuli are grouped into three blocks containing four stimuli each, according to their difficulty level. For each subject, the order of stimulus presentation within blocks is randomized, while the blocks themselves are presented in a fixed order e.g., block1 (simple environments - Env1, Env1R, Env2R, Env2R) is presented first, followed by block2 (moderate complexity - Env3, Env3R, Env4, Env4R), followed by block3 (high complexity - Env5, Env5R, Env6, Env6R). After the test stimuli, a final scene in Figure 7H is shown to thank the subjects for their participation, to get their comments about the strategies they used to solve the task, and their general feedback about the experiment.
Figure 8 shows the results from the experiment. Panel A shows the trajectories of a representative subject on six base test trials (Env1-Env6), shown in the order presented to the subject (top - bottom). Panel B shows the visitation heat-maps indicating the least to most visited regions in each environment, averaged across subjects. The heat-maps are aggregated across the base environments (Env1-Env3) and their reflected versions (Env1R-Env6R) shown in Figure 6B. Separate heat-maps for the base environments and their reflected versions are also shown in Figure 13 for comparison between the first and the second presentation (mirrored with respect to the first presentation).
A.2 EXPERIMENT 2
Figure 9 shows the stimuli used in this experiment, with practice stimuli in panel A and test stimuli in panel B. The practice stimuli have color cues at the entrance indicating the location of diamonds. Each of the test stimuli is composed of a corridor connecting five instances of a specific unit. Unlike Experiment 1, the diamonds are placed at different locations within each unit determined by the color cue in the cue room of the unit. Relative to the base test environments (Env1-Env6), the reflected versions (Env1R - Env6R) have a reflected geometry, however unlike Experiment 1, they have a different reward distribution. The task was to navigate the environments and collect all the diamonds in the least amount of time. At the beginning of each trial, the subject is spawned at a fixed starting location (marked by a red floor-mat) in all environments. The subjects can then use the keyboard controls to explore the environment and find the diamonds.
Figure 10 shows the scenes displayed during the progression of the experiment. Figure 10A is the welcome scene - same as in Experiment1. Figure 10B is the next scene that provides instructions to the subjects about the task. The next scene is the instruction quiz shown in Figure 10C that ensures that subjects have read the instructions. If they get the quiz wrong, they are sent back to the instructions page, and requested to re-read them. This is followed by five practice trials in the order shown in Figure 9A. As an example, the second practice trial is shown in Figure 10D. At the end of each trial, a “Great Job” (Figure 10E) or “Out of Time” (Figure 10F) pop-up window is displayed depending on whether the subject collected all the diamonds in the environment or ran out of time before doing so. Both these pop-ups also specify the ratio of the number of diamonds collected to the total diamonds embedded in the environment. This provides feedback to the subjects about their performance in the trial before they continue to the next trial. At the end of the practice trials, subjects are presented with another instruction quiz as shown in Figure 7G, to ensure that they understand the task. If they answer the instruction quiz incorrectly, they are requested to re-read the instructions and re-do the practice trials, and are sent back to the instructions scene in Figure 7B.
If the subjects answer the instruction quiz correctly, they are shown additional instructions (Figure 10H) and another instruction quiz (Figure 10I) before moving onto the test trials. Next, the twelve test trials (see Figure 9B) are presented in succession. An example test trial is shown in Figure 10J. The test stimuli are grouped into two blocks containing six stimuli each, according to their difficulty level. For each subject, the order of stimulus presentation within blocks is randomized, while the blocks themselves are presented in a fixed order e.g., block1 (relatively simple environments - Env1,
(i) (ii) (iii) (iv)
A
Env1R, Env3, Env3R, Env5, Env5R) is presented first, followed by block2 (high complexity - Env2, Env2R, Env4, Env4R, Env6, Env6R).
After the test stimuli, subjects are subjected to a controls skill test unbeknownst to them, to test their skills using navigation controls. This test is introduced to ensure that subjects are able to navigate in WebUnity without undue difficulty, given the larger environments, and a relatively higher cognitive
load in this experiment. The test is introduced at the end rather than at the beginning to account for the deterioration of control skills due to fatigue. Subjects are shown the scene in Figure 11A that tells them that they are about to enter an environment with ten diamonds, one in every room. They are instructed to visit every room to collect all the diamonds. Figure 11B shows the controls skill test trial with the top-down view of the stimulus shown in Figure 11C. To pass the test, subjects must collect all the diamonds in this trial. The test helps disqualify two types of subjects: i) subjects who do not complete the experiment i.e., wait at the entrance without exploring the spatial environments, in the hope of getting the base payment from the study; ii) subjects who have difficulty navigating
in WebUnity due to inexperience/fatigue or difficulty with controls since they may not have the appropriately functioning control devices (mouse/keyboard). Subjects who failed the controls skill test were paid, but excluded from the analysis. Figure 11D shows the trajectory of a representative subject who failed the test. After the controls skill test trial, a final scene is shown to thank the subjects for their participation, and to get their comments/feedback.
Figure 12 shows the results from the experiment on the six base test stimuli (Env1-Env6). Panel A shows the trajectories of a representative subject. The stimuli are shown in the order presented to the subject (top - bottom). Panel B shows the heat-maps indicating the least to most visited regions in each of the base test environments, averaged across subjects. Separate heat-maps for when the base environments are shown during the first and the second presentation (mirrored with respect to the first presentation) are shown in Figure 14.
A.3 MODEL LIKELIHOOD COMPARISONS
Our model likelihood analysis aims to compare the similarity of human decisions to model decisions. Specifically, we wanted to determine which models made the most human-like decisions. Because action-level similarity was too granular, we decided to compare room visitation similarity. We accomplished this by manually breaking each map into a set of convex rooms as shown in Figure 16. Using this map decomposition, we obtained an ordering of visited rooms for each human on each map. For each point on the human trajectory, we provided each model with the current human initial state and history of human observations. We asked the model to find an optimal plan from this state. The result of such a query to the models is a policy tree of the branches on observations. The most significant statistic of a POMDP policy tree is visitation frequency of nodes on the tree, as this serves as a surrogate for the value of that state according to the model. We look at all trajectories in the policy that led to new rooms and summed and normalized their state visitation frequency in the policy tree. This result for a single point in the human trajectory is a distribution of rooms that the model is likely to visit given the human’s experience. The model likelihood for a particular human
is defined as the average (arithmetic) probability of the human’s next room in the model’s visitation tree.

title: MAP INDUCTION: COMPOSITIONAL SPATIAL SUBMAP LEARNING FOR EFFICIENT EXPLORATION IN NOVEL ENVIRONMENTS