Theorem 5.7 — OSMD with a 0-potential: for semi-bandits
ProvedRegretBandits.Linear.osmd_zero_potentialConsider online combinatorial optimization with semi-bandit feedback. The arm set is a nonempty with for all , the convex hull meets , and the losses are fixed in advance. OSMD on plays random arms with .
- Let be a -potential and run OSMD with and non-negative, unbiased loss estimates (). Then for every and every
- Let , , the estimate (5.5), and
Then
- With , i.e. , this is .
The maximum of the left-hand side over is the pseudo-regret . The bound improves Theorem 5.6 by the factor . For it is the log-free bound for the adversarial multi-armed bandit.
Formalization Note Corrected misprint: the book prints , without the factor . The proof bounds by and the second term by per round (p. 81). The stated bound is attained by the above, which includes . is needed for to be a -potential. Non-negativity of the estimates is in the book's statement. Unbiasedness is the standing assumption of Section 5.4 behind (5.6). is the OMD requirement . is the same on every sample path. Iterates and arms are measurable; in part 1 the estimates and the right-hand side expectations are assumed integrable. is conditioning on .
import Mathlib import Definitions.Def_RegretBandits_Linear_ConvexBasics import Definitions.Def_RegretBandits_Linear_OMD import Definitions.Def_RegretBandits_Linear_Potential import Definitions.Def_RegretBandits_Linear_SemiBandit open MeasureTheory
namespace RegretBandits.Linear
/-- Theorem 5.7 (OSMD with a 0-potential; Bubeck, Cesa-Bianchi, arXiv:1204.5721v2, p. 80).
Semi-bandit setting of p. 77: arms `C ⊆ {0,1}^d` with `‖v‖₁ = m`, `K = Conv(C)`, oblivious losses
`ℓ_t ∈ [0,1]^d`, played arms `v_t ∈ C` with `E[v_t | x_t] = x_t`.
1. For every `0`-potential `ψ`, OSMD on `K` with `F_ψ` and non-negative estimates `ℓ̃_t` with
`E[ℓ̃_t | x_t] = ℓ_t` satisfies, for every `x ∈ K`,
`E ∑ ℓ_tᵀv_t - ∑ ℓ_tᵀx ≤ (sup_K F_ψ - F_ψ(x_1))/η + (η/2) ∑_t ∑_i E[ℓ̃_t(i)² / (ψ⁻¹)'(x_t(i))]`.
2. For `q > 1`, `ψ(x) = (-x)^{-q}`, the estimate (5.5) and
`η = √((2/(q-1)) m^{1-2/q} / (n d^{1-2/q}))` (corrected: the book prints no `n`),
`E ∑ ℓ_tᵀv_t - ∑ ℓ_tᵀx ≤ q √((2/(q-1)) m d n)`.
3. With `q = 2` (`η = √(2/n)`): `E ∑ ℓ_tᵀv_t - ∑ ℓ_tᵀx ≤ 2 √(2mdn)`. -/
theorem osmd_zero_potential {d m : ℕ} {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω)
[IsProbabilityMeasure P] {C : Set (Fin d → ℝ)} (hC : IsCombinatorialSet C m)
(hKD : (convexHull ℝ C ∩ posOrthant d).Nonempty)
(ℓ : ℕ → Fin d → ℝ) (hℓ : ∀ t i, ℓ t i ∈ Set.Icc (0 : ℝ) 1) (n : ℕ) :
(∀ (ψ : ℝ → ℝ) (a : EReal), IsPotential 0 a ψ →
∀ (η : ℝ), 0 < η → ∀ (x v ℓt w : ℕ → Ω → Fin d → ℝ) (x₁ : Fin d → ℝ),
(∀ ω, IsOMDRun (potentialFn ψ a 0) (posOrthant d) (convexHull ℝ C) η
(fun t => ℓt t ω) (fun t => x t ω) (fun t => w t ω)) →
(∀ ω, x 1 ω = x₁) →
(∀ t, 1 ≤ t → Measurable (x t)) → (∀ t, 1 ≤ t → Measurable (v t)) →
(∀ t, 1 ≤ t → ∀ ω, v t ω ∈ C) →
(∀ t, 1 ≤ t → condExpGiven P (x t) (v t) =ᵐ[P] x t) →
(∀ t, 1 ≤ t → ∀ ω i, 0 ≤ ℓt t ω i) →
(∀ t, 1 ≤ t → ∀ i, Integrable (fun ω => ℓt t ω i) P) →
(∀ t, 1 ≤ t → condExpGiven P (x t) (ℓt t) =ᵐ[P] fun _ => ℓ t) →
(∀ t, 1 ≤ t → ∀ i,
Integrable (fun ω => ℓt t ω i ^ 2 / deriv (potInv ψ a) (x t ω i)) P) →
∀ y ∈ convexHull ℝ C,
∫ ω, ∑ t ∈ Finset.Icc 1 n, ℓ t ⬝ᵥ v t ω ∂P - ∑ t ∈ Finset.Icc 1 n, ℓ t ⬝ᵥ y ≤
(sSup (potentialFn ψ a 0 '' convexHull ℝ C) - potentialFn ψ a 0 x₁) / η +
η / 2 * ∑ t ∈ Finset.Icc 1 n, ∑ i,
∫ ω, ℓt t ω i ^ 2 / deriv (potInv ψ a) (x t ω i) ∂P) ∧
(∀ (q : ℝ), 1 < q → ∀ (x v w : ℕ → Ω → Fin d → ℝ),
(∀ ω, IsOMDRun (potentialFn (powPotential q) 0 0) (posOrthant d) (convexHull ℝ C)
(Real.sqrt (2 / (q - 1) * (m : ℝ) ^ (1 - 2 / q) / (n * (d : ℝ) ^ (1 - 2 / q))))
(fun t => semiBanditEstimate (ℓ t) (v t ω) (x t ω)) (fun t => x t ω)
(fun t => w t ω)) →
(∀ t, 1 ≤ t → Measurable (x t)) → (∀ t, 1 ≤ t → Measurable (v t)) →
(∀ t, 1 ≤ t → ∀ ω, v t ω ∈ C) →
(∀ t, 1 ≤ t → condExpGiven P (x t) (v t) =ᵐ[P] x t) →
∀ y ∈ convexHull ℝ C,
∫ ω, ∑ t ∈ Finset.Icc 1 n, ℓ t ⬝ᵥ v t ω ∂P - ∑ t ∈ Finset.Icc 1 n, ℓ t ⬝ᵥ y ≤
q * Real.sqrt (2 / (q - 1) * m * d * n)) ∧
(∀ (x v w : ℕ → Ω → Fin d → ℝ),
(∀ ω, IsOMDRun (potentialFn (powPotential 2) 0 0) (posOrthant d) (convexHull ℝ C)
(Real.sqrt (2 / n))
(fun t => semiBanditEstimate (ℓ t) (v t ω) (x t ω)) (fun t => x t ω)
(fun t => w t ω)) →
(∀ t, 1 ≤ t → Measurable (x t)) → (∀ t, 1 ≤ t → Measurable (v t)) →
(∀ t, 1 ≤ t → ∀ ω, v t ω ∈ C) →
(∀ t, 1 ≤ t → condExpGiven P (x t) (v t) =ᵐ[P] x t) →
∀ y ∈ convexHull ℝ C,
∫ ω, ∑ t ∈ Finset.Icc 1 n, ℓ t ⬝ᵥ v t ω ∂P - ∑ t ∈ Finset.Icc 1 n, ℓ t ⬝ᵥ y ≤
2 * Real.sqrt (2 * m * d * n)) := by sorry
end RegretBandits.Linear
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.