Efficient Collaboration with Unknown Agents: Ignoring Similar Agents without Checking Similarity

Ad hoc teamwork (AHT) is concerned with developing an AI agent who learns to collaborate with different previously unseen partners. We consider a setting where the AI agent is provided with a hypothesis set of partners' policies. Several online algorithms that take the hypothesis set as input can be applied to solve the AHT problem. One way to speed up these online learning algorithms is to eliminate the redundant policies, i.e., partner models sharing the same collaborating policy, from the hypothesis set. Nevertheless, we show whether this elimination should be applied depends on the learning algorithm used by the AI agent. Specifically, we identify a property of a learning algorithm: redundancy-aware. When the learning algorithm is redundancy-aware, redundancy elimination is unnecessary. In other words, redundancy-aware algorithms can ignore similar agents in the hypothesis set. We demonstrate through an example that an online algorithm with redundancy-aware property exists when the hypothesis set contains the true partner policy. We test our approach on a team Markov game of two players. Comparative numerical analyses reveal that the redundancy-aware algorithm outperforms other standard no-regret learning algorithms including upper confidence bound (UCB), Q-learning with UCB exploration, and the optimistic posterior sampling algorithm when the set of partner policies contains many redundant policies.