Reduction step — optimizing within Π(s*) is a bandit problem with one state fewer, the reduced bandit with rate (2.3)
ProvedTsitsiklisGittins.IndexTheorem.reduction_step_valuesConsider the semi-Markov multi-armed bandit problem with finite nonempty state spaces, and let have maximal reward rate, . Suppose is not a singleton. Let be the set of policies that give top priority to (they play bandit whenever it is at ), and let the reduced problem be obtained by reducing bandit by removing , with the reduced statistics and the rate of (2.3). Then:
- the reduced data form a valid bandit problem with discount rate , and the number of present states is one less than ;
- for every and every joint state in which bandit is not at ,
where is the expected discounted reward in the reduced problem; 3. every policy of the reduced problem has, on these joint states, the same reduced value as some policy in .
Together, (2) and (3) say that the problem of finding an optimal policy within is the new multi-armed bandit problem, whose state spaces have total cardinality ; this is what the induction of Theorem 2.1 is applied to.
Formalization Note A policy of the reduced problem is still a map on all joint states; its choices at joint states with bandit at are irrelevant there, since the reduced data have no transition into . The maximality of is the page's setting; the value identity itself does not use it. The reduced problem may contain composite plays that never end (when is absorbing); validity allows this.
import Mathlib import Definitions.Def_TsitsiklisGittins_IndexTheorem_Reduction
namespace TsitsiklisGittins.IndexTheorem
/-- Reduction step in the proof of Theorem 2.1 of Tsitsiklis (1994), p. 197. Let `s = ⟨i*, s*⟩`
have maximal reward rate and let `𝒳_{i*}` not be a singleton. Reducing bandit `i*` by removing
`s*` gives a new multi-armed bandit problem (a valid stage) with one state fewer, and
(a) every policy giving top priority to `s*` has, from every joint state in which bandit `i*` is
not at `s*`, the same expected discounted reward in the original and in the reduced problem;
(b) every policy of the reduced problem has, on those joint states, the value of such a policy. -/
theorem reduction_step_values {n : ℕ} [NeZero n] {X : Fin n → Type} [∀ i, Fintype (X i)] [∀ i, DecidableEq (X i)]
[∀ i, Nonempty (X i)] [∀ i, MeasurableSpace (X i)] [∀ i, MeasurableSingletonClass (X i)]
(B : SemiMarkovBandit n X)
(s : Σ i, X i) (hmax : ∀ q : Σ i, X i, B.rate q ≤ B.rate s) (hns : ∃ x : X s.1, x ≠ s.2) :
(B.initStage.reduce s).Valid B.β ∧
(B.initStage.reduce s).alive.card + 1 = Fintype.card (Σ i, X i) ∧
(∀ π : Policy n X, (∀ z : JointState n X, z s.1 = s.2 → π z = s.1) →
∀ z : JointState n X, z s.1 ≠ s.2 → B.value π z = (B.initStage.reduce s).value π z) ∧
(∀ π' : Policy n X, ∃ π : Policy n X, (∀ z : JointState n X, z s.1 = s.2 → π z = s.1) ∧
∀ z : JointState n X, z s.1 ≠ s.2 →
(B.initStage.reduce s).value π z = (B.initStage.reduce s).value π' z) := by sorry
end TsitsiklisGittins.IndexTheorem
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.