BanditAlgorithm.mdp_ucrl2_regret_bound
DisprovedSUPERSEDED (2026-07-30, root replaced after the accepted disproof): two defects — (1) the one-state degenerate case was not excluded (the accepted disproof); (2) the policy was quantified before the reward function, contradicting the book's standing assumption (p.522) that "only the transition matrix is unknown while the reward function is given" — a reward-blind policy cannot learn , so the statement also fails non-degenerately. The corrected root is BanditAlgorithm.mdp_ucrl2_regret_bound_known_reward_diam_ge_one ( quantification + guard).
(UCRL2 regret bound, GOAL; L&S Theorem 38.6 and Eq. (38.12)) There is a universal constant such that:
(i) for all and there exists a policy (UCRL2, Algorithm 28; the book's ‘efficiently computable’ is dropped — only existence is formalized) such that for every strongly connected MDP with states, actions, rewards in and every initial state distribution, with probability at least ,
and (ii) for all there is a policy (the same algorithm run with , Eq. (38.12) / Exercise 38.18) with
import Definitions.Def_FiniteMDPLearning import Mathlib.Data.Real.Sqrt import Mathlib.Analysis.SpecialFunctions.Log.Basic open MeasureTheory ProbabilityTheory
theorem BanditAlgorithm.mdp_ucrl2_regret_bound :
∃ C : ℝ, 0 < C ∧
(∀ S A n : ℕ, 0 < S → 0 < A → 0 < n →
∀ δ : ℝ, δ ∈ Set.Ioo (0 : ℝ) 1 →
∃ π : MDPPolicy S A,
∀ M : FiniteMDP S A, M.IsCommunicating →
∀ μ0 : MDPStateDistribution S,
mdpMeasure M μ0 π n
{h | C * mdpDiameter M * S *
Real.sqrt (A * n * Real.log (n * S * A / δ)) ≤
mdpRegret M n h} ≤
ENNReal.ofReal δ) ∧
(∀ S A n : ℕ, 0 < S → 0 < A → 0 < n →
∃ π : MDPPolicy S A,
∀ M : FiniteMDP S A, M.IsCommunicating →
∀ μ0 : MDPStateDistribution S,
∫ h, mdpRegret M n h ∂(mdpMeasure M μ0 π n) ≤
1 + C * mdpDiameter M * S *
Real.sqrt (2 * A * n * Real.log n)) := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Setup. Notation from the finite-MDP bundle. A finite MDP with states and actions has transition probabilities (rows summing to ) and rewards . is the law of the -round trajectory (round- state , subsequent states from , actions from the history-dependent policy ). The pathwise regret is with the optimal gain. is the real diameter: over memoryless deterministic maps , where is the expected first-visit index of from (tail-sum form), converted from to with . " communicating": every ordered pair of distinct states is linked by some policy and horizon with nonzero visiting probability.
Assertion. There exists a single constant such that both of the following hold.
- (High-probability bound) For all and every (open interval), there exists one policy — chosen knowing only — such that for every communicating MDP on these state/action counts and every initial distribution :
- (Expectation bound) For all , there exists a policy such that for every communicating and every :
Hypotheses.
- , , (strict); in part 1, strictly.
- communicating (in the sense above); arbitrary.
- The same constant serves both parts.
Edge cases.
- The quantifier order is the content: in each part the policy is fixed before the MDP is chosen, yet the threshold/bound is expressed through the unknown 's own diameter and (inside ) its optimal gain .
- carries the junk: "communicating" quantifies over arbitrary history-dependent policies, whereas the diameter's infimum ranges only over memoryless deterministic maps, so the hypothesis does not by itself preclude , in which case the part-1 threshold is and the part-2 bound reduces to .
- The deviation event is one-sided and uses ("regret at least the threshold"); its probability, an extended nonnegative real, is compared against the cast of into .
- is the real natural logarithm applied to the real quotient (part 1) and to (part 2); expectations are Bochner integrals over the finite trajectory space.
- The pathwise regret may be negative; only its upper deviations are constrained.
Confirmed by the mission captain (proposal self-audit).