Tag
This paper proposes a noisy expert model to explain the gap between offline and online imitation learning, showing that offline learning from noisy trajectories requires exponential sample complexity while online on-policy distillation achieves polynomial dependence. The analysis leads to an alternative loss function and experiments confirm the theoretical findings.
This paper develops a Fourier analysis framework to study data augmentation under group invariances, showing that partial augmentation can achieve the same minimax rates as full augmentation up to a vanishing approximation error, while also proving that exact invariance requires full group averaging.
This paper demonstrates that two-layer neural networks trained with gradient-based methods can achieve the optimal computational-statistical tradeoff for learning Gaussian single-index models, matching the SQ lower bound up to polylogarithmic factors for all generative exponents and extending to sparse settings with a novel weight perturbation technique.
This paper develops a statistical theory for offline reinforcement learning from trajectory-level outcome supervision, proposing the OPAC algorithm and characterizing when such supervision enables efficient learning versus when fundamental barriers arise.
This paper studies the sample complexity of learning in average-reward weakly-coupled MDPs and restless bandits, establishing finite-sample PAC guarantees with polynomial complexity using a novel Lyapunov-based analysis framework.
This paper empirically measures the symmetry–data exchange rate predicted by equivariance theory, finding that wrong-group symmetry constraints are actively harmful, augmentation with test-time orbit averaging matches equivariant architectures, and the theoretical |G|-fold sample complexity reduction is only weakly confirmed with wide confidence intervals. The study is explicitly exploratory and not pre-registered.
This paper proves that learning by predicting latent representations (as in world models like JEPA and data2vec) requires exponentially less data than predicting tokens (as in LLMs) for hierarchical data with hidden structure.
This exploratory study empirically measures the symmetry–data exchange rate predicted by equivariance theory on controlled C_n-symmetric tasks, finding that wrong-group constraints are actively harmful, augmentation with test-time orbit averaging matches equivariant models exactly, and the empirical exchange rate is broadly consistent with theory but statistically inconclusive. The authors emphasize the study's exploratory nature and call for registered replications.
This paper provides a refined theoretical analysis of actor-critic methods with entropy regularization, showing that an exact critic acts as a strong variance reducer and enables sample complexity comparable to deterministic policy gradient, and that with a sufficiently accurate learned critic the benefits are preserved.
This paper introduces Good Policy Identification (GPI) in reinforcement learning, aiming to find a policy meeting a reward threshold rather than the optimal one, and proposes the BEE-GPI algorithm with near-optimal sample complexity guarantees.
This paper studies risk-sensitive reinforcement learning in finite discounted MDPs with a generative model, focusing on the sample complexity of learning optimal value functions and policies under the optimized certainty equivalent (OCE) risk measure. It provides exact conditions for PAC-learnability, analyzes a model-based approach, and establishes tight lower bounds, including an improved dependence on the risk parameter for CVaR.
This paper provides the first non-asymptotic sample complexity bounds for learning exponential families of polynomials with score matching, showing polynomial dependence on model dimension.