Commit to the Bit: Reactive Reinforcement Learning Done Right
This work provides a theoretically grounded algorithm for reinforcement learning in non-Markovian environments with deterministic observations, addressing a practical limitation of standard RL methods.
The paper tackles the problem of learning optimal reactive policies in environments with deterministic observations (hard state aggregation), where the Markov assumption is violated. It introduces Committed Q-learning, which provably converges almost surely to the optimal reactive policy under a novel assumption called rewire-robustness, which is strictly weaker than prior conditions like q*-realizability.
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.