Finite discounted prevailing-charge value
DefinitionGittinsPrevailingChargeValuebanditsgittins-indexoptimal-stoppingprobability
For a finite-armed rested Markov bandit, the prevailing charge of an arm after a history is the least Gittins index exposed for that arm so far. This module defines the expected prevailing charge selected in round and its finite discounted total
The quantity is the common interface between the retirement-value accounting argument and the deterministic greedy-interleaving comparison.
Formalization Note The expectation is taken over the platform's one-step product of the finite-history law and the policy/transition kernel.
Definition code
import Definitions.Def_GittinsTerminalPotential
open MeasureTheory ProbabilityTheory ENNReal
namespace BanditAlgorithm
/-- Expected prevailing charge selected in round `n`. -/
noncomputable def markovBanditRoundPrevailingCharge
{k : ℕ} {S : Type*} [MeasurableSpace S]
(P : Kernel S S) [IsMarkovKernel P]
(r : S → ℝ) (α : ℝ)
(π : MarkovBanditPolicy k S) (x : Fin k → S)
(n : ℕ) : ℝ :=
∫ p, currentHistoryPrevailingCharge
(gittinsIndex P r α) n p.1 p.2.1
∂(markovBanditMeasure P π x n).compProd
(markovBanditStepKernel P π n)
/-- Finite discounted sum of expected prevailing charges. -/
noncomputable def markovBanditFinitePrevailingChargeValue
{k : ℕ} {S : Type*} [MeasurableSpace S]
(P : Kernel S S) [IsMarkovKernel P]
(r : S → ℝ) (α : ℝ)
(π : MarkovBanditPolicy k S) (x : Fin k → S)
(N : ℕ) : ℝ :=
∑ n ∈ Finset.range N,
α ^ n * markovBanditRoundPrevailingCharge P r α π x n
end BanditAlgorithm
Source
Tor Lattimore and Csaba Szepesvári, Bandit Algorithms (free online edition), https://tor-lattimore.com/downloads/book/book.pdf, §35.4, proof of Theorem 35.9, Part 1 “Prevailing Charge”, printed pp. 451–452 / PDF pp. 459–460.