Back to search

Cornell University

ONLINE DECISION MAKING WITH UNKNOWN CONSTRAINTS

Abstract

dc:description.abstract

New safety concerns have arisen with the growth of machine learning, necessitating mitigation efforts to ensure algorithms adhere to trustworthiness standards. In this dissertation, we study problems where safety constraints are potentially unknown and are strictly enforced. In the first part of the dissertation, we study social network polarization as a form of unsafe outcome. In this setting, a learner must provide useful recommendations to a social network of users while preventing bias and polarization amongst the users - complex emergent phenomena based on network dynamics. We generalize established models of opinion formation in economic theory and mathematical sociology [Degroot [1974, Friedkin and Johnsen [1990]] to account for cognitive biases [Lord et al. [1979]] and the presence of a recommender system. Using this model, we define bias as opinion shift from initial opinions, and polarization as opinion shift from mean opinions. We develop algorithms perform well, while controlling bias and polarization through an indirect safety constraint leveraging network properties. To this end, we use tools from online learning literature to show that it is possible to design an algorithm to aggregate recommendation or predictions in a way that ensures that it is non-polarizing (or non-biasing) and also has vanishing regret w.r.t. to be best non-polarizing (or non-biasing) mixture of base recommenders. We also provide an efficient version of our aggregation algorithm that ensures non-biasedness under mild assumptions on our opinion dynamic model. In the second part of the dissertation, we study the broader problem of online learning where the sequence of actions played by the learner must adhere to an unknown safety constraint at every round. The goal is to minimize regret with respect to the best safe action in hindsight while simultaneously satisfying the safety constraint with high probability on each round. We provide a general meta-algorithm that leverages an online regression oracle to estimate the unknown safety constraint, and converts the predictions of an online learning oracle to predictions that adhere to the unknown safety constraint. On the theoretical side, our algorithm's regret can be bounded by the regret of the online regression and online learning oracles, the eluder dimension of the model class containing the unknown safety constraint, and a novel complexity measure that characterizes the difficulty of safe learning. We complement our result with an asymptotic lower bound that shows that the aforementioned complexity measure is necessary. When the constraints are linear, we instantiate our result to provide a the first algorithm with $\sqrt{T}$ regret using a scaling transformation that balances optimistic exploration with pessimistic constraint satisfaction.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Computer Science
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Computer Science
Grantor
Cornell University
Year dc:date.issued
2025

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Yoo, Seung Won
Chair dc:contributor.chair
  • Sridharan, Karthik
Committee members dc:contributor.committeemember
  • Tardos, Eva
  • De Sa, Christopher

Subjects

dc:subject × 5

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
17422375
Dc Identifier Other
ProQuest Submission ID: 15143
ProQuest Publication ID: 32166973

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Yoo, Seung Won. ONLINE DECISION MAKING WITH UNKNOWN CONSTRAINTS. Doctor of Philosophy thesis, Cornell University, 2025. https://hdl.handle.net/1813/120890