Laëtitia Matignon

Guillaume J Laurent

Nadine Le Fort-Piat

Coordination of independent learners in cooperative Markov games

In the framework of fully cooperative multi-agent systems, independent agents learning by reinforcement must overcome several difficulties as the coordination or the impact of exploration. The study of these issues allows first to synthesize the characteristics of existing reinforcement learning decentralized methods for independent learners in cooperative Markov games. Then, given the difficulties encountered by these approaches, we focus on two main skills: optimistic agents, which manage the coordination in deterministic environments, and the detection of the stochasticity of a game. Indeed, the key difficulty in stochastic environment is to distinguish between various causes of noise. The SOoN algorithm is so introduced, standing for "Swing between Optimistic or Neutral", in which independent learners can adapt automatically to the environment stochasticity. Empirical results on various cooperative Markov games notably show that SOoN overcomes the main factors of non-coordination and is robust face to the exploration of other agents.

1 Micro Electro Mechanical Systems.

2 also called strategic game. 3 also called policy. 4 also called zero-sum game. 5 also called team game or identical payoff game.

Introduction

Over the last decade, many approaches are concerned with the extension of RL to multi-agent systems (MAS) [START_REF] Busoniu | Multi-agent reinforcement learning: A survey[END_REF]. On the one hand, adopting a decentralized point of view with MAS offers several potential advantages as speed-up, scalability and robustness [2]. On the other hand, reinforcement learning (RL) methods do not need any a priori knowledge about the dynamics of the environment, which can be stochastic and non linear. An agent interacting with its environment tests different actions and learns a behavior by using a scalar reward signal called reinforcement as performance feedback. Modern RL methods rely on dynamic programming and have been studied extensively in single-agent framework [3]. By using RL in MAS, their advantages can be associated : autonomous and "simple" agents can learn to resolve in a decentralized way complex problems by adapting to them.

However, there are still many challenging issues in applying RL to MAS [START_REF] Yang | Multiagent reinforcement learning for multi-robot systems: A survey[END_REF]. For instance, one difficulty is the loss of theoretical guarantees. Indeed convergence hypothesis of singleagent framework are no longer satisfied. Another matter is that the computation complexity of decentralized MAS often grows exponentially with the number of agents [START_REF] Papadimitriou | On the complexity of designing distributed protocols[END_REF]6,7]. Finally, a fundamental difficulty faced by agents that work together is how to efficiently coordinate themselves [8,[START_REF] Chen | Coordinating multiple agents via reinforcement learning[END_REF]10]. MAS are qualified by a decentralized execution, so each agent takes individual decisions but all of the agents contribute globally to the system evolution. Learning in MAS is then more difficult since the selection of actions must take place in the presence of other learning agents. A study of some mis-coordination factors is proposed in this report.

Despite these difficulties, several successful applications of decentralized RL have been reported, like the control of a group of elevators [START_REF] Crites | Elevator group control using multiple reinforcement learning agents[END_REF] or adaptative load-balancing of parallel applications [START_REF] Stone | Multiagent systems: A survey from a machine learning perspective[END_REF]. Air traffic flow management [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF] and data transportation by a constellation of communication satellites [START_REF] Wolpert | Reinforcement learning in distributed domains: Beyond team games[END_REF] are other examples of real world applications of cooperative agents using RL algorithms. We have an interest in practical applications in robotics, where multiple cooperating robots are able to complete many tasks more quickly and reliably than one robot alone. Especially, the real world objective of our work is the decentralized control of a distributed micro-manipulation system based on autonomous distributed air-flow MEMS 1 , called smart surface [START_REF] Fukuta | Design, fabrication and control of memsbased actuator arrays for air-flow distributed micromanipulation[END_REF]. It consists of an actuators array on which an object is situated. The objective is for the hundreds of actuators to choose from a small set of actions over many trials so as to achieve a common goal.

We focus here on learning algorithm in cooperative MAS [START_REF] Papadimitriou | The complexity of markov decision processes[END_REF] which is a fitting model for such a real world scenario. Especially, in this report, we are interested in the coordination of adaptative and cooperative agents with the assumption of a full individual state observability. We consider independent learners (ILs) which were introduced in [START_REF] Bernstein | The complexity of decentralized control of markov decision processes[END_REF] as agents which don't know the actions taken by the other agents. The choice of ILs is particularly pertinent given our objective of robotic applications with numerous agents, where the assumption of joint action observability required for the joint action learners is hard to satisfy.

Our objective is to develop an easy-to-use, robust and decentralized RL algorithm for autonomous and independent learners in the framework of cooperative MAS. The chosen framework is cooperative Markov games. One of our contribution is to analyse what is at stake in the learning of ILs in this framework. Thanks to this study, we synthesize the characteristics of existing RL decentralized methods for ILs in cooperative Markov games. Then, we introduce a new algorithm named the SOoN algorithm, standing for "Swing between Optimistic or Neutral", in which ILs can adapt automatically to the environment stochasticity. We successfully develop this algorithm thanks to our analysis of previous algorithms and apply it within various matrix games and Markov games benchmarks. Its performance is also compared to other learning algorithms.

The report is organized as follows. In section 2, our theoretical framework is described. Learning in MAS has strong connections with game theory so a great part of the report concerns repeated matrix games. Matrix games study is a necessary first step toward the framework of Markov games. Indeed, it allows a better understanding of mis-coordination issues, presented in section 3 as one of major stakes of ILs in cooperative MAS. We overview related algorithms in section 4 and provide a uniform notation that has never been suggested and which emphasizes common points between some of these algorithms. This leads to a recursive version of the FMQ algorithm in the matrix game framework (section 6). It is successfully applied on matrix games which contain hard coordination challenges. Finally, in section 7, we present the SOoN algorithm in the general class of Markov games and show results demonstrating its robustness.

Theoretical framework

The studies of reinforcement learning algorithms in MAS are based on Markov games which define multi-agent multi-state models. They are the synthesis of two frameworks : Markov decision processes and matrix games. Markov decision processes are a single-agent multi-state model explored in the field of RL. Matrix games, on the other hand, are a multi-agent singlestate model used in the field of game theory. These frameworks are independently considered in this section. In addition, some classifications and equilibrium concepts are outlined.

Markov Decision Processes

Definition 1 A Markov Decision Process (MDP) [18,19] is a tuple < S, A, T, R > where :

• S is a finite set of states;

• A is a finite set of actions;

• T : S × A × S → [0; 1] is a transition function that defines a probability distribution over next states. T (s, a, s ) is the probability of reaching s when the action a is executed in s, also noted P (s |s, a),

• R : S × A × S → R is a reward function giving the immediate reward or reinforcement received under each transition.

At each time step, the agent chooses an action a t that leads the system from the state s t to the new state s t+1 according to a transition probability T (s t , a t , s t+1 ). Then it receives a reward r t+1 = R(s t , a t , s t+1 ). Solving MDPs consists in finding a mapping from states to actions, called a policy π : S × A → [0; 1], which maximizes a criterion. π(s, a) is the probability of choosing the action a in state s. Most of single agent RL algorithms are placed within this framework [20, 21, 3].

Matrix games

Game theory is commonly used to analyze the problem of multi-agent decision making, where a group of agents coexist in an environment and take simultaneous decisions. We first define the matrix game framework and the classification of these games, and then we examine two main equilibrium concepts.

Definition and strategy

Definition 2 A matrix game 2 [22,[START_REF] Osborne | A course in game theory[END_REF] is a multiple agent, single state framework. It is defined as a tuple < m, A 1 , ..., A m , R 1 , ..., R m > where :

• m is the number of players;

• A i is the set of actions available to player i (and A = A 1 × ... × A m is the joint action space);

• R i : A → R is player i's reward or payoff function.

The goal of a learning agent in a matrix game is to learn a strategy that maximizes its reward.

In matrix games, a strategy 3 π i : A i → [0; 1] for an agent i specifies a probability distribution over actions, i.e. ∀a i ∈ A i π i (a i ) = P (a i ). π is the joint strategy for all of the agents and π -i the joint strategy for all of the agents except agent i. We will use the notation π i , π -i to refer to the joint strategy where agent i follows π i while the other agents follow their policy from π -i . Similarly, A -i is the set of actions for all of the agents except agent i. The set of all of the strategies for the agent i is noted ∆(A i ).

Type of matrix games

Matrix games can be classified according to the structure of their payoff function. If payoff functions sum is zero, the game is called fully competitive game 4 . If all agents have the same payoff function, i.e. R 1 = ... = R m = R, the game is called fully cooperative game 5 . Finally, in general-sum game, the individual payoffs can be arbitrary.

In this paper, we focus on fully cooperative game. In these games, an action in the best interest of one agent is also in the best interest of all agents. Especially, we are interested in repeated games which consist of the repetition of the same matrix game by the same agents.

The game in table 1 depicts a team game between two agents which is graphically represented by a payoff matrix. The rows and columns correspond to the possible actions of respectively the first and second agent, while the entries contain the payoffs of the two agents for the corresponding joint action. In this example, each agent chooses between two actions a and b. Both agents receive a payoff of 0 when both selected actions of the agents differ, and a payoff of 1 or 2 when the actions are the same.

Equilibria

First, we define the expected gain for an agent i as the expected reward given its strategy and the strategies of others.

Definition 3

The expected gain for an agent i given a joint strategy π = π i , π -i , noted u i,π , is :

u i,π = E π {R i (a)} = a∈A π(a)R i (a). (1)
From a game-theoretic point of view, two common concepts of equilibrium are used to define optimal solutions in games. The first one is called Nash equilibrium [START_REF] Nash | Equilibrium points in n-person games[END_REF][START_REF] Osborne | A course in game theory[END_REF].

Definition 4 A joint strategy π * defines a Nash equilibrium iff, for each agent i, there is :

∀π i ∈ ∆(A i ) u i, π * i ,π * -i ≥ u i, π i ,π * -i .
(

Thus, no agent can improve its payoff by unilaterally deviating from a Nash equilibrium. A matrix game can have more than one Nash equilibrium. For example, the matrix game in table 1 has two Nash equilibria corresponding to the joint strategies where both agents select the same action. However, a Nash equilibrium is not always the best group solution. That's why the Pareto optimality has been defined.

Definition 5 A joint strategy π Pareto dominates another joint strategy π iff :

• each agent i following πi receives at least the same expected gain as with π i and,

• at least one agent j following πj receives a strictly higher expected gain than with π j , that's to say formally :

π > π ⇔ ∀i u i, π ≥ u i,π and ∃j u j, π > u j,π . ( 3
)
Definition 6 If a joint strategy π * is not Pareto dominated by any other joint strategy, then π * is Pareto optimal.

So a Pareto optimal solution is one in which no agent's expected gain can be improved upon without decreasing the expected gain of at least one other agent. There are many examples of general-sum games where a Pareto optimal solution is not a Nash equilibrium and vice-versa (for example, the prisoner's dilemma). However, in fully cooperative games, each Pareto optimal solution is also a Nash equilibrium by definition. This means that if a joint action provides one agent with maximal possible reward, it must also maximise the reward received by the other agents. For instance in the matrix game of the table 1, the joint strategy a, a defines a Pareto optimal Nash equilibrium.

Markov games

Markov games can be seen as the extension of matrix games to the multiple states framework. Specifically, each state of a Markov game can be viewed as a matrix game. Another point of view is to consider Markov games as an extension of MDP to multiple agents. Markov games were first examined in the field of game theory and more recently in the field of multi-agent RL.

Definition

Definition 7 A Markov game6 [START_REF] Shapley | Stochastic games[END_REF] is defined as a tuple < m, S, A 1 , ..., A m , T, R 1 , ..., R m > where :

• m is the number of agents;

• S is a finite set of states;

• A i is the set of actions available to the agent i (and A = A 1 × ... × A m the joint action space);

• T : S × A × S → [0; 1] a transition function that defines transition probabilities between states;

• R i : S × A → R the reward function for agent i.

In Markov game framework, all agents have access to the complete observable state s. The transition and reward functions are functions of the joint action. An individual policy π i : S × A i → [0; 1] for an agent i specifies a probability distribution over actions, i.e.

∀a i ∈ A i P (a i |s) = π i (s, a i ).
The set of all of the policies for the agent i is noted ∆(S, A i ). If for an agent i and for all states s, π i (s, a i ) is equal to 1 for a particular action a i and 0 for the others, then the policy π i is called a pure policy.

The same classification for matrix games can be used with Markov games. If all agents receive the same rewards, the Markov game is fully cooperative. It is then defined as an identical payoff stochastic game (IPSG)7 [26].

Equilibria

As in matrix games, we can define for each state s the immediate expected gain for an agent i following the joint strategy π as :

u i,π (s) = E π {R i (s, a)} = a∈A π(s, a)R i (s, a). ( 4
)
Thus, the long term expected gain from the state s for an agent i is, when all the agents follow π :

U i,π (s) = E π ∞ k=0 γ k u i,π (s) t+k+1 |s t = s (5)
where γ ∈ [0; 1] is a discount factor. The concepts of Nash equilibrium and Pareto optimality are also defined in Markov games.

Definition 8 A joint policy π * defines a Nash equilibrium in a Markov game iff, for each agent i, there is :

∀π i ∈ ∆(S, A i ) ∀s ∈ S U i, π * i ,π * -i (s) ≥ U i, π i ,π * -i (s). ( 6
)
Definition 9 A joint policy π Pareto dominates another joint policy π iff, in all states :

• each agent i following πi receives at least the same expected gain as with π i and,

• at least one agent j following πj receives a strictly higher expected gain than with π j , that's to say formally :

π > π ⇔ ∀i, ∀s ∈ S U i, π(s) ≥ U i,π (s) et ∃j U j, π(s) > U j,π (s). ( 7
)
Definition 10 If a joint policy π * is not Pareto dominated by any other joint strategy, then π * is Pareto optimal.

Conclusion

In this paper, we are interested in cooperative games, where we defined the objective as finding a Pareto-optimal Nash equilibrium, also called optimal equilibrium. Indeed, the policies which define Pareto-optimal Nash equilibria maximise the expected sum of the discounted rewards in the future for all agents. However, there can be several Pareto-optimal Nash equilibria so some coordination mechanisms on a single equilibrium are necessary.

The independent learners coordination problem

The main difficulty in the cooperative independent learners (ILs) framework is the coordination of ILs : how to make sure that all agents coherently choose their individual action such that the resulting joint action is optimal? We analyze this problem using the framework of fully cooperative matrix games that we have introduced in section 2.2. Each agent independently has to select an action from its action set. It receives a payoff based on the resulting joint action. Formally, the challenge in multi-agent RL is to guarantee that the individual optimal policies π * i define an optimal joint policy π * [START_REF] Vlassis | A concise introduction to multiagent systems and distributed AI[END_REF], i.e. a Pareto-optimal Nash equilibrium. The coordination is a complex problem which arises from the combined action of several factors. In large games, it is hard to identify these factors since they are often combined with other phenomena. So the classification proposed here is probably not exhaustive. It results from a study of matrix games with a small number of agents, where the identification and interpretation of some factors are more obvious. Of course, the exposed factors can be adapted to games with many agents and to Markov games. These factors make the analysis and development of coordination techniques in RL algorithms easier.

Fulda and Ventura [8] identify two main factors : shadowed equilibrium and equilibria selection problems that we formalized here. We also add two other factors : the noise in the game and the impact of the exploration of other agents on the learning of one agent.

Shadowed equilibrium

Definition 11 An equilibrium defined by a strategy π is shadowed by a strategy π iff : A particular structure game could be a game with a shadowed Pareto optimal Nash equilibrium. For instance, in the Climbing game (table 3), the Pareto optimal Nash equilibrium a, a and the sub-optimal Nash equilibrium b, b are shadowed because penalties are associated to mis-coordination on a, b or b, a . Moreover, there are no mis-coordination penalties associated with action c, potentially making it tempting for the agents. The joint action c, c is the only unshadowed equilibrium in the Climbing game. So c, c is potentially interesting for ILs.

∃i ∃π i u π i , π-i < min j,π j u π j , π-j (8)

Equilibria selection problems

The equilibria selection problem takes place whenever at least two agents are required to select between multiple Pareto optimal Nash equilibria. In this case, some agents must choose between several optimal individual policies but only some combinations of these optimal individual policies define an optimal equilibrium. So the equilibria selection problem can be defined as the coordination of individual policies so that the resulting joint policy is optimal. Craig Boutilier introduced the set of potentially individually optimal (PIO) actions for agent i at state s as those actions in A i that belong to at least one of the optimal joint actions for s [START_REF] Boutilier | Planning, learning and coordination in multiagent decision processes[END_REF]. An optimal joint action is a pure joint policy which defines a Pareto optimal Nash equilibrium. This set is denoted P IO(i, s). State s is said to be weakly dependent for agent i if there is more than one PIO choice for i at s. We can define the equilibria selection problem with this notion.

Definition 12

There is an equilibria selection problem at state s if at least two agents are required to select between multiple Pareto optimal Nash equilibria at this state, i.e. s is weakly dependent for at least two agents.

The Penalty game (table 3d) is usually chosen to illustrate the equilibria selection problem. There are two Pareto optimal Nash equilibria : a, a and c, c and one sub-optimal Nash equilibrium b, b . The set of potentially individually optimal actions for each agent is then {a, c}. So the Penalty game is weakly dependent for the two agents and agents confront an equilibria selection problem. Simply choosing an individual optimal action in the set PIO does not guarantee that the resulting joint action will be optimal since four joint actions are then possible ( a, a , c, c , a, c , c, a ) and only two of them are optimal.

In this game, k is usually chosen inferior to 0 so as to combine shadowed equilibria with equilibria selection issue. Indeed, the only unshadowed equilibrium in this game is the suboptimal Nash equilibrium b, b .

Noise in the environment

Agents in a MAS can be confronted with noise in their environment. Noise in the environment can be due to various phenomena : stochastic rewards, e.g. in the stochastic variations of the Climbing game (table 3d and c), unobservable factors in the state space, uncertainty, ... . However, changing behaviors of the other agents can also be interpreted as noise by an IL. For instance in the partially stochastic Climbing game, an IL must distinguish if distinct rewards received for the action b are due to various behaviors of the other agent or to stochastic rewards. The agent must learn that the average reward for the joint action b, b is 7 and is lower than that of a, a . Thus the difficulty in ILs games is to distinguish between noise due to the environment and noise due to other agents behaviors. This behavior is notably characterized by actions of exploration.

Exploration

In MAS as in single-agent case, each IL must choose actions of exploration or exploitation according to its decision strategy. The common action decision called softmax is based on agent's individual policy π i computed thanks to a Boltzman distribution :

π i (s, a) = e Q i (s,a) τ u∈A i e Q i (s,u) τ ( 9
)
where τ is the temperature parameter that decreases the amount of randomness as it approaches zero. The -greedy strategy is another common action selection method in which an agent follows its greedy policy8 with probability (1 -) (exploitation mode), and otherwise selects a uniformly random action with probability (exploration mode).

The exploration is a major stake in the reinforcement learning of ILs. Indeed, as stated before, an IL cannot detect the change of behaviors of the other agents. So the exploration of others can induce noise in received rewards of an IL.

So as to quantify the noise due to the exploration in a game, the concept of global exploration must be pointed out. The global exploration is the probability of having at least one agent which explores. It can be formulated with the individual exploration of each agent.

Property 1 Let a n-agents system in which each agent explores according to a probability . Then the probability of having at least one agent which explores is

ψ = 1 -(1 -) n . ψ is named global exploration.
The exploration of an agent can have strong influences on the learned policy of an IL. In a game with an optimal shadowed equilibrium defined by a policy π, let agent i follow its optimal individual policy πi . The exploration of others can then lead to penalties (equation 8). So the exploration of others has an influence on the learning of i's individual policy. Moreover, it can cause the "destruction" of the optimal policy of an IL. So it is necessary that RL algorithms should be robust face to exploration.

Conclusion

In this report, we focus our study on cooperative independent learners. In such a framework, the main issue is to manage the coordination of the learners. We have detailed four factors responsible of the non-coordination of agents. Solving these difficulties and overcoming miscoordination factors is one the main objectives of RL algorithms in MAS. Another key parameter is the robustness face to exploration.

Related works in Reinforcement Learning

Various approaches have been proposed in the literature to prevent coordination problems in multi-independent-learners systems. In this section, related works dealing with RL algorithms are reviewed with an emphasis on algorithms dealing with Q-learning [START_REF] Watkins | Technical note: Q-learning[END_REF] and Q-learning variants for ILs. We propose a uniform notation, that has never been suggested for these algorithms, and which stresses common points between some of them. For each algorithms, the robustness face to mis-coordination factors and exploration is discussed. Table 4: Percentage of trials which converged to the optimal joint action (averaged over 1000 trials). A trial consists of 3000 repetitions of the game. At the end of each trial, we determine if the greedy joint action is the optimal one. Results were obtained with softmax decision and various exploration strategies : stationary (τ ) or GLIE (τ = τ ini × δ t where t is the repetitions number).

Stationary strategy τ = 1000 τ = 200 τ = 10 τ = 1 Penalty game (k = -100) 62, 6% 65, 3% 62, 8% 65, 1% GLIE τ ini = 5000 τ ini = 500 τ ini = 100 strategy δ = 0.9 δ = 0.99 δ = 0.995 δ = 0.997 δ = 0.995 δ = 0.995 Penalty game (k = -100) 0% 61, 7% 84% 96, 6% 85, 3% 84, 8%

In the following methods, each IL builds its own Q i -table whose size is independent of the agents number and linear in function of its own actions. The task is for the agents to independently choose one action with the goal of maximizing the expected sum of the discounted rewards in the future.

Decentralized Q-learning

Q-learning [START_REF] Watkins | Technical note: Q-learning[END_REF] is one of the most used algorithm is single-agent framework because of its simplicity and robustness. That's also why it was one of the first RL algorithm applied to multi-agent environments [START_REF] Bernstein | The complexity of decentralized control of markov decision processes[END_REF]. The update equation for the agent i is :

Q i (s, a i ) ← (1 -α)Q i (s, a i ) + α(r + γ max u∈A i Q i (s , u)) ( 10
)
where s is the new state, a i is the agent's chosen action, r = R(s, a i , a -i ) the reward received, Q i (s, a i ) the value of the state-action for the agent i, α ∈ [0; 1] the learning rate and γ ∈ [0; 1] the discount factor.

Decentralized Q-learning has been applied with success on some applications [START_REF] Busoniu | Decentralized reinforcement learning control of a robotic manipulator[END_REF][START_REF] Sen | Individual learning of coordination knowledge[END_REF][START_REF] Sen | Learning to coordinate without sharing information[END_REF][START_REF] Wang | Multi-robot box-pushing: Single-agent q-learning vs. team q-learning[END_REF]. However, this algorithm has a low robustness face to exploration. Most of works concerning decentralized Q-learning use a GLIE9 strategy [START_REF] Satinder | Convergence results for single-step on-policy reinforcement-learning algorithms[END_REF] so as to avoid concurrent exploration. It consists in avoiding the simultaneous exploration of agents, namely the concurrent exploration. The principle is to decrease the exploration frequency as the learning goes along so that each agent should find the best response to the others behaviors. This method is investigated in MAS [START_REF] Claus | The dynamics of reinforcement learning in cooperative multiagent systems[END_REF][START_REF] Kapetanakis | Improving on the reinforcement learning of coordination in cooperative multi-agent systems[END_REF] and section 5.1.

Avoiding concurrent exploration can improved results of some algorithms by allowing ILs to overcome some mis-coordination factors. For instance, results of decentralized Q-learning can be improved as illustrated on table 4. Best results are obtained with a well chosen GLIE strategy. However, convergence then relies on the choice of decaying parameters. The use of a GLIE strategy does not ensure convergence to an optimal equilibrium [START_REF] Claus | The dynamics of reinforcement learning in cooperative multiagent systems[END_REF] and the key difficulty of this method is that the convergence relies on the choice of decaying parameters. Moreover, setting GLIE parameters requires high skills on algorithm behavior and so it is difficult to apply in real applications.

Algorithm 1: Distributed Q-learning for agent i 10 begin Initialization : forall a ∈ A i and s ∈ S do Q i,max (s, a) ← 0, π i (s, a) arbitrarily s ← initial state while s is not an absorbing state do

From s select a according to the -greedy selection method based on π i Apply a and observe reward r and next state s q ← r + γ max

u∈A i Q i,max (s , u) if q > Q i,max (s, a) then Q i,max (s, a) ← q optimistic update if Q i,max (s, arg max u∈A i π i (s, u)) = max u∈A i Q i,max (s, u) then
Select a random action a max ∈ arg max

u∈A i Q i,max (s, u) ∀b ∈ A i π i (s, b) ← 1 if b = a max 0 else equilibria selection mechanism s ← s end

Distributed Q-learning

To get round the issue of shadowed equilibria with ILs, Lauer & Riedmiller [START_REF] Lauer | An algorithm for distributed reinforcement learning in cooperative multi-agent systems[END_REF] introduced "optimistic independent agents". Such agents neglect in their update the penalties which are often due to a non-coordination of agents. For instance the evaluation of an action in matrix games is the maximum reward received. In the case of multiple optimal joint actions in a single state, an additional procedure for coordination is used to solve the equilibria selection problem. This equilibria selection mechanism is a social convention [START_REF] Boutilier | Planning, learning and coordination in multiagent decision processes[END_REF] which places constraints on the possible action choices of the agents. The central idea is to update the current policy π i only if an improvement in the evaluation values (Q i,max ) happens. This mechanism presents the other interest to allow simultaneously the learning of individual policies and exploration. The individual policies can't be "destroyed" by exploration since when one of the optimal joint policies is tried, it is nevermore modified. Distributed Q-learning associated with this equilibria selection method is in algorithm 1. It addresses two factors that can cause mis-coordination : shadowed equilibria are prevented through the optimistic update and the equilibria selection problem is solved thanks to the equilibria selection method. It is proved that this algorithm finds optimal policies in deterministic environments for cooperative Markov games. Moreover, distributed Q-learning is robust face to exploration. However this approach does generally not converge in stochastic environments.

Variable learning rate algorithms

To minimize the effect of shadowed equilibria with ILs, some authors propose to minimize the effect that the learning of other agents has on a given agent's own learning by using a variable learning rate. For instance some algorithms based on gradient ascent learners use the Win or Learn Fast (WoLF) heuristic [START_REF] Bowling | Multiagent learning using a variable learning rate[END_REF] and its variants PD-WoLF [START_REF] Banerjee | Adaptive policy gradient in multiagent learning[END_REF] or GIGA-WoLF [START_REF] Bowling | Convergence and no-regret in multiagent learning[END_REF]. Others are based on Q-learning, e.g. the hysteretic Q-learning [START_REF] Laetitia Matignon | Hysteretic q-learning :an algorithm for decentralized reinforcement learning in cooperative multi-agent teams[END_REF] in which two learning rates α and β are used for the increase and decrease rates of Q i -values. The update equation for the agent i is :

δ ← r + γ max u∈A i Q i (s , u) (11) Q i (s, a) ← (1 -α)Q i (s, a) + αδ if δ ≥ Q i (s, a) (1 -β)Q i (s, a) + βδ else ( 12
)
The idea is that agents should not be altogether blind to penalties at the risk of staying in sub-optimal equilibrium or mis-coordinating on the same optimal joint equilibrium. But they are chiefly optimistic to reduce oscillations in the learned policy (α > β).

Lenient Multiagent Reinforcement Learning

Panait et al. [START_REF] Panait | Lenient learners in cooperative multiagent systems[END_REF][START_REF] Sullivan | Can good learners always compensate for poor learners?[END_REF] are interested in varying the degree of optimism of the agents as the game is repeated. Indeed, being optimistic may be useful at early stages of learning to identify promising actions. In case of lenient learners, agents are exploring at the beginning so most selected actions are poor choices and ignoring penalties is then justified. Nevertheless, it may lead to an overestimation of actions, especially in stochastic domains where rewards are noisy. And once agents have explored, it becomes interesting to achieve accurate estimation of actions. So the agents are initially lenient (or optimistic) and the degree of lenience concerning an action decreases as the action is often selected. The main drawbacks of this method are that a large number of parameters must be set and that it is only proposed for matrix games.

Frequency Maximum Q-value (FMQ)

Kapetanakis & Kudenko [START_REF] Kapetanakis | Reinforcement learning of coordination in cooperative multi-agent systems[END_REF][START_REF] Kapetanakis | Reinforcement learning of coordination in heterogeneous cooperative multi-agent systems[END_REF] bias the probability of choosing an action with the frequency of receiving the maximum reward for that action. In their algorithm, the evaluation of an action E i is the Q i -value added to an heuristic value, taking into account how often an action produces its maximum corresponding reward. The evaluation of an action a is defined as :

E i (a) = Q i (a) + c × F i (a) × Q i,max (a) (13)
where Q i,max (a) is the maximum reward received so far for choosing action a, F i (a) is the frequency of receiving the maximum reward corresponding to an action, named occurrence frequency, and c is a weight which controls the importance of the FMQ heuristic in the evaluation.

The Frequency Maximum Q value (FMQ) algorithm is described in the algorithm 2. C i (a) holds the number of times the agent has chosen the action a in the game and C i,Qmax (a) the number of times that the maximum reward has been received as a result of playing a. Although FMQ algorithm is only proposed for matrix games, it shows interesting results on partially stochastic games.

Thanks to the uniform notation that we have proposed in this section, it is obvious that the FMQ has common points with the distributed Q-Learning. Indeed, the same Q i,max table is computed in both algorithms.

Kapetanakis & Kudenko [START_REF] Kapetanakis | Reinforcement learning of coordination in cooperative multi-agent systems[END_REF] use with FMQ a softmax decision method and an exponentially decaying temperature function :

τ k = τ max e -δk + τ ∞ ( 14
)
10 Rewards are supposed to be non-negative. 11 Rewards are supposed to be non-negative.

Algorithm 2: FMQ for Matrix Game for agent i 11 begin Initialization :

∀a ∈ A i , Q i (a) ← 0, Q i,max (a) ← 0, C i (a) ← 0 C i,Qmax (a) ← 0, F i (a) ← 1, E i (a) ← 0, π i arbitrarily repeat
Select a following the policy π i Apply a and observe reward r

C i (a) ← C i (a) + 1 action occurrence counter Q i (a) ← (1 -α)Q i (a) + αr if r > Q i,max (a) then Q i,max (a) ← r optimistic update C i,Qmax (a) ← 1 maximal reward occurrence counter else if r = Q i,max (a) then C i,Qmax (a) ← C i,Qmax (a) + 1 F i (a) ← C i,Qmax (a) C i (a)
occurrence frequency

E i (a) ← Q i (a) + c × F i (a) × Q i,max (a) heuristic ∀b ∈ A i , π i (b) ← e E i (b) τ u∈A i e E i (u) τ
until the end of the repetitions end Table 5: Percentage of trials which converged to the optimal joint action (averaged over 500 trials). A trial consists of 5000 repetitions of the game. We set α = 0.1 and c = 10. At the end of each trial, we determine if the greedy joint action is the optimal one. FMQ

Exploration strategy GLIE τ = 499e -0,006t + 1 100% τ = 100e -0,006t + 1 59% τ = 499e -0,03t + 1 86% τ = 100 × 0, 997 t 70% Stationary τ = 20 23%
where k is the number of repetitions of the game so far, δ controls the rate of the exponential decay, τ max and τ ∞ set the values of the temperature at the beginning and at the end of the repetitions. However, using such a temperature function requires to choose in an appropriate manner all the decaying parameters. Results in table 5 illustrate the difficulty to choose these parameters; changing just one setting in these parameters can turn a successful experiment into an unsuccessful one. So FMQ has a low robustness face to exploration.

Experimental results

We compare the performance of some of these algorithms in the cooperative matrix games presented in table 2 and 3. A trial consists of 3000 repetitions of the game. At the end of each trial, we determine if the greedy joint action is the optimal one. Results were obtained with the best chosen and tuned action selection strategy in order to achieve the best results of convergence (see Appendix A). Table 6 brings together the percentage of trials converging to the optimal joint action according to the algorithm and the type of cooperative matrix. First, it is interesting to notice that with an appropriate exploration strategy, all algorithms find the optimal joint action in the simple cooperative game. Concerning the distributed Qlearning, the convergence is managed with a stationary strategy in deterministic games only. The decentralized Q-learning succeeds in selecting the equilibrium in the Penalty game thanks to the GLIE strategy which plays an implicit role of equilibria selection mechanism. However, it could be more difficult to overcome shadowed equilibria as in the Climbing game. Penalties induce decentralized Q-learning agents to converge towards unshadowed equilibria so it fails. GLIE strategy does not ensure convergence to an optimal equilibrium. In deterministic matrix games, hysteretic Q-learning and FMQ achieve the convergence with a GLIE strategy. However, FMQ heuristic show the best results in partially and fully noisy games. The advantage of the FMQ is to be able to make the distinction between the noise due to the non-coordination of agents and the noise due to the environment in weak noise games.

Conclusion

Table 7 sums up which mis-coordination factors each algorithm is able to overcome and its robustness face to exploration. We specify that a GLIE strategy is difficult to set and requires high skills about the system and the algorithm. In view of this synthesis, two methods can be outlined. On the one hand, distributed Q-learning has been proved to converge in deterministic Markov games, and in this framework, it overcomes all factors and is robust face to exploration. But it ceases to be effective when stochastic rewards are introduced. On the other hand, FMQ heuristic is partially effective in non-deterministic matrix games and it could be an interesting way to detect the stochasticity causes of a game. Moreover, thanks to our uniform notation, common points between FMQ and distributed Q-learning have been shown, and especially they compute the same Q i,max tables. So it would be desirable to have an algorithm that improves the results of coordination techniques by combining these both methods. The objective is an algorithm robust face to exploration and able to overcome mis-coordination factors in deterministic and stochastic Markov games.

With the view to combine these two methods, we are first interested in improving FMQ heuristic in cooperative matrix games (section 5). Indeed FMQ requires a GLIE strategy and is weakly robust face to exploration. These improvements lead to a recursive FMQ designed for matrix games, robust face to exploration and gathering FMQ heuristic and optimistic indepen- [START_REF] Watkins | Technical note: Q-learning[END_REF] with GLIE partially Distributed total Q-Learning [START_REF] Lauer | An algorithm for distributed reinforcement learning in cooperative multi-agent systems[END_REF] Lenient learners [START_REF] Panait | Lenient learners in cooperative multiagent systems[END_REF] NT NT NT low Hysteretic low Q-Learning [START_REF] Laetitia Matignon | Hysteretic q-learning :an algorithm for decentralized reinforcement learning in cooperative multi-agent teams[END_REF] with GLIE partially WoLF PHC [START_REF] Bowling | Multiagent learning using a variable learning rate[END_REF] NT good FMQ [START_REF] Kapetanakis | Reinforcement learning of coordination in cooperative multi-agent systems[END_REF] low with GLIE partially dent agents (section 6). Then, we extend this algorithm to Markov game framework (section 7).

Frequency Maximum Q-value study

In this section, we are interested in improving FMQ heuristic in cooperative matrix games. Indeed, one of its difficulty is its low robustness face to exploration. Especially, there remain questions towards understanding exactly how the exploration strategy influences the convergence. The convergence also relies on the choice of the weight parameter c. Moreover, the evaluation of the action proposed in the original FMQ is not relevant. In this section, we investigate these issues in details and suggest some improvements. The objective is to achieve an algorithm more robust to the exploration and to get rid of the choice of the weight parameter c thanks to a novel evaluation of the action.

Improving the robustness face to the exploration strategy

Link between convergence and exploration

The low robustness of FMQ face to exploration has been illustrated in §4.5. To study these link between convergence and exploration in the FMQ, an exponentially decaying temperature is plotted in function of the number of repetitions of the game in figure1. The other curves are the average rewards and their dispersion received by FMQ agents using this temperature function and the softmax strategy in the Climbing game. Two phases can be identified. During a first phase of exploration, the average rewards remain constant; the agents choose all possible joint actions. Then, during the exponential decay of τ , the agents learn to coordinate until the temperature reaches some lower limit where agents are following their greedy policy. This is a phase of coordination.

Both of these phases of exploration and coordination are necessary for the FMQ to converge. If these phases are wrongly set or if a stationary strategy is used, FMQ success rate highly decreases (table 5). So FMQ has a low robustness face to exploration, i.e. the learning of a policy cannot be simultaneous to the exploration.

Instability of the frequency face to exploration

The link between convergence and exploration in the FMQ is due to an instability of the occurrence frequency F face to exploration. We illustrate this phenomenon on the Climbing game. We choose to study the instability of the occurrence frequency of the agent 1 for its action a, i.e. F 1 (a), face to the exploration of the other agent. a is the optimal individual action so F 1 (a) must tend toward 1.

Agents are supposed to be at the beginning of a learning phase. So the frequency F 1 (a) is initialized to 1. We plot the evolution of F 1 (a) according to the action choice of the other agent 12 (Fig. 2 dotted line). Actions chosen by the agents are represented on the diagram 13 . From beginning to end, the agent 1 only chooses action a and we study the instability of its frequency F 1 (a) face to the exploration of the other agent.

At the beginning, the joint action a, c is chosen many times. Agent 1 always receives the same reward for the action a. So C 1 (a) is high. Then, when the optimal joint action a, a is chosen for the first time (because of an exploration step), a new maximum reward is received for the action a and :

• the maximum reward received so far is modified Q 1,max (a) ← 11,
• the number of times that the maximum reward has been received as a result of playing a is reset C 1,Qmax (a) ← 1,

• the number of times the agent has chosen the action C 1 (a) is incremented.

12 An agent has 3 actions a, b and c. 13 Agents are following a "manual" policy. The frequency value, updated according to a) , drops at the 15th repetition (dotted line). Consequently, the action evaluation E 1 (a) might then be smaller than other action evaluations and the action a might be chosen only in exploration step. The convergence is not effective and many exploration steps are necessary so that the frequency F 1 (a) may increase enough for the coordination on the optimal joint action. Moreover, the later the optimal joint action is played, the more important is the drop in frequency values, and the higher is the number of exploration steps necessary for the coordination. So the optimal joint action must be chosen as sooner as possible. That's why the first phase of exploration is so important in the FMQ.

F 1 (a) ← C Q 1,max C 1 (a) = 1 C 1 (

Recursive computation of the frequency

In order to obtain an algorithm more robust to the exploration strategy, the counter C 1 (a) must be reset to 1 when a new maximum reward is received for the action a. The frequency a) is then also reset to 1 as at the fifteenth repetition in figure 2 (solid line). Thus, the frequency F 1 (a) is maintained around 1 and will only decrease in case of mis-coordination because of an exploration step of one agent or in case of noisy reward. The frequency is then more stable face to exploration.

F 1 (a) ← 1 C 1 (
Using incremental counters as C or C Qmax can also be a dependence factor on the oldness. The oldness is that the increase or decrease rate of the frequency depends on the number of repetitions after which an action of exploration or exploitation is played. So we introduce a recursive computation of the frequency :

F (a) ← (1 -α f )F (a) + α f if r = Q max (a) (1 -α f )F (a) else (15)
Table 8: Percentage of trials which converged to the optimal joint action (averaged over 500 trials). A trial consists of 5000 repetitions of the game. We set α = 0.1, α f = 0.05 and c = 10. At the end of each trial, we determine if the greedy joint action is the optimal one. FMQ Modified FMQ Exploration strategy

GLIE τ = 499e -0,006 t + 1 100% 100% τ = 100e -0,006 t + 1 59% 100% τ = 499e -0,03 t + 1 86% 100% τ = 100 × 0, 997 t 70% 100% Stationary τ = 20 23% 100%
where α f is the learning rate of the frequency. It is obvious in figure 2 that the frequency is now more robust to the exploration (solid line). The choice of α f will be discussed in §6.

Results

To check the robustness of modified FMQ with a reset and a recursive computation of the frequency, we choose the Climbing game. FMQ and its modified version are compared. Results are given in table 8. Modified FMQ converges with all tested strategies. Especially, a stationary strategy can be chosen. Using a constant exploration rate requires less parameters to set and is less inclined to instability due to the exploration. The only care concerns a sufficient number of repetitions of the game according to the constant exploration rate to ensure a complete exploration of the action set.

A new heuristic for the evaluation of the action

Kapetanakis & Kudenko [START_REF] Kapetanakis | Reinforcement learning of coordination in cooperative multi-agent systems[END_REF] introduce a weight c to control the importance of the FMQ heuristic in the evaluation of an action (equation 13). But the convergence relies on the value of this parameter [START_REF] Kapetanakis | Reinforcement learning of coordination in cooperative multi-agent systems[END_REF]. Moreover, Kapetanakis & Kudenko do not justify their choice of an action evaluation which is the sum of Q max values, weighted by c, F , and Q values. What are the theoretical justifications for using such a sum as an action evaluation? We propose another heuristic which has the advantage of avoiding the choice of any parameters and which is bound to converge in deterministic games.

First, we remind that both FMQ and distributed Q-learning compute the same Q max tables. This function returns in most cases an overestimation of the action evaluation, except in deterministic games where it is the exact maximal value of an action, as shown by Lauer & Riedmiller [START_REF] Lauer | An algorithm for distributed reinforcement learning in cooperative multi-agent systems[END_REF]. FMQ also uses Q-values which are an underestimation of the average rewards, since they include poor values due to mis-coordination. So real action values are between Q max and Q values. If Q max values are used to evaluate the actions in deterministic matrix game, the agents are ensured to converge if they use an equilibria selection mechanism. If the environment is stochastic, there is not any fitting algorithm so a solution could be to use Q values as action evaluations.

So if we can detect the stochasticity of the game, it is possible to evaluate actions with Q max is the game is deterministic or with Q values otherwise. To evaluate the stochasticity, we use the occurrence frequency F of receiving the maximum reward corresponding to an action. Indeed, if the game is deterministic and if the agents manage the coordination, the frequency tends to 1. So we propose to use a linear interpolation to evaluate an action a :

E(a) = [1 -F (a)]Q(a) + F (a)Q max (a). (16)
Thus, actions evaluation is close to optimistic values if the game is deterministic. Otherwise, it fluctuates between Q max and Q values according to the coordination of the agents. Indeed, when a new maximum reward for an action is received, the agent is first optimistic concerning this action. Then, if the reward is noisy, the frequency decreases and the agent becomes less optimistic and chooses its action according to Q-values. Thus this evaluation fluctuates between optimistic evaluation of distributed agents and mean evaluation of decentralized Q-learning agents according to the detection of the stochasticity. This action evaluation is a heuristic, so it can be modified or improved. For instance, an other option could be to apply an "all or nothing" evaluation instead of a linear interpolation. Then, a bound would be used for the frequency such that the agents would be optimistic (E = Q max ) if the frequency was upper than this bound, and they would be neutral (E = Q) if the frequency was lower than this bound. But such a heuristic requires to determine this bound.

Conclusion

Two main limitations of FMQ have been studied : its low robustness face to exploration and face to the weight parameter. Then improvements have been suggested. First, a recursive computation of the frequency is proposed to improve the robustness. Second, a new heuristic based on a linear interpolation between Q max and Q values is introduced. Thus, actions evaluation fluctuates between optimistic and mean evaluations according to the stochasticity of the game, which is estimated with the occurrence frequency. This method is set out in detail in the next section where these modifications are applied to the FMQ.

Recursive FMQ for cooperative matrix games

Previous modifications are incorporated to modify FMQ. The new algorithm, named recursive FMQ, is described in algorithm 3. Q max function is updated as in distributed Q-learning. In parallel are updated Q-values. These functions are used as bounds in the action evaluation. The evaluation is a linear interpolation heuristic based on the occurrence frequency. Actions evaluations fluctuate between Q max and Q values according to the stochasticity. The occurrence frequency is recursively computed thanks to a learning parameter α f and reset when a new maximum reward is received for an action. Thus if the game is deterministic and if the agents manage to coordinate on an optimal joint action, frequencies of individual optimal actions will be close to 1. Agents will be then optimistic. Otherwise, evaluations fluctuate between optimistic and mean values. The equilibria selection mechanism of [START_REF] Lauer | An algorithm for distributed reinforcement learning in cooperative multi-agent systems[END_REF] is used, with a random choice among actions that successfully maximizes the evaluation E.

The principle of this algorithm is then closest in spirit to lenient learners [START_REF] Panait | Lenient learners in cooperative multiagent systems[END_REF] (section 4.4) given that the degree of optimism of the agents can change. But concerning lenient learners, the degree of optimism inevitably decreases, although here, if the agents manage to coordinate in a deterministic environment, they stay optimistic. So they are bound to converge to the optimal joint action in deterministic environment, given that they follow the distributed Q-learning.

One of our stated goals was to obtain a more robust algorithm face to exploration. With this intention we have suggested a recursive computation of the frequency and removed the weight parameter c which influenced the convergence. Then a new parameter α f , named the Algorithm 3: Recursive FMQ for Matrix Game for agent i 14

begin

Initialization :

forall a ∈ A i do Q i (a) ← 0, Q i,max (a) ← 0, F i (a) ← 1, E i (a) ← 0, π i (a)
arbitrarily repeat Select a according to the -greedy selection method based on π i Apply a and observe reward r

Q i (a) ← (1 -α)Q i (a) + αr if r > Q i,max (a) then Q i,max (a) ← r optimistic update F i (a) ← 1 frequency reset else if r = Q i,max (a) then F i (a) ← (1 -α f )F i (a) + α f recursive computation of the frequency else F i (a) ← (1 -α f )F i (a) E i (a) ← [1 -F i (a)]Q i (a) + F i (a)Q i,max (a) linear interpolation heuristic if E i (arg max u∈A i π i (u)) = max u∈A i E i (u) then
Select a random action a max ∈ arg max

u∈A i E i (u) ∀b ∈ A i π i (b) ← 1 if b = a max 0 else equilibria selection
until the end of the repetitions end learning rate parameter of the recursive frequency, has been introduced. First, the benefit of removing the parameter c is that the new evaluation, based on a linear interpolation, has been justified and is more relevant. Second, the choice of α f can be stated so as to obtain a robust frequency. This will be the topic of the next paragraph.

Setting of the learning rate of the frequency α f

The frequency role is to detect the stochasticity in the game. So it must be able to set apart noise due to the non-coordination from noise due to the environment. So it is necessary that the frequency of one agent should not be sensitive to the exploration of others. Indeed, as stated in §3.4, the exploration of others can be considered as noise by an IL. The discrimination between various noise causes is all the more complex as agents number increases. Indeed, many agents imply that the noise due to their exploration increases. Thus the impact of many agents in a system can start to look like stochasticity. So we must make sure of the robustness face to the exploration of the frequency. α f choice is important and must be specified in function of global exploration.

α f sets the increase and decrease rates of the recursive frequency. With α f = 0, recursive FMQ is the same as distributed Q-learning. The higher is α f , the more sensitive is the frequency to the exploration of others. Indeed, let two agents be coordinated in a deterministic game, the agents' occurrence frequencies for the optimal individual actions are close to 1. If one explores, the received reward is smaller than the maximum reward. Then, for the greedy agent, the Table 9: Advocated choices for the learning rate of the frequency α f vs. global exploration ψ.

Global exploration

Learning rate of recursive frequency ψ = 0.1 α f = 0.01 ψ = 0.15 α f = 0.001 ψ = 0.2 α f = 0.0001 Advocated choices for the learning rate of the frequency are given in table 9 vs. global exploration. These choices arise from experimentations and lead to a robust frequency face to exploration. We advise against choosing a GLIE strategy because the choice of α f would then be complex 15 . This is in accordance with our previous warning about using such strategies, given their setting difficulties and their influence over the convergence. However, a stationary strategy is well fitted. In this case, a sufficient exploration must be set on the one hand for agents to find the optimal joint policy, and on the other hand for frequencies to converge toward their right values. Yet the global exploration must be restricted to avoid too much noise. Typically we suggest the value 0.2 as maximum bound for the global exploration.

Results on cooperative matrix games

We try recursive FMQ algorithm on various matrix games with 2 and more agents. These games bring together some mis-coordination factors. A key parameter of these tests is the exploration strategy and the repetitions number of the game per trial. As stated previously, we use a stationary strategy with recursive FMQ, since it is easier to set and the choice of α f is less complex (table 9). Nevertheless, it leads with many agents to a large number of repetitions. Indeed, on the one hand, a sufficient exploration must be realized for agents to find optimal equilibria. But on the other hand, the global exploration is limited to avoid too much noise.The number of joint actions is exponential with the number of agents. So the number of repetitions per trial is growing with the number of agents.

2 agents games

We test the performance of recursive FMQ on cooperative matrix games presented in table 2 and 3. Results are given in table 10. Recursive FMQ is used with a stationary strategy (greedy). It succeeds in all deterministic games and in partially stochastic Climbing game. Yet 15 GLIE is not necessary anymore. only half trials converge to the optimal in the fully stochastic Climbing game. So results are equivalent to original FMQ but the main interest of recursive FMQ is its robustness face to exploration thanks to a relevant choice of the frequency learning rate in function of the global exploration.

n agents games with n > 2

The role of the frequency is to distinguish noise from stochasticity versus noise from the other agents. In order to check that the frequency sets apart noise sources, we test recursive FMQ on large matrix games. Indeed, when there are many agents, it is more difficult to distinguish noise due to the environment from noise due to the others exploration. We use a n agents Penalty game detailed in appendix B. Recursive FMQ is compared with other RL algorithms. Results are given in table 11. Decentralized Q-learning succeeds in all deterministic games but with a well-chosen GLIE strategy. In stochastic games, its performances greatly reduce with the number of agents. However it is difficult to blame a wrong choice of the GLIE parameters or the lack of robustness face to noisy environments of the algorithm. Similarly, WoLF-PHC algorithm fails as soon as rewards are noisy. But we stress that in stochastic games, these algorithms converge toward sub-optimal equilibria.

Concerning distributed Q-learning, results comply with theoretical guarantee [START_REF] Lauer | An algorithm for distributed reinforcement learning in cooperative multi-agent systems[END_REF]. It succeeds in all deterministic games but fails in stochastic games.

Lastly, best results are achieved with recursive FMQ. It succeeds more than nine times out of ten with all games. In particular, it outperforms decentralized Q-learning in stochastic games with n > 3 agents. So the linear interpolation is a good measure of real actions values and the frequency manages the distinction between noise from stochasticity and noise from the other agents.

Conclusion

This section leads to a recursive version of the FMQ algorithm, which is more robust to the choice of the exploration strategy. A means of decoupling various noise sources in a matrix games has been studied. The recursive frequency sets apart noise due to others exploration from noise due to stochasticity. The choice of frequency parameter has been stated versus global exploration so as to obtain a robust frequency.

Recursive FMQ is effective with a constant exploration rate and is bound to converge in deterministic matrix game. It also outperforms the difficulties of partially stochastic environ-

Algorithm 4: Straightforward extension of recursive FMQ to Markov Games for i 16 begin

Initialization :

forall a ∈ A i and s ∈ S do Q i (s, a) ← 0, Q i,max (s, a) ← 0, F i (s, a) ← 1, E i (s, a) ← 0, π i (s,
Q i (s, a) ← (1 -α)Q i (s, a) + α(r + γ max u∈A i Q i (s , u)) q ← r + γ max u∈A i Q i,max (s , u) if q > Q i,max (s, a) then Q i,max (s, a) ← q optimistic update F i (s, a) ← 1 occurrence frequency reset else if q = Q i,max (s, a) then F i (s, a) ← (1 -α f )F i (s, a) + α f recursive frequency else F i (s, a) ← (1 -α f )F i (s, a) E i (s, a) ← [1 -F i (s, a)]Q i (s, a) + F i (s, a)Q i,max (s, a) linear interpolation heuristic if E i (s, arg max u∈A i π i (s, u)) = max u∈A i E i (s, u) then Select a random action a max ∈ arg max u∈A i E i (s, u) ∀b ∈ A i π(s, b) ← 1 if b = a max 0 else equilibria selection s ← s end ments.
The result is an easy-to-use and robust algorithm able to solve hard repeated matrix games. But an extension to Markov games is necessary.

The Swing between Optimistic or Neutral algorithm

In this section, we plan to design an algorithm for ILs in cooperative Markov games. We first propose a straightforward extension to Markov games of our previous recursive FMQ algorithm. But this extension presents few limits and some modifications are required to manage the coordination. We introduce a fitting frequency for multi-state framework. The Swing between Optimistic or Neutral (SOoN) algorithm is then proposed. We apply the SOoN algorithm to various multi-state benchmarks.

Straightforward extension to Markov games

The straightforward extension of recursive FMQ to Markov Games is in algorithm 4. This extension is obvious except the occurrence frequency F i (s, a) computation.

The frequency F i (a) computed in matrix games is the probability of receiving the maximum

F i (a) = P r {r t+1 = Q i,max (a t )|a t = a} . ( 17
)
In Markov games, the frequency is defined as following and named myopic frequency..

Definition 13

When action a is taken at state s, the myopic frequency F i (s, a) of agent i is the probability that the immediate transition should return a reward and a state whose evaluation, according to a greedy policy on Q i,max , is equal to the expected maximum value of Q i,max (s, a), i.e. :

F i (s, a) = P r r t+1 + γ max b∈A i Q i,max (s t+1 , b) = Q i,max (s t , a t )|s t = s, a t = a . ( 18
)
In the straightforward FMQ extension, following functions are defined for each individual agent i :

• the value function Q i updated as in decentralized Q-learning, • the value function Q i,max updated as in distributed Q-learning,
• the myopic frequency F i computed according to its definition 13,

• the evaluation function E i based on a linear interpolation between Q i and Q i,max values,

• the policy π i updated according to an equilibria selection mechanism based on a random choice among actions maximizing the evaluation function E i .

The myopic frequency is an immediate measure taking only the frequency in the current state into account. But is this myopic frequency enough for multi-state games?

Limitations of the myopic frequency

The straightforward extension can raise issues in some cases. To explain these limitations, we perform experiments on the cooperative Markov game given in figure 3, detailed in appendix C. This benchmark is difficult because agents must coordinate in each state. Especially, we study the development of the myopic frequency.

Optimal values of Q i,max for each agent i, at state s k , are :

Q * i,max (s k , a) = 10 × γ j-k-1 Q * i,max (s k , b) = 10 × γ j-k
From the point of view of one agent, we study two cases. 16 Rewards are supposed to be non-negative.

• The agent i plays the action b at state s k , so whatever the other agent plays, the next state s is s k and for each agent i :

q i = γ max u=1..2 Q i,max (s k , u) = 10 × γ j-k = Q * i,max (s k , b) (19)
So from the viewpoint of an agent, the action b is reliable and the occurrence frequency of receiving the Q i,max for the action b, namely F i (s k , b), increases each time action b is played at s by i. Moreover, it never decreases so F i (s k , b) converges to 1.

• The agent plays the action a at state s k . If the other agent also plays a, they coordinate and the next state s is s k+1 :

q i = γ max u=1..2 Q i,max (s k+1 , u) = 10 × γ j-k-1 = Q * i,max (s k , a) (20)
If the other agent plays b, they mis-coordinate and the next state s is s k :

q i = γ max u=1..2 Q i,max (s k , u) = 10 × γ j-k < Q * i,max (s k , a) (21)
So F i (s k , a) decreases each time the other agent plays b.

On the one hand, F i (s, b) increases each time action b is played at state s by agent i and never decreases. On the other hand, F i (s, a) decreases each time agents mis-coordinate at s. Consequently, from the viewpoint of one agent, the action b is safer than a.

Q * i,max (s, a) is close to Q * i,max (s, b) because Q * i,max (s, b) = γQ * i,max (s, a).
The evaluation E(s, b) can be higher than E(s, a). So the exploitation strategy of the agents is to choose the joint action < b, b > and so, to remain on the spot. Its failure to coordinate is illustrated in results presented in figure 4 at page 28 (dotted line). The number of steps per trial quickly increases since agents remain on the spot and mis-coordinate. At the beginning of the learning, agents have a random behavior so the number of steps per trial is low. This example illustrates a limitation in the straightforward extension of the recursive FMQ to Markov games due to the myopic frequency. This immediate measure only concerns the frequency in the current state, which is inadequate in multi-state games. The frequency must be globally considered by taking frequencies of future states into account. Indeed, in a given state, the myopic frequency of an action could be high, but this action could lead to a state where the optimal action has a low myopic frequency. In other words, an action could appear interesting in the current step according to its immediate frequency but could be a bad choice considering the future.

Using a myopic frequency could mislead the algorithm. So it could be relevant to use a long term or farsighted frequency.

Farsighted frequency

Definition 14 When action a is played at state s, the farsighted frequency G i (s, a) for agent i is the probability that all future transitions return rewards and states whose evaluations, according to a greedy policy on Q i,max , are equal to the expected maximum value Q i,max for these states, i.e. :

G i (s, a) = P πmax r r t+1 + γ max b∈A i Q i,max (s t+1 , b) = Q i,max (s t , a t ) ∧ r t+2 + γ max b∈A i Q i,max (s t+2 , b) = Q i,max (s t+1 , a t+1 ) ∧ . . . |s t = s, a t = a ( 22
)
The question is how to estimate this farsighted frequency?

We make the assumption that precedent events are independent, i.e. the occurrence of one event makes it neither more nor less probable that the other occurs. So the statement above is equivalent to :

G i (s, a) = P πmax r r t+1 + γ max b∈A i Q i,max (s t+1 , b) = Q i,max (s t , a t )|s t = s, a t = a × P πmax r r t+2 + γ max b∈A i Q i,max (s t+2 , b) = Q i,max (s t+1 , a t+1 ) ∧ . . . |s t = s, a t = a . (23)
According to the definition 13, the first term of the previous equation is equal to F i (s, a). And thanks to the total probability theorem, the second term is :

P πmax r r t+2 + γ max b∈A i Q i,max (s t+2 , b) = Q i,max (s t+1 , a t+1 ) ∧ . . . |s t = s, a t = a = s ∈S P πmax r r t+2 + γ max b∈A i Q i,max (s t+2 , b) = Q i,max (s t+1 , a t+1 ) ∧ . . . |s t = s, a t = a, s t+1 = s × P r s t+1 = s |s t = s, a t = a . (24)
The π max policy is following so a t+1 ∈ arg max

b∈A i Q i,max (s t+1 , b) and : G i (s, a) = F i (s, a) s ∈S P r s t+1 = s |s t = s, a t = a G i (s , arg max b∈A i Q i,max (s t+1 , b)) ( 25)
If P a ss is the probability of each next possible state s given a state s and an action a, we obtain :

G i (s, a) = F i (s, a) s ∈S P a ss G i (s , arg max u∈A i Q i,max (s , u)) (26)
As P a ss is unknown, we suggest to evaluate the farsighted frequency by following a temporal difference recursive computation :

G i (s, a) ← (1 -α g )G i (s, a) + α g F i (s, a) max v∈arg max u∈A i Q i,max (s ,u) G i (s , v) (27)
where α g ∈ [0; 1] is the learning rate of the farsighted frequency. The improvement supplied to the farsighted frequency is the product of the current state-action couple myopic frequency with the myopic frequency of the optimal action in the next state. Thus, if an action has at current state a high myopic frequency, but can lead to a state where the optimal action has a low farsighted frequency, then, this action will have a low farsighted frequency.

We could draw connections between the farsighted frequency general idea and bonus propagation for exploration [START_REF] Meuleau | Exploration of multi-state environments: Local measures and back-propagation of uncertainty[END_REF]. Bonus propagation leads to a full exploration of the environment thanks to a mechanism of retro-propagation concerning local measures of exploration bonuses. In the case of the farsighted frequency, values of myopic frequencies are spread : for each visited state, the agent "looks forward" future states to take into account values of frequencies of optimal actions in these states.

Algorithm 5: SOoN algorithm for Markov Game for agent i 17 begin

Initialization :

forall a ∈ A i and s ∈ S do Q i (s, a) ← 0, Q i,max (s, a) ← 0, F i (s, a) ← 1, G i (s, a) ← 1, E i (s, a) ← 0, π i (s, a)
arbitrarily s ← initial state while s is not an absorbing state do

From s select a according to the -greedy selection method based on π i Apply a and observe reward r and next state s

Q i (s, a) ← (1 -α)Q i (s, a) + α(r + γ max u∈A i Q i (s , u)) q ← r + γ max u∈A i Q i,max (s , u) if q > Q i,max (s, a) then Q i,max (s, a) ← q optimistic update F i (s, a) ← 1 myopic frequency reset G i (s, a) ← 1 farsighted frequency reset else if q = Q i,max (s, a) then F i (s, a) ← (1 -α f )F i (s, a) + α f frecursive myopic frequency else F i (s, a) ← (1 -α f )F i (s, a) farsighted frequency update G i (s, a) ← (1 -α g )G i (s, a) + α g F i (s, a) max v∈arg max u∈A i Q i,max (s ,u) G i (s , v) linear interpolation heuristic E i (s, a) ← [1 -G i (s, a)]Q i (s, a) + G i (s, a)Q i,max (s, a) if E i (s, arg max u∈A i π i (s, u)) = max u∈A i E i (s, u) then
Select a random action a max ∈ arg max

u∈A i E i (s, u) ∀b ∈ A i π i (s, b) ← 1 if b = a max 0 else equilibria selection s ← s end

Swing between Optimistic or Neutral algorithm

We use the farsighted frequency in a new algorithm, named Swing between Optimistic or Neutral (SOoN) and detailed in algorithm 5. Same functions as those defined at §7.1 are used. The novelty is the state-action evaluation based on the farsighted frequency G. The evaluation of a state-action couple sways from distributed Q max values to decentralized Q values according to G values and so according to a detection of stochasticity in the game. In deterministic Markov games, the farsighted frequency tends toward 1 and thus, the SOoN algorithm is close to the distributed Q-learning and is insured to converge towards optimal joint actions. Otherwise, in stochastic Markov games, the farsighted frequency is between 0 and 1 and the SOoN algorithm swings between optimistic or neutral evaluations.

We apply the SOoN algorithm to the cooperative Markov game of the figure 3 where the coordination of the two agents is difficult. Results are given in figure 4 (solid line). It is obvious that the agents then manage the coordination after 15 trials thanks to the use of the farsighted frequency.

Experimentations on Markov game benchmarks

We now show results of applying the SOoN algorithm to a number of different Markov games. We compare the performance of decentralized Q-learning, distributed Q-learning, WoLF-PHC, hysteretic Q-learning and SOoN. The domains include various levels of difficulty according to the agents number (2 and more), the state observability (full or incomplete), and mis-coordination factors (shadowed equilibria, equilibria selection, deterministic or stochastic environments). For each benchmarks, we state what is at stake in the learning of ILs. Moreover, and in a concern to be fair, all algorithms used -greedy selection method with a stationary strategy and global exploration of ψ = 0.1. It allows to check the robustness face to the exploration of each method.

Boutilier's coordination Markov games

The Boutilier's coordination game with two agents was introduced in [START_REF] Boutilier | Sequential optimality and coordination in multiagent systems[END_REF] and is shown in figure 5. This multi-state benchmark is interesting because all mis-coordination factors can Table 12: Percentage of cycles which converged to the optimal joint action (averaged over 50 cycles). We set α = 0.1, γ = 0.9, δ lose = 0.006, δ win = 0.003, α f = 0.01, α g = 0.03, = 0.05. β = 0.01 in deterministic games and β = 0.05 in stochastic games. At the end of each cycle, we determine if the greedy joint action is optimal.

Boutilier's coordination game deterministic stochastic A coordination issue applies in the second state of the game. Both agents should then agree on the same action. Moreover, there are two optimal equilibria so the agents are face to an equilibria selection problems and must coordinate on the same. Mis-coordination in the second state produces a penalty k. So the potential of choosing the action a for the first agent in the state s 1 is shadowed by the penalty k associated to mis-coordination. We also propose a partially stochastic version of the Boutilier's game with a random reward (14 or 0) received in state s 6 with equal probability instead of 7.

k = 0 k = -100 k = 0 k = -100 Decentralized Q-learning
A trials ends when agents reach one of the absorbing states (s 4 , s 5 or s 6 ). One cycle consists of 50000 learning trials. At the end of each cycle, we determine if the greedy joint action is optimal. Results are in table [START_REF] Stone | Multiagent systems: A survey from a machine learning perspective[END_REF].

In deterministic game with k = 0, all algorithms manage the coordination. Similarly, in the stochastic game with k = 0, all algorithms except for distributed Q-learning succeed. Indeed, an easy way to put Distributed Q-learning agents in the wrong is to insert stochastic rewards. So distributed Q-learning never manages the coordination in the partially stochastic Boutilier's game. When mis-coordination penalties are introduced in the deterministic game, decentralized Q-learning and WoLF-PHC fail because of shadowed equilibria. Distributed Qlearning, hysteretic Q-learning and SOoN succeed in the coordination. But in the stochastic version with k = -100, SOoN is the only one to be close to 100% of optimal joint action.

So SOoN gets best convergence results. In deterministic games, it turns towards the Distributed Q-learning. In the stochastic Boutilier's game without penalties, it turns towards the decentralized Q-learning. In the stochastic game with penalties, SOoN outperforms all other algorithms. The linear interpolation to evaluate state-action couples is a pertinent heuristic to measure real values of actions.

Two predators pursuit domains

The pursuit problem is a popular multi-agent domain in which some agents, called predators, have to capture one or several preys in a gridworld [START_REF] Benda | On optimal cooperation of knowledge sources -an experimental investigation[END_REF]. In the two agents pursuit domains, predators have to explicitly coordinate their actions in order to capture a single prey in a discrete 10 × 10 toroidal grid environment (Fig. 6a). At the beginning of each trial, predators and prey are set up in distinct random positions. At each time step, all predators simultaneously execute one of the 5 possible actions : move north, south, east, west or stand still. Moreover, noise is added to the environment through uncertainty in actions results. Any action moves a predator in the intended direction with probability 0.8, and otherwise a random action is applied. The prey moves according to a randomized policy : it remains on its current position with a probability of 0.2, and otherwise moves to ones of its free adjacent cells with uniform probability. A prey is captured when both predators are located in cells adjacent to the prey, and one of the two predators moves to the location of the prey while the other predator remains, for support, on its current position (Fig. 6b). A trials ends when the prey is captured.

The state space is represented by the relative position of the two predators to the prey. So each IL computes a Q i table with 99 × 98 × 5 values, i.e. 48510 different state-action pairs for each of both agents. A capture results in a reward R = 10 for every agent, and predators and prey are replaced to distinct random positions. Furthermore, predators receive penalties in case of mis-coordination. They both receive a penalty of -50 when one of them moves to the prey without support or when they end up in the same cell. Then both are moved to a random, empty cell. In all other situations, the reward is 0.

The main factors which complicate the coordination are action shadowing induced by penalties and the stochastic environment due to the random behavior of the prey and the uncertainty in actions results.

A trial consists of 10000 steps. We make out learning trials and greedy trials in which agents are following their learned greedy policies. After each learning trial is done a greedy trial. For each greedy trial, we plot the number of captures per trial and the sum of received rewards per agent during the trial. With the number of captures per trial, we can compare greedy policies learned with each algorithm; with the sum of received rewards, the number of collisions or non-support is observed. Results obtained on 10000 greedy trials are given in figure 7. We can notice that :

• greedy policies learned by decentralized Q-learning fail to coordinate,

• there is the same number of capture with WoLF-PHC and hysteretic Q-learning, but the second one creates less collisions,

• despite the stochastic environment, greedy policies learned by distributed Q-learning manage the coordination with around 45 captures per trial. However, collisions are not much avoided,

• SOoN gets best results. After around 4500 trials, it outperforms distributed Q-learning. Two phases can be identified : during a first phase, SOoN behaves as distributed Qlearning (2000 first trials). Indeed, agents are initially optimistic. This first stage is in some way an adaptative phase to the environment; the frequency refines according to the stochasticity of the environment. Then evaluations swing between optimistic or neutral. The second phase is when SOoN manages the coordination : the number of captures increases and overcome all other results. So SOoN realizes an automatic adaptation to the environment.

Four agents pursuit domains

In the four agents pursuit domains, four predators have to coordinate their actions in order to surround a single prey in a discrete 7×7 toroidal grid environment (Fig. 8a). Agents observations suffer from low resolution. Indeed, a predator perceives the others according to the 8 cardinal directions and a close or distant criterion (Fig. 8b), so 16 perceptions. Given that each predator perceives its 3 teammates plus the prey, there are 16 8c, every agent receives R = 25. When the prey is captured, they each receive R = 100. The low resolution in the perception induces stochasticity in the environment so the main factor here which complicates the coordination of predators is the noise. A trial consists of 1000 steps. We make out learning trials and greedy trials in which agents are following their learned greedy policies. After each learning trial is done a greedy trial. For each greedy trial, we plot the number of captures per trial (Fig. 9). We can compare greedy policies learned with each algorithm. We can notice that :

• it is very difficult for distributed Q-learning to do the coordination. Indeed, optimistic agents capture the prey for the first time after 48000 trials, and they capture the prey 5 times per trial at 80000 trials. The low resolution in perceptions induces stochasticity in the environment which puts optimistic agents in the wrong,

• decentralized Q-learning shows interesting results in this stochastic environment. It confirms that this algorithm can be applied with success on some MAS and manages the coordination,

• WoLF-PHC is the first one to achieve captures but its performance increases slowly,

• hysteretic Q-learning manages first captures late, but its performance increases fast. It notably overcomes WoLF-PHC and is close to decentralized Q-learning after 80000 trials with around 60 captures per trial,

• SOoN gets best results. Two phases can be identified. During the first adaptative phase, agents are initially optimistic so SOoN does not manage any captures as distributed Qlearning. Then, once the frequency is fitted to the environment, the number of captures per trial increases. It is the second phase of coordination. After around 50000 trials, 90 captures are managed per trial. SOoN realizes an automatic adaptation to the environment.

We can also notice that greedy policies learned with SOoN and decentralized Q-learning are noised, unlike WoLF-PHC or distributed Q-learning policies. So even if SOoN realizes a fast and successful coordination, it is more sensitive to the stochasticity in this game.

Discrete smart surface with 270 agents

Given our real world application of a decentralized control of a smart surface, we have developed a discrete smart surface benchmark. The system is composed of 270 actuators organized in array (Fig. 10). At each time step, all actuators simultaneously execute one of the 5 possible actions : up, down, right, left or nop, represented by arrows and a circle. Uncertainty is added to actions results : with a probability 0.001, each actuator executes a random action. An object is situated on the surface. The motion of the object is proportional to the actions sum of the actuators which are under and by the object. The influence factor on the actions of the actuators by the object is three times higher than the influence factor on the actions of the actuators under the object. The object moves in the four cardinal directions but it does not rotate. Additionally, the object cannot get out of the surface and instead stays by the edge. The system's state is the index position of the object (according to its up and left corner). Each actuator is driven by an independent agent so it has only access to the index position and to its action. In real application, the full state observability can be done thanks to an overhead camera that extracts the index position. The goal is for the agents to cooperate so as to move the object to a goal position. Then, all agents receive R = 10 and the trial ends. If the object is getting closer to the vertical edges of the surface, every agent receives a penalty (R = -50). Otherwise, the reward is 0.

A trial starts with the object at its initial position and ends when the object reaches the goal position (absorbing state). For each trial, we plot the number of steps to the goal and the sum of received rewards per agent (Fig. 11). With the sum of received rewards, we can observe if the object is getting closer to the vertical edges of the surface. With the number of steps to the goal, we can check if the learned policies are close to best policy achieved "by hand"' which makes 3 steps per trial (without uncertainty). We can notice that :

• the environment is stochastic so distributed Q-learning fails to coordinate. Moreover, optimistic agents are unaware of penalties so they do not avoid edges of the surface; the sum of received rewards per trial is low,

• decentralized Q-learning shows interesting results : after 300 trials, 20 steps are required to reach the goal and the object is getting closer to the vertical edges around 4 times per trial. However, learned policies are not stable. Mis-coordination penalties and the lack of robustness face to exploration lead to destruction of individual policies. During the experimentations, we notice that agents coordinate to avoid edges : the object move round in circles in the area without penalties,

• hysteretic Q-learning is close to decentralized Q-learning. But as these agents are chiefly optimistic, they do not avoid as much the edges and the sum of rewards increases slowly,

• with WoLF-PHC, learned policies are stable but slow,

• after 300 trials, best results are obtained with SOoN : 12 steps are required to reach the goal and the object is getting closer to the vertical edges around once per trial. Moreover, these performances are achieved from 100 trials. Again two phases draw attention. The first phase of adaptation when agents are initially optimistic and so fails to move the object to the goal. Then, SOoN adapts its frequency to the environment : the number of steps to goal decreases. So the second phase is the coordination.

Conclusion

In this section, the objective was to design an algorithm for ILs, robust face to exploration and mis-coordination factors in cooperative Markov games. Starting from the recursive FMQ, we show that using a one-step lookahead with the myopic frequency in multi-stage games could mislead the algorithm. So we introduced the computation of a farsighted frequency to detect the stochasticity of the game. This frequency is used in a heuristic to evaluate state-action couples in the Swing between Optimistic or Neutral algorithm. This heuristic is based on a linear interpolation between optimistic or neutral evaluations. Thus, SOoN realizes an automatic adaptation to the environment stochasticity of its evaluations. Especially, two phases are characteristic of this method. An adaptative phase when the frequency detects the stochasticity. Indeed, at the beginning, agents are optimistic. If the environment is deterministic and the agents manage the coordination, agents stay optimistic. Otherwise, the frequency adjusts evaluations between optimistic or neutral. When these evaluations are adjusted, the second phase is the successful coordination of agents. These both phases have been illustrated with some experimentations on Markov games. They confirm that the linear interpolation is a pertinent evaluation of real values of state-actions. They also highlight that SOoN is able to overcome mis-coordination factors and is robust face to exploration.

Conclusion

In this report, we focused on the learning of independent agents in cooperative multi-agent systems. First, we highlighted some of the difficulties encountered by ILs in this framework. Especially, we analyzed some factors which complicate the ILs coordination : shadowed equilibria, equilibria selection and noise. These factors have been identified and interpreted in matrix games. The impact of the exploration has also been studied as a major stake in the reinforcement learning of ILs. Through a section suggesting a uniform notation, related algorithms based on Q-learning have been reviewed according to some factors : the robustness face to exploration, the learning of optimal individual policies despite shadowed equilibria and noise, and the selection of a single optimal equilibria. Thanks to this study, we focused on developing an algorithm robust face to the exploration strategy and able to overcome mis-coordination factors in cooperative Markov games. For that, we emphasized common points between FMQ heuristic and distributed Qlearning. On the one hand, distributed Q-learning is robust face to exploration and insured to converge toward a Pareto optimal Nash equilibrium in deterministic Markov games. On the other hand, FMQ outperforms the difficulty of weakly noisy matrix games by decoupling noise due to agents behaviors and noise due to the environment.

Thus, we contribute to improve the FMQ algorithm in matrix games and propose a recursive version which is easy-to-use, robust and able to solve hard repeated matrix games. We further proposer the SOoN algorithm, standing for "Swing between Optimistic or Neutral". Thanks to the computation of a farsighted frequency and to a novel evaluation of the state-action values, this algorithm sways automatically from optimistic to neutral evaluation according to a detection of the noise in the environment. At the beginning, the environment is supposed to be deterministic and so agents are optimistic. Then, the SOoN automatically adapts its frequency to the stochasticity of the environment through the assessment of the probability of attaining the optimal gain.

We specify the choice of the two parameters of the SOoN so as to obtain an algorithm robust face to the exploration. The noise due to agents behaviors has been defined with the global exploration. We demonstrate empirically the robustness and advantages of the SOoN algorithm [START_REF] Watkins | Technical note: Q-learning[END_REF] with GLIE partially Distributed total Q-Learning [START_REF] Lauer | An algorithm for distributed reinforcement learning in cooperative multi-agent systems[END_REF] Lenient learners [START_REF] Panait | Lenient learners in cooperative multiagent systems[END_REF] NT NT NT low Hysteretic low Q-Learning [START_REF] Laetitia Matignon | Hysteretic q-learning :an algorithm for decentralized reinforcement learning in cooperative multi-agent teams[END_REF] with GLIE partially WoLF PHC [START_REF] Bowling | Multiagent learning using a variable learning rate[END_REF] NT good FMQ [START_REF] Kapetanakis | Reinforcement learning of coordination in cooperative multi-agent systems[END_REF] low with GLIE partially

Recursive FMQ good partially SOoN good partially on a number of multiple states cooperative Markov games with numerous agents. Results show that this algorithm overcomes all mis-coordination factors, even weakly noise Markov games, and is robust face to the exploration strategy (table 13). The SOoN manages the coordination thanks to two characteristic phases : an adaptative phase where the frequency automatically fits to the stochasticity, and the coordination phase where the agents coordinate themselves. Moreover, results confirm that the linear interpolation can be a pertinent evaluation of real values of state-action couples, especially in stochastic games.

Our research has raised a number of issues to be investigated in on-going and future work. The first perspective is to test the SOoN algorithm on a real problem as the decentralized control of a smart surface.

The second perspective is to improve the proposed evaluation of action. Indeed, we presented encouraging experimental results, but the proposed linear interpolation to evaluate a stateaction couple could be modified. Specifically, a bound for the farsighted frequency could be defined to mark optimistic or neutral evaluation out.

An other prospect concerns a common issue in RL of making algorithms scale to large problems. Indeed, the SOoN algorithm uses explicit table representations of Q, Q max and frequency functions. In larger state-action spaces application scenarios, explicit table representations become intractable. So it would be interesting to generalize and approximate these tables with some kind of function approximation mechanism. So an interesting direction of this work is to combine function approximation mechanism with the SOoN algorithm.

Figure 1 :

 1 Figure 1: Average rewards received in the Climbing game by FMQ agents (c = 10) with τ = e 0.006×k × 499 + 1.

Figure 2 :

 2 Figure 2: Frequency values of agent 1 vs. the number of repetitions of the game and according FMQ algorithm. Actions chosen by the agents are in the diagram above the curve.

Figure 3 :

 3 Figure 3: Two agents cooperative Markov game

Figure 4 :

 4 Figure 4: Two agents cooperative Markov game experiments with 10 states averaged over 200 runs (α = 0.1, γ = 0.9, α f = 0.05, α g = 0.3, = 0.05). Steps to goal vs. trial number.

Figure 5 :

 5 Figure 5: Boutilier's coordination game.

  (a) Complete 10 × 10 toroidal grid. (b) Possible capture position.

Figure 6 :

 6 Figure 6: Two predators pursuit problem.

Figure 7 :

 7 Figure 7: Number of captures and sum of received rewards per agent for 10000 steps (averaged over 20 runs) with α = 0.1, β = 0.01, α f = 0.01, α g = 0.3, δ lose = 0.06, δ win = 0.03, γ = 0.9.

Figure 8 :Figure 9 :

 89 Figure 8: Four predators pursuit problem. a) The prey is captured. b) (2 × 8) 4 perceptions per agent. c) The reinforcement is attributed in an individual way and is only function of local perceptions (and similar situations obtained by rotation of 90 • ).

Figure 10 :

 10 Figure 10: Discrete smart surface benchmark with 9 × 30 agents.

Figure 11 :

 11 Figure 11: Steps to goal (on the top) and sum of rewards received at each trial by an agent (on the bottom) vs. trial number (averaged over 100 runs and logarithmic scale). α = 0.1, α f = 0.01, α g = 0.3, γ = 0.9 and = 0.0005.

Table 1 :

 1 Fully cooperative game example.

	Agent 2
	a	b
	Agent 1 a 2	0
	b 0	1

Table 2 :

 2 Simple cooperative matrix game.

	Agent 2
	a b c
	a 5 3 1
	Agent 1 b 4 1 1
	c 1 1 0

Table 6 :

 6 Percentage of trials which converged to the optimal joint action (averaged over 500 trials). Entries marked with "NT" indicate it has not been tested.

		Decentralized Distributed Hysteretic FMQ
		Q-learning	Q-learning Q-learning
	Simple cooperative	100%	100%	100%	100%
	game
	Climbing game	3%	100%	100%	100%
	Penalty game	96%	100%	100%	100%
	(k = -100)
	Partially stochastic	NT	7%	82%	98%
	Climbing game
	Fully stochastic	NT	NT	0%	21%
	Climbing game

Table 7 :

 7 Characteristics of RL algorithms for independent learners in cooperative games. Entries marked with "NT" indicate it has not been tested.

	Matrix	Games	Markov	Games	Equilibria	Selection	Shadowed	Equilibria	Stochastic	environment	Robust face	to exploration
	Decentralized										low
	Q-Learning

Table 10 :

 10 Percentage of trials which converged to the optimal joint action (averaged over 500 trials). A trial consists of 5000 repetitions of the game. The exploration strategy is stationary. We set α = 0.1, α f = 0.01 and = 0.05. At the end of each trial, we determine if the greedy joint action is optimal (x%) or sub-optimal (y%). Results are noted x%[y%]. α f ). So if α f is too much high, occurrence frequencies can be "destroyed" by exploration of others. α f must be chosen all the smaller as the global exploration is high.

		Simple game Penalty game		Climbing game
			(k = -100)	deterministic partially stochastic fully stochastic
	recursive	100%	100%	100%	100%	56% [3%]
	FMQ
	frequency decreases according to (1

Table 11 :

 11 Percentage of trials which converged to the optimal joint action in Penalty game with n > 2 agents (averaged over 500 trials). Chosen parameters are specified in Appendix B. At the end of each trial, we determine if the greedy joint action is optimal (x%) or sub-optimal (y%).

	Results are noted x%[y%].
			Decentralized	Distributed	WoLF	Recursive
			Q-learning	Q-learning	PHC	FMQ
	n =	deterministic 100% [0%] 100%	[0%]	100%	[0%]	100% [0%]
	3	stochastic	98%	[2%]	0%	[100%] 87%	[13%]	99% [1%]
	n =	deterministic 100% [0%] 100%	[0%]	100%	[0%]	91% [9%]
	4	stochastic	6%	[94%]	0%	[100%]	0%	[100%] 92% [8%]
	n =	deterministic 100% [0%] 100%	[0%]	100%	[0%]	97% [3%]
	5	stochastic	10% [90%]	0%	[100%]	1%	[99%]	94% [6%]

  a) arbitrarily s ← initial state while s is not an absorbing state doFrom s select a according to the -greedy selection method based on π i Apply a and observe reward r and next state s

  At each state, each agent has a choice of two actions. The transitions on the diagram are marked by a pair of corresponding actions, denoting player 1's move and player 2's move respectively. " * " is a wild card representing any action. States that yield a reward are marked with the respective value. All other states yield a reward of 0.

		100%	6%	100%	12%
	Distributed Q-learning	100%	100%	0%	0%
	WoLF-PHC	100%	36%	100%	40%
	Hysteretic Q-learning	100%	100%	100%	30%
	SOoN	100%	100%	100%	96%
	easily be integrated and combined.

  4 possible observations per agent. Each agent has 5 possible actions, i.e. a Q i -table of size 16 4 × 5 for each predator. Concerning the reinforcement function, if at least one agent is in the situation in figure

Table 13 :

 13 Characteristics of RL algorithms for independent learners in cooperative games. Entries marked with "NT" indicate it has not been tested.

	Matrix	Games	Markov	Games	Equilibria	Selection	Shadowed	Equilibria	Stochastic	environment	Robust face	to exploration
	Decentralized										low
	Q-Learning

also called stochastic game.

also called Multi-agent Markov Decision Process (MMDP).

A greedy policy based on Qi is to select in a state s the action a for which Qi(s, a) is highest.

Greedy in the limit with infinite exploration.

Rewards are supposed to be non-negative.

Rewards are supposed to be non-negative.

Appendix A :

The following were the learning and decay rates used for the results presented in §4. Here t is the number of repetitions of the game. With the detailed algorithmic descriptions in section 4 and these parameters details, all of the presented results are reproducible.

Appendix B :

In the Penalty game with n > 2 agents, each agent has 3 actions a, b and c. If half agents or more play a and the others play c, the received reward is 10. If less than half agents play a and the others play c, the received reward is -100 since they fail to coordinate. If half agents or more play b and the others play c, the received reward is 2. Otherwise, the reward is 0. There are many Pareto optimal Nash equilibria when half agents or more play a and the others play c. These optimal equilibria are shadowed by penalties in case of mis-coordination. There are also many sub-optimal Nash equilibria when half agents or more play b and the others play c. So this game presents mis-coordination factors. Additionally, the reward can be noised : instead of receiving a reward equal to 2, 12 and 6 are received with equal probabilities.

The following were the learning and decay rates used for the results presented in §6.2. Here t is the number of repetitions of the game. With the detailed algorithmic descriptions and these parameters details, all of the presented results are reproducible.

• decentralized Q-learning

Appendix C :

The following is the description of the cooperative Markov game in figure 3. Each agent has a choice of two actions a and b. The game starts in state s 1 . The transitions on the figure are marked by a pair of corresponding actions, denoting agent 1's action and agent 2's action respectively. " * " is a wild card representing any action. So if both agents are coordinated on the joint action < a, a > in the state s k , they move to the next state s k+1 . If at least one agent plays b, they remain on the spot. When agents reach the absorbing state s j , they receive a reward 10. All other states yield a reward of 0.