Skip navigation
Skip navigation
Open Research will be down for maintenance between 8:00 and 8:15 am on Tuesday, December 1 2020.

Master algorithms for active experts problems based on increasing loss values

Poland, Jan; Hutter, Marcus

Description

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...[Show more]

dc.contributor.authorPoland, Jan
dc.contributor.authorHutter, Marcus
dc.date.accessioned2015-09-01T04:52:46Z
dc.date.available2015-09-01T04:52:46Z
dc.identifier.issn0929-0672
dc.identifier.urihttp://hdl.handle.net/1885/15052
dc.description.abstractWe 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.
dc.publisherBelgian-Dutch Conference on Machine Learning (Benelearn)
dc.relation.ispartofProceedings of the 14th Dutch-Belgium Conference on Machine Learning Benelearn'05
dc.rights© The Author(s)
dc.subjectPrediction with expert advice
dc.subjectresponsive environments
dc.subjectpartial observation game
dc.subjectuniversal learning
dc.subjectasymptotic optimality
dc.titleMaster algorithms for active experts problems based on increasing loss values
dc.typeConference paper
local.type.statusAccepted Version
local.contributor.affiliationHutter, M., Research School of Computer Science, The Australian National University
local.bibliographicCitation.startpage59
local.bibliographicCitation.lastpage66
CollectionsANU Research Publications

Download

File Description SizeFormat Image
Poland and Hutter Master Algorithms for Active Experts Problems 2005.pdf219.37 kBAdobe PDFThumbnail


Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator