A Linear Response Bandit Problem

By Alexander Goldenshluger, Assaf J. Zeevi. 2013

136 citations recorded by the source corpus.

We consider a two–armed bandit problem which involves sequential sampling from two non-homogeneous populations. The response in each is determined by a random covariate vector and a vector of parameters whose values are not known a priori. The goal is to maximize cumulative expected reward. We study this problem in a minimax setting, and develop rate-optimal polices that combine myopic action based on least squares estimates with a suitable “forced sampling” strategy. It is shown that the regret grows logarithmically in the time horizon n and no policy can achieve a slower growth rate over all feasible problem instances. In this setting of linear response bandits, the identity of the sub-optimal action changes with the values of the covariate vector, and the optimal policy is subject to sampling from the inferior population at a rate that grows like n.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering, 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 Artificial Intelligence

In Electrical and Electronic Engineering

In Management Science and Operations Research

Citations in the corpus

Estimation Considerations in Contextual Bandits (2017, methodology): “Even though in principle a variety of methods can be used to consistently estimate outcome models in the presence of complex, non-uniform arm assignment in large samples (Ridge regression as in [6, 45], ordinary least squares as in [32], LASSO as in [16]), in the early stages of learning where sampl”
Learning to Personalize from Observational Data (2016, methodology): “In each of [11, 12, 13], the proposed solution is to fit m regression functions, and, for a new instance, predict m outcomes and pick the smallest prediction (subject to cleverly ensuring su cient exploration by, e.”
Online Decision Making with High-Dimensional Covariates (2020, unknown): “This problem is tackled by Goldenshluger et al. (2013); however, their algorithm is impractical in settings where the dimension d of the observed covariates Xt is large (in particular, their regret bounds scale as O(d(3))). Yet, in many applications, the observed covariates are high-dimensional. For”
The Impact of Machine Learning on Economics (2018, background): “, 2010), ordinary least squares (OLS) (Goldenshluger and Zeevi, 2013), generalized linear model (GLM) (Li et al.”
Exploiting the Natural Exploration In Contextual Bandits (2017, methodology): “ number of arms K>2, and remove Assumption 3 on covariate diversity. Instead, we will make the following weaker Assumption 4, which is typically made in the contextual bandit literature (see e.g., Goldenshluger and Zeevi 2013, Bastani and Bayati 2015), which allows for multiple arms, and relaxes ”
Recursive Partitioning for Personalization using Observational Data (2016, background): “ces to our problem are (1) we consider an o!ine learning problem and (2) our data is observational whereas the data in a contextual bandit is the result of repeated controlled experiments. In each of [11, 12, 13], the proposed solution is to Þt m regression functions, and, for a new instance, predic”
Optimal trees for prediction and prescription (2018, background): “The online version of this problem, called the contextual bandit problem, has been studied by several authors [75, 53, 6]) in the multi-armed bandit literature [52].”
Optimal Prescriptive Trees (2019, methodology): “In an example of breast cancer, Gort et al. (2007) find that even when patients receive identical treatments, heterogeneity of the disease at the molecular level may lead to varying clinical outcomes.”