Uniqueness and Complexity of Inverse MDP Models
Authors: Marcus Hutter
Steven Stenberg Hansen
Venue: NeurIPS 2022 Submitted (2022)
Keywords: inverse models
reinforcement learning
causality
theory
multi-step models
reasoning

Abstract: What is the action sequence aa'a" that was likely responsible for reaching state s"' (from state s) in 3 steps?
Addressing such questions is important in causal reasoning and in reinforcement learning.
Inverse "MDP" models p(aa'a"|ss"') can be used to answer them.
In the traditional "forward" view, transition "matrix" p(s'|sa) and policy π(a|s) uniquely determine "everything":
the whole dynamics p(as'a's"a"...|s), and with it, the action-conditional state process p(s's"...|saa'a"), 
the multi-step inverse models p(aa'a"...|ss^i), etc.
If the latter is our primary concern,  a natural question, analogous to the forward case
is to which extent 1-step inverse model p(a|ss') plus policy π(a|s) 
determine the multi-step inverse models or even the whole dynamics.
In other words, can forward models be inferred from inverse models or even be side-stepped.
This work addresses this question and variations thereof,
and also whether there are efficient decision/inference algorithms for this.

Uniqueness and Complexity of Inverse MDP Models
Anonymous Author(s)
Affiliation Address
email
Abstract
What action sequence aa'a" was likely responsible for reaching state s" (from state s) in 3 steps? Addressing such questions is important in causal reasoning and in re- inforcement learning. Inverse "MDP" models p(aa' ofaaaa"|ss"" a"|ss"") can be used to answer them. In the traditional "forward" view, transition "matrix" p(s' ss)) and policy x (als) uniquely determine "everything": the whole dynamics p(as' a' s=."...|s) and with it, the
(s))
state process p(s' ss"..|ssad' a"), the multi-step inverse models p(aa' a".../ss*" "...|ss'), etc. If the latter is our primary concern, natural question, analogous to the forward case is to which extent 1-step inverse model p(a ss') plus policy π (a|s) determine the multi-step inverse models even the whole dynamics. In other words, can forward models be inferred from inverse models even be side-stepped. This work addresses this question and variations thereof, and also whether there are efficient decision/inference algorithms for this.
11
12
Keywords
13
inverse models; reinforcement Icarning; causality; theory; multi-step models; planning.
Introduction
14
Consider MDP with actions E (0,....k=11 and states s E (1.....d) Rewards play role in our
16 analysis, so controlled Markov process (DY79] or conditional Markov chain may a more apt naming. Transition "matrix" p(s'[sa) (" ("Forward model") and policy π (als) uniquely determine the
18 whole dynamics
p'as'd's"a
=<als) ((sss)pps'((sse ((s((sa) (aa (())ass'))aa))) (')sp(""(s'')))
and also determines the action-conditional state process ("Multi-Step Forward Model"):
pls 6" ... a") plas'd a' s" a" ...ss////// Σ a'a
Here consider Inverse Model (ss) and Multi-Step Inverse Models p(aa'a"...le .ssls'""''"'tt s"" s".... and p(alss") and variations thereof. Inverse MDP models should not confused with inverse reinforcement learning AD2I]. which infers rewards, which play role here.
21
23 Motivation. One motivation to consider inverse models is causal inference: An inverse model the cause of the transition from state state s'. A 25 multi-step inverse model captures the likelihood that a first action or action sequence aa'...a" the cause of the state sequence ss'...s" the cause of the transition from state state s². The 27 latter is the primary goal (automatic/stochastic) planning [HSHB99]: to find an action sequence that leads to desired goal state s' = Sgual- The shortest path, i.e. smallest i, that reaches Sgual (with
24 captures the likelihood that action
29 high probability in the stochastic case) can easily be found via a trivial search over i i= 1,2,3... if the fixed-i planning problem can be solved efficiently.
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). not distribute.

---

31 Another machine-learning motivation is that inverse models may be substantially smaller than
32 forward models. For instance, an action- irtion-iddependent Markov process p p(s'|sa) = p(s'ss) may
33 be very complex for large d, but for state-independent (known) policy x x(als) = m(a). the in-
34 verse model p(aa'...|s...$ ..) = . (a))(a)) is trivial (and known). Of course this extreme case
35 is uninteresting, but a partial similar simplification happens if state s decomposes into s == (3,5)
36 [EMK* 22). In this case, if the forward model p(s' ss) factors into (simple) controlled p( (sa) and (complex) uncontrolled p( (3), and the policy T ((]ss) I (a] only depends on (small) s, then aaad'... ... s...sssss........ .... = p(aa'...|$.....
37
38
is independent of (large) S. Note that this simplification happens "utoomaticall"". We do not need to know the factorization structure, say (8,3) - f(s) for some unknown f. Appendix B contains bit of practical contex//motivaioo/appiicail
39
40
Main questions.
42
The main question we consider here is: to which extent do inverse model p(a)ss') plus policy π (Taas))
43
determine the multi-step inverse model or even the whole dynamics.
44
45
For instance, do p(alss') plus s[als) determine
46
(i) the full dynamics I
(ii) the full dynamics, if also p(aa"|ss") is provided,
47
(iii) the multi-step inverse model p(aa'...|ss (or p( piaaa'..|ss' sa.ss)..)) ...).
48
49
(iv) the multi-step inverse model p(aa''... (as"...|ss") (or p(aa'
Laa'...|ss sss' s")), if also p(alss") is provided,
50
(v) just the initial action p(a) ss") from just final state s"
51
(vi) p(a (ssss)) ) if also (alss") is provided,
52 and variations thereof? Also, is there an efficient algorithm that can decide whether the solution is unique and/or computes any or all of them?
54
Unlike in the "forward"' case (T). the answer to all these questions 'complicated' and 'sometimes', For instance, (i) is true iff k 2 d and p(s'(sa) has full rank. (ii) seems true for "most" transition matrices. (iii-vi) can fail, but (iv) and (vi) seem hold for interesting cases. In some situations there are efficient algorithms which sometimes work.
55
56
57
58 Related work. There is of course abundant literature on causal reasoning in general [G and in the modern context of Deep Learning in particular [OKD=211 21), but to the best of our knowledge, the setup and questions we are asking are novel, at least in this generality and rigor.
60
61 A special case of our setup is considered in (EMK* 22). The authors consider Exogenous Block MDPs (EX- 3DXB) which correspond to the motivating decomposition example above, and formalized in
62
63 Section as tensor- -wwoorrr-ruutttoo MDPs. Additionally they assume episodic MDPs with -etermeteriiiisticc
64 dynamics. Their PPE algorithm finds action sequences of high inverse probability p(aa' ...a' -aaaa11p [ss')
85 in polynomial time in á rather than s, while our aim is to infer higher- from lower-step inverse models
86 for general MDPs.
In the context of Deep Learning, there is ample empirical work that would benefit from a positive answer to our main question: Variational Intrinsic Control GRW17 and Diversity is All You Need [EGIL18] are representative of a broad class of methods that learn diverse options (policies/ / action sequences) that are inferrable from their effects the environment. This relies inverse modelling, as their mutual information objective is decomposed into maximizing skill/policy entropy and minimizing the entropy of an inverse model:
I(s a=.....--1l)) = H ((a)..o-"1s)--H(aaaa
This is akin to finding all action sequences of sufficiently high probability "'aa..."""'|ss" or all skills when the policy space is captured by auxiliary variable p(zlss'). The EDDICT algorithm H21 also maximizes this objective, and parameterizes the requisite inverse models such that they yield forward predictions, but as detailed in Section iits unlikely that such models would yield optimal multi-step inverse predictions in general. Dynamics-Awe Aware Unsupervised Discovery of Skills [SG decomposes the mutual information in the opposite direction, so to avoid learning an
67
68
69
71
73 inverse model and instead relies on a conventional forward model. Uniting all of the above mentioned methods is that the action sequence/skill horizon must be fixed priori. Inferring long horizon

---

75
inverse models from shorter ones (the topic of the present work) would allow all of these methods to circumvent this constraint.
78
77 A second stream of empirical work uses single-step inverse models for representation learning
[BEP* 18). Agent57 is arguably the most prominent of these methods [BPK 20), and therein the authors note that this choice of representation limits the generality of their approach, as multi-step effects can be aliased over. Despite this being known limitation, multi-step inverse models are not used as they are too cumbersome to effectively learn online. A positive result to our questions (iii) or (iv) would allow such methods to leverage multi-step inverse predictions despite only learning single-step model.
79
81
85
84
These two beneficiaries of improvements to the construction of stelt inverse models (filtering action sequences and state abstraction) dovetail into potential benefits for a broad range of planning algorithms, Exploiting this relationship between the questions addressed here and planning problems left to future work, but we sketch out the motivation more fully in Section
85
86
87
88
Contents. In Section 2 we will formalize questions (i)-(vi) in matrix/tensor notation. Section gives a first probe into these questions by considering various degenerate cases. In Section 4 study the solvability and uniqueness questions (i), when only B is given, i.e. the case
89
90
91 i == 1, in preparation for and showing the necessity of considering i>> 1. In Section 5 we provide algorithm via linear relaxation that works under certain conditions. Section 6 provides some validation experiments toy domains. Section concludes, followed by references. Appendices A contain a list of notation, more motivation, counter-example experiments, and more.
92
a polynomial-ting
94
2
Problem Formalization and Preliminaries
96
We now formalize our questions (i)-(vi) from the introduction, and for this purpose introduce some useful matrix notation. We are not aware of prior work addressing these questions, so quite some ground-worf to suitably formalize the various question is needed, and many little results are derived or mentioned in passing to give better insight into the structure the problem. To avoid clutter, we will not constantly point out edge cases or domain constraints. For instance quantities that represent probabilities are obviously non-negative and sum to one. The reader worried about divisions by 0 strictly positive, but most considerations
98
99
100
102
here and there should best assume that all probabilities and results naturally generalize with some care, c.g. by adding "almost surely" w.r.t. to the joint distribution ①I. Appendix Q contains proper treatment of 0/0.
104
105
106 Notation. Capital letters ,,,... are used for d x d matrices over [0:1] C RR and tensors by adding further upper indices, e.g. M: is order-3 tensor, and M a matrix for each a {0: 1) = k 1}. and A,C,V, are other tensors. We define Id to be the identity (eye) matrix 1d == des :- [== s'] Vs,s' E [1:d], dJ, and / to be the all-one matrix Las' = Vss'. We drop all- clear from context. Let O denote element-wise (Hadamard) multiplication ([oB)] B) A.s.B..... B.s)), and similarly Ø, while (no) represents (conventional) matrix multiplication and has operator precedence over O and Ø. Matrices form a ring under conventional (+,) and commutative ring under (+,0), but (A B) C A- (B@C). A diagonal matrix D has the matrix with Das in the whole of column (Var=V V.S Desr) Note that A-D A ([A-D) s E. Ass Ders"= Agg" Dzng"
108
110
quantifiers Vs,s
112
property D D= i.e. Das D.s[= s']. V I.
114
115
116
Ags" Vas" = iAo V J.s"). Similar left-right reversed identities hold. denotes 'undefined". See
117
Appendix A for full List of Notation.
118 Matrix/tensor formalization. We define [[)
Marginalizing out the action, gives p(s'ls)=> > p(as'(sss (.p(sssss (s) Ma. = Marginalizing out the next-state, gives back Ma. =: M.. For instance, the multi-step dynamics can be written as
119
π (alss)= -.
120
plas' d's" _..ss = p(as""s))ppa's "la")".. M Ma'...
121
Marginalizing out the intermediate states gives
"iad'...a--ss'1 1M-.M" ....aa Iss
3

---

122
The inverse MDP model can then be expressed as
B == p(alss') = p(as' ss)p((s(ss) = M M as' = [M
123
The multi- step inverse model given the whole state sequence becomes
pp(asss)p(''''(s)) p( p(='1s)p(="1("))
M M M M g'gh....
s"...
p(a| so (
(3)
124
and can easily be computed from the 1-step inverse models. To answer the primary question: which action sequence can lead to (desired) state s' from state s, we need to marginalize out s' s'...-- For instance, the two-step inverse model from s s" with s' marginalized out becomes
125
128
Bag' == plaa'|ss') = E. M.MMMM
[M"-M' (M M. 55 MJ
(4)
Note that unlike the forward case, Baa' + Bo' which is responsible for all the problems We always use brackets to denote and disambiguate
128
will face. Also B + B" but =+= (matrix) powers ()2 from upper indices M The anitial-action 2-step (and similarly i-step) inverse
models follow from further marginalizing a' a'a"...:
130
Bat = p(alss") [M (M*+)
Ba+'-1 p(alss") =
(5)
131
With this notation, questions (i-vi) in the introduction can formally be written as
132
(i) Can M be inferred from : M²
(ii) Can M be inferred from B and Baa" := M Mo (M+)²
133
(iii) Can Ban' ...e" == MM ...Mo' ((M+)' be inferred from B
134
(iv) Can Ban' ...e" inferred from Ba and Boa'
135
(V) Can pp+t=M=' M 3MM 2 (M++) be inferred from Bo?
137
(vi) Can Ba++:=
(M+)3 be inferred from Ba and Ba+?
138
Each question comes in two versions, given also or not knowing m. We mainly consider the former version, i.e. knowing Mº+:
Constraint on M for known क: Mg+ (als) and in particular M 1
(6)
Questions (i)-(vi) also have multiple variations:
141 ()) Assume some arbitrary B (and Beo') given, but not defined via M.
Is there exactly one, or multiple M consistent with these B? Is there an efficient algorithm that can decide the previous question?
143
144
(III) Is there an efficient algorithm that can compute any/all solutions if one/many exist, and halts/loops if not (4 non-trivial combinations of /)-
145
146
(IV) Can we efficiently determine the "number" of solutions, e.g. the dimension of the variety formed by the set of all solutions.
147
148
Formulation of the uniqueness questions. Abstractly, these questions ask whether M (in case of (i-ii)) (MM for some function (in case of (iii-v)) can be inferred from some other function f(M). Let us define another MDP q(s sa) with same policy ा (s(a) and shorthand
150
Wa = ग (als))(ss|ssa)
(In applications, Ba would be learned from data, and W or Baa'... inferred from B in the hope
151
that W M.) One way to rephrase the questions is whether f(M) (WW) implies M W or
153
g(M)= (W) for all (or most or some) M and W. The condition that x is the same for p and translates
Constraint on M and W: M = = (als) Wa and in particular M 1 = W (7)

---

155
We name the two most interesting equation versions as follows:
(i): Bao'... = M" (MM+) & w ...' e( ((wt
(8)
EqIM(i+): Bat...=
M"(M+)"'OMM
(9)
156
We allow M = and keep probabilistic convention that p(alss') = x(als)p(s) sa)sssssa///// ssa/s(ss h/sppp(((ss)))))))))((s) is undefined iff p(s'|s [s) = 0 (see end of Appendix J and Appendix O for more discussion). Formally, 10 iff M = O, also W as'
157
158
B
as' =0 iff M
ss' = O, and similarly for larger i.
3
Degenerative Cases
159
To get some feeling about why these questions are more intricate than analogous ones in for- ward models, we consider some simple examples and special cases first, with details provided in Appendix [ Some further special cases (deterministic plamning, deterministic reachability, and deterministic inverse models) are considered in Appendix There a strong relationship between the examples violating (i.iii,v) and counter-examples seemingly different conjectures found in related work. See Section C for details.
161
163
165
186 It is easy to see that c.g. M = = ( (11) ?), - (), W = W = satisty EqIM(1) but violate EqIM which means that the 1-step inverse model B does not always uniquely determine the 2-step inverse model Bas', i.e. (i.ii.v) can fail. M W trivially implies g(M) 1 =(W),, ), which means that if (i) is true, then trivially also (iiivv, and if (ii) is true, then trivially also (iv&vi). If M se' is independent a or s' or M = M.s' Ta. then Bea's a" = k- is independent M, so any W & M leads to the same B, which shows that (i) and (ii) and higher order analogues can fail. If M and W are independent s, then EIIM(I) actually implies EqIM(i)Vi. Since there are such A & W satisfying
167
168
169
170
172
EqIM(I), this constitutes another failure case of (i) and (ii). For block-diagonal M = (6 M and
174
o v all operations (+-x/8a x x/0) preserve the block structure, so the above degenerative cases can be combined, one for the upper-left block and another for the lower-right block. The most interesting special case is as follows:
W = (W
176
177
Tensor-product M and W. Let (M: Mag with (8,3) and s':= ,3) be the ten- sor product of M and M (not to be confused with the element-wise product @). Assume M = M s
178
M. where the second factor is action-independent In this case, M M ...= (M* M &.
179
and similarly if a.a',.. is replaced by +. hence A M ... @ A "ara".... ...M" (M
180
is independent of M, and similarly for W V s W. That means, EqIM(i) hold if Ma = W
182
whatever M and W are. This formalizes our motivating example that if some part of the state (š) not controlled (by a) and the dynamics factorizes (p(s'ssa) = p( ('' 55) and the policy is then the multi-step inverse models 535) become much simpler than the forward model (2). namely independent 3. This case has been studied in [EMK + 22 for episodic near- near-deterministe M.
183
184
independent 3 (T(a)s (als) =
185
186
(Nonueniqeeness of Inverse MDP Models
187
188
We will now consider EqIM(I) and EqIM(2). We first provide a dimensional analysis which gives some insight and tentative answers about the solution space for W (given B or M): No, one, finitely many, or a polynomial variety (of some dimension) of solutions. We then consider EqIM(I) only and characterize M and W for which it holds. This will be used to provide an algorithm that can p determine a (and in some sense all) solution for W and hence Bea"... given only 8 EqIM(I)
190
192
193
quite simple, since it is effectively linear, but EqIM(2) is quadratic in W. which is where the difficulties start.
184
195
Dimensional analysis/ / counting solutions. Assume 3 d and B or M are given. The kd equations EqIM(I) in W constitute (k- 1)d (linear) constraints on (the kd2 real entries in) W. It's only (k-1) 1)d2, since summing over a gives d' vacuous equations B = = There are kd further (linear) constraints Wa = Taass. Assuming no further (missed/accidental) redundancies.
196
197
198
this leads to kd 2 (k- 1)d2 kd = d(d- k) dimensional (linear) solution space for W. This is
5

---

consistent with the algorithm below inferring Bed' from B" if all B" have full rank. Hence the set of solutions for Bea forms a polynomial variety of dimension at least d(d-k)..
200
201
If also B is given, EqIM(2+) provides (k-1)d² further (quadratic) constraints (EqIM(ia) even 1)d2, this now gives an over-determined system which generally has no solution. But by assumption, M is solution, which gives hope that there may be only one or a finite number of solutions.
202
provides 11' constraints). Since d(d-k)< (1-1dd=
203
204
205
206
We can use the kd+ (k-1)) linear equations to eliminate this number of variables in W, which leaves (k- 1)d quadratic equations, now in only d(d-k) variables, and no further equality constraints. By Bézout's 's bound [FW89], such a System of Quadratic Equations (SQE), either has a continuum number of solutions (as in the counter- examlee of Appendix K) or at most 2d(d= solutions (as
208
210
possibly in the counter- counter-example in Appendix DD. Multiple discrete solutions are often caused by symmetries, for random 8 and B consistent with M, the solution may indeed be unique.
Inferring some Baa' from B Even if B does not uniquely determine Bea', we can ask for an algorithm inferring some consistent Bas' from 8". Indeed this was our primary goal before realizing that the answer is not always unique. We know that 8 = W W for some W. This implies W = 8 o W So W = - JJ for some J independent a. We need to ensure proper normalization W = [a]ss) i.e. [B @J]++ = I[als). This leads to the following algorithm to
212
214
216
produce some (and indeed all) Bea
217
Given inverse 1-step model :=y:=a((asss] and policy a(als)
218
219
For each s. choose some d- J..
satisfying the & linear equations Σ. B
220
221
Compute forward model =" 1 OJ
Compute 2-step inverse model Bas's := Wawa' (W+))
222
223
Then p(aa') |ss") = Bag is some solution.
224 If for every s, matrix x- has rank d, then Bas' is unique. The equations have no solution iff B is invalid in the sense that no underlying MDP . could have produced such B. This
only happen for k d, i.c. based on M have some intrinsic constraints beyond B = 1 for & > d. For instance BO 2 (1 () B¹ = 2 (o 1). B²= (1 is inconsistent with r(aas) = For unknown л, any J with J++ 1 will do. In general, the valid J span linear subspace, but the set of all consistent Bea' forms algebraic variety of equal or lower dimension. Has' may even be unique even if J and W are not (see Scction 3). Noting that the ranks of Mj. and W;. are the same, this gives the precise conditions under which (i) is true:
226
228
230
Proposition 1 (Conditions under which (i) is true)
M W" W implies = iff Mj. has rank 2 d for every 8.
For this to be possible at all, we need & d, i.c. more actions than states. This is typically not the most interesting regime. See Appendix for an alternative derivation of this result without an intermediary algorithm.
233
235
We will next show that EqIM(2) removes this limitation, but we do not know of general and efficient algorithm for inferring (some) Bua'a" from B and Bea', We cannot even rule out that finding approximate solutions is NP-hard.
237
238
UNonnuniqesssss of Inverse MDP Models for i> 2. Above we have established that B does not uniquely determine Bea" for the interesting regime of l <<dd d. From the dimensional analysis. providing 2 2-step inverse model gas' in addition, has the potential of uniquely determining forward model W and/or multi-step inverse models Bas's a"... We have numerically verified that this is indeed the case
240
241
242
for 8a and Bao based on random M A more detailed analysis of the línear/quadratic structure of the problem is provided in Appendix G and a rank analyses in Appendices H and R Unfortunately,
243
even providing 3 and Bea' does not always uniquely determine M nor higher B, and (ii.iv,vi) fail for some M Furthermore this remains true for higher i- i-versions, i.c. even (.IM(()...EIIMM() do
244
246 not always uniquely determine 1q). We provide (potential) counter-cxamples in Appendices]] and ] but they involve "bad" 0/0. We discuss what this means at the end of Appendix We provide

---

248
fully satisfactory counter-example in Appendix K If the solution is not unique, the set of solutions forms a polynomial variety. Its (local) dimension measures the "number" of other solutions (in neighborhood). In Appendix R we provide explicit expressions for the tangent spaces from which these dimension can efficiently be calculated.
249
250
251
Linear Relaxation
252
253
In Section we provided an algorithm if only Bd given. Here we consider the > case, and derive an algorithm for k 2 d. provided the solution is unique and further conditions on B are met. That is, we require i2 loga (d), which is greater than the minimum necessary in theory i from the dimensional analysis. E.g. for = we recover k 2 d, and 2 improves this to k 2 vd, and
254
255
258
257
i logg(d) works for all k.
258
From EqIM(1) we know that W 3y"=B"W" W+ Plugging this into (qIM(ia) and abbreviating a="==a''.... aaaaaa.... and a² := aa'..." ...a" and j:=i+1, this gives
Recursive formulation.
Ba (W+)'* (8 (b" ... " W
(10)
If we plug EqIM((i-1)) ())) into EqIM(ia) and abbreviate : (W+) - this simplifies
280
Bed @ @V.WV* = (B @V).(B* @ @W+)
261
which written out becomes
Bes Ves W s'as
Bas Vas B W gtot
(II)
282
Linear relaxation. We can consider a linear relaxation of this System of Polynomial Equations (SPE) by introducing new variables Usstas (aiming at Ussts) W. W
263
A =0 with A Betig
Bat
B gigh
(12)
These are d2 potentially independent linear equations in d unknowns U. The solution can only be unique if k³ 2 d. For random B. for each fixed (s,8)), the kt x matrix A has indeed full rank min (k' .d} 2 d, hence U. =0 is the only solution. This is inconsistent with the constraints (7). and hence shows that (unrestricted random) B do not come from some M. This makes the validity of the B's sometimes semi-decidable time (Od (d+k))) or typicalyyrandoomzzed time Odd). For the B's originating from some M, Ug (M ) MJ.,. solves (12) Since for different ss the equations in (2) are independent, U U2y+ay==00 U.s' set also solves (12) for any K. other words, the rank of A is bounded by min 1d-1), and achieved e.g. for random matrices B consistent with M. Since the solution is not unique, for many solutions there will be no W+ satisfying
285
286
268
269
270
272
Uso (W+) (W+)--lW - g not speak of M- even if the original problem 11 has unique
274
solution.
275
Unique solution by lifted constraints. So we must (and least for random M can) make the solution unique by taking into account the linear constraints (7). Applying them to s f// sa ,ar a' and multiplying from the left with Vss and using Ves Ue we lift them to
276
277
Ees = (aa+) and Us++=1 =1
(13)
These kd? +d further linear constraints have the potential to make the solution of (12 unique, i...
279
resolve the d2 degeneracy Kgg. If so, we can recover a. = W s' = Uest ee* (and finally
280
M Wa 3 à W in polynomial time. It actually suffices to solve (2) and (33) for one fixed
e.g. s= 1, which with some care can be done in time O(d)). In practice, for approximate B one
281
282
would solve least-squares problem using all equations or a random projection for speed.
Algorithm. Putting pieces together, we have the following algorithm for computing W and hence _ed for all j via EqIM(ja) from 8a and S and Be
7

---

285
Given: Policy (a s) and j- 2, inverse 1,i i 1,---,,i-- step models
Ba = ss') and Bay =ss" and B = =paaapsas
287
Do the following calculations for one 1=
or few or all or some random linear combinations of 8:
For each s², let Üz es be a solution of (12) with Us++7 =1
289
If non-zero solution does exist, set Uss's/= =0 Vss..
280
281
Optional: If multiple solutions exist, return "W may not be unique"
292 If U0++=0, return "B is not consistent with any M
293 Solve Cee
se' se =0 0 and K,+ = for K... where Cie' If no solution, return "B is not consistent with any M
6stas := :B s' -
-x(aa) (=(a(s")))
295
Optional: multiple solutions exist, return "W may not unique"
Us = U2 es ees,
:= / / ++++ Vast==U, U Upe'+>
W o == -Us Uaste /Vss
286
Optional: If different lead to different W+ or V (
297
298
return "W may not be unique"
299
Return forward model W BWW and other inverse B computed via 8
Variations that don't work. For unknown æ, we only have d lifted constraints Us++=1, which are not sufficient to make the solution unique, also resulting in too many solutions for the relinearization trick [CKPS00] to work. The same is true if we had relaxed Uss'es = ss'
301
= V If we had applied linear relaxation directly to EqIM(ia), this would have led to order-i+-1 tensors and require 4> 11////
303
which is much worse than & 2dd' / for i> 2. Including B and EqIM(ja) for some or all j j<i- not only unhelpful but even counter-productive.
304
Experiments
308
The algorithm described in Section 5 was motivated by the dimensional analysis and properties of random matrices. Namely, that A is likely "full" rank, and thus yielding a unique solution. In order to explore the plausibility of this assumption in practice, on a set of toy (but structured) environments. This includes the canonical 'four-rooms' grid-world and samples from the distribution over all grid-worlds of that size. All environments have k = (local movement on the grid) and d= 24, thus satisfying the h 2 d2 constraint which permits solving M2).
308
have evaluated the algorithm
310
312
Experiments on naturalistic environments. As detailed in Appendix P for all environments tested the algorithm yielded a unique solution (recovering Mo) up to a reasonable level of numerical precision. This remained true after injecting noise (across several orders of magnitude) into the environmental transition dynamics. This is in contrast to related methods which rely on near- deterministic environments (EMK+221
315
316
317
319
This result is -oi-trivial, as the statistics of these environments differ significantly from those produced by random matrices. For example, grid-world dynamics are both local and sparse, unlike random matrix dynamics which almost always have non-zers probability for all transitions. It remains
320
321
322
to be seen whether or not larger-scale environments yield similar results, but it is at least non-obvious what additional environmental properties would break the constraints of the algorithm.
323
324
Experiments illustrating robustness noise. The propositions (and previous experimental result)
325
assume that we know the one and two step inverse models :=1:= B" B2:= =2:=BB+) exactly, but in practice these distributions must be estimated from data. Here we investigate the extent which our algorithnn is robust to noise arising from learning.
326
327
Rather than committing to specific learning algorithm, we instead directly inject noise into the true inverse distributions. Figure 2 shows that noise doesn't 't substantially degrade performance across several orders of magnitude (see Appendix P for details). Additionally, the effect of this noise is substantially diminished as the horizon of the inverse model is increased (from B1: 8 to B3 B While the is perhaps not surprising, the entropy of such inverse distributions increases monotonically with the horizon, it still shows that noise is not compounding in a way that renders long-horize predictions meaningless.
329
331
333
8

---

335
Experiments on the Tensor-product special case. As detailed in Section 3 if M factors into two processes Ma @3 M, where M action-independen, then only the complexity of the action-dependent process M matters for all of our questions. The significance of this special case, as well as the details of environments construction, can be found Appendix P
336
338
339
The linear algorithm of Section 4 can (implicitly) output all W and B2 consistent with B1, and the formulas derived in Appendix R
340
allow (explicitly) calculate the dimensions of the solution spaces.
341
In the experiments shown in Figure 3] the environments complexity is systematically varied. The results show that the space of forward dynamies W is always larger than the space of the 2-step inverse models (B2). This confirms that inverse models can be simpler than forward models.
343
Conclusion
344
345
Summary. We have shown that the 1-step inverse model p(alss') does not uniquely determine the 2-step probabilities (alss"") if there are less actions than states (k < d). Even for 2 d, the implication can fail, e-g- if the extra actions are ineffective, but if ((s'|sa) = M considered as matrices in a and s' for each have full rank, the implication holds. Even providing p(aa'...a'"'Iss)) for all <i not necessarily determines p(a|ss") Since the involved SPE is (heavily) over-determined,
346
347
348
349
350
we expect the failure cases to be sparse/rare in some sense. For (B based on) random M, we provided evidence that a o==2 2 suffices to determine M and hence p(aa'...|sse s" from p(a] (ssss') and p(alss").
352
For low-rank M the implication may fail.
Maybe characterizing all M for which EqIM(I) and EqIM(2) uniquely determine W is hopeless, not to speak of finding some or all W in case not. More formally, we can ask the question of whether there exists an efficient algorithm that can decide whether EqIM(i) has unique solution.
Open Problems.
354
356
Conjecture 2 (NP-hardness) Deciding (ii), (iv), (vi) is NP-hard. Deciding whether B and Baa' are consistent with some M is also Na-hard. Computing some solution is FNP-hard.
358
359
In Appendix we provide some weak preliminary evidence, why this problem may be NP-hard. O contains fully self-contained a few versions of this open problem in their simplest instantiation and most elegant form.
360
Appendix
Discussion. Given our analysis, we would expect that in practice, D and Bas' determines Bua'a" a"... and W sufficiently well. Sufficiently well in case of W means all and only those aspects of the forward model relevant for the inverse model. Then of course the question remains how to compute the/an answer. While the linear relaxation developed in Section (S) fails for < d'/² as an exact method, it might still lead to useful approximate solutions [Stu02] without formal guarantees. Indeed, Eiia is heavily over-determined for i 2, and heuristic solvers often work well in this regime.
362
383
384
385
386
387
368
Handling non-uniqueness: In practice, the state space is very often infinite, and no finite amount of data will determine even 8 uniquely without further structural assumptions. Neural networks intrinsically restrict the solution space, but this may not suffice for modern over-parametrized deep networks. Aiming for the maximum-entropy distribution consistent with the (constraints from) data is popular, and could make the solution unique, as well as any other optimization constraint.
370
372

---

charac- Environment Layout
True M+
Inferred M+
True M+ (noisy)
Inferred M+ (noisy)
i
Figure 1: Environments, their transition matrices (i.e. .M) and the matrices inferred by the algorithm
(i.e. W). Results shown on the most and least noisiest variants of each environment. Top 'four- rooms' grid-world. Bottom One of the randomly generated grid-worlds,
B1
800
0.08
B2
Manifold Dimension
B3
600
Average KL
0.06
0.04
400
0.02
200
0.00
-6
-2
5
10
15
20
25
30
Noise Exponent
of states in M
Figure 2: Noise-induced reconstruction error:
Figure 3: Solution dimensions of W and B2 given B1: When the solution to an inverse model (B2) given only B1 is not unique, terize the solution space in terms its manifold dimension. By comparing this to the dimension of that of inferred forward model (W), we can that our algorithm has narrowed down the space of inverse models further. also given, the solution dimension of W reduces from dw (blue curve) to dw- -dy (blue minus orange curve).
In practice W must be inferred from learned es- timates of B1 and B2. We investigate the ef- feet of the resulting eиrоr on the inverse models (B1,B2,B3) recovered from the inferred W in terms their proximity to the ground truth distri- butions. At each noise level the algorithm was run on 10 randomly generated grids, with shaded region representing 1:2g.
10

---

References
373
374
[AD21]
Saurabh Arora and Prashant Doshi. A survey of inverse reinforcement learning: Chal- lenges, methods and progress. Artificial Intelligence, 197:103500, August 2021.
[BEP*
Yuri Burda, Harri Edwards, Deepak Pathak, Amos Storkey, Trevor Darrell, and Alexei A Efros. Large-scale study of curiosity-driven learning. arXiv preprint arXiv:1808.04. 04355, 2018.
377
[BPK 20]
Adrià Puigdomènech Badia, Bilal Piot, Steven Kapturowski, Pablo Sprechmann, Alex Vitvitskyi, Zhaohan Daniel Guo, and Charles Blundell. Agent57: Outperforming the atari human benchmark. In International Conference Machine Learning, pages 507-517. PMLR, 2020.
380
382
383
[CKPS00]
Nicolas Courtois, Alexander Klimov, Jacques Patarin, and Adi Shamir. Efficient Al- gorithms for Solving Overdefined Systems of Multivariate Polynomial Equations. In Gerhard Goos, Juris Hartmanis, Jan van Leeuwen, and Bart Preneel, editors, Advances in Cryptology EUROCRYPT 2000, volume 1807, pages 392 407. Springer Berlin Heidelberg, Berlin, Heidelberg. 2000.
385
387
388
[DY79]
E. B. Dynkin and A. A. Yushkevich. Controlled Markov processes. Number 235 in Grundlehren der mathematischen Wissenschaften. Springer- Verlag, Berlin New York, 1979.
390
391
[EGIL18]
Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity is all you need: Learning skills without reward function. arXiv preprint arXiv:1802.06077, 2018.
393
394
[EMK 22]
Yonathan Efroni, Dipendra Misra, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Provable RL with Exogenous Distractors via Multistep Inverse Dynamics. arXiv:2 10.08847 [cs], March 2022.
396
397
[FW89]
William Fulton and Richard Weiss. Algebraic Curves: An Introduction to Algebraic Geometry. MadisonnWesleyy 1989.
399
[GRW17]
Karol Gregor, Danilo Jimenez Rezende, and Daan Wierstra. Variational Intrinsic Control. In Workshop, February 2017.
400
401
[HDB+21]
Steven Stenberg Hansen, Guillaume Desjardins, Kate Baumli, David Warde-Farley, Nicolas Heess, Simon Osindero, and Volodymyr Mnih. Entropic Desired Dynamics for Intrinsic Control. In Advances in Neural Information Processing Systems, May 2021.
402
403
404
[HL13]
Christopher J. Hillar and Lek-Heng Lim. Most Tensor Problems Are NP-Hard. Journal of the ACM. 60(6):1-39, November 2013.
405
406
[HSHB99]
Jesse Hoey, Robert St-Aubin, Alan Hu, and Craig Boutilier. SPUDD: Stochastic planning using decision diagrams. In Proceedings of the Fifteenth Conference on Uncertainty Artificial Intelligence, pages 279-288, 1999.
407
408
409
[KF09]
Daphne Koller and Nir Friedman. Probabilistic Graphical Models: Principles and Techniques. Adaptive Computation and Machine Learning. MIT Press, Cambridge, MA, 2009.
411
412
[LFLDP21] Bonnie Li, Vincent François-Lavet, Thang Doan, and Joelle Pineau. Domain adversarial reinforcement learning. arXiv preprint arXiv:2102.0709) 2021.
[MHKL20]
Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. Kinematic state abstraction and provably efficient rich-observation reinforcement learning. In International conference machine learning, pages 6961-6971. PMLR, 2020.
415
[MJR15]
Shakir Mohamed and Danilo Jimenez Rezende. Variational information maximisation for intrinsically motivated reinforcement learning. Advances in neural information processing systems, 28, 2015.
418
[OKD 1OKD+21] Pedro A. Ortega, Markus Kunesch, Grégoire Delétang, Tim Genewein, Jordi Grau- Moya, Joel Veness, Jonas Buchli, Jonas Degrave, Bilal Piot, Julien Perolat, Tom Everitt, Corentin Tallee, Emilio Parisotto, Tom Erez, Yutian Chen, Scott Reed, Marcus Hutter, Nando de Freitas, and Shane Legg. Shaking the foundations: Delusions in sequence models for interaction and control. arXiv:2110.10819 [cs], October 2021.
421
423
11

---

425
[PGJ16]
Judea Pearl, Madelyn Glymour. and Nicholas P. Jewell. Causal Inference in Statistics:
426
A Primer. Wiley, Chichester, West Sussex, 2016.
427
[Pre00]
Doina Precup. Temporal Abstraction in Reinforcement Learning, 2000.
428
[SGL* 1GGL+10 19]
Archit Sharma, Shixiang Gu, Sergey Levine. Vikash Kumar, and Karol Hausman. Dynamics-Aware Unsupervised Discovery of Skills. In International Conference on Learning Representations, September 2019.
429
430
431
[SP02]
Martin Stolle and Doina Precup. Learning Options in Reinforcement Learning, In Sven Koenig and Robert C. Holte, editors, Abstraction, Reformalation, and Approximation, Lecture Notes in Computer Science, pages 212-223, Berlin, Heidelberg, 2002. Springer. Bernd Sturmfels. Solving Systems of Polynomial Equations. Number 97 in Regional Conference Series in Mathematics. American Mathematical Society, Providence, RI, 2002.
432
433
434
[Stu02]
435
436
437
[WDG+16 16)
Grady Williams, Paul Drews, Brian Goldfain, James M Rehg, and Evangelos A Theodorou. Aggressive driving with model predictive path integral control. In 2016 IEEE International Conference on Robotics and Automation (ICRA), pages 1433-1440. IEEE, 2016.
438
439
Checklist
442
1. For all authors...
443
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
444
contributions and scope? [Yes]
445
(b) Did you describe the limitations of your work? [Yes]
446
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
447
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
448
449
2. If you are including theoretical results...
450
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
451
(b) Did you include complete proofs of all theoretical results? [Yes]
452
3. If you experiments..
459
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [No]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
456
457
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
458
459
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
461
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
463
(b) Did you mention the license of the assets? [N/A]
484
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
465
466
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
467
468
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
470
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
472
473
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
474
475
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
12

---

Inverse MDP Models
Supplementary Material
477
478
A
List of Notation
Symbol
Type
Explanation
undefined
[bool]
E {
=1 if bool=True, =0 if bool=False
das'
s=
Kronecker delta
EN
number of states number of actions time index/step Set of integers from to j (empty if <))
EN
ij
EN
(i:A}
CZ
8,8
E (1:d}
state at time step 1,2
a.
E 10:k 10:
action at time step 1,2.....
b,6
alternative action time step 1,2,...,
a
aa'
sequence of actions
= aa'....
sequence of i- actions
3,8
{(1:d}
parts of state, usually s= ($,8)
>0
small number >0
p(...)
E 00:1]
(conditional) probability distribution over states and actions policy. Probability of action in state
(aas))
E [0;1]
M",W"
e [0:1]xxd
cransition-poliqy tensor M p(s' sa) (a)as)) similarly W =y inverse 1-step model 8 =
Ba
E [0:1]<xc dxd
p(alss)) ) for each action a
Bat+
e [:1]
3-step first-action inverse model p(alss"") action-indepenn inteeedendeennennttt d "transition" matrices
egm
J.K.A
dadd
index summation, e.g. M E.. M
matrix multiplication: [Aβ]] SS -
E.. Aad Ay
element-wise multiplication of matrix elements: [A@B] B) Ags Bas
0
element-wise division of matrix elements: [A@ B ass' = - Bay
8
(+)
tensor product:
[M @ Mas'' == Ma Ma with = (8,8) and 5 =5'
B Application to Planning
479
480
In Section I various streams of applied work were highlighted; here we focus spelling out the overarching impact that compositional inverse models (an affirmative answer question (iv)) would have for planning problems.
481
482
Many forms of planning involve the evaluation of candidate i-step action sequences (e.g. model predictive path integral control [WDG+ 16)). Ideally, all possible action sequences would be evaluated, but the space of i-step action sequences grows exponentially in i, this is often intractable.
484
486
Access to the i-step inverse distribution p(a...a"|s....'" allows determining the subset of action sequences that likely reach state si+1 post-execution (e.g. those whose probability is above some threshold). It is often the case that only action sequences that are distinguished in this way are of interest (e.g. geal-reach tasks), thus access to an inverse model of the appropriate horizon allows for filtering candidates. This filtering method particularly appealing approach when the cost/reward function is initially unknown and frequently changes, as in [MRR5]]
487
488
489
490
492
Motivating Example. Consider agent who has control over but over For instance robot
493
equipped with a camera can control its position and orientation, but not the shape and color of objects its path. The forward model ((s'(as) essentially involves modelling the whole observable world. The inverse model p(a) (ssss)) on the other hand can ignore inputs that the agent has no control over. Of course in practice, does come neatly separated into & and 5, (say) deep neural network still
494
485
436
437
has to learn the controllable features, but neither needs to learn nor predict the uncontrollable features (under the factorization assumptions described in Section now in feature space).
499
the goal is to navigate from 5 to s in i time steps, and open-loop control suffices as e.g. in determinitiiiiiititc problems [MK +22 then action sequences for which p(aa'... "..a'''|ss" is large
13

---

501
are the most likely that caused the transition to s', hence these sequences are promising candidates for macro actions (temporally extended actions, options) in Reinforcement Learning [SP02] Pre00).
502
503
Since the action space is typically much smaller than the state space (the former often finite, the latter often even dimeniioddmms,,,nall),, even learning p(aa'...a* s'..s') directly for all small can be feasible and may be more data cuta-efficient than learning the one-step forward model. A closed-loop alternative would be to learn only p(a|s...s') ) find the likely first action that caused the ultimate transition to s", then take action a, iterate, and store the resulting sequence as an option.
505
507
508
The required sample complexity to learn inverse MDP models for larger i directly from data may grow exponentially in i, which why inferring i-step inverse models from 1-step and 2-step inverse models would be useful. The fact that this problem borders NP-hardness probably prevents even powerful transformer models to finding the structure in p(aa'.... .i'aa'aaa"'lll
509
510
"iaa.."""(ss...s") "|s...s") by themselves.
511
C Counter-Examples in Related Work
512
513 In Section 3 we presented a counter examme to questions (i,iii.)) Question (i) (i.e. Can M be inferred from B = M @ ?) has been implicitly addressed in previous work. In [EMK Ap3.A.3] the authors present a counter-example to the claim that a state representation constructed via an inverse model (i.e. two states have the same representation iff they yield the same inverse distribution for all of their possible successor states) is sufficient for representing a set of policies that differentially visit all states. This fails whenever two states are aliased by the inverse model. Technically, as per their Definition 2. this 'policy cover' need only account for all 'endogenous' states. But omit the "exogenous' states from their counter-example and it can be seen to address our question 521 (i).
515
517
519
522
Note that this failure of state representation learning implies a negative answer to our question (). as W would differ from M on these aliased states. Unlike our counter-example, theirs involves deterministic forward dynamics, and therefor buttresses our claims by showing that M cannot always be inferred even in this simpler case. Similar our counter-example in Section 3 [MHKL2) 20
523
524
525
526
proposes a stochastic counter-example to inverse modeling for state representation learning.
527
In general, the transferability of these counter-examples suggests strong relationship between the literature on using single-step inverse models for state representation learning and using them for inferring the forward model. It is an interesting open question whether or not algorithms for representation learning on the basis of multi-step inverse models (like those put forward in EMK +2) might be used to shed light on the questions put forward here and vice versa.
528
529
530
531
D Degenerative Cases Details
533
To get some feeling about why these questions are so more intricate than analogous ones in forward models, we consider some simple examples and special cases first. Some further special cases (deterministic planning, deterministic reachability, and deterministic inverse models) are considered
534
535
536
in Appendix E
537
Example violating vi. A specific example for M and W which satisfy EqIM(1) but violate E2))(2+) and hence EqIM(2a) is as follows:
538
M = (( 3) M' M'= =0= 31
which satisfies 7 (M = = In this example, 2+= and -+= 1) which shows
539
540
2 M
except that 22 = 0 -M,, hence there is one "dubious" 1-0/0 case. simple calculation shows that EqIM(2+) violated (w/o any division by 0). The division by can
541
casily avoided by mixing U = into M and W. e.g. M~ (M +U) and W (W+U) This
542
543
means that the 1-step inverse model B does not always uniquely determine the 2-step inverse model
Bea' i.e. vi can fail.
545
M W. This trivially implics (.AM)=g(WW) This means if (i) is true, then trivially also (iii) and (v), and if (ii) is true, then trivially also (iv) and (vi).
=
14

---

547 M and W are independent a. Note that = independent a implies M independent
a, hence <(als)= M2+ = 1/k independent a as well, hence M = Y/2 Mr The latter implies
548
M ...M" @(*+)* - is independent M hence is the same as for W. Since we can choose
550
M + W, this shows that (i) and (ii) and higher order analogues fail for these degenerate M and W.
551
M and W are nearly independent a. The above degeneracy generalizes to M = Ma To and W W. as Ta i.c. action-inde eetionnindependennt dynamies, and cate-inddeendent actions, which in turn is special case of the tensor product below (with s =3 3 and 5 0).
552
553
M and W are independent s'. In this case, M Ma+ = (a]s) = = hence is a special case of case M = W above.
655
M and W are independent s. In this case, [M'M"1 Jas" leg"=En E. Mi, T()+) Also the policy π (a|s)) (06))MM3) Mg+ is independent s. If we assume EqIM(I), this implics
557
T(a
T(alx) [+++*
M (M
[WOW*' O(W+)
M
hence EqIM(2) holds and similarly (qIM As an example, consider
M = 1)11 M = -0 W = 1 1 =
559
These M + W satisfy EqIM(1) (M*2M++ = 2M = - case of (i) and (ii).
Wt,, hence constitute another failure
560
Block-diagonal M and W. For ( the block structure, so the above degenerative cases can be combined, one for the upper-left block and another for the lower-right block.
(M 0 and W = ( ) all operations (+- x x/0x)//0))))))) preserve M)
561
562
563
584
Tensor-product M and W. Let
Mag with s: (5,3) and (s' ,3) be the ten-
sor product of M and M (not to be confused with the element-wise product @). Assume M = Ma R
565
(MM.... and similarly if a.a',.. ..... is replaced by +. hence M M ...M" @M M Mi"'....MM (M*) is independent of M, and similarly for W W s W. That means, EqIM(i) hold if Ma= = Wo, whatever M and W are. This formalizes our motivating example that if some part of the state (š) not controlled (by a) and the dynamics factorizes (p(s' (p(s'[sa) = ((5''ša)pi (3))p())))) and the policy is independent& 3 (x = then the multi-step inverse models 5 become much simpler than the forward model (2). namely independent 3. This case has been studied in [EMK + 22 for episodic near-deterministic M.
M, where the second factor is aetion-independent. In this case, M M = -M*"
566
567
568
589
570
571
572
573
574
E
Deterministic Cases
575
Deterministic planning/ / reachability problem. If we are only interested in finding some action sequence aa' ..." that leads to s", the problem becomes easy: The only thing that matters is the support of the various matrices, not the numerical values themselves. Since Ba > 0 iff M > 0 (either assuming + >0 or regarding 1>> 0 as False), and similarly for higher orders, we can replace
576
577
578
Ms by 8 in (iii,, and get Bea' ',,a" > 0 iff [B*D** "B"""1ss" > 0. We could also replace M by G - S5' > 0]. then [G" ...Gaa) ]axt+1 > 0 counts the number of paths of length from s to s++1 via action sequence aa' ...a'. and hence determines whether s s++1 can be reached. Similarly (G+) iff there is some action sequence that can reach s1+1 from s. An action a such that Go (G+ ) > can be chosen as the first action of such a sequence if it exists, and a' "a"... can be found the same way by recursion. So this deterministic plamning/reachabillty problem has a "unique" solution, which can be found in time (i-d-(ddkk) (d+ (for fixed s and s s1+1).
580
581
582
583
584
585
as' B is deterministic. Assume Mg /M =: Bg E (0,1,L)) This is true if and only if M has
586
587
disjoint support for different a, i.c iff M O0 Fb This in turn means that B - // > 0] Va b, which is another failure case of (i). Here we have included the case where action leads from to s' in which
588
for any and only those W with same support as M, and hence also W WoOW*
15

---

case W = - and B" is undefined (1). This readily extends to higher orders: If Baa'... E {0.1,1}.
590
then Baa'... "WN""e---WW"" (W++>>0) 0] iff W"W""... has the same support as M M and
391
W www" ... wa ow"w" ...''' =0 Vaa'... "bb'...'
(14)
Note that Wa F W 0 does not necessarily imply 14 e.g. for W - and W
2 (1
592
= In Appendices I & we construct W such that 14 holds for larger i.
583
F
Characterizing M and W for which E1 holds
O W
===M"0J with J: O*
595
That is, J is independent of a. Phrased differently
For any M and W. EqIM(I) is satisfied iff W MM is independent
(15)
596
For a given M, this allows to determine all W consistent with EgIM(1). by just multiplying with any 587 a-independent J 222 Not all though lead to W consistent with 7 In order also satisfy 7
598
needs to be restricted as follows: With Ass' == Jae' - 1, 7 becomes
0 - W W
Em Ma (A M
Mg. Dae'
(16)
589
For each fixed these are k homogenous linear equations (one for each a) in d variables. Given M, all and only the W consistent with EqIM(1) and (7) can be obtained via W M (1++A) with A satisfying M; A.. =.
600
As special case, A 0 necessarily if and only if the rank of Mg. is 2 d for every s. This gives the precise conditions as stated in Proposition Junder which (i) is true. We will next show that EqlM(2) removes this limitation.
603
G Characterizing M and W for which EqIM(1) and EqIM(2+) hold
From Appendix F we know that the most general Ansatz for W satisfying EqIM(I) M*+
607
Plugging this into 28 and expanding in A, we get
M (MPM
+ M
+ M
(A)
608
This is collection of quadratic equations in A. The A-independent first line is 0. We can write this in canonical form:
ERA N Au = (A) with
(17)
A = (Ev Ma. M ) M M M Mt. MM 61g M M.Mtt.da
Rº = (M*OA)(M ( M OM
Let us consider A as dl x d2 matrix for each a, A as a vector of length d2, and (wrongly) presume R =0 first. A is sum of 4 terms. The second and fourth terms are block-diagonal matrices (d blocks of size d x d in the diagonal) due to the dsk- The first and third terms are scrambled block-diagonal matrices due to the ō1g", or more precisely, consist of d d blocks, each bock being a dx d diagonal matrix. If Md has full rank, each of the four terms has full rank d², but A itself
610
612
613
614
615
can have lower rank, O-eigenvalues due some cancellations. Random M apparently achieves the highest rank, but even then, A itself has only rank d(d-1).
616
Actually, A A 0 is required to hold for all a, the rank of A as kel x dd matrix may still be de But A =0 for & ==2 implics - hence the rank is still at most ((d-1). l b>> 2 may rectify this, but there is an alternative, which works for all a: A also needs to satisfy (16), which can be
618
16

---

620
rewritten as
E =0 with C², = 02 Ad
(18)
621
These give another kd constraints, and apparently often d new ones from random M. If we combine A' = ( this implies that A' has often rank d,, A'A =0 can only be satisfied for A -. For k- - 2, A+ = 0, so inclusion of either A or A in A' would suffice, but Co and C* are potentially independent, so both have to be included.
622
623
624
Let us now return to the real case of R 0 for full random M, hence full-rank A'. With = we need to solve ='A Note that R' = =R is not a constant, but a (homogenous) quadratic function of A itself. Consider any A = (E), then A'A ((s) while RA(A) = which is contradiction for sufficiently small ε (this argument can be made rigorous). This implies that no A with 0 < ||| <E can satisfy A'A = RR ). In conclusion,
626
628
630
Proposition 3 (Random M and full-rank A')
631
If A' has full rank and W is close to M, then E) and EqIM(2) imply W= = M. Empirically A' has full rank for random M.
632
633
This of course implies (ilM and also (iv). Globally, i.e. if W is not close to M, these implica- tions may not hold.
634
We have yet establish sufficient conditions which M lead to full-rank A'. Empirically, this has been true for random M so should hold almost surely if M are sampled uniformly. One might conjecture that full-rank M are sufficient, but this is not the case. For instance, if M is independent a, then A' = O.
636
638
Zero A and R for full-rank Ma. We finally we note that A and R can have low rank, indeed A=
629
0= R even for a-dependent full-rank M Consider the example M from (22) or its generalization
640
641
27:: : First, if for two matrices M and Ma only one s' (depending on and s") contributes to
the sum in M M then (M*)J)(ME oJ))= M M
G.KK K for some K. This makes (99) valid for
M":= M1 and M for any J. since for oa' * 6b' both sides are O by construction of 1/
643
644
(the K does nothing it), and are trivially equal for aa' = -b'. By summing over a'bb', also (28) is
645
valid for any J. hence of course also for J 1 + A for any A. Since (17) is equivalent to (28). (17)
648
holds for any A. This can only be true for A =0 and R= 0. This degeneracy in itself does not violate
647
(ii), since the probability constraints require W = M, as established earlier.
H EQLMC)AAEQM(()))444MMMM
for full low rank M?
648
The following numerical approach may lead to counter-examples with full support to (v) without any divisions by (M++ > 0 and W >0 Vss'). We now consider full M but of rank r << d. The most interesting case is where all M span the same row-space, i.e. L== where L are
650
dx matrices and R is a x matrix. Recall :':= (A) with A and C defined in (17) and (T8) Empirically, for 2= the rank of A' typically is min (d (...((3rr)))) - 1)d--(r--1)))) 1)), never more, and only in degenerate cases less. Hence for r 22, A' is singular for d 5. Hence for d2 5, there exist A + with A' A 00
653
655
656
For A = A -= O(E), this is an approximate O(s?) solution of A'A = R')A). By iterating A + Ao + A (A)),, where A is the pseudo-inverse of A', we get an ( aaprrooapoiinnao after i 2 iterations. This should rapidly converge an "exact" non-zero(!) solution A'A (A) This would
657
658
659
show that (ii) can fail for full M. Generically, this solution also violates HqIM(3), i.e. also (vi) can fail. By this mean, for randomly sampled I." and R (for a r=r=2 and d 5) and performing the procedure above, E3IM(3) does not hold. There is a caveat with this argument, namely if R' is not in
660
661
662
the range of A', then this construction fails.
I EqIM(1) does not imply EqIM(2) (O-version)
663
664
We have already given a simple example that violates (v) in Section but the example and method- ology provided here generalizes to (vi) and even larger i. We consider deterministic reversible
17

---

688
forward dynamics for any policy T(a]s) > O Vas. For simplicity we assume k: 2 and uniform policy ([als)= 2. We defer discussion of 0/0 to the end of the next Appendix.
687
We consider R and Wo that permute states. That is, M == (5)] and =s':======0 o= [s)] for some permutations л. "i. (1,....d)) - (1.....d}. Strictly speaking, we should multiply this by [{a|8)= = k. but this global factor plays no role here, so will be dropped everywhere. Matrix
668
669
670
multiplication corresponds to permutation composition: [M W' = [s" oo (I (s)]. We denote
671
example permutation (matrices) by [T)).
672
We now construct counter-example for (v): For d let M - Id= [234] be the identity matrix/permutation. Let - [2341] be the cyclic permutation 1 and M - the cycle pair 1 <-> 2 and 3 4. We know from (15) that (1I holds isf W* is independent a J) isf W M W 2 M Va,b [0,1] iff W =M
674
676
Case a= b is trivial, so only T ④ 3 & needs to be verified. Now M @W of two permutations matrices not a permutation matrix (unless M = W:) It still a 0-1 matrix with at most one non-zero entry in each row and column. We can generalize the permutation notation to "sub-permutations" by defining r($)= if row s is empty. For instance @ [2046]. EqIM(1) holds, since
678
679
680
681
W @M' = [0000]= = M oW!
Similarly (2)) holds iff WaW'' MM is independent a.a' iff
682
W MM = Md ow Va,a b.,.'.
(19)
683
But for =0 and b=b'=1 1 we have
(M)) [1234] o [2334] [1234] * [0000] [1234] o [3412] o
684
hence E1I does not necessarily imply EqIM(2). The advantage of formulation 19 over (8) is
605
that matrix sums M and W+ are more complicated objects than the uub-permutation matrices (19).
686
Like random matrices, permutation matrices, have full rank, but unlike random matrices they can
687
violate (ii), (iv), and (vi).
J (...aaaa)....MMMM do not imply EqIM(i+I) 1) (O (O-version)
Counting variables and equations made the possibility of violating (v) for is < d plausible (cf. positive result for k2d), A similar counting argument indicates that (vi) and higher i analogues might actually hold. Unfortunately this is not the case. Le. even providing inverse models for all action sequences up to length is not sufficient to always uniquely determine the probability of longer action sequences. This is true even for deterministic reversible forward dynamics for any policy π Talss) >>> 0 Yas. As for 2- gloss over 0/0, and don't 't normalize M and W.
890
692
694 i i= 1, we assume a: 2, x (a]s)= = 1
For i 2, M":= : [134456] and = [23:566361]= (a for 'cycle") ) and M [231564]= can be shown to satisfy EqIM(l) and EqIM(2a) but violate EqIM(3). The calculations are not to onerous, but lets consider directly the general i case: Consider even 2d: and identity and cycle (pair)
696
698
M 0 Id [1,2,...,d dd,,.,,,,,,,,,,,, 1,d],
I [2,3 ,,,1] d,1], M = [2,,,..,,d' dl 22...d-,,dddddd +1]
EqIM(ia) holds if WoWo' ... @ -.- 0M M ... is independent an' iff
689
WWWo' "ewp"'..wa'.. @ MD M = M Maa @W* ..o. Vaa'...' ...'..
(20)
(While this looks like 2 matrix equations, by chaining, checking ks pairs suffices, which is the same number as in EqIM(ia)). Now W" ...Wa' consists of only two types of matrices, a
700
701
cycle for W1 = a and identity Wo, The / = can be climinated, leading to (W2)e*, where at:=a+a' +a', Similarly MMM ...Mo'' =(M+))t etc. Hence we only need to verify
702
703
(W+)a** @(M2)tt ( ( for 0 b si
(21)
18

---

704
(Wlya* = Ia +l,a + 2,..,,, while
(M = 1bt +1, +I.....d .I....,b bb. d' +1+b- "t..b......dd" + +I....,d' d'....,''b +b*
hence (o (M
-- = [00...0] =0 for Osa *b+ <d'. For at =b+ both sides of (21) are equal
705
706 too. Hence if we choose d' = (2T) and hence (qq(()) are all satisfied. If we choose
707
d' d'=i,a a d', b+ 0. (1 reduces to
(W (M [d' +1,...dd,111111 Old = 0, and
(M (W = Idold =
which are of course not equal. Hence EqIM(i) fails for d' = Summing over all a'...a" and b'..b"" and noting that other terms are 0 or cancel, shows that EqIM(i+) fails too. Together this shows for d' =i+1 that (qIMM()...FqlMii)
709
710
do not imply any version of EqIM(i+1).
Despite M having full rank, A and A' defined in Appendix G have very low rank, indicating potentially many more consistent W.
712
713
A downside of this example is that it strictly only applies to the O-version (0 Many entries of M and W+ and powers thereof are 0, so contains many divisions by zero. We were not able to
714
715
extend this example by mixing in e.g. uniform matrix done in the first counter-example to (v).
Many real-worke MDPs are sparse. Only subset SCSx S of transitions s' is possible. For (s,s') & G. p(s' =(s= Va, or formally M = M =0. In this case, no action causes ->s' and p(a]ss') s = / au' being undefined is actually appropriate. So we could restrict (s,s²) G (and analogously (s.....s") and (ss*) by chaining G) in the conditions and conclusions of the various conjectures. It then also natural to restrict the model class to M:= {M :M as > + (s,5))
717
718
719
720
For unknown G, the condition M.W EM then becomes M >
W > O. Unfortunately
722
the above counter-example does not even satisfy this weaker condition, but the more complicated example of Appendix K does. See Appendix for how to treat 0/0 in practice.
723
K Non-Uniqueness of Inverse MDP Models for i i22
724
725
In Appendices D
we provided comjecuured/ussaiisfacttoy counter-examples to EqIM(1:i) -qIM(i- 1). Here we provide a fully satisfactory counter-example that avoids the "bad" 0/0.
726
EqIM(1) and (2)) do not imply EqIM(3). Consider two matrices M/ and A with disjoint support, i.e. M7 Mr1 00, In this case M M+ E (0.1, 1.pxd is a partial binary matrix with entry undefined (1) wherever + but otherwise O wherever 2 =0 and wherever M 0.
727
728
That is, it is insensitive to the actual (non-zero) values of M A simple such M is A ( and
730
M = (1 1), ignoring normalization. For now we ignore ss' for which Mr = 0 and return to this issue later.
732
733
We consider A and p that permute states. That is, [='== (s)] and W == [s)] for some permutations
o {l.....d} + f. but this global factor plays no role here, so will be dropped everywhere. Matrix multiplication corresponds to permutation composition: Wo = =0 (i (s)]. We denote
[}. Strictly speaking, should multiply this by
e.g. ([ass)= = 1.
735
737
example permutation (matrices) by [ = [T(1) (d)). Consider now
A A [123456]
o = [456123] =: [=o]
M A [564312]
(22)
A = [231645] =: [=]]
M A = [645231]
M Ar' = [312564]
No column contains the same number twice, hence this not only satisfies A =0 but also
738
M Mra AM unless a a= and a' =6
(23)
19

---

That --55-4--6 is in reverse oder to 1-22-3--3222 is crucial for making M and M' not commute.
739
740
Note that (23) remains valid if each 1-entry of M is replaced by a different non-zero scalar, since
23 is purely multiplicative. So if = -M* for some J >> O, then Wa _M M K for some K K>0, 0. Let W be such a matrix. Then [W'W** @ WW+W+1 by+W++ls** = if [M M jas" > 0 and 0 (or undefined) otherwise, i.e. is independent of the choice of J. So such W + M satisfies Eql
741
743
Unfortunately the probability constraints W =1 require J =1 when M >> 0, and hence W M.
744
745
But the general idea is sound and can be made work as follows:
746
We split one state, e.g. ==6 into two states 8 8= 6a and s= -b. We leave the permutation structure intact, except that all deterministic transitions into 8 = 6 are split into stochastic transitions to 8 == 6a
747
748
and = 6b, and transitions from 6a and 6b will be to the same state as from original 6. Condition (23
749
still satisfied, so the above argument still goes through, but now we can choose different stochastic transitions to s = 6a and s 6b in W and M.
750
Finally, we have show violation of EqIM(3). EqIM(ia) holds iff WaW'' ... ..OM.MM'....
751
752
M M ... independent aa'... iff
W .'''' MM ...M'' = M ...M' "oww"" ....w Yaa'... ....a',bb'.. add,bb'... .bb....'
(24)
(While this looks like k-2t matrix equations, by chaining, checking kt pairs suffices, which is the same number of equations as FilM(ia)).
754
755
is easier to split every state into two states: 8: (8,8) with á & 66) as before and splitter E [0,1]. M == M Note that M is flexible enough to expand each I-entry in M to a
796
different 2 x (stochastic) matrix, while the O-entries become (a 0)- This flexibility is important: M independent a or independent á would not work. Now let us write out
757
758
M M" 11s""
Σ 3180
Mrg" Mg go giggn
Mgg Nigh 3'30
(25)
759
The crucial difference to the i= 2 case 23 is that now there are difference permutation sequences leading to the same permutation, for instance N70 1/1 = M
~ Mo Let us choose contribute to the sum and 8 = Tı (*")= ) = 2. For this choice, (25) becomes 1-1-1. 1/04 1/ sg we replace aa' a" in 25 by bb'b" and then choose 10'0=110 and again é $=1, then only 8'= ( and s" =8))
760
ao' a" = 001 and å = 1, then only 8' =o = 4 and === mp
762
contribute and 8" = (o(3") 2. For this choice, 25 becomes 1-1-1 [- 17 M We now
define W == Mo
Way. Since M remains the same, the same action and state sequences above
785
ss. ss'
lead to the same result for W, just with M replaced by W. If we plug the four expressions into (24
786
(for 3) we get
W o A7" 1/ 07 o 1704 M ow 11
788
Since this expressions involves 10 different 2x2 stochastic matrices, there are plenty of choices to make both sides different. If we choose all 2 matrices to have full support, then by construction, W and M have the same support, hence constitute a proper counter-example to EqIM(3). We now extend this construction to i>>
770
do not imply EqIM(i+ The construction in the previous para- graph generalizes to i <>> We need to find two permutations - and - such that for each fixed j S all possible 2 concatenations (products) of these permutation (matrices) differ in the sense
EgIM(1a)A...A
774
that no is mapped to the same s³ (they have disjoint support). Since all A' j'r"' ...'aa''' (0,,1), we
775
776
can write this condition compactly as
Σ Ma ...'a' (0, ou'
By factoring the sum, this is equivalent to (M/+ E [0,1]dxd, Note that [(*+)] ess counts the number of action sequences oa' ......'' of length that lead from to s For j= 1, want this condition to be violated. So in order to disprove the implication we need to find two permutations
777
778
779
M and M such that
780
eityye(0.100 Visi but (Art)++ & (0.1)
(26)
20

---

781
The rest of the argument is the same as for the i=2 case above: creating two versions M and W of M by spitting one or all states into two, and replacing the Is by 2x2 different stochastic matrices. choose 3-cycle and 5-cycle
782
783 As for the choice of M for 3
Mr" (6.7330000111221111111122333
(27)
M = [25445.199106671115511....
= (1,23445((4510077X11144111
784
where we also provide the more conventional cycle notation in round brackets. Crucially the S-cycles have been chosen to not commute with the 3-cycles (M" 4 M+). Conditions (26) can easily be verified numerically. For higher i we need p cycles and cycles, where and q are relative
785
786
prime and sufficiently large. We need at least p p-q 2 otherwise M & {0,1)axd by a simple
787
788
pigeon-hole argument. To prove SqlM(1a)A...r E.qI (i) & EqIM(i+1) in general for arbitrarily
789
large we need to invoke some group theory. All-together we have shown that
790
(A..A do not necessarily imply EqIM(i+ for any i. This in turn implies that (i)-(vi) each can fail for some M'.
Proposition 4 ((i-(vi) can fail) EqIM(1a) (.MMM..)....A..... A...
792
L
Computational Complexity
783
Maybe even just characterizing all M for which EqIM(I) and EqIM(2) uniquely determine W is hopeless, not to speak of finding some or all W in case not. More formally, we can ask the question of whether there exists efficient algorithm that can decide whether EqIM(1) has unique solution. We provide some weak preliminary evidence, why this problem may be NP-hard. Appendix contains fully self-contained a few versions of this open problem in their simplest instantiation and most elegant form.
794
785
796
797
798
799
Decidability and computability. EQIM(2) converted to (24) and or (28) or 29 below form a
System of Quadratic Equations (SQE). The constraint W + M can also be expressed as quadratic equation (see below). As such, the existence and uniqueness of solutions is formally decidable by computing a Gröbner basis [Stu02), and (some) solutions can be found by cylindrical algebraic decomposition in (double) exponential time, s-approximate solutions can of course be found by exponential brute-force search through all W on finite e'-grid, and verified in polynomial time.
801
803
Complexity considerations. 3SAT is NP complete. A CNF formula in n boolean variables can easily be converted to System of Quadratic Equations (SQE). Therefore SQE also NP hard. EqIM(2+) explicitly written in quadratic form
806
807
M+ (ew+j==ww-to@ee
=0
(28)
808
constitutes an SQE in W given M, also if we include linear EqIM(1) and probability constraints
7) Non-negativity of W can be enforced with (slack) variables (Y2.)² = W (Similarly (17)
809
810
plus constraints (T6) constitute an SQE in A.) To reduce the uniqueness question to a solvability problem we need to avoid the trivial solution W = M, e.g. by introducing further (slack) variables
E and r == (W .s' Mg./> )2 and constraint t- r = 1. Due the minus sign in (28), this cannor be converted to convex (optimization) problem. The choice of M gives significant freedom in creating SQE problems, even only considering permutation matrices M E {0.1)dddd If one could show that every SQE can be represented as (28) [plus W a M constraint] for a suitable choice of M, this would imply that proving the existence W * M satisfying (28) is NP hard. This in turn would imply that computing (any) p(a) ss"") from p(alss') and p( p(a|ss" ss is NP hard. On the other hand, matrix multiplication w is very specific quadratic form, which may not be flexible enough to incorporate every SQE within (28).
812
813
814
815
816
817
818
819
We could not find any work on NP-hardness of Systems of Polynomial Matrix Equations (SPME). There is work on the NP-hardness of tensor problems [HL13,, but this refers to the design tensors, e.g. Σn jk ARth 22 E B,,, Vi, but the unknowns are always treated as scalars or vectors. Of course [X-Y] = =Σ Labeg abedd Xat Yea, but A = daz dae is a very special fixed tensor (actually of low tensor rank d) with no flexibility of encoding NP-hard problems therein.
821
822
823
21

---

825
That inference in Bayesian networks is No-colle [KF09] does not help us either for two reasons: First, in our problem the probability distribution over states and actions is only partially given. More importantly, our network for i= 2 has only 5 nodes (s.a,s' ,a' s',s",, while the NP-hardness proofs we are aware of require large networks. Even for fixed i > is not obvious how to encode NP-hard problems into EqIM()), due to the severe structural constraints in EqIM(i) compared to a general network with +-+ nodes. is not clear how to exploit the fact that our (few) state nodes are large.
826
827
828
829
830
831
SQE are polynomially equivalent to Systems of Quadratic Matrix Equations (SQME), which may be the reason complexity theorists have ignored the latter. We suspect but do not know whether SQME of bounded structural complexity (only the definitions the constant matrices scale with dl d'xd) d) is hard (Open Problem 7. If we allow sparse encoding of SQE variables in W, i.e. we allow one equation involving C of the form B 0 with boolean matrix B, then bounded SQME becomes Na-hard. See Appendix M for details.
833
835
837
Below we directly reduce lin3SAT to a Bounded-SQMM with @ that resembles our problem as close as we were able to make it.
838
839
An NP-hard matrix problem. (QI)((a) gives
From EIIM(I) we know that =a= B===BWWW" W+, Plugging this into
Bod oW++W+) (B"OW*) (B" ow+) with constraints [ Neoowlje s+ 1++= (alss (29)
This set of equations is purely in terms of what given (B" and Bao') and only involves unknowns
841
W+ without reference to W See Appendix N for some further simplification and discussion. We
842
843
will show:
Proposition 5 (An NP-hard matrix problem) Given A.B,C,I,, deciding whether the following quadratic matrix problem has a solution in W is NP-hard:
845
A@ (W-W) = (C&W)(CoW)
[BoW),+=1 II-W=
(30)
846
This has some resemblance to (29) Since the boundary between P and NP is very fractal/subtle, this in-itself may not imply much, but more meant as a demonstration of how one may approach proving NP- Na-hardness of (29).
847
848
We reduce inn3SAT, which is an NP- NP-complete variant of 3SAT, where each clause must have exactly one satisfying assignment, to (30) A 3CNF(n,m.g) formula is a boolean conjunction of m clauses in n variables, where each clause c, = Ln VL, for ie m1) is a 1-in-3 disjunction of 3 literals, and each literal is lea =x, or it's complement Ls = -y = T.. where j j= g(i,a) is the variable index of clause in position
Proof.
850
852
854
We arithmetize the 3CNF expression in the standard way by replacing True 1, False~> and V-++, i.c. we ask whether the system of linear equations En + +6,== 1 Vi has solution in zz E {0,1). We need encode the x's into W somehow: We aim at the following embedding:
855
858
En
yo
W-
=
21 T1
In
Zn
yo
...
V/k
The y are k++ = max ( 1mm-++2 extra dummy variables to make the matrix a square dx d matrix 857
858
with d: max max(m=x) (m+ +222++++++++++11 1..
859
Choosing a cyclic permutation matrix I= (234.....d ensures that all rows of W are indeed the same via IT. -- W. The standard way of achieving 1y E {0,1) is via =²= and Vブ リ3- This can be achieved via (Ido 2 W, were Id,,/ = -_.- is the identity matrix.
862
We use B W 1 to ensure F, =1 1.-=,,,,. .T. Yo and 11 ... yv 0 and la2 + 422 1.s = by setting B - = for SE [1:n), and B if =x, and Bitn, = L.o = -
863
for i {1:m} } and a E [1,2,3] and 12-1 ... = -a-1 11, and Ba = 1, and B 0
865
for all other ss'. This also ensures that all rows of W sum to +1, hence W-W- (m+1)W, so
I2 E } can be achieved via C= ld and A= - ld in A (C)
887
The construction implics that the 3CNF( (mm(,,m.))))) formula is satisfiable iff (30) has a solution in W with the A,B,C.II as constructed above. This shows NP- MP-hardness of deciding whether (30 has
22

---

889
solution. A solution can trivially be verified (in the rationals or to e-precision over the reals) in time Odd), hence the problem is in NP, hence No-complete.
870
M Systems of Quadratic Matrix Equations
871
872
System of Polynomial Equations (SPE) is a set of multivariate polynomial equations
873
Poly, (x.)).....) =0 0 over R in n variables T, U........ E R for j ( (1:m.. This class is NP- hard (via simple reduction from 1in3SAT, see Section D. We can recursively replace each product my (sum bu-+cu) in the polynomials by new variable z (w) and add "polynomial" equation : = zy (w=bu+t bw). This results in SPEs consisting of only linear equations with a single + (bu+ cu w) and quadratic equations without any + (ry 2), which are still (even with all a a=b= 1 and r y =) NP- hard. We call them Simple Systems of Quadratic Equations (Simple SQE). For the reduction pro-
874
875
876
877
878
879
cess to actually work we need one further dummy variable and equation q q= =1 (to reduce bu- w). Alternatively, with some extra work, we can reduce any SPE into a Simple SQE asking for a non-zero
880
solution. We will pursue the latter, since this is closer to our interest (SQE (17) with solution A 0).
881
882
We can even merge the linear and quadratic equations into a single form zy=bbute cu by choosing
883
b b= 1 and c= 0 (replacing zy by w and adding zy = 0- --..---ww))))) 1.w).
We define a System of Polynomial/Quadratie Matrix Equations (SPME/SQME) as set of m multivariate (quadratic) polynomials Poly, , ,A, .,,,.....IA,,CCCCC B.......) = O in the (unknown) matrix variables AT... and the (given) matrix constants ("coefficients"" A.B.C,... Alternatiely, poly, might be 885
887
viewed as generalized polynomials over a non-commutative matrix ring in the unknowns only. In any case note that
* (A. (B.B)))))
889
By writing out all matrix operations in terms of their scalar operations, SPME is of course a sub-class of SPE. SPE is also sub-class of SPME (choose all matrices to be 1 x matrices), which implies SPME is NP-hard. But we are interested in NP-hard small subclasses of SPME, so will construct
891
more economical embedding: Assume we have a Simple SQE with n variables U.W,,,,U,U..... We place them into d d matrix A (d2 vT) introducing dummy variables for the remaining entries. We
893
can extract variable w- A,.' via ==e*T. -A-e", where e* is basis vector (d 1-matrix) (e")=1==
894
885
If we replace all variables in the Simple SQE expressions zy =y=autbo by such expressions, we get
898
Simple SQME with poly, equations of the form (dropping as usual)
a' AA" " = AR" +o A Vj
(31)
897
While these are scalar equations, since the outer matrices are x on the left and dx on the right, technically they are matrix equations. We could pad all involved matrices, including the outer ones, with zeros to square dxd matrices of the same size (for sufficiently large d, and only polynomial overhead).
898
899
900
We can reduce 31) to just one equation at the cost of making the equations more complicated as follows: Write each equation poly, =0 in the form e polyy Poly,-e' =0, with different (s,s")-pair for each j. These are now "proper" matrix equations, but with all entries identically except entry (s,s') being Poly,. This allows to sum all equations without conflating them into one (complex) matrix equations
902
903
905
Σ,AAA-AA''
(32)
Another way to combine B1 into one equation is by putting all M for all j into one block- dlokk-diagonal matrix M = Di-Diaa(MM M ...,MM for M E (a,A', ,'a" ..ll c.c/,A, .A). For Á we need to ensure that indeed all blocks A = A are equal. This can be done via 11 All= Å for some cyclic block permutation II. We further need to ensure that the off-diagonal blocks of Á are zero. We can zero each block with one equation, but it seems impossible to zero all with a bounded number of Simple QMEs. We can modify the decision problem to decide whether specific sparse solutions Á exist, Formally, we can introduce element-wise multiplication and allow one equation of the form B&A with B being
908
907
908
909
910
911
912
913
0/1 on the on/off-diagonal blocks. This leads to Simple SQME with @ in 3 equations (dropping the
914
AAA'A = CCAC', - BOA=0
(33)
23

---

915
Proposition 6 (NP-hardness of Simple SQME) Systems of Polynomial Equations (SPE) can be polynomially reduced to Simple Systems of Quadratic Matrix Equations (Simple SQME) (31). The number of equations can be reduced to I at the expense of making the equations complex (32) or to
916
917
2 by asking for sparse solutions or by enforcing sparsity via B = (33) Since SPE are NP-hard,
918
919
deciding the existence of non-zero solutions for all three SQME versions is also NP-hard.
920
An NP- up-hardness proof for Simple SQME with @ with 3 equations via reduction from 1in3SAT
that looks much closer the desired form 22 or (34) is given in Section L By similar reduction, 921
922
encoding all variables and their complement in the diagonal of A = Diag 2 Z.G.y.U..... one can also
923
show that solvability of
A = A
Ido AA1=1,
with Ae (0,1)mx2n
924
is NP-complete (I is the all-1 vector, sparse A with 2 or 3 ones in each row suffice), but not all SPE can be reduced to this form.
925
926
Open Problem 7 (Are Bounded SPME NP-hard?) Are Systems of Polynomial Matrix Equations
927
(without @) of bounded structural complexity NP-hard? Bounded means, only the definitions of the constant matrices scale with d d, but the polynomial degrees, number of equations, and number of matrix operations are bounded.
928
929
N
Compact Representation of EqIM(2+)
931
If only Bu+ (EqI)(2+)) is given, we can sum over a' If we further assume a= 2 and define B= B and A= B0+ and W = and exploit B B B++ =1, this reduces to the elegant quadratic
932
933 matrix equation
Ao (W- ((WW)--- (BoW)-W
(34)
with constraints in 29 even simpler W if n is unknown. This is the most pure formulation of the problem we are trying but are unable to solve we could come up with. For A and B defined via
935
936
M, we know that (34) has solution (namely W-++).
937
We neither know whether there exists an efficient algorithm to find some solution (34 nor to find the solution in case it is unique, nor to decide whether there exist solutions in case A and B are chosen
938
939
arbitrarily.
940
The condition W W can be relaxed to W 00 Wf is a solution of (34), then also v Wee Ugr for any v. > 0 (most easily checked via (TI). ). Every non-negative matrix has real negativee Eigenvector v, and W e+ >0 implies v, > 0 and Eigenvalue >>0, hence for Waorm:-- == (Jv²) W Ug'
942
we have W/narm = 1.
8 2 and B+ = 1 iff BE [0:1] (and B² = 1- B). Ba+ 2 and B++ =1 iff A [0:1] (and 94
B A). But can scale back any A and B by the same 0< <<><11 to satisfy these without changing 34 i.e. these extra conditions (A and B bounded by 1) do not make the problem any simpler.
946
Open Problem
948
We present the most important open problem(s) in their simplest instantiation and most elegant form, fully self-contained here: Consider matrices A,B.W e [0:1]dxd with d N, tied by the quadratic matrix equation
950
AO = (B&W).W and W = Vs
(35)
952
where c is element- wise (Hadamard) multiplication and is standard matrix multiplication. The open problems are as follows: Given A and B, are there efficient algorithms which
953
954
(a) decide whether there exists a W satisfying (35
(b) decide whether the solution is unique, assuming 35 has solution?
956
(c) compute a solution, assuming (35) has a solution?
compute the solution, assuming (35) has unique solution?
24

---

0.00e+00
1.18e-12
1.64e-10
1.85e-03
3.73e-02
0.00e+00
5.40e-07
5.46e-05
5.24e-03
1.29e-02
0.00e+00
3.45e-08
3.53e-06
7.72e-04
4.28e-03
0.00e+00
7.30c-05
7.71e-04
7.66e-02
5.27e-01
Figure 4: Reconstructing inverse and forward models from inverse models with noise injected. Rows, from top to bottom, show reconstructions of 3². Ba++ and M Noise increases exponentially across columns, from left to right, [0,10-6 1,0006,,0 ,10 9,10 9,10-4,1 -.10--0 The subplot titles show the average KL divergence of the recovered distribution from the ground truth.
Computing real number means, given any <>> 0, computing E-approximation. Efficient means running time is polynomial in d, ideally with a degree independent of 1/E. General systems of quadratic equations known to be NP-hard, but we do not know the complexity of this particular matrix sub-class.
959
961
962
The upper bounds A, B.B.W.W. <1 can always be satisfied by scaling, hence are irrelevant. W = can be relaxed to Ws+ 20 except in the uniqueness questions. If helpful: One may assume A,B.W strictly positive. Also, any finite (d-independent) number of equations of the form A'O(W (W-WW WW) = (B' W)).
983
964
W with other general matrices A', ,B' e [0:1]dxd may be added, which further constrain the solution space.
985
986
P Experimental Details
987
968
Here we provide further experiments supporting and illustrating the theory. In Appendix Q we show how we numerically dealt with B B=0/0= Appendix R derives the formulas for the plotted solution dimensions.
970
Experiments illustrating robustness to noise. As mentioned in the main text, rather than commit- ting to a specific learning algorithm, we instead directly inject noise into the true inverse distributions. This is done by adding x 10e to the true distribution and renormalizing B, where is drawn from the unit uniform distribution: e e~(((0,1) In Figure 2 this noise is evaluated across several orders of magnitude (c varied -7 to 0).
972
973
g74
375
976
The main text also mentions that the effect of this noise is substantially diminished as the horizon of the inverse model is increased (from B1 := 8 to B3:= +)+
this interpretation
25

---

Figure 5: Reproduced from [FLDP21 this 'half-cheetah' environment has been augmented with videos of complex scenes. This highlights how non-controllable aspects of the environment can be made more complex without changing the underlying control problem. The fact that such environments are of interest motivates our focus on the Tensor-product product special case.
978
by showing that the recovered B is qualitatively similar the ground truth even with substantial noise.
979
Experiments on the Tensor-product special case. As mentioned the main text, M factors into two processes M @ M, where M is action-independent, then only the complexity of the action-dependent process M matters for all of our questions.
980
982
This particular special case is important because of its frequency in applied work. Many environments have most of their complexity in sub-spaces that the agent has no control over. This is illustrated by Figure(3) reproduced from [FFDDP1]] wherein naturalistic videos are superimposed on relatively simple continuous control environments. Clearly, the background dynamics can be arbitrarily complex without impacting the underlying control problem.
984
985
986
987
We can construct small environments of this form via a simple procedure. We construct 1/ with d states and & actions by sampling each element of the appropriately sized matrices from 2//0,1] and then normalizing. M has d=2 states that transition uniformly regardless of the action. For the results
988
989
980
991
shown in Figure k= 5 as in the main text, and d= 2d is varied from 2 to 32.
Note that in Figure the solution dimension is non-zero even when d d= 2d (here =5 hence for d 6|8] 10) despite there necessarily being unique solution as per Section This is due the fact that the algorithm does not exploit knowledge of the fact that M is a tensor product, resulting in the solution dimension being correct for the more general case where W is not confined to being
982
983
984
985
986
tensor product.
Q How to Deal with 0/0
If for some pair of states (s,s"), no action a of positive r7-probability leads from state 8 to s', i.e. M =0, then B and Va are 0/0= = undefined. To also handle Ba we need adapt the linear algorithm in Section[4] We provide 2 different ways of doing so, a couple of variations, all leading to the same correct result.
996
1000
1001
We have restrict the sum in E. Jay ((lls) to those s' for which 8 is defined. We then solve for Jesr again for s' for which 8 is defined, and set Ja =0 0 for those s' for which 3 =L. Technically this can be achieved by removing the s' columns from matrix Bg. and J.. for which
1002
1003
1004
1005
B ... = =1 solve the reduced linear equation system, and finally reinsert J..- = 0 for the removed s
Simpler to replace Be - by B =0, solve the equation for J, and then set Jas =0 for the s' for which the original B was L. Some solvers automatically result in Jaw = 0, since this is the minimum norm solution, but it is better not to reply on this. Instead of setting J.y =0 after solving
1006
1007
1008
1009
the linear system, one could also augment B with extra rows that enforce J.. =0
1010
Alternatively, we could replace B.., = 1 by random vector which sums to 1, e.g. =Ta where r. = logu, with u. (0niform(0:1], Provided that the solution is unique, this also leads to the correct solution (almost surely), and in this way Jee' = automatically. If the solution is not unique, W will still satisfy 8 = Wd 2 W when for 1a L. but Wi may not be O.
1011
1012
1013
1014
The adaptation of the Linear Relaxation Algorithm in Section 5 follows the same pattern: A L
in 12), whenever one of the three involved B's is undefined. For such ss g2, we need to ensure that
1015
1016
sa 0. which can be done with any of the variations described above. Once have Usaas,
set C
0 if Bad L. No further intervention is needed, since USSts/ = 0 already.
1017
26

---

1018
R
For r {1:dj), the columns of matrix C span the tangential space of "rescaled" variety Bon' at Baa', Again, the columns may not be linearly independent. If [(M*)]? |a-r = 0. then = Vaa', hence all such ss" should be ignored in Caa'", but since the corresponding rows in C' are O. they don't it contribute to the rank anyway. Numerically, we need regard all singular values Solution Dimensions of W and Ban',
In Section 4 we presented an algorithm for inferring W and Baa' from B". Even if M cannot uniquely be reconstructed -(i), Bad' may still be unique (iii). More generally, the solutions J and W" form linear spaces of dimension d, = dw S Ed(d-1) (d, 2dw since W is a linear function of J and d, S dw since W+= Bad is a (non-linear, polynomial) variety of dimension dp S dw at regular points (it is smooth function of W).
1019
1020
1021
1022
1023
1024
Parameterizing the solutions for J and W and B. We can determine the solution dimensions
1025
d,, dw, and dB as follows: Let I os be solution of [B"H o1]++ O. If Jas' is a solution of [BaO @J |o = 77 [a]s), then so is J == J+I, hence Wa := M + A is a solution of B = V 2 W+ and W - (als), where M = Ba JJ and =
1026
1027
If we plug in = +M" into Ban := w" ((MW) we get the variety of Bas' parame- terized in terms A If we expand this non-linear expression up to linear order in A we get after
1028
1029
1030
some algebra
Bae's = IM"M +M + "
(36)
The linear part forms a tangent direction on the Ban' variety at Bad', := M
1031
1032
Determining the solution dimensions for J and W and B. Now, for each 8, let F for sg' E [1: {1:ddd;))) ) span all solutions of [Ba of =0, which can easily be determined by SVD: d,s is the number zero singular values of matrix B and r the corresponding singular vectors. Then,
1033
1034
Ja. Jaw + E 2rr for any 2 EER" Rd with d = -, is a solution of [+J]+++=
1035
ee'
1036
= Similarly, : Ma Eg with A B span all solutions consistent with B and
म. The solution dimension is E. dws. where for each 8, dws the rank of Ag. if interpreted
1037
1038
as a kdx d,, matrix in as' xr. dw, may be smaller than d.s,, since unlike 2.. Ag. may not be full
1039 rank.
If we plug Agg. = -, Zsr into 36 after some index manipulation we get
1040
d d.
Ban' = Bad! +
C
+ O(2?) with
(=1==1
Caglrt (MRA +[A" +[A M l.s" (AM
1 [M M Tse" (M M [A M* (11))
1041 Baa' (z) is local parametrization of B, and if we drop the + +2(2?), it parameterizes its tangential
hyperplane Baa', Its dimension d is the rank of C interppreeed dd matrix in na'ss" xrl.
1042
1043
Again, d may be smaller than dw, since C may not be full rank.
1044
Remarks.
1045
1048 SS"
1047
1048
below some threshold as O. For (to numerical precision) exact B, the threshold can be fairly small (10-1) 13 in all our experiments). For approximate/learned B, the threshold needs to be of the order of the accuracy of B.
1019
1050
1051
Sampling estimate of dg. A simpler, but less elegant, and more fragile method to estimate da is as follows: Fix one solution J. Add random noise in direction of the null-space spanned by I" so that it stays a solution, i.e. compute J= - z., for random 2, and from this, W and Bea' for
1052
1053
many such random J. The resulting point cloud spans covers the solution variety Baa', Various tools could be used to analyze this point cloud, e.g. determine its dimension. If = is chosen small, the point
1054
1055
cloud concentrates around gea' and forms a near-lineat space, whose dimension dg can easily be
1056
1057
determined by PCA.
27

---

1058
Higher-order B and higher i. In the same way we can derive the solution dimensions dB... for higher-order B--. Also, even though we don't 't have (yet) an efficient algorithm for solving (i) for i >>> 1 if the solution is not unique, we still can determine the dimension of the solutions (at
1059
1080
1081
particular point .M. Algorithmically already covered is the case of W satisfying Eq(())))
1082
whose solution dimension turns out to be dw - -d.. The general procedure is to plug W = MM +A into
1083
and linearly expand EqIM(i) for we hold. Together they form a system of linear equations whose solution dimension can be determined by SVD as above.
1084
28


Reviews:
[{"review_id": "pZUBFRmGxVP", "reviewer": "Reviewer_5AUZ", "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.", "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).", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality:\n\nThis 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).\n\n\nQuality:\n\nI have not checked most of the calculations carefully, but based on what I have checked, the maths appears to be sound.\n\n\nClarity:\n\nThe 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.\n\n\nSignificance:\n\nI 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.\n\n\nSummary:\n\nI 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2kxzc0J6Zj", "reviewer": "Reviewer_SKHG", "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.", "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?\n\n  **Motivation: causal inference, line 24**: It is written that \"An\n  inverse model captures the likelihood that an action $a$ was *the\n  cause* of the transition...\", but is this truly correct? To my\n  understanding, such a conditional model is incapable of inferring\n  causation. Wouldn't one need some sort of counterfactual analysis as\n  well?\n\n  **Marginalizing variables in transition tensors**: On lines 120 and 121,\n  I believe there is an inconsistency in the notation. In the Notation\n  section, it is writen that $M^a_{\\cdot\\cdot}$ is the matrix at\n  dimension $a$, but here it is written $M^a$. I'm assuming $M^a,\n  M^a_{\\cdot\\cdot}$ represent the same thing, but then maybe the\n  $M^a_{\\cdot\\cdot}$ notation should be avoided altogether.\n\n  **Challenges with the backward model**: Line 127 says $B^{a+}\\neq B^a$,\n  can this be expanded upon? This is unintuitive, at least to me. After\n  line 121, it says $B^a_{ss'} = p(a\\mid ss')$, and after line 129 it\n  says $B^{a+}_{ss''} = p(a\\mid ss'')$, thus\n\n  \\begin{equation*}\n  \\begin{aligned}\n  B_{ss'}^{a+} = p(a\\mid ss')  =B_{ss'}^a\n  \\end{aligned}\n  \\end{equation*}\n\n  Which implies that $B^a = B^{a+}$ since all of their entries are\n  equal.\n\n  **The Questions**: The six questions, first stated on line 46, are very\n  confusing. Firstly, they're stated in different terms several times,\n  which is confusing on its own. Why not list the questions only once,\n  in the most intuitive way? Moreover, the questions are too complicated\n  individually. I think it would be much clearer if you don't state all\n  of these questions explicitly, and rather prove the answers as\n  theorems/lemmas/propositions. It's very hard to remember which\n  question is which as you go through the text, and it's actually very\n  hard to digest what the paper is trying to do with such a dense list\n  of questions. In my opinion, the motivation for the paper is clear\n  enough on its own, and I don't think it'll be difficult to convince\n  most readers that understanding these inverse models is an important\n  task. But when the exact meaning of \"understanding\" is stated so\n  verbosely, it actually detracts from the clarity of the paper. One\n  example that is particularly confusing appears on line 139, where it\n  says \"Questions (i) - (vi) also have multiple variations\", followed by\n  a list of three questions. How do you go from 6 questions to 3, which\n  correspond to which? Now you're actually assuming that the reader will\n  recall at least 9 questions.\n\n  Moreover, if you must include these questions, it would be\n  tremendously more convenient if they can be hyperlinked.\n\n  **Line 149**: Another rephrasing of the questions here says\n\n  > One way to rephrase the questions is whether $f(M) = f(W)$\n  > implies $M=W$ or $g(M) = g(W)$ for all (or most or some)\n  > $M$ and $W$.\n\n  I don't understand this question at all. The property that $f(M) =\n  f(W)\\implies M = W$ is more a property of the function $f$ than the\n  objects $M,W$. Indeed, this property is known as\n  \"injectivity\". Likewise, \"whether $f(M) = f(W)$ implies $g(M) = g(W)$\"\n  is also highly dependent on the particular properties of\n  $f,g$. Currently $f,g$ are only assumed to be arbitrary functions, so\n  it is really unclear to me what the purpose of this question is. I had\n  a clearer understanding of the questions before reading this.\n\n  **Equations (8) and (9)**: Surely the notation can be improved here, it\n  is extremely difficult to parse. Why not use product notation\n  ($\\prod$)? Also, in equation (9), what is $B^{a+\\dots+}$? Are there\n  $i$ dots? Back to my previous comment, I believe $B^{a+\\dots+}\\equiv\n  B^a$ unless there's an inconsistency in the notation.\n\n  Later, on line 161, the term $\\text{EqIM(1)}$ is mentioned, but where\n  is that defined? Only equations $\\text{EqIM}(ia)$ and\n  $\\text{EqIM}(i+)$ are defined.\n\n  **Example violating (i, iii, v)**: It appears that what you're showing\n  is that for random variables $X, Y$ distributed by $\\mu_X, \\mu_Y$,\n  there may exist several distinct random variables $(X, Y)$ with\n  marginals $\\mu_X, \\mu_Y$. This is well known.\n\n  **Line 169**: I don't understand how this relates to (i), (iii), (v) at\n  all. You're assuming that two MDPs encoded by $M,W$ have the same\n  transition dynamics, and then based on that, the ability to infer\n  multistep models from fewer-step models is guaranteed? Something is\n  missing here. How does $W$ fit in?\n\n  **Line 171**: It says \"Note that $M_{ss'}^a\\equiv p(s'\\mid sa)$\n  independent of $a$ implies $M_{s+}^a$ independent of $a$...\" -- this\n  is only true if it holds /for every pair/ $(s, s')$. Also, this whole\n  \"degenerate case\" is fairly trivial: $M$ and $W$ are only related via\n  $\\pi(a\\mid\\cdot)$, so if they're both actually independent of $a$,\n  then of course any equality of this sort must imply that the MDPs are\n  identical.\n\n  **Line 175**: What does it mean for tensors to be \"nearly independent\"\n  of $a$?\n\n  **Line 178**: Similarly to the \"independent of $a$\" case, why is this\n  even an interesting case to study? As pointed out, the consequences\n  are fairly obvious.\n\n  Altogether, I didn't find section 3 to be very informative.\n\n  **Non-linear manifold**: On line 212, it says that $B^{aa'}$ forms a\n  non-linear manifold of dimension at least $d(d-k)$. But what is the\n  \"dimension\" of a non-linear manifold? Perhaps there is a definition\n  for this, but I doubt it's widely known to the Neurips audience. I'd\n  much prefer to have seen this definition in the background section in\n  place of the algebraic properties of tensors.\n\n  **Line 214**: I believe this logic is flawed. It says \"... this now\n  gives an over-determined system which generally has no solution. But\n  by assumption, $M$ is a solution, which gives hope that there may be\n  only one or a finite number of solutions\". What is being said here is\n  that the situation only makes sense if the \"over-determinacy\" is\n  redundant, so that it's not actually over-determined. This doesn't\n  give any hint about the number of solutions. There may very well be\n  infinitely-many solutions regardless of the fact that the system is\n  over-determined.\n\n  **Figure 1**: This figure is never mentioned in the text, it would be\n  nice to have some discussion of the results it's presenting.\n\n\nMinor issues\n============\n\n  **Contents section**: On line 88 \"Appendix A\" is mentioned, but then\n  subsequent appendices are written \"(B)\", for instance, which is a\n  little confusing.\n\n  **Matrix notation**: On line 105, it is written \"Capital letters... are\n  used for $d\\times d$ matrices over $[0;1]\\subset\\mathbf{R}$...\".  Is\n  $[0;1]$ the closed unit interval? Why not write \"Capital\n  letters... are used for matrices in $[0, 1]^{d\\times d}$\"?\n\n  **Tensor notation**: On line 109,\n\n  > Let $\\odot$ denote element-wise (Hadamard)\n  > multiplication... and similarly $\\oslash$, while (no)\n  > $\\cdot$ represents (conventional) matrix multiplication\n  > and has operator preference over $\\odot$ and $\\oslash$.\n\n  I don't understand this at all. What is $\\oslash$? What is $\\cdot$?\n  I'm assuming that by \"similarly $\\oslash$\" it is meant that $\\oslash$\n  is element-wise division (this should be stated, because the sentence\n  doesn't make sense otherwise), and that $\\cdot$ represents matrix\n  multiplication. But what does \"while (no) $\\cdot$\" mean?\n\n  **Algebraic properties of tensors**: Does this really need to be\n  included here? It's hard to read math packed into a paragraph like\n  this. Also many of these properties are very intuitive (i.e., I think\n  just about every reader will have inuition for the $D\\odot\\text{Id}$\n  property without it being stated), and then some properties are highly\n  abstract (matrices form a ring...). I think it's fair to assume that\n  readers of this paper understand how to do algebra with matrices and\n  tensors, even if they don't know what a ring is.\n", "limitations": "The authors have addressed the limitations of their methods.", "rating": 3, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "28lVMlmDQL", "reviewer": "Reviewer_mjPn", "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. ", "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.\n\nSection 2:\nFor 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.\n\nYour overloaded notation for EqIM is a bit confusing. You defined EqIM(ia) and EqIM(i+), but not EqIM(i).\n\nSection 4:\nFor 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.\n\nSection 5:\nAgain, 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)?\n\nSection 6:\nI don’t see the experimental details listed anywhere - how do you generate these randomized grid worlds? \n\nAlso 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.\n", "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.\n\nAnother 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.\n", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. \n\nIn 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.\n\nFinally, 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.\n\nOverall, 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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject