Título: Aprendiendo políticas de exploración generales para escalar la síntesis de controladores discretos.
Director: Sebastian Uchitel
Jurados: Agusting Gravano y Pablo Riera

Resumen:
El área de síntesis de controladores discretos estudia la construcción automática de estrategias de comportamiento con garantías de correctitud, para sistemas descriptos formalmente por autómatas. La limitación de estas técnicas viene dada por la maldición de la dimensionalidad, que hace que el tamaño de los autómatas crezca muy velozmente y restringe la aplicabilidad. La síntesis on-the-fly busca eludir esta problemática construyendo el espacio de estados parcialmente, agregando una transición a la vez desde el estado inicial del sistema e intentando explorar solo lo necesario para la estrategia ganadora, o para mostrar que tal estrategia no existe.
En esta tesis desarrollamos un primer método para aprender una heurística que guı́e la exploración a partir de la experiencia. En primer lugar, definimos una tarea de aprendizaje por refuerzo para la cual el agente representa una política de exploración. Luego, mostramos una forma de usar Q-Learning abstrayendo tanto estados como acciones en un conjunto de features. Esta abstracción hace posible el aprendizaje y la generalización, pero genera un alto grado de observabilidad parcial. La evaluación empírica muestra que, a pesar de la falta de garantías teóricas de convergencia, es posible aprender consistentemente políticas competitivas en las instancias de entrenamiento. Más aún, las políticas inducidas en instancias grandes superan en promedio a la mejor heurı́stica desarrollada por humanos, empujando la frontera de problemas resueltos en algunos de los dominios del benchmark utilizado.