提出BLINQ算法，高效学习马尔可夫决策过程的威特利指数。
Model-Based Learning of Whittle indices
- 基于经验模型构建与改进算法计算威特利指数
- 理论证明收敛性并给出精确学习所需时间上界
- 样本效率与计算成本均优于传统Q-learning
我们提出BLINQ，一种新型基于模型的算法，用于学习可索引、连通且单链马尔可夫决策过程（MDP）的威特利指数。该方法通过构建经验模型，并使用改进的前沿算法计算其威特利指数。我们提供了收敛到目标威特利指数的证明，以及以任意精度学习所需的最长时间上界。此外，分析了其计算复杂度。数值实验表明，与现有Q-learning方法相比，BLINQ在获得准确近似所需样本数上显著更优；且在合理高样本量下，总计算成本甚至低于Q-learning。即使对Q-learning使用神经网络加速预测Q值，这一优势仍持续存在。
原文摘要 · Abstract (English)
We present BLINQ, a new model-based algorithm that learns the Whittle indices of an indexable, communicating and unichain Markov Decision Process (MDP). Our approach relies on building an empirical estimate of the MDP and then computing its Whittle indices using an extended version of a state-of-the-art existing algorithm. We provide a proof of convergence to the Whittle indices we want to learn as well as a bound on the time needed to learn them with arbitrary precision. Moreover, we investigate its computational complexity. Our numerical experiments suggest that BLINQ significantly outperforms existing Q-learning approaches in terms of the number of samples needed to get an accurate approximation. In addition, it has a total computational cost even lower than Q-learning for any reasonably high number of samples. These observations persist even when the Q-learning algorithms are speeded up using neural networks to predict Q-values.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。