  We address the problem of reinforcement learning in which observations may
exhibit an arbitrary form of stochastic dependence on past observations and
actions, i.e. environments more general than (PO)MDPs. 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.
