  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, approximate online optimistic PI, and asynchronous online PI and
VI 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.
