In the field of Reinforcement Learning (RL), agents are often taught to think in terms of "options"—high-level temporal abstractions like "open the door" or "navigate the hallway," rather than just primitive actions like "move left" or "move right." While this options framework is well-established for episodic tasks where rewards are discounted over time, it has remained surprisingly underdeveloped for average-reward settings. These are scenarios where an agent operates indefinitely in a continuing environment, aiming to maximize its long-term rate of reward.
Research by Yi Wan, Abhishek Naik, and Richard Sutton bridges this gap, providing a robust theoretical and algorithmic foundation for learning and planning with options in the average-reward formulation.
The Problem: Discounted vs. Average-Reward Settings
Historically, most RL research has focused on discounted returns, where immediate rewards are weighted more heavily than future ones. While mathematically convenient for episodic tasks that eventually terminate, discounting becomes problematic in "continuing" tasks—especially when paired with function approximation. In non-terminating environments, the "average-reward" formulation is often more robust and physically meaningful.
However, the options framework was originally built for the discounted setting. Previous attempts to adapt options to average-reward RL were either unstable or relied on restrictive assumptions, such as requiring the environment to have a "special state" that the agent visits infinitely often. This left a clear gap: the field lacked a general, stable method for agents to learn high-level behaviors in continuing, non-episodic worlds.
Methodology: Extending Temporal Abstractions
To solve this, the authors propose several new algorithms that extend Differential Q-learning to handle temporal abstractions:
- Inter-option Learning: These algorithms update the agent's knowledge only after an option has finished executing. A major historical challenge here was instability caused by scaling updates based on the actual time an option took, which can be highly noisy. The authors' key innovation is scaling updates by the estimated expected length of the option instead, achieving mathematical convergence and stability.
- Intra-option Learning: These are more efficient algorithms that update the values of all possible options after every single primitive action. Because they utilize off-policy importance sampling, an agent can learn about a "go to the door" option even while it is actively executing a "clean the floor" option.
- Model Learning: The authors derive new Bellman equations for average-reward option models. This allows an agent to learn a "mental map" of how long an option takes, how much reward it yields, and where it ultimately leads.
- Option Interruption: They extend the theory of option interruption to the average-reward setting, proving that an agent can improve its overall reward rate by terminating a current option early if a more promising one becomes available.
Experimental Setup
As is standard in foundational RL research, the authors evaluate their algorithms using a simulated benchmark environment rather than a static dataset.
They utilize a Continuing Four-Room Domain, a classic grid-world modified to be non-episodic. The agent must navigate between rooms to reach goal states that provide rewards, but the task never resets. This environment tests whether the proposed algorithms can learn optimal policies using a mix of primitive actions and pre-defined "hallway options" (policies designed to reach room exits).
Key Insights and Results
Moving away from discounting makes these algorithms better suited for the future of continuing RL, where agents must learn indefinitely. The empirical results highlight several major successes:
- Stability and Performance: In the Four-Room domain, the proposed inter-option Differential Q-learning proved significantly more stable and less sensitive to hyperparameters than previous baselines.
- Synergy of Options and Actions: The agent achieved the highest reward rates when allowed to use both high-level options and primitive actions together, rapidly outpacing the performance of using either in isolation.
- Learning Without Doing: The intra-option experiments demonstrated that an agent could accurately learn the values for hallway options off-policy, even if it only ever performed random primitive actions.
- Interruption Works: Allowing an agent to interrupt an option mid-way to switch to a better one—based on their newly extended interruption theory—resulted in a higher overall reward rate than rigidly following options to completion.
Limitations and Future Work
While foundational, the current work is demonstrated in a "tabular" setting, where every state is tracked individually. The natural next step is extending these algorithms to linear and deep function approximation to handle larger, more complex state spaces.
Additionally, this paper assumes the set of options is already provided to the agent. A major open challenge remains "option discovery"—enabling an agent to automatically identify which high-level behaviors are worth learning in an average-reward environment. Finally, future work could integrate the separate learning and planning algorithms into a unified, Dyna-style architecture for average-reward options.
Summary updated