Resumo Técnico: Aprendizado por Reforço Bilevel baseado em Hipergradiente com Complexidade de Amostragem Melhorada

Formulação do Problema

O artigo aborda o Aprendizado por Reforço (RL) Bilevel, um framework utilizado para formalizar problemas como meta-aprendizado, decomposição de tarefas hierárquicas e Aprendizado por Reforço a partir de Feedback Humano (RL-HF). Neste cenário, um objetivo de nível externo $\phi(x, \theta^*(x))$ é otimizado em relação a um parâmetro $x$ (ex: parâmetros da função de recompensa), enquanto o objetivo de nível interno $J(\theta, x)$ é otimizado em relação aos parâmetros da política $\theta$. O problema de nível interno é tipicamente não convexo, e o objetivo de nível externo depende da solução ótima $\theta^*(x)$ do problema interno.

Abordagens existentes enfrentam limitações significativas:

1. Métodos baseados em penalidade (ex: Gaur et al., 2025) frequentemente dependem de gradientes aproximados e exigem a condição Polyak-Łojasiewicz (PL) no objetivo de nível externo, resultando em uma complexidade de amostragem subótima de $\tilde{O}(\epsilon^{-3})$.
2. Métodos de hipergradiente baseados em Hessiana (ex: Chakraborty et al., 2024) evitam a suposição PL, mas sofrem com problemas de escalabilidade devido à necessidade de calcular e inverter a matriz Hessiana, o que é computacionalmente proibitivo para grandes espaços de parâmetros.
3. Métodos de espaço finito (ex: Yang et al., 2025) utilizam a otimalidade da política de Boltzmann para derivar gradientes livres de Hessiana, mas não se estendem diretamente a classes de políticas parametrizadas e não-realizáveis em espaços contínuos.

O desafio central é desenvolver um algoritmo de RL bilevel escalável e livre de Hessiana que alcance a complexidade de amostragem de estado da arte sem assumir a condição PL no objetivo de nível externo ou exigir uma classe de política realizável (onde a classe de política pode representar todas as políticas de Boltzmann).

Metodologia

Os autores propõem o algoritmo Approximate Hypergradient Optimization (AHO). A metodologia baseia-se em três componentes teóricos e algorítmicos fundamentais:

1. Exploração da Otimalidade da Política de Boltzmann

O objetivo de nível interno é definido como uma função de recompensa descontada com regularização de entropia. O artigo aproveita a conhecida otimalidade da política de Boltzmann ($\pi_B$) para este objetivo específico. Embora a classe de políticas $\Theta$ seja geralmente não-realizável (ou seja, não pode representar perfeitamente a política de Boltzmann ideal), os autores estabelecem condições sob as quais a otimalidade de $\pi_B$ ainda pode ser utilizada para derivar gradientes.

2. Funções de Valor Deslocadas pelo Gradiente

Para evitar o termo de Hessiana tipicamente encontrado em expressões de hipergradiente (derivadas via Teorema da Função Implícita), os autores introduzem funções de valor deslocadas pelo gradiente ($U^\pi$ e $W^\pi$).

• $U^\pi(s, \theta, x)$ e $W^\pi(s, a, \theta, x)$ são definidas como as somas descontadas de longo prazo do gradiente da recompensa $\nabla r(s, a, x)$ sob a política de Boltzmann.
• Essas funções atuam como substitutos para os gradientes da função de valor de Boltzmann ($\nabla V^{\pi,B}$) e da função Q ($\nabla Q^\pi$).
• Erro de Aproximação: Devido à não-realizabilidade da classe de políticas, existe um erro de aproximação entre essas funções substitutas e os gradientes reais. Este erro é limitado por termos $\epsilon_{kl}$ (relacionados à divergência KL) e $\epsilon_{fd}$ (relacionados a diferenças de gradiente), que desaparecem se a classe de políticas for realizável.

3. Teorema do Hipergradiente Aproximado

Os autores derivam um hipergradiente aproximado para o objetivo de nível externo. Ao substituir os gradientes reais pelas funções deslocadas pelo gradiente, eles obtêm uma expressão de forma fechada que elimina o termo de inversa da Hessiana. O hipergradiente resultante consiste em:

• O gradiente direto da perda de preferência em relação a $x$.
• Um termo envolvendo a diferença entre a função Q e as funções de valor deslocadas pelo gradiente, escalado pelo coeficiente de temperatura $\tau$.

4. Algoritmo (AHO)

O algoritmo AHO (Algoritmo 1) opera em um loop aninhado:

• Loop Interno: Atualiza os parâmetros da política $\theta$ usando um método padrão de gradiente de política com uma função Q estimada.
• Loop Externo: Atualiza o parâmetro de recompensa $x$ usando o hipergradiente aproximado. Isso envolve estimar as funções deslocadas pelo gradiente ($U^\pi_{off}$ e $W^\pi_{off}$) usando atualizações do tipo Q-learning off-policy (Algoritmos 3 e 4) baseadas em trajetórias coletadas.

Principais Contribuições

1. Otimalidade de Boltzmann com Classes Não-Realizáveis: O artigo fornece condições (Assunção 3.1) sob as quais a otimalidade da política de Boltzmann pode ser aplicada a classes de políticas parametrizadas e não-realizáveis, discutindo o impacto dos erros de aproximação resultantes na convergência.
2. Algoritmo Escalável Livre de Hessiana: O proposto algoritmo AHO é totalmente livre de Hessiana, tornando-o escalável para espaços de parâmetros de alta dimensão onde métodos baseados em Hessiana falham.
3. Complexidade de Amostragem Melhorada: O algoritmo alcança uma complexidade de iteração de $O(\epsilon^{-1})$ e uma complexidade de amostragem de $\tilde{O}(\epsilon^{-2})$. Isso melhora a complexidade de amostragem de estado da arte anterior de $\tilde{O}(\epsilon^{-3})$ encontrada em métodos baseados em penalidade (Gaur et al., 2025).
4. Suposições Relaxadas: Diferente do trabalho de estado da arte anterior (Gaur et al., 2025), o AHO remove a suposição da condição PL no objetivo de nível externo. Ele também relaxa o requisito de um minimizador único no problema de nível interno, exigindo apenas um minimizador localmente isolado e não degenerado.

Resultados e Análise

Garantias Teóricas

Sob condições de regularidade brandas (continuidade Lipschitz, recompensas/log-probabilidades limitadas e condição PL apenas no nível interno), os autores provam que a norma quadrada média do gradiente de nível externo converge para um limite dependente dos erros de aproximação e dos parâmetros de amostragem:
$$\frac{1}{T} \sum_{t=0}^{T-1} \|\nabla \Phi(x_t)\|^2 \leq O(\epsilon) + O(\epsilon_{approx}) + O(\epsilon_{fd}) + O(\epsilon_{kl})$$
Ao definir os parâmetros $T = \Theta(\epsilon^{-1})$, $B = \Theta(\epsilon^{-1})$, $K = \Theta(\log(\epsilon^{-1}))$ e $H = \Theta(\log(\epsilon^{-1}))$, a complexidade de amostragem é estabelecida como $\tilde{O}(\epsilon^{-2})$.

Avaliação Empírica

Os autores avaliam o AHO em tarefas de controle contínuo do conjunto de dados DM Control (walker-walk e cheetah-run) formuladas como problemas de RL bilevel baseados em preferência.

• Baseline: Eles comparam o AHO com o algoritmo de RL bilevel baseado em penalidade de Gaur et al. (2025).
• Restrição de Comparação: Eles explicitamente observam que não comparam com o PARL (Chakraborty et al., 2024) porque a abordagem baseada em Hessiana do PARL é computacionalmente inviável para os tamanhos de rede utilizados (exigindo a inversão de uma Hessiana com $\sim 10^{12}$ entradas).
• Resultado: O AHO alcança uma recompensa de avaliação total maior que o baseline de Gaur et al. (2025) em ambas as tarefas, apoiando empiricamente a melhoria teórica na complexidade de amostragem.

Significância

O artigo afirma que o AHO representa um passo significativo à frente no RL bilevel ao resolver o compromisso entre escalabilidade e eficiência de amostragem.

• Escalabilidade: Ao remover a Hessiana, o método torna-se aplicável às políticas de redes neurais modernas de larga escala usadas em RL baseado em preferência.
• Eficiência: Ao utilizar a estrutura do objetivo com regularização de entropia e a otimalidade de Boltzmann, o método evita o compromisso entre aproximação de gradiente vs. erro de amostragem inerente aos métodos de penalidade, levando a um limite de complexidade de amostragem melhor ($\tilde{O}(\epsilon^{-2})$ vs. $\tilde{O}(\epsilon^{-3})$).
• Robustez Teórica: A remoção da condição PL no nível externo amplia a aplicabilidade do algoritmo para uma gama mais ampla de objetivos não convexos comuns em RL-HF e meta-aprendizado.