Quand les méthodes de Monte-Carlo sont-elles préférées aux différences temporelles?

12

J'ai fait beaucoup de recherches récemment sur l'apprentissage par renforcement. J'ai suivi l' apprentissage par renforcement de Sutton & Barto : une introduction pour la plupart de cela.

Je sais ce que sont les processus de décision de Markov et comment l'apprentissage par programmation dynamique (DP), Monte Carlo et différence temporelle (DP) peut être utilisé pour les résoudre. Le problème que j'ai, c'est que je ne vois pas quand Monte Carlo serait la meilleure option par rapport à l'apprentissage TD.

La principale différence entre eux est que l'apprentissage TD utilise le bootstrap pour approximer la fonction action-valeur et Monte Carlo utilise une moyenne pour y parvenir. Je ne peux pas vraiment penser à un scénario quand c'est la meilleure façon de procéder.

Je suppose que cela pourrait avoir quelque chose à voir avec les performances, mais je ne trouve aucune source qui puisse le prouver.

Suis-je en train de manquer quelque chose ou l'apprentissage TD est-il généralement la meilleure option?

Anne-dirk
la source

Réponses:

8

Le principal problème avec l'apprentissage TD et DP est que leurs mises à jour de pas sont biaisées sur les conditions initiales des paramètres d'apprentissage. Le processus d'amorçage met généralement à jour une fonction ou recherche Q (s, a) sur une valeur de successeur Q (s ', a') en utilisant quelles que soient les estimations actuelles dans cette dernière. De toute évidence, au tout début de l'apprentissage, ces estimations ne contiennent aucune information provenant de récompenses réelles ou de transitions d'état.

Si l'apprentissage fonctionne comme prévu, le biais se réduira asymptotiquement sur plusieurs itérations. Cependant, le biais peut causer des problèmes importants, en particulier pour les méthodes hors politique (par exemple Q Learning) et lors de l'utilisation d'approximateurs de fonction. Cette combinaison est si susceptible de ne pas converger qu'elle est appelée la triade mortelle de Sutton & Bart.

Les méthodes de contrôle de Monte Carlo ne souffrent pas de ce biais, car chaque mise à jour est effectuée en utilisant un véritable échantillon de ce que Q (s, a) devrait être. Cependant, les méthodes de Monte Carlo peuvent souffrir d'une variance élevée, ce qui signifie que davantage d'échantillons sont nécessaires pour atteindre le même degré d'apprentissage par rapport à la TD.

En pratique, l'apprentissage TD semble apprendre plus efficacement si les problèmes avec la triade mortelle peuvent être surmontés. Des résultats récents utilisant la relecture d'expérience et des copies «gelées» d'estimateurs fournissent des solutions de contournement qui résolvent les problèmes - par exemple, c'est ainsi que l'apprenant DQN pour les jeux Atari a été construit.

Il existe également un juste milieu entre la TD et Monte-Carlo. Il est possible de construire une méthode généralisée qui combine des trajectoires de différentes longueurs - du TD en une seule étape à des épisodes complets à Monte Carlo - et de les combiner. La variante la plus courante est l' apprentissage TD ( ), où est un paramètre de (apprentissage TD en une seule étape) à (effectivement apprentissage Monte Carlo, mais avec une fonctionnalité intéressante qu'il peut être utilisé en continu problèmes). En règle générale, une valeur comprise entre et fait l'agent d'apprentissage le plus efficace - bien que comme de nombreux hyperparamètres, la meilleure valeur à utiliser dépend du problème.λ 0 1 0 1λλ0101

Si vous utilisez une méthode basée sur les valeurs (par opposition à une méthode basée sur des politiques), l'apprentissage TD est généralement plus utilisé dans la pratique, ou une méthode de combinaison TD / MC telle que TD (λ) peut être encore meilleure.

En termes d '"avantage pratique" pour MC? L'apprentissage de Monte Carlo est conceptuellement simple, robuste et facile à mettre en œuvre, bien que souvent plus lent que TD. Je ne l'utiliserais généralement pas pour un moteur de contrôleur d'apprentissage (sauf si vous êtes pressé d'implémenter quelque chose pour un environnement simple), mais je l'envisagerais sérieusement pour l'évaluation des politiques afin de comparer plusieurs agents par exemple - cela est dû au fait qu'il s'agit d'un mesure impartiale, ce qui est important pour les tests.

Neil Slater
la source
Tout d'abord, merci pour la réponse. Je vois comment en théorie un algorithme non biaisé pourrait être préféré à un algorithme biaisé. Mais vu la grande variance que Monte Carlo peut donner au début de l'entraînement, je ne vois pas en quoi cela compte vraiment. Monte Carlo et TD commenceront par des approximations inexactes et d'après ce que j'ai lu, TD convergera beaucoup plus rapidement. Je n'arrive pas vraiment à trouver un avantage pratique d'utiliser Monte Carlo. (Amuser la triade mortelle peut être évité)
Anne-dirk
1
@ Anne-dirk Si vous utilisez une méthode basée sur des valeurs (par opposition à une méthode basée sur des politiques), alors l'apprentissage TD est généralement plus utilisé dans la pratique, ou une méthode de combinaison TD / MC telle que TD (λ) peut être uniforme meilleur. Je ne sais pas ce que vous entendez par «avantage pratique»? L'apprentissage de Monte Carlo est conceptuellement simple, robuste et facile à mettre en œuvre. Je ne l'utiliserais généralement pas pour un moteur de contrôleur d'apprentissage (sauf si vous êtes pressé d'implémenter quelque chose pour un environnement simple), mais je l'envisagerais sérieusement pour l'évaluation des politiques afin de comparer plusieurs agents par exemple.
Neil Slater
@Neul Slater Aaaah je vois ... C'est le genre de réponse que je cherchais :) Merci pour votre aide!
Anne-dirk
-1

Cela dépend essentiellement de votre environnement.

TD exploite la propriété Markov, c'est-à-dire que les états futurs d'un processus ne dépendent que de l'état actuel, et qu'il est donc généralement plus efficace d'utiliser TD dans les environnements Markov.

MC n'exploite pas la propriété Markov car elle base les récompenses sur l'ensemble du processus d'apprentissage, qui se prête aux environnements non-Markov.

BigBadMe
la source
Je ne pense pas que ce soit correct ou, du moins, évident à voir. La propriété Markov, dans le contexte de RL, est associée aux états. Pouvez-vous expliquer pourquoi les algorithmes MC fonctionneraient mieux lorsque la propriété Markov ne serait pas satisfaite?
nbro
Pour être clair, je parlais d'efficacité. Si vous pouvez exploiter la propriété Markov, TD est avantageux car vous pouvez commencer dans n'importe quel état, prendre et agir et le résultat sera toujours le même, vous pouvez donc calculer l'erreur TD avec des niveaux de certitude élevés. Avec le non-MDP, si vous obtenez un état partiellement observé, le TD peut ne pas être très efficace. Cela ne veut pas dire que vous ne pouvez pas utiliser TD dans des non-MDP, vous pouvez, mais cela pourrait être inefficace et obtenir un meilleur succès avec TD lambda plutôt qu'avec TD (1).
BigBadMe
"Si vous pouvez exploiter la propriété Markov, alors TD est avantageux car vous pouvez démarrer dans n'importe quel état, prendre et agir et le résultat sera toujours le même", il en sera de même si l'environnement est déterministe. Qu'est-ce que cela a à voir avec la propriété Markov? Je ne comprends pas vos réclamations. Où avez-vous lu que TD sera plus inefficace que MC dans les POMDP par exemple?
nbro
Cela a littéralement tout à voir avec le fait qu'il s'agit de Markov; si vous êtes dans un environnement Markov, une fois que vous établissez une action dans un état a, cela conduira à un 'avec récompense x - ce sera toujours le cas dans un environnement markov, donc vous n'avez pas besoin de l'évaluer sur et plus - vous pouvez prendre des mesures plus importantes et TD vous permet d'exploiter cela. Mais ce ne sera pas le cas dans un POMDP car vous pouvez avoir exactement le même état, prendre la même action, mais vous retrouver dans des états et des récompenses complètement différents.
BigBadMe
"Si vous êtes dans un environnement Markov, une fois que vous aurez établi une action a dans l'état a, cela conduira à l'état" avec récompense x ". Non . Cela n'est vrai que si l'environnement est déterministe . L'environnement peut également être stochastique . "ce sera toujours le cas dans un environnement markov", Non , il s'agit d'un problème orthogonal à la propriété Markov.
nbro