Theorem 38.6: UCRL2 regret (corrected root)
ProvedBanditAlgorithm.mdp_ucrl2_regret_bound_known_reward_diam_ge_one(UCRL2 regret bound, GOAL, Theorem 38.6 + Eq. (38.12); corrected root — supersedes the Disproved BanditAlgorithm.mdp_ucrl2_regret_bound.) Knowledge model (L&S pp. 522-523, standing assumption of §38.4-38.5: "we assume that only the transition matrix is unknown while the reward function is given"): the reward function is quantified before the policy, so the learner may depend on (UCRL2 uses it) but not on the transition function; its observed history of state-action pairs then determines every received reward.
Let be positive and . For every reward function there is a policy such that for every strongly connected MDP with states, actions, diameter , and every initial state distribution, with probability at least the random regret satisfies
encoded as . Moreover (Eq. (38.12), the same algorithm run with ), for every there is a policy with
Both claims share one universal constant .
Nondegeneracy guard. The hypothesis is automatically satisfied by every strongly connected MDP with at least two states (travelling between distinct states takes at least one step). It excludes the degenerate one-state case , where the purely multiplicative bound is and even the book's literal statement fails — the accepted disproof of the previous root instantiates exactly that case. It also excludes the junk value that the real-valued diameter assigns to non-strongly-connected MDPs (book: ).
This is the capstone of Chapter 38: the price of learning an unknown transition structure under the average-reward criterion, complemented in this mission by the lower bound (Theorem 38.7).
import Definitions.Def_FiniteMDPLearning import Mathlib.Data.Real.Sqrt import Mathlib.Analysis.SpecialFunctions.Log.Basic open MeasureTheory ProbabilityTheory
theorem BanditAlgorithm.mdp_ucrl2_regret_bound_known_reward_diam_ge_one :
∃ C : ℝ, 0 < C ∧
(∀ S A n : ℕ, 0 < S → 0 < A → 0 < n →
∀ δ : ℝ, δ ∈ Set.Ioo (0 : ℝ) 1 →
∀ r : Fin S → Fin A → ℝ, (∀ s a, r s a ∈ Set.Icc (0 : ℝ) 1) →
∃ π : MDPPolicy S A,
∀ M : FiniteMDP S A, M.r = r → M.IsCommunicating →
1 ≤ mdpDiameter M →
∀ μ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 →
∀ r : Fin S → Fin A → ℝ, (∀ s a, r s a ∈ Set.Icc (0 : ℝ) 1) →
∃ π : MDPPolicy S A,
∀ M : FiniteMDP S A, M.r = r → M.IsCommunicating →
1 ≤ mdpDiameter M →
∀ μ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