Aprendizaje por Refuerzo
Introducción a la Robótica Basada en Comportamientos
DC – FCEN - UBA
Diego Bendersky
Evaluación de políticas
• Dada una política π, queremos conocer
=
=
=
• |S| ecuaciones lineales, |S| incógnitas.
• Formas de resolverlo:
– Directo (preferido por los matemáticos)
– Iterativo (preferido por los computadores)
=
Evaluación de políticas
• Método iterativo: generamos una sucesión V0, V1, …
=
• Afortunadamente, la sucesión converge a Vπ (Bersekas, 1987)
– Vπ es punto fijo de la sucesión
– En cada paso, {Vk} se acerca a Vπ
Evaluación de políticas
• Algoritmo
Mejoramiento de políticas
• ¿Qué pasa si a una política π le cambiamos una sola
acción?
– Supongamos que en el estado s elegimos la acción a y después
seguimos la política π.
=
=
Mejoramiento de políticas
Teorema de mejoramiento de políticas
• sean π y π’ dos políticas determinísticas tales que, para
todo s  S,
Entonces, π’ es igual o mejor que π.
Esto es, para todo s  S
Mejoramiento de políticas
• Demostración:
• Si vale para un estado por separado, entonces vale para
todos!
Mejoramiento de políticas
• Si vale para cada estado por separado, entonces vale
para todos!
Iteración de políticas
• Estrategia para encontrar la política óptima:
• Algoritmo
Iteración por valor
• ¿Para qué calculamos en forma tan precisa el valor de V
en cada paso (sobre todo en las primeras iteraciones)?
No nos alcanzará con una aproximación?
• Caso extremo: hacemos sólo un paso de actualización
de V, y después mejoramos
Iteración por valor
• Algoritmo
Iteración de políticas generalizada
• Dos procesos independientes que interactúan
• Se deriva una familia de algoritmos
Diferencias temporales
• Idea “distintiva” de aprendizaje por refuerzo
– Hasta ahora, conocíamos el “modelo”
– En el mundo real, sólo tenemos instancias (outcomes)
rt | st=s, at=a, st+1=s’
st+1 | st=s, at=a
¿Podemos aprender de outcomes, sin tener la distribución?
Diferencias temporales
• Actualización incremental
Supongamos que tenemos que calcular
pero nos los van dando de a uno. ¿Cómo hacemos?
Diferencias temporales
• Regla de actualización incremental
NewEstimat e  (1  StepSize ) OldEstimat e  StepSize .Target
• En nuestro caso
V ' ( s t )  rt  1   V ( s t  1 )
V ( s t )  (1   )V ( s t )   V ' ( s t )
V ( s t )  V ( s t )   rt  1   V ( s t  1 )  V ( s t ) 
• Converge si α es suficientemente chico
Si consideramos el
outcome actual como
“la verdad”
Si lo combinamos
con el que
teníamos
Diferencias temporales
• Algoritmo (para evaluación de política)
Diferencias temporales
• Ejemplo: manejando a casa
Elapsed
Time
Predicted
Predicted
(minutes)
Time to
Go
Total
Time
leaving office, friday at 6
0
30
30
reach car, raining
5
35
40
exiting highway
20
15
35
2ndary road, behind truck
30
10
40
entering home street
40
3
43
arrive home
43
0
43
State
Diferencias temporales
• Ejemplo: manejando a casa
Diferencias temporales
• ¿Cómo mejoramos las políticas?
– Calculamos Q(s,a) en lugar de V(s)
– Definimos una política implícita: en cada estado, la acción
asociada es aquella que tiene un valor de Q más alto.
• ¡Problema!
– Los valores de Q para cada acción se van calculando a medida
que esa acción se ejecuta.
– Si ejecutamos siempre la misma, no vamos a poder calcular
cuan buenas son las otras
“Dilema exploración – explotación”
Diferencias temporales
• Una alternativa, es usar una política ε-greedy: elegir una
acción al azar con probabilidad ε y la mejor acción con
probabilidad (1-ε)
• Vamos reduciendo ε con el tiempo hasta hacerlo 0.
Diferencias temporales
• Algoritmo de mejoramiento de política: SARSA
Q-Learning
• La estrella de los algoritmos de RL
• Watkins, 1989
Novedad:
aprendizaje off-policy: aprendo una política (la óptima)
mientras sigo otra (una e-greedy).
Q-Learning
• Algoritmo
Descargar

Aprendizaje por Refuerzo