Resumo Técnico: Algoritmos Baseados na Média: Um Limite Inferior e Regret

Declaração do Problema

O artigo investiga algoritmos baseados na média no contexto de aprendizado online, focando especificamente no cenário de bandido de múltiplos braços (MAB) com feedback de bandido e um horizonte de tempo desconhecido.

Algoritmos baseados na média são definidos pelo princípio de que um agente deve selecionar ações com baixas médias de recompensas passadas com baixa probabilidade no futuro. Embora a literatura recente sugira que esses algoritmos convergem favoravelmente para ações seriadamente não dominadas (aproximando equilíbrios de Nash em jogos econômicos), estudos empíricos indicam que eles sofrem de uma convergência lenta em comparação com algoritmos estabelecidos em cenários de feedback de bandido. Além disso, há uma tensão entre a "explorabilidade" desses algoritmos em jogos de principal-agente e suas garantias teóricas de convergência.

Os desafios específicos abordados são:

1. Definir algoritmos baseados na média para o cenário de horizonte desconhecido (onde o número total de rodadas $T$ não é conhecido antecipadamente).
2. Determinar os limites teóricos sobre a sequência de taxa definidora do algoritmo, $\gamma_t$, que controla o limiar para evitar ações "dominadas".
3. Esclarecer a relação entre algoritmos baseados na média e algoritmos de sem-regret-externo (no-external-regret), particularmente se um algoritmo pode possuir ambas as propriedades simultaneamente sob feedback de bandido.

Metodologia

1. Definições e Preliminares

Os autores formalizam duas definições de algoritmos baseados na média:

• $\gamma_t$-baseado na média: Baseado nas médias de recompensas atuais $\alpha_t(a)$. Se $\alpha_t(a') - \alpha_t(a) > \gamma_t$, a probabilidade de escolher $a$ em $t+1$ é no máximo $\gamma_t$.
• Predictive $\gamma_t$-baseado na média: Baseado nas médias de recompensas do próximo passo $\alpha_{t+1}$.

O artigo estabelece que essas definições são mutuamente conversíveis e foca na variante não preditiva para o cenário de bandido.

2. Algoritmos Propostos

Os autores propõem dois algoritmos adaptados para feedback de bandido e horizontes desconhecidos:

• $\epsilon$-Greedy Generalizado: Uma variante onde ações são consideradas "dominadas" se sua recompensa cumulativa estimada for significativamente menor que as outras. O algoritmo atribui uma pequena probabilidade $\epsilon_t$ às ações dominadas e distribui a probabilidade restante entre as ações não dominadas.
• Exp3 Baseado na Média: Uma variante do algoritmo Exp3 (Exponential-weight algorithm for Exploration and Exploitation). Ele utiliza pesos multiplicativos baseados em recompensas cumulativas estimadas, com um componente de exploração $\epsilon_t$ para garantir amostragem suficiente.

Ambos os algoritmos utilizam estimadores ponderados por importância para lidar com a falta de feedback completo.

3. Derivação do Limite Inferior Teórico

Para determinar o limite fundamental de quão rápido esses algoritmos podem aprender, os autores derivam um limite inferior na sequência de taxa $\gamma_t$.

• Construção Adversária: Eles constroem dois ambientes adversários específicos ($x'_t$ e $x''_t$) que exploram o dilema exploração-explotação. Nesses ambientes, um algoritmo deve distinguir entre duas ações que inicialmente parecem similares, mas divergem posteriormente.
• Argumento de Indistinguibilidade: Devido ao feedback de bandido, se o algoritmo jogar uma ação específica com muita raridade (para satisfazer um $\gamma_t$ pequeno), ele não consegue distinguir entre os dois ambientes.
• Derivação da Desigualdade: Ao analisar a probabilidade de selecionar uma ação dominada nesses ambientes construídos, eles derivam uma desigualdade necessária: $\sum_{t=t_1}^{t_c-1} \gamma_t + k \cdot \gamma_{t_c} \geq 1$.
• Análise Assintótica: Eles aproximam essa soma usando integrais para mostrar que qualquer sequência de taxa que decaia mais rápido que $O(1/\sqrt{t})$ (especificamente, qualquer sequência onde $\gamma_t \in o(1/\sqrt{t})$) viola a condição necessária para que o algoritmo seja baseado na média no cenário de bandido.

4. Análise de Regret

Os autores analisam a interseção entre algoritmos baseados na média e algoritmos de sem-regret-externo. Eles demonstram que, embora os algoritmos baseados na média não garantam automaticamente o sem-regret (e possam sofrer regret linear em configurações adversárias específicas com $\gamma_t$ muito pequeno), existem configurações (especificamente certas parametrizações do Exp3) que satisfazem tanto a propriedade baseada na média quanto a propriedade de sem-regret-externo.

Principais Contribuições

1. Primeiro Limite Inferior para $\gamma_t$: O artigo fornece o primeiro limite inferior formal para a sequência de taxa $\gamma_t$ de algoritmos baseados na média no cenário de feedback de bandido. Estabelece que $\gamma_t$ não pode decair mais rápido que $O(1/\sqrt{t})$. Especificamente, qualquer sequência $\gamma_t \in o(1/\sqrt{t})$ é inválida para algoritmos baseados na média neste cenário.
2. Algoritmos de Horizonte Desconhecido: Os autores propõem dois algoritmos concretos baseados na média ( $\epsilon$-greedy generalizado e Exp3 baseado na média) que operam efetivamente sem conhecimento prévio do horizonte de tempo $T$.
3. Reconciliação de Definições: O trabalho esclarece a relação entre as definições preditivas e não preditivas de algoritmos baseados na média, mostrando sua conversibilidade.
4. Sobreposição Regret-Baseado na Média: O artigo prova que o conjunto de algoritmos baseados na média e o conjunto de algoritmos de sem-regret-externo não são disjuntos. Eles constroem uma variante específica do Exp3 que é tanto baseada na média quanto de sem-regret.
5. Validação Empírica: Através de experimentos numéricos, os autores mostram que, embora os algoritmos baseados na média possam convergir um pouco mais lentamente que seus equivalentes padrão, eles podem alcançar um desempenho competitivo tanto em cenários de MAB estocástico quanto em jogos econômicos (oligopólio de Bertrand).

Resultados

Resultados Teóricos

• Limite Inferior: A sequência $\gamma_t = \frac{1}{2\sqrt{t}+1}$ é identificada como um limiar crítico. Qualquer sequência que decaia estritamente mais rápido que esta (por exemplo, $\gamma_t = 1/t^{0.51}$ ou $\gamma_t = 1/t$) é provada como inválida para algoritmos baseados na média sob feedback de bandido.
• Regret: O artigo confirma que algoritmos baseados na média não são inerentemente "exploráveis" de uma forma que impeça garantias de sem-regret. Existem algoritmos que são simultaneamente baseados na média e de sem-regret.

Resultados Empíricos

• MAB Estocástico: Em um experimento de bandido de 10 braços, o Exp3 baseado na média proposto (com $\alpha=1/2$) mostrou uma convergência ligeiramente mais lenta para a ação ótima em comparação com uma configuração padrão do Exp3, mas a diferença foi marginal. As variantes $\epsilon$-greedy mostraram desempenho dependente da taxa de exploração.
• Oligopólio de Bertrand: Em um jogo de preços repetidos, o algoritmo Exp3 baseado na média convergiu para o equilíbrio de Nash significativamente mais rápido do que observado anteriormente em literatura similar (ex: Bichler et al., 2025). Os algoritmos $\epsilon$-greedy baseados na média foram mais lentos, atribuído à exploração excessiva quando o limiar de dominação era alto.

Significância e Alegações

O artigo alega fornecer um limite fundamental para o desempenho de algoritmos baseados na média. O limite inferior derivado explica por que esses algoritmos frequentemente aprendem lentamente: para satisfazer a condição baseada na média (evitar ações dominadas) sem feedback completo, o algoritmo deve manter um certo nível de exploração. Se a taxa de exploração cair muito rapidamente (ou seja, $\gamma_t$ torna-se muito pequeno), o algoritmo não consegue distinguir entre ambientes e é forçado a jogar ações dominadas, violando a definição baseada na média.

Os autores posicionam seu trabalho como um passo necessário para reconciliar as preocupações de "explorabilidade" em jogos de principal-agente com as garantias de convergência na teoria dos jogos. Ao mostrar que as propriedades baseada na média e de sem-regret podem coexistir, eles sugerem que algoritmos baseados na média são uma alternativa viável para cenários de aprendizado econômico, desde que a taxa $\gamma_t$ seja escolhida cuidadosamente para respeitar o limite inferior derivado.

O artigo conclui que, embora os algoritmos baseados na média não sejam universalmente mais rápidos que os algoritmos padrão de sem-regret, eles oferecem uma classe distinta de dinâmica de aprendizado que pode ser competitiva, particularmente em cenários onde a convergência para estratégias seriadamente não dominadas é o objetivo principal. O trabalho deixa em aberto a questão de se um algoritmo pode ser construído para coincidir exatamente com o limite teórico $\gamma_t \approx 1/\sqrt{t}$ enquanto mantém o regret ótimo.