depth first search

In response to a recent Coding Horror piece on Spartan programming I’d like to humbly submit two examples from my own recent work.

First, in C++ we have:

for (int i = 0; i < nstates; i++) {
    for (int a = 0; a < nactions; a++) {
        Q[i][a] += alpha * delta * e[i][a];
        e[i][a] *= gamma * lambda;
    }
}

Next, in Python with Numpy:

self.Q += self.alpha * delta * self.e
self.e *= self.gamma * self.ld

These are identical temporal difference updates in two versions of a Sarsa reinforcement learning agent. Having reasonable syntax and semantics for vector and matrix operations is essential for sparse programming in any kind of numerically intensive setting.

We’ve had some interesting discussion recently on the future goals of reinforcement learning. Penetration into industry seems to be a hot topic within the community, with the consensus being that reinforcement learning is currently too difficult to apply to problems without expertise. A related issue is that RL has no standard tookit, unlike machine learning, which now has Weka among others.

Then, of course, there is the search for the killer app, a reinforcement learning application that demonstrably revolutionizes an industry. The killer app must of course be preceded by a killer problem. Allow me to humbly submit one such potential area of application: Revenue Management.

I am most familiar with airline revenue management, the method by which airlines choose prices for the seats they sell. Most of the interesting dynamics of airline revenue management policies come from two key properties.

1. Customer behavior is difficult to predict.
2. An empty seat is perishable.

Modern airlines have next to no capital. Everything from the terminal, offices, runways, baggage carts, and planes is rented or leased. What airlines are is an orchestration of the revenue that flows through the organization of these combined resources, revenue that starts in your wallet.

The optimization problem is to pick prices for seats that maximize profit. Airlines have a number of nifty tricks to do this, like observing that certain kinds of travelers (business travelers with expense budgets) book late whereas recreational flyers book early. This allows for price discrimination.

Of course this optimization problem has a natural reward signal – profit, a reasonably tractable set of actions (setting prices) and a nice random state transition (customers purchase seats). Enter reinforcement learning.

UPDATE: A quick search of Google scholar shows that some work has already been done in this area: link. link. It’s nice to know that I’m on the curve, even if I’m behind on it.

A New Approach to Manipulator control: The Cerebellar Model Articulation Controller by J.S Albus (1975)

It is an old but good paper on a novel perceptron architecture that is widely used for reinforcement learning these days. I’ve created a bare-bones implementation in Python for those who are interested. You’ll need numpy and matplotlib.

Here’s a sin curve we all know and love:

And here’s the CMACs training error over time:

And finally a picture of the function that the CMAC outputs after training:

It turns out that optimizing warehouse tasks is hard.

As I near completion on my final project for a course on reinforcement learning, I came across the following from Sutton’s page on tile coding:

With the code described so far, there is a small probability that unrelated inputs will hash into some of the same tiles. In a group of tilings, usually there will be no more than one such “collision”, so that it is not a big problem; the learning process will sort it out. There will not be a big effect on performance unless the memory is too small or the hash functions are poorly designed. Nevertheless, the possibility of such a problem is annoying. When one’s program doesn’t work, there is a tendency, deserved or not, to suspect a failure of the hashing function.

I did, in fact, discover that my memory size was too small, resulting in a number of collisions. That was not the only problem with my agent, but one of many.

Of recent related significance, the UTCS/ART autonomous vehicle team did not make the finals in the Urban Challenge. One of the technical problems the team faced was a bad Ethernet cable that delayed critical sensor readings by as much as five seconds. The thread here is that debugging (in the classic sense as a programmer art) does not apply easily to systems that exhibit degrees of homeostasis or non-determinism (e.g. Ethernet protocol, TD-learning).