Notes

Bellman Equation The Bellman Equation (BE), named after Richard E. Bellman, is a necessary condition for optimality associated with the mathematical optimization method known as dynamic programming (aka. RL when the environment is known MDP). It allows us to "solve" the MDP problem, the problem of not knowing how to act in an environment where we are able to take action.

BE in MRP In the most simple case, we can just evaluate the Bellman expectation equation in an MRP where we have no policy to optimize.

This is the immediate reward $R_{t + 1}$ plus the discounted value of the successor state $\gamma v\left( S_{t + 1} \right)$. This is again close to the temporal difference rule. If we move the reward from the next state to the current one (by definition), we can pull $R_{s_{t}}$ out of it and compute the expected value through the sum and the equation becomes:

$$v_{s_{t}} = R_{s_{t}} + \gamma\sum_{s_{t + 1} \in S}^{}{P_{s_{t},s_{t + 1}}v\left( s_{t + 1} \right)}$$

In figure below, we have an example computation of the value of the red node in an MRP.

One might argue that this leads to action values by choosing the next state based on its value "score". Also this can be solved explicitly as a linear system.

BE in MDP In MDP, we must somehow include the actions. Over the entire task, the actions we take are defined to be the policy. Since we can optimize this policy, one might ask how to do this using the Bellman optimality equation.

• The state-value function $v_{\pi}(s)$ of an MDP is the expected return starting from state s, and then following policy$\ \pi$.
• The action-value function $q_{\pi}(s,a)$ is the expected return starting from state s, taking action a, and then following policy $\pi$.

We may rewrite both in a similar manner as we did in the MRP case.

And if we again shift the reward:

As you can see, the notation becomes quite tedious. From now on we use $S_{t} = s\ and\ \, S_{t + 1} = s^{'}$. The same applies to actions. In the figure below we have an example of policy based computation of the value of the red node in an MDP.

Finding the optimal action-value (Q) function We can now define the optimal value function:

$$v^{*}(s) = max\left( v_{\pi}(s) \right)$$

and the optimal action-value (q) function:

$$q^{*}(s,a) = max\left( q_{\pi}(s,a) \right)$$

You may have noticed that we depend on the policy for $v^{*}(s)$ and $q^{*}(s,a)$. An optimal policy can be found by maximizing the optimal Q-function $q^{*}(s,a)$:

There is always a deterministic optimal policy for any MDP. If we know $q^{*}(s,a)$, we immediately have the optimal policy. In the last step, this theorem allows us to assemble the Bellman optimality update equations. We now use the optimal value function ($v^{*}(s) = max\left( v_{\pi}(s) \right))$ to get the optimal Q-function:

$$q_{\pi}^{*}(s,a) = R_{t}^{a} + \gamma\sum_{s^{'} \in S}^{}P_{s,s^{'}}^{a}v^{*}\left( s^{'} \right)$$

Note that the agent has to average, because we can't choose. This is decided by the environment. Finally we may write down the Bellman optimality equations for $v^{*}$ and $q^{*}$:

Bellman figured out that our policy being optimal means that we can be greedy w.r.t these optimality equations. If we update over and over again, we will converge to a fixed point which is the optimality policy.

• The Bellman Optimality Equation is non-linear.
• No closed form solution (in general).
• Many iterative solution methods.
  • Iterative Policy Evaluation.
  • Iterative Value Evaluation.
  • Q-Learning.