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

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.