Aprendizagem por reforço para a logística a pedido

O algoritmo de atribuição da DoorDash foi criado ao longo dos anos para ter em conta todos estes factores e muito mais, de modo a servir melhor os consumidores, os comerciantes e os distribuidores. No entanto, dada a amplitude do problema de atribuição e o facto de não termos verdades básicas sobre quais são as melhores atribuições, as melhorias no algoritmo nem sempre são fáceis. Quando se realizou a Hackathon XIII, perguntámo-nos: "Será que um algoritmo de atribuição artificialmente inteligente poderia aprender a melhorar-se a si próprio?

O que é a aprendizagem por reforço?

A aprendizagem por reforço é um dos algoritmos de inteligência artificial mais populares e poderosos da atualidade. Alguns exemplos de aprendizagem por reforço chegaram à atualidade, como o AlphaGo, o programa de computador com aprendizagem por reforço que derrotou o melhor jogador de Go do mundo. Em suma, o objetivo da aprendizagem por reforço é aprender a melhor ação tendo em conta um estado do ambiente, de modo a maximizar as recompensas globais. Eis os conceitos fundamentais da aprendizagem por reforço, resumidos na Figura 2.

Estado: O estado atual do ambiente. Representa toda a informação necessária para escolher uma ação.

Ação: O conjunto de todos os movimentos possíveis num estado.

Recompensa: O feedback resultante da ação. Note-se que as recompensas podem ser imediatas ou atrasadas.

Política: A estratégia utilizada para escolher uma ação em cada estado.

Agente: A entidade que realiza acções e tenta aprender a melhor política.

Ambiente: O mundo com o qual o agente interage.

Eis um exemplo de aplicação para ilustrar estes conceitos. Imaginemos que estamos a conceber um robô de entregas e a ensiná-lo a recolher objectos de entrega evitando os peões. Neste caso, o robô é um agente que tenta aprender a política óptima, ou seja, a ação óptima em cada estado. Os estados podem ser a área em que o robô está a operar, com os artigos e os peões em vários locais, e as acções podem ser mover-se para a esquerda, para a direita, para a frente ou para trás. O robô recebe uma recompensa positiva quando apanha um objeto, uma recompensa negativa quando choca com um peão e nenhuma recompensa caso contrário. Com estas definições, o robô pode aprender a política óptima para apanhar todos os objectos de forma a maximizar a recompensa.

O objetivo da aprendizagem por reforço é encontrar a política óptima. Isto não é trivial, uma vez que, ao contrário dos processos de decisão de Markov, as recompensas e as probabilidades de transição entre estados são desconhecidas, como se pode ver na Figura 3. Por esta razão, existem muitas técnicas para obter esta informação (com base em modelos) ou para obter diretamente a política óptima (sem modelos), tais como Monte Carlo, Bootstrap e SARSA. O mais utilizado é o Q-learning, que é um método sem modelo e sem política que nos pode dar diretamente uma estimativa da função Q para encontrar a política óptima.

Vale a pena mencionar que, para utilizar o Q-learning, precisamos de recolher dados seguindo uma política de exploração. Quando estamos mais preocupados em aprender sobre o mundo do que em maximizar a utilidade, podemos escolher uma política de não-exploração, só de exploração, que explora o espaço de ação escolhendo sempre uma ação aleatória. Quando nos preocupamos mais com a utilidade, precisamos de equilibrar a exploração e o aproveitamento, para que possamos colher os benefícios do que aprendemos e, ao mesmo tempo, não ficarmos cegos às oportunidades que ainda não encontrámos. Uma abordagem comum no segundo caso é o algoritmo epsilon-greedy, que explora com probabilidade epsilon e explora com probabilidade 1-epsilon.

Na prática, quando há um grande número de estados, o espaço de estados é caracterizado e a aproximação de funções é utilizada para determinar a função Q. Isto faz com que a função Q seja um modelo em vez de uma tabela de pesquisa. Muitas vezes, a criação manual de características é difícil, pelo que são utilizados modelos de aprendizagem profunda, como redes neurais totalmente ligadas ou convolucionais, para representar a função Q. Esta abordagem é conhecida como Deep Q-Network (DQN) e é muito útil quando a dimensionalidade das características é elevada e o volume de dados também é elevado.

Atribuição aprendida por reforço

Agora vamos discutir como aplicámos a aprendizagem por reforço ao problema de atribuição do DoorDash. Para formular o problema de atribuição de uma forma adequada à aprendizagem por reforço, estabelecemos as seguintes definições.

Estado: As entregas pendentes e os Dashers em funcionamento, uma vez que representam o estado atual do mundo de uma perspetiva de atribuição. Note-se que isto significa que o espaço de estados é praticamente infinito, uma vez que as entregas e os Dashers podem ter individualmente muitas características diferentes (local/hora de recolha, local/hora de entrega, etc.) e podem existir muitas combinações diferentes de entregas e Dashers.

Ação: A escolha mais natural é a atribuição de Dashers às entregas. No entanto, mesmo com apenas 15 entregas e 15 Dashers, o número total de combinações excede um trilião! Por conseguinte, para reduzir significativamente o espaço de ação, definimos as acções como sendo diferentes variantes do algoritmo de atribuição com diferentes parâmetros. Isto pode ser considerado como uma afinação inteligente de parâmetros, em que o modelo aprende quais os melhores parâmetros para um determinado estado de entregas e Dashers.

Recompensa: Combinação de velocidades de entrega e eficiência do Dasher. Queremos que as entregas cheguem aos clientes o mais rapidamente possível, utilizando os Dashers da forma mais eficiente possível. Isto traduz-se na maximização das velocidades de entrega e na maximização da eficiência do Dasher. A recompensa também inclui uma penalização por entregas não entregues, para garantir que todas as entregas são efetivamente atribuídas aos Dashers e entregues aos consumidores.

Com estes conceitos definidos para se adequarem à aprendizagem por reforço, precisávamos agora de implementar os dois componentes-chave para efetuar efetivamente a aprendizagem por reforço, o ambiente e o agente.

Ambiente: Precisamos de um sistema que possa produzir estados (entregas e Dashers) e recompensas (velocidades de entrega e eficiências Dasher), bem como receber acções (variantes do algoritmo de atribuição) e, subsequentemente, atualizar os estados e as recompensas. O nosso sistema de atribuição de produção é adequado, mas corremos o risco de prejudicar as nossas entregas e clientes reais, uma vez que o agente pode escolher más acções à medida que aprende através de uma política de exploração. Felizmente, já temos um simulador para o nosso sistema de atribuição que pode receber um algoritmo de atribuição e produzir atribuições simuladas que reflectem o nosso sistema de produção. Este simulador de atribuição é utilizado para obter resultados offline antes de efetuar experiências online para o sistema de atribuição. Por conseguinte, utilizámos este simulador como ambiente, permitindo-nos treinar o nosso modelo de aprendizagem por reforço em estados/acções/recompensas que são exactos para o nosso sistema de produção sem afetar os nossos clientes.

Agente: Escolhemos uma rede neural profunda como agente, uma vez que faz sentido utilizar um modelo para a função Q e caraterizar os estados em vectores de elevada dimensão, dado o nosso espaço de estados infinito. Mais detalhes sobre esta caraterização e modelo serão abordados na próxima secção.

Um resumo de alto nível da nossa formulação do problema pode ser encontrado na Figura 4. Em resumo, o simulador de atribuição produz o estado, que o agente utiliza para escolher uma variante do algoritmo de atribuição. O simulador de atribuição executa o algoritmo escolhido e produz o novo estado e a recompensa, que são passados de volta para o agente. Este ciclo repete-se num intervalo de tempo predefinido.

Para a implementação efectiva, envolvemos o simulador de atribuição do DoorDash num ambiente OpenAI Gym e utilizámos o Keras RL para o agente e a formação, uma vez que as duas bibliotecas são compatíveis desde o início.

Agente de profundidade

Como mencionado anteriormente, utilizámos uma rede neural profunda como agente. Recorde-se que o agente mapeia pares de estado e ação para recompensas. Concretamente, a rede recebe como entrada o estado (representado por diferentes características) e prevê o valor Q para cada ação, como se pode ver na Figura 5.