AlgorithmAlgorithm: Literature-sourcedProof: Not applicablePipeline-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.

Extended value iteration for a confidence set

Definition

Input finite nonempty state and action sets, upper reward estimates $\tilde{r} (s, a)$ , empirical transition laws $\hat{P} (\cdot ∣ s, a)$ , nonnegative transition radii $b_{p} (s, a)$ , a tolerance $ε > 0$ , and fixed orders of the states and actions for tie-breaking. For a vector $v \in R^{S}$ , write $span (v) = \max_{s} v (s) - \min_{s} v (s)$ and let $Δ (S)$ be the probability simplex on $S$ . Initialize $u_{0} (s) = 0$ . At iteration $i \geq 1$ , compute $u_{i} (s) = \max_{a \in A (s)} [\tilde{r} (s, a) + \max_{q \in Δ (S) : ∥ q - \hat{P} (\cdot ∣ s, a) ∥_{1} \leq b_{p} (s, a)} q \cdot u_{i - 1}] .$ For every state-action pair $(s, a)$ , run the following transfer routine using $v = u_{i - 1}$ . Put $q = \hat{P} (\cdot ∣ s, a)$ , $c = \min {1, b_{p} (s, a) / 2}$ , and order the states $x_{1}, \dots, x_{m}$ by nondecreasing $v (x_{j})$ , using the fixed state order to break ties. Set $j = 1$ and $ℓ = m$ . While $c > 0$ and $j < ℓ$ , advance $j$ while $q (x_{j}) = 0$ , then decrease $ℓ$ while $j < ℓ$ and $q (x_{ℓ}) = 1$ . If $j \geq ℓ$ , stop. If $v (x_{j}) \geq v (x_{ℓ})$ , stop. Otherwise set $d = \min {c, q (x_{j}), 1 - q (x_{ℓ})}$ , replace $q (x_{j})$ by $q (x_{j}) - d$ and $q (x_{ℓ})$ by $q (x_{ℓ}) + d$ , and replace $c$ by $c - d$ ; repeat. Call the resulting vector $q_{i, s, a}$ .

For each state, compute $B_{i} (s, a) = \tilde{r} (s, a) + q_{i, s, a} \cdot u_{i - 1}$ for every action, record the first action $a_{i} (s)$ in the fixed action order attaining $\max_{a \in A (s)} B_{i} (s, a)$ , and set $q_{i} (\cdot ∣ s) = q_{i, s, a_{i} (s)}$ . If $span (u_{i} - u_{i - 1}) < ε$ , return the stationary deterministic policy $π_{i} (s) = a_{i} (s)$ , its corresponding transition rows $q_{i}$ , the vector $u_{i - 1}$ used in that backup, and the iteration index. Otherwise continue. The procedure is partial unless a separate termination result applies.

Definition references

Bounded-reward finite MDP: provides the finite state/action sets and reward/transition laws.

EVI correctness and termination: proves that the transfer routine returns the exact row maximum and that positive radii give finite termination.

UCRL2 Extended Value Iteration: §3.1.2, Figure 2 and equation (5).

Average-reward value iteration discussion: Chapter 7, §§7.3–7.4.

Depends on

Finite MDP with bounded real rewards

Used by

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

Thomas Jaksch, Ronald Ortner, and Peter Auer, Near-optimal Regret Bounds for Reinforcement Learning (standard reference, not scraped)
Martin L. Puterman and Timothy C. Y. Chan, Markov Decision Processes and Reinforcement Learning, Chapter 7: Average Reward Models (standard reference, not scraped)