fitted value iteration

Value iteration for the function-approximation world. Classic value iteration sweeps every state and replaces its value with the best one-step backup; you cannot do that when there are too many states to enumerate. Fitted value iteration instead samples a batch of states, computes the backed-up target for each, and then fits a function approximator to those (state, target) pairs by regression. Then it repeats.

Each iteration is two steps: first compute targets y_i = max_a [r + gamma v_old(s'_i)] for sampled transitions, then regress v_new to minimize the sum of squared errors against those targets. The approximator and the Bellman backup alternate. With a contraction in sup-norm and an exact fit each round it would converge; in practice the regression introduces an approximation error each step.

The danger is that the fit is a projection in a weighted L2 norm, but the Bellman backup contracts only in sup-norm — the two need not compose to a contraction, so errors can accumulate or even diverge. Fitted Q-iteration is the action-value version and is the more commonly used form.