Gittins index

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. 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{{cite journal LCM Kallenberg{{cite journal ==Mathematical definition==

Dynamic allocation index The classical definition by Gittins et al. is: :\nu(i)=\sup_{\tau>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}} where Z(\cdot) is a stochastic process, R(i) is the utility (also called reward) associated to the discrete state i, \beta is the probability that the stochastic process does not terminate, and \langle\cdot\rangle_c is the conditional expectation operator given c: :\langle X\rangle_c \doteq \sum_{x\in\chi}x P\{X=x|c\} with \chi being the domain of X. Retirement process formulation The dynamic programming formulation in terms of retirement process, given by Whittle, is: :w(i)=\inf\{k:v(i,k)=k\} where v(i,k) is the value function :v(i,k)=\sup_{\tau>0} \left\langle \sum_{t=0}^{\tau-1} \beta^t R[Z(t)] + \beta^t k \right\rangle_{Z(0) = i} with the same notation as above. It holds that :\nu(i)=(1-\beta)w(i). Restart-in-state formulation If Z(\cdot) 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 i, thereby constructing a Markov decision process M_i. The Gittins Index of that state i is the highest total reward which can be achieved on M_i if one can always choose to continue or restart from that state i. :h(i)=\sup_\pi \left\langle \sum_{t=0}^{\tau-1} \beta^t R[Z^\pi(t)] \right\rangle_{Z(0) = i} where \pi indicates a policy over M_i. It holds that :h(i)=w(i). Generalized index If the probability of survival \beta(i) depends on the state i, a generalization introduced by Sonin (2008) defines the Gittins index \alpha(i) as the maximum discounted total reward per chance of termination. :\alpha(i)=\sup_{\tau>0} \frac{R^\tau(i)}{Q^\tau(i)} where ::R^\tau(i)=\left\langle \sum_{t=0}^{\tau-1} R[Z(t)] \right\rangle_{Z(0) = i} ::Q^\tau(i)=\left\langle 1 - \prod_{t=0}^{\tau-1} \beta[Z(t)] \right\rangle_{Z(0) = i} If \beta^t is replaced by \prod_{j=0}^{t-1} \beta[Z(j)] in the definitions of \nu(i), w(i) and h(i), then it holds that :\alpha(i)=h(i)=w(i) :\alpha(i)\neq k \nu(i), \forall k this observation leads Sonin to conclude that \alpha(i) and not \nu(i) 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. ==Notes==