Learning Kernel-Based MDPs from Episodic Preferential Feedback

Resumo Técnico: Aprendizado de MDPs Baseados em Kernel a partir de Feedback Preferencial Episódico

Formulação do Problema
Este trabalho aborda o problema de Aprendizado por Reforço a partir de Feedback Humano (RLHF) no contexto de Processos de Decisão de Markov (MDPs) episódicos. Diferentemente do RL padrão, onde os agentes recebem recompensas escalares, o aprendiz aqui recebe apenas feedback preferencial binário. Em cada episódio $k$, o aprendiz implanta duas políticas, $\pi$ e $\pi'$, a partir de um estado inicial comum para gerar duas trajetórias, $\tau_k$ e $\tau'_k$. O feedback consiste em um único rótulo binário $y_k \in \{0, 1\}$ indicando qual trajetória é preferida. Essa preferência é modelada por meio de uma função de ligação Bradley–Terry–Luce (BTL) aplicada à diferença de recompensas cumulativas (não observadas):
$$y_k \sim \text{Ber}\left(\sigma\left(\sum_{h=1}^H r_h(z^k_h) - \sum_{h=1}^H r_h(z'^k_h)\right)\right)$$
onde $\sigma$ é a função sigmoide. O objetivo é aprender uma política que maximize a função valor $V^\pi_1$ enquanto minimiza o arrependimento cumulativo, definido como a diferença entre o valor ótimo e o valor médio das políticas implantadas.

O cenário assume uma estrutura de MDP com Kernel, onde a função de recompensa $r_h$ e o operador de transição $P_h$ são elementos de um Espaço de Hilbert de Kernel Reprodutor (RKHS) $\mathcal{H}_k$ induzido por um kernel conhecido $k$. Especificamente, os autores focam na família de kernels Matérn, que captura estruturas não lineares e é equivalente em norma a espaços de Sobolev, oferecendo uma generalização além dos MDPs lineares.

Metodologia: Algoritmo PROSTO
Os autores propõem o PROSTO (Otimização Regularizada Baseada em Preferências via Otimismo Induzido por Trajetórias Amostradas). O algoritmo opera em episódios e utiliza uma abordagem de iteração de valor adaptada para feedback preferencial e aproximação de funções de kernel.

1. Estimação de Recompensa via Regressão Logística de Kernel Regularizada (KLRR):
   Como o feedback é em nível de trajetória e binário, o vetor de recompensa $\theta$ é estimado usando estimação de máxima verossimilhança com uma penalidade ponderada por norma. O estimador $\hat{\theta}_k$ minimiza o log-verossimilhança negativo das preferências observadas mais um termo de regularização $\tau \|\theta\|^2_{\mathcal{H}_k}$. As covariáveis para essa regressão são as características de diferença de trajetória $\phi_i = \sum_{h=1}^H \phi(z^i_h) - \phi(z'^i_h)$.

2. Exploração via Perturbação Aleatória de GP:
   Para garantir exploração suficiente em nível de trajetória sem conhecer a dinâmica de transição antecipadamente (o que impede bônus elípticos determinísticos), o PROSTO emprega exploração aleatória. Um vetor de ruído de exploração $\epsilon_k$ é amostrado de um Processo Gaussiano (GP) com uma estrutura de covariância dependente da covariância empírica das diferenças de trajetória. Esse ruído é adicionado à estimativa de recompensa para induzir otimismo.

3. Estimação da Função Valor via Regressão de Ridge de Kernel (KRR):
   A função valor é estimada recursivamente. O valor esperado do próximo estado é aproximado usando regressão de ridge de kernel padrão em amostras de transição. A estimativa final da função Q, $\hat{Q}^k_h$, combina a estimativa de recompensa (KLRR + ruído GP) e a estimativa de transição (KRR), sujeita a truncamento para garantir limitação.

4. Execução da Política:
   O aprendiz seleciona duas políticas, $\pi$ e $\pi'$, que são gananciosas em relação às suas respectivas estimativas otimistas da função Q. Essas políticas são executadas para gerar as trajetórias e o feedback preferencial do próximo episódio.

Principais Contribuições Técnicas e Desafios
O artigo identifica três desafios técnicos primários específicos à combinação de MDPs com kernel e feedback preferencial em nível de trajetória, fornecendo soluções inovadoras:

• Controle dos Números de Cobertura Logarítmica: Em MDPs com kernel, o número de cobertura logarítmica da classe de funções valor escala polinomialmente com o inverso da malha de cobertura $\epsilon$ e depende das normas RKHS dos estimadores. Diferentemente dos MDPs lineares, onde os números de cobertura são logarítmicos no número de episódios, configurações com kernel podem levar a limites de arrependimento que são vazios se as normas dos estimadores crescerem demais.

  • Solução: Os autores ajustam cuidadosamente o parâmetro de regularização $\tau$ na KLRR para controlar explicitamente a norma RKHS do estimador de recompensa. Isso mantém o número de cobertura da classe de funções induzida pequeno, permitindo limites de confiança significativos.

• Exploração em Nível de Trajetória com Ruído Não Suave: Bônus de exploração padrão (bônus elípticos) exigem conhecimento da trajetória completa, o que não está disponível no momento da decisão. A exploração aleatória via amostragem de GP é usada, mas caminhos de amostra de GP de um kernel Matérn geralmente não pertencem ao RKHS correspondente (são menos suaves). Isso torna os limites de cobertura padrão inaplicáveis.

  • Solução: Os autores derivam novos limites de cobertura Gaussianos de alta probabilidade para os caminhos de amostra do GP posterior. Eles aproveitam resultados de van der Vaart e van Zanten [2008] para mostrar que, embora os caminhos do GP estejam fora da bola do RKHS, eles estão dentro de uma vizinhança $\epsilon$ (na norma $\ell_\infty$) de uma bola do RKHS adequadamente ampliada com alta probabilidade. Isso permite a derivação de limites de cobertura necessários para a análise de arrependimento.

• Equilíbrio entre Parâmetros de Regularização e Cobertura: O ajuste dos parâmetros de regularização ($\tau$ para recompensa, $\lambda$ para transição) e da malha de cobertura $\epsilon$ é não trivial. Um $\epsilon$ pequeno reduz o erro de especificação, mas infla o número de cobertura; um $\epsilon$ grande faz o oposto.

  • Solução: Os autores otimizam conjuntamente $\tau$, $\lambda$ e $\epsilon$ como funções do número de episódios $K$ e do parâmetro de suavidade do kernel $\beta_p$. Esse ato de equilíbrio garante que as larguras de confiança permaneçam suficientemente apertadas para arrependimento sublinear, enquanto controlam a complexidade da classe de funções.

Resultados e Limites de Arrependimento
O artigo prova que o PROSTO alcança um limite de arrependimento cumulativo sublinear para todos os kernels na família Matérn. Especificamente, o arrependimento $R(K)$ escala como:
$$R(K) \leq \tilde{O}\left( \kappa_Z \max\left( H^{2.5} K^{1 - \frac{(\beta_p-1)^2}{2\beta_p(\beta_p+1)}}, H^3 K^{1 - \frac{\beta_p-1}{2(\beta_p+1)}} \right) \right)$$
onde $\beta_p > 1$ é o parâmetro de decaimento de autovalor do kernel, $H$ é o horizonte e $\kappa_Z$ é o gradiente máximo da função de ligação inversa. O expoente de $K$ é estritamente menor que 1, implicando convergência para a política ótima à medida que $K \to \infty$.

Além disso, o algoritmo é computacionalmente eficiente, com um tempo de execução polinomial no número de episódios $K$. Isso o distingue de trabalhos anteriores sobre MDPs com kernel e recompensas padrão (por exemplo, Maran et al. [2024b]), que, embora alcancem arrependimento sublinear, dependem de particionamento de domínio ou oráculos de otimização que não são conhecidos por serem tratáveis computacionalmente em tempo polinomial para configurações de kernel gerais.

Significância e Alegações
Os autores afirmam que este trabalho fornece o primeiro algoritmo para RL baseado em preferências em MDPs com kernel que alcança arrependimento sublinear provável para toda a família de kernels Matérn, sendo ao mesmo tempo computacionalmente eficiente.

• Novidade Teórica: O trabalho preenche a lacuna entre o RL baseado em preferências (que geralmente lida com configurações tabulares ou lineares) e a aproximação de funções baseada em kernel (que lida com configurações não lineares). Introduz novas técnicas para lidar com a falta de suavidade no ruído de exploração GP no contexto de iteração de valor.
• Eficiência Computacional: Diferentemente de algoritmos anteriores sem arrependimento para MDPs suaves que podem exigir otimização intratável, o PROSTO oferece uma implementação em tempo polinomial.
• Limitações: Os autores reconhecem que o limite de arrependimento pode não ser ótimo em ordem. Eles observam que abordagens de particionamento de domínio, que atualmente oferecem limites ótimos em ordem em algumas configurações de kernel, são incompatíveis com feedback em nível de trajetória devido à estocasticidade das transições, que impede a estimação localizada do operador de Bellman.

O artigo conclui que, embora o limite de arrependimento derivado seja sublinear, alcançar um limite ótimo em ordem permanece uma questão em aberto, provavelmente exigindo técnicas fundamentalmente diferentes além dos métodos atuais de particionamento de domínio ou cobertura uniforme.