Agosto de 2018
Volumen 33, número 8
Serie de pruebas: introducción a Q-Learning con C#
Por James McCaffrey
.jpg "James McCaffrey")
Refuerzo (RL) de aprendizaje es una rama del aprendizaje automático que aborda problemas donde no hay ningún dato de aprendizaje explícita con valores de salida correctos conocidos. Q-learning es un algoritmo que puede utilizarse para resolver algunos tipos de problemas RL. En este artículo, explican el funcionamiento de Q-learning y proporciona un programa de ejemplo.
La mejor forma de ver dónde se dirige este artículo es echar un vistazo en el laberinto simple en figura 1 y el programa de demostración asociado en figura 2. El laberinto de 3 x 4 tiene 12 celdas, numeradas de 0 a 11. El objetivo es obtener de en la esquina inferior izquierda de la celda 8 a 11 de la celda en la esquina inferior derecha, en el menor número de movimientos. Puede mover a la izquierda, derecha, arriba o hacia abajo, pero no en diagonal.
.png "Problema de laberinto simple")
Figura 1 laberinto Simple problema
.png "Programa de demostración de Q-Learning")
Figura 2 programa de demostración de Q-Learning
El programa de demostración establece una representación de laberinto en memoria y, a continuación, usa el algoritmo de aprendizaje de preguntas y encontrar una matriz de preguntas Y. Preguntas y es el acrónimo de calidad, que son mejores valores más grandes. Los índices de fila son las celdas "from" y los índices de columna son las celdas "hasta". Si la celda inicial es 8, análisis, a continuación, esa fila muestran que el mayor valor de p es 0,44 en 9 a la celda. A continuación, desde la celda 9, el valor más grande en la fila es 1,08 en 5 para la celda. El proceso continúa hasta que el programa alcanza el estado de objetivo en la celda 11.
No es probable, deberá escribir código que resuelve un laberinto, pero se trata de Hello World de Q-learning porque es fácil de comprender el problema. Explicaré cómo puede generalizar Q-learning para los problemas más realistas más adelante en este artículo.
En este artículo se da por supuesto que tiene conocimientos de programación, pero no se supone que sepa nada acerca de Q-learning. El programa de demostración se codifica con C#, pero no debería resultar demasiado difícil refactorizarlo a otro lenguaje, como Visual Basic o Python. El código del programa de demostración se presenta en su totalidad en este artículo y también está disponible en la descarga del archivo adjunto.
El código
Para mí, al menos, Q-learning es un poco inusual porque creo que los conceptos se entienden mejor mediante el examen de código de demostración específica en lugar de a partir de los principios generales. La estructura general del programa de demostración, con algunos cambios menores para ahorrar espacio, se muestra en la Figura 3.
Figura 3 estructura del programa de demostración de Q-Learning
using System;
using System.Collections.Generic;
namespace QLearning
{
class QLearningProgram
{
static Random rnd = new Random(1);
static void Main(string[] args)
{
Console.WriteLine("Begin Q-learning maze demo");
Console.WriteLine("Setting up maze and rewards");
int ns = 12;
int[][] FT = CreateMaze(ns);
double[][] R = CreateReward(ns);
double[][] Q = CreateQuality(ns);
Console.WriteLine("Analyzing maze using Q-learning");
int goal = 11;
double gamma = 0.5;
double learnRate = 0.5;
int maxEpochs = 1000;
Train(FT, R, Q, goal, gamma, learnRate, maxEpochs);
Console.WriteLine("Done. Q matrix: ");
Print(Q);
Console.WriteLine("Using Q to walk from cell 8 to 11");
Walk(8, 11, Q);
Console.WriteLine("End demo");
Console.ReadLine();
}
static void Print(double[][] Q) { . . }
static int[][] CreateMaze(int ns) { . . }
static double[][] CreateReward(int ns) { . . }
static double[][] CreateQuality(int ns) { . . }
static List<int> GetPossNextStates(int s,
int[][] FT) { . . }
static int GetRandNextState(int s, int[][] FT) { . . }
static void Train(int[][] FT, double[][] R, double[][] Q,
int goal, double gamma, double lrnRate,
int maxEpochs) { . . }
static void Walk(int start, int goal, double[][] Q) { . . }
static int ArgMax(double[] vector) { . . }
} // Program
} // ns
Para crear el programa de demostración, inicié Visual Studio y crea un nuevo proyecto de aplicación de consola de C# denominado QLearning. He usado Visual Studio 2017, pero la demostración no tiene ninguna dependencia significativa de .NET para cualquier versión de Visual Studio funcionará correctamente. Después de carga el código de plantilla en el editor que quité todas innecesarios mediante instrucciones, dejé solo la referencia al espacio de nombres del sistema. A continuación, agregué una referencia al espacio de nombres Collections.Generic porque la demostración usa una colección List < int >.
El programa de demostración tiene un objeto Random de ámbito de clase dado Q-learning implica un componente de la selección aleatoria, como verá en breve. Variable ns significa el número de Estados, que es el sinónimo con el número de celdas en el laberinto. Objeto FT (transiciones factibles) es una matriz de matrices de estilo matriz. Matriz de R es la matriz de recompensa y matriz Q es la matriz de calidad.
El algoritmo de Q-learning requiere learnRate y gamma de parámetros (también conocido como el factor de descuento). Explicaré más adelante. Q-learning es iterativo, por lo que la demostración establece una variable maxEpochs para controlar cuánto puede usar el algoritmo para encontrar la matriz Q.
Configurar el laberinto y las recompensas
Se crea el laberinto método CreateMaze, que se define como sigue:
static int[][] CreateMaze(int ns) {
int[][] FT = new int[ns][];
for (int i = 0; i < ns; ++i) FT[i] = new int[ns];
FT[0][1] = FT[0][4] = FT[1][0] = FT[1][5] = FT[2][3] = 1;
FT[2][6] = FT[3][2] = FT[3][7] = FT[4][0] = FT[4][8] = 1;
FT[5][1] = FT[5][6] = FT[5][9] = FT[6][2] = FT[6][5] = 1;
FT[6][7] = FT[7][3] = FT[7][6] = FT[7][11] = FT[8][4] = 1;
FT[8][9] = FT[9][5] = FT[9][8] = FT[9][10] = FT[10][9] = 1;
FT[11][11] = 1; // Goal
return FT;
}
El método devuelve una matriz que define los movimientos permitidos. Por ejemplo, puede mover de celda de 4 a 8 de la celda, pero no se puede mover de celda de 4 a 5 de la celda porque no hay una pared de la forma. Recuerde que C# inicializa las matrices de int a 0, por lo que debe especificar solo los movimientos permitidos CreateMaze. Tenga en cuenta que no se puede mover de una celda a sí mismo, excepto la celda de objetivo 11.
La matriz de recompensas se define mediante:
static double[][] CreateReward(int ns) {
double[][] R = new double[ns][];
for (int i = 0; i < ns; ++i) R[i] = new double[ns];
R[0][1] = R[0][4] = R[1][0] = R[1][5] = R[2][3] = -0.1;
R[2][6] = R[3][2] = R[3][7] = R[4][0] = R[4][8] = -0.1;
R[5][1] = R[5][6] = R[5][9] = R[6][2] = R[6][5] = -0.1;
R[6][7] = R[7][3] = R[7][6] = R[7][11] = R[8][4] = -0.1;
R[8][9] = R[9][5] = R[9][8] = R[9][10] = R[10][9] = -0.1;
R[7][11] = 10.0; // Goal
return R;
}
En este ejemplo, puede pasar a la celda del objetivo 11 ofrece una recompensa de 10.0, pero ningún otro movimiento proporciona una recompensa negativa de -0.1. Estos valores son un poco arbitrarios. En general, cuando se trabaja con RL, la estructura de recompensa es totalmente dependiente del problema. Aquí, la recompensa negativa pequeña punishes cada movimiento un poco, que tiene el efecto de preferir las rutas de acceso más cortas a través de las rutas de acceso más largas que el objetivo. Tenga en cuenta que no tiene que establecer un premio por movimientos que no están permitidos ya que nunca se realizará.
Es el objetivo de Q-learning buscar el valor de la matriz de Q. Inicialmente, todos los valores de Q se establecen en 0,0 y se crea la matriz de preguntas y así:
static double[][] CreateQuality(int ns) {
double[][] Q = new double[ns][];
for (int i = 0; i < ns; ++i)
Q[i] = new double[ns];
return Q;
}
Definir los Estados posibles siguiente
Como verá en breve, el algoritmo de aprendizaje de preguntas y debe saber lo que indica que el sistema puede realizar la transición, reciben el estado actual. En este ejemplo, un estado del sistema es la misma que la ubicación en el laberinto por lo que solo hay 12 Estados. Método GetPossNextStates se define así:
static List<int> GetPossNextStates(int s, int[][] FT) {
List<int> result = new List<int>();
for (int j = 0; j < FT.Length; ++j)
if (FT[s][j] == 1) result.Add(j);
return result;
}
Por ejemplo, si el estado actual de s es 5, GetPossNextStates devuelve una colección List < int > que contiene (1, 6, 9). El algoritmo de aprendizaje de preguntas y a veces se pasa desde el estado actual al estado siguiente aleatorio. Esta funcionalidad está definida por el método GetRandNextState:
static int GetRandNextState(int s, int[][] FT) {
List<int> possNextStates = GetPossNextStates(s, FT);
int ct = possNextStates.Count;
int idx = rnd.Next(0, ct);
return possNextStates[idx];
}
Por lo tanto, si el estado actual de s es 5, a continuación, GetRandNextState devuelve 1 o 9 ó 6 con la misma probabilidad (0,33 cada).
El algoritmo de Q-Learning
La ecuación de actualización de la clave de Q-learning se basa en la ecuación matemática de Bellman y se muestra en la parte inferior de la figura 1. El algoritmo se implementa en el método Train. En pseudocódigo de alto nivel, el algoritmo de aprendizaje de Q es:
loop maxEpochs times
set currState = a random state
while currState != goalState
pick a random next-state but don't move yet
find largest Q for all next-next-states
update Q[currState][nextState] using Bellman
move to nextState
end-while
end-loop
El algoritmo no es obvio, y para mí, se entiende mejor al examinar el código. La definición comienza así:
static void Train(int[][] FT, double[][] R, double[][] Q,
int goal, double gamma, double lrnRate, int maxEpochs)
{
for (int epoch = 0; epoch < maxEpochs; ++epoch) {
int currState = rnd.Next(0, R.Length);
...
El número de épocas de entrenamiento debe determinarse mediante prueba y error. Es un diseño alternativo recorrer en iteración hasta que no cambian los valores de la matriz de preguntas Y, o hasta que estabilice a muy pequeños cambios por cada iteración. El bucle interior recorre en iteración hasta que el estado actual se convierte en el estado del objetivo, 11 de la celda en el caso de laberinto de demostración:
while (true) {
int nextState = GetRandNextState(currState, FT);
List<int> possNextNextStates = GetPossNextStates(nextState, FT);
double maxQ = double.MinValue;
for (int j = 0; j < possNextNextStates.Count; ++j) {
int nns = possNextNextStates[j]; // short alias
double q = Q[nextState][nns];
if (q > maxQ) maxQ = q;
}
...
Imagine que tiene en un laberinto. Verá que puede ir a las tres distintas habitaciones, A, B, C. Elegir B, pero aún no se mueven. Puede formular un amigo para entrar en el salón B y friend indica que desde la habitación B puede ir a salones de X, Y, Z y las salas Y tiene el mejor valor Q. En otras palabras, Y es el mejor estado siguiente siguiente.
Se realiza la actualización de la matriz de preguntas Y:
...
Q[currState][nextState] =
((1 - lrnRate) * Q[currState][nextState]) +
(lrnRate * (R[currState][nextState] + (gamma * maxQ)));
currState = nextState;
if (currState == goal) break;
} // while
} // for
} // Train
La ecuación de actualización consta de dos partes. La primera parte, ((1-lrnRate) * Q[currState][nextState]), se llama el componente de vulnerabilidad de seguridad y agrega una fracción del valor anterior. La segunda parte, (lrnRate * (R [currState] [nextState] + (gamma * maxQ))), se llama el componente de exploración. Los valores mayores del aumento lrnRate la influencia de recompensas actuales y futuras recompensas (exploración) a costa de los últimos recompensas (vulnerabilidad de seguridad). El valor de gamma, el factor de descuento, influye en la importancia de recompensas futuras.
Uso de la matriz de preguntas y
Después de la calidad que se calculó matriz, se puede usar para encontrar una ruta de acceso óptimo desde cualquier estado inicial en el estado de objetivo. Método recorrer implementa esta funcionalidad:
static void Walk(int start, int goal, double[][] Q) {
int curr = start; int next;
Console.Write(curr + "->");
while (curr != goal) {
next = ArgMax(Q[curr]);
Console.Write(next + "->");
curr = next;
}
Console.WriteLine("done");
}
Tenga en cuenta que el método supone que el estado del objetivo es accesible desde el estado inicial. El método usa auxiliar ArgMax para encontrar el mejor estado siguiente:
static int ArgMax(double[] vector) {
double maxVal = vector[0]; int idx = 0;
for (int i = 0; i < vector.Length; ++i) {
if (vector[i] > maxVal) {
maxVal = vector[i]; idx = i;
}
}
return idx;
}
Por ejemplo, si un vector tiene valores (0,5, 0.3, 0,7, 0,2) ArgMax devuelve 2. La demostración define un método de impresión para mostrar la matriz de Q. Puede obtener la versión de impresión con sangría en la descarga del archivo adjunto. Es una versión simplificada:
static void Print(double[][] Q) {
int ns = Q.Length;
Console.WriteLine("[0] [1] . . [11]");
for (int i = 0; i < ns; ++i) {
for (int j = 0; j < ns; ++j) {
Console.Write(Q[i][j].ToString("F2") + " ");
}
Console.WriteLine();
}
}
Resumen
El ejemplo de Q-learning presentado aquí debería proporcionarle una buena comprensión de los principios principales implicados. El escenario del problema presentado en este artículo es uno con Estados discretos, pero Q-learning puede trabajar con los Estados continua, demasiado. El desafío general es maximizar la recompensa a largo plazo, que el ejemplo de laberinto es el mismo como introducción al estado de objetivo en el menor número de movimientos. Q-learning puede ser útil cuando puede entrenar un sistema con muchas pruebas, como un robot industrial de entrenamiento para realizar una tarea de forma segura. Pero no es aplicable en escenarios como entrenamiento cómo navegar por el tráfico de un automóvil sin conductor Q-learning. Q-learning y RL Recordármelo ligeramente de las redes neuronales en la década de 1980, existen relativamente pocas aplicaciones prácticas ahora mismo, pero hay esfuerzos de investigación intensa. Muchos de mis colegas creen que en algún punto de RL se puede ampliar en utilidad de manera inesperada.
El Dr. James McCaffrey trabaja para Microsoft Research en Redmond, Washington. Ha colaborado en el desarrollo de varios productos de Microsoft como, por ejemplo, Internet Explorer y Bing. Puede ponerse en contacto con el Dr. McCaffrey en jamccaff@microsoft.com.
Gracias a los siguientes expertos técnicos de Microsoft por revisar este artículo: Asli Celikyilmaz, Chris Lee, Ricky Loynd, Amr Sharaf, Ken Tran