Reinforcement learning (RL) has emerged as a fundamental approach to decision-making in machine learning, with applications across a wide range of real-world domains, and several practical extensions, such as multi-agent RL (MARL) and RL from human feedback (RLHF). Despite the growing successful applications of these systems, there exists an inherent threat when it comes to applying them in the real world, where ill-intentioned third parties may intervene in both their training process and deployment. This typically has catastrophic consequences, where even small and inexpensive perturbations to the environment may cause the system to substantially diverge from the desired behavior. The purpose of this thesis is to provide a thorough investigation of various adversarial attacks and robustness against such attacks to (MA)RL and (MA)RLHF systems. In particular, we study training-time and test-time attacks in MARL and propose algorithms that are shown to be provably robust against such attacks. Beyond MARL, we establish fundamental statistical results for RLHF, provide a rigorous characterization of poisoning attacks to RLHF, and develop robust extensions for MARLHF. Our work is centered around robust algorithmic approaches with provable guarantees under common assumptions.

Anomaly detection is one of the fundamental topics in machine learning and artificial intelligence. The aim is to identify instances that deviate from the norm, so-called anomalies. Such anomalies arise in many scenarios, ranging from attacks on computer or energy networks to critical faults in industrial systems or rare tumors in medical imaging data. In this talk, I will first provide an overview of the field of anomaly detection, with an emphasis on approaches based on deep neural networks. I will then present recent algorithms and theoretical advances in deep anomaly detection. In particular, I will discuss why certain methods work and how their behavior can be better understood using principled analysis. Furthermore, I will highlight recent developments in anomaly detection for time series data, including new benchmark datasets and theoretically-grounded evaluation metrics. Finally, I will conclude with an outlook on promising future research directions in anomaly detection.

We build secure software on a seemingly obvious assumption: the processor executes instructions correctly and enforces the boundaries between programs, operating systems, and virtual machines. But what if the CPU itself breaks these rules? Over the past decade, research has found increasingly powerful ways in which processors violate the abstractions on which software relies. What started with tiny timing differences revealing secrets led to attacks such as Spectre and Meltdown, and more recently to CPU bugs that can directly corrupt data, bypass isolation, or expose information across security boundaries.

In this talk, I will show how seemingly harmless implementation details and useful optimizations turn into practical security vulnerabilities. Using examples from our research across Intel, AMD, and RISC-V processors, I will talk about how we discover and understand CPU vulnerabilities and ultimately turn them into security problems. The broader lesson goes beyond processor security: abstractions are only as strong as the layers implementing them. If we want trustworthy computer systems, hardware must increasingly be tested, analyzed, and secured with the same rigor that we already apply to software.

A word is a sequence of symbols drawn from a finite set, and is often a device to represent the evolution of a (discretised) system. Words are central to both symbolic dynamics and verification. In the former discipline, words that represent the same system constitute a shift space, and are typically studied for their combinatorial structure. In verification, a quintessential objective is to certify that a system satisfies a logical specification by showing that its representative words are accepted by an automaton. In this thesis, we bridge the two perspectives through the following contributions.

1) We describe how the action of a deterministic finite transducer on an infinite word preserves the structure of the word. If the input word x has a recurrence property, then this property is preserved for the output word A(x); using the ergodic theory of shift spaces, we identify a large class of words x, including Sturmian words, such that A(x) is guaranteed to admit factor frequencies.

2) We show that we can determine whether an automaton accepts a word by reading its so-called S-adic construction. This allows us, e.g., to decide, given an automaton A, whether A accepts all Sturmian words, or all d-letter Arnoux-Rauzy words.

3) As applications, we study Monadic Second-Order (MSO) logic, and show that the MSO theory of the natural numbers remains decidable when expanded with the following sets of predicates: (i) powers of 2 and 3; (ii) powers of 2, 3, and 5, subject to Schanuel's conjecture; (iii) perfect squares and powers of 2, subject to the binary expansion of the square root of 2 being a disjunctive word.

What if we played a modified version of the Imitation Game, where instead of reading a textual conversation between a human and a machine, the evaluator instead evaluated the video (or VR) conversation between them? Enabling, and eventually winning, this game has been a north star in digital human research. While tremendous progress has occurred in modeling the physicality of digital humans, modeling the behaviour that drives our actions remains a challenging pursuit.

In this talk, I will discuss our ongoing works towards this goal. I will first introduce our works on character animation, and how we enable multiple modalities like text and audio to generate the animations. In the second half, I will introduce our works on co-speech gesture generation for virtual humans. The talk will accompany a demo of our work on real-time Embodied Character Agents.

The remarkable advances in AI have given rise to a growing interest in AI-assisted decision support in domains ranging from medicine and drug-discovery, to criminal justice and education. The ultimate goal in AI-assisted decision support is to optimally combine the complementary strengths of humans and AI models to achieve greater outcomes than either can achieve on their own, in short human-AI complementarity. Achieving this goal, however, has shown to be a major challenge as it typically requires human experts to understand when they can rely on the AI model for their decision—a highly non-trivial task. In this thesis, I show that it is possible to circumvent this challenge and achieve human-AI complementarity under an alternative design of decision support systems. The key innovation in this design lies in adaptively controlling the level of human agency by using an AI model to narrow down the decisions a human can take to a subset. I introduce algorithmic methods to construct as well as optimize these subsets to provably improve performance in decision-making tasks compared to the performance of the AI model used by the system or the human deciding on their own. To empirically evaluate these methods, I conduct two large-scale human subject studies that show that the proposed decision support system leads to human-AI complementarity in practice.