Hot answers tagged

9

That can be done. For example, Chapter 13 of the 2nd edition of Sutton and Barto's Reinforcement Learning book (page 332) has pseudocode for "Actor Critic with Eligibility Traces". It's using $G_t^{\lambda}$ returns for the critic (value function estimator), but also for the actor's policy gradients. Note that you do not explicitly see the $G_t^{\lambda}$ ...


7

Recent actor-critic algorithms do use $\lambda$-returns, but they are disguised as something called the Generalized Advantage Estimator defined as $A^{GAE}_t = \sum_{i=0}^{\infty} (\gamma\lambda)^i \delta_{t+i}$ where $\delta_t = r_t + \gamma V(s_{t+1}) - V(s_t)$. This turns out to be identically equal to $[G^\lambda_t - V(s_t)]$, i.e. the $\lambda$-return ...


5

In a Markov Decision Process (MDP) model, we define a set of states ($S$), a set of actions ($A$), the rewards ($R$), and the transition probabilities $P(s' \mid s, a)$. The goal is to figure out the best action to take in each of the states, i.e. the policy $\pi$. Policy To calculate the policy we make use of the Bellman equation: $$V_{i+1}(s)=R(s)+\gamma \...


5

To rewrite $G_t^\lambda$ recursively, our goal is to define it in terms of $$G_{t+1}^\lambda = (1-\lambda)\sum_{n=1}^\infty \lambda^{n-1}G_{t+1:t+n+1}.\tag{0}$$ The $\lambda$-return is a weighted average of all $n$-step returns. We will split up the summation by pulling out the one-step return $G_{t:t+1}$ and the first step's reward $R_{t+1}$. $$ \begin{...


5

There is a strong relationship between a value function and a return. Namely that a value function calculates the expected return from being in a certain state, or taking a specific action in a specific state. A value function is not a "return function", it is an "expected return function" and that is an important difference. A return is a measured value (...


3

$T = \infty$ and $\gamma = 1$ cannot be both true at the same time because the return defined in equation 3.11 is supposed to be a unified definition of the return for both continuing and episodic tasks. In the case of continuing tasks, $T = \infty$ and $\gamma = 1$ cannot be true at the same time, because the return may not be finite in that case (as I ...


3

It wouldn't make sense to define the return as you propose, from time 0 to $t$. Once we are in a state at time $t$ we don't care what the returns have been, rather what they will be in the future, thus returns are defined as the total sum of discounted rewards from the current time step onwards. This allows the agent to make decisions about which actions to ...


3

However, from the blogs and texts I read, the equations are expressed in terms of V and NOT Q. Why is that? MC and TD are methods for associating value estimates to time step based on experienced gained in later time steps. It does not matter what kind of value estimate is being associated across time, because all value functions are expressing the same ...


3

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 $n$th step return. They would only be equal as $n \rightarrow \infty$.


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 table is almost correct. It is a minor difference, you should not have a $R_0$, the top row, leftmost column of numbers should be empty. That is because the first reward is $R_1$ (a result of taking action $A_0$ in state $S_0$). The alignment of the columns on the right hand side is correct though. It might help to add the time step number at the top. ...


2

In the reinforcement learning setting, an agent interacts with an environment in (discrete) time steps, which are incremented after the agent takes an action, receives a reward and the "system" (the environment and the agent) moves to a new state. More precisely, at time step $t=0$ (the first time step), the environment (including the agent) is in some ...


2

Value function: How good it is to be in a state $s$ following policy $\pi$. There are different value functions. There's the state value function, often denoted as $v(s)$ (or $V(s)$), so it's a function of only one variable, i.e. $s$ (a state). There's the state-action value function $q(s, a)$ (or $Q(s, a$)). A value function is a function, so it's not a ...


2

Return refers to the total discounted reward, starting from the current timestep.


2

You know all the rewards. They're 5, 7, 7, 7, and 7s forever. The problem now boils down to essentially a geometric series computation. $$ G_0 = R_0 + \gamma G_1 $$ $$ G_0 = 5 + \gamma\sum_{k=0}^\infty 7\gamma^k $$ $$ G_0 = 5 + 7\gamma\sum_{k=0}^\infty\gamma^k $$ $$ G_0 = 5 + \frac{7\gamma}{1-\gamma} = \frac{5 + 2\gamma}{1-\gamma} $$


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

The discussion uses poor notation, there should be a time index. You obtain a list of tuples $(s_t, a_t, r_t, s_{t+1})$ and then, for every visit MC, you update $$Q(s_t, a_t) = Q(s_t, a_t) + \alpha (G_t - Q(s_t, a_t))\;;$$ where $G_t = \sum_{k=0}^\infty \gamma^k r_{t+k}$, for each $t$ in the episode. You can see that the returns for each time step are ...


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 ...


1

There are a few ways to resolve values of infinite sums. In this case, we can use a simple technique of self-reference to create a solvable equation. I will show how to do it for the generic case here of an MDP with same reward $r$ on each timestep: $$G_t = \sum_{k=0}^{\infty} \gamma^k r$$ We can "pop off" the first item: $$G_t = r + \sum_{k=1}^{\...


1

According to my understanding, you don't use just the current behavior policy for sampling. The importance sampling ratio is calculated as the product of the probability ratios for both the target and behaviour policy throughout the trajectory. See the calculation below, where the product is happening for all the probabilities throughout the trajectories. (...


1

As the accepted answer states, the return at the current timestep is equal to the sum of discounted rewards from all future timesteps until the end of the episode. In Chapter 5 of Sutton and Barto, returns must be used to estimate the state-value and action-value functions because episode lengths are unrestricted and may be greater than one. In contrast, ...


1

shouldn't the expected return be calculated for some faraway time in the future (𝑡+𝑛) instead of current time $t$? This is partly a notation issue, but $G_t$ is already the future sum of rewards as seen by the first (and correct) equation in your question. You don't actually know the value of any individual return $g_t$* until after $t+n$. However, you ...


1

I think most of it is correct. Q function(also called state-action value, or just action value): How good it is to be in a state S and perform action A while following policy π. It uses reward to measure the state-action value This is a bit off. Q function basically tells you how good it is to be in state S and perform action A, and follow policy $\pi$ ...


1

Perfect. To back up your intuition about there not being a $G_5$, refer to the definition of discounted return in the periodic case (3.11). $$G_t \doteq \sum_{k=t+1}^T \gamma^{k-t-1} R_k$$ You'll see that $G_5$ would be written as a sum with no terms in it, since $T=5$.


Only top voted, non community-wiki answers of a minimum length are eligible