Eq. (12) — the information as averaged Bernoulli KL divergences, and Pinsker
ProvedBilateralProfit.eq_12bilateral-tradeonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1posted-pricesregret-bounds
Let be a distribution on and . Under the feedback is a Bernoulli variable with success probability , or conditionally on , and
The last inequality is Pinsker's inequality for Bernoulli laws; combined with the contradiction hypothesis it gives Claim 4.4 in the proof of Theorem 4.2.
Formalization Note is the published klBern p q. Conditional probabilities given are set to when ; such terms carry the factor .
Differences from the source:
- encoding: the grid of step size → hypothesis ; reason: the step size presupposes (Lemma A.6: "for every integer ")
- encoding: and conditional probabilities →
klBernand ratios with ; reason: terms with are multiplied by ; otherwise when and when , whereklBerntakes the true value
Preamble
import Mathlib import Definitions.Def_RegretBandits_Stochastic_klBernoulli import Definitions.Def_BilateralProfit_Analysis
Formal statement
namespace BilateralProfit
open RegretBandits.Stochastic (klBern)
/-- **Equation (12)**, Brüstle, di Gregorio, Fusco, Leonardi (manuscript, sha256 e91e8127…),
pp.19–20 (PDF 21–22), in the proof of Theorem 4.2: for every distribution `ρ` on `G_K × 𝒜` and
every action `a`,
`ℐ_ρ(a) = Σ_{a′} P_ρ(A = a′) [Σ_z P_ρ(z_a(V) = z | A = a′) log (P_ρ(z_a(V) = z | A = a′)/P_ρ(z_a(V) = z))]
= Σ_{a′} P_ρ(A = a′) D_KL(Bern(P_{a′}(a)) ‖ Bern(P0(a)))
≥ 2 Σ_{a′} P_ρ(A = a′) (P_{a′}(a) − P0(a))²`.
**Formalization Note.** `D_KL(Bern(p) ‖ Bern(q))` is the published `klBern p q`. The conditional
probabilities use `x / 0 = 0` when `P_ρ(A = a′) = 0`; those terms are multiplied by
`P_ρ(A = a′) = 0`. In the remaining terms `P_{a′}(a) = 0` whenever `P0(a) = 0` and `P_{a′}(a) = 1`
whenever `P0(a) = 1`, where `klBern` takes its correct value `0`. -/
theorem eq_12 (K : ℕ) (hK : 0 < K) (ρ : Grid K × Act K → ℝ) (hρ : IsDist ρ) (a : Act K) :
info ρ a = ∑ a', margA ρ a' * ∑ z : Bool,
(jointP ρ a a' z / margA ρ a') *
Real.log ((jointP ρ a a' z / margA ρ a') / zP ρ a z) ∧
∑ a', margA ρ a' * ∑ z : Bool,
(jointP ρ a a' z / margA ρ a') *
Real.log ((jointP ρ a a' z / margA ρ a') / zP ρ a z) =
∑ a', margA ρ a' * klBern (Pcond ρ a' (pt K a.1)) (P0 ρ (pt K a.1)) ∧
2 * ∑ a', margA ρ a' * (Pcond ρ a' (pt K a.1) - P0 ρ (pt K a.1)) ^ 2 ≤
∑ a', margA ρ a' * klBern (Pcond ρ a' (pt K a.1)) (P0 ρ (pt K a.1)) := by sorry
end BilateralProfit
Source
Brüstle, di Gregorio, Fusco, Leonardi, Regret Bounds for Profit Maximization in Bilateral Trade: Learning the Best Posted-Price Mechanism (manuscript, STOC 2027 submission, sha256 e91e81279505b765c7c96c219d674c0fbbbd6ca47a00da8fe228d498ca25ac87), eq. (12), pp.19–20 (PDF 21–22), in the proof of Theorem 4.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.