§2.6.4 (Katehakis–Veinott): the restart-in-state value iteration converges to μ(ξ) = max(0, ν(B, ξ)/(1 − a))
ProvedAllocationIndices.restart_value_iteration§2.6.4. Fix a state and let be the maximal payoff obtainable from the bandit when it starts in state and may be restarted in state whenever and as often as one likes; then . Katehakis and Veinott (1987) compute it by value iteration: , , and as .
Formally: for a bandit process on a countable state space with bounded reward, and any state , the iteration restartIter P r a ξ satisfies
Why the maximum with . Restarting is free in the iteration ( with no reward and no discounting), so restarting forever is available and the restart value is never negative: for a single state with reward the iteration is identically while . The book's derivation takes the supremum over only, which forces at least one continuation between restarts; for a nonnegative index (in particular for nonnegative rewards) the two agree and the limit is the book's . Checked on random finite chains with rewards of both signs.
import Definitions.Def_AllocationIndices_Index open MeasureTheory ProbabilityTheory BanditAlgorithm
namespace AllocationIndices
theorem restart_value_iteration {S : Type*} [MeasurableSpace S] [Countable S]
[MeasurableSingletonClass S] (P : Kernel S S) [IsMarkovKernel P] {r : S → ℝ}
(hr : BoundedReward r) {a : ℝ} (ha0 : 0 < a) (ha1 : a < 1) (ξ : S) :
Filter.Tendsto (fun k ↦ restartIter P r a ξ k ξ) Filter.atTop
(nhds (max 0 (gittinsIndex P r a ξ / (1 - a)))) := by sorry
end AllocationIndices
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.