The results are based on anovelanalysis ofreal-time dynamic programming, thenextended tomodel-based RL.Specifically,wegeneralize existing algorithms that perform full-planning to act by 1-step planning.

Real Time Dynamic Programming (RTDP) is an online algorithm based on Dynamic Programming (DP) that acts by 1-step greedy planning. Unlike DP, RTDP does not require access to the entire state space, i.e., it explicitly handles the exploration. This fact makes RTDP particularly appealing when the state space is large and it is not possible to update all states simultaneously. In this we devise a multi-step greedy RTDP algorithm, which we call $h$-RTDP, that replaces the 1-step greedy policy with a $h$-step lookahead policy. We analyze $h$-RTDP in its exact form and establish that increasing the lookahead horizon, $h$, results in an improved sample complexity, with the cost of additional computations. This is the first work that proves improved sample complexity as a result of {\em increasing} the lookahead horizon in online planning. We then analyze the performance of $h$-RTDP in three approximate settings: approximate model, approximate value updates, and approximate state representation. For these cases, we prove that the asymptotic performance of $h$-RTDP remains the same as that of a corresponding approximate DP algorithm, the best one can hope for without further assumptions on the approximation errors.

State-of-the-art efficient model-based Reinforcement Learning (RL) algorithms typically act by iteratively solving empirical models, i.e., by performing full-planning

We would like to begin by highlighting two contributions of the paper we feel remained unnoticed by R#2 and R#3. Due to its generality it is a powerful tool and is indeed central in all our analysis. RTDP is a well known and practical algorithm. We thank the reviewer for his/her favorable review. Abstract/Line 124/Line 263 - will be corrected, thanks!