Theorem 1 — Uniform near-optimal regret for DPA
DisprovedCloseGaps.DPA.theorem_1Theorem 1. Let Assumption 1 hold for Γ = Γ(M, K, m_L, m_U). Then there exists an admissible policy π generated by Algorithm DPA, such that for all n ≥ 1,
sup_{λ∈Γ} R_n^π(x,T;λ) ≤ C(log n)^{4.5}/√n
for some constant C.
Differences from the source:
- encoding: Continuous-time controlled Poisson sales with an off action. → A measurable price rule on sale histories, exponential interarrivals and Option-valued actions.; reason: The off action has zero intensity and revenue; the history rule cannot access the unknown demand.
- reading: The size parameter n is written without an integrality restriction. → n is real.; reason: This retains the displayed domain, including every integer size.
- encoding: The DPA objects are constructed by the displayed algorithm. → Partial stage construction and successful construction in the conclusion.; reason: Definedness is asserted in the conclusion at the source sizes: every printed real grid count must be an exact positive integer, each stage duration positive, and each stopping minimum attained; no rounding or restriction to executable sizes is introduced.
- encoding: A supremum of regrets over the demand class. → The same C bounds the regret for every member of the full class.; reason: Pointwise uniform comparison avoids empty or unbounded real-supremum defaults.
- encoding: General T and feasible price interval. → Multiplicative price and time normalization in the algorithm, with the physical fluid benchmark.; reason: Multiplication preserves revenue ordering; C remains outside the price-interval quantifier.
- encoding: Inventory sales are integral and at most nx. → The stochastic sale cap is floor(nx); the fluid inventory remains nx.; reason: These are the same unit-sales constraint, without restricting real initial inventory.
- reading: Stage counts appear as fixed summation limits and deterministic factors outside expectations in section 5, although the interval widths are random. → A common pair of deterministic counts satisfies the actual stopping tests almost surely on the constructed virtual traces.; reason: This is the literal fixed-count reading of the printed formulas; nominal-width equalities are not assumed, and successful construction is asserted in the conclusion.
- encoding: Grid prices have indices j=1,...,κ_i. → Grid indices are j=0,...,k-1, with price lo+j(hi-lo)/k.; reason: The same left endpoints are enumerated; only the index origin changes.
- reading: The empirical argmax and argmin do not specify a tie rule. → Choose the least grid index attaining each finite optimum.; reason: This fixes an observable deterministic selection from the source argmax or argmin, without demand information.
- reading: The base-instance estimator is count/Δ and its inventory target is x/T. → For the size-n normalized instance, estimate base demand by count/(nΔ) and compare with x.; reason: Instantiating the pseudocode with inventory nx and dividing its rate estimate and target by n gives this rule; normalized time has horizon one.
import Definitions.Def_CloseGaps_DPA_RevenueEvents open MeasureTheory Set open scoped Classical
namespace CloseGaps.DPA
theorem theorem_1 (c : Coefficients) (hc : c.Positive)
(x T : ℝ) (hx : 0 < x) (hT : 0 < T) :
∃ C : ℝ, 0 < C ∧ ∀ a : Market, a.Valid →
∃ π : ℝ → PriceRule, ∀ n : ℝ, 1 ≤ n →
∀ lam : ℝ → ℝ, InClass c a x T lam →
(∃ N : StageCounts, generated a lam n x T (π n) N) ∧
admissible a lam n x T (π n) ∧
(fluidRevenues a x T lam).Nonempty ∧ BddAbove (fluidRevenues a x T lam) ∧
0 < fluidValue a x T lam ∧
1 - expectedRevenue (π n) lam n x T / (n * fluidValue a x T lam) ≤
C * (Real.log n) ^ (9 / 2 : ℝ) / Real.sqrt n := by sorry
end CloseGaps.DPA
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
For a coefficient object (of type Coefficients) that satisfies the predicate c.Positive, and for real numbers and , the statement asserts the following.
There is a real constant , depending only on , and , with this property. For every market (of type Market) that satisfies the predicate a.Valid, there is a family of price rules . Each is an object of type PriceRule, and the family is indexed by all real numbers , not only by integers. The family may depend on , , , and . It is chosen before any intensity function is fixed, so it may not depend on .
The family must work as follows. For every real and every function satisfying InClass c a x T λ, all five of these hold at once:
- Generation. There is a stage-count object (of type
StageCounts) such thatgenerated a λ n x T (π n) Nholds. - Admissibility.
admissible a λ n x T (π n)holds. - Fluid revenues. The set given by
fluidRevenues a x T λis a nonempty subset of and is bounded above. - Fluid value. The real number given by
fluidValue a x T λis strictly positive. - Revenue gap. Write for the real number
expectedRevenue (π n) λ n x T. Then
where is the natural logarithm and is a real power.
Undefined names. Coefficients, Positive, Market, Valid, PriceRule, StageCounts, InClass, generated, admissible, fluidRevenues, fluidValue and expectedRevenue all come from the imported module Definitions.Def_CloseGaps_DPA_RevenueEvents. That module was not provided, so this read-back cannot unfold them. What each one asserts or computes is outside what is described here. In particular, conclusions 1–4 are claims about those definitions, and their content depends entirely on how the definitions are written. Conclusions 3 and 4 (nonemptiness, boundedness above, positivity) are asserted as conclusions, not assumed as hypotheses.
Logical form. The gap bound is one-sided. If exceeds , the left-hand side is negative and the inequality holds automatically. No lower bound on the gap and no upper bound on is claimed. The constant is uniform over all valid markets , all real and all admissible . Only the price-rule family is allowed to depend on .
Degenerate cases.
- If no market satisfies
a.Valid, everything after the choice of is vacuous, and the statement reduces to the existence of some , which is trivially true. - For a given and , if no satisfies
InClass c a x T λ, then nothing is required of for that pair. - If
c.Positivecan never hold, the whole statement is vacuous. - The denominator is strictly positive, because and conclusion 4 asserts . So the junk value that division by zero would give never enters.
- Because , , so the real power is the usual nonnegative value. Also , so neither the power nor the square root takes a junk value.
- At , , so the right-hand side is . The statement then requires for every admissible .
- Non-integer (for example ) are included, with the same requirements.
- Whether
expectedRevenueorfluidValuecan take a default value (for example an integral of a non-integrable function, or a supremum of an empty or unbounded set) depends on the unseen definitions. The statement only guarantees that is nonempty and bounded above, and that .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.