{'fraction_non_alphanumeric': 0.05803754802232585, 'fraction_numerical': 0.01152535820426704, 'mean_word_length': 3.8215284249767008, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 15, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Algorithms for Nash Equilibria in General-Sum Stochastic Games

Over the past few decades the quest for algorithms to compute Nash equilibria in general-sum stochastic games has intensified and several important algorithms (cf. [7,9,12,16]) have been proposed. However, they suffer from either lack of generality or are intractable for even medium sized problems or both. In this paper, we first formulate a non-linear optimization problem for stochastic games and then break it down into simpler sub-problems that ensure there is no Bellman error for a given state and agent. Next, we derive a set of novel necessary and sufficient conditions for solution points of these sub-problems to be Nash equilibria of the underlying game. Using these conditions, we develop two novel algorithms - OFF-SGSP and ON-SGSP,respectively. OFF-SGSP is an off-line centralized algorithm which assumes complete information of the game. On the other hand, ON-SGSP is an online decentralized algorithm that works with simulated transitions of the stochastic game. Both algorithms are guaranteed to converge to Nash equilibrium strategies for general-sum (discounted) stochastic games.


Introduction
Game theoretic approaches have been useful for analyzing multi-agent scenarios. Since the seminal work of Shapley [22], stochastic games have been an important class of models for multi-agent systems, with important applications in oligopolistic economics. In the past, zero-sum stochastic games have been modelled and solved for Nash equilibria using the standard techniques of Markov decision processes. General-sum stochastic games, on the contrary, have posed a difficulty and the quest for algorithms to compute Nash equilibria in this setting has intensified over the past few decades. Some important algorithms in this direction are stochastic tracing procedure [9], NashQ [12], FFQ [16], and their generalised representations such as the optimization problem formulations for various reward structures [7]. However, these suffer either from lack of generality or are intractable for even medium sized problems or both.
In our quest for deriving algorithms for stochastic games, we start with a non-linear optimization problem and then provide a characterization of those solution points which correspond to Nash equilibria of the underlying game. As a result, we also derive a set of necessary and sufficient conditions, henceforth referred to as SG-SP (Stochastic Game -Sub-Problem) conditions. These are obtained by breaking down the main optimization problem into several sub-problems. Each sub-problem can be seen as ensuring no Bellman error, for a particular choice of the state x ∈ S and agent i ∈ {1, . . . , N }, where S is the state space and N is the number of agents of the stochastic game considered. We also establish the kinship of these conditions to KKT conditions for the sub-problems.
Using SG-SP conditions, we propose two algorithms, OFF-SGSP and ON-SGSP, respectively. Here OFF-SGSP is an off-line iterative algorithm that works in a centralized setting and assumes complete information of the game in order to compute a Nash equilibrium strategy. On the other hand, ON-SGSP is an on-line decentralized algorithm which does not require any knowledge of the structure of the state transition or the reward schemes. Here the system model can be described as in Figure 1. The learning is localized to each agent with one instance of ON-SGSP running in each agent. Each agent presents its action to the environment and gets its reward and the next state. We provide a formal proof of convergence that both our algorithms converge to Nash equilibrium strategies, in the supplementary material. Related Work The field of stochastic games has been actively pursued over the last seven decades with several important applications in economics. Many problems like Fishery games, Advertisement games and several oligopolistic situations can be modelled as stochastic games [7,18,19,20,2]. A comprehensive treatment of stochastic games under various pay-off criteria is given by Filar and Vrieze [7]. Singh et al. [23] observed that in a two-agent iterated general-sum game, Nash convergence is assured either in strategies or in the very least in average payoffs. Later by Hu and Wellman [11], stochastic game framework was seen as an extension of the well studied Markov decision theory [3] to multi-agent scenarios. An interesting Q-learning algorithm based on reinforcement learning (RL) [4,24], has been proposed by Hu and Wellman [11] for general-sum games. An extension, NashQ, to the above algorithm was proposed by Hu and Wellman [12] which showed improvement in performance. However, the algorithm of Hu and Wellman [11] as well as NashQ assure convergence only if the game has exactly one Nash equilibrium. Littman [16] proposed a friend-or-foe Q-learning (FFQ) algorithm as an improvement over the NashQ algorithm with assured convergence, though not necessarily to a Nash equilibrium. Moreover, the FFQ algorithm is applicable to a restricted class of games where either full co-operation between agents is ensured or the game is zero-sum. Zinkevich et al. [26] show that the traditional Q-learning approach need not be sufficient to compute a Nash equilibrium for a typical general-sum stochastic game. Mac Dermed and Isbell [17] formulate intermediate optimization problems, called Multi-Objective Linear Programs (MOLPs), to compute Nash equilibria as well as Pareto optimal solutions. However, their algorithm is tractable only for small sized problems. Herings and Peeters [9] propose an algorithm, where a homotopic path between equilibrium points of N independent MDPs and the N player stochastic game in question, is traced numerically. This, in turn, gives a Nash equilibrium point of the stochastic game of interest. However, this approach is off-line with a computational complexity that is exponential in N .
A popular algorithm with guaranteed convergence to Nash equilibrium in general-sum stochastic games is rational learning, proposed by [13]. In their algorithm, each agent i maintains a prior on what he believes to be other agents' strategy and updates it in a Bayesian manner. Combining this with certain assumptions of absolute continuity and grain of truth, the algorithm there is shown to converge to Nash equilibrium. Our decentralized algorithm, ON-SGSP, operates in a similar setting as that considered by [13], with the exception that the knowledge of reward functions is not assumed. The strategy of any agent in ON-SGSP does not depend upon Bayesian estimates of other agents' strategies and hence, the absolute continuity/grain of truth assumptions from [13] do not apply. Instead, adopting the ordinary differential equations (ODEs) approach, we provide a novel proof of (asymptotic) convergence of our algorithms to Nash equilibrium.
A more recent approach for the computation of Nash equilibria is given by Akchurina [1]. The approach adopted there is to solve a system of ODEs using numerical methods. This is unlike some of the multi-agent RL type algorithms mentioned above, which use dynamic programming principles in arriving at a Nash strategy. Further, a system of ODEs given by Akchurina [1], also found in [25, pp. 189], turns out to be similar to a portion of the system of ODEs that are tracked by our algorithms. Though their experiments do show convergence in a large group of randomly generated games, unlike us, a formal proof of convergence is not provided.

Formal Definitions
A stochastic game can be seen to be an extension of the single-agent Markov decision process. A discounted reward stochastic game is described by a tuple < N, S, A, p, r, β >, where N represents the number of agents, S denotes Environment 1 2 . . . N

ON-SGSP
Action, a Reward vector r, next state y is the Cartesian product of action spaces of individual agents when the state of the game is x ∈ S. Further, p(y|x, a) denotes the probability of going from the current state x ∈ S to y ∈ S when the vector of actions a ∈ A(x) (of the N players) is chosen and r(x, a) = r i (x, a) : i = 1, 2, . . . , N denotes the vector of reward functions of all agents when the state is x ∈ S and the vector of actions a ∈ A(x) is chosen. Also, 0 < β < 1 denotes the discount factor.
We assume that the game is in normal form, i.e., in any given state x ∈ S, all agents act simultaneously with an action vector a ∈ A(x) resulting in transition to the next state y ∈ S according to the transition probability p(y|x, a). In other words, no agent gets to know what the other agents' actions are before selecting its own action.
A strategy π i n of the i th player prescribes the action to be performed in each state at the n th time instant by that player. We denote by π i n (·) the action prescribed for the i th agent by the strategy π i n at the n th time instant. The quantity '·' in π i n (·), in general, corresponds to the entire history of states and actions of all agents up to the (n − 1) st instant and the current system state at the n th instant. Let the set of all possible strategies for the i th player be denoted by F i . A strategy π i n is said to be a Markov strategy if π i n depends only on the current state x n ∈ S at time n, and may in general vary with n (i.e., could prescribe a different action, for the same state, at different times). Thus, for a Markov strategy, π i n (x) ∈ A i (x), ∀n ≥ 0, x ∈ S, i = 1, 2, . . . , N . If the action chosen in any state for a Markov strategy π i n is independent of the time instant n, viz., π i n ≡ π i , ∀n ≥ 0, i = 1, 2, . . . , N , then the strategy is said be stationary.
Let P (A(x)) (resp. P A i (x) ) denote the set of all probability measures on A(x) (resp. A i (x)). A randomized Markov strategy is specified via the sequence of maps φ i n : S → P A i (x) , x ∈ S, n ≥ 0, i = 1, 2, . . . , N . Thus, φ i n (x) is a distribution on the set of actions A i (x) and in general depends on n. We say that φ i n is a stationary randomized strategy or simply a randomized strategy for player i if φ i n ≡ φ i . By an abuse of notation, we denote by π ≡ π 1 , π 2 , . . . , π N , a stationary randomized strategy that we also (many times) call a strategy, since from now on, we shall only work with randomized strategies.
Notation. · · · represents a column vector and 1 m is a vector of ones with m elements. The various constituents of the stochastic game considered are denoted as follows: 1. Action: a = a 1 , a 2 , . . . , a N ∈ A(x) is the aggregate action, a −i is the action vector of all agents except agent i and is the randomized policy vector in state x ∈ S for the agent i, π i = π i (x) : x ∈ S , π = π i : i = 1, 2, . . . , N is the strategy-tuple and π −i = π j : j = 1, 2, . . . , N, j = i is the strategy-tuple of all agents except agent i.
3. Transition Probability: π i (x, a i ) represents the Markov transition probability from state x ∈ S to state y ∈ S when each agent i plays according to its randomized strategy π i , is the marginal transition probability from state x to y, x, y ∈ S, when action a i ∈ A i (x) is chosen by agent i when other agents play their respective strategies. 4. Reward: r i (x, a) is the single-stage reward obtained by agent i in state x ∈ S, where a ∈ A(x) is the aggregate action taken, is the marginal reward to agent i for picking action a i ∈ A i (x) when other agents are playing according to their respective (randomized) strategies.
We make the following assumption about the existence of stationary equilibria: Assumption 1. A Nash equilibrium in stationary randomized strategies exists for general-sum discounted stochastic games.
We shall refer to such stationary randomized strategies as Nash strategies. The above assumption is similar to Filar and Vrieze [7, Theorem 3.8.1, pp. 130] and is used in order to arrive at conditions that characterize the Nash equilibrium solution points of an optimization problem that we formulate subsequently.

Remark 1.
While stationary equilibria are known to exist for two player games, the same is not true in general for any N ≥ 2. Flesch et al. [8] showed that there exist 3 player stochastic games where no stationary equilibria exist. The focus in this work is to design novel algorithms that converge to stationary strategies (when they are known to exist) and we do not handle the question of existence of equilibria in a general stochastic game. The reader is referred to Filar and Vrieze [7,Part II] for an in-depth discussion on this topic.

Problem Formulation
Here we generalize the non-linear optimization problem formulated in Filar and Vrieze [7] for two agents, whose solution gives Nash equilibria of the underlying game. Next, we form sub-problems from the main optimization problem and derive a set of necessary and sufficient conditions that corresponding to Nash equilibria of the underlying stochastic game.

An Optimization Problem:
The objective is to obtain the value function for all agents such that in any state x, the value of each agent is equal to the maximum of the sum of single stage reward and the discounted expected value of the next state, averaged over the other agents' strategies. The latter operation, i.e., of averaging over the other agents' strategies, is done naturally because each agent i selects actions there using its randomized strategy π i , i = 1, . . . , N . Thus, given the knowledge of the other agents (randomized) strategies, agent i would select a strategy to maximize its expected pay-off.
Then, the optimization problem is given by s.t. ∀x ∈ S, i = 1, 2, . . . , N, In the above, U (x) ⊆ S denotes the set of all possible next states when the current state is x ∈ S, v i (x) denotes the value of state x ∈ S for agent i, v i = v i (y) : y ∈ S denotes the value vector for agent i (over all states) and v = v i : i = 1, 2, . . . , N the vector of value vectors of all agents. Prasad and Bhatnagar [21] consider a similar optimization problem as (1) and derive a set of verifiable necessary and sufficient conditions that they call KKT-SP conditions (see Appendix A for a description). We however derive an alternative easier set of conditions that we call SG-SP (Stochastic Game -Sub-Problem) conditions. SG-SP conditions will also be shown to be necessary and sufficient for Nash equilibrium of the underlying stochastic game.
Sub-problems of (1): We form sub-problems from the main optimization problem (1) along the lines of [21], for each state x ∈ S and each agent i ∈ {1, 2, . . . , N }. The sub-problems are formed with the objective of ensuring that there is no Bellman error (see g i x,z (θ) below). Let m = |A i (x)|. Then, the sub-problems are formulated as follows: For all x ∈ S and i ∈ {1, 2, . . . , N } where, The Lagrangian corresponding to (2) can be written as where λ z and δ z are the Lagrange multipliers and s z and t z , z = 1, 2, . . . , m are the slack variables, corresponding to the first and second constraint of the sub-problem (2), respectively. While Prasad and Bhatnagar [21] proposed certain KKT-SP conditions for N = 2, we generalize them next and also derive a simpler set of SG-SP conditions in our setting. (1) and for every sub-problem, i.e., for all x ∈ S and i ∈ {1, 2, . . . , N }

SG-SP conditions:
The above conditions, which define a point to be an SG-SP point, are called SG-SP conditions. The connection between SG-SP points and Nash equilibria of the underlying game can be seen intuitively as follows: Recall that the objective of the sub-problem is to ensure that there is no Bellman error, which in turn implies that the value estimates (v) are correct with respect to the policy (π) of all agents. The feasibility requirement above then ensures that players rationality constraints are met (no player wishes to change policies). In this light, the main result below states that the pair of value-function and the policy tuple (v * , π * ) is Nash if and only if the value-function is correct and the joint-policy is an equilibrium with respect to the value function. Theorem 2 (Nash ⇔ SG-SP). A strategy π * is Nash if and only if (v * , π * ) for the corresponding optimization problem (1) is an SG-SP point.
As a consequence of the above, a simpler set of necessary and sufficient conditions for Nash equilibrium can be used as compared to KKT-SP conditions proposed by [21] (for N = 2). Before proceeding onto the algorithms, we would like to remark here that, unlike KKT-SP points, SG-SP points do not impose a linear independence requirement to ensure they are Nash points (see Appendix A for a detailed discussion).

An offline algorithm (OFF-SGSP) for Nash equilibria
The analysis of the previous section suggests that it is sufficient to find an SG-SP point in order to compute Nash strategies of the underlying stochastic game. We now derive a descent direction for both our algorithms using this fact about SG-SP points.
For every sub-problem, substitute and eliminate λ z = p z and δ z = −g i x,z (θ), z = 1, 2, . . . , m. Then, complementary slackness conditions for optimality in the sub-problems reduce to SG-SP conditions. Further, differentiating the Lagrangian (3) of the sub-problem w.r.t. the slack variable t z and equating it to zero, we obtain , is an ascent direction in p z along the Lagrangian k. Since our aim is to minimize the objective, we need to descend in p z . Thus, √ p z g i x,z (θ) is a possible candidate for descent direction in p z along the Lagrangian k. The following proposition makes this claim precise.
in the objective of the main optimization problem (1). Here g i x,a i (v i , π −i ) ≤ 0 represents the first constraint in (1). Later it will be shown that the direction suggested in Proposition 3 is the key to convergence to a Nash strategytuple. Combining the above with extension of value iteration [3,24] type schemes for on-policy computation of v, we propose first an off-line algorithm, that we call OFF-SGSP, for the computation of an SG-SP point. This algorithm assumes the knowledge of the transition dynamics p and reward structure r of the underlying stochastic game. Further, it operates in a centralized setting.

Algorithm 1 OFF-SGSP Input:
The underlying general-sum stochastic game (N, S, A, p, r, β), step-sizes {b(n), c(n)} n≥1 , initial point The perturbation of the policy is performed every Q iterations in order to push the policy π out of the domain of attraction of any local equilibrium.
Further, b(n) c(n) → 0 as n → ∞. These requirements on the step-sizes are standard stochastic approximation conditions and in particular, ensure that the π-recursion proceeds on a slower timescale in comparison to the v-recursion.

An online (decentralized) algorithm (ON-SGSP) for Nash equilibria
Though OFF-SGSP is suitable for only off-line learning of Nash strategies, it is amenable for extension to the general on-line setting where neither the transition probability p nor the reward function r are explicitly known. ON-SGSP uses the stochastic game as a generative model and is a stochastic approximation algorithm that is in the spirit of reinforcement learning approaches for MDPs. The value v update can be seen to be similar to an on-policy value iteration used in MDPs where the reward and transition probability structures are not known. However, the novelty lies in its extension to the multi-agent setting with policy π update scheme shown to converge to Nash strategies for the underlying general-sum stochastic game.
, number of iterations to run M >> 0 and pickAtRandom(·), for picking an action according to randomized policy Output: Play action a i along with other agents in current state x ∈ S to get environment response as next state y ∈ S and reward r i ∈ R.
Note that, unlike OFF-SGSP, the above algorithm is a decentralized reinforcement learning scheme with learning localized to each agent i ∈ {1, 2, . . . , N }. Every iteration in algorithm 2 represents a discrete-time instant of transaction with the environment. We assume that the environment synchronizes all agents' iterations. Each agent learns his policy π i according to algorithm 2 and the theoretical convergence guarantees given subsequently establish that a Nash equilibrium for the underlying general-sum discounted stochastic game will be attained.

Remark 2. It was shown in Proposition 3 that
can also be seen to be a descent direction in π i (x, a i ) for every i = 1, 2, . . . , N, x ∈ S, a i ∈ A i (x). So, the policy updates in algorithms 1 and 2 can be generalized to However, per-iteration complexity alone is not sufficient and an analysis of the number of iterations required is necessary to complete the picture. However, convergence rate results for general multi-timescale stochastic approximation schemes are not available, see however, [14] for rate results of two timescale schemes with linear recursions.

Remark 4.
We would also like to point out that our algorithms are not proven to find Nash equilibrium of a stochastic game in polynomial time and hence, do not contradict existing game-theoretic complexity results. A well-known result in this context is that finding the Nash equilibrium of a two player (or even N player) game is PPAD-complete.

Outline of Convergence Proof
We provide here a sketch of the convergence analysis of the two proposed algorithms. For both the algorithms, we assume that the underlying Markov chain with transition probabilities p(y|x, π), x, y ∈ S, corresponding to the general-sum discounted stochastic game, is irreducible and positive recurrent for all possible strategies π.
Both our algorithms employ two time-scale stochastic approximation [5,Chapter 6]. That is, they comprise of iteration sequences that are updated using two different time-scales or step-size schedules defined via {b(n)} and {c(n)}, respectively. Here, {c(n)} is the faster of the two schedules that is used for update of the value v while the slower time-scale {b(n)} is used to update π. Hence, π appears quasi-static for updates of v. On the other hand, for updates of π, v seems to have converged to v π which is the value v given a particular π. Convergence analyses of the three algorithms involve the following steps: 1. We first show that the updates of v, that are on the faster time-scale, converge to a limit point of the following system of ODEs:∀x ∈ S, i = 1, 2, . . . , N, where π is assumed to be time-invariant. We will also see that the system of ODEs above has a unique limit point, henceforth referred to as v π , which is stable. 2. Next, using the converged values of v corresponding to strategy update π n , i.e., v πn on the slower timescale, we show that updates of π converge to a limit point of the following system of ODEs:∀a i ∈ A i (x), x ∈ S, i = 1, 2, . . . , N, where for any bounded and continuous function ǫ(·), the operatorΓ is defined bȳ Γ(ǫ(π)) = lim α↓0 Γ(π + αǫ(π)) − π α .
3. Finally, we will show that each stable limit point of the system of ODEs in Step 2 above is an SG-SP point. Thus, the strategy π corresponding to each stable limit of the above system of ODEs gives a Nash equilibrium of the underlying general-sum discounted stochastic game.

Simulation Results
We define a simple general-sum discounted stochastic game, named "Stick Together Game" or in short STG. Informally, STG is a game where participating agents located on a rectangular terrain are supposed to come together and stay close to each other. For the purpose of illustration we fix N = 2 and define the tuple (N, S, A, p, r, β) as follows.
1. State Space, S. Let M > 0 and O = {(x, y)|x, y ∈ Z}. Define W = {s = (x, y) ∈ O|0 ≤ x, y < M } as the possible positions of an agent. Then the state space is given by the Cartesian product S = W × W . 2. Action Space, A. For s ∈ W , let s 1 = |x| + |y| be its L 1 norm. Then, A(s) = {a ∈ O| s + a ≤ 1} represents the actions available for an agent to move to one-step neighbouring positions of s ∈ W . The action space is then defined by A = ∪ represent the set of all next states for an agent in state s ∈ W . 3. Transition probability, p. We assume that state transitions of individual agents are independent. Let q(s ′ |s, a i ) represent, for agent i, the probability of transition from state s ∈ W to s ′ ∈ W upon taking action a i ∈ A i (s). We define Then, the transition probability is given by p((s ′1 , s ′2 )|(s 1 , s 2 ), (a 1 , a 2 )) = q(s ′1 |s 1 , a 1 )q(s ′2 |s 2 , a 2 ). This transition probability function has the highest value towards that next state to which the action points to. 4. Reward, r. The reward for the two agents is defined as for state (s 1 , s 2 ) ∈ S and action (a 1 , a 2 ) ∈ A(s) × A(s). Thus, the reward is zero if the distance between the two agents is zero. Otherwise, it is a negative and monotonically decreasing function with respect to the distance between the two agents. For verification of the solution of on-line algorithms in this game, we define a simple average distance tracking iteration as follows:d n+1 =d n + a × (d n −d n ), where d n is the distance between the agents at simulation instant n, a > 0 is a small constant representing iterate step-size andd n is the average distance at simulation instant n.

Results:
In the case of OFF-SGSP, we provide the evolution of the objective function f as a function of the number of iterations in Figure 2(a). Note that f should go to zero for a Nash equilibrium point. Figure 2(b) shows the evolution of d n with the number of iterations in the case of ON-SGSP applied to the STG. One would expect the average distance d n would reduce to zero. However, considering that the transition probability is non-zero in various directions for each agent, the average is non-zero but small in value. All our simulation results are run on a 1.83GHz Intel Core2Duo, 2GB DDR2 667MHz machine. It took ≈ 50 minutes to run 10,000 iterations of OFF-SGSP while it took ≈ 2.5 seconds for 100,000 iterations of ON-SGSP. Now, we show simulation results for a more realistic version of the STG game where M = 30. The number of states here is |S| = 810, 000. We provide in this case the results only with on-line algorithms because OFF-SGSP's computational complexity grows exponentially with M . The evolution of the average distance d n between the two agents as a function of the number of iterations of ON-SGSP is shown in Figure 2 Simple function approximation for STG: OFF-SGSP and ON-SGSP represent two extreme cases of learning where OFF-SGSP assumes full information of the game while ON-SGSP assumes that neither rewards nor state transition probabilities are known. Here, we explore an intermediate information case albeit restricted to STG where a partial structure of rewards is made known. In particular, let it be known that the reward depends on the difference in positions between the two agents. Then, we can do an approximation about the value function v and strategy π as follows. Let t = (|x 1 −x 2 |, |y 1 −y 2 |) ∈ S where s 1 = (x 1 , y 1 ), s 2 = (x 2 , y 2 ) ∈ S are positions of the two agents. With the partial information about the reward being function of t, we could approximate v i (s) ≈v i (t) and possibly π i (s) ≈π i (t), ∀s ∈ S. Thus, the algorithms need to computev andπ which is on the subspace W ⊂ S. However, the result would apply to the entire state space S. We present the simulation result of ON-SGSP in Figure 2

Conclusions
In this paper, we presented two novel algorithms -OFF-SGSP and ON-SGSP, for the computation of Nash equilibrium strategies of any given discounted general-sum stochastic game. OFF-SGSP is an offline centralized algorithm that uses full information about stochastic game structure. On the other hand, ON-SGSP is an online  decentralized scheme that only uses the stochastic game as a generative model and follows a learning approach. Both the algorithms are shown to converge to a Nash equilibrium in stationary strategies. Further, experimental evaluation suggests that convergence is relatively quick.
There are several future directions to be explored such as handling (i) equilibrium selection based on some specified criteria, (ii) very large state spaces, and (iii) incomplete state information.

A KKT-SP conditions
Recall that the Lagrangian corresponding to (2), can be written as where s z and t z , z = 1, 2, . . . , m are the slack variables.
Using the Lagrangian, the associated KKT conditions for the sub-problem (2) corresponding to a state x ∈ S and agent i ∈ {1, . . . , N } at a point θ * , p * are the following: KKT-SP conditions were shown by Prasad and Bhatnagar [21] to be necessary and sufficient for (v * , π * ) to represent a Nash equilibrium point of the underlying stochastic game and π * to be a Nash strategy-pair in the case of N = 2. However, this was shown under an assumption that for each sub-problem, ∇ θ g i x,z (θ * ) : z = 1, 2, . . . , m is a set of linearly independent vectors. On the other hand, we formulated an alternative easier set of conditions that we called SG-SP conditions (see Definition 1). An added advantage with these conditions is that they do not impose any linear independence requirement to ensure that the solution points of the sub-problems correspond to Nash equilibria, unlike the KKT-SP conditions.
We now establish the kinship between SG-SP and KKT-SP conditions.

B Proofs of Section 3
Theorem 5. A feasible point (v * , π * ) of the optimization problem (1) provides a Nash equilibrium in stationary strategies to the corresponding general-sum discounted stochastic game if and only if f (v * , π * ) = 0.
Proof. See [7, Theorem 3.8.2] for a proof in the case of N = 2. The proof works in a similar manner for general N .

Theorem 8 (Nash ⇔ SG-SP).
A strategy π * is Nash if and only if (v * , π * ) for the corresponding optimization problem (1) is an SG-SP point.
Proof. The proof follows from a combination of Lemmas 6 and 7.

C Assumptions
We make the following assumptions for the analysis of our algorithms.

Assumption 2. A Nash equilibrium in stationary randomized strategies exists for general-sum discounted stochastic games.
Assumption 3. The step-sizes {b(n)}, {c(n)} are such that b(n), c(n) > 0 ∀n,

Assumption 4.
The underlying Markov chain with transition probabilities p(y|x, π), x, y ∈ S, corresponding to the general-sum discounted stochastic game, is irreducible and positive recurrent for all possible strategies π.

D Proofs of Section 4
Proposition 9. Suppose the value π i (x) is maintained as a probability over A i (x) for all x ∈ S, i = 1, 2, . . . , N . Then for each i = 1, 2, . . . , N, x ∈ S, a i ∈ A i (x), we have that π i (x, a i )g i x,a i (v i , π −i ) is a non-ascent, and in particular a descent direction if π i (x, a i )g i x,a i (v i , π −i ) = 0, in the objective of the main optimization problem (1). Here g i x,a i (v i , π −i ) ≤ 0 represents the first constraint (1).
Proof. The objective function of the optimization problem (1) can be rewritten in terms of g i x,a i (v i , π −i ) as Consider an a i ∈ A i (x) for some x ∈ S and i ∈ {1, 2, . . . , N }. We show that π i (x, a i )g i x,a i (v i , π −i ) is a descent direction by the following Taylor series argument. Let for a small δ > 0. Defineπ to be the same as π except with the probability of picking action a i in state x by agent i being changed toπ i (x, a i ) (and the rest staying the same). Then by Taylor series expansion of f (v,π) till the first order term for small δ, It is easy to see that Note that if f (v, π) > 0 which implies that solution is not yet achieved (see Theorem 5), there is at least one former case.

E Convergence analysis
We provide a proof of convergence of the two proposed algorithms -OFF-SGSP and ON-SGSP, respectively. For both the algorithms, we assume that the underlying Markov chain with transition probabilities p(y|x, π), x, y ∈ S, corresponding to the general-sum discounted stochastic game, is irreducible and positive recurrent for all possible strategies π.
Both our algorithms employ two time-scale stochastic approximation [5,Chapter 6]. That is, they comprise of iteration sequences that are updated using two different time-scales or step-size schedules defined via {b(n)} and {c(n)}, respectively. Here, {c(n)} is the faster of the two schedules that is used for update of the value v while the slower time-scale {b(n)} is used to update π. Hence, π appears quasi-static for updates of v. On the other hand, for updates of π, v seems to have converged to v π which is the value v given a particular π. Convergence analyses of the three algorithms involve the following steps: 1. We first show that the updates of v, that are on the faster time-scale, converge to a limit point of the following system of ODEs: where π is assumed to be time-invariant. We will also see that the system of ODEs (12) has a unique limit point which is stable. We will refer to the value v at that limit point as v π .
3. Finally, we will show that each stable limit point of the system of ODEs (13) is an SG-SP point. Thus, the strategy π corresponding to each stable limit of the system of ODEs (13) gives a Nash equilibrium of the underlying general-sum discounted stochastic game.

E.1 OFF-SGSP
Let R i π = r i (x, π), x ∈ S be a column vector of rewards to agent i and P π = [p(y|x, π), x ∈ S, y ∈ S] be the transition probability matrix, both for a given π. Lemma 10. The system of ODEs (12) has a unique globally asymptotically stable limit point given by Proof. The system of ODEs (12) can be re-written in vector form as given below.
Rearranging terms, we get where I is the identity matrix of suitable dimension. Note that for a fixed π, this ODE is linear in v i with state transition matrix as (βP π − I). Since P π is a stochastic matrix, the magnitude of all its eigen-values is upper bounded by 1. Hence all the eigen-values of the state transition matrix (βP π − I) have negative real parts and the matrix (βP π − I) is in particular non-singular. Thus by standard linear systems theory, the above ODE has a unique globally asymptotically stable limit point which can be computed by setting dv i dt = 0, i = 1, 2, . . . , N , i.e., R i π + (βP π − I)v i = 0, i = 1, 2, . . . , N.
The trajectories of the ODE (15) converge to the above point starting from any initial condition in lieu of the above.
For a given π, the updates of v in equation (6) (OFF-SGSP) can be seen as Euler discretization of the system of ODEs (12). We now show that v n in equation (6) of OFF-SGSP converges to v π as given in equation (14).
Lemma 11. For a given π, i.e., with π i n ≡ π i , updates of v governed by (6) (OFF-SGSP) satisfy v n → v π , as n → ∞, where v π is the globally asymptotically stable equilibrium point of the system of ODEs (12).
Proof. We verify here assumptions (A1) and (A2) of Borkar and Meyn [6] in order to use their result [6, Theorem for a scalar real number, r > 0. It is easy to see that h r (v i ) = (βP π − I)v i . Now since (βP π − I) has negative real parts, the ODE dv i dt = h ∞ (v i ) has the origin as its unique globally asymptotically stable equilibrium. Further, as shown in Lemma 10, v i π is the unique globally asymptotically stable equilibrium for the ODE (15). Assumption (A1) of Borkar and Meyn [6] is thus satisfied. Since the updates of v in equation (6) do not have any noise term in them, assumption (A2) of Borkar and Meyn [6] is trivially satisfied. Thus by Borkar and Meyn [6,Theorem 2.2], v n in equation (6) converges to the globally asymptotically stable limit point v π given in equation (14).
Thus on the faster time-scale {c(n)}, the updates of v obtained from (6) converge to v π , as given by (14). Let be the set of all limit points of the ODEs (13) and let L = π|π(x) is a probability vector over A i (x), ∀x ∈ S . Lemma 12. π ∈ K if and only if π ∈ L and Proof. If part: If π ∈ L and equation (16) is true, then by definition of operators Γ andΓ, the result follows. Only if part: The operatorΓ, by definition, ensures that π ∈ L. Suppose for some a i ∈ A i (x), x ∈ S and i ∈ {1, 2, . . . , N }, we haveΓ( π i (x, a i )g i x,a i (v i π , π −i )) = 0 but π i (x, a i )g i x,a i (v i π , π −i ) = 0. Then, g i x,a i (v i π , π −i ) = 0 and since π ∈ L, 1 ≥ π i (x, a i ) > 0. We analyze this condition by considering the following three cases.
1. Case when 1 > π i (x, a i ) > 0 and g i x,a i (v i π , π −i ) = 0. In this case, it is possible to find a ∆ > 0 such that for all δ ≤ ∆, which contradicts the initial supposition.
2. Case when π i (x, a i ) = 1 and g i x,a i (v i π , π −i ) = 0. Since v i π is solution of the system of ODEs (12), the following should hold: This again leads to a contradiction.
The result follows.
represent the set of all feasible points of the optimization problem (1). The set K can be partitioned using the feasible set G as K = K 1 ∪ K 2 where K 1 = K ∩ G and K 2 = K \ K 1 . We now show that the set K 1 is the set of all locally asymptotically stable equilibrium points and that K 2 is the set of locally unstable equilibrium points of the system of ODEs (13).
Lemma 13. All π * ∈ K 1 are locally asymptotically stable equilibrium points of the system of ODEs (13).
By Proposition 9, the direction chosen for update of π i (x, a i ), i.e., π i (x, is a steepest ascent direction in π i (x, a i ) along the objective f (v, π). Now since π i (x, a i ) is a scalar variable, it follows that . Thus, this corresponds to a non-boundary point which implies thatΓ( π i (x, a i )g i x,a i (v i π , π −i )) = 0 with same sign as that of g i x,a i (v i π , π −i ). Also, ∆ > 0 can be chosen such that Lemma 14. All π * ∈ K 2 are unstable equilibrium points of the system of ODEs (13).
Proof. The updates of π given by (5) on the slower time-scale {b(n)} can be rewritten as π i n+1 (x, a i ) = Γ(π i n (x, a i ) + b(n) π i n (x, a i )g i x,a i (v i πn , π −i n ) + b(n)χ n ), ∀a i ∈ A i (x), x ∈ S, i = 1, 2, . . . , N, where χ n is an o(1) error term that goes to zero as n → ∞. The set of iterations in (17) can be viewed as an Euler discretization of the system of ODEs (13) with an extra error term χ n which however (as mentioned before) is o(1). Using a standard stochastic approximation argument, see Kushner and Clark [15, pp. 191-196], and the Hirsch's Lemma [10, Theorem 1, pp. 339], it is easy to see that updates of π in (17) converge to an equilibrium point for the system of ODEs (13).
Note that from the foregoing, the set K comprises of both stable and unstable attractors and in principle from Lemma 14, the iterates π i n governed by (13) can converge to an unstable equilibrium. In most practical scenarios, however, a gradient descent scheme is observed to converge to a stable equilibrium. In fact, the δ-offset policy computed using perturb(·, δ) for every Q > 0 iterations in OFF-SGSP ensures numerically that as n → ∞, π n π * ∈ K 2 . In other words, convergence of the strategy sequence π n obtained from algorithm 1 is to the stable set K 1 . Let K ′ = {π ∈ L|π is an SG-SP point of the underlying stochastic game} .
We now show that K 1 = K ′ . Theorem 16. All stable limit points of the system of ODEs (13) correspond to SG-SP points of the underlying discounted stochastic game and the policy in every SG-SP point is a stable limit point of the system of ODEs (13).
Proof. The proof follows simply from the definition of SG-SP point and the set K 1 .
To summarize, OFF-SGSP converges to a stable limit point of the system of ODEs (12,13) and every stable limit point corresponds to a Nash-equilibrium of the underlying general-sum discounted stochastic game.

E.2 ON-SGSP
Theorem 17. The updates of v in ON-SGSP converge to the globally asymptotically stable limit point of the system of ODEs (12).
Proof. Fix a state x ∈ S. Let {n} represent a sub-sequence of iterations in ON-SGSP when the state is x ∈ S. Also, let Q n = {n :n < n}. For a given π, the updates of v on the slower time-scale {c(n)} given in equation (9) can be re-written as π ī n (x, a i )g i x,a i (v ī n , π −ī n ), is the noise term. LetM n = m∈Qn c(m)χ m . Note that by assumption 4, every state x ∈ S is visited infinitely often. Then,M n , n ≥ 0 is a convergent martingale sequence by the martingale convergence theorem (since n c 2 (n) < ∞ and g i △ = |g i x,a i (·, ·)| < ∞). The above equation can now be seen as an Euler discretization of the system of ODEs (12) using Hirsch's Lemma [10, Theorem 1, pp. 339]. Thus, v converges to the globally asymptotically stable limit point v π (see equation (14)) of the system of ODEs (12). Theorem 18. The updates of π in ON-SGSP converge to a limit point of the system of ODEs (13), almost surely.
Proof. The update of π on the slower time-scale can be re-written as π ī n+1 (x, a i ) = Γ(π ī n (x, a i ) + b(n) π ī n (x, a i )g i x,a i (v i πn , π −ī n ) + b(n)χn + b(n)χn), ∀i = 1, 2, . . . , N, where χn = o(1) is an error term as in (17) andχn = π ī n (x, a i ) ĝ i x,a i − g i x,a i (v i πn , π −ī n ) . LetM n = m∈Qn b(m)χ m . Then, following similar argument as previously,M n is an almost surely convergent martingale sequence by the martingale convergence theorem. Now again using Hirsch's Lemma, the updates of π can be viewed as noisy Euler discretization of the system of ODEs (13). Thus, updates of π in ON-SGSP converge to a stable limit point of the system of ODEs (13).
The rest of the analysis follows as that of OFF-SGSP.