Nearly Tight Bounds for the Continuum-Armed Bandit Problem

By Robert D. Kleinberg. 2004

423 citations recorded by the source corpus.

How researchers see this paper

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

Citations in the corpus

Theory-Guided Data Science: A New Paradigm for Scientific Discovery from Data (2016, neutral): “values instead of discrete steps [79], [80].”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, positive): “This result builds upon and generalizes a sequence of works that include the discretization approach (for the 1-dimensional case) of [Kleinberg, 2004] and [Auer et al.”
Entropy Search for Information-Efficient Global Optimization (2011, background): “But it is useful to pause at this point to contrast this deﬁnition with other concepts of optimization.”
Bandits with Knapsacks (2013, methodology): “on error: informally, the decrease in the performance benchmark due to restricting the action space to S. This generic approach has been successfully used in past work on MAB on metric spaces (e.g., [Kleinberg, 2004, Hazan and Megiddo, 2007, Kleinberg et al., 2008, Lu et al., 2010]) and dynamic pric”
X-Armed Bandits (2010, unknown): “During the last decades numerous authors have investigated such “continuum-armed” bandit problems [3; 21; 6; 22; 12].”
Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms (2014, unknown): “Since our work in Chen et al. (2013), several studies are also related to combinatorial multi-armed bandits or in general combinatorial online learning.”
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).”
Contextual Bandits with Similarity Information (2009, methodology): “In particular, the line of work [2, 20, 12, 5, 30, 25, 29, 24, 10] assumes that some information on similarity between arms is available to the algorithm.”
Pure Exploration in Multi-armed Bandits Problems (2009, methodology): “Therein, we consider theX ‐ armed bandit problem with bounded payoffs of, e.g., [ Kle04 ,BMSS09] and (re-)define the notions of cumulative and simple regrets.”
From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning (2014, background): “Other weaker assumptions on the mean-reward function have been considered, such as Lipschitz condition [83, 6, 17, 84] or even weaker local assumptions in [34, 115].”
Online convex optimization in the bandit setting: gradient descent without a gradient (2004, unknown): “Kleinberg [12] has given strikingly similar O(n) bounds for the same problem using an extremely similar approach.”
Truthful incentives in crowdsourcing tasks using regret minimization mechanisms (2013, background): “[24] [4] [10] [33] extend this approach to handle complex (possibly infinite) action spaces.”
Regret Bounds for Gaussian Process Bandit Problems (2010, unknown): “Diﬀerent approaches to the continuum arm space setting have already been proposed Agrawal (1995); Kleinberg (2004)”
Dynamic Pricing and Learning: Historical Origins, Current Research, and New Directions (2013, unknown): “This changes with the work of Kleinberg and Leighton (2003), who quantify the performance of a pricing policy by Regret(T ): the expected loss in T time periods incurred by not choosing optimal prices.”
Interactively optimizing information retrieval systems as a dueling bandits problem (2009, methodology): “Furthermore, we propose a gradient-descent method which builds on methods for on-line convex optimization (Zinkevich, 2003; Kleinberg, 2004; Flaxman et al., 2005).”
Dynamic Assortment Optimization with a Multinomial Logit Choice Model and Capacity Constraint (2010, background): “We are interested in finding a policy that minimizes the regret, which is equivalent to maximizing the total expected reward ∑T t=1 E [f(St)] .”