On the Sample Complexity of Reinforcement Learning with Policy Space Generalization
This work addresses the scalability issue in RL for researchers and practitioners by reducing sample complexity, though it is incremental as it builds on existing generalization models.
The paper tackles the sample complexity problem in large-scale Reinforcement Learning by introducing a new notion of eluder dimension for policy spaces, proving a near-optimal sample complexity upper bound that depends linearly on this dimension, avoiding dependence on state and action space sizes.
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.