Source-linked AI summary
Off-Policy Actor-Critic
Thomas Degris, Martha White, Richard S. Sutton
TL;DR
Off-policy actor-critic learning lacked an algorithm combining off-policy data with explicit, flexible policy representation. The paper introduces Off-PAC, combining an actor with an off-policy gradient-TD critic, and reports convergence, linear per-step complexity, and best final performance with lowest standard error on three benchmarks.
Problem
Prior actor-critic methods were limited to on-policy learning, despite off-policy methods offering policy learning from data generated by another behavior policy.
Method
Off-PAC combines a policy-updating actor with a critic that estimates the current actor policy’s value off-policy, using GTD(λ) with eligibility traces.
Results
Off-PAC achieved the best final performance on three benchmark problems and consistently had the lowest standard error.
Takeaways & Limitations
Off-PAC provides a practical route toward robust off-policy control while retaining explicit stochastic policy representation and linear time and space complexity.
Takeaways & Limitations
The paper omits incremental natural actor-critic methods and only states that their off-policy extension should be straightforward.
Abstract
from arXiv · showhide
This paper presents the first actor-critic algorithm for off-policy reinforcement learning. Our algorithm is online and incremental, and its per-time-step complexity scales linearly with the number of learned weights. Previous work on actor-critic algorithms is limited to the on-policy setting and does not take advantage of the recent advances in off-policy gradient temporal-difference learning. Off-policy techniques, such as Greedy-GQ, enable a target policy to be learned while following and obtaining data from another (behavior) policy. For many problems, however, actor-critic methods are more practical than action value methods (like Greedy-GQ) because they explicitly represent the policy; consequently, the policy can be stochastic and utilize a large action space. In this paper, we illustrate how to practically combine the generality and learning potential of off-policy learning with the flexibility in action selection given by actor-critic methods. We derive an incremental, linear time and space complexity algorithm that includes eligibility traces, prove convergence under assumptions similar to previous off-policy algorithms, and empirically show better or comparable performance to existing algorithms on standard reinforcement-learning benchmark problems.
1. Notation and Problem Setting
The paper formulates off-policy control for discrete-state, discrete-action Markov decision processes using data generated by a fixed behavior policy. It defines a policy-weighted value objective and assumes finite-time termination.
- The setting is a Markov decision process with discrete state and action spaces, transition probabilities P(s′|s, a), and expected rewards R(s, a, s′).
- Observed data are streams of states, actions, and rewards generated by a fixed behavior policy b(a|s) with positive probability for every action.
- For a policy π,γ, the value function is the expected sum of rewards until termination, conditioned on the current state.
- The policy πu is differentiable in weights u and assigns positive probability to every state-action pair; learning chooses u to maximize a scalar objective.
- The objective is weighted by db(s), the limiting state distribution under the behavior policy, because off-policy data follow that distribution.
2. The Off-PAC Algorithm
Off-PAC combines an off-policy critic with an actor update based on an approximate policy gradient. The resulting algorithm uses eligibility traces and supports fully incremental computation with complexity linear in the number of weights.
- Algorithm overview: Off-PAC combines an off-policy value-function critic with an actor that updates policy weights using the critic's estimate.The critic estimates the current actor policy's value function rather than the fixed behavior policy's value function.
- The Critic: Policy Evaluation: The critic uses GTD(λ), which incrementally learns a linear value approximation while minimizing a λ-weighted projected Bellman error.The approximation is ˆV(s) = v^T x_s, with feature vectors representing states.
- The Actor: Policy-gradient theorem: Off-PAC's actor update approximates the policy gradient by omitting the difficult off-policy term involving ∇uQπ,γ(s, a).The paper gives policy-improvement results to justify this approximation, including state-value non-decrease for tabular policies.
- The Actor: Policy-gradient theorem: If the value function is representable, true local maxima are contained among approximate-gradient maxima; with tabular policy representation, the two sets are equal.The tabular result relies on separate state-specific weights, preventing update overlap across states.
- The Actor: Incremental Update Algorithm with Eligibility Traces: The actor is derived from a forward view and converted to a backward view using eligibility traces, yielding a mechanistic incremental update.The backward view uses the temporal-difference error and an eligibility trace for the policy-gradient features.
- The Actor: Incremental Update Algorithm with Eligibility Traces: Off-PAC requires only feature vectors and behavior-policy probabilities, with per-time-step computation and memory complexity linear in Nu + Nv.The algorithm is therefore fully incremental and designed for large-scale function-approximation settings.
3. Convergence Analysis
The convergence analysis uses a two-timescale ODE framework for Off-PAC and proves convergence for λ = 0 with GTD(0) under stated assumptions. The actor converges to stationary policy weights, while the critic converges to the corresponding TD solution with probability one.
- Proof strategy: The analysis separates actor and critic dynamics through two-timescale ODEs, alternately fixing one set of parameters while analyzing the other.This follows the proof structure used for on-policy actor-critic and nonlinear GTD methods.
- Assumptions: The analysis assumes boundedness and regularity conditions, including bounded features, differentiable policies, projected actor weights, and suitable step sizes.The least practical stated assumption is that feature-transition-reward tuples are i.i.d. rather than generated by Markov noise.
- Assumptions: Without projection, proving bounded iterates is difficult, although the algorithm omits projection because stochasticity may make convergence to unstable equilibria unlikely.The projection appears in the convergence assumptions but is not included in the algorithm itself.
- Step sizes: The actor uses a slower timescale than the critic so that the value estimate can effectively approach convergence for the current policy.Suitable schedules make αu,t/αv,t tend to zero, with examples including αv,t = 1/t and αu,t = 1/(1+t log t).
- Theorem: The convergence theorem applies to Off-PAC with λ = 0 and GTD(0) for the critic, assuming conditions (A1)–(A5), (P1)–(P2), and (S1)–(S2).The proof sketch invokes seven requirements to ensure convergence to an asymptotically stable equilibrium.
- Theorem: The policy weights converge to the set of stationary points of the objective, while the value weights converge almost surely to the corresponding TD solution.The result concerns the set Ẑ = {u ∈ U | dg(u) = 0}.
4. Empirical Results
The experiments compare Off-PAC with three off-policy action-value methods on mountain car, pendulum, and continuous grid-world benchmarks. Off-PAC performed best across all problems and was the only method that reliably reached the grid-world goal.
- Experimental setup: Off-PAC, Q(λ), Greedy-GQ, and Softmax-GQ were compared using linear memory and computational complexity in three off-policy benchmarks.The benchmarks were mountain car, pendulum, and continuous grid world, with discrete actions and continuous states.
- Experimental setup: The behavior policy selected actions uniformly at random, while each algorithm learned and periodically evaluated a target policy from behavior-generated data.Target-policy updates were stopped during evaluation so learning depended only on behavior-policy data.
- Benchmarks: The evaluation included mountain car, pendulum, and continuous grid world, with Q(λ) noted as potentially unstable under this function-approximation setting.The pendulum task was intended to test how well algorithms use limited behavior-policy samples because random exploration rarely reaches the optimal region.
- Implementation: The experiments used tile-coded state and state-action features with ten tilings, hashed to 106 dimensions plus a constant feature.The discount factor was γ = 0.99, and thirty runs were conducted for each parameter setting.
- Overall results: Off-PAC performed best on all three problems and had the lowest standard error across all problems.Softmax-GQ and Off-PAC improved over the behavior policy on every problem, whereas Q(λ) and Greedy-GQ improved less in continuous grid world.
5. Discussion
The discussion emphasizes practical parameter sensitivity and two-timescale implementation choices, while identifying natural actor-critic as an unexplored extension. It also interprets Off-PAC’s lower variance as promising for broader off-policy control.
- Practical considerations: Off-PAC can be sensitive to parameter choices, particularly the step sizes, because it uses two-timescale updates with four parameters.The parameters are λ, αv, αw, and αu.
- Practical considerations: Subsampling the slow actor updates can further separate timescales and improve the critic’s value estimate for the current policy.The actor remains fixed between subsampled updates while the critic continues updating.
- Scope: The paper does not explore incremental natural actor-critic methods, although the authors describe an off-policy extension as requiring a small modification.The proposed extension would use the natural rather than conventional gradient.
- Interpretation: Off-policy updates can be noisier than on-policy learning, but the reported results suggest Off-PAC is more robust to this noise through lower variance than action-value methods.The authors view this as promising for extending off-policy learning toward continuous action spaces.
6. Conclusion
The paper introduces Off-PAC for off-policy control, proves its convergence, and evaluates it against gradient-TD alternatives. Across three benchmarks, Off-PAC achieved the best final performance and consistently the lowest standard error.
- Contribution: Off-PAC is presented as a new algorithm for learning control off-policy.The name denotes Off-Policy Actor-Critic.
- Theory: The paper proves that Off-PAC converges in a standard off-policy setting.The conclusion summarizes the theoretical result alongside the empirical evaluation.
- Empirical conclusion: Across three benchmark problems, Off-PAC had the best final performance and consistently the lowest standard error.The conclusion characterizes the method as a step toward robust off-policy control.
A.1. Policy Improvement and Policy Gradient Theorems
The paper establishes off-policy policy-improvement and policy-gradient relationships, with stronger equivalence results when the policy uses a tabular representation.
- Policy Improvement: Theorem 1 gives an off-policy policy-improvement result for appropriately updated policy parameters.The proof uses a sufficiently small positive step size and the action-value function of the current policy.
- Tabular Representation: With a tabular representation, the updated policy satisfies V^πu′,γ(s) ≥ V^πu,γ(s) for every state.The policy probabilities can be updated independently for each state.
- Policy Gradient: Theorem 2 relates the true objective gradient’s stationary points to zeros of the off-policy gradient estimate when the value function is representable.The result defines Z as true-gradient stationary points and ˜Z as zeros of g(u).
- Policy Gradient: The proof rules out points where the true gradient vanishes while the approximate gradient remains nonzero.Such points would contradict the policy-improvement theorem.
- Tabular Representation: For tabular policies, the off-policy gradient estimate and true gradient have the same zero set: Z = ˜Z.Separate weights for each state allow local policy changes without affecting other states.
A.2. Forward/Backward view analysis
The forward/backward analysis shows how off-policy TD errors and eligibility traces produce an equivalent recursive update under stationary behavior-policy sampling.
- Stationary Sampling: The analysis assumes stationary behavior-policy distributions generated by an aperiodic, irreducible Markov chain.Expectations are taken under the limiting state distribution d_b.
- Forward View: The forward-view TD error is recursively expressed using the conventional one-step TD error δ_t = r_t+1 + γ_t+1 V̂(s_t+1) − V̂(s_t).The recursion introduces importance sampling and discounting across prior time steps.
- Backward View: The eligibility trace is defined recursively as e_t = ρ_t(ψ_t + λγ_t e_t−1).Here ρ_t is the importance-sampling ratio and ψ_t is the policy-gradient term.
- Forward/Backward Equivalence: Repeated unrolling rewrites the forward view as an expectation involving the backward eligibility trace.The derivation uses the stated recursive identities and temporal-shift expectations.
A.3. Convergence Proofs
The convergence proof treats Off-PAC as a two-timescale stochastic approximation algorithm, with a faster critic and slower actor converging under explicit regularity and stability assumptions.
- ODE Conditions: The proof uses Lipschitz dynamics, step-size separation, martingale-noise conditions, bounded iterates, and globally asymptotically stable equilibria for the critic and actor ODEs.These conditions support the application of standard two-timescale stochastic-approximation results.
- Two-Timescale Analysis: Off-PAC’s critic and actor updates require a two-timescale analysis because the updates are coupled rather than linearly separable.The actor is analyzed on the slower timescale while the critic evolves on the faster timescale.
- Assumptions: The assumptions include differentiable policy functions, compact projected actor weights, behavior-policy coverage, bounded rewards and features, and bounded value functions.These are stated through assumptions A1–A5 and P1–P2.
- Convergence Result: For λ = 0, Theorem 3 states that the policy weights converge almost surely to ˆZ and the value weights converge to the corresponding TD solution.The result applies to the GTD(λ) critic with importance-sampling correction under assumptions A1–A5, P1–P2, and S1–S2.
- Critic Convergence: The critic ODE has a globally asymptotically stable equilibrium corresponding to the TD-solution value-function weights and an auxiliary expectation estimate.The map from actor weights to critic equilibrium is continuously differentiable with bounded gradient.
- Actor Convergence: The actor dynamics reduce to g(u), so the actor weights converge almost surely to the asymptotically stable fixed-point set ˜Z.The convergence argument relies on the forward/backward analysis and the two-timescale conditions.
B. Errata
The errata restrict the theoretical claims to tabular policy representations and identify errors affecting broader convergence and policy-improvement arguments.
- Scope of Theory: The current theoretical results apply to tabular policy representations, not necessarily to policy function approximation.The authors state that they are working to correct this restriction.
- Corrected Claims: The analysis contains two mistakes that require scaling back its claims.One concerns stable minima of the approximate gradient; the other concerns a set-inclusion claim in Theorem 2.
- Stable Minima: For tabular policies, local updates improve the value without aliasing-induced ripple effects, preserving the stable-minimum argument.Each iteration changes action probabilities for a specific state and action.
- Gradient Stationarity: The claim Z ⊆ ˜Z is erroneous in general, although Z = ˜Z remains true for tabular representations.The weighting mismatch becomes relevant with nonlocal policy representations and differing behavior and target distributions.
- Policy Improvement: When representation aliasing is significant and b differs from π, updates weighted by d_b may not improve performance weighted by d_π.The policy-improvement claim remains true on-policy and for tabular representations.