Importance-weighted vector estimators are unbiased for loss differences
ProvedBanditAlgorithm.pmVectorEstimator_importance_weighted_gapimportance-weightingonline-learningpartial-monitoring
Let be the finite comparator set used by Algorithm 26, let be a probability distribution supported on , let be a strictly positive sampling distribution, and let be a vector loss estimator on . For an outcome and comparator , importance weighting is unbiased for the -averaged loss difference:
Strict positivity of justifies cancellation of the importance weights. The common additive shift allowed in the vector-estimator definition cancels from every loss difference; coordinates outside contribute zero because is supported on .
Preamble
import Definitions.Def_PartialMonitoringAlgorithm26 open scoped BigOperators namespace BanditAlgorithm
Formal statement
theorem pmVectorEstimator_importance_weighted_gap
{k d : ℕ} {𝕊 : Type*}
(G : PartialMonitoringGame k d 𝕊) (S : Finset (Fin k))
(q p : Fin k → ℝ) (f : Fin k → 𝕊 → Fin k → ℝ)
(hq : PMSupportedOn S q) (hp : PMInteriorDistribution p)
(hf : PMVectorEstimatorOn G S f) (i : Fin d) (b : Fin k) (hb : b ∈ S) :
∑ a : Fin k, p a *
(∑ c : Fin k, q c *
(f a (G.Φ a i) c / p a - f a (G.Φ a i) b / p a)) =
∑ c : Fin k, q c * (G.L c i - G.L b i) := by sorrySource
Lattimore and Szepesvári, Bandit Algorithms (2020), §37.5 printed pp. 492–495, vector-estimator definition and proof of Theorem 37.15, https://tor-lattimore.com/downloads/book/book.pdf