Decision making in large stochastic systems is a central problem across computer systems, machine learning, and operations research. Such systems typically consist of a large number of interacting entities, which makes efficient and performant decision making especially challenging

In this thesis, we study a wide variety of large stochastic systems. Despite their diverse problem definitions, these systems share similar underlying structures and admit similar fundamental techniques for performance analysis and policy design. We identify two such structures, each grouping a family of seemingly distinct problems. The two structures share a common spirit: an intractable system can be approximated by a simpler, well-understood one.

The first part studies the weak-coupling structure, where a system can be approximated by a collection of independent, low-dimensional subsystems. We design a control policy on this simple proxy and convert it into a near-optimal policy for the original, coupled system. Applied to stochastic bin packing, restless bandits, and weakly-coupled Markov decision processes (WCMDPs), this yields efficiently computable policies that are provably near-optimal at scale, under substantially weaker and more easily verifiable conditions than were previously required.

The second part studies the one-dimensional structure, where a key quantity of the system can be approximated by a one-dimensional process even when the full state is high- or infinite-dimensional. Applying this idea to multiserver queues, we prove new universal bounds for the G/G/n queue, show that the Gittins policy is near-optimal for G/G/n queues with setup times, and determine the best achievable delay together with a near-optimal policy for the multiserver-job model.

672 pages

Thesis Committee:
Weina Wang (Chair)
Mor Harchol-Balter
Alan Scheller-Wolf
Jim Dai (Cornell University)
Yudong Chen (University of Wisconsin-Madison)
Qiaomin Xie (University of Wisconsin-Madison)

Jignesh Patel, Interim Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Creative Commons: CC-BY (Attribution)

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu