Chapter 3 Optimal Policy and Bellman Optimality Equation

We know that RL's ultimate goal is to find the optimal policy. In this chapter we will show how we obtain optimal policy through Bellman Optimality Equation.

Optimal Policy

The state value could be used to evaluate if a policy is good or not: if

$$v_{\pi_{1}}(s) \ge v_{\pi_{2}}(s), \ \ \forall s \in \mathcal S$$

We say policy $\pi_{1}$ is 'better' than $\pi_{2}$.

If

$$v_{\pi^*}(s) \ge v_{\pi}(s), \ \ \forall s \in \mathcal S under \forall \pi$$

We say policy $\pi^*$ is the optimal policy.

Here comes the questions:

• Does the optimal policy exist?

• Is the optimal policy unique?

• Is the optimal policy stochastic or deterministic?

• How to obtain the optimal policy?

Bellman Optimality Equation (BOE) will give you the answers.

Bellman optimality equation (BOE)

Bellman optimality equation (elementwise form):

$$\begin{align} v(s) &= \max_{\pi} \sum_{a} \pi(a\mid s) \Bigl( \sum_{r} p(r\mid s,a)\,r + \gamma \sum_{s'} p(s'\mid s,a)\,v(s') \Bigr), \quad \forall s \in \mathcal S,\\ &= \max_{\pi} \sum_{a} \pi(a\mid s)\,q(s,a), \quad s \in \mathcal S. \end{align}$$

Notes:

• $p(r|s, a), p(s_0 |s, a)$ are known.

• v(s), v(s_0) are unknown and to be calculated.

• $\pi(s)$ can be written with other $\pi(s)$.

Bellman optimality equation (matrix-vector form):

$$v = \max_{\pi} (r_{\pi} + \gamma P_{\pi}v)$$

The expression contains two unknown elements, namely the policy $\pi$ and state value $v$. So we need find an approach to solve it. But before introducing the solving algorithm, we need to learn some preliminaries through some intersting exapmles.

Motivating examples

As mentioned above, BOE has two unknowns from one equation. How to solve problems like this? See the following exapmle:

提示

Example (How to solve two unknowns from one equation

Okay, we know that the way is to fix one unknown and solve the equation. Suppose we fix $v(s \prime)$ on the rightside of the equation.

$$\begin{align} v(s) &= \max_{\pi} \sum_{a} \pi(a\mid s) \Bigl( \sum_{r} p(r\mid s,a)\,r + \gamma \sum_{s'} p(s'\mid s,a)\,v(s') \Bigr), \quad \forall s \in \mathcal S,\\ &= \max_{\pi} \sum_{a} \pi(a\mid s)\,q(s,a), \quad s \in \mathcal S. \end{align}$$

We know that $\max_{\pi} \sum_{a}=1$. We will need to solve is the maximum with different probability assigned to each action value. So a similar exapmle goes:

提示

Example (How to solve max)

So through that example, we will know how to gain optimal policy. That is to adopt the action with largest action value in all state.

gain

Solve the Bellman optimality equation

Preliminaries

• Fixed point: $x \in X$ is a fixed point of $f : x \to X$ if :

$$x = f(x)$$

• Contraction mapping: $f$ is a contraction mapping if:

$$\left | \right | f(x_1)- f(x_2) \left | \right | \le \gamma \left | \right | x_1- x_2 \left | \right |, \ \ \gamma < 1$$

提示

example

So here we can introduce the important theorem:

重要

Contraction mapping theorem

Examples like: $x = 0.5x$ ,$x_{k+1} = 0.5x_k$ . Suppose that $x_0 = 10$ So $x_1 = 5, x_2 = 2.5 ...... x \to 0$

Contraction property of BOE

The Bellman Equation:

$$v = \max_{\pi} (r_{\pi} + \gamma P_{\pi}v)$$

can be regarded as the function of $v$. So it can write like:

$$v=f(v)$$

And $f(v) is a contraction mapping.

So we can utilize the Contraction mapping theorem to solve BOE.

Applying the contraction mapping theorem to solve BOE

Iterative algorithm

Matrix vector form:

$$v_{k+1} \;=\; f(v_k) \;=\;\max_{\pi}\bigl(r_{\pi} + \gamma\,P_{\pi}\,v_k\bigr)$$

Elementwise form:

$$\begin{align*} v_{k+1}(s) &= \max_{\pi}\sum_{a}\pi(a\!\mid\!s)\Bigl(\sum_{r}p(r\!\mid\!s,a)\,r + \gamma\sum_{s'}p(s'\!\mid\!s,a)\,v_k(s')\Bigr),\\ &= \max_{\pi}\sum_{a}\pi(a\!\mid\!s)\,q_k(s,a),\\ &= \max_{a}q_k(s,a). \end{align*}$$

The procedure goes:

procedure

提示

example

Actions: $a_l , a_0, a_r$ represent go left, stay unchanged, and go right.

Reward: entering the target area: +1; try to go out of boundary -1.

example

example

example

Factors determine the optimal policy

• Reward design: $r$

• System model: $p(s_0|s, a), p(r|s, a)$

• Discount rate: $\gamma$, affecting whether the model is short-sighted or not.

• $v(s), v(s_0), π(a|s) are unknowns to be calculate.