Learning to Win Process-Control Games Watching Game-Masters

Abstract

The present paper focuses on some interesting classes of process-control games , where winning essentially means successfully controlling the process. A master for one of these games is an agent who plays a winning-strategy. In this paper we investigate situations, in which even a complete model (given by a program) of a particular game does not provide enough information to synthesize — even in the limit — a winning strategy. However, if in addition to getting a program, a machine may also watch masters play winning strategies, then the machine is able to learn in the limit a winning strategy for the given game. Studied are successful learning from arbitrary masters and from pedagogically useful selected masters. It is shown that selected masters are strictly more helpful for learning than are arbitrary masters. Both for learning from arbitrary masters and for learning from selected masters, though, there are cases where one can learn programs for winning strategies from masters but not if one is required to learn a program for the master’s strategy itself. Both for learning from arbitrary masters and for learning from selected masters, one can learn strictly more watching m + 1 masters than one can learn watching only m . Lastly a simulation result is presented where the presence of a selected master reduces the complexity from infinitely many semantic mind changes to finitely many syntactic ones.