4 · Bandidos multi-brazo
Reduce el RL a su forma más simple: un estado, k acciones, cada una una máquina tragamonedas con pago desconocido. Estima el valor de cada brazo promediando — y observa a un agente codicioso tropezar.
Un bandido de k brazos es un MDP con un solo estado y k acciones, donde cada brazo paga de una distribución de recompensa fija y desconocida. Aprendemos el valor de acción Q(a) — la recompensa media del brazo a — promediando las recompensas que realmente vemos, y luego actuamos de forma codiciosa eligiendo el brazo con la estimación más alta.
Sin esto:
Sin el bandido te saltas el lugar más limpio para conocer la estimación del valor de acción y el problema de explorar/explotar — las dos ideas en el corazón de todo método de RL basado en valores.
El bandido multi-brazo es el RL despojado de todo excepto el desafío central. Imagina una fila de k máquinas tragamonedas ("bandidos de un brazo"). Cada tirón del brazo a paga una recompensa aleatoria sacada de la propia distribución fija de ese brazo, con una media real q*(a) que no conoces. En cada paso eliges un brazo y observas una recompensa. Tu meta: maximizar la recompensa total a lo largo de muchos tirones.
Esto es un MDP con un solo estado — no hay "siguiente estado" de qué preocuparse, cada tirón enfrenta la misma fila de máquinas — así que aísla lo único que el RL debe hacer: averiguar qué acciones son buenas solo a partir de experiencia ruidosa.
La cantidad clave es el valor de acción Q(a): nuestra estimación de la recompensa media del brazo a. La estimación más natural es el promedio muestral — el promedio de todas las recompensas que realmente hemos recibido de ese brazo:
Q(a) = (suma de recompensas vistas de a) / (número de veces que se tiró a)
Por la ley de los grandes números, mientras más tiramos de un brazo, más se acerca su promedio muestral al verdadero q*(a). Un agente que actúa de forma codiciosa simplemente tira del brazo con la mayor estimación Q(a) actual. Pero hay una trampa que expondremos abajo: un agente codicioso solo confía en lo que ya muestreó — y un brazo tirado una vez con mala suerte puede ser descartado por error para siempre.
Python (in browser)
Un bandido de 10 brazos desde cero: Q(a) aprendido por promedio muestral incremental. El codicioso puro se fija en un favorito temprano; el aleatorio puro estima bien pero nunca explota.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
En un bandido de k brazos, ¿qué es el valor de acción Q(a) y cómo se estima por promedio muestral?
- Un bandido de k brazos es un MDP con un estado y k acciones; cada brazo paga de una distribución fija desconocida con media real q*(a).
- El valor de acción Q(a) se estima promediando las recompensas observadas: Q(a) <- Q(a) + (1/n)(r - Q(a)), la media progresiva.
- Un agente puramente codicioso se fija en estimaciones tempranas; uno puramente aleatorio estima bien pero nunca explota — ninguno basta.
Los bandidos ejecutan pruebas A/B, selección online de anuncios y contenido, asignación en ensayos clínicos y búsqueda de hiperparámetros — donde sea que elijas entre opciones bajo incertidumbre.
Si lo quitas: Sin la estimación del valor de acción no tienes forma de convertir muestras ruidosas de recompensa en un juicio sobre cuál acción es la mejor.