Search

Last-minute maintenance planning is often undesirable, as it may cause downtime during operational hours, may require rescheduling of other activities, and does not allow to optimize the management of spare parts, material, and personnel. In spite of the aforementioned drawbacks of last-minute planning, most existing methods plan maintenance activities at the last minute. In this paper, we propose a new strategy for timely maintenance planning in multi-component systems. As a first step, we determine for each system component independently the most appropriate maintenance planning strategy. This way, the maintenance decisions can be tailored to the specific situations. For example, conservative maintenance decisions can be taken when the risk tolerance is low, and maintenance decisions can be made timely when we can accurately predict future degradation behavior. In the second step, we optimize the maintenance plan at the system level. Here, we account for economic and structural dependence with the aim to profit from spreading or combining various maintenance activities. The applicability of the method is demonstrated on a railway case. It is shown how the different cost functions (e.g. costs of maintenance, downtime, and failure) influence the maintenance decisions.

In this thesis, we propose a method to build a decision support tool for the diagnosis of rare diseases. We aim to minimize the number of medical tests necessary to achieve a state where the uncertainty regarding the patient's disease is less than a predetermined threshold. In doing so, we take into account the need in many medical applications, to avoid as much as possible, any misdiagnosis. To solve this optimization task, we investigate several reinforcement learning algorithm and make them operable in our high-dimensional. To do this, we break down the initial problem into several sub-problems and show that it is possible to take advantage of the intersections between these sub-tasks to accelerate the learning phase. The strategies learned are much more effective than classic greedy strategies. We also present a way to combine expert knowledge, expressed as conditional probabilities, with clinical data. This is crucial because the scarcity of data in the field of rare diseases prevents any approach based solely on clinical data. We show, both empirically and theoretically, that our proposed estimator is always more efficient than the best of the two models (expert or data) within a constant. Finally, we show that it is possible to effectively integrate reasoning taking into account the level of granularity of the symptoms reported while remaining within the probabilistic framework developed throughout this work.; Dans cette thèse, nous proposons une méthode pour construire un outil d'aide à la décision pour le diagnostic de maladie rare. Nous cherchons à minimiser le nombre de tests médicaux nécessaires pour atteindre un état où l'incertitude concernant la maladie du patient est inférieure à un seuil prédéterminé. Ce faisant, nous tenons compte de la nécessité dans de nombreuses applications médicales, d'éviter autant que possible, tout diagnostic erroné. Pour résoudre cette tâche d'optimisation, nous étudions plusieurs algorithmes d'apprentissage par renforcement et les rendons opérationnels pour notre problème de très grande dimension. Pour cela nous décomposons le problème initial sous la forme de plusieurs sous-problèmes et montrons qu'il est possible de tirer partie des intersections entre ces sous-tâches pour accélérer l'apprentissage. Les stratégies apprises se révèlent bien plus performantes que des stratégies gloutonnes classiques. Nous présentons également une façon de combiner les connaissances d'experts, exprimées sous forme de probabilités conditionnelles, avec des données cliniques. Il s'agit d'un aspect crucial car la rareté des données pour les maladies rares empêche toute approche basée uniquement sur des données cliniques. Nous montrons, tant théoriquement qu'empiriquement, que l'estimateur que nous proposons est toujours plus performant que le meilleur des deux modèles (expert ou données) à une constante près. Enfin nous montrons qu'il est possible d'intégrer efficacement des raisonnements tenant compte du niveau de granularité des symptômes renseignés tout en restant dans le cadre probabiliste développé tout au long de ce travail.

International audience; This paper addresses the question of sequential collective decision making under qualitative uncertainty. It resumes the criteria introduced in previous works [4], [5], [6] by Ben Amor et al. and extends them to a more general context where every decision maker is free to have an optimistic or a pessimistic attitude w.r.t. uncertainty. These criteria are then considered for the optimization of possibilistic decision trees and an algorithmic study is performed for each of them. When the global utility does satisfy the monotonicity property, a classical possibilistic Dynamic Programming can be applied. Otherwise, two cases are possible: either the criterion is max oriented (the more is the satisfaction of any agent, the greater is the global satisfaction), and a dedicated algorithm can be proposed, that relies on as many calls to Dynamic Programming as the number of decision makers; or the criterion is min oriented (all the agents must like the common decision) and the optimal strategy can be provided by a Branch and Bound Algorithm. The paper concludes by an experimental study that shows the feasibility of the approaches, and details to what extent simple Dynamic programming algorithms can be used as approximation procedures for the non monotonic criteria.

International audience; This paper addresses safe path planning problem in urban environments under onboard sensor availability uncertainty. In this context, an approach based on Mixed-Observability Markov Decision Process (MOMDP) is presented. Such a model enables the planner to deal with a priori probabilistic sensor availability and path execution error propagation, the which depends on the navigation solution. Due to modelling particularities of this safe path planning problem, such as bounded hidden and fully observable state variables, discrete actions and particular transition function form, the belief state update function becomes a complex step that cannot be ignored during planning. Recent advances in Partially Observable Markov Decision Process (POMDP) solving have proposed a planning algorithm called POMCP, which is based on Monte-Carlo Tree Search method. It allows the planner to work on the history of the action-observation pairs without the need to compute belief state updates. Thereby, this paper proposes to apply a POMCP-like algorithm to solve the addressed MOMDP safe path planning problem. The obtained results show the feasibility of the approach and the impact of considering different a priori probabilistic sensor availability on the result policy.

Established in 2015, the Emotion Imbued Choice (EIC; Lerner et al., 2015) explains how emotions influence decision making. According to this model, incidental emotions (not related to the decision) associated with a high degree of certainty would trigger a heuristic information processing (Tiedens & Linton, 2001). In contrast, incidental emotions associated with a high level of uncertainty would trigger a deliberative information processing. This would explain the difference in performance on decision-making task.The influence of incidental emotions has been studied in one-shot decision and sequential decision making (i.e., sequence of decisions). While the EIC provides a clear and powerful framework for one-shot decision, its predictions are less explicit for sequential decision making. The particularity of this type of decision is that each decision is followed by a feedback (gain or loss) with an emotional cue (positive vs. negative). This integral source (related to the decision) of emotional influence can modify the subsequent decisions. Researchers have observed that the initiation of a heuristic processing leads participants to make more advantageous decisions than the initiation of a deliberative ones (Bagneux et al., 2012; Bagneux et al., 2013; Bollon & Bagneux, 2013). However, the impact of the processing of the emotional cue associated with feedbacks in obtaining this pattern of result has not yet been directly confirmed.Our objective was to identify how incidental emotions, based on their degree of certainty, modulate sequential decision making. Through a series of seven experiments, we have shown how incidental emotions interact with integral influence of feedbacks. Only the initiation of a heuristic processing leads participants to modulate their decisions according to the type of feedbacks received (positive vs. negative). These results concern both risky and ambiguous sequential decision making. The modulation of decision making has been highlighted, in a classic way, when inducing incidental negative emotions and, in a more original way, when inducing incidental positive emotions. The analysis of the results and the literature reveal difficulties in terms of the reliability of the measurement of the degree of certainty. A series of six other studies, in the general methodology of scale construction, investigated the origin of these difficulties. We have shown that these difficulties are the double consequence of an incomplete definition and an imperfect operationalization of the certainty appraisal dimension. From a theoretical level, we propose that all of our results support the need to extend the EIC to sequential decision making. From a methodological level, our results justify the interest of developing a new tool to measure the degree of certainty., Développé en 2015, l’Emotion Imbued Choice (EIC ; Lerner et al., 2015) explique la manière dont les émotions influencent la prise de décision. Selon ce modèle, les émotions incidentes (non reliées à la décision) associées à un haut degré de certitude déclencheraient un traitement plutôt heuristique de l’information tandis que les émotions associées à un haut degré d’incertitude déclencheraient un traitement plutôt délibératif (Tiedens & Linton, 2001), expliquant des différences de performances dans les tâches de prise de décision.L’influence des émotions incidentes a été étudiée dans la prise de décision unique et dans la prise séquentielle de décisions (i.e., séries de décisions). Si l’EIC, fournit un cadre explicatif clair concernant la prise de décision unique, ses prédictions sont moins explicites quant à la prise séquentielle de décisions. Cette dernière présente la particularité que chaque décision est suivie d’un feedback (gain ou perte) ayant une valeur émotionnelle (positive vs. négative). Cette source d’influence émotionnelle intégrée (reliée à la décision) peut modifier les décisions suivantes. Des auteurs ont observé que le déclenchement d’un traitement de l’information plutôt heuristique conduit les participants à prendre des décisions plus avantageuses que le déclenchement d’un traitement de l’information plutôt délibératif (Bagneux et al. 2013 ; voir aussi Bollon & Bagneux, 2013). Toutefois, l’implication du traitement de la valeur émotionnelle des feedbacks dans l’obtention de ce pattern de résultats n’a, à ce jour, pas reçu de confirmation directe.Notre objectif était d’identifier la manière dont les émotions incidentes, en fonction de leur degré de certitude, modulent la prise séquentielle de décisions. Au travers d’une série de sept expériences, nous avons montré comment ces émotions incidentes interagissent avec l’influence émotionnelle intégrée des feedbacks. Ainsi, seul le déclenchement d’un traitement plutôt heuristique conduit les participants à moduler leurs décisions en fonction du type (positifs vs. négatifs) de feedbacks reçus. Ces résultats concernent les tâches de prise séquentielle de décisions ambigües et risquées. La modulation du pattern de prise de décision a été mise en évidence, de manière classique, lors de l’induction d’émotions incidentes négatives et, de manière plus originale, lors de l’induction d’émotions incidentes positives. En second lieu, l’analyse des résultats et de la littérature a mis en évidence la fiabilité médiocre de la mesure du degré de certitude. Une série de six autres études, s’inscrivant dans la méthodologie générale de construction d’échelles, a été réalisée afin d’en recherche les origines. Nous avons montré que cette faible fiabilité était la double conséquence d’une définition incomplète et d’une opérationnalisation imparfaite de la dimension de certitude. À un niveau théorique, nous proposons que l’ensemble de nos résultats supportent la nécessité d’étendre le modèle EIC à la prise séquentielle de décisions. Sur le plan méthodologique, nos résultats justifient l’intérêt de développer un nouvel outil de mesure du degré de certitude.

Research on escalation of commitment has predominantly been studied in the context of a single decision without consideration for the psychological consequences of escalating. This study sought to examine (a) the extent to which people escalate their commitment to a failing course of action in a sequential decision-making task, (b) confidence and anger as psychological consequences of escalation of commitment, and (c) the reciprocal relationship between escalation of commitment and confidence and anger. Participants were 110 undergraduate students who completed a series of investment decisions regarding a failing endeavor. Results revealed that although a high proportion of individuals escalate through all decisions, the extent to which they escalated decreased with each decision as they were less willing to invest money in the project. Furthermore, as participants escalated, confidence in one's decision decreased and anger increased. Lastly, the analyses revealed that the relationship between escalation and confidence is reciprocal. Escalation was negatively associated with confidence, and confidence predicted escalation in the subsequent decision. These results highlight the importance of considering both the determinants and psychological consequences of escalation of commitment.

We conduct a framed laboratory experiment to gain in-depth insights on factors that drive collective research and development efforts among firms located along the automotive value chain. In particular, we employ a public goods experiment and analyze the influence of sequential decision-making on the willingness to engage in cooperation and on economic welfare. By using a linear value chain setting with three suppliers and one OEM, we analyze vertical R&D cooperation. Our results reveal that contributions increase in situations with sequential decision-making and that sequential decisions increase the overall welfare, even in case of unequally distributed R&D budgets. Wir verwenden ein ökonomisches Laborexperiment um Einblicke in Faktoren zu gewinnen, welche die gemeinsame Forschungs- und Entwicklungsarbeit von Unternehmen entlang der Wertschöpfungskette in der Automobilindustrie vorantreiben. Dabei setzen wir ein 'öffentliches Gut Experiment' ein und analysieren den Einfluss sequentieller Entscheidungen auf die Kooperationsbereitschaft sowie die Wohlfahrt. Hierfür modellieren wir eine lineare Wertschöpfungskette mit drei Lieferanten und einem OEM und analysieren vertikale F&E-Kooperationen. Unsere Ergebnisse zeigen, dass die Beiträge zum gemeinsamen Forschungsprojekt bei sequentiellen Entscheidungen zunehmen und dass sequentielle Entscheidungen die Wohlfahrt erhöhen. Dies gilt auch bei ungleich verteilten F&E-Budgets.

When humans or animals perform an action that led to a desired outcome, they show a tendency to repeat it. The mechanisms underlying learning from past experience and adapting future behavior are still not fully understood. In this thesis, I study how humans learn from sparse and delayed reward during multi-step tasks. Learning a sequence of multiple decisions, from a reward obtained only at the end of the sequence, requires a mechanism to link earlier actions to later reward. The theory of reinforce- ment learning suggests an algorithmic solution to this problem, namely, to keep a decaying memory of the state-action history. Such memories are called eligibility traces. They bridge the temporal delay between the moment an action is taken and a subsequent reward. We ask whether humans make use of eligibility traces when learning a sequential decision making task. The difficulty in answering this question is that different competing algorithmic solu- tions make similar predictions about behavior. Only during a few initial trials, learning with eligibility traces is qualitatively different from other algorithms. Here, I implemented a novel learning task with an experimental manipulation that allowed us to guide participants through a controlled sequence of states. With this hidden manipulation, we were able to isolate the specific trials in which the competing models are distinguishable. Behavioral data as well as simultaneously recorded pupil dilation revealed effects compatible with eligibility traces, but not with simpler models. Furthermore, the trial-by-trial reward prediction errors were correlated with pupil dilation and EEG measurements. Our experimental data show effects of eligibility traces in behavior and pupil data, after a single experience of state-action associations, which has not been studied before in a multi-step task. We view our results in the light of one-shot learning and as a signature of a learning mechanism present both in temporal difference and one-shot learning.

International audience; Many of the decisions we make in our everyday lives are sequential and entail sparse rewards. While sequential decision-making has been extensively investigated in theory (e.g., by reinforcement learning models) there is no systematic experimental paradigm to test it. Here, we developed such a paradigm and investigated key components of reinforcement learning models: the eligibility trace (i.e., the memory trace of previous decision steps), the external reward, and the ability to exploit the statistics of the environment's structure (model-free vs. model-based mechanisms). We show that the eligibility trace decays not with sheer time, but rather with the number of discrete decision steps made by the participants. We further show that, unexpectedly, neither monetary rewards nor the environment's spatial regularity significantly modulate behavioral performance. Finally, we found that model-free learning algorithms describe human performance better than model-based algorithms.

IDs are probabilistic graphical models used to represent and solve decision problems under uncertainty.Interval-valued IDs allow to gain realism in the modeling and perform a sensitivity analysis in precise IDs.The variable elimination and arc reversal inference algorithms are generalized to evaluate interval-valued IDs.The experimental work shows a better accuracy of the new methods based on linear programming. Influence diagrams are probabilistic graphical models used to represent and solve sequential decision problems under uncertainty. Sharp numerical values are required to quantify probabilities and utilities. This might be an issue with real models, whose parameters are typically obtained from expert judgments or partially reliable data. We consider an interval-valued quantification of the parameters to gain realism in the modeling and evaluate the sensitivity of the inferences with respect to perturbations in the sharp values of the parameters. An extension of the classical influence diagrams formalism to support such interval-valued potentials is presented. The variable elimination and arc reversal inference algorithms are generalized to cope with these models. At the price of an outer approximation, the extension keeps the same complexity as with sharp values. Numerical experiments show improved performances with respect to previous methods. As a natural application, we propose these models for practical sensitivity analysis in traditional influence diagrams. The maximum perturbation level on single or multiple parameters preserving the optimal strategy can be computed. This allows the identification of the parameters deserving a more careful elicitation.

In many daily tasks, we make multiple decisions before reaching a goal. In order to learn such sequences of decisions, a mechanism to link earlier actions to later reward is necessary. Reinforcement learning (RL) theory suggests two classes of algorithms solving this credit assignment problem: In classic temporal-difference learning, earlier actions receive reward information only after multiple repetitions of the task, whereas models with eligibility traces reinforce entire sequences of actions from a single experience (one-shot). Here, we show one-shot learning of sequences. We developed a novel paradigm to directly observe which actions and states along a multi-step sequence are reinforced after a single reward. By focusing our analysis on those states for which RL with and without eligibility trace make qualitatively distinct predictions, we find direct behavioral (choice probability) and physiological (pupil dilation) signatures of reinforcement learning with eligibility trace across multiple sensory modalities.

Breast cancer is the most common carcinosis with the largest number of mortalities in women. Its therapy comprises a wide spectrum of different treatment modalities a breast oncologist decides about for the individual patient case. These decisions happen according to medical guide lines, current scientific publications and experiences acquired in former cases. Clinical decision making therefore involves the time-consuming search for possible therapy options and their thorough testing for applicability to the current patient case. This research work addresses breast cancer therapy planning as a multi-criteria sequential decision making problem. The approach is based on a data model for patient cases with therapy descriptions and a mathematical notion for therapeutic relevance of medical information. This formulation allows for a novel decision support concept, which targets at eliminating observed weaknesses in clinical routine of breast cancer therapy planning.

International audience; We analyze a sequential decision making process, in which at each step the decision is made in two stages. In the first stage a partially optimal action is chosen, which allows the decision maker to learn how to improve it under the new environment. We show how inertia (cost of changing) may lead the process to converge to a routine where no further changes are made. We illustrate our scheme with some economic models.

In this paper, we introduce models of sequential decision making in consumer lending. From the definition of adverse selection in static lending models, we show that homogenous borrowers take-up offers at different instances of time when faced with a sequence of loan offers. We postulate that bounded rationality and diverse decision heuristics used by consumers drive the decisions they make about credit offers. Under that postulate, we show how observation of early decisions in a sequence can be informative about later decisions and can, when coupled with a type of adverse selection, also inform credit risk. We show through two examples how lenders may use such information in setting their offer rates.

Aiding to make decisions as early as possible by learning from past experiences is becoming increasingly important in many application domains. In these settings , information can be gained by waiting for more evidences to arrive, thus helping to make better decisions that incur lower misclassification costs, but, meanwhile, the cost associated with delaying the decision generally increases, rendering the decision less attractive. Learning requires then to solve an optimization problem combining two types of competing costs. In the growing literature on online decision making , very few works have explicitly incorporated the cost of delay in the decision procedure. One recent work [DBC15] has introduced a general formalization of this optimization problem. However, the algorithm presented there to solve it is based on a clustering step, with all the attendant necessary choices of parameters that can heavily impact the results. In this paper, we adopt the same conceptual framework but we present a more direct technique involving only one parameter and lower computational demands. Extensive experimental comparisons between the two methods on synthetic and real data sets show the superiority of our method when the classification of the incomplete time series is difficult, which corresponds to a large fraction of the applications.

This thesis describes an evolutionary theory of depression and related Rumination hypothesis. This hypothesis suggests that depression can have a positive effect on cognition and can lead to an analytical style of thinking that is useful for problem solving. To confirm the hypothesis, this thesis is using tasks focused on sequential decision making called secretary's problem. Thus, the work examines the hypothesis that depressed respondents perform better in the task than healthy respondents. Partial results of the whole study analyzed in this thesis show that the hypothesis could not be confirmed, which the author justifies in the debate and confronts these findings with the results of similar research.

Multi-Armed Bandits (MAB) constitute the most fundamental model for sequential decision making problems with an exploration vs. exploitation trade-off. In such problems, the decision maker selects an arm in each round and observes a realization of the corresponding unknown reward distribution. Each decision is based on past decisions and observed rewards. The objective is to maximize the expected cumulative reward over some time horizon by balancing exploitation (arms with higher observed rewards should be selectedoften) and exploration (all arms should be explored to learn their average rewards). Equivalently, the performanceof a decision rule or algorithm can be measured through its expected regret, defined as the gap betweenthe expected reward achieved by the algorithm and that achieved by an oracle algorithm always selecting the bestarm. This thesis investigates stochastic and adversarial combinatorial MAB problems, where each arm is a collection of several basic actions taken from a set of $d$ elements, in a way that the set of arms has a certain combinatorial structure. Examples of such sets include the set of fixed-size subsets, matchings, spanning trees, paths, etc. These problems are specific forms of online linear optimization, where the decision space is a subset of $d$-dimensional hypercube.Due to the combinatorial nature, the number of arms generically grows exponentially with $d$. Hence, treating arms as independent and applying classical sequential arm selection policies would yield a prohibitive regret. It may then be crucial to exploit the combinatorial structure of the problem to design efficient arm selection algorithms.As the first contribution of this thesis, in Chapter 3 we investigate combinatorial MABs in the stochastic setting and with Bernoulli rewards. We derive asymptotic (i.e., when the time horizon grows large) lower bounds on the regret of any algorithm under bandit and semi-bandit feedback. The proposed lower bounds are problem-specific and tight in the sense that there exists an algorithm that achieves these regret bounds. Our derivation leverages some theoretical results in adaptive control of Markov chains. Under semi-bandit feedback, we further discuss the scaling of the proposed lower bound with the dimension of the underlying combinatorial structure. For the case of semi-bandit feedback, we propose ESCB, an algorithm that efficiently exploits the structure of the problem and provide a finite-time analysis of its regret. ESCB has better performance guarantees than existing algorithms, and significantly outperforms these algorithms in practice. In the fourth chapter, we consider stochastic combinatorial MAB problems where the underlying combinatorial structure is a matroid. Specializing the results of Chapter 3 to matroids, we provide explicit regret lower bounds for this class of problems. For the case of semi-bandit feedback, we propose KL-OSM, a computationally efficient greedy-based algorithm that exploits the matroid structure. Through a finite-time analysis, we prove that the regret upper bound of KL-OSM matches the proposed lower bound, thus making it the first asymptotically optimal algorithm for this class of problems. Numerical experiments validate that KL-OSM outperforms state-of-the-art algorithms in practice, as well.In the fifth chapter, we investigate the online shortest-path routing problem which is an instance of combinatorial MABs with geometric rewards. We consider and compare three different types of online routing policies, depending (i) on where routing decisions are taken (at the source or at each node), and (ii) on the received feedback (semi-bandit or bandit). For each case, we derive the asymptotic regret lower bound. These bounds help us to understand the performance improvements we can expect when (i) taking routing decisions at each hop rather than at the source only, and (ii) observing per-link delays rather than end-to-end path delays. In particular, we show that (i) is of no use while (ii) can have a spectacular impact.For source routing under semi-bandit feedback, we then propose two algorithms with a trade-off betweencomputational complexity and performance. The regret upper bounds of these algorithms improve over those ofthe existing algorithms, and they significantly outperform state-of-the-art algorithms in numerical experiments. Finally, we discuss combinatorial MABs in the adversarial setting and under bandit feedback. We concentrate on the case where arms have the same number of basic actions but are otherwise arbitrary. We propose CombEXP, an algorithm that has the same regret scaling as state-of-the-art algorithms. Furthermore, we show that CombEXP admits lower computational complexity for some combinatorial problems. QC 20160201

In agriculture Markov decision processes (MDPs) with finite state and action space are often used to model sequential decision making over time. For instance, states in the process represent possible levels of traits of the animal and transition probabilities are based on biological models estimated from data collected from the animal or herd. State space models (SSMs) are a general tool for modeling repeated measurements over time where the model parameters can evolve dynamically. In this paper we consider methods for embedding an SSM into an MDP with finite state and action space. Different ways of discretizing an SSM are discussed and methods for reducing the state space of the MDP are presented. An example from dairy production is given Udgivelsesdato: First online 4. February In agriculture Markov decision processes (MDPs) with finite state and action space are often used to model sequential decision making over time. For instance, states in the process represent possible levels of traits of the animal and transition probabilities are based on biological models estimated from data collected from the animal or herd. State space models (SSMs) are a general tool for modeling repeated measurements over time where the model parameters can evolve dynamically. In this paper we consider methods for embedding an SSM into an MDP with finite state and action space. Different ways of discretizing an SSM are discussed and methods for reducing the state space of the MDP are presented. An example from dairy production is given

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.; 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).

Classification of time series as early as possible is a valuable goal. Indeed, in many application domains, the earliest the decision, the more rewarding it can be. Yet, often, gathering more information allows one to get a better decision. The optimization of this time vs. accuracy tradeoff must generally be solved online and is a complex problem. This paper presents a formal criterion that expresses this trade-off in all generality together with a generic sequential meta algorithm to solve it. This meta algorithm is interesting in two ways. First, it pinpoints where choices can (have to) be made to obtain a computable algorithm. As a result a wealth of algorithmic solutions can be found. Second, it seeks online the earliest time in the future where a minimization of the criterion can be expected. It thus goes beyond the classical approaches that myopically decide at each time step whether to make a decision or to postpone the call one more time step. After this general setting has been expounded, we study one simple declination of the meta-algorithm, and we show the results obtained on synthetic and real time series data sets chosen for their ability to test the robustness and properties of the technique. The general approach is vindicated by the experimental results, which allows us to point to promising perspectives.