Bandit processes and dynamic allocation indices

By John C. Gittins. 1979

Subfields: Statistics and Probability, Reinforcement Learning

How researchers see this paper

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

In Statistics and Probability

In Reinforcement Learning

Citations in the corpus

Taking the Human Out of the Loop: A Review of Bayesian Optimization (2016, methodology): “2) Multi-armed bandit: Until recently, the multi-armed bandit literature has focussed on maximizing the sum of rewards y i , possibly discounted by a discount factor γ ∈ (0 , 1] : When γ 1 , a Bayes-optimal sequence X can be computed for the Bernoulli bandit via dynamic programming, due to Gittins”
Counterfactual reasoning and learning systems: the example of computational advertising (2012, background): “The optimal exploration exploitation trade-off for multi-armed bandits is well understood (Gittins, 1989; Auer et al., 2002; Audibert et al., 2007) because an essential property of multi-armed bandits makes the analysis much simpler: the outcome observed after performing a particular action brings…”
Meta-Learning with Temporal Convolutions (2017, background): “The Gittins index [7] is the Bayes optimal solution in the discounted, inﬁnite-horizon setting, and serves as an oracle against which to benchmark performance.”
Variational Bayesian Reinforcement Learning with Regret Bounds (2018, methodology): “sian case the optimal policy can be formulated using belief states , but this is intractable for all but small problems [29]. In the multi-armed bandit case it can be formulated using Gittins indices [30], which converts a bandit problem into an MDP which can be solved for the optimal policy. Approx”
Unbiased offline evaluation of contextual-bandit-based news article recommendation algorithms (2010, methodology): “Another class of algorithms are based on Bayes rule, such as Gittins index methods [13].”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “2.1 Optimism in face of uncertainty 9 2.2 Upper Confidence Bound (UCB) strategies 10 2.3 Lower bound 12 2.4 Refinements and bibliographic remarks 16”
Behaviour Suite for Reinforcement Learning (2019, neutral): “1] (Gittins, 1979).”
Parallelizing Exploration-Exploitation Tradeoffs with Gaussian Process Bandit Optimization (2012, background): “In this setting, under some strong assumptions, optimal policies can be computed (Gittins, 1979).”
Fast and Slow Enigmas and Parental Guidance (2021, background): “Another issue related to the use of expensive predictors can be summarized as the explore-exploit tradeoff introduced in reinforcement learning research [5].”
A Minimum Relative Entropy Principle for Learning and Acting (2008, methodology): “This solution is based on the calculation of so-called Gittins indices (Gittins, 1979; Duff, 2002).”
An exploration strategy for non-stationary opponents (2017, background): “In the context ofmulti-armed bandits [23], there are someworks dealingwith non-stationarity.”
Simple Bayesian Algorithms for Best Arm Identification (2016, background): “In discounted bandit problems with independent arms, Gittins in- dices characterize the Bayes optimal policy [Gittins and Jones, 1974, Gittins, 1979].”
A theory of case-based decisions (2001, background): “The repeated problem we discuss in this section is akin to the multi-armed bandit problem (see Gittins (1979)): the decision maker is repeatedly faced with finitely many options (“arms”), each of which is guaranteed to yield an independent realization of a certain random variable (with finite expect”
Loss aversion, diminishing sensitivity, and the effect of experience on repeated decisions† (2008, background): “The agents are assumed to consider two cognitive strategies: exploration and exploitation (see Gittins, 1979; and Denrell & March, 2001, for discussions of the value of this distinction).”
Learning, risk attitude and hot stoves in restless bandit problems (2009, methodology): “For conventional armed bandits this can be achieved by using the Gittins strategy (Gittins, 1979), which prescribes choosing in every round the alternative with the higher Gittins index. Intuitively, the Gittins index is the sum of an alternative’s expected payoff and the information value from choo”
American Options, Multi–armed Bandits, and Optimal Consumption Plans: A Unifying View (2003, background): “The crucial idea of Gittins (1979) consists in reducing this multi–dimensional optimization problem to a family of simpler benchmark problems.”