Multi-armed Bandit Allocation Indices

By C. Ernst. 1989

Subfields: Reinforcement Learning, Game & Decision Theory

How researchers see this paper

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

In Reinforcement Learning

In Game & Decision Theory

Citations in the corpus

RL$^2$: Fast Reinforcement Learning via Slow Reinforcement Learning (2016, methodology): “We follow the practical approximations described in Gittins et al. (2011), Chakravorty & Mahajan (2013), and Whittle (1982), and choose the best-performing approximation for each setup.”
Reinforcement Learning: A Survey (1996, neutral): “Gittins gives an \allocation index" method for (cid:12)nding the optimal choice of action at each step in k-armed bandit problems (Gittins, 1989).”
Learning to Optimize via Posterior Sampling (2013, background): “[20] cover work on Gittin’s indices and related extensions.”
A Tutorial on Thompson Sampling (2017, methodology): “A thorough treatment of Gittins indices is provided in [52].”
Learning to Optimize via Information-Directed Sampling (2014, background): “It’s worth pointing out that, although Gittins’ indices characterize the Bayes optimal policy for infinite horizon discounted problems, the finite horizon formulation considered here is computationally intractable [24].”
Gambling in a rigged casino: The adversarial multi-armed bandit problem (1995, methodology): “A non-stochastic bandit problem was also considered by Gittins [4] and Ishikida and Varaiya [5].”
X-Armed Bandits (2010, unknown): “Bandit problems have been studied in the Bayesian framework [19], as well as in the frequentist parametric [25; 2] and non-parametric settings [4], and even in non-stochastic scenarios [5; 10].”
Superstars and Mediocrities: Market Failure in the Discovery of Talent (2009, background): “These theories are 1See Gittins (1989) for a general treatment of experimentation problems. concerned with the e¢ cient allocation of capital, consumers, and known talent, whereas the focus here is on the discovery process of talent under typical labor market imperfections.”
Better Optimism By Bayes: Adaptive Planning with Rich Models (2014, background): “…leaving open the possibility that it might not be justi-ﬁed compared to heuristic approaches that may perform very similarly at a much reduced computational cost, for instance treating the tradeoff as a learning problem in a regret setting, focusing on an asymptotic requirement to discover…”
Stochastic Multi-Armed-Bandit Problem with Non-stationary Rewards (2014, background): “the monographs by [10], [11] for Bayesian / dynamic programming formulations, and [12] that covers the machine learning literature and the so-called adversarial setting.”
Learning from Experience. (2014, unknown): “Then Gittins and Jones (1974) demonstrated a simple index solution – develop an index for each “arm” (i.”
Customer Acquisition via Display Advertising Using Multi-Armed Bandit Experiments (2017, background): “For a more complete review, see recent books such as Gittins et al. (2011) and White (2012).”
Prediction, learning, and games (2006, background): “Several variants of the basic problems have been studied, see, for example, Berry and Fristedt [26] and Gittins [129].”
Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges (2015, background): “…conclusions of this work naturally extend to the multinomial distribution (Glazebrook, 1978), normally distributed processes with known variance (Jones, 1970) and with unknown variance (Jones, 1975), and exponentially distributed populations (Do Amaral, 1985; Gittins, Glazebrook and Weber, 2011).”
Algorithms for multi-armed bandit problems (2014, background): “From a theoretical viewpoint, our ﬁndings indicate the need for a formal analysis of simple heuristics, and more generally for the development of theoretically sound algorithms that perform as well as the simpler heuristics in practice.”
From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning (2014, methodology): “…which has been analyzed recently in [Agrawal and Goyal, 2012, Kauffmann et al., 2012, Agrawal and Goyal, 2013, Kaufmann et al., 2013], the Gittins indexes, see [Gittins., 1979, Gittins et al., 1989], and optimistic Bayesian algorithms such as in [Srinivas et al., 2010, Kauffman et al., 2012]).”