24

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}_{p, \pi}[R_{t+1} + \gamma G_{t+1} | S_t = s, A_t = a]\;,$$ where $R_{t+1}$ is the random variable that represents the reward gained at time $t+1$, i.e. after we have taken action $A_t = a$ in state $S_t = s$, while $G_{t+1}$ is the random variable that represents the return, the sum of ...


6

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


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


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


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

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


4

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

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


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

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

The definition of the state-action value function is always the same. Your definition is correct, as $q_{\pi}(s,a)$ is conditioned on $a$, so you don't need to write $q_{\pi}(s,a)$ as an conditional expectation that depends on $\pi$. In fact, the conditional expectation is taken wrt the probability distribution $p(s',r|s,a)$. However, you need the subscript $...


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

Provided you have a finite number of states and actions, then there will not be an infinite number of terms. Therefore the state and action spaces need to be discrete and finite before the quote from the book applies. I am having a hard time understanding how one could solve this system of equations. There are a few techniques for solving simulteneous ...


3

Here's your equation with an additional couple of parenthesis that emphasizes the order of the operations (note that you had a small typo in your original equation). $$v_{\pi}(s) =\sum_a \pi(a \mid s) \left(\sum_{s',r} p(s',r \mid s,a)[r+ \gamma v_\pi(s')] \right)$$ Now, let me answer your other questions. Is the second sum using the index $a$ from the ...


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

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

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

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}) = ...


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

Reinforcement Learning is really fun because the agent will find any bug in your implementation and will exploit it. >>> take_left(0) 0 >>> take_left(1) -4 The agent figured out your bug with negative values and exploits negative indexing to get to the target faster.


2

A Bellman backup is an application of a Bellman operator. For example, the step $$ V(x)\leftarrow \alpha(R + \mathbf{E}[V(x')]) + (1-\alpha)V(x) $$ Is a Bellman backup for some learning rate $\alpha$. A Bellman error is $$ d(V(x), R + \mathbf{E}[V(x')]) $$ for some metric $d$, usually $d(x, y) = (x-y)^2$.


2

They have a few similarities, but they are quite different. Let me first give you a general description of both approaches/algorithms, so that you start to get a sense of their differences and similarities. Description Gradient descent (GD) can be applied to solving any optimization problem where your loss (aka cost or objective) function is differentiable ...


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


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