Bellman Equation

The bellman equation relates the value of a current state with the value of successive states.

They decompose the Value Function into the immediate reward + expected future rewards. They are ways to concretely represent our different functions, and later solve them.

IMPORTANT

Make sure to understand the difference between the bellman expectation backup and bellman optimality backup. See at bottom.

Bellman Expectation Equation

Because it is a MDP, the value function can be decomposed into two parts: immediate reward $R_{t+1}$ discounted value of successor state $\gamma v(S_{t+1})$.

$$\begin{array}{rl}{v}_{\pi }(s)& ={\mathbb{E}}_{\pi }[G_t|S_t=s]\\ [3pt]& ={\mathbb{E}}_{\pi }[R_{t+1}+\gamma v(S_{t+1})|S_t=s]\\ [3pt]& =\sum _a\pi (a|s)\sum _{s^{\prime },r}p(s^{\prime },r|s,a)[r+\lambda v_{\pi }(s^{\prime })]\end{array}$$

We usually use an iterative algorithm to solve the Value Function, doing the following:

• Initialize $V_0(s)=0$ for all $s$
• Start at $k=1$ and continue until convergence (i.e. $|v_k-v_{k-1}|<ϵ$)
• $\forall s\in S$, $V_k^{\pi }(s)=R(s,\pi (s))+\gamma {\sum }_{s^{\prime }\in S}P(s^{\prime }|s,\pi (s))V_{k-1}^{\pi }(s^{\prime })$ The above is called a bellman expectation backup for a particular policy. It is basically the same equation as the iterative algorithm to solve for Markov Reward Process, we just plug in the policy, since MDP = MRP + policy.

We use this in Policy Evaluation.

The bellman equation is a linear equation. It also can be solved directly by solving the matrix, where $v=R+\lambda Pv$ $v=R(I-\gamma P{)}^{-1}$

Danger

After some reflecting, I am realizing why I see some inconsistencies.

Sometimes, I see this format $V=R+\gamma PV$ $V_k^{\pi }(s)=R(s,\pi (s))+\gamma {\sum }_{s^{\prime }\in S}P(s^{\prime }|s,\pi (s))V_{k-1}^{\pi }(s^{\prime })$ so the reward $R$ seems to be separate, but in other equations I see this form $v_{k+1}(s)={\sum }_a\pi (a|s){\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)(r+\gamma v_k(s^{\prime }))$

Actually, they both are the same. The first is for a deterministic policy, while the second is for a stochastic policy.

the capitalized version $R$ represents a Function, while a lowercase $r$ is a discrete value. These are all minor notation differences.

Principle of Optimality

Any Optimal Policy can be subdivided into two components:

1. An optimal first action $A_{\ast }$
2. Followed by an optimal policy from successor state $S^{\prime }$

Theorem (Principle of Optimality)

A policy $\pi (a|s)$ achieves the optimal value from state $s$, $v_{\pi }(s)=v_{\ast }(s)$, if and only if

• For any state $s^{\prime }$ reachable from $s$,
• $\pi$ achieves the optimal value from state $s^{\prime }$, $v_{\pi }(s^{\prime })=v_{\ast }(s^{\prime })$

Bellman Optimality Equation

The Bellman Optimality Equation defines how the optimal value of a state is related to the optimal value of successor states. It has a “max” instead of an average.

The optimal value functions are recursively related by the Bellman optimality equations:

$v_{\ast }(s)={\max }_a{\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)[r+\lambda v_{\ast }(s^{\prime })]$

For the State-val $q_{\ast }(s,a)={\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)[r+\lambda {\max }_{a^{\prime }}{q}_{\ast }(s^{\prime },a^{\prime })]$ Other notation: $Q_{\ast }(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{\max }_{a^{\prime }\in A}{Q}_{\ast }(s^{\prime },a^{\prime })$ #gap-in-knowledge review david silver lectures, I don’t understand the big picture, why does a 1-step lookahead give you the optimal policy? Page 86 of RL book

A greedy policy is actually optimal in the long-term sense in which we are interested because $v_{\ast }$ already takes into account the reward consequences of all possible future behavior.

By means of $v_{\ast }$, the optimal expected long-term return is turned into a quantity that is locally and immediately available for each state. Hence, a one-step-ahead search yields the long-term optimal actions.

Solving the Bellman Optimality Equation

Bellman Optimality Equation is non-linear.

• No closed form solution
• Instead, there are many iterative solution methods
  • Value Iteration
  • Policy Iteration
  • Q-Learning
  • Sarsa

Difference between Bellman Expectation and Bellman Optimality

In summary, we have bellman expectation (used in Policy Evaluation) $v_{k+1}^{\pi }(s)={\sum }_a\pi (a|s){\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)(r+\gamma v_k^{\pi }(s^{\prime }))$ Else, we have bellman optimality (used in Value Iteration), where we don’t have a policy, simply take the max action $v_{k+1}(s)={\max }_{a^{\prime }}{\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)[r+\lambda v_k(s^{\prime })]$ The difference is that we use the bellman expectation to get the expected values of a particular policy $\pi$. On the other hand, we can use the bellman optimality to get the optimal value function (these values are obtained if we can somehow find an optimal policy $\pi$).