Você já ficou na dúvida entre ir em um restaurante que gosta ou experimentar um novo que ainda não conhece? Este texto é sobre o dilema entre prospectar novas possibilidades ou aproveitar aquelas que você já conhece. Saiba que existem alguns algoritmos que nos ajudam nisso.

Vamos imaginar uma situação. Você recebeu um convite para participar de uma pesquisa de 90 dias na Keio University, em Tóquio. É sua primeira vez na cidade e ainda não conhece nada. Na sua rua há três restaurantes que parecem bem legais e com pratos parecidos. Você está com fome e entra no mais próximo da sua casa. Naquele dia, sua experiência foi boa, nenhum prato veio esculachado, mas também não teve nada de excepcional.

No dia seguinte, você deve ir ao mesmo lugar ou tentar um novo restaurante? Esta é uma dúvida que sempre consome minha paciência em viagens (e aposto que acontece o mesmo com muitos de vocês).

A boa notícia é que a matemática pode nos ajudar. Esse é um tipo de problema conhecido como “Explore”(prospectar)/“Exploit”(aproveitar), ou seja, uma situação de tensão sobre quando devemos parar de explorar as opções existentes e focar em aproveitar aquela que achamos ser a melhor.

Como isso funciona? Vamos entender isso de uma forma didática. Suponha que os três restaurantes da sua nova rua em Tóquio lhe traga diferentes níveis de satisfação (um indicador arbitrário que inventei para facilitar o entendimento):

Restaurante A: em média 10 pontos (com desvio padrão de 6)
Restaurante B: em média 8 pontos (com desvio padrão de 3)
Restaurante C: em média 6 pontos (com desvio padrão de 9 pontos)

A solução ótima seria você visitar todos os dias o Restaurante A, o que lhe trará uma recompensa esperada de 900 pontos de satisfação durante a sua estadia na capital japonesa. Para chegar neste valor, eu apenas multipliquei os pontos de satisfação do Restaurante A (10 pontos) pela quantidade de dias total (90 dias).

Mas você acabou de chegar na cidade, como vai saber disso? Não tem com saber. Não tem qualquer conhecimento sobre essas distribuições. Você pode tentar explorar diferentes estratégias para maximizar o seu resultado.

Uma possibilidade é adotar a estratégia “Explore”, ficar testando os restaurantes durante toda a sua estadia. Em cada dia você vai num diferente. No nosso exemplo só existem três restaurantes, então no dia de sua partida, após 90 dias, você terá ido 30 vezes em cada um.

A recompensa esperada, neste caso, é 720 pontos de satisfação. O resultado veio da soma da multiplicação da média de cada restaurante pelo total de visitas (30 cada). O valor está abaixo da solução ótima de 900 pontos.

Outra possibilidade é adotar a estratégia “Exploit“. Você visita cada restaurante uma única vez, e, a partir do conhecimento gerado sobre a situação após as visitas, aproveita durante todo o tempo restante aquele que achou melhor.

No primeiro dia você visitou o Restaurante A, mas especialmente desta vez estava em falta o salmão. Que decepção. A sua satisfação ficou em 7 pontos (veja que é um valor possível de acordo com a distribuição). No segundo dia, você visitou o Restaurante B, que tinha todos os pratos e o atendimento aconteceu dentro do esperado. Satisfação de 8 pontos. No terceiro dia, a visita é no Restaurante C. Que tragédia. Além de não terem alguns pratos disponíveis, o ambiente ainda estava em obra. Satisfação de 5 pontos.

Após três dias, você tem conhecimento para sair da fase “Explore” e pular para a fase “Exploit”. O Restaurante B foi o melhor da sua experiência, então deve passar os outros 87 dias aproveitando esta opção. A recompensa esperada, neste caso, é 716 pontos de satisfação. Ficou abaixo até mesmo da estratégia de “Explore”.

O que houve de errado, se houve até uma visita a cada um dos restaurantes?
O modelo falhou em reconhecer o Restaurante A como aquele que dá a maior satisfação esperada, porque você o visitou apenas uma vez, exatamente em um dia que algo não saiu como de costume.
O desafio dos problemas “Explore/Exploit” é exatamente este: encontrar o equilíbrio entre as duas estratégias.

Na ciência da computação, esse desafio é conhecido como “O Problema do bandido de muitos braços”. O nome vem de uma inspiração com os cassinos, que disponibilizam diversas máquinas caça-níqueis que pagam prêmios como probabilidades diferentes. O problema foi considerado sem solução (e “insolucionável“) até a metade do século XX. Durante a segunda guerra, havia até uma piada entre os aliados que eles deveriam jogar esse problema na Alemanha para ocupar a cabeça dos cientistas nazistas.

O problema clássico é similar com a nossa situação dos restaurantes. Imagine agora que você está em um cassino que tem duas máquinas caça-níquel. Você jogou 15 vezes na Máquina A, ganhou 9 e perdeu 6. Na Máquina B, você jogou apenas duas vezes, ganhou uma e perdeu outra.

Qual é a melhor máquina para você continuar apostando?
De acordo com o valor esperado, a Máquina A parece ser a mais indicada por apresentar a probabilidade de 60%. Ma Máquina B é somente 50%.

Mas tem um problema nesta situação. Você explorou pouco a Máquina B. Só jogou nela 2 vezes. Pode ser que na verdade ela seja uma ótima máquina, mas que você não conseguiu descobrir por falta informação. Algo similar aconteceu quando você no restaurante certo, mas no dia errado, no nosso exemplo de Tóquio.

Então o melhor caminho é continuar explorando as diferentes máquinas?
Tudo isso vai depender do tempo que você tem para continuar jogando (o que chamamos de intervalo). Se você acabou de chegar e ainda tem mais 1000 jogadas, pode ser interessante testar mais a Máquina B para colher informações adicionais sobre o seu comportamento. Se já estiver indo embora, então aproveite a Máquina A.

Em 1979, John Gittins propôs uma medida de recompensa que pode nos ajudar com essas decisões, o que ficou conhecido como Índice Gittins. Um ponto considerado por ele no desenvolvimento de seu modelo é a tendência que o valor de uma recompensa tem de decrescer ao longo do tempo. Dada a incerteza do futuro, o presente deveria ser mais valorizado. Os economistas chama isso de desconto. Por exemplo, um possível jantar de amanhã terá 90% do valor de um jantar de hoje. Existe até uma tabela para ajudar na decisão.

O Índice Gittins para a Máquina A (9 ganhos e 6 perdas) é de 0,630; para a Máquina B (1 ganho e 1 perda), 0,634. Neste caso, o recomendando pelo índice é explorar a Máquina B. Mas faz sentido, se de acordo com a informação que temos até o momento é que esta é uma máquina pior.

Sim, porque o Índice Gittins não captura a probabilidade de uma opção ser boa ou ruim, mas o total de recompensa que você pode capturar. O índice leva em consideração os ganhos futuros. Se você ainda tiver muitas jogadas pela frente, então faz sentido explorar a Máquina B para descobrir se ela pode trazer ganhos maiores do que a Máquina A.

Mas e se for sua última chance?
Neste caso, vá para a Máquina A. Descobrir mais informações sobre a Máquina B não será mais útil porque você não poderá mais aproveitá-la. As jogadas do futuro acabaram.

Mas a estratégia baseada no Índice Gittins é limitada e deve ser aplicada em casos específicos. Se houver algum custo para mudar de opção, ela deixa de ser ótima. Se a situação também não envolver o conceito de desconto, também não é interessante utilizá-la.

Neste caso, podemos buscar alternativas trabalhando com o conceito de arrependimento. Podemos defini-lo como tudo o que você deixou de ganhar por não ter todas as informações disponíveis no início de sua jornada.

No nosso primeiro exemplo, sobre a escolhas de restaurantes em Tóquio, fica fácil de entender o que é o arrependimento. Vimos que a solução ótima (escolher sempre o Restaurante A), resultaria em uma recompensa esperada 900 pontos de satisfação. Mas ao simular o uso apenas da estratégia de “Explore”, a recompensa esperada foi de 720 pontos. Subtraindo este valor da solução ótima, chegamos ao arrependimento de 180 pontos.

Existem diferentes algoritmos para minimizar o arrependimento.

A estratégia Thompson Sampling basicamente nos diz para fazer tudo em proporção ao quanto sabemos ser a melhor opção. Se tivermos 80% de certeza que o Restaurante A é o melhor, então devemos ir lá 80% das vezes.

A estratégia Episolon-decreasing nos diz para investir uma proporção randômica do tempo explorando coisas novas, mas diminuir a proporção conforme ganhamos informação.

Por fim, a estratégia Limite Superior de Confiança é uma das queridinha dos pesquisadores. Este algoritmo nos diz para ignorar a média e os limites baixos da distribuições. Devemos nos importar apenas com os limites superiores, escolhendo a opção que pode nos dar o maior benefício. Focar na melhor saída possível é matematicamente uma das melhores maneiras de evitar arrependimentos. Este é um argumento computacional para o otimismo.

Um aprendizado importante é que vamos sempre experienciar o “Arrependimento Logarítmico”. Isso quer dizer que o nosso arrependimento sempre crescerá (o que é uma má notícia), mas a taxa desse crescimento sempre decairá ao longo do tempo (o que é uma boa notícia).

As áreas de psicologia e ciência cognitiva estudaram a relação desses tipos de algoritmos com o processo de desenvolvimento humano.

Alison Gopnik, professora de Berkeley, argumenta sobre a importância da infância. Vimos até aqui a fase “Explore”, no início de uma jornada, é estratégica para coletar informações e gerar conhecimento sobre o problema, mas que geralmente não trazem os melhores resultados. Assim ela argumenta que a infância é um momento propício para que os humanos explorem, prospectem, sem se preocupar com recompensa, afinal uma criança será alimentada e cuidada por um responsável.

O curioso é que não vemos essa dependência dos pais em outras espécies. No início da vida, os humanos parecem livres para explorar, conhecer e aprender, o que resultará em melhores decisões mais tarde.

Na velhice, as pessoas tendem a fechar seus leques de opções, focando naquelas que as fazem felizes. Laura Carsten, professora de Stanford, dedicou sua carreira às pesquisas sobre o processo de envelhecimento. Ela argumenta que os mais velhos têm menos interações sociais por opção. Eles exploraram as possibilidades quando mais jovens, agora querem aproveitar aquelas mais significativas.

Em geral, no início da vida estamos na fase de prospecção (“Explore”), enquanto na velhice nos dedicamos a aproveitar aquilo que aprendemos (“Exploit”). Pode parecer contra intuitivo, mas a matemática nos diz que os mais velhos devem ser constantemente mais felizes do que os jovens, e foi o que Laura Carsten encontrou em suas pesquisas.

Existem algoritmos para lidar com diferentes versões do “O Problema do bandido de muitos braços”. Tudo começou com estudos específicos na área da computação. Hoje, essas estratégias são aplicadas em diversos serviços que usamos no dia a dia – desde as recomendações na Netflix ao testes A/B em projetos de Design. O curioso é que os mesmos algoritmos e estratégias também podem ser adotados pela ciência cognitiva para estudar as decisões humanas.