Uniqueness of the optimal allocation for a Gaussian bandit
ProvedBanditAlgorithm.gaussian_optimal_allocation_uniqueLet be a -armed unit-variance Gaussian bandit whose best arm is strictly best, for every . Then the optimal allocation of Lattimore--Szepesv'ari Eq. (33.4) is unique: any two weight vectors attaining are equal.
This is what makes "the optimal allocation " a function of the environment rather than a choice, and it is what a tracking sampling rule needs: Track-and-Stop drives the empirical allocation towards , and a selection that jumps between equally optimal allocations cannot be tracked.
The proof runs through the closed form , which agrees with the variational definition on full-support allocations. Three steps:
-
Full support. The optimal value is positive (the uniform allocation already achieves a positive value) and a pair term vanishes as soon as one of its coordinates does, so every optimal allocation has all weights strictly positive.
-
Equalisation. At an optimum every pair term equals the value. If some arm's term were strictly larger, transferring a small mass from it to all other arms strictly increases every other term while decreasing its own by at most ; choosing below the excess divided by the squared gap raises the minimum, contradicting maximality.
-
Uniqueness. The midpoint of two optima is feasible and, by superadditivity of , each of its terms is at least the average of the corresponding two, hence at least the value; so the midpoint is optimal and equalises. That forces equality in superadditivity at every index, and the equality case gives for all . Two proportional probability vectors are equal.
Equalisation is necessary but not sufficient: for each value of there is an equalising allocation, and their values differ, so the optimum satisfies one further condition. Uniqueness therefore cannot be read off from the equalisation system alone.
import Definitions.Def_TrackAndStop import Definitions.Def_GaussianBandit import Theorems.Thm_BanditAlgorithm_pair_weight_superadditive import Theorems.Thm_BanditAlgorithm_pair_weight_add_eq_iff_proportional import Mathlib.Analysis.Convex.StdSimplex import Mathlib.Topology.Order.Lattice open MeasureTheory ProbabilityTheory InformationTheory NNReal ENNReal
theorem BanditAlgorithm.gaussian_optimal_allocation_unique {k : ℕ} [NeZero k]
{μvec : Fin k → ℝ} {istar : Fin k}
(hstar : ∀ j, j ≠ istar → μvec j < μvec istar) {α β : Fin k → NNReal}
(hα : BanditAlgorithm.IsOptimalAllocation (BanditAlgorithm.gaussianBandit μvec)
(Set.range (BanditAlgorithm.gaussianBandit (k := k))) α)
(hβ : BanditAlgorithm.IsOptimalAllocation (BanditAlgorithm.gaussianBandit μvec)
(Set.range (BanditAlgorithm.gaussianBandit (k := k))) β) : α = β := by
sorry