Multiscale Reward Hedging from Correct Demonstrations

Resumo Técnico: Multiscale Reward Hedging from Correct Demonstrations

Formulação do Problema
O artigo aborda o problema de aprender a partir de demonstrações corretas em cenários onde múltiplas ações podem ser ótimas. Diferente do aprendizado supervisionado padrão, o aprendiz observa uma única demonstração válida $a^*_t$ para um contexto $x_t$, mas não recebe feedback sobre se sua própria predição $\hat{a}_t$ estava correta, nem observa a função de recompensa subjacente ou a magnitude de sua perda. O objetivo é minimizar o "gap oculto" cumulativo (a diferença entre a recompensa da ação ótima e a ação do aprendiz) contra uma função de recompensa desconhecida $r^*$.

Este cenário generaliza o trabalho anterior sobre classes de recompensas finitas (Joshi et al., 2026) para classes de recompensas contínuas, uma lacuna anteriormente não abordada para classes contínuas gerais. O modelo de feedback é distinto da otimização inversa online ou do bandit contextual padrão, pois o aprendiz nunca observa um valor de recompensa ou um bit de correção; ele apenas observa uma ação válida de um conjunto desconhecido de ações ótimas.

Metodologia: Multiscale Reward Hedging
A principal contribuição é um algoritmo de reward-hedging determinístico e multiescala que opera sem um horizonte de tempo conhecido. A metodologia baseia-se nos seguintes componentes:

1. Métrica de Gap e Proxies: O algoritmo foca na função de gap de otimalidade $g_r(x, a) = \sup_{b \in A(x)} r(x, b) - r(x, a)$. Em vez de estimar a função de recompensa diretamente, o aprendiz mantém um voto ponderado sobre um conjunto de "proxies binários tolerantes".
2. Cobertura Multiescala (Multiscale Covering): Para uma sequência de escalas de precisão $\epsilon_j = 2^{-j-1}$, o algoritmo constrói coberturas apropriadas $\epsilon_j$ ($C_j$) da classe de funções de gap $G$. Cada elemento $h \in C_j$ define uma proxy $q_{j,h}$ que rotula uma ação como "boa" se $h(x, a) \le \epsilon_j$.
3. Voto Compartilhado: Em vez de executar aprendizes separados para cada escala (o que geraria ações incompatíveis), o algoritmo agrega todas as proxies de todas as escalas em um único voto ponderado. O peso inicial de uma proxy na escala $j$ é proporcional a $2^{-j}$.
4. Regra de Atualização: A atualização é "isenta de erros" (mistake unaware). Ao observar uma demonstração $a^*_t$, o algoritmo atualiza os pesos baseando-se apenas na comparação entre o julgamento da proxy e a predição do aprendiz:
   • Se a proxy considera a demonstração boa, mas a ação do aprendiz ruim, o peso da proxy dobra.
   • Se a proxy considera a demonstração ruim, o peso é zerado.
   • Caso contrário, o peso permanece inalterado.
     Esta regra garante que, se a ação do aprendiz tiver um gap grande em relação a uma escala específica, o peso da proxy que representa essa escala aumentará, efetivamente fazendo o "hedging" contra essa escala de erro.

Principais Resultados Teóricos

• Limites de Cauda Livres de Horizonte (Horizon-Free Tail Bounds): O algoritmo fornece um limite de cauda simultâneo para o número de rodadas onde a perda excede um limiar $2^{-j}$:
  $$|\{t : \ell_t > 2^{-j}\}| \le \log_2 N(G, 2^{-j-1}) + j$$
  onde $N(G, \epsilon)$ é o número de cobertura da classe de gap. A integração dessas caudas resulta em um limite de gap oculto cumulativo independente do horizonte de tempo $T$:
  $$\sum_{t=1}^T \ell_t \le \sum_{j \ge 1} 2^{-j} \log_2 N(G, 2^{-j-1}) + 2$$
  Esta soma é limitada por uma integral de entropia métrica, $H_{dyad}(G)$.

• Entropia Polinomial e Taxas de Regret:

  • Para classes com números de cobertura polinomiais $N(G, \epsilon) \le (A/\epsilon)^d$, o gap total é limitado por $O(d \log A)$.
  • Isso se traduz em uma taxa estatística de $O(d/m)$ no cenário online-to-batch.
  • Recomendação Contextual Linear: Para recompensas lineares limitadas com raio de parâmetro $B$ e diâmetro de menu $K$, o regret é $O(d)$ para menus compactos arbitrários. Este é o primeiro limite finito polinomial para menus arbitrários sem restrições estruturais (ex: M-convexidade), alcançado via um preditor impróprio.
  • Recompensas de Baixo Rank e Neurais: O framework se estende a recompensas bilineares de baixo rank ($O(BKr(m+n))$) e redes ReLU limitadas com limites explícitos dependentes da profundidade e parâmetros da rede.

• Complexidade Computacional:

  • O algoritmo geral é de natureza informacional e pode ser computacionalmente caro devido à enumeração de coberturas.
  • No entanto, para curvas de parâmetros Lipschitz unidimensionais (ex: recomendação de raio fixo de rank dois), o algoritmo é exato e roda em tempo polinomial. Especificamente, para recomendação de raio fixo de rank dois com tamanho de menu $k$ e custo de avaliação de recompensa $C$, a complexidade de tempo é $O(kCT^2)$.

• Limites Inferiores e Robustez:

  • O artigo prova um limite inferior correspondente de $\Omega(d)$ para classes contínuas com expoente de entropia $d$, confirmando a precisão da dependência $O(d)$.
  • Uma variante robusta lida com demonstrações subótimas, adicionando apenas a subotimalidade cumulativa do demonstrador $\Delta_T$ ao limite de regret.

Significância e Alegações
O artigo afirma resolver a questão aberta de aprender a partir de demonstrações corretas para classes de recompensas contínuas. Sua principal significância reside em:

1. Primeira Garantia Livre de Horizonte para Classes Contínuas: Fornece os primeiros limites de regret para classes contínuas que não dependem do horizonte de tempo $T$, baseando-se na entropia métrica.
2. Predição Imprópria para Menus Arbitrários: Alcança $O(d)$ de regret para recomendação contextual linear com menus compactos arbitrários, um cenário onde algoritmos próprios anteriores exigiam restrições estruturais (como M-convexidade) ou sofriam com dependências de dimensão mais altas.
3. Eficiência em Geometrias Específicas: Embora o voto geral seja custoso, o artigo isola um caso não trivial (curvas Lipschitz 1D) onde o algoritmo exato é de tempo polinomial, unindo o limite informacional à viabilidade computacional.
4. Validação Empírica: Um teste de estresse reproduzível usando dados do MovieLens demonstra que o algoritmo se adapta às escalas e melhora o gap médio latente em comparação tanto com políticas de classificação demonstrada quanto com baselines online próprios, usando apenas demonstrações de ações sem observar recompensas.

O autor enfatiza que, embora a solução geral seja imprópria (o voto pode não corresponder a um único parâmetro de recompensa válido), ela consegue minimizar o gap de recompensa alvo, distinguindo-se dos métodos de otimização inversa online próprios que visam estimar o próprio parâmetro de recompensa.