forward/backward through data access, not data storage

[sbenthall]

In light of the goal of disentangling solution and simulation #495 ...
by pulling out a separate Policy class #481 ...
which would be documented #482 ...

A core part of the model logic is going to need to change.

Currently, variation over time is represented as Python lists.
Depending on whether the model is being used to 'solve' (backwards) or 'simulate' (forwards), these lists are reverse()d.

https://github.com/econ-ark/HARK/blob/master/HARK/core.py#L248

In the current design, the way the data is being stored in memory is being used to determine which functionality of the model is "active".

This design makes it very difficult to make the solution/policy portable between model instances.
It also introduces an unnecessary O(n) reverse operation.

Instead of doing it this way, the representation of the time-varying attributes should stay stable in memory.
Backwards operations should traverse this data backwards, rather than reversing the data then traversing it forwards.

[mnwhite]

The good news is that the O(n) reversing operation is done only rarely, and never actually moves that much stuff in memory. But I strongly agree with your point here. This was basically the very first design disagreement we had on HARK: Chris wanted time-varying lists to always run backward in time, I wanted them to always run forward in time. I put in the timeFlip stuff as a compromise: they would run backward when solving but forward when simulating (or basically any other time). The reason I'd like time-varying parameters to run from beginning of time to end of time is that *that's how we refer to them on paper*, e.g. we write c_t(m_t) to refer to the t-th period's consumption function. Somewhere between 99 and 100% of the time that any user will interact with an AgentType in HARK, they want model results: something from the solution or simulation output. The *only* time that anyone ever wants these variables phrased backward is during solution... and the time loop stuff is handled internally by HARK! We are very capable of programming solve and solveOneCycle to get the correct inputs even if the lists run forward in time.

…

On Sun, Mar 15, 2020 at 11:26 AM Sebastian Benthall < ***@***.***> wrote: In light of the goal of disentangling solution and simulation #495 <#495> ... by pulling out a separate Policy class #481 <#481> ... which would be documented #482 <#482> ... A core part of the model logic is going to need to change. Currently, variation over time is represented as Python lists. Depending on whether the model is being used to 'solve' (backwards) or 'simulate' (forwards), these lists are reverse()d. https://github.com/econ-ark/HARK/blob/master/HARK/core.py#L248 In the current design, the way the data is being stored in memory is being used to determine which functionality of the model is "active". This design makes it very difficult to make the solution/policy portable between model instances. It also introduces an unnecessary O(n) reverse operation. Instead of doing it this way, the representation of the time-varying attributes should stay stable in memory. Backwards operations should traverse this data backwards, rather than reversing the data then traversing it forwards. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#569>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ADKRAFKNNLF7GK4H6WOJ45LRHTXQVANCNFSM4LLCYW6Q> .

[sbenthall]

@mnwhite we are in total agreement here.
I'm working on a PR that removes the backwards time representation issue.

@llorracc I'm curious what you were thinking here and if you would reconsider your earlier position in light of what @mnwhite have argued here.

[llorracc]

As Matt mentions, he and I discussed this at some length early on.

The issue doesn't really arise in infinite horizon models. But, for finite horizon models, like a life cycle, the deep intrinsic logic that everyone learns when they are first introduced to these kinds of models is "backwards induction": You start from the terminal period T-0, then solve for period T-1, T-2, to the first period of life (say, 60 years before death at 85). My view was that so long as the code and data structures are labeled clearly, it will not be hard to understand that you are counting backwards.

• Once the solution has been obtained by backward iteration for every period, it seems natural for the simulation just to crawl back up, starting at the 'last' period solved (say, 65) until the terminal period 0 is reached
• One way to handle this reasonably transparently is to be careful about the names of the variables used to keep track of where you are. When I did this in my Mathematica code years ago, that's how I handled it, I think using variables with long names like PeriodsBackFromEndOfLife and LastPeriodOfLife and FirstPeriodOfLife so that one could iterate from LastPeriodOfLife-PeriodsBackFromEndOfLife while solving and from FirstPeriodOfLife to PeriodsSinceFirstPeriodOfLife and the latter variable could be incremented from 0 to 65 as long as the age index was something like FirstPeriodOfLife-PeriodsSinceFirstPeriodOfLife.

This all makes a good bit of sense when the backward solution and the forward simulation are intrinsic attributes of the same object.

I think Matt's point of view was that, if you hand a generic simulation routine a sequence of decision rules, what the simulator will likely expect is that it should start at period 0 and simulate forward in time to the last period, which is the opposite of what it should do (for a finite horizon model).

Matt's case perhaps becomes stronger if we move to an approach where there is a generic MDP simulator that is fed a generic decision rule and stochastic process and asked to simulate it.

An important question to think about as we move in that direction is whether the right approach is to have a simulator that just simulates one period at a time and we expect the user to feed it a sequence of rules one by one, in which case it is up to the user to feed the simulator the rules in the right order, or whether we want to be able to feed the simulator an entire sequence of decision rules and have it do all of them together and then return a result. If there were no considerations of efficiency, I'd vote for the former approach, but it could be that such an approach would be highly inefficient and slow because there would be so many objects being passed back and forth between the one-step simulator and the code that was using it to produce a sequence of periods.

[sbenthall]

Thanks for this explanation. That is helpful.

I think what should happen is that the backwards induction solvers should be reimplemented so that they operate without assuming that the underlying data structures have been written or reversed into "backwards format".

In principle, that is straightforward enough: there's no reason why an algorithm can't iterate 'backwards' over data.

In practice, it means understanding better the assumptions made in the rather complex solution code of HARK.

I see that one place to start is this solveAgent() function, which at the time of this writing I have revised incompletely.

HARK/HARK/core.py

Lines 757 to 839 in b1b14ad

	def solveAgent(agent, verbose):
	'''
	Solve the dynamic model for one agent type. This function iterates on "cycles"
	of an agent's model either a given number of times or until solution convergence
	if an infinite horizon model is used (with agent.cycles = 0).
	Parameters
	----------
	agent : AgentType
	The microeconomic AgentType whose dynamic problem is to be solved.
	verbose : boolean
	If True, solution progress is printed to screen (when cycles != 1).
	Returns
	-------
	solution : [Solution]
	A list of solutions to the one period problems that the agent will
	encounter in his "lifetime". Returns in reverse chronological order.
	'''
	# Record the flow of time when the Agent began the process, and make sure time is flowing backwards
	original_time_flow = agent.time_flow
	agent.timeRev()
	# Check to see whether this is an (in)finite horizon problem
	cycles_left = agent.cycles # NOQA
	infinite_horizon = cycles_left == 0 # NOQA
	# Initialize the solution, which includes the terminal solution if it's not a pseudo-terminal period
	solution = []
	if not agent.pseudo_terminal:
	solution.append(deepcopy(agent.solution_terminal))
	# Initialize the process, then loop over cycles
	solution_last = agent.solution_terminal # NOQA
	go = True # NOQA
	completed_cycles = 0 # NOQA
	max_cycles = 5000 # NOQA - escape clause
	if verbose:
	t_last = time()
	while go:
	# Solve a cycle of the model, recording it if horizon is finite
	solution_cycle = solveOneCycle(agent, solution_last)
	if not infinite_horizon:
	solution += solution_cycle
	# Check for termination: identical solutions across cycle iterations or run out of cycles
	solution_now = solution_cycle[-1]
	if infinite_horizon:
	if completed_cycles > 0:
	solution_distance = solution_now.distance(solution_last)
	agent.solution_distance = solution_distance # Add these attributes so users can
	agent.completed_cycles = completed_cycles # query them to see if solution is ready
	go = (solution_distance > agent.tolerance and completed_cycles < max_cycles)
	else: # Assume solution does not converge after only one cycle
	solution_distance = 100.0
	go = True
	else:
	cycles_left += -1
	go = cycles_left > 0
	# Update the "last period solution"
	solution_last = solution_now
	completed_cycles += 1
	# Display progress if requested
	if verbose:
	t_now = time()
	if infinite_horizon:
	print('Finished cycle #' + str(completed_cycles) + ' in ' + str(t_now-t_last) +
	' seconds, solution distance = ' + str(solution_distance))
	else:
	print('Finished cycle #' + str(completed_cycles) + ' of ' + str(agent.cycles) +
	' in ' + str(t_now-t_last) + ' seconds.')
	t_last = t_now
	# Record the last cycle if horizon is infinite (solution is still empty!)
	if infinite_horizon:
	solution = solution_cycle # PseudoTerminal=False impossible for infinite horizon
	# Restore the direction of time to its original orientation, then return the solution
	if original_time_flow:
	agent.timeFwd()
	return solution

I wonder if I will need to fix just that method, or if every solver has been written in a way that assumes that, at the time it is executed, time_flow == False.

[sbenthall]

Regarding your point about simulators and decision rules, I've made a separate issue for that: #571

[mnwhite]

None of the model solvers "assume" the data is oriented backward. All of the functions that are given to AgentType subclasses for their solveOnePeriod attribute are completely foxholed in their perspective of the world. They know *only* about this one period problem, which includes some concept of "next period's solution" in the argument solution_next. All of handling of what arguments should be passed to the function in each period is handled by HARK.core.AgentType's top-level solve method. It's quite easy to remove all of the timeFlip stuff. In response to Chris: Yes, students are taught early on that problems are solved by backward induction, but that doesn't mean that they want or need the description of a lifecycle problem to be laid out backward. People understand that iterating from T to T-1 to T-2 to T-3, etc means you're going backward through sets of information. Even an absolute newcomer will be able to understand when told that the problem is solved by backward induction, so we work with the last things first. But more broadly, we should not make decisions about the core structure of the code in order to cater to the absolute least capable person who might ever use it. Moreover, this isn't a part of the code that a new user will *ever* interact with. As I said above, users (and new users in particular) interact with HARK objects from the perspective of looking at model output, or *maybe* describing a lifecycle structure with its parameters. When they do the former, they want time to flow forward: index t+1 > t means that t+1 happens after t. When they do the latter, essentially *everyone* writes down lifecycle parameters from beginning to end. They copy-paste an actuarial table from the SSA, or they snag a sequence of permanent income growth rates from a paper. If someone runs a single line of code like plt.plot(np.cumprod(MyType.PermGroFac)), they should see what they expect: a plot of cumulative permanent income growth since the start of the model. You say we just need to use clear labeling, but those variable names are insanely long, and make the code *very* hard to read. People can understand what indexing by t means.

…

On Sun, Mar 15, 2020 at 8:00 PM Sebastian Benthall ***@***.***> wrote: Thanks for this explanation. That is helpful. I think what should happen is that the backwards induction solvers should be reimplemented so that they operate without assuming that the underlying data structures have been written or reversed into "backwards format". In principle, that is straightforward enough: there's no reason why an algorithm can't iterate 'backwards' over data. In practice, it means understanding better the assumptions made in the rather complex solution code of HARK. I see that one place to start is this solveAgent() function, which at the time of this writing I have revised incompletely. https://github.com/econ-ark/HARK/blob/b1b14ad1539495e11d483f54bedf5f569d3885ce/HARK/core.py#L757-L839 I wonder if I will need to fix just that method, or if *every* solver has been written in a way that assumes that, at the time it is executed, time_flow == False. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#569 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ADKRAFLBLILVTJIREJCNM4TRHVT3VANCNFSM4LLCYW6Q> .

[llorracc]

I don't agree that long variable names make things hard to read; on the contrary, one of the criticisms we got from our consultants early (Sumana etc) was that we OUGHT to be using long and highly descriptive variable names. I'm not proposing that we actually use such long names, but we could use ones that are shorter and still fairly descriptive.

[llorracc]

@sbenthall, a few times you have said things that suggest that you think the only thing we need to keep track of is the decision rule or policy function. That might be true if we were just solving an MDP. But for Bellman problems you often (usually) want to keep track of the value function vFunc, the marginal value function vPFunc, maybe even the marginal marginal value function vPPFunc and perhaps some other things. Matt's code lets you specify which of those things you want to keep. So, any solver will need to be able to take all of those (and, generically, basically anything that gets constructed at any stage of the solution) as inputs and produce them as outputs.

[sbenthall]

In this issue and the related PR, the only thing I'm trying to change is:

• removing timeFlip and anything that depends on it
• that means having the backwards induction solver not write a 'chronologically reversed' solution

This is not a high-concept thing; it's an implementation detail.

It sounds like based on @mnwhite this should be a simple fix.

It might be useful to tell you in this context that if you want to add an item x to the beginning of a list, foo, you can use foo.insert(0,x).

Some bugs in my current implementation are blocking the PR currently.

[mnwhite]

I just had my first Mandela effect moment. I was about to mention that `foo.prepend(x)` is easier, only to realize that `prepend` does not exist. But I swear it did yesterday!

…

On Mon, Mar 16, 2020 at 11:58 AM Sebastian Benthall < ***@***.***> wrote: In this issue and the related PR, the only thing I'm trying to change is: - removing timeFlip and anything that depends on it - that means having the backwards induction solver not write a 'chronologically reversed' solution This is not a high-concept thing; it's an implementation detail. It sounds like based on @mnwhite <https://github.com/mnwhite> this should be a simple fix. It might be useful to tell you in this context that if you want to add an item x to the beginning of a list, foo, you can use foo.insert(0,x). Some bugs in my current implementation are blocking the PR currently. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#569 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ADKRAFLDBROLH3LSNPWFKCDRHZEBPANCNFSM4LLCYW6Q> .

[sbenthall]

a few times you have said things that suggest that you think the only thing we need to keep track of is the decision rule or policy function.

To clarify, I don't think this, in the context of the backwards induction solvers. I agree with what you say here.