LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-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-surrogate loss bounds finite-horizon task-cost increase

Statement

Let a finite-horizon MDP, horizon $T \geq 1$ , initial distribution, deterministic expert $π^{*}$ , learner policy $π_{θ}$ , task cost $J$ , expert cost-to-go $Q_{t}^{*}$ , expert value $V_{t}^{*} (s) = Q_{t}^{*} (s, π^{*} (s))$ , occupancy $d_{π_{θ}}$ , and surrogate $ℓ (s, θ)$ be as defined previously. Suppose $u \geq 0$ and

$Q_{t}^{*} (s, a) - V_{t}^{*} (s) \leq u$

for every time $0 \leq t < T$ , state $s \in S$ , and admissible action $a \in A (s)$ , and suppose $ℓ (s, θ) \geq \sum_{a \neq π^{*} (s)} π_{θ} (a ∣ s)$ for every state. Then

$J (π_{θ}) - J (π^{*}) \leq u T \sum_{s \in S} d_{π_{θ}} (s) ℓ (s, θ) .$

The one-step cost-to-go bound is required at all states and times, including states not reached by the expert.

Statement references

Finite-horizon imitation learning and expert-surrogate loss: defines finite-horizon task cost, expert cost-to-go recursion, normalized state occupancy, and the surrogate's expert-action-disagreement domination condition.

Ross, Gordon, and Bagnell, A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning: Theorem 2.2 and its complete hybrid-policy proof, §2.2, PDF pp. 2–3.

Duisterhof, Truong, and Agrawal, Algorithmic Foundations of Interactive Learning, Lecture 9: equations (9.72)–(9.74), PDF p. 54 / note page 48; used for terminology only.

Facts & Assumptions

Given: The finite MDP and policy definitions in the Statement, a learner parameter $θ$ , $u \geq 0$ , the uniform one-step expert cost-to-go upper bound, and the statewise surrogate disagreement upper bound.

[F1]

Finite-horizon imitation learning and expert-surrogate loss: $J (π)$ is the finite sum of expected per-time costs, $d_{π} = T^{- 1} \sum_{t < T} μ_{t}^{π}$ , and $Q_{t}^{*} (s, a) = c_{t} (s, a) + \sum_{s^{'}} P (s^{'} ∣ s, a) V_{t + 1}^{*} (s^{'})$ with $V_{t}^{*} (s) = Q_{t}^{*} (s, π^{*} (s))$ .

[F2]

For any sequence of Markov policies $(ρ_{t})_{t = 0}^{T - 1}$ , define $μ_{0}^{ρ} = μ_{0}$ , recursively set $μ_{t + 1}^{ρ} (s^{'}) = \sum_{s} μ_{t}^{ρ} (s) \sum_{a \in A (s)} ρ_{t} (a ∣ s) P (s^{'} ∣ s, a)$ , and define $J (ρ) = \sum_{t = 0}^{T - 1} \sum_{s} μ_{t}^{ρ} (s) \sum_{a \in A (s)} ρ_{t} (a ∣ s) c_{t} (s, a)$ . For a stationary policy this agrees with $J$ in [F1].

[A1]

$Q_{t}^{*} (s, a) - V_{t}^{*} (s) \leq u$ for every $t, s, a$ .

[A2]

$ℓ (s, θ) \geq \sum_{a \neq π^{*} (s)} π_{θ} (a ∣ s)$ for every $s$ .

Proof

1.1givenF1F2constructalgebra

For $k = 0, \dots, T$ , let $ρ_{t}^{(k)} = π_{θ}$ for $t < k$ and $ρ_{t}^{(k)} = π^{*}$ for $t \geq k$ . By [F2], these time-dependent policies have finite-horizon costs $J (ρ^{(k)})$ , with $J (ρ^{(0)}) = J (π^{*})$ and $J (ρ^{(T)}) = J (π_{θ})$ . Telescoping gives $J (π_{θ}) - J (π^{*}) = \sum_{k = 0}^{T - 1} (J (ρ^{(k + 1)}) - J (ρ^{(k)}))$ .

2.1F1F2step 1.1algebra

The two hybrid policies in the $k$ th difference have the same state distribution $μ_{k}^{π_{θ}}$ at time $k$ , because both use $π_{θ}$ for the first $k$ decisions. From then on, one takes the learner action at time $k$ and the other takes the expert action, and both follow the expert afterward. The cost recursion [F2] and the definition of $Q_{k}^{*}$ therefore give $J (ρ^{(k + 1)}) - J (ρ^{(k)}) = \sum_{s \in S} μ_{k}^{π_{θ}} (s) \sum_{a \in A (s)} π_{θ} (a ∣ s) (Q_{k}^{*} (s, a) - V_{k}^{*} (s))$ .

3.1A1A2step 2.1algebra

For $a = π^{*} (s)$ the cost-to-go difference in step 2.1 is zero by the definition of $V_{k}^{*}$ . For every other action it is at most $u$ by [A1]. Therefore each inner sum in step 2.1 is at most $u \sum_{a \neq π^{*} (s)} π_{θ} (a ∣ s) \leq u ℓ (s, θ)$ by [A2].

4.1F1step 1.1step 3.1algebra∎

Sum step 3.1 over $k = 0, \dots, T - 1$ and use $d_{π_{θ}} = T^{- 1} \sum_{k < T} μ_{k}^{π_{θ}}$ from [F1]. The result is $J (π_{θ}) - J (π^{*}) \leq u \sum_{k < T} \sum_{s} μ_{k}^{π_{θ}} (s) ℓ (s, θ) = u T \sum_{s} d_{π_{θ}} (s) ℓ (s, θ)$ , as claimed.

Depends on

Finite-horizon imitation learning and expert-surrogate loss

Used by

DAgger no-regret reduction under strongly convex surrogate losses Theorem

Dependency tree · two levels

4 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)