Computational Complexity

Let K=|S| and L=|A|, then the time complexity of the described algorithm is O(NLK²). The latter is derived from repeating the iterative step for t=1, 2, ..., N, calculating U_t(s_t) for K states, and a complexity of KL for the max operation.