BanditAlgorithm.gittins_index_theorem
Proved(Gittins index theorem, L&S Theorem 35.9) For the infinite-horizon -discounted -armed Markov bandit on a Borel state space, assume the integrability Assumption 35.6:
(hence for all the Markov chains of the game). Then every Gittins index policy (activating an arm of maximal index each round, ties arbitrary) attains the supremum of the expected total discounted reward over all policies:
import Mathlib.MeasureTheory.Constructions.Polish.Basic import Definitions.Def_GittinsIndex open MeasureTheory ProbabilityTheory ENNReal
theorem BanditAlgorithm.gittins_index_theorem {k : ℕ} {S : Type*} [MeasurableSpace S]
[StandardBorelSpace S] (P : Kernel S S) [IsMarkovKernel P]
{r : S → ℝ} (hr : Measurable r) {α : ℝ} (hα0 : 0 < α) (hα1 : α < 1)
(hint : DiscountedRewardIntegrable P r α)
(πstar : MarkovBanditPolicy k S) (hπ : IsGittinsIndexPolicy P r α πstar)
(x : Fin k → S) :
markovBanditDiscountedValue P r α πstar x =
⨆ π : MarkovBanditPolicy k S, markovBanditDiscountedValue P r α π x := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Setup. The model of the accompanying bundle: a measurable state space , a Markov kernel on , a reward , a discount , and arms all sharing . A policy is a per-round probability kernel from histories (past (state-vector, pulled-arm) pairs plus the current state vector) to arms. Its discounted value from initial state vector is , where is the expected value of at the pre-transition state of the arm pulled at round , under the interaction law in which only the pulled arm's state moves (one step of ) each round. The Gittins index of a single-arm state is the supremum over stopping times of the single-arm chain (started at , transitions ) of .
Assertion.
the supremum ranging over all history-dependent randomized policies of the type above.
Hypotheses.
- is an arbitrary natural number (including ).
- is a standard Borel measurable space; is a Markov kernel; is measurable.
- and (both strict).
- Discounted-reward integrability: for every start , along the single-arm chain law (terms clamped to ; the clamp is inert here since ).
- is a Gittins-index policy: at every round and every history it puts probability on the set of arms whose current-state Gittins index is maximal.
- is arbitrary.
Edge cases.
- The claim is an exact equality, so it simultaneously asserts that is optimal and that the supremum is attained.
- The right-hand side is a real-valued supremum over the type of all policies, with junk value if the value set were unbounded above; each is itself defined through the series-defaults-to- and integral-defaults-to- conventions, with no integrability requirement on the competing policies' values.
- For no policy exists, so the statement is vacuous (no can be supplied).
Confirmed by the mission captain (proposal self-audit).