Synchronous Online Abstract Dynamic Programming

This paper addresses the abstract dynamic programming (DP) in the online scenario, where the abstract DP mapping is time-varying, instead of static. In this case, optimal costs and policies at different time instants are not the same in general, and the problem amounts to tracking time-varying optimal costs and policies, which is of interest to many practical problems. It is thus necessary to analyze the performance of classical value iteration (VI) and policy iteration (PI) algorithms in the online case. In doing so, this paper develops and provides the theoretical analysis for several online algorithms, including approximate online VI, online PI, approximate online PI, online optimistic PI, and approximate online optimistic PI algorithms. It is proved that the tracking error bounds for all algorithms critically depend upon the largest difference between any two consecutive abstract mappings. Meanwhile, examples are presented to illustrate the theoretical results.