Optimal strategies in Markov decision processes with finitely additive evaluations

Cet article démontre que, contrairement au cas où la charge diffuse satisfait le principe de la valeur temporelle de l'argent, il existe des processus de décision markoviens à horizon infini et espaces finis qui ne possèdent aucune stratégie optimale, ni pure ni randomisée, lorsque la charge d'agrégation est choisie de manière adéquate.

L'essentiel

Voici une explication simple de ce papier de recherche, imaginée comme une histoire de décision et de temps.

Le Titre : Quand le futur n'a pas de poids fixe

Imaginez que vous êtes un chef d'entreprise qui doit prendre des décisions chaque jour, éternellement. Chaque jour, vous choisissez une action qui vous rapporte un petit gain (ou une perte). Le but est de maximiser votre richesse totale.

Dans la vie réelle, on utilise souvent deux méthodes pour calculer ce gain total :

1. L'approche classique : On additionne tout, mais on donne moins de valeur aux gains lointains (comme un intérêt bancaire).
2. L'approche moyenne : On regarde ce qui se passe sur le long terme, en faisant la moyenne de tous les jours, peu importe quand ils arrivent.

Les mathématiciens de ce papier (Flesch, Predtetchinski, Sudderth et Venel) s'intéressent à un troisième cas, beaucoup plus bizarre et abstrait : comment évaluer une vie entière de décisions si l'on utilise une règle de calcul très étrange, appelée "charge diffuse" ?

L'Analogie du "Juge Fantôme"

Pour comprendre leur travail, imaginez que vous avez un Juge Fantôme qui doit noter votre performance sur une échelle infinie de jours.

• Le problème habituel : Ce Juge a des règles claires. Soit il dit "Le jour 1 compte beaucoup, le jour 1000 compte un peu" (c'est l'approche classique). Soit il dit "Je ne regarde que la moyenne de vos 1000 derniers jours" (c'est l'approche moyenne). Dans ces cas, il existe toujours une stratégie parfaite (une recette magique) pour gagner le maximum de points.

• Le problème de ce papier : Les auteurs demandent : "Et si le Juge Fantôme utilisait une règle encore plus étrange ?"
  Imaginez un Juge qui dit : "Je ne donne de poids à aucun jour précis. Le jour 1 vaut 0, le jour 2 vaut 0, le jour 1000 vaut 0... et pourtant, quand je regarde l'ensemble de votre vie, je dois vous donner une note entre 0 et 1."
  C'est ce qu'ils appellent une charge diffuse. C'est comme si le Juge regardait l'océan des jours, mais ne pouvait jamais se concentrer sur une goutte d'eau spécifique.

La Grande Question

Les chercheurs savent déjà que si le Juge respecte une règle de base (le "principe de la valeur temporelle de l'argent", c'est-à-dire qu'il préfère un gain maintenant à un gain plus tard), alors il existe toujours une stratégie parfaite. Vous pouvez trouver une recette infaillible.

Mais la question est : Que se passe-t-il si le Juge ne respecte pas cette règle ? Existe-t-il encore une stratégie parfaite, même avec ces règles bizarres ?

La Réponse : "Non, c'est impossible !"

C'est la grande découverte de ce papier. Les auteurs ont construit un piège mathématique (un exemple concret appelé "le jeu pair ou impair") pour prouver que la réponse est NON.

L'Histoire du Jeu Pair ou Impair

Imaginez un jeu où vous êtes dans une pièce avec deux portes :

• Porte A (T) : Vous gagnez 1 euro maintenant, mais 0 euro demain.
• Porte B (B) : Vous gagnez 0 euro maintenant, mais 1 euro demain.
• Ensuite, le jeu recommence.

Vous devez choisir une porte chaque jour.

• Si vous choisissez A souvent, vous gagnez beaucoup les jours impairs (1, 3, 5...) mais rien les jours pairs.
• Si vous choisissez B souvent, c'est l'inverse.

Le Juge Fantôme de ce papier est un monstre mathématique. Il est composé de deux esprits :

1. Esprit 1 : Il ne regarde que les jours impairs. Il veut que vous choisissiez A le plus souvent possible.
2. Esprit 2 : Il ne regarde que les jours pairs, mais d'une manière très subtile. Il veut que vous choisissiez B assez souvent pour qu'il ait l'impression que vous avez gagné, même si vous ne gagnez pas tous les jours pairs.

Le Dilemme :

• Si vous jouez A tout le temps pour plaire à l'Esprit 1, vous gagnez 100% sur les jours impairs, mais l'Esprit 2 (qui regarde les jours pairs) vous donne un score très bas.
• Si vous jouez B tout le temps pour plaire à l'Esprit 2, vous perdez sur les jours impairs.
• Si vous essayez de faire un compromis (parfois A, parfois B), vous ne satisfaites parfaitement ni l'un ni l'autre.

Le Résultat Magique :
Les auteurs prouvent mathématiquement que, dans ce jeu précis avec ce Juge Fantôme, il n'existe aucune stratégie parfaite.

• Vous pouvez essayer de jouer "presque parfaitement" (par exemple, 99% de A), mais vous ne gagnerez jamais le score maximum théorique.
• Vous pouvez essayer de changer de stratégie chaque jour, mais le Juge est si bizarre qu'il n'y a aucune combinaison de choix (ni pure, ni aléatoire) qui vous permette d'atteindre le sommet.

C'est comme si vous couriez après une ligne d'arrivée qui recule exactement à la même vitesse que vous avancez. Vous pouvez vous approcher infiniment près, mais vous n'arriverez jamais à la toucher.

Pourquoi est-ce important ?

Ce papier est une leçon de prudence pour les mathématiciens et les économistes.

1. La réalité est complexe : Parfois, dans des systèmes très complexes (comme l'économie ou l'intelligence artificielle), on pense qu'il existe toujours une "meilleure solution" possible. Ce papier dit : "Attention, pas toujours !".
2. Les règles comptent : Si vous changez la façon dont vous mesurez le succès (la "charge"), vous pouvez passer d'un monde où tout est optimisable à un monde où l'optimisation parfaite est impossible.
3. L'existence n'est pas garantie : Même avec des règles simples (comme ce jeu de portes), si la façon de compter les points est trop étrange, le "meilleur joueur" n'existe tout simplement pas.

En résumé

Ce papier nous dit que dans un monde infini, si vous utilisez une règle de calcul très particulière pour évaluer vos décisions, il est possible qu'aucune stratégie ne soit la meilleure. Il n'y a pas de "solution miracle". C'est une preuve mathématique élégante que parfois, dans la vie (et en mathématiques), on peut courir après l'excellence sans jamais l'atteindre.

Résumé technique

1. Problématique et Contexte

L'article étudie les Processus de Décision Markoviens (MDP) à horizon infini avec des espaces d'états et d'actions finis. La particularité fondamentale de ce travail réside dans la manière dont le décideur évalue les stratégies.

• Évaluation standard : Habituellement, les MDP utilisent des sommes discountées ou des moyennes à long terme (limites de fréquences).
• Évaluation proposée : Ici, l'évaluation d'une stratégie est obtenue en agrégeant le flux infini des récompenses espérées par étape à l'aide d'une charge diffuse (une mesure de probabilité finiment additive sur l'ensemble des étapes $\mathbb{N}$, notée $\mu$).
  • Une charge $\mu$ est dite diffuse si $\mu(\{n\}) = 0$ pour tout $n \in \mathbb{N}$ (aucune étape individuelle n'a de poids).
  • L'espérance de gain (payoff) d'une stratégie $\sigma$ est définie par l'intégrale : $u_\mu(\sigma) = \int_{\mathbb{N}} \mathbb{E}_\sigma[r_t] \, \mu(dt)$.

La question centrale :
Des résultats antérieurs (Neyman [2023]) ont montré que si la charge $\mu$ satisfait le principe de la valeur temporelle de l'argent (ce qui inclut les charges patientes et les charges de fréquence), alors une stratégie pure et stationnaire optimale existe toujours.
Cependant, la question ouverte était la suivante : Une stratégie optimale (pure ou randomisée) existe-t-elle pour toute charge diffuse $\mu$, même si elle ne satisfait pas ce principe ?

2. Méthodologie

Les auteurs adoptent une approche combinant la théorie des jeux, l'analyse fonctionnelle (théorie des charges) et la théorie des MDP.

1. Cadre théorique :

   • Utilisation de l'axiome de choix (ZFC) pour garantir l'existence de charges sur l'ensemble des parties de $\mathbb{N}$.
   • Définition de l'espace des charges $\Delta_f$ muni de la topologie de la convergence ponctuelle. Cet espace est compact et de Hausdorff, mais non métrisable.
   • Distinction entre les charges de fréquence (basées sur les limites de fréquences asymptotiques) et les charges plus générales qui ne satisfont pas nécessairement le principe de la valeur temporelle de l'argent.

2. Construction du Contre-exemple (Le cœur de la preuve) :
   Pour répondre négativement à la question de l'existence, les auteurs construisent un MDP spécifique et une charge $\mu$ "délicatement construite".

   • Le MDP "Pair ou Impair" (Even-or-Odd) :
     • États : $S = \{1, 2, 3\}$. État initial : 1.
     • Actions : En état 1, choix entre $T$ (Top) et $B$ (Bottom). États 2 et 3 n'ont qu'une seule action.
     • Dynamique :
       • Si $T$ en état 1 : Récompense 1, transition vers état 2.
       • Si $B$ en état 1 : Récompense 0, transition vers état 3.
       • États 2 et 3 : Récompense respective 0 et 1, transition déterministe vers l'état 1.
     • Structure temporelle : Les étapes impaires sont des moments de décision. Choisir $T$ donne 1 maintenant et 0 ensuite ; choisir $B$ donne 0 maintenant et 1 ensuite.
   • La Charge $\mu$ :
     • Elle est définie comme une combinaison convexe : $\mu = \frac{1}{2}\mu_0 + \frac{1}{2}\mu^*$.
     • $\mu_0$ est concentrée sur les étapes impaires (basée sur une charge de fréquence $\phi$).
     • $\mu^*$ est un point d'accumulation (dans la topologie ponctuelle) d'une suite de charges $\mu_n$ concentrées sur des ensembles d'entiers de plus en plus "rares" (multiples de puissances de 2), ce qui force $\mu^*$ à être concentrée sur les étapes paires d'une manière non triviale.
     • Cette construction crée un conflit fondamental : pour optimiser $\mu_0$, il faut jouer $T$ souvent ; pour optimiser $\mu^*$, il faut jouer $B$ avec une certaine fréquence, mais les deux objectifs sont incompatibles à l'optimum strict.

3. Résultats Principaux

Le résultat central de l'article est le Théorème 3, qui établit l'absence d'optimalité.

• Théorème 3 (Non-existence) : Dans le MDP "Pair ou Impair" avec la charge $\mu$ construite ci-dessus, il n'existe aucune stratégie optimale, ni pure ni randomisée.

  • La valeur du jeu est $v_\mu = 1$.
  • Cependant, pour toute stratégie $\sigma$, le payoff strictement inférieur à 1 : $u_\mu(\sigma) < 1$.

• Preuve esquissée :

  1. On montre qu'on peut s'approcher arbitrairement de 1 en jouant une stratégie séquentielle $\sigma_n$ qui joue $B$ sur un sous-ensemble spécifique d'étapes et $T$ ailleurs.
  2. On montre par l'absurde qu'aucune stratégie ne peut atteindre 1. Si une stratégie atteignait 1, elle devrait donner une récompense espérée $> 1/2$ presque partout selon $\mu$. Or, la structure du MDP impose que si la récompense est élevée à l'étape $t$, elle doit être faible à l'étape $t+1$ (et vice-versa). La structure de la charge $\mu^*$ (point d'accumulation) force une contradiction : toute stratégie qui satisfait la condition pour $\mu_0$ échoue pour $\mu^*$, et inversement.

• Résultats secondaires (Remarques conclusives) :

  • Exemple 4 : Même dans un MDP où une stratégie pure optimale existe, il est possible qu'aucune stratégie stationnaire ne soit optimale si la charge ne satisfait pas le principe de la valeur temporelle de l'argent.
  • Exemple 5 : L'absence d'optimalité persiste même pour des charges non diffuses (combinaison de mesures dénombrablement additives et diffuses), illustrant que le problème n'est pas uniquement lié à la nature "diffuse" de la mesure, mais à la structure de l'agrégation.

4. Contributions Clés

1. Réponse négative à une question ouverte : L'article réfute l'hypothèse selon laquelle l'existence d'une stratégie optimale est garantie dans tous les MDP finis avec des charges diffuses.
2. Construction mathématique ingénieuse : La définition de la charge $\mu^*$ via un point d'accumulation dans la topologie de convergence ponctuelle permet de créer une mesure qui "détecte" des motifs temporels que les stratégies stationnaires ou même les stratégies adaptatives simples ne peuvent pas satisfaire simultanément.
3. Distinction entre robustesse et optimalité : Le travail met en lumière que la robustesse (existence d'une stratégie optimale pour une classe de charges, comme démontré par Neyman) ne se généralise pas à l'unicité de la charge. Pour une charge arbitraire, l'optimalité peut échouer.

5. Signification et Implications

• Théorique : Ce résultat est fondamental pour la théorie des MDP à horizon infini. Il montre que l'hypothèse de la "valeur temporelle de l'argent" (ou de la patientesse) n'est pas seulement une condition technique pour la simplicité des stratégies, mais une condition nécessaire pour garantir l'existence même d'une solution optimale dans le cadre des mesures finiment additives.
• Pratique : Dans les modèles économiques ou de contrôle où les agents utilisent des critères d'évaluation non standards (par exemple, des critères basés sur des limites de Banach ou des charges non invariantes par translation), les décideurs ne doivent pas présumer qu'une stratégie optimale existe. Ils pourraient se trouver dans des situations où toute amélioration marginale est possible, mais où l'optimum global est inaccessible.
• Limites des stratégies stationnaires : L'article renforce l'idée que les stratégies stationnaires (qui ne dépendent que de l'état courant) sont insuffisantes pour certains critères d'évaluation, même lorsque l'espace d'états est fini.

En résumé, cet article démontre que l'agrégation finiment additive, bien que puissante pour modéliser l'indifférence au temps, introduit des pathologies mathématiques qui peuvent rendre l'optimisation impossible dans des systèmes dynamiques déterministes simples.