Stationary and Transient Bounds for Nearly Lumpable or Uncertain Markov Chains
Peter Buchholz
Continuous-time and discrete-time Markov chains often face two major challenges, state space explosion and uncertainty in transition rates or probabilities. State space explosion can be mitigated through state aggregation, which reduces the number of states. However, aggregation typically introduces uncertainty in the transition matrix, resulting in a Markov process with imprecise parameters. This paper defines several variants of parameter uncertainty and presents methods to compute bounds for stationary, transient, and accumulated rewards in Markov chains with uncertain transition matrices and reward structures. For certain types of parameter uncertainty, the problem can be reformulated as an optimization problem for Markov decision processes, allowing the computation of tight bounds. For other variants, however, the resulting optimization problems are non-convex, and tightness of the computed bounds cannot, in general, be guaranteed.