An Optimal-Control Application of Two Paradigms of On-Line Learning
Abstract
We describe and compare two paradigms of on-line learning, which we call Bayesian and Popperian. In this paper the Bayesian paradigm is represented by Littlestone and Warmuth's Weighted Majority Algorithm, and the Popperian paradigm is represented by Rivest and Schapire's reset-free algorithm for exact learning of finite automata with membership and equivalence queries. Both algorithms are applied to the problem of optimal control of a finite-state plant in a finite-state environment. The advantage of the control strategy based on the Weighted Majority Algorithm is its robustness and better performance (actually, its performance is nearly optimal in the class of deterministic control strategies), and the advantage of the control strategy based on Rivest and Schapire's algorithm is its computational efficiency.
Cite
Text
Vovk. "An Optimal-Control Application of Two Paradigms of On-Line Learning." Annual Conference on Computational Learning Theory, 1994. doi:10.1145/180139.181020Markdown
[Vovk. "An Optimal-Control Application of Two Paradigms of On-Line Learning." Annual Conference on Computational Learning Theory, 1994.](https://mlanthology.org/colt/1994/vovk1994colt-optimal/) doi:10.1145/180139.181020BibTeX
@inproceedings{vovk1994colt-optimal,
title = {{An Optimal-Control Application of Two Paradigms of On-Line Learning}},
author = {Vovk, V. G.},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1994},
pages = {98-109},
doi = {10.1145/180139.181020},
url = {https://mlanthology.org/colt/1994/vovk1994colt-optimal/}
}