Guarantees for Epsilon-Greedy Reinforcement Learning with Function Approximation
Myopic exploration policies such as epsilon-greedy, softmax, or Gaussian
noise fail to explore efficiently in some reinforcement learning tasks and yet,
they perform well in many others. In fact, in practice, they are often selected
as the top choices, due to their simplicity. But, for what tasks do such
policies succeed? Can we give theoretical guarantees for their favorable
performance? These crucial questions have been scarcely investigated, despite
the prominent practical importance of these policies. This paper presents a
theoretical analysis of such policies and provides the first regret and
sample-complexity bounds for reinforcement learning with myopic exploration.
Our results apply to value-function-based algorithms in episodic MDPs with
bounded Bellman Eluder dimension. We propose a new complexity measure called
myopic exploration gap, denoted by alpha, that captures a structural property
of the MDP, the exploration policy and the given value function class. We show
that the sample-complexity of myopic exploration scales quadratically with the
inverse of this quantity, 1 / alpha^2. We further demonstrate through concrete
examples that myopic exploration gap is indeed favorable in several tasks where
myopic exploration succeeds, due to the corresponding dynamics and reward
structure.