La programmation dynamique expliquée

La programmation dynamique – le standard d'excellence pour tes objectifs financiers

À première vue, la programmation dynamique (PD) peut sembler être un terme informatique qui n'a pas grand-chose à voir avec la finance ou l'investissement. Mais en réalité, c'est un cadre très puissant pour prendre des décisions séquentielles optimales dans l'incertitude. Que tu navigues sur un échiquier, geres une chaîne d'approvisionnement ou développes un portefeuille au fil du temps, la PD offre un moyen systématique de décomposer des problèmes complexes en éléments gérables.

Dans cet article, nous t'expliquons la PD en langage simple à l'aide d'un jeu de grille basique, nous passons en revue un exemple concret avec un graphique, puis nous montrons comment cette même logique alimente l'approche de GBI en matière d'allocation d'actifs.

La programmation dynamique – Qu'est-ce que c'est ?

En termes très simples, la programmation dynamique est une méthode de résolution de problèmes complexes consistant à les décomposer en sous-problèmes plus petits, à résoudre chacun d'eux une seule fois et à réutiliser ces solutions pour construire la réponse finale. C'est à la fois un cadre mathématique pour l'optimisation et une approche algorithmique correspondante.

Les deux (la théorie mathématique et la partie algorithmique) sont étroitement liées. Pour certains types de problèmes, nous pouvons garantir qu'une stratégie optimale existe et que la programmation dynamique peut la trouver efficacement.

Le principe de l'induction inversée

L'idée clé de la programmation dynamique est de résoudre les problèmes à l'envers. En partant de l'étape finale, nous déterminons la meilleure décision pour un résultat souhaité, puis nous avançons pas à pas vers le présent, en identifiant la meilleure décision à chaque moment précis. Cela évite d'avoir à deviner l'avenir – à la place, nous laissons l'avenir nous dire ce que le présent doit faire.

L'exemple le plus courant (le jeu de grille)

Jouons à un jeu.

Imagine que tu te trouves sur une grille bidimensionnelle (comme un échiquier), en partant de la colonne la plus à gauche dans n'importe quelle cellule, et en te déplaçant de gauche à droite.

À chaque moment, tu peux choisir une action parmi un ensemble d'options prédéfinies. En fonction de ta décision, tu te déplaces d'une colonne vers la droite, atterrissant dans l'une des cellules de cette colonne avec certaines probabilités. Certaines actions/décisions auront plus de chances de t'amener dans une cellule spécifique plutôt qu'une autre.

Tu continues ce processus jusqu'à ce que tu atteignes la colonne la plus à droite. Ta position finale te donne un score. Comment devrais-tu agir à chaque moment pour maximiser ton score final ? Une stratégie optimale existe-t-elle ?

C'est exactement là que la programmation dynamique intervient.

Voyons comment l'algorithme fonctionnerait.

Commence à la colonne finale (colonne 8). Note que chaque cellule y a un score final connu (dans notre exemple, nous supposons que le haut représente le score le plus élevé).

► Reviens à la colonne 7. Pour chaque cellule (par exemple D7) et pour chaque action possible, calcule un score attendu comme la somme du score final de la cellule suivante multiplié par la probabilité d'y atterrir. Choisis l'action qui maximise cette attente.

► Enregistre ce score attendu maximum pour chaque cellule de la colonne 7. C'est le score pour le fait de se trouver dans cette cellule à ce moment-là, et l'action qui nous a donné un tel score (dans ce cas, l'action 'défensive'), est l'action optimale depuis cette cellule à ce moment-là.

► Reviens à la colonne 6 et fais de même, mais en utilisant cette fois les scores de la colonne 7.

► Répète l'opération tout au long du chemin du retour jusqu'à la première colonne.

Le résultat is une décision optimale pour chaque état possible à chaque moment précis.

Relier la terminologie à la grille

Pour relier cette intuition au cadre formel, nous pouvons introduire une terminologie standard :

► Les cellules de l'échiquier sont appelées des états (states)

► L'ensemble des décisions possibles est appelé l'ensemble de contrôle (control set)

► Les probabilités de passer d'une cellule à une autre définissent la loi de transition (transition law)

► Le score final est appelé la fonction de récompense (reward function)

Sous certaines hypothèses, nous pouvons prouver qu'une stratégie optimale existe bel et bien – et qu'elle peut être trouvée à l'aide d'un algorithme récursif.

La programmation dynamique et GBI

Tu te souviens de l'échiquier ?

Le déplacement de gauche à droite représente le passage du temps, et les cellules de chaque rangée représentent ton niveau de richesse à chaque moment précis. À chaque étape, les actions qui s'offrent à toi correspondent à différents portefeuilles que tu peux choisir. Chaque portefeuille te donne des probabilités différentes d'augmenter ou de diminuer ta richesse au cours de la période suivante. Chaque portefeuille te donnera des chances différentes de gagner plus ou moins au cours de la période suivante.

Enfin, la fonction de récompense peut être la richesse finale elle-même, ou simplement un résultat binaire (0 ou 1) selon que tu as atteint ou non un seuil donné.

Cela conduit à une question très concrète :

Quel portefeuille devrais-tu choisir à chaque moment précis, compte tenu de ta richesse actuelle, pour maximiser ton résultat final ?

C'est exactement le problème que GBI cherche à résoudre pour toi ! La bonne nouvelle est que ce problème peut être résolu grâce à la programmation dynamique. Sous nos hypothèses de modélisation, une stratégie optimale existe – et notre cadre est conçu pour la trouver pour toi.

Pour résumer

La programmation dynamique est plus qu'un concept académique – c'est un outil pratique pour prendre les meilleures décisions possibles au fil du temps lorsque l'avenir est incertain. En décomposant un problème complexe et pluripériodique en étapes plus petites et rétrospectives, la PD garantit une stratégie optimale sans qu'il soit nécessaire de deviner ou de se fier à son intuition.

Dans le jeu de grille, cela signifie savoir exactement quelle action entreprendre depuis n'importe quelle cellule à tout moment. En finance, cela signifie savoir exactement quel portefeuille choisir compte tenu de ta richesse actuelle, de ta tolérance au risque et de ton horizon d'investissement.

GBI s'appuie sur ce fondement mathématique exact, apportant la rigueur de la programmation dynamique à l'allocation d'actifs réelle.

Dans le prochain article, nous explorerons la structure mathématique derrière cette approche et verrons comment l'algorithme fonctionne en pratique.