Lemma 2, (5), p. 5 — dynamic programming equation V^M_{µ,i} = T^M_{µ(·,i)} V^M_{µ,i+1}, V^M_{µ,τ+1} = 0
ProvedPosteriorSamplingRL.Regret.lemma2_dynamic_programmingbellman-equationdynamic-programmingmarkov-decision-processp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite MDP of the family, with reward distributions supported on , and let be a deterministic policy. The path-defined value functions satisfy
with , where is the Bellman operator of the stationary rule .
The equation lets one compare value functions of two MDPs one step at a time; it is the tool behind the Bellman-error decomposition (6).
Formalization Note Steps are 0-based: the conclusion is stated for Lean steps , the paper's , and is value F θ π τ = 0. The value is defined by the expectation along the trajectory, not by this recursion, so the equation is not definitional.
Preamble
import Mathlib import Definitions.Def_PosteriorSamplingRL_Regret_MDP open MeasureTheory ProbabilityTheory
Formal statement
namespace PosteriorSamplingRL.Regret
/-- Lemma 2 (Dynamic programming equation), (5) (arXiv:1306.0940v5, p. 5). For every MDP `M_θ`
and policy `π : S × {1, …, τ} → A`, `V^θ_{π,i} = T^θ_{π(·,i)} V^θ_{π,i+1}` for `i = 1, …, τ`, with
`V^θ_{π,τ+1} = 0`. In 0-based steps: `value j = T_{π(·,j)} (value (j+1))` for `j < τ`, and
`value τ = 0`. -/
theorem lemma2_dynamic_programming (S A τ : ℕ) (Θ : Type) [MeasurableSpace Θ]
(F : MDPFamily S A Θ) (θ : Θ) (π : Policy S A τ) :
(∀ (j : ℕ) (hj : j < τ) (s : Fin S),
value F θ π j s = bellman F θ (fun s' => π s' ⟨j, hj⟩) (value F θ π (j + 1)) s) ∧
value F θ π τ = 0 := by sorry
end PosteriorSamplingRL.Regret
Source
arXiv:1306.0940v5, Lemma 2, (5), p. 5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.