Master algorithms for active experts problems based on increasing loss values
Date
Authors
Poland, Jan
Hutter, Marcus
Journal Title
Journal ISSN
Volume Title
Publisher
Belgian-Dutch Conference on Machine Learning (Benelearn)
Abstract
We specify an experts algorithm with the following
characteristics: (a) it uses only feedback from the actions
actually chosen (bandit setup), (b) it can be applied with
countably infinite expert classes, and (c) it copes with
losses that may grow in time appropriately slowly. We
prove loss bounds against an adaptive adversary. From this, we
obtain master algorithms for ``active experts problems'', which
means that the master's actions may influence the behavior of
the adversary. Our algorithm can significantly outperform
standard experts algorithms on such problems. Finally, we
combine it with a universal expert class. This results in a
(computationally infeasible) universal master algorithm
which performs - in a certain sense - almost as well as any
computable strategy, for any online problem.
Description
Keywords
Prediction with expert advice, responsive environments, partial observation game, universal learning, asymptotic optimality
Citation
Collections
Source
Type
Conference paper
Book Title
Proceedings of the 14th Dutch-Belgium Conference on Machine Learning Benelearn'05