Multi-step Reinforcement Learning: A Unifying Algorithm

• TD methods combine learning from raw experience with bootstrapping from learned estimates, supporting prediction and control without an environment model.Source: The Landscape of TD Algorithms · p. 1
• 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.Source: The Landscape of TD Algorithms · p. 1
• TD(λ) creates a spectrum from one-step TD learning at λ = 0 to Monte Carlo methods at λ = 1 through eligibility traces.Source: The Landscape of TD Algorithms · p. 1
• 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.Source: The Landscape of TD Algorithms · p. 2
• Experiments found that intermediate σ values can outperform both extremes, while dynamically varying σ can produce still greater performance on tabular and function-approximation problems.Source: The Landscape of TD Algorithms · p. 2

MDPs

• An MDP models an agent observing states, selecting actions, receiving rewards, and transitioning according to p(s′|s, a).Source: MDPs and One-step Solution Methods · p. 2
• The agent’s policy is a probability distribution over actions, and policy iteration seeks an optimal policy maximizing expected discounted return.Source: MDPs and One-step Solution Methods · p. 2

Value Functions

• For control, the action-value function estimates expected return after taking an action in a state and following a policy.Source: MDPs and One-step Solution Methods · p. 2

TD Updates

• TD updates bootstrap from future action-value estimates using a step-size parameter, and these update rules are called backup operations.Source: MDPs and One-step Solution Methods · p. 2

Control Methods

• Expected Sarsa averages subsequent action values under a target policy, while Q-learning is its greedy-policy special case.Source: MDPs and One-step Solution Methods · p. 2

Backup Diagrams

• Backup diagrams compare atomic 4-step Sarsa, Expected Sarsa, Tree-backup, and Q(σ) by showing how Q(σ) encompasses the others through σ settings.Source: Figure 1 · p. 3

• 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.Source: Atomic Multi-Step Algorithms · p. 3
• n-step Sarsa uses an n-step return that accumulates rewards before bootstrapping from a later action-value estimate.Source: Atomic Multi-Step Algorithms · p. 3
• Off-policy n-step Sarsa introduces an importance sampling ratio into the update.Source: Atomic Multi-Step Algorithms · p. 3
• 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.Source: Atomic Multi-Step Algorithms · p. 3
• Importance sampling can create high variance, requiring smaller step sizes that slow off-policy learning.Source: Atomic Multi-Step Algorithms · p. 3

• Tree-backup takes an expectation over all actions at each transition, making it a multi-step extension of Expected Sarsa.Source: Tree-backup · p. 3
• Tree-backup can learn off-policy without importance sampling, so the behavior policy need not be stationary, Markov, or known.Source: Tree-backup · p. 3
• 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.Source: Tree-backup · pp. 3–4
• Tree-backup’s atomic multi-step version was first presented by Sutton and Barto in 2018.Source: Tree-backup · p. 4
• Under a stochastic policy, Tree-backup is more biased than Sarsa because action-probability weighting reduces the weight of received rewards before bootstrapping.Source: Tree-backup · p. 4

• Q(σ) unifies the generalizations of Sarsa and Expected Sarsa into a single algorithm.Source: The Q(σ) Algorithm · p. 4
• Q(σ) chooses between sampled actions and expectations at each backup step, rather than requiring one choice throughout the backup.Source: The Q(σ) Algorithm · p. 4
• 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.Source: The Q(σ) Algorithm · p. 5
• At each time step, σ can be chosen so the Q(σ) contraction is no greater than that of Sarsa or Expected Sarsa, potentially speeding convergence.Source: The Q(σ) Algorithm · p. 5
• σ = 1 recovers Sarsa, σ = 0 recovers Expected Sarsa and Tree-backup, and a final-step σ = 0 recovers n-step Expected Sarsa.Source: The Q(σ) Algorithm · p. 5
• Intermediate σ values create algorithms between full sampling and pure expectation, and σ can vary by time, state, learning progress, or episode.Source: The Q(σ) Algorithm · p. 5

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.Source: 19-State Random Walk · p. 5
• 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.Source: 19-State Random Walk · p. 5
• 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.Source: 19-State Random Walk · p. 5

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.Source: Stochastic Windy Gridworld · p. 6

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.Source: Mountain Cliff · pp. 6–7

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.Source: Discussion · p. 7
• In continuous-state mountain cliff, intermediate σ improves initial performance, while small σ improves asymptotic performance.Dynamic σ exploits both benefits by adjusting σ over time.Source: Discussion · p. 7
• 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(λ).Source: Discussion · p. 7
• 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.Source: Discussion · p. 7

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.Source: Conclusions · p. 7
• Intermediate fixed sampling outperformed the extreme methods Sarsa and Tree-backup on prediction and control problems.Source: Conclusions · p. 7
• Dynamically adjusting σ outperformed every fixed degree of sampling.The paper presented one simple method for dynamically varying σ.Source: Conclusions · p. 7
• 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.Source: Conclusions · p. 7

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.Source: Proof of Theorem 1 · p. 8
• 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.Source: Proof of Theorem 1 · p. 8
• 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.Source: Proof of Theorem 1 · p. 8
• 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.Source: Proof of Theorem 1 · p. 8
• Consequently, Δ_t converges to 0 with probability 1, implying that Q_t converges to Q∗ with probability 1.Source: Proof of Theorem 1 · p. 8