Source-linked AI summary
Dyna-Style Planning with Linear Function Approximation and Prioritized Sweeping
Richard S. Sutton, Csaba Szepesvari, Alborz Geramifard, Michael P. Bowling
TL;DR
The paper addresses efficient online learning and planning for optimal control and value estimation over large state spaces. It extends Dyna with linear function approximation, generating imaginary experience and applying reinforcement-learning updates to it. The main theoretical result is convergence to a unique distribution-independent solution under stated conditions, with the policy-evaluation solution equal to LSTD; the paper also extends prioritized sweeping and evaluates it on two domains.
Problem
Online control requires updated estimates after each interaction, while planning over large state spaces is computationally difficult and prior linear-function-approximation planning work was limited.
Method
The paper extends the model-based Dyna architecture to linear function approximation and introduces prioritized-sweeping variants that back up to preceding features.
Results
Linear Dyna converges under natural conditions to a unique solution independent of the hypothetical-experience distribution, and policy evaluation reaches the LSTD solution.
Takeaways & Limitations
The results provide convergence and correctness guarantees for linear Dyna and support prioritized sweeping with linear approximation.
Takeaways & Limitations
The empirical results are preliminary, control theory is less clear than policy-evaluation theory, and asymptotic model-based and model-free performance can be identical under the paper’s structural assumptions.
Abstract
from arXiv · showhide
We consider the problem of efficiently learning optimal control policies and value functions over large state spaces in an online setting in which estimates must be available after each interaction with the world. This paper develops an explicitly model-based approach extending the Dyna architecture to linear function approximation. Dynastyle planning proceeds by generating imaginary experience from the world model and then applying model-free reinforcement learning algorithms to the imagined state transitions. Our main results are to prove that linear Dyna-style planning converges to a unique solution independent of the generating distribution, under natural conditions. In the policy evaluation setting, we prove that the limit point is the least-squares (LSTD) solution. An implication of our results is that prioritized-sweeping can be soundly extended to the linear approximation case, backing up to preceding features rather than to preceding states. We introduce two versions of prioritized sweeping with linear Dyna and briefly illustrate their performance empirically on the Mountain Car and Boyan Chain problems.
1 Online learning and planning
Online decision making requires repeatedly updating world models and plans, but full planning at every interaction is too slow for large problems. Dyna addresses this through incremental planning that interleaves acting, learning, and model-based generation of imaginary experience.
- Online learning and planning: Large online control problems require incremental planning because repeating complex planning after every interaction can greatly slow responses.The planning process must remain incomplete at each step while still computing optimal actions in a timely manner.
- Dyna architecture: Dyna maintains responsiveness by running planning, acting, and learning continually, with their time allocation adjusted to available resources.
- Dyna architecture: Dyna planning generates imaginary experience from the learned model and processes its transitions with model-free reinforcement-learning algorithms.Under various conditions, infinite imaginary experience produces the same limiting results as dynamic programming.
- Motivation: Tabular Dyna methods are limited to relatively small problems, motivating extension to linear function approximation for larger state spaces.The paper identifies linear function approximation as the most popular form of function approximation in reinforcement learning.
- Related work: Previous online planning work with linear function approximation was limited, including stochastic cascading models and structured value-iteration systems.
2 Notation
The paper represents reinforcement-learning experience through states, actions, rewards, and feature vectors, then approximates policy value functions linearly. Policies select actions from feature vectors, including greedy and ϵ-greedy policies.
- Notation: Experience is a time-indexed stream of states, actions, rewards, and successor states generated by an agent interacting with a stationary environment.
- Notation: The agent observes each state through a feature vector φ_t ∈ R^n rather than directly accessing the state.
- Notation: The value function for a policy is approximated as a linear function with parameter vector θ ∈ R^n.
- Notation: The considered policies are greedy or ϵ-greedy with respect to the approximate state-value function.
- Linear Dyna algorithm: Algorithm 1 performs p planning repetitions, sampling a feature and updating θ with a TD-style reward-and-next-feature error.
3 Theory for policy evaluation
For linear policy evaluation, Dyna-style TD and residual-gradient updates converge under matrix and sampling conditions to a unique fixed point independent of the feature-generating distribution. With a fitted linear model, that fixed point is the LSTD solution.
- Policy-evaluation setup: Policy-evaluation planning uses a forward transition matrix F and reward vector b to generate successor features and expected rewards from sampled starting features.The sampling distribution μ generates the starting feature vectors for planning.
- Policy-evaluation updates: The TD error combines sampled reward, discounted predicted successor value, and current predicted value in the planning update.The residual-gradient alternative is also considered, alongside a complete TD(0) algorithm with model learning.
- Convergence and fixed point: Linear Dyna convergence and its limit are unaffected by μ when μ exercises all directions in the full feature space; both depend on F.The limit is a deterministic fixed point whose TD error is zero for every feature that μ can generate.
- Convergence and fixed point: The TD fixed point is independent of μ, while an existing fixed point can fail when the model makes feature vectors diverge over time.Such cases are described as ill-posed planning problems rather than failures of the Dyna iterations.
- Convergence and fixed point: Under TD(0), bounded i.i.d. features, nonsingular C, suitable step sizes, and r(F) ≤ 1, θ_k converges with probability one to (I −γF^⊤)^−1b.The theorem allows an arbitrary initial parameter vector θ_0.
- Convergence and fixed point: The TD(0) convergence argument requires the numerical radius of F to be at most one, a condition tied to positive stability.The paper states that this requirement seems necessary for TD(0) convergence, whereas residual-gradient convergence needs only a nonsingular fixed-point system.
- Convergence and fixed point: Residual-gradient Dyna converges with probability one to (I −γF^⊤)^−1b when I −γF^⊤ is nonsingular.The proof identifies this point as the minimizer of the residual-gradient objective.
- Convergence to the LSTD solution: For a model fitted by least squares to finite transition data, the Dyna fixed point equals the least-squares temporal-difference solution found by LSTD(0).The equality holds when the relevant feature matrix has full rank.
4 Linear prioritized sweeping
Linear prioritized sweeping replaces predecessor-state backups with feature-level backups guided by the learned transition model. The paper presents PWMA and MG variants that combine prioritized planning with TD(0), gradient-descent model learning, and real experience updates.
- Linear prioritized sweeping: Prioritized sweeping selects preceding features whose values are likely affected by a changed feature component.Features j are prioritized when the corresponding model elements F_ij are large.
- Algorithm design: Unit basis vectors make each model multiplication Fφ equivalent to extracting one column of F without changing the convergence result.The theoretical results justify this starting-vector choice, which improves computational efficiency.
- PWMA prioritized sweeping: The PWMA variant queues predecessors of every state encountered in real experience, regardless of whether its value changed substantially.This mirrors the earlier tabular PWMA form while adapting backups to linear features.
- MG prioritized sweeping: The MG variant queues each encountered state but not its predecessors, yielding a more efficient tabular precedent adapted here to linear approximation.The paper gives a complete MG implementation for policy evaluation and control.
- Algorithm design: Both linear prioritized-sweeping algorithms update from real experience as well as model-generated experience.The authors state that real experience is more informative because model-generated experience is distorted by function approximation.
5 Theory for Control
For control, linear Dyna learns separate action models and applies model-generated transitions within a policy-dependent recursion. The convergence result requires stability of the least-squares mixture model, while the paper notes that the control theory is less clear than the policy-evaluation theory.
- 5 Theory for Control: Linear Dyna control learns separate forward-transition matrices and reward vectors for each action.For a selected feature vector and action, the model generates the next feature vector and reward used in a model-free update.
- Scope and limitation: The control theory is less clear because stability of the mixture of forward-model matrices is the main unresolved issue.The stated corollary assumes an i.i.d. feature sequence, though the authors say it can extend to policy-generated trajectories.
- 5 Theory for Control: The control recursion replaces F and b with action-selected models determined by the policy.The policy maps feature vectors to actions, producing F_π(φ) and b_π in the recursion.
- Implication: For any policy with a stable corresponding model, linear Dyna can compute its value function and support a form of policy iteration.The policy can be repeatedly evaluated for the currently greedy policy.
6 Empirical results
Experiments on Boyan Chain and Mountain Car illustrate how linear Dyna methods compare with model-free learning, with stronger and more consistent gains on Boyan Chain than on Mountain Car.
- Experimental setup: The experiments used Boyan Chain and Mountain Car, averaged results over 30 runs, and applied the same trajectories in policy evaluation.Boyan Chain was extended to 98 states and 25 features; added Mountain Car noise switched the selected action randomly with 10% probability.
- Policy evaluation: Dyna algorithms generally learned more rapidly than model-free TD(0) in the Boyan Chain environment.With p = 1, Dyna-MG initially lagged because of model variance but later surpassed the other methods; with p up to 10, Dyna learning rates improved further and Dyna-MG remained best.
- Policy evaluation: Dyna-MG was initially slower on Boyan Chain but became the best method when starting from a fixed, well-learned model.The authors attribute its poor early performance to high model variance during the first few episodes.
- Policy evaluation: Mountain Car results were less clear: Dyna-MG quickly outperformed TD(0), while the other Dyna algorithms initially lagged and never surpassed it.Despite more parameter updates, Dyna-MG tended to run faster overall because of other computational efficiencies.
- Control: In Mountain Car control, Dyna-MG showed a distinct learning-rate advantage over model-free Sarsa, but neither method had a clear advantage later.The comparison used Dyna-MG with planning against Sarsa with p = 0.
- Interpretation: The authors characterize the empirical results as limited and partly preliminary, while noting potential for linear Dyna methods to accelerate reinforcement learning.They also report that least-squares methods such as LSTD were difficult to adapt to online control because older data can become irrelevant or misleading as policies change.
7 Conclusion
The paper establishes theoretical and algorithmic foundations for Dyna-style planning with linear function approximation. It proves convergence to a unique least-squares solution independent of the hypothetical-experience distribution, extends prioritized sweeping with correctness guarantees, and presents empirical evidence of potential acceleration for online control.
- Theory: Linear Dyna planning converges under weak conditions to a unique least-squares solution independent of the distribution used to generate hypothetical experience.The conclusion describes these results as foundational for Dyna-style planning with linear function approximation.
- Algorithms: The paper introduces prioritized-sweeping algorithms for linear function approximation with correctness guarantees.These algorithms back up to preceding features rather than only preceding states.
- Empirical implications: Empirical results illustrate the use of linear prioritized-sweeping algorithms and their potential to accelerate reinforcement learning.The paper’s overall conclusion supports linear Dyna as a potentially practical approach to rapid online control in large-state stochastic sequential decision problems.