Inferring the Future by Imagining the Past

Summary

This paper presents an efficient Monte-carlo algorithm to infer goals from single snapshots. The problem the authors consider is the same as in work by Lopez-Brau (2020, 2022) but previous solutions are slow as they apply rejection sampling. In this work, the authors use the insight that one can sample a valid path by sampling the part of the path "before" the current snapshot and "after" the snapshot independently, decresing the computational complexity by a large amount. Further, A-star search is used to find likley paths. The authors validate their algorithm on different grid worlds and provide results of a human study indicating that inferences of their algorithm coincide with human judgements.

Strengths

The problem of inferring goals from a single snapshot is interesting, as a major limitation of most IRL methods is that they only work in a certain context (state/actions of the full trajectory). The paper is clearly written and easy to understand. The presented method is much more efficient than previous methods in terms of scalability. The plausability of the results found by the algorithm is supported by human experiments.

Weaknesses

Quantities are not clearly defined. Are states/actions/goals continuous or discrete? In the formulas, one integrates over states and sums over actions. It might be very helpful for the reader to formally define the MDP and its sets. Further, what are "paths" formally, what does the indexing operator "[0]" mean for paths? While the main idea of the algorithm to sample the path "before" and "after" is very simple, the overall algorithm seems quite hacky to me: The basic idea is combined with other tweaks such as roulette termination and A-star search to avoid unlikely paths. With these, the considered tasks can be efficiently solved but there is no particularly nice linking theory. In my opinion, the contribution is not strong enough for a NeurIPS submission as the main (conceptual) difference to previously published algorithms is not that large. The essential difference is that parts of the path before and after are sampled, together with other tweaks. I would find it helpful if the algorithm clearly indicated which quanitity it computes (p(x | g)), this is not direcly visible. The plots in Table 1 do not have a colorbar, therefore the precise meaning and interval of the color's values is not clear to me.

Questions

The regarded grid worlds all have a discrete state/action space. Is the algorithm applicable to the continuous domain? When introducing the algorithm, you write that the situation of the agent you consider is an MDP but you would relax this assumption later in the paper. Where do you do that?

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

Limitations are well discussed. To my understanding, only discrete state/action/goal spaces are considered. This point could be added.

Summary

This papers proposes a new approach to the inference problem of inferring an agent's goal state from information about a single state. This approach is based on the bidirectional Monte Carlo sampling of trajectory sequences, both from the agent's given state $x$ to the goal state $g$, and from an initial state $s$ to $x$. The authors show near convergent inference of the approach with 10 samples on two gridworld based environments, and a word game kind of environment when evaluated against human judgement.

Strengths

- The evaluations show a strong "near" convergence result of only 10 samples, even for multi-stage planning. This indicates their sampling strategy is practically sample-efficient, and a huge improvement over prior approaches requiring more than 300,000 samples (reportedly). - The connection drawn from path tracing in computer graphics is a fresh insight, which the authors show applies well to the goal/previous states' inference problem, and can potentially have broader scope applications such a for spatial navigation tasks etc. - The use of human judgement (using 200 participants) for evaluation is also a very reasonable choice instead of hand-engineered reward functions designed by a single person/a few people. - The authors also show efficient sampling in a variety of other domains (in the appendix) which indicates it is more broadly applicable.

Weaknesses

- _Experiments_: Something I might myself be unclear about, so let me know if that is the case-- there are no evaluations comparing the proposed model in this paper with the model shown by [Lopez-Brau et al 2022](https://psyarxiv.com/4zu9n), is this only because of sample-efficiency? It would be interesting to see how "nearly" convergent their proposed approach is in the cases where it can be applied. - _Theoretical analysis_: What is the complexity of the sampling with the size of the state space, the number of accessible states, the number of starting/goal states etc-- is it possible to perform some kind of theoretical analysis of this? I'll be very happy to increase my score on the addressal of these concerns/doubts.

Questions

- Have you checked how the sampling scales with an increasing number of possible starting states, and an increasing number of possible goal states? It could potentially be interesting to see. - Why is incremental A-star search used for planning on-line? - I am wondering if its possible to emphasize more on the scope of the applications of the proposed sampling approach-- what other domains can it be used in, apart from tasks that look like spatial navigation? The word blocks is one good example, also the cartpole experiment. There are intuitive physics based experiments, or reasoning based tasks which involve inferring over a sequence of images say, can this approach be applied there?

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

The authors adequately address the limitations of their approach, especially when it comes to sampling over goals, or scaling up to a larger goal space. There is just one minor point here-- the approach is based on a combination of well-founded insights and ideas, which when put together, work well, but there seems to be a lot of hand-engineering/domain-specific engineering in assembling these together, which I think should be acknowledged in the paper.

Summary

This paper presents an algorithm for efficiently inferring the goal of an RL agent from just observing its current (single) state $x$. The method improves substantially upon rejection sampling based prior work by 1) only sampling paths through $x$ by separating the path into past and future 2) sampling the past path backwards in time starting from $x$ and 3) using incremental A-star search for planning. The efficacy of the approach is demonstrated in two gridworld domains and a word-blocks game (as well as three more in the supplementary). The posterior estimates over the goal of the agent qualitatively match human judgements, and converges several orders of magnitude faster than vanilla rejection sampling.

Strengths

* The studied problem is interesting and potentially impactful for multi-agent RL or human-agent interactions. * The algorithmic modifications are well motivated and the efficiency improvement above simple rejection sampling is impressive. * The paper validated the results against human judgements and found a high correlation * The presentation is unusually clear, and a fun read.

Weaknesses

The quantitative evaluation in Table 3 assumes the ground-truth to be a converged estimate of the presented method. This leaves open the possibility that the TV is better than the rejection sampling baseline because the presented method is biased in some way. The concern is partially addressed with the numerical validation check in the supplementary section B, which in my opinion should at least be mentioned in the main paper. Another way to strengthen the results in Tab 3 would be to also compare to a "ground-truth" estimate from (very?) many vanilla rejection samples. If the presented method is still better at approximating this ground-truth with few samples than rejection sampling with few samples, that would be strong evidence.

Questions

* I am unclear about the role of A* in the proposed algorithm (sec 2.3). I assume that $p(x\rightarrow x') \propto \sum_a \exp (\beta(C(x \rightarrow g) - C(x' \rightarrow g)) $ takes the role of the A* heuristic. But in A* this heuristic is used to decide which node to further expand next, and I cannot find the equivalent of this search process in Algorithm 2. Could you please clarify the correspondence of A* with the proposed algorithm. * I am unclear about the shaded cells in in Table 1. The description states that "Shaded cells were excluded from the analysis because it would be irrational for the agent to be there for any goal". I assume "shaded cells" refers to the gray cells in the rows corresponding to the keys world. But the shading of cells doesn't make sense to me. In row 3 it seems to correspond to inaccessible areas (which make sense to exclude). In row 4 the bottom third is shaded except for a single spot next to the green key. Why would that spot be less irrational than the surrounding ones? In row 5 the leftmost column is shaded which also seems odd. Is it impossible for the agent to start there? Also why are no cells shaded in row 1? Please clarify.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

4 excellent

Limitations

The authors discuss an important limitation of their work regarding the sampling over goals. Another limitation that may be worth pointing out is that the separation of paths into independent paths for past and future depends on the environment to be Markovian (this *is* mentioned in the paper). More specifically that the current states $x$ contains all information connecting the past and the future. For more realistic environments this would for example have to include quantities like velocity or any relevant inner state of the agent in addition to the current position. Relaxing this assumption would require accounting for latent states and thus be equivalent to observing a distributions over current states $x$ instead of a concrete state.

Summary

This paper deals with the problem of inferring the goal state $g$ of an agent given only a single state $x$ in a trajectory, i.e., inferring $p(g|x)$. For this, the authors claim that we need to integrate all possible initial states, and thus, sampling past trajectories is necessary for Monte Carlo estimation. They propose several techniques to improve the sampling efficiency, and the main technique is to sample the past trajectory in reverse, starting from the given state $x$.

Strengths

The key intuition and motivation are clearly described.

Weaknesses

### The key assumptions are not clearly stated I think the main text does not explain the key assumptions, such as - What is given? A fully-trained agent? A fully transparent environment with perfectly known dynamics? - How can we perform the past and future sampling? ### Soundness of the main argument Most importantly, I am not convinced that explicitly sampling the past trajectory is necessary to infer $p(g|x)$. Since $x$ contains all the information that we have, sampling the past trajectory seems like an unnecessary complication. I think we can train a predictor that produces $p(g|x)$ directly from a decent amount of offline trajectories. Moreover, I believe there is a serious mistake in Eq.(2). The left hand side of Eq.(2) is $p(x|g)$, but the right hand side assumes that every path passes through $x$ and does not consider the cases where $x$ is not included in the path. As the authors noted in L81-82, most paths would not pass through $x$, so there should be a term that account for this fact. ### Limited scope of the experiments The experiments are limited to simple toy problems like grid world.

Questions

- Please state the key assumptions - Can you prove that sampling the past trajectory is absolutely necessary to predict $p(g|x)$?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

Yes

Response to rebuttal

I thank the authors for the clarifications, and for providing additional evidence for the unbiasedness of their method. Their response addresses my questions and concerns and would like to reaffirm my recommendation for a strong accept.

Response to rebuttal

Thank you to the authors for answering my questions and for the detailed clarifications! - sample complexity analysis: I see, makes sense. Thanks for attaching the plots, nevertheless. - revision of writing and scope of work: The authors' response of revising the paper with respect to their contributions and motivation for using incremental A* seems reasonable to me. Thus, I increase my score to 8 for a Strong Accept.