UCRL2 expected regret bound with known rewards
ProvedBanditAlgorithm.mdp_ucrl2_expected_regret_known_reward_diam_ge_onebanditsexpected-regretreinforcement-learningucrl2
There is a universal constant such that, for every positive number of states , actions , and rounds , and every known reward function , some policy independent of the unknown transition matrix satisfies, for every communicating MDP with reward function , diameter , and every initial distribution,
This is the expected-regret form of UCRL2 obtained from the high-probability analysis with a horizon-dependent confidence level. It uses the same known-reward learning model as Theorem 38.6 and excludes only the zero-diameter degeneracy.
Formalization Note The policy may depend on the horizon and the known reward function, matching the quantifier order in the source analysis.
Preamble
import Definitions.Def_FiniteMDPLearning open MeasureTheory ProbabilityTheory ENNReal
Formal statement
theorem BanditAlgorithm.mdp_ucrl2_expected_regret_known_reward_diam_ge_one :
∃ C : ℝ, 0 < C ∧
∀ 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
sorrySource
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), Eq. (38.12), printed p. 523 / PDF p. 532, derived from Theorem 38.6 in Exercise 38.18.