On Efficient Sampling for Multi-Agent Reinforcement Learning in Supply Demand Matching

A critical question in multi-agent reinforcement learning (MARL) is what the agents may share with each other, and how to utilize the information shared by others. A key challenge is to provide mathematical analysis on this issue rather than just ad hoc numerical analysis. Though mathematical analysis in general might be challenging, the particular structural property of supply demand matching problems might provide a clue. We consider this important issue in this work, and make the following major contributions. First, we formulate the sample allocation problem to optimize the performance of the policy learned by the multiple agents in supply demand matching problems, and convert the problem to the maximization of the probability of correctly selecting (PCS) the best action at a given state. Second, we provide an algorithm to iteratively allocate the sample budget across the action space to best learn from the other agents. Third, we show that this algorithm asymptotically maximizes the PCS. And we prove that under certain conditions, this algorithm strictly improves this PCS comparing with not sharing. We hope that this work sheds light on quantifying how knowledge shall be shared and digested in MARL.