On the Convergence of Bounded Agents
David Abel André Barreto Hado van Hasselt Benjamin Van Roy Doina Precup Satinder Singh
When has an agent converged? Standard models of the reinforcement learning
problem give rise to a straightforward definition of convergence: An agent
converges when its behavior or performance in each environment state stops
changing. However, as we shift the focus of our learning problem from the
environment's state to the agent's state, the concept of an agent's convergence
becomes significantly less clear. In this paper, we propose two complementary
accounts of agent convergence in a framing of the reinforcement learning
problem that centers around bounded agents. The first view says that a bounded
agent has converged when the minimal number of states needed to describe the
agent's future behavior cannot decrease. The second view says that a bounded
agent has converged just when the agent's performance only changes if the
agent's internal state changes. We establish basic properties of these two
definitions, show that they accommodate typical views of convergence in
standard settings, and prove several facts about their nature and relationship.
We take these perspectives, definitions, and analysis to bring clarity to a
central idea of the field.