Commit to the Bit: Reactive Reinforcement Learning Done Right

Onno Eberhard, Claire Vernade, Michael Muehlebach
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:27503-27520, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-eberhard26b, title = {Commit to the Bit: Reactive Reinforcement Learning Done Right}, author = {Eberhard, Onno and Vernade, Claire and Muehlebach, Michael}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {27503--27520}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/eberhard26b/eberhard26b.pdf}, url = {https://proceedings.mlr.press/v306/eberhard26b.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Commit to the Bit: Reactive Reinforcement Learning Done Right %A Onno Eberhard %A Claire Vernade %A Michael Muehlebach %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-eberhard26b %I PMLR %P 27503--27520 %U https://proceedings.mlr.press/v306/eberhard26b.html %V 306 %X 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.
APA
Eberhard, O., Vernade, C. & Muehlebach, M.. (2026). Commit to the Bit: Reactive Reinforcement Learning Done Right. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:27503-27520 Available from https://proceedings.mlr.press/v306/eberhard26b.html.

Related Material