nips nips2002 nips2002-78 nips2002-78-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Ronen I. Brafman, Moshe Tennenholtz
Abstract: We introduce efficient learning equilibrium (ELE), a normative approach to learning in non cooperative settings. In ELE, the learning algorithms themselves are required to be in equilibrium. In addition, the learning algorithms arrive at a desired value after polynomial time, and deviations from a prescribed ELE become irrational after polynomial time. We prove the existence of an ELE in the perfect monitoring setting, where the desired value is the expected payoff in a Nash equilibrium. We also show that an ELE does not always exist in the imperfect monitoring case. Yet, it exists in the special case of common-interest games. Finally, we extend our results to general stochastic games. 1
[1] R. I. Brafman and M. Tennenholtz. R-max - a general polynomial time algorithm for near-optimal reinforcement learning. In IJCAI'Ol, 200l.
[2] R. I. Brafman and M. Tennenholtz. Efficient learning equilibrium. Technical Report 02-06, Dept. of Computer Science, Ben-Gurion University, 2002.
[3] C. Claus and C. Boutilier. The dynamics of reinforcement learning in cooperative multi-agent systems. In Proc. Workshop on Multi-Agent Learning, pages 602- 608, 1997.
[4] I. Erev and A.E. Roth. Predicting how people play games: Reinforcement learning in games with unique strategy equilibrium. American Economic Review, 88:848- 881, 1998.
[5] D. Fudenberg and D. Levine. The theory of learning in games. MIT Press, 1998.
[6] D. Fudenberg and J. Tirole. Game Theory. MIT Press, 1991.
[7] J. Hu and M.P. Wellman. Multi-agent reinforcement learning: Theoretical framework and an algorithms. In Proc. 15th ICML , 1998.
[8] L. P. Kaelbling, M. L. Littman, and A. W. Moore. Reinforcement learning: A survey. Journal of AI Research, 4:237- 285, 1996.
[9] M. L. Littman. Markov games as a framework for multi-agent reinforcement learning. In Proc. 11th ICML, pages 157- 163, 1994.
[10] L.S. Shapley. Stochastic Games. In Proc. Nat. Acad. Scie. USA, volume 39, pages 1095- 1100, 1953.