Grid Interpolation Layer (vfoptions.gridinterplayer=1)

1

VFI Toolkit can now do a ‘second layer’ of interpolation on a finer grid. Currently this works for all the baseline finite-horizon problems, it will gradually roll-out to everything else.

As user you just set
vfoptions.gridinterplayer=1
which tells toolkit to use a ‘gridded interpolation layer’, and then use
vfoptions.ngridinterp=5
to say how many points to use for the interpolation.
And then you put the same into simoptions.

Idea is that if you have, say, n_a=20 (and so a_grid is 20-by-1), then between every two consecutive points on the a_grid it will put vfoptions.ngridinterp evenly spaced points. Conceptually, the problem we want to solve is using aprime_grid=interp1(1:1:N_a,a_grid,linspace(1,N_a,N_a+(N_a-1)*vfoptions.ngridinterpt)); (N_a=prod(n_a);) We evaluate the ReturnFn exactly on this aprime_grid, and we linearly interpolate E[V] (the expected next period value function) from a_grid onto aprime_grid.

This pdf explains what grid interpolation layer is and provides pseudocode. Following is intended to give you the intuition.

In the ‘first layer’ the codes just do the usual thing of solving ‘pure discretization’ with the 20 points on next period assets (the same points used for current assets, so a_grid). This gives us the optimal aprime index (on the a_grid).

In the 'second layer’, the codes consider the range for aprime from one a_grid point below the optimal aprime index to one point above, and puts ‘vfoptions.ngridinterp’ points between each of the original grid points, so considers a total of 2*vfoptions.ngridinterp+3 points. This is done conditional on any decision variables, d. Finally find the optimal of these, using exact valuation of the ReturnFn, and linear interpolation of E[V].

The output for the value function is essentially the same, and the interpretation is identical. The output for the policy function now contains two indexes for the aprime value, the first is a ‘lower grid point’ and the second is from 1-to-(vfoptions.ngridinterp+2) and the two endpoints represent the lower grid point and the upper grid point (and the rest count the evenly spaced points we interpolated onto).

You can use divide-and-conquer (vfoptions.divideandconquer=1) together with grid interpolation layer. In this case, there are the same two layers as described above, and divide-and-conquer is used to solve the first layer.

1 Like
2

Very clear, thanks!

There is a typo in the pseudo code of the second layer:

Solve for optimal aprime on second layer grid

g_j(a,z) = \arg \max_{i} F(aL2grid(i),a,z)

The line above should have also the interpolated EV

3

Fixed, and put a hat on the interpolated EV to be clear it is a different object than was used in the first layer.

1 Like
4

I have a suggestion for a small improvement to the interpolation codes. I tried it out for the simple case with (a',a,z) and no d variable but the principle should apply in general.

In ValueFnIter_FHorz_GI_raw the interpolation step is done as follows:

for z_c=1:N_z
        % omitted
        EV_z=sum(EV_z,2); % size: [N_a,1]
        % Interpolate EV over aprime_grid
        EVinterp_z=interp1(a_grid,EV_z,aprime_grid);

        % omitted
        [~,maxindex]=max(entireRHS_z,[],1);

        % Turn this into the 'midpoint'
        midpoint=max(min(maxindex,n_a-1),2); % avoid the top end (inner), and avoid the bottom end (outer)
        % midpoint is 1-by-n_a
        aprimeindexes=(midpoint+(midpoint-1)*n2short)+(-n2short-1:1:1+n2short)'; % aprime points either side of midpoint
        % aprime possibilities are n2long-by-n_a
        
        % ReturnMatrix_ii_z is [n2long,n_a]
        ReturnMatrix_ii_z=CreateReturnFnMatrix_Case1_Disc_DC1_nod_Par2(ReturnFn,special_n_z,aprime_grid(aprimeindexes),a_grid,z_val,ReturnFnParamsVec,2);
       

        entireRHS_ii_z=ReturnMatrix_ii_z+DiscountFactorParamsVec*reshape(EVinterp_z(aprimeindexes(:)),[n2long,N_a]);
   
        
        [Vtempii,maxindexL2]=max(entireRHS_ii_z,[],1);
        V(:,z_c,jj)=shiftdim(Vtempii,1);
        Policy(1,:,z_c,jj)=shiftdim(squeeze(midpoint),-1); % midpoint
        Policy(2,:,z_c,jj)=shiftdim(maxindexL2,-1); % aprimeL2ind
    end %end z

But why interpolating EV_z on the entire array aprime_grid, which is very long, when you need only a small part? You could instead do

aprime_query = aprime_grid(aprimeindexes);
EVinterp_z=interp1(a_grid,EV_z,aprime_query);
entireRHS_ii_z=ReturnMatrix_ii_z+DiscountFactorParamsVec*EVinterp_z;

The rest of the code is the same. The advantage is that you call interp1 on a shorter vector, aprime_query, and you don’t have to use the line
reshape(EVinterp_z(aprimeindexes(:)),[n2long,N_a])
which involves two reshape operations. First you reshape aprimeindexes as a column vector and then you reshape the vector EVinterp_z as a matrix. But there is no need to have EVinterp_z as a matrix.

5

I tested this modification in the example based on Fehr and Kindermann here: GitHub - aledinola/FehrKindermann_ch10_1

The original file from the toolkit is FehrKindermann_ch10_1/ValueFnIter_FHorz_GI_toolkit.m at main · aledinola/FehrKindermann_ch10_1 · GitHub
I basically copied and pasted the key function from the toolkit.

The new function is FehrKindermann_ch10_1/ValueFnIter_FHorz_GI_ale.m at main · aledinola/FehrKindermann_ch10_1 · GitHub

The speed gain is about 20-30%, so not considerable. Not sure if it is worth rewriting anything :slight_smile:

6

A small question related to the pseudo code for interpolation.

The pdf explains very nicely how to implement the VFI step with interpolation. Are other changes required to the codes besides VFI?

The agents distribution must be computed using the “lottery method”, since the policy function for next period a’, g_{a'}(a,z) does not lie on the grid for a.

What about the calculation of the model statistics?

Thanks!

1 Like
7

Modified the pdf on Grid Interpolation Layer, adding small subsection at end explaining agent dist and evaluating functions on grid.

That said, mostly it just refers you to the pseudocodes doc, which now contains a new section on iterating the agent distribution with ‘two probs’. Which covers how it is done.

‘two probs’ is used for grid interpolation, and also for experienceasset; for any setting where the optimal policy is ‘between’ grid points. This is what you refer to as the ‘lottery method’, although I describe it as ‘linear interpolation onto the grid’ (same method, just different way of thinking about what it does). [Not the cleanest explanation, but hopefully makes sense :slight_smile: ]

1 Like