Je voudrais tout d'abord remercier mon directeur de thèse, Gautier, sans qui rien n'aurait été possible, et à qui je dois beaucoup de ma formation scientifique actuelle.

J'aimerais également remercier tous les membres du jury qui ont accepté de lire et juger mon travail. Merci en particulier à Nadia, qui m'a beaucoup aidé dans cette période si particulière et qui m'a permis de soutenir dans les conditions que je souhaitais; et à Louis sans qui je n'aurais pas pu soutenir tellement il a été d'une aide immense à la fin de ma thèse.

Durant ces années de thèse, j'ai eu la chance de croiser beaucoup de monde au laboratoire. Merci à l'ancienne génération : Nico, Clément, Lucas (qui m'a tellement aidé), Lucile, Aurélie... Merci à Taume, Alex (meilleur co-bureau du monde), Dehia, et bien sûr Gricha qui m'a aidé tant dans le travail que dans les loisirs. Merci à Lucie qui a toujours été là dans les moments durs, et les bons aussi ! Et un immense merci à l'amour de ma vie, sans qui j'aurais craqué 1000 fois. On a affronté cette thèse à deux, puis à trois. On affrontera les autres épreuves de la vie ensemble, à trois ou à plus. Laura, voici notre manuscrit. | 11 cas 'avec escompte', c'est-à-dire le cas où il existe une probabilité non-nulle et constante d'atteindre l'état puits 0 en effectuant n'importe quelle action, Ye a été prouvé qu'il existait un algorithme de résolution fortement polynomial à facteur d'escompte fixé[109]. Il a prouvé par la suite que Policy Iteration (la version proposée par Howard [58]) avait une complexité fortement polynomiale [110]. Dans le cas 'sans escompte', cette question est toujours ouverte et (Howard) Policy Iteration a une complexité temporelle exponentielle [46]. Value Iteration a une complexité temporelle exponentielle et ce dans le cas discounted comme dans le cas undiscounted [42]. Même si l'on connait des algorithmes de résolution faiblement polynomiaux dans le cas undiscounted, la plupart des instances de MDP en général et de PCCS en particulier sont résolues grâce à Value Iteration et Policy Iteration quand elles sont de tailles moyennes. Pour de grandes instances, on préfèrera en général approcher les solutions optimales afin d'obtenir des solutions satisfaisantes en un temps raisonnable (en utilisant des méthodes de type programmation dynamique approchée par exemple [87])a. Match Play et JPCCS Un jeu de plus court chemin stochastique à deux joueurs est un jeu où deux joueurs, que nous appelons M IN et M AX, ont un but antagoniste. Un agent évolue dynamiquement dans un ensemble d'états partitionné en deux sous-ensembles : un ensemble d'états contrôlés par M IN et les autres contrôlés par M AX. En chaque état, le joueur qui le contrôle choisit une action disponible qui mènera l'agent dans un autre état selon une distribution de probabilités connue. Chaque action induit un coût et le but de M IN (resp. de M AX) est d'atteindre un état puits particulier tout en minimisant (resp. en maximisant) le coût moyen des actions qui l'y mène. Formellement, une instance de jeu de plus court chemin stochastique (JPCCS) est un tuple (S M IN , S M AX , A, J, P, c), où (S = S M IN ∪ S M AX , A, J, P, c) est une instance de plus court chemin stochastique et S M IN ∩ S M AX = {0}. S M IN est un ensemble d'états contrôlés par M IN et S M AX un ensemble d'états contrôlés par M AX. Comme on suppose que chaque action ne peut être effectuée que dans un seul état, on peut également partitionner A en A = A M IN ∪ A M AX avec A i = {a ∈ A|∃s ∈ S i , J(a, s) = 1} pour i ∈ {M IN, M AX}. Une politique déterministe et stationnaire pour M IN (resp. pour M AX) est une fonction Π M IN : S M IN → A M IN (resp. Π M AX : S M AX → A M AX ), telle que Π M IN (s) = a ⇒ J(a, s) = 1. Un couple de stratégie Π = (Π M IN , Π M AX ) définit une politique déterministe et stationnaire pour l'instance de PCCS (S = S M IN ∪ S M AX , A, J, P, c). On définit le coût du couple de stratégie Π = (Π M IN , Π M AX ) comme étant J Π , le coût de la stratégie Π pour l'instance du PCCS. Soit Σ M IN (resp. Σ M AX ) l'ensemble des stratégies déterministes et stationnaires pour M IN (resp. pour M AX). Considérons maintenant les instances de JPCCS (S M IN , S M AX , A, J, P, c) dont l'instance de PCCS associée (S = S M IN ∪ S M AX , A, J, P, c) est avec terminaison inévitable. Dans ce cas, on verra qu'il existe un équilibre de Nash, c'est-à-dire un couple de stratégies (Π M IN , Π M AX ) tel que pour tout i ∈ S \ {0}, pour tout Π M IN ∈ Σ M IN et tout

Introduction

Ces dernières années, le développement de 'super IAs' telles que AlphaGo [START_REF] Chen | The evolution of computing: Alphago[END_REF] pour le jeu de Go et de AlphaStar [START_REF] Arulkumaran | Alphastar: An evolutionary computation perspective[END_REF] pour des jeux de stratégies en ligne comme Starcraft II a grandement bouleversé les communautés de ces disciplines. Les stratégies préexistantes suivaient des schémas (souvent appelés metagames) qui ont été largement dépassés par les stratégies mises en place par le programme informatique, explorant des techniques jusqu'ici inconnues ou crues obsolètes. Ceci a permis aux joueurs de considérer d'autres aspects du jeu. Au Go, les joueurs, après avoir analysé les coups originaux de l'IA, ont depuis adopté certains de ces coups dans des parties professionnelles. À Starcraft, l'IA a surtout brillé par la gestion minutieuse de ses unités, même avec un nombre d'action par minute limité. L'outil informatique peut donc avoir un impact fort sur l'évolution du sport ou de l'e-sport de manière générale et sur l'optimisation de stratégies en particulier. L'optimisation de stratégies dans le sport est un grand enjeu à la fois pour l'amélioration des performances des sportifs, mais également pour l'analyse prédictive de résultats. Dans le premier cas, il s'agit d'utiliser des données relatives aux sportifs, aux terrains et à de potentiels adversaires afin de déterminer la manière optimale de jouer en tenant compte de tous ces aspects. On peut ainsi déterminer quels aspects du jeu il serait intéressant d'améliorer en priorité afin d'avoir le plus grand impact positif sur les performances du ou des sportifs. Dans le deuxième cas, il s'agit de simuler le jeu des sportifs afin d'obtenir des éléments statistiques sur les résultats possibles (distribution de scores, probabilités de gain...).

Dans ce manuscrit, nous nous sommes concentrés sur le Golf, et ce pour deux principaux aspects. D'abord un golfeur se confronte au 'terrain' plus qu'aux autres golfeurs : les interactions directes entre les joueurs sont très limitées. Ainsi, la stratégie de chaque joueur peut se déterminer indépendamment des actions des autres joueurs (sous certaines hypothèses que nous détaillerons plus tard).

De plus, nous avons eu accès à une base de données, Shotlink [START_REF] Pga Tour | Shotlink intelligence program[END_REF], qui nous donne une grande quantité d'informations sur les joueurs professionnels. Ces données sont indispensables pour la création de profils de joueurs et leurs accès a été déterminant dans le choix de notre application.

Il est cependant possible d'adapter les modèles que nous avons développé dans d'autres disciplines sportives et ce même quand deux équipes sont impliquées. Les 8| Introduction travaux de Hoffmeister et Rambau [START_REF] Hoffmeister | Strategy optimization in sports : A two-scale approach via markov decision problems[END_REF] [START_REF] Hoffmeister | Sport strategy optimization in beach volleyball? how to bound direct point probabilities dependent on individual skills[END_REF] utilisent le même type de modèles et permettent l'optimisation de stratégies des équipes de Beach Volley ou de Football.

Le Golf est un sport dans lequel des joueurs s'affrontent sur un parcours composé dix-huit trous. Chaque trou est composé de plusieurs éléments, dont une zone de départ, ou tee, une zone d'arrivée, ou green, où la pelouse est très rase avec en son sein un trou marqué par un drapeau (qu'on nommera dans la suite 'drapeau' pour éviter toute ambiguïté). Une zone d'herbe rase (mais moins que le green) appelée fairway relie le tee et le green. Entourant le fairway, on trouve une zone d'herbe plus haute, ou rough. On peut trouver également plusieurs obstacles : de l'eau, des zones de sables appelées bunkers et des arbres. Le golfeur doit acheminer la balle depuis le tee vers le drapeau en utilisant un club, parmi les quatorze clubs qu'il possède et dont il a fait la sélection. À chaque fois que le golfeur utilise un de ses clubs pour frapper la balle, son score (initialement de zéro sur le tee) est incrémenté de un en situation normale, ou de deux si il reçoit une pénalité. Une pénalité est par exemple octroyée à un joueur si la balle tombe dans l'eau ou en dehors des limites du terrain. Si la balle tombe dans l'eau, elle est alors replacée à la lisière de celle-ci ; et si elle sort des limites du terrain, elle est replacée à l'endroit où elle a été tirée. Le but du jeu est que la balle arrive au drapeau en un nombre minimum de coups. D'un point de vue compétitif, il y a principalement deux types de compétitions qui diffèrent selon la façon de déterminer le vainqueur sur les dix-huit trous (la taille réglementaire des parcours de golf). Lors d'une compétition Stroke Play, chaque joueur additionne les scores qu'il a fait sur les dix-huit trous et le vainqueur est celui qui a obtenu le score minimum sur l'ensemble du parcours (ou sur plusieurs parcours : les tournois professionnels se jouent sur quatre "tours"). Lors d'une compétition Match Play, seulement deux joueurs s'affrontent. À la fin de chaque trou, les deux joueurs comparent leur score. Celui qui a obtenu le plus petit score marque un point. En cas d'égalité, chaque joueur marque un demi point. À la fin des dix-huit trous, le joueur ayant le plus grand nombre de points est déclaré vainqueur. Les enjeux pour le golfeur sont différents dans les deux modes : en Stroke Play, le score d'un joueur sur un trou a un impact direct sur le score final, alors qu'en Match Play, l'enjeu (sur chaque trou) est uniquement de faire un meilleur score que son adversaire.

On s'intéresse dans cette thèse à l'optimisation de stratégie au Golf. Sous certaines hypothèses que nous développerons ultérieurement, il est possible de modéliser le Stroke Play comme un problème de Plus Court Chemin Stochastique (PCCS) et le Match Play comme un jeu de plus court chemin stochastique à deux joueurs.

Stroke Play et Plus Court Chemin Stochastique

Le plus court chemin stochastique (PCCS) est un processus de Markov (MDP) particulier dans lequel un agent évolue dynamiquement sur un ensemble fini d'états. À chaque | 9 période de temps, l'agent choisit une action parmi un ensemble d'actions disponibles qui le mènera aléatoirement dans un autre état suivant une distribution de probabilités connue. Chaque action induit un coût et le but de l'agent est d'atteindre à coup sûr un état puits particulier tout en minimisant le coût moyen des actions qui l'y mènent.

Formellement, une instance de plus court chemin stochastique est un tuple I = (S, A, J, P, c), où S = {0, 1, .., n} est un ensemble fini de n + 1 états, A = {0, 1, .., m} est un ensemble fini de m + 1 actions, J est une matrice en 0/1 de m lignes et n colonnes. L'élément J a,s = 1 si l'action a ∈ {1, .., m} est disponible en l'état s ∈ {1, .., n} et 0 sinon. On suppose sans perte de généralité qu'on peut partitionner A en A = ∪ s∈S A(s), où A(s) est l'ensemble des actions disponibles en s ∈ S, ce qui signifie qu'une action n'est disponible qu'en un unique état 1 . P est une matrice sous-stochastique (la somme des éléments d'une colonne est au plus 1) de m lignes et n colonnes appelée matrice de transition. Un élément P a,s = p(s|a) est la probabilité d'atteindre l'état s ∈ {1, .., n} sachant qu'on a effectué l'action a ∈ {1, .., m}. c est un vecteur de m éléments et c(a) définit le coût de l'action a ∈ {1, .., m}. L'état 0 est un état puits particulier, dans lequel la seule action disponible est l'action 0 : A(0) = {0} et l'action 0 mène en l'état 0 avec probabilité de un.

Une politique stationnaire (on définira une notion de politique plus générale dans cette thèse, notamment dans le chapitre 1) est une fonction Π qui associe une distribution de probabilités sur les actions à chaque état. On peut représenter une politique stationnaire par une matrice stochastique (la somme des éléments d'une colonne est exactement égale à 1) de n lignes et m colonnes qui vérifie Π(s, a) > 0 ⇒ J a,s = 1. Si Π est de plus une matrice en 0/1, la politique est dite déterministe. Une politique stationnaire est dite propre si 1 T (P T Π T ) n .e i < 1 (e i est un vecteur dont les n éléments valent 0, sauf le i eme qui vaut 1). Cela signifie qu'à partir de n'importe quel état i, la probabilité d'atteindre l'état puits 0 après n périodes de temps est strictement positive. Si pour une instance de PCCS toutes les politiques sont propres, on dira qu'il s'agit d'un plus court chemin stochastique avec terminaison inévitable. En effet dans ce cas, n'importe quelle stratégie mène au puits avec une probabilité de un.

On peut constater que choisir une politique propre et stationnaire définit une chaîne de Markov absorbante (voir [START_REF] Norris | Markov chains. Cambridge series in statistical and probabilistic mathematics[END_REF] pour plus de détails sur les chaînes de Markov), dont la matrice de transition est Q T = P T Π T . En particulier, (I -Q) est inversible et (I -Q) -1 = lim K→+∞ K k=0 Q k . On peut donc définir pour chaque i ∈ S \ {0},

J Π = lim K→+∞ K k=0 c T Π T (I -Q) -1 e i
et J * (i) = min{J Π (i) : Π propre et stationnaire}. Bertsekas et Tsitsiklis [START_REF] Bertsekas | An analysis of stochastic shortest path problems[END_REF] donne la définition suivante d'une politique optimale : une politique propre et stationnaire Π * est dite optimale si pour tout état i ∈ S \ {0}, J Π * = J * (i). Le problème qui consiste à trouver une telle politique s'appelle le problème du plus court chemin stochastique.

Le problème de PPCS apparaît naturellement lorsqu'on s'intéresse à l'optimisation de la stratégie de jeu d'un golfeur. En effet, lorsqu'un golfeur joue en Stroke Play, 10| Introduction on peut raisonnablement supposer qu'il joue chaque trou indépendamment, sans tenir compte des autres joueurs et qu'il essaye de minimiser son score moyen (puisqu'il réitère le processus 18 fois). Cette hypothèse est discutable, surtout quand on arrive à la fin du parcours (un joueur aura peut-être tendance à prendre plus de risques si il est en retard par rapport aux autres joueurs sur les derniers trous). Cependant, si on considère des joueurs professionnels, ce que nous allons faire dans la suite du document, le niveau des golfeurs est assez uniforme pour qu'il ne soit pas rentable de prendre de tels risques (ou vraiment uniquement dans des situations extrêmes). Si on fait de telles hypothèses, on peut donc considérer qu'en Stroke Play, un joueur ne joue pas contre les autres joueurs, mais contre "le parcours". Optimiser la stratégie d'un golfeur en Stroke Play peut dans ce cadre se modéliser comme un plus court chemin stochastique. En effet, si on définit des états comme étant les endroits possibles où la balle peut se trouver, des actions comme les coups que peut effectuer le golfeur dont les coûts valent 1 (ou 2 si pénalité il y a) et une matrice de transition qui décrit où la balle peut atterrir pour chaque action du golfeur, en prenant en compte à la fois des éléments physiques (obstacles des trous, conditions climatiques, physique de la balle de golf...) et le niveau du joueur en lui même ; alors résoudre l'instance de plus court chemin stochastique ainsi définie donnerait la stratégie optimale que le joueur devrait adopter afin de minimiser son score moyen. De plus, si on suppose qu'un joueur professionnel joue sa stratégie optimale, nous pouvons, en simulant la stratégie optimale calculée, créer un jumeau numérique du joueur qui aurait les mêmes caractéristiques que le joueur. Ce jumeau peut être utilisé pour de la prévision de score, mais aussi pour détecter les points de jeu critiques à améliorer afin d'avoir le meilleur impact sur le score final.

Le plus court chemin stochastique est un problème intéressant à étudier en soit avec de nombreuses applications. Dans la robotique : dans [START_REF] Bast | Route planning in transportation networks[END_REF], les auteurs décrivent comment manoeuvrer un véhicule dans eaux agitées mais également dans la recherche opérationnelle en général [START_REF] White | A survey of applications of markov decision processes[END_REF], en finance de manière générale [START_REF] Bäuerle | Markov Decision Processes with Applications to Finance: Markov Decision Processes with Applications to Finance[END_REF] et dans des modèles d'établissement de prix [START_REF] Merton | An intertemporal capital asset pricing model[END_REF] en particulier ou encore en apprentissage automatique [START_REF] Sutton | Introduction to Reinforcement Learning[END_REF]. Il a été introduit pour la première fois par Eaton et Zadeh en 1962 [START_REF] Eaton | Optimal pursuit strategies in discrete-state probabilistic systems[END_REF], puis très largement étudié par Bertsekas et Tsitsiklis [START_REF] Bertsekas | An analysis of stochastic shortest path problems[END_REF]. On connait à ce jour trois principales manières de résoudre exactement le problème (qui sont en fait des méthodes de résolution des processus de Markov) : Value Iteration, Policy Iteration et la programmation linéaire. Value Iteration est un algorithme itératif qui a pour principe d'approcher J * grâce à la programmation dynamique [START_REF] Bellman | Dynamic Programming[END_REF][START_REF] Howard | Dynamic programming and Markov processes[END_REF]. Policy Iteration est également un algorithme itératif qui nécessite une stratégie propre initiale et qui itère de stratégie propre en stratégie propre jusqu'à trouver une stratégie optimale [START_REF] Manne | Linear programming and sequential decisions[END_REF][START_REF] Denardo | On Linear Programming in a Markov Decision Problem[END_REF]. Le problème du plus court chemin stochastique peut également être formulé comme un programme linéaire et peut donc, comme la plupart des processus de Markov, être résolu en temps faiblement polynomial [START_REF] Manne | Linear programming and sequential decisions[END_REF][START_REF] Epenoux | A probabilistic production and inventory problem[END_REF][START_REF] Denardo | On Linear Programming in a Markov Decision Problem[END_REF][START_REF] Hordijk | Linear programming and markov decision chains[END_REF][START_REF] Hernández-Lerma | The linear programming approach[END_REF]. On pourra noter que Policy Iteration peut être interprété comme un algorithme du simplexe sur un tel programme linéaire. L'existence d'algorithmes de résolution fortement polynomiaux pour résoudre le PCCS (polynomial en le nombre d'états et d'actions), et plus généralement les processus de Markov, est une question ouverte très importante dans le domaine. Dans le

12| Introduction Π M AX ∈ Σ M AX , J (Π M IN ,Π M AX ) ≥ J (Π M IN ,Π M AX ) ≥ J (Π M IN ,Π M AX )
. Il en résulte du théorème minimax de Von Neumann que, pour tout i ∈ S \ {0}:

J (Π M IN ,Π M AX ) (i) = min Π M IN ∈Σ M IN max Π M AX ∈Σ M AX J (Π M IN ,Π M AX ) (i) = max Π M AX ∈Σ M AX min Π M IN ∈Σ M IN J (Π M IN ,Π M AX ) (i)
Un problème de jeux de plus court chemin stochastique consiste à trouver un tel équilibre de Nash.

Lors d'une compétition en Match Play, deux joueurs s'affrontent sur chaque trou du parcours afin de gagner le point lié à ce trou (ou de le partager en cas d'égalité). Le joueur qui commence est celui qui a gagné le trou précédent (et pour le premier trou il est tiré au hasard) et c'est toujours le joueur dont la balle est la plus loin du drapeau qui joue. Quand un joueur joue, les informations dont il dispose sont la position de sa balle, la position de la balle de son adversaire et la différence de [START_REF]Shotlink intelligence program[END_REF]). Si δ > D, alors le nouvel état est l'état puits (définit plus bas), et le coût engendré par cette transition est de 1. De même, quand M AX joue depuis s = (p M IN , p M AX , δ), la balle atterrit en p M AX et le nouvel état après son coup est s = (p M IN , p M AX , δ ) avec δ = δ -1 ou δ -2 si M AX a obtenu une pénalité (de même, si δ < -D, alors le nouvel état est l'état puits et le coût engendré est de -1). Ces transitions n'occasionnent aucun coût (à part quand l'état puits est atteint). On définit un état 'drapeau' comme un état du type s f lag = (p f lag , p f lag , δ f lag ) où p f lag correspond à la position du drapeau (il y a donc 2D + 1 états drapeau). Le jeu s'arrête quand un état drapeau s f lag est atteint. M IN gagne le point si δ f lag < 0, M AX le gagne si δ f lag > 0 et M IN et M AX gagnent chacun 0, 5 point si δ f lag = 0. Pour faire correspondre parfaitement le Match Play avec | 13 une instance de JPCCS, on définit un état puits artificiel qui est atteint à partir des états drapeaux de manière sûre et avec un coût de 1 si δ f lag > 0, de -1 si δ f lag < 0 et de 0 si δ f lag = 0 (ainsi que si la différence de score est inférieure strictement à -D ou supérieure strictement à D, comme on l'a vu plus haut). Le coût d'un couple de politique Π = (Π M IN , Π M AX ) est l'espérance de gain dans [-1, 1] du joueur M AX quand M IN suit la politique Π M IN et M AX suit Π M AX (c'est aussi l'opposé de l'espérance de gain de M IN ). Le but de M IN (resp. M AX) est de minimiser (resp. maximiser) ce coût. La notion d'espérance a du sens dans la mesure où les joueurs jouent dix-huit trous. Évidemment, plus on approche de la fin plus l'hypothèse est contestable. On notera que les instances sont à terminaison inévitable car les deux joueurs peuvent terminer indépendamment. Il est donc possible de modéliser une compétition en Match Play comme un problème de JPCCS avec terminaison inévitable. Résoudre une telle instance à l'optimal donne ainsi un couple de stratégies (Π * M IN , Π * M AX ) qui forme un équilibre de Nash.

Les jeux stochastiques ont été introduits pour la première fois par Shapley en 1953. Ce problème a de nombreuses applications, notamment en sécurité de réseaux [START_REF] Nguyen | Stochastic games for security in networks with interdependent nodes[END_REF], en économie [START_REF] Nowak | On stochastic games in economics[END_REF] [START_REF] Jaśkiewicz | Stochastic games with unbounded payoffs: Applications to robust control in economics[END_REF], et en robotique [START_REF] Schölkopf | Multi-Robot Negotiation: Approximating the Set of Subgame Perfect Equilibria in General-Sum Stochastic Games[END_REF] entre autres choses. On ne connait actuellement aucun algorithme de complexité temporelle polynomiale qui résout exactement les JPCCS. L'existence d'un tel algorithme est un problème non-résolu de longue date [START_REF] Condon | The complexity of stochastic games[END_REF]. L'algorithme utilisé en pratique est Strategy Iteration. Cet algorithme itératif consiste en l'application alternative de Policy Iteration pour un joueur, en fixant la stratégie de l'adversaire jusqu'à obtenir un équilibre de Nash. Cet algorithme est de complexité temporelle exponentielle dans le pire des cas (qui résulte de la complexité exponentielle de Policy Iteration) [START_REF] Condon | On algorithms for simple stochastic games[END_REF].

Base de données Shotlink

Organisation du document

Dans le premier chapitre, nous étudions le problème du plus court chemin stochastique d'un point de vue théorique. Nous étendons le cadre d'étude de Bertsekas et Tsitsiklis [START_REF] Bertsekas | An analysis of stochastic shortest path problems[END_REF] puis de Bertsekas et Yu [START_REF] Bertsekas | Stochastic shortest path problems under weak conditions[END_REF] en adoptant un point de vue polyédral sur le problème. Nous prouvons que dans ce nouveau cadre, les algorithmes classiques de résolution (Value Iteration, Policy Iteration) convergent même en présence de cycles de transition (généralisation des cycles dans le cas stochastique) de coûts nuls. Nous introduisons également un nouvel algorithme de résolution. Ce chapitre a fait l'objet d'une publication dans le journal européen de recherche opérationnel (EJOR) [START_REF] Guillot | The stochastic shortest path problem: A polyhedral combinatorics perspective[END_REF].

Dans le deuxième chapitre, nous nous intéressons à la modélisation de l'optimisation des stratégies de Golf en plus court chemin stochastique, ainsi qu'à des méthodes de prédiction de score. Nous présentons notre modèle, ainsi que des résultats numériques et leur validation statistique. Les travaux correspondants ont été présentés dans des conférences internationales [START_REF] Matthieu Guillot | Golf strategy optimization for professional golfers's performances estimation on the pga tour[END_REF] [START_REF] Matthieu Guillot | Golf strategy optimization for professional golfers's performances estimation on the pga tour[END_REF], et un article de journal est en préparation.

Dans le troisième et dernier chapitre, nous nous intéressons aux jeux stochastiques et plus particulièrement aux formulations programmation linéaire de ces jeux. Nous présentons une formulation programmation linéaire en nombres entiers pour les JPCCS. Nous étudions également deux cas particuliers des JPCCS : les Jeux Stochastiques Simples et le problème du Plus Court Chemin Robuste. Les travaux de ce chapitre n'ont pas encore été présentés en conférence ou en journal, mais ont vocation à l'être.

Prérequis théoriques

Dans cette section, nous introduisons les prérequis théoriques nécessaires à la bonne compréhension de cette thèse. Nous y faisons référence tout au long de celle-ci. Nous introduisons également ici les notations que nous allons utiliser dans le document. La plupart des notations sont tirées de [START_REF] Hansen | Worst-case Analysis of Strategy Iteration and the Simplex Method[END_REF]. Nous invitons les lecteurs à s'y référer pour plus de détails et pour accéder aux preuves manquantes.

Programmation Linéaire

La programmation linéaire est un cas particulier de programmation mathématique. Un programme mathématique est une modélisation d'un problème d'optimisation de la forme :

Minimiser ou Maximiser f (x) Sachant que g i (x)      ≥ ≤ =      0 ∀i ∈ {1, .., m}
x ∈ X (P rogM ath) | 15 où m ∈ N, x ∈ R n (n ∈ N) sont les variables, X est le domaine de définition de x, f : R n → R est la fonction objectif et pour tout i ∈ {1, .., m}, g i : R n → R est une fonction de contrainte.

Dans le cas où f et (g i ) i∈{1,..,m} sont des fonctions linéaires et X = R n , on parle alors de programmation linéaire. Il s'agit donc de programmes mathématiques du type :

Min/Max n j=1 c j x j Sachant que n j=1 a ij x j -b i      ≥ ≤ =      0 ∀i ∈ {1, .., m} x ∈ R n (P rogLin) où pour tout i ∈ {1, .., m} et tout j ∈ {1, .., n}, c j , a ij , b i ∈ R. De manière plus condensée, on utilisera une notation matricielle en posant A = (a ij ) 1≤i≤m,1≤j≤n , c = (c j ) j∈{1,..,n} et b = (b i ) i∈{1,..,m} . Min/Max c T x Sachant que Ax -b      ≥ ≤ =      0 x ∈ R n (P rogLin)
En notant que minimiser une fonction est équivalent à maximiser son opposé et en transformant les inégalités A i x ≥ b i en -A i x ≤ -b i , où A i est la i eme ligne de A, on peut supposer sans perte de généralité que n'importe quel programme linéaire peut s'écrire sous la forme suivante (appelée forme canonique) :

Max c T x Sachant que Ax ≤ b x ≥ 0 (P Can )
Definition 1 Un polyèdre convexe est l'ensemble des solutions d'un système fini d'inégalités linéaires.

Definition 2

Soit x ∈ R n et (P ) un programme linéaire sous forme canonique. On dit que x est une solution réalisable de (P ) si et seulement si Ax ≤ b et x ≥ 0. On nomme P = {x ∈ R n |x ≥ 0, Ax ≤ b} l'ensemble des solutions réalisables de (P ). Par définition, P est un polyèdre convexe. On appellera valeur de x la valeur de la fonction objectif appliquée à x, i.e. c T x.

Definition 3

Soit x * ∈ R n et (P ) un programme linéaire sous forme canonique. On dit que x * est une solution optimale de (P ) si et seulement si x * est une solution réalisable et que pour tout x ∈ P , c T x * ≥ c T x. On nommera valeur optimale de (P ) la valeur de x * , i.e. c T x * .

16| Introduction

Definition 4

Soit (P ) un programme linéaire sous forme canonique.

c T x Sachant que Ax = b x ≥ 0 (P Stand ) avec c ∈ R n , x ∈ R n , et A = (a ij ) 1≤i≤m,1≤j≤n et b ∈ R m
Sans perte de généralité, on peut supposer que dans un problème sous forme standard, les colonnes de A sont linéairement indépendantes (si ce n'est pas le cas, il y a des contraintes redondantes ou l'ensemble des contraintes est vide). On supposera donc dans la suite que pour un programme linéaire sous forme standard, A est de rang plein, i.e. rang(A) = m.

On remarquera qu'à tout programme linéaire sous forme canonique, on peut associer un programme linéaire sous forme standard. Soit (P ) un programme linéaire sous forme canonique:

Max c T x Sachant que Ax ≤ b x ≥ 0 (P ) avec c ∈ R n , x ∈ R n , et A = (a ij ) 1≤i≤m,1≤j≤n et b ∈ R m . On pose n = n + m et on définit x ∈ R n , c ∈ R n , Ã = (ã ij ) 1≤i≤n,1≤j≤m et b ∈ R m
tels que: On peut démontrer facilement que

• x = (x 1 , .., x n , , .., b 1 -A 1 x, .., b m -A m x) • c = (c 1 , .., c n , 0, .., 0) • Ã = (A|I m ) • b = b | 17 avec I m la matrice identité de taille m et (A|I m ) =          
• x est une solution réalisable de (P ) si et seulement si x est une solution réalisable de ( P )

• x est une solution optimale de (P ) si et seulement si x est une solution optimale de ( P )

On note que à 'contient' la matrice identité I m , donc à est de rang plein. Dans toute la suite, on considèrera que les programmes linéaires en forme standard possèdent n variables et m contraintes.

Definition 8

Soit (P ) un programme linéaire sous forme standard. On supposera sans perte de généralité que A est de rang plein (comme expliqué plus haut). On dit que B ⊆ {1, .., n} est une base de (P ) si et seulement si |B| = m et A B = (a ij ) 1≤i≤m,j∈B est inversible. Pour une base B, on appelle N = {1, .., n} \ B.

Les variables x i avec i ∈ B sont appelées les variables de base et les variables x i avec i ∈ N sont appelées variables hors-base.

Definition 9

Soit (P ) un programme linéaire sous forme standard et B une base de (P ). On définit

A B = (a ij ) 1≤i≤m,j∈B , A N = (a ij ) 1≤i≤m,j∈N , c B = (c j ) j∈B , c N = (c j ) j∈N , x B = (x j ) j∈B et x N = (x j ) j∈N .

Definition 10

Soit (P ) un programme linéaire sous forme standard et B une base. (P ) peut alors se réécrire :

Max c T B x B + c T N x N Sachant que x B = A -1 B b -A -1 B A N x N x B , x N ≥ 0 (P B Stand ) avec x B ∈ R m et x N ∈ R n-m (

Proposition 11

Soit (P ) un programme linéaire sous forme standard et x ∈ R n . x est un sommet de P si et seulement si x est une solution de base de (P ).

Méthodes de résolution et complexité

Il existe trois principaux types d'algorithmes permettant de résoudre de manière exacte les programmes linéaires : les méthodes d'ellipsoïdes [START_REF] Khachiyan | A polynomial algorithm in linear programming[END_REF], les méthodes de points intérieurs [START_REF] Karmarkar | A new polynomial-time algorithm for linear programming[END_REF] et le simplexe que nous allons détailler car il est au coeur de certaines méthodes de résolution des plus courts chemins stochastiques et de variantes de ceux-ci.

Les méthodes de points intérieurs et d'ellipsoïdes sont des méthodes polynomiales [START_REF] Khachiyan | A polynomial algorithm in linear programming[END_REF][START_REF] Karmarkar | A new polynomial-time algorithm for linear programming[END_REF], mais ne sont pas fortement polynomiales (polynomial en le nombre de variables et de contraintes). Pour plus de détails sur ces méthodes, nous invitons les lecteurs à lire [START_REF] Seese | a. schrijver: Geometric algorithms and combinatorial optimization[END_REF][START_REF] Nesterov | Interior-Point Polynomial Algorithms in Convex Programming[END_REF][START_REF] Ye | Interior Point Algorithms: Theory and Analysis[END_REF]. La résolution des programmes linéaires est donc un problème qui peut être résolu en temps (faiblement) polynomial. Cependant, un des algorithmes les plus utilisés en pratique n'est lui pas polynomial (comme nous allons le voir plus loin), il s'agit de l'algorithme du simplexe.

L'algorithme du simplexe a été créé par Dantzig en 1947 (et publié en 1951 [START_REF] Dantzig | Maximization of a linear function of variables subject to linear inequalities[END_REF]). L'idée générale de cet algorithme est de se déplacer de sommet en sommet du polyèdre des solutions réalisables afin de trouver une solution optimale s'il en existe. Cependant, il peut arriver que l'on reste sur le même sommet si plus de 3 contraintes concourent en un même point. On dit alors que (P ) est dégénéré. Cela peut engendrer des difficultés au niveau de l'exécution de l'algorithme du simplexe et leur résolution est un pan important de la recherche en programmation linéaire [START_REF] Charnes | Optimality and degeneracy in linear programming[END_REF][START_REF] Wolfe | A technique for resolving degeneracy in linear programming[END_REF].

Definition 12

Soit (P ) un programme linéaire sous forme standard et B une base de (P ). Le vecteur de coûts réduits lié à la base B est définit par :

cB = c -c B A -1
B A Pour une variable x i , i ∈ {1, .., n}, le coût réduit de x i est donc (c B ) i . On notera que pour toute variable de base x i , on a (c B ) i = 0.

Proposition 13

Soit (P ) un programme linéaire sous forme standard, B une base de (P ) et xB la solution de base associée à B. Soit x ∈ R n une solution réalisable de (P ). On a :

c T x = c T B xB + (c B ) T x
Ainsi, si on dispose d'une base réalisable, comme on a (c

B ) T x = (c B ) T B x B +(c B ) T N x N = (c B ) T N
x N , un programme linéaire (P ) peut se réécrire :

| 19 Max c T B xB + (c B ) T N x N Sachant que x B = A -1 B b -A -1 B A N x N x B , x N ≥ 0 (P B Stand )
On sait par définition que x, la solution de base associée à B, est une solution réalisable, car B est une base réalisable. On considère cette solution comme la solution courante.

On constate ensuite que dans la fonction objectif, c T B xB est une constante. Il convient donc de maximiser (c B ) T N x N . On peut interpréter (c B ) i comme le gain relatif pour la fonction objectif si on augmente la valeur de la variable x i d'une unité.

Si pour tout i ∈ N , (c B ) i ≤ 0, alors comme x N ≥ 0, x est optimale car elle est réalisable et que xN = 0. En effet, toute autre solution x ∈ R n avec x i = 0 pour un certain i ∈ N aura une valeur de fonction objectif plus faible.

Sinon, si il existe j ∈ N tel que (c B ) j > 0, alors on aura tendance à vouloir augmenter la valeur de x j afin d'obtenir une valeur plus grande que celle de la solution courante (laissant les autres valeurs de x j égales à 0 pour tout j ∈ N \ {j}). Pour tout i ∈ B, on a :

x i = (A -1 B b) i -(A -1 B A j x j ) i
Sachant qu'on veut assurer la réalisabilité du problème, on veut s'assurer que x i ≥ 0 pour tout i ∈ B. Si on a (A -1 B A j x j ) ≤ 0, alors le problème est non borné, car on pourra augmenter indéfiniment la valeur de x j sans compromettre la réalisabilité de la solution. Sinon, on définit :

i * ∈ argmin i∈B,(A -1 B A j x j ) i >0 (A -1 B b) i (A -1 B A j x j ) i
On nomme x j la variable entrante et x * i la variable sortante. On définit une nouvelle base B = B ∪ {j} \ {i * } (on a donc N = N ∪ {i * } \ {j}). D'après la définition du coût réduit, on a bien c T xB ≥ c T xB . L'algorithme du simplexe est l'algorithme itératif qui consiste à répéter cette étape jusqu'à ce que tous les coûts réduits des variables hors-base soient négatifs : ). C'est le cas de la règle de Bland.

Algorithm 1 L'algorithme du Simplexe Input : A, b, c et une base réalisable B while ∃j ∈ N , (c B ) j > 0 do Choisir un tel j if ∀i ∈ B, (A -1 B A j x j ) i ≤ 0 then return Problème non-borné else Choisir i * ∈ argmin i∈B,(A -1 B A j x j ) i >0 (A -1 B b) i (A -1 B A j x j ) i B = B ∪ {j} \ {i
• Règle de Bland : on définit au préalable un ordre sur les variables et quand il y a plusieurs variables de coût réduit positif, la variable entrante choisie est celle de plus petit rang dans cet ordre. Cette règle permet de ne pas 'boucler' sur un sous-ensemble de bases [START_REF] Bland | New finite pivoting rules for the simplex method[END_REF], mais le nombre d'itération est exponentiel dans le pire cas [START_REF] Avis | Notes on Bland's pivoting rule[END_REF].

• Règle de Dantzig : on définit la variable entrante comme celle qui a le plus grand coût réduit. Cette règle, bien que plus naturelle, peut ne pas faire terminer l'algorithme du simplexe (on cycle sur un sous-ensemble de bases) [START_REF] Klee | How good is the simplex algorithm[END_REF].

À l'heure actuelle, on ne connait aucune règle de pivot qui garantit une complexité temporelle polynomiale (toutes les règles de pivot connues nécessitent de parcourir un nombre exponentiel de solutions de base).

Dualité

Considérons un programme linéaire sous forme canonique (P ) :

Max c T x Sachant que Ax ≤ b x ≥ 0 (P )
Considérons que (P ) est réalisable. Il est clair que pour toute solution réalisable

x r ∈ R n , c T x r est une borne inférieure de la valeur optimale de (P ). Il est légitime de

| 21

se poser la question de l'existence d'une borne supérieure sur la valeur d'un programme linéaire. C'est la dualité qui va nous donner les outils permettant de trouver une telle borne.

Supposons que pour tout y ∈ (R + ) m on ait A T y ≥ c. Dans ce cas, pour tout x ∈ R n solution réalisable de (P ), on a :

b T y ≥ (Ax) T y = x T A T y ≥ x T c = c T x
Ainsi, si A T y ≥ c, alors y T b est une borne supérieure sur la valeur de n'importe quelle solution réalisable, donc également sur la valeur optimale de (P ). On a ainsi potentiellement une infinité de bornes supérieures disponibles. On voudrait connaître la meilleure borne possible, c'est-à-dire la plus petite d'entre elles.

Min b T y Sachant que A T y ≥ c y ≥ 0 (D)
(D) est un programme linéaire appelé le programme linéaire dual de (P ) ou plus simplement le dual de (P ). On appellera (P ) le primal de (D). Une solution réalisable de (P ) est appelée une solution primal-réalisable et une solution réalisable de (D) est appelée une solution dual-réalisable. On peut noter que le dual de (D) est (P ).

On cite trois importants théorèmes : le théorème de la dualité faible, de la dualité forte, et le théorème des écarts complémentaires (pour plus de détails voir par exemple [START_REF] Papadimitriou | Combinatorial optimization: Algorithms and complexity[END_REF]).

22| Introduction ii (A T y * -c) T x * = 0 iii (Ax * -b) T y * = 0
Programmation Linéaire en Nombres Entiers Soit (P ) un programme linéaire sous forme canonique. On impose maintenant que les variables ne soient plus dans R mais dans Z. Les méthodes de résolutions précédentes ne fonctionnent plus. Les méthodes de points intérieurs, les méthodes d'ellipsoïdes ainsi que l'algorithme du simplexe ne donnent pas des solutions entières dans le cas général. Cependant, on peut s'intéresser à l'enveloppe convexe des solutions entières 1). Ce polyèdre est difficile à caractériser en cas général. Si malgré tout on arrive à bien caractériser ce polyèdre, des méthodes de type ellipsoïde peuvent donner des résultats intéressants, comme dans le cas du polyèdre des couplages dans un graphe [START_REF] Grötschel | The ellipsoid method and its consequences in combinatorial optimization[END_REF]. D'autre part, il existe des cas particulier dans lequel on a P = P I . C'est notamment le cas si la matrice A est totalement unimodulaire (TU).

P I = conv({x ∈ Z n |Ax ≤ b}) (voir figure

Definition 17

Une matrice A est dite totalement unimodulaire si le déterminant de toute sous-matrice carrée de A vaut -1, 0 ou 1 (en particulier tous les coefficient de A sont dans {-1, 0, 1}).

Dans les formulation programmation linéaire des plus courts chemins, ou plus généralement pour les flots, la matrice définissant les contraintes est totalement unimodulaire [START_REF] Ford | Network flow theory[END_REF]. Lorsque P = P I , l'algorithme du simplexe donne une solution optimale entière, puisque les sommets de P ont des coordonnées entières.

Cependant dans le cas général, la programmation linéaire en nombre entier est un problème NP-complet [START_REF] Karp | Reducibility among Combinatorial Problems[END_REF]. Il existe cependant des algorithmes de résolution qui

| 23

s'exécutent en temps exponentiel dans le pire cas : on citera les algorithmes de type Cutting plane [START_REF] Kelley | The cutting-plane method for solving convex programs[END_REF], Branch & Bound [START_REF] Papadimitriou | Combinatorial optimization: Algorithms and complexity[END_REF], et Branch & Cut [START_REF] Padberg | A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems[END_REF].

Le Problème du Plus Court Chemin Déterministe

Definition 18

Un graphe orienté est un couple G = (V, A) où V = {s 1 , s 2 , .., s n } est un ensemble fini de n sommets et A ⊆ V × V est un ensemble d'arcs. De plus, on dit que G est pondéré s'il existe une application c : A -→ R appelée fonction de coûts.

Definition 19 Soit G = (V, A) un graphe orienté. On définit pour tout v ∈ V , δ + (v) = {a ∈ A|∃v ∈ V, a = (v, v )}. On définit également pour tout v ∈ V N (v) = {v ∈ V |∃a = (v, v ) ∈ A} l'ensemble des voisins de v.

Definition 20

Soit G = (V, A) un graphe orienté, c une fonction de coûts et s, t ∈ V . Un chemin de s à t ou (s, t)-chemin est une suite alternée de sommets et d'

arcs p = (v 0 a 1 v 1 a 2 ...a k , v k ) telle que v 0 = s, v k = t et pour tout i ∈ {1, .., k}, a i = (v i-1 , v i ). Le coût d'un chemin est la somme des coûts des arcs qui le composent : c(p) = n i=0 c(a i ) (

on notera par abus de notation c(p) le coût d'un chemin). Un circuit est un chemin p

c = (v 0 a 1 v 1 a 2 ...a k , v k ) tel que v 0 = v k.
Soit G = (V, A) un graphe orienté, c une fonction de coûts, ainsi que deux sommets particuliers s, t ∈ V qu'on appellera respectivement l'origine et la destination. Le problème du plus court chemina (PCC) de s à t est le problème consistant à trouver un (s-t)-chemin de coût minimum. On présente en figure 2

24| Introduction

Il existe une solution au PCC si et seulement si (i) il existe un (s, t)-chemin dans G et (ii) il n'existe pas de circuit de coût strictement négatif (appelé aussi circuit absorbant).

Il existe différents algorithmes de résolution du problème du plus court chemin. Dans les cas où le graphe ne possède pas de circuit, l'algorithme de Bellman permet de trouver un plus court chemin d'un graphe en un temps polynomial en le nombre de sommets et d'arcs [START_REF] Bellman | On a routing problem[END_REF]. En effet, lorsque le graphe ne possède pas de circuit, il existe un ordre topologique sur les sommets du graphe.

Definition 21

Soit G = (V, A) un graphe orienté. Un ordre topologique O sur V est un ordre (v 1 , v 2 , ..., v n ) sur les sommets tel que pour tout k, k ∈ {1, .., n}, (v k , v k ) ∈ A ⇒ k < k .

Proposition 22

Soit G = (V, A) un graphe orienté. Il existe un ordre topologique sur V si et seulement si G est sans circuit.

Dans le cas où tous les coûts des arcs sont positifs, l'algorithme de Dijkstra résout le problème en un temps polynomial également [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF]. Dans le cas général, l'algorithme de Bellman-Ford trouve une solution optimale s'il en existe et trouve un circuit absorbant le cas échéant [START_REF] Ford | Network flow theory[END_REF].

Dans le chapitre 1, nous détaillons une extension de l'algorithme de Dijkstra au cas du plus court chemin stochastique. Nous rappelons donc l'algorithme pour les PCC. Soit G = (V, A) un graphe orienté et c une fonction de coût telle que pour tout a ∈ A, c(a) ≥ 0. Soit s ∈ V , l'algorithme de Dijkstra calcule itérativement une s-arborescence de coût minimal.

Definition 23

Soit G = (V, A) un graphe orienté et c une fonction de coût sur A. Soit s ∈ V , une s-arborescence est une union de chemins de s à v pour tout v ∈ V sans circuit.

Une s-anti-arborescence est une union de (v -s)-chemins pour tout v ∈ V sans circuit.

Le coût d'une s-arborescence ou d'une s-anti-arborescence est la somme des coûts des arcs qui la compose.

Au fur et à mesure des itérations, l'algorithme met à jour un ensemble Y de sommets (initialement vide), et des 'étiquettes' y : V -→ R + sur les sommets de G. Y représente l'ensemble des sommets pour lesquels la valeur de l'étiquette ne changera plus, et pour tout v ∈ V , y(v) représente le coût du plus court (s, v)-chemin ne passant que par des sommets de Y . L'algorithme itère tant que Y = V . A chaque itération, l'algorithme va choisir un sommet z * dont l'étiquette courante est minimale et qui n'est pas dans Y . Par minimalité des étiquettes et comme les coûts des arcs sont positifs ou nuls, on sait que l'étiquette de z * représente le coût du plus court chemin de s à z * . En effet, il ne serait pas 'rentable' de passer par des sommets qui ne sont pas dans Y . Ensuite, on place z * dans Y et on met à jours les étiquettes de tous voisins v de z * s'il est plus intéressant que le (s, v)-chemin passe par z * . On détaille l'algorithme de Dijkstra.

| 25

Algorithm 2 Dijkstra Algorithm

Y = ∅ y(s) = 0, y(v) = ∞ ∀v ∈ V \ {s} while Y = V do Choisir z * tel que y(z * ) = min z∈V y(z) Y ← Y ∪ {z * } for all v ∈ N (z * ) do if y(v) > y(z * ) + c((z * , v)) then y(v) = y(z * ) + c((z * , v)) end if end for end while Soit n = |V | et m = |A|,
l'algorithme de Dijkstra est polynomial : il s'exécute en un temps de O(n 2 +m) L'algorithme peut être implémenté plus efficacement et ne nécessiter que O(m + n log(n)) opérations [START_REF] Yue | An efficient implementation of shortest path algorithm based on dijkstra algorithm[END_REF].

Une manière de voir le problème du plus court chemin déterministe (d'ailleurs adoptée par Ford dans [START_REF] Ford | Network flow theory[END_REF]) est de voir le problème comme un problème de flot particulier. L'idée est de voir un plus court chemin de s à t comme un flot réalisable de s à t de coût minimum. On peut donc formuler le problème grâce à un programme linéaire.

On définit un vecteur x ∈ R m sur les arcs, ainsi que la matrice d'adjacence

(A G ij ) i,j∈{1..n}×{1,..,m} de G. Cette matrice possède n lignes et m colonnes et pour chaque arc j = (i, i ), A G ij = 1, A G i j = -1 et A G i j = 0 pour tout autre i = i, i = i .
On définit le programme linéaire suivant :

Min c T x Sachant que A G i x =        1 si i = s -1 si i = t 0 sinon pour tout i ∈ {1, .., n} x ≥ 0 (P G P CC )
Le dual de (P G P CC ) est (D G P CC ) :

Max y s Sachant que y j -y i ≤ c a pour tout a = (i, j) ∈ A y t = 0 y ∈ R n (D G P CC )
On peut prouver que dans ce cas particulier, on peut trouver une solution optimale entière si elle existe [START_REF] Ford | Network flow theory[END_REF], ce qui définit un plus court chemin de s à t. En effet, la matrice A G est totalement unimodulaire.

Chapter 1 The Stochastic Shortest Path Problem: A polyhedral combinatorics perspective

The following chapter has been taken from an article that has been already published in the European Journal of Operational Research (EJOR) in 2018 [START_REF] Guillot | The stochastic shortest path problem: A polyhedral combinatorics perspective[END_REF]. Consequently, this chapter can be read independently from the other chapters. However, it contains all the formal definition of Stochastic Shortest Path problem needed in the rest of this manuscript.

Introduction

The Stochastic Shortest Path problem (SSP) is a Markov Decision Process (MDP) that generalizes the classic deterministic shortest path problem. We want to control an agent, who evolves dynamically in a system composed of different states, so as to converge to a predefined target. The agent is controlled by taking actions in each time period1 : actions are associated with costs and transitions in the system are governed by probability distributions that depend exclusively on the previous action taken and are thus independent of the past. We focus on finite state/action spaces: the goal is to choose an action for each state, i.e., a deterministic and stationary policy, so as to minimize the total expected cost incurred by the agent before reaching the (absorbing) target state, when starting from a given initial state.

More formally, a stochastic shortest path instance is defined by a tuple (S, A, J, P, c) where S = {0, 1, . . . , n} is a finite set of states, A = {0, 1, . . . , m} is a finite set of A row substochastic matrix is a matrix with nonnegative entries so that every row adds up to at most 1. We denote by M ≤ (l, k) the set of all l × k row substochastic matrices and by M = (l, k) the set of all row stochastic matrices (i.e. for which every row adds up to exactly 1). In the following, we denote by A(s) the set of actions available from s ∈ {1, ..., n} and we assume without loss of generality3 that for all a ∈ A, there exists a unique s such that a ∈ A(s). We denote by A -1 (s) the set of actions that lead to s i.e. A -1 (s) := {a : P (a, s) > 0}.

We can associate a directed bipartite graph G = (S, A, E) with (S, A, J, P ) by defining E := {(s, a) : s ∈ S \ {0}, a ∈ A \ {0} with J(a, s) = 1} ∪ {(a, s) : s ∈ S \ {0}, a ∈ A -1 (s)} ∪ {(0 S , 0 A ), (0 A , 0 S )}. G is called the support graph. We sometimes call the vertices/nodes of G in S the state nodes and the vertices/nodes of G in A the action nodes. A S-walk in G is a sequence of vertices (s 0 , a 0 , s 1 , a 1 , ..., s k ) for some k ∈ N with and(a i-1 , s i ) ∈ E for all 1 ≤ i ≤ k. k is called the length of the walk. s k is called the head of the walk. We denote by W k the set of all possible S-walk of length k and

s i ∈ S for all 0 ≤ i ≤ k, a i ∈ A for all 0 ≤ i ≤ k -1, (s i , a i ) ∈ E for all 0 ≤ i ≤ k -1,
W := ∪ k∈N W k . A policy Π is a function Π : (k, w k ) ∈ N × W → Π k,w k ∈ M = (n, m) satisfying w k ∈ W k ,
and Π k,w k (s, a) > 0 =⇒ J(s, a) = 1 for all s ∈ {1, ..., n} and a ∈ {1, ..., m}. We say that a policy is deterministic if Π k,w k is a 0/1 matrix for all k and w k , it is randomized otherwise. If there exist k and w k , w k ∈ W k that share a same head and such that

INTRODUCTION | 29

Π k,w k = Π k,w k , we say that the policy is history-dependent (otherwise it is usually said to be memoryless or Markovian). If Π is a constant function, we say that the policy is stationary. A policy Π induces a probability distribution over the (countable) set of all possible S-walks. When Π is stationary, we often abuse notation and identify Π with a n × m matrix.

We let y Π k ∈ R n + be the substochastic 4 vector representing the state of the system in period k when following policy Π (from an initial distribution y Π 0 ). That is y Π k (s) is the probability of being in state s, for all s = 1, ..., n at time k following policy Π. Similarly, we denote by x Π k ∈ R m + the substochastic5 vector representing the probability to perform action a, for all a = 1, ..., m, at time k following policy Π. Given a stationary policy Π and an initial distribution y Π 0 at time 0, by the law of total probability (and because each action is available in exactly one state), we have x Π k = Π T • y Π k for all k ≥ 0. Similarly, we have:

y Π k = P T x Π k-1 = P T • Π T • y Π k-1 for all k ≥ 1.
Hence the state of the system at time k ≥ 0 follows y

Π k = (P T • Π T ) k • y Π 0 .
The value c T x Π k represents the expected cost paid at time k following policy Π. One can define for each s ∈ S \ {0}, J Π (s) := lim sup K→+∞ K k=0 c T x Π k with y Π 0 := e s , and J * (s) := min{J Π (s) : Π deterministic and stationary policy}6 (e s is the characteristic vector of {s} i.e. the 0/1 vector with e s (s ) = 1 iff s = s). Bertsekas and Tsitsiklis [START_REF] Bertsekas | An analysis of stochastic shortest path problems[END_REF] introduced the notion of proper stationary policies: a stationary policy Π is said to be proper if 1 T (P T • Π T ) n • e s < 1 for all s = 1, ..., n, that is, after n periods of time, the probability of reaching the target state is positive, from any initial state s. We say that such policies are BT-proper (BTimproper otherwise) as we will introduce a slight generalization later. Bertsekas and Tsistiklis [START_REF] Bertsekas | An analysis of stochastic shortest path problems[END_REF] defined a stationary policy Π * to be optimal7 if J * (s) = J Π * (s) for all s ∈ S \ {0}. They introduced the Stochastic Shortest Path Problem as the problem of finding such an optimal stationary policy.

Literature review

The stochastic shortest path problem is a special case of Markov Decision Process and it is also known as total reward undiscounted MDP [START_REF] Bertsekas | Dynamic programming and optimal control[END_REF][START_REF] Bertsekas | Dynamic programming and optimal control[END_REF][START_REF] Puterman | Markov decision processes: discrete stochastic dynamic programming[END_REF]. It arises naturally in robot motion planning, from maneuvering a vehicle over unfamiliar terrain, steering a flexible needle through human tissue or guiding a swimming micro-robot through turbulent water for instance [START_REF] Alterovitz | The stochastic motion roadmap: A sampling framework for planning with markov motion uncertainty[END_REF]. It has also many applications in operations research, artificial intelligence and economics: from inventory control, reinforcement learning to asset pricing (see for instance [START_REF] White | A survey of applications of markov decision processes[END_REF][START_REF] Merton | An intertemporal capital asset pricing model[END_REF][START_REF] Bäuerle | Markov Decision Processes with Applications to Finance: Markov Decision Processes with Applications to Finance[END_REF][START_REF] Sutton | Introduction to Reinforcement Learning[END_REF]). SSP forms an important class of MDPs as it contains finite horizon MDPs, discounted MDPs (a euro tomorrow is worth less than a euro today) and average cost problems (through the so-called vanishing discounted factor approach) as special cases. It thus encapsulates most of the work on finite state/action MDPs. The stochastic shortest path problem was introduced first by Eaton and Zadeh

30| THE STOCHASTIC SHORTEST PATH PROBLEM:

A POLYHEDRAL COMBINATORICS PERSPECTIVE in 1962 [START_REF] Eaton | Optimal pursuit strategies in discrete-state probabilistic systems[END_REF] in the context of pursuit-evasion games and it was later studied thoroughly by Bertsekas and Tsitsiklis [START_REF] Bertsekas | An analysis of stochastic shortest path problems[END_REF].

MDPs were first introduced in the 50's by Bellman [START_REF] Bellman | Dynamic Programming[END_REF] and Shapley [START_REF] Shapley | Stochastic games[END_REF] and they have a long, rich and successful history (see for instance [START_REF] Bertsekas | Dynamic programming and optimal control[END_REF][START_REF] Bertsekas | Dynamic programming and optimal control[END_REF][START_REF] Puterman | Markov decision processes: discrete stochastic dynamic programming[END_REF]). For most MDPs, it is known that there exists an optimal deterministic and stationary policy [START_REF] Puterman | Markov decision processes: discrete stochastic dynamic programming[END_REF]. Building upon this fact, there are essentially three ways of solving such problems exactly (and some variants): value iteration (VI), policy iteration (PI) and linear programming (LP). Value iteration and policy iteration are the original 50+ years old methods [START_REF] Bellman | Dynamic Programming[END_REF][START_REF] Howard | Dynamic programming and Markov processes[END_REF]. The idea behind VI is to approximate the infinite horizon problem with a longer and longer finite one. The solution to the k-period approximation is built inductively from the optimal solution to the (k -1)-period problem using standard dynamic programing. The convergence of the method relies mainly on the theory of contraction mappings and Banach fixed-point theorem [START_REF] Bertsekas | Dynamic programming and optimal control[END_REF] for most MDPs. PI is an alternative method that starts from a feasible deterministic and stationary policy and iteratively improves the action in each state so as to converge to an optimal solution. It can be interpreted as a simplex algorithm where multiple pivots are performed in each step [START_REF] Manne | Linear programming and sequential decisions[END_REF][START_REF] Denardo | On Linear Programming in a Markov Decision Problem[END_REF]. As such it builds implicitly upon the geometry of the problem to find optimal solutions. Building explicitly upon this polyhedra, most MDPs can also be formulated as linear programs and as such they can thus be solved in (weakly) polynomial time [START_REF] Manne | Linear programming and sequential decisions[END_REF][START_REF] Epenoux | A probabilistic production and inventory problem[END_REF][START_REF] Denardo | On Linear Programming in a Markov Decision Problem[END_REF][START_REF] Hordijk | Linear programming and markov decision chains[END_REF][START_REF] Hernández-Lerma | The linear programming approach[END_REF].

In the context of the SSP, some hypothesis are required for standard methods and proof techniques to apply. Bertsekas and Tsitsiklis [START_REF] Bertsekas | An analysis of stochastic shortest path problems[END_REF] proved that VI, PI and LP still work when two assumptions hold, namely, when (i) there exists a BT-proper policy and (ii) any BT-improper policy Π have at least one state s for which J Π (s) = +∞. In particular they show that one can restrict to deterministic policies. Their assumptions naturally discriminate between BT-proper and BT-improper policies. Exploiting further the discrepency between these policies, Bertsekas and Yu [START_REF] Bertsekas | Stochastic shortest path problems under weak conditions[END_REF] showed that one can relax asumptions (i) and (ii) when the goal is to find an optimal BT-proper stationary policy. They could show that applying the standard VI and PI methods onto a perturbated problem where c is modified to c + δ • 1 with δ > 0 and letting δ tends to zero over the iterations, yields an optimal BT-proper solution if (j) there exists a BT-proper policy and (jj) J * is real-valued. Moreover they could also show that the problem can still be formulated (and thus solved) using linear programming, which settles the (weak) polynomiality of this extension. Some authors from the AI community proposed alternative extensions of the standard SSP introduced by Bertsekas and Tsitsiklis. It is easy to see that the most general one, titled Stochastic and Safety Shortest Path problem [START_REF] Teichteil-Königsbuch | Stochastic safest and shortest path problems[END_REF], is a special case of Bertsekas and Yu's framework (it is a bi-objective problem that can be easily modeled in this framework using artificial actions of prohibited cost).

The question of whether SSP, in its original form or the later generalization by Bertsekas and Yu, can be solved in strongly polynomial time 8 is a major open problem for MDPs (see for instance [START_REF] Ye | The simplex and policy-iteration methods are strongly polynomial for the markov decision problem with a fixed discount rate[END_REF]). It was proven in a series of breakthrough papers that it is the case for fixed discount rate (basically the same problem as before but where the transition matrix P is such that there is a fixed non-zero probability of ending up in 0

INTRODUCTION | 31

after taking any action). The result was first proved using interior point methods [START_REF] Ye | A new complexity result on solving the markov decision problem[END_REF] and then the same author showed that the original policy iteration method proposed by Howard was actually strongly polynomial too [START_REF] Ye | The simplex and policy-iteration methods are strongly polynomial for the markov decision problem with a fixed discount rate[END_REF] (the analysis was later improved [START_REF] Hansen | Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor[END_REF]). The problem is still open for the undiscounted case but Policy Iteration is known to be exponential in that setting [START_REF] Friedmann | An exponential lower bound for the parity game strategy improvement algorithm as we know it[END_REF]. In contrast, value iteration was proved to be exponential even for the discounted case [START_REF] Feinberg | The value iteration algorithm is not strongly polynomial for discounted dynamic programming[END_REF]. Because SSPs can be formulated as linear programs, the question relates very much to the existence of strongly polynomial time algorithms for linear programming, a very long-lasting open problem that was listed as one of the 18 mathematical problems of the 21st century by Smale in 1998 [START_REF] Smale | Mathematical problems for the next century[END_REF]. A possible line of attack is to study simplex-type of algorithms but existence of such algorithms is also a long standing open problem and relates to the Hirsch conjecture on the diameter of polyhedra. These questions are central in optimization, discrete geometry and computational complexity. Despite the fact that SSP exhibits strong additional properties over general LPs, these questions are still currently out of reach in this setting, too.

In practice, value iteration and policy iteration are the methods of choice when solving medium size MDPs. For large scale problems (i.e. most practical applications), approximate solutions are needed to provide satisfying solutions in a reasonable amount of time [START_REF] Powell | Approximate Dynamic Programming: Solving the Curses of Dimensionality[END_REF]. The field is known as Approximate Dynamic Programming and is a very active area of research. Most approximation methods are based on approximate versions of exact algorithms and developping new exact approaches is thus of great practical interest.

In this chapter, we propose an extension of the frameworks of Bertsekas and Tsitsiklis [START_REF] Bertsekas | An analysis of stochastic shortest path problems[END_REF] and Bertsekas and Yu [START_REF] Bertsekas | Stochastic shortest path problems under weak conditions[END_REF]. We prove in Section 1.3 that, in this setting, there is an optimal deterministic and stationary policy. Then we show in Section 1.4 that the standard Value Iteration and Policy Iteration methods converge, and we give an alternative approach that generalizes Dijkstra's algorithm when the costs are nonnegative.

Remark

We became aware recently [START_REF] Quilliot | [END_REF] that some related results were published in 1990 by Bendali and Quilliot [START_REF] Bendali | Réseaux stochastiques[END_REF]. Similarly to Bertsekas and Tsitsiklis [START_REF] Bertsekas | An analysis of stochastic shortest path problems[END_REF], they extended the shortest path problem to stochastic environments. Their approach was different though: they studied the natural extensions of directed graphs to the stochastic setting (they named the corresponding extensions stochastic networks) and they studied the extensions of arborescences and cycles and their role in an alternative notion of stochastic shortest path. They could prove results similar to Bertsekas and Tsitsiklis [START_REF] Bertsekas | An analysis of stochastic shortest path problems[END_REF] (namely that linear programming could be used to solve the problem and they also described a method similar to Value Iteration). They also proposed an extension of Dijkstra's algorithm. These results were totally unknown to the MDP community until now, probably due to the fact that they were published in French and in a different community (Bendali and Quilliot were apparently equally unaware of the work of Bertsekas and Tsitsiklis [START_REF] Bertsekas | An analysis of stochastic shortest path problems[END_REF]). While there are non empty intersections with our work too (in particular for Dijkstra's algorithm), our results are more general: our framework (stricly) encap-

32| THE STOCHASTIC SHORTEST PATH PROBLEM:

A POLYHEDRAL COMBINATORICS PERSPECTIVE sulates both the frameworks of Bertsekas and al. and of Bendali and Quilliot. Besides, our results were proved independently with different techniques.

Notations and definitions

For a graph G, we denote by V (G) the vertex/node set of G and by E(G) its edge set. Given a directed graph G(V, E), and a set S ⊂ V , we denote by δ + (S) the set of arcs (u, v) with u ∈ S and v ∈ S, and by N + (S) the set of vertices v ∈ V \ S such that (u, v) ∈ E for some u ∈ S. For convenience when S is a singleton, we denote δ + ({u}) by δ + (u) and N + ({u}) by N + (u). Then we define inductively

N + k (u) := N + (N + k-1 (u)) \ N + k-1 (u) ∪ . . . ∪ N + 0 (u)) for k ≥ 1 integer with N + 0 (u) = {u}. We denote by R + (u) the set of vertices reachable from u i.e. R + (u) = k≥0 N + k (u). We can define δ -(u), N -(u), N - k (u) and R -(u) analogously. Clearly v ∈ R -(u) if and only if u ∈ R + (v). R -(u)
are the vertices that can reach u. When confusion may arise, we denote R + (u) by R + G (u) (and similarly for the other notations). We say that a graph

G(V, E) is strongly connected if for all u, v ∈ V (G), we have u ∈ R + (v) and v ∈ R + (u).
We denote by 1 A the indicator function associated with a set A i.e. 1 A is a 0/1 function with 1 A (a) = 1 if and only if a ∈ A. For a vector x ∈ R d and I ⊆ {1, ..., d} we denote by x[I] the restriction of x to the indices in I and x(I) := i∈I x(i). For s ∈ {1, ..., n}, we denote by e s the 0/1 vector of R n with e s (i) = 1 if and only if i = s.

Main contributions and roadmap

In this chapter, we revisit the Stochastic Shortest Path problem, a well-known problem in Markov Decision Processes. We shed some new light on this well-established problem, both structurally and algorithmically. Our approach is to mimic the polyhedral analysis of the deterministic shortest path problem.

On the structural side, we study the polyhedra associated with the natural linear relaxation of the problem. We show that extreme points of the polyhedra are associated with deterministic and stationary policies by generalizing the flow decomposition property (a fundamental result in network flow theory). This allows to: (i) formally prove that we can restrict to such policies for this problem, a fact that was somewhat taken for granted in earlier works ; (ii) relax the conditions under which the problem is well-defined and (weakly) polynomial: this is the case now when there is a way to reach the target from any initial state, and there is no 'transition cycle' of negative cost (the extension of negative cost cycles to the stochastic setting) ; (iii) simplify the analysis of the problem.

On the algorithmic side, building upon our polyhedral findings: (i) we prove that the two standard methods for MDPs, i.e. Value Iteration and Policy Iteration, converge in our more general setting ; (ii) we also give a new iterative algorithm based on the standard primal-dual algorithm for linear programming. When the costs are nonnegative, this algorithm can be seen as a generalization of Dijkstra's algorithm to the stochastic setting.

INTRODUCTION | 33

We believe that our result closes some important algorithmic and structural gap between the deterministic problem and the stochastic extension. All in all, our new approach allows to generalize, unify and simplify most results on the SSP for finite state/action spaces and we believe that we set the appropriate and natural framework to study the problem in this case.

Besides, our approach has several strengths with respect to the literature: (i) Approaching the problem from a polyhedral combinatorics perspective is new. Polyhedral combinatorics has been a powerful tool in harmonizing and simplifying many fundamental results in combinatorial optimization. We believe that this new perspective on the problem might help address important remaining open questions such as the existence of a strongly polynomial time algorithm ; (ii) Our framework properly encapsulates the deterministic shortest path problem, in contrast with prior works ; (iii) Our proofs are elementary for people familiar with network flow theory and it should thus provide a new entry point to the problem for people in combinatorial optimization not familiar with Markov Decision Processes. This should help grasping further interest from this community ; (iv) Our generalization allows to capture many important subproblems that were not fitting in the previous frameworks, such as the so-called MAXPROB problem, where the goal is to reach a target with maximum probability: this is a core problem in optimal control, artificial intelligence and game theory.

We now try to give an overview of the different propositions, lemmas and theorems that follow. This should help the reader familiar with the deterministic shortest path problem and its relation with network flow theory to navigate smoothly through the next sections.

In Section 1.2, we introduce our new framework for the stochastic shortest path problem. We show in particular (Lemma 1.2) that our framework properly encapsulates the one proposed by Bertsekas and Tsitsiklis [START_REF] Bertsekas | An analysis of stochastic shortest path problems[END_REF]. In the deterministic setting the standard assumptions for the shortest (s, t)-path problem are that (i) there exists a path from any node to t and (ii) there is no negative cost cycle. Assumption 24 generalizes these two assumptions to the stochastic setting in the most natural way and we prove that the corresponding assumptions are easily checked (Lemma 1.3 , Lemma 1.4 and Lemma 1.5). We also introduce the natural linear programming relaxation of the problem, the so-called network flux relaxation (see (P s )). This is again the natural generalization of the network flow formulation for the deterministic version.

In Section 1.3, we prove that the network flux relaxation is actually a formulation by showing that the extreme points are associated with proper 9 , deterministic and stationary policies (Corollary 28). This result builds upon an extension of a fundamental theorem for network flows: the flow decomposition theorem. The idea in the deterministic case is to decompose a flow in paths and cycles. In the stochastic setting this translates into a decomposition in terms of proper, deterministic and stationary policies and transition cycles. The proof of the corresponding theorem (Theorem 1.7) builds upon different basic properties of flux vectors (that is, solutions to the network flux relaxation), namely, that if a flux 'goes through' a node, then this node has to be connected to the sink (Proposition

34| THE STOCHASTIC SHORTEST PATH PROBLEM:

A POLYHEDRAL COMBINATORICS PERSPECTIVE 25), and the fact that one can easily associate a flux vector to a proper, deterministic and stationary policy (Proposition 26). These properties are trivial when instantiated in the determininistic setting but a bit more technical in the stochastic case. As in the deterministic case, the idea behind the flow decomposition theorem is to first identify "paths" (Lemma 1.8) and then decompose "cycles" (Lemma 1.9). Lemma 1.6 shows that each step in the decomposition can be performed efficiently. Finally Lemma 1.10 generalizes Bellman optimality conditions to the stochastic setting (that is, if the optimal policy can visit a certain node, the policy should be optimal from this node too).

Bellman optimality conditions are then exploited in Section 1.4 to derive several iterative algorithms. We first prove that Value Iteration (the generalization of Bellman-Ford algorithm), converges in value to the optimal solution (Theorem 1.11) and we show that we can in fact extract a series of proper, deterministic and stationary policies that converge to the optimal policy (Theorem 1.12). We then prove that we can exploit the linear programming formulation to derive simplex-type of algorithms: any standard (single pivot) simplex method will find an optimal policy in a finite number of steps as the linear program is non degenerate (Theorem 1.13), and Howard's Policy Iteration method (a multi-pivot simplex algorithm) also converges in a finite number of steps (Theorem 1.14). The latter result exploits the fact that the objective function is nonincreasing in each iteration (Proposition 29). Finally Theorem 1.15 exploits the standard primal-dual algorithm for linear programming to provide a natural extension of Dijkstra's algorithm.

Our new framework

We start with a simple observation:

Lemma 1.1 Let Q be a matrix with lim k→+∞ Q k = 0. Then I -Q is invertible, k≥0 Q k is well defined and k≥0 Q k = (I -Q) -1 .

Lemma 1.2

For BT-proper stationary policies, lim

K→+∞ K k=0 x Π k is finite for any initial state distribution y Π 0 . Proof. x Π k = Π T • P T • x Π k-1 for all k ≥ 1 and x Π 0 = Π T y Π 0 . Therefore x Π k = (Π T • P T ) k • Π T y Π 0 , where y Π 0 is the original state distribution. It follows that K k=0 x Π k = K k=0 ((Π T • P T ) k • Π T y 0 ) = ( K k=0 (Π T • P T ) k ) • Π T y 0 and because of the standard Lemma 1.1, it implies that I -Π T •P T is invertible and that lim K→+∞ K k=0 x Π k = (I -Π T •P T ) -1 •Π T y 0 . (lim k→+∞ (Π T • P T ) k = 0 by definition of BT-properness since 1 T (P T • Π T ) n • e i < 1 for all i = 1, ..., n).

OUR NEW FRAMEWORK | 35

We now extend the notion of proper policies introduced by Bertsekas and Tsitsiklis using this alternative (relaxed) property and from now on we will only use this new definition.

Given a state s ∈ {1, ..., n}, a policy Π is said to be s-proper if k≥0 x Π k is finite, when y Π 0 := e s . Observe that k≥0 y Π k is also finite for s-proper policies (as

y Π k = P T x Π k-1
). In particular lim k→+∞ y Π k = 0 and thus the policy leads to the target state 0 with probability 1 from state s. A s-proper policy is thus a policy that converges to the target with probability one and whose expected number of visit in each action is finite. The expected cost of such a policy is thus the well-defined value c T k≥0 x Π k . The sstochastic-shortest-path problem (s-SSP for short) is the problem of finding a s-proper policy Π of minimal cost c T k≥0 x Π k . We say that a policy is proper if it is s-proper for all s and it is called improper otherwise. The stochastic shortest path problem (SSP) is the problem of finding a proper policy Π of minimal cost c T k≥0 x Π k where y Π 0 := 1 n 1. It is easily seen that the stochastic shortest path problem, as defined here, is also a special case of the s-SSP as one can add an artificial state with only one action that leads to all states in {1, ..., n} with probability 1 n . In the following two sections, unless otherwise stated, we restrict to the s-SSP. In this context, we often abuse notation and we simply call proper a s-proper policy.

Since for any policy Π (possibly history-dependent and randomized), Π k,w k are stochastic matrices, we have at any period k ≥ 0, a∈A(s) x Π k (a) = y Π k (s) (remember that each action is available in exactly one state). We also have y

Π k+1 (s) = a∈A p(s|a)x Π k (a) for all s ∈ {1, ..., n}. In matrix form this is equivalent to y Π k = J T x Π k and y Π k+1 = P T x Π k . This implies J T x Π k+1 = P T x Π k for all k ≥ 0. We also have J T x Π 0 = e s . Now x Π := ∞ k=0
x Π k is well-defined for proper policies. Summing up the previous relations over all periods k ≥ 0 we get (J -P ) T x Π = e s . Hence the following linear program is a relaxation of the s-SSP problem 10 .

min c T x (J -P ) T x = e s x ≥ 0
(P s )
Observe that for a deterministic problem (i.e. when P is a 0/1 matrix), (J -P ) T is the node-arc incidence matrix of a graph (up to a row as it does not containt the row associated with the sink node) and the corresponding LP is the standard network flow relaxation of the deterministic shortest path problem (again up to a row as we remove the (redundant) flow conservation constraint for the sink node). The vector x is sometimes called a network flux as it generalizes the notion of network flow. 10 We would like to stress on the fact that the LP relaxation we consider here is almost (except for the right hand side) the standard LP formulation of the problem of finding an optimal deterministic and stationary policy and it was already known for quite some time for many special cases of SSP (see [START_REF] Bertsekas | Stochastic shortest path problems under weak conditions[END_REF] for instance). However while usually, the LP formulation comes as a corollary of other results, here we reverse the approach and introduce this formulation as a natural relaxation of the problem and we derive the standard results as (reasonably) simple corollaries. This is what allows to simplify, generalize and unify many results from the litterature. This is a simple yet major contribution of this chapter. The notation and terminology is taken from [START_REF] Hansen | Worst-case Analysis of Strategy Iteration and the Simplex Method[END_REF].

36| THE STOCHASTIC SHORTEST PATH PROBLEM: A POLYHEDRAL COMBINATORICS PERSPECTIVE

We call a solution x to (J -P ) T x = 0, x ≥ 0 a transition cycle and the cost of such a transition cycle x is c T x. Negative cost transition cycles are the natural extension of negative cost cycles for deterministic problems. One can check the existence of such objects by solving a linear program.

Lemma 1.3

One can check in (weakly) polynomial time whether a stochastic shortest path instance admits a negative cost transition cycle through linear programming.

We will prove in the sequel that the extreme points of P s := {x ≥ 0 : (J -P ) T x = e s } 'correspond' to proper deterministic and stationary policies. Hence, when the relaxation (P s ) has a finite optimum (i.e. when there is no transition cycle of negative cost and when a proper policy exists), this will allow to prove that, the s-SSP admits an optimal proper policy which is deterministic and stationary. This answers, for this problem, one fundamental question in MDP theory "Under what conditions is it optimal to restrict to deterministic and stationary policies ?" [START_REF] Puterman | Markov decision processes: discrete stochastic dynamic programming[END_REF].

We can assume without loss of generality that there exists a path between all state node s and 0 in the support graph G. Indeed, if there is a state node s with no path to 0 in G, then no s-proper policy will pass through s at any point in time (because then the probability of reaching the target state, starting from s , is zero, contradicting lim k→+∞ y Π k = 0) ; we could thus remove s and the actions leading to s and iterate. Under this assumption, there is always a s-proper policy. Indeed the randomized and stationary policy Π that chooses an action uniformly at random among A(s ), in each state s = 1, ..., n, will work: in this case, for each state s , there is in fact a non zero probability of choosing one of the paths from s to 0 after at most n periods of time.

Lemma 1.4

Consider a s-SSP instance where there exists a path between all state node s and 0 in the support graph G. Then the policy that consists, for each state s ∈ S \ {0}, in choosing uniformly at random an action in A(s ) is a proper stationary policy.

The discussion above also gives a simple algorithm for testing the existence of a proper policy for any instance of the SSP.

Lemma 1.5 One can check in time O(|S| • (|S| + |A| + |E|)) whether a s-SSP instance with support graph G = (S, A, E) admits a proper policy or not.

We are now ready to introduce the new assumptions that we will use to study the stochastic shortest path problem. They are the very natural extensions of the standard assumptions for the deterministic shortest path problem.

Assumption 24

We consider s-SSP/SSP instances where:

• there exists a path between all state node s and 0 in the support graph G, and

• there is no negative cost transition cycle.

As already observed, these assumptions can be checked in (weakly) polynomial time. Moreover, these assumptions implies that (P s ) has a finite optimum (from standard LP arguments). Also Bertsekas and Yu's framework is a special case of our setting as in the presence of negative cost transition cycles, J * (s ) is not real-valued for some state s 11 . The main extension, with respect to Bertsekas and Yu, is that we allow for non-stationary proper policies in the first place.

Existence of an optimal, deterministic and stationary policy

In this section, we will prove essential properties about P s := {x ≥ 0 : (J -P ) T x = e s }. This will allow to prove that, under Assumption 24, we can restrict to optimal proper, deterministic and stationary policies.

We start with a few definitions. Let G = (S, A, E) be the support graph of our s-SSP instance and let x ∈ R m . We define G x to be the subgraph of G induced by the vertices

in A x ∪ N + G (A x ) ∪ N - G (A x )
where A x := {a ∈ {1, ..., m} with x(a) > 0}. G x is called the support graph of x in G. Again we call state nodes the vertices/nodes of G x that are in S and action nodes the vertices/nodes of G x that are in A. We denote by E x the set of edges of G x . A transition cycle x is simple if for all state nodes s in V (G x ), there exists exactly one edge of andG x is strongly connected.

N + G (s ) in E x , i.e. |N + Gx (s )| = 1,
The main theorem of this section is an extension of the flow decomposition theorem, which is a fundamental result in network flow theory (see [START_REF] Ahuja | Network Flows: Theory, Algorithms, and Applications[END_REF]). It asserts that any network flux is a convex combination of network flux 'associated with' proper policies plus a conic combination of simple transition cycles (see Theorem 1.7). Before we can prove this theorem , we need a couple of useful propositions. The proof of the first proposition builds upon simple flow conservation arguments.

11 One can prove using Lemma 1.9 and basic geometry that when there exists a negative cost transition cycle, there exists also a simple transition cycle of negative cost (see the definition in the second paragraph of Section 1.3): all state nodes s on this cycle will have J Π (s ) = -∞, where Π is the deterministic and stationary policy that consists in choosing the unique action a ∈ A(s ) with x(a) > 0 for each state node s on the cycle and any action for the state nodes that are not on the cycle.

38| THE STOCHASTIC SHORTEST PATH PROBLEM:

A POLYHEDRAL COMBINATORICS PERSPECTIVE

Proposition 25

Let x ∈ R m be a feasible solution of (P s ). There exists a path between all states reachable from s in G x and 0 S . In other word, for all s ∈ R + Gx (s), we have s ∈ R - Gx (0 S ).

Proof. Let us define x ∈ R |Ex| as follows: x((s , a)) := x(a) for all a ∈ A x and s the (unique) state with a ∈ A(s ), and x((a, s )) := P (a, s ) • x(a) for all a ∈ A x , and s ∈ S such that P (a, s ) > 0. Observe that x is only defined on E x and that x > 0. Because x is a feasible solution to (P s ), x satisfies x(δ

+ Gx (v)) -x(δ - Gx (v)) = 1 {s} (v) -1 {0 S } (v) for all v ∈ V (G x ) and x ≥ 0. It is thus a unit (s, 0 S )-flow in V (G x ). Now let us assume that there exists s ∈ R + Gx (s) with s ∈ R - Gx (0). Summing up all flow constraints over v ∈ R + Gx (s ), we get x(δ + Gx (R + Gx (s ))) -x(δ - Gx (R + Gx (s ))) = 1 R + Gx (i) (s). We have x(δ + Gx (R + Gx (s ))) = 0 by definition of R + Gx (s ). But then x(δ - Gx (R + Gx (s ))) + 1 R + Gx (s ) (s) = 0. Since x(δ - Gx (R + Gx (s ))) ≥ 0, this implies s ∈ R + Gx (s ) and x(δ - Gx (R + Gx (s ))) = 0. Now because s ∈ R + Gx (s ) and s ∈ R - Gx (s ) (by hypothesis), there is at least one arc of E x in δ - Gx (R + Gx (s )) but this implies x(δ - Gx (R + Gx (s ))) > 0 as x > 0, a contradiction.
Given a proper, deterministic and stationary policy Π, we denote by G Π the subgraph of G induced by the state vertices in S and the actions vertices in Π. Now let

G s Π be the subgraph of G Π induced by the vertices in R + G Π (s). G s Π is called the support graph of Π (it
is easily seen that it corresponds to the subgraph induced by the states and actions that we might visit under policy Π when starting from s). Because Π is proper, 0 S is reachable from each state s in G s Π . Let us denote by S the state vertices in G s Π and Π(S ) the actions associated with S in Π. We also denote by P S the restriction of P to the columns in S and the rows in Π(S ) (since Π is determinisitic, P S is a |S | × |S | matrix). P T S can be interpreted as the transition matrix associated with S when following policy Π (we do not leave S ): P S (Π(s ), s ) gives the probability of ending in state s (in one iteration) when starting in state s and using Π(s ). Hence, if we assume that the rows of P S are ordered according to S , then P T S e i defines the state of the system after one iteration of policy Π if we start in state i ∈ S (e i is the restriction of e i to to the indices in S ). Now as already observed, 0 S is reachable from any node in S and it thus follows that (P T S ) k e i , the state of the system after k steps, tends to zero as k tends to infinity (remember that 0 S is left out). Because this is true for any i ∈ S , we have lim k→+∞ (P T S ) k = 0 and thus (I S -P S ) is invertible by Lemma 1.1. Now observe that (I S -P S ) T x Π [Π(S )] = e s for x Π := +∞ k=0 x Π k , with y Π 0 := e s . Indeed x Π (a) = 0 for all a ∈ Π(S ) and thus (I S -P S ) T x Π [Π(S )] = e s corresponds to the constraints of (P s ) associated with the rows in S . We thus have the following result.

Proposition 26

Given a proper, deterministic and stationary policy Π, the flux vector x Π associated with Π and defined by x Π := +∞ k=0 x Π k , with y Π 0 := e s satisfies x Π [Π(S )] = (I S -P S ) -T e s and x Π (a) = 0 for all a ∈ Π(S ), with S , Π(S ), I S , P S and e s defined as above.

The following proposition is easy to prove using similar flow arguments as in the proof of Proposition 25.

Proposition 27

Let Π be a proper, deterministic and stationary policy. We have

G s Π = G x Π . Moreover if x ∈ P s and Π(S) ⊆ A x , then G s Π is a subgraph of G x .
Before proving Theorem 1.7, we need a final lemma.

Lemma 1.6

Let G = (S, A, E) be the support graph of a s-SSP instance and assume that there is a path from every state vertex s to 0 S in G. Then in time O(|S| + |A| + |E|), one can find a proper, deterministic and stationary policy Π.

Proof. We know that, 0 S ∈ R + (s ) for all s , is enough to ensure that there is a proper policy by Lemma 1.4. Now if there exists a state vertex s in G with |A(s )| > 1, we can delete from G an action in A(s ) that does not remove 0 S from R + (s ). Such an action exists as it is enough to keep an action a ∈ A(s ) with minimum distance to 0 (in terms of arc) to ensure that 0 S is still in R + (s ) after deletion (by minimality of the distance to 0, such an action has a directed path to 0 S that does not go through s ). If |A(s )| = 1 for all s then the only possible policy is proper (from Lemma 1.4), deterministic and stationary. We can implement such a procedure in time O(|S| + |A| + |E|) by computing N - k (0) for all k ≤ |S| + |A| and a 0 S -anti-arborescence A using a breadth first search algorithm: we then keep only the actions in A.

We are now ready to prove the main theorem of this section.

Theorem 1.7

Let x ∈ R m be a feasible solution of (P s ). In strongly polynomial time, one

can find k, k ∈ N with 1 ≤ k, k + k ≤ m, x 1 , ..., x k ∈ R m , x 1 , ..., x k ∈ R m , λ 1 , ..., λ k ∈ [0, 1],
and λ 1 , ..., λ k ≥ 0 such that x 1 , ..., x k are feasible solutions of (P s ), x 1 , ..., x k are simple transition cycles,

k j=1 λ j = 1 and x = k j=1 λ j x j + k j =1 λ j x j .
Moreover, the vectors x j are network flux corresponding to proper, deterministic and stationary policies, i.e. for all j ∈ 1, . . . , k, there exists a proper, deterministic and stationary policy Π j such that x j = x Π j .

Proof. We will start with a slightly simpler version.

Lemma 1.8

Let x ∈ R m be a feasible solution of (P s ). In strongly polynomial time, one can find k

∈ N, x 1 , ..., x k , x c ∈ R m ,and λ 1 , ..., λ k ∈ [0, 1] such that 1 ≤ k ≤ m -|A xc |, x 1 , ..., x k are feasible solutions of (P s ), x c is a transition cycle, k j=1 λ j = 1 and x = k j=1 λ j x j + x c . Moreover, the vectors x j are network

40| THE STOCHASTIC SHORTEST PATH PROBLEM:

A POLYHEDRAL COMBINATORICS PERSPECTIVE flux corresponding to proper, deterministic and stationary policies, i.e. for all j ∈ 1, . . . , k, there exists a proper, deterministic and stationary policy Π j such that

x j = x Π j .
Proof. We prove first that such a decomposition exists for any x ∈ P s . Let x be a smallest counter-example (in terms of |A x |). Because x is a feasible solution of (P s ), we know by Proposition 25 that there exists a path between all states reachable from s in G x and 0 S . Now from Lemma 1.6, we know that there exists a proper, deterministic and stationary policy Π to which we can associate and compute a flux x Π using Proposition 26. Let 1 ≥ λ ≥ 0 be the maximum value such that x := x -λx Π ≥ 0. By Proposition 27 we have that

G x Π is a subgraph of G x and thus λ > 0 (as x > 0 on A x ). If λ = 1,
x is a solution to (J -P ) T x = 0, x ≥ 0 and x := x Π + x provides a decomposition for x, a contradiction (note that |A x | < |A x | as A x must miss at least one action of Π leading to 0 S with non zero probability). If λ < 1, by maximality of λ, there is an arc a ∈ A x such that x(a) > 0 and x (a) = 0. Hence A x ⊂ A x and 1 1-λ x is a solution to (P s ) with

|A x | < |A x |.
By minimality of the counter-example, we can assume that there exists a decomposition for 1 1-λ x . Now we can get a decomposition for x from the decomposition for 1 1-λ x by scaling the multipliers by 1-λ and using x Π with multiplier λ, this is a contradiction. Clearly, we can make the proof algorithmic and because A x ⊂ A x at each iteration, the algorithm will terminate with a set of k solutions x 1 , ...., x k to (P s ) and a vector x c satisfying the theorem in at most

|A x | -|A xc | ≤ m -|A xc | steps.
The following lemma builds upon similar ideas.

Lemma 1.9

Let x = 0 ∈ R m be a transition cycle. In strongly polynomial time, one can find k ∈ N, x 1 , ..., x k , ∈ R m ,and

λ 1 , ..., λ k ≥ 0 such that 1 ≤ k ≤ |A x |,
x 1 , ..., x k are simple transition cycles and x = k j=1 λ j x j .

Proof. We prove first that such a decomposition exists for any transition cycle x = 0. Let x be a smallest counter-example (in terms of |A x |). We focus on the support graph G x . By minimality of the counter-example, we can assume that G x is connected. Now G x has to be strongly connected otherwise it would contradict flow conservation constraints (using similar argument as in Proposition 25). Observe also that 0 S is not in V (G x ). Let us consider any action a in A x and let us call e the edge between a and the unique node s with a ∈ A(s). We can consider the graph G a obtained by taking the subgraph of G x \ e induced by the vertices that are reachable from a (in G x \ e), by 'splitting' action a. Let s be the unique state where a is available. We add two artificial node states s 0 , t 0 and an artificial action a 0 that leads to t 0 with probability 1, such that a is removed from the set of actions available in s and a becomes the only action available in s 0 . Let G a be the corresponding graph. We can consider an instance of s 0 -SSP with target state t 0 in G a . Now x can easily be converted into a feasible network flux x for the corresponding problem by simply setting x(a ) = x (a )

x (a) for all a = a 0 and x(a 0 ) = 1.

We can then apply Lemma 1.8 to x to generate x 1 , ..., x k , λ 1 , ..., λ k and x c obeying the corresponding lemma. Now we can convert x 1 , ..., x k into simple transition cycles of our original instance by setting, for all i = 1, ..., k and for all a = a 0 ,

x i (a ) = x i (a ). It follows that x = x (a) • ( k i=1 λ i x i + x c ). Remember that k ≥ 1, so x 1 exists. Now for µ = min a { x (a )
x 1 (a ) }, x = x -µx 1 is still a transition cycle, but |A x | < |A x | by the choice of µ, so by minimality of the counter-example, x can be decomposed into simple transition cycles and so x = x + µx 1 too, a contradiction. We can again make the proof algorithmic and so k ≤ |A x |.

Theorem 1.7 is a direct corollary of Lemma 1.8 and Lemma 1.9: we apply Lemma 1.9 to the transition cycle x c returned by Lemma 1.8 .

We can now exploit Theorem 1.7 to prove that under our assumptions, we can restrict to deterministic and stationary policies.

Corollary 28

Under Assumption 24, the s-SSP admits an optimal proper, deterministic and stationary policy.

Proof. We know from linear programming that when a LP has a finite optimum, we can find an optimal solution in an extreme point. For (P s ), existence of of finite optimum is guaranteed by Assumption 24 : the first conditions implies the existence of a solution by Lemma 1.4 and the second conditions ensure that the value is bounded. But an extreme point x of P s cannot be expressed as a convex combination of other points of P s by definition. As such, using Theorem 1.7, x must be equal to x Π for some proper, deterministic and stationary policy Π. Now c T x Π is precisely the cost of policy Π. Hence we have a feasible solution to our original problem which is optimal for the linear relaxation (P s ). It is thus optimal for the original problem.

We can deduce from what preceeds a result which is standard for the deterministic shortest path problem: Bellman optimality conditions.

Lemma 1.10

Let Π be an optimal proper, deterministic and stationary solution to the s-SSP (under Assumption 24). Let G s Π be the support graph of Π. For all state vertex s in G s Π , Π is optimal for s -SSP.

Proof. Observe first that s -SSP satisfies Assumption 24. Now suppose Π is not optimal for s -SSP. We know from Corollary 28 that s -SSP admits an optimal proper, deterministic and stationary policy Π s . Now the (history-dependent and non stationary) policy Π that consists in applying policy Π to problem s-SSP, up to when state s is reached (if it ever is) and then applying policy Π s is a proper policy. The value of this policy

42| THE STOCHASTIC SHORTEST PATH PROBLEM:

A POLYHEDRAL COMBINATORICS PERSPECTIVE is (strictly) better than the value of Π as there exist realizations where s is reached, a contradiction.

Algorithms

We focused, up to now and without loss of generality, on the s-SSP problem. Bellman optimality conditions (i.e. Lemma 1.10) also tells us that, under Assumption 24, we can actually restrict attention to the SSP problem as well without loss of generality. Indeed we already observed that SSP can be converted to a s-SSP problem by simply adding an artificial state s and a unique action available from s that lead to all states i = 1, ..., n with probability 1 n . Now there is a one-to-one correspondence between the policies of SSP and the policies of the auxiliary s-SSP problem and hence any proper, deterministic and stationary solution Π to SSP is optimal if and only if it is optimal for the auxiliary problem. But by Lemma 1.10, an optimal policy Π * for SSP is optimal for s -SSP for all s = 1, ..., n (as all s are in G Π * ). It is easy to see that all theorems from the previous section extend naturally to the SSP setting. Of course, some definitions and results have to be slightly adapted: for instance, the flux vector x Π associated with a proper deterministic and stationary policy is now

x Π := +∞ k=0 x Π k with y Π 0 := 1 n 1 and it satisfies x Π = (I -P Π ) -T 1
n 1 (see Proposition 26 for the previous relation), where P Π is the n × n matrix obtained from P by keeping only the rows corresponding to actions in Π. For algorithmic reasons, it is more convenient to deal with the SSP problem as there is no problem of degeneracy: the feasible basic solution x Π (it is indeed now the basic solution associated with the basis (I -P Π ) T ) has positive values on the actions in Π. In this section, we will therefore focus on the SSP problem. The corresponding linear programming formulation is (in principle, the right hand side should be 1 n 1 but we simply rescaled it):

min c T x (J -P ) T x = 1 x ≥ 0 (P )
One possible way of solving the previous model is to use any polynomial time algorithm for linear programming. This would lead to weakly polynomial time algorithms for SSP. As pointed out in the introduction, there are two standard alternatives for solving a MDP: Value Iteration and Policy Iteration. We prove in the next two sections the convergence of these methods under Assumption 24. Then we give another new iterative method based on the standard primal-dual approach to linear programming: this can be considered as a natural generalization of Dijkstra's algorithm.

Value Iteration

We denote by P the set of all proper policies for SSP. For all s = 1, ..., n, we define V * (s) to be the optimal value of (P s ) (again under Assumption 24), i.e. V * (s) := min Π∈P c T x Π

ALGORITHMS | 43

with y Π 0 = e s . This is refered to as the value of state s. We have in particular

V * (s) = min Π∈P lim K→+∞ K k=0 c T x Π k by definition of x Π k .
In the following, we show that we can switch the min and lim operators with some care. We need first to introduce an auxiliary SSP instance obtained from (S, A, J, P, c) by adding an action of cost M (s) for each state s = 1, ..., n that lead to state 0 with probability one, with M (s) "big enough". We call aux-SSP this auxiliary problem (we slightly abuse notation and we still denote by c the corresponding cost function). Observe that in aux-SSP, there are proper policies that terminate in at most k time periods for all k ≥ 1, from any starting state. Indeed one can always chose an auxiliary action in period k -1. Let us denote by P k the proper policies in aux-SSP that terminate in at most k steps and by P aux the proper policies for aux-SSP. Observe that V K (s) := min Π∈P K K k=0 c T x Π k is well-defined for each K ≥ 1. In fact we can prove by induction that it follows the dynamic programming formula:

V k (s) = min{V k-1 (s), min a∈A(s) c(a) + s p(s |a)V k-1 (s )} for all k ≥ 2 and V 1 (s) = M (s
) for all s = 1, ..., n (an optimal, deterministic non-stationary policy Π * K can be recovered easily too): V k (s) is indeed the optimal value starting from s among policies in P k . The following result can be seen as an extension of Bellman-Ford algorithm for the deterministic shortest path problem.

Theorem 1.11

For

all s = 1, ..., n, if M (s) ≥ V * (s), then we have V * (s) = lim K→+∞ V K (s).
Proof. We will prove that min

Π∈P lim K→+∞ K k=0 c T x Π k = lim K→+∞ min Π∈P K K k=0 c T x Π k
with y Π 0 := e s , for all s = 1, ..., n, by proving both inequalities. ≤ Let Π * K be an optimal solution to min Π∈P K K k=0 c T x Π k computed by dynamic programming (as described above). Π * K is a proper policy for aux-SSP for all K. By feasibility of Π * K , we thus have

V K (s) = c T K k=0 x Π * K k ≥ min Π∈Paux lim K→+∞ K k=0 c T x Π k
(observe that this minimum is well defined since we are still satisfying Assumptions 24 in aux-SSP). By construction {V K (s), K ≥ 1} is nonincreasing, hence because it is bounded from below, it converges and lim K→+∞ V K (s) is well-defined. Taking the limit we get lim K→+∞ c T K k=0 x

Π * K k ≥ min Π∈Paux lim K→+∞ K k=0 c T x Π k . But min Π∈Paux lim K→+∞ K k=0 c T x Π k ≥ min Π∈P lim K→+∞ K k=0 c T x Π k if M (s)
is chosen so that auxiliary actions can be assumed not to be used in an optimal policy Π * for P aux . This is the case for M (s) ≥ V * (s) as we could consider the (non stationary) policy that applies policy Π * up to the first time we want to use an artificial action and then apply an optimal policy Π * * for P: the corresponding policy has a value no greater than the former. ≥ Let Π * be an optimal proper deterministic and stationary solution to

min Π∈P lim K→+∞ K k=0 c T x Π k 44| THE STOCHASTIC SHORTEST PATH PROBLEM:
A POLYHEDRAL COMBINATORICS PERSPECTIVE (Π * exists in our setting by Corollary 28). Let us denote by Π the policy of P aux that chooses the auxiliary action for each state. Consider the policy Π K of P K obtained from using Π * in periods 0, ..., K -1 and policy Π in period K. By feasibility of Π K , we have c

T x Π K K + K-1 k=0 c T x Π K k ≥ min Π∈P K K k=0 c T x Π k
. Now taking the limit as K tends to infinity, we have the result since lim K→+∞ x Π K K = lim K→+∞ x Π * K = 0 as Π K differs from Π * only in period K, and Π * is s-proper.

Notice that it is easy to find initial values for M (s) satisfying the previous theorem. Indeed one can use V Π (s), the values for state s when using policy Π for any s-proper policy Π. We can actually easily find a proper, deterministic and stationary policy for SSP (i.e. for all s simultaneously) by extending Lemma 1.6 to SSP.

The algorithm that consists in computing V k iteratively is called Value Iteration. Value Iteration was already known to converge for SSP in the presence of transition cycles of cost zero, when initialized appropriately, see Bertsekas and Yu [START_REF] Bertsekas | Stochastic shortest path problems under weak conditions[END_REF].

We now explain how to recover an optimal proper, deterministic and stationary policy, if we were lucky enough to get the optimal vector V * after some iterations (if we build a feasible policy Π k at each iteration, it may happen that we discover that Π is optimal by computing V Π and observing that it satisfies the Bellman equations). Let us consider the dual linear program (D) of (P ) :

max y1 y(J -P ) T ≤ c (D)
By definition of V * (s) and by Lemma 1.10, we know that V * satisfies V * (s) = min a∈A(s) c(a) + s p(s |a)V * (s ) for all s = 1, ..., n. Also extending Corollary 28 to SSP, we know that there exists an optimal proper deterministic and stationary policy Π * with V * (s) = c(Π * (s)) + s p(s |Π * (s))V * (s ) for all s = 1, .., n. In particular, y * := V * is feasible for (D) and because the pair (x Π * , y * ) satisfies the complementary slackness conditions, y * is optimal for (D). Now let us reverse the complementary slackness conditions. An optimal solution x * to (P ) can satisfy x * (a) > 0 only if V * (s) = c(a) + s p(s |a)V * (s ). Let A * be the set of all such actions and let us restrict our instance of SSP to those actions in A * . Because there is an optimal proper, deterministic and stationary policy Π * for SSP and because such a policy must use only actions in A * , we know that there is a path from every state to the target state 0 in the support graph G * = (S * , A * , E * ) of this instance. We know from Lemma 1.6 that we can thus find a proper, deterministic and stationary policy Π in time

O(|S * | + |A * | + |E * |).
The pair (x Π , y * ) satisfies the complementary slackness conditions and thus Π is optimal.

Unfortunately, we might never reach the precise value of V * when iterating VI. However, we can build a proper deterministic and stationary policy Π k at each step k of Value Iteration by considering an approximate version of the complementary slackness theorem. For all k ≥ 0, we define y k := V k , and, for each action a, k a := V k (s -1 (a)) -(c(a) + s p(s |a)V k (s )). For ≥ 0, we define A k the set of actions a ∈ A such that 1.4 ALGORITHMS | 45 k a ≥ -and we denote by SSP k the restriction of our SSP instance to the actions in A k . Let us denote by k ≥ 0 the minimum value ≥ 0 such that SSP k admits a proper, deterministic and stationary policy Π k . Observe that k ∈ {-k a , a ∈ A}. We can thus compute k and Π k in strongly polytime using Lemma 1.5 and Lemma 1.6. We will now prove that V Π k converges to V * as k tends to infinity (V Π k (s) is the value associated with Π k when starting from s).

Let us first notice that

k ≤ max s {V k (s) -V * (s)} (remember V k (s) ≥ V * (s)). Indeed for = max s {V k (s) -V * (s)}, we have V * (s) ≤ V k (s) ≤ V * (s) +
for all s and it follows that for any s and for any optimal policy Π * , we have c(Π * (s))

+ s p(s |Π * (s))V k (s ) ≤ c(Π * (s)) + s p(s |Π * (s))(V * (s ) + ) ≤ c(Π * (s)) + s p(s |Π * (s))V * (s ) + = V * (s) + . It follows that V k (s) -(c(Π * (s)) + s p(s |Π * (s))V k (s )) ≥ V k (s) -V * (s) -≥ -and thus Π * (s) ∈ A k .
Hence Π * is a proper deterministic and stationary policy of SSP k and the result follows. It implies in particular that k tends to zero as k tends to infinity by Theorem 1.11.

Let us consider the pair (x Π k , y k ). x Π k is a solution of (P ) but y k might not be a feasible solution to (D) so it is not a primal/dual pair of solutions. However it almost satisfies the complementary slackness conditions. In particular we have a∈A c(a

)x Π k (a) = a∈Π k c(a)x Π k (a) ≤ a∈Π k (y k (J-P ) T 1 a + k )x Π k (a) = y k (J-P ) T x Π k + a∈Π k k x Π k (a) = y k 1 + k 1 T x Π k .
It follows that, as k tends to infinity, a∈A c(a)x Π k (a) tends to the optimal value of (P ). Indeed y k tends to V * by Theorem 1.11 (and V * 1 is the optimal value of (D) and (P )), k tends to zero by the discusion above, and 1 T x is bounded for proper policies. Therefore x Π k tends to be an optimal solution of P , Π k tends to be an optimal policy, and V Π k tends to V * . We sum up the result in the following theorem.

Theorem 1.12

In each iteration k of Value Iteration, one can compute in strongly polynomial time a proper, deterministic and stationary policy Π k such that V Π k tends to V * as k tends to infinity.

Policy Iteration

An alternative to Value Iteration is to use a simplex algorithm to solve (P ). In order to do so we need an initial basis. We can use Lemma 1.6 to find a proper deterministic and stationary policy Π. Then as we already observed, x Π = (I -P Π ) -T 1 is a non-degenerate feasible basic solution of (P ). Because the basic solutions are non-degenerate, we can implement any pivot rule from this initial basic solution and the simplex algorithm will converge in a finite number of steps. This type of algorithm is often referred to as simple policy iteration in the litterature. This proves that simple PI terminates in a finite number of steps. Unfortunately, most pivot rules are known to be exponential in n and m in the worst case [START_REF] Melekopoglou | On the complexity of the policy improvement algorithm for markov decision processes[END_REF].

Theorem 1.13

46| THE STOCHASTIC SHORTEST PATH PROBLEM:

A POLYHEDRAL COMBINATORICS PERSPECTIVE Under Assumption 24, simple policy iteration converges in a finite number of steps.

In contrast with simple policy iteration, Howard's original policy iteration method [START_REF] Howard | Dynamic programming and Markov processes[END_REF] changes the actions of a (basic) policy in each state s for which there is an action in A(s) with negative reduced cost. We will prove now that this method converges under Assumption 24, by proving that the method iterates over proper, deterministic and stationary policies and that the cost is decreasing at each iteration. Given a proper, deterministic and stationary policy Π, x Π = (I -P Π ) -T 1 is the basic feasible solution of (P ) associated with the basis (I -P Π ) T . We define the reduced cost vector associated with c and Π as cΠ := c -c Π (I -P Π ) -T (J -P ) T following linear programming (in order not to overload the notations we consider c as a row vector in this section). Let us denote by A < (Π) the set of actions a of A such that cΠ (a) < 0. We know from linear programming that if cΠ (a) ≥ 0 for all a, then x Π (and thus Π) is optimal. If A < (Π) = ∅, then we can swap actions in Π with actions in A < (Π) for each state where such an action exists. Let us denote by Π the resulting policy.

Proposition 29 Π is proper and c • x Π < c • x Π
Proof. We denote by y Π the dual solution associated with Π i.e. y Π = c Π (I -P Π ) -T . Assume for contradiction that Π is not proper. Let G Π be the support graph of this policy. Since Π is not proper, there exists a non empty set of states that are not in R -

G Π (0). It implies that there is a set of vertices V in V (G Π ) such that 0 S , 0 A ∈ V and δ + (V ) = ∅. We can choose for instance V = V (G Π ) \ R - G Π
(0). Now we choose V minimal with this property. There exists an action a of A < (Π) in V , otherwise vertices in V are not in R - G Π (0), a contradiction with Π being proper. Consider the graph G a obtained by taking the subgraph of G Π induced by the vertices in V that are reachable from a, by removing the edge between a and the unique state s with a ∈ A(s), and by adding an artificial state s 0 with a as its unique possible action. Let A a be the set of actions in G a . Note that by minimality of V , every vertex in G a is in R - Π (s). Indeed if not we can change the set V by considering instead the vertices in G a that do not have a path to s.

We can associate a s 0 -SSP instance to G a by considering s as the target state. Π is a s 0 -proper policy for this problem. Now let x Π be the corresponding flux vector (in principle it is defined only on the actions in G a but we extend the flux on the other actions by setting it to zero). We can interpret x Π as a (non zero) transition cycle of the original problem (the flux is defined on the same set of actions and x Π (a) = 1). The vector x Π ≥ 0 thus satisfies (J -P ) T x Π = 0. Now the reduced cost cΠ (a ) = c(a ) -c Π (I -P Π ) -T (J -P ) T 1 a satisfies cΠ (a ) ≤ 0 for all a ∈ A a , by definition of Π and Π (actions in Π have reduced cost 0 and actions in Π that are not action from Π have a negative reduced cost). Also, as already observed, cΠ (a

) < 0. Let us analyze cx Π . We have cx Π = a ∈Aa c(a )•x Π (a ) = ( a ∈Aa cΠ (a )•x Π (a ))+c Π (I -P Π ) -T (J -P ) T x Π .

ALGORITHMS | 47

Because (J -P ) T x Π = 0, we have c x Π = a ∈Aa cΠ (a ) x Π (a ) but this is negative as x Π (a ) > 0, cΠ (a ) ≤ 0 for all a ∈ A a , and cΠ (a) < 0 . Therefore x Π is a negative cost transition cycle for our original instance, but this contradicts Assumption 24. Now that we know that Π is proper, we can define x Π to be the network flux associated with Π . We have

c x Π -c x Π = c (x Π -x Π ) = (c Π + c Π (I -P Π ) -T (J - P ) T )(x Π -x Π ).
But by feasibility of Π and Π, we have (J -P ) T x Π = (J -P ) T x Π = 1 and thus c x Π -c x Π = cΠ (x Π -x Π ) = cΠ x Π (as cΠ (a) = 0 for all a ∈ Π by definition of the current basis) . This latter term is negative as Π is using at least one action in A < (Π) and the actions in Π have reduced cost zero.

Because we have a finite number of proper, deterministic and stationary policies, we can conclude that Howard's policy iteration algorithm converges in a finite number of steps.

Theorem 1.14

Under Assumption 24, Howard's PI method converges in a finite number of steps.

Observe that it is important not to change actions which are not strictly improving. Indeed, in this case it is easy to build deterministic examples where Proposition 29 fails (see for instance Fig. 1.2). As for value iteration, prior to this work policy iteration was not known to converge in this setting. And again, as for VI, unfortunately Howard's Policy Iteration can be exponential in n and m [START_REF] Fearnley | Exponential lower bounds for policy iteration[END_REF].

The Primal-Dual algorithm: a generalization of Dijkstra's algorithm

Primal-dual algorithms proved very powerful in the design of efficient (exact or approximation) algorithms in combinatorial optimization. Edmonds' algorithm for the weighted matching problem [START_REF] Edmonds | Maximum matching and a polyhedron with (0,1) vertices[END_REF] is probably the most celebrated example. It is well-known that

48| THE STOCHASTIC SHORTEST PATH PROBLEM:

A POLYHEDRAL COMBINATORICS PERSPECTIVE for the deterministic shortest path problem, when the costs are nonnegative, the primaldual approach corresponds to Dijkstra's algorithm [START_REF] Papadimitriou | Combinatorial optimization: Algorithms and complexity[END_REF]. We extend this approach to the SSP setting. Let us first recall the linear formulation of the problem and its dual :

min c T x (J -P ) T x = 1 x ≥ 0 (P) max 1 T y (J -P ) y ≤ c (D)
The primal-dual algorithm works as follows here. Consider a feasible solution ȳ to (D) (initially ȳ = 0 is feasible if c ≥ 0). Now let Ā := {a ∈ A : 1 T a (J -P ) y = c a }. We know from complementary slackness that ȳ is optimal if and only if there exists x ≥ 0 : (J -P ) T x = 1 and x a = 0, ∀a ∈ Ā ((P) admits a finite optimum by Assumption 24). The problem can be rephrased as a so-called restricted primal (RP), where J Ā, P Ā and x Ā are the restrictions of J, P, x to the row in Ā. We also give its corresponding dual problem (DRP).

min 1 T z (J Ā -P Ā) T x Ā + z = 1 x Ā, z ≥ 0 (RP) max 1 T y (J Ā -P Ā) y ≤ 0 y ≤ 1 (DRP)
If there is a solution of cost 0 to (RP) then we have found an optimal solution to our original problem. Else, we use an optimal, positive cost solution y to (DRP) and we update the initial solution by setting ȳ := ȳ + y with ≥ 0 maximum with the property that ȳ + y remains feasible for (D), and we iterate. The algorithm is known to converge in a finite number of steps ((RP) being non degenerate, no anti-cycling rule is needed to guarantee finiteness here [START_REF] Papadimitriou | Combinatorial optimization: Algorithms and complexity[END_REF]) and this provides an alternative approach to the problem as long as we can also solve (RP) and (DRP).

Observe that (RP) can be interpreted as a SSP problem with action set Ā ∪ {m + 1, ..., m + n}, where actions m + k, for all k = 1, ..., n is an artificial action associated with state k that lead to the target state 0 with probability one. The cost of actions in Ā is zero while the cost of the artificial actions m + 1, ..., m + n is one. The primal-dual approach thus reduces the initial problem to a sequence of simpler 0/1 cost SSP problems. Note that (RP) is actually the problem of maximizing the probability of reaching state 0 using only actions in Ā. This problem is known in the AI community as MAXPROB [START_REF] Mausam | Planning with Markov Decision Processes: An AI Perspective[END_REF]. Little is known about the complexity of this problem. We know though that it can be solved in weakly polynomial time because it fits into our framework and we can thus solve it using linear programming. We could also use Value Iteration, the simplex method or Policy Iteration as described in the previous subsections. Some simplex rules are known to be exponential in this setting [START_REF] Melekopoglou | On the complexity of the policy improvement algorithm for markov decision processes[END_REF]: the question of the existence of a strongly polynomial algorithm is thus wide open for this subproblem too and we believe that MAXPROB deserves attention on its own. Using Howard's policy iteration algorithm to solve the auxiliary problem, the primal-dual approach provides an alternative finite algorithm to solve SSP for nonnegative costs instances.

CONCLUSION AND PERSPECTIVES | 49

Theorem 1. [START_REF] Bertsekas | Dynamic programming and optimal control[END_REF] When c ≥ 0, the primal-dual algorithm can be initialized with ȳ = 0 and if the MAXPROB subproblems are solved using Howard's Policy Iteration (or any other simple Policy Iteration method), then it terminates in a finite number of steps.

We are investigating the complexity of this extension of Dijkstra's algorithm to the SSP. Observe that we do not need to impose that c is nonnegative to apply the primaldual approach. In fact, one can use the standard trick of adding an artificial constraint a x a ≤ M to the problem, with M "big" to find an initial dual solution and iterate the algorithm [START_REF] Papadimitriou | Combinatorial optimization: Algorithms and complexity[END_REF]. The structure of the subproblem changes but it can still be solved using the simplex method. This provides an alternative approach to Value Iteration and Policy Iteration in the general case too.

One might consider variants of the primal-dual algorithm where the updates of the dual solution do not follow the generic mechanism that guarantees finiteness for general LPs, but instead the updates are 'ad-hoc' and exploit the structure of the problem. It might still be possible to prove finiteness of the algorithm in such cases. For instance the so-called auction algorithm [START_REF] Bertsekas | An auction algorithm for shortest paths[END_REF] introduced by Bertsekas to solve the (deterministic) shortest path problem can be seen as such an ad-hoc implementation of the primaldual algorithm. The original version is pseudo-polynomial but it could be turned into a strongly polynomial time algorithm [START_REF] Bertsekas | Polynomial auction algorithms for shortest paths[END_REF]. This might be an alternative route toward a strongly polynomial time algorithm for the stochastic shortest path problem.

Conclusion and Perspectives

In this chapter, we have introduced a new unifying framework for the stochastic shortest path problem. We have shown that the classic flow decomposition theorem extends naturally from network flows to network flux and we have exploited this result to prove that, in this setting, we can restrict to deterministic and stationary policies and that the standard iterative algorithms for Markov Decision Process, i.e. Value Iteration and Policy Iteration, converge. We have also introduced a new promising algorithm that can be seen as a generalization of Dijkstra's algorithm for the deterministic shortest path problem. Our goal is now to implement fast versions of these algorithms and to compare their practical performances on various real-world instances. While the implementation of Value Iteration and Policy Iteration does not seem to provide major numerical challenges (we are still testing the corresponding implementations), our first implementation of the generalization of Dijkstra's algorithm suffers from numerical instability. We are gaining expertise in this area by exchanging with experts of stabilization techniques. We should soon have a stable version of this algorithm implemented. Nevertheless a careful numerical evaluation of the different methods on significative instances is beyond the scope of the current chapter. We leave the corresponding project for future research.

This chapter leaves several fundamental questions unsolved. In particular, we do not provide new insight on the challenging question of whether the stochastic shortest path

50| THE STOCHASTIC SHORTEST PATH PROBLEM:

A POLYHEDRAL COMBINATORICS PERSPECTIVE problem (or total reward undiscounted MDPs) can be solved in strongly polynomial time. We conclude though with a few (possibly) simpler questions that, we believe, deserve some attention on their own and that might help addressing the former : Is it possible to solve MAXPROB in strongly polynomial time ? Can we bound the number of iterations of our variant of Dijkstra's algorithm by a polynomial ? by a polynomial in n and m ? Can the stochastic shortest path problem be solved in strongly polynomial time when the costs are nonnegative ?

Chapter 2

Golf Strategy Optimization for professional golfers performances estimation on the PGA Tour

Introduction

The PGA tour is a competitive Golf circuit which takes place mostly in North America. Every year, between 132 and 156 male professional golfers compete on about fifty events, including the U.S. Open, the PGA championship, the Masters Tournament and three of the four majors. In this chapter, our goal is to develop new methods to predict the scores of professional golfers during events of PGA. The methodology we develop can be used for both predictive analysis (anticipate results) and prescriptive analysis (help golfers to decide upon which skills to improve to maximize winning).

Golf is a sport where the player has to put a ball in a cup with the help of golf club in a minimum number of shots (see [START_REF]Shotlink intelligence program[END_REF] for the official rules of golf in 2019). The field where the golfer plays is called a golf course (or course for short). A course consists of eighteen holes. A hole is composed of different type of grounds:

• the tee where the ball is placed at the beginning of the game where the grass is short. The golfer can use a tee1 in order to raise the ball for his first shot;

• the green where the grass is the most closely mown and where the hole (cup) and a flag-stick (pin) are placed;

• the fairway is a part of the hole between the tee and the green where the grass is kept short;

52| GOLF STRATEGY OPTIMIZATION FOR PROFESSIONAL GOLFERS

PERFORMANCES ESTIMATION ON THE PGA TOUR

• different types of rough (depending of the height of the grass) which are the areas around the fairway. Usually, the further you get from the fairway, the higher the grass is;

• the bunkers, hollow areas filled with sand where it is difficult to hit from;

• different obstacles like water or trees.

The score of a golfer on a hole is the number of shots he made in order to put the ball in the cup, plus possible penalties (e.g. when the ball fall into the water, or goes out-of-bound of the course) [START_REF]Shotlink intelligence program[END_REF].

There are two main types of competitions in Golf:

• The Stroke Play is a mode where all players compete again each other. There is no limitation on the number of players. Each player plays on the 18 holes (or 72 for professional tournament) and the final score of a player is obtained by adding up each score on the different holes. The winner is the player with the lower final score.

• The Match Play is a 2-player mode where the player who has the lower score on a hole wins 1 point. If there is a draw, each player wins 0.5 point. At the end of the eighteen holes, the golfer with the most points wins (note that if the difference of points is more than the number of remaining holes, the players do not play the last holes).

At the beginning of a specific hole, the golfer places the ball on the tee. His score on the hole is initialized to 0. The golfer shoots the ball from the tee ground to the cup. Each time the golfer shoots, he chooses a direction and a distance of shooting and his score is increased by 1, or by 2 if the ball falls into the water, or out-of-bound (when the ball goes in the water or out-of-bound, a new ball in placed at a specific position: typically the previous position for out-of-bound and the entry point for water obstacles). The problem which consists in choosing the 'right' directions and distances for each shot in order to minimize the final score on a specific hole is what we call the golfer's strategy optimization problem (or sometimes, for short, the golfer's problem). In this chapter, we assume that the golfer is not influenced by his previous shots or his position in the leader-board. Even if a professional golfer might take more risks if he is far behind in order to catch up with the leaders, or if a missed-shot streak could impact in a bad way the play of the golfer (while a series of good shots could have the opposite effect), we do not consider these aspects. This kind of impacts are not to be under-estimated, in golf like in other sports [START_REF] Tanaka | The relationships between psychological/physiological changes and behavioral/performance changes of a golf putting task under pressure[END_REF] [START_REF] Mcauley | The effects of subjective and objective competitive outcomes on intrinsic motivation[END_REF]. However, professional golfers do not often take such risks and they usually play regardless of their position in the leader-board.

With these assumptions, the golfer's problem can be modeled as an Markov Decision Process (MDP) and especially as a Stochastic Shortest Path Problem (SSP). We will detail this later, but for formal definition of SSP, we encourage the reader to refer to chapter 1.

INTRODUCTION | 53

Broadie was a precursor in assessing golfer's performances through advanced quantitative analysis. In [START_REF] Broadie | Assessing golfer performance on the pga tour[END_REF], he introduced a new statistical measure called 'Strokes gained' in order to rank professional golfers in different parts of the game of Golf (typically for different distances, types of grounds...). In [START_REF] Bansal | A simulation model to analyze the impact of hole size on putting in golf[END_REF], Bansal and Broadie study the impact of the size of the hole on the putting 2 , for either professional and amateur golfers with simulation techniques. Using the same techniques, Broadie and Ko in [START_REF] Broadie | A simulation model to analyze the impact of distance and direction on golf scores[END_REF] study the impact of distance and direction errors on Golf scores. In [START_REF] Broadie | Every Shot Counts: Using the Revolutionary Strokes Gained Approach to Improve Your Golf Performance and Strategy[END_REF], Broadie explains how to use Strokes gained in order to help golfers to improve their skills and performances.

Sugawara, Kawamura and Suzuki [START_REF] Sugawara | Skill-based simulation model for optimizing strategy in golf[END_REF] used Q-Learning in order to optimize golfers' strategies, taking into account the course layout, and the golfers' skills using simulation models. Drappi and Co Ting Keh [START_REF] Drappi | Predicting golf scores at the shot level[END_REF] predict the discrete probability distribution of a golfer's score, shot after shot, taking into account the golfer's personal skill, the difficulty and the conditions of the course, using learning and Bayesian techniques.

Markov Decisions processes have already been used in Golf. Lowell Heiny [START_REF] Lowell | Stochastic model of the 2012 pga tour season[END_REF] used stochastic process and Markov chains in order to predict scores. He considered that golf could be modeled as an absorbing Markov chain, where the transition probabilities are given from Shotlink Database (see the introduction for details on Shotlink). As we try to infer the will of the player from the data, Lowell Heiny used directly 'gains' (a mark given for each shot) in order to build the transitions [START_REF] Lowell | Stochastic model of the 2012 pga tour season[END_REF]. Prior to his work, Maher applied Markov chain theory to several sports: tennis, soccer, darts, golf and snooker [START_REF] Maher | Stochastic modelling of sport[END_REF].

Markov decision processes has been also used in many other sports. In 2013, Terroba, Kosters and al [START_REF] Terroba | Finding optimal strategies in tennis from video sequences[END_REF] used Markov Decision Processes in order to compute optimal strategies in tennis. They study video sequences in order to build the transition probabilities. In 2012, Trumbelj and al. [START_REF] Trumbelj | Simulating a basketball match with a homogeneous markov model and forecasting the outcome[END_REF] modeled Basket-Ball as a Markov Decision Process. There transition probabilities are built from a play-by-play NBA program, and statistics of the teams themselves. With the same idea, Routley [START_REF] Routley | A markov game model for valuing player actions in ice hockey[END_REF] applied Markov decision processes algorithms in order to find the optimal strategy of a team in ice hockey. Pfeiffer et al. [START_REF] Pfeiffer | A markov chain model of elite table tennis competition[END_REF] in 2010 decomposed the different time period in table tennis matches in order to model this sport as a MDP. Hoffmeister and Rambau [START_REF] Hoffmeister | Strategy optimization in sports : A two-scale approach via markov decision problems[END_REF] [56] used a 2scale approach with two types of MDP in order to model different sports, and especially beach volley-ball. The first one is the 'strategic' MDP, where the macro decisions of the game are taken, and the second one is needed to build the transition probabilities of the strategic MDP by simulation.

In this study we model the golfer's strategy optimization problem as a stochastic shortest path problem in the same spirit as [START_REF] Sugawara | Skill-based simulation model for optimizing strategy in golf[END_REF] and [START_REF] Broadie | A simulation model to analyze the impact of distance and direction on golf scores[END_REF] but with a different target as we will detail later. We need to define the states, the actions available in each state, the costs of these actions and the transition matrix of the SSP. In our model, the states are the different positions where the ball can stand (we discretize the hole). The actions are shots that the golfer can perform in a particular state: it is basically defined by a targeted direction and a targeted distance. The cost of an action is 1, or 2 if there is penalty (if the ball fall into the water or out-of-bound).

54| GOLF STRATEGY OPTIMIZATION FOR PROFESSIONAL GOLFERS PERFORMANCES ESTIMATION ON THE PGA TOUR

The transition matrix contains the probabilities to end up in any state, given that we perform a particular action. Ideally, in order to have this kind of information for a particular golfer, he would have to shoot hundreds of balls from different distances, different directions and different grounds (fairway, rough and bunkers): both the intention of the shot and its realizations are needed to compute an empirical transition matrix. Beside, once the theoretical distribution of the players gathered (we define what it is later), we need a simulator in order to evaluate the true final position of impact of the ball given the weather conditions, the roll of the ball, the obstacle on the balla trajectory and so on. We developed a simple simulator that take into account some of these aspects under certain assumptions that we detail later in this chapter.

Shotlink is a huge database which collect millions of shots of professional golfers during international competitions [START_REF] Pga Tour | Shotlink intelligence program[END_REF]. This database gives access to a large number of information among which coordinates and distance to the pin before and after each shot, type of ground (fairway, rough, bunkers) from where the golfer has shot and a large number of other information. Unfortunately, we cannot access the intention of the player through Shotlink. One way to infer the intention of the player uses video sequences analysis in order to get the physical signs of potential targets. In 2006, Beetz et al. used this method in football [START_REF] Beetz | Camera-based observation of football games for analyzing multiagent activities[END_REF]. We did not have access to such information so, instead we developed a new methodology to infer the intention of a golfer from general knowledge of professional golfer's strategies. We detail this methodology later in the chapter.

Once the SSP model is set, we use algorithms from chapter 1 to solve the golfer's strategy optimization problem. Now the originality of our approach comes from the fact that we do not compute the optimal strategy to help the professional golfers to improve their game. Instead, we use it to predict their score. In order to be able to predict golfers scores, we first compute the optimal strategy for a player. As the player is a professional golfer, we assume that he is playing (close to) his optimal strategy according to his personal skill, the course layout, etc... Thus, we are able to create a 'numerical clone' of a player. This clone can play thousands of holes which allows to build statistical results such as distribution of scores or probability of winning. The same type of techniques is used in [START_REF] Chaslot | Monte-carlo tree search: A new framework for game ai[END_REF] in the game of Go in order to train AI. Monte Carlo simulation were also used in [START_REF] Newton | Monte carlo tennis[END_REF] in order to compute the probability for a player to win a match in tennis.

Organization of the chapter

In the first part of this chapter we describe precisely how we model the golfer's strategy optimization problem as a SSP. Then we explain how we infer the intention of the golfer from the Shotlink database. In order to evaluate the accuracy of our assumptions and the quality of our model in general, we compared the prediction we make with our model to what has happened in reality. For the two main types of golf competitions (Stroke Play and Match Play), we developed ad-hoc methods [START_REF] Brault | [END_REF] inspired by bootstrapping [START_REF] Athreya | Bootstrap of the mean in the infinite variance case[END_REF] [START_REF] Efron | The bootstrap and modern statistics[END_REF] to assess the performances of our approach. The numerical results and the validations methods are explained in the last part of this chapter.

We use the example of Phil Mickelson to illustrate the model. Then we present and

MODELING THE GOLFER'S PROBLEM AS A SSP | 55

analyze our results for two competitions: one in stroke-play at Augusta National Golf 2017 and one in match-play at the Ryder-Cup 2018, before concluding and giving some perspectives.

Modeling the golfer's problem as a SSP

In this section, we describe in more details how we create an instance of SSP for a given player and a given hole. This requires to define states, actions, action costs and a transition matrix.

The States

In our model, a hole is a bounded rectangle region encapsulating tee, fairway, green and the main obstacles within an area where the golfer might end up while playing rationally. The states are pairs (position, ground) of the hole. We assume that the hole is flat and we discretize the hole into a grid of identical cells in order to restrict to a finite set of states (see figures 2.1 2.2 for an illustration).

The choice of discretization is a trade-off between precision and computation time. Indeed, the smaller the cells are, the better the precision is (we know more precisely where the ball stands) but the higher the computation time is (the model size increases). The discretization size is consequently a parameter of our model. For the numerical experiments, we considered a square size of one meter which offers a good trade-off.

Note that in our case the state space has to be finite in order to define a SSP instance, but alternative exist, such as non finite or continuous state spaces [START_REF] Dufour | Approximation of markov decision processes with general state space[END_REF]. The entries of our model for the holes are pictures of these holes (see example in figure 2.1). Each pixel of the pictures has a color, which represent a type of ground. The flag is represented in black. In the discretization, the ground type of a cell is basically the ground type of the majority of the pixels it contains. We also add a sink state (the pin).

56| GOLF STRATEGY OPTIMIZATION FOR PROFESSIONAL GOLFERS PERFORMANCES ESTIMATION ON THE PGA TOUR

The Actions

In each state, the actions correspond to the different possible shots. In our model, an action consists (except for green states that we describe later) in a targeted (flying) direction and distance. An action defines the target of the player.

Note that in real conditions, the golfer chooses a direction, a golf club and usually an intensity for his shot. But each club is used for specific distance, so our approach matches the decisions the golfer has to make in real conditions.

In the following, we actually treat differently the actions performed on non-green states, and those performed on the green.

Actions performed in non-green states

An action performed in a non-green state consists, as already discussed, in a distance and a direction. We discretize the distances and directions so as to define a finite set of actions. For the distances, the discretization depends on the distance of the shot.

MODELING THE GOLFER'S PROBLEM AS A SSP | 57

Indeed, the discretization has to be greater if the golfer shoots far, and smaller if the golfer shoots closer: the golfer cannot target two points that are close when the distance of the shot is big, whereas it can be possible when the distance of shot is short. If the distance of the shot is greater than 30 meters, we assume that the player is able to target any multiple of 5 (meters). Under 30 meters, we assume that the golfer can target any multiple of 2 (meters). This limit of 30 meters corresponds to the short game which includes chipping and short pitching. In the short game, the golfer is usually more precise, so the discretization has to be smaller.

For the directions, we assume that the golfer can aim at any even angle (in degree from 0 to 360): this is also a parameter of our model which can be changed. This parameter has been chosen so as to have a targeted direction error lower than 3.5 meters for a distance of 100 meters, which seems reasonable given the fact that golfers aim 'visually'. The choice of discretization for distances and direction is different in nature from the choice of discretization for the states. For the states, the smaller the discretization is, the more precise the model is: there is no disadvantage to lower this discretization if we do not care about computational time complexity. Whereas for the actions, if the discretization is 'too small', we artificially define actions that a golfer cannot perform in real conditions: it would 'allow' the player to play more shots, even if the golfer is not able to play them. The discretization we took is based on the knowledge of professional golfer's play.

Actions performed in the green

For the states on the green, the layout of the field is quite different from the rest of the hole (assuming that the hole is flat is no longer reasonable). We would need another specific simulator, so we manage the actions on the green differently. We assume that the average number of shots the player has to shoot to put the ball in the cup from any point on the green is a function of the distance to the pin only, which is a very natural assumption, as studied by Tierney and Cook [START_REF] Tierney | A bivariate probability model for putting proficiency[END_REF] (see figure 2.3). Figure 2.3 shows the probability of 1 putt, the probability of more than 3 putts and the expected number of putts to put the ball in the cup according to the distance to the cup. We can read for example, that the expected number of shots when the ball is around 10 feet far from the cup is around 1.54. We can also see that the probability to put the ball in the cup in one shot when the ball is 20 feet far from the cup is around 17%.

58| GOLF STRATEGY OPTIMIZATION FOR PROFESSIONAL GOLFERS PERFORMANCES ESTIMATION ON THE PGA TOUR

Consequently, for each state on the green, we define only one action, that leads to the cup with probability 1. The cost of this action is the average number of shots the player makes to put the ball in the cup. The cost's definition, which depends on the distance to the pin and the golfer himself is described in the following section. Note that we implicitly assume that it is impossible to enter the cup from outside the green, which is also quite reasonable (even though it may happen).

The Cost Function

As we defined differently the actions performed from the green and the actions which are not, we define differently their costs as well.

For each shot which is performed out of the green, the player score is increased by 1, or 2 if there is a penalty. A penalty arises when the ball falls into the water, or when the ball goes out-of-bound. In this case the next state is the previous position for out-of-bound and the entry point for water obstacles. Since we know the transition matrix of the model (described in the following section), we can define the cost of an action as the average of the costs of its realizations.

On the green, there is only one action per state. The cost of an action depends on the golfer, and the distance between the (middle of the) state and the pin. This cost represents the average number of shots the player makes to put the ball in the pin from this distance. From the Shotlink database, we know how many shots the player made

MODELING THE GOLFER'S PROBLEM AS A SSP | 59

to reach the pin according to the distance on a certain period. Here is an example for Phil Mickelson in 2018 (see figure 2.4)

Figure 2.4 -Number of putts according to the distance (in inches) for Phil Mickelson in 2018

From this, we average over the number of shots with 'slices' of • 1 foot large when the distance to the pin is below 10 feet • 5 feet large when the distance to the pin is between 10 and 25 feet We can plot the average number of putts according to the distance to the pin (see figure 2.5).

MODELING THE GOLFER'S PROBLEM AS A SSP | 61

We can see some statistical aberration between 7 and 8 feet: the average number of shots is greater when the player shots from 8 feet than from 7. We assume that these errors are due to the data. Since a green state is one square-meter large, we smooth this effect by picking 100 points at random in this state (which correspond to possible 'true' positions), compute the cost from each point and average over these 100 realizations. Now that we defined the states, the actions from these states and the costs of these actions, let us define the probabilities: the transition matrix.

The Transition Matrix

To define the transition matrix, we have to know the probabilities to end up in a particular state, given that we performed a particular action. We build the transition matrix in two steps: we first define the player's theoretical distribution (of the impact point) around the target, and then simulate these results on the hole. The theoretical statistics of a player represent the intrinsic shot's deviations of the player, while the transition matrix also depends on the obstacles, the roll of the ball, etc...

Theoretical distributions

One possible way to get access to theoretical distribution of a player is to ask him perform all possible actions (distance and direction) hundreds of times in order to get the empirical deviations of his shots. Obviously this approach is unfeasible in practice for professional golfers of the PGA tour.

In our model we infer the theoretical distribution thanks to the Shotlink database. We describe the method we use in the next sections.

Simulation on the Hole

From the theoretical distribution of a golfer (a set of realizations of the impact of shots with the ground around the target point defined by the action) we simulate the shots on the hole we consider: we plug impact of the ball on the hole and we change the point of arrival if an obstacle is on the trajectory of the ball, or if the rules of golf say so.

We developed a simple simulator, assuming that:

• there is no rolling: the ball ends up exactly where it falls.

• the trees have infinite height: the golfer cannot shoot over a tree.

• the impact between the ball and the obstacles (trees) are very naive: when a ball hit a tree, it ends up at the earlier point in the trajectory before the tree.

• when the ball falls into the water or goes out-of-bound, the ball is repositioned where it was before shooting out-of-bound, and at the point of entrance for water obstacles. Then, a penalty occurs.

62| GOLF STRATEGY OPTIMIZATION FOR PROFESSIONAL GOLFERS PERFORMANCES ESTIMATION ON THE PGA TOUR

Our simulator is quite naive and can obviously be improved. However it is an independent piece of our model: it 'only' affects the probabilities of the transition matrix. We could easily plug in any more advanced simulator (e.g. game).

To sum up, from an action (a target point) if we have access to the distribution of impacts around the target, we can simulate these results on an actual hole and see in which cell of the hole (in which state) the ball would end up. Then we obtain an empirical probability distribution to end up in a state for a given action, which is exactly the transition matrix. Let us now describe how we can build the theoretical distribution.

Statistical Inference

In this section we will explain how we infer the theoretical distribution of a golfer from the Shotlink database. The main issue is to infer the aim of the player only from realizations of shots during professional competitions.

Shotlink Database

Shotlink is a huge database which collects shots of golfers during professional competitions [START_REF] Pga Tour | Shotlink intelligence program[END_REF] since 1983. Among all the quantitative information gathered by Shotlink, we can have access to:

• the name of the golfer who shoots;

• the name of the tournament, of the course, and the hole ;

• the type of ground before and after the shot;

• the coordinates of the ball before and after the shot;

• the distance to the pin before and after the shot;

• whether the shot is a recovery shot or not (i.e. if the players just wanted to reach a place easier to shoot from);

• the type of game: Approach the green (middle and long game), Around the green (short game), putting (on the green) or driving (from the tee).

We can get access to a lot of other informations (see Annex 3.6). These information are our raw material to construct the theoretical distribution. In order to be able to relate the level of the players at a precise instant, we restrict to the data of one year. The main informations missing (but quite impossible to collect without assumptions) is the intention of the golfer when he shoots (that is, his original target). In order to do that, we distinguish two cases: the shots made from the tee and the others (off the tee).

STATISTICAL INFERENCE | 63

Shots off the tee

The goal of the golfer is to put the ball in the cup. One natural way to infer the target is to assume that the golfer is targeting the pin directly (when the distance permits) for the shots off the tee.

In order to validate this assumption we need to gather all the shots played off the tee (at a distance where the pin is reachable). Then, we draw 'profiles' like so: for a shot, we have the coordinates of the point from which the shot has been made and the point of arrival of the same shot. We also have access to the coordinates of the pin of the hole on which the golfer shoots. We first draw at the origin all the starting points of the shots, as if the golfer shoots from the same point. Then on a vertical line we draw the points corresponding to the pins: ordinates the corresponding shots are the distance between the starting point of the shot to the pin. Finally, we draw the arrival points relatively to the corresponding pin position and we link with a line between the two. We give an example with two shots in figure 2.6.

Figure 2.6 -Construction of a profile

We compute the profiles (the drawing described above) of the player for two types of games: Approach the green and Around the green, and for four types of ground: Fairway, Primary Rough, Intermediate Rough and Bunkers. The distances are in inches (figure 2.7, 2.8, 2.9, 2.10, 2.11, 2.12, 2.13, 2. We consider that:

• long game cover shots over 100 meters long, excluding driving

• middle game cover shots between 30 and 100 meters long

• short game cover shots below 30 meters long, excluding putting We can observe 'visually' that in most cases, the pair of points (hypothetical target and arrival point) are close. For pairs that are remote, there are two possible explanations: either the golfer has completely missed his shot (unlikely for professional golfers, unlike he hit a tree), or the golfer was not targeting the flag. In both cases, we choose to erase the corresponding data. We erase these data according to two criteria: a flat distance and a percentage of the distance of the shot.a For the short game we deleted the shots that end up more than 5 meters away from the hypothetical target and more than 10% of the distance of the shot. For the middle game, we deleted the shots that end up more than 30 meters away from the hypothetical target and more than 10% of the distance of the shot. These parameters seem reasonable for professional golfers and can be modified.

A first approach would be to use these profiles as theoretical distribution directly: these profiles provide us pairs of (target, realization) which is enough to build the theoretical deviation of shots for a golfer. However, the problem of this approach is the lack of data for some type of ground. Indeed, from bunkers or intermediate rough, or for the

STATISTICAL INFERENCE | 67

short games, there are some distances with almost no historical shot. The issue is that if, for instance, there is only one shot played for a particular distance d on a particular ground g. Then if we adopt this first approach, the model would consider that every time the golfer is targeting a point from distance d on ground g, the ball will end up in the only state for which we have a realization. This is a serious issue as we want to assess the general behavior of a player and not consider that a particular shot relates the average play. So we have to manage the lack of data for some distance/ground. So the use of raw data alone is not satisfying. We have to 'regenerate' plausible additional data in order to cover all the distances in all types of grounds.

Creation of 'Stars' on the Fairway

In order to generate new plausible data, we want to take as reference the ground on which we have the greater number of data: the fairway. But already in the fairway, we might have the issue discussed above for some distance. So we start by regenerating new data for the fairway.

The main problem is to generate data for any distance. To be able to do so, we assume that there is a very simple linear dependency on the fairway between the distance of the shot and the deviation (depth and lateral deviation). That is, the deviation at distance d is twice the deviation at distance d 2 (figure 2.7, 2.11).

A star is drawn considering that all the shots are targeting a same artificial point: the aggregation point. From the shots of the profile, we align all the pins of the corresponding shot to the aggregation point and we multiply the coordinates of the arrival point of the corresponding point with a factor da ds where d a is the distance of distance of aggregation and d s the distance of the shot (see figure 2.15). Thus on the fairway, we create stars for the three different types of game: long, middle and short game (see figures 2.16, 2.17, 2.18 for Phil Mickelson with the 2018's data). The distances of aggregation are defined as follow. We also remind the definition of short, middle and long game. Note that the short game does not include putting and that the long game does not include driving.

68| GOLF STRATEGY OPTIMIZATION FOR PROFESSIONAL GOLFERS PERFORMANCES ESTIMATION ON THE PGA TOUR

Range (in m)

Distance of aggregation (in m) Short Game [ At this point, we want to test if our linear dependency between distance and deviation is reasonable enough. We consider that the linearity between the distance of the shot and both depth and lateral deviations is proven if both abscissa and ordinates of the points of the stars follow normal laws, as the number of realization is sufficiently big to assume that the central limit theorem is true.

We tested with the Shapiro-Wilk test if the normal assumption is reasonable. Shapiro-Wilk test is testing whether a set of real number is likely to be a realization of a normal distribution or not. It returns a p-value: if the p-value is greater than a threshold (usually 0.05), we can assume that the distribution follow normal law. The greater the p-value is, the most certain of the normality of the distribution we are. Here are the p-values of Shapiro-Wilk test for Phil Mickelson with the data from 2018: In the results above, if we take a threshold of 0.05, we consider that the distribution follows a normal law if the p-value is above 0.05. For the abscissa, the p-value is great enough to conclude about the normality of the distribution. This confirms that our assumption that players play the same way in every direction. For the ordinates of the short game, even if the p-value is smaller, we can reasonably conclude the same way. For the ordinates of the long game, however, the results are more questionable. On the one hand, the p-value is greater than 0.05. On the other hand, it is very close to the threshold we (arbitrarily) defined. This could mean that for the long game, the golfers may have different deviation before and after their target, which is empirically true if they play 'full shot' (with full intensity). In order to simplify our assumptions, we will still consider that the ordinates of the long game follow a normal law.

We obtain similar results with other players and different time periods. The linear dependency between the distance of shots and deviations are reasonable enough. Now we are able to regenerate data for all the distances, and for all grounds.

Regenerate data for all distances

With the previous results, we can reasonably assume that the abscissa and the ordinates of the stars follow normal distribution. As the stars were built applying a to the deviations of the shots a factor depending on the distance of the shot, we can reasonably assume that the dependency between the deviations (depth and lateral) is a linear function of the distance of the shots.

We now generate new plausible data on the fairway like so:

• as we assume that the coordinates of the points of the stars follow normal law, we compute the empiric parameters of the corresponding normal law (µ d , σ d ), (µ l , σ l ) (for the deviations in depth, and lateral deviation);

• for every distance of shots that we want to generate new plausible data, we simulate n shots points of coordinates (N (µ d , σ d ), N (µ l , σ l )) following normal laws;

• we multiply the coordinates of these points by ds da as we assume there is a linear dependency between the deviations and the distances.

As we assumed in section 2.2.2 that for the long game and the middle game a golfer is able to play every 5 meters, and 2 meters for the short game, we simulate shots accordingly. The number of shots we simulate for each distance is a parameter of our model. For our numerical experiment, we took n shots = 20. This parameter has been chosen so that the results are not sensitive to the random generation: the results that we detail later on the optimal strategies are the same with different random generations (figures 2.19 2.20 2.21 2.22).

72| GOLF STRATEGY OPTIMIZATION FOR PROFESSIONAL GOLFERS PERFORMANCES ESTIMATION ON THE PGA TOUR

For the short game, we regenerate n shots = 20 shots from 1 to 30 meters every 2 meters. For the middle game, from 30 to 100 meters every 5 meters. For the long game, in order to compute the maximal distance to which the golfer can play, we compute a ratio between his maximum distance on the drive and the maximal distance in the long game. Indeed, the maximal distance of each player for the long game depends on his intrinsic power. These assumption are consistent with the ability for the players to target different points described in section 2.2.2. The number of shots regenerated has been chosen large enough for the model not to be sensitive to the data without increasing too much the computational running time.

Regenerate data for all the grounds

In the previous section we succeed in regenerating data in order to get the theoretical statistics on the fairway. We are now about to regenerate shots for all the types of ground.

We will now assume that for a player, the ratio between the deviation on the fairway and on the bunkers/rough is constant. This is a first natural assumption to consider.

All we have to do now is to compute this constant factor between the fairway and the bunkers on the one hand, and between the fairway and the rough on the other hand, and to apply this factor to regenerate data with modified parameters for the normal laws. In order to be more realistic, we discriminated upon two cases: the case where the ball ends up before the target and the case where it ends up after the target. Indeed, on the rough and in the bunkers, it is more likely that the ball ends up before the target, because of the difficulty to have a clean shot on these grounds. So we compute the empirical probability for the ball to end up before the target (easy to do, as we have the coordinates of the pin, and the ones of arrival points), and we generate the right proportion of shots with the right constant coefficient. The coefficients of deviation are computed as the mean of the deviations of shots. We obtain the following generated profiles (figures 2. [START_REF] Brault | [END_REF]

The Driving

For the driving, it is not reasonable to assume that the player is targeting the hole: in many cases the golfer cannot reach the green in one shot because of the too big distance between the teeing ground and the flag. However, we have access to the location of the tee for each hole and to the coordinates of the arrival points for shots on the tee. We can plot the scatter plot of the corresponding arrival points, considering that all the shots have been played from the same point. Let us analyze this scatter plot of the shots on the tee (figure 2.31). Even with a small threshold, it is not reasonable to assume that abscissa and ordinates of the driving follow normal laws. This would mean that for each shot, the relative targets are not the same. This result was predictable, as the layout of the holes in the database are different.

76| GOLF STRATEGY OPTIMIZATION FOR PROFESSIONAL GOLFERS PERFORMANCES ESTIMATION ON THE PGA TOUR

Assumptions on the target for driving

In stroke play mode, the golfers are playing the entire course four times (four rounds). On every hole, we do have four realizations of their first shot on the tee. We assume that the player are following the same strategy for the drive during the whole competition: the golfers are targeting the same point in each round.

We begin by eliminating the shots on the holes that the player did not play four times (the golfer can concede). The idea here is to define the target of the four realizations as the centroid of all the shots that was not 'missed'. We consider that among the four distances of shots, the greater is the one wanted by the golfer. We assume that if a shot's arrival point is 'too far' from the longest shot (we defined a threshold of 50 meters) then there was likely an obstacle, so this shot was not intended by the golfer. We assume that the direction of the shots are never missed. Indeed, the distance of a shot can be quite easily shorten because of an obstacle when the direction is very rarely missed, and when it is missed, the distance of the shot is missed too (so the shot will not be taken into account).

To sum up, we define the target of the four realizations of the four rounds of a competition as the point where:

• direction is the mean of the four directions of the shots • the distance is the mean of the shots that end up less than 50 meters from the longest shot

Just as before, we can plot the profile of Phil Mickelson with 2018's data for the driving (see figure 2.32), just like we did before (see figure 2.6): According to the results of the tests, we can reasonably assume that the two coordinates follow normal distributions, so we can re-generate data for all the distances. We generate data every 5 meters, accordingly to section 2.2.2: we consider that a professional golfer is able to discriminate two targets if they are at least 5 meters away one from the other. The lower bound is the upper bound of the long game on the fairway (which was defined with a ratio between the longest shot of the drive and the longest shot on the fairway) so that the is a continuity between the different sections of distances. The upper bound is define as the distance for which 95% of the shots on the drive are above. This maximum distance of shot for the driving has been chosen so that the players are discriminated according to the maximum power of their shots but also to erase the statistical aberrations (typically when the layout of the hole makes the ball roll to a distance that could not been reached on another hole).

STATISTICAL INFERENCE | 77

We obtain this generated profile of Phil Mickelson for the driving: Now that we managed in creating theoretical distributions for a golfer, we can simulate these on a specific hole as described in section 2.2.4 to create the transition matrix. The states, the actions, the costs of these actions and the transition matrix have been defined, so the SSP model is complete.

RESULTS AND VALIDATION | 79

Results and Validation

Let us consider one specific player and one specific hole. We have seen that we can create an instance of SSP for the golfer's problem on this hole. We can solve the corresponding instance with standard algorithms: in practice we solved the instance with Value Iteration, but Policy Iteration and our new Dijkstra like algorithm (see chapter 1 for more details) have been implemented too. The optimal solution of this instance is a deterministic and stationary policy. It provides the optimal actions that the golfer has to perform in order to minimize the expected number of shots to put the ball in the pin. To represent a policy, we draw in the cells composing the state, the direction of the shot, and the distance of the shot in the bottom left corner. We also write the expected number of shots needed to reach the pin in the top left corner (see figures 2.35 2.36 2.37 2.38). Our goal is to predict the scores of professional golfers on the PGA Tour. We will create a digital clone of the player. We assume that the professional golfers play there optimal strategy, taking into account his personal skill and the hole's layout. Then the optimal strategy we find matches, with this assumption, the behavior of the player we consider, and we can artificially make the clone play as many times as we want to with Monte-Carlo simulations. A simulation consists on following the optimal policy from the tee to the pin:

• we initialize the golfer's score to 0;

• we start from the state whose location corresponds to the tee's location;

• we perform the optimal action on this state;

• from the transition matrix, we know the states in which we can end up, with a corresponding probability distribution;

• we add 1 on the score, or 2 if a penalty occurs;

• we pick randomly one realization (i.e. one state) according to the transition matrix;

• we iterate until a state on the green is reached;

• from figure 2.4 we know the distribution of number of shots the golfer makes to put the ball in the pin from the corresponding state on the green. We pick randomly one realization, i.e. one number of putt, and we add it to the score. So we are able to have an estimation of the scores of a player on a specific hole. We assume that all the holes of a course are independent, meaning that the player plays identically on the first and the eighteenth hole: his strategy is not influenced by his current score. As discussed in the introduction of this chapter, this assumption is questionable considering the risks that the golfers could take, but in practice this assumption is reasonable for professional golfers. Depending on the mode of the competition, we can either compute the expected score of the competition (Stroke-play) or the expected probability of winning (Matcha-play). We take in the following sections two examples of competition: the 2017' Augusta competition for Stroke-play and the 42 th Ryder Cup in 2018 for Match-play.

RESULTS AND VALIDATION | 81

Stroke-Play

During a stroke-play competition, each golfer plays the whole course four times. The score of the player on a round is the sum of the scores over the 18 holes.

Simulation

In order to evaluate the distribution of the score of a golfer in a stroke-play competition, we simulate his game thanks to his numerical clone on each hole and we add up his score over the 18 holes. We repeat this a large number of time (10000 in our numerical experiments). This provides us an approximation of the histogram of scores of the player. Let us call this histogram H S . (see figure 2.41 2.40 for an example with Phil Mickelson with his 2017 statistics on Augusta National Golf Club). Now that we have score distribution of a player on an entire course, we would like to know if this score distribution is accurate. We know the score that the golfer has made during the same competition in the same year: However, it seems difficult to compare a distribution of scores with only 4 realizations (one per round). We would like to create new artificial 'realization' from the one we have i.e. use bootstrapping techniques. As we consider that all the rounds are independent, we can create another (artificial) realization by considering the score on the first round, and switch the score of the first hole with the one of the first hole on 2nd round. We can generalize this by considering that on each hole there is a discrete empirical distribution of scores which corresponds to the four realizations of his four rounds. Then we can regenerate 'realizations' for an entire course by picking at random one of the four realizations for each hole. Thus, instead of having only one realization for the four rounds, we have 4 18 artificial realizations. As we assume that the strategy of the player is not modified neither by the number of the hole nor by the number of the round, we consider that the artificial realizations we get are plausible. Let us create 10000 artificial realizations and create the corresponding histogram of scores that we call H E (see figure 2.42 for a outline of the creation of H E and see 2.

RESULTS AND VALIDATION | 83

RESULTS AND VALIDATION | 85

The means and the standard deviations are quite 'similar'. The next sections describe the method we created to compare the simulations from our model and what happened in reality.

Match-Play

In Match Play, two golfers play against each others. Each hole is played once by the two players. The winner of a hole (the player who put the ball in the cup in the least number of shots) earns one point. If there is a tie, each golfer earns half a point. At the end of the 18 holes, the winner is the player with the most number of points. Thus, for each hole we can get an empirical probability of winning a point for each player by comparing the scores of each player on every hole and see who gets the most points at the end of the 18 holes (see figure 2.44 2.50). As we have this information on each hole, we can also, by simulating the play of each player on the entire course, compute the probability of winning more than 9 points over the 18 holes, i.e. the probability of victory of a golfer on the course (see figure 2

RESULTS AND VALIDATION | 87

When a player is sure to win the match before the end of the 18 holes, the players do not play the remaining holes (it was the case for the two last holes here, where Francesco Molinari was sure to win).

Unlike for the Stroke Play, we have only one realization (and not four). The validation of the accuracy of our winning probabilities is a big issue. We will see in the next section how we manage to give a way to evaluate our model.

Validation

In the previous sections, we managed in giving results for the two main modes in golf: the Stroke Play and the Match Play. For Stroke Play, we give a discrete score distribution for the players, and for Match we give probability of winning for both players. Now the main issue is to evaluate the accuracy of our forecasts. The main difficulty is the few number of realizations (4 per hole for Stroke Play, and only 1 for the Match Play).

Validation for Stroke-Play

For Stroke Play competitions, we have 4 realizations per hole (4 rounds on the 18 holes). One first idea of our validation is to use bootstrapping methods in order to regenerate 'artificial realizations' based on the only 4 we get (figure 2.43). Let us call this histogram H E . We can compare H E with the simulations from our model (figure 2.41), which we call H S . Even if looking at the mean and the standard deviation of H S and H E is a first approach, it is not enough to conclude (what is a reasonable difference between the means ? and the standard deviations ?).

We would like to define a distance between two histograms. A well known distance is the Kolmogorov distance. Let F 1 and F 2 be two distribution functions, and X the space of there distribution function. The Kolmogorov distance between F 1 and F 2 is defined as:

sup x∈X |F 1 (x) -F 2 (x)|
We want to know if the realizations we have could have been easily simulated with our model. The idea is to take 4 simulations on each hole from our model and consider that the corresponding simulations are the scores that the player could have done during 4 artificial rounds. We can bootstrap others realizations from them just like we did for H E . We get an histogram of realizations based on simulations from our model. Let us repeat this process n times. We get n histograms (H E 1 , .., H En ). We assume that if d E is one likely realization of H K then the realization H E can be easily simulated by picking at random 4 realizations from our model. Looking at the quantiles of H K , we have:

88| GOLF STRATEGY OPTIMIZATION FOR PROFESSIONAL GOLFERS PERFORMANCES ESTIMATION ON THE PGA TOUR

Quantiles 77% 78% Value 0.2686 0.2746
From the quantiles, and under our assumptions, we can conclude it is likely for d E to be a realization of H K . Thus, the realization that Phil Mickelson score in 2017 in Augusta National Golf Club can likely be simulated with our model. Indeed, the Kolmogorov distance between H E and H S is one plausible realization of H K . Here are the results for other players for the same year (2017) on Augusta competition. Note that the reader can reproduce the results thanks to our program in C++ and the R scripts given. For these players, we can also conclude that what happened in reality can plausibly be simulated with our model.

Validation for Match-Play

For the validation of Match Play, we adopt the same kind of method. Contrary to Stroke Play where each hole is played four times, in Match Play each hole is played only once by the two players involved. Let us consider the match Phil Mickelson against Francesco Molinari in the Ryder Cup 2018. We would like to know whether or not what happened could have been 'easily' simulated with our model.

We begin with simulating each digital clone of the two players involved on the 18 holes of Golf National course. Each simulation gives a winner (or a draw). By repeating this operation, we obtain a histogram H S which relates of the probability of victory for both players on the entire golf course as seen before (figure 2.46).

We want to compare this histogram with the reality (what happened in the Ryder Cup). The problem is that we have only one realization for it. The idea here is the same as before: we have to use bootstrap techniques in order to create artificially new 'realizations'. We can see that during the Ryder Cup 2018 between Phil Mickelson and Francesco Molinari, only the first 16 holes have been played. We can create new realizations by picking at random 18 holes among the 16 played holes during the Ryder Cup. By comparing the scores of the two players on these 18 holes, we have a winner, or a draw. By repeating this operation 10000 times, we obtain a histogram H E which related of the probability of winning for both player, and a probability of draw (figure 2.50). Obviously, since Molinari has won 7 holes over 16 and Mickelson has won only 3 holes over 16, it is predictable that picking at random 18 holes among these 16 holes makes Molinari wins in most of the cases. Because of the particularity of the unique realization we have, we cannot compare H E and H S (figure 2.46 and 2.50) directly. However, we can pick at random 18 holes among the first 16 played and simulate with our model clones of both players. By doing this n times, we get n histograms (H E i ) i∈{1,..,n} . These histograms represent possible realization from our model if we consider only the 16 first holes. Just like for the Stroke Play, we can compute the Kolmogorov distances d i between H S and the (H E i ) for all i ∈ {1, .., n}. For n = 1000 we get the following histogram, that we call H K of Kolmogorov distances (figure 2 In this case, we conclude that our model can predict what happened, as d E is a plausible value of H K . Obviously the fact that our model cannot predict the very particular cases is a big limit of our model.

RESULTS AND VALIDATION | 91

Computational techniques and remarks

Our computational experiments were developed in C++ and in R. Data analysis and treatment is done with R, while the optimization and the construction of the models are done in C++. We give full access to our code so that the readers can replicate the results.

The 'statistics' of a player are built using R from the Shotlink database. All the assumptions we made can be changed as parameters of the scripts. Once the script is 94| GOLF STRATEGY OPTIMIZATION FOR PROFESSIONAL GOLFERS PERFORMANCES ESTIMATION ON THE PGA TOUR ran, a file of general name "FirstName_LastName.stats" is created. This file is needed for the construction of the model.

The construction of the model, and the optimization has been written in C++. This program can build a SSP model from a ".stats" file (which can be created with our R scripts), and a ".data" file. This latter file describes the topology of the hole we consider. A ".data" file can be created thanks to our program from a picture of a hole. Once the model is created, the program can find an optimal solution thanks to Value Iteration, Policy Iteration or our new Dijkstra-like algorithm (see chapter 1). Our program can also solve generic SSP instance, using standard input files describing the states, actions, action costs, and transition matrix of the instance.

Even if Value Iteration, Policy Iteration and our Dijkstra-like algorithm can be used to solve an instance thanks to our program, all the results in this chapter were found with Value Iteration. Our program has been optimized in order to have good computational performances with Value Iteration: the internal memory management (cache memory) and the construction of our model's data structure were designed to speed-up parallel computing, which lower drastically the computational running time of Value Iteration (from several minutes to a few seconds). We mainly used arrays in order to store our data. As Value Iteration is iterating over all states, the way we store the state in the memory is very important and has drastic impact regarding computational running time (the change of our data divided by 20 the computational running time of Value Iteration).

Regarding the computational time, most of the time is used to load the model, and to create the SSP instance from the data (the Shotlink database and a picture of the hole). The solution time has been optimized as explained above, and take no more than a few second, while loading the model is done in few minutes. Obviously, the value of the parameters has an big impact on the computational running time (discretization of the hole, discretization of directions...). For our choice of parameters, we can create 10000 simulation of a player on the 18 holes of a course in about 6 hours (with a coreI7 4 cores 2.2GHz processor and 16Go 1600MHz DDR3 memory). A tiny part of which is dedicated to the optimization (about 1%).

Contrariwise, our model construction is not adapted to the execution of our Dijkstra algorithm, which explained (in part) the running time of this algorithm with our program.

Conclusion and Perspectives

We created a model for the golfer's problem using Markov Decision Processes, and in particular the Stochastic Shortest Path problem. The states, the actions and the cost of these actions were quite easy to define, while the transition probabilities were harder to model. We used the Shotlink database, which gather thousands of shots of professional golfers during international competitions in order to create theoretical distribution of the players. The main difficulty was to infer the intention of the players. Under certain assumptions, we succeeded in defining targets for the golfers for each

CONCLUSION AND PERSPECTIVES | 95

shot, and we checked the relevance of this assumptions with statistical tests. Once the transition matrix defined, we were able to apply standard algorithms of the SSP to solve the problem exactly and get the optimal strategy of the player, taking account his personal skills, and the simplified physics of the hole he plays on. As we assume that the professional golfers play their optimal strategy, we created 'digital clones' of players and simulate the play of the golfers thousands times on several courses. Depending on the mode (stroke-play or match-play), we were able to have a prediction of the scores, or a winning probability.

The results and their validation is a big issue of this chapter. We had to find ad hoc methods in order to compare our results and what happened in reality. The few number of realizations prevent us to use standard statistical methods (chi 2 test, p-values). We managed in creating artificially new realizations thanks to bootstrap techniques.

As we build our model, we had a lot of assumptions. Obviously these assumptions are questionable.

In order to build the transition matrix, we simulated the behavior of the physics of the ball. The assumptions we made are very simplistic: no rolling, infinite height for the trees, simplified impacts between the ball and the obstacles... The simulator could be improved to be more realistic. The improvement of this simulator would not have major consequences on the model: this is an independent piece which would change the transition matrix but would certainly impact the computational time for model creation.

The assumption we made regarding the intention of the players are also questionable. We consider that the golfers always target the pin if they are not on the tee (and if they are at reach). Although it is reasonable most of the cases, when the par is high (par 5 for example), or when the shape of the hole is elbowed (a so called dog-leg in golf), the golfers would rather target the middle of the fairway to insure to reach the green faster.

When we create the theoretical statistics of the golfers, we had a lot of parameters to tune: thresholds, percentage of shots we cut, statistical tests acceptance... These parameters were chosen based on knowledge of golfers. We also test our model on different year, and these parameters could have to be modified in order to pass the statistical tests. This lack of robustness is also a quite big limit of our model.

The tests we chose are also assumptions: we assume that the distribution of shots is realistic if it follows a normal law, which is questionable. The linearity between the deviation and the distance, the constant factor between the deviations on the different grounds are too.

Chapter 3 On Stochastic Games and MAX-PROB

Introduction

As explained in chapter 2, we came to the SSP problem by studying strategy optimization in Golf: a golfer has to put a ball in a hole in a minimum number of shots taking into account the topology of the field, the weather conditions and their personal skills among other things. The 'golfer's problem' can be modeled as a SSP under certain assumptions (see chapter 2 for more details). Consequently, solving SSP can provide golfers a 'best strategy' to reach the hole in an minimum expected number of shots.

Modeling the golfer's problem as a SSP only considers 'competing against the golf course' and does not include the other players into the equation. This is appropriate when modeling 'Stroke play' competitions where players try to score as low as possible on a large number of holes [START_REF] Matthieu Guillot | Golf strategy optimization for professional golfers's performances estimation on the pga tour[END_REF] to beat the field (that is, the rest of the players). But there are other competitions where two players compete against each others in another form of game called 'Match play' (like for the Ryder Cup, for example). In this mode, both players play potentially every holes of the same golf course against each other. On each hole, the player with the smaller score earns 1 point ( 12 if there is a draw). The winner is the player with the most points at the end of the 18 holes (it might end earlier if the difference of points is more than the number of remaining holes to play).

As Stroke Play competitions can be modeled as SSP, Match Play competitions can be modeled as Stochastic Shortest Path Games (SSPG), which are natural game extensions of SSP where two players control the states of the system.

A SSPG is basically a SSP where the states are partitioned into two sets that are controlled respectively by a M IN and a M AX player with antagonist objectives. The goal of the M IN player is to find a strategy (a choice of action for each state controlled by this player and each period of time) to reach the target state with minimum expected cost while the M AX player wants to find a strategy to maximize the expected cost. in 98| ON STOCHASTIC GAMES AND MAXPROB general, M IN might be tempted to keep looping in the system if negative cost transition cost cycle exist, and vice versa M AX might be tempted to keep looping in the system if positive cost cycle exists. So technical conditions are required to define the problem formally. in this chapter we focus mainly on the special case of SSPG with termination inevitable (where all pairs of strategies lead to the target state with probability 1).

SSPG are a special case of (zero-sum) stochastic games introduced originally by Shapley for discounted problems [START_REF] Shapley | Stochastic games[END_REF] but whose definition has been extended later to undiscounted problems (for a comprehensive treatment of stochastic games, see for instance [START_REF] Bellman | Stochastic Games and Applications[END_REF] and [START_REF] Filar | Competitive Markov decision processes[END_REF]). SSPG with termination inevitable are special cases of BWRgames (two-person zero-sum stochastic mean payoff games with perfect information) with total effective payoff [START_REF] Boros | Markov decision processes and stochastic games with total effective payoff[END_REF]. In particular, because stochastic shortest path games with inevitable termination have mean payoff (average cost per time period) of value 0 from any starting state as the game ends with probability one, it follows from Theorem 27 in [START_REF] Boros | Markov decision processes and stochastic games with total effective payoff[END_REF] and Von Neuman Minimax theorem for zero-sum games [START_REF] Neumann | Zur theorie der gesellschaftsspiele[END_REF] that: (i) there exists (at least) a pair of uniformly1 deterministic and stationary strategies for both players which forms a Nash Equilibrium (i.e. no player can benefit from deviating from his strategy) and (ii) that the corresponding strategy for M IN minimizes the maximum expected total cost over all possible strategy for M AX and the strategy for M AX maximizes the minimum expected total cost under all possible strategy for M IN . The stochastic shortest path game is the problem of finding such a pair of strategies. One well known iterative algorithm to solve exactly the SSPG is known as Strategy Iteration [START_REF] Hansen | Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor[END_REF][START_REF] Condon | The complexity of stochastic games[END_REF][START_REF] Condon | On algorithms for simple stochastic games[END_REF] which can be interpreted as a extended version of Policy Iteration for SSPG (we detail this later).

During a Match-Play competition in Golf, the first player teeing on a hole is the player who won a hole last (initially it is selected at random). Let us call him M IN , and M AX his opponent. This is then the player whose ball is the further from the flag who plays first. When a golfer shoots, he knows the position of his ball, the position of his opponent's ball and the current difference of scores between him and his opponent. This naturally defines a state space: for a specific hole, we consider the set S with element s of the form s

we have δ = σ M IN -σ M AX .
The initial state is s 0 = (P tee , P tee , 0) where P tee is the position of the tee. Even if the relative difference of scores cannot be bounded a priori, in practice beyond a certain point difference, usually, the late runner "gives" the hole to the opponent, so we can easily define a difference D ∈ Z + and restrict to states with δ ∈ {-D, -D + 1, .., D -1, D} (for professional golfers, D is rarely more than 2 or 3). ,δ ) with δ = δ + 1 (or δ = δ + 2 if a penalty occurs, see [START_REF]Shotlink intelligence program[END_REF] for details of penalties in Golf, unless δ > D and then it goes to the target node that we define later with a cost 1). Similarly, when M AX plays from s, the ball ends up in another position p M AX , and the new state is s = (p M IN , p M AX , δ ) with δ = δ -1 (or δ = δ -2), unless δ < -D and then it goes to the sink node with a cost -1. These transitions induce no cost except when reaching the sink node. Let us call flag states the states whose general form is (P f lag , P f lag , δ f ) where P f lag is the position of the flag. The game stops when a flag state (P f lag , P f lag , δ f ) is reached: M IN wins if δ f < 0 , M AX wins if δ f > 0 and there is a draw if δ f = 0. In order to match exactly a SSPG instance, we define a sink node (called 0) which can be reached only from flag states (P f lag , P f lag , δ f ) (and the states where δ < -D or δ > D as we have seen before) with a probability 1 and a cost 1 if

δ f > 0, -1 if δ f < 0 and 0 if δ f = 0 . The cost of a pair of policies Π = (Π M IN , Π M AX ) represents the points when M IN follows Π M IN and M AX follows Π M AX .
Despite the fact that Match Play competitions are well described by SSPG, the size of the state space is too large for implementing strategy iteration. Indeed, the state space size is n 2 * (2D + 1) where n is the number of possible locations on the hole (depending on the discretization we choose), and D the bound on the difference of scores between the players. With regards to the computational performances in chapter 2 where the state space size was only n, it is hopeless to run similar algorithms like strategy iteration on such big instances: this is why we used other techniques in chapter 2 to model Match Play competitions which we believe provide a decent heuristic. In [START_REF] Hoffmeister | Strategy optimization in sports : A two-scale approach via markov decision problems[END_REF] and [START_REF] Hoffmeister | Sport strategy optimization in beach volleyball? how to bound direct point probabilities dependent on individual skills[END_REF], Hoffmeister and Rambau used MDPs for strategy optimization in beach Volleyball. They also face too large instances that could not be solved exactly. They succeed in solving heuristically the problem by simulating strategies of MDP instead of solving it. Such an approach would certainly be of interest here too. However, it is interesting to study Stochastic Shortest Path Games for themselves. In this chapter though, we put the focus on the theory of SSPG and in particular on the question of existence of polynomial time algorithms.

Finding an optimal solution of SSPG, i.e. a Nash Equilibrium, is a problem in N P ∩ coN P , and the question whether it is in P or not is open [START_REF] Condon | The complexity of stochastic games[END_REF] (we refer to chapter 1 for definitions of P , N P and coN P ). In particular, the question of the existence of a LP-formulation with a polynomial number of variables and constraints (a polyhedron whose extreme points are solutions for the SSPG), even in a extended space, is open. Even if we know that some 'naive' formulations do not work for a special case of SSPG called the Simple Stochastic Games (that we define later formally) [START_REF] Condon | On algorithms for simple stochastic games[END_REF], the question has been neither answered positively nor negatively.

In this chapter we focus on this open question and we try to bring new insights and some directions for further investigations. Our goal is to analyze first which subproblems of SSPG are known to be polynomial, and in particular to identify polynomial size extended formulations for those or to prove that none exist. The idea would then be to extend the conclusion when possible to the general case.

There have been tremendous developments in the field of extended formulations 100| ON STOCHASTIC GAMES AND MAXPROB lately. In his survey [START_REF] Kaibel | Extended formulations in combinatorial optimization[END_REF], Kaibel gathers the combinatorial problems for which there exists compact extended formulation (meaning that the number of inequalities of the extended formulation is a polynomial function of the data of the original problem). Spanning trees, permutahedron, disjunctive programming are examples for which such extended formulations exist. However, there are some theoretical limitation regarding extended formulations. Rothvoss proves in [START_REF] Rothvoß | Some 0/1 polytopes need exponential size extended formulations[END_REF] that extended formulations of some 0/1 polytopes need exponential number of inequalities [START_REF] Rothvoß | Some 0/1 polytopes need exponential size extended formulations[END_REF]. Fiorini et al. in [START_REF] Fiorini | Exponential lower bounds for polytopes in combinatorial optimization[END_REF] prove that for the Traveling Salesman Problem (TSP), a LP-formulation need an exponential number of constraints. Even more striking is the fact that some polynomial problems like matching do not have a polynomial extended formulation [START_REF] Rothvoß | Some 0/1 polytopes need exponential size extended formulations[END_REF].

In this chapter, we first define formally the SSPG with termination inevitable, then the special case of stopping Simple Stochastic Games (SSG). Later in the document we study another special case, the Robust Shortest Path Problem with termination inevitable (RSP), for which we present a ILP-formulation that can be extended to SSPG, which is the main contribution of this chapter. Finally, after considering instances which are both stopping SSG and RSP with termination inevitable for which we find a condition for the existence of an optimal solution that, we believe, could be extended to stopping SSG instances, we analyze the complexity of these different problems, and of MAXPROB. This last problem has already been defined in chapter 1 and arise naturally in this chapter too. A,J,P,c) and we define the value of the game for the pair Π = (Π M IN , Π M AX ), from an initial state i, as the value of the SSP solution associated with Π i.e. J Π (i).

Stochastic Games

From now on, we assume that termination is inevitable, meaning that any strategy profile (Π M IN , Π M AX ) induces a policy Π that is proper for the corresponding SSP instance.

We denote by Σ M IN the set of all (positional) strategies for player M IN and by Σ M AX the set of all (positional) strategies for player M AX. SSPG with termination inevitable are a special case of BWR-Games with total effective payoff [START_REF] Boros | Markov decision processes and stochastic games with total effective payoff[END_REF]. Because all policies are proper, for all initial state i, the mean payoff version of the game starting in state i has value zero. It then follows from Theorem 27 in [START_REF] Boros | Markov decision processes and stochastic games with total effective payoff[END_REF] that there exists

J (Π M IN ,Π M AX ) (i) = min Π M IN ∈Σ M IN max Π M AX ∈Σ M AX J (Π M IN ,Π M AX ) (i) = max Π M AX ∈Σ M AX min Π M IN ∈Σ M IN J (Π M IN ,Π M AX ) (i)
The stochastic shortest path game with inevitable termination is the problem of finding such a Nash equilibrium.

We can represent an instance of SSPG with a graph

G = (V = (V S M IN ∪ V S M AX ) ∪ (V A M IN ∪ V A M AX ), A).

102| ON STOCHASTIC GAMES AND MAXPROB

Strategy Iteration

Even if no polynomial time algorithm is known for SSPGs, we can solve this problem with the so called strategy iteration algorithm [START_REF] Hoffman | On nonterminating stochastic games[END_REF][START_REF] Rao | Algorithms for discounted stochastic games[END_REF]. This iterative algorithm is very close to policy iteration for SSP: both players will improve their strategies step by step until a Nash equilibrium is found. For the following definition, we remind that c Π and P Π are the subvector and submatrix of c and P respectively, whose lines correspond to the actions of Π. We first define the reduced cost of an action. For all action a ∈ A, and all deterministic and stationary policy Π, the reduced cost of a is defined by: cΠ (a) = c(a) -c Π (I -P Π ) -T (J -P ) T 1 a where 1 a is a vector of m lines with 1 in the a th position, and 0 elsewhere. We denote by an improving set with regards to player j such a set. We denote by Π[B j ] the strategy such that:

• ∀s ∈ S if ∃a ∈ B j such that J(a, s) = 1 then Π[B j ](s) = a • Π[B j ](s) = Π(s) otherwise
We call Π[B j ] an improving strategy with regards to player j When a player does not have improving strategies anymore, we say that he has a best response. In the next definition, we define formally a best response.

STOCHASTIC GAMES | 103

J (Π M IN ,Π * M AX ) = max π M AX ∈Σ M AX J (Π M IN ,π M AX ) Similarly, Π * M IN ∈ Σ M IN is a best response to Π M AX if and only if J (Π * M IN ,Π M AX ) = min π M IN ∈Σ M IN J (π M IN ,Π M AX ) Definition 33 (Nash equilibrium) A pair of strategies (Π M IN , Π M AX ) ∈ Σ M IN × Σ M
J (Π M IN ,Π M AX ) ≥ J (Π M IN ,Π M AX )
and the inequality is strict for at least one state.

Proof. Π M IN is a best response to Π M AX so there is no improving set with regards to M IN (lemma 3.1). Thus, for all a ∈ A M IN , cΠ (a) ≥ 0 so in particular, cΠ (a) ≥ 0 for all a ∈ Π M IN . Π M AX be an improving strategy with regards to player M AX so there exists B M AX ⊆ A M AX which is an improving set with regards to M AX. It follows that cΠ (a) ≥ 0 for all a ∈ B M AX and there exists a ∈ B M AX such that cΠ (a) > 0 (by definition of an improving strategy). Let us see Π = (Π M IN , Π M AX ) as a strategy of the SSP instance related 104| ON STOCHASTIC GAMES AND MAXPROB with I. We have cΠ (a) ≥ 0 for all a ∈ Π , and there is at least one action a ∈ Π such that cΠ (a) > 0. It follows from chapter 1 that J

(Π M IN ,Π M AX ) = J Π ≥ J Π = J (Π M IN ,Π M AX )
, and the inequality is strict for at least one state.

We now define strategy iteration algorithm:

Algorithm 3 Strategy Iteration

Input

: a deterministic and stationary policy Π

= (Π M IN , Π M AX ) k = 1 Π k M IN ← Π M IN Π k M AX ← Π M AX Π k ← (Π k M IN , Π k M AX ) loop while ∃B M IN ⊆ A M IN such that Π k [B M IN ] is an improving strategy with regards to M IN do Π k ← Π k [B M IN ] Define Π k M IN , Π k M AX such that Π k = (Π k M IN , Π k M AX ) end while if ∃B M AX ⊆ A M AX such that Π k [B M AX ] is an improving strategy with regards to M AX then Π k+1 ← Π k [B M AX ] Define Π k M IN , Π k M AX such that Π k = (Π k M IN , Π k M AX ) k ← k + 1 else return Π k end if end loop
Let us apply this algorithm on the previous example of SSPG instance I (figure 3.1) with an initial deterministic and stationary policy Π

1 = (Π 1 M IN , Π 1 M AX ) with Π 1 M IN (s 1 ) = a 2 , Π 1 M AX (s 2 ) = a 3 , and Π 1 M AX (s 3 ) = a 4 .
We represent a deterministic and stationary policy by coloring in red (resp. in blue) the arc leading to the chosen action in the states of S M IN (resp. S M AX ).

STOCHASTIC GAMES | 105

J (Π k+1 M IN ,Π k+1 M AX ) ≥ J (Π k M IN ,Π k M AX )
and the inequality is strict for at least one state. It follows that a pair of strategies does not appear twice, and since there is a finite number of pairs of strategies, the algorithm terminates in a finite number of iteration, let us say N ∈ Z + . At the end of the algorithm the pair of strategy (Π the number of states and actions as the worst case of policy iteration is exponential [START_REF] Melekopoglou | On the complexity of the policy improvement algorithm for markov decision processes[END_REF] (even in the case of termination inevitable [START_REF] Tripathi | On strategy improvement algorithms for simple stochastic games[END_REF]).

Special cases of SSPG with termination inevitable

As mentioned before, the existence of a LP-formulation for SSPG is a long standing open question. Our idea is to dig into special cases of SSPG with termination inevitable: stopping Simple Stochastic Games (stopping SSG) and Robust Shortest Path with termination inevitable (RSP with termination inevitable), in order to find a LP-formulation for these potential 'simpler' cases and hopefully generalize these formulations to SSPG with termination inevitable. Note that more general version of stopping SSG and RSP with termination inevitable exists as we detail later, which are special case of SSPG (but without termination inevitable).

Simple Stochastic Games (SSG)

Condon introduced Simple Stochastic Games in 1992 [START_REF] Condon | The complexity of stochastic games[END_REF]. We follow her definition: a simple stochastic game is a game defined on a directed graph with three types of vertices, called max, min and average vertices. There are two special sink vertices named 0 M INsink and 0 M AX -sink and all but these two sink vertices have exactly two neighbors (possibly identical). The game is played by two players, a M IN and a M AX player. A 108| ON STOCHASTIC GAMES AND MAXPROB pebble is initially placed on a given node and the pebble is moved on the edges of the graph as follows: in a max (resp. min) node, M AX (resp. M IN ) chooses a neighbor to which the pebble is moved, and in a average node, the pebble is moved to one of the two neighbors with equal probability 1 2 . M AX wins if the pebble reaches the 0 M AX -sink and otherwise M IN wins (if the pebble reaches the 0 M IN -sink or if no sink is reached). Condon [START_REF] Condon | On algorithms for simple stochastic games[END_REF] proved that deciding if the probability that M AX wins is greater than 1 2 is in N P ∩ coN P and she conjectured that the problem is in P . She also proved that one can restrict attention to stopping simple stochastic games as far as polynomial solvability is concerned, i.e. simple stochastic games that end in a sink node with probability one for any possible choice of strategies of the players. In our representation, we color the M IN vertices in red, the M AX vertices in blue and the average vertices in green. We also distinguish the edges as follows: the regular edges represent the choices for the two players and the dashed edges represent the two possible stochastic transitions from an average vertex (with probability 1 2 ). 2 . The SSG decision problem is deciding whether there exists a policy for player M AX that guarantee that the probability to end up in sink 0 M AX (given by the stationary distribution of the absorbing Markov chain) is greater than 1 2 . From now on, we will consider only stopping SSG: we can see a stopping SSG instance as a special case of SSPG with termination inevitable. A stopping SSG instance can be seen as a tuple The existence of a (polynomial) LP formulation for stopping SSG (i.e. a linear program whose optimal solution would solve the SSG decision problem) is open [START_REF] Condon | The complexity of stochastic games[END_REF].

SPECIAL CASES OF SSPG WITH TERMINATION INEVITABLE | 109

Condon [START_REF] Condon | On algorithms for simple stochastic games[END_REF] proves that some 'naive' formulations do not work. She considers for instance the following linear program:

SPECIAL CASES OF SSPG WITH TERMINATION INEVITABLE | 111

min s∈S M AX v(s) -s∈S M IN v(s) v(i) ≥ v(j) ∀i ∈ S M IN and (i, j) ∈ E v(i) ≤ v(j) ∀i ∈ S M AX and (i, j) ∈ E v(i) = 1 2 (v(j) + v(k)) ∀i ∈ S Avg and (i, j), (i, k) ∈ E v(i) ≥ 0 ∀i ∈ S v(0 M IN ) = 0 v(0 M AX ) = 1 (P Condon )
The idea behind this linear program is to mimic the dual of the standard network flow formulation for the deterministic shortest path (for more details on network flow formulation see ) when there are only 0-cost edges. Indeed, if we consider only the min vertices, the previous linear program becomes:

max s∈S M IN v(s) v(i) ≤ v(j) ∀i ∈ S M IN and (i, j) ∈ E v(i) ≥ 0 ∀i ∈ S M IN v(0 M IN ) = 0 (D SP )
and a feasible solution of (D SP ) is a potential over the nodes in the special case of 0-cost edges. Thus, we would like v(i) to be the probability, starting from i ∈ S, to reach the sink 0 M IN : if v(i) = 0, the probability of reaching 0 M IN is 0 so from i, we would reach 0 M AX surely (as termination is inevitable for stopping SSG).

However, this linear program is not a formulation for stopping SSG. Let us consider the following instance of SSG (we keep Condon's representation for convenience, erasing all the actions). On this example, in each node, there is only one strategy for each player, and this strategy leads to 0 M AX with probability 1. Thus, we would like to have v(i) = 1 for i = 1, 2, 3 (which is feasible for (P Condon )), and in this case, the cost function in (P Condon ) is 1. However, if we define v(i) = 0 for i = 1, 2, 3, then it is another feasible solution to (P Condon ), and the cost is 0, hence the solution to the SSG does not coincide with the optimal solution to (P Condon ). The previous linear program, and the counter example 112| ON STOCHASTIC GAMES AND MAXPROB are from [START_REF] Condon | On algorithms for simple stochastic games[END_REF]. In this article, Condon presents algorithms to solve the SSG decision problem, and a quadratic formulation. She also proves that some naive algorithms such that a modified version of Hoffman-Karp algorithm, or Pollatschek Avi-Itzhak algorithm do not work. She also proved that one can restrict attention to stopping SSG as far as polynomial solvability is concerned. The main remaining question is the existence of a polynomial time algorithm to solve the stopping SSG decision problem.

Strategy Iteration can be applied to solve stopping SSG (as it is a special case of SSPG with termination inevitable), but we know that strategy iteration algorithm is exponential in the worst case in the number of states and actions even in this case as already discussed [START_REF] Tripathi | On strategy improvement algorithms for simple stochastic games[END_REF]. Our original idea was to start studying polynomial time solvable special cases of SSPG with termination inevitable. This is the case of the Robust Shortest Path with termination inevitable (RSP with termination inevitable) [START_REF] Bertsekas | Robust shortest path planning and semicontractive dynamic programming[END_REF]. It is the deterministic version of SSPG with termination inevitable. It can also be seen as a natural variation of Stochastic Shortest Path, where 'nature' does not choose randomly but as to 'hurt' as much as possible. For example in the golfer's problem, solving the RSP gives an upper bound for the number of shots the golfer has to shoot in order to put the ball in the hole.

Robust Shortest Path

In [START_REF] Bertsekas | Robust shortest path planning and semicontractive dynamic programming[END_REF], Bertsekas defines the RSP as a non-symmetrical game on a directed graph G = (S ∪ {0}, A) (0 is a special sink node), where player M IN controls the decisions on nodes S ∪ {0} while an antagonist player M AX controls the destination of these decisions. From each node s ∈ S, M IN chooses an edge (or action) a from a finite set A(s) ⊆ A of available actions in s. Then M AX chooses the destination s ∈ S ∪{0} from a subset of nodes that we call S + (a, s). Then a cost c(s, a, s ) is incurred. Bertsekas defines a policy for M IN to be proper if M AX cannot make M IN loop in the graph without being able to reach 0. A policy which is not proper is said to be improper. The RSP is the problem of finding a proper policy of minimum cost (the cost of a proper policy is the sum of the incurred costs until reaching the destination 0). He proves that such a policy exists if (i) there exists at least one proper policy and (ii) every improper policy makes player M IN loop in a positive cost cycle. Bertsekas could also relax the latter assumption and prove that an optimal policy exists even if every improper policy makes player M IN loop in a non-negative cost cycle. Regarding the computational methods, Bertsekas proves that three iterative algorithms converge to an optimal exact solution: Value Iteration, Policy Iteration and a Dijkstra-like algorithm when the costs are non negative. We explain a version of Value Iteration and the Dijkstra-like algorithm in this framework later in the chapter. Bertsekas also proves that both Value Iteration and Dijkstra converge in polynomial time, which proves that RSP is in P. We encourage the reader to refer to [START_REF] Bertsekas | Robust shortest path planning and semicontractive dynamic programming[END_REF] for more details. As RSP is a special case of SSPG, we could adopt the graphical representation of SSPG, but for convenience we erase the deterministic actions to replace them with simple edges. Hence, we can represent a RSP instance with a graph G

= (V = V M IN ∪V M AX , A) such that each node in V M IN (resp. in V M AX ) represent a state in S M IN (resp. S M AX ).
Each action a ∈ A is represented by an arc a = (s, s ) such that s is the unique state such that J(a, s) = 1 and s is the unique state such that P (a, s ) = 1 if it exists, and s = 0 otherwise. We will call this representation the graphical representation of RSP instance. We will slightly abuse notation and from now, a state s ∈ S will either denote the state or the corresponding node in V , and an action a ∈ A will either denote the action or the corresponding arc in A. can find the optimal strategy (figure 3.17).

Figure 3.17 -An optimal solution

This algorithm runs in O(n 2 m) in worst case, as it terminates with at most n + 1 iterations of nm operations in the worst case [START_REF] Bertsekas | Robust shortest path planning and semicontractive dynamic programming[END_REF] (n is the total number of states, and m the total number of actions/edges).

Proof. (sketch) We can note first that at each iteration (an iteration is the operations inside the outer while loop), there is one node that leaves Z, and this node is never coming back to Z. Thus, the number of iterations is bounded by n, where n is the number of nodes. In fact, the algorithm terminates in exactly n 1 + 1 iterations, where n 1 = |V M IN | and at the end, Y = V . We refer to [START_REF] Bertsekas | Robust shortest path planning and semicontractive dynamic programming[END_REF] for the proof.

Then, let us prove that at the end of each iteration, for all v ∈ V M IN ∩ Y and for all v ∈ V M IN ∩ (V \ Y ), we have y(v) ≥ y(v ), meaning that the labels of the nodes in V M IN ∩ Y are smaller (one by one) than the labels of the nodes in

V M IN ∩ (V \ Y ).
We use induction on the number of iterations. At the end of the first iteration, we have V M IN ∩ Y = {0} and y(0) = 0. Since all the costs are non-negative and from the updates of the labels in the algorithms, we have y(v) ≥ 0 for all v ∈ V . So the assertion holds for the first iteration. Let us assume that the assertion holds for the iteration k -1. Let us call y k the labels at the start of iteration k and ỹk the labels at the end of iteration k. By definition of z * , we have, for all v ∈ V M IN ∩ (Y ∪ {z * }) (whose labels do not change during an iteration) and for all

v ∈ V M IN ∩ (V \ (Y ∪ {z * }), ỹk (v) = y k (v) ≤ y k (z * ) ≤ y k (v) Then, for all v ∈ V M IN ∩ (V \ (Y ∪ {z * })), the labels are updated according to ỹk (v ) = min [y k (v ), min a=(v ,w)∈U (v ) y(w) + c(a)]
Because c(a) ≥ 0 for all a ∈ A, and z * ∈ δ + (a) for all a ∈ U (v ), we have:

ỹk (v ) ≥ min [y k (v ), y k (z * )] 120| ON STOCHASTIC GAMES AND MAXPROB ỹk (v ) ≥ y k (v) ỹk (v ) ≥ ỹk (v)
which proves the assertion. Now, as at the end of each iteration, the nodes in V M IN ∩ Y has smaller labels than the other nodes, and as the costs are non negative, we can prove by induction that at the end of each iteration, y(v) represents the cost of an optimal path from v to 0 using only nodes in Y . The main idea is that as the nodes in V M IN ∩ Y have smaller potentials, and the costs non-negative, it would not be worth to use a path that goes in and out Y . At the end of the algorithm, as Y = V , the returned labels are optimal potentials. We let the reader refer to the complete proof in [START_REF] Bertsekas | Robust shortest path planning and semicontractive dynamic programming[END_REF].

Note that this algorithm still works for instances of RSP that contains cycles [START_REF] Bertsekas | Robust shortest path planning and semicontractive dynamic programming[END_REF].

ILP-Formulations for RSP and SSPG

RSP with termination inevitable is in P, but no LP-formulation is known for this problem. The RSP is very close to the deterministic shortest path problem, so we tried to 'mimic' known LP-formulations for shortest path problems.

We know that for the (s -t)-deterministic shortest path problem, one linear programming formulation consists in looking for a feasible flow from s to t of minimum cost. Once an optimal solution is found, the optimal flow defines a path from s to t of minimum cost. For the RSP with termination inevitable, we want a shortest path from each v ∈ V M IN to 0, and a longest path from each v ∈ V M AX to 0. Thus, we define |V | feasible flows from each s ∈ V to 0 (constraint (1)). Constraint (5) defines potentials from the flows. Constraint (2) insure that all these paths are consistent: let s, s ∈ V be two states, and p, p the optimal paths from s to 0 and from s to 0, respectively. Then if p pass through s , then the sub-path of p from s to 0 and p have to be the same. In order to insure that the path from each s ∈ V M IN (resp. s ∈ V M AX ) have minimum cost (resp. maximum cost), we mimic the dual of the linear programming formulation for deterministic shortest path. We have seen in the introduction of this thesis that this dual uses potentials, and that the inequalities between potentials define the minimization of the path. We slightly adapt these constraints in order to define shortest and longest path from the states in V M IN and V M AX , respectively.

Let I = (S M IN , S M AX , A, J, P, c) be a instance of RSP, and G = (V = V M IN ∪ V M AX , A) be the graph representation of this instance. For all u ∈ V , we denote by N (u) the neighborhood of v, i.e. N (u) = {v ∈ V |∃a ∈ A, a = (u, v)}. We define the following polyhedron:

x s (δ + (v)) -x s (δ -(v)) = 1 if v = s and v = 0 0 otherwise ∀s, v ∈ V (1) x u a -x s a ≥ 0 ∀a ∈ δ + (u), ∀u, s ∈ V (2) y v -y u ≤ c a ∀a = (u, v) ∈ A, u ∈ V M IN (3) y v -y u ≥ c a ∀a = (u, v) ∈ A, u ∈ V M AX (4) a∈A x s a c a = y s ∀s ∈ V (5) (P I RSP )

SPECIAL CASES OF SSPG WITH TERMINATION INEVITABLE | 121

Proposition 35 There is a one-to-one correspondence between the feasible solutions of (P I RSP ) and the optimal solutions of I (considering RSP as an optimization problem for M IN ).

Proof. Let us define x ∈ {0, 1} m : ∀a ∈ A, x a = max s∈S x s a . As a∈δ + (v) x s a ≤ 1 for all s, v ∈ S (constraint (1)) and x u a ≥ x s a ∀a ∈ δ + (u) ∀u, s ∈ S (constraint (2)), since x s ∈ {0, 1} m , we know that supp G (x ) = {a ∈ A|x a > 0} is a 0-anti-arborescence. Reciprocally, from a 0-anti-arborescence Ā we can generate xs for all s ∈ S. Indeed, let us call p s the unique path in Ā from s to 0. Then for all a ∈ A, xs a = 1 if a ∈ p s and 0 otherwise. Then the constraints (1) and ( 2) are satisfied. Then constraints (1) and ( 2) define a pair of policies for M IN and M AX, which is a solution of the RSP instance with termination inevitable.

Finally, once the x s are defined, from constraint (5), y s is exactly the cost of the path defined by x s from s to 0. Thus, if constraints (3) and ( 4) are verified, we can define Π M IN , Π M AX such that Π M AX is a best response to Π M IN , and Π M AX have minimum cost. Thus, Π M IN is an optimal solution of I.

We also give another integer linear programming formulation for RSP, whose idea comes from Jannick Matuschke. The idea is to define variables y ∈ R n (n is still the total number of states) that represent potentials. We also define variables z ∈ {0, 1} |A M AX | , that represent the choice of actions for M AX: for all a ∈ A M AX , z a = 1 if M AX chooses a, and 0 otherwise. Once again, we 'mimic' the dual of the linear programming formulation for the deterministic shortest path problem. Let us consider the following linear programming formulation, where M is a constant to be defined: Proof. Once z * is fixed, the strategy for M AX is set. For all (u, v) = a ∈ A M AX chosen by M AX, constraints (2) are in fact equalities, and are true for the action not chosen by M AX (for which z a = 0), if we take M sufficiently large (such a M is easy to find by solving both a shortest path and a longest path on the RSP instance, and taking the 122| ON STOCHASTIC GAMES AND MAXPROB difference between the two). The problem becomes then a 'classic' deterministic shortest path problem for M IN , whose solution is a 0-anti-arborescence.

max v∈V M IN y v (1) y v -y u ≤ c a ∀(u, v) = a ∈ A M IN (2) y v -y u ≤ z a c a + (1 -z a )M ∀(u, v) = a ∈ A M AX (3) a=(u,v) u∈V M AX z a = 1 (4)
y t = 0 (5) y ∈ R n
The same kind of approach can be generalize to find an integer linear programming formulation for SSPG with termination inevitable. The main idea is the same: to insure that we have a deterministic strategy profile and then thanks to the dual of the linear programming formulation of SSP, insure the optimality of this pair of strategies.

(v) = {a ∈ A|P (a, v) > 0}. (J -P ) T x s = 1 s ∀s ∈ S (1) y v -y u ≤ c a ∀u ∈ S M IN , ∀v ∈ S, ∀a ∈ A(u) ∩ A -(v) (2) y v -y u ≥ c a ∀u ∈ S M AX , ∀v ∈ S, ∀a ∈ A(u) ∩ A -(v) (3) x s a ≤ M z a ∀s ∈ S, ∀a ∈ A (4) a∈δ + (s) z a = 1 ∀s ∈ S (5)
c T x s = y s ∀s ∈ S (6)
(P I SSP G )
Then there is a one-to-one correspondence between the feasible solutions of P I SSP G

and the optimal solutions of I.

Proof. The proof is quite equivalent as the proof of proposition 35. The constraints (1), ( 4) and ( 5) insure that ∪ s∈S x s induces a deterministic strategy profile. Indeed, the variables z over the actions define the choices of M IN and M AX (an action a chosen by one of the player is such that z a = 1, and 0 otherwise. Then constraint (6) defines exactly the variables y from the flux vectors (x s ) s∈S , and the constraints (2) and (3) insure the optimality of the solution.

We find a integer linear programming formulation for both RSP with termination inevitable and SSPG with termination inevitable. However, these formulation are not integral, even in the simpler case of RSP with termination inevitable.

Proposition 38

Linear relaxation of (P I RSP ) is not integral.

Proof. Let us consider the following instance of RSP with termination inevitable (in fact, a shortest path instance as there is no M AX player: in particular a Nash equilibrium is a shortest path arborescence) (figure 3.18). In order to prove that the extreme points of the linear relaxation of (P I RSP ) are not integer, we show that there is a weight function over (P I RSP ) and a fractional solution of better weight that the weight of any feasible integer solution.

SPECIAL CASES OF SSPG WITH TERMINATION INEVITABLE | 123

Let us define w 1 , w 2 , w 3 ∈ Z m and the objective function s∈{1,2,3} w s x s :

• w 1 = (100, 0, 0, 0, 1, 100)

• w 2 = (0, 1, 0, 100, 100, 0)

• w 3 = (0, 100, 100, 0, 0, 1) Figure 3.19 -Representation of w 1 (in blue), w 2 (in red) and w 3 (in green)

124| ON STOCHASTIC GAMES AND MAXPROB

The solution

x 1 = (0, 1 2 , 1 2 , 1 2 , 1 2 , 0), x 2 = ( 1 2 , 1 2 , 1 2 , 0, 0, 1 2 ), x 3 = ( 1 2 , 0, 0, 1 2 , 1 2 , 1 2
), and y = (0, 0, 0, 0) is a solution to the linear relaxation (figure 3.20). This solution has weight 1 2 + 1 2 + 1 2 = 3 2 . However, the optimal integer solution is the following (figure 3.21): Figure 3.21 -The (unique) optimal integer solution This solution corresponds to x 1 = (0, 0, 0, 0, 1, 0), x 2 = (0, 1, 0, 0, 0, 0), x 3 = (0, 0, 0, 0, 0, 1), y = (0, 0, 0, 0). Indeed, as we are looking for an integral solution, the solution is an 0anti-arborescence, and it is easy to see that any other 0-anti-arborescence induces a cost greater than 100. The value of this solution is 1+1+1 = 3. Thus, there exists a fractional solution of better weight than any integer solution, which proves the proposition. Now we know that the extreme points of the polyhedron of (P I RSP ) are not integer. However it could be interesting to study the convex hull of the integer solutions of this polyhedron. We have started to study this integer hull with tools like Porta on examples

INSTANCES OF RSP ∩ SSG | 125

and the results are not encouraging to carry on in this direction. Indeed, we strongly believe that, even thought we did not formalize proofs yet, that this linear programming formulation encapsulates NP-hard problems. We also could dig into alternative directions, like checking integer non emptiness only.

It is interesting to note that our counter-example does not involve nodes controlled by M AX. This means that it is an instance of deterministic shortest path. We can conclude that the following is not a linear programming formulation for the shortest path

x s (δ + (v)) -x s (δ -(v)) = 1 if v = s and v = 0 0 otherwise ∀s ∈ V x u a -x s a ≥ 0 ∀a = (u, v), u, s ∈ S, v ∈ N (u) y u -y v ≤ c a ∀a = (u, v) ∈ A, u ∈ V a∈A x s a c a = y s ∀s ∈ V (3.1)
The previous counter example show that (P I RSP ) is not a LP-formulation of the deterministic shortest path problem.

Instances of RSP ∩ SSG

We now restrict our attention to even simpler instances in our quest for LP formulation, that is, instances of RSP with termination inevitable which are also instances of stopping Simple Stochastic Games. We call the set of these instances stopping RSP∩SSG. An instance of stopping RSP∩SSG can be seen as an instance of stopping SSG where there is no average node.

Formally, an instance of stopping RSP∩SSG is a graph

G = ((V = V M IN ∪V M AX ), A) where V M IN is a finite set of nodes controlled by M IN and V M AX is finite set of nodes controlled by M AX. A is a set of arcs such that for all v ∈ V , |δ + (v)| ≤ 2. Just like for SSG, a (deterministic and stationary) policy for M IN (resp. for M AX) is a mapping Π M IN : V M IN → A (resp. Π M AX : V M AX → A) such that Π M IN (s) ∈ δ + (s) for all s ∈ V M IN (resp. Π M AX (s) ∈ δ + (s) for all s ∈ V M AX ).
There are two special sink nodes: 0 M IN and 0 M AX . We focus on instances where G is acyclic, so a pair of policies for M IN and M AX define an disjoint union of a 0 M IN -anti-arborescence and a 0 M AX -anti-arborescence. Thus, each node v ∈ V is connected exclusively to 0 M IN or 0 M AX . From a start node v 0 ∈ V and a pair of policies Π = (Π M IN , Π M AX ), we say that M IN wins if v 0 is connected to 0 M IN in the corresponding disjoint union of anti-arborescences, and that M AX wins if s 0 is connected to 0 M AX in this union. We give a simple algorithm to solve such instances: let G be an instance of stopping RSP∩SSG and let O be a topological order over the nodes of G (which exists since G is acyclic). Solving such instances boils down to labeling the nodes with 0 or 1, depending on if from it, M IN wins whatever the strategy of M AX is (then we label with 0 and with 1 otherwise). At the beginning of the algorithm, we can mark 0 M IN with 0 and 0 M AX with 1. As 0 M IN and 0 M AX are sinks, they can be assumed to be at the end of any topological order. Let us consider the nodes one by one, in opposite order of O. As I is an instance of SSG, each nodes has at most 2 neighbors, and can be either min or max. We label the current node according the following possible cases, according to the labels of his neighbors:

126| ON STOCHASTIC GAMES AND MAXPROB

• if the current node has only one neighbor, we label the current node with the label of its neighbor

• if the current node has exactly two neighbors, then we distinguish two cases:

the current node is min: if at least one of its neighbor's label is 0, we label the current node 0, and 1 otherwise the current node is max: if both its neighbor's labels are 0, we label the current node 0, and 1 otherwise Proposition 39 Once all the nodes are labeled, we can conclude who wins according to the label of the start node: if it is labeled 0, M IN wins and M AX wins otherwise (then the label is 1).

Proof. We prove this proposition by induction on the number of nodes. If there are only two nodes 0 M IN and 0 M AX , as we label 0 M IN with 0 and 0 M AX with 1, if v 0 = 0 M IN then min wins and max wins if v 0 = 0 M AX by definition.

INSTANCES OF RSP ∩ SSG | 127

Let us assume that the proposition is true for any graph composed of n -1 nodes. Let us consider a graph G n composed of n nodes. As G n is acyclic, we can define a topological order O over the nodes of G n . Let v be the first node in O, meaning that v has no incoming arc (and at most 2 outgoing arc). By induction, we can label the nodes of G n \ {v} such that from the nodes labeled 0, M IN wins and M AX wins from the nodes labeled 1. Then the proposition is true for all the nodes except v. Let us label v according to the different cases described above.

Let us assume that v ∈ V M IN (the same kind of proof can be made if v ∈ V M AX ).

If v has only one neighbor v , then if v is labeled 0, v is labeled with 0 and from v, M IN wins as v is connected to 0 M IN . Similarly, if v is labeled 1, v is labeled with 1 and from v, M AX wins since v is connected to 0 M AX .

If v has two neighbors then if at least of its neighbors v is labeled 0, we set Π M IN (v) = (v, v ) and from v, M IN wins. If all the neighbors of v are labeled 1, then we set Π M IN (s) to any of its outgoing arc and M AX wins from v.

Let us consider the following linear program, where v 0 ∈ V is the start node. We denote by N 1 ⊆ V the subset of V of nodes which have only 1 neighbor, and N 2 ⊆ V the subset of V of nodes which have exactly 2 neighbors. max y v 0 y i ≤ y j + y k ∀i ∈ V M AX ∩ N 2 , ∀(i, j), (i, k) ∈ A (1)

y i ≤ y j ∀i ∈ (V M AX ∩ N 1 ) ∪ V M IN , ∀(i, j) ∈ A (2) y 0 M IN = 0 (3) y 0 M AX = 1 (4)
(P I RSP ∩SSG )

In this linear program, y i represent the label of node i. The inequalities (1) and (2) force to label a node in V M AX to 0 if its neighbors are labeled 0 and to label a node in V M IN to 0 if at least one of its neighbor is 0. The objective function force to label a max node to 1 if at least one of its neighbor is 1, and a min node to be labeled to 1 if both of its neighbors is 1. Thus, if the optimal value of P RSP ∩SSG is 0, M IN wins from v 0 .

Note that if the optimal solution to the linear relaxation of P RSP ∩SSG is positive, then there exists a 0 -1 solution with y s = 1. Indeed, let y be an optimal solution with y s = > 0. Let ȳ be a 0 -1 vector over the nodes defined by ∀i ∈ V, ȳ(i) = y i . By definition of the constraints of P RSP ∩SSG , ȳ is a feasible solution of P RSP ∩SSG , of value 1. Thus, if the optimal value of P RSP ∩SSG is positive, we know that there exist a solution of value 1, and M AX is winning from s.

We think that the same logic might be applied to solve SSG. Indeed, even if we do not have a LP-formulation, we have defined a linear program, for which we can decide which player wins according to the optimal value, and a threshold (here the threshold is 0: if we have a optimal solution of positive cost, then we know that M AX wins). Even if we did not formalize it, we could define the same kind of linear program for SSG, and decide who wins according to whether or not the optimal solution has a value greater than 1 2 (in this case the threshold would be 1 2 ).

128| ON STOCHASTIC GAMES AND MAXPROB

Finally, the instance of RSP ∩ SSG are easy to solve. What happen if we introduce stochasticity in this problem ? If we re-introduce the average nodes, we come back to SSG. What if the transitions for player M AX were stochastic, with possibly different probabilities than 1 2 ? This is MAXPROB, so let us go back to this problem.

The MAXPROB Problem

As seen in chapter 1, MAXPROB is a special case of SSP. There are only two actions a M IN and a M AX that can lead to 0 with probability 1. These actions are available in only two states: respectively 0 M IN and 0 M AX . The costs of all actions are 0, except for a M AX which has cost 1. Thus, minimizing the expected cost of a proper policy is equivalent to maximizing the probability to reach state 0 M IN , as the only action that has non zero cost is a M AX , and a M AX is taken at most once. We refer to the first chapter for a formal definition of MAXPROB. As MAXPROB is a special case of SSP, there exists a LP formulation so MAXPROB can be solved in weakly polynomial time.

Proposition 40

If there exists a strongly polynomial algorithm to solve an instance of MAXPROB without transition cycle, then there exists a strongly polynomial algorithm to solve general instances.

Proof. Let I = (S, A, J, P, c) be an instance of MAXPROB with one only transition cycle x ≥ 0 (we can assume that there is only one transition cycle without loss of generality), and G I his graphical representation (see chapter 1 for more details on graphical representation of SSP). We remind the readers that a transition cycle is a solution x = 0 to (J -P ) T x = 0. We know that one can find a transition cycle in strongly polynomial time (see chapter 1 for more details).

THE MAXPROB PROBLEM | 129

As all the costs are 0 (except for a M AX ), the cost of a transition cycle x is c T x = 0, as x(a M AX ) = 0 for all transition cycle x.

Let S = {s ∈ S|P T x > 0} be the subset of reachable states if we perform actions a such that x(a) > 0. Let GI be the graph in which all nodes corresponding to the states of S have been contracted in one node s x and Ĩ the corresponding SSP instance. Then GI has no transition cycle. Let us assume that we can find an optimal (deterministic and stationary) policy Π of Ĩ in strongly polynomial time. Let us call s ∈ S the unique state such that J( Π(s x, s ) = 1, Let us now define Π * , a policy for instance I, such that:

Π * (s) =        Π(s) if s ∈ S \ S a such that x(a) > 0 if s ∈ S \ {s } Π(s x) if s = s
As Π is proper, and by definition of a transition cycle we know that Π * is proper. Then, as the cost of the transition cycle is 0, we have J Π * (s) = J Π(s x) for all s ∈ S. We conclude that Π * is an optimal policy for I, which proves the proposition.

We tried to answer the question of the existence of a strongly polynomial algorithm. For this quest, we can assume w.l.o.g that each action can lead to at most two states. We can easily generate an equivalent model with at most n 2 states and nm actions by repeating the following transformation:

In the LP-formulation of SSP, it results that we can assume there are at most three variables per inequality. With the help of László A. Végh, who is a specialist of strongly polynomial algorithms in combinatorial optimization, we tried to understand first to extend the results of [START_REF] Hochbaum | Simple and fast algorithms for linear and integer programs with two variables per inequality[END_REF] on linear programs with two variables per inequality. Even if we could not manage to extend the idea to find a strongly polynomial algorithm to solve MAXPROB. Our investigations were productive: László A. Végh found an error in the paper, and later corrected it. We understood from these first investigations that the quest of strongly polynomial time algorithm for MAXPROB was way too challenging and this is why we focused our research on games extensions of SSP where we though we had a better grip (even though as describe above, the open problems are very hard, but at least we could give some hopefully interesting directions).

130| ON STOCHASTIC GAMES AND MAXPROB

Conclusion and Perspectives

In this chapter we have studied variations of the Stochastic Shortest Path Problem, and in particular, we have to studied the existence of LP-formulations for some game extensions. The most natural 2-player stochastic game extension of the SSP is the Stochastic Shortest Path Game and even though we could not find a LP formulation for the problem, we could formulate what we believe is the first ILP formulation of the problem, which opens new ways to look at the problem from a polyhedral perspective and this is we believe a first contribution (it could provide an alternative to strategy iteration for instance which could be interesting to evaluate computationally). Even though we have started to investigate the integer hull exploiting tools like Porta, our first experiments suggested that hard inequalities would be needed and even though we did not formalize the proof yet, we strongly believe that the formulation encapsulate NP-hard problems which refrained us from pursuing in this direction. Therefore we restricted attention to simpler sub-problems for which existence of LP-formulation was still open. Our main contribution is a simple LP model that has the property that if the solution is positive, then it has an integer solution of value one (which provides a simple and original LP approach to answer the problem). We believe that this offers an interesting direction for further investigation for the SSG problem. Maybe no LPformulation exist but there might still be a LP model that has the property that z LP > 1 2 if and only if there exists a deterministic strategy that reaches 0 with probability more that 1 2 . By adding stochasticity to this last special case, we come back to a well known problem we have encountered in the first chapter: MAXPROB. For this last problem, we prove that we can focus only on instances without transition cycle. It is interesting to see that even if MAXPROB is a special case of SSP, we do not know if solving MAXPROB is easier than solving SSP.

Conclusion, Limites et Perspectives de Recherche

Dans ce manuscrit de thèse, nous nous sommes intéressés au problème de l'optimisation de stratégie dans le sport et plus particulièrement à l'optimisation de la stratégie des joueurs de golf. Comme nous l'avons vu, les joueurs professionnels peuvent participer à deux types de compétitions : les compétitions en Stroke Play et les compétitions en Match Play. Durant une compétition en Stroke Play, tous les joueurs en lice jouent les dix-huit trous du parcours, le gagnant est le joueur ayant obtenu le plus petit score à l'issu de celui-ci. Concernant les compétitions en Match Play, deux joueurs s'affrontent sur chaque trou se départageant un point par trou, le vainqueur étant le joueur ayant le plus de points à la fin du parcours.

Dans le premier chapitre, nous avons redéfini et élargi le cadre d'étude du plus court chemin stochastique. Ce problème avait été défini et largement étudié dans un cadre assez éloigné de notre communauté scientifique. Nous avons considéré le PCCS d'un point de vue polyédral, plus proche de nos domaines de compétences. Nous avons réussi à alléger les hypothèses d'existence d'une solution optimale (les cycles de transition de coût nul sont désormais autorisés) et prouvé que les algorithmes classiques de résolution préexistants (Value Iteration, Policy Iteration) convergeaient bien dans notre nouveau cadre d'étude. De plus, notre approche nous a permis d'appliquer des algorithmes, bien connus de notre communauté, au problème du plus court chemin stochastique. Cela nous a mené à définir et à prouver la convergence d'un nouvel algorithme de résolution basé sur l'algorithme du primal-dual qui peut s'apparenter à la version stochastique de l'algorithme de Dijkstra pour les plus courts chemins déterministes. Même si nous n'avons pas obtenu de résultats importants concernant la complexité théorique ou pratique de cet algorithme, cela nous a conduit à étudier un sous-problème connu de la communauté Intelligence Artificielle : MAXPROB. Ce problème est en fait un cas particulier de PCCS qui ne pouvait pas être résolu tel quel avec les algorithmes classiques de résolution des PCCS, notamment à cause de la présence potentielle de cycles de transition de coût nul. Avec l'allègement des conditions d'existence de solutions optimales, nous avons pu faire entrer MAXPROB dans le cadre classique d'étude. Malheureusement la complexité temporelle des algorithmes de résolution connus demeure exponentielle dans 132| Conclusion le pire cas, même dans ce cas particulier. Finalement, nous n'avons pas pu déterminer si MAXPROB était plus simple que le cas général des PCCS ou si il renfermait sa complexité.

La compréhension profonde de ce dernier problème aurait été doublement intéressante. D'abord d'un point de vue algorithmique : MAXPROB apparait naturellement quand on applique l'algorithme primal-dual au cas particulier du programme linéaire formulant les PCCS. La résolution efficace de ce problème pourrait potentiellement permettre de résoudre efficacement les PCCS. Sachant que l'existence d'algorithmes fortement polynomiaux pour résoudre les PCCS est une question ouverte très importante dans le domaine, une des pistes de recherche serait donc de trouver d'abord un algorithme fortement polynomial pour MAXPROB. D'autre part, ce problème étant un cas particulier des PCCS (les coûts ne valent que 0 et 1, on peut supposer qu'il n'y a pas de cycle de transition...), il est intéressant de l'étudier comme un problème 'élémentaire' afin de connaître l'essence de la difficulté des PCCS.

Dans le deuxième chapitre, nous avons détaillé la modélisation du "problème du golfeur" en PCCS. Après avoir défini les états, les actions et le coût de ces actions de manière assez naturelle, il nous a fallu définir la matrice de transition qui relate à la fois de la topologie du terrain mais aussi du niveau intrinsèque du joueur. Grâce à la base de données Américaine Shotlink [START_REF] Pga Tour | Shotlink intelligence program[END_REF], nous avons eu accès à des informations relatives aux coups des joueurs professionnels durant des compétitions internationales, comme par exemple la position de la balle avant et après le coup ou le type de terrain (fairway, rough, bunkers, green...) sur lequel le joueur a tiré. Ces données nous ont permis de créer des statistiques intrinsèques au joueur qui relatent de la déviation de ses coups. Nous avons ensuite simulé ces statistiques sur le trou considéré afin de créer la matrice de transition. Une fois l'instance de PCCS créée à partir des données du terrain et du joueur, nous avons résolu à l'optimal cette instance afin de déterminer la stratégie optimale du joueur. Les joueurs que nous avons considéré étant professionnels, nous avons supposé qu'ils jouaient leur stratégie optimale, ce qui nous a permis de créer un 'clone numérique' du joueur. En simulant ce clone sur les différents trous d'un parcours, nous pouvons établir une distribution du nombre de coups que le joueur jouera pour mettre la balle dans les dix-huit trous du parcours s'il s'agit d'une compétition en Stroke Play ou une probabilité de victoire face à son adversaire s'il s'agit d'une compétition en Match Play.

Tout au long de cette modélisation, nous avons fait des hypothèses que l'on peut classer en deux catégories : celles concernant la simulation du jeu de Golf et celles liées aux statistiques du joueur. Pour les premières, nous avons du faire des simplifications : on considère que le trou est plat, on ne prend pas en compte le roulement de la balle et la gestion des interactions entre la balle et les obstacles est simpliste. Il est clair que pour avoir un simulateur plus réaliste il serait intéressant d'intégrer (entre autres) tous ces aspects. Cependant ces hypothèses ne remettent pas en cause notre démarche globale et ces améliorations peuvent être apportées indépendamment de la partie optimisation du programme. Concernant les hypothèses faites afin de construire le profil théorique des joueurs, elles ont principalement été faites à l'aide de connaissances 'métier' des golfeurs.

| 133

L'intention des joueurs de viser le trou quand ils ne sont pas sur le tee et que le trou est atteignable est une hypothèse qui est discutable, la linéarité de la dépendance entre la déviation des coups et la distance de celui-ci, ainsi que le facteur constant reliant les déviations sur le fairway et le rough ou les bunkers sont des hypothèses qui nous ont parues naturelles à considérer dans un premier temps et peuvent sûrement être améliorées afin d'être plus réalistes. Une autre limite de notre modèle concerne la définition des paramètres nécessaires au traitement des données. Nous avons défini des paramètres afin de supprimer des données quand elles étaient aberrantes. Au niveau de la validation des résultats, notre principale difficulté a été de trouver une méthode satisfaisante sachant que le nombre de réalisations effectives était très limité. Ainsi, il est difficile de savoir à partir d'un faible échantillon si la viabilité du modèle est contestable ou si il s'agit uniquement de variance statistique. Ce manque de réalisation nous a également empêché d'utiliser des méthodes de validations statistiques plus classiques, comme le test du chi-2. Nous avons dû créer une méthode de validation ad-hoc qui a permis de déterminer si la réalisation que nous avons aurait pu être facilement simulée par notre modèle. Cette validation est bien sûr perfectible et des modèles de validations plus fins pourraient être développés afin d'avoir des critères plus objectifs relatant de la qualité du modèle. Concernant les résultats, on peut constater qu'on peut facilement simuler des scénarios probables, mais on ne pourra pas (ou presque pas) simuler des scénarios rares même avec une faible probabilité. Ce dernier point est une limite importante du modèle : dans un but de prédiction, il est dommage de ne pouvoir anticiper que les scénarios très probables.

Dans le troisième et dernier chapitre, nous nous sommes intéressés à une autre modélisation possible pour les compétitions en Match Play. Sachant que dans ce mode deux joueurs s'affrontent sur chaque trou avec des buts antagonistes, il parait naturel de vouloir modéliser ce problème comme un jeu de plus court chemin stochastique, qui est l'extension naturelle du PCCS à deux joueurs. Même si, au vu des expériences computationnelles du chapitre 2, la construction et la résolution de telles instances ne pourraient être faites en un temps raisonnable, nous nous sommes attelés à étudier théoriquement les jeux stochastiques à deux joueurs. Nous avons étudié les jeux de plus court chemin stochastique afin d'essayer de trouver des formulations programmation linéaire décrivant le problème, comme il en existe pour le PCCS. Le problème initial étant complexe, notre démarche a été de s'intéresser à des cas particuliers potentiellement plus simples. Nous avons donc étudié les jeux stochastiques simples, ainsi que le problème de plus court chemin robuste. Nous avons réussi à trouver une formulation linéaire en nombres entiers pour le plus court chemin robuste, qui peut se généraliser aux JPCCS.

Ce dernier chapitre ne comporte pas de résultats théoriques amajeurs. Il présente cependant un état de l'art sur ce que l'on connaît actuellement sur les JPCCS, ainsi que quelques résultats préliminaires. Nous espérons que cela pourra donner des idées de pistes de réflexion pour des recherches futures. Une des pistes qui nous apparait intéressante concerne le programme linéaire que nous avons défini pour les instances qui sont à la fois des instances de jeux stochastiques simples et de plus courts chemins robustes. Pour ces instances, nous avons défini un programme linéaire qui ne caractérise 134| Conclusion pas directement les solutions, mais telle que s'il existe une solution de coût strictement positif, alors il existe une solution de coût 1. Dans ce cas, nous pouvons définir une solution optimale à partir de la solution de coût 1. Nous pensons que le même type de raisonnement pourrait se généraliser aux instances de jeux stochastiques simples.

En plus d'apports théoriques, cette thèse comporte un aspect applicatif important. Le modèle décrit théoriquement dans le chapitre 2 pour formaliser le problème du golfeur en un PPCS a été implémenté en C++ et en R 'from scratch'. La partie de traitement des données, ainsi que la validation statistique a été faite en R, alors que la construction du modèle et l'optimisation a été faite en C++. L'intégralité du code est publique, afin que les résultats que nous avons trouvé soient reproductibles. Nous nous sommes également risqués à appliquer notre modèle de prédiction à la Ryder Cup 2018 qui a eu lieu en France. Avant la compétition nous avons créé un site [START_REF] Martin | Private Collaboration for a website creation[END_REF] qui rassemble nos prévisions. Tout au long de la compétition, nous avons mis à jour le site afin de donner des statistiques en temps réel. Le site est toujours disponible à l'adresse suivante : http://www.golfoptimization.com/. Les prévisions ont pu légèrement évoluer au vu des modifications que nous avons apporté au modèle depuis un an.

  score courante entre son adversaire et lui. On nomme M IN le joueur qui commence et M AX son adversaire. Pour un trou, on définit un ensemble d'états S, dont les états ont une forme générique du type s = (p M IN , p M AX , δ) avec p M IN la position de la balle de M IN sur le trou discrétisé, p M AX la position de la balle de M AX et δ ∈ Z la différence relative de score courante entre M IN et M AX : si l'on appelle s M IN ∈ N le score de M IN et s M AX ∈ N le score de M AX, on pose δ = s M IN -s M AX . L'état initial est donc s tee = (p tee , p tee , 0) avec p tee correspondant à la position du tee sur le trou. Même si la différence de score ne peut pas être bornée a priori (une différence de score quelconque engendrerait un ensemble d'états infini), on peut définir une différence de score D ∈ N qui n'a jamais été dépassée dans l'histoire du Golf (pour des joueurs professionnels, D ne dépasse généralement pas 2 ou 3 car en pratique, au delà d'une telle différence de score, le joueur en retard 'donne' le point à son adversaire). Dans la suite, on considèrera uniquement des joueurs professionnels, dont le niveau est assez proche pour que δ soit suffisamment facile à borner. On supposera donc que δ ∈ {-D, -D + 1, ..., D -1, D}. Un état (p M IN , p M AX , δ) est contrôlé par M IN si la distance de p M IN au trou est supérieure à la distance de p M AX au trou et est contrôlé par M AX sinon. Les actions disponibles en un état correspondent aux coups que peut jouer le joueur qui contrôle cet état. Quand M IN joue depuis s = (p M IN , p M AX , δ), la balle de M IN atterrit sur une autre position p M IN du trou et le nouvel état est s = (p M IN , p M AX , δ ) avec δ = δ + 1 ou δ = δ + 2 si M IN s'est vu octroyé une pénalité (une pénalité est octroyée dans des cas bien particuliers, qui sont indiqués dans les règles officielles du golf

a 11 .

 11 .. a 1n 1 0 0 ... 0 a 21 ... a 2n 0 1 0 ...

Théorème 14 Théorème 16

 1416 Dualité faible Soit (P ) un programme linéaire sous forme canonique et (D) son dual. Soit x ∈ R n une solution primal réalisable et y ∈ R m une solution dual réalisable. • on a c T x ≤ y T b • si (P ) est non borné, (D) est irréalisable • si (D) est non borné, (P ) est irréalisable Théorème 15 Dualité forte Soit (P ) un programme linéaire sous forme canonique et (D) son dual. (P ) admet une solution optimale x * si et seulement si (D) admet une solution optimale y * . De plus, si x * est une solution optimale pour (P ) et y * est une solution optimale pour (D), alors c T x * = b T y * . Écarts complémentaires Soit (P ) un programme linéaire sous forme canonique et (D) son dual. Soit x * ∈ R n et y * ∈ R m . x * et y * sont des solutions optimales de (P ) et (D), respectivement, si et seulement si : i x * est primal-réalisable et y * est dual-réalisable

Figure 1 -

 1 Figure 1 -Exemple d'un polyèdre et du polyèdre des solutions entières associé

  un exemple d'instance de PCC, dans lequel les sommets sont représentés par des cercles comprenant leurs étiquettes en leur centre, un arc a = (i, j) est représenté par une flèche allant de i à j et le coût d'un arc est indiqué à proximité de l'arc correspondant.

Figure 2 -

 2 Figure 2 -Représentation graphique d'une instance de PCC

Figure 1 .

 1 Figure 1.1 -A graphical representation of a SSP (with target state 0): circles are states, squares are actions, dashed arrows indicate state transitions (probabilities) for a given action, and black edges represent actions available in a given state with corresponding cost.

1 Figure 1 . 2 -

 112 Figure 1.2 -A deterministic shortest path (with target state 0): the dark "actions" represent the current policy, and the dashed "actions" have non positive reduced cost ; changing all actions with non positive reduced cost yield a new policy which is not proper.

Figure 2 . 1 -

 21 Figure 2.1 -The 15 th hole of Augusta National Golf Club

Figure 2 . 2 -

 22 Figure 2.2 -An illustration of our discretization approach

Figure 2 . 3 -

 23 Figure 2.3 -Probabilities of 1 and more putts according to the distance to the pin on the green (figure from [103])

Figure 2 . 5 -

 25 Figure 2.5 -Average number of putts according to the distance to the pin

14 )

 14 Figure 2.7 -Profile of Phil Mickelson for approach the Green on the Fairway

Figure 2 . 8 -Figure 2 . 9 -Figure 2 . 10 -

 2829210 Figure 2.8 -Profile of Phil Mickelson for approach the Green on Primary Rough

Figure 2 . 11 -

 211 Figure 2.11 -Profile of Phil Mickelson for around the Green on the Fairway

Figure 2 . 12 -Figure 2 . 13 -

 212213 Figure 2.12 -Profile of Phil Mickelson for around the Green on Primary Rough

Figure 2 . 15 -

 215 Figure 2.15 -Construction of a star

Figure 2 . 16 -

 216 Figure 2.16 -Star of Phil Mickelson for long game

Figure 2 . 17 -

 217 Figure 2.17 -Star of Phil Mickelson for middle game

Figure 2 . 18 -

 218 Figure 2.18 -Star of Phil Mickelson for short game

Figure 2 .

 2 Figure 2.19 -Regeneration of plausible data for Phil Mickelson for the long game

Figure 2 .

 2 Figure 2.20 -Regeneration of plausible data for Phil Mickelson for the middle game

Figure 2 . 21 -

 221 Figure 2.21 -Regeneration of plausible data for the short game

Figure 2 . 22 -

 222 Figure 2.22 -Full generated profile of Phil Mickelson on the Fairway

Figure 2 .

 2 Figure 2.23 -Regeneration of plausible data for Phil Mickelson for the long game on the rough

Figure 2 .

 2 Figure 2.24 -Regeneration of plausible data for Phil Mickelson for the middle game on the rough

Figure 2 . 25 -

 225 Figure 2.25 -Regeneration of plausible data for Phil Mickelson for the short game on the rough

Figure 2 . 26 -

 226 Figure 2.26 -Full generated profile of Phil Mickelson on the Rough

Figure 2 .

 2 Figure 2.28 -Regeneration of plausible data for Phil Mickelson for the middle game on bunkers

Figure 2 . 29 -

 229 Figure 2.29 -Regeneration of plausible data for Phil Mickelson for the short game on bunkers

Figure 2 . 30 -

 230 Figure 2.30 -Full generated profile of Phil Mickelson on the Bunkers

Figure 2 . 31 -

 231 Figure 2.31 -Driving of Phil Mickelson in 2018

Figure 2 . 32 -

 232 Figure 2.32 -Driving of Phil Mickelson in 2018 after statistical inference

Figure 2 . 33 -

 233 Figure 2.33 -Star for the Drive (Phil Mickelson, 2018)

Figure 2 . 34 -

 234 Figure 2.34 -Regenerated data for Phil Mickelson on the tee in 2018)

Figure 2 . 35 -

 235 Figure 2.35 -Part of an optimal policy of Phil Mickelson one the 15 th hole of Augusta National Golf Club. Each square represent a state, the optimal action on the corresponding state is represented as an arrow in the center with a distance in the bottom left corner

Figure 2 . 36 -

 236 Figure 2.36 -Part of an optimal policy of Phil Mickelson one the 15 th hole of Augusta National Golf Club with a larger scale

Figure 2 . 39 -

 239 Figure 2.39 -Histogram of expected number of shots for 10000 simulation of Phil Mickelson on the 1 st hole of Augusta National Golf Club)

Figure 2 . 40 -

 240 Figure 2.40 -Outline of the creation of H S

Figure 2 . 42 -

 242 Figure 2.42 -Outline of the creation of H E

Figure 2 . 44 -Figure 2 . 45 -

 244245 Figure 2.44 -Probability of victory of Phil Mickelson and Francesco Molinari on the 3 rd hole of Golf National

  Figure 2.46 -Probability of victory of Phil Mickelson and Francesco Molinari on Golf National

Figure 2 . 47 -

 247 Figure 2.47 -Outline of the creation of H E i

Figure 2 . 48 -

 248 Figure 2.48 -Outline of the creation of H K and d E

Figure 2 .

 2 Figure 2.49 -Histograma H K of Kolmogorov distances for Phil Mickelson in 2017

Figure 2 .

 2 Figure 2.50 -Bootstrapping for Mickelson-Molinari

  Figure 2.51 -histogram H K of Kolmogorov distances between H S and the H E i

Figure 2 .

 2 Figure 2.52 -histogram H K of Kolmogorov distances between H S and the H i

  = (p M IN , p M AX , δ) where p M IN (resp. p M AX ) is the position of the ball of M IN (resp. of M AX) on the discretized hole (typically 2D-coordinates) and δ ∈ Z is the current relative difference of scores between M IN and M AX. Let us call σ M IN ∈ Z + the current score of M IN and σ M AX ∈ Z + the current score of M AX,

  A state s = (p M IN , p M AX , δ) is controlled by M IN if the distance from p M IN to the flag is greater than the distance between p M AX and the flag, and is controlled by M AX otherwise. The actions available in a state are the shots of the player who controls this state. Each time M IN is playing from a state s = (p M IN , p M AX , δ), his ball ends up 3.1 INTRODUCTION | 99 in another position of the hole p M IN and the new state is s = (p M IN , p M AX

  An instance of a SSPG is defined by a tuple (S M IN , S M AX , A M IN , A M AX , J, P, c) where (S := S M IN ∪ S M AX , A = A M IN ∪ A M AX , J, P, c) is an instance of SSP and S M IN ∩ S M AX = {0}. We again assume w.l.o.g. that each action is available in exactly one state. A Min player controls the actions in the states S M IN , while a Max player controls the actions in the states S M AX . A (positional) strategy for player Min is a mapping Π M IN : S M IN → A M IN , and a (positional) strategy for player Max is a mapping Π M AX : S M AX → A M AX . The pair (Π M IN , Π M AX ) is called a (positional) strategy profile. A strategy profile Π = (Π M IN , Π M AX ) induces a policy Π = (Π M IN , Π M AX ) for the SSP instance defined by (S := S M IN ∪ S M AX ,

Figure 3 a

 3 Figure 3.1 -Example of an SSPG instance with I = (S M IN , S M AX , A M IN , A M AX , J, P, c) with S M IN = {s 1 , 0} (in red) , S M AX = {s 2 , s 3 , 0} (in blue), A M IN = {a 1 , a 2 } , A M AX = {a 3 , a 4 , a 5 } , c = (1, 2, 3, 1, 4), J =

  The representation is the same as the representation of SSP instances in chapter 1, but now the state nodes are colored according to the partition S M IN , S M AX of S, in particular the red nodes are controlled by player M IN , and the blue nodes are controlled by player M AX. As node 0 is 'controlled' neither by M IN nor M AX, it is colored in purple. An example is given in figure 3.1. The most famous algorithm to solve SSPG is Strategy Iteration.

Definition 30 (

 30 reduced cost) Let S = (S M IN , S M AX , A M IN , A M AX ,J, P, c) be an instance of SSPG with inevitable termination.

  The reduced cost cΠ (a) represent the relative gain to choose a with regards to Π. If cΠ (a) < 0, including a in the current policy should be interesting for M IN whereas if cΠ (a) > 0 it should be interesting for M AX to do so. Then we can define improving strategies for M IN and M AX like so. Definition 31 (improving strategy) Let S = (S M IN , S M AX , A M IN , A M AX , J, P, c) be an instance of SSPG with inevitable termination and Π = (Π M IN , Π M AX ) be a pair of deterministic and stationary policies for M IN and M AX. Let j ∈ {M IN, M AX} and B j ⊆ A j such that: • ∃a ∈ B j , cΠ (a) < 0 and ∀a ∈ B j , cΠ (a) ≤ 0 if j = M IN • ∃a ∈ B j , cΠ (a) > 0 and ∀a ∈ B j , cΠ (a) ≥ 0 if j = M AX • ∀s ∈ S, , a∈B j J(a, s) ≤ 1

Figure 3 . 2 -

 32 Figure 3.2 -Graphical representation of I with policy Π 1

Figure 3 . 3 -Figure 3 . 4 -Theorem 3 . 3

 333433 Figure 3.3 -Graphical representation of I with policy Π 2

Figure 3 . 5 -

 35 Figure 3.5 -Inclusions of SSPG, SSG and RSP

Figure 3 . 6 -

 36 Figure 3.6 -Inclusions SSG and SSPG with termination inevitable

Figure 3 . 7 -

 37 Figure 3.7 -Example of a SSG instance

  (S M IN , S M AX , A M IN , A M AX , A avg , J, P, c) where ((S M IN ∪ S avg ), S M AX , (A M IN ∪ A avg ), A M AX , J, P, c) is an instance of SSPG with termination inevitable. Moreover, for all state s ∈ S, a∈A J(a, s) ≤ 2, meaning that there is at most two actions available in each state. All actions A M IN ∪ A M AX are deterministic, the restriction of P to the actions of A M IN ∪A M AX contains only 0 and 1. The restriction of P to the actions of A avg contains only 0, 1 and 1 2 . There is a special state 0 M IN ∈ S M IN (resp. 0 M AX ∈ S M AX ) in which there is one only action that lead to 0 with probability 110| ON STOCHASTIC GAMES AND MAXPROB 1 and cost 0 (resp. with probability 1 and cost 1). The cost of all the other actions is 0, and cannot lead to state 0. Here the goal of M IN and M AX are pretty clear: since the only action that has positive cost is the outgoing action from 0 M AX , M IN wants to reach state 0 M IN and M AX want to reach state 0 M AX . A deterministic and stationary policy for M IN (resp. for M AX) is mapping Π M IN : S M IN → A M IN (resp. Π M AX : S M AX → A M AX ). Solving a stopping SSG instance is deciding whether or not there exist a deterministic and stationary policy Π * M AX such that for all deterministic and stationary Π M IN of M IN , we have J (Π M IN ,Π * M AX ) ≥ 1 2 . Note that as the only action which has a non-zero cost is the (only) action available in 0 M AX , the cost of a pair of strategies J (Π M IN ,Π M AX ) is exactly the probability to reach 0 M AX following Π M IN and Π M AX . Note that we artificially put the nodes of S avg under control of player M IN . We could have put them under control of player M AX without any consequences on the model, while only one action is available in nodes of S avg .A SSG is a special case of SSPG. The representation of the previous instance of SSG as an SSPG is given by figure 3.8.

Figure 3 . 8 -

 38 Figure 3.8 -Representation of the instance of SSG 3.7 as a SSPG

Figure 3 . 9 -

 39 Figure 3.9 -Counter-Example to D SP being a LP formulation of stopping SSGs (taken from [30] )

Figure 3 .

 3 Figure 3.10 -Inclusion of RSP and SSPG with termination inevitable

  (y * , z * ) be an optimal solution of (P I RSP _JM ). Then y * are optimal potentials: there exists Π * M IN ∈ Σ M IN an optimal policy for M IN such that y Π * M IN = y * .

Proposition 37

 37 Let I = (S M IN , S M AX , A M IN , A M AX , J, P, c) be an instance of SSPG, and G I = (V, A) his graphic representation. Let us consider the following linear program with A -

Figure 3 . 18 -

 318 Figure 3.18 -Example showing that the extreme points of the linear relaxation of (P I RSP ) are not integer

Figure 3 .

 3 Figure 3.20 -From left to right: representation of x 1 , x 2 and x 3

Figure 3 .

 3 Figure 3.22 -instances of Stopping RSP ∩ RSP with inevitable termination

Figure 3 . 23 -

 323 Figure 3.23 -Example of MAXPROB. All the actions have cost 0 except for a M AX which has cost 1

  • (P ) est dit irréalisable si et seulement si P = ∅ • (P ) est dit non-borné si seulement si ∀M ∈ R, ∃x ∈ P , c T x ≥ M Soit x ∈ R n et (P ) un programme linéaire sous forme canonique. x est un sommet de P si x ∈ P , et que pour tout x, x ∈ P , x = x+x 2 ⇒ x = x = x . On dit qu'un programme linéaire est sous forme standard si il est de la forme

	Proposition 5
	Soit (P ) un programme linéaire. Soit (P ) admet une solution optimale, soit il est irréal-
	isable, soit il est non-borné.
	Definition 6
	Definition 7
	Max

  De plus, si x est réalisable, on parlera de solution de base réalisable et B sera appelée base réalisable.

on peut toujours supposer que n > m, sinon l'ensemble des solutions réalisables est réduit à un point, car le rang de A est plein). L'unique vecteur 18| Introduction x ∈ R n solution de (P B Stand ) avec xN = 0 est appelé solution de base B.

  ..., n}, and a cost vector c ∈ R m . The state 0 is called the target state and the action 0 is the unique action available in that state. Action 0 leads to state 0 with probability 1. When confusion may arise, we denote state 0 by 0 S and action 0 by 0 A .

	1 -A graphical representation of a SSP (with target state 0): circles are states,
	squares are actions, dashed arrows indicate state transitions (probabilities) for a given
	action, and black edges represent actions available in a given state with corresponding
	cost.
	actions, J is a 0/1 matrix with m rows and n columns and general term J(a, s), for all
	a ∈ {1, ..., m} and s ∈ {1, ..., n}, with J(a, s) = 1 if and only if action a is available in
	state s, P is a row substochastic matrix 2 with m rows and n columns and general term
	P (a, s) := p(s|a) (probability of ending in s when taking action a), for all a ∈ {1, ..., m},
	s ∈ {1,

  2.24 2.25 2.26 2.27 2.28 2.29 2.30):

  90| GOLF STRATEGY OPTIMIZATION FOR PROFESSIONAL GOLFERS PERFORMANCES ESTIMATION ON THE PGA TOUR

	Name	d E	Quantiles
	Rory McIlroy	0.2423	[73%, 74%]
	Francesco Molinari	0.1248	[37%, 38%]
	Justin Thomas	0.1701	[52%, 53%]

  Definition 32 (best response) Let I = (S M IN , S M AX , A M IN , A M AX , J, P, C) be an instance of SSPG with inevitable termination, Π M IN ∈ Σ M IN and Π M AX ∈ Σ M AX . Π * M AX ∈ Σ M AX is a best response to Π M IN if and only if

  AX is a Nash Equilibrium if and only if Π M IN is a best response to Π M AX and Π M AX is a best response to Π M IN . M IN ∈ Σ M IN is a best response to a strategy Π M AX ∈ Σ M AX if and only if there is no improving strategy with regard to player M IN . Similarly, a strategy Π M AX ∈ Σ M AX is a best response to a strategy Π M IN ∈ Σ M IN if and only if there is no improving strategy with regard to player M AX. Proof. We know from chapter 1 that a strategy is optimal for SSP if and only if there is no action of negative reduced cost. Since fixing Π M IN or Π M AX leads to a (simplified) SSP problem for M IN or M AX, we have symmetrically Π M IN ∈ Σ M IN is a best response to a strategy Π M AX ∈ Σ M AX if and only if there is no action of negative reduced cost (no improving strategy with regards to M IN ), and Π M AX ∈ Σ M AX is a best response to a strategy Π M IN ∈ Σ M IN if and only if there is no action of positive reduced cost (no improving strategy with regards to M AX). Let I = (S M IN , S M AX , A M IN , A M AX , J, P, C) be an instance of SSPG and let Π = (Π M IN , Π M AX ) be a pair of deterministic and stationary strategies such that Π M IN is a best response to Π M AX . Let Π M AX be an improving strategy with regards to M AX, and Π M IN a best response to Π M AX . Then

	Lemma 3.1
	A strategy Π Lemma 3.2

On peut faire une telle hypothèse, quitte à dupliquer des actions.

Nous avons vu que le Stroke Play comme le Match Play peuvent se modéliser comme un plus court chemin stochastique ou un jeu de plus court chemin stochastique. Tandis que les états, les actions disponibles dans chaque état et les coûts de ces actions sont relativement naturels à définir, la matrice de transition, elle, est plus dure à caractériser. Elle décrit les probabilités d'atteindre les états quand on effectue une action. Elle renferme donc la complexité de la topologie du trou et surtout relate du niveau de précision des coups du joueur. Afin de construire cette matrice de transition, nous avons donc besoin de données relatives au joueur. Pour ce faire, nous avons utilisé une très grande base de données Américaine qui recense des millions d'informations relatives aux coups joués par des joueurs professionnels internationaux dans les compétitions Américaines, telles que les coordonnées de départ et d'arrivée de la balle, le type de terrain sur lequel le joueur a tiré, etc...[START_REF] Pga Tour | Shotlink intelligence program[END_REF].

We focus here on discrete time (infinite) horizon problems.

Observe that it is usually not a stochastic matrix as state 0 and action 0 are left out.

If not we simply duplicate the actions.

It is in general not a purely stochastic vector as state 0 is left out.

It is in general not a purely stochastic vector as action 0 is left out.

lim sup is used here as the limit need not be defined in general.

Note that it is not clear, a priori, whether such a policy exists.

same name but it refers to a small piece of wood T-shaped

i.e. the policy is the same for any starting state

Remerciements

Annex: The Shotlink Database

114| ON STOCHASTIC GAMES AND MAXPROB Figure 3.11 -Graphical representation of a RSP as a SSPG Figure 3.12 -Simplified graphical representation of a RSP At this point, RSP with termination inevitable can be seen with two different points of view. On the one hand, it can be seen as a special case of SSPG with termination inevitable. A solution is thus a pair of strategies Π = (Π M IN , Π M AX ) for M IN and M AX which forms a Nash Equilibrium, i.e. for which we have, in particular:

On the other hand, from the formulation above, the RSP can be seen as an optimization problem for M IN (just like Bertsekas does in [START_REF] Bertsekas | Robust shortest path planning and semicontractive dynamic programming[END_REF]). In this vision, an optimal solution is a policy for player M IN of minimum cost (the cost of a policy Π M IN ∈ Σ M IN is max Π M AX ∈Σ M AX J (Π M IN ,Π M AX ) ). We know that if Π = (Π M IN , Π M AX ) is a Nash equilibrium, then Π M IN is an optimal solution for the corresponding optimization problem.

If we consider only instances with termination inevitable, the solutions to the optimization problem are Nash equilibrium. Indeed in this case max

Definition 34

Let I be an instance of RSP seen as an optimization problem for M IN , and Π M IN ∈ Σ M IN any solution of I (a strategy for M IN ). Let s ∈ S, we define the potential of s with respect to Π M IN as:

are said to be the optimal potentials.

Note that, if we consider only instance with termination inevitable, there is no pair of policies for M IN and M AX such that the agent could 'loop' in the system. This implies that the graph that represents instances of RSP with termination inevitable is acyclic.

SPECIAL CASES OF SSPG WITH TERMINATION INEVITABLE | 115

In our representation, we color the chosen edges by M IN in red and by M AX in blue. We focus on deterministic policies and hence there is only one edge chosen for each state. Moreover, as the graph representing RSP with termination inevitable is acyclic, the subgraph induced by the selected edges is a 0-anti-arborescence. We give two examples of deterministic and stationary policies with the previous instance (figure 3.13).

Computational methods

We know that the Robust Shortest Path Problem is in P [START_REF] Bertsekas | Robust shortest path planning and semicontractive dynamic programming[END_REF]. We present two algorithms from [START_REF] Bertsekas | Robust shortest path planning and semicontractive dynamic programming[END_REF] a Bellman-like algorithm and Dijkstra-like one.

Bellman-like Algorithm

Let I = (S M IN , S M AX , A M IN , A M AX , J, P, c) be an instance of RSP with termination inevitable and G I = (V = V M IN ∪ V M AX , A) its graphical representation. As G I is acyclic, there exists a topological order O over the states (see the preliminaries for more details). We can apply a slightly modified version of Bellman algorithm for shortest path problem. Just like for Bellman algorithm, we will set and update labels y for each state v, that represent the potentials (here we see RSP as an optimization problem for M IN , so the optimal cost of a path is the cost incurred from v to 0 following the optimal policy for M IN that we are looking for). As 0 is a sink node, we can always assume that 0 is at the end of all topological order O and we set y(0) = 0. Then we update each node v one by one, following the reverse order of O:

To determine the strategy from the potentials, we only need to remember for which arc the min (resp. the max) has been obtained for the nodes in V M IN (resp. in V M AX ). We can prove inductively that it returns an optimal solution (an optimal strategy for M IN ).

Let us illustrate the previous algorithm on the following instance of RSP with the following topological order O = (s 1 , s 2 , s 4 , s 3 , s 5 , 0) (figure 3.14). Here are the different steps that lead to the optimal strategy Π * . We represent the labels y as a vector y = (y(s 1 ), y(s 2 ), y(s 3 ), y(s 4 ), y(s 5 ), y(0))

116| ON STOCHASTIC GAMES AND MAXPROB

SPECIAL CASES OF SSPG WITH TERMINATION INEVITABLE | 117

Dijkstra-like Algorithm

When the costs are non negative and even if termination is not inevitable, we can apply a Dijkstra-like algorithm. This algorithm is taken from [START_REF] Bertsekas | Robust shortest path planning and semicontractive dynamic programming[END_REF]. We slightly adjusted the algorithm to make it fit our framework: we symmetrize the points of view, and compute both strategies at the same time. Here again, we consider RSP as an optimization problem for M IN , so our goal is to find a policy of minimum cost for M IN .

Just like for Bellman-Like algorithm, we define labels y over the states. At the end of the algorithm, y(v) represents the optimal potential of v. We initialize y(0) = 0 and y(v) = ∞ for all v ∈ S \ {0}. We define two sets Y and Z that we set to: Y = ∅ and Z = {0} initially. At each step of the algorithm, Y represents the nodes for which the labels are the optimal potentials, and Z represent the nodes for which the labels have a finite value, but are maybe not the optimal potentials yet. The algorithm iterates until Z is empty.

Each iteration runs as follows (it generalizes naturally the standard Dijkstra's algorithm):

• we take from Z the state z * in V M IN of minimal label. As z * ∈ Z, the label of z * has finite value.

• as z * has minimum label, we can insure that its potential is optimal 2 . So we place it in Y .

• we update all the labels of the states u ∈ Z ∩ V M AX : if all the potentials of the neighbors of u are optimal. In this case the label of u is updated choosing the path incurring a maximum cost (best choice for M AX).

• we update all the labels of the states v ∈ Z ∩ V M IN if one choice induces a smaller cost. If we update, we now know that the label of u is finite, but may be not represent an optimal potential (so we place u in Z)

We give the outline of a Dijkstra-like algorithm. For all u ∈ V we denote by δ + (u) the outgoing arcs from u in G. (and by δ -(u) the incoming arcs to u in G). Once again, by looking for which arc the min or the max has been reached for y, we

118| ON STOCHASTIC GAMES AND MAXPROB

Algorithm 4 Dijkstra-like Algorithm

BIBLIOGRAPHY | 147

Un parcours de golf est composé de dix-huit trous. Sur chaque trou, le problème du golfeur est de déplacer la balle d'un point de départ prédéfini jusqu'au drapeau en un minimum de coups. Sous certaines hypothèses, ce problème peut se modéliser comme un problème de plus court chemin stochastique (PCCS). Le problème du PCCS est un processus de Markov particulier dans lequel un agent évolue dynamiquement dans un ensemble fini d'états. En chaque état, l'agent choisit une action, induisant un coût, qui le mène en un autre état en suivant une distribution de probabilité connue. Il existe également un état 'puits' particulier dans lequel, une fois atteint, on reste avec une probabilité un et un coût de zéro. Le but de l'agent est, depuis un état initial, d'atteindre l'état puits en un coût moyen minimal. Dans un premier chapitre, nous étudions de manière théorique le problème du PCCS. Après avoir redéfini un cadre d'étude dans lequel nous avons affaibli les hypothèses d'existence d'une solution optimale, nous avons prouvé que les algorithmes classiques de résolution convergent dans ce nouveau cadre. Nous avons également défini un nouvel algorithme de résolution basé sur l'algorithme primal-dual. Dans le deuxième chapitre, nous détaillons la modélisation du problème d'optimisation de stratégies au golf en un problème de PCCS. Grâce à la base de données Shotlink, nous définissons des 'clones numériques' de joueurs que nous pouvons faire jouer artificiellement sur différents parcours de golf afin de prédire les scores des joueurs. Nous avons appliqué ce modèle à deux compétitions : le master d'Augusta en 2017 et la Ryder Cup en 2018. Dans un troisième et dernier chapitre, nous étudions l'extension naturelle à deux joueurs du problème du PCCS : les jeux de plus courts chemins stochastiques. Nous étudions particulièrement les formulations programmation linéaire de ces jeux et de deux cas particuliers de ceux-ci.

A golf course consists of eighteen holes. On each hole, the golfer has to move the ball from the tee to the flag in a minimum number of shots. Under some assumptions, the golfer's problem can be modeled as a stochastic shortest path problem (SSP). SSP problem is a special case of Markov Decision Processes in which an agent evolves dynamically in a finite set of states. In each state, the agent chooses an action that leads him to another state following a known probability distribution. This action induces a cost. There exists a 'sink node' in which the agent, once in it, stays with probability one and a cost zero. The goal of the agent is to reach the sink node with a minimum expected cost. In the first chapter, we study the SSP problem theoretically. We define a new framework in which the assumptions needed for the existence of an optimal policy are weakened. We prove that the most famous algorithm still converge in this setting. We also define a new algorithm to solve exactly the problem based on the primal-dual algorithm. In the second chapter we detail the golfer's problem model as a SSP. Thanks to the Shotlink database, we create 'numerical clones' of players and simulate theses clones on different golf course in order to predict professional golfer's scores. We apply our model on two competitions: the master of Augusta in 2017 and the Ryder Cup in 2018. In the third chapter, we study the 2-player natural extension of SSP problem: the stochastic shortest path games. We study two special cases, and in particular linear programming formulation of these games.