0
$\begingroup$

I'm trying to wrap my head around the implementation of deep $Q$-learning, and why we even consider episodes in the first place. The usual set-up is that we initialize some starting state $s_0$, then let the agent run through the environment (following for example an epsilon-greedy policy with respect to the Q-values generate by a policy/online network) to create some set of episodes $e_t = (s_t, a_t, R_{t+1}, s_{t+1})$, where $s_t$ is the state at time $t$, $a_t$ is the action chosen at $s_t, R_{t+1}$ is the reward for taking action $a_t$ at state $s_t$, and $s_{t+1}$ is the state obtained from taking action $a_t$ at $s_t$.

In what follows, I denote the feedforward of state $s$ through the online net by $ff_o(s)$, and through the target net by $ff_t(s)$. Then, by construction, $$ff_o(s) = \begin{bmatrix} Q(s, a^1) \\ \vdots \\ Q(s, a^n)\end{bmatrix}$$ where $a^1, \dots, a^n$ denote the possible actions that the agent can take (ordered in some pre-determined way, and for some integer $n$). Suppose that $s'$ is the state obtained by taking action $a$ from state $s$. Then, we define $Q_{\max}(s, a) = \max ff_t(s')$. Our aim is to update the network parameters so that $Q(s, a)$ moves closer to $R(s, a) + \gamma Q_{\max}(s, a)$ for every state-action pair in our episodes, where $\gamma$ is the discount factor.

We define the loss function for our network by $$l(s, y) = \|ff_o(s) - y\|^2$$ where $y$ is the target output for input $s$, and $\|\cdot\|$ denotes the standard vector norm in $\mathbb{R}^n$. The training data takes the form $(s_t, y_t)$, where $s_t$ is the initial state in the episode $e_t$ and $y_t$ is the target output of the online network for input $s_t$. How should we choose the target outputs $y_t$?

I see two potential approaches.

  1. Suppose that $a_t = a^k$ in our ordering of the actions. Let $x[i]$ denote the $i^{\text{th}}$ component of the vector $x \in \mathbb{R}^n$. Then, we choose $$y_t[i] = \begin{cases} R(s_t,a_t) + \gamma Q_{\max}(s_t, a_t), &\text{if } i = k, \\ ff_o(s_t)[i], &\text{if } i \ne k \end{cases}.$$ Effectively, this says that we choose the component of $y_t$ that corresponds to the action $a_t$ of the episode $e_t$ as the right-hand side of the Bellman equation. Otherwise, we choose the $Q$-values as they currently are. In that sense, our loss function reduces to $(Q(s_t, a_t) - R_{t+1} - \gamma Q_{\max}(s_t, a_t))^2$. Is this the typical strategy?
  2. In the case that the reward function $R(s, a)$ is given, we choose $y[i] = R(s, a^i) + \gamma Q_{\max}(s, a^i)$ for all $i$. That is, we calculate the RHS of the Bellman equation over all possible actions that we can take from the state $s$. In this sense, the episodes only enter as some way to sample states $s_t$ from which the corresponding target outputs $y_t$ can be generated. Is there a problem with this approach? What stops us from just randomly sampling states in our environment and generating training data this way, instead of letting the agent explore in episodes?
$\endgroup$
9
  • $\begingroup$ Hi and welcome to the community! From what you write I see some misunderstandings. What i first recommend to everyone before touching approximate methods (e.g. NNs) is to understand very well simple tabular cases. With DeepQL there is no policy network. At a high level, with Actor Critic approaches you have Actor (policy gradient therefore policy net) and critic (value based method, q-learning). $\endgroup$ Oct 30, 2023 at 8:00
  • $\begingroup$ For only critic methods (DeepQL), the input is the state and output is a vector Q PER ACTION. So each output is Q(s, ai). Also Q is an ACTION-value function Q=Q(s,a) whereas V=V(s) is a STATE-value function. If you take into consideration what I wrote, and you still think that your question is unanswered, could you rephrase your question please? $\endgroup$ Oct 30, 2023 at 8:02
  • $\begingroup$ @Constantinos I have updated the title to "deep Q-learning", as that ultimately is what I'm doing based on what you have said. The input is the state, and output is the vector of all Q-values corresponding to the input state. My question regards how such a network is trained. I will try to rephrase it now in the comments, and if you believe it is more clear, I will attempt to update the original post accordingly. $\endgroup$ Oct 30, 2023 at 9:45
  • $\begingroup$ I understand that we aim to push the output of the NN so that the resulting $Q$-values satisfy the Bellman equation. First, given a state-action pair $(s, a)$, we may calculate $s'$ as the action obtained by taking action $a$ from state $s$. We then input $s'$ to the NN and calculate $Q_{\max}(s) = \max_{a'} Q(s', a')$, after which out target value for $Q(s, a)$ becomes $R(s, a) + \gamma Q_{\max}(s)$ for discount factor $\gamma$. However, this is just one element in the output vector of the NN. How should we choose the target values for the remaining $Q(s, a_i)$ for $a_i \ne a$? $\endgroup$ Oct 30, 2023 at 9:52
  • $\begingroup$ First of all: Q=Q(s,a) always! Q(s) is wrong if Q is an action value function. So $Q_{max}(s)$ doesn't mean anything as you do not integrate over actions. You simply pick the maximum value from the Q vector. On your question: we do not as we do not know the R(s,a) as we did not select these actions. The main idea is to use a batch of collected experience (s,a,r,s') and perform the training wrt to a loss function (sum over squared errors). There are tons of implementations out there and you can debug to see all the various dimensions! $\endgroup$ Oct 31, 2023 at 6:59

1 Answer 1

1
$\begingroup$

The neural network's weights are updated to reduce the difference between the predicted Q-value $Q(s,a;θ)$ and the target Q-value $y$. Since we're only interested in the action that was actually taken, the gradient for actions not taken is zero, and they do not affect the update. This selective updating means that the neural network learns the value of the action that was chosen, without interfering with the values of other actions.

Your loss is dependent only on actions that the agent selected. Since the loss only depends on the Q-value for the action that was actually taken, the partial derivatives (gradients) of the loss with respect to the Q-values of the other actions are zero. This is why the parameters of the network are only updated in relation to the action that was actually taken and the Q-values for the other actions remain unchanged for this particular training instance.

$\endgroup$
5
  • $\begingroup$ First, thank you for you answer. I've made some big edits to the question, and I believe it is much more clear now (the particular questions are in boldface). Although I do believe that you have already answered a part of my question, I would greatly appreciate it if you took a look at the edit, as I still have some doubts. $\endgroup$ Oct 31, 2023 at 12:45
  • $\begingroup$ I hope the issue with the gradient has been resolved. The rationale for combining Reinforcement Learning (RL) with Neural Networks (NN) in value-based methods is to approximate the Q-action values. Essentially, this approach employs supervised learning to minimize the mean squared error between the estimated Q-values (for the actions taken) and the observed returns. $\endgroup$ Nov 1, 2023 at 4:10
  • $\begingroup$ These returns are calculated by backtracking the reward from the end of an episode to the beginning, which explains why sequences of states (s), actions (a), subsequent states (s'), and rewards (r) are required (so random samples aren't good as you will get only the immediate reward). It is important to note that the Q-values are estimates of the expected return. $\endgroup$ Nov 1, 2023 at 4:13
  • $\begingroup$ Now for supervised learning you need the output of your network and the real observed return values. However, the return is calculated by taking into account some future return estimation. So we "correct" our observed "return" (r:immediate reward) with an estimation maxQ(s',a') which comes from the network. This is unstable as our network changes parameters after every update. Therefore we use a separate network that is updated slower than the agent's network.At the end we still do SL but our target is not exactly "perfect". As you can see exploration helps a lot in the overall training setup. $\endgroup$ Nov 1, 2023 at 4:18
  • $\begingroup$ If you try tabular Q-learning in a 3x3 gridworld and write the equations you will get better intuition. As I mentioned, for DeepQ there are multiple implementations that will help you debug and get concrete numerical examples. $\endgroup$ Nov 1, 2023 at 4:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.