Algorithm 26 policy bound for locally observable partial monitoring
DisprovedBanditAlgorithm.partial_monitoring_algorithm26_locally_observable_policy_boundbandit-theoryonline-learningpartial-monitoring
Let be a finite locally observable partial-monitoring game with actions and losses in . Then there is a constant such that, for every horizon , one can choose a partial-monitoring policy —the horizon-tuned exponential-weights policy of Algorithm 26—for which
This is the policy-level form of the locally observable upper bound. It combines Theorem 37.15,
with Theorem 37.17, which bounds for locally observable games, and tunes the learning rate as a function of the horizon. The policy is allowed to depend on , as is standard for the stated horizon-tuned bound.
Preamble
import Definitions.Def_PartialMonitoringGame import Mathlib.Analysis.SpecialFunctions.Pow.Real import Mathlib.Data.Real.Sqrt open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.partial_monitoring_algorithm26_locally_observable_policy_bound
{k d : ℕ} {𝕊 : Type*} [Fintype 𝕊] [MeasurableSpace 𝕊]
(G : PartialMonitoringGame k d 𝕊) (hk : 2 ≤ k)
(hL : ∀ a i, G.L a i ∈ Set.Icc (0 : ℝ) 1)
(hloc : LocallyObservable G) :
∃ C : ℝ, 0 < C ∧ ∀ n : ℕ, ∃ π : PMPolicy k 𝕊,
(⨆ i : Fin n → Fin d, pmRegret G π n i) ≤
C * max 1 (pmLocObsConst G) * (k : ℝ) ^ ((3 : ℝ) / 2) *
Real.sqrt (n * Real.log k) := by sorrySource
Lattimore and Szepesvári, Bandit Algorithms (2020), Algorithm 26 and Theorems 37.15 and 37.17, printed pp. 494–500; equations (37.11)–(37.17), https://tor-lattimore.com/downloads/book/book.pdf