In the realm of multi-arm bandit problems, the Gittins index policy is known
to be optimal in maximizing the expected total discounted reward obtained from
pulling the Markovian arms. In most realistic scenarios however, the Markovian
state transition probabilities are unknown and therefore the Gittins indices
cannot be computed. One can then resort to reinforcement learning (RL)
algorithms that explore the state space to learn these indices while exploiting
to maximize the reward collected. In this work, we propose tabular (QGI) and
Deep RL (DGN) algorithms for learning the Gittins index that are based on the
retirement formulation for the multi-arm bandit problem. When compared with
existing RL algorithms that learn the Gittins index, our algorithms have a
lower run time, require less storage space (small Q-table size in QGI and
smaller replay buffer in DGN), and illustrate better empirical convergence to
the Gittins index. This makes our algorithm well suited for problems with large
state spaces and is a viable alternative to existing methods. As a key
application, we demonstrate the use of our algorithms in minimizing the mean
flowtime in a job scheduling problem when jobs are available in batches and
have an unknown service time distribution. \

提出了一种基于退休公式的表格 (QGI) 和深度强化学习 (DGN) 算法来学习 Gittins 指标，在大状态空间问题中运行时间更短、存储空间要求更低 (QGI 中小的 Q 表尺寸，DGN 中较小的重放缓冲区)，并且展现了更好的实证收敛性，是现有方法的可行替代。