LemmaStatement: 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.

Finite-horizon MDP policy occupancy is a probability distribution

Statement

Let a finite Markov decision process have a nonempty finite state set $S$ and finite nonempty action sets $A (s)$ , with state transition probabilities $P (s^{'} ∣ s, a)$ obtained by summing its joint reward-transition law over rewards. Let $T \geq 1$ be an integer, let $μ_{0} : S \to [0, 1]$ satisfy $\sum_{s \in S} μ_{0} (s) = 1$ , and let $π (a ∣ s)$ be a stationary Markov policy. Define recursively

$μ_{t + 1} (s^{'}) = \sum_{s \in S} \sum_{a \in A (s)} μ_{t} (s) π (a ∣ s) P (s^{'} ∣ s, a), 0 \leq t < T .$

Then each $μ_{t}$ is a probability vector on $S$ , and the finite-horizon average occupancy

$d_{π} (s) = \frac{1}{T} \sum_{t = 0}^{T - 1} μ_{t} (s)$

is also a probability vector. This construction uses only finite sums and does not require an infinite-path probability extension.

Statement references

Finite Markov decision process with joint reward-transition law: the finite state/action sets, row-normalized joint reward-transition law, derived $P (s^{'} ∣ s, a)$ , and stationary Markov policy.

The sum $\sum_{i \in S} a_{i}$ over a finite index set, and its product form: finite-index sums are well-defined and independent of enumeration.

Laws of finite sums and finite products: finite sums preserve nonnegativity, add termwise, and commute with scalar multiplication.

$\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 over two finite index sets may be interchanged.

The principle of mathematical induction: a property proved at $0$ and preserved by successors holds for every natural index.

Sutton and Barto, Reinforcement Learning: An Introduction: §3.6, printed pp. 67–69.

Ross, Gordon, and Bagnell, A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning: §2, PDF p. 1.

Facts & Assumptions

Given: A nonempty finite MDP state set $S$ , finite nonempty action sets $A (s)$ , a normalized initial vector $μ_{0}$ , a stationary Markov policy $π$ , and an integer horizon $T \geq 1$ .

[A1]

$μ_{0}$ is nonnegative with finite sum one, and $T$ is a positive integer.

[L1]

At a successor step $t < T$ , assume $μ_{t}$ is nonnegative and $\sum_{s} μ_{t} (s) = 1$ .

[F1]

Finite Markov decision process with joint reward-transition law: the joint masses $p (s^{'}, ρ ∣ s, a)$ are nonnegative and sum to one over $(s^{'}, ρ)$ ; $P (s^{'} ∣ s, a) = \sum_{ρ} p (s^{'}, ρ ∣ s, a)$ ; and each policy row $π (\cdot ∣ s)$ is a probability vector.

[F2]

The sum $\sum_{i \in S} a_{i}$ over a finite index set, and its product form: sums over finite index sets are the enumeration-independent finite sums.

[F3]

$\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$ : the order of two finite sums may be interchanged.

[F4]

Laws of finite sums and finite products: finite sums preserve nonnegative inequalities, add termwise, and satisfy $\sum_{i} c a_{i} = c \sum_{i} a_{i}$ .

[F5]

The principle of mathematical induction: a property of $t \in N$ holds for every $t$ if it holds at zero and the successor step preserves it.

Proof

1.1A1

At $t = 0$ , $μ_{0}$ is nonnegative and has sum one by [A1].

1.2L1F1F2F3F4algebra

Fix $t < T$ and assume [L1]. Every term in the recursion for $μ_{t + 1} (s^{'})$ is nonnegative by [F1]. For each admissible $(s, a)$ , [F1] and finite-sum interchange [F3] give $\sum_{s^{'} \in S} P (s^{'} ∣ s, a) = \sum_{s^{'} \in S} \sum_{ρ \in R} p (s^{'}, ρ ∣ s, a) = 1$ . Interchange the finite state sums and factor constants using [F2]–[F4]: $\sum_{s^{'} \in S} μ_{t + 1} (s^{'}) = \sum_{s^{'} \in S} \sum_{s \in S} \sum_{a \in A (s)} μ_{t} (s) π (a ∣ s) P (s^{'} ∣ s, a) = \sum_{s \in S} μ_{t} (s) \sum_{a \in A (s)} π (a ∣ s) \sum_{s^{'} \in S} P (s^{'} ∣ s, a) = \sum_{s \in S} μ_{t} (s) \sum_{a \in A (s)} π (a ∣ s) = \sum_{s \in S} μ_{t} (s) = 1$ . The calculation and nonnegativity prove that $μ_{t + 1}$ is a probability vector.

2.1F5step 1.1step 1.2

Step 1.1 proves the base case and step 1.2 proves the successor case, so [F5] gives nonnegative normalized vectors $μ_{t}$ for every $0 \leq t \leq T$ .

3.1A1F2F4step 2.1algebra∎

Every term in $d_{π} (s)$ is nonnegative. Summing over $s$ and using the finite-sum scaling law [F4] gives $\sum_{s} d_{π} (s) = T^{- 1} \sum_{t = 0}^{T - 1} \sum_{s} μ_{t} (s) = T^{- 1} \sum_{t = 0}^{T - 1} 1 = 1$ , because there are exactly $T$ indices and $T \geq 1$ . Hence $d_{π}$ is a probability vector.

Depends on

Used by

Dependency tree · two levels

39 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)
Stéphane Ross, Geoffrey J. Gordon, and J. Andrew Bagnell, A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning (standard reference, not scraped)