5
$\begingroup$

What does the Bellman equation actually say? And are there many flavours of that?

I get a little confused when I look for the Bellman equation, because I feel like people are telling slightly different things about what it is. And I think the Bellman Equation is just basic philosophy and you can do whatever you want with that.

The interpretations that I have seen so far:

Let's consider this grid world.

+--------------+
| S6 | S7 | S8 |
+----+----+----+
| S3 | S4 | S5 |
+----+----+----+
| S0 | S1 | S2 |
+----+----+----+
  • Rewards: S1:10; S3:10
  • Starting Point: S0
  • Horizon: 2
  • Actions: Up, Down, Left, Right (If an action is not valid because there is no space, you remain in your position)

The V-Function/Value:

It tells you how good is it to be in a certain state.

With a horizon of 2, one can reach:

S0==>S3 (Up)   (R 5)
S0==>S0 (Down) (R 0)
S0==>S1 (Right)(R10)
S0==>S0 (Left) (R 0)

From that onwards

S0==>S3 (Up)   (R 5)
S0==>S0 (Down) (R 0)
S0==>S1 (Right)(R10)
S0==>S0 (Left) (R 0)

S1==>S4 (Up)   (R 0)
S1==>S1 (Down) (R10)
S1==>S2 (Right)(R 0)
S1==>S0 (Left) (R 0)

S3==>S6 (Up)   (R 0)
S3==>S0 (Down) (R 0)
S3==>S3 (Right)(R 5)
S3==>S2 (Left) (R10)

Considering no discount, this would mean that it is R=45 good to be in S0, because these are the options. Of course, you can't grab every reward, because you have to decide. Do I need to consider the best next state yet, because this would obviously reduce my expected total reward, but as I can only make two steps it would tell me what is really possible. Not what the overall Reward R(s) in that range is.

The Q-Function/Value

This function takes a state and an action, but I am not sure. If that means that I have a reward function that just considers my actions as well to give me a reward. Because in the previous example I just have to land on a state (It doesn't really matter how I get there). But this time I get a reward, when I choose a certain action. R(s,a) But otherwise I do not rate the best action and select that next state to calculate the next state. I choose every next step and from that I choose the 2nd next.

Optimization V-function or Q-function

This works the same as V-Function or Q-Function, but it just considers the next best award. Some sort of greedy approach:

First step:

S0==>S3 (Up)   (R 5) [x]
S0==>S0 (Down) (R 0) [x]
S0==>S1 (Right)(R10)
S0==>S0 (Left) (R 0) [x]

Second Step:

S1==>S4 (Up)   (R 0) [x]
S1==>S1 (Down) (R10) 
S1==>S2 (Right)(R 0) [x]
S1==>S0 (Left) (R 0)

So, this would say that is the best I can do in two steps. I know that there is a problem, because when I just follow a greedy approach I risk that I won't get the best result, if I would have had a reward of 1000 on S2 later.

But still, I just want to know, if I have a correct understanding. I know there might be many flavours and interpretations but at least I want to know that is the correct name of these approaches.

$\endgroup$
6
  • $\begingroup$ Your main questions seem to be 1. "What is the Bellman equation telling us?" and 2. "Are there different variants of the BE?". These are already 2 distinct questions that should be asked in their own separate post, so this post is already too broad and I could close it as such. In addition to that, you're also talking about value functions and there are some details/calculations that I don't think are really relevant to answer your 2 main questions. So, I suggest that you remove all the details that are not really necessary to answer your 2 main questions because this post is already long. $\endgroup$ – nbro Dec 21 '20 at 17:13
  • $\begingroup$ The answers below seem to address what are the Bellman equations and what they are telling us. They do not seem to address any of the details or calculations that you're performing. If you're interested in specific details, I suggest that you ask another question specifically asking about something that you don't understand about those calculations or value functions. Alternatively, instead of removing all the details, you could leave just a simplified version of your calculations that is relevant to your 2 main questions. $\endgroup$ – nbro Dec 21 '20 at 17:17
  • $\begingroup$ Moreover, you start by asking "What does the Bellman equation actually telling? And are there many flavours of that?", but you're not even specifying which Bellman equation are you referring to. Then you say "I get a little confused when I look for the Bellman equation, because I feel like people are telling slightly different things about what it is", which people? Can you provide a link? That's what a good question should include (links and the context). This post is just too broad and brings up too many topics that are difficult to address in a single answer. $\endgroup$ – nbro Dec 21 '20 at 17:22
  • $\begingroup$ So, as I said, simplify this post as much as possible, but keep the relevant context and information. More importantly, now that there are already 2 answers (both of them seem to be good), try to leave the questions that those answers address. If you have more questions, ask them in another post, as I already said. $\endgroup$ – nbro Dec 21 '20 at 17:23
  • $\begingroup$ @nbro I will do that. Just give me a little time. $\endgroup$ – Johnny Dec 22 '20 at 17:43
2
$\begingroup$

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$ at time $t$ is equal to the expected value of the discounted sum of future rewards, where the expectation is taken with respect to $\pi(\cdot | s)$ the action policy and the environment dynamics $P$.

We will now define $$\sum_{i=0}^\infty \gamma^{i+t}r(s_{t+i}, a_{i+t}) = G_t$$

Now, we can rewrite this as $$\mathbb{E}_{a_i \sim \pi, s_i \sim P}\left[G_t | S_t =s\right] = \mathbb{E}_{a_i \sim \pi, s_i \sim P}\left[ r(s_t, a_t) + \gamma G_{t+1} | S_t =s\right].$$ The RHS is now in a nicer format and we can express it as $$\mathbb{E}_{a_i \sim \pi, s_i \sim P}\left[G_t | S_t =s\right] = \mathbb{E}_{a_i \sim \pi, s_i \sim P}\left[ r(s_t, a_t) + \gamma v_\pi(s') | S_t =s\right],$$ where $s'$ is the state that we transition into at time $t+1$. Note that $s'$ is a random variable and we are taking the expectation over this according to the action policy and the environment dynamics -- this is because the state we transition into depends first on the action we select and then the environment dynamics $P$.

You can see that we now have $$v_\pi(s) = \mathbb{E}_{a_i \sim \pi, s_i \sim P}\left[ r(s_t, a_t) + \gamma v_\pi(s') | S_t =s\right].$$ This is the Bellman equation (at least a form of it) and it expresses a recursive relationship between the values of states. That is, the value of being in state $s$ is equal to the expected immediate reward from being in this state plus the value of being in the state that we transition into. This relationship is useful in Reinforcement Learning as many algorithms use this equation to form update rules to approximate the value/state-action value function of the MDP, such as the SARSA algorithm, so it is more than just a philosophy, it is the driving force behind many of the RL algorithms.

Now, when I say at least a form of it, that is because in RL it is also common to see a Bellman equation for the state action value function $$q_\pi(s, a) = \mathbb{E}_{a_i \sim \pi, s_i \sim P}\left[ G_t | S_t = s, A_t = a\right] = \mathbb{E}_{a_i \sim \pi, s_i \sim P}\left[ r(s_t, a_t) + v_\pi(s') | S_t = s, A_t = a\right];$$ noting that the value function $v$ is the expectation of $q$ over the action space, i.e. we marginalise out the action we condition on -- thus there is the recursive relationship.

As pointed out in the comments for this question, it is also worth noting that Bellman equations originated in Dynamic Programming, which exist to solve planning problems such as the knapsack problem.

$\endgroup$
2
  • $\begingroup$ This answer provides a nice/concise derivation of how one can get to one Bellman equation, but, especially because the OP was confused about different definitions of the "Bellman equation", I think it is worth emphasing that when people say "Bellman equation" in RL they typically mean any of the recursive equations that involves some value function, not just the state value function, but what they specifically refer to may probably depend on the context. For example, Barto & Sutton sometimes refer to Q as also a Bellman equation. $\endgroup$ – nbro Dec 21 '20 at 1:17
  • 1
    $\begingroup$ So, first, it may also be worth saying that the Bellman equations are actually very important in RL, and they are not just "philosophy" (as the OP thinks). Moreover, you may also say that "Bellman equations" typically arise in dynamic programming (basically invented by Richard Bellman, hence the name) and that dynamic programming solutions exist to solve planning problems (i.e. value/policy iteration, which require the "model"), but DP is not just used in the context of MDPs, but used to solve traditional CS problems (the knacksack problem and so on). $\endgroup$ – nbro Dec 21 '20 at 1:19
1
$\begingroup$

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 objective function of form \begin{equation} V_N(s_0) = \sum_{k=0}^N J(s_k, a_k) \end{equation} while satisfying dynamic constraints $(1)$ where $J(\cdot)$ is a stage cost at time $k$. The product of this optimization are optimal control policies $a_k = \pi_k(s_k)$ which provide optimal value for the multistage objective function. Bellman's principle of optimality states that, for the multistage optimization problems, the objective function value at timestep $k$ should satisfy \begin{align} V^*_{k}(s_k) &= \min_{a_k}[J(s_k, a_k) + V^*_{k-1}(s_{k+1})]\\ &= \min_{a_k}[J(s_k, a_k) + V^*_{k-1}(f_d(s_k, a_k))] \end{align} This can be of course proven, you can find the proof in any optimal control/dynamic programming book.

This also makes intuitive sense. Consider that you are at timestep $N$ (end of trajectory you want to optimize). You only need to consider 1 action $a_N$. You would now go through all possible states $s_N$ and pick action $a_N$ which minimizes your stage cost $J(s_N, a_N)$ for all those states separately. After you did that, you would go one step backwards in time and find optimal action $a_{N-1}$ for all states $s_{N-1}$. According to the Bellman optimality principle, you only need to consider action $a_{N-1}$ in your optimization, because you already know action $a_N$ (calculated previously) which would minimize $J(s_N, a_N)$ for any possible future state $s_N$. Then you would keep going backwards in time until $k=0$. This is very useful because you don't need to consider all $N$ timesteps at once, you only consider one timestep at a time which prevents combinatorial explosion for large $N$. Bellman optimality principle has been adapted to many different applications, including RL and stochastic systems.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.