Theorem 4.1, p. 16 (base case, p. 18) — along every orbit of (RL), every strictly dominated strategy becomes extinct
ProvedReinfRegGames.Extinction.theorem_4_1_dominateddominated-strategiesextinctionlearning-in-gamesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Consider a finite game in normal form, a penalty function (Definition 2.1) for every player , and an orbit , , of the reinforcement learning dynamics (RL). Let be a player and mixed strategies such that is dominated by :
Then becomes extinct along :
This is the case of Theorem 4.1 for strategies that are dominated in the original game, the base case of the paper's induction. No steepness of the penalty functions is assumed.
Formalization Note Extinction is written without a minimum: for every there is such that for every some with has ; this is the limit, not a . Every player has a penalty function because the orbit uses every player's choice map.
Preamble
import Mathlib import Definitions.Def_agt_games import Definitions.Def_ReinfRegGames_Extinction_Model
Formal statement
namespace ReinfRegGames.Extinction
theorem theorem_4_1_dominated {ι : Type*} [Fintype ι] [DecidableEq ι] {A : ι → Type*}
[∀ k, Fintype (A k)] [∀ k, DecidableEq (A k)]
(u : ι → (∀ k, A k) → ℝ) (h : ∀ k, (A k → ℝ) → ℝ) (K : ι → ℝ)
(hpen : ∀ k, IsPenalty (h k) (K k))
(y x : ℝ → ∀ k, A k → ℝ) (horb : IsRLOrbit u h y x)
(k : ι) (p p' : A k → ℝ) (hp : AGT.IsLottery p) (hp' : AGT.IsLottery p')
(hdom : ∀ z : ∀ ℓ, A ℓ → ℝ, AGT.IsMixedProfile z →
AGT.expectedPayoff u (Function.update z k p) k <
AGT.expectedPayoff u (Function.update z k p') k) :
∀ ε > 0, ∃ T : ℝ, ∀ t ≥ T, ∃ α, 0 < p α ∧ x t k α < ε := by sorry
end ReinfRegGames.Extinction
Source
Mertikopoulos & Sandholm, Learning in games via reinforcement and regularization, arXiv:1407.6267v2, p. 16, Theorem 4.1 (dominated case); proof p. 18
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.