Corollary 3.1 — stochastic convex bandits: regret (cited from Lattimore–György)
ProvedBilateralProfitRegular.corollary_3_1This is the stochastic convex bandit bound the paper takes from Lattimore and György (Improved regret for zeroth-order stochastic convex bandits, COLT 2021, Theorem 1). Its algorithm is called ConOpt.
Fix an affine dimension and a length . There is a constant with the following property. Let:
- (any ) be nonempty, compact and convex, of affine dimension at most ;
- , , and .
Then there is an -query algorithm on such that the following holds for every continuous convex and every noisy oracle returning , where , conditional on the previous queries and observations and on , has mean zero and :
The expectation is over the noise and the algorithm's randomness. The algorithm may depend on but not on or on the noise law. In the paper this result is applied to the scaled loss , which gives eq. (55).
Formalization Note is the published sub-Gaussian norm, valued in , with value for a non-subgaussian variable. Logarithms are natural.
Differences from the source:
- reading: "for every … " → every , with one constant ; reason: at the right side is and the claim is false (, , , or : one of the two has expected regret ); is asymptotic in , and for the finitely many small are absorbed since the regret is at most
- reading: "a known convex body of constant dimension"; "the hidden constant depends only on the affine dimension and the length of the specified interval" → (any ambient ) nonempty, compact, convex, with (possibly lower-dimensional); depends only on and ; reason: the proof (p.58) treats affine dimension and works in the affine hull, so a convex body need not be full-dimensional; a bound instead of is equivalent (take the largest of the finitely many constants)
- encoding: noise conditional on previous queries and observations and on , with mean zero and norm at most → Markov kernels from (history, query) to the observation law, with mean and at every history and every ; expectation by nested integration; reason: kernel form of the conditional laws of the process
- encoding: "known" , interval and ; unknown → the algorithm is chosen after and before and the environment; reason: what the algorithm may depend on
import Mathlib import Definitions.Def_HighDimProb_Concentration_SubgaussianNorm_v2 import Definitions.Def_BilateralProfitRegular_ConvexBandit
namespace BilateralProfitRegular
open MeasureTheory
/-- **Corollary 3.1 (Stochastic convex bandit)**, Brüstle, di Gregorio, Fusco, Leonardi
(manuscript, sha256 e91e8127…), p.30 (PDF 32; also p.10 and p.58); a corollary of Theorem 1 of
T. Lattimore and A. György, *Improved regret for zeroth-order stochastic convex bandits*, COLT
2021, PMLR 134:2938–2964 (proof in App. A.5, pp.58–59).
Let `𝒦` be a known convex body of constant dimension and `L : 𝒦 → ℝ` continuous and convex with
values in a known interval `[b, b + ℓ]` of constant length. Querying `x_τ ∈ 𝒦` returns
`L(x_τ) + ξ_τ`, where, conditional on the 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))] ≤ C (1 + γ) √n log²(n)`, the constant
depending only on the affine dimension and the length `ℓ`.
**Formalization Note.** `𝒦 ⊆ ℝ^d` (`Fin d → ℝ`, any ambient `d`) nonempty, compact and
convex, of affine dimension at most `k` (`finrank (vectorSpan 𝒦) ≤ k`; possibly
lower-dimensional, as the proof allows); `C` depends only on `k` and `ℓ`, not on the ambient `d`
("the hidden constant depends only on the affine dimension and the length"). The algorithm may depend on
the known data `𝒦, b, γ, n` (and `ℓ`), and is chosen before the unknown `L` and environment. The
environment is any sequence of Markov kernels giving the observation law from the past and the
current query, with conditional mean `L(x)` and `‖Y − L(x)‖_{ψ₂} ≤ γ` (the published `ψ₂` norm,
`⊤` for a non-subgaussian variable). `n ≥ 2`: at `n = 1` the right side is `0` and the claim
fails. Natural logarithm. -/
theorem corollary_3_1 :
∀ (k : ℕ) (ℓ : ℝ), 0 < ℓ → ∃ C : ℝ, 0 < C ∧
∀ (d : ℕ) (K : Set (Fin d → ℝ)), K.Nonempty → IsCompact K → Convex ℝ K →
Module.finrank ℝ (vectorSpan ℝ K) ≤ k →
∀ (b : ℝ) (γ : NNReal) (n : ℕ), 2 ≤ n →
∃ (Ω : Type) (_ : MeasurableSpace Ω) (Pω : Measure Ω) (_ : IsProbabilityMeasure Pω)
(alg : BanditAlg (Fin d → ℝ) Ω),
alg.QueriesIn K ∧
∀ L : (Fin d → ℝ) → ℝ, ContinuousOn L K → ConvexOn ℝ K L →
(∀ x ∈ K, b ≤ L x ∧ L x ≤ b + ℓ) →
∀ ν : ObsEnv (Fin d → ℝ), ν.MeanOn L K →
(∀ τ h, ∀ x ∈ K,
HighDimProb.Concentration.subgaussianNorm (ν τ (h, x)) (fun y => y - L x) ≤ γ) →
alg.regret ν Pω n L K ≤
ENNReal.ofReal (C * (1 + γ) * Real.sqrt n * Real.log n ^ 2) := by sorry
end BilateralProfitRegular
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.