Contextual Bandits with Similarity Information
arXiv:0907.3986
Abstract
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 webpages, 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 gives an upper bound on the difference between the respective expected payoffs. Prior work on contextual bandits with similarity uses "uniform" partitions of the similarity space, which is potentially wasteful. We design more efficient algorithms that are based on adaptive partitions adjusted to "popular" context and "high-payoff" arms.
This is the full version of a conference paper in COLT 2011, to appear in JMLR in 2014. A preliminary version of this manuscript (with all the results) has been posted to arXiv in February 2011. An earlier version on arXiv, which does not include the results in Section 6, dates back to July 2009. The present revision addresses various presentation issues pointed out by journal referees
References in corpus (4)
Cited by in corpus (58)
- Context-Aware Proactive Content Caching with Service Differentiation in Wireless Networks
- The multi-armed bandit problem with covariates
- Finite-Time Analysis of Kernelised Contextual Bandits
- Personalized Course Sequence Recommendations
- Distributed Clustering of Linear Bandits in Peer to Peer Networks
- Making Contextual Decisions with Low Technical Debt
- Algorithms with Logarithmic or Sublinear Regret for Constrained Contextual Bandits
- Spectral bandits for smooth graph functions
- Ranking and Selection with Covariates for Personalized Decision Making
- Online Stochastic Optimization under Correlated Bandit Feedback
- Multi-objective Contextual Multi-armed Bandit with a Dominant Objective
- Adapting multi-armed bandits policies to contextual bandits scenarios
- Adaptive Discretization for Episodic Reinforcement Learning in Metric Spaces
- Nonparametric Pricing Analytics with Customer Covariates
- Stochastic Contextual Bandits with Known Reward Functions
- Adaptive Discretization in Online Reinforcement Learning
- Context-Aware Online Learning for Course Recommendation of MOOC Big Data
- Counterfactual Reasoning and Learning Systems
- Zooming for Efficient Model-Free Reinforcement Learning in Metric Spaces
- Multi-Armed Bandits for Decentralized AP selection in Enterprise WLANs
- Adaptive Discretization for Model-Based Reinforcement Learning
- Fair Contextual Multi-Armed Bandits: Theory and Experiments
- Dynamic Ad Allocation: Bandits with Budgets
- contextual: Evaluating Contextual Multi-Armed Bandit Problems in R
- OSOM: A simultaneously optimal algorithm for multi-armed and linear contextual bandits
- Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Bandits
- Adaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problems
- Markov Decision Processes with Continuous Side Information
- Efficient Contextual Bandits with Continuous Actions
- Multi-Objective Generalized Linear Bandits
- Nonparametric Contextual Bandits in an Unknown Metric Space
- A Contextual Bandit Approach for Stream-Based Active Learning
- Provably adaptive reinforcement learning in metric spaces
- Randomized Allocation with Nonparametric Estimation for Contextual Multi-Armed Bandits with Delayed Rewards
- Episodic Multi-armed Bandits
- Bandit Learning with Delayed Impact of Actions
- Online Learning and Decision-Making under Generalized Linear Model with High-Dimensional Data
- Balanced Linear Contextual Bandits
- Infinite Arms Bandit: Optimality via Confidence Bounds
- Global Bandits with Holder Continuity
- A Dimension-free Algorithm for Contextual Continuum-armed Bandits
- Adaptive Discretization against an Adversary: Lipschitz bandits, Dynamic Pricing, and Auction Tuning
- Self-Tuning Bandits over Unknown Covariate-Shifts
- Dimension Reduction in Contextual Online Learning via Nonparametric Variable Selection
- Stochastic Lipschitz Q-Learning
- Action Centered Contextual Bandits
- Contextual Online Learning for Multimedia Content Aggregation
- Differentially Private Online Learning for Cloud-Based Video Recommendation with Multimedia Big Data in Social Networks
- Multi-armed Bandit Requiring Monotone Arm Sequences
- Optimal Contextual Pricing and Extensions
- Lipschitz Bandit Optimization with Improved Efficiency
- Multitask Bandit Learning Through Heterogeneous Feedback Aggregation
- Towards Fundamental Limits of Multi-armed Bandits with Random Walk Feedback
- Data-Driven Online Decision Making with Costly Information Acquisition
- No-Regret Learning in Unknown Games with Correlated Payoffs
- Graph-Based Recommendation System
- Bayesian Policy Reuse
- Lexicographic Multiarmed Bandit