This question is not directly related to QuantEcon lecture

I am writing a program to implement value function iteration with discretized grid and interpolation

The value function iteration must converge monotonically, at least in continuous case

However, I sometimes face a case in which the difference of old value and new value, measured by the norm of the gap, increases for a couple of iterations and goes back to decline (namely, the convergence is non-monotonic)

The value eventually converges to a certain value, which does not depend on initial guess (likely to be true one?)

Does it mean I am doing something wrong? or Is it a matter of discretization?

A little more info on why I ask about the sup norm.

The standard arguments for why VFI should have a monotonically decreasing error come from the contraction mapping theorem (Theorem 3.2 in Stokey and Lucas).

To apply this theorem we need to know that the natural operator defined by the Bellman equation (T in the notation of Stokey and Lucas) is a contraction mapping. To show this, people usually appeal to Blackwellâ€™s conditions (Theorem 3.3 in Stokey and Lucas). Blackwellâ€™s conditions are sufficient conditions for an T to be a contraction mapping, on the space of continuous, bounded functions under the sup norm.

So, to use â€śstandard dynamic programming argumentsâ€ť to argue that VFI should be monotonic, you should be considering the sup norm. I would imagine that in many cases you can prove a similar set of results under different norms, but I havenâ€™t seen/written those proofs.

I was wondering whether in (S&L, Theorem 3.3) continuity is really necessary? There the authors speak about â€śa space of bounded functionsâ€ť only. I imagine that it could sometimes be useful to consider elements with discontinuities.

Could you give a numerical estimate for the modulus of contraction? Is it close to one?

Also, could the problem be due to how you measure the sup-norm of the difference between iterates? (Perhaps you are not really measuring the true sup-norm, but only the sup-norm of a difference of interpolants?)

Sorry if these remarks are trivial or unhelpful. I find it a nice problem, so thank you for posting it.

@Janssens Approximately, contraction modulus is 0.7. I am not sure it is close to one, but the convergence must be slow because I set discount factor 0.99

Right, I measure the sup-norm of a difference of interpolants since discrete grid is used

As you suspect, continuity is not necessary for the basic results about convergence of the Bellman operator. The space of bounded real-valued functions with the sup norm is complete and all the theory goes through. Value functions with discontinuities are fine.

Of course once numerical approximation comes into play these results start to break downâ€¦

Also, in a stochastic setting, you need some regularity beyond just boundedness, otherwise you can have measurability problems. In my text I insist on continuity in the stochastic setting to mitigate this problem (although a finite number of discontinuities should be fine too).

I suspect, and I would like to hear thoughts, that (semi) continuity of the value-function and of the feasible correspondence is required to give existence of maximizers i.e. a policy function. Hence section 3.3 in SLP. We can prove existence of a value function on the space of bounded functions, but I am not sure how one can replace â€śsupâ€ť with â€śmaxâ€ť on the RHS of the Bellman Equation without (semi) continuity.