Segmenting Action-Value Functions over Time Scales in SARSA via TD(Δ)

Mahammad Humayoo, Gengzhong Zheng, Xiaoqing Dong, Wei Huang, Liming Miao, Shuwei Qiu, Zexun Zhou, Peitao Wang, Zakir Ullah, Naveed Ur Rehman Junejo, Xueqi ChengAlgorithms 2025 · OpenReview

TL;DR

This paper introduces SARSA(Δ), a novel reinforcement learning algorithm that decomposes the action-value function into multiple components, each learning at a different "time scale" defined by a unique discount factor. This approach aims to overcome the bias-variance trade-off inherent in traditional SARSA, leading to faster convergence and improved performance, especially in long-horizon tasks.

What Problem Does This Paper Address?

Reinforcement learning (RL) agents often struggle with tasks that require long-term planning and delayed rewards. Traditional RL algorithms like SARSA use a single discount factor (η) to balance short-term and long-term rewards. However, a low η leads to myopic policies (high bias, low variance), while a high η results in unstable policies (low bias, high variance). This fixed discount factor fails to adapt to varying reward densities and the inherent complexities of long-horizon problems, leading to suboptimal learning. The paper addresses this by proposing a method to learn action-value functions across multiple time scales simultaneously.

Methods

The core contribution is the extension of the Temporal Difference decomposition method, TD(Δ), to the SARSA algorithm, resulting in SARSA(Δ). Instead of learning a single action-value function Q(s, a), SARSA(Δ) decomposes it into multiple "delta estimators" (D). Each delta estimator, Dm(s, a), is associated with a specific discount factor ηm and learns the difference between action-value functions at consecutive discount factors (i.e., Dm = Qηm - Qηm-1). These delta estimators are learned independently, allowing the agent to capture information from various time scales. The paper details how this decomposition is applied to both single-step and multi-step SARSA updates, as well as its integration with Generalized Advantage Estimation (GAE) and Proximal Policy Optimization (PPO).

Datasets

The paper evaluates SARSA(Δ) on several benchmarks:

  • Tabular Ring MDP: A synthetic environment used to demonstrate the effectiveness of the proposed method in a controlled setting.
  • OpenAI Gym Environments:
    • Deterministic: FrozenLake-v1, CliffWalking-v0
    • Stochastic: Taxi-v3, Blackjack-v1
  • OpenAI Gym Atari Environments: SeaquestNoFrameskip-v4, QbertNoFrameskip-v4

Key Insights and Ideas

  • Decomposing Action-Value Functions: The key insight is that by breaking down the action-value function into components that learn at different discount factors (time scales), we can better manage the bias-variance trade-off.
  • Independent Learning of Time Scales: Learning each delta estimator independently allows for specialized learning at each time scale, potentially leading to more efficient and stable learning.
  • Bridging Tabular and Deep RL: The proposed SARSA(Δ) framework is shown to be effective in both traditional tabular settings and more complex deep RL environments, including Atari games.
  • Improved Convergence and Stability: The decomposition leads to faster convergence and more stable learning, particularly in scenarios requiring long-horizon planning.

Key Results

  • Tabular Ring MDP: SARSA(Δ) consistently outperformed K-step SARSA TD in terms of stability and accuracy across different learning rates and k-step values.
  • OpenAI Gym Environments: SARSA(Δ) achieved higher average rewards and faster convergence compared to K-step SARSA TD in FrozenLake-v1, Taxi-v3, CliffWalking-v0, and Blackjack-v1. For instance, in Taxi-v3, SARSA(Δ) achieved significantly better rewards (closer to -200) than K-step SARSA TD (around -1120).
  • OpenAI Gym Atari Environments: A PPO-based variant of SARSA(Δ) demonstrated superior performance and stability compared to standard PPO in SeaquestNoFrameskip-v4 and QbertNoFrameskip-v4. In Qbert, the proposed method achieved approximately 31% higher average rewards at 100K episodes.

Limitations and Future Work

  • Memory Overhead: The number of delta estimators (M) directly scales the memory requirements, leading to increased storage needs compared to standard SARSA.
  • Stochastic Environments: Rigid scheduling of discount factors (ηm) might not be optimal in highly unpredictable environments. Adaptive scheduling could improve performance.
  • Partial Observability: The current formulation is not directly applicable to Partially Observable Markov Decision Processes (POMDPs).
  • Off-Policy Extension: Adapting SARSA(Δ) to off-policy algorithms like Q-learning is challenging due to potential increases in variance and instability for long-horizon components.

Future work suggested includes:

  • Incorporating SARSA(Δ) with off-policy Q-learning.
  • Applying the method to multi-agent systems by sharing delta components.
  • Developing adaptive scheduling of discount factors using meta-gradients.
  • Extending the framework to handle partially observable environments.

Summary updated

Abstract

In numerous episodic reinforcement learning (RL) environments, SARSA-based methodologies are employed to enhance policies aimed at maximizing returns over long horizons. Traditional SARSA algorithms face challenges in achieving an optimal balance between bias and variation, primarily due to their dependence on a single, constant discount factor ( η ). This study enhances the temporal difference decomposition method, TD( Δ ), by applying it to the SARSA algorithm, wherein the action-value function is segmented into several components based on the differences between action-value functions linked to specific discount factors. Each component, referred to as a delta estimator (D), is linked to a specific discount factor and learned independently. This modified technique is referred to as SARSA( Δ ). SARSA is a widely used on-policy RL method that enhances action-value functions via temporal difference updates. This decomposition, namely SARSA( Δ ), facilitates learning across a range of time scales. This analysis makes learning more effective and guarantees consistency, especially in situations where long-horizon improvement is needed. The results of this research show that the proposed technique works to lower bias in SARSA’s updates and speed up convergence in both deterministic and stochastic settings, even in dense-reward Atari environments. Experimental results from a variety of benchmark settings show that the proposed SARSA( Δ ) outperforms existing TD learning techniques in both tabular and deep RL environments.
BibTeX
@inproceedings{humayoo2025segmenting,
  author = {Mahammad Humayoo and Gengzhong Zheng and Xiaoqing Dong and Wei Huang and Liming Miao and Shuwei Qiu and Zexun Zhou and Peitao Wang and Zakir Ullah and Naveed Ur Rehman Junejo and Xueqi Cheng},
  title = {{Segmenting Action-Value Functions over Time Scales in SARSA via TD(Δ)}},
  booktitle = {Algorithms},
  year = {2025},
  url = {https://openreview.net/forum?id=zgCI9Vl4Pk},
}
Figure