Dissertationen zum Thema „Apprentissage automatique – Jeux“

Dans cette thèse nous étudions différentes généralisations du problème dit « du bandit manchot ». Le problème du bandit manchot est un problème de décision séquentiel au cours duquel un agent sélectionne successivement des actions et obtient une récompense pour chacune d'elles. On fait généralement l'hypothèse que seule la récompense associée à l'action choisie est observée par l'agent, ce dernier ne reçoit aucune information sur les actions non choisies. Cette hypothèse s'avère parfois très restrictive pour certains problèmes très structurés tels que les systèmes de recommandations, la publicité en ligne, le routage de paquets, etc. Il paraît assez naturel de tenir compte de la connaissance de la structure du problème pour améliorer les performances des algorithmes d'apprentissage usuels. Dans cette thèse, nous nous focalisons sur les problèmes de bandits présentant une structure pouvant être modélisée par un graphe dont les nœuds représentent les actions. Dans un premier temps, nous étudierons le cas où les arêtes du graphe modélisent les similitudes entre actions. Dans un second temps, nous analyserons le cas où l'agent observe les récompenses de toutes les actions adjacentes à l'action choisie dans le graphe. Notre contribution principale a été d'élaborer de nouveaux algorithmes permettant de traiter efficacement les problèmes évoqués précédemment, et de démontrer théoriquement et empiriquement le bon fonctionnement de ces algorithmes. Nos travaux nous ont également amenés à introduire de nouvelles grandeurs, telles que la dimension effective et le nombre d'indépendance effectif, afin de caractériser la difficulté des différents problèmes
This thesis studies several extensions of multi-armed bandit problem, where a learner sequentially selects an action and obtain the reward of the action. Traditionally, the only information the learner acquire is about the obtained reward while information about other actions is hidden from the learner. This limited feedback can be restrictive in some applications like recommender systems, internet advertising, packet routing, etc. Usually, these problems come with structure, similarities between users or actions, additional observations, or any additional assumptions. Therefore, it is natural to incorporate these assumptions to the algorithms to improve their performance. This thesis focuses on multi-armed bandit problem with some underlying structure usually represented by a graph with actions as vertices. First, we study a problem where the graph captures similarities between actions; connected actions tend to grand similar rewards. Second, we study a problem where the learner observes rewards of all the neighbors of the selected action. We study these problems under several additional assumptions on rewards (stochastic, adversarial), side observations (adversarial, stochastic, noisy), actions (one node at the time, several nodes forming a combinatorial structure in the graph). The main contribution of this thesis is to design algorithms for previously mentioned problems together with theoretical and empirical guaranties. We also introduce several novel quantities, to capture the difficulty of some problems, like effective dimension and effective independence number

Les émotions jouant un rôle essentiel dans les rapports humains, il est important de développer des méthodologies pour évaluer les états émotionnels ressentis par un utilisateur lorsqu'il interagit avec des ordinateurs. Dans le domaine de la conception des jeux vidéo en particulier, ce besoin est primordial. Dans ce contexte, les mesures physiologiques ont un avantage clé parce qu'elles permettent un accès à des processus inconscients. Mais, faire correspondre des motifs physiologiques à des émotions reste encore une tâche extrêmement difficile. Dans cette thèse, nous développons un modèle d'apprentissage automatique le plus adapté à cette tâche particulière. Nous avons considéré deux méthodologies: l'apprentissage automatique par des arbres de décision flous, et la construction automatique de prototypes flous grâce aux calculs de typicalité. Grâce à ce modèle, nous avons développé un contrôleur flou psychophysiologique capable de mesurer de manière continue des états émotionnels.

La programmation des jeux de reflexion fut consideree comme the drosophilia melanogaster of machine intelligence. Ce domaine devait permettre l'elaboration de techniques et d'algorithmes reutilisables dans d'autres domaines de l'intelligence artificielle. Selon c. Shannon, il s'agit d'un sujet sensible ou l'avancee est facilement communicable au public. Nous abordons cette question dans le cadre de programmes de jeux devant repondre a un probleme dans des conditions de tournois. Nous comparons les differentes recherches minimax basees sur des elagages alpha-beta avec l'algorithme negac* que nous avons defini et donnons les principaux resultats que nous avons etablis sur sa complexite. Nous definissons, dans le paradigme negamax, le nouvel algorithme de recherche de nombre de preuves et nous le comparons avec notre programme d'echecs ecume, dans le cadre des recherches de mats. Nous exposons un ensemble d'heuristiques qui permettent de rendre les recherches negamax plus rapides et plus fiables en explicitant les options que nous avons prises dans nos programmes d'echecs. Nous presentons nos resultats sur la parallelisation de la recherche minimax pour une machine distribuee: la connection machine 5. Ils nous ont permis de definir une nouvelle methode que nous avons comparee aux meilleures methodes connues jusqu'alors, sur des arbres de jeux simules et reels. Nous continuons par la presentation de notre methode de construction de fonctions d'evaluation en expliquant comment nous avons pu introduire la notion de plan strategique. Nous montrons aussi comment construire automatiquement une fonction d'evaluation par apprentissage dans la finale roi et dame contre roi et dame. Enfin, nous decrivons l'ensemble des caracteristiques de nos programmes d'echecs, dont cumulus 2. 0 qui a remporte le titre de vice-champion du monde d'echecs logiciels toutes categories

Les systèmes collaboratifs à large échelle, où un grand nombre d’utilisateurs collaborent pour réaliser une tâche partagée, attirent beaucoup l’attention des milieux industriels et académiques. Bien que la confiance soit un facteur primordial pour le succès d’une telle collaboration, il est difficile pour les utilisateurs finaux d’évaluer manuellement le niveau de confiance envers chaque partenaire. Dans cette thèse, nous étudions le problème de l’évaluation de la confiance et cherchons à concevoir un modèle de confiance informatique dédiés aux systèmes collaboratifs. Nos travaux s’organisent autour des trois questions de recherche suivantes. 1. Quel est l’effet du déploiement d’un modèle de confiance et de la représentation aux utilisateurs des scores obtenus pour chaque partenaire ? Nous avons conçu et organisé une expérience utilisateur basée sur le jeu de confiance qui est un protocole d’échange d’argent en environnement contrôlé dans lequel nous avons introduit des notes de confiance pour les utilisateurs. L’analyse détaillée du comportement des utilisateurs montre que: (i) la présentation d’un score de confiance aux utilisateurs encourage la collaboration entre eux de manière significative, et ce, à un niveau similaire à celui de l’affichage du surnom des participants, et (ii) les utilisateurs se conforment au score de confiance dans leur prise de décision concernant l’échange monétaire. Les résultats suggèrent donc qu’un modèle de confiance peut être déployé dans les systèmes collaboratifs afin d’assister les utilisateurs. 2. Comment calculer le score de confiance entre des utilisateurs qui ont déjà collaboré ? Nous avons conçu un modèle de confiance pour les jeux de confiance répétés qui calcule les scores de confiance des utilisateurs en fonction de leur comportement passé. Nous avons validé notre modèle de confiance en relativement à: (i) des données simulées, (ii) de l’opinion humaine et (iii) des données expérimentales réelles. Nous avons appliqué notre modèle de confiance à Wikipédia en utilisant la qualité des articles de Wikipédia comme mesure de contribution. Nous avons proposé trois algorithmes d’apprentissage automatique pour évaluer la qualité des articles de Wikipédia: l’un est basé sur une forêt d’arbres décisionnels tandis que les deux autres sont basés sur des méthodes d’apprentissage profond. 3. Comment prédire la relation de confiance entre des utilisateurs qui n’ont pas encore interagi ? Etant donné un réseau dans lequel les liens représentent les relations de confiance/défiance entre utilisateurs, nous cherchons à prévoir les relations futures. Nous avons proposé un algorithme qui prend en compte les informations temporelles relatives à l’établissement des liens dans le réseau pour prédire la relation future de confiance/défiance des utilisateurs. L’algorithme proposé surpasse les approches de la littérature pour des jeux de données réels provenant de réseaux sociaux dirigés et signés
Large-scale collaborative systems wherein a large number of users collaborate to perform a shared task attract a lot of attention from both academic and industry. Trust is an important factor for the success of a large-scale collaboration. It is difficult for end-users to manually assess the trust level of each partner in this collaboration. We study the trust assessment problem and aim to design a computational trust model for collaborative systems. We focused on three research questions. 1. What is the effect of deploying a trust model and showing trust scores of partners to users? We designed and organized a user-experiment based on trust game, a well-known money-exchange lab-control protocol, wherein we introduced user trust scores. Our comprehensive analysis on user behavior proved that: (i) showing trust score to users encourages collaboration between them significantly at a similar level with showing nick- name, and (ii) users follow the trust score in decision-making. The results suggest that a trust model can be deployed in collaborative systems to assist users. 2. How to calculate trust score between users that experienced a collaboration? We designed a trust model for repeated trust game that computes user trust scores based on their past behavior. We validated our trust model against: (i) simulated data, (ii) human opinion, and (iii) real-world experimental data. We extended our trust model to Wikipedia based on user contributions to the quality of the edited Wikipedia articles. We proposed three machine learning approaches to assess the quality of Wikipedia articles: the first one based on random forest with manually-designed features while the other two ones based on deep learning methods. 3. How to predict trust relation between users that did not interact in the past? Given a network in which the links represent the trust/distrust relations between users, we aim to predict future relations. We proposed an algorithm that takes into account the established time information of the links in the network to predict future user trust/distrust relationships. Our algorithm outperforms state-of-the-art approaches on real-world signed directed social network datasets

Cette thèse s'intéresse à l'analyse des données longitudinales, potentiellement grandes selon les trois axes suivants : nombre d'individus, fréquence d'observation et nombre de covariables. A partir de ces données, éventuellement censurées, nous considérons comme facteur d'étude le temps d'apparition d'un ou plusieurs évènements. Nous cherchons dans des classes de modèles à coefficients dépendant du temps à estimer l’intensité d’apparition des événements. Or les estimateurs actuels, ne permettent pas de traiter efficacement un grand nombre d’observations et/ou un grand nombre de covariables. Nous proposons un nouvel estimateur défini via la vraisemblance complète de Cox et une pénalisation permettant à la fois la sélection de variables et de forcer, quand c’est possible, les coefficients à être constants. Nous introduisons des algorithmes d'optimisation proximaux, permettant d'estimer les coefficients du modèle de manière efficace. L'implémentation de ces méthodes en C++ et dans le package R coxtv permet d'analyser des jeux de données de taille supérieure à la mémoire vive; via un streaming du flux de données et des méthodes d'apprentissage en ligne, telles que la descente de gradient stochastique proximale aux pas adaptatifs. Nous illustrons les performances du modèle sur des simulations en nous comparant aux méthodes existantes. Enfin, nous nous intéressons à la problématique du design des jeux vidéo. Nous montrons que l'application directe de ce modèle, sur les grands jeux de données dont dispose l'industrie du jeu vidéo, permet de mettre en évidence des leviers d'amélioration du design des jeux étudiés. Nous nous intéressons d'abord à l'analyse des composantes bas niveau, telles que les choix d'équipement fait par les joueurs au fils du temps et montrons que le modèle permet de quantifier l'effet de chacun de ces éléments de jeu, offrant ainsi aux designers des leviers d'amélioration direct du design. Enfin, nous montrons que le modèle permet de dégager des enseignements plus généraux sur le design tels que l'influence de la difficulté sur la motivation des joueurs
This thesis focuses on longitudinal time to event data possibly large along the following tree axes : number of individuals, observation frequency and number of covariates. We introduce a penalised estimator based on Cox complete likelihood with data driven weights. We introduce proximal optimization algorithms to efficiently fit models coefficients. We have implemented thoses methods in C++ and in the R package coxtv to allow everyone to analyse data sets bigger than RAM; using data streaming and online learning algorithms such that proximal stochastic gradient descent with adaptive learning rates. We illustrate performances on simulations and benchmark with existing models. Finally, we investigate the issue of video game design. We show that using our model on large datasets available in video game industry allows us to bring to light ways of improving the design of studied games. First we have a look at low level covariates, such as equipment choices through time and show that this model allows us to quantify the effect of each game elements, giving to designers ways to improve the game design. Finally, we show that the model can be used to extract more general design recommendations such as dificulty influence on player motivations

Les décisions de justice contiennent des informations déterministes (dont le contenu est récurrent d'une décision à une autre) et des informations aléatoires (à caractère probabiliste). Ces deux types d'information rentrent en ligne de compte dans la prise de décision d’un juge. Les premières peuvent la conforter dans la mesure où l’information déterministe est un élément récurrent et bien connu de la jurisprudence (i.e. des résultats d’affaires passées). Les secondes, apparentées à des caractères rares ou exceptionnels, peuvent rendre la prise de décision difficile et peuvent elles-mêmes modifier la jurisprudence. L’objet de cette thèse est de proposer un modèle d’apprentissage profond mettant en évidence ces deux types d’information afin d’en étudier leur impact (contribution) dans la prise de décision d’un juge. L'objectif est d’analyser des décisions similaires, de mettre en évidence les informations aléatoires et déterministes dans un corpus de décisions et de quantifier leur importance dans le processus de jugement
Judicial decisions contain deterministic information (whose content is recurrent from one decision to another) and random information (probabilistic). Both types of information come into play in a judge's decision-making process. The former can reinforce the decision insofar as deterministic information is a recurring and well-known element of case law (ie past business results). The latter, which are related to rare or exceptional characters, can make decision-making difficult, since they can modify the case law. The purpose of this thesis is to propose a deep learning model that would highlight these two types of information and study their impact (contribution) in the judge’s decision-making process. The objective is to analyze similar decisions in order to highlight random and deterministic information in a body of decisions and quantify their importance in the judgment process

Cette thèse porte sur le domaine de la découverte causale, c’est-à-dire la construction de graphes causaux à partir de données observées, et en particulier, la découverte causale temporelle et la reconstruction de larges réseaux de régulation de gènes. Après un bref historique, ce mémoire introduit les principaux concepts, hypothèses et théorèmes aux fondements des graphes causaux ainsi que les deux grandes approches : à base de scores et à base de contraintes. La méthode MIIC (Multivariate Information-based Inductive Causation), développée au sein de notre laboratoire est ensuite décrite avec ses dernières améliorations : Interpretable MIIC. Les problématiques et solutions mises en œuvre pour construire une version temporelle (tMIIC) sont exposées ainsi que les benchmarks traduisant les avantages de tMIIC sur d’autres méthodes de l’état de l’art. L’application à des séquences d’images prises au microscope d’un environnement tumoral reconstitué sur des micro-puces permet d’illustrer les capacités de tMIIC à retrouver, uniquement à partir des données, des relations connues et nouvelles. Enfin, cette thèse introduit l’utilisation d’un a priori de conséquence pour appliquer la découverte causale à la reconstruction de réseaux de régulation de gènes. En posant l’hypothèse que tous les gènes, hormis les facteurs de transcription, sont des conséquences, il devient possible de reconstruire des graphes avec des milliers de gènes. La capacité à identifier des facteurs de transcription clés de novo est illustrée par une application à des données de séquençage d’ARN en cellules uniques avec identification de deux facteurs de transcription susceptibles d’être impliqués dans le processus biologique d’intérêt
This thesis focuses on the field of causal discovery : the construction of causal graphs from observational data, and in particular, temporal causal discovery and the reconstruction of large gene regulatory networks. After a brief history, this thesis introduces the main concepts, hypotheses and theorems underlying causal graphs as well as the two main approaches: score-based and constraint-based methods. The MIIC (Multivariate Information-based Inductive Causation) method, developed in our laboratory, is then described with its latest improvements: Interpretable MIIC. The issues and solutions implemented to construct a temporal version (tMIIC) are presented as well as benchmarks reflecting the advantages of tMIIC compared to other state-of-the-art methods. The application to sequences of images taken with a microscope of a tumor environment reconstituted on microchips illustrates the capabilities of tMIIC to recover, solely from data, known and new relationships. Finally, this thesis introduces the use of a consequence a priori to apply causal discovery to the reconstruction of gene regulatory networks. By assuming that all genes, except transcription factors, are only consequence genes, it becomes possible to reconstruct graphs with thousands of genes. The ability to identify key transcription factors de novo is illustrated by an application to single cell RNA sequencing data with the discovery of two transcription factors likely to be involved in the biological process of interest

Cette thèse traite des domaines suivant en Apprentissage Automatique: la théorie des Bandits, l'Apprentissage statistique et l'Apprentissage par renforcement. Son fil rouge est l'étude de plusieurs notions d'adaptation, d'un point de vue non asymptotique : à un environnement ou à un adversaire dans la partie I, à la structure d'un signal dans la partie II, à la structure de récompenses ou à un modèle des états du monde dans la partie III. Tout d'abord nous dérivons une analyse non asymptotique d'un algorithme de bandit à plusieurs bras utilisant la divergence de Kullback-Leibler. Celle-ci permet d'atteindre, dans le cas de distributions à support fini, la borne inférieure de performance asymptotique dépendante des distributions de probabilité connue pour ce problème. Puis, pour un bandit avec un adversaire possiblement adaptatif, nous introduisons des modèles dépendants de l'histoire et traduisant une possible faiblesse de l'adversaire et montrons comment en tirer parti pour concevoir des algorithmes adaptatifs à cette faiblesse. Nous contribuons au problème de la régression en montrant l'utilité des projections aléatoires, à la fois sur le plan théorique et pratique, lorsque l'espace d'hypothèses considéré est de dimension grande, voire infinie. Nous utilisons également des opérateurs d'échantillonnage aléatoires dans le cadre de la reconstruction parcimonieuse lorsque la base est loin d'être orthogonale. Enfin, nous combinons la partie I et II : pour fournir une analyse non-asymptotique d'algorithmes d'apprentissage par renforcement; puis, en amont du cadre des Processus Décisionnel de Markov, pour discuter du problème pratique du choix d'un bon modèle d'états.

Cette thèse étudie une classe d'algorithmes d'apprentissage par renforcement (RL), appelée « itération sur les politiques obtenues par classification » (CBPI). Contrairement aux méthodes standards de RL, CBPI n'utilise pas de représentation explicite de la fonction valeur. CBPI réalise des déroulés (des trajectoires) et estime la fonction action-valeur de la politique courante pour un nombre limité d'états et d'actions. En utilisant un ensemble d'apprentissage construit à partir de ces estimations, la politique gloutonne est apprise comme le produit d'un classificateur. La politique ainsi produite à chaque itération de l'algorithme, n'est plus définie par une fonction valeur (approximée), mais par un classificateur. Dans cette thèse, nous proposons de nouveaux algorithmes qui améliorent les performances des méthodes CBPI existantes, spécialement lorsque le nombre d’interactions avec l’environnement est limité. Nos améliorations se portent sur les deux limitations de CBPI suivantes : 1) les déroulés utilisés pour estimer les fonctions action-valeur doivent être tronqués et leur nombre est limité, créant un compromis entre le biais et la variance dans ces estimations, et 2) les déroulés sont répartis de manière uniforme entre les états déroulés et les actions disponibles, alors qu'une stratégie plus évoluée pourrait garantir un ensemble d'apprentissage plus précis. Nous proposons des algorithmes CBPI qui répondent à ces limitations, respectivement : 1) en utilisant une approximation de la fonction valeur pour améliorer la précision (en équilibrant biais et variance) des estimations, et 2) en échantillonnant de manière adaptative les déroulés parmi les paires d'état-action
This dissertation is motivated by the study of a class of reinforcement learning (RL) algorithms, called classification-based policy iteration (CBPI). Contrary to the standard RL methods, CBPI do not use an explicit representation for value function. Instead, they use rollouts and estimate the action-value function of the current policy at a collection of states. Using a training set built from these rollout estimates, the greedy policy is learned as the output of a classifier. Thus, the policy generated at each iteration of the algorithm, is no longer defined by a (approximated) value function, but instead by a classifier. In this thesis, we propose new algorithms that improve the performance of the existing CBPI methods, especially when they have a fixed budget of interaction with the environment. Our improvements are based on the following two shortcomings of the existing CBPI algorithms: 1) The rollouts that are used to estimate the action-value functions should be truncated and their number is limited, and thus, we have to deal with bias-variance tradeoff in estimating the rollouts, and 2) The rollouts are allocated uniformly over the states in the rollout set and the available actions, while a smarter allocation strategy could guarantee a more accurate training set for the classifier. We propose CBPI algorithms that address these issues, respectively, by: 1) the use of a value function approximation to improve the accuracy (balancing the bias and variance) of the rollout estimates, and 2) adaptively sampling the rollouts over the state-action pairs

Ce travail de thèse s'inscrit dans le domaine du machine learning et concerne plus particulièrement les sous-catégories de l'optimisation stochastique, du online learning et du clustering. Ces sous-domaines existent depuis plusieurs décennies mais ils ont tous reçu un éclairage différent au cours de ces dernières années. Notamment, les jeux de bandits offrent aujourd'hui un cadre commun pour l'optimisation stochastique et l'online learning. Ce point de vue conduit a de nombreuses extensions du jeu de base. C'est sur l'étude mathématique de ces jeux que se concentre la première partie de cette thèse. La seconde partie est quant à elle dédiée au clustering et plus particulièrement à deux notions importantes: la consistance asymptotique des algorithmes et la stabilité comme méthode de sélection de modèles.

La théorie des jeux à champ moyen fut introduite en 2006 par Jean-Michel Lasry et Pierre-Louis Lions. Elle permet l'étude de la théorie des jeux dans certaines configurations où le nombre de joueurs est trop grand pour espérer une résolution pratique. Nous étudions la théorie des jeux à champ moyen sur les graphes en nous appuyant sur les travaux d'Olivier Guéant que nous étendrons à des formes plus générales d'Hilbertien. Nous étudierons aussi les liens qui existent entres les K-moyennes et les jeux à champ moyen ce qui permettra en principe de proposer de nouveaux algorithmes pour les K-moyennes grâce aux techniques de résolution numérique propres aux jeux à champ moyen. Enfin nous étudierons un jeu à champ moyen à savoir le problème "d'heure de début d'une réunion" en l'étendant à des situations où les agents peuvent choisir entre deux réunions. Nous étudierons de manière analytique et numérique l'existence et la multiplicité des solutions de ce problème
The mean field game theory was introduced in 2006 by Jean-Michel Lasry and Pierre-Louis Lions. It allows us to study the game theory in some situations where the number of players is too high to be able to be solved in practice. We will study the mean field game theory on graphs by learning from the studies of Oliver Guéant which we will extend to more generalized forms of Hilbertian. We will also study the links between the K-means and the mean field game theory. In principle, this will offer us new algorithms for solving the K-means thanks to the techniques of numerical resolutions of the mean field games. Findly, we will study a mean field game called the "starting time of a meeting". We will extend it to situations where the players can choose between two meetings. We will study analytically and numerically the existence and multiplicity of the solutions to this problem

Cette thèse s'inscrit dans le cadre de l'apprentissage par renforcement pour les systèmes de dialogue. Ce document propose différentes manières de considérer l'être humain, interlocuteur du système de dialogue. Après un aperçu des limites du cadre agent/environnement traditionnel, nous proposons de modéliser dans un premier temps le dialogue comme un jeu stochastique. Dans ce cadre, l'être humain n'est plus vu comme une distribution de probabilité stationnaire mais comme un agent cherchant à optimiser ses préférences. Nous montrons que ce cadre permet une prise en compte de phénomènes de co-adaptation intrinsèques au dialogue humain/machine et nous montrons que ce cadre étend le champ d'application des systèmes de dialogue, par exemple aux dialogues de négociations. Dans un second temps, nous présentons une méthode permettant à l'être humain d'accélérer et de sécuriser la phase d'apprentissage de son système de dialogue par le biais de conseils encodés sous la forme d'une fonction de récompense. Nous montrons que cette prise en compte de conseils permet de significativement améliorer les performances d'un agent apprenant par renforcement. Finalement, une troisième situation est considérée. Ici, un système écoute une conversation entre humains et agit de manière à influer sur le cours de la conversation. Une fonction de récompense originale permettant de maximiser le résultat de la conversation tout en minimisant l'intrusivité du système est proposé. Nous montrons que notre approche permet de significativement améliorer les conversations. Pour implémenter cette approche, un modèle de la conversation est requis. C'est pourquoi nous proposons dans une quatrième contribution d'apprendre ce modèle à partir d'un algorithme d'apprentissage d'automates à multiplicité
The context of this thesis takes place in Reinforcement Learning for Spoken Dialogue Systems. This document proposes several ways to consider the role of the human interlocutor. After an overview of the limits of the traditional Agent/Environment framework, we first suggest to model human/machine dialogue as a Stochastic Game. Within this framework, the human being is seen as a rational agent, acting in order to optimize his preferences. We show that this framework allows to take into consideration co-adaptation phenomena and extend the applications of human/machine dialogue, e.g. negociation dialogues. In a second time, we address the issue of allowing the incorporation of human expertise in order to speed-up the learning phase of a reinforcement learning based spoken dialogue system. We provide an algorithm that takes advantage of those human advice and shows a great improvement over the performance of traditional reinforcement learning algorithms. Finally, we consider a third situation in which a system listens to a conversation between two human beings and talk when it estimates that its intervention could help to maximize the preferences of its user. We introduce a original reward function balancing the outcome of the conversation with the intrusiveness of the system. Our results obtained by simulation suggest that such an approach is suitable for computer-aided human-human dialogue. However, in order to implement this method, a model of the human/human conversation is required. We propose in a final contribution to learn this model with an algorithm based on multiplicity automata

Les besoins de l'industrie des jeux vidéo sont en constante évolution. Dans le domaine de l'intelligence artificielle, nous identifions dans le chapitre 1, les différents besoins de l'industrie dans ce domaine. Nous pensons que la conception d'une solution d'apprentissage de comportements par imitation qui soit fonctionnelle et efficace permettrait de couvrir la plupart de ces besoins. Dans le chapitre 2, nous montrons que les techniques d'extraction de données peuvent être très utiles pour offrir une telle solution. Cependant, ces techniques ne sont pas suffisantes pour construire automatiquement un comportement complet qui serait utilisable dans les jeux vidéo modernes. Dans le chapitre 3, nous proposons un modèle générique pour apprendre des comportements en imitant des joueurs humains : Orion. Ce modèle est composé de deux parties, un modèle structurel et un modèle comportemental. Le modèle structurel propose un framework généraliste d'exploration de données, fournissant une abstraction des différentes méthodes utilisées dans ce domaine de recherche. Ce framework nous permet de construire un outil d'usage général avec de meilleures possibilités de visualisation que les outils d'extraction de données existants. Le modèle comportemental est conçu pour intégrer des techniques d'exploration de données dans une architecture plus générale et repose sur les Behavior Trees. Dans le chapitre 4, nous illustrons comment nous utilisons notre modèle en mettant en oeuvre le comportement des joueurs dans les jeux Pong et UT3 en utilisant Orion. Dans le chapitre 5, nous identifions les améliorations possibles, à la fois de notre outil d'extraction de données et de notre modèle comportemental
The video game industry's needs are constantly changing. In the field of artificial intelligence, we identify inchapter 1, the different needs of industry in this area. We believe that the design of a learning behavior through imitation solution that is functional and efficient would cover most of these needs. In chapter 2, we show that data mining techniques can be very useful to provide such a solution. However, for now, these techniques are not sufficient to automatically build a comprehensive behavior that would be usable in modern video games. In chapter 3, we propose a generic model to learn behavior by imitating human players: Orion.This model consists of two parts, a structural model and a behavioral model. The structural model provides a general data mining framework, providing an abstraction of the different methods used in this research. This framework allows us to build a general purpose tool with better possibilities for visualizing than existing data mining tools. The behavioral model is designed to integrate data mining techniques in a more general architecture and is based on the Behavior Trees. In chapter 4, we illustrate how we use our model by implementing the behavior of players in the Pong and Unreal Tournament 3 games using Orion. In chapter 5,we identify possible improvements, both of our data mining framework and our behavioral model

Le problème des bandits manchots est un cadre théorique permettant d'étudier le compromis entre exploration et exploitation lorsque l'information observée est partielle. Dans celui-ci, un joueur dispose d'un ensemble de K bras (ou actions), chacun associé à une distribution de récompenses D(µk) de moyenne µk Є [0, 1] et de support [0, 1]. A chaque tour t Є [1, T], il choisit un bras kt et observe la récompense y kt tirée depuis D (µkt). La difficulté du problème vient du fait que le joueur observe uniquement la récompense associée au bras joué; il ne connaît pas celle qui aurait pu être obtenue en jouant un autre bras. À chaque choix, il est ainsi confronté au dilemme entre l'exploration et l'exploitation; explorer lui permet d'affiner sa connaissance des distributions associées aux bras explorés tandis qu'exploiter lui permet d'accumuler davantage de récompenses en jouant le meilleur bras empirique (sous réserve que le meilleur bras empirique soit effectivement le meilleur bras). Dans la première partie de la thèse nous aborderons le problème des bandits manchots lorsque les distributions générant les récompenses sont non-stationnaires. Nous étudierons dans un premier temps le cas où même si les distributions varient au cours du temps, le meilleur bras ne change pas. Nous étudierons ensuite le cas où le meilleur bras peut aussi changer au cours du temps. La seconde partie est consacrée aux algorithmes de bandits contextuels où les récompenses dépendent de l'état de l'environnement. Nous étudierons l'utilisation des réseaux de neurones et des forêts d'arbres dans le cas des bandits contextuels puis les différentes approches à base de méta-bandits permettant de sélectionner en ligne l'expert le plus performant durant son apprentissage
The multi-armed bandit is a framework allowing the study of the trade-off between exploration and exploitation under partial feedback. At each turn t Є [1,T] of the game, a player has to choose an arm kt in a set of K and receives a reward ykt drawn from a reward distribution D(µkt) of mean µkt and support [0,1]. This is a challeging problem as the player only knows the reward associated with the played arm and does not know what would be the reward if she had played another arm. Before each play, she is confronted to the dilemma between exploration and exploitation; exploring allows to increase the confidence of the reward estimators and exploiting allows to increase the cumulative reward by playing the empirical best arm (under the assumption that the empirical best arm is indeed the actual best arm).In the first part of the thesis, we will tackle the multi-armed bandit problem when reward distributions are non-stationary. Firstly, we will study the case where, even if reward distributions change during the game, the best arm stays the same. Secondly, we will study the case where the best arm changes during the game. The second part of the thesis tacles the contextual bandit problem where means of reward distributions are now dependent of the environment's current state. We will study the use of neural networks and random forests in the case of contextual bandits. We will then propose meta-bandit based approach for selecting online the most performant expert during its learning

Vivre des moments exceptionnels, connaître des sensations fortes, du bien-être, nous épanouir, font souvent partie de nos rêves ou aspirations. Nous choisissons des moyens divers pour y arriver comme le jeu. Que le joueur recherche l’originalité, les défis, la découverte, une histoire, ou d’autres buts, ce sont des états émotionnels qui sont l’objet de sa quête. Il attend que le jeu lui procure du plaisir, des sensations. Comment les lui apporter ? Mettre au point une nouvelle interaction humain environnement, dans les jeux vidéo ou pervasifs ou autres applications, prenant en compte et s’adaptant aux émotions de chacun, sans être gêné par les interfaces, biocapteurs de contact par exemple, est notre objectif. Cela soulève deux questions : - Peut-on découvrir des états émotionnels à partir de mesures physiologiques issues de biocapteurs de contact ? - Si oui, ces capteurs peuvent-ils être remplacés par des dispositifs distants, donc non invasifs, et produire les mêmes résultats ?Les modèles mis au point proposent des solutions à base de méthodes mathématiques d’apprentissage non supervisées. Nous présentons aussi des moyens de mesures à distance et expliquons les futurs travaux dans le domaine que nous baptisons affectique
Living exceptional moments, experiencing thrills, well-being, blooming, are often part of our dreams or aspirations. We choose various ways to get there like games. Whether the player is looking for originality, challenges, discovery, a story, or other goals, emotional states are the purpose of his quest. He remains until the game gives him pleasure, sensations. How bring them there? We are developing a new human environment interaction that takes into account and adapts to emotions. We address video or pervasive games or other applications. Through this goal, players should not be bothered by interfaces, or biosensors invasivness. This work raises two questions:- Can we discover emotional states based on physiological measurements from contact biosensors?- If so, can these sensors be replaced by remote, non-invasive devices and produce the same results?The models we have developed propose solutions based on unsupervised machine learning methods. We also present remote measurements technics and explain our future works in a new field we call affectics

Peer-to-peer real-time communication and media streaming applications optimize their performance by using application-level topology estimation services such as virtual coordinate systems. Virtual coordinate systems allow nodes in a peer-to-peer network to accurately predict latency between arbi- trary nodes without the need of performing extensive measurements. However, systems that leverage virtual coordinates as supporting building blocks, are prone to attacks conducted by compromised nodes that aim at disrupting, eavesdropping, or mangling with the underlying communications. Recent research proposed techniques to mitigate basic attacks (inflation, deflation, oscillation) considering a single attack strategy model where attackers perform only one type of attack. In this work, we define and use a game theory framework in order to identify the best attack and defense strategies assuming that the attacker is aware of the defense mechanisms. Our approach leverages concepts derived from the Nash equilibrium to model more powerful adversaries. We apply the game theory framework to demonstrate the impact and efficiency of these attack and defense strategies using a well-known virtual coordinate system and real-life Internet data sets. Thereafter, we explore supervised machine learning techniques to mitigate more subtle yet highly effective attacks (frog-boiling, network-partition) that are able to bypass existing defenses. We evaluate our techniques on the Vivaldi system against a more complex attack strategy model, where attackers perform sequences of all known attacks against virtual coordinate systems, using both simulations and Internet deployments.

Ce travail de thèse a été réalisé dans le contexte de la recommandation dynamique. La recommandation est l'action de fournir du contenu personnalisé à un utilisateur utilisant une application, dans le but d'améliorer son utilisation e.g. la recommandation d'un produit sur un site marchant ou d'un article sur un blog. La recommandation est considérée comme dynamique lorsque le contenu à recommander ou encore les goûts des utilisateurs évoluent rapidement e.g. la recommandation d'actualités. Beaucoup d'applications auxquelles nous nous intéressons génèrent d'énormes quantités de données grâce à leurs millions d'utilisateurs sur Internet. Néanmoins, l'utilisation de ces données pour évaluer une nouvelle technique de recommandation ou encore comparer deux algorithmes de recommandation est loin d'être triviale. C'est cette problématique que nous considérons ici. Certaines approches ont déjà été proposées. Néanmoins elles sont très peu étudiées autant théoriquement (biais non quantifié, borne de convergence assez large...) qu'empiriquement (expériences sur données privées). Dans ce travail nous commençons par combler de nombreuses lacunes de l'analyse théorique. Ensuite nous discutons les résultats très surprenants d'une expérience à très grande échelle : une compétition ouverte au public que nous avons organisée. Cette compétition nous a permis de mettre en évidence une source de biais considérable et constamment présente en pratique : l'accélération temporelle. La suite de ce travail s'attaque à ce problème. Nous montrons qu'une approche à base de bootstrap permet de réduire mais surtout de contrôler ce biais
The context of this thesis work is dynamic recommendation. Recommendation is the action, for an intelligent system, to supply a user of an application with personalized content so as to enhance what is refered to as "user experience" e.g. recommending a product on a merchant website or even an article on a blog. Recommendation is considered dynamic when the content to recommend or user tastes evolve rapidly e.g. news recommendation. Many applications that are of interest to us generates a tremendous amount of data through the millions of online users they have. Nevertheless, using this data to evaluate a new recommendation technique or even compare two dynamic recommendation algorithms is far from trivial. This is the problem we consider here. Some approaches have already been proposed. Nonetheless they were not studied very thoroughly both from a theoretical point of view (unquantified bias, loose convergence bounds...) and from an empirical one (experiments on private data only). In this work we start by filling many blanks within the theoretical analysis. Then we comment on the result of an experiment of unprecedented scale in this area: a public challenge we organized. This challenge along with a some complementary experiments revealed a unexpected source of a huge bias: time acceleration. The rest of this work tackles this issue. We show that a bootstrap-based approach allows to significantly reduce this bias and more importantly to control it

Cette thèse a pour objectif de créer et évaluer un modèle narratif pour les jeux vidéo émergents dont une part importante du contenu est générée de façon procédurale. Elle propose pour cela une application dans le jeu vidéo Minecraft. L'approche classique de la narration dans les jeux vidéo s'adaptant difficilement à des expériences de jeu plus libres nous proposons de donner au joueur les moyens de transformer le récit en temps réel et de manière explicite grâce à une forme narrative modulaire et adaptative au contexte de jeu courant. Dans un premier temps, la thèse explore les liens entre narration et interaction par le biais de l'étude des rôles de la narration dans les jeux vidéo. Puis, dans un deuxième temps, nous identifions les propriétés qui caractérisent les jeux vidéo émergents afin d'exposer les enjeux narratifs de ce type d'expérience de jeu. Dans un troisième temps, nous détaillons notre proposition d'un modèle narratif adapté aux jeux vidéo émergents ainsi que l'architecture logiciel permettant au joueur de transformer le récit en temps réel. Finalement, nous présentons deux expérimentations visant à vérifier nos hypothèses et à évaluer notre modèle narratif
This thesis aims to create and evaluate a narrative model for emergent videogames that make extensive use of procedurally generated content. As such, an application of this model is presented within the videogame Minecraft. The usual approach to narratives in videogames can hardly be applied to experiences of play that involve more freedom from the player's perspective, such as what offer emergents videogames. Thus, we aim to provide players with the means to explicitly alter the story in real time, thanks to a context sensitive and modular narrative form. First, we explore the relationship betweenstorytelling and interactivity by studying the various roles held by narratives in videogames. Then, we identify the properties that define emergent videogames to better expose the narrative challenges they represent. Next, we detail our proposal of a narrative model suitable for emergent games as well as the architecture allowing players to transform the story in real time. Finally, we present an experiment in which we evaluate the validity of our narrative model in the context of emergent videogames

Cette thèse étudie la reconnaissance des émotions à partir de signaux physiologiques dans le contexte des jeux vidéo et la faisabilité de sa mise en œuvre sur un système embarqué. Les défis suivants sont abordés : la relation entre les états émotionnels et les réponses physiologiques dans le contexte du jeu, les variabilités individuelles des réponses psycho-physiologiques et les problèmes de mise en œuvre sur un système embarqué. Les contributions majeures de cette thèse sont les suivantes. Premièrement, nous construisons une base de données multimodale dans le cadre de l'Affective Gaming (DAG). Cette base de données contient plusieurs mesures concernant les modalités objectives telles que les signaux physiologiques de joueurs et des évaluations subjectives sur des phases de jeu. A l'aide de cette base, nous présentons une série d'analyses effectuées pour la détection des moments marquant émotionnellement et la classification des émotions à l'aide de diverses méthodes d'apprentissage automatique. Deuxièmement, nous étudions la variabilité individuelle de la réponse émotionnelle et proposons un modèle basé sur un groupe de joueurs déterminé par un clustering selon un ensemble de traits physiologiques pertinents. Nos travaux mettent en avant le fait que le modèle proposé, basé sur un tel groupe personnalisé, est plus performant qu'un modèle général ou qu'un modèle spécifique à un utilisateur. Troisièmement, nous appliquons la méthode proposée sur un système ARM A9 et montrons que la méthode proposée peut répondre à l'exigence de temps de calcul
This thesis investigates physiological-based emotion recognition in a digital game context and the feasibility of implementing the model on an embedded system. The following chanllenges are addressed: the relationship between emotional states and physiological responses in the game context, individual variabilities of the pschophysiological responses and issues of implementation on an embedded system. The major contributions of this thesis are : Firstly, we construct a multi-modal Database for Affective Gaming (DAG). This database contains multiple measurements concerning objective modalities: physiological signals (ECG, EDA, EMG, Respiration), screen recording, and player's face recording, as well as subjective assessments on both game event and match level. We presented statistics of the database and run a series of analysis on issues such as emotional moment detection and emotion classification, influencing factors of the overall game experience using various machine learning methods. Secondly, we investigate the individual variability in the collected data by creating an user-specific model and analyzing the optimal feature set for each individual. We proposed a personalized group-based model created the similar user groups by using the clustering techniques based on physiological traits deduced from optimal feature set. We showed that the proposed personalized group-based model performs better than the general model and user-specific model. Thirdly, we implemente the proposed method on an ARM A9 system and showed that the proposed method can meet the requirement of computation time

Développer un programme capable de jouer à n’importe quel jeu de stratégie, souvent désigné par le General Game Playing (GGP) constitue un des Graal de l’intelligence artificielle. Les compétitions GGP, où chaque jeu est représenté par un ensemble de règles logiques au travers du Game Description Language (GDL), ont conduit la recherche à confronter de nombreuses approches incluant les méthodes de type Monte Carlo, la construction automatique de fonctions d’évaluation, ou la programmation logique et ASP. De par cette thèse, nous proposons une nouvelle approche dirigée par les contraintes stochastiques.Dans un premier temps, nous nous concentrons sur l’élaboration d’une traduction de GDL en réseauxde contraintes stochastiques (SCSP) dans le but de fournir une représentation dense des jeux de stratégies et permettre la modélisation de stratégies.Par la suite, nous exploitons un fragment de SCSP au travers d’un algorithme dénommé MAC-UCBcombinant l’algorithme MAC (Maintaining Arc Consistency) utilisé pour résoudre chaque niveau duSCSP tour après tour, et à l’aide de UCB (Upper Confidence Bound) afin d’estimer l’utilité de chaquestratégie obtenue par le dernier niveau de chaque séquence. L’efficacité de cette nouvelle technique sur les autres approches GGP est confirmée par WoodStock, implémentant MAC-UCB, le leader actuel du tournoi continu de GGP.Finalement, dans une dernière partie, nous proposons une approche alternative à la détection de symétries dans les jeux stochastiques, inspirée de la programmation par contraintes. Nous montrons expérimentalement que cette approche couplée à MAC-UCB, surpasse les meilleures approches du domaine et a permis à WoodStock de devenir champion GGP 2016
The ability for a computer program to effectively play any strategic game, often referred to General Game Playing (GGP), is a key challenge in AI. The GGP competitions, where any game is represented according to a set of logical rules in the Game Description Language (GDL), have led researches to compare various approaches, including Monte Carlo methods, automatic constructions of evaluation functions, logic programming, and answer set programming through some general game players. In this thesis, we offer a new approach driven by stochastic constraints. We first focus on a translation process from GDL to stochastic constraint networks (SCSP) in order to provide compact representations of strategic games and to model strategies. In a second part, we exploit a fragment of SCSP through an algorithm called MAC-UCB by coupling the MAC (Maintaining Arc Consistency) algorithm, used to solve each stage of the SCSP in turn, together with the UCB (Upper Confidence Bound) policy for approximating the values of those strategies obtained by the last stage in the sequence. The efficiency of this technical on the others GGP approaches is confirmed by WoodStock, implementing MAC-UCB, the actual leader on the GGP Continuous Tournament. Finally, in the last part, we propose an alternative approach to symmetry detection in stochastic games, inspired from constraint programming techniques. We demonstrate experimentally that MAC-UCB, coupled with our constranit-based symmetry detection approach, significantly outperforms the best approaches and made WoodStock the GGP champion 2016

Les problèmes d’investissements d’énergie sont difficiles à cause des incertitudes. Certaines incertitudes peuvent être modélisées par les probabilités. Mais il y a des problèmes difficiles tels que l'évolution de technologie et la pénalisation de CO2, délicats à modéliser par des probabilités. Aussi, les travaux sur l’optimisation des systèmes d’énergie est souvent déterministe. Cette thèse s’intéresse à appliquer l’optimisation bruitée aux systèmes d’énergie. Cette thèse se concentre sur trois parties principales: les études des méthodes pour gérer le bruit, y compris utiliser des méthodes de ré-échantillonnage pour améliorer la vitesse de convergence; les applications des méthodes de portefeuilles à l’optimisation bruitée dans le continu; les applications des méthodes de portefeuilles aux cas avec incertitudes pour la planification des investissements d’énergie et aux jeux, y compris l’utilisation de l’algorithme de bandit adversarial pour calculer l’équilibre de Nash d'un jeu matriciel à somme nulle et l’utilisation de “sparsity” pour accélérer le calcul de l’équilibre de Nash
This manuscript concentrates in studying methods to handle the noise, including using resampling methods to improve the convergence rates and applying portfolio methods to cases with uncertainties (games, and noisy optimization in continuous domains).Part I will introduce the manuscript, then review the state of the art in noisy optimization, portfolio algorithm, multi-armed bandit algorithms and games.Part II concentrates on the work on noisy optimization:∙ Chapter 4 provides a generic algorithm for noisy optimization recovering most of the existing bounds in one single noisy optimization algorithm.∙ Chapter5 applies different resampling rules in evolution strategies for noisy optimization, without the assumption of variance vanishing in the neighborhood of the optimum, and shows mathematically log-log convergence results and studies experimentally the slope of this convergence.∙ Chapter 6 compares resampling rules used in the differential evolution algorithm for strongly noisy optimization. By mathematical analysis, a new rule is designed for choosing the number of resamplings, as a function of the dimension, and validate its efficiency compared to existing heuristics - though there is no clear improvement over other empirically derived rules.∙ Chapter 7 applies “common random numbers”, also known as pairing, to an intermediate case between black-box and white-box cases for improving the convergence.Part III is devoted to portfolio in adversarial problems:∙ Nash equilibria are cases in which combining pure strategies is necessary for designing optimal strategies. Two chapters are dedicated to the computation of Nash equilibria:– Chapter 9 investigates combinations of pure strategies, when a small set of pure strategies is concerned; basically, we get improved rates when the support of the Nash equilibrium is small.– Chapter 10 applies these results to a power system problem. This compares several bandit algorithms for Nash equilibria, defines parameter-free bandit algorithms, and shows the relevance of the sparsity approach dis- cussed in Chapter 9.∙ Then, two chapters are dedicated to portfolios of game methods:– Chapter 11 shows how to generate multiple policies, from a single one, when only one such policy is available. This kind of bootstrap (based on random seeds) generates many deterministic policies, and then combines them into one better policy. This has been tested on several games.– Chapter 12 extends chapter 11 by combining policies in a position-specific manner. In particular, we get a better asymptotic behavior than MCTS.Part IV is devoted to portfolios in noisy optimization:∙ Chapter 14 is devoted to portfolio of noisy optimization methods in continuous domains;∙ Chapter 15 proposed differential evolution as a tool for non- stationary bandit problems

Avec le nombre croissant d’appareils intelligents à faible puissance, au cours ces dernières années, la question de l’efficacité énergétique a joué un rôle de plus en plus indispensable dans la conception des systèmes de communication. Cette thèse vise à concevoir des schémas de transmission distribués à faible consommation d’énergie pour les réseaux sans fil, utilisant la théorie des jeux et le codage réseau instantanément décodable (IDNC), qui est une sous-classe prometteuse du codage réseau. En outre, nous étudions le modèle de l'échange coopératif de donnée (CDE) dans lequel tous les périphériques coopèrent en échangeant des paquets codés dans le réseau, jusqu’à ce qu’ils récupèrent tous l’ensemble des informations requises. En effet, la mise en œuvre du CDE basé sur l’IDNC soulève plusieurs défis intéressants, notamment la prolongation de la durée de vie du réseau et la réduction du nombre de transmissions afin de répondre aux besoins des applications temps réel. Par conséquent, contrairement à la plupart des travaux existants concernant l’IDNC, nous nous concentrons non seulement sur le délai, mais également sur l’énergie consommée. En premier lieu, nous étudions le problème de minimisation de l’énergie consommée et du délai au sein d’un petit réseau IDNC coopératif, entièrement connecté et à faible puissance. Nous modélisons le problème en utilisant la théorie des jeux coopératifs de formation de coalitions. Nous proposons un algorithme distribué (appelé “merge and split“) permettant aux nœuds sans fil de s’auto-organiser, de manière distribuée, en coalitions disjointes et indépendantes. L’algorithme proposé garantit une consommation d’énergie réduite et minimise le délai de complétion dans le réseau clustérisé résultant. Par ailleurs, nous ne considérons pas seulement l'énergie de transmission, mais aussi la consommation de l'énergie de calcul des nœuds. De plus, nous nous concentrons sur la question de la mobilité et nous analysons comment, à travers la solution proposée, les nœuds peuvent s’adapter à la topologie dynamique du réseau. Par la suite, nous étudions le même problème au sein d’un réseau large et partiellement connecté. En effet, nous examinons le modèle de CDE multi-sauts. Dans un tel modèle, nous considérons que les nœuds peuvent choisir la puissance d’émission et change ainsi de rayon de transmission et le nombre de voisin avec lesquels il peut entrer en coalition. Pour ce faire, nous modélisons le problème avec un jeu à deux étages; un jeu non-coopératif de contrôle de puissance et un jeu coopératif de formation de coalitions. La solution optimale du premier jeu permet aux joueurs de coopérer à travers des rayons de transmission limités en utilisant la théorie des jeux coopérative. En outre, nous proposons un algorithme distribué “merge and split“ afin de former des coalitions dans lesquelles les joueurs maximisent leurs utilités en termes de délai et de consommation d’énergie. La solution proposée permet la création d’une partition stable avec une interférence réduite et une complexité raisonnable. Nous démontrons que la coopération entre les nœuds au sein du réseau résultant, permet de réduire considérablement la consommation d’énergie par rapport au modèle coopératif optimal qui maintient le rayon de transmission maximal
With significantly growing number of smart low-power devices during recent years, the issue of energy efficiency has taken an increasingly essential role in the communication systems’ design. This thesis aims at designing distributed and energy efficient transmission schemes for wireless networks using game theory and instantly decodable network coding (IDNC) which is a promising network coding subclass. We study the cooperative data exchange (CDE) scenario in which all devices cooperate with each other by exchanging network coded packets until all of them receive all the required information. In fact, enabling the IDNC-based CDE setting brings several challenges such us how to extend the network lifetime and how to reduce the number of transmissions in order to satisfy urgent delay requirements. Therefore, unlike most of existing works concerning IDNC, we focus not only on the decoding delay, but also the consumed energy. First, we investigate the IDNC-based CDE problem within small fully connected networks across energy-constrained devices and model the problem using the cooperative game theory in partition form. We propose a distributed merge-and-split algorithm to allow the wireless nodes to self-organize into independent disjoint coalitions in a distributed manner. The proposed algorithm guarantees reduced energy consumption and minimizes the delay in the resulting clustered network structure. We do not only consider the transmission energy, but also the computational energy consumption. Furthermore, we focus on the mobility issue and we analyse how, in the proposed framework, nodes can adapt to the dynamic topology of the network. Thereafter, we study the IDNC-based CDE problem within large-scale partially connected networks. We considerate that each player uses no longer his maximum transmission power, rather, he controls his transmission range dynamically. In fact, we investigate multi-hop CDE using the IDNC at decentralized wireless nodes. In such model, we focus on how these wireless nodes can cooperate in limited transmission ranges without increasing the IDNC delay nor their energy consumption. For that purpose, we model the problem using a two-stage game theoretical framework. We first model the power control problem using non-cooperative game theory where users jointly choose their desired transmission power selfishly in order to reduce their energy consumption and their IDNC delay. The optimal solution of this game allows the players at the next stage to cooperate with each other through limited transmission ranges using cooperative game theory in partition form. Thereafter, a distributed multihop merge-and-split algorithm is defined to form coalitions where players maximize their utilities in terms of decoding delays and energy consumption. The solution of the proposed framework determines a stable feasible partition for the wireless nodes with reduced interference and reasonable complexity. We demonstrate that the co-operation between nodes in the multihop cooperative scheme achieves a significant minimization of the energy consumption with respect to the most stable cooperative scheme in maximum transmission range without hurting the IDNC delay

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

Le trouble du Spectre de l’Autisme (TSA) est caractérisé par des difficultés concernant les habiletés sociales dont l’utilisation des expressions faciales émotionnelles (EFE). Si de nombreuses études s’intéressent à leur reconnaissance, peu évaluent leur production chez l’enfant typique et avec TSA. Les nouvelles technologies sont plébiscitées pour travailler les habiletés sociales auprès des enfants avec TSA, or, peu d’études concernent leur utilisation pour le travail de la production des EFE. Au début de ce projet, nous retrouvions seulement 4 jeux la travaillant. Notre objectif a été la création du jeu sérieux JEMImE travaillant la production des EFE chez l’enfant avec TSA grâce à un feedback automatisé. Nous avons d’abord constitué une base de données d’EFE d’enfants typiques et avec TSA pour créer un algorithme de reconnaissance des EFE et étudier leurs compétences de production. Plusieurs facteurs les influencent comme l’âge, le type d’émotion, la culture. Les EFE des enfants avec TSA sont jugées de moins bonne qualité par des juges humains et par l’algorithme de reconnaissance des EFE qui a besoin de plus de points repères sur leurs visages pour classer leurs EFE. L’algorithme ensuite intégré dans JEMImE donne un retour visuel en temps réel à l’enfant pour corriger ses productions. Une étude pilote auprès de 23 enfants avec TSA met en avant une bonne adaptation des enfants aux retours de l’algorithme ainsi qu’une bonne expérience dans l’utilisation du jeu. Ces résultats prometteurs ouvrent la voie à un développement plus poussé du jeu pour augmenter le temps de jeu et ainsi évaluer l’effet de cet entraînement sur la production des EFE chez les enfants avec TSA
The autism spectrum disorder (ASD) is characterized by difficulties in socials skills, as emotion recognition and production. Several studies focused on emotional facial expressions (EFE) recognition, but few worked on its production, either in typical children or in children with ASD. Nowadays, information and communication technologies are used to work on social skills in ASD but few studies using these technologies focus on EFE production. After a literature review, we found only 4 games regarding EFE production. Our final goal was to create the serious game JEMImE to work on EFE production with children with ASD using an automatic feedback. We first created a dataset of EFE of typical children and children with ASD to train an EFE recognition algorithm and to study their production skills. Several factors modulate them, such as age, type of emotion or culture. We observed that human judges and the algorithm assess the quality of the EFE of children with ASD as poorer than the EFE of typical children. Also, the EFE recognition algorithm needs more features to classify their EFE. We then integrated the algorithm in JEMImE to give the child a visual feedback in real time to correct his/her productions. A pilot study including 23 children with ASD showed that children are able to adapt their productions thanks to the feedback given by the algorithm and illustrated an overall good subjective experience with JEMImE. The beta version of JEMImE shows promising potential and encourages further development of the game in order to offer longer game exposure to children with ASD and so allow a reliable assessment of the effect of this training on their production of EFE

In this thesis we study two optimization fields. In a first part, we study the use of evolutionary algorithms for solving derivative-free optimization problems in continuous space. In a second part we are interested in multistage optimization. In that case, we have to make decisions in a discrete environment with finite horizon and a large number of states. In this part we use in particular Monte-Carlo Tree Search algorithms. In the first part, we work on evolutionary algorithms in a parallel context, when a large number of processors are available. We start by presenting some state of the art evolutionary algorithms, and then, show that these algorithms are not well designed for parallel optimization. Because these algorithms are population based, they should be we well suitable for parallelization, but the experiments show that the results are far from the theoretical bounds. In order to solve this discrepancy, we propose some rules (such as a new selection ratio or a faster decrease of the step-size) to improve the evolutionary algorithms. Experiments are done on some evolutionary algorithms and show that these algorithms reach the theoretical speedup with the help of these new rules.Concerning the work on multistage optimization, we start by presenting some of the state of the art algorithms (Min-Max, Alpha-Beta, Monte-Carlo Tree Search, Nested Monte-Carlo). After that, we show the generality of the Monte-Carlo Tree Search algorithm by successfully applying it to the game of Havannah. The application has been a real success, because today, every Havannah program uses Monte-Carlo Tree Search algorithms instead of the classical Alpha-Beta. Next, we study more precisely the Monte-Carlo part of the Monte-Carlo Tree Search algorithm. 3 generic rules are proposed in order to improve this Monte-Carlo policy. Experiments are done in order to show the efficiency of these rules.

Le sujet de cette these est de modeliser et de realiser un prototype d'un systeme d'apprentissage apprenant les regles et les meta-regles necessaires a l'expertise de certaines problematiques dont les exemples et les contre-exemples sont representables sur un espace euclidien a n dimensions. L'apprentissage se reitere sur quatre phases. Dans une premiere phase, les sequences d'actions des exemples sont partitionnees en sous-sequences coherentes (tactiques). Dans une seconde phase, les tactiques sont comparees par le biais de fonctions geometriques identifiant une relation geometrique causale, traduite par une regle conceptuelle. Ces regles sont generalisees pour recouvrir des classes de situations tactiques. Dans une troisieme phase de planification strategique, les exemples sont reecrits en chronologies de regles dont la comparaison et la generalisation generent des meta-regles ordonnancant l'application des regles. Lors d'une derniere phase de revision des connaissances, les regles et les meta-regles sont utilisees dans un systeme expert testant ses connaissances apprises, et reintroduisant comme contre-exemples, des sequences qu'il juge defavorables dans sa base de connaissances. Ce systeme est actuellement applique sur le jeu de go

L'explosion de la quantité de données produites chaque jour a fait de l' l'Apprentissage Automatique un outil vital pour extraire des motifs de haute valeur à partir de celles-là. Concrètement, un algorithme d'apprentissage automatique apprend de tels motifs après avoir été entraîné sur un jeu de données appelé données d'entraînement, et sa performance est évaluée sur échantillon différent, appelé données de test. L'Adaptation de Domaine est une branche de l'apprentissage automatique, dans lequel les données d'entraînement et de test ne sont plus supposées provenir de la même distribution de probabilité. Dans ce cas, les deux distributions des données d'entraînement et de test correspondent respectivement aux domaines source et cible. Nos contributions se focalisent sur trois aspects théoriques en relation avec l'adaptation de domaine pour les tâches de classification. Le premier est l'apprentissage avec des fonctions de similarité, qui traite les algorithmes de classification basés sur la comparaison d'une instance à d'autres exemples pour décider sa classe. Le deuxième est la classification à vaste marge qui concerne l'apprentissage d'un classifieur maximisant la séparation entre classes. Le troisième aspect est le Transport Optimal qui formalise un principe d'effort minimal pour le transport de masses de probabilité entre distributions. Au début de cette thèse, nous nous intéressions à l'apprentissage avec ce que l'on appelle fonctions de similarités (epsilon,gamma,tau)-bonnes dans le cadre de l'adaptation de domaine, puisque ces fonctions ont été introduites dans la littérature dans le cadre classique de l'apprentissage supervisé. C'est le sujet de notre première contribution dans laquelle nous étudions théoriquement la performance d'une fonction de similarité sur une distribution cible, étant donné qu'elle est adéquate pour la source. Puis, nous abordons plus généralement le thème de la classification à vaste marge pour l'adaptation de domaine, avec des hypothèses de départ plus faibles que celles adoptées dans la première contribution. Dans ce contexte, nous proposons une nouvelle étude théorique et un algorithme d'adaptation de domaine, ce qui constitue notre deuxième contribution. Nous dérivons de nouvelles bornes prenant en compte la marge de classification dans le domaine cible, que nous convexifions en tirant profit de la théorie du Transport Optimal, en vue de dériver un algorithme d'adaptation de domaine présentant une variation adversariale du problème classique de Kantorovitch. Finalement, nous dédions notre dernière contribution aux variations adversariales ou minimax du problème du transport optimal, où nous démontrons l'adaptabilité de notre approche
The surge in the quantity of data produced nowadays made of Machine Learning, a subfield of Artificial Intelligence, a vital tool used to extract valuable patterns from them and allowed it to be integrated into almost every aspect of our everyday activities. Concretely, a machine learning algorithm learns such patterns after being trained on a dataset called the training set, and its performance is assessed on a different set called the testing set. Domain Adaptation is an active research area of machine learning, in which the training and testing sets are not assumed to stem from the same probability distribution, as opposed to Supervised Learning. In this case, the two distributions generating the training and testing data correspond respectively to the source and target domains. Our contributions focus on three theoretical aspects related to domain adaptation for classification tasks. The first one is learning with similarity functions, which deals with classification algorithms based on comparing an instance to other examples in order to decide its class. The second is large-margin classification, which concerns learning classifiers that maximize the separation between classes. The third is Optimal Transport that formalizes the principle of least effort for transporting probability masses between two distributions. At the beginning of the thesis, we were interested in learning with so-called (epsilon,gamma,tau)-good similarity functions in the domain adaptation framework, since these functions have been introduced in the literature in the classical framework of supervised learning. This is the subject of our first contribution in which we theoretically study the performance of a similarity function on a target distribution, given it is suitable for the source one. Then, we tackle the more general topic of large-margin classification in domain adaptation, with weaker assumptions than those adopted in the first contribution. In this context, we proposed a new theoretical study and a domain adaptation algorithm, which is our second contribution. We derive novel bounds taking the classification margin on the target domain into account, that we convexify by leveraging the appealing Optimal Transport theory, in order to derive a domain adaptation algorithm with an adversarial variation of the classic Kantorovich problem. Finally, after noticing that our adversarial formulation can be generalized to include several other cases of interest, we dedicate our last contribution to adversarial or minimax variations of the optimal transport problem, where we demonstrate the versatility of our approach

Le problème posé est celui d'une planification didactique individualisée dans un système tutoriel intelligent. Le travail s'est effectué dans le cadre du projet AMICAL, Architecture Multi-Agents Interactive, Compagnon pour l'Apprentissage de la Lecture. Nous nous proposons une modélisation des étapes de raisonnement pour construire l'objectif d'une session de travail, premier objet de la planification didactique. Ce raisonnement s'appuie sur cinq bases de connaissances : linguistique, savoir-faire lecture, didactique, pédagogique, et représentation de l'élève. Pour chacune de ces bases, nous proposons aussi des éléments de modélisation. Dans AMICAL, la planification est à la charge d'un agent rationnel spécifique, ainsi, nous proposons une caractérisation de l'agent de construction de l'objectif. Ces différentes hypothèses ont été opérationnalisées pour partie, dans un prototype que nous présentons dans le premier chapitre