Adaptive candidate-hit event for the concrete policy
ProvedLG2021.Algorithm.candidateTerminalEvent_failure_leLet , , and . Let be compact and convex, with known pairwise diameter bound and a legal fallback anchor. Let the loss be globally convex and one-Lipschitz, and let the observation kernel be any measurable history-dependent kernel satisfying the stated centered subgaussian noise condition on legal queries. For any reference point , the concrete policy with its published candidate count, configuration, and seed law satisfies
after its first observations. The event includes the almost-sure candidate norm bounds and propagates candidate hits from each actual stage start. The proof uses fresh candidate-coordinate independence at adaptive stage starts and the published Gaussian surrogate separation theorem.
This is a formalization auxiliary for Algorithms 1–2 and their probability analysis in Tor Lattimore and András György, Improved Regret for Zeroth-Order Stochastic Convex Bandits, COLT 2021, PMLR 134, Lemma 4 and Sections 5–7. The implementation and event predicates are published definitions; the guarantee is proved in this theorem. Adaptive observation kernels and exact finite-history semantics are explicit formal interfaces. Statistical concentration and regret claims are not assumed by the implementation definitions.
import Mathlib import Definitions.Def_LG2021_Policy open LG2021 LG2021.Algorithm LG2021.Concentration BilateralProfitMHR MeasureTheory ProbabilityTheory Set Metric
theorem LG2021.Algorithm.candidateTerminalEvent_failure_le {d n N : ℕ} (hd : 0 < d) (hn : 2 ≤ n) (hN : N ≤ n)
{K : Set (Space d)} (hK : IsCompact K) (hcv : Convex ℝ K) {D : ℝ} (hD : 0 ≤ D)
(hdiam : ∀ x ∈ K, ∀ y ∈ K, dist x y ≤ D) (R : ℝ) (anchor : Space d) (ha : anchor ∈ K)
(L : Space d → ℝ) (hL : LipschitzWith 1 L) (hLc : ConvexOn ℝ univ L) (xstar : Space d)
(ν : ObsKernel (Space d)) (hνm : ν.IsMeasurable) (γ : ℝ) (hν : NoiseCond K L γ ν) :
(historyMeasure (policy (u := candidateCount n) (oracleConfig d D n) K hK.isClosed.measurableSet R anchor)
(seedMeasure d (candidateCount n) (oracleConfig d D n)) ν hνm (2*N)).real
(candidateTerminalEvent (oracleConfig d D n) K R L xstar)ᶜ ≤
((N : ℝ)+1)/(3*(n : ℝ)^2) := by sorry