From Optimal Actions to World Models: Identifiability of Transition Kernels in Discounted MDPs

Neal Batra

From Optimal Actions to World Models: Identifiability of Transition Kernels in Discounted MDPs

T0 review · 0 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Knowing only which actions are optimal can hide the true transition probabilities, but next-state rewards reveal almost all of them.

desk verdict A genuinely new and correctly proved identifiability classification for optimal-action observations; the all-rewards oracle is the only load-bearing idealization, and the paper is upfront about it. read the letter →

arxiv 2608.07301 v1 pith:GHKCEVMG submitted 2026-08-07 cs.LG

Neal Batra This is my paper · ORCID

classification cs.LG MSC 90C40

keywords Markovdecisionprocessesidentifiabilitytransitionkernelsoptimalactionsstate-actionrewardstransition-dependentequivalenceinversereinforcementlearning

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks how much of a Markov decision process's transition probabilities can be recovered from knowing only which actions are optimal, for every reward in a given class. For state-action rewards, optimal actions are not enough: two different kernels can produce identical optimal-action sets exactly when they are related by an invertible matrix transformation. The paper gives the full classification, shows the remaining ambiguity is n(n-1)-dimensional near a strictly positive kernel, and proves that rewards depending on the next state do much better, generically identifying the kernel exactly. The results separate the question of what an agent should do from the question of what will happen next, and show that the answer depends sharply on the form of the reward.

What carries the argument

The central object is the transformation Φ_L(P)_{s,a} = (P_{s,a} + (1/γ)e_s^T(L-I))$L^{{-1}}$ for L in the group G = {invertible matrices with L1=1}. It encodes a change of value-function coordinates that leaves all action comparisons invariant, and the paper shows the state-action equivalence class of P is exactly its orbit under this transformation. The necessity argument builds rewards r^P_v(s,a) = v(s) - γP_{s,a}v that make every action optimal, forcing a single matrix L to relate the two kernels' value functions for every deterministic policy.

What would settle it

For two given kernels P and Q, compute L = (I-γQ^π)^{-1}(I-γP^π) using any deterministic policy π. If P and Q give the same optimal actions for every state-action reward but L fails to satisfy L1=1 or Q_{s,a} = (P_{s,a} + (1/γ)e_s^T(L-I))$L^{{-1}}$ at some state-action pair, then Theorem 3.4 is false. Similarly, a kernel Q with identical transition-dependent optimal actions but differing from P at a state with at least two actions would refute Theorem 4.2.

Watch

Extended reading notes

Core claim

The paper proves that for state-action rewards, two transition kernels P and Q are equivalent if and only if there is an invertible matrix L with L1=1 such that Q_{s,a} = (P_{s,a} + (1/γ)e_s^T(L-I))$L^{{-1}}$ for every state and action. This is equivalent to saying that every action advantage A^π_{P,r}(s,a) equals A^π_{Q,r}(s,a) for every deterministic policy π and reward r, and it implies the value functions are related by a linear map L. Near any strictly positive kernel, the equivalent kernels form a smooth manifold of dimension n(n-1). Under transition-dependent rewards, all rows at states with at least two actions are identified, and a row at a one-action state can differ only when that state's indicator reward makes every action optimal everywhere; hence almost every strictly positive kernel is identified exactly. Under state rewards, equivalence is exactly equality of the optimality region for each deterministic policy, a strictly coarser relation.

Load-bearing premise

The entire classification assumes an oracle that reveals the complete set of optimal actions for every possible reward in the chosen class, including rewards constructed from the unknown transition kernel; if the observer sees only finitely many rewards or rewards from a restricted family, the set of indistinguishable kernels can be strictly larger.

Editorial extensions

If this is right

State-action reward observations reveal all action advantages but not the kernel itself; the remaining ambiguity is parameterized by an n(n-1)-dimensional family near a strictly positive kernel.
The fraction of kernel space lost to state-action equivalence is about 1/m when every state has m actions, so more actions per state make the equivalence class relatively smaller.
With at least one state offering two actions, transition-dependent rewards identify almost every strictly positive kernel; only a measure-zero set of kernels remains ambiguous.
Unique optimal actions are no more informative than allowing ties: the same equivalence classes arise from rewards with a unique optimizer at every state.
State rewards are strictly weaker: two kernels are state-reward equivalent exactly when every deterministic policy is optimal for the same set of rewards.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the observer sees only a finite set of tasks or rewards restricted to a feature space, the equivalence class can be strictly larger than the Φ_L orbit; quantifying this gap is a natural next step and directly relevant to inverse reinforcement learning from logged data.
The determinant identity det(I-γP^π)/det(I-γQ^π) = det L gives a policy-independent invariant that could serve as a statistical test for whether two estimated kernels are action-equivalent.
The measure-zero exceptional set in Proposition 4.4 suggests that a randomly perturbed kernel is almost surely identifiable under transition-dependent rewards, a form of generic identifiability useful for model-based reinforcement learning.
The Φ_L parameterization could be used to construct priors in Bayesian inverse reinforcement learning that are invariant under action-observation symmetry.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's my take. The paper gives the first exact identifiability classification for transition kernels from optimal actions alone, for three reward families. Theorem 3.4 is the core: with state-action rewards, two kernels produce identical optimal actions for every reward iff they are related by Q_{s,a} = (P_{s,a} + (1/γ)e_s^T(L-I))L^{-1} for an invertible L with L1=1. That is a clean, non-obvious statement, and the proof is complete. The transition-dependent result (Theorem 4.2) is also good: rows at states with at least two actions are pinned, and the only obstruction is a precisely characterized singleton-action state. The state-reward result (Theorem 5.2) is a bit softer—it characterizes equivalence via policy regions—but it's still a genuine converse. The examples (3.9, 5.4) correctly demonstrate the strict implications.

The proofs held up under scrutiny. The contraction argument, the L-matrix identity, and the measure-zero argument in Proposition 4.4 all check out. The paper is self-contained, and it is honest about what it does not cover.

The one assumption that does real work is the oracle: optimal actions for every real-valued reward in the class. Lemma 3.2's necessity direction constructs rewards r^P_v that depend on the unknown kernel P, and the argument only goes through because the oracle answers for those rewards too. For finite task sets or linear feature rewards, the equivalence class can be strictly larger; the paper says this explicitly in Section 6 and leaves the finite-reward case open. That is a boundary, not a hidden flaw, but it does mean the headline 'from optimal actions alone' is about an idealized observation model. Practical readers should not expect exact recovery from finite data. A minor editorial issue: references [10]–[14] are listed but never cited in the body.

Overall: this is a well-executed theory paper with new results and complete proofs. It should go to peer review. I would recommend acceptance after the uncited references are cleaned up, and with the oracle assumption stated up front in the abstract.

Referee Report

0 major / 5 minor

Summary. The paper studies identifiability of the transition kernel of a finite discounted MDP from optimal-action data. Three reward classes are compared. For state–action rewards, Theorem 3.4 shows that two kernels P and Q yield the same optimal actions for every reward if and only if there is an invertible matrix L with L1=1 such that Q_{s,a} = (P_{s,a} + γ^{-1} e_s^T(L-I))L^{-1} for every state-action pair; equivalently, all policy advantages coincide. Proposition 3.6 shows that near a strictly positive kernel the equivalence class is a smooth n(n-1)-dimensional manifold. For transition-dependent rewards, Theorem 4.2 shows that equivalence is state-action equivalence plus agreement of every row at states with at least two actions, with a precisely described exception at singleton-action states, and Proposition 4.4 proves that almost every strictly positive kernel is exactly identified when at least one state has two actions. For state rewards, Theorem 5.2 gives a finite-test characterization through policy optimality regions. Examples show that the three equivalence notions are strictly ordered.

Significance. The paper's main contribution is an exact, self-contained classification of a natural inverse problem, with all lemmas proved in the text and the key transformation Φ_L(P) described explicitly. The generic identifiability result for transition-dependent rewards and the strict separation of the three reward models are likely to be useful reference points for inverse RL and world-model identifiability. The paper is also honest about its main idealization: the classification assumes an oracle that returns optimal actions for every reward in the class, and Section 6 explicitly leaves finite or parametric reward families open. This limits direct application to ordinary finite datasets but does not undermine the mathematical claim, which is conditional on the stated observation model.

minor comments (5)

[§3.1, Proposition 3.6] The proof that the image of F_P is an embedded manifold of dimension n(n-1) would benefit from explicitly stating that the smooth left inverse Q ↦ (I-γQ^π)^{-1}(I-γP^π), defined in a neighborhood of P, makes F_P an immersion; as written the argument is correct but the dimension claim is too compressed.
[Theorem 4.2] In the necessity proof, the existence of h with ph = 0 and qh = 1 is asserted without proof; the existence follows because q-p is not proportional to p for two distinct probability rows, but a one-line justification would improve the exposition.
[Example 3.9 / Corollary 5.5] Example 3.9 would be clearer if it noted explicitly that P ≠ Q and both states have two actions, so Theorem 4.2(ii) rules out transition-reward equivalence; this is the fact used by Corollary 5.5 to show the first implication is strict.
[Abstract / Section 6] Because the central idealization is the all-rewards oracle, the abstract should perhaps say 'complete optimal-action information over all rewards' rather than 'optimal actions alone', which may suggest finite behavioural data; Section 6 already states the limitation clearly.
[Throughout] There are minor typographical errors, including the Section 3 heading 'State{action rewards' and 'University of W arwick' in the affiliation, which should be corrected.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the classification is proved from the Bellman equations and the all-rewards oracle is an explicit assumption, not a hidden reimport of the conclusion.

full rationale

The paper's central results are derived directly from the Bellman optimality equation and the stated equivalence relations, and the derivation is self-contained. The necessity direction in Lemma 3.2 constructs rewards r^P_v(s,a) = v(s) - gamma P_{s,a}v that depend on the unknown kernel P, but this is a legitimate proof device: the equivalence relation P ≡_sa Q is defined as agreement of optimal actions for every state-action reward, so model-dependent rewards are within the quantified domain. The reward construction does not fit a parameter to a data subset and then relabel it as a prediction; it is used to derive the existence of a single matrix L satisfying (I - gamma Q^pi)L = I - gamma P^pi for every policy. The transformation Phi_L is derived, not assumed, and the local dimension statement follows from the structure of the group G. Existing work by Letcher et al., Grimm et al., and others is used only for comparison and context, not as load-bearing support for the theorems, so there is no self-citation chain or imported uniqueness result. The Section 6 limitation paragraphs explicitly acknowledge that the classification assumes access to optimal actions for all rewards and that finite or restricted reward classes may produce larger equivalence classes; this is a boundary condition on the theorem's applicability, not a circular step. Overall, the derivation chain does not reduce to its inputs, and no fitted quantity is renamed as a prediction.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The paper introduces no new physical or mathematical entities. The only free object is the matrix L, which is the classification's parameter of indeterminacy. The proof uses explicitly constructed rewards that depend on the kernel P; these are legitimate members of the reward class but are chosen adversarially, reflecting the strong observation model. No data fitting or post-hoc selection is involved.

free parameters (1)

L (n x n matrix, invertible, L1=1)
The central classification (Theorem 3.4, (13)) says two kernels are indistinguishable exactly when Q = Φ_L(P) for some L in G. L is not fitted to data; it is the parameterization of the equivalence class itself. Near a strictly positive kernel the set of valid L has dimension n(n-1) (Proposition 3.6), which is the paper's main statement of residual indeterminacy.

assumptions (4)

domain assumption Finite discounted MDP: finite state/action sets, discount factor γ in (0,1), known state and action labels.
The entire framework of Section 2.1 and all definitions of equivalence rely on this finite setting.
domain assumption Optimal actions are observable for every real-valued reward in the chosen class, including rewards that depend on the unknown kernel.
Definition 2.1 quantifies over all rewards, and the necessity proof in Lemma 3.2 constructs rewards r^P_v(s,a)=v(s)-γP_{s,a}v. This oracle-like observation model is a stated limitation in Section 6.
standard math Existence of deterministic stationary optimal policies for finite discounted MDPs (Puterman [1]).
Used in Theorem 3.4 (ii)->(i) and in the state-reward section (Section 5).
standard math Contraction property of the Bellman optimality operator gives unique value functions.
Used in Lemma 3.1 and in the proof of (18) to identify the fixed point as the optimal value.

how reviews work

0 comments

Cite this review

Pith. "Pith review of From Optimal Actions to World Models: Identifiability of Transition Kernels in Discounted MDPs." pith.science (2026). https://pith.science/paper/GHKCEVMG

@misc{pith2026260807301,
  author       = {Pith},
  title        = {Pith review of: From Optimal Actions to World Models: Identifiability of Transition Kernels in Discounted MDPs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GHKCEVMG}},
  note         = {Machine review of arXiv:2608.07301}
}

abstract

We study what can be recovered about the transition probabilities of a Markov decision process from optimal actions alone. This is closely related to the inverse problem considered by Letcher et al., who ask when the dynamics can be recovered from numerical $Q$-values. Here the numerical values themselves are not observed; only the optimal actions are known, for every reward in a given class. For state-action rewards $r(s,a)$, knowing the optimal actions for every reward also tells us how much better one action is than another when each is followed by the same fixed policy. This is still not enough to determine the transition probabilities uniquely. We prove that two kernels give the same optimal actions for every reward exactly when \[ Q_{s,a} = \Bigl(P_{s,a}+\tfrac1\gamma e_s^{\mathsf T}(L-I)\Bigr)L^{-1} \] for one invertible matrix $L$ satisfying $L\mathbf 1=\mathbf 1$. Near a kernel with strictly positive entries, there is an $n(n-1)$-dimensional family of different kernels with this property. The result is unchanged if we consider only rewards having a unique optimal action at every state. We then compare this with rewards of the forms $r(s)$ and $r(s,a,s')$. Rewards that depend on the next state can usually recover the transition kernel itself: every row at a state with at least two actions is determined, and we describe exactly when a row at a state with one action can remain hidden. State rewards reveal less: two kernels give the same optimal actions exactly when every deterministic policy is optimal for the same set of rewards. The results show how the form of the reward affects what can be learned about the dynamics from optimal actions alone.

Figures

Figures reproduced from arXiv: 2608.07301 by the authors.

**Figure 1.** The kernels in Example 4.5. At state 0, actions a and b have the same transition row under both kernels. The only changed row is attached to the unique action c at state 1, so the change cannot affect which actions are optimal. Thus P and Q have different transition probabilities but always give the same optimal actions. The difference is hidden because state 1 has only one possible action, while the two actions at … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 13 canonical work pages

[10]

A. Y. Ng and S. Russell. Algorithms for inverse reinforcement learning. InProceedings of the 17th International Conference on Machine Learning, pages 663–670, 2000

work page 2000
[14]

Ferns, P

N. Ferns, P. Panangaden, and D. Precup. Metrics for finite Markov decision processes. InProceedings of the 20th Conference on Uncertainty in Artificial Intelligence, pages 162–169, 2004. 15

work page 2004
[1]

M. L. Puterman.Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley, 1994

work page 1994
[2]

R. D. Smallwood. Optimum policy regions for Markov processes with discounting.Operations Research, 14(4):658–669, 1966

work page 1966
[3]

Givan, T

R. Givan, T. Dean, and M. Greig. Equivalence notions and model minimization in Markov decision processes.Artificial Intelligence, 147(1–2):163–223, 2003

work page 2003
[4]

A. Y. Ng, D. Harada, and S. Russell. Policy invariance under reward transformations: Theory and application to reward shaping. InProceedings of the 16th International Conference on Machine Learning, pages 278–287, 1999

work page 1999
[5]

Grimm, A

C. Grimm, A. Barreto, S. Singh, and D. Silver. The value equivalence principle for model-based reinforcement learning. InAdvances in Neural Information Processing Systems, volume 33, 2020

work page 2020
[6]

J. M. V. Skalse, M. Farrugia-Roberts, S. Russell, A. Abate, and A. Gleave. Invariance in policy optimisation and partial identifiability in reward learning. InProceedings of the 40th International Conference on Machine Learning, volume 202 of PMLR, pages 32033–32058, 2023

work page 2023

Show all 14 references

[7]

Mustafin, A

A. Mustafin, A. Pakharev, A. Olshevsky, and I. C. Paschalidis. MDP geometry, normalization and reward balancing solvers. In Proceedings of the 28th International Conference on Artificial Intelligence and Statistics, volume 258 of PMLR, pages 2476–2484, 2025

2025
[8]

Richens, D

J. Richens, D. Abel, A. Bellot, and T. Everitt. General agents contain world models. arXiv:2506.01622, 2025

2025
[9]

Letcher, M

A. Letcher, M. Fellows, A. D. Goldie, J. Richens, J. N. Foerster, and O. Richardson. Inverting the Bellman equation: From Q-values to world models. arXiv:2606.21173, 2026

2026 arXiv
[11]

Ghatrani and A

Z. Ghatrani and A. Ghate. Inverse Markov decision processes with unknown transition probabilities.IISE Transactions, 55(6):588– 601, 2023

2023
[12]

H. Cao, S. Cohen, and L. Szpruch. Identifiability in inverse reinforcement learning. InAdvances in Neural Information Processing Systems, volume 34, pages 12362–12373, 2021

2021
[13]

K. Kim, S. Garg, K. Shiragur, and S. Ermon. Reward identification in inverse reinforcement learning. InProceedings of the 38th International Conference on Machine Learning, volume 139 ofProceedings of Machine Learning Research, pages 5496–5505, 2021

2021

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.

[1] [10]

A. Y. Ng and S. Russell. Algorithms for inverse reinforcement learning. InProceedings of the 17th International Conference on Machine Learning, pages 663–670, 2000

work page 2000

[2] [14]

Ferns, P

N. Ferns, P. Panangaden, and D. Precup. Metrics for finite Markov decision processes. InProceedings of the 20th Conference on Uncertainty in Artificial Intelligence, pages 162–169, 2004. 15

work page 2004

[3] [1]

M. L. Puterman.Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley, 1994

work page 1994

[4] [2]

R. D. Smallwood. Optimum policy regions for Markov processes with discounting.Operations Research, 14(4):658–669, 1966

work page 1966

[5] [3]

Givan, T

R. Givan, T. Dean, and M. Greig. Equivalence notions and model minimization in Markov decision processes.Artificial Intelligence, 147(1–2):163–223, 2003

work page 2003

[6] [4]

A. Y. Ng, D. Harada, and S. Russell. Policy invariance under reward transformations: Theory and application to reward shaping. InProceedings of the 16th International Conference on Machine Learning, pages 278–287, 1999

work page 1999

[7] [5]

Grimm, A

C. Grimm, A. Barreto, S. Singh, and D. Silver. The value equivalence principle for model-based reinforcement learning. InAdvances in Neural Information Processing Systems, volume 33, 2020

work page 2020

[8] [6]

J. M. V. Skalse, M. Farrugia-Roberts, S. Russell, A. Abate, and A. Gleave. Invariance in policy optimisation and partial identifiability in reward learning. InProceedings of the 40th International Conference on Machine Learning, volume 202 of PMLR, pages 32033–32058, 2023

work page 2023