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

Zuo, Shiliang

Permalink

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

Description

Title

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

Author(s)

Zuo, Shiliang

Issue Date

2025-07-07

Director of Research (if dissertation) or Advisor (if thesis)

Chekuri, Chandra

Doctoral Committee Chair(s)

Chekuri, Chandra

Committee Member(s)

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

Department of Study

Siebel School Comp & Data Sci

Discipline

Computer Science

Degree Granting Institution

University of Illinois Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Online learning
• bandit problems
• sequential decision-making
• principal-agent problems
• contract design
• robustness

Abstract

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.

Graduation Semester

2025-08

Type of Resource

Thesis

Handle URL

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

Copyright and License Information

Copyright 2025 Shiliang Zuo

Owning Collections