Finite discounted greedy charge-stack interleaving
ProvedBanditAlgorithm.discounted_charge_stack_interleaving_le_greedy_prefixbanditsgittins-indexprobability
Let be a nonincreasing real-valued charge stack for each of arms. An interleaving chooses one stack at each round and receives its next unused charge. Suppose the interleaving is greedy through round : at every , its selected next charge is at least the currently available next charge of every arm. For any other interleaving and any discount factor ,
where is the number of entries already taken from stack before round under the relevant interleaving.
This finite-horizon greedy-interleaving inequality isolates the deterministic rearrangement step used in the Gittins-index proof and is reusable independently of the stochastic bandit coupling.
Preamble
import Definitions.Def_GittinsChargeInterleaving
Formal statement
namespace BanditAlgorithm
theorem discounted_charge_stack_interleaving_le_greedy_prefix
{k N : ℕ} {H : Fin k → ℕ → ℝ} {astar : ℕ → Fin k}
(hH : ∀ i, Antitone (H i))
(hastar : ∀ n, n < N → ∀ i,
H i (stackPullCountBefore astar i n) ≤
H (astar n) (stackPullCountBefore astar (astar n) n))
{α : ℝ} (hα0 : 0 ≤ α) (hα1 : α ≤ 1)
(a : ℕ → Fin k) :
(∑ n ∈ Finset.range N,
α ^ n * chargeStackInterleaving H a n) ≤
∑ n ∈ Finset.range N,
α ^ n * chargeStackInterleaving H astar n := by
sorry
end BanditAlgorithm
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