- Rating
- 3
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies reinforcement learning with multi-step transition lookahead. The authors strengthen an existing NP-hardness result and propose a randomized polynomial-time approximation scheme (RPTAS) that achieves uniform near-optimality for any fixed lookahead depth. The framework is further extended to unknown transitions and noisy lookahead, with corresponding regret guarantees.
Critical strengths
-
I think the theoretical contribution is meaningful. The paper addresses an interesting question regarding the computational tractability of multi-step transition lookahead. The polynomial-time near-optimal planning despite the NP-hardness of exact planning is a valuable result.
-
The algorthmic framework uses sampled transition-table dictionary and online backward recursion avoid explicitly constructing the exponentially large augmented MDP, which is interesting.
-
The paper provides approximation and regret guarantees and includes experiments demonstrating improvements over existing methods.
Critical weaknesses
-
In my opinion, the computational efficiency remains a concern. Although the algorithm is polynomial-time for fixed lookahead depth l, its complexity scales as N^l, where N itself has substantial polynomial dependence on the problem parameters. The dependence on l remains exponential, potentially limiting practical scalability.
-
Conventional finite-horizon lookahead planning can be solved efficiently using backward dynamic programming. Although it does not provide the same infinite-horizon guarantee, a stronger comparison with rolling-horizon methods using appropriate terminal values would help clarify the practical advantages of RPTAS.
-
Limited experimental validation of the approximation scheme. The experiments use only N=8, which is way smaller than that of most tabular MDPs, while the theoretical dictionary-size requirement can be much larger. Sensitivity analysis with respect to N, along with runtime comparisons and empirical approximation gaps on small MDPs, would strengthen the results.
Questions for authors
-
Given that the complexity scales as N^l, how does the algorithm scale with the lookahead depth in practice? What is its computational advantage over simpler rolling-horizon planning methods?
-
Would RPTAS still outperform a rolling version of BOLA-BAYES that replans at every step using the same posterior model and terminal value? This comparison would help clarify the source of the performance improvement.
-
The experiments use only N=8, while the theoretical requirement can be substantially larger. How sensitive is the performance to N, and is there empirical evidence that such a small dictionary achieves near-optimal performance?
We thank reviewer e2Ed for its careful reading and very interesting remarks.
W1, Q1: Scaling with ℓ and computational advantage over simpler rolling-horizon planning methods
The complexity of RPTAS is exponential in ℓ. We refer the reviewer to the answer W2 of reviewer J3o5 and to the answer w1.2 of reviewer kq9R. In short, BOLA and stochastic MPC also have an exponential complexity in ℓ but do not enjoy the theoretical guarantees we have, while the complexity of sparse sampling is exponential in the effective horizon.
W2: "Conventional finite-horizon lookahead planning can be solved efficiently using backward dynamic programming."
This is not true in this setting. We agree that a standard finite-horizon MDP can be solved efficiently by backward dynamic programming when its state space is explicitly represented. However, here, the Markov state would be the augmented state (s,Cℓ), where Cℓ∈Ωℓ is the current look-ahead window and ∣Ω∣=∣S∣∣S∣∣A∣. Thus, applying backward dynamic programming directly requires reasoning over an exponentially large augmented state space. Similarly, truncating the discounted problem at an effective horizon controls the truncation error, but does not remove this issue: future look-ahead windows are random and are revealed sequentially, and the policy can adapt to each newly revealed window.
If you refers to backward induction over the currently observed finite look-ahead tree, we agree that this can be done efficiently for fixed ℓ (in the perfect look-ahead setting), however, this only optimizes over the current window and requires a terminal value for what happens afterwards if you want to act optimally. Our RPTAS is precisely designed to provide this continuation value without enumerating the augmented state space.
W2-Q2-Q3 : On the comparison with the rolling version of BOLA-Bayes and the size of the dictionnaries
Figure 2, that is added in the revised submission (in Appendix, section B5 p34), compares RPTAS with a rolling version of BOLA-Bayes and zero-terminal MPC on a 4-state, 3-action MDP (γ=0.9,ℓ=2). The size of the MDP is chosen so that the optimal augmented-state policy remains computable. Results average over 100 independently sampled dictionaries, with approximate 95% confidence intervals for the mean. We focus on small dictionaries because N=8 already outperforms both baselines and approaches the optimum. Although rolling BOLA improves over MPC, its terminal value is derived from a Bellman equation that commits to batches of ℓ actions. This criterion does not anticipate adaptation to newly arriving predictions, so its batch-optimality guarantee does not transfer to the rolling setting. Our planner explicitly accounts for these updates and targets the optimal rolling-lookahead policy.