Title: An Index Policy for Minimizing the Uncertainty-of-Information of Markov Sources Show Chinese title

Title: 一种用于最小化马尔可夫信源信息不确定性的索引策略

Abstract: This paper focuses on the information freshness of finite-state Markov sources, using the uncertainty of information (UoI) as the performance metric. Measured by Shannon's entropy, UoI can capture not only the transition dynamics of the Markov source but also the different evolutions of information quality caused by the different values of the last observation. We consider an information update system with M finite-state Markov sources transmitting information to a remote monitor via m communication channels. Our goal is to explore the optimal scheduling policy to minimize the sum-UoI of the Markov sources. The problem is formulated as a restless multi-armed bandit (RMAB). We relax the RMAB and then decouple the relaxed problem into M single bandit problems. Analyzing the single bandit problem provides useful properties with which the relaxed problem reduces to maximizing a concave and piecewise linear function, allowing us to develop a gradient method to solve the relaxed problem and obtain its optimal policy. By rounding up the optimal policy for the relaxed problem, we obtain an index policy for the original RMAB problem. Notably, the proposed index policy is universal in the sense that it applies to general RMABs with bounded cost functions. Show Chinese abstract

Abstract: 本文专注于有限状态马尔可夫信源的信息新鲜度，使用信息不确定性（UoI）作为性能指标。 通过香农熵衡量，UoI不仅可以捕捉马尔可夫信源的转移动态，还可以捕捉由于最后一次观测值的不同而导致的信息质量的不同演化。 我们考虑一个包含M个有限状态马尔可夫信源通过m个通信信道向远程监控器传输信息的信息更新系统。 我们的目标是探索最优调度策略，以最小化马尔可夫信源的总UoI。 这个问题被建模为一个不可休息的多臂老虎机（RMAB）。 我们放松RMAB，然后将放松后的问题分解为M个单老虎机问题。 分析单老虎机问题提供了有用性质，使得放松后的问题转化为最大化一个凹函数和分段线性函数，使我们能够开发一种梯度方法来解决放松后的问题并获得其最优策略。 通过对放松后问题的最优策略进行向上取整，我们得到原始RMAB问题的索引策略。 值得注意的是，所提出的索引策略在某种意义上是通用的，因为它适用于具有有界代价函数的一般RMAB。