Finite prevailing-charge stack-coupling representation
ProvedBanditAlgorithm.gittins_finite_prevailing_charge_eq_stack_coupling_valuebanditsgittins-indexprobability
Fix a finite horizon , an initial state vector, and a Markov bandit policy . On a common product space, sample one independent infinite Markov trajectory for each arm. For every length- action sequence, weight the associated interleaving of the arms' prevailing-charge stacks by the likelihood that follows that action sequence. Then the resulting finite sum of weighted stack integrals is exactly the policy's expected finite discounted prevailing-charge value:
Here is the product law of the independent arm trajectories, is the action-sequence likelihood, and counts prior selections of arm .
This theorem isolates the finite common-stack coupling identity used in the Gittins-index comparison.
Preamble
import Definitions.Def_GittinsPrevailingChargeValue
Formal statement
open MeasureTheory ProbabilityTheory ENNReal
theorem BanditAlgorithm.gittins_finite_prevailing_charge_eq_stack_coupling_value
{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 α)
(π : MarkovBanditPolicy k S) (x : Fin k → S) (N : ℕ) :
let count := fun (a : Fin N → Fin k) (i : Fin k) (t : ℕ) ↦
∑ s : Fin N, if (s : ℕ) < t ∧ a s = i then 1 else 0
let historyBefore := fun (a : Fin N → Fin k)
(ω : Fin k → ℕ → S) (t : Fin N) ↦
((fun u : Fin (t : ℕ) ↦
((fun i ↦ ω i (count a i u)),
a ⟨u, lt_trans u.isLt t.isLt⟩)),
fun i ↦ ω i (count a i t))
let likelihood := fun (a : Fin N → Fin k) (ω : Fin k → ℕ → S) ↦
∏ t : Fin N, (π.select t) (historyBefore a ω t) {a t}
let charge := fun (ω : Fin k → ℕ → S) (i : Fin k) (u : ℕ) ↦
(Finset.range (u + 1)).inf'
⟨0, Finset.mem_range.2 (Nat.zero_lt_succ u)⟩
(fun v ↦ gittinsIndex P r α (ω i v))
let value := fun (a : Fin N → Fin k) (ω : Fin k → ℕ → S) ↦
∑ t : Fin N, α ^ (t : ℕ) *
charge ω (a t) (count a (a t) t)
let stackMeasure : Measure (Fin k → ℕ → S) :=
Measure.pi (fun i ↦ markovChainMeasure P (x i))
markovBanditFinitePrevailingChargeValue P r α π x N =
∑ a : Fin N → Fin k,
∫ ω, value a ω ∂stackMeasure.withDensity (likelihood a) := by
sorry
Source
Tor Lattimore and Csaba Szepesvári, Bandit Algorithms, §35.4, proof of Lemma 35.10, printed pp. 452–453 (free PDF pp. 460–461), https://tor-lattimore.com/downloads/book/book.pdf