El uso de las opciones dentro del aprendizaje por refuerzo es beneficioso para acelerar el proceso de decisión y ejecución del agente, a la vez que se reduce el riesgo de tomar acciones con recompensas subóptimas en cada uno de los momentos de la ejecución (reduciendo el arrepentimiento), cambiandolas por secuencias de acciones que se extienden en el tiempo a más de un momento de ejecución.
Si bien la definición de las opciones presenta claros beneficios sobre la ejecución de algoritmos de aprendizaje estándar como SARSA o Q-learning, la definición de las opciones va en contradicción del objetivo del aprendizaje por refuerzo. Si definimos las secuencias de las acciones que se deben tomar, podríamos simplemente dar las acciones en la secuencia como instrucciones al agente, y por lo tanto salir del modelo evaluativo a un modelo imperativo del agente.
Por lo tanto, y teniendo en cuenta que el aprendizaje de las políticas es equivalente a aprender una secuencia de acciones a seguir, es natural que podemos aprender cuál es el comportamiento de las opciones a partir de la ejecución de acciones primitivas. En este tutorial cubriremos cinco de las técnicas representativas para la generación de opciones existentes. Estas técnicas incluyen: (1)
la generación manual de opciones [2] y aquellas que requieren conocimiento del dominio [3], (2) el aprendizaje de las opciones [5], (3) la identificación de secuencias que conducen al cumplimiento de subobjetivos [6], (4) la generación automática de todas las combinaciones de acciones, utilizando una capa de aprendizaje adicional para reducir el conjunto completo de opciones generadas, a las más útiles [4] y (5) el aprendizaje de opciones por medio de historias de comportamiento generadas extrayendo las secuencias más utilizadas de acciones primitivas [1].
Finalmente, existen alternativas que combinan dos o más de estas alternativas.
A continuación nos concentramos en las técnicas base para generación de opciones.
El ambiente para el uso de los algoritmos de opciones o macro acciones no requiere ninguna modificación, dado que el aprendizaje de las opciones depende únicamente de la forma en la que el agente adquiere conocimiento sobre las secuencias de acciones a tomar y con ello reducir la cantidad de toma de decisiones y llevando a una mejora en el tiempo de aprendizaje del agente.
Con esto, la definición del ambiente se puede mantener tal como la definición dada en Q-learning.
class Environment:
def __init__(self, board):
self.nrows, self.ncols = len(board),len(board[0])
self.states = [[0 for _ in range(self.ncols)] for _ in range(self.nrows)]
self.initial_state = None
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == 'S':
self.initial_state = (i,j)
elif board[i][j] == "#":
self.states[i][j] = None
elif board[i][j] != ' ':
self.states[i][j] = int(board[i][j])
self.current_state = self.initial_state
self.actions = ['left', 'right', 'up', 'down'] En esta sección nos concentraremos en extender el algoritmo de Q-learning para que los agentes puedan ejecutar secuencias de acciones preestablecidas, y no solo se ejecuten acciones simples como hemos hecho anteriormente. Para esto vamos a extender el algoritmo de Q-learning con la posibilidad de ejecutar opciones.
Como base del desarrollo del agente con opciones vamos a tomar el agente de Q-learning realizado en la semana 7, qlearning_agent.py.
Para la definición de las opciones es necesario definir los estados que comienzan una opción, y la extensión de la ejecución de las opciones. Para ello el agente debe tener un atributo options, definido como una lista de triplas conteniendo: (1) el estado en que inicia la opción, (2) la longitud de la opción y (3) la secuencia de opciones dentro de la opción (como una lista).
Adicionalmente, y como discutiremos más adelante, el agente debe recibir una probabilidad de ejecución de la opción, option_probability.
Note que para poder manejar las opciones, también es necesario modificar la Q-tabla, para que no maneje una lista de valores asociada a las acciones del ambiente, sino que maneje un mapa de valores, donde la llame es el nombre de la acción a ejecutar. Esto es necesario para poder agregar múltiples opciones a los estados.
class Agent:
def __init__(self, env, gamma=0.9, alpha=0.1, epsilon=0.9, o_epsilon=0.1, episodes=1):
#hyper parameters
self.alpha = alpha
self.gamma = gamma
self.epsilon = epsilon
self.environment = env
self.qtable = self.__initdic__() #rewards table
self.episodes = episodes
# Option information
self.option_probability = o_epsilon
self.options = [] #[(o,n,a1a2a3...an), ...(o,m,a1a2....am)]
def __initdic__(self):
table = dict()
# Initialize Q table with 0 for each state-action pair
for state in self.environment.get_states():
table[state] = {a:0 for a in self.environment.get_possible_actions(state)}
return tableAdicionalmente es necesario agregar el comportamiento para agregar opciones al agente, que simplemente recibirá la información como parámetros y los agrega a la lista de opciones.
def add_option(self, state, length, action_list):
self.options.append((state,length, action_list))
self.qtable[state][str(action_list)] = 0El otro cambio necesario para la ejecución del agente teniendo en cuenta opciones, está en la ejecución del agente, puesto que ahora se deben tener en cuenta las opciones. La diferencia entre la ejecución de Q-learning conocida, es que al ejecutar una opción, no se calculan los q-valores al ejecutar cada acción, sino que se calcula la recompensa total descontada de ejecutar todas las acciones dentro de la opción.
La primera modificación a la ejecución del agente, la función run, está en la decisión de la ejecución de las opciones. Para mantener aleatoriedad y ejecución de la mejor secuencia de acciones, las opciones ejecutarán con probabilidad option_probability y ejecutarán el proceso regular de Q-learning con probabilidad 1 - option_probability. Claramente la ejecución de las opciones únicamente debe suceder si el agente se encuentra en un estado de inicio de la opción
A continuación mostramos los cambios necesarios en la función run. Como se mencionó anteriormente debemos ser capaces de ejecutar las opciones. Cuando se toma este camino, la opción se debe ejecutar en su totalidad, tomando como recompensa de la opción, la recompensa acumulada con descuento (cum_reward = self.gamma*cum_reward + reward) de todas las acciones ejecutadas. Luego, con este valor de la recompensa se calcula el nuevo Q-valor para el estado dado y la ejecución de la opción.
def run(self):
for counter in range(self.episodes):
...
option_state = set([state for state, _, _ in self.options])
if current_state in option_state and random.uniform(0,1) < self.option_probability:
state, n, al = self.get_option(current_state)
cum_reward = 0
for i in range(n):
next_state, reward, done, info = self.step(al[i])
cum_reward = self.gamma*cum_reward + reward
old_value = self.qtable[current_state][str(al)]
next_max = max(self.qtable[next_state].values())
new_value = (1 - self.alpha)*old_value + self.alpha*(cum_reward + self.gamma*next_max)
self.qtable[current_state][str(al)] = new_value
else:
...
action_index = self.actions_index(current_state, action)
if action_index > len(self.environment.actions):
actions = ast.literal_eval(action)
reward = 0
for a in actions:
next_state, s_reward, done, info = self.step(a)
reward = self.gamma*reward + s_reward
else:
next_state, reward, done, info = self.step(action)
...
return self.qtable
Teniendo en cuenta que las opciones son "acciones" que se pueden escoger dentro del proceso regular de Q-learning, debemos asegurarnos que al escoger una opción, también se ejecute toda la secuencia de acciones definidas por la opción, acumulando su recompensa con descuento y actualizando el valor en la Q-tabla.
Ejecute el algoritmo (run.py) con opciones utilizando diferentes ambientes y la definición de diferentes opciones para observar su comportamiento. ¿Qué puede concluir del proceso de aprendizaje?
[1] S. Girgin and F. Polat. "Option Discovery in Reinforcement Learning using Frequent Common Subsequences of Actions". In: International Conference on Computational Intelligence for Modelling, Control and Automation and International Conference on Intelligent Agents, Web Technologies and Internet Commerce. Volume 1. CIMCA-IAWTIC'06. 2005, pages 371–376.
[2] S. Elfwing, E. Uchibe, K. Doya, and H. I. Christensen. "Multi-agent reinforcement learning: using macro actions to learn a mating task". In: IEEE/RSJ International Conference on Intelligent Robots and Systems. Volume 4. IROS'04. Sept. 2004, pages 3164–3169.
[3] Amy McGovern and Richard S. Sutton. Macro-Actions in Reinforcement Learning: An Empirical Analysis. Technical report. Amherst, MA, USA, 1998.
[4] Marc Pickett and Andrew G. Barto. "PolicyBlocks: An Algorithm for Creating Useful Macro-Actions in Reinforcement Learning". In: Int. Conference on Machine Learning. Morgan Kaufmann, 2002, pages 506–513.
[5] Jette Randløv. "Learning Macro-actions in Reinforcement Learning". In: Proceedings of the International Conference on Neural Information Processing Systems. NIPS'98. Denver, CO: MIT Press, 1998, pages 1045–1051. url: http://dl.acm.org/citation.cfm?id=3009055.3009201.
[6] Martin Stolle and Doina Precup. "Learning Options in Reinforcement Learning". In: Proceedings of the International Symposium on Abstraction, Reformulation and Approximation. Berlin, Heidelberg: Springer-Verlag, 2002, pages 212–223. isbn: 3540439412.
[7] Steven J. Bradtke and Michael O. Duff. Reinforcement learning methods for continuous-time Markov decision problems. In G. Tesauro, D. Touretzky, and T. Leen, editors, Advances in Neural Information Processing Systems, volume 7, pages 393–400. The MIT Press, 1995.
© - Derechos Reservados: La presente obra, y en general todos sus contenidos, se encuentran protegidos por las normas internacionales y nacionales vigentes sobre propiedad Intelectual, por lo tanto su utilización parcial o total, reproducción, comunicación pública, transformación, distribución, alquiler, préstamo público e importación, total o parcial, en todo o en parte, en formato impreso o digital y en cualquier formato conocido o por conocer, se encuentran prohibidos, y solo serán lícitos en la medida en que se cuente con la autorización previa y expresa por escrito de la Universidad de los Andes.
De igual manera, la utilización de la imagen de las personas, docentes o estudiantes, sin su previa autorización está expresamente prohibida. En caso de incumplirse con lo mencionado, se procederá de conformidad con los reglamentos y políticas de la universidad, sin perjuicio de las demás acciones legales aplicables.
Nicolás Cardozo, Profesor Asociado
Camilo Cabrera, Tutor
Facultad de Ingeniería
Departamento de Ingeniería de Sistemas y Computación
Universidad de los Andes
Bogotá, Colombia
Enero, 2023