Two-environment partial-monitoring regret tradeoff from KL
ProvedBanditAlgorithm.pmStochPseudoRegret_pair_tradeoff_of_klFix a partial-monitoring policy and two stochastic environments . Suppose actions and are respectively optimal in the two environments. Let be a neighbourhood of actions. Assume every action outside has expected loss gap at least in both environments, while for every the two gaps sum to . Let and be the induced history laws. If their KL divergence is finite and satisfies
where counts actions outside , then there is an such that
This is the fixed-policy testing tradeoff in Step 3 of the hard partial-monitoring lower bound. It isolates the regret comparison and Bretagnolle–Huber argument from the preceding geometric construction and adaptive KL calculation.
Formalization Note The two regrets on the right are stochastic pseudo-regrets relative to the designated optimal actions.
import Definitions.Def_PartialMonitoringStochastic import Theorems.Thm_BanditAlgorithm_bretagnolle_huber_inequality_finite_typeStar import Mathlib.MeasureTheory.Integral.Bochner.Set open MeasureTheory ProbabilityTheory InformationTheory open scoped BigOperators ENNReal
theorem BanditAlgorithm.pmStochPseudoRegret_pair_tradeoff_of_kl
{k d n : ℕ} {𝕊 : Type*} [Fintype 𝕊] [MeasurableSpace 𝕊]
(G : PartialMonitoringGame k d 𝕊) (π : PMPolicy k 𝕊)
(ua ub : Fin d → ℝ) (hua : ua ∈ stdSimplex ℝ (Fin d))
(hub : ub ∈ stdSimplex ℝ (Fin d)) (a b : Fin k)
(N : Finset (Fin k)) (ε C Δ : ℝ)
(hΔ : 0 < Δ) (hΔε : Δ ≤ ε)
(haopt : ∀ c : Fin k,
0 ≤ pmExpectedLoss G ua c - pmExpectedLoss G ua a)
(hbopt : ∀ c : Fin k,
0 ≤ pmExpectedLoss G ub c - pmExpectedLoss G ub b)
(houta : ∀ c : Fin k, c ∉ N →
ε / 2 ≤ pmExpectedLoss G ua c - pmExpectedLoss G ua a)
(houtb : ∀ c : Fin k, c ∉ N →
ε / 2 ≤ pmExpectedLoss G ub c - pmExpectedLoss G ub b)
(hinside : ∀ c : Fin k, c ∈ N →
(pmExpectedLoss G ua c - pmExpectedLoss G ua a) +
(pmExpectedLoss G ub c - pmExpectedLoss G ub b) = Δ)
(hKLfin : klDiv (pmStochMeasure G π ua hua n)
(pmStochMeasure G π ub hub n) ≠ ⊤)
(hKL : (klDiv (pmStochMeasure G π ua hua n)
(pmStochMeasure G π ub hub n)).toReal ≤
C * Δ ^ 2 *
∫ h, ∑ t : Fin n,
(if (h t).1 ∉ N then (1 : ℝ) else 0)
∂pmStochMeasure G π ua hua n) :
∃ x : ℝ, 0 ≤ x ∧
ε / 2 * x + (n : ℝ) * Δ / 8 *
Real.exp (-C * Δ ^ 2 * x) ≤
pmStochPseudoRegret G π ua hua n a +
pmStochPseudoRegret G π ub hub n b := by
sorry