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

Resumo Técnico: Aprendizado de Alvo Oculto Ótimo para Otimização de Inventário Online em Conjuntos Convexos Gerais

Formulação do Problema
O artigo aborda a Otimização de Inventário Online (OIO), um cenário onde um aprendiz seleciona vetores de pedido até $y_t$ de um conjunto de capacidade $Y \subseteq \mathbb{R}^n_+$ sujeito a restrições físicas de inventário. Diferente da Otimização Convexa Online (OCO) padrão, a OIO apresenta "memória física": o conjunto de ações viáveis no tempo $t$, denotado por $J_t = Y \cap \{y \mid y \succeq x_t\}$, depende do estado atual do inventário $x_t$. O inventário é transportado, o que significa que um aprendiz não pode simplesmente projetar um passo de gradiente sobre $Y$ se o vetor resultante estiver abaixo do nível de estoque atual. O ambiente escolhe a demanda adversária $d_t$ e as funções de perda $\ell_t$, e o aprendiz visa minimizar o regret dinâmico ou estático contra uma sequência de comparadores.

Trabalhos anteriores, como o MaxCOSD (Hihat et al., 2023), lidaram com conjuntos de capacidade convexos gerais usando ciclos adaptativos, alcançando um regret estático de $\tilde{O}(\sqrt{T/\mu})$ sob a condição de Demanda Uniformemente Provavelmente Positiva (UPPD). No entanto, essa dependência de $1/\mu$ (onde $\mu$ é a probabilidade de um choque de demanda comum) era subótima, e os métodos de alvo oculto existentes eram limitados a restrições de capacidade lineares devido à dependência de análises de "esgotamento de vendas" (sell-out) produto a produto.

Metodologia: Projeção de Alvo Oculto Alinhada à Norma
Os autores propõem que o princípio simples de manter um alvo oculto $z_t$ e projetá-lo no conjunto viável $J_t$ é suficiente para conjuntos convexos gerais, desde que a análise utilize um framework geométrico específico.

1. Algoritmo: O aprendiz mantém uma sequência de alvo oculto $z_t \in Y$ gerada por um algoritmo de aprendizado online base (ex: Gradiente Online Descendente). A ação implementada é $y_t = \text{Proj}_{J_t}^{\|\cdot\|}(z_t)$, a projeção de $z_t$ no conjunto viável $J_t$ medida em uma norma específica $\|\cdot\|$.
2. Princípio do Alinhamento de Norma: Uma contribuição metodológica crítica é a exigência de que a norma de projeção, a medição do estado da fila e a métrica de movimento do alvo utilizem a mesma norma admissível $\|\cdot\|$. Uma norma admissível domina a norma $\ell_\infty$ (ou seja, $\|x\|_\infty \le \|x\|$).
3. Redução Geométrica de Fila: O núcleo da análise define o "gap entre alvo e implementação" como $q_t = \|z_t - y_t\|$. Os autores provam uma recursão geométrica por trajetória (uma fila de Lindley):
   $$q_{t+1} \le [q_t + \|z_{t+1} - z_t\| - d^{\min}_t]_+$$
   onde $d^{\min}_t = \min_i d_{t,i}$ é a demanda comum.
   • Interpretação: O gap evolui como uma fila unidimensional. O movimento do alvo oculto ($z_{t+1} - z_t$) atua como "chegada", enquanto a demanda comum ($d^{\min}_t$) atua como "serviço".
   • Significância: Esta redução transforma o problema de viabilidade complexo e dependente de estado em um problema padrão de OCO com um custo de troca adicionado. Isso evita a necessidade de contabilidade produto a produto ou restrições lineares, o que anteriormente obstruía a generalização para conjuntos convexos curvos.

Principais Contribuições e Resultados

1. Regret Estático Ótimo para Perdas Convexas:
   Ao instanciar o aprendiz base com Gradiente Online Descendente (OGD), o artigo alcança um regret estático de $\tilde{O}(\sqrt{T/\mu})$. Isso melhora a melhor garantia conhecida para conjuntos convexos gerais de $O(1/\mu)$ para $O(1/\sqrt{\mu})$. Os autores provam um limite inferior correspondente de $\Omega(\sqrt{T/\mu})$, estabelecendo esta taxa como minimax ótima sob UPPD.

2. Regret Polilogarítmico para Perdas Fortemente Convexas:
   Para perdas $\alpha$-fortemente convexas, o mesmo framework produz um limite de regret de $\tilde{O}(\log(T/\mu))$. Isso resolve uma questão em aberto sobre se o regret polilogarítmico é alcançável em OIO adversarial com conjuntos de capacidade gerais.

3. Melhoria no Regret Dinâmico:
   O método fornece garantias de regret dinâmico que dependem da variação de caminho euclidiana $P_{T,2}$ do comparador, em vez da variação $\ell_1$ $P_{T,1}$ usada em análises anteriores de alvo oculto. Isso remove um fator explícito de $n^{1/4}$ e refina o limite para movimentos densos do comparador. Os autores utilizam tanto o OGD padrão (para variação conhecida) quanto o OGD Suavizado (SOGD) (para variação desconhecida) para alcançar esses resultados.

4. Refinamentos Sensíveis à Geometria via Descida de Espelho:
   O framework é estendido para a Descida de Espelho Online (OMD) com regularizadores fortemente convexos. Isso permite que os limites de regret se adaptem à geometria específica do conjunto de capacidade $Y$ e à norma dual dos gradientes. Por exemplo, o uso de regularização entrópica em restrições lineares melhora a dependência da dimensão $n$ em comparação com a projeção euclidiana quando os gradientes são densos em coordenadas.

5. Garantias Independentes da Dimensão:
   Os resultados são independentes da dimensão no sentido padrão de OCO; a dimensão $n$ entra apenas através dos parâmetros do problema (como o diâmetro de $Y$ ou limites de gradiente) em vez de como um fator multiplicativo explícito (ex: $n^{1/4}$).

Significância e Alegações
O artigo afirma que o princípio de "projeção de alvo oculto", frequentemente visto como uma heurística empírica ou limitado a restrições lineares, é teoricamente ótimo para o modelo completo de OIO convexo geral quando pareado com uma análise geométrica "alinhada à norma".

• Unificação Teórica: O trabalho unifica o controle de inventário com o OCO padrão ao mostrar que a restrição de viabilidade física pode ser desacoplada do algoritmo de aprendizado. A camada de inventário atua como um mecanismo de limpeza de fila que impõe um custo de troca no aprendiz base, sem exigir que o aprendiz base compreenda a dinâmica do inventário.
• Resolução de Obstruções: Demonstra que as obstruções que impediam a extensão das análises de fila para conjuntos convexos gerais (especificamente a falta de uma identidade de conservação para erros produto a produto) podem ser contornadas ao medir o estado como uma única distância geométrica em uma norma admissível.
• Validação Empírica: Experimentos com dados sintéticos e dados reais da competição de previsão M5 confirmam que o algoritmo HT-OGD proposto supera o MaxCOSD e o DDM (um método produto a produto) tanto em configurações de capacidade lineares quanto curvas, validando as melhorias teóricas nos limites de regret.

Os autores concluem que este template modular — separando o aprendizado de alvos ocultos da aplicação da viabilidade física via filas alinhadas à norma — oferece um framework robusto para futuros problemas online com restrições dependentes de estado.