acceptodds
Under review as a conference paper at ICLR 2027

Why Backward Induction Does Not Work in Sample-Based Reinforcement Learning?

Abstract

It is well known that, in exact finite-horizon dynamic programming, backward induction finds an optimal policy in a single backward sweep by selecting actions that maximize the action-value function. In sample-based reinforcement learning, however, the action-value function is unknown and must be estimated from data. Natural Policy Gradient (NPG) is widely used in this setting, updating the policy gradually according to estimated action values rather than directly selecting their maximizer. This raises a basic question: if hard maximization is sufficient under exact value information, why not use the same hard-max update in the sample-based setting? Equivalently, what explains the favorable behavior of NPG under noisy value estimates? We study this question in finite-horizon Markov decision processes by comparing sample-based hard-max updates with NPG under a common sampling model. We show that the two methods respond differently to estimation error: hard maximization is more sensitive to noisy value estimates, whereas NPG updates the policy more gradually. Our results clarify why the advantage of exact backward induction does not necessarily carry over to the sample-based setting.

Primary area:
reinforcement learning
Keywords:
finite-horizon Markov decision processes, backward induction, natural policy gradient, reinforcement learning, policy optimization

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_6aRSOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies finite-horizon tabular MDPs with generative-model (simulator) access, known rewards and unknown transitions. An algorithm can query any (h,s,a)(h,s,a) and receive one next state, and its cost is the total number of queries. The paper compares two planners that use samples only and build no transition model.

Critical strengths

The question is clearly posed and the proofs are complete and self-contained. The lower bound allows adaptive queries, and Table 1 together with Appendix 9.1 carefully converts prior results to the expected-gap criterion. The key steps appear correct, including the gap decomposition in Lemma 2, Lemmas 6–8 and the constants in Theorem 2, the variance and anti-concentration arguments in Lemmas 10–11, and the query count in Theorem 3. Section 6.3 openly states that the two procedures differ in both evaluation and update, and that the NPG bound is not optimal. The simulations use 500 independent runs and bootstrap intervals.

Critical weaknesses

W1. By the paper's own proofs, both methods need the same order of samples per (h,s,a)(h,s,a). Theorem 3 requires m≳H4/ε2m \gtrsim H^4/\varepsilon^2 rollouts per triple. Corollary 1 requires T≈H4log⁡A/ε2T \approx H^4\log A/\varepsilon^2 iterations with one sample per triple, which is even a log⁡A\log A factor more. The only difference is the cost of one sample. A backward-induction sample is a full rollout that costs H−hH-h transitions, while an NPG sample is a single transition. The extra factor HH is exactly the rollout length.

W2. Theorem 1 seems to adapt the construction of Kakade (2003) with a standard KL and Pinsker argument. Its rate is already known in online and generative settings (Domingues et al., 2021; Li et al., 2024), and the only change is the expected-gap criterion. Theorem 2 is a standard stochastic mirror descent analysis in the framework of Lan (2023) and Xiao (2022). It bounds the estimation error crudely by Lh2L_h^2 and is a factor Hlog⁡AH\log A above the lower bound. Theorem 3 is a lower bound for one specific naive implementation.

W3. The theoretical separation is only in the power of HH. At fixed HH, the ratio of query counts between the two methods is a constant. The experiment uses H=7H=7 only, so it cannot test the main result.

W4. The experiment fixes the step size at log⁡A/H\log A/H rather than the step size analyzed in Corollary 1.

Questions for authors

Q1. What is the sample complexity of NPG with fresh MC rollouts?

Q2. Do multiple sweeps (T>1T>1) change Theorem 3?

Q3. As HH varies, does the query ratio between NPG and backward induction grow like H/log⁡AH/\log A? Does NPG still win at larger budgets?

Reviewer_EgnGOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper asks why backward induction, which finds an optimal policy in one sweep when action values are exact, loses its advantage in sample-based reinforcement learning. It compares hard-max backward induction using fresh Monte Carlo rollouts with natural policy gradient (NPG) using one-step evaluation. The setting is finite-horizon tabular MDPs with a generative oracle, and performance is the expected optimality gap at an initial distribution. The authors prove three results: a lower bound for any agent, quartic in horizon; an NPG upper bound, quintic; and a backward-induction lower bound, sextic. They attribute the separation to hard-max retaining noise-induced selection errors, whereas NPG’s gradual update controls them through the step size. Simulations on one instance over 500 runs show NPG needing roughly 20–40% fewer queries for most accuracy targets, though backward induction wins at the loosest target and largest budgets.

Critical strengths
  1. The paper is clearly written and well organized. The theoretical development appears rigorous, with complete proofs and explicit constants.

  2. The authors adapt Kakade’s construction to establish an Ω(SAH4/ε2)\Omega(SAH^4/\varepsilon^2) lower bound under the expected-gap criterion that also covers adaptive query strategies. This is a careful and non-trivial derivation, and it gives a useful benchmark for the other two results.

  3. The experiments are small in scale, which is consistent with common practice in the tabular NPG literature. They are nonetheless carefully conducted: 500 independent runs, matched query budgets, and bootstrap confidence intervals. The authors also report regimes in which backward induction performs better.

Critical weaknesses
  1. The paper would benefit from a clearer statement of why this particular comparison matters.
  • The two procedures differ in both policy evaluation (fresh full Monte Carlo rollouts vs. one-step bootstrapped estimates) and policy update (hard-max vs. multiplicative). The separation therefore cannot be attributed to the update rule alone, as the title suggests.

  • Backward induction on an empirical model (Li et al., 2024; Table 1) already attains O~(SAH4/ε2)\widetilde{O}(SAH^4/\varepsilon^2), which improves on the NPG bound. The claim that backward induction “does not work” in the sample-based setting therefore seems overstated. It applies to one specific rollout-based implementation.

  • The relation of the derived bounds to existing NPG/PMD results is discussed only qualitatively, in Appendix 9.1 (see Question 7).

  1. The analysis is limited to tabular, finite-horizon MDPs with generative access, and both procedures sweep all (h,s,a)(h,s,a) triples at each iteration. The paper does not discuss whether its insight extends to online interaction, large state–action spaces, or function approximation. A brief discussion would broaden its relevance to the ICLR audience.

  2. Notation and definitions.

  • The instance symbol MM is used in Sec. 4.1 (Eq. (3)) and in Theorem 2 without a general definition. Defining M:=(S,A,H,P,R)M := (\mathcal{S},\mathcal{A},H,\mathcal{P},\mathcal{R}) in Sec. 2.1 would resolve this.

  • The role of ρ\rho should be stated explicitly. It is arbitrary in Sec. 4.1 and Theorem 2, but fixed as uniform over decision states for MK,A,H\mathcal{M}_{K,A,H} in Sec. 4.2.

  • The phrase “a common family” (Sec. 4.2) may be read as “commonly occurring”. “A shared family” would avoid this ambiguity.

  1. The simulations use a single instance, with labels fixed by one seed, from the family constructed for the lower bounds. This family is designed to be adversarial for backward induction. Results on other tabular MDPs, such as randomly generated MDPs or standard benchmarks, would show whether the observed advantage of NPG persists beyond this construction.
Questions for authors
  1. Appendix 9.1 argues that discounted PMD/NPG bounds do not translate directly to the finite-horizon setting. Could the authors nonetheless place the O(SAH5log⁡A/ε2)O(SAH^5\log A/\varepsilon^2) bound alongside the closest existing results, such as the stochastic finite-horizon analysis of Klein et al. (2024)? Is the new bound tighter than these in any regime?

  2. The two procedures differ in both policy evaluation and policy update. Can the authors say whether hard-max updates combined with one-step evaluation, or NPG combined with fresh Monte Carlo rollouts, would exhibit the same separation? This would show whether the gap is due to the update rule itself.

  3. Is the known-reward assumption essential to the results? If the rewards were also unknown, would the bounds change beyond lower-order terms?

  4. Both procedures enumerate all actions: hard-max in its maximization step, and NPG in its normalization and its queries over every (h,s,a)(h,s,a) triple. How might the insight extend to settings with very large action spaces or function approximation?

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

This paper claims that in finite-horizon dynamic programming under the sample-based setting, hard-max backward induction (BI) performs worse than natural policy gradient (NPG). The paper presents three informative sample complexity theorems. These are an information-theoretic lower bound, an upper bound for NPG with one-step evaluation, and a lower bound for BI with fresh Monte Carlo evaluation. The direct comparison of NPG (upper bound) and BI (lower bound), with complexity orders of SAH5/ϵ2SAH^5/\epsilon^2 and SAH6/ϵ2SAH^6/\epsilon^2 respectively, provides an insightful message on why, theoretically, BI fails and NPG performs better.

Critical strengths

Presentation. The authors clearly organize the message they intend to deliver and derive the theorems they intended to show. They explicitly provide a comparison. The simulation provides convincing and transparent results, in line with the authors' careful statements.

Critical weaknesses

Weakness 1. (Major concern) Although the theorems presented in this paper are informative and appear to be mathematically correct, they do not provide sufficient evidence for the main claim. The paper argues in the abstract that, under the sample-based setting, the main difference between NPG and BI lies in the hard-max operator of BI, and that the difference in sample complexity comes from the sensitivity of the hard-max to noise. To support this claim, the paper compares the lower bound Ω(SAH6/ϵ2)\Omega(SAH^6/\epsilon^2) for BI with the upper bound O(SAH5/ϵ2)O(SAH^5/\epsilon^2) for NPG. However, as the authors also mention, the algorithm of Li et al. (2024) achieves a complexity of order O~(SAH4/ϵ2)\tilde O(SAH^4/\epsilon^2), and as far as I understand, Li et al. (2024, Section 4.1) also uses the hard-max. Hence, this point seems to considerably weaken the main claim. A related issue is that NPG uses one-step evaluation in Section 5, whereas BI uses Monte Carlo evaluation in Section 6. To me, it seems that the difference in order might originate from this uncontrolled difference in evaluation, and I am not convinced that these different evaluation settings are compared under a fair criterion, since no reason or justification is given. This leads to the two questions (Q1, Q2) that I present below.

Weakness 2. Regarding the experiments. The main theorems compare NPG and BI with orders H5H^5 and H6H^6, respectively, so the claimed difference between the two is a factor of H. However, the numerical experiment compares them only at a fixed H = 7. I would like to see how the ratio of the query counts of BI and NPG varies with H, and whether this ratio grows linearly in H as the theorems predict. I believe this is important evidence for the authors to provide, because the title claims that "Backward Induction Does Not Work" and the difference is of order H.

I initially intended to recommend a weak accept, since this paper provides a clear organization, concise statements, and a convincing presentation. However, the concern I raised in Weakness 1 seems critical to me because it undermines the paper's main claim, and I would like to see a clearer distinction from previous work, in particular Li et al. (2024). I therefore maintain my rating of 2 (weak reject), and I am strongly willing to raise the rating toward 3 (weak accept) if my concern W1 and questions Q1 and Q2 are sufficiently addressed.

Questions for authors

Q1. Can the authors clearly justify why NPG is combined only with one-step evaluation, while BI uses only fresh MC? Is it impossible to combine BI with one-step evaluation, and if so, can the authors provide a reasonable justification? If it is possible, how might the complexity change?

Q2. Under the criterion provided in the paper (fresh MC vs. one-step, NPG vs. BI), which category does Li et al. (2024) belong to? As far as I understand, it should belong to BI with one-step evaluation. Li et al. (2024) does not explicitly mention one-step evaluation, but it appears to be BI based on Li et al. (2024, Section 4.1). Can the authors clearly state this categorization, and also distinguish the theoretical result of Li et al. (2024), SAH4/ϵ2SAH^4/\epsilon^2, from the results provided in this paper (NPG SAH5/ϵ2SAH^5/\epsilon^2 and BI SAH6/ϵ2SAH^6/\epsilon^2)?

Q3. Would it be possible to provide additional experiments that sweep H and show whether the difference of order H appears?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.