本周六下午 15:00-17:00，我们将在学堂 112【线下】给大家带来王康宁和陈树伦同学的报告。报告内容与理论计算机和强化学习理论。在报告前后，同学们可以吃零食 and/or 自由交流。
报告 1 摘要
王康宁学长是姚班 2013 级校友，现任罗格斯大学（Rutgers University）计算机科学系助理教授。他的研究领域是经济与计算，特别是社会选择、机制设计和信息设计。他的研究曾获得 SODA 2024 和 WINE 2018 最佳论文奖。他将分享关于「如何让多数人站在你这边」主题的研究。孔多塞悖论（Condorcet’s paradox）是社会选择理论的基石之一。它指出，在某些选举中，无论哪个候选人获胜，都会有大多数选民更偏爱另一位候选人。在这种情况下，我们能做些什么来保证获得多数人的支持呢？Elkind、Lang 和 Saffidine 提出了一个想法：选出多名候选人（组成一个「委员会」）。这样，一个选民只有在「更偏爱某个未当选的候选人胜过每一位已当选的候选人」时，才算作偏爱那个未当选的候选人。在这种设定下，我们希望这个当选候选人组成的「委员会」能够赢得多数支持，以对抗任何一个未当选的候选人。显然，如果我们把所有候选人都选上，这个性质肯定能得到保证，但要实现这一目标，我们最少需要选出多少名候选人呢？
报告 2 摘要
陈树伦是姚班 2022 级（计科 21）的本科生，他的主要研究方向是强化学习理论。本次 seminar 将介绍他在华盛顿大学与杜少雷教授与周润龙学长合作进行的研究。本次研究主要关注马尔科夫决策过程（Markov Decision Process, MDP）基于最优-次优间隔（gap）的在线学习复杂度。他提出了一种新的方差分析方法，基于这种方法，他首先证明了张子函等人提出的在线学习算法 MVP（Monotonic Value Propagation）的累积后悔（regret）上界的主项不依赖于决策深度。此外，他与周润龙、张子函等人合作提出了一种新的衡量 MDP 实例困难程度的方差度量并通过下界分析证明了其最优性，该结果还表明传统的最大总方差在已知 gap 时无法用来衡量 MDP 实例的难度。本工作已被 NeurIPS 2025 接受，论文链接：https://openreview.net/forum?id=phC2nmJywQ
欢迎全体同学参加~
【重复一遍时间地点】北京时间本周六 11 月 15 日下午 15:00 - 17:00 清华学堂112 点击此处进行时区转换 腾讯会议 457-447-716
Make IIIS Great Again!
