Theorem 2, p. 11 — EllipsoidPricing with ε = Rd²/T has worst-case regret O(Rd² ln(T/d))
DisprovedFeaturePricing.Ellipsoid.ellipsoid_pricing_regretTheorem 2. The worst-case regret of the EllipsoidPricing algorithm with parameter is .
Precisely: there is a universal constant such that for every dimension , every , every horizon , every parameter with , and every feature sequence with for all (Euclidean norms), the run of EllipsoidPricing with parameter started from satisfies
This is the main result of the paper: a pricing policy for products described by features whose worst-case regret is polynomial (quadratic) in and logarithmic in , in contrast with the exponential-in- regret of the multi-dimensional binary search (PolytopePricing, Theorem 1).
Formalization Note The is read with one constant quantified before and the features, so does not depend on the instance. The thresholds (Eq. (4) divides by ) and (for , and the bound is meaningless) are added. The maximum over 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 , so quantifying over the whole ball covers every . The initial ellipsoid is the ball , an ellipsoid containing as the paper allows (p. 11). The printed proof (p. 16) bounds each exploration round's regret by ; that bound is not justified as printed (see the mission description), so the statement here is the -claim of the theorem, not the proof's explicit inequality.
import Mathlib import Definitions.Def_FeaturePricing_Ellipsoid_EllipsoidPricing
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.