Prise de décision séquentielle (MDPs)
La prise de décision séquentielle formalise la manière dont un agent devrait agir au fil du temps dans un environnement stochastique, en utilisant des processus décisionnels de Markov dans lesquels les actions génèrent des récompenses et modifient l'état de manière probabiliste, afin de calculer une politique maximisant la récompense attendue à long terme.
Definition
Un processus décisionnel de Markov est défini par des états, des actions, une fonction de probabilité de transition et une fonction de récompense ; la prise de décision séquentielle recherche une politique qui associe des actions aux états et qui maximise la récompense cumulative attendue (généralement actualisée), étant donné le modèle.
Scope
Ce sujet couvre la planification décisionnelle au fil du temps : le modèle de processus décisionnel de Markov (MDP) incluant les états, les actions, les probabilités de transition, les récompenses et l'actualisation ; les politiques et les fonctions de valeur ; les équations de Bellman caractérisant le comportement optimal ; ainsi que les algorithmes de programmation dynamique d'itération de la valeur et d'itération de la politique pour résoudre un modèle connu. Il introduit également les MDPs partiellement observables (POMDPs) et la planification basée sur l'état de croyance. L'accent est mis sur la planification lorsque le modèle est donné ; l'apprentissage d'une politique à partir de l'expérience sans modèle connu relève de l'apprentissage par renforcement, qui appartient au sous-domaine de l'apprentissage automatique.
Core questions
- Comment l'action au fil du temps sous des transitions stochastiques est-elle modélisée en termes d'états, d'actions, de transitions et de récompenses ?
- Que dit l'équation d'optimalité de Bellman sur la valeur d'une politique optimale ?
- Comment l'itération de la valeur et l'itération de la politique calculent-elles une politique optimale lorsque le modèle est connu ?
- Comment l'observabilité partielle conduit-elle aux POMDPs et à la planification sur les états de croyance ?
Key concepts
- états, actions, transitions, récompenses
- politique
- fonction de valeur
- facteur d'actualisation
- équations de Bellman
- itération de la valeur
- itération de la politique
- POMDP et état de croyance
Key theories
- Équation d'optimalité de Bellman
- La valeur optimale d'un état est égale à la meilleure récompense immédiate plus la valeur optimale attendue actualisée de l'état suivant ; cette relation récursive caractérise le comportement séquentiel optimal et constitue le fondement des solutions de programmation dynamique.
- Itération de la valeur et de la politique
- Pour un MDP connu, l'itération de la valeur applique de manière répétée la mise à jour de Bellman jusqu'à convergence, et l'itération de la politique alterne l'évaluation et l'amélioration de la politique ; les deux sont garanties de trouver une politique optimale.
- MDPs partiellement observables
- Lorsque l'état n'est pas directement observable, la planification s'effectue sur un état de croyance (une distribution de probabilité sur les états) mis à jour à partir des observations ; résoudre de tels POMDPs est bien plus difficile que le cas entièrement observable mais permet de prendre en compte des limitations de perception réalistes.
Clinical relevance
La prise de décision basée sur les MDP et les POMDPs sous-tend la navigation et le contrôle de robots, la gestion automatisée de dialogues, les décisions de maintenance et de gestion des stocks, et l'allocation de ressources. Elle fournit également la base de planification décisionnelle sur laquelle l'apprentissage par renforcement s'appuie lorsque le modèle de l'environnement doit être appris.
History
La prise de décision séquentielle a émergé de la programmation dynamique de Bellman (1957) et de l'itération de politique de Howard (1960). La monographie de Puterman de 1994 a consolidé la théorie des processus décisionnels de Markov, et Kaelbling, Littman et Cassandra (1998) ont introduit les MDPs partiellement observables dans l'IA grand public comme modèle pour agir sous une perception incertaine.
Key figures
- Richard Bellman
- Ronald A. Howard
- Martin L. Puterman
- Leslie P. Kaelbling
- Michael L. Littman
Related topics
Seminal works
- bellman1957
- puterman1994
- kaelbling1998
Frequently asked questions
- En quoi cela diffère-t-il de l'apprentissage par renforcement ?
- La prise de décision séquentielle avec les MDPs suppose que le modèle de transition et de récompense est connu, de sorte qu'une politique optimale peut être calculée directement par programmation dynamique. L'apprentissage par renforcement aborde le cas où le modèle est inconnu et l'agent doit apprendre une bonne politique à partir de l'expérience ; il utilise le MDP comme formalisme sous-jacent.
- Qu'est-ce qu'un état de croyance dans un POMDP ?
- Dans un MDP partiellement observable, l'agent ne peut pas voir l'état réel, il maintient donc un état de croyance, une distribution de probabilité sur les états possibles, mis à jour au fur et à mesure qu'il effectue des actions et reçoit des observations. La planification s'effectue alors sur ces états de croyance plutôt que directement sur les états cachés.