Model-Based Reinforcement Learning Exploiting State-Action Equivalence
  Leveraging an equivalence property in the state-space of a Markov Decision
Process (MDP) has been investigated in several studies. This paper studies
equivalence structure in the reinforcement learning (RL) setup, where
transition distributions are no longer assumed to be known. We present a notion
of similarity between transition probabilities of various state-action pairs of
an MDP, which naturally defines an equivalence structure in the state-action
space. We present equivalence-aware confidence sets for the case where the
learner knows the underlying structure in advance. These sets are provably
smaller than their corresponding equivalence-oblivious counterparts. In the
more challenging case of an unknown equivalence structure, we present an
algorithm called ApproxEquivalence that seeks to find an (approximate)
equivalence structure, and define confidence sets using the approximate
equivalence. To illustrate the efficacy of the presented confidence sets, we
present C-UCRL, as a natural modification of UCRL2 for RL in undiscounted MDPs.
In the case of a known equivalence structure, we show that C-UCRL improves over
UCRL2 in terms of regret by a factor of $\sqrt{SA/C}$, in any communicating MDP
with $S$ states, $A$ actions, and $C$ classes, which corresponds to a massive
improvement when $C \ll SA$. To the best of our knowledge, this is the first
work providing regret bounds for RL when an equivalence structure in the MDP is
efficiently exploited. In the case of an unknown equivalence structure, we show
through numerical experiments that C-UCRL combined with ApproxEquivalence
outperforms UCRL2 in ergodic MDPs.
