Successors at visits to a pair are NOT i.i.d. (false as stated)
DisprovedBanditAlgorithm.mdp_visit_successors_iid_empirical_representation⚠️ Retired — specification defect
The Lean statement below does not encode the problem shown on this page, so its
Disprovedstatus carries no information about that problem. Do not import this node or use it as a dependency.
Fix a finite MDP , an initial distribution, a policy, a horizon , a state-action pair and an integer . There are random variables on the space of trajectories which are measurable, independent, each distributed as the true transition row , and which represent the empirical row: whenever a trajectory has had exactly transitions out of observed before some time , its empirical row mdpEmpiricalRow at that time is the empirical distribution
of that sample.
This is the step of the analysis of UCRL2 at which the interaction protocol is converted into an i.i.d. sample, and it is the only place where the sequential nature of the data is used. It is not a triviality: the rounds at which the pair is played are stopping times, chosen by a policy that may react to everything observed so far, so the successor states are not a fixed block of the trajectory. What makes the statement true is the strong Markov property of the protocol -- conditionally on the history up to the -th visit to , the next state is drawn from regardless of how that visit came about -- so the successors of the successive visits to a fixed pair are independent draws from the true row.
Formalization Note The conclusion is an existential over the sample rather than a statement about a conditional law, which is what makes it directly usable: the sample is defined on the trajectory space itself, so a concentration inequality for i.i.d. samples applies to it verbatim under the trajectory measure, and the last clause transfers the conclusion back to the empirical row on the event that the count equals .
Why this node was retired
The posted statement is
theorem BanditAlgorithm.mdp_visit_successors_iid_empirical_representation
(S A n : ℕ) (hS : 0 < S) (hA : 0 < A)
(M : FiniteMDP S A) (μ0 : MDPStateDistribution S) (π : MDPPolicy S A)
(s : Fin S) (a : Fin A) (m : ℕ) (hm : 0 < m) :
∃ X : Fin m → MDPTrajectory S A n → Fin S,
(∀ i, Measurable (X i)) ∧
iIndepFun X (mdpMeasure M μ0 π n) ∧
(∀ (i : Fin m) (s' : Fin S),
(mdpMeasure M μ0 π n).real {h | X i h = s'} = (M.P s a s' : ℝ)) ∧
(∀ (h : MDPTrajectory S A n) (k : ℕ), k ≤ n →
mdpObservedCount h k s a = m →
∀ s' : Fin S,
mdpEmpiricalRow h k s a s'
= (∑ i : Fin m, if X i h = s' then (1 : ℝ) else 0) / (m : ℝ)) := by
sorry
Unconditional IID variables with a specified non-Dirac law are required on every finite trajectory space, including the singleton horizon-zero space.
The recorded counterexample refutes the statement as encoded. It says nothing about the problem shown above, which is a different proposition.
Proposed corrected statement
Construct potential successor samples on an explicitly enlarged probability space with independent streams for every state-action pair and prove the trajectory coupling. Alternatively state the needed event-level deviation bound P(N(s,a)=m ∧ ‖P̂−P‖₁≥ε)≤2ˢ exp(−mε²/2), with the exact visit-count definition. Do not assume conditioning on N=m automatically preserves IID laws.
Diagnosis and correction from the public Prove2Me statement audit (wamlat/prove2me-errors). The correction is natural-language mathematics and is not Lean-verified — it is a specification for a corrected node, not a drop-in replacement. No corrected replacement node exists yet.
import Definitions.Def_UCRL2ConfidenceSets import Mathlib.Probability.Moments.SubGaussian open MeasureTheory ProbabilityTheory open scoped NNReal ENNReal
theorem BanditAlgorithm.mdp_visit_successors_iid_empirical_representation
(S A n : ℕ) (hS : 0 < S) (hA : 0 < A)
(M : FiniteMDP S A) (μ0 : MDPStateDistribution S) (π : MDPPolicy S A)
(s : Fin S) (a : Fin A) (m : ℕ) (hm : 0 < m) :
∃ X : Fin m → MDPTrajectory S A n → Fin S,
(∀ i, Measurable (X i)) ∧
iIndepFun X (mdpMeasure M μ0 π n) ∧
(∀ (i : Fin m) (s' : Fin S),
(mdpMeasure M μ0 π n).real {h | X i h = s'} = (M.P s a s' : ℝ)) ∧
(∀ (h : MDPTrajectory S A n) (k : ℕ), k ≤ n →
mdpObservedCount h k s a = m →
∀ s' : Fin S,
mdpEmpiricalRow h k s a s'
= (∑ i : Fin m, if X i h = s' then (1 : ℝ) else 0) / (m : ℝ)) := by
sorry