Uncertainty is fundamental to machine learning and decision-making, but the appropriate way to model it depends on the type of risk or randomness being considered, which in turn is governed by the structure of the specific problem at hand. This thesis explores structural uncertainty across diverse decision-making settings, from classical frameworks such as contextual bandits and linear quadratic control to modern foundation model systems including tool-using LLM agents and automated scientific discovery, arguing that effective decision-making requires identifying and exploiting the structure underlying uncertainty. We begin with off-policy evaluation in contextual bandits, where distributional uncertainty has factorization structure. We introduce a distributionally robust approach that models the factorization of the data-generating process for improved uncertainty quantification and robustness under general covariate shift. Next, we study linear quadratic control with untrusted ML predictions, where system disturbances have compositional structure arising from heterogeneous latent sources. We introduce DISC, an online policy that simultaneously disentangles latent disturbance structure and learns per-component confidence parameters, achieving near-optimal consistency when predictions are accurate while maintaining worst-case robustness guarantees when they fail. For tool-using LLM agents, standard logit-based uncertainty estimation fails to capture agent-environment interaction structure. We develop PROBECAL, which probes LLM hidden states to extract structural features of execution traces, yielding calibrated probabilities over execution correctness and improving existing LLM reasoning techniques. For LLM-based symbolic regression, uncertainty structure lies in the environment feedback mechanism, where scalar metrics like MSE compress rich statistical structure into a single number. We develop PROAUG, enabling code-based data analysis that lets agents actively extract structural signals during evolutionary search, significantly improving discovery efficiency. Across these settings, a common principle emerges: uncertainty is inherently structured, and decision-making systems that explicitly model this structure achieve superior robustness, efficiency, and reliability. This thesis demonstrates that structural uncertainty provides a unifying foundation for trustworthy machine learning across classical and modern AI paradigms.
H C Liu (Thu,) studied this question.