DefinitionDefinition: Literature-sourcedProof: AI-generatedPipeline-generatedprecheck pendingjudge pass (gpt-6-luna)

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.

Model exploitation under support shift

Definition

Let $M = (S, (A (s))_{s \in S}, r, P)$ be a finite MDP with nonempty finite state set $S$ and nonempty finite action sets $A (s)$ . Its finite reward alphabet is contained in $[0, 1]$ , so $r (s, a) \in [0, 1]$ , and $P (\cdot ∣ s, a)$ is a probability distribution on $S$ for every admissible pair. Let $\hat{M} = (S, (A (s))_{s \in S}, \hat{r}, \hat{P})$ be a finite learned model on the same domain, with $\hat{r} (s, a) \in [0, 1]$ and a probability distribution $\hat{P} (\cdot ∣ s, a)$ on $S$ for every admissible pair. Set $D = {(s, a) : s \in S, a \in A (s)}$ . Let $B \subseteq D$ be the pairs observed at least once in a data set, fix a horizon $H \geq 1$ and initial state law $μ$ , and let $Π$ be any finite nonempty class of deterministic time-dependent Markov policies for that horizon. For a policy $π \in Π$ , compute its expected return under the true model and learned model using $d_{0} = μ$ ,

$d_{t + 1} (s^{'}) = \sum_{s} d_{t} (s) \sum_{a \in A (s)} π_{t} (a ∣ s) P (s^{'} ∣ s, a), J_{H} (π) = \sum_{t = 0}^{H - 1} \sum_{s} d_{t} (s) \sum_{a \in A (s)} π_{t} (a ∣ s) r (s, a),$

and analogously ${\hat{J}}_{H} (π)$ using $\hat{P}, \hat{r}$ . The learned-model occupancy of a pair $(s, a)$ at time $t$ is ${\hat{d}}_{t} (s) π_{t} (a ∣ s)$ . A model-optimal policy is any $\hat{π} \in Π$ attaining $\max_{π \in Π} {\hat{J}}_{H} (π)$ . Such a policy exploits the model off support relative to $B$ if it has positive learned-model occupancy on at least one pair in $D ∖ B$ , overestimates its own true return ${\hat{J}}_{H} (\hat{π}) > J_{H} (\hat{π})$ , and is truly suboptimal within $Π$ : $J_{H} (\hat{π}) < \max_{π \in Π} J_{H} (π)$ . This definition describes a failure mode; it is not a performance claim about every model optimizer.

Definition references

The true and learned models supply rewards, transition rows, and state-action pairs.

The occupancy recursion defines a finite-horizon expected return under a Markov policy.

Finite-horizon MPC chooses a first action by optimizing a learned-model finite-horizon return.

Levine, Kumar, Tucker, and Fu, Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems.

Sutton and Barto, Reinforcement Learning: An Introduction.

Facts & Assumptions

Given: The finite true/learned model pair, a finite data-supported pair set $B$ , horizon $H$ , initial law $μ$ , and a finite nonempty policy class $Π$ as in the Definition.

[F1]

Finite learned transition and reward models: both true and learned reward/transition tables are defined on the same finite state-action domain, with reward means in $[0, 1]$ and probability transition rows.

[F2]

Finite-horizon return under a Markov policy: the finite occupancy recursion and sum of expected rewards define $J_{H}$ under either model.

[F3]

Every nonempty finite set of reals has a maximum and a minimum: a finite nonempty set of real returns has an attained maximum.

Verification

Given: The data and finite policy class in the Definition.

1.1givenF1F2algebra

For each $π \in Π$ , [F1] supplies finite state/action tables and [F2] defines its occupancy recursion and return. Since rewards lie in $[0, 1]$ and the horizon is finite, both $J_{H} (π)$ and ${\hat{J}}_{H} (π)$ are real numbers in $[0, H]$ .

2.1givenF3step 1.1algebra∎

The sets of returns ${J_{H} (π) : π \in Π}$ and ${{\hat{J}}_{H} (π) : π \in Π}$ are finite and nonempty, so [F3] gives attained maxima. Pair membership in $B$ and positive occupancy are defined on finite sets, and the remaining exploitation conditions are comparisons of these finite real returns. Thus the model-optimal policy and off-support exploitation predicate in the Definition are well-defined.

Depends on

Used by

A one-step optimizer selects a falsely rewarding unsupported action Example

Dependency tree · two levels

15 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

Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu, Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems (standard reference, not scraped)
Richard S. Sutton and Andrew G. Barto, Reinforcement Learning: An Introduction, second-edition-in-progress (standard reference, not scraped)