Nonnegativity of expected Gittins terminal potential
ProvedBanditAlgorithm.gittins_expected_terminal_potential_nonnegbanditsgittins-indexprobability
At every finite horizon, the expected Gittins terminal retirement potential is nonnegative:
This holds for every Markov bandit policy and initial state vector under the discounted absolute-reward integrability assumption. It records the lower bound needed when the terminal term is removed by a squeeze argument.
Preamble
import Definitions.Def_GittinsTerminalPotential
Formal statement
open MeasureTheory ProbabilityTheory ENNReal
theorem BanditAlgorithm.gittins_expected_terminal_potential_nonneg
{k : ℕ} {S : Type*} [MeasurableSpace S]
(P : Kernel S S) [IsMarkovKernel P]
{r : S → ℝ} (hr : Measurable r)
{α : ℝ} (hα0 : 0 < α) (hα1 : α < 1)
(hint : DiscountedRewardIntegrable P r α)
(π : MarkovBanditPolicy k S) (x : Fin k → S) (N : ℕ) :
0 ≤ markovBanditExpectedRetirementPotential P r α π x N := by
sorry
Source
Tor Lattimore and Csaba Szepesvári, Bandit Algorithms, §35.4, retirement-option argument in proof of Lemma 35.10, printed pp. 452–453 (free PDF pp. 460–461), https://tor-lattimore.com/downloads/book/book.pdf