Theorem 3, p.5 — bounded convex-box affine separation on
OpenDeepQOperator.Supplement.theorem_3adaptivitybellman-operatorinformation-based-complexityp2o-gran-per-chapterp2o-plan-paperp2o-v1query-complexity
Consider the three-row Bellman family (6) on the convex box , with , , and .
- All input coordinates and raw values lie in , every raw coefficient vector has norm at most one, and the three rows list raw sites (the constant is listed once in row A and once in row B).
- Every randomized fixed design of arbitrary affine measurements has
- For every put and . There is an at-most-two-stage randomized adaptive affine algorithm, with exact real replies, whose worst-input expected regret is at most and whose hard query budget is
Each of its queried affine maps has coefficient norm at most one and values in on . 4. For every fixed , the fixed affine complexity is and the adaptive upper bound is .
The theorem contrasts fixed and adaptive exact affine information on a bounded convex parameter box.
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: a fixed design of at most affine measurements → an
ExactDesignwith exactly rows, zero rows allowed; reason: a zero row is a known constant, so padding to rows changes nothing - 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
- reading: fixed affine complexity is , the adaptive upper bound is → for each there are (depending only on ) such that for all and : some fixed design with at most rows has regret , every fixed design with regret has at least rows, and some adaptive algorithm with budget at most has regret ; reason: the base mission's reading of its Θ clause (paper.md decision 8)
- encoding: there are raw sites → a listing of the raw dictionary by indices in which only the constant site may repeat; reason: the constant is a site of row A and of row B; as a set the dictionary has elements
Preamble
import Mathlib import Definitions.Def_DeepQOperator_Family import Definitions.Def_DeepQOperator_ExactDesign import Definitions.Def_DeepQOperator_Supplement_AdaptiveAlg open MeasureTheory
Formal statement
namespace DeepQOperator.Supplement
/-- **Theorem 3 (Bounded convex-box affine separation)** (Q. Qi, *Deep Q-Operator: Fixed-Accuracy
Adaptive Information and Shared Bellman Decisions*, STOC 2027 submission (manuscript sha256
9f8f3285…), Theorem 3, p.5, PDF p.8; proved in Appendix D, pp.20–22).
For the family (6) on `P_cb = [-1,1]^n × [0,1]^m`, `m ≥ 2`, `0 < γ < 1`:
* all input coordinates and raw values lie in `[-1, 1]`, every raw coefficient vector has `ℓ₁`
norm at most one, and the three rows list `3m + n + 2` raw sites (the constant `1/4` listed in
row A and again in row B);
* every randomized fixed design of `N` arbitrary-affine measurements has worst expected regret at
least `γ(m - N)₊/(256π²m)` (10);
* for every `ε > 0`, with `δ = min{1/2, 32ε/γ}` and `R = 2⌈log₂(m/δ)⌉ + 1` (11), an at-most-two-stage
randomized adaptive exact affine algorithm has worst-input expected regret at most `ε` and hard
query budget `min{2m, 512R + 2min(m, 64)}` (12), every queried map having coefficient `ℓ₁` norm at
most one and values in `[-1, 1]` on `P_cb`;
* for every fixed `0 < ε/γ ≤ 1/(512π²)` the fixed affine complexity is `Θ(m)` and the adaptive upper
bound is `O(log m)`.
**Formalization Note.** Fixed designs are `ExactDesign` (exactly `N` rows, zero rows allowed);
adaptive algorithms are `AdaptiveAlg` with exact replies (`IsExact`), run with fuel equal to the hard
budget. Seeds live on a standard Borel probability space; lower bounds quantify over all of them,
upper bounds choose one. `Θ`/`O` use constants `c, C > 0` depending only on `κ = ε/γ`, chosen before
`m` and `γ`; the logarithm is natural (another base changes only `C`). The "three rows" fact holds by
construction of the family. -/
theorem theorem_3 :
(∀ m : ℕ, 2 ≤ m → ∀ γ : ℝ, 0 < γ → γ < 1 →
(∀ θ ∈ Pcb m, ∀ c, θ c ∈ Set.Icc (-1 : ℝ) 1) ∧
(∀ q ∈ rawDictionary m, ∑ c, |q.1 c| ≤ 1 ∧ ∀ θ ∈ Pcb m, affEval q θ ∈ Set.Icc (-1 : ℝ) 1) ∧
(∃ L : Fin (3 * m + nn m + 2) → AffQuery (Coord m), Set.range L = rawDictionary m ∧
∀ i j, L i = L j → i = j ∨ L i = constSite m) ∧
(∀ (N : ℕ) (Ω : Type) [MeasurableSpace Ω] [StandardBorelSpace Ω] (μ : Measure Ω)
[IsProbabilityMeasure μ] (D : ExactDesign (Coord m) Ω N), D.IsMeasurable →
ENNReal.ofReal (γ * max 0 ((m : ℝ) - N) / (256 * Real.pi ^ 2 * m)) ≤
designRegret (Pcb m) (loss m γ) μ D) ∧
(∀ ε : ℝ, 0 < ε →
∃ (Ω : Type) (_ : MeasurableSpace Ω) (_ : StandardBorelSpace Ω) (μ : Measure Ω)
(_ : IsProbabilityMeasure μ) (A : AdaptiveAlg (Coord m) Ω),
A.IsExact ∧ A.IsMeasurable ∧ A.IsAtMostTwoStage ∧
(∀ ω h, A.ask ω h = true →
∑ c, |(A.query ω h).1 c| ≤ 1 ∧
∀ θ ∈ Pcb m, affEval (A.query ω h) θ ∈ Set.Icc (-1 : ℝ) 1) ∧
algRegret (Pcb m) (loss m γ) μ A
(min (2 * m)
(512 * (2 * ⌈Real.logb 2 ((m : ℝ) / min (1 / 2) (32 * ε / γ))⌉₊ + 1) +
2 * min m 64)) ≤ ENNReal.ofReal ε)) ∧
(∀ κ : ℝ, 0 < κ → κ ≤ 1 / (512 * Real.pi ^ 2) →
∃ c C : ℝ, 0 < c ∧ 0 < C ∧ ∀ m : ℕ, 2 ≤ m → ∀ γ : ℝ, 0 < γ → γ < 1 →
(∃ (N : ℕ) (Ω : Type) (_ : MeasurableSpace Ω) (_ : StandardBorelSpace Ω) (μ : Measure Ω)
(_ : IsProbabilityMeasure μ) (D : ExactDesign (Coord m) Ω N),
D.IsMeasurable ∧ (N : ℝ) ≤ C * m ∧
designRegret (Pcb m) (loss m γ) μ D ≤ ENNReal.ofReal (κ * γ)) ∧
(∀ (N : ℕ) (Ω : Type) [MeasurableSpace Ω] [StandardBorelSpace Ω] (μ : Measure Ω)
[IsProbabilityMeasure μ] (D : ExactDesign (Coord m) Ω N), D.IsMeasurable →
designRegret (Pcb m) (loss m γ) μ D ≤ ENNReal.ofReal (κ * γ) → c * m ≤ N) ∧
(∃ (N : ℕ) (Ω : Type) (_ : MeasurableSpace Ω) (_ : StandardBorelSpace Ω) (μ : Measure Ω)
(_ : IsProbabilityMeasure μ) (A : AdaptiveAlg (Coord m) Ω),
A.IsExact ∧ A.IsMeasurable ∧ (N : ℝ) ≤ C * Real.log m ∧
algRegret (Pcb m) (loss m γ) μ A N ≤ ENNReal.ofReal (κ * γ))) := by sorry
end DeepQOperator.Supplement
Source
Qi, Deep Q-Operator: Fixed-Accuracy Adaptive Information and Shared Bellman Decisions, STOC 2027 submission (manuscript sha256 9f8f3285…), Theorem 3 and eqs. (10)–(12), p.5 (PDF p.8); proof in Appendix D, pp.20–22