Skip to main content

Volumetric Spanners: An Efficient Exploration Basis for Learning

Author(s): Hazan, Elad; Karnin, Zohar

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1n84z
Full metadata record
DC FieldValueLanguage
dc.contributor.authorHazan, Elad-
dc.contributor.authorKarnin, Zohar-
dc.date.accessioned2021-10-08T19:50:21Z-
dc.date.available2021-10-08T19:50:21Z-
dc.date.issued2016en_US
dc.identifier.citationHazan, Elad, and Zohar Karnin. "Volumetric Spanners: An Efficient Exploration Basis for Learning." Journal of Machine Learning Research 17, no. 119 (2016): pp. 1-34.en_US
dc.identifier.urihttps://www.jmlr.org/papers/volume17/hazan16a/hazan16a.pdf-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1n84z-
dc.description.abstractNumerous learning problems that contain exploration, such as experiment design, multiarm bandits, online routing, search result aggregation and many more, have been studied extensively in isolation. In this paper we consider a generic and efficiently computable method for action space exploration based on convex geometry. We define a novel geometric notion of an exploration mechanism with low variance called volumetric spanners, and give efficient algorithms to construct such spanners. We describe applications of this mechanism to the problem of optimal experiment design and the general framework for decision making under uncertainty of bandit linear optimization. For the latter we give efficient and near-optimal regret algorithm over general convex sets. Previously such results were known only for specific convex sets, or under special conditions such as the existence of an efficient self-concordant barrier for the underlying set.en_US
dc.format.extent1 - 34en_US
dc.language.isoen_USen_US
dc.relation.ispartofJournal of Machine Learning Researchen_US
dc.rightsFinal published version. Article is made available in OAR by the publisher's permission or policy.en_US
dc.titleVolumetric Spanners: An Efficient Exploration Basis for Learningen_US
dc.typeJournal Articleen_US
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/journal-articleen_US

Files in This Item:
File Description SizeFormat 
VolumetricSpanners.pdf427.32 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.