The three-row envelope family (13)–(14) and its response mixing
DefinitionDeepQOperator_Supplement_Envelopeadaptivitybellman-operatorinformation-based-complexityp2o-gran-per-chapterp2o-plan-paperp2o-v1query-complexity
Fix . The parameter is , with two known anchor payloads . For let , and define the three critic rows
Decision has response and reward . Decision has and . The Bellman scores are , the contrast is , and the decision loss is .
The raw sites are the affine expressions inside each maximum: and for , and for (the listed sites).
Response mixing with weight replaces each response by and each reward by . The mixed scores are computed from (1) with these weights; is the unmixed family.
This family carries the paper's fixed-accuracy separation (Theorems 4, 5, 7, 11).
Formalization Note Coordinates are . Anchor indices run over , and is built in. Row C is a real supremum over indices, hence a maximum.
Definition code
import Mathlib
import Definitions.Def_DeepQOperator_Family
open Finset
namespace DeepQOperator.Supplement
/-!
# The three-row envelope family (13)–(14) and its response mixing
Q. Qi, *Deep Q-Operator: Fixed-Accuracy Adaptive Information and Shared Bellman Decisions*,
STOC 2027 submission (manuscript sha256 9f8f3285…), §4 eqs. (13)–(14) p.6 (PDF p.9),
"Strict positivity" p.7 (PDF p.10).
Fix `m ≥ 2`. The parameter is `θ = (s, z_1, …, z_m) ∈ [0, m+1] × [0,1]^m`, with the two known anchor
payloads `z_0 = z_{m+1} = 0`. For `0 ≤ j ≤ m+1` put `b_j(s) = 2js − j²`, and define the rows
`A(s,z) = max_{0≤j≤m+1} (z_j + b_j(s))`, `B(s) = max_{0≤j≤m+1} b_j(s)`, `C(z) = max_{1≤j≤m} z_j`.
The responses `w₊ = (1,0,0)`, `w₋ = (0,1,0)` and rewards `r₊ = −γ/2`, `r₋ = 0` give the contrast
`g_m = γ(A − B − 1/2)`. The expressions inside each maximum, including the individual `z_j` of row C,
are the raw oracle sites. Response mixing with `0 < λ < 1` replaces `w_a` by
`(1 − λ) w_a + λ(1,1,1)/3` and `r_a` by `(1 − λ) r_a`.
**Formalization Note.**
* The coordinates are `Unit ⊕ Fin m`: `Sum.inl ()` is the address `s`, `Sum.inr i` is the payload
`z_{i+1}`. Anchor indices `j ∈ {0, …, m+1}` are `Fin (m+2)`; `envZ m θ j` is `z_j`, equal to `0` at
`j = 0` and `j = m+1`.
* Row C is the real supremum over `Fin m`, which is the maximum for `m ≥ 1` (all theorems take
`m ≥ 2`).
* The scores are the Bellman scores (1) built with `bellmanScore` from the mixed responses and
rewards; `λ = 0` is the unmixed family. `envLoss m γ λ a θ` is the decision loss (3); `true` is the
action `+`.
* The raw dictionary is the set of the listed affine sites: `z_j + b_j(s)` and `b_j(s)` for
`0 ≤ j ≤ m+1` (at `j = 0` and `j = m+1` the first coincides with the second because the anchors are
zero), and `z_j` for `1 ≤ j ≤ m`.
-/
/-- Coordinates of the envelope family: the address `s` and the payloads `z_1, …, z_m`. -/
abbrev EnvCoord (m : ℕ) : Type := Unit ⊕ Fin m
/-- The parameter box `[0, m+1] × [0,1]^m`. -/
def envBox (m : ℕ) : Set (EnvCoord m → ℝ) :=
{θ | θ (Sum.inl ()) ∈ Set.Icc (0 : ℝ) (m + 1) ∧ ∀ i : Fin m, θ (Sum.inr i) ∈ Set.Icc (0 : ℝ) 1}
/-- The payload `z_j` for `0 ≤ j ≤ m+1`, with anchors `z_0 = z_{m+1} = 0`. -/
def envZ (m : ℕ) (θ : EnvCoord m → ℝ) (j : Fin (m + 2)) : ℝ :=
if h : 1 ≤ (j : ℕ) ∧ (j : ℕ) ≤ m then θ (Sum.inr ⟨(j : ℕ) - 1, by omega⟩) else 0
/-- `b_j(s) = 2js − j²` of (13). -/
def envB (j : ℕ) (s : ℝ) : ℝ := 2 * (j : ℝ) * s - (j : ℝ) ^ 2
/-- Row A: `max_{0≤j≤m+1} (z_j + b_j(s))`. -/
noncomputable def envRowA (m : ℕ) (θ : EnvCoord m → ℝ) : ℝ :=
Finset.univ.sup' ⟨0, Finset.mem_univ _⟩ (fun j : Fin (m + 2) => envZ m θ j + envB j (θ (Sum.inl ())))
/-- Row B: `max_{0≤j≤m+1} b_j(s)`. -/
noncomputable def envRowB (m : ℕ) (θ : EnvCoord m → ℝ) : ℝ :=
Finset.univ.sup' ⟨0, Finset.mem_univ _⟩ (fun j : Fin (m + 2) => envB j (θ (Sum.inl ())))
/-- Row C: `max_{1≤j≤m} z_j`. -/
noncomputable def envRowC (m : ℕ) (θ : EnvCoord m → ℝ) : ℝ := ⨆ i : Fin m, θ (Sum.inr i)
/-- The three row values `(A, B, C)`. -/
noncomputable def envRows (m : ℕ) (θ : EnvCoord m → ℝ) : Fin 3 → ℝ :=
![envRowA m θ, envRowB m θ, envRowC m θ]
/-- The mixed response `(1 − λ) w + λ(1,1,1)/3`. -/
noncomputable def mixResponse (lam : ℝ) (w : Fin 3 → ℝ) : Fin 3 → ℝ := fun i => (1 - lam) * w i + lam / 3
/-- The Bellman score (1) of action `a` in the envelope family mixed with weight `λ`
(`λ = 0`: unmixed): `+` has response `(1,0,0)` and reward `−γ/2`, `−` has `(0,1,0)` and `0`,
both mixed. -/
noncomputable def envScore (m : ℕ) (γ lam : ℝ) (a : Bool) (θ : EnvCoord m → ℝ) : ℝ :=
if a then bellmanScore γ ((1 - lam) * (-γ / 2)) (mixResponse lam ![1, 0, 0]) (envRows m θ)
else bellmanScore γ ((1 - lam) * 0) (mixResponse lam ![0, 1, 0]) (envRows m θ)
/-- The decision loss (3) of the (mixed) envelope family. -/
noncomputable def envLoss (m : ℕ) (γ lam : ℝ) (a : Bool) (θ : EnvCoord m → ℝ) : ℝ :=
max (envScore m γ lam true θ) (envScore m γ lam false θ) - envScore m γ lam a θ
/-- The raw site `z_j + b_j(s)` (`0 ≤ j ≤ m+1`). -/
noncomputable def envSiteA (m : ℕ) (j : Fin (m + 2)) : AffQuery (EnvCoord m) :=
(Sum.elim (fun _ => 2 * (j : ℝ)) (fun i => if (i : ℕ) + 1 = (j : ℕ) then 1 else 0), -((j : ℝ) ^ 2))
/-- The raw site `b_j(s)` (`0 ≤ j ≤ m+1`). -/
noncomputable def envSiteB (m : ℕ) (j : Fin (m + 2)) : AffQuery (EnvCoord m) :=
(Sum.elim (fun _ => 2 * (j : ℝ)) (fun _ => 0), -((j : ℝ) ^ 2))
/-- The raw site `z_{i+1}` of row C. -/
noncomputable def envSiteC (m : ℕ) (i : Fin m) : AffQuery (EnvCoord m) :=
(Sum.elim (fun _ => 0) (fun i' => if i' = i then 1 else 0), 0)
/-- The raw dictionary of the envelope family: the affine expressions inside the three maxima. -/
noncomputable def envDictionary (m : ℕ) : Set (AffQuery (EnvCoord m)) :=
Set.range (envSiteA m) ∪ Set.range (envSiteB m) ∪ Set.range (envSiteC m)
end DeepQOperator.Supplement
Source
Qi, Deep Q-Operator: Fixed-Accuracy Adaptive Information and Shared Bellman Decisions, STOC 2027 submission (manuscript sha256 9f8f3285…), §4 eqs. (13)–(14), p.6 (PDF p.9); 'Strict positivity', p.7 (PDF p.10)