Lemma 1 (Lower bound by duality) and Remark 2 #
This file proves Lemma 1 of the paper and Remark 2, following their proofs in Section S1.3, and eq. (S14) of Section S2.2.
eIntegral_log_le_klDiv: the inequality of the Donsker–Varadhan variational formula, eq. (S3):∫ log H dμ ≤ KL(μ ‖ ν)for everyH ≥ 0with∫ H dν ≤ 1, by Jensen's inequality applied toH/fwithf = dμ/dν;stoppedPathValue E: the functionH(t, x^t) = E_t(x^t)on the pairs(t, x^t)of Section 3, withE_∞ = limsup_t E_t, and its measurability (measurable_stoppedPathValue);lintegral_stoppedAlternative,eIntegral_stoppedAlternative_log: integrals againstQ^ξ, so that∫ log H dQ^ξ = ∑_t ξ_t E_Q(log E_t)whenH(t, x^t) = E_t(x^t)fort ≤ T;lintegral_stoppedMixture_le_one: by Fubini's theorem, a function whose integral against everyP_λ ⊗ U[0, 1]is at most one has integral at most one against(π ⊗ κ) ⊗ U[0, 1], eq. (S4);Setting.sum_mul_ePower_le_klDiv:∑_t ξ_t E_Q(log E_t) ≤ KL(Q^ξ ‖ P̄)for every e-process and everyP̄ ∈ ℬ(Section 3, proved in Section S1.3);Setting.sum_mul_regret_eq:∑_t ξ_t R_t(E_t) = ∑_t ξ_t E_Q(log E*_t) − ∑_t ξ_t E_Q(log E_t)(Lemma S1, summed with the convention0 × ∞ = 0);Setting.sum_mul_regret_ge(eq. (5)) andSetting.sum_mul_ePower_sub_klDiv_le_minimaxRegret(Γ_T ≥ ∑_t ξ_t E_Q(log E*_t) − KL(Q^ξ ‖ P̄)for oneP̄ ∈ ℬ);sec3_epower_le_kl_proof,lem_duality_proof(Lemma 1),rem_deterministic_proof(Remark 2), andeq_S_epower_proof(eq. (S14)).
With the convention of eIntegral, the identity ∫ log H dQ^ξ = ∑_t ξ_t E_Q(log E_t) holds in
[−∞, ∞] for every H, and, as in the paper, no bound on the integral of log⁺ H is needed.
Remark 2 is proved, as in the paper, by the inequality (S3) applied once on the pairs (t, x^t), to
the function H(t, x^t) = E*_t(x^t) 1(t ≤ T): since the stopping times of P̄ do not depend on the
data, ∫ H dP̄ is an average of E_{P_λ}(E*_t) over data-independent times t, hence at most
one. The paper adopted both arguments after the formalization (its Section S5).
Arithmetic in [−∞, ∞] #
For c ≥ 0 and p, n ∈ [0, ∞], c(p − n) = (cp) − (cn) in [−∞, ∞], with the convention
0 × ∞ = 0.
The sum over the times of the weighted expectations of the positive and negative parts.
The inequality of the Donsker–Varadhan variational formula #
The inequality of the Donsker–Varadhan variational formula, eq. (S3) (Donsker and
Varadhan, 1983, eq. (2.1) and Theorem 2.1): for probability measures μ and ν and a measurable
H ≥ 0 with ∫ H dν ≤ 1, ∫ log H dμ ≤ KL(μ ‖ ν). With f = dμ/dν, Jensen's inequality gives
∫ log H dμ − KL(μ ‖ ν) = ∫ log(H/f) dμ ≤ log ∫ (H/f) dμ ≤ log ∫ H dν ≤ 0.
The function H(t, x^t) = E_t(x^t) on the pairs (t, x^t) #
The function H(t, x^t) = E_t(x^t) on the pairs (t, x^t) of Section 3 (proof of Lemma 1),
including t = ∞, where E_∞ = limsup_t E_t.
Equations
Instances For
For an adapted process (E_t), the function H(t, x^t) = E_t(x^t) is measurable for the
σ-algebra of the pairs (t, x^t).
Integrals against the stopped alternative Q^ξ #
The integral of a measurable g ≥ 0 against Q^ξ is ∑_t ξ_t E_Q{g(t, X^t)}.
For ξ ∈ Δ_T and a probability measure Q, Q^ξ is a probability measure.
∫ log H dQ^ξ = ∑_t ξ_t E_Q(log E_t) when H(t, x^t) = E_t(x^t) for t ≤ T (proof of
Lemma 1), with the convention 0 × ∞ = 0.
Mixtures of stopped null distributions #
Fubini's theorem for mixtures of stopped null distributions, eq. (S4): if the integral of
F((λ, ·), ·) against P_λ ⊗ U[0, 1] is at most one for every λ, then the integral of F
against (π ⊗ κ) ⊗ U[0, 1] is at most one.
The map ((λ, x), u) ↦ (τ_λ(x, u), x^{τ_λ(x, u)}) of a mixture in ℬ is measurable.
The e-power is at most the divergence (Section 3, proved in Section S1.3): for every
e-process (E_t), every ξ ∈ Δ_T, and every P̄ ∈ ℬ, ∑_t ξ_t E_Q(log E_t) ≤ KL(Q^ξ ‖ P̄).
With H(t, x^t) = E_t(x^t), Fubini's theorem and the second inequality in (1), randomized, give
∫ H dP̄ ≤ 1 (S4), and the inequality (S3) gives ∫ log H dQ^ξ ≤ KL(Q^ξ ‖ P̄).
Lemma 1 #
The weighted optimal e-power ∑_t ξ_t E_Q(log E*_t) is a real number.
Lemma S1, summed over the times with the weights ξ_t ≥ 0 and the convention 0 × ∞ = 0:
∑_t ξ_t R_t(E_t) = ∑_t ξ_t E_Q(log E*_t) − ∑_t ξ_t E_Q(log E_t) when E_t ∈ ℰ_t for t ≤ T.
Lemma 1, eq. (5): ∑_t ξ_t R_t(E_t) ≥ ∑_t ξ_t E_Q(log E*_t) − KL(Q^ξ ‖ P̄).
∑_t ξ_t R_t(E_t) ≤ max_{t ≤ T} R_t(E_t) for ξ ∈ Δ_T, since the regrets are nonnegative.
Lemma 1 for one mixture: Γ_T ≥ ∑_t ξ_t E_Q(log E*_t) − KL(Q^ξ ‖ P̄) for every ξ ∈ Δ_T
and every P̄ ∈ ℬ, from eq. (5) and max_{t≤T} R_t(E_t) ≥ ∑_t ξ_t R_t(E_t).