While there are various learning methods that can be used in cooperative MAS systems, we focus on Reinforcement Learning (RL) which has demonstrated impressive recent success in many domains, notably game playing [1]}, and, more specifically, on Multi Agent RL (MARL). In standard Model Free (MF) RL, a learner aims to develop an optimal policy based on interaction with the environment through state observations and action selection. While there have been many heuristic algorithms suggested for cooperative MARL [2]}, [3]}, [4]}, theoretical results are lacking, and there are even fewer of them in the restricted communication setting. Works analyzing the exploration efficiency of RL algorithms usually use either Probably Approximately Correct (PAC) performance measures [5]}, [6]}, [7]}, or regret bounds [8]}. In this paper we focus on the former, in which there are a few results known for the unlimited communication MARL case [9]}, [10]}, but no results for the restricted communication case have been established to the best of our knowledge.
