El Fin Del Conocimiento - Bóveda 6/88 - CVPR - 2023 - Adaptándose a árboles de juegos en juegos de información imperfecta de suma cero

graph LR classDef game fill:#f9d4d4, font-weight:bold, font-size:14px classDef strategies fill:#d4f9d4, font-weight:bold, font-size:14px classDef exploration fill:#d4d4f9, font-weight:bold, font-size:14px classDef learning fill:#f9f9d4, font-weight:bold, font-size:14px A["Adaptándose a árboles de
juegos en juegos de
información imperfecta de suma cero"] --> B["Información del
Juego"] A --> C[Estrategias] A --> D[Exploración] A --> E["Aprendizaje
y
Complejidad"] B --> B1["Juegos de información
parcial. 1"] B --> B2["Los jugadores recuerdan
movimientos previos. 2"] B --> B3["Estados de juego
indistinguibles. 5"] B --> B4["Probabilidad de pares
de acciones. 6"] B --> B5["Entropías: Tsallis,
Shannon, Dilatada. 11, 12, 13"] B --> B6["Exploración equilibrada.
14"] C --> C1["Estrategias casi-óptimas. 3"] C --> C2["Minimizar
arrepentimiento. 4"] C --> C3["Arrepentimiento en conjuntos
de información. 7"] C --> C4["Muestreo de acciones
proporcional. 9"] C --> C5["FTRL: Minimizar
arrepentimiento. 10"] C --> C6["Regularizador en
FTRL. 11"] D --> D1["Reducir la varianza de
estimación de pérdida. 8"] D --> D2["Tasas de aprendizaje
adaptativas. 15"] D --> D3["Límites con alta
probabilidad. 16"] D --> D4["Límites teóricos de
arrepentimiento. 17"] D --> D5["Realizaciones para
estrategia ε-óptima. 18"] D --> D6["Aprender de las
trayectorias del juego. 19"] E --> E1["Tasas óptimas
con estructura conocida. 20"] E --> E2["Casi-óptimo con
estructura desconocida. 21"] E --> E3["Componentes de sesgo
de estimación. 22"] E --> E4["Componente de
regularización. 23"] E --> E5["Componente de varianza
de estimación. 24"] E --> E6["Costo computacional del
algoritmo. 27"] class A,B,B1,B2,B3,B4,B5,B6 game class C,C1,C2,C3,C4,C5,C6 strategies class D,D1,D2,D3,D4,D5,D6 exploration class E,E1,E2,E3,E4,E5,E6 learning

Resumen:

1.- Juegos de información imperfecta: Juegos donde los jugadores tienen información parcial sobre el estado actual del juego.

2.- Recuerdo perfecto: Los jugadores recuerdan sus movimientos previos y los conjuntos de información forman una estructura de árbol.

3.- Estrategias ε-óptimas: Estrategias que están dentro de ε de la estrategia óptima en términos de valor esperado.

4.- Minimización del arrepentimiento: Minimizar la diferencia entre la ganancia acumulada y la ganancia de la mejor estrategia fija.

5.- Conjuntos de información: Conjuntos de estados de juego indistinguibles para un jugador.

6.- Plan de realización: Probabilidad de alcanzar un par conjunto de información-acción dado.

7.- Arrepentimiento contrafactual: Arrepentimiento definido en conjuntos de información en lugar de estados de juego completos.

8.- Exploración implícita (IX): Técnica para reducir la varianza en las estimaciones de pérdida.

9.- Política equilibrada: Muestreo de acciones proporcional al tamaño de los sub-árboles asociados.

10.- Seguir al Líder Regularizado (FTRL): Algoritmo que minimiza el arrepentimiento siguiendo la mejor estrategia regularizada.

11.- Entropía de Tsallis: Regularizador usado en algoritmos FTRL.

12.- Entropía de Shannon: Regularizador alternativo usado en algoritmos FTRL.

13.- Entropía dilatada: Regularizador de entropía aplicado a través del árbol del juego.

14.- Transiciones equilibradas: Núcleo de transición definido para equilibrar la exploración a través del árbol del juego.

15.- Tasas de aprendizaje adaptativas: Tasas de aprendizaje que se adaptan según la estructura del juego observada.

16.- Límites de alta probabilidad: Límites que se mantienen con alta probabilidad en lugar de solo en expectativa.

17.- Límites inferiores: Límites teóricos inferiores sobre el arrepentimiento o la complejidad de la muestra.

18.- Complejidad de la muestra: Número de realizaciones del juego necesarias para aprender una estrategia ε-óptima.

19.- Retroalimentación de trayectoria: Aprender de las trayectorias del juego observadas en lugar de la información completa del juego.

20.- FTRL equilibrado: Algoritmo que usa transiciones equilibradas para lograr tasas óptimas con estructura conocida.

21.- FTRL adaptativo: Algoritmo que se adapta a la estructura desconocida mientras mantiene tasas casi-óptimas.

22.- Términos de BIAS: Componentes del arrepentimiento relacionados con el sesgo de estimación.

23.- Término REG: Componente del arrepentimiento relacionado con la regularización.

24.- Término VAR: Componente del arrepentimiento relacionado con la varianza de las estimaciones.

25.- Desigualdad de Azuma-Hoeffding: Desigualdad de concentración para secuencias de diferencia de martingala acotadas.

26.- Desigualdad de Freedman: Desigualdad de concentración para martingalas con varianza condicional acotada.

27.- Complejidad temporal: Costo computacional de las actualizaciones del algoritmo.

28.- Póker de Kuhn: Juego de póker simple usado como referencia.

29.- Póker de Leduc: Variante de póker más compleja usada como referencia.

30.- Dados de mentiroso: Juego de dados usado como referencia para algoritmos de información imperfecta.

Bóveda del Conocimiento construida por David Vivancos 2024