A Note on Greedy Policies for Scheduling Scalar Gauss-Markov Systems

It is being stated in recent literature that greedy policies provide optimal scheduling for identical scalar Gauss-Markov systems. Here, the performance index is the sum of the covariances of the systems from time 1 to a time horizon N. The scheduling decisions from time 0 to N-1 constitute the policy. In this note we show that when N=1, the statement is true. Our main result is to show that when N=2 the greedy policy fails to be optimal for identical scalar Gauss-Markov systems, in contradiction to the statement, and illustrating the complexity of the problem.