Textos Gerais

Teoria da Decisão, Problemas de Parada Ótima e Multi Armed Bandits. E como saber quando é a hora certa de abandonar um projeto pessoal. Ou um projeto na sua empresa

Na vida diária, é comum termos uma ocupação central (day job) e um ou um par de projetos pessoais que rodamos em paralelo. Nesse contexto, uma decisão importante e com frequência negligenciada (em relação a outras decisões relacionadas) é a de quando devemos abandonar um projeto pessoal e procurar por outro para substituí-lo. O conjunto de projetos pessoais disponíveis é potencialmente muito alto. Desse modo, é racional que a decisão de abandonar ou não um projeto atual também leve em consideração as características das alternativas (projetos) existentes.

Esse foi o objeto de estudo de McCardle, Tsetlin e Winkler, que acabou de ser publicado na Operations Research [1]. No modelo que propõem, um agente executa uma sequência de projetos pessoais. A probabilidade de um dado projeto ser completado com sucesso varia ao longo do tempo, à medida que diferentes projetos vão sendo executados. Essa variação dependerá da relação entre o tempo médio necessário para descobrir que um projeto atingiu êxito e o tempo necessário pra saber se ele falhou. No geral, se o “sucesso” chega mais rápido que a “falha”, a probabilidade de conclusão com êxito aumenta, do contrário diminui. Alternativamente, o agente pode abandonar o projeto atual (antes de saber se falhou ou não) e selecionar um novo projeto do pool de projetos disponíveis. Aqui, a pergunta fundamental é qual é o custo de oportunidade de não perseguir novas idéias, ou seja, de insistir com um projeto em detrimento de outros, ou quanto tempo você deve esperar antes de desistir.

Empiricamente, parece existir uma inércia natural movida a vieses cognitivos, como status quo, a falácia dos custos irrecuperáveis, escalada de comprometimento, viés de confirmação, indisposição em admitir falhas, etc. Nesse cenário em que continuar um projeto é a decisão inercial, é possível que seja vantajoso propor uma regra automática cuja aplicação transforme o abandono de um projeto na opção default.

No empreendedorismo tradicional existem métricas simples e acessíveis que ajudam a avaliar o desempenho de um projeto (impacto direto sobre o market share da empresa, sobre os lucros, etc.). No extremo oposto, a avaliação das atividades de pesquisa depende de tentar acessar os resultados parciais por meio de relatórios infrequentes e produzidos pelo próprio pesquisador, que vê incentivos para enfatizar os aspectos positivos do que foi desenvolvido (e semi-omitir o que pode ser interpretado como falha de execução ou uma aposta equivocada). Ou seja, o esforço de desenvolvimento não é inteiramente observável por quem financia a pesquisa e toma decisões que a afetam.

Nesse contexto, McCardle e colegas propuseram um modelo prescritivo de apoio a decisão aplicável a casos em que se tem pouca ou nenhuma informação sobre o progresso real do projeto em questão. A única informação que quem decide tem é que ambos estados, “sucesso” e “falha”, ainda não foram atingidos. Essa é uma realidade aplicável à P&D no setor farmacêutico (ao menos nos estágios iniciais dos projetos), às atividades de prospecção de petróleo/gás natural, à pesquisa acadêmica, ao desenvolvimento de novos produtos ou mesmo ao processo de prospecção de novos fornecedores ou parceiros de negócios (exemplo de interpretação: “completar um projeto com sucesso” = “fechar um acordo e perceber os benefícios”).

No caso de projetos pessoais, o próprio desenvolvedor é responsável pela decisão de continuidade ou abandono, mas isso não torna a decisão mais fácil. Pode ser difícil aceitar que se escolheu/organizou um projeto condenado a falhar ou que se falhou na sua execução. Assim, tende a ser útil ter uma regra fixa que recomende uma decisão.

Bandido Multi Armado

Nosso problema está relacionado ao clássico problema da parada ótima para processos que podem ser representados pelo modelo do “Bandido Multi Armado”. Em Teoria da Probabilidade, o problema do bandido multi-armado envolve a alocação de um conjunto limitado de recursos entre um conjunto de alternativas. No entanto, no momento da decisão há informação incompleta sobre cada alternativa, que vão se revelando gradualmente ao longo do tempo. O problema é melhor representado como um experimento repetido, em que as propriedades de cada alternativa vão sendo melhor compreendidas à medida em que alocamos recursos a cada uma delas e observamos os resultados. Imagine um apostador com um dado orçamento para gastar em um conjunto de máquinas caça-níqueis, que precisa escolher em que máquinas apostar, quantas vezes apostar em cada uma, em que sequência apostar, quanto apostar e, principalmente, se deve continuar apostando em uma dada máquina ou desistir dela e escolher outra para apostar. Cada máquina proporciona um retorno aleatório atrelado a uma distribuição de probabilidade a ela específica. Há uma tensão central entre “explorar” e “estudar”. Por um lado, é desejável insistir com a máquina que se observou ter o maior retorno esperado até o momento (otimização baseada no conhecimento disponível). Mas por outro lado, a maximização dos ganhos requer que se invista parte dos recursos na tentativa de descobrir máquinas com desempenho potencialmente superior (aquisição de conhecimento). Esse é um tradeoff comum em problemas de otimização e é relevante em Machine Learning (ver em especial Reinforcement Learning).

Em sua formulação mais simples, são duas máquinas: uma que seguramente retorna S e outra que pode retornar R ou 0. Considere uma doença conhecida, para a qual existem ao menos dois tratamentos farmacológicos: uma droga que já foi fartamente testada, é segura e tem eficácia conhecida; outra ainda experimental, com ótimo potencial, mas com eficácia e segura desconhecidas. Se a probabilidade a priori (prior) para a droga experimental for superior a um dado limiar, ela é selecionada para o tratamento; do contrário, o tratamento tradicional é escolhido. Esse é o cenário em [2], que introduz um arcabouço teórico para o desenvolvimento de tratamentos personalizados e adaptativos para doenças crônicas. A efetividade de cada tratamento é avaliada pela agregação de informações provenientes do monitoramento da evolução do estado do paciente e de eventos mais ou menos frequentes à ele relacionados. O timing e a intensidade desses eventos fornecem informações críticas para o apoio às decisões de tratamento. A partir da análise desse tipo de modelo são geradas estratégias ótimas que se comparam favoravelmente às recomendações mais tradicionais.

Na formulação geral, são k máquinas, k-1 delas com retornos incertos (R ou 0), que podem ser tratados como variáveis aleatórias. Há um teorema fundamental, descoberto por John Gittins [3], que afirma a existência de um Índice de Alocação Dinâmica associado aos estados de um conjunto de processos estocásticos caracterizados por uma função de retorno e uma probabilidade de terminação. O Índice de Gittins é uma medida do retorno que pode ser obtido de um processo estocástico que evolui a partir de um certo estado até a terminação; no caso das k máquinas, o índice aumenta quando uma máquina retorna R, diminui quando o retorno é 0. Numa estratégia de solução baseada no Índice de Gittins, em cada período selecionamos a máquina com maior índice; se em algum momento o maior índice ficar abaixo do índice da máquina de retorno fixo, então esta é selecionada e utilizada até o fim. Este tipo de estratégia é a solução ótima para problemas de parada envolvendo alocação dinâmica de recursos como os de interesse neste texto (agendamento estocástico).

Algumas outras aplicações importantes:

● apoio ao design de ensaios clínicos (estudar os efeitos de diferentes tratamentos experimentais, ao mesmo tempo minimizando os riscos aos pacientes/voluntários);

● roteamento adaptativo em redes de comunicação;

● montagem de portfólios de investimentos.

Voltando ao nosso problema original

Ao contrário da decisão sobre o uso de um tratamento de saúde tradicional ou experimental, nosso problema envolve escolher se continuamos o experimento corrente ou se o abandonamos e selecionamos outro experimento. Isso está mais próximo do processo de desenvolvimento de novas drogas na indústria farmacêutica. Alguns outros problemas relacionados que aparecem na literatura:

● determinação da estratégia ótima para adoção de novas tecnologias (em cada período, escolher se continua experimentando/coletando informações para avaliar as chances de sucesso, se a aprova para uso ou se a rejeita; em geral a solução envolve o uso de programação dinâmica);

● avaliação diagnóstica de pacientes em uma fila congestionada (decidir se executa outro teste, se manda o paciente pra casa ou se o seleciona para tratamento);

● gerenciar o processo de aquisição de informação necessária para a preparação de uma vacina para conter o próximo ciclo epidêmico de uma nova variação de uma doença contagiosa (há ambos, uma data limite e um número finito de alternativas de configuração).

Além disso, diferente da maioria dos trabalhos relacionados na literatura, McCardle e colegas endogeinizaram a determinação do custo de oportunidade associado à continuidade do projeto atual.

Na figura, o resumo dos principais resultados em [1]; para essa simulação foi considerada uma taxa de desconto nula e que os estados de “sucesso” e “falha” são atingidos com o mesmo tempo. Além disso, assumiu-se que não existe um tempo mínimo para se trabalhar em um projeto. No entanto, os autores apresentam resultados para diversos outros casos de interesse (por exemplo, é comum que um projeto tenha um custo fixo significativo, seja pela montagem de um laboratório, o recrutamento de voluntários, a realização de um levantamento inicial da literatura relacionada existente, etc.)

Para um amplo espectro de probabilidades a priori (priors) de que um projeto será completado com êxito - por exemplo, para 0 < p < 0.5 -, a determinação da solução ótima (t*, a melhor hora para abandoná-lo) é relativamente insensível às variações de p. Note que, em muitos contextos reais, ter uma baixa probabilidade de sucesso é bastante comum; considere, por exemplo, os projetos para desenvolvimento de novas drogas na indústria farmacêutica. Isso também é bastante conveniente, já que em muitos casos (inovação) é difícil fazer uma estimativa razoável para a probabilidade a priori p.

Por outro lado, t* é sensível à \lambda_zero, a taxa de chegada de novos projetos (associado ao tempo que você gasta para encontrar um novo projeto que queira desenvolver) e à rapidez com que os estados de “sucesso” e “falha” são alcançados.

A interpretação mais realista para aplicabilidade desses resultados é que eles devem ser usados para criar uma espécie de “alarme”: se seu projeto ainda não alcançou qualquer resultado quando esse alarme parar de tocar isso deve ser interpretado como um sinal de que você deve abandoná-lo e investir na busca de outro projeto.

Referências

[1] McCardle et al (2018). When to Abandon a Research Project and Search for a New One. Operations Research.

[2] Negoescu et al (2017). Dynamic Learning of Patient Response Types: An Application to Treating Chronic Diseases. Management Science.

[3] Gittins, J.C. (1979). Bandit Processes and Dynamic Allocation Indices. Journal of the Royal Statistical Society, Series B, Vol. 41, No. 2., pp. 148–177.