Distributed learning is the iterative process of decision-making in the presence of other decision-makers. In recent years, researchers across fields as disparate as engineering, biology, and economics have identified mathematically congruous problem formulations at the intersection of their disciplines. In particular, stochastic processes, game theory, and control theory have been brought to bare on certain very basic and universal questions. What sort of environments are conducive to distributed learning? Are there any generic algorithms offering non-trivial performance guarantees for a large class of models? The first half of this thesis makes contributions to two particular problems in distributed learning, self-assembly and language. Self-assembly refers to the emergence of high-level structures via the aggregate behavior of simpler building blocks. A number of algorithms have been suggested that are capable of generic self-assembly of graphs. That is, given a description of the objective they produce a policy with a corresponding performance guarantee. These guarantees have been in the form of deterministic convergence results. We introduce the notion of stochastic stability to the self-assembly problem. The stochastically stable states are the configurations the system spends almost all of its time in as a noise parameter is taken to zero. We show that in this framework simple procedures exist that are capable of self-assembly of any tree under stringent locality constraints. Our procedure gives an asymptotically maximum yield of target assemblies while obeying communication and reversibility constraints. We also present a slightly more sophisticated algorithm that guarantees maximum yields for any problem size. The latter algorithm utilizes a somewhat more presumptive notion of agents' internal states. While it is unknown whether an algorithm providing maximum yields subject to our constraints can depend only on the more parsimonious form of internal state, we are able to show that such an algorithm would not be able to possess a unique completing rule--- a useful feature for analysis. We then turn our attention to the problem of distributed learning of communication protocols, or, language. Recent results for signaling game models establish the non-negligible possibility of convergence, under distributed learning, to states of unbounded efficiency loss. We provide a tight lower bound on efficiency and discuss its implications. Moreover, motivated by the empirical phenomenon of linguistic drift, we study the signaling game under stochastic evolutionary dynamics. We again make use of stochastic stability analysis and show that the long-run distribution of states has support limited to the efficient communication systems. We find that this behavior is insensitive to the particular choice of evolutionary dynamic, a fact that is intuitively captured by the game's potential function corresponding to average fitness. Consequently, the model supports conclusions similar to those found in the literature on language competition. That is, we expect monomorphic language states to eventually predominate. Homophily has been identified as a feature that potentially stabilizes diverse linguistic communities. We find that incorporating homophily in our stochastic model gives mixed results. While the monomorphic prediction holds in the small noise limit, diversity can persist at higher noise levels or as a metastable phenomenon. The contributions of the second half of this thesis relate to more basic issues in distributed learning. In particular, we provide new results on the problem of distributed convergence to Nash equilibrium in finite games. A recently proposed class of games known as stable games have the attractive property of admitting global convergence to equilibria under many learning dynamics. We show that stable games can be formulated as passive input-output systems. This observation enables us to identify passivity of a learning dynamic as a sufficient condition for global convergence in stable games. Notably, dynamics satisfying our condition need not exhibit positive correlation between the payoffs and their directions of motion. We show that our condition is satisfied by the dynamics known to exhibit global convergence in stable games. We give a decision-theoretic interpretation for passive learning dynamics that mirrors the interpretation of stable games as strategic environments exhibiting self-defeating externalities. Moreover, we exploit the flexibility of the passivity condition to study the impact of applying various forecasting heuristics to the payoffs used in the learning process. Finally, we show how passivity can be used to identify strategic tendencies of the players that allow for convergence in the presence of information lags of arbitrary duration in some games.

Die Technische Mechanik (TM) ist ein Grundlagenfach vieler Ingenieurstudiengänge. Lern- und Verständnisschwierigkeiten in diesem Bereich führen jedoch verstärkt zu schlechten Prüfungsergebnissen und Problemen im weiteren Studienverlauf (Dammann, 2016). Von Studierenden häufig benannte Hürden sind v.a. den richtigen Lösungsansatz zu finden, mangelnde Vorstellungskraft, der hohe Lernaufwand, mathematische Grundlagen, unklare Aufgabenstellung, die Komplexität des Lernstoffs sowie nachträgliches (meist selbstständiges) Aufarbeiten (Seidel, Weidle, Flagmeier, Börner & Vossler, 2019). Game-based Learning (GBL) bietet eine Möglichkeit, Studierende und Lehrende bei der Bewältigung dieser Hürden zu unterstützen. In einem spielerisch gestalteten Lernszenario können Lernprozesse auf Grundlage vorher definierter Lernziele durch narrativ-immersive, adaptive, kompetitive und/oder kooperative Elemente unterstützt werden (Le, Weber & Ebner, 2013). Der Einsatz von GBL kann sich zudem positiv auf affektive, motivationale, kognitive und sozio-kulturelle Faktoren auswirken (Plass, Homer & Kinzer, 2015). Im Kontext des Ingenieurwesens erhofft sich das hier vorgestellte Learn&Play Projekt durch die geeignete Auswahl und Gestaltung von Spielelementen eine Ansprache dieser Faktoren, sodass eine Hinwendung zum Theorie geprägten Lerninhalt und schließlich auch zum Lernen selbst stattfindet. Dabei steht die aktive Auseinandersetzung und praktische Selbsterfahrung mit den Inhalten der TM im Vordergrund, was auch zu einer Verringerung der Komplexität führen soll. [... aus der Einführung]

This thesis investigates decision-making in two-player imperfect information games against opponents whose actions can affect our rewards, and whose strategies may be based on memories of interaction, or may be changing, or both. The focus is on modelling these dynamic opponents, and using the models to learn high-reward strategies. The main contributions of this work are: 1. An approach to learn high-reward strategies in small simultaneous-move games against these opponents. This is done by using a model of the opponent learnt from sequence prediction, with (possibly discounted) rewards learnt from reinforcement learning, to lookahead using explicit tree search. Empirical results show that this gains higher average rewards per game than state-of-the-art reinforcement learning agents in three simultaneous-move games. They also show that several sequence prediction methods model these opponents effectively, supporting the idea of using them from areas such as data compression and string matching; 2. An online expectation-maximisation algorithm that infers an agent's hidden information based on its behaviour in imperfect information games; 3. An approach to learn high-reward strategies in medium-size sequential-move poker games against these opponents. This is done by using a model of the opponent learnt from sequence prediction, which needs its hidden information (inferred by the online expectation-maximisation algorithm), to train a state-of-the-art no-regret learning algorithm by simulating games between the algorithm and the model. Empirical results show that this improves the no-regret learning algorithm's rewards when playing against popular and state-of-the-art algorithms in two simplified poker games; 4. Demonstrating that several change detection methods can effectively model changing categorical distributions with experimental results comparing their accuracies to empirical distributions. These results also show that their models can be used to outperform state-of-the-art reinforcement learning agents in two simultaneous-move games. This supports the idea of modelling changing opponent strategies with change detection methods; 5. Experimental results for the self-play convergence to mixed strategy Nash equilibria of the empirical distributions of plays of sequence prediction and change detection methods. The results show that they converge faster, and in more cases for change detection, than fictitious play.

This thesis is dedicated to creating a new system with capabilities to create new generic, autonomous strategy computer game controlling elements based on multi-agent systems with social, intelligent decision-making and learning skills. Basic types of strategy games and problems of their playing will be introduced, along with currently used methods of intelligent game AI development. This thesis also presents design and implementation of the new system, working model for a specific game and results obtained while testing it.

The purpose of this thesis was to examine if users of digital music games may acquire skills from the games that may be of use in learning to play a real instrument, that is a non-digitally simulated instrument like an acoustic piano. We have used Gee’s theory regarding a possible interconnection between different semiotic domains, and how this connection may enable a transfer of skills between related domains. In this thesis we examine possible skill transfer between the domains “digital games” and “non-digital instruments”. To examine our question formulation we chose to conduct a pilot study from which we collected both quantitative and qualitative data. The study was conducted on two groups of children, 6-9 years old, and consisted of the children accepting a musical challenge. The children in one of the groups got access to a digital piano application during a preparatory week, whilst the children in the second group lived their lives as usual. The results, and the time it took for the children to perform the assignment, was documented by the parents of the children in a questionnaire. The data from the questionnaire was then analyzed and used to draw conclusions regarding the possible effect of the piano application on the children. The analysis of the collected data showed that all children that had used the application passed the challenge. The analysis also showed that the child that had the fastest passing time on the challenge had used the application, and that the group of children that had used the application showed a faster average time for passing the challenge than the children who had not used the application. Even though some indicative patterns did emerge through our analysis of the collected data no definitive conclusions could be drawn regarding transfer of skills between the semiotic domains “digital games” and “non-digital instruments”. / Syftet med denna studie var att undersöka huruvida utövare av digitala musikspel kan tillgodogöra sig kunskaper från spel som är till nytta vid senare inlärning av ett riktigt, det vill säga fysiskt och icke digitalt simulerat instrument som exempelvis ett piano. Vi utgick från Gees teori om att olika semiotiska domäner kan vara kopplade till varandra på ett sätt som möjliggör överföring av kunskap mellan olika närbesläktade domäner. I vårt fall mellan domänerna ”digitala spel” och ”fysiska, icke-digitala musikinstrument”. För att utforska vår frågeställning valde vi att utföra en pilotstudie där vi samlade in och analyserade både kvantitativ och kvalitativ data. Studien bestod av att två grupper av barn, i åldrarna 6-9 år, fick en musikalisk utmaning. Barnen i den ena gruppen fick under en förberedande vecka tillgång till en digital pianoapplikation, medan barnen i den andra gruppen levde sina liv som vanligt. Resultatet, och tiden det tog för barnen att utföra utmaningen dokumenterades av barnens föräldrar i en enkät, och datan från enkäten användes sedan för att dra slutsatser kring den eventuella effekten av pianoapplikationen. Analysen av datan som samlades in via enkäten visade att alla barn som använt sig av applikationen klarade utmaningen. Analysen visade även att barnet som klarade utmaningen snabbast hade använt sig av applikationen och att den grupp med barn som använt applikationen hade en lägre genomsnittstid på utmaningen än barnen som ej använt applikationen. Trots att vissa antydande mönster kunde utläsas genom analys av vår enkätdata så kunde inga tydliga slutsatser dras kring möjligheten för kunskapsöverföring mellan de semiotiska domänerna ”digitala spel” och ”fysiska, icke-digitala musikinstrument”.