Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Oblivious corrupted stochastic linear bandit environments, history law and regret (Section 1.1)

Definition
IAFTRL_LinEnv

by Canzhe Zhao · Nov 17, 2026 · Mathlib 0df444a (Lean v4.33.1)

bandit-algorithmslinear-banditsonline-learning

This file fixes the protocol objects of the corrupted stochastic regime used by the lower bounds of the source (Section 1.1, pp. 5–6).

Setting. A learner faces a known action set A⊆Rd\mathcal A\subseteq\mathbb R^dA⊆Rd. In round ttt the environment fixes a loss vector θt∈Rd\theta_t\in\mathbb R^dθt​∈Rd with ∥θt∥A=sup⁡a∈A∣a⊤θt∣≤1\|\theta_t\|_{\mathcal A}=\sup_{a\in\mathcal A}|a^\top\theta_t|\le1∥θt​∥A​=supa∈A​∣a⊤θt​∣≤1. The learner chooses At∈AA_t\in\mathcal AAt​∈A and observes a feedback YtY_tYt​ with ∣Yt∣≤1|Y_t|\le1∣Yt​∣≤1 and E[Yt∣Ft−1,θt,At]=At⊤θt\mathbb E[Y_t\mid\mathcal F_{t-1},\theta_t,A_t]=A_t^\top\theta_tE[Yt​∣Ft−1​,θt​,At​]=At⊤​θt​. The regret over TTT rounds is

RegT=sup⁡u∈AE[∑t=1T(At−u)⊤θt].\mathrm{Reg}_T=\sup_{u\in\mathcal A}\mathbb E\Big[\sum_{t=1}^T(A_t-u)^\top\theta_t\Big].RegT​=u∈Asup​E[t=1∑T​(At​−u)⊤θt​].

In the corrupted stochastic regime there is a fixed loss vector θ\thetaθ with ∥θ∥A≤1\|\theta\|_{\mathcal A}\le1∥θ∥A​≤1, and θt=θ+ct\theta_t=\theta+c_tθt​=θ+ct​ with total corruption ∑t≤T∥ct∥A≤C\sum_{t\le T}\|c_t\|_{\mathcal A}\le C∑t≤T​∥ct​∥A​≤C.

Objects.

  1. ∥z∥A\|z\|_{\mathcal A}∥z∥A​ (setNorm) is the supremum of ∣a⊤z∣|a^\top z|∣a⊤z∣ over a∈Aa\in\mathcal Aa∈A.
  2. An oblivious environment (LinEnv) consists of a loss vector θt\theta_tθt​ for each round and a feedback law νt(a)\nu_t(a)νt​(a) for each round and action. The corruption is therefore deterministic, and the feedback depends on the past only through the action played.
  3. IsCorruptedStoch E 𝒜 θ C T states that, over the horizon TTT, the environment is a corrupted stochastic environment for A\mathcal AA with fixed loss vector θ\thetaθ and budget CCC. That is, ∥θ∥A≤1\|\theta\|_{\mathcal A}\le1∥θ∥A​≤1, ∥θt∥A≤1\|\theta_t\|_{\mathcal A}\le1∥θt​∥A​≤1, every feedback law νt(a)\nu_t(a)νt​(a) with a∈Aa\in\mathcal Aa∈A is supported in [−1,1][-1,1][−1,1] with mean a⊤θta^\top\theta_ta⊤θt​, and ∑t<T∥θt−θ∥A≤C\sum_{t<T}\|\theta_t-\theta\|_{\mathcal A}\le C∑t<T​∥θt​−θ∥A​≤C.
  4. histMeasure E π n is the law PE,πn\mathbb P_{E,\pi}^nPE,πn​ of the history (A1,Y1),…,(An,Yn)(A_1,Y_1),\dots,(A_n,Y_n)(A1​,Y1​),…,(An​,Yn​) when a (possibly randomized) policy π\piπ, given by Markov kernels from histories to actions, interacts with the environment.
  5. regret E 𝒜 π T is RegT\mathrm{Reg}_TRegT​ computed under PE,πT\mathbb P_{E,\pi}^TPE,πT​.

These objects let lower bounds quantify over every policy while exhibiting concrete corrupted environments.

Formalization Note. Rounds are 0-based in Lean. Policies are the platform's BanditAlgorithm.LinearBanditPolicy d; that a policy plays only actions of A\mathcal AA is the separate hypothesis IsSupportedLinearPolicy 𝒜 π. The source allows adaptive environments. Lower bounds that exhibit oblivious environments are therefore at least as strong as the source's statements.

Definition code
import Mathlib
import Definitions.Def_LinearBanditProtocol

/-!
# Oblivious (corrupted) stochastic linear bandit environments

Zhao–Tan, *Best-of-Both-Worlds FTRL for Linear Bandits: The Interplay of Information Acquisition,
Corruption, and Geometry* (STOC submission version), Section 1.1 "Preliminaries", p.5–6.

In round `t` the environment fixes a loss vector `θ_t ∈ ℝ^d`; the learner chooses `A_t ∈ 𝒜` and
observes a feedback `Y_t` with `E[Y_t | F_{t-1}, θ_t, A_t] = A_tᵀθ_t` and `|Y_t| ≤ 1`, and
`‖θ_t‖_𝒜 = sup_{a∈𝒜} |aᵀθ_t| ≤ 1`. The (pseudo-)regret is
`Reg_T = sup_{u ∈ 𝒜} E[∑_{t=1}^T (A_t − u)ᵀθ_t]`. In the corrupted stochastic regime
`θ_t = θ + c_t` with a fixed `θ`, `‖θ‖_𝒜 ≤ 1`, and `∑_{t ≤ T} ‖c_t‖_𝒜 ≤ C`.

* `LinEnv d` is an *oblivious* environment: the loss vectors `θs t` and the feedback law
  `fb t a` of each round `t` (0-based) and action `a` are fixed in advance (deterministic
  corruption, feedback independent of the past given the action).
* `LinEnv.IsCorruptedStoch E 𝒜 θ C T` says that, over the horizon `T`, `E` is a corrupted
  stochastic environment for the action set `𝒜` with fixed loss vector `θ` and corruption
  budget `C`.
* `LinEnv.histMeasure E π n` is the law of the history `(A_1, Y_1), …, (A_n, Y_n)` when the
  policy `π` (a `BanditAlgorithm.LinearBanditPolicy`, i.e. Markov kernels from histories to
  actions, which may randomize) interacts with `E`.
* `LinEnv.regret E 𝒜 π T` is `Reg_T = sup_{u∈𝒜} E[∑_{t<T} (A_t − u)ᵀθ_t]`.
-/

open MeasureTheory ProbabilityTheory Matrix

namespace IAFTRL

/-- The action-set seminorm `‖z‖_𝒜 = sup_{a ∈ 𝒜} |aᵀz|` (Section 1.1). -/
noncomputable def setNorm {d : ℕ} (𝒜 : Set (Fin d → ℝ)) (z : Fin d → ℝ) : ℝ :=
  sSup ((fun a => |a ⬝ᵥ z|) '' 𝒜)

/-- An oblivious linear bandit environment: the actual loss vector `θs t` of round `t`
(0-based) and the feedback law `fb t a` of round `t` when action `a` is played. -/
structure LinEnv (d : ℕ) where
  /-- The actual loss vector `θ_{t+1}` of round `t`. -/
  θs : ℕ → Fin d → ℝ
  /-- The law of the feedback `Y_{t+1}` given the action played in round `t`. -/
  fb : ℕ → Kernel (Fin d → ℝ) ℝ
  /-- Each feedback law is a probability measure. -/
  markov : ∀ t, IsMarkovKernel (fb t)

attribute [instance] LinEnv.markov

/-- `E` is a corrupted stochastic environment over the horizon `T` for the action set `𝒜`, with
fixed loss vector `θ` and corruption budget `C` (Section 1.1): `‖θ‖_𝒜 ≤ 1`; for every round
`t < T`, `‖θ_t‖_𝒜 ≤ 1` and, for every action `a ∈ 𝒜`, the feedback lies in `[-1, 1]` and has mean
`aᵀθ_t`; and the total corruption is `∑_{t<T} ‖θ_t − θ‖_𝒜 ≤ C`. -/
def LinEnv.IsCorruptedStoch {d : ℕ} (E : LinEnv d) (𝒜 : Set (Fin d → ℝ)) (θ : Fin d → ℝ)
    (C : ℝ) (T : ℕ) : Prop :=
  setNorm 𝒜 θ ≤ 1 ∧
    (∀ t < T, setNorm 𝒜 (E.θs t) ≤ 1) ∧
    (∀ t < T, ∀ a ∈ 𝒜, E.fb t a (Set.Icc (-1 : ℝ) 1)ᶜ = 0 ∧ ∫ y, y ∂(E.fb t a) = a ⬝ᵥ E.θs t) ∧
    ∑ t ∈ Finset.range T, setNorm 𝒜 (E.θs t - θ) ≤ C

/-- Appending a round `(a, y)` to a linear bandit history is measurable. -/
lemma measurable_histSnoc {d n : ℕ} :
    Measurable (fun p : (BanditAlgorithm.LinearBanditHistory d n × (Fin d → ℝ)) × ℝ ↦
      Fin.snoc (α := fun _ ↦ (Fin d → ℝ) × ℝ) p.1.1 (p.1.2, p.2)) := by
  rw [measurable_pi_iff]
  intro t
  by_cases ht : (t : ℕ) < n
  · have : (fun p : (BanditAlgorithm.LinearBanditHistory d n × (Fin d → ℝ)) × ℝ ↦
        Fin.snoc (α := fun _ ↦ (Fin d → ℝ) × ℝ) p.1.1 (p.1.2, p.2) t) =
        fun p ↦ p.1.1 (Fin.castLT t ht) := by
      funext p
      simp [Fin.snoc, ht]
    rw [this]
    exact (measurable_pi_apply _).comp (measurable_fst.comp measurable_fst)
  · have : (fun p : (BanditAlgorithm.LinearBanditHistory d n × (Fin d → ℝ)) × ℝ ↦
        Fin.snoc (α := fun _ ↦ (Fin d → ℝ) × ℝ) p.1.1 (p.1.2, p.2) t) =
        fun p ↦ (p.1.2, p.2) := by
      funext p
      simp [Fin.snoc, ht]
    rw [this]
    exact (measurable_snd.comp measurable_fst).prodMk measurable_snd

/-- The law of the history after `n` rounds of the interaction of the policy `π` with the
oblivious environment `E`: round `n + 1` samples `A ~ π.select n (history)` and then
`Y ~ E.fb n A`, and appends `(A, Y)`. -/
noncomputable def LinEnv.histMeasure {d : ℕ} (E : LinEnv d)
    (π : BanditAlgorithm.LinearBanditPolicy d) :
    (n : ℕ) → Measure (BanditAlgorithm.LinearBanditHistory d n)
  | 0 => Measure.dirac (fun t ↦ t.elim0)
  | n + 1 =>
      (((E.histMeasure π n).compProd (π.select n)).compProd
          ((E.fb n).comap Prod.snd measurable_snd)).map
        (fun p ↦ Fin.snoc (α := fun _ ↦ (Fin d → ℝ) × ℝ) p.1.1 (p.1.2, p.2))

instance LinEnv.histMeasure.instIsProbabilityMeasure {d : ℕ} (E : LinEnv d)
    (π : BanditAlgorithm.LinearBanditPolicy d) (n : ℕ) :
    IsProbabilityMeasure (E.histMeasure π n) := by
  induction n with
  | zero => exact Measure.dirac.isProbabilityMeasure
  | succ n ih =>
      rw [LinEnv.histMeasure]
      haveI := ih
      exact Measure.isProbabilityMeasure_map measurable_histSnoc.aemeasurable

/-- The regret `Reg_T = sup_{u ∈ 𝒜} E[∑_{t=1}^T (A_t − u)ᵀθ_t]` of the policy `π` in the
environment `E` over the horizon `T` (Section 1.1; rounds are 0-based in Lean). -/
noncomputable def LinEnv.regret {d : ℕ} (E : LinEnv d) (𝒜 : Set (Fin d → ℝ))
    (π : BanditAlgorithm.LinearBanditPolicy d) (T : ℕ) : ℝ :=
  sSup ((fun u => ∫ h, ∑ t : Fin T, ((h t).1 - u) ⬝ᵥ E.θs t ∂(E.histMeasure π T)) '' 𝒜)

end IAFTRL
Source
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits: The Interplay of Information Acquisition, Corruption, and Geometry (STOC submission version; arXiv:2611.01299), Section 1.1 Preliminaries, pp. 5–6 (pseudo-regret, Regime of the Environment)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me