Asymptotic Optimality of Thompson Sampling for Risk-Averse Bandits with Sub-Gaussian Rewards

Resumo Técnico: Otimalidade Assintótica de Thompson Sampling para Bandidos Avessos ao Risco com Recompensas Sub-Gaussianas

Enunciado do Problema
O artigo aborda o problema de Multi-Armed Bandit (MAB) sob objetivos de aversão ao risco. Diferente dos cenários padrão de MAB que maximizam a recompensa esperada, os cenários de aversão ao risco visam otimizar funcionais de risco gerais $\rho$ (por exemplo, Valor em Risco Condicional (CVaR), média-variância, razão de Sharpe ou medidas de risco de distorção). O desafio específico tratado é a análise teórica do $\rho$-NPTS (um algoritmo de Thompson Sampling não paramétrico proposto por Chang e Tan [2022]). Embora Chang e Tan tenham provado a otimalidade de instância para um companheiro paramétrico ($\rho$-MTS), eles deixaram a otimalidade do $\rho$-NPTS não paramétrico como um problema em aberto.

O obstáculo fundamental é que o $\rho$-NPTS constrói um posterior de Dirichlet onde o tamanho efetivo do alfabeto cresce com o número de observações ($N_k$). A aplicação direta de resultados de limites de cauda existentes resulta em um prefactor super-exponencial de $(N_k)^{N_k/2}$, o que impede a prova de limites de regret logarítmicos. Além disso, resultados anteriores frequentemente exigiam condições fortes, como a condição de "dominância" (para métodos paramétricos) ou continuidade de Lipschitz para funcionais do tipo UCB, excluindo funcionais não-Lipschitz importantes como a razão de Sharpe.

Metodologia
Os autores introduzem o $\rho$-NPTSSG, uma variante sem âncora do algoritmo de Thompson Sampling não paramétrico projetada para distribuições com densidade limitada e caudas sub-gaussianas ($P(B, \sigma)$). A inovação técnica central é um lema de discretização (e seu análogo truncado para caudas sub-gaussianas) que projeta o posterior de Dirichlet de alfabeto crescente sobre uma grade fixa.

1. Discretização e Agregação:
   O artigo define uma grade fixa $G_M$ de tamanho $M$. Para qualquer sequência de recompensas observada, a medida empírica é projetada sobre esta grade através da agregação de pesos de Dirichlet correspondentes a observações que caem dentro da mesma célula da grade.

   • Insight Chave: Pela propriedade de agregação da distribuição de Dirichlet, os pesos projetados nas células ocupadas seguem uma distribuição de Dirichlet com uma dimensão fixa ($M^+ \le M$), independentemente do tamanho da amostra $N_k$.
   • Consequência: Esta projeção limita o prefactor polinomial nos limites de cauda ao grau $(M-1)/2$, que é independente de $N_k$. Isso quebra a barreira super-exponencial que bloqueava provas anteriores.

2. Variantes do Algoritmo:

   • $\rho$-NPTS (Suporte Limitado): Opera em distribuições com suporte em $[0, 1]$ e densidade limitada. Utiliza uma âncora fixa (o limite direito) e uma grade uniforme.
   • $\rho$-NPTSSG (Sub-Gaussiana): Opera em distribuições em $\mathbb{R}$ com densidade limitada e caudas sub-gaussianas. Remove a âncora fixa (usando inicialização round-robin em vez disso) e emprega um lema de discretização truncada. Este lema utiliza uma grade centrada na média empírica com uma largura que encolhe conforme o tamanho da amostra cresce, enquanto trunca as caudas para controlar a probabilidade de transbordamento (overflow).

3. Análise de Regret:
   A prova segue uma decomposição padrão de regret em termos onde o algoritmo extrai um braço subótimo com um score de Thompson "alto" versus um score "baixo".

   • Limite Superior (Upper Bound): Utiliza o lema de discretização para aplicar os limites de cauda de Chang e Tan [2022] à projeção de grade fixa. A continuidade de $\rho$ (especificamente a continuidade $D_\infty$) garante que o risco da medida projetada aproxime o risco real.
   • Limite Inferior (Lower Bound): Corresponde ao limite inferior dependente da instância estabelecido por Chang e Tan [2022], que se baseia no problema de minimização da divergência de Kullback-Leibler (KL) $K^\rho_{\inf}$.

Principais Contribuições

1. Resolução do Problema em Aberto: O artigo prova que o $\rho$-NPTSSG alcança um regret de otimalidade de instância de $\sum_{k: \Delta^\rho_k > 0} \frac{\Delta^\rho_k \log n}{K^\rho_{\inf}(\nu_k, r^\rho_1)} + o(\log n)$ para qualquer funcional de risco contínuo $\rho$ na classe de distribuições com densidade limitada e caudas sub-gaussianas.
2. Condições Mais Fracas: O resultado requer apenas a continuidade do funcional de risco $\rho$ (especificamente em relação à métrica de Lévy–Prokhorov). Isso é estritamente mais fraco do que:
   • A condição de "dominância" exigida para o $\rho$-MTS paramétrico.
   • A condição de Lipschitz exigida para algoritmos do tipo UCB.
   • Isso permite as primeiras garantias de otimalidade de instância para funcionais não-Lipschitz, como a razão de Sharpe, sem assumir distribuições de recompensa paramétricas.
3. Lema de Discretização: O artigo introduz um lema técnico que controla um posterior de Dirichlet de alfabeto crescente em uma resolução fixa. Este lema é de potencial interesse independente para qualquer problema envolvendo processos de Dirichlet com suporte crescente.
4. Extensão Sub-Gaussiana: Os autores estendem os resultados de suporte limitado para a classe mais ampla de distribuições sub-gaussianas (incluindo braços gaussianos) via uma abordagem de discretização truncada, removendo a necessidade de um intervalo de suporte pré-especificado.

Resultados

• Teorema 1 (Suporte Limitado): Estabelece a otimalidade assintótica para $\rho$-NPTS em $P(B)$ sob continuidade isolada.
• Teorema 2 (Sub-Gaussiana): Estabelece a otimalidade assintótica para $\rho$-NPTSSG em $P(B, \sigma)$.
• Validação Experimental: O artigo apresenta quatro experimentos validando a teoria:
  1. O $\rho$-NPTS acompanha o limite inferior de otimalidade de instância para CVaR em braços Beta, superando a linha de base Risk-LCB (que possui um limite de $\log^2 n$).
  2. O $\rho$-NPTS alcança um regret de $O(\log n)$ para a razão de Sharpe em braços normais truncados, um caso onde nenhum algoritmo anterior forneceu garantias devido à não-Lipschitzness.
  3. O algoritmo lida com funcionais compostos (ex: $0.5 \text{CVaR} + 0.5 \text{Sharpe}$) sem modificação.
  4. O $\rho$-NPTSSG converge para o limite inferior de otimalidade de instância para braços Gaussianos, igualando o desempenho do algoritmo especializado Normal-Gamma Thompson Sampling (Shah et al. [2025]) sem assumir recompensas Gaussianas.

Significância e Alegações
O artigo afirma resolver o status teórico do Thompson Sampling não paramétrico para bandidos avessos ao risco. Ele demonstra que esses algoritmos não são meramente heurísticas empíricas, mas são provadamente otimizáveis assintoticamente.

A significância reside na relaxação das suposições:

• Praticantes podem usar observações brutas sem pré-especificar uma grade de recompensa ou ajustar um tamanho de alfabeto.
• O método aplica-se a uma classe estritamente mais ampla de funcionais de risco (incluindo a razão de Sharpe) e classes de distribuição (sub-gaussiana) do que os métodos ótimos anteriores.
• O resultado subsume o trabalho concomitante de Shah et al. [2025] ao fornecer uma constante mais nítida de otimalidade de instância para a razão de Sharpe sem exigir priors conjugados ou suposições paramétricas.

Os autores observam que a suposição de densidade limitada é necessária para os limites de probabilidade de bin utilizados na prova e não se aplica a distribuições com massas de ponto (ex: Bernoulli), para as quais o $\rho$-MTS paramétrico permanece a solução complementar. Direções de trabalhos futuros identificadas incluem bandidos contextuais, recompensas de cauda pesada (heavy-tailed) e distribuições discretas.