Least-Squares Policy Iteration

Michail G. LagoudakisRonald Parr

article2003JMLR1,504 citations

Proposes Least-Squares Policy Iteration (LSPI), a model-free, off-policy reinforcement learning algorithm that combines linear state-action value function approximation with approximate policy iteration to achieve highly sample-efficient control without requiring manually tuned learning rates.

Listen

Real-world autonomous decision-making and optimal control problems often involve complex, continuous environments where the underlying system dynamics are not fully known in advance. Traditional reinforcement learning methods frequently require vast amounts of trial data and rely on sensitive parameters, such as learning rates, which can cause erratic performance, slow convergence, or outright mathematical divergence when applied to large-scale systems.

The article develops and evaluates Least-Squares Policy Iteration, a model-free control algorithm designed to discover high-performing decision policies efficiently from sample data. The method combines linear value-function approximation with approximate policy iteration to eliminate sensitive learning rate tuning and improve sample efficiency.

The researchers assessed the approach through computer simulations on standard benchmark control tasks: balancing an inverted pendulum and balancing and riding a bicycle 1 kilometer to a target location. The algorithm learned decision policies using pre-collected datasets generated from purely random action selections, reusing the exact same data across iterations rather than discarding samples after a single pass. For comparison, benchmark tests were conducted against standard Q-learning and Q-learning enhanced with experience replay across identical linear architectures.

The evaluation revealed several critical findings. First, Least-Squares Policy Iteration reliably learned successful controllers using a single batch of randomly sampled trials, achieving an average balance duration of approximately 2,850 out of 3,000 maximum possible steps on the inverted pendulum with 1,000 training episodes. Second, on the difficult bicycle navigation task, the algorithm achieved an approximate 95% success rate in reaching the goal within 5,000 training episodes, typically converging to near-optimal riding paths in only 6 to 8 iterations. In contrast, standard Q-learning failed to balance the bicycle for more than a few dozen steps, and while experience replay improved balance duration, it could not navigate the bicycle to the goal and showed high variance.

These findings demonstrate that direct, least-squares fixed-point projection avoids the instability and gradient-step overshooting common to traditional algorithms. By efficiently reusing data and implicitly deriving policies without requiring an explicit policy model, the approach significantly lowers the data collection burden and operational risk in complex control settings.

Organizations evaluating automated control systems should consider least-squares methods as a reliable baseline when sample collection is expensive or risky. Future development should focus on active sampling techniques to ensure adequate coverage of critical system states, extending the architecture to continuous action spaces, and developing online adaptations that can handle slowly changing environments.

Readers should note that the performance of the algorithm remains dependent on the initial feature design and whether the sampled training data adequately cover the operational state space. While confidence in the reported benchmark stability is high, deploying the method on new industrial domains will require careful feature engineering until automated basis selection mechanisms are developed.

Duke University action selection control problems function approximation least-squares policy iteration approximate policy iteration least-squares temporal-difference learning

Lagoudakis et al (2003).pdf

Paper: Q-learning, CHRISTOPHER J.C.H. WATKINS et al. (1992). This foundational paper introduces model-free Q-learning and establishes its convergence properties, providing the core state-action value concepts that LSPI extends into approximate policy iteration.
Paper: Learning to Predict by the Methods of Temporal Differences, Richard S. Sutton (1988). This paper establishes the principles of temporal-difference learning with linear architectures, serving as the direct intellectual ancestor to LSTD and the least-squares projection mechanisms adapted by LSPI.
Paper: Self-improving reactive agents based on reinforcement learning, planning and teaching, Longxin Lin (1992). This work introduces experience replay to reinforcement learning, establishing sample reuse techniques that LSPI formalizes and evaluates against within batch learning settings.
Paper: Reinforcement Learning: A Survey, Leslie Pack Kaelbling et al. (1996). This comprehensive survey provides the standard formulations of Markov decision processes, value iteration, and model-free policy control necessary for contextualizing LSPI.
Paper: Actor-Critic Algorithms, Vijay Konda et al. (1999). This paper develops actor-critic architectures and temporal-difference critics under linear function approximation, offering essential background on policy evaluation with linear bases.
Paper: Policy Gradient Methods for Reinforcement Learning with Function Approximation, Richard S. Sutton et al. (1999). This work formalizes policy gradient theory and function approximation conditions, representing the key alternative paradigm to value-function approximate policy iteration.
Paper: A Natural Policy Gradient, Sham M. Kakade (2001). This paper connects natural policy gradients directly to approximate policy iteration with linear function approximation, clarifying the geometry of policy updates.

Paper: Off-Policy Deep Reinforcement Learning without Exploration, Scott Fujimoto et al. (2018). This paper tackles extrapolation error and instability in offline, batch reinforcement learning, directly addressing the limitations of unconstrained off-policy learning methods like LSPI.
Paper: Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems, Sergey Levine et al. (2020). This tutorial synthesizes the theoretical and practical foundations of offline reinforcement learning that originated with early batch, off-policy methods like LSPI.
Paper: Conservative Q-Learning for Offline Reinforcement Learning, Aviral Kumar et al. (2020). This work develops conservative value bounds to stabilize batch off-policy learning over static datasets without requiring live environmental interaction.
Paper: Offline Reinforcement Learning with Implicit Q-Learning, Ilya Kostrikov et al. (2021). This paper presents an offline reinforcement learning approach using expectile regression to perform multi-step dynamic programming without evaluating out-of-distribution actions.
Paper: Double Q-learning, Hado van Hasselt (2010). This paper analyzes and corrects the systematic overestimation bias inherent in standard max-operator action-value methods like Q-learning and policy iteration.
Paper: Deterministic Policy Gradient Algorithms, David Silver et al. (2014). This work develops deterministic policy gradient algorithms for continuous action spaces, offering a policy-based counterpart to linear value-function control methods.
Paper: Trust Region Policy Optimization, John Schulman et al. (2015). This paper introduces trust-region constraints to ensure monotonic policy improvements, providing a robust modern alternative to approximate policy iteration.
Paper: Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor, Tuomas Haarnoja et al. (2018). This paper unifies maximum-entropy exploration with off-policy actor-critic learning and experience reuse in continuous state and action domains.

Cover for Least-Squares Policy Iteration

Abstract

We propose a new approach to reinforcement learning for control problems which combines value-function approximation with linear architectures and approximate policy iteration. This new approach is motivated by the least-squares temporal-difference learning algorithm (LSTD) for prediction problems, which is known for its efficient use of sample experiences compared to pure temporal-difference algorithms. Heretofore, LSTD has not had a straightforward application to control problems mainly because LSTD learns the state value function of a fixed policy which cannot be used for action selection and control without a model of the underlying process. Our new algorithm, least-squares policy iteration (LSPI), learns the state-action value function which allows for action selection without a model and for incremental policy improvement within a policy-iteration framework. LSPI is a model-free, off-policy method which can use efficiently (and reuse in each iteration) sample experiences collected in any manner. By separating the sample collection method, the choice of the linear approximation architecture, and the solution method, LSPI allows for focused attention on the distinct elements that contribute to practical reinforcement learning. LSPI is tested on the simple task of balancing an inverted pendulum and the harder task of balancing and riding a bicycle to a target location. In both cases, LSPI learns to control the pendulum or the bicycle by merely observing a relatively small number of trials where actions are selected randomly. LSPI is also compared against Q-learning (both with and without experience replay) using the same value function architecture. While LSPI achieves good performance fairly consistently on the difficult bicycle task, Q-learning variants were rarely able to balance for more than a small fraction of the time needed to reach the target location.

Topics

action selection control problems function approximation genetic selection policy iteration q-learning temporal differences value function approximation solution methods model free

Keywords

least-squares policy iteration approximate policy iteration least-squares temporal-difference learning Markov decision processes linear approximation architecture policy evaluation policy improvement actor-critic architecture

1. Introduction
2. Markov Decision Processes
3. Policy Iteration and Approximate Policy Iteration
4. Reinforcement Learning and Approximate Policy Iteration
5. Value-Function Approximation using Linear Architectures
5.1 Bellman Residual Minimizing Approximation
5.2 Least-Squares Fixed-Point Approximation
5.3 Comparison of Projection Methods
6. LSTDQ: Least-Squares Temporal-Difference Learning for the State-Action Value Function
7. LSPI: Least-Squares Policy Iteration
8. Comparison to Other Methods
9. Experimental Results
9.1 Chain Walk
9.2 Inverted Pendulum
9.3 Bicycle Balancing and Riding
10. Future Work
11. Conclusion
Acknowledgments
References

Knowls

Knowl 1 — Least-Squares Policy Iteration Algorithm
algorithm
Least-Squares Policy Iteration (LSPI) is a model-free, off-policy reinforcement learning algorithm for finding optimal control policies in Markov decision processes (MDPs) with large or continuous state spaces and discrete action spaces. LSPI represents the state-action value function $Q(s, a)$ as a linear combination of $k$ fixed basis functions, $\hat{Q}(s, a; w) = \phi(s, a)^\top w$ , where $\phi(s, a) \in \mathbb{R}^k$ is a feature vector and $w \in \mathbb{R}^k$ is a parameter vector. Policies are represented implicitly through $w$ via greedy action selection: $\pi(s; w) = \arg\max_{a \in \mathcal{A}} \phi(s, a)^\top w$ .

LSPI iteratively evaluates the current policy using the LSTDQ algorithm on a fixed collection of transition samples $D = \{(s_i, a_i, r_i, s'_i)\}_{i=1}^L$ and updates the parameter vector until convergence.
LSPI(D, k, $\phi$ , $\gamma$ , $\epsilon$ , $w_0$ )
    Input: Dataset of transitions $D = \{(s_i, a_i, r_i, s'_i)\}_{i=1}^L$
    Input: Number of basis functions $k$
    Input: Basis function vector $\phi : \mathcal{S} \times \mathcal{A} \to \mathbb{R}^k$
    Input: Discount factor $\gamma \in [0, 1)$
    Input: Convergence threshold $\epsilon > 0$
    Input: Initial weight vector $w_0 \in \mathbb{R}^k$ (default: $w_0 = 0$ )
    Output: Learned parameter vector $w \in \mathbb{R}^k$
     $w' \leftarrow w_0$
    repeat
         $w \leftarrow w'$
         $w' \leftarrow \text{LSTDQ}(D, k, \phi, \gamma, w)$
    until $\|w - w'\| < \epsilon$
    return $w$
Because the policy is defined dynamically by maximizing over action values at query time, LSPI eliminates policy representation approximation errors entirely. The sample set $D$ can be gathered using any exploratory policy (e.g., uniform random actions) and reused across all policy iteration steps.
Knowl 2 — LSTDQ Algorithm for State-Action Value Function Evaluation
algorithm
Least-Squares Temporal-Difference Learning for State-Action Values (LSTDQ) computes the linear least-squares fixed-point approximation of the state-action value function $Q^\pi(s,a) \approx \phi(s,a)^\top w^\pi$ for a fixed policy $\pi$ directly from transition samples without requiring a model of the MDP.

Given a dataset of $L$ transition samples $D = \{(s_i, a_i, r_i, s'_i)\}_{i=1}^L$ , basis functions $\phi(s, a) \in \mathbb{R}^k$ , and discount factor $\gamma \in [0, 1)$ , LSTDQ estimates the matrix $\tilde{A} \in \mathbb{R}^{k \times k}$ and vector $\tilde{b} \in \mathbb{R}^k$ by summing empirical outer products, and then solves the linear system $\tilde{A} w^\pi = \tilde{b}$ :
LSTDQ(D, k, $\phi$ , $\gamma$ , $\pi$ )
    Input: Dataset of transitions $D = \{(s_i, a_i, r_i, s'_i)\}_{i=1}^L$
    Input: Number of basis functions $k$
    Input: Basis function vector $\phi : \mathcal{S} \times \mathcal{A} \to \mathbb{R}^k$
    Input: Discount factor $\gamma \in [0, 1)$
    Input: Policy $\pi$ (defined either explicitly or implicitly via parameter vector $w$ )
    Output: Parameter vector $\tilde{w}^\pi \in \mathbb{R}^k$
     $\tilde{A} \leftarrow 0_{k \times k}$
     $\tilde{b} \leftarrow 0_{k \times 1}$
    for each $(s, a, r, s') \in D$ do
         $a' \leftarrow \pi(s') = \arg\max_{a \in \mathcal{A}} \phi(s', a)^\top w$
         $\tilde{A} \leftarrow \tilde{A} + \phi(s, a) (\phi(s, a) - \gamma \phi(s', a'))^\top$
         $\tilde{b} \leftarrow \tilde{b} + \phi(s, a) r$
    end for
     $\tilde{w}^\pi \leftarrow \tilde{A}^{-1} \tilde{b}$
    return $\tilde{w}^\pi$
The computational complexity per policy evaluation is $O(L k^2 + k^3)$ , and the memory complexity is $O(k^2)$ beyond the storage of sample dataset $D$ . Singular value decomposition (SVD) or ridge regularization (initializing $\tilde{A} = \delta I$ for small $\delta > 0$ ) can be used to guarantee invertibility.
Knowl 3 — Recursive Least-Squares Implementation of LSTDQ (LSTDQ-OPT)
algorithm
When LSTDQ is evaluated incrementally or frequently, explicit matrix inversion of the $k \times k$ matrix $\tilde{A}$ can be avoided by maintaining and updating its inverse matrix $\tilde{B} = \tilde{A}^{-1}$ recursively using the Sherman-Morrison formula. This reduces the computational cost of solving the linear system from $O(k^3)$ to $O(k^2)$ operations per sample.
LSTDQ-OPT(D, k, $\phi$ , $\gamma$ , $\pi$ , $\delta$ )
    Input: Dataset of transitions $D = \{(s_i, a_i, r_i, s'_i)\}_{i=1}^L$
    Input: Number of basis functions $k$
    Input: Basis function vector $\phi : \mathcal{S} \times \mathcal{A} \to \mathbb{R}^k$
    Input: Discount factor $\gamma \in [0, 1)$
    Input: Policy $\pi$
    Input: Regularization parameter $\delta > 0$
    Output: Parameter vector $\tilde{w}^\pi \in \mathbb{R}^k$
     $\tilde{B} \leftarrow \frac{1}{\delta} I_{k \times k}$
     $\tilde{b} \leftarrow 0_{k \times 1}$
    for each $(s, a, r, s') \in D$ do
         $a' \leftarrow \pi(s')$
         $\Delta \phi \leftarrow \phi(s, a) - \gamma \phi(s', a')$
         $\tilde{B} \leftarrow \tilde{B} - \frac{\tilde{B} \phi(s, a) (\Delta \phi)^\top \tilde{B}}{1 + (\Delta \phi)^\top \tilde{B} \phi(s, a)}$
         $\tilde{b} \leftarrow \tilde{b} + \phi(s, a) r$
    end for
     $\tilde{w}^\pi \leftarrow \tilde{B} \tilde{b}$
    return $\tilde{w}^\pi$
The total computational complexity for evaluating a policy over $L$ samples becomes $O(L k^2)$ .
Knowl 4 — Performance Bound for Least-Squares Policy Iteration
theoretical result
Let $\pi_0, \pi_1, \pi_2, \dots, \pi_m$ be the sequence of policies generated by LSPI, let $\hat{Q}^{\pi_m}$ be the corresponding approximate state-action value functions computed by LSTDQ at iteration $m$ , and let $Q^*$ be the optimal state-action value function. Suppose the value-function approximation error across all iterations is uniformly bounded by a positive scalar $\epsilon$ :

$\forall m = 1, 2, \dots, \quad \|\hat{Q}^{\pi_m} - Q^{\pi_m}\|_\infty \le \epsilon$

Because LSPI represents policies implicitly by greedy action selection over $\hat{Q}^{\pi_m}$ without policy projection or representation error (that is, policy improvement error $\delta = 0$ ), the asymptotic performance loss of the generated policies is bounded by:

$\limsup_{m \to \infty} \|\hat{Q}^{\pi_m} - Q^*\|_\infty \le \frac{2\gamma \epsilon}{(1 - \gamma)^2}$

where $\gamma \in [0, 1)$ is the MDP discount factor. This bound guarantees that LSPI is stable: it either converges to a fixed policy or oscillates within a bounded region of policy space whose suboptimality is proportional to the approximation error $\epsilon$ .
Knowl 5 — Comparison of Fixed-Point and Bellman Residual Minimization Projections
model/method
In linear value-function approximation $\hat{Q} = \Phi w$ , two distinct projection principles can be used to determine the parameter vector $w$ :
1. Least-Squares Fixed-Point (LSFP) Approximation: Forces $\hat{Q}$ to be invariant under one application of the Bellman operator $T_\pi$ followed by orthogonal projection onto the subspace spanned by $\Phi$ : $\hat{Q} = \Phi (\Phi^\top \Phi)^{-1} \Phi^\top T_\pi \hat{Q} \implies \Phi^\top (\Phi - \gamma P \Pi_\pi \Phi) w = \Phi^\top R$
2. Bellman Residual Minimization (BRM): Minimizes the $L_2$ norm of the Bellman residual $\|\hat{Q} - T_\pi \hat{Q}\|_2^2$ : $(\Phi - \gamma P \Pi_\pi \Phi)^\top (\Phi - \gamma P \Pi_\pi \Phi) w = (\Phi - \gamma P \Pi_\pi \Phi)^\top R$
Sample Requirements Difference: Estimating the BRM system matrix from samples requires computing terms of the form $(\phi(s,a) - \gamma \phi(s'', \pi(s''))) (\phi(s,a) - \gamma \phi(s', \pi(s')))^\top$ , where $s'$ and $s''$ are two independent next-state transitions drawn from $P(s,a,\cdot)$ for the exact same state-action pair $(s,a)$ . Thus, BRM strictly requires 'doubled' samples from a generative simulator and cannot learn from single trajectory experiences. In contrast, LSFP estimates require only a single transition $(s, a, r, s')$ per sample summand, making LSFP practical for model-free learning directly from observed process paths.

Knowl 6 — Contrasting Characteristics of LSTD and LSTDQ

model/method

LSTD and LSTDQ differ fundamentally in the target value function, sample usability, and applicability to control problems without a transition model:

Property	LSTD	LSTDQ
Target value function	State value function $V^\pi(s)$	State-action value function $Q^\pi(s,a)$
Basis function inputs	State features $\phi(s)$	State-action features $\phi(s,a)$
Sample reuse	Samples cannot be reused across policies	Samples can be reused across all policies
Sample generation	Must follow policy $\pi$	Collected under arbitrary behavior policy
Sampling distribution	Biased by stationary distribution of $\pi$	Biased by sample dataset distribution $\mu_D$
Model requirement for control	Requires MDP transition model $P$	Model-free greedy action selection

By evaluating state-action pairs, LSTDQ allows greedy action selection $\pi'(s) = \arg\max_a \phi(s,a)^\top w$ without needing transition probabilities $P(s,a,s')$ , enabling model-free approximate policy iteration.

Knowl 7 — Model-Based Formulation of LSTDQ
algorithm
When a compact transition model $P(s, a, s')$ and reward function $R(s, a)$ are available, LSTDQ computes exact conditional expectations over next states $s'$ rather than estimating them by empirical sample transitions:
LSTDQ-Model(D, k, $\phi$ , $\gamma$ , $\pi$ , P, R)
    Input: Dataset of state-action query points $D = \{(s_i, a_i)\}_{i=1}^L$
    Input: Number of basis functions $k$
    Input: Basis function vector $\phi : \mathcal{S} \times \mathcal{A} \to \mathbb{R}^k$
    Input: Discount factor $\gamma \in [0, 1)$
    Input: Policy $\pi$
    Input: Transition probability model $P(s, a, s')$
    Input: Reward function $R(s, a)$
    Output: Parameter vector $\tilde{w}^\pi \in \mathbb{R}^k$
     $\tilde{A} \leftarrow 0_{k \times k}$
     $\tilde{b} \leftarrow 0_{k \times 1}$
    for each $(s, a) \in D$ do
         $\tilde{A} \leftarrow \tilde{A} + \phi(s, a) \left( \phi(s, a) - \gamma \sum_{s' \in \mathcal{S}} P(s, a, s') \phi(s', \pi(s')) \right)^\top$
         $\tilde{b} \leftarrow \tilde{b} + \phi(s, a) R(s, a)$
    end for
     $\tilde{w}^\pi \leftarrow \tilde{A}^{-1} \tilde{b}$
    return $\tilde{w}^\pi$
This eliminates sampling variance in the updates of $\tilde{A}$ and $\tilde{b}$ when the number of reachable next states $s'$ is small.
Knowl 8 — Empirical Performance on Inverted Pendulum Balancing Benchmark
empirical result
LSPI was evaluated on the inverted pendulum balancing task with 2D continuous state $(\theta, \dot{\theta})$ (vertical angle and angular velocity) and 3 discrete actions $\mathcal{A} = \{-50\text{ N}, 0\text{ N}, +50\text{ N}\}$ with additive uniform control noise in $[-10, 10]$ N. The discount factor was $\gamma = 0.95$ , simulation step was $0.1$ s, reward was $0$ while $|\theta| \le \pi/2$ , and $-1$ on termination ( $|\theta| > \pi/2$ ). The linear architecture used 10 basis functions per action (a constant plus a $3 \times 3$ grid of Gaussian RBFs with $\sigma^2 = 1$ centered at $\{-\pi/4, 0, \pi/4\} \times \{-1, 0, 1\}$ ), totaling $k = 30$ basis functions.

Training data consisted of short random-walk episodes (mean length $\approx 6$ steps) initialized near equilibrium $(0,0)$ . Evaluation ran for up to 3000 steps (5 minutes of real-time balancing):
- LSPI: Achieved an average of $\approx 2850$ balancing steps with 1000 training episodes (converging within 20 iterations using the exact same sample set). Excellent policies balancing for 3000 steps were found with as few as 50-100 episodes.
- Standard Q-learning: Using the identical linear architecture and an optimized decreasing learning rate schedule (initial $\alpha_0 = 0.5$ , final $\alpha = 0.01$ ), Q-learning failed to balance the pendulum for more than $\approx 40$ steps after 1000 training episodes.
- Q-learning with Experience Replay (ER): Making 100 passes over the samples achieved performance comparable to LSPI (nearly 3000 balancing steps at 700+ episodes), benefiting from the well-behaved, localized nature of Gaussian RBFs.
Knowl 9 — Empirical Performance on Bicycle Balancing and Riding Benchmark
empirical result
LSPI was tested on riding and balancing a bicycle toward a goal 1 km away from a starting angle of $90^\circ$ relative to the goal. The state is 6-dimensional $(\theta, \dot{\theta}, \omega, \dot{\omega}, \ddot{\omega}, \psi)$ representing handlebar angle, bicycle vertical angle, and angle to goal. Five discrete actions were used (handlebar torques $\tau \in \{-2, 0, +2\}$ N $\cdot$ m or displacement $v \in \{-0.02, 0, +0.02\}$ m) with uniform noise in $[-0.02, +0.02]$ m on displacement. A linear architecture with 20 basis functions per action (total $k = 100$ ) was employed, ignoring $\ddot{\omega}$ . Trajectories were truncated at 20 steps to prevent sample contamination by unrecoverable falling states, using potential-based shaping rewards with $\gamma = 0.8$ .
- LSPI: Converged in 6 to 8 iterations. With 5000 training episodes ( $60{,}000$ transitions), LSPI achieved a $\approx 95\%$ success rate (reaching the 1 km goal within 72,000 simulation steps / 2 km distance cap) and an average of $\approx 70{,}000$ balancing steps. Successful runs navigated to the goal in just over 1 km of path length.
- Q-learning (single pass) and Q-learning with Experience Replay (100 passes): Both failed to ride the bicycle to the goal. Even with normalized features and extensive learning rate schedule tuning (initial $\alpha_0 = 0.5$ , final $\alpha = 0.005$ ), Q-learning averaged under 1500 balancing steps with high variance, failing to learn coordinated steering and balancing.
Knowl 10 — Resolution of Approximate Policy Iteration Oscillation on 4-State Chain MDP
empirical result
On a 4-state Markov decision process with states $\{1, 2, 3, 4\}$ , actions $\{\text{Left}, \text{Right}\}$ , transition success probability $0.9$ , state rewards $(0, +1, +1, 0)$ , and $\gamma = 0.9$ , state-value approximate policy iteration using LSTD with basis functions $(1, s, s^2)^\top$ is known to oscillate indefinitely between suboptimal policies RRRR and LLLL (Koller and Parr, 2000) due to shifts in the state visitation distribution.

LSPI resolves this instability by approximating state-action values using 6 basis functions (the 3 polynomial terms replicated per action via indicator functions) over 50 samples collected under a uniform random walk. LSPI consistently converges to the true optimal policy RRLL within 4 to 5 iterations. The uniform sample distribution decouples the policy evaluation projection weighting from the evaluated policy's visitation frequencies.

Coverage note — None was omitted; all contributed algorithms (LSPI, LSTDQ, LSTDQ-OPT, LSTDQ-Model), theoretical bounds (Theorem 7.1), foundational comparison of projection methods (LSFP vs BRM), and empirical evaluations (4-state chain, 20/50-state chains, inverted pendulum, and bicycle benchmark) are covered.

References

1.Andrew G. Barto, Richard S. Sutton, and Charles W. Anderson. Neuronlike adaptive elements that can solve difficult learning control problems. IEEE Transactions on Systems, Man, and Cybernetics, 13(5):835–846, 1983.
2.Jonathan Baxter and Peter L. Bartlett. Infinite-horizon gradient-based policy search. Journal of Artificial Intelligence Research, 15:319–350, 2001.
3.Dimitri P. Bertsekas and John N. Tsitsiklis. Neuro-Dynamic Programming. Athena Scientific, Belmont, Massachusetts, 1996.
4.Justin A. Boyan. Technical update: Least-squares temporal difference learning. Machine Learning, 49(2-3):233–246, 2002.
5.Steven J. Bradtke. Reinforcement learning applied to linear quadratic regulation. In Advances in Neural Information Processing Systems 5: Proceedings of the 1992 Conference, pages 295–302, Denver, Colorado, 1993.
6.Steven J. Bradtke and Andrew G. Barto. Linear least-squares algorithms for temporal difference learning. Machine Learning, 22(2):33–57, 1996.
7.Arthur P. Dempster, Martin Schatzoff, and Nanny Wermuth. A simulation study of alternatives to ordinary least-squares. Journal of the American Statistical Association, 72 (357):77–91, 1977.
8.Ronald A. Howard. Dynamic Programming and Markov Processes. MIT Press, Cambridge, Massachusetts, 1960.
9.Daphne Koller and Ronald Parr. Policy iteration for factored MDPs. In Proceedings of the Sixteenth Conference on Uncertainty in Artificial Intelligence, pages 326–334, Stanford, California, 2000.
10.Vijay R. Konda and John Tsitsiklis. Actor-critic algorithms. In Advances in Neural Information Processing Systems 12: Proceedings of the 1999 Conference, pages 1008–1014, Denver, Colorado, 2000.
11.Long-Ji Lin. Reinforcement Learning for Robots Using Neural Networks. PhD thesis, Carnegie Mellon University, Pittsburgh, Pennsylvania, 1993.
12.Remi Munos. Error bounds for approximate policy iteration. In Proceedings of the Twentieth International Conference on Machine Learning, pages 560–567, Washington, District of Columbia, 2003.
13.Angelia Nedic and Dimitri P. Bertsekas. Least-squares policy evaluation algorithms with linear function approximation. Discrete Event Dynamic Systems: Theory and Applications, 13(1–2):79–110, 2003.
14.Andrew Y. Ng, Daishi Harada, and Stuart Russell. Policy invariance under reward transformations: Theory and application to reward shaping. In Proceedings of the Sixteenth International Conference on Machine Learning, pages 278–287, Bled, Slovenia, 1999.
15.Andrew Y. Ng and Michael Jordan. PEGASUS: A policy search method for large MDPs and POMDPs. In Proceedings of the Sixteenth Conference on Uncertainty in Artificial Intelligence, pages 406–415, Stanford, California, 2000.
16.Andrew Y. Ng, Ronald Parr, and Daphne Koller. Policy search via density estimation. In Advances in Neural Information Processing Systems 12: Proceedings of the 1999 Conference, pages 1022–1028, Denver, Colorado, 2000.
17.Dirk Ormoneit and Saunak Sen. Kernel-based reinforcement learning. Machine Learning, 49(2–3):161–178, 2002.
18.Doina Precup, Richard Sutton, and Sanjoy Dasgupta. Off-policy temporal difference learning with function approximation. In Proceedings of the Eighteenth International Conference on Machine Learning, pages 417–424, Williamstown, Massachusetts, 2001.
19.Jette Randlov and Preben Alstrom. Learning to drive a bicycle using reinforcement learning and shaping. In Proceedings of The Fifteenth International Conference on Machine Learning, pages 463–471, Madison, Wisconsin, 1998.
20.Gavin A. Rummery and Mahesan Niranjan. On-line Q-learning using connectionist systems. Technical Report CUED/F-INFENG/TR 166, Engineering Department, Cambridge University, Cambridge, United Kingdom, 1994.
21.Paul J. Schweitzer and Abraham Seidmann. Generalized polynomial approximations in Markovian decision processes. Journal of Mathematical Analysis and Applications, 110 (6):568–582, 1985.
22.Richard Sutton and Andrew Barto. Reinforcement Learning: An Introduction. MIT Press, Cambridge, Massachusetts, 1998.
23.Richard Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems 12: Proceedings of the 1999 Conference, pages 1057– 1063, Denver, Colorado, 2000.
24.Richard S. Sutton. Temporal Credit Assignment in Reinforcement Learning. PhD thesis, University of Massachusetts, Amherst, Massachusetts, 1984.
25.Richard S. Sutton. Generalization in reinforcement learning: Successful examples using sparse coarse coding. In Advances in Neural Information Processing Systems 8: Proceedings of the 1995 Conference, pages 1038–1044, Denver, Colorado, 1996.
26.Hua O. Wang, Kazuo Tanaka, and Michael F. Griffin. An approach to fuzzy control of nonlinear systems: Stability and design issues. IEEE Transactions on Fuzzy Systems, 4 (1):14–23, 1996.
27.Christopher J. C. H. Watkins. Learning from Delayed Rewards. PhD thesis, Cambridge University, Cambridge, United Kingdom, 1989.
28.Ronald J. Williams and Leemon C. Baird. Tight performance bounds on greedy policies based on imperfect value functions. Technical Report NU-CCS-93-14, College of Computer Science, Northeastern University, Boston, Massachusetts, 1993.

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Least-Squares Policy Iteration

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Least-Squares Policy Iteration Algorithm

Knowl 2 — LSTDQ Algorithm for State-Action Value Function Evaluation

Knowl 3 — Recursive Least-Squares Implementation of LSTDQ (LSTDQ-OPT)

Knowl 4 — Performance Bound for Least-Squares Policy Iteration

Knowl 5 — Comparison of Fixed-Point and Bellman Residual Minimization Projections

Knowl 6 — Contrasting Characteristics of LSTD and LSTDQ

Knowl 7 — Model-Based Formulation of LSTDQ

Knowl 8 — Empirical Performance on Inverted Pendulum Balancing Benchmark

Knowl 9 — Empirical Performance on Bicycle Balancing and Riding Benchmark

Knowl 10 — Resolution of Approximate Policy Iteration Oscillation on 4-State Chain MDP

References

Access the Paper