Proof of Lemma 5.6, p. 13, (17) — 1 + Q†E ≤ E + δ1 implies E ≥ (1 − δ)Ẽ for the expected travel times Ẽ
ProvedOptimisticPSRL.Diameter.travelTime_le_of_supersolutionLet be a finite MDP (in the application, the extended MDP ) with transition probability vectors , let be a deterministic stationary policy, a target state, , and a vector with entries in . Write for the matrix with entries , . Suppose that for every
that is, (equivalently , display (17)). Then the expected numbers of steps to reach in under satisfy
This is the comparison step of the proof of Lemma 5.6: with the vector of minimum expected times of the true MDP and the policy that, in each state, picks a sample satisfying (16), it gives , hence .
Formalization Note. States are Fin S (0-based) and is the platform's mdpTravelTime M' g s s₂. The hypothesis is the left half of (17), , with moved to the other side because has no subtraction; the conclusion is without the matrix inverse . Unlike the paper's argument, the statement does not assume that the entries of are strictly positive (the paper derives this from the Dirichlet law of the samples); the transition vectors are arbitrary. Values may be ; sums and products are in , and is computed in (positive since ).
import Mathlib import Definitions.Def_FiniteMDPLearning open BanditAlgorithm NNReal ENNReal
namespace OptimisticPSRL.Diameter
theorem travelTime_le_of_supersolution {S A' : ℕ} (M' : FiniteMDP S A') (g : Fin S → Fin A')
(tgt : Fin S) (E : Fin S → ℝ≥0∞) (δ : ℝ≥0) (hδ : δ < 1)
(hsuper : ∀ s, s ≠ tgt →
1 + ∑ s' ∈ Finset.univ.erase tgt, (M'.P s (g s) s' : ℝ≥0∞) * E s' ≤ E s + δ) :
∀ s, s ≠ tgt → ((1 - δ : ℝ≥0) : ℝ≥0∞) * mdpTravelTime M' g s tgt ≤ E s := by sorry
end OptimisticPSRL.Diameter
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.