This paper investigates a hybrid reinforcement learning setting in tabular Markov Decision Processes (MDPs), where an agent aims to learn an optimal policy by combining online interactions with a target environment and offline data from a source environment. A central challenge is that offline data may be collected from outdated environments with shifted transition dynamics, making naive integration of historical data ineffective. To address this, we propose a unified algorithmic framework featuring two algorithms: MIN-UCB-VI for regret minimization and MAX-LCB-VI for best policy identification. Both algorithms leverage fine-grained bias information to more effectively exploit offline data under general transition shifts. We provide theoretical guarantees for our framework, including both instance-dependent and independent upper bounds on regret and sub-optimality gap. Furthermore, we establish matching lower bounds to demonstrate the optimality of our approach and validate our theoretical findings through extensive experiments.
Influence Maximization (IM) problem aims to strategically identify a single set of influential individuals who can influence as many users as possible. It was first introduced in the context of viral marketing, where a company pays a small number of influencers to promote a product or service. Nevertheless, with the proliferation of modern social media platforms such as TikTok, real-world viral marketing scenarios have grown increasingly complex, generally requiring multiple sets of users to participate. To handle these scenarios, Huang et al. [42] recently formulated these problems as a general partition-constrained IM problem (IM-PC) and simultaneously proposed a tight (1-1/e-ε)-approximation RAMP algorithm for IM-PC. Despite its strong theoretical guarantee, RAMP is often hindered by its prohibitive memory overhead, as it must maintain 1/ε intermediate subsets during rounding, and sample inefficiency caused by requiring an additional RR set collection exclusively for solution evaluation. To overcome these limitations, we propose RBwA, a memory-efficient and sample-efficient progressive sampling algorithm for IM-PC. At its core, we utilize rademacher average from statistical learning theory to directly estimate solution quality, thereby eliminating the need for additional validation sets and simultaneously reducing the number of rounding invocations to a single call. Furthermore, we also devise a memory-efficient rounding scheme called BwARound for coverage maximization subroutines, which only requires storing one fractional vector and takes maximal feasible steps rather than tiny ε-increments, thus yielding significant improvements in both space complexity and iteration count over the rounding component AMPRound of RAMP. Finally, extensive experiments on large-scale social networks demonstrate the effectiveness of our proposed RBwA and BwARound.
Qixin Zhang, Qirun Zeng, Hui Lu et al.· Proceedings of the 32nd ACM...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
