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.

DAgger no-regret reduction under strongly convex surrogate losses

Statement

Consider the finite-horizon imitation-learning setting with deterministic expert $π^{*}$ , positive integer horizon $T$ , and expert surrogate $ℓ (s, θ) \in [0, 1]$ defined previously. Let $d \geq 1$ be an integer and let $K \subseteq R^{d}$ be nonempty and convex, with $∥ x - y ∥_{2} = (\sum_{r = 1}^{d} (x_{r} - y_{r})^{2})^{1 / 2}$ . Assume there are constants $μ > 0$ and $G \geq 0$ such that, uniformly in $s$ , $ℓ (s, \cdot)$ is $G$ -Lipschitz, meaning $∣ ℓ (s, x) - ℓ (s, y) ∣ \leq G ∥ x - y ∥_{2}$ , and is $μ$ -strongly convex on $K$ ; that is,

$ℓ (s, (1 - λ) x + λ y) \leq (1 - λ) ℓ (s, x) + λ ℓ (s, y) - \frac{μ}{2} λ (1 - λ) ∥ x - y ∥_{2}^{2}$

for all $x, y \in K$ and $λ \in [0, 1]$ . Run the population-loss version of DAgger for a positive integer $N$ rounds with exact FTL updates, and assume each cumulative population loss attains its minimum on $K$ . Let $β_{i} \in [0, 1]$ satisfy $β_{1} \leq 1$ and $β_{i} \leq (1 - α)^{i - 1}$ for $2 \leq i \leq N$ , where $α \in (0, 1]$ is fixed independently of $T$ and $N$ . Suppose $u \geq 0$ satisfies $Q_{t}^{*} (s, a) - V_{t}^{*} (s) \leq u$ for every time $t$ , state $s$ , and admissible action $a$ .

Let $L_{i} (θ) = \sum_{s} d_{π_{i}} (s) ℓ (s, θ)$ be the true round- $i$ loss under the mixed rollout policy, and let $ϵ_{N} = \min_{θ \in K} N^{- 1} \sum_{i = 1}^{N} L_{i} (θ)$ , with the minimum attained. Define $H_{0} = 0$ , $H_{n} = \sum_{j = 1}^{n} 1 / j$ , 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 some learned policy $\hat{π} \in {{\hat{π}}_{1}, \dots, {\hat{π}}_{N}}$ satisfies

$J (\hat{π}) \leq J (π^{*}) + u T [ϵ_{N} + \frac{1 + \frac{4 G^{2}}{μ} H_{N - 1} + k_{α} (q_{T} + 2)}{N}] .$

In particular, the additive term beyond $u T ϵ_{N}$ is at most $1$ whenever $N \geq u T (1 + \frac{4 G^{2}}{μ} H_{N - 1} + k_{α} (q_{T} + 2))$ . For fixed $α, μ, G$ and a valid scale $u \geq 1$ , the sufficient iteration count is $\tilde{O} (u T)$ because $H_{N - 1}$ and $q_{T}$ grow logarithmically. If a valid one-step bound has $u < 1$ , it may be enlarged to $1$ for this iteration-count corollary; the exact inequality above remains valid with the original $u$ . This is an infinite-sample statement: expert labels must be obtained by interaction on states visited under $π_{i}$ .

Statement references

Finite-horizon imitation learning and expert-surrogate loss: defines task cost, finite-horizon state occupancy, surrogate disagreement domination, mixed rollout losses, and $ϵ_{N}$ .

Dataset Aggregation (DAgger): population-loss FTL updates, expert/learner mixture, and interactive expert labels.

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

Expert mixing changes finite-horizon state occupancy by at most the mixing mass: a bounded state loss changes by at most $\min (1, T β_{i})$ between the mixed and learner occupancies.

Expert-surrogate loss bounds finite-horizon task-cost increase: task-cost increase is at most $u T$ times the learner's own-occupancy surrogate loss.

Ross, Gordon, and Bagnell, A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning: Theorems 3.1–3.2 and §4.2, PDF pp. 3–4.

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.

Facts & Assumptions

Given: The finite-horizon MDP and expert definitions, uniform bounded strongly convex Lipschitz surrogate, exact population FTL updates, geometric expert-use schedule, attained minimum defining $ϵ_{N}$ , and one-step expert cost-to-go bound in the Statement.

[F1]

Finite-horizon imitation learning and expert-surrogate loss: $d_{π}$ is the normalized average state occupancy; $L_{i} (θ) = \sum_{s} d_{π_{i}} (s) ℓ (s, θ)$ ; the surrogate upper-bounds action disagreement; and $J (π)$ is finite-horizon expected task cost.

[F2]

Dataset Aggregation (DAgger): at round $i$ , DAgger rolls out $π_{i} = β_{i} π^{*} + (1 - β_{i}) {\hat{π}}_{i}$ , obtains expert labels on visited states, and sets $θ_{i + 1}$ to an attained minimizer of the cumulative losses.

[F3]

Follow-the-Leader regret for bounded strongly convex losses: for the stated bounded $μ$ -strongly convex $G$ -Lipschitz losses, $\sum_{i} L_{i} (θ_{i}) - N ϵ_{N} \leq 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})$ ; in particular, either expectation is at most the other plus this error.

[F5]

Expert-surrogate loss bounds finite-horizon task-cost increase: $J ({\hat{π}}_{i}) - J (π^{*}) \leq u T \sum_{s} d_{{\hat{π}}_{i}} (s) ℓ (s, θ_{i})$ .

[A1]

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

[A2]

Every cumulative population loss attains its minimum on $K$ , and the minimum defining $ϵ_{N}$ is attained.

[A3]

The expert-use schedule satisfies $0 \leq β_{1} \leq 1$ and $0 \leq β_{i} \leq (1 - α)^{i - 1}$ for $2 \leq i \leq N$ , with fixed $0 < α \leq 1$ .

[A4]

The expert cost-to-go gap satisfies $Q_{t}^{*} (s, a) - V_{t}^{*} (s) \leq u$ for every time, state, and admissible action, with $u \geq 0$ .

Proof

1.1A1A2F1F2F3algebra

Since $L_{i}$ is the finite probability-weighted average of the statewise losses, averaging the uniform strong-convexity inequality and the $G$ -Lipschitz inequality in [A1] over $d_{π_{i}}$ shows that each $L_{i}$ is $μ$ -strongly convex, $G$ -Lipschitz, and valued in $[0, 1]$ . The exact FTL updates [F2], attained minima [A2], and bound [F3] therefore give $\frac{1}{N} \sum_{i = 1}^{N} L_{i} (θ_{i}) \leq ϵ_{N} + \frac{1 + \frac{4 G^{2}}{μ} H_{N - 1}}{N}$ .

1.2A3F2algebra

Let $q = 1 - α$ and $k = k_{α}$ . Since $(1 - α) (1 + α) = 1 - α^{2} \leq 1$ , $q \leq (1 + α)^{- 1}$ . For every integer $n \geq 1$ , $(1 + α)^{n} \geq 1 + n α$ : it is equality at $n = 1$ , and multiplying the inductive inequality by $1 + α > 0$ gives $(1 + α)^{n + 1} \geq 1 + (n + 1) α + n α^{2} \geq 1 + (n + 1) α$ . Thus $(1 + α)^{k} \geq 1 + k α \geq 2$ and $q^{k} \leq 1 / 2$ . Partition indices $i$ into blocks $i = j k + r + 1$ with $j \geq 0$ and $0 \leq r < k$ . On block $j$ , [A3] gives $\min (1, T β_{i}) \leq \min (1, T q^{j k}) \leq \min (1, T 2^{- j})$ . Hence $\sum_{i = 1}^{N} \min (1, T β_{i}) \leq k \sum_{j = 0}^{\infty} \min (1, T 2^{- j}) \leq k (q_{T} + 2)$ , because the first $q_{T} + 1$ terms are at most $1$ and the remaining geometric tail is $T \sum_{j = q_{T} + 1}^{\infty} 2^{- j} = T 2^{- q_{T}} \leq 1$ .

1.3F3algebraconstruct

For every positive integer $n$ , let $q_{n}$ be the least nonnegative integer with $n \leq 2^{q_{n}}$ . If $N = 1$ , then $H_{N - 1} = 0 \leq 1 + q_{N}$ . If $N \geq 2$ , group $H_{N - 1}$ into the initial term $1$ and blocks $2^{j - 1} < r \leq 2^{j}$ , $1 \leq j \leq q_{N}$ . Each block has at most $2^{j - 1}$ terms, each at most $2^{- (j - 1)}$ , so $H_{N - 1} \leq 1 + q_{N}$ . These dyadic lengths grow logarithmically in their arguments.

2.1A2F1F2F4step 1.1algebra

For each round, apply the absolute-value estimate [F4] to $g (s) = ℓ (s, θ_{i}) \in [0, 1]$ , using its direction $\sum_{s} d_{{\hat{π}}_{i}} (s) g (s) \leq L_{i} (θ_{i}) + \min (1, T β_{i})$ . Averaging over $i$ and using step 1.1 yields $\frac{1}{N} \sum_{i = 1}^{N} \sum_{s} d_{{\hat{π}}_{i}} (s) ℓ (s, θ_{i}) \leq ϵ_{N} + \frac{1 + \frac{4 G^{2}}{μ} H_{N - 1}}{N} + \frac{1}{N} \sum_{i = 1}^{N} \min (1, T β_{i})$ .

3.1F2step 1.2step 2.1algebra

By step 1.2 and step 2.1, the average own-occupancy surrogate loss of the finite sequence ${\hat{π}}_{1}, \dots, {\hat{π}}_{N}$ is at most $ϵ_{N} + \frac{1 + \frac{4 G^{2}}{μ} H_{N - 1} + k_{α} (q_{T} + 2)}{N}$ . At least one member ${\hat{π}}_{i}$ has own-occupancy surrogate loss no larger than this average, because otherwise every term in the finite average would be strictly larger than the average.

4.1A4F5step 3.1algebra

Apply the one-step assumption [A4] through [F5] to that index $i$ and substitute the bound from step 3.1. This gives the stated task-cost inequality.

5.1A1A3A4step 1.3step 4.1algebra∎

If $N \geq u T (1 + \frac{4 G^{2}}{μ} H_{N - 1} + k_{α} (q_{T} + 2))$ , then the additive term in the Statement is at most $1$ . To verify the iteration order, set $\overset{ˉ}{u} = \max (1, u)$ and $B = \overset{ˉ}{u} T \geq 1$ ; let $b = ⌈ B ⌉$ and let $Q$ be the least integer with $b + T + 2 \leq 2^{Q}$ . Choose an integer $C \geq 1$ and set $N = ⌈ C b Q ⌉$ . Since $b \leq 2^{Q}$ and $Q \leq 2^{Q}$ , $N \leq (C + 1) 2^{2 Q}$ , so the least $q_{N}$ with $N \leq 2^{q_{N}}$ satisfies $q_{N} \leq 2 Q + q_{C + 1}$ . By step 1.3 and $q_{T} \leq Q$ , the bracket is at most $1 + \frac{4 G^{2}}{μ} (2 Q + q_{C + 1} + 1) + k_{α} (Q + 2)$ . Set $c = 4 G^{2} / μ$ , $a = 2 c + k_{α}$ , $b_{0} = c$ , and $b_{1} = 1 + c + 2 k_{α}$ ; the bracket bound equals $a Q + b_{0} q_{C + 1} + b_{1}$ . Choose an integer $r \geq 2$ so large that $r (r - 1) / 2 \geq a + b_{0} (r + 1) + b_{1}$ ; such an $r$ exists because the left side is quadratic with positive leading coefficient and the right side is affine in $r$ . The binomial theorem gives $C : = 2^{r} \geq r (r - 1) / 2$ , while $C + 1 \leq 2^{r + 1}$ gives $q_{C + 1} \leq r + 1$ . Hence $C \geq a + b_{0} q_{C + 1} + b_{1}$ . Since $Q \geq 1$ and $a, b_{0}, b_{1} \geq 0$ , $C Q \geq (a + b_{0} q_{C + 1} + b_{1}) Q \geq a Q + b_{0} q_{C + 1} + b_{1}$ ; as $b \geq B$ , this gives $N \geq C b Q \geq B (a Q + b_{0} q_{C + 1} + b_{1})$ . Thus $N \geq \overset{ˉ}{u} T$ times the bracket, which also implies the required inequality with $u$ . Moreover $Q = O (\log (B + 2))$ , so $N = O (B \log (B + 2)) = \tilde{O} (\overset{ˉ}{u} T)$ . When $u \geq 1$ , this is $\tilde{O} (u T)$ ; if $u < 1$ , replacing it by $\overset{ˉ}{u} = 1$ is a valid upper-bound normalization for the iteration count. The estimate retains the hindsight optimum $ϵ_{N}$ and assumes no realizability condition $π^{*} \in Π$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

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