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.

A candidate loss score that does not control task cost

Example

Let $S = {s}$ , $A (s) = {a^{*}, b}$ , and let both actions return deterministically to $s$ at every decision. For every time, set task costs $c_{t} (s, a^{*}) = 0$ and $c_{t} (s, b) = 1$ . Let the expert always choose $a^{*}$ , let the learner class contain both the expert and a learner that always chooses $b$ , and define a candidate loss score by $ℓ (s, θ) = 0$ for every class policy. Then the learner's score is zero under every state distribution, while its total task cost over horizon $T \geq 1$ is $T$ and the expert's task cost is zero. This score fails the required disagreement-domination condition $ℓ (s, θ) \geq \sum_{a \neq π^{*} (s)} π_{θ} (a ∣ s)$ , so the example does not contradict the DAgger task-cost lemma; it shows why that premise is necessary.

The diagram labels each deterministic self-transition by action/task-cost. The two actions have the same next state but different task costs.

diagram failed to render:
\begin{tikzpicture}[>=stealth]
  \node[draw,circle] (s) at (0,0) {$s$};
  \draw[->] (s) edge[loop above] node[above] {$a^*/0$} (s);
  \draw[->] (s) edge[loop below] node[below] {$b/1$} (s);
\end{tikzpicture}

Example references

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

Facts & Assumptions

Given: The one-state MDP, expert, learner, task costs, candidate loss score, and horizon in the Example.

[F1]

Finite-horizon imitation learning and expert-surrogate loss: the expert-action disagreement probability is $\sum_{a \neq π^{*} (s)} π_{θ} (a ∣ s)$ , and task cost is the finite-horizon expected sum of per-time costs.

[A1]

$T$ is an integer with $T \geq 1$ .

Verification

1.1F1A1given

The state is always $s$ under both policies, so every occupancy is the point mass at $s$ . By the defined candidate score, the learner's expected loss score is $ℓ (s, θ) = 0$ . Its disagreement probability is $1$ , so [F1]'s required domination premise fails.

2.1A1givenalgebra∎

At each of the $T$ decisions the learner pays cost $1$ , while the expert pays cost $0$ . Therefore $J (\hat{π}) = T$ and $J (π^{*}) = 0$ . Any unconditional claim that a zero candidate score alone forces $J (\hat{π}) \leq J (π^{*})$ would assert $T \leq 0$ , contradicting $T \geq 1$ .

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)