A neighbouring common cell contains a strictly positive distribution
ProvedBanditAlgorithm.partial_monitoring_neighbour_positive_common_pointbanditsconvex-geometrypartial-monitoring
Let be neighbouring actions in a finite partial-monitoring game. Their common cell contains an outcome distribution in the relative interior of the probability simplex: there is such that
This supplies the interior base environment used for the two alternatives . The strict coordinate inequalities ensure both perturbations remain probability distributions when is sufficiently small.
Preamble
import Definitions.Def_PartialMonitoringGame
Formal statement
theorem BanditAlgorithm.partial_monitoring_neighbour_positive_common_point
{k d : ℕ} {𝕊 : Type*} (G : PartialMonitoringGame k d 𝕊)
(a b : Fin k) (hab : NeighbouringActions G a b) :
∃ u ∈ pmCell G a ∩ pmCell G b, ∀ i : Fin d, 0 < u i := by sorrySource
Lattimore and Szepesvári, Bandit Algorithms (Cambridge UP, 2020), Theorem 37.12, Step 1, printed pp. 488–490. The proof chooses the centroid of C_a ∩ C_b and states on p. 490 that it is not on the boundary of the probability simplex, so every coordinate is positive.