Issues concerning realizability of Blackwell optimal policies in
  reinforcement learning
  N-discount optimality was introduced as a hierarchical form of policy- and
value-function optimality, with Blackwell optimality lying at the top level of
the hierarchy Veinott (1969); Blackwell (1962). We formalize notions of myopic
discount factors, value functions and policies in terms of Blackwell optimality
in MDPs, and we provide a novel concept of regret, called Blackwell regret,
which measures the regret compared to a Blackwell optimal policy. Our main
analysis focuses on long horizon MDPs with sparse rewards. We show that
selecting the discount factor under which zero Blackwell regret can be achieved
becomes arbitrarily hard. Moreover, even with oracle knowledge of such a
discount factor that can realize a Blackwell regret-free value function, an
$\epsilon$-Blackwell optimal value function may not even be gain optimal.
Difficulties associated with this class of problems is discussed, and the
notion of a policy gap is defined as the difference in expected return between
a given policy and any other policy that differs at that state; we prove
certain properties related to this gap. Finally, we provide experimental
results that further support our theoretical results.
