# Different algorithms categorized in reinforcement learning

For some time I am going through reinforcement learning, and have found a lot of diverse information specially in area of Policies (algorithms).

I figured out that policies can be classified in On Vs Off, Model based vs Model Free, Also, these are kind of Q, DQN, SARSA etc.

I am looking for a categorized table where these are all well categorized . There is a good table given in wikipedia, but I think it is incomplete (Wikipedia page url - Reinforcement learning ), as it does not list Model based algorithms and it does not list examples where one kind of algorithm is a best fit.

Can someone help getting a bird's eye view of all, current known, reinforcement policies/algorithms, categorized in tabular format, and where to apply which one (and where not).

• To me, it looks like you are not talking about classifying policies, but different reinforcement learning algorithms. Each algorithm will produce a policy, but in each case the target optimal policy can be the same. I.e. there is no inherent difference between an optimal policy discovered by DDPG and DQN, although there might be practical differences that one or other algorithm is better at getting a close approximation to optimal behaviour. Also, the wikipedia page lists these as different "methods", not different policies. I suggest use term "method" or "algorithm" in the question Commented Apr 7, 2019 at 10:22
• Thanks for pointing out. Changed policies word to algorithm. Hope the question is more clear now I will a answer to my query. Commented Apr 8, 2019 at 5:29

In general, reinforcement learning algorithms can be classified into model-based and model-free algorithms.

Model-based Model-based algorithms require to know the dynamics (aka the model) of the environment they are trained in. Such dynamics can be transition probabilities (the probability of landing in state $$s'$$ given that action $$a$$ is taken in state $$s$$) or the reward function (what reward you are getting when taking some action $$a$$ in state $$s$$). In MDPs, there always is an optimal policy and given the model of the environment, value iteration and policy iteration (two model-based algorithms) are guaranteed to find that optimal policy. Regarding a best fit for this type of algorithms: Personally, I would go with value iteration as it often converges faster than policy iteration (to understand why, you need to go into the algorithmics of both approaches). If you do not know the model of the environment, you could explore the environment by taking some actions in it until you are sufficiently sure about the dynamics and then use the above methods to solve the RL problem. Either way, you need to know the dynamics of the environment to use model-based algorithms.

Model-free Model-free algorithms is where it gets interesting. Here you don't know the dynamics of the environment in advance and therefore the agent has to actively explore the environment to obtain some knowledge about it. At the same time, you do not try to explore the environment with the aim of approximating the dynamics of the environment (because this is model-based). So what you are actually trying to do is to solve the RL problem without having any estimate of the dynamics of the environment. How does this work? For example, you could keep an estimate of how good it is to be in a specific state or how good it is to take some specific action in a state. This estimate can be based on the experiences you are getting when taking some actions in the environment. Whenever going through the environment, you update these estimated values based on what reward you are actually getting (Note the difference to model-based algorithms: here, you keep track of how good it is to be in a state but in model-based methods you are keeping track of the environmental dynamics you have experienced). The algorithms you mentioned are all model-free algorithms. Now it makes sense to further distinguish between on-policy and off-policy algorithms:

Off-Policy When going acting in the environment to obtain additional information about it, you need to have some policy to knwo what action should be taken in a specific state. Off-policy means that this policy can be arbitrary e.g. you can follow a random policy and therefore take a random walk through the environment while updating your estimated values of the states you were in. Q-Learning is off-policy. DQN is just some special case of Q-learning. In Q-learning, you try to learn some function $$q: \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}$$ that represents the "goodness" of taking a specific action in a state. This function can be non-linearly approximated using a neural network (= Deep Q-learning).

On-policy Here, your policy cannot be arbitrary. In fact, the policy that is taken for deciding the next action is the same policy as the one that you are trying to learn. So basically you are following a policy that you know is imperfect and while following this very policy, you are trying to improve it. SARSA belongs to this class of algorithms.

Generally, there is no go-to algorithm for model-free learning as it always depends on the problem you are facing. However, Q-Learning is a good starting point when you want to get into RL.

Here is an overview of RL algorithms from OpenAI: https://spinningup.openai.com/en/latest/spinningup/rl_intro2.html#

In general a great resource to learn deep reinforcement learning.