What is the Bellman Equation actually telling?

Question

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.

Answer 1

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.

Answer 2

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.