Theorem 4.1 — a polynomial-time algorithm with regret against every oblivious adversary
ProvedBilateralProfit.theorem_4_1_regret_boundThere is a polynomial time algorithm such that, for every valuation sequence fixed in advance, the prices it posts satisfy
Precisely: Algorithm 1 (with OneRound, eqs. (5), (6), (8)) at resolution satisfies, for constants and :
- for every horizon , every sequence and every comparator ,
the expectation being over the algorithm's own randomness; 2. for every such , sequence and realization of the randomness, the run performs at most unit-cost operations.
The learner observes only the trade bit of each round. The comparator ranges over all of , including , and the valuations are arbitrary reals in .
Formalization Note Logarithms are natural. The algorithm's randomness is one uniform draw per round, independent across rounds; the expectation is the average over the outcomes. The operation count is the counter of the run in the cost model of OneRound.
Differences from the source:
- generalization: "there exists a polynomial time algorithm " (with ) → the explicit Algorithm 1 + OneRound at ; reason: the paper's algorithm with an explicit admissible resolution; it witnesses the existential statement
- encoding: → with the bound for every ; reason: at the right side is while every algorithm has positive regret on some one-round sequence; is asymptotic in
- encoding: "polynomial time" → the run's unit-cost operation count is at most for every input and every realization of the randomness; reason: the paper's own count (p.23) is of real-arithmetic operations; bit complexity is not claimed
- encoding: of the expected regret; natural → the bound for every comparator ;
Real.log; reason: a supremum is at most iff every term is; the paper's logarithms are natural (p.21) - encoding: the expectation over the learner's randomness → the uniform average over draw sequences ; reason: Algorithm 1's only randomness is the independent uniform of each OneRound call
import Mathlib import Definitions.Def_BilateralProfit_Algorithm1
namespace BilateralProfit
/-- **Theorem 4.1 (Regret bound)**, Brüstle, di Gregorio, Fusco, Leonardi (manuscript, sha256
e91e8127…), p.16 (PDF 18): there is a polynomial time algorithm whose regret against every
valuation sequence fixed in advance is `O(T^{2/3} log^{7/3} T)`.
Stated for the paper's algorithm (Algorithm 1 with OneRound, eqs. (5), (6), (8)) at the
resolution `K(T) = Kpin T`. Both clauses share the constant `C`:
1. for every horizon `T ≥ 2`, every valuation sequence `S ∈ ([0,1]²)^T` and every comparator
`(p, q) ∈ [0,1]²`, `Σ_t E[Profit_t(p, q) − Profit_t(p_t, q_t)] ≤ C T^{2/3} (log T)^{7/3}`,
the expectation being over the algorithm's own randomness;
2. for every such `T`, `S` and every realization `ω` of the randomness, the run performs at
most `C T^c` unit-cost operations.
**Formalization Note.** `O(·)` is `∃ C > 0` for all `T ≥ 2` (at `T = 1` the right side is `0`).
The supremum over comparators is written as a bound for every comparator. `log` is the natural
logarithm. The cost model is the one of `OneRound` (unit-cost real arithmetic, `log`,
comparisons, table reads and writes, loop dispatch), counted by the program itself. -/
theorem theorem_4_1_regret_bound :
∃ C c : ℝ, 0 < C ∧ ∀ T : ℕ, 2 ≤ T →
(∀ S : Fin T → ℝ × ℝ, (∀ t, S t ∈ Set.Icc (0 : ℝ) 1 ×ˢ Set.Icc (0 : ℝ) 1) →
∀ p q : ℝ, p ∈ Set.Icc (0 : ℝ) 1 → q ∈ Set.Icc (0 : ℝ) 1 →
∑ t, (profit (S t) (p, q) - expProfit (Kpin T) T S t) ≤
C * (T : ℝ) ^ ((2 : ℝ) / 3) * Real.log T ^ ((7 : ℝ) / 3)) ∧
(∀ S : Fin T → ℝ × ℝ, (∀ t, S t ∈ Set.Icc (0 : ℝ) 1 ×ˢ Set.Icc (0 : ℝ) 1) →
∀ ω : Fin T → Fin (Jpar (Kpin T)),
(alg1Cost (Kpin T) T S ω : ℝ) ≤ C * (T : ℝ) ^ c) := by sorry
end BilateralProfit
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.