Gittins index

The classical definition by Gittins et al. is:

${\displaystyle \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 ${\displaystyle Z(\cdot )}$ is a stochastic process, ${\displaystyle R(i)}$ is the utility (also called reward) associated to the discrete state ${\displaystyle i}$, ${\displaystyle \beta <1}$ is the probability that the stochastic process does not terminate, and ${\displaystyle \langle \cdot \rangle _{c}}$ is the conditional expectation operator given c:

${\displaystyle \langle X\rangle _{c}\doteq \sum _{x\in \chi }xP\{X=x|c\}}$

with ${\displaystyle \chi }$ being the domain of X.

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

${\displaystyle w(i)=\inf\{k:v(i,k)=k\}}$

where ${\displaystyle v(i,k)}$ is the value function

${\displaystyle 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

${\displaystyle \nu (i)=(1-\beta )w(i).}$

If ${\displaystyle 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 ${\displaystyle i}$, thereby constructing a Markov decision process ${\displaystyle M_{i}}$.

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

${\displaystyle h(i)=\sup _{\pi }\left\langle \sum _{t=0}^{\tau -1}\beta ^{t}R[Z^{\pi }(t)]\right\rangle _{Z(0)=i}}$

where ${\displaystyle \pi }$ indicates a policy over ${\displaystyle M_{i}}$. It holds that

${\displaystyle h(i)=w(i)}$.

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

${\displaystyle \alpha (i)=\sup _{\tau >0}{\frac {R^{\tau }(i)}{Q^{\tau }(i)}}}$

where

${\displaystyle R^{\tau }(i)=\left\langle \sum _{t=0}^{\tau -1}R[Z(t)]\right\rangle _{Z(0)=i}}$

${\displaystyle Q^{\tau }(i)=\left\langle 1-\prod _{t=0}^{\tau -1}\beta [Z(t)]\right\rangle _{Z(0)=i}}$

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

${\displaystyle \alpha (i)=h(i)=w(i)}$

${\displaystyle \alpha (i)\neq k\nu (i),\forall k}$

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