TheoremStatement: Literature-sourcedProof: AI-generatedPipeline-generatedjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Feature-reward data do not determine the Bellman error or, at positive discount, its minimizer

Statement

Assume the Axiom of Choice to form the infinite trajectory laws. Fix $0 \leq γ < 1$ . An actionless finite Markov reward process (MRP) here means a nonempty finite state set with a joint probability law for next state and reward at each state. Consider the following two MRPs, each with its stated stationary state-weighting distribution, meaning that one transition leaves the distribution unchanged.

In MRP 1 the state set is ${A, B}$ , with transitions $A \to B$ receiving reward $0$ deterministically and $B \to A$ receiving reward $1$ with probability $1 / 2$ or $B \to B$ receiving reward $- 1$ with probability $1 / 2$ . Its stationary weighting is $μ_{1} (A) = 1 / 3$ , $μ_{1} (B) = 2 / 3$ .

In MRP 2 the state set is ${A, B, B^{'}}$ , with transitions $A \to B$ and $A \to B^{'}$ each receiving reward $0$ with probability $1 / 2$ , $B \to A$ receiving reward $1$ deterministically, and $B^{'} \to B$ or $B^{'} \to B^{'}$ each receiving reward $- 1$ with probability $1 / 2$ . Its stationary weighting is $μ_{2} (A) = μ_{2} (B) = μ_{2} (B^{'}) = 1 / 3$ .

In both processes the observed feature is $ψ (A) = (1, 0)$ and $ψ (B) = ψ (B^{'}) = (0, 1)$ , so a parameter $w = (a, b)^{T}$ assigns values $v_{w} (A) = a$ and $v_{w} (B) = v_{w} (B^{'}) = b$ . Starting from the stated stationary weighting, the two processes induce the same probability law on the observed feature/reward sequence $((ψ (S_{n}), R_{n + 1}))_{n \geq 0}$ . Their mean square Bellman errors, defined as the stationary-weighted square of the conditional expected one-step TD error, are

\begin{aligned} {BE}_{1} (a, b) & = \frac{1}{3} (γ b - a)^{2} + \frac{2}{3} {(\frac{γ}{2} (a + b) - b)}^{2}, \\ {BE}_{2} (a, b) & = \frac{1}{3} ((γ b - a)^{2} + (1 + γ a - b)^{2} + (- 1 + (γ - 1) b)^{2}) . \end{aligned}

MRP 1 has the unique minimizer $(a, b) = (0, 0)$ and minimum $0$ . With $D = 1 + γ + γ^{2}$ , MRP 2 has the unique minimizer $(a, b) = (- \frac{γ}{D}, \frac{γ}{2 D})$ and minimum $\frac{(γ + 2)^{2}}{6 D}$ ; also ${BE}_{2} (0, 0) = 2 / 3$ . For every $0 < γ < 1$ the minimizing parameters differ. Thus the Bellman-error objective and, for positive discount, its minimizing parameter are not determined by the observable feature/reward sequence law. An MRP here has no action-dependent policy; it is not an unseen-action offline-MDP policy-impossibility claim.

Statement references

The axiom used for the infinite trajectory-law construction.

Finite joint reward-transition laws and their state-transition marginals.

The state-weighted Bellman-error objective as the squared norm of the expected TD-error vector.

The finite discounted policy Bellman operator used for the conditional expected residual.

A finite MDP with a stationary policy has a reward-state path law under Choice.

Uniqueness of a path law with specified finite-prefix kernels under Choice.

Sutton and Barto, Reinforcement Learning: An Introduction, 2nd ed., §11.6.

Hutter, Yang-Zhao, and Majeed, “Conditions on Features for Temporal Difference-Like Methods to Converge,” §§2 and 4.

Facts & Assumptions

Given: The two finite MRPs, their transition/reward laws, stationary weightings, feature map, $0 \leq γ < 1$ , and Choice for the infinite path laws.

[A1]

The Axiom of Choice: every family of nonempty sets has a choice function. This is used only through the path-law suppliers in step 1.2.

[F1]

Finite Markov decision process with joint reward-transition law: a finite joint reward-transition law determines the expected reward $r (s)$ and state-transition probabilities $P (s^{'} ∣ s)$ by finite sums; an MRP can be represented by giving every state a singleton action.

[F2]

State-weighted Bellman error and projected Bellman error and Policy Bellman operator: ${BE}_{μ} (w) = \sum_{s} μ (s) ((T v_{w}) (s) - v_{w} (s))^{2}$ , where $(T v_{w}) (s) = r (s) + γ \sum_{s^{'}} P (s^{'} ∣ s) v_{w} (s^{'})$ for a single-action process.

[F3]

A finite MDP and stationary policy generate a reward-state Markov chain: under Choice, every finite MDP with a nonempty state set and stationary policy has a path law with the prescribed one-step reward-state kernel.

[F4]

Ionescu-Tulcea construction of a Markov chain: under Choice, an initial law and a sequence of transition kernels determine a unique path law with the corresponding finite-prefix laws.

Proof

1.1givenF1algebra

The transition matrices, with states ordered as displayed in the Statement, are $P_{1} = (\begin{array}{cc} 0 & 1 \\ 1 / 2 & 1 / 2 \end{array})$ and $P_{2} = (\begin{array}{ccc} 0 & 1 / 2 & 1 / 2 \\ 1 & 0 & 0 \\ 0 & 1 / 2 & 1 / 2 \end{array})$ . Every row sums to one. Direct multiplication gives $μ_{1} P_{1} = (1 / 3, 2 / 3) = μ_{1}$ and $μ_{2} P_{2} = (1 / 3, 1 / 3, 1 / 3) = μ_{2}$ . The observed feature has mass $1 / 3$ at $A$ and $2 / 3$ at feature $B$ in each process.

1.2givenA1F3F4induction

Represent each MRP as a one-action finite MDP. Under Choice, [F3] supplies a state/reward path law for each fixed initial state; the finite mixture of these laws with weights $μ_{1}$ or $μ_{2}$ gives the stated random initial state. Let $Y_{n} = (ψ (S_{n}), R_{n + 1})$ and set $x_{A} = ((1, 0), 0)$ , $x_{+} = ((0, 1), 1)$ , and $x_{-} = ((0, 1), - 1)$ . In MRP 1, the initial state law and its outgoing rewards give probability $1 / 3$ to each of $x_{A}, x_{+}, x_{-}$ ; MRP 2 gives the same probabilities. In each process the transition kernel of $Y_{n}$ is $x_{A} \mapsto \frac{1}{2} x_{+} + \frac{1}{2} x_{-}$ , $x_{+} \mapsto x_{A}$ , and $x_{-} \mapsto \frac{1}{2} x_{+} + \frac{1}{2} x_{-}$ . Indeed, in MRP 1, $x_{A}$ comes from state $A$ and the next state is $B$ , whose outgoing reward is equally likely $1$ or $- 1$ ; $x_{+}$ records the transition $B \to A$ , so the next observation is $x_{A}$ ; and $x_{-}$ records $B \to B$ , after which the next outgoing reward is equally likely $1$ or $- 1$ . In MRP 2, $x_{A}$ comes from state $A$ , whose next state is $B$ or $B^{'}$ equally; $x_{+}$ identifies state $B$ , whose next state is $A$ ; and $x_{-}$ identifies state $B^{'}$ , whose next state is $B$ or $B^{'}$ equally. Thus both observed processes have the same initial law $ν$ and transition kernel $K$ , and their finite-prefix laws factor as $ν (x_{0}) \prod_{k = 0}^{n - 1} K (x_{k}, {x_{k + 1}})$ by repeated conditioning. By [F4], the path law with these finite-prefix laws is unique, so their observable path laws agree.

2.1givenF2step 1.1algebra

In MRP 1 the conditional expected Bellman residual at $A$ is $γ b - a$ , because $A$ moves to $B$ with reward zero. At $B$ , expected reward is $(1 - 1) / 2 = 0$ and the expected next value is $(a + b) / 2$ , so the residual is $γ (a + b) / 2 - b$ . Weighting their squares by $μ_{1}$ gives the stated ${BE}_{1}$ . In MRP 2, the residuals at $A, B, B^{'}$ are respectively $γ b - a$ , $1 + γ a - b$ , and $- 1 + γ b - b = - 1 + (γ - 1) b$ , which gives the stated ${BE}_{2}$ under $μ_{2}$ . At $(0, 0)$ the first objective is zero and the second is $2 / 3$ .

3.1givenstep 2.1algebra

Since ${BE}_{1}$ is a sum of nonnegative squares and vanishes at $(0, 0)$ , that point is a minimizer. If it vanishes at $(a, b)$ , its first residual gives $a = γ b$ and its second gives $b = γ (a + b) / 2 = γ (γ + 1) b / 2$ . Since $γ (γ + 1) / 2 < 1$ for $0 \leq γ < 1$ , $b = 0$ and then $a = 0$ , proving uniqueness.

3.2givenstep 2.1algebra

Let $r_{A} = γ b - a$ , $r_{B} = 1 + γ a - b$ , and $r_{B^{'}} = - 1 + (γ - 1) b$ . Then $3 {BE}_{2} = r_{A}^{2} + r_{B}^{2} + r_{B^{'}}^{2}$ . Its residual matrix is $X = (\begin{array}{cc} - 1 & γ \\ γ & - 1 \\ 0 & γ - 1 \end{array})$ , with residual vector $X (a, b)^{T} + (0, 1, - 1)^{T}$ . At $(a, b) = (- γ / D, γ / (2 D))$ , direct substitution gives $r_{B} = (γ + 2) / (2 D)$ , $r_{A} = γ r_{B}$ , and $r_{B^{'}} = - (γ + 1) r_{B}$ . Hence $X^{T} (r_{A}, r_{B}, r_{B^{'}})^{T} = 0$ . For any increment $h \in R^{2}$ , expanding the squared residual gives $3 ({BE}_{2} (w + h) - {BE}_{2} (w)) = ∥ X h ∥_{2}^{2}$ at this point. If $X h = 0$ , its first two rows give $h_{1} = γ h_{2}$ and $γ h_{1} = h_{2}$ , so $(1 - γ^{2}) h_{2} = 0$ ; because $γ < 1$ , $h = 0$ . Thus the objective is strictly larger at every nonzero perturbation and the stated point is the unique global minimizer. Its minimum value is $\frac{1}{3} (γ^{2} + 1 + (γ + 1)^{2}) (\frac{γ + 2}{2 D})^{2} = (γ + 2)^{2} / (6 D)$ .

4.1givenstep 1.2step 2.1step 3.1step 3.2algebra∎

The observable path laws agree by step 1.2, but the Bellman-error functions differ because their values at $(0, 0)$ are $0$ and $2 / 3$ . For $0 < γ < 1$ , their unique minimizers also differ because MRP 1 has minimizer $(0, 0)$ whereas MRP 2 has first coordinate $- γ / D < 0$ . Any quantity determined only by the observable law must be the same for two models with that law; it cannot equal these distinct objectives or, for positive discount, both minimizing parameters. This proves the non-identifiability claims.

Remarks

The exact MRP 2 minimizer above has one-sided limit $(- 1 / 3, 1 / 6)$ as $γ ↑ 1$ . At the excluded endpoint $γ = 1$ , the objective is $\frac{1}{3} ((b - a)^{2} + (1 + a - b)^{2} + 1)$ and is minimized exactly when $b - a = 1 / 2$ , so $(- 1 / 2, 0)^{T}$ is one of multiple endpoint minimizers. It is not the limit of the unique minimizers for $γ < 1$ , despite the book’s printed limiting value. The exact finite- $γ$ calculation, rather than that limiting value, is used in the Statement.

Diagram

Each arrow is a transition and its label gives the reward; the probability is shown in parentheses when that state has two outgoing edges. $B$ and $B^{'}$ have the same feature, while $A$ has a separate feature. The diagrams encode the transition data in the Statement; the proof uses the explicit kernels and feature map.

Depends on

Used by

At discount one-half, identical observable laws hide different Bellman-error minima Example

Dependency tree · two levels

34 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Richard S. Sutton and Andrew G. Barto, Reinforcement Learning: An Introduction, 2nd ed. (standard reference, not scraped)
Marcus Hutter, Samuel Yang-Zhao, and Sultan J. Majeed, Conditions on Features for Temporal Difference-Like Methods to Converge (standard reference, not scraped)