Near-optimal Policies for Resource Allocation with Correlated Arrivals
发布时间：2024年07月16日
浏览次数：1664
发布者: Xiaoni Tan
主讲人： Jiashuo Jiang(HKUST)
活动时间： 从 2024-07-22 10:00 到 12:00
场地： Room 78301, Jingchunyuan 78, BICMR
Abstract: Resource allocation is a central topic in operations research and enjoys wide applications in e-commerce systems, supply chain systems, and online advertising. In these problems, we must allocate fixed resources to satisfy queries that arrive sequentially. However, there is a lack of near-optimal policies that are aware of the correlations of the queries over time. In this talk, we aim to present policies that solve the resource allocation problems when queries are correlated in a Markovian manner, which is general enough to incorporate many specific correlated arrivals as special cases. In the first part, we present a policy that is based on approximate dynamic programming techniques and show a constant approximation ratio of our policy. In the second part, we consider a data-driven setting and take a "reinforcement learning" approach to approximate the optimal policy with instance-dependent sample complexity guarantee, based on joint work with Prof. Yinyu Ye.
