Source-linked AI summary
Multi-step Reinforcement Learning: A Unifying Algorithm
Kristopher De Asis, J. Fernando Hernandez-Garcia, G. Zacharias Holland, Richard S. Sutton
TL;DR
The paper addresses how to unify distinct multi-step TD control methods whose relative performance varies across problems. It introduces Q(σ), which continuously mixes sampling and expectation, and finds that intermediate or dynamically adjusted sampling can outperform fixed extremes. The empirical study focuses on on-policy prediction and control.
Problem
Existing multi-step TD control methods appear distinct, and no single method dominates across all problems, motivating a unified approach.
Method
Q(σ) uses a sampling parameter σ to vary continuously between full sampling and pure expectation in atomic multi-step backups.
Results
Intermediate fixed sampling outperformed Sarsa and Tree-backup, while a simple dynamically adjusted σ outperformed fixed sampling in the reported prediction and control problems.
Takeaways & Limitations
Varying the sampling degree provides a unified space in which intermediate and dynamic mixtures can achieve stronger performance than endpoint methods.
Takeaways & Limitations
The study used atomic multi-step backups without eligibility traces, evaluated only on-policy problems, and investigated one simple dynamic-σ scheme.
Abstract
from arXiv · showhide
Unifying seemingly disparate algorithmic ideas to produce better performing algorithms has been a longstanding goal in reinforcement learning. As a primary example, TD($λ$) elegantly unifies one-step TD prediction with Monte Carlo methods through the use of eligibility traces and the trace-decay parameter $λ$. Currently, there are a multitude of algorithms that can be used to perform TD control, including Sarsa, $Q$-learning, and Expected Sarsa. These methods are often studied in the one-step case, but they can be extended across multiple time steps to achieve better performance. Each of these algorithms is seemingly distinct, and no one dominates the others for all problems. In this paper, we study a new multi-step action-value algorithm called $Q(σ)$ which unifies and generalizes these existing algorithms, while subsuming them as special cases. A new parameter, $σ$, is introduced to allow the degree of sampling performed by the algorithm at each step during its backup to be continuously varied, with Sarsa existing at one extreme (full sampling), and Expected Sarsa existing at the other (pure expectation). $Q(σ)$ is generally applicable to both on- and off-policy learning, but in this work we focus on experiments in the on-policy case. Our results show that an intermediate value of $σ$, which results in a mixture of the existing algorithms, performs better than either extreme. The mixture can also be varied dynamically which can result in even greater performance.
The Landscape of TD Algorithms
TD control methods extend one-step updates across multiple steps, but the best way to combine sampling and expectation is not clear. Q(σ) unifies these methods by varying sampling continuously, and intermediate or dynamic settings can outperform endpoint algorithms.
- TD methods combine learning from raw experience with bootstrapping from learned estimates, supporting prediction and control without an environment model.
- Existing TD control methods such as Sarsa, Q-learning, and Expected Sarsa can be extended across multiple time steps, but their relationships are not fully unified.
- TD(λ) creates a spectrum from one-step TD learning at λ = 0 to Monte Carlo methods at λ = 1 through eligibility traces.
- Q(σ) controls the degree of sampling in multi-step TD control, with σ = 1 giving Sarsa, σ = 0 giving Tree-backup, and intermediate values mixing sampling with expectation.
- Experiments found that intermediate σ values can outperform both extremes, while dynamically varying σ can produce still greater performance on tabular and function-approximation problems.
MDPs and One-step Solution Methods
Reinforcement-learning agents are modeled as interacting with an MDP and estimate action values through TD backups. One-step methods differ in how they sample or average subsequent actions, while backup diagrams visualize these update structures.
- MDPs: An MDP models an agent observing states, selecting actions, receiving rewards, and transitioning according to p(s′|s, a).
- MDPs: The agent’s policy is a probability distribution over actions, and policy iteration seeks an optimal policy maximizing expected discounted return.
- Value Functions: For control, the action-value function estimates expected return after taking an action in a state and following a policy.
- TD Updates: TD updates bootstrap from future action-value estimates using a step-size parameter, and these update rules are called backup operations.
- Control Methods: Expected Sarsa averages subsequent action values under a target policy, while Q-learning is its greedy-policy special case.
- Backup Diagrams: Backup diagrams compare atomic 4-step Sarsa, Expected Sarsa, Tree-backup, and Q(σ) by showing how Q(σ) encompasses the others through σ settings.
Atomic Multi-Step Algorithms
Atomic multi-step algorithms extend TD control by bootstrapping over longer intervals through n-step returns. Longer backups can reduce bias while increasing variance, and off-policy n-step Sarsa uses importance sampling.
- Longer bootstrapping intervals can reduce update bias but increase variance, while n > 1 can improve performance in many cases.Atomic multi-step algorithms are characterized by their n-step returns.
- n-step Sarsa uses an n-step return that accumulates rewards before bootstrapping from a later action-value estimate.
- Off-policy n-step Sarsa introduces an importance sampling ratio into the update.
- n-step Expected Sarsa samples the first n − 1 states and actions, then backs up the final state using the target policy’s expected action-value.An importance sampling ratio can be added for fully off-policy learning while omitting the last time step.
- Importance sampling can create high variance, requiring smaller step sizes that slow off-policy learning.
Tree-backup
Tree-backup extends Expected Sarsa by taking expectations over actions at every backup step rather than only at the final step. It can learn off-policy without importance sampling, but its probability weighting makes it more biased than Sarsa under stochastic policies.
- Tree-backup takes an expectation over all actions at each transition, making it a multi-step extension of Expected Sarsa.
- Tree-backup can learn off-policy without importance sampling, so the behavior policy need not be stationary, Markov, or known.
- Tree-backup’s return weights branches by action probabilities and discount factors, while branch values represent later action-values and main-branch segments represent rewards.
- Tree-backup’s atomic multi-step version was first presented by Sutton and Barto in 2018.
- Under a stochastic policy, Tree-backup is more biased than Sarsa because action-probability weighting reduces the weight of received rewards before bootstrapping.
The Q(σ) Algorithm
Q(σ) unifies multi-step TD control methods by varying sampling and expectation at each backup step. Its endpoints recover existing algorithms, while intermediate or dynamic σ values provide additional choices for controlling the sampling mixture.
- Q(σ) unifies the generalizations of Sarsa and Expected Sarsa into a single algorithm.
- Q(σ) chooses between sampled actions and expectations at each backup step, rather than requiring one choice throughout the backup.
- One-step Q(σ) can learn optimal action-value functions under finite state-action spaces, bounded rewards, suitable step sizes, and greedy-in-the-limit exploration.
- At each time step, σ can be chosen so the Q(σ) contraction is no greater than that of Sarsa or Expected Sarsa, potentially speeding convergence.
- σ = 1 recovers Sarsa, σ = 0 recovers Expected Sarsa and Tree-backup, and a final-step σ = 0 recovers n-step Expected Sarsa.
- Intermediate σ values create algorithms between full sampling and pure expectation, and σ can vary by time, state, learning progress, or episode.
19-State Random Walk
The experiments evaluate Q(σ) across prediction, tabular control, and continuous-state control tasks. Intermediate or dynamically varying sampling generally performs strongly, with dynamic σ outperforming fixed alternatives in the reported experiments.
- 19-State Random Walk: The 19-state random walk estimates state values under equiprobable random behavior using RMS error against analytically computed values.Each Q(σ) setting ran for 50 episodes, averaged across 100 runs.
- 19-State Random Walk: Q(1) had better initial performance, whereas Tree-backup had better asymptotic performance; intermediate sampling traded off between them.The comparison used n = 3 and α = 0.4 as representative parameter settings.
- 19-State Random Walk: Dynamic σ outperformed all fixed sampling degrees in the random walk experiment.σ decreased by a factor of 0.95 after each episode to combine the initial advantage of Sarsa with the asymptotic advantage of Tree-backup.
- Stochastic Windy Gridworld: In stochastic windy gridworld, n = 3 produced the greatest performance across tested σ values, and dynamic σ performed best overall.σ = 0.5 was the closest fixed alternative.
- Mountain Cliff: In mountain cliff, dynamic σ outperformed all static-σ algorithms in average return per episode.The results were averaged over 500 runs, with smoothed and unsmoothed curves shown.
Discussion
The discussion interprets Q(σ) as a unified sampling spectrum with task- and training-dependent trade-offs. Intermediate and dynamically adjusted sampling can improve performance across prediction, tabular control, and continuous-state tasks.
- Discussion: Intermediate sampling can achieve higher per-episode average return than either extreme in stochastic windy gridworld, depending on elapsed episodes.The result reflects a trade-off between initial and asymptotic performance.
- Discussion: In continuous-state mountain cliff, intermediate σ improves initial performance, while small σ improves asymptotic performance.Dynamic σ exploits both benefits by adjusting σ over time.
- Discussion: Increasing the backup length n can improve performance by changing how many rewards are included before bootstrapping.The discussion relates this bias-variance trade-off to λ in TD(λ).
- Discussion: In the 19-state random walk, large σ lowers initial bias and RMS error, while small σ eventually benefits from lower variance.The result illustrates σ’s bias-variance trade-off over training.
Conclusions
Q(σ) unifies multi-step TD control through a sampling parameter that interpolates between full sampling and pure expectation. Intermediate fixed sampling can outperform Sarsa and Tree-backup, while dynamically adjusting σ performs better than any fixed degree of sampling.
- Conclusions: Q(σ) continuously varies multi-step backups between full sampling and pure expectation through the sampling parameter σ.This provides a unified framework for multi-step TD control methods.
- Conclusions: Intermediate fixed sampling outperformed the extreme methods Sarsa and Tree-backup on prediction and control problems.
- Conclusions: Dynamically adjusting σ outperformed every fixed degree of sampling.The paper presented one simple method for dynamically varying σ.
- Conclusions: The reported presentation was limited to atomic multi-step backups without eligibility traces and to on-policy experiments.Only one simple scheme for dynamically varying σ was investigated.
Proof of Theorem 1
The proof analyzes the error between Q_t and the optimal action-value function Q∗, establishes a contraction-style conditional-expectation bound, and concludes almost-sure convergence when the policy becomes greedy in the limit.
- Proof of Theorem 1: The proof defines Δ_t(X_t) as Q_t(X_t) − Q∗(X_t) and constructs a stochastic process around this error.The noise term F_t includes the reward and the σ-weighted mixture of sampled and expected next-state values.
- Proof of Theorem 1: Showing that Δ_t converges to 0 is equivalent to showing that Q_t converges to Q∗.The argument applies the conditions of a stochastic-approximation lemma.
- Proof of Theorem 1: The proof establishes ||E{F_t|P_t}|| ≤ k||Δ_t|| + C_t with k ∈ [0, 1) and C_t converging to 0 almost surely.This is the key bound needed for the convergence lemma.
- Proof of Theorem 1: When the policy becomes greedy and σ_t+1 ∈ [0, 1], the mixed backup equals the greedy maximum action-value.Under this condition, C_t converges to 0.
- Proof of Theorem 1: Consequently, Δ_t converges to 0 with probability 1, implying that Q_t converges to Q∗ with probability 1.