Autonomous Agents and Distributed Intelligence Laboratory

Difference evaluation functions have resulted in excellent multiagent behavior in many domains, including air traffic control, mobile robot control, and distributed sensor network control. In addition to empirical evidence, there is theoretical evidence that suggests difference evaluation functions help shape private agent utilities/objectives in order to promote coordination on a system-wide level. However, calculating difference evaluation functions requires determining the value of a counterfactual system objective function in which an agent took an alternate action. That step is often difficult when the system objective function is unknown or global state and action information is unavailable. In this work, we demonstrate that a local estimate of the system evaluation function may be used to locally compute difference evaluations using no more information than when using global evaluation functions, allowing for difference evaluations to be computed in multiagent systems where the mathematical form of the objective function is not known. This approximation technique is tested in two domains, and we demonstrate that approximating difference evaluation functions results in better performance and faster learning than when using global evaluation functions.