AFTD Auto-Formalizing Theoretical Domains

prefixHedgeWeight_pos

theoremverifiedimported Lean

Positivity of the prefix Hedge weight. Let $G$ be a finite two-player zero-sum game with $M$ row actions and $N$ column actions, let $\eta \in \bbr$ be a learning rate, and fix any prefix $a_0, \dots, a_{t-1}$ of $t$ column actions together with a row $i$. Then the prefix Hedge weight $w_t(i) = \exp\!\bigl(-\eta \cdot L_t(i)\bigr)$ is strictly positive, where $L_t(i) = \sum_{s=0}^{t-1}\bigl(1 - A_{i,a_s}\bigr)$ is the prefix cumulative loss of row $i$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open Real Finset BigOperators in
lemma prefixHedgeWeight_pos {M N : ℕ} (G : ZeroSumGame M N)
    (η : ℝ) {t : ℕ} (actions : Fin t → Fin N) (i : Fin M) :
    0 < prefixHedgeWeight G η actions i
Source
TCSlib, `prefixHedgeWeight_pos`
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 2
  • ZeroSumGameA finite two-player zero-sum game with $M$ row actions and $N$ column actions is a record consisting of a payoff matrix…
  • prefixHedgeWeightThe unnormalised Hedge weight of row $i$ after seeing a prefix of column actions at learning rate $\eta$ is…
Used by 2
  • prefixHedgeMixedStrategyThe normalised Hedge distribution after a prefix of $t$ column actions is the mixed row strategy with weights…
  • prefixPotential_posPositivity of the prefix potential. Let $G$ be a finite two-player zero-sum game with at least one row action, fix a learning rate…

Lean source view module on GitHub

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open Real Finset BigOperators in
/-- Every prefix Hedge weight is strictly positive, being an exponential. -/
lemma prefixHedgeWeight_pos {M N : ℕ} (G : ZeroSumGame M N)
    (η : ℝ) {t : ℕ} (actions : Fin t → Fin N) (i : Fin M) :
    0 < prefixHedgeWeight G η actions i :=
  Real.exp_pos _
See it in the graphDiscuss this resultChallenge it