Gittins index

The Gittins index is a measure of the reward that can be achieved through a given stochastic process with certain properties, namely: the process has an ultimate termination state and evolves with an option, at each intermediate state, of terminating. Upon terminating at a given state, the reward achieved is the sum of the probabilistic expected rewards associated with every state from the actual terminating state to the ultimate terminal state, inclusive. The index is a real scalar.

Terminology

To illustrate the theory we can take two examples from a developing sector, such as from electricity generating technologies: wind power and wave power. If we are presented with the two technologies when they are both proposed as ideas we cannot say which will be better in the long run as we have no data, as yet, to base our judgments on. It would be easy to say that wave power would be too problematic to develop as it seems easier to put up many wind turbines than to make the long floating generators, tow them out to sea and lay the cables necessary.

If we were to make a judgment call at that early time in development we could be condemning one technology to being put on the shelf and the other would be developed and put into operation. If we develop both technologies we would be able to make a judgment call on each by comparing the progress of each technology at a set time interval such as every three months. The decisions we make about investment in the next stage would be based on those results.

In a paper in 1979 called Bandit Processes and Dynamic Allocation Indices John C. Gittins suggests a solution for problems such as this. He takes the two basic functions of a "scheduling Problem" and a "multi-armed bandit" problem and shows how these problems can be solved using Dynamic allocation indices. He first takes the "Scheduling Problem" and reduces it to a machine which has to perform jobs and has a set time period, every hour or day for example, to finish each job in. The machine is given a reward value, based on finishing or not within the time period, and a probability value of whether it will finish or not for each job is calculated. The problem is "to decide which job to process next at each stage so as to maximize the total expected reward." He then moves on to the "Multi–armed bandit problem" where each pull on a "one armed bandit" lever is allocated a reward function for a successful pull, and a zero reward for an unsuccessful pull. The sequence of successes forms a Bernoulli process and has an unknown probability of success. There are multiple "bandits" and the distribution of successful pulls is calculated and different for each machine. Gittins states that the problem here is "to decide which arm to pull next at each stage so as to maximize the total expected reward from an infinite sequence of pulls."

Gittins says that "Both the problems described above involve a sequence of decisions, each of which is based on more information than its predecessors, and these both problems may be tackled by dynamic allocation indices."

Definition

In applied mathematics, the "Gittins index" is a real scalar value associated to the state of a stochastic process with a reward function and with a probability of termination. It is a measure of the reward that can be achieved by the process evolving from that state on, under the probability that it will be terminated in future. The "index policy" induced by the Gittins index, consisting of choosing at any time the stochastic process with the currently highest Gittins index, is the solution of some stopping problems such as the one of dynamic allocation, where a decision-maker has to maximize the total reward by distributing a limited amount of effort to a number of competing projects, each returning a stochastic reward. If the projects are independent from each other and only one project at a time may evolve, the problem is called multi-armed bandit (one type of Stochastic scheduling problems) and the Gittins index policy is optimal. If multiple projects can evolve, the problem is called Restless bandit and the Gittins index policy is a known good heuristic but no optimal solution exists in general. In fact, in general this problem is NP-complete and it is generally accepted that no feasible solution can be found.

History

Questions about the optimal stopping policies in the context of clinical trials have been open from the 1940s and in the 1960s a few authors analyzed simple models leading to optimal index policies, but it was only in the 1970s that Gittins and his collaborators demonstrated in a Markovian framework that the optimal solution of the general case is an index policy whose "dynamic allocation index" is computable in principle for every state of each project as a function of the single project's dynamics. In parallel to Gittins, Martin Weitzman established the same result in the economics literature.

Soon after the seminal paper of Gittins, Peter Whittle demonstrated that the index emerges as a Lagrange multiplier from a dynamic programming formulation of the problem called retirement process and conjectured that the same index would be a good heuristic in a more general setup named Restless bandit. The question of how to actually calculate the index for Markov chains was first addressed by Varaiya and his collaborators with an algorithm that computes the indexes from the largest first down to the smallest and by Chen and Katehakis who showed that standard LP could be used to calculate the index of a state without requiring its calculation for all states with higher index values. LCM Kallenberg provided a parametric LP implementation to compute the indices for all states of a Markov chain. Further, Katehakis and Veinott demonstrated that the index is the expected reward of a Markov decision process constructed over the Markov chain and known as Restart in State and can be calculated exactly by solving that problem with the policy iteration algorithm, or approximately with the value iteration algorithm. This approach also has the advantage of calculating the index for one specific state without having to calculate all the greater indexes and it is valid under more general state space conditions. A faster algorithm for the calculation of all indices was obtained in 2004 by Sonin as a consequence of his elimination algorithm for the optimal stopping of a Markov chain. In this algorithm the termination probability of the process may depend on the current state rather than being a fixed factor. A faster algorithm was proposed in 2007 by Niño-Mora by exploiting the structure of a parametric simplex to reduce the computational effort of the pivot steps and thereby achieving the same complexity as the Gaussian elimination algorithm. Cowan, W. and Katehakis (2014), provide a solution to the problem, with potentially non-Markovian, uncountable state space reward processes, under frameworks in which, either the discount factors may be non-uniform and vary over time, or the periods of activation of each bandit may be not be fixed or uniform, subject instead to a possibly stochastic duration of activation before a change to a different bandit is allowed. The solution is based on generalized restart-in-state indices.

Mathematical definition

Dynamic allocation index

The classical definition by Gittins et al. is:

[math]\displaystyle{ \nu(i)=\sup_{\tau\gt 0}\frac{ \left\langle\sum_{t=0}^{\tau-1}\beta^t R[Z(t)]\right\rangle_{Z(0)=i}}{ \left\langle\sum_{t=0}^{\tau-1}\beta^t \right\rangle_{Z(0)=i}} }[/math]

where [math]\displaystyle{ Z(\cdot) }[/math] is a stochastic process, [math]\displaystyle{ R(i) }[/math] is the utility (also called reward) associated to the discrete state [math]\displaystyle{ i }[/math], [math]\displaystyle{ \beta\lt 1 }[/math] is the probability that the stochastic process does not terminate, and [math]\displaystyle{ \langle\cdot\rangle_c }[/math] is the conditional expectation operator given c:

[math]\displaystyle{ \langle X\rangle_c \doteq \sum_{x\in\chi}x P\{X=x|c\} }[/math]

with [math]\displaystyle{ \chi }[/math] being the domain of X.

Retirement process formulation

The dynamic programming formulation in terms of retirement process, given by Whittle, is:

[math]\displaystyle{ w(i)=\inf\{k:v(i,k)=k\} }[/math]

where [math]\displaystyle{ v(i,k) }[/math] is the value function

[math]\displaystyle{ v(i,k)=\sup_{\tau\gt 0} \left\langle \sum_{t=0}^{\tau-1} \beta^t R[Z(t)] + \beta^t k \right\rangle_{Z(0) = i} }[/math]

with the same notation as above. It holds that

[math]\displaystyle{ \nu(i)=(1-\beta)w(i). }[/math]

Restart-in-state formulation

If [math]\displaystyle{ Z(\cdot) }[/math] is a Markov chain with rewards, the interpretation of Katehakis and Veinott (1987) associates to every state the action of restarting from one arbitrary state [math]\displaystyle{ i }[/math], thereby constructing a Markov decision process [math]\displaystyle{ M_i }[/math].

The Gittins Index of that state [math]\displaystyle{ i }[/math] is the highest total reward which can be achieved on [math]\displaystyle{ M_i }[/math] if one can always choose to continue or restart from that state [math]\displaystyle{ i }[/math].

[math]\displaystyle{ h(i)=\sup_\pi \left\langle \sum_{t=0}^{\tau-1} \beta^t R[Z^\pi(t)] \right\rangle_{Z(0) = i} }[/math]

where [math]\displaystyle{ \pi }[/math] indicates a policy over [math]\displaystyle{ M_i }[/math]. It holds that

[math]\displaystyle{ h(i)=w(i) }[/math].

Generalized index

If the probability of survival [math]\displaystyle{ \beta(i) }[/math] depends on the state [math]\displaystyle{ i }[/math], a generalization introduced by Sonin (2008) defines the Gittins index [math]\displaystyle{ \alpha(i) }[/math] as the maximum discounted total reward per chance of termination.

[math]\displaystyle{ \alpha(i)=\sup_{\tau\gt 0} \frac{R^\tau(i)}{Q^\tau(i)} }[/math]

where

[math]\displaystyle{ R^\tau(i)=\left\langle \sum_{t=0}^{\tau-1} R[Z(t)] \right\rangle_{Z(0) = i} }[/math]

[math]\displaystyle{ Q^\tau(i)=\left\langle 1 - \prod_{t=0}^{\tau-1} \beta[Z(t)] \right\rangle_{Z(0) = i} }[/math]

If [math]\displaystyle{ \beta^t }[/math] is replaced by [math]\displaystyle{ \prod_{j=0}^{t-1} \beta[Z(j)] }[/math] in the definitions of [math]\displaystyle{ \nu(i) }[/math], [math]\displaystyle{ w(i) }[/math] and [math]\displaystyle{ h(i) }[/math], then it holds that

[math]\displaystyle{ \alpha(i)=h(i)=w(i) }[/math]

[math]\displaystyle{ \alpha(i)\neq k \nu(i), \forall k }[/math]

this observation leads Sonin to conclude that [math]\displaystyle{ \alpha(i) }[/math] and not [math]\displaystyle{ \nu(i) }[/math] is the "true meaning" of the Gittins index.

Queueing theory

In queueing theory, Gittins index is used to determine the optimal scheduling of jobs, e.g., in an M/G/1 queue. The mean completion time of jobs under a Gittins index schedule can be determined using the SOAP approach. Note that the dynamics of the queue are intrinsically Markovian, and stochasticity is due to the arrival and service processes. This is in contrast to most of the works in the learning literature, where stochasticity is explicitly accounted through a noise term.

Fractional problems

While conventional Gittins indices induce a policy to optimize the accrual of a reward, a common problem setting consists of optimizing the ratio of accrued rewards. For example, this is a case for systems to maximize bandwidth, consisting of data over time, or minimize power consumption, consisting of energy over time.

This class of problems is different from the optimization of a semi-Markov reward process, because the latter one might select states with a disproportionate sojourn time just for accruing a higher reward. Instead, it corresponds to the class of linear-fractional markov reward optimization problem.

However, a detrimental aspect of such ratio optimizations is that, once the achieved ratio in some state is high, the optimization might select states leading to a low ratio because they bear a high probability of termination, so that the process is likely to terminate before the ratio drops significantly. A problem setting to prevent such early terminations consists of defining the optimization as maximization of the future ratio seen by each state. An indexation is conjectured to exist for this problem, be computable as simple variation on existing restart-in-state or state elimination algorithms and evaluated to work well in practice.

References

• Scully, Ziv and Harchol-Balter, Mor and Scheller-Wolf, Alan (2018). "SOAP: One Clean Analysis of All Age-Based Scheduling Policies". Proceedings of the ACM on Measurement and Analysis of Computing Systems (ACM) 2 (1): 16. doi:10.1145/3179419. 
• Berry, Donald A. and Fristedt, Bert (1985). Bandit problems: Sequential allocation of experiments. Monographs on Statistics and Applied Probability. London: Chapman & Hall. ISBN 978-0-412-24810-8. 
• Gittins, J.C. (1989). Multi-armed bandit allocation indices. Wiley-Interscience Series in Systems and Optimization.. foreword by Peter Whittle. Chichester: John Wiley & Sons, Ltd.. ISBN 978-0-471-92059-5. 
• Weber, R.R. (November 1992). "On the Gittins index for multiarmed bandits". The Annals of Applied Probability 2 (4): 1024–1033. doi:10.1214/aoap/1177005588. 
• "The multi-armed bandit problem: decomposition and computation". Mathematics of Operations Research 12 (2): 262–268. 1987. doi:10.1287/moor.12.2.262. 
• Cowan, W. and M.N. Katehakis (2014). "Multi-armed Bandits under General Depreciation and Commitment". Probability in the Engineering and Informational Sciences 29: 51–76. doi:10.1017/S0269964814000217. 

External links

• [1] Matlab/Octave implementation of the index computation algorithms
• Cowan, Robin (1991). "Tortoises and Hares: Choice Among Technologies of Unknown Merit". The Economic Journal 101 (407): 801–814. doi:10.2307/2233856.