Multi-armed bandits in metric spaces

By Robert D. Kleinberg, Aleksandrs Slivkins, Eli Upfal. Symposium on the Theory of Computing, 2008

516 citations recorded by the source corpus.

In a multi-armed bandit problem, an online algorithm chooses from a set of strategies in a sequence of $n$ trials so as to maximize the total payoff of the chosen strategies. While the performance of bandit algorithms with a small finite strategy set is quite well understood, bandit problems with large strategy sets are still a topic of very active investigation, motivated by practical applications such as online auctions and web advertisement. The goal of such research is to identify broad and natural classes of strategy sets and payoff functions which enable the design of efficient solutions. In this work we study a very general setting for the multi-armed bandit problem in which the strategies form a metric space, and the payoff function satisfies a Lipschitz condition with respect to the metric. We refer to this problem as the "Lipschitz MAB problem". We present a complete solution for the multi-armed problem in this setting. That is, for every metric space (L,X) we define an isometry invariant Max Min COV(X) which bounds from below the performance of Lipschitz MAB algorithms for $X$, and we present an algorithm which comes arbitrarily close to meeting this bound. Furthermore, our technique gives even better results for benign payoff functions.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/202fc649b2c7a5fa08519debd0aef07d2e2ef8c0

How researchers see this paper

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

In Artificial Intelligence

In Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

On Kernelized Multi-armed Bandits (2017, background): “An alternative line of work pertaining to X -armed bandits (Kleinberg et al., 2008; Bubeck et al., 2011; Carpentier & Valko, 2015; Azar et al., 2014) studies continuum-armed bandits with smoothness structure.”
Learning to Optimize via Posterior Sampling (2013, background): “Other authors have studied cases where the reward function is Lipschitz continuous [17], sampled from a Gaussian process [25], or takes the form of a generalized [13] or sparse [3] linear model.”
Improved Regret Bounds for Undiscounted Continuous Reinforcement Learning (2015, methodology): “Under Hölder conditions on the reward function, regret bounds have been given by Kleinberg (2005), Auer et al. (2007), Kleinberg et al. (2008), and Bubeck et al. (2010).”
Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting (2009, background): “Kleinberg et al. (2008) provide regret bounds under weaker and less conﬁgurable assumptions (only Lipschitz-continuity w.r.t. a metric is assumed; Bubeck et al. 2008 consider arbitrary topological spaces), which however degrade rapidly with the dimensionality of the problem (Ω( T d +1 d +2 )).”
Stochastic Convex Optimization with Bandit Feedback (2011, methodology): “For instance, the f is assumed to be linear in the paper [9], a Lipschitz condition on f is assumed in the works [3, 12, 13], and Srinivas et al.”
Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms (2014, result): “Bounded smoothness property in our paper is an extended form of Lipschitz condition, but our model and results differ from the Lipschitz bandit research (Kleinberg et al., 2008) in several aspects.”
Bandits with Knapsacks (2013, methodology): “see [15]), or enhancing the BalanceBwK algorithm with the technique of adaptively refined discretization, as in the zooming algortihm of [16].”
Incentivizing exploration (2014, unknown): “This notion of similarity among alternatives could be modeled, for instance, as a Lipschitz condition on payments [Kleinberg et al. 2008] or as a Gaussian process prior [Srinivas et al. 2012].”
Time-Sensitive Bandit Learning and Satisficing Thompson Sampling (2017, background): “Many papers [5, 12, 13] have studied bandit problems with continuous action spaces, where it is also necessary to learn only approximately optimal actions.”
Simple regret for infinitely many armed bandits (2015, background): “One class of examples is fixed design such as linear bandits (Dani et al., 2008) other settings consider bandits in known or unknown metric space (Kleinberg et al., 2008; Munos, 2014; Azar et al., 2014).”
Linearly Parameterized Bandits (2008, methodology): “le exponent. For our model, the zooming dimension is at least1 r−1, and thus, the regret under the zooming algorithm is Oe Tr/(r+1) . Bubeck et al. (2008) and Wang et al. (2008) extend the results of Kleinberg et al. (2008) by proposing alternative deﬁnitions of dimension and allowing for a diﬀerent”
Non-Stationary Markov Decision Processes a Worst-Case Approach using Model-Based Reinforcement Learning (2019, methodology): “Utilizing Lipschitz continuity to infer bounds on a function is common in the RL, bandit and optimization communities [Kleinberg et al., 2008, Rachelson and Lagoudakis, 2010, Pirotta et al., 2015, Pazis and Parr, 2013, Munos, 2014].”
Bandit Algorithms (2020, methodology): “The policy proposed by Lai and Robbins [1985] was based on upper confidence bounds, but was not a variant of UCB.”
Neural Contextual Bandits with UCB-based Exploration (2019, methodology): “A third approach uses nonparametric modeling, such as per-ceptrons (Kakade et al., 2008), random forests (F ´ eraud et al., 2016), Gaussian processes and kernels (Kleinberg et al., 2008; Srinivas et al., 2010; Krause & Ong, 2011; Bubeck et al., 2011).”