Near-optimal Policies for Resource Allocation with Correlated Arrivals
Time: 2024-07-16
Published By: Xiaoni Tan
Speaker(s): Jiashuo Jiang(HKUST)
Time: 10:00-12:00 July 22, 2024
Venue: 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.
