Resumo Técnico: Viabilidade Ordenada por Custo para Bandits Multi-Arma com Subsídio de Custo

Formulação do Problema

Este artigo aborda o problema dos Bandits Multi-Arma com Subsídio de Custo (MAB-CS), um framework projetado para tomada de decisão online sensível a custos, onde o objetivo é minimizar o custo cumulativo sujeito a uma restrição de qualidade. Diferentemente dos MABs padrão que maximizam a recompensa cumulativa, o MAB-CS busca o braço mais barato entre aqueles que satisfazem um limiar mínimo de recompensa esperada.

O cenário específico investigado aqui envolve uma restrição de qualidade definida em relação à melhor recompensa desconhecida no sistema. Dado um conjunto de braços $\mathcal{A} = \{a_1, \dots, a_K\}$ com recompensas esperadas $\mu_k$ e custos de amostragem conhecidos $c_k$, o conjunto viável é $S = \{a_k \in \mathcal{A} \mid \mu_k \geq \mu_{CS}\}$. O limiar é definido como $\mu_{CS} = (1-\alpha)\mu^*$, onde $\mu^* = \max_{a_k \in \mathcal{A}} \mu_k$ é a melhor recompensa desconhecida e $\alpha \in (0, 1)$ é um fator de subsídio. O braço ótimo $a^*$ é o braço mais barato no conjunto viável $S$.

O artigo define duas métricas de arrependimento:

1. Arrependimento de Custo: O custo excessivo incorrido em relação ao braço ótimo $a^*$.
2. Arrependimento de Qualidade: A penalidade incorrida quando a recompensa esperada do braço selecionado cai abaixo do limiar de viabilidade $\mu_{CS}$.

O desafio central reside em minimizar conjuntamente esses arrependimentos enquanto se estima simultaneamente o limiar desconhecido $(1-\alpha)\mu^*$ e se identifica o braço viável mais barato, sem conhecimento prévio de $\mu^*$.

Metodologia: O Algoritmo COF

Os autores propõem o algoritmo Viabilidade Ordenada por Custo (COF) para resolver o problema MAB-CS. O COF opera avaliando os braços em ordem crescente de seus custos conhecidos. Para cada braço candidato $a_\ell$, o algoritmo determina a viabilidade comparando-o com um conjunto de "braços de bloqueio" (braços mais caros que $a_\ell$).

Mecanismos-chave no COF incluem:

• Avaliação Ordenada por Custo: Os braços são testados sequencialmente do mais barato ao mais caro. O primeiro braço considerado viável é selecionado como o braço ótimo para o restante do horizonte.
• Combinação de Amostras (Agregação): Para determinar se um braço candidato $a_\ell$ é inviável, o COF não depende de uma única comparação par a par. Em vez disso, ele agrega evidências de comparações com todos os braços capazes de desqualificar $a_\ell$. Ele calcula um limite superior para a probabilidade de que $a_\ell$ seja viável em relação a cada braço de bloqueio e considera $a_\ell$ inviável assim que o produto dessas probabilidades cai abaixo de uma tolerância $\delta$.
• Amostragem Exclusiva: Se a contagem de amostras de um braço candidato ficar atrás do braço de bloqueio mais amostrado, o COF amostra o candidato exclusivamente para "alcançar", reduzindo o número total de amostras subótimas necessárias.
• Filtro BAI: Durante a avaliação de um candidato, o COF emprega um filtro que interrompe a amostragem de braços de bloqueio cujos Limites Superiores de Confiança (UCB) caem abaixo do Limite Inferior de Confiança (LCB) de outro braço de bloqueio. Isso evita desperdiçar amostras em braços estatisticamente improváveis de serem o braço de melhor recompensa ($i^*$).

Contribuições Teóricas

O artigo fornece uma análise teórica rigorosa do MAB-CS, estabelecendo limites inferiores e superiores para o arrependimento.

1. Limites Inferiores Dependentes da Instância:

   • Os autores derivam limites inferiores para o número esperado de amostras para braços baratos (custo $< c_{a^*}$) e braços caros (custo $> c_{a^*}$).
   • Uma contribuição novel é um limite inferior conjunto para uma coleção de braços. Este limite reflete a percepção de que um braço pode ser certificado como inviável se sua recompensa for pior que a recompensa subsidiada de qualquer braço arbitrário, não apenas do braço de melhor recompensa $i^*$. Isso generaliza limites anteriores que tratavam $i^*$ singularmente.

2. Limites Superiores de Arrependimento para o COF:

   • O artigo estabelece limites superiores dependentes da instância para o custo cumulativo esperado e o arrependimento de qualidade para o COF.
   • Para braços baratos, o limite é mostrado como ótimo em ordem, correspondendo à dependência $O(\log T / \Delta_{Q,k}^2)$ encontrada nos limites inferiores.
   • Para braços caros, o limite depende do máximo de dois termos: um relacionado à lacuna entre o braço e o braço ótimo, e outro relacionado à lacuna conjunta necessária para eliminar o melhor braço barato. Os autores notam uma pequena discrepância entre os limites inferior e superior para braços caros, sugerindo espaço para melhoria na análise teórica da complexidade de amostragem.

Resultados Experimentais

Os autores validam o COF através de simulações extensas em:

• Conjuntos de dados do mundo real: Goodreads (avaliações de livros) e MovieLens (avaliações de filmes), onde gêneros servem como braços de bandit.
• Instâncias sintéticas: Problemas projetados manualmente para testar comportamentos algorítmicos específicos.

Principais Descobertas:

• Desempenho: O COF supera consistentemente algoritmos de base, incluindo ETC-CS (exploração com orçamento fixo), PE-CS (eliminação par a par), UCB-CS e TS-CS.
• Robustez: Diferentemente do UCB-CS e TS-CS, que podem sofrer arrependimento linear devido à inclusão incorreta de braços baratos e inviáveis em seus conjuntos viáveis empiricamente, o COF mantém arrependimento sublinear ao testar rigorosamente a viabilidade.
• Sensibilidade ao Fator de Subsídio: Embora o PE-CS desempenhe ligeiramente melhor para fatores de subsídio ($\alpha$) muito pequenos devido a intervalos de confiança mais apertados em regimes de alta amostragem, o COF evita o platô de desempenho observado no PE-CS à medida que $\alpha$ aumenta.
• Estudos de Ablação: Experimentos confirmam que os recursos de "combinação de amostras" e "amostragem exclusiva" são críticos para a eficiência do algoritmo, reduzindo significativamente o arrependimento em comparação com variantes sem esses mecanismos.

Significado e Alegações

O artigo alega que o COF oferece um framework teórico e desempenho empírico qualitativamente superiores para problemas de bandits sensíveis a custos onde a restrição de qualidade é relativa à melhor recompensa desconhecida.

• Avanço Teórico: O trabalho fornece os primeiros limites inferiores dependentes da instância que caracterizam conjuntamente a complexidade de amostragem de múltiplos braços, oferecendo uma percepção mais profunda dos desafios estruturais do MAB-CS do que análises anteriores de pior caso ou de braço único.
• Eficiência Algorítmica: Ao evitar uma fase dedicada de Identificação do Melhor Braço (BAI) para encontrar $\mu^*$ antes de testar a viabilidade, o COF reduz a amostragem desnecessária. A estratégia de "combinação de amostras" permite que o algoritmo elimine braços inviáveis com mais eficiência do que métodos de comparação par a par.
• Aplicabilidade Prática: Os autores destacam a relevância do MAB-CS para cenários do mundo real, como roteamento de modelos de LLM, onde diferentes modelos têm custos variados e qualidade desconhecida, e o sistema deve equilibrar o custo contra um piso de desempenho relativo ao melhor modelo disponível. Da mesma forma, o framework aplica-se à seleção de modalidades de publicidade e entrega de conteúdo de serviços de streaming.

Os autores concluem que, embora o COF alcance desempenho ótimo em ordem para braços baratos e demonstre fortes resultados empíricos, trabalhos futuros devem abordar a lacuna entre os limites inferior e superior para braços caros e explorar variantes de amostragem enviesada por custo para aplicações com distribuições de custo altamente desiguais.