Nyfikenhet är inneboende strävan mot inhämtande av ny information. Länge har det ansetts vedertaget att yttre motivation hämmar nyfikenhet, men på senare år har det framkommit forskning som indikerar ett delvis annorlunda förhållande. För att undersöka interaktionen mellan nyfikenhet och yttre motivation konstruerades ett bildbaserat inlärningsexperiment i vilket deltagarna belönades respektive bestraffades för att inhämta information som stillade deras nyfikenhet. I experimentets första del skattade deltagarna sin nyfikenhet på mosaikmaskerade bilder. I experimentets andra del presenterades de skattade mosaikbilderna med en konstant bild. De 24 deltagarnas uppgift var att välja en av de två bilderna i varje spelomgång. Bilden deltagarna valde demaskerades efter olika väntetider. Väntetiden var antingen dragen från en lång eller kort väntetidsfördelning och avhängig om bilden var ny eller återkommande. Huruvida det var den nya eller återkommande bilden som hade kort respektive lång medelväntetid varierade mellan de två inomgrupps-betingelserna. Deltagarna antogs vara yttre motiverade att minimera väntetiden genom att lära sig och sedan föredra den bildkategori med kortast genomsnittlig väntetid. Deltagarna antogs dessutom vara nyfikna att se bilder demaskerade. I ena betingelsen sammanföll deltagarnas yttre motivation och nyfikenhet, i andra betingelsen var deltagarnas yttre motivation och nyfikenhet i konflikt. I en tredje kontrollbetingelse var nyfikenhetsdimensionen eliminerad för att mäta inlärning av väntetid. Experimentet visade att det krävdes fler spelomgångar för att lära sig väntetiden i kontrollbetingelsen jämfört med betingelsen där nya bilder också hade kortare medelväntetid. Betingelsen där nya bilder var förknippade med längre medelväntetid delade deltagarna i två grupper. Deltagare i den ena gruppen valde sällan nya bilder (proportionsmått: 0.75 – 1.0) medan deltagare i den andra gruppen valde nya bilder i hög utsträckning (proportionsmått: 0.0077 – 0.069). Dessa grupper utmärks också på personlighetsdrag kopplade till nyfikenhet. Sammantaget ger studien stöd för att nyfikenhet och yttre motivation kan integreras och att personlighetsdrag är relaterade till värderingen av information. / Curiosity is an intrinsic aspiration to obtain new information. It has been considered that external motivation inhibits curiosity, but over the last years new research has indicated a partially different relationship. To investigate the interaction between curiosity and external motivation a picture-based learning experiment was constructed, in which the participants were rewarded, alternatively punished for obtaining new information which pleased their curiosity. In the first part of the experiment, the participants scored their curiosity of mosaic-covered pictures. In the second part of the of the experiment, the scored mosaic-covered pictures were consequently presented next to a constant picture. The task for the 24 participants was then to choose one of the pictures in each round. The chosen mosaic-covered picture would then show according to a certain waiting time - either short or long - depending on if it was new or recurring. Whether the new or recurring picture had a short or long average waiting time varied between the two in-group conditions. It was hypothesized that the participants would be externally motivated to minimize the waiting time by learning and favouring the category of pictures with the shortest waiting time. In addition, it was hypothesized that the participants would be curious of the mosaic-covered pictures. In one of the conditions, the participants external motivation coincided with their curiosity, in the other condition the external motivation was in conflict with their curiosity. In a third controlling condition, the dimension of curiosity was eliminated to measure the learning of the waiting time. The experiment showed that more rounds are needed to learn the waiting time in the controlling conditions compared to when the new pictures also had a shorter average waiting time. When new pictures were associated with a longer average waiting time, it divided the participants into two groups. In one group the participant rarely chose new pictures (proportion: 0.75 – 1.0) while the participants in the other group to a large extent chose new pictures (proportion: 0.0077 – 0.069). These differences were also shown in the participants personal traits connected to curiosity. All together, the study supports the idea that curiosity and external motivation can be integrated and that personal traits are related to the evaluation of information.

No description available.

Dans cette thèse, nous abordons le problème fondamental de l'accès au spectre opportuniste dans un système de communication multi-canal. Plus précisément, nous considérons un système de communication dans lequel un utilisateur a accès à de multiples canaux, tout en étant limité à la détection et la transmission sur un sous-ensemble de canaux. Nous explorons comment l'utilisateur intelligent exploite ses observations passées et les propriétés stochastiques de ces canaux afin de maximiser son débit. Formellement, nous fournissons une analyse générique sur le problème d'accès au spectre opportuniste en nous basant sur le problème de `restless multi-bandit’ (RMAB), l'une des généralisations les plus connues du problème classique de multi-armed bandit (MAB), un problème fondamental dans la théorie de décision stochastique. Malgré les importants efforts de la communauté de recherche dans ce domaine, le problème RMAB dans sa forme générique reste encore ouvert. Jusqu'à aujourd'hui, très peu de résultats sont connus sur la structure de la politique optimale. L'obtention de la politique optimale pour un problème RMAB général est intraçable dû la complexité de calcul exponentiel. Par conséquent, une alternative naturelle est de se focaliser sur la politique myopique qui maximise la récompense à immédiate, tout en ignorant celles du futur. Donc, nous développons trois axiomes caractérisant une famille de fonctions que nous appelons fonctions régulières, qui sont génériques et pratiquement importantes. Nous établissons ensuite l'optimalité de la politique myopique lorsque la fonction de récompense peut être exprimée comme une fonction régulière et le facteur de discount est borné par un seuil déterminé par la fonction de récompense. Nous illustrons également l'application des résultats pour analyser une classe de problèmes RMAB dans l'accès opportuniste. Ensuite, nous étudions un problème plus difficile, où l'utilisateur doit configurer le nombre de canaux à accéder afin de maximiser son utilité (par exemple, le débit). Après avoir montré la complexité exponentielle du problème, nous développons une stratégie heuristique v-step look-ahead. Dans la stratégie développée, le paramètre v permet de parvenir à un compromis souhaité entre l'efficacité sociale et de la complexité de calcul. Nous démontrons les avantages de la stratégie proposée via des simulations numériques sur plusieurs scénarios typiques. / In the thesis, we address the fundamental problem of opportunistic spectrum access in a multi-channel communication system. Specifically, we consider a communication system in which a user has access to multiple channels, but is limited to sensing and transmitting only on one at a given time. We explore how the smart user should exploit past observations and the knowledge of the stochastic properties of these channels to maximize its transmission rate by switching channels opportunistically. Formally, we provide a generic analysis on the opportunistic spectrum access problem by casting the problem into the restless multi-armed bandit (RMAB) problem, one of the most well-known generalizations of the classic multi-armed bandit (MAB) problem, which is of fundamental importance in stochastic decision theory. Despite the significant research efforts in the field, the RMAB problem in its generic form still remains open. Until today, very little result is reported on the structure of the optimal policy. Obtaining the optimal policy for a general RMAB problem is often intractable due to the exponential computation complexity. Hence, a natural alternative is to seek a simple myopic policy maximizing the short-term reward. Therefore, we develop three axioms characterizing a family of functions which we refer to as regular functions, which are generic and practically important. We then establish the optimality of the myopic policy when the reward function can be expressed as a regular function and the discount factor is bounded by a closed-form threshold determined by the reward function. We also illustrate how the derived results, generic in nature, are applied to analyze a class of RMAB problems arising from multi-channel opportunistic access. Next, we further investigate the more challenging problem where the user has to decide the number of channels to sense in each slot in order to maximize its utility (e.g., throughput). After showing the exponential complexity of the problem, we develop a heuristic v-step look-ahead strategy. In the developed strategy, the parameter v allows to achieve a desired tradeoff between social efficiency and computation complexity. We demonstrate the benefits of the proposed strategy via numerical experiments on several typical settings.

Dans cette thèse, nous étudions le contrôle dynamique des systèmes de partage de ressources qui se posent dans divers domaines : réseaux de gestion des stocks, services de santé, réseaux de communication, etc. Nous visons à allouer efficacement les ressources disponibles entre des projets concurrents, selon certains critères de performance. Ce type de problème est de nature stochastique et peut être très complexe à résoudre. Nous nous concentrons donc sur le développement de méthodes heuristiques performantes. Dans la partie I, nous nous plaçons dans le cadre des Restless Bandit Problems, qui est une classe générale de problèmes d’optimisation dynamique stochastique. Relaxer la contrainte de trajectoire dans le problème d’optimisation permet de définir une politique d’index comme heuristique pour le modèle contraint d’origine, aussi appelée politique d’index de Whittle. Nous dérivons une expression analytique pour l’index de Whittle en fonction des probabilités stationnaires de l’état dans le cas où les bandits (ou projets) suivent un processus de naissance et de mort. D’une part, cette expression nécessite la vérification de plusieurs conditions techniques, d’autre part elle ne peut être calculée explicitement que dans certains cas spécifiques. Nous prouvons ensuite, que dans le cas particulier d’une file d’attente multi-classe avec abandon, la politique d’index de Whittle est asymptotiquement optimale aussi bien pour les régimes à faible trafic comme pour ceux à fort trafic. Dans la partie II, nous dérivons des heuristiques issues de l’approximation des systèmes stochastiques de partage de ressources par des modèles fluides déterministes. Nous formulons dans un premier temps une version fluide du problème d’optimisation relaxé que nous avons introduit dans la partie I, et développons une politique d’index fluide. L’index fluide peut toujours être calculé explicitement et surmonte donc les questions techniques qui se posent lors du calcul de l’index de Whittle. Nous appliquons les politiques d’index de Whittle et de l’index fluide à plusieurs cas : les fermes de serveurs éco-conscients, l’ordonnancement opportuniste dans les systèmes sans fil, et la gestion de stockage de produits périssables. Nous montrons numériquement que ces politiques d’index sont presque optimales. Dans un second temps, nous étudions l’ordonnancement optimal de la version fluide d’une file d’attente multi-classe avec abandon. Nous obtenons le contrôle optimal du modèle fluide en présence de deux classes de clients en concurrence pour une même ressource. En nous appuyant sur ces derniers résultats, nous proposons une heuristique pour le cas général de plusieurs classes. Cette heuristique montre une performance quasi-optimale lorsqu’elle est appliquée au modèle stochastique original pour des charges de travail élevées. Enfin, dans la partie III, nous étudions les phénomènes d’abandon dans le contexte d’un problème de distribution de contenu. Nous caractérisons une politique optimale de regroupement afin que des demandes issues d’utilisateurs impatients puissent être servies efficacement en mode diffusion. / In this thesis we study the dynamic control of resource-sharing systems that arise in various domains: e.g. inventory management, healthcare and communication networks. We aim at efficiently allocating the available resources among competing projects according to a certain performance criteria. These type of problems have a stochastic nature and may be very complex to solve. We therefore focus on developing well-performing heuristics. In Part I, we consider the framework of Restless Bandit Problems, which is a general class of dynamic stochastic optimization problems. Relaxing the sample-path constraint in the optimization problem enables to define an index-based heuristic for the original constrained model, the so-called Whittle index policy. We derive a closed-form expression for the Whittle index as a function of the steady-state probabilities for the case in which bandits (projects) evolve in a birth-and-death fashion. This expression requires several technical conditions to be verified, and in addition, it can only be computed explicitly in specific cases. In the particular case of a multi-class abandonment queue, we further prove that the Whittle index policy is asymptotically optimal in the light-traffic and heavy-traffic regimes. In Part II, we derive heuristics by approximating the stochastic resource-sharing systems with deterministic fluid models. We first formulate a fluid version of the relaxed optimization problem introduced in Part I, and we develop a fluid index policy. The fluid index can always be computed explicitly and hence overcomes the technical issues that arise when calculating the Whittle index. We apply the Whittle index and the fluid index policies to several systems: e.g. power-aware server-farms, opportunistic scheduling in wireless systems, and make-to-stock problems with perishable items. We show numerically that both index policies are nearly optimal. Secondly, we study the optimal scheduling control for the fluid version of a multi-class abandonment queue. We derive the fluid optimal control when there are two classes of customers competing for a single resource. Based on the insights provided by this result we build a heuristic for the general multi-class setting. This heuristic shows near-optimal performance when applied to the original stochastic model for high workloads. In Part III, we further investigate the abandonment phenomena in the context of a content delivery problem. We characterize an optimal grouping policy so that requests, which are impatient, are efficiently transmitted in a multi-cast mode.

Les Algorithmes Évolutionnaires sont des algorithmes d'optimisation qui ont déjà montré leur efficacité dans plusieurs domaines; mais leur performance dépend du réglage de plusieurs paramètres. Cette thèse est consacrée au développement de techniques pour automatiser ce réglage par le biais de l'apprentissage automatique. Plus spécifiquement, nous avons travaillé sur un sous-problème: étant donné un ensemble d'opérateurs, cela consiste à choisir lequel doit être appliqué pour la génération de chaque nouvelle solution, basé sur la performance connue de chaque opérateur. Cette approche est utilisée en ligne, au cours de la résolution du problème, en utilisant exclusivement l'histoire du processus d'optimisation courant pour décider parmi les différents opérateurs; ce paradigme est couramment référencé comme Sélection Adaptative d'Opérateurs (SAO). Pour faire de la SAO, deux composants sont nécessaires. L'Affectation de Crédit définit comment récompenser les opérateurs selon l'impact de leur application sur le processus de recherche. La Sélection d'Opérateurs règle leur choix selon les récompenses reçues ultérieurement. En résumé, la contribution principale de cette thèse consiste dans la proposition et l'analyse de différentes approches pour la SAO, basées sur le paradigme de Bandit Manchot (BM); nous avons proposé plusieurs modifications pour transformer un algorithme BM en une technique à la fois performante dans l'environnement dynamique de la SAO, et robuste par rapport aux caractéristiques des problèmes diverses. La dernière méthode, appelé AUC-MAB, est capable de suivre efficacement le meilleur opérateur sans nécessiter d'un réglage spécifique pour chaque problème.

<div>The multi-armed bandit (MAB) problem refers to the task of sequentially assigning treatments to experimental units so as to identify the best treatment(s) while controlling the opportunity cost of further investigation. Many algorithms have been developed that attempt to balance this trade-off between exploiting the seemingly optimum treatment and exploring the other treatments. The selection of an MAB algorithm for implementation in a particular context is often performed by comparing candidate algorithms in terms of their abilities to control the expected regret of exploration versus exploitation. This singular criterion of mean regret is insufficient for many practical problems, and therefore an additional criterion that should be considered is control of the variance, or risk, of regret.</div><div>This work provides an overview of how the existing prominent MAB algorithms handle both criteria. We additionally investigate the effects of incorporating prior information into an algorithm's model, including how sharing information across treatments affects the mean and variance of regret.</div><div>A unified and accessible framework does not currently exist for constructing MAB algorithms that control both of these criteria. To this end, we develop such a framework based on the two elementary concepts of dismemberment of treatments and a designed learning phase prior to dismemberment. These concepts can be incorporated into existing MAB algorithms to effectively yield new algorithms that better control the expectation and variance of regret. We demonstrate the utility of our framework by constructing new variants of the Thompson sampler that involve a small number of simple tuning parameters. As we illustrate in simulation and case studies, these new algorithms are implemented in a straightforward manner and achieve improved control of both regret criteria compared to the traditional Thompson sampler. Ultimately, our consideration of additional criteria besides expected regret illuminates novel insights into the multi-armed bandit problem.</div><div>Finally, we present visualization methods, and a corresponding R Shiny app for their practical execution, that can yield insights into the comparative performances of popular MAB algorithms. Our visualizations illuminate the frequentist dynamics of these algorithms in terms of how they perform the exploration-exploitation trade-off over their populations of realizations as well as the algorithms' relative regret behaviors. The constructions of our visualizations facilitate a straightforward understanding of complicated MAB algorithms, so that our visualizations and app can serve as unique and interesting pedagogical tools for students and instructors of experimental design.</div>

Neste experimento antropológico, fortemente inspirado na obra de Michel Foucault, apresento uma etnografia constituída principalmente a partir de conversas travadas com presos, ex-presos e seus familiares, em torno de experiências prisionais. No primeiro capítulo, exploro diferentes compreensões sobre o proceder e sobre a divisão espacial convívio-seguro, elaboradas como resposta à pergunta nativa o que é o certo?. Cada uma delas se faz como defesa do coletivo de presos donde emerge e como execração dos coletivos inimigos. No segundo capítulo, busco deslindar uma dimensão de estratégias adjacente a essas compreensões, onde os presos são levados a prestar atenção a eles próprios, precavendo-se para manterem um singular equilíbrio entre ser humilde e ser cabuloso. Nisso consiste o sentido do que designam por ser ladrão. Finalmente, no último capítulo mapeio uma noção de crime fundamental aos meus interlocutores, definido como movimento que estabelece as alianças nutridas entre ladrões e outros aliados ao mesmo tempo em que define inimigos a partir de considerações sobre suas caminhadas. / In this anthropological experiment inspired in the Michel Foucault works I present an ethnography mainly constituted from conversations with prisoners, ex-prisoners and their families about the experience of prison. In the first chapter I tried to present the native answers to the question they address to themselves: Which is the right way to behave?. So I worked on the meanings of the native concept of proceder and the internal division of the space of the prisons under the conviviality-security label. In each of these places they present their defenses and claim to be acting the right way, condemning the other collectivity. In the second chapter I show the strategies that underlies in the proceder especially those that make them pay attention to themselves in a balance between being humble and being fearless, the main definition they present for being a bandit. Finally, in the last chapter, I map the native concept of crime defined as a movement that institute the nurturing alliances among bandits and other allies in the same time that define the enemies from the speculations they get in their path.

L’immense quantité d'information générée et gérée au quotidien par les systèmes d'information et leurs utilisateurs conduit inéluctablement à la problématique de surcharge d'information. Dans ce contexte, les systèmes de recommandation traditionnels fournissent des informations pertinentes aux utilisateurs. Néanmoins, avec la propagation récente des dispositifs mobiles (smartphones et tablettes), nous constatons une migration progressive des utilisateurs vers la manipulation d'environnements pervasifs. Le problème avec les approches de recommandation traditionnelles est qu'elles n'utilisent pas toute l'information disponible pour produire des recommandations. Davantage d’informations contextuelles pourraient être utilisées dans le processus de recommandation pour aboutir à des recommandations plus précises. Les systèmes de recommandation sensibles au contexte (CARS) combinent les caractéristiques des systèmes sensibles au contexte et des systèmes de recommandation afin de fournir des informations personnalisées aux utilisateurs dans des environnements ubiquitaires. Dans cette perspective où tout ce qui concerne l'utilisateur est dynamique, les contenus qu’il manipule et son environnement, deux questions principales doivent être adressées : i) Comment prendre en compte l'évolution des contenus de l’utilisateur? et ii) Comment éviter d’être intrusif, en particulier dans des situations critiques? En réponse à ces questions, nous avons développé un système de recommandation dynamique et sensible au risque appelé DRARS (Dynamic Risk-Aware Recommender System), qui modélise la recommandation sensible au contexte comme un problème de bandit. Ce système combine une technique de filtrage basée sur le contenu et un algorithme de bandit contextuel. Nous avons montré que DRARS améliore la stratégie de l'algorithme UCB (Upper Confidence Bound), le meilleur algorithme actuellement disponible, en calculant la valeur d'exploration la plus optimale pour maintenir un bon compromis entre exploration et exploitation basé sur le niveau de risque de la situation courante de l'utilisateur. Nous avons mené des expériences dans un contexte industriel avec des données réelles et des utilisateurs réels et nous avons montré que la prise en compte du niveau de risque de la situation de l'utilisateur augmentait significativement la performance du système de recommandation / The vast amount of information generated and maintained everyday by information systems and their users leads to the increasingly important concern of overload information. In this context, traditional recommender systems provide relevant information to the users. Nevertheless, with the recent dissemination of mobile devices (smartphones and tablets), there is a gradual user migration to the use of pervasive computing environments. The problem with the traditional recommendation approaches is that they do not utilize all available information for producing recommendations. More contextual parameters could be used in the recommendation process to result in more accurate recommendations. Context-Aware Recommender Systems (CARS) combine characteristics from context-aware systems and recommender systems in order to provide personalized recommendations to users in ubiquitous environments. In this perspective where everything about the user is dynamic, his/her content and his/her environment, two main issues have to be addressed: i) How to consider content evolution? and ii) How to avoid disturbing the user in risky situations?. In response to these problems, we have developed a dynamic risk sensitive recommendation system called DRARS (Dynamic Risk-Aware Recommender System), which model the context-aware recommendation as a bandit problem. This system combines a content-based technique and a contextual bandit algorithm. We have shown that DRARS improves the Upper Confidence Bound (UCB) policy, the currently available best algorithm, by calculating the most optimal exploration value to maintain a trade-off between exploration and exploitation based on the risk level of the current user's situation. We conducted experiments in an industrial context with real data and real users and we have shown that taking into account the risk level of users' situations significantly increases the performance of the recommender system

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.

This habilitation thesis presents several contributions to (1) the PAC-Bayesian analysis of statistical learning, (2) the three aggregation problems: given d functions, how to predict as well as (i) the best of these d functions (model selection type aggregation), (ii) the best convex combination of these d functions, (iii) the best linear combination of these d functions, (3) the multi-armed bandit problems.