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.

✓ 8 results · all verified · 0 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 8 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Optimistic exploration and PAC-MDP sample complexity

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

DefinitionDefinition: Literature-sourcedProof: Not applicableOpen item page →

Finite discounted MDP with bounded real rewards

Definition

Let $S$ be a nonempty finite set, let $A (s)$ be a nonempty finite set for each $s \in S$ , and let $D = {(s, a) : s \in S, a \in A (s)}$ . Here finite means bijective with a natural number. Put $S_{0} = ∣ S ∣$ and $A_{0} = \max_{s \in S} ∣ A (s) ∣$ . Fix a discount $0 \leq γ < 1$ . Give $S$ and $D$ their discrete sigma-algebras and give $[0, 1]$ its Borel sigma-algebra. A bounded-reward finite discounted Markov decision process is a probability kernel $K$ from $D$ to $S \times [0, 1]$ . At pair $(s, a)$ , $K (\cdot ∣ s, a)$ is the joint law of the next state and the reward; these two coordinates need not be independent. Define the state-transition probabilities and expected rewards by

$P (s^{'} ∣ s, a) = K ({s^{'}} \times [0, 1] ∣ s, a), r (s, a) = \int_{S \times [0, 1]} ρ K (d s^{'}, d ρ ∣ s, a) .$

A history-dependent behavior is a sequence of probability kernels from observed-history spaces $H_{t}$ to the finite action alphabet $A = ⋃_{s \in S} A (s)$ , assigning probability zero to actions outside $A (s_{t})$ at every history ending in state $s_{t}$ . Here $H_{t}$ consists of histories $(s_{0}, a_{0}, R_{1}, s_{1}, \dots, a_{t - 1}, R_{t}, s_{t})$ , with discrete sigma-algebras on finite state/action coordinates and the Borel sigma-algebra on each reward coordinate; it has the resulting finite-product sigma-algebra. A stationary Markov policy assigns one distribution on $A (s)$ to each state, independently of earlier history. During interaction, after choosing $a_{t}$ in state $s_{t}$ , the next pair $(s_{t + 1}, R_{t + 1})$ is drawn from $K (\cdot ∣ s_{t}, a_{t})$ .

Definition references

Finite state/action sets, admissible pairs, and the joint next-state/reward convention; this item replaces its finite reward-alphabet restriction by a Borel law on the unit interval.

A probability kernel assigns a probability measure at every state-action input and has measurable event sections.

The Borel sigma-algebra is generated by the open sets of a topological space.

The product sigma-algebra is generated by measurable rectangles.

The state-reward sample space is a Cartesian product.

Expectation is the Lebesgue integral of a measurable random variable.

The reward-coordinate projection is measurable: the inverse image of a Borel set $B \subseteq [0, 1]$ is the measurable rectangle $S \times B$ . Since $0 \leq ρ \leq 1$ , monotonicity of the nonnegative integral gives $0 \leq \int ρ d K \leq \int 1 d K = K (S \times [0, 1]) = 1$ .

Strehl, Li, and Littman, Reinforcement Learning in Finite MDPs: PAC Analysis.

Szepesvári, Algorithms for Reinforcement Learning.

Sutton and Barto, Reinforcement Learning: An Introduction.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passOpen item page →

Well-defined discounted values and optimal Bellman fixed points

Statement

Assume the Axiom of Choice. In every bounded-reward finite discounted Markov decision process with nonempty finite state set $S$ , nonempty finite action sets $A (s)$ , and $0 \leq γ < 1$ , the trajectory law of every history-dependent behavior from every starting state exists. Its discounted return is measurable, integrable, and between $0$ and $1 / (1 - γ)$ . For each stationary policy $π$ , its value $V^{π}$ satisfies its Bellman equation. The optimality operator

$T^{*} V (s) = \max_{a \in A (s)} [r (s, a) + γ \sum_{s^{'} \in S} P (s^{'} ∣ s, a) V (s^{'})]$

is a $γ$ contraction in the supremum norm, meaning $∥ T^{*} V - T^{*} W ∥_{\infty} \leq γ ∥ V - W ∥_{\infty}$ for all $V, W : S \to R$ , where $∥ V ∥_{\infty} = \max_{s \in S} ∣ V (s) ∣$ , and has a unique fixed point $V^{*}$ . This fixed point is the supremum of the values of all history-dependent behaviors and is attained by a deterministic stationary greedy policy. The optimal action value is

$Q^{*} (s, a) = r (s, a) + γ \sum_{s^{'} \in S} P (s^{'} ∣ s, a) V^{*} (s^{'}),$

and $V^{*} (s) = \max_{a \in A (s)} Q^{*} (s, a)$ with $Q^{*} (s, a) \geq 0$ .

Statement references

The finite state/action model, joint transition-reward kernel, and discounted interaction convention.

The Axiom of Choice, required by the countable path-law construction.

History-dependent probability kernels determine a unique infinite path law under AC.

Strehl, Li, and Littman, Reinforcement Learning in Finite MDPs: PAC Analysis.

Szepesvári, Algorithms for Reinforcement Learning.

Facts & Assumptions

Given: A nonempty finite state set $S$ , nonempty finite action sets $A (s)$ , a probability kernel $K$ on $S \times [0, 1]$ for each admissible pair, and a discount $0 \leq γ < 1$ .

[F1]

Finite discounted MDP with bounded real rewards supplies $0 \leq R_{t + 1} \leq 1$ , state-transition probabilities $P (\cdot ∣ s, a)$ summing to one, expected rewards $r (s, a) \in [0, 1]$ , and measurable history-dependent behavior kernels.

[A1]

The Axiom of Choice is assumed for the infinite path-law existence theorem; the Bellman fixed-point and finite maximization arguments below use no arbitrary-index choice.

[F2]

Ionescu-Tulcea construction of a Markov chain: under AC, a starting law and a sequence of history-dependent probability kernels determine a probability law with the specified finite-prefix laws.

[F3]

Sequential suprema, infima, limsup, liminf, and pointwise limits of measurable functions are measurable: a pointwise limit of measurable real functions is measurable. Expectation of a nonnegative or integrable random variable defines expectation as the corresponding Lebesgue integral.

[F4]

For $∣ r ∣ < 1$ , $\sum_{k \geq 0} r^{k} = 1 / (1 - r)$ , and for $∣ r ∣ \geq 1$ the series diverges: for $0 \leq γ < 1$ , $\sum_{j = 0}^{n - 1} γ^{j} \leq 1 / (1 - γ)$ and $\sum_{j = n}^{\infty} γ^{j} = γ^{n} / (1 - γ)$ .

[F5]

Monotone convergence for the integral: an increasing sequence of nonnegative measurable functions has integrals increasing to the integral of its pointwise limit.

[F6]

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

[F7]

Laws of finite sums and finite products and Triangle inequality for finite sums: finite sums preserve termwise inequalities and scaling and satisfy the triangle inequality.

[F8]

The reals are complete: every Cauchy sequence of real numbers has a real limit.

[F9]

Finite, countably infinite, countable, uncountable defines a finite set as one bijective with a natural number, and Every natural-number-indexed list of nonempty sets has a choice function on its family of values constructs a choice function for any natural-number-indexed finite family of nonempty sets without AC.

[F10]

The Lebesgue integral is linear on $L^{1} (μ)$ , Change of variables for expectation, Expectation agrees with the published finite weighted sum, and Monotonicity and nonnegative homogeneity of the nonnegative integral: for every admissible pair and every real vector $v : S \to R$ , the bounded terms are integrable, inequalities between nonnegative integrands pass through the integral, and $\int_{S \times [0, 1]} (ρ + γ v (s^{'})) K (d s^{'}, d ρ ∣ s, a) = r (s, a) + γ \sum_{s^{'} \in S} P (s^{'} ∣ s, a) v (s^{'}) .$ The integral splits by linearity; the second term is the expectation of the finite-valued next-state function, evaluated using its marginal law $P (\cdot ∣ s, a)$ and the finite weighted-sum formula. The same formula evaluates a probability distribution on any finite action set.

Proof

1.1givenF1F2A1construct

Fix a starting state and a history-dependent behavior, and write $D = {(s, a) : a \in A (s)}$ as in [F1]. For a history $h_{t}$ ending at state $s$ and a measurable set $E \subseteq D \times S \times [0, 1]$ , define $Λ_{t} (h_{t}, E) = \sum_{a \in A (s)} π_{t} (a ∣ h_{t}) \int 1_{E} ((s, a), s^{'}, ρ) K (d s^{'}, d ρ ∣ s, a)$ . For each fixed $a$ , the integrand section is measurable by the product sigma-algebra, and the finite weighted sum is measurable in $h_{t}$ because $π_{t}$ is a probability kernel; its total mass is $\sum_{a} π_{t} (a ∣ h_{t}) = 1$ . Thus $Λ_{t}$ is a probability kernel from histories to the fixed space $D \times S \times [0, 1]$ . Applying [F2] to this sequence of history kernels and the initial point mass gives the full interaction path law.

1.2givenF1F7algebra

For a stationary policy $π$ , define $T_{π} v (s) = \sum_{a \in A (s)} π (a ∣ s) [r (s, a) + γ \sum_{s^{'}} P (s^{'} ∣ s, a) v (s^{'})]$ . This is a real vector by the finite sums. For any $v, w : S \to R$ , the absolute difference of each bracketed backup is at most $γ \sum_{s^{'}} P (s^{'} ∣ s, a) ∣ v (s^{'}) - w (s^{'}) ∣ \leq γ ∥ v - w ∥_{\infty}$ . Averaging over $π (a ∣ s)$ preserves this bound, so $∥ T_{π} v - T_{π} w ∥_{\infty} \leq γ ∥ v - w ∥_{\infty}$ .

1.3F1F6F7algebra

For finite real lists $(x_{a})$ and $(y_{a})$ , if $m = \max_{a} ∣ x_{a} - y_{a} ∣$ , then $x_{a} \leq y_{a} + m$ and $y_{a} \leq x_{a} + m$ for every $a$ , whence $∣ \max_{a} x_{a} - \max_{a} y_{a} ∣ \leq m$ . Applying this and [F7] to the definition of $T^{*}$ gives $∥ T^{*} v - T^{*} w ∥_{\infty} \leq γ ∥ v - w ∥_{\infty}$ . The operator maps $[0, 1 / (1 - γ)]^{S}$ into itself because rewards are in $[0, 1]$ and transition probabilities sum to one.

2.1step 1.1F3F4F5

Each reward coordinate on the product path space is measurable and lies in $[0, 1]$ . The finite partial discounted sums are measurable, increase pointwise, and are bounded above by $\sum_{j < n} γ^{j} \leq 1 / (1 - γ)$ by [F4]. Their pointwise limit is measurable by [F3] and has the same bound. By [F5] its expectation is the limit of the finite partial expectations and is finite; thus every behavior value is well-defined and lies in the stated interval.

2.2givenF1F2step 1.1step 1.2F7F10

For a stationary policy $π$ , let $v_{n}^{π} (s)$ be the expected sum of its first $n$ discounted rewards from $s$ , with $v_{0}^{π} = 0$ . The finite-prefix law from step 1.1 and conditioning on the first action and joint reward/next-state outcome give $v_{n + 1}^{π} (s) = \sum_{a} π (a ∣ s) \int [ρ + γ v_{n}^{π} (s^{'})] K (d s^{'}, d ρ ∣ s, a)$ . Apply [F10] to each integral to obtain $v_{n + 1}^{π} (s) = \sum_{a} π (a ∣ s) [r (s, a) + γ \sum_{s^{'}} P (s^{'} ∣ s, a) v_{n}^{π} (s^{'})] = T_{π} v_{n}^{π} (s)$ ; the finite action distribution is evaluated by the same finite weighted-sum formula in [F10]. The joint law allows dependence between reward and next state; the integral identity does not assume independence.

2.3step 1.3F4F8inductionalgebra

Start with $v_{0} = 0$ and set $v_{n + 1} = T^{*} v_{n}$ . Since $0 \leq v_{1} \leq 1$ and $T^{*}$ is a $γ$ contraction, induction gives $∥ v_{n + 1} - v_{n} ∥_{\infty} \leq γ^{n}$ . Thus for $m > n$ , $∥ v_{m} - v_{n} ∥_{\infty} \leq \sum_{j = n}^{m - 1} γ^{j} \leq γ^{n} / (1 - γ)$ ; every coordinate is Cauchy and converges by [F8], uniformly because $S$ is finite. Its limit $v^{*}$ is a fixed point by the finite-sum/max formula and the contraction estimate. If $w^{*}$ were another fixed point, step 1.3 would give $∥ v^{*} - w^{*} ∥_{\infty} \leq γ ∥ v^{*} - w^{*} ∥_{\infty}$ , so $v^{*} = w^{*}$ .

3.1step 2.1step 2.2step 1.2F4F7

The finite-horizon stationary-policy values converge to $V^{π}$ by step 2.1 and the geometric tail bound [F4]. Passing their finite recursions from step 2.2 to the limit is valid because each sum is finite and the maximum statewise error tends to zero; hence $T_{π} V^{π} = V^{π}$ . If two fixed points existed, step 1.2 would give their distance at most $γ$ times itself, forcing equality.

3.2givenF1F6F7F10step 2.3induction

We prove by induction on $n$ that, from every starting history ending at state $s$ , every history-dependent continuation has $n$ -reward expected discounted return at most $v_{n} (s)$ from step 2.3. The base $v_{0} = 0$ is the empty-horizon return. For the successor step, condition on the first chosen action and the joint next-state/reward outcome $(s^{'}, ρ)$ . The induction hypothesis applies to the extended history ending at $s^{'}$ , so its continuation return is pointwise at most $v_{n} (s^{'})$ , even when its action rule used the observed reward $ρ$ . For each first action, monotonicity of integration and [F10] bound the conditional expected total by $r (s, a) + γ \sum_{s^{'}} P (s^{'} ∣ s, a) v_{n} (s^{'})$ . Averaging over the randomized first action by the finite weighted-sum formula in [F10] is at most its finite maximum, namely $T^{*} v_{n} (s) = v_{n + 1} (s)$ . Thus the claimed upper bound holds uniformly over histories and behaviors.

3.3step 2.1step 2.3F4F5algebra

For any behavior, its omitted tail after $n$ rewards is at most $γ^{n} / (1 - γ)$ by [F4]. Therefore its infinite-horizon value is at most $v_{n} (s) + γ^{n} / (1 - γ)$ . Letting $n \to \infty$ and using step 2.3 proves that every behavior value is at most $v^{*} (s)$ .

4.1step 1.1step 2.3step 3.1step 3.3F1F6F9algebra∎

For each $s$ , let $B_{s}$ be the nonempty finite set of actions attaining the maximum in $T^{*} v^{*} (s)$ . By [F9] and the finiteness of $S$ , choose one member of each $B_{s}$ without AC; these choices define a deterministic stationary policy $π^{*}$ . It satisfies $T_{π^{*}} v^{*} = T^{*} v^{*} = v^{*}$ , so step 3.1 and uniqueness imply $V^{π^{*}} = v^{*}$ . Together with step 3.3 this proves $v^{*} = V^{*}$ and attainment. After forcing a first action $a$ and then following $π^{*}$ , the expected return is $r (s, a) + γ \sum_{s^{'}} P (s^{'} ∣ s, a) V^{*} (s^{'})$ . Any other continuation after that first action is bounded by $V^{*} (s^{'})$ at each next state by step 3.3, so this is the maximal value with first action fixed to $a$ , namely $Q^{*} (s, a)$ . Its maximum over $a$ is $V^{*} (s)$ , and it is nonnegative by [F1]. AC is used only for the path law in step 1.1.

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passOpen item page →

Concentration for adaptively sampled MDP observations

Statement

Assume AC and fix a bounded-reward finite discounted MDP with state set $S$ . For each admissible pair $(s, a)$ , let $(S_{i}^{'}, R_{i})_{i \geq 1}$ be an independent potential stream with common joint law $K (\cdot ∣ s, a)$ ; an interaction reveals the next unused sample from that pair's stream only when the pair is visited. This construction has the same finite-trajectory law as interaction with the MDP under any history-dependent behavior. For a fixed pair and $m \geq 1$ , its reward samples satisfy $P ⁣ (∣ \frac{1}{m} \sum_{i = 1}^{m} R_{i} - r (s, a) ∣ > x) \leq 2 e^{- 2 m x^{2}} (x > 0) .$ If ${\hat{P}}_{m}$ is the empirical distribution of $S_{1}^{'}, \dots, S_{m}^{'}$ and $P (\cdot ∣ s, a)$ is the true next-state marginal, then $E ∥ {\hat{P}}_{m} - P (\cdot ∣ s, a) ∥_{1} \leq \sqrt{\frac{∣ S ∣}{m}}, P ⁣ (∥ {\hat{P}}_{m} - P (\cdot ∣ s, a) ∥_{1} > \sqrt{\frac{∣ S ∣}{m}} + \sqrt{\frac{2 \ln (1 / δ)}{m}}) \leq δ (0 < δ < 1),$ where $∥ q ∥_{1} = \sum_{s^{'} \in S} ∣ q (s^{'}) ∣$ and $\ln$ is the natural logarithm. More generally, for a filtration $(F_{i})_{i = 0}^{m}$ , if $Y_{i}$ is $F_{i}$ -measurable, $0 \leq Y_{i} \leq B$ , and $μ_{i} = E [Y_{i} ∣ F_{i - 1}]$ , then $P ⁣ (∣ \sum_{i = 1}^{m} (Y_{i} - μ_{i}) ∣ \geq m x) \leq 2 e^{- 2 m x^{2} / B^{2}} (B > 0, x > 0) .$ No independence between reward and next state within a single transition is assumed. The confidence bounds are for a fixed deterministic sample size or a fixed-size batch; this item makes no uniform confidence claim at a data-dependent sample count. At a finite history-dependent visit count, the next fixed number of unused potential outcomes still has its conditional iid law.

Statement references

The joint next-state/reward law and the finite state-action domain.

The Axiom of Choice used for the infinite potential-stream construction and conditional-expectation suppliers.

A sequence of probability kernels has a unique infinite product path law under AC.

Conditional exponential-moment bound for bounded martingale differences with predictable endpoints.

Two-sided concentration for martingale increments with predictable bounded ranges.

Strehl, Li, and Littman, Reinforcement Learning in Finite MDPs: PAC Analysis.

Szepesvári, Algorithms for Reinforcement Learning.

Facts & Assumptions

Given: AC; a bounded-reward finite discounted MDP; a fixed state-action pair for the empirical estimates; and, in the final clause, a filtration and predictable bounded target sequence.

[F1]

Finite discounted MDP with bounded real rewards: the pair's joint next-state/reward law is $K (\cdot ∣ s, a)$ , rewards lie in $[0, 1]$ , and the next-state marginal is a probability distribution on the finite set $S$ .

[F2]

The Axiom of Choice: every family of nonempty sets has a choice function; AC is assumed here for the countable product law and the conditional-expectation classes.

[F3]

Finite, countably infinite, countable, uncountable and Ionescu-Tulcea construction of a Markov chain: the finite pair set can be enumerated, and a countable sequence of probability kernels admits the specified product law with the prescribed finite-prefix laws under AC.

[F4]

Basic algebra and order properties of conditional expectation: conditional expectation preserves order and constants, so $0 \leq E [Y_{i} ∣ F_{i - 1}] \leq B$ for $0 \leq Y_{i} \leq B$ .

[F5]

Conditional Hoeffding bound for bounded martingale differences: if $D \in L^{1}$ , $E [D ∣ G] = 0$ , and finite $G$ -measurable endpoints $A \leq D \leq C$ have deterministic width at most $b$ , then $E [e^{λ D} ∣ G] \leq e^{λ^{2} b^{2} / 8}$ .

[F6]

Tower property of conditional expectation and Taking out what is known: conditional expectations iterate through a filtration, and a finite measurable factor can be taken outside when the products are integrable.

[F7]

Markov's inequality for random variables: for nonnegative $Z$ and $c > 0$ , $P (Z \geq c) \leq E [Z] / c$ .

[F8]

Azuma-Hoeffding inequality: if a martingale has predictable increment endpoints of widths $c_{i}$ , each one-sided tail is bounded by $\exp (- 2 t^{2} / \sum_{i} c_{i}^{2})$ .

[F9]

Cauchy-Schwarz for random variables: $E ∣ X ∣ \leq (E [X^{2}])^{1 / 2}$ when $X \in L^{2}$ ; Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation gives $\sum_{j} \sqrt{p_{j}} \leq \sqrt{∣ S ∣}$ for a probability vector on $S$ .

[F10]

Filtration and filtered probability space and Martingale difference sequence: the visit/sample history is an increasing filtration, and a centered integrable adapted increment is a martingale difference relative to it.

[F11]

The finite union bound: the probability of a finite union of events is at most the sum of their probabilities.

Proof

1.1givenF1F2F3construct

Enumerate the finite pair set $D$ . For each $d \in D$ and $i \geq 1$ , prescribe the same probability kernel $K (\cdot ∣ d)$ on $S \times [0, 1]$ ; applying [F3] to the resulting countable sequence gives an array of independent potential outcomes. Generate behavior actions by their history kernels and reveal outcome $(d, i)$ on the $i$ th visit to pair $d$ . Conditional on the interaction history, the selected unused coordinate still has law $K (\cdot ∣ d)$ , so each finite interaction prefix has the same iterated-kernel law as the MDP under the behavior. Equality of these prefixes proves the coupling claim.

1.2givenF4F5F10

For the predictable-target clause, put $D_{i} = Y_{i} - μ_{i}$ and use $F_{i - 1}$ as the conditioning sigma-algebra. By [F4], $0 \leq μ_{i} \leq B$ , so the finite endpoints $- μ_{i}$ and $B - μ_{i}$ are $F_{i - 1}$ -measurable, contain $D_{i}$ , and have width $B$ . Also $E [D_{i} ∣ F_{i - 1}] = 0$ . Thus [F5] gives $E [e^{λ D_{i}} ∣ F_{i - 1}] \leq e^{λ^{2} B^{2} / 8}$ for every real $λ$ .

1.3F1F3F9F10algebra

For each $s^{'} \in S$ , let $I_{i} (s^{'})$ be one when $S_{i}^{'} = s^{'}$ and zero otherwise, and put $p_{s^{'}} = P (s^{'} ∣ s, a)$ . Independence across the potential stream gives $E [(m^{- 1} \sum_{i} I_{i} (s^{'}) - p_{s^{'}})^{2}] = p_{s^{'}} (1 - p_{s^{'}}) / m \leq p_{s^{'}} / m$ . By [F9], $E ∣ m^{- 1} \sum_{i} I_{i} (s^{'}) - p_{s^{'}} ∣ \leq \sqrt{p_{s^{'}} / m}$ . Summing over $s^{'}$ and using $\sum_{s^{'}} p_{s^{'}} = 1$ and [F9] gives $E ∥ {\hat{P}}_{m} - P ∥_{1} \leq \sqrt{∣ S ∣ / m}$ .

1.4F3F6F8F10construct

Let $f (Z_{1}, \dots, Z_{m}) = ∥ {\hat{P}}_{m} - P ∥_{1}$ and $M_{i} = E [f ∣ F_{i}]$ , where $F_{i} = σ (Z_{1}, \dots, Z_{i})$ for the state coordinates of the potential stream. Replacing one state coordinate changes ${\hat{P}}_{m}$ in $L^{1}$ by at most $2 / m$ , so, by independence of the remaining coordinates, the conditional range of $M_{i}$ given $F_{i - 1}$ has width at most $2 / m$ . The finite state alphabet makes its conditional minimum and maximum measurable functions of the prefix, so $(M_{i})$ is a martingale with finite predictable increment endpoints of that width.

2.1givenF2F3step 1.1construct

Fix a pair and write its independent potential stream as $(Z_{i})_{i \geq 1}$ . Let $N$ be a finite visit count determined by the observed interaction history before the next sample, and let $A$ be an event observable at that history. For each integer $n$ , the event $A \cap {N = n}$ depends only on the first $n$ coordinates of this pair's stream and on other revealed or behavior randomness, all independent of $Z_{n + 1}, \dots, Z_{n + m}$ . The product finite-prefix laws from [F3] therefore give, for every measurable block event $B$ , $P (A, N = n, (Z_{n + 1}, \dots, Z_{n + m}) \in B) = P (A, N = n) K^{\otimes m} (B)$ . Summing over $n$ proves that the next fixed-size block has conditionally the iid law at the history-dependent visit count.

2.2step 1.2F6F7algebra

For $λ > 0$ , set $S_{k} = \sum_{i = 1}^{k} D_{i}$ . The factor $e^{λ S_{k - 1}}$ is bounded and $F_{k - 1}$ -measurable; [F6] and step 1.2 give $E [e^{λ S_{k}}] \leq e^{λ^{2} B^{2} / 8} E [e^{λ S_{k - 1}}]$ . Iterating from $S_{0} = 0$ yields $E [e^{λ S_{m}}] \leq e^{m λ^{2} B^{2} / 8}$ . Apply [F7] to $e^{λ S_{m}}$ and optimize $- λ m x + m λ^{2} B^{2} / 8$ at $λ = 4 x / B^{2}$ to get $P (S_{m} \geq m x) \leq e^{- 2 m x^{2} / B^{2}}$ . Applying the same argument to $- D_{i}$ gives the lower tail, and addition gives the stated two-sided inequality.

2.3step 1.3step 1.4F8algebra

Apply the upper-tail half of [F8] with $c_{i} = 2 / m$ and $t = \sqrt{2 \ln (1 / δ) / m}$ ; since $\sum_{i} c_{i}^{2} = 4 / m$ , the probability that $f - E f > t$ is at most $e^{- m t^{2} / 2} = δ$ . Combining this with step 1.3 gives the stated empirical transition bound.

3.1F1F3step 2.2

For a fixed pair's potential stream, set $F_{i} = σ ((S_{j}^{'}, R_{j}) : j \leq i)$ . Independence of the stream makes $R_{i}$ independent of $F_{i - 1}$ , so $E [R_{i} ∣ F_{i - 1}] = E [R_{i}] = \int ρ K (d s^{'}, d ρ ∣ s, a) = r (s, a)$ almost surely. Since $0 \leq R_{i} \leq 1$ , apply step 2.2 with $B = 1$ , $Y_{i} = R_{i}$ , and this conditional mean to obtain the displayed reward bound.

4.1step 2.1step 2.2step 3.1step 2.3F3F11∎

At any finite history-dependent batch start, step 2.1 gives the next fixed-size block its conditional iid law. Applying steps 2.2, 3.1, and 2.3 conditionally at that start therefore supplies their stated concentration bounds for that batch; [F11] combines a finite set of such events when failure probabilities are allocated. This does not assert a uniform bound for a sample size chosen after observing its own samples.

DefinitionDefinition: Literature-sourcedProof: Not applicableOpen item page →

PAC-MDP sample complexity of exploration

Definition

Assume AC, fix a bounded-reward finite discounted MDP, an initial state, and a learning algorithm whose behavior is a history-dependent policy. At time $t \geq 1$ , let $h_{t}$ be the observed history ending at state $s_{t}$ . The continuation behavior $A_{t}$ is the tail of the algorithm's action kernels after $h_{t}$ , and $V^{A_{t}} (h_{t})$ is the expected discounted return of the continuation process generated from that fixed history by those tail kernels. Set $S = ∣ S ∣$ and $A = \max_{s \in S} ∣ A (s) ∣$ . For $ϵ \geq 0$ , the $ϵ$ -bad-step count is $N_{ϵ} = # {t \geq 1 : V^{A_{t}} (h_{t}) < V^{*} (s_{t}) - ϵ},$ where the count may be infinite. For $ϵ > 0$ and $0 < δ < 1$ , a PAC-MDP bound is a specified finite function $B (S, A, ϵ, δ, γ)$ such that, for every MDP with these finite state/action sizes and every initial state, $P (N_{ϵ} \leq B (S, A, ϵ, δ, γ)) \geq 1 - δ$ . This definition does not require the bad steps to precede a permanent stopping time.

For each fixed $t$ , the finite-horizon continuation values are measurable functions of $h_{t}$ : recursively, they are finite sums and integrals of nonnegative product-measurable functions against the behavior and MDP kernels. The kernel-integration theorem applies at each recursion, and the infinite-horizon value is the increasing limit of these finite-horizon values. Hence the bad-time sets and the extended count $N_{ϵ}$ are measurable, so the displayed probability is defined.

Definition references

Finite discounted MDPs, history-dependent behaviors, and observed histories with Borel reward coordinates.

The discounted return and optimal value are well-defined, with an optimal deterministic stationary policy.

AC is used for the countable trajectory law.

Integration of a nonnegative product-measurable function against a probability kernel is measurable in the history parameter.

Strehl, Li, and Littman, Reinforcement Learning in Finite MDPs: PAC Analysis.

Strehl et al., PAC Model-Free Reinforcement Learning.

DefinitionDefinition: AI-adaptedProof: Not applicableOpen item page →

Admissible upper heuristic for a discounted MDP

Definition

For a bounded-reward finite discounted MDP, an admissible upper heuristic is a function $U : D \to [0, V_{0}]$ such that $Q^{*} (s, a) \leq U (s, a)$ for every admissible pair and a supplied scalar satisfies $0 \leq V_{0} \leq (1 - γ)^{- 1}$ . Define the effective reward-scale cap $V_{\max} = \max {1, V_{0}}$ . Then $U (s, a) \leq V_{\max} \leq (1 - γ)^{- 1}$ . The floor at $1$ is part of this convention because an observed reward can lie anywhere in $[0, 1]$ , even when the heuristic values are all smaller than $1$ .

Definition references

The finite state-action domain and bounded real rewards.

Optimal action values and the geometric discounted-value cap.

Strehl, Li, and Littman, Reinforcement Learning in Finite MDPs: PAC Analysis.

Szepesvári, Algorithms for Reinforcement Learning.

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passOpen item page →

Value stability under empirical model error

Statement

Let $M_{1}$ and $M_{2}$ be bounded-reward finite discounted MDPs on the same finite state set $S$ and the same admissible action sets, with common discount $0 \leq γ < 1$ . Write $r_{i}, P_{i}, V_{i}^{π}, V_{i}^{*}$ for their mean rewards, transition laws, stationary-policy values, and optimal values. Suppose $0 \leq V_{i}^{π} (s), V_{i}^{*} (s) \leq V$ for every state, model index $i$ , and stationary policy $π$ , and that for every admissible pair $∣ r_{1} (s, a) - r_{2} (s, a) ∣ \leq α, ∥ P_{1} (\cdot ∣ s, a) - P_{2} (\cdot ∣ s, a) ∥_{1} \leq β .$ For finite vectors, $∥ v ∥_{\infty} = \max_{s \in S} ∣ v (s) ∣$ and $∥ p ∥_{1} = \sum_{s \in S} ∣ p (s) ∣$ . Then every common stationary policy and the optimal values satisfy $∥ V_{1}^{π} - V_{2}^{π} ∥_{\infty} \leq \frac{α + γ V β}{1 - γ}, ∥ V_{1}^{*} - V_{2}^{*} ∥_{\infty} \leq \frac{α + γ V β}{1 - γ} .$ There is also a trap-model form that does not assume a tight cap for the second model: for $W > 0$ , suppose all stationary-policy and optimal values in $M_{1}$ are at most $2 W$ , all rewards in $M_{2}$ lie in $[0, 1]$ , and $γ β \leq (1 - γ) / 2$ . Then every common stationary policy and the optimal values satisfy $∥ V_{1}^{π} - V_{2}^{π} ∥_{\infty} \leq \frac{2 (α + 2 γ W β)}{1 - γ}, ∥ V_{1}^{*} - V_{2}^{*} ∥_{\infty} \leq \frac{2 (α + 2 γ W β)}{1 - γ} .$

Statement references

Finite discounted MDPs, rewards, and transition laws.

Stationary and optimal Bellman fixed-point equations.

Strehl, Li, and Littman, Reinforcement Learning in Finite MDPs: PAC Analysis.

Szepesvári, Algorithms for Reinforcement Learning.

Facts & Assumptions

Given: The two MDPs, common state/action/discount data, the uniform reward and transition error bounds, and the common value cap $V$ in the Statement.

[F1]

Well-defined discounted values and optimal Bellman fixed points: each stationary value solves its policy Bellman equation, and each optimal value is the unique fixed point of its optimality Bellman operator.

[F2]

Every nonempty finite set of reals has a maximum and a minimum: a maximum over each nonempty finite action set is attained.

[F3]

Laws of finite sums and finite products: finite weighted sums preserve inequalities and satisfy the triangle inequality.

[A1]

Finite discounted MDP with bounded real rewards: rewards in $M_{2}$ lie in $[0, 1]$ , so its stationary and optimal discounted values are at most $(1 - γ)^{- 1}$ .

Proof

1.1givenF1F3algebra

Fix a stationary policy $π$ and put $d = ∥ V_{1}^{π} - V_{2}^{π} ∥_{\infty}$ . Subtract its two Bellman equations. For each state, split the transition term as $P_{1} (V_{1}^{π} - V_{2}^{π}) + (P_{1} - P_{2}) V_{2}^{π}$ . The first part has absolute value at most $d$ because $P_{1}$ is a probability vector; the second is at most $V ∥ P_{1} - P_{2} ∥_{1} \leq V β$ because $0 \leq V_{2}^{π} \leq V$ . Averaging over the common policy's action distribution and using the reward error gives $∣ V_{1}^{π} (s) - V_{2}^{π} (s) ∣ \leq α + γ d + γ V β$ . Taking the maximum over states and rearranging yields the first bound.

1.2givenF1F2F3algebra

Put $d = ∥ V_{1}^{*} - V_{2}^{*} ∥_{\infty}$ . For any state and action, the two optimal Bellman backup entries differ by at most $α + γ d + γ V β$ , by the same transition splitting and the cap on $V_{2}^{*}$ . For finite lists $(x_{a}), (y_{a})$ , $∣ \max_{a} x_{a} - \max_{a} y_{a} ∣ \leq \max_{a} ∣ x_{a} - y_{a} ∣$ : each $x_{a} \leq y_{a} + m$ and $y_{a} \leq x_{a} + m$ for $m = \max_{a} ∣ x_{a} - y_{a} ∣$ . Thus the optimal Bellman equations in [F1] imply $d \leq α + γ d + γ V β$ . Rearranging proves the second bound.

2.1givenF1F3A1step 1.1algebra

Under the additional trap-model hypotheses, fix $π$ and put $d = ∥ V_{1}^{π} - V_{2}^{π} ∥_{\infty}$ . Bellman subtraction as in step 1.1 gives $d \leq α + γ d + γ β ∥ V_{2}^{π} ∥_{\infty}$ . By [A1] and the triangle inequality, $∥ V_{2}^{π} ∥_{\infty} \leq ∥ V_{1}^{π} ∥_{\infty} + d \leq 2 W + d$ . Hence $(1 - γ - γ β) d \leq α + 2 γ W β$ . Since $γ β \leq (1 - γ) / 2$ , the left coefficient is at least $(1 - γ) / 2$ , yielding $d \leq 2 (α + 2 γ W β) / (1 - γ)$ .

3.1givenF1F2F3A1step 1.2step 2.1algebra∎

For optimal values, use the finite-maximum inequality from step 1.2 in the Bellman subtraction. It gives $d = ∥ V_{1}^{*} - V_{2}^{*} ∥_{\infty} \leq α + γ d + γ β ∥ V_{2}^{*} ∥_{\infty}$ . Again [A1] and the triangle inequality give $∥ V_{2}^{*} ∥_{\infty} \leq 2 W + d$ . The same rearrangement as step 2.1 proves the optimal-value bound.

DefinitionDefinition: Literature-sourcedProof: Not applicableOpen item page →

Known-state/action MDP with prescribed absorbing values

Definition

Let $M$ be a bounded-reward finite discounted MDP with discount $γ$ , let $K \subseteq D$ be a set of known state-action pairs, and let $q : D \to [0, V_{\max}]$ with $V_{\max} \leq (1 - γ)^{- 1}$ . The known-state/action MDP $M_{K} (q)$ agrees with $M$ on every pair in $K$ . For each pair $(s, a) \notin K$ , add a distinct absorbing state $⊥_{s, a}$ with one admissible action. The unknown pair transitions deterministically to $⊥_{s, a}$ and gives deterministic reward $(1 - γ) q (s, a)$ ; the sink action self-loops with the same deterministic reward $(1 - γ) q (s, a)$ . These rewards lie in $[0, 1]$ . The sink state's value is $q (s, a)$ , so the unknown pair's Bellman backup is exactly $(1 - γ) q (s, a) + γ q (s, a) = q (s, a)$ , independent of the value function on the original states.

Definition references

The finite discounted MDP and its admissible state-action pairs.

The normalized discounted-value cap.

Strehl, Li, and Littman, Reinforcement Learning in Finite MDPs: PAC Analysis.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicableOpen item page →

R-MAX with an admissible heuristic

Definition

Input: A bounded-reward finite discounted MDP interaction, its discount $0 \leq γ < 1$ , an admissible upper heuristic $U$ with cap $V_{\max}$ , an integer sample threshold $m \geq 1$ , a value-iteration error tolerance $0 < β < (1 - γ)^{- 1}$ , and a fixed total order on each finite action set. Write $\ln$ for the natural logarithm.

Output: At each interaction time $t$ , the selected action $a_{t}$ . The action-value table $Q$ , known set, sample lists, and empirical model are internal state; the procedure does not return $Q$ as an output.

Initialize each pair as unknown, set $Q (s, a) = U (s, a)$ , and give each pair an empty list of observed rewards and next states. For interaction times $t = 1, 2, \dots$ , in the current state choose a maximizing action using the fixed tie order, output and take that action $a_{t}$ , and observe reward $R_{t + 1}$ and next state $S_{t + 1}$ . If the pair is unknown, append this observation until its list has length $m$ . When it reaches $m$ , mark the pair known, set its empirical reward to the sample mean and its empirical transition law to the sample frequencies. Rebuild all action values by setting the working table $Q^{(0)} (s, a) = 0$ , then for $j = 0, \dots, L - 1$ setting $Q^{(j + 1)} = H_{K} Q^{(j)}$ , and finally replacing $Q$ by $Q^{(L)}$ , for the operator $H_{K} Q (s, a) = {\begin{cases} \hat{r} (s, a) + γ \sum_{s^{'}} \hat{P} (s^{'} ∣ s, a) \max_{b \in A (s^{'})} Q (s^{'}, b), & (s, a) \in K, \\ U (s, a), & (s, a) \notin K, \end{cases}$ where $K$ is the current known set and $L = \max ⁣ {1, ⌈ \frac{\ln (1 / [β (1 - γ)])}{1 - γ} ⌉} .$ Pairs and their samples are never removed from $K$ or discarded. After processing the observation and any rebuild, use the observed $S_{t + 1}$ as the current state in the next iteration. The algorithm specifies no computational-time bound.

Definition references

Finite discounted MDP interaction and the joint next-state/reward law.

Admissible upper heuristic and normalized reward-scale cap.

Strehl, Li, and Littman, Reinforcement Learning in Finite MDPs: PAC Analysis.

Szepesvári, Algorithms for Reinforcement Learning.

Sutton and Barto, Reinforcement Learning: An Introduction, 2nd ed..

AlgorithmAlgorithm: Literature-sourcedProof: Not applicableOpen item page →

Delayed Q-learning with an admissible heuristic

Definition

Input: A bounded-reward finite discounted MDP interaction, its discount $0 \leq γ < 1$ , an admissible upper heuristic $U$ with cap $V_{\max}$ , an integer batch size $m \geq 1$ , a bonus $0 < ϵ_{1} < 1$ , and a fixed total order on each action set.

Output: At each interaction time $t$ , the selected action $a_{t}$ . The table $Q$ , batch sums, sample counts, batch-start times, learning flags, and global last-update time are internal state; the procedure does not return them as outputs.

Initialize $Q (s, a) = U (s, a)$ , batch sum $B (s, a) = 0$ , sample count $ℓ (s, a) = 0$ , batch start $b (s, a) = 0$ , learning flag $L (s, a) = t r u e$ , and global last-update time $t^{*} = 0$ . For interaction times $t = 1, 2, \dots$ , in current state $s$ , choose an action maximizing $Q (s, \cdot)$ under the fixed tie order, output and take that action $a_{t}$ , then observe reward $r$ and next state $s^{'}$ . If $b (s, a) \leq t^{*}$ , set $L (s, a) = t r u e$ . If $L (s, a)$ is true, set $b (s, a) = t$ when $ℓ (s, a) = 0$ , increment $ℓ (s, a)$ by one, and add $r + γ \max_{c \in A (s^{'})} Q (s^{'}, c)$ to $B (s, a)$ . When $ℓ (s, a) = m$ , set $\overset{ˉ}{B} = B (s, a) / m$ . If $Q (s, a) - \overset{ˉ}{B} \geq 2 ϵ_{1}$ , replace $Q (s, a)$ by $\overset{ˉ}{B} + ϵ_{1}$ and set $t^{*} = t$ . Otherwise set $L (s, a) = f a l s e$ exactly when $b (s, a) > t^{*}$ . In either outcome reset $B (s, a) = 0$ and $ℓ (s, a) = 0$ after a completed batch; if $L (s, a)$ remains false, make no sample or Q update on this visit. Leave all other entries unchanged. Use $s^{'}$ as the current state in the next iteration.

Definition references

Finite discounted MDP interaction and the joint next-state/reward law.

The admissible initialization and value cap.

The one-step reward plus discounted greedy-successor target.

Strehl, Li, and Littman, Reinforcement Learning in Finite MDPs: PAC Analysis.

Strehl et al., PAC Model-Free Reinforcement Learning.

Szepesvári, Algorithms for Reinforcement Learning.

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passOpen item page →

Escape-event reduction for optimistic greedy learning

Statement

Assume AC. Let a learning algorithm interact with a bounded-reward finite discounted MDP. Suppose constants $B, W, Q_{c}$ satisfy $0 < B$ , $0 < W \leq (1 - γ)^{- 1}$ , $0 < Q_{c} \leq (1 - γ)^{- 1}$ , and $V^{*} (s) \leq B$ . The learner maintains $0 \leq Q_{t} (s, a) \leq Q_{c}$ and, whenever $(s, a) \notin K_{t}$ , $Q_{t} (s, a) \leq W$ . Put $V_{t} (s) = \max_{a \in A (s)} Q_{t} (s, a)$ , and let $π_{t}$ be the deterministic greedy policy under a fixed tie order. Require the learner to select $a_{t} = π_{t} (s_{t})$ at every time. Before acting at time $t$ , let $K_{t}$ be a history-measurable set of known pairs; assume it stays fixed until a Q-value update or a selection of a pair outside $K_{t}$ . Write $M_{t} = M_{K_{t}} (Q_{t})$ for the known-state/action MDP and $C = B + W$ . For parameters $0 < η \leq C$ with $η (1 - γ) < 1$ and $0 < ρ < 1 / 2$ , suppose that with probability at least $1 - ρ$ , simultaneously for every $t, s$ , $V_{t} (s) \geq V^{*} (s) - η, V_{t} (s) - V_{M_{t}}^{π_{t}} (s) \leq η,$ and the total number of Q-update times plus outside- $K_{t}$ selection times is at most a finite real $ζ \geq 0$ . Define $q = η / (2 C)$ , set $H = {\begin{cases} 1, & γ = 0, \\ \max {1, ⌈ \ln (1 / [η (1 - γ)]) / (- \ln γ) ⌉}, & 0 < γ < 1, \end{cases} M = ⌈ \frac{2 (ζ + 1) + 2 \ln (1 / ρ)}{q} ⌉ .$ Then, with probability at least $1 - 2 ρ$ , the PAC-MDP count satisfies $N_{4 η} \leq H M$ . Here $\ln$ is the natural logarithm.

Statement references

Finite discounted MDPs, history-dependent continuation behaviors, and nonnegative rewards.

The bad-step count and PAC-MDP bound convention.

The dedicated absorbing state and reward assigned to each pair outside the known set.

Continuation values are bounded by the optimal value, with a finite discounted geometric tail.

AC for the countable path law.

Strehl, Li, and Littman, Reinforcement Learning in Finite MDPs: PAC Analysis.

Strehl et al., PAC Model-Free Reinforcement Learning.

Facts & Assumptions

Given: The MDP, AC, the algorithm acting greedily under the fixed tie order and predictable known sets, the value caps, and the simultaneous optimism, policy-accuracy, and complexity event in the Statement.

[F1]

Known-state/action MDP with prescribed absorbing values: on a known pair the trap model has the true transition/reward law; outside the known set it has a dedicated absorbing state whose value is $Q_{t} (s, a)$ .

[F2]

Well-defined discounted values and optimal Bellman fixed points: under AC, every history-dependent continuation has a trajectory law; a history-conditioned continuation value in the true MDP is at most $V^{*} (s) \leq B$ , and truncating a nonnegative discounted return after $H$ terms loses at most $γ^{H} / (1 - γ)$ in expectation.

[F3]

PAC-MDP sample complexity of exploration: a time $t$ is counted in $N_{4 η}$ exactly when the conditional continuation value is strictly less than $V^{*} (s_{t}) - 4 η$ .

[A1]

The Axiom of Choice: every family of nonempty sets has a choice function. AC is assumed here to meet the hypotheses of the path-law result [F2] and the conditional-expectation suppliers [F5].

[F4]

Filtration and filtered probability space: the history through each successive trial is an increasing filtration.

[F5]

Basic algebra and order properties of conditional expectation, Tower property of conditional expectation, and Taking out what is known: conditional expectation is linear, iterates through nested histories, and allows bounded history-measurable factors to be removed from the conditional expectation.

[F6]

Markov's inequality for random variables: if $Z \geq 0$ and $c > 0$ , then $P (Z \geq c) \leq E [Z] / c$ .

[F7]

Measurability of integration against a kernel: integration of a nonnegative product-measurable function against a probability kernel gives a measurable function of the history parameter.

Proof

1.1givenF1F2F3A1construct

Fix a history at time $t$ at which the current optimism and policy-accuracy inequalities in the Statement hold, and let $W_{t}$ be the event that before $H$ transitions elapse the algorithm updates some Q-value or selects a pair outside $K_{t}$ . If $W_{t}$ does not occur, the greedy policy and known set remain fixed, every selected pair is in $K_{t}$ , and the true interaction and $M_{t}$ have the same transition/reward kernels along these $H$ steps by [F1]. The expected truncated returns therefore agree on $W_{t}^{c}$ . On $W_{t}$ , stop the coupling at the first update or outside-pair selection. The common prefix cancels. At any history, the true continuation value is at most $B$ by [F2]. In $M_{t}$ , before the first outside pair a policy follows a true-MDP prefix; its expected nonnegative prefix is at most $B$ , since continuing that policy in the true MDP can only add nonnegative rewards. After the first outside pair its dedicated sink contributes exactly $Q_{t} (s, a) \leq W$ by [F1] and the Statement. Thus every policy value in $M_{t}$ , including its continuation after the stopping history, is at most $B + W = C$ . Since both continuation values are nonnegative, their absolute difference is at most $C$ , and the expected loss contributed by $W_{t}$ is at most $C P (W_{t} ∣ h_{t})$ .

2.1givenF2F3step 1.1algebra

The known-model policy's infinite return exceeds its $H$ -step truncated return by at most $γ^{H} / (1 - γ) \leq η$ , by the definition of $H$ ; for $γ = 0$ the tail is zero. The true return is at least its truncated return because rewards are nonnegative. Combining step 1.1 with the assumed policy accuracy and optimism gives $V^{A_{t}} (h_{t}) \geq V_{t} (s_{t}) - 2 η - C P (W_{t} ∣ h_{t}) \geq V^{*} (s_{t}) - 3 η - C P (W_{t} ∣ h_{t})$ . Therefore, if $t$ is counted by $N_{4 η}$ , then $P (W_{t} ∣ h_{t}) > η / C \geq q$ .

3.1givenstep 2.1F7construct

Construct trials by starting at the first bad time not already covered by a previous trial window, running that window for $H$ transitions, and then waiting for the next bad time. The starts are stopping times: each bad-time test and current inequality is history measurable. For the continuation-value test, finite-horizon continuation values are measurable by recursive kernel integration using [F7], and the discounted continuation value is their increasing limit. The windows are disjoint. At a trial start satisfying the two current optimism and accuracy inequalities, its conditional chance of containing an update or escape is at least $q$ by step 2.1; this statement conditions only on its starting history, not on the future simultaneous good event. Every such success occurs at a distinct update/escape time, so on the simultaneous complexity event there are at most $ζ$ successes. Each trial window contains at most $H$ bad times, and there are no bad times between a completed window and the next trial start.

4.1givenF4F5F6step 3.1algebra∎

Write $τ_{i}$ for the successive trial starts, setting $τ_{i} = \infty$ when no such start exists. For $i \leq M$ , set $X_{i} = 1$ if $τ_{i} = \infty$ or either current optimism/accuracy inequality fails at its start; otherwise let $X_{i}$ indicate an update or escape during its window. Use the stopped-history sigma-algebra at $τ_{i}$ , with the full path sigma-algebra on ${τ_{i} = \infty}$ . It contains every earlier window outcome. On the first two cases $X_{i} = 1$ ; in the remaining case step 2.1 gives conditional success probability at least $q$ . Thus $E [X_{i} ∣ F_{τ_{i}}] \geq q$ without conditioning on the simultaneous future good event. Since $e^{- λ X_{i}} = 1 - (1 - e^{- λ}) X_{i}$ , [F5] and induction give $E [e^{- λ \sum_{i = 1}^{M} X_{i}}] \leq (1 - q (1 - e^{- λ}))^{M} \leq e^{- M q / 2}$ for $λ = \ln 2$ . Applying [F6] to this nonnegative exponential yields $P (\sum_{i = 1}^{M} X_{i} \leq ζ) \leq e^{(ζ + 1) \ln 2 - M q / 2} \leq ρ$ by the definition of $M$ . If more than $M$ bad-time trials occurred while the simultaneous optimism, accuracy and complexity event held, the first $M$ starts would be finite and every $X_{i}$ would be its actual update/escape indicator, so their sum would be at most $ζ$ . This has probability at most $ρ$ . Adding the probability at most $ρ$ that the simultaneous assumptions fail proves that, with probability at least $1 - 2 ρ$ , there are at most $M$ trials and hence at most $H M$ bad times.

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passOpen item page →

Adaptive empirical-model accuracy for R-MAX

Statement

Let $M$ be a bounded-reward finite discounted MDP, let $0 < η < V_{\max} / 4$ and $0 < δ < 1$ , and let $U, V_{\max}$ be an admissible heuristic with $V_{\max} = \max {1, V_{0}}$ . Put $b = \frac{η (1 - γ)}{64 V_{\max}}, L_{0} = \ln \frac{8 S A}{δ}, m = ⌈ \frac{8 (S + L_{0})}{b^{2}} ⌉, β = \frac{η (1 - γ)}{16},$ where $S = ∣ S ∣$ and $A = \max_{s} ∣ A (s) ∣$ . Run R-MAX with this sample threshold and approximation tolerance. For $K_{t}$ the current known set, let ${\hat{M}}_{K_{t}}$ use its empirical laws on $K_{t}$ and the heuristic absorbing states elsewhere, and let $M_{K_{t}} = M_{K_{t}} (U)$ use the true laws on $K_{t}$ . Define $E_{η} = {(s, a) : U (s, a) \geq V^{*} (s) - η}$ . With probability at least $1 - δ$ , simultaneously at all times: every stationary-policy value in ${\hat{M}}_{K_{t}}$ differs from its value in $M_{K_{t}}$ by at most $η / 8$ ; the current action values satisfy $∥ Q_{t} - Q_{{\hat{M}}_{K_{t}}}^{*} ∥_{\infty} \leq β$ and $0 \leq Q_{t} (s, a) \leq (1 - γ)^{- 1}$ ; the greedy value obeys $V_{t} (s) \geq V^{*} (s) - η$ ; and $V_{t} (s) - V_{M_{K_{t}}}^{π_{t}} (s) \leq η$ for every state. On this event, the total number of value-table rebuilds plus selections of pairs outside $K_{t}$ is at most $(m + 1) ∣ E_{η} ∣$ .

Statement references

R-MAX stores its initial empirical batch and performs the specified finite Bellman sweeps.

The admissible value cap and componentwise optimism condition.

The true and empirical known-state/action models.

Adaptive reward and transition estimates for each potential stream.

The policy-value perturbation bound.

Bellman contraction, value iteration, and optimal values.

Strehl, Li, and Littman, Reinforcement Learning in Finite MDPs: PAC Analysis.

Facts & Assumptions

Given: The MDP, admissible heuristic, parameters, R-MAX algorithm, and notation in the Statement.

[F1]

Concentration for adaptively sampled MDP observations: for each pair's first $m$ potential outcomes, the reward mean and transition $ℓ^{1}$ error obey the displayed concentration bounds, simultaneously under adaptive visits.

[F2]

Value stability under empirical model error: if the true trap model values are bounded by $2 V_{\max}$ , the empirical model has rewards in $[0, 1]$ , and $γ b \leq (1 - γ) / 2$ , then reward and transition errors at most $b$ give value error at most $2 (b + 2 γ V_{\max} b) / (1 - γ)$ for every policy and for the optimal values.

[F3]

Well-defined discounted values and optimal Bellman fixed points: the Bellman optimality operator is a $γ$ contraction; its value-iteration iterates converge to its fixed point, and an admissible action value is bounded by $(1 - γ)^{- 1}$ .

[F4]

Admissible upper heuristic for a discounted MDP and Known-state/action MDP with prescribed absorbing values: $U \geq Q^{*}$ , and the dedicated sink for an unknown pair in $M_{K} (U)$ has value $U (s, a)$ .

[F5]

R-MAX with an admissible heuristic: each newly known pair triggers one rebuild; a pair remains outside the known set for at most its first $m$ selections.

[F6]

The finite union bound: the probability of a finite union of events is at most the sum of their probabilities.

Proof

1.1givenF1F6algebra

Apply [F1] to each pair with reward and transition tolerance $b$ . For $δ_{0} = δ / (4 S A)$ , the transition threshold is $\sqrt{S / m} + \sqrt{2 \ln (1 / δ_{0}) / m} \leq b$ : its squared numerator is at most $2 S + 4 \ln (1 / δ_{0}) \leq 4 (S + L_{0})$ , while $m \geq 8 (S + L_{0}) / b^{2}$ . The reward failure is at most $2 e^{- 2 m b^{2}} \leq δ_{0}$ because $2 m b^{2} \geq 16 (S + L_{0}) \geq \ln (2 / δ_{0})$ . By [F6], the finite union over reward and transition events for at most $S A$ pairs has failure probability at most $2 S A δ_{0} = δ / 2$ .

1.2givenF3F5algebra

The Bellman operator of ${\hat{M}}_{K}$ is exactly the operator in [F5], with unknown backup $U$ . Its fixed point and zero-initialized sweeps lie in $[0, (1 - γ)^{- 1}]$ . The contraction estimate in [F3] gives error at most $γ^{L} / (1 - γ)$ . For $0 < γ < 1$ , $\ln γ \leq - (1 - γ)$ , so the stated $L$ makes this error at most $β$ ; when $γ = 0$ , one sweep is exact. The initial table $U$ is the exact fixed point for the empty known set. Thus the action-value approximation bound holds after every rebuild.

2.1givenF2F3F4step 1.1algebra

For a fixed known set $K$ , the true trap model has every stationary-policy and optimal value at most $2 V_{\max}$ . Indeed, until the first outside- $K$ pair its path is a true-MDP path, whose expected nonnegative prefix is at most $V^{*} (s) \leq V_{\max}$ ; after that pair its absorbing continuation is at most $U (s, a) \leq V_{\max}$ . The empirical trap model has all rewards in $[0, 1]$ . Also $γ b \leq (1 - γ) / 2$ , since $γ b / (1 - γ) = γ η / (64 V_{\max}) < 1 / 256$ . Apply the trap-model form of [F2] with $W = V_{\max}$ and $α = β = b$ . The value error for each policy and the optimum is at most $2 b (1 + 2 γ V_{\max}) / (1 - γ) = η (1 + 2 γ V_{\max}) / (32 V_{\max}) \leq 3 η / 32 < η / 8$ .

3.1givenF3F4step 2.1step 1.2algebra

Let $V_{M_{K}}^{*}$ and $V_{{\hat{M}}_{K}}^{*}$ denote the trap-model optima. For every state, the true Bellman backup at $V^{*}$ on a known pair is $Q^{*} (s, a)$ , and on an unknown pair the trap backup is $U (s, a) \geq Q^{*} (s, a)$ . Hence $T_{M_{K}}^{*} V^{*} \geq V^{*}$ . The operator preserves coordinatewise order because its transition weights are nonnegative; its iterates from $V^{*}$ therefore increase. Contraction makes these iterates converge to the unique fixed point, so $V_{M_{K}}^{*} \geq V^{*}$ . Step 2.1 gives $V_{{\hat{M}}_{K}}^{*} \geq V_{M_{K}}^{*} - η / 8$ . Since $∥ Q_{t} - Q_{{\hat{M}}_{K}}^{*} ∥_{\infty} \leq β$ , $V_{t} \geq V_{{\hat{M}}_{K}}^{*} - β \geq V^{*} - (η / 8 + β) \geq V^{*} - η$ .

3.2givenF2F3step 2.1step 1.2algebra

For each state $s$ , the action chosen by $π_{t}$ satisfies $Q_{{\hat{M}}_{K}}^{*} (s, π_{t} (s)) \geq V_{{\hat{M}}_{K}}^{*} (s) - 2 β$ : its optimal action value is at least its estimated value minus $β$ , while the estimated maximum is at least the optimal maximum minus $β$ . Thus $T_{{\hat{M}}_{K}}^{π_{t}} V_{{\hat{M}}_{K}}^{*} \geq V_{{\hat{M}}_{K}}^{*} - 2 β$ . Subtracting the policy Bellman equation and taking the maximum positive difference yields $V_{{\hat{M}}_{K}}^{*} - V_{{\hat{M}}_{K}}^{π_{t}} \leq 2 β / (1 - γ)$ . Comparing the same policy in $M_{K}$ by step 2.1 and using $V_{t} \leq V_{{\hat{M}}_{K}}^{*} + β$ gives $V_{t} - V_{M_{K}}^{π_{t}} \leq β + 2 β / (1 - γ) + η / 8 \leq 5 η / 16 < η$ , because $β = η (1 - γ) / 16$ .

4.1givenF4F5step 3.1algebra∎

On the event just proved, an outside- $K_{t}$ pair with $U (s, a) < V^{*} (s) - η$ cannot be selected: its current value is still $Q_{t} (s, a) = U (s, a)$ , whereas $V_{t} (s) \geq V^{*} (s) - η$ . Thus every escape pair lies in $E_{η}$ . By [F5], each such pair is selected outside the known set at most $m$ times and causes one rebuild. Summing over $E_{η}$ proves the complexity bound.

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passOpen item page →

Delayed Q-learning optimism and update-count bounds

Statement

Assume AC. Fix a bounded-reward finite discounted MDP, write $S = ∣ S ∣$ and $A = \max_{s} ∣ A (s) ∣$ , and fix an admissible heuristic with cap $V_{\max}$ , and $0 < ϵ_{1} < 1$ . Put $D (s, a) = [U (s, a) - V^{*} (s)]_{+}$ , $κ = ⌈ S A V_{\max} / ϵ_{1} ⌉$ , $N = S A (1 + κ)$ , and $C_{1} = 1 + γ V_{\max}$ . Run Delayed Q-learning with a positive integer $m$ satisfying $m \geq ⌈ \frac{C_{1}^{2}}{2 ϵ_{1}^{2}} \ln \frac{8 N}{δ} ⌉ (0 < δ < 1) .$ For $V_{t} (s) = \max_{a} Q_{t} (s, a)$ , define $K_{t} = {(s, a) : Q_{t} (s, a) - (r (s, a) + γ \sum_{s^{'}} P (s^{'} ∣ s, a) V_{t} (s^{'})) \leq 3 ϵ_{1}} .$ With probability at least $1 - δ$ , all estimates remain optimistic, $Q_{t} (s, a) \geq Q^{*} (s, a)$ for every $t, s, a$ ; every attempted update whose first sample is taken with its pair outside $K_{t}$ succeeds; the number of successful updates is at most $G = \sum_{s, a} (1 + \frac{D (s, a)}{ϵ_{1}});$ and the number of visits selecting a pair outside $K_{t}$ is at most $2 m G$ . The additive $1$ in each pair's update allowance is necessary, including when $U (s, a) = V^{*} (s)$ .

Statement references

The delayed batch target, success threshold, and global learning flags.

AC, assumed for the potential-stream and conditional-expectation concentration supplier.

The admissible initial upper values and discounted-value cap.

The known-state/action model used to evaluate escape pairs.

Conditional tails for bounded reward/next-state targets under adaptive visits.

The optimal action value and finite-state greedy maximizer.

Strehl, Li, and Littman, Reinforcement Learning in Finite MDPs: PAC Analysis.

Strehl et al., PAC Model-Free Reinforcement Learning.

Facts & Assumptions

Given: AC, the MDP, admissible heuristic, Delayed Q-learning algorithm, and parameters in the Statement.

[F1]

Concentration for adaptively sampled MDP observations: for a bounded predictable target $Y_{i} \in [0, C_{1}]$ , its sample mean differs from its predictable mean by at least $x$ with probability at most $2 e^{- 2 m x^{2} / C_{1}^{2}}$ ; pair visits can be coupled to independent potential outcomes.

[F2]

Delayed Q-learning with an admissible heuristic: a successful update replaces $Q (s, a)$ by a nonnegative batch mean plus $ϵ_{1}$ , decreases that entry by at least $ϵ_{1}$ , and Q-values never otherwise change. A failed batch disables its flag exactly when $b > t^{*}$ ; before sampling, a flag is re-enabled when $b \leq t^{*}$ .

[F3]

Admissible upper heuristic for a discounted MDP and Well-defined discounted values and optimal Bellman fixed points: initially $Q = U \geq Q^{*}$ , $0 \leq Q^{*}, V^{*} \leq V_{\max}$ , and an optimal action attaining $V^{*} (s)$ exists at each state.

[F4]

By the definition of $K_{t}$ in the Statement, the Bellman residual outside $K_{t}$ is strictly greater than $3 ϵ_{1}$ . The known model agrees with the true MDP on $K_{t}$ by Known-state/action MDP with prescribed absorbing values.

[F5]

The finite union bound: a finite union of events has probability at most the sum of their probabilities.

Proof

1.1givenF2algebra

Each successful update decreases one entry by at least $ϵ_{1}$ , while every updated entry stays nonnegative and starts at most $V_{\max}$ , by [F2]. Therefore the total number of updates is at most $S A V_{\max} / ϵ_{1} \leq κ$ . For two consecutive batch starts $b_{j} < b_{j + 1}$ of one pair, some successful global update occurs in $[b_{j}, b_{j + 1})$ : either the earlier batch succeeds, or it fails with $b_{j} \leq t^{*}$ , or it disables learning and a later global update re-enables it. These intervals are disjoint for that pair. Charging each start after its first to such an update gives at most $1 + κ$ starts per pair and at most $N$ overall, including unfinished batches.

2.1givenF1F3F5step 1.1algebra

Condition on a batch-start history at time $k_{1}$ for pair $(s, a)$ and freeze $V_{k_{1}}$ . The next $m$ potential joint outcomes give targets $X_{i} = R_{i} + γ V_{k_{1}} (S_{i}^{'}) \in [0, C_{1}]$ with common mean $r (s, a) + γ P V_{k_{1}}$ . By [F1], except with probability $2 e^{- 2 m ϵ_{1}^{2} / C_{1}^{2}}$ , their average is within $ϵ_{1}$ of that mean. Also, the fixed targets $X_{i}^{*} = R_{i} + γ V^{*} (S_{i}^{'})$ lie in $[0, C_{1}]$ and have mean $Q^{*} (s, a)$ , so their average is within $ϵ_{1}$ of $Q^{*} (s, a)$ except with the same probability. By [F5], a finite union over the at most $N$ batch starts and these two error events has failure at most $4 N e^{- 2 m ϵ_{1}^{2} / C_{1}^{2}} \leq δ / 2$ .

3.1givenF1F2F4step 2.1algebra

On the event from step 2.1, if a batch begins outside $K_{k_{1}}$ , then $Q_{k_{1}} (s, a) - [r + γ P V_{k_{1}}] > 3 ϵ_{1}$ . During that batch all action values can only decrease, so $V_{k_{i}} \leq V_{k_{1}}$ at every sample time $k_{i}$ . Its actual target average is therefore at most the frozen-target average, which is at most $r + γ P V_{k_{1}} + ϵ_{1}$ . The old value minus this average is strictly greater than $2 ϵ_{1}$ , so the attempted update succeeds.

3.2givenF1F2F3step 2.1induction

Initially $Q \geq Q^{*}$ by [F3]. Induct over successful updates. Before an update, all current values satisfy $V_{k_{i}} \geq V^{*}$ by the induction hypothesis, so each actual target $R_{i} + γ V_{k_{i}} (S_{i}^{'})$ is at least $R_{i} + γ V^{*} (S_{i}^{'})$ . Step 2.1 bounds the latter sample mean below by $Q^{*} (s, a) - ϵ_{1}$ . Adding the update bonus $ϵ_{1}$ leaves the new entry at least $Q^{*} (s, a)$ ; unchanged entries remain optimistic. This proves the all-time optimism claim. The event used above has probability at least $1 - δ / 2 \geq 1 - δ$ .

4.1givenF2F3step 3.2algebra

Fix a pair $(s, a)$ . If $U (s, a) < V^{*} (s)$ , choose an optimal action $a^{*}$ at $s$ . On the optimism event, $Q_{t} (s, a^{*}) \geq Q^{*} (s, a^{*}) = V^{*} (s)$ for every $t$ , while the pair's value never increases and therefore stays at most $U (s, a) < V^{*} (s)$ . It is never selected, so it cannot be updated. If $U (s, a) \geq V^{*} (s)$ and the pair is selected, its current value is the greedy maximum and hence at least $V^{*} (s)$ by optimism of $a^{*}$ . If the pair has $n \geq 1$ successful updates, the value immediately before its $n$ th update is at most $U (s, a) - (n - 1) ϵ_{1}$ and at least $V^{*} (s)$ . Indeed, each of the first $n - 1$ updates decreases it by at least $ϵ_{1}$ , and if any post-update value were below $V^{*} (s)$ , the pair could never be selected again. Thus $n \leq 1 + [U (s, a) - V^{*} (s)]_{+} / ϵ_{1}$ . The same bound holds when $n = 0$ and in the first case. Summing over pairs proves the stated bound $G$ .

5.1givenF2F4step 3.1step 4.1algebra∎

It remains to count visits outside $K_{t}$ . First, a failed attempted update that disables the learning flag must leave the pair inside $K$ : since $b > t^{*}$ , no Q table entry changed after that batch began, so the residual was constant through the batch; if it had been outside at batch start, step 3.1 would have forced success. Consequently a visit outside $K_{t}$ cannot occur with the flag still disabled: before sampling, [F2] tests $b \leq t^{*}$ , and an outside residual after the failed batch requires a later global update, which re-enables the flag. Now fix an outside visit for a pair while its flag is true. The next attempted batch occurs within at most $m$ visits to that pair. If the batch began outside $K$ , step 3.1 makes it successful. If it began inside $K$ , the residual became outside by the escape visit after a global update; with the pair's own Q value unchanged, other Q values only decrease, so its Bellman backup can only decrease and its residual remains outside through the attempted batch. Because a global update occurred after that batch began, a failed attempt does not disable the flag. The next attempted batch occurs within at most another $m$ visits and starts outside $K$ , so step 3.1 makes it successful. Thus every interval between successive successful updates of this pair, including the initial interval, contains at most $2 m$ outside visits. To include a possible final unfinished interval, count only intervals containing an outside visit. If the pair has $n$ successful updates and such an interval remains after the last update, its Q-value at an outside selection is at least $V^{*} (s)$ by step 4.1, while its $n$ previous updates have decreased it by at least $n ϵ_{1}$ . Hence $n ϵ_{1} \leq D (s, a)$ and these $n + 1$ intervals number at most $1 + D (s, a) / ϵ_{1}$ . If there is no such final interval, the at most $n$ completed intervals have the same bound by step 4.1. An interval with fewer than the $2 m$ visits needed for its next success is included in this count; an interval with $2 m$ outside visits would force that success by the preceding argument. Summing over pairs therefore gives at most $2 m G$ .

TheoremStatement: AI-adaptedProof: AI-generatedOpen item page →

The zero-tolerance boundary of PAC-MDP exploration

Statement

Assume AC, and use the history-conditioned bad-step count $N_{ϵ}$ for bounded-reward finite discounted MDPs. The endpoint $ϵ = 0$ has the following properties.

Fix any single learning rule whose action kernels depend only on its observed history and common supplied inputs, not on the unknown MDP reward means. For every finite real $B \geq 0$ and $0 < δ < 1 / 2$ , some one-state, two-action MDP with $γ = 0$ , Bernoulli rewards and the common admissible heuristic $U (a) = U (b) = V_{\max} = 1$ satisfies $P (N_{0} > B) > δ$ . Thus no finite bound depending only on state/action sizes, confidence and discount can hold uniformly at zero tolerance, even allowing randomized history-dependent learners.
For R-MAX, fix any integer $m \geq 1$ , $0 < β < 1$ , and a tie order selecting $a$ first. For each $0 < p < 1$ , take one state, $γ = 0$ , $U (a) = U (b) = V_{\max} = 1$ , reward $a \sim Bernoulli (p)$ and deterministic reward $b = p / 2$ . Then $P (N_{0} = \infty) \geq (1 - p)^{m}$ . For every $0 < δ < 1$ , some $p$ makes this probability exceed $δ$ ; no fixed finite legal sample threshold gives a uniform finite zero-tolerance bound.
For Delayed Q-learning, fix any integer $m \geq 1$ , $0 < ϵ_{1} < 1$ , and a tie order selecting $b$ first. In the one-state model with $γ = 0$ , $U (a) = U (b) = V_{\max} = 1$ and deterministic rewards $a = 1$ , $b = 1 - ϵ_{1}$ , the algorithm chooses $b$ forever and $N_{0} = \infty$ with probability one.
If $V^{*} (s) = 0$ at every state of any bounded-reward finite discounted MDP, then every behavior has $N_{0} = 0$ . The impossibility is a uniform assertion over unknown models, not a claim that zero-tolerance behavior must always fail.

All models in clauses1–3 have nonempty finite state/action sets, rewards in $[0, 1]$ , and an admissible normalized cap. No parameter formula that divides by $ϵ$ is evaluated at zero.

Statement references

History-conditioned bad-step counts, including zero tolerance.

Finite MDPs and bounded joint transition/reward laws.

Admissibility and the normalized reward-scale cap.

Nonnegative continuation values and optimal values.

Finite first-batch empirical models and fixed tie order.

The positive bonus, delayed batch update and learning flags.

Facts & Assumptions

Given: AC, the learning-rule information restriction, the finite bound and confidence in clause1, and the legal algorithm parameters and models in clauses2–4.

[F1]

PAC-MDP sample complexity of exploration and Well-defined discounted values and optimal Bellman fixed points: when $γ = 0$ , continuation value is the mean immediate reward under the current action distribution; $N_{0}$ counts exactly the times this is strictly below the largest action mean. Every continuation value is nonnegative and at most $V^{*}$ .

[F2]

Finite discounted MDP with bounded real rewards and Admissible upper heuristic for a discounted MDP: one-state self-transitions with any reward law on $[0, 1]$ are allowed; at $γ = 0$ , $U = V_{\max} = 1$ is admissible for these models.

[F3]

Finite probability spaces, outcome weights, events, and event probabilities: probabilities on a finite outcome space are sums of nonnegative weights with total one.

[F4]

Laws of finite sums and finite products: finite sums are additive, preserve inequalities, and allow a constant factor to be taken outside a sum. Thus, for a node of weight $w (h)$ and normalized child probabilities $p (c ∣ h)$ , $\sum_{c} w (h) p (c ∣ h) = w (h) \sum_{c} p (c ∣ h) = w (h)$ . Induction over tree levels preserves total weight one.

[F5]

Every complete ordered field is Archimedean: a natural number exceeds every prescribed finite real bound.

[F6]

R-MAX with an admissible heuristic: before the first $m$ observations an action retains its heuristic; afterwards its model uses only those observations. At $γ = 0$ , every rebuild sets known action values to their empirical reward means after its first sweep.

[F7]

Delayed Q-learning with an admissible heuristic: the initial values are $U$ ; a completed batch changes its entry only if the old value minus its mean target is at least $2 ϵ_{1}$ . A failed batch with start time greater than the last global update disables further learning of that pair until a new global update.

Proof

1.1givenF2F5chooseconstructalgebra

For clause1, choose an integer $T > 2 B$ by [F5] and choose $0 < d < \min {1 / 2, (1 - 2 δ) / T}$ . Define two one-state models $M_{+}, M_{-}$ whose action means are respectively $(1 / 2 + d, 1 / 2)$ and $(1 / 2, 1 / 2 + d)$ , with Bernoulli rewards, discount zero, and common heuristic $1$ . Their unique optimal actions are respectively $a, b$ , and [F2] verifies their model and heuristic conditions.

1.2givenF2construct

For clause2 use the stated R-MAX model, and let $E$ be the event that its first $m$ rewards from $a$ are all zero. Its action means are $p, p / 2$ , so $a$ is uniquely optimal and [F2] verifies admissibility.

1.3givenF2algebra

For clause3 the action means are $1, 1 - ϵ_{1}$ , so $a$ is uniquely optimal, the gap is $ϵ_{1} > 0$ , and [F2] verifies all model and heuristic conditions.

2.1step 1.1F3F4constructinductionalgebra

Couple the two length- $T$ histories of step 1.1 recursively. At equal histories draw the same action with the learning rule’s common action probabilities. For that action let $r_{+}, r_{-}$ be its two means, and assign reward-pair probabilities $\min (r_{+}, r_{-})$ to $(1, 1)$ , $1 - \max (r_{+}, r_{-})$ to $(0, 0)$ , $[r_{+} - r_{-}]_{+}$ to $(1, 0)$ , and $[r_{-} - r_{+}]_{+}$ to $(0, 1)$ . These weights are nonnegative, sum to one, have the desired Bernoulli marginals, and disagree with probability $d$ . After histories differ, use the product of the two prescribed action/reward laws. Give each child its parent weight times its conditional probability. At each node [F4] shows that the child weights sum to its parent weight, so induction from root weight one normalizes the finite coupling. Summing over the other component at each extension gives the prescribed action and Bernoulli reward marginals; induction over rounds therefore verifies each marginal is the learning rule’s actual length- $T$ law by [F3]–[F4].

2.2step 1.2F1F6algebrainduction

Until $a$ becomes known, R-MAX always selects $a$ , since both unknown values are $1$ and its tie order favors $a$ . On $E$ , the first rebuild sets its value to zero while $b$ remains unknown at $1$ . It therefore selects $b$ for $m$ observations, then the two frozen empirical means are $0, p / 2$ . All later rebuilds and actions retain those means, so $b$ is selected forever. By [F1], all those later times are zero-bad. The first $m$ draws from $a$ have their Bernoulli law conditionally at each visit, hence $P (E) = (1 - p)^{m}$ and $E \subseteq {N_{0} = \infty}$ .

2.3step 1.3F1F7algebrainduction

Delayed Q-learning initially ties at $1$ and selects $b$ . Every target in its first batch is $1 - ϵ_{1}$ , since the discount is zero. The old value minus the mean is $ϵ_{1} < 2 ϵ_{1}$ , so the batch fails and no value changes. Its start time is positive while $t^{*} = 0$ , so the flag becomes false. No other action is ever selected, no global update occurs, and the flag remains false. Induction gives $Q (a) = Q (b) = 1$ and action $b$ forever. Its value is $1 - ϵ_{1} < 1 = V^{*}$ , so [F1] gives $N_{0} = \infty$ .

3.1step 1.1step 2.1F3F4algebra

In the coupling of step 2.1, the probability that the first history disagreement occurs at a specified round is at most $d$ , since its preceding equal histories have total probability at most one. Thus the chance of any disagreement by round $T$ is at most $T d$ : sum the nonnegative weights of those disjoint first-disagreement events using [F3]–[F4]. Let $C$ be their complement, so $P (C) \geq 1 - T d$ .

3.2step 1.2step 2.2F3F4algebrachoose

For the final assertion of clause2, fix $0 < δ < 1$ and choose $p = (1 - δ) / (2 m) \in (0, 1)$ . Among the first $m$ rewards from $a$ , the event of at least one reward equal to one has probability at most $m p$ , by summing their indicator weights. Consequently $(1 - p)^{m} \geq 1 - m p = (1 + δ) / 2 > δ$ . Step 2.2 proves the claimed failure probability.

4.1step 1.1step 2.1step 3.1F1F3F4algebracontradiction

Suppose both models from step 1.1 had $P (N_{0} \leq B) \geq 1 - δ$ . The same is then true for the zero-bad count restricted to the first $T$ rounds, in each marginal of the finite coupling. The probability that both restricted counts are at most $B$ and $C$ occurs is at least $1 - 2 δ - T d > 0$ , by summing weights of the three complementary events as in [F3]–[F4]. On $C$ , the two histories and hence their current action distributions coincide at every round. If $z$ is the probability of $a$ , the two mean-reward deficits are respectively $d (1 - z)$ and $d z$ . Since $0 \leq z \leq 1$ and $d > 0$ , at least one deficit is strictly positive. Thus the two restricted zero-bad counts sum to at least $T > 2 B$ , contradicting that both are at most $B$ . At least one model must satisfy $P (N_{0} > B) > δ$ .

5.1step 4.1step 2.2step 3.2step 2.3F1algebra∎

Step 4.1 proves clause1; steps 2.2 and3.2 prove clause2; step 2.3 proves clause3. For clause4, [F1] gives $0 \leq V^{A_{t}} (h_{t}) \leq V^{*} (s_{t}) = 0$ , so no time is zero-bad. These statements establish all endpoint branches without assigning zero to a positive-tolerance denominator.

TheoremStatement: AI-adaptedProof: AI-adaptedprecheck passOpen item page →

PAC-MDP sample complexity of R-MAX

Statement

Let $M$ be a bounded-reward finite discounted MDP, write $S = ∣ S ∣$ and $A = \max_{s} ∣ A (s) ∣$ , and fix $0 \leq ϵ < (1 - γ)^{- 1}$ , $0 < δ < 1$ , and an admissible heuristic with normalized cap $V_{\max}$ . At $ϵ = 0$ , if $V^{*} (s) = 0$ at every state then $N_{0} = 0$ ; no finite zero-tolerance extension holds uniformly over this class: already at $γ = 0$ , every fixed finite legal sample threshold $m$ and value-iteration tolerance $β$ admits an admissible one-state example for R-MAX with $N_{0} = \infty$ with positive probability. This does not assert failure for every fixed heuristic or model. The parameter formulas below are evaluated only when $ϵ > 0$ . Assume now $ϵ > 0$ . If $ϵ \geq V_{\max}$ , then $N_{ϵ} = 0$ . Otherwise put $η = ϵ / 4, b = \frac{η (1 - γ)}{64 V_{\max}}, m = ⌈ \frac{8 (S + \ln (16 S A / δ))}{b^{2}} ⌉, β = \frac{η (1 - γ)}{16},$ and run R-MAX with sample threshold $m$ and value-iteration tolerance $β$ . Let $E_{η} = {(s, a) : U (s, a) \geq V^{*} (s) - η}$ and $ζ = (m + 1) ∣ E_{η} ∣$ . Define $q = η / (4 V_{\max})$ , and define $H$ and $M$ by $H = {\begin{cases} 1, & γ = 0, \\ \max {1, ⌈ \ln (1 / [η (1 - γ)]) / (- \ln γ) ⌉}, & 0 < γ < 1, \end{cases} M = ⌈ \frac{2 (ζ + 1) + 2 \ln (2 / δ)}{q} ⌉ .$ Then $P (N_{ϵ} \leq H M) \geq 1 - δ$ . For the uninformative heuristic $U (s, a) = V_{\max} = (1 - γ)^{- 1}$ , the bound is $\tilde{O} (S^{2} A / [ϵ^{3} (1 - γ)^{6}])$ , where $\tilde{O}$ suppresses logarithmic factors.

For every $ϵ > 0$ , a bound uniform over all MDPs and admissible heuristics with these $S, A, γ$ is obtained by setting $\overset{ˉ}{V} = \frac{1}{1 - γ}, \overset{ˉ}{b} = \frac{ϵ (1 - γ)^{2}}{256}, \overset{ˉ}{m} = ⌈ \frac{8 (S + \ln (16 S A / δ))}{{\overset{ˉ}{b}}^{2}} ⌉, \overset{ˉ}{q} = \frac{ϵ (1 - γ)}{16}, \overset{ˉ}{ζ} = (\overset{ˉ}{m} + 1) S A,$ and $\overset{ˉ}{H} = {\begin{cases} 1, & γ = 0, \\ \max {1, ⌈ \ln (1 / [(ϵ / 4) (1 - γ)]) / (- \ln γ) ⌉}, & 0 < γ < 1, \end{cases} \overset{ˉ}{M} = ⌈ \frac{2 (\overset{ˉ}{ζ} + 1) + 2 \ln (2 / δ)}{\overset{ˉ}{q}} ⌉ .$ Then $P (N_{ϵ} \leq \overset{ˉ}{H} \overset{ˉ}{M}) \geq 1 - δ$ . This bound depends only on $S, A, ϵ, δ, γ$ .

Statement references

The full zero-tolerance boundary, including admissible algorithm failures and the zero-value success case.

The bad-timestep count and the uniform PAC-MDP meaning of a bound.

Admissibility, the cap, and the reward-scale normalization.

R-MAX's known-set updates and finite value-iteration approximation.

Simultaneous optimism, model accuracy, policy accuracy, and update/escape count.

The high-probability conversion from update/escape counts to bad steps.

Strehl, Li, and Littman, Reinforcement Learning in Finite MDPs: PAC Analysis.

Szepesvári, Algorithms for Reinforcement Learning.

Facts & Assumptions

Given: The MDP, heuristic, parameters, R-MAX algorithm, and bad-step count in the Statement.

[F1]

Adaptive empirical-model accuracy for R-MAX: with the stated $m$ and $β$ , the simultaneous optimism and model/policy accuracy conditions hold with probability at least $1 - δ / 2$ , and updates plus escapes total at most $(m + 1) ∣ E_{η} ∣$ .

[F2]

Escape-event reduction for optimistic greedy learning: if those conditions hold with failure probability at most $ρ$ , then taking $B = W = V_{\max}$ and $Q_{c} = (1 - γ)^{- 1}$ gives $N_{4 η} \leq H M$ with failure probability at most $2 ρ$ for the displayed $H, M$ .

[F3]

Admissible upper heuristic for a discounted MDP: $0 \leq V^{*} (s) \leq V_{\max}$ and $U (s, a) \leq V_{\max}$ .

[F4]

The zero-tolerance boundary of PAC-MDP exploration: at zero tolerance the all-zero-optimal-value case has no bad steps; fixed finite legal R-MAX parameters admit an admissible one-state model with infinitely many zero-bad steps, with failure probability exceeding any prescribed confidence tolerance.

Proof

1.1givenF4cases

If $ϵ = 0$ , apply [F4] to obtain both stated endpoint branches. No finite sample-size or positive bonus is defined by substituting zero into the later formulas. For the remainder assume $ϵ > 0$ .

1.2givenF1F2F3algebra

If $ϵ \geq V_{\max}$ , then $V^{*} (s) - ϵ \leq 0$ for every state and every continuation value is nonnegative, so no time is counted. Assume now $ϵ < V_{\max}$ . The stated $η$ satisfies $0 < η < V_{\max} / 4$ and $η (1 - γ) < 1$ . Apply [F1] with confidence parameter $δ / 2$ ; its sample threshold is exactly the displayed $m$ . On its event, R-MAX has the hypotheses of [F2] with $ζ = (m + 1) ∣ E_{η} ∣$ .

1.3givenF1F2algebra

For the uninformative heuristic, $∣ E_{η} ∣ \leq S A$ and $V_{\max} = (1 - γ)^{- 1}$ . The displayed $b$ gives $m = O ((S + \ln (S A / δ)) V_{\max}^{} / [η^{2} (1 - γ)^{2}])$ . Also $H = O ((1 - γ)^{- 1} \ln (1 / [η (1 - γ)]))$ , since $- \ln γ \geq 1 - γ$ for $0 < γ < 1$ , and $M = O ((V_{\max} / η) (ζ + \ln (2 / δ)))$ . Using $ζ \leq (m + 1) S A$ and $η = ϵ / 4$ yields $\tilde{O} (S^{2} A / [ϵ^{3} (1 - γ)^{6}])$ .

2.1step 1.2F2algebra

Take $ρ = δ / 2$ in [F2]. Since $4 η = ϵ$ , the theorem gives $P (N_{ϵ} \leq H M) \geq 1 - δ$ .

3.1givenF1F2F3step 2.1algebra∎

Put $\overset{ˉ}{V} = (1 - γ)^{- 1}$ . Since $V_{\max} \leq \overset{ˉ}{V}$ and $∣ E_{η} ∣ \leq S A$ , the instance parameters satisfy $b \geq \overset{ˉ}{b}$ , $m \leq \overset{ˉ}{m}$ , $ζ \leq \overset{ˉ}{ζ}$ , and $q \geq \overset{ˉ}{q}$ , while the truncation horizon is $H = \overset{ˉ}{H}$ . If $ϵ < V_{\max}$ , then $M \leq \overset{ˉ}{M}$ and step 2.1 yields the uniform bound. If $ϵ \geq V_{\max}$ , then $N_{ϵ} = 0$ . Thus the displayed $\overset{ˉ}{H} \overset{ˉ}{M}$ is a finite PAC-MDP bound in the sense of the Definition.

TheoremStatement: AI-adaptedProof: AI-adaptedprecheck passOpen item page →

PAC-MDP sample complexity of Delayed Q-learning

Statement

Assume AC. Let $M$ be a bounded-reward finite discounted MDP, write $S = ∣ S ∣$ and $A = \max_{s} ∣ A (s) ∣$ , and fix $0 \leq ϵ < (1 - γ)^{- 1}$ , $0 < δ < 1$ , and an admissible heuristic with normalized cap $V_{\max}$ . At $ϵ = 0$ , if $V^{*} (s) = 0$ at every state then $N_{0} = 0$ ; no finite zero-tolerance extension holds uniformly over this class: already at $γ = 0$ , every fixed finite legal batch size $m$ and bonus $ϵ_{1}$ admits an admissible one-state example for Delayed Q-learning with $N_{0} = \infty$ with positive probability. This does not assert failure for every fixed heuristic or model. The parameter formulas below are evaluated only when $ϵ > 0$ . Assume now $ϵ > 0$ . If $ϵ \geq V_{\max}$ , then $N_{ϵ} = 0$ . Otherwise put $η = ϵ / 4, ϵ_{1} = \frac{η (1 - γ)}{3}, κ = ⌈ \frac{S A V_{\max}}{ϵ_{1}} ⌉, N = S A (1 + κ), C_{1} = 1 + γ V_{\max},$ and choose $m = ⌈ \frac{C_{1}^{2}}{2 ϵ_{1}^{2}} \ln \frac{16 N}{δ} ⌉ .$ Run Delayed Q-learning with $m$ and $ϵ_{1}$ . Write $D (s, a) = [U (s, a) - V^{*} (s)]_{+}$ , $G = \sum_{s, a} (1 + D (s, a) / ϵ_{1})$ , and $ζ = ⌈ (2 m + 1) G ⌉$ . Define $q, H, M$ by $q = \frac{η}{4 V_{\max}}, H = {\begin{cases} 1, & γ = 0, \\ \max {1, ⌈ \ln (1 / [η (1 - γ)]) / (- \ln γ) ⌉}, & 0 < γ < 1, \end{cases} M = ⌈ \frac{2 (ζ + 1) + 2 \ln (2 / δ)}{q} ⌉ .$ Then $P (N_{ϵ} \leq H M) \geq 1 - δ$ . Equivalently, up to logarithmic factors, the bound is $\tilde{O} ⁣ (\frac{V_{\max} (1 + γ V_{\max})^{2} [\sum_{s, a} D (s, a) + S A ϵ (1 - γ)]}{ϵ^{4} (1 - γ)^{4}}),$ where $\tilde{O}$ suppresses logarithmic factors. The additive term remains when all heuristic slacks vanish. For $V_{\max} = (1 - γ)^{- 1}$ this gives $\tilde{O} (S A / [ϵ^{4} (1 - γ)^{8}])$ .

For every $ϵ > 0$ , a bound uniform over all MDPs and admissible heuristics with these $S, A, γ$ is obtained by setting $\overset{ˉ}{V} = \frac{1}{1 - γ}, {\overset{ˉ}{ϵ}}_{1} = \frac{ϵ (1 - γ)}{12}, \overset{ˉ}{κ} = ⌈ \frac{S A \overset{ˉ}{V}}{{\overset{ˉ}{ϵ}}_{1}} ⌉, \overset{ˉ}{N} = S A (1 + \overset{ˉ}{κ}),$ $\overset{ˉ}{m} = ⌈ \frac{{\overset{ˉ}{V}}^{2}}{2 {\overset{ˉ}{ϵ}}_{1}^{2}} \ln \frac{16 \overset{ˉ}{N}}{δ} ⌉, \overset{ˉ}{G} = S A (1 + \frac{\overset{ˉ}{V}}{{\overset{ˉ}{ϵ}}_{1}}), \overset{ˉ}{ζ} = ⌈ (2 \overset{ˉ}{m} + 1) \overset{ˉ}{G} ⌉, \overset{ˉ}{q} = \frac{ϵ (1 - γ)}{16},$ and $\overset{ˉ}{H} = {\begin{cases} 1, & γ = 0, \\ \max {1, ⌈ \ln (1 / [(ϵ / 4) (1 - γ)]) / (- \ln γ) ⌉}, & 0 < γ < 1, \end{cases} \overset{ˉ}{M} = ⌈ \frac{2 (\overset{ˉ}{ζ} + 1) + 2 \ln (2 / δ)}{\overset{ˉ}{q}} ⌉ .$ Then $P (N_{ϵ} \leq \overset{ˉ}{H} \overset{ˉ}{M}) \geq 1 - δ$ . This bound depends only on $S, A, ϵ, δ, γ$ .

Statement references

The full zero-tolerance boundary, including admissible algorithm failures and the zero-value success case.

AC for the trajectory laws, concentration, escape reduction, and zero-tolerance suppliers.

The bad-timestep count and the uniform PAC-MDP meaning of a bound.

Admissibility, heuristic slack, and the normalized cap.

The delayed batch update and global learning flags.

Optimism, residual escape updates, and corrected visit counts.

The update/escape count reduction to bad steps.

Strehl, Li, and Littman, Reinforcement Learning in Finite MDPs: PAC Analysis.

Strehl et al., PAC Model-Free Reinforcement Learning.

Szepesvári, Algorithms for Reinforcement Learning.

Facts & Assumptions

Given: AC, the MDP, admissible heuristic, Delayed Q-learning algorithm, and bad-step count in the Statement.

[F1]

Delayed Q-learning optimism and update-count bounds: with the displayed $m$ , all estimates are optimistic, update/escape events total at most $(2 m + 1) G$ , and the lemma event has failure probability at most its confidence parameter.

[F2]

Escape-event reduction for optimistic greedy learning: taking $B = W = V_{\max}$ and $Q_{c} = V_{\max}$ , optimism, policy accuracy at most $η$ , and complexity at most $ζ$ yield $N_{4 η} \leq H M$ with failure at most twice the confidence parameter.

[F3]

Admissible upper heuristic for a discounted MDP: $V^{*} (s) \leq V_{\max}$ , so $N_{ϵ} = 0$ when $ϵ \geq V_{\max}$ .

[F4]

Known-state/action MDP with prescribed absorbing values: an action outside $K_{t}$ has known-model value exactly $Q_{t} (s, a)$ , using its dedicated absorbing state.

[F5]

Well-defined discounted values and optimal Bellman fixed points: the policy value in a finite MDP solves its Bellman equation.

[F6]

Delayed Q-learning with an admissible heuristic: Q-values start at $U \in [0, V_{\max}]$ and each successful update replaces one value by a nonnegative quantity no larger than its old value.

[F7]

The zero-tolerance boundary of PAC-MDP exploration: at zero tolerance the all-zero-optimal-value case has no bad steps; fixed finite legal Delayed Q-learning parameters admit an admissible one-state model with infinitely many zero-bad steps, with failure probability exceeding any prescribed confidence tolerance.

Proof

1.1givenF7cases

If $ϵ = 0$ , apply [F7] to obtain both stated endpoint branches. No finite sample-size or positive bonus is defined by substituting zero into the later formulas. For the remainder assume $ϵ > 0$ .

1.2givenF1F3algebra

If $ϵ \geq V_{\max}$ , then [F3] and nonnegativity of continuation values imply no bad step. Otherwise $η = ϵ / 4 < V_{\max} / 4$ and $η (1 - γ) < 1$ . The displayed batch size is the lemma threshold [F1] with internal failure parameter $δ / 2$ , so with probability at least $1 - δ / 2$ all Q-values are optimistic and the update/escape count is at most $ζ$ .

1.3givenF1F4F5algebra

Extend $V_{t}$ to the state set of $M_{t}$ by setting ${\tilde{V}}_{t} (s) = V_{t} (s)$ on original states and ${\tilde{V}}_{t} (⊥_{s, a}) = Q_{t} (s, a)$ at each added sink. Extend $π_{t}$ by the unique sink action. Both the sink's policy value and its Bellman backup at ${\tilde{V}}_{t}$ equal $Q_{t} (s, a)$ by [F4], so the sink residual is zero. At an original state $s$ , let $a = π_{t} (s)$ . If $(s, a) \notin K_{t}$ , its backup at ${\tilde{V}}_{t}$ is exactly $Q_{t} (s, a) = V_{t} (s)$ by [F4]. If $(s, a) \in K_{t}$ , the definition of $K_{t}$ gives $Q_{t} (s, a) \leq r (s, a) + γ \sum_{s^{'}} P (s^{'} ∣ s, a) V_{t} (s^{'}) + 3 ϵ_{1}$ . Hence on the entire expanded state set, ${\tilde{V}}_{t} \leq T_{M_{t}}^{π_{t}} {\tilde{V}}_{t} + 3 ϵ_{1}$ . Subtract the policy Bellman equation [F5] and set $Δ = \max_{x} [{\tilde{V}}_{t} (x) - V_{M_{t}}^{π_{t}} (x)]_{+}$ . Nonnegative stochastic transition rows give $Δ \leq γ Δ + 3 ϵ_{1}$ , hence on the original states $V_{t} - V_{M_{t}}^{π_{t}} \leq 3 ϵ_{1} / (1 - γ) = η$ .

2.1givenF1F2F6step 1.2step 1.3

The residual sets $K_{t}$ are history-measurable and change only after a Q update; they satisfy the stability condition of [F2]. By [F6], the Q table remains in $[0, V_{\max}]$ . Step 1.2 supplies optimism and the count bound; step 1.3 supplies policy accuracy. Apply [F2] with $ρ = δ / 2$ . Since $4 η = ϵ$ , it gives $P (N_{ϵ} \leq H M) \geq 1 - δ$ .

3.1givenF1F2step 2.1algebra

From the definitions, $G = [\sum_{s, a} D (s, a) + ∣ D ∣ ϵ_{1}] / ϵ_{1} \leq [\sum_{s, a} D (s, a) + S A ϵ_{1}] / ϵ_{1}$ , where $∣ D ∣ = \sum_{s} ∣ A (s) ∣ \leq S A$ , $m = O ((1 + γ V_{\max})^{2} ϵ_{1}^{- 2} \ln (16 N / δ))$ , and $M = O ((V_{\max} / η) (m G + \ln (2 / δ)))$ . Also $H = O ((1 - γ)^{- 1} \ln (1 / [η (1 - γ)]))$ : for $0 < γ < 1$ , the function $x - 1 - \ln x$ has its minimum $0$ at $x = 1$ , so $- \ln γ \geq 1 - γ$ . Substituting $ϵ_{1} = ϵ (1 - γ) / 12$ and $η = ϵ / 4$ into $H (V_{\max} / η) m G$ gives a constant multiple of $\frac{V_{\max} (1 + γ V_{\max})^{2} [\sum_{s, a} D (s, a) + S A ϵ (1 - γ)]}{ϵ^{4} (1 - γ)^{4}} \ln \frac{16 N}{δ} \ln \frac{1}{η (1 - γ)}$ . The remaining $H (V_{\max} / η) \ln (2 / δ)$ term is bounded by the same expression up to logarithmic factors because $m \geq 1$ and $G \geq ∣ D ∣ \geq 1$ . For the uninformative heuristic, $\sum D \leq S A / (1 - γ)$ and $1 + γ V_{\max} = (1 - γ)^{- 1}$ ; substitution yields $\tilde{O} (S A / [ϵ^{4} (1 - γ)^{8}])$ .

4.1givenF1F2F3step 2.1algebra∎

Put $\overset{ˉ}{V} = (1 - γ)^{- 1}$ and ${\overset{ˉ}{ϵ}}_{1} = ϵ (1 - γ) / 12$ . Admissibility gives $0 \leq D (s, a) \leq V_{\max} \leq \overset{ˉ}{V}$ , and hence $C_{1} = 1 + γ V_{\max} \leq \overset{ˉ}{V}$ , $κ \leq \overset{ˉ}{κ}$ , $N \leq \overset{ˉ}{N}$ , $m \leq \overset{ˉ}{m}$ , $G \leq \overset{ˉ}{G}$ , $ζ \leq \overset{ˉ}{ζ}$ , $q \geq \overset{ˉ}{q}$ , and $H = \overset{ˉ}{H}$ . If $ϵ \geq V_{\max}$ , then $N_{ϵ} = 0$ . Otherwise $M \leq \overset{ˉ}{M}$ , so step 2.1 proves the uniform bound. All barred quantities depend only on $S, A, ϵ, δ, γ$ , as required by the Definition.

4 · Examples, counterexamples and false statements

None yet.

Optimistic exploration and PAC-MDP sample complexity

2 · Logical flowchart

3 · Definitions, theorems and proofs

Finite discounted MDP with bounded real rewards

Definition

Definition references

Well-defined discounted values and optimal Bellman fixed points

Statement

Statement references

Facts & Assumptions

Proof

Concentration for adaptively sampled MDP observations

Statement

Statement references

Facts & Assumptions

Proof

PAC-MDP sample complexity of exploration

Definition

Definition references

Admissible upper heuristic for a discounted MDP

Definition

Definition references

Value stability under empirical model error

Statement

Statement references

Facts & Assumptions

Proof

Known-state/action MDP with prescribed absorbing values

Definition

Definition references

R-MAX with an admissible heuristic

Definition

Definition references

Delayed Q-learning with an admissible heuristic

Definition

Definition references

Escape-event reduction for optimistic greedy learning

Statement

Statement references

Facts & Assumptions

Proof

Adaptive empirical-model accuracy for R-MAX

Statement

Statement references

Facts & Assumptions

Proof

Delayed Q-learning optimism and update-count bounds

Statement

Statement references

Facts & Assumptions

Proof

The zero-tolerance boundary of PAC-MDP exploration

Statement

Statement references

Facts & Assumptions

Proof

PAC-MDP sample complexity of R-MAX

Statement

Statement references

Facts & Assumptions

Proof

PAC-MDP sample complexity of Delayed Q-learning

Statement

Statement references

Facts & Assumptions

Proof

4 · Examples, counterexamples and false statements

Sources