Proof of Lemma 5.6, p. 13 — first-step analysis: E = 1 + P†_π E for expected travel times
ProvedOptimisticPSRL.Diameter.first_step_travelTimefirst-step-analysishitting-timemarkov-chainmdpp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite MDP with transition probability vectors , let be a deterministic stationary policy, and let denote the expected number of steps to reach the target from under . For every state ,
In matrix form, the vector solves , where is the matrix with entries , . This is the first-step equation the proof of Lemma 5.6 starts from.
Formalization Note. States and actions are 0-based (Fin S, Fin A); is the platform's mdpTravelTime M f s s₂ in . The identity is stated for every deterministic stationary policy (the proof uses it for one) and with no finiteness assumption: both sides may equal . Products and sums are taken in , where .
Preamble
import Mathlib import Definitions.Def_FiniteMDPLearning open BanditAlgorithm NNReal ENNReal
Formal statement
namespace OptimisticPSRL.Diameter
theorem first_step_travelTime {S A : ℕ} (M : FiniteMDP S A) (f : Fin S → Fin A)
(src tgt : Fin S) (hne : src ≠ tgt) :
mdpTravelTime M f src tgt =
1 + ∑ s' ∈ Finset.univ.erase tgt, (M.P src (f src) s' : ℝ≥0∞) * mdpTravelTime M f s' tgt := by sorry
end OptimisticPSRL.Diameter
Source
Agrawal & Jia, Posterior sampling for reinforcement learning: worst-case regret bounds, arXiv:1705.07041v3, p. 13, proof of Lemma 5.6, first display (E = 1 + P†_π E)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.