Source-linked AI summary
Finite-Sample Analysis for SARSA with Linear Function Approximation
Shaofeng Zou, Tengyu Xu, Yingbin Liang
TL;DR
The paper addresses the unresolved finite-sample analysis of on-policy SARSA with linear function approximation under a single non-i.i.d. trajectory and dynamically changing behavior policy. It characterizes stochastic bias in time-varying Markov processes, derives finite-sample analyses for SARSA and fitted SARSA, and identifies scope limitations concerning policy performance and the Lipschitz constant.
Problem
Finite-sample convergence and sample-complexity guarantees for on-policy SARSA remain difficult because samples are non-i.i.d. and the behavior policy changes dynamically with the learned parameters.
Method
The paper constructs auxiliary uniformly ergodic Markov chains to characterize stochastic bias under time-varying transition kernels, then combines this technique with gradient-descent analysis for SARSA and fitted SARSA.
Results
The paper provides finite-sample analyses for on-policy SARSA with linear function approximation and for a more general fitted SARSA algorithm under single-trajectory non-i.i.d. data.
Takeaways & Limitations
Fitted SARSA supports iterative on-policy fitted policy iteration, and its fitted step can stop before convergence without affecting the overall convergence and sample complexity established by the analysis.
Takeaways & Limitations
The paper leaves the theoretical performance characterization of policies produced by Lipschitz-continuous operators open and notes a tension between convergence requirements and larger Lipschitz constants preferred for exploitation.
Abstract
from arXiv · showhide
SARSA is an on-policy algorithm to learn a Markov decision process policy in reinforcement learning. We investigate the SARSA algorithm with linear function approximation under the non-i.i.d.\ data, where a single sample trajectory is available. With a Lipschitz continuous policy improvement operator that is smooth enough, SARSA has been shown to converge asymptotically \cite{perkins2003convergent,melo2008analysis}. However, its non-asymptotic analysis is challenging and remains unsolved due to the non-i.i.d. samples and the fact that the behavior policy changes dynamically with time. In this paper, we develop a novel technique to explicitly characterize the stochastic bias of a type of stochastic approximation procedures with time-varying Markov transition kernels. Our approach enables non-asymptotic convergence analyses of this type of stochastic approximation algorithms, which may be of independent interest. Using our bias characterization technique and a gradient descent type of analysis, we provide the finite-sample analysis on the mean square error of the SARSA algorithm. We then further study a fitted SARSA algorithm, which includes the original SARSA algorithm and its variant in \cite{perkins2003convergent} as special cases. This fitted SARSA algorithm provides a more general framework for \textit{iterative} on-policy fitted policy iteration, which is more memory and computationally efficient. For this fitted SARSA algorithm, we also provide its finite-sample analysis.
1 Introduction
The paper studies finite-sample convergence of on-policy SARSA with linear function approximation under a single non-i.i.d. trajectory and dynamically changing behavior policies. It develops a bias-characterization technique for time-varying Markov processes and extends the analysis to fitted SARSA.
- 1 Introduction: SARSA updates action-value estimates from on-policy samples and improves its behavior policy iteratively.The policy improvement operator is applied after each action-value update.
- 1 Introduction: Function approximation makes SARSA more scalable for large or continuous state spaces but does not generally guarantee convergence with ϵ-greedy or softmax improvement.Convergence can be established under additional conditions, including sufficiently smooth Lipschitz policy improvement.
- 1 Introduction: Prior SARSA studies mainly established asymptotic convergence, leaving finite-sample accuracy and sample-complexity dependence unresolved.The paper also studies how Markov-process and algorithm parameters affect convergence rates.
- 1 Introduction: The paper introduces a bias characterization for time-varying Markov transition kernels and applies it to finite-sample on-policy SARSA analysis.Auxiliary uniformly ergodic Markov chains approximate the dynamically changing process, while gradient-descent analysis yields convergence guarantees.
- 1 Introduction: Fitted SARSA generalizes on-policy fitted policy iteration by using multiple TD iterations between policy improvements and includes prior SARSA variants as special cases.Its finite-sample analysis shows that the fitted step need not run to convergence.
- 1 Introduction: The analysis addresses stochastic bias caused jointly by non-i.i.d. samples and behavior policies that change with the learned parameters.These dependencies distinguish the problem from analyses with fixed transition kernels or fixed behavior policies.
2 Preliminaries
The paper formulates reinforcement learning as an MDP with continuous states and finite actions, then represents action-value functions using linear combinations of fixed features. The objective is a compact parameterized approximation to the optimal action-value function.
- 2 Preliminaries: The environment is modeled as an MDP with continuous state space X, finite action set A, transition kernel P, reward function r, and discount factor γ.The reward is assumed uniformly bounded.
- 2 Preliminaries: A stationary policy maps each state to an action distribution that does not depend on time.Its value function is the expected total discounted reward under that policy.
- 2 Preliminaries: The action-value function Qπ measures discounted reward from a state-action pair under policy π, while Q* is the supremum over policies.The optimal policy is greedy with respect to Q*.
- 2 Preliminaries: The Bellman operator maps an action-value function to one-step reward plus discounted expected maximized continuation value.It is a contraction in the sup norm, and Q* is its fixed point.
- 2 Preliminaries: Linear function approximation represents Qθ(x,a) as a weighted sum of N fixed features, equivalently φ(x,a)^Tθ.Feature vectors are normalized so their Euclidean norm is at most one.
- 2 Preliminaries: The approximation goal is to use the compact parameter vector θ to represent an action-value function approximating Q* in continuous state spaces.This provides the parameterized function class analyzed by the paper.
3 Finite-Sample Analysis for SARSA
The paper analyzes projected SARSA with linear function approximation under a time-varying behavior policy and single-trajectory Markovian data. Its finite-sample analysis explicitly characterizes stochastic bias using auxiliary Markov chains and derives convergence bounds under stated regularity assumptions.
- Algorithm and assumptions: Projected SARSA uses a θ-dependent policy πθt, linear action-value estimates, temporal-difference updates, and projection onto a radius-R ball.The policy is generated through a Lipschitz policy improvement operator, while projection controls the gradient norm.
- Algorithm and assumptions: The analysis assumes uniformly ergodic fixed-policy Markov chains, linearly independent basis functions, and a policy Lipschitz condition strong enough to preserve negative definiteness.These assumptions support convergence toward a unique limit point θ∗ and require the projection radius to contain it.
- Finite-sample results: Under the stated assumptions, the paper derives finite-sample mean-square error bounds for SARSA with both diminishing and constant step sizes.For αt = 1/T, the reported upper bound converges to zero as T →∞; the theorem statements also characterize dependence on mixing and algorithm parameters.
- Finite-sample results: The diminishing-step-size result is reported to have a faster convergence rate than an existing finite-sample bound for nearest-neighbor Q-learning.The comparison is stated at the theorem-summary level without replacing the SARSA bound with a task-specific metric.
- Technical challenge: The central difficulty is stochastic-gradient bias caused by non-i.i.d. samples, strong coupling between parameters and observations, and a behavior policy that changes the transition kernel over time.Unlike analyses with fixed policies, SARSA uses the evolving parameter both in the update and in subsequent action generation.
- Technical challenge: The proof constructs an auxiliary Markov chain that follows SARSA initially, then fixes the policy at πθt−τ so its observations approach the corresponding stationary distribution.This construction supports a decomposition that explicitly bounds the bias induced by the original time-varying process.
4 Finite-sample Analysis for Fitted SARSA Algorithm
The fitted SARSA algorithm generalizes on-policy fitted policy iteration by performing a configurable number of TD(0) updates between policy improvements. Under the stated assumptions, it converges with finite-sample guarantees while retaining the original SARSA sample complexity.
- Algorithm: The fitted SARSA algorithm performs B TD(0) iterations after each policy improvement to estimate the current policy’s action-value function.It uses one Markov trajectory and does not require TD iterations to converge between policy improvements.
- Algorithm: Original SARSA is recovered when B = 1, while the earlier convergent variant is recovered when B = ∞.Thus, the framework covers both single-update and fully converged fitted steps.
- Analysis setting: The analysis focuses on a common fitted-step length B, although different numbers of TD iterations can be used to control estimation accuracy.The general unequal-B case is described as analytically more involved.
- Guarantee: Theorem 3 provides a finite-sample convergence bound for fitted SARSA under Assumptions 1 and 2.The theorem is stated for the linear-function-approximation version of Algorithm 2.
- Guarantee: With a sufficiently small constant step size and sufficiently large T, fitted SARSA converges to a small neighborhood of θ∗.The bound uses a transient quantity τ0, which scales as log T for sufficiently large T.
- Efficiency: Fitted SARSA has the same overall sample complexity as original SARSA but can be more computationally efficient by using fewer policy improvements.For n0 samples, it uses n0/B policy improvement operators, whose computation scales linearly with |A|.
5 Discussion of Lipschitz Continuity Assumption
The discussion motivates Lipschitz continuity as important for SARSA convergence because discontinuous action selection can destabilize policy updates. It also identifies a trade-off between convergence conditions and exploitation, plus an unresolved performance question.
- Assumption: Lipschitz continuity of the policy improvement operator plays an important role in SARSA convergence.The discussion contrasts this with discontinuous ϵ-greedy and softmax action selection.
- Related behavior: With function approximation, ϵ-greedy SARSA can chatter and fail to converge, while another result places SARSA in a bounded region rather than showing divergence.A proposed explanation is that small value-estimate changes can cause large behavior-policy changes.
- Fixed points: Continuous policy improvement operators guarantee existence of SARSA fixed points, while Lipschitz continuity supports convergence to a unique limit point under the cited construction.The softmax case may have fixed points that are not unique.
- Trade-off: The Lipschitz constant C must not be too large for the convergence guarantee, although larger C is generally preferred for exploitation.An adaptive method for selecting a suitable C was proposed, and convergence may sometimes hold for larger values than the theorems require.
- Open problem: Theoretical performance characterization of policies produced by SARSA with Lipschitz continuous operators remains an open problem.The discussion identifies this as future work for continuous action-selection methods.
6 Conclusion
The paper develops the first finite-sample analysis of online SARSA with continuous states, linear function approximation, a single trajectory, and non-i.i.d. data. It also introduces and analyzes a more general fitted SARSA framework.
- Conclusion: The paper presents the first finite-sample analysis for SARSA with continuous state space and linear function approximation.The analysis applies to online learning from a single sample path with non-i.i.d. data.
- Conclusion: A novel technique characterizes stochastic bias under dynamically changing behavior policies, enabling non-asymptotic analysis of this stochastic-approximation setting.The paper applies this technique to SARSA convergence analysis.
- Conclusion: The paper introduces a fitted SARSA algorithm as a general framework for iterative on-policy fitted policy iteration and provides its finite-sample analysis.The fitted method is studied alongside the original SARSA algorithm.
A Useful Lemmas for Proof of Theorem 1
The supplied proof passages establish bounded updates, negative-definite mean dynamics, and a bias-control strategy for time-varying Markov behavior policies. They support the technical route to the finite-sample SARSA analysis.
- Boundedness: The stochastic update is bounded by G when the parameter norm is bounded and feature vectors satisfy ∥φ(x, a)∥2 ≤ 1.The bound follows from the reward and discounted feature terms in the update.
- Kernel comparison: The transition-kernel comparison uses operator and total-variation norms to relate policies with different parameters.The stationary state-action measure is represented as µθ(dx, a) = Pθ(dx)πθ(a|x).
- Mean dynamics: The mean-update matrix Aθ∗ is negative definite, yielding a stabilizing quadratic term around θ∗.The proof identifies this term as ˜θT Aθ∗˜θ.
- Bias control: The proof separates parameter drift from Markov-chain mixing by bounding changes in Λt across a delay window through accumulated step sizes.The delay argument uses the Lipschitz continuity of Λt.
- Bias control: A time-varying-policy bias is analyzed by comparing the original process with an auxiliary chain that repeatedly applies a fixed policy πθt−τ.The comparison is controlled recursively using total-variation distances and uniform ergodicity.
B Proof of Equation (40)
The proof rewrites the total-variation terms using joint distributions of states, actions, and evolving policy variables. It then bounds the resulting components using the Lipschitz condition and an auxiliary Markov chain.
- Total-variation decomposition: The total variation in (39) is decomposed into terms involving the actual and auxiliary state-action transitions.The proof explicitly compares joint probabilities conditioned on the past trajectory and policy variables.
- Auxiliary-chain representation: An auxiliary Markov chain is introduced to express the second term in (50) under a fixed conditional transition structure.Its state-action transition probability is written explicitly in terms of the conditional state and policy distributions.
- Bounding the components: The two principal terms are bounded by repeatedly applying conditional-probability factorizations and the Lipschitz condition in (2).The resulting bounds include factors involving C, |A|, G, and P_{t-1}.
- Combining bounds: The proof separately bounds the first and second terms in (56), then combines them to obtain an upper bound for the total-variation expression.The argument uses analogous bounds for the two terms and concludes with an upper bound for (63).
C Proof of Theorem 1
The proof analyzes the projected error recursion by decomposing the squared-error update and applying monotonicity and noise bounds. This yields the recursive inequality used to establish Theorem 1.
- Error decomposition: The squared error is decomposed into the projected update, the mean operator difference, and the stochastic term Λ_t(θ_t).The projection step uses nonexpansiveness, while the fixed point satisfies ḡ(θ*) = 0.
- Error decomposition: Orthogonal projection nonexpansiveness and ḡ(θ*) = 0 reduce the update to a term involving ⟨θ_t − θ*, ḡ(θ_t) − ḡ(θ*)⟩.This isolates the contraction-related component from the stochastic error contribution.
- Recursive bound: Applying Lemmas 2 and 4 gives a recursive bound with contraction coefficient 1 − 2α_t w_s and additive terms α_t^2G^2 and 2α_tΛ_t(θ_t).The resulting inequality is stated as equation (69).
D Proof of Lemma 1
The proof bounds the limiting parameter through the negative definiteness of the expected matrix and the fixed-point relation. It then outlines how the constant-step-size result follows by the same recursive-error strategy.
- Limit-point relation: The limit point satisfies −A_{θ*}θ* = b_{θ*}, which links the limiting parameter to the expected reward vector.Multiplying by (θ*)^T yields a quadratic-form identity used in the proof.
- Constant-step-size analysis: The constant-step-size proof follows the proof of Theorem 1, using a truncated lag τ and recursively applying the resulting error inequality.The lag is set to t when t ≤ τ_0 and to τ_0 otherwise.
F Proof of Theorem 3
The proof of Theorem 3 controls block-level error terms for a non-increasing step-size sequence. It uses an auxiliary fixed-policy Markov chain, bounds temporal differences, and recursively applies the resulting inequalities.
- Blockwise bounds: Lemma 8 provides bounds for each index within a block, distinguishing the cases tB ≤ τ and tB > τ.The lemma assumes a non-increasing step-size sequence and applies separately before and after the lag threshold.
- Temporal-difference control: The difference between stochastic and mean terms is bounded by parameter changes across the block and lag intervals.The bound contains coefficients involving R, γ, λC, and G.
- Auxiliary-chain argument: For the first term, the proof constructs an auxiliary Markov chain following the fixed policy Γ(φ^Tθ_{tB−τ}).This construction is used to control dependence on the delayed iterate.
- Recursive conclusion: Recursive application of the blockwise inequalities yields bounds involving τ_0, B, log T, and the spectral quantity w.The proof treats both non-increasing and constant step sizes, with the constant case setting α_t = α_0 < 1.