Contextual Bandits with Similarity Information

By Aleksandrs Slivkins. 2009

481 citations recorded by the source corpus.

In a multi-armed bandit (MAB) problem, an online algorithm makes a sequence of choices. In each round it chooses from a time-invariant set of alternatives and receives the payoff associated with this alternative. While the case of small strategy sets is by now well-understood, a lot of recent work has focused on MAB problems with exponentially or infinitely large strategy sets, where one needs to assume extra structure in order to make the problem tractable. In particular, recent literature considered information on similarity between arms. We consider similarity information in the setting of contextual bandits, a natural extension of the basic MAB problem where before each round an algorithm is given the context--a hint about the payoffs in this round. Contextual bandits are directly motivated by placing advertisements on web pages, one of the crucial problems in sponsored search. A particularly simple way to represent similarity information in the contextual bandit setting is via a similarity distance between the context-arm pairs which bounds from above the difference between the respective expected payoffs. Prior work on contextual bandits with similarity uses "uniform" partitions of the similarity space, so that each context-arm pair is approximated by the closest pair in the partition. Algorithms based on "uniform" partitions disregard the structure of the payoffs and the context arrivals, which is potentially wasteful. We present algorithms that are based on adaptive partitions, and take advantage of "benign" payoffs and context arrivals without sacrificing the worst-case performance. The central idea is to maintain a finer partition in high-payoff regions of the similarity space and in popular regions of the context space. Our results apply to several other settings, e.g., MAB with constrained temporal change (Slivkins and Upfal, 2008) and sleeping bandits (Kleinberg et al., 2008a).

Subfields: Computer Networks and Communications, 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 Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Counterfactual reasoning and learning systems: the example of computational advertising (2012, background): “Refined contextual bandit approaches (Slivkins, 2011) account for similarities in the context and action spaces but do not take advantage of all the additional opportunities expressed by structural equation models.”
Balanced Linear Contextual Bandits (2018, methodology): “, the general bounds of (Russo and Van Roy 2014), the bounds of (Rigollet and Zeevi 2010), (Perchet and Rigollet 2013), (Slivkins 2014) in the case of non-parametric function of arm rewards), has demonstrated successful applications (e.”
Estimation Considerations in Contextual Bandits (2017, neutral): “, the general bounds of [51], the bounds of [50, 49, 56] in the case of non-parametric function of arm rewards), has demonstrated successful applications (e.”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “We refer the interested reader to Kleinberg et al. [2010], Kanade et al. [2009], Slivkins [2011], Kanade and Steinke [2012] for the details of this model as well as the theoretical guarantees that can be obtained.”
Online Decision Making with High-Dimensional Covariates (2020, methodology): “For example, Slivkins (2014), Perchet et al. (2013), Rigollet and Zeevi (2010) prove regret bounds where the arm rewards are smooth, non-parametric functions of the contexts, Langford and Zhang (2008) considers a practical epoch-greedy algorithm whose regret scales with the complexity of the…”
Nonparametric Bandits with Covariates (2010, background): “2 Description of the problem”
Optimistic Bayesian Sampling in Contextual-Bandit Problems (2012, background): “Slivkins (2011) provides an example of finite-time analysis of contextual bandits in a more general setting, in which a regret bound is proved for the Contextual Zooming algorithm under the assumptions that the joint regressor and action space is a compact metric space and the reward functions are…”
The multi-armed bandit problem with covariates (2011, background): “Notable entries in that stream of work are [16] and [20], who impose a smoothness condition both on the space of arms and the space of covariates, obtaining optimal regret bounds up to logarithmic terms.”
Finite-Time Analysis of Kernelised Contextual Bandits (2013, background): “The setting in (Slivkins, 2009) is diﬀerent from ours: they assume a Lipschitz property in a similarity space, which is a weaker condition than in our setting, but as a consequence their bound depends more heavily on the relevant dimensions (the covering dimensions of the context and action spaces…”
Contextual Gaussian Process Bandit Optimization (2011, background): “Another related approach is taken by Slivkins [21], who presents several algorithms with sublinear contextual regret for the case of inﬁnite actions and contexts, assuming Lipschitz continuity of the payoff function in the context-action space.”
Making Contextual Decisions with Low Technical Debt (2016, background): “icy evaluation in contextual bandits [21, 23, 36, 37]. Alternative approaches for contextual bandits typically impose substantial modeling assumptions such as linearity [7, 17, 36], Lipschitz rewards [39, 51], or availability of (correct) Bayesian priors [5], which often limits applicability. 8.2Sys”
Semiconvex Regression for Metamodeling-Based Optimization (2014, methodology): “Estimation methods include linear combinations of basis functions [44], discretization the state space [56], random histograms, nearest neighbors [76] or adaptive partitioning [66].”