Woodroofe's One-Armed Bandit Problem Revisited
By A. Goldenshluger, Assaf J. Zeevi. 2009
63 citations recorded by the source corpus.
We consider the one-armed bandit problem of Woodroofe [J. Amer. Statist. Assoc. 74 (1979) 799-806], which involves sequential sampling from two populations: one whose characteristics are known, and one which depends on an unknown parameter and incorporates a covariate. The goal is to maximize cumulative expected reward. We study this problem in a minimax setting, and develop rate-optimal polices that involve suitable modifications of the myopic rule. It is shown that the regret, as well as the rate of sampling from the inferior population, can be finite or grow at various rates with the time horizon of the problem, depending on "local" properties of the covariate distribution. Proofs rely on martingale methods and information theoretic arguments.
Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research
View Paper: https://www.semanticscholar.org/paper/aaf41fd865a2263deb1e0a7d0961e1c3f782302c
Citations in the corpus
- Dynamic Pricing and Learning: Historical Origins, Current Research, and New Directions (2013, unknown): “Prescott (1972), Grossman et al. (1977), Mirman et al.”
- Linearly Parameterized Bandits (2008, unknown): “A somewhat related literature on bandits with dependent arms is the recent work by Wang et al. (2005a,b) and Goldenshluger and Zeevi (2008, 2009) who consider bandit problems with two arms, where the expected reward of each arm depends on an exogenous variable that represents side information.”
- The multi-armed bandit problem with covariates (2011, unknown): “It was originally imported to the bandit setup by Goldenshluger and Zeevi (2009).”
- A Linear Response Bandit Problem (2013, unknown): “When α > 1, the policy proposed in this paper is no longer rate–optimal; see Goldenshluger and Zeevi (2009) that treats a particular one-armed setting from which the above conclusion can be drawn.”
- Dynamic Pricing with an Unknown Demand Model: Asymptotically Optimal Semi-Myopic Policies (2014, unknown): “Let λ be an absolutely continuous density on Θ, taking positive values on the interior of Θ and zero on its boundary (cf. Goldenshluger and Zeevi 2009, p. 1632 for a standard choice of λ).”