Machine PDF

Definición de Aprendizaje por Refuerzo
Procesos de Decisión de Markov

Aprendizaje por Refuerzo
Programación Dinámica
Aprendizaje Automático
Ingenierı́a Informática
Fernando Fernández Rebollo y Daniel Borrajo Millán
Grupo de Planificación y Aprendizaje (PLG)

Departamento de Informática
Escuela Politécnica Superior
Universidad Carlos III de Madrid
27 de febrero de 2009
Fernando Fernández y Daniel Borrajo Aprendizaje Automático

Aprendizaje Por Refuerzo
Generalización
Ejemplos de Aplicación
En Esta Sección:
10 Procesos de Decisión de Markov
Definición de Aprendizaje por Refuerzo
Definición de un MDP
Polı́ticas y Optimalidad
Programación Dinámica
11 Aprendizaje por Refuerzo
Aproximaciones Libres de Modelo
Métodos Basados en el Modelo
Representación de la función Q
Generalización en Aprendizaje por Refuerzo
Discretización del Espacio de Estados
Aproximación de Funciones
Generalización
Introducción
Problema de Aprendizaje por Refuerzo (definido como un

MDP):
Conjunto de todos los posibles
estados, S,
Entorno r
Conjunto de todas las posibles
T(s,a) s’
acciones, A, R(s,a)
a
Función de transición de estados
desconocida, s
Agente r
T :S ×A×S →< π (s)
Función de refuerzo desconocida,
R : S × A → <.
Objetivo: aprender la polı́tica de acción Π : S → A que
maximice el refuerzo medio esparado.
Generalización
Q-Learning (Watkins, 1989)
No se conocen las funciones de transición de estado ni de

refuerzo
Aprendizaje por prueba y error
Q-Learning (γ, α).

Inicializar Q(s, a), ∀s ∈ S, a ∈ A
Repetir (para cada episodio)
Inicializa el estado inicial, s, aleatoriamente.
Repetir (para cada paso del episodio)
Selecciona una acción a y ejecútala
Recibe el estado actual s 0 , y el refuerzo, r
Q(s, a) ← (1 − α)Q(s, a) + α[r + γ máxa0 Q(s 0 , a0 )]
Asigna s ← s 0
Devuelve Q(s, a)

Generalización
Funciones de Actualización
Función de actualización determinista:

Q(s, a) ← r + γ máxa0 Q(s 0 , a0 )
Función de actualización no determinista:
Q(s, a) ← (1 − α)Q(s, a) + α[r + γ máxa0 Q(s 0 , a0 )]

Generalización
Ejemplo
Suponer el siguiente MDP determinista
a1
s1 s2
a2
a1
a2 a3
s4
a2 s3 a3
Tabla Q Inicial:
Q(s,a) a1 a2 a3
s1 0 0 0
s2 0 0 0
s3 0 0 0
s4 0 0 0
Generalización
Ejemplo
El agente ejecuta el siguiente episodio o secuencia de

acciones: s1 →a1 s2 →a3 s3 →a3 s4
Actualizaciones en la tabla Q:
Q(s1 , a1 ) = R(s1 , a1 ) + γ arga máx Q(s2 , a) = 0 + γ0 = 0
Tabla Q resultante:
Q(s,a) a1 a2 a3
s1 0 0 0
s2 0 0 0
s3 0 0 1
s4 0 0 0

Generalización
Ejemplo
Segundo episodio de aprendizaje: s1 →a2 s3 →a2 s2 →a2 s4

Actualizaciones en la tabla Q:
Q(s1 , a2 ) = R(s1 , a2 ) + γ arga máx Q(s3 , a) =
0 + γ máx(0, 0, 1) = γ = 0,5
Tabla Q resultante:
Q(s,a) a1 a2 a3
s1 0 0,5 0
s2 0 1 0
s3 0 0 1
s4 0 0 0

Generalización
Ejemplo
Tabla Q óptima:
Q ∗ (s, a) a1 a2 a3
s1 0,5 0,5 0,25
s2 0,25 1 0,5
s3 0,5 0.5 1
s4 0 0 0
Polı́tica óptima:
π ∗ (s3 ) = arga máx Q(s3 , a) = a3
π ∗ (s2 ) = a2
π ∗ (s1 ) = a1
Otra polı́tica óptima: igual que la anterior pero con
π ∗ (s1 ) = a2

Generalización
Exploración vs. Explotación
Métodos de balancear la exploración/explotación

Estrategias de selección de acciones:
-greedy:
Ejecuta arga máx Q(s, a) con probabilidad
Ejecuta una acción aleatoria con probabilidad 1 −
Softmax:
e Q(s,ai )/τ
P(ai ) = P Q(s,aj )/τ
aj ∈A e
Inicialización de la función Q
Sesgar la selección de acciones con conocimiento del dominio
adicional

Generalización
Métodos Basados en el Modelo para Resolver MDP’s
Si no se conoce el modelo: aprenderlo

Ejemplo: Dyna-Q
Similar a Q-Learning
En cada paso, también actualiza su conocimiento del modelo
El modelo es utilizado para realizar nuevas actualizactiones de
Q

Generalización
Métodos Basados en el Modelo: Dyna-Q

Algoritmo Dyna-Q
Inicializar Q(s, a) y Modelo(s, a) arbitrariamente

Repetir para siempre
Inicializar s
Seleccionar una acción a a partir de s usando una polı́tica
derivada de Q
Q(s, a) ← Q(s, a) + α[r + γ máxa0 Q(s 0 , a0 ) − Q(s, a)]
Modelo(s, a) ← s 0 , r
s ← s0
Repetir N veces
s ← estado visitado anteriormente y elegido aleatoriamente
a ← acción aleatoria ejecutada anteriormente desde s
s 0 , r ←Modelo(s, a)
Q(s, a) ← Q(s, a) + α[r + γ máxa0 Q(s 0 , a0 ) − Q(s, a)]

Generalización
Representación Tabular de la Función Q
Actions {a 1 , ..., a L }
States
...
Problema: espacio de estados
{s 1 , ...,s N }
...
Q Table: continuo o de gran tamaño
Q(s,a) Solución: métodos de
s ... ... ... ...
generalización
Aproximaciones ad-hoc
...
Q(s,a L)
basadas en conocimiento del
...
...
Arg
dominio
... Max
ai
Discretización del espacio de
ai
Q(s,a 1 ) estados
Aproximación de funciones

Generalización
Discretización del Espacio de Estados
Actions
States
...
...
Q Table:
s ... ... ... ...
Q(D(s),a) Problema:
... ... ... ... Discretizaciones erróneas
pueden romper fácilmente la
...
State Space
Q(D(s), a1)
propiedad de Markov
Representation: ...
D(s) Cuántas regiones necesitamos
... Max
ai ai
para discretizar el espacio de
... estados?
Q(D(s), aL )

Generalización
Ejemplo
Dominio de navegación de un robot:

Espacio de estados continuo de tamaño 5 × 5
Acciones: Norte, Sur, Este, Oeste, de tamaño 1
0 1 2 3 4 5 0 1 2 3 4 5
5 5
Goal V=12.5 V=25 V=50 V=100 V=0

4 4
V=6.25 V=12.5 V=25 V=50 V=100

3 3
V=3.12 V=6.25 V=12.5 V=25 V=50

2 2
V=1.6 V=3.12 V=6.25 V=12.5 V=25

1 1
V=0.8 V=1.6 V=3.12 V=6.25 V=12.5

0 0
Discretización óptima de tamaño 5 × 5

Generalización
Pérdida de la Propiedad de Markov
0 1 2 3 4 5
0000
1111
1111
0000 Goal Area
5 0000
1111
0000
1111
0000
1111
0000
1111 Non−determinism Introduced:
0000
1111
0000
1111 Same action from same state
0000
1111
0000
1111
4 0000
1111 produces different immediate
rewards
3
Limits of the Regions
(6 x 6 discretization)
Value Function Limits

1

Generalización
Keepaway (Stone, Sutton and Kuhlmann, 05)

Generalización
Ejemplo: la Tarea Keepaway
Espacio de estados: 19 atributos continuos (Los keepers y los

takers se ordenan tomando en cuenta su distancia al jugador)
dist(k1 , C ), . . . , dist(k4 , C )
dist(t1 , C ), . . . , dist(t3 , C )
dist(k1 , t1 ), . . . , dist(k1 , t3 )
Min(dist(k2 , t1 ), dist(k2 , t2 ), dist(k2 , t3 ))
etc. . .
Espacio de estados discreto: 4 acciones
Mantener la pelota
Pasar a k2, Pasar a k3, Pasar a k4
Función de transición de estados desconocida
Función de refuerzo desconocida

Generalización
Discretización uniforme del espacio de estados

Discretizar cada atributo en un número dado de niveles de
discretización o regiones
En Keepaway:
d=5 niveles de discretización
f=19 atributos
d f = 1,907348e + 13 regiones/estados
Ejemplo para la caracterı́stica 2 (dist(k2 , C )):
25
Level 1
20
Level 2
15
dist(k2,C)
Level 3
10
Level 3
5
Level 5
0
0 1000 2000 3000 4000 5000 6000
example

Generalización
Regiones Generadas por la Discretización Uniforme
Proyección del espacio de estados sobre los atributos 2 y 3:

30
25
20
dist(k3,C)
15
10
0
0 5 10 15 20 25
dist(k2,C)

Generalización
CMAC (Albus, 81)
Superponer varias discretizaciones:

Tile #3
30
Tile #1
25
Tile #2
20
dist(k3,C)
15
10
0
0 5 10 15 20 25
dist(k2,C)
Cada celda mantiene su propia aproximación de la funcón Q:

Celda #i aproxima Qi (s, a)
Q(s, a) = f (Q1 (s, a), Q2 (s, a), Q3 (s, a))
Generalización
Discretización de Resolución Variable: Árboles KD (Munos

and Moore, 02)
Los nodos y hojas del árbol

...
representan regiones del ...
espacio de estados
En cada nodo del árbol, una
región se divide en dos:
Los criterios para partir un
nodo son diversos, y buscan 30
diferencias dentro de la 25
región: 20
dist(k3,C)
15
en la función de valor 10
en la polı́tica 5
... 0
0 5 10 15 20 25
dist(k2,C)

Generalización
Aproximación de Funciones
Utilizar un aproximador de funciones para representar la

función Q:
NN 1 NN 1
^ ^
Qa (s) Q(s, a 1)
1
a1
NN 2 NN 1
^ ^
Qa (s) Q(s, a )
2
2
a2
Arg a ai Arg a ai
s NN 3 i
s NN 1 i
Max Max
Q^ a (s) ^ a )
Q(s,
3
3
a3
... ... ... ... ... ... ... ... ... ...
... ... ... ... ... ... ... ... ... ...
NN L NN 1
Q^ a (s) ^
Q(s, a )
L L
aL
L aproximadores (Q̂ai (s)) 1 aproximador (Q̂(s, a))

Generalización
Batch Q-Learning (1/2)
Entradas:
1 Un espacio de estados X
2 Un conjunto de L acciones, A = {a1 , . . . , aL }
3 Una colección T de N tuplas de experiencia del tipo
< s, ai , s 0 , r >, donde s ∈ X es un estado desde donde la
acción ai es ejecutada y s 0 es el estado resultante

Generalización
Batch Q-Learning (2/2)
Sea Q̂ 0 (s, a) = 0
iter = 0
Repetir
Inicializar los conjuntos de aprendizaje T iter = ∅
Desde j=1 hasta N, utilizando la j ésima tupla < sj , aj , sj0 , rj >
hacer
cj = rj + máxa∈A γ Q̂ iter −1 (sj0 , a)
T iter = T iter ∪ {< sj , aj , cj >}
Entrenar Q̂ iter (s, a) para aproximar el conjunto de aprendizaje
T iter
iter = iter + 1
Hasta que el vector cj no cambie

Generalización
Generar Tuplas de Experiencia
0 1 2 3 4 5
5 s7 s9 s 12
s 13
s8
s 25
4
s5
s 11
s6 s 23
s 10
s24
3
s4
s 21
2 s 22
s2
s3
s 20
1
s1
T 0 ={(s 1 , norte, 0), (s2 , este, 0), (s3 , norte, 0), (s4 , norte, 0),
. . . , (s12 , este, rmax ), . . . , (s20 , norte, 0), (s21 , este, 0), . . . ,
(s24 , norte, rmax ), . . . }

Generalización
Batch Q-Learning: Iter. 1
Q 1 (s, a): Action "Go East" Action "Go West"

0 1 2 3 4 5 0 1 2 3 4 5
5 5
r max Goal Goal
(Q=0) (Q=0)
4 4
3 3
Q=0 Q=0
2 2
1 1
0 0
Action "Go North" Action "Go South"
0 1 2 3 4 5 0 1 2 3 4 5
5 5
Goal Goal
(Q=0) (Q=0)
4 4
r max
3 3
Q=0 Q=0
2 2
1 1
0 0

Generalización

0 1 2 3 4 5 0 1 2 3 4 5
5 5
r max Goal Goal
γ r max (Q=0) (Q=0)
4 4
γ r max
3 3
Q=0 Q=0
2 2
1 1
0 0
0 1 2 3 4 5 0 1 2 3 4 5
5 5
Goal Goal
(Q=0) (Q=0)
4 γ r 4
max
r max
3 3
Q=0 γ r max Q=0

2 2
1 1
0 0

Generalización

0 1 2 3 4 5 0 1 2 3 4 5
5 5
2 Goal Goal
γ rmax γ r max r max
(Q=0)
γ 2 rmax (Q=0)
4 4
2
γ rmax γ r max γ 2 rmax
3 3
2
γ rmax Q=0
2 2
Q=0
1 1
0 0
0 1 2 3 4 5 0 1 2 3 4 5
5 5
Goal Goal
γ 2 rmax (Q=0)
(Q=0)
γ rmax γ r max
4 2 4
r max γ 2 rmax
3 3
2
Q=0 γ rmax γ r max Q=0
2 2
2
γ rmax
1 1
0 0

Generalización
Ejecución de Batch Q-Learning: Iteración 9

0 1 2 3 4 5 0 1 2 3 4 5
5 5
3 2 r max Goal 3 2 Goal
γ rmax γ rmax γ r max (Q=0) γ rmax γ rmax γ rmax γ rmax (Q=0)
5 4
4 4
3 2
γ 4 rmax γ 3 r γ rmax
2
γ r max γ 6 rmax γ 5 rmax γ 4 rmax γ rmax γ rmax
max
3 3
3
γ rmax γ rmax γ rmax γ rmax γ rmax
6 5 4
γ rmax γ 4 rmax γ 3 rmax
5 2 7
γ rmax
2 2
γ 3 rmax 6 5 4
6 5 4 8 7
γ rmax γ rmax γ rmax
1 1
γ 7 rmax γ 6 rmax γ 5 rmax γ 4 rmax γ 9 rmax γ 8 r 7 γ 6 rmax γ 5 rmax

max γ rmax
0 0
0 1 2 3 4 5 0 1 2 3 4 5
5 5
Goal 3 2 Goal
γ 5 rmax γ 4 rmax γ rmax γ rmax (Q=0)
(Q=0)
γ 4 rmax γ rmax γ 2 rmax γ r max
4 3 4
3 2
γ 6 rmax γ rmax γ 4 rmax γ rmax γ rmax
r max 5
3 3
3
γ 7 rmax γ rmax γ rmax γ rmax γ rmax
2 6 5 4
4
γ rmax γ rmax γ 3 r
5 γ rmax γ r max
max
2 2
6 5 4
2 8 7
γ 6 rmax γ 5 rmax γ 4 rmax γ 3 r γ rmax
max
1 1
γ 9 rmax γ 8 r 7 γ 6 rmax γ 5 rmax

γ 7 rmax γ rmax γ rmax γ 4 r max γ rmax
6 5 3
max γ rmax
0 0

Generalización
Aprendizaje con Aproximación de Funciones

Problemas en la aplicación de aprendizaje supervisado en
aprendizaje por refuerzo:
Las etiquetas de los datos (valor Q) son desconocidos a priori
Los refuerzos positivos pueden ser escasos comparados con
refuerzos nulos (problema de clasificación de conjuntos no
balanceados)
Los distintos pasos del aprendizaje pueden tener distintas
caracterı́sticas de aprendizaje
Las estimaciones son calculadas sobre estimaciones:
propagación de errores:
Buena convergencia: se obtienen la función de valor y polı́tica
óptimas
Convergencia por casualidad: la función de valor calculada es
subóptima pero genera una polı́tica óptima
Mala convergencia: tanto la función de valor como la polı́tica
son subóptimas
Divergencia: no se converge ni a una función de valor ni a una
polı́tica
Generalización
TD-Gammon
Juego del backgammon
34 piezas y 24 posiciones posibles: espacio
de estados enorme!!!
20 posibles movimientos por cada tirada de
dado
Perfecto concimiento de espacios de estado,
acción, y transiciones de estado
Refuerzo cuando se gana la partida
V(s) evalua la probabilidad de ganar desde
el estado s
Uso de una red de neuronas para aproximar
V(s)
Aprendizaje mediante una versión no lineal
de TD(λ)
Aprendizaje de los pesos mediante descenso
de gradiente
Generalización
Problemas de control: Acrobot
Acrobot
Espacio de estados continuo: 2 ángulos y 2
velocidades
Goal
Espacio de acciones discreto: 2 acciones:
empujar el codo en una dirección y otra
Objetivo: colocar el brazo en posicion θ1
vertical invertida
Perfecto concimiento de espacios de estado,
Elbow
acción, y transiciones de estado
Diversas aproximaciones para
generalización: Variable Resolution θ2
Discretization, redes de neuronas, árboles
de decisión, etc.

Generalización
Módulo Pedagógico en Tutores Inteligentes
RLATES:
Estado: conocimiento que dispone el
alumno sobre el contenido del tutor Domain
Knowledge Browser
Acción: mostrar un contenido al Def11
Def
.....
Definición
Subtema 1.1
SubT
Defn1
........
Subtemas
T
.........
Def
E jemplos
Subtema 1.n
SubT
Tema 1
P ro blemas
.......................
........ T
Ejercicios
Ejer11 .....
........
Ejern
1
Tests
.....
.
Navegador
.
..... ... .... ..... ...
Client
1.n
Def11.1 ..... Def n1.1 T1 T n1.n
Student 1
I
alumno Domain
Module
Interface
Module
n
t .
Percepción realizada mediante tests e
r .
Objetivo: obtener una polı́tica
Student
Module
Pedagogical
Module
n
e
t
.
pedagógica Student
Knowledge
Student 1
Pedagogical
Knowledge
Class A
Browser
Navegador
Client
Simplificación a un espacio de
students Student n
Server
estados con caracterı́sticas binarias

Difı́cil percepción/modelización del
estado: POMDP

Generalización
Módulo Pedagógico en Tutores Inteligentes
Definition

Generalización
Otras Aplicaciones
Adaptive Cognitive Orthotics: Combining Reinforcement Learning and

Constraint-Based Temporal Reasoning by Matthew Rudary, Satinder Singh and
Martha Pollack. In Proceedings of the Twenty-First International Conference on
Machine Learning (ICML), pages 719-726, 2004.
Cobot: A Social Reinforcement Learning Agent by Charles Isbell, Christian
Shelton, Michael Kearns, Satinder Singh and Peter Stone. In Advances in Neural
Information Processing Systems 14 (NIPS) pages 1393-1400, 2002.
Empirical Evaluation of a Reinforcement Learning Spoken Dialogue System by
Satinder Singh, Michael Kearns, Diane Litman, and Marilyn Walker. In
Proceedings of the Seventeenth National Conference on Artificial Intelligence
(AAAI), pages 645-651, 2000
Mori, T., Nakamura, Y., Sato, M., and Ishii, S. (2004). Reinforcement learning
for CPG-driven biped robot. Nineteenth National Conference on Artificial
Intelligence (AAAI), pp.623-630.

Generalización
Resumen
Diferencias entre Programación Dinámica, métodos libres de

modelo y basados en el modelo
Planificación en Procesos de Decisión de Markov
Aprendizaje por Refuerzo:
Algoritmo Q-Learning
Importancia de la representación de los estados, las acciones y
las funciones de valor
Discretizaciones incorrectas pueden romper la propiedad de
Markov
Divergencia de los métodos de aproximación de las funciones
de valor

Generalización
Bibliografı́a
Machine Learning, Tom Mitchell. Capı́tulo 13.

Reinforcement Learning: An Introduction. Richard Sutton y
Andrew Barto. MIT Press. 1998
Reinforcement Learning Repository:
http://www-anw.cs.umass.edu/rlr/
Aprendizaje Automático: conceptos básicos y avanzados.
Basilio Sierra Araujo. Pearson Prentice Hall. 2006

Machine PDF

Cargado por

Copyright:

Formatos disponibles

Machine PDF

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Machine PDF

Cargado por

Copyright:

Formatos disponibles

Definición de Aprendizaje por Refuerzo

Procesos de Decisión de Markov

Aprendizaje por Refuerzo

Fernando Fernández Rebollo y Daniel Borrajo Millán

Grupo de Planificación y Aprendizaje (PLG)

Fernando Fernández y Daniel Borrajo Aprendizaje Automático

Problema de Aprendizaje por Refuerzo (definido como un

Q-Learning (Watkins, 1989)

No se conocen las funciones de transición de estado ni de

Q-Learning (γ, α).

Fernando Fernández y Daniel Borrajo Aprendizaje Automático

Función de actualización determinista:

Fernando Fernández y Daniel Borrajo Aprendizaje Automático

El agente ejecuta el siguiente episodio o secuencia de

Fernando Fernández y Daniel Borrajo Aprendizaje Automático

Segundo episodio de aprendizaje: s1 →a2 s3 →a2 s2 →a2 s4

Fernando Fernández y Daniel Borrajo Aprendizaje Automático

Fernando Fernández y Daniel Borrajo Aprendizaje Automático

Exploración vs. Explotación

Métodos de balancear la exploración/explotación

Fernando Fernández y Daniel Borrajo Aprendizaje Automático

Métodos Basados en el Modelo para Resolver MDP’s

Si no se conoce el modelo: aprenderlo

Fernando Fernández y Daniel Borrajo Aprendizaje Automático

Métodos Basados en el Modelo: Dyna-Q

Inicializar Q(s, a) y Modelo(s, a) arbitrariamente

Fernando Fernández y Daniel Borrajo Aprendizaje Automático

Representación Tabular de la Función Q

Fernando Fernández y Daniel Borrajo Aprendizaje Automático

Discretización del Espacio de Estados

Fernando Fernández y Daniel Borrajo Aprendizaje Automático

Dominio de navegación de un robot:

Goal V=12.5 V=25 V=50 V=100 V=0

V=6.25 V=12.5 V=25 V=50 V=100

V=3.12 V=6.25 V=12.5 V=25 V=50

V=1.6 V=3.12 V=6.25 V=12.5 V=25

V=0.8 V=1.6 V=3.12 V=6.25 V=12.5

Fernando Fernández y Daniel Borrajo Aprendizaje Automático

Pérdida de la Propiedad de Markov

Value Function Limits

Fernando Fernández y Daniel Borrajo Aprendizaje Automático

Keepaway (Stone, Sutton and Kuhlmann, 05)

Fernando Fernández y Daniel Borrajo Aprendizaje Automático

Ejemplo: la Tarea Keepaway

Espacio de estados: 19 atributos continuos (Los keepers y los

Fernando Fernández y Daniel Borrajo Aprendizaje Automático

Discretización uniforme del espacio de estados

Fernando Fernández y Daniel Borrajo Aprendizaje Automático

Regiones Generadas por la Discretización Uniforme

Proyección del espacio de estados sobre los atributos 2 y 3:

Fernando Fernández y Daniel Borrajo Aprendizaje Automático

CMAC (Albus, 81)

Superponer varias discretizaciones:

Cada celda mantiene su propia aproximación de la funcón Q:

Discretización de Resolución Variable: Árboles KD (Munos

Los nodos y hojas del árbol

Fernando Fernández y Daniel Borrajo Aprendizaje Automático

Utilizar un aproximador de funciones para representar la

L aproximadores (Q̂ai (s)) 1 aproximador (Q̂(s, a))