Kinds of Reinforcement Learning Algorithms

Topics: Reinforcement Learning

RL Algorithms Tree

The following tree is not an exhaustive list of all RL algorithms. It is a starting point to understand with main kinds and the most popular algorithms.

Model-Based vs. Model-Free

The main distinction between RL algorithms is whether the agent has access to a model of the environment, that is, a function that predicts state transitions and rewards.

Model-Based RL

In Model-Based RL, the agent knows or learns a model of the environment. This allows the agent to plan by thinking ahead and to make better decisions given the possible choices. Another upside is that having a model results in a substantial increase in sample efficiency, as the agent would have to interact less with the environment to improve learning. The main downside is that a ground-truth model of the environment is usually not available, so the agent would have to learn it from experience. This is quite challenging and can result in learning bias, where the agent performs well with the learned model but not so well with the real environment.

Model-Free RL

In Model-Free RL, the agent does not have a model of the environment. It learns from samples collected by interacting with the environment. But what does the agent actually learn? The options are:

• policies (deterministic/stochastic)
• action-value functions $Q^\pi(s,a)$
• value functions $V^\pi(s)$

Based on which of the above the agent learns, and how it learns it, we can divide Model-Free RL algorithms into 3 main categories:

Policy Optimization

In this family of algorithms, the agent learns the parameters $\theta$ of the policy network either directly by gradient ascent, or indirectly by maximizing local approximations of a performance objective $J(\pi_\theta)$. The optimization is on-policy and involves learning the on-policy value function $V^\pi(s)$.

Popular Policy Optimization algorithms include:

• Vanilla Policy Gradient
• A2C/A3C
• PPO

Policy Optimization intuitively makes sense because it directly optimizes what we care about learning: the policy parameters $\theta$. This makes it stable and reliable.

Q-Learning

In this family of algorithms, the agent learns an approximator $Q_\theta (s,a)$ of the optimal action-values $Q^* (s,a)$. This is usually done off-policy using an objective function based on the Bellman Equation. The policy corresponding to $Q_\theta (s,a)$ is then obtained as:
$a(s)=\underset{a}{arg\;max}\; Q_\theta (s,a)$
The most popular Q-Learning algorithms are:

• Deep Q-Learning
• Double Q-Learning

In contrast to Policy Optimization, Q-Learning does not directly optimize the policy; it optimizes Q-values then extracts a corresponding policy. This makes it less stable and prone to several failure modes.

Interpolating Between Policy Optimization and Q-Learning

There is a family of RL algorithms that live between Policy Optimization and Q-Learning, and trades-off between the strengths and weaknesses of both.

The most popular algorithms are:

• DDPG
• TD3
• SAC

On-Policy vs. Off-Policy

• On-Policy: each learning update only uses data collected while acting with the most recent version of the policy. In other words, the agent learns from its own current policy
• Off-Policy: each learning update can use data collected at any point during training regardless of the policy followed back then. In other words, the agent can learn from experience collected by following any policy.

References

1. https://spinningup.openai.com/en/latest/spinningup/rl_intro2.html