acceptodds
Under review as a conference paper at ICLR 2027

Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead

Abstract

We study reinforcement learning (RL) with transition look-ahead, where the agent may observe which states would be visited upon playing any sequence of actions before deciding its course of action. Although look-ahead can substantially improve achievable performance, [1] showed that optimal planning with multi-step transition look-ahead is NP-hard. However, this hardness was established using a discount factor close to one. It was therefore unknown whether the problem remains hard for every discount factor, and whether near-optimal planning can nevertheless be performed efficiently. We resolve both questions. First, we show that for every fixed discount factor, exact planning remains NP-hard. Second, we introduce a randomized polynomial-time approximation scheme for every fixed look-ahead depth. Third, we extend our approach to account for unknown transitions. We empirically validate the soundness of our results on the wind-farm storage-control benchmark of [2], showing that our approach, optimally accounting for -step look-ahead information, offers substantially better performance than existing algorithms. [1] Corentin Pla, Hugo Richard, Marc Abeille, Nadav Merlis, Vianney Perchet : On the Hardness of Reinforcement Learning with Transition Look-Ahead [2] Chenbei Lu, Zaiwei Chen, Tongxin Li, Chenye Wu, Adam Wierman : Reinforcement Learning with Imperfect Transition Predictions: A Bellman-Jensen Approach

Primary area:
reinforcement learning
Keywords:
Reinforcement Learning

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_e2EdOpenReview ↗
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
  1. 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.

  2. The algorthmic framework uses sampled transition-table dictionary and online backward recursion avoid explicitly constructing the exponentially large augmented MDP, which is interesting.

  3. The paper provides approximation and regret guarantees and includes experiments demonstrating improvements over existing methods.

Critical weaknesses
  1. 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.

  2. 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.

  3. 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
  1. 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?

  2. 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.

  3. 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?

1 comment

We thank reviewer e2Ed for its careful reading and very interesting remarks.

W1, Q1: Scaling with ℓ\ell and computational advantage over simpler rolling-horizon planning methods

The complexity of RPTAS is exponential in ℓ\ell. 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 ℓ\ell 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ℓ)(s,C^\ell), where Cℓ∈ΩℓC^\ell\in\Omega^\ell is the current look-ahead window and ∣Ω∣=∣S∣∣S∣∣A∣|\Omega|=|\mathcal S|^{|\mathcal S||\mathcal 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 ℓ\ell (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\gamma=0.9,\ell=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=8N=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 ℓ\ell 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.

Reviewer_J3o5OpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies reinforcement learning with multi-step transition look-ahead, where the agent observes potential future transitions before selecting an action. The authors investigate the computational complexity of planning in this setting and develop efficient approximation and learning algorithms.

The main contributions are threefold. First, the paper strengthens previous hardness results by proving that exact planning remains NP-hard for every fixed rational discount factor γ∈(0,1)\gamma \in (0,1) and look-ahead depth ℓ≥2\ell \geq 2. Second, it establishes a randomized polynomial-time approximation scheme for every fixed ℓ\ell, providing a uniformly near-optimal policy without explicitly constructing the exponentially large augmented state space. Third, it extends the approach to unknown transition dynamics and establishes regret guarantees. Additional extensions address noisy transition predictions.

Critical strengths
  1. The combination of a strengthened NP-hardness result and an efficient approximation scheme provides a useful characterization of the computational landscape of reinforcement learning with multi-step transition look-ahead. In particular, the distinction between the hardness of exact planning and the tractability of near-optimal planning for fixed ℓ\ell is interesting and well motivated. The uniform approximation guarantee is especially valuable, as it applies to arbitrary observed look-ahead windows rather than only those encountered during preprocessing.

  2. The dictionary-based approximation and backward recursion provide a conceptually natural way to avoid enumerating the full augmented state space. The extension to unknown transitions, together with the regret analysis, makes the contribution more substantial than a standalone planning result. The empirical evaluation also provides encouraging evidence of the practical relevance of the approach.

Critical weaknesses

The main limitation is the scope of the empirical evaluation, which focuses on a single application benchmark. Although the reported improvements are encouraging, additional experiments would help establish how broadly the results translate to other environments.

Furthermore, the computational guarantees hold for fixed look-ahead depth ℓ\ell, and the dependence on ℓ\ell may limit practical scalability. A more explicit discussion of this trade-off would strengthen the presentation.

Questions for authors
  1. The experiments use a relatively small dictionary size (N=8N=8), while the theoretical guarantees allow substantially larger values of NN. How sensitive is the empirical performance to the dictionary size and its random initialization? Results across several independently sampled dictionaries would help assess the robustness of the method.

  2. In the hardness reduction, the constructed rewards are initially described as nonnegative but are not explicitly normalized to [0,1][0,1]. Could the authors clarify whether a common rescaling is implicitly assumed to ensure consistency with the MDP model in Section 2?

1 comment

We thank reviewer J3o5 for its carefull reading and very interesting remarks.

W1. On the empirical evaluation

We agree that experiments on more environments would strengthen the empirical evaluation. This paper is mainly theoretical, and our experiments aim to show that the theoretical properties of our algorithm can lead to better performance in practice. A more extensive empirical study is beyond the scope of this work and is left for future work.

W2. On the exponential dependence in ℓ\ell

We acknowledge that the exponential dependence on ℓ\ell limits scalability. However, such exponential dependence in $\ell $ also arises in existing approaches. BOLA [1] optimizes over ∣A∣ℓ|\mathcal A|^\ell action sequences in the general noisy setting, while scenario-based stochastic MPC can incur exponential growth with the prediction horizon [4], but none of these methods provides guarantees relative to the optimal look-ahead policy. Crucially, while exponential dependence on planning depth also arises in our method, we are the first to provide a method that runs in polynomial time and enjoys a near-optimality guarantee. This resolves the important open problem of efficient near-optimal planning with predictions refreshed at every step, highlighted by [1], [2], and [3].

Q1. On the small dictionary in the experiments We added Figure 2 to the manuscript (in Appendix, section B5 p34). It shows the convergence in performance RPTAS (in red) to that of the optimal-lookahead augmented policy (black dotted line) as the size of the dictionnary increases. Experiment is run in a 4-state, 2-action MDP γ=0.9,ℓ=2\gamma=0.9,\ell=2. The size 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.

To answer your question, we focus on dictionaries of size N=8N=8 because we already outperform other baselines with such a setting. As you can see in Figure 2, performance increases with the dictionary size but it seems to get close to optimum even for small dictionary sizes.

Q2. On the renormalization of rewards Yes, a common rescaling is implicitly assumed. Let Rmax⁡R_{\max} denote the largest reward in our construction. Dividing all rewards and the decision threshold by Rmax⁡R_{\max} ensures that rewards lie in [0,1][0,1], as required by our model. Such a normalization does not change the validity of our reduction. We thank the reviewer for noticing this discrepancy. In the revised version, we updated the proof so that the normalization is explicit.

[1] N. Merlis, Reinforcement learning with lookahead information (Neurips 2024)

[2] Pla & al, On the Hardness of Reinforcement Learning with Transition Look-Ahead (AISTATS 2026)

[3] Lu & al, Reinforcement Learning with Imperfect Transition Predictions: A Bellman-Jensen Approach (Neurips 2025)

Reviewer_kq9ROpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper suggests the theoretical result that the ℓ\ell-step (ℓ≥2\ell \ge 2) lookahead planning formulation is an NP-hard problem for every fixed γ\gamma (Theorem 1). Furthermore, the paper suggests an approximate algorithm (RPTAS) to solve ℓ\ell-step lookahead planning through randomization, and achieves polynomial-time calculation with near-optimality (Theorem 2). Furthermore, the paper suggests a version of RPTAS with Theorem 3 under the condition that the transition kernel PP is unknown. Empirically, the paper shows that the suggested algorithm RPTAS performs better on a specific benchmark compared to baseline algorithms.

Critical strengths

Informative contributions. Specifically, the suggested algorithm RPTAS gives a polynomial guarantee (in 1/ϵ1/\epsilon and 1/(1−γ)1/(1-\gamma)) under uniform near-optimality. Furthermore, the paper extends its own result to unknown kernel conditions.

Critical weaknesses

Weakness 1. Presentation.

(1) The motivation and significance of Theorem 1 are still insufficiently discussed. Compared to Pla et al. (2026a), the delta of Theorem 1 is mainly "fixed γ\gamma" in establishing that transition lookahead with ℓ≥2\ell \ge 2 is NP-hard. As the authors mentioned, the proof of Theorem 1 is almost identical to that of Pla et al. (2026a). So far, this explanation may cause a misunderstanding of the contribution of the paper, and the contribution might seem incremental. As far as I understand, the key takeaway of Theorem 1 is cause isolation, that the NP-hardness comes from the ℓ\ell-lookahead information structure rather than from the effective horizon (1−γ)−1(1-\gamma)^{-1}. However, it is written less explicitly than I expected. Although the authors mentioned that their established result claims that the difficulty does not rely on a large effective horizon, the paper does not emphasize why this is significant. Specifically, I expect that the fixed-γ\gamma hardness eliminates the possibility of exact planning with polynomial dependence on (1−γ)−1(1-\gamma)^{-1}, and leads to the necessity of the approximation scheme in Theorem 2.

(2) Connection between Theorem 1 and Theorem 2 (Algorithm 1). The presentation is not natural because the spine of the contribution of the paper is not condensed. Specifically, I understand that the approximation is required since the problem is NP-hard under fixed γ\gamma (Theorem 1), but why, then, is randomization required? I further wonder which specific part of the randomization makes RPTAS computable in polynomial time, compared to previous baselines. The relevant explanations appear in the Related Work, Section 4, and Appendix A.2, but they are scattered and not organized into a coherent claim. Hence, the motivation for randomization is unclear.

Weakness 2. Empirical validation

The authors mentioned that they "empirically validate the soundness of our results on the wind-farm storage-control benchmark", but the numerical simulations only present performance improvements compared to baseline methods. What I exactly expect from the simulation is rather evidence of "near-optimality", as this claim is central enough to appear in the title. Indeed, the numerical study does not give direct evidence of Theorem 2. Specifically, I would like to see evidence of the following tendencies on a small MDP by measuring Vℓ∗−VℓπV^*_\ell - V^{\pi}_\ell: (i) the suboptimality decreases as NN increases, (ii) how far the empirical suboptimality is below the theoretically calculated upper bound, and (iii) the dependency on 1−γ1-\gamma is as expected. Among (i)-(iii), I would specifically like to see the result of (ii) to check whether the bound is loose or not. (i) and (iii) can already be shown through the theorem, but they would be convincing if included. However, these experiments may require constructing another MDP rather than the benchmark of Lu et al. (2025).

Currently, my assessment lies between weak accept and weak reject. I recommend 3 (weak accept) with the expectation that the authors will sufficiently address my concerns. If these concerns are only partially resolved, I will consider lowering my score to 2 (weak reject).

Questions for authors

Q1. Do the authors agree with Weakness 1-(1)? Is there a further explanation that clarifies the motivation, significance, and novelty compared to Pla et al. (2026a)?

Q2. (Regarding regret minimization) Algorithm 3 and Theorem 3 show another result of RPTAS when the transition kernel PP is unknown, and the authors present this as a separate contribution. However, there is no numerical simulation for Algorithm 3. Is it possible to construct a numerical simulation to provide empirical evidence of Theorem 3, or is there a prepared explanation of why such an experiment is practically impossible?

4 comments

We thank reviewer kq9R for his carefull reading and very interesting remarks.

w1.1-Q1: On the motivation and significance of Theorem 1.

You are right, Theorem 1 extends the hardness result of Pla et al. (2026a) to any fixed discount factor. This shows that NP-hardness comes from the multi-step lookahead information structure rather than a large effective horizon. Indeed, the reduction of Pla et al. requires γ\gamma to be exponentially close to one, leaving open the possibility of an exact planning algorithm with polynomial dependence on 1/(1−γ)1/(1-\gamma). Theorem 1 shows that this is not possible. This directly motivates Theorem 2, which shows that uniformly near-optimal planning remains possible in polynomial time, including polynomial dependence on 1/(1−γ)1/(1-\gamma) and 1/ε1/\varepsilon, for fixed ℓ\ell. We updated the introduction of section 3 to make this connection clearer.

w1.2: Why is randomization necessary in the approximation scheme?

We do not claim that randomization is necessary for polynomial-time approximation: whether a deterministic scheme with the same guarantees exists remains open. The other baselines, sparse sampling and block-based methods, are not guaranteed to give near-optimal policies in polynomial time for fixed ℓ\ell.

Sparse sampling guarantees near-optimality, but its computational cost is exponential in the effective horizon. Specifically, for rewards bounded by one and absolute value tolerance ϵ\epsilon, Kearns et al. (2002, Theorem 1) give the per-decision running time

O\left(\frac{1}{1-\gamma} \log\frac{1}{\epsilon(1-\gamma)}\right)}.$$ This dependence arises because the algorithm recursively samples $C$ successors per action at every node, constructing a tree of size $O((|\mathcal A|C)^{\frac{1}{1-\gamma}})$. On the other hand, the block-based method in (Lu et al. (2025)) called BOLA solves the \$ \ell\$-lookahead problem by committing to an action sequence of size $\ell$, therefore reducing the problem of \$ \ell\$-lookahead to that of $1$-lookahead. Such an approach is suboptimal because new predictions are taken into account only every $\ell$ steps. A natural heuristic would then be to keep the same algorithm but commit only on the first action of the sequence. This heuristic, which we call \emph{receding BOLA} is, however, suboptimal because the value of a state is still computed as if the algorithm had to commit to $\ell$ actions in advance. In the Figure 2 added to the revised manuscript (in Appendix, section B5 p34), we see that BOLA and receding BOLA are not near-optimal. In our algorithm, we use randomness to construct the offline dictionary. The randomness ensures that averaging across points in the dictionary produces a good estimate of the expectation over possible next predictions. Whether it is possible to modify our algorithm to make it deterministic while keeping its near-optimality guarantees and its polynomial complexity is an interesting question that we leave to future work. Nevertheless, we consider that the current work is a major advance in the field of planning with lookahead despite our algorithm being random. We have revised Section 4.1 and the conclusion to clarify the novelty of our approach. **w2: Empirical validation.** **(i) and (ii) Suboptimality and dependency with respect to $N$ increases** We added Figure 2 to the revised manuscript (in Appendix, section B5 p34). It shows that the performance of RPTAS (in red) converges to the performance of the optimal-lookahead augmented policy (black dotted line) as the size of the dictionary increases. Experiment is run in a 4-state, 2-action MDP ($\gamma=0.9,\ell=2$). The size 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. As can be seen on Figure 2, RPTAS outperforms other baselines even for small dictionary sizes. **(iii)** We would appreciate some clarification on the experiment the reviewer has in mind. Do we understand correctly that the reviewer would instead like us to fix $N$ and study the effect of $\gamma$ empirically? **(Q2) Empirical validation of Theorem 3** Following the reviewer’s suggestion, we added a numerical experiment for Algorithm 3 (figure 3 in Appendix, section B5 p34). We use the same 4-states, 3-actions synthetic MDP as for Figure 2, with $\ell=2$, $\gamma=0.9$, known rewards, and unknown transitions. We run 10,000 independent simulations of 10,000 environment interactions. The added log--log plot shows the pointwise 0.90 percentile of the cumulative regret across the 10,000 runs, together with the leading term of theorem 3. The empirical regret remains below this reference curve and exhibits a similar sublinear growth pattern. The experiment therefore provides a numerical sanity check of the sublinear regret behavior predicted by Theorem 3.

A final remark.

We thank again the reviewer for the very interesting feedback, we agree with most of the comments raised and believe they will help us improve the paper. We would also like to emphasize that our RPTAS resolves a significant open question in the field of RL with lookahead as pointeed out by [1],[2], and [3], which we see as a major contribution. We hope our responses clarify this point, and would be happy to address any remaining issue that may prevent the reviewer from supporting a clear acceptance.

[1] N. Merlis, Reinforcement learning with lookahead information (Neurips 2024)

[2] Pla & al, On the Hardness of Reinforcement Learning with Transition Look-Ahead (AISTATS 2026)

[3] Lu & al, Reinforcement Learning with Imperfect Transition Predictions: A Bellman-Jensen Approach (Neurips 2025)

I sincerely appreciate the authors' response and revision.

Among the authors' responses, I am mainly satisfied with Figure 2, which directly shows the "near-optimality" that I emphasized as important in my review. Moreover, considering that this is a theoretical paper, I requested a substantial number of experiments, and the authors addressed most of them. I organize below which parts are resolved and which are not.

Resolved

W1-(1) and Q1. The authors agree with my concern on the motivation of Theorem 1. The revised introduction of Section 3 (lines 159-164) now states the takeaway explicitly. Theorem 1 separates the two possible causes of hardness, the long effective horizon and the multi-step look-ahead information structure, since NP-hardness persists for every fixed discount factor. The revision also states that Theorem 1 excludes an exact planning algorithm with polynomial dependence on 1/(1−γ)1/(1-\gamma), which motivates Theorem 2.

W1-(2). The response corrected my misunderstanding on randomization. Randomization is not claimed to be the only way to obtain a polynomial-time approximation, and the existence of a deterministic scheme remains open. Randomization is the tool that constructs the empirical approximation of the transition-table distribution (Section 4.1, lines 203-204), and the response justifies this choice. The revised Section 4.1 (lines 205-211) also collects in one place why sparse sampling and block-based methods do not give the same guarantee, which directly answers my question on previous baselines.

W2-(i). Figure 2 shows that RPTAS converges to the optimal look-ahead value as NN increases, and that RPTAS is close to the optimum even at small NN. This is the direct evidence of near-optimality that I requested.

Q2. Figure 3 provides numerical evidence for Theorem 3. The empirical regret stays below the theoretical curve and grows sublinearly.

Not resolved

W2-(ii). I should clarify my request. By "theoretically calculated upper bound" I meant the bound of Theorem 2 on the suboptimality, not the optimal value. Figure 2 compares RPTAS with the optimal look-ahead value, which resolves (i). My question in (ii) is how the guarantee of Theorem 2 compares with this empirical result.

Theorem 2 guarantees, with probability at least 1−δ1-\delta,

Vℓ⋆(s,c)−Vℓπ(s,c)≤εVmax⁡∀(s,c),N=O~(ℓ∣S∣∣A∣ε2(1−γ)4).V_\ell^\star(s,c) - V_\ell^{\pi}(s,c) \le \varepsilon V_{\max} \quad \forall (s,c), \qquad N = \tilde O\left(\frac{\ell|S||A|}{\varepsilon^2(1-\gamma)^4}\right).

Solving this relation for ε\varepsilon gives the value εthm(N)\varepsilon_{\mathrm{thm}}(N) that Theorem 2 guarantees at a given dictionary size NN. My request is the comparison of the following two quantities on the MDP of Figure 2.

Vℓ⋆−VℓπVmax⁡⏟empirical gapversusεthm(N)⏟guarantee of Theorem 2\underbrace{\frac{V_\ell^\star - V_\ell^{\pi}}{V_{\max}}}_{\text{empirical gap}} \quad \text{versus} \quad \underbrace{\varepsilon_{\mathrm{thm}}(N)}_{\text{guarantee of Theorem 2}}

Figure 2 already contains the empirical gap. Could the authors report εthm(N)\varepsilon_{\mathrm{thm}}(N) at the dictionary sizes of Figure 2, with the constants of Appendix A.2? If the guarantee is loose on this instance, a new figure is not necessary. In that case, could the authors add their interpretation of the gap? In particular, I would like to know whether the looseness is an artifact of the analysis, or whether a dictionary size of this order is necessary on worst-case instances. A short remark would be enough for me.

W2-(iii). Yes, the authors' understanding is correct. On the MDP of Figure 2, fix NN (for example N=8N=8), vary γ\gamma (for example γ∈0.5,0.7,0.9,0.95,0.99\gamma \in \\{0.5, 0.7, 0.9, 0.95, 0.99\\}), and report the normalized gap (Vℓ⋆−Vℓπ)/Vmax⁡(V_\ell^\star - V_\ell^{\pi})/V_{\max} for each γ\gamma. The purpose is to compare the change of the empirical gap with the dependence on 1/(1−γ)1/(1-\gamma) in Theorem 2, since polynomial dependence on 1/(1−γ)1/(1-\gamma) is the main advantage of RPTAS over sparse sampling. This item is optional, and (ii) has priority. If time does not allow the experiment, a commitment to include it in the final version is enough for me.

Rating

In my review, I wrote that I would consider lowering my score to 2 if my concerns were only partially resolved. The response and the revision have resolved my main concerns sufficiently, so I rule out lowering the score and recommend a rating of 3 (weak accept). If the remaining questions above, in particular W2-(ii), receive a sufficient answer and interpretation, I will consider between 3 and 4.

Thank you again for your quick answer and the quality of your review. We focus below on the remaining questions that you raised.

W2-(ii) From equation (55) of Appendix A.2, we have \begin{equation} \varepsilon_{thm}(N) = \frac{1}{(1-\gamma)^2} \sqrt{ \frac{8}{N} \left[ \log\frac{2}{\delta} +\bigl(1+(\ell-1)|S||A|\bigr)\log|S| \right] }. \end{equation}

For the MDP of Figure 2, we have ℓ=2,∣S∣=4\ell=2, |\mathcal{S}| = 4 and ∣A∣=3|\mathcal{A}| = 3. Setting γ=0.9,δ=0.9\gamma=0.9, \delta=0.9 and N=56N=56, we get 164≥εthm(N)≥163.164 \geq \varepsilon_{thm}(N) \geq 163.

The bound ϵ≤εthm(N)\epsilon \leq \varepsilon_{thm}(N) is therefore vacuous since it is worse than the trivial bound ϵ≤1\epsilon \leq 1.

Constants and worst-case bound The mismatch between εthm(N)\varepsilon_{thm}(N) and the empirical gap computed on the MDP of Figure 2 is mainly because the constants are not optimal, and because εthm(N)\varepsilon_{thm}(N) is a worst-case bound : it bounds the empirical gap for any MDP and is therefore very conservative. Indeed, a data-dependent bound would take into account the characteristics of the MDP it is applied to and, for instance, would predict a smaller empirical gap for an MDP with smaller variance, a distinction that our worst-case bound cannot make. Having such a data-dependent bound would be interesting, but we leave that to future work.

Improving the worst-case bound Let us note that our worst-case bound could be improved in several ways. We chose to use simple tools in order to keep the proof and the algorithm as simple and understandable as possible, but here are some rather classical tricks that could be used in order to get a better guarantee that we sketch quickly.

In Lemma 3, we used the Hoeffding inequality. Instead, one could proceed as in [1], where the authors apply a Bernstein inequality and smartly bound the resulting variance. Such manipulation would improve our bound by a factor 1/(1−γ)\sqrt{1/(1-\gamma)}.

A second sub-optimal step in our proof is when we bound the value of a policy greedy with respect to an ϵ\epsilon-optimal Q-value (line 1096 paragraph \emph{From score to values}). A smarter manipulation that avoids this step is detailed in [2] in what is called "The monotonicity technique" (p6). This manipulation would make us gain an additional factor 1/(1−γ)1/(1 - \gamma).

Combining the two tricks would give ϵthm(N)\epsilon_{thm}(N) on the order of ℓ∣S∣∣A∣N(1−γ)\sqrt{\frac{\ell |\mathcal{S}| |\mathcal{A}|}{N (1 - \gamma)}}. We deliberately chose not to include these improvements to keep our proofs and our algorithm simple. We believe our paper is more readable that way.

[1] Azar & al. On the Sample Complexity of Reinforcement Learning with a Generative Model

[2] Sidford & al. Near-Optimal Time and Sample Complexities for Solving Discounted Markov Decision Process with a Generative Model

W2-(iii). As requested, we added Figure 4 p 35. The experimental protocol is detailed lines 1819-1835. We use the same MDP as for figure 2, fix (N=16) and vary γ∈{0.5,0.7,0.8,0.9,0.95,0.98,0.99}\gamma\in\{0.5,0.7,0.8,0.9,0.95,0.98,0.99\}. We report the worst-case value gap (over 1000 episode seeds) averaged over 100 dictionaries. We note that for larger effective horizons, the absolute gap remains approximately constant, while the normalized gap decreases.

This observation complements our response to W2-(ii): the horizon dependence in Theorem 2 is a worst-case upper bound and need not describe the behaviour of each individual MDP. Favorable instances may exhibit an even better dependence, potentially admitting horizon-independent bounds as illustrated by this experiment. Again, this motivates an instance-dependent analysis that exploits its transition structure. We let this question as futur work.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.