AFTD Auto-Formalizing Theoretical Domains

hedge_construction

theoremverifiedimported Lean

Hedge yields an approximate minimax pair. Let $G$ be a finite two-player zero-sum game with $M \ge 2$ row actions and $N \ge 1$ column actions, with payoff matrix $(A_{ij})$ satisfying $0 \le A_{ij} \le 1$; the row player maximises and the column player minimises. Fix an integer $T > 0$ and a learning rate $\eta > 0$. Then there exist a mixed row strategy $p$ and a mixed column strategy $q$ such that, for every pure row $i \in \{1,\dots,M\}$ and every pure column $j \in \{1,\dots,N\}$, \[ \sum_{i'} p_{i'}\,A_{i'j} \;+\; \frac{(\ln M)/\eta + \eta T/8}{T} \;\ge\; \sum_{j'} A_{ij'}\,q_{j'}. \]

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open Real Finset BigOperators in
lemma hedge_construction {M N : ℕ} [NeZero M] [NeZero N] (G : ZeroSumGame M N)
    (_hM : 1 < M)
    (T : ℕ) (hT : 0 < T)
    (η : ℝ) (hη_pos : 0 < η) :
    ∃ (p : MixedStrategy M) (q : MixedStrategy N),
      ∀ (i : Fin M) (j : Fin N),
        payoffVsPure G p j + (Real.log M / η + η * T / 8) / T ≥
          pureVsPayoff G i q
Source
TCSlib, `hedge_construction`
Lean proof
By Karim Abdel Sadek, Mark Bedaywi, from github.com/Shilun-Allan-Li/tcslib at c8a02591b1e5 (Copyright (c) 2026 Karim Abdel Sadek and Mark Bedaywi. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 25
  • hedgeResponseNat_isBestResponseOnline column response is a best response. Let $G$ be a finite zero-sum game with $M \ge 1$ row actions and $N \ge 1$ column actions, let…
  • pureVsPayoffGiven a game $G$, a pure row $i$, and a mixed column strategy $q$, the expected payoff of row $i$ against $q$ is…
  • MixedStrategyA mixed strategy over $n$ actions is a record consisting of a weight function $w : \mathrm{Fin}\,n \to \mathbb{R}$ together with…
  • hedge_regret_bound_tightTight Hedge regret bound. Fix $N \ge 1$ experts and a horizon of $T$ rounds, and run the Hedge algorithm with a learning rate $\eta > 0$.…
  • hedgeResponseNatThe sequence of column best responses generated online against Hedge: at time $t$, given the history $a_0, \dots, a_{t-1}$ of prior column…
  • cumLoss_horizonCumulative loss at the horizon. Fix $N$ experts and a horizon $T$, and let $\ell$ be a loss sequence assigning to each round $t$ and…
  • ZeroSumGameA finite two-player zero-sum game with $M$ row actions and $N$ column actions is a record consisting of a payoff matrix…
  • hedgeDistThe Hedge distribution at round $t$ is the normalization of the weight vector: \[ p_t(i) \;=\; \frac{w_t(i)}{W_t}. \]
  • payoffVsPure_averageStrategyAverage strategy's payoff against a pure column. Let $G$ be a finite two-player zero-sum game with $M \ge 1$ row actions and $N$ column…
  • ZeroSumGame.toLossSeqGiven a game $G$ and a sequence of column responses $j_0, \dots, j_{T-1}$, the induced loss sequence for the row player is…
  • averageStrategyGiven $T$ distributions $p_0, \dots, p_{T-1}$ over $\mathrm{Fin}\,n$ (each presented as non-negative weights summing to $1$) and $T > 0$,…
  • LossSeq.ValidA loss sequence $\ell$ is valid if all individual losses are in $[0,1]$: $\forall t\,i,\; 0 \le \ell_t(i) \le 1$.
  • hedgeCumLossThe cumulative loss of the Hedge algorithm over all $T$ rounds is \[ \widehat{L}_T \;=\; \sum_{t=0}^{T-1} \widehat{\ell}_t. \]
  • hedgeLossThe expected loss of the learner at round $t$ under the Hedge distribution is…
  • regretThe regret of the Hedge algorithm is the excess cumulative loss over the best expert in hindsight:…
  • empiricalStrategyGiven $T > 0$ pure actions $a_0, \dots, a_{T-1} \in \mathrm{Fin}\,n$, the empirical strategy is the mixed strategy assigning to…
  • hedgeDist_nonnegNonnegativity of the Hedge distribution. Fix $N \ge 1$ experts and $T$ rounds, a learning rate $\eta \in \bbr$, and a loss sequence…
  • ZeroSumGame.toLossSeq_validValidity of the loss sequence induced by a zero-sum game. Let $G$ be a finite two-player zero-sum game with $M$ row actions and $N$ column…
  • regret_to_payoffRegret-to-payoff bridge for zero-sum games. Consider a finite two-player zero-sum game with $M \ge 1$ row actions and $N$ column actions…
  • bestExpertLossThe best expert loss in hindsight is the minimum cumulative loss achieved by any single expert:…
  • payoffVsPureGiven a game $G$, a mixed row strategy $p$, and a pure column $j$, the expected payoff against column $j$ is…
  • pureVsPayoff_empiricalStrategyPure-row payoff against the empirical column strategy. Let $G$ be a finite two-player zero-sum game with $M$ row actions and $N \ge 1$…
  • LossSeqA loss sequence $\ell$ for $N$ experts over $T$ rounds is a function $\ell : \mathrm{Fin}\,T \to \mathrm{Fin}\,N \to \mathbb{R}$,…
  • hedgeDist_sumThe Hedge distribution sums to one. Fix a number of experts $N \ge 1$, a horizon $T$, a learning rate $\eta \in \bbr$, a loss sequence…
  • cumLossThe cumulative loss of expert $i$ through the first $t$ rounds is \[ L_t(i) \;=\; \sum_{s < t} \ell_s(i), \] where the sum ranges…
Used by 1
  • approx_minimaxApproximate minimax for finite zero-sum games. Let $G$ be a finite two-player zero-sum game with payoff matrix $A$, having $M \ge 2$ row…

Lean source view module on GitHub

set_option relaxedAutoImplicit false inset_option autoImplicit false inopen Real Finset BigOperators in/-- The Hedge construction: given a game `G` with `M ≥ 2` rows, a horizon `T > 0`, and a learning rate `η > 0`, there exist mixed strategies `p`, `q` such that for all pure `i`, `j`, `payoffVsPure G p j + (log M / η + η T / 8) / T ≥ pureVsPayoff G i q`. Here `p` is the time average of the Hedge distributions played on the losses `1 − A(·, j_t)` and `q` is the empirical distribution of the columns `j_t`, each of which is a pure best response to the current Hedge distribution. [FS99, §§5–6.1]; [CBL06, proof of Thm 7.1]. The hypothesis `1 < M` is not used by this lemma's proof (it is carried for `approx_minimax`). **Proof sketch.** Step 1 (`hvalid`): generate the online column responses `hedgeResponseNat`, form the induced loss sequence `ℓ` (valid, since payoffs lie in `[0, 1]`), and record the Hedge distributions `strategies t := hedgeDist η ℓ t`; take `p := averageStrategy` and `q := empiricalStrategy`. Step 2 (`hreg`): the tight Hedge regret bound `log M / η + η T / 8` on `ℓ` (`hedge_regret_bound_tight`), read through `regret_to_payoff`, says the realized payoff sum is at least the best fixed row's payoff sum minus `R`. Step 3 (`hbest_sum`): by `hedgeResponseNat_isBestResponse`, replacing each played column by the fixed column `j` can only increase the row payoff, round by round. Step 4 (`hmain`): for the fixed row `i`, chain Steps 2 and 3 (`i`'s payoff sum is at most the supremum) and divide by `T`. Step 5 (`hpj`, `hqi`): both sides of the goal are the time averages computed in `payoffVsPure_averageStrategy` and `pureVsPayoff_empiricalStrategy`; conclude by linear arithmetic. -/lemma hedge_construction {M N : ℕ} [NeZero M] [NeZero N] (G : ZeroSumGame M N)    (_hM : 1 < M)    (T : ℕ) (hT : 0 < T)    (η : ℝ) (hη_pos : 0 < η) :    ∃ (p : MixedStrategy M) (q : MixedStrategy N),      ∀ (i : Fin M) (j : Fin N),        payoffVsPure G p j + (Real.log M / η + η * T / 8) / T ≥          pureVsPayoff G i q := by  classical  -- Step 1 (`hvalid`): generate the online column responses, turn them into a  -- valid Hedge loss sequence, and record the row distributions Hedge plays.  let actions : Fin T → Fin N := fun t => hedgeResponseNat G η t.val  let ℓ : LossSeq M T := G.toLossSeq actions  let strategies : Fin T → Fin M → ℝ := fun t i => hedgeDist η ℓ t.val i  have h_nonneg : ∀ t i, 0 ≤ strategies t i := fun t i => hedgeDist_nonneg η ℓ t.val i  have h_sum : ∀ t, ∑ i : Fin M, strategies t i = 1 := fun t => hedgeDist_sum η ℓ t.val  have hvalid : ℓ.Valid := ZeroSumGame.toLossSeq_valid G actions  refine ⟨averageStrategy hT strategies h_nonneg h_sum, empiricalStrategy hT actions, ?_⟩  intro i j  set R : ℝ := Real.log ↑M / η + η * ↑T / 8 with hR  -- Step 2 (`hreg`): the tight Hedge bound on `ℓ`, translated into a payoff  -- guarantee against the best fixed row action (`regret_to_payoff`).  have hreg :      ∑ t : Fin T, ∑ i : Fin M, strategies t i * G.payoff i (actions t) ≥        ⨆ i : Fin M, ∑ t : Fin T, G.payoff i (actions t) - R := by    have hbestEq :        bestExpertLoss ℓ =          ⨅ i : Fin M, (∑ t : Fin T, (1 - G.payoff i (actions t))) := by      unfold bestExpertLoss      congr 1      ext i      rw [cumLoss_horizon]      rfl    have hreg' :        (∑ t : Fin T, ∑ i : Fin M, strategies t i * (1 - G.payoff i (actions t))) -          ⨅ i : Fin M, (∑ t : Fin T, (1 - G.payoff i (actions t))) ≤ R := by      simpa only [R, regret, hedgeCumLoss, hedgeLoss, strategies, ℓ, ZeroSumGame.toLossSeq,        hbestEq] using hedge_regret_bound_tight η hη_pos ℓ hvalid    exact regret_to_payoff G hT strategies h_sum actions R hreg'  -- Step 3 (`hbest_sum`): each generated column is a best response to the  -- current Hedge distribution, so replacing it by the fixed column `j` can  -- only increase the row payoff, round by round.  have hbest_sum :      ∑ t : Fin T, ∑ i : Fin M, strategies t i * G.payoff i (actions t) ≤        ∑ t : Fin T, ∑ i : Fin M, strategies t i * G.payoff i j :=    Finset.sum_le_sum fun t _ => hedgeResponseNat_isBestResponse G η t j  -- Step 4 (`hmain`): combine Steps 2 and 3 for the fixed row `i`, then divide  -- by `T`.  have hmain :      (∑ t : Fin T, G.payoff i (actions t)) / ↑T - R / ↑T ≤        (∑ t : Fin T, ∑ i : Fin M, strategies t i * G.payoff i j) / ↑T := by    have hi_sup : (∑ t : Fin T, G.payoff i (actions t)) - R ≤        ⨆ i : Fin M, ∑ t : Fin T, G.payoff i (actions t) - R := by      have hbdd : BddAbove (Set.range (fun i : Fin M => ∑ t : Fin T, G.payoff i (actions t) - R)) :=        Set.Finite.bddAbove (Set.finite_range _)      exact le_ciSup hbdd i    have hTpos : (0 : ℝ) < ↑T := Nat.cast_pos.mpr hT    have := div_le_div_of_nonneg_right (show ∑ t : Fin T, G.payoff i (actions t) - R ≤        ∑ t : Fin T, ∑ i : Fin M, strategies t i * G.payoff i j by linarith) hTpos.le    field_simp at this ⊢    linarith  -- Step 5 (`hpj`, `hqi`): both sides of the goal are time averages.  have hpj :      payoffVsPure G (averageStrategy hT strategies h_nonneg h_sum) j =        (∑ t : Fin T, ∑ i : Fin M, strategies t i * G.payoff i j) / ↑T :=    payoffVsPure_averageStrategy G hT strategies h_nonneg h_sum j  have hqi :      pureVsPayoff G i (empiricalStrategy hT actions) =        (∑ t : Fin T, G.payoff i (actions t)) / ↑T :=    pureVsPayoff_empiricalStrategy G hT actions i  rw [hpj, hqi, hR]  linarith
See it in the graphDiscuss this resultChallenge it