×

Learning to win process-control games watching game-masters. (English) Zbl 1009.68116

Summary: 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 incrementally – 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 incrementally learn 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 by watching \(m+1\) masters than one can learn by watching only \(m\). Last, 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.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
91A26 Rationality and learning in game theory

Software:

C4.5
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Bain, M.; Sammut, C., A framework for behavioural cloning, (Muggleton, K. F.S.; Michie, D., Machine Intelligence 15 (1996), Oxford Univ. Press: Oxford Univ. Press Oxford)
[2] Bārzdiņš, J. M., Two theorems on the limiting synthesis of functions, Theory of Algorithms and Programs, Latvian State University, Riga (1974), p. 82-88
[3] Büchi, J. R.; Landweber, L. H., Solving sequential conditions by finite-state strategies, Trans. Amer. Math. Soc., 138, 295-311 (1969) · Zbl 0182.02302
[4] Case, J.; Kaufmann, S.; Kinber, E.; Kummer, M., Learning recursive functions from approximations, J. Comput. System Sci., 55, 183-196 (1997) · Zbl 0880.68107
[5] Case, J.; Smith, C., Comparison of identification criteria for machine inductive inference, Theoret. Comput. Sci., 25, 193-220 (1983) · Zbl 0524.03025
[6] Cenzer, D.; Remmel, J., Recursively presented games and strategies, Math. Soc. Sci., 24, 117-139 (1992) · Zbl 0786.90103
[7] Freivalds, R. V.; Wiehagen, R., Inductive inference with additional information, Elektron. Informationsverarb. Kybernet., 15, 179-185 (1979) · Zbl 0437.03018
[8] Jain, S.; Sharma, A., Learning with the knowledge of an upper bound on program size, Inform. and Comput., 102, 118-166 (1993) · Zbl 0769.68109
[9] Jockusch, C. G.; Lewis, A.; Remmel, J. B., \(II_1^0\)-Classes and Rado’s selection principle, J. Symbolic Logic, 56, 684-693 (1991) · Zbl 0744.03046
[10] Kummer, M.; Ott, M., Learning branches and learning to win closed games, Proceedings of the Ninth Annual Conference on Computational Learning Theory (1996), Assoc. Comput. Mach: Assoc. Comput. Mach New York, p. 280-291
[11] Kummer, M.; Stephan, F., On the structure of degrees of inferability, J. Comput. System Sci., 52, 214-238 (1996) · Zbl 1152.68452
[12] Maler, O.; Pnueli, A.; Sifakis, J., On the synthesis of discrete controllers for timed systems, Proceedings of the Annual Symposium on the Theoretical Aspects of Computer Science, Lecture Notes in Computer Science (1995), Springer-Verlag: Springer-Verlag Berlin/New York, p. 229-242 · Zbl 1379.68227
[13] McNaughton, R., Infinite games played on finite graphs, Ann. Pure Appl. Logic, 65, 149-184 (1993) · Zbl 0798.90151
[14] Michie, D.; Sammut, C., Machine learning from real-time input-output behaviour, Proceedings of the International Conference on Design to Manufacture in Modern Industry (1993), p. 363-369
[15] Odifreddi, P., Classical Recursion Theory (1989), North-Holland: North-Holland Amsterdam · Zbl 0931.03057
[16] Osherson, D.; Stob, M.; Weinstein, S., Systems That Learn (1986), MIT Press: MIT Press Cambridge
[17] Ott, M., Learning Strategies for Infinite Games (1998), Universität KarlsruheInstitut für Logik, Komplexität und Deduktionssysteme: Universität KarlsruheInstitut für Logik, Komplexität und Deduktionssysteme Shaker Verlag
[18] Ott, M.; Stephan, F., The complexity of learning branches and strategies from queries, Proceedings of the Eighth Annual International Symposium on Algorithms and Computation (1997), Springer-Verlag: Springer-Verlag Berlin/New York, p. 283-292 · Zbl 0886.68113
[19] Ott, M.; Stephan, F., Structural measures for games and process control in the branch learning model, (Ben-David, S., Proceedings of the Third European Conference on Computational Learning Theory (1997), Springer-Verlag: Springer-Verlag Berlin/New York), 94-108 · Zbl 0945.68150
[20] Pitt, L., Probabilistic inductive inference, J. Assoc. Comput. Mach., 36, 383-433 (1989) · Zbl 0676.68046
[21] Quinlan, J., C4.5: Programs for Machine Learning (1992), Morgan Kaufmann: Morgan Kaufmann San Mateo
[22] Rivest, R. L.; Schapire, R. E., Inference of finite automata using homing sequences, Inform. and Comput., 103, 299-347 (1993) · Zbl 0786.68082
[23] Sammut, C., Acquiring expert knowledge by learning from recorded behaviours, Japanese Knowledge Acquisition Workshop (1992)
[24] Sammut, C., Automatic construction of reactive control systems using symbolic machine learning, Knowledge Engrg. Rev., 11, 27-42 (1996)
[25] Sammut, C.; Hurst, S.; Kedzier, D.; Michie, D., Learning to fly, Proceedings of the Ninth International Conference on Machine Learning (1992), Morgan Kaufmann: Morgan Kaufmann San Meteo
[26] Smith, C., The power of pluralism for automatic program synthesis, J. Assoc. Comput. Mach., 29, 1144-1165 (1982) · Zbl 0496.68065
[27] Thomas, W.1995, On the synthesis of strategies in infinite games, in; Thomas, W.1995, On the synthesis of strategies in infinite games, in
[28] Urbanc̆ic̆, T.; Bratko, I., Reconstructing human skill with machine learning, (Cohn, A., Proceedings of the Eleventh European Conference on Artificial Intelligence (1994), Wiley: Wiley New York)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.