Bellman Equation

Related to Value Based Methods. Mathematics and ideas taken from Steven.

FUNDAMENTAL IDEA: Consider the value of any state as:

$$\text{Value}=\text{immediate reward}+\text{discounted sum of future rewards (values)}$$

i.e.

$$V^{\pi }(s)={\mathbb{E}}_{\pi }[r+\gamma V^{\pi }(s^{\prime })]$$

The bellman equation relates the value of a current state with the value of successive states. Apparently the problem is divided in bellman expectation and bellman optimality.

• the expectation is used in Policy Evaluation which defines the expected value of a state relating to successor states.

$$\begin{array}{rl}{V}^{\pi }(s)& ={\mathbb{E}}_{a\sim \pi (\cdot |s),s^{\prime },r\sim p(\cdot |s,a)}[r+\gamma V^{\pi }(s^{\prime })]\\ & =\sum _a\pi (a|s)\sum _{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma V^{\pi }(s^{\prime })]\\ & \\ Q^{\pi }(s,a)& ={\mathbb{E}}_{s^{\prime },r\sim p(\cdot |s,a)}[r+\gamma {\mathbb{E}}_{a^{\prime }\sim \pi (\cdot |s^{\prime })}{Q}^{\pi }(s^{\prime },a^{\prime })]\\ & =\sum _{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma \sum _{a^{\prime }}\pi (a^{\prime }|s^{\prime })Q^{\pi }(s^{\prime },a^{\prime })]\end{array}$$

We can write it recursively:

$$\begin{array}{rl}v(s)& =\mathbb{E}[R_{t+1}+v(S_{t+1})\mid S_t=s]\\ & \\ q(s,a)& =\mathbb{E}[R_{t+1}+q(S_{t+1},A_{t+1})\mid S_t=s,A_t=a]\end{array}$$