Bandit Theory meets Compressed Sensing for high dimensional Stochastic Linear Bandit

By A. Carpentier, R´emi Munos. 2012

105 citations recorded by the source corpus.

We consider a linear stochastic bandit problem where the dimension K of the unknown parameter is larger than the sampling budget n. In such cases, it is in general impossible to derive sub-linear regret bounds since usual linear bandit algorithms have a regret in O(K p n). In this paper we assume that is S sparse, i.e. has at most S non-zero components, and that the space of arms is the unit ball for the jj:jj2 norm. We combine ideas from Compressed Sensing and Bandit Theory and derive an algorithm with a regret bound in O(S p n). We detail an application to the problem of optimizing a function that depends on many variables but among which only a small number of them (initially unknown) are relevant.

Subfields: Computational Mechanics, Finance, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Finance

In Management Science and Operations Research

Citations in the corpus

Taking the Human Out of the Loop: A Review of Bayesian Optimization (2016, background): “For linear bandits, Carpentier and Munos [35] recently proposed a compressed sensing strategy to attack problems with a high degree of sparsity.”
Joint Optimization and Variable Selection of High-dimensional Gaussian Processes (2012, background): “Con-currently, (Carpentier et al., 2012) combines compress sensing and bandit theory to achieve sub-linear regret bounds for sparse functions.”
UvA-DARE (Digital Academic Repository) Bayesian Optimization in High Dimensions via Random Embeddings (2013, unknown): “For linear bandits, Carpentier et al [ 2012 ] recently proposed a compressed sensing strategy to attack problems with a high degree of sparsity.”
Active Learning of Linear Embeddings for Gaussian Processes (2013, methodology): “Within Bayesian optimization, much recent work has focused on high-dimensional problems (Hut-ter et al., 2011; Chen et al., 2012; Carpentier & Munos, 2012; Bergstra & Bengio, 2012; Hutter, 2009).”
High-Dimensional Gaussian Process Bandits (2013, background): “Bandit algorithms that exploit low-dimensional structure of the function appeared first for the linear setting, where under sparsity assumptions one can obtain bounds, which depend only weakly on the ambient dimension [16, 17].”
Bayesian Optimization in a Billion Dimensions via Random Embeddings (2013, background): “In the linear bandits case, Carpentier & Munos (2012) recently proposed a compressed sensing strategy to attack problems with a high degree of sparsity.”
Bandit Algorithms (2020, methodology): “Rustichini shows how to reduce the problem to Blackwell approachability (see Cesa-Bianchi and Lugosi [2006]) and uses this to deduce the existence of a Hannan consistent strategy.”
Online Decision Making with High-Dimensional Covariates (2020, unknown): “In particular, Carpentier and Munos (2012) uses random projections, and Deshpande and Montanari (2012), Abbasi-Yadkori et al. (2012) use L2-regularized regression.”
From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning (2014, methodology): “Several extensions to the linear setting have been considered, such as Generalized Linear models [49] and sparse linear bandits [40, 3].”