Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper provides the first finite-sample convergence guarantees for Q-learning with options under the average-reward formulation, addressing continual tasks beyond discounted or episodic settings. The authors establish $\tilde{O}(1/\text{iterations})$ mean-square convergence rates by proving multi-step span contraction properties for both inter- and intra-option Bellman operators under unichain assumptions. They then introduce synchronous estimators for these operators, leading to two Q-learning variants whose convergence is analyzed within the stochastic approximation framework.
Average-reward option Q-learning achieves $\tilde{O}(1/\text{iterations})$ convergence, unlocking continual RL tasks previously intractable for option-based methods.
We study the finite-sample convergence of Q-learning algorithms for the average-reward formulation of Reinforcement Learning (RL) with options. While options allow temporarily extended and hierarchical actions, the average-reward formulation incorporates continual tasks beyond discounted and episodic RL. We establish the first $\tilde{O}(1/\text{iterations})$ convergence guarantees, in the mean-square sense, for average-reward option Q-learning algorithms in both the inter- and intra-option settings. First, we prove that both inter- and intra-option Bellman operators satisfy multi-step span contractions under unichain assumptions. Then, we propose synchronous estimators of these multi-step option Bellman operators leading to two variants of option Q-learning. Finally, we extend the stochastic approximation framework to prove convergence rates of these two algorithms under the minimal assumptions used in the literature.