----------------------------------------------------------------------------------------------------







    Department of Systems Engineering and Engineering Management



                       The Chinese University of Hong Kong



----------------------------------------------------------------------------------------------------



Date: Friday, Feburary 28, 4:30 pm – 5:30 pm



Venue: ERB 513, The Chinese University of Hong Kong



Title: On the Foundation and Tractability of Robust Markov Decision Processes



Speaker: Professor Nian Si, HKUST







Abstract: The main theme of this talk is to investigate the existence

or absence of the dynamic programming principle (DPP).



In the first part, we focus on rectangular uncertainty sets and

develop a comprehensive modeling framework for distributionally robust

Markov decision processes (DRMDPs). This framework requires the

decision maker to optimize against the worst-case distributional shift

induced by an adversary. By unifying and extending existing

formulations, we rigorously construct DRMDPs that accommodate various

modeling attributes for both the decision maker and the adversary.

These attributes include different levels of adaptability granularity,

ranging from history-dependent to Markov and Markov time-homogeneous

dynamics. We further explore the flexibility of adversarial shifts by

examining SA- and S-rectangularity. Within this DRMDP framework, we

analyze conditions under which the DPP holds or fails, systematically

studying different combinations of decision-maker and adversary

attributes.



In the second part, we extend our analysis beyond rectangular

uncertainty sets and introduce the notion of tractability.

Surprisingly, we show that, in full generality—without any assumptions

on instantaneous rewards—rectangular uncertainty sets are the onlytractable models. Our analysis further reveals that existing

non-rectangular models, including R-rectangular uncertainty and its

generalizations, are only weakly tractable. A key insight underlying

our results is the novel simultaneous solvability property, which we

identify as central to several fundamental properties of robust MDPs,

including the existence of stationary optimal policies and dynamic

programming principles. This property enables a unified approach to

analyzing the tractability of all uncertainty models, whether

rectangular or non-rectangular.



This talk is based on two papers: https://arxiv.org/abs/2311.09018 and

https://arxiv.org/abs/2411.08435.







Bio: Nian Si is an assistant professor at HKUST IEDA. He was a

postdoctoral principal researcher at the University of Chicago Booth

School of Business, working with Professor Baris Ata. He obtained my

Ph.D. in the Department of Management Science and Engineering (MS&E)

at Stanford University, where he was advised by Professor Jose

Blanchet and closely worked with Professor Ramesh Johari. He was a

member of the Stanford Operations Research Group. Previously, He

obtained a B.A. in Economics and a B.S. in Mathematics and Applied

Mathematics both from Peking University in 2017.



His research lies at the interface of operations research, statistics,

machine learning, and economics. He is also interested in real-world

operational problems arising from online platforms, including A/B

tests, recommendation systems, online advertising, cloud computing,

AI, etc.



Everyone is welcome to attend the talk!