Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learning.
Yuanzhi LiRuosong WangLin F. YangPublished in: FOCS (2021)
Keyphrases
- sample complexity
- reinforcement learning
- learning problems
- learning algorithm
- supervised learning
- theoretical analysis
- pac learning
- vc dimension
- active learning
- sequential decision problems
- generalization error
- upper bound
- special case
- pac learnability
- state space
- optimal policy
- number of irrelevant features
- lower bound
- machine learning
- sample complexity bounds
- learning process
- sample size
- training examples
- multi agent
- partially observable markov decision processes
- learning tasks
- average case
- concept classes
- irrelevant features
- markov decision processes
- high dimensional
- cross validation