Commit to the Bit: Reactive Reinforcement Learning Done Right

Reinforcement learning algorithms are commonly analyzed (and designed) under the Markov assumption. This is unrealistic, as most environments encountered in practice are either partially observable, or require function approximation that restricts the agent to access non-Markovian state features. We consider the problem of learning an optimal reactive policy in a finite environment with deterministic observations (or equivalently, hard state aggregation). We introduce a new algorithm, _Committed Q-learning_, and prove almost-sure convergence to the optimal reactive policy under an intuitive assumption we call _rewire-robustness_. This assumption is strictly weaker than the $q_\star$-realizability condition used in prior work. Our algorithm is a variant of classical Q-learning in which the behavior policy commits to a single action upon entering a feature, and only resamples actions when the observed feature changes. A crucial part of our analysis is the introduction of _quasi-Markov_ environments.

Most artificial intelligence agents learn by trial and error through reinforcement learning (RL), which relies heavily on a mathematical framework called dynamic programming. Dynamic programming breaks large problems down into smaller steps, allowing the agent to find the best action simply by looking one step ahead. However, classic RL and dynamic programming assume that the agent has a perfect, complete view of its surroundings. In reality, agents often have to group different situations together to save memory. This creates a flaw: the grouped situations might look identical to the agents but have completely different properties, which breaks the standard theory and algorithms. This paper introduces a new RL algorithm called Committed Q-learning to fix this. The agent is programmed to commit to a single plan of action whenever it enters a grouped category, only changing its strategy when its surroundings visibly shift. We prove that this simple commitment allows dynamic programming to work perfectly within RL under a much wider, more realistic range of conditions than previously thought possible.