Answers.Body: <p>This <a href="https://spinningup.openai.com/en/latest/spinningup/rl_intro2.html" rel="noreferrer">Tutorial by OpenAI</a> offers a great comparison of different RL methods.<br>
  I'll try to summarize the differences between Q-Learning and Policy Gradient methods:</p>
  
  <ol>
  <li><p>Objective Function</p>
  
  <ol>
  <li>In <em>Q-Learning</em> we learn a Q-function that satisfies the Bellman (Optimality) Equation. This is most often achieved by minimizing the <strong>Mean Squared Bellman Error (MSBE)</strong> as the loss function. The Q-function is then used to obtain a policy (e.g. by greedily selecting the action with maximum value). </li>
  <li><em>Policy Gradient methods</em> directly try to maximize the expected return by taking small steps in the direction of the policy gradient. The policy gradient is the <strong>derivative of the expected return w.r.t. the policy parameters</strong>.</li>
  </ol></li>
  <li><p>On- vs. Off-Policy</p>
  
  <ol>
  <li>The <em>Policy Gradient</em> is derived as an expectation over trajectories (<span class="math-container">$s_1,a_1,r_1,s_2,a_2,...,r_n$</span>), which is estimated by a sample mean. To get an unbiased estimate of the gradient, the trajectories have to be sampled from the current policy. Thus, policy gradient methods are <strong>on-policy</strong> methods. </li>
  <li><em>Q-Learning</em> only makes sure to satisfy the Bellman-Equation. This equation has to hold true for all transitions. Therefore, Q-learning can also use experiences collected from previous policies and is <strong>off-policy</strong>. </li>
  </ol></li>
  <li><p>Stability and Sample Efficiency</p>
  
  <ol>
  <li>Directly optimizing the return and thus the actual performance on a given task, <em>Policy Gradient methods</em> tend to more stably converge to a good behavior. Indeed being on-policy, makes them very <strong>sample inefficient</strong>. <em>Q-learning</em> find a function that is guaranteed to satisfy the Bellman-Equation, but this does not guarantee to result in near-optimal behavior. Several tricks are used to improve convergence and in this case, Q-learning is more sample efficient.</li>
  </ol></li>
  </ol>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-17T18:55:38.153Z
Answers.Text: your answer is so good for comparison. thank you. Is it that we are using only a greedy deterministic policy in q learning?
Answers.UserDisplayName: Mathav Raj
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-22T20:10:20.683Z
Answers.Text: @MathavRaj In Q-learning, you assume that the optimal policy is greedy with respect to the optimal value function. This can easily be seen from the Q-learning update rule, where you use the max to select the action at the next state that you ended up in with behaviour policy, i.e. you compute the target by assuming that at the next state you would use the greedy policy.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-13T11:48:07.657Z
Answers.Text: This answer could be improved if you explained the relation between being sample efficient (or inefficient) and stable (or unstable) convergence. Why would Q-learning be more sample efficient but it's more unstable when it comes to convergences? Those seem to be somehow contradictory.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-23T07:49:17.953Z
Answers.Text: Very well summarized answer. To answer nbro's query - 'sample efficient' means the ease with which one can collect the samples to perform the gradient updates. In online learning, we can't use experience replay and so we dont have access to a huge repository of samples. The positive side is that convergence is faster (given same quantity of samples) since we are directly optimizing the policy itself (and not indirectly by optimizing the Q values and selecting actions greedily). The contradiction vanishes upon assuming equal sample sizes. This is why we have 2 branches of algos & the hybrids.
Answers.UserDisplayName: Allohvk
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-22T12:05:54.623Z
Answers.LastActivityDate: 2020-04-22T12:05:54.623Z
Answers.UserDisplayName: Ray Walker
Answers.Body: <blockquote>
    <p>However, both approaches appear identical to me i.e. predicting the maximum reward for an action (Q-learning) is equivalent to predicting the probability of taking the action directly (PG).</p>
  </blockquote>
  
  <p>Both methods are theoretically driven by the <a href="https://en.wikipedia.org/wiki/Markov_decision_process" rel="noreferrer">Markov Decision Process</a> construct, and as a result use similar notation and concepts. In addition, in simple solvable environments you should expect both methods to result in the same - or at least equivalent - optimal policies.</p>
  
  <p>However, they are actually different internally. The most fundamental differences between the approaches is in how they approach action selection, both whilst learning, and as the output (the learned policy). In Q-learning, the goal is to learn a single deterministic action from a discrete set of actions by finding the maximum value. With policy gradients, and other direct policy searches, the goal is to learn a map from state to action, which can be stochastic, and works in continuous action spaces.</p>
  
  <p>As a result, policy gradient methods can solve problems that value-based methods cannot:</p>
  
  <ul>
  <li><p>Large and continuous action space. However, with value-based methods, this can still be approximated with discretisation - and this is not a bad choice, since the mapping function in policy gradient has to be some kind of approximator in practice.</p></li>
  <li><p>Stochastic policies. A value-based method cannot solve an environment where the optimal policy is stochastic requiring specific probabilities, such as Scissor/Paper/Stone. That is because there are no trainable parameters in Q-learning that control probabilities of action, the problem formulation in TD learning assumes that a deterministic agent can be optimal.</p></li>
  </ul>
  
  <p>However, value-based methods like Q-learning have some advantages too:</p>
  
  <ul>
  <li><p>Simplicity. You can implement Q functions as simple discrete tables, and this gives some guarantees of convergence. There are no tabular versions of policy gradient, because you need a mapping function <span class="math-container">$p(a \mid s, \theta)$</span> which also must have a smooth gradient with respect to <span class="math-container">$\theta$</span>.</p></li>
  <li><p>Speed. TD learning methods that bootstrap are often much faster to learn a policy than methods which must purely sample from the environment in order to evaluate progress.</p></li>
  </ul>
  
  <p>There are other reasons why you might care to use one or other approach:</p>
  
  <ul>
  <li><p>You may want to know the predicted return whilst the process is running, to help other planning processes associated with the agent.</p></li>
  <li><p>The state representation of the problem lends itself more easily to either a value function or a policy function. A value function may turn out to have very simple relationship to the state and the policy function very complex and hard to learn, or <em>vice-versa</em>.</p></li>
  </ul>
  
  <p>Some state-of-the-art RL solvers actually use both approaches together, such as Actor-Critic. This combines strengths of value and policy gradient methods.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-19T02:16:08.050Z
Answers.Text: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/118623/discussion-on-answer-by-neil-slater-what-is-the-relation-between-q-learning-and).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-04-28T07:47:57.307Z
Answers.LastActivityDate: 2018-11-18T13:47:14.037Z
Answers.LastEditDate: 2018-11-18T13:47:14.037Z
Answers.UserDisplayName: Neil Slater
Body: <p>As far as I understand, Q-learning and policy gradients (PG) are the two major approaches used to solve RL problems. While Q-learning aims to predict the reward of a certain action taken in a certain state, policy gradients directly predict the action itself.</p>
  
  <p>However, both approaches appear identical to me, i.e. predicting the maximum reward for an action (Q-learning) is equivalent to predicting the probability of taking the action directly (PG). Is the difference in the way the loss is back-propagated?</p>
  
Tags: <reinforcement-learning><q-learning><policy-gradients><comparison>
Title: What is the relation between Q-learning and policy gradients methods?
UserDisplayName: Tejas Ramdas
ThreadText: # What is the relation between Q-learning and policy gradients methods?
  
  (Asked by: username_0 on 2018-04-28)
  
  As far as I understand, Q-learning and policy gradients (PG) are the two major approaches used to solve RL problems. While Q-learning aims to predict the reward of a certain action taken in a certain state, policy gradients directly predict the action itself.
  
  However, both approaches appear identical to me, i.e. predicting the maximum reward for an action (Q-learning) is equivalent to predicting the probability of taking the action directly (PG). Is the difference in the way the loss is back-propagated?
  
  **Tags:** reinforcement-learning, q-learning, policy-gradients, comparison
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_5 on 2018-04-28. Score: 49 | Accepted answer
  
  > However, both approaches appear identical to me i.e. predicting the maximum reward for an action (Q-learning) is equivalent to predicting the probability of taking the action directly (PG).
  
  Both methods are theoretically driven by the [Markov Decision Process](https://en.wikipedia.org/wiki/Markov_decision_process) construct, and as a result use similar notation and concepts. In addition, in simple solvable environments you should expect both methods to result in the same - or at least equivalent - optimal policies.
  
  However, they are actually different internally. The most fundamental differences between the approaches is in how they approach action selection, both whilst learning, and as the output (the learned policy). In Q-learning, the goal is to learn a single deterministic action from a discrete set of actions by finding the maximum value. With policy gradients, and other direct policy searches, the goal is to learn a map from state to action, which can be stochastic, and works in continuous action spaces.
  
  As a result, policy gradient methods can solve problems that value-based methods cannot:
  
  * Large and continuous action space. However, with value-based methods, this can still be approximated with discretisation - and this is not a bad choice, since the mapping function in policy gradient has to be some kind of approximator in practice.
  * Stochastic policies. A value-based method cannot solve an environment where the optimal policy is stochastic requiring specific probabilities, such as Scissor/Paper/Stone. That is because there are no trainable parameters in Q-learning that control probabilities of action, the problem formulation in TD learning assumes that a deterministic agent can be optimal.
  
  However, value-based methods like Q-learning have some advantages too:
  
  * Simplicity. You can implement Q functions as simple discrete tables, and this gives some guarantees of convergence. There are no tabular versions of policy gradient, because you need a mapping function $p(a \mid s, \theta)$ which also must have a smooth gradient with respect to $\theta$.
  * Speed. TD learning methods that bootstrap are often much faster to learn a policy than methods which must purely sample from the environment in order to evaluate progress.
  
  There are other reasons why you might care to use one or other approach:
  
  * You may want to know the predicted return whilst the process is running, to help other planning processes associated with the agent.
  * The state representation of the problem lends itself more easily to either a value function or a policy function. A value function may turn out to have very simple relationship to the state and the policy function very complex and hard to learn, or *vice-versa*.
  
  Some state-of-the-art RL solvers actually use both approaches together, such as Actor-Critic. This combines strengths of value and policy gradient methods.
  
  > **Comments:**
  > **username_3**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/118623/discussion-on-answer-by-username_5-what-is-the-relation-between-q-learning-and).  
  
  ---
  
  ### Answer by username_1 on 2020-04-22. Score: 15
  
  This [Tutorial by OpenAI](https://spinningup.openai.com/en/latest/spinningup/rl_intro2.html) offers a great comparison of different RL methods.  
  I'll try to summarize the differences between Q-Learning and Policy Gradient methods:
  
  1. Objective Function
  
     1. In *Q-Learning* we learn a Q-function that satisfies the Bellman (Optimality) Equation. This is most often achieved by minimizing the **Mean Squared Bellman Error (MSBE)** as the loss function. The Q-function is then used to obtain a policy (e.g. by greedily selecting the action with maximum value).
     2. *Policy Gradient methods* directly try to maximize the expected return by taking small steps in the direction of the policy gradient. The policy gradient is the **derivative of the expected return w.r.t. the policy parameters**.
  2. On- vs. Off-Policy
  
     1. The *Policy Gradient* is derived as an expectation over trajectories ($s\_1,a\_1,r\_1,s\_2,a\_2,...,r\_n$), which is estimated by a sample mean. To get an unbiased estimate of the gradient, the trajectories have to be sampled from the current policy. Thus, policy gradient methods are **on-policy** methods.
     2. *Q-Learning* only makes sure to satisfy the Bellman-Equation. This equation has to hold true for all transitions. Therefore, Q-learning can also use experiences collected from previous policies and is **off-policy**.
  3. Stability and Sample Efficiency
  
     1. Directly optimizing the return and thus the actual performance on a given task, *Policy Gradient methods* tend to more stably converge to a good behavior. Indeed being on-policy, makes them very **sample inefficient**. *Q-learning* find a function that is guaranteed to satisfy the Bellman-Equation, but this does not guarantee to result in near-optimal behavior. Several tricks are used to improve convergence and in this case, Q-learning is more sample efficient.
  
  > **Comments:**
  > **username_2**: your answer is so good for comparison. thank you. Is it that we are using only a greedy deterministic policy in q learning?  
  > **username_3**: @username_2 In Q-learning, you assume that the optimal policy is greedy with respect to the optimal value function. This can easily be seen from the Q-learning update rule, where you use the max to select the action at the next state that you ended up in with behaviour policy, i.e. you compute the target by assuming that at the next state you would use the greedy policy.  
  > **username_3**: This answer could be improved if you explained the relation between being sample efficient (or inefficient) and stable (or unstable) convergence. Why would Q-learning be more sample efficient but it's more unstable when it comes to convergences? Those seem to be somehow contradictory.  
  > **username_4**: Very well summarized answer. To answer username_3's query - 'sample efficient' means the ease with which one can collect the samples to perform the gradient updates. In online learning, we can't use experience replay and so we dont have access to a huge repository of samples. The positive side is that convergence is faster (given same quantity of samples) since we are directly optimizing the policy itself (and not indirectly by optimizing the Q values and selecting actions greedily). The contradiction vanishes upon assuming equal sample sizes. This is why we have 2 branches of algos & the hybrids.  
  
  ---
  
  