Signal laws coincide under a fiber-invisible symmetric perturbation
ProvedBanditAlgorithm.pmSignalMeasure_eq_symmetric_perturbation_of_fiber_sumbandit-theoryinformation-theorypartial-monitoring
Let a finite partial-monitoring game have signal map . Fix an action , a base outcome distribution , a perturbation direction , and a scale . Assume both symmetric perturbations and are probability distributions. If the perturbation is invisible in every signal fiber of action , meaning
then action induces exactly the same signal law under the two perturbed environments:
This is the finite signal-law identity used for actions in the neighborhood in the hard-game lower bound for partial monitoring. It isolates the precise consequence of the kernel/fiber condition in equation (37.6).
Preamble
import Definitions.Def_PartialMonitoringStochastic import Mathlib.Data.ENNReal.BigOperators open MeasureTheory ProbabilityTheory open scoped BigOperators ENNReal namespace BanditAlgorithm
Formal statement
theorem pmSignalMeasure_eq_symmetric_perturbation_of_fiber_sum
{k d : ℕ} {𝕊 : Type*} [Fintype 𝕊] [MeasurableSpace 𝕊]
[DecidableEq 𝕊]
(G : PartialMonitoringGame k d 𝕊) (c : Fin k)
(u q : Fin d → ℝ) (Δ : ℝ)
(hminus : (fun i => u i - Δ * q i) ∈ stdSimplex ℝ (Fin d))
(hplus : (fun i => u i + Δ * q i) ∈ stdSimplex ℝ (Fin d))
(hfiber : ∀ σ : 𝕊,
∑ i ∈ Finset.univ.filter (fun i => G.Φ c i = σ), q i = 0) :
pmSignalMeasure G (fun i => u i - Δ * q i) c =
pmSignalMeasure G (fun i => u i + Δ * q i) c := by sorrySource
Lattimore and Szepesvári, Bandit Algorithms (2020), Theorem 37.12, Step 2, printed p. 490; equation (37.6), https://tor-lattimore.com/downloads/book/book.pdf