Bellman theory values multi-step transition predictions in finite MDPs
BF-BOLA learns near-optimal policies with sample bounds that match up to logarithmic factors.
Stories per day · 30 days
1 RSS
Relatedbellman1convolutional-networks1cs-cr1differential-privacy1learning-dynamics1markov-chains1mdps1reinforcement-learning1teacher-student1theory1user-level-privacy1weight-sharing1
11 stories, newest first · one card per story
Stories tagged #sample-complexity
Theory separates locality from weight sharing in convolutional learning
With uncorrelated inputs a convolutional student learns exactly P times faster, but spatial correlation can erase that edge.
Differentially Private Learning of Markov Chains: Near-Optimal Sample Complexity for Item and User Level Privacy
Researchers give near-optimal private bounds for learning Markov chain transition matrices.
Hitting-Time Bounds for Asynchronous Q-Learning
Asynchronous Q-learning reaches epsilon error with a quartic horizon term plus an additive hitting-time cost.
Best Arm Identification for Bandits with Shifting Means
ISM identifies the best arm when shared mean shifts are adversarial but gaps stay fixed.
Expected Sample Complexity in Multi-Armed Bandits
A new expected sample-complexity measure for stochastic bandits separates known and unknown suboptimality and rules out deterministic algorithms.
Provable Benefits of Regularization: Fast Rates for Adversarial Imitation Learning
Theory paper proves fast finite-sample rates for dually regularized adversarial imitation learning.
When are bosonic Gaussian states classical to learn?
Cold bosonic Gaussian states need more samples to learn than classical Gaussians; warm states match.
Exponential Hardness of Off-Policy Evaluation under History-Dependent Logging
Researchers prove off-policy evaluation under history-dependent logging requires exponentially many episodes, resolving a hardness question for model-based POMDP evaluation.
A positive resolution of the gap-entropy conjecture
New proof resolves the gap-entropy conjecture for Gaussian bandits, bounding optimal best-arm identification samples by H(log(1/delta)+Ent(I)) up to constants.
The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements
Researchers derive sufficient sample-size conditions for recovering sparse binary signals from sparse Gaussian measurements, quantifying an information-theoretic threshold of order slog(p/s)/log(ds/p).