LemmaStatement: AI-adaptedProof: AI-generatedPipeline-generated

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.

Expert mixing changes finite-horizon state occupancy by at most the mixing mass

Statement

Let a finite-horizon MDP have positive integer horizon $T$ , and let $π^{*}$ and $\hat{π}$ be stationary Markov policies. For a stationary policy $π$ , define its state transition matrix by $P_{π} (s, s^{'}) = \sum_{a \in A (s)} π (a ∣ s) P (s^{'} ∣ s, a)$ ; for a state vector $μ$ , define $(μ P_{π}) (s^{'}) = \sum_{s \in S} μ (s) P_{π} (s, s^{'})$ . Fix $β \in [0, 1]$ and let $π_{β} (a ∣ s) = β π^{*} (a ∣ s) + (1 - β) \hat{π} (a ∣ s)$ , which is the per-decision expert/learner mixture. For every function $g : S \to [0, 1]$ , its finite-horizon average occupancies satisfy

$∣ \sum_{s \in S} d_{π_{β}} (s) g (s) - \sum_{s \in S} d_{\hat{π}} (s) g (s) ∣ \leq 1 - (1 - β)^{T} \leq \min {1, T β} .$

Here $d_{π} = T^{- 1} \sum_{t = 0}^{T - 1} μ_{t}^{π}$ is the normalized average of the state marginals from the common initial distribution.

Statement references

Finite-horizon imitation learning and expert-surrogate loss: defines the finite-horizon state recursion, normalized average occupancy, and the DAgger per-decision policy mixture.

The principle of mathematical induction: finite recursion and Bernoulli inequality use natural-number induction.

Ross, Gordon, and Bagnell, A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning: Lemma 4.1 and proof, §4.2, PDF p. 4.

Duisterhof, Truong, and Agrawal, Algorithmic Foundations of Interactive Learning, Lecture 9: PDF pp. 50–53 / note pages 46–47.

Facts & Assumptions

Given: The finite MDP, initial distribution, horizon, policies, and mixture parameter in the Statement.

[F1]

Finite-horizon imitation learning and expert-surrogate loss: for each policy $π$ , $μ_{t + 1}^{π} = μ_{t}^{π} P_{π}$ and $d_{π} = T^{- 1} \sum_{t < T} μ_{t}^{π}$ .

[F2]

Finite-horizon MDP policy occupancy is a probability distribution: every $μ_{t}^{π}$ and $d_{π}$ is a probability vector, with nonnegative coordinates.

[F3]

The principle of mathematical induction: a property holding at zero and preserved by successors holds for all natural indices.

Proof

1.1F1F2F3algebraconstruct

Put $q = 1 - β$ . The transition matrix of the mixed policy is $P_{π_{β}} = q P_{\hat{π}} + β P_{π^{*}}$ by finite-sum distributivity. For each $t \leq T$ , we show $μ_{t}^{π_{β}} = q^{t} μ_{t}^{\hat{π}} + r_{t}$ , where $r_{t}$ has nonnegative coordinates and total mass $1 - q^{t}$ . At $t = 0$ , take $r_{0} = 0$ . If the formula holds at $t < T$ , the recursion gives $μ_{t + 1}^{π_{β}} = q^{t + 1} μ_{t + 1}^{\hat{π}} + \underset{r_{t + 1}}{\underset{⏟}{q^{t} β μ_{t}^{\hat{π}} P_{π^{*}} + r_{t} P_{π_{β}}}}$ . The two terms defining $r_{t + 1}$ have nonnegative coordinates, and their total masses are $q^{t} β$ and $1 - q^{t}$ , so $r_{t + 1}$ has mass $1 - q^{t + 1}$ . Induction proves the decomposition for every $t \leq T$ .

2.1F1F2step 1.1algebraconstruct

Since $0 \leq q \leq 1$ , for each $t < T$ one has $q^{t} \geq q^{T}$ . Thus $r_{t}^{'} : = r_{t} + (q^{t} - q^{T}) μ_{t}^{\hat{π}}$ is nonnegative and has mass $1 - q^{T}$ . Averaging over $t = 0, \dots, T - 1$ gives $d_{π_{β}} = q^{T} d_{\hat{π}} + r^{'}$ , where $r^{'} = T^{- 1} \sum_{t < T} r_{t}^{'}$ has mass $1 - q^{T}$ . If $1 - q^{T} > 0$ , normalize $r^{'}$ to a probability vector $ν$ ; then for $g : S \to [0, 1]$ the difference of expectations is $(1 - q^{T}) (\sum_{s} ν (s) g (s) - \sum_{s} d_{\hat{π}} (s) g (s))$ , whose absolute value is at most $1 - q^{T}$ . If $1 - q^{T} = 0$ , the occupancies are equal and the same bound is zero.

3.1F3step 2.1algebra∎

The Bernoulli inequality $q^{T} = (1 - β)^{T} \geq 1 - T β$ follows by induction: it is equality at $T = 0$ , and multiplying $q^{n} \geq 1 - n β$ by $q \geq 0$ gives $q^{n + 1} \geq (1 - n β) (1 - β) = 1 - (n + 1) β + n β^{2} \geq 1 - (n + 1) β$ . Also $1 - q^{T} \leq 1$ , so $1 - q^{T} \leq \min {1, T β}$ . Combining this with step 2.1 proves the Statement.

Depends on

Used by

Dependency tree · two levels

11 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

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)
Bardienus Duisterhof, Kimberly Truong, and Khush Agrawal, Algorithmic Foundations of Interactive Learning, Lecture 9: DAgger & Covariate Shift in IL, lecturer J. Andrew Bagnell (standard reference, not scraped)