Recent Progress in Coevolutionary Learning

April 3, 2008
2:50 pm - 4:00 pm
Halligan 111

Abstract

For many years my lab has been working on electronic and software systems which can learn and develop on their own in open-ended innovative ways. This is based on understanding and mimicking natural coevolution. However, in nature, coevolution refers to the contingent development between species. For machine learning, coevolution has come to mean the search for “arms-race” type phenomena which can lead multiple agents to improve through their own interaction, without the need for an explicit fitness function or an intelligent designer.

The setup is usually as a set of players to a “game” who start with only the rules and must develop strategy or tactics through interaction. Generally, this interaction is a two-level competition - first in playing a game, and second in competing for limited slots in a fixed-size population. We have had some success, for example in optimization, such as discovering the best sorting networks and cellular automata rules, as well as in five generations of the GOLEM automatically designed robots.

However, as we developed these coevolutionary systems, we found many phenomena which arise to prevent continuous innovation. It is as if the agents creatively learn to avoid learning. These phenomena are economic rather than biologic, and include winner-take-all monopolies, boom/bust cycles, and collusive oligarchies (groups of players who divide the market and protect each other from innovative invaders.)

Student in my laboratory have been on the forefront of developing new fundamental theory and algorithmic techniques for avoiding these problems, including Pareto coevolution, emergent dimensions, and memory mechanisms. We have developed a new principle to understand learning among agents - “The Teacher’s Dilemma,” which models the teacher-student relationship, and provides a new interaction framework which is neither competitive nor altruistic.

The first major practical application of Teacher's Dilemma work has been the development of scaleable peer-to-peer learning environments for children. These are multi-player online video games, but the highest scores accrue to players who provide appropriate challenges to each other, essentially turning students into each other’s teachers. We launched the first online spelling bee in 2004 and now have 60,000 members in www.Beeweb.org.

Bio. Jordan B. Pollack received the Ph.D from University of Illinois in 1987, after a career in the computer industry. He taught at Ohio State University from 1988-1994 prior to moving to Brandeis University in 1994 where he is a full professor of computer science and complex systems. He has also been involved with several startups including Abuzz and Thinmail.