A (2/3)n^3 fast-pivoting algorithm for the Gittins index and optimal stopping of a Markov chain

DOI10.1287/IJOC.1060.0206arXiv2304.01840WikidataQ56001619 ScholiaQ56001619MaRDI QIDQ6432053FDOQ6432053

Publication date: 4 April 2023

Abstract: This paper presents a new emph{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 elimination. The algorithm further applies to the problem of optimal stopping of a Markov chain, for which a novel Gittins-index solution approach is introduced. The algorithm draws on Gittins and Jones' (1974) index definition via calibration, on Kallenberg's (1986) proposal of using parametric linear programming, on Dantzig's simplex method, on Varaiya et al.'s (1985) algorithm, and on the author's earlier work. The paper elucidates the structure of parametric simplex tableaux. Special structure is exploited to reduce the computational effort of pivot steps, decreasing the operation count by a factor of three relative to using conventional pivoting, and by a factor of

3 / 2

relative to recent state-elimination algorithms. A computational study demonstrates significant time savings against alternative algorithms.

Mathematics Subject Classification ID

Numerical analysis or methods applied to Markov chains (65C40) Stopping times; optimal stopping problems; gambling theory (60G40) Markov and semi-Markov decision processes (90C40)

This page was built for publication: A $(2/3)n^3$ fast-pivoting algorithm for the Gittins index and optimal stopping of a Markov chain

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6432053)