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

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

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

The main work for this thesis has been a thorough study of the novel Prediction with Partially Monitored Grouped Expert Advice and Side Information paradigm. This is newly proposed in this thesis, and it extends the widely studied Prediction with Expert Advice paradigm. The extension is based on two assumptions and one restriction that modify the original problem. The first assumption, Grouped, presumes that the experts are structured into groups. The second assumption, Side Information, introduces additional information that can be used to timely relate predictions with groups. Finally, the restriction, Partially Monitored, imposes that the groups’ predictions are only known for one group at a time. The study of this paradigm includes the design of a complete prediction algorithm, the proof of a theoretical bound of the worse-case cumulative regret for such algorithm, and an experimental evaluation of the algorithm (proving the existence of cases where this paradigm outperforms Prediction with Expert Advice). Furthermore, since the development of the algorithm is constructive, it allows to easily build two additional prediction algorithms for the Prediction with Grouped Expert Advice and Prediction with Grouped Expert Advice and Side Information paradigms. Therefore, this thesis presents three novel prediction algorithms, with corresponding regret bounds, and a comparative experimental evaluation including the original Prediction with Expert Advice paradigm. / Huvudarbetet för den här avhandlingen har varit en grundlig studie av den nya Prediction with Partially Monitored Grouped Expert Advice and Side Information paradigmet. Detta är nyligen föreslagit i denna avhandling, och det utökar det brett studerade Prediction with Expert Advice paradigmet. Förlängningen baseras på två antaganden och en begränsning som ändrar det ursprungliga problemet. Det första antagandet, Grouped, förutsätter att experterna är inbyggda i grupper. Det andra antagandet, Side Information, introducerar ytterligare information som kan användas för att i tid relatera förutsägelser med grupper. Slutligen innebär begränsningen, Partially Monitored, att gruppens förutsägelser endast är kända för en grupp i taget. Studien av detta paradigm innefattar utformningen av en komplett förutsägelsesalgoritm, beviset på en teoretisk bindning till det sämre fallet kumulativa ånger för en sådan algoritm och en experimentell utvärdering av algoritmen (bevisar förekomsten av fall där detta paradigm överträffar Prediction with Expert Advice). Eftersom algoritmens utveckling är konstruktiv tillåter den dessutom att enkelt bygga två ytterligare prediksionsalgoritmer för Prediction with Grouped Expert Advice och Prediction with Grouped Expert Advice and Side Information paradigmer. Därför presenterar denna avhandling tre nya prediktionsalgoritmer med motsvarande ångergränser och en jämförande experimentell utvärdering inklusive det ursprungliga Prediction with Expert Advice paradigmet.

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

<div>This thesis consists of three chapters. In the first chapter, I investigate the effects of complexity in various voting systems on individual behavior in small group electoral competitions. Using a laboratory experiment, I observe individual behavior within one of three voting systems -- plurality, instant runoff voting (IRV), and score then automatic runoff (STAR). I then estimate subjects' behavior in three different models of bounded rationality. The estimated models are a model of Level-K thinking (Nagel, 1995), the Cognitive Hierarchy (CH) model (Camerer, et al. 2004), and a Quantal Response Equilibrium (QRE) (McKelvey and Palfrey 1995). I consistently find that more complex voting systems induce lower levels of strategic thinking. This implies that policy makers desiring more sincere voting behavior could potentially achieve this through voting systems with more complex strategy sets. Of the tested behavioral models, Level-K consistently fits observed data the best, implying subjects make decisions that combine of steps of thinking with random, utility maximizing, errors.</div><div><br></div><div>In the second chapter, I investigate the relationship between the mechanisms used to select leaders and both measures of group performance and leaders' ethical behavior. Using a laboratory experiment, we measure group performance in a group minimum effort task with a leader selected using one of three mechanisms: random, a competition task, and voting. After the group task, leaders must complete a task that asks them to behave honestly or dishonestly in questions related to the groups performance. We find that leaders have a large impact on group performance when compared to those groups without leaders. Evidence for which selection mechanism performs best in terms of group performance seems mixed. On measures of honesty, the strongest evidence seems to indicate that honesty is most positively impacted through a voting selection mechanism, which differences in ethical behavior between the random and competition selection treatments are negligible.</div><div><br></div><div><br></div><div>In the third chapter, I provide an investigation into the factors and conditions that drive "free riding" behavior in dynamic innovation contests. Starting from a dynamic innovation contest model from Halac, et al. (2017), I construct a two period dynamic innovation contest game. From there, I provide a theoretical background and derivation of mixed strategies that can be interpreted as an agent's degree to which they engage in free riding behavior, namely through allowing their opponent to exert effort in order to uncover information about an uncertain state of the world. I show certain conditions must be fulfilled in order to induce free riding in equilibrium, and also analytically show the impact of changing contest prize structures on the degree of free riding. I end this paper with an experimental design to test these various theoretical conclusions in a laboratory setting while also considering the behavioral observations recorded in studies investigating similar contest models and provide a plan to analyze the data collected by this laboratory experiment.</div><div><br></div><div>All data collected for this study consists of individual human subject data collected from laboratory experiments. Project procedures have been conducted in accordance with Purdue's internal review board approval and known consent from all participants was obtained.</div>

承襲清末地方軍事主義與西方條約特權體系脈絡，加以民初軍閥亂政影響，民國時期的中國社會逐漸出現兩種類型的特權人物：一個是手握槍桿子的「丘八爺」，另一個則是同時操持著條約與砲艦的「洋大人」。 「丘八爺」是軍閥割據與頻繁內戰的產物。數以百萬計的「丘八爺」平素身著戎裝，打著軍人名義，動輒打打殺殺，作戰失敗或軍隊欠餉時，即譁變作亂，化為草莽土匪，到處打家劫舍。但遇軍閥招安，則又由匪轉兵，形成兵、匪間的惡性循環。雖然嚴格說來兵、匪之間不無差異，但是民國以來，尤其北京政府時期，「丘八爺」往往以兵、匪不分的兵匪面目，烙印在一般人的印象中。 另一方面，歐美國家自清末挾帶條約體系與船堅砲利來到中國之後，經由一連串戰爭，透過砲艦外交模式教導中國人：條約必須遵守、外人生命財產安全必須獲得保障。歐美國家常設性駐華外交、領事機構，則是扮演關鍵性的角色，手持上帝之鞭，多年來宣傳、馴化中國政府與中國人。如此，中國逐漸從抗拒、反彈，到接受西方權威，承認外國人在華的地位不容輕蔑與挑戰。「洋大人」的權威形象，由此在中國樹立起來。 理論上，「丘八爺」為禍雖大，百姓亦深以為苦，但畢竟是中國內政問題，與外交事務無涉。可是，清末以來，隨著大批洋人進入中國內陸通商、傳教與居住、外國資金流入中國市場、外國軍艦巡弋重要內河、外國領事機構與軍隊駐紮各通商要衢，條約特權體制進一步內化為中國權勢結構的一部份。當數量龐大、散佈全國的「丘八爺」，與深入中國內陸的「洋大人」頻繁接觸，「丘八爺」將魔爪伸向「洋大人」之後，也就變成嚴重的外交問題。 歐戰後的東亞秩序，歷經巴黎和會、華盛頓會議的凝聚共識，歐美列強（包括日本）逐漸形成一個觀念：將美國對華政策擴大為各國對華政策，也就是放棄原先帝國主義競爭、權力均勢的模式，改以「門戶開放政策」作為處理中國事務的中心指標。與此同時，經過馬列主義、無產階級革命洗禮的蘇聯，也重新回到中國：一方面利用放棄在華特權博取中國同情，另一方面以打倒歐美帝國主義為口號，大肆宣傳民族主義式理念。列強任何強硬的舉動，常被布爾什維克宣傳家渲染為帝國主義侵華鐵證，激發更強大的反帝浪潮。在這樣的國際場景之下，當「丘八爺」遇上了「洋大人」，會發生什麼問題？當「丘八爺」以打、殺、搶、綁等各種暴力形式，一再挑釁「洋大人」威嚴，甚至任意污衊指為「洋鬼子」時，「洋大人」該如何應付？蘇聯宣傳家環伺在側、伺機扯後腿的情況下，「洋大人」是否還能重施故技，以帝國主義的老路子—砲艦外交來施以懲罰？另謀他法？抑或默認中國現狀的發展？ 此外，1920年代前後，中國軍閥割據、南北對立逐漸發展到高峰，北京政府對外雖有中央之名、對內則無約束地方之實力。面對如此威信不足、欲振乏力的北京政府，以及地方分裂割據的現狀，「洋大人」顯然無法經由「代理人機制」，透過北京政府有效地制約地方問題。 因此，1920年代上半期，當意氣風發、趾高氣昂的「丘八爺」，遇上了受到外在與內部多重制約、看似有些跛腳的「洋大人」，勢必會產生許多值得深入討論、分析的有趣問題。 其次，當我們回顧以往被定位為帝國主義侵華—國賊賣國史的北洋外交史，面對民族主義史觀與俯拾皆是的情緒性指責字眼，是否應該嘗試以新的理解取代原先的敵意，重新建構不同視野的北洋外交史？處於中國軍閥主義高漲的1920年代上半期，體現中國內政不安因子、大肆肆虐中國社會各個角落的「丘八爺」現象，與「洋大人」之間的互動，及其衍生出的種種外交交涉，乃是當時最常見的外交與內政問題。但是囿於傳統民族主義史觀，外交史家往往只著重關係國家民族大義的重大外交事件，以及國際會議層次，屬於政府高層官方外交(high diplomacy)往來交涉模式。對於發生於社會下層，一些名不見經傳的「丘八爺」與「洋大人」衝突問題，外交史家若非視而不見，即是匆匆帶過，而忽略華洋衝突背後所隱藏的重要文化意涵。究其實際，當西方列強以帝國主義強權之姿在中國樹立起條約特權體制，「洋大人」頻頻以傳教士、商人角色深入中國內陸之際，中外之間國家主權界線因此變動不居，產生許多不明確的灰色地帶。而發生在中國內部，由「丘八爺」與「洋大人」構織出的華洋衝突事件，就是徘徊在邊境與邊界之間的重要問題。一方面華洋衝突涉及到兩國之間條約權利與義務的界定，屬於官方外交層次、明確的國家主權邊界設定。另一方面，華洋衝突在本質上，同時也涉及到不同文化邂逅下的族群衝突問題，以及彼此認知、設想的民族偏見問題，如中國人心中的「洋大人形象」，與洋人心中的中國的「兵匪問題」均屬於這個層次。而在文化邊際效應的作用下，華洋勢力之間的滲透、爭執與磨合，構成中外往來的真實文化底蘊，正是當時日常生活的寫實反映。透過發生在邊境地帶的華洋衝突研究，與中外官方外交進行對話、討論，或許可以思索出與傳統相當不一樣的中外關係史。 因此，本文試圖從複雜的華洋糾葛角度，以「丘八爺」與「洋大人」的互動切入點，經由複線式歷史論述與中外不同觀點的探討，由下往上地剖析外交問題，探究當時中外重疊地帶上的北洋外交史。

The multi-armed bandit (MAB) problem provides a convenient abstraction for many online decision problems arising in modern applications including Internet display advertising, crowdsourcing, online procurement, smart grids, etc. Several variants of the MAB problem have been proposed to extend the basic model to a variety of practical and general settings. The sleeping multi-armed bandit (SMAB) problem is one such variant where the set of available arms varies with time. This study is focused on analyzing the efficacy of the Thompson Sampling algorithm for solving the SMAB problem. Any algorithm for the classical MAB problem is expected to choose one of K available arms (actions) in each of T consecutive rounds. Each choice of an arm generates a stochastic reward from an unknown but fixed distribution. The goal of the algorithm is to maximize the expected sum of rewards over the T rounds (or equivalently minimize the expected total regret), relative to the best fixed action in hindsight. In many real-world settings, however, not all arms may be available in any given round. For example, in Internet display advertising, some advertisers might choose to stay away from the auction due to budget constraints; in crowdsourcing, some workers may not be available at a given time due to timezone difference, etc. Such situations give rise to the sleeping MAB abstraction. In the literature, several upper confidence bound (UCB)-based approaches have been proposed and investigated for the SMAB problem. Our contribution is to investigate the efficacy of a Thomp-son Sampling-based approach. Our key finding is to establish a logarithmic regret bound, which non-trivially generalizes a similar bound known for this approach in the classical MAB setting. Our bound also matches (up to constants) the best-known lower bound for the SMAB problem. Furthermore, we show via detailed simulations, that the Thompson Sampling approach in fact outperforms the known algorithms for the SMAB problem.