VF example

Example of Value Function

From table to function

之前我们所有的state和action的值都是用表格来表示的。例如，state value:

State	$s_1$	$s_2$	$\cdots$	$s_n$
Value	$v_{\pi }(s_1)$	$v_{\pi }(s_2)$	$\cdots$	$v_{\pi }(s_n)$

又例如，action value:

State/Action	$a_1$	$a_2$	$a_3$	$\cdots$	$a_m$
$s_1$	$q_{\pi }(s_1,a_1)$	$q_{\pi }(s_1,a_2)$	$q_{\pi }(s_1,a_3)$	$\cdots$	$q_{\pi }(s_1,a_m)$
$⋮$	$⋮$	$⋮$	$⋮$	$\ddots$	$⋮$
$s_n$	$q_{\pi }(s_n,a_1)$	$q_{\pi }(s_n,a_2)$	$q_{\pi }(s_n,a_3)$	$\cdots$	$q_{\pi }(s_n,a_m)$

优缺点

优点： 直观且容易分析 缺点： 难以处理 large or continuous state or action spaces

而且tabular method还面临着两个问题：

1. storage: 当 state space 和 action space连续时，意味着我们需要存储无限多的值（无穷行和列）。
2. generalization: 由于我们的tabular是离散的，优化一个state-action pair时无法泛化到未见过的state或action。

Sutton书作为Part II Approximate Solution Methods的开篇，举了一个例子：the number of possible camera images is much larger than the number of atoms in the universe. 这就是为什么我们需要approximate solution methods。

An example

考虑一个例子：

• 有$n$个状态：$s_1,s_2,\cdots ,s_n$
• the state values are $v_{\pi }(s_1),v_{\pi }(s_2),\cdots ,v_{\pi }(s_n)$, where $\pi$ is a given policy
• n is very large! (or even infinite)
• use a simple curve to approximate these values(linear?polynomial-basis or fourier-basis?)

Use a simple straight line to fit the dots:

$$\hat{v}(s,w)=as+b=\underset{{\varphi }^T(s)}{\underbrace{[s,1]}}\underset{w}{\underbrace{\left[\begin{array}{c}a\\ b\end{array}\right]}}={\varphi }^T(s)w$$

• $w$ is the parameter vector
• $\varphi (s)$ is the feature vector of $s$
• $v(s,w)$ is linear in $w$

Difference between the tabular and function methods

How to retrieve the value of a state?

• 这个问题主要是在讨论$\varphi (s)$的 representation
• represented by a table, 那么我们可以直接通过state index $s$来获取值
• represented by a function, 那么我们需要通过$\varphi (s)$来input state index $s$ and calculate the value

For example, $s\to \varphi (s)\to {\varphi }^T(s)w=\hat{v}(s,w)$

解决了storage的问题，不用存储整个$\mathcal{S}$无穷多的state value，而是存储一个lower-dimensional的映射 $w$即可

How to update the value of a state?

• tabular: directly, rewrite the value in the table
• function: indirectly, update the parameter vector $w$

解决了generalization的问题，我们可以泛化到未见过的state或action，update $\hat{v}(s,w)$ by changing $w$ ⇒ the values of neighboring states will also change

Every coin has two sides

• 使用 function 也会带来一些问题
• 我们无法精确表示所有是state values
• 所有又叫 function approximation
• 解决方法是使用high-order (e.g. polynomial) or non-linear functions (e.g. neural networks)

High-order curves:

$$\hat{v}(s,w)=a{s}^2+bs+c=\underset{{\varphi }^T(s)}{\underbrace{[s^2,s,1]}}\underset{w}{\underbrace{\left[\begin{array}{c}a\\ b\\ c\end{array}\right]}}={\varphi }^T(s)w$$

• dimensions of $\varphi (s)$ and $w$ are increased
• linear in $w$, nonliearity in $\varphi (s)$

有意思的地方

在神经网络中，我们有

• $Y=\sigma (WX+b)$
• linear in $W$, nonlinearity in $\sigma$

刚好和这里的顺序是倒过来的，对比一下：

• 基函数方法：先非线性每个特征 ⇒ 再线性叠加 （一次，其实也可以多次但看起来很怪）
• 神经网络方法：先线性叠加特征 ⇒ 再非线性激活 ⇒ 线性叠加 …（多次）

Summary

• Idea: 使用parameterized functions来近似state和action values
• Key difference: 如何获取和改变$v(s)$的值
• Advantages：
  1. Storage: $w$的维度可能远小于$S$
  2. Generalization: 当访问一个state $s$时，更新参数$w$，使得其他未访问的state的值也会被更新