Hi,

You can see your problem as a dynamic game. The multiple agents interact with the environment but also among them.

Thus, from the point of view of a single agent, the actual environment is composed of what you call the environment together with the other agents. This point is very important. In other words, for one single agent, the rest of agents are also part of the environment.

Now, the problem is that since the rest of agents are learning, their behavior policy may change with time. Therefore, the problem is non-stationary anymore and you cannot use Q-learning in the single agents.

There are different ways to overcome this problem. For instance, If the dynamic game is potential, then you can find a single equivalent control problem. However, although potential games have many applications, it might not be the case for your problem.

Perhaps, you could also consider that the agents learn in a fully off-policy fashion. This way, they behave always the same (i.e., their policy is stationary), while they are also able to learn the optimal policy. Indeed, this is an idea I am working on for dynamic games. By the way, do you use value function approximation? 

Finally, you could also review the literature on Nash-Q and other forms of multiagent-Q-learning to see whether your game fits under the assumptions of these algorithms.

Hope this helps!

Thanks dear Sergio,

As you said, “for one single agent, the rest of agents are also part of the environment.”. I did pay attention to this point!  But, all the agents are homogenous. So, the learned policy for all of them must be the same. That’s the reason that I used a single QTable for all of them.

Fortunately, I managed to solve the mentioned problem in my question! As I said, I’ve used a shared QTable for all the agents so that at each time step each agent can update entries of this table. But, the conflict is met when two agents are supposed to assign two different values to an entry! In this case, I’ll randomly retain one of these Q-values so that all the agents caused conflict will use this value. I doubt whether it is correct or not. But, I guess it’s right, although the solution might not have the most efficient convergence speed!

Would you mind telling me whether this is correct or not? If not, what’s your suggested solution?

I were wondering if other ones also could get involved in our conversation.

I think your intuition that multiple homogeneous agents could be considered as just one agent from the Q-learning point of view could be incorrect. 

So, my first suggestion would be: try to proof your intuition. This will be an interesting exercise that will help you to grasp your problem better. Who knows? perhaps your problem belongs to a class of games for which your intuition holds.

Indeed, if you consider a very large (i.e., asymptotically infinite) number of homogeneous agents, you could model the problem as a mean-field game.

But I do not think this holds in the general case. 

Do the state dynamics and each player's utility depend on the actions of every other player? If so, this means that you have a set of coupled control problems (rather than one single multivariate control problem) and, thus, there is no even a clear solution concept because what could be good for one agent may be bad for another (even if they are homogeneous, other environmental factors, e.g., location, could break the symmetry). So in this case, what do you mean by solving your problem? You may have in terms of finding a Nash equilibrium, or a Pareto optimal point, etc.

I also suggest you to have a look at this draft:

https://www.researchgate.net/publication/281576649_Dynamic_Potential_Games_in_Communications_Fundamentals_and_Applications

Best!!!

Article Dynamic Potential Games With Constraints: Fundamentals and A...

Hi Negin,

You can use blackboard communication strategy. Keep the q-table in a shared memory inside a central unit. Each learning agent can precive its own environment and act seperatly while update a shares q-table. Note that, in this situation the reward is a global reward comprising of the sum of the rewards of all the individual learning agents. For more details you can request one of my papers has been published as a poster in ICAC 2015. And also you can wait for the extended version will be appeard soon in my profile.

Best,

Seyed Saeid

Bonjour Negin,

For me, you try to deal with 2 dilemma:

The first is about a big shared table of Q-values against several tables of Q-Values (that you need or not to aggregate later) like maybe one table by agent (ie a single Q-learning but on multiple areas of the environment).

The second is about the distributed architecture of agents: the parallelism of agents processing (fully autonomous) against a controlled scenarios of agents with a kind of scheduler (semi-autonomous) to fill a common Q-table.

What is your justified choice?

Thanks all,

Dear Sébastien, you posed two challenges:

About the first challenge: At first, agents choose their actions. Then, we pause the time of simulation till agents update their state, sequentially. Next, we will increase time of simulation by one unit.

About the second challenge: As I said before, I’ve used a shared QTable for all the agents so that at each time step each agent can update entries of this table. But, the conflict is met when two agents are supposed to assign two different values to an entry! In this case, I’ll randomly retain one of these Q-values so that all the agents caused conflict will use this value. I doubt whether it is correct or not. But, I guess it’s right, although the solution might not have the most efficient convergence speed! What is your idea about this?

Dear Negin,

Thank you for your clear explanation. I have few questions for you:

How several agents can update the same Q-Value? do you mean that they have the same state and/or the same action in the same context? Maybe it would be better to split the environment and affect parts of the environment to agents but it is too simple that way.

Is your quality Q:SxA ->IR ? If it is the case, you cannot have 2 agents in the same position, logically. For instance, if agents are planes or in planes, they should have a Z-position (altitude) in the state Sk(xk,yk,zk). However they can choose the same action Ak in different states Sk.

You can simply add a constraint in your agent algorithm: don't go to a occupied position. then you have no redundancy in your program.

Convergence rate should be calculated on GPU or parallel machines, or you can evaluate the complexity of algorithm in term of Space & Time, I think parallel agents should speed your algorithm like GPU for Pictures or Video. For sure, You cannot measure convergence time on a single CPU.

Dear Sébastien

In our case, when some agents have the same state and action can update the same Q-value.  You’re right, we can’t have 2 agents in the same position at the same time. Actually, the position of an agent is not a part of its state space.

Using GPU or something like that is a good idea. But, our model is not real time, and time is not a critical issue in our model.

Considering all condition above, what is your suggested method to update QTable? Do you still think our approach is wrong?

I don't think your approach is wrong, it's a good idea to improve Q-learning with multiple agents but in terms of research, you should compare your work with state of the art and show your improvements with graphs. My questions were here to help you to compare. In brief, what makes your algorithm better? Complexity calculation helps to measure differences.

I mean that if your algorithm is equivalent to one agent a time and a space, then multiply agents is not so necessary even if it can be useful for Ambient intelligence but is it relevant for the final application?

I can help you only after reading your article or results.

See this state of the art:

https://www.google.fr/search?q=q+learning+multi+agent+shared+Q+table

This presentation from MIT will help you:

http://web.mit.edu/larsb/Public/16.412/Advanced%20Lecture/Lecture5.ppt

Cheers

Dear Sébastien,

I would like to thank you for your helpful resources! I studied the MIT presentation. They suggested a method for cooperation between agents by sharing policy. In their model, agents average their policy at certain frequency. I think it’s a good idea. Actually, I’ve thought of it that way. But, I guessed some mathematical proof is needed to use this approach. Now, I’ll probably use this approach.

The thing is I don’t want to use Q Learning anymore. I want to use TD with function approximation (for continuous states), instead. I’ll use gradient-descent Sarsa (lambda) given in Figure 8.8 of the book "Reinforcement Learning: An Introduction", by Sutton and Barto. So, do you think agents can share the same policy in this case as well? If so, do you think agents can average their policy in the case of same features or change the shared policy sequentially at each time step?

Thanks in advance

Hi Negin,

Take time to think to your assumptions. It's your research ;-) Think of the final application and thus the problem to solve. don't forget the state of the art to not reproduce an existing solution. I know it's a long work but take only 5 to 3 years old papers.I like your idea (last question).

Personally, I think a good idea will be one agent-one policy with each agent have a different policy. And the global policy is to make them solve a big problem or at the end, you should obtain the best agent with the best policy. More you have agents, more your algorithm can improve general policy. It's a sort of pareto, genetic algo or Nash Equilibrium. You see? TD is used for long lifetime agent.

https://webdocs.cs.ualberta.ca/~sutton/  => Course

https://www.dropbox.com/sh/3xowt7qvyadvejn/AAC0zLkJrEF6KhIbsWpZhwYfa?dl=0

You can download without login.

The previous algorithms of Sutton and Barto are made for one agent trying to improve its own policy (state-action transition function depending of a starting state and a final state) in term of optimality. If agents share the same policy, what is the refinement you propose? They share or they build a policy? what will be your improvement criteria to ensure your learning is efficient?

Thanks dear Sébastien

https://www.hindawi.com/journals/complexity/2018/7172614/

http://users.isr.ist.utl.pt/~mtjspaan/readingGroup/learningNeto05.pdf

http://www.aamas-conference.org/Proceedings/aamas2010/pdf/01%20Full%20Papers/06_01_FP_0040.pdf