Resumo Técnico: Aprendizado de Política Ótima sob Restrições de Orçamento e Cobertura

1. Formulação do Problema

O artigo aborda o problema de aprendizado de política ótima em cenários onde um tomador de decisão deve alocar um recurso limitado (tratamento) entre uma população de $N$ unidades para maximizar o bem-estar total (ganhos esperados). A alocação está sujeita a duas restrições simultâneas:

1. Restrição de Orçamento: O custo total do tratamento não pode exceder um orçamento fixo $B$ (ou orçamento per capita $C$).
2. Restrição Mínima de Cobertura: Uma fração mínima $\rho$ da população deve ser tratada.

Este problema surge em contextos como treinamento para emprego público, intervenções médicas ou benefícios sociais, onde a eficiência (maximização de ganhos) deve ser equilibrada com equidade ou requisitos políticos (garantia de ampla cobertura). O desafio central é que a solução ótima requer a seleção de um subconjunto de unidades de um conjunto exponencialmente grande de alternativas ($2^N$), formando um problema de otimização combinatória que é NP-difícil.

2. Metodologia e Marco Teórico

2.1 Caracterização Primal-Dual

O autor formula o problema dentro de uma estrutura de resultados potenciais. Seja $\tau(x)$ o efeito médio do tratamento condicional (CATE) e $c(x)$ o custo de tratar um indivíduo com covariáveis $x$. O objetivo é maximizar $E[\pi(X)\tau(X)]$ sujeito a $E[\pi(X)c(X)] \leq C$ e $E[\pi(X)] \geq \rho$.

Usando dualidade Lagrangiana, o artigo estabelece que a política ótima $\pi^*$ assume a forma de uma regra de limiar afim:
$$\pi^*(x) = \mathbb{1}\{ \tau(x) - \lambda^* c(x) + \nu^* \geq 0 \}$$
onde:

• $\lambda^*$ é o preço sombra da restrição orçamentária.
• $\nu^*$ é o preço sombra da restrição de cobertura.
• A regra trata um indivíduo se seu benefício, ajustado pelo preço sombra da cobertura, exceder o custo escalado pelo preço sombra do orçamento.

Esta estrutura difere de problemas padrão com restrição orçamentária (que geram uma regra de razão simples $\tau(x)/c(x) \geq \lambda^*$) porque a restrição de cobertura introduz um deslocamento aditivo ($\nu^*$), criando uma fronteira de decisão heterogênea.

2.2 Equivalência com Mochila e Relaxação de Programação Linear

A contraparte empírica do problema é mostrada como equivalente a um problema da mochila 0-1 com uma restrição adicional de cardinalidade.

• Forma Combinatória: Selecionar um vetor binário $d \in \{0,1\}^n$ para maximizar $\sum \hat{\tau}_i d_i$ sujeito a $\sum c_i d_i \leq nC$ e $\sum d_i \geq n\rho$.
• Relaxação de Programação Linear (LP): A restrição binária é relaxada para $z_i \in [0,1]$.

Um resultado teórico crítico é a análise da lacuna de integralidade (a diferença entre o valor ótimo da LP e o valor ótimo 0-1). O artigo prova que:

1. Qualquer solução de ponto extremo da relaxação LP possui no máximo duas componentes fracionárias.
2. Consequentemente, a lacuna de integralidade absoluta é limitada por uma constante $O(1)$ (especificamente $2V_{max}$).
3. Em termos per capita, a lacuna desaparece assintoticamente como $O(1/n)$. Isso implica que a relaxação LP é assintoticamente equivalente à solução ótima discreta.

2.3 Algoritmos Implementáveis

Com base na relaxação LP e na estrutura de limiar afim, dois algoritmos são propostos:

1. Ganancioso-Lagrangiano com Cobertura (GLC):

   • Mecanismo: Uma busca primal-dual sobre o preço sombra do orçamento $\lambda$. Para um $\lambda$ fixo, as unidades são pontuadas por $a_i(\lambda) = \hat{\tau}_i - \lambda c_i$.
   • Procedimento: O algoritmo impõe a restrição de cobertura forçando as $K_n$ unidades superiores (mínimo necessário) por pontuação no conjunto de tratamento, e depois adiciona greedymente as unidades restantes com pontuações positivas até que o orçamento se esgote. O multiplicador $\lambda$ é ajustado via bissecção para satisfazer a restrição orçamentária.
   • Complexidade: $O(n \log n \cdot \log(1/\varepsilon))$.

2. Classificação e Corte (RC):

   • Mecanismo: Uma regra heurística não iterativa que classifica as unidades exclusivamente pela razão de custo-efetividade $s_i = \hat{\tau}_i / c_i$.
   • Procedimento: As unidades são ordenadas por $s_i$ em ordem decrescente. O algoritmo seleciona o maior prefixo viável que satisfaz tanto a restrição orçamentária quanto a de cobertura.
   • Complexidade: $O(n \log n)$.

3. Resultados Principais

3.1 Otimalidade Assintótica

O artigo estabelece que o algoritmo GLC é assintoticamente ótimo. Como a relaxação LP possui uma lacuna de integralidade per capita que desaparece, qualquer regra gananciosa viável que aproxime o ótimo da LP (o que o GLC faz) também é assintoticamente ótima para o problema combinatório original.

3.2 Desempenho da Classificação e Corte (RC)

O artigo fornece uma caracterização precisa de quando a regra RC mais simples é aproximadamente ótima. A perda de bem-estar do RC em relação à política ótima é impulsionada pela discrepância entre o limiar constante usado pelo RC e o limiar afim heterogêneo da política ótima.

• Condição para Equivalência: O RC é aproximadamente ótimo se:
  1. Os custos são homogêneos ($c(x) \approx c_0$), OU
  2. A restrição de cobertura é frouxa ($\nu^* \approx 0$).
• Condição para Má Alocação: Má alocação significativa ocorre apenas quando a heterogeneidade de custos é substancial E a restrição de cobertura é vinculativa ($\nu^* > 0$). Neste regime específico, a fronteira afim da política ótima não pode ser replicada por uma classificação simples baseada em razão, levando ao tratamento de unidades de baixa razão (para atender à cobertura) e à exclusão de unidades de alta razão (devido ao orçamento).

3.3 Evidência de Monte Carlo

Dois estudos de simulação apoiam as descobertas teóricas:

1. GLC vs. LP: À medida que o tamanho da amostra $n$ aumenta, o arrependimento per capita do GLC em relação à solução ótima exata (MILP) diminui rapidamente, estabilizando-se em níveis baixos. A lacuna de integralidade da LP também desaparece rapidamente, confirmando a convergência $O(1/n)$.
2. RC vs. LP: Simulações em quatro regimes (variando heterogeneidade de custos e rigor de cobertura) confirmam que a má alocação entre RC e a política ótima é negligenciável em todos os casos, exceto quando os custos são heterogêneos e a cobertura é vinculativa. Nesse cenário específico de "pior caso", a área de má alocação é significativa (~15%), validando o efeito de interação teórico.

4. Contribuições e Significado

O artigo faz três contribuições primárias:

1. Representação Estrutural: Fornece uma caracterização estrutural do aprendizado de política com restrições como um problema do tipo mochila com uma regra de limiar afim envolvendo dois preços sombra, modelando explicitamente a interação entre restrições orçamentárias e de cobertura.
2. Ajuste Assintótico: Estabelece que a relaxação LP deste problema combinatório possui uma lacuna de integralidade $O(1)$, provando a equivalência assintótica entre as soluções relaxada e discreta em termos per capita. Isso justifica o uso de regras mais simples e escaláveis em aplicações de grande escala.
3. Implementação e Limites: Propõe e analisa dois algoritmos escaláveis (GLC e RC). Crucialmente, identifica as condições estruturais precisas sob as quais a regra RC simples e não iterativa falha. O artigo preenche a lacuna entre o aprendizado de políticas estatístico e a otimização combinatória, oferecendo um framework que é tanto teoricamente fundamentado quanto computacionalmente escalável.

O significado do trabalho reside em sua capacidade de ir além da caracterização teórica de políticas ótimas para fornecer soluções implementáveis e escaláveis com garantias de desempenho. Ele esclarece que, embora a classificação simples por custo-efetividade seja frequentemente suficiente, os formuladores de políticas devem estar cientes das condições estruturais específicas (custos heterogêneos + cobertura vinculativa) onde tais heurísticas podem levar a perdas significativas de bem-estar.