Добірка наукової літератури з теми "Processus de décision markovien partiellement observable"

Le projet informatique (SiSU) de l’Unité Mixe de Recherche CNRS Science pour l’Environnement conçoit des méthodes d’aide à la décision pour aider à une meilleure gestion des systèmes complexes environnementaux. Ces travaux de thèse s’inscrivent dans ce contexte. Ils ont pour objectif d'étudier les apports de plusieurs types de méthodes informatiques afin d'améliorer nos connaissances sur les systèmes complexes et ainsi de fournir une aide à leur gestion en situation de fortes incertitudes. En effet, les systèmes complexes environnementaux ne peuvent pas toujours être connus et modélisés avec précision. C’est par exemple le cas en biologie halieutique où des méthodes de gestion doivent être proposées malgré un manque de connaissances sur le système observé, dans notre cas d’étude : la pêche côtière Corse. Nos premiers travaux ont porté sur la calibration de modèles, c’est-à-dire le recherche de valeurs de paramètres permettant à nos modèles de représenter au mieux la dynamique du système. Ils ont montré les limites des approches habituelles et la nécessité d’utiliser des approches probabilistes basées sur de grandes quantités de simulations. Elles apportent une aide précieuse quant à l’acquisition de connaissances, notamment en délimitant des ensembles de solutions. Ceux-ci peuvent alors être utilisés dans des méthodes d’optimisation robuste, voire d’optimisation robuste ajustable. Ces approches permettent non seulement de prendre en compte les incertitudes, mais également de quantifier la réduction d’incertitude que de nouvelles années de données pourront apporter, afin de proposer des stratégies de plus en plus précises à long terme. L’optimisation est donc utilisable efficacement à l’échelle des décideurs. Cependant, la petite pêche côtière Corse, est un système sur lequel agissent un grand nombre d’acteurs avec des comportements différents et difficilement prévisibles et contrôlables. L’optimisation ne semble pas adaptée à l’étude de cette échelle de par la quantité de paramètres et le nombre infini de transitions stochastiques engendrées. Pour cela, des méthodes basées sur l’apprentissage profond par renforcement ont été proposées. Ces approches nous ont permis dans un premier temps de proposer un modèle gérant à la fois décideurs et pêcheurs, les uns cherchant à réduire l’impact écologique, les autres à maximiser leurs gains. À partir de cela, nous avons pu montrer que de faibles connaissances suffisent pour la maximisation des gains des pêcheurs. De plus, cette approche, couplée à de l’optimisation, a permis d’obtenir des décisions d’instauration de quotas efficaces. Enfin, ce système nous a permis d’étudier l’impact de certains comportements individuels de maximisation des gains au détriment du respect des recommandations des décideurs. Il est alors apparu que des politiques de gestion efficaces et adaptées peuvent permettre de pallier l’impact écologique d’une quantité non négligeable de ces comportements. Ainsi, nous avons pu contribuer de manière théorique à élargir les domaines d’application de la théorie de la modélisation et de la simulation, proposer un ensemble d’outils d’optimisation et d’apprentissage automatique à la gestion de systèmes dynamiques partiellement observables, mais également applicative pour la problématique de la gestion de la pêche en Corse
The computer science project (SiSU) of the CNRS Science for the Environment Joint Research Unit designs decision support methods to help better management of complex environmental systems.This thesis work is part of this context. They aim to study the contributions of several types of computer methods to improve our knowledge of complex systems and thus provide assistance in their management in situations of high uncertainty. Indeed, complex environmental systems cannot always be known and modeled with precision. This is for example the case in fisheries biology where management methods must be proposed despite a lack of knowledge on the observed system, in our case study: the Corsican coastal fishery. Our first work focused on the calibration of models, i.e. the search for parameter values allowing our models to best represent the dynamics of the system. They have shown the limits of the usual approaches and the need to use probabilistic approaches based on large quantities of simulations. They bring a precious help for the acquisition of knowledge, in particular by delimiting sets of solutions. These sets can then be used in robust optimization methods, or even in adjustable robust optimization. These approaches allow not only to take into account the uncertainties, but also to quantify the reduction of uncertainty that new years of data can bring, in order to propose more and more precise strategies in the long term. Optimization can therefore be used effectively at the level of decision makers. However, the small-scale coastal fishery in Corsica is a system in which a large number of actors act with different behaviors that are difficult to predict and control. Optimization does not seem adapted to the study of this scale because of the quantity of parameters and the infinite number of stochastic transitions generated. For this, methods based on deep reinforcement learning have been proposed. These approaches allowed us to propose a model that manages both decision-makers and fishermen, the former seeking to reduce the ecological impact, the latter to maximize their gains. From this, we were able to show that little knowledge is sufficient for the maximization of the fishermen's gains. Moreover, this approach, coupled with optimization, allowed us to obtain efficient quota decisions. Finally, this system allowed us to study the impact of certain individual behaviors of maximizing gains to the detriment of respecting the recommendations of the decision makers. It then appeared that effective and adapted management policies can help to mitigate the ecological impact of a significant amount of these behaviors. Thus, we were able to contribute in a theoretical way to broaden the application domains of the theory of modeling and simulation, to propose a set of optimization and machine learning tools for the management of dynamic systems partially observable, but also applicative for the problem of fisheries management in Corsica

La dernière décennie a vu l'émergence d'Internet et l'apparition des applications multimédia qui requièrent de plus en plus de bande passante, ainsi que des utilisateurs qui exigent une meilleure qualité de service. Dans cette perspective, beaucoup de travaux ont été effectués pour améliorer l'utilisation du spectre sans fil.Le sujet de ma thèse de doctorat porte sur l'application de la théorie des jeux, la théorie des files d'attente et l'apprentissage dans les réseaux sans fil,en particulier dans des environnements partiellement observables. Nous considérons différentes couches du modèle OSI. En effet, nous étudions l'accès opportuniste au spectre sans fil à la couche MAC en utilisant la technologie des radios cognitifs (CR). Par la suite, nous nous concentrons sur le contrôle de congestion à la couche transport, et nous développons des mécanismes de contrôle de congestion pour le protocole TCP.

Cette thèse étudie les communications directes entre les mobiles, appelées communications D2D, en tant que technique prometteuse pour améliorer les futurs réseaux cellulaires. Cette technologie permet une communication directe entre deux terminaux mobiles sans passer par la station de base. La modélisation, l'évaluation et l'optimisation des différents aspects des communications D2D constituent les objectifs fondamentaux de cette thèse et sont réalisés principalement à l'aide des outils mathématiques suivants: la théorie des files d'attente, l'optimisation de Lyapunov et les processus de décision markovien partiellement observable POMDP. Les résultats de cette étude sont présentés en trois parties. Dans la première partie, nous étudions un schéma de sélection entre mode cellulaire et mode D2D. Nous dérivons les régions de stabilité des scénarios suivants: réseaux cellulaires purs et réseaux cellulaires où les communications D2D sont activées. Une comparaison entre ces deux scénarios conduit à l'élaboration d'un algorithme de sélection entre le mode cellulaire et le mode D2D qui permet d'améliorer la capacité du réseau. Dans la deuxième partie, nous développons un algorithme d'allocation de ressources des communications D2D. Les utilisateurs D2D sont en mesure d'estimer leur propre qualité de canal, cependant la station de base a besoin de recevoir des messages de signalisation pour acquérir cette information. Sur la base de cette connaissance disponibles au niveau des utilisateurs D2D, une approche d'allocation des ressources est proposée afin d'améliorer l'efficacité énergétique des communications D2D. La version distribuée de cet algorithme s'avère plus performante que celle centralisée. Dans le schéma distribué des collisions peuvent se produire durant la transmission de l'état des canaux D2D ; ainsi un algorithme de réduction des collisions est élaboré. En outre, la mise en œuvre des algorithmes centralisé et distribué dans un réseau cellulaire, type LTE, est décrite en détails. Dans la troisième partie, nous étudions une politique de sélection des relais D2D mobiles. La mobilité des relais représente un des principaux défis que rencontre toute stratégie de sélection de relais. Le problème est modélisé par un processus contraint de décision markovien partiellement observable qui prend en compte le dynamisme des relais et vise à trouver la politique de sélection de relais qui optimise la performance du réseau cellulaire sous des contraintes de coût
This thesis considers Device-to-Device (D2D) communications as a promising technique for enhancing future cellular networks. Modeling, evaluating and optimizing D2D features are the fundamental goals of this thesis and are mainly achieved using the following mathematical tools: queuing theory, Lyapunov optimization and Partially Observed Markov Decision Process (POMDP). The findings of this study are presented in three parts. In the first part, we investigate a D2D mode selection scheme. We derive the queuing stability regions of both scenarios: pure cellular networks and D2D-enabled cellular networks. Comparing both scenarios leads us to elaborate a D2D vs cellular mode selection design that improves the capacity of the network. In the second part, we develop a D2D resource allocation algorithm. We observe that D2D users are able to estimate their local Channel State Information (CSI), however the base station needs some signaling exchange to acquire this information. Based on the D2D users' knowledge of their local CSI, we provide an energy efficient resource allocation framework that shows how distributed scheduling outperforms centralized one. In the distributed approach, collisions may occur between the different CSI reporting; thus, we propose a collision reduction algorithm. Moreover, we give a detailed description on how both centralized and distributed algorithms can be implemented in practice. In the third part, we propose a mobile relay selection policy in a D2D relay-aided network. Relays' mobility appears as a crucial challenge for defining the strategy of selecting the optimal D2D relays. The problem is formulated as a constrained POMDP which captures the dynamism of the relays and aims to find the optimal relay selection policy that maximizes the performance of the network under cost constraints

Cette thèse étudie les problèmes d'allocation des ressources dans les réseaux stochastiques à grande échelle dans lesquels les paramètres fluctuent dans le temps. Nous supposons que l'état du système est formé de deux processus, une partie contrôlable dont l'évolution dépend de l'action du décideur et la partie environnement dont l'évolution est exogène. L'évolution stochastique du processus contrôlable dépend de l'état actuel de l'environnement. Selon que le décideur observe l'état de l'environnement, nous disons que l'environnement est observable ou non observable.La thèse suit trois axes de recherche principaux. Dans le premier problème, nous étudions le contrôle optimal d'un problème de bandit agité multi-bras MARBP avec un environnement inobservable. L'objectif est de caractériser la politique optimale de maîtrise du processus contrôlable malgré le fait que l'environnement ne peut pas être observé. Nous considérons le régime asymptotique à grande échelle dans lequel le nombre de bandits et la vitesse de l'environnement tendent tous deux à l'infini. Dans notre résultat principal, nous établissons qu'un ensemble de politiques prioritaires est asymptotiquement optimal. Nous montrons que cet ensemble comprend notamment l'indice de Whittle d'un système dont les paramètres sont moyennés sur le comportement stationnaire de l'environnement. Dans le second problème, nous considérons un MARBP avec un environnement observable. L'objectif est de tirer parti des informations sur l'environnement pour dériver une politique optimale pour le processus contrôlable. En supposant que la condition technique d'indexabilité soit vérifiée, nous développons un algorithme pour calculer numériquement l'indice de Whittle. Nous appliquons ensuite ce résultat au cas particulier d'une file d'attente avec abandon. Nous établissons une indexabilité, et nous obtenons des caractérisations de l'indice de Whittle sous forme fermée. Dans le troisième problème, nous considérons un modèle d'allocation de fichiers dans un grand système de stockage, où il y a des fichiers répartis sur un ensemble de nœuds. Chaque nœud tombe en panne selon une loi qui dépend de la charge qu'il gère. Chaque fois qu'un nœud tombe en panne, tous les fichiers qu'il possédait sont réalloués selon une stratégie d'allocation fixe, et le nœud redémarre son travail en étant vide. Nous étudions l'évolution de la charge d'un nœud dans le régime de champ moyen, lorsque le nombre de fichiers et le nombre de nœuds deviennent importants. Nous prouvons l'existence et l'unicité de la mesure de probabilité stationnaire du processus, et la convergence dans la distribution de cette mesure
This thesis studies resource allocation problems in large-scale stochastic networks. We work on problems where the availability of resources is subject to time fluctuations, a situation that one may encounter, for example, in load balancing systems or in wireless downlink scheduling systems. The time fluctuations are modelled considering two types of processes, controllable processes, whose evolution depends on the action of the decision maker, and environment processes, whose evolution is exogenous. The stochastic evolution of the controllable process depends on the the current state of the environment. Depending on whether the decision maker observes the state of the environment, we say that the environment is observable or unobservable. The mathematical formulation used is the Markov Decision Processes (MDPs).The thesis follows three main research axes. In the first problem we study the optimal control of a Multi-armed restless bandit problem (MARBP) with an unobservable environment. The objective is to characterise the optimal policy for the controllable process in spite of the fact that the environment cannot be observed. We consider the large-scale asymptotic regime in which the number of bandits and the speed of the environment both tend to infinity. In our main result we establish that a set of priority policies is asymptotically optimal. We show that, in particular, this set includes Whittle index policy of a system whose parameters are averaged over the stationary behaviour of the environment. In the second problem, we consider an MARBP with an observable environment. The objective is to leverage information on the environment to derive an optimal policy for the controllable process. Assuming that the technical condition of indexability holds, we develop an algorithm to compute Whittle's index. We then apply this result to the particular case of a queue with abandonments. We prove indexability, and we provide closed-form expressions of Whittle's index. In the third problem we consider a model of a large-scale storage system, where there are files distributed across a set of nodes. Each node breaks down following a law that depends on the load it handles. Whenever a node breaks down, all the files it had are reallocated to other nodes. We study the evolution of the load of a single node in the mean-field regime, when the number of nodes and files grow large. We prove the existence of the process in the mean-field regime. We further show the convergence in distribution of the load in steady state as the average number of files per node tends to infinity

Cette thèse traite de méthodes « model-based » pour résoudre des problèmes d'apprentissage par renforcement. On considère un agent confronté à une suite de décisions et un environnement dont l'état varie selon les décisions prises par l'agent. Ce dernier reçoit tout au long de l'interaction des récompenses qui dépendent à la fois de l'action prise et de l'état de l'environnement. L'agent ne connaît pas le modèle d'interaction et a pour but de maximiser la somme des récompenses reçues à long terme. Nous considérons différents modèles d'interactions : les processus de décisions markoviens, les processus de décisions markoviens partiellement observés et les modèles de bandits. Pour ces différents modèles, nous proposons des algorithmes qui consistent à construire à chaque instant un ensemble de modèles permettant d'expliquer au mieux l'interaction entre l'agent et l'environnement. Les méthodes dites « model-based » que nous élaborons se veulent performantes tant en pratique que d'un point de vue théorique. La performance théorique des algorithmes est calculée en terme de regret qui mesure la différence entre la somme des récompenses reçues par un agent qui connaîtrait à l'avance le modèle d'interaction et celle des récompenses cumulées par l'algorithme. En particulier, ces algorithmes garantissent un bon équilibre entre l'acquisition de nouvelles connaissances sur la réaction de l'environnement (exploration) et le choix d'actions qui semblent mener à de fortes récompenses (exploitation). Nous proposons deux types de méthodes différentes pour contrôler ce compromis entre exploration et exploitation. Le premier algorithme proposé dans cette thèse consiste à suivre successivement une stratégie d'exploration, durant laquelle le modèle d'interaction est estimé, puis une stratégie d'exploitation. La durée de la phase d'exploration est contrôlée de manière adaptative ce qui permet d'obtenir un regret logarithmique dans un processus de décision markovien paramétrique même si l'état de l'environnement n'est que partiellement observé. Ce type de modèle est motivé par une application d'intérêt en radio cognitive qu'est l'accès opportuniste à un réseau de communication par un utilisateur secondaire. Les deux autres algorithmes proposés suivent des stratégies optimistes : l'agent choisit les actions optimales pour le meilleur des modèles possibles parmi l'ensemble des modèles vraisemblables. Nous construisons et analysons un tel algorithme pour un modèle de bandit paramétrique dans un cas de modèles linéaires généralisés permettant ainsi de considérer des applications telles que la gestion de publicité sur internet. Nous proposons également d'utiliser la divergence de Kullback-Leibler pour la construction de l'ensemble des modèles vraisemblables dans des algorithmes optimistes pour des processus de décision markoviens à espaces d'états et d'actions finis. L'utilisation de cette métrique améliore significativement le comportement de des algorithmes optimistes en pratique. De plus, une analyse du regret de chacun des algorithmes permet de garantir des performances théoriques similaires aux meilleurs algorithmes de l'état de l'art.