{"id":"b7e50dcb-55be-4031-b4ad-0f1da125d3f5","arxiv_id":"2608.07301","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":1,"one_line_summary":"For finite discounted MDPs, optimal actions under all state-action rewards identify transitions only up to an n(n-1)-dimensional matrix orbit, while transition-dependent rewards identify almost every strictly positive kernel exactly.","lead":"Knowing which action is optimal in every situation does not reveal the probabilities of what happens next. This paper proves exactly which hidden transition tables are indistinguishable, and shows that rewards involving the next state usually expose the true table.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Oracle over all rewards is the load-bearing idealization; with finite or parametric reward sets the equivalence class can be strictly larger, as Section 6 concedes.","rationale":"The paper is a clean mathematical contribution: Theorems 3.4 and 4.2 are proved rigorously, the transformation Φ_L is correctly derived, and the local geometry (Prop 3.6) is sound. I re-derived the key identities (10)-(15) and the construction of L in Lemma 3.2; no algebraic or logical gap was found. The only substantive limitation is the all-rewards oracle. The reader's weakest_assumption identifies this same point. Because the paper transparently labels it as an open limitation rather than a hidden assumption, it does not undermine the theorems as stated. The proposed experiment would make the boundary quantitative and is the natural next step toward practical finite-task identifiability. Thus the reader's ACCEPT stands unchanged.","tokens_in":12688,"tokens_out":16657,"duration_ms":147045,"concrete_test":"For a 2-state, 2-action MDP with γ=0.9 and a fixed strictly positive kernel P, enumerate a finite reward set R of, say, 20 randomly sampled state-action rewards. Compute the set of kernels Q that match P's optimal-action sets on every r∈R (using linear feasibility in Q-row variables). Compare this set with the orbit {Φ_L(P): L∈G, Φ_L(P)≥0, row-stochastic}. If the finite-reward equivalence class strictly contains the orbit, the oracle assumption is essential. The same check can be run with a one-dimensional feature class r_θ(s,a)=θ φ(s,a).","verdict_should_be":"UNCHANGED","load_bearing_attack":"The classification in Theorem 3.4 quantifies over every state-action reward. The necessity direction (Lemma 3.2) uses rewards r^P_v(s,a)=v(s)-γP_{s,a}v that are defined in terms of the unknown kernel P; the proof is valid only because the observation oracle is assumed to answer for all rewards, including these model-dependent ones. If instead one observes optimal actions for a finite collection of tasks, or for rewards from a feature class r_θ=⟨φ(s,a),θ⟩, the equivalence class can be strictly larger than the Φ_L(P) orbit. The paper states this limitation explicitly in Section 6 ('All rewards are still required', 'Restricted reward classes') and leaves the finite-reward case open. This is not an internal inconsistency, but it marks the boundary of the central claim: the 'optimal actions alone' in real applications are finite samples, not an all-rewards oracle.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":12876,"tokens_out":21691,"duration_ms":184994,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"§3.1, Proposition 3.6"},{"comment":"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.","section":"Theorem 4.2"},{"comment":"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.","section":"Example 3.9 / Corollary 5.5"},{"comment":"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.","section":"Abstract / Section 6"},{"comment":"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.","section":"Throughout"}],"recommendation":"minor_revision","confidential_remarks":"The manuscript is within the journal's scope and I do not see a novelty or attribution problem. The all-rewards oracle is fully disclosed, and the finite-data extension is left as open work; the recommendation of minor revision reflects only local presentation issues."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nThe 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.\n\nOverall: 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.","headline":"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.","tokens_in":13381,"tokens_out":2837,"would_cite":true,"duration_ms":23731,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C40"],"pacs":[],"model":"deepseek-v4-flash","headline":"Knowing only which actions are optimal can hide the true transition probabilities, but next-state rewards reveal almost all of them.","keywords":["Markov decision processes","identifiability","transition kernels","optimal actions","state-action rewards","transition-dependent rewards","equivalence","inverse reinforcement learning"],"falsifier":"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.","tokens_in":12505,"feed_emoji":"🎯","tokens_out":7210,"duration_ms":60795,"temperature":0.7,"pith_summary":"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.","feed_headline":"Next-state rewards pin down almost every MDP kernel","feed_subtitle":"Without successor-state rewards, optimal choices can hide the true dynamics behind an n(n−1)-parameter family.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the standard optimality condition for deterministic stationary policies used throughout the paper.","marker":"[1]"},{"why":"Introduces policy regions for discounted MDPs, which the state-reward equivalence theorem relies on.","marker":"[2]"},{"why":"Earlier equivalence notions for MDPs that this work contrasts with and extends.","marker":"[3]"},{"why":"Value equivalence principle, a related way of comparing models through Bellman updates on selected functions.","marker":"[5]"},{"why":"The inverse problem of recovering dynamics from Q-values, which this paper adapts to the optimal-action observation setting.","marker":"[9]"}],"fun_headline_variants":["Optimal actions can hide the true MDP dynamics","Next-state rewards recover almost all MDP kernels","State-action rewards leave kernels n(n-1)-fold ambiguous","Reward form decides if optimal choices reveal dynamics","From actions alone, kernel identity stays hidden"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Optimal actions can hide the true MDP dynamics","Next-state rewards recover almost all MDP kernels","State-action rewards leave kernels n(n-1)-fold ambiguous","Reward form decides if optimal choices reveal dynamics","From actions alone, kernel identity stays hidden"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00015,"raw_usage":{"total_tokens":1268,"prompt_tokens":1085,"completion_tokens":183,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":701,"completion_tokens_details":{"reasoning_tokens":109}},"tokens_in":701,"tokens_out":183,"duration_ms":2508,"temperature":1.0,"reasoning_tokens":109,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T10:46:14.367657+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the standard optimality condition for deterministic stationary policies used throughout the paper."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces policy regions for discounted MDPs, which the state-reward equivalence theorem relies on."},{"cited_title":"Givan, T","cited_arxiv_id":null,"evidence_quote":"Earlier equivalence notions for MDPs that this work contrasts with and extends."},{"cited_title":"Grimm, A","cited_arxiv_id":null,"evidence_quote":"Value equivalence principle, a related way of comparing models through Bellman updates on selected functions."},{"cited_title":"Inverting the Bellman Equation: From $Q$-Values to World Models","cited_arxiv_id":"2606.21173","evidence_quote":"The inverse problem of recovering dynamics from Q-values, which this paper adapts to the optimal-action observation setting."}],"review_version":1}