Theorem 7, p.13 — finite-reply separation for the envelope family
OpenDeepQOperator.Supplement.theorem_7Consider the envelope family (13)–(14) with and , in the scalar-reply model of Appendix A. Each field is one affine scalar quantized to a symbol of bits, and the hard reply budget bounds the total bits on every input and random path.
- For integers , every fixed affine protocol with hard budget satisfies
- Every adaptive raw protocol with hard reply budget satisfies
- For let
There is an adaptive raw scheme with at most three replies and reply bits, and a fixed raw scheme with reply bits. Each has worst expected regret at most . 4. Consequently, for every fixed ,
where and are the least budgets of fixed affine, resp. adaptive raw, protocols with worst expected regret at most . The constants depend only on the tolerance ratio.
The theorem converts the exact-query separation into a reply-bit separation: linear in for fixed protocols, logarithmic for adaptive ones.
Differences from the source:
- encoding: worst-input expected regret → an -valued supremum of lower Lebesgue integrals of the loss; reason: Lean convention; the loss is nonnegative and bounded, so the values agree
- encoding: at most queries (reply bits) on every input and random path → the algorithm is run with fuel (protocols: hard budget
HardBudgetOnand fuel ); reason: a run with fuel asks at most queries, and an algorithm with hard budget behaves identically under fuel - encoding: randomized algorithm with private seed; deterministic algorithm → seed space a standard Borel probability space ; deterministic = seed space
Unitwith the Dirac measure; reason: the standing randomization model (20), §5, p.8 - encoding: the minimax value is at least → every algorithm of the class (measurable, on every standard Borel probability seed space) has worst regret at least ; reason: an infimum is at least exactly when every member is
- encoding: a reply of bits; zero-bit replies → the published
ReplyProtocol: every asked field has length and symbol below ; reason: a zero-bit reply is constant and can be removed (App. A, p.13) - encoding: of an integer →
Nat.clog 2 x; reason: equal for integers - reading: , → for each there are such that for all , : a fixed (raw) protocol with budget and regret exists and every fixed protocol with regret has budget ; an adaptive raw protocol with budget exists and every adaptive raw protocol with regret has budget ; reason: a least budget is described by an attaining protocol and a lower bound on all protocols; constants depend only on the tolerance ratio, as the theorem says
import Mathlib import Definitions.Def_DeepQOperator_Family import Definitions.Def_DeepQOperator_ReplyProtocol import Definitions.Def_DeepQOperator_Supplement_AdaptiveAlg import Definitions.Def_DeepQOperator_Supplement_Envelope open MeasureTheory
namespace DeepQOperator.Supplement
/-- **Theorem 7 (Finite-reply separation)** (Q. Qi, *Deep Q-Operator: Fixed-Accuracy Adaptive
Information and Shared Bellman Decisions*, STOC 2027 submission (manuscript sha256 9f8f3285…),
Theorem 7, p.13, PDF p.16; proved in Appendix C, pp.17–19).
For the envelope family (13), `m ≥ 2`, `0 < γ < 1`, in the scalar-reply model of Appendix A:
* for integers `0 ≤ B ≤ m`, every fixed affine protocol with hard budget `B` has worst expected
regret at least `γ(m+1-B)/(32π²(√m+1)²)` (27);
* every adaptive raw protocol with hard reply budget `B ≥ 0` has worst expected regret at least
`(γ/4)[1 - (2^B - 1)/m]₊` (28);
* for `0 < τ ≤ 1/4`, with `b_s(τ) = ⌈log₂(1 + ⌈(m+1)/τ⌉)⌉` and `b_z(τ) = ⌈log₂(1 + ⌈1/(2τ)⌉)⌉` (29), an
adaptive raw scheme with at most three replies and `b_s + 2b_z` reply bits and a fixed raw scheme
with `b_s + m b_z` reply bits each have worst expected regret at most `γτ`;
* for every fixed `0 < ε/γ ≤ 1/4096`, `C_fix(ε) = Θ(m)` and `C_ad(ε) = Θ(log(m+1))` (30), where `C_fix`
is the least hard budget of a fixed affine protocol and `C_ad` that of an adaptive raw protocol with
worst expected regret at most `ε`.
**Formalization Note.** Protocols are the published `ReplyProtocol` (lengths `≥ 1`, symbols below
`2^len`, quantizers measurable functions of the field's scalar, the seed and earlier symbols) on a
standard Borel probability seed space; "fixed" is `IsFixed`, "raw" is `IsRawProtocol (envDictionary m)`,
the budget `HardBudgetOn (envBox m) B` holds on every input and seed. `⌈log₂ x⌉` for an integer
`x ≥ 1` is `Nat.clog 2 x`. `Θ` is read with constants `c, C > 0` depending only on `κ = ε/γ`, chosen
before `m` and `γ`; the least-budget statements are stated as an attaining protocol plus a lower bound
on every protocol (no `sInf` on `ℕ`). The logarithm is natural. -/
theorem theorem_7 :
(∀ m : ℕ, 2 ≤ m → ∀ γ : ℝ, 0 < γ → γ < 1 →
(∀ B : ℕ, B ≤ m → ∀ (Ω : Type) [MeasurableSpace Ω] [StandardBorelSpace Ω] (μ : Measure Ω)
[IsProbabilityMeasure μ] (P : ReplyProtocol (EnvCoord m) Ω),
P.IsMeasurable → P.IsFixed → P.HardBudgetOn (envBox m) B →
ENNReal.ofReal (γ * ((m : ℝ) + 1 - B) / (32 * Real.pi ^ 2 * (Real.sqrt m + 1) ^ 2)) ≤
replyRegret (envBox m) (envLoss m γ 0) μ P B) ∧
(∀ (B : ℕ) (Ω : Type) [MeasurableSpace Ω] [StandardBorelSpace Ω] (μ : Measure Ω)
[IsProbabilityMeasure μ] (P : ReplyProtocol (EnvCoord m) Ω),
P.IsMeasurable → IsRawProtocol (envDictionary m) P → P.HardBudgetOn (envBox m) B →
ENNReal.ofReal (γ / 4 * max 0 (1 - ((2 : ℝ) ^ B - 1) / m)) ≤
replyRegret (envBox m) (envLoss m γ 0) μ P B) ∧
(∀ τ : ℝ, 0 < τ → τ ≤ 1 / 4 →
(∃ (Ω : Type) (_ : MeasurableSpace Ω) (_ : StandardBorelSpace Ω) (μ : Measure Ω)
(_ : IsProbabilityMeasure μ) (P : ReplyProtocol (EnvCoord m) Ω),
P.IsMeasurable ∧ IsRawProtocol (envDictionary m) P ∧ AtMostFields P (envBox m) 3 ∧
P.HardBudgetOn (envBox m)
(Nat.clog 2 (1 + ⌈((m : ℝ) + 1) / τ⌉₊) + 2 * Nat.clog 2 (1 + ⌈1 / (2 * τ)⌉₊)) ∧
replyRegret (envBox m) (envLoss m γ 0) μ P
(Nat.clog 2 (1 + ⌈((m : ℝ) + 1) / τ⌉₊) + 2 * Nat.clog 2 (1 + ⌈1 / (2 * τ)⌉₊)) ≤
ENNReal.ofReal (γ * τ)) ∧
(∃ (Ω : Type) (_ : MeasurableSpace Ω) (_ : StandardBorelSpace Ω) (μ : Measure Ω)
(_ : IsProbabilityMeasure μ) (P : ReplyProtocol (EnvCoord m) Ω),
P.IsMeasurable ∧ IsRawProtocol (envDictionary m) P ∧ P.IsFixed ∧
P.HardBudgetOn (envBox m)
(Nat.clog 2 (1 + ⌈((m : ℝ) + 1) / τ⌉₊) + m * Nat.clog 2 (1 + ⌈1 / (2 * τ)⌉₊)) ∧
replyRegret (envBox m) (envLoss m γ 0) μ P
(Nat.clog 2 (1 + ⌈((m : ℝ) + 1) / τ⌉₊) + m * Nat.clog 2 (1 + ⌈1 / (2 * τ)⌉₊)) ≤
ENNReal.ofReal (γ * τ)))) ∧
(∀ κ : ℝ, 0 < κ → κ ≤ 1 / 4096 →
∃ c C : ℝ, 0 < c ∧ 0 < C ∧ ∀ m : ℕ, 2 ≤ m → ∀ γ : ℝ, 0 < γ → γ < 1 →
(∃ (Ω : Type) (_ : MeasurableSpace Ω) (_ : StandardBorelSpace Ω) (μ : Measure Ω)
(_ : IsProbabilityMeasure μ) (P : ReplyProtocol (EnvCoord m) Ω) (B : ℕ),
P.IsMeasurable ∧ IsRawProtocol (envDictionary m) P ∧ P.IsFixed ∧
P.HardBudgetOn (envBox m) B ∧ (B : ℝ) ≤ C * m ∧
replyRegret (envBox m) (envLoss m γ 0) μ P B ≤ ENNReal.ofReal (κ * γ)) ∧
(∀ (B : ℕ) (Ω : Type) [MeasurableSpace Ω] [StandardBorelSpace Ω] (μ : Measure Ω)
[IsProbabilityMeasure μ] (P : ReplyProtocol (EnvCoord m) Ω),
P.IsMeasurable → P.IsFixed → P.HardBudgetOn (envBox m) B →
replyRegret (envBox m) (envLoss m γ 0) μ P B ≤ ENNReal.ofReal (κ * γ) → c * m ≤ B) ∧
(∃ (Ω : Type) (_ : MeasurableSpace Ω) (_ : StandardBorelSpace Ω) (μ : Measure Ω)
(_ : IsProbabilityMeasure μ) (P : ReplyProtocol (EnvCoord m) Ω) (B : ℕ),
P.IsMeasurable ∧ IsRawProtocol (envDictionary m) P ∧
P.HardBudgetOn (envBox m) B ∧ (B : ℝ) ≤ C * Real.log (m + 1) ∧
replyRegret (envBox m) (envLoss m γ 0) μ P B ≤ ENNReal.ofReal (κ * γ)) ∧
(∀ (B : ℕ) (Ω : Type) [MeasurableSpace Ω] [StandardBorelSpace Ω] (μ : Measure Ω)
[IsProbabilityMeasure μ] (P : ReplyProtocol (EnvCoord m) Ω),
P.IsMeasurable → IsRawProtocol (envDictionary m) P → P.HardBudgetOn (envBox m) B →
replyRegret (envBox m) (envLoss m γ 0) μ P B ≤ ENNReal.ofReal (κ * γ) →
c * Real.log (m + 1) ≤ B)) := by sorry
end DeepQOperator.Supplement