Paper Info
Title
How to Combine Expert (and Novice) Advice when Actions Impact the Environment?
Abstract
The so-called "experts algorithms" constitute a methodology for choosing actions repeatedly, when the rewards depend both on the choice of action and on the unknown current state of the environment. An experts algorithm has access to a set of strategies ("experts"), each of which may recommend which action to choose. The algorithm learns how to combine the recommendations of individual experts so that, in the long run, for any fixed sequence of states of the environment, it does as well as the best expert would have done relative to the same sequence. This methodology may not be suitable for situations where the evolution of states of the environment depends on past chosen actions, as is usually the case, for example, in a repeated non-zero-sum game. A new experts algorithm is presented and analyzed in the context of repeated games. It is shown that asymptotically, under certain conditions, it performs as well as the best available expert. This algorithm is quite different from previously proposed experts algorithms. It represents a shift from the paradigms of regret minimization and myopic optimization to consideration of the long-term effect of a player's actions on the opponent's actions or the environment. The importance of this shift is demonstrated by the fact that this algorithm is capable of inducing cooperation in the repeated Prisoner's Dilemma game, whereas previous experts algorithms converge to the suboptimal non-cooperative play.
Year
Venue
Keywords
2003
ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 16
reward dependence,zero sum game,prisoner s dilemma
Field
DocType
Volume
Regret minimization,State of the Environment,Computer science,As is,Repeated game,Artificial intelligence,Adversary,Dilemma,Machine learning
Conference
16
ISSN
Citations 
PageRank 
1049-5258
15
1.44
References 
Authors
3
2
Name
Order
Citations
PageRank
Daniela Pucci de Farias117617.09
Nimrod Megiddo24244668.46