Volumetric Spanners: an Efficient Exploration Basis for Learning
This work addresses the exploration challenge in bandit linear optimization for machine learning practitioners, offering a general solution that is not incremental but a novel advancement.
The paper tackles the problem of exploration in machine learning by introducing volumetric spanners, a low-variance geometric exploration basis, and provides efficient algorithms for their construction. This leads to the first efficient and optimal regret algorithm for bandit linear optimization over general convex sets, improving upon previous results limited to specific sets or special conditions.
Numerous machine learning problems require an exploration basis - a mechanism to explore the action space. We define a novel geometric notion of exploration basis with low variance, called volumetric spanners, and give efficient algorithms to construct such a basis. We show how efficient volumetric spanners give rise to the first efficient and optimal regret algorithm for bandit linear optimization 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.