Bellman optimality inequality upper-bounds the expected reward
ProvedBanditAlgorithm.mdp_expected_reward_le_of_bellman_ineqLet be a finite MDP and suppose the pair satisfies the Bellman optimality inequality
with taking values in . Then for every policy , every initial distribution and every horizon ,
The error term is the span of , and the bound holds for arbitrary history-dependent randomised policies, with no communication or ergodicity assumption on .
This is the finite-horizon estimate underlying Theorem 38.2 of Lattimore and Szepesvári, and it is what the analysis of UCRL2 consumes: in phase the algorithm solves the Bellman optimality equation of the extended MDP, and because the true MDP lies in the confidence set its own rows satisfy the inequality above, which yields the optimism of Eq. (38.17).
The proof accumulates the inequality along the interaction. Writing , the hypothesis gives , and the last term is the conditional expectation of given the history, so the quantity is non-increasing in expectation. Formally one shows by induction on the horizon, using the Markov property of the trajectory measure, that the expected reward of rounds plus the expected value of the state reached after them is at most ; discarding the terminal value costs at most .
import Definitions.Def_FiniteMDPLearning import Mathlib.Probability.Kernel.Composition.IntegralCompProd open MeasureTheory ProbabilityTheory
theorem BanditAlgorithm.mdp_expected_reward_le_of_bellman_ineq {S A : ℕ}
(M : FiniteMDP S A) (μ0 : MDPStateDistribution S) (π : MDPPolicy 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) (n : ℕ) :
mdpExpectedReward M μ0 π n ≤ n * ρ + (hi - lo) := by
sorry