averageStrategy
defimported Lean
Given $T$ distributions $p_0, \dots, p_{T-1}$ over $\mathrm{Fin}\,n$ (each presented as non-negative weights summing to $1$) and $T > 0$, the average strategy is the mixed strategy with weights \[ \bar{p}_i \;=\; \frac{1}{T} \sum_{t=0}^{T-1} p_t(i). \]
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open Real Finset BigOperators in noncomputable def averageStrategy {n T : ℕ} [NeZero n] (hT : 0 < T) (strategies : Fin T → Fin n → ℝ) (h_nonneg : ∀ t i, 0 ≤ strategies t i) (h_sum : ∀ t, ∑ i : Fin n, strategies t i = 1) : MixedStrategy n
- Defined in
- TCSlib, `averageStrategy`
- 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.averageStrategy← averageStrategy (TCSlib/LearningTheory/Minimax/HedgeInteraction.lean:85): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Built on 1
- MixedStrategyA mixed strategy over $n$ actions is a record consisting of a weight function $w : \mathrm{Fin}\,n \to \mathbb{R}$ together with…
- Used by 2
- 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…
- hedge_constructionHedge 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…
Lean source view module on GitHub
set_option relaxedAutoImplicit false in set_option autoImplicit false in open Real Finset BigOperators in /-- The time average of `T > 0` probability distributions over `n` actions, as a mixed strategy: the weight of action `i` is `(1/T) Σ_t strategies t i`. This packages the averaged row strategy `P̄ = (1/T) Σ_t P_t` used after running Hedge for `T` rounds. [FS99, §5]. -/ noncomputable def averageStrategy {n T : ℕ} [NeZero n] (hT : 0 < T) (strategies : Fin T → Fin n → ℝ) (h_nonneg : ∀ t i, 0 ≤ strategies t i) (h_sum : ∀ t, ∑ i : Fin n, strategies t i = 1) : MixedStrategy n where weights i := (∑ t : Fin T, strategies t i) / T nonneg i := div_nonneg (Finset.sum_nonneg fun t _ => h_nonneg t i) (Nat.cast_nonneg T) sum_one := by rw [← Finset.sum_div, Finset.sum_comm] simp_rw [h_sum, Finset.sum_const, Finset.card_fin, nsmul_eq_mul, mul_one] exact div_self (Nat.cast_ne_zero.mpr (Nat.pos_iff_ne_zero.mp hT))