# Tag Info

Advantage function: $A(s,a) = Q(s,a) - V(s)$ More interesting is the General Value Function (GVF), the expected sum of the (discounted) future values of some arbitrary signal, not necessarily reward. It is therefore a generalization of value function $V(s)$. The GVF is defined on page 459 of the 2nd edition of Sutton and Barto's RL book as $$v_{\pi,\gamma,C}... 5 We are ultimately interested in getting an optimal policy, that is the optimal sequence of actions to reach the final goal. State values on its own don't provide that, they tell you expected return from specific state onward but they don't tell you which action to take. In order to derive an optimal action in a specific state you would have to simulate all ... 5 Not quite. You are missing the reward at time step t+1. The definition you are looking for is (leaving out the \pi subscripts for ease of notation)$$q(s,a) = \mathbb{E}[R_{t+1} + \gamma v(s') | S_t=s,A_t=a] = \sum_{r,s'}(r + v(s'))p(s',r|s,a)\;.$$Because q(s,a) relates to expected returns at time t, and returns are defined as G_t = \sum_{b = 0}... 4 There needs to be an E_{\pi} over the infinite discounted return term because of two reasons- The policy could be stochastic in nature. That is, for any given state s_t at time t, the policy \pi(s_t) does not provide a deterministic action a, but rather, it provides us with a distribution over the possible next states, that is the action at time ... 4 In the Sutton and Barto book q(s,a) is used to denote the true expected value of taking action a in state s, whereas capital Q(s,a) is used to denote an estimate of q(s,a). However, there is likely to be a lot of inconsistency in the literature as each author has their own preference on how to denote things. I would encourage you to consider ... 3 The value of a state depends on the policy that you use, so I'll make the assumption here that you're talking about value using the optimal policy. According to the optimal policy, the agent would choose to stay in the square (1,1) every time, but since it has a 0.8 probability of actually staying (and 0.2 probability of dying), we can compute the value of ... 3 These two definitions are not exactly the same, even though they have a very similar formulation. David Silver's notation is probably an abuse of notation. The first difference between those two definitions is that, in the case of David Silver's slides, the policy is parametrized by \theta (i.e. the policy could be represented e.g. by a neural network), ... 3 Can someone provide the reasoning behind why G_{t+1} is equal to v_*(S_{t+1})? The two things are not usually exactly equal, because G_{t+1} is a probability distribution over all possible future returns whilst v_*(S_{t+1}) is a probability distribution derived over all possible values of S_{t+1}. These will be different distributions much of the ... 3 Your calculations are correct, but you have misinterpreted the equations and the diagram. The index k in v_k for the diagram refers to the policy evaluation update iteration only, and is not related to the policy update step (which uses the notation \pi' and does not mention k). Policy improvement consists of multiple sweeps through states to fully ... 3 The deep Q-learning (DQL) algorithm is really similar to the tabular Q-learning algorithm. I think that both algorithms are actually quite simple, at least, if you look at their pseudocode, which isn't longer than 10-20 lines. Here's a screenshot of the pseudocode of DQL (from the original paper) that highlights the Q target. Here's the screenshot of Q-... 3 Whats does the target Q-values represent? In a DQN, which uses off-policy learning, they represent a refined estimate for the expected future reward from taking an action a in state s, and from that point on following a target policy. The target policy in Q learning is based on always taking the maximising action in each state, according to current ... 3 I was able to solve the problem with the help of comment from @NeilSlater. The main issue for non-convergence was that I was not decaying the learning rate appropriately. I put a decay rate of -0.00005 on the learning rate lr and subsequently Q-Learning also converged to the same value as value iteration. 3 Removing the learning rate will likely yield poor convergence to the optimal policy and optimal Q-values. Note that the current policy is completely dependent on the Q-values, as we take the action with highest Q-value in a given state (with a few other considerations such as exploration, etc.). If we were to remove the learning rate, then we are making a ... 3 So, naturally, if you've observed something that contradicts the theoretical properties of Value Iteration, something's wrong, right? Well, the code you've linked, as it is, is fine. It works as intended when all the values are initialized to zero. HOWEVER, my guess is that you're the one introducing an (admittedly very subtle) error. I think you're changing ... 2 Consider a very simple grid-world, consisting of 4 cells, where an agent starts in the bottom-left corner, has actions to move North/East/South/West, and receives a reward R = 1 for reaching the top-right corner, which is a terminal state. We'll name the four cells NW, NE, SW and SE (for north-west, north-east, south-west and south-east). We'll ... 2 Depending on your needs and the size of the project, you might be better off making a custom set of environments. If you'd rather not do that, though, you should take a look at OpenAI's CoinRun environment. A high-level description can be found in their blog post. The "RandomMazes" version of this environment might be useful to you. And if you want to make ... 2 When training a Deep Q network with experienced replay, you accumulate what is known as training experiences e_t = (s_t, a_t, r_t, s_{t+1}). You then sample a batch of such experiences and for each sample you do the following. Feed s_t into the network to get Q(s,a;\theta). Feed s_{t+1} into the network to get Q(s’,a’,\theta). Choose max_aQ(s’,a’,... 2 It seems to me that you're thinking about the parameters a and b as being characteristic of the agent that's moving in the environment (therefore determining the final policy), but they are actually a characteristic of the environment. Think of a frozen lake. You want to pass the lake but there is a hole five meters in front of you. Let's say you have boots ... 2 First of all, Q_\pi(s, a) IS DEFINED AS the value (i.e. the expected return) of taking some action a in some state s, AND THEN following some given policy \pi (until e.g. the end of the game or your life). In other words, suppose that you take action a in state s, AND THEN use the policy \pi to behave in the world until you die, then Q_\pi(s, ... 2 Note that for a general policy \pi we have that q_{\pi}(s,a) = \mathbb{E}_{\pi}[G_t | S_t = s, A_t = a], where in state S_t we take action a and thereafter following policy \pi. Note that the expectation is taken with respect to the reward transition distribution \mathbb{P}(R_{t+1} = r, S_{t+1} = s' | A_t = a, S_t = s) which I will denote as p(s'... 2 By definition of V_{n+1}, we have: V_{n+1} = \frac{\sum_{k=1}^{n} W_{k} G_{k}}{\sum_{k=1}^{n} W_{k}} \; \tag{1} Then, taking the n^{th} term out of the sum in the numerator, we have: V_{n+1} = \frac{W_{n}G_{n} \; + \; \sum_{k=1}^{n-1} W_{k} G_{k}}{\sum_{k=1}^{n} W_{k}} \; \tag{2} Then, from the definition of V_n, V_{n} = \frac{\sum_{k=1}^{n-1} ... 2 Do policy independent state and action values exist in reinforcement learning? No. They do not exist, because in order to progress in any MDP and receive any reward - i.e. to get any measure of value - you must take an action. Any consistent means of selecting actions is a policy, and the nature of that policy impacts which transitions and rewards you ... 2 Can we say that Q^\pi(s, a) = V^\pi(s) No. The correct relationship is this:$$V^\pi(s) = \sum_a \pi(a|s) Q^\pi(s, a)$$or, if you have a deterministic policy a = \pi(s) you can instead write:$$V^\pi(s) = Q^\pi(s, \pi(s))$$Intuitively, this is because the V^\pi(s) is the expected future return when following the policy \pi from state s, ... 2 I assume this is an iterative function. It means the current V(S_t) is the sum of the previous plus some adjustment. The arrow is like an assignment. In code, you would do vst = vst + alpha * (gt - vst) So vst will be overwritten. 2 In addition to this answer, I would like to note that, if the future trajectories were fixed (i.e. the environment and the policies were deterministic, and the agent always starts from the same state), the expectation of the sum (of the fixed rewards) would simply correspond to the actual sum, because the sum is a constant (i.e. the expectation of a constant ... 2 I will fill in some details in shaabhishek's answer for people who are interested. With this in mind, what is the value of a square (1,1)? First of all, the value function is dependent on a policy. The supposed correct answer you provided is the value of (1, 1) under the optimal policy, so from now on, we will assume that we are finding the value ... 2 isn't then v_\pi(s) just the expected action value function at s over all actions a that are given by the policy \pi, namely v_\pi(s) = E_{a \sim \pi}[q_\pi(s,a) | S_t = s, A_t = a] = \sum_{a \in A}\pi(a|s) q_\pi(s,a)? Yes this is 100% correct. There is no "trick" to this or deeper thought needed. You have correctly isolated the key ... 2 Why is the expected return in Reinforcement Learning (RL) computed as a sum of cumulative rewards? That is the definition of return. In fact when applying a discount factor this should formally be called discounted return, and not simply "return". Usually the same symbol is used for both (R in your case, G in e.g. Sutton & Barto). There ... 2 In general, \mathbb{E}_\pi[G_{t:t+n}|S_t = s] \neq v_\pi(s). v_\pi(s) is defined as \mathbb{E}_\pi[\sum_{k=0}^{\infty} \gamma^k R_{t+k+1} | S_t = s], so you should be able to see why the two are not equal when the LHS is an expectation of the nth step return. They would only be equal as n \rightarrow \infty. 1 Ordinary variables vs Random Variables The difference is whether you're talking about a ordinary variable or a random variable. For instance, the q-function (lowercase) is an expectation value (i.e. not a random variable), conditioned on a specific state-action pair:$$ q(s,a)\ =\ \mathbb{E}_t\left\{ R_t+\gamma R_{t+1} + \gamma^2R_{t+2}+\dots\,\Big|\, S_t=...