Photo source: University of Alberta
Athabasca Hall, University of Alberta
University Commons, University of Alberta
Photo source: University of Alberta
Photo source: University of Alberta
Athabasca Hall, University of Alberta
University Commons, University of Alberta
Photo source: University of Alberta
The Systems-Oriented Decision Algorithms Lab (SODALab) studies algorithms and decision-making in dynamic, uncertain environments. Based at the University of Alberta and the Alberta Machine Intelligence Institute (Amii) in Edmonton, we develop algorithms for increasingly complex decision systems that underpin modern computation and digital infrastructure.
At SODALab, we view the modern world as a collection of complex decision systems, ranging from large-scale digital platforms (e.g., online marketplaces) to AI infrastructures such as LLM inference systems. As algorithms increasingly shape the allocation of resources and broader social and economic outcomes, their design and analysis must be grounded in the structural properties of the systems and environments they serve, especially those arising from constraints (e.g., physical limits and institutional rules) and information (e.g., data, predictions, and feedback from interactions). Our research develops mathematical models that capture these features and analyzes how algorithmic performance scales with them. Ultimately, our goal is to develop a principled framework for decision-making under uncertainty, in which structural modeling, robustness, and learning are integrated to support reliable and adaptive decision-making in high-stakes environments.
May 2026: [Paper Acceptance] Our paper, “Offline-to-Online Learning in Linear Bandits,” accepted to RLC 2026.
May 2026: [Paper Acceptance] Our paper, “Trajectory Data Suffices for Statistically Efficient Policy Evaluation in Finite-Horizon Offline RL with Linear $q^{\pi}$-Realizability and Concentrability,” accepted to COLT 2026.
Apr 2026: [Member Highlights] Hossein won the MSc Outstanding Thesis Award in Computing Science at the University of Alberta. Congratulations!!
- Hossein’s thesis: “Randomized Posted Pricing and Rounding Schemes for Online Selection and Matching.”
- Publications related to Hossein’s thesis: [arXiv:2512.02427], WWW 2026, WWW 2025, WINE 2024.
- Photo from the award ceremony; Link to Hossein’s social post.
Jan 2026: [Student Milestones] Siyuan successfully passed his thesis defense. Congratulations!!
- Siyuan’s MSc thesis: “Online Fractional Knapsack with Packing Costs and Group Quotas.”
Jan 2026: [Paper Acceptance] Our paper, “Online Rounding and Pricing Schemes for $ k $-Rental Problems,” accepted to WWW 2026.
Nov 2025: [Paper Acceptance] Our paper, Ordinal Secretaries with Advice, accepted to AAAI 2026.
Sep 2025: [Paper Acceptance] Two papers accepted to NeurIPS 2025.
Our first paper, “Computational Hardness of Reinforcement Learning with Partial $q^{\pi}$-Realizability,” investigates the computational complexity of reinforcement learning with a generative model under partial $q^\pi$-realizability—a setting where only a subset of policies admit linear realizability. This is in contrast to the conventional $q^\pi$-realizability assumption, under which the action-value functions of all policies are linearly realizable.
The second paper, “Online Multi-Class Selection with Group Fairness Guarantee,” studies an online allocation problem with group fairness guarantees. It addresses two key questions left open by our prior work in ACM SIGMETRICS 2025: (i) how to handle the case where agents may belong to multiple groups, and (ii) how to ensure group fairness in online allocation when resources are indivisible.
Sep 2025: [Member Highlights] Lyndon joined the lab as a MSc student. Welcome!!
Jul 2025: [Service Updates] Xiaoqi to serve on the program committees of ACM SIGMETRICS 2026, WINE 2025, and ACM e-Energy 2026.
May 2025: [Member Highlights] Vlad received the Canada Graduate Scholarships – Doctoral (CGS D) Award. Congratulations!!
Apr 2025: [Paper Acceptance] Our paper, “Cap-and-Penalize: Competitive Mechanisms for Multi-Phase Regularized Online Allocation,” accepted to IJCAI 2025.
Apr 2025: [Student Milestones] Four MSc students successfully defended their theses. Congratulations!!
- Hasti’s MSc thesis: “Value-oblivious Secretaries with Advice.”
- Kimia’s MSc thesis: “Multi-phase Regularized Online Allocation.”
- Shayan’s MSc thesis: “Computational Complexity of Reinforcement Learning under Partial $ q^{\pi}$-realizability.”
- Hossein’s MSc thesis: “Randomized Posted Pricing and Rounding Schemes for Online Selection and Matching.”
Mar 2025: [Paper Acceptance] Our paper, “Online Allocation with Multi-Class Arrivals: Group Fairness vs Individual Welfare,” accepted to ACM SIGMETRICS 2025.
Feb 2025: [Paper Acceptance] Our paper, “Threshold Policies with Tight Guarantees for Online Selection with Convex Costs,” accepted to ACM Transactions on Economics and Computation. An earlier version of this paper was presented in WINE 2023.
Feb 2025: [Paper Acceptance] Our paper, “Posted Price Mechanisms for Online Allocation with Diseconomies of Scale,” accepted to WWW 2025.
Jan 2025: [Student Milestones] Yanzhao successfully passed his thesis defense. Congratulations!!
- Yanzhao’s MSc thesis: “Online Conversion under Horizon Uncertainty: From Competitive Analysis to Learning-Augmented Algorithms.” The thesis is partially based on the paper: “Knowing When to Stop Matters: A Unified Framework for Online Conversion under Horizon Uncertainty.”
Jan 2025: [Member Highlights] Haoxin and Faraz joined the lab as PhD students. Welcome!!
We are grateful for the generous support from the following sponsors.
