Proposition 4.7 — regret of the Multiplicative Weights Algorithm (Arora et al., Theorem 2.1)
ProvedBilateralProfit.proposition_4_7bilateral-tradeonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1posted-pricesregret-bounds
Let be a finite action space, a horizon and (, ) losses. Let be the distributions generated by the Multiplicative Weights Algorithm with learning rate against these losses. Then for every fixed ,
In the proof of Lemma 4.6 it is applied to OneRound's table updates with decisions , losses and learning rate .
Formalization Note Rounds are indexed . The loss sequence is arbitrary, which covers losses chosen after is played.
Differences from the source:
- encoding: learning rate → ; reason: a learning rate is positive; the bound divides by
- encoding: "the Multiplicative Weights Algorithm" → weights , , ; reason: the algorithm of Arora–Hazan–Kale's Theorem 2.1, and the update the paper uses on p.21
- encoding: losses in , rounds → a sequence with values in at every , rounds ; reason: only enters the statement, and any losses on extend (e.g. by ) to such a sequence
Preamble
import Mathlib import Definitions.Def_BilateralProfit_MWU
Formal statement
namespace BilateralProfit
/-- **Proposition 4.7** (Theorem 2.1 of Arora, Hazan, Kale), Brüstle, di Gregorio, Fusco,
Leonardi (manuscript, sha256 e91e8127…), p.21 (PDF 23): for losses `ℓ_{i,t} ∈ [−1, 1]` over a
finite action space `𝒳` and horizon `T`, the distributions `p_t` of the Multiplicative Weights
Algorithm with learning rate `γ ≤ 1/2` satisfy, for every fixed `j ∈ 𝒳`,
`Σ_t ⟨p_t, ℓ_t⟩ ≤ Σ_t ℓ_{j,t} + γ Σ_t |ℓ_{j,t}| + log|𝒳|/γ`.
**Formalization Note.** Rounds are `t = 0, …, T − 1`. `𝒳` is a finite type (nonempty, as it contains `j`); `γ > 0`
(the bound divides by `γ`). The loss sequence is arbitrary, which covers losses chosen after
seeing `p_t`. -/
theorem proposition_4_7 {X : Type} [Fintype X] (γ : ℝ) (hγ : 0 < γ)
(hγ' : γ ≤ 1 / 2) (T : ℕ) (ℓ : ℕ → X → ℝ) (hℓ : ∀ t i, ℓ t i ∈ Set.Icc (-1 : ℝ) 1) (j : X) :
∑ t ∈ Finset.range T, ∑ i, mwDist γ ℓ t i * ℓ t i ≤
∑ t ∈ Finset.range T, ℓ t j + γ * ∑ t ∈ Finset.range T, |ℓ t j| +
Real.log (Fintype.card X) / γ := 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), Proposition 4.7, p.21 (PDF 23), quoting Arora, Hazan, Kale, The Multiplicative Weights Update Method: a Meta-Algorithm and Applications, Theory of Computing 8 (2012), Theorem 2.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.