Schedules and Prioritization: A Behavioral Foundation for Multi-Armed Bandits and Stopping Problems

Resumo Técnico: Cronogramas e Priorização: Uma Fundamentação Comportamental para Bandidos de Múltiplos Braços e Problemas de Parada

Enunciado do Problema
As formulações econômicas padrão de bandidos de múltiplos braços (MAB - multi-armed bandits) e problemas de parada ótima geralmente começam com primitivos exógenos: uma coleção de braços governados por processos markovianos conhecidos, espaços de estados, estruturas de recompensa e regras de transição. O tomador de decisão é então apresentado a esses objetos e solicitado a derivar uma política ótima. Este artigo argumenta que tais formulações pulam uma etapa comportamental crucial. Em muitos contextos econômicos, os tomadores de decisão não enfrentam "máquinas" ou "braços" pré-especificados. Em vez disso, eles enfrentam "fios de responsabilidade" (ex: projetos de trabalho, obrigações familiares, experimentos) que se desenrolam em seu próprio tempo interno. O problema econômico fundamental é ajustar esses distintos fios, que evoluem localmente, em um único calendário escasso. O artigo busca fornecer uma fundamentação comportamental para problemas de bandido, derivando a estrutura do bandido a partir de preferências sobre esses fios locais, em vez de assumir a estrutura do bandido como um primitivo.

Metodologia
O artigo emprega uma abordagem axiomática enraizada na teoria da preferência revelada e na teoria da decisão recursiva. A metodologia procede em três estágios distintos:

1. Definição do Domínio Primitivo: Os objetos primitivos são definidos como cronogramas contingentes locais. Um cronograma é um mapeamento de histórias locais (tempo interno) para consequências, terminando em uma data finita ao longo de cada ramo. Esses cronogramas representam os possíveis desenrolares de um único fio de responsabilidade antes de ser colocado em um calendário comum.
2. Representação de Fio Único (Parada): Os autores impõem axiomas comportamentais sobre preferências de um único cronograma para caracterizar uma representação de parada recursiva.
   • Axiomas de fluxo determinístico (D1–D8): Estabelecem uma escala de utilidade comum para consequências atuais e um fator de desconto geométrico sobre o tempo local, garantindo estacionariedade e independência para fluxos determinísticos.
   • Axiomas recursivos de um passo (R1–R6): Regem a troca entre uma consequência atual e uma pasta contingente de continuações futuras. Eles garantem que continuações equivalentes possam ser substituídas, que melhorias em ramos sejam respeitadas e que as trocas entre presente e futuro sejam estáveis.
   • Resultado: Esses axiomas produzem uma representação de parada recursiva generalizada onde o valor de um cronograma é a utilidade atual mais um agregador descontado de valores de continuação.
3. Integração de Múltiplos Fios (Bandido): Para passar de um problema de fio único para um de múltiplos fios, o artigo introduz uma restrição de escassez: a restrição de calendário decorrido. Apenas um relógio local pode avançar por período de calendário.
   • Axioma de Compensação de Cauda Comum (R7): Uma restrição comportamental crítica é introduzida para garantir que mudanças escalares nos valores de continuação permaneçam escalares após a agregação. Esta propriedade de "aditividade de caixa" permite que um preço sombra escalar do tempo de calendário seja definido consistentemente entre diferentes fios, mesmo quando a avaliação da continuação é não linear (ex: sob ambiguidade ou dependência de ranking).
   • Resultado: Combinar a representação recursiva com a restrição de calendário resulta em um bandido generalizado descansado.

Contribuições Principais e Resultados

• Derivação da Estrutura do Bandido: O artigo demonstra que um bandido de múltiplos braços não é um objeto primitivo, mas uma representação derivada de preferências sobre cronogramas locais interrompidos sujeitos a uma restrição de calendário. Os "braços" não são máquinas markovianas exógenas, mas representam fios de responsabilidade.
• Representação de Parada Recursiva Generalizada: O Teorema 1 estabelece que as preferências sobre cronogramas interrompidos são equivalentes a uma avaliação recursiva envolvendo uma utilidade atual, desconto local e um amplo agregador de continuação. Este agregador não é restrito à utilidade esperada; ele pode acomodar ambiguidade, robustez e dependência de ranking.
• Otimalidade de Índice via Preços Sombra: O resultado central (Teorema 2) prova que a política ótima para o problema com restrição de calendário decorrido é uma política de índice.
  • O índice para um fio é definido como o preço sombra crítico do tempo de calendário no qual o tomador de decisão é indiferente entre avançar o fio e colocá-lo em espera indefinidamente.
  • Mostra-se que o axioma de "compensação de cauda comum" é a condição necessária para que este preço sombra escalar seja bem definido e para que a política de índice seja ótima.
  • A regra ótima é avançar o fio com o índice atual mais alto.
• Unificação de Casos Especiais: O arcabouço recupera modelos familiares como casos especiais ao impor restrições adicionais ao domínio do cronograma ou ao agregador de continuação:
  • Utilidade Esperada Subjetiva (SEU): Impor independência sobre cronogramas de continuação resulta em um agregador linear (núcleo de transição subjetivo), recuperando o clássico índice de Gittins–Jones.
  • Aprendizado: As crenças são tratadas como estados locais. Avançar um fio atualiza a crença (estado local), enquanto deixá-lo em espera congela a crença. Isso recupera bandidos de aprendizado bayesiano.
  • Preferências Variacionais e Max–Min: Ao permitir que o agregador seja um operador variacional ou max-min, o artigo deriva índices robustos que consideram a ambiguidade dinâmica sem vincular a incerteza entre distintos fios.
  • Preferências de Dependência de Ranking e Choquet: Estas permitem a avaliação não aditiva de ramos, capturando o "medo de perder" (fear of missing out) de resultados futuros salientes.
  • Problema de Pandora: Ao restringir o domínio do cronograma de modo que a incerteza seja resolvida em um único passo (abrir uma caixa), o índice geral reduz-se a um valor de reserva, recuperando a regra de Weitzman.

Significância e Alegações
O artigo alega fornecer uma justificativa comportamental fundamental para modelos de bandido, análoga à forma como a teoria do consumidor deriva a demanda a partir de preferências sobre cestas, em vez de assumir curvas de demanda.

• Mudança Fundamental: O artigo argumenta que leis de transição, conjuntos de ambiguidade e valores de reserva não são pontos de partida, mas emergem de restrições sobre as preferências ou sobre o domínio do cronograma. O "braço" é um fio de responsabilidade representado, e o "bandido" é um problema de priorização para o avanço local sob um calendário escasso.
• Papel do Índice: O índice não é uma regra de classificação externa imposta pelo analista, mas é derivado como o multiplicador de Lagrange (preço sombra) da restrição de calendário. Um índice alto significa que o próximo passo de um fio é valioso mesmo quando o tempo de calendário é caro.
• Flexibilidade: O arcabouço é projetado para ser amplo, acomodando várias atitudes em relação à incerteza (ambiguidade, robustez, dependência de ranking) dentro de fios individuais, mantendo a estrutura de produto do problema de múltiplos fios. Isso contrasta com a literatura de bandidos robustos que frequentemente coloca a ambiguidade no ambiente conjunto, potencialmente vinculando projetos que seriam independentes.
• Escopo: O artigo limita explicitamente seu escopo a bandidos "descansados" (os fios não evoluem enquanto não atendidos) e um único calendário. Nota que extensões para bandidos "inquietos" (restless) ou múltiplos inputs escassos são extensões naturais, mas deixadas para trabalhos futuros.

Em resumo, o artigo estabelece que a complexa maquinaria de alocação de recursos sob incerteza pode ser construída a partir dos mesmos ingredientes da escolha estática: um domínio primitivo de alternativas, restrições comportamentais que geram uma representação e uma restrição de escassez.