The emergence of shanzhaiji handset industry or bandit handset industry (山寨機手機產業) is an interesting phenomenon that is the only socioeconomic behavior occurring in mainland china. According to the National Development and Reform Commission of PRC, a company is permitted to produce the cellular phones with 200 million RMB and R&D capabilities. However, with only 100 thousands RMB capital, a shanzhaji handset producer can deliver the cellular phones in mainland china by getting a core technology of one package of chipset total solution (turnkey) from MediaTek / MTK (聯發科) in Taiwan. This new business model has been impacting the phone industry significantly in the mainland china. My research will focus on the development of entire shanzhaiji industry development from its origin to the status quo as well as future development. Three aspects of supply chain, market channel and government policy in terms of shanzhaiji industry are addressed in this research.

Cette thèse se penche sur les problèmes de décisions devant être prises de manière séquentielle au sein d'un environnement aléatoire. Lors de chaque étape d'un tel problème décisionnel, une alternative doit être sélectionnée parmi un ensemble d'alternatives. Chaque alternative possède un gain moyen qui lui est propre et lorsque l'une d'elles est sélectionnée, celle-ci engendre un gain aléatoire. La sélection opérée peut suivre deux types d'objectifs. Dans un premier cas, les tests viseront à maximiser la somme des gains collectés. Un juste compromis doit alors être trouvé entre l'exploitation et l'exploration. Ce problème est couramment dénommé dans la littérature scientifique "multi-armed bandit problem". Dans un second cas, un nombre de sélections maximal est imposé et l'objectif consistera à répartir ces sélections de façon à augmenter les chances de trouver l'alternative présentant le gain moyen le plus élevé. Ce deuxième problème est couramment repris dans la littérature scientifique sous l'appellation "selecting the best". La sélection de type gloutonne joue un rôle important dans la résolution de ces problèmes de décision et opère en choisissant l'alternative qui s'est jusqu'ici montrée optimale. Or, la nature généralement aléatoire de l'environnement rend incertains les résultats d'une telle sélection. Dans cette thèse, nous introduisons une nouvelle quantité, appelée le "gain espéré d'une action gloutonne". Sur base de quelques propriétés de cette quantité, de nouveaux algorithmes permettant de résoudre les deux problèmes décisionnels précités seront proposés. Une attention particulière sera ici prêtée à l'application des techniques présentées au domaine de la sélection de modèles en l'apprentissage artificiel supervisé. La collaboration avec le service d'anesthésie de l'Hôpital Erasme nous a permis d'appliquer les algorithmes proposés à des données réelles, provenant du milieu médical. Nous avons également développé un système d'aide à la décision dont un prototype a déjà été testé en conditions réelles sur un échantillon restreint de patients.

Dans le domaine de l'apprentissage par renforcement, la planifi ation dans les processus de décisions markoviens est une approche en ligne utilisée pour contrôler un système dont on possède un modèle génératif. Nous nous proposons d'adresser ce problème dans le cas déterministe avec espace d'action discret ou continu. Cette thèse s'attache au chapitre 2 à présenter succinctement les processus de décision markoviens puis l'apprentissage par renforcement. Nous présentons en particulier trois algorithmes centraux que sont l'itération de la valeur, l'itération de la politique et le Q-Learning. Au chapitre 3, nous expliquons l'approche de la planifi cation dans les processus de décision markoviens pour contrôler des systèmes en ligne. Ainsi, nous supposons posséder un modèle génératif d'un système à contrôler et nous l'utilisons pour décider, à chaque pas de temps du système à contrôler, de l'action à lui appliquer en vue de le faire transiter dans un état maximisant la somme future des récompenses dépréciées. Nous considérons un modèle génératif comme une boite noire, laquelle étant donnée un état et une action, nous retourne un état successeur ainsi qu'une récompense associée. L'approche optimiste est détaillée dans sa philosophie et dans son application à la résolution du dilemme exploration-exploitation au travers de di fférentes techniques présentes dans la littérature. Nous présentons di fférents algorithmes issus de la littérature et s'appliquant dans le cadre de la plani fication dans les processus de décision markoviens. Nous nous concentrons en particulier sur les algorithmes effectuant une recherche avant par construction d'un arbre des possibilités look-ahead tree en anglais. Les algorithmes sont présentés et mis en relation les uns avec les autres. L'algorithme de recherche du plus court chemin dans un graphe A est présenté en vue d'être relié à notre première contribution, l'algorithme de plani fication optimiste. Nous détaillons cette première contribution au chapitre 4. Dans un premier temps, nous présentons en détail le contexte de la planification sous contrainte de ressources computationnelles ainsi que la notion de regret. Dans un second temps, l'algorithme de plani cation uniforme est présenté et son regret est analysé pour obtenir une base comparative avec l'algorithme de plani cation optimiste. Enfi n, celui-ci est présenté et son regret est analysé. L'analyse est étendue à une classe de problèmes dé finie par la proportion de chemins -optimaux, permettant ainsi d'établir une borne supérieure sur le regret de l'algorithme de plani cation optimiste meilleure que celle de l'algorithme de plani cation uniforme dans le pire des cas. Des expérimentations sont menées pour valider la théorie et chi rer les performances de l'algorithme de plani cation optimiste par le biais de problèmes issus de la littérature comme le cart-pole, l'acrobot ou le mountain car et en comparaison à l'algorithme de plani cation uniforme, à l'algorithme UCT ainsi qu'à l'algorithme de recherche aléatoire. Nous verrons que, comme suggéré par la dé nition de la borne supérieure sur son regret, l'algorithme de plani cation optimiste est sensible au facteur de branchement ce qui nous mène à envisager le cas où l'espace d'action est continu. Ceci fait l'objet de nos deux autres contributions au chapitre 5. Notre deuxième contribution est l'algorithme de plani cation lipschitzienne reposant sur une hypothèse de régularité sur les récompenses menant à supposer que la fonction de transition et la fonction récompense du processus de décision markovien modélisant le système à contrôler sont lipschitziennes. De cette hypothèse, nous formulons une borne sur un sous-ensemble de sousespaces de l'espace d'action continu nous permettant de l'explorer par discr étisations successives. L'algorithme demande cependant la connaissance de la constante de Lipschitz associée au système à contrôler. Des expérimentations sont menées pour évaluer l'approche utilisée pour diff érentes constantes de Lipschitz sur des problèmes de la littérature comme le cart-pole, l'acrobot ou la lévitation magnétique d'une boule en acier. Les résultats montrent que l'estimation de la constante de Lipschitz est diffi cile et ne permet pas de prendre en compte le paysage local des récompenses. Notre troisième contribution est l'algorithme de plani cation séquentielle découlant d'une approche intuitive où une séquence d'instances d'un algorithme d'optimisation globale est utilisée pour construire des séquences d'actions issues de l'espace d'action continu. Des expérimentations sont menées pour évaluer cet approche intuitive pour diff érents algorithmes d'optimisation globale sur des problèmes de la littérature comme le cart-pole, le bateau ou le nageur. Les résultats obtenus sont encourageants et valident l'approche intuitive. Finalement, nous concluons en résumant les di érentes contributions et en ouvrant sur de nouvelles perspectives et extensions.

No description available.

Age of information (AoI) captures the freshness of information and has been used broadly for scheduling data transmission in the Internet of Things (IoT). We consider a general scenario where a meaningful piece of information consists of multiple packets and the information would not be considered complete until all related packets have been correctly received. This general scenario, seemingly a trivial extension of exiting work where information update is in terms of single packet, is actually challenging in both scheduling algorithm design and theoretical analysis, because we need to track the history of received packets before a complete piece of information can be updated. We first analyse the necessary condition for optimal scheduling based on which we present an optimal scheduling method. The optimal solution, however, has high time complexity. To address the problem, we investigate the problem in the framework of restless multi-armed bandit (RMAB) and propose an index-based scheduling policy by applying Whittle index. We also propose a new transmission strategy based on erasure codes to improve the performance of scheduling policies in lossy networks. Performance evaluation results demonstrate that our solution outperforms other baseline policies such as greedy policy and naive Whittle index policy in both lossless and lossy networks. / Graduate

This work explores the legendary 19th-century California bandit Joaquin Murieta as he is manifest in the history, literature and folklore of the West. The first section of the work examines in some detail the historical milieu which gave rise to widespread banditry dur~ng the California gold rush, at which time Murieta is said to have been active. The second section traces the development of the literary hero Joaquin Murieta from his creation by John Rollin Ridge through a number of American, Mexican, Chilean, Spanish and French incarnations. Section three similarly traces Murieta as a folk hero through a cycle of legends perpetuated by California's Anglo-American folk community. Section four of the work returns to history, examining in some detail the evolving relationship between California's Mexican-American and Anglo-American populations in the century following the gold rush. The fifth section explores Murieta's development and perpetuation as a folk hero in the~ Mexican-American folk community. The work's final section examines some dynamic mechanisms at work in the evolution of Murieta folk lore, and suggests some directions for further study.

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 ?a 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 pérvasifs. Le problème avec les approches traditionnelles de recommandation 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 recommandations sensibles au contexte (CARS) combinent les caractéristiques des systèmes sensibles au contexte et des systèmes de recommandation an de fournir des informations personnalisées aux utilisateurs dans des environnements ubiquitaires. Dans cette perspective ou 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 la dynamicité des contenus de l'utilisateur ? et ii ) Comment éviter d'être intrusif en particulier dans des situations critiques ?. En réponse ?a 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 Con dence Bound), le meilleur algorithme actuellement disponible, en calculant la valeur d'exploration la plus optimale pour maintenir un 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.

Les systèmes de recommandation actuels ont besoin de recommander des objets pertinents aux utilisateurs (exploitation), mais pour cela ils doivent pouvoir également obtenir continuellement de nouvelles informations sur les objets et les utilisateurs encore peu connus (exploration). Il s'agit du dilemme exploration/exploitation. Un tel environnement s'inscrit dans le cadre de ce que l'on appelle " apprentissage par renforcement ". Dans la littérature statistique, les stratégies de bandit sont connues pour offrir des solutions à ce dilemme. Les contributions de cette thèse multidisciplinaire adaptent ces stratégies pour appréhender certaines problématiques des systèmes de recommandation, telles que la recommandation de plusieurs objets simultanément, la prise en compte du vieillissement de la popularité d'un objet ou encore la recommandation en temps réel. / Current recommender systems need to recommend items that are relevant to users (exploitation), but they must also be able to continuously obtain new information about items and users (exploration). This is the exploration / exploitation dilemma. Such an environment is part of what is called "reinforcement learning". In the statistical literature, bandit strategies are known to provide solutions to this dilemma. The contributions of this multidisciplinary thesis the adaptation of these strategies to deal with some problems of the recommendation systems, such as the recommendation of several items simultaneously, taking into account the aging of the popularity of an items or the recommendation in real time.

Des problèmes de Bandit constituent une séquence d’allocation dynamique. D’une part, l’agent de système doit explorer son environnement ( à savoir des bras de machine) pour recueillir des informations; d’autre part, il doit exploiter les informations collectées pour augmenter la récompense. Comment d’équilibrer adéquatement la phase d’exploration et la phase d’exploitation, c’est une obscurité des problèmes de Bandit, et la plupart des chercheurs se concentrent des efforts sur les stratégies d’équilibration entre l’exploration et l’exploitation. Dans cette dissertation, nous nous concentrons sur l’étude de deux problèmes spécifiques de Bandit: les problèmes de Bandit contextuel et les problèmes de Bandit Multi- objectives. Cette dissertation propose deux aspects de contributions. La première concerne la classification sous la surveillance partielle, laquelle nous codons comme le problème de Bandit contextuel avec des informations partielles. Ce type des problèmes est abondamment étudié par des chercheurs, en appliquant aux réseaux sociaux ou systèmes de recommandation. Nous proposons une série d’algorithmes sur la base d’algorithme Passive-Aggressive pour résoudre des problèmes de Bandit contextuel. Nous profitons de sa fondations, et montrons que nos algorithmes sont plus simples à mettre en œuvre que les algorithmes en état de l’art. Ils réalisent des biens performances de classification. Pour des problèmes de Bandit Multi-objective (MOMAB), nous proposons une méthode motivée efficace et théoriquement à identifier le front de Pareto entre des bras. En particulier, nous montrons que nous pouvons trouver tous les éléments du front de Pareto avec un budget minimal dans le cadre de PAC borne. / Bandit problems constitute a sequential dynamic allocation problem. The pulling agent has to explore its environment (i.e. the arms) to gather information on the one hand, and it has to exploit the collected clues to increase its rewards on the other hand. How to adequately balance the exploration phase and the exploitation phase is the crux of bandit problems and most of the efforts devoted by the research community from this fields has focused on finding the right exploitation/exploration tradeoff. In this dissertation, we focus on investigating two specific bandit problems: the contextual bandit problems and the multi-objective bandit problems. This dissertation provides two contributions. The first contribution is about the classification under partial supervision, which we encode as a contextual bandit problem with side informa- tion. This kind of problem is heavily studied by researchers working on social networks and recommendation systems. We provide a series of algorithms to solve the Bandit feedback problem that pertain to the Passive-Aggressive family of algorithms. We take advantage of its grounded foundations and we are able to show that our algorithms are much simpler to implement than state-of-the-art algorithms for bandit with partial feedback, and they yet achieve better perfor- mances of classification. For multi-objective multi-armed bandit problem (MOMAB), we propose an effective and theoretically motivated method to identify the Pareto front of arms. We in particular show that we can find all elements of the Pareto front with a minimal budget.

Problems in statistical analysis, economics, and many other disciplines often involve a trade-off between rewards and additional information that could yield higher future rewards. This thesis investigates such a trade-off, using a class of problems known as bandit problems. In these problems, a reward-seeking agent makes decisions based upon his beliefs about a parameter that controls rewards. While some choices may generate higher short-term rewards, other choices may provide information that allows the agent to learn about the parameter, thereby potentially increasing future rewards. Learning occurs if the agent's subjective beliefs about the parameter converge over time to the parameter's true value. However, depending upon the environment, learning may or may not be optimal, as in the end, the agent cares about maximizing rewards and not necessarily learning the true value of the underlying parameter.