A Harmonic Mean Formulation of Average Reward Reinforcement Learning in SMDPs

Résumé Technique : Une Formulation de la Moyenne Harmonique pour l'Apprentissage par Renforcement à Récompense Moyenne dans les Processus Décisionnels de Markov Semi-Markoviens

1. Énoncé du Problème

L'article aborde le défi de l'optimisation de la récompense moyenne non escomptée dans les Processus Décisionnels de Markov Semi-Markoviens (SMDP) à horizon infini. Contrairement aux Processus Décisionnels de Markov (MDP) standards où les actions prennent une unité de temps fixe, les SMDP impliquent des actions qui génèrent stochastiquement à la fois des récompenses et des durées variables (temps de séjour). L'objectif est de maximiser le taux de récompense moyen (récompense par unité de temps), plutôt que la récompense totale accumulée.

Les algorithmes sans modèle existants pour ce cadre, spécifiquement SMART et Relaxed-SMART, souffrent de limitations critiques lorsque les récompenses et les durées sont non stationnaires ou dépendantes :

• SMART repose sur la moyenne d'échantillon à long terme (récompense totale divisée par le temps total). Cette approche est fragile ; elle suppose la stationnarité et peut être dominée par des valeurs aberrantes ou échouer à s'adapter aux changements de régime dans des environnements non stationnaires.
• Relaxed-SMART tente de gérer la non-stationnarité en utilisant des Moyennes Mobiles Exponentielles (MME) pour les récompenses et les durées, puis en prenant leur ratio. Cependant, cette méthode approxime le taux moyen comme le ratio de moyennes arithmétiques. L'article démontre que cette approximation n'est mathématiquement correcte que si les récompenses et les durées sont indépendantes. Lorsqu'elles sont corrélées (liées de manière non linéaire), le ratio des moyennes produit une estimation incorrecte du véritable taux moyen.

2. Méthodologie

Les auteurs proposent une approche novatrice basée sur la Moyenne Harmonique, qui est l'opérateur théoriquement correct pour moyenner des taux (par exemple, vitesse = distance/temps).

La Limitation de la Moyenne Harmonique :
Bien que la moyenne harmonique soit l'agrégation correcte pour les taux, sa définition standard est mal adaptée à l'Apprentissage par Renforcement (RL) général car :

1. Elle est indéfinie pour les valeurs nulles (division par zéro).
2. Elle perd la propriété d'"internalité" (la moyenne tombant entre le minimum et le maximum) lorsque les valeurs ont des signes mixtes (récompenses positives et négatives).

L'Opérateur de Moyenne Harmonique Modifié ($\mathcal{H}$) :
Pour surmonter ces limitations, les auteurs introduisent un Opérateur de Moyenne Harmonique Modifié ($\mathcal{H}$). Cet opérateur :

• Partitionne les données en trois ensembles : récompenses positives ($X_+$), récompenses négatives ($X_-$) et récompenses nulles ($X_0$).
• Calcule la moyenne harmonique standard pour les sous-ensembles positifs et négatifs séparément.
• Calcule une moyenne arithmétique pondérée de ces résultats, traitant les valeurs nulles comme ayant une valeur de 0.
• Propriétés Théoriques : Les auteurs prouvent que $\mathcal{H}$ est une moyenne générale (satisfaisant l'internalité, l'idempotence, la symétrie et la monotonie) et généralise la moyenne harmonique standard là où cette dernière est définie. Cependant, ils prouvent qu'il n'est pas une moyenne quasi-arithmétique, le distinguant de la classe contenant les moyennes arithmétique, géométrique et harmonique standards.

Algorithme d'Apprentissage $R$ Harmonique :
Les auteurs intègrent $\mathcal{H}$ dans un algorithme de RL sans modèle appelé Apprentissage $R$ Harmonique.

• Il suit les règles de mise à jour structurelles de l'Apprentissage $R$ et de SMART (mise à jour des valeurs $Q$ basée sur la récompense marginale par rapport au taux moyen).
• Au lieu de mettre à jour le taux moyen $\rho$ en utilisant une simple MME arithmétique ou un ratio de MME, il maintient une Moyenne Mobile Exponentielle Harmonique.
• L'algorithme suit les réciproques des taux ($r/\tau$) pour les récompenses positives et négatives séparément, en maintenant des moyennes mobiles exponentielles de ces réciproques et de leurs poids associés, puis les inverse pour calculer l'estimation actuelle de $\rho$.

3. Contributions Clés

1. Analyse Théorique des Algorithmes Existants : L'article démontre formellement (via le Théorème 1) que le ratio des moyennes arithmétiques (utilisé par Relaxed-SMART) est égal à la moyenne harmonique uniquement si la covariance entre les récompenses et le ratio temps/récompense est nulle. Dans des contextes non stationnaires ou dépendants, cela conduit à une estimation incorrecte du taux.
2. Opérateur Novateur : L'introduction de l'Opérateur de Moyenne Harmonique Modifié ($\mathcal{H}$), qui est robuste aux récompenses nulles et de signes mixtes tout en maintenant la correction mathématique requise pour moyenner des taux.
3. Généralisation Algorithmique : Le développement de l'Apprentissage $R$ Harmonique, un algorithme sans modèle qui généralise les variantes existantes de l'Apprentissage $R$ aux SMDP sans les hypothèses de stationnarité ou d'indépendance de SMART et Relaxed-SMART.
4. Preuves Axiomatiques : Des preuves établissant que $\mathcal{H}$ est une moyenne générale mais pas une moyenne quasi-arithmétique, clarifiant son statut mathématique par rapport aux moyennes traditionnelles.

4. Résultats Empiriques

Les auteurs ont évalué l'Apprentissage $R$ Harmonique contre SMART et Relaxed-SMART dans deux domaines :

• SMDP Synthétique à Deux États :

  • Configuration : Une tâche continue avec deux actions. L'action A avait des récompenses et des durées indépendantes. L'action B avait des récompenses et des durées dépendantes et non stationnaires (utilisant des fonctions sinus/cosinus dérivantes avec mise à l'échelle logarithmique).
  • Résultat : Dans des configurations où la dépendance entre récompense et durée rendait l'action optimale "vraie" (Action B) difficile à détecter dans l'horizon d'apprentissage, SMART et Relaxed-SMART ont échoué (chutant à 0 % de succès dans des configurations plus difficiles). L'Apprentissage $R$ Harmonique a maintenu un taux de succès élevé sur toutes les combinaisons de paramètres, démontrant une robustesse supérieure face à la non-stationnarité et à la dépendance.

• Trading de Bitcoin (Données Réelles) :

  • Configuration : Un environnement à haute volatilité et non stationnaire utilisant des données de prix du Bitcoin à l'échelle de la minute (2012–2025). La tâche impliquait d'acheter/vendre avec des durées d'action stochastiques (5–45 secondes). Deux versions ont été testées : l'une avec des durées aléatoires (indépendantes) et l'autre où la durée était mise à l'échelle par l'ampleur de la récompense (dépendante).
  • Résultat :
    • Dans la version indépendante, tous les algorithmes ont performé de manière similaire, comme prévu par la théorie.
    • Dans la version dépendante (où l'ampleur de la récompense influençait la durée), l'Apprentissage $R$ Harmonique a nettement surpassé SMART et Relaxed-SMART, obtenant un ratio de victoires plus élevé sur 21 segments de données. Cela confirme l'affirmation théorique selon laquelle l'approximation du ratio des moyennes échoue lorsque les récompenses et les durées sont couplées.

5. Importance et Revendications

L'article revendique que l'Apprentissage $R$ Harmonique apporte une correction nécessaire pour l'RL à récompense moyenne dans les SMDP où les distributions de récompense et de durée sont non stationnaires ou dépendantes.

• Il soutient que les méthodes précédentes (SMART/Relaxed-SMART) sont fondamentalement défectueuses dans ces conditions spécifiques car elles reposent sur des approximations arithmétiques qui ignorent le couplage entre l'ampleur de la récompense et le temps.
• L'opérateur de moyenne harmonique modifié est présenté comme l'outil mathématiquement correct pour moyenner des taux en RL, étendant l'applicabilité de l'Apprentissage $R$ à des scénarios complexes et réels comme le trading financier où de telles dépendances sont courantes.
• Le travail est positionné comme une amélioration théorique et empirique par rapport à l'état de l'art pour l'optimisation de la récompense moyenne sans modèle dans des contextes semi-markoviens, adressant spécifiquement les lacunes "non stationnaires" et "dépendantes" dans la littérature actuelle.