Eldan Goldenberg's lab notebook

Timing problems

The trip to Bloomington was very fruitful in terms of getting to meet a few people I'd previously only heard from over email, going to interesting talks, and getting feedback from my advisor. Unfortunately, the most important single thing I found out represented a substantial setback, and this is why it's taken me a while to get around to blogging about where I'm at with research.

The problem was that my advisor noticed a potentially very important mistake I had made a few months ago. Or rather—I should be more specific here—the problem is not that he noticed it, but that I hadn't noticed earlier (and it could still be much worse - at least he noticed now, and not after a paper was submitted or something).

Our simulations implement continuous-time controllers on discrete-time hardware [ordinary digital computers] by numerically approximating their behaviour. We [I use code supplied by my advisor for this part] use the Euler Method to do this, largely because it is the computationally cheapest way. The problem is that there's always a trade-off in choosing the size of integration steps: smaller steps make the simulation slower, but larger steps increase the amount of noise in the approximation. There is also a time constant for each individual unit of a CTRNN, and really it's the size of the integration steps relative to the time constants that matter. It's a fairly intuitive concept, and I discovered today that it's called the Courant-Friedrichs-Lewy Condition.

Anyway, over the past few months I've been continually tinkering with simulation parameters in an effort to get the blasted things to work reliably without taking impractical amounts of time. I thought that I had finally found some parameters that led to successful searches often enough to be useful, and while the searches were still annoyingly long (at about 5 days each) they were not so long as to be useless. However, in the course of the parameter tinkering, I had managed to set the lower bound on time constants to the same value (0.1) as the Euler integration step size; a violation of the Courant-Friedrichs-Lewy Condition which potentially allows controllers to do weird things by exploiting the integration noise. Given the generally remarkable ability of evolutionary algorithms to exploit bugs in simulators, this is a serious concern.

Since the discovery of this error, all of my research activity has been directed towards trying to understand if and how much it really matters. Thus far, I have contradictory evidence:

The case for the prosecution

1. Running a search with an integration step size of 0.1 does not yield the same results as running a search with the same parameters except for a step size of 0.01 and the relevant time periods being multiplied by 10 to compensate.
2. The searches I have run with step sizes an order of magnitude smaller than the smallest allowed time constant have so far been utterly fruitless, suggesting that exploitation of the integration noise has been necessary in some way for the searches to succeed.
3. The best agent found by searches with a step size of 0.1—which is also the one I've spent the most time analysing, for obvious reasons—has two CTRNN units with a time constant of exactly 0.1, so its behaviour is liable to be affected by integration noise. To make things worse, one of those two units is the interneuron with the most obvious role in its behaviour.

The case for the defence

4. In spite of the above, that controller's performance is barely changed—the fitness score differs only in the third decimal place—when I run it with integration step sizes even two orders of magnitude smaller. This suggests that it's not doing anything that would depend on integration noise to work.
5. The same controller's behaviour, while qualitatively somewhat different with different step sizes, is not dramatically changed. The changes in units' outputs are a little more gradual, but the agent makes almost exactly the same decisions about which food to eat and which to ignore, again suggesting that the difference doesn't matter.

Conclusion?

The jury's still out on this one. Clearly I do have a problem, if the outcome of evolutionary searches is dependent on a parameter being set outside the range it should be in. But on the other hand, if this is important then why does the best agent work just fine without that being the case? One possibilty is that there's a necessary intermediate stage in which agents do 'abuse' the integration noise; this is going to take a lot of work to find.

To do

There are three things I'm working on in order to figure out what's going on here:

1. Run more searches with appropriate step sizes - because these are even slower than those with inappropriately large integration steps, I don't have enough yet to rule out the possibility that only bad luck has stopped me from yet seeing a successful search this way.
2. Analyse more agents from the old batch, to see if I do find any that abuse the integration noise.
3. Look at many of the agents that were saved during the search that found the best agent so far, to see if the search arrived at that good agent via abuse of integration noise.