Theorem 7.1 — every algorithm has regret on some independent regular valuations
ProvedBilateralProfitLB.theorem_7_1_lower_boundConsider profit maximization in bilateral trade with posted prices in the stochastic setting: the valuation pairs are i.i.d. from a law on , and in round the learner posts and earns .
There are a universal constant and a horizon such that for every and every learning algorithm (randomized, with feedback the two bits and per round, hence in particular with the one trade bit of §2), there is an independent and regular distribution , with densities strictly positive on and nondecreasing virtual cost and virtual value on , such that
the expectation being over the valuations and the algorithm's randomness.
With the upper bound of Theorem 6.1 this settles the minimax regret rate for independent regular valuations up to logarithmic factors, and separates it from the rate of the MHR class.
Formalization Note An algorithm is a policy with an arbitrary probability space of seeds, chosen after ; the regret bound is witnessed by one comparator . is the real power.
Differences from the source:
- generalization: "any learning algorithm" (one-bit feedback, §2) → every randomized two-bit policy; reason: one-bit policies are the two-bit policies whose prices depend only on the trade bits, and the proof is for this class ("an even stronger class of algorithms", p.49)
- reading: "for any learning algorithm there exists … for some universal and large enough" → ; reason: §2 (p.4) defines the minimax regret as the infimum over algorithms of the worst case over instances, Table 1 lists (Thms. 6.1 & 7.1) as a minimax rate, and the proof's instance depends on through
- encoding: "for large enough" and → , , and one comparator in achieving the bound; reason: the supremum is attained (p.4)
- encoding: "regular and independent distributions" → an independent environment with supports , densities strictly positive on , and Definition 2.2 for seller and buyer; reason: the standing assumption of §2 (p.4) for this class; requiring it of the hard instance makes the bound stronger
import Mathlib import Definitions.Def_BilateralProfitLB_Stochastic
namespace BilateralProfitLB
open MeasureTheory MechanismDesign.BilateralTrade
/-- **Theorem 7.1**, Brüstle, di Gregorio, Fusco, Leonardi (manuscript, sha256 e91e8127…), p.49
(PDF 51): for any learning algorithm `𝒜` there exist regular and independent distributions `𝒟`
such that `𝒜` suffers regret `R_T(𝒜, 𝒟) ≥ c T^{3/5}`, for some universal constant `c` and `T`
large enough.
Stated as: there are `c > 0` and `T₀` such that for every horizon `T ≥ T₀`, every probability
space `(Ω, P)` of seeds and every randomized two-bit posted-price policy `π` on it, there is an
independent environment `E` (seller and buyer independent, densities strictly positive on
`[0, 1]`) with both virtual-value functions nondecreasing on `[0, 1]` (Definition 2.2) and a
comparator `(p, q) ∈ [0, 1]²` with
`Σ_{t < T} (E[Profit_t(p, q)] − E[Profit_t(p_t, q_t)]) ≥ c T^{3/5}`, the valuations being
i.i.d. with law `E.prior` and independent of the seed.
**Formalization Note.** Two-bit policies (feedback `(1{s_t ≤ p_t}, 1{q_t ≤ b_t})`) contain the
paper's one-bit algorithms (`Policy.OneBit`); the proof is for this class (p.49). `c` and `T₀`
come first; `𝒟` may depend on `T` and on the algorithm (the minimax reading, §2 p.4 and
Table 1). `R_T ≥ c T^{3/5}` is witnessed by one comparator (the supremum of §2 is attained).
`T^{3/5}` is the real power `(T : ℝ) ^ (3/5 : ℝ)`. -/
theorem theorem_7_1_lower_bound :
∃ c : ℝ, 0 < c ∧ ∃ T₀ : ℕ, ∀ T : ℕ, T₀ ≤ T →
∀ (Ω : Type) [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(π : Policy Ω),
∃ E : Environment, UnitSupport E ∧ E.Regular ∧
∃ a ∈ Set.Icc (0 : ℝ) 1 ×ˢ Set.Icc (0 : ℝ) 1,
c * (T : ℝ) ^ ((3 : ℝ) / 5) ≤ regret π P E.prior T a := by sorry
end BilateralProfitLB
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.