Greedy charge-stack interleaving maximizes the discounted sum
ProvedBanditAlgorithm.tsum_chargeStackInterleaving_le_greedybanditsgittins-indexhardy-littlewood
Let be a finite number of arms. For each arm , let be a nonincreasing real-valued charge stack. An action sequence is greedy when, at every round, it selects an arm whose currently exposed charge is maximal.
For a discount factor , let denote the charge exposed at round by an arbitrary action sequence . If both discounted interleavings are summable, then
Thus greedy interleaving maximizes the geometrically discounted total of decreasing stacks. This is the deterministic Hardy--Littlewood step used in the Gittins-index theorem.
Preamble
import Definitions.Def_GittinsChargeInterleaving
Formal statement
theorem BanditAlgorithm.tsum_chargeStackInterleaving_le_greedy
{k : ℕ} {H : Fin k → ℕ → ℝ} {astar : ℕ → Fin k}
(hH : ∀ i, Antitone (H i))
(hastar : IsGreedyChargeStackInterleaving H astar)
{α : ℝ} (hα0 : 0 ≤ α) (hα1 : α ≤ 1)
(a : ℕ → Fin k)
(hsuma : Summable
(fun n ↦ α ^ n * chargeStackInterleaving H a n))
(hsumg : Summable
(fun n ↦ α ^ n * chargeStackInterleaving H astar n)) :
(∑' n : ℕ, α ^ n * chargeStackInterleaving H a n) ≤
∑' n : ℕ, α ^ n * chargeStackInterleaving H astar n := by
sorrySource
Tor Lattimore and Csaba Szepesvári, Bandit Algorithms (free online edition), https://tor-lattimore.com/downloads/book/book.pdf, Section 35.4, printed p. 451 / PDF p. 459, Lemma 35.10; the proof is assigned as Exercise 35.9.