Theorem 4.8: any index for the class of bandit processes with discount factor a is strictly increasing in ν(B, x)
ProvedAllocationIndices.index_unique_up_to_increasingTheorem 4.8. Any index for (), if there is one, must be a strictly increasing function of .
Formally: let assign a real number to every bandit process and state (an IndexFunction), and suppose is an index for every SFABP formed by a bandit process on a countable state space with bounded reward and a standard bandit process: every policy that continues an arm of maximal -value at each decision time is optimal for that family. Then for any two bandit processes on and on (countable, bounded rewards) and states ,
The hypothesis is weaker than the book's "index for " (optimality for every finite SFABP), since the proof only uses the two-member families , so the statement is slightly stronger than printed; the conclusion compares processes on different state spaces, as the book's does.
The conclusion is the order form of "a strictly increasing function of ". The printed form also says that is a function of , i.e. equal indices get equal -values, and that part is not true. An index may break the ties within one level of in any way: with a different value on some of the bandit processes of index exactly still orders every family as does, up to ties, which Theorem 2.1 allows to be broken arbitrarily.
import Definitions.Def_AllocationIndices_Superprocess open MeasureTheory ProbabilityTheory BanditAlgorithm
namespace AllocationIndices
theorem index_unique_up_to_increasing (μ : IndexFunction) {a : ℝ} (ha0 : 0 < a) (ha1 : a < 1)
(hμ : IsIndexForStandardPairs μ a)
{T : Type} [MeasurableSpace T] [Countable T] [MeasurableSingletonClass T]
(P : Kernel T T) [IsMarkovKernel P] {r : T → ℝ} (hr : BoundedReward r) (x : T)
{T' : Type} [MeasurableSpace T'] [Countable T'] [MeasurableSingletonClass T']
(P' : Kernel T' T') [IsMarkovKernel P'] {r' : T' → ℝ} (hr' : BoundedReward r') (x' : T')
(hlt : gittinsIndex P r a x < gittinsIndex P' r' a x') :
μ T P r x < μ T' P' r' x' := by sorry
end AllocationIndices
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.