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

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.