Optimize ram for a DDP problem

Lectures
1

Hi guys, as many people have mentioned THANKS for the lectures (sorry for shouting).

Anyway, I’m trying to solve a problem I have using a ddp object in python. The problem is a model really close to Hugget (1993). In my model, agents decide both savings and effort, that means that my state space is huge (particularly if I have a grid of 200 states of effort and 200 of savings and employed and unemployed state I’d have 80_000_000 possible states) To store a “Q” tri-dimensional transition matrix this big I’d require something north of 10 TB of ram, so, not good. Do you happen to know any way in which I can implement both decisions without having to create such a huge matrix?

Thanks !

2

Hi @Daniel_Gomez_Salazar,

Thanks for the appreciation :-)

Yes, that’s a known problem with that routine. I think there’s a sparse option – does that help at all?

Other than that, you can change course and solve the consumer problem using these kinds of methods: https://python-intro.quantecon.org/ifp_advanced.html (check out previous lectures too).

Since the state space is not discrete, you still have the issue of how to solve for aggregate capital. But you can do this by Monte Carlo — just simulate a lot of households. I’m going to write a lecture on this soon, probably in the context of a Huggett model. If I don’t come up with the goods in the next week or two you can give me a prod. :-)

Good luck with your work.

3

Hello,

You can solve for the decision rules on a grid and then simulate a lot of households. Aggregating in this case is just a summation and you can check whether prices clear markets and if no, adjust and repeat until you get general equilibrium allocations ans prices.

A lecture on this would be extremely helpful. I am not sure how to use sparse matrices. Benjamin Moll has lectures on this (I never got around reading them). Apparently they are useful and fast.

4

@Daniel_Gomez_Salazar,
First of all, I know nothing about the problem you are trying to solve, but the general practice of optimization within computer science will tell you few things:

  • Are there ways of not doing the entire processing? Ex.: do you have intermediary states that may help you reduce the full length of the grid?
  • Divide and conquer: Try to split your operations in to smaller chunks so you can a) write to disk and spread the execution of the application over a longer period of time. or b) run in a distributed environment so you can run faster. Perhaps you should try something like https://distributed.dask.org/en/latest/

Hope that helps in some way.

5

Hi @Daniel_Gomez_Salazar:

It is an inherent limitation of DiscreteDP. As mentioned by @john.stachurski, the best you can do is to use a sparse matrix format for Q (if you have many zeros there). You might run DiscreteDP by making the grid much smaller to get a rough hint for the properties of the solution of your problem (and then code your own custom solver specialized in your problem).

You might look at the discussion at https://github.com/QuantEcon/QuantEcon.py/issues/185. Blaze may be interesting to look at (where dask mentioned above is one of the core projects).

6

Hi there, thanks for all your useful replies! I’ve been trying to solve my problem for a couple of weeks now. I finally, ended up going for a “write all my code” approach. So far it’s been very successful for finding an optimal policy. I plan to put to solution in github… not that is gonna be really elegant. Anyway, in my approach after I find the optimal policy, I plan on finding the stationary distribution. For this I simulate a bunch of agents, during a lot of years. After that I look at the distribution, and assume it should be stationary. The problem is that different runs give me slightly different distributions, and this should not be the case.

This is the simulation function:
n, is the number of states
time = number of periods that i’m simulating (its currently fixed a 10_000)

The states are employed and unemployed with a decision of how much to save for the next period(a_t), the indexing is as follows:
(a_0,employed)
(a_0,unemployed)
…
(a_n/2, unemployed)

P, its an array in which each element is the the probability of being employed the next period given the current state (it is not constant) P[0] will then be:
P(employed| a_0, employed)
and P[n-1] will be:
P(employed| a_n/2, unemployed)

Policy its a policy vector that tells the agent how much to save given his current state.
So the elements range from 0 to n/2 (the number of savings states).

Agents is an array of length n*10 in which each element represent an agent by a number that is the current state he is in.

@njit
def simulate(n, time, P, policy):
    no_agents_total = 10 * n #10 agents per state 
    agents = np.zeros(no_agents_total) #every agent starts at state 0 
    for t in range(time):
        randoms = np.random.uniform(0,1,no_agents_total) 
        for i in range(no_agents_total):
            current_state = int(agents[i])
            current_random = randoms[i]
            if current_state % 2 == 0: # The agent is employed
                if current_random > P[current_state]: 
                    current_state += 1 #she became unemployed
            else: 
                if current_random < P[current_state]: #the agent is unemployed
                    current_state -= 1 #she became employed

            agents[i] = policy[current_state]*2 + current_state % 2 #the agents go to the new state that the policy tells him but keeps his employment status. 

    return agents

#simple function to count the number of agents in each state.
def distribution(agents,n):

    distribution_a = np.zeros(n)
    for i in agents:
        current_i = int(i)
        distribution_a[current_i] +=1 
    
    return (distribution_a/len(agents))

Anyway… Do you see why it does not convege to a constant stationary state?

Sorry for the sloppy code but this is the first time im doing anything in Python!

Thanks!