Skip to main content

Volumetric Spanners: An Efficient Exploration Basis for Learning

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

To refer to this page use:
Abstract: Numerous 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.
Publication Date: 2016
Citation: Hazan, Elad, and Zohar Karnin. "Volumetric Spanners: An Efficient Exploration Basis for Learning." Journal of Machine Learning Research 17, no. 119 (2016): pp. 1-34.
Pages: 1 - 34
Type of Material: Journal Article
Journal/Proceeding Title: Journal of Machine Learning Research
Version: Final published version. Article is made available in OAR by the publisher's permission or policy.

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