One Sample Is Not An Expectation

A team has a simulator that returns a sampled $(r, s')$ for any $(s, a)$ , but no access to $p(s' \mid s, a)$ . They keep their value-iteration loop and swap the expectation for one sampled successor per action:

for s in states:
    targets = []
    for a in actions:
        r, s_next = simulator.step(s, a)      # one sampled transition
        targets.append(r + gamma * v[s_next])
    v[s] = max(targets)

The environment is stochastic. What actually goes wrong, and what does the model-free fix change?

It converges as long as $\gamma < 1$ , since discounting bounds the contribution of the sampled successor and shrinks the sampling error geometrically.

The assignment overwrites the estimate with whichever successor was drawn, so nothing averages the samples and the values oscillate; the max over noisy estimates also biases them upward. Q-learning restores the averaging with a step size $\alpha$ .

Nothing breaks in principle: each sampled backup is an unbiased estimate of the expected backup, so repeated sweeps converge to $v_*$ ∗ exactly as the model-based version does.

The loop is unusable no matter what the dynamics are, because dynamic programming needs the reward function in closed form, so it would still be wrong on a deterministic environment.