Stochastic Stability Analysis of Perturbed Learning Automata with Constant Step-Size in Strategic-Form Games
Georgios C. Chasparis



  





Georgios C. Chasparis 


Georgios C. Chasparis

Software Competence Center Hagenberg GmbH, Softwarepark 21, A-4232 Hagenberg, Austria

georgios.chasparis@scch.at,


Stochastic Stability Analysis of Perturbed Learning Automata with Constant Step-Size in Strategic-Form GamesThis work has been partially supported by the European Union grant EU H2020-ICT-2014-1 project RePhrase (No. 644235).
    Georgios C. Chasparis
    December 30, 2023
=================================================================================================================================================================================================================================





This paper considers a class of reinforcement-learning that belongs to the family of Learning Automata and provides a stochastic-stability analysis in strategic-form games. For this class of dynamics, convergence to pure Nash equilibria has been demonstrated only for the fine class of potential games. Prior work primarily provides convergence properties of the dynamics through stochastic approximations, where the asymptotic behavior can be associated with the limit points of an ordinary-differential equation (ODE). However, analyzing global convergence through the ODE-approximation requires the existence of a Lyapunov or a potential function, which naturally restricts the applicabity of these algorithms to a fine class of games. To overcome these limitations, this paper introduces an alternative framework for analyzing stochastic-stability that is based upon an explicit characterization of the (unique) invariant probability measure of the induced Markov chain. 





§ INTRODUCTION
 

Recently, multi-agent formulations have been utilized to tackle distributed optimization problems, since communication and computation complexity might be an issue in centralized optimization problems. 
In such formulations, decisions are usually taken in a repeated fashion, where agents select their next actions based on their own prior experience of the game. 

The present paper discusses a class of reinforcement-learning dynamics, that belongs to the large family of Learning Automata <cit.>, within the context of (non-cooperative) strategic-form games. 
In this class of dynamics, agents are repeatedly involved in a game with a fixed payoff-matrix, and they need to decide which action to play next having only access to their own prior actions and payoffs. In Learning Automata, agents build their confidence over an action through repeated selection of this action and proportionally to the reward received from this action. Naturally, it has been utilized to analyze human-like (bounded) rationality <cit.>.

Reinforcement learning has been applied in evolutionary economics, for modeling human and economic behavior <cit.>. 
It is also highly attractive to several engineering applications, since agents do not need to know neither the actions of the other agents, nor their own utility function. It has been utilized for system identification and pattern recognition <cit.>, distributed network formation and coordination problems <cit.>.

In strategic-form games, the main goal is to derive conditions under which convergence to Nash equilibria can be achieved. In social sciences, deriving such conditions may be important for justifying emergence of certain social phenomena. 
In engineering, convergence to Nash equilibria may also be desirable in distributed optimization problems, when the set of optimal solutions coincides with the set of Nash equilibria. 

In Learning Automata, deriving conditions under which convergence to Nash equilibria is achieved may not be a trivial task. In particular, there are two main difficulties: a) excluding convergence to pure strategies that are not Nash equilibria, and b) excluding convergence to mixed strategy profiles. As it will be discussed in detail in a forthcoming Section <ref>, for some classes of (discrete-time) reinforcement-learning algorithms, convergence to non-Nash pure strategies may be achieved with positive probability. Moreover, excluding convergence to mixed strategy profiles may only be achieved under strong conditions in the utilities of the agents, (e.g., existence of a potential function).

In the present paper, we consider a class of (discrete-time) reinforcement-learning algorithms introduced in <cit.> that is closely related to existing algorithms for modeling human-like behavior, e.g., <cit.>. The main difference with prior reinforcement learning schemes lies in a) the step-size sequence, and b) the perturbation (or mutations) term. The step-size sequence is assumed constant, thus introducing a fading-memory effect of past experiences in each agent's strategy. On the other hand, the perturbation term introduces errors in the selection process of each agent. 
Both these two features can be used for designing a desirable asymptotic behavior.

We provide an analytical framework for deriving conclusions over the asymptotic behavior of the dynamics that is based on an explicit characterization of the invariant probability measure of the induced Markov chain. In particular, we show that in all strategic-form games satisfying the Positive-Utility Property, the support of the invariant probability measure coincides with the set of pure strategy profiles. This extends prior work where nonconvergence to mixed strategy profiles may only be excluded under strong conditions in the payoff matrix (e.g., existence of a potential function). A detailed discussion of the exact contributions of this paper is provided in the forthcoming Section <ref>. At the end of the paper, we also provide a brief discussion over how the proposed framework can be further utilized to provide a more detailed characterization of the stochastically stable states (e.g., excluding convergence to non-Nash pure strategy profiles). Due to space limitations, this analysis is not presented in this paper.

In the remainder of the paper, Section <ref> presents a class of reinforcement-learning dynamics, related work and the main contribution of this paper. Section <ref> provides the main result of this paper (Theorem <ref>), where the set of stochastically stable states is characterized. A short discussion is also provided over the significance of this result and how it can be utilized to provide further conclusions. Finally, Section <ref> provides the technical derivation of the main result and Section <ref> presents concluding remarks.

Notation:


  * For a Euclidean topological space 𝒳⊂ℝ^n, let 𝒩_δ(x) denote the δ-neighborhood of x∈ℝ^n, i.e.,

    𝒩_δ(x) {y∈𝒳:|x-y|<δ},

where |·| denotes the Euclidean distance.

  * e_j denotes the unit vector in ℝ^n where its jth entry is equal to 1 and all other entries is equal to 0.

  * Δ(n) denotes the probability simplex of dimension n, i.e.,

    Δ(n) { x∈ℝ^n : x≥0, 1 x=1 }.






  * For some set A in a topological space , let 𝕀_A:→{0,1} denote the index function, i.e.,

    𝕀_A(x) 
    1     x∈A, 
    
    0



  * δ_x denotes the Dirac measure at x.


  * Let A be a finite set and let any (finite) probability distribution σ∈Δ(A). The random selection of an element of A will be denoted rand_σ[A]. If σ=(1/A,...,1/A), i.e., it corresponds to the uniform distribution, the random selection will be denoted by rand_ unif[A].








§ REINFORCEMENT LEARNING
	



 §.§ Terminology


We consider the standard setup of finite strategic-form games. Consider a finite set of agents (or players) ℐ = {1,...,n}, and let each agent have a finite set of actions 𝒜_i. Let α_i∈𝒜_i denote any such action of agent i. The set of action profiles is the Cartesian product 𝒜𝒜_1×⋯×𝒜_n and let α=(α_1,...,α_n) be a representative element of this set. We will denote -i to be the complementary set \i and often decompose an action profile as follows α=(α_i,α_-i). The payoff/utility function of agent i is a mapping i·:𝒜→ℝ. A strategic-form game is defined by the triple ⟨ℐ,𝒜,{i·}_i⟩. 

For the remainder of the paper, we will be concerned with strategic-form games that satisfy the Positive-Utility Property. 

[Positive Utility Property]		
For any agent i∈ℐ and any action profile α∈𝒜, iα>0.





 §.§ Reinforcement-learning algorithm


We consider a form of reinforcement learning that belongs to the general class of learning automata <cit.>. In learning automata, each agent updates a finite probability distribution x_i∈Δ(𝒜_i) representing its beliefs with respect to the most profitable action. 

The precise manner in which x_i(t) changes at time t, depending on the performed action and the response of the environment, completely defines the reinforcement learning model.

The proposed reinforcement learning model is described in Table <ref>. At the first step, each agent i updates its action given its current strategy vector x_i(t). Its selection is slightly perturbed by a perturbation (or mutations) factor λ>0, such that, with a small probability λ agent i follows a uniform strategy (or, it trembles).  At the second step, agent i evaluates its new selection by collecting a utility measurement, while in the last step, agent i updates its strategy vector given its new experience.


Here we identify actions 𝒜_i with vertices of the simplex, {e_1,...,e_𝒜_i}. For example, if agent i selects its jth action at time t, then e_α_i(t)≡ e_j. Note that by letting the step-size ϵ to be sufficiently small and since the utility function i· is uniformly bounded in 𝒜, x_i(t)∈Δ(𝒜_i) for all t. 

In case λ=0, the above update recursion will be referred to as the unperturbed reinforcement learning.




 §.§ Related work




  §.§.§ Erev-Roth type dynamics


In prior reinforcement learning in games, analysis has been restricted to decreasing step-size sequences ϵ(t) and λ=0. More specifically, in <cit.>, the step-size sequence of agent i is ϵ_i(t) = 1/(ct^ν+iα(t+1) for some positive constant c and for 0<ν<1 (in the place of the constant step size ϵ of (<ref>)). A comparative model is also used by <cit.>, with ϵ_i(t) = 1/(V_i(t)+iα(t+1)), where V_i(t) is the accumulated benefits of agent i up to time t which gives rise to an urn process 
<cit.>. Some similarities are also shared with the Cross' learning model of <cit.>, where ϵ(t)=1 and iα(t)≤1, and its modification presented in <cit.>, where ϵ(t), instead, is assumed decreasing.

The main difference of the proposed reinforcement-learning algorithm (Table <ref>) lies in the perturbation parameter λ>0 which was first introduced and analyzed in <cit.>. A state-dependent perturbation term has also been investigated in <cit.>. The perturbation parameter may serve as an equilibrium selection mechanism, since it excludes convergence to non-Nash action profiles. It resolved one of the main issues of several (discrete-time) reinforcement-learning algorithms, that is the positive probability of convergence to non-Nash action profiles under some conditions in the payoff function and the step-size sequence. 

This issue has also been raised by <cit.>. Reference <cit.> considered the model by <cit.> and showed that convergence to non-Nash pure strategy profiles can be excluded as long as c>iα for all i∈ℐ and ν=1. On the other hand, convergence to non-Nash action profiles was not an issue with the urn model of <cit.> (as analyzed in <cit.>). However, the use of an urn-process type step-size sequence significantly reduces the applicability of the reinforcement learning scheme. In conclusion, the perturbation parameter λ>0 may serve as a design tool for reinforcing convergence to Nash equilibria without necessarily employing an urn-process type step-size sequence. For engineering applications this is a desirable feature.

Although excluding convergence to non-Nash pure strategies can be guaranteed by using λ>0, establishing convergence to pure Nash equilibria may still be an issue, since it further requires excluding convergence to mixed strategy profiles. As presented in <cit.>, this can be guaranteed only under strong conditions in the payoff matrix. For example, as shown in <cit.>, excluding convergence to mixed strategy profiles requires a) the existence of a potential function, b) conditions over the second gradient of the potential function. Requiring the existence of a potential function considerably restricts the class of games where equilibrium selection can be described. Furthermore, condition (b) may not easily be verified in games of large number of players or actions. 




  §.§.§ Learning automata


Certain forms of learning automata have been shown to converge to Nash equilibria in some classes of strategic-form games. For example, in <cit.>, and for a generalized nonlinear reward-inaction scheme, convergence to Nash equilibrium strategies can be shown in identical interest games. Similar are the results presented in <cit.> for a linear reward-inaction scheme. These convergence results are restricted to games of payoffs in [0,1]. Extension to a larger class of games is possible if absolute monotonicity (cf., <cit.>) is shown (similarly to the discussion in <cit.>). 



Reference <cit.> introduced a class of linear reward-inaction schemes in combination with a coordinated exploration phase so that convergence to the efficient Nash equilibrium is achieved. However, coordination of the exploration phase requires communication between the players.

Recently, work by the author <cit.> has introduced a new class of learning automata (namely, perturbed learning automata) which can be applied in games with no restriction in the payoff matrix. Furthermore, a small perturbation factor also influences the decisions of the players, through which convergence to non-Nash pure strategy profiles can be excluded. However, to demonstrate global convergence, a monotonicity condition still needs to be established <cit.>. 




  §.§.§ Q-learning


Similar questions of convergence to Nash equilibria also appear in alternative reinforcement learning formulations, such as approximate dynamic programming methodologies and Q-learning. However, this is usually accomplished under a stronger set of assumptions, which increases the computational complexity of the dynamics. For example, the Nash-Q learning algorithm of <cit.> addresses the problem of maximizing the discounted expected rewards for each agent by updating an approximation of the cost-to-go function (or Q-values). Alternative objectives may be used, such as the minimax criterion of <cit.>. However, it is indirectly assumed that agents need to have full access to the joint action space and the rewards received by the other agents. 

More recently, reference <cit.> introduces a Q-learning scheme in combination with either adaptive play or better-reply dynamics in order to attain convergence to Nash equilibria in potential games <cit.> or weakly-acyclic games. However, this form of dynamics require that each player observes the actions selected by the other players, since a Q-value needs to be assigned in each joint action.

When the evaluation of the Q-values is totally independent, as in the individual Q-learning in <cit.>, then convergence to Nash equilibria has been shown only for 2-player zero-sum games and 2-player partnership games with countably many Nash equilibria. Currently, there are no convergent results in games in multi-player games.



  §.§.§ Payoff-based learning


The aforementioned types of dynamics can be considered as a form of payoff-based learning dynamics, since adaptation is only governed by the perceived utility of the players. Recently, there have been several attempts for establishing convergence to Nash equilibria through alternative payoff-based learning dynamics, (see, e.g., the benchmark-based dynamics of <cit.>, or the aspiration-based dynamics in <cit.>). For these type of dynamics, convergence to Nash equilibria can be established without requiring any strong monotonicity property (e.g., in multi-player weakly-acyclic games in <cit.>). However, an investigation is required with respect to the resulting convergence rates as compared to the dynamics incorporating policy iterations (e.g., the Erev-Roth type of dynamics or the learning automata discussed above).



 §.§ Objective


This paper provides an analytical framework for analyzing convergence in multi-player strategic-form games when players implement a class of perturbed learning-automata. We wish to impose no strong monotonicity assumptions in the structure of the game (e.g., the existence of a potential function). We provide a characterization of the invariant probability measure of the induced Markov chain that shows that only the pure-strategy profiles belong to its support. Thus, we implicitly exclude convergence to any mixed strategy profile (including mixed Nash equilibria). This result imposes no restrictions in the payoff matrix other than the Positive-Utility Property.











§ CONVERGENCE ANALYSIS
	



 §.§ Terminology and notation
	

Let 𝒜×Δ, where ΔΔ(𝒜_1)×…×Δ(𝒜_n), i.e., pairs of joint actions α and nominal strategy profiles x. The set 𝒜 is endowed with the discrete topology, Δ with its usual Euclidean topology, and  with the corresponding product topology. We also let () denote the Borel σ-field of , and 𝔓() the set of probability measures on () endowed with the Prohorov topology, i.e., the topology of weak convergence. The algorithm introduced in Table <ref> defines an -valued Markov chain. Let P_λ:×()→[0,1] denote its transition probability function (t.p.f.), parameterized by λ>0. We refer to the process with λ>0 as the perturbed process. Let also P:×() denote the t.p.f. of the unperturbed process, i.e., when λ=0.

We let C_b() denote the Banach space of real-valued continuous functions on  under the sup-norm (denoted by ·_∞) topology. For f∈(), define

    P_λf(z) ∫_P_λ(z,dy)f(y),

and 

    μ[f] ∫_μ(dx)f(z), μ∈𝔓().


The process governed by the unperturbed process P will be denoted by {Z_t : t≥0}. Let Ω^∞ denote the canonical path space, i.e., an element ω∈Ω is a sequence {ω(0),ω(1),…}, with ω(t)= (α(t),x(t))∈. We use the same notation for the elements (α,x) of the space  and for the coordinates of the process Z_t=(α(t),x(t)).
Let also _z[·] denote the unique probability measure induced by the unperturbed process P on the product σ-algebra of ^∞, initialized at z=(α,x), and _z[·] the corresponding expectation operator. Let also _t, 
t≥0, denote the σ-algebra generated by {Z_τ, τ≤t}.




 §.§ Stochastic stability
	

First, we note that both P and P_λ (λ>0) satisfy the weak Feller property (cf., <cit.>).
		
Both the unperturbed process P (λ=0) and the perturbed process P_λ (λ>0) have the weak Feller property.


Let us consider any sequence {Z^(k)=(α^(k),x^(k))} such that Z^(k)→Z=(α,x)∈.

For the unperturbed process governed by P(·,·), and for any open set O∈(), the following holds:

    P(Z^(k)=(α^(k),x^(k)),O)     =    ∑_α∈𝒫_(O){_Z^(k)[ rand_x_i^(k)[𝒜_i]=α_i, ∀ i∈ℐ] . ·      .∏_i=1^n_Z^(k)[ℛ_i(α,x_i^(k))∈𝒫_𝒳_i(O)] }    =    ∑_α∈𝒫_𝒜(O){∏_i=1^n𝕀_𝒫_𝒳_i(O)(ℛ_i(α,x_i^(k))) x_iα_i^(k)},

where 𝒫_𝒳_i(O) and 𝒫_𝒜(O) are the canonical projections defined by the product topology. Similarly, we have: 

    P(Z=(α,x),O)     =    ∑_α∈𝒫_𝒜(O){∏_i=1^n𝕀_𝒫_𝒳_i(O)(ℛ_i(α,x_i)) x_iα_i}.


(a) Consider the case x∈Δ^o, i.e., x belongs to the interior of Δ. For all i∈, due to the continuity of ℛ_i(·,·) with respect to its second argument, and the fact that O is an open set, there exists δ>0 such that 𝕀_𝒫_𝒳_i(O)(ℛ_i(α,x_i)) = 𝕀_𝒫_𝒳_i(O)(α,y_i)) for all y_i∈𝒩_δ(x_i). Thus, for any sequence  Z^(k)=(α^(k),x^(k)) such that Z^(k)→ Z=(α,x), we have that 
P(Z^(k),O) → P(Z,O), as k→∞.

(b) Consider the case x∈∂Δ, i.e., x belongs to the boundary of Δ.  Then, there exists i∈ such that x_i∈∂Δ(𝒜_i), i.e., there exists an action j∈_i such that x_ij=0. For any open set O∈(), x_i∉𝒫_𝒳_i(O). Furthermore, for any α_i∈ rand_x_i[_i], 𝕀_𝒫_𝒳_i(O)(ℛ_i((α_i,α_-i),x_i) = 0 (since x_ij=0 and therefore x_i cannot escape from the boundary). This directly implies that P(Z=(α,x),O)=0. Construct a sequence (α^(k),x^(k)) that converges to (α,x) such that α^(k)=α, x_iα_i^(k)>0 and x_i=e_α_i, i.e., the strategy of player i converges to the vertex of action α_i. Pick also O∈(), such that 𝕀_𝒫_𝒳_i(O)(ℛ_i(α,x_i^(k))) = 1 for all large k. This is always possible by selecting an open set O such that x∈∂𝒫_𝒳(O) and x^(k)∈𝒫_𝒳(O) for all k. In this case, lim_k→∞P(Z^(k),O) = 1. We conclude that for any sequence Z^(k)=(α^(k),x^(k)) that converges to Z=(α,x), such that x∈∂Δ, and for any open set O∈(), 
    lim_k→∞P(Z^(k),O) ≥ P(Z,O)=0.


By <cit.>, we conclude that P satisfies the weak Feller property. The same steps can be followed to show that P_λ also satisfies the weak Feller property. 

The measure μ_λ∈𝔓() is called an invariant probability measure for P_λ if

    (μ_λP_λ)(A) ∫_μ_λ(dx)P_λ(z,A) = μ_λ(A),      A∈().

Since  defines a locally compact separable metric space and P, P_λ have the weak Feller property, they both admit an invariant probability measure, denoted μ and μ_λ, respectively <cit.>.

We would like to characterize the stochastically stable states z∈ of P_λ, that is any state z∈ for which any collection of invariant probability measures {μ_λ∈𝔓():μ_λP_λ=μ_λ,λ>0} satisfies lim inf_λ→0μ_λ(z)>0. As the forthcoming analysis will show, the stochastically stable states will be a subset of the set of pure strategy states (p.s.s.) defined as follows:

	

A pure strategy state is a state s=(α,x)∈ such that for all i∈ℐ, x_i = e_α_i, i.e., x_i coincides with the vertex of the probability simplex Δ(𝒜_i) which assigns probability 1 to action α_i.



We will denote the set of pure strategy states by 𝒮.

		
There exists a unique probability vector π=(π_1,...,π_𝒮) such that for any collection of invariant probability measures {μ_λ∈𝔓():μ_λP_λ=μ_λ, λ>0}, the following hold:


  (a) lim_λ→0μ_λ(·) = μ̂(·) ∑_s∈𝒮π_sδ_s(·), where convergence is in the weak sense.

  (b) The probability vector π is an invariant distribution of the (finite-state) Markov process P̂, such that, for any s,s'∈𝒮, 

    P̂_ss'lim_t→∞ QP^t(s,𝒩_δ(s')),

for any δ>0 sufficiently small, where Q is the t.p.f. corresponding to only one player trembling (i.e., following the uniform distribution of (<ref>)).



The proof of Theorem <ref> requires a series of propositions and will be presented in detail in Section <ref>. 



 §.§ Discussion


Theorem <ref> establishes an important observation. That is, the “equivalence” (in a weak convergence sense) of the original (perturbed) learning process with a simplified process, where agents simultaneously tremble at the first iteration and then they do not tremble. This form of simplification of the dynamics has originally been exploited to analyze aspiration learning dynamics in <cit.>, and it is based upon the fact that under the unperturbed dynamics, agents' strategies will eventually converge to a pure strategy profile.

Furthermore, the limiting behavior of the original (perturbed) dynamics can be characterized by the (unique) invariant distribution of a finite-state Markov chain {P_ss'}, whose states correspond to the pure-strategy states of the game. In other words, we should expect that as the perturbation parameter λ approaches zero, the algorithm spends the majority of the time on pure strategy profiles. The importance of this result lies on the fact that no constraints have been imposed in the payoff matrix of the game other than the Positive-Utility Property <ref>. Thus, it extends to games beyond the fine set of potential games.

This convergence result can further be augmented with an ODE analysis for stochastic approximations to exclude convergence to pure strategies that are not Nash equilibria (as derived in <cit.> for the case of diminishing step size). Due to space limitations this analysis is not presented in this paper, however it can be the subject of future work. 





§ TECHNICAL DERIVATION
	





 §.§ Unperturbed Process
	

For t≥0 define the sets

    A_t   {ω∈Ω:α(τ)=α(t) ,  for all τ≥ t } ,
    
    B_t   {ω∈Ω:α(τ)=α(0) ,  for all  0≤τ≤t} .

Note that {B_t:t≥0} is a non-increasing sequence, i.e., B_t+1⊆ B_t, while {A_t:t≥0} is non-decreasing, i.e., A_t+1⊇ A_t. Let

    A_∞⋃_t=0^∞A_t B_∞⋂_t=1^∞B_t.

In other words, the set A_∞ corresponds to the event that agents eventually play the same action profile, while B_∞ corresponds to the event that agents never change their actions. 

	
Let us assume that the step size ϵ>0 is sufficiently small such that 0<ϵ u_i(α)<1 for all α∈𝒜 and for all agents i∈ℐ. Then, the following hold: 


  (a) inf_z∈ ℙ_z[B_∞]>0, 

  (b) inf_z∈_z[A_∞]=1.



The first statement of Proposition <ref> states that the probability that agents never change their actions is bounded away from zero, while the second statement states that the probability that eventually agents play the same action profile is one.

(a) Let us consider an action profile α=(α_1,...,α_n)∈𝒜, and an initial strategy profile x(0)=(x_1(0),...,x_n(0)) such that x_iα_i(0)>0 for all i∈ℐ. Note that if the same action profile α is selected up to time t, then the strategy of agent i satisfies:

    x_i(t) = e_α_i - (1-ϵ u_i(α))^t(e_α_i-x_i(0)).

Given that B_t is non-increasing, from continuity from above we have

    _z[B_∞] = lim_t→∞_z[B_t] = lim_t→∞∏_k=0^t∏_i=1^nx_iα_i(k).

Note that [B_∞] > 0 if and only if 

    ∑_t=1^∞log(x_iα_i(t)) > -∞.

Let us introduce the variable 
    y_i(t)  1-x_iα_i(t) = ∑_j∈𝒜_i\α_ix_ij(t),
 which corresponds to the probability of agent i selecting any action other than α_i. Condition (<ref>) is equivalent to

    -∑_t=0^∞log(1-y_i(t)) < ∞,	 i∈ℐ.

We also have that 

    lim_t→∞-log(1-y_i(t))/y_i(t) = lim_t→∞1/1-y_i(t) > ρ

for some ρ>0, since 0≤ y_i(t) ≤ 1. Thus, from the Limit Comparison Test, we conclude that condition (<ref>) holds if and only if ∑_t=1^∞y_i(t) < ∞, for each i∈ℐ.

Lastly, note that y_i(t+1)/y_i(t) = 1-ϵ u_i(α). By Raabe's criterion, the series ∑_t=0^∞y_i(t) is convergent if lim_t→∞t(y_i(t)/y_i(t+1) - 1 ) > 1.
We have

    t(y_i(t)/y_i(t+1)-1) = tϵ u_i(α)/1-ϵ u_i(α).

Thus, if ϵ u_i(α)<1 for all α∈𝒜 and i∈ℐ, then 1-ϵ u_i(α)>0 and 

lim_t→∞t(ϵ u_i(α)/1-ϵ u_i(α)) > 1,

which implies that the series ∑_t=1^∞y_i(t) is convergent. Thus, we conclude that _z[B_∞]>0.

(b) Define the event

    C_t {∃α'≠α(t):x_iα_i'(t)>0,  i∈ℐ},

i.e., C_t corresponds to the event that there exists an action profile different from the current action profile for which the nominal strategy assigns positive probability for all agents i. Note that A_t^c ⊆ C_t, since A_t^c occurs only if there is some action profile α'≠α(t) for which the nominal strategy assigns positive probability. This further implies that _z[A_t^c]≤_z[C_t]. Then, we have:

    _z[A_t+1|A_t^c]    =    _z[A_t+1∩ A_t^c]/_z[A_t^c]   ≥   _z[A_t+1∩ A_t^c]/_z[C_t]
    
       ≥   _z[A_t+1∩ A_t^c|C_t]     =    _z[{α(τ)=α'≠α(t),∀τ>t}|C_t]    ≥   inf_α'≠α∏_i=1^nx_iα_i'(t)∏_k=t+1^∞{1-(1-ϵiα')^k-t-1c_i(α')}   ≥   inf_α'≠α∏_i=1^nx_iα_i'(t)∏_k=0^∞{1-(1-ϵiα')^kc_i(α')}

where c_i(α') 1 - x_iα_i'(t) ≥ 0. We have already shown in part (a) that the second part of the r.h.s. is bounded away from zero. Therefore, we conclude that _z[A_t+1|A_t^c]>0. Thus, from the counterpart of the Borel-Cantelli Lemma, _z[A_∞]=1. 

The above proposition is rather useful in characterizing the support of any invariant measure of the unperturbed process, as the following proposition shows.

	
Let μ denote an invariant probability measure of P. Then, there exists a t.p.f. Π on ×() such that 


  (a) for μ-a.e. z∈, Π(z,·) is an invariant probability measure for P;

  (b) for all f∈(), lim_t→∞P^tf-Π f_∞=0;

  (c) μ is an invariant probability measure of Π;

  (d) the support[The support of a measure μ on  is the unique closed set F⊂() such that μ(\F)=0 and μ(F∩O)>0 for every open set O⊂ such that F∩O≠∅.] of Π is on 𝒮 for all z∈.



The state space  is a locally compact separable metric space and the t.p.f. of the unperturbed process P admits an invariant probability measure due to Proposition <ref>. Thus, statements (a), (b) and (c) follow directly from <cit.>. 

(d) Let us assume that the support of Π includes points in  other than the pure strategy states. Let also O⊂ be an open set such that O∩=∅ and Π(z^*,O)>0 for some z^*∈. Given that P^t converges weakly to Π as t→∞, from Portmanteau theorem (cf., <cit.>), we have that 
    lim inf_t→∞ P^t(z^*,O) ≥Π(z^*,O)>0.
 This is a contradiction of Proposition <ref>(b). Thus, the conclusion follows. 








Proposition <ref> states that the limiting unperturbed t.p.f. converges weakly to a t.p.f. Π which accepts the same invariant p.m. as P. Furthermore, the support of Π is the set of pure strategy states 𝒮. This is a rather important observation, since the limiting perturbed process can also be “related” (in a weak-convergence sense) to the t.p.f. Π, as it will be shown in the following section.




 §.§ Decomposition of perturbed t.p.f.
		

We can decompose the t.p.f. of the perturbed process as follows:

    P_λ = (1-φ(λ))P + φ(λ)Q_λ
 where φ(λ) = 1-(1-λ)^n is the probability that at least one agent trembles (since (1-λ)^n is the probability that no agent trembles), and Q_λ corresponds to the t.p.f. induced by the one-step reinforcement-learning update when at least one agent trembles. Note that φ(λ)→0 as λ→0. 

Define also Q to be the t.p.f. when only one players trembles, and Q^* is the t.p.f. where at least two players tremble. Then, we may write:

    Q_λ = (1-ψ(λ))Q + ψ(λ)Q^*,

where ψ(λ)  1-nλ/1-(1-λ)^n corresponds to the probability that at least two players tremble given that at least one player trembles. 

Let us also define the infinite-step t.p.f. when trembling only at the first step (briefly, lifted t.p.f.) as follows: 

    P_λ^Lφ(λ)∑_t=0^∞(1-φ(λ))^tQ_λP^t = Q_λR_λ

where

R_λφ(λ)∑_t=0^∞(1-φ(λ))^tP^t,

i.e., R_λ corresponds to the resolvent t.p.f.


		
The following hold:


  (a) For f∈(), lim_λ→0R_λf-Πf_∞ = 0.

  (b) For f∈(), lim_λ→0P_λ^Lf-QΠf_∞ = 0.

  (c) Any invariant distribution μ_λ of P_λ is also an invariant distribution of P_λ^L.

  (d) Any weak limit point in 𝔓() of μ_λ, as λ→0, is an invariant probability measure of QΠ.




(a) For any f∈ C_b(), we have

    R_λf - Πf_∞    =    φ(λ)∑_t=0^∞(1-φ(λ))^tP^tf - Π f    =    φ(λ)∑_t=0^∞(1-φ(λ))^t(P^t f - Π f)

where we have used the property φ(λ)∑_t=0^∞(1-φ(λ))^t=1. Note that

    φ(λ)∑_t=T^∞(1-φ(λ))^tP^tf-Π f   ≤    (1-φ(λ))^Tsup_t≥TP^tf - Π f.

From Proposition <ref>(b), we have that for any δ>0, there exists T=T(δ)>0 such that the r.h.s. is uniformly bounded by δ for all t≥ T. Thus, the sequence 
    A_Tφ(λ)∑_t=0^T(1-φ(λ))^t(P^tf - Π f)
 is Cauchy and therefore convergent (under the sup-norm). In other words, there exists A∈ℝ such that 
    lim_T→∞A_T-A=0.
 
For every T>0, we have

    R_λf-Πf≤A_T + A - A_T.

Note that 

    A_T≤φ(λ) ∑_t=0^T (1-φ(λ))^tP^t f-Π f.

If we take λ↓0, then the r.h.s. converges to zero. Thus,

    R_λf-Πf_∞≤A-A_T,  T>0,

which concludes the proof.

(b) For any f∈ C_b(), we have

    P_λ^Lf-QΠf_∞   ≤   Q_λ(R_λf-Πf)_∞ + Q_λΠf - QΠf_∞   ≤   R_λf-Πf_∞ + Q_λΠf-QΠf_∞.

The first term of the r.h.s. approaches 0 as λ↓0 according to (a). The second term of the r.h.s. also approaches 0 as λ↓0 since Q_λ→Q as λ↓0.

(c) Note that, by definition of the perturbed t.p.f. P_λ, we have

    P_λR_λ = (1-φ(λ))PR_λ + φ(λ)Q_λR_λ.

Note further that Q_λR_λ=P_λ^L and 
    (1-φ(λ))PR_λ = R_λ - φ(λ)I,
 where I corresponds to the identity operator. Thus, we have

    P_λR_λ = R_λ-φ(λ)I+φ(λ)P_λ^L.

For any invariant probability measure of P_λ, μ_λ, we have

    μ_λP_λR_λ = μ_λR_λ-φ(λ)μ_λ+φ(λ)μ_λP_λ^L,

which equivalently implies that 

    μ_λ = μ_λP_λ^L,

since μ_λP_λ = μ_λ. Thus, we conclude that μ_λ is also an invariant p.m. of P_λ^L.

(d) Let μ̂ denote a weak limit point of μ_λ as λ↓0. To see that such a limit exists, take μ̂ to be an invariant probability measure of P. Then, 

    P_λf-Pf_∞   ≥   μ_λ(P_λf-Pf)_∞    =    (μ_λ-μ̂)(I-P)[f]_∞.
 
Note that the weak convergence of P_λ to P, it necessarily implies that μ_λ⇒μ̂. Note further that

    μ̂[f] - μ̂QΠf    =     (μ̂[f]-μ_λ[f]) + μ_λ[P_λ^Lf-QΠf]+        (μ_λ[QΠf]-μ̂[QΠf]).

The first and the third term of the r.h.s. approaches 0 as λ↓0 due to the fact that μ_λ⇒μ̂. The same holds for the second term of the r.h.s. due to part (b). Thus, we conclude that any weak limit point of μ_λ as λ↓0 is an invariant p.m. of QΠ. 




 §.§ Invariant p.m. of one-step perturbed process
	

Define the finite-state Markov process P̂ as in (<ref>). 

		
There exists a unique invariant probability measure μ̂ of QΠ. It satisfies 

    μ̂(·) = ∑_s∈𝒮π_sδ_s(·)

for some constants π_s≥0, s∈𝒮. Moreover, π=(π_1,...,π_𝒮) is an invariant distribution of P̂, i.e., π=πP̂.



From Proposition <ref>(d), we know that the support of Π is on the set of pure strategy states 𝒮. Thus, the support of QΠ is also on 𝒮. From Proposition <ref>, we know that QΠ admits an invariant measure, say μ̂, whose support is also 𝒮. Thus, μ̂ admits the form of (<ref>), for some constants π_s≥0, s∈𝒮.

Note also that 𝒩_δ(s') is a continuity set of QΠ(s,·), i.e., QΠ(s,∂𝒩_δ(s'))=0. Thus, from Portmanteau theorem, given that QP^t⇒ QΠ, 
    QΠ(s,𝒩_δ(s')) = lim_t→∞QP^t(s,𝒩_δ(s')) = P̂_ss'.
  If we also define π_s μ̂(𝒩_δ(s)), then

    π_s' = μ̂(𝒩_δ(s')) = ∑_s∈𝒮π_s QΠ(s,𝒩_δ(s')) = ∑_s∈𝒮π_sP̂_ss',
 which shows that π is an invariant distribution of P̂, i.e., π=πP̂.

It remains to establish uniqueness of the invariant distribution of QΠ. Note that the set 𝒮 of pure strategy states is isomorphic with the set 𝒜 of action profiles. If agent i trembles (as t.p.f. Q dictates), then all actions in 𝒜_i have positive probability of being selected, i.e., Q(α,(α_i',α_-i))>0 for all α_i'∈𝒜_i and i∈. It follows by Proposition <ref> that QΠ(α,(α_i',α_-i))>0 for all α_i'∈𝒜_i and i∈. Finite induction then shows that (QΠ)^n(α,α')>0 for all α,α'∈. It follows that if we restrict the domain of QΠ to 𝒮, it defines an irreducible stochastic matrix. Therefore, QΠ has a unique invariant distribution. 




 §.§ Proof of Theorem <ref>
	

Theorem <ref>(a)–(b) is a direct implication of Propositions <ref>–<ref>.






















































































































































































































































































§ CONCLUSIONS & FUTURE WORK
    

In this paper, we considered a class of reinforcement-learning algorithms that belong to the family of learning automata, and we provided an explicit characterization of the invariant probability measure of its induced Markov chain. Through this analysis, we demonstrated convergence (in a weak sense) to the set of pure-strategy states, overcoming prior restrictions necessary under an ODE-approximation analysis, such as the existence of a potential function. Thus, we opened up new possibilities for equilibrium selection through this type of algorithms that goes beyond the fine class of potential games.

Although the set of pure-strategy-states (which are the stochastically-stable states) may contain non-Nash pure strategy profiles, a follow-up analysis that excludes convergence to such pure-strategy-states may be performed (similarly to the analysis presented in <cit.> for diminishing step size).


IEEEtran


