Abstract: Heterogeneity poses a fundamental challenge for many real-world large-scale decision-making problems but remains largely understudied.  In this paper, we study the fully heterogeneous setting of a prominent class of such problems, known as weakly-coupled Markov decision processes (WCMDPs).  Each WCMDP consists of N arms (or subproblems), which have distinct model parameters in the fully heterogeneous setting, leading to the curse of dimensionality when N is large.  We show that, under mild assumptions, an efficiently computable policy achieves an $O(1/\sqrt{N})$ optimality gap in the long-run average reward per arm for fully heterogeneous WCMDPs as N becomes large.  This is the first asymptotic optimality result for fully heterogeneous average-reward WCMDPs.  Our main technical innovation is the construction of projection-based Lyapunov functions that certify the convergence of rewards and costs to an optimal region, even under full heterogeneity.

Bio: Weina Wang is an Associate Professor in the Computer Science Department at Carnegie Mellon University. Her research lies in the broad area of applied probability, with a focus on decision-making in large stochastic systems. She was a joint postdoctoral research associate in the Coordinated Science Lab at the University of Illinois at Urbana-Champaign, and in the School of ECEE at Arizona State University, from 2016 to 2018. She received her Ph.D. degree in Electrical Engineering from Arizona State University in 2016, and her Bachelor’s degree from the Department of Electronic Engineering at Tsinghua University in 2009. Her dissertation received the Dean’s Dissertation Award in the Ira A. Fulton Schools of Engineering at Arizona State University in 2016. She received the Kenneth C. Sevcik Outstanding Student Paper Award at ACM SIGMETRICS 2016, the Best Paper Award at ACM MobiHoc 2022, an NSF CAREER award in 2022, and the ACM SIGMETRICS Rising Star Research Award in 2023.

Abstract: Multi-agent systems appear in many engineering and socioeconomic settings, wherein a group of agents or controllers interact with each other in a shared and possibly non-stationary environment, and make sequential decisions based on their own information using a (causal) interaction-mechanism. In this talk we focus attention on cooperative sequential decision making under uncertainty—a decentralized team, where a fixed finite number of agents act as a team with the common goal of minimizing a long-term cost function. We investigate the general situation where one long-term (objective) cost must be minimized, while maintaining multiple other long-term (constraint) costs within prescribed limits via a cooperative Multi-Agent Constrained Partially Observable Markov Decision Process (MAC-POMDP) model. Such constrained sequential team decision problems arise in several real-world applications where efficient operation must be balanced with maintaining safe operating margins—such considerations arise in communication networks, traffic management, energy-grid optimization, e-commerce pricing, environmental monitoring, etc. We focus on the discounted cost criterion, and start by establishing general results on Lagrangian duality and existence of a global saddle-point. Next, we consider decentralized policy-profiles and their mixtures, and establish that when agents mix jointly over their policy-profiles, there is no (Lagrangian) duality gap, and a global saddle-point exists under the Slater’s condition. However, when agents mix independently over their policy-profiles, we show (through a concrete counterexample) that a non-zero duality gap can exist. Then, we consider coordination policies and their mixtures, and establish that, except for pure coordination policies, they are all equivalent to joint mixtures of decentralized policy-profiles. This equivalence result helps reformulate the original multi-agent constrained optimization problem into a single-agent constrained optimization problem, which is then used to propose a primal-dual framework for model-based optimal control. Finally, we extend the notion of a Multi-Agent Approximate Information State (MA-AIS) to constrained decision making, and formalize MA-AIS based coordination policies and their mixtures. We establish through a concrete counterexample that, in contrast to behavioral coordination policies, MA-AIS based behavioral coordination policies and their mixtures are not equivalent. We also establish approximate optimality of mixtures of MA-AIS based coordination policies, and use this result to guide the development of a data-driven alternative for the aforementioned model-based primal-dual framework. 

Bio: Vijay Subramanian received the Ph.D. in electrical engineering from the University of Illinois at Urbana-Champaign in 1999. He worked with Motorola Inc., The Hamilton Institute, Maynooth, Ireland, for many years, and with the Department of Electrical Engineering and Computer Science at Northwestern University. In fall 2014, he joined the Department of Electrical Engineering and Computer Science at the University of Michigan as an associate professor and was promoted to professor in fall 2024. His research interests are in stochastic analysis, random graphs, multiagent systems, and game theory (mechanism and information design) with applications to social, economic, and technological networks.

Abstract: Polyak averaging is a well-known technique for achieving asymptotically optimal convergence in Stochastic Approximation. In this work, we establish the first high-probability bound for general Stochastic Approximation with Polyak Averaging. We take a black-box approach, assuming access to an anytime high-probability bound for a given Stochastic Approximation, and derive tight finite-time bounds for its Polyak-averaged version. Applying our black-box framework to general contractive Stochastic Approximation, we analyze the impact of averaging under various settings.

Bio: Sajad Khodadadian is an Assistant Professor in the Grado Department of Industrial and Systems Engineering in Virginia Tech. Dr. Khodadadian’s research is on design and analysis of Reinforcement Learning algorithms. He received his PhD in Operations Research from School of Industrial and Systems Engineering in Georgia Institute of Technology.

Abstract: We explore two complementary frameworks that harness reinforcement learning (RL) to unlock the full potential of large language models (LLMs) for “reasoning” (rationale generation) and “acting” (decision making).

- The first part introduces RAFA — a prompting mechanism that enables autonomous LLM agents to “reason for the future, act for now” in complex long-horizon decision-making tasks. In particular, we implement the reasoning process as learning and planning in Bayesian-adaptive Markov decision processes (MDPs), where the learning and planning subroutines employ in-context learning to emulate actor-critic updates. By guiding short-term acting with long-term reasoning, RAFA achieves provable regret guarantees while outperforming most existing approaches.

- The second part introduces BRiTE — a training paradigm that enhances the reasoning ability of LLMs. In particular, we view the reasoning process via a latent variable model, which yields a bootstrapping strategy that resembles the expectation-maximization (EM) algorithm. Here, the “E-step” samples rationales from the base model via RL in token-level MDPs, while the “M-step” distills rationales into the base model via supervised learning (SL). Through the RL-SL update, BRiTE enjoys provable convergence guarantees while providing significant empirical improvements, especially on various challenging benchmarks, without requiring expensive human-annotated rationales.

Together, RAFA and BRiTE showcase two distinct yet synergistic applications of RL — at the task level and the token level — for enhancing both the decision-making and rationale-generating abilities of LLMs.

Bio: Zhaoran Wang is an associate professor at Northwestern University, working at the interface of machine learning, statistics, and optimization. He is the recipient of the AISTATS (Artificial Intelligence and Statistics Conference) notable paper award, ASA (American Statistical Association) best student paper in statistical learning and data mining, INFORMS (Institute for Operations Research and the Management Sciences) best student paper finalist in data mining, Microsoft Ph.D. Fellowship, Simons-Berkeley/J.P. Morgan AI Research Fellowship, Amazon Machine Learning Research Award, and NSF CAREER Award.

Abstract: In this talk, we focus on a class of sampling-based optimization (SBO) algorithms that have gained remarkable empirical success in robotics optimal control problems that are non-convex and even discontinuous, often defying conventional wisdom that such optimizations are hard. We first reveal that these SBO algorithms are in fact zeroth order gradient methods for a smoothed version of the objective function controlled by a smoothing parameter decided by the sampling variance. Then, we provide a characterization of the landscape of the smoothed objective: smoothing renders the landscape more benign by enlarging the convex region around the global minimizer, but at the cost of introducing an optimality gap. Building on this insight, we establish non-asymptotic convergence guarantees for SBO algorithms to a neighborhood of the global minimizer. Further, we propose new SBO algorithms with diffusion-style annealing that lead to the first optimization-based method that optimizes over full-order quadruped dynamics in real-time. 

Bio: Guannan Qu has been an Assistant Professor at the Electrical and Computer Engineering Department of Carnegie Mellon University since September 2021. He received his B.S. degree in Electrical Engineering from Tsinghua University in Beijing, China in 2014, and his Ph.D. in Applied Mathematics from Harvard University in Cambridge, MA in 2019. He was a CMI and Resnick postdoctoral scholar in the Department of Computing and Mathematical Sciences at California Institute of Technology from 2019 to 2021. He is the recipient of NSF CAREER Award, IEEE Transactions on Smart Grid Top Papers Award, Caltech Simoudis Discovery Award, PIMCO Fellowship, Amazon AI4Science Fellowship, and IEEE SmartGridComm Best Student Paper Reward. His research interest lies in control, optimization, and machine/reinforcement learning with applications to power systems, multi-agent systems, Internet of things, smart city, etc.

Abstract: Queueing theory is rife with intractable scheduling and dispatching problems. Even seemingly simple problems remain open, especially when they involve multiple servers (e.g. scheduling in the M/G/k) or metrics beyond simple means (e.g. minimizing tail latency). But the last several years have seen significant progress in our understanding of these intractable problems, including solutions for certain asymptotic regimes.

This talk will give an overview of this recent progress. We will discuss what problems have been recently solved, what new tools underlie those recent solutions, what open problems are potentially solvable with the same new tools, and what open problems remain (subjectively!) out of reach without new ideas. Problems discussed will span

• both scheduling and dispatching,

• both single-server and multiserver systems,

• both known and unknown service times, and

• both mean and tail metrics.

Bio: Ziv Scully is an assistant professor at Cornell ORIE (Operations Research and Information Engineering). Prior to joining Cornell, he completed his PhD in Computer Science at CMU in 2022, advised by Mor Harchol-Balter and Guy Blelloch, then spent a postdoctoral year split between the UC Berkeley Simons Institute, Harvard SEAS, and MIT CSAIL. Ziv researches the theory of decision making under uncertainty and stochastic control, with a particular emphasis on scheduling and load balancing in queueing systems. His work has been recognized by awards from ACM SIGMETRICS (e.g. 2024 Best Paper), IFIP PERFORMANCE (e.g. 2023 Best Paper), and INFORMS (e.g. 2022 Nicholson Competition, first place).