Geometric alternatives for a hard partial-monitoring edge
ProvedBanditAlgorithm.partial_monitoring_hard_geometric_alternativesbanditspartial-monitoring
Let be globally observable but not locally observable. There exist neighbouring actions , a base distribution , a zero-sum normalized direction , and constants such that the alternatives have the cell, loss-gap, feedback-indistinguishability, and Eq. (37.10) properties for every .
This packages the geometric half of the hard partial-monitoring lower bound.
Preamble
import Definitions.Def_PartialMonitoringGame
Formal statement
theorem BanditAlgorithm.partial_monitoring_hard_geometric_alternatives
{k d : ℕ} {𝕊 : Type*} [Fintype 𝕊] [DecidableEq 𝕊]
(G : BanditAlgorithm.PartialMonitoringGame k d 𝕊)
(hglob : BanditAlgorithm.GloballyObservable G)
(hloc : ¬ BanditAlgorithm.LocallyObservable G) :
∃ a b : Fin k, ∃ u q : Fin d → ℝ, ∃ ε δ : ℝ,
BanditAlgorithm.NeighbouringActions G a b ∧ 0 < ε ∧ 0 < δ ∧
(∑ i, q i) = 0 ∧
(∑ i, (G.L a i - G.L b i) * q i) = 1 ∧
(∀ c : Fin k, c ∈ BanditAlgorithm.pmNeighbourhood G a b → ∀ σ : 𝕊,
∑ i ∈ Finset.univ.filter (fun i ↦ G.Φ c i = σ), q i = 0) ∧
∀ Δ : ℝ, 0 < Δ → Δ ≤ δ →
let ua := fun i ↦ u i - Δ * q i
let ub := fun i ↦ u i + Δ * q i
ua ∈ BanditAlgorithm.pmCell G a ∧ ub ∈ BanditAlgorithm.pmCell G b ∧
(∀ c : Fin k, c ∉ BanditAlgorithm.pmNeighbourhood G a b →
ε / 2 ≤ ∑ i, (G.L c i - G.L a i) * ua i ∧
ε / 2 ≤ ∑ i, (G.L c i - G.L b i) * ub i) ∧
(∀ c : Fin k, c ∈ BanditAlgorithm.pmNeighbourhood G a b →
(∑ i, (G.L c i - G.L a i) * ua i) +
(∑ i, (G.L c i - G.L b i) * ub i) = Δ) :=
by sorrySource
Lattimore and Szepesvári, Bandit Algorithms (Cambridge UP, 2020), Theorem 37.12, Steps 1 and 3, printed pp. 488–491, Eqs. (37.5)–(37.7) and (37.10); Lemma 37.8(a), printed pp. 484–485.