Agosto de 2019
Volumen 34, número 8
[Serie de pruebas]
El algoritmo UCB1 para problemas Multi-Armed Bandit
Por James McCaffrey
.jpg "James McCaffrey")
Imagine que está en un casino enfrente de tres máquinas tragaperras. Tiene 30 fichas. Cada máquina da premios según una distribución de probabilidad diferente y no conoce las distribuciones. Nuestro objetivo es encontrar rápidamente la mejor máquina para que pueda optimizar la cantidad de dinero que gana. Este es un ejemplo de problema Multi-Armed Bandit, denominado así porque, informalmente, en inglés, las máquinas tragaperras también se denominan one-armed bandits.
En su entorno de trabajo diario, es poco probable que tenga que trabajar con máquinas tragaperras de casino. Pero el escenario Multi-Armed Bandit se aplica a muchos problemas reales. Por ejemplo, una empresa farmacéutica que tiene tres nuevos medicamentos para una afección médica debe determinar qué medicamento es el más eficaz con un número mínimo de ensayos clínicos con seres humanos. Y una campaña de publicidad en línea con varios enfoques debe determinar qué enfoque maximiza los ingresos lo antes posible.
Existen muchos algoritmos diferentes que pueden usarse para un problema Multi-Armed Bandit. El algoritmo UCB1 (límite de confianza superior, versión 1) es uno de los más sofisticados desde el punto de vista matemático, pero, sorprendentemente, es uno de los más fáciles de implementar. Una buena manera de comprender qué es el algoritmo UCB1 y ver el camino que va a tomar este artículo es echar un vistazo al programa de demostración de la figura 1.
.png "Ejecución de demostración del algoritmo UCB1")
Figura 1 Ejecución de demostración del algoritmo UCB1
La demostración configura tres máquinas con un índice basado en 0, cada una con una probabilidad de ganar diferente. Las tres probabilidades son (0,3; 0,7; 0,5), por lo que la máquina 1 es la mejor. Cada vez que se baja una palanca, si una máquina gana, paga 1 USD, mientras que, si pierde, paga 0 USD. El algoritmo UBC1 empieza a jugar en cada máquina una vez. En la demostración, las máquinas [0] y [1] ganaron, pero la [2] perdió.
El algoritmo UCB1 es iterativo. La demostración especifica seis pruebas después de los intentos de inicialización. En la primera prueba, el algoritmo calcula el premio promedio para cada máquina. Dado que las máquinas [0] y [1] ganaron en la fase de inicialización, su premio promedio actual es de 1,00 USD / 1 intento = 1,00 USD. Dado que la máquina [2] perdió, su premio promedio actual es de 0,00 USD / intento = 0,00 USD.
Los premios promedio actuales y el número de prueba actual se usan de forma ingeniosa para calcular un valor de decisión para cada máquina. Para la prueba n.º 1, los valores de coinciden con los premios promedio. La palanca o la máquina en la que hay que jugar es la que tiene un mayor valor de decisión. En este punto, las máquinas [0] y [1] están vinculadas con el mayor valor de decisión. La máquina [0] se selecciona arbitrariamente, en lugar de la máquina [1]. A continuación, se juega con la máquina [0], pero se pierde.
En la prueba n.º 2, el premio promedio actualizado para la máquina [0] es 1,00 USD / 2 intentos = 0,50 USD. El promedio de premios para las máquinas [1] y [2] sigue siendo 1,00 USD y 0,00 USD, respectivamente, porque no se ha jugado con ninguna máquina. Los valores de decisión se calculan como (1,33; 2,18; 1,18), por lo que se selecciona la máquina [1] y gana.
El proceso continúa hasta la prueba n.º 6. En ese momento, el algoritmo UCB1 parece ser correcto porque la máquina [1], la mejor máquina, es la que se ha usado para jugar más veces (4) y tiene el mayor premio promedio (0,75 USD).
El algoritmo UCB1 es bastante inteligente. Observe la prueba n.º 5 en la figura 1. Los premios acumulativos son (1,00 USD, 3,00 USD, 0,00 USD) y el número de veces que se ha jugado con las máquinas es (2, 4, 1). Por lo tanto, la máquina [2] no se ha probado desde su pérdida inicial en la fase de inicialización. Un algoritmo poco sofisticado seguiría seleccionando la máquina [0] o [1], pero UCB1 hace balance entre la exploración de las características de la máquina y el aprovechamiento de la mejor máquina que se encuentra y selecciona la máquina [2].
El algoritmo UCB1 está diseñado específicamente para los problemas de tragaperras con valores de pago de 0 o 1. Esto se denomina proceso de Bernoulli. UCB1 puede aplicarse a otros tipos de problemas, como uno donde el pago sigue una distribución gaussiana. Pero cuanto más se diferencia la distribución de pago de Bernoulli, peor es el rendimiento del algoritmo UCB1. No recomiendo UCB1 para problemas distintos de Bernoulli, pero algunos de mis compañeros creen que UCB1 puede tener éxito si se usa de manera conservadora.
La información de este artículo se basa en el artículo de investigación de 2002 titulado "Finite-Time Analysis of the Multiarmed Bandit Problem" (Análisis de tiempo finito del problema Multi-Armed Bandit), por P. Auer, N. Cesa-Bianchi y P. Fischer P. Además de UCB1, el artículo presenta un algoritmo denominado UCB-Normal pensado para usarse con problemas Multi-Armed Bandit de distribución gaussiana.
En este artículo se asume que tiene conocimientos intermedios o altos de programación con C# o un lenguaje de la familia C, como Python o Java, pero no que sepa nada acerca del algoritmo UCB1. La demostración se programó en C#, pero no debería tener problemas para refactorizar el código a otro lenguaje si lo desea. En este artículo se presenta el código de demostración completo. El código fuente también está disponible en la descarga complementaria.
Reconocimiento del algoritmo UCB1
La clave para el algoritmo UCB1 es una función que convierte un conjunto de premios promedio en la prueba t en un conjunto de valores de decisión, que, a continuación, se usan para determinar en qué máquina se debe jugar. La ecuación se muestra en la figura 2. En otras palabras, en la prueba t, seleccione la palanca a, entre todas las palancas, que tiene el mayor premio promedio (r-hat) más el límite de confianza superior (término de la raíz cuadrada). En este caso, n(a) es el número de veces que se ha bajado una palanca.
.png "Ecuación clave para UCB1")
Figura 2 Ecuación clave para UCB1
La ecuación es más sencilla de lo que parece y se explica mejor con un ejemplo. Supongamos que, como en la demostración, el algoritmo está en la prueba t = 5, los premios acumulativos son (1,00; 3,00; 0,00) y los recuentos de palanca son (2, 4, 1). El primer paso es calcular el premio promedio para cada palanca: (1,00 / 2; 3,00 / 4; 0,00 / 1) = (0,50; 0,75; 0,00). A continuación, el valor de decisión para la palanca [0] se calcula como:
decision[0] = 0.50 + sqrt( 2 * ln(5) / 2 )
= 0.50 + sqrt(1.61)
= 0.50 + 1.27
= 1.77
De forma similar, los valores de decisión para las palancas [1] y [2] son:
decision[1] = 0.75 + sqrt( 2 * ln(5) / 4 )
= 0.75 + sqrt(0.80)
= 0.75 + 0.90
= 1.65
decision[2] = 0.00 + sqrt( 2 * ln(5) / 1 )
= 0.00 + sqrt(3.22)
= 0.00 + 1.79
= 1.79
Dado que el número de veces que se ha bajado la palanca es el denominador de la parte de fracción del término del límite de confianza superior, los valores pequeños aumentan el valor de decisión. Esto permite que las palancas que apenas se bajan puedan llegar a tener una oportunidad contra las palancas con un premio promedio alto. Bien.
Programa de demostración
El programa de demostración completo, con ediciones menores para ahorrar espacio, se presenta en la Figura 3. Para crear el programa, inicié Visual Studio y creé una nueva aplicación de consola denominada BanditUCB. Usé Visual Studio 2017, pero la demostración no tiene ninguna dependencia significativa de .NET Framework.
Figura 3 Programa de demostración del algoritmo UCB1
using System;
namespace BanditUCB
{
class BanditProgram
{
static void Main(string[] args)
{
Console.WriteLine("Begin UCB1 bandit demo \n");
Console.WriteLine("Three arms with true means u1 = " +
"0.3, u2 = 0.7, u3 = 0.5");
Random rnd = new Random(20);
int N = 3;
int trials = 6;
double p = 0.0;
double[] means = new double[] { 0.3, 0.7, 0.5 };
double[] cumReward = new double[N];
int[] armCounts = new int[N];
double[] avgReward = new double[N];
double[] decValues = new double[N];
// Play each arm once to get started
Console.WriteLine("Playing each arm once: ");
for (int i = 0; i < N; ++i) {
Console.Write("[" + i + "]: ");
p = rnd.NextDouble();
if (p < means[i]) {
Console.WriteLine("win");
cumReward[i] += 1.0;
}
else {
Console.WriteLine("lose");
cumReward[i] += 0.0;
}
++armCounts[i];
}
Console.WriteLine("-------------");
for (int t = 1; t <= trials; ++t) {
Console.WriteLine("trial #" + t);
Console.Write("curr cum reward: ");
for (int i = 0; i < N; ++i)
Console.Write(cumReward[i].ToString("F2") + " ");
Console.Write("\ncurr arm counts: ");
for (int i = 0; i < N; ++i)
Console.Write(armCounts[i] + " ");
Console.Write("\ncurr avg reward: ");
for (int i = 0; i < N; ++i) {
avgReward[i] = (cumReward[i] * 1.0) / armCounts[i];
Console.Write(avgReward[i].ToString("F2") + " ");
}
Console.Write("\ndecision values: ");
for (int i = 0; i < N; ++i) {
decValues[i] = avgReward[i] +
Math.Sqrt( (2.0 * Math.Log(t) / armCounts[i]) );
Console.Write(decValues[i].ToString("F2") + " ");
}
int selected = ArgMax(decValues);
Console.WriteLine("\nSelected machine = [" +
selected + "]");
p = rnd.NextDouble();
if (p < means[selected]) {
cumReward[selected] += 1.0;
Console.WriteLine("result: a WIN");
}
else {
cumReward[selected] += 0.0;
Console.WriteLine("result: a LOSS");
}
++armCounts[selected];
Console.WriteLine("-------------");
} // t
Console.WriteLine("End bandit UCB1 demo ");
Console.ReadLine();
} // Main
static int ArgMax(double[] vector)
{
double maxVal = vector[0];
int result = 0;
for (int i = 0; i < vector.Length; ++i) {
if (vector[i] > maxVal) {
maxVal = vector[i];
result = i;
}
}
return result;
}
} // Program
} // ns
Después de cargar el código de plantilla, en la parte superior de la ventana del editor, quité todas las referencias al espacio de nombres innecesarias y solo dejé la referencia al espacio de nombres del sistema de nivel superior. En la ventana Explorador de soluciones, hice clic con el botón derecho en el archivo Program.cs, le cambié el nombre por uno más descriptivo (BanditProgram.cs) y permití que Visual Studio cambiase automáticamente el nombre de la clase Program.
Se han eliminado todas las comprobaciones de errores normales para mantener las ideas principales lo más claras posible. El método Main contiene toda la lógica de control. Hay una función auxiliar única denominada ArgMax que devuelve el índice del valor mayor en una matriz numérica. Por ejemplo, si una matriz contiene valores (5,0; 7,0; 2,0; 9,0), ArgMax devuelve 3.
Configuración de UCB1
El programa de demostración empieza con estas instrucciones:
Random rnd = new Random(20);
int N = 3;
int trials = 6;
double p = 0.0;
double[] means = new double[] { 0.3, 0.7, 0.5 };
El objeto Random se usa para determinar si una máquina seleccionada gana o pierde. El valor de inicialización, 20, se usa solo porque proporciona una demostración representativa. La matriz llamada means podría tener un nombre similar a probsWin, en lugar del actual. Pero, dado que cada máquina paga 1 USD o 0 USD, el valor promedio (medio) para cada máquina es igual que la probabilidad de ganar. Por ejemplo, si la probabilidad de ganar de una máquina es 0,6 y juega a la máquina 1000 veces, esperaría ganar 1 USD aproximadamente 600 veces. El valor medio por intento es 600 USD/ 1000 = 0,60.
Cálculo de los valores de decisión
El programa de demostración calcula los valores de decisión mediante una asignación directa a la ecuación UCB1 en la figura 2:
for (int i = 0; i < N; ++i) {
decValues[i] = avgReward[i] +
Math.Sqrt( (2.0 * Math.Log(t) / armCounts[i]) );
Console.Write(decValues[i] + " ");
}
El cálculo iniciará una excepción si t = 0 (el registro de 0 es infinito negativo) o si cualquier número de palanca es 0 (división por 0). Sin embargo, la fase de inicialización de UCB1 donde cada máquina se intenta una vez impide cualquiera de las condiciones de excepción.
Una vez calculados los valores de decisión, la máquina en la que se jugará viene determinada por esta instrucción:
int selected = ArgMax(decValues);
Console.WriteLine("Selected machine = [" + selected + "]");
La función ArgMax devuelve el índice del valor mayor de decisión. Si dos o más valores de decisión están vinculados como más grande, ArgMax devuelve el primer índice que encuentra. Esto presenta un pequeño sesgo para las máquinas con una indexación inferior. Un enfoque para eliminar este sesgo sería refactorizar ArgMax para que, en caso de vínculo, se elija uno de los índices vinculados aleatoriamente.
El algoritmo Epsilon-Greedy
El algoritmo UCB1 está estrechamente relacionado con otro algoritmo para Multi-Armed Bandit denominado epsilon-greedy. Para empezar, el algoritmo epsilon-greedy especifica un pequeño valor para épsilon. A continuación, en cada prueba, se genera un valor de probabilidad aleatorio entre 0,0 y 1,0. Si la probabilidad generada es menor que (1 - épsilon), se selecciona la palanca con el mayor premio promedio. En caso contrario, se selecciona una palanca de forma aleatoria. Una implementación de epsilon-greedy basada en la estructura del programa de demostración podría tener un aspecto similar a este:
//int selected = ArgMax(decValues); // UCB1
double epsilon = 0.05; // Epsilon-greedy
int selected;
double pr = rnd.NextDouble(); // [0.0, 1.0)
if (pr < (1 - epsilon))
selected = ArgMax(avgReward); // Usually
else
selected = rnd.Next(0, N); // 5% of the time
Una de diversas variantes del algoritmo epsilon-greedy básico consiste en reducir el valor de épsilon con el tiempo. Esto tiene el efecto de concentrarse en la exploración al principio de la ejecución y, a continuación, hacer énfasis en la explotación de la mejor palanca, más adelante en la ejecución. El mayor problema con epsilon-greedy es que no hay ninguna manera fácil de determinar un buen valor para épsilon.
En mi opinión, los resultados de las investigaciones que comparan UCB1 con epsilon-greedy y otros muchos algoritmos Multi-Armed Bandit no son concluyentes. Según mi experiencia, no hay ningún algoritmo único y coherente que sea mejor utilizar y, si es posible, es recomendable ejecutar algunos experimentos con algoritmos diferentes mediante una simulación del problema real.
El método estándar para comparar diferentes algoritmos Multi-Armed Bandit es calcular una métrica de pesar. El pesar es la diferencia entre el valor que se esperaba en el sistema, asumiendo que sabe cuál es la mejor palanca, y el valor real del sistema en los experimentos. Por ejemplo, suponga que jugó a las tres máquinas del sistema de demostración 10 veces y que ganó seis veces y perdió cuatro veces. La recompensa total es 6,00 USD. Pero si, hipotéticamente, bajó la mejor palanca (con una probabilidad de ganar del 0,7) las 10 veces, la recompensa promedio total sería de 7,00 USD. Por lo tanto, el pesar es 7,00 USD - 6,00 USD = 1,00 USD.
Resumen
Mentalmente, organizo el aprendizaje automático en tres categorías: aprendizaje supervisado, donde tiene datos de aprendizaje con respuestas conocidas y correctas; aprendizaje no supervisado, donde tiene datos sin respuestas correctas; y aprendizaje de refuerzo (RL), donde un resultado correcto o incorrecto se llama premio (que podría ser negativo) y procede de una función, en lugar de datos. Los problemas Multi-Armed Bandit se suelen considerar parte del RL, pero algunos de mis compañeros consideran Multi-Armed Bandit como un tipo distinto de problema.
Existen docenas de algoritmos para los escenarios Multi-Armed Bandit. Según mi experiencia, además de los algoritmos UCB1 y epsilon-greedy descritos en este artículo, el algoritmo más común utilizado en la práctica se denomina muestreo de Thompson. Puede obtener información sobre ese algoritmo en el número de febrero de 2018 de MSDN Magazine en msdn.com/magazine/mt829274.
El Dr. James McCaffrey trabaja para Microsoft Research en Redmond, Washington. Ha colaborado en varios productos clave de Microsoft, como Azure 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: Chris Lee, Ricky Loynd