Yuting Wei

Yuting Wei

Auto-generated profile, based on publicly available information

Yuting Wei

Department of Statistics and Data Science, Wharton School, University of Pennsylvania, Philadelphia, Pennsylvania 19104

Research Focus & Metrics

Academic Career Length

7Years (2020-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
14 October 2021 in IEEE Transactions on Information Theory
Verified
Journal Article
Open access
GLGen Li
Gen Li
YWYuting Wei
Yuting Wei
YCYuejie Chi
Yuejie Chi
YGYuantao Gu
Yuantao Gu
YCYuxin Chen
Yuxin Chen
Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP), based on a single trajectory of Markovian samples induced by a behavior policy. Focusing on a $\gamma $ -discounted MDP with state space $\mathcal {S}$ and action space $\mathcal {A}$ , we demonstrate that the $\ell _{\infty }$ -based sample complexity of classical asynchronous Q-learning — namely, the number of samples needed to yield an entrywise $\varepsilon $ -accurate estimate of the Q-function — is at most on the order of $\frac {1}{ \mu _{\mathsf {min}}(1-\gamma)^{5}\varepsilon ^{2}}+ \frac { t_{\mathsf {mix}}}{ \mu _{\mathsf {min}}(1-\gamma)}$ up to some logarithmic factor, provided that a proper constant learning rate is adopted. Here, $t_{\mathsf {mix}}$ and $\mu _{\mathsf {min}}$ denote respectively the mixing time and the minimum state-action occupancy probability of the sample trajectory. The first term of this bound matches the sample complexity in the synchronous case with independent samples drawn from the stationary distribution of the trajectory. The second term reflects the cost taken for the empirical distribution of the Markovian trajectory to reach a steady state, which is incurred at the very beginning and becomes amortized as the algorithm runs. Encouragingly, the above bound improves upon the state-of-the-art result by a factor of at least $|\mathcal {S}||\mathcal {A}|$ for all scenarios, and by a factor of at least $t_{\mathsf {mix}}|\mathcal {S}||\mathcal {A}|$ for any sufficiently small accuracy level $\varepsilon $ . Further, we demonstrate that the scaling on the effective horizon $\frac {1}{1-\gamma }$ can be improved by means of variance reduction.

1 January 2024 in Operations Research
Verified
Journal Article
Closed access
GLGen Li
Gen Li
CCChangxiao Cai
Changxiao Cai
YCYuxin Chen
Yuxin Chen
YWYuting Wei
Yuting Wei
YCYuejie Chi
Yuejie Chi
This paper investigates a model-free algorithm of broad interest in reinforcement learning, namely, Q-learning. Whereas substantial progress had been made toward understanding the sample efficiency of Q-learning in recent years, it remained largely unclear whether Q-learning is sample-optimal and how to sharpen the sample complexity analysis of Q-learning. In this paper, we settle these questions: (1) When there is only a single action, we show that Q-learning (or, equivalently, TD learning) is provably minimax optimal. (2) When there are at least two actions, our theory unveils the strict suboptimality of Q-learning and rigorizes the negative impact of overestimation in Q-learning. Our theory accommodates both the synchronous case (i.e., the case in which independent samples are drawn) and the asynchronous case (i.e., the case in which one only has access to a single Markovian trajectory).

1 January 2024 in Operations Research
Verified
Journal Article
Closed access
GLGen Li
Gen Li
YWYuting Wei
Yuting Wei
YCYuejie Chi
Yuejie Chi
YCYuxin Chen
Yuxin Chen
This paper studies a central issue in modern reinforcement learning, the sample efficiency, and makes progress toward solving an idealistic scenario that assumes access to a generative model or a simulator. Despite a large number of prior works tackling this problem, a complete picture of the trade-offs between sample complexity and statistical accuracy has yet to be determined. In particular, all prior results suffer from a severe sample size barrier in the sense that their claimed statistical guarantees hold only when the sample size exceeds some enormous threshold. The current paper overcomes this barrier and fully settles this problem; more specifically, we establish the minimax optimality of the model-based approach for any given target accuracy level. To the best of our knowledge, this work delivers the first minimax-optimal guarantees that accommodate the entire range of sample sizes (beyond which finding a meaningful policy is information theoretically infeasible).

25 July 2023 in Proceedings of the National Academy of Sciences
Verified
Journal Article
Open access
GLGen Li
Gen Li
WFWei Fan
Wei Fan
YWYuting Wei
Yuting Wei
This paper is concerned with the problem of reconstructing an unknown rank-one matrix with prior structural information from noisy observations. While computing the Bayes optimal estimator is intractable in general due to the requirement of computing high-dimensional integrations/summations, Approximate Message Passing (AMP) emerges as an efficient first-order method to approximate the Bayes optimal estimator. However, the theoretical underpinnings of AMP remain largely unavailable when it starts from random initialization, a scheme of critical practical utility. Focusing on a prototypical model called Z 2 synchronization, we characterize the finite-sample dynamics of AMP from random initialization, uncovering its rapid global convergence. Our theory—which is nonasymptotic in nature—in this model unveils the non-necessity of a careful initialization for the success of AMP.

10 September 2021 in IEEE Transactions on Information Theory
Verified
Journal Article
Open access
CCChen Cheng
Chen Cheng
YWYuting Wei
Yuting Wei
YCYuxin Chen
Yuxin Chen
This paper aims to address two fundamental challenges arising in eigenvector estimation and inference for a low-rank matrix from noisy observations: 1) how to estimate an unknown eigenvector when the eigen-gap (i.e. the spacing between the associated eigenvalue and the rest of the spectrum) is particularly small; 2) how to perform estimation and inference on linear functionals of an eigenvector—a sort of “fine-grained” statistical reasoning that goes far beyond the usual $\ell _{2}$ analysis. We investigate how to address these challenges in a setting where the unknown $n\times n$ matrix is symmetric and the additive noise matrix contains independent (and non-symmetric) entries. Based on eigen-decomposition of the asymmetric data matrix, we propose estimation and uncertainty quantification procedures for an unknown eigenvector, which further allow us to reason about linear functionals of an unknown eigenvector. The proposed procedures and the accompanying theory enjoy several important features: 1) distribution-free (i.e. prior knowledge about the noise distributions is not needed); 2) adaptive to heteroscedastic noise; 3) minimax optimal under Gaussian noise. Along the way, we establish valid procedures to construct confidence intervals for the unknown eigenvalues. All this is guaranteed even in the presence of a small eigen-gap (up to $O(\sqrt {n/\mathrm {poly}\log (n)}\,)$ times smaller than the requirement in prior theory), which goes significantly beyond what generic matrix perturbation theory has to offer.

17 March 2020 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
YWYuting Wei
Yuting Wei
MWMartin J. Wainwright
Martin J. Wainwright
Mean testing over ellipses is a decision problem that arises in several applications, including non-parametric goodness-of-fit testing, signal detection in cognitive radio, and regression function testing in reproducing kernel Hilbert spaces. We study the local geometry of such testing problems with compound alternatives. Given samples of a Gaussian random vector, the goal is to distinguish whether the mean is equal to a known vector within an ellipse, or equal to some other unknown vector in the ellipse. While past work on such problems has focused on the difficulty in a global sense, we study difficulty in a way that is localized to each vector within the ellipse. Our main result is to give sharp upper and lower bounds on the localized minimax testing radius in terms of an explicit formula involving the Kolmogorov width of the ellipse intersected with a Euclidean ball. When applied to particular examples, our general theorems yield interesting rates that were not known before: as a particular case, for testing in Sobolev ellipses of smoothness α, we demonstrate rates that vary from (σ2)4α4α+1, corresponding to the classical global rate, to the faster rate (σ2)8α8α+1, achievable for vectors at favorable locations within the ellipse. We also show that the optimal test for this problem is achieved by a linear projection test that is based on an explicit lower-dimensional projection of the observation vector.