Communicating with Unknown Teammates

Past research has investigated a number of methods for co-ordinating teams of agents, but with the growing number of sources of agents, it is likely that agents will encounter team-mates that do not share their coordination methods. There-fore, it is desirable for agents to adapt to these teammates, forming an effective ad hoc team. Past ad hoc teamwork re-search has focused on cases where the agents do not directly communicate. However when teammates do communicate, it can provide a valuable channel for coordination. Therefore, this paper tackles the problem of communication in ad hoc teams, introducing a minimal version of the multiagent, multi-armed bandit problem with limited communication between the agents. The theoretical results in this paper prove that this problem setting can be solved in polynomial time when the agent knows the set of possible teammates. Furthermore, the empirical results show that an agent can cooperate with a variety of teammates following unknown behaviors even when its models of these teammates are imperfect.