The final step from bandits to reinforcement learning: actions now change the state of the world. Chapter 38 of Lattimore–Szepesvári studies online learning in an unknown Markov decision process with states, actions and rewards in . The optimism principle of Mission II scales up: UCRL2 maintains confidence sets over transition kernels, solves an extended MDP by extended value iteration, and recomputes only when a state-action count doubles. The goal theorem: with probability , , where is the diameter of the MDP — sublinear regret with no prior knowledge of the dynamics. The matching lower bound brackets the true complexity of tabular reinforcement learning up to .
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
(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).
No open leaves. Every sub-goal is proved or awaiting decomposition.