Shuai Li
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Shuai Li has a total of 123 co-authors. Here are the top co-authors by number of shared publications:
- Canzhe Zhao
Shanghai Jiao Tong University, Shanghai, China
8 shared publications - Fang Kong
Shanghai Jiao Tong University
6 shared publications Ruofeng Yang
Shanghai Jiao Tong University wanshuiyin joseph_y
5 shared publications- Tong Yu
Adobe Research, San Jose, CA, USA
5 shared publications - Zilong Wang
Shanghai Jiao Tong University
5 shared publications - Baoxiang Wang
The Chinese University of Hong Kong
4 shared publications
Latest Publications
- Open Access
- 6 November 2026
- Published by Association for Computing Machinery (ACM)
- p. 5052-5062
Anytime-Valid Multi-Objective Online Experimentation with Contrast Certificates
- 6 November 2026
- Published by Association for Computing Machinery (ACM)
- p. 5052-5062
Open AccessAnytime-Valid Multi-Objective Online Experimentation with Contrast Certificates
- Open Access
- 6 November 2026
- Published by Association for Computing Machinery (ACM)
- p. 6550-6561
FISolver: Data-Driven Discovery of First Integrals via Backward Generation and Guided Reinforcement Learning
- 6 November 2026
- Published by Association for Computing Machinery (ACM)
- p. 6550-6561
Open AccessFISolver: Data-Driven Discovery of First Integrals via Backward Generation and Guided Reinforcement Learning
- Open Access
- 8 August 2026
- Published by Association for Computing Machinery (ACM)
- p. 11843-11853
From Surface to Depth: Diagnosing Ocean Vertical Velocity with 3D Frequency Operator
- 8 August 2026
- Published by Association for Computing Machinery (ACM)
- p. 11843-11853
Open AccessFrom Surface to Depth: Diagnosing Ocean Vertical Velocity with 3D Frequency Operator
- 25 February 2026
- Published by Elsevier in Theoretical Computer Science
- Vol. 1071
Bandit learning in matching markets with relative feedback
- 25 February 2026
- Published by Elsevier in Theoretical Computer Science
- Vol. 1071
Bandit learning in matching markets with relative feedback
- Open Access
- 24 February 2026
- Published by Elsevier in SSRN Electronic Journal
Finite Sample Analysis for Single-Loop Single-Timescale Natural Actor-Critic Algorithm
Natural actor-critic (NAC) methods are widely used in reinforcement learning due to their parameterization-invariant updates and strong empirical performance. Despite this success, existing finite-time analyses largely focus on \emph{double-loop} variants (multiple critic steps per actor step) or \emph{two-timescale} variants (a much slower actor), both of which simplify analysis but deviate from practical implementations. In this paper, we study a more practical \emph{single-loop single-timescale} NAC algorithm under \emph{Markovian sampling}, where the actor, critic, and Fisher-information estimator are updated \emph{once per iteration} using \emph{a single sample}. To enable single-sample NAC, we employ an exponentially-weighted Fisher estimator that combines the previous estimate with a fresh unbiased outer-product sample.We establish finite sample guarantees under linear function approximation. With the standard single-timescale stepsizes $\alpha_t,\beta_t,\zeta_t \propto t^{-1/2}$, we prove an $\tilde O(\epsilon^{-2})$ sample complexity to reach an $\epsilon$-approximate stationary point. For \emph{global} convergence, we show that the stationary-optimal schedule is suboptimal due to a dominant \emph{bias term} that enters through a square-root in the KL-based analysis; by choosing a different (yet still single-timescale) schedule $\alpha_t,\beta_t,\zeta_t \propto t^{-2/3}$ and developing refined coupled tracking bounds for three estimation errors, we obtain an improved $\tilde O(\epsilon^{-3})$ sample complexity for attaining an $\epsilon$-approximate globally optimal value.- 24 February 2026
- Published by Elsevier in SSRN Electronic Journal
Open AccessFinite Sample Analysis for Single-Loop Single-Timescale Natural Actor-Critic Algorithm
Natural actor-critic (NAC) methods are widely used in reinforcement learning due to their parameterization-invariant updates and strong empirical performance. Despite this success, existing finite-time analyses largely focus on \emph{double-loop} variants (multiple critic steps per actor step) or \emph{two-timescale} variants (a much slower actor), both of which simplify analysis but deviate from practical implementations. In this paper, we study a more practical \emph{single-loop single-timescale} NAC algorithm under \emph{Markovian sampling}, where the actor, critic, and Fisher-information estimator are updated \emph{once per iteration} using \emph{a single sample}. To enable single-sample NAC, we employ an exponentially-weighted Fisher estimator that combines the previous estimate with a fresh unbiased outer-product sample.We establish finite sample guarantees under linear function approximation. With the standard single-timescale stepsizes $\alpha_t,\beta_t,\zeta_t \propto t^{-1/2}$, we prove an $\tilde O(\epsilon^{-2})$ sample complexity to reach an $\epsilon$-approximate stationary point. For \emph{global} convergence, we show that the stationary-optimal schedule is suboptimal due to a dominant \emph{bias term} that enters through a square-root in the KL-based analysis; by choosing a different (yet still single-timescale) schedule $\alpha_t,\beta_t,\zeta_t \propto t^{-2/3}$ and developing refined coupled tracking bounds for three estimation errors, we obtain an improved $\tilde O(\epsilon^{-3})$ sample complexity for attaining an $\epsilon$-approximate globally optimal value. - Open Access
Multi-Subspace Multi-Modal Modeling for Diffusion Models: Estimation, Convergence and Mixture of Experts
Recently, diffusion models have achieved a great performance with a small dataset of size $n$ and a fast optimization process. However, the estimation error of diffusion models suffers from the curse of dimensionality $n^{-1/D}$ with the data dimension $D$. Since images are usually a union of low-dimensional manifolds, current works model the data as a union of linear subspaces with Gaussian latent and achieve a $1/\sqrt{n}$ bound. Though this modeling reflects the multi-manifold property, the Gaussian latent can not capture the multi-modal property of the latent manifold. To bridge this gap, we propose the mixture subspace of low-rank mixture of Gaussian (MoLR-MoG) modeling, which models the target data as a union of $K$ linear subspaces, and each subspace admits a mixture of Gaussian latent ($n_k$ modals with dimension $d_k$). With this modeling, the corresponding score function naturally has a mixture of expert (MoE) structure, captures the multi-modal information, and contains nonlinear property. We first conduct real-world experiments to show that the generation results of MoE-latent MoG NN are much better than MoE-latent Gaussian score. Furthermore, MoE-latent MoG NN achieves a comparable performance with MoE-latent Unet with $10 \times$ parameters. These results indicate that the MoLR-MoG modeling is reasonable and suitable for real-world data. After that, based on such MoE-latent MoG score, we provide a $R^4\sqrt{Σ_{k=1}^Kn_k}\sqrt{Σ_{k=1}^Kn_kd_k}/\sqrt{n}$ estimation error, which escapes the curse of dimensionality by using data structure. Finally, we study the optimization process and prove the convergence guarantee under the MoLR-MoG modeling. Combined with these results, under a setting close to real-world data, this work explains why diffusion models only require a small training sample and enjoy a fast optimization process to achieve a great performance.Open AccessMulti-Subspace Multi-Modal Modeling for Diffusion Models: Estimation, Convergence and Mixture of Experts
Recently, diffusion models have achieved a great performance with a small dataset of size $n$ and a fast optimization process. However, the estimation error of diffusion models suffers from the curse of dimensionality $n^{-1/D}$ with the data dimension $D$. Since images are usually a union of low-dimensional manifolds, current works model the data as a union of linear subspaces with Gaussian latent and achieve a $1/\sqrt{n}$ bound. Though this modeling reflects the multi-manifold property, the Gaussian latent can not capture the multi-modal property of the latent manifold. To bridge this gap, we propose the mixture subspace of low-rank mixture of Gaussian (MoLR-MoG) modeling, which models the target data as a union of $K$ linear subspaces, and each subspace admits a mixture of Gaussian latent ($n_k$ modals with dimension $d_k$). With this modeling, the corresponding score function naturally has a mixture of expert (MoE) structure, captures the multi-modal information, and contains nonlinear property. We first conduct real-world experiments to show that the generation results of MoE-latent MoG NN are much better than MoE-latent Gaussian score. Furthermore, MoE-latent MoG NN achieves a comparable performance with MoE-latent Unet with $10 \times$ parameters. These results indicate that the MoLR-MoG modeling is reasonable and suitable for real-world data. After that, based on such MoE-latent MoG score, we provide a $R^4\sqrt{Σ_{k=1}^Kn_k}\sqrt{Σ_{k=1}^Kn_kd_k}/\sqrt{n}$ estimation error, which escapes the curse of dimensionality by using data structure. Finally, we study the optimization process and prove the convergence guarantee under the MoLR-MoG modeling. Combined with these results, under a setting close to real-world data, this work explains why diffusion models only require a small training sample and enjoy a fast optimization process to achieve a great performance. - Open Access
Optimal Analysis for Bandit Learning in Matching Markets with Serial Dictatorship
The problem of two-sided matching markets is well-studied in computer science and economics, owing to its diverse applications across numerous domains. Since market participants are usually uncertain about their preferences in various online matching platforms, an emerging line of research is dedicated to the online setting where one-side participants (players) learn their unknown preferences through multiple rounds of interactions with the other side (arms). Sankararaman et al. provide an $Ω\left( \frac{N\log(T)}{Δ^2} + \frac{K\log(T)}Δ \right)$ regret lower bound for this problem under serial dictatorship assumption, where $N$ is the number of players, $K (\geq N)$ is the number of arms, $Δ$ is the minimum reward gap across players and arms, and $T$ is the time horizon. Serial dictatorship assumes arms have the same preferences, which is common in reality when one side participants have a unified evaluation standard. Recently, the work of Kong and Li proposes the ET-GS algorithm and achieves an $O\left( \frac{K\log(T)}{Δ^2} \right)$ regret upper bound, which is the best upper bound attained so far. Nonetheless, a gap between the lower and upper bounds, ranging from $N$ to $K$, persists. It remains unclear whether the lower bound or the upper bound needs to be improved. In this paper, we propose a multi-level successive selection algorithm that obtains an $O\left( \frac{N\log(T)}{Δ^2} + \frac{K\log(T)}Δ \right)$ regret bound when the market satisfies serial dictatorship. To the best of our knowledge, we are the first to propose an algorithm that matches the lower bound in the problem of matching markets with bandits.Open AccessOptimal Analysis for Bandit Learning in Matching Markets with Serial Dictatorship
The problem of two-sided matching markets is well-studied in computer science and economics, owing to its diverse applications across numerous domains. Since market participants are usually uncertain about their preferences in various online matching platforms, an emerging line of research is dedicated to the online setting where one-side participants (players) learn their unknown preferences through multiple rounds of interactions with the other side (arms). Sankararaman et al. provide an $Ω\left( \frac{N\log(T)}{Δ^2} + \frac{K\log(T)}Δ \right)$ regret lower bound for this problem under serial dictatorship assumption, where $N$ is the number of players, $K (\geq N)$ is the number of arms, $Δ$ is the minimum reward gap across players and arms, and $T$ is the time horizon. Serial dictatorship assumes arms have the same preferences, which is common in reality when one side participants have a unified evaluation standard. Recently, the work of Kong and Li proposes the ET-GS algorithm and achieves an $O\left( \frac{K\log(T)}{Δ^2} \right)$ regret upper bound, which is the best upper bound attained so far. Nonetheless, a gap between the lower and upper bounds, ranging from $N$ to $K$, persists. It remains unclear whether the lower bound or the upper bound needs to be improved. In this paper, we propose a multi-level successive selection algorithm that obtains an $O\left( \frac{N\log(T)}{Δ^2} + \frac{K\log(T)}Δ \right)$ regret bound when the market satisfies serial dictatorship. To the best of our knowledge, we are the first to propose an algorithm that matches the lower bound in the problem of matching markets with bandits. - Open Access
Decentralized Asynchronous Multi-player Bandits
In recent years, multi-player multi-armed bandits (MP-MAB) have been extensively studied due to their wide applications in cognitive radio networks and Internet of Things systems. While most existing research on MP-MAB focuses on synchronized settings, real-world systems are often decentralized and asynchronous, where players may enter or leave the system at arbitrary times, and do not have a global clock. This decentralized asynchronous setting introduces two major challenges. First, without a global time, players cannot implicitly coordinate their actions through time, making it difficult to avoid collisions. Second, it is important to detect how many players are in the system, but doing so may cost a lot. In this paper, we address the challenges posed by such a fully asynchronous setting in a decentralized environment. We develop a novel algorithm in which players adaptively change between exploration and exploitation. During exploration, players uniformly pull their arms, reducing the probability of collisions and effectively mitigating the first challenge. Meanwhile, players continue pulling arms currently exploited by others with a small probability, enabling them to detect when a player has left, thereby addressing the second challenge. We prove that our algorithm achieves a regret of $\mathcal{O}(\sqrt{T \log T} + {\log T}/{Δ^2})$, where $Δ$ is the minimum expected reward gap between any two arms. To the best of our knowledge, this is the first efficient MP-MAB algorithm in the asynchronous and decentralized environment. Extensive experiments further validate the effectiveness and robustness of our algorithm, demonstrating its applicability to real-world scenarios.Open AccessDecentralized Asynchronous Multi-player Bandits
In recent years, multi-player multi-armed bandits (MP-MAB) have been extensively studied due to their wide applications in cognitive radio networks and Internet of Things systems. While most existing research on MP-MAB focuses on synchronized settings, real-world systems are often decentralized and asynchronous, where players may enter or leave the system at arbitrary times, and do not have a global clock. This decentralized asynchronous setting introduces two major challenges. First, without a global time, players cannot implicitly coordinate their actions through time, making it difficult to avoid collisions. Second, it is important to detect how many players are in the system, but doing so may cost a lot. In this paper, we address the challenges posed by such a fully asynchronous setting in a decentralized environment. We develop a novel algorithm in which players adaptively change between exploration and exploitation. During exploration, players uniformly pull their arms, reducing the probability of collisions and effectively mitigating the first challenge. Meanwhile, players continue pulling arms currently exploited by others with a small probability, enabling them to detect when a player has left, thereby addressing the second challenge. We prove that our algorithm achieves a regret of $\mathcal{O}(\sqrt{T \log T} + {\log T}/{Δ^2})$, where $Δ$ is the minimum expected reward gap between any two arms. To the best of our knowledge, this is the first efficient MP-MAB algorithm in the asynchronous and decentralized environment. Extensive experiments further validate the effectiveness and robustness of our algorithm, demonstrating its applicability to real-world scenarios. - Open Access
- 1 September 2025
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 8, 6552-6560
Fast Second-Order Online Kernel Learning Through Incremental Matrix Sketching and Decomposition
Second-order Online Kernel Learning (OKL) has attracted considerable research interest due to its promising predictive performance in streaming environments. However, existing second-order OKL approaches suffer from at least quadratic time complexity with respect to the pre-set budget, rendering them unsuitable for large-scale datasets. Moreover, the singular value decomposition required to obtain explicit feature mapping is computationally expensive due to the complete decomposition process. To address these issues, we propose FORKS, a fast incremental matrix sketching and decomposition approach tailored for second-order OKL. FORKS constructs an incremental maintenance paradigm for second-order kernelized gradient descent, which includes incremental matrix sketching for kernel approximation and incremental matrix decomposition for explicit feature mapping construction. Theoretical analysis demonstrates that FORKS achieves a logarithmic regret guarantee on par with other second-order approaches while maintaining a linear time complexity w.r.t. the budget, significantly enhancing efficiency over existing methods. We validate the performance of our method through extensive experiments conducted on real-world datasets, demonstrating its superior scalability and robustness against adversarial attacks.
- 1 September 2025
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 8, 6552-6560
Open AccessFast Second-Order Online Kernel Learning Through Incremental Matrix Sketching and Decomposition
Second-order Online Kernel Learning (OKL) has attracted considerable research interest due to its promising predictive performance in streaming environments. However, existing second-order OKL approaches suffer from at least quadratic time complexity with respect to the pre-set budget, rendering them unsuitable for large-scale datasets. Moreover, the singular value decomposition required to obtain explicit feature mapping is computationally expensive due to the complete decomposition process. To address these issues, we propose FORKS, a fast incremental matrix sketching and decomposition approach tailored for second-order OKL. FORKS constructs an incremental maintenance paradigm for second-order kernelized gradient descent, which includes incremental matrix sketching for kernel approximation and incremental matrix decomposition for explicit feature mapping construction. Theoretical analysis demonstrates that FORKS achieves a logarithmic regret guarantee on par with other second-order approaches while maintaining a linear time complexity w.r.t. the budget, significantly enhancing efficiency over existing methods. We validate the performance of our method through extensive experiments conducted on real-world datasets, demonstrating its superior scalability and robustness against adversarial attacks.
- Open Access
- 1 September 2025
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 6, 5065-5073
Multi-player Multi-armed Bandits with Delayed Feedback
Multi-player multi-armed bandits (MP-MAB) have been extensively studied due to their application in cognitive radio networks. In this setting, multiple players simultaneously select arms and instantly receive feedback. However, in realistic decentralized networks, feedback is often delayed due to sensing latency and signal processing. Without a central coordinator, explicit communication is impossible, and delayed feedback disrupts implicit coordination, since it depends on synchronous observations. As a result, collisions are frequent and system performance degrades significantly. In this paper, we propose an algorithm in MP-MAB with stochastic delay feedback. Each player in the algorithm independently maintains an estimate of the optimal arm set based on their own delayed rewards but only pulls arms from the set, which is, with high probability, identical to those of other players, thus avoiding collisions. The identical arm set also enables implicit communication, allowing players to utilize the exploration results of others. We establish a regret upper bound and derive a lower bound to prove the algorithm is near-optimal. Numerical experiments on both synthetic and real-world datasets validate the effectiveness of our algorithm.
- 1 September 2025
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 6, 5065-5073
Open AccessMulti-player Multi-armed Bandits with Delayed Feedback
Multi-player multi-armed bandits (MP-MAB) have been extensively studied due to their application in cognitive radio networks. In this setting, multiple players simultaneously select arms and instantly receive feedback. However, in realistic decentralized networks, feedback is often delayed due to sensing latency and signal processing. Without a central coordinator, explicit communication is impossible, and delayed feedback disrupts implicit coordination, since it depends on synchronous observations. As a result, collisions are frequent and system performance degrades significantly. In this paper, we propose an algorithm in MP-MAB with stochastic delay feedback. Each player in the algorithm independently maintains an estimate of the optimal arm set based on their own delayed rewards but only pulls arms from the set, which is, with high probability, identical to those of other players, thus avoiding collisions. The identical arm set also enables implicit communication, allowing players to utilize the exploration results of others. We establish a regret upper bound and derive a lower bound to prove the algorithm is near-optimal. Numerical experiments on both synthetic and real-world datasets validate the effectiveness of our algorithm.