Theorem 6.1, p. 25 — in 2-player games, bounded score differences make the time average of an (RL) orbit converge to the Nash set
ProvedReinfRegGames.TimeAvg.theorem_6_1Let be a 2-player game with finite strategy sets and payoffs , let each player use a penalty function (Definition 2.1), and let be an orbit of (RL), . Suppose the score differences remain bounded: there is with
Then has a Nash equilibrium, and the time average converges to the set of mixed Nash equilibria:
This is the reinforcement-learning analogue of the classical result that interior replicator trajectories of 2-player games have time averages converging to the Nash set; bounded score differences replace "staying away from the boundary".
Formalization Note Players are indexed by Fin 2; the page states and proves the result only for 2-player games (the proof uses that is linear in the single opponent's strategy). Distances are those of Lean's sup metric on profiles. Because the distance to the empty set is in Lean, the conclusion includes explicitly that the Nash set is nonempty, which is what the page's proof shows (the ω-limit set of is nonempty and consists of Nash equilibria); without it the convergence statement would hold vacuously for a game without equilibria.
import Mathlib import Definitions.Def_agt_games import Definitions.Def_ReinfRegGames_Extinction_Model import Definitions.Def_ReinfRegGames_TimeAvg_TimeAverage
namespace ReinfRegGames.TimeAvg
theorem theorem_6_1 {A : Fin 2 → Type*} [∀ k, Fintype (A k)] [∀ k, DecidableEq (A k)]
(u : Fin 2 → (∀ k, A 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)
(hbdd : ∃ M : ℝ, ∀ t, 0 ≤ t → ∀ k (α β : A k), |y t k α - y t k β| ≤ M) :
{z : ∀ k, A k → ℝ | AGT.IsMixedNash u z}.Nonempty ∧
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.