Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2, p. 11 — EllipsoidPricing with ε = Rd²/T has worst-case regret O(Rd² ln(T/d))

Disproved
FeaturePricing.Ellipsoid.ellipsoid_pricing_regret

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

contextual-banditsdynamic-pricingellipsoid-methodp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1regret

Theorem 2. The worst-case regret of the EllipsoidPricing algorithm with parameter ϵ=Rd2/T\epsilon=Rd^2/Tϵ=Rd2/T is O(Rd2ln⁡(T/d))O(Rd^2\ln(T/d))O(Rd2ln(T/d)).

Precisely: there is a universal constant C>0C>0C>0 such that for every dimension d≥2d\ge2d≥2, every R>0R>0R>0, every horizon T≥2dT\ge2dT≥2d, every parameter θ∈Rd\theta\in\mathbb R^dθ∈Rd with ∥θ∥≤R\|\theta\|\le R∥θ∥≤R, and every feature sequence (xt)(x_t)(xt​) with ∥xt∥≤1\|x_t\|\le1∥xt​∥≤1 for all ttt (Euclidean norms), the run of EllipsoidPricing with parameter ϵ=Rd2/T\epsilon=Rd^2/Tϵ=Rd2/T started from E1=B(0,R)E_1=B(0,R)E1​=B(0,R) satisfies

∑t=1T[θ′xt−pt I{θ′xt≥pt}] ≤ C R d2ln⁡(T/d).\sum_{t=1}^T\big[\theta'x_t-p_t\,\mathbb I\{\theta'x_t\ge p_t\}\big]\ \le\ C\,R\,d^2\ln(T/d).t=1∑T​[θ′xt​−pt​I{θ′xt​≥pt​}] ≤ CRd2ln(T/d).

This is the main result of the paper: a pricing policy for products described by ddd features whose worst-case regret is polynomial (quadratic) in ddd and logarithmic in TTT, in contrast with the exponential-in-ddd regret of the multi-dimensional binary search (PolytopePricing, Theorem 1).

Formalization Note The O(⋅)O(\cdot)O(⋅) is read with one constant CCC quantified before d,R,T,θd,R,T,\thetad,R,T,θ and the features, so CCC does not depend on the instance. The thresholds d≥2d\ge2d≥2 (Eq. (4) divides by d2−1d^2-1d2−1) and T≥2dT\ge2dT≥2d (for T≤dT\le dT≤d, ln⁡(T/d)≤0\ln(T/d)\le0ln(T/d)≤0 and the bound is meaningless) are added. The maximum over θ∈K1\theta\in K_1θ∈K1​ and over nature's closed-loop strategies in Eq. (1) becomes a universal quantifier: the algorithm is deterministic, so a closed-loop nature yields a fixed feature sequence, and K1⊆{∥θ∥≤R}K_1\subseteq\{\|\theta\|\le R\}K1​⊆{∥θ∥≤R}, so quantifying over the whole ball covers every K1K_1K1​. The initial ellipsoid is the ball B(0,R)B(0,R)B(0,R), an ellipsoid containing K1K_1K1​ as the paper allows (p. 11). The printed proof (p. 16) bounds each exploration round's regret by RRR; that bound is not justified as printed (see the mission description), so the statement here is the OOO-claim of the theorem, not the proof's explicit inequality.

Preamble
import Mathlib
import Definitions.Def_FeaturePricing_Ellipsoid_EllipsoidPricing
Formal statement
namespace FeaturePricing.Ellipsoid

open Matrix LinearOptimization

/-- **Theorem 2, p. 11.** The worst-case regret of EllipsoidPricing with parameter `ε = Rd²/T`,
started from `E₁ = B(0, R)`, is `O(Rd² ln(T/d))`: there is a universal constant `C > 0` such that
for every dimension `d ≥ 2`, radius `R > 0`, horizon `T ≥ 2d`, parameter `θ` with `‖θ‖ ≤ R` and
feature sequence with `‖x_t‖ ≤ 1` (Euclidean norms), the regret (1) over `T` periods is at most
`C · R · d² · ln(T/d)`. -/
theorem ellipsoid_pricing_regret :
    ∃ C : ℝ, 0 < C ∧
      ∀ (d : ℕ), 2 ≤ d → ∀ (R : ℝ), 0 < R → ∀ (T : ℕ), 2 * d ≤ T →
      ∀ (θ : Fin d → ℝ), θ ⬝ᵥ θ ≤ R ^ 2 →
      ∀ (x : ℕ → Fin d → ℝ), (∀ t, x t ⬝ᵥ x t ≤ 1) →
        regret R (R * (d : ℝ) ^ 2 / (T : ℝ)) θ x T ≤
          C * R * (d : ℝ) ^ 2 * Real.log ((T : ℝ) / (d : ℝ)) := by sorry

end FeaturePricing.Ellipsoid
Source
Cohen, Lobel, Paes Leme, Feature-Based Dynamic Pricing, Management Science (2020), DOI 10.1287/mnsc.2019.3485 (authors' copy, SSRN 2737045), p. 11, Theorem 2 (regret Eq. (1), p. 8; proof pp. 15–16)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

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