CS Peer Talk | On the Informativeness of Moments in Optimal Stopping

第六十二期

报告人：Jiechen Zhang, EPFL

时间：9月7日（星期一）3:00pm

地点：静园五院204

Host：宋铭宇

报告信息

Title

On the Informativeness of Moments in Optimal Stopping

Abstract

The Prophet Inequality is a cornerstone of optimal stopping. While the classic Prophet Inequality relies on full distributional knowledge, recent research has successfully extended it to limited information settings, showing that access to even a single sample is enough to recover the optimal guarantee. In this talk, I investigate a different natural model: what if the decision-maker knows only the moments of the distributions?

To start, I will show a simple algorithm that achieves an  competitive ratio using only the first moment. Then, I will present a strong negative result: unlike the sample-based case, even knowledge of all moments is insufficient to achieve a competitive ratio better than   . This implies that higher-order moments provide no additional utility over knowing just the mean in the worst case.

Finally, I will discuss how structural assumptions can break this logarithmic barrier. I will also share some additional developed results and insights derived that go beyond the scope of the paper.

Biography

Jiechen Zhang is a Ph.D. candidate at EPFL, advised by Prof. Andrés Cristi. He received his bachelor's degree with honours in mathematics and computer science from McGill University. His research focuses on stochastic optimization and online decision-making in large-scale systems.

about CS Peer Talk

作为活动的发起人，我们来自果冻传媒 图灵班科研活动委员会，主要由图灵班各年级同学组成。我们希望搭建一个CS同学交流的平台，促进同学间的交流合作，帮助同学练习展示，同时增进友谊。

目前在计划中的系列包括但不限于：

教程系列：学生讲者为主，介绍自己的研究领域

研究系列：学生讲者为主，介绍自己的研究成果

客座系列：邀请老师作主题报告

除非报告人特别要求，报告默认是非公开的，希望营造一个自由放松但又互相激励的交流氛围。

主讲嘉宾招募

如果你愿意和大家分享你的学术成果、经历经验，总结回顾、触发新思，欢迎报名自荐。

主讲人报名：发邮件至 [email protected]，并抄送 [email protected]，写明想讲的题目、内容及时间。