  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.
