Monotonicity of value function iteration convergence

1

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?

2

Hi @Shunsuke-Hori, that sounds odd to me. I have a few questions that might help us diagnose the problem:

  • What norm are you using?
  • What “features” does the Bellman equation have? Are the states and controls both continuous?
  • What type of interpolation are you using?
3

Thank you, @spencer.lyon

Here is my answer:

  • Euclidean norm
  • Theoretically, they are continuous (but in computation, states (capital and shock) are descretized)
  • Linear interpolation

I do not think I am solving an irregular problem

4

Could you report back what the convergence behavior is if you use he supremum norm (max, absolute value)?

5

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.

1 Like
6

@spencer.lyon I took a brief look of some proofs and agree with you. I should use sup norm now (although others may be also OK as you guess)

However, even with sup norm, maximum of absolute value, I still sometimes see non-monotonic convergence

7

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.

8

@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

9

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).

10

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.