Two guys holding beers

Le jeu de la bière est une simulation bien connue de l’effet de fouet. Elle consiste à construire un environnement multi-agents qui représente le réseau de la chaîne d’approvisionnement : client, détaillant, distributeur et usine. L’idée est alors de minimiser le coût de l’ensemble du réseau sachant que les agents ne communiquent pas et ne peuvent qu’agir selon leur politique. Chaque agent commande des quantités pour répondre à la demande.

Notre projet est de construire un algorithme d’apprentissage machine basé sur des Q-Networks profonds pour guider la décision de l’agent à chaque épisode.

Introduction

Le jeu de la bière est une simulation d’un réseau de chaîne d’approvisionnement composé de quatre agents : usine, distributeur, grossiste et détaillant. Le détaillant reçoit une demande stochastique d’une cinquième entité appelée le client et l’usine a une source d’approvisionnement illimitée.

A chaque étape, chaque agent reçoit un ordre de l’agent juste avant lui dans la chaîne et envoie les ordres à l’agent juste à côté de lui. Les délais de transport d’aval en amont et d’amont en aval sont fixes et on suppose qu’il n’y a pas de communication entre les agents.
Le jeu de la bière est un problème décentralisé, à apprenants indépendants, multi-agents, coopératif. Malgré l’absence de communication, l’objectif est de minimiser le coût total de la chaîne :

\sum\limits_{t=1}^{T}\sum\limits_{i=1}^{4}c_{h}^{i} \max(0,IL_{t}^{i}) + c_{p}^{i}\max(0,-IL_{t}^{i})

où i=1,…,4 indexe les agents et t=1,…,T indexe les épisodes, c_{h}^{i} et c_{p}^{i} sont respectivement le coût de détention et le coût de rupture de stock de l’agent i.

Cette fonction de coût nous permet d’inclure le coût de détention uniquement lorsque le niveau de stock de l’agent i, IL_{t}^{I}, est positif et vice versa.

L’algorithme

Pour résoudre le problème de la bière, nous avons modélisé chaque agent comme un réseau DQN. Dans cette section, nous donnons les spécificités de l’algorithme et du mécanisme d’apprentissage utilisé pour former les agents : Tout d’abord, nous décrivons le fonctionnement du DQN, les détails de ses interactions avec l’environnement (Etats, Actions et récompenses) et le processus de formation (Experience Replay, Exploration – Exploitation, Training delay, Transfer Learning).

Le Deep Q-Network

Le Deep Q-Network est une application des réseaux neuronaux à Q-Learning. Le but de Q-Learning est d’apprendre la fonction Etat-Action :

Q(s,a) = r(s,a) + \gamma \sum p(y|s,a) V(y)

Ce qui nous permet d’apprendre la politique optimale \pi(s) = argmax(Q(s,a)).

Le DQN vise à apprendre cette fonction à travers un réseau neuronal avec rétropropropagation. Cependant, la perte utilisée est différente d’un problème de régression classique. Nous utilisons plutôt la différence temporelle couplée à la perte de Huber, qui provient de l’équation de Bellman :

Q^{\pi}(s, a) = r(s ,a) + \gamma Q^{\pi}(s', \pi(s'))

La différence temporelle est : \delta = Q(s, a) - (r(s,a) + \gamma \max_a Q(s', a)) . Cette erreur est transmise au réseau par la perte de Huber.

L’architecture utilisée pour le réseau neuronal dépend de la nature du problème. Pour notre problème, nous avons choisi d’implémenter un réseau entièrement connecté avec deux couches cachées et une couche finale égale au nombre de couches possibles. Cependant, d’autres architectures peuvent s’appliquer à ce problème (RNNs par exemple).

Pour augmenter la stabilité, le réseau utilisé pour calculer le deuxième terme de la différence temporelle n’est pas le réseau réel, mais une version plus ancienne (anciens poids).

Les variables d’état

Les variables d’état transmises au réseau sont les informations des derniers m tours. Ces variables incluent le stock possédé par l’agent, l’expédition reçue pendant le tour en cours, les commandes restantes des tours précédents, la nouvelle commande reçue pendant le tour en cours et les actions précédentes de l’agent.

Le choix de m est important car il y a un délai entre la passation d’une commande et sa réception. Dans ce cas, les récompenses sont également retardées et l’effet d’une action n’est pas immédiat. la valeur de m doit être suffisamment grande pour que l’agent puisse observer l’effet de ses actions sur la récompense retardée. nous avons choisi une valeur supérieure au nombre d’agents multiplié par le nombre de semaines de retard.

Les récompenses

La récompense obtenue par un agent à chaque tour est moins le coût encouru pendant ce tour. Ce coût est calculé comme la somme des coûts de stock et des coûts des commandes en attente :

c_{h}^{i} \max(0,IL_{t}^{i}) + c_{p}^{i}\max(0,-IL_{t}^{i})

Au début de la formation, les récompenses peuvent être importantes en raison de l’exploration de l’espace d’action, ce qui peut conduire à des gradients importants. Pour éviter cela, nous utilisons des récompenses par écrêtage, ce qui nous permet d’augmenter la stabilité de l’agent formé. La valeur maximale autorisée des récompenses est déterminée à partir de leur répartition.

Exploration-Exploitation

Pour assurer une bonne exploration de l’espace d’action, nous mettons en œuvre une probabilité d’exploration à chaque tour, où l’agent va effectuer une action aléatoire au lieu d’une action basée sur le résultat du DQN. La probabilité d’exploration diminue de façon exponentielle avec le nombre d’épisodes pour assurer un bon compromis entre exploration et exploitation pendant la formation.

Revivez l’expérience

La relecture de l’expérience stocke les transitions observées par chaque agent. Cela nous permet de réutiliser les transitions pendant le processus de formation en les stockant dans une « mémoire ». A chaque époque, un lot de taille fixe est prélevé de la mémoire et utilisé pour former l’agent. Il a été démontré que cela a également un effet stabilisateur sur l’agent, puisque les transitions ne sont pas corrélées en raison de l’échantillonnage aléatoire.

Pour notre problème, nous avons utilisé un objet mémoire différent par agent. A chaque tour, l’agent stocke l’état précédent, l’action effectuée, la récompense obtenue et le nouvel état.

Délai de formation

Pour améliorer la stabilité de l’algorithme, les agents ne sont pas formés immédiatement, mais l’entraînement de chaque agent commence après un nombre prédéterminé d’épisodes. La première formation à commencer est celle du détaillant (au bas de la chaîne d’approvisionnement) et la dernière formation à commencer est celle de l’usine. Après un nombre fixe d’épisodes, l’entraînement d’un agent est arrêté. Plus l’agent est haut dans la chaîne d’approvisionnement, plus il a besoin d’époques de formation. L’arrêt permet également aux autres agents de s’adapter aux actions.

Le délai entre la formation de l’agent et le nombre d’époques de formation est déterminé empiriquement, en fonction de la stabilité observée de l’agent entraîné seul dans le même contexte.

LEAVE A REPLY

Please enter your comment!
Please enter your name here