Answers.Body: <h1>Short answer</h1>
  <p>The Q values are updated using a <strong>greedy policy</strong> because, in the Q-learning algorithm, the <span class="math-container">$\max$</span> operator is used to determine the <strong>target</strong>, which is denoted by</p>
  <p><span class="math-container">$$\color{green}{R_{t+1}} + \gamma \color{blue}{\max_{a}Q(S_{t+1}, a)}$$</span></p>
  <p>Intuitively, the <span class="math-container">$\max$</span> operator is used because we assume that the <strong>target policy</strong> (the policy associated with the optimal value function that we want to learn) takes a <strong>greedy action</strong>, which is defined, in this context, as the action associated with the highest Q value: <span class="math-container">$\color{blue}{\max_{a}Q(S_{t+1}, a)}$</span> means that we are selecting the <span class="math-container">$Q$</span> value, associated with the (next) state <span class="math-container">$S_{t+1}$</span>, which corresponds to the action <span class="math-container">$a$</span>, such that <span class="math-container">$Q(S_{t+1}, a)$</span> is the highest (with respect to other possible actions from <span class="math-container">$S_{t+1}$</span>).</p>
  <p>Note that the <span class="math-container">$Q$</span> function receives as input a state and an action. So, for each state <span class="math-container">$s$</span>, we have an action (among all possible actions, <span class="math-container">$a_1, a_2, \dots$</span>, which we can take from the state <span class="math-container">$s$</span>), denote it by <span class="math-container">$a^*$</span>, such that <span class="math-container">$Q(s, a^*) &gt; Q(s, a_1)$</span>, <span class="math-container">$Q(s, a^*) &gt; Q(s, a_2)$</span>, etc. In the expression <span class="math-container">$\color{blue}{\max_{a}Q(S_{t+1}, a)}$</span>, we are basically selecting <span class="math-container">$Q(s, a^*)$</span> for <span class="math-container">$s = S_{t+1}$</span>.</p>
  <h1>More explanations</h1>
  <p>To explain all the components of this <strong>target</strong>, I will explain the Q-learning algorithm. Hopefully, after this explanation, you will be able to understand why Q-learning uses the <strong>greedy policy</strong> to update the Q values and why it is an <strong>off-policy algorithm</strong> (which is, IMHO, a quite unintuitive and confusing term to describe what off-policy actually means).</p>
  <h2>How does Q-learning work?</h2>
  <p>Here's the <a href="https://github.com/udacity/rl-cheatsheet/blob/master/cheatsheet.pdf" rel="nofollow noreferrer">Q-learning algorithm</a></p>
  <p><a href="https://i.sstatic.net/qymVD.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/qymVD.png" alt="enter image description here" /></a></p>
  <p>The Q-learning algorithm estimates a <a href="https://ai.stackexchange.com/q/10575/2444"><strong>value function</strong></a>, known as the Q-function, associated with a policy <span class="math-container">$\pi$</span>. Intuitively, it does that by simulating an <a href="https://ai.stackexchange.com/a/12995/2444"><strong>agent</strong></a> which takes <strong>actions</strong> in the <strong>environment</strong>, <strong>observes</strong> the impact of those actions on the environment in terms of the received <strong>rewards</strong> and the <strong>new states</strong> where the agent ends up in after taking those actions. Meanwhile, during this <strong>exploration</strong> of the environment, it attempts to estimate the optimal <span class="math-container">$Q$</span> function (i.e. the value function associated with the optimal policy, which, if followed, will give the agent the highest <em>amount of reward in the long run</em>, aka <strong>return</strong>).</p>
  <p>Q-learning proceeds in <strong>episodes</strong>. So, initially, you need to pass the number of episodes as input. You can think of episodes as iterations (like in any iterative optimisation algorithm). However, in the context of RL, an episode is a little bit more specific: the start and end of an episode are associated with specific states of the environment: the episode starts when the agent is in a <strong>starting state</strong> <span class="math-container">$S_0$</span> (which can be sampled from a probability distribution over <span class="math-container">$S_0$</span>, if there is more than one) and ends when it is in a <strong>terminal state</strong>.</p>
  <p>In the pseudocode above, at the beginning of each episode, we initialise <span class="math-container">$t=0$</span>, where <span class="math-container">$t$</span> represents the <a href="https://ai.stackexchange.com/a/11605/2444"><strong>time step</strong></a> of a specific episode.</p>
  <h3>Inner/Episode loop</h3>
  <p>We then have the following loop, which terminates when the agent reaches a terminal state:</p>
  <p><a href="https://i.sstatic.net/66r6E.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/66r6E.png" alt="enter image description here" /></a></p>
  <p>So, at each episode, we run the loop above. The block of code inside this loop contains the main logic of the Q-learning algorithm.</p>
  <h3>Behaviour policy</h3>
  <p>On each iteration of this inner loop, the agent chooses an action <span class="math-container">$A_t$</span> (the action at time step <span class="math-container">$t$</span> of the current episode) using a policy (which is known, in this context, as the <a href="https://ai.stackexchange.com/q/10492/2444"><strong>behaviour policy</strong></a>, which should ensure that all states are sufficiently visited, <a href="https://ai.stackexchange.com/a/21408/2444">in order for tabular Q-learning to converge</a>). In this case, <a href="https://ai.stackexchange.com/a/17626/2444">the <span class="math-container">$\epsilon$</span>-greedy policy</a> is used.</p>
  <h3>How does this <span class="math-container">$\epsilon$</span>-greedy policy work?</h3>
  <p>If you look at the pseudocode above, <span class="math-container">$\epsilon$</span> is initialised at beginning of each episode. In the pseudocode above, <span class="math-container">$\epsilon$</span> can change from episode to episode, but assume, for simplicity, that, at every episode, it is a fixed small number (e.g. <span class="math-container">$0.01$</span>). The statement</p>
  <blockquote>
  <p>Choose action <span class="math-container">$A_t$</span> using policy <strong>derived from</strong> <span class="math-container">$Q$</span> (e.g., <span class="math-container">$\epsilon$</span>-greedy)</p>
  </blockquote>
  <p>means that, with probability <span class="math-container">$1 - \epsilon$</span>, the <strong>greedy action</strong> is chosen, and, with probability <span class="math-container">$\epsilon$</span>, a random action is taken.</p>
  <h3>What is the greedy action in this case?</h3>
  <p>In this case, the <strong>greedy action</strong> is the action, in the current state <span class="math-container">$S_t$</span>, which is associated with the highest Q value (given the current estimate of the Q value). It is exactly the same action as the action <span class="math-container">$a^*$</span> (as I explained above). The difference is that, in this case, we choose <span class="math-container">$A_t$</span> using the <span class="math-container">$\epsilon$</span>-greedy policy: so, most of the time, we choose the greedy action, but, sometimes, we can also choose a random action.</p>
  <p>The agent then executes the just chosen action <span class="math-container">$A_t$</span> in the environment, and it observes the impact of this action on the environment, which is determined by how the environment responds to this action: the response consists of a reward, <span class="math-container">$R_{t+1}$</span>, and a next state, <span class="math-container">$S_{t+1}$</span>.</p>
  <p>To recapitulate, the agent chooses an action using the <span class="math-container">$\epsilon$</span>-greedy policy, executes this action on the environment, and it observes the response (that is, a reward and a next state) of the environment to this action. This is the part of the Q-learning algorithm where the agent interacts with the environment in order to gather some info about it, so as to be able to estimate the Q function.</p>
  <h3>Q-learning update</h3>
  <p>After that, the agent can update its estimate of the Q function using the following update rule</p>
  <p><span class="math-container">$$\color{orange}{Q(S_t, A_t)} \leftarrow \color{red}{Q(S_t, A_t)} + \alpha ([\color{green}{R_{t+1}} + \gamma \color{blue}{\max_{a}Q(S_{t+1}, a)}] - \color{red}{Q(S_t, A_t)})$$</span></p>
  <p>where <span class="math-container">$S_t$</span> is the current state (of the current episode) the agent is in, <span class="math-container">$A_t$</span> is the action chosen using the <span class="math-container">$\epsilon$</span>-greedy policy (as described above), and <span class="math-container">$S_{t+1}$</span> and <span class="math-container">$R_{t+1}$</span> are respectively the next state and rewards, which, collectively, are the response of the environment to the just taken action <span class="math-container">$A_t$</span>.</p>
  <p>So, how is the estimate of this <span class="math-container">$Q$</span> function updated?</p>
  <p>First of all, I would like to note that, if you look at the beginning of the pseudocode above, <span class="math-container">$Q(s, a)$</span> is initialized arbitrarily for all states <span class="math-container">$s \in \mathcal{S}$</span> and for all actions <span class="math-container">$a \in \mathcal{A}$</span>: it can e.g. be initialised to <span class="math-container">$0$</span>. <span class="math-container">$Q(s, a)$</span> can e.g. be implemented as a matrix (or 2-dimensional array) <span class="math-container">$M \in \mathbb{R}^{|\mathcal{S}| \times |\mathcal{A}|}$</span>, where <span class="math-container">$M[s, a] = Q(s, a)$</span>, <span class="math-container">$|\mathcal{S}|$</span> is the number of states in your problem and <span class="math-container">$|\mathcal{A}|$</span> the number of actions.</p>
  <p>Furthermore, note that the symbol <span class="math-container">$\leftarrow$</span> means &quot;assignment&quot; (like assignment to a variable, in the context of programming). So, in the update rule above, we are assigning to <span class="math-container">$\color{orange}{Q(S_t, A_t)}$</span> (which will be the next or updated estimate of the Q value for the current state <span class="math-container">$S_t$</span> and the just taken action from that state <span class="math-container">$A_t$</span>) the value <span class="math-container">$\color{red}{Q(S_t, A_t)} + \alpha (\color{green}{R_{t+1}} + \gamma \color{blue}{\max_{a}Q(S_{t+1}, a)} - \color{red}{Q(S_t, A_t)})$</span>. Let's break this value down.</p>
  <p><span class="math-container">$\color{red}{Q(S_t, A_t)}$</span> (on the right side of the assignment) is the estimate of the Q value for the state <span class="math-container">$S_t$</span> and action <span class="math-container">$A_t$</span> before the assignment. So, we are summing <span class="math-container">$\color{red}{Q(S_t, A_t)}$</span> and <span class="math-container">$\alpha (\color{green}{R_{t+1}} + \gamma \color{blue}{\max_{a}Q(S_{t+1}, a)} - \color{red}{Q(S_t, A_t)})$</span>, and then we assign it to <span class="math-container">$\color{orange}{Q(S_t, A_t)}$</span> again.</p>
  <p><span class="math-container">$\color{green}{R_{t+1}} + \gamma \color{blue}{\max_{a}Q(S_{t+1}, a)}$</span> is what is often called the <strong>target</strong>. Q-learning is a <strong>temporal-difference (TD) algorithm</strong>, and TD algorithms update estimates of the value or action-value functions based on the difference between the current estimate, in the case of Q-learning it is denoted by <span class="math-container">$\color{red}{Q(S_t, A_t)}$</span> (on the right side of the <span class="math-container">$\leftarrow$</span>), and a &quot;target&quot;. So, in the Q-learning algorithm, <span class="math-container">$\color{green}{R_{t+1}} + \gamma \color{blue}{\max_{a}Q(S_{t+1}, a)}$</span> is the target. We can roughly think of it as &quot;the value that <span class="math-container">$\color{red}{Q(S_t, A_t)}$</span> should have been&quot;. So, in a certain way, we are performing <a href="https://ai.stackexchange.com/q/14167/2444">supervised learning</a>, where <span class="math-container">$\color{green}{R_{t+1}} + \gamma \color{blue}{\max_{a}Q(S_{t+1}, a)}$</span> would be the <a href="https://ai.stackexchange.com/a/28109/2444">ground-truth label</a> and <span class="math-container">$\color{red}{Q(S_t, A_t)}$</span> the current estimate, and so <span class="math-container">$[\color{green}{R_{t+1}} + \gamma \color{blue}{\max_{a}Q(S_{t+1}, a)}] - \color{red}{Q(S_t, A_t)}$</span> would be the <em>error</em> (or <em>loss</em>): in fact, it is often called the <strong>TD error</strong>. However, note that this is not really supervised learning, because <span class="math-container">$\color{green}{R_{t+1}} + \gamma \color{blue}{\max_{a}Q(S_{t+1}, a)}$</span> is <strong>not</strong> a ground-truth (it is partially an estimate, because of the part <span class="math-container">$\gamma \color{blue}{\max_{a}Q(S_{t+1}, a)} $</span>, and it partially a ground-truth, because of <span class="math-container">$\color{green}{R_{t+1}}$</span>).</p>
  <p>To recapitulate, <span class="math-container">$\color{green}{R_{t+1}} + \gamma \color{blue}{\max_{a}Q(S_{t+1}, a)}$</span> is the <strong>target</strong>, <span class="math-container">$\color{red}{Q(S_t, A_t)}$</span> is the current estimate, and <span class="math-container">$[\color{green}{R_{t+1}} + \gamma \color{blue}{\max_{a}Q(S_{t+1}, a)}] - \color{red}{Q(S_t, A_t)}$</span> is the <strong>TD error</strong>. We are thus summing the &quot;error&quot; (weighted by the hyper-parameter <span class="math-container">$\alpha$</span>, which is, in this case, often called the <strong>learning rate</strong>) and the current estimate <span class="math-container">$\color{red}{Q(S_t, A_t)}$</span> in order to produce the new estimate <span class="math-container">$\color{orange}{Q(S_t, A_t)}$</span>.</p>
  <p>In the <strong>target</strong>, you can see that we are multiplying the <span class="math-container">$\color{blue}{\max_{a}Q(S_{t+1}, a)}$</span> by <span class="math-container">$\gamma$</span>. This is a hyper-parameter (a parameter which often needs to be chosen by the programmer before the algorithm is executed), known as the <strong>discount factor</strong>. It controls the contribution of <span class="math-container">$\color{blue}{\max_{a}Q(S_{t+1}, a)}$</span> to the <strong>target</strong>: that is, how much of <span class="math-container">$\color{blue}{\max_{a}Q(S_{t+1}, a)}$</span> we want to include in the <strong>target</strong>. Recall that I've just said above that the <strong>target</strong> is composed of the reward <span class="math-container">$\color{green}{R_{t+1}}$</span> (which is a <a href="https://ai.stackexchange.com/a/28109/2444">ground-truth</a> or real-world experience, because it is directly received from the environment) and <span class="math-container">$\color{blue}{\max_{a}Q(S_{t+1}, a)}$</span> (which actually uses an estimate of the Q function, that is, it uses <span class="math-container">$Q(S_{t+1}, a)$</span>). So, <span class="math-container">$\gamma$</span> controls the contribution of an estimate to the <a href="https://ai.stackexchange.com/a/28109/2444">ground-truth</a>.</p>
  <p>As I said at the beginning of this answer, <span class="math-container">$\color{blue}{\max_{a}Q(S_{t+1}, a)}$</span> can be thought of as the <span class="math-container">$Q$</span> value associated with the next state <span class="math-container">$S_{t+1}$</span> (which was observed by the agent after he has taken the action <span class="math-container">$A_t$</span>) and associated with the action <span class="math-container">$a$</span>, such that <span class="math-container">$Q(S_{t+1}, a)$</span> is the highest among all other possible actions from state <span class="math-container">$S_{t+1}$</span>. In other words, <span class="math-container">$\color{blue}{\max_{a}Q(S_{t+1}, a)}$</span> can be thought of the estimate of the Q value associated with the next state <span class="math-container">$S_{t+1}$</span> and the <strong>greedy action</strong> taken from that same state.</p>
  <h3>Q-learning is off-policy</h3>
  <p>Note that, when we update the value function, the agent is <strong>not</strong> really taking actions in the environment (the only action taken is <span class="math-container">$A_t$</span>, and it was taken, using the behavior policy, before the update!). Nonetheless, people often call Q-learning an <strong>off-policy algorithm</strong> because</p>
  <ol>
  <li><p>It uses the <span class="math-container">$\epsilon$</span>-greedy policy to interact with the environment (aka a <strong>behavior policy</strong>). In this case, actions are really taken, and the responses of the environment are really produced, observed, and used to update estimates of the <span class="math-container">$Q$</span> function.</p>
  </li>
  <li><p>It uses a <strong>target</strong> that is based on an estimate which is <strong>greedy</strong> (i.e. it uses <span class="math-container">$\color{blue}{\max_{a}Q(S_{t+1}, a)}$</span>).</p>
  </li>
  </ol>
  <p>Given that Q-learning uses estimates of the form <span class="math-container">$\color{blue}{\max_{a}Q(S_{t+1}, a)}$</span>, Q-learning is often considered to be performing updates to the Q values, as if those Q values were associated with the <strong>greedy policy</strong>, that is, the policy that always chooses the action associated with highest Q value. So, you will often hear that Q-learning finds a <strong>target policy</strong> (i.e. the policy that is derived from the last estimate of the Q function) that is <strong>greedy</strong> (so, usually, different from the behavior policy).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-13T18:48:47.270Z
Answers.Text: Small note: start and end of episodes do not necessarily have to be associated with specific states. In theory we can have a probability distribution over initial states $S_0$, although in practice the most common case certainly is that the starting state is always the same. It is relatively common that in practice that there are many different states that can all end the episode, though I believe that is already consistent with what you wrote :)
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-09T16:31:33.343Z
Answers.Text: @nbro: Thanks for your answer. I have a couple of questions to it as several things are unclear. 1) How can we actually calculate the max Q( S(t+1), a)? You write "We can roughly think of it as "the value that Q(St,At) should have been"". What is exactly meat by that? How can we know, what value it should have been? 2) Can you give me an example on how the Q-values are updated in each iteration (or a link where an example is explained in a comprehensive way)? 3) You claim that Q-learning used e-greedy policy for taking the actions and greedy policy for updating. Can other policies be used?
Answers.UserDisplayName: PeterBe
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-09T16:31:35.873Z
Answers.Text: 4) If we initialise all Q(s, a) to 0, will then not every max Q (s(t+1), a) be also 0 in each iteration? 5) If we always use a greedy policy to udate the Q values, I would assume that the chances are quite high that we will be stuck in a local (but not global) optimum. Why can we for example not also use the e-greedy policy for updating the Q values?
Answers.UserDisplayName: PeterBe
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-09T17:00:13.517Z
Answers.Text: @PeterBe I am not sure I understand your first question. $\max Q( S(t+1), a)$ is just the maximum state-action value function with respect to $a$. For example, say you have a function $f: \{1, 2 \} \rightarrow \{10, 5\}$, and define it like this: $f(1) = 10$ and $f(2) = 5$, then $\max_x f(x) = 10$ and $\text{argmax}_x f(x) = 1$. To answer your second question, remember that, during learning, $Q$ is an estimate of the true value function $q^*$. $\color{green}{R_{t+1}} + \gamma \color{blue}{\max_{a}Q(S_{t+1}, a)}$ is an estimate of the true value $q^*(S_t, A_t)$.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-09T17:02:48.137Z
Answers.Text: To answer your 3rd question, we don't know $q^*(S_t, A_t)$. @PeterBe This post is already too long and I already spent too much effort on it, so I don't plan to give you a step-by-step explanation of Q-learning, because that was not even the question originally. I explained Q-learning here, but I should not have done that. I recommend that you ask your other questions in separate posts, but make sure to search for answers on our site first, because I think some of your questions are already answered by my post above and other posts on the site. **Please, ask only one question per post!**
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-13T17:14:14.137Z
Answers.LastActivityDate: 2021-12-08T08:56:19.877Z
Answers.LastEditDate: 2021-12-08T08:56:19.877Z
Answers.UserDisplayName: nbro
Body: <p>Apparently, in the Q-learning algorithm, the Q values are not updated according to the "current policy", but according to a "greedy policy". Why is that the case? I think this is related to the fact that Q-learning is off-policy, but I am also not familiar with this concept. </p>
  
Tags: <reinforcement-learning><q-learning><off-policy-methods><greedy-policy>
Title: Why are Q values updated according to the greedy policy?
UserDisplayName: Shifat E Arman
ThreadText: # Why are Q values updated according to the greedy policy?
  
  (Asked by: username_0 on 2018-11-17)
  
  Apparently, in the Q-learning algorithm, the Q values are not updated according to the "current policy", but according to a "greedy policy". Why is that the case? I think this is related to the fact that Q-learning is off-policy, but I am also not familiar with this concept.
  
  **Tags:** reinforcement-learning, q-learning, off-policy-methods, greedy-policy
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-02-13. Score: 5
  
  # Short answer
  
  The Q values are updated using a **greedy policy** because, in the Q-learning algorithm, the $\max$ operator is used to determine the **target**, which is denoted by
  
  $$\color{green}{R\_{t+1}} + \gamma \color{blue}{\max\_{a}Q(S\_{t+1}, a)}$$
  
  Intuitively, the $\max$ operator is used because we assume that the **target policy** (the policy associated with the optimal value function that we want to learn) takes a **greedy action**, which is defined, in this context, as the action associated with the highest Q value: $\color{blue}{\max\_{a}Q(S\_{t+1}, a)}$ means that we are selecting the $Q$ value, associated with the (next) state $S\_{t+1}$, which corresponds to the action $a$, such that $Q(S\_{t+1}, a)$ is the highest (with respect to other possible actions from $S\_{t+1}$).
  
  Note that the $Q$ function receives as input a state and an action. So, for each state $s$, we have an action (among all possible actions, $a\_1, a\_2, \dots$, which we can take from the state $s$), denote it by $a^\*$, such that $Q(s, a^\*) > Q(s, a\_1)$, $Q(s, a^\*) > Q(s, a\_2)$, etc. In the expression $\color{blue}{\max\_{a}Q(S\_{t+1}, a)}$, we are basically selecting $Q(s, a^\*)$ for $s = S\_{t+1}$.
  
  # More explanations
  
  To explain all the components of this **target**, I will explain the Q-learning algorithm. Hopefully, after this explanation, you will be able to understand why Q-learning uses the **greedy policy** to update the Q values and why it is an **off-policy algorithm** (which is, IMHO, a quite unintuitive and confusing term to describe what off-policy actually means).
  
  ## How does Q-learning work?
  
  Here's the [Q-learning algorithm](https://github.com/udacity/rl-cheatsheet/blob/master/cheatsheet.pdf)
  
  [![enter image description here](https://i.sstatic.net/qymVD.png)](https://i.sstatic.net/qymVD.png)
  
  The Q-learning algorithm estimates a [**value function**](https://ai.stackexchange.com/q/10575/2444), known as the Q-function, associated with a policy $\pi$. Intuitively, it does that by simulating an [**agent**](https://ai.stackexchange.com/a/12995/2444) which takes **actions** in the **environment**, **observes** the impact of those actions on the environment in terms of the received **rewards** and the **new states** where the agent ends up in after taking those actions. Meanwhile, during this **exploration** of the environment, it attempts to estimate the optimal $Q$ function (i.e. the value function associated with the optimal policy, which, if followed, will give the agent the highest *amount of reward in the long run*, aka **return**).
  
  Q-learning proceeds in **episodes**. So, initially, you need to pass the number of episodes as input. You can think of episodes as iterations (like in any iterative optimisation algorithm). However, in the context of RL, an episode is a little bit more specific: the start and end of an episode are associated with specific states of the environment: the episode starts when the agent is in a **starting state** $S\_0$ (which can be sampled from a probability distribution over $S\_0$, if there is more than one) and ends when it is in a **terminal state**.
  
  In the pseudocode above, at the beginning of each episode, we initialise $t=0$, where $t$ represents the [**time step**](https://ai.stackexchange.com/a/11605/2444) of a specific episode.
  
  ### Inner/Episode loop
  
  We then have the following loop, which terminates when the agent reaches a terminal state:
  
  [![enter image description here](https://i.sstatic.net/66r6E.png)](https://i.sstatic.net/66r6E.png)
  
  So, at each episode, we run the loop above. The block of code inside this loop contains the main logic of the Q-learning algorithm.
  
  ### Behaviour policy
  
  On each iteration of this inner loop, the agent chooses an action $A\_t$ (the action at time step $t$ of the current episode) using a policy (which is known, in this context, as the [**behaviour policy**](https://ai.stackexchange.com/q/10492/2444), which should ensure that all states are sufficiently visited, [in order for tabular Q-learning to converge](https://ai.stackexchange.com/a/21408/2444)). In this case, [the $\epsilon$-greedy policy](https://ai.stackexchange.com/a/17626/2444) is used.
  
  ### How does this $\epsilon$-greedy policy work?
  
  If you look at the pseudocode above, $\epsilon$ is initialised at beginning of each episode. In the pseudocode above, $\epsilon$ can change from episode to episode, but assume, for simplicity, that, at every episode, it is a fixed small number (e.g. $0.01$). The statement
  
  > Choose action $A\_t$ using policy **derived from** $Q$ (e.g., $\epsilon$-greedy)
  
  means that, with probability $1 - \epsilon$, the **greedy action** is chosen, and, with probability $\epsilon$, a random action is taken.
  
  ### What is the greedy action in this case?
  
  In this case, the **greedy action** is the action, in the current state $S\_t$, which is associated with the highest Q value (given the current estimate of the Q value). It is exactly the same action as the action $a^\*$ (as I explained above). The difference is that, in this case, we choose $A\_t$ using the $\epsilon$-greedy policy: so, most of the time, we choose the greedy action, but, sometimes, we can also choose a random action.
  
  The agent then executes the just chosen action $A\_t$ in the environment, and it observes the impact of this action on the environment, which is determined by how the environment responds to this action: the response consists of a reward, $R\_{t+1}$, and a next state, $S\_{t+1}$.
  
  To recapitulate, the agent chooses an action using the $\epsilon$-greedy policy, executes this action on the environment, and it observes the response (that is, a reward and a next state) of the environment to this action. This is the part of the Q-learning algorithm where the agent interacts with the environment in order to gather some info about it, so as to be able to estimate the Q function.
  
  ### Q-learning update
  
  After that, the agent can update its estimate of the Q function using the following update rule
  
  $$\color{orange}{Q(S\_t, A\_t)} \leftarrow \color{red}{Q(S\_t, A\_t)} + \alpha ([\color{green}{R\_{t+1}} + \gamma \color{blue}{\max\_{a}Q(S\_{t+1}, a)}] - \color{red}{Q(S\_t, A\_t)})$$
  
  where $S\_t$ is the current state (of the current episode) the agent is in, $A\_t$ is the action chosen using the $\epsilon$-greedy policy (as described above), and $S\_{t+1}$ and $R\_{t+1}$ are respectively the next state and rewards, which, collectively, are the response of the environment to the just taken action $A\_t$.
  
  So, how is the estimate of this $Q$ function updated?
  
  First of all, I would like to note that, if you look at the beginning of the pseudocode above, $Q(s, a)$ is initialized arbitrarily for all states $s \in \mathcal{S}$ and for all actions $a \in \mathcal{A}$: it can e.g. be initialised to $0$. $Q(s, a)$ can e.g. be implemented as a matrix (or 2-dimensional array) $M \in \mathbb{R}^{|\mathcal{S}| \times |\mathcal{A}|}$, where $M[s, a] = Q(s, a)$, $|\mathcal{S}|$ is the number of states in your problem and $|\mathcal{A}|$ the number of actions.
  
  Furthermore, note that the symbol $\leftarrow$ means "assignment" (like assignment to a variable, in the context of programming). So, in the update rule above, we are assigning to $\color{orange}{Q(S\_t, A\_t)}$ (which will be the next or updated estimate of the Q value for the current state $S\_t$ and the just taken action from that state $A\_t$) the value $\color{red}{Q(S\_t, A\_t)} + \alpha (\color{green}{R\_{t+1}} + \gamma \color{blue}{\max\_{a}Q(S\_{t+1}, a)} - \color{red}{Q(S\_t, A\_t)})$. Let's break this value down.
  
  $\color{red}{Q(S\_t, A\_t)}$ (on the right side of the assignment) is the estimate of the Q value for the state $S\_t$ and action $A\_t$ before the assignment. So, we are summing $\color{red}{Q(S\_t, A\_t)}$ and $\alpha (\color{green}{R\_{t+1}} + \gamma \color{blue}{\max\_{a}Q(S\_{t+1}, a)} - \color{red}{Q(S\_t, A\_t)})$, and then we assign it to $\color{orange}{Q(S\_t, A\_t)}$ again.
  
  $\color{green}{R\_{t+1}} + \gamma \color{blue}{\max\_{a}Q(S\_{t+1}, a)}$ is what is often called the **target**. Q-learning is a **temporal-difference (TD) algorithm**, and TD algorithms update estimates of the value or action-value functions based on the difference between the current estimate, in the case of Q-learning it is denoted by $\color{red}{Q(S\_t, A\_t)}$ (on the right side of the $\leftarrow$), and a "target". So, in the Q-learning algorithm, $\color{green}{R\_{t+1}} + \gamma \color{blue}{\max\_{a}Q(S\_{t+1}, a)}$ is the target. We can roughly think of it as "the value that $\color{red}{Q(S\_t, A\_t)}$ should have been". So, in a certain way, we are performing [supervised learning](https://ai.stackexchange.com/q/14167/2444), where $\color{green}{R\_{t+1}} + \gamma \color{blue}{\max\_{a}Q(S\_{t+1}, a)}$ would be the [ground-truth label](https://ai.stackexchange.com/a/28109/2444) and $\color{red}{Q(S\_t, A\_t)}$ the current estimate, and so $[\color{green}{R\_{t+1}} + \gamma \color{blue}{\max\_{a}Q(S\_{t+1}, a)}] - \color{red}{Q(S\_t, A\_t)}$ would be the *error* (or *loss*): in fact, it is often called the **TD error**. However, note that this is not really supervised learning, because $\color{green}{R\_{t+1}} + \gamma \color{blue}{\max\_{a}Q(S\_{t+1}, a)}$ is **not** a ground-truth (it is partially an estimate, because of the part $\gamma \color{blue}{\max\_{a}Q(S\_{t+1}, a)} $, and it partially a ground-truth, because of $\color{green}{R\_{t+1}}$).
  
  To recapitulate, $\color{green}{R\_{t+1}} + \gamma \color{blue}{\max\_{a}Q(S\_{t+1}, a)}$ is the **target**, $\color{red}{Q(S\_t, A\_t)}$ is the current estimate, and $[\color{green}{R\_{t+1}} + \gamma \color{blue}{\max\_{a}Q(S\_{t+1}, a)}] - \color{red}{Q(S\_t, A\_t)}$ is the **TD error**. We are thus summing the "error" (weighted by the hyper-parameter $\alpha$, which is, in this case, often called the **learning rate**) and the current estimate $\color{red}{Q(S\_t, A\_t)}$ in order to produce the new estimate $\color{orange}{Q(S\_t, A\_t)}$.
  
  In the **target**, you can see that we are multiplying the $\color{blue}{\max\_{a}Q(S\_{t+1}, a)}$ by $\gamma$. This is a hyper-parameter (a parameter which often needs to be chosen by the programmer before the algorithm is executed), known as the **discount factor**. It controls the contribution of $\color{blue}{\max\_{a}Q(S\_{t+1}, a)}$ to the **target**: that is, how much of $\color{blue}{\max\_{a}Q(S\_{t+1}, a)}$ we want to include in the **target**. Recall that I've just said above that the **target** is composed of the reward $\color{green}{R\_{t+1}}$ (which is a [ground-truth](https://ai.stackexchange.com/a/28109/2444) or real-world experience, because it is directly received from the environment) and $\color{blue}{\max\_{a}Q(S\_{t+1}, a)}$ (which actually uses an estimate of the Q function, that is, it uses $Q(S\_{t+1}, a)$). So, $\gamma$ controls the contribution of an estimate to the [ground-truth](https://ai.stackexchange.com/a/28109/2444).
  
  As I said at the beginning of this answer, $\color{blue}{\max\_{a}Q(S\_{t+1}, a)}$ can be thought of as the $Q$ value associated with the next state $S\_{t+1}$ (which was observed by the agent after he has taken the action $A\_t$) and associated with the action $a$, such that $Q(S\_{t+1}, a)$ is the highest among all other possible actions from state $S\_{t+1}$. In other words, $\color{blue}{\max\_{a}Q(S\_{t+1}, a)}$ can be thought of the estimate of the Q value associated with the next state $S\_{t+1}$ and the **greedy action** taken from that same state.
  
  ### Q-learning is off-policy
  
  Note that, when we update the value function, the agent is **not** really taking actions in the environment (the only action taken is $A\_t$, and it was taken, using the behavior policy, before the update!). Nonetheless, people often call Q-learning an **off-policy algorithm** because
  
  1. It uses the $\epsilon$-greedy policy to interact with the environment (aka a **behavior policy**). In this case, actions are really taken, and the responses of the environment are really produced, observed, and used to update estimates of the $Q$ function.
  2. It uses a **target** that is based on an estimate which is **greedy** (i.e. it uses $\color{blue}{\max\_{a}Q(S\_{t+1}, a)}$).
  
  Given that Q-learning uses estimates of the form $\color{blue}{\max\_{a}Q(S\_{t+1}, a)}$, Q-learning is often considered to be performing updates to the Q values, as if those Q values were associated with the **greedy policy**, that is, the policy that always chooses the action associated with highest Q value. So, you will often hear that Q-learning finds a **target policy** (i.e. the policy that is derived from the last estimate of the Q function) that is **greedy** (so, usually, different from the behavior policy).
  
  > **Comments:**
  > **username_2**: Small note: start and end of episodes do not necessarily have to be associated with specific states. In theory we can have a probability distribution over initial states $S_0$, although in practice the most common case certainly is that the starting state is always the same. It is relatively common that in practice that there are many different states that can all end the episode, though I believe that is already consistent with what you wrote :)  
  > **username_3**: @nbro: Thanks for your answer. I have a couple of questions to it as several things are unclear. 1) How can we actually calculate the max Q( S(t+1), a)? You write "We can roughly think of it as "the value that Q(St,At) should have been"". What is exactly meat by that? How can we know, what value it should have been? 2) Can you give me an example on how the Q-values are updated in each iteration (or a link where an example is explained in a comprehensive way)? 3) You claim that Q-learning used e-greedy policy for taking the actions and greedy policy for updating. Can other policies be used?  
  > **username_3**: 4) If we initialise all Q(s, a) to 0, will then not every max Q (s(t+1), a) be also 0 in each iteration? 5) If we always use a greedy policy to udate the Q values, I would assume that the chances are quite high that we will be stuck in a local (but not global) optimum. Why can we for example not also use the e-greedy policy for updating the Q values?  
  > **username_1**: @PeterBe I am not sure I understand your first question. $\max Q( S(t+1), a)$ is just the maximum state-action value function with respect to $a$. For example, say you have a function $f: \{1, 2 \} \rightarrow \{10, 5\}$, and define it like this: $f(1) = 10$ and $f(2) = 5$, then $\max_x f(x) = 10$ and $\text{argmax}_x f(x) = 1$. To answer your second question, remember that, during learning, $Q$ is an estimate of the true value function $q^*$. $\color{green}{R_{t+1}} + \gamma \color{blue}{\max_{a}Q(S_{t+1}, a)}$ is an estimate of the true value $q^*(S_t, A_t)$.  
  > **username_1**: To answer your 3rd question, we don't know $q^*(S_t, A_t)$. @PeterBe This post is already too long and I already spent too much effort on it, so I don't plan to give you a step-by-step explanation of Q-learning, because that was not even the question originally. I explained Q-learning here, but I should not have done that. I recommend that you ask your other questions in separate posts, but make sure to search for answers on our site first, because I think some of your questions are already answered by my post above and other posts on the site. **Please, ask only one question per post!**  
  
  ---
  
  