  The Exploration-Exploitation tradeoff arises in Reinforcement Learning when
one cannot tell if a policy is optimal. Then, there is a constant need to
explore new actions instead of exploiting past experience. In practice, it is
common to resolve the tradeoff by using a fixed exploration mechanism, such as
$\epsilon$-greedy exploration or by adding Gaussian noise, while still trying
to learn an optimal policy. In this work, we take a different approach and
study exploration-conscious criteria, that result in optimal policies with
respect to the exploration mechanism. Solving these criteria, as we establish,
amounts to solving a surrogate Markov Decision Process. We continue and analyze
properties of exploration-conscious optimal policies and characterize two
general approaches to solve such criteria. Building on the approaches, we apply
simple changes in existing tabular and deep Reinforcement Learning algorithms
and empirically demonstrate superior performance relatively to their
non-exploration-conscious counterparts, both for discrete and continuous action
spaces.
