Corollary 3.1 (Lattimore–György) — stochastic convex bandits with expected regret
ProvedBilateralProfitMHR.corollary_3_1This is the paper's corollary of Theorem 1 of Lattimore and György, Improved regret for zeroth-order stochastic convex bandits (COLT 2021).
Let be a known convex body (nonempty, compact, convex), and let be continuous and convex with values in a known interval . Querying returns , where, conditional on the previous queries and observations and on , the noise has mean zero and norm at most a known . Then there is a constant depending only on and such that for every there is an -query algorithm with
the expectation being over the noise and the algorithm's randomness. The algorithm may depend on , , , and , but not on or on the noise.
This is the routine ConOpt that the MHR algorithm runs on the loss .
Differences from the source:
- reading: "for every … " → there is with the bound for every ; reason: at the right side is and the claim is false: with , , , interval , the losses and give and , one of which is at least ; for the constant absorbs small (regret is at most )
- encoding: "of constant dimension … depends only on the affine dimension and the length of the specified interval" → and depends on and ; reason: for fixed the affine dimension takes finitely many values, so the largest of their constants serves
- reading: "conditional on previous queries and observations, and on , has mean zero and norm at most " → the observation law is a measurable kernel in the past queries, past observations and the current query, with mean and norm of the centered observation at most for every history with queries in ; the noise depends on the learner's seed only through the queries; reason: conditional laws on are kernels, a condition holding almost surely can be imposed everywhere by changing the kernel on a null set, and the learner's private randomness is independent of the environment in the bandit protocol
- encoding: "known" , interval and ; "convex body"; ; the expectation → the algorithm is chosen after and before and the noise; nonempty compact convex (lower-dimensional allowed); the infimum of on (attained); a -valued nested integral over the seed and the observations; reason: what "known" and "unknown" mean; the proof treats lower-dimensional bodies in their affine hull; the summands are nonnegative
import Mathlib import Definitions.Def_BilateralProfitMHR_ConvexBandit
namespace BilateralProfitMHR
open MeasureTheory
/-- **Corollary 3.1 (Stochastic convex bandit)**, Brüstle, di Gregorio, Fusco, Leonardi
(manuscript, sha256 e91e8127…), pp.10–11 (PDF 12–13), restated p.30 (PDF 32), proof App. A.5,
pp.58–59 (PDF 60–61); a corollary of Lattimore and György, *Improved regret for zeroth-order
stochastic convex bandits*, COLT 2021, PMLR 134:2938–2964, Theorem 1.
Let `𝒦` be a known convex body of constant dimension and `L : 𝒦 → ℝ` continuous and convex with
values in a known interval of constant length. Suppose querying `x_τ ∈ 𝒦` returns
`L(x_τ) + ξ_τ`, where, conditional on previous queries and observations and on `x_τ`, `ξ_τ` has
mean zero and `ψ₂` norm at most a known `γ ≥ 0`. Then for every `n` there is an `n`-query
algorithm with `E[∑_{τ=1}^n (L(x_τ) − min_{x∈𝒦} L(x))] ∈ O((1 + γ) √n log²(n))`, the hidden
constant depending only on the dimension and the length of the interval.
**Formalization Note.** The ambient space is `ℝ^d` (`EuclideanSpace ℝ (Fin d)`); the constant `C`
depends on `d` and on the interval length `ℓ` only. A convex body is a nonempty compact convex
set (lower-dimensional bodies allowed, as in the proof). The algorithm may depend on the known
data `𝒦`, `b`, `ℓ`, `γ`, `n`; the loss `L` and the environment `ν` (any measurable kernel
satisfying the noise condition, `NoiseCond`) are quantified after it. `O(·)` is read as `∃ C`
for every `n ≥ 2` (at `n = 1` the right side is `0` and the claim fails). `min_{𝒦} L` is
`sInf (L '' 𝒦)`, attained since `L` is continuous on the compact `𝒦`. The expectation over the
seed and the observations is `expectedCumLoss`, in `ℝ≥0∞`. Logarithms are natural. -/
theorem corollary_3_1 :
∀ (d : ℕ) (ℓ : ℝ), 0 < ℓ → ∃ C : ℝ, ∀ (K : Set (EuclideanSpace ℝ (Fin d))),
K.Nonempty → IsCompact K → Convex ℝ K → ∀ (b γ : ℝ), 0 ≤ γ → ∀ n : ℕ, 2 ≤ n →
∃ (Ω : Type) (_ : MeasurableSpace Ω) (P : Measure Ω), IsProbabilityMeasure P ∧
∃ A : QueryAlg (EuclideanSpace ℝ (Fin d)) Ω, A.IsOn K ∧
∀ L : EuclideanSpace ℝ (Fin d) → ℝ, ContinuousOn L K → ConvexOn ℝ K L →
(∀ x ∈ K, L x ∈ Set.Icc b (b + ℓ)) →
∀ ν : ObsKernel (EuclideanSpace ℝ (Fin d)), ν.IsMeasurable → NoiseCond K L γ ν →
expectedCumLoss A P ν (fun x => ENNReal.ofReal (L x - sInf (L '' K))) n ≤
ENNReal.ofReal (C * (1 + γ) * Real.sqrt n * Real.log n ^ 2) := by sorry
end BilateralProfitMHR
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.