TheoremStatement: AI-adaptedProof: 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.

A finite MDP and stationary policy generate a reward-state Markov chain

Statement

Assume the Axiom of Choice. Let a finite MDP have nonempty state set $S$ , and let $π$ be a stationary Markov policy. Put $E = S \times (R \cup {0})$ with its discrete sigma-algebra and define, for $x = (s, η) \in E$ and $B \subseteq E$ ,

$K_{π} (x, B) = \sum_{a \in A (s)} π (a ∣ s) \sum_{\begin{array}{c} s^{'} \in S \\ ρ \in R \end{array}} 1_{B} (s^{'}, ρ) p (s^{'}, ρ ∣ s, a) .$

Then $K_{π}$ is a probability kernel on $E$ . For each initial state $s \in S$ , there is a probability law on $E^{N}$ whose coordinate process starts at $(s, 0)$ and is a time-homogeneous Markov chain with transition kernel $K_{π}$ relative to its natural filtration.

Statement references

Sutton and Barto, Reinforcement Learning: An Introduction.

Kaelbling, Littman, and Cassandra, Brown Technical Report CS-96-08.

Facts & Assumptions

Given: A finite MDP with $S \neq \emptyset$ , a stationary policy $π$ , and the Axiom of Choice.

[A1]

The Axiom of Choice: every family of nonempty sets has a choice function.

[F1]

Finite Markov decision process with joint reward-transition law: for every $(s, a)$ , the finite joint masses $p (s^{'}, ρ ∣ s, a)$ are nonnegative and sum to one; $π (\cdot ∣ s)$ is a probability distribution.

[F2]

Measure kernel and probability kernel: a probability kernel assigns a probability measure at each input and has measurable event sections at every input.

[F3]

Ionescu-Tulcea construction of a Markov chain: under Choice, an initial probability and a sequence of probability kernels give a unique path-space probability law with the prescribed iterated finite-prefix laws; in the homogeneous last-coordinate case, the coordinate process is a homogeneous chain.

[F4]

Time-homogeneous Markov chain with transition kernel: a process is a homogeneous Markov chain relative to a filtration when its conditional next-state law equals the specified kernel applied to the current state, almost surely.

[F5]

A subset of a finite set is finite, with $∣ B ∣ \leq ∣ A ∣$ , and equality holds if and only if $B = A$ , The sum rule: a finite disjoint union is finite with $∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣$ and $∣ ⋃_{i \in I} A_{i} ∣ = \sum_{i \in I} ∣ A_{i} ∣$ , and a sum over a finite index set splits along a partition, and The product rule: $∣ A \times B ∣ = ∣ A ∣ ∣ B ∣$ , and $∣ \prod_{i < m} A_{i} ∣ = \prod_{i < m} ∣ A_{i} ∣$ : subsets, finite unions, and finite Cartesian products of finite sets are finite; a sum over a finite partition splits into the sums over its parts.

[F6]

The sum $\sum_{i \in S} a_{i}$ over a finite index set, and its product form and $\sum_{i \in S} \sum_{j \in T} a_{i j} = \sum_{(i, j) \in S \times T} a_{i j} = \sum_{j \in T} \sum_{i \in S} a_{i j}$ for finite index sets $S$ and $T$ : finite sums are independent of enumeration and the order of two finite sums may be interchanged.

[F7]

The product sigma-algebra and its finite iterates: finite product sigma-algebras are generated by measurable rectangles, so coordinate projections are measurable.

[F8]

The well-ordering principle: every nonempty subset of the natural numbers has a least element.

Proof

1.1givenF1F2F5F6F8algebra

Fix $x = (s, η) \in E$ . By [F5], $E = S \times (R \cup {0})$ is finite: ${0} ∖ R$ is a subset of a finite singleton, $R \cup {0} = R \cup ({0} ∖ R)$ is a finite union, and then take its product with $S$ . For each $a \in A (s)$ , the point masses $p (s^{'}, ρ ∣ s, a)$ on $S \times R \subseteq E$ (and zero on the added dummy-reward points) define a probability measure $μ_{a}$ on $E$ : they are nonnegative and total $1$ by [F1]. To check countable additivity, fix a bijection $e : n \to E$ . For any disjoint sequence $(B_{j})$ , each nonempty $B_{j}$ has a least index $i_{j} < n$ with $e (i_{j}) \in B_{j}$ , by [F8]; disjointness makes these indices distinct, so only finitely many $B_{j}$ are nonempty. Additivity then follows from finite-sum additivity over the partition of the finite support, as in [F5]. The displayed kernel is the finite mixture $K_{π} (x, B) = \sum_{a \in A (s)} π (a ∣ s) μ_{a} (B)$ . Its values are nonnegative and $K_{π} (x, E) = \sum_{a} π (a ∣ s) = 1$ by [F1]. For a disjoint countable family $(B_{j})$ , only finitely many $B_{j}$ are nonempty by the same argument; additivity of each $μ_{a}$ and finite-sum interchange [F6] give $K_{π} (x, ⋃_{j} B_{j}) = \sum_{j} K_{π} (x, B_{j})$ . Thus $B \mapsto K_{π} (x, B)$ is a probability measure. Every subset of $E$ is measurable and every function on the discrete source $E$ is measurable, so [F2] makes $K_{π}$ a probability kernel.

2.1step 1.1F2F7construct

For fixed $s \in S$ , the point mass $μ_{0} = δ_{(s, 0)}$ is a probability measure on $E$ . At every $n \geq 0$ , use the history-dependent kernel $K_{n} (x_{0}, \dots, x_{n}, B) = K_{π} (x_{n}, B)$ . Its final-coordinate projection is measurable because the preimage of each measurable set is a product-measurable coordinate cylinder by [F7]; composition with the measurable section $x \mapsto K_{π} (x, B)$ is measurable. Each section is a probability measure by step 1.1, so $K_{n}$ is a probability kernel.

3.1givenA1step 2.1F3

Apply [F3] to $(E, P (E))$ , $μ_{0}$ , and the sequence $(K_{n})$ . Its homogeneous specialization gives a probability law on $E^{N}$ with initial state $(s, 0)$ and the iterated finite-prefix laws of $K_{π}$ .

4.1step 3.1F3F4∎

The coordinate process under that law is a homogeneous chain relative to its natural filtration by [F3], and its conditional transition identity is exactly the convention in [F4]. This proves the claimed chain construction for every initial $s \in S$ .

Depends on

Used by

Dependency tree · two levels

61 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)
Leslie Pack Kaelbling, Michael L. Littman, and Anthony R. Cassandra, Planning and Acting in Partially Observable Stochastic Domains, Brown CS-96-08 (standard reference, not scraped)