Bellman optimality inequality upper-bounds the optimal gain
ProvedBanditAlgorithm.mdp_optimal_gain_le_of_bellman_ineqLet be a finite MDP with at least one state and one action, and suppose the pair satisfies the Bellman optimality inequality
with bounded. Then the optimal gain of satisfies
This is the verification half of Theorem 38.2 of Lattimore and Szepesvári — the direction stating that any solution of the optimality equation certifies an upper bound on the achievable long-run average reward. It is the form in which optimistic reinforcement learning uses the theorem: in phase the algorithm UCRL2 computes a pair solving the Bellman optimality equation of the extended MDP, whose transition rows include those of the true MDP whenever the confidence sets hold; the inequality above then holds for the true and gives the optimism of Eq. (38.17), which is Step 1 of the proof of Theorem 38.6.
Note that the hypothesis is only an inequality and that is the supremum over all history-dependent randomised policies and all starting states, so no communication assumption is needed.
The proof divides the finite-horizon estimate by : the span disappears in the limit, so the gain of every policy from every state is at most , and is the supremum of those gains.
import Definitions.Def_FiniteMDPLearning import Mathlib.Probability.Kernel.Composition.IntegralCompProd open MeasureTheory ProbabilityTheory
theorem BanditAlgorithm.mdp_optimal_gain_le_of_bellman_ineq {S A : ℕ}
(hS : 0 < S) (hA : 0 < A) (M : FiniteMDP S A) (ρ : ℝ) (v : Fin S → ℝ) (lo hi : ℝ)
(hv : ∀ s, v s ∈ Set.Icc lo hi)
(hbell : ∀ s a, M.r s a + ∑ s', (M.P s a s' : ℝ) * v s' ≤ ρ + v s) :
mdpOptimalGain M ≤ ρ := by
sorry