Semantic-Aware Remote Estimation of Multiple Markov Sources Under Constraints

This paper studies the remote estimation of multiple Markov sources over a lossy and rate-constrained channel. Unlike most existing studies that treat all source states equally, we exploit the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">semantics of information</i> and consider that the remote actuator has different tolerances for the estimation errors. We aim to find an optimal scheduling policy that minimizes the long-term <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">state-dependent</i> costs of estimation errors under a transmission frequency constraint. The optimal scheduling problem is formulated as a <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">constrained Markov decision process</i> (CMDP). We show that the optimal Lagrangian cost follows a piece-wise linear and concave (PWLC) function, and the optimal policy is, at most, a randomized mixture of two simple deterministic policies. By exploiting the structural results, we develop a new <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">intersection search</i> algorithm that finds the optimal policy using only a few iterations. We further propose a reinforcement learning (RL) algorithm to compute the optimal policy without knowing <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">a priori</i> the channel and source statistics. To avoid the “curse of dimensionality” in MDPs, we propose an online low-complexity <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">drift-plus-penalty</i> (DPP) algorithm. Numerical results show that continuous transmission is inefficient, and remarkably, our semantic-aware policies can attain the optimum by strategically utilizing fewer transmissions by exploiting the timing of the important information.