Comparison of Major Advantages and Disadvantages of Different RL Methods
High-level comparison
Here is a high-level comparison of the practical advantages and disadvantages between the algorithm families.
| Method family | Major advantage | Major disadvantage |
|---|---|---|
| DP | Strong convergence guarantees, no sampling | Requires complete model |
| Monte Carlo | Model-free and no bootstrapping | High variance; delayed updates |
| TD | Online, model-free, efficient, lower variance then MC | Biased bootstrapped targets |
| (n)-step | Bias–variance tradeoff between TD and MC | Additional (n) parameter |
| Planning / Dyna | Reuses experience through a model | Model errors can hurt learning |
| Linear approximation | Scales while retaining useful theory | Requires good features |
| Non-Linear approximation | Very flexible | Removes guarantees |
| Off-policy + approximation | Can learn from data generated by other policies | Potential instability/divergence |
| Eligibility traces | Improved temporal credit assignment | Extra computation and $\lambda$ |
| Policy gradient | Directly optimizes stochastic policies | High variance/local optima |
| Actor-Critic | Combines policy optimization with efficient TD learning | More complex and critic introduces bias |
Off-policy + bootstrapping + function approximation → deadly triad
Detailed Comparison by Algorithm
Here is a detailed comparison of individual algorithms.
| Ch. | Method | Advantages | Disadvantages | |
|---|---|---|---|---|
| 2 | $\epsilon$-greedy | Very simple; guarantees continued exploration for $\epsilon>0$; inexpensive | Explores randomly without considering uncertainty; fixed $\epsilon$ never becomes fully greedy | |
| Optimistic Initial Values | Encourages exploration without explicit randomness; simple | Exploration is temporary; sensitive to initialization; poorly suited to nonstationary problems | ||
| UCB | Directly balances exploration and exploitation; favors uncertain actions; strong theoretical properties | Requires action counts; less straightforward in large/continuous spaces and nonstationary settings | ||
| 4 | Policy Evaluation | Simple; guaranteed convergence for tabular finite MDPs; foundation for DP methods | Requires complete environment model; repeated sweeps can be expensive | |
| Policy Iteration | Strong convergence guarantees; often requires relatively few policy improvements | Each policy evaluation can be expensive; requires model | ||
| Value Iteration | Combines evaluation and improvement; usually simpler/faster than exact policy iteration | Requires model; full sweeps expensive for large state spaces | ||
| Asynchronous DP | Does not require complete sweeps; can prioritize important states | Must ensure adequate updates of states; still requires a model | ||
| 5 | MC Prediction | Model-free; unbiased returns; no bootstrapping | Must wait until return is known; high variance; primarily episodic | |
| MC Exploring Starts | Simple convergence argument for optimal control | Exploring-starts assumption often unrealistic | ||
| On-policy MC Control | Model-free; learns directly from experience; conceptually simple | High variance; inefficient use of experience; continued exploration needed | ||
| Off-policy MC / Importance Sampling | Can evaluate one policy while following another; enables reuse of data | Importance ratios can produce extremely high variance | ||
| Weighted Importance Sampling | Usually much lower variance than ordinary importance sampling | Introduces finite-sample bias; still suffers when target and behavior policies differ greatly | ||
| 6 | TD(0) | Online; model-free; lower variance than MC; learns before episode ends | Biased target due to bootstrapping; step-size sensitive | |
| Sarsa | Simple on-policy control; accounts for actual exploratory behavior; strong tabular guarantees | Exploration affects learned policy/value; can learn conservative behavior | ||
| Q-learning | Off-policy; directly learns optimal action values; strong tabular convergence guarantee | Maximization bias; potentially unstable with function approximation; target ignores actual behavior policy | ||
| Expected Sarsa | Lower variance than Sarsa; can combine advantages of Sarsa and Q-learning | Requires computing expectation over actions; more computation per update | ||
| Double Q-learning | Reduces maximization/overestimation bias | Maintains two value estimates; additional complexity and storage | ||
| 7 | (n)-step TD | Flexible tradeoff between TD and MC; often learns faster than either extreme | Must choose (n); delays updates; requires storing recent trajectory | |
| (n)-step Sarsa | Propagates rewards faster than one-step Sarsa | More storage/computation; choice of (n) problem-dependent | ||
| Off-policy (n)-step methods | Can learn from behavior generated by another policy | Importance-sampling variance can grow dramatically with (n) | ||
| 8 | Dyna-Q | Combines planning and learning; reuses experience efficiently; can learn much faster | Requires learning/storing a model; model errors can produce poor planning updates | |
| Prioritized Sweeping | Focuses computation where value changes matter most; efficient planning | More complex bookkeeping; requires predecessor/model information | ||
| Trajectory Sampling | Concentrates computation on states likely to be encountered | May neglect low-probability but important states | ||
| 9 | Gradient Monte Carlo | True stochastic-gradient method; stable with linear approximation | High variance; must wait for return; inefficient for long episodes | |
| Semi-gradient TD | Online; computationally efficient; typically lower variance than MC | Not true gradient of ordinary prediction error; bootstrapping introduces bias | ||
| Linear Function Approximation | Efficient; scalable; strong theoretical results; relatively stable | Quality limited by features; cannot automatically learn complex representations | ||
| Tile Coding | Simple; efficient; good generalization; works well with linear methods | Requires feature engineering and scaling; dimensionality can grow quickly | ||
| 10 | Semi-gradient Sarsa | Scales tabular Sarsa to large/continuous state spaces; simple with linear features | No general global optimality guarantee; feature quality critical | |
| Differential Sarsa | Handles continuing tasks without discounting/episode boundaries | Average-reward formulation and tuning are less intuitive; theoretical guarantees more limited | ||
| 11 | Off-policy Semi-gradient TD | Simple; allows learning about target policy from other behavior | Can diverge, even with linear approximation | |
| Q-learning + Function Approximation | Powerful and scalable idea; basis for many deep-RL algorithms | Deadly triad can cause instability/divergence | ||
| Gradient TD / TDC / GTD2 | Provides convergence guarantees for important linear off-policy cases | More complicated; additional weights and computation; often two step sizes | ||
| 12 | TD($\lambda$) | Smoothly combines one-step TD and MC; faster credit assignment | Extra $\lambda$ parameter; eligibility traces add computation/storage | |
| Accumulating Traces | Simple backward implementation; reinforces frequently visited states | Traces can become large with repeated visits | ||
| Replacing Traces | Prevents traces from growing excessively; often effective with binary features | Less general; behavior differs from accumulating traces | ||
| True Online TD($\lambda) | Exact online forward-view equivalence; often better learning performance | More complicated update equations | ||
| Sarsa($\lambda$) | Fast propagation of reward information; combines traces with control | More parameters; interaction of exploration and traces can complicate behavior | ||
| 13 | REINFORCE | True policy-gradient method; simple; unbiased gradient estimate; supports stochastic/continuous policies | Very high variance; slow learning; episodic return required in basic form | |
| REINFORCE + Baseline | Reduces variance without changing expected policy gradient | Requires learning/choosing a useful baseline | ||
| Actor-Critic | Lower variance than pure REINFORCE; online/incremental; works naturally for continuing tasks | Critic introduces bias; two learning processes must be tuned |