Como o aprendizado por reforço ajuda os varejistas

Introdução



Olá! Nossa equipe de Glowbyte Advanced Analytics desenvolve soluções de ML para indústrias aplicadas (varejo, bancos, telecomunicações, etc.). Muitas tarefas requerem soluções não padronizadas. Uma delas é a otimização das cadeias de comunicação com o cliente através do Reinforcement Learning (RL), à qual decidimos dedicar este artigo.



Dividimos o artigo em três blocos: introdução ao problema de otimização das cadeias de comunicação; introdução à RL; e no terceiro bloco, fundimos 1 e 2 juntos.



imagem



A tarefa de otimizar as cadeias de comunicação



Para começar, um pequeno glossário:



CRM é um sistema de gerenciamento de relacionamento com o cliente. Normalmente, inclui o processo de acumular e analisar o conhecimento do cliente, que é usado para melhorar as vendas e os níveis de serviço.



Um cliente é alguém que usa os serviços de uma organização.



Atributos do cliente - O conhecimento acumulado sobre o cliente. Exemplos:



  • Verificação média;
  • Frequência média de compras por mês;
  • Era;
  • Região de residência.


Campanha de marketing \ comunicação \ oferta - ofertas promocionais que os clientes recebem de uma organização. Exemplos:



  • Você recebeu XXX pontos, tem tempo para gastar até YYY;
  • Para você desconto XXX em produtos da marca YYY.


Uma cadeia de comunicação é uma sequência de campanhas de marketing.



Programa de fidelidade é um conjunto de atividades de marketing destinadas a aumentar o valor do cliente. Um exemplo típico são os cartões de desconto.



Clustering customers - dividindo os clientes em grupos, nos quais os clientes são semelhantes entre si no comportamento do consumidor.



Um sistema de recomendação é um sistema que gera as melhores ofertas ao cliente em termos de valor de negócio.



LTV (valor vitalício) - o lucro esperado do cliente durante todo o período de cooperação com ele.



Acredita-se que, ao desenvolver um programa de fidelidade, a principal tarefa de um analista é criar um sistema de recomendação de primeira classe que saiba o que, quando e em que quantidades um cliente precisa em um determinado momento. Certamente, isso é importante e até traz algum lucro, mas não é uma tarefa importante para os negócios. Qualquer organização deseja, antes de mais nada, desenvolver o hábito de seus clientes utilizarem seus serviços. O cliente ideal é aquele que utiliza exclusivamente os serviços desta organização, traz um lucro estável, recomenda serviços a amigos, mas exige um mínimo de custos ao negócio. A fidelidade do cliente não é conquistada instantaneamente e o trabalho da organização é orientar o cliente desde o primeiro pedido até as compras regulares da maneira mais eficiente.



Por exemplo, imagine um grupo escolar onde o professor precisa não apenas explicar uma regra ou um algoritmo, é importante que ele instale nos alunos o amor pelo aprendizado ou por um assunto. Um professor experiente sabe que o processo de aprendizagem nem sempre é agradável, às vezes até doloroso para ambas as partes, mas o resultado final é importante. O professor tem uma abordagem própria para cada aluno, levando em consideração diversos fatores individuais.



Ao contrário de um pequeno grupo escolar, uma organização pode ter dezenas de milhões de clientes, cada um dos quais precisa ser ajudado pela mão. Para isso, não basta adivinhar o desejo uma vez. E é claro que isso está além das capacidades humanas.



Então, quais são as nossas notas introdutórias:



  1. — (, LTV ). , , ;
  2. , , .;
  3. , , ;
  4. , , .1. , ( .2). , .


Nossa solução para este problema é baseada no conceito de Reinforcement Learning (ou Reinforcement Learning). Antes de prosseguir com a apresentação de nossa abordagem, preparamos uma pequena excursão pela teoria.



Aprendizagem por reforço. INTRODUÇÃO



O que é isso e por quê?



A tarefa do Reinforcement Learning é formar um algoritmo ideal para interagir com um determinado ambiente para atingir o resultado desejado.



Um exemplo de uso de RL é encontrar uma maneira de sair de um labirinto. Inicialmente, nada se sabe sobre o labirinto. Ao examinar diferentes opções, o algoritmo aprende a encontrar o caminho mais curto para a saída.



imagem



Quais são as características da RL do ponto de vista do ML?



O Aprendizado por Reforço é uma classe separada de algoritmos de aprendizado de máquina. Como regra, inicialmente faltam informações sobre o ambiente, ou seja, não existem exemplos rotulados de treinamento.



A peculiaridade da RL é que você pode experimentar diferentes ações, tirar uma conclusão sobre o seu sucesso, acumular o conhecimento adquirido e utilizá-lo na próxima escolha. E tantas vezes. Um processo de aprendizado iterativo, no qual o algoritmo explora o ambiente de forma independente, é uma das principais diferenças da RL.



Como RL difere da enumeração aleatória de todas as opções?



Primeiro, com a ajuda de RL clássico (sem usar redes profundas), você pode tornar a enumeração sequencial e eficiente. Um dos princípios básicos da RL é a exploração, que se alterna com a exploração do conhecimento. Ou seja, nada nos impede de combinar a aplicação do modelo e o teste, o principal é manter o equilíbrio.



Em segundo lugar, nem em todas as tarefas é possível resolver todas as situações existentes. Nestes casos, algoritmos RL avançados permitem generalizar o conhecimento acumulado para novos casos. No entanto, mesmo neste caso, a ideia de teste e aplicação conjunta permanece.



O que significa o algoritmo ideal para interagir com o ambiente?



As vitórias instantâneas nem sempre garantem o sucesso a longo prazo.



Por exemplo, no jogo de xadrez, capturar uma peça do oponente pode resultar em perdas mais caras.



Porém, escolhendo uma ação específica, podemos supor que estaremos aguardando a próxima etapa. Na próxima etapa, por sua vez, você pode supor o que acontecerá a seguir. Etc. Todo esse conhecimento pode ser levado em consideração na escolha da próxima ação. Assim, uma estratégia de comportamento é construída.



Onde é usado?



Nos jogos. Além disso, há sucessos no ensino de robôs, bots de negociação e sistemas de recomendação. Algumas referências interessantes:





Antes de mergulhar nos detalhes da terminologia, fornecemos exemplos que ilustram alguns dos recursos conceituais da RL.



Iniciantes de exemplo



Tradicionalmente, vamos começar com o bandido multi-armado.



Considere uma máquina caça-níqueis com N alças. Apenas uma alça da máquina pode ser levantada por vez.



Objetivo: identificar a ação (ou seja, a alça) que traz o retorno máximo.



Solução: podemos puxar cada alça várias vezes. Então, como a “ação ótima”, escolhemos a alça com o maior retorno médio.



E se no futuro escolhermos a melhor ação o tempo todo, essa estratégia será chamada de gananciosa .



Obviamente, tal estratégia funcionará apenas em um ambiente estacionário (ou seja, onde não há mudanças ao longo do tempo). Em um ambiente não estacionário(por exemplo, alguém altera as configurações da máquina de vez em quando) com o tempo, ao usar uma estratégia gananciosa, não haverá um resultado ideal.



Além da estratégia gananciosa, existem outras:



  • estratégia ε-greedy : em % dos casos, escolhemos a ação ideal, emϵ % - aleatório;(1ϵ)
  • Estratégia de limite de confiança superior (UCB) : na escolha de uma ação, é utilizado um coeficiente de peso, cujo valor depende de quão bem o evento é testado (ou seja, quanto menos estudado o evento, maior a probabilidade de escolha dessa ação);
  • Softmax: quanto maior o retorno esperado, maior a probabilidade de escolher esta ação.


O problema do bandido multi-armado é um exemplo do problema mais simples em que inicialmente não sabemos nada sobre o objeto de observação, ou seja, aprendemos a interagir com ele do zero. A solução para este problema é baseada no método de tentativa e erro (muito vital) e à medida que ganhamos experiência, nossas ações se tornam cada vez mais bem-sucedidas.



O que aprendemos com o exemplo:



  • Tentativa e erro também é um método;
  • A enumeração aleatória pode ser mais eficiente usando diferentes variantes de estratégias;
  • Ambientes estacionários e não estacionários separados.


Exemplo intermediário



Agora podemos complicar um pouco a tarefa e considerar uma haste como exemplo:



imagem



Uma carruagem com uma haste pode se mover para “esquerda” e “direita”.



Objetivo: você precisa aprender a manter a haste na posição vertical o maior tempo possível.



Diferença da tarefa anterior: agora é necessário levar em consideração parâmetros adicionais: ângulo de inclinação e velocidade da haste(a) e tomar uma decisão com base nessas informações. A tarefa parece mais complicada porque as combinações(v)



muito e você não poderá tentar cada um deles muitas vezes. Qualquer combinação(a;v)



(a;v) é chamado deestado. O número de estados pode ser contínuo ou finito. Os algoritmos de estado finito são geralmente mais fáceis de implementar.



Acontece que o estado é um conjunto de alguns parâmetros do sistema. Há uma suposição importante na teoria RL de que este conjunto de parâmetros deve descrever completamente o estado do sistema. Ou seja, não deve importar para nós o que aconteceu com o sistema nas etapas anteriores, é importante apenas o que observamos em um determinado momento no tempo.



O que aprendemos com o exemplo:



  • Ao escolher a ação ideal, o estado do sistema deve ser considerado. O número de estados afeta a complexidade do algoritmo;
  • Os parâmetros que descrevem o estado do sistema devem fornecer informações completas sobre o sistema no momento.


Exemplo avançado



Agora vamos dar uma olhada no jogo de xadrez.



O número de posições possíveis das peças no tabuleiro é expresso em 52 dígitos. E essa não é a única dificuldade. A diferença das duas tarefas anteriores é que, no caso do xadrez, é importante escolher não a ação que trará o resultado máximo agora, mas aquela que levará à vitória no futuro (após muitos passos à frente).



O que aprendemos com o exemplo:



  • Ao tomar uma decisão, considere o efeito de longo prazo, não o benefício imediato.


Agora, usando exemplos, definiremos os termos RL geralmente aceitos.



Terminologia RL básica



Agente é um sujeito que interage com o meio, realizando determinadas ações, recebe feedback dele e se lembra dele.



  • Por exemplo, um motor que aciona um carro com uma haste; os bandidos multi-armados são agentes.


Ambiente - o local em que o agente existe e de onde recebe feedback.



O feedback que o agente recebe do ambiente geralmente apresenta alguma incerteza.



  • Por exemplo, quando um carrinho com uma barra faz um movimento, o feedback da ação realizada é o resultado da barra cair ou não. Transporte e barra - médio.


Estado - qualquer conhecimento que ajude a tomar decisões. Os estados referem-se ao meio ambiente e o definem de maneira única em cada momento. Como regra, tais estados são escritos como um conjunto de parâmetros, matrizes ou tensores de ordem superior.



  • Por exemplo, a posição atual das peças em um tabuleiro de xadrez é um estado.


Ação - ações que estão disponíveis para o agente. Como regra, o número de ações no espaço é finito.

  • Por exemplo, os movimentos de uma barra para a direita ou esquerda são ações.


Recompensa - feedback instantâneo que um agente recebe por ações. Ou seja, é o resultado da ação realizada. A recompensa é sempre um número.



  • Por exemplo, ganhar um autômato em um problema de bandido multi-armado é uma recompensa.


Objetivo - Como regra, o objetivo do agente é maximizar a recompensa total. Em outras palavras, o objetivo final é maximizar a recompensa não na etapa atual, mas a recompensa final com base nos resultados da sequência de etapas.



  • Por exemplo, nosso objetivo não é segurar o pivô uma vez, mas o maior tempo possível.


Estratégia - mapeamento de estados em ações. Por exemplo, a probabilidade de escolher a ação A no estado S.



Declaração formal do problema



  1. Em cada etapa, o ambiente pode estar no estado .sS
  2. Em cada etapa, o agente seleciona uma ação do conjunto de ações disponíveis acordo com alguma estratégia π.aA
  3. O ambiente diz ao agente qual é a recompensa ele recebeu por isso e em que condiçõesrsS então acabou por ser.
  4. O agente ajusta a estratégia π.


Tudo parece simples. Há uma questão não resolvida - de onde vem a misteriosa estratégia π , ou seja, como o agente toma uma decisão em cada etapa.



Como na parte final do artigo será proposta uma solução baseada em Q-learning, iremos deliberadamente focar apenas em métodos tabulares.



Algoritmos Tabulares RL



Alguns dos métodos fundamentais de RL são métodos tabulares, usados ​​para tarefas nas quais os conjuntos de estados e ações são finitos. Uma característica de tais métodos é o uso de tabelas de estado-ação. As linhas são geralmente estados adiados, as colunas são ações. As células contêm os valores da função de valor.



imagem



Q(si;aj) - valor da açãoaj é capazsi . Em termos gerais, este é o benefício esperado que receberemos se escolhermos uma açãoaj , estando em um estadosi . Na primeira etapa, os valores inicializados, por exemplo, com zeros. Para o exemplo do labirinto, a tabela inicial de Estado-Ação pode ser semelhante a esta: Aqui, o estado é a posição (célula do labirinto) na qual o agente está localizado. Após realizar qualquer ação, nosso agente muda de estado e recebe uma recompensa. Nesta tarefa, a recompensa pode ser a seguinte:Q(si;aj)







imagem







  • 1 se o objeto encontrou uma saída do labirinto;
  • 0 caso contrário.


Além disso, depois que o agente recebeu feedback real do ambiente, o valor corrigido. Os algoritmos de correção são diferentes, por exemplo, o método Monte Carlo, SARSA, Q-learning. Leia mais sobre elesaquiouaqui. Por exemplo, as fórmulas Q-learning e SARSA parecem muito semelhantes à primeira vista: ambos os métodos usam o valor esperado da ação na próxima etapa. É recebido de forma muito simples: digamos que o agente está no estadoQ(si;aj)







imagem



e executa a açãosi . Em seguida, o ambiente informa ao agente que como resultado de sua ação ele recebe uma recompensaaj e novo estadorisk . Usando a tabela Status-Ação, você pode encontrar a linha com o statussk e determinar o valor que esta ou aquela ação terá.



A diferença é que no Q-learningQ(sk;a) é sempre o valor máximo em um novo estado. Já no método SARSA assume-se que o agente simula a escolha da ação no estado , por exemplo, de acordo com a estratégia ε-gulosa ou UCB. Ao usar a estratégia gulosa, os métodos são equivalentes. A desvantagem de tais algoritmos é a necessidade de armazenar a tabela Estado-Ação. Algumas tarefas podem ter um grande espaço de estado e ação, o que torna impossível usar os métodos de tabela clássicos. Nesses casos, as abordagens são usadas para aproximar os valoressk



usando redes neurais. A programação dinâmica pode ser uma alternativa aos métodos de tabela. Não vamos nos alongar sobre esses algoritmos, mas recomendamos a leitura do livroReinforcement Learning de R. S. Sutton e E. G. Barto. É aqui que terminamos a teoria e depois falamos sobre como o Aprendizado por Reforço pode ser usado em uma tarefa aplicada.Q(si;aj)











Encontrar a estratégia de incentivo ideal para o cliente usando Reinforcement Learning



Declaração do problema em termos de negócios



Restrições sob as quais nossa abordagem foi desenvolvida:



  • A solução deve ser flexível às limitações da política de comunicação com os clientes;
  • A função a ser otimizada deve ser orientada por objetivos de negócios e pode ser mais complexa do que uma simples resposta;
  • ;
  • ( , , , );
  • .


RL



Assim,

Agente e Ambiente é um sistema de programa de fidelização que envia comunicações ao cliente com propostas de marketing e ao próprio cliente.



Estado é o estado do cliente, caracterizado por atributos do cliente.



Ações são ofertas de marketing (por exemplo, “obtenha X% de desconto na compra Y”). Supõe-se que a lista de propostas é fixa e finita.



Recompensa é alguma função de mudar o comportamento do cliente (por exemplo, aumentar a receita ou responder a uma campanha direcionada).



imagem



Abordagem de solução



Agora, vamos olhar para as soluções possíveis usando métodos tabulares de Aprendizado por Reforço.



O algoritmo de solução usando Q-Learning ou Sarsa pode ser o seguinte:



1. Definição de estados do cliente



O estado do cliente pode ser especificado usando atributos do cliente. A maioria desses atributos são números reais, portanto, antes de usar métodos tabulares, os atributos devem ser discretizados para obter um conjunto finito de estados.



Em nossa solução, utilizamos os clusters obtidos como resultado do agrupamento da base de clientes com base nos atributos selecionados como estados do cliente. O número de clusters afeta a rapidez com que o algoritmo aprende. As recomendações gerais são as seguintes:



  • para poder gerir o fluxo de clientes de cluster para cluster, é necessário que a lista de atributos inclua aqueles que podem ser alterados pela influência da presença e reacção às ofertas de marketing;
  • dentro de cada cluster, os clientes devem ter comportamento homogêneo;
  • a atualização de atributos deve ser possível em uma base regular;
  • em cada cluster, o número de clientes deve ser superior ao mínimo estabelecido (o mínimo pode ser devido, por exemplo, a restrições no número mínimo de clientes para que os resultados sejam significativos)


2. Escolha de recompensa



A escolha da recompensa é o estágio mais importante no desenvolvimento do sistema. Por essa tarefa, a recompensa pode caracterizar o sucesso da campanha. Por exemplo, as opções possíveis são:



  • Conversão por oferta;
  • Aumento em resposta a uma oferta;
  • Receita específica por participante da campanha;
  • Lucro específico levando em conta custos;
  • ...


Voltando ao problema de aumentar a lealdade do cliente, a métrica alvo pode ser LTV ou a métrica da proximidade do cliente com o segmento fiel.



De qualquer forma, a escolha da recompensa deve estar alinhada aos objetivos de marketing.



PS Algumas das opções de remuneração propostas são calculadas agregadas por um grupo de clientes (por exemplo, o aumento na resposta às ofertas é a resposta do grupo alvo menos a resposta do grupo de controle). Nesse caso, seria mais correto dizer que escolhemos uma ação não para um cliente, mas para um cluster de clientes (que estão no mesmo estado), dentro do qual a recompensa é calculada.



3. Escolha de ações possíveis



Ações são propostas de marketing que podem ser enviadas ao cliente. Ao escolher as campanhas de marketing a serem utilizadas no sistema, tenha em mente:



  • a proposta de marketing não deve mudar de lançamento para lançamento;
  • a escolha do número de sentenças afeta a taxa de aprendizagem do algoritmo;
  • um cenário deve ser considerado quando nenhuma das campanhas é adequada para o estado (por exemplo, todas as variantes de oferta trazem receita negativa). Nesse caso, uma das ações pode ser “campanha padrão”. Pode ser alguma mala direta básica que pode ser enviada a todos os clientes, ou a ausência de uma oferta (ou seja, é possível que seja mais lucrativo não enviar nada para o cliente).


4. Projetar um algoritmo de seleção sujeito a restrições



Ao projetar um algoritmo, deve-se considerar:



  1. (, iphone, iphone).
  2. , .
  3. .
  4. Q-learning SARSA . , , .
  5. , ( ) -.


5. Inicialização da tabela Estado-Ação



Inicialmente, a tabela Estado-Ação se parece com isto:



imagem



O lançamento posterior do sistema é possível na ausência de lançamentos históricos para as campanhas selecionadas, o que é uma vantagem importante do conceito.



Porém, se houver um determinado histórico, então ele pode ser utilizado, ou seja, é possível o pré-treinamento retrospectivo da tabela Estado-Ação:



  1. Inicialize a tabela Estado-Ação com zeros
  2. Pegue o histórico de lançamento da campanha X. Calcule os estados dos clientes participantes da campanha no momento do lançamento e no final da campanha. Calcule a recompensa recebida em cada estado.
  3. De acordo com a fórmula para Q-learning ou SARSA, recalcular a tabela Estado-Ação levando em consideração os valores esperados dos valores da campanha no próximo lançamento.


6. Treinar o algoritmo em lançamentos piloto



O objetivo do nosso sistema é aprender a selecionar as melhores ofertas para toda a base de clientes. No entanto, na fase de teste do sistema, recomendamos que você conduza testes piloto em uma pequena amostra representativa de clientes.



O que você precisa prestar atenção nesta fase:



  1. Mudanças nos valores na tabela Estado-Ação: conforme o histórico se acumula, os valores na tabela Estado-Ação devem se tornar cada vez mais estáveis;
  2. Dinâmica positiva do efeito das campanhas: do lançamento ao lançamento, a eficácia de cada proposta de marketing deve crescer.


Assim que (1) e (2) atingirem um platô, podemos supor que o sistema está pronto para ser implantado em toda a base de clientes.



7. Sistema de desenrolamento



Antes de começar a implantar o sistema, é aconselhável analisar a sustentabilidade dos resultados da campanha no contexto de cada estado do cliente. Como mostra a prática, apesar da estabilidade geral, em alguns estados pode haver história insuficiente ou os próprios estados podem ser instáveis ​​no tempo => temos um resultado instável.



Assim, desenvolvemos as seguintes recomendações para laminação:



  • Exclua condições instáveis ​​de rolamento;
  • Use uma estratégia ε-greedy para que o sistema possa se ajustar de forma independente às mudanças no comportamento da base de clientes;
  • Continue o monitoramento regular do desempenho do sistema.


Portanto, neste artigo, tentamos descrever o conceito de alto nível de nossa abordagem. Os resultados da operação do sistema com base no algoritmo proposto podem ser encontrados aqui .



Conclusão



Descrevemos o uso de RL para resolver o problema de seleção da cadeia ótima de ações. No entanto, deve ser mencionado que um conceito semelhante pode ser aplicado a outras tarefas de marketing, por exemplo, sistemas de recomendação, escolha do canal / horário de comunicação ideal ou seleção de um banner pessoal no site. Apesar do fato de o Aprendizado por Reforço ser inferior em popularidade aos métodos tradicionais de ML, queríamos transmitir ao leitor que RL pode ser uma solução excelente se houver necessidade de manter o retreinamento automático do sistema ou treinar totalmente o sistema a partir do zero.



A equipe GlowByte gostaria de agradecer ao X5 Retail Group pela oportunidade de implementar este caso.



All Articles