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.

Discounted episodic policy gradients from trajectory likelihoods

Statement

Assume the Axiom of Choice. Let a finite Markov decision process have nonempty finite state set $S$ , finite nonempty action sets $A (s)$ , finite reward set $R$ , and fixed joint transition-reward masses $p (s^{'}, r ∣ s, a)$ . Fix an initial state $s_{0} \in S$ , a terminal set $S_{†} \subseteq S$ , and $0 \leq γ < 1$ . Let $U \subseteq R^{d}$ be open, let $θ_{0} \in U$ , and let $π_{θ}$ be a differentiable stationary policy family with fixed common support on an open neighborhood $U_{0}$ of $θ_{0}$ . Suppose every episode from $s_{0}$ under $π_{θ}$ , for $θ \in U_{0}$ , reaches $S_{†}$ in finite time almost surely. Let $T$ be the first terminal time, let

$G_{t} = \sum_{k = t}^{T - 1} γ^{k - t} R_{k + 1} (t < T), G_{T} = 0,$

and set $J (θ) = V^{π_{θ}} (s_{0}) = E_{θ} [\sum_{k = 0}^{T - 1} γ^{k} R_{k + 1}]$ . Let $T$ be the set of finite trajectories that use only actions in the common policy support, have positive transition masses, and stop at their first terminal state. For $τ = (s_{0}, a_{0}, r_{1}, s_{1}, \dots, a_{m - 1}, r_{m}, s_{m}) \in T$ , define

$p_{θ} (τ) = \prod_{t = 0}^{m - 1} π_{θ} (a_{t} ∣ s_{t}) p (s_{t + 1}, r_{t + 1} ∣ s_{t}, a_{t}), R_{γ} (τ) = \sum_{k = 0}^{m - 1} γ^{k} r_{k + 1} .$

Assume the trajectory masses $p_{θ} (τ)$ are totally differentiable at $θ_{0}$ , the linear map $h \mapsto \sum_{τ \in T} R_{γ} (τ) D p_{θ_{0}} (τ) h$ is defined by an absolutely convergent sum, and there is a summable $H : T \to [0, \infty)$ that dominates the return-weighted normalized remainders below and for which those remainders tend to zero pathwise:

$\frac{∣ R_{γ} (τ) ∣ ∣ p_{θ_{0} + h} (τ) - p_{θ_{0}} (τ) - D p_{θ_{0}} (τ) h ∣}{∥ h ∥_{2}} \leq H (τ), \frac{∣ R_{γ} (τ) ∣ ∣ p_{θ_{0} + h} (τ) - p_{θ_{0}} (τ) - D p_{θ_{0}} (τ) h ∣}{∥ h ∥_{2}} ⟶ 0$

for every $τ \in T$ as $h \to 0$ , with $\sum_{τ \in T} H (τ) < \infty$ .

Also assume

$E_{θ_{0}} ⁣ [\sum_{t < T} \sum_{k < T} γ^{k} ∥ ψ_{θ_{0}} (S_{t}, A_{t}) ∥_{2} ∣ R_{k + 1} ∣] < \infty,$

where $ψ_{θ} (s, a) = \nabla_{θ} \log π_{θ} (a ∣ s)$ on the common support. Then $J$ is totally differentiable at $θ_{0}$ and

$\nabla_{θ} J (θ_{0}) = E_{θ_{0}} ⁣ [\sum_{t = 0}^{T - 1} γ^{t} \nabla_{θ} \log π_{θ_{0}} (A_{t} ∣ S_{t}) G_{t}] .$

Statement references

Sutton and Barto, Reinforcement Learning: An Introduction, second-edition draft.

Williams, Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning.

Facts & Assumptions

Given: The finite MDP, Axiom of Choice, start and terminal states, discount, policy family, almost-sure termination, and the two stated dominated-differentiation and integrability assumptions.

[A1]

The Axiom of Choice: every family of nonempty sets has a choice function; it is used to obtain the policy path law.

[A2]

The return-weighted normalized likelihood remainders in the Statement tend to zero pathwise and are dominated by one summable envelope; this is the exact hypothesis for applying dominated convergence to the trajectory series.

[A3]

The discounted score-reward double sum in the Statement is integrable; it permits the expectation and time sums in the proof to be interchanged by dominated convergence.

[F1]

Finite Markov decision process with joint reward-transition law: state, action, and reward sets are finite; $p (s^{'}, r ∣ s, a)$ is a normalized joint next-state/reward law, and the dynamics do not depend on $θ$ .

[F2]

Differentiable stationary stochastic policies and score vectors: each $π_{θ} (\cdot ∣ s)$ is normalized and totally differentiable, with fixed positive support; $ψ_{θ} (s, a) = \nabla_{θ} \log π_{θ} (a ∣ s)$ on that support.

[F3]

Episodic returns, temporal-difference errors, and policy support: the episode stops at its first terminal state, terminates almost surely, and $G_{t} = \sum_{k = t}^{T - 1} γ^{k - t} R_{k + 1}$ is the return from time $t$ ; its initial value is the discounted value on the absorbing extension.

[F4]

A finite MDP policy generates action-state-reward trajectories: under AC, every feasible finite action-state-reward prefix has mass equal to the product of its policy probabilities and joint transition-reward masses; its one-step record alphabet is finite.

[F5]

Finite, countably infinite, countable, uncountable and A natural-number coding of finite sequences: a set is at most countable when it injects into $N$ , and every finite sequence of natural numbers has an injective natural-number code.

[F6]

Chain sum product and composition rules for Banach derivatives: for a bounded bilinear map, $D (B (f, g)) h = B (D f h, g) + B (f, D g h)$ .

[F7]

The chain rule for total derivatives: $D (g \circ f) (a) = D g (f (a)) \circ D f (a)$ : derivatives of compositions are compositions of total derivatives.

[F8]

The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t: for positive $x$ , $\log^{'} (x) = 1 / x$ .

[F9]

A policy score has zero conditional mean before the action: before each action, the conditional expectation of its score vector given the entire past and current state is zero.

[F10]

Conditional expectation given a sigma algebra: conditional expectation preserves integrals on conditioning events; Taking out what is known permits an integrable measurable past factor to be taken outside it.

[F11]

Dominated convergence: pointwise convergence under one integrable majorant permits convergence of the corresponding integrals.

[F12]

Expectation of a nonnegative or integrable random variable: expectation of an integrable real random variable is its finite Lebesgue integral.

Proof

technique · differentiate the finite-trajectory likelihood, then remove rewards earned before each action by the zero-mean score identity

1.1givenF1F3F4F5algebra

If $s_{0} \in S_{†}$ , then $T = 0$ , the return and gradient are zero, and the sum in the conclusion is empty. Otherwise, the transition-record alphabet is finite by [F1] and [F4]. Fix an enumeration of that alphabet; every finite terminal path becomes a finite sequence of natural-number indices, so [F5] injects $T$ into $N$ .

1.2F1F2F4F6F7F8algebra

Fix $τ = (s_{0}, a_{0}, r_{1}, s_{1}, \dots, a_{m - 1}, r_{m}, s_{m}) \in T$ . By [F4], its probability is the displayed product. Repeatedly applying the bounded-bilinear product rule [F6] to its finitely many policy factors, and using [F2], [F7], and [F8], gives $D p_{θ_{0}} (τ) = p_{θ_{0}} (τ) \sum_{t = 0}^{m - 1} ψ_{θ_{0}} (s_{t}, a_{t})$ . Paths with a zero transition mass or an unsupported action have probability zero throughout $U_{0}$ and are omitted from $T$ . The empty trajectory has empty product $1$ and empty score sum $0$ .

2.1A1A2F3F4F11F12step 1.2

The episode termination assumption makes the masses of $T$ sum to one, and [F3] identifies $J (θ) = \sum_{τ \in T} p_{θ} (τ) R_{γ} (τ)$ . By [A2] and [F11], the derivative of this series at $θ_{0}$ is the absolutely convergent sum $\sum_{τ} R_{γ} (τ) D p_{θ_{0}} (τ)$ . Substituting step 1.2 shows that, for every direction $h \in R^{d}$ , $D J (θ_{0}) h = E_{θ_{0}} [R_{γ} (τ) ⟨ \sum_{t < T} ψ_{θ_{0}} (S_{t}, A_{t}), h ⟩]$ .

3.1A3F9F10F11step 2.1

Expand $R_{γ} = \sum_{k < T} γ^{k} R_{k + 1}$ . For each $k < t$ , the event $t < T$ and the past reward $R_{k + 1}$ are $H_{t}$ -measurable. By [F9] and [F10], each coordinate of $E [1_{{t < T}} R_{k + 1} ψ_{t}]$ is zero. The bound [A3] dominates every finite rectangular truncation of the double sum by an integrable random variable, so [F11] permits passing to the full sum. All terms with $k < t$ therefore vanish in step 2.1.

4.1F2F3step 2.1step 3.1algebra∎

The remaining terms have $k \geq t$ , and the return definition [F3] gives $\sum_{k = t}^{T - 1} γ^{k} R_{k + 1} = γ^{t} G_{t}$ . Hence step 2.1 becomes $D J (θ_{0}) h = ⟨ E_{θ_{0}} [\sum_{t = 0}^{T - 1} γ^{t} G_{t} ψ_{θ_{0}} (S_{t}, A_{t})], h ⟩$ . Since this holds for every $h$ , the vector inside the inner product is the Euclidean gradient of $J$ at $θ_{0}$ , proving the assertion.

Remarks

The factor $γ^{t}$ is part of the identity for the discounted start-state objective and the return convention stated here. The result is episodic. A continuing average-reward policy-gradient statement uses a different objective and requires an existing stationary state distribution independent of the start state under the source's ergodicity premise. No convergence theorem for nonlinear or deep parameter updates is asserted here.

Depends on

Used by

Dependency tree · two levels

87 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, second-edition draft (standard reference, not scraped)
Ronald J. Williams, Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning, Machine Learning 8 (1992) (standard reference, not scraped)