{"id":4579,"date":"2023-09-18T20:08:56","date_gmt":"2023-09-18T18:08:56","guid":{"rendered":"https:\/\/sites.ac-corse.fr\/maths\/?page_id=4579"},"modified":"2023-11-27T11:54:47","modified_gmt":"2023-11-27T10:54:47","slug":"presentation-de-lequation-de-bellman","status":"publish","type":"page","link":"https:\/\/sites.ac-corse.fr\/maths\/presentation-de-lequation-de-bellman\/","title":{"rendered":"Pr\u00e9sentation de l\u2019\u00e9quation de Bellman"},"content":{"rendered":"\n
\n
Cors’IA<\/a><\/div>\n\n\n\n
Apprentissage par renforcement<\/a><\/div>\n\n\n\n
Apprentissage supervis\u00e9<\/a><\/div>\n<\/div>\n\n\n\n
\n\n\n
\n
\"\"<\/figure>\n<\/div>\n\n\n

\u00c9tats et Actions<\/h3>\n\n\n\n

En apprentissage par renforcement, l’\u00e9quation de Bellman<\/strong> d\u00e9crit une fa\u00e7on de r\u00e9compenser<\/strong> un agent suite \u00e0 une action.<\/p>\n\n\n\n

Avant tout, il est n\u00e9cessaire de comprendre que dans un environnement<\/strong> donn\u00e9, on d\u00e9finit :<\/p>\n\n\n\n

    \n
  • des \u00e9tats<\/strong> : ce sont les diff\u00e9rentes configurations de l’environnement. Par exemple, si on consid\u00e8re une grille de jeu de morpion (notre environnement), alors les \u00e9tats sont les diff\u00e9rents arrangements possibles de croix et de ronds.<\/li>\n<\/ul>\n\n\n\n
    \n
    \n
    \n
    \"\"<\/figure>\n<\/div><\/div>\n\n\n\n
    \n
    \"\"<\/figure>\n<\/div><\/div>\n<\/div>\n\n\n\n

    Deux \u00e9tats diff\u00e9rents au morpion<\/em><\/p>\n\n\n\n

    <\/p>\n\n\n\n

    G\u00e9n\u00e9ralement, on associe \u00e0 chaque \u00e9tat un nombre entier, de 1 \u00e0 N (nombre total d’\u00e9tats).
    Au morpion, il y a th\u00e9oriquement N = 39<\/sup> = 19683 \u00e9tats, mais certains n’apparaissent jamais, comme une grille remplie de ronds.<\/p>\n\n\n\n

      \n
    • des actions<\/strong> : ce sont les choix possibles, quel que soit l’\u00e9tat consid\u00e9r\u00e9. Au morpion, en consid\u00e9rant le joueur qui place les croix, il y a donc 9 actions possibles, une pour chaque case de la grille. Certaines actions m\u00e8nent \u00e0 la victoire ou \u00e0 la d\u00e9faite, d’autres font simplement progresser le jeu. Une action \u00ab\u00a0impossible\u00a0\u00bb, comme jouer sur une case d\u00e9j\u00e0 occup\u00e9e, am\u00e8nera \u00e0 la d\u00e9faite.<\/li>\n<\/ul>\n<\/div><\/div>\n\n\n\n

      Un tableau de scores : la Q-Table<\/em><\/h3>\n\n\n\n

      Pour choisir quelle action effectuer dans un \u00e9tat donn\u00e9, on utilise un tableau de scores, appel\u00e9 Q-table<\/em> (Q<\/em> pour Qualit\u00e9<\/em>) : c’est un tableau \u00e0 double entr\u00e9e qui, \u00e0 chaque paire (\u00e9tat , action) associe un score, positif ou n\u00e9gatif.<\/p>\n\n\n\n

      Dans un \u00e9tat donn\u00e9, on choisira alors l’action avec le plus grand score.<\/p>\n\n\n

      \n
      \"\"<\/figure>\n<\/div>\n\n\n

      Dans cet exemple, on voit que les actions menant \u00e0 une victoire sont mieux r\u00e9compens\u00e9es que les autres. Quant aux actions \u00ab\u00a0interdites\u00a0\u00bb, elles sont fortement punies par un score n\u00e9gatif.<\/p>\n\n\n\n

      Dans le cas du morpion, la Q-Table<\/em> contient au plus 39<\/sup> x 9 = 177 147 cases. C’est beaucoup pour un humain, mais pas pour un ordinateur.
      Cependant, dans le cas d’un jeu comme le puissance 4, il y a 7 actions possibles et un maximum th\u00e9orique de 342<\/sup> \u00e9tats, soit une Q-Table<\/em> contenant au maximum 342<\/sup> x 7 = 765932923920586514463 cases !<\/p>\n\n\n\n

      Le probl\u00e8me qui se pose alors est : comment remplir correctement et efficacement la Q-Table ? C’est l\u00e0 qu’intervient l’\u00e9quation de Bellman<\/strong>.<\/p>\n\n\n\n

      Q-Table et \u00e9quation de Bellman<\/h3>\n\n\n

      \n Q<\/mi>\n (<\/mo>\n s<\/mi>\n ,<\/mo>\n a<\/mi>\n )<\/mo>\n ←<\/mo>\n Q<\/mi>\n (<\/mo>\n s<\/mi>\n ,<\/mo>\n a<\/mi>\n )<\/mo>\n +<\/mo>\n α<\/mi>\n \n (<\/mo>\n R<\/mi>\n +<\/mo>\n γ<\/mi>\n \n (<\/mo>\n m<\/mi>\n a<\/mi>\n \n x<\/mi>\n \n \n a<\/mi>\n ′<\/mo>\n <\/msup>\n <\/mrow>\n <\/msub>\n Q<\/mi>\n (<\/mo>\n \n s<\/mi>\n ′<\/mo>\n <\/msup>\n ,<\/mo>\n \n a<\/mi>\n ′<\/mo>\n <\/msup>\n )<\/mo>\n −<\/mo>\n Q<\/mi>\n (<\/mo>\n s<\/mi>\n ,<\/mo>\n a<\/mi>\n )<\/mo>\n )<\/mo>\n <\/mrow>\n )<\/mo>\n <\/mrow>\n<\/math><\/p>\n\n\n\n

      Quelques explications s’imposent :<\/p>\n\n\n\n

        \n
      • \n s<\/mi>\n<\/math> repr\u00e9sente un \u00e9tat, \n a<\/mi>\n<\/math> une action et \n Q<\/mi>\n (<\/mo>\n s<\/mi>\n ,<\/mo>\n a<\/mi>\n )<\/mo>\n<\/math> le score associ\u00e9 au couple (\u00e9tat, action)<\/li>\n\n\n\n
      • \u03b1<\/mi> <\/math> et \u03b3<\/mi> <\/math> sont des param\u00e8tres d’apprentissage, nomm\u00e9s respectivement la vitesse d’apprentissage et le facteur d’actualisation<\/li>\n\n\n\n
      • R est la r\u00e9compense associ\u00e9e \u00e0 l’action a<\/mi><\/math> dans l’\u00e9tat s<\/mi><\/math>, et prend en g\u00e9n\u00e9ral au moins 3 valeurs :\n
          \n
        • une valeur en cas de victoire, comme +10<\/li>\n\n\n\n
        • une valeur en cas de d\u00e9faite, comme -10<\/li>\n\n\n\n
        • une valeur par d\u00e9faut, lorsque le jeu continue, comme -1<\/li>\n<\/ul>\n<\/li>\n\n\n\n
        • m<\/mi> a<\/mi> x<\/mi> a<\/mi> \u2032<\/mo> <\/msup> <\/mrow> <\/msub> Q<\/mi> (<\/mo> s<\/mi> \u2032<\/mo> <\/msup> ,<\/mo> a<\/mi> \u2032<\/mo> <\/msup> )<\/mo> <\/math> repr\u00e9sente le score maximum que l’on peut obtenir depuis l’\u00e9tat s<\/mi> \u2032<\/mo><\/msup><\/math>, suivant l’\u00e9tat s<\/mi><\/math>  apr\u00e8s l’action a<\/mi><\/math>.<\/li>\n<\/ul>\n\n\n\n

          On peut r\u00e9\u00e9crire cette \u00e9quation de la fa\u00e7on suivante :<\/p>\n\n\n

          \n Q<\/mi>\n (<\/mo>\n s<\/mi>\n ,<\/mo>\n a<\/mi>\n )<\/mo>\n ←<\/mo>\n (<\/mo>\n 1<\/mn>\n −<\/mo>\n α<\/mi>\n )<\/mo>\n ×<\/mo>\n Q<\/mi>\n (<\/mo>\n s<\/mi>\n ,<\/mo>\n a<\/mi>\n )<\/mo>\n +<\/mo>\n α<\/mi>\n ×<\/mo>\n R<\/mi>\n +<\/mo>\n α<\/mi>\n γ<\/mi>\n ×<\/mo>\n m<\/mi>\n a<\/mi>\n \n x<\/mi>\n \n \n a<\/mi>\n ′<\/mo>\n <\/msup>\n <\/mrow>\n <\/msub>\n Q<\/mi>\n (<\/mo>\n \n s<\/mi>\n ′<\/mo>\n <\/msup>\n ,<\/mo>\n \n a<\/mi>\n ′<\/mo>\n <\/msup>\n )<\/mo>\n<\/math><\/p>\n\n\n\n

          Un cas particulier est celui o\u00f9  \u03b1<\/mi> =<\/mo> 1<\/mn> <\/math> : on \u00ab\u00a0oublie\u00a0\u00bb le score pr\u00e9c\u00e9dent Q<\/mi> (<\/mo> s<\/mi> ,<\/mo> a<\/mi> )<\/mo> <\/math>, et on met \u00e0 jour la Q-Table<\/em> uniquement avec la r\u00e9compense  R et le score \u00ab\u00a0futur\u00a0\u00bb maximum  :<\/p>\n\n\n

          \n Q<\/mi>\n (<\/mo>\n s<\/mi>\n ,<\/mo>\n a<\/mi>\n )<\/mo>\n ←<\/mo>\n R<\/mi>\n +<\/mo>\n γ<\/mi>\n ×<\/mo>\n m<\/mi>\n a<\/mi>\n \n x<\/mi>\n \n \n a<\/mi>\n ′<\/mo>\n <\/msup>\n <\/mrow>\n <\/msub>\n Q<\/mi>\n (<\/mo>\n \n s<\/mi>\n ′<\/mo>\n <\/msup>\n ,<\/mo>\n \n a<\/mi>\n ′<\/mo>\n <\/msup>\n )<\/mo>\n<\/math><\/p>\n\n\n\n

          Avec cette derni\u00e8re formule, on voit bien le r\u00f4le de \n  <\/mtext>\n m<\/mi>\n a<\/mi>\n \n x<\/mi>\n \n \n a<\/mi>\n \u2032<\/mo>\n <\/msup>\n <\/mrow>\n <\/msub>\n Q<\/mi>\n (<\/mo>\n \n s<\/mi>\n \u2032<\/mo>\n <\/msup>\n ,<\/mo>\n \n a<\/mi>\n \u2032<\/mo>\n <\/msup>\n )<\/mo>\n<\/math> : plus l’\u00e9tat \n \n s<\/mi>\n \u2032<\/mo>\n <\/msup>\n<\/math> est int\u00e9ressant pour gagner, plus ce maximum sera grand et la valeur de \n Q<\/mi>\n (<\/mo>\n s<\/mi>\n ,<\/mo>\n a<\/mi>\n )<\/mo>\n<\/math> augment\u00e9e en cons\u00e9quence, indiquant qu’effectuer l’action \n a<\/mi>\n<\/math> dans l’\u00e9tat \n s<\/mi>\n<\/math> est une bonne solution. Inversement, moins cet \u00e9tat est int\u00e9ressant et moins \n Q<\/mi>\n (<\/mo>\n s<\/mi>\n ,<\/mo>\n a<\/mi>\n )<\/mo>\n<\/math> augmentera.<\/p>\n","protected":false},"excerpt":{"rendered":"

          \u00c9tats et Actions En apprentissage par renforcement, l’\u00e9quation de Bellman d\u00e9crit une fa\u00e7on de r\u00e9compenser un agent suite \u00e0 une action. Avant tout, il est n\u00e9cessaire de comprendre que dans un environnement donn\u00e9, on d\u00e9finit : Deux \u00e9tats diff\u00e9rents au morpion G\u00e9n\u00e9ralement, on associe \u00e0 chaque \u00e9tat un nombre entier, de 1 \u00e0 N (nombre total d’\u00e9tats).Au morpion, il y […]<\/p>\n","protected":false},"author":90,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-4579","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/sites.ac-corse.fr\/maths\/wp-json\/wp\/v2\/pages\/4579","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sites.ac-corse.fr\/maths\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/sites.ac-corse.fr\/maths\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/sites.ac-corse.fr\/maths\/wp-json\/wp\/v2\/users\/90"}],"replies":[{"embeddable":true,"href":"https:\/\/sites.ac-corse.fr\/maths\/wp-json\/wp\/v2\/comments?post=4579"}],"version-history":[{"count":40,"href":"https:\/\/sites.ac-corse.fr\/maths\/wp-json\/wp\/v2\/pages\/4579\/revisions"}],"predecessor-version":[{"id":5039,"href":"https:\/\/sites.ac-corse.fr\/maths\/wp-json\/wp\/v2\/pages\/4579\/revisions\/5039"}],"wp:attachment":[{"href":"https:\/\/sites.ac-corse.fr\/maths\/wp-json\/wp\/v2\/media?parent=4579"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}