Search

In this thesis, we develop accelerated algorithms for Markov decision processes (MDP) and more generally for zero-sum stochastic games (SG). We also address best approximation problems arising in tropical geometry.Dynamic programming is one of the main approaches used to solve MDP and SG problems. It allows one to transform a game to a fixed point problem involving an operator called Shapley operator (or Bellman operator in the case of MDP). Value iteration (VI) and policy iteration (PI) are the two main algorithms allowing one to solve these fixed point problems. However, in the case of large scale instances, or when we want to solve a mean payoff problem (where there is no discount factor for the payments received in the future), classical methods become slow.In the first part of this thesis, we develop two refinements of the classical value or policy iteration algorithms. We first propose an accelerated version of value iteration (AVI) allowing to solve affine fixed point problems with non self-adjoint matrices, alongside with an accelerated version of policy iteration (API) for MDP, building on AVI. This acceleration extends Nesterov accelerated gradient algorithm to a class of fixed point problems -- which cannot be interpreted in terms of convex programming. We characterize the spectra of matrices for which this algorithm does converge with an accelerated asymptotic rate. We also introduce an accelerated algorithm of degree d, and show that it yields a multiply accelerated rate of convergence under more demanding conditions on the spectrum of the matrices. Another contribution is a deflated version of value iteration (DVI) to solve the mean payoff version of stochastic games. This method allows one to transform a mean payoff problem to a discounted one under the hypothesis of existence of a distinguished state that is accessible from all other states and under all policies. Combining this deflation method with variance reduction techniques, we derive a sublinear algorithm solving mean payoff stochastic games.In the second part of this thesis, we study tropical best approximation problems. We first solve a tropical linear regression problem consisting in finding the best approximation of a set of points by a tropical hyperplane. We show that the value of this regression problem coincides with the maximal radius of a Hilbert's ball included in a tropical polyhedron, and that this problem is polynomial-time equivalent to mean payoff games. We apply these results to an inverse problem from auction theory. We study also a tropical analogue of low-rank approximation for matrices. This is motivated by approximate methods in dynamic programming, in which the value function is approximated by a supremum of elementary functions. We establish general properties of tropical low-rank approximation, and identify classes of low-rank approximation problems that are polynomial-time solvable. In particular, we show that the best tropical rank-one matrix approximation is equivalent to finding the minimal radius of a Hilbert's ball containing a tropical polyhedron., Dans cette thèse, nous développons des algorithmes accélérés pour les processus de décision Markoviens (MDP) et plus généralement pour les jeux stochastiques à somme nulle (SG). Nous abordons également les problèmes de meilleure approximation qui se posent en géométrie tropicale.La programmation dynamique est l'une des principales approches utilisées pour résoudre les problèmes MDP et SG. Elle permet de transformer un jeu en un problème de point fixe faisant intervenir un opérateur appelé opérateur de Shapley (ou opérateur de Bellman dans le cas de MDP). L'itération sur les valeurs (VI) et l'itération sur les politiques (PI) sont les deux principaux algorithmes permettant de résoudre ces problèmes de point fixe. Cependant, dans le cas d'instances à grande échelle, ou lorsque l'on veut résoudre un problème à paiement moyen (où il n'y a pas de facteur d'escompte pour les paiements reçus dans le futur), les méthodes classiques deviennent lentes.Dans la première partie de cette thèse, nous développons deux raffinements des algorithmes classiques d'itération sur les valeurs ou sur les politiques. Nous proposons d'abord une version accélérée de l'itération sur les valeurs (AVI) permettant de résoudre des problèmes de point fixe affines avec des matrices non auto-adjointes, ainsi qu'une version accélérée de l'itération sur les politiques (API) pour MDP, basée sur AVI. Cette accélération étend l'algorithme de gradient accéléré de Nesterov à une classe de problèmes de point fixe qui ne peuvent pas être interprétés en termes de programmation convexe. Nous caractérisons les spectres des matrices pour lesquelles cet algorithme converge avec un taux de convergence traduisant une accélération. Nous introduisons également un algorithme accéléré de degré d, et montrons qu'il donne un taux de convergence multi-accéléré sous des conditions plus exigeantes sur le spectre des matrices. Une autre contribution est une version déflatée de l'itération sur les valeurs (DVI) pour résoudre la version à paiement moyen des jeux stochastiques. Cette méthode permet de transformer un problème à paiement moyen en un problème escompté sous l'hypothèse d'existence d'un état distingué accessible depuis tous les autres états et sous toutes les politiques. En combinant cette méthode de déflation avec des techniques de réduction de la variance, nous obtenons un algorithme sous-linéaire résolvant les jeux stochastiques à paiement moyen.Dans la deuxième partie de cette thèse, nous étudions différents problèmes de meilleure approximation tropicale. Nous résolvons d'abord un problème de régression linéaire tropicale consistant à trouver la meilleure approximation d'un ensemble de points par un hyperplan tropical. Nous montrons que la valeur de ce problème de régression coïncide avec le rayon maximal d'une boule de Hilbert incluse dans un polyèdre tropical, et que ce problème est équivalent en temps polynomial aux jeux à paiement moyen. Nous appliquons ces résultats à un problème inverse de la théorie des enchères. Nous étudions également un analogue tropical de l'approximation de petit rang pour les matrices. Ceci est motivé par les méthodes approchées en programmation dynamique, dans lesquelles la fonction valeur est approximée par un supremum de fonctions élémentaires. Nous établissons des propriétés générales de l'approximation tropicale de petit rang et identifions des classes particulières de problèmes d'approximation de petit rang qui peuvent être résolus en temps polynomial. En particulier, nous montrons que la meilleure approximation matricielle tropicale de rang un équivaut à trouver le rayon minimal d'une boule de Hilbert contenant un polyèdre tropical.

In this work we study strong Stackelberg equilibria in stationary policies for discounted stochastic games, named (SSSE). We provide classes of games where the SSSE exists, and we prove via counterxamples that SSSE does not exist in the general case. We define suitable dynamic programming operators and we study their fixed points, named FPE. We show that the FPE and SSSE coincides for some games. In particular, we introduce the class of games with Myopic Follower Strategy, which have this property. We study the behaviour of Value Iteration, Policy Iteration and Mathematical programming formulations for this problem. Finally, we show an application in security in order to test the solution concepts and the efficiency of the algorithms studied in this article., PDR T0098.18., info:eu-repo/semantics/published

In this work we focus on Stackelberg equilibria for discounted stochasticgames. We begin by formalizing the concept of Stationary Strong Stackelberg Equlibrium(SSSE) policies for such games. We provide classes of games where the SSSE exists, andwe prove via counterexamples that SSSE does not exist in the general case. We definesuitable dynamic programming operators whose fixed points are referred to as FixedPoint Equilibrium (FPE). We show that the FPE and SSSE coincide for a class of gameswith Myopic Follower Strategy. We provide numerical examples that shed light on therelationship between SSSE and FPE and the behavior of Value Iteration, Policy Iterationand Mathematical programming formulations for this problem. Finally, we present asecurity application to illustrate the solution concepts and the efficiency of the algorithmsstudied in this article.; Dans cet article, nous nous focalisons sur les équilibres de Stackelbergpour pour les jeux stochastiques actualisés. Nous commençons par formaliser le conceptd’équilibre fort de Stackelberg en politiques stationnaires (Strong Stationary StackelbergEquilibria, SSSE) pour ces jeux. Nous exhibons des classes de jeux pour lesquels le SSSEexiste et nous montrons par des contre-exemples que les SSSE n’existent pas dans le casgénéral. Nous définissons des opérateurs de programmation dynamique appropriés pour ceconcept dont les points fixes sont nommés FPE (Fixed Point Equilibria). Nous montronsque le FPE et le SSSE coïncident pour la classe de jeux stochastiques avec stratégiedu “follower” myope (Myopic Follower Strategy, MFS). Nous montrons des exemplesnumériques qui éclairent la relation entre SSSE et FPE ainsi que le comportement desalgorithmes Value Iteration, Policy Iteration, et la formulation par ProgrammationMathématique de ce problème. Finalement, nous décrivons une application dans ledomaine de la sécurité pour illustrer les concepts de solution et l’efficacité des algorithmesintroduits dans cet article.

Nous étudions les jeux ramifiés introduits par Mio pour définir la sémantique du μ-calcul modal stochastique. Ces jeux stochastiques infinis à information imparfaite joués tour à tour par deux joueurs forment une sous-classe des jeux infinis à somme nulle. Elles étendent les jeux de Gale- Stewart en ce que chaque partie peut se scinder en sous-parties qui se déroulent indépendamment et simultanément. En conséquence, chaque partie a une structure arborescente, contrairement à la structure linéaire des parties des jeux de Gale-Stewart.Dans cette thèse, nous étudions les jeux ramifiés réguliers. Ceux-ci ont pour caractéristique d’avoir leurs ensembles gagnants régulières, c’est à dire, des ensembles d’arbres infinis reconnus par automates finis d’arbres. Nous nous intéressons aux problèmes de détermination, de calcul des valeurs de jeux ramifiés réguliers et de calcul effectif de la mesure d’un ensemble régulier d’arbres. De plus, nous utilisons des données réelles pour présenter comment on peut employer des techniques de la théorie des jeux stochastiques en pratique. Nous proposons une procédure générale qui à partir d’une série temporelle crée un modèle réactif capable de prédire l’évolution du système. Ce modèle facilite aussi les choix des stratégies permettant d’atteindre certains objectifs prédéfinis. La procédure nous sert ensuite à créer un jeux basé sur les processus décisionnels de Markov. Le jeu obtenu peut être utilisé pour prédire et contrôler le niveau d’infestation d’un verger expérimental., We study a class of games introduced by Mio to capture the probabilistic μ-calculi called branching games. They are a subclass of stochastic two-player zero-sum turn-based infinite-time games of imperfect information. Branching games extend Gale-Stewart games by allowing players to split the execution of a play into new concurrent sub-games that continue their execution independently. In consequence, the play of a branching game has a tree-like structure, as opposed to linearly structured plays of Gale-Stewart games.In this thesis, we focus our attention on regular branching games. Those are the branching games whose pay-off functions are the indicator functions of regular sets of infinite trees, i.e. the sets recognisable by finite tree automata. We study the problems of determinacy, game value computability and the related problem of computing a measure of a regular set of infinite trees.Moreover, we use real-life data to show how to incorporate game-theoretic techniques in practice. We propose a general procedure that given a time series of data extracts a reactive model that can be used to predict the evolution of the system and advise on the strategies to achieve predefined goals. We use the procedure to create a game based on Markov decision processes that is used to predict and control level of pest in a tropical fruit farm.

Delay-Tolerant Networks (DTNs) were designed to provide a sustainable means of communication between mobile terminals in regions without cellular infrastructure. In such networks, the set of neighbors of every node changes over time due to the mobility of nodes, resulting in intermittent connectivity and unstable routes in the network. We analyze the performance of an incentive scheme for two-hop DTNs in which a backlogged source pro- poses a fixed reward to the relays to deliver a message. Only one message at a time is proposed by the source. For a given message, only the first relay to deliver it gets the reward corresponding to this message thereby inducing a competition between the relays. The relays seek to maximize the expected reward for each message whereas the objective of the source is to satisfy a given constraint on the probability of message delivery. We consider two different settings: one in which the source tells the relays for how long a message is in circulation, and one in which the source does not give this information. In the first setting, we show that the optimal policy of a relay is of thresh- old type: it accepts a message until a first threshold and then keeps the message until it either meets the destination or reaches the second threshold. Formulas for computing the thresholds as well as probability of message delivery are derived for a backlogged source. We then investigate the asymptotic performance of this setting in the mean field limit. When the second thresh- old in infinite, we give the mean-field ODE and show that all the messages have the same probability of successful delivery. When the second threshold is finite we only give an ODE approximation since in this case the dynamics are not Markovian. For the second setting, we assume that the source proposes each message for a fixed period of time and that a relay decides to accept a message accord- ing to a randomized policy upon encounter with the source. If it accepts the message, a relay keeps it until it reaches the destination. We establish under which condition the acceptance probability of the relays is strictly positive and show that, under this condition, there exists a unique symmetric Nash equilibrium, in which no relay has anything to gain by unilaterally changing its acceptance probability. Explicit expressions for the probability of message delivery and the mean time to deliver a message at the symmetric Nash equilibrium are derived, as well as an expression of the asymptotic value of message delivery. Finally, we present numerous simulations results to compare performances of the threshold-type strategy and the randomized strategy, in order to determine under which condition it is profitable for the source to give the information on the age of a message to the relays; Les réseaux tolérants aux retards (DTN) ont été conçus pour fournir un moyen de communication durable entre terminaux mobiles dans les régions dépourvues d’infrastructure cellulaire. Dans de tels réseaux, l’ensemble des voisins de chaque nœud change au fil du temps en raison de la mobilité des nœuds, ce qui entraîne une connectivité intermittente et des routes instables dans le réseau. Nous analysons la performance d’un système d’incitation pour les DTN à deux sauts dans lequel une source en arriéré offre une récompense fixe aux relais pour délivrer un message. Un seul message à la fois est proposé par la source. Pour un message donné, seul le premier relais à le délivrer reçoit la récompense correspondant à ce message, induisant ainsi une compétition entre les relais. Les relais cherchent à maximiser la récompense attendue pour chaque message alors que l’objectif de la source est de satisfaire une contrainte donnée sur la probabilité de livraison du message. Nous considérons deux réglages différents : l’un dans lequel la source indique aux relais pendant combien de temps un message est en circulation, et l’autre dans lequel la source ne donne pas cette information. Dans le premier paramètre, nous montrons que la politique optimale d’un relais est de type seuil : il accepte un message jusqu’à un premier seuil et le conserve jusqu’à ce qu’il atteigne la destination ou le deuxième seuil. Les formules de calcul des seuils ainsi que de la probabilité de livraison des messages sont dérivées pour une source d’arriérés. Nous étudions ensuite la performance asymptotique de ce réglage dans la limite moyenne du champ. Lorsque le deuxième seuil est infini, nous donnons l’ODE du champ moyen et montrons que tous les messages ont la même probabilité de réussite. Lorsque le deuxième seuil est fini, nous ne donnons qu’une approximation ODE car dans ce cas, la dynamique n’est pas markovienne. Pour le second réglage, nous supposons que la source propose chaque message pour une période de temps fixe et qu’un relais décide d’accepter un message selon une politique randomisée lors d’une rencontre avec la source. S’il accepte le message, un relais le garde jusqu’à ce qu’il atteigne la destina- tion. Nous établissons dans quelle condition la probabilité d’acceptation des relais est strictement positive et montrons que, dans cette condition, il existe un équilibre de Nash symétrique unique, dans lequel aucun relais n’a quelque chose à gagner en changeant unilatéralement sa probabilité d’acceptation. Des expressions explicites pour la probabilité de livraison du message et le temps moyen de livraison d’un message à l’équilibre symétrique de Nash sont dérivées, ainsi qu’une expression de la valeur asymptotique de la livraison du message. Enfin, nous présentons de nombreux résultats de simulations pour com- parer les performances de la stratégie de type seuil et de la stratégie ran- domisée, afin de déterminer dans quelle condition il est rentable pour la source de donner l’information sur l’âge d’un message aux relais.

National audience; In various types of problems, such as sequential decision-making, heuristic search algorithms allow exploiting the knowledge of the initial situation and of an admissible heuristic to efficiently search for an optimal solution. Such algorithms exist including in case of uncertain dynamics, of partial observability, of multiple criteria, or of multiple collaborating agents. Here we propose a heuristic search algorithm for two-player zero-sum stochastic games with discounted criterion. This algorithm relies on HSVI—hence on generating trajectories. We demonstrate that, each player acting in an optimistic manner, and employing simple heuristic initializations, the resulting algorithm converges in finite time to an-optimal solution.; Dans divers types de problèmes, par exemple de prise de décision séquentielle, les algorithmes de recherche heuristique permettent d'exploiter la connaissance d'une situation initiale et d'une heuristique admissible pour rechercher efficacement une solution optimale. De tels algorithmes existent y compris en cas de dynamique incertaine, d'observabilité partielle, de critères multiples, ou d'agents multiples collaborant. Nous proposons ici un algorithme de recherche heuristique pour jeux stochastiques à deux joueurs et à somme nulle, et avec critère décompté, algorithme reposant sur HSVI—donc sur la génération de trajectoires. Nous démontrons que, chaque joueur agissant de manière optimiste, et en employant des initialisations heuristiques simples, l'algorithme obtenu converge vers une solution-optimale en temps fini.

We consider stochastic games that are played on finite graphs. The subject of the first part are two-player stochastic games with perfect information. In such games the two players take turns choosing actions from a finite set, for an infinite duration, resulting in an infinite play. The objective of the game is given by a Borel-measurable and bounded payoff function that maps infinite plays to real numbers. The first player wants to maximize the expected payoff, and the second player has the opposite objective, that of minimizing the expected payoff. We prove that if the payoff function is both shift-invariant and submixing then the game is half-positional. This means that the first player has an optimal strategy that is at the same time pure and memoryless. Both players have perfect information, so the actions are chosen based on the whole history. In the second part we study finite-duration games where the protagonist player has zero information. That is, he gets no feedback from the game and consequently his strategy is a finite word over the set of actions. Probabilistic finite automata can be seen as an example of such a game that has only a single player. First we compare two classes of probabilistic automata: leaktight automata and simple automata, for which the value 1 problem is known to be decidable. We prove that simple automata are a strict subset of leaktight automata. Then we consider half-blind games, which are two player games where the maximizer has zero information and the minimizer is perfectly informed. We define the class of leaktight half-blind games and prove that it has a decidable maxmin reachability problem.; On considère des jeux stochastiques joués sur un graphe fini. La première partie s’intéresse aux jeux stochastiques à deux joueurs et information parfaite. Dans de tels jeux, les joueurs choisissent des actions dans ensemble fini, tour à tour, pour une durée infinie, produisant une histoire infinie. Le but du jeu est donné par une fonction d’utilité qui associe un réel à chaque histoire, la fonction est bornée et Borel-mesurable. Le premier joueur veut maximiser l’utilité espérée, et le deuxième joueur veut la minimiser. On démontre que si la fonction d’utilité est à la fois shift-invariant et submixing alors le jeu est semi-positionnel. C’est-à-dire le premier joueur a une stratégie optimale qui est déterministe et sans mémoire. Les deux joueurs ont information parfaite: ils choisissent leurs actions en ayant une connaissance parfaite de toute l’histoire. Dans la deuxième partie, on étudie des jeux de durée fini où le joueur protagoniste a zéro information. C’est-à-dire qu’il ne reçoit aucune information sur le déroulement du jeu, par conséquent sa stratégie est un mot fini sur l’ensemble des actions. Un automates probabiliste peut être considéré comme un tel jeu qui a un seul joueur. Tout d’abord, on compare deux classes d’automates probabilistes pour lesquelles le problème de valeur 1 est décidable: les automates leaktight et les automates simples. On prouve que la classe des automates simples est un sous-ensemble strict de la classe des automates leaktight. Puis, on considère des jeux semi-aveugles, qui sont des jeux à deux joueurs où le maximiseur a zéro information, et le minimiseur est parfaitement informé. On définit la classe des jeux semi-aveugles leaktight et on montre que le problème d’accessibilité maxmin est décidable sur cette classe.

The problems addressed and results obtained in this thesis are divided in two parts. The first part concerns the study of the asymptotic value of frequency-dependent games (FD-games). We introduce a differential game associated to the FD-game whose value leads to a Hamilton-Jacob-Bellman-lsaacs equation. Although an irregularity occurs at the origin, we prove existence of the value in the differential game played over [0.1 ], which allows to prove that the value of the FD-game, as the number of stages tend to infinity, converges to the value of the continuous-time game with initial state 0. ln the second part, the objective is the decomposition of the space of finite games in subspaces of suitable games which admit disguised equilibria and more tractable analysis. This part is divided in two chapters. In the first chapter, we establish a canonical decomposition of an arbitrary game into three components and we characterize the approximate equilibria of a given game in terms of the uniform equilibrium and the equilibrium in dominant strategies that appear in its components. In the second part, we introduce a family of inner products in the space of finite games and we define the class of harmonic games relatively to the chosen inner product. Inspired of the Helmholtz-Hodge decomposition applied to games by Candogan et al (2011 ), we establish an orthogonal decomposition of the space of finite games with respect to the chosen inner product, in the subspaces of potential harmonic and non-strategic games and we further generalize several results of Candogan et al (2011)., Les problèmes abordés et les résultats obtenus dans cette thèse se divisent en deux parties. La première concerne l'étude de la valeur asymptotique de jeux dépendant de la fréquence (jeux-FD). Nous introduisons un jeu différentiel associé au jeu-FD dont la valeur se ramène à une équation de Hamilton-Jacobi-Bellman-lsaacs. En affrontant un problème d'irrégularité à l'origine, nous prouvons l’existence de la valeur du jeu différentiel sur [0.1 ] et ceci nous permet de prouver que la valeur du jeu FD converge vers la valeur du jeu continu qui débute à l'état initial 0. Dans la deuxième partie, l'objectif fondamental est la décomposition de l'espace des jeux finis en sous espaces des jeux adéquats et plus faciles à étudier vu que leurs équilibres sont distingués. Cette partie est divisée en deux chapitres. Dans le premier chapitre, nous établissons une décomposition canonique de tout jeu arbitraire fini en trois composantes et nous caractérisons les équilibres approximatifs d'un jeu donné par les équilibres uniformément mixtes et en stratégies dominantes lesquels apparaissent sur ses composantes. Dans le deuxième chapitre, nous introduisons sur l'espace des jeux finis une famille de produits scalaires et nous définissons la classe des jeux harmoniques relativement au produit scalaire choisi dans cette famille. Inspiré par la décomposition de Helmholtz-Hodge appliquée aux jeux par Candogan et al. (2011), nous établissons une décomposition orthogonale de l'espace des jeux finis, par rapport au produit scalaire choisi, en les sous espaces des jeux potentiels, des jeux harmoniques et des jeux non­stratégiques c nous généralisons les résultats de Candogan et al. (2011).

This dissertation studies limit properties in optimal control problems (one-player, in continuous time) and in zero-sum repeated games (two-player, in discrete time) with large horizons. More precisely, we investigate the convergence of the value function when the duration of the control problem or the repetition of the game tends to infinity (the asymptotic analysis), and the existence of robust strategies, i.e. ԑ-optimal strategies to guarantee the limit value in all control problems with sufficiently long durations or in all repeated games with sufficiently large repetitions (the uniform analysis). The part on optimal control is composed of three chapters. Chapter 2 is a survey article on recent literature of long-term properties in various models of dynamic optimization. In the following two chapters, we focus on optimal control problems where the running cost is evaluated by a general probability measure, instead of the usual T-horizon average (Cesàro mean) or the λ-discount (Abel mean). In Chapter 3, we introduce an asymptotic regularity condition for a sequence of probability measures on positive real numbers which induces a horizon tending to infinity (in particular T tending to infinity or λ tending to zero) for the control problem. We prove that for any sequence of evaluations satisfying this condition, the associated sequence of value function of the control problem converges uniformly if and only if this sequence is totally bounded for the uniform norm. We deduce that for control problems defined on a compact invariant domain and satisfying some non expansive condition, the value function defined by a general probability measure converges as the evaluation becomes sufficiently regular. Further, we prove in Chapter 4 that under the same compact and non expansive conditions, there exist ԑ-optimal controls for all problems where the running cost is evaluated by a sufficiently regular probability measure. The part on repeated games consists of two chapters. Chapter 5 is devoted to the study of a subclass of absorbing games with one-sided incomplete information. The model we consider is a generalization of Big match with one-sided incomplete information introduced by Sorin (1984). We prove the existence of the limit value, Maxmin, Minmax, and that Maxmin is equal to the limit value. In Chapter 6, we establish several results for recursive games. We first consider recursive games with a countable state space and prove that if the family of n-stage value functions is totally bounded for the uniform norm, then the uniform value exists. In particular, the uniform convergence of n-stage values implies the uniform convergence of λ-discounted values. Combined with a result in Rosenberg and Vieille (2000), we deduce a uniform Tauberian theorem for recursive games. Second, we use the existence result of uniform value to a class of the generalized models of repeated games and prove that both the limit value and Maxmin exist and are equal. This class of repeated games are recursive games with signals where player 1 can always deduce the signal of player 2 from his own along the play., Cette thèse étudie des propriétés limites de problèmes de contrôle optimal (un joueur, en temps continu) et de jeux répétés à somme nulle (à deux joueurs, en temps discret) avec horizon tendant vers l'infini. Plus précisément, nous étudions la convergence de la fonction valeur lorsque la durée du problème de contrôle ou la répétition du jeu tend vers l'infini (analyse asymptotique), et l'existence de stratégies robustes, i.e. des stratégies ԑ-optimales pour guarantir la valeur limite dans tous les problèmes de contrôle de durée suffisamment longue ou dans tous les jeux répétés de répétition suffisamment large (analyse uniforme). La partie sur le contrôle optimal est composée de trois chapitres. Le chapitre 2 est un article de présentation de la littérature récente sur les propriétés à long terme dans divers modèles d'optimisation dynamique. Dans les deux chapitres suivants, nous nous concentrons sur les problèmes de contrôle optimal où le coȗt de la trajectoire est évalué par une mesure de probabilité générale sur R_+, au lieu de la moyenne de T-horizon (moyenne de Cesàro) ou de la λ-escompté (moyenne d'Abel). Dans le chapitre 3, nous introduisons une condition de régularité asymptotique pour une suite de mesures de probabilité sur R_+ induisant un horizon tendant vers l'infini (en particulier, T tendant vers l'infini ou λ tendant vers zéro). Nous montrons que pour toute suite d'évaluations satisfaisant cette condition, la suite associée des valeurs du problème de contrôle converge uniformément si et seulement si cette suite est totalement bornée pour la norme uniforme. On en déduit que pour des problèmes de contrôle définis sur un domaine invariant compact et vérifiant une certaine condition de non-expansivité, la fonction valeur définie par une mesure de probabilité générale converge quand l'évaluation devient suffisamment régulière. En outre, nous prouvons dans le chapitre 4 que sous les mȇmes conditions de compacité et de non-expansivité, il existe des contrôles ԑ-optimaux pour tous les problèmes où le coȗt de la trajectoire est évalués par une mesure de probailité suffisamment régulières. La partie sur les jeux répétés se compose de deux chapitres. Le chapitre 5 est consacré à l'étude d'une sous-classe de jeux absorbants à information incomplète d'un côté. Le modèle que nous considérons est une généralisation du Big match à information incomplète d'un côté introduit par Sorin (1984). Nous démontrons l'existence de la valeur limite, du Maxmin, du Minmax, et l'égalité du Maxmin et de la valeur limite. Dans le chapitre 6, nous établissons plusieurs résultats concernant des jeux récursifs. Nous considérons d'abord les jeux récursifs avec un espace dénombrable d'états et prouvons que si la famille des fonctions valeur des jeux à n étapes est totalement bornée pour la norme uniforme, alors la valeur uniforme existe. En particulier, la convergence uniforme des valeurs des jeux à n étapes implique la convergence uniforme des valeurs des jeux escomptés. à l'aide d'un résultat dans Rosenberg et Vieille (2000), on en déduit un théorème taubérien uniforme pour les jeux récursifs. Deuxièmement, nous appliquons le résultat d'existence de la valeur uniforme à une classe des modèles général de jeux répétés et nous prouvons que la valeur limite et le Maxmin existent et sont égaux. Ces jeux répétés sont des jeux récursifs avec signaux où le joueur 1 peut toujours déduire le signal du joueur 2 de son propre signal.

In this thesis we describe some links between a) discrete and continuous time games and b) games with finitely many players and games with a continuum of players. A motivation to the subject and the main contributions are outlined in Chapter 2. The rest of the thesis is organized in three parts: Part I is devoted to differential games, describing the different approaches for establishing the existence of the value of two player, zero sum differential games in Chapter 3 and pointing out connections between them. In Chapter 4 we provide a proof of the existence of the value using an explicit description of ε-optimal strategies and a proof of the equivalence of minimax solutions and viscosity solutions for Hamilton-Jacobi-Isaacs equations in Chapter 5. Part II concerns discrete time mean field games. We study two models with different assumptions, in particular, in Chapter 6 we consider a compact action space while in Chapter 7 the action space is finite. In both cases we derive the existence of an ε-Nash equilibrium for a stochastic game with finitely many identical players, where the approximation error vanishes as the number of players increases. We obtain explicit error bounds in Chapter 7 where we also obtain the existence of an ε-Nash equilibrium for a stochastic game with short stage duration and finitely many identical players, with the approximation error depending both on the number of players and the duration of the stage. Part III is concerned with two player, zero sum stochastic games with short stage duration, described in Chapter 8. These are games where a parameter evolves following a continuous time Markov chain, while the players choose their actions at the nodes of a given partition of the positive real axis. The continuous time dynamics of the parameter depends on the actions of the players. We consider three different evaluations for the payoff and two different information structures: when players observe the past actions and the parameter and when players observe past actions but not the parameter., Cette thèse étudie les liens entre a) les jeux en temps discret et continu, et b) les jeux à très grand nombre de joueurs identiques et les jeux avec un continuum de joueurs. Une motivation pour ces sujets ainsi que les contributions principales de cette thèse sont présentées dans le Chapitre 1. Le reste de la thèse est organisé en trois parties. La Partie I étudie les jeux différentiels à somme nulle et à deux joueurs. Nous décrivons dans le Chapitre 3 trois approches qui ont été proposées dans la littérature pour établir l’existence de la valeur dans les jeux différentiels à deux joueurs et à somme nulle, en soulignant les liens qui existent entre elles. Nous fournissons dans le Chapitre 4 une démonstration de l’existence de la valeur à l’aide d’une description explicite des stratégies ε optimales. Le Chapitre 5 établit l’équivalence entre les solutions de minimax et les solutions de viscosité pour les équations de Hamilton-Jacobi-Isaacs. La Partie II porte sur les jeux à champ moyen en temps discret. L’espace d’action est supposé compact dans le Chapitre 6, et fini dans le Chapitre 7. Dans les deux cas, nous obtenons l’existence d’un ε- équilibre de Nash pour un jeu stochastique avec un nombre fini de joueurs identiques, où le terme d’approximation tend vers zéro lorsque le nombre de joueurs augmente. Nous obtenons dans le Chapitre 7 des bornes d’erreur explicites, ainsi que l’existence d’un ε-équilibre de Nash pour un jeu stochastique à durée d’étape évanescente et à un nombre fini de joueurs identiques. Dans ce cas, le terme d’approximation est fonction à la fois du nombre de joueurs et de la durée d’étape. Enfin, la Partie III porte sur les jeux stochastiques à durée d’étape évanescente, qui sont décrits dans le Chapitre 8. Il s’agit de jeux où un paramètre évolue selon une chaîne de Markov en temps continu, tandis que les joueurs choisissent leurs actions à des dates discrètes. La dynamique en temps continu dépend des actions des joueurs. Nous considérons trois évaluations différentes pour le paiement et deux structures d’information : dans un cas, les joueurs observent les actions passées et le paramètre, et dans l’autre, seules les actions passées sont observées.

Game theory proved to be very useful in the field of verification of open reactive systems. This is due to the wide variety of games' model that differ in the way players interact and the amount of information players have. In this thesis, we study the value problem for games where players have full knowledge on their current configuration of the game, partial knowledge, and no knowledge. In the case where players have perfect information, we study the value problem for objectives that consist in combination of qualitative and quantitative conditions. In the case of one player stochastic games, we show that the values are computable in polynomial time and show that the optimal strategies exist and can be implemented with finite memory. We also showed that our construction for parity and positive-average Markov decision processes extends to the case of two-player stochastic games. In the case where the players have partial information, we study the value problem for reachability objectives. We show that computing the set of states with value 1 is an undecidable problem and introduce a decidable subclass for the value 1 problem. This sub class is PSPACE-complete in the case of blind controllers and EXPTIME is the setting of games with partial observations.; La théorie des jeux est un outils standard quand il s'agit de l'étude des systèmes réactifs. Ceci est une conséquence de la variété des modèles de jeux tant au niveau de l'interaction des joueurs qu'au niveau de l'information que chaque joueur possède. Dans cette thèse, on étudie le problème de la valeur pour des jeux où les joueurs possèdent une information parfaite, information partiel et aucune information. Dans le cas où les joueurs possèdent une information parfaite sur l'état du jeu, on étudie le problème de la valeur pour des jeux dont les objectifs sont des combinaisons booléennes d'objectifs qualitatifs et quantitatifs. Pour les jeux stochastiques à un joueur, on montre que les valeurs sont calculables en temps polynomiale et on montre que les stratégies optimales peuvent être implementées avec une mémoire finie. On montre aussi que notre construction pour la conjonction de parité et de la moyenne positive peut être étendue au cadre des jeux stochastiques à deux joueurs. Dans le cas où les joueurs ont une information partielle, on étudie le problème de la valeur pour la condition d'accessibilité. On montre que le calcul de l'ensemble des états à valeur 1 est un problème indécidable, on introduit une sous classe pour laquelle ce problème est décidable. Le problème de la valeur 1 pour cette sous classe est PSPACE-complet dans le cas de joueur aveugle et dans EXPTIME dans le cas de joueur avec observations partielles.

Irreversible games are stochastic games in which once the play leaves a state it never revisits that state. This class includes absorbing games. This paper proves the existence and a characterization of the asymptotic value for any finite irreversible game with incomplete information on both sides. This result extends Mertens and Zamir 1971 for repeated games with incomplete information on both sides, and Rosenberg 2000 for absorbing games with incomplete information on one side., Les jeux irréversibles sont des jeux stochastiques où une fois un état est quitté, il n'est plus jamais revisité. Cette classe contient les jeux absorbants. Cet article démontre l'existence et une caractérisation de la valeur asymptotique pour tout jeu irréversible fini à information incomplète des deux côtés. Cela généralise Mertens et Zamir 1971 pour les jeux répétés à information incomplète des deux côtés et Rosenberg 2000 pour les jeux absorbants à information incomplète d'un côté.

Explicit formulas for the asymptotic value and the asymptotic minmax of finite discounted absorbing games are provided. New simple proofs for the existence of the limits when the players are more and more patient (i.e. when the discount factor goes zero) are given. Similar characterizations for stationary Nash equilibrium payoffs are obtained. The results may be extended to absorbing games with compact action sets and jointly continuous payoff functions.

His manuscript presents dynamic foundations of population games with variable number of players and their solutions and stability concepts. We first introduce delayed evolutionary game dynamics and study their stability. Applications to both wired and wireless networks are presented. We then introduce mobility and spatial aspects of players distribution into the network dynamics. This leads to a new class of game dynamics with multicomponent strategies and migration constraints called evolutionary game dynamics with migration. We derived such dynamics for hybrid systems such as power control in heterogenous networks, switching between technologies and migration between different classes of users. After that we focus on stochastic population games with multiple classes of players in which each player has its own state and facing to an evolving vector which represents the population profile. We use this model to analyze resource and energy constrained interactions in wireless networks. Finally, we present a class of mean field games. When taking the asymptotics of finite systems, we derive a new class of game dynamics called mean field game dynamics. This class contains the standard evolutionary game dynamics based on revision of pure actions. We apply this model to analyze spatial random access game and dynamic resource competition game with individual states. We establish a link betweenmean field games and differential population games inwhich each player optimizes its long-term objective during its sojourn time in the system subject to the constraint that the population profile evolves according to some mean field game dynamics, Ce manuscrit présente les fondements dynamiques des jeux de population avec un nombre variable de joueurs ainsi que leurs concepts de solutions et de stabilités. Nous introduisons d'abord les dynamiques de jeux avec retard et étudions leurs stabilités. Nous les appliquons aux réseaux filaires et aux réseaux sans fils. Ensuite nous nous intéressons aux aspects de mobilité et aux distributions spatiales des joueurs sur le réseau. Cela nous conduit à une nouvelle classe de dynamique de jeux à stratégies vectorielles avec des contraintes de migrations, appelée dynamique de jeux d'évolution avec migration. Nous dérivons de telles dynamiques pour les réseaux hybrides et appliquons aux problèmes de contrôle de puissance dans les réseaux hétérogènes, choix entre plusieurs technologies et migration entre plusieurs classes d'utilisateurs. Ensuite nous nous focalisons aux jeux stochastiques de population avec plusieurs classes de joueurs dans lesquels chaque joueur possède son propre état et fait face un vecteur qui évolue dans le temps. Des applications à la gestion d'énergie dans les réseaux sont présentées. Finalement, nous étudions une classe de jeux à champ moyen. Lorsque la taille de la population devient très grande, les asymptotiques du système conduisent à des dynamiques appelées dynamiques de jeux à champ moyen. Cette classe de dynamiques contient les dynamiques standard basées sur des révisions de stratégies. Nous utilisons ce modèle pour analyser les problèmes accès aléatoires à des ressources dans un environnement où les utilisateurs et les ressources sont spatialement distribuées. Nous établissons un lien entre les jeux à champ moyen et les jeux différentiels de population dans lesquels chaque joueur a son état individuel et optimise son paiement à long terme pendant son temps de séjour dans le système sous contraintes que le profil de population évolue selon une dynamique de jeux à champ moyen

His manuscript presents dynamic foundations of population games with variable number of players and their solutions and stability concepts. We first introduce delayed evolutionary game dynamics and study their stability. Applications to both wired and wireless networks are presented. We then introduce mobility and spatial aspects of players distribution into the network dynamics. This leads to a new class of game dynamics with multicomponent strategies and migration constraints called evolutionary game dynamics with migration. We derived such dynamics for hybrid systems such as power control in heterogenous networks, switching between technologies and migration between different classes of users. After that we focus on stochastic population games with multiple classes of players in which each player has its own state and facing to an evolving vector which represents the population profile. We use this model to analyze resource and energy constrained interactions in wireless networks. Finally, we present a class of mean field games. When taking the asymptotics of finite systems, we derive a new class of game dynamics called mean field game dynamics. This class contains the standard evolutionary game dynamics based on revision of pure actions. We apply this model to analyze spatial random access game and dynamic resource competition game with individual states. We establish a link betweenmean field games and differential population games inwhich each player optimizes its long-term objective during its sojourn time in the system subject to the constraint that the population profile evolves according to some mean field game dynamics, Ce manuscrit présente les fondements dynamiques des jeux de population avec un nombre variable de joueurs ainsi que leurs concepts de solutions et de stabilités. Nous introduisons d'abord les dynamiques de jeux avec retard et étudions leurs stabilités. Nous les appliquons aux réseaux filaires et aux réseaux sans fils. Ensuite nous nous intéressons aux aspects de mobilité et aux distributions spatiales des joueurs sur le réseau. Cela nous conduit à une nouvelle classe de dynamique de jeux à stratégies vectorielles avec des contraintes de migrations, appelée dynamique de jeux d'évolution avec migration. Nous dérivons de telles dynamiques pour les réseaux hybrides et appliquons aux problèmes de contrôle de puissance dans les réseaux hétérogènes, choix entre plusieurs technologies et migration entre plusieurs classes d'utilisateurs. Ensuite nous nous focalisons aux jeux stochastiques de population avec plusieurs classes de joueurs dans lesquels chaque joueur possède son propre état et fait face un vecteur qui évolue dans le temps. Des applications à la gestion d'énergie dans les réseaux sont présentées. Finalement, nous étudions une classe de jeux à champ moyen. Lorsque la taille de la population devient très grande, les asymptotiques du système conduisent à des dynamiques appelées dynamiques de jeux à champ moyen. Cette classe de dynamiques contient les dynamiques standard basées sur des révisions de stratégies. Nous utilisons ce modèle pour analyser les problèmes accès aléatoires à des ressources dans un environnement où les utilisateurs et les ressources sont spatialement distribuées. Nous établissons un lien entre les jeux à champ moyen et les jeux différentiels de population dans lesquels chaque joueur a son état individuel et optimise son paiement à long terme pendant son temps de séjour dans le système sous contraintes que le profil de population évolue selon une dynamique de jeux à champ moyen

National audience; L'objectif est de développer de nouveaux algorithmes permettant la commande distribuée d'une smart surface et la coopération entre les micro actionneurs (valves pneumatiques) pour trier et positionner de façon optimale et robuste les pièces sur la smart surface. Ces algorithmes doivent permettre de commander un grand nombre de micro actionneurs, de prendre en compte l'hétérogénéité de leurs comportements et de gérer les coopérations entre actionneurs. L'approche que nous proposons pour commander ce système massivement distribué est fondée sur l'apprentissage par renforcement et les environnements multiagents. Le point de vue distribué permet de surmonter l'explosion combinatoire du nombre de commandes possibles. L'application de l'apprentissage par renforcement à un environnement multiagent constitue un réel challenge dû à l'apprentissage simultané des agents qui rompt l'hypothèse markovienne traditionnelle des méthodes d'apprentissage par renforcement.

Quitting games are I-player sequential games in which, at any stage, each player has the choice between continuing and quitting. The game ends as soon as at least one player chooses to quit; player i then receives a payoff, which depends on the set of players that did choose to quit. If the game never ends, the payoff to each player is zero. We study a four-player game, where the simplest equilibrium profile is cyclic with period two. We also use geometrical arguments to show why techniques that work for 3-player games cannot be applied in general., Les jeux d'arrêt sont des jeux séquentiels où, à chaque étape, chacun des joueurs peut décider d'arrêter ou de continuer. Le jeu s'arrête dès lors que l'un au moins des joueurs décide de s'arrêter. Le paiement reçu alors par les joueurs dépend de l'ensemble des joueurs qui ont choisi de s'arrêter à cette date. Si le jeu ne s'arrête jamais, le paiement est nul. Nous étudions un jeu à quatre joueurs. Dans ce jeu, les équilibres les plus simples sont périodiques de période deux. Par ailleurs, nous utilisons des outils géométriques pour montrer que les techniques utilisées pour les jeux à trois joueurs ne peuvent être adaptées au cas général.

This is a survey of recent results on stopping games, prepared for the forthcoming book Annals of Dynamic Games, ed A. Nowak, Ce texte présente des résultats récents sur les jeux d'arrêts. Il a été préparé pour l'ouvrage collectif à paraître, Annals of Dynamic Games, ed A. Nowak

This is a contribution to appear in Proceedings of the NATO ASI on Stochastic Games (editors: A. Neyman and S. Sorin). It deals with the existence of equilibrium payoffs in a class of recursive stochastic games., Ce texte est à paraître dans les Proceedings of the NATO ASI on Stochastic Games (volume préparé sous la direction de A. Neyman et S. Sorin). Il traite de l'existence de paiements d'équilibres dans une classe de jeux stochastiques récursifs.

This is a survey of recent results on stochastic games, prepared for the le Handbook of Game Theory, vol 3., eds. R.J. Aumann et S. Hart, Nous présentons des résultats récents sur les jeux stochastiques finis. Ce texte est à paraître dans le Handbook of Game Theory, vol 3., eds. R.J. Aumann et S. Hart

We study zero-sum stochastic games in which players do not observe the actions of the opponent. Rather, they observe a stochastic signal that may depend on the state, and on the pair of actions chosen by the players. We assume each player observes the state and his own action. We propose a candidate for the max-min value, which does not depend on the information structure of player 2. We prove that player 2 can defend the proposed max-min value, and that in absorbing games player 1 can guarantee it. Analogous results hold for the min-max value. This paper thereby unites several results due to Coulomb., Nous étudions les jeux stochastiques à somme nulle où les joueurs n'observent pas nécessairement les actions choisies par leur adversaire. Nous supposons seulement que chacun des joueurs observe au moins l'état courant du jeu, ainsi que sa propre action. L'article propose un traitement unifié de plusieurs résultats dus à Coulomb.

Game theory proved to be very useful in the field of verification of open reactive systems. This is due to the wide variety of games' model that differ in the way players interact and the amount of information players have. In this thesis, we study the value problem for games where players have full knowledge on their current configuration of the game, partial knowledge, and no knowledge. In the case where players have perfect information, we study the value problem for objectives that consist in combination of qualitative and quantitative conditions. In the case of one player stochastic games, we show that the values are computable in polynomial time and show that the optimal strategies exist and can be implemented with finite memory. We also showed that our construction for parity and positive-average Markov decision processes extends to the case of two-player stochastic games. In the case where the players have partial information, we study the value problem for reachability objectives. We show that computing the set of states with value 1 is an undecidable problem and introduce a decidable subclass for the value 1 problem. This sub class is PSPACE-complete in the case of blind controllers and EXPTIME is the setting of games with partial observations., La théorie des jeux est un outils standard quand il s'agit de l'étude des systèmes réactifs. Ceci est une conséquence de la variété des modèles de jeux tant au niveau de l'interaction des joueurs qu'au niveau de l'information que chaque joueur possède. Dans cette thèse, on étudie le problème de la valeur pour des jeux où les joueurs possèdent une information parfaite, information partiel et aucune information. Dans le cas où les joueurs possèdent une information parfaite sur l'état du jeu, on étudie le problème de la valeur pour des jeux dont les objectifs sont des combinaisons booléennes d'objectifs qualitatifs et quantitatifs. Pour les jeux stochastiques à un joueur, on montre que les valeurs sont calculables en temps polynomiale et on montre que les stratégies optimales peuvent être implementées avec une mémoire finie. On montre aussi que notre construction pour la conjonction de parité et de la moyenne positive peut être étendue au cadre des jeux stochastiques à deux joueurs. Dans le cas où les joueurs ont une information partielle, on étudie le problème de la valeur pour la condition d'accessibilité. On montre que le calcul de l'ensemble des états à valeur 1 est un problème indécidable, on introduit une sous classe pour laquelle ce problème est décidable. Le problème de la valeur 1 pour cette sous classe est PSPACE-complet dans le cas de joueur aveugle et dans EXPTIME dans le cas de joueur avec observations partielles.