Yilun Chen is an assistant professor in the School of Data Science at CUHK Shenzhen (currently on leave), and a postdoctoral researcher at Columbia Business School. He obtained a PhD in Operations Research at Cornell University in 2021. Yilun’s research interest lies broadly in applied probability, with a specific focus on decision-making under uncertainty and its wide applications in Operations Research/Operations Management. His work was awarded first place in the 2019 INFORMS Nicholson Best Student Paper Competition.
| Name of Speaker | Dr Chen Yilun |
| Schedule | Friday 15 October, 10am – 11.30am
(60 min talk + 30 min Q&A) |
| Link to Register | https://nus-sg.zoom.us/meeting/register/tZcrde-rrDMsHNRtAlSfk8uzRR1XMiPuCd-f |
| Title | Tractability of high-dimensional online decision-making with limited action changes |
| Abstract | Data-driven online decision-making tasks arise frequently in various practical settings in OR/ OM, finance, healthcare, etc. Such tasks often boil down to solving certain stochastic dynamic programs (DPs) with prohibitively large state space and complicated dynamics, suffering from the computational challenge known as the curse of dimensionality. Existing approaches (e.g. ADP, deep learning) typically focus on achieving practical success and have limited performance guarantees. We propose an algorithm that overcomes this computational obstacle for a rich class of problems, subject only to a “limited-action-change’’ constraint, which incorporate important special cases including optimal stopping and limited-price-change dynamic pricing. Assuming a black-box simulator of the problem’s dynamics, our algorithm can return epsilon-optimal policies with sample and computational complexity scaling polynomially in T (the time horizon), and effectively independent of the underlying state space, analogous to a “PTAS’’. We further demonstrate that the limited-action-change constraint is crucial for such efficient algorithms to exist through the construction of a hard instance. The recent algorithmic progress in high-dimensional optimal stopping of Chen and Goldberg 21 is a key building block of our algorithm. |
