In Algorithm , in lines \(4-13\)  the algorithm updates the sample sets with the newly collected samples awaiting in list \(Z\) . In order to maintain the collected samples independent, for each state-action, the algorithm first waits for \(2^{p}k_{m}\)  new samples to be gathered for some parameter \(k_{m}\)  and integer \(p\) , before replacing the old sample set \(u(s,a)\)  with the new samples. To keep the computational and space complexity bounded, we limit the size of the sample set to no more than \(k\) , where \(k/k_{m}\)  is some power of 2. Given that there was an update of some sample set, the algorithm performs value iteration on lines \(15-17\)  with convergence up to a factor of \(\epsilon _{a}\) , and then publishes noisy copies of the \(Q\) -function for all agents. The approximate Bellman operator \(\widetilde{B}\)  uses the median of means trick to estimate the mean-value for the collected samples [1]}, [2]}, [3]}, and is defined in Appendix . In this regard, \(k_{m}\)  is the number of groups we divide the samples to in a sample set, in order to calculate the median. Note that if the learner does not update the \(Q\) -function on a given time-step, it does not re-publish it, and the agents continue using the latest published table. Recently, it was shown that in order to perform efficient cooperative exploration by multiple agents, a given agent should not change its policy at every time-step, but `commit' to a fixed policy expressing the exploration of a given part of the world for a limited amount of time [4]}, which agrees with our algorithm.
