What is the difference between dynamic programming and Q-learning?

What is the difference between the DP-based algorithm and Q-learning?

Both Q learning and Value Iteration (a DP technique) use similar update rules based on Bellman optimality equations:

$$v_*(s) = \text{max}_{a}\sum_{s',r} p(s',r|s,a)(r + \gamma v_*(s'))$$

$$q_*(s,a) = \sum_{s',r} p(s',r|s,a)(r + \gamma\text{max}_{a'}q_*(s',a'))$$

The main difference is that DP uses an explicit model. DP requires that you know $$p(s',r|s,a)$$. The update rule for DP is literally the first equation turned into an update rule:

$$v_{k+1}(s) = \text{max}_{a}\sum_{s',r} p(s',r|s,a)(r + \gamma v_{k}(s'))$$

In comparison, Q learning does not require knowing $$p(s',r|s,a)$$, as it is based on sampling from experience. The update rule is modified to be based on samples of observed data, which have the same values in expectation, as if you had used $$p(s',r|s,a)$$, but without knowing it:

$$Q_{k+1}(S_t,A_t) = Q_{k}(S_t,A_t) + \alpha(R_{t+1} + \gamma\text{max}_{a'}Q_k(S_{t+1},a') - Q_{k}(S_t,A_t))$$

This is still an important difference even when both systems are run on an internal model/simulation. DP does not need to simulate anything, it iterates over the model directly. Whilst Q learning needs to work with sampled transitions - they might be simulated, but this is not the same as iterating over all states as in DP. It can often be the case that it is easier to simulate the environment than to calculate $$p(s',r|s,a)$$ for the full model.

Which should you choose:

• Choose Dynamic Programming when you have access to the full state transition and reward model in a simple form (i.e. you have $$p(s',r|s,a)$$ or equivalent), and the state space is not too large - ideally the number of states is small enough to fit in memory. However, there are ways to use DP when you have a larger state space, by modifying which states it processes. So you still can use DP on larger problems if you really want to.

• Choose Q learning when you don't have a model, or when the state space is too large to iterate over in full.

• Thanks Neil, as there is some vague point about difference between the reason of immigration from DP to RL and the reason of immigration from RL to DQN would you please reply my question in this field? – user10296606 Jan 22 '19 at 6:10
• datascience.stackexchange.com/questions/44356/… – user10296606 Jan 22 '19 at 10:00
• @user10296606: I read that earlier, but did not understand the question - it has too many parts, and the original language has not been translated well to English. I think you need to simplify it to have just one question, that may help. Perhaps also make more use of maths notation, as that doesn't need to be translated. – Neil Slater Jan 22 '19 at 10:09
• Both Q-learning and DP are "MDP approaches" and I would consider them both to be RL. Your questions show that you are not understanding some basic concepts, and you need to slow down, ask one question at a time. I answer your first question here in this answer though, so there is no need to ask it again. – Neil Slater Jan 22 '19 at 10:48