Adaptive Social Learning for Slow Markov Chains

This paper studies the problem of interconnected agents collaborating to track a dynamic state from partially informative observations, where the state follows a slow finite-state Markov chain. While the centralized version of this problem is well understood, the decentralized setting warrants further exploration. This work aims to demonstrate that a decentralized social learning strategy can achieve the same error probability scaling law in the rare transitions regime as the optimal centralized solution. To study this problem, we focus on adaptive social learning (ASL), a recent strategy developed for non-stationary environments, and analyze its performance when the agents’ observations are governed by a hidden, slow Markov chain. Our study yields two key findings. First, we demonstrate that the ASL adaptation performance is closely linked to the dynamics of the underlying Markov chain, achieving a vanishing steady-state error probability when the average drift time of the Markov chain exceeds the ASL adaptation time. Second, we derive a closed-form upper bound for the ASL steady-state error probability in the rare transition regime, showing that it decays similarly to the optimal centralized solution. Simulations illustrate our theoretical findings and provide a comparative analysis with existing strategies.