  This paper considers the efficient exact computation of the counterpart of
the Gittins index for a finite-horizon discrete-state bandit, which measures
for each initial state the average productivity, given by the maximum ratio of
expected total discounted reward earned to expected total discounted time
expended that can be achieved through a number of successive plays stopping by
the given horizon. Besides characterizing optimal policies for the
finite-horizon one-armed bandit problem, such an index provides a suboptimal
heuristic index rule for the intractable finite-horizon multiarmed bandit
problem, which represents the natural extension of the Gittins index rule
(optimal in the infinite-horizon case). Although such a finite-horizon index
was introduced in classic work in the 1950s, investigation of its efficient
exact computation has received scant attention. This paper introduces a
recursive adaptive-greedy algorithm using only arithmetic operations that
computes the index in (pseudo-)polynomial time in the problem parameters
(number of project states and time horizon length). In the special case of a
project with limited transitions per state, the complexity is either reduced or
depends only on the length of the time horizon. The proposed algorithm is
benchmarked in a computational study against the conventional calibration
method.
