Proposition 6.2, p. 26 — in 2-player zero-sum games with an interior equilibrium, time-averaged (RL) play converges to the Nash set
ProvedReinfRegGames.TimeAvg.proposition_6_2Let be a 2-player zero-sum game, , with finite strategy sets , and suppose has an interior Nash equilibrium (every pure strategy has positive probability under ). Let each player use a penalty function on (Definition 2.1), and let be any orbit of the reinforcement learning dynamics (RL),
Then the time average converges to the set of mixed Nash equilibria of :
The trajectory itself need not converge (in Matching Pennies it cycles, possibly hitting the boundary of the strategy space infinitely often), but its time average does. The result holds for every penalty function, steep or not, and so covers both the replicator dynamics and the projection dynamics.
Formalization Note Players are indexed by Fin 2, and is for every pure profile . Interiority is for all . Distances are those of Lean's sup metric on profiles; the Nash set contains , so the distance is to a nonempty set. (RL) is used in its differential form, equivalent to the integral form on p. 7. No steepness is assumed on the penalty functions, and strong convexity is stated for the Euclidean norm.
import Mathlib import Definitions.Def_agt_games import Definitions.Def_ReinfRegGames_Extinction_Model import Definitions.Def_ReinfRegGames_TimeAvg_TimeAverage
namespace ReinfRegGames.TimeAvg
theorem proposition_6_2 {A : Fin 2 → Type*} [∀ k, Fintype (A k)] [∀ k, DecidableEq (A k)]
(u : Fin 2 → (∀ k, A k) → ℝ) (hzs : ∀ s, u 0 s + u 1 s = 0)
(xstar : ∀ k, A k → ℝ) (hNash : AGT.IsMixedNash u xstar) (hint : ∀ k α, 0 < xstar k α)
(h : ∀ k, (A k → ℝ) → ℝ) (K : Fin 2 → ℝ) (hpen : ∀ k, ReinfRegGames.Extinction.IsPenalty (h k) (K k))
(y x : ℝ → ∀ k, A k → ℝ) (horb : ReinfRegGames.Extinction.IsRLOrbit u h y x) :
Filter.Tendsto (fun t => Metric.infDist (timeAvg x t) {z | AGT.IsMixedNash u z})
Filter.atTop (nhds 0) := by sorry
end ReinfRegGames.TimeAvg
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.