prefixGameLoss_eq_cumLoss
Prefix game loss equals induced cumulative loss. Let $G$ be a finite two-player zero-sum game with $M$ row actions and $N$ column actions, given by a payoff matrix $A$ with $0 \le A_{ij} \le 1$, and let $a_0, \dots, a_{T-1}$ be a sequence of column actions with each $a_s \in \mathrm{Fin}\,N$. Fix a row action $i \in \mathrm{Fin}\,M$ and a round $t \in \mathrm{Fin}\,T$. Then the prefix cumulative loss of row $i$ along the first $t$ column actions coincides with the cumulative loss of expert $i$ through the first $t$ rounds of the loss sequence induced by $G$ and $(a_s)_s$; that is, \[ \sum_{s=0}^{t-1} \bigl(1 - A_{i,\,a_s}\bigr) \;=\; \sum_{s < t} \bigl(1 - A_{i,\,a_s}\bigr). \]
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open Real Finset BigOperators in lemma prefixGameLoss_eq_cumLoss {M N T : ℕ} (G : ZeroSumGame M N) (actions : Fin T → Fin N) (t : Fin T) (i : Fin M) : prefixGameLoss G (t := t.val) (fun s : Fin t.val => actions ⟨s.val, lt_trans s.isLt t.isLt⟩) i = cumLoss (G.toLossSeq actions) t.val i
- Source
- TCSlib, `prefixGameLoss_eq_cumLoss`
- 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.prefixGameLoss_eq_cumLoss← prefixGameLoss_eq_cumLoss (TCSlib/LearningTheory/Minimax/HedgeInteraction.lean:275): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- prefixGameLossGiven a game $G$, a prefix of $t$ column actions, and a row $i$, the prefix cumulative loss of row $i$ is…
- ZeroSumGameA finite two-player zero-sum game with $M$ row actions and $N$ column actions is a record consisting of a payoff matrix…
- 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…
- 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
- prefixHedgeWeight_eq_hedgeWeightPrefix Hedge weight agrees with the induced-loss Hedge weight. Let $G$ be a finite two-player zero-sum game with $M$ row actions and $N$…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option relaxedAutoImplicit false inset_option autoImplicit false inopen Real Finset BigOperators in/-- The prefix game loss of row `i` over the first `t` actions of a sequence of `T` column actions equals `cumLoss` at time `t` of the loss sequence induced by that sequence. **Proof sketch.** After unfolding, both sides are sums of the loss `1 − A(i, actions s)`: the left over all `s : Fin t`, the right over the rounds `s : Fin T` with `s < t`. Apply `Finset.sum_bij` with the inclusion `s ↦ ⟨s, _⟩ : Fin t → Fin T`: it lands in the filtered index set since `s < t`, it is injective (equal underlying values), every filtered index `b < t` is the image of `⟨b, _⟩`, and the summands agree definitionally. -/lemma prefixGameLoss_eq_cumLoss {M N T : ℕ} (G : ZeroSumGame M N) (actions : Fin T → Fin N) (t : Fin T) (i : Fin M) : prefixGameLoss G (t := t.val) (fun s : Fin t.val => actions ⟨s.val, lt_trans s.isLt t.isLt⟩) i = cumLoss (G.toLossSeq actions) t.val i := by -- This identifies the recursive prefix view of the interaction with the -- `LossSeq` view expected by the generic Hedge theorem. simp only [prefixGameLoss, cumLoss, ZeroSumGame.toLossSeq] refine Finset.sum_bij (fun s (_ : s ∈ (Finset.univ : Finset (Fin t.val))) => (⟨s.val, lt_trans s.isLt t.isLt⟩ : Fin T)) ?mem ?eq ?inj ?surj · intro s _ simp only [Finset.mem_filter, Finset.mem_univ, true_and] exact s.isLt · intro s _ b _ h have hv : (⟨s.val, lt_trans s.isLt t.isLt⟩ : Fin T).val = (⟨b.val, lt_trans b.isLt t.isLt⟩ : Fin T).val := congrArg Fin.val h exact Fin.ext hv · intro b hb simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hb refine ⟨⟨b.val, hb⟩, Finset.mem_univ _, ?_⟩ exact Fin.ext rfl · intro s _ rfl