What should we call non-evolutionary reinforcement learning?

I work in evolutionary reinforcement learning. That is, I develop reinforcement learning problems, and evolutionary algorithms that solve such problems.

The problem is that many people in reinforcement learning (RL) would say that I'm not working on RL at all. These people work on things like temporal difference learning, policy gradients, or (more likely) some newfangled algorithms I have never heard of, but which are most certainly not evolutionary. Most of the people working on non-evolutionary RL probably don't know much (maybe nothing!) about evolutionary RL either. So disconnected are our communities. It's a shame.

In their discipline-defining (4880 citations on Google Scholar) book "Reinforcement Learning", Sutton and Barto start with defining RL as the study of algorithms that solve RL problems, and mention in passing that they can be solved by evolutionary algorithms as well. The book then mentions nothing more about evolution, and goes on to essentially discuss TD-learning and variations thereof for a few hundred pages.

In practice, the evolutionary and non-evolutionary RL folks publish in different conferences and journals, and don't cite (nor read?) each other much. We write our papers in very different styles (the non-evolutionary RL people having much more maths in them, evolutionary RL researchers often relying on qualitative argument coupled with experimental results), and I for one often simply don't understand non-evolutionary RL papers.

Again, it's a shame. And it would be great if we could find some way of bridging this divide, as we work on the same class of problems.

But to do this, we need to find a way of addressing the issue, which was really the purpose of this blog post. Simply put, what do we call the two classes of algorithms and the research communities studying them? This is an issue I run into now and then, most recently when writing a grant proposal, and now again when preparing lecture slides for a course I'll be teaching this autumn.

The non-evolutionary RL people would not want a negative definition, based on what their algorithms aren't rather than what they are. They would rather go for RL, plain and simple, but this has the problem that non-evolutionary RL is excluded from that field, in spite of being part of the definition. In the proposal we wrote we ended up talking about "classical" versus evolutionary RL, but this has the problem that evolutionary algorithms predated td-learning by several decades. We could also use the term "single-agent RL", but then again, a simple hill-climber is arguably a (degenerate) evolutionary algorithm, and very much single-agent. Besides, there is multi-agent non-evolutionary RL. Sigh.

So I really don't know.

CIG 2008 special session on coevolution in games

Coevolution in Games: A Special Session at IEEE Symposium on Computational Intelligence and Games
Perth, Australia
15-18 December, 2008

Special Session Chairs: Julian Togelius, Alan Blair and Philip
Hingston
Contact: julian@togelius.com

Submission deadline: 15 August 2008

http://www.csse.uwa.edu.au/cig08/specialSessions.html

Description:

In coevolution, the fitness of a solution is determined not (only) by a fixed fitness function, but also by the other solution(s) being evaluated. Thus, coevolution has the potential to overcome several problems with static fitness functions, paving the way for more open-ended evolution. However, several phenomena common to coevolutionary algorithms are at present poorly understood, including cycling and loss of gradient. Further understanding of such phenomena would facilitate more widespread use of coevolutionary algorithms.

This special session seeks to bring together research that uses coevolutionary algorithms to learn to play games, uses games to investigate coevolution, or uses coevolution as a basis for game design. Due to their adversarial nature, often involving interaction of multiple agents, games are uniquely suited to be combined with
coevolution. We invite both theoretical and applied work in the intersection of coevolution and games, including but not limited to the following topics:

Competitive coevolution
Cooperative coevolution
Multiple populations in coevolution
Coevolution with diverse representations
Theory of coevolution
Preventing cycling and loss of gradient
Coevolution-based game design
Self-play and coevolutionary-like reinforcement learning
Relative versus absolute fitness metrics

About the organisers:

Julian Togelius is a researcher at the Dalle Molle Institute for Artificial Intelligence (IDSIA) in Lugano, Switzerland. His research interests include evolving game-playing agents, modelling player behaviour, and evolving interesting game content, mainly using evolutionary and coevolutionary techniques. He also co-organizes the well-attended Simulated Car Racing Competitions for the IEEE CIG and CEC conferences. See his home page for more information.

Philip Hingston is an associate professor of computer science at Edith Cowan University in Perth. His research interests are in the theory and application of artificial intelligence and computational intelligence. He has a particular interest in evolutionary computation as a tool for design, and in computer games. He is chair of the IEEE CIS Task Force on co-evolution. More information can be found on his home page.

Alan Blair is Chair of the IEEE CIS Task Force on Co-evolution and Games. His research interests include robot navigation, image and language processing as well as co-evolutionary learning for Backgammon, Tron, IPD, simulated hockey and language games. Homepage.