Ciencias Computacionales - Aprendizaje por Refuerzoemorales/Cursos/Aprendizaje2/...Los refuerzos pueden ser componentes o sugerencias de la utilidad actual a maximizar (e.g., buena

Introduccion

Metodos deSolucion deMDPs

Lideando conEspaciosGrandes

Algunos denuestrosdesarrollos

Aprendizaje por Refuerzo

Eduardo Morales

INAOE

(INAOE) 1 / 105

Introduccion




Contenido

1 Introduccion

2 Metodos de Solucion de MDPs

3 Lideando con Espacios Grandes

4 Algunos de nuestros desarrollos

(INAOE) 2 / 105

Introduccion




Introduccion


• Uno de los enfoques mas usados dentro de aprendizajees el aprendizaje supervisado a partir de ejemplos(pares entradas – salida provistos por el medioambiente), para despues predecir la salida de nuevasentradas.• Cualquier sistema de prediccion puede verse dentro de

este paradigma, sin embargo, ignora la estructurasecuencial del mismo.• En algunos ambientes, muchas veces se puede

obtener solo cierta retroalimentacion o recompensa orefuerzo (e.g., gana, pierde).

(INAOE) 3 / 105

Introduccion




Introduccion


• El refuerzo puede darse en un estado terminal y/o enestados intermedios.• Los refuerzos pueden ser componentes o sugerencias

de la utilidad actual a maximizar (e.g., buena movida).• En aprendizaje por refuerzo (RL) el objetivo es

aprender como mapear situaciones a acciones paramaximizar una cierta senal de recompensa.• Promesa: programar agentes mediante premio y

castigo sin necesidad de especificar como realizar latarea

(INAOE) 4 / 105

Introduccion




Introduccion

Diferencias con Otro Tipo de Aprendizaje

1 No se le presentan pares entrada - salida.2 El agente tiene que obtener experiencia util acerca de

los estados, acciones, transiciones y recompensas demanera activa para poder actuar de manera optima.

3 La evaluacion del sistema ocurre en forma concurrentecon el aprendizaje.

(INAOE) 5 / 105

Introduccion




Introduccion

Aplicaciones

• La primera aplicacion en aprendizaje por refuerzo fue elprograma para jugar damas de Samuel• Uso una funcion lineal de evaluacion con pesos usando

hasta 16 terminos• Su programa era parecido a la ecuacion de

actualizacion de pesos, pero no usaba recompensa enlos estados terminales, lo que hace que puede o noconverger y puede aprender a perder.• Logro evitar esto haciendo que el peso para ganancia

de material fuera siempre positivo.

(INAOE) 6 / 105

Introduccion




Introduccion

Aplicaciones

• Una de las mas conocidas es el control del penduloinvertido. Controlar la posicion x para que se mantengaaproximadamente derecho (θ ≈ π/2), manteniendoseen los lımites de la pista. X , θ, X y θ son continuas. Elcontrol es de tipo bang–bang.• Boxes (Michie, Chambers ’68) balanceaba el pendulo

por mas de una hora despues de 30 intentos (nosimulado)• Discretizaron el espacio en cajas. Se corrıa el sistema

hasta que se caıa el pendulo o se salıa de los lımites.Entonces se daba un refuerzo negativo a la ultima“caja” y se propagaba a la secuencia de “cajas” por lasque paso.

(INAOE) 7 / 105

Introduccion




Introduccion

Aplicaciones

• TD-gammon (Tesauro ’92) represento una funcion deevaluacion con una red neuronal de una sola capaintermedia con 40 nodos, que despues de 200,000juegos de entrenamiento mejoro notablemente sudesempeno.• Anadiendo atributos adicionales a una red con 80

nodos escondidos, despues de 300,000 juegos deentrenamiento, juega como los 3 mejores jugadores delmundo.• Tambien se desarrollo un algoritmo de RL que actualiza

las funciones de evaluacion en un arbol de busquedaen juegos. En ajedrez mejora el puntaje de unprograma de 1,650 a 2,150 despues de 308 juegos en3 dıas.

(INAOE) 8 / 105

Introduccion




Introduccion

Aplicaciones

Algunas aplicaciones recientes incluyen:• Watson (IBM) - campeon en el juego de Jeopardy

(2011). Se uso RL para aprender un funcion de valorque se uso para generar “apuestas” y ganar maspuntos.• Atari 2600 - se aprendio como jugar 46 video juegos,

superando en 29 a humanos• Go - campeon en el juego de Go• Multiples aplicaciones en robotica

(INAOE) 9 / 105

Introduccion




Introduccion


• En RL un agente trata de aprender un comportamientomediante interacciones de prueba y error en unambiente dinamico e incierto• En general, al sistema no se le dice que accion debe

tomar, sino que el debe de descubrir que acciones danel maximo beneficio• En un RL estandar, un agente esta conectado a un

ambiente por medio de percepcion y accion• En cada interaccion el agente recibe como entrada una

indicacion de su estado actual (s ∈ S) y selecciona unaaccion (a ∈ A). La accion cambia el estado y el agenterecibe una senal de refuerzo o recompensa (r ∈ R)

(INAOE) 10 / 105

Introduccion




Introduccion


(INAOE) 11 / 105

Introduccion




Introduccion


• El comportamiento del agente debe de ser tal queseleccione acciones que tiendan a incrementar a largoplazo la suma de las recompensas totales• El objetivo del agente es encontrar una polıtica (π, que

mapea estados a acciones) que maximice a largo plazoel refuerzo acumulado• En general el ambiente es no-determinıstico (tomar la

misma accion en el mismo estado puede dar resultadosdiferentes)• Sin embargo, se supone que el ambiente es

estacionario (las probabilidades de cambio de estadono cambian o cambian muy lentamente)

(INAOE) 12 / 105

Introduccion




Introduccion

Ejemplo de Problema

(INAOE) 13 / 105

Introduccion




Introduccion

Exploracion y Explotacion

• Aspectos importantes:1 Se sigue un proceso de prueba y error2 La recompensa puede estar diferida

• Existe un balance entre exploracion y explotacion• Para obtener buena ganancia uno prefiere seguir

ciertas acciones, pero para saber cuales, se tiene quehacer cierta exploracion• Muchas veces depende de cuanto tiempo se espera

que el agente interactue con el medio ambiente

(INAOE) 14 / 105

Introduccion




Introduccion

Procesos de Decision de Markov

• En RL se tiene que decidir en cada estado la accion arealizar• Este proceso de decision secuenial se puede

caracterizar como un proceso de decision de Markov oMDP• Un MDP modela un problema de decision secuencial

en donde el sistema evoluciona en el tiempo y escontrolado por un agente• La dinamica del sistema esta determinada por una

funcion de transicion de probabilidad que mapeaestados y acciones a otros estados

(INAOE) 15 / 105

Introduccion




Introduccion

MDP

Formalmente, un MDP es una tupla M =< S,A,Φ,R >formada por:• Un conjunto finito de estados S, (si ∈ S, i = {1, . . . ,n})• Un conjunto finito de acciones A, que pueden depender

de cada estado (aj(si), j = {1, . . . ,m})• Una funcion de recompensa (R), que define la meta y

mapea cada estado–accion a un numero (recompensa),indicando lo deseable del estado (f (s,a)⇒ R)• Un modelo del ambiente o funcion de transicion de

estados Φ(s′|s,a) (Φ : A× S → S) que nos dice laprobabilidad de alcanzar el estado s′ ∈ S al realizar laaccion a ∈ A en el estado s ∈ S

(INAOE) 16 / 105

Introduccion




Introduccion

Elementos Adicionales

• Polıtica (π): define como se comporta el sistema encierto tiempo. Es un mapeo (a veces estocastico) delos estados a las acciones (π(S)→ A)• Funcion de valor (V ): indica lo que es bueno a largo

plazo. Es la recompensa total que un agente puedeesperar acumular empezando en un estado s (V (s)) oen un estado haciendo una accion a (Q(s,a))• Las recompensas estan dadas por el ambiente, pero

los valores se deben de estimar (aprender) con base enlas observaciones

Aprendizaje por refuerzo aprende las funciones de valor o lapolıtica mientras interactua con el ambiente.

(INAOE) 17 / 105

Introduccion




Introduccion

Modelos de Recompensas

• Dado un estado st ∈ S y una accion at ∈ A(st ), elagente recibe una recompensa rt+1 y se mueve a unnuevo estado st+1

• Si las recompensas recibidas despues de un tiempo tse denotan como: rt+1, rt+2, rt+3, . . ., lo que queremoses maximizar lo que esperamos recibir de recompensatotal acumulada (Rt )• Si se tiene un punto terminal se llaman tareas

episodicas, si no se tiene se llaman tareas contınuas.

(INAOE) 18 / 105

Introduccion




Introduccion


• Horizonte finito: el agente trata de optimizar surecompensa esperada en los siguientes h pasos, sinpreocuparse de lo que ocurra despues:

E(h∑

t=0

rt )

• Se puede usar como:• polıtica no estacionaria: en el primer paso se toman los

h siguientes pasos, en el siguiente los h − 1, etc., hastaterminar. El problema principal es que no siempre seconoce cuantos pasos considerar

• receeding-horizon control: siempre se toman lossiguientes h pasos

(INAOE) 19 / 105

Introduccion




Introduccion


• Horizonte infinito (la mas utilizada): las recompensasque recibe un agente son reducidas geometricamentede acuerdo a un factor de descuento γ (0 ≤ γ ≤ 1):

R = r0 + γr1 + γ2r2 + . . . =∞∑

t=0

γk rt

donde γ se conoce como la razon de descuento y loque queremos maximizar es la recompensa totalesperada:

E(∞∑

t=0

γt rt )

(INAOE) 20 / 105

Introduccion




Introduccion


• Recompensa promedio: optimizar a largo plazo larecompensa promedio:

limh→∞E(1h

h∑t=0

rt )

Problema: no distingue polıticas que reciban grandesrecompensas al principio de las que no.

(INAOE) 21 / 105

Introduccion




Introduccion

Modelo Markoviano

• RL supone que se cumple con la propiedad Markoviana(las transiciones de estado solo dependen del estadoactual) y las probabilidades de transicion estan dadaspor:

Pass′ = Pr{st+1 = s′ | st = s,at = a}

El valor de recompensa esperado es:

Rass′ = E{rt+1 | st = s,at = a, st+1 = s′}

• Lo que se busca es estimar las funciones de valor. Estoes, que tan bueno es estar en un estado (o realizar unaaccion)• La nocion de “que tan bueno” se define en terminos de

recompensas futuras o recompensas esperadas

(INAOE) 22 / 105

Introduccion




Introduccion

Funciones de Valor• La polıtica π es un mapeo de cada estado s ∈ S y

accion a ∈ A(s) a la probabilidad π(s,a) de tomar laaccion a estando en el estado s• El valor de un estado s bajo la polıtica π, denotado

como Vπ(s), es la recompensa total esperada estandoen el estado s y siguiendo la polıtica π:

Vπ(s) = Eπ{Rt | st = s} = Eπ

{ ∞∑k=o

γk rt+k+1 | st = s

}

• El valor esperado tomando una accion a en estado sbajo la polıtica π (Qπ(s,a)):

Qπ(s,a) = Eπ{Rt | st = s,at = a}= Eπ

{∑∞k=o γ

k rt+k+1 | st = s,at = a}

(INAOE) 23 / 105

Introduccion




Introduccion

Funciones de Valor Optimas

• Las funciones de valor optimas se definen como:

V ∗(s) = maxπVπ(s) y Q∗(s,a) = maxπQπ(s,a)

• Las cuales se pueden expresar como las ecuacionesde optimalidad de Bellman:

V ∗(s) = maxa∑s′Pa

ss′ [Rass′ + γV ∗(s′)]

Q∗(s,a) =∑s′Pa


Q∗(s,a) =∑s′Pa

ss′ [Rass′ + γmaxa′Q∗(s′,a′)]

(INAOE) 24 / 105

Introduccion




Metodos de Solucion de MDPs

Metodos de Solucion

Existen tres metodos principales de resolver MDPs:1 Programacion Dinamica2 Monte Carlo, y3 Diferencias Temporales o de Aprendizaje por Refuerzo

(INAOE) 25 / 105

Introduccion





Programacion Dinamica

• Si se conoce el modelo del ambiente, o sea, lastransiciones de probabilidad (Pa

ss′) y los valoresesperados de recompensas (Ra

ss′), las ecuaciones deoptimalidad de Bellman nos representan un sistema de|S| ecuaciones y |S| incognitas• Consideremos primero como calcular la funcion de

valor Vπ dada una polıtica arbitraria π.

(INAOE) 26 / 105

Introduccion





Funciones de Valor para una Polıtica

Vπ(s) = Eπ{Rt | st = s}= Eπ

{rt+1 + γrt+2 + γ2rt+3 + . . . | st = s

}= Eπ {rt+1 + γVπ(st+1) | st = s}=

∑a π(s,a)

∑s′ Pa

ss′ [Rass′ + γVπ(s′)]

donde π(s,a) es la probabilidad de tomar la accion a enestado s bajo la polıtica π.

(INAOE) 27 / 105

Introduccion






• Podemos hacer aproximaciones sucesivas, evaluandoVk+1(s) en terminos de Vk (s).

Vk+1(s) =∑

a

π(s,a)∑s′Pa

ss′ [Rass′ + γVk (s′)]

• Podemos entonces definir un algoritmo de evaluacioniterativa de polıticas

(INAOE) 28 / 105

Introduccion






Inicializa V (s) = 0 para toda s ∈ SRepite

∆← 0Para cada s ∈ S

v ← V (s)V (s)←

∑a π(s,a)

∑s′ Pa

ss′ [Rass′ + γV (s′)]

∆← max(∆, |v − V (s)|)Hasta que ∆ < θ (numero positivo pequeno)Regresa V ≈ Vπ

(INAOE) 29 / 105

Introduccion





Iteracion de Polıticas

• Calculamos la funcion de valor de una polıtica paratratar de encontrar mejores polıticas• Dada una funcion de valor, podemos probar una accion

a 6= π(s) y ver si su V (s) es mejor o peor que el Vπ(s)

• En lugar de hacer un cambio en un estado y ver elresultado, se pueden considerar cambios en todos losestados considerando todas las acciones de cadaestado, seleccionando aquella que parezca mejor deacuerdo a una polıtica greedy.• Podemos entonces calcular una nueva polıticaπ′(s) = argmaxaQπ(s,a) y continuar hasta que nomejoremos.

(INAOE) 30 / 105

Introduccion






• Esto sugiere, partir de una polıtica (π0) y calcular lafuncion de valor (Vπ0), con la cual encontrar una mejorpolıtica (π1) y ası sucesivamente hasta converger a π∗ yV ∗.• A este procedimiento se llama iteracion de polıticas

(INAOE) 31 / 105

Introduccion






V (s) ∈ R y π(s) ∈ A(s) arbitrariamente ∀s ∈ S (Inicializa)Repite (Evaluacion de Polıtica)


v ← V (s)

V (s)←∑

s′ Pπ(s)ss′ [Rπ(s)ss′ + γV (s′)]

∆← max(∆, |v − V (s)|)Hasta que ∆ < θ (numero positivo pequeno)pol-estable← true (Mejora de Polıtica)Para cada s ∈ S:

b ← π(s)π(s)← argmaxa

∑s′ Pa

ss′ [Rass′ + γV (s′)]

if b 6= π, then pol-estable← falseIf pol-estable, then stop, else evalua nva. polıtica

(INAOE) 32 / 105

Introduccion





Iteracion de Valor

• Iteracion de polıticas en cada iteracion evalua la polıticay requiere recorrer todos los estados varias veces• El paso de evaluacion de polıtica lo podemos truncar

sin perder la garantıa de convergencia, despues derecorrer una sola vez todos los estados• A esta forma se le llama iteracion de valor (value

iteration) y se puede escribir combinando la mejora enla polıtica y la evaluacion de la polıtica truncada comosigue:

Vk+1(s) = maxa∑s′Pa

ss′ [Rass′ + γVk (s′)]

• Se puede ver como expresar la ecuacion de Bellman enuna regla de actualizacion

(INAOE) 33 / 105

Introduccion





Iteracion de Valor

Inicializa V (s) = 0 para toda s ∈ SRepite


v ← V (s)V (s)← maxa

∑s′ Pa


∆← max(∆, |v − V (s)|)Hasta que ∆ < θ (numero positivo pequeno)Regresa una polıtica determinıstica tal que:

π(s) = argmaxa∑

s′ Pass′ [R

ass′ + γV ∗(s′)]

(INAOE) 34 / 105

Introduccion





Monte Carlo

• Los metodos de Monte Carlo, solo requieren deexperiencia y la actualizacion se hace por episodio masen lugar de en cada paso• El valor de un estado es la recompensa esperada que

se puede obtener a partir de ese estado• Para estimar Vπ y Qπ podemos tomar estadısticas

haciendo un promedio de las recompensas obtenidas

(INAOE) 35 / 105

Introduccion





Monte Carlo para Estimar V π

RepiteGenera un episodio usando πPara cada estado s en ese episodio:

R ← recompensa despues de la primera ocurrencia de sAnade R a recomp(s)V (s)← promedio(recomp(s))

(INAOE) 36 / 105

Introduccion





Monte Carlo

• Para estimar pares estado-accion (Qπ) corremos elpeligro de no ver todos los pares, por lo que se buscamantener la exploracion.• Lo que normalmente se hace es considerar solo

polıticas estocasticas que tienen una probabilidaddiferente de cero de seleccionar todas las acciones.

(INAOE) 37 / 105

Introduccion





Monte Carlo para Mejorar Polıticas

• Con Monte Carlo podemos alternar entre evaluacion ymejoras con base en cada episodio• La idea es que despues de cada episodio las

recompensas observadas se usan para evaluar lapolıtica y la polıtica se mejora para todos los estadosvisitados en el episodio

(INAOE) 38 / 105

Introduccion





Algoritmo de Monte Carlo para MejorarPolıticas

RepiteGenera un episodio usando π con exploracionPara cada par (s,a) en ese episodio:

R ← recompensa despues de la primeraocurrencia de (s,a)

Anade R a recomp(s,a)Q(s,a)← promedio(recomp(s,a))

Para cada s en el episodio:π(s)← argmaxaQ(s,a)

(INAOE) 39 / 105

Introduccion





Diferencias Temporales

• Los metodos de TD combinan las ventajas de los dosanteriores: permiten hacer bootstrapping - estimarvalores con base en otras estimaciones - (como DP) yno requieren tener un modelo del ambiente (como MC).• Metodos tipo TD solo tienen que esperar el siguiente

paso.• TD usan el error o diferencia entre predicciones

sucesivas (en lugar del error entre la prediccion y lasalida final) aprendiendo al existir cambios entrepredicciones sucesivas.

(INAOE) 40 / 105

Introduccion





Esquemas de Exploracion

• ε−greedy: La mayor parte del tiempo se selecciona laaccion que da el mayor valor estimado, pero conprobabilidad ε se selecciona una accion aleatoriamente.• softmax: La probabilidad de seleccion de cada accion

depende de su valor estimado. La mas comun sigueuna distribucion de Boltzmann o de Gibbs, y seleccionauna accion con la siguiente probabilidad:

eQt (a)/τ∑nb=1 eQt (b)/τ

donde τ es un parametro positivo (temperatura).

(INAOE) 41 / 105

Introduccion





Algoritmos “on” y “off-policy”

• Los algoritmos on-policy: Estiman el valor de la polıticamientras la usan para el control. Se trata de mejorar lapolıtica que se usa para tomar decisiones.• Los algoritmos off-policy: Usan la polıtica y el control en

forma separada. La estimacion de la polıtica puede serpor ejemplo greedy y la polıtica de comportamientopuede ser ε-greedy.• Esto es, la polıtica de comportamiento esta separada

de la polıtica que se quiere mejorar (es lo que haceQ-learning)

(INAOE) 42 / 105

Introduccion






• Los algoritmos son incrementales y facil de computar• Actualizan las funciones de valor usando el error entre

lo estimado y la suma de la recompensa inmediata y loestimado del siguiente estado• El mas simple TD(0) es:

V (st )← V (st ) + α [rt+1 + γV (st+1)− V (st )]

(INAOE) 43 / 105

Introduccion





Algoritmo TD(0)

Inicializa V (s) arbitrariamente y π a la polıtica a evaluarRepite (para cada episodio):

Inicializa sRepite (para cada paso del episodio):

a← accion dada por π para sRealiza accion a; observa la recompensa, r ,

y el siguiente estado, s′

V (s)← V (s) + α [r + γV (s′)− V (s)]s ← s′

hasta que s sea terminal

(INAOE) 44 / 105

Introduccion





SARSA

• La actualizacion de valores tomando en cuenta laaccion serıa:

Q(st ,at )← Q(st ,at )+α[rt+1 +γQ(st+1,at+1)−Q(st ,at )]

• y el algoritmo es practicamente el mismo, solo que sellama SARSA

(INAOE) 45 / 105

Introduccion





Algoritmo SARSA

Inicializa Q(s,a) arbitrariamenteRepite (para cada episodio):

Inicializa sSelecciona una a a partir de s usando la polıtica

dada por Q (e.g., ε–greedy)Repite (para cada paso del episodio):

Realiza accion a, observa r , s′

Escoge a′ de s′ usando la polıtica derivada de QQ(s,a)← Q(s,a) + α [r + γQ(s′,a′)−Q(s,a)]s ← s′; a← a′;


(INAOE) 46 / 105

Introduccion





Q-Learning

• Uno de los desarrollos mas importantes en aprendizajepor refuerzo fue el desarrollo de un algoritmo“fuera-de-polıtica” (off-policy) conocido comoQ-learning.• La idea principal es realizar la actualizacion de la

siguiente forma (Watkins, 89):

Q(st ,at )← Q(st ,at )+α[rt+1+γmaxaQ(st+1,at+1)−Q(st ,at )]

(INAOE) 47 / 105

Introduccion





Algoritmo Q-Learning

Inicializa Q(s,a) arbitrariamenteRepite (para cada episodio):

Inicializa sRepite (para cada paso del episodio):

Selecciona una a de s usando la polıtica dada por Q(e.g., ε–greedy)Realiza accion a, observa r , s′

Q(s,a)← Q(s,a) + α [r + γmax ′aQ(s′,a′)−Q(s,a)]s ← s′;


(INAOE) 48 / 105

Introduccion




Lideando con Espacios Grandes

Estrategias para Espacios Grandes

• Uno de los problemas principales de RL es suaplicacion a espacios grandes (muchos estados yacciones). Aunque los algoritmos convergen en teorıa,en la practica pueden tomar un tiempo inaceptable.• Se han propuesto diferentes estrategias para esto:

1 Actualizar varias funciones de valor a la vez2 Aprender un modelo y usarlo3 Utilizar abstracciones y jerarquıas4 Incorporar ayuda adicional5 Usar aproximacion de funciones

(INAOE) 49 / 105

Introduccion





Trazas de Elegibilidad

• Estan entre metodos de Monte Carlo y TD de un paso.• Los metodos Monte Carlo realizan la actualizacion

considerando la secuencia completa de recompensasobservadas.• La actualizacion de los metodos de TD la hacen

utilizando unicamente la siguiente recompensa.• La idea de las trazas de elegibilidad es considerar las

recompensas de n estados posteriores (o afectar a nanteriores).

(INAOE) 50 / 105

Introduccion






• Si recordamos:

Rt = rt+1 + γrt+2 + γ2rt+3 + . . .+ γT−t−1rT

• Lo que se hace en TD es usar:

Rt = rt+1 + γVt (st+1)

donde Vt (st+1) reemplaza a los siguientes terminos(rt+2 + γrt+3 . . .)• Sin embargo, hace igual sentido hacer:

Rt = rt+1 + γrt+2 + γ2Vt (st+2)

y, en general, para n pasos en el futuro.

(INAOE) 51 / 105

Introduccion






• En la practica, mas que esperar n pasos para actualizar(forward view), se realiza al reves (backward view). Sepuede probar que ambos enfoques son equivalentes.• Se guarda informacion sobre los estados por los que se

paso y se actualizan hacia atras los “errores”(descontadas por la distancia)• Para esto se asocia a cada estado o par estado-accion

una variable extra, representando su traza deelegibilidad (eligibility trace) que denotaremos por et (s)o et (s,a).• Este valor va decayendo con la longitud de la traza

creada en cada episodio

(INAOE) 52 / 105

Introduccion






• Para TD(λ):

et (s) =

{γλet−1(s) si s 6= stγλet−1(s) + 1 si s = st

• Para SARSA se tiene lo siguiente:

et (s,a) =

{γλet−1(s,a) si s 6= stγλet−1(s,a) + 1 si s = st

(INAOE) 53 / 105

Introduccion





SARSA(λ)

Inicializa Q(s,a) arbitrariamente y e(s,a) = 0 ∀s,aRepite (para cada episodio)

Inicializa s,aRepite (para cada paso en el episodeo)

Toma accion a y observa r , s′

Selecciona a′ de s′ usando una polıtica derivadade Q (e.g., ε−greedy)

δ ← r + γQ(s′,a′)−Q(s,a)e(s,a)← e(s,a) + 1Para todos s,a

Q(s,a)← Q(s,a) + αδe(s,a)e(s,a)← γλe(s,a)

s ← s′; a← a′


(INAOE) 54 / 105

Introduccion





Q(λ)

• Para Q-learning como la seleccion de acciones sehace, por ejemplo, siguiendo una polıtica ε−greedy, setiene que tener cuidado, ya que a veces losmovimientos son movimientos exploratorios• No queremos propagar en caminos buenos “errores”

negativos por acciones exporatorias• Se puede mantener historia de la traza solo hasta el

primer movimiento exploratorio, ignorar las accionesexploratorias, o hacer un esquema un poco mascomplicado que considera todas las posibles accionesen cada estado.

(INAOE) 55 / 105

Introduccion





Aprendiendo Modelos

• Con un modelo podemos predecir el siguiente estado yla recomepensa dado un estado y una accion• La prediccion puede ser un conjunto de posibles

estados con su probabilidad asociada o puede ser unestado que es muestreado de acuerdo a la distribucionde probabilidad de los estados resultantes• Lo interesante es que podemos utilizar los estados y

acciones simulados para aprender. Al sistema deaprendizaje no le importa si los pares estado-accionson dados de experiencias reales o simuladas.

(INAOE) 56 / 105

Introduccion





Dyna-Q

• Dado un modelo del ambiente, uno puede seleccionaraleatoriamente un par estado–accion, usar el modelopara predecir el siguiente estado, obtener unarecompensa y actualizar valores Q. Esto se puederepetir indefinidamente hasta converger a Q∗.• El algoritmo Dyna-Q combina experiencias con

planificacion para aprender mas rapidamente unapolıtica optima.• La idea es aprender de experiencia, pero tambien usar

un modelo para simular experiencia adicional y asıaprender mas rapidamente

(INAOE) 57 / 105

Introduccion





Algoritmo de Dyna-Q

Inicializa Q(s,a) y Modelo(s,a) ∀s ∈ S,a ∈ ADO forever

s ← estado actuala← ε−greedy(s,a)realiza accion a observa s′ y rQ(s,a)← Q(s,a) + α[r + γmaxa′Q(s′,a′)−Q(s,a)]Modelo(s,a)← s′, rRepite N veces:

s ← estado anterior seleccionado aleatoriamentea← accion aleatoria tomada en ss′, r ← Modelo(s,a)Q(s,a)← Q(s,a) + α[r + γmaxa′Q(s′,a′)−Q(s,a)]

(INAOE) 58 / 105

Introduccion





Prioritized Sweeping

• El algoritmo de Dyna-Q selecciona pares estado-accionaleatoriamente de pares anteriores. Sin embargo, laplanificacion se puede usar mucho mejor si se enfoca apares estado-accion especıficos.• Por ejemplo, enfocarnos en las metas e irnos hacia

atras o, mas generalmente, irnos hacia atras decualquer estado que cambie de manera importante suvalor.• Este proceso se puede repetir sucesivamente, sin

embargo, algunos estados cambian mucho mas queotros. Lo que podemos hacer es ordenarlos y cambiarsolo los que rebasen un cierto umbral. Esto esprecisamente lo que hace el algoritmo de prioritizedsweeping

(INAOE) 59 / 105

Introduccion





Algoritmo de Prioritized Sweeping

Inicializa Q(s,a) y Modelo(s,a) ∀s ∈ S,a ∈ A y ColaP = ∅DO forever

s ← estado actuala← ε−greedy(s,a)realiza accion a observa s′ y rModelo(s,a)← s′, rp ←| r + γmaxa′Q(s′,a′)−Q(s,a) |if p > θ, then inserta (s,a) a ColaP con prioridad pRepite N veces, mientras ColaP 6= ∅:

s,a← primero(ColaP)s′, r ← Modelo(s,a)Q(s,a)← Q(s,a) + α[r + γmaxa′Q(s′,a′)−Q(s,a)]Repite ∀s,a que se predice llegan a s:

r ← recompensa predichap ←| r + γmaxaQ(s,a)−Q(s,a) |if p > θ, then inserta s,a a ColaP con prioridad p

(INAOE) 60 / 105

Introduccion





Abstracciones y Jerarquıas

• Agregacion de estados: se juntan estados “parecidos” ya todos ellos se les asigna el mismo valor, reduciendoel espacio de estados. Por ejemplo: tile-coding, coarsecoding, radial basis functions, Kanerva coding, ysoft-state aggregation.• Abstracciones basadas en maquinas de estado finito: el

aprendizaje por refuerzo tiene que decidir que maquinautilizar (por ejemplo, HAM y PHAM).

(INAOE) 61 / 105

Introduccion





Abstracciones y Jerarquıas

• Definicion de jerarquıas: se divide el espacio ensubproblemas, se aprenden polıticas a los espacios demas bajo nivel y estas se usan para resolver problemasde mas alto nivel (e.g., MAXQ, HEXQ).• Algo parecido se usa con Macros y Options, en donde

se aprenden polıticas de subespacios que se usan pararesolver problemas mas grandes.• Tambien se ha buscado utilizar representaciones

relacionales dentro de aprendizaje por refuerzo (RRL),ya sea para representar las funciones de valor y/o pararepresentar los estados y las acciones.

(INAOE) 62 / 105

Introduccion





Incorporar Informacion Adicional

• En su forma tradicional, RL no utiliza practicamentenada de conocimiento del dominio• Una forma de ayudar a RL a coverger mas rapidamente

es incorporardo informacion adicional:1 La idea de reward shaping es incorporar informacion

adicional a la funcion de recompensa2 Tambien se han utilizado soluciones conocidas como

guıas o trazas que se usan para aprender masrapidamente las funciones de valor o para aprender undirectamente la polıtica

(INAOE) 63 / 105

Introduccion




Algunos de nuestros desarrollos

Algunos de Nuestros Desarrollos

• Aprendizaje por refuerzo con una representacionrelacional• Reward shaping por parte del usuario• Transfer Learning para RL

(INAOE) 64 / 105

Introduccion





¿Podemos usar RL para aprender a volar?

(INAOE) 65 / 105

Introduccion





Aprender a Volar

Retos: muchas variables contınuas, un espacio deestados-acciones contınuo, areas grandes sin unarecompenza clara, ...

(INAOE) 66 / 105

Introduccion





Ideas Prtincipales

• Usar una representacion relacional• Facil expresar abstracciones• Puede incorporar conocimiento del dominio• Las polıticas son re-utilizables en problemas parecidos

• Aprende/considera solo un conjunto de accionesrelevantes de trazas dadas por un usuario

(INAOE) 67 / 105

Introduccion





Representacion Relacional

• > 150,000 (posiciones) estados• hasta 22 acciones por estado

(INAOE) 68 / 105

Introduccion





Estados Equivalentes

• Estado: kings in oppos(S) and not threatened(S) and ...• Accion: If kings in oppos(S1) and not threatened(S1)

and ... Then move(rook,S1,S2) and check(S2) andL-shaped-pattern(S2)

(INAOE) 69 / 105

Introduccion





Aprender Acciones de Trazas

• Aprende un subconjunto de acciones relevantes porestado de trazas de usuarios• Para cada cuadro:

• Transforma la informacion a una representacionrelacional

• Construye, si es nueva, una accion con la conjuncion depredicados y accion relacionales

(INAOE) 70 / 105

Introduccion





rQ-learning

Inicializa Q(sr ,ar ) arbitrariamenteRepite (para cada episodio):

Inicializa s, sr ← rels(s)Repite (para cada paso del episodio):

Selecciona una ar de sr usando la polıtica dada por Q(e.g., ε−greedy)Realiza accion aleatoria a de ar ,

observa r , s′, s′r ← rels(s′)Q(sr ,ar )← Q(sr ,ar ) + α

[r + γmaxa′

rQ(s′r ,a′r )−Q(sr ,ar )

]s ← s′, sr ← s′r ;


(INAOE) 71 / 105

Introduccion





Algunos Resultados

(INAOE) 72 / 105

Introduccion





Converge mas Rapido

(INAOE) 73 / 105

Introduccion





Se Pueden Re-Utilizar las Polıticas

(INAOE) 74 / 105

Introduccion





Avion

Dos etapas:• Aprende acciones de trazas de vuelos (5 trazas)• Usa las acciones aprendidas para explorar y aprender

nuevas acciones hasta que (casi) no exista masaprendizaje (20 pruebas)• 32% (359) aleron 1.5 acc. (de 5) por estado• 64% (180) elevacion 3.2 acc. (de 5) por estado

(INAOE) 75 / 105

Introduccion





Algunos Resultados

(INAOE) 76 / 105

Introduccion





Algunos Resultados

(INAOE) 77 / 105

Introduccion





Algunos Resultados

(INAOE) 78 / 105

Introduccion





Robot

• Misma estrategia para aprender tareas de navegacion• Transformar la informacion de los sensores a

representacion relacional• Transformar las acciones discretas en contınuas al

momento de ejecucion

(INAOE) 79 / 105

Introduccion





Transformacion de Informacion

(INAOE) 80 / 105

Introduccion





Transformacion de Informacion

(INAOE) 81 / 105

Introduccion





Resultados

• Entrenamiento: 20 trazas de navegacion y 10 deseguimiento• Pruebas: 10 de navegacion y 10 de seguimiento en

diferentes mapas y con diferentes metas

(INAOE) 82 / 105

Introduccion





Trazas y retro-alimentacion por voz

• Generar trazas instruyendo con voz al robot• Nuevo:

• Se tienen errores en el reconocimiento de voz• Permitir al usuario retro-alimentar durante el proceso de

aprendizaje (dynamic/on-line reward shaping)

(INAOE) 83 / 105

Introduccion





Dynamic Reward Shaping

• La retro-alimentacion puede:• Calificar el desempeno del robot y cambiar

temporalmente la recompensa (r = rrl + rusuario)• Alterar la polıtica al comandar acciones directamente

• La retro-alimentacion se da:• Con retardos• No necesariamente de forma consistente

(INAOE) 84 / 105

Introduccion





Vocabulario

Se uso Sphinx3 y Dimex (UNAM) con alrededor de 250palabras

(INAOE) 85 / 105

Introduccion





Algunos Resultados

Tambien se demuestra que si le dan demostraciones alsistema, el numero de intervenciones del usuario se reducea la mitad.

(INAOE) 86 / 105

Introduccion





El usuario muestra la tarea

• Se generan trazas mostrandolas (se captura conKinect)• Se transforman a posibles trazas del robot (brazo)• Se usa posicion y distancia relativas entre la

mano/manipulador y el objeto/lugar meta

(INAOE) 87 / 105

Introduccion





Mostrando Tareas

(INAOE) 88 / 105

Introduccion





Mostrando Tareas

(INAOE) 89 / 105

Introduccion





Mostrando Tareas

(INAOE) 90 / 105

Introduccion





Transfer Learning

• La idea es aprender mas rapido/mejor una tareausando informacion de otra(s) tarea(s) previamenteaprendida(s)

(INAOE) 91 / 105

Introduccion





Efectos de TL en RL

(INAOE) 92 / 105

Introduccion





TL en RL con GPs

• Se transfirieron parametros y se sintetizaron tuplas• Al transferir tuplas se tiene que definir cuales• Filtro de Lazaric:

• ¿De donde transferir? La probabilidad de que la tareaorigen genere muestras de la tarea destino (taskcompliance)

• ¿Cuales transferir? Muestras muy relevantes o muyalejadas (relevance)

(INAOE) 93 / 105

Introduccion





QTL• La idea es transferir hiperparametros (sesgo sobre la

distribucion de posibles funciones de transicion)• Hay que definir como hacer la transferencia• Esta se hace de forma gradual:

• Usando un factor de olvido

Θ0 = Θs

Θi = γΘi−i + (1− γ)Θpi , i > 0

• Actualizacion Bayesiana

p(Θpk ) ∼ N (µp, σ2p) σ2

k =σ2

pσ2k−i

σ2p+σ2

k+1

p(Θ | Θpk ) ∼ N (µk , σ2k ) σ2

k=0 = 1nsource

µk = σ2k

(µk−1

σ2k−1

+µp

σ2p

)σ2

p = 1ntarget

(INAOE) 94 / 105

Introduccion





SST

Sıntesis de Tuplas:• Aprender una funcion de transicion en la tarea objetivo• Aprender/usar la funcion de transicion de la tarea

original• Aprender una funcion de diferencias• En espacios poco explorados, generar ejemplos

artificiales usando los ejemplos de la tarea original y lafuncion de diferencias

(INAOE) 95 / 105

Introduccion





¿Donde y Cuantas Tuplas?

• En lugares desconocidos (alejados en < s,a >): Si yatengo ejemplos, no necesito generar• Generar hasta completar el numero de ejemplos

usados en la tarea original• Mantener ese numero fijo => ir reduciendo el numero

de ejemplos de la tarea original conforme se explora latarea objetivo

(INAOE) 96 / 105

Introduccion





Proceso

(INAOE) 97 / 105

Introduccion





Proceso

(INAOE) 98 / 105

Introduccion





Proceso

(INAOE) 99 / 105

Introduccion





Proceso

(INAOE) 100 / 105

Introduccion





Experimentos

Probar en 3 dominios:

1 Pendulo invertido(clasico)

2 Auto en la montana(tranferencianegativa)

3 De cuadricoptero ahelicoptero

(INAOE) 101 / 105

Introduccion





Algunos Resultados

(INAOE) 102 / 105

Introduccion





Algunos Resultados

(INAOE) 103 / 105

Introduccion





Resultados SST

(INAOE) 104 / 105

Introduccion





Resultados SST

(INAOE) 105 / 105

Documents

Ciencias Computacionales - Aprendizaje por Refuerzoemorales/Cursos/Aprendizaje2/...Los refuerzos pueden ser componentes o sugerencias de la utilidad actual a maximizar (e.g., buena