On the Sample Complexity of Reinforcement Learning with Policy Space Generalization
arXiv:2008.07353
Abstract
We study the optimal sample complexity in large-scale Reinforcement Learning (RL) problems with policy space generalization, i.e. the agent has a prior knowledge that the optimal policy lies in a known policy space. Existing results show that without a generalization model, the sample complexity of an RL algorithm will inevitably depend on the cardinalities of state space and action space, which are intractably large in many practical problems. To avoid such undesirable dependence on the state and action space sizes, this paper proposes a new notion of eluder dimension for the policy space, which characterizes the intrinsic complexity of policy learning in an arbitrary Markov Decision Process (MDP). Using a simulator oracle, we prove a near-optimal sample complexity upper bound that only depends linearly on the eluder dimension. We further prove a similar regret bound in deterministic systems without the simulator.
References in corpus (10)
- Continuous control with deep reinforcement learning
- Trust Region Policy Optimization
- Noisy Networks for Exploration
- Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
- On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
- Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches
- Provably Efficient -learning with Function Approximation via Distribution Shift Error Checking Oracle
- Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
- Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity
- Reinforcement Learning Upside Down: Don't Predict Rewards -- Just Map Them to Actions