Soluciones emergentes para alta dimensión
Aprendizaje por refuerzo multitarea

Esteban Kelly
Departamento de Ciencias de la Computación, Universidad de Dalhousie, 6050 Avenida Universidad,
halifax, NS, B3H 4R2, Canada

skelly@cs.dal.ca

malcolm yo. heywood
Departamento de Ciencias de la Computación, Universidad de Dalhousie, 6050 Avenida Universidad,
halifax, NS, B3H 4R2, Canada

mheywood@cs.dal.ca

doi:10.1162/EVCO_a_00232

Abstracto

Algoritmos que aprenden a través de la interacción ambiental y recompensas retrasadas, o volver-
aprendizaje por refuerzo (rl), enfrentan cada vez más el desafío de escalar a la dinámica, alto-
dimensional, y entornos parcialmente observables. Se está prestando mucha atención
a marcos de aprendizaje profundo, que escalan a datos de alta dimensión mediante descomposiciones-
Realizar la tarea a través de redes neuronales multicapa.. Si bien es efectivo, la representación
es complejo y computacionalmente exigente. En este trabajo, proponemos un marco
basado en una programación genética que complejiza adaptativamente las políticas a través de-
acción con la tarea. Hacemos una comparación directa con varios refuerzos profundos.
marcos de aprendizaje en el desafiante entorno de videojuegos Atari, así como más
Marcos tradicionales de aprendizaje por refuerzo basados ​​en características diseñadas a priori..
Los resultados indican que el enfoque propuesto coincide con la calidad del aprendizaje profundo mientras
siendo un mínimo de tres órdenes de magnitud más simple con respecto al modelo com-
plejidad. Esto da como resultado la operación en tiempo real del agente campeón de RL sin recursos.
al soporte de hardware especializado. Además, el enfoque es capaz de desarrollar soluciones-
ciones a múltiples títulos de juegos simultáneamente sin costo computacional adicional. En
este caso, comportamientos de los agentes para un juego individual, así como agentes individuales capaces de
jugar todos los juegos surgen de la misma carrera evolutiva.

Palabras clave

Modularidad emergente, coevolución cooperativa, programación genética, reforzamiento
aprendiendo, aprendizaje multitarea.

1

Introducción

Aprendizaje reforzado (rl) Es un área del aprendizaje automático en la que un agente desarrolla una
Política de toma de decisiones a través de la interacción directa con un entorno de tareas.. Específicamente,
El agente observa el entorno y sugiere una acción basada en la observación.,
repetir el proceso hasta que se encuentre un estado final de tarea. El estado final proporciona una
señal de recompensa que caracteriza la calidad de la póliza, o el grado de éxito/fracaso.
Por lo tanto, el objetivo de la política es seleccionar acciones que maximicen esta recompensa a largo plazo..
En aplicaciones del mundo real de RL, Es probable que el agente observe el entorno.
a través de una interfaz sensorial de alta dimensión (p.ej., una cámara de vídeo). Esto potencialmente
implica que: (1) Los agentes de RL deben poder evaluar grandes cantidades de información de “bajo nivel”.-
formación; (2) A menudo no se dispone de información completa sobre el medio ambiente.

Manuscrito recibido: 11 Julio 2017; revisado: 22 Puede 2018 y 1 Junio 2018; aceptado: 6 Junio 2018.
© 2018 Instituto de Tecnología de Massachusetts.
Publicado bajo Creative Commons
Atribución 4.0 no portado (CC POR 4.0) licencia.

Computación evolutiva 26(3): 347–380

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

/

/

mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d

yo

F
/

/

/

/

2
6
3
3
4
7
1
5
5
2
3
7
5
mi
v
C
oh
_
a
_
0
0
2
3
2
pag
d

.

/

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

S. kelly y m. I. heywood

una sola observación; y (3) Las interacciones prolongadas y las recompensas escasas son comunes.,
Requerir que el agente tome miles de decisiones antes de recibir suficiente retroalimentación.
evaluar la calidad de la política. dicho eso, Las aplicaciones potenciales para RL son enormes.
y diverso, de la robótica autónoma (Kober y Peters, 2012) a los videojuegos (Tamiz,
2012), motivando así la investigación sobre marcos de RL que sean lo suficientemente generales como para ser aplicables.-
Se aplica a una variedad de entornos sin el uso de características específicas de la aplicación..

Abordar la dinámica, de alta dimensión, y las tareas parcialmente observables en RL tienen
Recientemente ha recibido mucha atención debido a: (1) la disponibilidad de un conveniente
Emulador de videojuegos que admite cientos de títulos., como Arcade Learning Envi-
ambiente (PERO) (Bellamare, Naddaf et al., 2012); y, (2) resultados humanos competitivos de
aprendizaje profundo (p.ej., Mnih et al., 2015). ALE define el estado, (cid:2)s(t ), en términos de pantalla directa
captura, mientras que las acciones se limitan a las de la consola Atari original. De este modo, aprender-
Los agentes interactivos interactúan con los juegos a través de la misma interfaz que experimentan los jugadores humanos..
En muestreo 49 títulos de juegos, cada uno diseñado para ser interesante y desafiante para los humanos
jugadores, Se identifican entornos de tareas con una amplia gama de propiedades.. Tal como, cada
El título del juego requiere una política de RL distinta que sea capaz de maximizar la puntuación a lo largo del tiempo.
curso del juego.

En este trabajo, Introducimos una programación genética. (médico de cabecera) marco que especifica-
aborda fácilmente los desafíos en la ampliación de RL a tareas del mundo real manteniendo un mínimo
complejidad del modelo. El algoritmo utiliza modularidad emergente. (Nolfi, 1997) a adaptativamente
Complejizar las políticas a través de la interacción con el entorno de la tarea.. Un equipo de programas
representa el módulo de comportamiento básico (Lichodzijewski y Heywood, 2008b), o un
mapeo de la observación del estado a una acción. En tareas secuenciales de toma de decisiones, cada
El programa dentro de un equipo define un comportamiento de oferta único. (Sección 3.2), tal que pro-
Los gramos seleccionan cooperativamente una acción del equipo en relación con el estado actual del observador.-
variación en cada paso de tiempo.

La evolución comienza con una población de equipos simples., Figura 1a, que luego son pieles-
luego desarrollado agregando, eliminando, y modificar programas individuales. este trabajo
extiende versiones anteriores de una versión anterior (simbiótico) enfoque para el equipo de GP (Lichodz-
ijewski y heywood, 2011; Doucette y cols., 2012; Kelly y col., 2012; kelly y oye-
madera, 2014b, 2014a) para permitir una modularidad conductual emergente a partir de un único ciclo de
evolución mediante la recombinación adaptativa de múltiples equipos en equipos dirigidos de forma variable y profunda.
estructuras graficas, o gráficos de programas enredados (TPG)1 (Figura 1b). El comportamiento de cada uno.
programa, complemento de programas por equipo, complemento de equipos por gráfico, y el
La conectividad dentro de cada gráfico son propiedades emergentes de una evolución abierta.-
proceso ario. Los beneficios de este enfoque son dobles.:

1. Un único gráfico de equipos, o gráfico de políticas, eventualmente puede evolucionar para incluir hun-
cientos de equipos, donde cada uno representa un simple, comportamiento especializado (Cifra
1b). Sin embargo, mapear una observación de estado a una acción requiere atravesar solo
un camino a través del gráfico desde la raíz (equipo) hojear (acción). De este modo, el representante-
La presentación es capaz de compartimentar muchos comportamientos y recordar sólo
aquellos relevantes para las condiciones ambientales actuales. Esto permite que TPG escale
a complejo, entornos de tareas de alta dimensión manteniendo un nivel relativamente
Bajo coste computacional por decisión..

2. Los programas de cada equipo indexarán colectivamente una pequeña, subconjunto único de la
espacio de estados. A medida que surgen gráficos de políticas de varios equipos, sólo regiones específicas del estado

1El código fuente está disponible en https://web.cs.dal.ca/∼mheywood/Code/index.html

348

Volumen de cálculo evolutivo 26, Número 3

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

/

/

mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d

yo

F
/

/

/

/

2
6
3
3
4
7
1
5
5
2
3
7
5
mi
v
C
oh
_
a
_
0
0
2
3
2
pag
d

/

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Aprendizaje por refuerzo emergente multitarea de alta dimensión

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

/

/

mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d

yo

F
/

/

/

/

2
6
3
3
4
7
1
5
5
2
3
7
5
mi
v
C
oh
_
a
_
0
0
2
3
2
pag
d

/

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Cifra 1: Políticas de GTP. Toma de decisiones en cada paso del tiempo. (marco) comienza en la raíz
equipo (nodo negro) y sigue la ventaja con la oferta del programa ganador (producción) hasta un
acción atómica (Posición del joystick Atari) se alcanza. La población inicial contiene sólo
políticas de un solo equipo (a). Los gráficos multiequipo surgen a medida que avanza la evolución. (b).

Los espacios que son importantes para la toma de decisiones serán indexados por el gráfico como un
entero. De este modo, La modularidad emergente permite que la política se descomponga simultáneamente.-
Plantear la tarea espacial y conductualmente., detectando regiones importantes del estado
espacio y optimizar las decisiones tomadas en diferentes regiones. Esto minimiza
el requisito de características específicas de la tarea de elaboración a priori, y deja que TGP realice
tanto la construcción de características como el descubrimiento de políticas simultáneamente.

A diferencia del aprendizaje profundo, El marco TPG propuesto adopta una perspectiva explícitamente emergente.,
enfoque de desarrollo para la identificación de políticas. Nuestro interés es si podemos con-
estructurar topologías de gráficos de políticas “de abajo hacia arriba” que coincidan con la calidad del aprendizaje profundo para que-
luciones sin la correspondiente complejidad. Específicamente, El aprendizaje profundo supone que
La arquitectura neuronal está diseñada a priori., con la misma arquitectura empleada para
cada título de juego. De este modo, El aprendizaje profundo siempre realiza millones de cálculos por deci.-
sión. TPG, por otro lado, tiene el potencial de ajustar la complejidad de las políticas a cada tarea

Volumen de cálculo evolutivo 26, Número 3

349

S. kelly y m. I. heywood

ambiente, o título del juego, requiriendo solo ≈ 1000 cálculos por decisión en la mayoría
caso complejo, y ≈ 100 cálculos en los casos más simples.

En breve, El objetivo de este trabajo es demostrar que soluciones mucho más simples pueden
ser descubierto a la dinámica, de alta dimensión, y ambientes parcialmente observables en
RL sin tomar decisiones previas sobre la complejidad del modelo.. Como consecuencia,
los costos computacionales típicamente asociados con el aprendizaje profundo se evitan sin im-
Pactar sobre la calidad de las políticas resultantes., eso es, El costo de la capacitación y el despliegue.
una solución ahora es mucho menor. Las soluciones funcionan en tiempo real sin recurrir a
plataformas de hardware multinúcleo o GPU, simplificando así potencialmente el desarrollo-
gastos generales de cuenta/despliegue al plantear soluciones a tareas desafiantes de RL.

En relación con nuestro trabajo anterior, nosotros: (1) ampliar la comparación de título único de 20 títulos
con dos algoritmos comparadores (kelly y heywood, 2017a) para incluir todos 49 Atari
títulos de juegos y ocho algoritmos comparadores (Sección 5); y (2) demostrar que mul-
El rendimiento de la tarea se puede ampliar desde 3 al menos 5 títulos de juegos por política y, a diferencia de
el trabajo anterior, no requiere una formulación objetiva de Pareto (kelly y oye-
madera, 2017a), solo elitismo (Sección 7).

2 Fondo

2.1

Entorno de tareas

El entorno de aprendizaje arcade (PERO) (Bellamare, Naddaf et al., 2012) es un atari
2600 Emulador de videojuegos diseñado específicamente para comparar algoritmos RL. El ALE
permite a los agentes de RL interactuar con cientos de videojuegos clásicos usando los mismos en-
Interfaz experimentada por jugadores humanos.. Eso es, un agente de RL se limita a interactuar
con el juego usando el estado, (cid:2)s(t ), como lo define la pantalla del juego, y 18 discreto (atómico)
comportamiento, eso es, el conjunto de instrucciones de paletas de la consola Atari que incluyen "sin acción," en com-
combinación con/sin botón de disparo. Cada pantalla de juego está definida por un 210 × 160 píxel
matriz con 128 colores potenciales por píxel, actualizado a una velocidad de fotogramas de 60 Hz. en la práctica-
tice, Los marcos de pantalla sin procesar se preprocesan antes de ser presentados a un agente de RL.
(mira la sección 2.2 para un resumen de los enfoques adoptados hasta la fecha, y Sección 4.1 para el
enfoque específico asumido en este trabajo).

Curiosamente, Las entidades importantes del juego a menudo aparecen de forma intermitente en secuencias.
marcos, creando un parpadeo visible en la pantalla. Esta es una técnica común que utilizan los diseñadores de juegos.
para solucionar las limitaciones de memoria en el hardware original de Atari. Sin embargo, se presenta
un desafío para RL porque implica que los entornos de juego de Atari son parcialmente observados.-
capaz. Es decir, un solo cuadro rara vez representa el estado completo del juego.

Además, los agentes se saltan estocásticamente los fotogramas de la pantalla con una probabilidad p = 0.25, con
la acción anterior se repite en fotogramas omitidos (Bellamare, Naddaf et al., 2012;
Hausknecht y la piedra, 2015). Esta es una configuración predeterminada en ALE, y tiene como objetivo limitar
agentes a aproximadamente el mismo tiempo de reacción que un jugador humano, además de introducir un
fuente adicional de estocasticidad. Un solo episodio de juego dura un máximo de 18,000
marcos, sin incluir fotogramas omitidos.

2.2 RL bajo Tareas ALE

Históricamente, Los enfoques de RL se han basado en representantes estatales específicos de tareas diseñadas a priori.-
resentaciones (atributos). Esto cambió con la introducción de Deep Q-Network.
(DQN) (Mnih et al., 2015). DQN emplea un archivo de red neuronal convolucional profunda-
Tecnología para codificar una representación directamente desde la captura de pantalla. (por lo tanto, un representante de tarea específica-
resentimiento). A partir de esta representación se entrena simultáneamente un perceptrón multicapa.

350

Volumen de cálculo evolutivo 26, Número 3

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

/

/

mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d

yo

F
/

/

/

/

2
6
3
3
4
7
1
5
5
2
3
7
5
mi
v
C
oh
_
a
_
0
0
2
3
2
pag
d

/

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Aprendizaje por refuerzo emergente multitarea de alta dimensión

estimar una función de valor (el selector de acciones) a través del Q-learning. Preproceso de imagen-
Todavía era necesario y tomó la forma de muestreo descendente del original. 210 × 160 RGB
datos del marco a 84 × 84 y extrayendo el canal de luminancia. Además, un deslizamiento temporal-
Se asumió una ventana de configuración en la que la entrada a la primera capa de convolución era en realidad
una secuencia de los cuatro fotogramas que aparecen más recientemente. Esto redujo la observación parcial-
capacidad de la tarea, ya que todo el estado del juego ahora debería ser visible.

Al asumir Q-learning, DQN es un método fuera de política, por cual uno de los más
Los elementos críticos son el soporte para la memoria de repetición.. Tal como, el rendimiento podría verse afectado-
sitivo al contenido específico de esta memoria (los “recuerdos” que se reproducen son aleatorios
muestreado). La arquitectura general del aprendizaje por refuerzo (Gorila) extendió la aplicación-
Enfoque de DQN con una infraestructura distribuida masivamente paralela. (100s de GPU) a
Apoyar el desarrollo simultáneo de múltiples estudiantes de DQN. (Nair et al., 2015).
Las contribuciones de los estudiantes distribuidos actualizan periódicamente un “parámetro” central.-
ter server” que en última instancia representa la solución. Gorila tuvo un mejor desempeño que DQN
en la mayoría de los títulos de juegos, pero no en todos los casos, lo que indica que posiblemente todavía haya sensibilidad-
idades para reproducir el contenido de la memoria.

También se sabe que el Q-learning puede dar como resultado valores de acción que son excesivamente
alto. Recientemente se demostró que tales “sobreestimaciones” estaban asociadas con imprecisiones en
los valores de acción, donde es probable que esto sea la norma durante las etapas iniciales de la formación
(van Hasselt et al., 2016). La solución propuesta por van Hasselt et al.. (2016) para dirección-
Para solucionar este problema se introdujeron dos conjuntos de pesos., uno para la selección de acciones y otro para
evaluación de políticas. Esto fue diseñado en la arquitectura DQN asociando el
dos roles con la red en línea de DQN y la red de destino respectivamente.2 El resultado
El marco de doble DQN mejoró los resultados de DQN originales durante más de la mitad de los casos.
el 49 títulos de juegos de la tarea ALE.

Más recientemente, métodos de política (p.ej., vendaje) han aparecido en los que múltiples en-
Las políticas dependientes se entrenan en paralelo. (Mnih et al., 2016). La experiencia de cada agente de
el entorno es totalmente independiente (No se hace ningún intento de hacer cumplir la centralización.-
ción de memoria/experiencia). Esto significa que el conjunto de agentes de RL experimenta colectivamente-
ence una gama más amplia de estados. La evaluación resultante bajo la tarea Atari demostró
reducciones significativas de los requisitos computacionales3 y mejores estrategias de agentes. Eso
dicho, en todos los casos, La arquitectura de aprendizaje profundo se especifica a priori y está sujeta a controles previos.
ajuste de parámetros en un subconjunto de títulos de juegos.

La neuroevolución representa una de las técnicas más investigadas dentro
El contexto del descubrimiento de agentes para juegos.. Hausknecht y otros. (2014) realizó una com-
comparación de diferentes marcos neuroevolutivos bajo dos representaciones estatales:
Objetos específicos del título del juego versus captura de pantalla.. El preprocesamiento para la captura de pantalla tomó
la forma de muestreo del original 210 × 160 Datos de cuadro RGB para producir ocho
“sustratos” de dimensión 16 × 21 = 336; cada sustrato correspondiente a uno de los
ocho colores presentes en una representación SECAM (proporcionada por la ALE). si el color
está presente en los datos del marco original, aparece en un nodo de sustrato correspondiente.
Hausknecht y otros. (2014) comparado Hyper-NEAT, LIMPIO, y dos esquemas más simples para
Redes neuronales en evolución bajo el conjunto de títulos de juegos de Atari.. Hyper-NEAT proporciona
un enfoque de desarrollo para describir grandes arquitecturas de redes neuronales de manera eficiente,
mientras que NEAT proporciona un esquema para descubrir topologías neuronales arbitrarias, así como

2La red “en línea” en DQN mantiene la copia maestra del MLP, mientras que la red objetivo

se actualiza durante la “repetición de la experiencia” (Mnih et al., 2015).

3Una CPU de 16 núcleos en lugar de una GPU.

Volumen de cálculo evolutivo 26, Número 3

351

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

/

/

mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d

yo

F
/

/

/

/

2
6
3
3
4
7
1
5
5
2
3
7
5
mi
v
C
oh
_
a
_
0
0
2
3
2
pag
d

/

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

S. kelly y m. I. heywood

valores de peso, comenzando con una sola neurona completamente conectada. NEAT fue más efectivo-
fectivo bajo la representación de objetos de baja dimensión, mientras que Hyper-NEAT era
preferible para la representación del sustrato.

Finalmente, Liang et al.. (2016) revisar el diseño de información de estado específica de la tarea utilizando
una hipótesis sobre la acción de la neurona convolucional en el aprendizaje profundo. Esta re-
resultado en un espacio de estados en el orden de 110 millones de atributos cuando se aplican a la pantalla de Atari
captura, pero toma de decisiones simplificada a un modelo lineal. De este modo, un agente de RL podría ser
identificado utilizando el método de Diferencia Temporal sobre póliza de Sarsa. En comparación con
aprendizaje profundo, Los requisitos computacionales para el entrenamiento y el despliegue están limitados.-
considerablemente más bajo, pero los modelos producidos son tan buenos como la capacidad de diseñar
atributos apropiados.

2.3 RL multitarea bajo ALE

Los enfoques revisados ​​en la Sección 2.2 se asumió que se entrenó una sola política de RL
en cada título de juego. En cambio, RL multitarea (MTL) intenta llevar esto más lejos y
Desarrollar un único agente de RL que pueda jugar múltiples títulos de juegos.. Tal como, MTRL es un
paso hacia la “inteligencia general artificial”,” y representa una tarea mucho más difícil
por al menos dos razones: (1) Los agentes de RL no deben “olvidar” ninguna de sus políticas para jugar un
juego anterior mientras aprende una política para jugar un juego nuevo, y (2) durante la prueba, un
El agente de RL debe poder distinguir entre títulos de juegos sin recurrir a información adicional.
información del estado.

Hasta la fecha, Se han propuesto dos enfoques de aprendizaje profundo para esta tarea.. parisotto
et al. (2015) Primero aprende cada título de juego de forma independiente y luego úsalo para entrenar a un solo jugador.
arquitectura para jugar múltiples títulos. Más recientemente Kirkpatrick et al.. (2016) propuesto
una modificación de Double DQN en la que subconjuntos de pesos (particularmente en el MLP)
están asociados con diferentes tareas y sujetos a tasas de aprendizaje más bajas que las ponderaciones no
ya asociado con tareas previamente aprendidas. Pudieron aprender a jugar.
a 6 títulos de juegos a un nivel comparable con el DQN original (capacitado en cada título en-
dependiente), aunque cuando los títulos de los juegos se seleccionan del conjunto de juegos para los cuales
Se sabía que DQN tenía un buen desempeño en.

3 Gráficos de programas enredados

La descomposición modular de tareas a través de la formación de equipos ha sido un tema recurrente en ge.-
programación magnética. Estudios anteriores examinaron métodos para combinar la contribución.-
ción de miembros individuales del equipo (Brameier y Banzhaf, 2001), isla haciendo cumplir
modelos (Imamura et al., 2003), o intercambiar selecciones de equipo versus individuales-
ción (Thomason y Soule, 2007). Una limitación común de tales planes era la exigencia-
ment para preespecificar el número de programas que aparecen dentro de un equipo. Además, incluso
cuando el complemento del equipo evoluciona de forma abierta, anteriormente ha sido necesario-
Es necesario definir el fitness tanto a nivel del programa individual como del equipo. (p.ej., Wu y
Banzhaf, 2011). Es necesario abordar estas limitaciones para facilitar por completo
Enfoques abiertos a la evolución..

3.1

Equipos de programas en evolución

Permitir la evolución del número y complemento de programas por equipo en un
La manera abierta se abordó anteriormente en parte mediante el uso de una metáfora de licitación.
(Lichodzijewski y Heywood, 2008a), en cuyo caso los programas representan acción, a, y
contexto, pag, independientemente. Eso es, cada programa define el contexto para un solo discreto
acción, o un ∈ {A} donde A denota el conjunto de acciones atómicas específicas de la tarea. Las acciones son

352

Volumen de cálculo evolutivo 26, Número 3

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

/

/

mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d

yo

F
/

/

/

/

2
6
3
3
4
7
1
5
5
2
3
7
5
mi
v
C
oh
_
a
_
0
0
2
3
2
pag
d

/

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Aprendizaje por refuerzo emergente multitarea de alta dimensión

asignado al programa en la inicialización y potencialmente modificado por variación oper-
Agentes durante la evolución.. Se supone una representación lineal del programa4 en la que un reg-
El lenguaje de transferencia de nivel superior admite la 4 operadores aritméticos, coseno, logarítmico,
la operación exponencial, y una declaración condicional (ver algoritmo 1). el lineal
la representación facilita omitir el código "intrón", donde esto puede potencialmente representar
60–70% de las instrucciones del programa (Brameier y Banzhaf, 2007). Naturalmente, determinando
cuáles de las variables de estado disponibles se utilizan realmente en el programa, así como el
Número de instrucciones y sus operaciones., son ambas propiedades emergentes de la evolución-
proceso cionario. Después de la ejecución, registrar R[0] representa la “oferta” o “confianza” por
la acción del programa, a, en relación con el estado observado actualmente, (cid:2)s(t ). Un equipo mapea cada
observación del estado, (cid:2)s(t ), a una sola acción ejecutando a todos los miembros del equipo (programas) rel-
activo a (cid:2)s(t ), y luego elegir la acción del mejor postor. Si los programas no fueran
organizado en equipos, en cuyo caso todos los programas dentro de la misma población
competir por el derecho a sugerir su acción, es muy probable que ese individuo degenerado-
como (programas que ofrecen altas ofertas para cada estado), interrumpiría la licitación que de otro modo sería efectiva
estrategias.

La creación adaptativa de equipos de programas se aborda aquí mediante el uso de un
Relación simbiótica entre una población de equipo y una población de programa.; lo sucesivo
“EquipoGP” (Lichodzijewski y Heywood, 2008b). Cada individuo de la población del equipo.-
La ción representa un índice para algún subconjunto de la población del programa. (ver Figura 2a). Equipo
Por lo tanto, los individuos asumen una representación de longitud variable en la que cada individuo
se inicializa estocásticamente con [2, . . . , Vaya] punteros a programas desde el pop del programa-
ulación. La única restricción es que debe haber al menos dos acciones diferentes indexadas.
por el complemento de programas dentro de un mismo equipo. Puede aparecer el mismo programa
en varios equipos, pero debe aparecer en al menos un equipo para sobrevivir entre partidos consecutivos.
generaciones.

Actuación (es decir., aptitud física) se expresa sólo a nivel de equipos, y toma la forma
del objetivo dependiente de la tarea(s). Después de evaluar el desempeño de todos los equipos., el
Los peores equipos de Rgap se eliminan de la población de equipos.. Después de la eliminación del equipo, cualquier profesional-
El programa que no puede ser indexado por ningún equipo debe haber estado asociado con el peor
equipos de actuación, por lo tanto también se elimina. Esto evita la necesidad de tomar decisiones arbitrarias.-
Sesiones con respecto a la definición de condición física a nivel de equipo versus nivel de programa. (que genero-
aliado tomar la forma de heurísticas específicas de la tarea, limitando así la aplicabilidad del modelo

4Se podría emplear cualquier representación de médico de cabecera.; La innovación importante es que el contexto y la acción son

representado independientemente.

Volumen de cálculo evolutivo 26, Número 3

353

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

/

/

mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d

yo

F
/

/

/

/

2
6
3
3
4
7
1
5
5
2
3
7
5
mi
v
C
oh
_
a
_
0
0
2
3
2
pag
d

.

/

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

S. kelly y m. I. heywood

Cifra 2: Subtrama (a) Ilustración de la relación simbiótica entre equipo y programa.
poblaciones. La aptitud para la tarea sólo se expresa a nivel de equipo.. Cada equipo define
un conjunto único de indicadores para algún subconjunto de individuos de la población del programa.
Varios programas pueden tener la misma acción., ya que el contexto asociado para la acción es
definido por el programa. Los equipos legales deben probar al menos dos acciones diferentes.. Subtrama
(b) La acción atómica mutó en un índice para un equipo.. Ahora hay un equipo raíz menos en
la población del equipo.

a dominios de aplicación específicos). Tras la eliminación de los peores equipos, nuevos equipos
se introducen por muestreo, clonación, y modificando los equipos supervivientes de Rgap. Naturalmente, si
Hay un beneficio de rendimiento en equipos más pequeños o más grandes y/o en diferentes programas.-
complementos, Esto se reflejará en los complementos del programa del equipo superviviente. (Lichodzi-
jewski y heywood, 2010), eso es, La complejidad del programa de equipo es un rasgo del desarrollo..

3.2

Gráficos en evolución de equipos

La evolución comienza con una población de programas en la que las acciones del programa se limitan a
tarea específica (atómico) comportamiento (Figuras 1a y 2a). Para prever la evolución
de código organizado jerárquicamente bajo un proceso de evolución completamente abierto
(es decir., modularidad conductual emergente), Los operadores de variación del programa pueden
introducir acciones que indexen a otros equipos dentro de la población del equipo. para hacerlo, cuando un
Se modifica la acción del programa., tiene una probabilidad (patomico) de hacer referencia a un diferente
acción atómica u otro equipo. De este modo, Los operadores de variación tienen la capacidad de aumentar
construir gráficos de políticas de varios equipos (Figuras 1b y 2b).

Cada vértice del gráfico es un equipo., mientras cada miembro del equipo, o programa, representar-
envía una ventaja saliente que conduce a otro equipo o a una acción atómica. Decisión-
La elaboración de un gráfico de políticas comienza en el equipo raíz., donde cada programa en el equipo
producir una oferta relativa al estado actual, (cid:2)s(t ). El recorrido del gráfico luego sigue el pro-
gramo/borde con la oferta más grande, repetir el proceso de licitación por el mismo (cid:2)s(t ) en cada
equipo/vértice a lo largo del camino hasta que se encuentre una acción atómica. De este modo, dado algunos
estado del medio ambiente en el paso de tiempo t, el gráfico de políticas calcula una ruta desde la raíz hasta
acción atómica, donde solo un subconjunto de programas en el gráfico (es decir., aquellos en equipos a lo largo
el camino) requerir ejecución. Algoritmo 2 detalla el proceso de evaluación del TPG indi-
individuales, que se repite en cada fotograma, (cid:2)s(t ), hasta que se encuentre un estado de fin de juego
y se puede determinar la idoneidad para el gráfico de políticas.

A medida que surgen gráficos de políticas de varios equipos, una red de conectividad cada vez más enredada
se desarrolla entre el equipo y las poblaciones del programa.. El número de soluciones únicas.,
o gráficos de políticas, en cualquier generación dada es igual al número de nodos raíz (es decir., equipos

354

Volumen de cálculo evolutivo 26, Número 3

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

/

/

mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d

yo

F
/

/

/

/

2
6
3
3
4
7
1
5
5
2
3
7
5
mi
v
C
oh
_
a
_
0
0
2
3
2
pag
d

/

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Aprendizaje por refuerzo emergente multitarea de alta dimensión

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

/

/

mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d

yo

F
/

/

/

/

2
6
3
3
4
7
1
5
5
2
3
7
5
mi
v
C
oh
_
a
_
0
0
2
3
2
pag
d

/

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

que no están referenciados como acción de ningún programa) en la población del equipo. Sólo estas raíces
Los equipos son candidatos para que se evalúe su condición física., y están sujetos a modificación por
los operadores de variación.

En cada generación, La brecha de los equipos raíz se elimina y se reemplaza por la descendencia de
las raíces sobrevivientes. El proceso para generar descendencia en equipo toma muestras y
clona un equipo raíz, luego aplica operadores de variación basados ​​en mutaciones al equipo clonado
que eliminar, agregar, y mutar algunos de sus programas.

El proceso de generación del equipo introduce nuevos nodos raíz hasta que el número de raíces
en la población alcanza Rsize. El número total de pasos de muestreo para generar-
la primavera fluctúa, como equipos raíz (junto con el gráfico de política inferior) a veces son “sub-
asumido” por un nuevo equipo. En cambio, Los gráficos se pueden separar., Por ejemplo, a través de
mutación de acción del programa, dando como resultado nuevos nodos/políticas raíz. Esto implica que después
inicialización, El tamaño de la población tanto del equipo como del programa varía. Además, mientras que la
El número de equipos raíz permanece fijo., el número de equipos que se “archivan” como
nodos internos (es decir., una biblioteca de código reutilizable) fluctúa.

Evaluación limitante, selección, y la variación a equipos raíz solo tiene dos beneficios críticos-
beneficios: (1) El costo de la evaluación y el tamaño del espacio de búsqueda siguen siendo bajos porque sólo
una fracción de la población del equipo (equipos raíz) representan políticas únicas para ser evaluadas
y modificado en cada generación y (2) ya que solo se eliminan los equipos raíz, introducido,
o modificado, Los gráficos de políticas se desarrollan incrementalmente desde abajo hacia arriba.. Tal como,
Las estructuras complejas de nivel inferior dentro de un gráfico de políticas están protegidas siempre que concuerden.-
homenaje a una política global fuerte.

En resumen, el marco de trabajo en equipo de GP de Lichodzijewski y Heywood (2010) es
Ampliado para permitir que surjan gráficos de políticas., definir la interrelación entre equipos.
Como los programas que componen un equipo suelen indexar diferentes subconjuntos del espacio de estados (es decir.,

Volumen de cálculo evolutivo 26, Número 3

355

S. kelly y m. I. heywood

la pantalla en el caso de ALE), el gráfico de políticas resultante se adaptará progresivamente, en-
definir más o menos el espacio estatal y definir los tipos de decisiones tomadas en diferentes-
regiones entrantes. Finalmente, Kelly y otros. (2018) proporcionar un resumen pictórico adicional de la
algoritmo TPG.

3.2.1 Prueba de neutralidad
Cuando los operadores de variación introducen cambios en un programa, no hay garantía de que
el cambio será: (1) resultar en un cambio de comportamiento, y (2) incluso si un cambio de comportamiento
resultados, Será único en relación con el conjunto actual de programas.. Punto 1 sigue siendo útil como
da como resultado la posibilidad de que se realicen múltiples cambios de código de forma incremental antes
ellos aparecen, o redes neutrales (Brameier y Banzhaf, 2007). Sin embargo, esto también puede
resultan en ciclos de evaluación desperdiciados porque no hay diferencia funcional en relación con
el padre. Dado que la evaluación de la condición física es costosa, Por lo tanto, probamos el comportamiento.
unicidad. Específicamente, 50 de las observaciones estatales más recientes se conservan en un formato global
archivo, o (cid:2)s(t ) ∈ {último − 49, . . . , último }. Cuando se modifica un programa o se crea un programa nuevo
creado, su oferta para cada estado en el archivo se compara con la oferta de cada programa
en la población actual. Mientras todos 50 Los valores de oferta del nuevo programa no son
dentro de τ de todas las ofertas de cualquier otro programa en la población actual, el nuevo programa
es aceptado. Si el nuevo programa no pasa la prueba, luego se muta otra instrucción y el
prueba repetida. Observamos que tal proceso tiene similitudes con la motivación de la novedad.
buscar (Lehman y Stanley, 2011), eso es, una prueba para diferentes resultados. Sin embargo, como esto
El proceso aparece en un programa., no hay garantía de que esto resulte en una novela
Comportamiento cuando aparece en un equipo y sigue siendo apto a nivel de equipo/agentes.
eso determina la supervivencia.

4

Metodología experimental

Para fines comparativos, La evaluación de TPG asumirá el mismo enfoque general.
según lo establecido en la evaluación DQN original (Mnih et al., 2015). De este modo, asumimos el
mismo subconjunto de 49 Títulos de juegos de Atari y, post entrenamiento, prueba el agente campeón de TPG
bajo 30 episodios de prueba inicializados con un número seleccionado estocásticamente de no operativos iniciales
comportamiento (descrito en la Sección 5.1). Esto nos proporcionará la más amplia gama de anteriores.
resultados con fines comparativos.5 Se realizan cinco carreras de TPG independientes por juego
título, donde esto parece reflejar la práctica más reciente para obtener resultados de aprendizaje profundo.6

Se utilizó la misma parametrización para TPG para todos los juegos. (Sección 4.2). El único
La información proporcionada a los agentes fue el número de acciones atómicas disponibles para cada uno.
juego, el marco de pantalla preprocesado durante el juego (Sección 4.1), y el resultado final del juego.
Cada gráfico de políticas fue evaluado en 5 episodios de juegos por generación, hasta un máximo
de 10 episodios de juego por vida. La aptitud para cada gráfico de políticas es simplemente el promedio
puntuación del juego en todos los episodios. Se identificó una política de campeón único para cada juego como
el que tiene la mayor recompensa de entrenamiento al final de la evolución.

4.1

Captura de pantalla del espacio de estado

Basado en la observación de que la entrada visual tiene mucha información redundante (es decir.,
El contenido visual del juego está diseñado para maximizar el valor del entretenimiento., en contraposición a un

5También ha aparecido un escenario de prueba alternativo en el que el agente RL asume el control del estado del juego.
identificado por un jugador humano en un intento de introducir mayor diversidad en el estado de inicio del agente RL
selección (Nair et al., 2015; Mnih et al., 2016).

6Los resultados originales de DQN solo reflejaron una ejecución por título. (Mnih et al., 2015).

356

Volumen de cálculo evolutivo 26, Número 3

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

/

/

mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d

yo

F
/

/

/

/

2
6
3
3
4
7
1
5
5
2
3
7
5
mi
v
C
oh
_
a
_
0
0
2
3
2
pag
d

/

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Aprendizaje por refuerzo emergente multitarea de alta dimensión

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

/

/

mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d

yo

F
/

/

/

/

2
6
3
3
4
7
1
5
5
2
3
7
5
mi
v
C
oh
_
a
_
0
0
2
3
2
pag
d

.

/

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Cifra 3: Pasos de cuantificación de pantalla, reduciendo la matriz de píxeles de Atari sin procesar (a) a 1344 dic-
variables de estado imales (C) utilizando un esquema de submuestreo cuadriculado (b).

Necesidad de transmitir contenido con una cantidad mínima de información.), adoptamos una cuantificación
enfoque para el preprocesamiento. El siguiente procedimiento de dos pasos se aplica a cada juego.
marco:

1. Se utiliza una máscara de patrón a cuadros para muestrear 50% de los píxeles del juego raw
pantalla (ver Figura 3b). Cada píxel restante asume el SECAM de 8 colores.-
codificación. ALE proporciona la codificación SECAM como alternativa a la codificación de-
fallo Formato NTSC de 128 colores. saltando uniformemente 50% de los píxeles de la pantalla sin procesar
mejora la velocidad de recuperación de funciones y tiene un efecto mínimo en la fi-
representación final, ya que las entidades importantes del juego suelen ser más grandes que una sola
píxel.

2. El marco se subdivide en un 42 × 32 grid.7 Cada mosaico de la cuadrícula se describe mediante un pecado-
byte gle, en el que cada bit codifica la presencia de uno de los ocho colores SECAM
dentro de ese azulejo. La representación de pantalla cuantificada final incluye cada byte de mosaico.
como valor decimal, definiendo así un espacio de estados estatales (cid:2)s(t ) de 42 × 32 = 1,344 decimal
características en el rango de 0 a 255, visualizado en la Figura 3c para el juego Up 'N Down
en el paso del tiempo (marco) t.

Esta representación del estado está inspirada en el método básico definido en Bellemare., Limpiar
et al. (2012). Nota, sin embargo, que este método no utiliza detección de fondo a priori
o combinaciones de características por pares.

7Implica que el original 210 × 160 La pantalla está dividida por 5.

Volumen de cálculo evolutivo 26, Número 3

357

S. kelly y m. I. heywood

En comparación con el enfoque DQN (Mnih et al., 2015; Nair et al., 2015), ningún intento
está hecho para diseñar las propiedades parcialmente observables del contenido del juego. (ver discusión
de Sección 2.2). Además, Las tres capas de convolución de la arquitectura de aprendizaje profundo.
Los filtros reducen el muestreo. 84 × 84 = 7,056 espacio de píxeles a una dimensión de 3,136
antes de aplicar un perceptrón multicapa completamente conectado (MLP).8 es la combinacion
de capa convolucional y MLP que representa el costo computacional del aprendizaje profundo.
Naturalmente, esto imparte un costo computacional fijo de aprendizaje ya que todo el archivo DQN-
La tecnología se especifica a priori. (Sección 6.3).

A diferencia de, TPG desarrolla un agente de toma de decisiones desde un 1,344 espacio dimensional.
En común con el enfoque DQN, no se realiza ninguna extracción de características como parte del
paso de preprocesamiento, sólo una cuantificación de los datos del cuadro original. Implícito en esto hay una
Suposición de que el espacio de estados es altamente redundante.. Por lo tanto, TPG percibe el estado
espacio, (cid:2)s(t ) (Figura 3c), como memoria de solo lectura. Cada programa TPG define entonces un po-
subconjunto potencialmente único de entradas de (cid:2)s(t ) para incorporarlos en su toma de decisiones
proceso. Luego se requieren las propiedades emergentes de TPG para desarrollar la complejidad de
una solución, o gráfico de políticas, con programas organizados en equipos y equipos en gráficos.
De este modo, en lugar de asumir que todo el contenido de la pantalla contribuye a la toma de decisiones, el
El enfoque adoptado por TPG es submuestrear de forma adaptativa desde el espacio de imagen cuantificado..
El subconjunto específico de variables de estado muestreadas dentro de cada política de agente es una
propiedad, Se descubre únicamente a través de la interacción con el entorno de la tarea.. lo implícito-
cationes de asumir un enfoque tan explícitamente emergente sobre el costo computacional
ser revisado en la Sección 6.3.

4.2

Parametrización de TPG

La implementación de algoritmos basados ​​en la población puede resultar costosa debido a la cantidad de
Parámetros e interrelación entre diferentes parámetros.. En este trabajo, ningún intento
Se ha realizado para optimizar la parametrización. (ver tabla 1); en lugar de eso, trasladamos un
parametrización básica a partir de la experiencia con equipos individuales en evolución bajo una supervisión
tarea de aprendizaje (Lichodzijewski y Heywood, 2010).

Se enumeran tres categorías básicas de parámetros.: Prueba de neutralidad (Sección 3.2.1), Equipo
población, y población del programa (Cifra 2). En el caso de la población del Equipo, el
Las decisiones sobre parámetros más importantes son el tamaño de la población. (cuantos equipos al mismo tiempo
apoyo), y cuántas soluciones candidatas reemplazar en cada generación (Rgap). El
parámetros que controlan la aplicación de los operadores de variación comunes a los anteriores en-
posturas del TeamGP (pmd , pma, pmm, pmn) asumir también los valores utilizados bajo supervisión
tareas de aprendizaje (Lichodzijewski y Heywood, 2010). En cambio, patomico representa un
parámetro específico de TPG, donde esto define la probabilidad relativa de mutar una acción
a una acción atómica versus un puntero a un equipo (Sección 3.2).

Asimismo, los parámetros que controlan las propiedades de la población del programa como-
Sume los valores utilizados para TeamGP aplicados a las tareas de aprendizaje supervisadas para todos excepto
maxP rogTamaño. En esencia, esto se ha incrementado hasta el punto en que es poco probable que sea
encontrado durante la evolución. El título del algoritmo 1 resume la instrucción
conjunto y representación adoptados para los programas.

El límite computacional para TPG se define en términos de un recurso computacional
restricción de tiempo. De este modo, Los experimentos se ejecutaron en un clúster compartido con un tiempo de ejecución máximo.
de 2 semanas por título de juego. The nature of some games allowed for >800 generations,

8Para ver un tutorial sobre cómo estimar el tamaño de los filtros en arquitecturas de aprendizaje profundo, consulte http://cs231n

.github.io/convolutional-networks/

358

Volumen de cálculo evolutivo 26, Número 3

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

/

/

mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d

yo

F
/

/

/

/

2
6
3
3
4
7
1
5
5
2
3
7
5
mi
v
C
oh
_
a
_
0
0
2
3
2
pag
d

.

/

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Aprendizaje por refuerzo emergente multitarea de alta dimensión

Mesa 1: Parametrización de TPG.

Prueba de neutralidad (Sección 3.2.1)

Número de muestras históricas en prueba de diversidad.
Umbral para la unicidad de la oferta (t )

Población del equipo

Número de (raíz) equipos en la población inicial (tamaño R)
Número de nodos raíz que se pueden reemplazar por generación (Rgap)
Probabilidad de eliminar o agregar un programa (pmd , pma)
máx.. tamaño inicial del equipo (Vaya)
problema. de crear un nuevo programa (pmm)
problema. de cambiar una acción del programa (pmn)
problema. de definir una acción como un equipo o acción atómica (patomico)

Población del programa

Número total de registros por programa (numRegistros)
máx.. Número de instrucciones que puede tomar un programa. (maxProgSize)
problema. de eliminar o agregar una instrucción dentro de un programa (borrar, paddock )
problema. de mutar una instrucción dentro de un programa (pmutado)
problema. de intercambiar un par de instrucciones dentro de un programa (pswap)

50
10−4

360
50%
0.7
5
0.2
0.1
0.5

8
96
0.5
1.0
1.0

mientras que otros limitaron la evolución a unos pocos cientos. No se hizo ningún intento de paralelizar
ejecución dentro de cada ejecución (es decir., la base del código TPG se ejecuta como un solo hilo), el clus-
ter simplemente permitió que cada ejecución se hiciera simultáneamente. De paso, los resultados de DQN
se requieren entre 12 y 14 días por título de juego en una plataforma informática GPU (Nair et al., 2015).

5

Aprendizaje de una sola tarea

Esta sección documenta la capacidad del TPG para construir políticas de toma de decisiones en el ALE desde
la perspectiva de la IA independiente del dominio, eso es, descubrir políticas para una variedad de
Entornos de juego ALE sin ajuste de parámetros específicos de tareas. Antes de presentar de-
resultados de cola, Proporcionamos una descripción general del rendimiento del entrenamiento para TPG en el conjunto de
49 Títulos ALE comunes a la mayoría de los estudios de evaluación comparativa. (Sección 2.2). Cifra 4 ilustra
rendimiento medio del entrenamiento TPG (a través del 5 carreras por título de juego) como relación normalizada-
Ativo al puntaje de la prueba DQN. (100%) y juego aleatorio (0%) (Mnih et al., 2015). el azar
El agente simplemente selecciona acciones con probabilidad uniforme en cada marco del juego.9 Bajo prueba
condiciones, TPG supera puntuación de DQN en 27 juegos (Figura 4a), mientras que DQN mantiene el
puntuación más alta en 21 juegos (Figura 4b). De este modo, TPG y DQN son ampliamente comparables desde
una perspectiva de rendimiento, cada uno igualando/venciendo al otro en un subconjunto del entorno del juego-
ambientes. En efecto, no hay diferencia estadística entre los puntajes de las pruebas TPG y DQN
en general 49 juegos (Sección 5.1). Sin embargo, TPG produce soluciones mucho más simples en todos
casos, en gran parte debido a su representación modular emergente, que escala automáticamente
a través de la interacción con el entorno de la tarea. Es decir, simultáneamente con el aprendizaje de

9La puntuación normalizada se calcula como 100 × (Puntuación TPG: puntuación de juego aleatorio)/(Puntuación DQN: aleatoria
jugar puntuación). La normalización de puntuaciones permite trazar el progreso de TPG en relación con múltiples juegos.
juntos independientemente del esquema de puntuación en diferentes juegos, y facilita hacer una comparación directa
con DQN.

Volumen de cálculo evolutivo 26, Número 3

359

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

/

/

mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d

yo

F
/

/

/

/

2
6
3
3
4
7
1
5
5
2
3
7
5
mi
v
C
oh
_
a
_
0
0
2
3
2
pag
d

.

/

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

S. kelly y m. I. heywood

Cifra 4: Curvas de entrenamiento TPG, cada uno normalizado en relación con la puntuación de DQN en el mismo
juego (100%) y juego aleatorio (0%): (a) muestra curvas para el 27 juegos en los que TPG
finalmente superó el nivel de DQN en condiciones de prueba y (b) muestra curvas para el
21 juegos en los que TPG no alcanzó el nivel DQN durante la prueba. Tenga en cuenta que en varios juegos
TPG comenzó con políticas aleatorias (generación 1) que superó el nivel de DQN. Nota
que estos son puntajes de entrenamiento promediados durante 5 episodios en el título del juego dado, y son
por lo tanto, no es tan sólido como el puntaje de la prueba DQN utilizado para la normalización.. También, estas políticas fueron
a menudo degenerado. Por ejemplo, en ciempiés, es posible obtener una puntuación de 12,890 por
seleccionar la acción "disparar hacia arriba" en cada fotograma. Aunque es completamente poco interesante, este
La estrategia supera la puntuación de la prueba informada para DQN. (8,390) y la puntuación de la prueba reportada para
un probador de videojuegos profesional humano (11,963) (Mnih et al., 2015). Independientemente de su
punto de partida, Las políticas de TPG mejoran a lo largo de la evolución para volverse más receptivas
e interesante. Tenga en cuenta también que en Video Pinball, TPG superó la puntuación de DQN durante
entrenando pero no bajo prueba. La curva de La venganza de Moctezuma no aparece en la foto., un juego
en el que ninguno de los algoritmos obtiene puntos.

estrategia para el juego, TPG responde explícitamente a la pregunta de: (1) qué indexar del
representación estatal para cada juego; y (2) ¿Qué componentes de otras políticas candidatas
potencialmente incorporar dentro de una política más amplia. En cambio, DQN asume una partícula-
gran arquitectura, basado en una combinación específica de aprendizaje profundo y MLP, en el que todos los estados
la información siempre contribuye.

5.1 Competencia en el entorno de aprendizaje de Atari

La calidad de las políticas TPG se mide bajo las mismas condiciones de prueba que se utilizan para DQN.,
o la puntuación media sobre 30 episodios por título de juego con diferentes condiciones iniciales
y un máximo de 18,000 fotogramas por juego (Mnih et al., 2015; Nair et al., 2015). Diverso
Las condiciones iniciales se logran obligando al agente a seleccionar "ninguna acción" para la primera vez.-
fotogramas operativos de cada juego de prueba, donde no-op ∈ [0, 30], seleccionado con probabilidad uniforme en

360

Volumen de cálculo evolutivo 26, Número 3

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

/

/

mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d

yo

F
/

/

/

/

2
6
3
3
4
7
1
5
5
2
3
7
5
mi
v
C
oh
_
a
_
0
0
2
3
2
pag
d

.

/

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Aprendizaje por refuerzo emergente multitarea de alta dimensión

el comienzo de cada juego.10 Dado que algunos títulos de juegos derivan su semilla aleatoria de la inicial
acciones del jugador, el no-op estocástico asegura una semilla diferente para cada juego de prueba. estocástico
salto de fotograma, discutido en la Sección 2.1, implica variación en las semillas aleatorias y una
entorno estocástico durante el juego. Se aplican tanto el salto de fotograma como la no operación.
en este trabajo para garantizar un entorno estocástico y una comparación justa con DQN. Asimismo,
También se supone que se conocen las acciones disponibles por juego.11

Se consideran dos conjuntos de algoritmos comparadores.:

• Estado de captura de pantalla: construir modelos a partir del estado del juego, (cid:2)s(t ), definido en términos
de alguna forma de entrada de captura de pantalla.12 Estos incluyen el DQN profundo original
resultados de aprendizaje (Mnih et al., 2015), DQN implementado a través de un despliegue masivo-
búsqueda homenajeada (Nair et al., 2015), doble DQN (van Hasselt et al., 2016), y
hiper-ordenado (Hausknecht et al., 2014). Si bien el informe original de DQN enfatiza-
comparación de tamaño con un probador de juegos profesional humano (Mnih et al., 2015),
Aquí evitamos tal comparación principalmente porque los resultados en humanos no son
reproducible.

• Funciones de ingeniería: definir el estado del juego, (cid:2)s(t ), en términos de características diseñadas
a priori; de este modo, simplificando significativamente la tarea de encontrar políticas efectivas
para jugar, pero potencialmente introduciendo sesgos no deseados. Específicamente, el
Los resultados Hyper-NEAT y NEAT utilizan características de "Objeto" diseñadas a mano y específicas para
cada título de juego en el que diferentes “sustratos” denotan la presencia y ubicación-
ción de diferentes clases de objetos (véase Hausknecht et al., 2014 y la discusión
de Sección 2.2). Los resultados de Blob-PROST asumen características diseñadas a partir de un at-
Tentar a aplicar ingeniería inversa al proceso realizado por DQN. (Liang et al., 2016).
El espacio de estados resultante es un vector de ≈110 × 106 atributos de los cuales un lin-
Se construye el agente RL del oído. (vendaje). Finalmente, el agente Sarsa RL con mejor desempeño
(Conti-Sarsa) está incluido en el estudio DQN (Mnih et al., 2015) donde esto como-
asume la disponibilidad de funciones de “conciencia de contingencia” (Bellamare, Venecia
et al., 2012b).

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

/

/

mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d

yo

F
/

/

/

/

2
6
3
3
4
7
1
5
5
2
3
7
5
mi
v
C
oh
_
a
_
0
0
2
3
2
pag
d

.

/

En cada caso, el TPG basado en la captura de pantalla se comparará con el conjunto de comparador.
modelos en un conjunto común de 49 Títulos de juegos de Atari. La significancia estadística será como-
evaluado mediante la prueba de Friedman, donde esta es una forma no paramétrica de ANOVA (Demšar,
2006; Japkowicz y Shah, 2011). Específicamente, Las pruebas de hipótesis paramétricas asumen com.-
mensurabilidad de las medidas de desempeño. Esto implicaría que promediar los resultados entre
múltiples títulos de juegos tienen sentido. Sin embargo, dado que el tamaño del paso de puntuación y los tipos de
Las propiedades medidas en cada título suelen ser diferentes., luego promediando el rendimiento de la prueba nula-
La rentabilidad entre varios títulos ya no es conmensurable.. En cambio, la prueba de Friedman
Establece si hay o no un patrón en las filas.. Rechazando la hipótesis nula
implica que hay un patrón, y la prueba post hoc de Nemenyi se puede aplicar para evaluar
el significado (Demšar, 2006; Japkowicz y Shah, 2011).

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

10Algunos títulos de juegos se verán más afectados que otros. Por ejemplo, títulos como Sra.. juego pac-man
una canción para los primeros ≈70 fotogramas del juego mientras se ignoran las acciones del agente (por lo tanto, la operación no operativa no tiene ningún efecto),
mientras que en otros títulos el agente toma el control inmediatamente.

11El estudio de Liang et al.. (2016) cuestiona esta suposición, pero descubre que un mejor rendimiento se refiere-

Resultó cuando los agentes RL se construyeron con el espacio de acción completo..

12Revisado en la sección 2.2 para algoritmos comparadores y se detalla en la Sección 4.1 para TPG.

Volumen de cálculo evolutivo 26, Número 3

361

S. kelly y m. I. heywood

En el caso de agentes RL derivados de información de estado de captura de pantalla (Mesa 7,
= 21.41 que para los efectos de la
Apéndice A), la prueba de Friedman arroja una χ 2
F
La hipótesis nula tiene un valor equivalente de la distribución F de FF = 5.89 (Demšar,
2006). El valor crítico correspondiente F (un = 0.01, 4, 192) es 3.48, de ahí el nulo hy-
la potesis es rechazada. Aplicando la prueba post hoc de Nemenyi (un = 0.05) proporciona una crítica
diferencia de 0.871. De este modo, en relación con el algoritmo mejor clasificado (Gorila), solo hiper-
NEAT se identifica explícitamente como fuera del conjunto de algoritmos de rendimiento equivalente
(o 2.63 + 0.871 < 3.87). This conclusion is also borne out by the number of game ti- tles for which each RL agent provides best case performance; Hyper-NEAT provides 4 best case game titles, whereas TPG, Double DQN and Gorila return at least 11 best title scores each (Table 7, Appendix A). Repeating the process for the comparison of TPG13 to RL agents trained under = 80.59 and an equiv- hand crafted features (Table 8), the Friedman test returns a χ 2 F alent value from the F-distribution of FF = 33.52. The critical value is unchanged as the number of models compared and game titles is unchanged, hence the Null hypothesis is rejected. Likewise the critical difference from the post hoc Nemenyi test (α = 0.05) is also unchanged, 0.871. This time only the performance of the Conti-Sarsa algorithm is identified as significantly worse (or 2.16 + 0.871 < 4.76). In summary, these results mean that despite TPG having to develop all the architec- tural properties of a solution, TPG is still able to provide an RL agent that performs as well as current state of the art. Conversely, DQN assumes a common prespecified deep learning topology consisting of millions of weights. Likewise, Hyper-NEAT assumes a pre-specified model complexity of ≈900,000 weights, irrespective of game title. As will become apparent in the next section, TPG is capable of evolving policy complexities that reflect the difficulty of the task. 6 Simplicity through Emergent Modularity The simplest decision making entity in TPG is a single team of programs (Figure 1a), representing a standalone behaviour which maps quantized pixel state to output (ac- tion). Policies are initialized in their simplest form: as a single team with between 2 and ω programs. Each initial team will subsample a typically unique portion of the available (input) state space. Throughout evolution, search operators will develop team/program complement and may incrementally combine teams to form policy graphs. However, policies will complexify only when/if simpler solutions are outperformed. Thus, solu- tion complexity is an evolved property driven by interaction with the task environment. By compartmentalizing decision making over multiple independent modules (teams), and incrementally combining modules into policy graphs, TPG is able to simultane- ously learn which regions of the input space are important for decision making and discover an appropriate decision-making policy. 6.1 Behavioural Modularity Emergent behavioural modularity in the development of TPG solutions can be visual- ized by plotting the number of teams incorporated into the champion policy graph as a function of generation (see Figure 5a). Development is nonmonotonic, and the speci- ficity of team compliment as a function of game environment is readily apparent. For example, a game such as Asteroids may see very little in the way of increases to team complement as generations increase. Conversely, Ms. Pac-Man, which is known to be 13TPG still assumes screen capture state. 362 Evolutionary Computation Volume 26, Number 3 l D o w n o a d e d f r o m h t t p : / / d i r e c t . m i t . / / e d u e v c o a r t i c e - p d l f / / / / 2 6 3 3 4 7 1 5 5 2 3 7 5 e v c o _ a _ 0 0 2 3 2 p d / . f b y g u e s t t o n 0 8 S e p e m b e r 2 0 2 3 Emergent High-Dimensional Multitask Reinforcement Learning l D o w n o a d e d f r o m h t t p : / / d i r e c t . m i t . / / e d u e v c o a r t i c e - p d l f / / / / 2 6 3 3 4 7 1 5 5 2 3 7 5 e v c o _ a _ 0 0 2 3 2 p d / . f b y g u e s t t o n 0 8 S e p e m b e r 2 0 2 3 Figure 5: Emergent modularity. (a) Development of the number of teams per champion policy graph as a function of generation and game title. The run labeled “Rand” reflects the number of teams per policy when selection pressure is removed, confirming that module emergence is driven by selective pressure rather than drift or other potential biases. Black circles indicate the total number of teams in each champion policy, while × symbols indicate the average number of teams visited to make each single decision during testing. (b) Development of the proportion of input space indexed by champion policies. Black circles indicate the total proportion indexed by each champion policy, while × symbols indicate the average proportion observed to make each single decision during testing. For clarity, only the 27 game titles with TPG agent performance ≥DQN are depicted. a complex task (Pepels and Winands, 2012; Schrum and Miikkulainen, 2016), saw the development of a policy graph incorporating ≈200 teams. Importantly, making a deci- sion in any single time step requires following one path from the root team to atomic action. Thus, the cost in mapping a single game frame to an atomic action is not linearly correlated to the graph size. For example, while the number of teams in the Alien policy was ≈60, on average only 4 teams were visited per graph traversal during testing (see × symbols in Figure 5a). Indeed, while the total number of teams in champion TPG policy graphs ranges from 7 (Asteroids) to 300 (Bowling), the average number of teams visited per decision is typically less than 5 (Figure 5a). 6.2 Evolving Adapted Visual Fields Each Atari game represents a unique graphical environment, with important events occurring in different areas of the screen, at different resolutions, and from different perspectives (e.g., global maze view versus first-person shooter). Part of the challenge with high-dimensional visual input data is determining what information is relevant to the task. Naturally, as TPG policy graphs develop, they will incrementally index more of the state space. This is likely one reason why they grow more in certain environments. Evolutionary Computation Volume 26, Number 3 363 S. Kelly and M. I. Heywood l D o w n o a d e d f r o m h t t p : / / d i r e c t . m i t . / / e d u e v c o a r t i c e - p d l f / / / / 2 6 3 3 4 7 1 5 5 2 3 7 5 e v c o _ a _ 0 0 2 3 2 p d / . f b y g u e s t t o n 0 8 S e p e m b e r 2 0 2 3 Figure 6: Adapted Visual Field (AVF) of champion TPG policy graph in Up ’N Down. Black regions indicate areas of the screen not indexed. (a) Shows the raw game screen. (b) Shows the preprocessed state space, where each decimal state variable (0–255) is mapped to a unique colour. (c) Shows the AVF for a single team along the active path through the policy graph at this time step, while (d) shows the AVF for the policy graph as a whole. Both AVFs exhibit patterns of sensitivity consistent with important regular- ities of the environment, specifically the zigzagging track. Figure 5b plots the proportion of input space indexed by champion policy graphs throughout development, where this naturally correlates with the policy graph devel- opment shown in Figure 5a. Thus, the emergent developmental approach to model building in TPG can also be examined from the perspective of the efficiency with which information from the state space (cid:2)s(t ) is employed. In essence, TPG policies have the ca- pacity to develop their own Adapted Visual Fields (AVF). While the proportion of the visual field (input space) covered by a policy’s AVF ranges from about 10% (Asteroids) to 100% (Bowling), the average proportion required to make each decision remains low, or less than 30% (see × symbols Figure 5b). Figure 6 provides an illustration of the AVF as experienced by a single TPG team (c) versus the AVF for an entire champion TPG policy graph (d) in the game “Up ‘N Down.” This is a driving game in which the player steers a dune buggy along a track that zigzags vertically up and down the screen. The goal is to collect flags along the route and avoid hitting other vehicles. The player can smash opponent cars by jumping on them using the joystick fire button, but loses a turn upon accidentally hitting a car or jumping off the track. TPG was able to exceed the level of DQN in Up ’N Down (test games consistently ended due to the 18,000 frame limit rather than agent error) with a policy graph that indexed only 42% of the screen in total, and an average 12% of the screen per decision 364 Evolutionary Computation Volume 26, Number 3 Emergent High-Dimensional Multitask Reinforcement Learning (see column %SP in Table 3). The zigzagging patterns that constitute important game areas are clearly visible in the policy’s AVF. In this case, the policy learned a simplified sensor representation well tailored to the task environment. It is also apparent that in the case of the single TPG team, the AVF does not index state information from a specific local region, but instead samples from a diverse spatial range across the entire image (Figure 6c). In order to provide more detail, column %SP in Table 3 gives the percent of state space (screen) indexed by the policy as a whole. Maze tasks, in which the goal involves directing an avatar through a series of 2-D mazes (e.g., Bank Heist, Ms. Pac-Man, Ven- ture) typically require near-complete screen coverage in order to navigate all regions of the maze, and relatively high-resolution is important to distinguish various game en- tities from maze walls. However, while the policy as a whole may index most of the screen, the modular nature of the representation implies that no more than 27% of the indexed space is considered before making each decision (Table 3, column %SP), sig- nificantly improving the runtime complexity of the policy. Furthermore, adapting the visual field implies that extensive screen coverage is only used when necessary. Indeed, in 10 of the 27 games for which TPG exceeded the score of DQN, it did so while index- ing less that 50% of the screen, further minimizing the number of instructions required per decision. In summary, while the decision-making capacity of the policy graph expands through environment-driven complexification, the modular nature of a graph repre- sentation implies that the cost of making each decision, as measured by the number of teams/programs which require execution, remains relatively low. Section 6.3 investi- gates the issue of computational cost to build solutions, and Section 6.4 will consider the cost of decision making post-training. 6.3 Computational Cost The budget for model building in DQN was to assume a fixed number of decision mak- ing frames per game title (50 million). The cost of making each decision in deep learn- ing is also fixed a priori, a function of the preprocessed image (Section 6.3) and the complexity of a multilayer perceptron (MLP). Simply put, the former provides an en- coding of the original state space into a lower-dimensional space; the latter represents the decision-making mechanism. As noted in Section 4.2, TPG runs are limited to a fixed computational time of 2 weeks per game title. However, under TPG the cost of decision making is variable as solutions do not assume a fixed topology. We can now express computational cost in terms of the cost to reach the DQN performance threshold (27 game titles), and the typical cost over the two-week period (remaining 21 game titles). Specifically, let T be the generation at which a TPG run exceeds the performance of DQN. P (t ) denotes the number of policies in the population at generation t. Let i(t ) be the average number of instructions required by each policy to make a decision, and let f (t ) be the total number of frames observed over all policies at generation t; then the total number of operations t=1 P (t ) × required by TPG to discover a decision-making policy for each game is i(t ) × f (t ). When viewed step-wise, this implies that computational cost can increase or decrease relative to the previous generation, depending on the complexity of evaluating TPG individuals (which are potentially all unique topologies). (cid:2) T Figure 7 plots the number of instructions required for each game over all decision- making frames observed by agents during training. Figure 7a characterizes computa- tional cost in terms of solutions to the 27 game titles that reached the DQN performance Evolutionary Computation Volume 26, Number 3 365 l D o w n o a d e d f r o m h t t p : / / d i r e c t . m i t . / / e d u e v c o a r t i c e - p d l f / / / / 2 6 3 3 4 7 1 5 5 2 3 7 5 e v c o _ a _ 0 0 2 3 2 p d . / f b y g u e s t t o n 0 8 S e p e m b e r 2 0 2 3 S. Kelly and M. I. Heywood Figure 7: Number of operations per frame (y-axis) over all game frames observed dur- ing training (x-axis). (a) Shows the subset of games up to the point where TPG exceeded DQN test score. (b) Shows games for which TPG did not reach DQN test score. Black diamonds denote the most complex cases, with text indicating the cumulative number of operations required to train each algorithm up to that point. DQN’s architecture is fixed a priori, thus cumulative computational cost at each frame is simply a sum over the number of operations executed up to that frame. TPG’s complexity is adaptive, thus producing a unique development curve and max operations for each game title. Frame limit for DQN was 50 million (5 × 107). Frame limit for TPG, imposed by a cluster re- source time constraint of 2 weeks, is only reached in (b). threshold, that is, the computational cost of reaching the DQN performance threshold. Conversely, Figure 7b illustrates the computational cost for games that never reached the DQN performance threshold, that is, terminated at the 2-week limit. As such, this is representative of the overall cost of model building in TPG for the ALE task given a two-week computational budget. In general, cost increases with an increasing number of (decision-making) frames, but the cost benefit of the nonmonotonic, adaptive nature of the policy development is also apparent. It is also readily apparent that TPG typically employed more than the DQN budget for decision-making frames (5 × 107). However, the cost of model construction is also a function of the operations per decision. For example, the parameterization adopted by DQN results in an MLP hidden layer consisting of 1,605,632 weights, or a total com- putational cost in the order of 0.8 × 1014 over all 50,000,000 training frames. The total cost of TPG model building is 4 × 1011 in the worst case (Figure 7a). Thus, the cost of the MLP step, without incorporating the cost of performing the deep learning convolu- tion encoding (>3 millones de cálculos en la capa 1 para la parametrización de Mnih et al.,
2015), supera el TPG en varios órdenes de magnitud. Además, esto no refleja la
Costo adicional de realizar una única actualización de peso..

366

Volumen de cálculo evolutivo 26, Número 3

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

/

/

mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d

yo

F
/

/

/

/

2
6
3
3
4
7
1
5
5
2
3
7
5
mi
v
C
oh
_
a
_
0
0
2
3
2
pag
d

/

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Aprendizaje por refuerzo emergente multitarea de alta dimensión

Mesa 2: Tiempo de reloj de pared para tomar cada decisión y requerimiento de memoria..

Método

Decisiones por segundo

Fotogramas por segundo

Memoria

DQN
Blob-PROST
TPG

5
56–300
758–2853

20
280–1500
3032–11412

9.8 ES
50 MB–9GB
118 MB–146 MB†

†Los valores de TPG reflejan la memoria utilizada para apoyar a toda la población, mientras que solo un campeón
El agente se despliega después del entrenamiento., eso es, decenas a cientos de kilobytes. El tiempo del reloj de pared TPG se mide en un
2.2-Procesador Intel Xeon E5-2650 de GHz.

6.4 Costo de la toma de decisiones en tiempo real

Mesa 2 Resume el costo/requisito de recursos al tomar decisiones después del tren.-
En g, eso es, el costo de implementar un agente. Liang et al.. (2016) reportar cifras para el mem-
Hora de la memoria y del reloj de pared en una CPU Intel Core i7-4790S de 3,2 GHz. Costo computacional para
DQN es esencialmente estático debido a que se asume una arquitectura fija para todos los juegos.. Gota-
La complejidad de PROST es una función de la diversidad de la paleta de colores en el título del juego.. AP-
paternalmente el 9 El número de GB fue el peor de los casos., con 3.7 GB representa el siguiente mayor
requisito de memoria. Es evidente que las soluciones TPG suelen ser 2 a 3 órdenes de
magnitud más rápido que DQN y un orden de magnitud más rápido que Blob-PROST.

La complejidad del modelo TPG es un rasgo evolucionado (Sección 6) y sólo una fracción del
El gráfico TPG resultante se visita alguna vez por decisión.. Mesa 3 proporciona una caracterización de
esto en términos de tres propiedades de los equipos campeones (como promedio durante el 5 campeones
por título de juego, un campeón por carrera):

• Equipos (tm)—tanto el número total promedio de equipos por campeón como el cor-

número promedio de equipos visitados por decisión.

• Instrucciones por decisión (Ins)—el número promedio de instrucciones ejecutadas
por decisión del agente. Tenga en cuenta que como representación de programación genética lineal
se supone, la mayoría de los códigos de intrones se pueden identificar fácilmente y omitir para el propósito.-
poses de ejecución del programa (Brameier y Banzhaf, 2007). De este modo, “Ins” refleja
el código realmente ejecutado.

• Proporción del campo visual (%SP)—la proporción del espacio de estados (Sección 4.1)
indexado por todo el gráfico TPG versus el realmente indexado por decisión. Este
refleja el hecho de que los médicos de cabecera, a diferencia del aprendizaje profundo o Blob-PROST, son
nunca obligado a indexar explícitamente todo el espacio de estados. En cambio las partes del
El espacio estatal utilizado por programa es una propiedad emergente. (discutido en detalle
en la sección 6.2).

Ahora resulta evidente que, en promedio, sólo 4 Los equipos requieren evaluación por decisión. (vale-
ues entre paréntesis en la columna Tm, Mesa 3). Esto también significa que las decisiones suelen ser
hecho sobre la base del 3-27% del espacio de estado disponible (valores entre paréntesis en %SP
columna, Mesa 3). Asimismo, el número de instrucciones ejecutadas depende en gran medida
en el título del juego. El agente TPG de Time Pilot ejecutó más de mil instrucciones
por acción, mientras que el agente TPG para Asteroides sólo ejecutó 96. En breve, en vez de
tener que asumir una topología fija de toma de decisiones con cientos de miles de

Volumen de cálculo evolutivo 26, Número 3

367

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

/

/

mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d

yo

F
/

/

/

/

2
6
3
3
4
7
1
5
5
2
3
7
5
mi
v
C
oh
_
a
_
0
0
2
3
2
pag
d

.

/

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

S. kelly y m. I. heywood

Mesa 3: Caracterizando la complejidad general de TPG. Tm denota el número total de equipos.
en campeones versus el número promedio de equipos visitados por decisión (valor en par-
tesis). Ins denota el número promedio de instrucciones ejecutadas para tomar cada decisión..
%SP denota la proporción total del espacio estatal cubierto por la política versus (valor
entre paréntesis).

Título

tm

Ins

%SP

Título

tm

Ins

%SP

Extranjero
Agresión
asteroides
Atraco a un banco
Jinete de haz
Boxeo
Ciempiés
Escalador loco
Doble mate
Derbi de pesca
Congelación
gravitar
Hockey sobre hielo
Canguro
Maestro de Kung Fu
EM. Pac-Man
Apestar
Q*Berto
Correcaminos
Búsqueda del mar
Artillero estelar
Piloto del tiempo
Arriba y abajo
Vídeo pinball
Zaxxón

67(4)
37(4)
7(2)
94(3)
115(4)
102(6)
36(4)
150(3)
10(2)
33(3)
45(4)
49(4)
29(4)
52(4)
31(2)
197(5)
12(4)
255(8)
86(7)
58(4)
17(4)
189(5)
28(3)
38(3)
81(4)

498
420
96
532
443
1156
587
1076
98
472
434
499
442
877
137
603
283
2346
1169
579
516
1134
425
399
613

68(13) Medir
50(14) Astérix
Atlántida
10(4)
Zona de batalla
75(15)
Bolos
83(13)
79(26)
Fugarse
48(18) C. Dominio
99(28) Ataque demoníaco
enduro
20(3)
50(15)
autopista
53(13) Ardilla de tierra
62(14) HÉROE.
39(14)
64(21) krüll
44(5) La venganza de M
95(19) Nombra este juego
20(10)
Detective privado
99(46) Incursión al río
74(27) Robotank
60(15)
35(15)
95(27)
42(12) Venture
55(13) Wizard of Wor
68(16)

Space Invader
Tennis
Tutankham

James Bond

132(6)
77(5)
39(4)
15(2)
300(4)
6(3)
49(4)
19(3)
24(3)
18(4)
4(2)
96(5)
41(4)
62(4)
403(2)
93(3)
71(7)
7(3)
42(2)
68(4)
3(2)
36(2)
77(6)
23(4)

1066
739
939
191
927
158
464
311
381
296
156
979
973
376
722
361
761
286
252
624
71
464
1262
433

87(23)
73(20)
64(22)
24(6)
100(26)
8(6)
54(15)
26(8)
37(10)
26(11)
8(5)
75(24)
59(22)
58(10)
100(22)
77(13)
64(17)
15(9)
47(8)
65(17)
5(3)
58(14)
74(23)
36(12)

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

/

/

mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d

yo

F
/

/

/

/

2
6
3
3
4
7
1
5
5
2
3
7
5
mi
v
C
oh
_
a
_
0
0
2
3
2
pag
d

/

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

parámetros, TPG is capable of discovering emergent representations appropriate for
each task.

7 Multitask Learning

Up to this point we have demonstrated the ability of TPG to build strong single-task
decision-making policies, where a unique policy graph was trained from scratch for
each Atari game title. This section reports on TPG’s ability to learn multiple tasks si-
multaneously, or multitask reinforcement learning (MTL). MTRL operates with the
same state representation as single-task learning. Eso es, state variables consist of raw
screen capture with no additional information regarding which game is currently being
played. Además, the full Atari action set is available to agents at all times.

When the TPG population is trained on multiple Atari games simultaneously, a
Una sola ejecución puede producir múltiples políticas campeonas., uno para cada título de juego, ese partido
o exceder el nivel de juego reportado para DQN. En algunos casos, una política multitarea (es decir., a
gráfico de política único capaz de reproducir múltiples títulos) También surge que juega todos los juegos.

368

Volumen de cálculo evolutivo 26, Número 3

Aprendizaje por refuerzo emergente multitarea de alta dimensión

Mesa 4: Grupos de tareas utilizados en experimentos de aprendizaje por refuerzo multitarea. cada grupo
Representa un conjunto de juegos que se aprenden simultáneamente. (mira la sección 7.1).

3-Grupos de títulos

Juego

5-Grupos de títulos

3.1

3.2

3.3

3.4

3.5

Extranjero
asteroides
Atraco a un banco
Zona de batalla
Bolos
Ciempiés
Comando de helicóptero
Derbi de pesca
Congelación
Canguro
krüll
Maestro de Kung Fu
EM. Pac-Man
Detective privado
Piloto del tiempo

5.1

5.2

5.3

a nivel de DQN. Además, el costo de capacitación para TPG bajo MTRL no es mayor
que el aprendizaje por tareas específicas, y la complejidad de las políticas de TPG multitarea campeonas es
todavía significativamente menos que las soluciones de aprendizaje profundo para tareas específicas.

7.1

Grupos de tareas

Si bien es posible categorizar los juegos de Atari a mano para admitir juegos incrementales
aprendiendo (Braylan et al., 2015), No se hizo ningún intento aquí de organizar grupos de juego basados
sobre la similitud percibida o la compatibilidad multitarea. Tal proceso sería laborioso en-
tenso y potencialmente engañoso, ya que cada título de juego de Atari define su propio diseño gráfico.
ambiente, combinación de colores, física, objetivo(s), y esquema de puntuación. Además,
Las acciones del joystick no están necesariamente correlacionadas entre los títulos de los juegos.. Por ejemplo, el
La posición del joystick “abajo” generalmente hace que el avatar se mueva verticalmente hacia abajo en la pantalla.
en juegos de laberintos (p.ej., EM. Pac-Man, Extranjero), pero podría interpretarse como "pull-up" en mosca-
juegos de ing (Zaxxón), o incluso hacer que el avatar de una nave espacial entre en el hiperespacio, desapareciendo
y reapareciendo en una ubicación aleatoria de la pantalla (asteroides).

Para investigar la capacidad de TPG para aprender múltiples títulos de juegos Atari simultáneamente-
iosamente, una variedad de grupos de tareas, eso es, títulos de juegos específicos para aprender simultáneamente-
iosamente, se crean a partir del conjunto de juegos para los cuales se realizaron ejecuciones de TPG de una sola tarea
Bueno. Relative to the four comparison algorithms which use a screen capture state rep-
resentimiento, TPG achieved the best reported test score in 15 del 49 Títulos de juegos de Atari
consideró (Mesa 7, Apéndice A). De este modo, task groupings for MTRL can be created in an
unbiased way by partitioning the list of 15 titles in alphabetical order. Específicamente, Mesa
4 identifies 5 groups of 3 games each, y 3 groups of 5 games each.

7.2

Task Switching

As in single-task learning, each policy is evaluated in 5 episodes per generation. Cómo-
alguna vez, under MTRL, new policies are first evaluated in one episode under each game title
in the current task group. Después de eso, the game title for each training episode is selected

Volumen de cálculo evolutivo 26, Número 3

369

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

/

/

mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d

yo

F
/

/

/

/

2
6
3
3
4
7
1
5
5
2
3
7
5
mi
v
C
oh
_
a
_
0
0
2
3
2
pag
d

/

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

S. kelly y m. I. heywood

with uniform probability from the set of titles in the task group. The maximum training
episodes for each policy is 5 episodes under each game title. For each consecutive block
de 10 generaciones, one title is selected with uniform probability to be the active title for
which selective pressure is applied. De este modo, while a policy may store the final score from
hasta 5 training episodes for each title, fitness at any given generation is the average
score over up to 5 episodes in the active title only. De este modo, selective pressure is explicitly
applied only relative to a single game title. Sin embargo, stochastically switching the active
title at regular intervals throughout evolution implies that a policy’s long-term survival
is dependent on a level of competence in all games.

7.3

Elitism

There is no multiobjective fitness component in the formulation of MTRL proposed
in this work. Sin embargo, a simple form of elitism is used to ensure the population as
a whole never entirely forgets any individual game title. Tal como, the single policy with
the best average score in each title is protected from deletion, regardless of which ti-
tle is currently active for selection. Tenga en cuenta que esta forma simple de elitismo no favorece-
proteger políticas multitarea, que puede no tener la puntuación más alta para ninguna tarea, pero
Son capaces de desempeñarse relativamente bien en múltiples tareas.. No proteger la política multitarea-
Las condiciones se volvieron problemáticas bajo la metodología de nuestro primer estudio MTRL. (kelly y
heywood, 2017b). De este modo, En este trabajo se emplea una forma simple de elitismo multitarea..
El equipo multitarea de élite se identifica en cada generación mediante los siguientes dos pasos
procedimiento:

1. Normalizar la puntuación media de cada política en cada tarea en relación con el resto de la actual-
población de alquiler. Puntuación normalizada para el equipo tmi en la tarea tj , o scn(tmi, tj ), es cal-
calculado como (Carolina del Sur(tmi, tj ) − scmin(tj ))/(scmax (tj ) − scmin(tj )), donde sc(tmi, tj ) es el
puntuación media del equipo tmi en la tarea tj y scmin,máximo (tj ) son los mínimos de toda la población
y puntuaciones medias máximas para la tarea tj .

2. Identifique la política de élite multitarea como aquella con el mínimo normal más alto.-
puntuación izada en todas las tareas. En relación con todos los equipos raíz de la población actual, R,
el equipo multitarea de élite se identifica como tmi ∈ R | ∀tmk ∈ R : mín.(scn(tmi, t{1..norte}) >
mín.(scn(gracias, t{1..norte}), donde min(scn(tmi, t{1..norte}) es la puntuación mínima normalizada
para el equipo tmi sobre todas las tareas en el grupo de juego y n denota el número de títulos
en el grupo.

De este modo, en cada generación, el elitismo identifica 1 equipo campeón para cada título de juego y 1
campeón multitarea, donde los equipos de élite están protegidos contra la eliminación en esa generación.

7.4

Parametrización

La parametrización utilizada para TPG en el aprendizaje por refuerzo multitarea es idéntica
a lo descrito en la tabla 1 con la excepción del parámetro Rsize, o el número de raíz
equipos a mantener en la población. Bajo MTRL, el tamaño de la población se redujo
a 90 (1/4 of the size used under single-task learning) in order to speed up evolution
and allow more task switching cycles to occur throughout the given training period.14
Un total de 5 independent runs were conducted for each task group in Table 4. Multitask
elite teams represent the champions from each run at any point during development.

14As under single-task experiments, the computational limit for MTRL is defined in terms of a com-
putational time constraint. Experiments ran on a shared cluster with a maximum runtime of 1 week
per run.

370

Volumen de cálculo evolutivo 26, Número 3

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

/

/

mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d

yo

F
/

/

/

/

2
6
3
3
4
7
1
5
5
2
3
7
5
mi
v
C
oh
_
a
_
0
0
2
3
2
pag
d

.

/

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Aprendizaje por refuerzo emergente multitarea de alta dimensión

Mesa 5: Summary of multitask learning results over all task groups. MT and ST report
test scores for the single best multitask (MONTE) and single-task (ST) policy for each game
group over all 5 independent runs. Scores that match or exceed the test score reported
for DQN in Mnih et al. (2015) are highlighted in grey (the MT score for Krull in group
5.3 es 90% of DQN’s score, and is considered a match).

MONTE

ST

Group

Juego

Group

MONTE

ST

864
2176
1085
36166
197
13431.2
3173.3
−66.6
2900.7
11200
4921.3
25600
3067.7
14665
7846.7

1494.3
2151
1085
37100
197
22374.6
3266.7
−38.4
4216
10940
17846.7
42480
3164.7
14734.7
8193.3

3.1

3.2

3.3

3.4

3.5

Extranjero
asteroides
Atraco a un banco
Zona de batalla
Bolos
Ciempiés
Comando de helicóptero
Derbi de pesca
Congelación
Canguro
krüll
Maestro de Kung Fu
EM. Pac-Man
Detective privado
Piloto del tiempo

5.1

5.2

5.3

346.7
1707
724
11800
107
9256.9
1450
24.967
2087.3
11200
3644.3
25393.3
3312.3
4000
7270

759
2181.3
724
30466.7
212
20480.2
2716.7
27.7
4283.3
11893.3
6099.7
34273.3
3430
15000
8570

Post training, the final champions from each run are subject to the same test procedure
as identified in Section 4 for each game title.

7.5 MTRL Performance

Cifra 8 reports the MTRL training and test performance for TPG relative to game group
5.3, where all TPG scores are normalized relative to scores reported for DQN in Mnih
et al. (2015). By generation ≈750, the best multitask policy is able to play all 5 títulos de juegos
at the level reported for DQN.15 Under test, the multitask champion (es decir., a single policy
that plays all game titles at a high level) exceeds DQN in 4 del 5 juegos, while reaching
encima 90% of DQN’s score in the remaining title (krüll) (Figure 8b). Note that in the case
of task group 5.3, only one run produced a multitask policy capable of matching DQN
in all 5 tareas.

Si bien el enfoque principal de MTRL es producir políticas multitarea, un subproducto de
la metodología empleada aquí (es decir., Cambio de tareas y elitismo en lugar de multiobjetos.-
métodos tivos) es que cada ejecución también produce políticas de tarea única de alta calidad (es decir., poli-
cies que sobresalen en un título de juego). Resultados de las pruebas para estos especialistas en juegos específicos, cual
son simplemente los 5 Políticas de élite de tarea única al final de la evolución., se informa en la figura
8C. Si bien no es tan competente como las políticas capacitadas en una sola tarea (Sección 5.1), al menos uno
El campeón de tarea única emerge de MTRL en el grupo de tareas. 5.3 que iguala o supera
la puntuación de DQN en cada título de juego.

Mesa 5 proporciona una descripción general resumida de los puntajes de las pruebas para el campeón multitarea
y política de tarea única relativa a cada grupo de juegos. Puntajes de exámenes que igualan o superan

15Tenga en cuenta que los puntajes de entrenamiento informados para TPG en la Figura 8a se promedian a partir de un máximo de 5 episodios en

cada título de juego, y por lo tanto no son tan sólidos como los puntajes de las pruebas reportados en la Figura 8b.

Volumen de cálculo evolutivo 26, Número 3

371

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

/

/

mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d

yo

F
/

/

/

/

2
6
3
3
4
7
1
5
5
2
3
7
5
mi
v
C
oh
_
a
_
0
0
2
3
2
pag
d

.

/

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

S. kelly y m. I. heywood

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

/

/

mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d

yo

F
/

/

/

/

2
6
3
3
4
7
1
5
5
2
3
7
5
mi
v
C
oh
_
a
_
0
0
2
3
2
pag
d

/

.

Cifra 8: Resultados de aprendizaje por refuerzo multitarea de TPG para grupos de juegos 5.3. cada carrera
identifica una política multitarea de élite por generación. El rendimiento formativo de este
La política relativa a cada título de juego se traza en (a), donde cada curva representa la media
Puntuación en cada título de juego para la mejor política multitarea de todas. 5 independent runs.
Tenga en cuenta que la multitarea implica que las puntuaciones reportadas en cada generación provienen todas de la
misma politica. Puntajes de las pruebas para el campeón final multitarea de cada uno de 5 se trazan carreras
en (b), con el mejor en negro. Puntajes de las pruebas para los campeones de tarea única de cada uno
ejecutar se trazan en (C). Tenga en cuenta que la tarea única implica que todas las puntuaciones provienen potencialmente de
diferentes políticas. Todas las puntuaciones de TPG están normalizadas en relación con la puntuación de DQN en el mismo
juego (100%) y un agente aleatorio (0%). Puntuaciones de entrenamiento en (a) representar la política
puntuación media sobre un máximo de 5 episodios en cada título. Puntajes de pruebas en (b) y (C) son los
puntuación media del juego superior 30 episodios de prueba en el título del juego dado. (La línea que conecta
puntos en (b) enfatiza que las puntuaciones provienen de la misma política multitarea.) Puntuaciones DQN
son de Mnih et al.. (2015).

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

los de DQN están resaltados en gris. Para los grupos de 3 títulos, TPG produjo multitarea
campeones capaces de jugar todos 3 títulos de juegos en grupos 3.2, 3.4, y 3.5, mientras que la
campeones multitarea aprendieron 2/3 títulos en grupo 3.1 y solo 1/3 títulos en grupo 3.3.

372

Volumen de cálculo evolutivo 26, Número 3

Aprendizaje por refuerzo emergente multitarea de alta dimensión

Para los grupos de 5 títulos, TPG produjo campeones multitarea capaces de jugar todo 5 de-
tulos en grupo 5.3, 4/5 títulos en grupo 5.2, y 3/5 títulos en grupo 5.1. Parece que extraterrestre
y Chopper Command son dos títulos de juegos que TPG tuvo dificultades para aprender bajo el
Metodología MTRL adoptada aquí (no surgieron políticas multitarea ni monotarea
para cualquier título de juego). Curiosamente, mientras que Fishing Derby fue difícil de aprender cuando
agrupado con Frostbite y Chopper Command (grupo 3.3), agregando 2 juego adicional
títulos del procedimiento de cambio de tarea (es decir., grupo 5.2) parece haber sido útil para
aprendiendo derbi de pesca. Tenga en cuenta que los puntajes de las pruebas de las políticas desarrolladas bajo el MTRL
La metodología generalmente no es tan alta como las puntuaciones obtenidas mediante el aprendizaje de una sola tarea.
para los mismos títulos de juegos (Sección 5.1). Esto se debe principalmente al desafío adicional de
aprender múltiples tareas simultáneamente. Sin embargo, es importante tener en cuenta que la población-
El tamaño de lación para los experimentos MTRL fue 1/4 del utilizado para experimentos de tarea única y
el presupuesto computacional para MTRL fue la mitad que el de los experimentos de tarea única. En efecto,
Los resultados de MTRL aquí representan una prueba de concepto de la capacidad multitarea de TPG en lugar de
que un estudio exhaustivo de todo su potencial.

7.6 Descomposición modular de tareas

La descomposición del problema tiene lugar en dos niveles en TPG.: (1) nivel de programa, en el cual
Los programas individuales dentro de un equipo definen cada uno un contexto único para implementar un único
acción; y (2) nivel de equipo, en el que los equipos individuales dentro de un gráfico de políticas definen cada uno
un complemento de programa único, y por lo tanto representan un mapeo único del estado
observación a la acción. Además, ya que cada programa normalmente indexa sólo una pequeña porción-
ción del espacio de estados, el mapeo resultante será sensible a una región específica de
el espacio de estados. Esta sección examina cómo la modularidad a nivel de equipo apoya la
development of multitask policies.

As TPG policy graphs develop, they will subsume an increasing number of stan-
dalone decision-making modules (equipos) into a hierarchical decision-making structure.
Recall from Section 3.2 that only root teams are subject to modification by variation op-
erators. De este modo, teams that are subsumed as interior nodes of a policy graph undergo no
modification. This property allows a policy graph to avoid (quickly) unlearning tasks
that were experienced in the past under task switching but are not currently the ac-
tive task. This represents an alternative approach to avoiding “catastrophic forgetting”
(Kirkpatrick et al., 2016) during the continual, sequential learning of multiple tasks. El
degree to which individual teams specialize relative to each objective experienced dur-
ing evolution (eso es, los títulos de juegos en un grupo de juegos en particular) se puede caracterizar
observando qué equipos contribuyen a la toma de decisiones al menos una vez durante las pruebas,
relativo a cada título de juego.

Cifra 9 muestra el gráfico de política de TPG multitarea campeón del grupo 3.2 experto-
mento. El diagrama de Venn indica qué equipos son visitados al menos una vez mientras se juega
cada juego, sobre todos los episodios de prueba. Naturalmente, El equipo raíz contribuye a cada decisión.
(Nodo marcado ABC en el gráfico, centro del diagrama de Venn). Cinco equipos contribuyen a
jugando bolos y ciempiés (Nodo marcado AB en el gráfico), mientras que el resto de
Los equipos se especializan para un título de juego específico. (Nodo marcado A en el gráfico). En breve,
Tanto los equipos generalistas como los especialistas aparecen dentro de la misma política y colectivamente de-
multar una política capaz de jugar múltiples títulos de juegos.

7.6.1 Complexity of Multitask Policy Graphs
Mesa 6 reports the average number of teams, instructions, and proportion of state space
contributing to each decision for the multitask champion during testing. Curiosamente,

Volumen de cálculo evolutivo 26, Número 3

373

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

/

/

mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d

yo

F
/

/

/

/

2
6
3
3
4
7
1
5
5
2
3
7
5
mi
v
C
oh
_
a
_
0
0
2
3
2
pag
d

.

/

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

S. kelly y m. I. heywood

Cifra 9: Champion multitask TPG policy graph from the group 3.2 experimento. De-
cision making in a policy graph begins at the root node (ABC) and follows one path
through the graph until an atomic action (joystick position) se alcanza (ver algoritmo
2). The Venn diagram indicates which teams are visited while playing each game, encima
all test episodes. Note that only graph nodes (teams and programs) that contributed to
decision making during test are shown.

Mesa 6: Complexity of champion multitask policy graphs from each game group in
which all tasks were covered by a single policy. The cost of making each decision is
relative to the average number of teams visited per decision (tm), average number of
instrucciones ejecutadas por decisión (Ins), y proporción de espacio de estados indexado por de-
decisión (%SP). El tiempo del reloj de pared TPG se mide en una CPU Intel Xeon E5-2650 de 2,2 GHz.

Group

Título

Tm Ins %SP Decisiones por segundo

3.2

3.4

3.5

5.3

Zona de batalla
Bolos
Ciempiés

Canguro
krüll
Maestro de Kung Fu

EM. Pac-Man
Detective privado
Piloto del tiempo

krüll
Maestro de Kung Fu
EM. Pac-Man
Detective privado
Piloto del tiempo

3
4
2

2
2
2

3
4
5

5
2
5
3
4

413
499
595

200
394
512

532
804
869

782
455
673
481
657

11
15
15

6
11
12

14
18
19

18
13
16
13
16

2687
2922
2592

3141
2502
2551

2070
1857
1982

1832
2342
1989
2192
2306

374

Volumen de cálculo evolutivo 26, Número 3

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

/

/

mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d

yo

F
/

/

/

/

2
6
3
3
4
7
1
5
5
2
3
7
5
mi
v
C
oh
_
a
_
0
0
2
3
2
pag
d

/

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Aprendizaje por refuerzo emergente multitarea de alta dimensión

incluso para un gráfico de políticas multitarea evolucionado (es decir., post-entrenamiento), el número de instrucciones-
Las operaciones ejecutadas dependen del juego en juego., Por ejemplo, que van desde 200 en canguro
a 512 en Maestro de Kung-Fu para el Grupo 3.4 campeón. Si bien la complejidad/costo de
La toma de decisiones varía dependiendo del juego en juego., el número promedio de instrucciones-
ciones por decisión para el grupo 5.3 campeón es 610, no significativamente diferente de
el promedio de 602 requerido por políticas específicas de tareas al jugar los mismos juegos (ver
Mesa 3). Además, el grupo 5.3 La política multitarea defensora promedió entre 1832 y 2342 años.-
decisiones por segundo durante la prueba, que es significativamente más rápido que las políticas de tarea única
tanto de DQN como de Blob-PROST (ver tabla 2). Finalmente, as the parameterization for TPG
under MTRL is identical to task-specific experiments with a significantly smaller popu-
lation size (90 vs. 360), and the number of generations is similar in both cases,16 podemos
conclude that the cost of development is not significantly greater under MTRL.

8 Conclusión

Applying RL directly to high-dimensional decision-making tasks has previously been
demonstrated using both neuro-evolution and multiple deep learning architectures.
para hacerlo, neuro-evolution assumed an a priori parameterization for model complex-
ity whereas deep learning had the entire architecture pre-specified. Además, evolving
the deep learning architectures only optimizes the topology. The convolution operation
central to providing the encoded representation remains, and it is this operation that
results in the computational overhead of deep learning architectures. En este trabajo, un
entirely emergent approach to evolution, o gráficos de programas enredados, is proposed in
which solution topology, state space indexing, and the types of action actually utilized
are all evolved in an open ended manner.

We demonstrate that TPG is able to evolve solutions to a suite of 49 Títulos de juegos de Atari
that generally match the quality of those discovered by deep learning at a fraction of the
complejidad del modelo. para hacerlo, TPG begins with single teams of programs and incremen-
tally discovers a graph of interconnectivity, potentially linking hundreds of teams by the
time competitive solutions are found. Sin embargo, as each team can only have one action
(per state), very few of the teams composing a TPG solution are evaluated in order to
make each decision. This provides the basis for efficient real-time operation without re-
course to specialized computing hardware. We also demonstrate a simple methodology
for multitask learning with the TPG representation, in which the champion agent can
play multiple games titles from direct screen capture, all at the level of deep learning,
without incurring any additional training cost or solution complexity.

Future work is likely to continue investigating MTRL under increasingly high-
dimensional task environments. One promising development is that TPG seems to be
capable of policy discovery in VizDoom and ALE directly from the frame buffer (es decir.,
without the quantization procedure in Section 4.1) (p.ej., Kelly y col., 2018; Smith and
heywood, 2018). dicho eso, there are many more open issues, such as finding the rel-
evant diversity mechanisms for tasks such as Montezuma’s Revenge and providing
efficient memory mechanisms that would enable agents to extend beyond the reactive
models they presently assume.

16MTRL runs lasted 200–750 generations, which is roughly the range of generations reached for the

single-task runs (see Figure 4a).

Volumen de cálculo evolutivo 26, Número 3

375

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

/

/

mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d

yo

F
/

/

/

/

2
6
3
3
4
7
1
5
5
2
3
7
5
mi
v
C
oh
_
a
_
0
0
2
3
2
pag
d

/

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

S. kelly y m. I. heywood

Expresiones de gratitud

S. Kelly gratefully acknowledges support from the Nova Scotia Graduate Scholarship
programa. METRO. Heywood gratefully acknowledges support from the NSERC Discovery
programa. All runs were completed on cloud computing infrastructure provided by
ACENET, the regional computing consortium for universities in Atlantic Canada. El
TPG code base is not in any way parallel, but in adopting ACENET the five independent
runs for each of the 49 games were conducted in parallel.

Referencias

Bellamare, METRO. GRAMO., Limpiar, y., Venecia, J., and Bowling, METRO. (2012a). The arcade learning environ-
mento: An evaluation platform for general agents. Journal of Artificial Intelligence Research,
47:253–279.

Bellamare, METRO. GRAMO., Venecia, J., and Bowling, METRO. (2012b). Investigating contingency awareness us-
ing Atari 2600 juegos. In Proceedings of the AAAI Conference on Artificial Intelligence, páginas. 864–
871.

Brameier, METRO., and Banzhaf, W.. (2001). Evolving teams of predictors with linear genetic program-

ming. Genetic Programming and Evolvable Machines, 2(4):381–407.

Brameier, METRO., and Banzhaf, W.. (2007). Linear genetic programming. 1st ed. Nueva York: Saltador.

Braylan, A., Hollenbeck, METRO., Meyerson, MI., and Miikkulainen, R. (2015). Reuse of neural modules

for general video game playing. Retrieved from arXiv:1512.01537.

Demšar, j. (2006). Statistical comparisons of classifiers over multiple data sets. Journal of Machine

Investigación del aprendizaje, 7(1):1–30.

Doucette, j. A., Lichodzijewski, PAG., and Heywood, METRO. I. (2012). Hierarchical task decomposition
through symbiosis in reinforcement learning. In Proceedings of the ACM Genetic and Evolu-
tionary Computation Conference, páginas. 97–104.

Hausknecht, METRO., Lehman, J., Miikkulainen, r., and Stone, PAG. (2014). A neuroevolution approach to
general Atari game playing. IEEE Transactions on Computational Intelligence and AI in Games,
6(4):355–366.

Hausknecht, METRO., and Stone, PAG. (2015). The impact of determinism on learning Atari 2600 juegos.

In AAAI Workshop on Learning for General Competency in Video Games.

Imamura, K., Soule, T., Heckendorn, R. B., and Foster, j. A. (2003). Behavioural diversity and
probabilistically optimal GP ensemble. Genetic Programming and Evolvable Machines, 4(3):235–
254.

Japkowicz, NORTE., and Shah, METRO. (2011). Evaluating learning algorithms. Cambridge: Cambridge Uni-

versity Press.

Kelly, S., and Heywood, METRO. I. (2014a). Genotypic versus behavioural diversity for teams of pro-
grams under the 4-v-3 keepaway soccer task. In Proceedings of the AAAI Conference on Artificial
Inteligencia, páginas. 3110–3111.

Kelly, S., and Heywood, METRO. I. (2014b). On diversity, teaming, and hierarchical policies: Obser-
vations from the keepaway soccer task. In European Conference on Genetic Programming, páginas.
75–86. Lecture Notes in Computer Science, volumen. 8599.

Kelly, S., and Heywood, METRO. I. (2017a). Emergent tangled graph representations for Atari game
playing agents. In European Conference on Genetic Programming, páginas. 64–79. Lecture Notes in
Computer Science, volumen. 10196.

376

Volumen de cálculo evolutivo 26, Número 3

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

/

/

mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d

yo

F
/

/

/

/

2
6
3
3
4
7
1
5
5
2
3
7
5
mi
v
C
oh
_
a
_
0
0
2
3
2
pag
d

.

/

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Aprendizaje por refuerzo emergente multitarea de alta dimensión

Kelly, S., and Heywood, METRO. I. (2017b). Multi-task learning in Atari video games with emergent
tangled program graphs. In Proceedings of the Genetic and Evolutionary Computation Conference,
páginas. 195–202.

Kelly, S., Lichodzijewski, PAG., and Heywood, METRO. I. (2012). On run time libraries and hierarchical

symbiosis. In IEEE Congress on Evolutionary Computation, páginas. 3245–3252.

Kelly, S., Herrero, r., and Heywood, METRO. I. (2018). Emergent policy discovery for visual reinforce-
ment learning through tangled program graphs: A tutorial. In Genetic programming theory
and practice XVI. Nueva York: Saltador.

Kirkpatrick, J., Pascanu, r., Rabinowitz, NORTE., Venecia, J., Desjardins, GRAMO., Rusu, A. A., Milan, K.,
Quan, J., Ramalho, T., Grabska-Barwinska, A., Hassabis, D., Clopata, C., Kumaran, D., y
Hadsell, R. (2016). Overcoming catastrophic forgetting in neural networks. Retrieved from
arXiv:1612.00796.

Kober, J., and Peters, j. (2012). Reinforcement learning in robotics: A survey. En m. Wiering and

METRO. van Otterio (Editores.), Aprendizaje reforzado, páginas. 579–610. Nueva York: Saltador.

Lehman, J., and Stanley, k. oh. (2011). Abandoning objectives: Evolution through the search for

novelty alone. Computación evolutiva, 19(2):189–223.

Liang, y., Machado, METRO. C., Talvitie, MI., and Bowling, METRO. (2016). State of the art control of Atari
games using shallow reinforcement learning. In Proceedings of the ACM International Confer-
ence on Autonomous Agents and Multiagent Systems, páginas. 485–493.

Lichodzijewski, PAG., and Heywood, METRO. I. (2008a). Coevolutionary bid-based genetic programming
for problem decomposition in classification. Genetic Programming and Evolvable Machines,
9:331–365.

Lichodzijewski, PAG., and Heywood, METRO. I. (2008b). Managing team-based problem solving with sym-
biotic bid-based genetic programming. In Proceedings of the ACM Genetic and Evolutionary
Computation Conference, páginas. 863–870.

Lichodzijewski, PAG., and Heywood, METRO. I. (2010). Symbiosis, complexification and simplicity un-
der GP. In Proceedings of the ACM Genetic and Evolutionary Computation Conference, páginas. 853–
860.

Lichodzijewski, PAG., and Heywood, METRO. I. (2011). The Rubik cube and GP temporal sequence learn-
En g: An initial study. In Genetic programming theory and practice VIII, capítulo 3, páginas. 35–54.
Nueva York: Saltador.

Mnih, v., Badia, A. PAG., Mirza, METRO., Tumbas, A., Harley, T., Lillicrap, t. PAG., Silver, D., and Kavukcuoglu,
k. (2016). Asynchronous methods for deep reinforcement learning. In Proceedings of the 33rd
International Conference on Machine Learning, páginas. 1928–1937.

Mnih, v., Kavukcuoglu, K., Silver, D., Rusu, A. A., Venecia, J., Bellamare, METRO. GRAMO., Tumbas, A., Ried-
miller, METRO., Fidjeland, A. K., Ostrovski, GRAMO., Petersen, S., Beattie, C., Sadik, A., Antonoglou, I.,
Rey, h., Kumaran, D., Wierstra, D., Legg, S., and Hassabis, D. (2015). Human-level control
through deep reinforcement learning. Naturaleza, 518(7540):529–533.

Nair, A., Srinivasan, PAG., Blackwell, S., Alcicek, C., Fearon, r., de Maria, A., Panneershelvam, v.,
Suleyman, METRO., Beattie, C., Petersen, S., Legg, S., Mnih, v., Kavukcuoglu, K., and Silver, D.
(2015). Massively parallel methods for deep reinforcement learning. In International Confer-
ence on Machine Learning—Deep Learning Workshop.

Nolfi, S. (1997). Using emergent modularity to develop control systems for mobile robots. Adaptado

Comportamiento, 5(3–4):343–363.

parisotto, MI., Ba, l. J., and Salakhutdinov, R. (2015). Actor-mimic: Deep multitask and transfer

aprendizaje reforzado. Retrieved from arXiv:1511.06342.

Volumen de cálculo evolutivo 26, Número 3

377

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

/

/

mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d

yo

F
/

/

/

/

2
6
3
3
4
7
1
5
5
2
3
7
5
mi
v
C
oh
_
a
_
0
0
2
3
2
pag
d

.

/

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

S. kelly y m. I. heywood

Pepels, T., and Winands, METRO. h. METRO. (2012). Enhancements for Monte-Carlo tree search in Ms Pac-

Man. In IEEE Symposium on Computational Intelligence in Games, páginas. 265–272.

Schrum, J., and Miikkulainen, R. (2016). Discovering multimodal behavior in Ms. Pac-Man
through evolution of modular neural networks. IEEE Transactions on Computational Intelli-
gence and AI in Games, 8(1):67–81.

Herrero, R. J., and Heywood, METRO. I. (2018). Scaling tangled program graphs to visual reinforcement
learning in Vizdoom. In European Conference on Genetic Programming, páginas. 135–150. Lecture
Notes in Computer Science, volumen. 10781.

Tamiz, I. (2012). Reinforcement learning in games. En m. Wiering and M. van Otterio (Editores.), Rein-

forcement learning, páginas. 539–577. Nueva York: Saltador.

Thomason, r., and Soule, t. (2007). Novel ways of improving cooperation and performance in en-
semble classifiers. In Proceedings of the ACM Genetic and Evolutionary Computation Conference,
páginas. 1708–1715.

van Hasselt, h., Guez, A., and Silver, D. (2016). Deep reinforcement learning with double Q-
aprendiendo. In Proceedings of the AAAI Conference on Artificial Intelligence, páginas. 2094–2100.

Wu, S., and Banzhaf, W.. (2011). Rethinking multilevel selection in genetic programming. En profesional-

ceedings of the ACM Genetic and Evolutionary Computation Conference, páginas. 1403–1410.

Apéndice A: Comparator Tables

Test performance over all 49 game titles is split between two comparator groups (Sección
5.1), those assuming screen capture state information (ver tabla 7) and those assuming
hand-crafted state (ver tabla 8). TPG uses screen capture state in both cases.

Mesa 7: Average game score of best agent under test conditions for TPG along with
comparator algorithms in which screen capture represents state information. Numbers
in bold represent best score on each game title. Source information for comparitor al-
gorithms is as follows: DQN (Mnih et al., 2015), Gorila (Nair et al., 2015), Double DQN
(van Hasselt et al., 2016), and Hyper-NEAT (Hausknecht y la piedra, 2015).

Juego

TPG

DQN

Gorila

Double DQN

Hyper-NEAT

Extranjero
Medir
Agresión
Astérix
asteroides
Atlántida
Atraco a un banco
Zona de batalla
Jinete de haz
Bolos
Boxeo
Fugarse
Ciempiés
C. Dominio
Escalador loco
Ataque demoníaco

3,382.7
398.4
2,422
2,400
3,050.7
89,653
1,051
47,233.4
1,320.8
223.7
76.5
12.8
34,731.7
7,070
8,367
2,920.4

3,069.3
739.5
3,359.6
6,011.7
1,629.3
85,950
429.7
26,300
6,845.9
42.4
71.8
401.2
8,309.4
6,686.7
114,103.3
9,711.2

2,621.53
1,189.7
1,450.4
6,433.3
1,047.7
100,069
609
25,266.7
3,302.9
54
94.9
402.2
8,432.3
4,167.5
85,919.1
13,693.1

2,907.3
702.1
5,022.9
15,150
930.3
64,758
728.3
25,730
7,654
70.5
81.7
375
4,139.4
4,653
101,874
9,711.9

1,586
184.4
912.6
2,340
1,694
61,260
214
36,200
1,412.8
135.8
16.4
2.8
25,275.2
3,960
0
3,590

378

Volumen de cálculo evolutivo 26, Número 3

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

/

/

mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d

yo

F
/

/

/

/

2
6
3
3
4
7
1
5
5
2
3
7
5
mi
v
C
oh
_
a
_
0
0
2
3
2
pag
d

/

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Aprendizaje por refuerzo emergente multitarea de alta dimensión

Juego

TPG

DQN

Gorila

Double DQN

Hyper-NEAT

Mesa 7: Continuado.

Doble mate
enduro
Derbi de pesca
autopista
Congelación
Ardilla de tierra
gravitar
HÉROE.
Hockey sobre hielo
James Bond
Canguro
krüll
Maestro de Kung Fu
La venganza de M
EM. Pac-Man
Nombra este juego
Apestar
Detective privado
Q*Berto
Incursión al río
Correcaminos
Robotank
Búsqueda del mar
Space Invader
Artillero estelar
Tennis
Piloto del tiempo
Tutankham
Arriba y abajo
Venture
Vídeo pinball
Wizard of Wor
Zaxxón
Avg. Rango (Ri)

2
125.9
49
28.9
8,144.4
581.4
786.7
16,545.4
10
3,120
14,780
12,850.4
43,353.4
0
5,156
3,712
6
15,028.3
2,245
3,884.7
27,410
22.9
1,368
1,597.2
1,406.7
0
13,540
128
34,416
576.7
37,954.4
5,196.7
6,233.4
2.74

−18.1
301.8
−0.8
30.3
328.3
8,520
306.7
19,950.3
−1.6
576.7
6,740
3,804.7
23,270
0
2,311
7,256.7
18.9
1,787.6
10,595.8
8,315.7
18,256.7
51.6
5,286
1,975.5
57,996.7
−1.6
5,946.7
186.7
8,456.3
380
42,684.1
3,393.3
4,976.7
3.11

−10.6
114.9
20.2
11.7
605.2
5,279
1,054.6
14,913.9
−0.6
605
2,547.2
7,882
27,543.3
4.3
3,233.5
6,182.2
18.3
748.6
10,815.6
8,344.8
51,008
36.4
13,169.1
1,883.4
19,145
10.9
10,659.3
245
12,561.6
1,245
157,550.2
13,731.3
7,129.3
2.63

−6.3
319.5
20.3
31.8
241.5
8,215.4
170.5
20,357
−2.4
438
13,651
4,396.7
29,486
0
3,210
6,997.1
21
670.1
14,875
12,015
48,377
46.7
7,995
3,154
65,188
1.7
7,964
190.6
16,769.9
0
70,009
5,204
10,182
2.64

2
93.6
−49.8
29
2,260
364
370
5,090
10.6
5,660
800
12,601.4
7,720
0
3,408
6,742
−17.4
10,747.4
695
2,616
3,220
43.8
716
1,251
2,720
0
7,340
23.6
43,734
1,188
0
3,360
3,000
3.87

Mesa 8: Average game score of best agent under test conditions for TPG (screen capture)
along with comparator algorithms based on prior object/feature identification. Numbers in
bold represent best score on each game title. Source information for comparitor algo-
rithms is as follows: Blob-PROST (Liang et al., 2016), Hyper-NEAT (Hausknecht and
Piedra, 2015), LIMPIO (Hausknecht y la piedra, 2015), and Conti-Sarsa (Mnih et al., 2015).

Juego

TPG

Blob-PROST

Hyper-NEAT

LIMPIO

Conti-Sarsa

Extranjero
Medir
Agresión
Astérix

3,382.7
398.4
2,422
2,400

4,886.6
825.6
1,829.3
2,965.5

2,246
218.8
2,396
2,550

4,320
325.2
2,717.2
1,490

103.2
183.6
537
1,332

Volumen de cálculo evolutivo 26, Número 3

379

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

/

/

mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d

yo

F
/

/

/

/

2
6
3
3
4
7
1
5
5
2
3
7
5
mi
v
C
oh
_
a
_
0
0
2
3
2
pag
d

/

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

S. kelly y m. I. heywood

Juego

TPG

Blob-PROST

Hyper-NEAT

LIMPIO

Conti-Sarsa

Mesa 8: Continuado.

asteroides
Atlántida
Atraco a un banco
Zona de batalla
Jinete de haz
Bolos
Boxeo
Fugarse
Ciempiés
C. Dominio
Escalador loco
Ataque demoníaco
Doble mate
enduro
Derbi de pesca
autopista
Congelación
Ardilla de tierra
gravitar
HÉROE.
Hockey sobre hielo
James Bond
Canguro
krüll
Maestro de Kung Fu
La venganza de M
EM. Pac-Man
Nombra este juego
Apestar
Detective privado
Q*Berto
Incursión al río
Correcaminos
Robotank
Búsqueda del mar
Space Invader
Artillero estelar
Tennis
Piloto del tiempo
Tutankham
Arriba y abajo
Venture
Vídeo pinball
Wizard of Wor
Zaxxón
Avg. Rango (Ri)

3,050.7
89,653
1,051
47,233.4
1,320.8
223.7
76.5
12.8
34,731.7
7,070
8,367
2,920.4
2
125.9
49
28.9
8,144.4
581.4
786.7
16,545.4
10
3,120
14,780
12,850.4
43,353.4
0
5,156
3,712
6
15,028.3
2,245
3,884.7
27,410
22.9
1,368
1,597.2
1,406.7
0
13,540
128
34,416
576.7
3,794.4
5,196.7
6233.4
2.81

2,229.9
42,937.7
793.6
37,850
2,965.5
91.1
98.3
190.3
21,137
4,898.9
81,016
2,166
−4.1
299.1
−28.8
32.6
4,534
7,451.1
1,709.7
20,273.1
22.8
1,030.5
9,492.8
33,263.4
51,007.6
2,508.4
5,917.9
7,787
20.5
100.3
14,449.4
14,583.3
41,828
34.4
2,278
889.8
1,651.6
0
5,429.5
217.7
41,257.8
1,397
21,313
5,681.2
11,721.8
2.16

220
44,200
1,308
37,600
1,443.2
250.4
91.6
40.8
33,326.6
8,120
12,840
3,082
4
112.8
−37
29.6
2,226
6,252
1,990
3,638
9
12,730
4,880
23,890.2
47,820
0
3,830
8,346
4
15,045.2
810
4,736
14,420
42.4
2,508
1,481
4,160
0.2
15,640
110
6,818
400
82,646
3,760
4,680
2.81

4,144
126,260
380
45,000
1,900
231.6
92.8
43.6
22,469.6
4,580
25,060
3,464
10.8
133.8
−43.8
30.8
1,452
6,029
2,840
3,894
3.8
2,380
12,800
20,337.8
87,340
340
4,902
7,084
15.2
1,926.4
1,935
4,718
9,600
18
944
1,481
9,580
1.2
14,320
142.4
10,220
340
253,986
17,700
6,460
2.47

89
852.9
67.4
16.2
1,743
36.4
9.8
6.1
4,647
16.9
149.8
0
−16
159.4
−85.1
19.7
180.9
2,368
429
7,295
−3.2
354.1
8.8
3,341
29,151
259
1,227
2,247
−17.4
86
960.3
2,650
89.1
12.4
675.5
267.9
9.4
0
24.9
98.2
2,449
0.6
19,761
36.9
21.4
4.76

380

Volumen de cálculo evolutivo 26, Número 3

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

/

/

mi
d
tu
mi
v
C
oh
a
r
t
i
C
mi
–
pag
d

yo

F
/

/

/

/

2
6
3
3
4
7
1
5
5
2
3
7
5
mi
v
C
oh
_
a
_
0
0
2
3
2
pag
d

.

/

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

Descargar PDF