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

FROM OPTIMAL ACTIONS TO WORLD MODELS IDENTIFIABILITY OF TRANSITION KERNELS IN DISCOUNTED MDPS NEAL BATRA Dovetail Research · University of Warwick

arXiv:2608.07301v1 [cs.LG] 7 Aug 2026

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. [9], 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   −1 Qs,a = Ps,a + γ1 eT s (L − I) L for one invertible matrix L satisfying L1 = 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.

1. Introduction

A transition model tells us both what an agent should do and what is likely to happen after each action. These are not the same kind of information. Two models may recommend exactly the same actions while making different predictions about the next state. This paper asks when that can happen, even if the optimal actions are known for every reward in a large class. The question is closely related to recent work of Letcher et al. [9], who ask when a transition kernel can be recovered from numerical Q-values. Here, we retain only optimal actions. Since one optimal action contains far less information than a full vector of Q-values, it is not clear in advance how much of the transition kernel can still be recovered. Let P be the transition kernel of a finite discounted Markov decision process. For a reward r, write OptP,r (s) for the set of optimal actions at state s. We classify all kernels Q satisfying OptP,r (s) = OptQ,r (s)

for every permitted reward r and every s ∈ S.

(1)

Thus P and Q are regarded as indistinguishable when every reward in the chosen class leads to exactly the same optimal actions. We compare three kinds of reward: r(s),

r(s, a),

r(s, a, s′ ).

(2)

The distinction matters because each form of reward can test the dynamics in a different way. A state reward can only value the states that are visited. A state–action reward can also distinguish actions immediately. A transition-dependent reward can directly reward or penalize a particular successor state. Our main result concerns state–action rewards. Suppose that P and Q give the same optimal actions for every reward r(s, a). We prove something stronger than equality of the optimal choices: for every deterministic policy and every reward, taking an action once and then following that policy has the same advantage under both kernels. Equivalently, the difference between the returns from any two actions is the same under P and Q. Funded by the Advanced Research + Invention Agency (ARIA) through project code MSAI-SE01-P005. 1

Introduction

This happens exactly when there is one invertible matrix L, the same for every policy and reward, such that   −1 Qs,a = Ps,a + γ1 eT , s (L − I) L

L1 = 1.

(3)

The matrix L relates the value functions under the two kernels. Formula (3) gives all kernels that cannot be distinguished using state–action rewards. Near a kernel with strictly positive entries, these kernels form an n(n − 1)-dimensional smooth subset of a space of dimension X (n − 1) |A(s)|. (4) s∈S

The proof initially uses rewards for which several actions are optimal. Appendix A shows that these rewards are not essential: the same classification already follows from rewards having a unique optimal action at every state. Transition-dependent rewards give substantially more information. Because the reward may depend on the successor state, it can be chosen to distinguish two different transition rows directly. We prove that every row at a state with at least two actions must therefore be identified. A row at a state with one action can remain hidden, but only in the special case where rewarding visits to that state never changes any optimal action. As a consequence, once the MDP contains at least one genuine choice, almost every strictly positive kernel is identified exactly by transition-dependent rewards. State rewards give less information. For each deterministic policy, one can consider the set of state rewards for which that policy is optimal. We prove that two kernels give the same optimal actions for every state reward exactly when all of these sets agree. This gives a finite test for equivalence, although not the explicit description obtained for state–action rewards. The three cases therefore satisfy P ≡tr Q =⇒ P ≡sa Q =⇒ P ≡s Q, and both implications are strict. Allowing the reward to depend on more of the transition makes it possible to distinguish more transition models. The comparison with the existing literature is as follows. Letcher et al. [9] retain numerical Q-values for a finite collection of rewards, whereas we retain only the maximizing actions but allow every reward in the chosen class. The two settings therefore make different assumptions: their data are numerically richer, while our set of rewards is larger. Grimm et al. [5] compare models through their Bellman updates on selected functions and policies. Richens et al. [8] study when policies for sufficiently rich goals contain enough information to recover a world model. Earlier notions of MDP equivalence similarly ask which changes to a model preserve quantities relevant to decision making [3]. Work on reward invariance instead holds the transition model fixed and asks which changes to the reward preserve behaviour [4, 6, 7]. Here the reward is held fixed while the transition kernel is varied. 2. Discounted Markov decision processes 2.1.

The model

Let S = {1, . . . , n} be a finite set of labelled states. At state s, the available labelled actions form a finite nonempty set A(s). For every state and action, Ps,a := P (· | s, a) is a row vector of transition probabilities. Thus Ps,a (x) ≥ 0 and Ps,a 1 = 1, where 1 is the all-ones column vector. We identify a function on S with a column vector in Rn , and es denotes the sth standard basis column vector. Fix a discount factor γ ∈ (0, 1). A stationary deterministic policy π chooses one action π(s) ∈ A(s) at each state. The matrix P π has row Ps,π(s) at state s. A state–action reward is simply a collection of real numbers r(s, a), one for each available pair. Write rπ (s) = r(s, π(s)). The value of policy π is "∞ # X π t VP,r (s) := EP,π γ r(St , At ) S0 = s . t=0

It satisfies π π VP,r = rπ + γP π VP,r ,

π VP,r = (I − γP π )−1 rπ .

(5) 2

Discounted Markov decision processes

The inverse exists because P π is stochastic and γ ∈ (0, 1). The optimal value is the unique vector satisfying ∗ ∗ VP,r (s) = max {r(s, a) + γPs,a VP,r }.

(6)

∗ OptP,r (s) := arg max{r(s, a) + γPs,a VP,r }

(7)

a∈A(s)

We write a∈A(s)

for the set of optimal actions at state s. A deterministic policy is optimal exactly when it chooses an action in this set at every state [1]. For later use, the advantage of action a relative to a policy π is π π AπP,r (s, a) := r(s, a) + γPs,a VP,r − VP,r (s).

(8)

It is the gain from taking a once and then continuing with π, relative to following π immediately. 2.2.

Equivalence under different reward models

We use three direct notions, one for each reward model. Definition 2.1. Let P and Q be transition kernels on the same labelled state space S, with the same labelled action sets A(s) and the same discount factor γ. (i) P and Q are state–action equivalent, written P ≡sa Q, if OptP,r (s) = OptQ,r (s) for every state–action reward r(s, a) and every state s ∈ S. (ii) P and Q are state-reward equivalent, written P ≡s Q, if OptP,r (s) = OptQ,r (s) for every state reward r(s) and every state s ∈ S. (iii) P and Q are transition-reward equivalent, written P ≡tr Q, if OptP,r (s) = OptQ,r (s) for every transition-dependent reward r(s, a, s′ ) and every state s ∈ S. The state and action labels are fixed throughout. Thus the equalities above are equalities of the actual subsets of A(s), not equalities up to a relabeling of states or actions. 3. State{action rewards

We begin with rewards of the form r(s, a). Suppose we know, for every such reward, which actions are optimal under a transition kernel. The main result of this section asks exactly how much of the kernel is determined by this information. The upcoming necessity argument uses the rewards rvP (s, a) = v(s) − γPs,a v, which prescribe an arbitrary optimal value v while making every action optimal. Comparing the resulting policy-evaluation equations under P and Q forces one matrix L to work for every deterministic policy. Appendix A shows that the same classification is already determined by rewards having a unique optimal action at every state. For any v ∈ Rn , define rvP (s, a) := v(s) − γPs,a v. (9) This reward cancels the expected continuation term. Hence rvP (s, a) + γPs,a v = v(s) for every action at every state. 3

State–action rewards

Lemma 3.1. For the reward rvP , the optimal value under P is v, and every action is optimal at every state. Conversely, if a reward makes every action optimal under P and has optimal value v, then it must equal rvP . Proof. Let (T u)(s) := max {rvP (s, a) + γPs,a u} a∈A(s)

be the optimality operator for this reward. Substituting u = v gives (T v)(s) = max v(s) = v(s), a∈A(s)

and every action attains the maximum. It remains to know that this fixed point is the optimal value. For any u, z ∈ Rn , |(T u)(s) − (T z)(s)| ≤ max γ|Ps,a (u − z)| a∈A(s)

≤ γ∥u − z∥∞ . ∗ Thus T is a contraction with modulus γ < 1 and has a unique fixed point. Therefore VP,r P = v. v Conversely, suppose every action is optimal and the optimal value is v. Then every action attains equality in (6), so

v(s) = r(s, a) + γPs,a v for every s and a ∈ A(s). Rearranging gives (9).

□

The next lemma proves that one matrix L relates the values under P and Q, and that the same matrix works for every deterministic policy. Lemma 3.2. Assume P ≡sa Q. Then there is a unique invertible matrix L such that L1 = 1 and (I − γQπ )L = I − γP π

(10)

for every deterministic policy π. Equivalently, Qs,a L = Ps,a + γ1 eT s (L − I)

(11)

for every state s and action a ∈ A(s). Proof. Fix v ∈ Rn . By Lemma 3.1 every action is optimal under P for the reward rvP , so by P ≡sa Q every ∗ action is optimal under Q as well. Write w(v) := VQ,r P . Every deterministic policy therefore selects an v optimal action at every state under Q, hence is optimal, so for every such π, w(v) = rvP,π + γQπ w(v),

rvP,π (s) := rvP (s, π(s)).

By (9), rvP,π = v − γP π v = (I − γP π )v, so (I − γQπ )w(v) = (I − γP π )v

(12)

for every deterministic policy π and every v ∈ Rn . Fix one policy π0 and set L := (I − γQπ0 )−1 (I − γP π0 ), which is invertible as a product of invertible matrices. Taking π = π0 in (12) gives w(v) = Lv, and substituting this back into (12) for arbitrary π gives (I − γQπ )Lv = (I − γP π )v

(v ∈ Rn ),

which is (10). Since P π 1 = Qπ 1 = 1, applying (10) to 1 gives (I − γQπ )L1 = (I − γP π )1 = (1 − γ)1 = (I − γQπ )1, so L1 = 1 by invertibility of I − γQπ . For (11), fix s ∈ S and a ∈ A(s) and choose π with π(s) = a. The sth row of (10) reads T eT s L − γQs,a L = es − γPs,a ,

which rearranges to Qs,a L = Ps,a + γ1 eT s (L − I). For uniqueness, suppose M also satisfies (I − γQπ )M = I − γP π for every deterministic policy π. Fixing any one such policy gives (I − γQπ )(L − M ) = 0, so L = M . In particular, L does not depend on the choice of π0 . □ 4

State–action rewards

Let G be the subgroup G := {L ∈ GLn (R) : L1 = 1}. For L ∈ G, define   −1 ΦL (P )s,a := Ps,a + γ1 eT . s (L − I) L

(13)

Every row in (13) sums to one because L−1 1 = 1. It is a transition kernel when all entries are nonnegative. The transformation preserves the numbers used to compare actions, after values are changed by L. Lemma 3.3. Let Q = ΦL (P ) for some L ∈ G, and suppose Q is a transition kernel. Then, for every state–action reward r, every v ∈ Rn , and every (s, a), r(s, a) + γQs,a Lv − (Lv)(s) = r(s, a) + γPs,a v − v(s).

(14)

(I − γQπ )L = I − γP π

(15)

Moreover, for every deterministic policy π. Proof. Multiplying (13) by L gives γQs,a L = γPs,a + eT s (L − I). Therefore T r(s, a) + γQs,a Lv − (Lv)(s) = r(s, a) + γPs,a v + eT s (L − I)v − es Lv

= r(s, a) + γPs,a v − v(s), which proves (14). Selecting the row corresponding to π(s) at each state gives (15).

□

Theorem 3.4. Let P and Q be transition kernels on the same labelled states and actions, with the same discount factor. The following are equivalent. (i) P ≡sa Q. (ii) For every deterministic policy π, every state–action reward r, every state s, and every action a ∈ A(s), AπQ,r (s, a) = AπP,r (s, a). (iii) There exists L ∈ G such that Q = ΦL (P ). The matrix L is unique. When these conditions hold, (I − γQπ )L = I − γP π , π π VQ,r = LVP,r , ∗ ∗ VQ,r = LVP,r .

(16) (17) (18)

Proof. Assume first that (i) holds. Lemma 3.2 gives a unique L ∈ G satisfying (I − γQπ )L = I − γP π for every deterministic policy π. Reading this identity row by row gives Q = ΦL (P ), so (iii) holds. Now assume (iii). Lemma 3.3 gives (16). For a fixed policy π and reward r, π π (I − γQπ )LVP,r = (I − γP π )VP,r = rπ . π The solution of (I − γQπ )u = rπ is unique, so (17) holds. Applying (14) with v = VP,r gives

AπQ,r (s, a) = AπP,r (s, a), which proves (ii). It remains to prove that (ii) implies (i). Fix a reward r, a state s, and an action a ∈ OptP,r (s). Choose a deterministic policy π with π(s) = a and π(t) ∈ OptP,r (t) at every other state t. This policy is optimal under P , so AπP,r (t, c) ≤ 0 (t ∈ S, c ∈ A(t)). By (ii), the same inequalities hold under Q, so π is optimal under Q. In particular, a = π(s) is optimal at s under Q. Hence OptP,r (s) ⊆ OptQ,r (s). Interchanging P and Q gives the reverse inclusion, proving (i). ∗ Finally, let v = VP,r and w = Lv. By (14), r(s, a) + γQs,a w − w(s) = r(s, a) + γPs,a v − v(s). The right-hand side is nonpositive for every action and is zero for at least one action at each state. Thus w satisfies the optimality equation under Q, proving (18). □ 5

State–action rewards

Corollary 3.5. The kernels that are state–action equivalent to P are exactly [P ]sa = {ΦL (P ) : L ∈ G, ΦL (P ) is a transition kernel}.

(19)

The matrix L is unique. Given P and Q, it may be recovered from any deterministic policy π by L = (I − γQπ )−1 (I − γP π ).

(20)

Thus membership in the equivalence class can be checked by computing this L, verifying L1 = 1, and checking (11) for every state and action. Proof. The set identity is Theorem 3.4. Rearranging (16) gives (20). Uniqueness was proved in Lemma 3.2.

□

As L varies, the set in (19) is the orbit of P under the transformations ΦL ; the word “orbit” refers only to this set of transformed kernels. The theorem also gives two useful identities not involving a reward. If a, b ∈ A(s), then (Qs,a − Qs,b )L = Ps,a − Ps,b .

(21)

For every deterministic policy π, det(I − γP π ) = det L. det(I − γQπ ) In particular, the determinant ratio is independent of the policy. 3.1.

(22)

Local geometry of the equivalence class

Each transition row Ps,a has n entries subject to the single constraint Ps,a 1 = 1. Thus each row has n − 1 free parameters. Since there is one transition row for every available state–action pair, the ambient space of transition kernels with the fixed states and actions has dimension X D = (n − 1) |A(s)|. (23) s∈S

The next result describes the local structure of [P ]sa : its dimension and the directions in which P may be varied while remaining in the same equivalence class. Proposition 3.6. Suppose every transition probability P (x | s, a) is strictly positive. Then, in a neighbourhood of P , the equivalence class [P ]sa is a smooth embedded manifold of dimension n(n − 1). Its tangent space at P is  TP [P ]sa =

Ṗ : Ṗs,a =

1 T e H − Ps,a H, γ s

 H1 = 0 .

(24)

Proof. The condition L1 = 1 imposes n independent linear equations on the n2 entries of L. Hence G is a smooth manifold of dimension n2 − n = n(n − 1). Consider the map FP (L) := ΦL (P ). It is continuous and satisfies FP (I) = P . Since every entry of P is positive, sufficiently small changes of L leave every entry of FP (L) positive. Thus, near the identity, FP takes values in the space of transition kernels. The map is injective near the identity, and in fact globally wherever its image is a transition kernel. If FP (L) = FP (M ) = Q, then, for any fixed deterministic policy π, (I − γQπ )L = I − γP π = (I − γQπ )M. Since I − γQπ is invertible, L = M . Moreover, the inverse on the image is given by the smooth formula Q 7−→ (I − γQπ )−1 (I − γP π ). Therefore the image near P is a smooth embedded manifold with the same dimension as G. To compute its tangent space, let L(ε) = I + εH + O(ε2 ),

H1 = 0. 6

State–action rewards

Then L(ε)−1 = I − εH + O(ε2 ). Substituting into (13) gives 


ε T 2 ΦL(ε) (P )s,a = Ps,a + es H + O(ε ) I − εH + O(ε2 ) γ   1 T e H − Ps,a H + O(ε2 ). = Ps,a + ε γ s The coefficient of ε gives the tangent vectors in (24).

□

Corollary 3.7. Suppose the assumptions of Proposition 3.6 hold and every state has exactly m actions. Then the ambient kernel space has dimension mn(n − 1), whereas [P ]sa has local dimension n(n − 1). Proof. When |A(s)| = m for every s, equation (23) gives X D = (n − 1) m = mn(n − 1). s∈S

The remaining statements follow from Proposition 3.6.

□

Remark 3.8. Corollary 3.7 shows that the ratio of the local dimension of [P ]sa to the dimension of the ambient kernel space is n(n − 1) 1 = . mn(n − 1) m Thus state–action equivalence becomes increasingly restrictive as the number of available actions grows. Each additional action introduces further action comparisons that must be preserved for two kernels to remain in the same equivalence class. Consequently, although distinct kernels may still produce exactly the same optimal-action data, the equivalence class becomes progressively smaller relative to the ambient kernel space as m increases. This is a local geometric statement; it does not mean that the observations retain a literal fraction 1/m of the statistical information about the kernel. Example 3.9. Let S = {0, 1}, let both states have actions a, b, and take γ = 4/5. Set   11/10 −1/10 L= , L1 = 1. 1/5 4/5 Define P and Q by P (· | 0, ·) P (· | 1, ·)

a (13/20, 7/20) (11/20, 9/20)

b (7/20, 13/20) (1/4, 3/4)

Q(· | 0, ·) Q(· | 1, ·)

a (23/36, 13/36) (2/3, 1/3)

b (11/36, 25/36) (1/3, 2/3).

Direct substitution gives Q = ΦL (P ). Hence P = ̸ Q, but the two kernels have the same optimal actions for every state–action reward. 4. Transition-dependent rewards

A transition-dependent reward assigns a number r(s, a, x) when action a at state s leads to the next state x. Under a kernel P , it induces the state–action reward X r̄P (s, a) := P (x | s, a)r(s, a, x). (25) x∈S

Thus the same transition-dependent reward r may induce different state–action rewards under different transition kernels. This makes an individual transition row easy to test when a second action is available at the same state. If Ps,a ̸= Qs,a , one can choose r(s, a, ·) to have expectation zero under one row and nonzero under the other, and compare action a with another action at s. The only case requiring care is a state with one action. There is no comparison at that state, although its row may still affect choices elsewhere through the continuation value. We use the following elementary fact. 7

Transition-dependent rewards

Lemma 4.1. For a fixed kernel K, the state rewards for which every action is optimal at every state form a vector subspace of Rn . If z is such a reward, then for every state–action reward r, (s ∈ S),

OptK,r+z (s) = OptK,r (s) where (r + z)(s, a) = r(s, a) + z(s).

∗ Proof. Suppose every action is optimal for state rewards z1 , . . . , zm , and write wi = VK,z . Then i

wi (s) = zi (s) + γKs,a wi

(s ∈ S, a ∈ A(s)).

For scalars c1 , . . . , cm , the vectors z=

X

ci zi ,

w=

i

X

ci wi

i

satisfy the same identity, so every action is optimal for z. This proves the vector-space statement. ∗ Now let v = VK,r . For every state and action, r(s, a) + z(s) + γKs,a (v + w) = r(s, a) + γKs,a v + w(s). The maximizing actions are therefore unchanged, and v + w is the optimal value for r + z.

□

Let U := {s ∈ S : |A(s)| = 1}, and write au for the unique action at u ∈ U . For u ∈ U , let eu denote the state reward ( 1, s = u, eu (s) = 0, s ̸= u. Thus eu rewards each visit to u. Theorem 4.2. Let P and Q be transition kernels on the same labelled states and actions. Then P ≡tr Q if and only if: (i) P ≡sa Q; (ii) Ps,a = Qs,a whenever |A(s)| ≥ 2; (iii) if u ∈ U and Pu,au ̸= Qu,au , then every action is optimal at every state under P for the state reward eu . Under (i), the last condition is unchanged if P is replaced by Q. Proof. Assume first that P ≡tr Q. Every state–action reward ρ(s, a) is the transition reward r(s, a, s′ ) = ρ(s, a), so P ≡sa Q. Suppose that Ps,a = ̸ Qs,a at a state with at least two actions. Write p = Ps,a and q = Qs,a . Since p and q are distinct probability rows, there is an h ∈ Rn such that ph = 0,

qh = 1.

Choose b ∈ A(s) \ {a}, and set r(s, a, x) = h(x),

r(t, c, x) = 0

when (t, c) ̸= (s, a).

Under P , the expected immediate reward is zero for every state and action, so every action is optimal. Under Q, a policy choosing b at s receives zero reward everywhere and therefore has value zero. If every action were optimal under Q, then this policy would be optimal. However, at state s, taking action a gives immediate expected reward 1, whereas taking action b gives immediate expected reward 0. Hence a is strictly better than b at s, a contradiction. Therefore the rows must agree at every state with at least two actions. Now let u ∈ U and suppose Pu,au ̸= Qu,au . Choose h as above and support r only on (u, au ). Its expected reward is zero under P and is the state reward eu under Q. Transition-reward equivalence therefore implies that every action is optimal under Q for eu . Since P ≡sa Q, the same is true under P . Conversely, assume (i)–(iii), and fix a transition reward r. Put ρ(s, a) = r̄P (s, a),

d(s, a) = r̄Q (s, a) − r̄P (s, a).

By (ii), d(s, a) = 0 at every state with at least two actions. It also vanishes at a one-action state whose row is the same under P and Q. Hence X d= cu e u , D := {u ∈ U : Pu,au ̸= Qu,au }, u∈D

8

Transition-dependent rewards

for suitable scalars cu , where state rewards are identified with state–action rewards constant across the available actions. By (i) and (iii), every action is optimal under Q for each eu with u ∈ D. Lemma 4.1 therefore gives OptQ,ρ+d = OptQ,ρ . Using P ≡sa Q, OptP,r = OptP,ρ = OptQ,ρ = OptQ,ρ+d = OptQ,r . Thus P ≡tr Q.

□

Condition (iii) can be checked directly. Fix any deterministic policy π, and for u ∈ U set hu := (I − γP π )−1 eu .

(26)

Then every action is optimal for the state reward eu if and only if (Ps,a − Ps,b )hu = 0

(s ∈ S, a, b ∈ A(s)).

(27)

Indeed, hu is the value of π for the reward eu , and the displayed condition says that replacing π(s) by any other action leaves the value unchanged. Corollary 4.3. Suppose that for every u ∈ U , the state reward eu makes some action non-optimal at some state. Then transition-dependent rewards determine P exactly. In particular, exact identification holds when every state has at least two actions. Proof. Let Q ≡tr P . By Theorem 4.2(ii), P and Q agree at every state with at least two actions. If they differed at some u ∈ U , condition (iii) would imply that every action is optimal for the reward eu , contrary to the hypothesis. Hence every row agrees and P = Q. When every state has at least two actions, U is empty. □ Proposition 4.4. Suppose n ≥ 2 and at least one state has at least two actions. Among strictly positive transition kernels, the kernels not identified by all transition-dependent rewards lie in a set of Lebesgue measure zero in the usual coordinates on the kernel space. Proof. Fix a state s0 with distinct actions a, b, and fix a deterministic policy π with π(s0 ) = b. For a singleton-action state u, set fu (P ) := (Ps0 ,a − Ps0 ,b )(I − γP π )−1 eu . If the reward eu makes every action optimal, then fu (P ) = 0 by (27). Multiplying by det(I − γP π ) writes fu as a polynomial divided by a nonzero denominator. The numerator polynomial is not identically zero. To see this, choose P so that every row of P π is uniform on S. In particular, Ps0 ,b is the uniform row. For some v ̸= u, take T Ps0 ,a = Ps0 ,b + δ(eT u − ev )

with δ > 0 small. Then the kernel is strictly positive and (I − γP π )−1 eu = eu +

γ 1, n(1 − γ)

so fu (P ) = δ ̸= 0. Hence the condition fu (P ) = 0 holds on a measure-zero set. If P is not identified by all transition-dependent rewards, then by Corollary 4.3 there is some u ∈ U for which eu makes every action optimal. For this u, (27) implies fu (P ) = 0. Hence the kernels that are not identified lie in the finite union [ {P : fu (P ) = 0}. u∈U

Each set in this union has measure zero, so the union has measure zero.

□

Example 4.5. Let S = {0, 1},

A(0) = {a, b},

A(1) = {c},

and define  P0,a = P0,b = Q0,a = Q0,b =

1 1 , 2 2

 ,

while  P1,c = (1, 0),

Q1,c =

1 1 , 2 2

 . 9

Transition-dependent rewards

a, b : 12

Kernel P

a, b : 12

a, b : 21

Kernel Q

c : 12

a, b : 12

0

1

0

c:1

1 c : 12

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 state 0 behave in exactly the same way. 5. State rewards

We now consider rewards of the form r : S → R, so the reward depends only on the current state. The optimal value function satisfies ∗ ∗ VP,r (s) = r(s) + γ max Ps,a VP,r . a∈A(s)

It is enough to consider deterministic stationary policies. Indeed, every finite discounted MDP has an optimal policy of this form, and a deterministic stationary policy is optimal exactly when it chooses an optimal action at every state. For a deterministic stationary policy π, let P π be the transition matrix whose s-th row is Ps,π(s) . Its value function is π VP,r = (I − γP π )−1 r. Define  RP (π) := r ∈ Rn : (Ps,π(s) − Ps,a )(I − γP π )−1 r ≥ 0 for every s ∈ S, a ∈ A(s) . Thus RP (π) is the set of state rewards for which π is optimal under P . Such policy regions for discounted MDPs go back to Smallwood [2]. Lemma 5.1. A deterministic stationary policy π is optimal under the state reward r if and only if r ∈ RP (π). Proof. The policy π is optimal if and only if, at every state, its chosen action is at least as good as every other action. Thus π π r(s) + γPs,π(s) VP,r ≥ r(s) + γPs,a VP,r for every s ∈ S and a ∈ A(s). Cancelling r(s) and using π VP,r = (I − γP π )−1 r

gives (Ps,π(s) − Ps,a )(I − γP π )−1 r ≥ 0. These are precisely the inequalities defining RP (π).

□

Theorem 5.2. Let P and Q be transition kernels on the same labelled state and action spaces. Then P ≡s Q if and only if RP (π) = RQ (π) for every deterministic stationary policy π. Proof. Suppose first that P ≡s Q. A deterministic stationary policy is optimal exactly when it chooses an optimal action at every state. Since P and Q have the same optimal-action sets for every state reward, they have the same optimal deterministic stationary policies. Lemma 5.1 therefore gives RP (π) = RQ (π) for every π. 10

State rewards

Conversely, suppose that RP (π) = RQ (π) for every deterministic stationary policy π. By Lemma 5.1, P and Q have the same optimal deterministic stationary policies for every state reward. Fix r ∈ Rn , s ∈ S, and a ∈ A(s). The action a is optimal at s under P if and only if there is an optimal deterministic stationary policy π such that π(s) = a. Indeed, one may choose a at s and choose any optimal action at each other state. Since the optimal deterministic stationary policies are the same under P and Q, it follows that a is optimal at s under P if and only if it is optimal at s under Q. Hence OptP,r (s) = OptQ,r (s) for every r and s, so P ≡s Q. □ The theorem gives a finite classification. There are only finitely many deterministic stationary policies, and for each policy π, the set RP (π) is determined by finitely many linear inequalities in r. Corollary 5.3. If P ≡sa Q, then P ≡s Q. Proof. Every state reward r : S → R can be regarded as the state–action reward re(s, a) := r(s). Thus equality of the optimal-action sets for every state–action reward implies equality for every state reward. □ The converse does not hold. Example 5.4. State-reward equivalence is strictly weaker than state–action equivalence, even with two states, two actions, and strictly positive transition probabilities. Let S = {0, 1}, A(0) = A(1) = {a, b}, and define 1 P = 10



8 7

 2 , 3

1 P = 10

 4 5

 6 , 5

1 Q = 10



6 8

 4 , 2

1 Q = 10

 5 5

 5 . 5

a

b

and a

b

We first show that P ≡s Q. Let R denote either P or Q, and let ∗ ∗ dR := VR,r (1) − VR,r (0).

For both kernels and at both states, action b has a larger probability of moving to state 1 than action a. Therefore, if dR > 0, action b is uniquely optimal at both states; if dR < 0, action a is uniquely optimal at both states; and if dR = 0, both actions are optimal. Suppose that dR > 0. Since action b is then optimal at both states, the optimality identities at states 1 and 0 give
dR = r(1) − r(0) + γ R(1 | 1, b) − R(1 | 0, b) dR . Hence

r(1) − r(0)
. 1 − γ R(1 | 1, b) − R(1 | 0, b) The denominator is strictly positive, so dR > 0 implies dR =

r(1) > r(0). 11

State rewards

Similarly, if dR < 0, action a is optimal at both states, and the optimality identities give dR =

r(1) − r(0)
. 1 − γ R(1 | 1, a) − R(1 | 0, a)

Again the denominator is strictly positive, so dR < 0 implies r(1) < r(0). Finally, if dR = 0, the optimality identities at the two states give r(1) = r(0). It follows that
sgn(dR ) = sgn r(1) − r(0) . Consequently, for both P and Q,   {b}, r(1) > r(0),    OptR,r (s) = {a}, r(1) < r(0),     {a, b}, r(1) = r(0), at both states. Hence P ≡s Q. We now show that P ̸≡sa Q. If P ≡sa Q, then by the state–action classification there would be an invertible matrix L satisfying L1 = 1 and (Qs,b − Qs,a )L = Ps,b − Ps,a for both states s. Let u = (−1, 1). The action differences are P0,b − P0,a =

4 u, 10

P1,b − P1,a =

2 u, 10

Q0,b − Q0,a =

1 u, 10

Q1,b − Q1,a =

3 u. 10

whereas Since L1 = 1,

(uL)1 = u1 = 0. 2

The zero-sum subspace of R is spanned by u, so uL = λu for some λ ∈ R. The identity at state 0 would then give 1 4 λu = u, 10 10 and hence λ = 4. The identity at state 1 would give 3 2 λu = u, 10 10 and hence λ=

2 . 3

This is impossible. Therefore P ̸≡sa Q. Thus P ≡s Q

but

P ̸≡sa Q. 12

Conclusion

Corollary 5.5. The three notions of equivalence satisfy P ≡tr Q

=⇒

P ≡sa Q

=⇒

P ≡s Q,

and neither implication can be reversed. Proof. The first implication follows from Theorem 4.2, and the second is Corollary 5.3. Example 3.9 shows that state–action equivalence does not imply transition-reward equivalence, while Example 5.4 shows that state-reward equivalence does not imply state–action equivalence. □ 6. Limitations and open problems All rewards are still required

Corollary A.2 shows that rewards with several optimal actions are not needed, but the classification still assumes access to the unique optimal actions over all state–action rewards. Ordinary data may contain only one selected action on visited states and only a finite collection of tasks. Determining how much of the equivalence class can be removed by a finite or adaptively chosen set of rewards remains open. Restricted reward classes

If rewards are restricted to rθ (s, a) = ⟨ϕ(s, a), θ⟩, the remaining ambiguity should depend on which policy action gaps can be generated by the feature vectors. A finite-reward or rank condition would connect the exact classification here with the design of informative tasks. Approximate observations

The equivalence notions in this paper are exact. A quantitative extension would ask how close a kernel must be to the family (19) when action gaps or optimal-action regions agree only approximately. This would turn the classification into stability bounds for noisy values, finite reward samples, or approximately optimal actions. A direct parameterization for state rewards

Theorem 5.2 gives a finite exact test for state-reward equivalence, but not a direct parameterization of all equivalent kernels. Finding a description comparable to (19) remains open. 7. Conclusion

Knowing which actions are optimal does not usually determine the transition kernel. Nevertheless, when the optimal actions are known for every reward, they reveal more than a single choice might suggest. For state–action rewards, they determine every comparison between actions under every deterministic policy. Two kernels can therefore agree on all optimal actions only if they also agree on how much better one action is than another. Even this does not determine the kernel itself. The remaining kernels are described exactly by the matrix transformation (3), and near a strictly positive kernel they form a family of dimension n(n − 1). Rewards with a unique optimal action at every state already determine this same family. The amount that can be recovered changes with the reward. State rewards may leave substantially different kernels indistinguishable. State–action rewards determine all action comparisons but still leave a continuous ambiguity in the dynamics. Transition-dependent rewards can test successor states directly and, except for a precisely described obstruction at states with one action, recover the transition kernel itself. The results separate two questions that are often treated as one. A model may contain enough information to choose the same actions for a given class of rewards without giving the correct probabilities of what happens next. That may be sufficient when the only aim is to reproduce those decisions. It is not sufficient for predicting transitions, simulating the process, evaluating counterfactual actions, or transferring to rewards outside the observed class.

13

Appendix: Supplementary Results

A. Supplementary results A.1.

Unique optimal actions suffice

The purpose of this subsection is to show that rewards with several optimal actions are not needed for the state–action classification. It is enough to know the uniquely optimal action at every state for every reward for which such an action exists. The reason is geometric. For a deterministic policy π, let  UP (π) := r : OptP,r (s) = {π(s)} for every s ∈ S . Thus UP (π) is the set of state–action rewards for which π is the unique optimal deterministic policy. Lemma A.1. The closure of UP (π) is the set of rewards for which π is optimal under P . Proof. Optimality of a fixed policy is given by the closed inequalities AπP,r (s, a) ≤ 0

(s ∈ S, a ∈ A(s)).

Since policy values, and hence advantages, depend continuously on r, any limit of rewards in UP (π) makes π optimal. Conversely, suppose π is optimal for r, and for ε > 0 define rε (s, a) := r(s, a) + ε1{a=π(s)} . Following π receives the additional reward ε at every time step, so ε 1. 1−γ

π π VP,r = VP,r + ε

For a ̸= π(s), using Ps,a 1 = 1,  π AπP,rε (s, a) = r(s, a) + γPs,a VP,r +

   ε ε π 1 − VP,r (s) + 1−γ 1−γ

= AπP,r (s, a) − ε < 0. Hence π(s) is the unique optimal action at every state under rε , so rε ∈ UP (π). Since rε → r, the result follows. □ Corollary A.2. The following are equivalent: (i) P ≡sa Q; (ii) UP (π) = UQ (π) for every deterministic policy π. Proof. The forward implication is immediate. For the converse, suppose UP (π) = UQ (π) for every deterministic policy π. Taking closures gives UP (π) = UQ (π). By Lemma A.1, these closures are precisely the sets of rewards for which π is optimal under P and Q, respectively. Thus each deterministic policy is optimal for exactly the same rewards under the two kernels. An action is optimal at a state if and only if it is selected there by some optimal deterministic policy, so P ≡sa Q. □ A.2.

Composition Laws

Proposition A.3. For all L, M ∈ G for which the expressions below are transition kernels, ΦI (P ) = P,

ΦM (ΦL (P )) = ΦM L (P ),

ΦL−1 (ΦL (P )) = P.

Proof. Rewrite (13) as ΦL (P )s,a = Ps,a L−1 +

1 T e (I − L−1 ). γ s 14

Appendix: Supplementary Results

Then 1 T e (I − M −1 ) γ s
1 −1 = Ps,a L−1 M −1 + eT )M −1 + I − M −1 s (I − L γ
1 T −1 = Ps,a (M L) + es I − (M L)−1 γ = ΦM L (P )s,a .

ΦM (ΦL (P ))s,a = ΦL (P )s,a M −1 +

The identity and inverse formulas follow by setting L = I and M = L−1 .

□

References [1] M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley, 1994. [2] R. D. Smallwood. Optimum policy regions for Markov processes with discounting. Operations Research, 14(4):658–669, 1966. [3] R. Givan, T. Dean, and M. Greig. Equivalence notions and model minimization in Markov decision processes. Artificial Intelligence, 147(1–2):163–223, 2003. [4] A. Y. Ng, D. Harada, and S. Russell. Policy invariance under reward transformations: Theory and application to reward shaping. In Proceedings of the 16th International Conference on Machine Learning, pages 278–287, 1999. [5] C. Grimm, A. Barreto, S. Singh, and D. Silver. The value equivalence principle for model-based reinforcement learning. In Advances in Neural Information Processing Systems, volume 33, 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. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of PMLR, pages 32033–32058, 2023. [7] 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. [8] J. Richens, D. Abel, A. Bellot, and T. Everitt. General agents contain world models. arXiv:2506.01622, 2025. [9] 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. [10] A. Y. Ng and S. Russell. Algorithms for inverse reinforcement learning. In Proceedings of the 17th International Conference on Machine Learning, pages 663–670, 2000. [11] Z. Ghatrani and A. Ghate. Inverse Markov decision processes with unknown transition probabilities. IISE Transactions, 55(6):588– 601, 2023. [12] H. Cao, S. Cohen, and L. Szpruch. Identifiability in inverse reinforcement learning. In Advances in Neural Information Processing Systems, volume 34, pages 12362–12373, 2021. [13] K. Kim, S. Garg, K. Shiragur, and S. Ermon. Reward identification in inverse reinforcement learning. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 5496–5505, 2021. [14] N. Ferns, P. Panangaden, and D. Precup. Metrics for finite Markov decision processes. In Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence, pages 162–169, 2004.

15

Related documents

• Learning Chance-Constrained MDPs with Bellman Distributional Certificates#1105415
• Voight-Kampff Machine v2#86904
• Official Review · ICLR 2026#787012
• Limit-sure reachability for small memory policies in POMDPs is NP-complete#1066571
• MISSing the World. Models as Isolations and Credible Surrogate Systems#754275