BOE Bellman Optimality Equation

Bellman Optimality Equation

Introduction

Bellman optimality equation (elementwise form):

$$\begin{array}{rl}v(s)& =\underset{\pi }{\max }\sum _a\pi (a\mid s)\left[\sum _{r}p(r\mid s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }\mid s,a)v(s^{\prime })\right]\forall s\in \mathcal{S}\\ & =\underset{\pi }{\max }\sum _a\pi (a\mid s)q(s,a)\forall s\in \mathcal{S}\end{array}$$

• $p(r\mid s,a),p(s^{\prime }\mid s,a)$ are known
• $v(s),v(s^{\prime })$ to be calculated
• $\pi (a\mid s)$ unknown to be optimized

两个细节

• 下标去哪了？ 会想起我们的Bellman equantion形式实际是

  $$v_{\pi }(s)=\sum _a\pi (a\mid s)q_{\pi }(s,a)$$

  这里的最优公式为什么会下标$\pi$不见了呢，就是因为策略已经是确定的一个值（${\max }_{\pi }{v}_{\pi }(s)$之后找到${\pi }^{\ast }$），所以就不再依赖它了。

• ${\max }_{\pi }$是啥意思？ 这里的max是指相对与其它所有的$\pi$的当前的状态值都要大就可以了，实际上如果把$\pi$当成一个参数来看会更容易理解。假设有m个动作，我们就相当于每个状态有m个概率，通过分配概率的分布去调整状态值的大小，我们希望对于每个状态而言，都可以调整得出一个最大的状态值。

矩阵形式

$$\begin{array}{rl}v& =\underset{\pi }{\max }(r_{\pi }+\gamma P_{\pi }v)\\ & =\underset{\pi }{\max }\pi @(P_{r}R+\gamma P_{s}v)\\ & =\underset{\pi }{\max }\pi @q\end{array}$$

questions:

• have solutions? Existence
• how to solve? Algorithm
• solution unique? Uniqueness
• optimal? Optimality

Maximization on the right-hand side

Fix all $v(s^{\prime })$，and then $q(s,a)$ if fixed, solve $\pi$

$$v(s)=\underset{\pi }{\max }\sum _a\pi (a\mid s)q(s,a)\forall s\in \mathcal{S}$$

Consider ${\sum }_a\pi (a\mid s)=1$, we have

$$\underset{\pi }{\max }\sum _a\pi (a\mid s)q(s,a)=\underset{a\in \mathcal{A}(s)}{\max }q(s,a)\forall s\in \mathcal{S}$$

where the optimality is achieved when

$$\pi (a\mid s)=\{\begin{array}{rl}1& a=a^{\ast }\\ 0& a\ne a^{\ast }\end{array}$$

where $a^{\ast }={\mathrm{argmax}}_{a}q(s,a)$.

简单中文描述

对于当前状态$s$ ⇒ 下一个状态$s^{\prime }$

1. 首先固定下一个状态值，这样我们在求解的时候q值也是固定的了
2. 对于当前状态，假设我们有m个动作，要选择的m个动作的概率之和为1
3. 对于当前状态，我们又知道q值了，有m个q值，我们要求的当前状态值其实就是加权平均q值
4. 显然我们把权重都放在最大q值上即可有最大当前状态值

Rewrite as v=f(v)

The BOE is $v={\max }_{\pi }(r_{\pi }+\gamma P_{\pi }v)$, Let

$$f(v):=\underset{\pi }{\max }(r_{\pi }+\gamma P_{\pi }v)$$

Then the BOE becomes

$$v=f(v)$$

where

$$[f(v){]}_s=v(s)=\underset{\pi }{\max }\sum _a\pi (a\mid s)q(s,a)\forall s\in \mathcal{S}$$

Imagine the v is a vector, then $v(s)$ or $[f(v){]}_s$ just selects the sth element

Preliminiary: Contraction mapping therom

Solution

$$v=f(v)=\underset{\pi }{\max }(r_{\pi }+\gamma P_{\pi }v)$$

• $f(v)$ is a contraction mapping satisfying

$$\Vert f(v_1)-f(v_2)\Vert \le \gamma \Vert v_1-v_2\Vert$$

• where $\gamma$ is the discount rate
• exists a solution $v^{\ast }$
• solution is unique
• algo: $v_{k+1}=f(v_k)={\max }_{\pi }(r_{\pi }+\gamma P_{\pi }{v}_k)$
• $\{v_k\}$ converges to $v^{\ast }$ exponentially fast

Optimality

Suppose $v^{\ast }$ is the solution to BOE. It satisfies

$$v^{\ast }=\underset{\pi }{\max }(r_{\pi }+\gamma P_{\pi }{v}^{\ast })$$

Suppose

$${\pi }^{\ast }=\arg \underset{\pi }{\max }(r_{\pi }+\gamma P_{\pi }{v}^{\ast })$$

Then

$$v^{\ast }=r_{{\pi }^{\ast }}+\gamma P_{{\pi }^{\ast }}{v}^{\ast }$$

policy optimality

$$v^{\ast }=v_{{\pi }^{\ast }}\ge v_{\pi },\forall \pi$$

Greedy Optimal Policy

$${\pi }^{\ast }(a\mid s)=\{\begin{array}{rl}1& a=a^{\ast }(s)\\ 0& a\ne a^{\ast }(s)\end{array}\forall s\in \mathcal{S}$$

where

• $a^{\ast }=\arg {\max }_a{q}^{\ast }$
• $q^{\ast }=P_{r}R+\gamma P_s{v}^{\ast }$

$$\begin{array}{r}{\pi }^{\ast }(s)=\arg \underset{\pi }{\max }\sum _a\pi (a\mid s)\underset{q^{\ast }(s,a)}{\underbrace{\left(\sum _{r}p(r\mid s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }\mid s,a)v^{\ast }(s^{\prime })\right)}}\end{array}$$

policy_star = action_star.one_hot()