ExampleConstruction: AI-generatedVerification: 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.

Behavior cloning can incur quadratic cost under state-distribution shift

Example

Let the states be $g$ (good) and $b$ (bad), with initial state $S_{0} = g$ . At $g$ the actions are $c$ and $e$ ; action $c$ stays at $g$ with task cost $0$ , while action $e$ moves to $b$ with cost $1$ . At $b$ the actions are $r$ and $e$ ; action $r$ moves to $g$ with cost $0$ , while action $e$ stays at $b$ with cost $1$ . The transition is deterministic for every state/action pair. The deterministic expert chooses $c$ at $g$ and $r$ at $b$ . For a parameter $ϵ$ with $0 < ϵ \leq 1 / T$ , the learner chooses $e$ at $g$ with probability $ϵ$ and $c$ otherwise, and always chooses $e$ at $b$ . Use the statewise 0–1 expert-action disagreement as surrogate loss.

The diagram labels each deterministic transition by action/task-cost; the text specifies the two stochastic action probabilities of the learner. The expert occupancy is concentrated at $g$ , so the behavior-cloning disagreement loss on expert states is $ϵ$ . Under the learner, the expected total task cost is

$\sum_{k = 1}^{T} (1 - (1 - ϵ)^{k}),$

which lies between $ϵ T^{2} / 8$ and $ϵ T^{2}$ . Thus an $ϵ$ disagreement rate on expert states can correspond to quadratic-in- $T$ learner cost when a mistake moves the learner to states absent from expert demonstrations.

Example references

Ross, Gordon, and Bagnell, A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning: Theorem 2.1 and §2.1, PDF pp. 1–2.

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

Facts & Assumptions

Given: The two-state transition/task-cost model, expert, learner, horizon, and surrogate loss in the Example.

[F1]

Finite-horizon imitation learning and expert-surrogate loss: $d_{π}$ is the normalized average of the state distributions at times $0, \dots, T - 1$ , and an expert surrogate is a $[0, 1]$ -valued upper bound on the probability of taking an action different from the deterministic expert. The Example chooses the surrogate equal to that disagreement probability.

[A1]

$T \geq 1$ and $0 < ϵ \leq 1 / T$ .

Verification

1.1F1A1given

Under the expert, the state remains $g$ at every decision time, so $d_{π^{*}}$ is the point mass at $g$ . The learner's action-disagreement probability at $g$ is $ϵ$ , hence its behavior-cloning surrogate loss averaged under $d_{π^{*}}$ equals $ϵ$ .

1.2A1F1algebra

Put $q = 1 - ϵ$ . The probability that the learner is at $g$ at time $t$ is $q^{t}$ : it is $1$ at $t = 0$ , and if it is $g$ at time $t$ it remains there at the next state with probability $q$ , while if it is $b$ it remains $b$ . Thus the probability at time $t + 1$ is $q^{t} q = q^{t + 1}$ . At decision time $t$ , expected cost is $q^{t} ϵ + (1 - q^{t}) = 1 - q^{t + 1}$ . Summing for $t = 0, \dots, T - 1$ gives the displayed cost.

2.1A1step 1.2algebra

For each integer $k \geq 1$ , $(1 - ϵ)^{k} \geq 1 - k ϵ$ : the case $k = 1$ is equality, and if it holds at $k$ , multiplication by $1 - ϵ \geq 0$ gives $(1 - ϵ)^{k + 1} \geq (1 - k ϵ) (1 - ϵ) = 1 - (k + 1) ϵ + k ϵ^{2} \geq 1 - (k + 1) ϵ$ . Therefore $1 - q^{k} \leq k ϵ$ .

2.2A1step 1.2algebra

If $T = 1$ , the displayed cost is $ϵ$ , which lies between $ϵ T^{2} / 8$ and $ϵ T^{2}$ . Now assume $T \geq 2$ , so $0 < ϵ \leq 1 / 2$ . Then $(1 - ϵ)^{- 1} \geq 1 + ϵ$ because $(1 - ϵ)^{- 1} - (1 + ϵ) = ϵ^{2} / (1 - ϵ) \geq 0$ . Also $(1 + ϵ)^{k} \geq 1 + k ϵ$ for all $k \geq 1$ : it is equality for $k = 1$ , and multiplication by $1 + ϵ > 0$ gives $(1 + ϵ)^{k + 1} \geq (1 + k ϵ) (1 + ϵ) = 1 + (k + 1) ϵ + k ϵ^{2} \geq 1 + (k + 1) ϵ$ . Hence $q^{k} \leq 1 / (1 + k ϵ)$ . For $k \leq T$ , [A1] gives $k ϵ \leq 1$ , so $1 - q^{k} \geq k ϵ / (1 + k ϵ) \geq k ϵ / 2$ . Let $r = ⌈ T / 2 ⌉$ ; there are at least $T / 2$ integer indices from $r$ through $T$ , each at least $T / 2$ , so $\sum_{k = 1}^{T} k \geq T^{2} / 4$ . The expected cost is at least $ϵ T^{2} / 8$ .

3.1A1step 2.1step 2.2algebra∎

Summing the upper estimate $1 - q^{k} \leq k ϵ$ from step 2.1 gives cost at most $ϵ \sum_{k = 1}^{T} k \leq ϵ T^{2}$ . Together with the lower estimate from step 2.2, this proves the claimed bounds.

Depends on

Finite-horizon imitation learning and expert-surrogate loss

Used by

Nothing in the library uses this result yet.

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