Comment l'apprentissage par renforcement aide les détaillants

introduction

salut! Notre équipe Glowbyte Advanced Analytics développe des solutions ML pour les industries appliquées (retail, banque, télécom, etc.). De nombreuses tâches nécessitent des solutions non standard. L'un d'eux est l' optimisation des chaînes de communication client à l'aide du Reinforcement Learning (RL), auquel nous avons décidé de consacrer cet article.



Nous avons divisé l'article en trois blocs: introduction au problème de l'optimisation des chaînes de communication; introduction à RL; et dans le troisième bloc, nous combinons 1 et 2 ensemble.

La tâche d'optimiser les chaînes de communication

Pour commencer, un petit glossaire: le



CRM est un système de gestion de la relation client. En règle générale, cela comprend le processus d'accumulation et d'analyse des connaissances client, qui est utilisé pour améliorer les niveaux de vente et de service.



Un client est une personne qui utilise les services d'une organisation.



Attributs du client - Les connaissances accumulées sur le client. Exemples:

• Chèque moyen;
• Fréquence moyenne des achats par mois;
• Âge;
• Région de résidence.

Campagne marketing \ Communication \ Offre - offres promotionnelles que les clients reçoivent d'une organisation. Exemples:

• Vous avez reçu XXX points, vous avez le temps de dépenser jusqu'à YYY;
• Pour vous XXX de réduction sur les produits de la marque YYY.

Une chaîne de communication est une séquence de campagnes marketing.



Le programme de fidélité est un ensemble d'activités marketing visant à augmenter la valeur client. Un exemple typique est celui des cartes de réduction.



Regrouper les clients - diviser les clients en groupes, au sein desquels les clients se ressemblent dans le comportement des consommateurs.



Un système de recommandation est un système qui génère les meilleures offres au client en termes de valeur commerciale.



LTV (valeur à vie) - le bénéfice attendu du client pour toute la période de coopération avec lui.



On pense que lors du développement d'un programme de fidélisation, la tâche principale d'un analyste est de créer un système de recommandation de première classe qui sait de quoi, quand et en quelles quantités un client a besoin à un moment donné. Ceci est certainement important et apporte même des bénéfices, mais ce n'est pas une tâche commerciale clé. Toute organisation souhaite avant tout développer l'habitude de ses clients d'utiliser leurs services. Le client idéal est celui qui utilise les services exclusivement de cette organisation, apporte un bénéfice stable, recommande des services à des amis, tout en exigeant un minimum de coûts de l'entreprise. La fidélité des clients ne se gagne pas instantanément et le travail de l'organisation est de guider le client de la première commande aux achats réguliers de la manière la plus efficace.



Par exemple, imaginez un groupe scolaire où l'enseignant n'a pas seulement besoin d'expliquer une règle ou un algorithme, il est important pour lui d'inculquer aux élèves le goût d'apprendre ou une matière. Un enseignant expérimenté sait que le processus d'apprentissage n'est pas toujours agréable, parfois même douloureux pour les deux parties, mais le résultat final est important. L'enseignant a sa propre approche de chaque élève, en tenant compte de nombreux facteurs individuels.



Contrairement à un petit groupe scolaire, une organisation peut avoir des dizaines de millions de clients, dont chacun doit être élevé par la poignée. Pour cela, il ne suffit pas de deviner le désir une fois. Et il est clair que cela dépasse les capacités humaines.



Alors, quelle est notre introduction:

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

Notre solution à ce problème est basée sur le concept d'apprentissage par renforcement (ou apprentissage par renforcement). Avant de procéder à la présentation de notre approche, nous avons préparé une petite excursion dans la théorie.

Apprentissage par renforcement. INTRO

Qu'est ce que c'est et pourquoi?

La tâche de l'apprentissage par renforcement est de former un algorithme optimal pour interagir avec un certain environnement afin d'obtenir le résultat souhaité.



Un exemple d'utilisation de RL est de trouver un moyen de sortir d'un labyrinthe. Au départ, on ne sait rien du labyrinthe. En examinant différentes options, l'algorithme apprend à trouver le chemin le plus court vers la sortie.

Quelles sont les fonctionnalités de RL du point de vue ML?

L'apprentissage par renforcement est une classe distincte d'algorithmes d'apprentissage automatique. En règle générale, les informations sur l'environnement sont initialement manquantes, en d'autres termes, il n'y a pas d'exemples étiquetés pour la formation.



La particularité de RL est que vous pouvez essayer différentes actions, tirer une conclusion sur leur succès, accumuler les connaissances acquises et les utiliser dans le prochain choix. Et tant de fois. Un processus d'apprentissage itératif, dans lequel l'algorithme explore indépendamment l'environnement, est l'une des principales différences de RL.

En quoi RL diffère-t-il du dénombrement aléatoire de toutes les options?

Tout d'abord, avec l'aide de la RL classique (sans utiliser de réseaux profonds), vous pouvez rendre l'énumération séquentielle et efficace. L'un des principes de base de la RL est l'exploration, qui alterne avec l'exploitation des connaissances. En d'autres termes, rien ne nous empêche de combiner l'application du modèle et les tests, l'essentiel est de maintenir un équilibre.



Deuxièmement, toutes les tâches ne permettent pas de régler toutes les situations existantes. Dans ces cas, des algorithmes RL avancés permettent de généraliser les connaissances accumulées à de nouveaux cas. Cependant, dans ce cas, l'idée de tests et d'applications conjoints demeure.

Que signifie l'algorithme optimal pour interagir avec l'environnement?

Les gains instantanés ne garantissent pas toujours un succès à long terme.



Par exemple, dans le jeu d'échecs, capturer la pièce d'un adversaire peut entraîner des pertes plus coûteuses.



Cependant, en choisissant une action spécifique, nous pouvons supposer que nous attendrons la prochaine étape. À l'étape suivante, à son tour, vous pouvez deviner ce qui va se passer ensuite. Etc. Toutes ces connaissances peuvent être prises en compte lors du choix de l'action suivante. Ainsi, une stratégie comportementale est construite.

Où est-il utilisé?

Dans les jeux. En outre, il existe des succès dans l'enseignement des robots, des robots de négociation et des systèmes de recommandation. Quelques références intéressantes:

• Learn Go: AlphaGo bat les meilleurs pros de Go
• Bot de négociation: un bot négocie avec un autre agent et son objectif est de conclure un certain accord
• Une voiture autonome
• Vous trouverez ici une sélection d'applications RL dans une grande variété de domaines

Avant de plonger dans les détails de la terminologie, nous fournissons des exemples qui illustrent clairement certaines des caractéristiques conceptuelles de RL.

Exemple de débutants

Traditionnellement, commençons par le bandit multi-armé.



Prenons une machine à sous avec N poignées. Une seule poignée de la machine peut être soulevée à la fois.



Objectif: identifier l'action (c'est-à-dire la poignée) qui rapporte le maximum.



Solution: nous pouvons tirer plusieurs fois sur chaque poignée. Ensuite, comme «action optimale», nous choisissons la poignée avec le gain moyen le plus élevé.



Et si à l'avenir, nous choisissons la meilleure action tout le temps, alors une telle stratégie sera qualifiée de cupide .



De toute évidence, une telle stratégie ne fonctionnera que dans un environnement stationnaire (c'est-à-dire où il n'y a pas de changement au fil du temps). Dans un environnement non stationnaire(par exemple, quelqu'un modifie les paramètres de la machine de temps en temps) au fil du temps, lors de l'utilisation d'une stratégie gourmande, il n'y aura pas de résultat optimal.



Outre la stratégie gourmande, il y en a d'autres:

• Stratégie ε-gourmande : en$$ % des cas on choisit l'action optimale, en$\epsilon$$$ % - aléatoire;$(1-\epsilon)$
• Stratégie de limite de confiance supérieure (UCB) : lors du choix d'une action, un facteur de pondération est utilisé, dont la valeur dépend de la qualité du test de l'événement (c'est-à-dire que moins l'événement est étudié, plus la probabilité de choisir cette action est élevée);
• Softmax: plus le gain attendu est élevé, plus la probabilité de choisir cette action est élevée.

Le problème du bandit multi-armé est un exemple du problème le plus simple dans lequel, au départ, nous ne savons rien du sujet de l'observation, c'est-à-dire que nous apprenons à interagir avec lui à partir de zéro. La solution à ce problème est basée sur la méthode des essais et des erreurs (très vitale) et à mesure que nous acquérons de l'expérience, nos actions deviennent de plus en plus fructueuses.



Ce que nous avons appris de l'exemple:

• Les essais et erreurs sont également une méthode;
• Le dénombrement aléatoire peut être rendu plus efficace en utilisant différentes variantes de stratégies;
• Environnements fixes et non stationnaires séparés.

Exemple intermédiaire

Maintenant, nous pouvons compliquer un peu la tâche et considérer une tige comme exemple:







Un chariot avec une tige peut se déplacer «à gauche» et «à droite».



Objectif: vous devez apprendre à maintenir la canne en position verticale le plus longtemps possible.



Différence par rapport à la tâche précédente: il est maintenant nécessaire de prendre en compte des paramètres supplémentaires: angle d'inclinaison$$ et vitesse de la tige$(a)$$$ et prendre une décision sur la base de ces informations. La tâche semble plus compliquée car les combinaisons$(v)$



$$ beaucoup et vous ne pourrez pas essayer chacun d'eux plusieurs fois. Toute combinaison$(a;v)$



$$ est appelé unétat. Le nombre d'états peut être continu ou fini. Les algorithmes à états finis sont généralement plus faciles à implémenter. Il s'avère que l'état est un ensemble de certains paramètres du système. Il y a une hypothèse importante dans la théorie RL que cet ensemble de paramètres devrait décrire complètement l'état du système. Autrement dit, peu importe ce qui est arrivé au système lors des étapes précédentes, il importe uniquement de ce que nous observons à un moment donné. Ce que nous avons appris de l'exemple:$(a;v)$

• Lors du choix de l'action optimale, l'état du système doit être pris en compte. Le nombre d'états affecte la complexité de l'algorithme;
• Les paramètres qui décrivent l'état du système doivent donner des informations complètes sur le système à l'heure actuelle.

Exemple avancé

Regardons maintenant le jeu d'échecs.



Le nombre de positions possibles des pièces sur le plateau est exprimé en 52 chiffres. Et ce n'est pas la seule difficulté. La différence avec les deux tâches précédentes est que dans le cas des échecs, il est important de ne pas choisir l'action qui apportera le résultat maximal maintenant, mais celle qui mènera à la victoire dans le futur (après de nombreux pas en avant).



Ce que nous avons appris de l'exemple:

• Lorsque vous prenez une décision, tenez compte de l'effet à long terme et non du bénéfice immédiat.

Maintenant, à l'aide d'exemples, nous allons définir les termes généralement acceptés RL.

Terminologie de base de RL

Un agent est un sujet qui interagit avec l'environnement, effectue certaines actions, reçoit des commentaires de lui et s'en souvient.

• Par exemple, un moteur qui entraîne un chariot avec une tige; les bandits aux multiples armes sont des agents.

Environnement - l'endroit dans lequel l'agent existe et à partir duquel il reçoit des commentaires.



Le retour d'information que l'agent reçoit de l'environnement comporte généralement une certaine incertitude.

• Par exemple, lorsqu'un chariot avec une barre effectue un mouvement, le retour de l'action entreprise est le résultat de la chute ou non de la barre. Chariot et barre - moyen.

État - toute connaissance qui aide à prendre des décisions. Les États se réfèrent à l'environnement et le définissent de manière unique à chaque instant. En règle générale, ces états sont écrits sous la forme d'un ensemble de paramètres, de matrices ou de tenseurs d'ordre supérieur.

• Par exemple, la position actuelle des pièces sur un échiquier est un état.

Action - actions disponibles pour l'agent. En règle générale, le nombre d'actions dans l'espace est fini.

• Par exemple, les mouvements d'une barre vers la droite ou la gauche sont des actions.

Récompense - rétroaction instantanée qu'un agent reçoit pour ses actions. Autrement dit, c'est le résultat de l'action entreprise. La récompense est toujours un nombre.

• Par exemple, gagner un automate dans un problème de bandit multi-armé est une récompense.

Objectif - En règle générale, l'objectif de l'agent est de maximiser la récompense totale. En d'autres termes, le but ultime est de maximiser la récompense non pas à l'étape actuelle, mais à la récompense finale basée sur les résultats de la séquence d'étapes.

• Par exemple, notre objectif n'est pas de maintenir le pivot une fois, mais aussi longtemps que possible.

Stratégie - cartographie des états en actions. Par exemple, la probabilité de choisir l'action A dans l'état S.

Énoncé formel du problème

1. A chaque étape, l'environnement peut être dans l'état $$ .$s \in S$
2. À chaque étape, l'agent sélectionne une action dans l'ensemble d'actions disponibles $$ selon une stratégie π.$a \in A$
3. L'environnement dit à l'agent quelle est la récompense $$ il a reçu pour cela et dans quel état$r$$$ s'est alors avéré être.$s^* \in S$
4. L'agent ajuste la stratégie π.

Tout semble simple. Il y a une question non résolue - d'où vient la mystérieuse stratégie π , c'est-à-dire comment l'agent prend une décision à chaque étape.



Puisque dans la dernière partie de l'article une solution basée sur le Q-learning sera proposée, nous nous concentrerons délibérément uniquement sur les méthodes tabulaires.

Algorithmes tabulaires RL

Certaines des méthodes fondamentales de RL sont des méthodes tabulaires, utilisées pour des tâches dans lesquelles les ensembles d'états et d'actions sont finis. Une caractéristique de ces méthodes est l'utilisation de tableaux État-Action. Les lignes sont généralement des états différés, les colonnes sont des actions. Les cellules contiennent les valeurs de la fonction de valeur.







$$ - valeur de l'action$Q(s_i;a_j)$$$ est capable$a_j$$$ . En gros, c'est le bénéfice attendu que nous recevrons si nous choisissons une action$s_i$$$ , être dans un état$a_j$$$ . Dans la première étape, les valeurs$s_i$$$ initialisés, par exemple, avec des zéros. Pour l'exemple de labyrinthe, la table initiale État-Action pourrait ressembler à ceci: Ici, l'état est la position (cellule de labyrinthe) dans laquelle se trouve l'agent. Après avoir effectué une action, notre agent change d'état et reçoit une récompense. Dans cette tâche, la récompense peut être la suivante:$Q(s_i;a_j)$

• 1 si l'objet a trouvé un moyen de sortir du labyrinthe;
• 0 sinon.

De plus, une fois que l'agent a reçu des commentaires réels de l'environnement, la valeur $$ corrigé. Les algorithmes de correction sont différents, par exemple la méthode de Monte Carlo, SARSA, Q-learning. En savoir plus sur euxiciouici. Par exemple, les formules Q-learning et SARSA semblent très similaires à première vue: les deux méthodes utilisent la valeur attendue de l'action à l'étape suivante. Il est reçu très simplement: disons que l'agent est dans l'état$Q(s_i;a_j)$











$$ et exécute l'action$s_i$$$ . Ensuite, l'environnement informe l'agent qu'à la suite de son action, il reçoit une récompense$a_j$$$ et nouvel état$r_i$$$ . À l'aide du tableau Status-Action, vous pouvez trouver la ligne avec l'état$s_k$$$ et déterminez quelle valeur telle ou telle action lui apportera. La différence est que dans Q-learning$s_k$



$$ est toujours la valeur maximale dans un nouvel état. Alors que la méthode SARSA suppose que l'agent simule le choix de l'action dans l'état$Q(s_k;a)$$$ , par exemple, selon la stratégie ε-gourmande ou UCB. Lors de l'utilisation d'une stratégie gourmande, les méthodes sont équivalentes. L'inconvénient de ces algorithmes est la nécessité de stocker la table State-Action. Certaines tâches peuvent avoir un grand espace d'états et d'actions, ce qui rend impossible l'utilisation des méthodes de table classiques. Dans de tels cas, des approches sont utilisées pour approximer les valeurs$s_k$



$$ utilisant des réseaux de neurones. La programmation dynamique peut être une alternative aux méthodes de table. Nous ne nous attarderons pas sur ces algorithmes, mais nous vous recommandons de lire le livreReinforcement Learning de R. S. Sutton et E. G. Barto. C'est là que nous terminons la théorie, puis parlons de la façon dont l'apprentissage par renforcement peut être utilisé dans une tâche appliquée.$Q(s_i;a_j)$

Trouver la meilleure stratégie d'incitation client à l'aide de l'apprentissage par renforcement

Énoncé du problème en termes commerciaux

Contraintes sous lesquelles notre approche a été développée:

• La solution doit être flexible face aux limites de la politique de communication avec les clients;
• La fonction à optimiser doit être guidée par des objectifs commerciaux et peut être plus complexe qu'une simple réponse;
• ;
• ( , , , );
• .

RL

Ainsi,

Agent and Environment est un système de programme de fidélisation qui envoie au client des communications avec des propositions marketing et au client lui-même.



State est l'état du client, qui est caractérisé par les attributs du client.



Les actions sont des offres marketing (par exemple, «obtenez X% de réduction sur l'achat Y»). On suppose que la liste des propositions est fixe et finie.



La récompense est une fonction du changement de comportement des clients (par exemple, l'augmentation des revenus ou la réponse à une campagne ciblée).

Approche de la solution

Examinons maintenant les solutions possibles à l'aide des méthodes tabulaires d'apprentissage par renforcement.



L'algorithme de solution utilisant Q-Learning ou Sarsa peut être le suivant:

1. Définition des états des clients

L'état du client peut être spécifié à l'aide des attributs du client. La plupart de ces attributs sont des nombres réels, donc avant d'utiliser des méthodes tabulaires, les attributs doivent être discrétisés pour obtenir un ensemble fini d'états.



Dans notre solution, nous avons utilisé les clusters obtenus à la suite de la mise en cluster de la base de clients en fonction des attributs sélectionnés en tant qu'états du client. Le nombre de clusters affecte la rapidité d'apprentissage de l'algorithme. Les recommandations générales sont les suivantes:

• afin de pouvoir gérer le flux de clients de cluster en cluster, il est nécessaire que la liste des attributs inclue ceux qui peuvent être modifiés sous l'influence de la présence et de la réaction aux offres marketing;
• au sein de chaque cluster, les clients doivent avoir un comportement homogène;
• la mise à jour des attributs devrait être possible sur une base régulière;
• dans chaque cluster, le nombre de clients doit être supérieur au minimum établi (le minimum peut être dû, par exemple, à des restrictions sur le nombre minimum de clients pour que les résultats soient significatifs)

2. Choix de la récompense

Le choix de la récompense est l'étape la plus importante du développement du système. Pour cette tâche, la récompense peut caractériser le succès de la campagne. Par exemple, les options possibles sont:

• Conversion par offre;
• Augmentation en réponse à une offre;
• Revenus spécifiques par participant à la campagne;
• Bénéfice spécifique prenant en compte les coûts;
• ...

Revenant au problème de l'augmentation de la fidélité des clients, la métrique cible peut être la LTV ou la métrique de la proximité du client avec le segment fidèle.



Dans tous les cas, le choix de la récompense doit être cohérent avec les objectifs du marketing.



PS Certaines des options de rémunération proposées sont calculées agrégées par un groupe de clients (par exemple, l'augmentation de la réponse aux offres est la réponse du groupe cible moins la réponse du groupe témoin). Dans ce cas, il serait plus correct de dire que nous choisissons une action non pas pour un client, mais pour un cluster de clients (qui sont dans le même état), au sein duquel la récompense est calculée.

3. Choix des actions possibles

Les actions sont des propositions marketing qui peuvent être envoyées au client. Lors du choix des campagnes marketing à utiliser dans le système, gardez à l'esprit:

• la proposition marketing ne doit pas changer du lancement au lancement;
• le choix du nombre de phrases influe sur le taux d'apprentissage de l'algorithme;
• un scénario doit être envisagé lorsqu'aucune des campagnes n'est adaptée à l'état (par exemple, toutes les variantes d'offre génèrent des revenus négatifs). Dans ce cas, l'une des actions peut être "default-campaign". Cela peut être soit une liste de diffusion de base qui peut être envoyée à tous les clients, soit l'absence d'offre (c'est-à-dire qu'il est possible qu'il soit plus rentable de ne rien envoyer au client).

4. Conception d'un algorithme de sélection soumis à des contraintes

Lors de la conception d'un algorithme, il convient de considérer:

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

5. Initialisation du tableau État-Action

Au départ, le tableau État-Action ressemble à ceci:







Un lancement supplémentaire du système est possible en l'absence de lancements historiques pour les campagnes sélectionnées, ce qui est un avantage important du concept.



Cependant, s'il existe un certain historique, il peut être utilisé, c'est-à-dire qu'un pré-apprentissage rétrospectif de la table État-Action est possible:

1. Initialisez la table State-Action avec des zéros
2. Prenons le lancement historique de la campagne X. Calculez les états des clients participant à la campagne au moment du lancement et à la fin de la campagne. Calculez la récompense reçue dans chaque état.
3. Selon la formule Q-learning ou SARSA, recalculez le tableau État-Action en tenant compte des valeurs attendues des valeurs de campagne au prochain lancement.

6. Entraînement de l'algorithme sur les lancements pilotes

L'objectif de notre système est d'apprendre à sélectionner les meilleures offres pour l'ensemble de la clientèle. Cependant, au stade du test du système, nous recommandons de réaliser des lancements pilotes sur un petit échantillon représentatif de clients.



Ce à quoi vous devez faire attention à ce stade:

1. Changements dans les valeurs de la table État-Action: à mesure que l’historique s’accumule, les valeurs de la table État-Action devraient devenir de plus en plus stables;
2. Dynamique positive de l'effet des campagnes: du lancement au lancement, l'efficacité de chaque proposition marketing doit croître.

Dès que (1) et (2) atteignent un plateau, nous pouvons supposer que le système est prêt à être déployé auprès de l'ensemble de la clientèle.

7. Système de déroulement

Avant de commencer à déployer le système, il est conseillé d'analyser la durabilité des résultats de la campagne dans le contexte de chaque état client. Comme le montre la pratique, malgré la stabilité générale, dans certains états, il peut y avoir soit un historique insuffisant, soit les états eux-mêmes peuvent être instables dans le temps => nous avons un résultat instable.



Ainsi, nous avons développé les recommandations suivantes pour le roulage:

• Exclure les conditions instables du roulement;
• Utiliser une stratégie ε-gourmande afin que le système puisse s'adapter indépendamment aux changements de comportement de la clientèle;
• Continuez à surveiller régulièrement les performances du système.

Ainsi, dans cet article, nous avons essayé de décrire le concept de haut niveau de notre approche. Les résultats du fonctionnement du système basé sur l'algorithme proposé peuvent être trouvés ici .

Conclusion

Nous avons décrit l'utilisation de RL pour résoudre le problème de la sélection de la chaîne optimale d'actions. Cependant, il convient de mentionner qu'un concept similaire peut être appliqué à d'autres tâches de marketing, par exemple, les systèmes de recommandation, le choix du canal / moment de communication optimal ou la sélection d'une bannière personnelle sur le site. Malgré le fait que l'apprentissage par renforcement soit moins populaire que les méthodes traditionnelles de ML, nous voulions faire comprendre au lecteur que RL peut être une excellente solution s'il est nécessaire de maintenir un recyclage automatique du système ou de former complètement le système à partir de zéro.



L'équipe GlowByte tient à remercier X5 Retail Group pour l'opportunité de mettre en œuvre ce cas.