Technical Summary: Commit to the Bit: Reactive Reinforcement Learning Done Right

1. Problem Statement

Reinforcement learning (RL) algorithms are traditionally designed and analyzed under the Markov assumption, where the agent has full access to the state. However, practical environments are often partially observable (POMDPs) or require function approximation that restricts the agent to non-Markovian state features (hard state aggregation). In such settings, the agent must learn a reactive policy—a mapping from observed features to action distributions (options)—without memory of past observations.

Existing theoretical results for learning optimal reactive policies under hard state aggregation typically rely on the $q^\star$-realizability assumption. This condition requires that the optimal action-value function $q^\star(x, u)$ be constant within each feature (i.e., $q^\star(x, u) = q(\phi(x), u)$). The authors argue this assumption is overly restrictive, excluding simple environments (like the "corridor" example) where an optimal reactive policy exists but the underlying states within a feature have different optimal values. Furthermore, standard Q-learning fails in these scenarios because it attempts to approximate a value function that is ambiguous within the aggregated feature.

The paper addresses the problem of learning an optimal reactive policy in finite, episodic POMDPs with deterministic observations, aiming to relax the realizability assumptions required for convergence.

2. Methodology

Committed Q-learning

The authors propose Committed Q-learning, a variant of classical Q-learning. The core mechanism is a "commitment" strategy:

• Upon entering a feature $z$, the behavior policy samples a single option (action distribution) $\omega$.
• The agent commits to this option and executes it until the observed feature changes ($z' \neq z$).
• Only when the feature changes does the agent resample a new option.
• The Q-values $Q(z, \omega)$ are updated based on the transition from feature $z$ to $z'$.

This contrasts with non-committed Q-learning, which might resample actions at every time step regardless of feature stability. The commitment ensures that the learning process operates on the timescale of feature transitions rather than raw state transitions.

Theoretical Framework: Quasi-Markov Environments and Rewire-Robustness

To analyze convergence, the authors introduce two key concepts:

1. Quasi-Markov Environments: An environment is quasi-Markov if, for every feature, there is a unique distribution over entrance states (or a unique entrance state). In such environments, the Markov property holds between features: the state distribution upon entering a feature is independent of the previous feature. The authors show that in quasi-Markov environments, the optimal value for a feature corresponds to the value of its entrance state, allowing dynamic programming to work correctly.

2. Rewire-Robustness: This is the central contribution of the paper. An environment is rewire-robust if the optimal reactive policy remains unchanged under any "rewiring" of the environment. A rewiring modifies the "entrance dynamics" (how a feature is entered) while keeping the internal dynamics of the feature and the feature transition probabilities invariant.

   • Generalized Rewiring: Allows arbitrary changes to entrance distributions.
   • $\pi$-Rewiring: A specific type of rewiring where entrance distributions are replaced by the "average" entrance distribution induced by the behavior policy $\pi$.

The authors define Bellman Risk and Value Risk as learnable objectives (unlike Bellman Error or Value Error in partially observable settings) and show that minimizing Bellman Risk in a quasi-Markov environment yields the correct entrance values.

3. Key Contributions

• Committed Q-learning Algorithm: An algorithm that provably converges to the optimal reactive policy under a strictly weaker assumption than prior work.
• Rewire-Robustness Condition: The introduction of a new assumption for state aggregation. The paper proves that rewire-robustness is strictly weaker than $q^\star$-realizability. This means the algorithm converges in a broader class of environments, including those where the optimal value function is not constant within a feature (e.g., the corridor environment).
• Quasi-Markov Formalism: A rigorous definition of quasi-Markov environments and the associated aggregate MDP, which serves as the theoretical bridge between the partially observable environment and the learning algorithm.
• Convergence Proof: Using an extension of the Borkar-Meyn theorem to Markovian noise (Liu et al., 2025), the authors prove that Committed Q-learning converges almost surely to the optimal reactive policy in any rewire-robust environment.

4. Results

• Convergence: The iterates $(Q_t)$ of Committed Q-learning converge almost surely to a solution $Q^\star$. The greedy policy derived from $Q^\star$ is optimal in the environment if the environment is rewire-robust.
• Hierarchy of Assumptions: The paper establishes a strict hierarchy of assumptions:
  • $q^\star$-realizability $\implies$ Generalized rewire-robustness $\implies$ Rewire-robustness.
  • The converse implications do not hold. Specifically, the corridor environment is rewire-robust but not $q^\star$-realizable.
• Empirical Validation: Numerical experiments in the corridor environment demonstrate that while regular Q-learning fails to make progress, Committed Q-learning quickly converges to the optimal policy across various corridor lengths.

5. Significance and Claims

The paper claims that Committed Q-learning provides a theoretically grounded solution for reactive reinforcement learning in partially observable environments without requiring the strong $q^\star$-realizability assumption.

• Relaxing Assumptions: By introducing rewire-robustness, the work expands the class of environments where optimal reactive policies can be learned. The authors note that finding an optimal reactive policy under state aggregation is generally NP-complete (Littman, 1994), making such assumptions necessary for efficient algorithms; however, this work identifies the weakest known assumption for convergence.
• Interpretability: The algorithm operates on a "higher level" (the feature space) effectively solving an aggregate MDP. The "commitment" mechanism is not a restriction but a natural alignment with the goal of finding a reactive policy that maps features to options.
• Learnability: The paper clarifies that standard error metrics (Value Error, Bellman Error) are not learnable in partially observable settings because they depend on unobservable state distributions. In contrast, the proposed Bellman Risk is learnable from observed features and rewards, providing a solid foundation for the convergence analysis.

The authors conclude that their approach offers a robust framework for reactive RL, bridging the gap between the theoretical limitations of state aggregation and the practical need for memory-less policies in complex environments. Future work is suggested to extend these results to non-stationary options, infinite-horizon discounted problems, and approximate rewire-robustness.