03 Bellman Optimality Equation

• 👆A special case of Bellman equation
• Two concepts: optimal policy ${\pi }^{\ast }$ & optimal state value

强化学习的最终目标是什么？

就是在求解最优策略

• One tool: Bellman optimality equation(BOE)

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

1. fixed-point theorem
2. fundamental problems
3. an algorithm solving the equation

Outline

• Optimal policy
• BOE: Introduction
• BOE: Maximization on the right-hand side
• BOE: Rewrite as v=f(v)
• Contraction mapping theorem
• BOE: Solution
• BOE: Optimality
• Analyzing optimal policies
• Summary

Analyzing optimal policies

$$\begin{array}{r}v(s)=\underset{\pi }{\max }\sum _a\pi (a\mid s)\underset{q(s,a)}{\underbrace{\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}\end{array}$$

• Known
  • Reward design: $r$
  • System model: $p(s^{\prime }|s,a),p(r|s,a)$
  • Discount rate: $\gamma$
• Unknown
  • $v(s),v(s^{\prime }),\pi (a\mid s)$

What matters is not the absolute reward values! It is their relative values!

奖励在通过线性变换之后最优state value会变，但最优策略是不会变的，从q的形式就可以看出来了，线性变换并不会影响q的相对大小，选择q最大的动作依然还是不变，所以最优策略不变。

奖励设计 vs $\gamma$

同样重要，比如在权衡1. 惩罚一次到达终点和2. 避免惩罚绕远路到达终点两个策略的时候

• 只考虑调整奖励设计
  • 惩罚区域的奖励为负数，绝对值很小的时候，当然模型会更倾向选1
  • 惩罚为负数，绝对值很大的时候，模型比较得出绕远路的return更高，就会倾向选2
• 只考虑调整$\gamma$
  • $\gamma$很小，比如<0.5，模型非常短视，一次惩罚也不肯接受，选择2
  • $\gamma$很大，接近1，比较远视，未来奖励累积过来也不会衰减很快，选择1

Summary

Bellman optimality equation:

• Elementwise form:

$$\begin{array}{r}v(s)=\underset{\pi }{\max }\sum _a\pi (a\mid s)\underset{q(s,a)}{\underbrace{\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}\end{array}$$

• Matrix-vector form:

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

回答最开始的四个问题

1. Existence: 这个公式存在解
2. Uniqueness: 解唯一，指的是$v^{\ast }$是唯一解，但${\pi }^{\ast }$不一定唯一
3. Algorithms: 解算法就用那个Iterative algorithm就可以了，初始化$v_0$，然后价值迭代
4. Optimality: 解是optimal state value，也可以推出optimal policy

Later

next⇒04 Value Iteration & Policy Iteration