Hölder step:
ProvedBanditAlgorithm.mdp_inner_prob_diff_le_half_l1_mul_spanLet be probability vectors on a finite set and let take values in . Then
This is the Hölder step of Eq. (38.20) in the proof of the UCRL2 regret bound (Lattimore and Szepesvári, Theorem 38.6), where is the optimistic transition vector , the true one, and the optimistic value function. The book applies Hölder's inequality together with the normalisation of Eq. (38.19); the statement above isolates the underlying fact and makes the normalisation unnecessary, because the bound is stated directly in terms of the range of .
The proof is one line of algebra: a difference of probability vectors is orthogonal to constants, , so may be replaced by , which has sup-norm at most ; Hölder's inequality applied to the recentred vector gives the claim.
Taking recovers the standard bound , which is the form in which the estimate is used throughout the analysis of optimistic reinforcement learning.
import Mathlib.Analysis.SpecialFunctions.Sqrt import Mathlib.Algebra.Order.BigOperators.Ring.Finset
theorem BanditAlgorithm.mdp_inner_prob_diff_le_half_l1_mul_span
{ι : Type*} [Fintype ι] (P Q v : ι → ℝ) (a b : ℝ)
(hP : ∑ i, P i = 1) (hQ : ∑ i, Q i = 1)
(hv : ∀ i, v i ∈ Set.Icc a b) :
∑ i, (P i - Q i) * v i ≤ (∑ i, |P i - Q i|) / 2 * (b - a) := by
sorry