REINFORCEMENT LEARNING
Jesús Fernández Bes
Noviembre 2012
ÍNDICE
1. ¿Qué es, qué no es y para qué sirve el RL?
2. Formulación: Markov Decision Processes
1.
2.
Dynamic Programming
Algoritmos clásicos de RL
3. Líneas de Investigación y otros aspectos de interés
en RL.
1.
2.
3.
4.
Aproximación funcional
RL con GP
POMDP
Otros aspectos
REINFORCEMENT LEARNING
2
DEFINICIÓN
Reinforcement Learning is the problem faced by
an autonomous agent that learns behavior
through trial-and-error interactions with a
dynamic environment.
Kaelbling et al. 1996
Interacción
Recompensa
Autonomía
REINFORCEMENT LEARNING
Muestreo
3
EL PROBLEMA DE REINFORCEMENT
LEARNING
1.
r
2.
s’
Environment
s  s’
3.
a
4.
El agente interactua con el
entorno.
Acciones modifican el
entorno y proporcionan
una recompensa.
No se conoce la dinámica
de estados.
Agente trata de aprender
comportamiento óptimo.
¿Qué acción tomar en cada estado para maximizar
una recompensa a largo plazo?
REINFORCEMENT LEARNING
4
¿A QUÉ SE PARECE PERO NO ES RL?
• Supervised Learning.
Hay par entrada/salida. No una recompensa inmediata.
En RL no se sabe que acción es mejor a largo plazo.
• Active Learning.
Elegir muestras de las que aprender. Siguen siendo pares
entrada/salida.
• Multi – Armed Bandits.
En MAB no existe concepto estado.
• Dynamic Programming.
Se conoce toda la dinámica de estados.
REINFORCEMENT LEARNING
5
APLICACIONES
RL application
areas
aircraft control
engine control
bio/chemical reactors
signal processing
natural language processing
web services
brain-computer interfaces
Process Control
23%
Other
8%
Finance
4%
option pricing
Autonomic
Computing
asset management
6% Traffic
load balancing
memory management
algorithm tuning
6%
stoplight control, trains, unmanned vehicles
Networking
21%
Survey by Csaba Szepesvari
of 77 recent application
papers, based on an IEEE.org
search for the keywords
“RL” and “application”
sensor networks
routing
call admission control
network resource management
Resource Management
18%
Robotics
13%
power systems
inventory control
supply chains
customer service
mobile robots, motion control, Robocup, vision
Rick Sutton. Deconstructing Reinforcement Learning. ICML 09
REINFORCEMENT LEARNING
6
MARKOV DECISION PROCESSES
Un Markov Decision Process (MDP) es un tupla <S,A,T,R>
donde:
• S es un conjunto finito de estados,
• A es un conjunto finito de acciones,
• T es una función de transición definida como
• R es una función de recompensa definida como
Dado un MDP definimos una política
• Determinista
como una función:
• Estocástica
REINFORCEMENT LEARNING
7
OBJETIVOS. CRITERIOS A OPTIMIZAR
• ¿ Cual es el objetivo del agente?
• ¿ Cómo tener en cuenta la recompensa a largo plazo?
Principalmente hay tres modelos:
Horizonte Finito
Horizonte Infinito
REINFORCEMENT LEARNING
Recompensa
Promedio
8
FUNCIONES DE VALOR
Discounted returns. Valor esperado de las recompensas
futuras (con descuento).
– State Value function:
Value Function Assumption:
“All efficient methods for solving
sequential decision problems
estimate value functions as an
intermidiate step.”
– State-Action Value function:
REINFORCEMENT LEARNING
9
ECUACIONES DE BELLMAN
Richard Bellman 1957.
• Ambas funciones se pueden escribir de forma
recursiva.
• La solución óptima satisface:
REINFORCEMENT LEARNING
10
ECUACIONES DE BELLMAN (2)
• Desarrollo equivalente para Q
• Existe una relación directa entre V* y Q*:
REINFORCEMENT LEARNING
11
DYNAMIC PROGRAMMING
• Model-Based.
– Entorno Determinista o estadística conocida.
– Modelo perfecto de MDP.
• Útil desde el punto de vista teórico y algorítmico.
• Relativamente eficientes pero poco útiles en RL o
cuando el espacio de estados es muy grande.
REINFORCEMENT LEARNING
12
ALGORITMOS BÁSICOS DE DP (1):
POLICY ITERATION
REINFORCEMENT LEARNING
13
ALGORITMOS BÁSICOS DE DP (2):
VALUE ITERATION
REINFORCEMENT LEARNING
14
DE DYNAMIC PROGRAMMING A
REINFORCEMENT LEARNING
• Model - Free
– Estadística desconocida y parcialmente desconocida.
• Necesidad de muestreo y exploración.
Compromiso Exploration vs. Exploitation
• Necesario explorar el espacio de políticas para
encontrar buenas políticas.
• Necesario usar las políticas buenas el mayor
tiempo posible para obtener mucha
recompensa.
REINFORCEMENT LEARNING
15
POLÍTICAS DE EXPLORACIÓN
• Hay políticas sencillas de exploración. Se basan
en las utilizadas en problemas de bandits:
– ε – greedy strategy
• Elegir acción a según π (mejor acción posible) con
probabilidad 1-ε.
• Elegir acción a aleatoria con probabilidad ε.
– Boltzmann (softmax) strategy
– Optimistic Q initialization
REINFORCEMENT LEARNING
16
MÉTODOS BÁSICOS DE RL
• Métodos de Monte Carlo
– Se estiman las funciones de valor como promedios
observados durante la iteración.
– Sobretodo útiles en horizonte finito. Juegos.
• Temporal - Difference Learning
– Se aprenden las estimaciones de los valores a
partir de otras estimaciones.
– Online. No necesitan barrer todo el espacio de
estado.
REINFORCEMENT LEARNING
17
TD (0)
• Sólo modifica la policy evaluation.
REINFORCEMENT LEARNING
18
SARSA
• On-policy.
• Útil en entornos no estacionarios.
REINFORCEMENT LEARNING
19
Q - LEARNING
• Algoritmo más popular con diferencia.
• Off-Policy.
REINFORCEMENT LEARNING
20
ACTOR-CRITIC LEARNING
• El agente se compone de dos partes.
– Actor: selecciona la política de acuerdo a las
preferencias p(st,at).
– Critic: Evalúa las acciones. Mediante el TD-error:
– Se actualizan las
Preferencias:
REINFORCEMENT LEARNING
21
APROXIMACIÓN FUNCIONAL
• Si el número de estados es GRANDE o
INFINITO.
– No se puede representar V o Q como una tabla.
• Aproximación Least Squares
– Se representa la Value function ( V o Q ) como
una combinación lineal de funciones.
– Se aproxima minimizando una norma LS
REINFORCEMENT LEARNING
22
Reinforcement Learning con GP
Bayesiano:
– Se mantiene una distribución de probabilidad sobre distintos valores.
– Permiten incluir conocimiento a priori, exploración, …
– Existen otras aproximaciones bayesianas además de los GP: BQL,…
• Rassmussen C.E., Kuss M.
– Distribución sobre discounted returns, no sólo Esperanza (V = E{D})
mediante un GP.
– Aprende también las transiciones como GP.
– Solución cerrada para algunas distribuciones de recompensas.
• Engel Y., Mannor S., Mier R.
– TD + Aproximación de V con GP.
– Implementación online. Kernel Sparsification.
REINFORCEMENT LEARNING
23
PARTIALLY OBSERVABLE MDP
• Relajar asunción de los MDP: Parte del estado puede
ser oculta.
– Estado S ya no es Markoviano.
• En POMDP además de <S,A,T,R> se define el conjunto
de observaciones Ω y la función O.
• R y T siguen dependiendo de s, no de o, decidir
acción en base a 1 observación ya no es óptimo.
Necesita memoria.
– Belief vector b(s).
REINFORCEMENT LEARNING
24
POMDP
• En general se necesita modelo de T y R.
– DP o Model-based RL.
• Diferentes heurísticos para obtener las
políticas a partir de los b(s)
• Métodos de búsqueda de política basados en
simulaciones.
– PEGASUS: Andrew Ng. & Michael Jordan.
REINFORCEMENT LEARNING
25
OTROS ASPECTOS IMPORTANTES
• Conexiones con la Psicología Cognitiva y la Neurociencia.
– Los inicios de RL se basan en investigaciones en comportamiento
animal. TD basado en “condicionamiento clásico”.
– Algunos mecanismos del cerebro son muy similares a los algoritmos
RL. “Actividad neuronal dopaminérgica”.
• Resultados Teóricos.
– Resultados de convergencia asintóticos. Algoritmos básicos.
– Cotas de complejidad (muestras finitas): PAC-MDP.
• RL Multiagente.
• Batch Reinforcement Learning.
REINFORCEMENT LEARNING
26
ALGUNAS REFERENCIAS
• LIBROS
– Reinforcement Learning: An Introduction. Sutton R. S. & Barto
A. G. (1998).
– Reinforcement Learning: State-of-the-art. Wiering M. & van
Otterlo M. (2012). { Capítulo 1 }
• TUTORIALES
– Reinforcement Learning: A Survey. Leslie Pack Kaelbling,
Michael L. Littman, Andrew W. Moore. Journal of Artificial
Intelligence Research , 1996
– A tutorial on reinforcement learning techniques. C. H. C.
Ribeiro. Proceedings of International Conference on Neural
Networks, INNS Press, Washington, DC, USA, July 1999.
REINFORCEMENT LEARNING
27
BIBLIOGRAFÍA EXTRA
• Engel, Y., Mannor, S., Meir, R. Reinforcement Learning with Gaussian
Processes. In: Proceedings of the 22nd International Conference on
Machine Learning. Vol. 22. Bonn, Germany, pp. 201–208, August 2005.
• C.E. Rasmussen and M. Kuss. Gaussian Processes in Reinforcement
Learning. Advances in Neural Information Processing Systems 16—Proc.
Ann. Conf. Neural Information Processing Systems, pp. 751-759, 2004.
• Andrew Y. Ng , Michael I. Jordan. PEGASUS: A policy search method for
large MDPs and POMDPs. Proceedings of the 16th Conference on
Uncertainty in Artificial Intelligence, p.406-415, June 30-July 03, 2000
• VIDEOLECTURES.NET TALK.
Rick Sutton. Deconstructing Reinforcement Learning. ICML 2009
http://videolectures.net/icml09_sutton_itdrl/
REINFORCEMENT LEARNING
28
Descargar

Slides