Efficient learning of multi-step best response

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient learning of multi-step best response

Full text

Pdf (307 KB)

Source

International Conference on Autonomous Agents archive
Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems table of contents

The Netherlands

SESSION: Papers: learning table of contents

Pages: 60 - 66

Year of Publication: 2005

ISBN:1-59593-093-0

Authors

Bikramjit Banerjee	Tulane University, New Orleans, LA
Jing Peng	Tulane University, New Orleans, LA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 25, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1082473.1082483 What is a DOI?

ABSTRACT

We provide a uniform framework for learning against a recent history adversary in arbitrary repeated bimatrix games, by modeling such an agent as a Markov Decision Process. We focus on learning an optimal non-stationary policy in such an MDP over a finite horizon and adapt an existing efficient Monte Carlo based algorithm for learning optimal policies in such MDPs. We show that this new efficient algorithm can obtain higher average rewards than a previously known efficient algorithm against some opponents in the contract game. Though this improvement comes at the cost of increased domain knowledge, a simple experiment in the Prisoner's Dilemma game shows that even when no extra domain knowledge (besides that the opponent's memory size is known) is assumed, the error can still be small.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	R. Axelrod. The Evolution of Cooperation. Basic Books, 1984.
	2	J. A. Bagnell, S. Kakade, A. Y. Ng, and J. Schneider. Policy search by dynamic programming. In Advances in Neural Information Processing Systems 16. MIT Press, 2003.
	3	B. Banerjee and J. Peng. Performance bounded reinforcement learning in strategic interactions. In Proceedings of the 19th National Conference on Artificial Intelligence (AAAI-04), pages 2--7, San Jose, CA, 2004. AAAI Press.
	4	Dimitri P. Bertsekas, Dynamic Programming and Optimal Control, Two Volume Set, Athena Scientific, 2001
	5	Multiagent learning using a variable learning rate, Artificial Intelligence, v.136 n.2, p.215-250, April 2002 [doi>10.1016/S0004-3702(02)00121-2]
	6	Ronen I. Brafman , Moshe Tennenholtz, R-max - a general polynomial time algorithm for near-optimal reinforcement learning, The Journal of Machine Learning Research, 3, p.213-231, 3/1/2003
	7	D. Carmel and S. Markovitch. Learning models of intelligent agents. In Thirteenth National Conference on Artificial Intelligence, pages 62--67, Menlo Park, CA, 1996. AAAI Press/MIT Press.
	8	David Carmel , Shaul Markovitch, How to Explore your Opponent's Strategy (almost) Optimally, Proceedings of the 3rd International Conference on Multi Agent Systems, p.64, July 03-07, 1998
	9	D. Carmel and S. Markovitch. Model-based learning of interaction strategies in multiagent systems. Journal of Experimental and Theoretical Artificial Intelligence, 10(3):309 -- 332, 1998.
	10	V. Conitzer and T. Sandholm. AWESOME: A general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents. In Proceedings of the 20th International Conference on Machine Learning, 2003.
	11	Claude-Nicolas Fiechter, Efficient reinforcement learning, Proceedings of the seventh annual conference on Computational learning theory, p.88-97, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.181019]
	12	Claude-Nicolas Fiechter, Expected Mistake Bound Model for On-Line Reinforcement Learning, Proceedings of the Fourteenth International Conference on Machine Learning, p.116-124, July 08-12, 1997
	13	Lance Fortnow , Duke Whang, Optimality and domination in repeated games with bounded players, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.741-749, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195448]
	14	Y. Freund , M. Kearns , Y. Mansour , D. Ron , R. Rubinfeld , R. E. Schapire, Efficient algorithms for learning to play repeated games against computationally bounded adversaries, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.332, October 23-25, 1995
	15	S. Kakade. On the Sample Complexity of Reinforcement Learning. PhD thesis, University College London, 2003.
	16	M. Kearns, Y. Mansour, and A. Ng. Approximate planning in large pomdps via reusable trajectories. In Advances in Neural Information Processing Systems 12. MIT Press, 2000.
	17	Michael J. Kearns , Satinder P. Singh, Near-Optimal Reinforcement Learning in Polynominal Time, Proceedings of the Fifteenth International Conference on Machine Learning, p.260-268, July 24-27, 1998
	18	Karèn Pivazyan , Yoav Shoham, Polynomial-time reinforcement learning of near-optimal policies, Eighteenth national conference on Artificial intelligence, p.205-210, July 28-August 01, 2002, Edmonton, Alberta, Canada
	19	Satinder P. Singh , Michael J. Kearns , Yishay Mansour, Nash Convergence of Gradient Dynamics in General-Sum Games, Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, p.541-548, June 30-July 03, 2000
	20	G. Tesauro. Extending Q-learning to general adaptive multi-agent systems. In S. Thrun, L. Saul, and B. Schölkopf, editors, Advances in Neural Information Processing Systems 16. MIT Press, Cambridge, MA, 2004.