Rozprawy doktorskie na temat „Bandit Contextuel”

Cette thèse s'intéresse au problème de l'apprentissage à partir d'interactions en utilisant le cadre du bandit contextuel hors ligne. En particulier, nous nous intéressons à deux sujets connexes : (1) l'apprentissage de politiques hors ligne avec des certificats de performance, et (2) l'apprentissage rapide et efficace de politiques, pour le problème de recommandation à grande échelle. Pour (1), nous tirons d'abord parti des résultats du cadre d'optimisation distributionnellement robuste pour construire des bornes asymptotiques, sensibles à la variance, qui permettent l'évaluation des performances des politiques. Ces bornes nous aident à obtenir de nouveaux objectifs d'apprentissage plus pratiques grâce à leur nature composite et à leur calibrage simple. Nous analysons ensuite le problème d'un point de vue PAC-Bayésien et fournissons des bornes, plus étroites, sur les performances des politiques. Nos résultats motivent de nouvelles stratégies, qui offrent des certificats de performance sur nos politiques avant de les déployer en ligne. Les stratégies nouvellement dérivées s'appuient sur des objectifs d'apprentissage composites qui ne nécessitent pas de réglage supplémentaire. Pour (2), nous proposons d'abord un modèle bayésien hiérarchique, qui combine différents signaux, pour estimer efficacement la qualité de la recommandation. Nous fournissons les outils computationnels appropriés pour adapter l'inférence aux problèmes à grande échelle et démontrons empiriquement les avantages de l'approche dans plusieurs scénarios. Nous abordons ensuite la question de l'accélération des approches communes d'optimisation des politiques, en nous concentrant particulièrement sur les problèmes de recommandation avec des catalogues de millions de produits. Nous dérivons des méthodes d'optimisation, basées sur de nouvelles approximations du gradient calculées en temps logarithmique par rapport à la taille du catalogue. Notre approche améliore le temps linéaire des méthodes courantes de calcul de gradient, et permet un apprentissage rapide sans nuire à la qualité des politiques obtenues
This thesis presents contributions to the problem of learning from logged interactions using the offline contextual bandit framework. We are interested in two related topics: (1) offline policy learning with performance certificates, and (2) fast and efficient policy learning applied to large scale, real world recommendation. For (1), we first leverage results from the distributionally robust optimisation framework to construct asymptotic, variance-sensitive bounds to evaluate policies' performances. These bounds lead to new, more practical learning objectives thanks to their composite nature and straightforward calibration. We then analyse the problem from the PAC-Bayesian perspective, and provide tighter, non-asymptotic bounds on the performance of policies. Our results motivate new strategies, that offer performance certificates before deploying the policies online. The newly derived strategies rely on composite learning objectives that do not require additional tuning. For (2), we first propose a hierarchical Bayesian model, that combines different signals, to efficiently estimate the quality of recommendation. We provide proper computational tools to scale the inference to real world problems, and demonstrate empirically the benefits of the approach in multiple scenarios. We then address the question of accelerating common policy optimisation approaches, particularly focusing on recommendation problems with catalogues of millions of items. We derive optimisation routines, based on new gradient approximations, computed in logarithmic time with respect to the catalogue size. Our approach improves on common, linear time gradient computations, yielding fast optimisation with no loss on the quality of the learned policies

Cette thèse développe des méthodes d'Inférence Variationnelle pour l'apprentissage bayésien en grande dimension. L'approche bayésienne en machine learning permet de gérer l'incertitude épistémique des modèles et ainsi de mieux quantifier l'incertitude de ces modèles, ce qui est nécessaire dans de nombreuses applications de machine learning. Cependant, l'inférence bayésienne n'est souvent pas réalisable car la distribution à posteriori des paramètres du modèle n'est pas calculable en général. L'Inférence Variationnelle (VI) est une approche qui permet de contourner ce problème en approximant la distribution à posteriori par une distribution plus simple appelée distribution Variationnelle.Dans la première partie de cette thèse, nous avons travaillé sur les garanties théoriques de l'Inférence Variationnelle. Dans un premier temps, nous avons étudié cette approche lorsque la distribution Variationnelle est une Gaussienne, dans le régime surparamétré, c'est-à-dire lorsque les modèles sont en très grande dimension. Puis, nous nous sommes intéressés aux distributions Variationnelles plus expressives que sont les mélanges de Gaussiennes et nous avons étudié à la fois l'erreur d'optimisation et l'erreur d'approximation de cette méthode.Dans la deuxième partie de la thèse, nous avons étudié les garanties théoriques des problèmes de bandit contextuels en utilisant une approche bayésienne appelée Thompson Sampling. Dans un premier temps, nous avons exploré l'utilisation d'Inférence Variationnelle pour l'algorithme Thompson Sampling. Nous avons notament démontré que dans le cadre linéaire, cette approche permet d'obtenir les mêmes garanties théoriques que lorsque la distribution à posteriori est connue. Dans un deuxième temps, nous avons étudié une variante de Thompson Sampling appelée Feel-Good Thompson Sampling (FG-TS). Cette méthode permet d'obtenir de meilleures garanties théoriques que l'algorithme classique. Nous avons alors étudié l'utilisation d'une méthode de Monte Carlo Markov Chain pour approximer la distribution à posteriori. Plus spécifiquement, nous avons ajouté à FG-TS un algorithme de Langevin Monte Carlo et de Metropolized Langevin Monte Carlo. De plus, nous avons obtenu les mêmes garanties théoriques que pour FG-TS lorsque la distribution à posteriori est connue
This thesis explores Variational Inference methods for high-dimensional Bayesian learning. In Machine Learning, the Bayesian approach allows one to deal with epistemic uncertainty and provides and a better uncertainty quantification, which is necessary in many machine learning applications. However, Bayesian inference is often not feasible because the posterior distribution of the model parameters is generally untractable. Variational Inference (VI) allows to overcome this problem by approximating the posterior distribution with a simpler distribution called the variational distribution.In the first part of this thesis, we worked on the theoretical guarantees of Variational Inference. First, we studied VI when the Variational distribution is a Gaussian and in the overparameterized regime, i.e., when the models are high dimensional. Finally, we explore the Gaussian mixtures Variational distributions, as it is a more expressive distribution. We studied both the optimization error and the approximation error of this method.In the second part of the thesis, we studied the theoretical guarantees for contextual bandit problems using a Bayesian approach called Thompson Sampling. First, we explored the use of Variational Inference for Thompson Sampling algorithm. We notably showed that in the linear framework, this approach allows us to obtain the same theoretical guarantees as if we had access to the true posterior distribution. Finally, we consider a variant of Thompson Sampling called Feel-Good Thompson Sampling (FG-TS). This method allows to provide better theoretical guarantees than the classical algorithm. We then studied the use of a Monte Carlo Markov Chain method to approximate the posterior distribution. Specifically, we incorporated into FG-TS a Langevin Monte Carlo algorithm and a Metropolized Langevin Monte Carlo algorithm. Moreover, we obtained the same theoretical guarantees as for FG-TS when the posterior distribution is known

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.

The multi-armed bandit framework can be motivated by any problem where there is an abundance of choice and the utility of trying something new must be balanced with that of going with the status quo. This is a trade-off that is present in the everyday problem of where and what to eat: should I try a new restaurant or go to that Chinese place on the corner? In this work, a multi-armed bandit algorithm is presented which uses a non-parametric non-linear data model (a Gaussian process) to solve problems of this sort. The advantages of this method over existing work is highlighted through experiments. The method is also capable of modelling correlations between separate instances of problems, e.g., between similar dishes at similar restaurants. To demonstrate this, a few experiments are performed. The first, a synthetic example where the reward function is actually sampled from a Gaussian process, begs the question but helps pin down the properties of the algorithm in a controlled environment. The second, a problem where the objective is to aim a cannon at a distant target, shows how a well-defined objective, i.e., hit the target, can be used to speed up convergence. Finally, the third, an experiment with photographic post-processing, shows how the algorithm can learn from experience. The experiments demonstrate both the flexibility and the computational complexity of the model. This complexity means that problems such as the aforementioned restaurant problem, among others, are still future work.

Cette thèse s'inscrit dans le domaine de la prise de décision séquentielle en environnement inconnu, et plus particulièrement dans le cadre des bandits manchots (multi-armed bandits, MAB), défini par Robbins et Lai dans les années 50. Depuis les années 2000, ce cadre a fait l'objet de nombreuses recherches théoriques et algorithmiques centrées sur le compromis entre l'exploration et l'exploitation : L'exploitation consiste à répéter le plus souvent possible les choix qui se sont avérés les meilleurs jusqu'à présent. L'exploration consiste à essayer des choix qui ont rarement été essayés, pour vérifier qu'on a bien identifié les meilleurs choix. Les applications des approches MAB vont du choix des traitements médicaux à la recommandation dans le contexte du commerce électronique, en passant par la recherche de politiques optimales de l'énergie. Les contributions présentées dans ce manuscrit s'intéressent au compromis exploration vs exploitation sous deux angles spécifiques. Le premier concerne la prise en compte du risque. Toute exploration dans un contexte inconnu peut en effet aboutir à des conséquences indésirables ; par exemple l'exploration des comportements d'un robot peut aboutir à des dommages pour le robot ou pour son environnement. Dans ce contexte, l'objectif est d'obtenir un compromis entre exploration, exploitation, et prise de risque (EER). Plusieurs algorithmes originaux sont proposés dans le cadre du compromis EER. Sous des hypothèses fortes, l'algorithme MIN offre des garanties de regret logarithmique, à l'état de l'art ; il offre également une grande robustesse, contrastant avec la forte sensibilité aux valeurs des hyper-paramètres de e.g. (Auer et al. 2002). L'algorithme MARAB s'intéresse à un critère inspiré de la littérature économique(Conditional Value at Risk), et montre d'excellentes performances empiriques comparées à (Sani et al. 2012), mais sans garanties théoriques. Enfin, l'algorithme MARABOUT modifie l'estimation du critère CVaR pour obtenir des garanties théoriques, tout en obtenant un bon comportement empirique. Le second axe de recherche concerne le bandit contextuel, où l'on dispose d'informations additionnelles relatives au contexte de la décision ; par exemple, les variables d'état du patient dans un contexte médical ou de l'utilisateur dans un contexte de recommandation. L'étude se focalise sur le choix entre bras qu'on a tirés précédemment un nombre de fois différent. Le choix repose en général sur la notion d'optimisme, comparant les bornes supérieures des intervalles de confiance associés aux bras considérés. Une autre approche appelée BESA, reposant sur le sous-échantillonnage des valeurs tirées pour les bras les plus visités, et permettant ainsi de se ramener au cas où tous les bras ont été tirés un même nombre de fois, a été proposée par (Baransi et al. 2014)
This thesis focuses on sequential decision making in unknown environment, and more particularly on the Multi-Armed Bandit (MAB) setting, defined by Lai and Robbins in the 50s. During the last decade, many theoretical and algorithmic studies have been aimed at cthe exploration vs exploitation tradeoff at the core of MABs, where Exploitation is biased toward the best options visited so far while Exploration is biased toward options rarely visited, to enforce the discovery of the the true best choices. MAB applications range from medicine (the elicitation of the best prescriptions) to e-commerce (recommendations, advertisements) and optimal policies (e.g., in the energy domain). The contributions presented in this dissertation tackle the exploration vs exploitation dilemma under two angles. The first contribution is centered on risk avoidance. Exploration in unknown environments often has adverse effects: for instance exploratory trajectories of a robot can entail physical damages for the robot or its environment. We thus define the exploration vs exploitation vs safety (EES) tradeoff, and propose three new algorithms addressing the EES dilemma. Firstly and under strong assumptions, the MIN algorithm provides a robust behavior with guarantees of logarithmic regret, matching the state of the art with a high robustness w.r.t. hyper-parameter setting (as opposed to, e.g. UCB (Auer 2002)). Secondly, the MARAB algorithm aims at optimizing the cumulative 'Conditional Value at Risk' (CVar) rewards, originated from the economics domain, with excellent empirical performances compared to (Sani et al. 2012), though without any theoretical guarantees. Finally, the MARABOUT algorithm modifies the CVar estimation and yields both theoretical guarantees and a good empirical behavior. The second contribution concerns the contextual bandit setting, where additional informations are provided to support the decision making, such as the user details in the ontent recommendation domain, or the patient history in the medical domain. The study focuses on how to make a choice between two arms with different numbers of samples. Traditionally, a confidence region is derived for each arm based on the associated samples, and the 'Optimism in front of the unknown' principle implements the choice of the arm with maximal upper confidence bound. An alternative, pioneered by (Baransi et al. 2014), and called BESA, proceeds instead by subsampling without replacement the larger sample set. In this framework, we designed a contextual bandit algorithm based on sub-sampling without replacement, relaxing the (unrealistic) assumption that all arm reward distributions rely on the same parameter. The CL-BESA algorithm yields both theoretical guarantees of logarithmic regret and good empirical behavior

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

In sequential decision problems in unknown environments, decision makers often face dilemmas over whether to explore to discover more about the environment, or to exploit current knowledge. In this thesis, we address this exploration/exploitation dilemma in a general setting encompassing both standard and contextualised bandit problems, and also multi-agent (game-theoretic) problems. We consider an approach of Thompson (1933) which makes use of samples from the posterior distributions for the instantaneous value of each action. Our initial focus is on problems with a single decision maker acting. We extend the approach of Thompson (1933) by introducing a new algorithm, Optimistic Bayesian Sampling (OBS), in which the probability of playing an action increases with the uncertainty in the estimate of the action value. This results in better directed exploratory behaviour. We prove that, under unrestrictive assumptions, both approaches result in optimal behaviour with respect to the average reward criterion of Yang and Zhu(2002) . The problem has recently resurfaced in the context of contextual bandits for maximising revenue in sponsored web search advertising. We implement OBS and test its performance in several simulated domains. We find that it performs consistently better than numerous competitor methods. Our second focus is that of extending the method of Thompson (1933) to problems with more than one decision maker acting, and individual rewards depending on actions of others. Each agent must predict the actions of others to maximise reward. We consider combining Thompson sampling with fictitious play and establish conditions under which agents strategies converge to best responses to the empirical frequencies of opponent play, and also under which the belief process is a generalised weakened fictitious play process of Leslie and Collins (2006). Fictitious play is a deterministic algorithm, and so is not entirely consistent with the philosophy of Thompson sampling. We consider combining Thompson sampling with a randomised version of fictitious play that guarantees players play best responses to the empirical frequencies of opponent play. We also consider how the LTS and OBS algorithms can be extended to team games, where all agents receive the same reward. We suggest a novel method of achieving 'perfect coordination', in the sense that the multi-agent problem is effectively reduced to a single-agent problem.

Recent advances in deep neural networks (DNNs) have substantially improved the accuracy of intelligent applications. However, the pursuit of a higher accuracy has led to an increase in the complexity of DNNs, which inevitably increases the inference latency. For many time-sensitive mobile inferences, such a delay is intolerable and could be fatal in many real-world applications. To solve this problem, one effective scheme known as DNN partition is proposed, which significantly improves the inference latency by partitioning the DNN to a mobile device and an edge server to jointly process the inference. This approach utilises the stronger computing capacity of the edge while reducing the data transmission. Nevertheless, this approach requires a reliable network connection, which is oftentimes unstable. Therefore, DNN partition is vulnerable in the presence of service outages. In this thesis, we are motivated to investigate how to maintain the quality of the service during service outages to avoid interruptions. Inspired by the recently developed early exit technique, we propose three solutions: (1) When the service outage time is predictable, we propose eDeepSave to decide which frames to process during the service outage. (2) When the service outage time is not predictable but relatively short, we design LEE to effectively learn the optimal exit point in a per-instance manner. (3) When the service outage time is not predictable and relatively long, we present the DEE scheme to learn the optimal action (to exit or not) at each exit point, so that the system can dynamically exit the inference by utilising the observed environmental information. For each scheme, we provide detailed mathematical proofs of the performance and then test their performance in real-world experiments as well as the extensive simulations. The results of the three schemes demonstrate their effectiveness in maintaining the service during the service outage under a variety of scenarios.

L'électricité se stockant difficilement à grande échelle, l'équilibre entre la production et la consommation doit être rigoureusement maintenu. Une gestion par anticipation de la demande se complexifie avec l'intégration au mix de production des énergies renouvelables intermittentes. Parallèlement, le déploiement des compteurs communicants permet d'envisager un pilotage dynamique de la consommation électrique. Plus concrètement, l'envoi de signaux - tels que des changements du prix de l'électricité – permettrait d'inciter les usagers à moduler leur consommation afin qu'elle s'ajuste au mieux à la production d'électricité. Les algorithmes choisissant ces signaux devront apprendre la réaction des consommateurs face aux envois tout en les optimisant (compromis exploration-exploitation). Notre approche, fondée sur la théorie des bandits, a permis de formaliser ce problème d'apprentissage séquentiel et de proposer un premier algorithme pour piloter la demande électrique d'une population homogène de consommateurs. Une borne supérieure d'ordre T⅔ a été obtenue sur le regret de cet algorithme. Des expériences réalisées sur des données de consommation de foyers soumis à des changements dynamiques du prix de l'électricité illustrent ce résultat théorique. Un jeu de données en « information complète » étant nécessaire pour tester un algorithme de bandits, un simulateur de données de consommation fondé sur les auto-encodeurs variationnels a ensuite été construit. Afin de s'affranchir de l'hypothèse d'homogénéité de la population, une approche pour segmenter les foyers en fonction de leurs habitudes de consommation est aussi proposée. Ces différents travaux sont finalement combinés pour proposer et tester des algorithmes de bandits pour un pilotage personnalisé de la consommation électrique
As electricity is hard to store, the balance between production and consumption must be strictly maintained. With the integration of intermittent renewable energies into the production mix, the management of the balance becomes complex. At the same time, the deployment of smart meters suggests demand response. More precisely, sending signals - such as changes in the price of electricity - would encourage users to modulate their consumption according to the production of electricity. The algorithms used to choose these signals have to learn consumer reactions and, in the same time, to optimize them (exploration-exploration trade-off). Our approach is based on bandit theory and formalizes this sequential learning problem. We propose a first algorithm to control the electrical demand of a homogeneous population of consumers and offer T⅔ upper bound on its regret. Experiments on a real data set in which price incentives were offered illustrate these theoretical results. As a “full information” dataset is required to test bandit algorithms, a consumption data generator based on variational autoencoders is built. In order to drop the assumption of the population homogeneity, we propose an approach to cluster households according to their consumption profile. These different works are finally combined to propose and test a bandit algorithm for personalized demand side management

Adaptive learning is a crucial part in intelligent tutoring systems. It provides students with appropriate tutoring interventions, based on students’ characteristics, status, and other related features, in order to optimize their learning outcomes. It is required to determine students’ knowledge level or learning progress, based on which it then uses proper techniques to choose the optimal interventions. In this dissertation work, I focus on these aspects related to the process in adaptive learning: student modeling, k-armed bandits, and contextual bandits. Student modeling. The main objective of student modeling is to develop cognitive models of students, including modeling content skills and knowledge about learning. In this work, we investigate the effect of prerequisite skill in predicting students’ knowledge in post skills, and we make use of the prerequisite performance in different student models. As a result, this makes them superior to traditional models. K-armed bandits. We apply k-armed bandit algorithms to personalize interventions for students, to optimize their learning outcomes. Due to the lack of diverse interventions and small difference of intervention effectiveness in educational experiments, we also propose a simple selection strategy, and compare it with several k-armed bandit algorithms. Contextual bandits. In contextual bandit problem, additional side information, also called context, can be used to determine which action to select. First, we construct a feature evaluation mechanism, which determines which feature to be combined with bandits. Second, we propose a new decision tree algorithm, which is capable of detecting aptitude treatment effect for students. Third, with combined bandits with the decision tree, we apply the contextual bandits to make personalization in two different types of data, simulated data and real experimental data.

Dans cette thèse, nous étudions d'abord le problème de l'optimisation d'ordre zéro dans le cadre actif pour des fonctions lisses et trois classes différentes de fonctions : i) les fonctions qui satisfont la condition de Polyak-Łojasiewicz, ii) les fonctions fortement convexes, et iii) la classe plus large des fonctions non convexes fortement lisses.De plus, nous proposons un nouvel algorithme basé sur la randomisation de type l1, et nous étudions ses propriétés pour les fonctions convexes Lipschitz dans un cadre d'optimisation en ligne. Notre analyse est due à la dérivation d'une nouvelle inégalité de type Poincar'e pour la mesure uniforme sur la sphère l1 avec des constantes explicites.Ensuite, nous étudions le problème d'optimisation d'ordre zéro dans les schémas passifs. Nous proposons une nouvelle méthode pour estimer le minimiseur et la valeur minimale d'une fonction de régression lisse et fortement convexe f. Nous dérivons des limites supérieures pour cet algorithme et prouvons des limites inférieures minimax pour un tel cadre.Enfin, nous étudions le problème du bandit contextuel linéaire sous contraintes d'équité où un agent doit sélectionner un candidat dans un pool, et où chaque candidat appartient à un groupe sensible. Nous proposons une nouvelle notion d'équité qui est pratique dans l'exemple susmentionné. Nous concevons une politique avide qui calcule une estimation du rang relatif de chaque candidat en utilisant la fonction de distribution cumulative empirique, et nous prouvons sa propriété optimale
In this thesis, we first study the problem of zero-order optimization in the active setting for smooth and three different classes of functions: i) the functions that satisfy the Polyak-Łojasiewicz condition, ii) strongly convex functions, and iii) the larger class of highly smooth non-convex functions.Furthermore, we propose a novel algorithm that is based on l1-type randomization, and we study its properties for Lipschitz convex functions in an online optimization setting. Our analysis is due to deriving a new Poincar'e type inequality for the uniform measure on the l1-sphere with explicit constants.Then, we study the zero-order optimization problem in the passive schemes. We propose a new method for estimating the minimizer and the minimum value of a smooth and strongly convex regression function f. We derive upper bounds for this algorithm and prove minimax lower bounds for such a setting.In the end, we study the linear contextual bandit problem under fairness constraints where an agent has to select one candidate from a pool, and each candidate belongs to a sensitive group. We propose a novel notion of fairness which is practical in the aforementioned example. We design a greedy policy that computes an estimate of the relative rank of each candidate using the empirical cumulative distribution function, and we proved its optimal property

Les algorithmes de bandits-manchots pour les systèmes de recommandation sensibles au contexte font aujourd’hui l’objet de nombreuses études. Afin de répondre aux enjeux de cette thématique, les contributions de cette thèse sont organisées autour de 3 axes : 1) les systèmes de recommandation ; 2) les algorithmes de bandits-manchots (contextuels et non contextuels) ; 3) le contexte. La première partie de nos contributions a porté sur les algorithmes de bandits-manchots pour la recommandation. Elle aborde la diversification des recommandations visant à améliorer la précision individuelle. La seconde partie a porté sur la capture de contexte, le raisonnement contextuel pour les systèmes de recommandation d’événements culturels dans la ville intelligente, et l’enrichissement dynamique de contexte pour les algorithmes de bandits-manchots contextuels
Nowadays, Multi-Armed Bandit algorithms for context-aware recommendation systems are extensively studied. In order to meet challenges underlying this field of research, our works and contributions have been organised according to three research directions : 1) recommendation systems ; 2) Multi-Armed Bandit (MAB) and Contextual Multi-Armed Bandit algorithms (CMAB) ; 3) context.The first part of our contributions focuses on MAB and CMAB algorithms for recommendation. It particularly addresses diversification of recommendations for improving individual accuracy. The second part is focused on contextacquisition, on context reasoning for cultural events recommendation systems for Smart Cities, and on dynamic context enrichment for CMAB algorithms

Machine learning (ML) has become one of the most powerful classes of tools for artificial intelligence, personalized web services and data science problems across fields. Within the field of machine learning itself, there had been quite a number of paradigm shifts caused by the explosion of data size, computing power, modeling tools, and the new ways people collect, share, and make use of data sets. Data privacy, for instance, was much less of a problem before the availability of personal information online that could be used to identify users in anonymized data sets. Images, videos, as well as observations generated over a social networks, often have highly localized structures, that cannot be captured by standard nonparametric models. Moreover, the “common task framework” that is adopted by many sub- disciplines of AI has made it possible for many people to collaboratively and repeated work on the same data set, leading to implicit overfitting on public benchmarks. In addition, data collected in many internet services, e.g., web search and targeted ads, are not iid, but rather feedbacks specific to the deployed algorithm. This thesis presents technical contributions under a number of new mathematical frameworks that are designed to partially address these new paradigms. • Firstly, we consider the problem of statistical learning with privacy constraints. Under Vapnik’s general learning setting and the formalism of differential privacy (DP), we establish simple conditions that characterizes the private learnability, which reveals a mixture of positive and negative insight. We then identify generic methods that reuses existing randomness to effectively solve private learning in practice; and discuss weaker notions of privacy that allows for more favorable privacy-utility tradeoff. • Secondly, we develop a few generalizations of trend filtering, a locally-adaptive nonparametric regression technique that is minimax in 1D, to the multivariate setting and to graphs. We also study specific instances of the problems, e.g., total variation denoising on d-dimensional grids more closely and the results reveal interesting statistical computational trade-offs. • Thirdly, we investigate two problems in sequential interactive learning: a) off- policy evaluation in contextual bandits, that aims to use data collected from one algorithm to evaluate the performance of a different algorithm; b) the problem of adaptive data analysis, that uses randomization to prevent adversarial data analysts from a form of “p-hacking” through multiple steps of sequential data access. In the above problems, we will provide not only performance guarantees of algorithms but also certain notions of optimality. Whenever applicable, careful empirical studies on synthetic and real data are also included.

Les systèmes de communications sans fil ne cessent de se multiplier pour devenir incontournables de nos jours. Cette croissance cause une augmentation de la demande des ressources spectrales, qui sont devenues de plus en plus rares. Afin de résoudre ce problème de pénurie de fréquences, Joseph Mitola III, en 2000, a introduit l'idée de l'allocation dynamique du spectre. Il définit ainsi le terme " Cognitive Radio " (Radio Intelligente), qui est largement pressenti pour être le prochain Big Bang dans les futures communications sans fil [1]. Dans le cadre de ce travail on s'intéresse à la problématique du spectrum sensing qui est la détection de présence des Utilisateurs Primaires dans un spectre sous licence, dans le contexte de la radio intelligente. L'objectif de ce travail est de proposer des méthodes de détection efficaces à faible complexité et/ou à faible temps d'observation et ceci en utilisant le minimum d'information a priori sur le signal à détecter. Dans la première partie on traite le problème de détection d'un signal aléatoire dans le bruit. Deux grandes méthodes de détection sont utilisées : la détection d'énergie ou radiomètre et la détection cyclostationnaire. Dans notre contexte, ces méthodes sont plus complémentaires que concurrentes. Nous proposons une architecture hybride de détection des bandes libres, qui combine la simplicité du radiomètre et la robustesse des détecteurs cyclostationnaires. Deux méthodes de détection sont proposées qui se basent sur cette même architecture. Grâce au caractère adaptatif de l'architecture, la détection évolue au cours du temps pour tendre vers la complexité du détecteur d'énergie avec des performances proches du détecteur cyclostationnaire ou du radiomètre selon la méthode utilisée et l'environnement de travail. Dans un second temps on exploite la propriété parcimonieuse de la Fonction d'Autocorrelation Cyclique (FAC) pour proposer un nouvel estimateur aveugle qui se base sur le compressed sensing afin d'estimer le Vecteur d'Autocorrelation Cyclique (VAC), qui est un vecteur particulier de la Fonction d'Autocorrelation Cyclique pour un délai fixe. On montre par simulation que ce nouvel estimateur donne de meilleures performances que celles obtenues avec l'estimateur classique, qui est non aveugle et ceci dans les mêmes conditions et en utilisant le même nombre d'échantillons. On utilise l'estimateur proposé, pour proposer deux détecteurs aveugles utilisant moins d'échantillons que nécessite le détecteur temporel de second ordre de [2] qui se base sur l'estimateur classique de la FAC. Le premier détecteur exploite uniquement la propriété de parcimonie du VAC tandis que le second détecteur exploite en plus de la parcimonie la propriété de symétrie du VAC, lui permettant ainsi d'obtenir de meilleures performances. Ces deux détecteurs outre qu'ils sont aveugles sont plus performants que le détecteur non aveugle de [2] dans le cas d'un faible nombre d'échantillons.

Cette recherche doctorale se propose de discuter des modalités de construction et d’observation des modes de consommation culturelle pluriels à partir du cas de la bande dessinée. La revue de littérature de cette thèse met en évidence l’importance de rendre compte à la fois de la dimension multi-située(synchronique) et temporelle (diachronique) des pratiques culturelles observées. La perspective dispositionnaliste et contextualiste développée par Bernard Lahire (2005, 2013) semble répondre à cette exigence. En effet, les pratiques culturelles observées n’y sont jamais déconnectées des cadres qui participent à leur construction ni de ceux qui permettent leur observation en contextes. Pour rendre compte de cette double dimension des pratiques culturelles, ce travail s’appuie sur la réalisation de six portraits sociologiques (Lahire, 2005). Ces derniers permettent non seulement d’identifier la variété des cadres à l’origine de la construction des modes de consommation observés, mais également de rendre compte de la variété de leurs effets à l’échelle individuelle : les dispositions
This doctoral research aims to discuss the construction and observation of plural cultural consumption patterns based on the case of comics. The literature review seems to highlight the importance of reporting both the present (synchronic) and temporal (diachronic) dimensions of the cultural practices observed. Lahire's (2005, 2013) dispositionalist and contextualist perspective seems to be a response to this requirement. Indeed, the cultural practices observed are never disconnected from the frameworks that participate in their construction or from those that allow them to be observed in contexts. To reflect this dual dimension of cultural practices, this work is based on the production of six sociological portraits (Lahire, 2005). They allow not only to identify the variety of frameworks behind the construction of observed consumption patterns, but also to describe the variety of their effects at the individual level: the dispositions

L'allocation des ressources spectrales à des services de communications sans fil, sans cesse plus nombreux et plus gourmands, a récemment mené la communauté radio à vouloir remettre en question la stratégie de répartition des bandes de fréquences imposée depuis plus d'un siècle. En effet une étude rendue publique en 2002 par la commission fédérale des communications aux Etats-Unis (Federal Communications Commission - FCC) mit en évidence une pénurie des ressources spectrales dans une large bande de fréquences comprise entre quelques mégahertz à plusieurs gigahertz. Cependant, cette même étude expliqua cette pénurie par une allocation statique des ressources aux différents services demandeurs plutôt que par une saturation des bandes de fréquences. Cette explication fut par la suite corroborée par de nombreuses mesures d'occupation spectrale, réalisées dans plusieurs pays, qui montrèrent une forte sous-utilisation des bandes de fréquences en fonction du temps et de l'espace, représentant par conséquent autant d'opportunité spectrale inexploitée. Ces constations donnèrent naissance à un domaine en plein effervescence connu sous le nom d'Accès Opportuniste au Spectre (Opportunistic Spectrum Access). Nos travaux suggèrent l'étude de mécanismes d'apprentissage pour la radio intelligente (Cognitive Radio) dans le cadre de l'Accès Opportuniste au Spectre (AOS) afin de permettre à des équipements radio d'exploiter ces opportunités de manière autonome. Pour cela, nous montrons que les problématiques d'AOS peuvent être fidèlement représentées par des modèles d'apprentissage par renforcement. Ainsi, l'équipement radio est modélisé par un agent intelligent capable d'interagir avec son environnement afin d'en collecter des informations. Ces dernières servent à reconnaître, au fur et à mesure des expériences, les meilleurs choix (bandes de fréquences, configurations, etc.) qui s'offrent au système de communication. Nous nous intéressons au modèle particulier des bandits manchots (Multi-Armed Bandit appliqué à l'AOS). Nous discutons, lors d'une phase préliminaire, différentes solutions empruntées au domaine de l'apprentissage machine (Machine Learning). Ensuite, nous élargissons ces résultats à des cadres adaptés à la radio intelligente. Notamment, nous évaluons les performances de ces algorithmes dans le cas de réseaux d'équipements qui collaborent en prenant en compte, dans le modèle suggéré, les erreurs d'observations. On montre de plus que ces algorithmes n'ont pas besoin de connaître la fréquence des erreurs d'observation afin de converger. La vitesse de convergence dépend néanmoins de ces fréquences. Dans un second temps nous concevons un nouvel algorithme d'apprentissage destiné à répondre à des problèmes d'exploitation des ressources spectrales dans des conditions dites de fading. Tous ces travaux présupposent néanmoins la capacité de l'équipement intelligent à détecter efficacement l'activité d'autres utilisateurs sur la bande (utilisateurs prioritaires dits utilisateurs primaires). La principale difficulté réside dans le fait que l'équipement intelligent ne suppose aucune connaissance a priori sur son environnement (niveau du bruit notamment) ou sur les utilisateurs primaires. Afin de lever le doute sur l'efficacité de l'approche suggérée, nous analysons l'impact de ces incertitudes sur le détecteur d'énergie. Ce dernier prend donc le rôle d'observateur et envoie ses observations aux algorithmes d'apprentissage. Nous montrons ainsi qu'il est possible de quantifier les performances de ce détecteur dans des conditions d'incertitude sur le niveau du bruit ce qui le rend utilisable dans le contexte de la radio intelligente. Par conséquent, les algorithmes d'apprentissage utilisés pourront exploiter les résultats du détecteur malgré l'incertitude inhérente liée à l'environnement considéré et aux hypothèses (sévères) d'incertitude liées au problème analysé.

Cette thèse traite de l’aspect radio sur fibre dans le contexte du réseau d’accès et du réseau privatif. Elle nous a permis de comprendre les problèmes liés à une transmission radio sur fibre. Par la suite, nous avons réalisé des bilans de liaison radio sur fibre pour les systèmes suivant UMTS, WiMAX WiFi et UWB afin d’avoir une première idée sur les architectures réalisables. Puis nous avons réalisé et validé les modèles équivalents en bande de base des équipements optiques pour une transmission radio sur fibre. Ces modèles permettront d’ajuster et d’optimiser les signaux radio en tenant compte de la dégradation du signal lié à l’optique. Enfin, nous avons proposé des architectures radio sur fibre innovantes qui permettent de mutualiser les infrastructures d’accès optiques.

Une recherche DBR comprenant la conception et la mise en oeuvre d'une séquence de 10 leçons (combinant la physique et la création de BD) et visant à atteindre les objectifs d'apprentissage de la physique, a fourni le corpus de données, à savoir la production de BD par les élèves, dans une classe d'école secondaire. La théorie sémiotique appliquée au langage visuel des images séquentielles a fourni les outils qui ont permis de relier les signes sur les BD aux processus d'apprentissage et principalement les modes de raisonnement des élèves et leurs caractéristiques
A design-based research comprising the design and implementation of a sequence of 10 lessons (combining physics and comics-making) and aiming at the attainment of physics learning objectives, provided the data corpus, namely the students' comics production, in a secondary school class. Semiotic theory applied to the visual language of sequential images provided the analytical tools that linked the signs in the comics to processes of learning and primarily to the students' modes of reasoning and their characteristics

Cette thèse traite de l'aspect radio sur fibre dans le contexte du réseau d'accès et du réseau privatif. Elle nous a permis de comprendre les problèmes liés à une transmission radio sur fibre. Par la suite, nous avons réalisé des bilans de liaison radio sur fibre pour les systèmes suivant UMTS, WiMAX WiFi et UWB afin d'avoir une première idée sur les architectures réalisables. Puis nous avons réalisé et validé les modèles équivalents en bande de base des équipements optiques pour une transmission radio sur fibre. Ces modèles permettront d'ajuster et d'optimiser les signaux radio en tenant compte de la dégradation du signal lié à l'optique. Enfin, nous avons proposé des architectures radio sur fibre innovantes qui permettent de mutualiser les infrastructures d'accès optiques.

Cette thèse porte sur l’étude de systèmes ultra large bande (UWB) qui présentent des perspectives intéressantes dans le domaine des communications radio. Les systèmes UWB se prêtent bien à une utilisation dans les réseaux ad hoc, de type Piconet, avec un très haut niveau de flexibilité. Cette thèse focalise d’une part sur le développement de méthodes a faible complexité pour l’estimation aveugle de paramètres, pouvant jouer un rôle très important au niveau synchronisation, et d’autre part sur l’étude statistique du canal dans le but d’établir des critères de réglages en temps réel d'une transmission de données (dans une approche aveugle). Les travaux se positionnent suivant trois directions principales. La première concerne l’estimation du temps chip pour un système UWB par impulsions, a partir de mesures de temps d’arrivée bruitées, en présence d’observations manquantes et/ou issues de fausses alarmes. Le principal problème de cette première approche est que le modèle des temps d’arrivée est idéalisé et ne peut pas refléter de manière réaliste le canal UWB indoor. Pour cette raison nous avons propose une deuxième approche complémentaire, permettant de réaliser la détection conjointe du temps chip d’un signal UWB par impulsions, et de la période d’intégration d’un détecteur d’énergie. La différence essentielle entre cette approche et la précédente est que l’on utilise, pour l’estimation du temps chip, directement le signal reçu ce qui du point de vue pratique est plus réaliste. La troisième orientation concerne la réalisation d’une étude statistique de l’interférence liée à la propagation multi-trajet d’un canal U
This thesis is concerned with the study of UWB systems which represent a promising perspective in low range radio systems field. UWB technology is best suited to be used within ad-hoc Piconet radio networks, which must dispose of high flexibility. Consequently this thesis is focused on one hand on the development of very low complexity parameters blind estimation methods, which can play an essential role in the synchronization stage, and on the other hand on the statistical characterization of the propagation channel, with the scope of establishing criteria to realize blind real time adjustments of the digital transmission. The study is organized in three main directions. The first consists of developing a method to estimate the chip time, based on noisy times of arrival measurements, with false and missing observations. The main problem with this approach is that the considered times of arrival statistical model cannot realistically reflect indoor UWB channels. Therefore a second direction is concerned with the development of a method to estimate the chip time based on energy measurements on the received UWB impulse radio signal. Using the well known energy detector principle this approach jointly estimates the chip time and this optimal integration window, the main advantage is that it allows considering propagation noise, multipath propagation and multiuser interference. The third direction deals with a statistical study of the multipath propagation interference of a UWB propagation channel

L'Ultra Wide Band (UWB) est une technique de communication radio à haut débit et courte portée qui utilise des bandes de fréquence de 500 MHz à plusieurs GHz. Cette thèse présente une caractérisation expérimentale du canal de propagation UWB afin de proposer des modèles pour le développement de ces systèmes.
Les deux techniques de sondage proposées permettent la mesure du canal statique dans la bande 3,1 – 11,1 GHz et le sondage en temps réel dans la bande 4 – 5 GHz. Plusieurs campagnes de mesure réalisées en environnement intérieur de bureau sont détaillées. Leur analyse permet de dégager les paramètres grande échelle et les évanouissements rapides du canal statique, avec une étude particulière de l'influence de la fréquence. Des études spécifiques sont dédiées aux variations du canal UWB dues au mouvement des antennes et au passage de personnes. Un modèle statistique est proposé, permettant de reproduire les effets du canal de propagation UWB, en configurations statique et dynamique.

Dans ce travail de thèse, on a proposé une structure de génération des signaux multi-porteuse afin de créer plusieurs oscillateurs locaux (OL ) tout en utilisant qu’un modulateur I/Q. Ces signaux peuvent être utilisés dans les récepteurs de LTE-A pour la transposition des signaux agrégé en fréquence vers la bande de base. On développe la structure afin de l’utiliser en émetteur répondant aux normes du standard LTE-A. La nouvelle structure nous permet de générer n signaux agrégés en fréquences, de manière simultanée, par une seule chaîne de transmission (c.a.d un modulateur I/Q, un OL). En utilisant cette structure on réduit le nombre de circuits utilisés, en comparaison du cas où n signaux agrégés en fréquences sont générés par n émetteurs. La fréquence d’échantillonnage est réduite dans notre cas par rapport au cas où les signaux sont générés directement de la bande de base à la bande RF avec des convertisseurs analogiques numériques adéquats. Dans la troisième partie, on se concentre sur les imperfections et les non linéarités du modulateur I/Q dans le cadre de notre structure multibande. On modélise le fonctionnement du modulateur multi-bande en utilisant les échantillons en entrée et en sortie. Notre modèle est dérivé de la série de Volterra qui prends en compte les effets non linéaires et les effets mémoires ainsi que les imperfections du modulateur I/Q. Puis, on obtient la fonction "inverse" du modèle et on l’applique à l’entrée du modulateur afin de corriger et linéariser la sortie du modulateur I/Q. La fonction "inverse" est appelée DPD (en anglais : Digital Pre-Distortion). Enfin, on a évalué le modèle et la DPD en simulations et en mesures
In this dissertation, a signal generation structure is proposed using which a multitone Local Oscillator (LO) signal is created by a single I/Q modulator. These LOs can be used in the CA receivers to down-convert the transmitted component carriers simultaneously. The multi-tone LO signal structure is further developed to be used at the transmitter as a CA generation solution. Using the proposed structure n-component carriers can be generated in parallel. This structures requires lower sampling rates with respect to the case where RF signals are synthesized directly by digital-to- analog converters. Moreover, less circuitry is required, because one single I/Q modulator is used to generate n component carriers, instead of n I/Q modulators. This work follows on investigating the origin of impairments and mild nonlinearities in our I/Q modulator. To overcome these problems, we focus on the functionality of the overall system rather than each component of the I/Q modulator. This method is called behavioral modeling. Once the nonlinear model is obtained, if its inverse function is applied to the input, a linearized output is expected. The generation of the inverse function is called Digital Pre-Distortion (DPD). We propose a tri-band behavioral model for nonlinearities and impairments in tri-band CA using our I/Q modulator. Furthermore, the DPD of the model is evaluated in simulations and experiments

Depuis peu, le grand public manifeste un engouement pour des objets communicants qui requièrent le transfert rapide d'une quantité d'information sans cesse croissante. Dans ce contexte, l'un des challenges scientifiques repose sur la recherche de techniques de transmissions radio à très haut débit sur de courtes portées. Une technique possible est l'utilisation de signaux UWB, lesquels ont été autorisés en février 2002 par l'organisme américain de régulation des fréquences. Pour évaluer les performances des systèmes UWB, la modélisation du canal de propagation est indispensable. Ces modélisations sont généralement statistiques. L'objectif de la thèse a consisté à examiner l'apport de la modélisation déterministe pour l'étude du canal UWB. Les travaux présentés portent sur l'étude de l'impact des mécanismes de propagation sur les signaux UWB, sur la conception d'un outil de modélisation déterministe et sur la réalisation de campagnes de mesures pour l'évaluation de l'outil.

Lors du développement d'un nouvel avion, la phase précédant l'obtention du certificat de navigabilité est basée sur de nombreux essais au sol ou en vol. L'une des formes d'essai les plus délicates est la mesure de la pression de l'air autour de l'aile. Ces mesures permettent à la fois d'évaluer les deux composantes fondamentales de l'aérodynamisme que sont la portance et la trainée, de valider les résultats de simulation, et d'améliorer les données d'entrée des souffleries virtuelles pour les futurs développements. Dans le domaine spatial, le lancement est l'une des phases les plus critiques pour les systèmes. En effet, les structures doivent faire face à un stress mécanique et à des vibrations importantes qui ne doivent endommager ni le satellite ni les instruments embarqués. Des essais sol particulièrement rigoureux sont donc réalisés préalablement au lancement afin de vérifier que la charge utile ne sera pas endommagée. Des milliers de capteurs de pression ou de jauges de contrainte sont utilisés par les industriels du secteur pour ce type d'essais. Tous ces éléments sont aujourd'hui connectés entre eux par des fils. La première difficulté liée à cette forme d'installation est le poids supplémentaire imposé à la structure. Ce poids représentant une préoccupation importante en aéronautique, il est très délicat d'alourdir l'avion en ajoutant, le temps de l'essai, une quantité importante de câbles sur l'aile dans le seul but de connecter des capteurs entre eux. D'autres contraintes sont également associées au déploiement de ces réseaux de capteurs. La mise en place ces systèmes de mesure filaire engendre en effet un cout important, tant en raison du prix des câbles que de la très longue immobilisation de l'appareil nécessaire à l'installation du système. Cette dernière contrainte financière, très lourde, est de plus en plus difficile à supporter pour les industriels. Le remplacement des réseaux de mesure classiques par des réseaux de capteurs sans fil est une solution évidente aux différents problèmes soulevés. Cela permettrait également d'augmenter le nombre de points de mesure. Malgré le grand intérêt porté à la question des réseaux de capteur sans fil, les verrous technologiques sont encore très nombreux et il n'existe aujourd'hui aucun protocole permettant de répondre aux attentes et besoins des professionnels de l'aéronautique. Les protocoles classiques comme ZigBee ou Bluetooth ne permettent en effet d'atteindre, ni le débit nécessaire (plus de 100Mbits/s) ni le nombre de nœuds du réseau (plus de 800). Les travaux présentés dans cette thèse ont ainsi vocation à répondre aux besoins d'un canal de communication très haut débit, basse consommation, à faible puissance d'émission, fiable et autorisant un grand nombre de nœuds. Des mesures en conditions réelles effectuées à l'aide de circuits commerciaux reposant sur le protocole MB-OFDM/Wimedia, le standard le plus approchant du besoin exprimé, ont servi à la définition des bases de l'étude et ont permis de choisir des pistes de développement. Les mesures effectuées ayant démontré la spécificité de l'environnement de propagation, et n'ayant pas permis de définir un modèle de propagation suffisamment fiable, il est apparu nécessaire de recourir à un flot de conception utilisant des outils de synthèse de code automatique. Ce mode de développement, relativement original dans un contexte de recherche, a permis d'identifier précisément les besoins matériels nécessaires à la conception du démonstrateur, et de réduire considérablement le délai entre le choix des algorithmes et leurs tests en conditions réelles. La couche physique développée est basée sur un système OFDM ultra large bande permettant d'atteindre un débit de plus de 150 Mbits/s. Un démonstrateur parfaitement fonctionnel, implémenté sur FPGA et composé de quatre nœuds communicants a été réalisé et a permis de valider la couche physique. Enfin sont présentées des pistes pour le développement d'un ASIC numérique permettant d'atteindre l'objectif de faible consommation.

碩士
國立臺灣大學
資訊工程學研究所
101
The contextual bandit problem is usually used to model online applications like article recommendation. Somehow the problem cannot fully meet some needs of these applica- tions, such as making multiple actions at the same time. We propose a new Contextual Bandit Problem with Multiple Ac- tions (CBMA), which is an extension of the traditional con- textual bandit problem and fits the online applications better. We adapt some existing contextual bandit algorithms for our CBMA problem, and propose a new Pairwise Regression with Upper Confidence Bound (PairUCB) algorithm which utilizes the new properties of the CBMA problem, The experiment re- sults demostrate that PairUCB outperforms other algorithms.

碩士
國立臺灣大學
資訊工程學研究所
101
We study the contextual bandit problem that arises in many real world applications such as advertising, recommendations, and otherWeb applications. One leading algorithm for contextual bandit is the linear upper confidence bound (LINUCB) approach, which is based on updating internal linear regression models with the partial feedback from the environment. Because of updating with only the partial feedback, LINUCB can be slow in converging to the optimal performance. In this work, we study techniques that improve LINUCB by updating the linear regressionmodels with some additional feedback called the pseudo-reward. By choosing a proper pseudo-reward formula and implementing a forgetting mechanism to avoid being overly biased by the pseudo-rewards, we propose an improved algorithm that matches the regret guarantee of LINUCB in theory. Furthermore, we design a variant of the proposed algorithm that can be significantly more efficient than LINUCB during action selection, which directly implies faster response time in many applications. Extensive experimental results from both artificial data and the benchmark Yahoo! News recommendation data show that the proposed algorithm enjoys better performance than LINUCB and other contextual bandit algorithms.

碩士
國立中山大學
資訊管理學系研究所
104
The Contextual Bandit Problem (CMAB) is usually used to recommend for online applications on article, music, movie, etc. One leading algorithm for contextual bandit is the LinUCB algorithm, which updates internal linear regression models by the partial feedback from the environment. However, we observe that CMAB is rarely used in the stock recommendation, while most of the recommendations are for the purpose of profit, and ignore investor’s features (risk tolerance, investment features, and the others). We propose a personalized recommendation system for stock by using contextual multi-armed bandit algorithm. We take investor’s investment records as user features, and recommend the “arm”, which is a type of stock, based on two kinds of analysis, the technical and fundamental analysis. To the chosen arm, we rank the stocks according to the similarity of the stock and the arm. Our experiment is base on an online investment dataset, and the result demonstrates that our method outperforms other algorithms. Our experiment dataset collects simulation investment on the online website, and the result demonstrates that our method outperforms other algorithms.

The elicitation and aggregation of preferences is often the key to making better decisions. Be it a perfume company wanting to relaunch their 5 most popular fragrances, a movie recommender system trying to rank the most favoured movies, or a pharmaceutical company testing the relative efficacies of a set of drugs, learning from preference feedback is a widely applicable problem to solve. One can model the sequential version of this problem using the classical multiarmed-bandit (MAB) (e.g., Auer, 2002) by representing each decision choice as one bandit-arm, or more appropriately as a Dueling-Bandit (DB) problem (Yue \& Joachims, 2009). Although DB is similar to MAB in that it is an online decision making framework, DB is different in that it specifically models learning from pairwise preferences. In practice, it is often much easier to elicit information, especially when humans are in the loop, through relative preferences: `Item A is better than item B' is easier to elicit than its absolute counterpart: `Item A is worth 7 and B is worth 4'. However, instead of pairwise preferences, a more general $k$-subset-wise preference model $(k \ge 2)$ is more relevant in various practical scenarios, e.g. recommender systems, search engines, crowd-sourcing, e-learning platforms, design of surveys, ranking in multiplayer games. Subset-wise preference elicitation is not only more budget friendly, but also flexible in conveying several types of feedback. For example, with subset-wise preferences, the learner could elicit the best item, a partial preference of the top 5 items, or even an entire rank ordering of a subset of items, whereas all these boil down to the same feedback over pairs (subsets of size 2). The problem of how to learn adaptively with subset-wise preferences, however, remains largely unexplored; this is primarily due to the computational burden of maintaining a combinatorially large, $O(n^k)$, size of preference information in general (for a decision problem with $n$ items and subsetsize $k$). We take a step in the above direction by proposing ``Battling Bandits (BB)''---a new online learning framework to learn a set of optimal ('good') items by sequentially, and adaptively, querying subsets of items of size up to $k$ ($k\ge 2$). The preference feedback from a subset is assumed to arise from an underlying parametric discrete choice model, such as the well-known Plackett-Luce model, or more generally any random utility (RUM) based model. It is this structure that we leverage to design efficient algorithms for various problems of interest, e.g. identifying the best item, set of top-k items, full ranking etc., for both in PAC and regret minimization setting. We propose computationally efficient and (near-) optimal algorithms for above objectives along with matching lower bound guarantees. Interestingly this leads us to finding answers to some basic questions about the value of subset-wise preferences: Does playing a general $k$-set really help in faster information aggregation, i.e. is there a tradeoff between subsetsize-$k$ vs the learning rate? Under what type of feedback models? How do the performance limits (performance lower bounds) vary over different combinations of feedback and choice models? And above all, what more can we achieve through BB where DB fails? We proceed to analyse the BB problem in the contextual scenario – this is relevant in settings where items have known attributes, and allows for potentially infinite decision spaces. This is more general and of practical interest than the finite-arm case, but, naturally, on the other hand more challenging. Moreover, none of the existing online learning algorithms extend straightforwardly to the continuous case, even for the most simple Dueling Bandit setup (i.e. when $k=2$). Towards this, we formulate the problem of ``Contextual Battling Bandits (C-BB)'' under utility based subsetwise-preference feedback, and design provably optimal algorithms for the regret minimization problem. Our regret bounds are also accompanied by matching lower bound guarantees showing optimality of our proposed methods. All our theoretical guarantees are corroborated with empirical evaluations. Lastly, it goes without saying, that there are still many open threads to explore based on BB. These include studying different choice-feedback model combinations, performance objectives, or even extending BB to other useful frameworks like assortment selection, revenue maximization, budget-constrained bandits etc. Towards the end we will also discuss some interesting combinations of the BB framework with other, well-known, problems, e.g. Sleeping / Rotting Bandits, Preference based Reinforcement Learning, Learning on Graphs, Preferential Bandit-Convex-Optimization etc.

Numerous optimization problems in production systems can be considered as decision-making processes that determine the best allocation of resources to tasks over time to optimize one or more objectives in concert with big data. Among the optimization problems, production scheduling and routing of robots for material handling are becoming more important due to their impacts on system performance. However, the development of efficient algorithms for scheduling or routing faces several challenges. While the scheduling and vehicle routing problems can be solved by mathematical models such as mixed-integer linear programming to find optimal solutions to smallsized problems, they are not applicable to larger problems due to the nature of NP-hard problems. Thus, further research on machine learning applications to those problems is a significant step towards increasing the possibilities and potentialities of field application. In order to create truly intelligent systems, new frameworks for scheduling and routing are proposed to utilize machine learning (ML) techniques. First, the dynamic single-machine scheduling problem for minimization of total weighted tardiness is addressed. In order to solve the problem more efficiently, a decisiontree-based approach called Generation of Rules Automatically with Feature construction and Treebased learning (GRAFT) is designed to extract dispatching rules from existing or good schedules. In addition to the single-machine scheduling problem, the flexible job-shop scheduling problem with release times for minimizing the total weighted tardiness is analyzed. As a ML-based solution approach, a random-forest-based approach called Random Forest for Obtaining Rules for Scheduling (RANFORS) is developed to solve the problem by generating dispatching rules automatically. Finally, an optimization problem for routing of autonomous robots for minimizing total tardiness of transportation requests is analyzed by decomposing it into three sub-problems. In order to solve the sub-problems, a comprehensive framework with consideration of conflicts between routes is proposed. Especially to the sub-problem for vehicle routing, a new local search algorithm called COntextual-Bandit-based Adaptive Local search with Tree-based regression (COBALT) that incorporates the contextual bandit into operator selection is developed. The findings from my research contribute to suggesting a guidance to practitioners for the applications of ML to scheduling and control problems, and ultimately to lead the implementation of smart factories.