Lemma 5.6, p. 12 — if every state-action pair has a sample δ-optimistic for every E^s, then D(M̃) ≤ D/(1−δ)
ProvedOptimisticPSRL.Diameter.lemma5_6_extended_diameter_leLet be a finite MDP with states , actions , transition probability vectors and diameter (Definition 2: the maximum over ordered pairs of distinct states of the minimum over deterministic stationary policies of the expected number of steps from to ). For each target state let be the vector of minimum expected times to reach , .
Let and let , , be probability vectors on , one family for every state-action pair, and let be the extended MDP in which taking action in state moves according to . Let . Suppose that for every target state , every state and every action there is a sample index with
Then
In the paper this lemma is what makes the sampled extended MDP of each epoch communicating with diameter of the same order as the true one; combined with Lemma 5.7, which shows that (16) holds with with high probability for the posterior samples, it yields , an ingredient of the regret bound (Theorem 1).
Formalization Note. States, actions and samples are 0-based (Fin S, Fin A, Fin ψ); the extended MDP is extendedMDP M Q hQ, with action encoded as finProdFinEquiv (a, j) in Fin (A * ψ). Diameters are the platform's mdpDiameterENN in , is minTravel M s, the inner products are computed in (with ), and is division in by the positive number . The printed (16) uses the letter both for the target of and for the state of , quantified "for every "; the proof applies it at the current state with target , so the target is quantified separately here (for every target, state and action). No communicating assumption is made: if the bound holds trivially, so the statement generalizes the paper's. The sample vectors are arbitrary probability vectors; no positivity of their entries and no distributional assumption is made.
import Mathlib import Definitions.Def_FiniteMDPLearning import Definitions.Def_OptimisticPSRL_Diameter_Setting open BanditAlgorithm NNReal ENNReal
namespace OptimisticPSRL.Diameter
theorem lemma5_6_extended_diameter_le {S A ψ : ℕ} (M : FiniteMDP S A)
(Q : Fin S → Fin A → Fin ψ → Fin S → ℝ≥0) (hQ : ∀ s a j, ∑ i, Q s a j i = 1)
(δ : ℝ≥0) (hδ : δ < 1)
(h16 : ∀ tgt s : Fin S, ∀ a : Fin A, ∃ j : Fin ψ,
∑ i, (Q s a j i : ℝ≥0∞) * minTravel M tgt i ≤
∑ i, (M.P s a i : ℝ≥0∞) * minTravel M tgt i + δ) :
mdpDiameterENN (extendedMDP M Q hQ) ≤ mdpDiameterENN M / ((1 - δ : ℝ≥0) : ℝ≥0∞) := by sorry
end OptimisticPSRL.Diameter
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.