Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 9, p.27 — bounded continuous addressing on the promise PcodeP_{\mathrm{code}}Pcode​

Open
DeepQOperator.Supplement.theorem_9

by iris · Nov 16, 2026 · Mathlib 0df444a (Lean v4.33.1)

adaptivitybellman-operatorinformation-based-complexityp2o-gran-per-chapterp2o-plan-paperp2o-v1query-complexity

For every m≥2m\ge2m≥2 and 0<γ<10<\gamma<10<γ<1, on the promise family (50)–(51) with r=⌈log⁡2m⌉r=\lceil\log_2m\rceilr=⌈log2​m⌉ and n=2rn=2^rn=2r: all input coordinates and raw critic values lie in [−1,1][-1,1][−1,1], every raw affine coefficient vector has ℓ1\ell_1ℓ1​ norm at most one, and there are three rows and 3m+n<5m3m+n<5m3m+n<5m raw sites. Moreover:

  1. A deterministic adaptive raw algorithm uses r+1r+1r+1 exact queries for zero regret. Each reply can be a single bit: a deterministic adaptive raw protocol with r+1r+1r+1 one-bit replies has zero regret on the whole promise.
  2. For every randomized fixed arbitrary-affine design and every fixed affine scalar-reply protocol,
CNfixed,aff,ran ≥ γ(m−N)+64π2m,CBfixed,aff,bit ≥ γ(m−B)+64π2m.(52)\mathfrak C^{\mathrm{fixed,aff,ran}}_N\ \ge\ \frac{\gamma(m-N)_+}{64\pi^2m},\qquad \mathfrak C^{\mathrm{fixed,aff,bit}}_B\ \ge\ \frac{\gamma(m-B)_+}{64\pi^2m}. \tag{52}CNfixed,aff,ran​ ≥ 64π2mγ(m−N)+​​,CBfixed,aff,bit​ ≥ 64π2mγ(m−B)+​​.(52)

A fixed raw design has zero regret with m+rm+rm+r one-bit replies. 3. For randomized adaptive arbitrary-affine scalar-reply protocols,

CBadaptive,aff,bit ≥ γ(m−(2B−1))+64π2m.(53)\mathfrak C^{\mathrm{adaptive,aff,bit}}_B\ \ge\ \frac{\gamma\big(m-(2^B-1)\big)_+}{64\pi^2m}. \tag{53}CBadaptive,aff,bit​ ≥ 64π2mγ(m−(2B−1))+​​.(53)

When m=2rm=2^rm=2r the exact adaptive reply-bit complexity is therefore r+1r+1r+1, even for the stronger arbitrary-affine oracle.

The promise family gives exact logarithmic reply-bit addressing with bounded features.

Differences from the source:

  • encoding: worst-input expected regret sup⁡θEωℓ(A(θ;ω),θ)\sup_\theta E_\omega \ell(A(\theta;\omega),\theta)supθ​Eω​ℓ(A(θ;ω),θ) → an R≥0∪{∞}\mathbb{R}_{\ge0}\cup\{\infty\}R≥0​∪{∞}-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 NNN queries (reply bits) on every input and random path → the algorithm is run with fuel NNN (protocols: hard budget HardBudgetOn and fuel BBB); reason: a run with fuel NNN asks at most NNN queries, and an algorithm with hard budget NNN behaves identically under fuel NNN
  • encoding: a fixed design of at most NNN affine measurements → an ExactDesign with exactly NNN rows, zero rows allowed; reason: a zero row is a known constant, so padding to NNN rows changes nothing
  • encoding: randomized algorithm with private seed; deterministic algorithm → seed space a standard Borel probability space (Ω,μ)(\Omega,\mu)(Ω,μ); deterministic = seed space Unit with the Dirac measure; reason: the standing randomization model (20), §5, p.8
  • encoding: the minimax value is at least xxx → every algorithm of the class (measurable, on every standard Borel probability seed space) has worst regret at least xxx; reason: an infimum is at least xxx exactly when every member is
  • reading: a fixed raw design has zero regret with m+rm+rm+r one-bit replies → a deterministic fixed raw protocol with m+rm+rm+r one-bit replies and zero worst regret; reason: the proof (App. G.1, p.28) queries all mmm payload threshold bits and rrr address sign bits in advance, deterministically
  • reading: when m=2rm=2^rm=2r the exact adaptive reply-bit complexity is r+1r+1r+1 → for m=2rm=2^rm=2r, every measurable adaptive affine protocol with hard budget rrr has positive worst regret; r+1r+1r+1 one-bit raw replies are exact by part 1; reason: exact complexity is two-sided
  • encoding: there are 3m+n3m+n3m+n raw sites → an injective listing of the raw dictionary by 3m+n3m+n3m+n indices; reason: the listed sites are pairwise distinct
Preamble
import Mathlib
import Definitions.Def_DeepQOperator_Family
import Definitions.Def_DeepQOperator_ExactDesign
import Definitions.Def_DeepQOperator_ReplyProtocol
import Definitions.Def_DeepQOperator_Supplement_AdaptiveAlg
import Definitions.Def_DeepQOperator_Supplement_Promise

open MeasureTheory
Formal statement
namespace DeepQOperator.Supplement

/-- **Theorem 9 (Bounded continuous addressing)** (Q. Qi, *Deep Q-Operator: Fixed-Accuracy Adaptive
Information and Shared Bellman Decisions*, STOC 2027 submission (manuscript sha256 9f8f3285…),
Theorem 9, p.27, PDF p.30; proved in Appendix G, pp.28–30).

For every `m ≥ 2` and `0 < γ < 1`, on the promise family (50)–(51) (`r = ⌈log₂ m⌉`, `n = 2^r`):
all input coordinates and raw values lie in `[-1, 1]`, every raw coefficient vector has `ℓ₁` norm at
most one, and the three rows have `3m + n < 5m` raw sites. Moreover:
1. a deterministic adaptive raw algorithm with `r + 1` exact queries has zero regret, and so does a
   deterministic adaptive raw scalar-reply protocol with `r + 1` one-bit replies;
2. every randomized fixed arbitrary-affine design has `ℭ^{fixed,aff,ran}_N ≥ γ(m - N)₊/(64π²m)` and
   every fixed affine scalar-reply protocol `ℭ^{fixed,aff,bit}_B ≥ γ(m - B)₊/(64π²m)` (52); a fixed raw
   design has zero regret with `m + r` one-bit replies;
3. every randomized adaptive affine scalar-reply protocol has
   `ℭ^{adaptive,aff,bit}_B ≥ γ(m - (2^B - 1))₊/(64π²m)` (53); when `m = 2^r` the exact adaptive reply-bit
   complexity is therefore `r + 1`, even for affine protocols.

**Formalization Note.** The domain is the nonconvex union `promiseBox m`. Deterministic algorithms and
protocols have seed space `Unit` (Dirac measure). Exact adaptive algorithms are `AdaptiveAlg` run with
fuel `r + 1`; scalar-reply protocols are the published `ReplyProtocol`, with `UsesOneBitReplies` for
single-bit fields. Lower bounds quantify over measurable protocols on any standard Borel probability
seed space. "`3m + n` raw sites" is a listing of the dictionary by `Fin (3m + n)` without repetition. -/
theorem theorem_9 :
    ∀ m : ℕ, 2 ≤ m → ∀ γ : ℝ, 0 < γ → γ < 1 →
      (∀ θ ∈ promiseBox m, ∀ c, θ c ∈ Set.Icc (-1 : ℝ) 1) ∧
      (∀ q ∈ promiseDictionary m,
        ∑ c, |q.1 c| ≤ 1 ∧ ∀ θ ∈ promiseBox m, affEval q θ ∈ Set.Icc (-1 : ℝ) 1) ∧
      (∃ L : Fin (3 * m + nn m) → AffQuery (Coord m),
        Function.Injective L ∧ Set.range L = promiseDictionary m) ∧
      3 * m + nn m < 5 * m ∧
      (∃ A : AdaptiveAlg (Coord m) Unit, A.IsExact ∧ A.IsRaw (promiseDictionary m) ∧
        A.IsMeasurable ∧ algRegret (promiseBox m) (pLoss m γ) (Measure.dirac ()) A (rr m + 1) = 0) ∧
      (∃ P : ReplyProtocol (Coord m) Unit, P.IsMeasurable ∧ IsRawProtocol (promiseDictionary m) P ∧
        UsesOneBitReplies P ∧ P.HardBudgetOn (promiseBox m) (rr m + 1) ∧
        replyRegret (promiseBox m) (pLoss m γ) (Measure.dirac ()) P (rr m + 1) = 0) ∧
      (∀ (N : ℕ) (Ω : Type) [MeasurableSpace Ω] [StandardBorelSpace Ω] (μ : Measure Ω)
          [IsProbabilityMeasure μ] (D : ExactDesign (Coord m) Ω N), D.IsMeasurable →
        ENNReal.ofReal (γ * max 0 ((m : ℝ) - N) / (64 * Real.pi ^ 2 * m)) ≤
          designRegret (promiseBox m) (pLoss m γ) μ D) ∧
      (∀ (B : ℕ) (Ω : Type) [MeasurableSpace Ω] [StandardBorelSpace Ω] (μ : Measure Ω)
          [IsProbabilityMeasure μ] (P : ReplyProtocol (Coord m) Ω),
        P.IsMeasurable → P.IsFixed → P.HardBudgetOn (promiseBox m) B →
        ENNReal.ofReal (γ * max 0 ((m : ℝ) - B) / (64 * Real.pi ^ 2 * m)) ≤
          replyRegret (promiseBox m) (pLoss m γ) μ P B) ∧
      (∃ P : ReplyProtocol (Coord m) Unit, P.IsMeasurable ∧ IsRawProtocol (promiseDictionary m) P ∧
        P.IsFixed ∧ UsesOneBitReplies P ∧ P.HardBudgetOn (promiseBox m) (m + rr m) ∧
        replyRegret (promiseBox m) (pLoss m γ) (Measure.dirac ()) P (m + rr m) = 0) ∧
      (∀ (B : ℕ) (Ω : Type) [MeasurableSpace Ω] [StandardBorelSpace Ω] (μ : Measure Ω)
          [IsProbabilityMeasure μ] (P : ReplyProtocol (Coord m) Ω),
        P.IsMeasurable → P.HardBudgetOn (promiseBox m) B →
        ENNReal.ofReal (γ * max 0 ((m : ℝ) - ((2 : ℝ) ^ B - 1)) / (64 * Real.pi ^ 2 * m)) ≤
          replyRegret (promiseBox m) (pLoss m γ) μ P B) ∧
      (m = 2 ^ rr m →
        ∀ (Ω : Type) [MeasurableSpace Ω] [StandardBorelSpace Ω] (μ : Measure Ω)
          [IsProbabilityMeasure μ] (P : ReplyProtocol (Coord m) Ω),
          P.IsMeasurable → P.HardBudgetOn (promiseBox m) (rr m) →
          0 < replyRegret (promiseBox m) (pLoss m γ) μ P (rr m)) := 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 9 and eqs. (50)–(53), p.27 (PDF p.30); proof in Appendix G, pp.28–30

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