One-step divergence increment on an event of the past
ProvedBanditAlgorithm.bandit_prefix_klDiv_one_step_on_eventOne round of interaction adds at most one round's worth of information, even after restricting to an event decided by the past.
Fix a -armed policy and run it in two bandit environments and , writing and for the two laws of the infinite interaction trajectory, and for the natural filtration. Let be any event decided by the first rounds. Then
where denotes restriction of the measure to .
Only the reward divergences appear on the right: the policy is the same in both environments, so the policy factors cancel from the likelihood ratio, and the single new observation in round contributes weighted by the probability that arm is the one played, on the part of the space selected by .
Localising to an -event is what makes this usable inside a stopping-time argument: taking isolates the rounds on which the learner has not yet stopped, and summing the resulting increments over produces the expected number of pulls in place of the horizon.
Formalization Note Trajectory coordinate is round , so the arm played in round is the first component of coordinate . The restriction of a probability measure to is a sub-probability measure, so the two divergences are those of finite measures.
import Definitions.Def_BanditTrajectory open MeasureTheory ProbabilityTheory InformationTheory ENNReal
theorem BanditAlgorithm.bandit_prefix_klDiv_one_step_on_event {k : ℕ}
(ν ν' : BanditAlgorithm.StochasticBandit k) (π : BanditAlgorithm.BanditPolicy k) (n : ℕ)
(E : Set (ℕ → Fin k × ℝ))
(hE : MeasurableSet[BanditAlgorithm.banditFiltration k n] E) :
@klDiv (ℕ → Fin k × ℝ) (BanditAlgorithm.banditFiltration k (n + 1))
(((BanditAlgorithm.banditTrajMeasure ν π).trim
((BanditAlgorithm.banditFiltration k).le (n + 1))).restrict E)
(((BanditAlgorithm.banditTrajMeasure ν' π).trim
((BanditAlgorithm.banditFiltration k).le (n + 1))).restrict E) ≤
@klDiv (ℕ → Fin k × ℝ) (BanditAlgorithm.banditFiltration k n)
(((BanditAlgorithm.banditTrajMeasure ν π).trim
((BanditAlgorithm.banditFiltration k).le n)).restrict E)
(((BanditAlgorithm.banditTrajMeasure ν' π).trim
((BanditAlgorithm.banditFiltration k).le n)).restrict E) +
∑ i, (BanditAlgorithm.banditTrajMeasure ν π) (E ∩ {ω | (ω n).1 = i}) *
klDiv (ν.P i) (ν'.P i) := by
sorry