Polynomial-time solution of change detection problems

Change detection problems are ubiquitous, but there are no existing tractable techniques for e-exact solution of discrete-time, discrete-observation problems. A polynomial-time algorithm for solution of Markov Bayes change detection problems is presented. The algorithm combines backward induction on a tree with induction of bounds on the value function at specific points from those of neighboring points.