BOXES: balancing a pole
In Machine Intelligence 2 (Edinburgh, 1968) Donald Michie and Roger Chambers described the program BOXES, which learns to control a cart with a pole from nothing but a state vector and a failure signal. The state space is cut into 225 boxes (5 × 5 × 3 × 3), and in each a «demon» chooses left or right from an accumulated «life» of its decisions. The algorithm was devised by Michie and turned into a Fortran II program in 1961 by Dean Wooldridge, Jr.; the tests were run on a simulation.
Why it matters
This is a forerunner of reinforcement learning on the problem that fifteen years later Barto, Sutton and Anderson took for the actor and critic (evt-0143): their paper names the problem as posed by Michie and Chambers and compares its own system with BOXES. This is an editorial assessment.
The task. A rigid pole on a cart running on a track of finite length; the motor's force is constant in size and its sign is set by a switch («bang-bang» control). In the runs reported the cart and pole were modelled by a separate part of the program, not by apparatus; the interval from sense to action is zero, from action to sense 0.05 s. The controller knows nothing of the system: at regular intervals it gets a state vector or a failure signal, after which the system is set up afresh. The design. Four state variables (position of the cart, angle of the pole, velocity of the cart, rate of change of the angle) are quantised: 5 grades of position, 5 of angle, 3 of velocity, 3 of angle-rate, that is 5 × 5 × 3 × 3 = 225 boxes. In each box a «local demon» has a switch and a scoreboard: a «left life» and a «right life» (a weighted sum of the number of decisions taken before failure) and usage; a «global demon» supplies a «target» level by the formula C0 + C1 × merit, where merit is the weighted mean life of the system. The demon picks the side with the higher optimistic value: a weighted mean of the real life and the target. Parameters: DK = 0.99, K = 20.0, C0 = 0, C1 = 1; there was no optimisation. The result (by the authors). Four runs A-D; the quality («merit») was recorded after every fiftieth control run. In run C there was a run of 1,368 decisions at a point where merit was 146; in run D a run of over 72,000 decisions (by the authors, an hour of real-time control) where merit was 4,865. Runs B and C match the best and the average of earlier versions without the target, and A is better than any earlier performance. What the record does not claim: that BOXES controlled a physical cart (in the runs read it is a simulation); that the method is optimal (the authors say no optimal policy is known for such problems); the comparison figures of Barto, Sutton and Anderson (the pages with the comparison were not read, the introduction and reference list were); the noughts-and-crosses results in the same paper, which belong to another program. This is the authors' own account; it is confirmed only in that the problem and the system are mentioned in the 1983 paper, hence the medium confidence.