A (2/3)<i>n</i><sup>3</sup> Fast-Pivoting Algorithm for the Gittins Index and Optimal Stopping of a Markov Chain
A (2/3)<i>n</i><sup>3</sup> Fast-Pivoting Algorithm for the Gittins Index and Optimal Stopping of a Markov Chain
This paper presents a new fast-pivoting algorithm that computes the n Gittins index values of an n-state bandit—in the discounted and undiscounted cases—by performing (2/3)n 3 + O(n 2 ) arithmetic operations, thus attaining better complexity than previous algorithms and matching that of solving a corresponding linear-equation system by Gaussian …