← Back to papers
2006 NIPS NeurIPS 2006

Sample Complexity of Policy Search with Known Dynamics

Abstract

We consider methods that try to find a good policy for a Markov decision process by choosing one from a given class. The policy is chosen based on its empirical performance in simulations. We are interested in conditions on the complexity of the policy class that ensure the success of such simulation based policy search methods. We show that under bounds on the amount of computation involved in computing policies, transition dynamics and rewards, uniform convergence of empirical estimates to true value functions occurs. Previously, such results were derived by assuming boundedness of pseudodimension and Lipschitz continuity. These assumptions and ours are both stronger than the usual combinatorial complexity measures. We show, via minimax inequalities, that this is essential: boundedness of pseudodimension or fat-shattering dimension alone is not sufficient.

🚀 Conference Pioneer — NIPS 2006
🌉 Interdisciplinary Bridge — Machine Learning and Reinforcement Learning
📈 Trend Setter — Policy Learning
🧭 Keyword Pioneer — policy search
🐣 Hot Topic Early Bird — reinforcement learning
🐝 Cross-Pollinator — Artificial Intelligence, Computer Science, Computer Vision, Data Science & Analytics, Deep Learning, Healthcare & Medicine, Interdisciplinary, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning, Robotics
🌱 Topic Pioneer — Sample Complexity

Authors

Peter L. Bartlett , Ambuj Tewari

Topics

Machine Learning > Optimization & Theory > Learning Theory Reinforcement Learning > Methods > Policy Learning Machine Learning > Learning Types > Reinforcement Learning Machine Learning > Optimization & Theory > Sample Complexity

Keywords

reinforcement learning sample complexity markov decision process value function policy search uniform convergence
Download PDF

Related papers

Temporal Coding using the Response Properties of Spiking Neurons 2006
Parameter Expanded Variational Bayesian Methods 2006
Effects of Stress and Genotype on Meta-parameter Dynamics in Reinforcement Learning 2006
Ordinal Regression by Extended Binary Classification 2006
Blind source separation for over-determined delayed mixtures 2006