21

The notation I'll be using is from two different lectures by David Silver and is also informed by these slides. The expected Bellman equation is $$v_\pi(s) = \sum_{a\in \cal{A}} \pi(a|s) \left(\cal{R}_s^a + \gamma\sum_{s' \in \cal{S}} \cal{P}_{ss'}^a v_\pi(s')\right) \tag 1$$ If we let $$\cal{P}_{ss'}^\pi = \sum\limits_{a \in \cal{A}} \pi(a|s)\cal{P}_{ss'}^a ...


8

Let's first write the state-value function as $$q_{\pi}(s,a) = \mathbb{E}_{s_{t},r_{t} \sim E,a_t \sim \pi}[r(s_t,a_t) + \gamma G_{t+1} | S_t = s, A_t = a]\; ;$$ where $r(s_t,a_t)$ is written to show that the reward gained at time $t+1$ is a function of the state and action tuple we have at time $t$ (note here that $G_{t+1}$ would be just the sum of future ...


5

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

First of all, efficiency and convergence are two different things. There's also the rate of convergence, so an algorithm may converge faster than another, so, in this sense, it may be more efficient. I will focus on the proof that policy evaluation (PE) converges. If you want to know about its efficiency, maybe ask another question, but the proof below also ...


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

David Ireland gives a fantastic answer, and I will provide an intuitive and gentle (but less rigorous) answer for those who are unfamiliar with the relevant statistical concepts. Next reward $R_{t+1}$: The next reward $R_{t+1}$ is solely dependent on the current state $S_t$ and action $A_t$. It is only dependent on the policy because the policy details the ...


3

It seems that you are getting confused between the definition of a Q-value and the update rule used to obtain these Q-values. Remember that to simply obtain an optimal Q-value for a given state-action pair we can evaluate $$Q(s, a) = r + \gamma \max_{a'} Q(s', a)\;;$$ where $s'$ is the state we transitioned into (note that this only holds when obtaining the ...


3

Your equations all look correct to me. It is not possible to solve the linear equation for state values in the vector $V$ without knowing the policy. There are ways of working with MDPs, through sampling of actions, state transitions and rewards, where it is possible to estimate value functions without knowing either $\pi(a|s)$ or $P^{a}_{ss'}$. For instance,...


3

Based on this and this resources, let me give an answer to my own question, but, essentially, I will just rewrite the contents of the first resource here, for reproducibility, with some minor changes to the notation (to be consistent with Sutton & Barto's book, 2nd edition). Note that I am not fully sure if this formulation is universal (i.e. maybe there ...


3

Your understanding of the Bellman equation is not quite right. The state-action value function is defined as the expected (discounted) returns when taking action $a$ in state $s$. Now, in your equation (2) you have conditioned on taking action $a'$ in the inner expectation - this is not what happens in the state-action value function, you do not condition on ...


3

In Tabular Q-learning the update is as follows $$Q(s,a) = Q(s,a) + \alpha \left[R_{t+1} + \gamma \max_aQ(s',a) - Q(s,a) \right]\;.$$ Now, as we are interested in learning about the optimal policy, this would correspond to the $\max_aQ(s',a)$ term in the TD target because that is how the optimal policy chooses its actions - i.e. $\pi_*(a|s) = \arg\max_aQ_*(...


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

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

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

I am wondering which definition is correct. The asterisk * in both the definitions stands for "optimal" in the sense of "value when following the optimal policy" So this one is correct: $V^*$ actually assumes the optimal action in a given state, meaning $V^*$ would be $50$ in the above case However, you have got the definition of Q ...


3

Why are we allowed to convert the Bellman equations into update rules? There is a simple reason for this: convergence. The same chapter 4 of the same book mentions it. For example, in the case of policy evaluation, the produced sequence of estimates $\{v_k\}$ is guaranteed to converge to $v_\pi$ as $k$ (i.e. the number of iterations) goes to infinity. There ...


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

The Bellman optimality equation is given by $$q_*(s,a) = \sum_{s' \in \mathcal{S}, r \in \mathcal{R}}p(s',r \mid s,a)(r + \gamma \max_{a'\in\mathcal{A}(s')}q_*(s',a')) \tag{1}\label{1}.$$ If the reward is multiplied by a constant $c > 0 \in \mathbb{R}$, then the new optimal action-value function is given by $cq_*(s, a)$. To prove this, we just need to ...


2

Policy gradient methods directly learn parameters of a policy function, which is a mapping from states to actions. For example, $p(s, a)$ can denote a function which takes a state $s$ and an action $a$ as input, and returns a probability of taking action $a$ in state $s$ as output (equivalently it could just take $s$ as input, and output a vector or a ...


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

You appear to comparing the value table update steps in policy iteration and value iteration, which are both derived from Bellman equations. Policy iteration In policy iteration, a policy lookup table is generated, which can be arbitrary. It usually maps a deterministic policy $\pi(s): \mathcal{S} \rightarrow \mathcal{A}$, but can also be of the form $\pi(a|...


2

The inequality \begin{align} \left\|T^{\pi} V-T^{\pi} U\right\|_{\infty} & \leq \gamma\|V-U\|_{\infty} \label{1}\tag{1}, \end{align} where $U$ and $V$ are two value functions, follows from the definition of Bellman policy operator (at slide 16) \begin{align} T^{\pi} V(s) &\triangleq R(s, a)+\gamma \sum_{s^{\prime}} \operatorname{Pr}\left(s^{\prime}...


2

The Bellman equation in RL is usually defined $$v_\pi(s) = \sum_a \pi(a|s) \sum_{s', r} p(s', r|s, a)\left[r + v_\pi(s')\right] = \mathbb{E}_{s' \sim p, a \sim \pi}\left[r(s, a) + v_\pi(s')\right] \; .$$ The way you have written it is correct, but I just thought I would point this out. Regardless, your intuition is correct in that it expresses a recursive ...


2

For a Markov Decision Process $(\mathcal{S}, \mathcal{A}, P, R)$ (here $P(s, s') = \mathbb{P}(S_{t+1} = s' | S_t = s, A_t = a))$;, let us define the value of being in a certain state. That is, $$v_\pi(s) = \mathbb{E}_{a_i \sim \pi, s_i \sim P}\left[\sum_{i=0}^\infty \gamma^{i+t}r(s_{t+i}, a_{i+t}) | S_t =s\right].$$ That is, the value of being in state $s$ ...


2

There's not much to derive here it's simply a definition of Bellman operator, it comes from Bellman equation. If you're wondering why \begin{equation} Q^{\pi} = (I - \gamma P^{\pi})^{-1}r \tag{1} \end{equation} they state that $Q^{\pi}$ is a fixed point which means if you apply Bellman operator to it you get the same value \begin{equation} T^{\pi}(Q^{\pi}) = ...


1

What am I missing here? You are not missing anything mathematically. Potentially what you are missing is that the discount factor $\gamma$, is part of the problem definition. In reinforcement learning (RL), you do not always solve problems to obtain the highest total sum of rewards. Instead you solve problems to obtain the highest expected return on any ...


1

I will refer to $\mathcal T^{\pi} $as $\mathcal T$ and $P^{\pi}$ as $P$ for notational simplicity \begin{align} (\mathcal{T})^{n+1} Q &= \mathcal{T}(\mathcal{T}(...(\mathcal{T}(Q))))\\ &= r + \gamma P(r + \gamma P(...(r + \gamma P Q)))\\ &= r + r\sum_{i=1}^{n} \gamma^i P^i + \gamma^{n+1} P^{n+1} Q \end{align} \begin{align} \mathcal{T}_{\lambda}Q &...


1

Just to add to the previous answer some more background and intuition. The background of Bellman equation comes from optimal control theory of dynamic systems of form (in discrete time case) \begin{equation} s_{k+1} = f_d(s_k, a_k) \tag{1} \end{equation} where $s_k$ represents state at time $k$ and $a_k$ action at time $k$. The goal is to optimize multistage ...


1

In general they are not the same and that should be clear as to why -- mathematically you are conditioning on an extra random variable being known in the state-action value function. You have the correct relationship between them, but I think your understanding of the two may be slightly off. The state-action value function is a function of both $s$ and $a$ ...


1

Theorem The optimal state-action value function of $r'(s, a) \triangleq r(s, a) + c$, for $c \in \mathbb{R}$, would be \begin{align} q_*(s, a) + c + c\gamma + c \gamma^2 + c \gamma^3 + \dots &=q_*(s, a) + c \left( 1 + \gamma + \gamma^2 + \gamma^3 + \dots \right) \\ &= q_*(s, a) + c \left( \sum_{k=0}^{\infty} \gamma^{k} \right) \\ &=q_*(s, a) + c\...


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