Resumo Técnico: Experimentação para Diferentes Políticas de Agendamento em Filas

Declaração do Problema

Em data centers modernos, algoritmos de agendamento são críticos para distribuir cargas de trabalho através de redes de servidores, equilibrando tempos de resposta e custos computacionais. Ao implantar uma nova política de agendamento, os praticantes geralmente dependem de testes A/B para avaliar seu impacto no mundo real. No entanto, testes A/B padrão em sistemas de filas são suscetíveis a interferência markoviana (também conhecida como interferência intertemporal).

Em um teste A/B randomizado padrão, onde tarefas são atribuídas a grupos de tratamento e controle, o estado do sistema (por exemplo, comprimentos de fila) evolui dinamicamente. Uma política de agendamento aplicada a um grupo influencia a carga do servidor, o que subsequentemente afeta os tempos de resposta e os estados de fila das tarefas no outro grupo. Essa interferência faz com que estimadores "ingênuos" — que simplesmente comparam resultados médios entre os grupos — produzam viés sistemático. Especificamente, o estimador ingênuo subestima o efeito do tratamento porque a presença de uma política mais eficiente no grupo de controle encurta artificialmente as filas para o grupo de tratamento, e vice-versa.

Embora estimadores Diferenças-em-Q (DQ), introduzidos por Farias et al. [2022], tenham sido propostos para mitigar esse viés somando recompensas futuras para estimar valores-Q, esses estimadores frequentemente sofrem de alta variância devido à acumulação de ruído ao longo de horizontes longos.

Metodologia

1. Modelo do Sistema

Os autores modelam o data center como uma rede de filas de servidores paralelos (o "modelo de supermercado") com $N$ servidores. As tarefas chegam como uma corrente de Poisson e são roteadas para os servidores com base em políticas de balanceamento de carga (por exemplo, Power-of-$d$). O estado do sistema é definido pelo vetor de comprimentos de fila. Os autores definem duas métricas de desempenho principais:

• Tempo de Resposta ($C_w$): O tempo que uma tarefa passa no sistema (espera + serviço).
• Comprimento da Fila ($C_q$): O número médio de tarefas no sistema.

O objetivo é estimar o Efeito Global do Tratamento (GTE), definido como a diferença no desempenho médio de longo prazo entre uma política de tratamento (por exemplo, Power-of-$d_2$) e uma política de controle (por exemplo, Power-of-$d_1$).

2. Fundamentação Teórica: Lei de Little

Uma contribuição teórica central é a aplicação da Lei de Little ao framework de estimação. A Lei de Little afirma que, em um sistema estável, o comprimento médio de fila de longo prazo é igual à taxa de chegada multiplicada pelo tempo médio de resposta.
Os autores provam que o GTE definido via tempo de resposta ($GTE_w$) é equivalente ao GTE definido via comprimento de fila ($GTE_q$) escalado pela taxa de chegada $\lambda$:
$$GTE_w = GTE_q = \frac{C_{1,q}(\lambda) - C_{0,q}(\lambda)}{\lambda}$$
Essa equivalência permite que os autores tratem o comprimento de fila e o tempo de resposta como proxies intercambiáveis para o efeito do tratamento, desde que a taxa de chegada seja levada em conta.

3. O Estimador Diferenças-Mistas-em-Q

Para abordar a alta variância dos estimadores DQ padrão, os autores propõem um Estimador Diferenças-Mistas-em-Q.

• DQ Padrão: Estima o GTE somando as diferenças nos custos (tempo de resposta ou comprimento de fila) ao longo de um horizonte truncado $L$ para todas as tarefas futuras que seguem uma atribuição de tratamento.
• Abordagem Mista: Reconhecendo que as funções-Q baseadas em comprimento de fila e as funções-Q baseadas em tempo de resposta são fortemente correlacionadas, os autores empregam uma técnica de variável de controle. Eles constroem uma função-Q mista:
  $$\hat{Q}^{\alpha, L}_{mix} = \alpha \hat{Q}^L_w + (1-\alpha) \frac{\hat{Q}^L_q}{\lambda}$$
  onde $\alpha$ é um peso ótimo escolhido para minimizar a variância do estimador misto. O $\alpha^*$ ótimo é derivado analiticamente com base nas variâncias e covariância dos estimadores individuais.

Este método aproveita as propriedades estruturais dos sistemas de filas (especificamente a Lei de Little) para reduzir a variância sem sacrificar as propriedades de redução de viés da abordagem DQ original.

Contribuições Principais

1. Framework de Teste A/B para Data Centers: O artigo estabelece um framework rigoroso de teste A/B dentro do modelo de supermercado, capturando explicitamente o impacto no desempenho de estratégias de agendamento alternativas sob experimentos randomizados.
2. Estimador Diferenças-Mistas-em-Q: Os autores propõem um novo estimador que generaliza o estimador DQ de Farias et al. [2022]. Ao combinar funções-Q de comprimento de fila e tempo de resposta via Lei de Little, o método alcança variância significativamente menor enquanto mantém baixo viés.
3. Validação Extensiva por Simulação: O estudo valida o método proposto em diversos e desafiadores cenários, incluindo:
   • Taxas de serviço heterogêneas.
   • Taxas de chegada não estacionárias (padrões cíclicos).
   • Atrasos de comunicação entre despachador e servidores.
   • Tempos de serviço não exponenciais (tanto constantes quanto distribuições Pareto de cauda pesada).
   • Comparação contra designs experimentais de "switchback" (alternância).

Resultados

Os experimentos numéricos (conduzidos com $N=20$ servidores e taxas de chegada variáveis) demonstram o seguinte:

• Redução de Viés: O estimador ingênuo exibe viés significativo (subestimando o efeito do tratamento) devido à interferência. Tanto os estimadores DQ padrão (baseados em comprimento de fila e tempo de resposta) quanto o estimador DQ misto reduzem com sucesso esse viés.
• Redução de Variância: Embora os estimadores DQ padrão reduzam o viés, eles frequentemente exibem desvios padrão 50–500 vezes maiores que o estimador ingênuo. O Estimador DQ Misto mitiga significativamente esse problema. Em configurações homogêneas, ele reduz o desvio padrão por um fator de 2 a 5 em comparação com os estimadores DQ padrão.
• Erro Quadrático Médio (MSE): Em todos os cenários testados (homogêneo, heterogêneo, não estacionário, com atraso e tempos de serviço não exponenciais), o Estimador DQ Misto consistentemente alcança o menor MSE entre todos os estimadores comparados (Ingênuo, Grupo, qDQ, wDQ e Switchback).
• Robustez: O método permanece eficaz mesmo sob tempos de serviço de cauda pesada e atrasos de comunicação. Em configurações não estacionárias, o Estimador DQ Misto supera os designs de switchback, mesmo quando a taxa de chegada é periódica (um cenário teoricamente favorável aos switchbacks).
• Sensibilidade à Truncagem: Um estudo de ablação sobre o comprimento de truncagem $L$ revela uma compensação entre viés e variância. Os autores encontram que $L = 30N\lambda$ fornece um equilíbrio robusto, e o Estimador DQ Misto converge mais rápido que seus contrapartes mesmo com $L$ menor.

Significado e Alegações

O artigo alega que o significado principal deste trabalho reside em demonstrar que incorporar conhecimento de domínio — especificamente as propriedades estruturais dos sistemas de filas como a Lei de Little — pode melhorar substancialmente a confiabilidade da avaliação de desempenho em testes A/B.

Os autores argumentam que confiar apenas na análise teórica sob suposições restritivas é insuficiente para a prática industrial. Em vez disso, seu Estimador DQ Misto proposto oferece uma solução prática e fácil de implementar que reduz significativamente tanto o viés quanto a variância na presença de interferência markoviana. Isso permite que operadores de data centers avaliem com mais precisão o impacto no mundo real de novos algoritmos de agendamento antes da implantação total.

O artigo conclui modestamente, observando que, embora a metodologia seja demonstrada no modelo de supermercado, ela é amplamente aplicável a configurações gerais de redes de filas. Trabalhos futuros são identificados como o desenvolvimento rigoroso de procedimentos de inferência para o estimador e a extensão do framework para cenários complexos, como inferência de Modelos de Linguagem Grandes (LLM).