Optimal Hidden-Target Learning for Online Inventory Optimization on General Convex Sets

Resumen Técnico: Aprendizaje de Objetivo Oculto Óptimo para la Optimización de Inventario en Línea sobre Conjuntos Convexos Generales

Formulación del Problema
El artículo aborda la Optimización de Inventario en Línea (OIO, por sus siglas en inglés), un escenario donde un aprendiz selecciona vectores de pedido hasta $y_t$ de un conjunto de capacidad $Y \subseteq \mathbb{R}^n_+$ sujeto a restricciones físicas de inventario. A diferencia de la Optimización Convexa en Línea (OCO) estándar, la OIO presenta "memoria física": el conjunto de acciones factibles en el tiempo $t$, denotado como $J_t = Y \cap \{y \mid y \succeq x_t\}$, depende del estado actual del inventario $x_t$. El inventario se transfiere, lo que significa que un aprendiz no puede simplemente proyectar un paso de gradiente sobre $Y$ si el vector resultante es inferior al nivel de stock actual. El entorno elige una demanda adversaria $d_t$ y funciones de pérdida $\ell_t$, y el aprendiz busca minimizar el arrepentimiento (regret) dinámico o estático frente a una secuencia de comparadores.

Trabajos previos, como MaxCOSD (Hihat et al., 2023), manejaron conjuntos de capacidad convexos generales utilizando ciclos adaptativos, logrando un arrepentimiento estático de $\tilde{O}(\sqrt{T/\mu})$ bajo la condición de Demanda Uniformemente Probablemente Positiva (UPPD). Sin embargo, esta dependencia de $1/\mu$ (donde $\mu$ es la probabilidad de un choque de demanda común) era subóptima, y los métodos de objetivo oculto existentes se limitaban a restricciones de capacidad lineales debido a la dependencia de análisis de "agotamiento de ventas" (sell-out) producto por producto.

Metodología: Proyección de Objetivo Oculto Alineada con la Norma
Los autores proponen que el principio simple de mantener un objetivo oculto $z_t$ y proyectarlo sobre el conjunto factible es suficiente para conjuntos convexos generales, siempre que el análisis utilice un marco geométrico específico.

1. Algoritmo: El aprendiz mantiene una secuencia de objetivos ocultos $z_t \in Y$ generada por un algoritmo de aprendizaje en línea base (por ejemplo, Descenso de Gradiente en Línea). La acción implementada es $y_t = \text{Proj}_{J_t}^{\|\cdot\|}(z_t)$, la proyección de $z_t$ sobre el conjunto factible $J_t$ medida en una norma específica $\|\cdot\|$.
2. Principio de Alineación de la Norma: Una contribución metodológica crítica es el requisito de que la norma de proyección, la medición del estado de la cola y la métrica de movimiento del objetivo utilicen la misma norma admisible $\|\cdot\|$. Una norma admisible domina la norma $\ell_\infty$ (es decir, $\|x\|_\infty \le \|x\|$).
3. Reducción Geométrica de la Cola: El núcleo del análisis define la "brecha entre objetivo e implementación" como $q_t = \|z_t - y_t\|$. Los autores demuestran una recursión geométrica de trayectoria (una cola de Lindley):
   $$q_{t+1} \le [q_t + \|z_{t+1} - z_t\| - d^{\min}_t]_+$$
   donde $d^{\min}_t = \min_i d_{t,i}$ es la demanda común.
   • Interpretación: La brecha evoluciona como una cola unidimensional. El movimiento del objetivo oculto ($z_{t+1} - z_t$) actúa como "llegada", mientras que la demanda común ($d^{\min}_t$) actúa como "servicio".
   • Significado: Esta reducción transforma el complejo problema de factibilidad dependiente del estado en un problema estándar de OCO con un costo de cambio añadido. Evita la necesidad de contabilidad producto por producto o restricciones lineales, lo que anteriormente obstruía la generalización a conjuntos convexos curvos.

Contribuciones Clave y Resultados

1. Arrepentimiento Estático Óptimo para Pérdidas Convexas:
   Al instanciar el aprendiz base con Descenso de Gradiente en Línea (OGD), el artículo logra un arrepentimiento estático de $\tilde{O}(\sqrt{T/\mu})$. Esto mejora la mejor garantía conocida para conjuntos convexos generales de $O(1/\mu)$ a $O(1/\sqrt{\mu})$. Los autores demuestran un límite inferior coincidente de $\Omega(\sqrt{T/\mu})$, estableciendo esta tasa como minimax óptima bajo UPPD.

2. Arrepentimiento Polilogarítmico para Pérdidas Fuertemente Convexas:
   Para pérdidas $\alpha$-fuertemente convexas, el mismo marco produce un límite de arrepentimiento de $\tilde{O}(\log(T/\mu))$. Esto resuelve una pregunta abierta sobre si es posible lograr un arrepentimiento polilogarítmico en OIO adversaria con conjuntos de capacidad convexos generales.

3. Arrepentimiento Dinámico Mejorado:
   El método proporciona garantías de arrepentimiento dinámico que dependen de la variación de trayectoria euclidiana $P_{T,2}$ del comparador, en lugar de la variación $\ell_1$ $P_{T,1}$ utilizada en análisis previos de objetivo oculto. Esto elimina un factor explícito de $n^{1/4}$ y agudiza el límite para movimientos densos del comparador. Los autores utilizan tanto OGD estándar (para variación conocida) como SOGD (Descenso de Gradiente Suavizado, para variación desconocida) para lograr estos resultados.

4. Refinamientos Sensibles a la Geometría mediante Descenso de Espejo:
   El marco se extiende al Descenso de Espejo en Línea (OMD) con regularizadores fuertemente convexos. Esto permite que los límites de arrepentimiento se adapten a la geometría específica del conjunto de capacidad $Y$ y a la norma dual de los gradientes. Por ejemplo, el uso de regularización entrópica en restricciones lineales mejora la dependencia de la dimensión $n$ en comparación con la proyección euclidiana cuando los gradientes son densos en coordenadas.

5. Garantías Independientes de la Dimensión:
   Los resultados son independientes de la dimensión en el sentido estándar de OCO; la dimensión $n$ entra solo a través de los parámetros del problema (como el diámetro de $Y$ o los límites de los gradientes) en lugar de como un factor multiplicativo explícito (por ejemplo, $n^{1/4}$).

Significado y Reivindicaciones
El artículo sostiene que el principio de "proyección de objetivo oculto", a menudo visto como una heurística empírica o limitado a restricciones lineales, es teóricamente óptimo para el modelo completo de OIO de conjuntos convexos generales cuando se combina con un análisis de cola alineado con la norma.

• Unificación Teórica: El trabajo unifica el control de inventarios con el OCO estándar al mostrar que la restricción de factibilidad física puede desacoplarse del algoritmo de aprendizaje. La capa de inventario actúa como un mecanismo de limpieza de colas que impone un costo de cambio al aprendiz base, sin requerir que el aprendiz base comprenda la dinámica del inventario.
• Resolución de Obstrucciones: Demuestra que las obstrucciones que impedían la extensión de los análisis de colas a conjuntos convexos generales (específicamente la falta de una identidad de conservación para los errores producto por producto) pueden sortearse midiendo el estado como una única distancia geométrica en una norma admisible.
• Validación Empírica: Experimentos con datos sintéticos y datos reales de la competencia de pronóstico M5 confirman que el algoritmo HT-OGD propuesto supera a MaxCOSD y DDM (un método de producto por producto) tanto en configuraciones de capacidad lineales como curvas, validando las mejoras teóricas en los límites de arrepentimiento.

Los autores concluyen que esta plantilla modular —que separa el aprendizaje de los objetivos ocultos de la imposición de la factibilidad física mediante colas alineadas con la norma— ofrece un marco robusto para futuros problemas en línea con restricciones dependientes del estado.