Search papers, labs, and topics across Lattice.
This paper introduces Committed Q-learning, a novel reinforcement learning algorithm designed for finite environments with deterministic observations where the Markov assumption does not hold. The algorithm commits to a single action upon entering a feature and resamples only when the observed feature changes. The authors prove almost-sure convergence to the optimal reactive policy under a new, weaker assumption called rewire-robustness, and introduce the concept of quasi-Markov environments for analysis.
Q-learning can provably converge to optimal policies in non-Markovian environments, even with hard state aggregation, using a simple action-commitment strategy.
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.
