Uncertainty in interactive decision-making: learning, incentives, and robustness

This thesis investigates decision-making under uncertainty, particularly in interactive settings where outcomes depend on both the decision-maker’s actions and the responses of a dynamic or strategic environment. We study decision-making from three interconnected perspectives: learning, incentives, and robustness. The sequential decision-making with partial feedback framework models settings in which a decision-maker repeatedly interacts with an environment and improves their actions based on observed feedback. This framework captures the learning aspect of interactive decision-making, where the agent must adapt and improve over time using only partial and often noisy signals. The principal-agent model focuses on strategic environments in which a principal must design mechanisms that incentivize an agent—who may hold private information or take unobservable actions—to act in ways that align with the principal's objectives. This captures the incentive alignment component of decision-making under strategic uncertainty. These two frameworks often interact. In many real-world problems, the feedback the learner receives may be generated by strategic agents, or the environment may adapt in response to the learner’s behavior. In such cases, we study how to design learning algorithms that can adapt to strategic responses from a strategic source. At the same time, robustness emerges as a critical design objective across both settings. In online learning, we study how to design algorithms that remain effective when feedback is adversarially corrupted. In principal-agent problems, we study how the robustness of mechanisms can be measured and how to design such mechanisms. The first theme of the thesis is the study of online learning with adversarial corruption. We design corruption-robust algorithms for the contextual search problem, a problem motivated by applications such as dynamic pricing. We also study stochastic bandits under adversarial corruption, showing how minimal corruption can manipulate widely used algorithms such as UCB and Thompson Sampling. The second theme is learning and robustness in contract design problems. We show how tools from the first-order approach, traditionally used in economic theory to characterize optimal contracts, can be adapted for algorithmic learning. We also study the multi-task principal-agent problem, analyzing linear contracts from both robustness, fairness, and learning perspectives. Our results identify conditions under which linear contracts are worst-case optimal and explore how to estimate optimal contracts from data. Finally, we study the greedy algorithm in structured bandit problems. We provide a sharp characterization of when greedy succeeds or fails, based on a condition we call self-identifiability. This property determines whether greedy learning leads to asymptotically optimal behavior or suffers from linear regret.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois Urbana-Champaign

Year dc:date

2025

Author dc:creator

• Zuo, Shiliang

Contributors dc:contributor

• Chekuri, Chandra
• Srikant, Rayadurgam
• Xu, Yunzong
• Zhang, Tong
• Slivkins, Aleksandrs

• Online Learning
• Bandit Problems
• Sequential Decision-making
• Principal-agent Problems
• Contract Design
• Robustness

Statement dc:rights

• Copyright 2025 Shiliang Zuo

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/129913

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F129913