CS 221 - Intelligence Artificielle

Modèles basés sur les états : optimisation de parcours et MDPs

Par Afshine Amidi et Shervine Amidi

Star

Optimisation de parcours

Dans cette section, nous supposons qu'en effectuant une action $a$ à partir d'un état $s$, on arrive de manière déterministe à l'état $\textrm{Succ}(s,a)$. Le but de cette étude est de déterminer une séquence d'actions $(a_1,a_2,a_3,a_4,...)$ démarrant d'un état initial et aboutissant à un état final. Pour y parvenir, notre objectif est de minimiser le coût associés à ces actions à l'aide de modèles basés sur les états (state-based model en anglais).

Parcours d'arbre

Cette catégorie d'algorithmes explore tous les états et actions possibles. Même si leur consommation en mémoire est raisonnable et peut supporter des espaces d'états de taille très grande, ce type d'algorithmes est néanmoins susceptible d'engendrer des complexités en temps exponentielles dans le pire des cas.

Tree

Problème de recherche Un problème de recherche est défini par :

Search problem

L'objectif est de trouver un chemin minimisant le coût total des actions utilisées.


Retour sur trace L'algorithme de retour sur trace (en anglais backtracking search) est un algorithme récursif explorant naïvement toutes les possibilités jusqu'à trouver le chemin de coût minimal. Ici, le coût des actions peut aussi bien être positif que négatif.


Parcours en largeur (BFS) L'algorithme de parcours en largeur (en anglais breadth-first search ou BFS) est un algorithme de parcours de graphe traversant chaque niveau de manière successive. On peut le coder de manière itérative à l'aide d'une queue stockant à chaque étape les prochains nœuds à visiter. Cet algorithme suppose que le coût de toutes les actions est égal à une constante $c\geqslant0$.

BFS

Parcours en profondeur (DFS) L'algorithme de parcours en profondeur (en anglais depth-first search ou DFS) est un algorithme de parcours de graphe traversant chaque chemin qu'il emprunte aussi loin que possible. On peut le coder de manière récursive, ou itérative à l'aide d'une pile qui stocke à chaque étape les prochains nœuds à visiter. Cet algorithme suppose que le coût de toutes les actions est égal à 0.

DFS

Approfondissement itératif L'astuce de l'approfondissement itératif (en anglais iterative deepening) est une modification de l'algorithme de DFS qui l'arrête après avoir atteint une certaine profondeur, garantissant l'optimalité de la solution trouvée quand toutes les actions ont un même coût constant $c\geqslant0$.


Récapitulatif des algorithmes de parcours d'arbre En notant $b$ le nombre d'actions par état, $d$ la profondeur de la solution et $D$ la profondeur maximale, on a :

Algorithme Coût des actions Espace Temps
Retour sur trace peu importe $\mathcal{O}(D)$ $\mathcal{O}(b^D)$
Parcours en largeur $c\geqslant0$ $\mathcal{O}(b^d)$ $\mathcal{O}(b^d)$
Parcours en profondeur 0 $\mathcal{O}(D)$ $\mathcal{O}(b^D)$
DFS-approfondissement itératif $c\geqslant0$ $\mathcal{O}(d)$ $\mathcal{O}(b^d)$

Parcours de graphe

Cette catégorie d'algorithmes basés sur les états vise à trouver des chemins optimaux avec une complexité moins grande qu'exponentielle. Dans cette section, nous allons nous concentrer sur la programmation dynamique et la recherche à coût uniforme.

Graphe Un graphe se compose d'un ensemble de sommets $V$ (aussi appelés nœuds) et d'arêtes $E$ (appelés arcs lorsque le graphe est orienté).

Graph

Remarque : un graphe est dit être acyclique lorsqu'il ne contient pas de cycle.


État Un état contient le résumé des actions passées suffisant pour choisir les actions futures de manière optimale.


Programmation dynamique La programmation dynamique (en anglais dynamic programming ou DP) est un algorithme de recherche de type retour sur trace qui utilise le principe de mémoïsation (i.e. les résultats intermédiaires sont enregistrés) et ayant pour but de trouver le chemin à coût minimal allant de l'état $s$ à l'état final $s_\textrm{end}$. Cette procédure peut potentiellement engendrer des économies exponentielles si on la compare aux algorithmes de parcours de graphe traditionnels, et a la propriété de ne marcher que dans le cas de graphes acycliques. Pour un état $s$ donné, le coût futur est calculé de la manière suivante :

\[\boxed{\textrm{FutureCost}(s)=\left\{\begin{array}{lc}0 & \textrm{si IsEnd}(s)\\\underset{a\in\textrm{Actions}(s)}{\textrm{min}}\big[\textrm{Cost}(s,a)+\textrm{FutureCost(Succ}(s,a))\big] & \textrm{sinon}\end{array}\right.}\]
Dynamic Programming

Remarque : la figure ci-dessus illustre une approche ascendante alors que la formule nous donne l'intuition d'une résolution avec une approche descendante.


Types d'états La table ci-dessous présente la terminologie relative aux états dans le contexte de la recherche à coût uniforme :

État Explication
Exploré $\mathcal{E}$ États pour lesquels le chemin optimal a déjà été trouvé
Frontière $\mathcal{F}$ États rencontrés mais pour lesquels on se demande toujours comment s'y rendre avec un coût minimal
Inexploré $\mathcal{U}$ États non rencontrés jusqu'à présent

Recherche à coût uniforme La recherche à coût uniforme (uniform cost search ou UCS en anglais) est un algorithme de recherche qui a pour but de trouver le chemin le plus court entre les états $s_\textrm{start}$ et $s_\textrm{end}$. Celui-ci explore les états $s$ en les triant par coût croissant de $\textrm{PastCost}(s)$ et repose sur le fait que toutes les actions ont un coût non négatif.

Uniform Cost Search

Remarque 1 : UCS fonctionne de la même manière que l'algorithme de Dijkstra.

Remarque 2 : cet algorithme ne marche pas sur une configuration contenant des actions à coût négatif. Quelqu'un pourrait penser à ajouter une constante positive à tous les coûts, mais cela ne résoudrait rien puisque le problème résultant serait différent.


Théorème de correction Lorsqu'un état $s$ passe de la frontière $\mathcal{F}$ à l'ensemble exploré $\mathcal{E}$, sa priorité est égale à $\textrm{PastCost}(s)$, représentant le chemin de coût minimal allant de $s_\textrm{start}$ à $s$.


Récapitulatif des algorithmes de parcours de graphe En notant $N$ le nombre total d'états dont $n$ sont explorés avant l'état final $s_\textrm{end}$, on a :

Algorithme Acyclicité Coûts Temps/Espace
Programmation dynamique oui peu importe $\mathcal{O}(N)$
Recherche à coût uniforme non $c\geqslant0$ $\mathcal{O}(n\log(n))$

Remarque : ce décompte de la complexité suppose que le nombre d'actions possibles à partir de chaque état est constant.


Apprentissage des coûts

Supposons que nous ne sommes pas donnés les valeurs de $\textrm{Cost}(s,a)$. Nous souhaitons estimer ces quantités à partir d'un ensemble d'apprentissage de chemins à coût minimaux d'actions $(a_1, a_2, ..., a_k)$.

Perceptron structuré L'algorithme du perceptron structuré vise à apprendre de manière itérative les coûts des paires état-action. À chaque étape, il :

Remarque : plusieurs versions de cette algorithme existent, l'une d'elles réduisant ce problème à l'apprentissage du coût de chaque action $a$ et l'autre paramétrisant chaque $\textrm{Cost}(s,a)$ à un vecteur de paramètres pouvant être appris.


Algorithme $\textrm{A}^{\star}$

Fonction heuristique Une heuristique est une fonction $h$ opérant sur les états $s$, où chaque $h(s)$ vise à estimer $\textrm{FutureCost}(s)$, le coût du chemin optimal allant de $s$ à $s_\textrm{end}$.

A star

Algorithme $A^{*}$ est un algorithme de recherche visant à trouver le chemin le plus court entre un état $s$ et un état final $s_\textrm{end}$. Il le fait en explorant les états $s$ triés par ordre croissant de $\textrm{PastCost}(s) + h(s)$. Cela revient à utiliser l'algorithme UCS où chaque arête est associée au coût $\textrm{Cost}'(s,a)$ donné par :

\[\boxed{\textrm{Cost}'(s,a)=\textrm{Cost}(s,a)+h(\textrm{Succ}(s,a))-h(s)}\]

Remarque : cet algorithme peut être vu comme une version biaisée de UCS explorant les états estimés comme étant plus proches de l'état final.


Consistance Une heuristique $h$ est dite consistante si elle satisfait les deux propriétés suivantes :


Correction Si $h$ est consistante, alors $A^*$ renvoie le chemin de coût minimal.


Admissibilité Une heuristique $h$ est dite admissible si l'on a :

\[\boxed{h(s)\leqslant\textrm{FutureCost}(s)}\]

Théorème Soit $h(s)$ une heuristique. On a :

\[\boxed{h(s)\textrm{ consistante}\Longrightarrow h(s)\textrm{ admissible}}\]

Efficacité $A^*$ explore les états $s$ satisfaisant l'équation :

\[\boxed{\textrm{PastCost}(s)\leqslant\textrm{PastCost}(s_{\textrm{end}})-h(s)}\]
Efficiency

Remarque : avoir $h(s)$ élevé est préférable puisque cette équation montre que le nombre d'états $s$ à explorer est alors réduit.


Relaxation

C'est un type de procédure permettant de produire des heuristiques consistantes. L'idée est de trouver une fonction de coût facile à exprimer en enlevant des contraintes au problème, et ensuite l'utiliser en tant qu'heuristique.


Relaxation d'un problème de recherche La relaxation d'un problème de recherche $P$ aux coûts Cost est noté $P_{\textrm{rel}}$ avec coûts $\textrm{Cost}_{\textrm{rel}}$, et vérifie la relation :

\[\boxed{\textrm{Cost}_{\textrm{rel}}(s,a)\leqslant\textrm{Cost}(s,a)}\]

Relaxation d'une heuristique Étant donné la relaxation d'un problème de recherche $P_{\textrm{rel}}$, on définit l'heuristique relaxée $h(s)=\textrm{FutureCost}_{\textrm{rel}}(s)$ comme étant le chemin de coût minimal allant de $s$ à un état final dans le graphe de fonction de coût $\textrm{Cost}_{\textrm{rel}}(s,a)$.


Consistance de la relaxation d'heuristiques Soit $P_{\textrm{rel}}$ une relaxation d'un problème de recherche. Par théorème, on a :

\[\boxed{h(s)=\textrm{FutureCost}_{\textrm{rel}}(s)\Longrightarrow h(s)\textrm{ consistante}}\]

Compromis lors du choix d'heuristique Le choix d'heuristique se repose sur un compromis entre :


Heuristique max Soient $h_1(s)$ et $h_2(s)$ deux heuristiques. On a la propriété suivante :

\[\boxed{h_1(s),\textrm{ }h_2(s)\textrm{ consistante}\Longrightarrow h(s)=\max\{h_1(s),\textrm{ }h_2(s)\}\textrm{ consistante}}\]

Processus de décision markovien

Dans cette section, on suppose qu'effectuer l'action $a$ à partir de l'état $s$ peut mener de manière probabiliste à plusieurs états $s_1',s_2',...$ Dans le but de trouver ce qu'il faudrait faire entre un état initial et un état final, on souhaite trouver une stratégie maximisant la quantité des récompenses en utilisant un outil adapté à l'imprévisibilité et l'incertitude : les processus de décision markoviens.

Notations

Définition L'objectif d'un processus de décision markovien (en anglais Markov decision process ou MDP) est de maximiser la quantité de récompenses. Un tel problème est défini par :

Markov Decision Process

Probabilités de transitions La probabilité de transition $T(s,a,s')$ représente la probabilité de transitionner vers l'état $s'$ après avoir effectué l'action $a$ en étant dans l'état $s$. Chaque $s' \mapsto T(s,a,s')$ est une loi de probabilité :

\[\forall s,a,\quad\boxed{\displaystyle\sum_{s'\in\textrm{ États}}T(s,a,s')=1}\]

Politique Une politique $\pi$ est une fonction liant chaque état $s$ à une action $a$, i.e.

\[\boxed{\pi : s \mapsto a}\]

Utilité L'utilité d'un chemin $(s_0, ..., s_k)$ est la somme des récompenses dévaluées récoltées sur ce chemin. En d'autres termes,

\[\boxed{u(s_0,...,s_k)=\sum_{i=1}^{k}r_i\gamma^{i-1}}\]
Utility

La figure ci-dessus illustre le cas $k=4$.


Q-value La fonction de valeur des états-actions ($Q$-value en anglais) d'une politique $\pi$ évaluée à l'état $s$ avec l'action $a$, aussi notée $Q_{\pi}(s,a)$, est l'espérance de l'utilité partant de l'état $s$ avec l'action $a$ et adoptant ensuite la politique $\pi$. Cette fonction est définie par :

\[\boxed{Q_{\pi}(s,a)=\sum_{s'\in\textrm{ États}}T(s,a,s')\left[\textrm{Reward}(s,a,s')+\gamma V_\pi(s')\right]}\]

Fonction de valeur des états d'une politique La fonction de valeur des états d'une politique $\pi$ évaluée à l'état $s$, aussi notée $V_{\pi}(s)$, est l'espérance de l'utilité partant de l'état $s$ et adoptant ensuite la politique $\pi$. Cette fonction est définie par :

\[\boxed{V_\pi(s)=Q_\pi(s,\pi(s))}\]

Remarque : $V_\pi(s)$ vaut 0 si s est un état final.


Applications

Évaluation d'une politique Étant donnée une politique $\pi$, on peut utiliser l'algorithme itératif d'évaluation de politiques (en anglais policy evaluation) pour estimer $V_\pi$ :

Remarque : en notant $S$ le nombre d'états, $A$ le nombre d'actions par états, $S'$ le nombre de successeurs et $T$ le nombre d'itérations, la complexité en temps est alors de $\mathcal{O}(T_{\textrm{PE}}SS')$.


Q-value optimale La $Q$-value optimale $Q_{\textrm{opt}}(s,a)$ d'un état $s$ avec l'action $a$ est définie comme étant la $Q$-value maximale atteinte avec n'importe quelle politique. Elle est calculée avec la formule :

\[\boxed{Q_{\textrm{opt}}(s,a)=\sum_{s'\in\textrm{ États}}T(s,a,s')\left[\textrm{Reward}(s,a,s')+\gamma V_\textrm{opt}(s')\right]}\]

Valeur optimale La valeur optimale $V_{\textrm{opt}}(s)$ d'un état $s$ est définie comme étant la valeur maximum atteinte par n'importe quelle politique. Elle est calculée avec la formule :

\[\boxed{V_{\textrm{opt}}(s)=\underset{a\in\textrm{ Actions}(s)}{\textrm{max}}Q_\textrm{opt}(s,a)}\]

Politique optimale La politique optimale $\pi_{\textrm{opt}}$ est définie comme étant la politique liée aux valeurs optimales. Elle est définie par :

\[\forall s,\quad\boxed{\pi_{\textrm{opt}}(s)=\underset{a\in\textrm{ Actions}(s)}{\textrm{argmax}}Q_\textrm{opt}(s,a)}\]

Itération sur la valeur L'algorithme d'itération sur la valeur (en anglais value iteration) vise à trouver la valeur optimale $V_{\textrm{opt}}$ ainsi que la politique optimale $\pi_{\textrm{opt}}$ en deux temps :

Remarque : si $\gamma < 1$ ou si le graphe associé au processus de décision markovien est acyclique, alors l'algorithme d'itération sur la valeur est garanti de converger vers la bonne solution.


Cas des transitions et récompenses inconnues

On suppose maintenant que les probabilités de transition et les récompenses sont inconnues.

Monte-Carlo basé sur modèle La méthode de Monte-Carlo basée sur modèle (en anglais model-based Monte Carlo) vise à estimer $T(s,a,s')$ et $\textrm{Reward}(s,a,s')$ en utilisant des simulations de Monte-Carlo avec :

\[\boxed{\widehat{T}(s,a,s')=\frac{\#\textrm{ de fois où }(s,a,s')\textrm{ se produit}}{\#\textrm{ de fois où }(s,a)\textrm{ se produit}}}\]
et
\[\boxed{\widehat{\textrm{Reward}}(s,a,s')=r\textrm{ dans }(s,a,r,s')}\]
Ces estimations sont ensuite utilisées pour trouver les $Q$-values, ainsi que $Q_\pi$ et $Q_\textrm{opt}$.

Remarque : la méthode de Monte-Carlo basée sur modèle est dite "hors politique" (en anglais "off-policy") car l'estimation produite ne dépend pas de la politique utilisée.


Monte-Carlo sans modèle La méthode de Monte-Carlo sans modèle (en anglais model-free Monte Carlo) vise à directement estimer $Q_{\pi}$ de la manière suivante :

\[\boxed{\widehat{Q}_\pi(s,a)=\textrm{moyenne de }u_t\textrm{ où }s_{t-1}=s, a_t=a}\]
où $u_t$ désigne l'utilité à partir de l'étape $t$ d'un épisode donné.

Remarque : la méthode de Monte-Carlo sans modèle est dite "sur politique" (en anglais "on-policy") car l'estimation produite dépend de la politique $\pi$ utilisée pour générer les données.


Formulation équivalente En introduisant la constante $\eta=\frac{1}{1+(\#\textrm{mises à jour à }(s,a))}$ et pour chaque triplet $(s,a,u)$ de la base d'apprentissage, la formule de récurrence de la méthode de Monte-Carlo sans modèle s'écrit à l'aide de la combinaison convexe :

\[\boxed{\widehat{Q}_\pi(s,a)\leftarrow(1-\eta)\widehat{Q}_\pi(s,a)+\eta u}\]
ainsi qu'une formulation mettant en valeur une sorte de gradient :
\[\boxed{\widehat{Q}_\pi(s,a)\leftarrow\widehat{Q}_\pi(s,a) - \eta (\widehat{Q}_\pi(s,a) - u)}\]


SARSA État-action-récompense-état-action (en anglais state-action-reward-state-action ou SARSA) est une méthode de bootstrap qui estime $Q_\pi$ en utilisant à la fois des données réelles et estimées dans sa formule de mise à jour. Pour chaque $(s,a,r,s',a')$, on a :

\[\boxed{\widehat{Q}_\pi(s,a)\longleftarrow(1-\eta)\widehat{Q}_\pi(s,a)+\eta\Big[r+\gamma\widehat{Q}_\pi(s',a')\Big]}\]

Remarque : l'estimation donnée par SARSA est mise à jour à la volée contrairement à celle donnée par la méthode de Monte-Carlo sans modèle où la mise à jour est uniquement effectuée à la fin de l'épisode.


Q-learning Le $Q$-apprentissage (en anglais $Q$-learning) est un algorithme hors politique (en anglais off-policy) donnant une estimation de $Q_\textrm{opt}$. Pour chaque $(s,a,r,s',a')$, on a :

\[\boxed{\widehat{Q}_{\textrm{opt}}(s,a)\leftarrow(1-\eta)\widehat{Q}_{\textrm{opt}}(s,a)+\eta\Big[r+\gamma\underset{a'\in\textrm{ Actions}(s')}{\textrm{max}}\widehat{Q}_{\textrm{opt}}(s',a')\Big]}\]

Epsilon-glouton La politique epsilon-gloutonne (en anglais epsilon-greedy) est un algorithme essayant de trouver un compromis entre l'exploration avec probabilité $\epsilon$ et l'exploitation avec probabilité $1-\epsilon$. Pour un état $s$, la politique $\pi_{\textrm{act}}$ est calculée par :

\[\boxed{\pi_\textrm{act}(s)=\left\{\begin{array}{ll}\underset{a\in\textrm{ Actions}}{\textrm{argmax }}\widehat{Q}_\textrm{opt}(s,a) & \textrm{avec proba }1-\epsilon\\\textrm{aléatoire venant d'Actions}(s) & \textrm{avec proba }\epsilon\end{array}\right.}\]

Jeux

Dans les jeux (e.g. échecs, backgammon, Go), d'autres agents sont présents et doivent être pris en compte au moment d'élaborer une politique.

Arbre de jeu Un arbre de jeu est un arbre détaillant toutes les issues possibles d'un jeu. En particulier, chaque nœud représente un point de décision pour un joueur et chaque chemin liant la racine à une des feuilles traduit une possible instance du jeu.


Jeu à somme nulle à deux joueurs C'est un type jeu où chaque état est entièrement observé et où les joueurs jouent de manière successive. On le définit par :

Remarque : nous assumerons que l'utilité de l'agent a le signe opposé de celui de son adversaire.


Types de politiques Il y a deux types de politiques :


Expectimax Pour un état donné $s$, la valeur d'expectimax $V_{\textrm{exptmax}}(s)$ est l'utilité maximum sur l'ensemble des politiques utilisées par l'agent lorsque celui-ci joue avec un adversaire de politique connue $\pi_{\textrm{opp}}$. Cette valeur est calculée de la manière suivante :

\[\boxed{V_{\textrm{exptmax}}(s)=\left\{\begin{array}{ll}\textrm{Utility}(s) & \textrm{IsEnd}(s)\\\underset{a\in\textrm{Actions}(s)}{\textrm{max}}V_{\textrm{exptmax}}(\textrm{Succ}(s,a)) & \textrm{Player}(s)=\textrm{agent}\\\displaystyle\sum_{a\in\textrm{Actions}(s)}\pi_{\textrm{opp}}(s,a)V_{\textrm{exptmax}}(\textrm{Succ}(s,a)) & \textrm{Player}(s)=\textrm{opp}\end{array}\right.}\]

Remarque : expectimax est l'analogue de l'algorithme d'itération sur la valeur pour les MDPs.

Expectimax

Minimax Le but des politiques minimax est de trouver une politique optimale contre un adversaire que l'on assume effectuer toutes les pires actions, i.e. toutes celles qui minimisent l'utilité de l'agent. La valeur correspondante est calculée par :

\[\boxed{V_{\textrm{minimax}}(s)=\left\{\begin{array}{ll}\textrm{Utility}(s) & \textrm{IsEnd}(s)\\\underset{a\in\textrm{Actions}(s)}{\textrm{max}}V_{\textrm{minimax}}(\textrm{Succ}(s,a)) & \textrm{Player}(s)=\textrm{agent}\\\underset{a\in\textrm{Actions}(s)}{\textrm{min}}V_{\textrm{minimax}}(\textrm{Succ}(s,a)) & \textrm{Player}(s)=\textrm{opp}\end{array}\right.}\]

Remarque : on peut déduire $\pi_{\textrm{max}}$ et $\pi_{\textrm{min}}$ à partir de la valeur minimax $V_{\textrm{minimax}}$.

Minimax

Propriétés de minimax En notant $V$ la fonction de valeur, il y a 3 propriétés sur minimax qu'il faut avoir à l'esprit :

À la fin, on a la relation suivante :
\[\boxed{V(\pi_{\textrm{exptmax}},\pi_{\textrm{min}})\leqslant V(\pi_{\textrm{max}},\pi_{\textrm{min}})\leqslant V(\pi_{\textrm{max}},\pi)\leqslant V(\pi_{\textrm{exptmax}},\pi)}\]


Accélération de minimax

Fonction d'évaluation Une fonction d'évaluation estime de manière approximative la valeur $V_{\textrm{minimax}}(s)$ selon les paramètres du problème. Elle est notée $\textrm{Eval}(s)$.

Remarque : l'analogue de cette fonction utilisé dans les problèmes de recherche est $\textrm{FutureCost}(s)$.


Élagage alpha-bêta L'élagage alpha-bêta (en anglais alpha-beta pruning) est une méthode exacte d'optimisation employée sur l'algorithme de minimax et a pour but d'éviter l'exploration de parties inutiles de l'arbre de jeu. Pour ce faire, chaque joueur garde en mémoire la meilleure valeur qu'il puisse espérer (appelée $\alpha$ chez le joueur maximisant et $\beta$ chez le joueur minimisant). À une étape donnée, la condition $\beta < \alpha$ signifie que le chemin optimal ne peut pas passer par la branche actuelle puisque le joueur qui précédait avait une meilleure option à sa disposition.

Alpha beta pruning

TD learning L'apprentissage par différence de temps (en anglais temporal difference learning ou TD learning) est une méthode utilisée lorsque l'on ne connait pas les transitions/récompenses. La valeur et alors basée sur la politique d'exploration. Pour pouvoir l'utiliser, on a besoin de connaître les règles du jeu $\textrm{Succ}(s,a)$. Pour chaque $(s,a,r,s')$, la mise à jour des coefficients est faite de la manière suivante :

\[\boxed{w\longleftarrow w-\eta\big[V(s,w)-(r+\gamma V(s',w))\big]\nabla_wV(s,w)}\]

Jeux simultanés

Ce cas est opposé aux jeux joués tour à tour. Il n'y a pas d'ordre prédéterminé sur le mouvement du joueur.


Jeu simultané à un mouvement Soient deux joueurs $A$ et $B$, munis de possibles actions. On note $V(a,b)$ l'utilité de $A$ si $A$ choisit l'action $a$ et $B$ l'action $b$. $V$ est appelée la matrice de profit (en anglais payoff matrix).


Stratégies Il y a principalement deux types de stratégies :


Évaluation de jeu La valeur d'un jeu $V(\pi_A,\pi_B)$ quand le joueur $A$ suit $\pi_A$ et le joueur $B$ suit $\pi_B$ est telle que :

\[\boxed{V(\pi_A,\pi_B)=\sum_{a,b}\pi_A(a)\pi_B(b)V(a,b)}\]

Théorème minimax Soient $\pi_A$ et $\pi_B$ des stratégies mixtes. Pour chaque jeu à somme nulle à deux joueurs ayant un nombre fini d'actions, on a :

\[\boxed{\max_{\pi_A}\min_{\pi_B}V(\pi_A,\pi_B)=\min_{\pi_B}\max_{\pi_A}V(\pi_A,\pi_B)}\]

Jeux à somme non nulle

Matrice de profit On définit $V_p(\pi_A,\pi_B)$ l'utilité du joueur $p$.


Équilibre de Nash Un équilibre de Nash est défini par $(\pi_A^*,\pi_B^*)$ tel qu'aucun joueur n'a d'intérêt de changer sa stratégie. On a :

\[\boxed{\forall \pi_A, V_A(\pi_A^*,\pi_B^*)\geqslant V_A(\pi_A,\pi_B^*)}\quad\textrm{et}\quad\boxed{\forall \pi_B, V_B(\pi_A^*,\pi_B^*)\geqslant V_B(\pi_A^*,\pi_B)}\]

Remarque : dans un jeu à nombre de joueurs et d'actions finis, il existe au moins un équilibre de Nash.