Theorem 5.1 — one-bit feedback achieves regret for independent MHR valuations
ProvedBilateralProfitMHR.theorem_5_1_regret_boundThere exists a learning algorithm with one-bit feedback such that, for every horizon and every pair of independent MHR buyer and seller distributions on with strictly positive densities,
Precisely: there are a constant , a probability space of seeds and, for every horizon , a pricing policy that observes only the trade bit of each round, all fixed in advance, such that for every , every such and every comparator (including ),
the expectations being over the i.i.d. valuations and the algorithm's randomness. MHR means that the seller's hazard rate is nonincreasing on and the buyer's is nondecreasing on .
This improves the regret of the adversarial setting to under the monotone hazard rate assumption, still with one-bit feedback.
Formalization Note Logarithms are natural; rounds are indexed .
Differences from the source:
- reading: "there exists a learning algorithm … for every " → a family of policies indexed by the horizon , with one seed space, fixed before and ; reason: Algorithm 6 takes the horizon as input and sets from
- encoding: → there is with the bound for every ; reason: at the right side is ; is asymptotic in
- encoding: ; ; rounds ; the learner's private randomness → the bound for every comparator in ; the natural logarithm; rounds ; a seed drawn once from a probability space; reason: a supremum is at most iff every term is; the remaining items are notation
- encoding: "independent MHR buyer and seller distributions on with strictly positive densities" → the published bilateral trade environment with supports (independent values, measurable densities strictly positive on integrating to ) satisfying Definition 2.3 for both agents; reason: §2's class exactly; the reused structure adds no condition
import Mathlib import Definitions.Def_BilateralProfitMHR_Model
namespace BilateralProfitMHR
open MeasureTheory BilateralProfit MechanismDesign.BilateralTrade
/-- **Theorem 5.1 (Regret for MHR distributions)**, Brüstle, di Gregorio, Fusco, Leonardi
(manuscript, sha256 e91e8127…), p.30 (PDF 32): there exists a learning algorithm `𝒜` with
one-bit feedback such that, for every `T` and every pair `𝒟` of independent MHR buyer and seller
distributions on `[0, 1]` with strictly positive densities,
`R_T(𝒜, 𝒟) ≤ O(√T (log T)^{5/2})`.
There are a constant `C > 0`, a seed space `(Ω, P)` and, for every horizon `T`, a one-bit
policy `π T`, chosen before `T` and `𝒟`, such that for every `T ≥ 2`, every environment `E`
(independent values, densities strictly positive on `[0, 1]`, both MHR) and every comparator
`(p, q) ∈ [0, 1]²`,
`∑_{t=1}^T (E[Profit_t(p, q)] − E[Profit_t(p_t, q_t)]) ≤ C √T (log T)^{5/2}`, the expectations
being over the i.i.d. valuations with law `E.prior` and the seed.
**Formalization Note.** "A learning algorithm … for every `T`" is a family indexed by the
horizon (Algorithm 6 takes `T` as input and sets `K` from `T`), fixed before `T` and `𝒟`.
`O(·)` is `∃ C > 0` for every `T ≥ 2` (at `T = 1` the right side is `0`). The supremum over
comparators is a bound for every comparator. Logarithms are natural; rounds are `Fin T`. -/
theorem theorem_5_1_regret_bound :
∃ C : ℝ, 0 < C ∧ ∃ (Ω : Type) (_ : MeasurableSpace Ω) (P : Measure Ω),
IsProbabilityMeasure P ∧ ∃ π : (T : ℕ) → Policy T Ω, (∀ T, (π T).OneBit) ∧
∀ T : ℕ, 2 ≤ T → ∀ E : Environment, UnitSupport E → IsMHR E →
∀ p q : ℝ, p ∈ Set.Icc (0 : ℝ) 1 → q ∈ Set.Icc (0 : ℝ) 1 →
(π T).regret P E.prior (p, q) ≤
C * Real.sqrt T * Real.log T ^ ((5 : ℝ) / 2) := by sorry
end BilateralProfitMHR
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.