Loss vectors incident to an edge interpolate its endpoint losses
ProvedBanditAlgorithm.partial_monitoring_neighbour_loss_interpolationbanditsconvex-geometrypartial-monitoring
Let be neighbouring actions and let be incident to their edge, meaning . Then the loss vector of lies on the segment joining the endpoint loss vectors:
The endpoint cases include actions with the same loss vector as or ; the strict interior case is exactly Lemma 37.8(a). This identity yields Eq. (37.10) for the two perturbed environments.
Preamble
import Definitions.Def_PartialMonitoringGame
Formal statement
theorem BanditAlgorithm.partial_monitoring_neighbour_loss_interpolation
{k d : ℕ} {𝕊 : Type*} (G : PartialMonitoringGame k d 𝕊)
(a b : Fin k) (hab : NeighbouringActions G a b) :
∀ c : Fin k, c ∈ pmNeighbourhood G a b →
∃ α : ℝ, 0 ≤ α ∧ α ≤ 1 ∧
∀ i : Fin d, G.L c i = α * G.L a i + (1 - α) * G.L b i := by sorrySource
Lattimore and Szepesvári, Bandit Algorithms (Cambridge UP, 2020), Lemma 37.8(a), printed pp. 484–485; applied in Theorem 37.12, Step 3, Eq. (37.10), printed p. 491.