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

Finite-sample DAgger surrogate-loss guarantee

Statement

Assume the finite-horizon imitation-learning setting with deterministic expert $π^{*}$ , positive integer horizon $T$ , expert surrogate $ℓ (s, θ) \in [0, 1]$ , learner policies $π_{θ}$ , and nonempty convex parameter set $K \subseteq R^{d}$ defined previously. Let $d \geq 1$ be an integer and use $∥ x - y ∥_{2} = (\sum_{r = 1}^{d} (x_{r} - y_{r})^{2})^{1 / 2}$ . Suppose for every state $s$ , $ℓ (s, \cdot)$ is $G$ -Lipschitz and $μ$ -strongly convex on $K$ , with constants $G \geq 0$ and $μ > 0$ , where Lipschitz means $∣ ℓ (s, x) - ℓ (s, y) ∣ \leq G ∥ x - y ∥_{2}$ and strong convexity means $ℓ (s, (1 - λ) x + λ y) \leq (1 - λ) ℓ (s, x) + λ ℓ (s, y) - \frac{μ}{2} λ (1 - λ) ∥ x - y ∥_{2}^{2}$ for $x, y \in K$ and $λ \in [0, 1]$ . Assume also that $θ \mapsto π_{θ} (a ∣ s)$ is Borel measurable for every state-action pair.

Run finite-trajectory DAgger for positive integers $N, m$ , with per-decision expert-use probabilities $β_{i} \in [0, 1]$ satisfying $β_{1} \leq 1$ and $β_{i} \leq (1 - α)^{i - 1}$ for $2 \leq i \leq N$ , where $α \in (0, 1]$ is fixed. Let ${\hat{π}}_{i} = π_{θ_{i}}$ and $π_{i} = β_{i} π^{*} + (1 - β_{i}) {\hat{π}}_{i}$ . In round $i$ , let $S_{i j t}$ , $1 \leq j \leq m$ , $0 \leq t < T$ , be the states of trajectory $j$ , and define ${\overset{ˉ}{ℓ}}_{i j} (θ) = T^{- 1} \sum_{t = 0}^{T - 1} ℓ (S_{i j t}, θ)$ , ${\hat{L}}_{i} (θ) = m^{- 1} \sum_{j = 1}^{m} {\overset{ˉ}{ℓ}}_{i j} (θ)$ , and ${\hat{ϵ}}_{N} = \min_{θ \in K} N^{- 1} \sum_{i = 1}^{N} {\hat{L}}_{i} (θ)$ . Assume this minimum and every cumulative empirical-loss minimum are attained, and DAgger uses exact Follow-the-Leader updates.

Assume the samples are observed in a filtered probability space with nested sigma-algebras $F_{i, j}$ , where $F_{1, 0} = F_{0}$ , $F_{i, 0} = F_{i - 1, m}$ for $i > 1$ , and $F_{i, j - 1} \subseteq F_{i, j}$ . Suppose $θ_{i}$ is $F_{i, 0}$ -measurable, each trajectory state $S_{i j t}$ is $F_{i, j}$ -measurable, and the conditional rollout law satisfies $E [{\overset{ˉ}{ℓ}}_{i j} (θ_{i}) ∣ F_{i, j - 1}] = L_{i} (θ_{i})$ almost surely, where $L_{i} (θ) = \sum_{s} d_{π_{i}} (s) ℓ (s, θ)$ is the true round- $i$ loss under the mixed rollout policy. Assume the Axiom of Choice for the conditional-expectation and martingale results used below. Let $δ \in (0, 1)$ , define $H_{0} = 0$ and $H_{n} = \sum_{r = 1}^{n} 1 / r$ , let $q_{T}$ be the least nonnegative integer with $T \leq 2^{q_{T}}$ , and let $k_{α}$ be the least positive integer with $k_{α} α \geq 1$ . Then with probability at least $1 - δ$ , some $i \in {1, \dots, N}$ satisfies

$\sum_{s} d_{{\hat{π}}_{i}} (s) ℓ (s, θ_{i}) \leq {\hat{ϵ}}_{N} + \frac{1 + \frac{4 G^{2}}{μ} H_{N - 1} + k_{α} (q_{T} + 2)}{N} + \sqrt{\frac{2 \ln (1 / δ)}{m N}} .$

For each fixed $m \geq 1$ , $α \in (0, 1]$ , $μ > 0$ , and $G \geq 0$ , there are constants $C, C^{'} > 0$ depending only on these parameters such that if $δ \in (0, 1 / 2]$ and $N \geq C T^{2} \ln (1 / δ)$ , the right side is at most ${\hat{ϵ}}_{N} + C^{'} / T$ . This is a surrogate-loss guarantee with interactive expert labels; it does not assert a finite-sample task-cost bound.

Statement references

Finite-horizon imitation learning and expert-surrogate loss: defines finite-horizon state occupancy, the mixed rollout policy, and the true round loss.

Dataset Aggregation (DAgger): defines finite-trajectory DAgger, empirical round loss, and exact FTL updates using interactive expert labels.

Follow-the-Leader regret for bounded strongly convex losses: supplies the empirical FTL regret bound $1 + (4 G^{2} / μ) H_{N - 1}$ .

Expert mixing changes finite-horizon state occupancy by at most the mixing mass: bounds the absolute change in a bounded state-loss expectation under expert mixing by $\min (1, T β_{i})$ .

Azuma-Hoeffding inequality: supplies the bounded-increment martingale tail bound under the stated Axiom of Choice assumption.

Filtration and filtered probability space: defines the nested information sigma-algebras used to reveal samples.

Adapted and integrable stochastic process: defines adaptedness and integrability of the trajectory-loss increments.

Martingale difference sequence: defines the centered adapted increments.

Martingales and martingale differences correspond: converts the centered increments to a martingale.

Martingale submartingale and supermartingale: defines the martingale property used by Azuma–Hoeffding.

Conditional expectation as an ae class: fixes the almost-sure class convention for conditional means.

The Axiom of Choice: states the axiom assumed by the conditional-expectation and Azuma interfaces.

Ross, Gordon, and Bagnell, A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning: Theorem 4.2 and complete proof, §4.2, PDF pp. 4–5.

Bagnell, Boots, and Choudhury, Modern Adaptive Control and Reinforcement Learning, Chapter 6: PDF pp. 4–7 / printed pp. 57–60.

Duisterhof, Truong, and Agrawal, Algorithmic Foundations of Interactive Learning, Lecture 9: PDF pp. 51–54 / note pages 47–48; cited for conventions, not for the incomplete final cost-proof sketch.

Facts & Assumptions

Given: The finite-horizon MDP, expert and surrogate definitions, bounded strongly convex Lipschitz loss, exact empirical DAgger updates, nested sample filtration, conditional rollout-mean identity, attained empirical minima, geometric expert-use schedule, confidence parameter, and Axiom of Choice in the Statement.

[F1]

Finite-horizon imitation learning and expert-surrogate loss: $d_{π}$ is the normalized average state occupancy and $L_{i} (θ) = \sum_{s} d_{π_{i}} (s) ℓ (s, θ)$ is the true round loss.

[F2]

Dataset Aggregation (DAgger): ${\hat{L}}_{i} (θ) = \frac{1}{m T} \sum_{j = 1}^{m} \sum_{t = 0}^{T - 1} ℓ (S_{i j t}, θ)$ and $θ_{i + 1}$ minimizes $\sum_{r = 1}^{i} {\hat{L}}_{r}$ .

[F3]

Follow-the-Leader regret for bounded strongly convex losses: for bounded, $G$ -Lipschitz, $μ$ -strongly convex round losses with attained cumulative minima, empirical FTL regret is at most $1 + (4 G^{2} / μ) H_{N - 1}$ .

[F4]

Expert mixing changes finite-horizon state occupancy by at most the mixing mass: for every $g : S \to [0, 1]$ , the absolute difference between its mixed-policy and learner-policy occupancy expectations is at most $\min (1, T β_{i})$ .

[F5]

Azuma-Hoeffding inequality: under AC, martingale increments with predictable endpoints of width at most $c_{k}$ satisfy $P (M_{n} - M_{0} \geq t) \leq \exp (- 2 t^{2} / \sum_{k} c_{k}^{2})$ .

[F6]

Martingale difference sequence: a martingale difference is integrable, adapted, and has zero conditional mean given the preceding sigma-algebra.

[F7]

Martingales and martingale differences correspond: an adapted integrable martingale-difference sequence sums, from any integrable initial value, to a martingale.

[F8]

Filtration and filtered probability space: a filtered probability space has nested sigma-algebras $F_{n} \subseteq F_{n + 1}$ .

[F9]

Adapted and integrable stochastic process: adaptedness means time- $n$ measurability with respect to $F_{n}$ , and integrability means finite $E ∣ X_{n} ∣$ at each time.

[F10]

Martingale submartingale and supermartingale: an integrable adapted process is a martingale when $E [M_{n + 1} ∣ F_{n}] = M_{n}$ almost surely.

[F11]

Conditional expectation as an ae class: conditional expectations are unique almost-sure equivalence classes of measurable integrable versions.

[F12]

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

[F13]

Basic algebra and order properties of conditional expectation: conditional expectation is linear on integrable random variables.

[F14]

Conditioning a known variable and an independent variable: if an integrable variable is measurable with respect to the conditioning sigma-algebra, its conditional expectation is itself almost surely.

[F15]

Arithmetic and lattice operations preserve measurability whenever they are defined: finite sums and products of real-valued Borel-measurable functions are Borel measurable.

[F16]

The principle of mathematical induction: a property of positive integer indices that holds at the first index and is preserved by successors holds for every positive integer index.

[A1]

For every state, $ℓ (s, \cdot)$ is valued in $[0, 1]$ , $G$ -Lipschitz, and $μ$ -strongly convex on the nonempty convex set $K$ .

[A2]

All cumulative empirical-loss minima and the minimum defining ${\hat{ϵ}}_{N}$ are attained; the algorithm uses exact FTL updates.

[A3]

The per-sample conditional mean identity $E [{\overset{ˉ}{ℓ}}_{i j} (θ_{i}) ∣ F_{i, j - 1}] = L_{i} (θ_{i})$ holds almost surely, with $θ_{i}$ measurable before round $i$ and trajectory states measurable when revealed.

[A4]

$0 \leq β_{1} \leq 1$ and $0 \leq β_{i} \leq (1 - α)^{i - 1}$ for $i \geq 2$ , with fixed $0 < α \leq 1$ .

[A5]

For the rate corollary, $0 < δ \leq 1 / 2$ , while the main probability bound only requires $0 < δ < 1$ .

Proof

1.1A1A2F2F3algebra

For any realized sample sequence, ${\hat{L}}_{i}$ is a finite average of functions $ℓ (S_{i j t}, \cdot)$ , so [A1] makes it $[0, 1]$ -valued, $G$ -Lipschitz, and $μ$ -strongly convex on $K$ . By [F2] and [A2], the iterates are exact FTL iterates and the hindsight minimum is attained. Applying [F3] samplewise gives $\frac{1}{N} \sum_{i = 1}^{N} {\hat{L}}_{i} (θ_{i}) \leq {\hat{ϵ}}_{N} + \frac{1 + \frac{4 G^{2}}{μ} H_{N - 1}}{N}$ .

1.2A1A3F1F6F8F9F11F13F14F15construct

Flatten the pairs $(i, j)$ in round-major order. Put $G_{0} = F_{1, 0}$ and, for $r = (i - 1) m + j$ with $1 \leq i \leq N$ and $1 \leq j \leq m$ , put $G_{r} = F_{i, j}$ ; for every $r > m N$ , put $G_{r} = G_{m N}$ . Within each round the sigma-algebras are nested, and at round boundaries $F_{i, 0} = F_{i - 1, m}$ , so $(G_{r})_{r \geq 0}$ is an infinite filtration. Define $D_{(i - 1) m + j} = L_{i} (θ_{i}) - {\overset{ˉ}{ℓ}}_{i j} (θ_{i})$ for the sample indices and set $D_{r} = 0$ for $r > m N$ . For each fixed round $i$ , the policy probabilities are Borel functions of $θ$ , the finite occupancy recursion uses only finite sums and products, and $ℓ (s, \cdot)$ is continuous by its Lipschitz property. Thus [F15] makes $L_{i} (θ)$ Borel, so $L_{i} (θ_{i})$ is measurable with respect to $G_{(i - 1) m} = F_{i, 0}$ and hence with respect to each $G_{r - 1}$ in round $i$ . Since the state set is finite and each statewise loss is continuous, $(s, θ) \mapsto ℓ (s, θ)$ is measurable; the revealed states and preceding measurable parameter therefore make each ${\overset{ˉ}{ℓ}}_{i j} (θ_{i})$ measurable with respect to $G_{r}$ . By [A1] and the probability-occupancy property in [F1], both $L_{i} (θ_{i})$ and ${\overset{ˉ}{ℓ}}_{i j} (θ_{i})$ lie in $[0, 1]$ , so each sample increment is integrable and in $[- 1, 1]$ ; the zero extension has the same properties. For $r = (i - 1) m + j \leq m N$ , [A3], [F13], and [F14] give $E [D_{r} ∣ G_{r - 1}] = L_{i} (θ_{i}) - L_{i} (θ_{i}) = 0$ . For $r > m N$ , [F14] gives $E [0 ∣ G_{r - 1}] = 0$ . Thus $D$ is an infinite adapted martingale-difference sequence by [F6], using the filtration and process conventions [F8, F9, F11].

1.3A4F16algebrainduction

Put $q = 1 - α$ and $k = k_{α}$ . For every integer $n \geq 1$ , $(1 + α)^{n} \geq 1 + n α$ : equality holds for $n = 1$ , and if it holds for $n$ , then multiplication by $1 + α > 0$ gives $(1 + α)^{n + 1} \geq (1 + n α) (1 + α) = 1 + (n + 1) α + n α^{2} \geq 1 + (n + 1) α$ . Thus [F16] gives $(1 + α)^{k} \geq 1 + k α \geq 2$ . Also $q (1 + α) = 1 - α^{2} \leq 1$ , so $q \leq (1 + α)^{- 1}$ and $q^{k} \leq 1 / 2$ . For block $j \geq 0$ , let $I_{j} = {j k + 1, \dots, (j + 1) k}$ . If $j = 0$ , [A4] gives $β_{1} \leq 1 = q^{0}$ and $β_{i} \leq q^{i - 1} \leq 1$ for the other indices; if $j \geq 1$ , every $i \in I_{j}$ satisfies $β_{i} \leq q^{i - 1} \leq q^{j k}$ . Thus each block contributes at most $k \min (1, T 2^{- j})$ . Let $J = ⌈ N / k ⌉ - 1$ , so the blocks $j = 0, \dots, J$ cover all sample indices. Their terms with $j \leq q_{T}$ contribute at most $q_{T} + 1$ inside the sum over blocks. If $J \geq q_{T} + 1$ , the identity $2^{- j} = 2^{- (j - 1)} - 2^{- j}$ telescopes to $\sum_{j = q_{T} + 1}^{J} 2^{- j} = 2^{- q_{T}} - 2^{- J} \leq 2^{- q_{T}}$ ; if $J < q_{T} + 1$ , this tail is empty. Hence the remaining block contribution is at most $T 2^{- q_{T}} \leq 1$ , and $\sum_{i = 1}^{N} \min (1, T β_{i}) \leq k_{α} (q_{T} + 2)$ .

2.1A3F5F7F10F12step 1.2algebra

By [F7], $M_{0} = 0$ and $M_{r} = \sum_{k = 1}^{r} D_{k}$ form a martingale on the infinite filtration $(G_{r})$ . Its restriction to $r = 0, \dots, m N$ is the finite martingale required by [F5]. Each of its first $m N$ increments has predictable endpoints $- 1$ and $1$ , of width $2$ , so [F5] and the AC hypothesis [F12] give $P (M_{m N} \geq t) \leq \exp (- t^{2} / (2 m N))$ . Taking $t = \sqrt{2 m N \ln (1 / δ)}$ makes this probability at most $δ$ . Since $M_{m N} = m \sum_{i = 1}^{N} (L_{i} (θ_{i}) - {\hat{L}}_{i} (θ_{i}))$ , outside that event $\frac{1}{N} \sum_{i} L_{i} (θ_{i}) \leq \frac{1}{N} \sum_{i} {\hat{L}}_{i} (θ_{i}) + \sqrt{\frac{2 \ln (1 / δ)}{m N}}$ .

3.1A2step 1.1step 2.1algebra

On the event from step 2.1, combine its mixed-policy loss bound with step 1.1 to obtain $\frac{1}{N} \sum_{i} L_{i} (θ_{i}) \leq {\hat{ϵ}}_{N} + \frac{1 + \frac{4 G^{2}}{μ} H_{N - 1}}{N} + \sqrt{\frac{2 \ln (1 / δ)}{m N}}$ .

4.1A1F1F4step 2.1step 3.1step 1.3algebra

Apply both directions of the absolute occupancy estimate [F4] with $g (s) = ℓ (s, θ_{i})$ , giving $\sum_{s} d_{{\hat{π}}_{i}} (s) ℓ (s, θ_{i}) \leq L_{i} (θ_{i}) + \min (1, T β_{i})$ . Average over $i$ and use step 3.1 and step 1.3. At least one of the $N$ own-occupancy losses is no larger than their average, so on the event of step 2.1 some $i$ satisfies the displayed inequality in the Statement. Its probability is at least $1 - δ$ .

5.1A5step 4.1algebra∎

For the rate claim, set $L = \ln (1 / δ) \geq \ln 2$ and choose a fixed $C \geq 3 / \ln 2$ , so $N_{0} = C T^{2} L \geq 3 > e$ . With $c = 4 G^{2} / μ$ , for $N \geq 2$ we have $H_{N - 1} = 1 + \sum_{r = 2}^{N - 1} 1 / r \leq 1 + \sum_{r = 2}^{N - 1} \int_{r - 1}^{r} d x / x = 1 + \ln (N - 1) \leq 1 + \ln N$ , with the sum empty when $N = 2$ . The derivative of $x \mapsto [1 + c (1 + \ln x)] / x$ is $(c - 1 - c \ln x) / x^{2} \leq 0$ for $x \geq e$ , so for $N \geq N_{0}$ the FTL term is at most $[1 + c (1 + \ln N_{0})] / N_{0} = O ((1 + \ln T) / T^{2})$ , since $L \geq \ln 2$ and $(1 + \ln L) / L$ is bounded on $[\ln 2, \infty)$ . Also $q_{T} \leq 1 + \log_{2} T$ , so the mixing term is $O ((1 + \ln T) / T^{2})$ , while the Azuma term is at most $\sqrt{2 / (m C)} / T$ . As $1 + \ln T \leq T$ for $T \geq 1$ , the two former terms are $O (1 / T)$ as well. This proves the stated rate on the same event as step 4.1.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

49 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)
James A. Bagnell, Byron Boots, and Sanjiban Choudhury, Modern Adaptive Control and Reinforcement Learning, Chapter 6: An Invitation to Imitation (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)