27 votes
Accepted

What is the Bellman operator in reinforcement learning?

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}...
user avatar
8 votes
Accepted

Why does the state-action value function, defined as an expected value of the reward and state value function, not need to follow a policy?

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 ...
user avatar
7 votes
Accepted

What is the proof that policy evaluation converges to the optimal solution?

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. ...
user avatar
  • 33.8k
5 votes

Why can the Bellman equation be turned into an update rule?

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 ...
user avatar
  • 33.8k
5 votes
Accepted

Apart from the state and state-action value functions, what are other examples of value functions used in RL?

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. ...
user avatar
5 votes
Accepted

What is the difference between a greedy policy and an optimal policy?

I would like to know if the optimal value function can also be defined as $$v_*(s_t) = \max_{a \in A(s_t)} \big\{ E_F \left[ r_{t+1} | s_t,a \right]+ \delta E_F \left[v_* \left(s_{t+1}\right)| s_t,a \...
user avatar
4 votes

Why does the state-action value function, defined as an expected value of the reward and state value function, not need to follow a policy?

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}...
user avatar
  • 938
4 votes
Accepted

Why is there an expectation sign in the Bellman equation?

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 $\...
user avatar
  • 78
4 votes
Accepted

Why doesn't value iteration use $\pi(a \mid s)$ while policy evaluation does?

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 ...
user avatar
4 votes

Why are the Bellman operators contractions?

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 ...
user avatar
  • 33.8k
4 votes
Accepted

How would I compute the optimal state-action value for a certain state and action?

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 ...
user avatar
3 votes
Accepted

How can we find the value function by solving a system of linear equations without knowing the policy?

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 ...
user avatar
3 votes
Accepted

How are afterstate value functions mathematically defined?

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 ...
user avatar
  • 33.8k
3 votes
Accepted

In reinforcement learning, does the optimal value correspond to performing the best action in a given state?

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 ...
user avatar
3 votes
Accepted

Connection between the Bellman equation for the action value function $q_\pi(s,a)$ and expressing $q_\pi(s,a) = q_\pi(s, a,v_\pi(s'))$

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 ...
user avatar
3 votes
Accepted

Why we don't use importance sampling in tabular Q-Learning?

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, ...
user avatar
3 votes
Accepted

Why is $G_{t+1}$ is replaced with $v_*(S_{t+1})$ in the Bellman optimality equation?

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 ...
user avatar
3 votes
Accepted

Are these two definitions of the state-action value function equivalent?

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 ...
user avatar
  • 33.8k
3 votes

How can we find the value function by solving a system of linear equations?

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 ...
user avatar
3 votes
Accepted

Where are the parentheses in the Bellman update rule?

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) ...
user avatar
  • 33.8k
3 votes
Accepted

calculating the value of a state in an optimal policy analytically and iteratively

In the gridworld setting, you can replicate the lecture's results, by defining the reward function $R_t(s,a) = R(s)$, meaning that the reward function simply aggregates only on the current state and ...
user avatar
  • 889
3 votes

What is the Bellman equation for V(s) in the case of a deterministic environment?

Your 2nd equation is the Bellman optimality equation (BOE) for $V$. So, to emphasise that, you could write it as follows $$ V^\color{red}{*}(s) = \max_a(R(s,a) + \gamma\sum_{s'} P(s,a,s') V^\color{red}...
user avatar
  • 33.8k
3 votes
Accepted

Determining to terminate at a reward or not

I am trying to understand how you would determine whether it is better for the agent to terminate at the state with the number 3 or to continue to the state with a number 4 to collect the more reward? ...
user avatar
3 votes

Can we also estimate $V_{\pi}$ with SARSA?

What you suggest will work, the main restriction is needing to know $\pi$ fully in order to perform the conversion. If you know that you are going to be estimating $V_{\pi}$ from the start, and have a ...
user avatar
2 votes

Why is $G_{t+1}$ is replaced with $v_*(S_{t+1})$ in the Bellman optimality equation?

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 ...
user avatar
2 votes
Accepted

Why do Bellman equations indirectly create a policy?

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$...
user avatar
  • 9,379
2 votes

Why is there an expectation sign in the Bellman equation?

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),...
user avatar
  • 33.8k
2 votes
Accepted

How is the DQN loss derived from (or theoretically motivated by) the Bellman equation, and how is it related to the Q-learning update?

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] \; ....
user avatar
2 votes

What is the Bellman Equation actually telling?

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(...
user avatar

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