PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Reinforcement Learning Using Recursive Least-Squares Methods

H. He, D. Hu, X. Xu

arXiv:1106.0707v1cs.LGcs.AI

TL;DR

The paper tackles inefficient reinforcement-learning prediction and control when models are unknown and feedback is delayed. It develops RLS-TD(λ) and Fast-AHC, proving convergence for the former and reporting improved data efficiency for the latter, while showing that variance-matrix initialization matters.

  • Problem

    Reinforcement-learning methods need efficient learning prediction and control from delayed evaluative feedback without prior model information, while linear TD(λ) methods require step-size design and use data inefficiently.

  • Method

    The paper proposes RLS-TD(λ), an RLS-based multi-step TD algorithm with eligibility traces, and Fast-AHC, which uses RLS-TD(λ) in an actor-critic critic.

  • Results

    Fast-AHC achieves better learning-control data efficiency than conventional AHC in pole-balancing and acrobot experiments, while RLS-TD(λ) is shown to converge with probability 1 for ergodic Markov chains.

  • Takeaways & Limitations

    RLS methods can improve learning-prediction and learning-control efficiency, but their performance depends on selecting the initial variance-matrix value for each problem.

  • Takeaways & Limitations

    RLS-TD(λ) can have better transient convergence than LS-TD(λ), whereas LS-TD(λ) may perform better in long-term convergence and provide unbiased estimates under white additive noise.

Abstract

from arXiv · show

The recursive least-squares (RLS) algorithm is one of the most well-known algorithms used in adaptive filtering, system identification and adaptive control. Its popularity is mainly due to its fast convergence speed, which is considered to be optimal in practice. In this paper, RLS methods are used to solve reinforcement learning problems, where two new reinforcement learning algorithms using linear value function approximators are proposed and analyzed. The two algorithms are called RLS-TD(lambda) and Fast-AHC (Fast Adaptive Heuristic Critic), respectively. RLS-TD(lambda) can be viewed as the extension of RLS-TD(0) from lambda=0 to general lambda within interval [0,1], so it is a multi-step temporal-difference (TD) learning algorithm using RLS methods. The convergence with probability one and the limit of convergence of RLS-TD(lambda) are proved for ergodic Markov chains. Compared to the existing LS-TD(lambda) algorithm, RLS-TD(lambda) has advantages in computation and is more suitable for online learning. The effectiveness of RLS-TD(lambda) is analyzed and verified by learning prediction experiments of Markov chains with a wide range of parameter settings. The Fast-AHC algorithm is derived by applying the proposed RLS-TD(lambda) algorithm in the critic network of the adaptive heuristic critic method. Unlike conventional AHC algorithm, Fast-AHC makes use of RLS methods to improve the learning-prediction efficiency in the critic. Learning control experiments of the cart-pole balancing and the acrobot swing-up problems are conducted to compare the data efficiency of Fast-AHC with conventional AHC. From the experimental results, it is shown that the data efficiency of learning control can also be improved by using RLS methods in the learning-prediction process of the critic. The performance of Fast-AHC is also compared with that of the AHC method using LS-TD(lambda). Furthermore, it is demonstrated in the experiments that different initial values of the variance matrix in RLS-TD(lambda) are required to get better performance not only in learning prediction but also in learning control. The experimental results are analyzed based on the existing theoretical work on the transient phase of forgetting factor RLS methods.

1. Introduction

The paper addresses reinforcement-learning problems where delayed feedback and unknown models make efficient learning prediction and control important. It proposes RLS-based TD and actor-critic methods to improve efficiency and establishes theoretical and empirical results for them.

  • Motivation: Existing linear TD(λ) methods require carefully designed step sizes and use data inefficiently, motivating least-squares alternatives.LS-TD(0) and RLS-TD(0) remove step-size design, while RLS is suited to online estimation and control.
  • Contributions: RLS-TD(λ) extends RLS-TD(0) to general 0≤λ≤1, adding eligibility traces while eliminating step-size schedules.Its convergence with probability one and convergence limit are analyzed for ergodic Markov chains.
  • Implications: The parameter λ affects approximation-error bounds, with the smallest bound at λ=1 and the worst bound at λ=0.The convergence rate is mainly influenced by variance-matrix initialization, while the approximation-error bound is dominantly determined by λ.
  • Contributions: Fast-AHC applies RLS-TD(λ) in the critic of an actor-critic architecture to improve learning-prediction efficiency for control.Experiments cover cart-pole balancing and acrobot swing-up, comparing Fast-AHC with conventional AHC and AHC using LS-TD(λ).

2. Previous Work on Linear Temporal-Difference Algorithms

Prior linear TD(λ) methods use eligibility traces and linear value approximators but can require step-size design and inefficient computation. Least-squares methods address these issues, although LS-TD(λ) remains costly for online learning.

  • Linear TD(λ): Eligibility traces improve learning efficiency by representing multi-step prediction information without recording all data in the trajectory.TD(λ) combines temporal differences with eligibility traces based on truncated returns.
  • Linear TD(λ): Linear TD(λ) estimates value functions with fixed basis functions and updates their weights incrementally from temporal differences and eligibility traces.The value estimate is represented by a weighted linear combination of basis functions.
  • Limitations of prior methods: LS-TD(λ) requires O(K^3) computation per time step, making its cost grow rapidly with the number K of state features.This computational burden is undesirable for online learning.
  • Motivation for RLS-TD(λ): RLS-TD(λ) is introduced to reduce LS-TD(λ)'s computational burden from O(K^3) to O(K^2) while providing a probability-one convergence analysis.The method uses recursive least squares to make the multi-step algorithm more suitable for online learning.

3. The RLS-TD( Ȝ ) Algorithm

RLS-TD(λ) applies recursive least-squares updates with eligibility traces to linear value-function estimation. Under stated assumptions for ergodic Markov chains, it converges almost surely to the same limiting solution characterized for linear TD(λ).

  • Algorithm: The algorithm recursively updates the weight vector, variance matrix, and eligibility traces from observed transitions and rewards.For ergodic chains, each iteration observes a transition, applies the RLS-TD(λ) updates, and continues until termination.
  • Algorithm: For absorbing Markov chains, absorbing-state updates use terminal rewards and the process is reinitialized to transform the chain into an equivalent ergodic chain.Eligibility traces are reset after reinitialization, so convergence analysis focuses on ergodic chains.
  • Convergence analysis: The approximation-error bound is smallest at λ=1 and worsens as λ decreases, reaching its worst bound at λ=0.These are bounds on the distance between the limiting function and the true value function.
  • Initialization effects: The initial variance-matrix constant δ affects transient performance, while LS-TD(λ) and RLS-TD(λ) approach nearly the same final solutions with sufficiently long data.A relatively small initialization can yield faster convergence in some cases, whereas large initialization makes RLS behavior resemble LS methods.

4. Learning Prediction Experiments on Markov Chains

Experiments on the 13-state Hop-World absorbing Markov chain evaluate RLS-TD(λ) against conventional TD(λ) and LS-TD(λ). Results show that initialization of the variance matrix and λ strongly affect convergence, while RLS-TD(λ) offers online computational advantages.

  • Effect of initialization: Larger initial variance-matrix values substantially improve RLS-TD(λ) performance in the Hop-World experiments.With μ=0.995, RLS-TD(λ) using a large initial value performs much better than using a small value; similar effects are observed for μ=1.
  • Effect of λ and initialization: When the initial variance value is small, convergence becomes slower as λ decreases, and performance is sensitive to both initialization and λ.The experiments report faster convergence as λ increases from 0 to 1 under small initialization, while smaller initialization deteriorates performance at fixed λ.
  • Comparison with LS-TD(λ): With large initialization, RLS-TD(λ) approaches LS-TD(λ), whose long-term convergence performance may be preferable in some cases.The reported comparison uses P0=500I for RLS-TD(λ); the paper distinguishes RLS-TD(λ)'s transient and computational advantages from LS-TD(λ)'s possible long-term advantage.
  • Comparison with conventional TD(λ): RLS-TD(λ) outperforms conventional linear TD(λ) in value-function prediction while replacing step-size scheduling with variance-matrix initialization.The experiments compare online TD(λ) schedules with RLS-TD(λ), whose initial variance parameter can be selected as relatively large or small.
  • Computational considerations: RLS-TD(λ) requires O(K^2) computation per step, compared with O(K^3) for LS-TD(λ), where K is the number of state features.This computational difference is presented as an advantage for online applications.

5. The Fast-AHC Algorithm and Two Learning Control Experiments

Fast-AHC applies RLS-TD(λ) in the critic of an actor–critic system to improve learning prediction and control efficiency. Across cart-pole and acrobot experiments, it uses fewer trials or data than conventional AHC, although performance depends on the variance-matrix initialization.

  • 5.1 The Fast-AHC Algorithm: Fast-AHC uses RLS-TD(λ) in the critic to improve learning prediction and solve learning-control problems within an actor–critic architecture.The critic estimates the actor’s policy value and supplies internal reinforcement signals, while the actor selects actions from state and critic estimates.
  • 5.2 Learning Control Experiments on The Cart-Pole Balancing Problem: Fast-AHC requires more computation per step than AHC but uses fewer trials or less data to successfully balance the pole.
  • 5.2 Learning Control Experiments on The Cart-Pole Balancing Problem: In the cart-pole experiment, large variance-matrix initialization values of δ, such as 100 or 500, significantly deteriorate Fast-AHC performance.With large initialization, Fast-AHC behaves similarly to AHC using LS-TD(λ), and both perform worse than Fast-AHC with small δ.
  • 5.3 Learning Control Experiments of The Acrobot: Fast-AHC achieves higher data efficiency than AHC in the acrobot swing-up experiment.The experiment compares Fast-AHC settings with different values of G and also includes AHC using LS-TD(λ).
  • 5.4 Analysis of The Experimental Results: The preferred variance-matrix initialization differs by task: small δ benefits cart-pole control, whereas relatively large δ improves acrobot data efficiency.The paper relates these contrasting behaviors to different signal-to-noise conditions and identifies fuller theoretical analysis as future work.
  • 5.4 Analysis of The Experimental Results: Fast-AHC with large initialization has performance similar to AHC using LS-TD(λ).

6. Conclusions and Future Work

The paper proposes RLS-TD(λ) and Fast-AHC, extending efficient prediction to actor-critic control while proving convergence and identifying initialization sensitivity. Experiments report improved data efficiency, but the best initialization varies by task and further theoretical study remains open.

  • Contributions: RLS-TD(λ) is proposed with probability-one convergence analysis, while Fast-AHC applies it in the critic to improve learning-control data efficiency.The methods are evaluated in prediction and in pole-balancing and acrobot control.
  • Learning prediction: RLS-TD(λ) outperforms conventional TD(λ) in data efficiency, removes step-size design, and is computationally superior to LS-TD(λ) for per-observation updates.
  • Learning control: Fast-AHC achieves better data efficiency than conventional AHC in pole-balancing and acrobot experiments.
  • Initialization sensitivity: Different initializing constants δ are required for best RLS-TD(λ) and Fast-AHC performance in different cases.
  • Future work: A complete investigation of initialization effects is left for future work, although existing RLS theory provides some explanatory basis.
  • Future work: RLS-TD(λ) may also be useful in other actor-critic methods whose convergence requires a faster-converging critic.

Appendix A. Derivation of the RLS-TD(Ȝ) Algorithm

The appendix derives RLS-TD(λ) in separate unit-forgetting and forgetting-factor cases, presenting recursive updates based on the RLS formulation.

  • Derivation cases: The derivation distinguishes RLS-TD(λ) with a unit forgetting factor from the case with forgetting factor μ<1.
  • Forgetting-factor case: For μ<1, the derivation follows exponentially weighted RLS and presents the resulting recursive expressions.
  • Unit-forgetting case: The unit-forgetting derivation specifies recursive updates involving the parameter vector, covariance matrix, gain, and eligibility-related quantities.

Appendix B. Proof of Theorem 1

The proof constructs a stationary Markov-chain process, establishes finite expectations and invertibility, and concludes probability-one convergence of RLS-TD(λ) to W*.

  • Stationary process: The proof places the Markov chain in steady state and forms a stationary process containing the state, successor state, and eligibility-related variables.
  • Supporting lemmas: The appendix invokes established expectation identities involving the stationary distribution matrix D and transition-related quantities.
  • Limit characterization: The expected matrix E0[A(Xt)] is finite, negative definite, and therefore invertible, enabling the limiting expression for W*.

Appendix C. Some details of the coding structures of CMAC networks

The appendix specifies CMAC coding structures for cart-pole balancing and acrobot swing-up, including tilings, state bounds, hashing, and memory sizes for actor and critic networks.

  • Cart-pole coding: The cart-pole CMAC designs use four tilings, seven intervals per input, and separate actor and critic memory configurations.The actor memory size is 100; the critic memory size is 30 in the detailed configurations.
  • Cart-pole coding: Cart-pole state variables are assigned explicit position, angle, and velocity bounds for the CMAC representations.
  • Acrobot coding: The acrobot simulation bounds its angles and angular velocities, with four tilings used for both actor and critic networks.
  • Cart-pole coding: The cart-pole tilings use non-uniform critic partitions with explicitly listed breakpoint sets for the represented inputs.
Loading 1106.0707v1…