  We address the problem of reinforcement learning in which observations may
exhibit an arbitrary form of stochastic dependence on past observations and
actions. The task for an agent is to attain the best possible asymptotic reward
where the true generating environment is unknown but belongs to a known
countable family of environments. We find some sufficient conditions on the
class of environments under which an agent exists which attains the best
asymptotic reward for any environment in the class. We analyze how tight these
conditions are and how they relate to different probabilistic assumptions known
in reinforcement learning and related fields, such as Markov Decision Processes
and mixing conditions.
