Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: This paper concerns the question of if and when the transition dynamics of an MDP can be determined based on a policy together with its corresponding inverse dynamics. In the case of single-step inverse dynamics, they find that this is not the case, unless the number of actions is greater than the number of states, and each action corresponds to a full-rank transition matrix. The paper also studies a number of similar questions.
strengths_and_weaknesses: Originality:

This question has, to be best of my knowledge, not been examined previously (at least not as thoroughly as in this paper). However, some of the results seem to be reasonably straightforward (for example, the fact that the transition dynamics cannot necessarily be inferred from a given policy together with its corresponding one-step inverse model is immediately clear if one considers any policy that samples actions independently from the state).


Quality:

I have not checked most of the calculations carefully, but based on what I have checked, the maths appears to be sound.


Clarity:

The clarity of the writing is reasonable, but could be improved. For example, the text takes time to explain elementary notions from linear algebra, and other facts that I think the reader could reasonably be assumed to be familiar with (such as e.g. the fact that matrices form a ring under ordinary matrix addition and matrix multiplication, etc). I also think the paper could be better organised. For example, the introduction does not make it clear what are the main results of the paper, or what their significance is, and it takes some digging to get a full overview of things.


Significance:

I think that the significance of the results is not well explained in the paper, and this is one of its main weak points, in my opinion. The introduction states that the presented results are relevant to causal inference, but the example that is given afterwards is just an instance of normal retrodiction, which doesn't engage with most of the issues discussed in the current literature on causal inference. It is also stated that these results could be of interest for automatic planning, but this seems unclear to me (at least in their current form). It is also stated that the inverse model could be much smaller than the forward model, but it is again not clear to me why that is (practically or theoretically) significant.


Summary:

I have not recommended this paper for publication. The main reason for this is that the problems which are studied here are fairly niche, and it is somewhat unclear what their significance is. Moreover, many of the problems which are stated in the paper are not solved, and some of the ones which are solved are somewhat straightforward. For this reason, I do unfortunately not think that these results will be of significant interest to the wider NeurIPS readership.
questions: What is the main (practical or theoretical) significance of these results? Which result is the most important?
limitations: The limitations are discussed, though this discussion is dispersed throughout the paper, rather than being collected in one place. There is no discussion of potential negative societal impacts (but I also do not think that is needed in this case).
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors pose the question of whether or not the 1-step inverse model, along with the policy \pi, determine the multi-step inverse model p(a | ss^i) - or if the forward dynamics of an environment can be inferred by the inverse model plus policy. Besides this question, the work also looks to analyze other cases of whether or not the 1-step inverse model and policy can determine other forms of inverse dynamics, such as the multi-step inverse models, and present analysis and empirical evidence for when these cases hold or when they do not hold. 
strengths_and_weaknesses: I believe that the authors make a meaningful and well-justified contribution towards understanding the theory behind inverse dynamics models and reinforcement learning as a whole. The authors present interesting theoretical insights into the realizability and limitations of inverse models, along with algorithms to potentially calculate both the two-step inverse model and forward dynamics model from the inverse model plus policy. 

In terms of weaknesses, one weakness that comes to mind from the perspective of someone not too familiar with this form of reinforcement learning theory is the writing itself - the writing style is hard to follow in many parts, taking multiple passes for even some of the non-notation heavy parts - this seems to come from the somewhat informal tone the authors take in this manuscript, that sometimes adds a bit of cognitive burden for a reader of this paper. While the authors might be very familiar with the notation and work, I believe it would improve the polish of the paper quite a bit if the authors were a bit more careful and precise with their use of language and notation.

Finally, I believe the experimental section has a decent amount to be desired. While I don’t think there’s anything wrong with the fundamental methodology of their experiments, the authors have left out quite a bit of experimental details and forego presenting actual statistics of experimental results - instead they simply present two examples in the main work. While they do show a plot detailing the effect of adding noise to the inverse dynamics models, my biggest question is with the grid world generation itself. It seems that most of the grid worlds generated would have very sparse dynamics (like in the second grid world presented) - many of the positions/states would be unreachable from many other states. It would be more clear if the authors presented more details on their experiments done to validate their theory.

Overall, while I not intimately familiar with the theory presented in this paper, I do think this work provides a valuable contribution to the field in terms of understanding the limitations of inverse dynamics models.

questions: As an aside, many of these questions will be clarification questions - hopefully these questions will help polish the paper so that it’s more clear for a more broad set of readers.

Section 2:
For the end of section 2, could you give an example of how one of the 6 questions can be inferred from f(M) = f(W) -> M = W? I find it a bit hard to follow what this other MDP W relates to B^a and M^a.

Your overloaded notation for EqIM is a bit confusing. You defined EqIM(ia) and EqIM(i+), but not EqIM(i).

Section 4:
For the introduction to this section, it would be nice to relate back to the 6 questions the authors were trying to answer and how EqIM(1) and EqIM(2) relates to those questions. This also relates back to my question in Section 2 about your definition of EqIM and how it is another way of posing the questions.

Section 5:
Again, it would be good to relate back to the questions. Correct me if I’m wrong but this section tries to answer (iii) to (vi)?

Section 6:
I don’t see the experimental details listed anywhere - how do you generate these randomized grid worlds? 

Also instead of just showing samples of the true vs inferred forward dynamics matrices, I think it would be more prudent to show statistics gathered from experiments, instead of just one or two examples. See limitation for more suggestions for experimental section.

limitations: One limitation of this approach is the scalability to large-scale environments. While this is a limitation, I don’t believe this is any issue in the analysis provided in this work, or with the claims made. That being said, it would be very interesting to see how well some of these theoretical claims hold in larger environments, with more complicated dynamics/inverse dynamics that can’t be feasibly represented with tensors.

Another limitation of this work is with the experiments and empirical results. While the do run experiments to back up the theory they develop, they don’t provide details of their experimental set up, nor do they present any meaningful statistics with regards to their main result - showing one or two examples from generated grid worlds in the main work (the first grid world does not match the canonical 4-room by the way - it is something akin to it), and presenting a few plots over noise added for noisy inverse models. There is also stochasticity from the grid world generation - was there a lot of variation in terms of inferred dynamics models in the deterministic case? How were the grid worlds generated? It seems that (based on the second grid world presented) the dynamics of the grid world would be quite sparse. As mentioned earlier, presenting a more detailed account and analysis of the experiments done would improve the paper.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: This paper analyzes the prospects of inferring meaningful inverse models of discrete-time controlled Markov processes. In particular, the paper focuses on determining the existence/uniqueness properties of these inverse models, and investigate the computational complexity of computing them.
strengths_and_weaknesses: Unfortunately, several technical parts of this paper concern me. There are several mathematical statements that I believe to be invalid (see the Questions section). Moreover, I found the structure of the paper to be extremely confusing, especially the recurring "questions" which are rephrased several times, some of which (as far as I'm concerned) are not rephrased correctly. Finally, the notation used in the paper is very difficult to parse.
questions: **General Question**: As the authors acknowledge, the setting here is not that of inverse MDPs, but inverse controlled Markov processes. I'd argue actually that it's simply inverse Markov chains, since the policy appears to be fixed everywhere. How do the studies in this paper differ from those in the inverse kinematics literature?

  **Motivation: causal inference, line 24**: It is written that "An
  inverse model captures the likelihood that an action $a$ was *the
  cause* of the transition...", but is this truly correct? To my
  understanding, such a conditional model is incapable of inferring
  causation. Wouldn't one need some sort of counterfactual analysis as
  well?

  **Marginalizing variables in transition tensors**: On lines 120 and 121,
  I believe there is an inconsistency in the notation. In the Notation
  section, it is writen that $M^a_{\cdot\cdot}$ is the matrix at
  dimension $a$, but here it is written $M^a$. I'm assuming $M^a,
  M^a_{\cdot\cdot}$ represent the same thing, but then maybe the
  $M^a_{\cdot\cdot}$ notation should be avoided altogether.

  **Challenges with the backward model**: Line 127 says $B^{a+}\neq B^a$,
  can this be expanded upon? This is unintuitive, at least to me. After
  line 121, it says $B^a_{ss'} = p(a\mid ss')$, and after line 129 it
  says $B^{a+}_{ss''} = p(a\mid ss'')$, thus

  \begin{equation*}
  \begin{aligned}
  B_{ss'}^{a+} = p(a\mid ss')  =B_{ss'}^a
  \end{aligned}
  \end{equation*}

  Which implies that $B^a = B^{a+}$ since all of their entries are
  equal.

  **The Questions**: The six questions, first stated on line 46, are very
  confusing. Firstly, they're stated in different terms several times,
  which is confusing on its own. Why not list the questions only once,
  in the most intuitive way? Moreover, the questions are too complicated
  individually. I think it would be much clearer if you don't state all
  of these questions explicitly, and rather prove the answers as
  theorems/lemmas/propositions. It's very hard to remember which
  question is which as you go through the text, and it's actually very
  hard to digest what the paper is trying to do with such a dense list
  of questions. In my opinion, the motivation for the paper is clear
  enough on its own, and I don't think it'll be difficult to convince
  most readers that understanding these inverse models is an important
  task. But when the exact meaning of "understanding" is stated so
  verbosely, it actually detracts from the clarity of the paper. One
  example that is particularly confusing appears on line 139, where it
  says "Questions (i) - (vi) also have multiple variations", followed by
  a list of three questions. How do you go from 6 questions to 3, which
  correspond to which? Now you're actually assuming that the reader will
  recall at least 9 questions.

  Moreover, if you must include these questions, it would be
  tremendously more convenient if they can be hyperlinked.

  **Line 149**: Another rephrasing of the questions here says

  > One way to rephrase the questions is whether $f(M) = f(W)$
  > implies $M=W$ or $g(M) = g(W)$ for all (or most or some)
  > $M$ and $W$.

  I don't understand this question at all. The property that $f(M) =
  f(W)\implies M = W$ is more a property of the function $f$ than the
  objects $M,W$. Indeed, this property is known as
  "injectivity". Likewise, "whether $f(M) = f(W)$ implies $g(M) = g(W)$"
  is also highly dependent on the particular properties of
  $f,g$. Currently $f,g$ are only assumed to be arbitrary functions, so
  it is really unclear to me what the purpose of this question is. I had
  a clearer understanding of the questions before reading this.

  **Equations (8) and (9)**: Surely the notation can be improved here, it
  is extremely difficult to parse. Why not use product notation
  ($\prod$)? Also, in equation (9), what is $B^{a+\dots+}$? Are there
  $i$ dots? Back to my previous comment, I believe $B^{a+\dots+}\equiv
  B^a$ unless there's an inconsistency in the notation.

  Later, on line 161, the term $\text{EqIM(1)}$ is mentioned, but where
  is that defined? Only equations $\text{EqIM}(ia)$ and
  $\text{EqIM}(i+)$ are defined.

  **Example violating (i, iii, v)**: It appears that what you're showing
  is that for random variables $X, Y$ distributed by $\mu_X, \mu_Y$,
  there may exist several distinct random variables $(X, Y)$ with
  marginals $\mu_X, \mu_Y$. This is well known.

  **Line 169**: I don't understand how this relates to (i), (iii), (v) at
  all. You're assuming that two MDPs encoded by $M,W$ have the same
  transition dynamics, and then based on that, the ability to infer
  multistep models from fewer-step models is guaranteed? Something is
  missing here. How does $W$ fit in?

  **Line 171**: It says "Note that $M_{ss'}^a\equiv p(s'\mid sa)$
  independent of $a$ implies $M_{s+}^a$ independent of $a$..." -- this
  is only true if it holds /for every pair/ $(s, s')$. Also, this whole
  "degenerate case" is fairly trivial: $M$ and $W$ are only related via
  $\pi(a\mid\cdot)$, so if they're both actually independent of $a$,
  then of course any equality of this sort must imply that the MDPs are
  identical.

  **Line 175**: What does it mean for tensors to be "nearly independent"
  of $a$?

  **Line 178**: Similarly to the "independent of $a$" case, why is this
  even an interesting case to study? As pointed out, the consequences
  are fairly obvious.

  Altogether, I didn't find section 3 to be very informative.

  **Non-linear manifold**: On line 212, it says that $B^{aa'}$ forms a
  non-linear manifold of dimension at least $d(d-k)$. But what is the
  "dimension" of a non-linear manifold? Perhaps there is a definition
  for this, but I doubt it's widely known to the Neurips audience. I'd
  much prefer to have seen this definition in the background section in
  place of the algebraic properties of tensors.

  **Line 214**: I believe this logic is flawed. It says "... this now
  gives an over-determined system which generally has no solution. But
  by assumption, $M$ is a solution, which gives hope that there may be
  only one or a finite number of solutions". What is being said here is
  that the situation only makes sense if the "over-determinacy" is
  redundant, so that it's not actually over-determined. This doesn't
  give any hint about the number of solutions. There may very well be
  infinitely-many solutions regardless of the fact that the system is
  over-determined.

  **Figure 1**: This figure is never mentioned in the text, it would be
  nice to have some discussion of the results it's presenting.


Minor issues
============

  **Contents section**: On line 88 "Appendix A" is mentioned, but then
  subsequent appendices are written "(B)", for instance, which is a
  little confusing.

  **Matrix notation**: On line 105, it is written "Capital letters... are
  used for $d\times d$ matrices over $[0;1]\subset\mathbf{R}$...".  Is
  $[0;1]$ the closed unit interval? Why not write "Capital
  letters... are used for matrices in $[0, 1]^{d\times d}$"?

  **Tensor notation**: On line 109,

  > Let $\odot$ denote element-wise (Hadamard)
  > multiplication... and similarly $\oslash$, while (no)
  > $\cdot$ represents (conventional) matrix multiplication
  > and has operator preference over $\odot$ and $\oslash$.

  I don't understand this at all. What is $\oslash$? What is $\cdot$?
  I'm assuming that by "similarly $\oslash$" it is meant that $\oslash$
  is element-wise division (this should be stated, because the sentence
  doesn't make sense otherwise), and that $\cdot$ represents matrix
  multiplication. But what does "while (no) $\cdot$" mean?

  **Algebraic properties of tensors**: Does this really need to be
  included here? It's hard to read math packed into a paragraph like
  this. Also many of these properties are very intuitive (i.e., I think
  just about every reader will have inuition for the $D\odot\text{Id}$
  property without it being stated), and then some properties are highly
  abstract (matrices form a ring...). I think it's fair to assume that
  readers of this paper understand how to do algebra with matrices and
  tensors, even if they don't know what a ring is.

limitations: The authors have addressed the limitations of their methods.
review_title: null

Meta-review: metareview: In this paper, the authors concern the question of whether or not the 1-step inverse model, along with the policy, can determine the multi-step inverse model - or if the forward dynamics of an environment can be inferred by the inverse model along with the policy. The authors also dwell into other related questions. The authors provide insightful answers and discussions to these questions, but the paper is unfortunately written in a very unconventional format which makes it very hard to read. I hope the authors find the reviewer comments below help restructuring the paper to better enlighten the readers.
confidence: Less certain
Decision: Reject