Dynamic Regret in Time-varying MDPs with Intermittent Information
For researchers in online learning and control, this provides a theoretical understanding of how intermittent information updates affect performance in non-stationary environments.
This paper studies decision-making in time-varying MDPs where the agent updates its model only intermittently due to constraints. It proposes a skip-update framework and derives a dynamic regret bound that quantifies how performance degrades with update rate, showing linear dependence on interval length and temporal variation.
We study sequential decision-making in time-varying Markov decision processes (TVMDPs) under limited update rates, where the decision-maker observes the system and updates its model only intermittently. Such settings arise in applications with sensing, communication, or computational constraints that preclude continuous adaptation. Our goal is to understand how the performance of an agent, which learns and plans using receding-horizon control under these information constraints, degrades as a function of the update rate. We propose a skip-update learning and planning framework that combines likelihood-based estimation of time-varying transition kernels with finite-horizon planning and executes policies between updates using stale information. We analyze its performance via dynamic regret relative to an oracle policy with full knowledge of the dynamics and continuous observations. Our main result establishes a dynamic regret bound that explicitly quantifies the impact of intermittent updates, decomposing regret into contributions from update times and skip intervals and revealing its dependence on temporal variation, estimation uncertainty, and the duration of intervals without updates. In particular, the dominant contribution from skip intervals admits a linear dependence on the interval length and the rate of temporal variation, while its effect is mitigated by mixing-induced contraction.