Efficient algorithms for learning to play repeated games against computationally bounded adversaries

Yoav Freund, Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire

Research output: Contribution to journalConference article

20 Scopus citations

Abstract

The problem of learning to play various games optimally against resource-bounded adversaries is examined, with an explicit emphasis on the computational efficiency of the learning algorithm. This is aimed at providing efficient algorithms for games other than penny-matching and for adversaries other than classically studied finite automata. In particular, examined are games and adversaries for which the learning algorithm's past actions may strongly affect the adversary's future willingness to 'cooperate', i.e., to permit high payoff, and therefore require carefully planned actions on the part of the learning algorithm.

Original languageEnglish (US)
Pages (from-to)332-341
Number of pages10
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - Dec 1 1995
Externally publishedYes
EventProceedings of the 1995 IEEE 36th Annual Symposium on Foundations of Computer Science - Milwaukee, WI, USA
Duration: Oct 23 1995Oct 25 1995

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Efficient algorithms for learning to play repeated games against computationally bounded adversaries'. Together they form a unique fingerprint.

  • Cite this