Peter Stone
ABSTRACT
In typical multiagent teamwork settings, the teammates are either programmed together, or are otherwise provided with standard communication languages and coordination protocols. In contrast, this paper presents an ad hoc team setting in which the teammates are not pre-coordinated, yet still must work together in order to achieve their common goal(s). We represent a specific instance of this scenario, in which a teammate has limited action capabilities and a fixed and known behavior, as a finite-horizon, cooperative k-armed bandit. In addition to motivating and studying this novel ad hoc teamwork scenario, the paper contributes to the k-armed bandits literature by characterizing the conditions under which certain actions are potentially optimal, and by presenting a polynomial dynamic programming algorithm that solves for the optimal action when the arm payoffs come from a discrete distribution.
- D. Bergemann and J. Valimaki. Bandit problems. Technical report, Cowles Foundation Discussion Paper, 2006.Google Scholar
- P. Bolton and C. Harris. Strategic experimentation. Econometrica, 67:349--374, 1999.Google ScholarCross Ref
- R. I. Brafman and M. Tennenholtz. On partially controlled multi-agent systems. JAIR, 4:477--507, 1996. Google ScholarDigital Library
- H. Chalupsky, Y. Gil, C. Knoblock, K. Lerman, J. Oh, D. Pynadath, T. Russ, and M. Tambe. Electric elves: Applying agent technology to support human organizations. In IAAI, 2001. Google ScholarDigital Library
- C. Claus and C. Boutilier. The dynamics of reinforcement learning in cooperative multiagent systems. In AAAI, pages 746--752, 1998. Google ScholarDigital Library
- M. Cripps, G. Keller, and S. Rady. Strategic experimentation with exponential bandits. ECONOMETRICA, 73:39--68, 2005.Google ScholarCross Ref
- J. A. Giampapa, K. Sycara, and G. Sukthankar. Toward identifying process models in ad hoc and distributed teams. In K. V. Hindriks and W.-P. Brinkman, editors, HuCom, pages 55--62, December 2008. Google ScholarDigital Library
- B. J. Grosz and S. Kraus. Collaborative plans for complex group actions. AIJ, 86:269--358, 1996. Google ScholarDigital Library
- L. ji Lin. Self-improving reactive agents based on reinforcement learning, planning and teaching. MLJ, 8(3/4):293--321, 1992. Google ScholarDigital Library
- J. Just, M. Cornwell, and M. Huhns. Agents for establishing ad hoc cross-organizational teams. In International Conference on Intelligent Agent Technology, pages 526--30, September 2004. Google ScholarDigital Library
- A. Kayay. When does it pay to get informed? International Economic Review, 2009. forthcoming.Google Scholar
- R. Kildare. Ad-hoc online teams as complex systems: agents that cater for team interaction rules. In Proceedings of the 7th Asia-Pacific Conference on Complex Systems, December 2004.Google Scholar
- R. D. Kleinberg. Online Decision Problems. PhD thesis, Department of Mathematics, MIT 2005.Google Scholar
- L. Panait and S. Luke. Cooperative multi-agent learning: The state of the art. JAAMAS, 11:387--434, 2005. Google ScholarDigital Library
- H. Robbins. Some aspects of the sequential design of experiments. Bulletin American Mathematical Society, 55:527--535, 1952.Google ScholarCross Ref
- A. Schaerf, Y. Shoham, and M. Tennenholtz. Adaptive load balancing: A study in multi-agent learning. JAIR, 2:475--500, 1995. Google ScholarDigital Library
- P. Stone and M. Veloso. Task decomposition, dynamic role assignment, and low-bandwidth communication for real-time strategic teamwork. AIJ, 110(2):241--273, June 1999. Google ScholarDigital Library
- P. Stone and M. Veloso. Multiagent systems: A survey from a machine learning perspective. Autonomous Robots, 8(3):345--383, July 2000. Google ScholarDigital Library
- R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA, 1998. Google ScholarDigital Library
- K. Sycara, K. Decker, A. Pannu, M. Williamson, and D. Zeng. Distributed intelligent agents. IEEE Expert, 11(6), December 1996. Google ScholarDigital Library
- H. Zhang, Y. Chen, and D. Parkes. A general approach to environment design with one agent. In IJCAI, 2009. Google ScholarDigital Library
Index Terms
- To teach or not to teach?: decision making under uncertainty in ad hoc teams
Recommendations
Autonomy-oriented computing (AOC): formulating computational systems with autonomous components
Autonomous multientity systems are plentiful in natural and artificial worlds. Many systems have been studied in depth and some models of them have been built as computational systems for problem solving. Central to these computational systems is the ...
Autonomous Learning Agents: Layered Learning and Ad Hoc Teamwork
AAMAS '16: Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent SystemsIn order to achieve long-term autonomy in the real world, fully autonomous agents need to be able to learn, both to improve their behaviors in a complex, dynamically changing world, and to enable interaction with previously unfamiliar agents. This talk ...
Teaching and leading an ad hoc teammate: Collaboration without pre-coordination
As autonomous agents proliferate in the real world, both in software and robotic settings, they will increasingly need to band together for cooperative activities with previously unfamiliar teammates. In such ad hoc team settings, team strategies cannot ...
Comments